CRC算法

大家好，欢迎来到IT知识分享网。

一、定义

• CRC（Cyclic Redundancy Check）：循环冗余检验；
• 多项式：例如有多项式y=x16+x12+x5+1，可用二进制表达为y=1 0001 0000 0010 0001；
• 模二除法：类似于“算数除法”，但无借位；如除以1110，结果得到商为11，余数为1，如图：

二、计算原理

1. 确定多项式y；
2. 将需要计算的数据x左移k-1位，得出x1；（k=多项式y的位数）
3. 用模二除法，将数据x1除以多项式y；
4. 计算的k-1位的余数即为数据x的CRC校验值；（计算的次数为数据x的位数）

如：多项式y=x4 + x3 + 1，计算数据的CRC校验值为0100；

三、基本算法（手算）

1. 假设需要对3个字节的数据流(byte[0]、byte[1]、byte[2])做crc16计算；
2. 数据流左移16位，变成：byte[0]、byte[1]、byte[2]、crc[0]、crc[1]；
3. 对40位数据做模二除法；
4. 所得的16位余数为crc16的校验码；

效果类似于：

uint16_t get_crc16(uint8_t* buffer, uint16_t length) { 
    uint32_t data, crc_val = 0; uint8_t i; while (length--) { 
    data = *buffer++; crc_val ^= (data << 16); //异或的具体原因不清楚。猜测是为了将上一个字节的crc校验码承接下去 for (i = 0; i < 8; i++) { 
    if (crc_val & 0x) { 
    crc_val = crc_val ^ ((poly | 0x10000) << 7); } else { 
   } crc_val <<= 1; } } crc_val >>= 8; //结果在高16位，所以要右移8位 return crc_val; } 

四、计算机算法（比特型算法）

1. 假设需要对3个字节的数据流(byte[0]、byte[1]、byte[2])做crc16计算；
2. 数据流左移16位，变成：byte[0]、byte[1]、byte[2]、crc[0]、crc[1]；
3. 取数据流高16位数据（byte[0]、byte[1]），放到16位的寄存器中；
4. 如果寄存器的最高位为1，则寄存器先左移一次（寄存器低位的值从下一个字节获得），再对寄存器和多项式做一次异或计算。否则则寄存器直接左移一次（寄存器低位的值从下一个字节获得）；

为什么变成了先左移一次？如果不先左移，其实会发现如果数据流最高bit为1，最终最高1bit在每轮计算中结果都是0。因此数据流的最高bit其实不需要进行计算，直接右移就行。并且，这个方式需要忽略多项式的最高bit，本来是17位的多项式，只需要16位来表示，那么16位的寄存器刚好可以放下多项式的值。

6. 如果数据流没有全部都移到寄存器，重复上一步；
7. 最后得到的寄存器的值为crc16的校验码；

函数实现如下：

uint16_t get_crc16(uint8_t* buffer, uint16_t length) { 
    uint32_t data, crc_val = 0; uint8_t i; while (length--) { 
    data = *buffer++; crc_val ^= (data << 8); for (i = 0; i < 8; i++) { 
    if (crc_val & 0x8000) { 
    crc_val = (crc_val << 1) ^ poly; } else { 
    crc_val <<= 1; } } } return crc_val; } 

加入输入翻转、输出翻转、输出异或、初始值后的函数实现：

uint32_t get_ref(uint32_t num, uint8_t bit) { 
    uint32_t ret = 0; for (uint8_t i = 0; i < bit; i++) { 
    if (num & 0x01) { 
    ret |= (0x01 << (bit - i - 1)); } else { 
   } num >>= 1; } return ret; } uint16_t get_crc16(uint8_t* buffer, uint16_t length) { 
    uint16_t data, crc_val = init; //初始值 while (length--) { 
    data = *buffer++; if (ref_in) { 
    data = get_ref(data, 8); //计算输入翻转 } else { 
   } crc_val ^= (data << 8); for (uint8_t i = 0; i < 8; i++) { 
    if (crc_val & 0x8000) { 
    crc_val = (crc_val << 1) ^ poly; } else { 
    crc_val <<= 1; } } } if (ref_out) { 
    crc_val = get_ref(crc_val, 16); //计算输出翻转 } else { 
   } crc_val ^= xor_out; //计算输出异或 return crc_val; } 

部分内容参考于：

https://blog.csdn.net/ydyuse/article/details/