逆向工程中面对并理解编译器对除法的优化(2)

逆向工程中遭遇如下代码，输入short型变量xxx，经某种数学变换得到变量yyy:

00007FFFF3A7DE35 0F B7 B4 24 98 00 00 00    movzx   esi, [rsp+xxx]   ; Move with Zero-Extend
00007FFFF3A7DE3D B8 A7 C8 67 DD             mov     eax, 0DD67C8A7h
00007FFFF3A7DE42 F7 EE                      imul    esi              ; Signed Multiply
00007FFFF3A7DE44 89 F1                      mov     ecx, esi
00007FFFF3A7DE46 C1 F9 1F                   sar     ecx, 1Fh         ; Shift Arithmetic Right
00007FFFF3A7DE49 01 F2                      add     edx, esi         ; Add
00007FFFF3A7DE4B C1 FA 05                   sar     edx, 5           ; Shift Arithmetic Right
00007FFFF3A7DE4E 29 CA                      sub     edx, ecx         ; Integer Subtraction
00007FFFF3A7DE50 6B DA 25                   imul    ebx, edx, 25h    ; Signed Multiply
00007FFFF3A7DE53 F7 DB                      neg     ebx              ; Two's Complement Negation
00007FFFF3A7DE55 01 F3                      add     ebx, esi         ; Add
00007FFFF3A7DE57 48 63 CB                   movsxd  rcx, ebx         ; Move with Sign-Extend Doubleword
00007FFFF3A7DE5A 48 89 4C 24 48             mov     [rsp+yyy], rcx

这段代码的F5结果并不会提供更有价值的信息，比如我的Hex-Rays显示:

yyy = xxx - 0x25 * (((signed int)(xxx + (0xFFFFFFFFDD67C8A7LL * xxx >> 32)) >> 5) - ((signed int)xxx >> 31));

这个神鬼莫测的F5结果，还不如直接看汇编代码。

你猜，yyy的最简表达式是什么？是这个:

yyy = xxx % 0x25

即xxx模37。这事慢慢说，先提个小问题。如下”8字节宽”代码:

mov     esi, 0xffff
mov     eax, 0xdd67c8a7
imul    esi

imul之后edx等于多少？不许在调试器中实际执行。当时截图在微博上提这个问，渣浪进行图片OCR后不知识别出什么敏感词，然后限流了。要说是位数，可我写的不是”sixty four”啊，活久见。

很久没有折腾ASM编程，逆水行舟不进则退，最初误以为答案是0xdd66，因为:

0xdd67c8a7 * 0xffff = 0xdd66eb3f3759

但实际结果是:

(gdb) i r edx eax
edx            0xffffdd67       -8857
eax            0xeb3f3759       -348178599

后来bluerust、hume分别指出问题所在，imul是有符号相乘，此时0xdd67c8a7实际是个负数。在Python3中执行:

hex( 0x10000000000000000 - ( 0x100000000 - 0xdd67c8a7 ) * 0xffff )

得到:

0xffffdd67eb3f3759

这个64位数与edx:eax相符。再挖个imul的小坑，如下代码:

mov     esi, 0xffffffff
mov     eax, 0xdd67c8a7
imul    esi

imul之后edx等于多少？

(gdb) i r edx eax
edx            0x0      0
eax            0x22983759       580400985

在Python3中执行:

hex( ( 0x100000000 - 0xdd67c8a7 ) * ( 0x100000000 - 0xffffffff ) )

得到:

0x22983759

00007FFFF3A7DE35 0F B7 B4 24 98 00 00 00    movzx   esi, [rsp+xxx]   ; Move with Zero-Extend
00007FFFF3A7DE3D B8 A7 C8 67 DD             mov     eax, 0DD67C8A7h
00007FFFF3A7DE42 F7 EE                      imul    esi              ; Signed Multiply
00007FFFF3A7DE44 89 F1                      mov     ecx, esi
/*
 * 这是算术右移，不是逻辑右移。
 *
 * ecx由于源自short型变量，其结果恒为0。
 */
00007FFFF3A7DE46 C1 F9 1F                   sar     ecx, 1Fh         ; Shift Arithmetic Right
/*
 * edx = hex( ( 0xdd67c8a7 * xxx ) >> 0x20 )
 */
00007FFFF3A7DE49 01 F2                      add     edx, esi         ; Add
/*
 * 这是算术右移，不是逻辑右移。
 */
00007FFFF3A7DE4B C1 FA 05                   sar     edx, 5           ; Shift Arithmetic Right
/*
 * edx减0
 */
00007FFFF3A7DE4E 29 CA                      sub     edx, ecx         ; Integer Subtraction

相当于在Python3中执行:

hex( ( 0xdd67c8a7 * xxx ) >> 0x25 )

进一步等价于:

hex( xxx // 0x25 )

注意，”>> 0x25″与”// 0x25″中都出现了0x25，这只是巧合，不要瞎联想。

这两个Python3表达式为什么会等价？

将X除以37优化成乘法运算，其中一种方案如下:

mov ecx,X
mov eax,0DD67C8A7h
imul ecx
add edx,ecx
sar edx,05h
shr ecx,31
add edx,ecx
; quotient now in edx

之前写过一篇:

《逆向工程中面对并理解编译器对除法的优化》

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

推荐过一本书:

《Hacker’s Delight 2nd Edition》

有兴趣深究者可以看看，此处不展开。

00007FFFF3A7DE35 0F B7 B4 24 98 00 00 00    movzx   esi, [rsp+xxx]   ; Move with Zero-Extend
00007FFFF3A7DE3D B8 A7 C8 67 DD             mov     eax, 0DD67C8A7h
00007FFFF3A7DE42 F7 EE                      imul    esi              ; Signed Multiply
00007FFFF3A7DE44 89 F1                      mov     ecx, esi
/*
 * 这是算术右移，不是逻辑右移。
 *
 * ecx由于源自short型变量，其结果恒为0。
 */
00007FFFF3A7DE46 C1 F9 1F                   sar     ecx, 1Fh         ; Shift Arithmetic Right
/*
 * edx = hex( ( 0xdd67c8a7 * xxx ) >> 0x20 )
 */
00007FFFF3A7DE49 01 F2                      add     edx, esi         ; Add
/*
 * 这是算术右移，不是逻辑右移。
 */
00007FFFF3A7DE4B C1 FA 05                   sar     edx, 5           ; Shift Arithmetic Right
/*
 * edx减0
 */
00007FFFF3A7DE4E 29 CA                      sub     edx, ecx         ; Integer Subtraction
/*
 * 有符号相乘
 */
00007FFFF3A7DE50 6B DA 25                   imul    ebx, edx, 25h    ; Signed Multiply
/*
 * 求负
 */
00007FFFF3A7DE53 F7 DB                      neg     ebx              ; Two's Complement Negation
00007FFFF3A7DE55 01 F3                      add     ebx, esi         ; Add
00007FFFF3A7DE57 48 63 CB                   movsxd  rcx, ebx         ; Move with Sign-Extend Doubleword
00007FFFF3A7DE5A 48 89 4C 24 48             mov     [rsp+yyy], rcx

相当于在Python3中执行:

hex( xxx - ( ( 0xdd67c8a7 * xxx ) >> 0x25 ) * 0x25 )

进一步等价于:

hex( xxx - ( xxx // 0x25 ) * 0x25 )
hex( xxx % 0x25 )

python

参看:

https://github.com/benaadams/Primes
https://github.com/benaadams/Primes/blob/master/Program.cs

Program.cs中列举了一批用于除法优化的神密常量，比如:

new PrimeInfo(37, 0xdd67c8a7, 5)
new PrimeInfo(968897, 0x8a86bc61, 19)
new PrimeInfo(1843042529, 0x4a925fdf, 29)

将X除以968897优化成乘法运算，其中一种方案如下:

mov ecx,X
mov eax,08A86BC61h
imul ecx
add edx,ecx
sar edx,013h
shr ecx,31
add edx,ecx
; quotient now in edx

提一个通用问题，假设在IDA中肉眼怀疑有对除法的优化，不考虑Google搜索神密常量，不考虑动态调试获取商后反向求出除数，有无办法从神密常量(0xdd67c8a7,5)着手进行数学推导得到除数37，从而得到人性化的最简表达式。

假设a是被除数、b是除数，有如下关系:

( 0xdd67c8a7 * a ) >> 0x20 >> 5 = a // b
=>
( 0xdd67c8a7 * a ) = pow(2,0x20+5) * a // b
=>
b = pow(2,0x20+5) // 0xdd67c8a7 + 1

在Python3中执行:

pow(2,0x20+5) // 0xdd67c8a7 + 1     = 37
pow(2,0x20+19) // 0x8a86bc61 + 1    = 968897
pow(2,0x20+29) // 0x4a925fdf + 1    = 1843042529

用此办法可以静态获取除法优化前的除数，绝对比F5结果好。