原创 使用半字节查表法之CRC16的code sample(一)

在进行通讯的过程中, 我们需要和CRC打交道. Allen觉得, 尽管在很多时候, CRC并不是那么重要. 但是出于通讯协议兼容, 我们往往被迫使用CRC计算. 在通宵的工作过程中, Allen 对网络资源进行了一番整理, 并自行加入理解, 便于同行们, 在相应工作时, 节省大量查阅资料的时间.

前提:
1. 运算法则的可靠性: 在反复检索资料后, Allen 意识到, 弄清运算法则需要至少1个工作日, 用大量实例和思考, 并配合相当的实例进行思考. 在极大的项目时间压力下, 我们放弃这个know-why 的行为. 我们接受现有算法, 作为"定理"的引用, 而非作为一个严谨算数逻辑推导的结果.


CRC要素:
1. 多项式除法
在进行 CRC 计算之前, 我们不得不重温多项式除法. 检索:  http://certmaths.ilongman.com/chi/ppt/ch03/lecture03_02c.ppt 的 ppt 文档.
大致我们知道: 多项式除以单项式时, 我们可以使用分配率. 而多项式除以多项式时, 我们必须使用长除法.

2. CRC原理
简单描述: 把待传送的数据 M 的二进制码序列看成多项式 M, 事先选定一个 r+1 bit 的二进制数看成多项式 P, 把多项式 M 除以 P, 得到商Q 和余数 R(r bit), 把余数 R 附加在信息码 M 一起发送. 在接收端, 使用同样的 M/P 获取余数 R', 与 R 比较验证 M 是否正确.
引用讨论: http://topic.csdn.net/u/20090625/09/d3121402-443c-4d6d-be2d-6746f9434c72.html

举例说明:
信息位: 1011001
CRC码: 4位 r = 4
校验多项式(生成码): 11001 (x4+x3+1)
运算步骤: 1011001 -> 左移4位 -> 10110010000 -> 除以 11001 -> 遵守运算法则: 不借位除法, 即异或运算, 得到结果(余数) 1010, 即为 CRC 码.

3. 例程实现:
CRC的算法包括: 基本算法, 字节查表法, 半字节查表法
我们主要讨论 16 bit 的 CRC 实现, 使用 CRC16-CCITT, 也即是 X16+X12+X5+1, 生成码为 0x1021. 本来实际值应该是 0x010121, 这里又引入了一个运算法则: "最高位一定为1故抛弃", 因此是 0x1021.

3.1 基本算法:
http://read.pudn.com/downloads90/sourcecode/embed/341559/crc.c__.htm

/**************************************************************** 
 *函数性质：公共 
 *入口：要进行CRC校验的数据缓冲unsigned char *ptr，要进行CRC校验的数据长度 
 *出口：CRC计算结果 
 *功能：CRC16计算（计算速度慢，程序空间小） 
 *调用方式：unsigned short CalCRC16Slow(unsigned char *ptr, unsigned char len) 
*****************************************************************/  
#if CRC16 == CRC16SLOW   
unsigned short CalCRC16Slow(unsigned char *ptr, unsigned char len)  
{  
    unsigned char i;  
    unsigned short crc = 0;  
    while(len--!=0)   
    {  
        for(i = 0x80; i != 0; i/=2)   
        {  
            if((crc&0x8000)!=0)   
            {  
                crc*=2;   
                crc^=0x1021;  
            }                                           /* 余式CRC乘以2再求CRC  */  
            else crc*=2;  
            if((*ptr&i)!=0) crc^=0x1021;                /* 再加上本位的CRC */  
        }  
        ptr++;  
    }  
    return(crc);  
}  
#endif   
注: 我们未验证该例程. 并注意到这里又引入了一个运算法则: 使用模2的方式, 进行异或运算(应该指不借位除法).

使用半字节查表法之CRC16的code sample(一)
使用半字节查表法之CRC16的code sample(二)