三种常用的CRC16校验算法的C51程序的优化
CRC校验又称为循环冗余校验，是数据通讯中常用的一种校验算法。它可以有效的判别出数据在传输过程中是否发生了错误，从而保障了传输的数据可靠性。
CRC校验有多种方式，如：CRC8、CRC16、CRC32等等。在实际使用中，我们经常使用CRC16校验。CRC16校验也有多种，如：1005多项式、1021多项式（CRC-ITU）等。在这里我们不讨论CRC算法是怎样产生的，而是重点落在几种算法的C51程序的优化上。
计算CRC校验时，最常用的计算方式有三种：查表、计算、查表＋计算。一般来说，查表法最快，但是需要较大的空间存放表格；计算法最慢，但是代码最简洁、占用空间最小；而在既要求速度，空间又比较紧张时常用查表＋计算法。
下面我们分别就这三种方法进行讨论和比较。这里以使用广泛的51单片机为例，分别用查表、计算、查表＋计算三种方法计算 1021多项式（CRC-ITU）校验。原始程序都是在网上或杂志上经常能见到的，相信大家也比较熟悉了，甚至就是正在使用或已经使用过的程序。
编译平台采用 Keil C51 7.0，使用小内存模式，编译器默认的优化方式。
常用的查表法程序如下，这是网上经常能够看到的程序范例。因为篇幅关系，省略了大部分表格的内容。
code unsigned int Crc1021Table[256] = {
0x0000, 0x1021, 0x2042, 0x3063,... 0x1ef0
};
unsigned int crc0(unsigned char *pData, unsigned char nLength)
{
unsigned int CRC16 = 0;
while(nLength>0)
{
CRC16 = (CRC16 << 8 ) ^ Crc1021Table[((CRC16>>8) ^ *pData) & 0xFF];
nLength--;
pData++;
}
return CRC16;
}
编译后，函数crc0的代码为68字节，加上表格占用的512字节，一共使用了580个字节的代码空间。
下面是常见的计算法的程序：
unsigned int crc2(unsigned char *ptr,unsigned char count)
{
unsigned int crc =0;
unsigned char i;
while(count-- >0)
{
crc = ( crc^(((unsigned int)*ptr)<<8));
for(i=0;i<8;i++)
{
if(crc&0x8000) crc= ((crc<<1)^0x1021);
else crc <<= 1;
}
ptr++;
}
return crc;
}
下面是常见的一种查表＋计算的方法：
unsigned int crc4(unsigned char *ptr, unsigned char len) {
unsigned int crc;
unsigned char da;
code 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 = ((crc/256))/16; /* 暂存CRC的高四位 */
crc <<=4; /* CRC右移4位，相当于取CRC的低12位）*/
crc ^= crc_ta[da^(*ptr/16)
]; /* CRC的高4位和本字节的前半字节相加后查表*/
/*计算CRC，然后加上上一次CRC的余数 */
da = ((crc/256))/16; /* 暂存CRC的高4位 */
crc <<=4; /* CRC右移4位， 相当于CRC的低12位） */
crc ^= crc_ta[da^(*ptr&0x0f)];/* CRC的高4位和本字节的后半字节相加后查表*/
/*计算CRC，然后再加上上一次CRC的余数 */
ptr++;
}
return crc;
}
程序优化策略：上面程序都只是给出了通用算法，并没有考虑到51单片机的特点。我们知道，51单片机是8位单片机，使用的变量类型也是8位的。如果在程序中使用8位的变量速度是最快的，比使用16位的变量代码短、效率高。在上面的程序中都使用了大量整型数类型（16位）的表格和整型数类型的变量，特别是关键的变量。如果我们不使用整型类型的表格和变量，而使用字节类型的表格和变量，就能够使程序的性能得到优化。基于这种思路，我们将原来整型的表格拆分为两个字节型（8位）的表格，即将原来表格的高低字节分别拆开，每个表格还是256个单元，这样表格的大小和顺序都没有变；原来使用16位变量计算的地方，改用8位变量计算。
修改后的查表程序如下（省略了表格的内容）：
code unsigned char crctableh[256]={
0x00,0x10,0x20,0x30,... 0x0E,0x1E,
};
code unsigned char crctablel[256]={
0x00,0x21,0x42,0x63,... 0xD1,0xF0,
};
unsigned int crc1(unsigned char *buf,unsigned char n)
{
unsigned char t;
union{
unsigned char c[2];
unsigned int x;
}data crc;
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 );
}
表面上看起来，函数crc1比crc0的源代码还长一些。但是编译后，函数crc1的目标代码实际为44个字节，加上表格占用的512个字节，一共使用了556个字节，比函数crc0反而节约了24个字节。这两个函数的运行对比情况见表一。
我们采用和上面相同的优化方法来优化计算法的程序，优化后的计算法程序为：
unsigned int crc3(unsigned char *ptr,unsigned char count)
{
data unsigned char i;
union{
unsigned char c[2];
unsigned int x;
}data crc;
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;
else crc.x=crc.x<<1;
}
ptr++;
count--;
}
return crc.x;
}
编译后函数crc2的代码长度为76，函数crc3的代码长度为68，变化不是太大，但是执行效率是很不一样的，具体差别见后面的表一。
优化后的查表＋计算法的程序为：
unsigned int crc5(unsigned char *ptr
,unsigned char len)
{
code unsigned char crch[16]={ /* CRC余式表 */
0x00,0x10,0x20,0x30,0x40,0x50,0x60,0x70,
0x81,0x91,0xa1,0xb1,0xc1,0xd1,0xe1,0xf1,
};
code unsigned char crcl[16]={ /* CRC余式表 */
0x00,0x21,0x42,0x63,0x84,0xa5,0xc6,0xe7,
0x08,0x29,0x4a,0x6b,0x8c,0xad,0xce,0xef,
};
union{
unsigned char c[2];
unsigned int x;
}data crc;
unsigned char t;
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--;
}
return crc.x;
}
优化前后的代码长度分别为175字节和146字节（包括了32字节的表格空间）。
代码测试：仅代码长度变短是不够的，衡量优化后的程序一个重要的标准是看优化前后两个函数执行相同的计算量使用的时间，或者说执行的效率是否提高了。如果优化后的函数需要时间少，就说明我们优化后的函数确实提高了效率，否则就是反而降低了程序的效率，优化失败。我在 Keil C51 下编写了一个测试程序，在程序中调用了上面的六个函数，共同计算一个长度为200字节的CRC校验，并记录下每个函数使用的时间。测试方法为：使用 Keil C51 的软件仿真功能（采用带计时功能的硬件仿真器也可以），在每个函数上加上断点，记录下执行到每个断点的时间，然后前后相减就得出每个函数的执行时间。仿真时使用的单片机型号为AT89C51，晶体频率为12MHz。
测试文件的源代码为：
xdata unsigned char buf[200];
unsigned char i;
unsigned int crc;
extern unsigned int crc0(unsigned char *,unsigned char);
extern unsigned int crc1(unsigned char *,unsigned char);
extern unsigned int crc2(unsigned char *,unsigned char);
extern unsigned int crc3(unsigned char *,unsigned char);
extern unsigned int crc4(unsigned char *,unsigned char);
extern unsigned int crc5(unsigned char *,unsigned char);
void main(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;
}
测试结果见表一：
函数
代码长度(字节)
执行时间（微秒）
提高效率
查表法
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校验算法及其优化的比较
从表中可以看出，优化后的函数执行速度都有了明显的提高，这说明我们的优化是很有效的。其实优化前后的函
数区别并不大，算法都是完全一样的，只是个别地方的写法调整了一下，但是取得的效果是非常明显的。现在很多人写单片机的程序，都带有写VC或C＋＋的习惯，而没有考虑到51单片机的特点，从而造成了一些资源的浪费。
这三种计算方法之间的对比也很清楚，查表法使用的时间最短，查表＋计算次之，计算法最长，它们的执行效率比为1：3.4：2.6，代码效率比为8.1：1：2.1（优化后的函数）。从代码长度看，查表法因为使用了一个相对较大的表格，所以代码最长，适合于代码空间比较充足的情况；计算法没有使用任何表格，所以代码长度最小，适合于ROM空间比较小的情况。而查表＋计算法从执行速度和代码长度都是处于中流，是一种很好的折衷方案。
下面是我总结的一些C51编程优化的几个小技巧和方法：
1. 尽量使用无符号的变量；
2. 尽量使用data与idata寄存器变量；它们之间的效率顺序为data>idata>xdata ；
3. 使用最小的变量类型，能使用整型时就不要使用长整型，能使用字符型时就不要使用整型；
4. 多使用局部变量，少使用全局变量、静态变量，这样可以充分利用Keil提供的变量覆盖技术。同时局部变量也要尽量使用寄存器变量；
5. 少使用浮点数。使用浮点数需要连接浮点库，会增加大约1K的代码；而且浮点运算的速度是很慢的，没有特殊情况尽量使用定点数代替浮点数；
6. 没有必要就不要使用printf等标准输入输出函数，它会增加大约3K的代码。
7. 函数带有的参数不要太多，多了会影响效率；
8. 注意C51的特点，按照C51的特点编写程序；
9. 多用几种方法优化，比较后找出最佳方法；
10. 注意软件的写法，有时一个写法上很小的变化就会有意想不到的效果。因为Keil的优化是与上下文的程序相关的，对于不同的情况产生不同的优化。如果对比一下产生的汇编代码，就能够更加容易的找出不合理的代码，从而有针对性的优化了；
11. 不要过于依赖C51提供的优化功能，能够自己优化的地方就自己手工优化了，程序不可能完成所有的事情；
12. 不同版本的C51（特别是6.0和7.0的版本与低于6.0的版本相比）产生的优化效果可能会不同，产生的代码会不完全一样，需要特别注意；
13. 在循环中比较条件尽量与0作比较（这与51单片机的特点有关，对比一下编译产生的汇编代码就明白了），这样可以减少代码，加快速度。如：
将while( n > 10 )修改为
while( n != 0 )；
14. 在循环中比较中不要直接使用 n-- 或 n++ ，而要分开写，这样产生的代码较小。
如：while( n-- != 0)修改为
while(n != 0)
{
n--;
...//其他代码
}
15.
尽量不要使用太复杂的表达式，虽然这样程序简洁，但是对程序的调试不方便。
只要能充分考虑到所使用的单片机的特点，在加上一些经验和技巧，就一定可以编写出高性能的程序来。