C語言實現(xiàn)CRC16校驗

1、CRC(CyclicRedundancyCheck)校驗應用較為廣泛，以前為了處理簡單，在程序中大多數(shù)采用LRC(LongitudinalRedundancyCheck)校驗，LRC校驗很好理解，編程實現(xiàn)簡單。用了一天時間研究了CRC的C語言實現(xiàn)，理解和掌握了基本原理和C語言編程。結(jié)合自己的理解簡單寫下來。1、CRC簡介CRC檢驗的基本思想是利用線性編碼理論，在發(fā)送端根據(jù)要傳送的k位二進制碼序列，以一定的規(guī)則產(chǎn)生一個檢驗碼r位(就是CRC碼)，附在信息后面，構(gòu)成一個新的二進制碼序列數(shù)共(k+r)位，最后發(fā)送出去。接收端根據(jù)同樣的規(guī)則校驗，以確定傳送中是否出錯。接收端有兩種處理方式：1、計算k位

2、序列的CRC碼，與接收到的CRC比較，一致則接收正確。2、計算整個k+r位的CRC碼，若為0，則接收正確。CRC碼有多種檢驗位數(shù)，8位、16位、32位等，原理相同。16位的CRC碼產(chǎn)生的規(guī)則是先將要發(fā)送的二進制序列數(shù)左移16位（即乘以2的16次方后），除以一個多項式，最后所得到的余數(shù)就是CRC碼。求CRC碼所采用的是模2運算法則，即多項式除法中采用不帶借位的減法運算，運算等同于異或運算。這一點要仔細理解，是編程的基礎。CRC-16:(美國二進制同步系統(tǒng)中采用)CRC-CCITT:(由歐洲CCITT推薦)CRC-32:+X1+12、按位計算CRC采用CRC-CCITT多項式，多項式為0x1102

3、1，C語言編程時，參與計算為0x1021，這個地方得深入思考才能體會其中的奧妙，分享一下我的思路：當按位計算CRC時，例如計算二進制序列為1001101010101111時，將二進制序列數(shù)左移16位，即為1001101010101111(0000000000000000)，實際上該二進制序列可拆分為1000000000000000(0000000000000000)+000000000000000(0000000000000000)+00000000000000(0000000000000000)+1000000000000(0000000000000000)+現(xiàn)在開始分析運算：<1&g

4、t;對第一個二進制分序列求余數(shù)，豎式除法即為0x100000x11021運算，后面的0位保留；<2>接著對第二個二進制分序列求余數(shù)，將第一步運算的余數(shù)*2后再和第二個二進制分序列一起對0x11021求余，這一步理解應該沒什么問題。如果該分序列為0，無需計算。序列求余與上面兩步相同。<4>計算到最后一位時即為整個二進制序列的余數(shù)，即為CRC校驗碼。該計算方法相當于對每一位計算，運算過程很容易理解，所占內(nèi)存少，缺點是一位一位計算比較1G(X)=X16+X15+X2+1G(X)=X16+X12+X5+1G(X)=X32+X26+X23+X22+X16+X12+X11+X10+

5、X8+X7+X5+X4+X2<3>對其余的二進制耗時。下面給出C語言實現(xiàn)方法：unsignedchartest16=0x00,0x11,0x22,0x33,0x44,0x55,0x66,0x77,0x88,0x99,0xaa,0xbb,0xcc,0xdd,0xee,0xff;unsignedcharlen=16;voidmain(void)unsignedlongtemp=0;unsignedintcrc;unsignedchari;unsignedchar*ptr=test;while(len-)for(i=0x80;i!=0;i=i>>1)temp=temp*2;i

6、f(temp&0x10000)!=0)temp=temp0x11021;if(*ptr&i)!=0)temp=temp(0x100000x11021);ptr+;crc=temp;printf("0x%x",crc);上面的程序根據(jù)運算分析而來，很容易理解。為了節(jié)約內(nèi)存空間，我們對程序作進一步的簡化。分析可知，當二進制序列中上一位計算的余數(shù)第15bit位為1時，即(上一位計算的余數(shù)&0x8000)!=0，計算本位時，上一位余數(shù)*2后可對0x11021作求余運算,然后再加上本位計算所得余數(shù)。這個很好理解，也就是說，打個比方，把它看作簡單的除法，計算上一

7、位時的余數(shù)乘以2后，如果比較大可以當被除數(shù)，就再去除除數(shù)求余。有一點和普通除法不同的是，因為多項式除法中采用不帶借位的減法運算，所以0x10000也可以被0x11021除，余數(shù)并非為0x10000,而是0x1021。這個自己動手算一下就知道了。余數(shù)之和也是不帶進位的加法運算，即異或。最后還強調(diào)一點，因為二進制序列是左移16位后參與運算的，所以，一直算到序列的最后一位也是可以被除的，這點大家要明白。下面給出簡化后的C語言實現(xiàn)。unsignedchartest16=0x00,0x11,0x22,0x33,0x44,0x55,0x66,0x77,0x88,0x99,0xaa,0xbb,0xcc,0x

8、dd,0xee,0xff;unsignedcharlen=16;voidmain(void)unsignedintcrc=0;unsignedchari;unsignedchar*ptr=test;while(len-)for(i=0x80;i!=0;i=i>>1)if(crc&0x8000)!=0)crc=crc<<1;crc=crc0x1021;elsecrc=crc<<1;if(*ptr&i)!=0)crc=crc0x1021;ptr+;printf("0x%x",crc);上面這段程序網(wǎng)上較為常見，但冇得詳細的解釋

9、。通過我上面的詳細分析，如果對此段程序理解還有困難，可以對比一下沒簡化之前的程序，細細品味一哈，還是比較容易理解的。要是還理解不了，還是從頭再看下，我碼這么多字容易嗎。按位計算CRC代碼比較簡單，所占內(nèi)存少，但要一位一位去計算，下面再介紹一種按字節(jié)查表快速計算CRC的方法。3、按字節(jié)計算CRC有了上面按位計算的知識，理解這個就是小case了。還是舉前面的例子：當字節(jié)計算CRC時，例如計算二進制序列為1001101010101111時，即0x9a9f時，將二進制序列數(shù)左移16位，即為0x9a9f(0000)，實際上該二進制序列可拆分為0x9a00(0000)+0x009f(0000)，分析計算時

10、和上面的步驟一樣，唯一不同的是計算中上一步的余數(shù)CRC要乘以2的八次方參與下一步的運算，這個應該好理解撒。為了簡化編程，將計算中的CRC拆成高八位和低八位的形式，高八位的值直接與本位值相加求余，低八位的值乘以2的八次方后作為余數(shù)和計算得的余數(shù)相加。為了提高計算速度，我們把8位二進制序列數(shù)的CRC全部計算出來，放在一個表中，采用查表法可大大提高計算速度。表是怎么得到的呢？當然是計算出來的，下面的程序給出了多項式是0x11021的計算程序。voidmain(void)unsignedintcrc=0;unsignedchari;unsignedintj;for(j=0;j<256;j+)cr

11、c=0;for(i=0x80;i!=0;i=i>>1)if(crc&0x8000)!=0)crc=crc<<1;crc=crc0x1021;elsecrc=crc<<1;if(j&i)!=0)crc=crc0x1021;printf("0x");if(crc<0x10)printf("000");elseif(crc<0x100)printf("00");elseif(crc<0x1000)printf("0");printf("%x,

12、",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,0x

13、9339,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,0

14、x78a7,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,

15、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

16、,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,0xe92

17、f,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,0x1c

18、e0,0x0cc1,0xef1f,0xff3e,0xcf5d,0xdf7c,0xaf9b,0xbfba,0x8fd9,0x9ff8,0x6e17,0x7e36,0x4e55,0x5e74,0x2e93,0x3eb2,0x0ed1,0x1ef0,好了，我們來寫按字節(jié)計算的源程序：unsignedchartest16=0x00,0x11,0x22,0x33,0x44,0x55,0x66,0x77,0x88,0x99,0xaa,0xbb,0xcc,0xdd,0xee,0xff;unsignedcharlen=16;unsignedintcrc_table256=0x0000,0x1021,0x204

19、2,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,0xf5

20、cf,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,0xd

21、bfd,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