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.

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.