Data scan mechanism
View Patent ↗Methods and devices for scanning an incoming datastream for a plurality of target patterns. The scanning system receives an incoming data stream and stores the stream as sequential symbols in a register array. Previously received symbols are shifted in the array as incoming symbols are shifted in. A trigger stage computes a hash value based on the k most recently received symbols. The trigger stage then uses the hash value to determine whether a more detailed symbol by symbol comparison is required between a group of sequential symbols stored in the array and a target pattern stored in external storage. This is done by comparing the hash value with the indices of the target patterns in the external storage. If the more detailed comparison is indicated, a full comparison stage retrieves the relevant target pattern and compares the target pattern with the sequentially stored symbols in the array. To improve the determination of whether the detailed comparison is required, a confidence stage may be placed between the trigger stage and the full comparison stage. The confidence stage computes a hashing function value based on c sequential symbols in the array with c≧k. The hashing function value is then used to determine whether the more time consuming symbol by symbol comparison is needed.
1. A system for scanning an incoming data stream for a plurality of symbol patterns, the system comprising:
a microprocessor;
a symbol register array for receiving said data stream and sequentially storing symbols comprising said data stream, said symbol register array shifting previously received symbols in said symbol register array as new data is received;
a trigger stage for determining, using the microprocessor, a possible match between consecutive symbols in said symbol register array and a pattern stored in a storage device, the pattern containing x symbols, said trigger stage providing data regarding said possible match to a subsequent stage, wherein said trigger stage comprises at least one trigger group, each trigger group comprising:
a hash module for calculating a hash value based on k consecutive symbols stored in said symbol register array, wherein k<x, and wherein k is less than the number of symbols in the smallest one of the symbol patterns, said hash module reading said k consecutive symbols from said symbol register array;
a trigger table; and
a trigger comparison module for comparing results from said hash module with indices of entries in said trigger table, said trigger table having entries indicative of whether a specific entry in said storage module is a valid entry, said results from said hash module being compared with indices of said entries in said trigger table; and
a full comparison stage for retrieving and comparing one of said plurality of symbol patterns with a symbol sequence stored in and retrieved from said symbol register array, said consecutive symbols being part of said symbol sequence, said one of said plurality of symbol patterns being retrieved from said storage device when data regarding said possible match is received from a preceding stage.
2. A system according to claim 1 wherein said system further comprises a confidence stage for determining if a possible match determined by said trigger stage should be passed to said full comparison stage, the confidence stage receiving an output of said trigger stage and providing an output to said full comparison stage.
3. A system according to claim 2 wherein said confidence stage retrieves c symbols from predetermined addresses in said symbol register array based on said output of said trigger stage, wherein k<c<x, and applies a hash function to said c symbols to result in a hashing function value, said hashing function value being compared to an entry in said confidence stage, said possible match being passed to said full comparison stage if said hashing function value matches said entry.
4. A system according to claim 2 wherein said confidence stage comprises :
a hashing function module for calculating an extra hash value based on consecutive symbols stored in said symbol register array, said consecutive symbols being received from said symbol register array by said hashing function module;
a confidence table module for storing values to be compared with results from said hashing function module, each entry in said table module having a larger corresponding entry in said storage device
an extra comparison block for comparing results from said hashing function module and an entry stored in said confidence table module, results from a comparison of said hashing function value and said entry stored in said confidence table module being indicative of a possible match or non-match between said larger corresponding entry in said storage device and said consecutive symbols in said symbol register array.
5. A system according to claim 4 wherein each entry in said confidence table module includes a scope value for use by said hashing function module in calculating said extra hash value.
6. A system according to claim 5 wherein said scope value is a mask for masking out at least a predetermined one of said consecutive symbols prior to applying said hashing function to said consecutive symbols.
7. A system according to claim 1 wherein said trigger stage comprises a plurality of the trigger groups, each trigger group reading a group of consecutive symbols different from consecutive symbols read by other trigger groups.
8. A system according to claim 7 wherein at least one of said plurality of trigger groups reads a number of consecutive symbols different from a number of consecutive symbols read by other trigger groups.
9. A system according to claim 7 wherein said confidence stage further comprises a plurality of buffers, each one of said plurality of buffers corresponding to and receiving an output of a specific one of said plurality of trigger groups.
10. A system according to claim 1 wherein said full comparison stage compares said symbol sequence with said one of said symbol patterns in a symbol by symbol manner.
11. A system according to claim 10 wherein said full comparison stage comprises:
a full comparison module for comparing said symbol sequence with said one of said plurality of symbol patterns in a symbol by symbol manner, said full comparison module receiving said one of said plurality of symbol patterns from said storage device;
a retrieval module for retrieving said symbol sequence from said symbol register array and for sending said symbol sequence to said full comparison module.
12. A method for scanning an incoming data stream of symbols for a plurality of symbol patterns, the method comprising:
a) receiving said incoming data stream of symbols;
b) storing received symbols in an array and shifting said received symbols in said array as further incoming symbols are received;
c) determining, using a microprocessor, a possible match between consecutive symbols in said array and a pattern stored in a storage device, the pattern containing x symbols, said pattern being one of said plurality of symbol patterns, by calculating a hash value based on k consecutive symbols in said array, wherein k<x, and wherein k is less than the number of symbols in the smallest one of the symbol patterns, and comparing said hash value with entries indicative of whether a specific entry in said storage device is a valid entry; and
d) in the event a possible match is indicated, performing a symbol by symbol comparison between said consecutive symbols in said array and said pattern retrieved from said storage device.
13. A method according to claim 12 further comprising a determining step of determining if a possible match determined in step c) necessitates a symbol by symbol comparison between said consecutive symbols in said array and said pattern in said storage device.
14. A method according to claim 13 wherein said determining step comprises calculating a hash value based on said symbols in said array and comparing said hash value with a stored value.
15. A system for finding matches between a plurality of symbol patterns and an incoming data stream of symbols, the system comprising:
a microprocessor;
a symbol register array for receiving said incoming data stream, said symbol register array storing received symbols and shifting received symbols as said data stream is received;
at least one trigger group for providing, using the microprocessor, an initial indication of a possible match between the received symbols stored in the symbol register array and a particular one of the symbols patterns containing x symbols, said initial indication based on a sequence of k consecutive symbols stored in said symbol register array, wherein k<x, and wherein k is less than the number of symbols in the smallest one of the symbol patterns, using a hash function applied to said sequence of k consecutive symbols;
a retrieval module for retrieving c symbols from said symbol register array, wherein k<c<x, and for applying a second hashing function to selected ones of said c symbols retrieved from said symbol register array when said at least one trigger group provides the initial indication of the possible match;
a confidence table module for storing entries containing values which select said c symbols based on an output from said at least one trigger group and, which select a value to be compared with results from said retrieval module;
a comparison block for comparing a result from said retrieval module with an entry from said confidence table module and for receiving said output from said at least one trigger group; and
a full comparison module for comparing x symbols retrieved from the symbol register array with an entry from a storage device corresponding to the particular symbol pattern, said entry being the particular symbol pattern, said full comparison module comparing said x symbols with said entry from said storage device in a symbol by symbol manner.
16. A system according to claim 15 wherein said system comprises a plurality of trigger groups, each trigger group reading a group of consecutive symbols different from consecutive symbols read by other trigger groups.
17. A system according to claim 15 wherein said storage device is an external storage device.