CRC, Cyclic Redundancy Check, 循环冗余校验
1. 基本原理
CRC的本质是除法,把待检验的数据当作一个很大(很长)的被除数,两边选定一个除数(有的文献叫poly),最后得到的余数就是CRC的校验值。
判定方法:
-
将消息和校验和分开。计算消息的校验和(在附加W个零后),并比较两个校验和。
-
把校验值放到数据的结尾,对整批进行校验和(不附加零),看看结果是否为零!
1.1. 为什么用CRC
比较常见的是累加和校验,但是有以下缺点:
-
80
与80 00 .. 00
的计算结果一致,即如果数据里参杂了00
是检测不出来的,对于不定长的检测不友好 -
因为是累加和,所以
80 00
有非常多的组合是校验值相等的,比如70 10
,79 06
等等
那么什么情况下会导致CRC失败呢?
2. 推导前准备
2.1. 无进位加法及减法
CRC算术中的两个数字相加与普通二进制算术中的数字相加相同,除了没有进位。
无进位的加法及减法其实是异或运算(异或,不一样就或在一起:不一样为1,相同为0)
这意味着每对对应的比特确定对应的输出比特,而不参考任何其他比特位置。例如
10011011
+11001010
--------
01010001
--------
加法的4中情况:
0+0=0
0+1=1
1+0=1
1+1=0 (no carry)
减法也是类似的:
10011011
-11001010
--------
01010001
--------
with
0-0=0
0-1=1 (wraparound)
1-0=1
1-1=0
这么一来,我们相当于把加法和减法合并成为了一种算法,或者可以理解为加法和减法这里称为了一种互逆运算,比如我们可以通过加减相同的数量,可以从1010到1001:
1001 = 1010 + 0011
1001 = 1010 - 0011
所以在无进位的加减法里,1010不再可以被视为大于1001;
这么做有什么好处?
你会发现无论多长的数据bit在运算时都不再依赖于前一位或者后一位的状态,这和带进位的加法及带借位的减法不同,你可以理解为运行并行计算:
-
带进位的加法,高位的计算结果需要累加低位结果产生的进位,这就导致了必须要先计算低位,之后才能计算高位;比如下面的例子,如果带进位的话就必须从最右边开始计算,依次算到最左边得到结果。但是如果我们把进位取消,就会发现我从那边开始算都可以,当然也可以多位同时一起算(并行计算)
1011 1011 + 1101 + 1101 ---- ---- 1 1000 (with carry) 0110 (no carry)
-
减法也是如此,不再赘述。
2.2. 无进位乘法
定义了加法后,我们可以进行乘法和除法。乘法是简单的,只不过在加法运算的时候使用XOR就行了
1101
x 1011
----
1101
1101.
0000..
1101...
-------
1111111 Note: The sum uses CRC addition
-------
2.3. 无进位除法
除法也是类似的,只不过有两点需要注意:
-
当除数和被除数的最高位都是1的时候,就当作是
对齐
了,就可以开始XOR运算,不要比较数据大小,比如1001
可以被1011
除,至于商的结果是1或者0,没有人去关注,自己开心就好,因为这个算法压根就不用; -
被除数和除数做减法时,需要使用无进位的减法,即XOR运算;
1 = 商 (nobody cares about the quotient) ______ 1011 ) 1001 除数 =Poly 1011 ---- 0010
3. 算法推导
即使我们知道CRC的算法是基于除法,我们也不能直接使用除法运算,一个是待校验的数据很长,我们没有这么大的寄存器;再则,你知道除法在MCU中是怎么实现的吗?
3.1. 仿人算方法
现在我们假设一个消息数据为1101011011
,选取除数为10011
,使用CRC算法将消息除以poly:
1100001010 = Quotient (nobody cares about the quotient)
_______________
10011 ) 11010110110000 = Augmented message (1101011011 + 0000)
=Poly 10011,,.,,..|.
-----,,.,,|...
10011,.,,|.|.
10011,.,,|...
-----,.,,|.|.
10110...
10011.|.
-----...
010100.
10011.
-----.
01110
00000
-----
1110 = Remainder = THE CHECKSUM!!!!
除数poly的左边的高位的作用其实是给人看的(实际上参与运算的是0011),目的是干掉当前最高位的被除数,本质上是让poly和被除数对齐
,然后开始XOR运算。
那么什么情况算是对齐
呢? 从例子上看,当被除数和除数的最高位都是1时,就算是对齐了。
转换成算法的思路就是,你也可以理解成一长串的数据不断的从右边移位到寄存器中,当寄存器最左边溢出的数值是1的时候,那么当前寄存器的数据就可以和poly异或运算了,用算法表示,大概是这样:
3 2 1 0 Bits
+---+---+---+---+
Pop! <-- | | | | | <----- Augmented message
+---+---+---+---+
1 0 0 1 1 = The Poly
用算法语言描述就是:
寄存器清零
数据最右边补齐W位0 // W是CRC校验值的位数
when(还有数据){
左移寄存器1位,读取数据的下一位到寄存器的bit 0
if (左移寄存器时出现溢出){
寄存器 ^= poly; // 这里的poly=0011,按照上面的例子
}
}
寄存器的值就是校验值了
用C语言:
// CRC8生成多项式
#define POLYNOMIAL 0x07
// 计算CRC8校验值
uint8_t crc8_data(const uint8_t dat8) {
uint8_t crc = dat8;
for (j = 8; j; j--) {
if (crc & 0x80)
crc = (crc << 1) ^ POLYNOMIAL;
else
crc <<= 1;
}
return crc;
}
但是这个方法太笨了,按位进行计算,效率有待提升。
3.2. 使用Table驱动计算CRC4
3.2.1. 4-bit 数据计算
为了方便描述,我们举例W=4
且poly=3
的情况,比如我们计算一个3
的CRC值为5
,我们写成XOR的计算过程:
0011 0000 // 补W=4个零 (值1)
,,10 011 // poly对齐 (值2)
---------
0001 0110
,,,1 0011 // poly对齐 (值3)
---------
0000 0101 // CRC值 (值4)
上面的计算经过了N次迭代运算(其实多少次迭代我们并不关心),等价于
CRC值 = 值1 ^ 值2 ^ 值3
= 值1 ^ (值2 ^ 值3)
= 值1 ^ 查表值 // 令 `查表值` = 值2 ^ 值3
需要注意的是,在CRC计算时,末尾补了4个0,但是我们是清楚的,任何数和0的XOR运算都是其本身,所以补0不会影响最后CRC的值,只不过相当于把CRC的值提取出来。 CRC计算等价于一系列的移位和XOR运算,所以上面的表达式实际上为:
CRC值 = (值1 ^ 0) ^ 值2 ^ 值3
= (值1 ^ 0) ^ (值2 ^ 值3)
= (值1 ^ 0) ^ 查表值
= 值1 ^ 查表值 // 令 `查表值` = 值2 ^ 值3
也就是说,我们可以实现把0~15
的CRC的值先预先算一遍,然后存起来,这样下次再计算就可以直接查表计算,这很好理解。
3.2.2. 8-bit 数据计算
想象一下,一个8-bit的字节是可以拆分成两个4-bit数据的,如果我们可以利用查表的方法,是不是通过两次计算就可以得到一个8-bit的CRC值了?具体要怎么做呢,我们举例W=4
且poly=3
的情况,比如我们计算一个33h
的CRC值,我们写成XOR的计算过程:
0011 0011 0000 // 补W=4个零 (值1)
,,10 011 // poly对齐 (值2)
--------------
0001 0101 0000
,,,1 0011 // poly对齐 (值3)
--------------
0000 0110 0000 // 变回4-bit CRC计算 (值4)
下面的计算我们就熟悉了,回到 计算4-bit数据为 6
的CRC值:
0110 0000 // 补W=4个零
,100 11 // poly对齐
---------
0010 1100
,,10 011 // poly对齐
---------
0000 1010 // CRC值
我们发现一个有意思的事情,原来4-bit数据3
的CRC值是5
,但是当33h
先进行计算高4-bit的CRC值却是6
,和之前的不一样(也幸亏不一样,如果后面无论跟什么数据都一样还有校验干嘛用),这是什么原因?
首先,我们看一下8-bit计算和原来4-bit计算的区别在于末尾补数:
-
4-bit CRC计算时,末尾补的是0,是不影响计算结果的;
-
8-bit CRC计算时,末尾补的是后面跟的低4-bit数据,是会影响原来计算结果的:
为了方便描述,我们把8-bit的
值1
的高4-bit数据记为H4,低4-bit数据记为L4`值4` = `值1` ^ 值2 ^ 值3 = `值1` ^ `查表值` // 令 `查表值` = 值2 ^ 值3 = `(H4<<4 ^ L4)` ^ `查表值` = `(H4<<4)` ^ `查表值` ^ L4 // (H4<<4)其实就是计算H4的CRC值且末尾补0的情况
所以,我们可以得2段4-bit的计算流程:
- 去掉字节的高4-bit值为H4
- 将H4值进行查表计算,得到值TMP1
- 把TMP1的值
异或上
低4位的值L4,得到值TMP2 - 然后用TMP2的值进行查表计算,得到值CRC
4. 算法改进
4.1. CRC8计算
现在我们可以根据CRC4的计算过程类比到CRC8计算,其实主要的区别就是寄存器的位数从4位提升到了8位,一个典型的CRC8计算模型如下,现在你应该可以读懂了。
#include <stdio.h>
#include <stdint.h>
// CRC8生成多项式
#define POLYNOMIAL 0x07
// 初始化CRC8查找表
void init_crc8_table(void) {
uint8_t i, j;
for (i = 0; i < 256; i++) {
uint8_t crc = i;
for (j = 8; j; j--) {
if (crc & 0x80)
crc = (crc << 1) ^ POLYNOMIAL;
else
crc <<= 1;
}
crc8_table[i] = crc;
}
}
// 计算CRC8校验值
uint8_t crc8(const void *data, size_t len) {
const uint8_t *byte = data;
uint8_t crc = 0x00;
for (; len > 0; len--) {
crc = crc8_table[(crc ^ *byte++) & 0xFF];
}
return crc;
}
int main(int argc, char *argv[]) {
int fd;
uint8_t buffer;
size_t bytes_read;
uint8_t crc;
if (argc != 2) {
fprintf(stderr, "Usage: %s filename\n", argv);
exit(1);
}
fd = open(argv, O_RDONLY);
bytes_read = read(fd, buffer, sizeof(buffer));
crc = crc8(buffer, bytes_read);
printf("CRC: 0x%02X\n", crc);<q refer="1"></q><span class="_q_s_"></span>
close(fd);
return 0;
}
4.2. CRC8计算-改进型
上面的算法还是不够好,因为Table的表太大了占用256字节,对于FLASH空间紧张的MCU来说不怎么友好,能不能把一个8-bit数据拆分成两次4-bit数据的计算,这样是不是就可以搞成16
字节的表了?我们来试一下!
实际上使用了32字节
idx | L4 | H4 | H4说明 |
---|---|---|---|
0 | 0 | 0 | (L4<<4) ^ 07*0 |
1 | 07 | 70 | (L4<<4) ^ 07*0 |
2 | 0E | E0 | (L4<<4) ^ 07*0 |
3 | 09 | 90 | (L4<<4) ^ 07*0 |
4 | 1C | C7 | (L4<<4) ^ 07 |
5 | 1B | B7 | (L4<<4) ^ 07 |
6 | 12 | 27 | (L4<<4) ^ 07 |
7 | 15 | 57 | (L4<<4) ^ 07 |
8 | 38 | 89 | (L4<<4) ^ ((07<<1) ^ 07) |
9 | 3F | F9 | (L4<<4) ^ ((07<<1) ^ 07) |
A | 36 | 69 | (L4<<4) ^ ((07<<1) ^ 07) |
B | 31 | 19 | (L4<<4) ^ ((07<<1) ^ 07) |
C | 24 | 4E | (L4<<4) ^ (07<<1) |
D | 23 | 3E | (L4<<4) ^ (07<<1) |
E | 2A | AE | (L4<<4) ^ (07<<1) |
F | 2D | DE | (L4<<4) ^ (07<<1) |
// 计算CRC8校验值
uint8_t crc8(const void *data, size_t len) {
const uint8_t *byte = data;
uint8_t crc = 0x00;
for (; len > 0; len--) {
crc = crc8_table_h4[(crc ^ *byte)>>4] ^
crc8_table_l4[(crc ^ *byte) & 0xF] ;
byte++;
}
return crc;
}
验证:
-
CRC8计算单字节
crc8(88) = 38 ^ 89 = B1
-
CRC8计算多字节
crc8(8888) = crc8(B1 ^ 88) = crc8(39) = 90^3F=AF crc8(1234) = crc8(crc8(12) ^ 34) = crc8(7E ^ 34 = 4A) = C7^36=F1
4.3. CRC16计算-改进型
进一步地,我们可不可以使用相同的原理实现CRC16算法?W=16, poly=8005
idx | X[3:0] | X[7:4] | X[7:4]说明 | X[11:8] | X[11:8]说明 | X[15:12] | X[15:12]说明 |
---|---|---|---|---|---|---|---|
0 | 0 | 0 | |||||
1 | 8005 | 8063 | X[3:0]<<4 ^ 8033 | 8603 | X[3:0]<<8 ^ 8303 | E003 | X[3:0]<<12 ^ B003 |
2 | 800F | 80C3 | X[3:0]<<4 ^ 8033 | 8C03 | X[3:0]<<8 ^ 8303 | 4003 | X[3:0]<<12 ^ B003 |
3 | 0A | 00A0 | X[3:0]<<4 | A00 | X[3:0]<<8 | A000 | X[3:0]<<12 |
4 | 801B | 8183 | X[3:0]<<4 ^ 8033 | 9803 | X[3:0]<<8 ^ 8303 | 8006 | X[3:0]<<12 ^ B003 ^ 8005 |
5 | 1E | 1E0 | X[3:0]<<4 | 1E00 | X[3:0]<<8 | 6005 | X[3:0]<<12 ^ 8005 |
6 | 14 | 140 | X[3:0]<<4 | 1400 | X[3:0]<<8 | C005 | X[3:0]<<12 ^ 8005 |
7 | 8011 | 8123 | X[3:0]<<4 ^ 8033 | 9203 | X[3:0]<<8 ^ 8303 | 2006 | X[3:0]<<12 ^ B003 ^ 8005 |
8 | 8033 | 8303 | X[3:0]<<4 ^ 8033 | B003 | X[3:0]<<8 ^ 8303 | 8009 | X[3:0]<<12 ^ B003 ^ A |
9 | 36 | 360 | X[3:0]<<4 | 3600 | X[3:0]<<8 | 600A | X[3:0]<<12 ^ A |
A | 3C | 3C0 | X[3:0]<<4 | 3C00 | X[3:0]<<8 | C00A | X[3:0]<<12 ^ A |
B | 8039 | 83A3 | X[3:0]<<4 ^ 8033 | BA03 | X[3:0]<<8 ^ 8303 | 2009 | X[3:0]<<12 ^ B003 ^ A |
C | 28 | 280 | X[3:0]<<4 | 2800 | X[3:0]<<8 | 000F | X[3:0]<<12 ^ 800F |
D | 802D | 82E3 | X[3:0]<<4 ^ 8033 | AE03 | X[3:0]<<8 ^ 8303 | E00C | X[3:0]<<12 ^ B003 ^ 800F |
E | 8027 | 8243 | X[3:0]<<4 ^ 8033 | A403 | X[3:0]<<8 ^ 8303 | 400C | X[3:0]<<12 ^ B003 ^ 800F |
F | 22 | 220 | X[3:0]<<4 | 2200 | X[3:0]<<8 | A00F | X[3:0]<<12 ^ 800F |
验证:
-
CRC16计算双字节
比如计算
ABCD
的CRC16:crc16(A000) = C00A crc16(0B00) = BA03 crc16(00C0) = 0280 crc16(000D) = 802D 故crc16(ABCD) = C00A ^ BA03 ^ 0280 ^ 802D = F8A4
-
CRC16计算四字节
如果数据是连贯的呢,比如
ABCD
crc(ABCD) = F8A4 crc(ABCD1234) = crc(F8A4 ^ 1234) = crc(EA90) = 400C ^ 3C00 ^ 360 ^ 0 = 7F6C