CRC算法詳解與c源碼

《CRC算法詳解與c源碼》由會員分享，可在線閱讀，更多相關(guān)《CRC算法詳解與c源碼（11頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、文檔供參考，可復(fù)制、編制，期待您的好評與關(guān)注！ CRC計算方法詳解與c源碼 循環(huán)冗余碼（CRC，cyclic redundancy code）校驗技術(shù)是一種十分有效的數(shù)據(jù)傳輸錯誤檢測技術(shù)，能檢驗一位錯、雙位錯、所有的奇數(shù)錯、所有長度小于或等于所用的生成多項式長度的錯誤，在通信系統(tǒng)、控制系統(tǒng)中得到廣泛運用。 計算CRC校驗碼和驗證報文是否有誤，總是由計算機實時地完成的，手工計算僅僅用于說明CRC校驗碼的生成原理。由于實時性的要求，必須使用快捷的計算機計算方法。 CRC校驗原理 在k位信息碼后再拼接r位的校驗碼，報文編碼長度為n位，因此，這種編碼又叫（n，k）

2、碼。對于一個給定的（n，k）碼，可以證明,存在一個最高次冪為n=k+r的多項式G(x)，存在且僅存在一個R次多項式G(x)，使得。其中:m(x)為k次信息多項式，r(x)為r-1次校驗多項式，g(x)稱為生成多項式：。發(fā)送方通過指定的G(x)產(chǎn)生r位的CRC校驗碼，接收方則通過該G(x)來驗證收到的報文碼的CRC校驗碼是否為0。 假設(shè)發(fā)送信息用信息多項式C(X)表示，將C(x)左移r位，則可表示成C(x)*2r，這樣C(x)的右邊就會空出r位校驗碼的位置，做除法（模2除），得到的余數(shù)R就是校驗碼。發(fā)送的CRC編碼是,驗證接收到的報文編碼是否至正確，依然是做模2除：。 CRC的生成多

3、項式 生成多項式的選取應(yīng)滿足以下條件： a、生成多項式的最高位和最低位必須為1。 b、當被傳送信息（CRC碼）任何一位發(fā)生錯誤時，被生成多項式做模2除后，應(yīng)該使余數(shù)不為0。 c、不同位發(fā)生錯誤時，應(yīng)該使余數(shù)不同。 d、對余數(shù)繼續(xù)做模2除，應(yīng)使余數(shù)循環(huán)。 主要的生成多項式G(x)有以下幾種： 名稱 生成多項式 數(shù)值式 簡記式 標準引用 CRC-16 x16+x15+x2+1 0x1’8005 8005 IBM SDLC CRC-CCITT x16+x12+x5+1 0X1’1021 0x1021 ISO H

4、DLC，ITU X.25，V.34/V.41/V.42，PPP-FCS CRC-32 注* 0X1’04C11DB7 0x04C11DB7 ZIP，RAR，IEEE 802 LAN/FDDI，IEEE1394，PPP-FCS 注* x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1 下表中的生成多項式G(x)也常見的： 名稱 生成多項式 數(shù)值式 簡記式 標準引用 CRC-4 x4+x+1 0x1’3 0x3 ITU G.704 CRC-8 x8+x5+x4+1 0x1’31 0x31 C

5、RC-8 x8+x2+x1+1 0x1’07 0x07 CRC-8 x8+x6+x4+x3+x2+x1 0x1’5E 0x5E CRC-12 x12+x11+x3+x2+x+1 0x1’80F 0x80F CRC-32c 注** 0X1’1EDC6F41 0x1EDC6F41 SCTP 注** x32+x28+x27+x26+x25+x23+x22+x20+x19+x18+x14+x13+x11+x10+x9+x8+x6+1 CRC校驗碼的手工計算 CRC的手工計算，就是按普通的二進制豎式除法的格式做模2除法。由于我們需要的是余數(shù)，不必

6、關(guān)心商的大小，所以，可以不用寫出商，而直接進行一次次移位和模2減。具體計算過程是： a. 在信息碼后面加上r（即CRC校驗碼的位數(shù)）個0，作為被除數(shù)，讓除數(shù)（即生成多項式）的最高位1，對齊被除數(shù)的最高位1。 b. 做模二減：如果被除數(shù)最高位為1，減生成多項式，余數(shù)作為中間余數(shù)，否則，不減。 c. 生成多項式右移1位。 e. 反復(fù)進行步驟b，c，直到余數(shù)與a中添加的r個0在位置上對齊，該余數(shù)就是最終余數(shù)，即信息碼的CRC校驗碼。 16位CRC校驗碼的計算機 本節(jié)使用的生成多項式為G16= x16+x12+x5+1=0x11021。在計算機程序中

7、，因為16位rcr校驗碼的生成多項式總寬度為17，而最高位為1，故多占用一個8位寄存器。然而，在模2除的過程中，多項式的最高位1總是與被除數(shù)（或中間余數(shù)）的最左邊的1對齊，而相異或的結(jié)果總是為0。這樣，在程序中可以把生成多項式的最高位1去掉，而只包含后面的16位，例如，將0x11021簡化為0x1021,稱做生成多項式簡化式。 用左移位模2除求余數(shù)時，在異或前，檢查被除數(shù)（或中間余數(shù)）的最高位否為1，如果為1，被除數(shù)（或中間余數(shù)）左移1位，與生成多項式簡化式異或；如果為0，被除數(shù)（或中間余數(shù)）左移1位，不做其它操作?？偟囊莆淮螖?shù)為“被除數(shù)的位數(shù)-除數(shù)（生成多項式簡化式）的位數(shù)”。

8、 1 模擬手工移位計算相 設(shè)n個字節(jié)信息數(shù)據(jù)Bn-1，Bn-2，...，B1，B0，用生成多項式CRC16-CCITT計算crc。 1．設(shè)置一個32bit的變量，例如crc0。Bn-1，Bn-2，Bn-3，Bn-4依次放入crc0。如果n<4，后面的字節(jié)為0。 2．Crc0左移1位，檢查移出位，如果為1，crc與生成多項式簡化式異或，結(jié)果存入crc。如果不為1，則不做異或。 3．上一步重復(fù)8次后，右端空出1個字節(jié)的位置，將下一個信息字節(jié)補入。 4．重復(fù)2，3兩步，直到信息數(shù)據(jù)全部取完。crc右移16位，crc中的內(nèi)容即為CRC校驗榪。

9、 //f1 仿手工，逐位移位 unsigned short f1(unsigned char *mess,unsigned int len) { unsigned int crc0=0; unsigned int div=0x1021*0x10000; unsigned int i,j; for(j=0;j<4;j++) //crc0中至少填入4個信息字節(jié) { crc0=crc0<<8; //信息字節(jié)數(shù)少于4時，用0補齊 if(j

10、 crc0=crc0^*mess; mess++; } } for(j=0;j

11、 if(j+4>16; return crc0; //將32位數(shù)變?yōu)?6位數(shù) } 2 根據(jù)前k 位信息碼的CRC校驗碼移位計算前k+1位信息碼的CRC校驗碼 計算前k位信息碼mk的crc校驗碼： 。式中，rk即為前k位信息碼mk的crc校驗碼。 若在前k位信息碼之后

12、的一位為bi，計算mk+1的crc校驗碼： 。 按位移位計算mk+1的crc校驗碼的方法可表述為：(的余數(shù))+(的余數(shù))。求的余數(shù)，只需要進行1次左移位除，求的余數(shù)，采用查表的方法，默認0的余數(shù)為0，1的余數(shù)為0x1021。 //f2 根據(jù)前n位的crc碼計算前n+1位的crc碼，逐位移位 unsigned short f2(unsigned char *mess,unsigned len) { unsigned int crc0=0; unsigned char i; while(len--!=0)

13、 { for(i=0x80;i!=0;i>>=1) //0的余數(shù)為0,1的余數(shù)為1021 { if((crc0&0x8000)!=0) //先求的余數(shù) { crc0<<=1; crc0^=0x1021; } else crc0<<=1; if((*mess&i)!=0) crc0^=0x1021; //再加上的余數(shù) } mess++; } return cr

14、c0; } 3 根據(jù)前k 字節(jié)信息碼的CRC校驗碼移位計算前k+1字節(jié)信息碼的CRC校驗碼 計算前k字節(jié)信息碼的crc校驗碼： 。式中，Rk即為前k字節(jié)信息碼Mk的crc校驗碼。 若在前k字節(jié)信息碼之后的一字節(jié)為Mi，計算Mk+1的crc校驗碼： 。 按字節(jié)移位計算Mk+1的crc校驗碼的方法表述為：，左移位除8次。 //f3 根據(jù)前n字節(jié)的crc碼計算前n+1字節(jié)的crc碼，逐位移位 unsigned short f3(unsigned cha

15、r *mess,unsigned len) { unsigned short crc0=0; unsigned short i; while(len--) { crc0=crc0^*mess<<8; //信息字節(jié)左移8位與與前次crc校驗碼異或 for(i=0x8000;i!=0x80;i=i>>1) //8次移位除 { if((crc0&0x8000)!=0) { crc0=crc0<<1; crc0=crc0^0x1021

16、; } else crc0=crc0<<1; } mess++; } return crc0; } 4 根據(jù)前k 字節(jié)信息碼的CRC校驗碼查表計算前k+1字節(jié)信息碼的CRC校驗碼 計算前k字節(jié)信息碼的crc校驗碼： Rk即為前k字節(jié)信息碼Mk的crc校驗碼。 。 將Rk分解為高字節(jié)（高8位）和低字節(jié)（低8位）兩部分 如果在Mk之后增加一個字節(jié)Mi，則k+1個字節(jié)的數(shù)據(jù)序列可以表示為：，計算Mk+1的CRC校驗碼

17、： 。 // 按查字節(jié)表計算mk+1的crc校驗碼的語言表述為：(Rkh8+mi)查字節(jié)表+Rk<<8 //f4 根據(jù)前n字節(jié)的crc碼計算前n+1字節(jié)的crc碼，按字節(jié)查表 unsigned short f4(unsigned char *mess,unsigned len) { unsigned short crc0=0; unsigned short crc; unsigned short i; for(i=0;i

18、 { crc=remB[(crc0>>8)^*mess]; //對異或結(jié)果從表中查余數(shù)，得本次中間余數(shù) crc0=crc^(crc0<<8); //與本次中間余數(shù)異或，得本次余數(shù) mess++; } return crc0; } 5 根據(jù)前k 字節(jié)信息碼的CRC校驗碼按高低半字節(jié)查表計算前k+1字節(jié)信息碼的CRC校驗碼 已求得。 對上式繼續(xù)變換： 。 查高低半字節(jié)表計算mk+1的crc校驗碼的語言表述為：查h表+查

19、l表+。 //f5 根據(jù)前n字節(jié)的crc碼計算前n+1字節(jié)的crc碼，分別按高低半字節(jié)查表 unsigned short f5(unsigned char *mess,unsigned len) { unsigned short crc0=0; unsigned short crc; unsigned short i; for(i=0;i>8)^*mess; //前次余數(shù)高字節(jié)與本次數(shù)據(jù)異或 crc0=remBh4[(crc&0xf0)>>4]^remBl4[crc&0x0f

20、]^(crc0<<8); //2個余數(shù)與前次余數(shù)低字節(jié)異或 mess++; } return crc0; } 6 根據(jù)前k 半字節(jié)信息碼的CRC校驗碼查表計算前k+1半字節(jié)信息碼的CRC校驗碼 計算前k半字節(jié)信息碼的crc校驗碼： 。 Rk為16bit余數(shù)，即為CRC校驗碼。 如果在Mk之后增加一個半字節(jié)Mi，則k+1個半字節(jié)的數(shù)據(jù)序列可以表示為：，計算Mk+1的CRC校驗碼： 。 // 查半字節(jié)表計算mk

21、+1的crc校驗碼的語言表述為：查半字節(jié)表+()。示例程序中，每次取1個字節(jié)，所以分兩次分別計算前半字節(jié)和后半字節(jié)。 //f6 根據(jù)前n半字節(jié)的crc碼計算前n+1半字節(jié)的crc碼，按低半字節(jié)查表 unsigned short f6(unsigned char *mess,unsigned int len) { unsigned short crc0=0; unsigned char crc0_m; unsigned char i; for(i=0;i

22、char)(crc0>>12); //得到前次余數(shù)的最高4位 crc0=crc0<<4; //前次余數(shù)右移4位，使最低4位為0 crc0=crc0^rem05[crc0_m^(*mess>>4)]; //相加后得本次中間余數(shù) //一個字節(jié)的低半字節(jié) crc0_m=(unsigned char)(crc0>>12); //得到本次中間余數(shù)的最高4位 crc0=crc0<<4; //本次中間余數(shù)右移

23、4位，使最低4位為0 crc0=crc0^rem05[crc0_m^(*mess&0x0f)]; //相加后得本次余數(shù) mess++; } return crc0; } 7 余數(shù)表計算 計算余數(shù)表采用仿手工算法，以單字節(jié)數(shù)0-255為索引的crc-ccitt的余數(shù)表，其256項，512個字節(jié)。余數(shù)用printf函數(shù)輸出到開發(fā)環(huán)境的不i/o窗口，將余數(shù)表復(fù)制下來，在函數(shù)中建立一個常量數(shù)組，將余數(shù)表粘貼到數(shù)組中。另一個比較好的辦法是，建立一個頭文件，例如crc_32.h，在其中建立一個常量數(shù)組，將余數(shù)表粘貼到數(shù)組中。 unsign

24、ed short crc01(void) { unsigned short remain; unsigned short i,j; for(j=0;j<256;j++) { remain=j<<8; for(i=0;i<8;i++) { if((remain&0x8000)!=0) { remain<<=1; remain^=0x1021; } else remain<<=1; } printf("0x%04x, ",remain);

25、 //16進制輸出，4位寬度，不足4位左端補0 if((j+1)%8==0) printf("\n"); } return 0; } 32位CRC校驗碼的計算機計算 32位CRC校驗碼的算法與16位CRC校驗碼的算法以及c源碼，同出一轍，差別在于crc校驗碼的位數(shù)不同，因而在公式推導(dǎo)和程序的變量設(shè)置上略有不同。鑒于計算32位校驗碼的實際情況，相應(yīng)于6位crc校驗碼的f1-f6，以下僅給出f1，f3，f4，3個公式的推導(dǎo)的示例程序。G32=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1=

26、0x104C11DB7。 1 模擬手工移位計算 //f1 仿手工，逐位移位 unsigned long hand(unsigned char *byt,unsigned int len) { unsigned char buff_ch=0; unsigned long crc=0; unsigned int i,j; for(j=0;j<4;j++) //data中至少填入4個信息字節(jié) { crc<<=8; //信息字節(jié)數(shù)少于4時，用

27、0補齊 if(j

28、80)!=0) crc^=0x00000001; crc^= 0x04C11DB7; } else { crc<<=1; if((buff_ch&0x80)!=0) crc^=0x00000001; } buff_ch<<=1; } if(j+5

29、 //未完則繼續(xù)讀取 byt++; } } return crc; } 2 根據(jù)前k 字節(jié)信息碼的CRC校驗碼移位計算前k+1字節(jié)信息碼的CRC校驗碼 計算前k字節(jié)信息碼的crc校驗碼： 。 式中Rk即為前k字節(jié)信息碼Mk的crc校驗碼。 若在前k字節(jié)信息碼之后的一字節(jié)為Mi，計算Mk+1的crc校驗碼： 。 按字節(jié)移位計算Mk+1的crc校驗碼方法表述為：，左移位除8次。即，單字節(jié)的Mi

30、與4字節(jié)的Rk的最高位字節(jié)相異或，然后，進行左移位除8次。 //f3 unsigned long f3(unsigned char *mess,unsigned int len) { unsigned long crc0=0; unsigned long i; while(len--) { crc0=crc0^(*mess<<24); for(i=0;i<8;i++) { if((crc0&0x80000000)!=0) { crc0<<=1; crc0^=0x04C11DB7;

31、 } else crc0<<=1; } mess++; } return crc0; } 4 根據(jù)前k 字節(jié)信息碼的CRC校驗碼查表計算前k+1字節(jié)信息碼的CRC校驗碼 為了計算32bit的CRC碼，應(yīng)將Mk向左移32位，再除以33bit的生成多項式，余數(shù)即為CRC碼： 。 如果在Mk之后增加一個字節(jié)mi，計算前k+1個字節(jié)的CRC校驗碼： 。 將代入上式，

32、 。 // 查字節(jié)表計算mk+1的crc校驗碼的語言表述為：查字節(jié)表+。 //f2 unsigned long f4(unsigned char *mess,unsigned int len) { unsigned long crc0=0; unsigned long crc_m; unsigned int i; for(i=0;i>24)^*mess]; crc0=crc_m^(crc0<<8); mess++; } ret

33、urn crc0; } 7 余數(shù)表計算 計算余數(shù)表采用仿手工算法，以單字節(jié)數(shù)0-255為索引的crc-32的余數(shù)表，共256項，1024個字節(jié)。程序中dxs=0x1EDC6F41。余數(shù)用printf函數(shù)輸出到開發(fā)環(huán)境下的i/o窗口。在函數(shù)中建立一個常量數(shù)組，將余數(shù)表復(fù)制下來，粘貼到數(shù)組中。或者，建立一個頭文件，例如crc_32.h，在其中建立一個常量數(shù)組，將余數(shù)表粘貼到數(shù)組中。 unsigned long crc01(void) { unsigned long remain; unsigned short i,j; for(j=0;j<256;j++

34、) { remain=j<<24; for(i=0;i<8;i++) { if((remain&0x80000000)!=0) { remain<<=1; remain^=dxs; } else remain<<=1; } printf("0x%08x, ",remain); //16進制輸出，8位寬度，不足8位左端補0 if((j+1)%8==0) printf("\n"); } return 0; } 11 / 11