[MM32软件] CRC算法查表法推导及C语言实现

以半字节为例，将数据 g = 0101 0011 1010 0001 按每 4 位组成 1 个 block，这样 g 就被分成 6 个 block。

[color=var(--theme-color)]

下面的表展示了 4 次迭代计算步骤，灰色背景的位是保存在寄存器中的。

[color=var(--theme-color)]

经 4 次迭代，B1 被移出寄存器。被移出的部分不是我们关心的，我们关心的是这 4 次迭代对 B2 和 B3 产生了什么影响。注意表中红色的部分，先作如下定义：

B23 = 00111010
b1 = 00000000
b2 = 01010100
b3 = 10101010
b4 = 11010101
b’ = b1 xor b2 xor b3 xor b4

4 次迭代对 B2 和 B3 来说，实际上就是让它们与 b1,b2,b3,b4 做了 xor 计算，既：

B23 xor b1 xor b2 xor b3 xor b4

可以证明 xor 运算满足交换律和结合律，于是：

B23 xor b1 xor b2 xor b3 xor b4 = B23 xor (b1 xor b2 xor b3 xor b4) = B23 xor b’

b1 是由 B1 的第 1 位决定的，b2 是由 B1 迭代 1 次后的第 2 位决定（既是由 B1 的第 1 和第 2 位决定），同理,b3 和 b4 都是由 B1 决定。通过 B1 就可以计算出 b’。另外，B1 由 4 位组成，其一共 2^4 有种可能值。于是我们就可以想到一种更快捷的算法，事先将 b’所有可能的值，16 个值可以看成一个表；这样就可以不必进行那 4 次迭代，而是用 B1 查表得到 b’值，将 B1 移出，B3 移入，与 b’计算，然后是下一次迭代。

[color=var(--theme-color)]

可看到每次迭代，寄存器中的数据以 4 位为单位移入和移出，关键是通过寄存器前 4 位查表获得，这样的算法可以大大提高运算速度。

上面的方法是半字节查表法，另外还有单字节和双字节查表法，原理都是一样的——事先计算出 2^8 或 2^16 个 b’的可能值，迭代中使用寄存器前 8 位或 16 位查表获得 b’。

下表是某款芯片的 CRC 查找表，对应的多项式为：

Polynomial = x^8 + x^5 + x^3 + x^2 + x^1 + 1

[color=var(--theme-color)]

先看一下这个表是怎么来的，以 0x82 为例，通过上表，可以找到对应的 CRC 值为十进制 147，十六进制为 0x93。

先来通过 CRC 在线计算工具来验证。

[color=var(--theme-color)]

由于该款芯片先传输 LSB，所以上述的计算勾选了输入数据反转和输出数据反转。

输入数据反转，即将 0x82 反转为 0x41，在与多项式进行异或计算（当前多项式不需要进行反转了）；输出数据反转，即将上述计算结果再次反转，即可得到最终结果。

[color=var(--theme-color)]

当然，也可以手动计算一下 0x82 的 CRC 值，由于该款芯片是先传输 LSB，数据右移进入寄存器，所以将多项式的值 0x2F 反转，与寄存器中的数据由 LSB 到 HSB 逐位取异或运算，最后得到结果，即是 CRC 值。

[color=var(--theme-color)]

即 0x82 对应的 CRC 值为 0x93。

总之，不管哪种计算方式，均是从LSB 到 MSB 逐位与多项式取异或运算（由芯片决定），最终可以得到正确的 CRC 值。

通过上述分析，可以得到 256 个数据，并形成上述表格。接下来，计算多个字节的数据时，就比较方便了。

例如，在计算 0x82 的过程中，下一个字节的数据（即高 8 位，上图为 0x00，也有可能是 0x01~0xFF 的任意值）也会相应的与 b1~b8 取异或，可以证明，b1~b8 的异或值为 0x93（红色框中的值）。即下一字节的数据与 0x93 异或的结果再与多项式逐位异或，即为下一字节的 CRC 值。

比方说，要计算 0x82, 0x80 的 CRC 值，通过 0x82 查表得到对应 CRC 值为 0x93，计算 0x82 的过程中会影响下一字节，影响的结果为 0x93 与下一字节 0x80 取异或，得到 0x13，再查表可得到 0x13 对应的 CRC 值为 0x4A。

C 语言实现 CRC 查表法步骤如下：

（1）设置 CRC 寄存器，并给其赋值为“余数初始值”。

（2）将数据的一个 8-bit 字符与 CRC 寄存器进行异或，并把结果存入 CRC 寄存器。

（3）将 CRC 寄存器中的值查表，查表结果再次存入 CRC 寄存器。

（4）重复第 2 至第 3 步直到所有数据全部处理完成。

（5）最终 CRC 寄存器的内容即为 CRC 值。

下面是 CRC 查表法示例性的 C 代码：

unsigned char crc_calculation(unsigned char *data, unsigned char num)

{

  unsigned char crc_res = 0x00;

  for(; num > 0; num--)

  {

    crc_res = crc_res ^ (*data++);

    crc_res = crc_lookup_table[crc_res];

  }

  return crc_res;

}

通过这种方法可以极大的加快 CRC 计算过程，节省处理器的运算时间。