Embedded Small Table CRC16 Routines
Author: Ashley Roll. May, 2002.
To generate a CRC16 value efficiently, one needs to use a table driven algorithm. The generation of these tables fairly simple but the code is often hard to find and is almost always designed for generating a 256 entry table for operating on 8 bits at a time.
In Embedded Systems there are often severe space limitations and a full table of 256 16 bit entries would never fit. However the CRC16 algorithm does not require such a large table to work. It can be done smaller. On the PIC micro processors, a nibble (4 bit) implementation can be achieved fairly easily and this requres only a table of 16 16-bit values or 32 bytes.
This code was developed from the explanations and examples at http://www.geocities.com/SiliconValley/Pines/8659/crc.htm This is a good reference for those wanting to understand what is happening in the CRC algorithm.
The ex4bit.c file contains an implementation of the CCITT CRC16 which processes the message data in 4-bit chunks. This sould be easily portable to any processor. I didn't optimise the code to allow easier understanding of what it is doing. This code allows a very small 16 element table to be used. Note that the lookup value is actually a 16-bit number and most small embedded processors are only able to deal with an 8-bit table lookup so I've split the data accross two tables.
A PIC Assmebler implementation, piccrc.asm can also be found. This is the version containing some optimisation from Scott Dattalo. This results in 74 instruction cycles to update the CRC registers for each byte of message data. The two lookup tables are merged into one larger one. It can probably be optimised further (Scott suggested some other optimisations, but they make the code much harder to understand). This code was written to work on a PIC12C508 and so should be portable to any PIC processor. The original version (85 instructions) can be found in piccrcorig.asm.
To see how the lookup table was generated, please refer to the gentable.c file. This is a simple C program to generate the tables for a given polynomial.
If you have any questions, please don't hesitate to contact us.