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.

What exactly do you expect `start_crc >> 8` to accomplish for `uint8_t start_crc`? — EOF, Aug 22 '16 at 23:07
`crcTable[byte]` are you addressing memory outside of the array bounds here? byte needs to be 0 - 15. Also, where do you actually iterate over all the bytes in a message like the reference implementation does? — samgak, Aug 22 '16 at 23:08
`crc remainder; .... printf("%hu\n", remainder);` does not make much sense unless unposted `crc` is `unsigned short` or perhaps `unsigned`. Post definition of `crc`. — chux - Reinstate Monica, Aug 23 '16 at 01:26
_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._ So provide some of those examples, with the data and the expected CRC values. Or provide a reference with the full definition of the CRC. Just the polynomial is not sufficient. There are two different 4-bit CRC definitions [here](http://reveng.sourceforge.net/crc-catalogue/1-15.htm#crc.cat-bits.4), both using that polynomial. The one you want could be yet another definition. — Mark Adler, Aug 23 '16 at 02:02

Mark Adler · Accepted Answer · 2020-06-07T19:24:04.630

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"

Is the `size_t len` argument the length of `data` in bytes? Thank you, by the way — Aginor, Aug 23 '16 at 12:41
I don't understand the CRC-4/INTERLAKEN table. Table[0] = 0x90, rather than 0x00. Consider initial CRC = 0x0f, shifted left 4 bits for 0xf0, 1 byte of data = 0xf0, then crc^data[0] = 0, table[0] = 0x90, function returns 0x09, when it seems it should be returning 0x0f (xorout 0x0f on 0x00). — rcgldr, Jun 06 '20 at 20:11
@rcgldr You will note that there is no final exclusive-or in the function. The exclusive-or constant was folded into the table to avoid that extra instruction. — Mark Adler, Jun 06 '20 at 23:22
@MarkAdler - Visual Studio has a precedent issue with post increment. To eliminate a compile error, it requires `*((unsigned char const *)data)++` . This may be due to VS C compiler being C89 (not C99 or later). — rcgldr, Jun 07 '20 at 00:18
@rcgldr I have updated the answer with the conventions for the CRC routines. — Mark Adler, Jun 07 '20 at 04:33
@rcgldr Interestingly, Visual Studio is correct about the precedence for C89, C99, and later. No other compiler has ever complained about that, but I will fix it. — Mark Adler, Jun 07 '20 at 04:34
@MarkAdler - reposting a prior comment that missed a major edit. I saw there was no xorout in the interlaken function, and realized the table values ^= 0xf0, and table indexes effectively remove it (index ^= 0xf0). I got hung on on not the initial crc parameter, not making connection that the initial value 0xf is the same a the xorout value, and is taken care of by the indexing, so the initial crc parameter should be 0x0. — rcgldr, Jun 07 '20 at 06:50
@MarkAdler - There is an endian inconsistency between the Interlaken and ITU CRC's. Interlaken treats bytes as if they are big endian (with respect to nibbles), while ITU treats bytes as if they are little endian. I've seen this with other examples for Interlaken and ITU CRC. In the case of ITU G.704, the crc bits are split up into 1 bit every other byte, so I don't know if it's ever actually used on an array of nibbles other than academic purposes. — rcgldr, Jun 07 '20 at 06:55

CRC4 Implementation in C

1 Answers1

Linked