CRC校驗源碼分析

CRC 根據(jù)”權(quán)”(即多項表達(dá)式)的不同而相應(yīng)的源代碼也有稍許不同。以下是各種常用的權(quán)。

　　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 為例。其實本質(zhì)都是一樣，搞明白一種，其他的都是小菜。

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

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

　　X5 代表 Bit5，X12 代表 Bit12，1 自然是代表 Bit0，X16 比較特別，是指移位寄存器移出的數(shù)據(jù)，即圖中的DATA OUT。可以這樣理解，與數(shù)據(jù)位做XOR運算的是上次 CRC值的 Bit15。

　　根據(jù)以上說明，可以依葫蘆畫瓢的寫出以下程序。(程序都是在 keil C 7.10 下調(diào)試的)

　　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; // 指向第一個 Byte 數(shù)據(jù)

　　crc = crc16l(ptr,8);

　　while(1);

　　}

　　uint crc16l(uchar *ptr,uchar len) // ptr 為數(shù)據(jù)指針，len 為數(shù)據(jù)長度

　　{

　　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);

　　}

　　執(zhí)行結(jié)果 crc = 0xdbc0;

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

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

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

　　code test[]={0x01};

　　crc = 0;

　　ptr = test;

　　crc = crc16l(ptr,1);

　　執(zhí)行結(jié)果 crc = 1021，這就是1 對應(yīng)的余式。

　　進(jìn)一步修改函數(shù)，我這里就懶得寫了，可得到 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,