It was always my intention to employ block messages for BODNET and that these should use a reliable checksum. I had considered going for the simple eight bit 'XOR' checksum often employed in simple microprocessor message protocols but I fancied using something a little more sophisticated. Many years ago I wrote a handler for the GEM80 ESP protocol which incorporated a function to generate a 16 bit CRC, adding data a byte at a time. Eventually I found an old listing languishing in the attic from which I could extract the code. Although I no longer have the document from which I derived the code Ben Johnson of Alstom has been kind enough to supply me with a scan of the relevant section of the GEM80 manuals.

There was a slight problem in that this algorithm was optimised for the CRC-16/CITT standard employing the ^16+^15+^2+1 polynomial and I really wanted to use the HDLC/X.25 standard which employed ^16+^12+^5+1. Unfortunately I don't have a copy of the original reference from which I'd derived the function and looking at the code, even after converting it to 'C', I have yet to fathom the algebraic rules by which it was devised so I set off across the web in search of an equivalent for my desired polynomial.

My search was successful in that I found a 'C' function heavily optimised for the ^16+^12+^5+1 polynomial, but on the way I also found a few others which were interesting. The first was a simple brute force calculation which would eat up processing time but at least could be used to verify the highly optimised version. The next two were both examples of using pre calculated look up tables, one eight bit and the other four bit (hence needing a smaller table). All three of these non optimised solutions although not what I was after for actual use would allow me to verify my optimised functions as they could be given the polynomial value to be used.

One last thing. The 4 bit look up table and 'hard wired' functions had been coded to calculate the CRC using the standard memory convention of most significant bit on the left and least significant on the right. As my serial routines follow the accepted communications convention of transmitting the rightmost bit first the code had to be modified to treat the right most bit as most significant and left most bit as least significant. Also please be aware that the assembler version of the optimised functions are for 'little endian' memory layout where a sixteen bit word is stored low byte then high byte in consecutive memory locations.

I have no intention of going into the theory and practice of 16 bit CRC calculation, there are any number of sites that do this. If you want know more I recommend you vist Ross WIlliams' site. I simply thought somebody else might find the following code fragments useful or interesting.

First is the simple brute force CRC algorithm courtesy of Mathew Rowe. 'C': crc_16.c
The next step is to use the same algorithm but employ it to calculate a look up table that can be used at runtime. This version is available from Summit Instruments, Inc. 'C': crc_smmt.c
Ashley Roll has optimised the look up table idea by keying on 4 bits rather than 8. 'C': crc_4bit.c
Now we get to the really optimised stuff. Credit to Eagle Air Australia Pty.Ltd. for this one which is 'hard wired' for the HDLC/X.25 ^16+^12+^5+1 polynomial, I still haven't figured out exactly how it works. I've created a 'x86' and PIC assembler version of this. 'C': crc_citt.c
TASM: crc_citt.asm
Just to complete things here's the original GEM80 ESP function I started off with. This is 'hard wired' for the CRC-16 ^16+^15+^2+1 polynomial. My original reference was page 4 from the GEM80 manual 'CRC/UI T434 Issue 1'. I created a 'C' version of this whilst trying to remember how it had been arrived at. TASM: crc_esp.asm
'C': crc_esp.c
Lastly a little bit of code to test all the above. These are the Borland 'C++' (I used C++ v4.0 for this little project) and PIC assembler files with which I exercised the various algorithm implementations. 'C++': crctest.cpp
PIC: crctest.asm


© Monitor Computing Services Limited 2002