吾爱破解 - LCG - LSG |安卓破解|病毒分析|www.52pojie.cn

 找回密码
 注册[Register]

QQ登录

只需一步,快速开始

查看: 4268|回复: 9
收起左侧

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

  [复制链接]
S18 发表于 2019-5-10 18:44
本帖最后由 S18 于 2019-5-10 22:43 编辑

0x01 除法优化浅析

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

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

图片 1.png

结合示例来看:
[C] 纯文本查看 复制代码
void test(unsigned int a) {
  LOG("unsigned int a / 3 = %d", a / 3);
}

test函数很简单,看一下反汇编代码(主要关心其中的a/3):
[Asm] 纯文本查看 复制代码
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行反汇编代码,现在来反推回高级代码。

[Asm] 纯文本查看 复制代码
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。与实际的源码正好对应的上:
[C] 纯文本查看 复制代码
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函数简单修改一下:
[C] 纯文本查看 复制代码
void test(int a) {
  LOG("int a / 3 = %d", a / 3);
}

原先参数类型是unsigned int,现在参数类型是int。看一下a/3对应的反汇编代码:
[Asm] 纯文本查看 复制代码
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取整。

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

文/十八垧   

免费评分

参与人数 4威望 +2 吾爱币 +15 热心值 +4 收起 理由
qtfreet00 + 2 + 12 + 1 感谢发布原创作品,吾爱破解论坛因你更精彩!
XhyEax + 1 + 1 热心回复!
独行风云 + 1 + 1 欢迎分析讨论交流,吾爱破解论坛有你更精彩!
lzc090 + 1 + 1 很容易理解,Tks

查看全部评分

本帖被以下淘专辑推荐:

发帖前要善用论坛搜索功能,那里可能会有你要找的答案或者已经有人发布过相同内容了,请勿重复发帖。

cat95f 发表于 2019-5-10 19:17
复杂,脑壳不够用了
Hmily 发表于 2019-5-10 21:57
 楼主| S18 发表于 2019-5-10 22:43
Hmily 发表于 2019-5-10 21:57
@S18 加外链是可以,但变相加群这是违规的。

sorry,不知坛规,已将博客地址删除了。
狂派威震天 发表于 2019-5-10 23:39
好东西,果断收藏。谢谢
chenjingyes 发表于 2019-5-11 00:23
感谢楼主分享,是新手必须学习的知识点
wengmingao 发表于 2019-5-11 13:45
感谢楼主分享,为我们新手提供知识
shuiyun 发表于 2019-5-12 10:33
多谢楼主
云胡不喜di 发表于 2019-5-12 10:54
感谢楼主分享,为我们新手提供知识
王宇 发表于 2019-5-15 21:00
感谢分享,支持一下
您需要登录后才可以回帖 登录 | 注册[Register]

本版积分规则 警告:本版块禁止灌水或回复与主题无关内容,违者重罚!

快速回复 收藏帖子 返回列表 搜索

RSS订阅|小黑屋|处罚记录|联系我们|吾爱破解 - LCG - LSG ( 京ICP备16042023号 | 京公网安备 11010502030087号 )

GMT+8, 2024-3-29 07:23

Powered by Discuz!

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表