High speed data stream pattern recognition

The method of recognizing a particular pattern formed by a plurality of bytes in stream of bytes, said method operating in a series of states, and utilizing:

• a plurality of lookup tables, one for each of said plurality of bytes, each lookup table having a section associated with each state;
• a first index table for storing a plurality of index bits associated with each particular state;
• and
• a next state table for storing data words, each of which indicates the next state and/or a special operation flag,
• said method including the following steps in each particular state in a series of states;
• a) interrogating a particular section of each lookup table utilizing the value of the associated byte to determine the value of a series of bits, said particular section of each lookup table being based on the particular state;
• b) generating a pointer which specifies the address of a data word in said next state table from a combination of the selected values from the lookup tables and a value from the first index table associated with the particular state;
• c) reading the particular data work specified in step “b” and based on the contents of said data word proceeding to the next state and/or performing operations indicated by a flag in said data work;
• and
• d) repeating steps “a”, “b” and “c” until a flag in said next state table indicates an end of the operation.

An integrated circuit for recognizing a plurality of characters in parallel, said integrated circuit operating in series of states, and said integrated circuit including:

• a plurality of lookup tables, one for each of said characters, each lookup table having a section associated with each state;
• an index table for storing a plurality of index bits for each state;
• and
• a next state table for storing data words, each of which indicates the next state of said state machine,
• said integrated circuit performing the following steps in a plurality of particular states;
• a) interrogating the section of said lookup table associated with said particular state and generating a series of bits based on the value of the associated character;
• b) generating a pointer which specifies the address of a data word in said next state table from a combination of the selected values from the lookup tables and a value from said first index table;
• c) reading the particular data word specified in step “b” and proceeding to the state specified by said data word;
• and
• d) repeating steps “a”, “b” and “c” until said operation ends.

A method for evaluating in parallel a plurality of characters in a stream of bytes, said method operating in a series of states and utilizing a set of alphabet lookup tables, one lookup table for each of said plurality of characters, each lookup table having a section associated with each of said states, and a next state table, said method comprising:

• a) selecting an alphabet lookup table from said set of alphabet tables, as a function of a current state and byte position within said set of bytes, and obtaining a class code from said selected alphabet table corresponding to the character represented by said byte;
• b) selecting a value from said next state table as a function of the current state, and generating an indication of the next state from said class codes of said set of bytes and from said value from said next state table;
• and
• c) repeating steps “a” and “b” until said state machine arrives at acceptance state or until entering a failure state.

A system for recognizing a particular pattern formed by a number of bytes in a stream of bytes, said number being at least one, said system operating in a series of states, and said system including:

• a lookup table for each byte in said number of bytes, each lookup table having a section associated with each state;
• a first index table which has index data associated with each state, the index data associated with each state comprising a plurality of index bits;
• and
• a next state table which has a data word associated with each state, each data word having data that specifies the next state and/or a special flag;
• said system performing the following steps in each particular state of a series of states;
• a) interrogating a particular section of each lookup table utilizing the value of each of said bytes to determine the value of a series of bits, said particular section of each lookup table being determined by the particular state;
• b) generating a pointer from a combination of the series of bits generated by the lookup tables and bits in the current state location in said first index table, said pointer specifying the address of a particular data word in said next state table;
• c) reading the particular data word specified by the pointer generated in step “b” and based on the contents of said data word proceeding to the next state specified by said data word and/or performing special operations in response to said flag;
• and
• d) repeating steps “a”, “b” and “c” until an end of operation is indicated by said flag.