# US 2008/0270342 A1 · Hardware processing of regular expressions

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2008/0270342 A1
- Document ID: US20080270342A1
- Status: Published application
- Kind: A1
- Application number: 12/112,988
- Filed: 2008-04-30
- Published: 2008-10-30
- Earliest claimed: 2007-04-30
- Assignees: Tarari, Inc.
- Inventors: Michael D. Ruehle
- Web page: https://patentgrep.com/patent/US20080270342A1

## CPC

- G06F 16/90344: {by using string matching techniques}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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.

## Claims

### Claim 1

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.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
initiating an action included in the state information associated with the one or more next states associated with the satisfied transition conditions.

### Claim 3 (depends on 1)

The method of claim 1, further comprising:
storing in the register bank respective spin counters for any states associated with transition conditions wherein one or more characters result in a transition to the same state, wherein each respective spin counter is incremented when the one or more characters is determined as the next character.

### Claim 4 (depends on 3)

The method of claim 3, wherein the one or more next states associated with respective spin states are not marked as active until an associated spin counter reaches a spin quantity indicated in the transition condition.

### Claim 5 (depends on 3)

The method of claim 3, further comprising:
resetting the respective spin counter when the associated state is marked inactive.

### Claim 6 (depends on 2)

The method of claim 2 wherein the action comprises outputting a token.

### Claim 7 (depends on 1)

The method of claim 1, further comprising:
loading new state information into the register bank, wherein the new state information is based at least in part on the transition conditions associated with active states that are satisfied by the next character.

### Claim 8 (depends on 7)

The method of claim 7, further comprising:
initiating an action indicated in the state information associated with the one or more next states associated with the satisfied transition conditions.

### Claim 9 (depends on 7)

The method of claim 7, further comprising:
storing in the register bank respective spin counters for any states associated with transition conditions wherein one or more characters result in a transition to the same state, wherein each respective spin counter is incremented when the one or more characters is determined as the next character.

### Claim 10 (depends on 9)

The method of claim 9, wherein the one or more next states associated with respective spin states are not marked as active until an associated spin counter reaches a spin quantity indicated in the transition condition.

### Claim 11 (depends on 9)

The method of claim 9, further comprising:
resetting the respective spin counter when the associated state is marked inactive.

### Claim 12 (depends on 8)

The method of claim 8, wherein the action comprises outputting a token.

### Claim 13

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.

### Claim 14 (depends on 13)

The method of claim 13, further comprising resetting the values of each of the N bits to the first value when the spin state is marked inactive.

### Claim 15

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.

### Claim 16 (depends on 15)

The apparatus of claim 15,
wherein the reconfiguration connection matrix comprises an FPGA that is reconfigured to create the signal paths when a state of the state machine becomes active.

### Claim 17 (depends on 15)

The apparatus of claim 15, wherein the reconfigurable connection matrix comprises at least one of an integrated circuit (IC), and application-specific integrated circuit (ASIC), a field-programmable gate array (FPGA), a discrete logic component and logic gates.

### Claim 18 (depends on 15)

The apparatus of claim 15, wherein the reconfigurable connection matrix is implemented in a network interface card that is configured for interfacing with a network server.

### Claim 19 (depends on 15)

The apparatus of claim 15, wherein at least some signal paths comprise one or more transistors, logic gates, and resistors.

### Claim 20

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.

### Claim 21 (depends on 20)

The apparatus of claim 20, wherein the apparatus further comprises:
a reconfigurable connection matrix configured to dynamically create electrical connections between state slots so that electrical connections are created between state slots associated with each of the currently active states and respective next states of the currently active states.

### Claim 22 (depends on 20)

The apparatus of claim 20, wherein one or more of the register bank, the loader and the transition logic are implemented in an integrated circuit (IC), and application-specific integrated circuit (ASIC), a field-programmable gate array (FPGA), a discrete logic component, or a plurality of logic gates.
