Patent ID: 7783688

Claim:
A method of performing an incremental hash function on a data string, the method comprising: using a processor to perform at least a portion of one or more of the following acts: receiving the data string over a network at a network interface device, the data string including a plurality of data samples B 0 to B I , wherein represents a number of data samples that are received in parallel; defining a moving window of length wl within the data string; as the plurality of data samples are received, calculating and maintaining a corresponding plurality of hash values H 0 to H I , one hash value for each data sample that can be received in parallel; wherein calculating the plurality of hash values includes: defining a hash multiplier constant to be k; calculating a first hash value H 0 by adding a first data sample B 0 to a last hash value H I , and by subtracting a data sample that was received wl bytes previously multiplied by k wl ; calculating a second hash value H 1 by adding the first data sample B 0 multiplied by k and a second data sample B 1 to the last hash value H I , by subtracting the data sample that was received wl bytes previously multiplied by k wl+1 , and by subtracting a data sample received wl+1 bytes previously multiplied by k wl ; calculating the last hash value H I by adding the correspondingly multiplied values of the first data samples to the last hash value H I , and by subtracting the correspondingly multiplied values of bytes received from wl to wl+previously; combining the calculated first hash value through last hash value into a result; using the result to identify content in the form of a particular reference string; and performing a particular action based upon the particular reference string.