使⽤C语⾔实现CRC校验的⽅法
CRC(Cyclic Redundancy Check)校验应⽤较为⼴泛，以前为了处理简单，在程序中⼤多数采⽤LRC(Longitudinal Redundancy Check)校验，LRC校验很好理解，编程实现简单。⽤了⼀天时间研究了CRC的C语⾔实现，理解和掌握了基本原理和C语⾔编程。结合⾃⼰的理解简单写下来。
CRC检验的基本思想是利⽤线性编码理论，在发送端根据要传送的k位⼆进制码序列，以⼀定的规则产⽣⼀个检验码r位(就是CRC码)，附在信息后⾯，构成⼀个新的⼆进制码序列数共(k+r)位，最后发送出去。接收端根据同样的规则校验，以确定传送中是否出错。接收端有两种处理⽅式：1、计算k位序列的CRC码，与接收到的CRC⽐较，⼀致则接收正确。2、计算整个k+r 位的CRC码，若为0，则接收正确。
CRC码有多种检验位数，8位、16位、32位等，原理相同。16位的CRC码产⽣的规则是先将要发送的⼆进制序列数左移16位（即乘以2的16次⽅后），除以⼀个多项式，最后所得到的余数就是CRC码。
求CRC码所采⽤的是模2运算法则，即多项式除法中采⽤不带借位的减法运算，运算等同于异或运算。这⼀点要仔细理解，是编程的基础。
CRC-16: (美国⼆进制同步系统中采⽤) G(X) = X16 + X15 + X2 + 1
CRC-CCITT: (由欧洲CCITT推荐) G(X) = X16 + X12 + X5 + 1
CRC-32: G(X) = X32 + X26 + X23 + X22 + X16 +X12 + X11 + X10 + X8 + X7 + X5 + X4 + X2 + X1 + 1
采⽤CRC-CCITT多项式，多项式为0x11021，C语⾔编程时，参与计算为0x1021，这个地⽅得深⼊思考才能体会其中的奥妙，分享⼀下我的思路：当按位计算CRC时，例如计算⼆进制序列为1001 1010 1010 1111时，将⼆进制序列数左移16位，即为1001 1010 1010 1111 (0000 0000 0000 0000)，实际上该⼆进制序列可拆分为1000 0000 0000 0000 (0000 0000 0000 0000) + 000 0000 0000 0000 (0000 0000 0000 0000) + 00 0000 0000 0000 (0000 0000 0000 0000) + 1 0000 0000 0000 (0000 0000 0000 0000) + ……
现在开始分析运算：
<1>对第⼀个⼆进制分序列求余数，竖式除法即为0x10000 ^ 0x11021运算，后⾯的0位保留；
<2>接着对第⼆个⼆进制分序列求余数，将第⼀步运算的余数*2后再和第⼆个⼆进制分序列⼀起对0x11021求余，这⼀步理解应该没什么问题。如果该分序列为0，⽆需计算。
<3>对其余的⼆进制序列求余与上⾯两步相同。
<4>计算到最后⼀位时即为整个⼆进制序列的余数，即为CRC校验码。
该计算⽅法相当于对每⼀位计算，运算过程很容易理解，所占内存少，缺点是⼀位⼀位计算⽐较耗时。
下⾯给出C语⾔实现⽅法：
复制代码代码如下:
unsigned char test[16] = {0x00,0x11,0x22,0x33,0x44,0x55,0x66,0x77,0x88,0x99,0xaa,0xbb,0xcc,0xdd,0xee,0xff}; unsigned char len = 16;
void main( void )
{
unsigned long temp = 0;
unsigned int crc;
unsigned char i;
unsigned char *ptr = test;
while( len-- ) {
for(i = 0x80; i != 0; i = i >> 1) {
temp = temp * 2;
if((temp & 0x10000) != 0)
temp = temp ^ 0x11021;
if((*ptr & i) != 0)
temp = temp ^ (0x10000 ^ 0x11021);
}
ptr++;
}
crc = temp;
printf("0x%x ",crc);
}
上⾯的程序根据运算分析⽽来，很容易理解。为了节约内存空间，我们对程序作进⼀步的简化。分析可知，当⼆进制序列中上⼀位计算的余数第15bit位为1时，即( 上⼀位计算的余数 & 0x8000) != 0，计算本位时，上⼀位余数 * 2后可对0x11021作求余
运算，然后再加上本位计算所得余数。这个很好理解，也就是说，打个⽐⽅，把它看作简单的除法，计算上⼀位时的余数乘以2后，如果⽐较⼤可以当被除数，就再去除除数求余。有⼀点和普通除法不同的是，因为多项式除法中采⽤不带借位的减法运算，所以0x10000也可以被0x11021除，余数并⾮为0x10000,⽽是0x1021。这个⾃⼰动⼿算⼀下就知道了。余数之和也是不带进位的加法运算，即异或。最后还强调⼀点，因为⼆进制序列是左移16位后参与运算的，所以，⼀直算到序列的最后⼀位也是可以被除的，这点⼤家要明⽩。下⾯给出简化后的C语⾔实现。
复制代码代码如下:
unsigned char test[16] ={0x00,0x11,0x22,0x33,0x44,0x55,0x66,0x77,0x88,0x99,0xaa,0xbb,0xcc,0xdd,0xee,0xff}; unsigned char len = 16;
void main( void )
{
unsigned int crc = 0;
unsigned char i;
unsigned char *ptr = test;
while( len-- ) {
for(i = 0x80; i != 0; i = i >> 1) {
if((crc & 0x8000) != 0) {
crc = crc << 1;
crc = crc ^ 0x1021;
}
else {
crc = crc << 1;
}
if((*ptr & i) != 0) {
crc = crc ^ 0x1021;
}
}
ptr++;
}
printf("0x%x ",crc);
}
上⾯这段程序⽹上较为常见，但冇得详细的解释。通过我上⾯的详细分析，如果对此段程序理解还有困
难，可以对⽐⼀下没简化之前的程序，细细品味⼀哈，还是⽐较容易理解的。要是还理解不了，还是从头再看下，我码这么多字容易吗。。。。。按位计算CRC代码⽐较简单，所占内存少，但要⼀位⼀位去计算，下⾯再介绍⼀种按字节查表快速计算CRC的⽅法。
有了上⾯按位计算的知识，理解这个就是⼩case了。还是举前⾯的例⼦：当字节计算CRC时，例如计算⼆进制序列为1001 1010 1010 1111时，即0x9a9f时，将⼆进制序列数左移16位，即为0x9a9f(0 0 0 0)，实际上该⼆进制序列可拆分为0x9a00(0 0 0 0) + 0x009f(0 0 0 0)，分析计算时和上⾯的步骤⼀样，唯⼀不同的是计算中上⼀步的余数CRC要乘以2的⼋次⽅参与下⼀步的运算，这个应该好理解撒。为了简化编程，将计算中的CRC拆成⾼⼋位和低⼋位的形式，⾼⼋位的值直接与本位值相加求余，低⼋位的值乘以2的⼋次⽅后作为余数和计算得的余数相加。为了提⾼计算速度，我们把8位⼆进制序列数的CRC全部计算出来，放在⼀个表中，采⽤查表法可⼤⼤提⾼计算速度。
表是怎么得到的呢？当然是计算出来的，下⾯的程序给出了多项式是0x11021的计算程序。
复制代码代码如下:
void main( void )
{
unsigned int crc = 0;
unsigned char i;
unsigned int j;
for(j = 0; j < 256; j++) {
crc = 0;
for(i = 0x80; i != 0; i = i >> 1) {
if((crc & 0x8000) != 0) {
crc = crc << 1;
crc = crc ^ 0x1021;
}
else {
crc = crc << 1;
}
if((j & i) != 0) {
crc = crc ^ 0x1021;
}
}
printf("0x");
if(crc < 0x10) {
printf("000");
}
c语言编译器怎么用不了else if(crc < 0x100) {
printf("00");
}
else if(crc < 0x1000) {
printf("0");
}
printf("%x, ",crc);
}
}
如果你不是使⽤的0x11021多项式，只需把程序中0x1021换成其他的就可以了。后⾯的⼏个printf语句为了控制使⽣成的表⽐较整齐，如果⽆所谓，可直接⽤printf("0x%x, ",crc)；代替。⽣成的表如下：
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, 0x26d3, 0x36f2, 0x0691, 0x16b0, 0x6657, 0x7676, 0x4615, 0x5634, 0xd94c, 0xc96d, 0xf90e, 0xe92f, 0x99c8,
0x89e9, 0xb98a, 0xa9ab, 0x5844, 0x4865, 0x7806, 0x6827, 0x18c0, 0x08e1, 0x3882, 0x28a3, 0xcb7d, 0xdb5c, 0xeb3f,
0xfb1e, 0x8bf9, 0x9bd8, 0xabbb, 0xbb9a, 0x4a75, 0x5a54, 0x6a37, 0x7a16, 0x0af1, 0x1ad0, 0x2ab3,
0x3a92, 0xfd2e,
0xed0f, 0xdd6c, 0xcd4d, 0xbdaa, 0xad8b, 0x9de8, 0x8dc9, 0x7c26, 0x6c07, 0x5c64, 0x4c45, 0x3ca2, 0x2c83, 0x1ce0,
0x0cc1, 0xef1f, 0xff3e, 0xcf5d, 0xdf7c, 0xaf9b, 0xbfba, 0x8fd9, 0x9ff8, 0x6e17, 0x7e36, 0x4e55, 0x5e74, 0x2e93, 0x3eb2, 0x0ed1, 0x1ef0,
好了，我们来写按字节计算的源程序：
复制代码代码如下:
unsigned char test[16] ={0x00,0x11,0x22,0x33,0x44,0x55,0x66,0x77,0x88,0x99,0xaa,0xbb,0xcc,0xdd,0xee,0xff}; unsigned char len = 16;
unsigned int crc_table[256] ={
x0000, 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, 0x26d3, 0x36f2, 0x0691, 0x16b0, 0x6657, 0x7676, 0x4615, 0x5634, 0xd94c, 0xc96d, 0xf90e, 0xe92f, 0x99c8,
0x89e9, 0xb98a, 0xa9ab, 0x5844, 0x4865, 0x7806, 0x6827, 0x18c0, 0x08e1, 0x3882, 0x28a3, 0xcb7d, 0xdb5c, 0xeb3f, 0xfb1e, 0x8bf9, 0x9bd8, 0xabbb, 0xbb9a, 0x4a75, 0x5a54, 0x6a37, 0x7a16, 0x0af1, 0x1ad0, 0x2ab3, 0x3a92, 0xfd2e,
0xed0f, 0xdd6c, 0xcd4d, 0xbdaa, 0xad8b, 0x9de8, 0x8dc9, 0x7c26, 0x6c07, 0x5c64, 0x4c45, 0x3ca2, 0x2c83, 0x1ce0, 0x0cc1, 0xef1f, 0xff3e, 0xcf5d, 0xdf7c, 0xaf9b, 0xbfba, 0x8fd9, 0x9ff8, 0x6e17, 0x7e36, 0x4e55, 0x5e74, 0x2e93, 0x3eb2, 0x0ed1, 0x1ef0};
void main(void)
{
unsigned int crc = 0;
unsigned char crc_H8;
unsigned char *ptr = test;
while( len-- ) {
crc_H8 = (unsigned char)(crc >> 8);
crc = crc << 8;
crc = crc ^ crc_table[ crc_H8 ^ *ptr];
ptr++;
}
printf("0x%x ",crc);
}
是不是感觉上⾯的表太⼤了，不是很爽，我们再来改进⼀下，按半字节计算，原理我就不赘述了，程序如下：
复制代码代码如下:
unsigned char test[16] ={0x00,0x11,0x22,0x33,0x44,0x55,0x66,0x77,0x88,0x99,0xaa,0xbb,0xcc,0xdd,0xee,0xff}; unsigned char len = 16;
unsigned int crc_table[16] =
{0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50a5, 0x60c6, 0x70e7, 0x8108, 0x9129, 0xa14a, 0xb16b, 0xc18c, 0xd1ad, 0xe1ce, 0xf1ef
};
void main(void)
{
unsigned int crc = 0;
unsigned char crc_H4;
unsigned char *ptr = test;
while( len-- )
{
crc_H4 = (unsigned char)(crc >> 12);
crc = crc << 4;
crc = crc ^ crc_table[ crc_H4 ^ (*ptr >> 4)];
crc_H4 = (unsigned char)(crc >> 12);
crc = crc << 4;
crc = crc ^ crc_table[ crc_H4 ^ (*ptr & 0x0f)];
ptr++;
}
printf("0x%x ",crc);
}
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论