Granted Patent B1

US 8,631,195 · App. 12/132,053 · Granted Jan 14, 2014

Abstract

Claims (39)

1. A search system including a shift register circuit for detecting whether one or more overlapping sequences of input characters match a regular expression including a prefix string preceding an intermediate expression having a quantified number m of characters belonging to a specified character class, the shift register circuit comprising:

a control circuit having an input responsive to a prefix match signal indicative of whether an input character sequence matches the prefix string, and having an output, wherein the control circuit is configured to produce an output signal that varies based on whether the input character sequence matches the prefix string;

a shift register having an input connected to the output of the control circuit and including a number of registers connected in a chain, each register having a data output connected to a data input of the next register in the chain and each having a clock input to receive a clocked match signal that represents a logic combination of a clock signal and a character class match signal, the clocked match signal indicating whether a current input character matches the character class;

a compare circuit having a first input to receive a bitwise decoded version of the quantified number, having second inputs coupled to the shift register, and having an output for generating a trigger signal indicating that a sequence of m input characters matches the character class; and

a programmable quantifier memory configured to be programmed with the bitwise decoded version of the quantified number and to output the bitwise decoded version of the quantified number to the first input of the compare circuit.

2. The search system of claim 1 , wherein each assertion of the prefix match signal causes the control circuit to provide an asserted character match bit to the shift register input, and each assertion of the character class match signal shifts the character match bits by one position in the shift register.

3. The search system of claim 2 , wherein de-assertion of the prefix match signal causes the control circuit to provide a de-asserted character match bit to the shift register input.

4. The search system of claim 3 , wherein the control circuit includes a reset terminal to receive a logical complement of the prefix match signal.

5. The search system of claim 2 , wherein each overlapping sequence of input characters that matches the character class is represented by a corresponding asserted character match bit stored in the shift register.

6. The search system of claim 1 , wherein the compare circuit asserts the trigger signal if the asserted character match bit is shifted into the m th register of the shift register.

7. The search system of claim 1 , wherein each of the registers includes a reset terminal to receive a logical complement of the character class match signal.

8. The search system of claim 7 , wherein de-assertion of the character class match signal resets the shift register to an initial state and forces de-assertion of the trigger signal.

9. The search system of claim 1 , wherein the programmable quantifier memory comprises an array of storage elements, and wherein the bitwise decoded version of the quantified number is programmed into the array of storage elements.

10. The search system of claim 9 , wherein the compare circuit comprises:

a number of comparators, each comparator having a first input to receive a corresponding one of the state bits, a second input coupled to the output of a corresponding register, and an output coupled to a character class match line that generates the trigger signal.

11. The search system of claim 10 , wherein each comparator discharges the character class match line to logic low to assert the trigger signal only if the corresponding character match bit and the corresponding state bit are both asserted.

12. The search system of claim 10 , wherein each comparator comprises:

first and second pull-down transistors connected in series between the character class match line and ground potential, wherein the first transistor has a gate coupled to the output of the corresponding register, and the second transistor has a gate to receive the corresponding state bit.

13. The search system of claim 10 , wherein the shift register circuit further comprises:

a pre-charge transistor connected between a voltage supply and the character class match line and having a gate to receive a shift register pre-charge signal.

14. The search system of claim 1 , further including a content addressable memory (CAM) device comprising:

a first row of CAM cells configured to store the prefix string and to generate the prefix match signal; and

a second row of CAM cells configured to store the character class and to generate the character class match signal.

15. The search system of claim 14 , wherein assertion of the character class match signal enables the second row of CAM cells in a next compare operation to detect a subsequent character class match.

16. The search system of claim 14 , wherein the regular expression further includes a suffix string following the intermediate expression, and the CAM device further comprises:

a third row of CAM cells configured to store the suffix string.

17. The search system of claim 16 , wherein the third row of CAM cells is enabled for a next compare operation to detect a suffix string match in response to assertion of the trigger signal.

18. The search system of claim 10 , wherein the trigger signal represents a logic compliment of the character class match line.

19. A method for detecting whether one or more overlapping sequences of input characters match a regular expression including a prefix string preceding an intermediate expression having a quantified number m of characters belonging to a specified character class, comprising:

receiving, at a control circuit, a prefix match signal indicative of whether an input character sequence matches the prefix string;

generating an output signal based on the prefix match signal;

receiving the output signal at a shift register having a plurality of registers connected in a chain;

receiving, at each of the plurality of registers, a clocked match signal that represents a logic combination of a clock signal and a character class match signal, the clocked match signal indicating whether a current input character matches the character class;

programming a quantifier memory with a bitwise decoded version of the quantified number;

receiving, at a compare circuit, the bitwise decoded version of the quantified number and an output signal from the shift register; and

generating, at the compare circuit, a trigger signal indicating that a sequence of m input characters matches the character class.

20. The method of claim 19 , further comprising:

providing, by the control circuit, an asserted character match bit to the shift register upon each assertion of the prefix match signal; and

shifting the character match bits by one position in the shift register upon each assertion of the character class match signal.

Assignments (8)