CRC校验算法详解、C语言实现
一、前言
1.1 CRC算法介绍
CRC（Cyclic Redundancy Check）校验算法是一种广泛应用于数据通信和存储系统中的错误检测方法，主要用于检测数据在传输过程中是否发生了改变。CRC算法通过计算一个固定长度的校验码，将该校验码附加到原始数据的末尾，接收方在接收到数据后重新计算校验码并与接收到的校验码进行比较，以此判断数据在传输过程中是否发生了错误。这种校验机制不仅能够检测出大多数类型的错误，而且计算效率高，占用资源少，因此在各种通信协议、文件系统、磁盘驱动器和网络协议中都有广泛应用。
CRC算法的原理基于多项式除法。在CRC校验中，数据被视为一个系数为0或1的多项式序列，而CRC校验码则是通过使用一个预定义的生成多项式对该数据多项式进行模2除法运算得到的。生成多项式的选择对CRC算法的错误检测能力有重要影响，通常选取的生成多项式能够检测出尽可能多类型的错误。在计算CRC校验码时，原始数据与生成多项式的模2除法的结果被附加到数据的末尾，形成一个完整的数据包。在接收端，同样使用生成多项式对数据包进行模2除法，如果余数为零，则认为数据在传输过程中未发生错误。
CRC算法的具体实现过程如下：
- 将待发送的数据视为一个二进制多项式D(x)，其中每一位代表一个系数。
- 选取一个生成多项式G(x)，该多项式的长度决定了CRC校验码的长度。
- 对D(x)乘以x^n（n为生成多项式的长度减1），形成一个与G(x)同阶的多项式。
- 使用生成多项式G(x)对该扩展后的多项式进行模2除法，得到的余数即为CRC校验码。
- 将CRC校验码附加到原始数据的末尾，形成完整的数据包。
- 在接收端，对数据包再次进行相同的模2除法运算，若余数为零，则认为数据包未发生错误。
CRC校验算法在实际应用中非常灵活，可以通过选择不同的生成多项式来适应不同场合的需求。例如，CRC-32使用一个32位的生成多项式，可以检测出绝大多数常见的错误类型，包括所有奇数位错误、所有双位错误（在数据长度不超过31位的情况下）、所有突发错误（长度小于等于32位）以及大多数长度超过32位的突发错误。
在C语言中实现CRC算法时，可以利用位运算和循环结构来高效地完成模2除法运算。下面是使用标准C库函数和位运算符来实现。
下面是一个CRC-32算法的C语言实现示例：
#include <stdint.h>
uint32_t crc32(const unsigned char *buf, size_t len) {
uint32_t crc = 0xFFFFFFFF;
const unsigned char *end = buf + len;
uint32_t table[256];
// Pre-compute the CRC table
for (int i = 0; i < 256; i++) {
uint32_t c = i;
for (int j = 0; j < 8; j++) {
if (c & 1) {
c = 0xEDB88320 ^ (c >> 1);
} else {
c = c >> 1;
}
}
table[i] = c;
}
// Process each byte of the data
while (buf < end) {
crc = table[(crc ^ *buf++) & 0xFF] ^ (crc >> 8);
}
return crc ^ 0xFFFFFFFF;
}
这段代码首先预计算了一个CRC表，用于加速后续的模2除法运算，然后逐字节处理输入数据，最终返回CRC校验码。通过这种方式，CRC算法能在保证准确性的同时，达到较高的计算速度，满足实时性和效率的要求。
CRC校验算法凭借其高效的错误检测能力，在数据通信和存储系统中发挥着不可或缺的作用。无论是嵌入式系统、网络通信还是文件系统，CRC都是确保数据完整性和可靠性的一种重要手段。
1.2 CRC校验算法分类
CRC（Cyclic Redundancy Check）校验算法是一种基于多项式除法的错误检测方法，用于数据传输和存储中的完整性验证。CRC算法的分类主要依据生成多项式的长度和特性，这些差异导致了CRC校验码的不同长度和错误检测能力。CRC16、CRC32、CRC8等都是根据生成多项式的位数命名的，分别表示16位、32位和8位的校验码长度。
CRC校验算法分类的情况：
-
CRC8：
- CRC8生成的校验码长度为8位（1字节）。它通常用于小数据量的校验，比如在一些简单的通信协议中，或者是对字节级数据进行校验。
- 由于校验码长度较短，CRC8的冲突概率较高，但是计算速度非常快。
-
CRC16：
- CRC16生成的校验码长度为16位（2字节）。它适用于中等大小的数据块校验，例如在串行通信中或者对短消息进行校验。
- CRC16的冲突概率比CRC8低，但仍然存在一定的可能性，尤其是在校验较长的数据流时。
-
CRC32：
- CRC32生成的校验码长度为32位（4字节）。它是最常见的CRC算法，适用于对大型数据块、文件或者网络数据包进行校验。
- CRC32提供了更高级别的错误检测能力，冲突率极低，适合于需要高度可靠性的数据传输场景。
- 计算CRC32虽然相对于CRC16和CRC8要稍微慢一些，但由于现代处理器的速度，这种差异在实际应用中往往可以忽略。
除了上述常见的CRC版本，还有CRC64，生成64位的校验码，适用于要求极高可靠性的应用中。
1.3 为什么有CRC16、CRC32等不同版本？
不同版本的CRC校验算法之所以存在，主要是为了平衡错误检测能力和计算效率。在某些情况下，可能不需要过于强大的错误检测能力，例如在短距离、低噪声环境下的通信，这时使用CRC8或CRC16就足够了，因为它们计算速度快，硬件实现简单，可以节省资源。
然而，在长距离、高噪声环境下，或者在需要高度可靠性的数据传输中，比如互联网数据包的传输，CRC32或CRC64就是更好的选择，因为它们可以检测到更多类型的错误，尽管计算成本会相应增加。
此不同的应用领域可能有各自的标准和要求，比如在某些通信协议中，CRC16的特定变体（如CRC-CCITT、CRC-16/ARC）是被规定的，而在其他地方，比如压缩文件和网络传输中，CRC32可能是首选。
CRC16、CRC32等不同版本的CRC校验算法是为了适应不同应用场景的需求，它们在错误检测能力和计算效率之间提供了不同的权衡。
1.5 查表法
在CRC（Cyclic Redundancy Check）算法的实现中，经常使用一个预计算的查找表（lookup table），这个查找表就是一个数组，用来加速CRC的计算过程。这个数组通常被称为“CRC表”或“CRC查找表”。
CRC算法的核心是基于二进制的多项式除法，其中使用的除数是一个固定的多项式（即生成多项式）。在软件实现中，特别是当需要快速计算CRC校验值时，查找表可以显著减少计算量。
查找表的工作原理：
-
预计算： 在CRC算法的初始化阶段，程序会预先计算出所有可能的8位（或其他位数，取决于查找表的设计）输入与生成多项式进行模2除法的结果，并将这些结果存储在一个数组中。这个数组的大小通常是256个元素，每个元素对应一个8位输入的CRC校验值。
-
快速计算： 当实际计算数据的CRC校验值时，算法会对数据进行逐字节处理。对于每个字节，算法会在查找表中查找对应的CRC值，然后与之前计算得到的部分CRC值进行异或操作。这个过程会重复直到所有的数据字节都被处理完毕。
-
最终CRC值： 在处理完所有数据后，累积的CRC值会经过可能的反转（reflect）和初始值（seed）调整，得到最终的CRC校验值。
使用查找表的主要优点是减少了每次迭代中的复杂计算，尤其是避免了多项式除法，而代之以简单的数组查找和异或操作，这在大多数现代计算机架构上是非常快速的。
查找表的生成：
查找表的生成涉及对每一个可能的8位输入（从0到255）执行CRC算法的完整计算过程，并存储最终结果。这个过程只在程序启动时执行一次，之后就可以复用这个查找表来快速计算任何数据的CRC校验值。
查找表的使用使得CRC计算在软件中变得既快速又高效，尤其在实时系统和大量数据处理中，这一点尤为重要。
二、代码实操
2.1 文件校验-CRC8
下面是一个使用C语言实现的CRC8校验值计算的示例代码。这里使用一个常见的生成多项式 0x07（也就是多项式 x^8 + x^2 + x^1 + x^0）来生成CRC8校验和。 使用一个查找表来优化计算过程。
#include <stdio.h>
#include <stdint.h>
#include <fcntl.h>
#include <unistd.h>
// CRC8生成多项式
#define POLYNOMIAL 0x07
// 初始化CRC8查找表
uint8_t crc8_table[256];
void init_crc8_table(void)
{
uint8_t i, j;
for (i = 0; i < 256; i++)
{
uint8_t crc = i;
for (j = 8; j; j--)
{
if (crc & 0x80)
crc = (crc << 1) ^ POLYNOMIAL;
else
crc <<= 1;
}
crc8_table[i] = crc;
}
}
uint8_t crc8(const void *data, size_t len)
{
const uint8_t *byte = data;
uint8_t crc = 0x00;
for (; len > 0; len--)
{
crc = crc8_table[(crc ^ *byte++) & 0xFF];
}
return crc;
}
int main(int argc, char *argv[])
{
int fd;
uint8_t buffer[4096];
size_t bytes_read;
uint8_t crc;
if (argc != 2)
{
fprintf(stderr, "Usage: %s filename\n", argv[0]);
return 1;
}
// 初始化CRC8查找表
init_crc8_table();
// 打开文件
fd = open(argv[1], O_RDONLY);
if (fd == -1)
{
perror("Error opening file");
return 1;
}
// 读取文件并计算CRC8校验值
crc = 0x00;
while ((bytes_read = read(fd, buffer, sizeof(buffer))) > 0)
{
crc = crc8(buffer, bytes_read);
}
close(fd);
// 输出CRC8校验值
printf("CRC8 checksum: 0x%02X\n", crc);
return 0;
}
这段代码首先定义了一个CRC8查找表，并通过init_crc8_table函数进行初始化。crc8函数用于计算给定数据块的CRC8校验值，它使用查找表来进行快速计算。main函数负责打开文件、读取数据并调用crc8函数来计算整个文件的CRC8校验值。
2.2 文件校验-CRC16
下面是使用CRC16并采用CCITT标准生成多项式（0x1021，即多项式x^16 + x^12 + x^5 + x^0）来计算文件CRC16校验值的C语言代码示例。与之前的CRC8示例类似，这里也会使用查找表来优化计算过程。
#include <stdio.h>
#include <stdint.h>
#include <fcntl.h>
#include <unistd.h>
// CRC16 CCITT生成多项式
#define POLYNOMIAL 0x1021
// 初始化CRC16查找表
uint16_t crc16_table[256];
void init_crc16_table(void)
{
uint16_t crc, poly;
uint8_t i, j;
for (i = 0; i < 256; i++)
{
crc = i;
for (j = 8; j; j--)
{
if (crc & 0x0001)
crc = (crc >> 1) ^ POLYNOMIAL;
else
crc >>= 1;
}
crc16_table[i] = crc;
}
}
uint16_t crc16(const void *data, size_t len)
{
const uint8_t *byte = data;
uint16_t crc = 0xFFFF;
while (len--)
{
crc = (crc >> 8) ^ crc16_table[(crc ^ *byte++) & 0xFF];
}
return crc;
}
int main(int argc, char *argv[])
{
int fd;
uint8_t buffer[4096];
size_t bytes_read;
uint16_t crc;
if (argc != 2)
{
fprintf(stderr, "Usage: %s filename\n", argv[0]);
return 1;
}
// 初始化CRC16查找表
init_crc16_table();
// 打开文件
fd = open(argv[1], O_RDONLY);
if (fd == -1)
{
perror("Error opening file");
return 1;
}
// 读取文件并计算CRC16校验值
crc = 0xFFFF;
while ((bytes_read = read(fd, buffer, sizeof(buffer))) > 0)
{
crc = crc16(buffer, bytes_read);
}
close(fd);
// 输出CRC16校验值
printf("CRC16 checksum: 0x%04X\n", crc);
return 0;
}
这个示例代码中的init_crc16_table函数用于生成CRC16的查找表，而crc16函数则利用该表计算输入数据的CRC16校验值。在主函数main中，程序会读取文件的内容并调用crc16函数计算CRC16校验值，最后输出该值。
2.3 文件校验-CRC32
下面是一个使用CRC32算法计算文件校验和的C语言代码示例。这里使用的是IEEE 802.3标准的多项式（0x04C11DB7），这是最常用的CRC32实现。
#include <stdio.h>
#include <stdint.h>
#include <fcntl.h>
#include <unistd.h>
// CRC32 IEEE 802.3生成多项式
#define POLYNOMIAL 0xEDB88320
// 初始化CRC32查找表
uint32_t crc32_table[256];
void init_crc32_table(void)
{
uint32_t crc, poly;
uint8_t i, j;
for (i = 0; i < 256; i++)
{
crc = i;
for (j = 8; j; j--)
{
if (crc & 0x00000001)
crc = (crc >> 1) ^ POLYNOMIAL;
else
crc >>= 1;
}
crc32_table[i] = crc;
}
}
uint32_t crc32(const void *data, size_t len)
{
const uint8_t *byte = data;
uint32_t crc = 0xFFFFFFFF;
while (len--)
{
crc = (crc >> 8) ^ crc32_table[(crc ^ *byte++) & 0xFF];
}
return crc ^ 0xFFFFFFFF;
}
int main(int argc, char *argv[])
{
int fd;
uint8_t buffer[4096];
size_t bytes_read;
uint32_t crc;
if (argc != 2)
{
fprintf(stderr, "Usage: %s filename\n", argv[0]);
return 1;
}
// 初始化CRC32查找表
init_crc32_table();
// 打开文件
fd = open(argv[1], O_RDONLY);
if (fd == -1)
{
perror("Error opening file");
return 1;
}
// 读取文件并计算CRC32校验值
crc = 0xFFFFFFFF;
while ((bytes_read = read(fd, buffer, sizeof(buffer))) > 0)
{
crc = crc32(buffer, bytes_read);
}
close(fd);
// 输出CRC32校验值
printf("CRC32 checksum: 0x%08X\n", crc);
return 0;
}
在这个示例中，init_crc32_table函数初始化了CRC32的查找表，crc32函数用于计算输入数据的CRC32校验值。主函数main负责读取文件内容并调用crc32函数计算CRC32校验值，最后输出该值。
注意，在CRC32计算结束时，通常需要对CRC值进行反转（XOR 0xFFFFFFFF），这是为了与大多数CRC32实现保持一致。
- 点赞
- 收藏
- 关注作者
评论（0）