CRC校驗(yàn)源碼學(xué)習(xí)

　　這兩天做項(xiàng)目，需要用到 CRC 校驗(yàn)。以前沒(méi)搞過(guò)這東東，以為挺簡(jiǎn)單的。結(jié)果看看別人提供的匯編源程序，居然看不懂?；藘商鞎r(shí)間研究了一下 CRC 校驗(yàn)，希望我寫(xiě)的這點(diǎn)東西能夠幫助和我有同樣困惑的朋友節(jié)省點(diǎn)時(shí)間。

　　先是在網(wǎng)上下了一堆亂七八遭的資料下來(lái)，感覺(jué)都是一個(gè)模樣，全都是從 CRC 的數(shù)學(xué)原理開(kāi)始，一長(zhǎng)串的表達(dá)式看的我頭暈。第一次接觸還真難以理解。這些東西不想在這里講，隨便找一下都是一大把。我想根據(jù)源代碼來(lái)分析會(huì)比較好懂一些。

　　費(fèi)了老大功夫，才搞清楚 CRC 根據(jù)”權(quán)”(即多項(xiàng)表達(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 為例。其實(shí)本質(zhì)都是一樣，搞明白一種，其他的都是小菜。

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

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

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

　　根據(jù)以上說(shuō)明，可以依葫蘆畫(huà)瓢的寫(xiě)出以下程序。(程序都是在 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; // 指向第一個(gè) Byte 數(shù)據(jù)

　　crc = crc16l(ptr,8);

　　while(1);

　　}

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

　　{

　　uchar i;

　　while(len--)

　　{

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

　　{

　　if((crc&0x8000)!=0) {crc<<=1; crc^=0x1021;} 1-1

　　else crc<<=1; 1-2

　　if((*ptr&i)!=0) crc^=0x1021; 1-3

　　}

　　ptr++;

　　}

　　return(crc);

　　}

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

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

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

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

　　code test[]={0x01};

　　crc = 0;

　　ptr = test;

　　crc = crc16l(ptr,1);

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

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

　　0xa7db, 0xb7fa, 0x8799, 0x97b8, 0xe75f, 0xf77e, 0xc71d, 0xd73c,

　　0x26d3, 0x36f2, 0x0691, 0x16b0, 0x6657, 0x7676, 0x4615, 0x5634,

　　0xd94c, 0xc96d, 0xf90e, 0xe92f, 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, 0x1ce0, 0x0cc1,

　　0xef1f, 0xff3e, 0xcf5d, 0xdf7c, 0xaf9b, 0xbfba, 0x8fd9, 0x9ff8,

　　0x6e17, 0x7e36, 0x4e55, 0x5e74, 0x2e93, 0x3eb2, 0x0ed1, 0x1ef0

　　};

　　根據(jù)這個(gè)思路，可以寫(xiě)出以下程序：

　　uint table_crc(uchar *ptr,uchar len) // 字節(jié)查表法求 CRC

　　{

　　uchar da;

　　while(len--!=0)

　　{

　　da=(uchar) (crc/256); // 以 8 位二進(jìn)制數(shù)暫存 CRC 的高 8 位

　　crc<<=8; // 左移 8 位

　　crc^=crc_ta[da^*ptr]; // 高字節(jié)和當(dāng)前數(shù)據(jù) XOR 再查表

　　ptr++;

　　}

　　return(crc);

　　}

　　本質(zhì)上 CRC 計(jì)算的就是移位和異或。所以一次處理移動(dòng)幾位都沒(méi)有關(guān)系，只要做相應(yīng)的處理就好了。

　　下面給出半字節(jié)查表的處理程序。其實(shí)和全字節(jié)是一回事。

　　code uint crc_ba[16]={

　　0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50a5, 0x60c6, 0x70e7,

　　0x8108, 0x9129, 0xa14a, 0xb16b, 0xc18c, 0xd1ad, 0xe1ce, 0xf1ef,

　　};

　　uint ban_crc(uchar *ptr,uchar len)

　　{

　　uchar da;

　　while(len--!=0)

　　{

　　da = ((uchar)(crc/256))/16;

　　crc <<= 4;

　　crc ^=crc_ba[da^(*ptr/16)];

　　da = ((uchar)(crc/256)/16);

　　crc <<= 4;

　　crc ^=crc_ba[da^(*ptr&0x0f)];

　　ptr++;

　　}

　　return(crc);

　　}

　　crc_ba[16]和crc_ta[256]的前 16 個(gè)余式是一樣的。

　　其實(shí)講到這里，就已經(jīng)差不多了。反正當(dāng)時(shí)我以為自己是懂了。結(jié)果去看別人的源代碼的時(shí)候，也是說(shuō)采用 CCITT，但是是反相的。如圖 3

　　反過(guò)來(lái)，一切都那么陌生，faint.吐血，吐血。

　　仔細(xì)分析一下，也可以很容易寫(xiě)出按位異或的程序。只不過(guò)由左移變成右移。

　　uint crc16r(unsigned char *ptr, unsigned char len)

　　{

　　unsigned char i;

　　while(len--!=0)

　　{

　　for(i=0x01;i!=0;i <<= 1)

　　{

　　if((crc&0x0001)!=0) {crc >>= 1; crc ^= 0x8408;}

　　else crc >>= 1;

　　if((*ptr&i)!=0) crc ^= 0x8408;

　　}

　　ptr++;

　　}

　　return(crc);

　　}

　　0x8408 就是 CCITT 的反轉(zhuǎn)多項(xiàng)式。

　　套用別人資料上的話(huà)

　　“反轉(zhuǎn)多項(xiàng)式是指在數(shù)據(jù)通訊時(shí)，信息字節(jié)先傳送或接收低位字節(jié)，如重新排位影響 CRC計(jì)算速度，故設(shè)反轉(zhuǎn)多項(xiàng)式。”

　　如

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

　　反過(guò)來(lái)就是

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

　　crc = 0;

　　ptr = crcbuff_fan;

　　crc = crc16r(ptr,8);

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

　　如想驗(yàn)證是否正確，可改

　　code uchar crcbuff_fan_result[] = {0xe3,0xd2,0x0d,0x06,0x00,0x00,0x00,0x00,0x1d,0x5f};

　　ptr = crcbuff_fan_result;

　　crc = crc16r(ptr,10);

　　執(zhí)行結(jié)果 crc = 0; 符合 CRC 校驗(yàn)的原理。

　　請(qǐng)注意 0x5f1d 在數(shù)組中的排列中低位在前，正是反相運(yùn)算的特點(diǎn)。不過(guò)當(dāng)時(shí)是把我搞的暈頭轉(zhuǎn)向。

　　在用半字節(jié)查表法進(jìn)行反相運(yùn)算要特別注意一點(diǎn)，因?yàn)槭怯乙?，所?CRC 移出的 4Bit與數(shù)據(jù) XOR 的操作是在 CRC 的高位端。因此余式表的產(chǎn)生是要以下列數(shù)組通過(guò)修改函數(shù)crc16r 產(chǎn)生。

　　code uchar ban_fan[]=

　{0,0x10,0x20,0x30,0x40,0x50,0x60,0x70,0x80,0x90,

0xa0,0xb0,0xc0,0xd0,0xe0,0xf0};

　　得出余式表

　　code uint fan_yushi[16]={

　　0x0000, 0x1081, 0x2102, 0x3183,

　　0x4204, 0x5285, 0x6306, 0x7387,

　　0x8408, 0x9489, 0xa50a, 0xb58b,

　　0xc60c, 0xd68d, 0xe70e, 0xf78f

　　};

　　uint ban_fan_crc(uchar *ptr,uchar len)

　　{

　　uchar da;

　　while(len--!=0)

　　{

　　da = (uchar)(crc&0x000f);

　　crc >>= 4;

　　crc ^= fan_yushi [da^(*ptr&0x0f)];

　　da = (uchar)(crc&0x000f);

　　crc >>= 4;

　　crc ^= fan_yushi [da^(*ptr/16)];

　　ptr++;

　　}

　　return(crc);

　　}

　　主程序中

　　crc = 0;

　　ptr = crcbuff_fan;

　　crc = ban_fan_crc(ptr,8);

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