-
-
[推荐]《C++反汇编与逆向分析技术揭秘》第5章 流程控制语句的识别
-
发表于: 2011-10-9 15:47
-
|
|
|---|---|
|
|
|
|
|
|
|
|
5.1节讲述了if语句的构成，但是，只有if的语句是不完整的分支结构，图5-1对比了两种语句结构的执行流程。
 图5-1 if与if…else…结构对比 如图5-1所示，if语句是一个单分支结构，if…else…组合后是一个双分支结构。两者间完成的功能有所不同。从语法上看，if…else…只比if语句多出了一个else。else有两个功能，如果if判断成功，则跳过else分支语句块；如果if判断失败，则进入else分支语句块中。有了else语句的存在，程序在进行流程选择时，必会经过两个分支中的一个。通过代码清单5-3，我们来分析else如何实现这两个功能。 代码清单5-3 if…else…组合—Debug版 // C++源码说明：if…else…组合
if (argc == 0) {
// 执行if语句块
printf("argc == 0");
}else{
// 执行else语句块
printf("argc != 0");
}
// C++源码与对应汇编代码讲解
// C++源码对比，比较参数变量argc == 0
if (argc == 0)
; 使用变量argc减去0
004010B8 cmp dword ptr [ebp+8],0
; 使用条件跳转JNE，检查cmp影响标记位
; 跳转成立，跳转到地址0x004010CD处，即else语句块的首地址
004010BC jne IfElse+2Dh (004010cd)
{
// C++源码对比，进入if语句块，调用printf函数
printf("argc == 0");
; printf函数汇编讲解略
}else
; 直接跳转到地址0x004010DA地址处，当if语句执行后跳转过else语句块
004010CB jmp IfElse+3Ah (004010da)
{
// C++源码对比，进入else语句块，调用printf函数
printf("argc != 0");
; printf函数汇编讲解略
004010CD push offset string "argc != 0" (00420030)
004010D2 call printf (00401150)
004010D7 add esp,4
}
; else语句结束处
004010DA pop edi在代码清单5-3中，if语句转换的条件跳转和代码清单5-1中的if语句相同，都是取相反的条件跳转指令。而在else处（地址004010CB）多了一句jmp指令，这是为了在if语句比较后，如果结果为真，则程序流程执行if语句块并且跳过else语句块，反之执行else语句块。else处的jmp指令跳转的目标地址为else语句块结尾处的地址，这样的设计可以跳过else语句块，实现两个分支语句二选一的功能。 4.2.3节介绍了条件表达式，当条件表达式中的表达式2或表达式3为变量时，没有进行优化处理。条件表达式转换后的汇编代码和if…else…结构非常相似，将代码清单4-17与代码清单5-3进行分析对比可以发现，两者间有很多相似之处，如没有源码比照，想要分辨出是条件表达式还是if…else…结构实在太难。它们都是先比较，然后再执行条件跳转指令，最后进行流程选择的。 通常，VC++ 6.0对条件表达式和if…else…使用同一套处理方式。代码清单5-3对应条件表达式转换方式4。将代码清单5-3稍作改动，改为符合条件表达式转换方式1的形式，如代码清单5-4所示。 代码清单5-4 模拟条件表达式转换方式1 // C++源码说明：if…else…模拟条件表达式转换方式1
if (argc == 0){ // 等价条件表达式中的表达式1
// 修改上例，将上例中的printf函数替换成变量赋值语句
argc = 5; // 等价条件表达式中的表达式2
}else{
// 代码上例，将上例中的printf函数替换成变量赋值语句
argc = 6; // 等价条件表达式中的表达式3
}
// 防止变量被优化处理
printf("%d \r\n", argc);
// Debug调试版，由于注重调试功能，没有进行优化，反汇编讲解如下
22: if (argc == 0){
; 直接与0进行比较，注意后面的jne，如果不相等就跳走，C源码中的逻辑与汇编代码相反
00401098 cmp dword ptr [ebp+8],0
0040109C jne main+27h (004010a7)
23: argc = 5;
; 这里是if语句块的内容，将参数赋值为5
0040109E mov dword ptr [ebp+8],5
24: }else{
; 注意这里的跳转，正好跳出了else块
004010A5 jmp main+2Eh (004010ae)
25: argc = 6;
; 这里是else语句块的内容，将参数赋值为6
004010A7 mov dword ptr [ebp+8],6
26: }
27: printf("%d \r\n", argc);
; printf函数汇编讲解略
004010AE ......按if…else…的逻辑，如果满足if条件，则执行if语句块；否则执行else语句块，两者有且仅有一个会执行。所以，如果编译器生成的代码在0040109C处的跳转条件成立，则必须到达else块的代码开始处。而004010A5处有个无条件跳转jmp，它的作用是绕过else块，因为如果能执行到这个jmp，if条件必然成立，对应的反汇编代码处的跳转条件必然不能成立，且if语句块已经执行完毕。由此，我们可以将这里的两处跳转指令作为“指路明灯”，准确划分if块和else块的边界。 总结： ; 先执行影响标志位的相关指令 jxx ELSE_BEGIN ; 该地址为else语句块的首地址 IF_BEGIN: …… ; if语句块内的执行代码 IF_END: jmp ELSE_END ; 跳转到else语句块的结束地址 ELSE_BEGIN: …… ; else语句块内的执行代码 ELSE_END: 如果遇到以上指令序列，先考察其中的两个跳转指令，当第一个条件跳转指令跳转到地址ELSE_BEGIN处之前有个JMP指令，则可将其视为由if…else…组合而成的双分支结构。根据这两个跳转指令可以得到if和else语句块的代码边界。通过cmp与jxx可还原出if的比较信息，jmp指令之后即为else块的开始。依此分析，即可逆向分析出if…else…组合的原型。 在Debug编译模式下，所使用的编译选项是Od+ZI，于是在这里不能做流水线优化，分支必须存在，以便于开发者设置断点观察程序流程。 使用O2优化选项，重新编译代码清单5-4。通过IDA查看优化后的反汇编代码，如代码清单5-5所示。 代码清单5-5 模拟条件表达式转换方案1—Release版 ; 参数标记定义，arg_表示函数参数1 arg_0= dword ptr 4 ; 将取得的参数数据放到edx中 mov edx, [esp+arg_0] ; 将eax清0 xor eax, eax ; 对edx和edx执行相与操作，结果不影响edx test edx, edx ; 检查ZF标记位，edx不等于0则al=1，反之al=0，这里的操作与代码清单4-14类似 setnz al add eax, 5 ;到此，eax的取值只可能是5或6，如果edx为0，则eax为5，反之则为6 push eax push offset Format ; "%d \r\n" call _printf add esp, 8 retn 代码清单5-5中的这些指令似曾相识，与条件表达式使用了同样的优化手法。其他3种优化方案同样适用于if…else…。通过以上分析，得出VC++ 6.0编译的代码，在很多情况下，会发现条件表达式的反汇编代码和if…else…组合是一样的，这时，可以根据个人习惯还原出等价的高级代码。 有时候会遇到复杂的条件表达式作为分支或者循环结构的判定条件的情况，这时即使直接阅读高级源码也会让人抓狂。在没有高级源码的情况下，分析者需要先定位语句块的边界，然后根据跳转目标和逻辑依赖慢慢反推出高级代码。 |
|
|
5.1节和5.2节介绍了由if与if…else…组成的分支结构。本节将介绍它们的组合形式—多分支结构。多分支结构类似于if…else…的组合方式，在if…else…的else之后再添加一个else if进行二次比较，这样就可以进行多次比较，再次选择程序流程，形成了多分支流程。它的C++语法格式为：if…else if…else if…，可重复后缀为else if。当最后为else时，便到了多分支结构的末尾处，不可再分支。通过代码清单5-6可以查看多分支结构的组成。
代码清单5-6 多分支结构—Debug版 // C++源码说明：多分支结构
void IfElseIf(int argc){
if (argc > 0){ // 判断函数参数argc是否大于0
printf("argc > 0"); // 比较成功后执行printf("argc > 0");
}else if (argc == 0){ // 判断函数参数argc是否等于0
printf("argc == 0"); // 比较成功后执行printf("argc == 0");
}else{ // 前两次比较都失败，则此条语句被执行
printf("argc <= 0");
}
}
// C++源码与对应汇编代码讲解
// C++源码对比
if (argc > 0)
; if比较转换
00401108 cmp dword ptr [ebp+8],0
; 使用JLE条件跳转指令，如果判断后的结果小于等于0，则跳转到地址0x0040111D
0040110C jle IfElseIf+2Dh (0040111d)
{
printf("argc > 0");
; printf函数讲解略
0040110E push offset string "argc > 0" (00420f9c)
00401113 call printf (00401150)
00401118 add esp,4
}else if (argc == 0)
; 对应else，当上一条if语句被执行，执行JMP指令，跳转到地址0x0040113F处
; 该地址为多分支结构结束地址，即最后一个else 或 else if的结束地址
0040111B jmp IfElseIf+4Fh (0040113f)
; if比较转换，使用条件跳转指令JNE，不等于0则跳转到地址0x00401132
0040111D cmp dword ptr [ebp+8],0
00401121 jne IfElseIf+42h (00401132)
{
printf("argc == 0");
; printf函数讲解略
00401123 push offset string "argc == 0" (0042003c)
00401128 call printf (00401150)
0040112D add esp,4
}else
; 跳转到多分支结构的结束地址
00401130 jmp IfElseIf+4Fh (0040113f)
{
printf("argc <= 0");
; 注意，此处无判定。当以上各个条件均不成立时，以下代码则无条件执行
; 可将此处定义为最后的else块
00401132 push offset string "argc != 0" (00420030)
00401137 call printf (00401150)
0040113C add esp,4
}
0040113F pop edi
代码清单5-6给出了if…else if…else 的组合。从代码中可以分析出，每条if语句由cmp和jxx组成，而else由一个jmp跳转到分支结构的最后一个语句块结束地址所组成。由此可见，虽然它们组合在了一起，但是每个if和else又都是独立的，if仍然是由CMP/TEST加jxx所组成，我们仍然可以根据上一节介绍的知识，利用jxx和jmp识别出if和else if语句块的边界，jxx指出了下一个else if的起始点，而jmp指出了整个多分支结构的末尾地址以及当前if或者else if语句块的末尾。最后的else块的边界也很容易识别，如果发现多分支块内的某一段代码在执行前没有判定，即可定义为else块，如上述代码中的00401132地址处。 总结： ; 会影响标志位的指令 jxx ELSE_IF_BEGIN ; 跳转到下一条else if语句块的首地址 IF_BEGIN: …… ; if语句块内的执行代码 IF_END: jmp END ; 跳转到多分支结构的结尾地址 ELSE_IF_BEGIN: ; else if 语句块的起始地址 ; 可影响标志位的指令 jxx ELSE_BEGIN ; 跳转到else分支语句块的首地址 …… ; else if语句块内的执行代码 IF_ELSE_ END: ; else if 结尾处 jmp END ; 跳转到多分支结构的结尾地址 ELSE_BEGIN: ; else语句块的起始地址 …… ; else语句块内的执行代码 END: ; 多分支结构的结尾处 …… 如果遇到这样的代码块，需要考察各跳转指令之间的关系。当每个条件跳转指令的跳转地址之前都紧跟JMP指令，并且它们跳转的地址值都一样时，可视为一个多分支结构。JMP指令指明了多分支结构的末尾，配合比较判断指令与条件跳转指令，可还原出各分支语句块的组成。如果某个分支语句块中没有判定类指令，但是存在语句块，且语句块的位置在多分支语句块范围内，可以判定其为else块。 由于编译器可以在编译期间对代码进行优化，当代码中的分支结构形成永远不可抵达的分支语句块时，它永远不会被执行，可以被优化掉而不参与编译处理。向代码清单5-6中插入一句“argc = 0;”，这样argc将被“常量传播”，因此可以在编译期得知，“if(argc < 0)”与“else”这两个分支语句块将永远不可抵达，它们就不会再参与编译。 void IfElseIf(int argc)
{
// 仿造可分支归并代码
argc = 0;
// 其他代码与代码清单5-6相同
}选择O2编译选项，将修改后的代码再次编译。使用IDA查看优化后的不可达分支是否被删除，如图5-2所示。  图5-2 优化后的不可达分支结构 优化后，图5-2中的不可达分支被删除了。由于只剩下一个必达的分支语句块，编译器直接提取出必达分支语句块中的代码，将整个分支结构替换，就形成了如图5-2所示的代码。更多分支结构的优化，会遵循第4章中讲述的各种优化方案。以代码清单5-6为例，此多分支结构执行结束后，并没有做任何工作，直接函数返回；且当某一分支判断成立时，其他分支将不会被执行。可以选择在每个语句块内插入return语句，以减少跳转次数。 代码清单5-6中的多分支结构，共有两条比较语句块。如果其中一个分支成立，则其他分支结构语句块便会被跳过。因此可将前两个分支语句块转换为单分支if结构，在各分支语句块中插入return语句，这样既没有破坏程序流程，又可以省略掉else语句。由于没有了else，减少了一次JMP跳转，使程序执行效率得到提高。其C++代码表现为： void IfElseIf(int argc){
if (argc > 0){ // 判断函数参数argc是否大于0
printf("argc > 0"); // 比较成功则执行printf("argc > 0");
return;
}
if (argc == 0){ // 判断函数参数argc是否等于0
printf("argc == 0");// 比较成功则执行printf("argc == 0");
return;
}
printf("argc <= 0"); // 否则执行printf("argc < 0");
return;
}
以上是我们在源码中进行的手工优化，编译器是否会按照我们的意图提升运行效率呢？开启O2编译选项，还原修改过的代码清单5-6，去掉“argc = 0;”再次编译。使用IDA分析反汇编代码，如代码清单5-7所示。 代码清单5-7 优化后的多分支结构—Release版 ; 函数入口处，对应代码清单5-6中if…else if函数 .text:00401000 sub_401000 proc near ; CODE XREF: _main+5p ; arg_0为函数参数 .text:00401000 arg_0 = dword ptr 4 ; 取出参数数据，放入eax，进行第一次if比较 .text:00401000 mov eax, [esp+arg_0] .text:00401004 test eax, eax ; 根据比较结果，使用条件跳转指令JLE，若小于等于则跳转到地址标号short loc_401016处 .text:00401006 jle short loc_401016 ; 跳转失败，执行printf函数参数传递及调用，显示字符串"argc > 0" .text:00401008 push offset Format ; "argc > 0" .text:0040100D call _printf .text:00401012 add esp, 4 ; 使用retn指令返回，结束函数调用 .text:00401015 retn ; 下面指令的注释是由IDA做的标记 ; 表示此处代码被标号sub_401000地址加6的地方引用 .text:00401016 loc_401016: ; CODE XREF: sub_401000+6j ; 第二条if比较，由于之前已经使用过test指令进行比较，这里省去重复操作 ; 直接使用条件跳转指令JNZ，若不等于0则跳转到地址标号short loc_401026处 .text:00401016 jnz short loc_401026 ; 跳转失败，执行printf函数参数传递及调用，显示字符串"argc == 0" .text:00401018 push offset aArgc0_0 ; "argc == 0" .text:0040101D call _printf .text:00401022 add esp, 4 ; 使用retn指令返回，结束函数调用 .text:00401025 retn ; 前两次比较判断都失败，执行此处代码 .text:00401026 loc_401026:; CODE XREF: sub_401000:loc_401016j .text:00401026 push offset aArgc0_1 ; "argc <= 0" .text:0040102B call _printf .text:00401030 pop ecx .text:00401031 retn .text:00401031 sub_401000 endp 由于选择的是O2优化选项，因此在优化方向上更注重效率，而不是节省空间。既然是对效率的优化，就会尽量减少分支中指令的使用。代码清单5-7中就省去了else对应的JMP指令，当第一次比较成功后，则直接在执行分支语句块后返回，省去了一次跳转操作，从而提升效率。 |
|
|
switch是比较常用的多分支结构，使用起来也非常方便，并且效率上也高于if…else if多分支结构。同样是多分支结构，switch是如何进行比较并选择分支的？它和if…else if的处理过程一样吗？下面我们通过简单的switch多分支结构慢慢揭开它的神秘面纱。编写case语句块不超过3条的switch多分支结构，如代码清单5-8所示。
代码清单5-8 switch 转换if else的 C++代码 //略去无关代码
int nIndex = 1;
scanf("%d", &nIndex);
switch(nIndex) {
case 1: printf("nIndex == 1"); break;
case 3: printf("nIndex == 3"); break;
case 100: printf("nIndex == 100") ;break;
}
代码清单5-8中的case语句块只有3条，也就是只有3条分支。if…else if的处理方案是分别进行比较，得到选择的分支，并跳转到分支语句块中。switch也会使用同样的方法进行分支处理吗？下面通过代码清单5-9进行分析和验证。 代码清单5-9 switch 转换if else —Debug版 switch(nIndex) { // 源码对比
0040DF00 mov ecx,dword ptr [ebp-4]
; 取出变量nIndex的值并放到ecx中，再将ecx放入临时变量 ebp - 8中
0040DF03 mov dword ptr [ebp-8],ecx
; 将临时变量和1进行比较
0040DF06 cmp dword ptr [ebp-8],1
; 条件跳转比较，等于1则跳转到地址0x0040DF1A处
0040DF0A je SwitchIf+4Ah (0040df1a)
; 将临时变量和3比较
0040DF0C cmp dword ptr [ebp-8],3
; 条件跳转比较，等于3则跳转到地址0x0040DF29处
0040DF10 je SwitchIf+59h (0040df29)
; 将临时变量和100比较
0040DF12 cmp dword ptr [ebp-8],64h
; 条件跳转比较，等于100则跳转到地址0x0040DF38处
0040DF16 je SwitchIf+68h (0040df38)
0040DF18 jmp SwitchIf+75h (0040df45)
case 1: // 源码对比
printf("nIndex == 1"); // 源码对比
0040DF1A push offset string "nIndex == 1" (00421024)
0040DF1F call printf (004014b0)
0040DF24 add esp,4
break; // 源码对比
0040DF27 jmp SwitchIf+75h (0040df45)
case 3: // 源码对比
printf("nIndex == 3"); // 源码对比
0040DF29 push offset string "nIndex == 3" (004210d8)
0040DF2E call printf (004014b0)
0040DF33 add esp,4
break; // 源码对比
0040DF36 jmp SwitchIf+75h (0040df45)
case 100: // 源码对比
printf("nIndex == 100"); // 源码对比
0040DF38 push offset string "nIndex == 100" (0042004c)
0040DF3D call printf (004014b0)
0040DF42 add esp,4
break; }} // 源码对比
0040DF45 pop edi
从对代码清单5-9的分析中得出，switch语句使用了3次条件跳转指令，分别与1、3、100进行了比较。如果比较条件成立，则跳转到对应的语句块中。这种结构与if…else if多分支结构非常相似，但仔细分析后发现，它们之间有很大的区别。先看看if…else if结构产生的代码，如代码清单5-10所示。 代码清单5-10 if…else if结构—Debug版 if (nIndex == 1) { // 源码对比
; if比较跳转
004011C5 cmp dword ptr [ebp-4],1
004011C9 jne SwitchIf+8Ah (004011da)
printf("nIndex == 1"); // 源码对比
; if语句块
004011CB push offset string "nIndex == 1" (00423080)
004011D0 call printf (00401680)
004011D5 add esp,4
}else if (nIndex == 3) // 源码对比
; else跳转
004011D8 jmp SwitchIf+0B2h (00401202)
; if比较跳转
004011DA cmp dword ptr [ebp-4],3
004011DE jne SwitchIf+9Fh (004011ef)
{printf("nIndex == 3"); // 源码对比
; if语句块
004011E0 push offset string "nIndex == 3" (0042304c)
004011E5 call printf (00401680)
004011EA add esp,4
}else if (nIndex == 3) // 源码对比
; else 跳转
004011ED jmp SwitchIf+0B2h (00401202)
; if比较跳转
004011EF cmp dword ptr [ebp-4],3
004011F3 jne SwitchIf+0B2h (00401202)
{ printf("nIndex == 100"); // 源码对比
; if语句块
004011F5 push offset string "nIndex == 100" (00423090)
004011FA call printf (00401680)
004011FF add esp,4
} // 结尾
将代码清单5-10与代码清单5-9进行对比分析：if…else if结构会在条件跳转后紧跟语句块；而switch结构则将所有的条件跳转都放置在了一起，并没有发现case语句块的踪影。通过条件跳转指令，跳转到相应case语句块中，因此每个case的执行是由switch比较结果引导“跳”过来的。所有case语句块都是连在一起的，这样是为了实现C语法的要求，在case语句块中没有break语句时，可以顺序执行后续case语句块。 总结： mov reg, mem ; 取出switch中考察的变量 ; 影响标志位的指令 jxx xxxx ; 跳转到对应case语句块的首地址处 ; 影响标志位的指令 jxx xxxx ; 影响标志位的指令 jxx xxxx jmp END ; 跳转到switch的结尾地址处 ...... ; case语句块的首地址 jmp END ; case语句块结束，有break则产生这个jmp ...... ; case语句块的首地址 jmp END ; case语句块的结束，有break则产生这个jmp ...... ; case语句块的首地址 jmp END ; case语句块结束，有break则产生这个jmp END: ; switch结尾 ...... 遇到这样的代码块，需要重点考察每个条件跳转指令后是否跟有语句块，以辨别switch分支结构。根据每个条件跳转到的地址来分辨case语句块首地址。如果case语句块内有break，会出现jmp作为结尾。如果没有break，可参考两个条件跳转所跳转到的目标地址，这两个地址之间的代码便是一个case语句块。 在switch分支数小于4的情况下，VC++ 6.0采用模拟if…else if的方法。这样做并没有发挥出switch的优势，在效率上也没有if…else if强。当分支数大于3，并且case的判定值存在明显线性关系组合时，switch的优化特性便可以凸显出来，如代码清单5-11所示。 代码清单5-11 有序线性的C++示例代码 int nIndex = 0;
scanf("%d", & nIndex);
switch(nIndex){
case 1: printf("nIndex == 1");break;
case 2: printf("nIndex == 2");break;
case 3: printf("nIndex == 3");break;
case 5: printf("nIndex == 5");break;
case 6: printf("nIndex == 6");break;
case 7: printf("nIndex == 7");break;
}
在此段代码中，case语句的标号为一个数值为1~7的有序序列。按照if…else if转换规则，会将1~7的数值依次比较一次，从而得到分支选择结果。这么做需要比较的次数太多，如何降低比较次数，提升效率呢？由于是有序线性的数值，可将每个case语句块的地址预先保存在数组中，考察switch语句的参数，并依此查询case语句块地址的数组，从而得到对应case语句块的首地址，通过代码清单5-12，验证这一优化方案。 代码清单5-12 有序线性示例—Debug版 switch(nIndex) { // 源码对比
; 将变量nIndex内容放入ecx中
00401110 mov ecx,dword ptr [ebp-4]
; 取出ecx的值并放入临时变量ebp-8中
00401113 mov dword ptr [ebp-8],ecx
; 取临时变量的值放入edx中，这几句代码的功能看似没有区别
; 只有在Debug版下才会出现
00401116 mov edx,dword ptr [ebp-8]
; 对edx减1，进行下标平衡
00401119 sub edx,1
; 将加1后的临时变量放回
0040111C mov dword ptr [ebp-8],edx
; 判断临时变量是否大于6
0040111F cmp dword ptr [ebp-8],6
; 大于6跳转到0x00401187处
00401123 ja $L556+0Dh (00401187)
; 取出临时变量的值放到eax中
00401125 mov eax,dword ptr [ebp-8]
; 以eax为下标，0x00401198为基址进行寻址，跳转到该地址处
; 注意：地址0x00401198就是case地址数组
00401128 jmp dword ptr [eax*4+401198h]
代码清单5-12的第4条汇编语句为什么要对edx减1呢？因为代码中为case语句制作了一份case地址数组（或者称为“case地址表”），这个数组保存了每个case语句块的首地址，并且数组下标是以0为起始。而case中的最小值是1，与case地址表的起始下标是不对应的，所以需要对edx减1调整，使其可以作为表格的下标进行寻址。 在进入switch后会先进行一次比较，检查输入的数值是否大于case值的最大值，由于case的最小值为1，那么对齐到0下标后，示例中case的最大值为（7-1=6）6。又由于使用了无符号比较（ja指令是无符号比较，大于则跳转），当输入的数值为0或一个负数时，同样会大于6，将直接跳转到switch的末尾。当然，如果有default分支，就直接跳至default语句块的首地址。当case的最小值为0时，不需要调整下标，当然也不会出现类似“sub edx,1”这样的下标调整代码。 保证了switch的参数值在case最大值的范围内，就可以以地址0x00401198作为基地址进行寻址了，查表①后跳转到对应case地址处。地址0x00401198就是case地址表（数组）的首地址，图5-3便是代码清单5-12的case地址表信息。  图5-3 有序线性case地址表 图5-3以0x00401198为起始地址，每4个字节数据保存了一个case语句块的首地址。依次排序下来，第一个case语句块所在地址为0x0040112F。表中第0项保存的内容为0x0040112F，即case 1 语句块的首地址。当输入给switch的参数值为1时，编译器减1调整到case地址数组的下标0后，eax*4+401198h就变成了0 * 4 + 0x00401198，查表得到第0项，即得到case 1语句块的首地址。其他case语句块首地址的查询同理，不再赘述。case语句块的首地址可以对照代码清单5-13查询。 代码清单5-13 线性的case语句块—Debug版 case 1: printf("nIndex == 1"); // 源码对比
; 取字符串"nIndex == 1"的首地址0x0004200470作为参数并压栈
0040112F push offset string "nIndex == 1" (00420070)
; 调用printf函数输出字符串，__cdecl调用方式
00401134 call printf (004014b0)
; 平衡printf参数的栈空间
00401139 add esp,4
break; // 源码对比
; 跳转到switch结束处，以下case语句相似，不做注释说明
0040113C jmp $L556+0Dh (00401187)
case 2: printf("nIndex == 2"); // 源码对比
0040113E push offset string "nIndex == 2" (00420064)
00401143 call printf (004014b0)
00401148 add esp,4
break; // 源码对比
0040114B jmp $L556+0Dh (00401187)
case 3: printf("nIndex == 3"); // 源码对比
0040114D push offset string "nIndex == 3" (00420058)
00401152 call printf (004014b0)
00401157 add esp,4
break; // 源码对比
0040115A jmp $L556+0Dh (00401187)
case 5: printf("nIndex == 5"); // 源码对比
0040115C push offset string "nIndex == 5" (00420048)
00401161 call printf (004014b0)
00401166 add esp,4
break; // 源码对比
00401169 jmp $L556+0Dh (00401187)
case 6: printf("nIndex == 6"); // 源码对比
0040116B push offset string "nIndex == 6" (00421024)
00401170 call printf (004014b0)
00401175 add esp,4
break; // 源码对比
00401178 jmp $L556+0Dh (00401187)
case 7: printf("nIndex == 7"); // 源码对比
0040117A push offset string "nIndex == 7" (0042003c)
0040117F call printf (004014b0)
00401184 add esp,4
break; // 源码对比
将图5-3和代码清单5-13对比可知，每个case语句块的首地址都在表中，但有一个地址却不是case语句块的首地址0x00401187。这个地址是每句break跳转的一个地址值，显然这是switch结束的地址。这个地址值出现在图5-3表格的第3项，表格项的下标以0为起始，反推回case应该是（3+1=4）4，而实际中却没有case 4 这个语句块。为了达到线性有序，对于没有case对应的数值，编译器以switch的结束地址或者default语句块的首地址填充对应的表格项。 代码清单5-13中的每一个break语句都对应一个jmp指令，跳转到的地址都是switch的结束地址处，起到了跳出switch的作用。如果没有break语句，则会顺序执行代码，执行到下一句case语句块中，这便是case语句中没有break可以顺序执行的原因。 代码清单5-13中没有使用default语句块。当所有条件都不成立后，才会执行到default语句块，它和switch的末尾实质上是等价的。switch中出现default后，就会填写default语句块的首地址作为switch的结束地址。 如果每两个case值之间的差值小于等于6，并且case语句数大于等于4，编译器中就会形成这种线性结构。在编写代码的过程中无需有序排列case值，编译器会在编译过程中对case线性地址表进行排序，如case的顺序为3、2、1、4、5，在case线性地址表中，会将它们的语句块的首地址进行排序，将case 1语句块的首地址放在case线性地址表的第0项上，case 2语句块首地址放在表中第1项，以此类推，将首地址变为一个有序的表格进行存放。 这种switch的识别有两个关键点，取数值内容进行比较；比较跳转失败后，出现4字节的相对比例因子寻址方式。有了这两个特性，就可以从代码中正确分析出switch结构。switch结构中的case线性地址模拟图如图5-4所示。  图5-4 case线性地址表模拟图 Release版与Debug版的反汇编代码基本一致，下面将在Release版中对这种结构进行实际分析，如代码清单5-14所示。 代码清单5-14 case语句的有序线性结构—Release版 ; 取出switch语句的参数值并放入ecx中 00401018 mov ecx,dword ptr [esp+8] 0040101C add esp,8 ; 平衡scanf函数的参数 ; 将ecx减1后放入eax中，因为最小的case 1存放在case地址表中下标为0处，需要调整对齐到0下标，便于直接查表 0040101F lea eax,[ecx-1] ; 与6进行比较，有了这两步操作可以初步假设这里的代码是一个switch结构 ; 无符号比较，大于6时跳转到地址0x00401086处 00401022 cmp eax,6 00401025 ja 00401086 ; 下面的指令体现了switch的第二个特性：查表（case地址表） ; 可以确认这是一个switch结构 ; 上一步的跳转地址00401086就是switch结尾或者是default语句块的首地址 ; 下面指令中的地址0x00401088便是case线性地址表的首地址 ; 可参考图5-5 00401027 jmp dword ptr [eax*4+401088h] ; 地址0x0040706C为字符串"nIndex == 1"的首地址 ; 此处为第一个case语句块的地址 0040102E push 40706Ch ; 此处调用printf函数 00401033 call 004012F0 ; 平衡printf函数破坏的栈空间 00401038 add esp,4 ; 还原esp 0040103B pop ecx ; 返回，在Release版中，编译器发现switch后什么也没做就直接返回，所以 ; 将每句break优化为了return ; 到此处，第一个case语句块结束，顺序向下为第二个case语句块 0040103C ret ; 第二个case语句块 ; 以下代码相似，除地址外，不再进行注释，请读者自行分析 ; 地址0x00407060为字符串"nIndex == 2"的首地址 0040103D push 407060h 00401042 call 004012F0 00401047 add esp,4 0040104A pop ecx 0040104B ret ; 第三个case语句块 ; 地址0x00407054为字符串"nIndex == 3"的首地址 0040104C push 407054h 00401051 call 004012F0 00401056 add esp,4 00401059 pop ecx 0040105A ret ; 第四个case语句块 ; 地址0x00407048为字符串"nIndex == 5"的首地址 0040105B push 407048h 00401060 call 004012F0 00401065 add esp,4 00401068 pop ecx 00401069 ret ; 第五个case语句块 ; 地址0x0040703C为字符串"nIndex == 6"的首地址 0040106A push 40703Ch 0040106F call 004012F0 00401074 add esp,4 00401077 pop ecx 00401078 ret ; 第六个case语句块 ; 地址0x00407030为字符串"nIndex == 7"的首地址 00401079 push 407030h 0040107E call 004012F0 00401083 add esp,4 00401086 pop ecx 00401087 ret 所有的case语句块都已找到，接下来将每个case的标号值进行还原。如何得到这个标号值呢？很简单，只要找到case线性地址表即可。此示例的case线性地址表的首地址为0x00401088，如图5-5所示。  图5-5 switch的有序线性case地址表 case线性地址表是一个有序表，在switch语句块中有减1操作，地址表是以0为下标开始，那么表中的第0项对应的case标号值应为（0+1=1）1，地址0x0040102E处为“case 1”。后续case语句块按此方案，请读者进行依次还原。 总结： mov reg, mem ; 取变量 ; 对变量进行运算，对齐case地址表的0下标，非必要 ; 上例中的eax也可用其他寄存器替换，这里也可以是其他类型的运算 lea eax, [reg+xxxx] ; 影响标志位的指令，进行范围检查 jxx DEFAULT_ADDR jmp dword ptr [eax*4+xxxx]; 地址xxxx为case地址表的首地址 当遇到这样的代码块时，可获取某一变量的信息并对其进行范围检查，如果超过case的最大值，则跳转条件成立 ，跳转目标指明了switch语句块的末尾或者是default块的首地址。条件跳转后紧跟jmp指令，并且是相对比例因子寻址方式，且基址为地址表的首地址，说明此处是线性关系的switch分支结构。对变量做运算，使对齐到case地址表0下标的代码不一定存在（当case的最小值为0时）。根据每条case地址在表中的下标位置，即可反推出线性关系的switch分支结构原型。 |
|
|
通过5.4节的学习可知，当switch为一个有序线性组合时，会对其case语句块制作地址表，以减少比较跳转次数。但并非所有switch结构都是有序线性的，当两个case值的间隔较大时，仍然使用switch的结尾地址或者default语句块的首地址来代替地址表中缺少的case地址，这样就会造成极大的空间浪费。
对于非线性的switch结构，可以采用制作索引表的方法来进行优化。索引表优化，需要两张表：一张为case语句块地址表，另一张为case语句块索引表。 地址表中的每一项保存一个case语句块的首地址，有几个case语句块就有几项。default语句块也在其中，如果没有则保存一个switch结束地址。这个结束地址在地址表中只会保存一份，不会像有序线性地址表那样，重复保存switch的结束地址。 索引表中保存地址表的编号，它的大小等于最大case值和最小case值的差。当差值大于255时，这种优化方案也会浪费空间，可通过树方式优化，这里就只讨论差值小于或等于255的情况。表中的每一项为一个字节大小，保存的数据为case语句块地址表中的索引编号。 当case值比较稀疏，且没有明显的线性关系时，如将代码清单5-11中case 7改为case 15，并且还采用有序线性的方式优化，则在case地址表中，下标7~15之间将保存switch结构的结尾地址，这样会浪费很多空间。所以，这样的情况可以采用二次查表法来查找地址。 首先将所有case语句块的首地址保存在一个地址表中，参见图5-8。地址表中的表项个数会根据程序中case分支来决定。有多少个case分支，地址表就会有多少项，不会像有序线性那样过多浪费内存。但是，如何通过case值获取对应地址表中保存的case语句块首地址呢？为此建立了一张对应的索引表，参见图5-7，索引表中保存了地址表中的下标值。索引表中最多可以存储256项，每一项的大小为1字节，这决定了case值不可以超过1字节的最大表示范围（0~255），因此索引表也只能存储256项索引编号。 在数值间隔过多的情况下，与上节介绍的制作单一的case线性地址表相比，制作索引表的方式更加节省空间，但是由于在执行时需要通过索引表来查询地址表，会多出一次查询地址表的过程，因此效率会有所下降。我们可以通过图5-6来了解非线性索引表的组成结构。 此方案所占用的内存空间如下： （MAX - MIN）* 1字节 = 索引表大小 SUM * 4字节 = 地址表大小 占用总字节数 = （（MAX - MIN）* 1字节）+（SUM * 4字节）  图5-6 索引表结构模拟图 看了这么多的理论，你可能会觉得烦琐，通过实际调试，你会发现这个优化结构很简单，并没有想象中的那么复杂，如代码清单5-15所示。 代码清单5-15 非线性索引表的C++代码 int nIndex = 0;
scanf("%d", &nIndex);
switch(nIndex){
case 1: printf("nIndex == 1");break;
case 2: printf("nIndex == 2");break;
case 3: printf("nIndex == 3");break;
case 5: printf("nIndex == 5");break;
case 6: printf("nIndex == 6");break;
case 255: printf("nIndex == 255");break;
}
在代码清单5-15中，从case 1开始到case 255结束，共255个case值，会生成一个255字节大小索引表。其中从6到255间隔了249个case值， 这249项保存的是case语句块地址表中switch的结尾地址下标，如代码清单5-16所示。 代码清单5-16 非线性索引表—Debug版 switch(nIndex){ // 源码对比
0040DF80 mov ecx,dword ptr [ebp-4]
0040DF83 mov dword ptr [ebp-8],ecx
; 这三条指令为取出变量nIndex的值并保存到edx的操作
0040DF86 mov edx,dword ptr [ebp-8]
; 索引表以0下标开始，case最小标号值为1，需要进行减1调整
0040DF89 sub edx,1
; 将对齐下标后的值放回到临时变量ebp-8中
0040DF8C mov dword ptr [ebp-8],edx
; 将临时变量与254进行无符号比较，若临时变量大于254则跳转
; 跳转到地址0x0040e002处，那里是switch结构的结尾
0040DF8F cmp dword ptr [ebp-8],0FEh
0040DF96 ja $L566+0Dh (0040e002)
; switch的参数值在case值范围内，取出临时变量中的数据并保存到ecx中
0040DF98 mov ecx,dword ptr [ebp-8]
; 清空eax的值，以ecx为下标在索引表中取出1字节的内容放入al中
; 地址0x0040E02F为索引表的首地址，查看图5-5
0040DF9B xor eax,eax
; 从索引表中取出对应地址表的下标
0040DF9D mov al,byte ptr (0040e02f)[ecx]
; 以eax作下标，0x0040E013为基址进行寻址，跳转到该地址处
; 地址0x0040E013为case语句块地址表的首地址，查看图5-5
0040DFA3 jmp dword ptr [eax*4+40E013h]
case 1: printf("nIndex == 1"); // 源码对比
0040DFAA push offset string "nIndex == 1" (00421024)
0040DFAF call printf (004014b0)
0040DFB4 add esp,4
break; // 源码对比
0040DFB7 jmp $L566+0Dh (0040e002)
case 2: printf("nIndex == 2"); // 源码对比
0040DFB9 push offset string "nIndex == 2" (0042003c)
0040DFBE call printf (004014b0)
0040DFC3 add esp,4
break; // 源码对比
0040DFC6 jmp $L566+0Dh (0040e002)
case 3: printf("nIndex == 3"); // 源码对比
0040DFC8 push offset string "nIndex == 3" (004210d8)
0040DFCD call printf (004014b0)
0040DFD2 add esp,4
break; // 源码对比
0040DFD5 jmp $L566+0Dh (0040e002)
case 5: printf("nIndex == 5"); // 源码对比
0040DFD7 push offset string "i == 3" (00420028)
0040DFDC call printf (004014b0)
0040DFE1 add esp,4
break; // 源码对比
0040DFE4 jmp $L566+0Dh (0040e002)
case 6: printf("nIndex == 6");
0040DFE6 push offset string "nIndex == 6" (004210cc)
0040DFEB call printf (004014b0)
0040DFF0 add esp,4
break; // 源码对比
0040DFF3 jmp $L566+0Dh (0040e002)
case 255: printf("nIndex == 255"); // 源码对比
0040DFF5 push offset string "nIndex == 255" (0042005c)
0040DFFA call printf (004014b0)
0040DFFF add esp,4
break; } // 源码对比
; switch结束地址
0040E002 pop edi
代码清单5-16首先查询索引表，索引表由数组组成，数组的每一项大小为1字节。从索引表中取出地址表的下标，根据下标值，找到跳转地址表中对应的case语句块首地址，跳转到该地址处。这种查询方式会产生两次间接内存访问，在效率上低于线性表方式。  图5-7 非线性索引表—Debug版 图5-7中的第0项为数值0，在图5-8的地址表中查询第0项，取4字节数据作为case语句块首地址—0x0040DFAA，对应代码清单5-16中的“case 1”的首地址（还记得之前的减1调整吗？见代码清单5-16中的0040DF89地址处）。在表中，标号相同的为switch的结束地址标号（有default块则是default块的地址）。然后在地址表中第6项找到switch的结束地址，图5-8中地址表的第6项对应的地址为0x0040E02B。该地址中保存的数据按照地址方式解释为：0x0040E002对应着代码清单5-16中switch的结束地址。  图5-8 非线性地址表—Debug版 已知case语句数及每个case语句块的地址，如何还原每个case的标号值呢？需要将两表相结合，分析出每个case语句的标号值。将索引表看做一个数组，参考反汇编代码中将索引表对齐到0下标的操作，代码清单5-16中对齐到0下标的数值为-1，因此地址表所对应的索引表的下标加1就是case语句的标号值。 例如，索引表中的第0项内容为0（索引表以0为起始下标），在表中是一个独立的数据，说明其不是switch结尾地址下标。它对应于地址表中第0项，地址0x0040DFAA这条case语句的标号值就是（0+1=1）1。地址表中的最后一项0x0040E002是表中的第6项，这个值在索引表中重复出现，可以断定其是switch的结束地址或者是default语句块的首地址。地址表第5项0x0040DFF5对应索引表中的下标值254，将其加1就是地址0x0040DFF5的case语句标号值。 在case语句块中没有任何代码的情况下，索引表中也会出现相同标号。由于case中没有任何代码，当执行到它时，则会顺序向下，直到发现下一个case语句不为空为止。这时所有没有代码的case属于一段多个case值共用的代码。索引表中这些case的对应位置处所保存的都是这段共用代码在地址表中的下标值，因此出现了索引表中标号相同的情况。 总结： mov reg, mem ; 取出switch变量 sub reg,1 ; 调整对齐到索引表的下标0 mov mem, reg ; 影响标记位的指令 jxx xxxx ; 超出范围跳转到switch结尾或default mov reg, [mem] ; 取出switch变量 ; eax不是必须使用的，但之后的数组查询用到的寄存器一定是此处使用到的寄存器 xor eax,eax mov al,byte ptr (xxxx)[reg] ; 查询索引表，得到地址表的下标 jmp dword ptr [eax*4+xxxx] ; 查询地址表，得到对应的case块的首地址 如果遇到以上代码块，可判定其是添加了索引表的switch结构。这里有两次查找地址表的过程，先分析第一次查表代码，byte ptr指明了表中的元素类型为byte；然后分析是否使用在第一次查表中获取的单字节数据作为下标，从而决定是否使用相对比例因子的寻址方式进行第二次查表；最后检查基址是否指向了地址表。有了这些特征后，即可参考索引表中保存的下标值来恢复索引表形式的switch结构中的每一句case原型。 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5.5节讲述了对非线性索引表的优化，讨论了最大case值和最小case值之差在255以内的情况。当最大case值与最小case值之差大于255，超出索引1字节的表达范围时，上述优化方案同样会造成空间的浪费，此时采用另一种优化方案—判定树：将每个case值作为一个节点，从这些节点中找到一个中间值作为根节点，以此形成一棵二叉平衡树，以每个节点为判定值，大于和小于关系分别对应左子树和右子树，这样可以提高效率。
如果打开O1选项—体积优先，由于有序线性优化和索引表优化都需要消耗额外的空间，因此在体积优先的情况下，这两种优化方案是不被允许的。编译器尽量以二叉判定树的方式来降低程序占用的体积，如代码清单5-17所示。 代码清单5-17 switch树的C++源码 int nIndex = 0;
scanf("%d", &nIndex);
switch(nIndex){
case 2: printf("nIndex == 2\n"); break;
case 3: printf("nIndex == 3\n"); break;
case 8: printf("nIndex == 8\n"); break;
case 10: printf("nIndex == 10\n"); break;
case 35: printf("nIndex == 35\n"); break;
case 37: printf("nIndex == 37\n"); break;
case 666: printf("nIndex == 666\n"); break;
default: printf("default\n"); break;
}
如果代码清单5-17中没有case 666这句代码，可以采用非线性索引表方式进行优化。有了case 666这句代码后，便无法使用仿造if else优化、有序线性优化、非线性索引表优化等方式。需要使用更强大的解决方案，将switch做成树，Debug版代码见代码清单5-18。 代码清单5-18 树结构switch片段—Debug版 switch(nIndex){ // 源码对比
00401490 mov ecx,dword ptr [ebp-4]
00401493 mov dword ptr [ebp-8],ecx
; 取出变量nIndex进行比较
00401496 cmp dword ptr [ebp-8],0Ah
; 条件跳转，大于10跳转到地址0x004014B9处
0040149A jg SwitchTree+59h (004014b9)
0040149C cmp dword ptr [ebp-8],0Ah
; 条件跳转，等于10跳转到地址0x004014FD处
004014A0 je SwitchTree+9Dh (004014fd)
004014A2 cmp dword ptr [ebp-8],2
; 条件跳转，等于2跳转到地址0x004014D0处
004014A6 je SwitchTree+70h (004014d0)
004014A8 cmp dword ptr [ebp-8],3
; 条件跳转，等于3跳转到地址0x004014DF处
004014AC je SwitchTree+7Fh (004014df)
004014AE cmp dword ptr [ebp-8],8
; 条件跳转，等于8跳转到地址0x004014EE处
004014B2 je SwitchTree+8Eh (004014ee)
; JE跳转失败，直接跳转到地址0x00401539（default块首地址）处
004014B4 jmp SwitchTree+0D9h (00401539)
004014B9 cmp dword ptr [ebp-8],23h
; 条件跳转，等于35跳转到地址0x0040150C处
004014BD je SwitchTree+0ACh (0040150c)
004014BF cmp dword ptr [ebp-8],25h
; 条件跳转，等于37跳转到地址0x0040151B处
004014C3 je SwitchTree+0BBh (0040151b)
004014C5 cmp dword ptr [ebp-8],29Ah
; 条件跳转，等于666跳转到地址0x0040152A处
004014CC je SwitchTree+0CAh (0040152a)
; JE跳转失败，直接跳转到地址0x00401539（default块首地址）处
004014CE jmp SwitchTree+0D9h (00401539)
…… // case 语句块部分略
// default 语句块
default:printf("default\n");break; // 源码对比
00401539 push offset string "default\n" (004230b0)
0040153E call printf (004015e0)
00401543 add esp,4
分析代码清单5-18得出，在switch的处理代码中，比较判断的次数非常之多。首先与10进行了比较，大于10跳转到地址0x004014B9处，这个地址对应的代码又是条件跳转操作，比较的数值为35。如果不等于35，则与37比较；不等于37又再次与666进行比较；与666比较失败后会跳转到switch结尾或default块的首地址处。到此为止，大于10的比较就全部结束了。从这几处比较可以发现，这类似一个if 分支结构。 继续分析，第一次与10进行比较，小于10则顺序向下执行。再次与2进行比较，如果不等于2，就继续与3比较；如果不等于3，再继续与8进行比较。小于10的比较操作到此就都结束了，很明显，条件跳转指令后，没有语句块，这是一个仿造if else的switch分支结构。大于10的比较情况与小于10的类似，也是一个仿造的if else分支结构。如果每一次比较都以失败告终，最后将只能够执行JMP指令，跳转到地址0x00401539处，即default块首地址。将这两段比较组合后的结构图如图5-9所示。  图5-9 二叉判定树 图5-9为代码清单5-18的结构图，从图中可以发现，这棵树的左右两侧并不平衡，而是两个if else结构。由于判断较少，平衡后的效果并不明显，且进行树平衡的效率明显低于if else。这时，编译器采取的策略是，当树中的叶子节点数小于等于3时，就会转换形成一个if else 结构。 当向左子树中插入一个叶子节点10000时，左子树叶子节点数大于4。此时if else的转换已经不适合了，优先查看是否可以匹配有序线性优化、非线性索引表优化，如果可以，则转换为相应的优化。在不符合以上两个优化规则的情况下，就做成平衡树。 在Release版下，使用IDA查看编译器是如何优化的。树结构流程图如图5-10所示。  图5-10 树结构流程图 图5-10是从IDA中提取出来的，根据流程走向可以看出，有一个根节点，左边的多分支流程结构很像一个switch，而右边则是一个多次比较判断，和if else类似。进一步观察汇编代码，如代码清单5-19所示。 代码清单5-19 判定树结构片段1—Release版 .text:00401018 mov eax, [esp+0Ch+var_4] ; 平衡scanf的参数 .text:0040101C add esp, 8 ; eax中保存着switch语句的参数，与35 比较 .text:0040101F cmp eax, 35 ; 大于35跳转到标号short loc_401080处 .text:00401022 jg short loc_401080 ; 等于35跳转到标号short loc_401071处 .text:00401024 jz short loc_401071 ; 用eax加-2，进行下标平衡 .text:00401026 add eax, 0FFFFFFFEh ; switch 9 cases ; 比较最大case值，之前进行了减2的对齐下标操作 ; 这里的比较数为8，考察对齐下标操作后，说明这里的最大case值为10 .text:00401029 cmp eax, 8 ; 大于8跳转到标号short loc_401093处 ; IDA已经识别出这是个default分支 .text:0040102C ja short loc_401093 ; default ; 看到这种4字节的相对比例因子寻址方式，之前又进行了下标判断比较， ; 可以肯定这个off_4010D0标号的地址为case地址表 .text:0040102E jmp ds:off_4010D0[eax*4] ; switch jump 判定树中的case地址表如图5-11所示。  图5-11 判定树中的case地址表—Release版 图5-11中的编号off_4010D0并不容易识别，可将此标号重新命名—按N键重新命名为CASE_JMP_TABLE，表示这是一个case跳转表。这个表保存了10个case块的首地址，其中的5个地址值相同，这5个地址值表示的可能是default语句块的首地址或者switch的结束地址。将编号loc_401093修改为SWITCH_DEFAULT，这样，图5-11中还剩下4个地址标号需要解释。 根据之前所学的知识，这个表中的第0项为下标值加下标对齐值—下标对齐值为2，地址标号loc_401035为表中第0项，对应的case值为0 + 2，将其修改为CASE_2。类似地，标号loc_401044为 case 3代码块的首地址，可修改为CASE_3；标号loc_401053为 case 8代码块的首地址，可修改为CASE_8；标号loc_401062为 case 10代码块的首地址，可修改为CASE_10。这样线性表部分就全都分析完了。 在代码清单5-19中还有两个标号short loc_401080与short loc_401071。标号short loc_40107表示的是比较等于35后才会跳转到的地址，可以判断这个标号表示的地址为case 35语句块的首地址，将其重新命名为CASE_35。如果大于35，则会跳转到标号short loc_401080表示的地址处。继续分析汇编代码，如代码清单5-20所示。 代码清单5-20 树结构片段2—Release版 .text:00401080 loc_401080: .text:00401080 cmp eax, 37 ; 比较是否等于37，等于则跳转到标号short loc_4010C0 .text:00401083 jz short loc_4010C0 .text:00401085 cmp eax, 666 ; 比较是否等于666，等于则跳转到标号short loc_4010B1 .text:0040108A jz short loc_4010B1 .text:0040108C cmp eax, 10000 ; 比较是否等于10000，等于则跳转到标号short loc_4010A2 .text:00401091 jz short loc_4010A2 代码清单5-20中的多分支结构为一个仿if else的switch结构，在两个比较跳转中间没有任何语句执行块。根据比较的数值可以知道跳转的地址标号代表的case语句。标号short loc_4010C0表示 case 37代码块的首地址，可修改为 CASE_37，标号short loc_4010B1表示 case 666代码块的首地址，可修改为 CASE_666，标号short loc_4010A2表示case 10000代码块的首地址，可修改为CASE_10000。至此，这个switch结构分析完毕。 为了降低树的高度，在树的优化过程中，检测树的左子树或右子树能否满足if else优化、有序线性优化、非线性索引优化，利用这三种优化来降低树高度。选择哪种优化也是有顺序的，谁的效率最高，又满足其匹配条件，就可以被优先使用。以上三种优化都无法匹配，就会选择使用判定树。 |
|
|
VC++使用三种语法来完成循环结构，分别为为do、while、for。虽然它们完成的功能都是循环，但是每种语法有着不同的执行流程。
● 对每种结构进行分析，了解它们生成的汇编代码，它们之间的区别，以及如何根据每种循环结构的特性进行还原。 （1）do循环 do循环的工作流程清晰，识别起来也相对简单。根据其特性，先执行语句块，再进行比较判断。当条件成立时，会继续执行语句块。C++中的goto语句也可以用来模拟do循环结构，如代码清单5-21所示。 代码清单5-21 使用goto语句模拟do循环 // goto模拟do循环完成正数累加和
int GoToDo(int nCount){
int nSum = 0;
int nIndex = 0;
// 用于goto语句跳转使用标记
GOTO_DO:
// 此处为循环语句块
nSum += nIndex; // 保存每次累加和
nIndex++; // 指定循环步长为每次递增1
// 若nIndex大于nCount，则结束goto调用
if (nIndex <= nCount){
goto GOTO_DO;
}
return nSum; // 返回结果
}
代码清单5-21演示了使用goto语句与if分支结构来实现do循环过程。程序执行流程是自上向下地顺序执行代码，通过goto语句向上跳转修改程序流程，实现循环。do循环结构也是如此，如代码清单5-22所示。 代码清单5-22 do循环—Debug版 // C++源码说明：do循环完成整数累加和
int LoopDO(int nCount){
int nSum = 0;
int nIndex = 0;
do {
nSum += nIndex;
nIndex++;
// 循环判断，是否结束循环体
} while(nIndex <= nCount);
return nSum;
}
// C++源码与对应汇编代码讲解
// C++源码对比，变量初始化
int nSum = 0;
0040B4D8 mov dword ptr [ebp-4],0
int nIndex = 0;
0040B4DF mov dword ptr [ebp-8],0
// C++源码对比，进入循环语句块
do{
nSum += nIndex;
; 循环语句块的首地址，即循环跳转地址
0040B4E6 mov eax,dword ptr [ebp-4]
0040B4E9 add eax,dword ptr [ebp-8]
0040B4EC mov dword ptr [ebp-4],eax
nIndex++;
0040B4EF mov ecx,dword ptr [ebp-8]
0040B4F2 add ecx,1
0040B4F5 mov dword ptr [ebp-8],ecx
// C++源码对比，比较是否结束循环
} while(nIndex <= nCount);
0040B4F8 mov edx,dword ptr [ebp-8]
; 比较两个内存中的数据
0040B4FB cmp edx,dword ptr [ebp+8]
; 根据比较结果，使用条件跳转指令JLE，小于等于则跳转到地址0x0040B4E6处
0040B4FE jle LoopDO+26h (0040b4e6)
return nSum;
0040B500 mov eax,dword ptr [ebp-4]
代码清单5-22中的循环比较语句“while(nIndex <= nCount)”转换成的汇编代码和if分支结构非常相似，分析后发现它们并不相同。if语句的比较是相反的，并且跳转地址大于当前代码的地址，是一个向下跳转的过程；而do中的跳转地址小于当前代码的地址，是一个向上跳转的过程，所以条件跳转的逻辑与源码中的逻辑相同。有了这个特性，if语句与do循环判断就很好区分了。 总结： DO_BEGIN: …… ; 循环语句块 ; 影响标记位的指令 jxx DO_BEGIN ; 向上跳转 如果遇到以上代码块，即可判定它为一个do循环结构，只有do循环结构无需先检查，直接执行循环语句块。根据条件跳转指令所跳转到的地址，可以得到循环语句块的首地址，jxx指令的地址为循环语句块的结尾地址。在还原while比较时，应该注意，它与if不同，while的比较数并不是相反，而是相同的。依此分析即可还原do循环结构的原型。 （2）while循环 while循环和do循环正好相反，在执行循环语句块之前，必须要进行条件判断，根据比较结果再选择是否执行循环语句块，如代码清单5-23所示。 代码清单5-23 while循环—Debug版 // C++源码说明：while循环完成整数累加和 int LoopWhile(int nCount){ int nSum = 0; int nIndex = 0; // 先执行条件比较，再进入循环体 while (nIndex <= nCount){ nSum += nIndex; nIndex++; } return nSum; } // C++源码于对应汇编代码讲解 int nSum = 0; 0040B7C8 mov dword ptr [ebp-4],0 int nIndex = 0; 0040B7CF mov dword ptr [ebp-8],0 // C++源码对比，判断循环条件 while (nIndex <= nCount) 0040B7D6 mov eax,dword ptr [ebp-8] 0040B7D9 cmp eax,dword ptr [ebp+8] ; 条件判断比较，使用JG指令，大于则跳转到地址0x0040B7F2处，和if语句一样 ; 地址0x0040B7F2为while循环结束地址 0040B7DC jg LoopWhile+42h (0040b7f2) { // 循环语句块 nSum += nIndex; 0040B7DE mov ecx,dword ptr [ebp-4] 0040B7E1 add ecx,dword ptr [ebp-8] 0040B7E4 mov dword ptr [ebp-4],ecx nIndex++; 0040B7E7 mov edx,dword ptr [ebp-8] 0040B7EA add edx,1 0040B7ED mov dword ptr [ebp-8],edx } ; 执行跳转指令JMP，跳转到地址0x0040B7D6处 0040B7F0 jmp LoopWhile+26h (0040b7d6) return nSum; 0040B7F2 mov eax,dword ptr [ebp-4] 在代码清单5-23中，转换后的while比较和if语句一样，也是比较相反，向下跳转。如何区分代码中是分支结果还是循环结构呢？查看条件指令跳转地址0x0040B7F2，如果这个地址上有一句JMP指令，并且此指令跳转到的地址小于当前代码地址，那么很明显是一个向上跳转。要完成语句循环，就需要修改程序流程，回到循环语句处，因此向上跳转就成了循环结构的明显特征。根据这些特性可知while循环结构的特征，在条件跳转到的地址附近会有JMP指令修改程序流程，向上跳转，回到条件比较指令处。 while循环结构中使用了两次跳转指令完成循环，由于多使用了一次跳转指令，因此while循环要比do循环效率低一些。 总结： WHILE_BEGIN: ; 影响标记位的指令 jxx WHILE_END ; 条件成立跳转到循环语句块结尾处 …… ; 循环语句块 jmp WHILE_BEGIN ; 跳转到取出条件比较数据处 WHILE_END: 遇到以上代码块，即可判定它为一个while循环结构。根据条件跳转指令，可以还原相反的while循环判断。循环语句块的结尾地址即为条件跳转指令的目标地址，在这个地址之前会有一条jmp跳转指令，指令的目标地址为while循环的起始地址。需要注意的是，while循环结构很可能会被优化成do循环结构，被转换后的while结构由于需要检查是否可以被成功执行一次，通常会被嵌套在if单分支结构中，其还原的高级代码如下所示： if(xxx)
{
do
{
// ……
}while(xxx)
}
（3）for循环 for循环是三种循环结构中最复杂的一种。for循环由赋初值、设置循环条件、设置循环步长这三条语句组成。由于for循环更符合人类的思维方式，在循环结构中被使用的频率也最高。根据for语句组成特性分析代码清单5-24。 代码清单5-24 for循环结构—Debug版 // C++源码说明：for循环完成整数累加和
int LoopFor(int nCount){
int nSum = 0;
// 初始计数器变量、设置循环条件、设置循环步长
for (int nIndex = 0; nIndex <= nCount; nIndex++){
nSum += nIndex;
}
return nSum;
}
// C++源码于对应汇编代码讲解
int nSum = 0;
0040B818 mov dword ptr [ebp-4],0
// C++源码对比，for语句
for (int nIndex = 0; nIndex <= nCount; nIndex++)
;=====================================================
; 初始化计数器变量—nIndex 1.赋初值部分
0040B81F mov dword ptr [ebp-8],0
; 跳转到地址0x0040B831处，跳过步长操作
0040B826 jmp LoopFor+31h (0040b831)
;=====================================================
; 取出计数器变量，用于循环步长 2.步长计算部分
0040B828 mov eax,dword ptr [ebp-8]
; 对计数器变量执行加1操作，步长值为1
0040B82B add eax,1
; 将加1后的步长值放回计数器变量—nIndex
0040B82E mov dword ptr [ebp-8],eax
;=====================================================
; 取出计数器变量nIndex放入ecx 3.条件比较部分
0040B831 mov ecx,dword ptr [ebp-8]
; ebp+8地址处存放数据为参数nCount，见C++源码说明
0040B834 cmp ecx,dword ptr [ebp+8]
; 比较nIndex与nCount，大于则跳转到地址0x0040B844处，结束循环
0040B837 jg LoopFor+44h (0040b844)
;=====================================================
{
// for循环内执行语句块
nSum += nIndex;
mov edx,dword ptr [ebp-4] ; 4.循环体代码
0040B83C add edx,dword ptr [ebp-8]
0040B83F mov dword ptr [ebp-4],edx
}
; 跳转到地址0x0040B828处，这是一个向上跳
0040B842 jmp LoopFor+28h (0040b828)
return nSum;
// 设置返回值eax为ebp-4，即nSum
0040B844 mov eax,dword ptr [ebp-4]
代码清单5-24演示了for循环结构在Debug调试版下的汇编代码组成。需要由3次跳转来完成循环过程，其中一次为条件比较跳转，另外两次为jmp跳转。for循环结构为什么要设计得如此复杂呢？由于for循环分为赋初值、设置循环条件、设置循环步长这三个部分，为了可以单步调试程序，将汇编代码与源码进行一一对应，因此在Debug版下有了这样的设计，其循环流程如图5-12所示。  图5-12 for循环结构流程图 根据对代码清单5-24及图5-12中for循环流程的分析，总结出for循环结构在Debug版下的特性。 总结： mov mem/reg, xxx ; 赋初值 jmp FOR_CMP ; 跳到循环条件判定部分 FOR_STEP: ; 步长计算部分 ; 修改循环变量Step mov reg, Step add reg,xxxx ; 修改循环变量的计算过程，在实际分析中，视算法不同而不同 mov Step,eax FOR_CMP: ; 循环条件判定部分 mov ecx,dword ptr Step ; 判定循环变量和循环终止条件StepEnd 的关系，满足条件则退出for循环 cmp ecx, StepEnd jxx FOR_END ; 条件成立则结束循环 …… jmp FOR_STEP ; 向上跳转，修改流程回到步长计算部分 FOR_END: 遇到以上代码块，即可判定它为一个for循环结构。这种结构是for循环独有的，在计数器变量被赋初值后，利用jmp跳过第一次步长计算。然后，可以通过三个跳转指令还原for循环的各个组成部分：第一个jmp指令之前的代码为初始化部分；从第一个jmp指令到循环条件比较处（也就是上面代码中FOR_CMP标号的位置）之间的代码为步长计算部分；在条件跳转指令jxx之后寻找一个jmp指令，这jmp指令必须是向上跳转的，且其目标是到步长计算的位置，在jxx和这个jmp（也就是上面代码中省略号所在的位置）之间的代码即为循环语句块。 在这三种循环结构中，while循环和for循环一样，都是先判断再循环。由于需要先判断，因此需要将判断语句放置在循环语句之前，这就使while循环和for循环在结构上没有do循环那么简洁。那么在效率上这三个循环之间又有哪些区别呢？下一节将分析这三者间的效率对比。 |
|
|
5.7节介绍了3种循环结构，在执行效率上，do循环结构是最高的。由于do循环在结构上非常精简，利用了程序执行时由低地址到高地址的特点，只使用一个条件跳转指令就完成了循环，因此已经无需在结构上进行优化处理。
由于循环结构中也有分支功能，所以4.4.2节介绍的分支优化同样适用于循环结构。分支优化会使用目标分支缓冲器，预读指令。由于do循环是先执行后比较，因此执行代码都在比较之前，如下所示。 int i = 0;
00401248 mov dword ptr [ebp-4],0
do
{
i++;
0040124F mov eax,dword ptr [ebp-4]
00401252 add eax,1
00401255 mov dword ptr [ebp-4],eax
printf("%d", i);
; printf讲解略
} while(i < 1000);
; 此处的汇编代码在退出循环时才预测失败
00401269 cmp dword ptr [ebp-4],3E8h
00401270 jl main+1Fh (0040124f)
do循环结构中只使用了一次跳转就完成了循环功能，大大提升了程序的执行效率。因此，在三种循环结构中，它的执行效率最高。 while循环结构的效率要比do循环结构低。while循环结构先比较再循环，因此无法利用程序执行顺序来完成循环。同时，while循环结构使用了2个跳转指令，在程序流程上就弱于do循环结构。为了提升while循环结构的效率，可以将其转成效率较高的do循环结构。在不能直接转换成do循环结构的情况下，可以使用if单分支结构，将do循环结构嵌套在if语句块内，由if语句判定是否能执行循环体。因此，所有的while循环都可以转换成do循环结构，如图5-13所示。  图5-13 while循环结构的优化图 图5-13为代码清单5-23使用O2选项后编译的Release版结构流程图，该图截取自IDA。图5-13划分了程序的流程，箭头方向显示,反汇编代码中有一个单分支结构与循环结构。首先由条件跳转指令jl比较参数，小于等于0则跳转。可见这是一个if语句。 如果jl跳转失败，则顺序向下执行，进入标号loc_40100C处。这是一个循环语句块。此语句块内使用条件跳转指令jle，当ecx小于等于edx时，跳转到地址标号loc_40100C处。edx中保存参数数据，ecx每次加1，使eax每次对ecx累加。先执行，后判断，有了这个特性便可将图5-13所对应的代码还原成由单分支结构中嵌套do循环结构的高级代码。转换成对应的C++代码如下： int LoopWhile(int nCount){
int nSum = 0;
int nIndex = 0;
if(nCount >= 0){
do{
nSum += nIndex;
nIndex++;
}while(nIndex <= nCount)
}
return nSum;
}经过转换后，代码的功能没有任何改变，只是在结构上有了调整，变成了单分支结构加do循环结构。 以上讨论了while循环结构的优化，可以将其转换为do循环结构来提升效率。 从结构特征上可知，for循环是执行速度最慢的，它需要三个跳转指令才能够完成循环，因此也需要对其进行优化。for循环可以这么转换吗？从循环结构上看，其结构特征和while循环结构类似。由于赋初值部分不属于循环体，可以忽略。只要将比较部分放到循环体内，即是一个while循环结构。既然可以转换while循环结构，那么自然可以转换为do循环结构进行优化以提升效率。 有了for循环结构的优化方案，那么在对其优化过程中，VC++ 6.0能否按照此方案进行优化呢？将代码清单5-24使用O2选项进行重新编译，优化后的for循环反汇编代码如代码清单5-25所示。 代码清单5-25 for循环结构—Release版 .text:00401000 sub_401000 proc near ; 函数参数标号定义arg_0 .text:00401000 arg_0 = dword ptr 4 ; 使用edx保存参数arg_0 .text:00401000 mov edx, [esp+arg_0] ; 清空eax，ecx .text:00401004 xor eax, eax .text:00401006 xor ecx, ecx .text:00401008 test edx, edx ; 检查edx，小于0则跳转到标号short locret_401013处，该函数结束 .text:0040100A jl short locret_401013 ; 说明此处标号在地址sub_401000+0x11处被调用 .text:0040100C loc_40100C: ; 执行eax加等于ecx操作 .text:0040100C add eax, ecx ; 执行ecx自加1操作 .text:0040100E inc ecx .text:0040100F cmp ecx, edx ; 比较ecx与edx，小于等于则跳转到标号short loc_40100C处，这是一个向上跳 .text:00401011 jle short loc_40100C ; 函数返回地址标号locret_401013处，被地址标号sub_401000+0x0A处调用 .text:00401013 locret_401013: .text:00401013 retn 分析代码清单5-25发现，它与图5-13的思路竟然完全一致。编译器通过检查，将for循环结构最终转换成了do循环结构。使用if单分支结构进行第一次执行循环体的判断，再将转换后的do循环嵌套在if语句中，就形成了“先执行，后判断”的do循环结构。由于在O2选项下，while循环及for循环都可以使用do循环进行优化，所以在分析经过O2选项优化的反汇编代码时，很难转换回相同源码，只能尽量还原等价源码。读者可根据个人习惯转换对应的循环结构。 从结构上优化循环后，还需从细节上再次优化，以进一步提高循环的效率。4.4节介绍了编译器的各种优化技巧，循环结构的优化也使用这些技巧，其中常见的优化方式是“代码外提”。例如，循环结构中经常有重复的操作，在对循环结构中语句块的执行结果没有任何影响的情况下，可选择相同代码外提，以减少循环语句块中的执行代码，提升循环执行效率，如代码清单5-26所示。 代码清单5-26 循环结构优化—代码外提 // C++源码说明：for循环完成整数累加和
int CodePick(int nCount){
int nSum = 0;
int nIndex = 0;
do {
nSum += nIndex;
nIndex++;
// 此处代码每次都要判断nCount – 1，nCount并没有自减，仍然为一个固定值
// 可在循环体外先对nCount进行减等于1操作，再进入循环体
} while(nIndex < nCount - 1);
return nSum;
}
// 经过优化后的反汇编代码
.text:00401000 sub_401000 proc near; CODE XREF: _main+21-p
.text:00401000 arg_0 = dword ptr 4
; 获取参数到edx中
.text:00401000 mov edx, [esp+arg_0]
.text:00401004 xor eax, eax
.text:00401006 xor ecx, ecx
; 代码外提，对edx执行自减1操作
.text:00401008 dec edx
; 进入循环体，在循环体内直接对保存参数的edx进行比较，没有任何减1操作
.text:00401009 loc_401009: ; CODE XREF: sub_401000+Ej
.text:00401009 add eax, ecx
.text:0040100B inc ecx
.text:0040100C cmp ecx, edx
.text:0040100E jl short loc_401009
.text:00401010 retn
.text:00401010 sub_401000 endp
分析代码清单5-26可知，编译器将循环比较“nIndex < nCount - 1”中的“nCount – 1”进行了外提。由于“nCount – 1”中nCount在循环体中没有被修改，因此对它的操作是可以被拿到循环体外。被外提后的代码如下： int CodePick(int nCount){
int nSum = 0;
int nIndex = 0;
nCount -= 1; // 外提代码
do {
nSum += nIndex;
nIndex++;
} while(nIndex < nCount); // 原来的nCount-1被外提了
return nSum;
}这种外提是有选择性的—只有在不影响循环结果的情况下，才可以外提。 除了代码外提，还可以通过一些方法进一步提升循环结构的执行效率—强度削弱，即用等价的低强度运算替换原来代码中的高强度运算，例如，用加法代替乘法，如代码清单5-27所示。 代码清单5-27 循环强度降低优化—Release版 // C++源码说明：强度削弱
int main(int argc){
int t = 0;
int i = 0;
while (t < argc){
t = i * 99; // 强度削弱后，这里将不会使用乘法运算
i++; // 此处转换后将为 t = i; i += 99;
} // 利用加法运算替换掉了指令周期长的乘法运算
printf("%d", t);
return 0;
}
; 优化后的反汇编代码
.text:00401020 arg_0 = dword ptr 4
; 将参数信息保存到edx中
.text:00401020 mov edx, [esp+arg_0]
.text:00401024 xor eax, eax ; 清空eax
.text:00401026 test edx, edx
.text:00401028 jle short loc_401035
.text:0040102A xor ecx, ecx ; 清空ecx
.text:0040102C
; 循环语句块首地址
.text:0040102C loc_40102C: ; CODE XREF: sub_401020+13j
.text:0040102C mov eax, ecx ; 将ecx传入eax中
; ecx自加63h，即十进制99，等价于ecx每次加1乘以99
.text:0040102E add ecx, 63h
.text:00401031 cmp eax, edx
.text:00401033 jl short loc_40102C ; eax小于edx则执行跳转
.text:00401035
.text:00401035 loc_401035: ; CODE XREF: sub_401020+8j
;printf函数调用处略
.text:00401043 retn
.text:00401043 sub_401020 endp
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
