反汇编代码还原之除数为2的幂

本文为看雪论坛精华文章

看雪论坛作者ID：TkBinary

• 目录
  

•         系列文章

•          一. 除法优化以及反汇编代码还原

•              1.1 为什么学习除法优化以及除法为什么优化

•              1.2 学习除法优化的必备数学能力

•              1.3 除法的向零取整

•              1.4 汇编中除法要了解的知识

•          二. 除法除数为正数2的幂有符号表现形式与代码还原

•              2.1 向下取整转化为向上取整 数学定理

•              2.2的幂有符号高级代码与汇编代码

•              2.3 除数为变量,未知除数不做优化

•              2.4除数为2以及无分支优化

•              2.5除数为4的优化

•              2.6 除数为8的优化

•          三. 除法除数为正数2的幂无符号表现形式与代码还原

•              3.1 高级代码与核心汇编代码

•          四. 除数为负2的幂表现形式

•              4.1 高级代码与核心汇编代码

•          五.  Visual Studio 2019 x86x64 下除数为2的幂的优化方式

•              5.1 x86下 除数为正数2的幂

•              5.2 x86下除数为负数2的幂

•              5.3 x64下除数为负数2的幂

系列文章

反汇编技术之熟悉IDA工具

https://bbs.pediy.com/thread-224499.htm

反汇编逆向技术之寻找Main入口点

https://bbs.pediy.com/thread-224500.htm

*点击文字即可跳转文章

一. 除法优化以及反汇编代码还原

1.1 为什么学习除法优化以及除法为什么优化

学习除法优化能使我们认识反汇编中的除法表达式，进而更好地进行代码还原。

除法指令对应的指令是Div以及IDIV，而这两个指令周期是特别长的。

比如一个DIV是100，而sar指令就10，那么编译器肯定会选择使用Sar指令来进行优化。

除法是优化的除数，而我们反汇编的时候就是得出除数是多少，进而还原为C代码。

除数是常量才有优化的余地。如果是一个未知除数(变量) ，那么就会使用原生 DIV 或者IDIV来进行操作。

1.2 学习除法优化的必备数学能力

不过多赘述，必备技能。

1.3 除法的向零取整

除法优化是根据数学模型来进行优化的。除非数学上有突破，否则在底层的除法反汇编表现形式不会有多大的变化，学习除法要具备简单的数学知识.。

原因是在我们计算机中，除法是整数除法，也就是向零取整的。

比如现实中：

7/3 = 2..1 而计算机中就如下 7 / 3 = 2

• 向下取整

• 向上取整

• 向零取整

何为向下取整、向上取整、零取整？

有一坐标线，在这条坐标线上有一些列数字，包含正数、负数、0。

如下：

0往右，属于正数。

0往左，属于负数。

向下取整：

比如我们说对 a 向下取整，那么意思就是取得不大于a的最大整数。

比如 a = 4.5 ，那么向下取整就是 4。

比如 a = -4.5 ，那么向下取整就是 -5。

向下取整也可以理解为在坐标线上，是向左走，取得不大于这个数的最大整数。

向上取整：向上取整则相反，在坐标线上往右走，意思是取得 +  最接近a的整数值。另一个意思就是：取得不小于a的最大整数值。

比如a = 4.5 向上取整则是 5

比如 a = -4.5 向上取整就是 -4

向零取整：

向零取整就简单的，都是往0方向取整的。

对于正数 a 的向零取整，等价于是对a的向下取整。

对于负数 a 的向零取整，等价于是对 -a的向上取整。

a = 4.5 向零取整则为4。

a = -4.5 向零取整则为 -4。

a = 被除数

b = 除数

当商为正数 > 0 与商为负数分别有两种表现形式

正数除数计算，则使用的公式是向下取整。

负数除数计算，则使用的公式是向上取整。

1.4 汇编中除法要了解的知识

汇编中有符号和无符号、混除，其结果是有符号数。

二. 除法除数为正数2的幂
有符号表现形式与代码还原

2.1 向下取整转化为向上取整数学定理

看下图：

如上图，分别对被除数为正负数向上取整与向下取整做了公式转换。

这里有四个公式分别为公式1、公式2、公式3、公式4。

2.2 幂有符号高级代码与汇编代码

首先我们先看一下除法是2的幂的时候，代码表现形式。

高级代码：

int main(int argc, char* argv[])
{
    /*
    除法
    */
    int NumberOne = 0;
    int NumberTwo = 0;

    scanf("%d",&NumberOne);
    scanf("%d",&NumberTwo);


     int  Count1 = NumberOne / NumberTwo; 

     int Count2 = NumberOne / 2;

     int Count3 = NumberTwo / 4 ;   

     int Count5 = NumberTwo / 8;     

    printf("%d%d%d%d%d",Count5,Count3,Count2,Count1);
    system("pause");

    return 0;
}

核心代码反汇编，去掉无用汇编：

mov     ecx, [esp+1Ch+var_8]
mov     esi, [esp+1Ch+var_4]
mov     eax, ecx
cdq                   
idiv    esi


mov     eax, ecx
cdq
sub     eax, edx
sar     eax, 1


mov     eax, esi
cdq
and     edx, 3
add     eax, edx
sar     eax, 2


cdq
and     edx, 7
add     eax, edx
sar     eax, 3
push    eax

2.3 除数为变量，未知除数不做优化

看下高级代码：

int  Count1 = NumberOne / NumberTwo;

对应反汇编：

mov     ecx, [esp+1Ch+var_8]
mov     esi, [esp+1Ch+var_4]
mov     eax, ecx
cdq                   
idiv    esi

这里使用了cdq汇编指令。cdq是符号扩展的意思，是将eax扩展为edx。eax 什么意思？如果eax符号位为1，那么edx就用1填充，也就是FFFFFFFF，如果符号位为0，那么edx结果就为 0。

这里使用cdq 意思就是我们是个有符号数，直接使用 idiv 来进行除法。

遇到这种形式，我们直接根据汇编进行还原即可。

ecx = var_8
esi = var_4
ecx / esi   == var_8 / var_4

2.4 除数为2以及无分支优化

除数为 2 等价于是 2的一次方。设幂 = n ，则n = 1 sar n 等价于 x / 2^n。

首先如果除数为2，且为正数，那么我们的思路是可以用sar算术右移，进行优化的。

在汇编中sar为算术右移，shr为逻辑右移。

两者区别如下：

正因为我们是用有符号被除数来进行除法的，所以需要判断符号位。如果判断符号位，那么就可能需要cmp或者影响标志位的指令，以及对应的jxx指令来判断商是为正数的计算结果，以及为负数的计算结果。

而显然如果这样，CPU指令周期会更长，根本没有优化的余地，所以就要进行无分支优化。

观看高级代码与对应汇编：

int Count2 = NumberOne / 2;

mov     eax, ecx                获得被除数
cdq                                被除数进行符号扩展
sub     eax, edx                被除数减去符号扩展位
sar     eax, 1                    算术右移

乍一看这几句代码很晕，为什么/2汇编代码表现为这样？

其实可以分为两部分看。因为这里面带有无分支优化(也就是判断商为负还是为正数)，我们拆分开看。

1）算术右移的优化

mov     eax, ecx                获得被除数
sar     eax, 1

这两句应该能看明白吧。获得被除数，被除数算术右移1位，等价于被除数/2，这也是sar指令的作用。

sar 1就等于 /2 ，那么 sar2 就是4，以此类推 sar n 是否就是等价于 /2^n。

如果单看这两句应该就明白了，反汇编代码还原的时候直接还原为 eax /2，除数还原出来就是2。

2）无分支优化

无分支优化我们说过，就是判断商为正还是为负数。

mov     eax, ecx                获得被除数
cdq                                被除数进行符号扩展
sub     eax, edx                被除数减去符号扩展位
sar     eax, 1                    算术右移

着重看一下cdq 以及 sub eax,edx。

cdq 如果被除数是负数，那么扩展符号位之后 edx = -1 (也就是FFFFFFFF)。

cdq 如果被除数为正数 那么扩展符号位之后 edx = 0。

所以在这里 edx要么是-1，要么是0。

sub eax,edx 指令的含义就是调整被除数。如果为负数那么被除数+1，如果是正数不做调整。

负数的情况下，sub eax,edx === (-被除数) - (-1) 。根据数学定理，负负得正，等价于 (-被除数) + 1。

正数的请开情况下 sub eax,edx == 被除数- 0 == 被除数。所以如果是正数的情况下，cdq + sub eax,edx。

这两个指令是没有用的。

3）无分支优化的调整疑问

很多人看完之后可能会想，为什么要做调整？比如 4 /2 = 2 那么-4 /2 = -2 结果不一样吗？

+1调整之后我们的被除数就变为了 -5 / 2了，再计算 -5/2 =-2.5了吗？原因也是我说过的，在计算机中只会计算整数除法。

而我们的整数除法本质就是向零取整，所以对于负数来说，其结果是向上取整来计算的。对于正数来说其结果是向下取整来计算了，所以我们总结起来就是向零取整，就是让计算负数的时候满足向上取整。

对于计算正数的时候满足向下取整，所以这里优化如果是负数的情况下，应该要满足向上调整，所以+1调整。

4）反汇编代码还原

mov     eax, ecx                获得被除数
cdq                                被除数进行符号扩展
sub     eax, edx                被除数减去符号扩展位
sar     eax, 1                    算术右移

遇到这种反汇编不要慌，稳一下，其实就是再算除法，直接根据 sar n来进行还原除数即可。

上述汇编进行高级代码还原为如下：

eax = 被除数

eax / 2^1 === 被除数 / 2

只不过这里有无分支判断，所以被除数可以看做是有符号数。

5）数学原理

被除数为正数且除数为>0：

如果想知道原理，那么可以看这个小主题。如果想知道如何还原不用看这个主题了。

我们说过对于被除数为正数的除法计算，且其除数为2^n值的时候，那么商就按照向下取整来计算。

汇编中表现形式就是 sar n即可，被除数 >> n的形式。

那么设 x = 被除数，那么 x / 2n 等价于 x >>n

x = 4

2^n = 2

代入公式得出 4 / 2 = 2 n，值取为1，那么 2^1 = 2。

被除数为负数：

被除数为负数的除法计算，且除数大于0，那么商就按照向上取整来计算。

而如果被除数为负数，那么使用公式2可以将向上取整优化为向下取整。

设x = 被除数 x < 0 设置b = 除数，并且值 = 2^n 并且是大于0。

那么 x / b 是向下取整来计算的。

如果转化为向上取整，则等于 (x + b - 1) / b

设x = -4

b = 2

代入公式得

(-4 + 2 - 1) / 2 ===> (-3) /2 商向下取整 = -2

所以我们的负数在汇编中的表现形式其实是定式 (x + (b - 1)) >>n

所以才有了我们的代码：

mov     eax, ecx               
cdq                                被除数为负数 edx = -1
sub     eax, edx                -被除数 - 1    == (被除数 + 1)
sar     eax, 1                    /n

(-被除数 - 1) / n ，商向下取整。

所以这里sar是向下取整，对于正数来说没问题，向下取整就是直接计算即可.。x >>n 但是对于负数来说，直接向下。

取整那么结果就会有问题，所以要做+1调整才可以。中间产生的变化就是将向上取整变为了向下取整转化后如果除数大于0且被除数是负数，所以就产生了 +1 调整。

2.5 除数为4的优化

4 = 2的2次方

1）汇编代码表现形式

观看汇编：

mov     eax, esi   获得被除数
cdq                   符号扩展.edx 要么为1 要么为0
and     edx, 3     被除数 & 2^n - 1
add     eax, edx   被除数 + 符号扩展
sar     eax, 2     向下取整完成除法

还是分为两部分看：

被除数为正数，除数为正数，向下取整计算 x >> n

mov     eax, esi   获得被除数
sar     eax, 2     向下取整完成除法

被除数为负数，除数为正数：

mov     eax, esi   获得被除数
cdq                   符号扩展.edx 要么为1 要么为0
and     edx, 3     被除数 & 2^n - 1
add     eax, edx   被除数 + 符号扩展
sar     eax, 2     向下取整完成除法

还是带有无分支指令。

如果被除数为负数，那么除法需要按照向上取整原则来进行运算。但是我们因为要去掉分支，所以还是要将向上取整转化为向下取整，使用公式2。

正数：

 (x + b -1) / b

and edx,3 这里的3可以看做是b-1，也就是2^n-1值，其实是已经计算出来了。

add eax,edx 这里可以看做是 -被除数 + (2^n-1)。

简化一下：

(-被除数 + (2^n-1) /b

n的取值我们看到是2 那么2^n = 4

继续简化

(-被除数 + (4 - 1) / 4

继续简化

(-被除数 + 3) / 4

所以上面的and edx,3 其实就是让edx变为3。如果是正数计算，edx = 0，那么我们说正数不用看这两条指令。如果是负数，edx就是-1，-1%3 = 3，其实就是设置edx为3，最后add再去想加，就满足了我们的公式。

sar 2 等价于 /4

2）代码定式反汇编

mov     eax, esi  
cdq                 
and     edx, 3    
add     eax, edx  
sar     eax, 2

遇到这种定式，直接看下n值。这里的n值为2，所以得出 2^n = 4，也就是得出了除数为4。

这里的3可以看做是负数做优化的时候，需要将向上取整代码转化为向下取整所产生的额外代码。

比如这里是3，可以看做是 2^n - 1，如果符合这个形式，那么直接得出除数为2即可。

这一块代码反汇编为高级代码为：

eax = var_xxx
eax = eax / 4  == var_xxx / 4

2.6 除数为8的优化

除数8 = 2 ^3 次方，所以还是按照公式还原即可。如果被除数为负数，除数为正数，去看公式2。公式2将向上取整转为向下取整。

正数：x >> n

负数(x + (b - 1) / b：

mov     eax, esi
cdq
and     edx, 7
add     eax, edx
sar     eax, 3

代码同 2^1 次方 2^2次方 还原方式一样。

三. 除法除数为正数2的
幂无符号表现形式与代码还原

3.1 高级代码与核心汇编代码

高级代码：

int main(int argc, char* argv[])
{
    /*
    除法
    */
     unsigned int NumberOne = 0;
     unsigned int NumberTwo = 0;



    scanf("%u",&NumberOne);
    scanf("%u",&NumberTwo);


     unsigned  Count1 = NumberOne / NumberTwo; 

     unsigned Count2 = NumberOne / 2;

     unsigned Count3 = NumberTwo / 4 ;


     unsigned Count5 = NumberTwo / 8;     

    printf("%d%d%d%d%d",Count5,Count3,Count2,Count1);
    system("pause");

    return 0;
}

核心汇编：

.text:0040102C                 mov     esi, [esp+1Ch+var_8]
.text:00401030                 mov     ecx, [esp+1Ch+var_4]
.text:00401034                 mov     eax, esi
.text:00401036                 xor     edx, edx
.text:00401038                 div     ecx                变量/变量 符号位不适用cdq因为无符号所以直接清空edx

.text:0040103A                 mov     edx, ecx
.text:0040103C                 shr     esi, 1            直接使用逻辑右移来进行计算结果.符号位补0
.text:0040103E                 shr     edx, 2
.text:00401041                 shr     ecx, 3

可以看到如果我们无符号 / 2的幂，直接使用shr逻辑右移来进行优化了。

反汇编的时候取n值进行还原即可：

.text:0040103C                 shr     esi, 1            除数还原为 esi / 2^1
.text:0040103E                 shr     edx, 2            除数还原为 edx /2^2
.text:00401041                 shr     ecx, 3            除数还原为 ecx /2^3

四. 除数为负2的幂表现形式

4.1 高级代码与核心汇编代码

int main(int argc, char* argv[])
{
    /*
    除法
    */
      int NumberOne = 0;
      int NumberTwo = 0;



    scanf("%d",&NumberOne);
    scanf("%d",&NumberTwo);


     int  Count1 = NumberOne / NumberTwo; 

     int Count2 = NumberOne / -2;

     int Count3 = NumberTwo / -4 ;

     int Count5 = NumberTwo / -8;     

    printf("%d%d%d%d%d",Count5,Count3,Count2,Count1);
    system("pause");

    return 0;
}

汇编：

mov     esi, [esp+1Ch+var_8]
mov     ecx, [esp+1Ch+var_4]
mov     eax, esi
cdq
idiv    ecx



mov     eax, esi
cdq
sub     eax, edx
sar     eax, 1
neg     eax



mov     eax, ecx
cdq
and     edx, 3
add     eax, edx
sar     eax, 2
neg     eax



mov     eax, ecx
cdq
and     edx, 7
add     eax, edx
sar     eax, 3
neg     eax

观看汇编代码，可以看到其代码定式跟除数为2的幂一样，唯一不同的就是商的结果进行求补。

neg 指令的作用就是 0 -xxx 比如eax = 1 neg(eax) 等于是 0 - 1 = FFFFFFFF。

这里加这条指令的含义就是，如果商为负数，那么进行求补，商的结果就为正数了。

还原方式还是取n值，唯一不同的是因为有neg，所以前边加负数。

sar eax,1     还原为 eax / (-2^1)  下面同上
neg eax

sar eax,2
neg eax

sar eax,3
neg eax

五.  Visual Studio 2019 x86x64
下除数为2的幂的优化方式

其实这个主题主要做一个对比，目的就是告诉大家 VC6.0 与 Visual Studio 2019下代码优化方式一样。

5.1 x86下 除数为正数2的幂

高级代码：

int main(int argc, char* argv[])
{
    /*
    除法
    */
    int NumberOne = 0;
    int NumberTwo = 0;
 
 
 
    scanf("%d", &NumberOne);
    scanf("%d", &NumberTwo);
 
 
    int  Count1 = NumberOne / NumberTwo;
 
    int Count2 = NumberOne / 2;
 
    int Count3 = NumberTwo / 4;
 
    int Count5 = NumberTwo / 8;
 
    printf("%d%d%d%d%d", Count5, Count3, Count2, Count1);
    system("pause");
 
    return 0;
}

反汇编代码：

.text:00401080                 push    ebp
.text:00401081                 mov     ebp, esp
.text:00401083                 sub     esp, 8
.text:00401086                 push    esi
.text:00401087                 lea     eax, [ebp+var_4]
.text:0040108A                 mov     [ebp+var_4], 0
.text:00401091                 push    eax
.text:00401092                 push    offset unk_41ECDC
.text:00401097                 mov     [ebp+var_8], 0
.text:0040109E                 call    sub_401050
.text:004010A3                 lea     eax, [ebp+var_8]
.text:004010A6                 push    eax
.text:004010A7                 push    offset unk_41ECDC
.text:004010AC                 call    sub_401050
 
核心汇编
.text:004010B1                 mov     eax, [ebp+var_4]
.text:004010B4                 mov     esi, [ebp+var_8]
.text:004010B7                 cdq
.text:004010B8                 idiv    esi
.text:004010BA                 push    eax
.text:004010BB                 mov     eax, [ebp+var_4]
.text:004010BE                 cdq
.text:004010BF                 sub     eax, edx
.text:004010C1                 sar     eax, 1
.text:004010C3                 push    eax
.text:004010C4                 mov     eax, esi
.text:004010C6                 cdq
.text:004010C7                 and     edx, 3
.text:004010CA                 add     eax, edx
.text:004010CC                 sar     eax, 2
.text:004010CF                 push    eax
.text:004010D0                 mov     eax, esi
.text:004010D2                 cdq
.text:004010D3                 and     edx, 7
.text:004010D6                 add     eax, edx
.text:004010D8                 sar     eax, 3
.text:004010DB                 push    eax
 
 
.text:004010DC                 push    offset aDDDDD   ; "%d%d%d%d%d"
.text:004010E1                 call    sub_401020
.text:004010E6                 push    offset aPause   ; "pause"
.text:004010EB                 call    sub_4048C7
.text:004010F0                 add     esp, 28h
.text:004010F3                 xor     eax, eax
.text:004010F5                 pop     esi
.text:004010F6                 mov     esp, ebp
.text:004010F8                 pop     ebp
.text:004010F9                 retn
.text:004010F9 sub_401080      endp

可以发现，同vc6.0的代码并没有什么变化，因为优化是根据数学定理优化的。除非数学变了，否则不会发生改变。

5.2 x86下除数为负数2的幂

高级代码：

int main(int argc, char* argv[])
{
    /*
    除法
    */
    int NumberOne = 0;
    int NumberTwo = 0;
    scanf("%d", &NumberOne);
    scanf("%d", &NumberTwo);
    int  Count1 = NumberOne / NumberTwo;
    int Count2 = NumberOne / -2;
    int Count3 = NumberTwo / -4;
    int Count5 = NumberTwo / -8;
    printf("%d%d%d%d%d", Count5, Count3, Count2, Count1);
    system("pause");
 
    return 0;
}

汇编代码：

.text:004010B1                 mov     eax, [ebp+var_4]
.text:004010B4                 mov     esi, [ebp+var_8]
.text:004010B7                 cdq
.text:004010B8                 idiv    esi
.text:004010BA                 push    eax
.text:004010BB                 mov     eax, [ebp+var_4]
.text:004010BE                 cdq
.text:004010BF                 sub     eax, edx
.text:004010C1                 sar     eax, 1
.text:004010C3                 neg     eax
.text:004010C5                 push    eax
.text:004010C6                 mov     eax, esi
.text:004010C8                 cdq
.text:004010C9                 and     edx, 3
.text:004010CC                 add     eax, edx
.text:004010CE                 sar     eax, 2
.text:004010D1                 neg     eax
.text:004010D3                 push    eax
.text:004010D4                 mov     eax, esi
.text:004010D6                 cdq
.text:004010D7                 and     edx, 7
.text:004010DA                 add     eax, edx
.text:004010DC                 sar     eax, 3
.text:004010DF                 neg     eax
.text:004010E1                 push    eax

跟VC6.0一样没有多大变化。

5.3 x64下除数为负数2的幂

高级代码：

int main(int argc, char* argv[])
{
    /*
    除法
    */
    __int64 NumberOne = 0;
    __int64 NumberTwo = 0;
    scanf("%Id", &NumberOne);
    scanf("%Id", &NumberTwo);
    __int64  Count1 = NumberOne / NumberTwo;
    __int64 Count2 = NumberOne / -2;
    __int64 Count3 = NumberTwo / -4;
    __int64 Count5 = NumberTwo / -8;
    printf("%lld%I64d%lld%I64d", Count5, Count3, Count2, Count1);
    system("pause");
 
    return 0;
}

核心汇编代码：

.text:000000014000110E                 mov     rax, [rsp+38h+arg_10]
.text:0000000140001113                 cqo
.text:0000000140001115                 idiv    r10
 
 
 
.text:000000014000111B                 mov     rax, [rsp+38h+arg_10]
.text:0000000140001120                 cqo
.text:0000000140001122                 mov     [rsp+38h+var_18], r11
.text:0000000140001127                 sub     rax, rdx
.text:000000014000112A                 sar     rax, 1
.text:000000014000112D                 neg     rax
 
.text:0000000140001130                 mov     r9, rax
.text:0000000140001133                 mov     rax, r10
.text:0000000140001136                 cqo
.text:0000000140001138                 and     edx, 3
.text:0000000140001144                 sar     r8, 2
.text:000000014000114B                 neg     r8
 
 
.text:000000014000113F                 mov     rax, r10
.text:0000000140001142                 cqo
.text:0000000140001148                 and     edx, 7
.text:000000014000114E                 add     rdx, rax
.text:0000000140001151                 sar     rdx, 3
.text:0000000140001155                 neg     rdx
 
.text:0000000140001158                 call    sub_140001020
.text:000000014000115D                 lea     rcx, aPause     ; "pause"
.text:0000000140001164                 call    sub_1400045A4
.text:0000000140001169                 xor     eax, eax
.text:000000014000116B                 add     rsp, 38h

可以看到，除了 cdq 换成了 cqo之外，还是使用数学定理。

那么同理，除数为正数2的幂一样，大家自己建立工程出查看即可。

- End -

看雪ID：TkBinary

https://bbs.pediy.com/user-home-723188.htm

  *本文由看雪论坛 TkBinary 原创，转载请注明来自看雪社区。

本文参与了#看雪30天发帖打卡挑战#活动。

发帖见证成长，坚持见证不凡。

不仅可以收获进步，还可赢取物质奖励哦！

想要了解更多活动详情，戳 ↓

另外，贴心提示本次再印刷还没购买0day安全正版书籍的小伙伴抓紧时间啦！

目前已热销486本，满500本就可安排发货啦！
点击以下小程序即可预购！

推荐文章++++

公众号ID：ikanxue

官方微博：看雪安全

商务合作：[e-mail]

求分享

求点赞

求在看

戳“阅读原文”一起来充电吧！