CRC算法实现：查表法 vs 直接计算法

说到CRC的软件实现，圈子里一直有个老话题：到底用查表法还是直接计算法？

我入行那会儿，项目里MCU资源抠得很死，ROM才几KB，RAM更是按字节算。那时候我首选直接计算法，简单嘛，占用空间小。后来芯片越来越便宜，Flash动不动几百KB，查表法才真正成为主流。但这不是说直接计算法就没用了——关键看你的场景。

这一节，咱们就把两种实现方式掰开揉碎了讲清楚。不只是贴代码，更重要的是让你理解：为什么查表法快？快在哪里？直接计算法什么时候反而更好？

两种方法的核心差异

先看一个简单的对比表格，后面再细说细节。

其实说白了，这就是「时间」和「空间」的经典取舍。你想想看，一个字节8个bit，直接计算法要依次处理每一位，一个字节进一次计算函数就要循环8次；而查表法——一次查表，搞定。

直接计算法：逐位模拟硬件移位寄存器

直接计算法，本质上是在用软件模拟硬件里的LFSR（线性反馈移位寄存器）。我个人习惯用这种实现来做原型验证，因为改起来快，调试方便。

看一个标准CRC-16的实现：

uint16_t crc16_direct(uint8_t *data, uint32_t len) {
    uint16_t crc = 0xFFFF;   // 初始值
    for (uint32_t i = 0; i < len; i++) {
        crc ^= data[i];      // 把输入字节异或到寄存器高位
        for (int j = 0; j < 8; j++) {
            if (crc & 0x8000) {
                crc = (crc << 1) ^ 0x8005;  // 多项式
            } else {
                crc <<= 1;
            }
        }
    }
    return crc;
}

这段代码的逻辑很直观：

• 外部循环处理每个字节
• 内部循环处理每个bit
• 每次判断最高位，决定是否异或多项式

避坑指南：我见过不少新手把内层循环的移位方向搞反了。嗯，这里要特别注意：你的多项式0x8005是左移版本，移位次数也是8次。如果换成右移实现的CRC，移位方向和多项式写法都要跟着变。不要抄错方向！

直接计算法的优点很明显——代码量小，依赖少，任何C编译器都能编译。但它的性能短板也很致命：每字节8次循环，1000字节就要跑8000次移位和判断。在高速QSPI传输场景下，这种开销根本扛不住。

查表法：用空间换时间

查表法的核心思想很简单：既然每次对一个字节做8次移位的结果是确定的，为什么不提前算好，存起来？

我用的是一个经典思路：对0~255这256个值，分别用直接计算法算出它们的CRC「余数」，存在一个表里。实际校验时，直接查表代替8次循环。

先看建表函数：

void crc16_build_table(uint16_t table[256]) {
    for (int i = 0; i < 256; i++) {
        uint16_t crc = i << 8;   // 模拟字节进入寄存器高位
        for (int j = 0; j < 8; j++) {
            if (crc & 0x8000) {
                crc = (crc << 1) ^ 0x8005;
            } else {
                crc <<= 1;
            }
        }
        table[i] = crc;
    }
}

建好的表长这样（只截取部分）：

接下来是用表计算CRC的函数：

uint16_t crc16_table_driven(uint16_t table[256], uint8_t *data, uint32_t len) {
    uint16_t crc = 0xFFFF;
    for (uint32_t i = 0; i < len; i++) {
        uint8_t idx = ((crc >> 8) ^ data[i]) & 0xFF;
        crc = (crc << 8) ^ table[idx];
    }
    return crc;
}

看到了吗？内层循环完全消失了。每处理一个字节，就是一次查表、一次异或、一次移位。

为什么能这样写？ 我简单解释下原理：寄存器高8位和输入字节异或后，正好作为表的索引。表的输出就是原本要移位8次才能得到的结果。你想想看，256个表项，查一次只要一个数组访问，比串行移64次快多少？

SVG：查表法核心流程图

下面这张图，是我画给团队新人看的，清晰展示了查表法的数据流：

两种方法的选择建议

我做个简单的小结，方便你照着选：

• 用查表法，如果：
  • 你要校验的数据量比较大（几百字节以上）
  • CRC计算频率高，比如每包数据都要算
  • 你的MCU有足够的Flash（多256字节/512字节不是事）
  • QSPI等高速接口的数据校验
• 用直接计算法，如果：
  • ROM/RAM非常紧张，比如4KB以下的MCU
  • 只需要算几次CRC，对速度没要求
  • 你还在调试前期，频繁换多项式
  • 做Bootloader时不想多占空间

再说一个少见但重要的点：查表法不只是字节索引这一个版本。如果你追求极致速度，还可以用半字节查表法（16项的表）或者双字节查表法（65536项的表）。前者平衡了空间和速度，后者几乎是暴力提速——但表太大，一般MCU吃不消。我只有在FPGA仿真验证时才会用双字节表，嵌入式里很少碰。

好了，两种方法的核心实现和对比就到这。你可以在实际项目中按需选用。记住一个原则：先确认性能瓶颈在哪，再决定用哪种。不要为了炫技选查表法浪费资源，也不要为了省空间死磕直接计算法拖垮系统。