CRC算法詳解與c源碼

文檔供參考，可復(fù)制、編制，期待您的好評(píng)與關(guān)注！ CRC計(jì)算方法詳解與c源碼 循環(huán)冗余碼（CRC，cyclic redundancy code）校驗(yàn)技術(shù)是一種十分有效的數(shù)據(jù)傳輸錯(cuò)誤檢測(cè)技術(shù)，能檢驗(yàn)一位錯(cuò)、雙位錯(cuò)、所有的奇數(shù)錯(cuò)、所有長(zhǎng)度小于或等于所用的生成多項(xiàng)式長(zhǎng)度的錯(cuò)誤，在通信系統(tǒng)、控制系統(tǒng)中得到廣泛運(yùn)用。 計(jì)算CRC校驗(yàn)碼和驗(yàn)證報(bào)文是否有誤，總是由計(jì)算機(jī)實(shí)時(shí)地完成的，手工計(jì)算僅僅用于說明CRC校驗(yàn)碼的生成原理。由于實(shí)時(shí)性的要求，必須使用快捷的計(jì)算機(jī)計(jì)算方法。CRC校驗(yàn)原理 在k位信息碼后再拼接r位的校驗(yàn)碼，報(bào)文編碼長(zhǎng)度為n位，因此，這種編碼又叫（n，k）碼。對(duì)于一個(gè)給定的（n，k）碼，可以證明,存在一個(gè)最高次冪為n=k+r的多項(xiàng)式G(x)，存在且僅存在一個(gè)R次多項(xiàng)式G(x)，使得。其中:m(x)為k次信息多項(xiàng)式，r(x)為r-1次校驗(yàn)多項(xiàng)式，g(x)稱為生成多項(xiàng)式：。發(fā)送方通過指定的G(x)產(chǎn)生r位的CRC校驗(yàn)碼，接收方則通過該G(x)來驗(yàn)證收到的報(bào)文碼的CRC校驗(yàn)碼是否為0。 假設(shè)發(fā)送信息用信息多項(xiàng)式C(X)表示，將C(x)左移r位，則可表示成C(x)*2r，這樣C(x)的右邊就會(huì)空出r位校驗(yàn)碼的位置，做除法（模2除），得到的余數(shù)R就是校驗(yàn)碼。發(fā)送的CRC編碼是,驗(yàn)證接收到的報(bào)文編碼是否至正確，依然是做模2除：。CRC的生成多項(xiàng)式 生成多項(xiàng)式的選取應(yīng)滿足以下條件： a、生成多項(xiàng)式的最高位和最低位必須為1。 b、當(dāng)被傳送信息（CRC碼）任何一位發(fā)生錯(cuò)誤時(shí)，被生成多項(xiàng)式做模2除后，應(yīng)該使余數(shù)不為0。 c、不同位發(fā)生錯(cuò)誤時(shí)，應(yīng)該使余數(shù)不同。 d、對(duì)余數(shù)繼續(xù)做模2除，應(yīng)使余數(shù)循環(huán)。 主要的生成多項(xiàng)式G(x)有以下幾種：名稱生成多項(xiàng)式數(shù)值式簡(jiǎn)記式標(biāo)準(zhǔn)引用CRC-16x16+x15+x2+10x180058005IBM SDLCCRC-CCITTx16+x12+x5+10X110210x1021ISO HDLC，ITU X.25，V.34/V.41/V.42，PPP-FCSCRC-32注*0X104C11DB70x04C11DB7ZIP，RAR，IEEE 802 LAN/FDDI，IEEE1394，PPP-FCS注* x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1 下表中的生成多項(xiàng)式G(x)也常見的：名稱生成多項(xiàng)式數(shù)值式簡(jiǎn)記式標(biāo)準(zhǔn)引用CRC-4x4+x+10x130x3ITU G.704CRC-8x8+x5+x4+10x1310x31CRC-8x8+x2+x1+10x1070x07CRC-8x8+x6+x4+x3+x2+x10x15E0x5ECRC-12x12+x11+x3+x2+x+10x180F0x80FCRC-32c注*0X11EDC6F410x1EDC6F41SCTP注* x32+x28+x27+x26+x25+x23+x22+x20+x19+x18+x14+x13+x11+x10+x9+x8+x6+1CRC校驗(yàn)碼的手工計(jì)算 CRC的手工計(jì)算，就是按普通的二進(jìn)制豎式除法的格式做模2除法。由于我們需要的是余數(shù)，不必關(guān)心商的大小，所以，可以不用寫出商，而直接進(jìn)行一次次移位和模2減。具體計(jì)算過程是： a. 在信息碼后面加上r（即CRC校驗(yàn)碼的位數(shù)）個(gè)0，作為被除數(shù)，讓除數(shù)（即生成多項(xiàng)式）的最高位1，對(duì)齊被除數(shù)的最高位1。 b. 做模二減：如果被除數(shù)最高位為1，減生成多項(xiàng)式，余數(shù)作為中間余數(shù)，否則，不減。 c. 生成多項(xiàng)式右移1位。 e. 反復(fù)進(jìn)行步驟b，c，直到余數(shù)與a中添加的r個(gè)0在位置上對(duì)齊，該余數(shù)就是最終余數(shù)，即信息碼的CRC校驗(yàn)碼。16位CRC校驗(yàn)碼的計(jì)算機(jī) 本節(jié)使用的生成多項(xiàng)式為G16= x16+x12+x5+1=0x11021。在計(jì)算機(jī)程序中，因?yàn)?6位rcr校驗(yàn)碼的生成多項(xiàng)式總寬度為17，而最高位為1，故多占用一個(gè)8位寄存器。然而，在模2除的過程中，多項(xiàng)式的最高位1總是與被除數(shù)（或中間余數(shù)）的最左邊的1對(duì)齊，而相異或的結(jié)果總是為0。這樣，在程序中可以把生成多項(xiàng)式的最高位1去掉，而只包含后面的16位，例如，將0x11021簡(jiǎn)化為0x1021,稱做生成多項(xiàng)式簡(jiǎn)化式。 用左移位模2除求余數(shù)時(shí)，在異或前，檢查被除數(shù)（或中間余數(shù)）的最高位否為1，如果為1，被除數(shù)（或中間余數(shù)）左移1位，與生成多項(xiàng)式簡(jiǎn)化式異或；如果為0，被除數(shù)（或中間余數(shù)）左移1位，不做其它操作?？偟囊莆淮螖?shù)為“被除數(shù)的位數(shù)-除數(shù)（生成多項(xiàng)式簡(jiǎn)化式）的位數(shù)”。 1 模擬手工移位計(jì)算相 設(shè)n個(gè)字節(jié)信息數(shù)據(jù)Bn-1，Bn-2，.，B1，B0，用生成多項(xiàng)式CRC16-CCITT計(jì)算crc。 1設(shè)置一個(gè)32bit的變量，例如crc0。Bn-1，Bn-2，Bn-3，Bn-4依次放入crc0。如果n<4，后面的字節(jié)為0。 2Crc0左移1位，檢查移出位，如果為1，crc與生成多項(xiàng)式簡(jiǎn)化式異或，結(jié)果存入crc。如果不為1，則不做異或。 3上一步重復(fù)8次后，右端空出1個(gè)字節(jié)的位置，將下一個(gè)信息字節(jié)補(bǔ)入。 4重復(fù)2，3兩步，直到信息數(shù)據(jù)全部取完。crc右移16位，crc中的內(nèi)容即為CRC校驗(yàn)榪。/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個(gè)信息字節(jié) crc0=crc0<<8; /信息字節(jié)數(shù)少于4時(shí)，用0補(bǔ)齊 if(j<len) crc0=crc0*mess; mess+; for(j=0;j<len;j+) /左移位（len×8)次 for(i=0;i<8;i+) /逐位異或 if(crc0&0x80000000)!=0) crc0=crc0<<1; crc0=crc0div; else crc0=crc0<<1; if(j+4<len) /信息字節(jié)是否已經(jīng)讀取完畢 crc0=crc0*mess; mess+; crc0=crc0>>16; return crc0; /將32位數(shù)變?yōu)?6位數(shù) 2 根據(jù)前k 位信息碼的CRC校驗(yàn)碼移位計(jì)算前k+1位信息碼的CRC校驗(yàn)碼 計(jì)算前k位信息碼mk的crc校驗(yàn)碼： 。式中，rk即為前k位信息碼mk的crc校驗(yàn)碼。 若在前k位信息碼之后的一位為bi，計(jì)算mk+1的crc校驗(yàn)碼： 。 按位移位計(jì)算mk+1的crc校驗(yàn)碼的方法可表述為：(的余數(shù))+(的余數(shù))。求的余數(shù)，只需要進(jìn)行1次左移位除，求的余數(shù)，采用查表的方法，默認(rèn)0的余數(shù)為0，1的余數(shù)為0x1021。/f2 根據(jù)前n位的crc碼計(jì)算前n+1位的crc碼，逐位移位unsigned short f2(unsigned char *mess,unsigned len) unsigned int crc0=0; unsigned char i; while(len-!=0) 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 crc0; 3 根據(jù)前k 字節(jié)信息碼的CRC校驗(yàn)碼移位計(jì)算前k+1字節(jié)信息碼的CRC校驗(yàn)碼 計(jì)算前k字節(jié)信息碼的crc校驗(yàn)碼： 。式中，Rk即為前k字節(jié)信息碼Mk的crc校驗(yàn)碼。 若在前k字節(jié)信息碼之后的一字節(jié)為Mi，計(jì)算Mk+1的crc校驗(yàn)碼： 。 按字節(jié)移位計(jì)算Mk+1的crc校驗(yàn)碼的方法表述為：，左移位除8次。/f3 根據(jù)前n字節(jié)的crc碼計(jì)算前n+1字節(jié)的crc碼，逐位移位unsigned short f3(unsigned char *mess,unsigned len) unsigned short crc0=0; unsigned short i; while(len-) crc0=crc0*mess<<8; /信息字節(jié)左移8位與與前次crc校驗(yàn)碼異或 for(i=0x8000;i!=0x80;i=i>>1) /8次移位除 if(crc0&0x8000)!=0) crc0=crc0<<1; crc0=crc00x1021; else crc0=crc0<<1; mess+; return crc0; 4 根據(jù)前k 字節(jié)信息碼的CRC校驗(yàn)碼查表計(jì)算前k+1字節(jié)信息碼的CRC校驗(yàn)碼 計(jì)算前k字節(jié)信息碼的crc校驗(yàn)碼： Rk即為前k字節(jié)信息碼Mk的crc校驗(yàn)碼。 。 將Rk分解為高字節(jié)（高8位）和低字節(jié)（低8位）兩部分 如果在Mk之后增加一個(gè)字節(jié)Mi，則k+1個(gè)字節(jié)的數(shù)據(jù)序列可以表示為：，計(jì)算Mk+1的CRC校驗(yàn)碼： 。 / 按查字節(jié)表計(jì)算mk+1的crc校驗(yàn)碼的語言表述為：(Rkh8+mi)查字節(jié)表+Rk<<8/f4 根據(jù)前n字節(jié)的crc碼計(jì)算前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<len;i+) crc=remB(crc0>>8)*mess; /對(duì)異或結(jié)果從表中查余數(shù)，得本次中間余數(shù) crc0=crc(crc0<<8); /與本次中間余數(shù)異或，得本次余數(shù) mess+; return crc0; 5 根據(jù)前k 字節(jié)信息碼的CRC校驗(yàn)碼按高低半字節(jié)查表計(jì)算前k+1字節(jié)信息碼的CRC校驗(yàn)碼 已求得。 對(duì)上式繼續(xù)變換： 。 查高低半字節(jié)表計(jì)算mk+1的crc校驗(yàn)碼的語言表述為：查h表+查l表+。/f5 根據(jù)前n字節(jié)的crc碼計(jì)算前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<len;i+) crc=(crc0>>8)*mess; /前次余數(shù)高字節(jié)與本次數(shù)據(jù)異或 crc0=remBh4(crc&0xf0)>>4remBl4crc&0x0f(crc0<<8); /2個(gè)余數(shù)與前次余數(shù)低字節(jié)異或 mess+; return crc0; 6 根據(jù)前k 半字節(jié)信息碼的CRC校驗(yàn)碼查表計(jì)算前k+1半字節(jié)信息碼的CRC校驗(yàn)碼 計(jì)算前k半字節(jié)信息碼的crc校驗(yàn)碼： 。 Rk為16bit余數(shù)，即為CRC校驗(yàn)碼。 如果在Mk之后增加一個(gè)半字節(jié)Mi，則k+1個(gè)半字節(jié)的數(shù)據(jù)序列可以表示為：，計(jì)算Mk+1的CRC校驗(yàn)碼： 。 / 查半字節(jié)表計(jì)算mk+1的crc校驗(yàn)碼的語言表述為：查半字節(jié)表+()。示例程序中，每次取1個(gè)字節(jié)，所以分兩次分別計(jì)算前半字節(jié)和后半字節(jié)。/f6 根據(jù)前n半字節(jié)的crc碼計(jì)算前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<len;i+) /一個(gè)字節(jié)的高半字節(jié) crc0_m=(unsigned char)(crc0>>12); /得到前次余數(shù)的最高4位 crc0=crc0<<4; /前次余數(shù)右移4位，使最低4位為0 crc0=crc0rem05crc0_m(*mess>>4); /相加后得本次中間余數(shù) /一個(gè)字節(jié)的低半字節(jié) crc0_m=(unsigned char)(crc0>>12); /得到本次中間余數(shù)的最高4位 crc0=crc0<<4; /本次中間余數(shù)右移4位，使最低4位為0 crc0=crc0rem05crc0_m(*mess&0x0f); /相加后得本次余數(shù) mess+; return crc0; 7 余數(shù)表計(jì)算 計(jì)算余數(shù)表采用仿手工算法，以單字節(jié)數(shù)0-255為索引的crc-ccitt的余數(shù)表，其256項(xiàng)，512個(gè)字節(jié)。余數(shù)用printf函數(shù)輸出到開發(fā)環(huán)境的不i/o窗口，將余數(shù)表復(fù)制下來，在函數(shù)中建立一個(gè)常量數(shù)組，將余數(shù)表粘貼到數(shù)組中。另一個(gè)比較好的辦法是，建立一個(gè)頭文件，例如crc_32.h，在其中建立一個(gè)常量數(shù)組，將余數(shù)表粘貼到數(shù)組中。unsigned 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); /16進(jìn)制輸出，4位寬度，不足4位左端補(bǔ)0 if(j+1)%8=0) printf("n"); return 0;32位CRC校驗(yàn)碼的計(jì)算機(jī)計(jì)算 32位CRC校驗(yàn)碼的算法與16位CRC校驗(yàn)碼的算法以及c源碼，同出一轍，差別在于crc校驗(yàn)碼的位數(shù)不同，因而在公式推導(dǎo)和程序的變量設(shè)置上略有不同。鑒于計(jì)算32位校驗(yàn)碼的實(shí)際情況，相應(yīng)于6位crc校驗(yàn)碼的f1-f6，以下僅給出f1，f3，f4，3個(gè)公式的推導(dǎo)的示例程序。G32=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1=0x104C11DB7。 1 模擬手工移位計(jì)算/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個(gè)信息字節(jié) crc<<=8; /信息字節(jié)數(shù)少于4時(shí)，用0補(bǔ)齊 if(j<len) crc=*byt; byt+; if(j<len) buff_ch=*byt; byt+; for(j=0;j<len;j+) /左移位（len×8)次 for(i=0;i<8;i+) /逐位異或 if(crc&0x80000000)!=0) crc<<=1; if(buff_ch&0x80)!=0) crc=0x00000001; crc= 0x04C11DB7; else crc<<=1; if(buff_ch&0x80)!=0) crc=0x00000001; buff_ch<<=1; if(j+5<len) /信息字節(jié)是否已經(jīng)讀取完畢 buff_ch=*byt; /未完則繼續(xù)讀取 byt+; return crc; 2 根據(jù)前k 字節(jié)信息碼的CRC校驗(yàn)碼移位計(jì)算前k+1字節(jié)信息碼的CRC校驗(yàn)碼 計(jì)算前k字節(jié)信息碼的crc校驗(yàn)碼： 。 式中Rk即為前k字節(jié)信息碼Mk的crc校驗(yàn)碼。 若在前k字節(jié)信息碼之后的一字節(jié)為Mi，計(jì)算Mk+1的crc校驗(yàn)碼： 。 按字節(jié)移位計(jì)算Mk+1的crc校驗(yàn)碼方法表述為：，左移位除8次。即，單字節(jié)的Mi與4字節(jié)的Rk的最高位字節(jié)相異或，然后，進(jìn)行左移位除8次。/f3unsigned 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; else crc0<<=1; mess+; return crc0; 4 根據(jù)前k 字節(jié)信息碼的CRC校驗(yàn)碼查表計(jì)算前k+1字節(jié)信息碼的CRC校驗(yàn)碼 為了計(jì)算32bit的CRC碼，應(yīng)將Mk向左移32位，再除以33bit的生成多項(xiàng)式，余數(shù)即為CRC碼：。 如果在Mk之后增加一個(gè)字節(jié)mi，計(jì)算前k+1個(gè)字節(jié)的CRC校驗(yàn)碼：。 將代入上式， 。 / 查字節(jié)表計(jì)算mk+1的crc校驗(yàn)碼的語言表述為：查字節(jié)表+。/f2unsigned long f4(unsigned char *mess,unsigned int len) unsigned long crc0=0; unsigned long crc_m; unsigned int i; for(i=0;i<len;i+) crc_m=rem(crc0>>24)*mess; crc0=crc_m(crc0<<8); mess+; return crc0; 7 余數(shù)表計(jì)算 計(jì)算余數(shù)表采用仿手工算法，以單字節(jié)數(shù)0-255為索引的crc-32的余數(shù)表，共256項(xiàng)，1024個(gè)字節(jié)。程序中dxs=0x1EDC6F41。余數(shù)用printf函數(shù)輸出到開發(fā)環(huán)境下的i/o窗口。在函數(shù)中建立一個(gè)常量數(shù)組，將余數(shù)表復(fù)制下來，粘貼到數(shù)組中?；蛘撸⒁粋€(gè)頭文件，例如crc_32.h，在其中建立一個(gè)常量數(shù)組，將余數(shù)表粘貼到數(shù)組中。unsigned long crc01(void) unsigned long remain; unsigned short i,j; for(j=0;j<256;j+) 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進(jìn)制輸出，8位寬度，不足8位左端補(bǔ)0 if(j+1)%8=0) printf("n"); return 0;11 / 11