Patent ID: 8631195

Claim:
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.