首页
服装论坛t.vhao.net
专栏
课程

[原创]so逆向中碰到的除法优化浅析

2019-5-10 19:15 1501

[原创]so逆向中碰到的除法优化浅析

2019-5-10 19:15
1501

0x01 除法优化浅析

比来花了点时间去逆向一些小法式榜样,碰到“(R0 * 0xAAAAAAAB) >> 32”如许的运算时,一时看不出何意。后来经过搜刮,才知道这是编译器对除法做的优化(由于除法指令比较耗时)。在这里做个小笔记。

关于除法操作,假设除数是2的整数次方,那直接右移便可以了。比如:R0/4可以用R0>>2代替。假设除数不是2的整数次方,那若何优化呢?简单写一下道理:


结合示例来看:

void test(unsigned int a) {
  LOG("unsigned int a / 3 = %d", a / 3);
}

test函数很简单,看一下反汇编代码(重要关怀个中的a/3):

LDR        R2, =0xAAAAAAAB
UMULL.W    R2, R3, R0, R2
LSRS       R1, R3, #1

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行反汇编代码,如今来反推回高等代码。

LDR        R2, =0xCCCCCCCD
UMULL.W    R2, R3, R0, R2
LSRS       R1, R3, #2

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。与实际的源码正好对应的上:

void test(int a) {
  LOG("int a / 5 = %d", a / 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函数简单修改一下:

void test(int a) {
  LOG("int a / 3 = %d", a / 3);
}

本来参数类型是unsigned int,如今参数类型是int。看一下a/3对应的反汇编代码:

LDR        R2, =0x55555556  
MOV        R1, R0           
SMULL.W    R2, R3, R0, R2   
SUB.W      R1, R3, R1,ASR#31

这4行代码合起来就是:(R0 * 0x55555556) >> 32 – (R0 >> 31),个中R0 >> 31是算数右移。先忽视前面的减法,只关怀“(R0*0x55555556)>>32”。

除法优化道理:a/b = (a*c) >> n,个中c=(2^n)/b。

由“(R0 * 0x55555556) >> 32”,可知n=32,c=0x55555556。根据c=(2^n)/b,可知b=(2^n)/c=(2^32)/0x55555556=2.9999999986,即b=3。所以“(R0 * 0x55555556) >> 32”即R0/3。这么一看,貌似前面的“– (R0 >> 31)”是多余的。其实不然,简单分析一下。

参数类型是int,“R0 >> 31”就是取符号位(算数右移)。那么有两种情况:

1)R0是正数,那么R0 >> 31成果为0,减法相当于甚么也没做。除法优化道理照样:a/b = (a*c) >> n,个中c=(2^n)/b。

2)R0是正数,那么R0 >> 31成果为0xFFFFFFFF,即-1,减-1相当于加1。除法优化道理变成:a/b = ((a*c) >> n) + 1,个中c=(2^n)/b。

为甚么被除数为正数时,前面要加1呢?由于“(a*c) >> n”是向下取整的成果。加1是为了向0取整,而c/c++说话关于整数除法的规定正是向0取整。

关于除法优化,还有很多更复杂的情况,和一系列的实际推导。限于时间,我就先懂得到这。关于简单的情况,能根据反汇编代码,反推回优化之前的除法操作了。

文/十八垧    

https://www.jianshu.com/p/c2ecadbb7b19



[推荐]看雪企服平台,供给安然分析、定制项目开辟、APP等级保护、渗透渗出测试等安然办事!

最后于 2019-5-11 09:06 被十八垧编辑 ,缘由:
上一主题 下一主题
最新答复 (6)
dreamerqq 2019-5-10 21:35
2
0
楼主分析得挺清楚的了。看了下链接中的误差分析,感到数学推导过程看着挺复杂。
假设能总结下n是怎样拔取得就更好了
Vn小帆 2019-5-11 08:55
3
0
可以的
金奔跑 2019-5-13 09:24
5
0
进修了~
渔夫不吃鱼 2019-5-15 22:03
6
0
dreamerqq 楼主分析得挺清楚的了。看了下链接中的误差分析,感到数学推导过程看着挺复杂。 假设能总结下n是怎样拔取得就更好了
n的值是根据存放器位数决定的
关键的就是这步 :UMULL.W    R2, R3, R0, R2,计算的成果只保存在了低位,就产生了移位操作,这个移位的位数就是存放器位数
十八垧 1 2019-5-15 22:22
7
0
渔夫不吃鱼 n的值是根据存放器位数决定的 关键的就是这步 :UMULL.W R2, R3, R0, R2,计算的成果只保存在了低位,就产生了移位操作,这个移位的位数就是存放器位数
文中n的值,指的是总的移位数。平日是由:2^k < b(除数) < 2^(k+1),算出k,然后n=32+k。
最后于 2019-5-15 22:23 被十八垧编辑 ,缘由:
旅客
登录 | 注册 方可回帖
前往