I have a telemetry stream that is passed through a hardware CRC generator appending the CRC to the end of each telemetry frame. Now I am trying to make something to verify the hardware generated CRC. I have old legacy code (see below) that computes the correct CRC (verified multiple times). However it is slow since each telemetry frame is 300+ bytes and there can be upwards of 10,000,000+ frames to process.
After some research I found some literature pointing me to a table driven approach. The legacy method uses a Poly of 0x8005, reverses the bit order of each byte before processing, and initializes the CRC to zero. However, after building tables for that poly with reversed and non-reversed input and just trying to work through even the first byte of data (0x10) I can not get anything to match what the legacy method is generating.
Inside the calcCRC16 function (below) the existing method checks the LSB where others seem to check the MSB ... and the bit shifts are to the right where other examples I have seen are to the left. I am getting lost in why this is especially since the bit order is swapped before passing it to this function. I have tried on-line calculators & manually doing the look-ups in tables switching the poly from 8005 to A001(reversed), normal and reversed input bytes, and every combination I can think of but can't get any table approach to match the legacy code which I know to be correct for our hardware implementation.
Can anyone help me out if I am missing something obvious? How would you go about creating a table based approach to create the same output? I am a novice at C++ and not really familiar with CRC generation and could be overlooking something fundamental. Sample code and output which was verified against the hardware CRC follows:
Sample Code: I just hard coded a few bytes out of a know telemetry stream as an example
/** ********************************************************************************
* TEST CRC METHOD
*******************************************************************************/
#include <iostream>
using namespace std;
unsigned char swapBits(unsigned char d);
void calcCRC16(unsigned int *CRCVal, unsigned char value);
/** **************************************************************************
* @function main
* TEST CRC METHOd
*******************************************************************************/
int main(int argc, char* argv[])
{
short dataLength = 5;
unsigned int givenCrc;
unsigned int calcCrc;
unsigned char byte[] = {0x10,0xbb,0x42,0x4d,0xfd};
/* Init CRC. */
calcCrc = 0;
cout << "Inital CRC = " << hex << calcCrc << "\n";
/* Read frame data. */
for (int i = 0; i < dataLength; i++)
{
cout << "byte = " << hex << static_cast<int16_t>(byte[i]) << " ";
calcCRC16(&calcCrc, swapBits(byte[i]));
cout << "calcCRC = " << hex << calcCrc << "\n";
}
}
/** ********************************************************************
* @function swapBits
* Swaps the bits so they match the order sent to CRC Gen Hardware
************************************************************************/
unsigned char swapBits(unsigned char d)
{
unsigned char t = 0;
int i = 0;
int n = 0x80;
for(i=0x01; i<0x100; i=i<<1)
{
if (d & i)
{
t|=n;
}
n=n>>1;
}
return t;
}
/** ********************************************************************
* @function calcCRC16
* WORKING METHOD VERIFIED AGAINST CRC HARDWARE
************************************************************************/
void calcCRC16(unsigned int *CRCVal, unsigned char value)
{
unsigned char lsb;
unsigned char bcnt;
for (bcnt=0 ; bcnt<8 ; bcnt++)
{
lsb = (value ^ *CRCVal) & 0x01;
*CRCVal >>= 1;
value >>= 1;
if (lsb != 0)
{
*CRCVal ^= 0x8005;
}
}
}
Output:
Inital CRC = 0
byte = 10 calcCRC = b804
byte = bb calcCRC = 1fb8
byte = 42 calcCRC = 461d
byte = 4d calcCRC = 3d47
byte = fd calcCRC = 683e
rev16(crc16(0, buf, len)) will give you the CRCs listed.
#include <stdio.h>
static unsigned short crc16_table[] = {
0x0000, 0xa001, 0xe003, 0x4002, 0x6007, 0xc006, 0x8004, 0x2005,
0xc00e, 0x600f, 0x200d, 0x800c, 0xa009, 0x0008, 0x400a, 0xe00b,
0x201d, 0x801c, 0xc01e, 0x601f, 0x401a, 0xe01b, 0xa019, 0x0018,
0xe013, 0x4012, 0x0010, 0xa011, 0x8014, 0x2015, 0x6017, 0xc016,
0x403a, 0xe03b, 0xa039, 0x0038, 0x203d, 0x803c, 0xc03e, 0x603f,
0x8034, 0x2035, 0x6037, 0xc036, 0xe033, 0x4032, 0x0030, 0xa031,
0x6027, 0xc026, 0x8024, 0x2025, 0x0020, 0xa021, 0xe023, 0x4022,
0xa029, 0x0028, 0x402a, 0xe02b, 0xc02e, 0x602f, 0x202d, 0x802c,
0x8074, 0x2075, 0x6077, 0xc076, 0xe073, 0x4072, 0x0070, 0xa071,
0x407a, 0xe07b, 0xa079, 0x0078, 0x207d, 0x807c, 0xc07e, 0x607f,
0xa069, 0x0068, 0x406a, 0xe06b, 0xc06e, 0x606f, 0x206d, 0x806c,
0x6067, 0xc066, 0x8064, 0x2065, 0x0060, 0xa061, 0xe063, 0x4062,
0xc04e, 0x604f, 0x204d, 0x804c, 0xa049, 0x0048, 0x404a, 0xe04b,
0x0040, 0xa041, 0xe043, 0x4042, 0x6047, 0xc046, 0x8044, 0x2045,
0xe053, 0x4052, 0x0050, 0xa051, 0x8054, 0x2055, 0x6057, 0xc056,
0x205d, 0x805c, 0xc05e, 0x605f, 0x405a, 0xe05b, 0xa059, 0x0058,
0xa0e9, 0x00e8, 0x40ea, 0xe0eb, 0xc0ee, 0x60ef, 0x20ed, 0x80ec,
0x60e7, 0xc0e6, 0x80e4, 0x20e5, 0x00e0, 0xa0e1, 0xe0e3, 0x40e2,
0x80f4, 0x20f5, 0x60f7, 0xc0f6, 0xe0f3, 0x40f2, 0x00f0, 0xa0f1,
0x40fa, 0xe0fb, 0xa0f9, 0x00f8, 0x20fd, 0x80fc, 0xc0fe, 0x60ff,
0xe0d3, 0x40d2, 0x00d0, 0xa0d1, 0x80d4, 0x20d5, 0x60d7, 0xc0d6,
0x20dd, 0x80dc, 0xc0de, 0x60df, 0x40da, 0xe0db, 0xa0d9, 0x00d8,
0xc0ce, 0x60cf, 0x20cd, 0x80cc, 0xa0c9, 0x00c8, 0x40ca, 0xe0cb,
0x00c0, 0xa0c1, 0xe0c3, 0x40c2, 0x60c7, 0xc0c6, 0x80c4, 0x20c5,
0x209d, 0x809c, 0xc09e, 0x609f, 0x409a, 0xe09b, 0xa099, 0x0098,
0xe093, 0x4092, 0x0090, 0xa091, 0x8094, 0x2095, 0x6097, 0xc096,
0x0080, 0xa081, 0xe083, 0x4082, 0x6087, 0xc086, 0x8084, 0x2085,
0xc08e, 0x608f, 0x208d, 0x808c, 0xa089, 0x0088, 0x408a, 0xe08b,
0x60a7, 0xc0a6, 0x80a4, 0x20a5, 0x00a0, 0xa0a1, 0xe0a3, 0x40a2,
0xa0a9, 0x00a8, 0x40aa, 0xe0ab, 0xc0ae, 0x60af, 0x20ad, 0x80ac,
0x40ba, 0xe0bb, 0xa0b9, 0x00b8, 0x20bd, 0x80bc, 0xc0be, 0x60bf,
0x80b4, 0x20b5, 0x60b7, 0xc0b6, 0xe0b3, 0x40b2, 0x00b0, 0xa0b1};
static unsigned char rev_table[] = {
0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0, 0x10, 0x90, 0x50, 0xd0,
0x30, 0xb0, 0x70, 0xf0, 0x08, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8,
0x18, 0x98, 0x58, 0xd8, 0x38, 0xb8, 0x78, 0xf8, 0x04, 0x84, 0x44, 0xc4,
0x24, 0xa4, 0x64, 0xe4, 0x14, 0x94, 0x54, 0xd4, 0x34, 0xb4, 0x74, 0xf4,
0x0c, 0x8c, 0x4c, 0xcc, 0x2c, 0xac, 0x6c, 0xec, 0x1c, 0x9c, 0x5c, 0xdc,
0x3c, 0xbc, 0x7c, 0xfc, 0x02, 0x82, 0x42, 0xc2, 0x22, 0xa2, 0x62, 0xe2,
0x12, 0x92, 0x52, 0xd2, 0x32, 0xb2, 0x72, 0xf2, 0x0a, 0x8a, 0x4a, 0xca,
0x2a, 0xaa, 0x6a, 0xea, 0x1a, 0x9a, 0x5a, 0xda, 0x3a, 0xba, 0x7a, 0xfa,
0x06, 0x86, 0x46, 0xc6, 0x26, 0xa6, 0x66, 0xe6, 0x16, 0x96, 0x56, 0xd6,
0x36, 0xb6, 0x76, 0xf6, 0x0e, 0x8e, 0x4e, 0xce, 0x2e, 0xae, 0x6e, 0xee,
0x1e, 0x9e, 0x5e, 0xde, 0x3e, 0xbe, 0x7e, 0xfe, 0x01, 0x81, 0x41, 0xc1,
0x21, 0xa1, 0x61, 0xe1, 0x11, 0x91, 0x51, 0xd1, 0x31, 0xb1, 0x71, 0xf1,
0x09, 0x89, 0x49, 0xc9, 0x29, 0xa9, 0x69, 0xe9, 0x19, 0x99, 0x59, 0xd9,
0x39, 0xb9, 0x79, 0xf9, 0x05, 0x85, 0x45, 0xc5, 0x25, 0xa5, 0x65, 0xe5,
0x15, 0x95, 0x55, 0xd5, 0x35, 0xb5, 0x75, 0xf5, 0x0d, 0x8d, 0x4d, 0xcd,
0x2d, 0xad, 0x6d, 0xed, 0x1d, 0x9d, 0x5d, 0xdd, 0x3d, 0xbd, 0x7d, 0xfd,
0x03, 0x83, 0x43, 0xc3, 0x23, 0xa3, 0x63, 0xe3, 0x13, 0x93, 0x53, 0xd3,
0x33, 0xb3, 0x73, 0xf3, 0x0b, 0x8b, 0x4b, 0xcb, 0x2b, 0xab, 0x6b, 0xeb,
0x1b, 0x9b, 0x5b, 0xdb, 0x3b, 0xbb, 0x7b, 0xfb, 0x07, 0x87, 0x47, 0xc7,
0x27, 0xa7, 0x67, 0xe7, 0x17, 0x97, 0x57, 0xd7, 0x37, 0xb7, 0x77, 0xf7,
0x0f, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef, 0x1f, 0x9f, 0x5f, 0xdf,
0x3f, 0xbf, 0x7f, 0xff};
unsigned crc16(unsigned crc, unsigned char *buf, int len)
{
while (len--) {
crc ^= *buf++ << 8;
crc = (crc << 8) ^ crc16_table[(crc >> 8) & 0xff];
}
return crc & 0xffff;
}
inline unsigned rev16(unsigned val)
{
return (rev_table[val & 0xff] << 8) | rev_table[(val >> 8) & 0xff];
}