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)