时间戳

首页 > 解决方案 > CRC 查表优化是如何工作的？

crc - CRC 查表优化是如何工作的？

问题描述

我试图通过以下方式了解 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 进行 rshift？为什么这个技巧有效？它的依据是什么？

谢谢。

PS：是的，我读了这个帖子：如何计算 CRC32 校验和？（这不是骗子，因为它描述了基本方法）

标签： crccrc32

解决方案

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

左移 CRC 类似于在二进制中进行长手除法，使用 CRC 多项式作为除数，数据作为长被除数，只是使用 XOR 代替减法，最后的余数是 CRC。事实证明，一次异或 8 个数据（除数）位不会影响结果，因为每个商位仅基于 CRC 多项式的最高有效位和工作除数的当前最高有效位（数据)，它允许优化使用表查找。

推荐阅读