CRC32概述以及实现和使用

一、CRC16实现

思路：取一个字符(8bit)，逐位检查该字符，如果为1，crc^crc_mul;同时，如果原本crc最高位是1，那么crc^crc_mul后左移1位，否则只是左移一位。计算完一个字符后，装入下一个字符。

#include<stdio.h>

#define crc_mul 0x1021  //生成多项式

unsigned int cal_crc16(unsigned char *ptr, unsigned char len)
{
    unsigned char i;
    unsigned int crc=0;
    while(len-- != 0)
    {
        for(i=0x80; i!=0; i>>=1)
        {
            if((crc&0x8000)!=0)
            {
               crc<<=1;
               crc^=(crc_mul);
            }else{
               crc<<=1;
            }
            if((*ptr&i)!=0)
            {
               crc ^= (crc_mul);
            }
        }
        ptr++;
    }
    return (crc);
}

int main()
{
    unsigned char i[8] = {0x00,0x00,0x00,0x00,0x06,0x0d,0xd2,0xe3};
    unsigned int crc;
    crc=cal_crc16(i,8);
    return 0;
} 

/*结果：0x7123dbc0*/

二、CRC32编码字符表

世界上一共就256个字符，把每个字符的CRC都算出来存入数组，因此，就有了CRC编码字符表

unsigned int CRC;//int的大小是32位，作32位CRC寄存器
unsigned int CRC_32_Table[256];//用来保存CRC码表
void GenerateCRC32_Table()
{
   for(int i=0;i<256;++i)//用++i以提高效率
{      CRC=i;
       for(int j=0;j<8;++j)
         {
           if(CRC&1)// LSM为1
           CRC=(CRC>>1)^0xEDB88320;//采取反向校验
           else //0xEDB88320就是CRC-32多项表达式的reversed值
            CRC>>=1;
         }
     CRC_32_Table[i]=CRC;
  }
}

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#include<stdio.h>
unsigned int CRC32_table[256] = {0};
void init_CRC32_table()
{
  for (int i = 0; i != 256; i++)
  {
    unsigned int CRC = i;
    for (int j = 0; j != 8; j++)
    {
      if (CRC & 1)
        CRC = (CRC >> 1) ^ 0xEDB88320;
      else
        CRC >>= 1;
    }
    CRC32_table[i] = CRC;
  }
}
unsigned int GetCRC32(unsigned char* buf, unsigned int len)
{
  unsigned int CRC32_data = 0xFFFFFFFF;
  for (unsigned int i = 0; i != len; ++i)
  {
    unsigned int t = (CRC32_data ^ buf[i]) & 0xFF;
    CRC32_data = ((CRC32_data >> 8) & 0xFFFFFF) ^ CRC32_table[t];
  }
  return ~CRC32_data;
}

int main()
{
    unsigned char i[8] = {0x00,0x00,0x00,0x00,0x06,0x0d,0xd2,0xe3};
    init_CRC32_table();
    printf("BUFFER i's CRC32: 0x%x\n", GetCRC32(i,8));
    printf("CRC32 TABLE:\n");
    for(int i=0;i<256;i++)
    {
         printf("0x%8x\t",CRC32_table[i]);
         if((i+1)%8 == 0)
             printf("\n");
    }
} 

三、CRC校验原理

在对信息的处理过程中，我们可以将要被处理的数据块M看成一个n阶的二进制多项式，其形式如下

CRC校验就是基于这种多项式进行的运算，以GF(2)(The integers modulo 2)多项式算术为数学基础，即 （模-2）除法余数运算（其实说白了就是异或Xor)

使用的除数不同，CRC的类型也就不一样。CRC传输实际上就是在长度为 k 的数据后面添加供差错检测(Frame Check Sequence) 用的 r 位冗余码（Redundant code 没错CRC里面的R就是这个），使原数据构成 n = k + r 位并发送出去, 此方式又叫（n, k）码。可以证明存在一个最高次幂为n-k=r的多项式G(x),  根据G(x)可以生成k位信息的校验码，而 G(x) 叫做这个CRC码的生成多项式( Poly )。而根据 k 值的不同，就形成了不同的CRC码的生成多项式，以下为各种常用的多项表达式：

这些多项表达式的值便是(模-2)除法的除数，本文这里选取CRC-32多项式（即为对应除数）格式，通过取余做操，获取CRC检验码。

四、CRC的生成多项式

一般来说CRC有多种实现方式，在本文中我们以C语言为例，并给出 直接生成法 和 查表法 两个例子。

直接生成法 适用于 CRC 次幂较小的格式，当CRC 次幂逐渐增高时，因为其复杂的Xor 逻辑运算会拖累系统运行速度，不再建议使用直接生成法，取而代之的是查表法——将数据块M 的一部分提前运算好，并将结果存入数组中，系统开始执行运算时，相当于省去了之前的操作，直接从类似中间的位置开始计算，所以会提高效率。

在计算CRC时也可以选择正向校验（Normal） 或者反向校验（Reversed），由于 Normal 和 Reversed 是镜像关系，两种方法会影响到最后的校验码，使得两种方式最后得到的校验码呈现镜像关系。 但这对CRC 本身的成功率并没有影响，只不过是： 正向走一遍，还是镜像走一遍罢了。

那为什么还会有Reversed格式呢？ 是因为在大多数硬件系统的传输中，普遍先发送LSB，而Reversed 的CRC 正是满足于这种LSB First 的格式，因此适用。

五、Q & A

Q: 为什么寄存器初始化置0？

A: 寄存器的初始值不为 0，那么寄存器中的值就相当于是待测数据，这样算出的 CRC 结果并不正确。再考虑CRC32 模型的 Init=0xFFFFFFFF，待测数据的内容和长度为随机，如果寄存器初始值为 0，那么待测字节则为 1 字节 0x00，计算出来的 CRC32 值也就为 0。寄存器用0xFFFFFFFF 进行初始化，就可以避免这个问题

Q：为什么先移位再XOR？

A: 0xEDB88320已经是Gx 去掉最高项的简写，为了确保运算无误，所以需要先移位再XOR。这不会影响最后的结果，因为在做XOR运算时，gx 的最高位都会被消掉（因为在除法运算中每次循环都是从1 开始除， 而gx 的最高项就是1，所以每次都会被消掉）

Q: 查表法的index 是什么，而内容又是什么？

A: Index 为数据块M 的前8位，内容是前8位与CRC XOR后的值，用时需再与gx异或。

Q: 查表法为什么会有256个字符？

A: 在CRC-16和32中，一次移出的待测数据为 8 位 bits，即一次进行一个字节的计算，则表格有 2^8＝256 个表值。一个字节有8位二进制数，每一位都有2种选择。