CRC-16 Nibble Lookup Table

I already wrote about using smaller-than-256-byte lookup table. What we ended up with was a smaller 32 byte lookup setup for CRC-8. However, if you're sending a lot of data, CRC-8 won't do. Can one make a nibble lookup table for CRC-16 too?

Of course one can. It's actually exactly the same - just expand all variables to 16 bytes. In order to calculate lookup table, one can just use this code:

for (uint8_t i = 0; i < 16; i++) {
    uint16_t crc = (uint16_t)i;
    for (uint8_t j = 1; j <= 16; j++) {
        if (crc & 0x8000) {
            crc = (uint16_t)((crc << 1) ^ poly);
        } else {
            crc <<= 1;
        }
    }
    Crc16LutL[i] = crc;
}
for (uint8_t i = 0; i < 16; i++) {
    uint16_t crc = (uint16_t)i << 4;
    for (uint8_t j = 1; j <= 16; j++) {
        if (crc & 0x8000) {
            crc = (uint16_t)((crc << 1) ^ poly);
        } else {
            crc <<= 1;
        }
    }
    Crc16LutH[i] = crc;
}

I will be using polynomial 0xA2EB (0xD175 in Koopman's notation) since that one seems to be the best at this time. Mind you, in year from now, one might find another polynomial with better characteristics yet.

// Polynomial 0xA2EB
const uint16_t Crc16LutL[] = { 0x0000, 0xA2EB, 0xE73D, 0x45D6, 0x6C91, 0xCE7A, 0x8BAC, 0x2947, 0xD922, 0x7BC9, 0x3E1F, 0x9CF4, 0xB5B3, 0x1758, 0x528E, 0xF065, };
const uint16_t Crc16LutH[] = { 0x0000, 0x10AF, 0x215E, 0x31F1, 0x42BC, 0x5213, 0x63E2, 0x734D, 0x8578, 0x95D7, 0xA426, 0xB489, 0xC7C4, 0xD76B, 0xE69A, 0xF635, };

uint16_t crc16(uint8_t* data, uint8_t length) {
    uint16_t crc = 0;
    while (length--) {
        uint8_t combo = (crc >> 8) ^ *data++;
        crc = (crc << 8) ^ Crc16LutL[combo & 0x0F] ^ Crc16LutH[combo >> 4];
    }
    return crc;
}

These extra 64 bytes (two lookup tables, 32 bytes each) allows us to use shift-less CRC code. And yes, there will one shift operation in there but XC8 compiler should actually optimize that one away in most cases.

Since we do have a bit more complicated data handling, implemented on a microcontroller using XC8 compiler, this code needs 141 words of program memory (was 80 for CRC-8) and uses 16 bytes of RAM (was 4 for CRC-8). All in all, pretty handleable by almost any PIC microcontroller.

Interestingly, here you cannot use trick of removing const in order to move usage more toward memory. While RAM usage for such case indeed increases to 76 bytes, program memory usage doesn't go down at all.

As always, the example code is available for download.