Development: Small Table CRC

/*
 
	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);
}