CRC8 algorithm clarifications

Question

I have stumbled upon this implementation of 8 bit CRC: https://stackoverflow.com/a/15171925/243827

Can someone shed some light on how that table was obtained ? I have uncommented the crc8_slow function and tried feeding it with

  byte crc;
  byte data[1] = {0x01};
  crc = crc8_slow(0, data, sizeof(data)/sizeof(byte));
  printf("0x%.2X", crc);

for POLY defined to 4d, d4, a6 or b2. I can't seem to reproduce the value from that table. Also, how do I need to modify that code for a non 0xff initial value of the shift register ?

EDIT1:

#define POLY              0xB2

byte crc;
byte data[1] = {0x80};
crc = crc8_slow(0, data, sizeof(data)/sizeof(byte));
printf("0x%.2X", crc);

byte crc8_slow(byte crc, byte *data, size_t len)
{
    byte *end;

    if (len == 0)
        return crc;

//    crc ^= 0xff;
    end = data + len;

    do {
        crc ^= *data++;
        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
    } while (data < end);

//    return crc ^ 0xff;
    return crc;
}

Yields 0x01 when ran. I am on an Atmega 8 bits should it matter.

The "EDIT1" code is not directly runnable, but when made runnable, it gives `0xB2`. I had to add a `typedef unsigned char byte;`. — Mark Adler, Jan 29 '17 at 17:21
@MarkAdler nope, switched everything to `unsigned char` - same result — kellogs, Jan 29 '17 at 17:32

Mark Adler · Answer 1 · 2017-01-29T17:25:15.460

The table is the crc8_slow() of the single bytes 0..255 without the initial and final exclusive-ors. That code already has POLY defined as 0xb2, which is the reflection of the given polynomial (0x4d bit reversed).

For a different CRC-8 definition with a zero initial register value and no final exclusive-or, just remove the two exclusive-ors from the code.

You can look at crcany to generate CRC code for any given specification.

rcgldr · Accepted Answer · 2017-01-30T01:30:17.053

Poly is 0x14D reversed, then shifted right 1 bit to get 0xB2. The crc is bit reflected, which uses right shifts instead of left shifts.

101001101      0x14d
101100101      0x14d bit reversed = 0x165
 10110010      0x14d bit reversed >> 1 = 0xB2

If you look at crc8_table[0x80], you'll see a 0xB2. Each row is 12 bytes long, and since index 0x80 is decimal 128, look at the 10th row starting with 0x1d, and look at byte 8 (first byte of that row is 120), to see the 0xB2.

I tested this code and it prints a 0xB2:

#include <stdio.h>
typedef unsigned char byte;
#define POLY              0xB2

// prototype
byte crc8_slow(byte crc, byte *data, size_t len);

int main(){
    byte crc;
    byte data[1] = {0x80};
    crc = crc8_slow(0, data, sizeof(data)/sizeof(byte));
    printf("0x%.2X", crc);
    return 0;
}

byte crc8_slow(byte crc, byte *data, size_t len)
{
    byte *end;
    if (len == 0)
        return crc;
//  crc ^= 0xff;
    end = data + len;
    do {
        crc ^= *data++;
        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
    } while (data < end);
//  return crc ^ 0xff;
    return crc;
}

ok, it porbably has to do with my 8 bit architecture. I'll see some more into it. Thank you! — kellogs, Jan 29 '17 at 17:39

CRC8 algorithm clarifications

2 Answers2