设为首页|收藏本站|求打赏 关注微信公众号

腾龙技术论坛

 找回密码
 立即注册

QQ登录

只需一步,快速开始

PS鏁欑▼
【官方公告】论坛所有广告均为商业行为,需要交易的请尽量走担保程序,所有因广告产生的任何纠纷请私下解决,版主出售东西是私人行为,如有纠纷请私下解决,与论坛无关。【官方公告】禁止发布黑客工具如,扫描,抓鸡,爆破...等破坏网络安全的工具!欢迎举报违规工具! 【站外广告】挂机赚钱-利用硬件平台的CPU和GPU的运算能力——利用闲置资源做分布式计算(云计算),这种模式不占硬盘空间,不占网速,联网即可!注册就送钱 【站外广告】承接软件定制,出售免杀远控 上线无提示 重启上线 可捆绑任意图片或可执行文件,另出售集群,挖矿软件 收徒~ QQ 544003575

【站外广告】强烈推荐你使用宝塔面板,并送你半年宝塔面板小程序
 【站外广告】出售免杀远控 可捆绑图片文档、免杀360全套、管家、金山、免杀持久win7/8/win10系统 QQ:723200497
【站外广告】出售免杀远控 上线无提示 重启上线 可捆绑任意图片或可执行文件,另出售集群,挖矿软件 收徒~ QQ 2100818883 【站外广告】出售单文件过启动远控,超级完美的稳定性,出售扫爆服务器,需要联系QQ835266201【站外广告】出售扫描爆破服务器,24小时永不封机!自带100G防御免疫CC,有需要Q我510676301【站外广告】DarkNet论坛,有丰富的黑客工具教程,免杀远控资源
【站外广告】出售扫爆服务器,永不封机!100G防御免疫CC,QQ:3249264512【站外广告】出售实力免杀远控、免杀360套装、金山管家、瑞星卡巴、等杀毒、接游戏封装exe、dll免杀制作。联系QQ319371100【站外广告】网站搭建,博客搭建,网站搬家,QQ:676672384投放广告请联系QQ:2918857571
本站长不接单,不卖远控之类的。
 
查看: 257|回复: 0

[编程开发] so逆向中遇到的除法优化浅析

[复制链接] |关注本帖
  • TA的每日心情
    奋斗
    2019-5-19 00:24
  • 签到天数: 205 天

    连续签到: 2 天

    [LV.7]常住居民III

    298

    主题

    597

    帖子

    4134

    积分

    ☆独步武林★

    Rank: 8Rank: 8

    UID
    2342
    威望
    987
    贡献
    442
    在线时间
    67 小时
    注册时间
    2017-1-18
    扫一扫,手机访问本帖
    发表于 2019-5-12 10:29 | 显示全部楼层 |阅读模式
    0x01 除法优化浅析
    最近花了点时间去逆向一些小程序,遇到“(R0 * 0xAAAAAAAB) >> 32”这样的运算时,一时看不出何意。后来经过搜索,才知道这是编译器对除法做的优化(因为除法指令比较耗时)。在这里做个小笔记。
    对于除法操作,如果除数是2的整数次方,那直接右移就可以了。比如:R0/4可以用R0>>2代替。如果除数不是2的整数次方,那如何优化呢?简单写一下原理:
    738921_5HZZPYYU9JN4KFP.png
    结合示例来看:
    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取整。
    关于除法优化,还有很多更复杂的情况,以及一系列的理论推导。限于时间,我就先了解到这。对于简单的情况,能根据反汇编代码,反推回优化之前的除法操作了。
    文/十八垧   






    上一篇:2019年5月12日签到记录贴
    下一篇:2019年5月13日签到记录贴
    回复

    使用道具 举报

    *滑动验证:
    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    QQ|Archiver|手机版|小黑屋|腾龙技术论坛 ( 粤ICP备18109381号 )

    免杀论坛
    Keywords: 免杀论坛 免杀论坛

    GMT+8, 2019-5-21 01:39 , Processed in 0.072504 second(s), 27 queries , Gzip On, Redis On.

    Powered by 腾龙技术论坛 X3.4

    © 2012-2018 腾龙技术论坛

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