Back to results
US 8,898,094 B2Granted
NFA character class matching
AssigneeLSI Corporation
InventorMichael Ruehle
Life of this patent
Estimating the term…
Abstract
Disclosed is method of matching a character class to a symbol of an input stream. A character class, or a plurality of character classes, is defined into an accessible format which when accessed is compared to a symbol in an input stream. The format may be stored in an NFA array cell or it may be broadcast to the cell array with an input symbol for comparison.
Claims16
A method of matching character classes (CCLs) from an NFA in an NFA cell array, said method comprising:
- encoding information of at least one frequent CCL in a frequent CCL table;
- accessing a location in the frequent CCL table indicated by an input symbol;
- broadcasting the content of that location, which is a membership vector, to each cell in the NFA cell array;
- broadcasting the input symbol to each cell in the NFA cell array;
- and
- in an NFA cell, using the encoded frequent CCL to select a bit in the membership vector, said bit indicating membership in the frequent CCL.
3 more elements
A system of matching character classes (CCLs) from an NFA in an NFA cell array, said system comprising:
- a frequent CCL table;
- an input stream comprising a plurality of input symbols;
- a loader enabled to receive NFA instructions and configure the NFA cells;
- and
- a plurality of NFA cells enabled to receive information from the frequent CCL table, loader and input stream;
- wherein the input stream provides symbols to the frequent CCL table and the NFA cells, the frequent CCL table utilizes the input symbol to access a membership vector, the membership vector and symbols from the input stream are broadcast to each cell in the NFA cell array, and a bit from the membership vector is selected to determine membership in a CCL.
3 more elements
Dependencies are inferred from the claim text.