CRC校驗源碼學(xué)習

CRC 根據”權”(即多項表達式)的不同而相應的源代碼也有稍許不同。以下是各種常用的權。

　　CRC8=X8+X5+X4+1

　　CRC-CCITT=X16+X12+X5+1

　　CRC16=X16+X15+X5+1

　　CRC12=X12+X11+X3+X2+1

　　CRC32=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+1

　　以下的源程序全部以 CCITT 為例。其實(shí)本質(zhì)都是一樣，搞明白一種，其他的都是小菜。

　　圖 1，圖 2 說(shuō)明了 CRC 校驗中 CRC 值是如何計算出來(lái)的，體現的多項式正是 X16+X12+X5+1。 Serial Data 即是需要校驗的數據。從把數據移位開(kāi)始計算，將數據位(從最低的數據位開(kāi)始)逐位移入反向耦合移位寄存器(這個(gè)名詞我也不懂，覺(jué)得蠻酷的，就這樣寫(xiě)了，嘿)。當所有數據位都這樣操作后，計算結束。此時(shí)，16 位移位寄存器中的內容就是 CRC 碼。

　　圖中進(jìn)行 XOR 運算的位與多項式的表達相對應。

　　X5 代表 Bit5，X12 代表 Bit12，1 自然是代表 Bit0，X16 比較特別，是指移位寄存器移出的數據，即圖中的DATA OUT?？梢赃@樣理解，與數據位做XOR運算的是上次 CRC值的 Bit15。

　　根據以上說(shuō)明，可以依葫蘆畫(huà)瓢的寫(xiě)出以下程序。(程序都是在 keil C 7.10 下調試的)

　　typedef unsigned char uchar;

　　typedef unsigned int uint;

　　code uchar crcbuff [] = { 0x00,0x00,0x00,0x00,0x06,0x0d,0xd2,0xe3};

　　uint crc; // CRC 碼

　　void main(void)

　　{

　　uchar *ptr;

　　crc = 0; // CRC 初值

　　ptr = crcbuff; // 指向第一個(gè) Byte 數據

　　crc = crc16l(ptr,8);

　　while(1);

　　}

　　uint crc16l(uchar *ptr,uchar len) // ptr 為數據指針，len 為數據長(cháng)度

　　{

　　uchar i;

　　while(len--)

　　{

　　for(i=0x80; i!=0; i>>=1)

　　{

　　if((crc0x8000)!=0) {crc=1; crc^=0x1021;} 1-1

　　else crc=1; 1-2

　　if((*ptri)!=0) crc^=0x1021; 1-3

　　}

　　ptr++;

　　}

　　return(crc);

　　}

　　執行結果 crc = 0xdbc0;

　　程序 1-1,1-2,1-3 可以理解成移位前 crc 的 Bit15 與數據對應的 Bit(*ptri)做 XOR運算，根據此結果來(lái)決定是否執行 crc^=0x1021。只要明白兩次異或運算與原值相同，就不難理解這個(gè)程序。

　　很多資料上都寫(xiě)了查表法來(lái)計算，當時(shí)是怎么也沒(méi)想通。其實(shí)蠻簡(jiǎn)單的。假設通過(guò)移位處理了 8 個(gè) bit 的數據，相當于把之前的 CRC 碼的高字節(8bit)全部移出，與一個(gè) byte 的數據做XOR 運算，根據運算結果來(lái)選擇一個(gè)值(稱(chēng)為余式)，與原來(lái)的 CRC 碼再做一次 XOR 運算，就可以得到新的 CRC 碼。

　　不難看出，余式有 256 種可能的值，實(shí)際上就是 0~255 以 X16+X12+X5+1 為權得到的 CRC碼，可以通過(guò)函數 crc16l來(lái)計算。以1 為例。

　　code test[]={0x01};

　　crc = 0;

　　ptr = test;

　　crc = crc16l(ptr,1);

　　執行結果 crc = 1021，這就是1 對應的余式。

　　進(jìn)一步修改函數，我這里就懶得寫(xiě)了，可得到 X16+X12+X5+1 的余式表。

　　code uint crc_ta[256]={ // X16+X12+X5+1 余式表

　　0x0000, 0x1021, 0x2042, 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, 0xf5cf, 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,

　　0xdbfd, 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, 0x8589, 0xf56e, 0xe54f, 0xd52c, 0xc50d,

　　0x34e2, 0x24c3, 0x14a0, 0x0481, 0x7466, 0x6447, 0x5424, 0x4405,