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?

I read this thread: How is a CRC32 checksum calculated?, it describes the basic method, but not how the lookup optimization works.

Answer 1

This is an example of a left shifting CRC. A byte of data is XOR'ed with the high order byte of the CRC.

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.

Following the code in the question, for each byte of data, the higher order byte of the CRC is shifted right 8 bits and XOR'ed with the next byte of data to produce an 8 bit table index. The low order byte is shifted left 8 bits and XOR'ed with the indexed 16 bit table entry. The table consists of 256 16 bit values which represent all 256 cases of cycling the high order byte of a CRC 8 times for the 8 bits.