目录
CRC校验即循环冗余校验（Cyclic Redundancy Check），是基于数据计算一组效验码，用于核对数据传输过程中是否被更改或传输错误。首先看两个概念，后续会用到。
CRC校验本质上是选取一个合适的除数，要进行校验的数据是被除数，然后做模2除法，得到的余数就是CRC校验值。
下面用具体的例子做讲解：给定一组数据A：10110011（二进制），选取除数B：11001。
第1章讲解了CRC校验的基本原理，通常我们把选取的除数称之为“生成多项式”。事实上，生成多项式的选取是由一定标准的，如果选的不好，那么检出错误的概率就会低很多。好在这个问题已经被专家们研究了很长一段时间了，对于我们这些使用者来说，只要把现成的成果拿来用就行了。下表是一些标准的CRC生成多项式，可以直接使用。
| 名称 | 生成多项式 | 简记式 |
| CRC-4 | x4+x+1 | 0x03 |
| CRC-8 | x8+x5+x4+1 | 0x31 |
| CRC-8 | x8+x2+x1+1 | 0x07 |
| CRC-8 | x8+x6+x4+x3+x2+x1 | 0x5E |
| CRC-12 | x12+x11+x3+x+1 | 0x080F |
| CRC-16 | x16+x15+x2+1 | 0x8005 |
| CRC16-CCITT | x16+x12+x5+1 | 0x1021 |
| CRC-32 | x32+x26+x23+...+x2+x+1 | 0x04C11DB7 |
更多标准CRC生成式请参考https://en.wikipedia.org/wiki/Cyclic_redundancy_check
有一点要特别注意，文献中提到的生成多项式经常会说到多项式的位宽（Width，简记为W），这个位宽不是多项式对应的二进制数的位数，而是位数减1。比如CRC8中用到的位宽为8的生成多项式，其实对应得二进制数有九位：100110001。另外一点，多项式表示和二进制表示都很繁琐，交流起来不方便，因此，文献中多用16进制简写法来表示，因为生成多项式的最高位肯定为1，最高位的位置由位宽可知，故在简记式中，将最高的1统一去掉了，如CRC32的生成多项式简记为04C11DB7实际上表示的是104C11DB7。当然，这样简记除了方便外，在编程计算时也有它的用处。所以在第一章中提到的在被除数后增加0的位数就是位宽，计算出的CRC校验值长度也是位宽。
实际工程中多使用CRC-16校验，即选取生成多项式为0x8005。按照前面提到的CRC校验原理，编程实现步骤如下：（注意实际编程时并不用这种直接的方法，如不想看可直接跳到3.3.2）
这种直接的方法有一个弊端，那就是在字符串前面加0，并不影响校验值，这就不符合我们的预期了。比如，我们想校验的1字节1001 1100，现在在前面补1字节0，变成2字节0000 0000 1001 1100，结果两个得到的校验值是一样的。所以在实际应用中，CRC校验过程做了一些改变：增加了“余数初始值”、“结果异或值”、“输入数据反转”和“输出数据反转”四个概念。
实际应用中，生成多项式、余数初始值、结果异或值、输入数据反转和输出数据反转是有对应关系的，这些对应关系是大家都遵守的标准，如下表所示：
| CRC算法名称 | 多项式公式 | 宽度 | 多项式（16进制） | 初始值（16进制） | 结果异或值（16进制） | 输入值反转 | 输出值反转 |
|---|---|---|---|---|---|---|---|
| CRC-4/ITU | x4 + x + 1 | 4 | 03 | 00 | 00 | true | true |
| CRC-5/EPC | x4 + x3 + 1 | 5 | 09 | 09 | 00 | false | false |
| CRC-5/ITU | x5 + x4 + x2 + 1 | 5 | 15 | 00 | 00 | true | true |
| CRC-5/USB | x5 + x2 + 1 | 5 | 05 | 1F | 1F | true | true |
| CRC-6/ITU | x6 + x + 1 | 6 | 03 | 00 | 00 | true | true |
| CRC-7/MMC | x7 + x3 + 1 | 7 | 09 | 00 | 00 | false | false |
| CRC-8 | x8 + x2 + x + 1 | 8 | 07 | 00 | 00 | false | false |
| CRC-8/ITU | x8 + x2 + x + 1 | 8 | 07 | 00 | 55 | false | false |
| CRC-8/ROHC | x8 + x2 + x + 1 | 8 | 07 | FF | 00 | true | true |
| CRC-8/MAXIM | x8 + x5 + x4 + 1 | 8 | 31 | 00 | 00 | true | true |
| CRC-16/IBM | x16 + x15 + x2 + 1 | 16 | 8005 | 0000 | 0000 | true | true |
| CRC-16/MAXIM | x16 + x15 + x2 + 1 | 16 | 8005 | 0000 | FFFF | true | true |
| CRC-16/USB | x16 + x15 + x2 + 1 | 16 | 8005 | FFFF | FFFF | true | true |
| CRC-16/MODBUS | x16 + x15 + x2 + 1 | 16 | 8005 | FFFF | 0000 | true | true |
| CRC-16/CCITT | x16 + x12 + x5 + 1 | 16 | 1021 | 0000 | 0000 | true | true |
| CRC-16/CCITT-FALSE | x16 + x12 + x5 + 1 | 16 | 1021 | FFFF | 0000 | false | false |
| CRC-16/x5 | x16 + x12 + x5 + 1 | 16 | 1021 | FFFF | FFFF | true | true |
| CRC-16/XMODEM | x16 + x12 + x5 + 1 | 16 | 1021 | 0000 | 0000 | false | false |
| CRC-16/DNP | x16 + x13 + x12 + x11 + x10 + x8 + x6 + x5 + x2 + 1 | 16 | 3D65 | 0000 | FFFF | true | true |
| CRC-32 | x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1 | 32 | 04C11DB7 | FFFFFFFF | FFFFFFFF | true | true |
| CRC-32/MPEG-2 | x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1 | 32 | 04C11DB7 | FFFFFFFF | 00000000 | false | false |
接下来以CRC-16/IBM校验为例，讲解工程中使用的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
#endifcrc.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) ;
#endifcrc.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.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函数的区别。
查表法速度快，但是表要占一部分内存，这是以空间换时间。
为了便于理解查表法，首先看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");
}生成的表如下：
需要注意的是，查表法所用的表根据多项式的不同而不同，所以再用不同多项式时，一定要重新生成对应的表。所以多项式为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循环，直接从表中取值，速度快了很多。实际在用时，需要将表写成数组放在代码前面，这样代码就可以查表了。
crc16查表法和crc8查表法类似，也是首先是生成一个表，然后再用查表代替for循环。
以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");
}生成表如下：
拆分后低字节 crcHighTable 拆分后高字节crcLowTable
有了表格后，就可以实现查表法了（为什么用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代码计算结果作比较。结果是一样的。实际在用时，需要将表写成数组放在代码前面，这样代码就可以查表了。
https://download.csdn.net/download/u013073067/13138335
编译环境：VS2010
语言：C
如有疑问，欢迎大家在评论区留言讨论。
参考文献：
[1]https://www.cnblogs.com/sinferwu/p/7904279.html