Skip to content

Latest commit

 

History

History
169 lines (151 loc) · 8.37 KB

200803311316.txt.md

File metadata and controls

169 lines (151 loc) · 8.37 KB
Raw

标题: 手工计算"1314"的CRC32

http://scz.617.cn/misc/200803311316.txt

2005-06-01 17:32 scz

CRC32 "1314"

Plain : 31 33 31 34 CRC32 : 0xA817E816

CRC32.c算出来的CRC32值与很多现成工具算出来的相一致。试图手工进行多项式长除 法得到这个结果，但总是得不到。很想知道如何通过多项式长除法得到结果，就算是 涉及一些二进制位的反序处理，也给我一个针对"\x31\x33\x31\x34"的手工计算例子 吧。可惜天下文章一大抄，没找到可答疑解惑的文章。

2008-03-31 10:23 tnttools@pediy

tnttools@pediy给出了最终手工运算过程，他是唯一一个正面解答了我的困惑的人， 十分感谢。

[PKZIP, AUTODIN II, Ethernet, FDDI]

Width : 32 Poly : 04C11DB7 : 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 + x^0 : (32,26,23,22,16,12,11,10,8,7,5,4,2,1,0) Init : FFFFFFFF RefIn : True RefOut : True XorOut : FFFFFFFF

(Poly:04C11DB7)
    |
    v

0000 0100 1100 0001 0001 1101 1011 0111 | (给出Poly时，一般省略了最高位的1，实际运算时要补上) | v 1 0000 0100 1100 0001 0001 1101 1011 0111 | v (这就是除数)

"\x31\x33\x31\x34" (原始数据) | (展开成二进制表示) | v 0011 0001 0011 0011 0011 0001 0011 0100 | (RefIn:True) | v 1000 1100 1100 1100 1000 1100 0010 1100 | (Init:FFFFFFFF) | v 1000 1100 1100 1100 1000 1100 0010 1100 1111 1111 1111 1111 1111 1111 1111 1111 +(模2加法，非进位算术加法，就是异或)

0111 0011 0011 0011 0111 0011 1101 0011 (由于是与全1异或，实际就相当于取反) | (在尾部添加0，0的个数比除数的2进制位数少1，就本例而言，添加32个0) | v 0111 0011 0011 0011 0111 0011 1101 0011 0000 0000 0000 0000 0000 0000 0000 0000 | v (这就是被除数)

进行多项式长除法运算:

                                                                1110010110111011010101100101110(我们不关心商)
                              +----------------------------------------------------------------

100000100110000010001110110110111 ) 111001100110011011100111101001100000000000000000000000000000000 100000100110000010001110110110111 --------------------------------- 110010000000110011010010111110110 100000100110000010001110110110111 --------------------------------- 100101001101100010111000010000010 100000100110000010001110110110111 --------------------------------- 101101011100000110110100110101000 100000100110000010001110110110111 --------------------------------- 110111101000010011101000001111100 100000100110000010001110110110111 --------------------------------- 101110011100100011001101110010110 100000100110000010001110110110111 --------------------------------- 111011101010000100001100010000100 100000100110000010001110110110111 --------------------------------- 110110011000001100000101001100110 100000100110000010001110110110111 --------------------------------- 101101111100011100010111110100010 100000100110000010001110110110111 --------------------------------- 110101101001111001100100001010100 100000100110000010001110110110111 --------------------------------- 101010011111110111010101111000110 100000100110000010001110110110111 --------------------------------- 101011100111010101101100111000100 100000100110000010001110110110111 --------------------------------- 101100000101011110001000111001100 100000100110000010001110110110111 --------------------------------- 110010001101110000011000111101100 100000100110000010001110110110111 --------------------------------- 100101010111100100101100010110110 100000100110000010001110110110111 --------------------------------- 101110001100110100010100000001000 100000100110000010001110110110111 --------------------------------- 111010101011011001101011011111100 100000100110000010001110110110111 --------------------------------- 110100011010110111001011010010110 100000100110000010001110110110111 --------------------------------- 101001111001101010001011001000010 100000100110000010001110110110111 --------------------------------- 10010111111010000001011111101010(余数)

1001 0111 1110 1000 0001 0111 1110 1010 (余数) | (RefOut:True) | v 0101 0111 1110 1000 0001 0111 1110 1001 | (XorOut:FFFFFFFF) | v 0101 0111 1110 1000 0001 0111 1110 1001 1111 1111 1111 1111 1111 1111 1111 1111 +(模2加法，非进位算术加法，就是异或)

1010 1000 0001 0111 1110 1000 0001 0110 (由于是与全1异或，实际就相当于取反) | v 0xA817E816 (最终结果)

我当时手工计算失败的原因在于没有针对下列参数进行相应处理，只是简单地进行多 项式长除法运算:

Init : FFFFFFFF RefIn : True RefOut : True XorOut : FFFFFFFF

再次感谢tnttools@pediy的手工运算过程。顺便以他的原话结尾:

献给那些永远充满着好奇心的人们