CRC算法,从原理到实现

CRC,一种基于有限域GF(2)的多项式环的Hash算法。在GF(2)中,多项式系数只有0、1,加减运算等同于异或(XOR)运算,乘除运算与一般多项式运算一致(合并同类项时需要注意为XOR运算)

abstract.jpg

概述

在GF(2)中,多项式系数只有0、1,加减运算等同于异或(XOR)运算,乘除运算与一般多项式运算一致(合并同类项时需要注意为XOR运算)。在CRC-n算法中,有M(x)·x^n^=Q(x)·G(x)+R(x),M(x)为m位的数据,G(x)为一个GF(2)的n+1项的生成多项式(Poly),M(x)·x^n^ 则是通过在数据M(x)后添加n个0形成的对应的m+n位多项式,而R(x)即为M(x)·x^n^ 除以G(x)的n位余数——即CRC校验码,Q(x)为商,直接丢弃。通过比较两次计算产生的Signature是否一致判断故障的发生

基本原理

假定M(x)=11100110,G(x)=x^3^ + x + 1,其中n=3,则M(x)·x^n^=11100110000,将G(x)多项式中的各项系数取出,按降幂排列所对应的数据Poly=1011,然后对其进行除法运算:

Fig1.png

所得n位余数即为CRC——100

根据定义可以建立一个简单的CRC实现算法,模型如下图所示:
1)建立一个长度为r的CRC Register,并初始化为0
2)在M(x)后添加r个0形成M(x)·x^n^
3)将CRC Register左移一位,将M(x)·x^n^的MSB移入CRC Register的Bit 0
4)第3步中的从CRC Register移出的数,如果是1,则计算,CRC Register=Poly XOR CRC Register
5)重复第3步,直到M(x)·x^n^全部移入CRC Register
6) CRC Register即为CRC校验值

Fig2.png

算法实现

Table Driven Algorithm

根据定义所建立的算法模型存在明显缺陷,按位移动处理效率低下,为此我们探索如何实现更大处理单元的算法。这次我们以CRC-32为例,按照前面的算法思路构建的模型如下图所示:

Fig3.png

设CRC Register中的Byte 3依次为:t7 t6 t5 t4 t3 t2 t1 t0,Poly中的Bit31-Bit24依次为:g7 g6 g5 g4 g3 g2 g1 g0,根据1.3.2可知,在第1次迭代中,CRC Register的MSB:t7将会决定Poly与CRC Register的异或,如果t7=1,这就会发生,反之就不会发生;在第2次迭代中,CRC Register的MSB:t6 XOR (t7*g7) 将会决定本次Poly与CRC Register的异或是否发生,即t7、t6控制第2XOR操作;同理,在第3次迭代中,CRC Register的MSB也是通过t7、t6、t5决定,即t7、t6、t5控制第3次XOR操作。故我们可以得出下述结论:k次以后的迭代的最高位的值,可以由寄存器的前k位计算得到。根据这个结论,我们可以一次性取出CRC Register的Byte 3,提前计算出8次迭代后的寄存器余式,因为高位终将会在迭代中被移出,我们只需要关心余式即可。同时XOR运算满足结合律:A XOR B XOR C = A XOR (B XOR C)

Fig4.png

上图即为Byte 3全部迭代移出的示意图,根据结合律可以看出,我们可以依据Byte 3直接确定8次异或的与否及Poly的偏移量,从而提前计算出不同偏移量的Poly间XOR的值,令其为A,易知A的高8位和Byte 3一定相等,Reg向左移出btye3,从M(x)·x^n^读取一个byte放在byte 0,最后将A的低32位与Reg完成XOR操作。为避免与字节边界发生冲突,我们采用字节的整数倍——字节(1 byte)、字(2 byte)、双字(4 byte),故一般不采用4bit作为处理单元。由于一个字节的取值是有限的——256种,我们只要提前计算一个字节全部的A值保存到表中。运行时以byte值为索引,直接从表里取出即可

至此我们完成基于1 byte为处理单元的Table Driven,算法模型如下图所示:
1)建立一个长度为r的CRC Register,并初始化为0
2)在M(x)后添加r个0形成M(x)·x^n^
3)将CRC Register左移一个byte,从M(x)·x^n^读入一个byte至CRC Register的byte 0中
4)以第3步中的从CRC Register移出的byte为index,从表中取出对应的n位宽的值,将该值与CRC Register进行XOR
5)重复第3步,直到M(x)·x^n^全部移入CRC Register
6) CRC Register即为CRC校验值

Fig5.png

Direct Table Algorithm

在上述的两种算法中,我们每次都需要在M(x)后添加n个0,其并不参与运算,目的只是为了将M(x)的全部推入CRC Register而已,并且在有些情境下在M(x)后添0操作并不总是能够实现的,故通过改进计算步骤有了直接表法,避免了对原始数据的添0操作
算法流程,算法模型如下图所示:
1)建立一个长度为r的CRC Register,按照Init值对其初始化
2)将CRC Register左移一个byte,从M(x)左移一个byte,两者进行XOR
3)第2步中XOR后的值作为index,从表中取出对应的n位宽的值,将该值与CRC Register进行XOR
4)重复第2步,直到M(x)全部取出
5) CRC Register即为CRC校验值

Fig6.png

Reflected Direct Table Algorithm

在Direct Table算法中,当RefIn、RefOut为True,每次都需要对数据做颠倒操作,很麻烦。为此产生了Reflected Direct Table算法,该算法改变了CRC Register的移动方向,而不需要对M(x)做任何处理,按字节顺序读取即可,算法模型如下图所示

算法流程如下:
1)建立一个长度为r的CRC Register,按照Init值对其初始化
2)将CRC Register右移一个byte,从M(x)左移一个byte,两者进行XOR
3)第2步中XOR后的值作为index,从表中取出对应的n位宽的值,将该值与CRC Register进行XOR
4)重复第2步,直到M(x)全部取出
5) CRC Register即为CRC校验值

Fig7.png

CRC模型

Name: CRC标准

Width: 生成的CRC的位宽

Poly: 生成多项式,一般采用十六进制简记,长度为width+1,由于其最高位恒为1,故记法中不体现出来(例如:x^16^+x^12^+x^5^+1记为0x1021)

Init: 初始值,如果数据前添加了若干个前导零,在前述算法中,一般是检测不到的,故通过改变CRC Register中的预设值,以实现对该类型错误的检测。在Direct Table算法中用Init初始化CRC Register即可,在Table Driven算法中,不可以直接用Init初始化CRC Register,因为其等同于在原始数据前插入了Init,必须要先把CRC Register设为0,等M(x)·x^n^移动n/8次后,即CRC Register的预设值0全部移出时,再将Init值异或进CRC Register。完成Init操作

Xorout: 结果异或值,所有计算完成后将CRC Register与Xorout进行异或作,作为最后的校验值

RefIn: 输入反转,这是一个布尔值,如果为False,则每个字节内的位顺序保持不变,即Bit 7为MSB,Bit0为LSB。如果为True,则将需要每个字节内的位顺序颠倒,即Bit 7为LSB,Bit0为MSB。这个约定在硬件CRC中是合理的,因为在串口通讯中硬件一般默认先发送字节的Bit 0,最后发送Bit 7

RefOut: 输出反转,这是一个布尔值,如果为False,则在计算结束后,直接进入Xorout环节,如果为True,则在计算结束后,将CRC Register进行颠倒后,再进入Xorout环节。注意,和RefIn颠倒字节内的位顺序不同的是,这个是将CRC Register的值作为一个整体颠倒,即Bit n到Bit0进行颠倒

实现

针对常见常用的下述CRC给出了实现方法,以供参考

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
#include <stdio.h>

typedef unsigned char uint8_t;
typedef signed char int8_t;
typedef unsigned short int uint16_t;
typedef signed short int int16_t;
typedef unsigned int uint32_t;
typedef signed int int32_t;
typedef unsigned long long int uint64_t;
typedef signed long long int int64_t;

uint16_t Table16[256];
uint32_t Table32[256];
uint32_t Table32Ref[256];

/******************** CRC-16/CITI False Model ********************/
/*
Name : "CRC-16/CITT FALSE"
Width : 16
Poly : 1021
Init : FFFF
RefIn : False
RefOut : False
XorOut : 0000
*/
/***************************************************************************/
uint16_t CRC16_CITIFalse(uint8_t *ptr, uint32_t len);
uint8_t GenerateT16(void);


/******************** CRC-32 Model *******************************/
/*
Name : "CRC-32"
Width : 32
Poly : 04C11DB7
Init : FFFFFFFF
RefIn : True
RefOut : True
XorOut : FFFFFFFF
*/
/***************************************************************************/
uint32_t CRC32(const uint8_t* ptr, uint32_t len);
uint8_t GenerateT32(void);
uint32_t CRC32Ref(const uint8_t* ptr, uint32_t len);
uint8_t GenerateT32Ref(void);
uint32_t ExchBitOrder(uint32_t data, uint8_t bitnum);

uint8_t main(void)
{
uint8_t Table16Flag = 0;
uint8_t Table32Flag = 0;
uint8_t Table32RefFlag = 0;

if (0 == Table16Flag)
{
printf("Calc Table16 Start...\r\n");
GenerateT16();
printf("Calc Table16 Over!\r\n");
Table16Flag = 1;
}
if (0 == Table32Flag)
{
printf("\r\nCalc Table32 Start...\r\n");
GenerateT32();
printf("Calc Table32 Over!\r\n");
Table32Flag = 1;
}
if (0 == Table32RefFlag)
{
printf("\r\nCalc Table32Ref Start...\r\n");
GenerateT32Ref();
printf("Calc Table32Ref Over!\r\n");
Table32Flag = 1;
}

uint8_t test1[4] = { 0,0,0,0};
uint8_t test2[3] = { 0xF2,0x01,0x83};
uint8_t test3[9] = { 0x33,0x22,0x55,0xAA,0xBB,0xCC,0xDD,0xEE,0xFF};
uint8_t test4[4] = { 0xFF,0xFF,0xFF,0xFF};
uint8_t test5[4] = { 0x31,0x32,0x33,0x34 };

printf("\r\n CRC-16/CITT-FALSE Test\r\n");
printf("____________________________________________________\r\n");
printf(" TestData Expecte Actual\r\n");
printf("____________________________________________________\r\n");
printf("0x00000000 0x84C0 0x%X\r\n", CRC16_CITIFalse(test1,4));
printf("0xF20183 0xD374 0x%X\r\n", CRC16_CITIFalse(test2,3));
printf("0x332255AABBCCDDEEFF 0xF53F 0x%X\r\n", CRC16_CITIFalse(test3,9));
printf("0xFFFFFFFF 0x1D0F 0x%X\r\n", CRC16_CITIFalse(test4,4));
printf("0x31323334 0x5349 0x%X\r\n", CRC16_CITIFalse(test5,4));
printf("____________________________________________________\r\n");


printf("\r\n CRC-32 Test\r\n");
printf("Algorithm : Direct Table\r\n");
printf("__________________________________________________________\r\n");
printf(" TestData Expecte Actual\r\n");
printf("__________________________________________________________\r\n");
printf("0x00000000 0x2144DF1C 0x%X\r\n", CRC32(test1, 4));
printf("0xF20183 0x24AB9D77 0x%X\r\n", CRC32(test2, 3));
printf("0x332255AABBCCDDEEFF 0xB0AE863D 0x%X\r\n", CRC32(test3, 9));
printf("0xFFFFFFFF 0xFFFFFFFF 0x%X\r\n", CRC32(test4, 4));
printf("0x31323334 0x9BE3E0A3 0x%X\r\n", CRC32(test5, 4));
printf("__________________________________________________________\r\n");

printf("\r\n CRC-32 Test\r\n");
printf("Algorithm : Reflected Direct Table\r\n");
printf("__________________________________________________________\r\n");
printf(" TestData Expecte Actual\r\n");
printf("__________________________________________________________\r\n");
printf("0x00000000 0x2144DF1C 0x%X\r\n", CRC32Ref(test1, 4));
printf("0xF20183 0x24AB9D77 0x%X\r\n", CRC32Ref(test2, 3));
printf("0x332255AABBCCDDEEFF 0xB0AE863D 0x%X\r\n", CRC32Ref(test3, 9));
printf("0xFFFFFFFF 0xFFFFFFFF 0x%X\r\n", CRC32Ref(test4, 4));
printf("0x31323334 0x9BE3E0A3 0x%X\r\n", CRC32Ref(test5, 4));
printf("__________________________________________________________\r\n");

return 0;
}

uint16_t CRC16_CITIFalse(const uint8_t *ptr,uint32_t len) // Algorithm:Direct Table
{
uint16_t CrcReg = 0xFFFF;
uint8_t TopByte = 0;
uint8_t index = 0;
while (0!=len)
{
TopByte = (uint8_t)((CrcReg & 0xFF00) >> 8);
CrcReg = (uint16_t)((uint32_t)CrcReg << 8);
index = (uint8_t)(*ptr) ^ TopByte;
CrcReg = CrcReg^Table16[index];
ptr++;
len--;
}
return CrcReg;
}

uint8_t GenerateT16(void)
{
uint16_t i=0;
uint16_t pxp = 0;
for (i = 0; i < 256; i++)
{
pxp = 0;
for (int8_t nbit = 7; nbit > -1; nbit--)
{
if (((i >> nbit) ^ (pxp >> 15)) & 0x0001)
{
//待测数据位和pxp高位相异,poly进行XOR
pxp = (uint16_t)((uint32_t)pxp << 1) ^ 0X1021;
}
else
{
//待测数据位和pxp高位相同,poly不进行XOR
pxp = (uint16_t)((uint32_t)pxp << 1);
}
}
Table16[i] = pxp;
}
return 0;
}

uint32_t CRC32(const uint8_t* ptr,uint32_t len) // Algorithm : Direct Table
{
uint32_t CrcReg = 0xFFFFFFFF;
uint8_t TopByte = 0;
uint8_t index = 0;
uint8_t tmp = 0;
while (0!=len)
{
tmp = ExchBitOrder((uint8_t)(*ptr),8); // RefIn : True
TopByte = (uint8_t)((CrcReg & 0xFF000000) >> 24);
CrcReg = (uint32_t)(CrcReg << 8);
index = (uint8_t)tmp ^ TopByte;
CrcReg = CrcReg^Table32[index];
ptr++;
len--;
}
CrcReg = ExchBitOrder(CrcReg,32); // RefOut : True
CrcReg = CrcReg ^ 0xFFFFFFFF; // XorOut : FFFFFFFF
return CrcReg;
}

uint8_t GenerateT32(void)
{
uint16_t i = 0;
uint32_t pxp = 0;
for (i = 0; i < 256; i++)
{
pxp = 0;
for (int8_t nbit = 7; nbit > -1; nbit--)
{
if (((i >> nbit) ^ (pxp >> 31)) & 0x00000001)
{
pxp = (pxp << 1) ^ 0x04C11DB7; //待测数据位和pxp高位相异,poly进行XOR
}
else
{
pxp = pxp << 1; //待测数据位和pxp高位相同,poly不进行XOR
}
}
Table32[i] = pxp;
}
return 0;
}

// Algorithm : Reflected Direct Table
uint32_t CRC32Ref(const uint8_t* ptr, uint32_t len)
{
uint32_t CrcReg = 0xFFFFFFFF;
uint8_t TopByte = 0;
uint8_t index = 0;
uint8_t tmp = 0;
while (0 != len)
{
tmp = *ptr; // RefIn : True X
TopByte = (uint8_t)(CrcReg & 0x000000FF);
CrcReg = (uint32_t)(CrcReg >> 8);
index = (uint8_t)tmp ^ TopByte;
CrcReg = CrcReg^Table32Ref[index];
ptr++;
len--;
}
// CrcReg = ExchBitOrder(CrcReg, 32); // RefOut : True X
CrcReg = CrcReg ^ 0xFFFFFFFF; // XorOut : FFFFFFFF
return CrcReg;
}

uint8_t GenerateT32Ref(void)
{
uint16_t i = 0;
uint32_t pxp = 0;
uint8_t iRef = 0;
for (i = 0; i < 256; i++)
{
pxp = 0;
for (int8_t nbit = 7; nbit > -1; nbit--)
{
if (((i >> nbit) ^ (pxp >> 31)) & 0x0001)
{
pxp = (pxp << 1) ^ 0x04C11DB7; //待测数据位和pxp高位相异,poly进行XOR
}
else
{
pxp = pxp << 1; //待测数据位和pxp高位相同,poly不进行XOR
}
}
iRef = (uint8_t)ExchBitOrder(i, 8);
pxp = ExchBitOrder(pxp, 32);
Table32Ref[iRef] = pxp;
}
return 0;
}

uint32_t ExchBitOrder(uint32_t data, uint8_t bitnum)
{
uint32_t bar = 0;
for (uint8_t j = 0; j < bitnum; j++)
{
if ((data >> j) & 0x01)
{
bar = (1 << (bitnum - 1 - j)) | bar;
}
}
return bar;
}

Fig8.png

0%