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分支结构原型。
上传的附件: