Apparatus and method for parallel regular expression matching
US8990232B2 · kind B2 · utility
Assignee
Inventor
Key dates
| Filing date | May 15, 2012 |
| Grant date | Mar 24, 2015 |
| Priority date | — |
| Expiry date | May 15, 2032 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L69/22
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A regular expression matching hardware implementation comprises two tightly coupled hardware engines. A regex engine performs state transitions and accepts (as matching) or rejects (as not matching) an input string. The regex engine takes also care of the logic of the operators and deals with the complexity of the state machine. A lookup engine reads characters from an input (e.g., tape, memory, network packets, or the like), and provides them to the regex engine. A preprocessing procedure transforms a regular expression into a regex state transition table and a lookup table, for use by the regex engine and lookup engine, respectively. The two hardware engines are synchronized by a global state machine. The regex engine advances the state machine, and the lookup engine reads it.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.