三种常用的CRC16校验算法的C51程序的优化.doc

三种常用的CRC16校验算法的C51程序的优化 2009-10-10 09:34:17| 分类： 技术知识 | 标签： |字号大中小 订阅 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 Crc1021Table256 = 0x0000, 0x1021, 0x2042, 0x3063,. 0x1ef0 ;unsigned int crc0(unsigned char *pData, unsigned char nLength) unsigned int CRC16 = 0; while(nLength0) CRC16 = (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;i8;i+) if(crc&0x8000) crc= (crc1)0x1021); else crc 0) da = (crc/256)/16; /* 暂存CRC的高四位 */ crc =4; /* CRC右移4位，相当于取CRC的低12位）*/crc = crc_tada(*ptr/16); /* CRC的高4位和本字节的前半字节相加后查表*/ /*计算CRC，然后加上上一次CRC的余数 */ da = (crc/256)/16; /* 暂存CRC的高4位 */ crc 0;i-) if(crc.c0&0x70)crc.x=(crc.x1)&0x1021; else crc.x=crc.x4) (*ptr 4); crc.x 4) (*ptr & 0x0F); crc.x =4; crc.c0 =crcht; crc.c1 =crclt; ptr+; len-; return crc.x;优化前后的代码长度分别为175字节和146字节（包括了32字节的表格空间）。代码测试：仅代码长度变短是不够的，衡量优化后的程序一个重要的标准是看优化前后两个函数执行相同的计算量使用的时间，或者说执行的效率是否提高了。如果优化后的函数需要时间少，就说明我们优化后的函数确实提高了效率，否则就是反而降低了程序的效率，优化失败。我在 Keil C51 下编写了一个测试程序，在程序中调用了上面的六个函数，共同计算一个长度为200字节的CRC校验，并记录下每个函数使用的时间。测试方法为：使用 Keil C51 的软件仿真功能（采用带计时功能的硬件仿真器也可以），在每个函数上加上断点，记录下执行到每个断点的时间，然后前后相减就得出每个函数的执行时间。仿真时使用的单片机型号为AT89C51，晶体频率为12MHz。测试文件的源代码为：xdata unsigned char buf200;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;iidataxdata ；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+ ，而要分开写，这样产生的代码