DFA compression and execution
View Patent ↗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.
1. A method of character class encoding and DFA (deterministic finite automaton) execution in a DFA engine wherein an instruction execute pipeline in said DFA engine comprises at least one CCL (character class) 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, wherein at least one symbol is a member of at least two character classes;
representing, with at least a plurality of instructions, transitions of one or more DFA states, wherein each instruction comprises at least one character class code;
extracting at least two character class codes from an instruction of the plurality of instructions;
accessing said at least one character class memory to retrieve at least two accessed character classes that corresponds to the at least two character class codes;
matching a current input symbol with said at least two accessed character classes; and
executing the instruction to determine a transition to a next state.
2. The method of claim 1 , wherein each single symbol class is represented by a character class code.
3. The method of claim 1 , wherein each of a plurality of single symbol classes is represented by a character class code and each of a plurality of fixed, multi-symbol classes is represented by a character class code.
4. The method of claim 1 , wherein each of said character classes matches a transition in an NFA (nondeterministic finite automaton) constructed from a ruleset.
5. The method of claim 1 , wherein each of a plurality of single symbol classes is represented by a character class code, each of a plurality of fixed, multi-symbol classes is represented by a character class code, and each of a plurality of programmable classes is represented by a character class code.
6. The method of claim 1 , further comprising storing at least one equivalence class map in the character class memory and accessing a word of the equivalence class map determined by an equivalence class map reference in the instruction and an input symbol.
7. The method of claim 1 , wherein the at least one character class comprises at least two character class codes and the step of executing the instruction comprises using priority encoding according to the results of said step of comparing.
8. The method of claim 7 , wherein at least two instructions are used to encode the transition from a DFA state and if no character class codes in a first instruction match the current input symbol, then the character classes from a second instruction are used to determine the transition to the next state.
9. The method of claim 1 , wherein the at least one character class code comprises at least two character class codes and the step of executing the instruction comprises using Venn diagram analysis according to the results of said step of comparing.
10. The method of claim 9 , wherein at least two instructions are used to encode the transition from a DFA state and if no character class codes in a first instruction match the current input symbol, then the character classes from a second instruction are used to determine the transition to the next state.
11. The method of claim 1 , wherein the at least one character class comprises at least two character class codes and the step of executing the instruction comprises using priority encoding and Venn diagram analysis according to the results of said step of comparing.
12. The method of claim 7 , wherein at least two instructions are used to encode the transition from a DFA state and if no character class codes in a first instruction match the current input symbol, then the character classes from a second instruction are used to determine the transition to the next state.
13. The method of claim 5 , wherein the programmable classes are mask classes stored in multiple consecutive CCL memory words.
14. A system for character class encoding and DFA (deterministic finite automaton) execution in a DFA engine, comprising:
a compiler enabled to represent, with at least a plurality of instructions, transitions of one or more DFA states, wherein each instruction comprises at least one character class code; and
an instruction execute pipeline, said pipeline comprising at least one CCL (character class) memory, wherein at least one symbol is a member of at least two character classes;
wherein said pipeline is enabled to extract character class codes from the plurality of instructions and access at least two corresponding character classes from said at least one CCL memory, and match an input symbol with the at least two accessed character classes and to execute a DFA transition based on the determination of character class representation.
15. The system of claim 14 , wherein the character class codes comprise fixed codes and programmable codes.
16. The system of claim 14 , wherein the character class codes comprise fixed codes and programmable codes and wherein the pipeline is further enabled to compare character classes corresponding to fixed classes by dedicated logic without accessing one of the plurality of CCL memories.
17. The system of claim 14 , wherein the pipeline executes the instruction using at least one of priority encoding and a Venn diagram.
18. A system for character class encoding and DFA (deterministic finite automaton) execution in a DFA engine, comprising:
a compiler enabled to represent, with at least a plurality of instructions, transitions of one or more DFA states, wherein each instruction comprises at least one character class code; and
an instruction execute pipeline, said pipeline comprising at least one CCL (character class) memory, wherein at least one symbol is a member of at least two character classes;
wherein at least one equivalence class map is stored in said at least one CCL memory and said pipeline is enabled to access a word of said equivalence class map, said word being determined by an equivalence class map reference in an instruction and an input symbol.
19. One or more non-transitory, machine-readable storage media comprising a plurality of instructions stored thereon that in response to being executed cause a computing device to:
store a plurality of character classes in at least one character class memory;
represent the plurality of character classes with a plurality of character class codes, wherein at least one symbol is a member of at least two character classes;
represent, with at least a plurality of instructions, transitions of a DFA, wherein each instruction comprises at least one character class code;
extract at least two character class codes from an instruction of the plurality of instructions;
access said at least one character class memory to retrieve at least two accessed character classes that corresponds to the at least two character class codes;
match a current input symbol with said at least two accessed character classes; and
execute the instruction to determine a transition to a next state.
20. The one or more non-transitory, machine-readable media of claim 19 , wherein the instructions further cause the computing device to store at least one equivalence class map in the character class memory and access a word of the equivalence class map determined by an equivalence class map reference in the instruction and an input symbol.