# US 2014/0208076 A1 · Dfa compression and execution > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2014/0208076 A1 - Document ID: US20140208076A1 - Status: Published application - Kind: A1 - Application number: 13/747,538 - Filed: 2013-01-23 - Published: 2014-07-24 - Earliest claimed: 2013-01-23 - Assignees: LSI Corporation - Applicants: Lsi Corporation - Inventors: Michael Ruehle - Web page: https://patentgrep.com/patent/US20140208076A1 ## CPC - G06F 9/30079: {Pipeline control instructions, e.g. multicycle NOP} - H04L 63/0245: {Filtering by information in the payload} - G06N 5/025: Extracting rules from data - G06N 7/01: Probabilistic graphical models, e.g. probabilistic networks - G06N 20/00: Machine learning - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) - G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS ## 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. ## Claims ### Claim 1 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. ### Claim 2 (depends on 1) The method of claim 1, wherein each single symbol class is represented by a character class code. ### Claim 3 (depends on 1) 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. ### Claim 4 (depends on 1) The method of claim 1, wherein each of said character classes matches a transition in an NFA constructed from a ruleset. ### Claim 5 (depends on 1) 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. ### Claim 6 (depends on 1) 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. ### Claim 7 (depends on 1) 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 mapping according to the results of said step of comparing. ### Claim 8 (depends on 7) 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. ### Claim 9 (depends on 1) 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. ### Claim 10 (depends on 9) 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. ### Claim 11 (depends on 1) 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 mapping and Venn diagram analysis according to the results of said step of comparing. ### Claim 12 (depends on 7) 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. ### Claim 13 (depends on 5) The method of claim 5, wherein the programmable classes are mask classes stored in multiple consecutive CCL memory words. ### Claim 14 A system for character class encoding and DFA execution in a DFA engine, comprising: a compiler enabled to encode ruleset instructions with character class codes; and an instruction execute pipeline, said pipeline comprising at least one CCL memory; wherein said pipeline is enabled to extract said character class codes from the instructions and access a corresponding character class from said at least one CCL memory, and compare the accessed character class with an input symbol to determine if the input symbol is a member of the character class represented by said character class code and to execute a DFA transition based on the determination of character class representation. ### Claim 15 (depends on 9) The system of claim 9, wherein the character class codes comprise fixed codes and programmable codes. ### Claim 16 (depends on 9) The system of claim 9, 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. ### Claim 17 (depends on 14) The system of claim 14, wherein the pipeline executes the instruction using at least one of priority mapping and a Venn diagram. ### Claim 18 A system for character class encoding and DFA execution in a DFA engine, comprising: a compiler enabled to encode ruleset instructions with character class codes; and an instruction execute pipeline, said pipeline comprising at least one CCL memory; 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.