單片機(jī)C語(yǔ)言實(shí)現(xiàn)的CRC算法

crc=0;
while(len--!=0) {
da=(uchar) (crc/256); /* 以8位二進(jìn)制數(shù)的形式暫存CRC的高8位 */
crc=8; /* 左移8位，相當(dāng)于CRC的低8位乘以 */
crc^=crc_ta[da^*ptr]; /* 高8位和當(dāng)前字節(jié)相加后再查表求CRC ，再加上以前的CRC */
ptr++;
}
return(crc);
}
很顯然，按字節(jié)求CRC時(shí)，由于采用了查表法，大大提高了計(jì)算速度。但對(duì)于廣泛運(yùn)用的8位微處理器，代碼空間有限，對(duì)于要求256個(gè)CRC余式表（共512字節(jié)的內(nèi)存）已經(jīng)顯得捉襟見(jiàn)肘了，但CRC的計(jì)算速度又不可以太慢，因此再介紹下面一種按半字節(jié)求CRC的算法。
5 按半字節(jié)計(jì)算CRC
同樣道理，對(duì)于一個(gè)二進(jìn)制序列數(shù)可以按字節(jié)表示為式(5-1)，其中 為半個(gè)字節(jié)(共4位)。
(5-1)
求此二進(jìn)制序列數(shù)的CRC碼時(shí)，先乘以 后（既左移16位），再除以多項(xiàng)式G(X)，所得的余數(shù)既是所要求的CRC碼。如式(4-2)所示：
（5-2）
可以設(shè)： (5-3)
其中 為整數(shù)， 為16位二進(jìn)制余數(shù)。將式(5-3)代入式(5-2)得：
（5-4）
因?yàn)椋?
（5-5）
其中 是 的高4位， 是 的低12位。將式（5-5）代入式（5-4），經(jīng)整理后得：
（5-6）
再設(shè)： (5-7)
其中 為整數(shù)， 為16位二進(jìn)制余數(shù)。將式(5-7)代入式(5-6)，如上類推，最后得：
(5-8)
很顯然，十六位二進(jìn)制數(shù) 既是我們要求的CRC碼。
式(5-7)是編寫按字節(jié)計(jì)算CRC程序的關(guān)鍵，它說(shuō)明計(jì)算本字節(jié)后的CRC碼等于上一字節(jié)CRC碼的低12位左移4位后，再加上上一字節(jié)余式CRC右移4位（也既取高4位）和本字節(jié)之和后所求得的CRC碼，如果我們把4位二進(jìn)制序列數(shù)的CRC全部計(jì)算出來(lái)，放在一個(gè)表里，采用查表法，每個(gè)字節(jié)算兩次（半字節(jié)算一次），可以在速度和內(nèi)存空間取得均衡。由此不難理解下面按半字節(jié)求CRC碼的C語(yǔ)言程序。*ptr指向發(fā)送緩沖區(qū)的首字節(jié)，len是要發(fā)送的總字節(jié)數(shù)，CRC余式表是按0x11021多項(xiàng)式求出的。
unsigned cal_crc(unsigned char *ptr, unsigned char len) {
unsigned int crc;
unsigned char da;
unsigned int crc_ta[16]={ /* CRC余式表 */
0x0000,0x1021,0x2042,0x3063,0x4084,0x50a5,0x60c6,0x70e7,
0x8108,0x9129,0xa14a,0xb16b,0xc18c,0xd1ad,0xe1ce,0xf1ef,
}

crc=0;
while(len--!=0) {
da=((uchar)(crc/256))/16; /* 暫存CRC的高四位 */
crc=4; /* CRC右移4位，相當(dāng)于取CRC的低12位）*/
crc^=crc_ta[da^(*ptr/16)]; /* CRC的高4位和本字節(jié)的前半字節(jié)相加后查表計(jì)算CRC，
然后加上上一次CRC的余數(shù) */
da=((uchar)(crc/256))/16; /* 暫存CRC的高4位 */
crc=4; /* CRC右移4位， 相當(dāng)于CRC的低12位） */
crc^=crc_ta[da^(*ptr0x0f)]; /* CRC的高4位和本字節(jié)的后半字節(jié)相加后查表計(jì)算CRC，
然后再加上上一次CRC的余數(shù) */
ptr++;
}
return(crc);
}
5 結(jié)束語(yǔ)
以上介紹的三種求CRC的程序，按位求法速度較慢，但占用最小的內(nèi)存空間；按字節(jié)查表求CRC的方法速度較快，但占用較大的內(nèi)存；按半字節(jié)查表求CRC的方法是前兩者的均衡，即不會(huì)占用太多的內(nèi)存，同時(shí)速度又不至于太慢，比較適合8位小內(nèi)存的單片機(jī)的應(yīng)用場(chǎng)合。以上所給的C程序可以根據(jù)各微處理器編譯器的特點(diǎn)作相應(yīng)的改變，比如把CRC余式表放到程序存儲(chǔ)區(qū)內(nèi)等。