US 2014/0208076 A1 · DFA COMPRESSION AND EXECUTION

Abstract

A character class (CCL) memory containing simple CCLs represented by encoding contained symbols or minimum and maximum symbols of a range, complex CCLs represented by bit-masks indicating contained symbols, and equivalence class (EC) maps represented as tables of ED values for each symbol value. Determining a next DFA transition by comparing multiple CCLs with a single input symbol, and selecting a transition according to the first matching CCL, or selecting a transition corresponding to a vector of CCL match result bits. Comparing CCLs from one DFA instruction to determine a transition and if no CCLs match, comparing CCLs from a second DDFA instruction to determine the transition. Matching linear sequence of two or more DFA states using a sequence of multiple CCLs encoded in a single DFA instruction.

Claims18

Dependent claims

A method of character class encoding and DFA execution in a DFA engine wherein an instruction execute pipeline in said DFA engine comprises at least one CCL memory, the method comprising:

storing a plurality of character classes in said at least one character class memory;
representing the plurality of character classes with a plurality of character class codes;
extracting at least one character class code from an instruction;
accessing said at least one character class memory to retrieve at least one accessed character class that corresponds to the at least one character class code;
comparing a current input symbol with said at least one accessed character class;
and
executing the instruction to determine a transition to a next state.

4 more elements

Dependencies are inferred from the claim text.

Dfa compression and execution

Life of this patent

Dfa compression and execution

Life of this patent

Abstract

Claims18