CRC校验源码分析
CRC 根据”权”(即多项表达式)的不同而相应的源代码也有稍许不同。以下是各种常用的权。
CRC8=X8+X5+X4+1
CRC-CCITT=X16+X12+X5+1
CRC16=X16+X15+X5+1
CRC12=X12+X11+X3+X2+1
CRC32=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+1
以下的源程序全部以 CCITT 为例。其实本质都是一样,搞明白一种,其他的都是小菜。
图 1,图 2 说明了 CRC 校验中 CRC 值是如何计算出来的,体现的多项式正是 X16+X12+X5+1。 Serial Data 即是需要校验的数据。从把数据移位开始计算,将数据位(从最低的数据位开始)逐位移入反向耦合移位寄存器(这个名词我也不懂,觉得蛮酷的,就这样写了,嘿)。当所有数据位都这样操作后,计算结束。此时,16 位移位寄存器中的内容就是 CRC 码。
![](../img/eep/emb/emb-25539avx1xtbvlba.jpg)
![](../img/eep/emb/emb-25540i0i3n4lckeo.jpg)
图中进行 XOR 运算的位与多项式的表达相对应。
X5 代表 Bit5,X12 代表 Bit12,1 自然是代表 Bit0,X16 比较特别,是指移位寄存器移出的数据,即图中的DATA OUT。可以这样理解,与数据位做XOR运算的是上次 CRC值的 Bit15。
根据以上说明,可以依葫芦画瓢的写出以下程序。(程序都是在 keil C 7.10 下调试的)
typedef unsigned char uchar;
typedef unsigned int uint;
code uchar crcbuff [] = { 0x00,0x00,0x00,0x00,0x06,0x0d,0xd2,0xe3};
uint crc; // CRC 码
void main(void)
{
uchar *ptr;
crc = 0; // CRC 初值
ptr = crcbuff; // 指向第一个 Byte 数据
crc = crc16l(ptr,8);
while(1);
}
uint crc16l(uchar *ptr,uchar len) // ptr 为数据指针,len 为数据长度
{
uchar i;
while(len--)
{
for(i=0x80; i!=0; i>>=1)
{
if((crc0x8000)!=0) {crc=1; crc^=0x1021;} 1-1
else crc=1; 1-2
if((*ptri)!=0) crc^=0x1021; 1-3
}
ptr++;
}
return(crc);
}
执行结果 crc = 0xdbc0;
程序 1-1,1-2,1-3 可以理解成移位前 crc 的 Bit15 与数据对应的 Bit(*ptri)做 XOR运算,根据此结果来决定是否执行 crc^=0x1021。只要明白两次异或运算与原值相同,就不难理解这个程序。
很多资料上都写了查表法来计算,当时是怎么也没想通。其实蛮简单的。假设通过移位处理了 8 个 bit 的数据,相当于把之前的 CRC 码的高字节(8bit)全部移出,与一个 byte 的数据做XOR 运算,根据运算结果来选择一个值(称为余式),与原来的 CRC 码再做一次 XOR 运算,就可以得到新的 CRC 码。
不难看出,余式有 256 种可能的值,实际上就是 0~255 以 X16+X12+X5+1 为权得到的 CRC码,可以通过函数 crc16l来计算。以1 为例。
code test[]={0x01};
crc = 0;
ptr = test;
crc = crc16l(ptr,1);
执行结果 crc = 1021,这就是1 对应的余式。
进一步修改函数,我这里就懒得写了,可得到 X16+X12+X5+1 的余式表。
code uint crc_ta[256]={ // X16+X12+X5+1 余式表
0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50a5, 0x60c6, 0x70e7,
0x8108, 0x9129, 0xa14a, 0xb16b, 0xc18c, 0xd1ad, 0xe1ce, 0xf1ef,
0x1231, 0x0210, 0x3273, 0x2252, 0x52b5, 0x4294, 0x72f7, 0x62d6,
0x9339, 0x8318, 0xb37b, 0xa35a, 0xd3bd, 0xc39c, 0xf3ff, 0xe3de,
0x2462, 0x3443, 0x0420, 0x1401, 0x64e6, 0x74c7, 0x44a4, 0x5485,
0xa56a, 0xb54b, 0x8528, 0x9509, 0xe5ee, 0xf5cf, 0xc5ac, 0xd58d,
0x3653, 0x2672, 0x1611, 0x0630, 0x76d7, 0x66f6, 0x5695, 0x46b4,
0xb75b, 0xa77a, 0x9719, 0x8738, 0xf7df, 0xe7fe, 0xd79d, 0xc7bc,
0x48c4, 0x58e5, 0x6886, 0x78a7, 0x0840, 0x1861, 0x2802, 0x3823,
0xc9cc, 0xd9ed, 0xe98e, 0xf9af, 0x8948, 0x9969, 0xa90a, 0xb92b,
0x5af5, 0x4ad4, 0x7ab7, 0x6a96, 0x1a71, 0x0a50, 0x3a33, 0x2a12,
0xdbfd, 0xcbdc, 0xfbbf, 0xeb9e, 0x9b79, 0x8b58, 0xbb3b, 0xab1a,
0x6ca6, 0x7c87, 0x4ce4, 0x5cc5, 0x2c22, 0x3c03, 0x0c60, 0x1c41,
0xedae, 0xfd8f, 0xcdec, 0xddcd, 0xad2a, 0xbd0b, 0x8d68, 0x9d49,
0x7e97, 0x6eb6, 0x5ed5, 0x4ef4, 0x3e13, 0x2e32, 0x1e51, 0x0e70,
0xff9f, 0xefbe, 0xdfdd, 0xcffc, 0xbf1b, 0xaf3a, 0x9f59, 0x8f78,
0x9188, 0x81a9, 0xb1ca, 0xa1eb, 0xd10c, 0xc12d, 0xf14e, 0xe16f,
0x1080, 0x00a1, 0x30c2, 0x20e3, 0x5004, 0x4025, 0x7046, 0x6067,
0x83b9, 0x9398, 0xa3fb, 0xb3da, 0xc33d, 0xd31c, 0xe37f, 0xf35e,
0x02b1, 0x1290, 0x22f3, 0x32d2, 0x4235, 0x5214, 0x6277, 0x7256,
0xb5ea, 0xa5cb, 0x95a8, 0x8589, 0xf56e, 0xe54f, 0xd52c, 0xc50d,
0x34e2, 0x24c3, 0x14a0, 0x0481, 0x7466, 0x6447, 0x5424, 0x4405,
0xa7db, 0xb7fa, 0x8799, 0x97b8, 0xe75f, 0xf77e, 0xc71d, 0xd73c,
- 基于赛灵思Spartan-3A DSP的安全视频分析(02-17)
- 关于Linux操作系统的NTFS和内核分析(05-19)
- Linux 2.4.x内核软中断机制(04-06)
- 基于DSP的人脸识别系统设计(04-26)
- 3D图形芯片的算法原理分析(07-16)
- 解析:视频图像智能分析处理技术(08-08)