5.5 难以构成跳转表的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来了解非线性索引表的组成结构。

此方案所占用的内存空间如下[1]

(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原型。

[1]MAX表示最大case值,MIN表示最小case值,SUM表示case总数加1(包含default)。