在学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;
      }
    }
  }
}
CRC-32校验:
      前面介绍的串行方法,对于任意长度的生成多项式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);
          }
    }
运用查表法来完成CRC-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;   
  }