Start pointer tracking in NFAs
OwnerMichael Ruehleinventor
Life of this patent
Estimating the term…
Abstract
In a hardware engine, finding rule matches within an input stream by executing a Nondeterministic Finite Automaton (NFA) with active states tracked in parallel cells, a Start Pointer (SP) is captured by the cell beginning a match and passed from cell to cell until the match completes, when it is reported by the cell ending the match. For multiple overlapping matches, different cells may hold different SPs, and a cell representing multiple NFA states may hold multiple SPs. Methods are given to select one SP when multiple SPs collide in the same state.
Claims15
A method of tracking a start pointer in active parallel cells in an NFA scanning system, said NFA scanning system comprising a plurality of start point references to a table containing representations of positions in the input stream, a Free Queue containing unallocated start point references, a Used Queue containing allocated start point references, a start point table, and a cell array, said method comprising:
- establishing a start position value in an active start state cell where a match begins;
- reading a start point reference from said Free Queue;
- transmitting said read start point reference to a cell;
- writing said position where a match began into said start point bable at an address based on said start point reference;
- writing said start point reference into said Used Queue;
- upon a state transition from an active cell to a destination cell, transmitting the start position value from said active cell to the destination cell and activating the destination cell;
- and
- reporting the start position value by an active cell completing the match.
A method for allocating a start position reference for a start state in an array of cells, comprising:
- reading at least one start position reference from a Free Queue and storing the read start position references in a circulating loop to represent first symbol positions;
- presenting one of said read start position references to all cells as each symbol of an input stream is consumed;
- if any start cell begins matching, storing the presented start position reference in that cell;
- signaling an SP Manager that the cell that began matching utilized the presented start position reference;
- writing, via the SP Manager, the presented start position reference into a Used Queue;
- and
- writing a corresponding symbol position into an SP Table at the address corresponding to the presented start position reference.
A system for tracking a start pointer in active parallel cells in an NFA scanning system, said system comprising:
- an SP manager, a loader, a harvester and a reaper;
- a Free Queue;
- a Used Queue;
- and
- a plurality of NFA cells;
- wherein start point references (SPRs) are allocated by the loader communicating with the SP manager and the SP manager records a start position into an SP table;
- SPRs are freed by the SP manager circulating start pointer references from the Used Queue through the plurality of NFA cells, the reaper and the harvester and transferring any SPR that is reported unused by the plurality of NFA cells, reaper and harvester to the Free Queue;
- and the SPRs are used within the NFA cells and transferred from one cell to another along with NFA state transitions.
Dependencies are inferred from the claim text.