# Development: Small Table CRC

From WxWiki

/* Computing CRCs This set of implementations was written by David M. Dantowitz, and has been placed in the public domain, to be used at the user's discretion. The original code was implemented in Turbo Pascal 3.0 this submission is a version written in C. This program demonstrates various ways by which Cyclic Redundancy Checks (CRC) may be computed and their relative speeds. CRC polynomials in this program are represented by replacing each term that is non-zero with a 1 and each zero term with a 0. Note that the highest order bits represent the low order terms of the polynomial. Thus X^3+X^1+1 becomes 1101 and X^4+X^1+1 becomes 11001. Now, since all polynomials have a highest term (X^a) we drop the highest term during computation (shift right one bit, dropping the low bit). Here are some examples of conversion from symbolic to binary representation (but not necessarily polynomials with desirable CRC properties): Polynomial Representation Hex X^5 + X^2 + 1 10100 $14 X^7 + 1 1000000 $40 X^3+X^2+X^1+1 111 $7 X^6+X^5+X^3+1 100101 $25 For a good discussion of polynomial selection see "Cyclic Codes for Error Detection", by W. W. Peterson and D. T. Brown, Proceedings of the IEEE, volume 49, pp 228-235, January 1961. A reference on table driven CRC computation is "A Cyclic Redundancy Checking (CRC) Algorithm" by A. B. Marton and T. K. Frambs, The Honeywell Computer Journal, volume 5, number 3, 1971. Also used to prepare these examples was "Computer Networks", by Andrew S. Tanenbaum, Prentice Hall, Inc. Englewood Cliffs, New Jersey, 1981. The following four polynomials are international standards: CRC-12 = X^12 + X^11 + X^3 + X^2 + X^1 + 1 CRC-16 = X^16 + X^15 + X^2 + 1 CRC-CCITT = X^16 + X^12 + X^5 + 1 CCITT-32 = X^32 + X^26 + X^23 + X^22 + X^16 + X^12 + X^11 + X^10 + X^8 + X^7 + X^5 + X^4 + X^2 + X^1 + 1 In Binary and hexadecimal : Binary Hex CRC-12 = 1111 0000 0001 $0F01 CRC-16 = 1010 0000 0000 0001 $A001 CRC-CCITT = 1000 0100 0000 1000 $8404 (Used below) CCITT-32 = 1110 1101 1011 1000 1000 0011 0010 0000 $EDB88320 The first is used with 6-bit characters and the second two with 8-bit characters. All of the above will detect any odd number of errors. The second two will catch all 16-bit bursts, a high percentage of 17-bit bursts (~99.997%) and also a large percentage of 18-bit or larger bursts (~99.998%). The paper mentioned above (Peterson and Brown) discusses how to compute the statistics presented which have been quoted from Tanenbaum. (A burst of length N is defined a sequence of N bits, where the first and last bits are incorrect and the bits in the middle are any possible combination of correct and incorrect. See the paper by Peterson and Brown for more information) Note that when using a polynomial of degree N, the CRC is the first N bits of the value returned by the routines below. (e.g. with CRC-12, the CRC is bits 0 to 11 of the CRC value, with the other two mentioned above, the CRC is all 16 bits.) Here is a quick idea of what is being calculated ... The CRC is the residual from division of the data stream by the CRC polynomial. The data stream is also thought of as a polynomial, with the highest order term being the lowest bit of the first byte of the data stream and the lowest order term of the polynomial being the high bit of the last byte of data. The actual division is performed on the data stream polynomial multiplied by X^y where y is the degree of the CRC polynomial. All math used to compute CRCs is done modulo 2. This means the following relationships are used: 0+0=0 0+1=1 1+0=1 1+1=0 (XOR) 0-0=0 0-1=1 1-0=1 1-1=0 (XOR) 0*0=0 0*1=0 1*0=0 1*1=1 (AND) Thus addition and subtraction have NO carries or borrows. Here is a sample computation showing the actual division. Polynomial = X^4+X^3+1; Data = $94. The division performed is 1001 into 0010 1001. Notice that the highest order terms of the data polynomial are the lowest order bits of the data stream. We will also multiply the dividend by X^4 as noted above: 1011011 - The quotient is not important and is discarded. 1001/001010010000 -1001 ---- The extra 0s result from multiplying the data by X^4 ---- 1101 <-- The code below calculates this value -1001 ---- 1000 -1001 ---- 1000 -1001 ---- 0001 This is the CRC (the residual from the division)! The code below does not shift the data by the number of bits equal to the degree of the CRC polynomial. There is no ill effect caused by not doing this multiply. Now, the result of the CRC computation is just the residue from the division of the data by the CRC. None of the routines below appear to compute a division. In the example above the subtractions are really XORs (pronounced exclusive OR). XOR has the same behavior as +/- in modulo two arithmetic, so it is used in the computations. The first CRC routine below (Simple_CRC) models the computation lucidly. The other routines use various optimization techniques to speed the computation. CRC use ... The CRC is appended to the end of the original data stream (or stored separetely). When the receiver gets the data stream, the CRC is again computed and matched against the received CRC, if the two do not match then an error has most likely occurred. My address is David Dantowitz Dantowitz Consulting and Research P.O. Box 8105 Englewood, NJ 07631 (201) Low-Bug-C AppleLink: Dantowitz */ #include <stdio.h> #include <string.h> #define INITIAL_CRC 0xFFFFFFFF /* This result was obtained by calling make_crc_table(0xedb88320). */ int crc_table[16] = { 0x00000000, 0xfdb71064, 0xfb6e20c8, 0x06d930ac, 0xf6dc4190, 0x0b6b51f4, 0x0db26158, 0xf005713c, 0xedb88320, 0x100f9344, 0x16d6a3e8, 0xeb61b38c, 0x1b64c2b0, 0xe6d3d2d4, 0xe00ae278, 0x1dbdf21c }; make_crc_table(crc_poly) int crc_poly; { int i, val, result; for (val = 0; val < 16; val++) { result = val; for (i = 0; i < 4; i++) if (result & 1) result = (result >> 1) ^ crc_poly; else result >>= 1; crc_table[val] = result; printf("0x%08lx\n", result); } } int compute_crc(old_crc, s, len) int old_crc; char *s; int len; { int i; for (i = 0; i < len; i++) { /* XOR in the data. */ old_crc ^= s[i]; /* Perform the XORing for each nybble */ old_crc = (old_crc >> 4) ^ crc_table[old_crc & 0x0f]; old_crc = (old_crc >> 4) ^ crc_table[old_crc & 0x0f]; } return (old_crc); } main() { char line[100]; int crc_val; int len; /* make_crc_table(0xedb88320); done at compile time... */ /* initialize the crc -- start with this value each time you start a session. */ crc_val = INITIAL_CRC; strcpy(line, "This will test the crc function"); len = strlen(line); crc_val = compute_crc(crc_val, line, len); /* let's add MORE text to the CRC -- they can be cumulative across many blocks of data. */ strcpy(line, "More text to add"); len = strlen(line); crc_val = compute_crc(crc_val, line, len); }