数据处理 — CRC32校验算法整理
CRC（循环冗余校验）技术文档整理
CRC32（Cyclic Redundancy Check 32-bit）是一种常见的校验和算法，广泛应用于网络通信、文件校验等领域。
核心思想
CRC32 利用一种基于二进制多项式的算法，将输入数据视为一个大整数，并通过一个固定的生成多项式进行模除运算，得到的余数即为 CRC 校验和。这个过程有效地将数据压缩为一个固定长度的值，该值可以用于验证数据的完整性。
多项式表示
数据和生成多项式都可以表示为二进制多项式。例如，数据 (1101011011) 可以表示为多项式：
x
10
+
x
9
+
x
7
+
x
5
+
x
4
+
x
2
+
x
1
x^{10} + x^9 + x^7 + x^5 + x^4 + x^2 + x^1
x10+x9+x7+x5+x4+x2+x1
生成多项式
CRC32 使用的生成多项式通常为：
x
32
+
x
26
+
x
23
+
x
22
+
x
16
+
x
12
+
x
11
+
x
10
+
x
8
+
x
7
+
x
5
+
x
4
+
x
2
+
x
+
1
x^{32} + x^{26} + x^{23} + x^{22} + x^{16} + x^{12} + x^{11} + x^{10} + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1
x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1
其对应的二进制表示为 0x04C11DB7。
初始值和最终异或
初始化 CRC 寄存器为 0xFFFFFFFF，最终结果再与 0xFFFFFFFF 进行异或处理。
逐字节处理
对输入数据逐字节进行处理，每处理一个字节时，将其与当前 CRC 值进行异或操作。对每个字节的每一位执行移位和条件异或操作，具体如下：
- 如果当前 CRC 值的最高位为 1，将 CRC 值左移一位，然后与生成多项式进行异或。
- 如果最高位为 0，只将 CRC 值左移一位。
得到最终 CRC 值
所有字节处理完毕后，得到的余数即为 CRC 校验和。
具体实现过程
数据与初始 CRC 值异或：对输入数据的每个字节，与当前 CRC 寄存器的高字节进行异或。
按位处理数据：将异或后的结果左移一位，并检查最高位是否为 1。如果为 1，则与生成多项式进行异或。如果为 0，则继续左移。这个过程重复 8 次（因为每个字节有 8 位）。
最终处理：在所有数据处理完成后，将最终的 CRC 值与
0xFFFFFFFF进行异或。
示例代码
以下是 Python 实现 CRC32 计算的示例代码：
def crc32(data):
crc = 0xFFFFFFFF
poly = 0x04C11DB7
for byte in data:
crc ^= byte << 24
for _ in range(8):
if crc & 0x80000000:
crc = (crc << 1) ^ poly
else:
crc <<= 1
crc &= 0xFFFFFFFF # 确保 CRC 结果在 32 位范围内
return crc ^ 0xFFFFFFFF
# 测试数据
data = b"123456789"
result = crc32(data)
print(f"CRC32: {result:08X}")
生成多项式选择原则
- 错误检测能力：不同的生成多项式在检测单比特错误、多比特错误、突发错误等方面的能力不同。选择合适的生成多项式可以提高错误检测的效率。
- 多项式长度：多项式的长度（即阶数）决定了 CRC 校验和的长度。常见的长度有 CRC-8、CRC-16、CRC-32 等。
- 标准化和兼容性：选择标准化的生成多项式可以确保不同设备和系统之间的兼容性。
常用生成多项式
CRC-8
- 多项式：
x
8
+
x
2
+
x
+
1
x^8 + x^2 + x + 1
x8+x2+x+1 - 二进制表示：
0x07 - 应用：常用于小型数据包和简单通信协议。
CRC-16
- CRC-16-IBM：
- 多项式：
x
16
+
x
15
+
x
2
+
1
x^{16} + x^{15} + x^2 + 1
x16+x15+x2+1 - 二进制表示：
0x8005 - 应用：广泛用于工业协议，如Modbus。
- 多项式：
- CRC-CCITT (XModem)：
- 多项式：
x
16
+
x
12
+
x
5
+
1
x^{16} + x^{12} + x^5 + 1
x16+x12+x5+1 - 二进制表示：
0x1021 - 应用：用于电信和网络协议。
- 多项式：
CRC-32
- 多项式：
x
32
+
x
26
+
x
23
+
x
22
+
x
16
+
x
12
+
x
11
+
x
10
+
x
8
+
x
7
+
x
5
+
x
4
+
x
2
+
x
+
1
x^{32} + x^{26} + x^{23} + x^{22} + x^{16} + x^{12} + x^{11} + x^{10} + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1
x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1 - 二进制表示：
0x04C11DB7 - 应用：广泛用于网络通信、文件校验和压缩文件格式，如ZIP和RAR。
规范和标准
许多协议和标准定义了特定的生成多项式，以确保不同实现之间的兼容性。以下是一些重要的标准和协议中定义的生成多项式：
以太网：
- 使用的生成多项式：
0x04C11DB7（CRC-32） - 用于帧校验序列（FCS）。
- 使用的生成多项式：
HDLC：
- 使用的生成多项式：
0x8408（CRC-16-CCITT） - 用于帧校验序列。
- 使用的生成多项式：
USB：
- 使用的生成多项式：
0x8005（CRC-16-IBM） - 用于数据包校验。
- 使用的生成多项式：
ZIP文件格式：
- 使用的生成多项式：
0x04C11DB7（CRC-32） - 用于文件压缩和解压缩过程中的数据完整性校验。
- 使用的生成多项式：
选择生成多项式的建议
- 应用场景：根据具体的应用场景选择生成多项式。例如，工业控制和通信协议通常选择 CRC-16，而网络协议和文件压缩通常选择 CRC-32。
- 标准化：尽量选择标准化的生成多项式，以确保不同系统和设备之间的兼容性。
- 错误检测需求：根据对错误检测能力的需求，选择适当的多项式长度和形式。例如，对于高可靠性要求的系统，可以选择更复杂和更长的生成多项式。
总之，生成多项式的选择对 CRC 算法的性能和可靠性有重要影响。在选择时，应考虑应用场景、标准化要求和错误检测能力。
按字节处理的示例说明
假设我们有一个数据字节 0x31，我们使用生成多项式 0x04C11DB7 来计算 CRC32 校验和。
初始设置：
- 数据：
0x31（ASCII 编码为00110001） - 生成多项式：
0x04C11DB7 - 初始 CRC 值：
0xFFFFFFFF
- 数据：
处理数据：
- 第一步：
crc = 0xFFFFFFFF ^ (0x31 << 24) = 0xCEFFFFFF - 第二步：逐位处理，从最高位到最低位，按上述规则进行移位和条件异或。
- 位 1：
0xCEFFFFFF高位为 1，左移后异或多项式：0x9DFFFFFE ^ 0x04C11DB7 = 0xD229A1C9 - 位 2：
0xD229A1C9高位为 1，左移后异或多项式：0xA4534392 ^ 0x04C11DB7 = 0xE7568A51 - 位 3：
0xE7568A51高位为 1，左移后异或多项式：0xCEAD14A2 ^ 0x04C11DB7 = 0x8F07B5F3 - 位 4：
0x8F07B5F3高位为 1，左移后异或多项式：0x1E0F6BE6 ^ 0x04C11DB7 = 0x5AF0C5A9 - 位 5：
0x5AF0C5A9高位为 0，仅左移：0xB5E18B52 - 位 6：
0xB5E18B52高位为 1，左移后异或多项式：0x6BC316A4 ^ 0x04C11DB7 = 0x2D345678 - 位 7：
0x2D345678高位为 0，仅左移：0x5A68ACF0 - 位 8：
0x5A68ACF0高位为 0，仅左移：0xB4D159E0
- 位 1：
- 处理后的中间结果：
0xB4D159E0
- 第一步：
处理所有字节后：
- 逐字节进行异或和移位操作，最终得到中间 CRC 值。
最终处理：
- 最终中间 CRC 值：
0xB4D159E0 - 将中间 CRC 值与
0xFFFFFFFF进行异或，得到最后的 CRC32 校验和：0x4B2EA61F
- 最终中间 CRC 值：
分布式运算和并行计算
CRC 算法通常用于串行处理数据，但在需要处理大数据集或高性能应用时，可以通过分布式运算和并行计算来优化计算效率。以下是一些优化方法：
数据分块：
- 将大数据集分成多个块，分别计算每个块的 CRC 值。
- 每个块的计算可以独立进行，从而可以在多核处理器或多台机器上并行处理。
并行处理：
- 使用多线程或多进程技术，在同一台机器上并行计算多个数据块的 CRC。
- 每个线程或进程处理一个数据块，最后将各个块的 CRC 值合并。
硬件加速：
- 使用专用的硬件，如 FPGA 或 GPU，加速 CRC 计算。
- 硬件加速器可以在更短的时间内完成大量数据的 CRC 计算。
增量计算：
- 对于实时数据流，可以使用增量计算的方法，不断更新 CRC 值，而无需重新计算整个数据集。
- 这种方法特别适用于网络通信中的实时错误检测。
CRC 合并分块计算的例子与原理分析
在实际应用中，我们常常需要将数据分块处理，然后合并各个分块的 CRC 值来得到最终的 CRC 值。这涉及到一些特定的数学原理和处理步骤。下面我们详细解释这些步骤，并给出具体的代码实现。
分块计算 CRC 的原理
CRC（循环冗余校验）的基础是多项式代数，其中数据和生成多项式都被表示为二进制多项式。CRC 合并的核心思想是如何将两个分开的 CRC 结果合并成一个整体的 CRC 值。为了理解这一点，我们需要回顾以下几个关键点：
多项式表示
数据和生成多项式都可以表示为多项式。例如，数据字节 (11010110) 可以表示为：
x
7
+
x
6
+
x
4
+
x
2
+
x
1
x^7 + x^6 + x^4 + x^2 + x^1
x7+x6+x4+x2+x1
多项式除法
CRC 的计算本质上是多项式除法的过程，将数据多项式除以生成多项式，得到的余数即为 CRC 校验和。
位移和余数
在分块处理数据时，每个块的 CRC 计算会影响到整个数据的最终 CRC 值。这是因为每个数据块在多项式除法中相当于一个部分商，必须通过适当的位移和余数计算来合并这些部分商。
生成多项式
CRC32 使用的生成多项式是：
x
32
+
x
26
+
x
23
+
x
22
+
x
16
+
x
12
+
x
11
+
x
10
+
x
8
+
x
7
+
x
5
+
x
4
+
x
2
+
x
+
1
x^{32} + x^{26} + x^{23} + x^{22} + x^{16} + x^{12} + x^{11} + x^{10} + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1
x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1
其对应的二进制表示为 0x04C11DB7。
反射式 CRC 和 0xEDB88320
0xEDB88320 是 0x04C11DB7 的位反射形式，用于优化计算：
- 正向生成多项式：
0x04C11DB7 - 位反射生成多项式：
0xEDB88320
使用位反射形式可以简化硬件实现，并且在处理低位优先的数据时更为方便。通过位反射，我们可以使用相同的逻辑来处理高位优先和低位优先的数据。
分块计算的详细示例
假设我们有如下数据：“123456789”，我们将其分为两个块进行处理：
- 块1：
"1234"（ASCII 编码为0x31 0x32 0x33 0x34） - 块2：
"56789"（ASCII 编码为0x35 0x36 0x37 0x38 0x39）
计算块1的 CRC
初始 CRC 值：
0xFFFFFFFF处理字节
0x31（”1″的ASCII编码）：- CRC =
0xFFFFFFFF ^ (0x31 << 24) = 0xCEFFFFFF - 执行 8 次移位和条件异或：
- 位1：
0x9DFFFFFE ^ 0x04C11DB7 = 0xD229A1C9 - 位2：
0xA4534392 ^ 0x04C11DB7 = 0xE7568A51 - 位3：
0xE7568A51 ^ 0x04C11DB7 = 0x8F07B5F3 - 位4：
0x1E0F6BE6 ^ 0x04C11DB7 = 0x5AF0C5A9 - 位5：
0x5AF0C5A9高位为0，仅左移：0xB5E18B52 - 位6：
0xB5E18B52 ^ 0x04C11DB7 = 0x6BC316A4 - 位7：
0x6BC316A4高位为0，仅左移：0xD7862D48 - 位8：
0xD7862D48 ^ 0x04C11DB7 = 0xA1E10F77
- 位1：
- CRC =
继续处理其余字节，得到块1的 CRC 中间值
0xC814E496。
计算块2的 CRC
- 初始 CRC 值：
0xFFFFFFFF - 按照上述步骤逐字节处理，得到块2的 CRC 中间值
0x5A5AA6F4。
合并块的 CRC 值
为了合并两个块的 CRC 值，我们需要对第一个块的 CRC 值进行预处理，并结合第二个块的 CRC 值。
预处理块1的 CRC 值
我们需要将块1的 CRC 值根据块2的长度（5个字节）进行位移和多项式余数计算。具体步骤如下：
- 块1的 CRC 值
0xC814E496进行 5 字节（40位）的预处理：- 对每一位进行条件异或和移位，最终得到预处理后的 CRC 值。
合并块1和块2的 CRC 值
- 使用预处理后的 CRC 值与块2的 CRC 值进行 XOR 操作。
- 按照具体的多项式合并逻辑，计算得到最终的 CRC 值。
代码实现示例
以下是一个具体的代码实现，用于计算和合并分块 CRC 值：
import zlib
def crc32_combine(crc1, crc2, len2):
# 预处理第一个 CRC 值，长度为 len2 的数据块大小
for _ in range(len2 * 8):
if crc1 & 1:
crc1 = (crc1 >> 1) ^ 0xEDB88320
else:
crc1 >>= 1
return crc1 ^ crc2
def calculate_crc32(data):
return zlib.crc32(data) & 0xFFFFFFFF
def calculate_crc32_in_chunks(data, chunk_size):
chunks = [data[i:i + chunk_size] for i in range(0, len(data), chunk_size)]
crc = 0
for chunk in chunks:
chunk_crc = calculate_crc32(chunk)
crc = crc32_combine(crc, chunk_crc, len(chunk))
return crc
# 测试数据
data = b"123456789"
chunk_size = 4 # 将数据分成两个块
result = calculate_crc32_in_chunks(data, chunk_size)
print(f"CRC32: {result:08X}")
代码解释
crc32_combine：该函数用于合并两个分块 CRC 值，len2是第二个数据块的长度。calculate_crc32：函数计算单个数据块的 CRC 值。calculate_crc32_in_chunks：函数将数据分块并计算每块的 CRC 值，最后合并得到整体的 CRC 值。
通过上述示例，可以更好地理解如何分块计算和合并 CRC 值，以确保数据完整性检测的准确性。
