Program CRC;
{ CRC generation program, version 7b (optimized + timing + documentation)
This set of implementations was written by David Dantowitz, and
has been placed in the public domain, to be used at the user's
discretion.
This program demonstrates various ways by which Cyclic
Redundancy Checks (CRC) may be computed and their relative speeds.
Please note the cautionary notice involving the routine SET_TIMER.
This routine should be used only by users who understand its
consequences and who wish to experiment with interrupt and timer
routines. The routine has been written for use on an IBM PC or
compatible.
The variable TIME is the location of the low 16 bits of the TIMER
location incremented by DOS 2.0 with each clock tick. It is defined
in the source code for the IBM PC ROM BIOS. This should work with
most compatibles as well as later versions of the operating system.
Here are some sample results. These were obtained using TURBO 3.0
under DOS 2.0 on a SEEQUA Chameleon. (Your mileage may vary.)
(Note that the CRC is printed to assure that all implementations
are working properly.)
D a t a S t r e a m L e n g t h
512 1024 2048 4096 32767
No table 0.33 0.65 1.31 2.62 20.93 CRC = -31717
Nybble table 0.10 0.18 0.38 0.76 6.03 CRC = -31717
Two Nybble tables 0.10 0.18 0.36 0.74 5.88 CRC = -31717
Byte table 0.08 0.16 0.32 0.64 5.12 CRC = -31717
Nybble string 0.03 0.05 0.09 0.18 1.50 CRC = -31717
Byte string 0.01 0.03 0.05 0.09 0.73 CRC = -31717
}
Const
max = 32767;
Type
Bytes = Array [1..max] of Byte;
Var
time : Integer Absolute $0040:$006c; { TIMER_LOW
IBM PC ROM BIOS location }
initial_clock, stop, j, i : Integer;
length : Array [1..5] of Integer;
table_16 : Array [0..15] of Integer;
table_32a : Array [0..16] of Integer;
table_32b : Array [0..16] of Integer;
table_256 : Array [0 .. 255] of Integer;
CRC_value : Integer;
byte_string : Bytes;
POLY : Integer;
{
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.
Since all polynomials have a highest term (X^a) we drop the
highest term during computation (shift right one bit).
Here are some examples :
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 three 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
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)
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.
CRC use ...
The CRC is then appended to the end of the data stream. 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.
}
{
This work was prompted by a submission by David Kirschbaum,
who unknowingly submitted a program that contained an error.
I have not determined if what it computed has any reliable
error-detecting capabilities, only that it was an attempt to
compute a CRC, that really did not work. The original code
is correctly used in the program KERMIT (Columbia University)
to compute the CRC-CCITT polynomial CRC.
My address is
David Dantowitz
Digital Equipment Corporation
Dantowitz%eagle1.dec@decwrl
The views and ideas expressed here are my own and do not necessarily
reflect those of the Digital Equipment Corporation.
David Kirschbaum
Toad Hall
ABN.ISCAMS@USC-ISID.ARPA
}
Procedure set_timer(count : Integer);
{
This routine sets the clock (timer) count-down value to
count. The DOS value is 0 (this is the maximum value ...
it really means 65536). This routine is used to obtain
better resolution in timing.
WARNING : The setting of count to too small a value will
HANG your system. Please study interrupts in
real time systems before using this routine.
WARNING : This routine was written to run on an IBM PC or
compatible. Disable this routine when this
program is run on other machines.
}
Begin
inline($b0/$36/ { mov al,36 }
$e6/$43/ { out 43,al }
$8b/$86/count/ { mov ax,bp[count] }
$e6/$40/ { out 40,al }
$88/$e0/ { mov al,ah }
$e6/$40); { out 40,al }
End;
Procedure simple_crc(b:byte);
{
This routine computes the CRC value bit by bit. The initial value
is assumed to be in a global variable CRC_value and the global variable
POLY contains the representation of the polynomial be used. The routine
is called for each byte. The result is placed in the global CRC_value.
}
Var
i : Integer;
Begin
CRC_value := b xor CRC_value;
For i := 1 to 8 Do
Begin
If (CRC_value and 1) = 1
then CRC_value := (CRC_value shr 1) xor POLY
else CRC_value := CRC_value shr 1;
End;
End;
Procedure generate_table_16(POLY : Integer);
{
This routine computes the remainder values of 0 through 15 divided
by the polynomial represented by POLY. These values are placed in a
table and used to compute the CRC of a block of data efficiently.
This implementation only permits polynomials up to degree 16.
}
Var
val, i, result : Integer;
Begin
For val := 0 to 15 Do
Begin
result := val;
For i := 1 to 4 Do
Begin
If (result and 1) = 1
then result := (result shr 1) xor POLY
else result := result shr 1;
End;
table_16[val] := result;
End
End;
Procedure generate_table_32(POLY : Integer);
{
This routine computes the remainder values of 0 through 15 divided
by the polynomial represented by POLY. These values are placed in two
tables and used to compute the CRC of a block of data efficiently.
This implementation only permits polynomials up to degree 16.
}
Var
val, i, result, divide : Integer;
Begin
{
Table_32a divides the number for eight bits (not four).
Note that Table_32b is identical to Table_16.
}
For val := 0 to 15 Do
Begin
result := val;
For i := 1 to 4 Do
Begin
If (result and 1) = 1
then result := (result shr 1) xor POLY
else result := result shr 1;
End;
table_32b[val] := result;
End;
For val := 0 to 15 Do
Begin
result := table_32b[val];
For i := 1 to 4 Do
Begin
If (result and 1) = 1
then result := (result shr 1) xor POLY
else result := result shr 1;
End;
table_32a[val] := result;
End;
End;
Procedure generate_table_256(POLY : Integer);
{
This routine computes the remainder values of 0 through 255 divided
by the polynomial represented by POLY. These values are placed in a
table and used to compute the CRC of a block of data efficiently.
More space is used, but the CRC computation will be faster.
This implementation only permits polynomials up to degree 16.
}
Var
val, i, result, divide : Integer;
Begin
For val := 0 to 255 Do
Begin
result := val;
For i := 1 to 8 Do
Begin
If (result and 1) = 1
then result := (result shr 1) xor POLY
else result := result shr 1;
End;
table_256[val] := result;
End
End;
Procedure Compute_crc_16(next_byte : byte);
{
This routine calculates the CRC and stores the result in a global
variable CRC_value. You must first initialize CRC_value to 0 or the
proper initial value for the CRC and then call this routine with
each byte.
This routine uses table_16.
}
Begin
inline(
$8b/$16/CRC_value/ {mov dx,CRC_value }
$32/$56/