NFA byte detector

1. A circuit comprising:

a hardware byte characterizer that receives an m-bit incoming byte value and uses combinatorial logic and no sequential logic to generate a plurality of single bit characterizations signals, wherein the single bit characterization signals together form a 2m-bit hardware byte characterizer output value;

a first matching circuit that performs a (Ternary Content-Addressable Memory) TCAM match function, wherein the first matching circuit receives the m-bit incoming byte value, an n-bit mask value, and an o-bit match value;

a second matching circuit that performs a wide match function, wherein the second matching circuit receives the 2m-bit hardware byte characterizer output value and an n+o-bit mask value;

a multiplexer having a first data input coupled to a data output of the first matching circuit, a second data input coupled to a data output of the second matching circuit, and a plurality of multiplexer select inputs; and

a storage device that has a first plurality of storage locations, a second plurality of storage locations, and a third plurality of storage locations, wherein n data values stored in the first plurality of storage locations are supplied to the first matching circuit as the n-bit mask value and are simultaneously supplied to the second matching circuit as n bits of the n+o-bit mask value, and wherein o data values stored in the second plurality of storage locations are supplied to the first matching circuit as the o-bit match value and are simultaneously supplied to the second matching circuit as o bits of the n+o-bit mask value, and wherein p data values stored in the third plurality of storage locations are supplied onto the select inputs of the multiplexer.

2. The circuit of claim 1 , wherein each bit of the 2m-bit hardware byte characterizer output value coming into the second matching circuit has an associated corresponding mask bit in the n+o-bit mask value, and wherein the second matching circuit asserts an output signal on its data output if any unmasked bit of the 2m-bit hardware byte characterizer output value is asserted.

3. The circuit of claim 1 , wherein each bit of the 2m-bit hardware byte characterizer output value coming into the second matching circuit has an associated corresponding mask bit in the n+o-bit mask value, and wherein the second matching circuit asserts an output signal on its data output if none of the unmasked bits of the 2m-bit hardware byte characterizer output value is asserted.

4. The circuit of claim 1 , wherein each bit of the m-bit incoming byte value coming into the first matching circuit has an associated corresponding mask bit and an associated corresponding match bit, wherein if the mask bit has a first digital logic value and the match bit has the first digital logic value then a first masking function is applied whereas if the mask bit has the first digital logic value and the match bit has a second digital logic value then a second masking function is applied whereas if the mask bit has the second digital logic value then no masking function is applied regardless of the digital logic value of the match bit.

5. The circuit of claim 4 , wherein the first matching circuit asserts an output signal onto its data output only if at least one of any bits of the m-bit incoming byte value for which the second masking function is applied is asserted.

6. The circuit of claim 1 , wherein the first matching circuit comprises combinatorial logic gates but comprises no sequential logic elements and no memory cells.

7. The circuit of claim 1 , further comprising:

a third matching circuit that performs an equal either match function, wherein the third matching circuit receives the m-bit incoming byte value, the n data values from the first plurality of storage locations of the storage device, and the o data values from the second plurality of storage locations of the storage device, and wherein a data output of the third matching circuit is coupled to a third data input of the multiplexer.

8. The circuit of claim 7 , wherein the third matching circuit asserts an output signal onto its data output if either of the n-bit value or the o-bit value matches the m-bit incoming byte value.

9. The circuit of claim 1 , further comprising:

a combiner circuit that has a data input and a control input, wherein the combiner circuit performs a selectable one of a plurality of logical operations on successive data output values output from the multiplexer, wherein the data input of the combiner circuit is coupled to a data output of the multiplexer, wherein the storage device also stores a combiner control bit, and wherein the control input of the combiner circuit is coupled to receive the combiner control bit from the storage device.

10. A method comprising:

receiving an m-bit incoming byte value onto a stage of a pipeline and using combinatorial logic and no sequential logic of the pipeline to generate a plurality of single bit characterizations signals, wherein the single bit characterization signals together form a 2m-bit hardware byte characterizer output value;

storing n data values in a first plurality of storage locations of a storage device, o data values in a second plurality of storage locations, and p data values in a third plurality of storage locations, wherein the storage device is a part of the stage of the pipeline;

performing a (Ternary Content-Addressable Memory) TCAM match function using the m-bit incoming byte value as an incoming data value, using n data values as an n-bit mask value, and using the o data values as an o-bit match value, thereby generating a TCAM output value;

performing a wide match function using the 2m-bit hardware byte characterizer output value as an incoming data value, and using the n data values and the o data values as an n+o-bit mask value, thereby generating a wide match output value; and

a multiplexer that receives the TCAM output value onto a first data input, that receives the wide match output value onto a second data input, and that receives the p data values onto a plurality of select inputs of the multiplexer, wherein the multiplexer is a part of the stage of the pipeline.