CRC-16 in C
Ron Irvine
ron at scocan.sco.COM
Tue Nov 6 09:31:57 AEST 1990
> in my utilities library. His routine was based on two sixteen-entry
> tables, because, he said, they would fit in cache. Well one
> machine I use has a much larger cache than that, and the other
> has none, so I decided just for the fun of it to convert the algorithm
> to one based on one 256-entry table. I did that, and testing
> has verified that it produces the same results.
Yes a 256 table can be faster if it is in cache. But if you
are hashing a string for lookup in a table you may boot out some
other useful data in the cache. The nibble table (2 * 16) has
a better chance of cache hits than the sparse 256 table, and less
chance of booting out other useful data, but it takes more work
to calcutate a crc. Your mileage may vary.
> Now then, for purposes of documentation, and to verify the original
> algorithm, (and for my own education I guess), I decided to figure
> out what the thing actually does.
There are two popular 16 bit crc calculations. The one I
used is the crc16 used for DDCMP and Bisync communications.
Its polynomial is: x^16 + x^15 + x^2 + 1, with an initial
value of 0. I call it crc16(). The other common crc is used
in ADCCP, HDLC and SDLC; its polynomial is: x^16 + x^12 + x^5 + 1,
with an initial value of -1. I call it ccitt(). If you are
using the crc to hash you may want to play with both or invent
your own.
----------- Here is some more code -----------------
/* Computing a POLY number from the crc equation.
* Crc's are usually expressed as an polynomial expression such as:
*
* x^16 + x^12 + x^5 + 1
*
* Since the highest order term is to the power 16 this is a
* 16 bit crc. The POLY number is determined by setting bits
* corresponding to the power terms in the polynomial equation
* in an integer. To do this we number the bits of the integer
* with the most significant bit = bit 0. CAUTION: this is the
* opposite to the some bit numbering schemes. This is due to
* the least significant bit first convention of crc calculations.
* The above equation becomes:
*
* 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0
* |___.___.___.___|___.___.___.___|___.___.___.___|___.___.___.___|
* 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
* msb lsb
*
* Note: the "1" term is equivalent to "x^0" and the "x^16"
* term is ignored (it does determine the length to be 16 bits).
* Thus the POLY number is 0x8408 (ccitt crc).
*/
/* crc16 - DDCMP and Bisync (16 bit)
* x^16 + x^15 + x^2 + 1
*/
#define POLY_CRC16 0xa001
#define INIT_CRC16 0
/* CCITT - ADCCP, HDLC, SDLC (16 bit)
* x^16 + x^12 + x^5 + 1
*/
#define POLY_CCITT 0x8408
#define INIT_CCITT -1
/* a bit at a time */
unsigned crc_16(in)
char *in;
{
register unsigned short crc, bit;
register int i;
crc = INIT_CRC16;
while (*in) {
for (i=1; i <= 0x80; i<<=1) {
bit = (((*in)&i)?0x8000:0);
if (crc & 1) bit ^= 0x8000;
crc >>= 1;
if (bit) crc ^= (int)(POLY_CRC16);
}
++in;
}
return crc;
}
/* For even more fun - ccitt() crc routine */
/* nibble table for CCITT crc */
unsigned int ccitt_h[] = {
0x0000, 0x1081, 0x2102, 0x3183, 0x4204, 0x5285, 0x6306, 0x7387,
0x8408, 0x9489, 0xa50a, 0xb58b, 0xc60c, 0xd68d, 0xe70e, 0xf78f, };
unsigned int ccitt_l[] = {
0x0000, 0x1189, 0x2312, 0x329b, 0x4624, 0x57ad, 0x6536, 0x74bf,
0x8c48, 0x9dc1, 0xaf5a, 0xbed3, 0xca6c, 0xdbe5, 0xe97e, 0xf8f7, };
unsigned short
ccitt(in, size)
register unsigned char *in;
{
register unsigned int n, crc;
crc = -1;
while (*in) {
n = *in++ ^ crc;
crc = ccitt_l[n&0x0f] ^ ccitt_h[(n>>4)&0x0f] ^ (crc>>8);
};
return(crc);
}
More information about the Comp.lang.c
mailing list