CRC(循环冗余校验)

这是一个使用 CMake 构建的 C 项目模板，包含源代码和单元测试结构，支持 Clang 编译器，并配置了代码格式管理。

CRC(循环冗余校验)

参考资料

1. 字节序

字节序 （Endianness）是指在计算机内存中或数字通信链路中，多字节数据的排列顺序。它影响数据在不同系统之间的传输和存储方式。

1.1 大端序与小端序

大端序（Big Endian） ：高位字节存储在低地址处，低位字节存储在高地址处。
小端序（Little Endian） ：低位字节存储在低地址处，高位字节存储在高地址处。

示例

假设变量 x 类型为 int，值为 0x01234567：

地址	小端序	大端序
0x100	0x67	0x01
0x101	0x45	0x23
0x102	0x23	0x45
0x103	0x01	0x67

对于 0x0A0B0C0D：

大端序 ：0x0A 0x0B 0x0C 0x0D
小端序 ：0x0D 0x0C 0x0B 0x0A

混合模式示例（高16位和低16位以大端序存储，但16位内部以小端存储）：

....|0x0B|0x0A|0x0D|0x0C|....

1.2 处理器体系

不同处理器架构对字节序的支持如下：

小端序 ：x86、MOS Technology 6502、Z80、VAX、PDP-11 等。
大端序 ：Motorola 6800、Motorola 68000、PowerPC 970、System/370、SPARC（除 V9 外）等。
可配置字节序 ：ARM、PowerPC（除 PowerPC 970 外）、DEC Alpha、SPARC V9、MIPS、PA-RISC 及 IA64。

1.3 网络序

网络传输通常采用大端序 ，也称为网络字节序 。IP 协议定义大端序为标准字节序。

转换函数

Berkeley 套接字定义了以下函数用于字节序转换：

htonl、htons：主机字节序转网络字节序。
ntohl、ntohs：网络字节序转主机字节序。

1.4 位序

位序决定了数据在串行通信中的传输顺序：

小端序（先传低位）：
- RS-232、RS-422、RS-485、USB、以太网（每字节内低位先传）。
大端序（先传高位）：
- I2C 协议、SPI 协议、摩尔斯电码。

2. 循环冗余校验（CRC）

循环冗余校验（CRC） 是一种错误检测代码，广泛应用于数字网络和存储设备中，用于检测数据的意外更改。进入这些系统的数据块会根据其内容的多项式除法的余数附加一个短*校验值。*在检索时，重复计算，如果检查值不匹配，则可以采取纠正措施来防止数据损坏。CRC 可用于纠错（请参阅位过滤器）。[1]

之所以称为 CRC，是因为校验（数据验证）值是一种冗余（它在不添加信息的情况下扩展消息）并且该算法基于循环码。CRC 很受欢迎，因为它们易于在二进制硬件中实现，易于进行数学分析，并且特别擅长检测由传输通道中的噪声引起的常见错误。因为校验值的长度是固定的，所以生成它的函数偶尔会被用作哈希函数。

当其校验值是n位长时，CRC 称为n位 CRC 。对于给定的n，可能有多个 CRC，每个都有不同的多项式。这样的多项式具有最高次数n，这意味着它有n + 1项。换句话说，多项式的长度为n + 1；它的编码需要n + 1位。请注意，大多数多项式规范会丢弃MSB或LSB，因为它们始终为 1。

最简单的错误检测系统，即奇偶校验位，实际上是一个 1 位的 CRC：它使用生成多项式 x + 1（两项），[3]并命名为 CRC-1。

2.1 数据完整性

CRC 的设计目标是防止通信通道上的常见错误类型，并提供快速且合理的数据完整性保证。然而，CRC 不适合防止故意篡改数据，因为攻击者可以重新计算 CRC 并替换数据而不被检测到。

安全性建议

使用消息认证码（MAC） 或数字签名 来防止恶意篡改。
结合密码学哈希函数（如 SHA 系列）增强安全性。

2.2 计算方法

CRC 的计算基于多项式除法。以下是计算步骤的详细说明：

示例

假设需要编码的消息为 11010011101100，使用生成多项式 x³ + x + 1（二进制表示为 1011），计算 3 位 CRC。

消息填充 在消息后添加 n 个零（n 为 CRC 长度）。
```
消息：11010011101100

填充后：11010011101100 000
```
多项式除法 使用模 2 除法（不考虑进位和借位）进行计算。
```
11010011101100 000 ÷ 1011 = 商 + 余数
```
结果最终得到的余数即为 CRC 值。例如，假设余数为 101，则 CRC 值为 101。

注意事项

生成多项式的最高次幂决定 CRC 的长度。
多项式的 MSB 和 LSB 通常固定为 1，因此在描述时可能省略。

In this example, we shall encode 14 bits of message with a 3-bit CRC, with a polynomial x3 + x + 1. The polynomial is written in binary as the coefficients; a 3rd-degree polynomial has 4 coefficients (1x3 + 0x2 + 1x + 1). In this case, the coefficients are 1, 0, 1 and 1. The result of the calculation is 3 bits long, which is why it is called a 3-bit CRC. However, you need 4 bits to explicitly state the polynomial.

Start with the message to be encoded:

11010011101100

This is first padded with zeros corresponding to the bit length n of the CRC. This is done so that the resulting code word is in systematic form. Here is the first calculation for computing a 3-bit CRC:

11010011101100 000 <--- input right padded by 3 bits
1011               <--- divisor (4 bits) = x³ + x + 1
------------------
01100011101100 000 <--- result

The algorithm acts on the bits directly above the divisor in each step. The result for that iteration is the bitwise XOR of the polynomial divisor with the bits above it. The bits not above the divisor are simply copied directly below for that step. The divisor is then shifted right to align with the highest remaining 1 bit in the input, and the process is repeated until the divisor reaches the right-hand end of the input row. Here is the entire calculation:

11010011101100 000 <--- input right padded by 3 bits
1011               <--- divisor
01100011101100 000 <--- result (note the first four bits are the XOR with the divisor beneath, the rest of the bits are unchanged)
 1011              <--- divisor ...
00111011101100 000
  1011
00010111101100 000
   1011
00000001101100 000 <--- note that the divisor moves over to align with the next 1 in the dividend (since quotient for that step was zero)
       1011             (in other words, it doesn't necessarily move one bit per iteration)
00000000110100 000
        1011
00000000011000 000
         1011
00000000001110 000
          1011
00000000000101 000
           101 1
-----------------
00000000000000 100 <--- remainder (3 bits).  Division algorithm stops here as dividend is equal to zero.

每一次Xor都是固定不动的生成项与其对应的数据首位“消1”。

那我们就可以假想出一个与生成项长度一致的“盒子”，取出一部分的数据出来若首位是1时就进行一次Xor，遇到0则左移到1为止，左移造成的右端的空缺用0补充。而这里0希望理解为一种“存储”，它“存储” 生成项中未和数据进行计算的那一部分，按顺序先后附加被计算数据的后面，当先一部分的数据全部计算之后，实际上“盒子”中剩下都是未和数据计算的部分的“和”11011 xor 10110 = 11011 xor ( 10000 xor 00100 xor 00010)(这里实际上就是Xor的交换律到后面就会体会到他的强大)

2.3 数学公式

CRC为校验和的一种，是两个字节数据流采用二进制除法（没有进位，使用XOR来代替减法）相除所得到的余数。其中被除数是需要计算校验和的信息数据流的二进制表示；除数是一个长度为的预定义（短）的二进制数，通常用多项式的系数来表示。在做除法之前，要在信息数据之后先加上个0。

CRC是基于有限域GF(2)（即除以2的同余）的多项式环。简单的来说，就是所有系数都为0或1（又叫做二进制）的多项式系数的集合，并且集合对于所有的代数操作都是封闭的。例如：

$(x^{3}+x)+(x+1)=x^{3}+2x+1\equiv x^{3}+1$

2会变成0，因为对系数的加法运算都会再取2的模数。乘法也是类似的：

$(x^{2}+x)(x+1)=x^{3}+2x^{2}+x\equiv x^{3}+x$

同样可以对多项式作除法并且得到商和余数。例如，如果用x3 + x2 + x除以x + 1。会得到：

${\frac {(x^{3}+x^{2}+x)}{(x+1)}}=(x^{2}+1)-{\frac {1}{(x+1)}}$

也就是说，

$(x^{3}+x^{2}+x)=(x^{2}+1)(x+1)-1$

等价于

$(x^{2}+x+1)x=(x^{2}+1)(x+1)-1$

这里除法得到了商x2 + 1和余数-1，因为是奇数所以最后一位是1。

字符串中的每一位其实就对应了这样类型的多项式的系数。为了得到CRC，首先将其乘以 $x^{n}$ ，这里n是一个固定多项式的**阶数**，然后再将其除以这个固定的多项式，余数的系数就是CRC。

在上面的等式中， $x^{2}+x+1$ 表示了本来的信息位是111, 是所谓的钥匙，而余数1也就是 $x^{0}$ 就是CRC. key的最高次为1,所以将原来的信息乘上 $x^{1}$ 来得到 $x^{3}+x^{2}+x$ ，也可视为原来的信息位补1个零成为1110。

一般来说，其形式为：

$M(x)\cdot x^{n}=Q(x)\cdot K(x)-R(x)$

这里M(x)是原始的信息多项式。K(x)是阶的“钥匙”多项式。 $M(x)\cdot x^{n}$ 表示了将原始信息后面加上个0。R(x)是余数多项式，即是CRC“校验和”。在通信中，发送者在原始的信息数据M后附加上�位的R（替换本来附加的0）再发送。接收者收到M和R后，检查 $M(x)\cdot x^{n}+R(x)$ 是否能被整除。如果是，那么接收者认为该信息是正确的。值得注意的是 $M(x)\cdot x^{n}+R(x)$ 就是发送者所想要发送的数据。这个串又叫做codeword.

CRCs经常被叫做“校验和”，但是这样的说法严格来说并不是准确的，因为技术上来说，校验“和”是通过加法来计算的，而不是CRC这里的除法。

2.4 应用场景

数据传输 ：确保网络数据包的完整性。
存储设备 ：检测硬盘或闪存中的数据损坏。
嵌入式系统 ：验证固件更新的正确性。

总结

本文详细介绍了字节序和循环冗余校验（CRC）的相关知识。通过理解字节序的概念及其在不同系统中的应用，可以更好地处理跨平台数据传输问题。而 CRC 作为一种高效的错误检测机制，能够有效保障数据的完整性，但在安全性要求较高的场景下需结合其他加密技术使用。

环境

Visual Studio Code 中使用 C++

对应环境在Visual Studio Code 官网文档中心都有详细说明，点击对应链接查看配置过程

Linux

GCC on Linux

macOS

Clang on macOS

Windows

Microsoft C++ on Windows

GCC on Windows

请确保已安装以下工具：

ClangFormat包含在LLVM软件包中

安装后将对应软件的bin目录，添加到系统环境变量 PATH 中，以便在命令行中方便地访问

LLVM
- ClangFormat: 代码格式化工具
CMake : 跨平台的构建系统生成工具
Ninja: 小巧且高效的构建系统
Python: 脚本编写

使用方法

运行项目

以下代码展示如何编写并运行一个简单的测试示例：

代码格式管理

项目中配置了 clang-format，用于统一代码风格。你可以在 .vscode 的 settings.json 中配置自动格式化支持，或者手动运行格式化脚本 scripts/run-clang-format-from-config.py。

代码格式化

该项目包含 .clang-format 和 clang-format-config.json 文件，可以使用 clang-format 工具统一代码风格。在 .vscode 目录中还设置了代码格式的自动化管理。

格式化命令：

python .\scripts\run-clang-format-from-config.py

项目结构

TEMPLATE
│
├── .vscode                  # VSCode 配置，支持 clang-format
│
├── build                    # 构建生成目录
│
├── cmake                    # CMake 配置
│   └── clang.cmake          # Clang 编译器的 CMake 配置
│
├── scripts                  # 脚本目录
│   └── run-clang-format-from-config.py # 格式化脚本
│
├── src                      # 源代码目录
│   └── crc          		 # crc模块
│
├── test                     # 单元测试目录
│   └── crc          		 # crc模块测试
│
├── .clang-format            # Clang 格式化配置文件
├── .gitignore               # Git 忽略文件
├── CMakeLists.txt           # 顶层 CMake 配置文件
├── LICENSE                  # 许可证
└── README.md                # 项目说明文件

贡献

欢迎任何形式的贡献！如果你发现任何问题或希望增加新功能，请提交 Issue 或 Pull Request。

提交指南

遵循约定式提交规范。请确保你的提交信息符合以下格式：

<类型>(<范围>): <描述>

其中：

类型：用于描述提交的类别，常见的类型包括：
- feat：新功能
- fix：修复问题
- docs：仅文档更新
- style：不影响代码含义的更改（例如格式化、缺少分号等）
- refactor：既不修复错误也不添加功能的代码更改
- test：添加缺失的测试或修改现有测试
- chore：构建过程或辅助工具的变动
范围：提交影响的模块或文件，可以省略。
描述：简要说明修改内容。

示例

feat(calculator): 添加乘法功能
fix(stack): 修复栈溢出问题
docs(readme): 更新安装说明
chore(ci): 添加 GitHub Actions 配置

提交步骤

Fork 此仓库
创建分支 (git checkout -b feat/your-feature)
按照约定式提交规范提交更改 (git commit -m 'feat(scope): 添加新功能')
推送到分支 (git push origin feat/your-feature)
创建一个 Pull Request

许可证

此项目基于 MIT许可证。详细信息请查看 LICENSE 文件。

Name		Name	Last commit message	Last commit date
Latest commit History 1 Commit
.vscode		.vscode
cmake		cmake
docs/vscode		docs/vscode
scripts		scripts
src		src
test		test
.clang-format		.clang-format
.gitattributes		.gitattributes
.gitignore		.gitignore
CMakeLists.txt		CMakeLists.txt
CMakePresets.json		CMakePresets.json
LICENSE		LICENSE
README.md		README.md
clang-format-config.json		clang-format-config.json

License

VectorQiu/crc

Folders and files

Latest commit

History

Repository files navigation

CRC(循环冗余校验)

目录