吊炸天的switch-case语句

来看下面一段代码

#include<stdio.h>
int main()
{
	int xh;
	scanf("%d",&xh);
	switch(xh)
	{
	case 0:
		printf("this is 0\n");
		break;
	case 1:
		printf("this is 1\n");
		break;
	case 2:
		printf("this is 2\n");
		break;
	default:
		printf("this is 3\n");
	
	
	}
	return 0;
}

它的反汇编代码

text:00401017                 sub     eax, 0
.text:0040101A                 jz      short loc_401055
.text:0040101C                 dec     eax
.text:0040101D                 jz      short loc_401044
.text:0040101F                 dec     eax
.text:00401020                 jz      short loc_401033
.text:00401022                 push    offset aThisIs3 ; "this is 3\n"
.text:00401027                 call    sub_401070
.text:0040102C                 add     esp, 4
.text:0040102F                 xor     eax, eax
.text:00401031                 pop     ecx
.text:00401032                 retn

eax里面存的是变量xh

可以发现用减法代替了cmp,进行了优化

对源代码稍作修改,增加一个case

#include<stdio.h>
int main()
{
	int xh;
	scanf("%d",&xh);
	switch(xh)
	{
	case 0:
		printf("this is 0\n");
		break;
	case 1:
		printf("this is 1\n");
		break;
	case 2:
		printf("this is 2\n");
		break;
	case 3:
		printf("this is 3\n");
	default:
		printf("this is 4\n");
	
	
	}
	return 0;
}

它的反汇编代码

1017                 cmp     eax, 3          ; switch 4 cases
.text:0040101A                 ja      short loc_401063 ; jumptable 0040101C default case
.text:0040101C                 jmp     ds:off_401074[eax*4] ; switch jump

其中地址0×401074处的数据

.text:00401074 off_401074      dd offset loc_401023    ; DATA XREF: _main+1Cr
.text:00401074                 dd offset loc_401034    ; jump table for switch statement
.text:00401074                 dd offset loc_401045
.text:00401074                 dd offset loc_401056

分别是4个分支指令块的地址
可以发现用了一个跳转表来优化代码,实际上这是hash算法(不明白?想想计数排序是怎么样的)

 

继续修改

#include<stdio.h>
int main()
{
	int xh;
	scanf("%d",&xh);
	switch(xh)
	{
	case 0:
		printf("this is 0\n");
		break;
	case 1:
		printf("this is 1\n");
		break;
	case 2:
		printf("this is 2\n");
		break;
	case 254:
		printf("this is 3\n");
	default:
		printf("this is 4\n");
	
	
	}
	return 0;
}

来看它的反汇编代码:

.text:00401017                 cmp     eax, 0FEh       ; switch 255 cases
.text:0040101C                 ja      short loc_40106D ; jumptable 00401026 default case
.text:0040101E                 xor     ecx, ecx
.text:00401020                 mov     cl, ds:byte_401094[eax]
.text:00401026                 jmp     ds:off_401080[ecx*4] ; switch jump

碉堡,这回编译器用两个表来实现switch,先来看地址0×401094处的表

.text:00401094 byte_401094     db 0, 1, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
.text:00401094                                         ; DATA XREF: _main+20r
.text:00401094                 db 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4 ; indirect table for switch statement
.text:00401094                 db 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
.text:00401094                 db 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
.text:00401094                 db 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
.text:00401094                 db 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
.text:00401094                 db 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
.text:00401094                 db 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
.text:00401094                 db 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
.text:00401094                 db 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
.text:00401094                 db 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
.text:00401094                 db 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
.text:00401094                 db 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
.text:00401094                 db 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
.text:00401094                 db 4, 4, 3

可以看到,这个字符数组里面只有0,1,2,3,4.其实这几个数字正好对应了5个分支
再来看0×401080处的数据

.text:00401080 off_401080      dd offset loc_40102D, offset loc_40103E, offset loc_40104F
.text:00401080                                         ; DATA XREF: _main+26r
.text:00401080                 dd offset loc_401060, offset loc_40106D ; jump table for switch statement

这个数组和上面那个例子中的表一样,都是不同分支的代码处的地址

所以,联系起来可以发现,实际上这种情况下,编译器是用两次hash的方式进行优化的,由于0,1,2和254相差很大,如果只采用一个跳转表的话势必会浪费空间,因为这个表大小是256*4byte.而实际只有5个dword是真正起作用的。那么如果用两个表(或者说数组)呢?
首先第一个数组是字符数组hash[255],hash[i]的值是分支的编号,第二个数组ad[]是双字数组,ad[hash[i]]表示编号为hash[i]的分支的地址。那么所需空间为256*1byte+5*4byte。看,空间降下来了。

看到这里,读者可能意识到一个问题,第一个数组是byte型的,那要是代码中实际分支数超过256呢?显然,这时编译器不会再采用这种两个跳转表的方式

再来思考一个问题:如果case还是很少,但是case间的差值真的太大呢?也就是假如有case 10000这种情况,难道要开辟一个10002*1byte的数组?

显然写编译器的程序员不会这么豆逼嘛。。

继续修改上面的代码
(实在不好意思,突然发现上面的代码里面少打了一个break;。。。)

#include<stdio.h>
int main()
{
	int xh;
	scanf("%d",&xh);
	switch(xh)
	{
	case 0:
		printf("this is 0\n");
		break;
	case 1:
		printf("this is 1\n");
		break;
	case 2:
		printf("this is 2\n");
		break;
	case 10000:
		printf("this is 3\n");
		break;
	default:
		printf("this is 4\n");
	}
	return 0;
}

相应的反汇编代码:

.text:00401017                 cmp     eax, 800
.text:0040101C                 jg      short loc_40105E
.text:0040101E                 jz      short loc_40104D
.text:00401020                 test    eax, eax
.text:00401022                 jz      short loc_40103C
.text:00401024                 cmp     eax, 200
.text:00401029                 jnz     short loc_401065
.text:0040102B                 push    offset aThisIs1 ; "this is 1\n"
.text:00401030                 call    sub_401090
.text:00401035                 add     esp, 4
.text:00401038                 xor     eax, eax
.text:0040103A                 pop     ecx
.text:0040103B                 retn

上面代码中不含各分支具体处理的代码
这样好像看不出啥,我们把比较过程化成树的形式来直观的感受

可见,是一颗二叉树,如果继续修改源代码,结果应当是差不多的,得到的二叉树近似是平衡的,这样查找的时间复杂度是O(logn)
也就是说,当各个case的差值很大且case数较多时,编译器是用平衡二叉树来优化的,这样时间效率还是很高

One thought on “吊炸天的switch-case语句

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>