Search engine having multiple co-processors for performing inexact pattern search operations
View Patent ↗A search engine configured to determine whether an input string including a plurality of input characters matches a regular expression including an inexact pattern including a specified range of instances of pattern characters each belonging to a specified set of characters, the search engine including a microcontroller having an input to receive a microprogram embodying the inexact pattern, a first co-processor coupled to the microcontroller and dedicated to determine whether each input character in a first portion of the input string is a member of the specified set of characters, and a second co-processor coupled to the microcontroller and dedicated to determine whether the number of input characters in the first portion of the input string falls within the specified range.
1. A search engine configured to determine whether an input string including a plurality of input characters matches a regular expression including an inexact patter, wherein the inexact pattern comprises a specified range of instances of selected characters each belonging to a specified set of characters, the search engine comprising:
a microcontroller having an input to receive a microprogram embodying the inexact pattern, wherein a first portion of the microprogram embodies the specified set of characters and a second portion of the microprogram embodies the specified range;
a first co-processor coupled to the microcontroller and dedicated to determine whether each input character in a first portion of the input string is a member of the specified set of characters by executing the first portion of the microprogram; and
a second co-processor coupled to the microcontroller and dedicated to determine whether the number of input characters in the first portion of the input string falls within the specified range by executing the second portion of the microprogram.
2. The search engine of claim 1 , wherein the first co-processor references each input character to a corresponding compliance bit in a bitmap embodying the specified set of characters.
3. The search engine of claim 2 , wherein for each input character, the first co-processor generates a compliance signal indicating whether the input character is a member of the specified set of characters.
4. The search engine of claim 3 , wherein the second co-processor is responsive to the compliance signal.
5. The search engine of claim 3 , wherein the second co-processor selectively increments a count value in response to a control signal and compares the count value with at least one boundary value embodying the specified range.
6. The search engine of claim 5 , wherein the control signal comprises the compliance signal.
7. The search engine of claim 6 , wherein the second co-processor generates a range signal indicating whether the number of input characters in the first portion of the input string falls within the specified range.
8. The search engine of claim 7 , wherein the microcontroller generates a match signal in response to a combination of the compliance signal and the range signal.
9. The search engine of claim 8 , wherein the microcontroller de-asserts the match signal if the compliance signal indicates that one of the input characters in the first portion of the input string is not a member of the specified set of characters.
10. The search engine of claim 1 , wherein the microprogram comprises:
a bitcheck command including a bitmap embodying the specified set of characters; and
a count command including at least one boundary value embodying the specified range.
11. The search engine of claim 10 , wherein the microcontroller delegates the bitcheck command to the first co-processor and delegates the count command to the second co-processor.
12. The search engine of claim 10 , wherein the first co-processor comprises:
a buffer having an input to receive the input string and configured to output a selected input character in response to a cursor value; and
a bitmap memory for storing the bitmap, the bitmap memory having an address port to receive the selected input character.
13. The search engine of claim 10 , wherein the second co-processor comprises:
a counter for selectively incrementing a count value in response to a control signal; and
compare logic for comparing the count value to the at least one boundary value.
14. The search engine of claim 1 , wherein the regular expression further includes an exact pattern, and the search engine further comprises:
a third co-processor coupled to the microcontroller and dedicated to determine whether the input string contains a second portion that matches the exact pattern.
15. The search engine of claim 14 , wherein the microprogram includes a reference match identification (MID) value corresponding to the exact pattern, and the third co-processor comprises:
a jump FIFO memory having a plurality of storage locations for storing a plurality of result MID values provided by an external search circuit in response to a comparison between the input string and a plurality of exact patterns; and
compare logic having a first input to receive the reference MID value, a second input to receive one or more result MID values from a selected storage location of the jump FIFO memory, and an output to generate an exact match flag.
16. A search engine configured to determine whether a selected portion of an input string including a plurality of input characters matches a regular expression including an inexact pattern, the search engine comprising:
a microcontroller having an input to receive a microprogram embodying the inexact pattern and comprising a plurality of commands, wherein each command embodies a different portion of the inexact pattern; and
a plurality of co-processors coupled to the microcontroller, wherein each co-processor is dedicated to execute a corresponding one of the commands to implement its associated portion of an inexact pattern match operation between the input string and the inexact pattern, wherein the inexact pattern comprises a specified range of instances of selected characters each belonging to a specified set of characters.
17. The search engine of claim 16 , wherein the microcontroller delegates each of the commands to a designated one of the plurality of co-processors.
18. The search engine of claim 16 , wherein:
a first of the commands comprises a bitcheck command embodying the specified set of characters; and
a first of the co-processors is dedicated to execute the bitcheck command to generate a compliance signal indicating whether a selected input character is a member of the specified set of characters.
19. The search engine of claim 18 , wherein:
the bitcheck command contains a bitmap including a plurality of compliance bits, each indicating whether a corresponding reference character of a general set of characters is a member of the specified set of characters; and
the first co-processor references each of the input characters to a corresponding compliance bit in the bitmap to generate the compliance signal.
20. The search engine of claim 19 , wherein:
the bitmap is stored in a compressed format.
21. The search engine of claim 18 , wherein:
a second of the commands comprises a count command embodying the specified range of instances; and
a second of the co-processors is dedicated to execute the count command to generate a range signal indicating whether the number of input characters in the selected portion falls within the specified range of instances.
22. The search engine of claim 21 , wherein:
the count command includes one or more boundary values that define the specified range of instances; and
the second co-processor compares the number of input characters determined to be members of the specified set of characters to the one or more boundary values to generate the range signal.
23. The search engine of claim 21 , wherein the microcontroller combines the compliance signal and the range signal to generate a match flag indicating a match condition between the input string and the inexact pattern.
24. The search engine of claim 21 , wherein the second co-processor is selectively disabled in response to the compliance signal.
25. The search engine of claim 21 , wherein the first co-processor is selectively disabled in response to the range signal.
26. The search engine of claim 21 , wherein:
the regular expression further includes an exact pattern;
a third of the commands comprises a check string command embodying the exact pattern; and
a third of the co-processors is dedicated to execute the check string command to determine whether the input string matches the exact pattern.
27. The search engine of claim 26 , wherein:
the check string command includes a reference match identification (MID) value identifying the exact pattern; and
the third co-processor compares the reference MID value to a plurality of result MID values provided by an external searchable database in response to an exact pattern match operation between the input string and a plurality of exact patterns stored in the searchable database.
28. A method performed by a content search system for determining whether a selected portion of an input string including a plurality of input characters matches a regular expression including an inexact pattern, comprising:
receiving a microprogram embodying the inexact pattern and comprising a plurality of commands, wherein each command embodies a different portion of the inexact pattern;
for each command, delegating the command to a corresponding co-processor that is dedicated to execute the command; and
processing the commands in the corresponding co-processors, wherein each co-processor implements an associated portion of an inexact pattern match operation between the input string and the inexact pattern, wherein the inexact pattern comprises a specified range of instances of selected characters each belonging to a specified set of characters.
29. The method of claim 28 , further comprising:
selectively disabling each of the co-processors in response to results from one or more other co-processors.
30. The method of claim 28 , further comprising:
combining results from at least two of the co-processors to generate a match signal indicating whether the input string matches the regular expression.
31. The method of claim 28 , wherein the inexact pattern is specified to include one or more pattern characters that are members of a specified set of characters, a first of the commands comprises a bitcheck command embodying the specified set of characters, and the processing comprises:
executing the bitcheck command in a first of the co-processors to generate a compliance signal indicating whether a selected input character is a member of the specified set of characters.
32. The method of claim 31 , wherein the first co-processor is optimized to execute the bitcheck command.
33. The method of claim 31 , wherein the bitcheck command contains a bitmap including a plurality of compliance bits, each indicating whether a corresponding reference character of a general set of characters is a member of the specified set of characters.
34. The method of claim 33 , wherein the bitmap is stored in a compressed format.
35. The method of claim 31 , wherein the inexact pattern is further specified to include a range of instances of the pattern characters, a second of the commands comprises a count command embodying the specified range of instances, and the processing further comprises:
executing the count command in a second of the co-processors to generate a range signal indicating whether the number of input characters in the selected portion falls within the specified range of instances.
36. The method of claim 35 , wherein the second co-processor is optimized to execute the count command.
37. The method of claim 35 , further comprising:
reporting the compliance signal and the range signal to a microcontroller; and
combining the compliance signal and the range signal in the microcontroller to generate a match signal.
38. The method of claim 33 , wherein the regular expression further includes an exact pattern, a third of the commands comprises a check string command embodying the exact pattern, and the processing further comprises:
executing the check string command in a third of the processors to determine whether the input string matches the exact pattern.
39. The method of claim 38 , wherein the third co-processor is optimized to execute the check string command.
40. The method of claim 38 , wherein the check string command includes a reference match identification (MID) value identifying the exact pattern, and executing the check string command comprises:
receiving a plurality of result MID values from an external searchable database in response to an exact pattern match operation between the input string and a plurality of exact patterns stored in the searchable database; and
comparing the reference MID value to the result MID values.
41. A search engine for determining whether a selected portion of an input string including a plurality of input characters matches a regular expression including an inexact pattern, comprising:
means for receiving a microprogram embodying the inexact pattern and comprising a plurality of commands, wherein each command embodies a different portion of the inexact pattern;
means for delegating each command to a corresponding co-processor that is dedicated to execute the command; and
means for processing the commands in the corresponding co-processors, wherein each co-processor implements an associated portion of an inexact pattern match operation between the input string and the inexact pattern, wherein the inexact pattern comprises a specified range of instances of selected characters each belonging to a specified set of characters.
42. The search engine of claim 41 , further comprising:
means for selectively disabling each of the co-processors in response to results from one or more other co-processors.
43. The search engine of claim 41 , further comprising:
means for combining results from at least two of the co-processors to generate a match signal indicating whether the input string matches the regular expression.
44. The search engine of claim 41 , wherein a first of the commands comprises a bitcheck command embodying the specified set of characters, and the means for processing comprises:
means for executing the bitcheck command in a first of the co-processors to generate a compliance signal indicating whether a selected input character is a member of the specified set of characters.
45. The search engine of claim 44 , wherein the first co-processor is optimized to execute the bitcheck command.
46. The search engine of claim 44 , wherein the bitcheck command contains a bitmap including a plurality of compliance bits, each indicating whether a corresponding reference character of a general set of characters is a member of the specified set of characters.
47. The search engine of claim 46 , wherein the bitmap is stored in a compressed format.
48. The search engine of claim 44 , wherein a second of the commands comprises a count command embodying the specified range of instances, and the means for processing further comprises:
means for executing the count command in a second of the co-processors to generate a range signal indicating whether the number of input characters in the selected portion falls within the specified range of instances.
49. The search engine of claim 48 , wherein the second co-processor is optimized to execute the count command.
50. The search engine of claim 46 , wherein the regular expression further includes an exact pattern, a third of the commands comprises a check string command embodying the exact pattern, and the means for processing further comprises:
means for executing the check string command in a third of the processors to determine whether the input string matches the exact pattern.
51. The search engine of claim 50 , wherein the third co-processor is optimized to execute the check string command.
52. The search engine of claim 50 , wherein the check string command includes a reference match identification (MID) value identifying the exact pattern, and the means for executing the check string command comprises:
means for receiving a plurality of result MID values from an external searchable database in response to an exact pattern match operation between the input string and a plurality of exact patterns stored in the searchable database; and
means for comparing the reference MID value to the result MID values.