跳到主要内容CRC 循环冗余校验算法原理与实现 | 极客日志Javajava算法
CRC 循环冗余校验算法原理与实现
CRC 是一种基于模二除法的错误检测编码，广泛应用于数据存储和网络通信。核心思想是将数据视为多项式，用生成多项式除法获取余数作为校验码。关键参数包括宽度、生成多项式、初始值及位反转设置。实现方式有位驱动、查表法和硬件实现，其中查表法效率最高。 CRC 原理、常见标准（如 CRC-32），并提供了完整的 Java 查表法实现代码及验证示例，适用于需要数据完整性校验的场景。
Ne01 浏览 CRC（循环冗余校验）算法介绍
CRC 是一种非常流行的错误检测编码，广泛应用于数据存储（如硬盘、ZIP 文件）、网络通信（如以太网、Wi-Fi）、数字传输（如 SATA、USB）等领域。它的核心思想是通过一种基于模二除法的运算，为数据块生成一个简短、固定的校验码。
一、核心思想与基本原理
1.1 核心思想
将待发送的数据位串视为一个巨大的二进制数（例如，数据 110101 可以看作多项式 x⁵ + x⁴ + x² + 1 的系数），然后用一个预先选定的生成多项式（Generator Polynomial） 去除它。得到的余数就是 CRC 校验码，附在原数据后面一起发送。
1.2 模二运算（Modulo-2 Arithmetic）
这是 CRC 计算的数学基础。它非常简化：
- 加法/减法：等价于异或（XOR） 运算。
0 ± 0 = 0, 0 ± 1 = 1, 1 ± 0 = 1, 1 ± 1 = 0。
- 乘法/除法：与普通二进制运算类似，但中间的加减法使用模二加法（即异或）。
1.3 生成多项式（G）
这是一个关键的、双方预先约定好的除数。它通常用一个十六进制数或一个多项式来表示。
- 示例：CRC-16-CCITT 的标准生成多项式是 x¹⁶ + x¹² + x⁵ + 1。
- 表示方式：
- 多项式： x¹⁶ + x¹² + x⁵ + 1
- 二进制位串：
1 对应存在的项，0 对应不存在的项。最高位（x¹⁶）和最低位（1）总是1。所以是 1 0001 0000 0010 0001（17 位）。
- 十六进制：通常省略最高位的
1，用 16 位表示，即 0x1021。
1.4 基本计算步骤
- 附加零：在原始数据（长度为 k 位）的末尾附加 n 个零（n 是生成多项式的位数减一，即 CRC 码的长度）。
- 模二除法：用附加零后的新数据（k+n 位）除以生成多项式 G。
- 获取余数：除法运算得到的余数（长度一定是 n 位，不足则高位补零）就是 CRC 校验码。
- 组成帧：将原始数据与 CRC 校验码拼接在一起发送。
- 校验：接收方用同样的生成多项式 G 去除接收到的整个数据帧。如果余数为 0，则认为数据在传输过程中没有出错；如果余数不为 0，则肯定有错。
二、关键参数与变种
一个 CRC 算法由以下几个参数精确定义，不同的组合产生了各种各样的 CRC 标准：
- 宽度（Width）：即 CRC 校验码的位数（n），如 8, 16, 32 bits。常见的如 CRC-8, CRC-16, CRC-32。
- 生成多项式（Poly）：这是最重要的参数，决定了算法的特性。
- 初始值（Init）：在计算开始前，CRC 寄存器的初始值。通常用于避免全零数据产生全零 CRC 等问题。
- 输入反转（RefIn）：在计算之前，是否将每个输入字节（8 位）的位序反转（例如，第 7 位和第 0 位交换，第 6 位和第 1 位交换，等等）。
- 输出反转（RefOut）：在计算完成后、输出最终结果之前，是否将整个 CRC 寄存器的 n 位进行反转。
- 异或值（XorOut）：计算完成后，将整个 CRC 寄存器与这个值进行异或操作后再输出。
微信扫一扫，关注极客日志
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
相关免费在线工具
- Keycode 信息
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
- Escape 与 Native 编解码
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
- JavaScript / HTML 格式化
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
- JavaScript 压缩与混淆
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
- 加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
- Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
| 算法名称 | 多项式 (Poly) | 初始值 (Init) | RefIn | RefOut | 异或值 (XorOut) | 用途举例 |
|---|
| CRC-8 | 0x07 | 0x00 | False | False | 0x00 | ATM 头校验，一些通信协议 |
| CRC-16-CCITT | 0x1021 | 0xFFFF | False | False | 0x0000 | XMODEM, Bluetooth, P25 radio |
| CRC-16-IBM | 0x8005 | 0x0000 | True | True | 0x0000 | Modbus, USB Token packets |
| CRC-32 | 0x04C11DB7 | 0xFFFFFFFF | True | True | 0xFFFFFFFF | PKZIP, GZIP, PNG, Ethernet (IEEE 802.3) |
三、具体算法实现
3.1 位驱动算法（Bit-by-Bit）
这是最直接、最容易理解但效率最低的实现。它模拟了手算模二除法的过程。
#define POLY 0x04C11DB7
uint32_t crc32_bitwise(const uint8_t *data, size_t length) {
uint32_t crc = 0xFFFFFFFF;
for (size_t i = 0; i < length; i++) {
crc ^= (data[i] << 24);
for (int j = 0; j < 8; j++) {
if (crc & 0x80000000) {
crc = (crc << 1) ^ POLY;
} else {
crc = (crc << 1);
}
}
}
return crc ^ 0xFFFFFFFF;
}
特点：代码清晰，适合学习和理解原理。但每次处理一位，循环次数多，性能差。
3.2 查表法（Table-Driven / Lookup Table）
这是最常用、最高效的软件实现方法。其核心思想是空间换时间：预先计算好所有可能字节（256 种可能）的 CRC 结果，存入一个 256 大小的表中。计算时，每次处理一个字节，通过查表快速完成该字节对应的 8 轮位运算。
原理：一个字节的数据与当前 CRC 寄存器的高 8 位异或后，其结果（是一个 8 位的索引值）可以预先计算出它会导致 CRC 寄存器发生怎样的变化。这个变化结果就是查表得到的值。然后将当前 CRC 寄存器的低位移位后，再与查表得到的值进行异或。
uint32_t crc_table[256];
void build_crc_table() {
for (int i = 0; i < 256; i++) {
uint32_t crc = i << 24;
for (int j = 0; j < 8; j++) {
if (crc & 0x80000000)
crc = (crc << 1) ^ POLY;
else
crc = (crc << 1);
}
crc_table[i] = crc;
}
}
uint32_t crc32_fast(const uint8_t *data, size_t length) {
uint32_t crc = 0xFFFFFFFF;
for (size_t i = 0; i < length; i++) {
uint8_t index = (crc ^ (data[i] << 24)) >> 24;
crc = (crc << 8) ^ crc_table[index];
}
return crc ^ 0xFFFFFFFF;
}
特点：速度极快，比位驱动算法快一个数量级以上。是实际应用中的首选。
3.3 硬件实现
CRC 的模二运算本质是移位和异或，非常适合用硬件实现。
- 线性反馈移位寄存器（LFSR）：CRC 计算可以直接用一个 LFSR 电路来实现。生成多项式决定了哪些寄存器的输出需要反馈回来进行异或。
(上图是一个简单 CRC 的 LFSR 实现示意图)
特点：速度极快，每个时钟周期可以处理一位，不占用 CPU 资源。现代网卡、存储控制器等硬件通常都内置了 CRC 计算单元。
四、算法选择与总结
| 算法类型 | 优点 | 缺点 | 适用场景 |
|---|
| 位驱动算法 | 实现简单，易于理解，内存占用小 | 速度极慢 | 教学、理解原理、数据量极小 |
| 查表法 | 速度非常快 | 需要 256 * n 字节的静态表 | 绝大多数软件应用 |
| 硬件实现 | 速度最快，不占用 CPU | 需要特定的硬件支持 | 网络设备、高速存储接口 |
如何选择 CRC 算法？
通常不是自己设计一个 CRC，而是根据行业标准或协议要求选择一个现成的、经过验证的 CRC 变种（如上面的 CRC-16-CCITT 或 CRC-32）。选择时主要考虑：
- 错误检测能力：不同生成多项式对不同类型的错误（单比特、双比特、突发错误）检测能力不同。标准算法都经过充分测试。
- 数据长度：CRC-8 用于短数据，CRC-32 用于长数据帧（如以太网帧）。
- 历史与兼容性：遵循既定的协议标准（如 ZIP 文件必须用 CRC-32）。
六、Java 语言实现 CRC 校验示例
下面将提供 Java 语言实现的 CRC8、CRC16、CRC32 常用校验算法的完整代码。这些实现都使用高效的查表法。
6.1 完整的 CRC 校验工具类
import java.util.zip.CRC32;
import java.util.zip.Checksum;
public class CRCUtils {
public static final byte CRC8_POLY = (byte) 0x07;
public static final byte CRC8_ITU_POLY = (byte) 0x07;
public static final byte CRC8_ROHC_POLY = (byte) 0x07;
public static final byte CRC8_MAXIM_POLY = (byte) 0x31;
private static byte[] crc8Table;
private static void initCRC8Table(byte polynomial) {
crc8Table = new byte[256];
for (int i = 0; i < 256; i++) {
byte crc = (byte) i;
for (int j = 0; j < 8; j++) {
if ((crc & 0x80) != 0) {
crc = (byte) ((crc << 1) ^ polynomial);
} else {
crc = (byte) (crc << 1);
}
}
crc8Table[i] = crc;
}
}
public static byte calculateCRC8(byte[] data, byte polynomial) {
if (crc8Table == null || crc8Table[0] != (byte) (polynomial == CRC8_POLY ? 0 : crc8Table[0])) {
initCRC8Table(polynomial);
}
byte crc = 0x00;
for (byte b : data) {
crc = crc8Table[(crc ^ b) & 0xFF];
}
return crc;
}
public static byte calculateCRC8(byte[] data) {
return calculateCRC8(data, CRC8_POLY);
}
public static final int CRC16_IBM_POLY = 0x8005;
public static final int CRC16_CCITT_POLY = 0x1021;
public static final int CRC16_MODBUS_POLY = 0x8005;
public static final int CRC16_USB_POLY = 0x8005;
private static int[] crc16Table;
private static void initCRC16Table(int polynomial) {
crc16Table = new int[256];
for (int i = 0; i < 256; i++) {
int crc = i << 8;
for (int j = 0; j < 8; j++) {
if ((crc & 0x8000) != 0) {
crc = (crc << 1) ^ polynomial;
} else {
crc = crc << 1;
}
}
crc16Table[i] = crc & 0xFFFF;
}
}
public static int calculateCRC16(byte[] data, int polynomial, int initialValue, boolean refIn, boolean refOut, int xorOut) {
if (crc16Table == null) {
initCRC16Table(polynomial);
}
int crc = initialValue;
for (byte b : data) {
int index;
if (refIn) {
index = (crc ^ reverseByte(b)) & 0xFF;
} else {
index = ((crc >> 8) ^ (b & 0xFF)) & 0xFF;
}
crc = (refIn ? ((crc >> 8) & 0xFF) : (crc << 8)) ^ crc16Table[index];
crc &= 0xFFFF;
}
if (refOut) {
crc = reverseShort((short) crc) & 0xFFFF;
}
return crc ^ xorOut;
}
public static int calculateCRC16CCITT(byte[] data) {
return calculateCRC16(data, CRC16_CCITT_POLY, 0xFFFF, false, false, 0x0000);
}
public static int calculateCRC16Modbus(byte[] data) {
return calculateCRC16(data, CRC16_MODBUS_POLY, 0xFFFF, true, true, 0x0000);
}
public static int calculateCRC16IBM(byte[] data) {
return calculateCRC16(data, CRC16_IBM_POLY, 0x0000, true, true, 0x0000);
}
public static long calculateCRC32(byte[] data) {
Checksum crc32 = new CRC32();
crc32.update(data, 0, data.length);
return crc32.getValue();
}
public static long calculateCRC32Custom(byte[] data) {
int[] table = getCRC32Table();
int crc = 0xFFFFFFFF;
for (byte b : data) {
crc = (crc >>> 8) ^ table[(crc ^ (b & 0xFF)) & 0xFF];
}
return (crc ^ 0xFFFFFFFF) & 0xFFFFFFFFL;
}
private static int[] crc32Table = null;
private static int[] getCRC32Table() {
if (crc32Table != null) {
return crc32Table;
}
int polynomial = 0xEDB88320;
crc32Table = new int[256];
for (int i = 0; i < 256; i++) {
int crc = i;
for (int j = 0; j < 8; j++) {
if ((crc & 1) == 1) {
crc = (crc >>> 1) ^ polynomial;
} else {
crc = crc >>> 1;
}
}
crc32Table[i] = crc;
}
return crc32Table;
}
private static byte reverseByte(byte b) {
return (byte) (Integer.reverse(b << 24) & 0xFF);
}
private static short reverseShort(short s) {
return (short) (Integer.reverse(s << 16) & 0xFFFF);
}
public static String bytesToHex(byte[] bytes) {
StringBuilder sb = new StringBuilder();
for (byte b : bytes) {
sb.append(String.format("%02X ", b));
}
return sb.toString().trim();
}
public static void main(String[] args) {
String testData = "Hello, CRC!";
byte[] data = testData.getBytes();
System.out.println("测试数据：" + testData);
System.out.println("字节数据：" + bytesToHex(data));
System.out.println();
byte crc8 = calculateCRC8(data);
System.out.println("CRC8 校验值：0x" + String.format("%02X", crc8));
int crc16CCITT = calculateCRC16CCITT(data);
int crc16Modbus = calculateCRC16Modbus(data);
int crc16IBM = calculateCRC16IBM(data);
System.out.println("CRC16/CCITT 校验值：0x" + String.format("%04X", crc16CCITT));
System.out.println("CRC16/MODBUS 校验值：0x" + String.format("%04X", crc16Modbus));
System.out.println("CRC16/IBM 校验值：0x" + String.format("%04X", crc16IBM));
long crc32BuiltIn = calculateCRC32(data);
long crc32Custom = calculateCRC32Custom(data);
System.out.println("CRC32(内置) 校验值：0x" + String.format("%08X", crc32BuiltIn));
System.out.println("CRC32(自定义) 校验值：0x" + String.format("%08X", crc32Custom));
System.out.println("CRC32 实现一致性：" + (crc32BuiltIn == crc32Custom));
}
}
6.2 使用示例
public class CRCExample {
public static void main(String[] args) {
String message = "Hello World!";
byte[] data = message.getBytes();
System.out.println("=== CRC 校验示例 ===");
System.out.println("原始数据：" + message);
System.out.println();
byte crc8 = CRCUtils.calculateCRC8(data);
System.out.println("CRC8: 0x" + String.format("%02X", crc8));
int crc16Modbus = CRCUtils.calculateCRC16Modbus(data);
System.out.println("CRC16/MODBUS: 0x" + String.format("%04X", crc16Modbus));
long crc32 = CRCUtils.calculateCRC32(data);
System.out.println("CRC32: 0x" + String.format("%08X", crc32));
System.out.println();
System.out.println("=== 数据完整性验证 ===");
byte[] originalData = "Test Data".getBytes();
int originalCRC = CRCUtils.calculateCRC16Modbus(originalData);
System.out.println("原始 CRC: 0x" + String.format("%04X", originalCRC));
byte[] receivedData = "Test DataX".getBytes();
int receivedCRC = CRCUtils.calculateCRC16Modbus(receivedData);
System.out.println("接收 CRC: 0x" + String.format("%04X", receivedCRC));
if (originalCRC == receivedCRC) {
System.out.println("✓ 数据完整性验证通过");
} else {
System.out.println("✗ 数据完整性验证失败，数据可能已损坏");
}
}
}
6.3 针对特定协议的专用方法
public class ProtocolCRCUtils {
public static int calculateModbusCRC16(byte[] data) {
return CRCUtils.calculateCRC16Modbus(data);
}
public static int calculateXMODEMCRC16(byte[] data) {
return CRCUtils.calculateCRC16(data, CRCUtils.CRC16_CCITT_POLY, 0x0000, false, false, 0x0000);
}
public static boolean verifyModbusFrame(byte[] frame) {
if (frame.length < 3) return false;
byte[] data = new byte[frame.length - 2];
System.arraycopy(frame, 0, data, 0, data.length);
int calculatedCRC = calculateModbusCRC16(data);
int receivedCRC = ((frame[frame.length - 1] & 0xFF) << 8) | (frame[frame.length - 2] & 0xFF);
return calculatedCRC == receivedCRC;
}
public static byte[] addModbusCRC(byte[] data) {
int crc = calculateModbusCRC16(data);
byte[] frameWithCRC = new byte[data.length + 2];
System.arraycopy(data, 0, frameWithCRC, 0, data.length);
frameWithCRC[data.length] = (byte) (crc & 0xFF);
frameWithCRC[data.length + 1] = (byte) (crc >> 8);
return frameWithCRC;
}
}
6.4 主要特性
- 多种算法支持：支持 CRC8、CRC16（多种变体）、CRC32
- 高效实现：使用查表法提高计算效率
- 灵活性：支持自定义多项式、初始值等参数
- 标准兼容：内置常见标准算法的实现
- 实用工具：提供十六进制转换、数据验证等辅助方法
这个工具类可以满足大多数 Java 项目中 CRC 校验的需求，您可以根据具体的协议要求选择合适的算法变体。
