單片機C語言實現(xiàn)的CRC算法

crc=0;
while(len--!=0) {
da=(uchar) (crc/256); /* 以8位二進制數(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時，由于采用了查表法，大大提高了計算速度。但對于廣泛運用的8位微處理器，代碼空間有限，對于要求256個CRC余式表（共512字節(jié)的內(nèi)存）已經(jīng)顯得捉襟見肘了，但CRC的計算速度又不可以太慢，因此再介紹下面一種按半字節(jié)求CRC的算法。
5 按半字節(jié)計算CRC
同樣道理，對于一個二進制序列數(shù)可以按字節(jié)表示為式(5-1)，其中 為半個字節(jié)(共4位)。
(5-1)
求此二進制序列數(shù)的CRC碼時，先乘以 后（既左移16位），再除以多項式G(X)，所得的余數(shù)既是所要求的CRC碼。如式(4-2)所示：
（5-2）
可以設(shè)： (5-3)
其中 為整數(shù)， 為16位二進制余數(shù)。將式(5-3)代入式(5-2)得：
（5-4）
因為：
（5-5）
其中 是 的高4位， 是 的低12位。將式（5-5）代入式（5-4），經(jīng)整理后得：
（5-6）
再設(shè)： (5-7)
其中 為整數(shù)， 為16位二進制余數(shù)。將式(5-7)代入式(5-6)，如上類推，最后得：
(5-8)
很顯然，十六位二進制數(shù) 既是我們要求的CRC碼。
式(5-7)是編寫按字節(jié)計算CRC程序的關(guān)鍵，它說明計算本字節(jié)后的CRC碼等于上一字節(jié)CRC碼的低12位左移4位后，再加上上一字節(jié)余式CRC右移4位（也既取高4位）和本字節(jié)之和后所求得的CRC碼，如果我們把4位二進制序列數(shù)的CRC全部計算出來，放在一個表里，采用查表法，每個字節(jié)算兩次（半字節(jié)算一次），可以在速度和內(nèi)存空間取得均衡。由此不難理解下面按半字節(jié)求CRC碼的C語言程序。*ptr指向發(fā)送緩沖區(qū)的首字節(jié)，len是要發(fā)送的總字節(jié)數(shù)，CRC余式表是按0x11021多項式求出的。
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é)相加后查表計算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é)相加后查表計算CRC，
然后再加上上一次CRC的余數(shù) */
ptr++;
}
return(crc);
}
5 結(jié)束語
以上介紹的三種求CRC的程序，按位求法速度較慢，但占用最小的內(nèi)存空間；按字節(jié)查表求CRC的方法速度較快，但占用較大的內(nèi)存；按半字節(jié)查表求CRC的方法是前兩者的均衡，即不會占用太多的內(nèi)存，同時速度又不至于太慢，比較適合8位小內(nèi)存的單片機的應(yīng)用場合。以上所給的C程序可以根據(jù)各微處理器編譯器的特點作相應(yīng)的改變，比如把CRC余式表放到程序存儲區(qū)內(nèi)等。