CRC校驗又稱為循環(huán)冗余校驗，是數(shù)據(jù)通訊中常用的一種校驗算法。它可以有效的判別出數(shù)據(jù)在傳輸過程中是否發(fā)生了錯誤，從而保障了傳輸?shù)臄?shù)據(jù)可靠性。
CRC校驗有多種方式，如：CRC8、CRC16、CRC32等等。在實際使用中，我們經(jīng)常使用CRC16校驗。CRC16校驗也有多種，如：1005多項式、1021多項式（CRC-ITU）等。在這里我們不討論CRC算法是怎樣產生的，而是重點落在幾種算法的C51程序的優(yōu)化上。
計算CRC校驗時，最常用的計算方式有三種：查表、計算、查表＋計算。一般來說，查表法最快，但是需要較大的空間存放表格；計算法最慢，但是代碼最簡潔、占用空間最小；而在既要求速度，空間又比較緊張時常用查表＋計算法。
下面我們分別就這三種方法進行討論和比較。這里以使用廣泛的51單片機為例，分別用查表、計算、查表＋計算三種方法計算 1021多項式（CRC-ITU）校驗。原始程序都是在網(wǎng)上或雜志上經(jīng)常能見到的，相信大家也比較熟悉了，甚至就是正在使用或已經(jīng)使用過的程序。
編譯平臺采用KeilC517.0，使用小內存模式，編譯器默認的優(yōu)化方式。
常用的查表法程序如下，這是網(wǎng)上經(jīng)常能夠看到的程序范例。因為篇幅關系，省略了大部分表格的內容。
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個字節(jié)的代碼空間。
下面是常見的計算法的程序：
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;
}
下面是常見的一種查表＋計算的方法：
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位，相當于取CRC的低12位）*/
crc^=crc_ta[da^(*ptr/16)]; /*CRC的高4位和本字節(jié)的前半字節(jié)相加后查表*/
/*計算CRC，然后加上上一次CRC的余數(shù)*/
da=((crc/256))/16; /*暫存CRC的高4位*/
crc<<=4; /*CRC右移4位，相當于CRC的低12位）*/
crc^=crc_ta[da^(*ptr&0x0f)];/*CRC的高4位和本字節(jié)的后半字節(jié)相加后查表*/
/*計算CRC，然后再加上上一次CRC的余數(shù)*/
ptr++;
}
returncrc;
}
程序優(yōu)化策略：上面程序都只是給出了通用算法，并沒有考慮到51單片機的特點。我們知道，51單片機是8位單片機，使用的變量類型也是8位的。如果在程序中使用8位的變量速度是最快的，比使用16位的變量代碼短、效率高。在上面的程序中都使用了大量整型數(shù)類型（16位）的表格和整型數(shù)類型的變量，特別是關鍵的變量。如果我們不使用整型類型的表格和變量，而使用字節(jié)類型的表格和變量，就能夠使程序的性能得到優(yōu)化?；谶@種思路，我們將原來整型的表格拆分為兩個字節(jié)型（8位）的表格，即將原來表格的高低字節(jié)分別拆開，每個表格還是256個單元，這樣表格的大小和順序都沒有變；原來使用16位變量計算的地方，改用8位變量計算。
修改后的查表程序如下（省略了表格的內容）：
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的目標代碼實際為44個字節(jié)，加上表格占用的512個字節(jié)，一共使用了556個字節(jié)，比函數(shù)crc0反而節(jié)約了24個字節(jié)。這兩個函數(shù)的運行對比情況見表一。
我們采用和上面相同的優(yōu)化方法來優(yōu)化計算法的程序，優(yōu)化后的計算法程序為：
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)化后的查表＋計算法的程序為：
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)化后的程序一個重要的標準是看優(yōu)化前后兩個函數(shù)執(zhí)行相同的計算量使用的時間，或者說執(zhí)行的效率是否提高了。如果優(yōu)化后的函數(shù)需要時間少，就說明我們優(yōu)化后的函數(shù)確實提高了效率，否則就是反而降低了程序的效率，優(yōu)化失敗。我在KeilC51下編寫了一個測試程序，在程序中調用了上面的六個函數(shù)，共同計算一個長度為200字節(jié)的CRC校驗，并記錄下每個函數(shù)使用的時間。測試方法為：使用KeilC51的軟件仿真功能（采用帶計時功能的硬件仿真器也可以），在每個函數(shù)上加上斷點，記錄下執(zhí)行到每個斷點的時間，然后前后相減就得出每個函數(shù)的執(zhí)行時間。仿真時使用的單片機型號為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;
}
測試結果見表一：
函數(shù)
代碼長度(字節(jié))
執(zhí)行時間（微秒）
提高效率
查表法
Crc0
68+512=580
10626
28%
Crc1
44+512=556
7622
計算法
Crc2
76
30309
13.6%
Crc3
68
26186
查表＋計算
Crc4
175
24229
18.2%
Crc5
146
19822
表一：三種CRC16校驗算法及其優(yōu)化的比較
從表中可以看出，優(yōu)化后的函數(shù)執(zhí)行速度都有了明顯的提高，這說明我們的優(yōu)化是很有效的。其實優(yōu)化前后的函數(shù)區(qū)別并不大，算法都是完全一樣的，只是個別地方的寫法調整了一下，但是取得的效果是非常明顯的。現(xiàn)在很多人寫單片機的程序，都帶有寫VC或C＋＋的習慣，而沒有考慮到51單片機的特點，從而造成了一些資源的浪費。
這三種計算方法之間的對比也很清楚，查表法使用的時間最短，查表＋計算次之，計算法最長，它們的執(zhí)行效率比為1：3.4：2.6，代碼效率比為8.1：1：2.1（優(yōu)化后的函數(shù)）。從代碼長度看，查表法因為使用了一個相對較大的表格，所以代碼最長，適合于代碼空間比較充足的情況；計算法沒有使用任何表格，所以代碼長度最小，適合于ROM空間比較小的情況。而查表＋計算法從執(zhí)行速度和代碼長度都是處于中流，是一種很好的折衷方案。
下面是我總結的一些C51編程優(yōu)化的幾個小技巧和方法：
1.盡量使用無符號的變量；
2.盡量使用da
3.使用最小的變量類型，能使用整型時就不要使用長整型，能使用字符型時就不要使用整型；
4.多使用局部變量，少使用全局變量、靜態(tài)變量，這樣可以充分利用Keil提供的變量覆蓋技術。同時局部變量也要盡量使用寄存器變量；
5.少使用浮點數(shù)。使用浮點數(shù)需要連接浮點庫，會增加大約1K的代碼；而且浮點運算的速度是很慢的，沒有特殊情況盡量使用定點數(shù)代替浮點數(shù)；
6.沒有必要就不要使用printf等標準輸入輸出函數(shù)，它會增加大約3K的代碼。
7.函數(shù)帶有的參數(shù)不要太多，多了會影響效率；
8.注意C51的特點，按照C51的特點編寫程序；
9.多用幾種方法優(yōu)化，比較后找出最佳方法；
10.注意軟件的寫法，有時一個寫法上很小的變化就會有意想不到的效果。因為Keil的優(yōu)化是與上下文的程序相關的，對于不同的情況產生不同的優(yōu)化。如果對比一下產生的匯編代碼，就能夠更加容易的找出不合理的代碼，從而有針對性的優(yōu)化了；
11.不要過于依賴C51提供的優(yōu)化功能，能夠自己優(yōu)化的地方就自己手工優(yōu)化了，程序不可能完成所有的事情；
12.不同版本的C51（特別是6.0和7.0的版本與低于6.0的版本相比）產生的優(yōu)化效果可能會不同，產生的代碼會不完全一樣，需要特別注意；
13.在循環(huán)中比較條件盡量與0作比較（這與51單片機的特點有關，對比一下編譯產生的匯編代碼就明白了），這樣可以減少代碼，加快速度。如：
將while(n>10)修改為
while(n!=0)；
14.在循環(huán)中比較中不要直接使用n--或n++，而要分開寫，這樣產生的代碼較小。
如：while(n--!=0)修改為
while(n!=0)
{
n--;
...//其他代碼
}
15.盡量不要使用太復雜的表達式，雖然這樣程序簡潔，但是對程序的調試不方便。
只要能充分考慮到所使用的單片機的特點，在加上一些經(jīng)驗和技巧，就一定可以編寫出高性能的程序來。
下載文檔
