CRC

校验原理

• 循环校验码（CRC 码）：是数据通信领域中最常用的一种差错校验码，其特
  征是信息字段和校验字段的长度可以任意选定。
• 生成 CRC 码的基本原理：任意一个由二进制位串组成的代码都可以和一个系
  数仅为‘0’ 和‘1’取值的多项式一一对应。例如： 代码 1010111 对应的多项式
  为 x^6 +x^4 +x^2+x+1，而多项式为 x^5+x3+x^2+x+1 对应的代码 101111。
• CRC 码集选择的原则：若设码字长度为 N，信息字段为 K 位，校验字段为 R位(N=K+R)， 则对于 CRC 码集中的任一码字， 存在且仅存在一个 R 次多项式 g(x)，使得V(x)=A(x)g(x)=xRm(x)+r(x);
  其中: m(x)为 K 次信息多项式， r(x)为 R-1 次校验多项式，
  g(x)称为生成多项式：
  发送方通过指定的 g(x)产生 CRC 码字，接收方则通过该 g(x)来验证收到的 CRC码字。
• CRC 校验码软件生成方法：
  借助于多项式除法，其余数为校验字段。
  例如：信息字段代码为: 1011001；对应 m(x)=x^6+x4+x^3+1
  假设生成多项式为：g(x)=x^4+x3+1；则对应 g(x)的代码为: 11001
  采用多项式除法: 得余数为: 1010 (即校验字段为：1010）
  发送方：发出的传输字段为: 1 0 1 1 0 0 1 1 0 10
  信息字段 校验字段
  接收方：使用相同的生成码进行校验:接收到的字段/生成码（二进制除法）
  如果能够除尽，则正确

代码分析

基础代码

#define MASK 0x1021

typedef unsigned char uchar;
typedef unsigned int uint;
code uchar crcbuff [] = { 0x00,0x00,0x00,0x00,0x06,0x0d,0xd2,0xe3};

uint crc; // CRC 码
void main(void)
{
uchar *ptr;
crc = 0; // CRC 初值
ptr = crcbuff; // 指向第一个 Byte 数据
crc = crc16l(ptr,8);
while(1);
}
uint crc16l(uchar *ptr,uchar len) // ptr 为数据指针，len 为数据长度
{
uchar i;
while(len--)
{
for(i=0x80; i!=0; i>>=1)
{
if((crc&0x8000)!=0) {crc<<=1; crc^=MASK;} 1-1
else crc<<=1; 1-2
if((*ptr&i)!=0) crc^=MASK; 1-3
}
ptr++;
}
return(crc);
}
执行结果 crc = 0xdbc0;
程序 1-1,1-2,1-3 可以理解成移位前 crc 的 Bit15 与数据对应的 Bit(*ptr&i)
做 XOR 运算，根据此结果来决定是否执行 crc^=0x1021。只要明白两次异或
运算与原值相同，就不难理解这个程序

优化代码

不难看出，余式有 256 种可能的值，实际上就是 0~255 以 X16+X12+X5+1
为权得到的 CRC 码，可以通过函数 crc16l 来计算。

code uint crc_ta[256]={ // X16+X12+X5+1 余式表
0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50a5, 0x60c6, 0x70e7,
0x8108, 0x9129, 0xa14a, 0xb16b, 0xc18c, 0xd1ad, 0xe1ce, 0xf1ef,
0x1231, 0x0210, 0x3273, 0x2252, 0x52b5, 0x4294, 0x72f7, 0x62d6,
0x9339, 0x8318, 0xb37b, 0xa35a, 0xd3bd, 0xc39c, 0xf3ff, 0xe3de,
0x2462, 0x3443, 0x0420, 0x1401, 0x64e6, 0x74c7, 0x44a4, 0x5485,
0xa56a, 0xb54b, 0x8528, 0x9509, 0xe5ee, 0xf5cf, 0xc5ac, 0xd58d,
0x3653, 0x2672, 0x1611, 0x0630, 0x76d7, 0x66f6, 0x5695, 0x46b4,
0xb75b, 0xa77a, 0x9719, 0x8738, 0xf7df, 0xe7fe, 0xd79d, 0xc7bc,
0x48c4, 0x58e5, 0x6886, 0x78a7, 0x0840, 0x1861, 0x2802, 0x3823,
0xc9cc, 0xd9ed, 0xe98e, 0xf9af, 0x8948, 0x9969, 0xa90a, 0xb92b,
0x5af5, 0x4ad4, 0x7ab7, 0x6a96, 0x1a71, 0x0a50, 0x3a33, 0x2a12,
0xdbfd, 0xcbdc, 0xfbbf, 0xeb9e, 0x9b79, 0x8b58, 0xbb3b, 0xab1a,
0x6ca6, 0x7c87, 0x4ce4, 0x5cc5, 0x2c22, 0x3c03, 0x0c60, 0x1c41,
0xedae, 0xfd8f, 0xcdec, 0xddcd, 0xad2a, 0xbd0b, 0x8d68, 0x9d49,
0x7e97, 0x6eb6, 0x5ed5, 0x4ef4, 0x3e13, 0x2e32, 0x1e51, 0x0e70,
0xff9f, 0xefbe, 0xdfdd, 0xcffc, 0xbf1b, 0xaf3a, 0x9f59, 0x8f78,
0x9188, 0x81a9, 0xb1ca, 0xa1eb, 0xd10c, 0xc12d, 0xf14e, 0xe16f,
0x1080, 0x00a1, 0x30c2, 0x20e3, 0x5004, 0x4025, 0x7046, 0x6067,
0x83b9, 0x9398, 0xa3fb, 0xb3da, 0xc33d, 0xd31c, 0xe37f, 0xf35e,
0x02b1, 0x1290, 0x22f3, 0x32d2, 0x4235, 0x5214, 0x6277, 0x7256,
0xb5ea, 0xa5cb, 0x95a8, 0x8589, 0xf56e, 0xe54f, 0xd52c, 0xc50d,
0x34e2, 0x24c3, 0x14a0, 0x0481, 0x7466, 0x6447, 0x5424, 0x4405,
0xa7db, 0xb7fa, 0x8799, 0x97b8, 0xe75f, 0xf77e, 0xc71d, 0xd73c,
0x26d3, 0x36f2, 0x0691, 0x16b0, 0x6657, 0x7676, 0x4615, 0x5634,
0xd94c, 0xc96d, 0xf90e, 0xe92f, 0x99c8, 0x89e9, 0xb98a, 0xa9ab,
0x5844, 0x4865, 0x7806, 0x6827, 0x18c0, 0x08e1, 0x3882, 0x28a3,
0xcb7d, 0xdb5c, 0xeb3f, 0xfb1e, 0x8bf9, 0x9bd8, 0xabbb, 0xbb9a,
0x4a75, 0x5a54, 0x6a37, 0x7a16, 0x0af1, 0x1ad0, 0x2ab3, 0x3a92,
0xfd2e, 0xed0f, 0xdd6c, 0xcd4d, 0xbdaa, 0xad8b, 0x9de8, 0x8dc9,
0x7c26, 0x6c07, 0x5c64, 0x4c45, 0x3ca2, 0x2c83, 0x1ce0, 0x0cc1,
0xef1f, 0xff3e, 0xcf5d, 0xdf7c, 0xaf9b, 0xbfba, 0x8fd9, 0x9ff8,
0x6e17, 0x7e36, 0x4e55, 0x5e74, 0x2e93, 0x3eb2, 0x0ed1, 0x1ef0
};
根据这个思路，可以写出以下程序：
uint table_crc(uchar *ptr,uchar len) // 字节查表法求 CRC
{
uchar da;
while(len--!=0)
{
da=(uchar) (crc/256); // 以 8 位二进制数暂存 CRC 的高 8 位
crc<<=8; // 左移 8 位
crc^=crc_ta[da^*ptr]; // 高字节和当前数据 XOR 再查表
ptr++;
}
return(crc);
}