Support » Pololu TReX User’s Guide » 5. The Serial Interface »
5.f. CRC-Generation Algorithm in C
The CRC algorithm is typically defined as a bit-wise operation, however it is possible to rewrite the algorithm to work at the byte level if we do some calculations ahead of time. We can store CRC computations for all 256 possible byte values when our program first runs, and then retrieve those values as needed when generating a CRC for a given message. This requires we set aside 256 bytes of RAM/EEPROM/flash, but it makes the CRC calculation for an arbitrary message much faster than if we work through the message bit by bit.
The following sample code stores a CRC lookup table in RAM using the function GenerateCRCTable(), which only needs to be called once (probably somewhere during the initialization phase of your program). You could easily change this function to store the lookup table to EEPROM or flash. To process a message, initialize your CRC variable to zero and use the CRCAdd() function to “add” each message byte to your CRC, as is done in the getCRC() function.
unsigned char CRCPoly = 0x89; // the value of our CRC-7 polynomial unsigned char CRCTable[256]; void GenerateCRCTable() { int i, j; // generate a table value for all 256 possible byte values for (i = 0; i < 256; i++) { CRCTable[i] = (i & 0x80) ? i ^ CRCPoly : i; for (j = 1; j < 8; j++) { CRCTable[i] <<= 1; if (CRCTable[i] & 0x80) CRCTable[i] ^= CRCPoly; } } } // adds a message byte to the current CRC-7 to get a the new CRC-7 unsigned char CRCAdd(unsigned char CRC, unsigned char message_byte) { return CRCTable[(CRC << 1) ^ message_byte]; } // returns the CRC-7 for a message of "length" bytes unsigned char getCRC(unsigned char message[], int length) { int i; unsigned char CRC = 0; for (i = 0; i < length; i++) CRC = CRCAdd(CRC, message[i]); return CRC; }