选择结构，也称为switch语句，是计算机编程中的一种控制结构，用于根据表达式的值选择不同的执行路径。它允许程序根据表达式的值来决定执行哪个代码块，从而实现多分支选择逻辑。switch语句由一个表达式、多个case标签以及对应的代码块组成。程序会将表达式的值与每个case标签进行匹配，一旦找到匹配的case标签，程序将执行对应的代码块，并继续执行该代码块之后的代码，直到遇到break语句或者switch语句结束。
11.25 仿写有序线性优化
在switch分支数小于4的情况下，编译器将采用模拟IF-ELSE分支的方式构建SWITCH结构，这样则无法发挥出SWITCH语句的优势，当分支数大于3并且case的判断值存在明显线性关系时，Switch语句的优化特性才可以被凸显出来。
该优化方式将每个case语句块的首地址预先保存在数组(地址表)中，并依据寻址时传入的下标(下标以0开头)，在此数组中查询case语句块对应的首地址，取出首地址并跳转到指定分支上，并执行分支流程代码。
int main(int argc, char *argv[])
{
int index = 1;
switch (index)
{
case 1:
printf("index 1"); break;
case 2:
printf("index 2"); break;
case 3:
printf("index 3"); break;
case 6:
printf("index 6"); break;
case 7:
printf("index 7"); break;
default:
printf("default"); break;
}
return 0;
}首先我们手动构建MemArray跳转地址表，通过offset伪指令取出分支内存地址，并将分支地址拷贝到MemArray跳转表中，因为分支语句下标从0开始，所以需要dec ecx减去1，在进入switch语句之前，判断输入的下标是否高于6，如果高于则直接跳出switch，否则执行jmp dword ptr ds:[ecx * 4 MemArray]寻址并跳转到相应的分支上。
.386p
.model flat,stdcall
option casemap:none
include windows.inc
include kernel32.inc
includelib kernel32.lib
.data
MemArray DWORD 0,0,0,0,0,0,0dh
InputNumber DWORD ?
.code
main PROC
; 寻找第2个分支语句
mov dword ptr ds:[InputNumber],2
; 填充跳转地址表
mov dword ptr ds:[MemArray],offset S0
mov dword ptr ds:[MemArray 4],offset S1
mov dword ptr ds:[MemArray 8],offset S2
mov dword ptr ds:[MemArray 12],offset S3
mov dword ptr ds:[MemArray 16],offset S4
mov dword ptr ds:[MemArray 20],offset S5
mov dword ptr ds:[MemArray 24],offset Send
; 判断下标是否高于6高于则结束switch
mov ecx,dword ptr ds:[InputNumber]
dec ecx ; Switch语句获取比例因子,需要减1
cmp ecx,6 ; 首先对比输入数据是否大于6
ja lop_end ; 大于则说明Switch分支无对应结构 (则直接跳转到结束)
jmp dword ptr ds:[ecx * 4 MemArray] ; 否则直接寻址，找到对应的内存地址
S0:
mov eax,0
jmp lop_end
S1:
mov eax,1
jmp lop_end
S2:
mov eax,2
jmp lop_end
S3:
mov eax,3
jmp lop_end
S4:
mov eax,4
jmp lop_end
S5:
mov eax,5
jmp lop_end
Send:
mov eax,6
jmp lop_end
lop_end:
int 3
main ENDP
END main11.26 仿写非线性索引优化
如果两个case值间隔较大，仍然使用switch的结尾地址或default地址代替地址表中缺少的case地址，这样则会造成极大的空间浪费，对于这种非线性结构，可采用制作索引表的方式进行优化，但此方式需要通过索引表来查询地址表，会多出一次查表的过程，因此效率上会有所下降。
索引表需要两张表:
- case 语句块地址表：地址表中每一项保存一个case语句块首地址，有几个case语句块或default语句块，就保存几项，结束地址在地址表中只会保存一份。
- case 语句块索引表：索引表中保存了地址表中的下标值，索引表最多可容纳256项，每项1字节，所以case值不可超过1字节，索引表也只能存储256项索引编号。
我们在上方C代码基础上稍加改动,如下分支结构4,5默认是不存在的,也就是当用户选择4或5时,默认会执行6号分支,如果单独为4,5创建一个4字节存储,分支偏差小还能接受,一旦分支偏差过大,则会占用大量内存空间,此时就需要使用索引表来优化空间占用。
int main(int argc, char *argv[])
{
int index = 5;
switch (index)
{
case 1:
printf("index 1"); break;
case 2:
printf("index 2"); break;
case 3:
printf("index 3"); break;
case 6:
printf("index 6"); break;
case 7:
printf("index 7"); break;
}
return 0;
}这段C代码如果改成非线性优化则会呈现以下类型的汇编指令,与地址表差不多,索引表MemIndexTable中每一个字节对应一个地址表MemAddressTable的下标,如果该索引在4,5范围内,则会默认指向地址表MemAddressTable中同一块内存区域,这样即可解决内存资源浪费的问题。
.386p
.model flat,stdcall
option casemap:none
include windows.inc
include kernel32.inc
includelib kernel32.lib
.data
MemAddressTable DWORD 0,0,0,0,0,0dh
MemIndexTable BYTE 0,0,0,0,0,0,0,0dh
InputNumber DWORD ?
.code
main PROC
; 寻找第5个分支语句 对应S3
mov dword ptr ds:[InputNumber],5
; 填充地址表
mov dword ptr ds:[MemAddressTable],offset S0
mov dword ptr ds:[MemAddressTable 4],offset S1
mov dword ptr ds:[MemAddressTable 8],offset S2
mov dword ptr ds:[MemAddressTable 12],offset S3
mov dword ptr ds:[MemAddressTable 16],offset S4
; 填充索引表
mov byte ptr ds:[MemIndexTable],0 ; 对应S0
mov byte ptr ds:[MemIndexTable 1],1 ; 对应S1
mov byte ptr ds:[MemIndexTable 2],2 ; 对应S2
mov byte ptr ds:[MemIndexTable 3],3 ; 对应S3
mov byte ptr ds:[MemIndexTable 4],3 ; 对应S3
mov byte ptr ds:[MemIndexTable 5],3 ; 对应S3
mov byte ptr ds:[MemIndexTable 6],4 ; 对应S4
; 得到索引表的基地址
lea edx,MemIndexTable
; 定位到第5个分支上
mov ecx,dword ptr ds:[InputNumber]
dec ecx
cmp ecx,7
ja lop_end
; 关键定位算法 索引表找下标,下标找函数地址
movzx eax,byte ptr ds:[ecx edx] ; 从索引表找地址表下标
jmp dword ptr ds:[eax * 4 MemAddressTable] ; 比例因子寻找函数地址
S0:
mov eax,0
jmp lop_end
S1:
mov eax,1
jmp lop_end
S2:
mov eax,2
jmp lop_end
S3:
mov eax,3
jmp lop_end
S4:
mov eax,4
jmp lop_end
lop_end:
int 3
main ENDP
END main11.27 仿写平衡判定树优化
当最大case值与最小case值之差大于255时，则会采用判定树优化，将每个case值作为一个节点，从节点中找出中间值作为根节点，以此形成一颗平衡二叉树，以每个节点为判定值，大于和小于关系分别对应左子树和右子树，从而提高查询效率。
如果打开编译器体积优先，编译器尽量会以二叉判定树的方式来降低程序占用体积，如果无法使用前两种优化方式时，则需要将switch做成一棵树，首先编译C代码。
代码语言：javascript复制int main(int argc, char *argv[])
{
int index = 15;
switch (index)
{
case 2:
printf("index 2"); break;
case 3:
printf("index 3"); break;
case 8:
printf("index 8"); break;
case 10:
printf("index 10"); break;
case 35:
printf("index 35"); break;
case 37:
printf("index 37"); break;
case 666:
printf("index 666"); break;
}
return 0;
}判定树，通过增加多条分支结构，从中位数10开始判断，大于走左子树或小于走右子树分支，直到遇到符合条件的分支为止，这段汇编代码编写时应格外注意次序，否则容易写乱套，不论如何本人还是按照编译器习惯将其转换为了对等汇编语句。
代码语言：javascript复制 .386p
.model flat,stdcall
option casemap:none
include windows.inc
include kernel32.inc
includelib kernel32.lib
.data
InputNumber DWORD ?
; 排列后 左子树大/右子树小 666 37 35 [10] 2 3 8
.code
main PROC
mov dword ptr ds:[InputNumber],40
; 先判断输入的数据是否大于最大分支
mov eax,666
cmp dword ptr ds:[InputNumber],eax
jg lop_end
; 取出中位数10作为第一个判定条件
cmp dword ptr ds:[InputNumber],10
jg left
je S10
cmp dword ptr ds:[InputNumber],8 ; 对比8
jle S8
cmp dword ptr ds:[InputNumber],7 ; 对比7
jle S37
cmp dword ptr ds:[InputNumber],2 ; 对比2
jle S2
jmp lop_end
left:
cmp dword ptr ds:[InputNumber],35 ; 对比35
jle S35
cmp dword ptr ds:[InputNumber],37 ; 对比37
jle S37
cmp dword ptr ds:[InputNumber],666 ; 对比666
jle S35
jmp lop_end
S2:
mov eax,2
jmp lop_end
S3:
mov eax,3
jmp lop_end
S8:
mov eax,8
jmp lop_end
S10:
mov eax,10
jmp lop_end
S35:
mov eax,35
jmp lop_end
S37:
mov eax,37
jmp lop_end
S666:
mov eax,666
jmp lop_end
lop_end:
int 3
main ENDP
END main为了降低判定树的高度，在优化过程中，会检查代码是否满足if-else优化，有序线性优化，非线性索引优化，利用三种优化来降低树高度，谁的效率高就优先使用谁，如果三种优化都无法匹配才会使用判定树。
本文作者： 王瑞 本文链接： https://www.lyshark.com/post/c44b7f4.html 版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
