4. CRC 计算实现：软件逐位法与查表法
上一节我给大家介绍了 CRC 的基本数学原理，说白了就是多项式除法取余数。但理论归理论，真到写代码的时候，你会发现 CPU 面对这种位运算其实挺“笨”的。嗯，今天咱们就来聊聊两种最常用的软件实现方法——逐位法和查表法。
我刚开始做嵌入式时，项目里用的是 32 位无转盘电机，QSPI 通信每次要传 256 字节的波形数据。那时候我傻乎乎地用了逐位法，结果发现每包数据的 CRC 计算竟然占掉了主循环 20% 的时间。后来换成查表法，才把时间压到 2% 以内。今天就把这两种方法的坑和经验全倒出来。
4.1 软件逐位法
逐位法的思路非常直接：模拟硬件移位寄存器的行为，按位处理输入数据。每次移入 1 位，判断移出的最高位是否为 1，如果为 1 就做一次多项式异或。
下面是一个典型的 CRC-8 逐位法 C 代码（多项式 0x07，初始值 0x00）：
uint8_t crc8_bitwise(uint8_t *data, uint16_t len, uint8_t poly) {
uint8_t crc = 0x00;
for (uint16_t i = 0; i < len; i++) {
crc ^= data[i];
for (uint8_t bit = 0; bit < 8; bit++) {
if (crc & 0x80) {
crc = (crc << 1) ^ poly;
} else {
crc <<= 1;
}
}
}
return crc;
}个人提示：注意这里的多项式 0x07 是去掉最高位 1 后的形式，也就是生成多项式的低 8 位。很多初学者会直接写完整多项式，结果算出来的 CRC 永远对不上。我踩过这个坑，连续查了两天才发现问题。
逐位法的优点是代码简单、内存占用极低，只需要几个寄存器和临时变量。但缺点也很明显：每个字节都要循环 8 次，每处理 1 字节就要执行 8 × (若干次移位+判断) 的操作。
拿刚才的 CRC-8 来说，处理 1KB 数据需要大约 8×1024 = 8192 次移位循环。如果是 CRC-32，循环次数更是翻倍。实际上，在 STM32F103 @72MHz 上，逐位法跑 256 字节的 QSPI 数据包，大概耗时 60μs 左右——对于 10MHz 的 QSPI 时钟来说，这个时间已经开始影响帧间隔了。
注意：逐位法在硬件不支持 CRC 计算时是“保底方案”，但不建议用在数据量大于 64 字节的高频通信中。我曾经在一个 CAN-FD 项目里用了逐位法，结果导致帧间间隔超标，控制器反复重发，差点把总线打爆。
4.2 查表法
查表法的核心思路是以空间换时间。它的原理是这样的：
对于任意一个字节输入（0~255），我们可以提前计算出这个字节对当前 CRC 寄存器值的“贡献”。更准确地说，是预计算出一个 crc_high_byte ^ input_byte 到新 CRC 高字节的映射表。因为移位过程本质上是线性变换，所以通过查一次表就能代替 8 次逐位循环。
标准查表法实现（CRC-8，多项式 0x07）：
// 预计算 256 字节的表
static uint8_t crc8_table[256];
void crc8_init_table(uint8_t poly) {
for (uint16_t i = 0; i < 256; i++) {
uint8_t crc = i;
for (uint8_t bit = 0; bit < 8; bit++) {
if (crc & 0x80) {
crc = (crc << 1) ^ poly;
} else {
crc <<= 1;
}
}
crc8_table[i] = crc;
}
}
uint8_t crc8_table_lookup(uint8_t *data, uint16_t len) {
uint8_t crc = 0x00;
for (uint16_t i = 0; i < len; i++) {
crc = crc8_table[crc ^ data[i]];
}
return crc;
}你看，查表法的计算核心只有一行 crc = crc8_table[crc ^ data[i]];，速度比逐位法快了将近 8 倍。对于 CRC-16 / CRC-32，查表法通常使用 256 字 × 2 字节或 4 字节的大表，虽然内存占用增大（例如 CRC-32 表需要 1024 字节），但在绝大多数 MCU 上都可以接受。
关键点：查表法的本质是“用预先算好的结果，跳过重复的移位循环”。表越大，速度越快，但内存开销也越大。实际项目中，如果 CRC 计算在中断中或频繁调用，我会毫不犹豫选查表法。
4.3 两种方法的对比
| 特性 | 逐位法 | 查表法 |
|---|---|---|
| 代码量 | 很小，几行函数 | 中等，需预计算表 |
| 内存占用 | 极低（仅栈变量） | 较多（256~1024 字节表） |
| 计算速度 | 慢，每字节 8~32 次移位 | 快，每字节 1 次查表+异或 |
| 适合场景 | 偶发校验、资源受限 MCU | 高频通信、大数据量、中断中 |
| QSPI 推荐度 | 不推荐（超过 16 字节时） | 强烈推荐 |
这里我要特别说一下：查表法的表也可以放在 flash 中。很多 MCU 的 flash 比 RAM 大得多，把 const 表放在 flash 里，就不占用 RAM。我在 STM32G4 上就写过 const uint8_t crc8_table[256] = {...}; 用编译时的常量初始化，运行时直接查 flash，速度完全不受影响。
4.4 查表法的高级变体：双字节查表
如果 QSPI 的数据是 16 位对齐的，我们还可以进一步优化。CRC-16 可以使用 256×2 字节的表，每次处理 2 字节。原理类似：将两个输入字节合并成一个 16 位索引，一步算出两个字节对 CRC 的贡献。
实现思路如下：
- 预计算一个 65536 条目的大表（每个条目 2 字节），内存约 128KB，普通 MCU 放不下。
- 更实用的方案是使用“反射表”+“半字节查表”组合，即把 16 位 CRC 分成高低两个 8 位表，分别查两次。这样总表大小 2×256×2 = 1KB，速度比单字节快一倍。
对于 QSPI 应用，我个人建议 先上标准 256 字节查表法，如果还需要提速，再考虑双字节或半字节优化。不要一开始就把复杂度拉满，免得出了问题不好排查。
避坑指南：我曾经在某个项目里用了双字节查表，结果因为结构体字节对齐问题，导致查表索引算错了值。折腾了一个下午才发现是编译器把 #pragma pack(1) 给忽略了。建议在使用多字节查表前，先用 assert(sizeof(your_struct) == expected) 检查对齐。
4.5 知识结构总结
为了帮你理清这两种方法的关系，我画了一张流程图。它展示了从输入数据到最终 CRC 值的两条路径，以及各自的决策点。
从这张图你能看到，逐位法路径长、节点多，而查表法路径短，不需要内部移位循环。实际选择时，你只要问自己两个问题：
1. 我的 RAM/Flash 能不能分出几百字节存放 CRC 表？
2. 我的 QSPI 通信速率需要多快的校验？
如果答案都是“是”，那就直接上查表法。如果 RAM 实在紧张（比如只有 2KB 的廉价 MCU），或者数据量极小（比如每次只发 4 字节命令），逐位法也能凑合。但说实话，现在哪怕是最便宜的单片机，128 字节的表都能轻松放下，所以我个人极少再用逐位法。