c 语言 crc32校验算法,如何计算CRC32校验和?
CRC32的多项式为:
十
32
26
+十
23
+十
22
+十
16
+十
12
11
+十
10
8
7
5
+十
4
2
或十六进制和二进制:
0x 01 04 C1 1D B7
1万0100 1100 0001 0001 1101 1011 0111
最高项(x
32
)通常不是显式编写的,因此它可以用十六进制表示,就像
你可以随意数数1和0,但是你会发现它们与多项式匹配,其中
1
是位0(或第一位)并且
x
你可以把CRC-32看作一系列“无进位的二进制算术”,或者基本上是“异或和移位运算”。这在技术上称为多项式算法。
为了更好地理解它,想想这个乘法:
(x^3 + x^2 + x^0)(x^3 + x^1 + x^0)
= (x^6 + x^4 + x^3
+ x^5 + x^3 + x^2
+ x^3 + x^1 + x^0)
= x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0
x^7 + x^3 + x^2 + x^1 + x^0
为什么?因为3x^3是11x^11(但我们只需要1个或0个前数字),所以我们继续:
=1x^110 + 1x^101 + 1x^100 + 11x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^101 + 1x^100 + 1x^100 + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^101 + 1x^101 + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^110 + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^111 + 1x^11 + 1x^10 + 1x^1 + x^0
=( 1x^110 + 1x^101 + 1x^100 + 11x^11 + 1x^10 + 1x^1 + x^0 ) MOD 2
=( 1x^110 + 1x^101 + 1x^100 + 1x^11 + 1x^10 + 1x^1 + x^0 )
= x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0 (or that original number we had)
我知道这是一个信念的飞跃,但这超出了我作为一个线程序员的能力。如果你是一个核心的CS学生或工程师,我挑战打破这一点。每个人都会从中受益。
因此,我们要举一个完整的例子:
Original message : 1101011011
Polynomial of (W)idth 4 : 10011
Message after appending W zeros : 11010110110000
现在我们使用CRC算法将扩增后的消息除以多边形。这和以前一样:
1100001010 = Quotient (nobody cares about the quotient)
_______________
10011 ) 11010110110000 = Augmented message (1101011011 + 0000)
=Poly 10011,,.,,….
-——,,.,,….
10011,.,,….
10011,.,,….
-——,.,,….
00001.,,….
00000.,,….
-——.,,….
00010,,….
00000,,….
-——,,….
00101,….
00000,….
-——,….
01011….
00000….
-——….
10110…
10011…
-——…
01010..
00000..
-——..
10100.
10011.
-——.
01110
00000
-——
1110 = Remainder = THE CHECKSUM!!!!
除法产生一个商,我们扔掉它,和一个余数,这是计算出的校验和。这就结束了计算。通常,校验和随后被附加到消息中,并传输结果。在这种情况下,传输将是:11010110111110。
普通人评价:
QUOTIENT
-————-
DIVISOR ) DIVIDEND
= REMAINDER
取前32位。
移位位
如果32位小于除数,则转到步骤2。
异或32位除数。转到步骤2。
(请注意,流必须可以被32位分割,否则应该进行填充。例如,必须填充8位ANSI流。也在分水岭的尽头停住了。)
桃扇骨
小鱼儿
红太狼
Bertha 。
港控/mmm°
刺骨的言语ヽ痛彻心扉
还没有评论，来说两句吧...