Hardware processing of regular expressions
AssigneeTarari, Inc.
InventorMichael D. Ruehle
Life of this patent
Estimating the term…
Abstract
A system and method for hardware processing of regular expressions is disclosed. A register bank is loaded with state information associated with one or more states of a state machine. State information such as transitions and spin counts are updated as characters of an input data stream are processed. A crossbar is used to interconnect the states stored in the register bank.
Claims22
A method of tracking active states of a nondeterministic state machine during a process of traversing states of the state machine in response to characters of an input data stream, the method comprising:
- (a) loading state information associated with one or more states of the state machine into a register bank and marking as active the state information of at least one state, the state information for each state comprising one or more transition conditions associated with the state and one or more next states associated with respective transition conditions;
- (b) determining a next character of the input stream;
- (c) accessing the transition conditions of only the currently active states in order to determine one or more transition conditions that are satisfied by the next character;
- (d) marking as active in the register bank state information associated with one or more next states associated with the satisfied transition conditions;
- (e) marking as inactive in the register bank state information associated with any next states that are not associated with one or more satisfied transition conditions;
- (f) repeating steps (b)-(e) for each character of the input stream.
A method of tracking a number of times a spin states of a nondeterministic state machine is sequentially accessed in response to respective transition conditions of the spin state matching sequential input characters of an input data stream, the method comprising:
- determining N bits of memory for tracking a spin count associated with the spin state, wherein N is greater than or equal to a predetermined quantity of accesses to the spin state that must occur in response to sequentially received input characters before a transition condition of the spin states is satisfied;
- setting a value of each of the N bits to a first value;
- receiving an input character matching a transition character indicating transition from the spin state to the spin state and, in response thereto, setting a first bit of the N bits to a second value;
- in response to each sequentially received input character matching a transition character indicating a transition from the spin state to the spin state, setting a different bit of the N bits to a second value, wherein the bits set to the second value are indicative of one or more current spin counts associated with the spin state.
An apparatus for detecting patterns in a data stream comprising:
- a memory storing state information associated with one or more states of a state machine in respective memory locations of the memory, the state machine being configured to detect patterns in an input data stream, wherein the state information stored in the memory is updated as the state machine is traversed in response to characters of the input data stream, the state information for each state comprising one or more transition conditions associated with respective states and one or more next states associated with respective transition conditions, the memory further storing an activity indicator for the one or more states indicative of which of the one or more states is currently active in evaluation of the input data stream;
- and
- a reconfigurable connection matrix configured to dynamically create signal paths between memory locations so that signal paths are created between memory locations associated with each of the currently active states and respective memory locations associated with the next states associated with the respective currently active states.
An apparatus for evaluating a state machine in response to a data string, the apparatus comprising:
- a register bank comprising a plurality of state slots configured to selectively store information associated with states of the state machine;
- a loader configured to selectively load state information associated with one or more states of the state machine into state slots of the register bank and to initiate marking of certain states as active;
- and
- transition logic configured to access transition conditions associated with each of the states in the register bank that are marked as active, to determine one or more of the transition conditions that are satisfied by a next character of the data string, and to provide an indication of one or more next states indicate in the determined transition conditions to the loader, wherein the loader is configured to update the state information loaded in the register bank and the states that are marked as active based on the indication received from the transition logic.
Dependencies are inferred from the claim text.