三種常用的CRC16校驗(yàn)算法的C51程序的優(yōu)化
CRC校驗(yàn)又稱為循環(huán)冗余校驗(yàn)，是數(shù)據(jù)通訊中常用的一種校驗(yàn)算法。它可以有效的判別出數(shù)據(jù)在傳輸過程中是否發(fā)生了錯(cuò)誤，從而保障了傳輸?shù)臄?shù)據(jù)可靠性。
CRC校驗(yàn)有多種方式，如：CRC8、CRC16、CRC32等等。在實(shí)際使用中，我們經(jīng)常使用CRC16校驗(yàn)。CRC16校驗(yàn)也有多種，如：1005多項(xiàng)式、1021多項(xiàng)式（CRC-ITU）等。在這里我們不討論CRC算法是怎樣產(chǎn)生的，而是重點(diǎn)落在幾種算法的C51程序的優(yōu)化上。
計(jì)算CRC校驗(yàn)時(shí)，最常用的計(jì)算方式有三種：查表、計(jì)算、查表＋計(jì)算。一般來說，查表法最快，但是需要較大的空間存放表格；計(jì)算法最慢，但是代碼最簡潔、占用空間最?。欢诩纫笏俣?，空間又比較緊張時(shí)常用查表＋計(jì)算法。
下面我們分別就這三種方法進(jìn)行討論和比較。這里以使用廣泛的51單片機(jī)為例，分別用查表、計(jì)算、查表＋計(jì)算三種方法計(jì)算 1021多項(xiàng)式（CRC-ITU）校驗(yàn)。原始程序都是在網(wǎng)上或雜志上經(jīng)常能見到的，相信大家也比較熟悉了，甚至就是正在使用或已經(jīng)使用過的程序。
編譯平臺采用KeilC517.0，使用小內(nèi)存模式，編譯器默認(rèn)的優(yōu)化方式。
常用的查表法程序如下，這是網(wǎng)上經(jīng)常能夠看到的程序范例。因?yàn)槠P(guān)系，省略了大部分表格的內(nèi)容。
co
0x0000,0x1021,0x2042,0x3063,...0x1ef0
};
unsignedintcrc0(unsignedchar*pData,unsignedcharnLength)
{
unsignedintCRC16=0;
while(nLength>0)
{
CRC16=(CRC16<<8)^Crc1021Table[((CRC16>>8)^*pData)&0xFF];
nLength--;
pData++;
}
returnCRC16;
}
編譯后，函數(shù)crc0的代碼為68字節(jié)，加上表格占用的512字節(jié)，一共使用了580個(gè)字節(jié)的代碼空間。
下面是常見的計(jì)算法的程序：
unsignedintcrc2(unsignedchar*ptr,unsignedcharcount)
{
unsignedintcrc=0;
unsignedchari;
while(count-->0)
{
crc=(crc^(((unsignedint)*ptr)<<8));
for(i=0;i<8;i++)
{
if(crc&0x8000)crc=((crc<<1)^0x1021);
elsecrc<<=1;
}
ptr++;
}
returncrc;
}
下面是常見的一種查表＋計(jì)算的方法：
unsignedintcrc4(unsignedchar*ptr,unsignedcharlen){
unsignedintcrc;
unsignedcharda;
co
0x0000,0x1021,0x2042,0x3063,0x4084,0x50a5,0x60c6,0x70e7,
0x8108,0x9129,0xa14a,0xb16b,0xc18c,0xd1ad,0xe1ce,0xf1ef,
};
crc=0;
while(len-->0){
da=((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=((crc/256))/16; /*暫存CRC的高4位*/
crc<<=4; /*CRC右移4位，相當(dāng)于CRC的低12位）*/
crc^=crc_ta[da^(*ptr&0x0f)];/*CRC的高4位和本字節(jié)的后半字節(jié)相加后查表*/
/*計(jì)算CRC，然后再加上上一次CRC的余數(shù)*/
ptr++;
}
returncrc;
}
程序優(yōu)化策略：上面程序都只是給出了通用算法，并沒有考慮到51單片機(jī)的特點(diǎn)。我們知道，51單片機(jī)是8位單片機(jī)，使用的變量類型也是8位的。如果在程序中使用8位的變量速度是最快的，比使用16位的變量代碼短、效率高。在上面的程序中都使用了大量整型數(shù)類型（16位）的表格和整型數(shù)類型的變量，特別是關(guān)鍵的變量。如果我們不使用整型類型的表格和變量，而使用字節(jié)類型的表格和變量，就能夠使程序的性能得到優(yōu)化?；谶@種思路，我們將原來整型的表格拆分為兩個(gè)字節(jié)型（8位）的表格，即將原來表格的高低字節(jié)分別拆開，每個(gè)表格還是256個(gè)單元，這樣表格的大小和順序都沒有變；原來使用16位變量計(jì)算的地方，改用8位變量計(jì)算。
修改后的查表程序如下（省略了表格的內(nèi)容）：
co
0x00,0x10,0x20,0x30,...0x0E,0x1E,
};
co
0x00,0x21,0x42,0x63,...0xD1,0xF0,
};
unsignedintcrc1(unsignedchar*buf,unsignedcharn)
{
unsignedchart;
union{
unsignedcharc[2];
unsignedintx;
}da
crc.x=0;
while(n!=0)
{
t=crc.c[0]^*buf;
crc.c[0]=crc.c[1]^crctableh[t];
crc.c[1]=crctablel[t];
n--;
buf++;
}
return(crc.x);
}
表面上看起來，函數(shù)crc1比crc0的源代碼還長一些。但是編譯后，函數(shù)crc1的目標(biāo)代碼實(shí)際為44個(gè)字節(jié)，加上表格占用的512個(gè)字節(jié)，一共使用了556個(gè)字節(jié)，比函數(shù)crc0反而節(jié)約了24個(gè)字節(jié)。這兩個(gè)函數(shù)的運(yùn)行對比情況見表一。
我們采用和上面相同的優(yōu)化方法來優(yōu)化計(jì)算法的程序，優(yōu)化后的計(jì)算法程序?yàn)椋?/p>
unsignedintcrc3(unsignedchar*ptr,unsignedcharcount)
{
da
union{
unsignedcharc[2];
unsignedintx;
}da
crc.x=0;
while(count!=0)
{
crc.c[0]^=*ptr;
for(i=8;i>0;i--)
{
if(crc.c[0]&0x70)crc.x=(crc.x<<1)&0x1021;
elsecrc.x=crc.x<<1;
}
ptr++;
count--;
}
returncrc.x;
}
編譯后函數(shù)crc2的代碼長度為76，函數(shù)crc3的代碼長度為68，變化不是太大，但是執(zhí)行效率是很不一樣的，具體差別見后面的表一。
優(yōu)化后的查表＋計(jì)算法的程序?yàn)椋?/p>
unsignedintcrc5(unsignedchar*ptr,unsignedcharlen)
{
co
0x00,0x10,0x20,0x30,0x40,0x50,0x60,0x70,
0x81,0x91,0xa1,0xb1,0xc1,0xd1,0xe1,0xf1,
};
co
0x00,0x21,0x42,0x63,0x84,0xa5,0xc6,0xe7,
0x08,0x29,0x4a,0x6b,0x8c,0xad,0xce,0xef,
};
union{
unsignedcharc[2];
unsignedintx;
}da
unsignedchart;
crc.x=0;
while(len!=0){
t=(crc.c[0]>>4)^(*ptr>>4);
crc.x<<=4;
crc.c[0]^=crch[t];
crc.c[1]^=crcl[t];
t=(crc.c[0]>>4)^(*ptr&0x0F);
crc.x<<=4;
crc.c[0]^=crch[t];
crc.c[1]^=crcl[t];
ptr++;
len--;
}
returncrc.x;
}
優(yōu)化前后的代碼長度分別為175字節(jié)和146字節(jié)（包括了32字節(jié)的表格空間）。
代碼測試：僅代碼長度變短是不夠的，衡量優(yōu)化后的程序一個(gè)重要的標(biāo)準(zhǔn)是看優(yōu)化前后兩個(gè)函數(shù)執(zhí)行相同的計(jì)算量使用的時(shí)間，或者說執(zhí)行的效率是否提高了。如果優(yōu)化后的函數(shù)需要時(shí)間少，就說明我們優(yōu)化后的函數(shù)確實(shí)提高了效率，否則就是反而降低了程序的效率，優(yōu)化失敗。我在KeilC51下編寫了一個(gè)測試程序，在程序中調(diào)用了上面的六個(gè)函數(shù)，共同計(jì)算一個(gè)長度為200字節(jié)的CRC校驗(yàn)，并記錄下每個(gè)函數(shù)使用的時(shí)間。測試方法為：使用KeilC51的軟件仿真功能（采用帶計(jì)時(shí)功能的硬件仿真器也可以），在每個(gè)函數(shù)上加上斷點(diǎn)，記錄下執(zhí)行到每個(gè)斷點(diǎn)的時(shí)間，然后前后相減就得出每個(gè)函數(shù)的執(zhí)行時(shí)間。仿真時(shí)使用的單片機(jī)型號為AT89C51，晶體頻率為12MHz。
測試文件的源代碼為：
xdataunsignedcharbuf[200];
unsignedchari;
unsignedintcrc;
externunsignedintcrc0(unsignedchar*,unsignedchar);
externunsignedintcrc1(unsignedchar*,unsignedchar);
externunsignedintcrc2(unsignedchar*,unsignedchar);
externunsignedintcrc3(unsignedchar*,unsignedchar);
externunsignedintcrc4(unsignedchar*,unsignedchar);
externunsignedintcrc5(unsignedchar*,unsignedchar);
voidmain(void)
{
for(i=0;i<200;i++)
buf[i]=i+1;
crc=crc0(buf,200);
crc=crc1(buf,200);
crc=crc2(buf,200);
crc=crc3(buf,200);
crc=crc4(buf,200);
crc=crc5(buf,200);
i=0;
}
測試結(jié)果見表一：
函數(shù)
代碼長度(字節(jié))
執(zhí)行時(shí)間（微秒）
提高效率
查表法
Crc0
68+512=580
10626
28%
Crc1
44+512=556
7622
計(jì)算法
Crc2
76
30309
13.6%
Crc3
68
26186
查表＋計(jì)算
Crc4
175
24229
18.2%
Crc5
146
19822
表一：三種CRC16校驗(yàn)算法及其優(yōu)化的比較
從表中可以看出，優(yōu)化后的函數(shù)執(zhí)行速度都有了明顯的提高，這說明我們的優(yōu)化是很有效的。其實(shí)優(yōu)化前后的函數(shù)區(qū)別并不大，算法都是完全一樣的，只是個(gè)別地方的寫法調(diào)整了一下，但是取得的效果是非常明顯的。現(xiàn)在很多人寫單片機(jī)的程序，都帶有寫VC或C＋＋的習(xí)慣，而沒有考慮到51單片機(jī)的特點(diǎn)，從而造成了一些資源的浪費(fèi)。
這三種計(jì)算方法之間的對比也很清楚，查表法使用的時(shí)間最短，查表＋計(jì)算次之，計(jì)算法最長，它們的執(zhí)行效率比為1：3.4：2.6，代碼效率比為8.1：1：2.1（優(yōu)化后的函數(shù)）。從代碼長度看，查表法因?yàn)槭褂昧艘粋€(gè)相對較大的表格，所以代碼最長，適合于代碼空間比較充足的情況；計(jì)算法沒有使用任何表格，所以代碼長度最小，適合于ROM空間比較小的情況。而查表＋計(jì)算法從執(zhí)行速度和代碼長度都是處于中流，是一種很好的折衷方案。
下面是我總結(jié)的一些C51編程優(yōu)化的幾個(gè)小技巧和方法：
1.盡量使用無符號的變量；
2.盡量使用da
3.使用最小的變量類型，能使用整型時(shí)就不要使用長整型，能使用字符型時(shí)就不要使用整型；
4.多使用局部變量，少使用全局變量、靜態(tài)變量，這樣可以充分利用Keil提供的變量覆蓋技術(shù)。同時(shí)局部變量也要盡量使用寄存器變量；
5.少使用浮點(diǎn)數(shù)。使用浮點(diǎn)數(shù)需要連接浮點(diǎn)庫，會(huì)增加大約1K的代碼；而且浮點(diǎn)運(yùn)算的速度是很慢的，沒有特殊情況盡量使用定點(diǎn)數(shù)代替浮點(diǎn)數(shù)；
6.沒有必要就不要使用printf等標(biāo)準(zhǔn)輸入輸出函數(shù)，它會(huì)增加大約3K的代碼。
7.函數(shù)帶有的參數(shù)不要太多，多了會(huì)影響效率；
8.注意C51的特點(diǎn)，按照C51的特點(diǎn)編寫程序；
9.多用幾種方法優(yōu)化，比較后找出最佳方法；
10.注意軟件的寫法，有時(shí)一個(gè)寫法上很小的變化就會(huì)有意想不到的效果。因?yàn)镵eil的優(yōu)化是與上下文的程序相關(guān)的，對于不同的情況產(chǎn)生不同的優(yōu)化。如果對比一下產(chǎn)生的匯編代碼，就能夠更加容易的找出不合理的代碼，從而有針對性的優(yōu)化了；
11.不要過于依賴C51提供的優(yōu)化功能，能夠自己優(yōu)化的地方就自己手工優(yōu)化了，程序不可能完成所有的事情；
12.不同版本的C51（特別是6.0和7.0的版本與低于6.0的版本相比）產(chǎn)生的優(yōu)化效果可能會(huì)不同，產(chǎn)生的代碼會(huì)不完全一樣，需要特別注意；
13.在循環(huán)中比較條件盡量與0作比較（這與51單片機(jī)的特點(diǎn)有關(guān)，對比一下編譯產(chǎn)生的匯編代碼就明白了），這樣可以減少代碼，加快速度。如：
將while(n>10)修改為
while(n!=0)；
14.在循環(huán)中比較中不要直接使用n--或n++，而要分開寫，這樣產(chǎn)生的代碼較小。
如：while(n--!=0)修改為
while(n!=0)
{
n--;
...//其他代碼
}
15.盡量不要使用太復(fù)雜的表達(dá)式，雖然這樣程序簡潔，但是對程序的調(diào)試不方便。
只要能充分考慮到所使用的單片機(jī)的特點(diǎn)，在加上一些經(jīng)驗(yàn)和技巧，就一定可以編寫出高性能的程序來。
下載文檔
