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优化、有序线性优化、非线性索引优化,利用这三种优化来降低树高度。选择哪种优化也是有顺序的,谁的效率最高,又满足其匹配条件,就可以被优先使用。以上三种优化都无法匹配,就会选择使用判定树。