0x01 除法优化浅析

最近花了点时间去逆向一些小程序，遇到“(R0 * 0xAAAAAAAB) >> 32”这样的运算时，一时看不出何意。后来经过搜索，才知道这是编译器对除法做的优化（因为除法指令比较耗时）。在这里做个小笔记。

对于除法操作，如果除数是2的整数次方，那直接右移就可以了。比如：R0/4可以用R0>>2代替。如果除数不是2的整数次方，那如何优化呢？简单写一下原理：

结合示例来看：

test函数很简单，看一下反汇编代码（主要关心其中的a/3）：

R0即test函数的参数a，最后a/3的计算结果保存在R1中。

首先，R0和R2做无符号数乘法（UMULL），结果的高32位保存到R3，低32位保存到R2。R2的值后续并没有用到，相当于舍弃了，即只保留R0*R2的高32位，也就是相当于整个乘法运算的结果右移了32位。所以前2行代码即：(R0 * R2) >> 32。第3行代码，又把R3逻辑右移了1位，所以这3行代码合起来就是：(R0 * R2) >> 33。而R2的值是0xAAAAAAAB，所以最终结果就是：(R0 * 0xAAAAAAAB) >> 33。也就是编译器将a/3优化成了(a * 0xAAAAAAAB) >> 33。

那么这个结果，与上面提到的除法优化原理（a/b = (a*c) >> n，其中c=(2^n)/b）吻合吗？

从“(a * 0xAAAAAAAB) >> 33”可知，编译器选择的n值为33，那么c=(2^33)/b。这里除数b为3，所以c=(2^33)/3=2863311530.67，向上取整为2863311531，换成16进制，即：0xAAAAAAAB。所以，这里编译器所做的优化与上面提到的优化原理正好吻合。刚才有一个c从2863311530.67向上取整为2863311531的操作，那么c的值就有一个0.33的误差。那为什么这个误差不会影响到最后的计算结果呢？这个是可以进行推理证明的，可以参考：https://www.cnblogs.com/shines77/p/4189074.html

0x02 由汇编反推除法

再来看一个例子，巩固一下。假设有以下3行反汇编代码，现在来反推回高级代码。

3行代码合起来即：(R0 * 0xCCCCCCCD) >> 34。

除法优化原理：a/b = (a*c) >> n，其中c=(2^n)/b。

由(R0 * 0xCCCCCCCD) >> 34，可知n=34，c=0xCCCCCCCD。根据c=(2^n)/b，可知b=(2^n)/c=(2^34)/0xCCCCCCCD=4.99999999971，即b=5（因为c值有一个很小的，不影响除法运算结果的误差，所以这里得到的值近似5）。所以，上述3行汇编代码对应的高级代码即：R0/5。与实际的源码正好对应的上：

再回头看一下刚开始提到的“R0 * 0xAAAAAAAB >> 32”，这个对应的高级代码应该是什么？

除法优化原理：a/b = (a*c) >> n，其中c=(2^n)/b。

由“(R0 * 0xAAAAAAAB) >> 32”，可知n=32，c=0xAAAAAAAB。根据c=(2^n)/b，可知b=(2^n)/c=(2^32)/0xAAAAAAAB=1.49999999983，即b=1.5。所以“(R0 * 0xAAAAAAAB) >> 32”即R0/1.5。不过，这里提到的除法优化是针对整数常量来说的，所以实际就是R0/(3/2)，即R0*2/3。

0x03 有符号数的除法优化

现在把test函数简单修改一下：

[招生]科锐逆向工程师培训(2024年11月15日实地，远程教学同时开班, 第51期)