5.6 降低判定树的高度

5.5 节讲述了对非线性索引表的优化,讨论了最大case值和最小case值之差在255以内的情况。当最大case值与最小case值之差大于255,超出索引1字节的表达范围时,上述优化方案同样会造成空间的浪费,此时采用另一种优化方案—判定树:将每个case值作为一个节点,从这些节点中找到一个中间值作为根节点,以此形成一棵二叉平衡树,以每个节点为判定值,大于和小于关系分别对应左子树和右子树,这样可以提高效率。

如果打开O1选项—体积优先,由于有序线性优化和索引表优化都需要消耗额外的空间,因此在体积优先的情况下,这两种优化方案是不被允许的。编译器尽量以二叉判定树的方式来降低程序占用的体积,如代码清单5-17所示。

代码清单5-17 switch树的C++源码


int nIndex=0;

scanf("%d",&nIndex);

switch(nIndex){

case 2:printf("nIndex==2\n");break;

case 3:printf("nIndex==3\n");break;

case 8:printf("nIndex==8\n");break;

case 10:printf("nIndex==10\n");break;

case 35:printf("nIndex==35\n");break;

case 37:printf("nIndex==37\n");break;

case 666:printf("nIndex==666\n");break;

default:printf("default\n");break;

}


如果代码清单5-17中没有case 666这句代码,可以采用非线性索引表方式进行优化。有了case 666这句代码后,便无法使用仿造if else优化、有序线性优化、非线性索引表优化等方式。需要使用更强大的解决方案,将switch做成树,Debug版代码见代码清单5-18。

代码清单5-18 树结构switch片段—Debug版


switch(nIndex){//源码对比

00401490 mov ecx, dword ptr[ebp-4]

00401493 mov dword ptr[ebp-8],ecx

;取出变量nIndex进行比较

00401496 cmp dword ptr[ebp-8],0Ah

;条件跳转,大于10跳转到地址0x004014B9处

0040149A jg SwitchTree+59h(004014b9)

0040149C cmp dword ptr[ebp-8],0Ah

;条件跳转,等于10跳转到地址0x004014FD处

004014A0 je SwitchTree+9Dh(004014fd)

004014A2 cmp dword ptr[ebp-8],2

;条件跳转,等于2跳转到地址0x004014D0处

004014A6 je SwitchTree+70h(004014d0)

004014A8 cmp dword ptr[ebp-8],3

;条件跳转,等于3跳转到地址0x004014DF处

004014AC je SwitchTree+7Fh(004014df)

004014AE cmp dword ptr[ebp-8],8

;条件跳转,等于8跳转到地址0x004014EE处

004014B2 je SwitchTree+8Eh(004014ee)

;JE跳转失败,直接跳转到地址0x00401539(default块首地址)处

004014B4 jmp SwitchTree+0D9h(00401539)

004014B9 cmp dword ptr[ebp-8],23h

;条件跳转,等于35跳转到地址0x0040150C处

004014BD je SwitchTree+0ACh(0040150c)

004014BF cmp dword ptr[ebp-8],25h

;条件跳转,等于37跳转到地址0x0040151B处

004014C3 je SwitchTree+0BBh(0040151b)

004014C5 cmp dword ptr[ebp-8],29Ah

;条件跳转,等于666跳转到地址0x0040152A处

004014CC je SwitchTree+0CAh(0040152a)

;JE跳转失败,直接跳转到地址0x00401539(default块首地址)处

004014CE jmp SwitchTree+0D9h(00401539)

……//case语句块部分略

//default语句块

default:printf("default\n");break;//源码对比

00401539 push offset string"default\n"(004230b0)

0040153E call printf(004015e0)

00401543 add esp,4


分析代码清单5-18得出,在switch的处理代码中,比较判断的次数非常之多。首先与10进行了比较,大于10跳转到地址0x004014B9处,这个地址对应的代码又是条件跳转操作,比较的数值为35。如果不等于35,则与37比较;不等于37又再次与666进行比较;与666比较失败后会跳转到switch结尾或default块的首地址处。到此为止,大于10的比较就全部结束了。从这几处比较可以发现,这类似一个if分支结构。

继续分析,第一次与10进行比较,小于10则顺序向下执行。再次与2进行比较,如果不等于2,就继续与3比较;如果不等于3,再继续与8进行比较。小于10的比较操作到此就都结束了,很明显,条件跳转指令后,没有语句块,这是一个仿造if else的switch分支结构。大于10的比较情况与小于10的类似,也是一个仿造的if else分支结构。如果每一次比较都以失败告终,最后将只能够执行JMP指令,跳转到地址0x00401539处,即default块首地址。将这两段比较组合后的结构图如图5-9所示。

图 5-9 二叉判定树

图5-9为代码清单5-18的结构图,从图中可以发现,这棵树的左右两侧并不平衡,而是两个if else结构。由于判断较少,平衡后的效果并不明显,且进行树平衡的效率明显低于if else。这时,编译器采取的策略是,当树中的叶子节点数小于等于3时,就会转换形成一个if else结构。

当向左子树中插入一个叶子节点10000时,左子树叶子节点数大于4。此时if else的转换已经不适合了,优先查看是否可以匹配有序线性优化、非线性索引表优化,如果可以,则转换为相应的优化。在不符合以上两个优化规则的情况下,就做成平衡树。

在Release版下,使用IDA查看编译器是如何优化的。树结构流程图如图5-10所示。

图 5-10 树结构流程图

图5-10是从IDA中提取出来的,根据流程走向可以看出,有一个根节点,左边的多分支流程结构很像一个switch,而右边则是一个多次比较判断,和if else类似。进一步观察汇编代码,如代码清单5-19所示。

代码清单5-19 判定树结构片段1—Release版


.text:00401018 mov eax,[esp+0Ch+var_4]

;平衡scanf的参数

.text:0040101C add esp,8

;eax中保存着switch语句的参数,与35比较

.text:0040101F cmp eax,35

;大于35跳转到标号short loc_401080处

.text:00401022 jg short loc_401080

;等于35跳转到标号short loc_401071处

.text:00401024 jz short loc_401071

;用eax加-2,进行下标平衡

.text:00401026 add eax,0FFFFFFFEh;switch 9 cases

;比较最大case值,之前进行了减2的对齐下标操作

;这里的比较数为8,考察对齐下标操作后,说明这里的最大case值为10

.text:00401029 cmp eax,8

;大于8跳转到标号short loc_401093处

;IDA已经识别出这是个default分支

.text:0040102C ja short loc_401093;default

;看到这种4字节的相对比例因子寻址方式,之前又进行了下标判断比较,

;可以肯定这个off_4010D0标号的地址为case地址表

.text:0040102E jmp ds:off_4010D0[eax*4];switch jump


判定树中的case地址表如图5-11所示。

图 5-11 判定树中的case地址表—Release版

图5-11中的编号off_4010D0并不容易识别,可将此标号重新命名—按N键重新命名为CASE_JMP_TABLE,表示这是一个case跳转表。这个表保存了10个case块的首地址,其中的5个地址值相同,这5个地址值表示的可能是default语句块的首地址或者switch的结束地址。将编号loc_401093修改为SWITCH_DEFAULT,这样,图5-11中还剩下4个地址标号需要解释。

根据之前所学的知识,这个表中的第0项为下标值加下标对齐值—下标对齐值为2,地址标号loc_401035为表中第0项,对应的case值为0+2,将其修改为CASE_2。类似地,标号loc_401044为case 3代码块的首地址,可修改为CASE_3;标号loc_401053为case 8代码块的首地址,可修改为CASE_8;标号loc_401062为case 10代码块的首地址,可修改为CASE_10。这样线性表部分就全都分析完了。

在代码清单5-19中还有两个标号short loc_401080与short loc_401071。标号short loc_40107表示的是比较等于35后才会跳转到的地址,可以判断这个标号表示的地址为case 35语句块的首地址,将其重新命名为CASE_35。如果大于35,则会跳转到标号short loc_401080表示的地址处。继续分析汇编代码,如代码清单5-20所示。

代码清单5-20 树结构片段2—Release版


.text:00401080 loc_401080:

.text:00401080 cmp eax,37

;比较是否等于37,等于则跳转到标号short loc_4010C0

.text:00401083 jz short loc_4010C0

.text:00401085 cmp eax,666

;比较是否等于666,等于则跳转到标号short loc_4010B1

.text:0040108A jz short loc_4010B1

.text:0040108C cmp eax,10000

;比较是否等于10000,等于则跳转到标号short loc_4010A2

.text:00401091 jz short loc_4010A2


代码清单5-20中的多分支结构为一个仿if else的switch结构,在两个比较跳转中间没有任何语句执行块。根据比较的数值可以知道跳转的地址标号代表的case语句。标号short loc_4010C0表示case 37代码块的首地址,可修改为CASE_37,标号short loc_4010B1表示case 666代码块的首地址,可修改为CASE_666,标号short loc_4010A2表示case 10000代码块的首地址,可修改为CASE_10000。至此,这个switch结构分析完毕。

为了降低树的高度,在树的优化过程中,检测树的左子树或右子树能否满足if else优化、有序线性优化、非线性索引优化,利用这三种优化来降低树高度。选择哪种优化也是有顺序的,谁的效率最高,又满足其匹配条件,就可以被优先使用。以上三种优化都无法匹配,就会选择使用判定树。