Byte-wise determination of a checksum from a CRC-32 polynomial

Details Byte-wise determination of a checksum from a CRC-32 polynomial Byte-wise determination of a checksum from a CRC-32 polynomial

1992-11-12

1995-02-14

Envall, Jr., Roy N.

Excavating

G06F 1112

Patent

active

053901967

ABSTRACT:
A fast and memory efficient software method for generating a checksum employing a 32-bit generator polynomial such as X.sup.32 +X.sup.26 +X.sup.23 +X.sup.22 +X.sup.16 +X.sup.12 +X.sup.11 +X.sup.10 +X.sup.8 +X.sup.7 +X.sup.5 +X.sup.4 +X.sup.2 +X.sup.1 +X.sup.0. This end is achieved by performing the successive steps of reversing the 32-bit polynomial, to obtain hexadecimal EDB88320 in the example, as an initial CRC; XORing the least significant unprocessed byte of the data set with the least significant 8-bit byte of the CRC as currently positioned to obtain X8, X7, X6, X5, X4, X3, X2, X1; shifting the CRC right eight bits; for Xi=X8 to X3, inclusive, successively testing the highest numbered unprocessed Xi bit to determine if it is a one or a zero; if the Xi bit being tested is a zero, the CRC remains unchanged for this bit; if the Xi bit being tested is a one, then XOR the shifted CRC with the a 32-bit pattern of Xi corresponding to EDB88320 shifted right zero places for X8, one place for X7, two places for X6, three places for X5, four places for X4 and five places for X3; for Xi=X2 and X1, successively testing the highest numbered unprocessed Xi bit to determine if it is a one or a zero; if the Xi bit being tested is a zero, the CRC remains unchanged for this bit; if the Xi bit being tested is a one, then XOR the shifted CRC with the a 32-bit pattern of Xi corresponding to a second predetermined polynomial, hexadecimal EE0E612C in the example, shifted right zero places for X2 and one place for X1; if bytes of the data set remain to be processed, looping to process the next byte; and if the last byte has been processed, appending the current value of the CRC to the data set as a checksum.

REFERENCES:
patent: 4712215 (1987-12-01), Joshi et al.
patent: 4720830 (1988-01-01), Joshi et al.
patent: 4720831 (1988-01-01), Joshi et al.
patent: 4723243 (1988-02-01), Joshi et al.
patent: 5251215 (1993-10-01), Dravida et al.
patent: 5282214 (1994-01-01), Dravida
Powers, IBM Technical Disclosure Bulletin, "Dual Length Cyclic Redundancy Check Circuit", vol. 18, No. 7, Dec. 1975.
Beaven, IBM Tech. Disc. Bulletin, "Parallel Programmable Array-Structured CRC Generator", vol. 21, No. 5, Oct. 1978.
IBM Tech. Disc. Bulletin, "Cyclic Redundancy Checking For Multiple Valued Logic", vol. 34, No. 11, Apr. 1992.
IBM Tech. Disc. Bulletin, "High Efficiency Real Time Cyclic Redundancy Checker/Generator For Integrated Serv. Dig. Net.," vol. 34, No. 10B, Mar. 1992.
Breslau et al, IBM Tech. Disc. Bulletin, "Cyclic Redundancy Check for SDLC Architecture," vol. 19, No. 2, Nov. 1976.
Hinkel, IBM Tech. Disc. Bulletin, "Utilization of CRC Bytes For Error Correction on Multiple Formatted Data Strings", vol. 24, No. 1B, Jun. 1981.
IBM Tech. Disc. Bulletin, "Robust Complement/Recomplement Method," vol. 34, No. 10A, Mar. 1992.

Affiliated with

Also associated with

Rating

Byte-wise determination of a checksum from a CRC-32 polynomial does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Byte-wise determination of a checksum from a CRC-32 polynomial, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Byte-wise determination of a checksum from a CRC-32 polynomial will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-293389