本帖最后由 luobeihai 于 2024-9-23 00:00 编辑
#申请原创# @21小跑堂
1. CRC简单介绍
CRC是英文 Cyclic redundancy check 的缩写，即循环冗余校验。
循环冗余校验( CRC )是一种错误检测码，常用于数字网络和存储设备，以检测数字数据的意外更改。进入这些系统的数据块会附加一个短校验值，该值基于其内容的多项式除法的余数。在检索时，会重复计算，如果校验值不匹配，则可以采取纠正措施防止数据损坏。
CRC 之所以如此命名，是因为校验（数据验证）值是冗余的（它扩展了消息但不添加信息），并且算法基于循环码。CRC 之所以流行，是因为它们在二进制硬件中易于实现，易于进行数学分析，并且特别擅长检测传输信道中噪声引起的常见错误。由于校验值具有固定长度，因此生成校验值的函数偶尔会用作哈希函数。
CRC 基于循环纠错码理论。1961年，W. Wesley Peterson首次提出了使用[系统循环码（通过添加固定长度的校验值对消息进行编码）来检测通信网络中的错误。循环码不仅易于实现，而且特别适合检测突发错误：消息中连续的错误数据符号序列。对于这一点是非常重要的，因为突发错误是许多通信信道（包括磁性和光学存储设备）中常见的传输错误。通常，对任意长度的数据块应用n位 CRC 可以检测到不长于n位的任何单个错误突发，而它能检测到的所有更长的错误突发中的比例约为（1 − 2 − n）。
2. CRC基本概念及其模型
在以前很多前辈们在研究CRC算法的时候，就已经设计了各种CRC的算法模型，这些模型可以适用不同的校验场合，比如 CRC-16 ，CRC-32 等不同的算法模型。
一般我们在具体的项目中，要使用CRC校验的时候，首先就要选择合适的算法模型，根据选定的CRC算法模型，才能计算得到对应的CRC校验码。然后，通信双方约定好使用的CRC校验模型，才能保证校验的一致性。
下表仅列出了所使用的各种算法的多项式。特定协议的变体可以强制执行如上所述的预反转、后反转和反转位排序。例如，Gzip 和 Bzip2 中使用的 CRC32 使用相同的多项式，但 Gzip 采用反转位排序，而 Bzip2 则不采用。请注意，GF(2) 中次数大于 1 的偶校验多项式***不会是原始的。本表中标记为原始的偶校验多项式表示原始多项式乘以 (x + 1)。多项式的最高有效位始终为 1，并且不会在十六进制表示中显示。
这些CRC算法模型中，有几个重要的组成部分，或者说计算CRC校验码时，需要知道的一些概念，如多项式公式、16进制多项式、宽度、初始值、结果异或值等等。
2.1 多项式的概念
对于CRC校验，多项式是非常重要的一个概念。
对任意的二进制数都可以构造一个与其对应的二进制系数多项式公式。
比如，二进制：10011b，它对应的二进制系数多项式就是：
P(x) = x4 + x + 1
这个公式怎么来的呢？
# 二进制数 1 0 0 1 1
# 下标 4 3 2 1 0
# 二进制多项式 1 * X4 + 0 * X3 + 0 * X2 + 1 * X1 + 1 * X0
# 所以最后得出的多项式公式就是：X4 + X + 1
成为多项式要满足的条件
2.2 CRC多项式的表示
一般在计算CRC校验码的时候，我们习惯使用16进制的多项式，这个16进制的多项式，是被省略了最高位 1 的。
因为前面说了，多项式的最高位和最低位，都必须是1，所以一般都会把这个多项式的最高位给省略掉（这里我也没搞懂，反正当它是一个不可描述的规定吧）。
比如前面介绍的，P(x) = X4 + X + 1 ，这个多项式公式，他对应的CRC模型就是 CRC-4/ITU ，然后它的多项式使用16进制表示就是 0x03 ，本来这个多项式应该是0x13的，但是省略了最高位，所以变成了 0x03.
2.3 位宽
位宽，指的就是CRC校验码的二进制位数。这个是和你选择的CRC模型有关的，你选择不同的CRC模型，那么CRC的多项式公式就不一样，所以对应的CRC校验码数据位宽也不一样。
比如前面介绍的多项式公式 ：P(x) = X4 + X + 1 ，那么CRC的校验码位宽就是 4 个二进制位数。因为多项式的最高位为4.
2.4 CRC变体相关的概念
前面介绍的3个参数概念，是CRC模型中必须要有的概念。其他一些概念，比如初始值、输入数据反转，输出数据反转，结果值是否异或处理等，这些都属于CRC变体的处理。
如果没有特意规定的话，那么这些参数默认都是没有的，比如初始值没有规定，则默认为0。没有说明是否反转，那么一般不会对数据进行反转的操作等。
2.4.1 初始值
CRC模型中，有些模型规定CRC的初始值不是0。这个初始值，其实就是CRC校验码的计算过程中，在第一次进行异或计算时，是否有一个初始值。这个如果看C言语实现CRC计算过程就比较直观。
初始值的数据位宽和CRC校验码的位宽是一样的。
2.4.2 输出结果值异或
计算得到了CRC校验码后，如果规定了输出的结果值要进行异或的数不为0，那么最后得到CRC校验码时，还得进行结果值异或这步操作。这样才能最终得到CRC校验码
2.4.3 输入输出值反转
在一些CRC模型中，还会规定输入值与输出值是否反转。
输入值反转，就是在计算CRC校验码之前，是否对原始数据（待测数据）进行按位反转。比如：1010001，反转之后就是：1000101
输出值反转，就是最终得到的CRC结果值，是否进行反转操作。
2.5 如何设计多项式
设计多项式是CRC算法实现中最重要的部分，所设计选择的多项式必须有最大的错误检测能力，同时保证总体的碰撞概率最小。多项式最重要的属性是它的长度，也就是最高非零系数的数值，因为它直接影响着计算的校验和的长度。
最常用的多项式长度有 9位（CRC-8） 17位（CRC-16） 33位（CRC-32） 65位（CRC-64）
在构建一个新的CRC多项式或者改进现有的CRC时，一个通用的数学原则是使用满足所有模运算不可分解多项式约束条件的多项式。 生成多项式的特性可以从算法的定义中推导出来： 如果CRC有多于一个的非零系数，那么CRC能够检查出输入消息中的所有单数据位错误。 CRC可以用于检测短于2k的输入消息中的所有双位错误，其中k是多项式的最长的不可分解部分的长度。 如果多项式可以被x+1整除，那么不存在可以被它整除的有奇数个非零系数的多项式。因此，它可以用来检测输入消息中的奇数个错误，就像奇偶校验函数那样。
3. 与CRC校验有关的模2运算
CRC校验的计算理论源自多项式除法，它是一种二进制除法，被叫做模2除法。待检测的数据除以多项式，最终得到的余数就是CRC检验码。
模2运算，是一种二进制运算，是二进制编码理论中的运算基础。这种运算和我们以前学的四则运算的规则不同，模2运算不考虑进位、借位这些规则，它有着新的运算规则。
模2运算也有加减乘除，下面是它们的运算示例。
3.1 模2加法
加法规则：1+1=0 0+0=0 1+0=1 0+1=1
1 0 1 0
+ 1 1 0 0
-----------
0 1 1 0
3.2 模2减法
减法规则：0-0=0 1-1=0 0-1=1 1-0=1
1 0 1 0
- 1 1 0 0
-----------
0 1 1 0
3.3 模2乘法
乘法规则：0×0=0 0×1=0 1×0=0 1×1=1
模2乘法与普通的乘法一样的演算规则，只不过在按位相加时，是按照模2加法规则进行的。
1 0 1 1
x 1 0 1
----------------
1 0 1 1
0 0 0 0
1 0 1 1
----------------
1 0 0 1 1 1
3.4 模2除法
除法规则：0÷1=0 1÷1=1
模2除法与普通的除法也是一样的演算规则，但是就是在按位相减时，是按照模2减法规则进行的。
1 1 1 0 (商)
|-----------------
1 0 1 1 | 1 1 0 0 1 0 0 (被除数)
1 0 1 1
-----------------
0 1 1 1 1
1 0 1 1
-----------------
0 1 0 0 0
1 0 1 1
-----------------
0 0 1 1 0 (最后余数)
总结：从上面的模2运算的示例中，可以总结出一些规律如下： 模2的加减法运算结果是一样的，他和C语言的异或运算有着一样的规则。所以我们软件实现这个算法时就是使用异或实现的。 模2的乘除法运算，与普通的运算有着类似的演算规则。但是在乘法时乘积相加，除法时余数和除数相减，就需要安装模2加减法规则运算。 当余数的位数小于除数时，模2除法停止运算 当被除数，或者在除法进行过程中得到的部分余数，它们与除数位数一样多，那么商1，否则商0.
4. CRC的检测原理和校验码的计算
4.1 CRC校验码如何计算
CRC校验码的计算，其实就是模2除法的运算过程。
在计算过程中，我们首先要知道二进制多项式，这个多项式其实就是除数，而待校验的数据就是被除数，最终进行模2除法运算得到的余数，就是CRC校验码。
下面以多项式： P(x) = x^4 + x + 1 为例，该多项式对应的二进制数就是：10011 ，进行计算演示。
第一步：原始数据补充 n 个 0 假设要进行编码的原始数据为：1100110，而前面约定好了的多项式的最高位是4，所以CRC校验码的位宽就是4。所以我们先假设余数是 0000 四个0，补充在原始数据的后面，那么最终参与计算的数就是：11001100000
第二步：进行模2除法运算
1 1 0 0 1 1 0 0 0 0 0 （原始数据，后面加了4个0）
1 0 0 1 1 （多项式）
----------------------------------
0 1 0 1 0 1
1 0 0 1 1
----------------------------------
0 0 1 1 0 0 0
1 0 0 1 1
----------------------------------
0 1 0 1 1 0
1 0 0 1 1
----------------------------------
0 0 1 0 1 0 0
1 0 0 1 1
----------------------------------
0 0 1 1 1
当最终计算得到的余数的位数，小于多项式的位数的时候，运算停止，然后得到的余数就是CRC的校验码。
在数据传输过程中，就会把这个校验码放到原始数据的后面，组成一个新的数：11001100111 ，发送给接收方。当接收方在接收到这个数据后，就会进行CRC校验，也就是除以约定好的多项式，如果最终的余数为0，那么说明接收方接收的数据正确。
4.2 CRC校验检测原理
上面介绍计算CRC校验码说了，我们首先要约定好收发双方的除数，这个除数其实就是多项式。进行校验检测的大概过程就是：
(1) 先约定好收发双方选择的CRC多项式 多项式，这个多项式其实就是计算过程中的除数。
(2) 在待校验的数据（可看作是发送方的数据）后面加上 n 个0，这个 n 是多少取决于你所选择的多 项式。比如你选择的多项式是：P(x) = x^4 + x + 1 。那么CRC检验码的位宽就是4，也就是说你要补4个0
(3) 对待校验数据进行模2除法运算，得出的余数就是CRC校验值。
(4) 然后把CRC检验码添加到待检验数据的末尾。这样就组成了一个新的数了，这个是是添加了CRC校验码的。然后把这个新的数发送给接收方。
(5) 接收方，把接收到的数据，也进行模2除法的计算过程，如果余数为0，那么接收正确，如果不为0，那么数据在传输过程中出错。
5. CRC校验的纯软件实现
我们前面一直说了，CRC校验码的计算，其实就是模2除法。然后模2除法，对应到C言语中来，那就可以通过异或和移位操作来实现。
所以，CRC算法的软件实现，主要就是异或和移位操作实现的。实现方法主要有两种： 按位校验和查表。按位校验法消耗更多的CPU算力，查表法则消耗更多的RAM空间。
不同的CRC模型，按位校验法有不同的算法实现，主要是CRC变体的处理，初始值的不同等。不过也是有相似的规律，大致的代码实现过程是相同的。
网上也有大佬们已经实现了的各种CRC模型的算法库，我这里给出一个网上比较全的CRC算法库，如果有我们需要软件实现CRC校验的话，可以去移植过来。
LibCRC官网：https://www.libcrc.org/
LibCRC github仓库：https://github.com/lammertb/libcrc
还有下面这个，主要是按位校验法实现的CRC代码库：
https://github.com/whik/crc-lib-c
5.1 CRC按位校验法软件实现的通用代码
下面是摘抄自 wiki 的其中一种按位校验方式实现的CRC算法，大致的代码思路如下：
function crc(byte array string[1..len], int len)
{
remainderPolynomial := 0 // 多项式的初始值
// 这里有一个流行的变体对剩余多项式进行补充，比如输入数据是否进行反转
for i from 1 to len
{
// 这个步骤要看不同的CRC模型，有不同的处理。n是CRC的位宽，如果小于8的位宽，不用移位
remainderPolynomial := remainderPolynomial xor (string[i] * (n << 8))
for j from 1 to 8
{ // 每个字节是 8 bit
if (remainderPolynomial最高位为1)
{
remainderPolynomial := (remainderPolynomial << 1) xor generatorPolynomial(多项式)
}
else
{
remainderPolynomial := (remainderPolynomial << 1)
}
}
}
// 这里有一个流行的变体对剩余多项式进行补充，比如是否对CRC校验码进行输出反转，进行异或处理
return remainderPolynomial
}
基本上，按位校验法的CRC代码实现，就是上面的这个套路。
5.2 CRC32-MPEG-2 模型的代码实现
这里给出一个 CRC32-MPEG-2 这个模型的CRC代码实现。
uint32_t crc32_mpeg2(uint8_t data[], uint32_t length)
{
uint32_t crc = 0xffffffff;
for (int i = 0; i < length; i++)
{
crc = crc ^ (data[i] << 24);
for (int j = 0; j < 8; j++)
{
if ( crc & 0x80000000 )
{
crc = (crc << 1) ^ 0x04C11DB7;
}
else
{
crc = crc << 1;
}
}
}
return crc;
}
上面这个模型，就是APM32 MCU使用的CRC模型。
6. APM32的CRC外设使用
6.1 APM32 CRC外设基本介绍
基本介绍： APM32几乎所有系列的MCU都带有硬件CRC计算单元（除了F003那些系列）。硬件CRC在计算过程中可以不占用CPU，而且计算速度也更快。 所有系列 APM32 的 CRC 功能，在使用起来都是差不多的。库函数都有提供对应的API函数进行计算。 有些系列的MCU（如F0xx系列）可以自定义CRC的初始值、多项式，这样可以提供给用户更大的自由空间。
对于常用的APM32 MCU，比如 APM32F1/F4 等系列，其 CRC 外设，使用的算法模型是 CRC32-MPEG-2 。数据位宽为 32 位，十六进制多项式为 0x4C11DB7， INIT=0xFFFFFFFF, REFIN=false，REFOUT=false， XOROUT=0x00000000
6.2 APM32 CRC外设如何使用
对于 APM32 CRC外设的使用也很简单，在使能了CRC外设时钟之后，就可以调用SDK提供的CRC计算函数，然后就可以得到对应数据的CRC校验码了。
下面以 APM32F407 为例，使用CRC外设计算校验码的代码：
static uint32_t CRC_Test_Buff[2] = {0x01, 0x02};
int main(void)
{
uint32_t uCRCValue = 0;
/* Enable CRC Periph clock */
RCC_AHB1PeriphClockCmd(RCC_AHB1Periph_CRC, ENABLE);
/* Resets the CRC Data register */
CRC_ResetDR();
/* Calculate the 32-bit CRC value */
uCRCValue = CRC_CalcBlockCRC(CRC_Test_Buff, sizeof(CRC_Test_Buff) / 4);
printf("CalculateBlockCRC = 0x%08X \r\n", uCRCValue);
while (1)
{
}
}
其中要注意的是，CRC_CalcBlockCRC 这个函数提供的输入数据类型是 32 位 的。
运行上面的代码输出结果如下：
然后我们到CRC校验码的在线计算工具，验证下我们使用APM32 CRC外设计算得到的校验码是否一致。计算结果如下图：
我们要选择的参数模型是， CRC32-MPEG-2 这个，输入的数据类型要注意一下是16进制，而且是1个字节。这个和我们APM32的代码是4个字节的数据不同，要自己拆分为1个字节输入到那个框框里面。
然后最终的计算结果是：0x298BE7BA ，这个值和我们使用 APM32 外设计算出来的结果是一致的。
由于代码比较简单，就不附加代码工程了。
| 
楼主
标题置顶
标题高亮
一文摸透CRC基本概念和校验码基础的计算方式，并同时给出几种代码实现CRC计算。最后在APM32中使用芯片自带的CRC计算。整个流程完整，关键点阐述清楚。