CRC算法及其数论原理详解

以前的文章提到过CRC32C算法，实在没什么可写的了就干脆拿CRC算法水一篇文章（

模二运算

CRC 算法基于二进制域 GF(2) 上的多项式除法，其核心算法是模二运算

模二加、模二减

在任何特征为 p 的域中，加法是系数模 p 相加（减法同理）

所以 GF(2) 上的多项式加法就是模二加，等价于异或（XOR），可看作是不进位的加法（减法同理）

// 不进位（异或）
0b1101 + 0b0001 = 0b1100
// 不借位（异或）
0b1100 - 0b0001 = 0b1101

模二除

模二除类似长除法，但是减法用模二减代替

例如 0b101001 / 0b1101 = 0b110 余 0b111

至于模二乘，类似长乘法，但是加法用模二加代替（CRC用不到模二乘，这里就不写了）

CRC算法基本步骤

收发双方约定生成多项式 G(x)，其次数为 r

将载荷多项式 D(x) 左移 r 位
$$ x^{r} , D(x) $$

然后模二除 G(x)，得到余数 R(x)（商不重要，省略就行）
$$ R(x) = x^{r}D(x) mod G(x) $$

将余数附加到载荷后，最终发送的数据为：
$$ T(x) = x^{r} , D(x) + R(x) $$

接收方用相同 G(x) 做模二除法，若余数为 0，则认为无错
$$ T(x) mod G(x) = 0 $$

408真题解析

【2023统考真题】甲向乙发送数据，使用CRC算法，生成多项式为 $$ G(x) = x^{4} + x + 1 $$ 则乙方接收到比特串( D )时，可以断定无错误

A. 101110000
B. 101110100
C. 101111000
D. 101111100

解析：

首先要判断出所给数据哪一部分是载荷位，哪一部分是校验位

王道书解析：ABCD选项所给数据的前5位都是10111，所以可断定载荷部分为10111

更好的方法：多项式的次数为4，所以冗余码占4位，那么载荷就有5位，为10111

根据所给多项式，可知除数为10011，算出冗余码1100，故选D

查表法优化原理

标准 CRC 算法按位处理输入数据，判断是否需要异或生成多项式

查表法的原理是以字节为单位处理，利用线性性质实现预计算

CRC 在 GF(2) 上是线性的，也就是有
$$ CRC(A \oplus B) = CRC(A) \oplus CRC(B) $$

也就是说，可构建一张256项的预计算表，每项对应一个字节值（0x00 ~ 0xff）对应的 CRC 更新值

反射式和非反射式

反射的意思就是比特顺序反转

早期串行通信常先传 LSB（先接收二进制最低位），而 CRC 的数学模型基于 MSB

为了在 LSB 硬件中实现流式处理（在 LSB 硬件上使用 MSB 需要缓存整个字节），就采用反射方式让输入和输出反转，LSB 方式处理，等价于 MSB 直接处理原始未反转的数据

1
输入反转 + LSB + 输出反转 -> MSB

检错能力分析

已知余数 R(x) 的计算步骤为
$$ R(x) = x^{r}D(x) mod G(x) $$

在本分析中，我们不省略商，将商定义为 Q(x)

所以有
$$ x^{r}D(x) = Q(x)G(x) + R(x) $$

在 GF(2) 中有 a+a=0，将上式带入 T(x)，可得
$$ T(x) = x^{r} , D(x) + R(x) = Q(x)G(x) + R(x) + R(x) = Q(x)G(x) $$

所以
$$ T(x) = Q(x)G(x) \Rightarrow G(x) \mid T(x) $$

定义 E(x) 为错误图样多项式，其非零系数位置表示出错的比特位

则接收方实际收到的数据多项式是 T’(x)
$$ T’(x) = T(x) + E(x) $$

所以有
$$ T(x) \equiv 0 mod G(x) \Rightarrow T’(x) \equiv E(x) mod G(x) $$

也就是说，接收端计算的余数其实就是
$$ E(x) \bmod G(x) $$

若
$$ G(x) \nmid E(x) $$
则接收端计算的余数非零，检测到错误

若
$$ G(x)
\mid E(x)
$$
则接收端计算的余数为零，漏检

通俗地说，错误发生后，如果错误图样恰好是 G(x) 的倍式，那么接收端无法区分“这是原始数据”还是“这是出错后的数据”，这就导致了漏检

因此，CRC算法的检错能力完全由 G(x) 的代数性质决定

此处不会深入讨论代数编码理论，这对软件开发和408考研来说过于超纲，仅涉及结论

检测项目 100% 检出条件
单比特错误 G(0) = 1（常数项为1）
双比特错误 G(x) 的阶 > 最大帧长
奇数个比特错误 G(1) = 0（含因子 x + 1）
偶数个比特错误 无法保证 100% 检出
突发错误（长度 ≤ L） L ≤ G(x) 的次数

SSE4.2实现CRC32

SSE4.2指令集提供了四个指令用于计算CRC32，生成多项式为0x1EDC6F41（也就是 CRC-32C）

首先使用detect_sse42检测处理器是否支持SSE4.2指令集，如果不支持则降级到查表实现

C++20实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
module;

#include <intrin.h>

export module crc32c;

import <span>;
import <cstdint>;

constexpr uint32_t crc32c_table[256] = {
	0x00000000, 0xF26B8303, 0xE13B70F7, 0x1350F3F4, 0xC79A971F, 0x35F1141C, 0x26A1E7E8, 0xD4CA64EB,
	0x8AD958CF, 0x78B2DBCC, 0x6BE22838, 0x9989AB3B, 0x4D43CFD0, 0xBF284CD3, 0xAC78BF27, 0x5E133C24,
	0x105EC76F, 0xE235446C, 0xF165B798, 0x030E349B, 0xD7C45070, 0x25AFD373, 0x36FF2087, 0xC494A384,
	0x9A879FA0, 0x68EC1CA3, 0x7BBCEF57, 0x89D76C54, 0x5D1D08BF, 0xAF768BBC, 0xBC267848, 0x4E4DFB4B,
	0x20BD8EDE, 0xD2D60DDD, 0xC186FE29, 0x33ED7D2A, 0xE72719C1, 0x154C9AC2, 0x061C6936, 0xF477EA35,
	0xAA64D611, 0x580F5512, 0x4B5FA6E6, 0xB93425E5, 0x6DFE410E, 0x9F95C20D, 0x8CC531F9, 0x7EAEB2FA,
	0x30E349B1, 0xC288CAB2, 0xD1D83946, 0x23B3BA45, 0xF779DEAE, 0x05125DAD, 0x1642AE59, 0xE4292D5A,
	0xBA3A117E, 0x4851927D, 0x5B016189, 0xA96AE28A, 0x7DA08661, 0x8FCB0562, 0x9C9BF696, 0x6EF07595,
	0x417B1DBC, 0xB3109EBF, 0xA0406D4B, 0x522BEE48, 0x86E18AA3, 0x748A09A0, 0x67DAFA54, 0x95B17957,
	0xCBA24573, 0x39C9C670, 0x2A993584, 0xD8F2B687, 0x0C38D26C, 0xFE53516F, 0xED03A29B, 0x1F682198,
	0x5125DAD3, 0xA34E59D0, 0xB01EAA24, 0x42752927, 0x96BF4DCC, 0x64D4CECF, 0x77843D3B, 0x85EFBE38,
	0xDBFC821C, 0x2997011F, 0x3AC7F2EB, 0xC8AC71E8, 0x1C661503, 0xEE0D9600, 0xFD5D65F4, 0x0F36E6F7,
	0x61C69362, 0x93AD1061, 0x80FDE395, 0x72966096, 0xA65C047D, 0x5437877E, 0x4767748A, 0xB50CF789,
	0xEB1FCBAD, 0x197448AE, 0x0A24BB5A, 0xF84F3859, 0x2C855CB2, 0xDEEEDFB1, 0xCDBE2C45, 0x3FD5AF46,
	0x7198540D, 0x83F3D70E, 0x90A324FA, 0x62C8A7F9, 0xB602C312, 0x44694011, 0x5739B3E5, 0xA55230E6,
	0xFB410CC2, 0x092A8FC1, 0x1A7A7C35, 0xE811FF36, 0x3CDB9BDD, 0xCEB018DE, 0xDDE0EB2A, 0x2F8B6829,
	0x82F63B78, 0x709DB87B, 0x63CD4B8F, 0x91A6C88C, 0x456CAC67, 0xB7072F64, 0xA457DC90, 0x563C5F93,
	0x082F63B7, 0xFA44E0B4, 0xE9141340, 0x1B7F9043, 0xCFB5F4A8, 0x3DDE77AB, 0x2E8E845F, 0xDCE5075C,
	0x92A8FC17, 0x60C37F14, 0x73938CE0, 0x81F80FE3, 0x55326B08, 0xA759E80B, 0xB4091BFF, 0x466298FC,
	0x1871A4D8, 0xEA1A27DB, 0xF94AD42F, 0x0B21572C, 0xDFEB33C7, 0x2D80B0C4, 0x3ED04330, 0xCCBBC033,
	0xA24BB5A6, 0x502036A5, 0x4370C551, 0xB11B4652, 0x65D122B9, 0x97BAA1BA, 0x84EA524E, 0x7681D14D,
	0x2892ED69, 0xDAF96E6A, 0xC9A99D9E, 0x3BC21E9D, 0xEF087A76, 0x1D63F975, 0x0E330A81, 0xFC588982,
	0xB21572C9, 0x407EF1CA, 0x532E023E, 0xA145813D, 0x758FE5D6, 0x87E466D5, 0x94B49521, 0x66DF1622,
	0x38CC2A06, 0xCAA7A905, 0xD9F75AF1, 0x2B9CD9F2, 0xFF56BD19, 0x0D3D3E1A, 0x1E6DCDEE, 0xEC064EED,
	0xC38D26C4, 0x31E6A5C7, 0x22B65633, 0xD0DDD530, 0x0417B1DB, 0xF67C32D8, 0xE52CC12C, 0x1747422F,
	0x49547E0B, 0xBB3FFD08, 0xA86F0EFC, 0x5A048DFF, 0x8ECEE914, 0x7CA56A17, 0x6FF599E3, 0x9D9E1AE0,
	0xD3D3E1AB, 0x21B862A8, 0x32E8915C, 0xC083125F, 0x144976B4, 0xE622F5B7, 0xF5720643, 0x07198540,
	0x590AB964, 0xAB613A67, 0xB831C993, 0x4A5A4A90, 0x9E902E7B, 0x6CFBAD78, 0x7FAB5E8C, 0x8DC0DD8F,
	0xE330A81A, 0x115B2B19, 0x020BD8ED, 0xF0605BEE, 0x24AA3F05, 0xD6C1BC06, 0xC5914FF2, 0x37FACCF1,
	0x69E9F0D5, 0x9B8273D6, 0x88D28022, 0x7AB90321, 0xAE7367CA, 0x5C18E4C9, 0x4F48173D, 0xBD23943E,
	0xF36E6F75, 0x0105EC76, 0x12551F82, 0xE03E9C81, 0x34F4F86A, 0xC69F7B69, 0xD5CF889D, 0x27A40B9E,
	0x79B737BA, 0x8BDCB4B9, 0x988C474D, 0x6AE7C44E, 0xBE2DA0A5, 0x4C4623A6, 0x5F16D052, 0xAD7D5351
};

export class CRC32C {
public:
	void reset() noexcept {
		crc32_ = 0xffffffff;
	}

	static bool detect_sse42() noexcept {
		int cpu_info[4];
		__cpuid(cpu_info, 1);
		return (cpu_info[2] & (1 << 20)) != 0;
	}

	void update(std::span<const uint8_t> buffer) noexcept {
		static const bool has_sse42 = detect_sse42();

		if (has_sse42) [[likely]] {
			const uint8_t* start = buffer.data();
			const uint8_t* end = start + buffer.size();

			while (start + 8 <= end) {
				crc32_ = static_cast<uint32_t>(_mm_crc32_u64(crc32_, *reinterpret_cast<const uint64_t*>(start)));
				start += 8;
			}

			if (start + 4 <= end) {
				crc32_ = _mm_crc32_u32(crc32_, *reinterpret_cast<const uint32_t*>(start));
				start += 4;
			}
			if (start + 2 <= end) {
				crc32_ = _mm_crc32_u16(crc32_, *reinterpret_cast<const uint16_t*>(start));
				start += 2;
			}
			if (start < end) {
				crc32_ = _mm_crc32_u8(crc32_, *start);
			}
		}
		else {
			for (size_t i = 0; i < buffer.size(); ++i) {
				crc32_ = crc32c_table[(crc32_ ^ buffer[i]) & 0xff] ^ (crc32_ >> 8);
			}
		}
	}

	uint32_t final() noexcept {
		uint32_t result = crc32_ ^ 0xffffffff;
		reset();
		return result;
	}

	static uint32_t process(std::span<const uint8_t> buffer) noexcept {
		CRC32C c;
		c.update(buffer);
		return c.final();
	}

private:
	uint32_t crc32_ = 0xffffffff;
};
#网络安全 #C/C++ #考研408
CRC算法及其数论原理详解
https://crackme.net/articles/simdcrc/
作者
Brassinolide
发布于
2025年12月22日
许可协议