CRC表查找优化如何工作？

Question

我试图通过以下方式了解CRC表查找优化：http://www.sunshine2k.de/articles/coding/crc/understanding_crc.html#ch5，特别是：

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;
}

我确实理解基本的逐位方法，并且我理解查找方法，但是我很难抓住这一行：

crc = (ushort)((crc << 8) ^ (ushort)(crctable16[pos])); 为什么现有的crc需要被摧毁？为什么这个技巧有效？它的基础是什么？

谢谢。

PS：是的，我读了这个帖子：How is a CRC32 checksum calculated?（它不是一个骗子，因为它描述了基本方法）

Answer 1

这是左移CRC的示例。一个字节的数据与CRC的高位字节进行异或。要进行表查找（索引数组），结果需要右移，或者CRC的高位字节可以先右移，然后与一个数据字节进行异或，以产生新的中间高位字节然后，必须循环8次以产生循环CRC 8时间的结果，或者这可以预先对所有256个可能的8位值进行，以生成表，并且可以使用表查找而不是骑自行车8次。在循环之后，低位字节需要向左移动，因此您最终得到的代码。

左移CRC类似于以二进制进行长手除法，使用CRC多项式作为除数，并且数据作为长除数，除了使用XOR而不是减法，并且最终余数是CRC。事实证明，一次XOR'ing 8个数据（被除数）位不会影响结果，因为每个商位仅基于CRC多项式的最高有效位和工作被除数的当前最高有效位（数据） ），允许使用表查找进行优化。