C语言实现crc16原理及解释

CRC (Cyclic Redundancy Check) 16是一种广泛用于数据校验的算法，它计算数据的二进制串并返回一个16位的校验码，用于检测传输过程中的错误。在C语言中实现CRC16的基本步骤包括：

1. 初始化：定义一组固定的CRC寄存器值（通常称为Polynomial Generator Register，PGR），如常见的x^16 + x^15 + x^2 + 1（用于CRC-16-CCITT）。这个值会作为除法的操作数。

2. 加载数据：逐字节读取输入数据，并将每个字节与PGR进行异或操作，然后将结果放入CRC寄存器。

3. 现场更新：通过一系列的模运算（模2除法）对CRC寄存器进行位移和异或操作。这是循环冗余检查的关键部分，因为每次处理一个新数据块都会更新 CRC 寄存器。

4. 循环完成：当所有数据都被处理完毕后，最后的CRC寄存器状态就是最终的校验码。

下面是一个简单的C语言函数示例，使用了lookup表来加速模2运算：

unsigned short crc16_table[256];
// 初始化 lookup 表（实际生成过程很复杂，这里省略）
void crc16_update(unsigned char data, unsigned short *crc)
{
    static const int POLYNOMIAL = 0x8408; // x^16 + x^15 + x^2 + 1
    *crc ^= data;
    for (int i = 8; i > 0; i--)
    {
        if (*crc & 0x8000)
            *crc = (*crc << 1) ^ POLYNOMIAL;
        else
            *crc <<= 1;
    }
}

unsigned short crc16(const void *data, size_t len)
{
    unsigned short crc = 0xFFFF; // 初始化 CRC 到最高值
    const unsigned char *ptr = data;
    while(len--) {
        crc16_update(*ptr++, &crc);
    }
    return crc;
}