CRC循环冗余校验

CRC在嵌入式开发中用得非常频繁，但仔细想想，我们很少真正去写它。要么抄个查表法，要么调个现成函数，代码靠Ctrl+C/V，调通就再也不动。

可一旦被问起原理，却支支吾吾讲不明白。多项式为什么是那个数？初始值为什么是0xFF？查表法到底在查什么？

1. CRC

CRC（Cyclic Redundancy Check，循环冗余校验）是一种根据数据产生固定长度校验码的算法，主要用于检测数据传输或存储过程中的偶然错误。

优点：计算开销小，只需要异或和移位，速度快。纠错能力强。结果确定。
缺点：无法纠错。校验码位数限值，数据较长时必然会出现碰撞（校验码重复）。

CRC重要概念：模型

计算一个正确的CRC指，需要知道CRC的参数模型。一个完整的CRC参数模型包含以下信息¹：

NAME：参数模型名称；
WIDTH：宽度，即生成的CRC数据位宽，如CRC-8，生成的CRC为8位；
POLY：十六进制多项式，省略最高位1，如x^8 + x^2 + x + 1，二进制为1 0000 0111，省略最高位1，转换为十六进制为0x07；
- 多项式简写是为了人方便，补全是为了“机器”运算。
- CRC-32，x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1，二进制为0001 0000 0100 1100 0001 0001 1101 1011 0111，高位1省略，结果即为0x04C11DB7
INIT：CRC初始值，和WIDTH位宽一致；
REFIN：输入反转，true 或 false，在进行计算之前，原始数据是否翻转，如原始数据：0x34 = 0011 0100，如果REFIN为 true，进行翻转之后为0010 1100 = 0x2c；
- 标准的REFIN=true，是指对输入的每一个字节单独进行位反转。例如：如果你的数据是 0x12 0x34（两个字节），REFIN=true 的处理顺序是：先反转 0x12 -> 0x48，再反转 0x34 -> 0x2C，然后按顺序送入计算器。绝不会把整个0x1234一起反转；
REFOUT：输出反转，true 或 false，运算完成之后，得到的CRC值是否进行翻转，如计算得到的CRC值：0x97 = 1001 0111，如果REFOUT为 true，进行翻转之后为1110 1001 = 0xE9；
XOROUT：结果异或值，计算结果与此参数进行异或运算后得到最终的CRC值，和WIDTH位宽一致；

常用CRC多项式模型：

CRC算法名称	多项式公式	宽度	多项式	初始值	结果异或值	输入反转	输出反转
CRC-16/MODBUS	x¹⁶ + x¹⁵ + x² + 1	16	8005	FFFF	0000	true	true
CRC-8	x⁸ + x² + x + 1	8	07	00	00	false	false
CRC-32	x³² + x²⁶ + x²³ + x²² + x¹⁶ + x¹² + x¹¹ + x¹⁰ + x⁸ + x⁷ + x⁵ + x⁴ + x² + x + 1	32	04C11DB7	FFFFFFFF	FFFFFFFF	true	true
CRC-16/CCITT	x¹⁶ + x¹² + x⁵ + 1	16	1021	0000	0000	true	true
CRC-16/XMODEM	x¹⁶ + x¹² + x⁵ + 1	16	1021	0000	0000	false	false
CRC-8/MAXIM	x⁸ + x⁵ + x⁴ + 1	8	31	00	00	true	true

Q: CRC多项式为什么会形成这么多的模型？
A: 受限于不同行业硬件差异、检错效率要求、历史遗留问题等因素权衡下形成。

2. 模2运算

模2运算是一种二进制运算算法，是CRC计算的核心，与常规的二进制加减乘除不同，本质是异或运算，且不考虑进位和借位；

2.1. 模2加减

模即mod(Modulo)，取余数。所以模2就是除2取余。所以无论多大的数，模2的结果只有两种：0（偶数）或 1（奇数）。

本质就是异或操作，结果相同。

2.2. 模2除法

模2除法一种二进制计算方法，再进行除法运算时不计进位的除法

被除数首位为1时，商为1；首位为0时，商为0；
每一步得到的余数都要抛弃首位；
若新的被除数首位（即已抛弃首位的余数）为0，除数为0；

经典计算例子竖式：

          11101      ← 商
     ──────────
1001 ) 11110001      ← 被除数
       1001          ← 除数 × 1
       ────            模2减法处理
       01100001      ← 余数（抛弃首位，保留后4位）
        1001         ← 除数 × 1
        ────
        0101001      ← 余数
         1001        ← 除数 × 1
         ────
         001101      ← 余数
          0000       ← 除数 × 0（首位为0，商写0）
          ────
          01101      ← 余数
           1001      ← 除数 × 1
           ────
           0100      ← 最终余数

2.3. 模2乘法

模2乘法，同样不计进位

对中间结果处理方式使用模2加法处理

经典计算例子竖式：

      1 0 1 1
×       1 0 1
───────────────
      1 0 1 1
    0 0 0 0
  1 0 1 1
───────────────     模2加法处理
  1 0 0 1 1 1

2. CRC计算

简单来说：

发送方：数据 / 固定多项式 → 得到余数（= CRC），附在数据后面发出去；
接收方：收到数据 / 同一个固定多项式 → 求余数；
- 余数为0 → 数据正确；
- 余数非0 → 有错误。

2.1. CRC发送方计算处理流程

flowchart TD
    A[开始] --> B[CRC = INIT]
    B --> C[取下一个输入字节 DATA]

    C --> D{REFIN = true?}
    D -- 是 --> E[对 DATA 按位反转]
    D -- 否 --> F[保持 DATA 不变]
    E --> G[CRC = CRC XOR DATA]
    F --> G[CRC = CRC XOR DATA]

    G --> H[按CRC宽度补零<br>执行WIDTH次移位约简]
    H --> I[模2除法求余数]
    I --> J[得到新的CRC值]

    J --> K{还有下一个字节吗?}
    K -- 是 --> C
    K -- 否 --> L{REFOUT = true?}

    L -- 是 --> M[对CRC按位反转]
    L -- 否 --> N[保持CRC不变]

    M --> O[CRC = CRC XOR XOROUT]
    N --> O[CRC = CRC XOR XOROUT]

    O --> P[输出最终CRC]
    P --> Q[结束]

以一个简单的CRC-8为例，计算0x34：

多项式：0x07，实际为x^8 + x^2 + x + 1；
初始值：0x00；
结果异或：0x00；
输入反转：false；
输出反转：false；

步骤：

原始数据：0x34，即0x0011 0100；
INIT == 0x00，与原始异或（XOR，相同为0，不同为1，相异则或）运算后，仍为0x34；
REFIN == false，无需反转，仍为0x34；
左移8位补零，0011 0100 0000 0000；
- 补0是为了让除法的余数位数正好等于CRC宽度（这里是8位）；
模2除法！非二进制除法。11 0100 0000 0000 / 1 0000 0111 = 11 0100…1000 1100；
更新CRC = 0xC8；
REFOUT == false，无需反转CRC仍为0xC8；
XOROUT == 0x00，CRC异或后仍为0xC8；
通过CRC计算器计算结果位0xC8，与手算结果一致；

                    110100      ← 商
          ────────────────
100000111 ) 11010000000000      ← 被除数
            100000111           ← 除数 × 1
            ─────────
            01010011100000      ← 余数
             100000111          ← 除数 × 1
             ─────────
             0010010010000      ← 余数
              010010010000      ← 除数 × 0，余数
               100000111        ← 除数 × 1
               ─────────
               00010001100      ← 余数
                0010001100      ← 除数 × 0，余数
                 010001100      ← 除数 × 0，余数
                  ─────────
                  10001100      ← 最终余数

如果是多个数据会发生什么？计算0x12 0x34：

同上，模型用CRC-8

步骤：

原始数据：0x12，即0x0001 0010；
INIT == 0x00，与原始异或运算后，仍为0x12；
REFIN == false，仍为0x12；
左移8位补零，0001 0010 0000 0000；
模2除法：0001 0010 0000 0000 / 1 0000 0111 = 0001 0010…0111 1110；
更新CRC = 0x7E，取下一个DATA = 0x34；
REFIN == false 无需反转，DATA仍为0x34；
结合新数据，将当前CRC值0x7E与新字节0x34异或，为0x4A；
左移8位补零，0100 1010 0000 0000；
模2除法：0100 1010 0000 0000 / 1 0000 0111 = 0100 1010…1111 0001；
更新CRC = 0xF1；
REFOUT == false，无需反转CRC仍为0xF1；
XOROUT == 0x00，CRC异或后仍为0xF1；
通过CRC计算器计算结果位0xF1，与手算结果一致；

2.2. CRC接收方计算处理流程

接收方对于CRC校验的结果通常有以下两种校验方式：

直接比较法
- 发送方计算完成CRC，放在数据包的末尾发送出去。将数据和末尾的CRC值分离，用与发送方一样的模型，重新计算CRC，最后比较是否一致;
- 符合直觉。
零余子式
- 发送方计算完成CRC后，同样附加在末尾发送，接受方将接收到的整个字段（数据+CRC）作为输入，用与发送方一样的模型，重新计算CRC，如果传输正确，计算CRC结果一定是0（未验证过，数学原理，精力有限，点到为止）。
- 如果是带初始值和异或的模型里，余数并非为0，而是一个固定常数。这个常数，就是“余数为0”在寄存器里的“替身”，我们只需要判断最后这个值是不是常数，就能确定数据是否完整。
- 处理简单，无需区分数据和CRC字段。

3. CRC代码实现

以CRC-16/MODBUS为例：

多项式：0x8005，实际为x^16 + x^15 + x^2 + 1；
初始值：0xFFFF；
结果异或：0x00；
输入反转：true；
输出反转：true；

3.1. 直接计算法

/* CRC-16/MODBUS模型参数 */
#define CRC16_MODBUS_INIT           (0xFFFFU) // 初始值INIT
#define CRC16_MODBUS_XOROUT         (0x0000U) // 初始值XOROUT
#define CRC16_MODBUS_REFLECTED_POLY (0xA001U) // 反射多项式（REFIN=REFOUT=true时使用）
#define CRC16_MODBUS_BITS_PER_BYTE  (8U)      // 单字节位宽，即移位次数
#define CRC16_MODBUS_LSB_MASK       (0x0001U) // 最低有效位掩码

/**
 * @brief   计算CRC-16/MODBUS校验值（直接及算法）
 * @param   pBuf          [in]  待校验数据缓冲区
 * @param   u32Len        [in]  待校验数据长度（字节）
 * @param   pu16CrcResult [out] CRC计算结果
 * @retval  0  成功；-1  失败（入参为空）
 * @note    POLY=0x8005(反射0xA001) INIT=0xFFFF XOROUT=0x0000 REFIN=true REFOUT=true
 */
int8_t Crc16Modbus(const uint8_t *pBuf, uint32_t u32Len, uint16_t *pu16CrcResult)
{
    if ((pBuf == NULL) || (pu16CrcResult == NULL)) {
        return -1;
    }

    uint16_t u16Crc = CRC16_MODBUS_INIT;

    while (u32Len-- > 0U) {
        // REFIN=true：反转下，输入字节异或到CRC低字节即可，无需单独反转
        u16Crc ^= (uint16_t)(*pBuf++);

        // 每次处理一个字节，等效模2除法：右移8次，用反射多项式0xA001约简
        for (uint32_t i = 0U; i < CRC16_MODBUS_BITS_PER_BYTE; i++) {
            if ((u16Crc & CRC16_MODBUS_LSB_MASK) != 0U) {
                u16Crc = (u16Crc >> 1U) ^ CRC16_MODBUS_REFLECTED_POLY;
            } else {
                u16Crc >>= 1U;
            }
        }
    }

    // XOROUT=0x0000 无影响；
    // REFOUT=true 已由反射算法隐式处理
    *pu16CrcResult = u16Crc;
    return 0;
}

如何理解呢？似乎跟我们的手算的流程有所差异，主要还是为了提示工程实践中代码运行效率而做的优化。

代码首先给我们的CRC赋值初始值，相当于补0操作，如果不需要反转的初始值需要左移8位放到高字节；
因为REFIN=true，输入字节异或到CRC低字节。本来是要对输入进行位反转的。但这里并没有显式调用位反转函数，反转的效果被右移过程代替了，而无需真正反转每一位。这样省去了一个位反转步骤，提高了效率；
传统CRC算法通常用左移，但MODBUS因为 REFIN=REFOUT=true，所以采用右移算法，配合反射多项式 0xA001，其实就是模2除法的位级实现；
1. 检查CRC寄存器最低位（LSB）是否为1？
2. 如果为1，CRC右移1位再与反射多项式0xA001做异或；
3. 如果是0，仅右移1位；
输出结果，无需再反转，因为已经是反转过的了
- 右移算法中，输入反转，多项式反转，输出就是正的了不用再反转（算法已隐式处理）
- 左移手算中，输入反转，多项式正，输出就是反转的，还要再反转（需要显式反转）

这里我们假设输入0x34进行验证：

u16Crc = 0xFFFF

u16Crc ^= 0x34 → 0xFFCB

位0: LSB=1 → 右移0x7FE5 ^ 0xA001 = 0xDFE4
位1: LSB=0 → 右移 → 0x6FF2
位2: LSB=0 → 右移 → 0x37F9
位3: LSB=1 → 右移0x1BFC ^ 0xA001 = 0xBBFD
位4: LSB=1 → 右移0x5DFE ^ 0xA001 = 0xFDFF
位5: LSB=1 → 右移0x7EFF ^ 0xA001 = 0xDEFE
位6: LSB=0 → 右移 → 0x6F7F
位7: LSB=1 → 右移0x37BF ^ 0xA001 = 0x97BE

最终: 0x97BE，与CRC计算器计算结果一致

基本所有的CRC都是这个框架，遇到具体的模型适当修改即可。

3.2. 查表法

#define CRC16_MODBUS_INIT           (0xFFFFU) // 初始值INIT
#define CRC16_MODBUS_XOROUT         (0x0000U) // 初始值XOROUT

/* 预计算查找表：256个字节，每个对应8次右移约简的结果 */
static const uint16_t s_u16Table[256] = {
    0x0000U, 0xC0C1U, 0xC181U, 0x0140U, 0xC301U, 0x03C0U, 0x0280U, 0xC241U,
    0xC601U, 0x06C0U, 0x0780U, 0xC741U, 0x0500U, 0xC5C1U, 0xC481U, 0x0440U,
    0xCC01U, 0x0CC0U, 0x0D80U, 0xCD41U, 0x0F00U, 0xCFC1U, 0xCE81U, 0x0E40U,
    0x0A00U, 0xCAC1U, 0xCB81U, 0x0B40U, 0xC901U, 0x09C0U, 0x0880U, 0xC841U,
    0xD801U, 0x18C0U, 0x1980U, 0xD941U, 0x1B00U, 0xDBC1U, 0xDA81U, 0x1A40U,
    0x1E00U, 0xDEC1U, 0xDF81U, 0x1F40U, 0xDD01U, 0x1DC0U, 0x1C80U, 0xDC41U,
    0x1400U, 0xD4C1U, 0xD581U, 0x1540U, 0xD701U, 0x17C0U, 0x1680U, 0xD641U,
    0xD201U, 0x12C0U, 0x1380U, 0xD341U, 0x1100U, 0xD1C1U, 0xD081U, 0x1040U,
    0xF001U, 0x30C0U, 0x3180U, 0xF141U, 0x3300U, 0xF3C1U, 0xF281U, 0x3240U,
    0x3600U, 0xF6C1U, 0xF781U, 0x3740U, 0xF501U, 0x35C0U, 0x3480U, 0xF441U,
    0x3C00U, 0xFCC1U, 0xFD81U, 0x3D40U, 0xFF01U, 0x3FC0U, 0x3E80U, 0xFE41U,
    0xFA01U, 0x3AC0U, 0x3B80U, 0xFB41U, 0x3900U, 0xF9C1U, 0xF881U, 0x3840U,
    0x2800U, 0xE8C1U, 0xE981U, 0x2940U, 0xEB01U, 0x2BC0U, 0x2A80U, 0xEA41U,
    0xEE01U, 0x2EC0U, 0x2F80U, 0xEF41U, 0x2D00U, 0xEDC1U, 0xEC81U, 0x2C40U,
    0xE401U, 0x24C0U, 0x2580U, 0xE541U, 0x2700U, 0xE7C1U, 0xE681U, 0x2640U,
    0x2200U, 0xE2C1U, 0xE381U, 0x2340U, 0xE101U, 0x21C0U, 0x2080U, 0xE041U,
    0xA001U, 0x60C0U, 0x6180U, 0xA141U, 0x6300U, 0xA3C1U, 0xA281U, 0x6240U,
    0x6600U, 0xA6C1U, 0xA781U, 0x6740U, 0xA501U, 0x65C0U, 0x6480U, 0xA441U,
    0x6C00U, 0xACC1U, 0xAD81U, 0x6D40U, 0xAF01U, 0x6FC0U, 0x6E80U, 0xAE41U,
    0xAA01U, 0x6AC0U, 0x6B80U, 0xAB41U, 0x6900U, 0xA9C1U, 0xA881U, 0x6840U,
    0x7800U, 0xB8C1U, 0xB981U, 0x7940U, 0xBB01U, 0x7BC0U, 0x7A80U, 0xBA41U,
    0xBE01U, 0x7EC0U, 0x7F80U, 0xBF41U, 0x7D00U, 0xBDC1U, 0xBC81U, 0x7C40U,
    0xB401U, 0x74C0U, 0x7580U, 0xB541U, 0x7700U, 0xB7C1U, 0xB681U, 0x7640U,
    0x7200U, 0xB2C1U, 0xB381U, 0x7340U, 0xB101U, 0x71C0U, 0x7080U, 0xB041U,
    0x5000U, 0x90C1U, 0x9181U, 0x5140U, 0x9301U, 0x53C0U, 0x5280U, 0x9241U,
    0x9601U, 0x56C0U, 0x5780U, 0x9741U, 0x5500U, 0x95C1U, 0x9481U, 0x5440U,
    0x9C01U, 0x5CC0U, 0x5D80U, 0x9D41U, 0x5F00U, 0x9FC1U, 0x9E81U, 0x5E40U,
    0x5A00U, 0x9AC1U, 0x9B81U, 0x5B40U, 0x9901U, 0x59C0U, 0x5880U, 0x9841U,
    0x8801U, 0x48C0U, 0x4980U, 0x8941U, 0x4B00U, 0x8BC1U, 0x8A81U, 0x4A40U,
    0x4E00U, 0x8EC1U, 0x8F81U, 0x4F40U, 0x8D01U, 0x4DC0U, 0x4C80U, 0x8C41U,
    0x4400U, 0x84C1U, 0x8581U, 0x4540U, 0x8701U, 0x47C0U, 0x4680U, 0x8641U,
    0x8201U, 0x42C0U, 0x4380U, 0x8341U, 0x4100U, 0x81C1U, 0x8081U, 0x4040U
};

/**
 * @brief   计算CRC-16/MODBUS校验值（查表法）
 * @param   pBuf          [in]  待校验数据缓冲区
 * @param   u32Len        [in]  待校验数据长度（字节）
 * @param   pu16CrcResult [out] CRC计算结果
 * @retval  0  成功；-1  失败（入参为空）
 * @note    POLY=0x8005(反射0xA001) INIT=0xFFFF XOROUT=0x0000 REFIN=true REFOUT=true
 *          查表法原理：把逐位右移8次的过程预计算成256个表项，
 *          每个表项=该字节值经过8次“检查LSB→右移→条件异或”后的CRC值
 */
int8_t Crc16ModbusTable(const uint8_t *pBuf, uint32_t u32Len, uint16_t *pu16CrcResult)
{
    if ((pBuf == NULL) || (pu16CrcResult == NULL)) {
        return -1;
    }

    uint16_t u16Crc = CRC16_MODBUS_INIT;

    while (u32Len-- > 0U) {
        uint8_t u8Index = (uint8_t)(u16Crc ^ (*pBuf++));
        u16Crc = (u16Crc >> 8U) ^ s_u16Table[u8Index];
    }

    *pu16CrcResult = u16Crc;
    return 0;
}

查表法等效于直接计算法中的内层for循环：

CRC赋值初始值；
REFIN=true，输入字节异或到CRC低字节；
查表：(CRC的低字节)作为索引，取出预计算的8次右移结果。它这个表的索引就是所有可能的低字节值，在8次右移过程中产生的CRC累积值。是一个空间换时间的办法；
CRC右移8位（高字节→低字节），异或表项，相当于一次性完成8次约简。
注意：这里的异或、移位顺序与逐位直接计算法完全等价。

其他衍生：

双表法：针对8位单片机，处理16位需要额外开销，避免编译器生成低效代码，手动拆成8位。
短表法：针对Flash极度紧张的场景，折中之道。

3.3. 硬件CRC

一些芯片支持硬件CRC，内部集成专门实现了CRC运算的数字逻辑电路（LFSR）。这样的话CPU不需要自己移位异或，因此速度远快于软件实现。但是由于运算规则由硬件电路决定，灵活性有限，即意味着它把多项式画成门电路焊死在硬件上了，所以不能随意更改。

像HC32的硬件CRC模块遵循ISO/IEC 13239定义，支持CRC32(x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x^+1)、CRC16(x^16+x^12+x^5+1)两种算法。虽然生成多项式固定，无法修改，但支持配置CRC的其他模型参数，包括初始值（Init）、输入反转（RefIn）、输出反转（RefOut）以及最终异或（XorOut）。CPU可通过APB总线读写相关寄存器，实现CRC数据输入、参数配置、结果读取以及校验状态获取等操作。

我CRC用MODBUS版本比较多，这个多项式不匹配，没现成代码，此处可以参考官方例程。

常见问题

初始值为什么是0xFF？

CRC的计算，本质上就是把你的数据（看作一个很大的二进制数）除以多项式（比如 0x07），得到的余数就是CRC值。

被除数 = 你的原始数据（后面补上 WIDTH 个 0）
除数 = 多项式（如 0x07）
余数 = CRC校验值

如果INIT为0x00，意味着0x01 0x02算出来的CRC，和数据0x00 0x01 0x02算出来的CRC，完全一样，失去校验能力。

如果INIT为0xFF，意味着寄存器初值是0xFF，0x01 0x02算出来的CRC，和数据0x00 0x01 0x02算出来的CRC， CRC就不同了。

全F和全0的关键区别在于：全F能区分数据开头的0，全0则不能。

但是为什么部分多项式仍用0x00作为初始值，可能数据本身不会出现前置0填充？或是历史遗留问题？

参考资料

Leslie Shang. (2022). CRC校验原理与手算案例. https://shangzg.top/zh-cn/2022-11-07-crc-verification-principle-and-manual-calculation-case/ ↩