CRC校验

CRC校验也叫循环冗余校验，相比校验和与奇偶校验的检错能力提升了很多，又因为他的硬件实现简单被广泛应用于各种数字通信和存储系统。我最近对CRC感兴趣也是因为使用Ymodem协议的时候需要CRC就看了一下，我也就用一个Ymodem使用的CRC校验函数开始这个文章。

#include <stdint.h>
uint16_t crc16_0x1021_msb_init0(const uint8_t *data, uint32_t len) {
  uint16_t crc = 0x0000;
  while (len--) {
    crc ^= (uint16_t)(*data++) << 8; // MSB
    for (int i = 0; i < 8; i++) {
      if (crc & 0x8000)
        crc = (crc << 1) ^ 0x1021;
      else
        crc <<= 1;
    }
  }
  return crc;
}

处理一个字节序列的的时候把依次把每一个字节最高位与CRC最高有效位对齐，不足部分补0然后异或，连续8次左移根据最高位0或1与多项式进行异或操作，最后得到的就是CRC校验值。

其实这个函数的名字我故意这样写已经包含了很多信息，CRC数值是16位，多项式是0x1021，优先处理最高有效位，crc初始值是全0，实际使用选择的时候这每一项都要经过验证权衡性能与开销。

CRC位数:

先说CRC自身位数的问题，CRC值自身的位数决定了CRC校验的能力，很显然位数越多检错能力越强，但是也要注意检错能力不仅仅取决于CRC位数，和多项式的选择有关系，广泛使用的最小就是CRC-8，然后就是各种字节整数倍比如CRC-16，CRC-32，这样有利于计算机的处理。

然后是CRC单次处理的位数，理论上CRC处理的是一个比特流，没有任何位数上的规定，只要单次从比特流中选取的位数不超过CRC位数就可以正常异或，然后进行对应次数左移并看最高位0/1情况与多项式异或。

上面的例子中单次循环内（while (len--) {……}）也是一个字节与CRC值的前8位（注意我说的前8位不是高8位，和后面要说的优先位顺序有关系）对齐处理，理论上来说CRC16也可以与连续的16比特异或，然后16次左移并根据最高位情况与多项式异或，但是很显然一个数据帧并不一定就是16比特的整数倍，但是一定是8比特（字节）的整数倍。

我看有的说是因为大小端问题导致字节顺序变化，刚开始也给我搞迷糊了，细想一下完全不是这么回事，比如说下面的数据帧如果从电脑上发送顺序就是0x12，0x34，0x56，0x78，0x9A，虽然说到了单片机上进行大小端转换确实改变了字节序，但是如果一个数据帧没有经过校验就进行大小端转换完全就没有意义，转换完发现错了不是浪费时间吗？

最重要的是大小端转换之后就算是一个字节一个字节的处理顺序也不对啊，所以CRC校验是针对通信本身数据流的，单次处理一个字节就是为了不出现最后剩余字节不够16/32位（当然这个代码也能写但是没有必要）。

typedef struct {
  uint16_t frame_header; // 帧头
  uint8_t data; // 数据
  uint16_t frame_tail; // 帧尾
} frame_t;
frame_t frame = {
  .frame_header = 0x1234,
  .data = 0x56,
  .frame_tail = 0x789A
};
// 大端模式
// 地址:    0x1000   0x1001   0x1002   0x1003  0x1004
//         ├─ frame_header ─┤├─ data ─┤├─ frame_tail ─┤
// 数据:     0x12     0x34     0x56     0x78    0x9A

// 小端模式
// 地址:    0x1000   0x1001   0x1002   0x1003  0x1004
//         ├─ frame_header ─┤├─ data ─┤├─ frame_tail ─┤
// 数据:     0x34     0x12     0x56     0x9A    0x78

优先有效位:

我们先来看一个硬件实现的CRC校验过程，看明白这个有助于理解在实际应用中CRC校验的各种形式，这个电路就相当于每次拿最高位与输入的一个比特进行异或，根据结果将CRC寄存器原始值左移并与多项式异或，直接左移不改变相当于与0异或，当t是0的时候就是所有的位全部直接左移。（图中的$$C_0$$可以换一种理解方式就是左侧还有一个永远是0的寄存器每次与t异或就是直接输入了，这样每一个右侧有$$ \oplus $$ 符号的就相当于多项式的1。）

一般情况下硬件的设计是比较固定的，但是通信的比特顺序是不一定的，比如串口是优先传递最低有效位，0x12，0b0001 0010，传递的顺序是0b0100 1000。有些时候使用硬件CRC并不会在传递完成后送入硬件CRC，而是传输时立即送入硬件CRC的，依旧拿0x1021：0b0001 0000 0010 0001来说。

// CRC16 0x1021: 0b0001 0000 0010 0001
//  理想顺序:     0b0001 0010
//  实际顺序:     0b0100 1000

// CRC16 0x8408: 0b1000 0100 0000 1000
//  实际顺序:                0b0100 1000

uint16_t crc16_lsb_1021_init0(const uint8_t *data, uint32_t len) {
  uint16_t crc = 0x0000;
  while (len--) {
    crc ^= (uint16_t)(*data++);
    for (int i = 0; i < 8; i++) {
      if (crc & 0x0001)
        crc = (crc >> 1) ^ 0x8408; // 0x1021的LSB多项式
      else
        crc >>= 1;
    }
  }
  return crc;
}

为了软件计算的结果硬件计算生成的CRC校验值一致，就可以把0x1021高低位对调，对于每一个字节进行低位对齐右移处理，然后在结束后把CRC数值重新反转就是一样的结果。当然对现在的CRC通常来说这个功能已经变成了一个可以配置的功能，可以手动选择MSB或者LSB以应对各种情况，而不需要手动处理。

多项式的选择：

虽然说CRC本身没有规定多项式具体是多少，但是及实际用的时候多项式的选取直接影响检错的能力，下面是一些常见情况使用的CRC校验多项式。稍微仔细观察你就可以发现常数项都是1，如果你对于计算机比较敏感很容易发现实际上这一位就相当于进行了奇偶校验。

生成多项式的选择是CRC算法实现中最重要的部分，在CRC位数相同的情况下，应尽量使多项式有最大的错误检测能力，同时保证总体的碰撞概率最小。在构建一个新的CRC多项式或者改进现有的CRC时，一个通用的数学原则是使用满足所有模运算不可分解多项式约束条件的多项式。

初始值选择：

最后你可能会看到有些CRC里面的初始值不是全0而是全1，这个其实非常容易理解，还是下面这个假设比特流前面X个字节全部是0，要知道与0进行异或不会改变CRC的初始值，进行左移也一直不会与多项式异或，也就是说如果比特流前面有很多0的时候实际上是没有检测效果的，学术一点叫做CRC对前导零不敏感。

// CRC16 0x1021: 0b0001 0000 0010 0001
// CRC_init:     0b0000 0000 0000 0000
// byte1:        0b0000 0000
// byte2:        0b0000 0000
// ……
// byteX:        0b0000 0000

为了能够正常校验数据要么将CRC初始值设定为全1，要么自己手动把数据流变成非0起始，很显然无端改变数据流并不是什么很好的做法，而改变CRC校验初始值不需要对原始数据流造成任何影响，只需要保持通信双方初始值一致即可，是更好的做法。

因为我更多关注于应用而不是原理，所以关于CRC的原理也就是为什么能够检错尤其是多项式的选取对检错能力的影响，我这个文章里并没有详细说明。只是说了最低位就相当于奇偶校验了，因为这个容易看出来，但是整个多项式的选取对于检错能力的影响想要严格的证明也不是一篇博客能够说明的，也需要有一定的离散数学的功底。如果你对背后的数学原理有兴趣可以自己去学习，对于计算机的学习一定会有帮助，但是也不必过于深究。