Aginor Aginor - 3 months ago 21
C Question

CRC4 Implementation in C

I have modified the implementation found here, to build a table generating function for a CRC4 as follows:

#define bufferSize 16
crc crcTable[bufferSize];
#define POLYNOMIAL 0x13

void Init()
{
crc remainder;

for(int dividend = 0; dividend < bufferSize; ++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("%hu\n", remainder);
}
}


And then calculate the CRC like this:

uint8_t calc_crc4(uint8_t start_crc, uint8_t byte)
{
byte ^= start_crc;
start_crc = crcTable[byte] ^ (start_crc >> 8);

return start_crc;
}


With a generated crcTable of:

/*
* Table based on Polynomial 0x13
*/
uint8_t crcTable[tableSize] = {
0x00, 0x0E, 0x1C, 0x12,
0x1F, 0x11, 0x03, 0x0D,
0x19, 0x17, 0x05, 0x0B,
0x06, 0x08, 0x1A, 0x14
};


The issue is that when I run it against an ERF file, none of my generated CRC values are equal to the ones attached to the end of an ERF frame. When I print values, it looks like the call to
crcTable[byte]
in the
calc_crc4
function is almost always returning the value 0x00, but I don't grasp the concept well enough to know if this is the correct value or not. The only thing I can think of is that it's not finding anything at the index location of byte, so it returns 0x00. I was under the assumption that there can only be 16 values of a CRC4 though, so there would have to be something in that location.

Answer

You don't have the full definition of the desired CRC, and your attempt at extrapolating the implementation to four bits has many errors.

First off, you need to know more than the polynomial. You need to know if the CRC is reflected, if the output is also reflected, what the initial register value is, and whether the output is exclusive-or'ed with some value or not.

Second, if you are processing a byte at a time, the table needs to have 256 entries, regardless of the length of the CRC. Furthermore, each entry must be the length of the CRC, in this case four bits, where you have entries with five. Also you need to put the CRC at the proper end of the byte for the initial exclusive-or before the table lookup, or shift the table. As already noted, an eight-bit value shifted down by eight bits is zero, so exclusive-or'ing with that does nothing.

A table-driven implementation of a four-bit CRC would something like one of these, depending on reflection. Both of these happen to have an initial register value of zero and no final exclusive-or.

static unsigned char const table_byte[256] = {
    0x90, 0xa0, 0xf0, 0xc0, 0x50, 0x60, 0x30, 0x00, 0x20, 0x10, 0x40, 0x70, 0xe0,
    0xd0, 0x80, 0xb0, 0xc0, 0xf0, 0xa0, 0x90, 0x00, 0x30, 0x60, 0x50, 0x70, 0x40,
    0x10, 0x20, 0xb0, 0x80, 0xd0, 0xe0, 0x30, 0x00, 0x50, 0x60, 0xf0, 0xc0, 0x90,
    0xa0, 0x80, 0xb0, 0xe0, 0xd0, 0x40, 0x70, 0x20, 0x10, 0x60, 0x50, 0x00, 0x30,
    0xa0, 0x90, 0xc0, 0xf0, 0xd0, 0xe0, 0xb0, 0x80, 0x10, 0x20, 0x70, 0x40, 0xe0,
    0xd0, 0x80, 0xb0, 0x20, 0x10, 0x40, 0x70, 0x50, 0x60, 0x30, 0x00, 0x90, 0xa0,
    0xf0, 0xc0, 0xb0, 0x80, 0xd0, 0xe0, 0x70, 0x40, 0x10, 0x20, 0x00, 0x30, 0x60,
    0x50, 0xc0, 0xf0, 0xa0, 0x90, 0x40, 0x70, 0x20, 0x10, 0x80, 0xb0, 0xe0, 0xd0,
    0xf0, 0xc0, 0x90, 0xa0, 0x30, 0x00, 0x50, 0x60, 0x10, 0x20, 0x70, 0x40, 0xd0,
    0xe0, 0xb0, 0x80, 0xa0, 0x90, 0xc0, 0xf0, 0x60, 0x50, 0x00, 0x30, 0x70, 0x40,
    0x10, 0x20, 0xb0, 0x80, 0xd0, 0xe0, 0xc0, 0xf0, 0xa0, 0x90, 0x00, 0x30, 0x60,
    0x50, 0x20, 0x10, 0x40, 0x70, 0xe0, 0xd0, 0x80, 0xb0, 0x90, 0xa0, 0xf0, 0xc0,
    0x50, 0x60, 0x30, 0x00, 0xd0, 0xe0, 0xb0, 0x80, 0x10, 0x20, 0x70, 0x40, 0x60,
    0x50, 0x00, 0x30, 0xa0, 0x90, 0xc0, 0xf0, 0x80, 0xb0, 0xe0, 0xd0, 0x40, 0x70,
    0x20, 0x10, 0x30, 0x00, 0x50, 0x60, 0xf0, 0xc0, 0x90, 0xa0, 0x00, 0x30, 0x60,
    0x50, 0xc0, 0xf0, 0xa0, 0x90, 0xb0, 0x80, 0xd0, 0xe0, 0x70, 0x40, 0x10, 0x20,
    0x50, 0x60, 0x30, 0x00, 0x90, 0xa0, 0xf0, 0xc0, 0xe0, 0xd0, 0x80, 0xb0, 0x20,
    0x10, 0x40, 0x70, 0xa0, 0x90, 0xc0, 0xf0, 0x60, 0x50, 0x00, 0x30, 0x10, 0x20,
    0x70, 0x40, 0xd0, 0xe0, 0xb0, 0x80, 0xf0, 0xc0, 0x90, 0xa0, 0x30, 0x00, 0x50,
    0x60, 0x40, 0x70, 0x20, 0x10, 0x80, 0xb0, 0xe0, 0xd0};

unsigned crc4interlaken(unsigned crc, void const *data, size_t len) {
    if (data == NULL)
        return 0;
    crc &= 0xf;
    crc <<= 4;
    while (len--)
        crc = table_byte[crc ^ *(unsigned char const *)data++];
    crc >>= 4;
    return crc;
}

or

static unsigned char const table_byte[256] = {
    0x0, 0x7, 0xe, 0x9, 0x5, 0x2, 0xb, 0xc, 0xa, 0xd, 0x4, 0x3, 0xf, 0x8, 0x1, 0x6,
    0xd, 0xa, 0x3, 0x4, 0x8, 0xf, 0x6, 0x1, 0x7, 0x0, 0x9, 0xe, 0x2, 0x5, 0xc, 0xb,
    0x3, 0x4, 0xd, 0xa, 0x6, 0x1, 0x8, 0xf, 0x9, 0xe, 0x7, 0x0, 0xc, 0xb, 0x2, 0x5,
    0xe, 0x9, 0x0, 0x7, 0xb, 0xc, 0x5, 0x2, 0x4, 0x3, 0xa, 0xd, 0x1, 0x6, 0xf, 0x8,
    0x6, 0x1, 0x8, 0xf, 0x3, 0x4, 0xd, 0xa, 0xc, 0xb, 0x2, 0x5, 0x9, 0xe, 0x7, 0x0,
    0xb, 0xc, 0x5, 0x2, 0xe, 0x9, 0x0, 0x7, 0x1, 0x6, 0xf, 0x8, 0x4, 0x3, 0xa, 0xd,
    0x5, 0x2, 0xb, 0xc, 0x0, 0x7, 0xe, 0x9, 0xf, 0x8, 0x1, 0x6, 0xa, 0xd, 0x4, 0x3,
    0x8, 0xf, 0x6, 0x1, 0xd, 0xa, 0x3, 0x4, 0x2, 0x5, 0xc, 0xb, 0x7, 0x0, 0x9, 0xe,
    0xc, 0xb, 0x2, 0x5, 0x9, 0xe, 0x7, 0x0, 0x6, 0x1, 0x8, 0xf, 0x3, 0x4, 0xd, 0xa,
    0x1, 0x6, 0xf, 0x8, 0x4, 0x3, 0xa, 0xd, 0xb, 0xc, 0x5, 0x2, 0xe, 0x9, 0x0, 0x7,
    0xf, 0x8, 0x1, 0x6, 0xa, 0xd, 0x4, 0x3, 0x5, 0x2, 0xb, 0xc, 0x0, 0x7, 0xe, 0x9,
    0x2, 0x5, 0xc, 0xb, 0x7, 0x0, 0x9, 0xe, 0x8, 0xf, 0x6, 0x1, 0xd, 0xa, 0x3, 0x4,
    0xa, 0xd, 0x4, 0x3, 0xf, 0x8, 0x1, 0x6, 0x0, 0x7, 0xe, 0x9, 0x5, 0x2, 0xb, 0xc,
    0x7, 0x0, 0x9, 0xe, 0x2, 0x5, 0xc, 0xb, 0xd, 0xa, 0x3, 0x4, 0x8, 0xf, 0x6, 0x1,
    0x9, 0xe, 0x7, 0x0, 0xc, 0xb, 0x2, 0x5, 0x3, 0x4, 0xd, 0xa, 0x6, 0x1, 0x8, 0xf,
    0x4, 0x3, 0xa, 0xd, 0x1, 0x6, 0xf, 0x8, 0xe, 0x9, 0x0, 0x7, 0xb, 0xc, 0x5, 0x2};


unsigned crc4itu(unsigned crc, void const *data, size_t len) {
    if (data == NULL)
        return 0;
    crc &= 0xf;
    while (len--)
        crc = table_byte[crc ^ *(unsigned char const *)data++];
    return crc;
}