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。
- 首先需要在被除数A后加4个比特位0(具体加几个0是根据除数B的位数决定的,比如这里B是5位,那么A后面加4个0;如果B选6位,则A后面加5个0,总之加的0的个数比除数B的个数少1位。后面还会提到怎么添加)。
- 进行模2除法运算。注意每次都是模2运算,即异或。
- 最后得到余数C就是CRC校验值。注意余数位数必须比除数少1位,如果不够前面加0补齐。运算如下图所示
2.生成多项式
第1章讲解了CRC校验的基本原理,通常我们把选取的除数称之为“生成多项式”。事实上,生成多项式的选取是由一定标准的,如果选的不好,那么检出错误的概率就会低很多。好在这个问题已经被专家们研究了很长一段时间了,对于我们这些使用者来说,只要把现成的成果拿来用就行了。下表是一些标准的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校验值长度也是位宽。
3.以CRC-16校验为例讲解编程实现
3.3.1 完全按照CRC原理实现校验
实际工程中多使用CRC-16校验,即选取生成多项式为0x8005。按照前面提到的CRC校验原理,编程实现步骤如下:(
注意实际编程时并不用这种直接的方法,如不想看可直接跳到3.3.2)
- 预置1个16位的变量为CRC,此值存放CRC校验值,赋初值为0;
- 将需要校验的字符串str后面添加16个0;
- 如果变量CRC最高位为1,变量CRC与0x8005异或,然后将变量CRC左移1位,最低位补入1比特新的数据(来自需要校验的字符串str);
- 如果变量CRC最高位为0,直接将变量CRC左移1位,最低位补入1比特新的数据(来自需要校验的字符串str);
- 重复2-3步,直到字符串str最后1位补入变量CRC中;
- 此时得到的余数就是CRC校验值。
这种直接的方法有一个弊端,那就是在字符串前面加0,并不影响校验值,这就不符合我们的预期了。比如,我们想校验的1字节1001 1100,现在在前面补1字节0,变成2字节0000 0000 1001 1100,结果两个得到的校验值是一样的。所以在实际应用中,CRC校验过程做了一些改变:增加了“
余数初始值”、“
结果异或值”、“
输入数据反转”和“
输出数据反转”四个概念。
3.3.2 工程中常用CRC校验过程
- 余数初始值:即在计算开始前,先给变量CRC赋的初值。
- 结果异或值:即在计算结束后,得到的变量CRC与这个值进行异或操作,就得到了最终的校验值。
- 输入数据反转:即在计算开始前,将需要校验的数据反转,如数据位1011,反转后为1101。
- 输出数据反转:即在计算结束后,与结果异或值异或之前,计算值反转,如计算结果为1011,反转后为1101。
实际应用中,生成多项式、余数初始值、结果异或值、输入数据反转和输出数据反转是有对应关系的,这些对应关系是大家都遵守的标准,如下表所示:
表3-1 常见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校验编程实现。具体实现时,以字节为单位进行计算。
- 预置1个16位的变量CRC,存放校验值,首先根据表3-1赋初值0x0000;
- 将第1个字节按照表3-1看是否需要反转,若需要,则按反转,若不需要,直接进入第3步。这里需要反转;
- 把第1个字节按照步骤2处理后,与16位的变量CRC的低高8位相异或,把结果放于变量CRC,低8位数据不变;
- 把变量CRC的内容左移1位(朝高位)用0填补最低位,并检查左移后的移出位;
- 如果移出位为0:重复第3步(再次左移一位);如果移出位为1,变量CRC与多项式8005(1000 0000 0000 0101)进行异或;
- 重复步骤4和5,直到左移8次,这样整个8位数据全部进行了处理;
- 重复步骤2到步骤6,进行通讯信息帧下一个字节的处理;
- 将该通讯信息帧所有字节按上述步骤计算完成后,将得到的16位变量CRC按照表3-1看是否需要反转,这里需要反转;
- 最后,与结果异或值异或,得到的变量CRC即为CRC校验值;
我在这里按照如上方法整理了一个通用代码,包含CRC-8,CRC-16和CRC-32。代码如下:
type.h
#ifndef __TYPE_H__
#define __TYPE_H__
#include
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
#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函数的区别。
以上是计算法计算校验值,最后还有一小节,讲解查表法计算校验值,查表法更快,但是需要占用一定内存空间。计算法和查表法各有利弊,使用时根据实际情况选择。最后一节后续在更。
如有疑问,欢迎大家在评论区留言讨论。
参考文献:
[1]
https://www.cnblogs.com/sinferwu/p/7904279.html
[2]
https://en.wikipedia.org/wiki/Cyclic_redundancy_check
[3]
https://www.cnblogs.com/94cool/p/3559585.html