CRC4 Implementation in C

Question

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 1

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 be something like one of these, depending on reflection.

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_byte(unsigned crc, void const *mem, size_t len) {
    unsigned char const *data = mem;
    if (data == NULL)
        return 0;
    crc &= 0xf;
    crc <<= 4;
    while (len--)
        crc = table_byte[crc ^ *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 crc4g_704_byte(unsigned crc, void const *mem, size_t len) {
    unsigned char const *data = mem;
    if (data == NULL)
        return 0;
    crc &= 0xf;
    while (len--)
        crc = table_byte[crc ^ *data++];
    return crc;
}

This code and tables were generated by my crcany code. The functions advance a CRC using the len bytes at data. The initial CRC (i.e. a CRC of zero bytes) is returned when called with data equal to NULL. The CRCs are in the least-significant bits of the return value.

Those two CRCs are defined in Greg Cook's catalog, where the two 4-bit CRC definitions are:

width=4 poly=0x3 init=0xf refin=false refout=false xorout=0xf check=0xb residue=0x2 name="CRC-4/INTERLAKEN"
width=4 poly=0x3 init=0x0 refin=true refout=true xorout=0x0 check=0x7 residue=0x0 name="CRC-4/G-704"