crc32算法校验
㈠ CRC32 算法
为了提高编码效率，在实际运用中大多采用查表法来完成CRC-32校验，下面是产生CRC-32校验吗的子程序。
unsigned long crc_32_tab[256]={
0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3,0x0edb8832,…, 0x5a05df1b, 0x2d02ef8d
};//事先计算出的参数表，共有256项，未全部列出。
unsigned long GenerateCRC32(char xdata * DataBuf,unsigned long len)
{
unsigned long oldcrc32;
unsigned long crc32;
unsigned long oldcrc;
unsigned int charcnt;
char c,t;
oldcrc32 = 0x00000000; //初值为0
charcnt=0;
while (len--) {
t= (oldcrc32 >> 24) & 0xFF; //要移出的字节的值
oldcrc=crc_32_tab[t]; //根据移出的字节的值查表
c=DataBuf[charcnt]; //新移进来的字节值
oldcrc32= (oldcrc32 << 8) | c; //将新移进来的字节值添在寄存器末字节中
oldcrc32=oldcrc32^oldcrc; //将寄存器与查出的值进行xor运算
charcnt++;
}
crc32=oldcrc32;
return crc32;
}
参数表可以先在PC机上算出来，也可在程序初始化时完成。下面是用于计算参数表的c语言子程序，在Visual C++ 6.0下编译通过。
#include <stdio.h>
unsigned long int crc32_table[256];
unsigned long int ulPolynomial = 0x04c11db7;
unsigned long int Reflect(unsigned long int ref, char ch)
{ unsigned long int value(0);
// 交换bit0和bit7，bit1和bit6，类推
for(int i = 1; i < (ch + 1); i++)
{ if(ref & 1)
value |= 1 << (ch - i);
ref >>= 1; }
return value;
}
init_crc32_table()
{ unsigned long int crc,temp;
// 256个值
for(int i = 0; i <= 0xFF; i++)
{ temp=Reflect(i, 8);
crc32_table[i]= temp<< 24;
for (int j = 0; j < 8; j++){
unsigned long int t1,t2;
unsigned long int flag=crc32_table[i]&0x80000000;
t1=(crc32_table[i] << 1);
if(flag==0)
t2=0;
else
t2=ulPolynomial;
crc32_table[i] =t1^t2 ; }
crc=crc32_table[i];
crc32_table[i] = Reflect(crc32_table[i], 32);
}
}
㈡ 求助crc32的原理
数据结构算法:CRC32算法实现原理
简而言之，CRC是一个数值。该数值被用于校验数据的正确性。CRC数值简单地说就是通过让你需要做处理的数据除以一个常数而得到的余数。当你得到这个数值后你可以将这个数值附加到你的数据后，当数据被传送到其他地方后，取出原始数据(可能在传送过程中被破坏)与附加的CRC数值，然后将这里的原始数据除以之前那个常数(约定好的)然后得到新的CRC值。比较两个CRC值是否相等即可确认你的数据是否在传送过程中出现错误。
那么，如何让你的数据除以一个常数？方法是对你的数据进行必要的编码处理，逐字节处理成数字。
那么这个常数是什么？你不必关注它是什么，也不需要关注它是如何获得的。当你真的要动手写一个CRC的实现算法时，我可以告诉你，CRC的理论学家会告诉你。不同长度的常数对应着不同的CRC实现算法。当这个常数为32位时，也就是这里所说的CRC32。
以上内容你不必全部理解，因为你需要查阅其他资料来获取CRC完整的理论介绍。
The mathematics behind CRC ?
很多教科书会把CRC与多项式关联起来。这里的多项式指的是系数为0或1的式子，例如：a0 + a1*x + a2*x^2 + ... + an*x^n。其中a0, a1, ..., an要么为0要么为1。我们并不关注x取什么值。
(如果你要关注，你可以简单地认为x为2) 这里把a0, a1, ..., an的值取出来排列起来，就可以表示比特流。例如 1 + x + x^3所表示的比特流就为：1101。部分资料会将这个顺序颠倒，这个很正常。
什么是生成多项式？
所谓的生成多项式，就是上面我所说的常数。注意，在这里，一个多项式就表示了一个比特流，也就是一堆1、0，组合起来最终就是一个数值。例如CRC32算法中，这个生成多项式为：c(x) = 1 + x + x^2 + x^4 + x^5 + x^7 + x^8 + x^10 + x^11 + x^12 + x^16 + x^22 + x^23 + x^26 + x^32。其对应的数字就为：(x^32在实际计算时隐含给出，因此这里没有包含它的系数)，也就是0xEDB88320(多项式对应的数字可能颠倒，颠倒后得到的是0x04C11DB7，其实也是正确的)。
由此可以看出，CRC值也可以看成我们的数据除以一个生成多项式而得到的余数。
如何做这个除法？
套用大部分教科书给出的计算方法，因为任何数据都可以被处理成纯数字，因此，在某种程度上说，我们可以直接开始这个除法。尽管事实上这并不是标准的除法。例如，我们的数据为1101011011(方便起见我直接给二进制表示了，从这里也可以看出，CRC是按bit进行计算的)，给定的生成多项式(对应的值)为10011。通常的教科书会告诉我们在进行这个除法前，会把我们的数据左移几位(生成多项式位数-1位)，从而可以容纳将来计算得到的CRC值(我上面所说的将CRC值附加到原始数据后)。但是为什么要这样做？我也不知道。(不知道的东西不能含糊过)那么，除法就为：
1100001010
_______________
10011 ) 11010110110000 附加了几个零的新数据
10011......... 这里的减法(希望你不至于忘掉小学算术)是一个异或操作
-----.........
10011........
10011........
-----........
00001....... 逐bit计算
00000.......
-----.......
00010......
00000......
-----......
00101.....
00000.....
-----.....
01011....
00000....
-----....
10110...
10011...
-----...
01010..
00000..
-----..
10100.
10011.
-----.
01110
00000
-----
1110 = 这个余数也就是所谓的CRC值，通常又被称为校验值。
希望进行到这里，你可以获取更多关于CRC的感性认识。而我们所要做的，也就是实现一个CRC的计算算法。说白了，就是提供一个程序，给定一段数据，以及一个生成多项式(对于CRC32算法而言该值固定)，然后计算得出上面的1110余数。
㈢ crc32算法原理
一、循环冗余码校验英文名称为Cyclical Rendancy Check,简称CRC.
它是利用除法及余数的原理来作错误侦测（Error Detecting）的.实际应用时,发送装置计算出CRC值并随数据一同发送给接收装置,接收装置对收到的数据重新计算CRC并与收到的CRC相比较,若两个CRC值不同,则说明数据通讯出现错误.
根据应用环境与习惯的不同,CRC又可分为以下几种标准：
①CRC-12码；
②CRC-16码；
③CRC-CCITT码；
④CRC-32码.
CRC-12码通常用来传送6-bit字符串.
CRC-16及CRC-CCITT码则用是来传送8-bit字符,其中CRC-16为美国采用,而CRC-CCITT为欧洲国家所采用.
CRC-32码大都被采用在一种称为Point-to-Point的同步传输中.
下面以最常用的CRC-16为例来说明其生成过程.
CRC-16码由两个字节构成,在开始时CRC寄存器的每一位都预置为1,然后把CRC寄存器与8-bit的数据进行异或(异或：二进制运算 相同为0,不同为1；0^0=0;0^1=1;1^0=1;1^1=0),
之后对CRC寄存器从高到低进行移位,在最高位（MSB）的位置补零,而最低位（LSB,移位后已经被移出CRC寄存器）如果为1,则把寄存器与预定义的多项式码进行异或,否则如果LSB为零,则无需进行异或.重复上述的由高至低的移位8次,第一个8-bit数据处理完毕,用此时CRC寄存器的值与下一个8-bit数据异或并进行如前一个数据似的8次移位.所有的字符处理完成后CRC寄存器内的值即为最终的CRC值.
下面为CRC的计算过程：
1．设置CRC寄存器,并给其赋值FFFF(hex).
2．将数据的第一个8-bit字符与16位CRC寄存器的低8位进行异或,并把结果存入CRC寄存器.
3．CRC寄存器向右移一位,MSB补零,移出并检查LSB.
4．如果LSB为0,重复第三步；若LSB为1,CRC寄存器与多项式码相异或.
5．重复第3与第4步直到8次移位全部完成.此时一个8-bit数据处理完毕.
6．重复第2至第5步直到所有数据全部处理完成.
7．最终CRC寄存器的内容即为CRC值.
常用的CRC循环冗余校验标准多项式如下：
CRC(16位) = X16+X15+X2+1
CRC(CCITT) = X16+X12 +X5+1
CRC(32位) = X32+X26+X23+X16+X12+X11+X10+ X8+X7+X5+X4+X2+X+1
以CRC(16位)多项式为例,其对应校验二进制位列为1 1000 0000 0000 0101.
注意：这儿列出的标准校验多项式都含有(X+1)的多项式因子；各多项式的系数均为二进制数,所涉及的四则运算仍遵循对二取模的运算规则.
(注：对二取模的四则运算指参与运算的两个二进制数各位之间凡涉及加减运算时均进行XOR异或运算,即：1 XOR 1=0,0 XOR 0=0,1 XOR 0=1,0 XOR 1=1,即相同为0,不同为1)