5.4 switch的真相
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作为基地址进行寻址了,查表[1]后跳转到对应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分支结构原型。
[1]本书将查询得到数组某个元素的过程称为查表。本示例代码使用了比例因子寻址取得数组内容。