How does CRC table lookup optimization work?

Question

I'm trying to understand CRC table lookup optimization by going through: http://www.sunshine2k.de/articles/coding/crc/understanding_crc.html#ch5, particularly:

public static ushort Compute_CRC16(byte[] bytes)
{
    ushort crc = 0;
    foreach (byte b in bytes)
    {
        /* XOR-in next input byte into MSB of crc, that's our new intermediate divident */
        byte pos = (byte)( (crc >> 8) ^ b); /* equal: ((crc ^ (b << 8)) >> 8) */
        /* Shift out the MSB used for division per lookuptable and XOR with the remainder */
        crc = (ushort)((crc << 8) ^ (ushort)(crctable16[pos]));
    }
    return crc;
}

I do understand the basic bit-by-bit approach and I do understand the lookup method, but I'm having a hard time to catch this line:

crc = (ushort)((crc << 8) ^ (ushort)(crctable16[pos])); why is the existing crc needs to be rshifted? Why does this trick work? What is it based on?

Thanks.

PS: yes, I read this thread: How is a CRC32 checksum calculated? (it's not a dupe, because it describes the basic method)

The painless guide linked in the answer you reference explains it very well. — Mark Adler

rcgldr rcgldr · Accepted Answer · 2018-09-07T21:49:11

This is an example of a left shifting CRC. A byte of data is XOR'ed with the high order byte of the CRC. To do a table lookup (index an array), the result needs to be right shifted, or the high order byte of the CRC can be right shifted first, then XOR'ed with a byte of data to produce the new intermediate high order byte of the CRC, then that has to be cycled 8 times to produce the result of cycling the CRC 8 time, or this can be done in advance for all 256 possible 8 bit values, to generate a table, and a table lookup can be used instead of cycling 8 times. After this cycling, the low order byte will need to be shifted left, so you end up with the code shown.

A left shifting CRC is similar to doing a long hand division in binary, using the CRC polynomial as the divisor, and the data as a long dividend, except that XOR is used instead of subtraction, and the final remainder is the CRC. It turns out that XOR'ing 8 data (dividend) bits at a time doesn't affect the result, since each quotient bit is based only on the most significant bit of CRC polynomial and the current most significant bit of the working dividend (data), which allows for the optimization of using a table lookup.

How does CRC table lookup optimization work?

1 Answers