在学TCP/IP中,关于Ethernet帧结构中的最后一部分帧校验字段FCS(4B),在编程通信程序时,我们需对数据链路层通信Ethernet帧进行校验,即对帧校验字段FCS进行校验。FCS采用32位CRC校验。校验的范围包括目的地址、源地址字段、类型字段、数据字段。在接受段进行校验,如果发现错误,帧将被丢弃。
下面是关于CRC的循序渐进的知识:
循环冗余码校验(CRC=cyclic redundancy check),是一个信息字段和校验字段的长度可以任意选定的差错校验码。
原理:任意一个由二进制位串组成的代码都可以和一个系数仅为‘0’和‘1’取值的多项式一一对应。例如:代码1010111对应的多项式为x6+x4+x2+x+1,而多项式为x5+x3+x2+x+1对应的代码101111。发过来看:x8+ x2+x1+1= 1*x8+0*x7+ 0*x6+0*x5+0*x4+1*x2+1*x1+1*1,所得到的代码是100000111。
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)=g0+g1x1+ g2x2+...+g(R-1)x(R-1)+gRxR。发送方通过指定的g(x)产生CRC码字,接收方则通过该g(x)来验证收到的CRC码字。
CRC校验码软件生成方法:借助于多项式除法,其余数为校验字段。例如:信息字段代码为: 1011001;对应m(x)=x6+x4+x3+1 。假设生成多项式为:g(x)=x4+x3+1;则对应g(x)的代码为: 11001 。x4m(x)=x10+x8+x7+x4 对应的代码记为:10110010000;x4m(x)/ g(x)即采用多项式除法(如何运算见下段): 得余数为: 1010 (即校验字段为:1010)。发送方:发出的传输字段为: 1 0 1 1 0 0 1 1010(信息字段 校验字段)。接收方:使用相同的生成码进行校验:接收到的字段/生成码(二进制除法)如果能够除尽,则正确。
给出余数(1010)的计算步骤:除法没有数学上的含义,而是采用计算机的模二除法,即,除数和被除数做异或运算。进行异或运算时除数和被除数最高位对齐,按位异或。
1011001 0000
-11001
--------------------------
=01111010000
1111010000
-11001
-------------------------
=0011110000
11110000
-11001
--------------------------
=00111000
111000
- 11001
-------------------
= 001010
以下是8位CRC校验为例:
关于CRC校验实现的方法有很多,简单起见,采用8位CRC校验,其生成多项式为G(x)= x8+ x2+x1+1。例:一个实现CRC-8的硬件电路:由8个移位寄存器和3个异或单元组成。
计算过程如下:
(1)开始编码解码前所有寄存器清0。
(2)输入位作为最左边异或或操作的输入之一,8个寄存器上的移位操作同时进行,均为左移一位。
(3)每次移位时寄存器R7的输出作为所有3个异或操作的输入之一,寄存器R0的输出作为中间异或操作的输入之一,寄存器R1的输出作为最左边异或操作的输入之一。
(4)各个异或操作的结果作为它左边那个寄存器的输入位。
(5)重复以上操作,每输入一位就做一次移位操作,直到输入了所有要计算的数据为止。这时,这个寄存器组中的数据就是CRC-8的结果。
以1010为例,将1010后补8个0所得的比特序列(即101000000000)当做输入值,8个移位寄存器组中的值为00110110。该结果与101000000000除以100000111(G(x)= x8+ x2+x1+1)所得的余数相同。
对上面计算过程分析可以得到,当寄存器R7的移出位为1时,寄存器组才和00000111进行XOR运算;移出位为0时,不做运算。每次寄存器中的数据左移后就需要从输入数据中读入一位新的数据,如果读入的新数据为1,则需要把寄存器R0置为1,然后再判断寄存器是否需要与00000111进行XOR运算。
思路:
//register8是一个8位的寄存器,把register8中的值置为0,在原始数据后添加8个0(因为校验字段为8位,得到的是x8 m(x))
While(数据未处理完) { if(register8首位是1) { register8中的数据左移1位; if(从输入中读入的新数据为1) { 将register8的最低位置1; } register8= register8 XOR 00000111 } else { register8中的数据左移1位; if(从输入中读入的新数据为1) { 将register8的最低位置1; } } }
void checkCRC(int &chCurrByte, int chNextByte) { // CRC循环:每次调用进行8次循环,处理一个字节的数据。 for (int nMask = 0x80; nMask > 0; nMask >>= 1) { if ((chCurrByte & 0x80) != 0) // 首位为1:移位,并进行异或运算 { chCurrByte <<= 1; // 移一位 if ( (chNextByte & nMask) != 0) // 补一位 { chCurrByte |= 1; } chCurrByte ^= 7; // 首位已经移出,仅对低8位进行异或运算,7的二进制为0000,0111 } else // 首位为0,只移位,不进行异或运算 { chCurrByte <<= 1; // 移一位 if ( (chNextByte & nMask) != 0) // 补一位 { chCurrByte |= 1; } } } }
前面介绍的串行方法,对于任意长度的生成多项式G(x)都是适用。如果发送的数据块很长的话,这种方法就不太合适,效率太低。为了提高效率,可以一次处理8,16或32位。
Ethernet一般是对一帧数据进行CRC校验,而字节是帧的基本单位,所以最常用的CRC校验算法是按字节查表的快速算法:本字节后的CRC码,等于上一节CRC右移8位和本字节之和再与上一字节余式CRC码的低8位左移8位相加所求的CRC码。如果把8位二进制序列数的CRC(共256个)全部计算出来放在一个表中,编码时只要从表中查找对应的值进行处理即可。
下面给出网上搜到的参数表生成程序:
#include <stdio.h> unsigned long int crc32_table[256]; unsigned long int ulPolynomial = 0x04c11db7; unsigned long int Reflect(unsigned long int ref, char ch) { unsigned long int value(0); // 交换bit0和bit7,bit1和bit6,类推 for(int i = 1; i < (ch + 1); i++) { if(ref & 1) value |= 1 << (ch - i); ref >>= 1; } return value; } init_crc32_table() { unsigned long int crc,temp; // 256个值 for(int i = 0; i <= 0xFF; i++) { temp=Reflect(i, 8); crc32_table[i]= temp<< 24; for (int j = 0; j < 8; j++){ unsigned long int t1,t2; unsigned long int flag=crc32_table[i]&0x80000000; t1=(crc32_table[i] << 1); if(flag==0) t2=0; else t2=ulPolynomial; crc32_table[i] =t1^t2 ; } crc=crc32_table[i]; crc32_table[i] = Reflect(crc32_table[i], 32); } }
unsigned long crc_32_tab[256]= {0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f, 0xe963a535 , 0x9e6495a3,0x0edb8832,…, 0x5a05df1b, 0x2d02ef8d };//事先计算出的参数表,共有256项,未全部列出。 unsigned long GenerateCRC32(char xdata * DataBuf,unsigned long len) { unsigned long oldcrc32; unsigned long crc32; unsigned long oldcrc; unsigned int charcnt; char c,t; oldcrc32 = 0x00000000; //初值为0 charcnt=0; while(len--) { t= (oldcrc32 >> 24)&0xFF; //要移出的字节的值 oldcrc=crc_32_tab[t]; //根据移出的字节的值查表 c=DataBuf[charcnt]; //新移进来的字节值 oldcrc32= (oldcrc32 << 8) | c; //将新移进来的字节值添在寄存器末字节中 oldcrc32=oldcrc32^oldcrc; //将寄存器与查出的值进行xor运算 charcnt++; } crc32=oldcrc32; return crc32; }