我们或许知道if…else if…与switch的功能基本相似，而switch也完全可以转换成if…else if…的结构，并且switch总体来说效率要高于if…else if…。但是很少有人知道总体来说if…else if…的效率为什么低于switch，以及为什么说总体来说switch效率高，而不是一定高，以及什么时候效率一定比if…else if…高。今天我们就从反汇编的层面来看看switch语句的多种结构与其效率分析（测试采用VC++6.0集成环境）。
1、普通结构：
所谓普通结构，指的是和普通的if…else if…反汇编结构是完全相同的，在遇到正确匹配条件之前是需要一直去判断的，直到条件匹配后面的指令才不再继续执行。如下所示：
#include "stdafx.h"
int main(int argc, char* argv[])
{
int s = ;
switch(s){
case :
printf("1\n");
break;
case :
printf("2\n");
break;
case :
printf("3\n");
break;
default:
printf("error\n");
break;
}
return ;
}
对应的反汇编代码如下所示：
;main:
push ebp
mov ebp,esp
sub esp,h
push ebx
push esi
push edi
lea edi,[ebp-h]
C mov ecx,h
mov eax,CCCCCCCCh
rep stos dword ptr [edi]
mov dword ptr [ebp-],
F mov eax,dword ptr [ebp-]
mov dword ptr [ebp-],eax
;if(s == 1),即case 1
cmp dword ptr [ebp-],
je main+h ()
;else if(s == 2),即case 2
B cmp dword ptr [ebp-],
F je main+h ()
;else if(s == 3),即case 3
cmp dword ptr [ebp-],
je main+h ()
;else,即default
jmp main+h ()
;case 1:
push offset string "1\n" (c)
E call printf (f0)
add esp,
;break;
jmp main+h ()
;case 2:
push offset string "2\n" ()
D call printf (f0)
add esp,
;break;
jmp main+h ()
;case 3:
push offset string "5\n" ()
C call printf (f0)
add esp,
;break;
jmp main+h ()
;default:
push offset string "error\n" (c)
B call printf (f0)
add esp,
;break;
xor eax,eax
pop edi
pop esi
pop ebx
add esp,h
B cmp ebp,esp
D call __chkesp ()
mov esp,ebp
pop ebp
ret
该结构产生的条件(情况)：当case分支语句比较少（VC++6.0中是少于等于4条时），我们测试用的是三条，则switch…case被反汇编成和if…else if…相同的结构。那么在该情况在switch…case效率和if…else if…的效率是一样的。
2、大表结构（索引表）：
然而我们说switch也有效率高于if…else if…的情况，即下面所示的情况，举例说明：
#include "stdafx.h"
int main(int argc, char* argv[])
{
int s = ;
switch(s){
case :
printf("101\n");
break;
case :
printf("102\n");
break;
case :
printf("103\n");
break;
case :
printf("104\n");
break;
default:
printf("error\n");
break;
}
return ;
}
对应汇编代码如下所示：
;main:
;提升栈、保存现场、初始化函数栈等操作(省略)
mov dword ptr [ebp-],
;eax存储s，ecx存储
mov eax,dword ptr [ebp-]
mov dword ptr [ebp-],eax
mov ecx,dword ptr [ebp-]
;由于是从开始的连续常量，所以需要减去H(即)则索引(下标)从开始
sub ecx,h
B mov dword ptr [ebp-],ecx
;将减去的case值与比较（、、、、default）
;大于则为默认，直接跳转到default指令处
E cmp dword ptr [ebp-],
ja $L541+h (a)
;这里jmp指令是核心，"edx*4+4010AAh"是case分支指令地址在表中的下标，即AAh是索引表的首地址
mov edx,dword ptr [ebp-]
jmp dword ptr [edx*+AAh]
;case
$L535:
E push offset string "101\n" (bc)
call printf (0)
add esp,
B jmp $L541+Ch ()
;case
$L537:
D push offset string "1\n" (c)
call printf (0)
add esp,
A jmp $L541+Ch () ;break
;case
$L539:
C push offset string "3\n" ()
call printf (0)
add esp,
jmp $L541+Ch () ;break
;case
$L541:
B push offset string "104\n" (b4)
call printf (0)
add esp,
jmp $L541+Ch () ;break
;default
A push offset string "error\n" (c)
call printf (0)
add esp, ;不需要jmp，直接可达到break的效果
xor eax,eax
;销毁函数栈、恢复现场等操作(省略)
下面我们来具体分析：为什么叫大表结构？首先我们根据上面代码中标出的重要的那条jmp指令：jmp dword ptr [edx*4+4010AAh]来查看基址4010AAh的内存情况：
从0X004010AAh开始的内存中形成了一张所谓的“表”（该表由编译器产生），由于表中每个元素以四字节为单位，存储了对应case语句的地址，则称为大表（小表是1个字节）。而该地址是根据case n:中的n来计算的，比如case 104，所以edx = 104 - 101=3(sub edx,65H)，3*4+4010AAh=4010B6则jmp dword ptr [edx*4+4010AAh]即jmp dword ptr [4010B6]，而0X004010B6处存放的就是满足“case 104:”条件的指令的地址0X00401078，eip被修改为0X004010B6处存放的值即eip = 0X00401078，因此CPU下一步执行时就从0X00401078处开始执行，执行完毕后，一个jmp 00401097使得swtich语句结束。无论switch(s)的s是多少只需要提前做好初始化，然后一步jmp dword ptr [edx*4+4010AAh]指令就可以找到对应case的指令。而不需要一个一个去判断，节省了CPU指令周期，而其时间节省的代价是内存的付出。这也是为什么sub edx,65H。因为在现有规律下没有必要浪费不必要浪费的内存。
大表结构的另一种情况：
但是如果case后面的常量如果有不连续的情况，又该如何？我们先来看看比较轻微的不连续情况，即不连续的case值比较少时的情况，case分支依旧为4个，分别为1001，1002，1003，1005（1004为不连续点）：
减去的值不再是65H,而是1001即3E9H，此时依旧为大表结构，但是1004不存在，其处理方式观察下图：
由于case 1004不存在，所以1004属于默认default之列，故用1004索引出来的表中的地址即为default处的地址，这里只有一个不连续点，但是1004依旧占用了大表的4个字节（4个case，5个地址元素）。同理在不连续情况比较少的时候，编译器都会将这些连续值中间“断开”的少部分（不止一个）填充为default的地址，虽然内存有些浪费但是换得的效率依旧是比较划算的。如下为case 1001、1002、1003、1007，而缺少1004、1005、1006三个值的大表情况（4个case，7个地址元素）：
总结一下：在case分语句比较多的时候if…else if…结构明显效率不高的情况下，如果case的常量是连续的且有小部分间断，则采用大表结构（即四个字节存储case跳转的指令地址）来编译switch…case语句。间断处填充的地址则为default处执行的指令地址。这一些都是编译器根据相应的算法自行识别后做的。
3、大表+小表结构：
但是如果间断点比较多，大表中重复填充default地址的4字节空间比较多时，就显得有点浪费空间。这时候就需要引入小表，以下例来做分析：
#include "stdafx.h"
int main(int argc, char* argv[])
{
int s = ;
switch(s){
case :
printf("1001\n");
break;
case :
printf("1002\n");
break;
case :
printf("1003\n");
break;
case :
printf("1007\n");
break;
case :
printf("1009\n");
break;
case :
printf("1012\n");
break;
case :
printf("1014\n");
break;
case :
printf("1017\n");
break;
default:
printf("error\n");
break;
}
return ;
}
部分汇编代码如下：
;main:
;提升栈、保存现场、初始化函数栈等操作(省略)
D798 mov dword ptr [ebp-],
D79F mov eax,dword ptr [ebp-]
D7A2 mov dword ptr [ebp-],eax
D7A5 mov ecx,dword ptr [ebp-]
;该处依旧是为了减小大表的内存占用，减去1001
D7A8 sub ecx,h
D7AE mov dword ptr [ebp-],ecx
;由于对于连续的大表来说，总共有1007-1001=16条case语句(其实只有8条有效的case)
;所以如果减去1001后的索引值依旧大于10H即16则超过大表索引范围，直接跳去default
D7B1 cmp dword ptr [ebp-],h
D7B5 ja $L549+Fh (d845)
;依旧是根据基址来索引，但是此时的索引是有一点不同的，不同处在下面具体分析
D7BB mov eax,dword ptr [ebp-]
D7BE xor edx,edx
D7C0 mov dl,byte ptr (d889)[eax]
D7C6 jmp dword ptr [edx*+D865h]
;case 1001
$L535:
D7CD push offset string "1001\n" (fdc)
D7D2 call printf (f0)
D7D7 add esp,
D7DA jmp $L549+Ch (d852)
;case 1002
$L537:
D7DC push offset string "1002\n" (fd4)
D7E1 call printf (f0)
D7E6 add esp,
D7E9 jmp $L549+Ch (d852)
;case 1003
$L539:
D7EB push offset string "1003\n" (fcc)
D7F0 call printf (f0)
D7F5 add esp,
D7F8 jmp $L549+Ch (d852)
;case 1007
$L541:
D7FA push offset string "1007\n" (fc4)
D7FF call printf (f0)
D804 add esp,
D807 jmp $L549+Ch (d852)
;case 1009
$L543:
D809 push offset string "1009\n" (fbc)
D80E call printf (f0)
D813 add esp,
D816 jmp $L549+Ch (d852)
;case 1012
$L545:
D818 push offset string "1012\n" (c)
D81D call printf (f0)
D822 add esp,
D825 jmp $L549+Ch (d852)
;case 1014
$L547:
D827 push offset string "1014\n" ()
D82C call printf (f0)
D831 add esp,
D834 jmp $L549+Ch (d852)
;case 1017
$L549:
D836 push offset string "104\n" (fb4)
D83B call printf (f0)
D840 add esp,
D843 jmp $L549+Ch (d852)
;default
D845 push offset string "error\n" (c)
D84A call printf (f0)
D84F add esp,
D852 xor eax,eax
;销毁函数栈、恢复现场等操作(省略)
我们具体来分析在索引处的四行代码：
0040D7BB mov eax,dword ptr [ebp-8]
0040D7BE xor edx,edx
0040D7C0 mov dl,byte ptr (0040d889)[eax]
0040D7C6 jmp dword ptr [edx*4+40D865h]
[ebp-8]中现在存放的是switch(s)中的s减去1001之后的值，mov dl,byte ptr (0040d889)[eax]指令则是将[eax+0040d889H]处的值复制到dl处。我们看看对应的内存情况：
黑色选中部分即所谓小表（小表首地址即0040d889），而小表上方为大表（大表首地址为0040D865），我们的case分支总共有8条，所以大表中有九个地址（包括了default）。而我们mov dl,byte ptr (0040d889)[eax]是将小表中的值作为大表的索引，即case常量处理后的值为小表的索引，小表所索引到的值为大表的索引，大表所索引到的值为case的指令地址。比如：case 1009，常量处理后，eax=1009 - 1001 = 8，则mov dl,byte ptr (0040d889)[eax]，获取0040d889+8=0040d891处的值，dl=04H，edx=0X00000004H，所以jmp dword ptr [edx*4+40D865h]修改eip的值为edx*4+40D865h处的值，即4*4H+0040D865h=0040D875H，即00D04809处的值，eip = 00D04809。而我们可以从上面反汇编代码中获取：
;case 1009，eip = 00D04809从此处开始执行
$L543:
D809 push offset string "1009\n" (fbc)
D80E call printf (f0)
D813 add esp,
D816 jmp $L549+Ch (d852)
则下一条要执行的指令即为1009的地址，经过case常量、小表、大表的索引最终成功修改eip为准确的要执行的指令地址。而对于空出来的间断点，其在小表中的值均为08H，4*8H+0040D865h=0040D885H，该内存存储的均是default的地址，所以说小表中有效的case索引从00开始01、02、03、依次增加，而间断处均填充有效的case分支数（本例为8条case，即填充8），这样就使得原本只使用大表的内存（需要16*4=64B）节省了16字节（小表只需要：8*4+16*1=48B），当分支越多并且间断点越多节省相对也更多。但是小表也有局限性，当分支间隔大于256时，小表一个字节就存不下default的偏移量了（据说能设计出间隔大于256的cae常量的程序员应该直接拉出去…（枪毙））。
4、树形结构：
树形结构就是小表不能表示时，即间断大于256时的一种反汇编结构。我们以下例来分析：
该代码中switch有0、500、100、1500、2000、2500、3000、3500、4000几条case分支（间断大于256），反汇编如下（我们要分析的是判断阶段的树形结构）：
main:
;提升栈、保存现场、初始化函数栈等操作(省略)
;判断阶段
F mov eax,dword ptr [ebp-]
mov dword ptr [ebp-],eax
cmp dword ptr [ebp-],D0h
C jg main+h ()
E cmp dword ptr [ebp-],D0h
je main+F1h ()
B cmp dword ptr [ebp-],h
jg main+h ()
cmp dword ptr [ebp-],h
B je main+D3h ()
cmp dword ptr [ebp-],
je main+B2h (c2)
cmp dword ptr [ebp-],F4h
E je main+C4h (d4)
jmp main+Ch (c)
cmp dword ptr [ebp-],DCh
C je main+h (f2)
E jmp main+Ch (c)
cmp dword ptr [ebp-],DACh
A jg main+A0h (b0)
C cmp dword ptr [ebp-],DACh
je main+Eh (e)
cmp dword ptr [ebp-],C4h
A0 je main+h ()
A2 cmp dword ptr [ebp-],BB8h
A9 je main+Fh (f)
AB jmp main+Ch (c)
B0 cmp dword ptr [ebp-],FA0h
B7 je main+Dh (d)
BD jmp main+Ch (c)
;具体处理阶段
C2 push offset string "0\n" ()
C7 call printf (d0)
CC add esp,
CF jmp main+h ()
D4 push offset string "500\n" (c)
D9 call printf (d0)
DE add esp,
jmp main+h ()
push offset string "1000\n" ()
call printf (d0)
ED add esp,
F0 jmp main+h ()
F2 push offset string "1500\n" (c)
F7 call printf (d0)
FC add esp,
FF jmp main+h ()
push offset string "2000\n" ()
call printf (d0)
B add esp,
E jmp main+h ()
push offset string "2500\n" (c)
call printf (d0)
A add esp,
D jmp main+h ()
F push offset string "3000\n" ()
call printf (d0)
add esp,
C jmp main+h ()
E push offset string "3500\n" (c)
call printf (d0)
add esp,
B jmp main+h ()
D push offset string "4000\n" ()
call printf (d0)
add esp,
A jmp main+h ()
C push offset string "error\n" (c)
call printf (d0)
add esp,
xor eax,eax
;销毁函数栈、恢复现场等操作(省略)
根据判断阶段的分析，由jg指令分，可以将0、500、100、1500、2000、2500、3000、3500、4000分为以下的树形结构：
根据树形结构的每个节点再分为等于和不等于两种情况，进行处理。但是由于该情况基本不常见（写出这样的代码似乎应该已经被拉了出去……），所以我们不在仔细分析。而大表的小表是比较常见的两种结构，需要熟练掌握。