單片機(jī)CRC快速算法

3.2 三字節(jié)序列計(jì)算 提到簡單快捷，人們自然會(huì)想到采用查表的辦法，例如事先把三字節(jié)序列的所有余式計(jì)算出來，置于一個(gè)稱為“余式表”的表格中，供隨時(shí)讀取。不過，這樣的表格太大，需要224個(gè)單元，也就是要占用225個(gè)字節(jié)的存儲(chǔ)空間，這對(duì)單片機(jī)來說是絕對(duì)無法接受的，因此，需要想辦法減少所占用的存儲(chǔ)空間。

　　　　　　　　　　　　　　　　 圖1

遞推計(jì)算步驟 設(shè)一個(gè)三字節(jié)序列Tabc ＝[ a b c ] 、一個(gè) Ta00＝[ a 0 0 ]和一個(gè)二字節(jié)序列 Tbc＝[ b c ]。可以用多項(xiàng)式形式表示它們之間的關(guān)系為 Tabc(x)＝Ta00(x)＋Tbc(x)，因此，對(duì)Ta00來說，
　

（8） 而對(duì)Tabc來說，

?其中，Qa00是整數(shù)，與余式無關(guān)；而Ra00和Tbc都是二字節(jié)序列，因而，它們的和（模2加法，即異或運(yùn)算）仍然是二字節(jié)序列（二進(jìn)制16位，小于生成多項(xiàng)式的17位），因此，它就是 Tabc的余式Rabc，即

（9） 這說明，可以把三字節(jié)序列Tabc＝[ a b c ]的運(yùn)算分解成兩個(gè)步驟來進(jìn)行，如圖2所示。 1. 通過查余式表（表1），讀取Ta00＝[a 0 0 ]的余式Ra00＝[ ha00 la00 ]； 2. 將Ra00與[ b c ]進(jìn)行異或運(yùn)算，從而得到[ a b c ]的余式Rabc＝[ habc labc ]，即habc＝ha00 ＆ b，labc＝la00 ＆ c。 由于[a 0 0 ]中只有一個(gè)字節(jié)不為零，因此，[a 0 0 ]余式表僅需要256個(gè)單元，即占用512個(gè)字節(jié)。

4　適用于51系列等單片機(jī)的算法 前面所述的辦法可以直接用于51系列等單片機(jī)，因?yàn)?12字節(jié)的余式表對(duì)它們的程序存儲(chǔ)容量來說是完全不成問題的。 計(jì)算直接通過上述的遞推過程來進(jìn)行，每一次遞推都是對(duì)一個(gè)三字節(jié)序列進(jìn)行的計(jì)算：第一次是[ m1 m2 m3 ]，結(jié)果是[ h3 l3 ]；第二次是[ h3 l3 m4 ]，結(jié)果是[ h4 l4 ]；......，第i次是[ hi+1 li+1 mi+2 ]，結(jié)果是[ hi+2 li+2 ]；......；最后是[ hk+1 lk+1 mk+2 ]，最終結(jié)果是[ h l ]。如果有k個(gè)數(shù)據(jù)字節(jié)，則遞推k次。下面給出一個(gè)三字節(jié)序列計(jì)算子程序，供每一次遞推運(yùn)算時(shí)調(diào)用。注意，在第一次被調(diào)用之前，先將m1、 m2和m3分別存入R0、R1和R2中（子程序返回時(shí)，計(jì)算結(jié)果將存放在R0和R1中）。從第二次調(diào)用時(shí)開始，每次在調(diào)用之前只需先將參與本次運(yùn)算的字節(jié)存入R2即可（第二次是m4，第三次是m5，...，第i次是mi+2，...）。當(dāng)最后一次調(diào)用返回后，R0和R1分別存放的就是最終結(jié)果h和l 。

CRC MOV DPH, #table ; 指向余式表下半?yún)^(qū)


　　MOVC A, @A+DPTR ; 讀余式的高字節(jié)

　　XRL A, R1 ; 計(jì)算余式的高字節(jié)

　　MOV R0, A ; 存入R0

　　INC DPH ; 指向余式表上半?yún)^(qū)

　　CLR A ;

　　MOVC A, @A+DPTR ; 讀余式的低字節(jié)

　　XRL A, R2 ; 計(jì)算余式的低字節(jié)

　　MOV R1, A ; 存入R1

　　 RET

這一子程序只有12條指令，因此十分簡捷，而且只占用16個(gè)機(jī)器周期，也就是說，相當(dāng)于計(jì)算每一個(gè)字節(jié)只需16個(gè)機(jī)器周期即可完成，這將比傳統(tǒng)的軟件算法快十幾倍。