Computing CRC16 with reflected / bit reversed input in C

Question

I want to compute the reflected CRC16 of the CCITT polynomial 0x1021 starting from 0xC6C6 (no XOR at end, also known as CRC16-A on this page https://crccalc.com) in two different ways with (embedded) C.

For the two alternatives, I want to use the polynomial 0x1021 starting with 0xC6C6 as well as the reflected polynomial 0x8408 starting from 0x6363 (= reflect(0xC6C6)).

Assume I have a lookup-table for each polynomial:

static const UINT16 au16Table1021[256u]

and

static const UINT16 au16Table8408[256u]

and a reflect function that reverses the bit order of a byte (e.g. based on In C/C++ what's the simplest way to reverse the order of bits in a byte?)

From the accepted answer of How to configure calculation of CRC table I expected that I would get the same result by reflecting the input, the starting CRC (wOldCRC = 0xC6C6), shifting the CRC calculation in the opposed direction and finally reflecting the resulting CRC. However, the second option I tried does not yield the expected result. What am I doing wrong?

Minimal (more or less) working example with incorrect CRC for option 2:

#include <stdio.h>
#include <stdlib.h>
typedef unsigned char uint8_t;
typedef unsigned short uint16_t;

static const uint16_t crcTable1021[256u] = {
  0x0000u, 0x17CEu, 0x0FDFu, 0x1811u, 0x1FBEu, 0x0870u, 0x1061u, 0x07AFu,
  0x1F3Fu, 0x08F1u, 0x10E0u, 0x072Eu, 0x0081u, 0x174Fu, 0x0F5Eu, 0x1890u,
  0x1E3Du, 0x09F3u, 0x11E2u, 0x062Cu, 0x0183u, 0x164Du, 0x0E5Cu, 0x1992u,
  0x0102u, 0x16CCu, 0x0EDDu, 0x1913u, 0x1EBCu, 0x0972u, 0x1163u, 0x06ADu,
  0x1C39u, 0x0BF7u, 0x13E6u, 0x0428u, 0x0387u, 0x1449u, 0x0C58u, 0x1B96u,
  0x0306u, 0x14C8u, 0x0CD9u, 0x1B17u, 0x1CB8u, 0x0B76u, 0x1367u, 0x04A9u,
  0x0204u, 0x15CAu, 0x0DDBu, 0x1A15u, 0x1DBAu, 0x0A74u, 0x1265u, 0x05ABu,
  0x1D3Bu, 0x0AF5u, 0x12E4u, 0x052Au, 0x0285u, 0x154Bu, 0x0D5Au, 0x1A94u,
  0x1831u, 0x0FFFu, 0x17EEu, 0x0020u, 0x078Fu, 0x1041u, 0x0850u, 0x1F9Eu,
  0x070Eu, 0x10C0u, 0x08D1u, 0x1F1Fu, 0x18B0u, 0x0F7Eu, 0x176Fu, 0x00A1u,
  0x060Cu, 0x11C2u, 0x09D3u, 0x1E1Du, 0x19B2u, 0x0E7Cu, 0x166Du, 0x01A3u,
  0x1933u, 0x0EFDu, 0x16ECu, 0x0122u, 0x068Du, 0x1143u, 0x0952u, 0x1E9Cu,
  0x0408u, 0x13C6u, 0x0BD7u, 0x1C19u, 0x1BB6u, 0x0C78u, 0x1469u, 0x03A7u,
  0x1B37u, 0x0CF9u, 0x14E8u, 0x0326u, 0x0489u, 0x1347u, 0x0B56u, 0x1C98u,
  0x1A35u, 0x0DFBu, 0x15EAu, 0x0224u, 0x058Bu, 0x1245u, 0x0A54u, 0x1D9Au,
  0x050Au, 0x12C4u, 0x0AD5u, 0x1D1Bu, 0x1AB4u, 0x0D7Au, 0x156Bu, 0x02A5u,
  0x1021u, 0x07EFu, 0x1FFEu, 0x0830u, 0x0F9Fu, 0x1851u, 0x0040u, 0x178Eu,
  0x0F1Eu, 0x18D0u, 0x00C1u, 0x170Fu, 0x10A0u, 0x076Eu, 0x1F7Fu, 0x08B1u,
  0x0E1Cu, 0x19D2u, 0x01C3u, 0x160Du, 0x11A2u, 0x066Cu, 0x1E7Du, 0x09B3u,
  0x1123u, 0x06EDu, 0x1EFCu, 0x0932u, 0x0E9Du, 0x1953u, 0x0142u, 0x168Cu,
  0x0C18u, 0x1BD6u, 0x03C7u, 0x1409u, 0x13A6u, 0x0468u, 0x1C79u, 0x0BB7u,
  0x1327u, 0x04E9u, 0x1CF8u, 0x0B36u, 0x0C99u, 0x1B57u, 0x0346u, 0x1488u,
  0x1225u, 0x05EBu, 0x1DFAu, 0x0A34u, 0x0D9Bu, 0x1A55u, 0x0244u, 0x158Au,
  0x0D1Au, 0x1AD4u, 0x02C5u, 0x150Bu, 0x12A4u, 0x056Au, 0x1D7Bu, 0x0AB5u,
  0x0810u, 0x1FDEu, 0x07CFu, 0x1001u, 0x17AEu, 0x0060u, 0x1871u, 0x0FBFu,
  0x172Fu, 0x00E1u, 0x18F0u, 0x0F3Eu, 0x0891u, 0x1F5Fu, 0x074Eu, 0x1080u,
  0x162Du, 0x01E3u, 0x19F2u, 0x0E3Cu, 0x0993u, 0x1E5Du, 0x064Cu, 0x1182u,
  0x0912u, 0x1EDCu, 0x06CDu, 0x1103u, 0x16ACu, 0x0162u, 0x1973u, 0x0EBDu,
  0x1429u, 0x03E7u, 0x1BF6u, 0x0C38u, 0x0B97u, 0x1C59u, 0x0448u, 0x1386u,
  0x0B16u, 0x1CD8u, 0x04C9u, 0x1307u, 0x14A8u, 0x0366u, 0x1B77u, 0x0CB9u,
  0x0A14u, 0x1DDAu, 0x05CBu, 0x1205u, 0x15AAu, 0x0264u, 0x1A75u, 0x0DBBu,
  0x152Bu, 0x02E5u, 0x1AF4u, 0x0D3Au, 0x0A95u, 0x1D5Bu, 0x054Au, 0x1284u,
};

static const uint16_t crcTable8408[256u] = {
  0x0000u, 0x1189u, 0x2312u, 0x329Bu, 0x4624u, 0x57ADu, 0x6536u, 0x74BFu,
  0x8C48u, 0x9DC1u, 0xAF5Au, 0xBED3u, 0xCA6Cu, 0xDBE5u, 0xE97Eu, 0xF8F7u,
  0x1081u, 0x0108u, 0x3393u, 0x221Au, 0x56A5u, 0x472Cu, 0x75B7u, 0x643Eu,
  0x9CC9u, 0x8D40u, 0xBFDBu, 0xAE52u, 0xDAEDu, 0xCB64u, 0xF9FFu, 0xE876u,
  0x2102u, 0x308Bu, 0x0210u, 0x1399u, 0x6726u, 0x76AFu, 0x4434u, 0x55BDu,
  0xAD4Au, 0xBCC3u, 0x8E58u, 0x9FD1u, 0xEB6Eu, 0xFAE7u, 0xC87Cu, 0xD9F5u,
  0x3183u, 0x200Au, 0x1291u, 0x0318u, 0x77A7u, 0x662Eu, 0x54B5u, 0x453Cu,
  0xBDCBu, 0xAC42u, 0x9ED9u, 0x8F50u, 0xFBEFu, 0xEA66u, 0xD8FDu, 0xC974u,
  0x4204u, 0x538Du, 0x6116u, 0x709Fu, 0x0420u, 0x15A9u, 0x2732u, 0x36BBu,
  0xCE4Cu, 0xDFC5u, 0xED5Eu, 0xFCD7u, 0x8868u, 0x99E1u, 0xAB7Au, 0xBAF3u,
  0x5285u, 0x430Cu, 0x7197u, 0x601Eu, 0x14A1u, 0x0528u, 0x37B3u, 0x263Au,
  0xDECDu, 0xCF44u, 0xFDDFu, 0xEC56u, 0x98E9u, 0x8960u, 0xBBFBu, 0xAA72u,
  0x6306u, 0x728Fu, 0x4014u, 0x519Du, 0x2522u, 0x34ABu, 0x0630u, 0x17B9u,
  0xEF4Eu, 0xFEC7u, 0xCC5Cu, 0xDDD5u, 0xA96Au, 0xB8E3u, 0x8A78u, 0x9BF1u,
  0x7387u, 0x620Eu, 0x5095u, 0x411Cu, 0x35A3u, 0x242Au, 0x16B1u, 0x0738u,
  0xFFCFu, 0xEE46u, 0xDCDDu, 0xCD54u, 0xB9EBu, 0xA862u, 0x9AF9u, 0x8B70u,
  0x8408u, 0x9581u, 0xA71Au, 0xB693u, 0xC22Cu, 0xD3A5u, 0xE13Eu, 0xF0B7u,
  0x0840u, 0x19C9u, 0x2B52u, 0x3ADBu, 0x4E64u, 0x5FEDu, 0x6D76u, 0x7CFFu,
  0x9489u, 0x8500u, 0xB79Bu, 0xA612u, 0xD2ADu, 0xC324u, 0xF1BFu, 0xE036u,
  0x18C1u, 0x0948u, 0x3BD3u, 0x2A5Au, 0x5EE5u, 0x4F6Cu, 0x7DF7u, 0x6C7Eu,
  0xA50Au, 0xB483u, 0x8618u, 0x9791u, 0xE32Eu, 0xF2A7u, 0xC03Cu, 0xD1B5u,
  0x2942u, 0x38CBu, 0x0A50u, 0x1BD9u, 0x6F66u, 0x7EEFu, 0x4C74u, 0x5DFDu,
  0xB58Bu, 0xA402u, 0x9699u, 0x8710u, 0xF3AFu, 0xE226u, 0xD0BDu, 0xC134u,
  0x39C3u, 0x284Au, 0x1AD1u, 0x0B58u, 0x7FE7u, 0x6E6Eu, 0x5CF5u, 0x4D7Cu,
  0xC60Cu, 0xD785u, 0xE51Eu, 0xF497u, 0x8028u, 0x91A1u, 0xA33Au, 0xB2B3u,
  0x4A44u, 0x5BCDu, 0x6956u, 0x78DFu, 0x0C60u, 0x1DE9u, 0x2F72u, 0x3EFBu,
  0xD68Du, 0xC704u, 0xF59Fu, 0xE416u, 0x90A9u, 0x8120u, 0xB3BBu, 0xA232u,
  0x5AC5u, 0x4B4Cu, 0x79D7u, 0x685Eu, 0x1CE1u, 0x0D68u, 0x3FF3u, 0x2E7Au,
  0xE70Eu, 0xF687u, 0xC41Cu, 0xD595u, 0xA12Au, 0xB0A3u, 0x8238u, 0x93B1u,
  0x6B46u, 0x7ACFu, 0x4854u, 0x59DDu, 0x2D62u, 0x3CEBu, 0x0E70u, 0x1FF9u,
  0xF78Fu, 0xE606u, 0xD49Du, 0xC514u, 0xB1ABu, 0xA022u, 0x92B9u, 0x8330u,
  0x7BC7u, 0x6A4Eu, 0x58D5u, 0x495Cu, 0x3DE3u, 0x2C6Au, 0x1EF1u, 0x0F78u,
};

static uint8_t reverse(uint8_t n) {
   static uint8_t lookup[16] = {
            0x0, 0x8, 0x4, 0xc, 0x2, 0xa, 0x6, 0xe,
            0x1, 0x9, 0x5, 0xd, 0x3, 0xb, 0x7, 0xf, };
   uint8_t result;
   result = lookup[n & 0xF] << 4 | lookup[n>>4];
   return result;
}

static uint16_t reverse16(uint16_t n) {
   return reverse(n & 0xFF) << 8 | reverse(n >> 8);
}

uint16_t Calculate(const uint8_t *message, int nBytes, uint16_t wOldCRC) {
    uint8_t data;
    uint16_t remainder = wOldCRC;
    for (int byte = 0; byte < nBytes; ++byte) {
        data = message[byte] ^ remainder;
        remainder = crcTable8408[data] ^ (remainder >> 8);
    }
    return remainder;
}

uint16_t CalculateInv(const uint8_t *message, int nBytes, uint16_t wOldCRC) {
    uint8_t data;
    uint16_t remainder = wOldCRC; //already reversed in function call
    for (int byte = nBytes; byte > 0; --byte) {
        data = reverse(message[byte-1]) ^ remainder;
        remainder = crcTable1021[data] ^ (remainder << 8);
    }
    return reverse16(remainder);
}

int main(void) {
   uint16_t expected = 0x4167;
   uint8_t pattern[] = "Hello World!";

   uint16_t result = Calculate(pattern, 12, 0x6363);
   printf("CRC option 1: 0x%04x, expected 0x%04x\n", result, expected);

   result = CalculateInv(pattern, 12, 0xC6C6);
   printf("CRC option 2: 0x%04X, expected 0x%04X\n", result, expected);

   return EXIT_SUCCESS;
}

Output:

CRC option 1: 0x4167, expected 0x4167
CRC option 2: 0x62FD, expected 0x4167

Edit: I created the tables by slightly adapting the code from the accepted answer from How to configure calculation of CRC table as follows:

uint16_t  crcTable[256];
void Init(uint16_t polynomial) {
    uint16_t  remainder;
    for (int dividend = 0; dividend < 256; ++dividend) {
        remainder = dividend;
        for (uint8_t bit = 8; bit > 0; --bit) {
            if (remainder & 1)
                remainder = (remainder >> 1) ^ polynomial;
            else
                remainder = (remainder >> 1);
        }
        crcTable[dividend] = remainder;
    }

    printf("static const uint_t crcTable[256u] = {");
    for (int i = 0; i<32; ++i) {
       printf("\n  ");
       for (int j=0; j<8; ++j) {
          printf("0x%04Xu, ",crcTable[i*8+j]);
       }
    }
    printf("\n};\n");
}

Simplify your test cases for start. Try checking the result for a single zero (0x00), then for a single byte with a simple pattern (0xAA), and then for an array containing two bytes, again something simple like (0xAA 0x00). The answer you linked mentions different ways of shifting and calculating the polynomial depending on whether the input data is reversed or not, so probably the mistake is in a missing shift, or in the way you calculated these crc tables. — Groo

rcgldr rcgldr · Accepted Answer · 2018-12-17T13:45:51

For a reflected CRC16, only the bits of each byte of a message are reversed, the message itself is not reversed. The other issue is that crcTable1021 needs to be based on a left shifting algorithm, or it can be a copy of crcTable8408 with the index and values reflected. (Comment - the 8408 CRC is a reflected CRC, while the 1021 is normally a non-reflected CRC, but in this case the input and output is being reflected to match the 8408 CRC). Example code that appears to be working:

static uint16_t crcTable8408[256u];   // could use table from question
static uint16_t crcTable1021[256u];   // could use table from automationwiki

// ... no changes ... //

uint16_t CalculateInv(const uint8_t *message, int nBytes, uint16_t wOldCRC) {
    uint8_t data;
    uint16_t remainder = wOldCRC; //already reversed in function call
    for (int byte = 0; byte < nBytes; ++byte) {             // fix
        data = reverse(message[byte]) ^ (remainder >> 8);   // fix
        remainder = crcTable1021[data]  ^ (remainder << 8); // fix
    }
    return reverse16(remainder);
}

void InitTables(void) {          // generate tables
    uint16_t  polynomial = 0x8408;
    uint16_t  remainder;
    for (int dividend = 0; dividend < 256; ++dividend) {
        remainder = dividend;
        for (uint8_t bit = 8; bit > 0; --bit) {
            if (remainder & 1)
                remainder = (remainder >> 1) ^ polynomial;
            else
                remainder = (remainder >> 1);
        }
        crcTable8408[dividend] = remainder;
        crcTable1021[reverse(dividend)] = reverse16(remainder);
    }
}

int main(void) {
   uint16_t expected = 0x4167;
   uint8_t pattern[] = "Hello World!";

   InitTables();     // generate tables (or use constant tables)

   uint16_t result = Calculate(pattern, 12, 0x6363);
   printf("CRC option 1: 0x%04X, expected 0x%04x\n", result, expected);

   result = CalculateInv(pattern, 12, 0xC6C6);
   printf("CRC option 2: 0x%04X, expected 0x%04X\n", result, expected);

   return 0;
}

Computing CRC16 with reflected / bit reversed input in C

2 Answers