如何手工计算0x31333134的CRC-32值?
献给那些永远充满着好奇心的人们
有些答案永远在二进制洪流中飘[前言]
这几天,分析某软件算法时,涉及到CRC。在重拾记忆碎片时,发现有网友提出一个问题:如何手工计算0x31333134的CRC-32值。我乐于接受这个挑战。因为此任务可以强化我的记忆。(虽然已经我的大脑证明,2年前写的东西我已经可以全部忘光。但愿这次,我可以记得更久一些。)
[过程]
CRC-32标准有着各种各样的变形,下面的参数集定义的是最常见的一个,也是本文中采用的CRC-32算法。
―――――――――――――――――― [Ross93]
Name : "CRC-32"
Width : 32
Poly(Reverse) : 04C11DB7( EDB88320 )
Init : FFFFFFFF
RefIn : True
RefOut : True
XorOut : FFFFFFFF
Check : CBF43926
――――――――――――――――――
[预备知识1]
最常见的一种解决方案
little-endian CPU
------------
每一个字节内,相对低位的比特位是多项式中的相对高位的系数;
每一个机器字内,相对低位的字节是多项式中的相对高位的系数。
------------
big-endian
------------这样来表述:
每一个字节内,相对低位的比特位是多项式中的相对高位的系数;
每一个机器字内,相对高位的字节是多项式中的相对高位的系数。
------------
每一次模2除法的被除数:上一次模2除法的余数+上一次未参与运算的被除数的低位
模2除法的余数总比除数少1位。
polynormical arithmetics多项式运算,特指没有进位的多项式加法和乘法、没有借位的多项式减法和除法。
模n多项式运算:对运算结果的各项系数进行模n运算,运算过程中各项系数的加减执行模n加、模n减。
Step I. 被除数是什么? 0010 1100 1000 1100 1100 1100 1000 1100 … …
+ 1111 1111 1111 1111 1111 1111 1111 1111 … …
=
1101 0011 0111 0011 0011 0011 0111 0011 … …(这就是被除数)
注I. … …表示跟在后面的无穷字节
0x31333134在CRC, Little-endian的语境中,要表示成多项式的话,应该所有n比特位与所有的32-n比特位互调位置,结果如下
3 1 3 3 3 1 3 4
0011 0001 0011 0011 0011 0001 0011 0100
->
0010 1100 1000 1100 1100 1100 1000 1100
Init 值为FFFFFFFF,它表示上一次高位的模2除法运算的余数,理所当然要加到本次除法中。
Step II. 除数是什么?1 0000 0100 1100 0001 0001 1101 1011 0111(这就是除数)
因为Poly(Reverse)的值为04C11DB7( EDB88320 ),表示成二进制数就是
0000 0100 1100 0001 0001 1101 1011 0111
在说明除数Poly时,一般省略了最高位32位的比特1。
所以,别忘了最高位32位的1,它保证了CRC-32的结果值为32位,...
Step III. 计算
记住,是无进位的多项式模2除法
被除数(后面的32个比特零仅仅是余数的占位符)
1101001101110011001100110111001100000000000000000000000000000000 … …
除数
100000100110000010001110110110111
过程-> 商,余数
-> 1,
101000100010011101111011010100010000000000000000000000000000000
-> 11,
01000000100011111110101100010101000000000000000000000000000000
-> 1101,
000001101111111010110001111000110000000000000000000000000000
-> 1101000001,
101110110110110101100101011101110000000000000000000000
-> 11010000011,
01110010000110111101011101011001000000000000000000000
-> 1101000001101
110011001010111001000000110100110000000000000000000
-> 11010000011011
10011101100111011001110000010001000000000000000000
-> 110100000110111
0011111111111010001001011001010100000000000000000
-> 110100000110111001
1111101100010000001100010001111100000000000000
-> 1101000001101110011
111100101110000101111111100010010000000000000
-> 11010000011011100111
11100001000000111110001010100101000000000000
-> 110100000110111001111
1100011011000110110110001111110100000000000
-> 1101000001101110011111
100010010100110010101100010011010000000000
-> 11010000011011100111111
00010110010110000100010100101101000000000
-> 110100000110111001111110001
0110000101000101010011110110011100000
-> 11010000011011100111111000101
10000001110101000010000000101011000
-> 110100000110111001111110001011
0000011101101001010111011110000100
-> 11010000011011100111111000101100
00011101101001010111011110000100
因为人工计算和机器计算的差异,结果要反序存放
00100001111011101010010110111000
最后还要与0xFFFFFFFF值异或(XorOut : FFFFFFFF)
1101 1110 0001 0001 0101 1010 0100 0111
所以最后的结果是:
DE115A47
[致谢]
Ross, [Ross93] PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS
My Family, though you all will never have interest in taking a look of this shit.
[补充]如何手工计算0x31 0x33 0x31 0x34的CRC-32值?
ASCII C型字符串”1314”用十六进制数表示是0x31 0x33 0x31 0x34 0x00
ASCII C型字符串”4131”用十六进制数表示是0x34 0x31 0x33 0x31 0x00
我在上文中计算的是”4131”的CRC-32值,现在计算”1314”的CRC-32值。
在这里,要注意,对于字符串"1314"和数据流0x31 0x33 0x31 0x34 0x00的计算结果是不同的。对于针对字符串的算法,当遇到0x00时便停止计算;对于针对数据流的算法,0x00要继续参与计算。对于针对字符串的算法,是把NULL字符作为停止计算的条件;对于针对数据流的算法,是把到达整个数据流的长度作为停止计算的条件。
Step I. 被除数
1000 1100 1100 1100 1000 1100 0010 1100
+ 1111 1111 1111 1111 1111 1111 1111 1111 … …
=
+ 0111 0011 0011 0011 0111 0011 1101 0011 (被除数)
Step II. 除数
1 0000 0100 1100 0001 0001 1101 1011 0111(这就是除数)
Step III. 计算
被除数(后面的32个比特零是余数的占位符)
0111001100110011011100111101001100000000000000000000000000000000 … …
除数
100000100110000010001110110110111
-> 商,余数
-> 01,
11001000000011001101001011111011000000000000000000000000000000
-> 011
1001010011011000101110000100000100000000000000000000000000000
-> 0111
001011010111000001101101001101010000000000000000000000000000
-> 0111001
011011110100001001110100000111110000000000000000000000000
-> 011100101
1011100111001000110011011100101100000000000000000000000
-> 0111001011
011101110101000010000110001000010000000000000000000000
-> 011100101101
1101100110000011000001010011001100000000000000000000
-> 0111001011011
101101111100011100010111110100010000000000000000000
-> 01110010110111
01101011010011110011001000010101000000000000000000
-> 0111001011011101
101010011111110111010101111000110000000000000000
-> 01110010110111011
01010111001110101011011001110001000000000000000
-> 0111001011011101101
010110000010101111000100011100110000000000000
-> 011100101101110110101
0110010001101110000011000111101100000000000
-> 01110010110111011010101
10010101011110010010110001011011000000000
-> 011100101101110110101011
0010111000110011010001010000000100000000
-> 011100101101110110101011001
0111010101011011001101011011111100000
-> 01110010110111011010101100101
11010001101011011100101101001011000
-> 011100101101110110101011001011
1010011110011010100010110010000100
-> 0111001011011101101010110010111
010010111111010000001011111101010
-> 01110010110111011010101100101110
10010111111010000001011111101010
结果倒序存放
01010111111010000001011111101001
与0xFFFFFFFF异或
10101000000101111110100000010110
转换成十六进制数,为
A817E816
TnTTools
The ART of Reverse Engineering
Enjoy it.
[培训]《安卓高级研修班(网课)》月薪三万计划