Development: Small Table CRC
Jump to navigation
Jump to search
/*
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);
}