CRC-8 Nibble Lookup Table

A few weeks ago I left you with the following CRC-8 code for microcontrollers:

uint8_t crc8(uint8_t* data, uint8_t length) {
    uint8_t crc = 0;
    while (length--) {
        crc ^= *data++;
        for (uint8_t i = 0; i < 8; i++) {
            if (crc & 0x80) {
                crc = (uint8_t)(crc << 1) ^ 0x2F;
            } else {
                crc <<= 1;
            }
        }
    }
    return crc;
}

However, this code is a bit lacking when it comes to the performance. And yes, adding a lookup table would speed things up by a lot since it would allow use of precalculated values instead of shifting stuff around.

uint8_t crc8(uint8_t* data, uint8_t length) {
    uint8_t crc = 0;
    while (length--) {
        crc ^= *data++;
        crc = Crc8Lut[crc];
    }
    return crc;
}

However, 256 bytes such lookup table requires is too much when dealing with a microcontroller that often has only that amount available for all its functionality. Some, like my favorite small micro PIC12F1501) might have as little as 64 bytes of RAM.

What we need is a smaller lookup table.

Fortunately, this is actually quite possible if we calculate lookup table independently for the high and low nibble.

for (uint8_t i = 0; i < 16; i++) {
    uint8_t crc = (uint8_t)i;
    for (uint8_t j = 1; j <= 8; j++) {
        if (crc & 0x80) {
            crc = (uint8_t)((crc << 1) ^ poly);
        } else {
            crc <<= 1;
        }
    }
    Crc8LutL[i] = crc;
}
for (uint8_t i = 0; i < 16; i++) {
    uint8_t crc = (uint8_t)i << 4;
    for (uint8_t j = 1; j <= 8; j++) {
        if (crc & 0x80) {
            crc = (uint8_t)((crc << 1) ^ poly);
        } else {
            crc <<= 1;
        }
    }
    Crc8LutH[i] = crc;
}

This shrinks our lookup table to 32 bytes and allows us to use shift-less CRC code. And yes, there is one shift operation in there but XC8 compiler should actually optimize that one away in most cases.

// Polynomial 0x2F
const uint8_t Crc8LutL[] = { 0x00, 0x2F, 0x5E, 0x71, 0xBC, 0x93, 0xE2, 0xCD, 0x57, 0x78, 0x09, 0x26, 0xEB, 0xC4, 0xB5, 0x9A, };
const uint8_t Crc8LutH[] = { 0x00, 0xAE, 0x73, 0xDD, 0xE6, 0x48, 0x95, 0x3B, 0xE3, 0x4D, 0x90, 0x3E, 0x05, 0xAB, 0x76, 0xD8, };

uint8_t crc8(uint8_t* data, uint8_t length) {
    uint8_t crc = 0;
    while (length--) {
        crc ^= *data++;
        crc = Crc8LutL[crc & 0x0F] ^ Crc8LutH[crc >> 4];
    }
    return crc;
}

Implemented on a microcontroller using XC8 compiler, this code fits in 80 words of program memory and uses just 4 extra bytes of RAM (const means your table goes to program memory).

You might opt to go without const and in that case code needs 72 words of program memory and whooping 35 bytes of RAM. As I'm usually running out of RAM before I run out of program memory, I don't find that particular compromise
worth it.

And again, one could squeeze a few more bytes by implementing this in assembly, but not too many.

As always, the example code is available for download.

PS: For curious ones, a full CRC-8 lookup table implementation uses whooping 287 words of program memory but only 2 bytes of RAM.