📚 课程目录第4章 CRC软件实现

4. CRC软件实现：查表法CRC计算、逐位计算法、性能对比分析

CRC校验在Bootloader里有多重要，我就不多说了。今天咱们直接聊实现——两种主流软件算法：查表法和逐位计算法。我会把两种方法的原理、代码、性能差异都掰开揉碎了讲清楚。

我个人习惯在项目初期先用逐位法验证CRC多项式是否正确，等逻辑稳定了再换成查表法提速。你想想看，如果一开始就上查表法，表生成错了，排查起来多麻烦。

4.1 逐位计算法：最朴素的CRC实现

逐位计算法，说白了就是按照CRC的数学定义，一个bit一个bit地算。虽然慢，但逻辑最直观，适合理解CRC的本质。

核心思路是这样的：

把数据左移一位，腾出最低位给新bit
检查移出的最高位是不是1
如果是1，就跟多项式做异或（XOR）
重复直到所有bit处理完

来看代码，我用的是CRC-16/CCITT（多项式0x1021）做例子：

uint16_t crc16_bitwise(uint8_t *data, uint32_t len)
{
    uint16_t crc = 0x0000;  // 初始值
    uint32_t i, j;
    
    for (i = 0; i < len; i++) {
        crc ^= (uint16_t)data[i] << 8;  // 把字节放到CRC寄存器高8位
        for (j = 0; j < 8; j++) {
            if (crc & 0x8000) {          // 检查最高位
                crc = (crc << 1) ^ 0x1021;  // 左移并异或多项式
            } else {
                crc <<= 1;               // 只左移
            }
        }
    }
    return crc;
}

我的经验：这段代码我一般放在单元测试里用。它慢是慢了点，但每一步都能单步调试，特别适合验证多项式选对了没有。我曾经在一个项目里因为多项式搞反了高低位，查了整整两天bug，最后就是用逐位法对比标准值才发现的。

4.2 查表法：空间换时间的经典套路

查表法的核心思想很简单：既然逐位法里每个字节都要循环8次，那不如提前把256种可能的字节结果算好，存成一张表。计算时直接查表，一个字节只需要一次查表和几次异或操作。

先看表怎么生成：

uint16_t crc16_table[256];

void crc16_init_table(void)
{
    uint16_t i, j;
    uint16_t crc;
    
    for (i = 0; i < 256; i++) {
        crc = i << 8;  // 把字节值放到高8位
        for (j = 0; j < 8; j++) {
            if (crc & 0x8000) {
                crc = (crc << 1) ^ 0x1021;
            } else {
                crc <<= 1;
            }
        }
        crc16_table[i] = crc;
    }
}

表生成后，计算就快多了：

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

你看，内层循环没了。每个字节只需要：一次异或、一次查表、一次移位、一次异或。就这么简单。

注意：查表法虽然快，但表要占512字节（CRC-16）或1024字节（CRC-32）的ROM空间。在Flash只有几KB的老旧MCU上，这个开销你得掂量掂量。我曾经在一个8051项目里，ROM只剩1KB，最后硬着头皮用了逐位法。

4.3 两种方法的性能对比

光说理论不够，咱们上数据。我在STM32F103（72MHz）上实测过，处理1KB数据：

对比项	逐位计算法	查表法
代码量（ROM）	约200字节	约800字节（含表）
RAM占用	几乎为0	0（表放ROM）
处理1KB耗时	约2.3ms	约0.15ms
每字节CPU周期	约160周期	约10周期
适用场景	ROM紧张、调试阶段	性能敏感、量产固件

看到差距了吧？查表法快了整整15倍。在Bootloader里，如果你要校验一个256KB的固件，逐位法要算将近600ms，查表法只要40ms左右。用户等升级进度条的时候，这差距体感很明显。

4.4 查表法的变种：半字节查表

如果觉得256字节的表还是太大，有个折中方案——半字节查表。一次查4个bit，表只有16项，32字节。速度介于逐位法和全表法之间。

我简单说一下思路：

表大小：16项，每项2字节，共32字节
每个字节分高4位和低4位两次查表
速度大约是逐位法的2倍，全表法的1/8

这个方案在资源极度受限的MCU上很实用。我记得有一次帮客户优化一个8位机的Bootloader，ROM只剩256字节，全表放不下，逐位法又太慢，最后就是用半字节查表搞定的。

4.5 性能对比的底层逻辑

为什么会差这么多？我画个图你就明白了：

从图上能清楚看到，逐位法每个字节要经历8次判断和分支，而查表法只有4步固定操作。CPU最怕的就是分支预测失败，查表法恰好避开了这个问题。

4.6 实际项目中的选择建议

说了这么多，到底该用哪种？我根据经验给个参考：

Bootloader场景（推荐查表法）：固件校验是Bootloader的核心功能，速度直接影响用户体验。而且Bootloader的ROM通常留得比较充裕，几百字节的表不是问题。
调试阶段（用逐位法）：我习惯在开发初期先用逐位法，配合标准CRC计算器验证结果。等逻辑确认无误了，再换成查表法。
资源极度受限（半字节查表）：如果ROM实在紧张，半字节查表是个不错的折中。

核心结论：

逐位法：代码简单，适合教学和调试，但性能差（每字节约160周期）
查表法：速度快（每字节约10周期），但多占几百字节ROM
半字节查表：折中方案，表仅32字节，速度约为全表的1/8
实际项目中，Bootloader固件校验强烈建议用查表法

嗯，CRC的软件实现就聊到这儿。两种方法各有各的用武之地，关键是你得清楚自己项目的资源约束和性能要求。选对了，事半功倍；选错了，后面改起来可够你喝一壶的。