CRC算法

这篇具有很好参考价值的文章主要介绍了CRC算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、定义

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

二、计算原理

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

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

三、基本算法（手算）

假设需要对3个字节的数据流(byte[0]、byte[1]、byte[2])做crc16计算；
数据流左移16位，变成：byte[0]、byte[1]、byte[2]、crc[0]、crc[1]；
对40位数据做模二除法；
所得的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;
}

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

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

为什么变成了先左移一次？如果不先左移，其实会发现如果数据流最高bit为1，最终最高1bit在每轮计算中结果都是0。因此数据流的最高bit其实不需要进行计算，直接右移就行。并且，这个方式需要忽略多项式的最高bit，本来是17位的多项式，只需要16位来表示，那么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 << 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;
}