CRC校验详解（附代码示例）

心已赠人 2023-05-30 06:28 8阅读 0赞

CRC校验即循环冗余校验（Cyclic Redundancy Check），是基于数据计算一组效验码，用于核对数据传输过程中是否被更改或传输错误。首先看两个概念，后续会用到。

*  模2除法：也叫模2运算，就是结果除以2后取余数。模2除法每一位除的结果不影响其它位，即不向上一位借位，所以实际上就是异或。在CRC计算中有应用到模2除法。
 *  多项式与二进制：二进制可表示成多项式的形式，比如二进制1101表示为： x3+x2+x0；1011表示为：x3+x1+x0。

### 1.CRC校验原理 ###

**CRC校验本质上是选取一个合适的除数，要进行校验的数据是被除数，然后做模2除法，得到的余数就是CRC校验值。**

下面用具体的例子做讲解：给定一组数据A：10110011（二进制），选取除数B：11001。

1.  首先需要在被除数A后加4个比特位0（具体加几个0是根据除数B的位数决定的，比如这里B是5位，那么A后面加4个0；如果B选6位，则A后面加5个0，总之加的0的个数比除数B的个数少1位。后面还会提到怎么添加）。
2.  进行模2除法运算。注意每次都是模2运算，即异或。
3.  最后得到余数C就是CRC校验值。注意余数位数必须比除数少1位，如果不够前面加0补齐。运算如下图所示

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ExNDQ5NTE2NDg3_size_16_color_FFFFFF_t_70][]

## 2.生成多项式 ##

第1章讲解了CRC校验的基本原理，通常我们把选取的除数称之为“生成多项式”。事实上，生成多项式的选取是由一定标准的，如果选的不好，那么检出错误的概率就会低很多。好在这个问题已经被专家们研究了很长一段时间了，对于我们这些使用者来说，只要把现成的成果拿来用就行了。下表是一些标准的CRC生成多项式，可以直接使用。

<table style="width:500px;">  标准CRC生成多项式  
 <thead> 
  <tr> 
   <th>名称</th> 
   <th>生成多项式</th> 
   <th>简记式</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>CRC-4</td> 
   <td>x4+x+1</td> 
   <td>0x03</td> 
  </tr> 
  <tr> 
   <td>CRC-8</td> 
   <td>x8+x5+x4+1</td> 
   <td>0x31</td> 
  </tr> 
  <tr> 
   <td>CRC-8</td> 
   <td>x8+x2+x1+1</td> 
   <td>0x07</td> 
  </tr> 
  <tr> 
   <td>CRC-8</td> 
   <td>x8+x6+x4+x3+x2+x1</td> 
   <td>0x5E</td> 
  </tr> 
  <tr> 
   <td>CRC-12</td> 
   <td>x12+x11+x3+x+1&nbsp;</td> 
   <td>0x080F</td> 
  </tr> 
  <tr> 
   <td>CRC-16</td> 
   <td>x16+x15+x2+1</td> 
   <td>0x8005</td> 
  </tr> 
  <tr> 
   <td>CRC16-CCITT</td> 
   <td>x16+x12+x5+1</td> 
   <td>0x1021</td> 
  </tr> 
  <tr> 
   <td>CRC-32</td> 
   <td>x32+x26+x23+...+x2+x+1</td> 
   <td>0x04C11DB7</td> 
  </tr> 
 </tbody> 
</table>

有一点要特别注意，讨论生成多项式经常会说到多项式的位宽（Width，简记为W），这个位宽不是多项式对应的二进制数的位数，而是位数减1。比如CRC8中用到的位宽为8的生成多项式，其实对应得二进制数有九位：100110001。另外一点，多项式表示和二进制表示都很繁琐，交流起来不方便，因此，多用16进制简写法来表示，因为生成多项式的最高位肯定为1，最高位的位置由位宽可知，故在简记式中，将最高的1统一去掉了，如CRC32的生成多项式简记为04C11DB7实际上表示的是104C11DB7。当然，这样简记除了方便外，在编程计算时也有它的用处。所以在第一章中提到的在被除数后增加0的位数就是位宽，计算出的CRC校验值长度也是位宽。

## 3.以CRC-16校验为例讲解编程实现 ##

### 3.3.1 完全按照CRC原理实现校验 ###

实际工程中多使用CRC-16校验，即选取生成多项式为0x8005。按照前面提到的CRC校验原理，编程实现步骤如下：（注意实际编程时并不用这种直接的方法，如不想看可直接跳到3.3.2）

1.  预置1个16位的变量为CRC，此值存放CRC校验值，赋初值为0；
2.  将需要校验的字符串str后面添加16个0；
3.  如果变量CRC最高位为1，变量CRC与0x8005异或，然后将变量CRC左移1位，最低位补入1比特新的数据（来自需要校验的字符串str）；
4.  如果变量CRC最高位为0，直接将变量CRC左移1位，最低位补入1比特新的数据（来自需要校验的字符串str）；
5.  重复2-3步，直到字符串str最后1位补入变量CRC中；
6.  此时得到的余数就是CRC校验值。

这种直接的方法有一个弊端，那就是在字符串前面加0，并不影响校验值，这就不符合我们的预期了。比如，我们想校验的1字节1001 1100，现在在前面补1字节0，变成2字节0000 0000 1001 1100，结果两个得到的校验值是一样的。所以在实际应用中，CRC校验过程做了一些改变：增加了“余数初始值”、“结果异或值”、“输入数据反转”和“输出数据反转”四个概念。

### 3.3.2 工程中常用CRC校验过程 ###

*  余数初始值：即在计算开始前，先给变量CRC赋的初值。
 *  结果异或值：即在计算结束后，得到的变量CRC与这个值进行异或操作，就得到了最终的校验值。
 *  输入数据反转：即在计算开始前，将需要校验的数据反转，如数据位1011，反转后为1101。
 *  输出数据反转：即在计算结束后，与结果异或值异或之前，计算值反转，如计算结果为1011，反转后为1101。

实际应用中，生成多项式、余数初始值、结果异或值、输入数据反转和输出数据反转是有对应关系的，这些对应关系是大家都遵守的标准，如下表所示：

<table>  表3-1 常见CRC参数模型  
 <thead> 
  <tr> 
   <th>CRC算法名称</th> 
   <th>多项式公式</th> 
   <th>宽度</th> 
   <th>多项式（16进制）</th> 
   <th>初始值（16进制）</th> 
   <th>结果异或值（16进制）</th> 
   <th>输入值反转</th> 
   <th>输出值反转</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>CRC-4/ITU</td> 
   <td>x4&nbsp;+ x + 1</td> 
   <td>4</td> 
   <td>03</td> 
   <td>00</td> 
   <td>00</td> 
   <td>true</td> 
   <td>true</td> 
  </tr> 
  <tr> 
   <td>CRC-5/EPC</td> 
   <td>x4&nbsp;+ x3&nbsp;+ 1</td> 
   <td>5&nbsp;</td> 
   <td>09</td> 
   <td>09</td> 
   <td>00&nbsp;</td> 
   <td>false&nbsp;&nbsp;</td> 
   <td>&nbsp;false</td> 
  </tr> 
  <tr> 
   <td>CRC-5/ITU</td> 
   <td>x5&nbsp;+ x4&nbsp;+ x2&nbsp;+ 1</td> 
   <td>5</td> 
   <td>15</td> 
   <td>00</td> 
   <td>00</td> 
   <td>true</td> 
   <td>true</td> 
  </tr> 
  <tr> 
   <td>CRC-5/USB</td> 
   <td>x5&nbsp;+ x2&nbsp;+ 1</td> 
   <td>5</td> 
   <td>05</td> 
   <td>1F</td> 
   <td>1F</td> 
   <td>true</td> 
   <td>true</td> 
  </tr> 
  <tr> 
   <td>CRC-6/ITU</td> 
   <td>x6&nbsp;+ x + 1</td> 
   <td>6</td> 
   <td>03</td> 
   <td>00</td> 
   <td>00</td> 
   <td>true</td> 
   <td>true</td> 
  </tr> 
  <tr> 
   <td>CRC-7/MMC</td> 
   <td>x7&nbsp;+ x3&nbsp;+ 1</td> 
   <td>7</td> 
   <td>09</td> 
   <td>00</td> 
   <td>00</td> 
   <td>false</td> 
   <td>false</td> 
  </tr> 
  <tr> 
   <td>CRC-8</td> 
   <td>x8&nbsp;+ x2&nbsp;+ x + 1</td> 
   <td>8</td> 
   <td>07</td> 
   <td>00</td> 
   <td>00</td> 
   <td>false</td> 
   <td>false</td> 
  </tr> 
  <tr> 
   <td>CRC-8/ITU</td> 
   <td>x8&nbsp;+ x2&nbsp;+ x + 1</td> 
   <td>8</td> 
   <td>07</td> 
   <td>00</td> 
   <td>55</td> 
   <td>false</td> 
   <td>false</td> 
  </tr> 
  <tr> 
   <td>CRC-8/ROHC</td> 
   <td>x8&nbsp;+ x2&nbsp;+ x + 1</td> 
   <td>8</td> 
   <td>07</td> 
   <td>FF</td> 
   <td>00</td> 
   <td>true</td> 
   <td>true</td> 
  </tr> 
  <tr> 
   <td>CRC-8/MAXIM</td> 
   <td>x8&nbsp;+ x5&nbsp;+ x4&nbsp;+ 1</td> 
   <td>8</td> 
   <td>31</td> 
   <td>00</td> 
   <td>00</td> 
   <td>true</td> 
   <td>true</td> 
  </tr> 
  <tr> 
   <td>CRC-16/IBM<br> &nbsp;</td> 
   <td>x16&nbsp;+ x15&nbsp;+ x2&nbsp;+ 1</td> 
   <td>16</td> 
   <td>8005</td> 
   <td>0000</td> 
   <td>0000</td> 
   <td>true</td> 
   <td>true</td> 
  </tr> 
  <tr> 
   <td>CRC-16/MAXIM<br> &nbsp;</td> 
   <td>x16&nbsp;+ x15&nbsp;+ x2&nbsp;+ 1</td> 
   <td>16</td> 
   <td>8005</td> 
   <td>0000</td> 
   <td>FFFF</td> 
   <td>true</td> 
   <td>true</td> 
  </tr> 
  <tr> 
   <td>CRC-16/USB<br> &nbsp;</td> 
   <td>x16&nbsp;+ x15&nbsp;+ x2&nbsp;+ 1</td> 
   <td>16</td> 
   <td>8005</td> 
   <td>FFFF</td> 
   <td>FFFF</td> 
   <td>true</td> 
   <td>true</td> 
  </tr> 
  <tr> 
   <td>CRC-16/MODBUS<br> &nbsp;</td> 
   <td>x16&nbsp;+ x15&nbsp;+ x2&nbsp;+ 1</td> 
   <td>16</td> 
   <td>8005</td> 
   <td>FFFF</td> 
   <td>0000</td> 
   <td>true</td> 
   <td>true</td> 
  </tr> 
  <tr> 
   <td>CRC-16/CCITT</td> 
   <td>x16&nbsp;+ x12&nbsp;+ x5&nbsp;+ 1</td> 
   <td>16</td> 
   <td>1021</td> 
   <td>0000</td> 
   <td>0000</td> 
   <td>true</td> 
   <td>true</td> 
  </tr> 
  <tr> 
   <td>CRC-16/CCITT-FALSE</td> 
   <td>x16&nbsp;+ x12&nbsp;+ x5&nbsp;+ 1</td> 
   <td>16</td> 
   <td>1021</td> 
   <td>FFFF</td> 
   <td>0000</td> 
   <td>false</td> 
   <td>false</td> 
  </tr> 
  <tr> 
   <td>CRC-16/x5<br> &nbsp;</td> 
   <td>x16&nbsp;+ x12&nbsp;+ x5&nbsp;+ 1</td> 
   <td>16</td> 
   <td>1021</td> 
   <td>FFFF</td> 
   <td>FFFF</td> 
   <td>true</td> 
   <td>true</td> 
  </tr> 
  <tr> 
   <td>CRC-16/XMODEM<br> &nbsp;</td> 
   <td>x16&nbsp;+ x12&nbsp;+ x5&nbsp;+ 1</td> 
   <td>16</td> 
   <td>1021</td> 
   <td>0000</td> 
   <td>0000</td> 
   <td>false</td> 
   <td>false</td> 
  </tr> 
  <tr> 
   <td>CRC-16/DNP</td> 
   <td>x16&nbsp;+ x13&nbsp;+ x12&nbsp;+ x11&nbsp;+ x10&nbsp;+ x8&nbsp;+ x6&nbsp;+ x5&nbsp;+ x2&nbsp;+ 1</td> 
   <td>16</td> 
   <td>3D65</td> 
   <td>0000</td> 
   <td>FFFF</td> 
   <td>true</td> 
   <td>true</td> 
  </tr> 
  <tr> 
   <td>CRC-32<br> &nbsp;</td> 
   <td>x32&nbsp;+ x26&nbsp;+ x23&nbsp;+ x22&nbsp;+ x16&nbsp;+ x12&nbsp;+ x11&nbsp;+ x10&nbsp;+ x8&nbsp;+ x7&nbsp;+ x5&nbsp;+ x4&nbsp;+ x2&nbsp;+ x + 1</td> 
   <td>32</td> 
   <td>04C11DB7</td> 
   <td>FFFFFFFF</td> 
   <td>FFFFFFFF</td> 
   <td>true</td> 
   <td>true</td> 
  </tr> 
  <tr> 
   <td>CRC-32/MPEG-2</td> 
   <td>x32&nbsp;+ x26&nbsp;+ x23&nbsp;+ x22&nbsp;+ x16&nbsp;+ x12&nbsp;+ x11&nbsp;+ x10&nbsp;+ x8&nbsp;+ x7&nbsp;+ x5&nbsp;+ x4&nbsp;+ x2&nbsp;+ x + 1</td> 
   <td>32&nbsp;</td> 
   <td>04C11DB7</td> 
   <td>FFFFFFFF</td> 
   <td>00000000</td> 
   <td>false</td> 
   <td>false</td> 
  </tr> 
 </tbody> 
</table>

接下来以**CRC-16/IBM**校验为例，讲解工程中使用的CRC校验编程实现。具体实现时，以字节为单位进行计算。

1.  预置1个16位的变量CRC，存放校验值，首先根据表3-1赋初值0x0000；
2.  将第1个字节按照表3-1看是否需要反转，若需要，则按反转，若不需要，直接进入第3步。这里需要反转；
3.  把第1个字节按照步骤2处理后，与16位的变量CRC的高8位相异或，把结果放于变量CRC，低8位数据不变；
4.  把变量CRC的内容左移1位（朝高位）用0填补最低位，并检查左移后的移出位；
5.  如果移出位为0：重复第4步（再次左移一位）；如果移出位为1，变量CRC与多项式8005（1000 0000 0000 0101）进行异或；
6.  重复步骤4和5，直到左移8次，这样整个8位数据全部进行了处理；
7.  重复步骤2到步骤6，进行通讯信息帧下一个字节的处理；
8.  将该通讯信息帧所有字节按上述步骤计算完成后，将得到的16位变量CRC按照表3-1看是否需要反转，这里需要反转；
9.  最后，与结果异或值异或，得到的变量CRC即为CRC校验值；

**我在这里按照如上方法整理了一个通用代码，包含CRC-8，CRC-16和CRC-32。代码如下：**

type.h

#ifndef __TYPE_H__
    #define __TYPE_H__
    #include <stdio.h>
     
    typedef unsigned char        u8;
    typedef unsigned short       u16;
    typedef unsigned int         u32;
    typedef unsigned long long   u64;
     
    typedef unsigned char        BOOL;
    #define FALSE                0
    #define TRUE                 1
     
    #endif

crc.h文件

#ifndef __CRC_H__
    #define __CRC_H__
    #include "type.h"
     
    typedef struct
    {
    	u8 poly;//多项式
    	u8 InitValue;//初始值
    	u8 xor;//结果异或值
    	BOOL InputReverse;
    	BOOL OutputReverse;
    }CRC_8;
     
    typedef struct
    {
    	u16 poly;//多项式
    	u16 InitValue;//初始值
    	u16 xor;//结果异或值
    	BOOL InputReverse;
    	BOOL OutputReverse;
    }CRC_16;
     
    typedef struct
    {
    	u32 poly;//多项式
    	u32 InitValue;//初始值
    	u32 xor;//结果异或值
    	BOOL InputReverse;
    	BOOL OutputReverse;
    }CRC_32;
     
    const CRC_8 crc_8;
    const CRC_8 crc_8_ITU;
    const CRC_8 crc_8_ROHC;
    const CRC_8 crc_8_MAXIM;
     
    const CRC_16 crc_16_IBM;
    const CRC_16 crc_16_MAXIM;
    const CRC_16 crc_16_USB;
    const CRC_16 crc_16_MODBUS;
    const CRC_16 crc_16_CCITT;
    const CRC_16 crc_16_CCITT_FALSE;
    const CRC_16 crc_16_X5;
    const CRC_16 crc_16_XMODEM;
    const CRC_16 crc_16_DNP;
     
    const CRC_32 crc_32;
    const CRC_32 crc_32_MPEG2;
     
    u8 crc8(u8 *addr, int num,CRC_8 type) ;
    u16 crc16(u8 *addr, int num,CRC_16 type) ;
    u32 crc32(u8 *addr, int num,CRC_32 type) ;
     
    #endif

crc.c文件

#include <stdio.h>
    #include "type.h"
    #include "CRC.h"
     
    const CRC_8 crc_8 = {0x07,0x00,0x00,FALSE,FALSE};
    const CRC_8 crc_8_ITU = {0x07,0x00,0x55,FALSE,FALSE};
    const CRC_8 crc_8_ROHC = {0x07,0xff,0x00,TRUE,TRUE};
    const CRC_8 crc_8_MAXIM = {0x31,0x00,0x00,TRUE,TRUE};
     
    const CRC_16 crc_16_IBM = {0x8005,0x0000,0x0000,TRUE,TRUE};
    const CRC_16 crc_16_MAXIM = {0x8005,0x0000,0xffff,TRUE,TRUE};
    const CRC_16 crc_16_USB = {0x8005,0xffff,0xffff,TRUE,TRUE};
    const CRC_16 crc_16_MODBUS = {0x8005,0xffff,0x0000,TRUE,TRUE};
    const CRC_16 crc_16_CCITT = {0x1021,0x0000,0x0000,TRUE,TRUE};
    const CRC_16 crc_16_CCITT_FALSE = {0x1021,0xffff,0x0000,FALSE,FALSE};
    const CRC_16 crc_16_X5 = {0x1021,0xffff,0xffff,TRUE,TRUE};
    const CRC_16 crc_16_XMODEM = {0x1021,0x0000,0x0000,FALSE,FALSE};
    const CRC_16 crc_16_DNP = {0x3d65,0x0000,0xffff,TRUE,TRUE};
     
    const CRC_32 crc_32 = {0x04c11db7,0xffffffff,0xffffffff,TRUE,TRUE};
    const CRC_32 crc_32_MPEG2 = {0x04c11db7,0xffffffff,0x00000000,FALSE,FALSE};
     
    /*****************************************************************************
    *function name:reverse8
    *function: 字节反转，如1100 0101 反转后为1010 0011
    *input：1字节
    *output:反转后字节
    ******************************************************************************/
    u8 reverse8(u8 data)
    {
        u8 i;
        u8 temp=0;
        for(i=0;i<8;i++)	//字节反转
            temp |= ((data>>i) & 0x01)<<(7-i);
        return temp;
    }
    /*****************************************************************************
    *function name:reverse16
    *function: 双字节反转，如1100 0101 1110 0101反转后为1010 0111 1010 0011
    *input：双字节
    *output:反转后双字节
    ******************************************************************************/
    u16 reverse16(u16 data)
    {
        u8 i;
        u16 temp=0;
        for(i=0;i<16;i++)		//反转
            temp |= ((data>>i) & 0x0001)<<(15-i);
        return temp;
    }
    /*****************************************************************************
    *function name:reverse32
    *function: 32bit字反转
    *input：32bit字
    *output:反转后32bit字
    ******************************************************************************/
    u32 reverse32(u32 data)
    {
        u8 i;
        u32 temp=0;
        for(i=0;i<32;i++)		//反转
            temp |= ((data>>i) & 0x01)<<(31-i);
        return temp;
    }
     
    /*****************************************************************************
    *function name:crc8
    *function: CRC校验，校验值为8位
    *input:addr-数据首地址；num-数据长度（字节）；type-CRC8的算法类型
    *output:8位校验值
    ******************************************************************************/
    u8 crc8(u8 *addr, int num,CRC_8 type)  
    {  
        u8 data;
        u8 crc = type.InitValue;                   //初始值
        int i;  
        for (; num > 0; num--)               
        {  
            data = *addr++;
            if(type.InputReverse == TRUE)
            data = reverse8(data);                 //字节反转
            crc = crc ^ data ;                     //与crc初始值异或 
            for (i = 0; i < 8; i++)                //循环8位 
            {  
                if (crc & 0x80)                    //左移移出的位为1，左移后与多项式异或
                    crc = (crc << 1) ^ type.poly;    
                else                               //否则直接左移
                    crc <<= 1;                  
            }
        }
        if(type.OutputReverse == TRUE)             //满足条件，反转
            crc = reverse8(crc);
        crc = crc^type.xor;                        //最后返与结果异或值异或
        return(crc);                               //返回最终校验值
    }
     
    /*****************************************************************************
    *function name:crc16
    *function: CRC校验，校验值为16位
    *input:addr-数据首地址；num-数据长度（字节）；type-CRC16的算法类型
    *output:16位校验值
    ******************************************************************************/
    u16 crc16(u8 *addr, int num,CRC_16 type)  
    {  
        u8 data;
        u16 crc = type.InitValue;					//初始值
        int i;  
        for (; num > 0; num--)               
        {  
            data = *addr++;
            if(type.InputReverse == TRUE)
                data = reverse8(data);				//字节反转
            crc = crc ^ (data<<8) ;					//与crc初始值高8位异或 
            for (i = 0; i < 8; i++)					//循环8位 
            {  
                if (crc & 0x8000)					//左移移出的位为1，左移后与多项式异或
                    crc = (crc << 1) ^ type.poly;    
                else		                        //否则直接左移
                    crc <<= 1;                  
            }
        }
        if(type.OutputReverse == TRUE)              //满足条件，反转
            crc = reverse16(crc);
        crc = crc^type.xor;	                        //最后返与结果异或值异或
        return(crc);                                //返回最终校验值
    }
    /*****************************************************************************
    *function name:crc32
    *function: CRC校验，校验值为32位
    *input:addr-数据首地址；num-数据长度（字节）；type-CRC32的算法类型
    *output:32位校验值
    ******************************************************************************/
    u32 crc32(u8 *addr, int num,CRC_32 type)  
    {  
        u8 data;
        u32 crc = type.InitValue;					//初始值
        int i;  
        for (; num > 0; num--)               
        {  
            data = *addr++;
            if(type.InputReverse == TRUE)
                data = reverse8(data);				//字节反转
            crc = crc ^ (data<<24) ;				//与crc初始值高8位异或 
            for (i = 0; i < 8; i++)					//循环8位 
            {  
                if (crc & 0x80000000)				//左移移出的位为1，左移后与多项式异或
                    crc = (crc << 1) ^ type.poly;    
                else                                //否则直接左移
                    crc <<= 1;                  
            }
        }
        if(type.OutputReverse == TRUE)              //满足条件，反转
            crc = reverse32(crc);
        crc = crc^type.xor;	                        //最后返与结果异或值异或
        return(crc);                                //返回最终校验值
    }

调用时，只需传入相应的参数即可。

### 3.3.3 改进的CRC校验过程 ###

3.3.2中的代码具有通用性，但是可以看到效率不高。以crc16函数为例，需要判断字节是否需要反转，结束时，也需要判断是否需要反转，这都会耗费时间，如果需要反转，那么反转函数要花费更多时间。如何能提高效率呢？实际中我们常用某一种具体的校验方法，所以可以写单独的代码而非通用的，这样就可以省去两次判断反转的时间。以crc16/MAXIM为例，开始和结束都需要反转，改进后可以省略，具体操作如下：

/*****************************************************************************
    *function name:crc16_MAXIM
    *function: CRC校验，校验值为16位
    *input:addr-数据首地址；num-数据长度（字节）
    *output:16位校验值
    ******************************************************************************/
    u16 crc16_MAXIM(u8 *addr, int num)  
    {  
        u8 data;
        u16 crc = 0x0000;//初始值
        int i;  
        for (; num > 0; num--)             
        {  
            crc = crc ^ (*addr++) ;     //低8位异或
            for (i = 0; i < 8; i++)             
            {  
                if (crc & 0x0001)       //由于前面和后面省去了反转，所以这里是右移，且异或的值为多项式的反转值
                    crc = (crc >> 1) ^ 0xA001;//右移后与多项式反转后异或
                else                   //否则直接右移
                    crc >>= 1;                    
            }                               
        }
        return(crc^0xffff);            //返回校验值 
    }

读者可对比通用代码中crc16函数和crc16\_MAXIM函数的区别。

## 4.以CRC-8校验为例讲解查表法 ##

查表法速度快，但是表要占一部分内存，这是以空间换时间。

为了便于理解查表法，首先看3.3.2中CRC.c中u8 crc8(u8 \*addr, int num,CRC\_8 type)函数。为了方便观察，我将此段函数单独放在下面：

/*****************************************************************************
    *function name:crc8
    *function: CRC校验，校验值为8位
    *input:addr-数据首地址；num-数据长度（字节）；type-CRC8的算法类型
    *output:8位校验值
    ******************************************************************************/
    u8 crc8(u8 *addr, int num,CRC_8 type)  
    {  
        u8 data;
        u8 crc = type.InitValue;                   //初始值
        int i;  
        for (; num > 0; num--)               
        {  
            data = *addr++;
            if(type.InputReverse == TRUE)
            data = reverse8(data);                 //字节反转
            crc = crc ^ data ;                     //与crc初始值异或 
            for (i = 0; i < 8; i++)                //循环8位 
            {  
                if (crc & 0x80)                    //左移移出的位为1，左移后与多项式异或
                    crc = (crc << 1) ^ type.poly;    
                else                               //否则直接左移
                    crc <<= 1;                  
            }
        }
        if(type.OutputReverse == TRUE)             //满足条件，反转
            crc = reverse8(crc);
        crc = crc^type.xor;                        //最后返与结果异或值异或
        return(crc);                               //返回最终校验值
    }

观察上面代码，仔细发现18-24行的for循环可以生成一个表。进入for循环的变量crc大小为1个字节，即变量crc的大小可以为0-255之间的任何一个值，并且也只能是0-255之间的一个值。因此，可以实现将0-255都经过这个for循环，生成对应的值，生成的值也是0-255，这些生成的值就是crc要查的表，而传入for循环的变量crc就是表的索引值。

以下代码是生成8位crc表的代码（多项式为0x07，核心的代码为11-17行for循环）：

void GenerateCrc8Table(u8 *crc8Table)  
    {  
        u8 crc=0;
        u16 i,j;
        for(j = 0;j<256;j++)
        {
            if(!(j%16))                        //16个数为1行
                printf("\r\n");
     
            crc = (u8)j;
            for (i = 0; i < 8; i++)             
            {  
                if (crc & 0x80)               //最高位为1
                    crc = (crc << 1) ^ 0x07;  //左移后与多项式异或
                else                          //否则直接左移
                    crc <<= 1;                    
            }
            crc8Table[j] = crc;//取低字节
            printf("%2x ",crc);		
        }
        printf("\r\n");
    }

生成的表如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ExNDQ5NTE2NDg3_size_16_color_FFFFFF_t_70 1][]

需要注意的是，查表法所用的表根据多项式的不同而不同，所以再用不同多项式时，一定要重新生成对应的表。所以多项式为0x07的u8 crc8函数用查表法可以改写为如下：

/*****************************************************************************
    *function name:crc8withTable
    *function: CRC校验，校验值为8位
    *input:addr-数据首地址；len-数据长度（字节）；crc8Table-CRC8表
    *output:8位校验值
    ******************************************************************************/
    u8 crc8withTable(u8 *addr, int len,u8 *crc8Table)  
    {  
        u8 data;
        u8 crc = 00;                   //初始值
        int i;  
        for (; len > 0; len--)               
        {  
            data = *addr++;
            crc = crc ^ data ;                     //与crc初始值异或 
            crc = crc8Table[crc];                  //替换下面for循环
    //        for (i = 0; i < 8; i++)                //循环8位 
    //        {  
    //            if (crc & 0x80)                    //左移移出的位为1，左移后与多项式异或
    //                crc = (crc << 1) ^ 0x07;    
    //            else                               //否则直接左移
    //                crc <<= 1;                  
    //        }
        }
        crc = crc^0x00;                            //最后返与结果异或值异或
        return(crc);                               //返回最终校验值
    }

可以看到第16行代码替换了for循环，直接从表中取值，速度快了很多。实际在用时，需要将表写成数组放在代码前面，这样代码就可以查表了。

## 5.以CRC-16校验为例讲解查表法 ##

crc16查表法和crc8查表法类似，也是首先是生成一个表，然后再用查表代替for循环。

### 5.1.生成表格 ###

以3.3.3中的CRC16代码为例，首先生成一个表，此表每个元素都是2字节，一共256个元素。但是需要将这个表拆分成两个表，其中高字节放在crcLowTable，低字节放在crcHighTable（我也不理解为什么这样做，但是按照这样的方法确实能实现查表法）。生成表代码如下：

/*****************************************************************************
    *function name:GenerateCrc16Table
    *function: 生成crc16查表法用的表格
    *input: crcHighTable，crcLowTable:256大小的数组，即生成的表格首地址 
    *output:无
    ******************************************************************************/
    void GenerateCrc16Table(u8 *crcHighTable,u8 *crcLowTable)  
    {  
        u16 crc=0;
        u16 i,j;
        for(j = 0;j<256;j++)
        {
            if(!(j%8))
                printf("\r\n");
     
            crc = j;
            for (i = 0; i < 8; i++)             
            {  
                if (crc & 0x0001)       //由于前面和后面省去了反转，所以这里是右移，且异或的值为多项式的反转值
                    crc = (crc >> 1) ^ 0xA001;//右移后与多项式反转后异或
                else                   //否则直接右移
                    crc >>= 1;                    
            }
            crcHighTable[j] = (u8)(crc&0xff);//取低字节
            crcLowTable[j] = (u8)((crc>>8)&0xff);//取高字节
            printf("%4x  ",crc);		
        }
        printf("\r\n");
    }

生成表如下：

![整体表][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ExNDQ5NTE2NDg3_size_16_color_FFFFFF_t_70 2]

### 5.2.查表法实现 ###

有了表格后，就可以实现查表法了（为什么用15-17行代码我也不清楚，这里可能涉及到推倒，欢迎大神们在评论区指导），代码如下：

/*****************************************************************************
    *function name:Crc16withTable
    *function: 用查表法计算CRC
    *input:  addr：字符串起始地址；len ：字符串长度；table：用到的表格
    *output:无
    ******************************************************************************/
    u16 Crc16withTable(u8 *addr, int len,u8 *crcHighTable,u8 *crcLowTable)  
    {  
        u8 crcHi = 0x00;
        u8 crcLo = 0x00;
        u8 index;
        u16 crc;
        for (;len>0;len--)             
        {  
            index = crcLo ^ *(addr++);//低8位异或，得到表格索引值
            crcLo = crcHi ^ crcHighTable[index];
            crcHi = crcLowTable[index];
        }
        crc = (u16)(crcHi<<8 | crcLo);
        return(crc^0xffff);//返回校验值
    }

大家可以自行验证，将3.3.3代码和5.2代码计算结果作比较。结果是一样的。实际在用时，需要将表写成数组放在代码前面，这样代码就可以查表了。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ExNDQ5NTE2NDg3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191108101800282.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ExNDQ5NTE2NDg3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ExNDQ5NTE2NDg3_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191108104638614.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ExNDQ5NTE2NDg3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ExNDQ5NTE2NDg3_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191108104906183.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ExNDQ5NTE2NDg3,size_16,color_FFFFFF,t_70