本文转自公众号，欢迎关注
Micrium全家桶之uC-CRC: 0x02 CRC (qq.com)
(资料图)
前言
前一篇我们讲了Micrium全家桶之uC-CRC: 0x01 ECC:https://mp.weixin.qq.com/s/FKVvzwL7wzxLJCkx3gOdJQ。ECC常用于NAND进行误码校正。而CRC一般用于错误检测,比如镜像,协议的正确完备性检测。
这一篇我们来讲讲uC-CRC组件的CRC部分，老规矩先代码用起来,然后再讲讲原理,理论结合实践。
使用
可以从https://github.com/qinyunti/uC-CRC.git下载代码,该版本在原版本基础上进行了修改,删除了其他依赖,可以单独使用,方便移植,也可以参考https://mp.weixin.qq.com/s/FKVvzwL7wzxLJCkx3gOdJQ。有了上一篇基础我们不再详细介绍如何集成该代码,直接进入测试环节。文件
如果只使用CRC的话只需要crc_cfg.h和edc_crc.c,edc_crc.h即可。配置
其中cec_cfg.h的宏EDC_CRC_CFG_OPTIMIZE_ASM_EN配置是否使用汇编代码实现,默认为DEF_DISABLED.
以下宏配置是否使能对应的算法和反转查找表
其中前面4个宏使能了4种算法,后面4个宏定义是否支持位反转模式,如果是则会定义对应的CRC查找表,比如EDC_CRC_CFG_CRC32_REF_EN使能则使用CRC_TblCRC32_ref,EDC_CRC_CFG_CRC32_EN使能则使用CRC_TblCRC32。
所谓的位反转就是bit7和bit0交换,bit6和bit1交换...，通过查表法空间换时间加快速度。有些场景需要位翻转,所以有这个实现。
#define EDC_CRC_CFG_CRC16_1021_EN DEF_ENABLED /* See Note#3. */#define EDC_CRC_CFG_CRC16_8005_EN DEF_ENABLED#define EDC_CRC_CFG_CRC16_8048_EN DEF_ENABLED#define EDC_CRC_CFG_CRC32_EN DEF_ENABLED#define EDC_CRC_CFG_CRC16_1021_REF_EN DEF_ENABLED#define EDC_CRC_CFG_CRC16_8005_REF_EN DEF_ENABLED#define EDC_CRC_CFG_CRC16_8048_REF_EN DEF_ENABLED#define EDC_CRC_CFG_CRC32_REF_EN DEF_ENABLED接口
CRC提供了以下接口
CRC_Open_16BitCRC_WrBlock_16BitCRC_WrOctet_16BitCRC_Close_16BitCRC_Open_32BitCRC_WrBlock_32BitCRC_WrOctet_32BitCRC_Close_32Bit提供了两组接口16位的和32位的
流式操作,结果存在结构体参数种 只支持查表法
CRC_Open_16Bit()->
CRC_WrBlock_16Bit()-> 一次写多个字节
CRC_WrOctet_16Bit()-> 一次写一个字节
CRC_Close_16Bit()->
32位的类似
CRC_Open_32Bit->
CRC_WrBlock_32Bit->
CRC_WrOctet_32Bit->
CRC_Close_32Bit->
这里提供这几个位反转接口,最后结果再调用这些接口进行位反转。
CRC_Reflect_08Bit 查表法实现8位数据位反转 查表是CRC_ReflectTbl
CRC_Reflect_16Bit 查表法实现16位数据位反转
CRC_Reflect_32Bit 查表法实现32位数据位反转
还提供两个接口直接计算,立即返回计算值,支持查表和不查表
CRC_ChkSumCalc_16Bit
CRC_ChkSumCalc_32Bit
所以以上有几种配置:使用查表还是不使用查表，使用位反转还是不使用
p_model->Reflect == DEF_YES 则使用位反转
p_model->TblPtr == (const CPU_INT16U *)0则不使用查表
测试
以CRC_ChkSumCalc_16Bit为例
CPU_INT16U crc = CRC_ChkSumCalc_16Bit((CRC_MODEL_16*)&CRC_ModelCRC16_8005,(void*)p_datap,strlen(p_datap),&err);第一个参数传入默认配置好的
const CRC_MODEL_16 CRC_ModelCRC16_8005 = {0x8005u,0x0000u,DEF_NO,0x0000u,&CRC_TblCRC16_8005[0]};即多项式为0x8005,初始值为0x0000,不进行位反转,不进行异或输出,查表为CRC_TblCRC16_8005。
测试代码如下
#include < stdio.h >#include < stdint.h >#include "edc_crc.h"uint8_t s_buffer[33];int crc_main(int argc, char* argv[]){ const char* p_datap="123456789"; EDC_ERR err; CPU_INT16U crc = CRC_ChkSumCalc_16Bit((CRC_MODEL_16*)&CRC_ModelCRC16_8005,(void*)p_datap,strlen(p_datap),&err); if(EDC_CRC_ERR_NONE != err) { printf("err\\r\\n"); } else { printf("crc = %#x\\r\\n",crc); } return 0;}打印值如下
crc = 0xfee8和edc_crc.h下列举的测试用例结果一致
* ------------------------------------------------------------------* | POLY | REFLECT? | INIT VAL | COMP. OUT? | CRC |* -------------+------------+------------+------------+-------------* | 0x1021 | NO | 0x0000 | NO | 0x31C3 |* | 0x1021 | NO | 0x0000 | YES | 0xCE3C |* | 0x1021 | NO | 0x1D0F | NO | 0xE5CC |* | 0x1021 | NO | 0xFFFF | NO | 0x29B1 |* | 0x1021 | NO | 0xFFFF | YES | 0xD64E |* -------------+------------+------------+------------+-------------* | 0x1021 | YES | 0x0000 | NO | 0x2189 |* | 0x1021 | YES | 0x0000 | YES | 0xDE76 |* | 0x1021 | YES | 0xFFFF | NO | 0x6F91 |* | 0x1021 | YES | 0xFFFF | YES | 0x906E |* -------------+------------+------------+------------+-------------* | 0x8005 | NO | 0x0000 | NO | 0xFEE8 |* | 0x8005 | NO | 0x0000 | YES | 0x0117 |* | 0x8005 | NO | 0xFFFF | NO | 0xAEE7 |* | 0x8005 | NO | 0xFFFF | YES | 0x5118 |* -------------+------------+------------+------------+-------------* | 0x8005 | YES | 0x0000 | NO | 0xBB3D |* | 0x8005 | YES | 0x0000 | YES | 0x44C2 |* | 0x8005 | YES | 0xFFFF | NO | 0x4B37 |* | 0x8005 | YES | 0xFFFF | YES | 0xB4C8 |* -------------+------------+------------+------------+-------------* | 0x8048 | NO | 0x0000 | NO | 0x80A0 |* | 0x8048 | NO | 0x0000 | YES | 0x7F5F |* | 0x8048 | NO | 0xFFFF | NO | 0xE8E0 |* | 0x8048 | NO | 0xFFFF | YES | 0x171F |* -------------+------------+------------+------------+-------------* | 0x8048 | YES | 0x0000 | NO | 0x1506 |* | 0x8048 | YES | 0x0000 | YES | 0xEAF9 |* | 0x8048 | YES | 0xFFFF | NO | 0x1710 |* | 0x8048 | YES | 0xFFFF | YES | 0xE8EF |* -------------+------------+------------+------------+-------------* | 0x04C11DB7 | NO | 0x00000000 | NO | 0x89A1897F |* | 0x04C11DB7 | NO | 0x00000000 | YES | 0x765E7680 |* | 0x04C11DB7 | NO | 0xFFFFFFFF | NO | 0x0376E6E7 |* | 0x04C11DB7 | NO | 0xFFFFFFFF | YES | 0xFC891918 |* -------------+------------+------------+------------+-------------* | 0x04C11DB7 | YES | 0x00000000 | NO | 0x2DFD2D88 |* | 0x04C11DB7 | YES | 0x00000000 | YES | 0xD202D277 |* | 0x04C11DB7 | YES | 0xFFFFFFFF | NO | 0x340BC6D9 |* | 0x04C11DB7 | YES | 0xFFFFFFFF | YES | 0xCBF43926 |* -------------+------------+------------+------------+-------------CRC原理
参考
https://www.iar.com/knowledge/support/technical-notes/general/checksum-generation/
https://ecomputernotes.com/computernetworkingnotes/communication-networks/cyclic-redundancy-check
CRC即Cyclic Redundancy Check循环冗余校验码,用来进行错误检测,我们对数据进行CRC计算得到一个校验码,校验码和数据一起发送,接收时再对数据计算CRC和收到的校验码比对,如果校验值一样则认为数据正确。其根本原理还是奇偶校验,只是可以认为是花式奇偶校验,源数据反转一个bit会对应到CRC值的1位变化,但是源数据多位改变则有可能CRC不变。
所以CRC的校验能力并不是很强,但是比奇偶校验和求和校验强,且好在简单计算快,所以以太网等数据传输,一些传感器数据,底层总线信号包等都使用CRC校验。
从另一个角度CRC是基于二进制除法(MODULO ARITHMETIC)的算法,要传输的数据单元被一个预定的除数(二进制数)除以得到余数。这个余数称为CRC。CRC比除数小1位。这意味着如果CRC为n位，则除数为n+ 1位。发送方将这个CRC附加到数据单元的末尾，这样得到的数据单元就可以被预定的除数完全整除，即余数变为零。在目的地，输入的数据单元(即数据+ CRC)被相同的数字(预定的二进制除数)所除,如果能整除就说明数据正确。
过程如下
先选择除数(即二进制值),即对应的我们所说的多项式,比如选1011则对应多项式x^3+X^1+x^0,位数为4.
然后在源数据的后面添上4-1个0.比如源数据是1001则变为了1001000,然后这个值除以1011
注意这里除法有一点不一样,看最左边的一位如果余数最左边是0则商0,否则商1,另外做减法时不需要借位,只需要满足0-1=1 0-0=0 1-1=0 1-0=1
以上运算最终得到余数110所以,所以接到数据后就是1001110
接收端检测时用1001110除以1011,如果余数为0说明数据正确
总结一下
l除数(多项式的位数)是CRC值的位数+1,比如对于8位CRC,其多项式的最高位为X^8,包括常数项就是9位。
lCRC可以检测到所有影响奇数位的突发错误,偶数位不保证
l选择的多项式决定了检测错误的能力和类型,所以才有了那些标准的多项式
比如
除数和多项式的关系如下,最高次项始终是1,次数和CRC位数一样.
用多项式的角度看除法就是如下图,注意减法时不需要借位,系数满足1bit的减法。
而CRC的计算一般都采用了查表法。
CRC计算工具
https://crccalc.com/?crc=01020304&method=crc32&datatype=hex
http://www.sunshine2k.de/coding/javascript/crc/crc_js.html
https://www.lammertbies.nl/comm/info/crc-calculation.html
总结
以上进行了uC-CRC的CRC部分测试以及相应的原理讲解,在理解的基础上可以将代码集成到自己的项目中使用。
审核编辑：汤梓红
