CRC校验---之avrbootloader

#include

这是计算单个字节的CRC（旧crc与data生成）

static __inline__ uint16_t _crc_xmodem_update(uint16_t __crc, uint8_t __data)；
多项式Polynomial: x^16 + x^12 + x^5 + 1 (0x1021)
crc初始值Initial value: 0x0
专用于XMODEM通讯协议，等效于C写的
uint16_t crc_xmodem_update (uint16_t crc, uint8_t data)
{
int i;
crc = crc ^ ((uint16_t)data << 8);
for (i=0; i<8; i++)
{
if (crc & 0x8000)

crc = (crc << 1) ^ 0x1021;
else
crc <<= 1;
}
return crc;
}

下面是计算count个数据（*ptr）的CRC。

先计算第一个字节数据的CRC，然后计算下一个字节数据的CRC。依次计算其余数据的CRC。所有的字符处理完成后CRC寄存器内的值即为最终的CRC值。

//计算CRC16
unsigned int calcrc(unsigned char *ptr, unsigned char count)
{
unsigned int crc = 0;
while (count--)
{
crc =_crc_xmodem_update(crc,*ptr++);
}
return crc;
}

在主函数里是这样调用的

crc=strXMODEM.CRC16hi<<8;
crc+=strXMODEM.CRC16lo;

crc为主机发送过来的校验码

//AVR的16位整数是低位在先，XMODEM的CRC16是高位在先
if(calcrc(&strXMODEM.Xdata[0],128)!=crc) //计算收到的数据的CRC，并判断是否与主机发送过来的CRC

//相等，若不相等，数据出错，要求重发当前数据块

{
put_c(XMODEM_NAK); //CRC错误，要求重发当前数据块

continue;
}

==================================================

下面为CRC的计算过程：
1．设置CRC寄存器，并给其赋值0000(hex)。
2．将数据的第一个8-bit字符与16位CRC寄存器的高8位进行异或，并把结果存入CRC寄存器。
3．CRC寄存器向左移一位，LSB补零，移出并检查MSB。
4．如果MSB为0，重复第三步；若MSB为1，CRC寄存器与多项式码相异或。
5．重复第3与第4步直到8次移位全部完成。此时一个8-bit数据处理完毕。
6．重复第2至第5步直到所有数据全部处理完成。
7．最终CRC寄存器的内容即为CRC值。

CRC校验采用多项式编码方法。
被处理的数据块可以看作是一个二进制多项式，例如，10110101可以看作是2^7+2^5+2^4+2^2+2^0,多项式乘除法运算过程与普通代数多项式的乘除法相同。多项式的加减法运算以2为模，加减时不进，错位，和逻辑异或运算一致。
采用CRC校验时，发送方和接收方用同一个生成多项式g（x）,并且g（x）的首位和最后一位的系数必须为1。CRC的处理方法是：发送方以g（x）去除t（x），得到余数作为CRC校验码。校验时，以计算的校正结果是否为0为据，判断数据帧是否出错。

CRC 校验码的算法分析
CRC 校验码的编码方法是用待发送的二进制数据t（x）除以生成多项式g（x），将最后的余数
作为CRC 校验码。其实现步骤如下：
（1） 设待发送的数据块是m 位的二进制多项式t（x），生成多项式为r 阶的g（x）。在数据块
的末尾添加r个0，数据块的长度增加到m+r位，对应的二进制多项式为xr t(x)。
（2） 用生成多项式g（x）去除xr t(x)，求得余数为阶数为r-1 的二进制多项式y（x）。此二进
制多项式y（x）就是t（x）经过生成多项式g（x）编码的CRC 校验码。
（3） 用xr t(x)以模2 的方式减去y（x），得到二进制多项式xr t(x)。xr t(x)就是包含了CRC
校验码的待发送字符串。
从 CRC 的编码规则可以看出，CRC 编码实际上是将代发送的m 位二进制多项式t（x）转换成
了可以被g（x）除尽的m+r位二进制多项式xr t(x)，所以解码时可以用接受到的数据去除g（x），
如果余数位零，则表示传输过程没有错误；如果余数不为零，则在传输过程中肯定存在错误。许多
CRC 的硬件解码电路就是按这种方式进行检错的。同时xr t(x)可以看做是由t（x）和CRC校验码
的组合，所以解码时将接收到的二进制数据去掉尾部的r 位数据，得到的就是原始数据。
为了更清楚的了解 CRC 校验码的编码过程，下面用一个简单的例子来说明CRC 校验码的编码
过程。由于CRC-32、CRC-16、CCITT 和CRC-4 的编码过程基本一致，只有位数和生成多项式不
一样。为了叙述简单，用一个CRC-4 编码的例子来说明CRC 的编码过程。
设待发送的数据 t（x）为12 位的二进制数据100100011100；CRC-4 的生成多项式为g（x）
= x4 + x +1，阶数r为4，即10011。首先在t（x）的末尾添加4 个0 构成x4t(x)，数据块就成了
1001000111000000。然后用g（x）去除x4t(x)，不用管商是多少，只需要求得余数y（x）。下表为
给出了除法过程。

从上面表中可以看出，CRC 编码实际上是一个循环移位的模2 运算。对

CRC-4，我们假设有一个5 bits 的寄存器，通过反复的移位和进行CRC 的除

法，那么最终该寄存器中的值去掉最高一位
就是我们所要求的余数。所以可以将上述步骤用下面的流程描述：
//reg 是一个5 bits 的寄存器
把 reg 中的值置0.
把原始的数据后添加r 个0.
While (数据未处理完)
Begin
If (reg 首位是1)
reg = reg XOR 0011.
把reg 中的值左移一位，读入一个新的数据并置于register 的0 bit 的位置。
End
reg 的后四位就是我们所要求的余数。
这种算法简单，容易实现，对任意长度生成多项式的G（x）都适用。在发

送的数据不长的情
况下可以使用。但是如果发送的数据块很长的话，这种方法就不太适合了。

它一次只能处理一位数
据，效率太低。为了提高处理效率，可以一次处理4 位、8 位、16 位、32

位。由于处理器的结构基
本上都支持8 位数据的处理，所以一次处理8 位比较合适。
为了对优化后的算法有一种直观的了解，先将上面的算法换个角度理解一下

。在上面例子中，
可以将编码过程看作如下过程：
由于最后只需要余数，所以我们只看后四位。构造一个四位的寄存器reg，

初值为0，数据依
次移入reg0（reg 的0 位），同时reg3 的数据移出reg。有上面的算法可以

知道，只有当移出的数据
为1 时，reg 才和g（x）进行XOR 运算；移出的数据为0 时，reg 不与g（x

）进行XOR 运算，相
当与和0000 进行XOR 运算。就是说，reg 和什么样的数据进行XOR 移出的

数据决定。由于只有一
个bit，所以有21种选择。上述算法可以描述如下，
//reg 是一个4 bits 的寄存器
初始化 t[]={0011,0000}
把reg 中的值置0.
把原始的数据后添加r 个0.
While (数据未处理完)
Begin
把reg 中的值左移一位，读入一个新的数据并置于register 的0 bit 的位置。
reg = reg XOR t[移出的位]
End
上面算法是以bit 为单位进行处理的，可以将上述算法扩展到8 位，即以

Byte 为单位进行处理，
即CRC-32。构造一个四个Byte 的寄存器reg，初值为0x00000000，数据依

次移入reg0（reg 的0
字节，以下类似），同时reg3 的数据移出reg。用上面的算法类推可知，移

出的数据字节决定reg 和
什么样的数据进行XOR。由于有8 个bit，所以有28种选择。上述算法可以描

述如下：
//reg 是一个4 Byte 的寄存器
初始化 t[]＝{…}//共有28＝256 项
把 reg 中的值置0.
把原始的数据后添加r/8 个0 字节.
While (数据未处理完)
Begin
把reg 中的值左移一个字节，读入一个新的字节并置于reg 的第0 个byte 的

位置。
reg = reg XOR t[移出的字节]
End