C++反汇编与逆向分析技术(二)

发表于 | 更新于: | 分类于 | |

记录一下《C++反汇编与逆向分析技术》(二)

第四章 各种表达式的求值过程

单独的算术运算虽然可以编译通过，但是并不会生成代码。因为只进行计算而没有传递结果的运算不会对程序结果有任何影响，此时编译器将其视为无效语句，与空语句等价，不会有任何编译处理

加法

VC++ 6.0有两种常用的优化方案

  • O1方案，生成文件占用空间最小
  • O2方案，执行效率最快

在VC++ 6.0中，Release编译选项组的默认选项为O2选项，在Debug编译选项组中，使用的是Od+ZI选项，此选项使编译器产生的一切代码都以便于调试为最根本的前提，甚至为了便于单步调试，以及源码和目标代码块的对应阅读 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//C++源码说明：加法运算
//无效语句，不参与编译
15+20

//变量定义
int nVarOne = 0;
int nVarTwo = 0;

//变量加常量的加法运算
nVarOne = nVarOne + 1;

//两个常量加法的加法运算
nVarOne = 1 + 2;

//两个变量相加的加法运算
nVarOne = nVarOne + nVarTwo
printf("nVarOne = %d \r\n", nVarOne);

//C++源码与对应汇编代码

//C++源码对比，变量赋值
int nVarOne = 0;

//将立即数0，传入地址ebp-0x4中，即变量nVarOne所在的地址
00401028 mov dword ptr [ebp-4],0

//C++源码对比，变量赋值
int nVarTwo = 0;
0040102F mov dword ptr [ebp-8],0

//C++源码对比，变量 + 常量
nVarOne = nVarOne + 1;

//取出变量nVarOne数据放入eax中
00401036 mov eax,dword ptr [ebp-4]

//对eax执行加等于1运算
00401039 add eax,1

//将结果返回变量nVarOne中，完成加法运算
0040103C mov dword ptr [ebp-4],eax

//C++源码对比，常量 + 常量
nVarOne = 1 + 2;

//这里编译器直接计算出了两个常量相加后的结构，放入变量nVarOne中
0040103F mov dword ptr [ebp-4],3

//C++源码对比，变量 + 变量
nVarOne = nVarOne + nVarTwo;

//使用ecx存放变量nVarOne
00401046 mov ecx,dword ptr [ebp-4]

//使用ecx对变量nVarTwo执行加等于操作
00401049 add ecx,dword ptr [ebp-8]

//将结果存入地址ebp-4处，即变量nVarOne
0040104C mov dword ptr [ebp-4],ecx

由上方代码可得：

  • 在两常量相加的情况下，编译器在编译期间就计算出两常量相加后的结果，将这个结果值作为立即数参与运算，减少了程序在运行期的计算
  • 当有变量参与加法运算时，会先取出内存中的数据，放入通用寄存器中，再通过加法指令来完成计算过程得到结果，最后存回到变量所占用的内存空间中

在开启O2选项后，编译出来的汇编代码会由于效率优先的编译选项而发生很大变化，编译器会将无用代码去除，并将可合并代码进行归并处理。例如，在代码清单4-1中，“nVarOne =
nVarOne+1;”这样的代码将被删除，因为在其后又重新对变量nVarOne进行了赋值操作，而在此之前没有对变量nVarOne的任何访问，所以编译器判定此句代码是可被删除的

O2选项后Release版代码如下： 

1
2
3
4
5
6
7
8
9
; int _cdecl main(int argc, const char **argu, const char **enup)
__main proc near
push    3
push    offset format   ;"nVarOne = %d \r\n"
call    __printf
add     esp,8
xor     eax,eax
retn
__main endp
  • 常量传播
1
2
3
4
void main(){
    int nVar = 1;
    printf("nVarOne = %d  \r\n", nVar);
}

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

1
2
3
void main(){
    printf {"nVarOne = %d \r\n"，1) ;
}
  • 常量折叠

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

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

在这串算式被编译后会直接转化成常量-12，即”int nVar = -12;”

在给出的加法代码中，变量nVarOne和nVarTwo的初始化值是-一个常量， VC++编译器在开启02优化方案后，会尝试使用常量替换掉变量。如果在程序的逻辑中，声明的变量没有被修改过，而且上下文中不存在针对此变量的取地址和间接访问操作，那么这个变量也就等价于常量，编译器就认为可以删除掉这个变量，直接用常量代替。使用常量的好处是可以生成立即数寻址的目标代码，常量作为立即数成为指令的一-部分，从而减少了内存的访问次数 

1
2
3
4
5
6
7
8
9
10
int nVarOne = 0;    //常量化以后: int nVarOne = 0; nVarOne 用0代替了
int nVarTwo = 0;    // int nVarTwo = 0; 同上，这句也没有了

//变量加常量的加法运算
nVarOne = nVarOne + 1;      //nVarOne=0+1;

//两常量相加的加法运算
nVarOne = 1 + 2;    //nVarOne=1+2;
nVarOne = nVarOne + nVarTwO;    // nVarOne = nVarOne + 0;
printf ("nVarOne = %d \r\n", nVarOne);

经过转化后，直接变成”printf(“nVarOne = %d \r\n”);”
将代码修改为： 

1
2
3
4
5
6
7
8
9
10
int main(int argc, char* argv[]) {
    int nVarOne = argc;      //修改处
    int nVarTwo = argc;      //修改处

    nVarOne = nVarOne + 1 ;
    nVarOne = 1 + 2;
    nVarOne = nVarOne + nVarTwo;
    printf {"nVarOne = %d \r\n"， nVarOne) ;
    return 0;
}

这里初始化nVarOne和nVarTwo的时候用命令行参数argc，故在编译期间无法确定，程序中的变量就不会被常量替换掉，汇编代码为 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
; int_ cdec1 main(int argc, const char **argu, const char **envp)
__main proc near  

arg_0 = dword ptr 4

mov  eax, [esp+arg_0]
add  eax, 3  
push  eax  
push  offset Format     ; "nVarOne = 0 \r\n"

call  printf
add  esp,8
xor  eax, eax
retn

__main endp

这里还是被删除了一个变量，优化过程如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int main(int argc, char* argv[]) {
    // int nVarOne = argc;在后面的代码中被常量代替
    // int nVarTwo = argc;虽然不能用常量代替，但是由于之后没有对nVarTwo进行修改，所以引用nVarTwo等价于引用argc, nVarTwo 则被删除掉，这种方法称为”复写传播”

    // nVarOne = nVarOne + 1;其后即刻重新对nVarOne赋值，这句被删除了
    // nVarOne = 1+2;常量折叠，等价于nVarOne=3;

    // nVarOne = nVarOne + nVarTwo; 常量传播和复写传播，等价于nVarOne = 3 + argc ;
    // printf ("nVarOne = %d \r\n", nVarOne) ;

    //其后nVar0ne没有被访问，可以用3 + argc代替
    printf ("nVarOne = %d \r\n", 3 + argc) ;

    return 0;
}

减法

减法运算对应于汇编指令sub，计算机是通过补码将减法转变为加法形式来完成转换，有公式

设有二进制数Y，其反码记为Y(反)，假定其二进制长度为8位，有:

  • Y + Y(反) = 1111 1111B
  • Y + Y(反) + 1 = 0(进位丢失)

根据以上两点，可推出

  • Y(反) + 1 = 0 - Y<==>Y(反) + 1 = -Y <==> Y(补} = -Y 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//C++源码说明：减法运算
//变量定义
int nVarOne = argc;
int nVarTwo = 0;

//获取变量nVarTwo的数据，使用scanf防止被常量化
scanf("%d",&nVarTwo);

//变量减常量的减法运算
nVarOne = nVarOne - 100;

//减法与加法混合运算
nVarOne = nVarOne + 5 - nVarTwo;
printf("nVarOne = %d \r\n",nVarOne);

//C++源码对应汇编代码讲解
//C++源码对比，变量 - 常量
nVarOne = nVarOne - 100;

//取变量nVarOne的数据到eax中
00401125	mov	eax,dword ptr [ebp-4]

//是用减法指令sub，对eax执行减等于100操作
00401128	sub	eax,64h

//将结果赋值回nVarOne中
0040112B	mov dword ptr [ebp-4],eax

//C++源码对比，减法与加法混合运算
nVarOne = nVarOne +5 - nVarTwo;

//按照自左向右顺序依次执行
0040112E	mov	ecx,dword ptr [ebp-4]
00401131	add	ecx,5
00401134	sub	ecx,dword ptr [ebp-8]
00401137	mov	dword ptr [ebp-4],ecx
//printf函数调用显示略

Release与加法相同，就不赘述了

乘法

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

乘法转换——Debug版 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//C++源码说明，乘法运算
//防止被视为无效代码，将每条运算作为printf参数使用
//变量定义
int nVarOne = argc;
int nVarTwo = argc;

//变量乘常量(常量为非2的幂)
printf("nVarOne*15 = %d \r\n",nVarOne * 15);

//变量乘常量(常量值为2的幂)
printf("nVarOne*16 = %d",nVarOne * 16);

//两常量相乘
printf("2*2 = %d",2 * 2);

//混合运算
printf("nVarTwo *4 +5 = %d",nVarTwo * 4 + 5);

//两变量相乘
printf("nVarOne * nVarTwo = %d",nVarOne * nVarTwo);

//C++源码对应汇编
//C++源码对比，变量 * 常量
printf("nVarOne*15 = %d \r\n",nVarOne * 15);
0040B8A4	mov	edx,dword ptr [ebp-4]
//直接使用有符号乘法指令imul
0040B8A7	imul	edx,edx,0Fh

//C++源码对比 常量*常量(常量值为2的幂)
printf("nVarOne*16 = %d",nVarOne * 16)
0040B8B8	mov	eax,dword ptr [ebp-4]
//使用左移运算代替乘法运算
0040B8BB	shl	eax,4

//C++源码对比，常量*常量
printf("2*2 = %d",2 * 2);
//在编译期间计算出2*2的结果，将表达式转换为常量值
0040B8CC	push 4
0040B8CE	push offest string "2 * 2 = %d"(0041ffac)
0040B8D3	call printf(0040B750)
0040B8D8	add esp,8

//c++源码对比，变量*常量+常量(组合运算)
printf("nVarTwo *4 +5 = %d",nVarTwo * 4 + 5);
0040B8DB	mov	ecx,dword ptr [ebp-8]
//利用lea指令完成组合运算
0040B8DE	lea	edx,[ecx*4+5]

//c++源码对比，变量*变量
printf("nVarOne * nVarTwo = %d",nVarOne * nVarTwo);
0040B90A	mov	ecx,dword ptr [ebp-4]
//直接使用有符号乘法指令
0040B90D	imul ecx,dword ptr [ebp-8]

代码使用编译选项为Od+ZI。在这种侧重调试的编译方式下，有符号数乘以常量值，且这个常量非2的幂，会直接使用有符号乘法imul指令。当常量值为2的幂时，编译器会采用执行周期短的左移运算来代替执行周期长的乘法指令,而若乘数不等于2的幂次方，则会先拆分后用imul指令进行编译

各类型的乘法转换示例——Release版 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
    //IDA直接将参数作为局部变量使用
arg_0 = dword ptr 4  

//保存环境
push esi
//取出参数变量存入esi中
mov esi,[esp+4+arg_0]
//经过优化后，将nVarOne*15先转化为 乘2加自身，相当于乘3
//eax = esi*2+esi = 3*esi
lea	eax,[esi+esi*2]

//将上一步操作结果乘4加自身，等同于乘15
//eax = eax * 4 + eax = 5 * eax = 5 * (3*esi)
lea	eax,[eax+eax*4]
push eax
push offset aNvaronel15D; "nVarOne * 15 = %d"
call _printf

// esi中的数据传送到ecx，esi中保存的为参数数据
mov	ecx,esi
//将ecx中的数据左移4为，ecx乘以2^4
shl	ecx,4
push ecx
push offset aNvarone15D; "nVarOne * 16 = %d"
call _printf

//两常量相乘直接转换常量值
push 4
push offset a22D;	"2*2 = %d"
call _printf
//这句话等等同于lea edx,[esi*4+5]都是混合运算
lea	edx,ds:5[esi*4]
push edx
push offset aNvartwo45D;	"nVarTwo * 4 +5 =%d"
call _printf

//此处为乘数不等于2 4 8 情况，编译优化9进行分解：(nVarTwo*1+nVarTwo*8),这样就可以使用lea了
lea eax,[esi+esi*8+5]
push eax
push _offset aNvartwo95D;	"nVarTwo * 9 +5 =%d"
call _printf
//此处为两个变量相乘，都是未知数，无忧化
mov	ecx,esi
imul ecx,esi
push ecx
push offest aNvaroneNvartwo;	"nVarOne * nVarTwo = %d"
call _printf
add	esp,30h
pop	esi

除法

  • 向下取整：所谓对x向下取整，就是取得往-∞方向最接近x的整数值，换而言之也就是取得不大于x的最大整数

在标准C语言的math.h中，定义了floor函数，其作用就是向下取整，也有人称之为“地板取整”

  • 向上取整：所谓对x向上取整，就是取得往+∞方向最接近x的整数值，换而言之也就是取得不小于x的最小整数

在标准C语言的math.h中有定义ceil函数，其作用就是向上取整，也有人称之为“天花板取整”

  • 向0取整：所谓对x向零取整，就是取得往0方向最接近x的整数值，换而言之也就是放弃小数部分

C语言是向0取整

定义

定义

VC++6.0对除数为整型常量的除法会进行优化:如果除数是变量，则只能使用除法指令。如果除数为常量，就有了优化的余地。根据除数值的相关特性，编译器有对应的处理方式。

各类型除法转换——Debug版 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
//C++源码说明：除法运算
//变量定义
int	nVarOne = argc;
int nVarTwo = argc;

//两个变量做除法
printf("nVarOne / nVarTwo = %d", nVarOne / nVarTwo);

//变量除以常量，常量为2的1次方
printf("nVarOne / 2 = %d", nVarOne / 2);

//变量除以非2的幂
printf("nVarTwo / 7 = %d", nVarTwo / 7);

//变量对非2的幂取模
printf("nVarTwo % 7 = %d", nVarTwo % 7);

//变量除以常量，常量为2的3次方
printf("nVarOne / 8 = %d", nVarOne / 8);

//C++源码与对应汇编代码讲解
//C++源码对比，变量定义
int nVarOne = argc;
0040B7E8	mov	eax,dword ptr [ebp+8]
0010B7EB	mov	dword ptr [ebp-4],eax

//C++源码对比，变量定义
int nVarTwo = argc;
0040B7EE	mov	ecx,dword ptr [ebp+8]
0040B7F1	mov	dword ptr [ebp-8],ecx

//除法运算转换特性
//C++源码对比，变量 / 变量
printf("nVarOne / nVarTwo = %d", nVarOne / nVarTwo);

//取出被除数放入eax中
0040B7F4	mov	eax,dword ptr [ebp-4]

//扩展高位(EDX:EAX,这里表示EDX，EAX连用表示64位数 )
0040B7F7	cdq

//两变量相除，直接使用有符号除法指令idiv
0040B7F8	idiv	eax,dword ptr [ebp-8]

//eax保存商值，作为参数压栈，调用函数printf
0040B7FB	push eax
0040B7FC	push offset string "nVarOne / nVarTwo = %d" (00420034)
0040B801	call printf (0040B750)
0040B806	add	esp,8

//C++源码对比，变量 / 常量 (常量值为2的1次方)
printf("nVarOne / 2 = %d", nVarOne / 2);
0040B809	mov	eax,dword ptr [ebp-4]
0040B80C	cdq

//自身减去扩展高位
0040B80D	sub	eax,edx

//和乘法运算类似，乘法是左移
0040B80F	sar	eax,1

//printf函数说明略
//C++源码对比，变量 / 常量 (非2的幂)
printf("nVarTwo / 7 = %d", nVarTwo / 7);
0040B81F	mov eax,dword ptr [ebp-8]
00040B22	cdq
0040B823	mov	ecx,7

//无忧化直接使用有符号除法指令idiv
0040B828	idiv eax,ecx

//printf函数说明略
//C++源码对比，变量 % 常量
printf("nVarTwo % 7 = %d", nVarTwo % 7);
0040B838	mov	eax,dword ptr [ebp-8]
0040B83B	cdq  //执行 CDQ 后， CDQ 把第 31 bit 复制至 EDX 所有 bit
0040B83C	mov ecx,7

//无忧化，直接使用有符号指令idiv
0040B841	idiv eax,ecx

//除法指令过后，余数保存在扩展为edx中
0040B843	push edx

//printf 函数说明略
//C++源码对比，变量 / 常量(常量值为2的3次方)
printf("nVarOne / 8 = %d",nVarOne / 8);

//取出被除数放入eax
0040B851	mov eax,dword ptr [ebp-4]

//扩展eax高位到edx
0040B854	cdq

//如果eax为负数
0040B855	and edx,7

//使用eax加edx，若eax为负数则加7，反之加0
0040B858	add	eax,edx

//将eax右移3位
0040B85A	sar	eax,3
//printf函数说明略

这里只对除数为2的幂的情况进行了优化处理：
这里运用了推导7的结论：(x+(2^n-1)) >> n

除数为2的幂

上述代码中的0040B80C的cdq是符号扩展到高位edx,如果eax的最高位(符号位)为1,那么edx的值为0xFFFFFFFF，也就是-1，否则为0。0040B80D地址处的sub eax,edx指令执行的操作是将eax减去高位edx，实际上就是被除数为负数的情况下，由于除数为正数(+2的幂)，故除法的商为负数。移位运算等价于向下取整，C语言的除法是向零取整，因此需要对商为负的情况做加1调整(见推导7)，减去-1等同于加1。eax不为负则减0，等于没处理。最后sar右移完成除法。这样的设计可以避免分支结构的产生 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//C++源码对比，变量 / 常量(常量值为2的3次方)
printf("nVarOne / 8 = %d",nVarOne / 8);

//取出被除数放入eax
0040B851	mov eax,dword ptr [ebp-4]

//扩展eax高位到edx
0040B854	cdq

//如果eax为负数
0040B855	and edx,7

//使用eax加edx，若eax为负数则加7，反之加0
0040B858	add	eax,edx

//将eax右移3位
0040B85A	sar	eax,3
//printf函数说明略

这里我要记录一下我的犯蠢时刻，计算机里负数的各项计算都是通过补码进行的，所以add eax，edx这句话就不会有问题，基础太差了呜呜

0040B854的cdq是符号扩展到高位edx，在0040B855处对edx做位与运算，当被除数为负数时，edx的值为7，在0040B858处的add eax，edx就是被除数为负数时加上2^n-1，不为负数则加0，最后sar右移完成除法

除数非2的幂
Release版中还对除数不为2的幂的情况做了优化： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//IDA中的参数标识，经过优化后，省去了局部变量，直接使用参数
arg_0 = dword ptr 4
//变量 / 变量 和Debug版相同，此处省略
//......
//变量 / 常量 (常量值为2的幂)和Debug版相同，此处省略
//.....
//变量 / 常量 (常量值为非2的幂)，这里的汇编代码和Debug版的汇编代码差别很大
//将数值 92492493h放到eax中
mov	eax,92492493h
//有符号乘法，用esi乘以eax，esi中保存被除数
imul esi
//edx为扩展的高位
add	edx,esi
//右移2位
sar	edx,2
//结果放回eax
mov	eax,edx
//将eax右移31次
shr	eax，1Fh
//加以右移结果，放入edx中
add	edx,eax
push edx
push offset aNvarTwo7D; "nVarTwo / 7 = %d"
call _printf
//其余代码和Debug版类似，略
//......

由于除法指令的周期比乘法要长出很多，所以release版的除法指令会被乘法和其他指令替代，这里出现了一个大数92492493，给出数学证明

证明

来个例子看一下 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
.text:00401000	_main proc near ; CODE XREF: start+AF p
.text:00401000	arg_0 = dword ptr 4
.text:00401000	mov	ecx,[esp+arg_0]
.text:00401004	mov	eax,38E38E39h
.text:00401000  imul ecx	//ecx乘以参数
.text:0040100B	sar	edx,1	//有符号移位
.text:0040100D	mov eax,edx
.text:0040100F	shr	eax,1Fh	//无符号移位
.text:00401012	add	edx,eax
.text:00401014	push edx
.text:00401015	push offset Format ; "%d"
.text:0040101A	call _printf
.text:0040101F	add esp,8
.text:00401022	retn
.text:00401022_main endp

看到在地址.text: 00401004处，我们看到了mov eax, 38E38E39h，此后做了乘法和移位操作,最后直接使用edx显示。在乘法指令中，由于edx存放乘积数据的高4字节，因此直接使用edx就等价于乘积右移了32位，再算上.text:0040100B sar edx, 1，那就一共移动了33位。在地址.text: 0040100D 处，eax 得到了edx 的值，然后对eax右移了1Fh位，对应10进制也就是右移了31位，然后有个很奇怪的加法。其实这里移位的目的是得到有符号数的符号位，如果结果是正数，add edx, eax就是加0，等于什么都没干;如果结果是负数，由于其后面的代码直接使用edx作为计算结果，需要对除法的商调整加1。简单证明如下:

证明

于是可以推出C代码: 

1
printf("%d",arg/9);

总结: 

1
2
3
4
5
6
7
mov	eax,MagicNumber
imul ...
sar	edx,...
mov	reg,edx
shr	reg,1Fh
add	edx,reg
//之后就直接用edx的值，eax的不用

遇到上面你的指令序列的时候，基本可以判定是除法优化后的代码，除法的原型为a/o，imul是表明的有符号计算，操作数是优前的被除数a，右移的总次数确定n的值，用公式o= 2^n/c，将MagicNumber作为c代入公式求我们的除数o的近似值，四舍五入取整，就可以恢复除法原型！

再来个例子 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
.text:00401080 _main proc near ; CODE xREF: start+AF p
.text:00401080 arg_0 = dword ptr 4
.text:00401080	mov ecx,[esp+arg_0]
.text:00401084	mov eax,24924925h
.text:00401089	mul	ecx
.text:0040108B	sub	ecx,edx
.text:0040108D	shr	ecx,1
.text:0040108F	add	ecx,edx
.text:00401091	shr	ecx,2
.text:00401094	push ecx
.text:00401095	push offset	Format
.text:0040109A	call _printf
.text:0040109F	add	esp,8
.text:004010A2	xor	eax,eax
.text:004010A4	retn
.text:004010A4 _ma in endp

手推：

推导

于是，可以推出代码来: 

1
printf ("nVarTwO / 7 = %d\r\n", argc / 7);

计算得出MagicNumber后，如果其值超出4字节整数的表达范围，编译器会对其进行调整，如上个例子中的argc/7，计算MagicNumber时，编译器选择 2^35/7，其结果超出了4字节整数的表达范围，所以编译器调整MagicNumber的取值为2^35/7-2^32

公式：a/o = [((a-a * c)/2^32)/2 + a * c/2^32]/2^(n-1)

总结： 

1
2
3
4
5
6
7
mov eax,MagicNumber
//reg表示通用寄存器
mul reg
sub	reg,edx
shr	reg,1
add	reg,edx
shr	reg,A	//这句没有，那么n就是1，否则这里就是n-1的值

如果遇到上面的指令序列，基本可以判定出发优化后的代码，其除法原型为a/常量o，mul代表的无符号计算，用公式o = 2^(32+n)/(2^32+c)将MagicNumber作为c值代入公式求解常数除数o，即可恢复除法原型

现在再来看之前的代码 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
; 92492493h疑似 2^n/o
. text:004010AA     mov eax, 92492493h
;这里是流水线优化，esp和上次调用的call指令相关，和除法计算无关，可暂不理会  
;关于流水线优化详见4.4.1小节  
. text:004010AF     add esp,8  

;有符号乘法，用esi乘以eax，esi中保存被除数
. text:004010B2     imul esi

;这里又多出一个诡异的加法
. text:004010B4     add edx, esi

;右移2位，也可看做除4
. text:004010B6     sar edx, 2

;结果给eax
. text:004010B9     mov eax, edx

;负数调整加1
. text:004010BB     shr eax, 1Fh
. text:004010BE     add edx，eax
. text:004010C0     push edx
. text:004010C1     push offset aNvartwo7D ; "nVarTwo / 7 = td" ;
. text:004010C6     ca11 _printf

这段代码在.text:004010B4处的加法显得很奇怪,其实这里的代码是上面介绍的除法转乘法公式的变化。在.text:004010B2处的指令是imul esi,这是个有符号数的乘法。请注意，编译器在计算MagicNumber时是作为无符号处理的，而代入除法转换乘法的代码中又是作为有符号乘数处理的。因为有符号数的最高位不是数值，而是符号位，所以，对应的有符号乘法指令是不会让最高位参与数值计算的，这会导致乘数的数学意义和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的值

当遇到以上指令序列时，基本可判定是除法优化后的代码，其除法原型为a除以常量o,imul表明是有符号计算，其操作数是优化前的被除数a,接下来统计右移的总次数以确定公式中的n值，然后使用公式o=(2^n)/c,将MagicNumber作为c值代入公式求解常量除数o，即可恢复除法原型

  • 除数为负的非2的幂(MagicNumber大于0x7fffffffh)

总结 

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

如果遇到以上指令序列，则基本可判定是除法优化后的代码，其除法原型为a除以常量o, imul可表明是有符号计算，其操作数是优化前的被除数a,由于MagicNumber取值大于7fffffffh，而imul和sar之间未见任何调整代码，故可认定除数为负，且MagicNumber为补码形式。接下来统计右移的总次数以确定公式中的n值，然后使用公式|o|=2^n/((2^32)-c),MagicNumber作为c值代人公式求解常量除数|o|，即可恢复除法原型

  • 除数为负的非2的幂(MagicNumber小于0x7fffffffh)

总结 

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

如果遇到以上指令序列，则基本可判定是除法优化后的代码，其除法原型为a除以常量o, imul可表明是有符号计算，其操作数是优化前的被除数a,由于MagicNumber取值小于7fffffffh，而imul和sar之间未见任何调整代码，故可认定除数为负，且MagicNumber为补码形式。接下来统计右移的总次数以确定公式中的n值，然后使用公式|o|=2^n/((2^32)-c),MagicNumber作为c值代人公式求解常量除数|o|，即可恢复除法原型

  • 除法优化原则

这里我直接copy l0x1c师傅的blog了，没错，👴就是懒狗

先给一些背景：

（1）比如 7 / 2 = 3 …… 1 -7 / 2 = -3 …… -1

比较重要的是，余数的绝对值小于除数的绝对值，并且余数和被除数同正负

（2）由于C语言中除法是向0取整，也就是“截断除法”

不难发现，正数除以正数时，截断除法相当于向下取整（3.5 -> 3）；而负数除以正数时，截断除法相当于向上取整( -3.5 -> -3 )

（3）除以2的k次幂通常会被优化成右移k位，这里考虑除以2时

用一个signed byte表示7，是00000111，右移一位变成00000011是3，是正确的

但是，考虑-7/2，-7是11111001，右移一位后变成11111100，这是-4，因为这是向下取整的结果，所以比正确的答案 -3少了1

代码中为了统一和效率，如果是32位的数字，会先右移31位扩展符号位。原先是正数则最高位是0，那么最后会变成32个0，也就是0,；原先是负数最高位是1，最后会变成32个1，也就是-1，暂且把这个扩展符号位后形成的数记作S,

那么，我们只需要把右移一位的结果，减去这个S，就可以得到正确的截断除法的值

7/2 = 7>>1 – (0) = 3 -7/2 == -7>>1 – (-1) = -3

( 这一点在例题代码中会再次提到 )

（4）当除以正数N，而N不是2的次幂时，编译器会生成一个magic_number（C），以使除法优化成乘法，提高效率

贴一道例题分析

![https://ctftime.org/task/5294?tdsourcetag=s_pcqq_aiomsg]

  • 取模运算 
1
2
3
4
5
6
7
mov reg,被除数
and reg, 8000001F ;这里的立即数是去掉高位保留低位的掩码，其值由2^k决定
jns LAB1
dec reg
or reg, FFFFFFE0
inc reg
LAB1 :

当遇到以上指令序列时，基本可判定是取模代码，其取模原型为被除数(变量)对2^k(常量)执行取模运算，jns 可表明是有符号计算，考察“and reg,8000001F”这类去掉高位保留低位的代码，统计出一共保留了多少低位，即可得到k的值，代入求得2*的值后，可恢复取模代码原型

对于x%(2^k)，有的编译器会得到以下代码: 

1
2
3
4
5
6
7
8
9
;先求x/2^5的商
mov eax，被除数
cdq
and edx, 1F
add eax, edx
sar eax,5;这时eax已经得到了商
;余数=被除数-商*2^5
shl eax,5
sub 被除数，eax ;此时可以得到余数

算术结果溢出

  • 进位
    无符号数超出存储范围叫做进位。因为没有符号位，不会破坏数据，而多出的1位数据会被进位标志位CF保存，数据产生了进位，只是进位后的1位数据1不在自身的存储空间中，而在标志位CF中。可通过查看进位标志位CF,检查数据是否进位

  • 溢出
    有符号数超出存储范围叫做溢出，由于数据进位，从而破坏了有符号数的最高位——符号位。只有有符号数才有符号位，所以溢出只针对有符号数。可查看益出标志位OF,检查数据是否溢出。OF的判定规则很简单，如果参与加法计算的数值符号一致，而计算结果符号不同，则判定OF成立，其他都不成立

自增和自减

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

代码如下 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//自增自减代码
//C++源码说明:除法运算
//变量定义并出初始化
int nvarOne = argc;
int nvarTwo = argc;
//变量后缀自增参与表达式运算
nvarTwo = 5 + (nvarOne++);
//变量前缀自增参与表达式运算
nvarTwo = 5 + (++nvarOne);
//变量后缀自减参与表达式运算
nvarone = 5 + (nvarTwo--);
//变量前缀自减参与表达式运算
nvarone = 5 + (--nvarTwo);

//c++源码对应汇编
//变量对应初始化

//后缀自增运算
nvarTwo = 5 + (nvarTwo++);
//取出变量nvarOne，保存在edx中
0040BA34	mov	edx,dword ptr [ebp-4]
//讲edx执行加等于5
0040BA37	add	edx,5
//讲edx赋值给变量nvarTwo，可以看到没有对变量nvarOne执行自增操作
0040BA3A	mov	dword ptr [ebp-8],edx
//再次取出变量nvarOne数据存入eax中
0040BA3D	mov	eax,dword ptr [ebp-4]
//执行eax加等于1
0040BA40	add	eax,1
将eax赋值给变量nvarOne,等同于对变量nvarOne执行自增1操作
0040BA43	mov	dword ptr [ebp-4],ecx

//c++源码对比，前缀自增运算
nVarTwo = 5 + (++nvarOne);
//取出变量nvarOne数据放入ecx中
0040BA46	mov	ecx,dword ptr [ebp-4]
//对ecx执行加等于1的操作
0040BA49	add	ecx,1
//将ecx赋值给变量nvarOne，完成自增1操作
0040BA4C	mov	dword ptr [ebp-4],ecx
//取出变量nvarOne放到edx中
0040BA4F	mov	edx,dword ptr [ebp-4]
//对edx执行加等于5
0040BA52	add	edx,5
//将结果edx赋值给变量nvarTwo
0040BA55	mov	dword ptr [ebp-8],edx
//自增和自减差不多相同，add替换成sub就可

关系运算和逻辑运算

  • 与运算(&&)
  • 或运算(||)
  • 非运算(!)

各种关系对应的条件跳转指令如表

指令助记符 检查标记位 说明
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 大于则跳转

表达式短路

表达式短路通过逻辑与运算和逻辑或运算使语句根据条件在执行时发生中断，从而不予执行后面的语句。是根据逻辑与和逻辑或运算的特性，如果是与运算，当运算符左边的语句块为假值时，则直接返回假值，不执行右边的语句;如果是或运算，当运算符左边的语句块为真值时，直接返回真值，不执行右边的语句块

汇编代码如下 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//C++源码说明：递归函数，用于计算整数累计，nNumber为累加值
int Accumulation(int nNumber){
//当nNumber等于0时，逻辑与运算符左边的值为假，不会执行右边的语句
//形成表达式短路，从而找到递归出口
nNumber && (nNumber += Accumulation(nNumber - 1));
return nNumber
}

//对应汇编
int Accumulation(int nNumber){
nNumber && (nNumber += Accumulation(nNumber - 1));
//这里为短路模式汇编代码，比较变量nNumber是否等于0
0040BAA8	cmp	dword ptr [ebp+8],0
//通过JE跳转，检查ZF标记位等于1跳转
0040BAAC	je	Accumulation+35h (0040bac5)
//跳转失败，进入递归调用
0040BAAE	mov	eax,dword ptr [ebp+8]
//对变量nNumber减1后，结果作为参数压栈
0040BAB1	sub	eax,1
0040BAB4	push eax
//继续调用自己，形成递归
0040BAB5	call @ILT+30(Accumulation) (00401023)
0040BABA	add esp,4
0040BABD	mov ecx,dword ptr [ebp+8]
0040BAC0	add ecx,eax
0040BAC2	mov dword ptr [ebp+8],ecx
//返回变量nNumber
return nNumber
0040BAC5	mov eax,dword ptr [ebp+8]
}

这个递归函数的出口是逻辑式“&&”的左侧判断。逻辑运算“||”虽然与逻辑运算“&&”有些不同，但它们的构成原理相同，只需稍作修改就可以解决上方代码的问题，代码如下 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//c++源码说明，和上面的类似
int Accumulation (int nNumber){
//当nNumber等于0时，逻辑或运算符的左边如果为真就不执行右边的语句
//形成表达式短路，从而找到递归的出口
(nNumber == 0) || (nNumber += Accumulation(nNumber - 1));
return nNumber;
}
//C++源码与对应汇编代码
int Accumulation(int nNumber){
(nNumber == 0) || (nNumber += Accumulation(nNumber - 1));
00401618	cmp	dword ptr [ebp+8],0
0040161C	je Acumulation+35h (00401635)
0040161E	mov	eax,dword ptr [ebp+8]
00401621	sub	eax,1
00401624	push eax
00401625	call @ILT+30(Accumulation) (00401023)
0040162A	add	esp,4
0040162D	mov ecx,dword ptr [ebp+8]
00401630	add	ecx,eax
00401632	mov	dword ptr [ebp+8],ecx
return nNumber
00401635	mov eax,dword ptr [ebp+8]
}

条件表达式

条件表达式也称为三目运算：
表达式1 ? 表达式2 : 表达式3
这个意思是如果表达式1是真值，则执行表达式2，如果是假值，则执行表达式3

表达式1，2，3都可以套用到条件表达式中。条件表达式被套用后，其执行顺序依然是由左向右，自内向外。当表达式2与表达3都为常量时，条件表达式可以被优化:而当表达式2或表达式3中的一个为变量时，条件表达式不可以被优化，会转换成分支结构。当表达式1为-一个常量值时，编译器会在编译期间得到答案，将不会有条件表达式存在，共有四套转换方案

  • 表达式1为简单比较，而表达式2和表达式3两者的差值等于1
  • 表达式1为简单比较，而表达式2和表达式3两者的差值大于1
  • 表达式1为复杂比较，而表达式2和表达式3两者的差值大于1
  • 表达式2和表达式3有一个为变量，于是无优化

方案一具体代码 

1
2
3
4
5
6
7
8
9
10
11
12
13
//c++源码说明，条件表达式
int Condition(int argc , int n){
//比较参数argc是否等于5，真值返回5，假值返回6
return argc == 5 ? 5 : 6;
}
//汇编比较
//清空eax
00401678	xor eax,eax
0040167A	cmp	dword ptr [ebp+8],5
//setne检查ZF标记位，当ZF==1，则赋值al为0，反之则赋值al为1
0040167E	setne al
//若argc等于5则al==0，反之al==1，执行这句后，eax正好为5/6
00401681	add	eax,5

方案二具体代码 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//c++源码说明，条件表达式
int Condition(int argc , int n){
//比较参数argc是否等于5，真值返回5，假值返回6
return argc == 5 ? 4 : 10;
}
//汇编比较
return argc == 5 ? 4 : 10;
00401678	mov	eax,dword ptr [ebp+8]
0040167B	sub	eax,5
0040167E	neg	eax
00401680	sbb	eax,eax
//eax的取值只可能为0或者0xFFFFFFFF
00401682	and	eax,6
00401685	add	eax,4

对于argc == 5这种等职的比较，VC++会使用减法和求补运算来判断是否为真值，如果我们的argc不为5，那么执行sub指令后的eax就不为0，neg的指令会将eax的符号位发生改变，也就是求补的运算，如果eax为0，也就是argc为5的话，那么0进行补+1，也是0，那么CF=0，我们现在假设CF=1的情况，那么执行sbb eax,eax 等同于了 eax-eax-CF 那么eax会变成0xFFFFFFFF，另一个情况就是0，使用eax与6进行与运算，如果eax数值为0xFFFFFFFF那么 想与就是6，相加4就是10，如果是0的情况那么直接就是0+4 = 4

总结 

1
2
3
4
5
6
7
总结：
sub reg,A
neg	reg
sbb reg,reg
and reg,B
add reg,C
//reg == A ? C : B

如果表达式2大于表达式3,那么最后加的数字为一个负数。这是由表达式3减去表达式2得到的数值

方案三具体代码 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//C++源码说明，条件表达式
int Condition(int argc,int n){
	return argc < = 8 ? 4 ：10；
}
//汇编代码
return argc < = 8 ? 4 ：10；
//清空eax,与方案1类似
00401678	xor	eax,eax
0040167A	cmp	dword ptr [ebp+8],8
//根据变量与8进行比较的结果，使用setg指令，当标记位SF=OF且ZF=0赋值al为1
符号标志位SF（Sign Flag），符号标志SF用来反映运算结果的符号位，他与运算结果的最高位相同
溢出标志位OF（Overflow Flag）：比如有一个杯子，放水放满了再放就出去了，叫溢出，但是怎么区别看起来都是最高位的问题
零标志位ZF（Zero Flag），零标志ZF用来反映运算结果是否为0，如果运算结果为0，则值为1，否则值为0，在判断运算结果是否为0时，可以用此标志位
//用于检查变量数据是否大于8，大于则赋值1，小于就赋值0
0040167E	setg al
//此时al中只能为0或1，执行自减的操作，eax中为0xFFFFFFFF或0
00401681	dec eax
//使用al和0xFA做与运算，eax中是0xFFFFFFFA或者0
//2-3=0xFFFFFFFA
00401682	and	al,0FAh
//由于eax只能有两个结果0xFFFFFFFA(-6)或0，加0x0A后结果比然为4，10
00401684	add	eax，0Ah

总结：

1
2
3
先调整reg为0或者为-1
and     reg, A
add     reg, B

遇到这样的代码块，需要重点考察and前的指令，以辨别真假逻辑的处理方式。对于上例中dec reg这样的指令，之前reg只能是0或者是1，因此这里的dec其实是对reg进行修正，如果原来reg为1, dec后修正为0，否则为ffffff，便于其后的and运算。这时候要根据and前的指令流程分析原来的判定在什么情况下会导致reg为0offfffff或者0，以便于还原。编译器这样做是为了避免产生分支语句。而对于顺序结构，处理器会预读下一条指令，以提高运行效率

无优化使用分支结果

如果表达式2或者表达式3中的值为未知数时候，就无法使用之前的方案去优化，编译器会那招正常的语句流程进行比较和判断，选择对应的表达式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//C++源码说明：条件表达式
int Condition(int argc,int n){
	return argc ? 8 : n;
}
//汇编代码
return argc ? 8 : n;
//比较变量argc
00401448	cmp	dword ptr [ebp+8],0
//使用JE跳转，检查变量argc是否等于0，跳转的地址为0x00401457位置
004014CC	je Condition+27 (00401457)
//跳转失败说明操作数1为真，将表达式1的值(立即数8)存入局部变量ebp-4中
0040144E	mov dword ptr [ebp-4],8
//跳转到返回值赋值处
00401455	jmp Condition+2Dh (00145d)
//参数2的数据存入eax中
00401457	mov	eax，dword ptr [ebp+0Ch]
0040145A	mov dword ptr [ebp-4],eax
0040145D	mov	eax,dword ptr [ebp-4]
//恢复现场
00401466	ret

位运算

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

位运算——Debug版 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//C++源码对应汇编，位运算(有符号数)
//左移运算3次
argc = argc << 3;
00401498	mov	eax,dword ptr [ebp+8]
//左移运算对应汇编指令SHL
0040149B	shl	eax,3
0040149E	mov	dword ptr [ebp+8],eax
//C++源码对比，右移运算5
argc = argc >> 5;
004014A1	mov	ecx,dword ptr [ebp+8]
//右移运算对应汇编指令SAR
004014A4	sar	ecx,5
004014A7	mov	dword ptr [ebp+8],ecx
//C++源码对比，位或运算，变量argc低16位不变，高16位设置为1
argc = argc | 0xFFFF0000
004014AA	mov edx,dword ptr [ebp+8]
//位或运算对应汇编指令OR
004014AD	or	edx,0FFFF0000h
004014B3	mov	dword ptr [ebp+8],edx
//C++源码对比，将变量argc低16位清0，高位不变
argc = argc & 0xFFFF0000
//位与运算对应汇编指令AND
004014B9	and eax，0xFFFFh
004014BE	mov	dword ptr [ebp+8],eax
//C++源码对比，对变量argc做异或运算
argc = argc ^ 0xFFFF0000
004014C1	mov	ecx,dword ptr [ebp+8]
//异或运算对应汇编指令XOR
004014C4	xor ecx,0FFFF0000h
004014CA	mov	dword ptr [ebp+8],ecx
//C++源码对比，将argc按位取反
argc = ~argc;
004014CD	mov	edx,dword ptr [ebp+8]
//取反运算对应汇编指令NOT
004014D0	not	edx
004014D2	mov	dword ptr [ebp+8],edx

无符号数位移 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//C++源码说明：无符号数位移
int BitOperation(int argc){
	unsigned int nVar = argc;
	nVar <<= 3;
	nVar >>= 5;
}
//C++源码对应汇编代码讲解
unsigned int nVar = argc;
004016C8	mov	eax,dword ptr [ebp+8]
004016CB	mov	dword ptr [ebp-4],eax
//C++源码对比，对变量nVar左移3位
nVar <<= 3;
004016CE	mov	ecx,dword ptr [ebp-4]
//和有符号数左移一样
004016D1	shl	ecx,3
004016D4	mov	dword ptr [ebp-4],ecx
//C++源码对比，对变量nVar右移5位
004016D7	mov	edx,dword ptr [ebp-4]
//使用shr进行右移位，最高位补0，最低位进CF
004016DA	shr edx,5
004016DD	mov dword ptr [ebp-4],edx

符号数与无符号数的差别在右移运算，有符号数对应的指令为sar，可以保留符号位;无符号数不需要符号位，所以直接使用shr将最高位补0

编译器使用的优化技巧

代码优化:是指为了达到某一种优化目的对程序代码进行变换。这样的变换有一个原则:变化前和变换后等价

就优化目的而论，代码优化一般有四个方向：

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

编译器的工作过程中可以分为几个阶段:预处理→词法分析→语法分析→语义分析→中间代码生成→目标代码生成。其中，优化的机会一般存在于中间代码生成和目标代码生成这两个阶段。尤其是在中间代码生成阶段所做的优化，这类优化不具备设备相关性，在不同的硬件环境中都能通用，因此编译器设计者广泛采用这类办法

  • 常量折叠
    x = 1 + 2
    1和2都是常量，所以结果可以预见，直接生成x = 3

  • 常量传播
    接上面的代码，其后代码为y = x + 3;由于上例最后生成了x = 3，其结果还是可以预见的，所以直接生成y = 6

  • 减少变量
    假设一个 x = i * 2 y = j * 2 if(x>y){}这里的x和y比较等价于i和j的比较，所以如果后面没有引用x，y，那么就会直接去掉x，y，生成 if(i>j)

  • 公共表达式
    那么假设 x = i * 2，y = i * 2所以 i * 2 叫做公共表达式，可以归并为一个，x = i * 2，y = x

  • 复写传播
    类似于常量传播，但是目标变成了变量，示例如下: 

    1
    2
    3
    x = a;
    ……
    y = x + c;

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

  • 剪去不可达分支
    如果if作用域内的代码内容永远不会被执行，因此整个if代码块没有存在的理由

  • 还有顺序语句代替分支，强度削弱，数学变换，代码外提等等

流水线优化

  1. 取指令：CPU从高速缓存或内存中取机器码
  2. 指令译码：分析指令的长度，功能和寻址方式
  3. 按寻址方式确定操作数：指令的操作数可以是寄存器，内存单元或者立即数，如果操作数在内存单元里，这一步就要计算出有效地址
  4. 取操作数：按操作数存放的位置获得数值，并存放在临时寄存器中
  5. 执行指令：由控制单元或者计算单元执行指令规则的操作
  6. 存放计算结果

来个例子~ 

1
2
执行指令： add	eax,dword ptr ds:[ebx+40DA44]
对应的机器代码： 0383	44DA4000

Intel处理器位小端序排列，数据的高位对应内存的高地址，低位对应内存的低地址

步骤：取指令，得到第一个十六进制字节：0x03，并且eip+1，译码知道这个指令是加法，但是信息不够，于是乎将0x03放入处理器的指令队列缓存中，取指令得到第二个十六进制字节：0x83，机器码放入处理器的指令队列缓存中，eip+1，译码后知道这个寄存器相对寻址方法的加法，而且参与寻址的寄存器是ebx，存放的目标是eax，后面还有4字节的偏移，指令长度确定后，机器码放入处理器的指令队列，取地址，得到第三个十六进制字节：0x44，这是指令中包含的4字节地址偏移量信息的第一个字节，放入内部暂存区，ebx保存在ALU，准备计算有效的地址，eip+1，之后依次开始取指令0xDA 0x40 0x00 放入寄存器，eip依次+1，这时候eax的值传给ALU，调度MMU，得到内存单元，传送到ALU，计算结果，最后将计算结果存回eax中

流水线

来个例子~ 

1
2
004010AA	mov	eax,92492493h
004010AF	add	esp,8

执行这段代码，不具备流水线的处理器先读取004010AA处的二进制指令，然后开始译码等操作，这–系列工作的每–步都是需要时间的，比如取指令，内存管理单元开始工作，其他部件闲置等待，等拿到了指令才进行下一步工作。于是，为了提高效率，Intel 公司从486开始就引入了流水线的机制

引入流水线之后，在第一条流水线执行mov指令的过程中，第二条流水线就可以开始对add执行读取和译码了，Intel采用长流水线设计，把每条指令划分出很多阶段，使得每个步骤的工作内容简单，但这容易取指令错误的时候回滚操作过多，AMD厂商使用多流水线设计，回滚错误少，但电路设计复杂

注意点

  • 指令相关性
    对于顺序安排的两条指令，后一条指令的执行依赖前–条指令的硬件资源，这样的情况就是指令相关，如下面的代码所示:
    add edx,esi
    sar edx,2
    由于以上两条代码都需要访问并设置edx，因此只能在执行完add edx,esi后才能执行sar edx, 2。这样的情况会存在寄存器的争用，影响并行效率，应尽量避免

  • 地址相关性

对于顺序安排的两条指令，前一条指令需要访问并回写到某一地址上，而后一条指令也需要访问这一-地址，这样的情况就是地址相关，如下面的代码所示:

add [00401234], esi
mov eax, [00401234]

由于第一条指令访问的是0x401234地址，那么只能第一条指令操作完后再去执行第二条语句，会影响效率，VC++的O2的release选项生成的代码会考虑流水线执行的工作方式

代码如下： 

1
2
3
4
5
6
7
8
9
10
11
0040101F	push eax
00401020	push offset aNvarone2D ; "nVarOne / 2 = %d"
00401025	call _printf
0040102A	mov	eax,92492493h
0040102F	add	esp,8
00401032	imul esi
00401034	add edx,esi
00401036	sar edx,2
00401039	mov eax,edx
0040103B	shr eax,1Fh
0040103E	add	edx,eax

恢复栈顶的指令add esp,8，中间有mov eax,92492493h指令，这里为流水线优化，因为后面的imul esi需要设置eax，把计算结果的低位放在eax中，那么中间换成add esp,8防止了寄存器争用，后面的这里的 add edx,esi 与 sar edx,2不能移动是因为，在后面的mov eax,edx 与 edx有关系，如果位置移动的话，我们会出现edx的一个的计算结果不正确，于是乎不能改变顺序

分支优化

配合流水线的工作模式，处理器增加了一个分支目标缓冲器，在流水线的工作模式下，如果遇见分支结构，我们就可以利用分支目标缓冲器预测并且读取指令的目标地址，分支目标缓冲器在程序运行的时候将动态记录和调整转移指令的目标地址，可以记录多个地址，进行表格化的管理，当发生转移的时候秒如果分支目标缓冲器中有记录，下一条指令在取指令阶段就会将其作为目标地址，如果我们记录地址不等于实际目标地址，就会被流水线冲刷，用一个分支，多次与邪恶失败，就会更新记录目标地址，所以我们在编写多重循环的时候，要把大循环放在内层，可以增加分支预测的准确度 

1
2
3
4
5
6
7
8
for(int i=0; i < 10; i++){
//下面每次循环会预测成功9999次
//第一次没有预测，最后退出循环的时候预测失败1次
//重复10次
for(int j = 0 ; j < 10000 ; j++){
	a[i][j]++;
	}
}
1
2
3
4
5
6
7
8
for(int i=0; i < 10000; i++){
//下面每次循环会预测成功9次
//第一次没有预测，最后退出循环的时候预测失败1次
//重复10000次
for(int j = 0 ; j < 9 ; j++){
	a[i][j]++;
	}
}

高速缓存优化规则

  1. 数据对齐
    cache不会保存VA的二进制低位，对于Intel的32位处理器来说，如果访问的地址是4的倍数，则可以直接查询并提取之;如果不是4的倍数，则需要访问多次。因此，VC++编译器在设置变量地址时会按照4字节边界对齐

  2. 数据集中
    将访问次数多的数据或代码尽量安排在-起，一方面是cache在抓取命中数据时会抓取周围的其他数据;另- -方面是虚拟内存分页的问题，如果数据分散，保留到多个分页中，就会导致过多的虚拟地址转换，甚至会导致缺页中断频繁发生，这些都会影响效率

  3. 减少体积
    命中率高的代码段应该减少体积，尽量放入cache中，以提高效率

第四章记录完毕~