home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
ftp.barnyard.co.uk
/
2015.02.ftp.barnyard.co.uk.tar
/
ftp.barnyard.co.uk
/
cpm
/
walnut-creek-CDROM
/
CPM
/
MODEMS
/
MODEM
/
CRC.NZT
/
CRC.NOT
Wrap
Text File
|
2000-06-30
|
9KB
|
212 lines
Calculating the XMODEM CRC
J. LeVan, Ph.D.
Introduction:
I have been in the process of developing a terminal emulator
program for my home computer. I was very unhappy with the Xmodem
transfer rate, especially at high modem speeds. The checksum
method is clearly faster, but cannot catch communication errors
as effectively. The CRC method has an upper end throughput of
500 bytes per second.
I place a help call on CompuServe and receive an intriquing
response from Bela Lubkin. The algorithm he suggested appeared
to be much quicker than the classical bit shift method. It was
not at all clear to me how the algorithm worked. The purpose of
this note is an explanation of how and why a table lookup
algorithm can work.
Throughout this note, I will use "effective throughput" to
mean:
(SizeOfPacket * NumberOfPackets)/(TimeOfEot - TimeOfInitialSOH)
All source code will be in C. These programs were written to run
on an Apple MacIntosh, which is equipped with a high speed serial
port.
Below is the standard bit shift and occasionally XOR
algorithm. The condition for doing the XOR is simply, if a 1 is
going to be shifted out of the sign bit then shift and XOR the
old CRC with the generator. Note that the inner loop is
performed exactly eight times.
________________________________________________________________
___Fig.1: Bit Shift CRC_________________________________________
unsigned short ComputeCrc(crc,bufptr,len)
register unsigned short crc; /* unsigned shorts are 16 bits */
register char *bufptr;
register short len;
{
register int i;
while (len--) { /* calculate CRC from end to start*/
crc ^= (unsigned short) (*bufptr++)<<8;
for ( i=0 ; i<8 ; ++i ) {
if (crc & 0x8000)
crc = (crc << 1) ^ 0x1021;
else
crc <<= 1;
}
}
return(crc);
}
________________________________________________________________
After exactly eight shifts, there will be no carries from
the low byte out of the top of the high byte. This leads us to a
critical observation:
Ob 1: Whether or not an XOR is done with the CRC does *not*
depend on the low byte of the CRC.
Let A, B, and C be sixteen bit unsigned quantities. We'll
use the standard C notation for XOR, a carat (^). The following
mathematical properties hold.
Ob 2: XOR is Associative and Commutative. I.e: For any choice
of A, B and C; these equations will always hold true:
A^B = B^A (1)
(A^B)^C = A^(B^C) (2)
Likewize, using the standard C notation for a left shift
( A<<B means A shifted left B times ), it can be shown that left
shift is distributive over XOR.
Ob 3: Left shift distributes over XOR. I.e: For any choice of A
and B; this equation will always hold true:
(A^B)<<1 = (A<<1) ^ (B<<1) (3)
Now take a close look at the inner loop of the ComputeCrc
algorithm. First decompose the variable 'crc' into two parts,
'crch' and 'crcl'. The variable 'crch' is simply the high byte
of 'crc' with the low byte changed to all zeroes. Similarly,
'crcl' is the low byte of 'crc', with zeroes in the high half of
that word. To create 'crc' from 'crch' and 'crcl' we can use:
crc = crch ^ crcl
The first pass through the loop yields:
crc = ((crch ^ crcl)<<1) ^ P1
wherein P1 is either 0 or 0x1021. After two iterations we have:
crc = {[ ((crch^crcl)<<1) ^ P1] << 1} ^ P2
or:
crc = (crch << 2) ^ (crcl << 2) ^ (P2 << 1) ^ P2
wherein P2 is either 0 or 0x1021. Looking ahead we can write the
equation for crc after eight iterations:
crc = (crch << 8) ^ (crcl << 8) ^ ((P1<<7) ^ (P2<<6) ^..^ P8)
The term (crch<<8) vanishes, and (crcl<<8) is easy enough to
compute so the only question remaining is how we can calculate
the last term. Observation one tells us that the third term only
depends on the initial value of crch. This means that we can
compute the third term by computing all possible values in the
inner loop for crc = 0x0000 to 0xFF00 stepping by 0x100 and
storing the values in an array CrcTable, indexed by values
running from 0x00 to 0xFF. This is exactly the function of the
algorithm presented below:
________________________________________________________________
___Fig.2: Table lookup CRC______________________________________
unsigned short CrcTable[256]; /* declaration for the table */
InitCrcTable()
/* this routine calls ComputeCrc, defined in Fig.1 */
{
int count;
char zero;
zero=0;
for ( count=0 ; count<256 ; count++ )
CrcTable[count] = ComputeCrc(count<<8,&zero,1);
}
unsigned short TableCrc(crc,bufptr,len)
register unsigned short crc;
register unsigned char *bufptr;
register short len;
{
while (len--)
crc = CrcTable[crc >> 8^(*bufptr++)] ^ crc<<8;
return(crc);
}
________________________________________________________________
Thus our third term is found by:
((P1<<7) ^ (P2<<6) ^ ... ^ P8) = CrcTable[crch>>8]
the final crc is caluclated by:
crc = crc_table[crch>>8] ^ (crcl<<8)
Substituting this relation into the algorithm in Fig. 1, we
easily obtain the algorithm in Fig. 2.
That much having been said, it only remains to be seen,
whether or not it has all been worthwhile. How much faster is
table lookup?
After building a 128 byte sector filled with random numbers,
I ran a benchmark in which the CRC and Checksum were each
calculated 100 times with the following results. Here each tick
represents 1/60th of a second.
________________________________________________________________
___Table.1: Comparison of methods for 100 sectors_______________
Slow CRC 120 ticks
Table CRC 25 ticks
Checksum 3 ticks
________________________________________________________________
The table driven method is an order of magnitude faster than
the older CRC method, and only an order of magnitude slower than
the Checksum method. This offers a much smoother trade off than
originally available with the CRC check. What do these
differences mean in terms of effective through put?
My communications program also uses the following
optimizations which can affect transfer speed:
All disk I/O is double buffered.
The transmitter sends the body of the Xmodem Packet while
simultaneously calculating the CRC. This leads to an almost zero
calculate time at low speeds.
The machine on the receiving end of the line only calculates
the CRC after a complete packet has arrived.
________________________________________________________________
___Table.2: Transfer measurements_______________________________
Effective Throughput: (bytes/sec)
Baud: 1200 2400 9600 19200 57600
Method: (128 byte packets)
Slow CRC 106.......201.......598.......770.......773
Table CRC 109.......210.......692.......1113......1172
Checksum 110.......213.......709.......1155......1263
Method: (1k byte packets)
Slow CRC ..........210.......628.......939.......994
Table CRC ..........220.......729.......1185......1185
Checksum ..........222.......745.......1226......1973
________________________________________________________________
One should take benchmarks with a grain of salt. However,
it is clear that the table lookup algorithm stays closer to the
checksum method than the standard bit shift algorithm. The
efficiency and speed of compiled code can vary greatly from
machine to machine. These tests were made with two computers
linked directly through their serial ports.
I have found that CompuServe typically yields and effective
throughput of 60-80 bytes per second at 1200 baud. Genie
typically yields 70-80 bytes per second, and my neighborhood Vax
785 lets me run with an effective throughput of 103-105 bytes per
second, all with Xmodem.
In my first attempt at Xmodem, I used a function call for
processing each character in the crc loop. In addition, I did
not overlap the CRC calculation with transmission of the packet.
This was a dreadful mistake. I could not get an effective
throughput of more than 500 characters per second even with 4k
buffers at any speed. The bottom line is that it take a number
of optimizations to speed up a complex process.