📚 课程目录第4章 CRC计算方法

CRC计算方法：按位计算与查表法

说到CRC的计算，其实就两种主流方式：按位算和查表算。我刚开始啃那会儿总觉得查表法很神秘，后来自己手写过一张表，发现核心逻辑就是预计算。你想想看，一个是纯串行，一个是用空间换时间，各有各的用武之地。

按位计算：最原生的方式

按位计算，也叫逐比特法。直接对应多项式除法的数学定义，比特流从左向右（或从右向左）逐个输入，每进一位就决定要不要异或多项式。说白了就是手工在电路上做除法。

uint8_t crc8_bitwise(uint8_t data, uint8_t poly) {
    uint8_t crc = 0;
    for (int i = 0; i < 8; i++) {
        // 取出最高位（这里假设 MSB-first）
        uint8_t msb = (crc >> 7) & 0x01;
        crc <<= 1;
        if (msb) crc ^= poly;
        // 处理数据位
        uint8_t data_bit = (data >> (7 - i)) & 0x01;
        crc ^= data_bit;
    }
    return crc;
}

上面这段代码虽然简单，但坑不少。我记得有个项目，嵌入式工程师把 poly 写成 0x07（标准 CRC-8），却用的是 0x31 的表格，结果算出来的 CRC 死活对不上。找了一下午，发现就是字节序没对齐。

我曾经踩过的坑： 在按位计算中，"输入序"和"多项式序"必须一致。
MSB-first 就要用正向多项式，LSB-first 就要用反向多项式。混用的话，查表法和按位法永远算不到一起。

一个小技巧： 按位计算适合硬件 RTL 实现，容易流水化。但在软件里，每比特一次循环，一帧 1500 字节需要循环 12000 次，性能堪忧——这就是查表法诞生的原因。

查表法：把计算变成查内存

查表法，说白了就是把"按位计算一个字节"的结果事先算好存起来。实际查表时，只需要从当前寄存器中拿到索引值，做一次查表加一次异或。

为什么能这么做？因为 CRC 计算是线性的，一个字节的完整处理可以折叠成一步。核心公式可以表达为：

CRC_new = (CRC_old << 8) XOR table[(CRC_old >> 8) XOR byte]

我们用预计算方法生成这张表。下面是一个典型的表生成函数（以 CRC-8 为例）：

void generate_crc8_table(uint8_t table[256], uint8_t poly) {
    for (int i = 0; i < 256; i++) {
        uint8_t crc = i;
        for (int j = 0; j < 8; j++) {
            if (crc & 0x80) {
                crc = (crc << 1) ^ poly;
            } else {
                crc <<= 1;
            }
        }
        table[i] = crc;
    }
}

表建好后，查表计算一个消息的 CRC 就简单了：

uint8_t crc8_table_lookup(uint8_t *data, size_t len, uint8_t table[256]) {
    uint8_t crc = 0;
    for (size_t i = 0; i < len; i++) {
        uint8_t index = crc ^ data[i];
        crc = (crc << 8) ^ table[index];  // 注意这里左移8位适用于CRC-16/32写法
    }
    return crc;
}

当然这个简化示例只适合 CRC-8 的位宽消化。对于 CRC-16/32，你需要将寄存器拆分成高字节和低字节进行查表。我通常的做法是将 2 字节或 4 字节的寄存器看作整体，每次用高 8 位做索引。

    核心思想： 查表法的速度突破就在那里——每个字节只用两次操作（一次异或、一次查内存）。比按位法快整整一个数量级，尤其是在 Cortex-M 这类有单周期闪存读取的 MCU 上。

对比与选型

对比项	按位计算	查表法（256 字节表）
处理粒度	逐比特	逐字节
速度	低，约 1 循环 / 比特	高，约 3-5 循环 / 字节
内存占用	仅寄存器	256 字节（CRC-8）～ 1KB（CRC-32）
适用场景	硬件实现、极低资源环境	软件实现、高吞吐
灵活性	多项式可运行时变更	需预生成表

我个人习惯：如果芯片 flash 够用（现在基本都够），我二话不说用查表法。只有在 FPGA 或模拟验证里确认算法行为时，我才会按位手算验证。

千万别忘： 查表法的表是按位宽和多项式配套的。CRC-8 用 256 字节表，CRC-16 用 512 字节表（一列高字节，一列低字节），CRC-32 用 1024 字节表。
我曾经帮同事调试，他发现 CRC-32 算出来不对，结果是因为他把一张 16 位的表当 32 位用，索引范围直接从 0-255 扩到了 0-65535，表长度不够，数组越界。

看到这个图你应该能理解：查表法并没有改变 CRC 的数学本质，它只是把"逐比特的循环"合并成了"逐字节的查表+异或"。速度提升的关键就在于减少循环次数：从 8M 次减到 M 次（M 为字节数）。

不过说实话，两种方式并不是非此即彼。我在做故障注入测试的时候，经常会在测试夹具里用按位法验证查表法的输出。一旦两边的 CRC 计算结果不一致，立刻就能发现查表有没有对齐，表有没有生成错。