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, Sep 08 '18 at 17:08

rcgldr · Answer 1 · 2018-09-07T23:53:09.810

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.

Wagner Lipnharski · Answer 2 · 2022-12-05T17:45:09.070

Okay, found the mechanics, but on CRCCALC.COM, the tables are used differently in CRC16-XMODEM (poly 1021) and CRC16/ARC (poly 8005). CRC=HHLL, Data=NEW

On CRC16-XMODEM:
TT=Table(HH xor NEW), Shift CRC 8bits Left = LL00, result = LL00 xor TT.

On CRC16/ARC:
TT=Table(LL xor NEW), Shift CRC 8bits Right = 00HH, result = 00HH xor TT.

Examples:

CRC16-XMODEM, 0x01,0x07 = 0x43D6
0x01 = 0x1021
0x10 xor 0x07 = 0x17
Table(0x17)= 0x62D6
Shift CRC 8 bits LEFT, 0x1021 becomes 0x2100
Xor 0x2100 with 0x62D6 = 0x43D6, correct CRC for 0x01 0x07.

CRC16/ARC, 0x01, 0x07 = 0x5240
0x01 = 0xC0C1
0xC1 xor 0x07 = 0xC6
Table(0xC6) = 0x5280
Shift 0xC0C1 8 bits RIGHT, 0xC0C1 becomes 0x00C0
Xor 0x00C0 with 0x5280 = 0x5240, correct CRC for 0x01 0x07

I tested with several other values and quantity of data, it works always. It seems each table (on CRCCALC.COM) is used in a particular way. I didn't tested the other CRCs on that webpage.

How does CRC table lookup optimization work?

2 Answers2