BROWN%FORUM.VA.GOV@plus5.UUCP (04/24/87)
detect all burst errors of 16 bits or less and at least 99.997%
of all longer burst errors (see {U}Computer Networks{u} by Andrew
S. Tanenbaum).
PROPOSAL:
add in section 1.2.7:
$CRC calculates a 16 bit cyclic redundancy checksum
add in section 3.2.8:
$CRC({U}expr1{u},[{U}intexpr2{u}])
calculates a CRC (Cyclic Redundancy Checksum) using the polyno-
mial 1021(hex). The result will be in the closed interval [0-
65535]. The input data is {U}expr1{u}. The optional second
argument, {U}intexpr1{u}, is an input from a previous invocation
of $CRC. It is necessary for calculation of strings longer than
255 characters.
Note that 2 extra nulls ($C(0,0) should be concatenated to the
end of the specified string for most communication systems (this
allows for the 2 byte checksum field).
METHODOLOGY
To calculate the 16 bit CRC the message bits are considered to be
the coefficients of a polynomial. This message polynomial is
first multiplied by X^16 and then divided by the generator poly-
nomial (X^16 + X^12 + X^5 + 1) using modulo two arithmetic. The
remainder left after the division is the desired CRC. For a
message block of 128 bytes or 1024 bits, the message polynomial
will be of order X^1023. The high order bit of the first byte of
the message block is the coefficient of X^1023 in the message
polynomial. The low order bit of the last byte of the message
block is the coefficient of X^0 in the message polynomial.
Example of CRC Calculation written in C:
/*
* This function calculates the CRC
* The first argument is a pointer to the message block.
* The second argument is the number of bytes in the message
block.
* The function returns an integer which contains the CRC.
* The low order 16 bits are the coefficients of the CRC.
*/
int calcrc(ptr, count)
char *ptr;
int count;
{
int crc, i;
crc = 0;
while(--count >= 0) {
crc = crc ^ (int)*ptr++ << 8;
for(i = 0; i < 8; ++i)
if(crc & 0x8000)
crc = crc << 1 ^ 0x1021;
else
crc = crc << 1;
}
return (crc & 0xFFFF);
}