Understanding and implementing CRC

http://www.sunshine2k.de/articles/coding/crc/understanding_crc.html#ch6

说明

CRC（循环冗余校验）是一种检测数据不一致性的校验算法，例如在数据传输过程中出现的位错误。由 CRC 计算得出的校验和附加到数据上，以帮助接收方检测此类错误。

CRC 基于除法。实际输入数据被解释为一个长的二进制位流（被除数），它被另一个固定的二进制数（除数）所除。这个除法的余数就是校验和。二进制数字（被除数和除数）不像普通整型值那样处理，而是作为二元多项式来处理，其中实际位用作系数。

例如输入数据 0x25 = 0010 0101 被视为 $0*x^7 + 0*x^6 + 1*x^5 + 0*x^4 + 0*x^3 + 1*x^2 + 0*x^1 + 1*x^0$ .

• 被除数是完整的输入数据（解释为二进制流）
• 除数，也称为生成多项式，由使用的 CRC 算法定义。CRC-n 使用具有 (n+1) 位的固定定义生成多项式
• CRC 校验和的值被定义为被除数 % 除数，对生成多项式的余数

举例

// 输出数据是 byte 0xC2 = b1100 0010
// 生成多项式，即除数为    b10001 1101(除数9位，因此是CRC-8,添加8个 0bits 到输入数据末尾)
// 将除数的前导“1”与被除数的第一个“1”对齐，逐步进行除法运算，但是对每个位使用XOR操作：

1100001000000000
100011101
---------
010011001
 100011101
 ---------
 000101111
    100011101 (*)
    ---------
    001100101
      100011101
      ---------
      010001001
       100011101
       ---------
       000001111 = 0x0F

• 在每一步中，除数的前导“1”始终与被除数的第一个“1”对齐。这意味着，在每一步中，除数不仅向右移动 1 位，有时还会移动几个步骤（例如像 (*) 行）。
• 算法会在除数将实际输入数据（不包括填充字节）的每个位都清零时停止。或者说最后的有效位全部位于填充字节(这里 n=8)，也即最终的余数在 n-bit 范围内。
• 每一步中只有余数是感兴趣的，因此实际除法结果（商）可以不关心。
• 最后只取 n-bit 的余数

CRC 验证

余数是 CRC 值，它与输入数据一起传输到接收器。常见的做法是，直接将 CRC 值附加到实际数据末尾。然后接收器在整个数据上（包括已附加了 CRC 值的输入）计算 CRC：如果 CRC 值为 0，则很可能在传输过程中没有发生位错误。

实现细节

通过手动模拟的过程，可以很容易地通过移位寄存器的方式逐步计算出最后的余数。

1. 初始化固定大小(n-bit)的移位寄存器为 0;
2. 逐位移动输入流。如果弹出的 MSB 是 1，则使用生成多项式对寄存器值进行异或操作;
3. 如果所有输入位都被处理，则 CRC 移位寄存器内容就是 CRC 值。

CRC-8 实现

生成多项式的最高位是 1，并且在除法过程中会将生成多项式的最高位 1 与被除数的下一个最高位 1 对齐，异或为 0，所以运算过程可以忽略生成多项式的最高位 1，例如 9 位的 b100011101 只需要使用 0x1D 进行运算。

• 注意，可以每个字节单独处理，处理完一个字节后的余数与下一个字节异或后继续处理
• 类似这样处理

// 按照手动除法的模拟
b1 0
   b2 0
      b3 0
      ......

#include <cstdint>
uint8_t Compute_CRC8_Simple(const unsigned char* bytes, size_t length)
{
    const uint8_t generator = 0x1D; //  b100011101 = 0x1D
    uint8_t crc = 0; /* first byte can be 'xored' in */

    for (size_t j = 0; j < length; j++)
    {
        crc ^= bytes[j]; /* XOR-in the next input byte */

        for (int i = 0; i < 8; i++)
        {
            if ((crc & 0x80) != 0)
                crc = (crc << 1) ^ generator;
            else
                crc <<= 1;
        }
    }

    return crc;
}

CRC-32 实现

生成多项式取 33-bit，这里使用 0x04C11DB7(省略最高位的 1)。

• 类似，可以逐个字节进行计算

#include <cstdint>
uint32_t Compute_CRC32_Simple(const unsigned char* bytes, size_t length){
    const uint32_t polynomial = 0x04C11DB7; /* divisor is 32bit */
    uint32_t crc = 0; /* CRC value is 32bit */

    for (size_t j = 0; j < length; j++){
        crc ^= (uint32_t)(bytes[j] << 24); /* move byte into MSB of 32bit CRC */

        for (int i = 0; i < 8; i++){
            if ((crc & 0x80000000) != 0) /* test for MSB = bit 31 */
                crc = (uint32_t)((crc << 1) ^ polynomial);
            else
                crc <<= 1;
        }
    }
    return crc;
}

附录

• http://www.sunshine2k.de/coding/javascript/crc/crc_js.html