聊聊嵌入式系统中常用的循环冗余校验技术

所谓完整性是指数据在其生命周期中的准确性和一致性。这些数据可能存储在EEPROM/FLASH里，或者基于通信协议进行传输，它们有可能因为外界干扰或者程序错误，甚至系统入侵而导致被破坏。如果这些数据在使用前不做校验，产品功能可能失效。在一些特定领域，严重时可能会危及用户财产甚至生命安全。

本文就来聊聊使用较为广泛的循环冗余校验技术，以及在STM32中的一些具体使用体会。

所谓循环冗余校验（CRC：Cyclic Redundancy Check）是一种错误检测算法，通常在通信协议中或存储设备中用于检测原始数据的意外变动。可以简单理解成对有用数据按照一定的算法进行计算后，提取出一个特征值，并附加在有用数据后。在应用中将有用数据按照特定的算法提取特征值与预先存储的特征值进行比对，如相等则校验通过，反之校验失败，从而识别出数据是否异常。

为何要校验数据完整性(Data Integrity)？

数据在存储以及传输的过程中可能发生异动。以数据通信应用场景为例，常见的错误大致有两种失效模式：

单个位错误(Single Bit Error)：仅仅某一个数据位出现错误，如图：

突发错误(BurstError)：两个或更多个数据位在码流中出现错误，如图：

为什么可能会出现这些位错误呢？对于电子系统通信，它涉及到物理层、链路层、通信介质等，其中物理层主要将原始二进制数据利用一定的编解码原理对其进行调制，然后经由发送电路将调制信号输送至传输介质，接收端利用接收电路进行接收并解调，将信息还原成二进制码流。在这个过程中介质有可能被干扰，接收电路、发送电路、调制电路、解调电路都可能由于某些干扰原因导致工作失效而出现误码。此时，如果没有一个很好的机制去确保数据的正确性，比如一个飞控系统中某些控制命令、车辆系统中CAN报文数据，系统直接使用这些错误数据去控制被控对象（比如电机、发动机等），严重的时候就会造成难以估量的生命财产灾难。

存储系统中的数据也是一样。一般来说，系统在上电运行时会从物理存储介质装载系统参数，比如一些校准数据。如果由于介质的某些位被破坏，或者软件bug导致数据被误操作了，而没有数据完整性检测，这样的数据直接被应用于系统控制，一样会造成安全隐患。

所以，对于数据完整性检测的重要性不言而喻。常见的数据完整性算法有很多种，比如简单的异或校验、CRC循环冗余校验、FEC前向纠错算法等等。而循环冗余校验在嵌入式系统中应用非常广泛，在通信协议制定、数据存储、压缩解压算法等都有广泛的应用。

循环冗余校验使用二进制除法作为算法原理，具有强大的错误检测机制。对于二进制除法使用少量的硬件逻辑电路就可实现。至于软件代码实现，有查表法和移位计算两种思路及策略。查表法以空间换时间，移位计算法以时间换空间。

何为循环冗余校验？

循环冗余校验的核心数学算法原理基于循环码，在不增加原始数据的信息基础上扩展了信息，以极小的存储代价存储其冗余特征。该算法是W. Wesley Peterson 于1961年发明的。

这里的n位二进制数据为有效信息载荷。(可能是传输或存储的有用信息)

根据CRC算法计算出m位冗余码，即根据该CRC校验多项式结合CRC算法从前面有效数据中提取出特征冗余码，这就是冗余的真实含义。

实际传输或者存储的就是n+m位二进制数据。

这里引出一个概念：多项式，在CRC校验算法中多项式可做如下理解及表示：

其本质就是多进制的数学表示法，这里是二进制，故X为2。

其基本的算法处理过程示意如下：

假定待发送有效数据为二进制多项式M(x)，而校验多项式P(x)为收发双方约定好了的，双方已知，这里介绍一下几个多项式表示的意思及相关处理流程：

接收方接收到数据后进行CRC校验。余数为0，校验通过。

其实CRC的本质就是二进制多项式除法求取冗余码的计算过程，无论软件的查表法、移位计算法，还是纯硬件逻辑电路实现，本质都是一样的。对于数字逻辑电路利用移位计算则更具优势，因为几乎不占用CPU时间。

常见的CRC校验多项式

常见的CRC校验多项式算子有哪些？

不同的校验多项式，除了复杂度有差异外，从应用角度看有什么差异呢？从应用角度看主要体现在错误诊断率。不妨看看CRC-16以及CRC-CCITT的错误检测效果：

可完全检测出单bit及双bit错误

奇数个位错误

能检测出16位长度及小于16的突发错误

能以99.997%的概率检测出长度为17位及以上的错误

选择不同的校验多项式算子，其位错误诊断成功率是不一样的，当然其计算开销也不一样。我们来查查权威的IEC标准看看。下图截自《IEC61508-7》。

由上文可见，CRC-8可诊断出99.6%的位错误概率，而CRC-16则提高至99.998%的位错误概率。

注：IEC61508是国际电工委员会功能安全标准(Functional safety of electrical/electronic/programmable electronicsafety-related systems)。

技术发展至今，已有大量不同的校验多项式生成器被各行各业使用。下面是来自wikipedia截图，供大家参考：

STM32的CRC硬件外设

如下图，STM32内置了一个CRC-32硬件计算单元，实现了一个固定多项式0x4C11DB7（16进制表示），可应用于以太网报文校验码计算。

STM32 全系列产品都具有 CRC 外设，对 CRC 的计算提供硬件支持，节省了应用代码存储空间。CRC 校验值既可以用于传输中的数据正确性验证，也可用于数据存储时的完整性检查。在 IEC60335 中，也接受通过 CRC 校验对 FLASH 的完整性进行检查。在对 FLASH 完整性检查的应用中，需要事先计算出整个 FLASH 的 CRC 校验值（不包括最后保存CRC 值的字节），放在FLASH 的末尾。在程序启动或者运行的过程中重新用同样的方法计算整个 FLASH 的 CRC 校验值，然后与保存在 FLASH 末尾地址空间的 CRC 值进行比较。

EWARM 从 v5.5 版本之后开始支持 STM32 芯片的 CRC计算。计算整个 FLASH的 CRC 校验值并保存在 FLASH末尾的过程，可以在 IAR 中完成。通过配置EWARM 的 CRC 计算参数，自动对整个 FLASH 空间进行 CRC 计算，并将计算结果放到 内部FLASH空间 的末尾。

或许你会问，这有什么应用价值呢？不妨以基于MCU程序的升级为例。在代码升级过程中，如果不对bootloader升级接口传入的二进制程序文件做校验，就无法及时发现升级过程中发生的代码错误。相反，如果原始代码添加了校验码，升级程序在接受到升级文件后做校验计算，并与待升级文件末尾的校验码进行比对，如果不匹配则放弃升级，这样就不至于将无效的甚至有安全隐患的代码写进芯片。

修改 Link 文件，指定 checksum 在FLASH 中的存储位置，在 Link 文件中增加下面语句。

place at end of ROM_region { ro section .checksum };    

该语句指定将 CRC 的值放在 FLASH 空间的末尾位置。是整个 FLASH 空间的末尾，不是应用程序的代码末尾。这样，CRC 值的位置就是固定的，不会随代码大小而变化。 

配置 Checksum 页面的参数

IAR Checksum 页说明（v6.4 及以上）

IAR 的 checksum 页面分为两个部分:

红线圈出的部分：定义了FLASH 中需要计算 CRC 的范围和空闲字节填充值。

checksum 计算参数的设定部分：Checksum size：选择 checksum 的大小（字节数）

Alignment：指定 checksum 的对齐方式。不填的话默认 2 字节对齐。

Algorithm：选择 checksum 的算法

Complement：是否需要进行补码计算。选择“As is”就是不进行补码计算。

Bit order：位输出的顺序。MSB first，每个字节的高位在前。LSB first，每个字节的低位在前。

Reverse byte order within word：对于输入数据，在一个字内反转各个字节的顺序。

Initial value：checksum 计算的初始化值 

Checksum unit size ：选择进行迭代的单元大小，按 8-bit，16-bit 还是 32-bit 进行迭代。

STM32 CRC 外设使用默认配置时 IAR 的配置

STM32CRC 外设的配置：

POLY= 0x4C11DB7（CRC32） 

Initial_Crc = 0Xffffffff 

输入/输出数据不反转 

输入数据：0x08000000~0x0801FFFB。(最后 4 个字节用来放计算出的 CRC 值)

在实验的过程发现， ”Alignment ”似乎对计算出的 CRC 值没有影响。但“Reverse byte order within word ”与“Checksumunit size ”这两项的配置有一定关系。如果后者选择 32-bit，则不能勾选前者；反之如果后者选择 8-bit，则一定要勾选上“ Reverse byte order within word ”。也可以参照下图进行设置：

对于IAR v6.4 以下版本，没有”Checksum unit size”选项。参考配置如下：

代码怎么写？

如前文描述，这个应用可以用于对Flash中数据进行校验，参考代码如下：

/*-1- 配置CRC外设 */  CrcHandle.Instance = CRC;  /* 默认二进制多项式使能 */  CrcHandle.Init.DefaultPolynomialUse    = DEFAULT_POLYNOMIAL_ENABLE;  /* 默认初值设置 */  CrcHandle.Init.DefaultInitValueUse     = DEFAULT_INIT_VALUE_ENABLE;  /* 输入数据不反转 */  CrcHandle.Init.InputDataInversionMode  = CRC_INPUTDATA_INVERSION_NONE; /* 输出数据不反转 */  CrcHandle.Init.OutputDataInversionMode = CRC_OUTPUTDATA_INVERSION_DISABLED;  /* 输入数据基本单元长度为32bit */  CrcHandle.InputDataFormat              = CRC_INPUTDATA_FORMAT_WORDS;  if(HAL_CRC_Init(&CrcHandle) != HAL_OK)  { /* 初始化错误 */    Error_Handler();   }  pdata = (uint32_t*)ROM_START; /*##-2- 调用HAL库利用硬件CRC外设对ROM区计算CRC-32校验码*/  uwCRCValue = HAL_CRC_Calculate(&CrcHandle, pdata, ROM_SIZEinWORDS);

小结

对于CRC应用，还可以根据多项式算子编写纯软件方案，网上有很多现成的代码。其基本思路无外乎查表法以及移位计算法。差异在于一个牺牲存储空间以换取计算效率，一个牺牲计算时间而节省存储空间，至于如何选择，则根据所设计的系统综合考虑，一般根据应用场景来定。

将块数据利用CRC算法计算出冗余码，有的文章、标准称这个冗余码为签名。实际应用时计算有效数据所得校验码与预存校验码进行比较，相等则校验通过，反之则失败。当然，也可以将原数据与所存校验码一起传入校验算法，所得结果为0则校验通过，反之失败。

对于数据通信，一般会在报文的尾部添加有效数据的校验码，再由接收方校验收到报文的数据完整性