CRC32的原理介绍以及查表法实现和多项式相除实现

2024-01-07 10:28

本文主要是介绍CRC32的原理介绍以及查表法实现和多项式相除实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1、CRC32的生成多项式

G\left ( x \right )=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}+1

 多项式系数提取出来,改写位16进制数为:0x104C11DB7,如果转换为33个二进制数[1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1,
       1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1] ,那么从左到右对应于生成多项式的每个项目的系数(0或1)。

2  CRC32校验码的生成:

    如果待校验的数据写成多项式的形式,也就是把数据先转换为二进制的数,然后每个二进制数对应一个多项式的一个系数;比如待校验的数据是0x85,那么对应二进制[1000 0101],对应多项式:X^{7}+X^{2}+1,把这个多项式再乘以X^{32},然后再除以G(x),最终的余数就是CRC校验码,也就是(X^{7}+X^{2}+1)*X^{32}/G(x)的余数。

3 CRC32校验码完整流程介绍:

  1. Invert bits on each byte,如果输入是多个字节的数据,每个字节的对应二进制数字要逆序排列,字节之间还是保持输入顺序;
  2. 经过上面处理的数据,需要在末尾增加0x00000000四个字节;相当于给输入数据的多项式乘以X^{32}
  3. xor first four bytes with 0xFF (this is to avoid errors on the leading 0s),经过上面步骤处理后输入数据的前四个字节要和0xFFFFFFFF异或。如果输入数据不足4个字节,也没关系,因为步骤2末尾增加0x00000000四个字节,总长度是够4个字节的。
  4. Compute the reminder ,上面步骤生成的数据对应的多项式除以生成多项式G(x)后的余数
  5. Reverse the bits again,余数是4个字节,这4个字节对应的二进制数字要按一个整体逆序排列。
  6. xor the result again. 逆序后的4个字节再和0xFFFFFFFF异或,得到最终的CRC校验值。

上面步骤中,输入数据的逆序,余数的逆序,输入数据和0xFFFFFFFF的异或,以及余数和0xFFFFFFFF的异或,都是可选步骤,根据不同的应用,可能会有不同的选择。

CRC(循环冗余校验)在线计算_ip33.com

4 举例:

calculate the CRC-32 hash for the 'ANSI' string 'abc':inputs:
dividend: binary for 'abc': 0b011000010110001001100011 = 0x616263
polynomial: 0b100000100110000010001110110110111 = 0x104C11DB7start with the 3 bytes 'abc':
61 62 63 (as hex)
01100001 01100010 01100011 (as bin)reverse the bits in each byte:
10000110 01000110 11000110append 32 0 bits:
10000110010001101100011000000000000000000000000000000000XOR (exclusive or) the first 4 bytes with 0xFFFFFFFF:
(i.e. flip the first 32 bits:)
01111001101110010011100111111111000000000000000000000000next we will perform 'CRC division':a simple description of 'CRC division':
we put a 33-bit box around the start of a binary number,
start of process:
if the first bit is 1, we XOR the number with the polynomial,
if the first bit is 0, we do nothing,
we then move the 33-bit box right by 1 bit,
if we have reached the end of the number,
then the 33-bit box contains the 'remainder',
otherwise we go back to 'start of process'note: every time we perform a XOR, the number begins with a 1 bit,
and the polynomial always begins with a 1 bit,
1 XORed with 1 gives 0, so the resulting number will always begin with a 0 bit'CRC division':
'divide' by the polynomial 0x104C11DB7:
01111001101110010011100111111111000000000000000000000000100000100110000010001110110110111---------------------------------111000100010010111111010010010110100000100110000010001110110110111---------------------------------110000001000101011101001001000010100000100110000010001110110110111---------------------------------100001011101010011001111111101010100000100110000010001110110110111---------------------------------111101101000100000100101110100000100000100110000010001110110110111---------------------------------111010011101000101010110000101110100000100110000010001110110110111---------------------------------110101110110001110110001100110010100000100110000010001110110110111---------------------------------101010100000011001111110100001010100000100110000010001110110110111---------------------------------101000011001101111000001011110100100000100110000010001110110110111---------------------------------100011111110110100111110100001100100000100110000010001110110110111---------------------------------110110001101101100000101110110000100000100110000010001110110110111---------------------------------101101010111011100010110000001110100000100110000010001110110110111---------------------------------110111000101111001100011011100100100000100110000010001110110110111---------------------------------10111100011111011101101101010011we obtain the 32-bit remainder:
0b10111100011111011101101101010011 = 0xBC7DDB53note: the remainder is a 32-bit number, it may start with a 1 bit or a 0 bitXOR the remainder with 0xFFFFFFFF:
(i.e. flip the 32 bits:)
0b01000011100000100010010010101100 = 0x438224ACreverse bits:
bit-reverse the 4 bytes (32 bits), treating them as one entity:
(e.g. 'abcdefgh ijklmnop qrstuvwx yzABCDEF'
to 'FEDCBAzy xwvutsrq ponmlkji hgfedcba':)
0b00110101001001000100000111000010 = 0x352441C2thus the CRC-32 hash for the 'ANSI' string 'abc' is: 0x352441C2

5 查表法计算原理:

  1.  输入数据是多个字节,可以按照逐个字节的方式去计算CRC检验值
  2. 首先要对0-255这256个数字,计算每个数字对应的CRC检验值,形成一个表格,可以用0-255来索引校验值
  3. 对于第一个输入字节,首先进行逆序,然后逆序后取值作为索引去查表,获得校验值,得到校验值是4个字节,那么按照多项式的除法步骤,校验值4个字节的开头一个字节需要和第二个输入字节(逆序处理后的)进行二进制加法,也就是异或,然后用这个异或后的值作为索引去查表,得到新的校验值,然后再和下一个字节进行相同的处理,以此类推,直至所有输入数据处理完。
  4. 最后得到的4个字节校验值,进行整体逆序,然后和0xFFFFFFFF异或,得到最终的CRC32校验值。

6  多项式相除方法和查表方法的python代码:

mport numpy as nphex_num = "104C11DB7" # 要转换的十六进制数字
binary_num = bin(int(hex_num, 16))[2:] # 将十六进制转换为十进制再转换为二进制
print("二进制结果:", binary_num)
crc32_gen = np.array(list(binary_num), dtype=int)
print(crc32_gen)# 使用np.pad()函数进行补零操作myCRC32Table = np.zeros(0,dtype=int)for j in range(256):Bytes = bin(j)[2:]Bytes_bin_array = np.array(list(Bytes), dtype=int)Padded_Bytes_bin_array = np.pad(Bytes_bin_array,(0, 32), mode='constant')#print("\n补零后的数组:\n", Padded_Bytes_bin_array)for i in range(len(Padded_Bytes_bin_array)-33+1) :tmp_value = Padded_Bytes_bin_array[i:i+33]#print(tmp_value)if tmp_value[0] ==0:continueelse:Padded_Bytes_bin_array[i:i+33] =  tmp_value ^   crc32_gen#print(Padded_Bytes_bin_array[i:i+33]) remaider_of_Padded_Bytes_bin_array = Padded_Bytes_bin_array[-32:]        CRC32_bytes = int(''.join(map(str, remaider_of_Padded_Bytes_bin_array)),2)       myCRC32Table = np.append(myCRC32Table,CRC32_bytes)#hex_num = "EDB883208" # 要转换的十六进制数字#################   下面是查表法方法计算CRC32 ===================================
Message1 ='0102'
Message1_bin = bin(int(Message1, 16))[2:].zfill(len(Message1)*4) # 将十六进制转换为十进制再转换为二进制
Message1_bin_array = np.array(list(Message1_bin), dtype=int)##reverse the bits in each byte:Message1_bin_array_reverse = np.zeros(0,dtype=int)
for i in range(int(np.size(Message1_bin_array)/8)) :tmp_flip = np.flipud(Message1_bin_array[i*8:i*8+8])tmp_flip_number = int(''.join(map(str, tmp_flip)),2)Message1_bin_array_reverse = np.append(Message1_bin_array_reverse,tmp_flip_number)# 按照字节查询CRC32 table,前一个字节的CRC查表值的前8位需要和下个字节进行异或操作,算出来的新值作为新的查表索引值;每次查出的CRC值还需要和上一次查出的CRC值的高24位异或操作
crc32_result = 0
for i in range(int(np.size(Message1_bin_array_reverse))) :    if i < 4:Message1_bin_array_reverse[i] =Message1_bin_array_reverse[i] ^ 0xFFcrc32_result =myCRC32Table[(crc32_result >> 24) ^ Message1_bin_array_reverse[i]] ^ (crc32_result & 0x00FFFFFF)<<8   #### 如果输入数据小于4个字节,需要对FFFFFFFF剩余的FF特别处理下,比如原始输入数据1个字节,那么有3个0xFF没有在上面的代码中用到,所以要在下面的代码中异或上这三个FF
if int(np.size(Message1_bin_array_reverse)) < 4:if 4-int(np.size(Message1_bin_array_reverse))      ==1 :crc32_result = crc32_result ^ 0xFF000000if 4- int(np.size(Message1_bin_array_reverse))     ==2 :crc32_result = crc32_result ^ 0xFFFF0000                if 4- int(np.size(Message1_bin_array_reverse))     ==3 :crc32_result = crc32_result ^ 0xFFFFFF00# Reverse the result:
crc32_result_bin = bin(crc32_result)[2:].zfill(32)
crc32_result_array = np.array(list(crc32_result_bin), dtype=int)
crc32_result_reverse = np.flipud(crc32_result_array)
crc32_result_reverse = ''.join(map(str, crc32_result_reverse))
print('crc32_result_reverse =  ',hex(int(crc32_result_reverse,2)))crc32_result_reverse_complement  = int(crc32_result_reverse,2)^0xFFFFFFFF
print('crc32_result_reverse_complement',hex(crc32_result_reverse_complement))#################   下面是多项式相除方法计算CRC32 ===================================#Message ='8040C020'
Message ='0102'Message_bin = bin(int(Message, 16))[2:].zfill(len(Message)*4) # 将十六进制转换为十进制再转换为二进制
#Message_bin = '01111001101110010011100111111111000000000000000000000000'
Message_bin_array = np.array(list(Message_bin), dtype=int)############ Reverse input per byte
Message_bin_array_reverse = np.zeros(0,dtype=int)
for i in range(int(np.size(Message_bin_array)/8)) :tmp_flip = np.flipud(Message_bin_array[i*8:i*8+8])Message_bin_array_reverse = np.append(Message_bin_array_reverse,tmp_flip)outputXor = 'ffffffff'
outputXor_bin = bin(int(outputXor, 16))[2:]
outputXor_array = np.array(list(outputXor_bin), dtype=int)kk = len(Message)*4# 使用np.pad()函数进行补零操作
padded_message = np.pad(Message_bin_array_reverse,(0, 32), mode='constant')
print("\n补零后的数组:\n", padded_message)#padded_message = Message_bin_arraypadded_outputXor = np.pad(outputXor_array,(0, kk), mode='constant')#padded_message = padded_message^padded_outputXorfor i in range(len(padded_message)-33+1) :tmp_value = padded_message[i:i+33]print(tmp_value)if tmp_value[0] ==0:continueelse:padded_message[i:i+33] =  tmp_value ^ crc32_genprint(padded_message[i:i+33]) remaider_of_padded_message = padded_message[-32:]CRC32 = ''.join(map(str, remaider_of_padded_message))
print('remaider_of_padded_message = ',hex(int(CRC32,2)))remaider_of_padded_message_reverse = np.flipud(remaider_of_padded_message)
CRC32 = ''.join(map(str, remaider_of_padded_message_reverse))
print('remaider_of_padded_message_reverse = ',hex(int(CRC32,2)))for i in range(len(padded_outputXor)-33+1) :tmp_value = padded_outputXor[i:i+33]print(tmp_value)if tmp_value[0] ==0:continueelse:padded_outputXor[i:i+33] =  tmp_value ^   crc32_genprint(padded_outputXor[i:i+33]) 
remaider_of_padded_outputXor = padded_outputXor[-32:]
remaider_of_padded_outputXor_reverse = np.flipud(remaider_of_padded_outputXor)
CRC32 = ''.join(map(str, remaider_of_padded_outputXor_reverse))
print('remaider_of_padded_outputXor_reverse = ',hex(int(CRC32,2)))CRC32 = remaider_of_padded_message ^ remaider_of_padded_outputXor
CRC32_reverse = np.flipud(CRC32)print(CRC32)CRC32 = ''.join(map(str, CRC32))
print(hex(int(CRC32,2)))print(CRC32_reverse)CRC32_reverse = ''.join(map(str, CRC32_reverse))
print(hex(int(CRC32_reverse,2)))CRC32_reverse_complement  = int(CRC32_reverse,2)^0xFFFFFFFF
print('CRC32_reverse_complement=',hex(CRC32_reverse_complement))

 注意:WLAN的MAC帧的FCS是完整的CRC32校验

这篇关于CRC32的原理介绍以及查表法实现和多项式相除实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/579604

相关文章

性能测试介绍

性能测试是一种测试方法,旨在评估系统、应用程序或组件在现实场景中的性能表现和可靠性。它通常用于衡量系统在不同负载条件下的响应时间、吞吐量、资源利用率、稳定性和可扩展性等关键指标。 为什么要进行性能测试 通过性能测试,可以确定系统是否能够满足预期的性能要求,找出性能瓶颈和潜在的问题,并进行优化和调整。 发现性能瓶颈:性能测试可以帮助发现系统的性能瓶颈,即系统在高负载或高并发情况下可能出现的问题

水位雨量在线监测系统概述及应用介绍

在当今社会,随着科技的飞速发展,各种智能监测系统已成为保障公共安全、促进资源管理和环境保护的重要工具。其中,水位雨量在线监测系统作为自然灾害预警、水资源管理及水利工程运行的关键技术,其重要性不言而喻。 一、水位雨量在线监测系统的基本原理 水位雨量在线监测系统主要由数据采集单元、数据传输网络、数据处理中心及用户终端四大部分构成,形成了一个完整的闭环系统。 数据采集单元:这是系统的“眼睛”,

Hadoop数据压缩使用介绍

一、压缩原则 (1)运算密集型的Job,少用压缩 (2)IO密集型的Job,多用压缩 二、压缩算法比较 三、压缩位置选择 四、压缩参数配置 1)为了支持多种压缩/解压缩算法,Hadoop引入了编码/解码器 2)要在Hadoop中启用压缩,可以配置如下参数

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

深入探索协同过滤:从原理到推荐模块案例

文章目录 前言一、协同过滤1. 基于用户的协同过滤(UserCF)2. 基于物品的协同过滤(ItemCF)3. 相似度计算方法 二、相似度计算方法1. 欧氏距离2. 皮尔逊相关系数3. 杰卡德相似系数4. 余弦相似度 三、推荐模块案例1.基于文章的协同过滤推荐功能2.基于用户的协同过滤推荐功能 前言     在信息过载的时代,推荐系统成为连接用户与内容的桥梁。本文聚焦于

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

hdu4407(容斥原理)

题意:给一串数字1,2,......n,两个操作:1、修改第k个数字,2、查询区间[l,r]中与n互质的数之和。 解题思路:咱一看,像线段树,但是如果用线段树做,那么每个区间一定要记录所有的素因子,这样会超内存。然后我就做不来了。后来看了题解,原来是用容斥原理来做的。还记得这道题目吗?求区间[1,r]中与p互质的数的个数,如果不会的话就先去做那题吧。现在这题是求区间[l,r]中与n互质的数的和

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现,因为rasa本身是带有remindschedule模块的。不过经过一番折腾后,忽然发现,chatbot上实现的定时,语音助手不一定会有响应。因为,我目前语音助手的代码设置了长时间无应答会结束对话,这样一来,chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢? 我最后选择的方法是用threading.Time

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸(两张壁纸可不一致)

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸: 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  (注意不能是bmp格式) 替换默认锁屏壁纸: 将图片资源放入vendo