CRC校验算法详解、C语言实现

一、前言

1.1 CRC算法介绍

CRC（Cyclic Redundancy Check）校验算法是一种广泛应用于数据通信和存储系统中的错误检测方法，主要用于检测数据在传输过程中是否发生了改变。CRC算法通过计算一个固定长度的校验码，将该校验码附加到原始数据的末尾，接收方在接收到数据后重新计算校验码并与接收到的校验码进行比较，以此判断数据在传输过程中是否发生了错误。这种校验机制不仅能够检测出大多数类型的错误，而且计算效率高，占用资源少，因此在各种通信协议、文件系统、磁盘驱动器和网络协议中都有广泛应用。

CRC算法的原理基于多项式除法。在CRC校验中，数据被视为一个系数为0或1的多项式序列，而CRC校验码则是通过使用一个预定义的生成多项式对该数据多项式进行模2除法运算得到的。生成多项式的选择对CRC算法的错误检测能力有重要影响，通常选取的生成多项式能够检测出尽可能多类型的错误。在计算CRC校验码时，原始数据与生成多项式的模2除法的结果被附加到数据的末尾，形成一个完整的数据包。在接收端，同样使用生成多项式对数据包进行模2除法，如果余数为零，则认为数据在传输过程中未发生错误。

image-20240715160811534

CRC算法的具体实现过程如下：

  1. 将待发送的数据视为一个二进制多项式D(x)，其中每一位代表一个系数。
  2. 选取一个生成多项式G(x)，该多项式的长度决定了CRC校验码的长度。
  3. 对D(x)乘以x^n（n为生成多项式的长度减1），形成一个与G(x)同阶的多项式。
  4. 使用生成多项式G(x)对该扩展后的多项式进行模2除法，得到的余数即为CRC校验码。
  5. 将CRC校验码附加到原始数据的末尾，形成完整的数据包。
  6. 在接收端，对数据包再次进行相同的模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 tablefor (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 datawhile (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校验算法分类的情况：

  1. CRC8：

    • CRC8生成的校验码长度为8位（1字节）。它通常用于小数据量的校验，比如在一些简单的通信协议中，或者是对字节级数据进行校验。
    • 由于校验码长度较短，CRC8的冲突概率较高，但是计算速度非常快。

  2. CRC16：

    • CRC16生成的校验码长度为16位（2字节）。它适用于中等大小的数据块校验，例如在串行通信中或者对短消息进行校验。
    • CRC16的冲突概率比CRC8低，但仍然存在一定的可能性，尤其是在校验较长的数据流时。

  3. 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校验值时，查找表可以显著减少计算量。

查找表的工作原理：

  1. 预计算：
    在CRC算法的初始化阶段，程序会预先计算出所有可能的8位（或其他位数，取决于查找表的设计）输入与生成多项式进行模2除法的结果，并将这些结果存储在一个数组中。这个数组的大小通常是256个元素，每个元素对应一个8位输入的CRC校验值。

  2. 快速计算：
    当实际计算数据的CRC校验值时，算法会对数据进行逐字节处理。对于每个字节，算法会在查找表中查找对应的CRC值，然后与之前计算得到的部分CRC值进行异或操作。这个过程会重复直到所有的数据字节都被处理完毕。

  3. 最终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;elsecrc <<= 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;elsecrc >>= 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;elsecrc >>= 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实现保持一致。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/400239.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Linux：进程

Linux：进程

先了解一下这篇的基础知识 操作系统简述-CSDN博客还有这篇 ok我们来说进程 进程是什么&#xff1f; 在Windows下我们按下EscCtrlShift召唤任务管理器&#xff0c;查看Windows下的进程 我们的进程也是由操作系统管理的&#xff0c;操作系统对进程的管理也是先描述再组织。 …
阅读更多...
Docker Hub 镜像代理加速

Docker Hub 镜像代理加速

因为未知原因&#xff0c;docker hub 已经不能正常拉取镜像&#xff0c;可以使用以下代理服务来进行&#xff1a; "https://docker.m.daocloud.io", "https://noohub.ru", "https://huecker.io", "https://dockerhub.timeweb.cloud"…
阅读更多...
更深层的理解视觉Transformer， 对视觉Transformer的剖析

更深层的理解视觉Transformer， 对视觉Transformer的剖析

写在前面&&笔者的个人理解 目前基于Transformer结构的算法模型已经在计算机视觉&#xff08;CV&#xff09;领域展现出了巨大的影响力。他们在很多基础的计算机视觉任务上都超过了之前的卷积神经网络&#xff08;CNN&#xff09;算法模型&#xff0c;下面是笔者找到的…
阅读更多...
无字母绕过webshell

无字母绕过webshell

目录 代码 payload构造 php7 php5 构造payload 代码 不可以使用大小写字母、数字和$然后实现eval的注入执行 <?php if(isset($_GET[code])){$code $_GET[code];if(strlen($code)>35){die("Long.");}if(preg_match("/[A-Za-z0-9_$]/",$code))…
阅读更多...
JavaEE 的入门

JavaEE 的入门

1. 学习JavaEE Java EE(Java Platform Enterprise Edition), Java 平台企业版. 是JavaSE的扩展, ⽤于解决企业级的开 发需求, 所以也可以称之为是⼀组⽤于企业开发的Java技术标准. 所以, 学习JavaEE主要是学习Java在 企业中如何应⽤. 前⾯学习的是Java基础, JavaEE 主要学习Jav…
阅读更多...
easyExcel2.1.6自动trim()的问题

easyExcel2.1.6自动trim()的问题

环境&#xff1a;easyExcel 2.1.6 问题&#xff1a;easyExcel会自动忽略String中的空格&#xff0c;调用trim()函数&#xff0c;导致excel中的空格失效。 代码如上所示&#xff0c;所以只需要把globalConfiguration的autoTrim()&#xff0c;设置为false即可 那么怎么设置confi…
阅读更多...
【区块链+金融服务】河北股权交易所综合金融服务平台 | FISCO BCOS应用案例

【区块链+金融服务】河北股权交易所综合金融服务平台 | FISCO BCOS应用案例

区域性股权市场是我国资本市场的重要组成部分&#xff0c;是多层次资本市场体系的基石。河北股权交易所&#xff08;简称&#xff1a;河交所&#xff09; 作为河北省唯一一家区域性股权市场运营机构&#xff0c;打造河北股权交易所综合金融服务平台&#xff0c;将区块链技术与区…
阅读更多...
Linux centos stream 9命令及源码

Linux centos stream 9命令及源码

学过linux操作系统的人，对文件、命令比较熟悉。最多的操作是用命令处理文件。 随着学习的深入，会提出疑问:命令长什么样？ 出于好奇，会找到命令存放的地方，用cat命令看一下，结果可想而知。 我们知道，命令分内部命令和外部命令，存放在不同的位置。外部命令就是一个可执…
阅读更多...
OpenAI API error: “Unrecognized request argument supplied“

OpenAI API error: “Unrecognized request argument supplied“

题意&#xff1a;OpenAI API 错误&#xff1a;‘提供了无法识别的请求参数’ 问题背景&#xff1a; Im receiving an error when calling the OpenAI API. Its not recognizing file argument, which I submitted to the API. 我在调用 OpenAI API 时遇到错误。API 不识别我提…
阅读更多...
HikariCP连接池：Possibly consider using a shorter maxLifetime value.

HikariCP连接池：Possibly consider using a shorter maxLifetime value.

相关的SQL总结&#xff1a; session级别&#xff1a; show variables like %timeout%; mysql的global级别&#xff1a; show global variables like %timeout%; # 对应 mysql 修改配置&#xff08;单位 秒&#xff09; set global wait_timeout300; set global interacti…
阅读更多...
C++结构体指针强制转换以处理电力系统IEC103报文

C++结构体指针强制转换以处理电力系统IEC103报文

前言 最近依旧是开发规约解析工具的103篇&#xff0c;已经完成了通用分类服务部分的解析&#xff0c;现在着手开始搞扰动数据传输&#xff0c;也就是故障录波的传输。 在103故障录波&#xff08;扰动数据&#xff09;的报文中&#xff0c;数据是一个数据集一个数据集地存放&a…
阅读更多...
51单片机学习记录-数码管操作

51单片机学习记录-数码管操作

这里实现了静态数码管的显示。51单片机一共有可以显示4个数字&#xff0c;可以通过控制P2(4-2)的端口选择8个数字显示器中的一个显示数字&#xff0c;控制P0端口写入显示的数值信息。将操作的逻辑使用了函数Nixie进行了封装。 #include <8051.h>unsigned char NixieTabl…
阅读更多...
思科默认路由配置2

思科默认路由配置2

#路由协议实现# #任务二默认路由配置2# #1配置计算机的IP地址、子网掩码和网关 #2配置Router-A的名称及其接口IP地址 Router(config)#hostname Router-A Router-A(config)#int g0/0 Router-A(config-if)#ip add 192.168.1.1 255.255.255.0 Router-A(config-if)#no shutdow…
阅读更多...
Selenium + Python 自动化测试07（滑块的操作方法）

Selenium + Python 自动化测试07（滑块的操作方法）

我们的目标是&#xff1a;按照这一套资料学习下来&#xff0c;大家可以独立完成自动化测试的任务。 本篇文章主要讲述如何操作滑块。 目前很多系统登录或者注册的页面都有滑块相关的验证&#xff0c;selenium 中对滑块的基本操作采用了元素的拖曳的方式。需要用到Actiochains模…
阅读更多...
应用兼容性问题-abi动态库错误分析和解决

应用兼容性问题-abi动态库错误分析和解决

1&#xff0c;应用名和现象 运行环境&#xff1a; 云手机 现象&#xff1a; 2&#xff0c;分析 --------- beginning of crash 08-14 03:59:59.014 28740 28740 E AndroidRuntime: FATAL EXCEPTION: main 08-14 03:59:59.014 28740 28740 E AndroidRuntime: Process: com.ks…
阅读更多...
大型、复杂、逼真的安全服和安全帽检测：数据集和方法

大型、复杂、逼真的安全服和安全帽检测：数据集和方法

智能升级工地安全&#xff1a;SFCHD数据集与SCALE模块介绍 在人工智能&#xff08;AI&#xff09;技术飞速发展的今天&#xff0c;其在建筑工地安全领域的应用正逐渐展现出巨大潜力。尤其是高风险行业如化工厂的施工现场&#xff0c;对工人的保护措施要求极为严格。个人防护装…
阅读更多...
十四、迭代器模式

十四、迭代器模式

文章目录 1 基本介绍2 案例2.1 Aggregate 接口2.2 Iterator 接口2.3 MyArray 类2.4 MyArrayIterator 类2.5 Client 类2.6 Client 类的运行结果2.7 总结 3 各角色之间的关系3.1 角色3.1.1 Aggregate ( 集合 )3.1.2 Iterator ( 迭代器 )3.1.3 ConcreteAggregate ( 具体的集合 )3.…
阅读更多...
Luminar Neo for Mac/Win：创新AI图像编辑软件的强大功能

Luminar Neo for Mac/Win：创新AI图像编辑软件的强大功能

Luminar Neo&#xff0c;这款由Skylum公司倾力打造的图像编辑软件&#xff0c;为Mac和Windows用户带来了前所未有的创作体验与编辑便利。作为一款融合了先进AI技术的图像处理工具&#xff0c;Luminar Neo以其独特的功能和高效的操作流程&#xff0c;成为了摄影师、设计师及摄影…
阅读更多...
TPshop商城的保姆教程（Ubuntu）

TPshop商城的保姆教程（Ubuntu）

1.上传TPSHOP源码 选择适合自己的版本下载 TPshop商城源文件下载链接&#xff1a; 百度网盘 请输入提取码 上传tpshop的源码包到特定目录/var/www/html 切换到/var/www/html 目录下 cd /var/www/html修改HTML目录下所有文件权限 chmod -R 777 * 2.打开网址配置 TPshop安…
阅读更多...
第九届“创客中国”武汉区域赛正式启幕 灵途科技勇夺前三，晋级决赛！

第九届“创客中国”武汉区域赛正式启幕 灵途科技勇夺前三，晋级决赛！

8月8日&#xff0c;第九届“创客中国”武汉区域赛正式启幕&#xff0c;首场聚焦先进制造领域。灵途科技勇夺先进制造领域专场企业组前三名&#xff0c;成功晋级决赛。 “创客中国”大赛是工业和信息化部组织开展的双创赛事活动&#xff0c;以构建产业链协同发展为出发点&#…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023