【小课堂】汇编级除法优化

小课堂


先给一些背景:

(1)比如 7 / 2 = 3 …… 1       -7 / 2= -3 …… -1

比较重要的是,余数的绝对值小于除数的绝对值,并且余数和被除数同正负

(2)由于C语言中除法是向0取整,也就是“截断除法”

不难发现,正数除以正数时,截断除法相当于向下取整(3.5 -> 3);而负数除以正数时,截断除法相当于向上取整( -3.5 -> -3 )

(3)除以2的k次幂通常会被优化成右移k位,这里考虑除以2时

用一个signed byte表示7,是00000111,右移一位变成00000011是3,是正确的

但是,考虑-7/2,-7是11111001,右移一位后变成11111100,这是-4,因为这是向下取整的结果,所以比正确的答案 -3少了1

代码中为了统一和效率,如果是32位的数字,会先右移31位扩展符号位。原先是正数则最高位是0,那么最后会变成32个0,也就是0,;原先是负数最高位是1,最后会变成32个1,也就是-1,暂且把这个扩展符号位后形成的数记作S,

那么,我们只需要把右移一位的结果,减去这个S,就可以得到正确的截断除法的值

7/2 = 7>>1 –(0) = 3        -7/2 =-7>>1 – (-1)= -3

(这一点在例题代码中会再次提到)

(4)当除以正数N,而N不是2的次幂时,编译器会生成一个magic_number(C),以使除法优化成乘法,提高效率

注意我强调的……(n,c)这个取值是成对的,一般取右移的位数n大于64,(理由一会再解释),比如n取72,这样C也就是常数了

图片中的证明表示:被除数(正数)乘以magic_number后再右移n位,即为除法的结果;如果是负数需要 +1

没错…就是第三点,最后统一减去符号扩展形成的数即可

好了,背景介绍的差不多了,来道CTFtime上的题目吧 :https://ctftime.org/task/5294?tdsourcetag=s_pcqq_aiomsg


简单看下,这就是除以N的除法优化代码,题目一般都是二分查找搞定flag的,这里作为一个较真的人……用数学来解一下

汇编代码中,0x49ea309a821a0d01就是magic_number

sar   $0x3f,%rdi   因为long long是64位的,这里把函数参数rdi(被除数)右移63位,原先是正数则rdi变为0,原先是负数则rdi变为-1

 

imul %rdx之后,因为被除数被保存在了rax之中,因此乘积高位被放在rdx,低位被放在rax,最后我们发现乘积低位rax在后面没有被用到

原因是第四点背景提到的,n取值要大于64,这样128位的乘积只需要考虑rdx就可以了,乘积低64位rax被移位后必定为0,无需考虑,也提高了效率

后面因为rax作为返回值,x*c>>n被保存在了rax中,再sub rax,rdi

也就是我们提到的减去符号拓展形成的数

这个证明可能需要好好理解下(手写推导一次…)

好了现在我们看看flag(除数)是多少

因为我们最后只保留了乘积高位rdx,把rdx右移了0x30位

这就相当于把128位乘积右移了(64+0x30)==112位

那么,因为c = 2^n / y   y = 2^n / c (其中c就是magic_number)

 

现在c已知,为0x49ea309a821a0d01,n已知,为112

算出除数y即可

注意的是这里虽然除法结果是精准的,但是反推除数时python的计算结果可能会有1的误差,这一点用二分算法时也会出现

其实除以正数还有第二种情况的优化算法,编译器根据C的值会有不同的选择,这就是《加密与解密》上除以正非2次幂的优化公式2,比如此题

以及除数为负数的稍复杂情况就不讨论了,相关内容可以看下《加密与解密》和《C++反汇编与逆向分析揭秘》,前者结论全面,后者推导较多



本文作者:白帽100安全攻防实验室

本文为安全脉搏专栏作者发布,转载请注明:https://www.secpulse.com/archives/96340.html

Tags:
评论  (0)
快来写下你的想法吧!

白帽100安全攻防实验室

文章数:13 积分: 52

安全问答社区

安全问答社区

脉搏官方公众号

脉搏公众号