C++逆向之表达式求值过程

算术运算和赋值

算术运算是指加法、减法、乘法、除法这四种数学运算。计算机中的四则运算和数学上的四则运算有些不同。
赋值运算类似于数学中的“等于”,是将一个内存空间中的数据传递到另一个内存空间中。由于内存没有处理器那样的控制能力,各个内存单元之间是无法直接传递数据的,必须通过处理器访问并中转,以实现两个内存单元间的数据传递。

各种算术运算的工作形式

加法

加法运算对应的汇编指令位ADD。在执行加法运算时,针对不同的操作数,转换的指令也会不同,编译器会根据优化方式选择最佳的匹配方案。常用的优化方案有如下两种:

  • O1:生成文件占用空间最小
  • O2:执行效率最高

本文主要对比和分析不开优化和O2优化时各种计算产生的目标代码方案。不开优化时编译的汇编代码会和源码是一一对应的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
using namespace std;
int main()
{
//变量定义
int nVarOne=0;
int nVarTwo=0;
//变量加常数的加法运算
nVarOne=nVarOne+1;
//常量加常量的加法运算
nVarOne=1+2;
//变量加变量的加法运算
nVarOne=nVarOne+nVarTwo;
printf("nVarOne = %d \n",nVarOne);
return 0;
}

不开任何优化

int nVarOne=0;
int nVarTwo=0;

1
2
00401637  |.  C74424 1C 000>mov dword ptr ss:[esp+0x1C],0x0          ;  把立即数0赋值给esp+0x1C.即nVarOne
0040163F |. C74424 18 000>mov dword ptr ss:[esp+0x18],0x0 ; 把立即数0赋值给esp+0x18.即nVarTwo

nVarOne=nVarOne+1;

1
00401647  |.  834424 1C 01  add dword ptr ss:[esp+0x1C],0x1          ;  对esp+0x1C进行加1运算

nVarOne=1+2;

1
0040164C  |.  C74424 1C 030>mov dword ptr ss:[esp+0x1C],0x3          ;  这里编译器直接计算出了两个常量相加后的结果,放入变量nVarOne中

nVarOne=nVarOne+nVarTwo;

1
2
00401654  |.  8B4424 18     mov eax,dword ptr ss:[esp+0x18]          ;  取出变量nVarTwo的数据放入eax中
00401658 |. 014424 1C add dword ptr ss:[esp+0x1C],eax ; 变量nVarOne加上eax的值

printf(“nVarOne = %d \n”,nVarOne);

1
2
3
4
0040165C  |.  8B4424 1C     mov eax,dword ptr ss:[esp+0x1C]          ;  取出变量nVarOne的数据放入eax中
00401660 |. 894424 04 mov dword ptr ss:[esp+0x4],eax ; 把eax的数据当作参数传入
00401664 |. C70424 459040>mov dword ptr ss:[esp],1.00409045 ; 传入字符串参数“nVarOne = %d \n”
0040166B |. E8 90FFFFFF call 1.00401600 ; 调用printf

在两个常量相加的情况下,编译器在编译期间就计算出两常量相加后的结果,将这个结果值作为立即数参与运算,减少了程序在运行期间的计算。

开启O2优化

开启O2优化后,编译出来的汇编代码有较大变化。由于效率优先,编译器会将无用代码去除,并将可合并代码进行归并处理。
观察代码,代码中没有任何加法操作。这是怎么回事?首先介绍两个关于优化的概念。在编译过程中,编译器常常会采用“常量传播”和“常量折叠”这样的方案对代码中的变量于常量进行优化,下面详细讲解这两种方案。

  • 常量传播
1
2
3
4
5
int main()
{
int nVar=1;
printf("nVar=%d\n",nVar);
}

变量nVar是一个在编译期间可以计算出结果的变量。因此,在程序中所有引用到nVar的地方都会直接使用常量1来代替,于是代码等价于:

1
2
3
4
int main()
{
printf("nVar=%d\n",1);
}
  • 常量折叠

当公式中出现多个常量进行计算的情况。且编译器可以在编译期间计算出结果时,源码中所有的常量计算都将被计算结果代替,如下面的代码:

1
2
3
4
5
int main()
{
int nVar=1+5-3*6;
printf("nVar=%d\n",nVar);
}

此时不会生成计算指令,因为1+5-3*6的值是可以在编译过程中计算出来的,所以编译器首先会计算出1+5-3*6的结果:-12,然后将数值-12替换原表达式,其结果依然等价,如下面代码所示:

1
2
3
4
5
int main()
{
int nVar=-12;
printf("nVar=%d\n",nVar);
}

现在变量nVar为一个在编译期间可计算出结果的变量,那么接下来组合使用“常量传播”对其进行常量转换是很合理的,程序中将不会出现变量nVar,直接以常量-12代替,如下面代码所示:

1
2
3
4
int main()
{
printf("nVar=%d\n",-12);
}

所以之前的代码被直接优化成了

1
2
3
4
5
int main()
{
printf("nVarOne = %d \n",3);
return 0;
}

减法

减法运算对应汇编指令SUB,虽然计算机只会做加法,但是可以通过补码转换将减法转变为加法形式来完成。

x-y<==>x+y(补)<==>x+y(反)+1

有了这个特性,所有的减法运算都可以转换成加法运算了。
不开任何优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
using namespace std;
int main(int argc,char * argv[])
{
//变量定义
int nVarOne=argc;
int nVarTwo=0;
//获取变量nVarTwo的数据,使用scanf防止变量被常量化
scanf("%d",&nVarTwo);
//变量减常量的减法运算
nVarOne=nVarOne-100;
//减法与加法混合运算
nVarOne=nVarOne+5-nVarTwo;
printf("nVarOne=%d\n",nVarOne);
return 0;
}

nVarOne=nVarOne-100;

1
00401683    836C24 1C 64    sub dword ptr ss:[esp+0x1C],0x64         ; 对esp+0x1C即nVarOne进行减100操作

nVarOne=nVarOne+5-nVarTwo;

1
2
3
4
5
6
7
00401683    836C24 1C 64    sub dword ptr ss:[esp+0x1C],0x64         ; 对esp+0x1C即nVarOne进行减100操作
00401688 8B4424 1C mov eax,dword ptr ss:[esp+0x1C] ; 取出nVarOne的数据放入eax
0040168C 8D50 05 lea edx,dword ptr ds:[eax+0x5] ; 通过取址操作间接完成eax加5,并把结果放入edx中
0040168F 8B4424 18 mov eax,dword ptr ss:[esp+0x18] ; 取出nVarTwo的数据放入eax
00401693 29C2 sub edx,eax ; 使用减法指令edx减去eax
00401695 89D0 mov eax,edx ; 把edx的值赋予eax
00401697 894424 1C mov dword ptr ss:[esp+0x1C],eax ; 把eax的数据放入变量nVarOne中

代码中的减法运算没有使用加负数的表现形式。那么,在实际的分析中,根据加法操作数的情况,当加数为负数时,执行的并非加法而是减法。
0040168C处通过lea操作间接完成加法,并赋值。lea AX,[BX]等价于 mov AX,BX。故0040168C等价于 mov edx,eax+0x5,但是由于mov不支持对操作数进行额外的加减,故采用lea指令的方式实现相加并赋值。
在O2选项下,其优化策略和加法一致,故不多言。

乘法

乘法运算对应的汇编指令有有符号imul和无符号mul两种。由于乘法指令的执行周期较长,在编译过程中。编译器会先尝试将乘法指令转换成加法,或使用位移等周期较短的指令。当它们都不可转换时,才会使用乘法指令。具体代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
using namespace std;
int main(int argc,char * argv[])
{
//为防止被视为无效代码,将每条运算作为printf参数使用
//变量定义
int nVarOne=argc;
int nVarTwo=argc;
//变量乘常量(常量值为非2的幂)
printf("nVarOne*15=%d\n",nVarOne*15);
//变量乘常量(常量值为2的幂)
printf("nVarOne*16=%d\n",nVarOne*16);
//两常量相乘
printf("2*2=%d\n",2*2);
//混合运算
printf("nVarTwo*4+5=%d\n",nVarTwo*4+5);
//两变量相乘
printf("nVarOne*nVarTwo=%d\n",nVarOne*nVarTwo);
return 0;
}

printf(“nVarOne15=%d\n”,nVarOne15);

1
2
3
4
5
6
7
00401645    8B5424 1C       mov edx,dword ptr ss:[esp+0x1C]          ; 取出esp+0x1C即变量nVarOne的数据放入edx
00401649 89D0 mov eax,edx ; 把edx的数据放入eax中
0040164B C1E0 04 shl eax,0x4 ; 把eax左移4位,即乘以16
0040164E 29D0 sub eax,edx ; eax=eax-edx,即综合上一句,即eax=edx*15
00401650 894424 04 mov dword ptr ss:[esp+0x4],eax ; 传入参数
00401654 C70424 45904000 mov dword ptr ss:[esp],1.00409045 ; ASCII "nVarOne*15=%d\n"
0040165B E8 A0FFFFFF call 1.00401600 ; 调用printf

printf(“nVarOne16=%d\n”,nVarOne16);

1
2
3
4
5
00401660    8B4424 1C       mov eax,dword ptr ss:[esp+0x1C]          ; 取出nVarOne的值放入eax中
00401664 C1E0 04 shl eax,0x4 ; eax左移4位,即乘以16
00401667 894424 04 mov dword ptr ss:[esp+0x4],eax ; 传入参数
0040166B C70424 54904000 mov dword ptr ss:[esp],1.00409054 ; ASCII "nVarOne*16=%d\n"
00401672 E8 89FFFFFF call 1.00401600 ; 调用printf

printf(“22=%d\n”,22);

1
2
3
00401677    C74424 04 04000>mov dword ptr ss:[esp+0x4],0x4           ; 编译期间计算出2*2=4,直接传入参数
0040167F C70424 63904000 mov dword ptr ss:[esp],1.00409063 ; ASCII "2*2=%d\n"
00401686 E8 75FFFFFF call 1.00401600 ; 调用printf

printf(“nVarTwo4+5=%d\n”,nVarTwo4+5);

1
2
3
4
5
6
0040168B    8B4424 18       mov eax,dword ptr ss:[esp+0x18]          ; 取出nVarTwo的值放入eax中
0040168F C1E0 02 shl eax,0x2 ; eax左移2位,即乘以4
00401692 83C0 05 add eax,0x5 ; eax加上5
00401695 894424 04 mov dword ptr ss:[esp+0x4],eax ; 传入参数
00401699 C70424 6B904000 mov dword ptr ss:[esp],1.0040906B ; ASCII "nVarTwo*4+5=%d\n"
004016A0 E8 5BFFFFFF call 1.00401600 ; 调用printf

printf(“nVarOnenVarTwo=%d\n”,nVarOnenVarTwo);

1
2
3
4
5
004016A5    8B4424 1C       mov eax,dword ptr ss:[esp+0x1C]          ; 取出变量nVarOne的数据放入eax中
004016A9 0FAF4424 18 imul eax,dword ptr ss:[esp+0x18] ; 使用有符号乘法指令
004016AE 894424 04 mov dword ptr ss:[esp+0x4],eax ; 传入参数
004016B2 C70424 7B904000 mov dword ptr ss:[esp],1.0040907B ; ASCII "nVarOne*nVarTwo=%d\n"
004016B9 E8 42FFFFFF call 1.00401600 ; 调用printf

除了两个未知变量的相乘无法优化外,其他形式的乘法运算都可以优化处理。如果运算表达式有一个常量值,则此时编译器会首先匹配各类优化方案,最后对不符合优化方案的运算进行调整。无符号乘法的原理与有符号的相同,不再说明。

除法

除法运算对应的辉壁指令分有符号idiv和无符号div两种。除法指令的执行周期较长,效率也较低,所以编译器会想尽办法用其他运算指令代替除法指令。C++中的除法和数学中的除法不同。在C+=中,除法运算不保留余数,有专门求取余数的运算(%)。也称之为取模运算。对于整数除法,C++的规则是仅仅保留整数部分,小数部分完全舍弃。
在C++中两个无符号整数相除,结果依然是无符号的;两个有符号的整数相除,结果则是有符号的;如果有符号数和无符号数混除,其结果则是无符号的。有符号数的最高位被未做数据位对待,然后作为无符号数参与计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
using namespace std;
int main(int argc,char * argv[])
{
//为防止被视为无效代码,将每条运算作为printf参数使用
//变量定义
int nVarOne=argc;
int nVarTwo=argc;
//两个变量做除法
printf("nVarOne/nVarTwo=%d\n",nVarOne/nVarTwo);
//变量除以常量,常量位2的1次方
printf("nVarOne/2=%d\n",nVarOne/2);
//变量除以非2的幂
printf("nVarTwo/7=%d\n",nVarTwo/7);
return 0;
}

printf(“nVarOne/nVarTwo=%d\n”,nVarOne/nVarTwo);

1
2
3
4
5
6
00401645    8B4424 1C       mov eax,dword ptr ss:[esp+0x1C]              ; 取出变量nVarOne的数据放入eax中
00401649 99 cdq ; 将eax的符号位扩展到edx中
0040164A F77C24 18 idiv dword ptr ss:[esp+0x18] ; 直接调用idiv进行除法运算
0040164E 894424 04 mov dword ptr ss:[esp+0x4],eax ; 传入参数
00401652 C70424 45904000 mov dword ptr ss:[esp],1.00409045 ; ASCII "nVarOne/nVarTwo=%d\n"
00401659 E8 A2FFFFFF call 1.00401600 ; 调用printf

两变量相除直接使用idiv进行除法计算。
接下来开始玄学了。

printf(“nVarOne/2=%d\n”,nVarOne/2);

1
2
3
4
5
6
7
8
0040165E    8B4424 1C       mov eax,dword ptr ss:[esp+0x1C]              ; 取出nVarOne的数据放入eax中
00401662 89C2 mov edx,eax ; 把eax的数据放入edx中
00401664 C1EA 1F shr edx,0x1F ; edx右移31位,即取出变量nVarOne的符号位
00401667 01D0 add eax,edx ; 自身加上符号位
00401669 D1F8 sar eax,1 ; 带符号右移1位,即除以2
0040166B 894424 04 mov dword ptr ss:[esp+0x4],eax ; 传入参数
0040166F C70424 59904000 mov dword ptr ss:[esp],1.00409059 ; ASCII "nVarOne/2=%d\n"
00401676 E8 85FFFFFF call 1.00401600 ; 调用printf

00401667地址处的指令add eax,edx,edx的值为eax的符号位。实际上就是被除数为负数的情况下,由于位移运算等价于向下取值,C++的除法是向零取整,因此需要对商为负的情况做加1调整,即加上符号位。若为正数则等于没处理。最后sar右移完成除法。这样的设计可以有效避免分支结构的产生。
怎么样是不是感觉开始玄学了起来,接下来除以7更加的玄学。

printf(“nVarTwo/7=%d\n”,nVarTwo/7);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
0040167B    8B4C24 18       mov ecx,dword ptr ss:[esp+0x18]              ; 取出变量nVarTwo的值
0040167F BA 93244992 mov edx,0x92492493
00401684 89C8 mov eax,ecx
00401686 F7EA imul edx ; edx:eax=eax*edx
00401688 8D040A lea eax,dword ptr ds:[edx+ecx] ; eax=edx+ecx
0040168B C1F8 02 sar eax,0x2
0040168E 89C2 mov edx,eax
00401690 89C8 mov eax,ecx
00401692 C1F8 1F sar eax,0x1F
00401695 29C2 sub edx,eax
00401697 89D0 mov eax,edx
00401699 894424 04 mov dword ptr ss:[esp+0x4],eax
0040169D C70424 67904000 mov dword ptr ss:[esp],1.00409067 ; ASCII "nVarTwo/7=%d\n"
004016A4 E8 57FFFFFF call 1.00401600

imul的乘法指令完成后高4字节放入edx,低四字节放入eax,故直接使用edx相当于把计算结果右移32位。
00401688地址处的edx+ecx是对符号位的特殊处理。
0040168E ~ 00401695均是对符号位的处理。
我们忽略符号的处理,以上代码可以转换成
((nVarTwo*92492493h)>>32)/4=nVarTwo/(2^34/92492493h)=nVarTwo/6.999999997962732≈nVarTwo/7
我们把92492493h叫做MagicNumber。
当遇到一下指令序列时,基本可以判断是除法优化后的代码

1
2
3
4
5
6
7
8
mov eax,MagicNumber(大于7fffffffh)
imul reg
add edx,reg
sar edx, ...
mov reg,edx
shr reg,1Fh
add edx,reg
;此后直接使用edx的值

除法优化后的代码可以说是非常的玄学了,在实际分析过程中通常借助IDA的F5插件直接进行还原。另外,以上的指令序列也有多个原形,但有一个共同点——都有MagicNumber。

算术结果溢出

int类型的数据0xFFFFFFFF加2得到的结果将会超出int类型的储存范围,超出的部分也称为溢出数据。溢出数据无法被保存,将会丢失。对于有符号数而言,原数据为一个负数,溢出后由于表示符号的最高位被进位,原来的1变成0,这是负数也相应地成为了正数。
溢出是由于数据进位后超出数据的保存范围导致的。溢出和进位都表示数据超出了存储范围,它们之间又有什么区别呢?

  • 进位
    无符号数超出存储范围叫做进位。因为没有符号位,不会破坏数据,而多处的1位数据会被进位标志位CF保存,数据产生了进位,只是进位后的1位数据1不在自身的存储空间中,而是在标志位CF中。可通过查看进位标志位CF,检查数据是否进位。
  • 溢出
    有符号数超出存储范围叫做溢出,由于数据进位,从而破坏了有符号数的最高位——符号位。只有有符号数才有符号位,所以溢出只针对有符号数。可查看溢出标志位OF,检查数据是否溢出。OF的判定规则很简单,如果参与加法计算的数值符号一直,而计算结果符号不同,则判定OF成立,其他都不成立。

自增和自减

C++中使用“++”、“—”来实现自增和自减操作。自增和自减有两种定义,一种为自增自减运算符在语句块之后,则先执行语句块,再执行自增自减;另一种恰恰相反,自增自减运算符在语句块之前,则先执行自增和自减,再执行语句块。通常,自增和自减是被拆分成两条汇编指令执行的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
using namespace std;
int main(int argc,char * argv[])
{
//为防止被视为无效代码,将每条运算作为printf参数使用
//变量定义
int nVarOne=argc;
int nVarTwo=argc;
//变量后缀自增参与表达式运算
nVarTwo=5+(nVarOne++);
//变量前缀自增参与表达式运算
nVarTwo=5+(++nVarOne);

//变量后缀自减参与表达式运算
nVarOne=5+(nVarTwo--);
//变量前缀自减参与表达式运算
nVarOne=5+(--nVarTwo);
return 0;
}

nVarTwo=5+(nVarOne++);

1
2
3
4
5
0040161C    8B4424 0C       mov eax,dword ptr ss:[esp+0xC]           ; 取出变量nVarOne保存在eax中
00401620 8D50 01 lea edx,dword ptr ds:[eax+0x1] ; 利用取址,计算edx=eax+0x1
00401623 895424 0C mov dword ptr ss:[esp+0xC],edx ; 把edx保存在nVarOne中
00401627 83C0 05 add eax,0x5 ; eax加上5
0040162A 894424 08 mov dword ptr ss:[esp+0x8],eax ; 把eax保存进nVarTwo中

nVarTwo=5+(++nVarOne);

1
2
3
4
0040162E    834424 0C 01    add dword ptr ss:[esp+0xC],0x1           ; 在nVarOne加上1
00401633 8B4424 0C mov eax,dword ptr ss:[esp+0xC] ; 取出nVarOne的数据放入eax中
00401637 83C0 05 add eax,0x5 ; eax加上5
0040163A 894424 08 mov dword ptr ss:[esp+0x8],eax ; eax的数据放入nVarTwo中

nVarOne=5+(nVarTwo- -);

1
2
3
4
5
0040163E    8B4424 08       mov eax,dword ptr ss:[esp+0x8]           ; 取出nVarTwo的数据放入eax中
00401642 8D50 FF lea edx,dword ptr ds:[eax-0x1] ; 利用取址,计算edx=eax-0x1
00401645 895424 08 mov dword ptr ss:[esp+0x8],edx ; 把edx的值放入nVarTwo中
00401649 83C0 05 add eax,0x5 ; 在eax加上0x5
0040164C 894424 0C mov dword ptr ss:[esp+0xC],eax ; 把eax保存进nVarOne中

nVarOne=5+(- -nVarTwo);

1
2
3
4
00401650    836C24 08 01    sub dword ptr ss:[esp+0x8],0x1           ; 在nVarTwo减去1
00401655 8B4424 08 mov eax,dword ptr ss:[esp+0x8] ; 取出nVarTwo的数据放入eax中
00401659 83C0 05 add eax,0x5 ; 在eax加上0x5
0040165C 894424 0C mov dword ptr ss:[esp+0xC],eax ; 把eax的数据放入nVarOne中

从代码可以看出C++先将自增和自减运算进行分离,然后根据运算符的位置来决定执行顺序。将原语句块“nVarTwo=5+(nVarOne++);”分解为“nVarTwo=5+nVarOne;”和“nVarOne+=1;”,这样就实现了先参与语句块运算,再自增1。同理,前缀++的拆分过程只是执行顺序做了替换,先将自身加1,再参与表达式运算。

关系运算和逻辑运算

关系运算用于判断两者之间的关系,如等于、不等于、大于等于、小于等于、大于和小于,对应的符号分别为“==”、“!=”、“>=”、“<=”、“>”、“<”。关系运算的作用是比较关系运算符左右两边的操作数的值,得出一个判断结果:真或假。
逻辑运算符用于判断两个逻辑值之间的依赖关系,如或、与、非,对应的符号有“||”、“&&”、“!”。逻辑运算也是可以组合的,执行顺序和关系运算相同。

  1. 或运算:比较运算符||左右的语句的结果,如果有一个值为真,则返回真值;如果都为假,则返回假值。
  2. 与运算:比较运算符&&左右的语句的结果,如果有一个值为假,则返回假值;如果都是真值,则返回真值。
  3. 非运算:改变运算符!后面的语句真假结果,如果该语句的结果为真值,则返回假值;如果为假值,则返回真值。

关系运算和条件跳转的对应

在C++中,可以利用各种类型的跳转来实现两者间的比较关系,根据比较结果所影响到的标记位来选择对应的条件跳转指令。如何选择条件跳转指令,需要根据两个进行比较的数值所使用到的关系运算,不同的关系运算对应的条件跳转指令也不相同。各种关系对应的条件跳转指令如表所示。

指令助记符 检查标记位 说 明
JZ ZF==1 等于0则跳转
JE ZF==1 相等则跳转
JNZ ZF==0 不等于0则跳转
JNE ZF==0 不相等则跳转
JS SF==1 符号为负则跳转
JNS SF==0 符号为正则跳转
JP/JPE PF==1 “1”的个数为偶数则跳转
JNP/JPO PF==0 “1”的个数为奇数则跳转
JO OF==1 溢出则跳转
JNO OF==0 无溢出则跳转
JC CF==1 进位则跳转
JB CF==1 小于则跳转
JNAE CF==1 不大于等于则跳转
JNC CF==0 无进位则跳转
JNB CF==0 不小于则跳转
JAE CF==0 大于则跳转
JBE CF==1 或 ZF==1 小于等于则跳转
JNA CF==1 或 ZF==1 不大于则跳转
JNBE CF==0 或 ZF==0 不小于等于则跳转
JA CF==0 或 ZF==0 大于则跳转
JL SF!=OF 小于则跳转
JNGE SF!=OF 不大于等于则跳转
JNL SF==OF 不小于则跳转
JGE SF==OF 大于等于则跳转
JLE ZF!=OF 或 ZF==1 小于等于则跳转
JNG ZF!=OF 或 ZF==1 不大于则跳转
JNLE SF==OF 且 ZF==0 不小于等于则跳转
JG SF==OF 且 ZF==0 大于则跳转

在通常情况下,这些条件跳转指令都与CMP和TEST匹配出现,但条件跳转指令检查的是标记位。因此,在有修改标记位的代码处,也可以根据需要使用条件跳转指令来修改程序流程。

表达式短路

表达式短路通过逻辑与运算和逻辑或运算使语句根据条件在执行时发生中断,从而不予执行后面的语句。如何利用表达式短路来实现语句中断呢?根据逻辑与和逻辑或运算特性,如果是与运算,当运算符左边的语句块为假时,则直接返回假值,不执行右边的语句;如果是或运算,当运算符左边的语句块为真值时,直接返回真值,不执行右边的语句块。
利用表达式短路实现用递归方式计算累加和

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<iostream>
using namespace std;
int Accumulation(int number)
{
number && (number += Accumulation(number-1));
return number;
}
int main(int argc,char * argv[])
{
int n=Accumulation(100);
printf("%d",n);
return 0;
}

找到函数Accumulation

number && (number += Accumulation(number-1));

1
2
3
4
5
6
7
8
0040162F    837D 08 00      cmp dword ptr ss:[ebp+0x8],0x0           ; 这里为短路模式汇编代码,比较变量number是否等于0
00401633 74 15 je short 1.0040164A ; 通过JE跳转,检查ZF标志位等于1跳转
00401635 8B45 08 mov eax,dword ptr ss:[ebp+0x8] ; 跳转失败进入递归调用
00401638 83E8 01 sub eax,0x1 ; 对变量number-1后,结果作为参数压栈
0040163B 890424 mov dword ptr ss:[esp],eax
0040163E E8 E6FFFFFF call 1.00401629 ; 继续调用自己,形成递归
00401643 0145 08 add dword ptr ss:[ebp+0x8],eax ; 在number上加上,递归调用的返回值
00401646 837D 08 00 cmp dword ptr ss:[ebp+0x8],0x0 ; 比较变量number是否等于0

return number;

1
2
3
0040164A    8B45 08         mov eax,dword ptr ss:[ebp+0x8]           ; 返回变量number
0040164D C9 leave ; 平衡堆栈
0040164E C3 retn ; 返回

通过递归函数Accumulation完成了整数累加和计算。在递归函数的构成中,必须要有一个出口,本示例中选择了逻辑运算“&&”来制造递归函数的出口。通过使用CMP指令来检查运算符左边的语句是否为假值,根据跳转指令JE来决定是否跳过程序流程。当变量number为0时(即,假),JE跳转成功,跳过递归函数调用,程序流程将会执行到 出口return处。
逻辑运算“||”虽然与逻辑运算“&&”有些不同,但它们的构成原理相同,只需稍作修改就可以解决这一类问题。修改以上代码,讲逻辑与运算改成逻辑或运算来实现表达式短路。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<iostream>
using namespace std;
int Accumulation(int number)
{
(number==0)||(number+=Accumulation(number-1));
return number;
}
int main(int argc,char * argv[])
{
int n=Accumulation(100);
printf("%d",n);
return 0;
}

生成的反汇编代码与使用逻辑与是意一样的。虽然使用的逻辑运算符不同,但在两种情况下,运算符左边的语句块都是在与0值作比较,而且判定的结果等于0时不执行运算符右边的语句块,因此就变成了相同的汇编代码。
转换成汇编代码后,通过比较后跳转来实现短路,这次结构实际上就是分支结构。在反汇编代码中是没有表达式短路的,我们能够看到的都是分支结构。

条件表达式

条件表达式也称三目运算,根据比较表达式1得到的结果进行选择。如果是真值,选择表达式2;如果是假值,选择表达式3.语句的构成如下:

**表达式1?表达式2:表达式3**

条件表达式也属于表达式的一种,所以表达式1、表达式2、表达式3都可以套用到条件表达式中。条件表达式被套用后,其执行顺序依然是由左到右,自内向外。
条件表达式的构成应该是先判断再选择。但是,编译器并不一定会按照这种方式进行编译,当表达式2与表达式3都为常量时,表达式可以被优化;而当表达式2或表达式3中的一个为变量时,条件表达式不可以被优化,会转换成分支结构。当表达式1为一个常量值时,编译器会在编译期间得到答案,将不会有条件表达式存在。编译器优化分为以下几种方案。

  • 方案1:表达式1为简单比较,而表达式2和表达式3两者的差值等于1。
  • 方案2:表达式1为简单比较,而表达式2和表达式3两者的差值大于1。
  • 方案3:表达式1为复杂比较,而表达式2和表达式3两者的差值大于1。
  • 方案4:表达式2和表达式3有一个为常量,于是无优化。

这里不再做详细讨论。

位运算

  • “<<”:左移运算,最高位左移到CF中,最低位补零。
  • “>>”:右移运算,最高位不变,最低位右移到CF中。
  • “|”:位或运算,在两个数的相同位上,只要有一个为1,则结果为1。
  • “&”:位与运算,在两个数的相同位上,只有同时为1,结果才为1。
  • “^”:异或运算,在两个数的相同位上,当两个值相同时为0,不相同时为1。
  • “~”:取反运算,将操作数每一位上的0变成1,1变成0。

位运算在程序算法中被大量使用,如不可逆算法MD5,就是通过大量位运算来完成的。如何使一个数不可逆转呢?利用位运算就可以达到目的,如X&0=结果为0,而根据结果,是不可以逆推X的。由于大多数位运算会导致数据信息丢失(取反~和异或^可以反推),因此,在知道原算法的前提下,使用逆转算法是无法计算出原数据的。在算术运算中,编译器会将各种运算转换成位运算,因此掌握位运算对于算法识别是一件非常重要的事。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
using namespace std;
int main(int argc,char * argv[])
{
//将变量argc左移3位
argc=argc<<3;
//将变量argc右移5位
argc=argc>>5;
//将变量argc与0xFFFF0000做位与运算
argc=argc | 0xFFFF0000;
//将变量argc与0x0000FFFF做位或运算
argc=argc & 0x0000FFFF;
//将变量argc与0xFFFF0000做异或运算
argc=argc ^ 0xFFFF0000;
//将变量argc按位取反
argc=~argc;
//返回argc
return argc;
}

argc=argc<<3;

1
0040160B    C165 08 03      shl dword ptr ss:[ebp+0x8],0x3           ; 左移运算对于汇编指令shl

argc=argc>>5;

1
0040160F    C17D 08 05      sar dword ptr ss:[ebp+0x8],0x5           ; 右移运算对于汇编指令sar

argc=argc | 0xFFFF0000;

1
2
3
00401613    8B45 08         mov eax,dword ptr ss:[ebp+0x8]           
00401616 0D 0000FFFF or eax,0xFFFF0000 ; 位或运算对应汇编指令or,变量低16位不变,高16位设置为1
0040161B 8945 08 mov dword ptr ss:[ebp+0x8],eax

argc=argc & 0x0000FFFF;

1
0040161E    8165 08 FFFF000>and dword ptr ss:[ebp+0x8],0xFFFF        ; 位与运算对应汇编指令and,变量低16位清0,高位不变

argc=argc ^ 0xFFFF0000;

1
2
3
00401625    8B45 08         mov eax,dword ptr ss:[ebp+0x8]           
00401628 35 0000FFFF xor eax,0xFFFF0000 ; 异或运算对应汇编指令xor
0040162D 8945 08 mov dword ptr ss:[ebp+0x8],eax

argc=~argc;

1
00401630    F755 08         not dword ptr ss:[ebp+0x8]               ; 取反运算对应汇编指令not

return argc;

1
2
3
00401633    8B45 08         mov eax,dword ptr ss:[ebp+0x8]           ; 把argc的数据放入eax中作为返回值
00401636 C9 leave ; 堆栈平衡
00401637 C3 retn ; 返回

1
2
3
4
5
6
7
8
9
#include<iostream>
using namespace std;
int main(int argc,char * argv[])
{
unsigned int nVar=argc;
nVar<<=3;
nVar>>=5;
return 0;
}

nVar<<=3;

1
00401615    C16424 0C 03    shl dword ptr ss:[esp+0xC],0x3           ; 和有符号数左移一样

nVar>>=5;

1
0040161A    C16C24 0C 05    shr dword ptr ss:[esp+0xC],0x5           ; 使用shr进行右位移,最高位补0,最低位进CF

在之前代码中,对于左移运算而言,无符号数和有符号数的位移操作是一样的,都不需要考虑到符号位。但右移运算则有变化,有符号数对于的指令为sar,可以保留符号位;无符号数不需要符号位,所以直接使用shr将最高位补0。

编译器使用的优化技巧

所谓代码优化,是指为了达到某一种优化目的对程序代码进行变换。这样的变换有一个原则:变换前和变换后等价(不改变程序的运行结果)。
就优化目的而论,代码优化一般有四个方向:

  • 执行速度优化
  • 内存存储空间优化
  • 磁盘存储空间优化
  • 编译时间优化

常见的与设备无关的优化方案有以下几种。

  • 常量折叠

示例如下:
x=1+2;
1和2都是常量,结果可以预见。必然是3,因此没必要产生加法指令,直接生成x=3;即可

  • 常量传播

接上例,其后代码为y=x+3;由于上例最后生成了x=3;,其结果还是可以预见的,所以直接生成y=6;即可。

  • 减少变量

示例如下:
x=i*2;
y=j*2;
if(x>y) //其后再也没有引用x,y
{

}
这时对x,y的比较等价于对i,j的比较,可以去掉x,y,直接生成if(i>j)。

  • 公共表达式

示例如下:
x=i*2;
y=i*2;
这时i*2被称为公共表达式,可以归并为一个,如下:
x=i*2;
y=x;

  • 复写传播

类似于常量传播,但是目标变成了变量,示例如下:
x=a;

y=x+c;
如果省略号表示的代码中没有修改变量x,则可以直接用变量a代替x:
y=a+c;

  • 剪去不可达分支(剪支优化)

示例如下:
if(1>2) //条件永远为假
{

}
由于if作用域内的代码内容永远不可能被执行,因此整个if代码块没有存在的理由。

  • 顺序语句替代分支

参考之前乘法对符号位的处理。

  • 强度削弱

用加法指令或位移指令替代乘法,用乘法或位移代替除法。参考之前乘法和除法的优化。

  • 数学变化

以下表达式都是代数恒等式:
x=a+0;
x=a-0;
x=a*1;
x=a/1;
因此,不会产生运算指令,直接输入x=a;即可。
下面这个表达式稍微复杂点:
x=a*y+b*y; //等价于x=(a+b)*y;
这样只需一次加法一次乘法即可。

  • 代码外提

这类优化一般存在于循环中,如下面代码所示:
while(x>y/2)
{
… //循环体内没有修改y值
}
以上代码不必在每次判定循环条件时都做一次除法,可以进行如下优化:
t=y/2;
while(x>t)
{

}
在实际分析中,可能会组合应用以上优化方案。应先建立优化概念,遇到各类方案的组合时用心琢磨体会即可。

文章目录
  1. 1. 算术运算和赋值
    1. 1.1. 各种算术运算的工作形式
      1. 1.1.1. 加法
      2. 1.1.2. 减法
      3. 1.1.3. 乘法
      4. 1.1.4. 除法
    2. 1.2. 算术结果溢出
    3. 1.3. 自增和自减
  2. 2. 关系运算和逻辑运算
    1. 2.1. 关系运算和条件跳转的对应
    2. 2.2. 表达式短路
    3. 2.3. 条件表达式
  3. 3. 位运算
  4. 4. 编译器使用的优化技巧