• 循环冗余检验CRC

在学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;   
  }