C语言CRC-CCITT校验的按位、查表与半字节实现原理及代码

CRC的基本原理与生成规则

CRC校验基于线性编码理论。发送端将待发送的数据序列视为一个高阶多项式，使用预定义的生成多项式进行模2除法（即异或运算），得到的余数即为CRC校验码。接收端接收到数据后，重新进行同样的运算，若余数为0，则判定传输无误。

不同标准对应不同的生成多项式，常见的包括：

• CRC-CCITT：G(X) = X^16 + X^12 + X^5 + 1，对应的系数常量为 0x1021（不含高位隐含项）。
• CRC-32：常用于以太网等高速传输，多项式为 X^32 + X^26 + ... + 1。

理解模2运算的关键在于“无进位加法”与“无借位减法”，这在底层均等同于 XOR（异或）操作。

第一步：实现基础按位计算

这是最直观的方法，通过将数据每一位左移并参与异或运算来求余。虽然占用内存极少，但循环次数多，实时性较差。

1. 初始化：设置 crc 寄存器初始值为 0。
2. 遍历字节与位：对每个输入字节的8个位依次进行处理。
3. 核心判断逻辑：

unsigned char test[16] = {0x00,0x11,0x22,0x33,0x44,0x55,0x66,0x77,0x88,0x99,0xaa,0xbb,0xcc,0xdd,0xee,0xff};
unsigned int crc = 0;
// 假设 ptr 指向 test，len 为长度

while(len--) {
    for(i = 0x80; i != 0; i = i >> 1) {
        // 如果最高位为1，则左移后需要除以生成多项式
        if((crc & 0x8000) != 0) {
            crc = (crc << 1) ^ 0x1021;
        } else {
            crc = crc << 1;
        }
        
        // 如果当前数据位为1，同样需要对数据进行异或处理
        if((*ptr & i) != 0) {
            crc = crc ^ 0x1021;
        }
    }
    ptr++;
}

注：上述简化版代码利用了 (X * 2) % P == (X % P) * 2 % P 的特性。在模2除法中，左移一位等效于乘以2；若最高位溢出，则必须再异或多项式以求得新的余数。

第二步：构建按字节查表快速算法

按位计算在处理大数据流时耗时过长。利用“同态性质”，可以将一个字节的校验结果预先算好并存入数组（查找表）。这样只需针对每个字节进行一次查表操作，速度可提升约8倍。

1. 生成 256 项 CRC 表

通过调用上面的按位算法，计算出 0x00 到 0xFF 每个字节独立运算后的 CRC 值：

// 生成表格的过程示例
for(j = 0; j < 256; j++) {
    unsigned int crc = 0;
    for(i = 0x80; i != 0; i = i >> 1) {
        if((crc & 0x8000) != 0)
            crc = (crc << 1) ^ 0x1021;
        else
            crc = crc << 1;
        if((j & i) != 0)
            crc = crc ^ 0x1021;
    }
    table[j] = crc;
}

2. 使用表格进行快速计算

计算时，将当前的 CRC 值右移8位作为索引，并与当前字节进行异或。该结果作为下标访问 table[]，然后与原来的 CRC 值剩余部分再次异或。

unsigned int crc_table[256] = {
    0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50a5, 0x60c6, 0x70e7,
    0x8108, 0x9129, 0xa14a, 0xb16b, 0xc18c, 0xd1ad, 0xe1ce, 0xf1ef,
    // ... 此处省略中间16项，实际需填入完整的 256 项常量 ...
    0xef1f, 0xff3e, 0xcf5d, 0xdf7c, 0xaf9b, 0xbfba, 0x8fd9, 0x9ff8,
    0x6e17, 0x7e36, 0x4e55, 0x5e74, 0x2e93, 0x3eb2, 0x0ed1, 0x1ef0
};

void calc_crc_byte(unsigned char *data, int len) {
    unsigned int crc = 0;
    while(len--) {
        // 取高8位并异或新数据
        unsigned char index = (unsigned char)(crc >> 8) ^ *data;
        // 左移8位（丢弃已处理的高字节），并查表异或
        crc = (crc << 8) ^ crc_table[index];
        data++;
    }
    return crc;
}

第三步：进阶——半字节（Nibble）查表法

如果系统 RAM 非常紧张（例如老旧单片机），256 项的整型表（占据 512 bytes）可能显得过大。可以将查表粒度缩小至 4 位（Hex），仅需 16 项。

此方法每次处理半个字节，需要循环两次才能处理完一个完整字节：

unsigned int crc_table[16] = {
    0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50a5, 0x60c6, 0x70e7,
    0x8108, 0x9129, 0xa14a, 0xb16b, 0xc18c, 0xd1ad, 0xe1ce, 0xf1ef
};

void calc_crc_nibble(unsigned char *data, int len) {
    unsigned int crc = 0;
    while(len--) {
        // 处理上半个 4 位
        unsigned char idx_high = (crc >> 12) ^ (*data >> 4);
        crc = (crc << 4) ^ crc_table[idx_high];
        
        // 处理下半个 4 位
        unsigned char idx_low = (crc >> 12) ^ (*data & 0x0f);
        crc = (crc << 4) ^ crc_table[idx_low];
    }
    return crc;
}

总结

CRC-CCITT 算法在 C 语言中有多种权衡方案：按位法无需额外空间但速度慢；全字节查表法速度快且是工程首选；半字节查表法则是在速度与体积间的折中。开发者应依据目标平台的内存限制与性能需求进行选择。以上就是 C语言实现CRC校验方法的详细内容，更多关于C语言基础算法的资料请关注本站其它相关文章！