CRC算法

一、定义

• CRC（Cyclic Redundancy Check）：循环冗余检验；
• 多项式：例如有多项式y=x16+x12+x5+1，可用二进制表达为y=1 0001 0000 0010 0001；
• 模二除法：类似于“算数除法”，但无借位；如100101除以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，计算数据10110011的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 & 0x800000) {
				crc_val = crc_val ^ ((poly | 0x10000) << 7);
			} else {}
			crc_val <<= 1;
		}
	}
	crc_val >>= 8;	//结果在高16位，所以要右移8位

	return crc_val;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

---

部分内容参考于：

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