Complex NFA state matching method that matches input symbols against character classes (CCLs), and compares sequence CCLs in parallel
View Patent ↗Disclosed is a method and system for matching a complex NFA state comprising a spinner followed by a character class sequence which may be represented by the general regular expression form [S] {N,M}[A0][A1] . . . [Ak−1]. An input transition activates the spinner and the spin count increments with successive matches of the spin class [S]. When the spin count is between N and M, sequence matching begins. Several base sequence CCLs are compared in parallel with a corresponding window of input symbols. If all match, a signal enters a delay line until the end of the base sequence. When the signal exits the delay line, extended sequence CCLs are accessed from a table sequentially and compared with successive input symbols. After the final extension CCL matches, an output transition is signaled. For short sequences, unused base sequence CCLs may be configured with look-ahead classes.
1. A method of matching an NFA (nondeterministic finite automaton) state in at least one cell of an NFA cell array, said state comprising a spinner, said spinner comprising a spin class, followed by a CCL (character class) sequence, said method comprising:
configuring the at least one cell with predetermined information;
activating the spinner via an input transition signal to the cell;
incrementing a spin count pursuant to successive successful matches of the spin class with input symbols from an input stream;
when the spin count ranges from a predetermined minimum to a predetermined maximum, beginning sequence matching; and
comparing a predetermined number of the sequence CCLs in parallel with input symbols.
2. The method of claim 1 , wherein said predetermined number of the sequence CCLs comprises a portion of the CCL sequence, wherein any portion of the CCL sequence not comprised of the predetermined number is an extended CCL sequence.
3. The method of claim 2 , said method further comprising, if the CCL sequence comprises an extended sequence:
accessing a first extended sequence CCL, and comparing the first extended sequence CCL with a successive input symbol from the input stream; and
if the first extended sequence CCL matches the successive input symbol, continuing to access remaining extended sequence CCLs, and comparing said remaining extended sequence CCLs with further successive input symbols from the input stream.
4. The method of claim 2 , said method further comprising, if the CCL sequence does not comprise an extended sequence, signaling an out transition.
5. The method of claim 1 , wherein the step of comparing a predetermined number of sequence CCLs in parallel comprises comparing the predetermined number of sequence CCLs in parallel with a corresponding number of successive input symbols.
6. The method of claim 1 , wherein the step of comparing a predetermined number of sequence CCLs in parallel comprises comparing the predetermined number of sequence CCLs in parallel with the same input symbol.
7. The method of claim 5 , further comprising:
if all of the predetermined number of the sequence CCLs successfully match the input symbols, entering a delay line with a length corresponding to the length of the predetermined number of the sequence CCLs;
when the delay line terminates, accessing at least one extended sequence CCL; and
comparing the at least one extended sequence CCL with a successive input symbol from the input stream.
8. The method of claim 3 , further comprising:
signaling an out-transition when the predetermined number of the sequence CCLs successfully matches the corresponding input symbols or when a final extended sequence CCL matches an input symbol.
9. The method of claim 3 , wherein:
said predetermined information configured in the at least one cell comprises a plurality of base CCLs stored in a plurality of storage units said base CCLs being used in the step of comparing a predetermined number of the CCL sequence in parallel, at least one extended sequence CCL which is stored in a table in the cell and which is used in the step of accessing a first extended sequence CCL, a spin minimum, a spin maximum, and an extended sequence length field.
10. The method of claim 9 wherein said spin count is a vector.
11. The method of claim 9 wherein said spin count is binary.
12. The method of claim 1 , further comprising:
if at least one of the predetermined number of CCL sequences does not successfully match the input symbols, terminating the NFA state.