Efficient CRC generation utilizing parallel table lookup operations

• US 6,223,320 B1
• Filed: 02/10/1998
• Issued: 04/24/2001
• Est. Priority Date: 02/10/1998
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kaplan, Marc Adam, Dubey, Pradeep Kumar, Joshi, Sanjay Mukund
• Primary Examiner(s): DeCady, Albert
• Assistant Examiner(s): Chase, Shelly A
• Application Number:
  US09/021,516
• Time in Patent Office: 1,169 Days
• Field of Search: 714/781, 714/758, 714/759, 714/807, 714/782, 714/800, 714/801, 714/808, 714/757
• US Class Current: 714/757
• CPC Class Codes: G06F 9/30018 Bit or string instructions
• CPC Class Codes: G06F 9/30032 Movement instructions, e.g. MOVE, SHIFT, ROTATE, SHUFFLE
• CPC Class Codes: G06F 9/30036 Instructions to perform operations on packed data, e.g. vector, tile or matrix operations
• CPC Class Codes: G06F 9/3004 to perform operations on memory
• CPC Class Codes: G06F 9/345 of multiple operands or results addressing multiple banks G06F12/06
• CPC Class Codes: H03M 13/091 Parallel or block-wise CRC computation

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.

Claims

1. 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.

2. The method of claim 1, wherein the step of combining said CRC values for said chunks comprises the steps of:

performing a logical shift operation on a first subset of the CRC values for said chunks to thereby generate an extended CRC value; and

performing a logical bit by bit XOR operation on the extended CRC value and a second subset of the CRC values for said chunks, wherein said first and second subsets each comprise at least one of said CRC values for said chunks, and wherein said first subset of CRC values is distinct from said second subset of CRC values.

3. The method of claim 2, wherein said first and second subsets of CRC values each comprise a plurality of CRC values for said chunks.

4. The method of claim 2, wherein said logical shift operation on said first subset of CRC values performs the following logical operations:

a right shift operation by a predetermined number of k bits on said first subset of CRC values, perpending k 0-valued bits onto the left of said first subset of CRC values, and dropping k bits from the right of said first subset of CRC values.

5. The method of claim 1, further comprising the step of:

loading from persistent storage a table of precomputed CRC values for a range of chunks, and wherein the CRC value of at least two chunks is determined by performing a parallel table lookup on said table.

6. The method of claim 5, wherein the CRC value for the relevant data is generated by a source node, and is used by a target node to detect a transmission error in a data stream communicated between the source node and a target node of a communication system.

7. The method of claim 5, wherein the CRC value for the relevant data is generated by a target node, and is used by the target node to detect a transmission error in a data stream communicated between a source node and the target node of a communication system.

8. The method of claim 5, wherein the CRC value for the relevant data is generated by a storage device, and is used by a processing unit to detect a transmission error in a data stream communicated between the storage device and said processing unit of a data processing system.

9. The method of claim 5, wherein the CRC value for the relevant data is generated by a processing unit, and is used by the processing unit to detect a transmission error in a data stream communicated between a storage device and the processing unit in a data processing system.

10. The method of claim 5, wherein said table of CRC values is stored as data elements in at least one vector register V1, and wherein said chunks are stored as data elements in at least one vector register V2.

11. The method of claim 10, wherein portions of said data elements in said at least one vector register V1 are copied to a vector register VA, wherein portions of said data elements in said at least one vector register V2 are copied to a vector register VB, and wherein the parallel table lookup comprises at least one vector permute instruction that selects data elements from said source vector register VA based upon indices stored as data elements in said source vector register VB and writes the selected data elements into a target vector register VT.

12. The method of claim 10, wherein said table of CRC values is stored as data elements in a first plurality of vector registers, and wherein said chunks are stored as data elements in a second plurality of vector registers.

13. The method of claim 12, wherein portions of said data elements stored in said first plurality of vector registers are copied to a vector register VA, wherein portions of said data elements stored in said second plurality of vector registers are copied to a vector register VB, and wherein the parallel table lookup comprises at least one vector permute instruction that selects data elements from said source vector register VA based upon indices stored as data elements in said source vector register VB and writes the selected data elements into a target vector register.

14. The method of claim 12, wherein said indices of said source vector register VB of said vector permute instruction are byte aligned, and wherein, a shift operation is performed on said portions of said data elements stored in said second plurality of vector registers that are copied to the vector register VB.

15. The method of claim 1, wherein said chunks are 4 bits in length.

16. The method of claim 1, wherein each CRC value is a 32-bit CRC value.

17. The method of claim 1, wherein said step of determining the CRC value for each of said chunks comprises the step of accessing a table of precomputed CRC values using an indexing scheme that is dependent upon a size of the chunks and independent of a size of the CRC values.

18. 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.

19. The program storage device of claim 18, wherein the step of combining said CRC values for said chunks comprises the steps of:

performing a logical shift operation on a first subset of the CRC values for said chunks to thereby generate an extended CRC value; and

performing a logical bit by bit XOR operation on the extended CRC value and a second subset of the CRC values for said chunks, wherein said first and second subsets each comprise at least one of said CRC values for said chunks, and wherein said first subset of CRC values is distinct from said second subset of CRC values.

20. The program storage device of claim 19, wherein said first and second subsets of CRC values each comprise a plurality of CRC values for said chunks.

21. The program storage device of claim 19, wherein said logical shift operation on said first subset of CRC values performs the following logical operations:

a right shift operation by a predetermined number of k bits on said first subset of CRC values, perpending k 0-valued bits onto the left of said first subset of CRC values, and dropping k bits from the right of said first subset of CRC values.

22. The program storage device of claim 18, further comprising the step of:

loading from persistent storage a table of precomputed CRC values for a range of chunks, and wherein the CRC value of at least two chunks is determined by performing a parallel table lookup on said table.

23. The program storage device of claim 22, wherein the CRC value of the relevant data is generated by a source node, and is used by a target node to detect a transmission error in a data stream communicated between the source node and a target node of a communication system.

24. The program storage device of claim 22, wherein the CRC value of the relevant data is generated by a target node, and is used by the target node to detect a transmission error in a data stream communicated between a source node and the target node of a communication system.

25. The program storage device of claim 22, wherein the CRC value of the relevant data is generated by a storage device, and is used by a processing unit to detect a transmission error in a data stream communicated between the storage device and said processing unit of a data processing system.

26. The program storage device of claim 22, wherein the CRC value of the relevant data is generated by a processing unit, and is used by the processing unit to detect a transmission error in a data stream communicated between a storage device and the processing unit in a data processing system.

27. The program storage device of claim 18, wherein said table of CRC values is stored as data elements in at least one vector register V1, and wherein said chunks are stored as data elements in at least one vector register V2.

28. The program storage device of claim 27, wherein portions of said data elements in said at least one vector register V1 are copied to a vector register VA, wherein portions of said data elements in said at least one vector register V2 are copied to a vector register VB, and wherein the parallel table lookup comprises at least one vector permute instruction that selects data elements from said source vector register VA based upon indices stored as data elements in said source vector register VB and writes the selected data elements into a target vector register VT.

29. The program storage device of claim 27, wherein said table of CRC values is stored as data elements in a first plurality of vector registers, and wherein said chunks are stored as data elements in a second plurality of vector registers.

30. The program storage device of claim 29, wherein portions of said data elements stored in said first plurality of vector registers are copied to a vector register VA, wherein portions of said data elements stored in said second plurality of vector registers are copied to a vector register VB, and wherein the parallel table lookup comprises at least one vector permute instruction that selects data elements from said source vector register VA based upon indices stored as data elements in said source vector register VB and writes the selected data elements into a target vector register.

31. The program storage device of claim 30, wherein said indices of said source vector register VB of said vector permute instruction are byte aligned, and wherein, a shift operation is performed on said portions of said data elements stored in said second plurality of vector registers that are copied to the vector register VB.

32. The program storage device of claim 18, wherein said chunks are 4 bits in length.

33. The program storage device of claim 18, wherein each CRC value is a 32-bit CRC value.

34. The method of claim 18, wherein said step of determining the CRC value for each of said chunks comprises the step of accessing a table of precomputed CRC values using an indexing scheme that is dependent upon a size of the chunks and independent of a size of the CRC values.