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

（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++反汇编与逆向分析揭秘》，前者结论全面，后者推导较多