US 6,223,320 B1 · Efficient CRC generation utilizing parallel table lookup operations

Abstract

An improved CRC generation mechanism for generating a CRC value of relevant data in a digital data stream is disclosed wherein relevant data in the data stream is identified and partitioned into a plurality of intervals. A CRC value is determined for each interval by partitioning the interval into a plurality of chunks, loading from persistent storage a table of CRC values for a range of chunks, determining a CRC value for each of the chunks with parallel table lookup operations on the table, and combining the CRC values for the chunks. The CRC values for each of the intervals is combined to generate the CRC for the relevant data. The parallel table look operation is preferably a vector permute instruction that is executed by a SIMD-style vector unit.

Claims34

Dependent claims

A method for generating a CRC value representing data in a digital data stream, the method comprising the steps of:

identifying relevant data in said digital data stream;
identifying a plurality of successive intervals in the relevant data, wherein said plurality of successive intervals comprise a set of intervals followed by a final interval;
determining a partial CRC value representing said set of intervals, wherein the following substeps are performed for each given interval in said set of intervals:
partitioning said given interval into a plurality of chunks;
determining a CRC value for each of said chunks;
and
combining said CRC values for said chunks;
combining portions of said final interval with said partial CRC value to thereby generate an augmented final interval;
and
generating a CRC value for said augmented final interval that represents a CRC value for the relevant data of said digital data stream.

7 more elements

A program storage device readable by a machine, tangibly embodying a sequence of instructions executable by the machine to perform method steps for generating a CRC value representing data in a digital data stream, the method steps comprising:

identifying relevant data in said digital data stream;
identifying a plurality of successive intervals in the relevant data, wherein said plurality of successive intervals comprise a set of intervals followed by a final interval;
determining a partial CRC value representing said set of intervals, wherein the following substeps are performed for each given interval in said set of intervals:
partitioning said given interval into a plurality of chunks;
determining a CRC value for each of said chunks;
and
combining said CRC values for said chunks;
combining portions of said final interval with said partial CRC value to thereby generate an augmented final interval;
and
generating a CRC value for said augmented final interval that represents a CRC value for the relevant data of said digital data stream.

7 more elements

Dependencies are inferred from the claim text.

Efficient CRC generation utilizing parallel table lookup operations

Life of this patent

Efficient CRC generation utilizing parallel table lookup operations

Life of this patent

Abstract

Claims34