選擇結(jié)構(gòu)，也稱(chēng)為switch語(yǔ)句，是計(jì)算機(jī)編程中的一種控制結(jié)構(gòu)，用于根據(jù)表達(dá)式的值選擇不同的執(zhí)行路徑。它允許程序根據(jù)表達(dá)式的值來(lái)決定執(zhí)行哪個(gè)代碼塊，從而實(shí)現(xiàn)多分支選擇邏輯。switch語(yǔ)句由一個(gè)表達(dá)式、多個(gè)case標(biāo)簽以及對(duì)應(yīng)的代碼塊組成。程序會(huì)將表達(dá)式的值與每個(gè)case標(biāo)簽進(jìn)行匹配，一旦找到匹配的case標(biāo)簽，程序?qū)?zhí)行對(duì)應(yīng)的代碼塊，并繼續(xù)執(zhí)行該代碼塊之后的代碼，直到遇到break語(yǔ)句或者switch語(yǔ)句結(jié)束。

11.25 仿寫(xiě)有序線性?xún)?yōu)化

在switch分支數(shù)小于4的情況下，編譯器將采用模擬IF-ELSE分支的方式構(gòu)建SWITCH結(jié)構(gòu)，這樣則無(wú)法發(fā)揮出SWITCH語(yǔ)句的優(yōu)勢(shì)，當(dāng)分支數(shù)大于3并且case的判斷值存在明顯線性關(guān)系時(shí)，Switch語(yǔ)句的優(yōu)化特性才可以被凸顯出來(lái)。

該優(yōu)化方式將每個(gè)case語(yǔ)句塊的首地址預(yù)先保存在數(shù)組(地址表)中，并依據(jù)尋址時(shí)傳入的下標(biāo)(下標(biāo)以0開(kāi)頭)，在此數(shù)組中查詢(xún)case語(yǔ)句塊對(duì)應(yīng)的首地址，取出首地址并跳轉(zhuǎn)到指定分支上，并執(zhí)行分支流程代碼。

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;
}

首先我們手動(dòng)構(gòu)建MemArray跳轉(zhuǎn)地址表，通過(guò)offset偽指令取出分支內(nèi)存地址，并將分支地址拷貝到MemArray跳轉(zhuǎn)表中，因?yàn)榉种дZ(yǔ)句下標(biāo)從0開(kāi)始，所以需要dec ecx減去1，在進(jìn)入switch語(yǔ)句之前，判斷輸入的下標(biāo)是否高于6，如果高于則直接跳出switch，否則執(zhí)行jmp dword ptr ds:[ecx * 4 +MemArray]尋址并跳轉(zhuǎn)到相應(yīng)的分支上。

????.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個(gè)分支語(yǔ)句
??????mov?dword?ptr?ds:[InputNumber],2
????
??????;?填充跳轉(zhuǎn)地址表
??????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
??????
??????;?判斷下標(biāo)是否高于6高于則結(jié)束switch
??????mov?ecx,dword?ptr?ds:[InputNumber]
??????dec?ecx?????????????????????????;?Switch語(yǔ)句獲取比例因子,需要減1
??????cmp?ecx,6???????????????????????;?首先對(duì)比輸入數(shù)據(jù)是否大于6
??????ja?lop_end??????????????????????;?大于則說(shuō)明Switch分支無(wú)對(duì)應(yīng)結(jié)構(gòu)?(則直接跳轉(zhuǎn)到結(jié)束)
??????
??????jmp?dword?ptr?ds:[ecx?*?4?+MemArray]?;?否則直接尋址，找到對(duì)應(yīng)的內(nèi)存地址
??????
????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?main

11.26 仿寫(xiě)非線性索引優(yōu)化

如果兩個(gè)case值間隔較大，仍然使用switch的結(jié)尾地址或default地址代替地址表中缺少的case地址，這樣則會(huì)造成極大的空間浪費(fèi)，對(duì)于這種非線性結(jié)構(gòu)，可采用制作索引表的方式進(jìn)行優(yōu)化，但此方式需要通過(guò)索引表來(lái)查詢(xún)地址表，會(huì)多出一次查表的過(guò)程，因此效率上會(huì)有所下降。

索引表需要兩張表:

• ??case 語(yǔ)句塊地址表：地址表中每一項(xiàng)保存一個(gè)case語(yǔ)句塊首地址，有幾個(gè)case語(yǔ)句塊或default語(yǔ)句塊，就保存幾項(xiàng)，結(jié)束地址在地址表中只會(huì)保存一份。

• ??case 語(yǔ)句塊索引表：索引表中保存了地址表中的下標(biāo)值，索引表最多可容納256項(xiàng)，每項(xiàng)1字節(jié)，所以case值不可超過(guò)1字節(jié)，索引表也只能存儲(chǔ)256項(xiàng)索引編號(hào)。

我們?cè)谏戏紺代碼基礎(chǔ)上稍加改動(dòng),如下分支結(jié)構(gòu)4,5默認(rèn)是不存在的,也就是當(dāng)用戶(hù)選擇4或5時(shí),默認(rèn)會(huì)執(zhí)行6號(hào)分支,如果單獨(dú)為4,5創(chuàng)建一個(gè)4字節(jié)存儲(chǔ),分支偏差小還能接受,一旦分支偏差過(guò)大,則會(huì)占用大量?jī)?nèi)存空間,此時(shí)就需要使用索引表來(lái)優(yōu)化空間占用。

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代碼如果改成非線性?xún)?yōu)化則會(huì)呈現(xiàn)以下類(lèi)型的匯編指令,與地址表差不多,索引表MemIndexTable中每一個(gè)字節(jié)對(duì)應(yīng)一個(gè)地址表MemAddressTable的下標(biāo),如果該索引在4,5范圍內(nèi),則會(huì)默認(rèn)指向地址表MemAddressTable中同一塊內(nèi)存區(qū)域,這樣即可解決內(nèi)存資源浪費(fèi)的問(wèn)題。

????.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個(gè)分支語(yǔ)句?對(duì)應(yīng)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????????????;?對(duì)應(yīng)S0
??????mov?byte?ptr?ds:[MemIndexTable?+?1],1????????;?對(duì)應(yīng)S1
??????mov?byte?ptr?ds:[MemIndexTable?+?2],2????????;?對(duì)應(yīng)S2
??????mov?byte?ptr?ds:[MemIndexTable?+?3],3????????;?對(duì)應(yīng)S3
??????mov?byte?ptr?ds:[MemIndexTable?+?4],3????????;?對(duì)應(yīng)S3
??????mov?byte?ptr?ds:[MemIndexTable?+?5],3????????;?對(duì)應(yīng)S3
??????mov?byte?ptr?ds:[MemIndexTable?+?6],4????????;?對(duì)應(yīng)S4
??????
??????;?得到索引表的基地址
??????lea?edx,MemIndexTable
??????
??????;?定位到第5個(gè)分支上
??????mov?ecx,dword?ptr?ds:[InputNumber]
??????dec?ecx
??????cmp?ecx,7
??????ja?lop_end
??????
??????;?關(guān)鍵定位算法?索引表找下標(biāo),下標(biāo)找函數(shù)地址
??????movzx?eax,byte?ptr?ds:[ecx?+?edx]?????????????????;?從索引表找地址表下標(biāo)
??????jmp?dword?ptr?ds:[eax?*?4?+?MemAddressTable]??????;?比例因子尋找函數(shù)地址
??????
????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?main

11.27 仿寫(xiě)平衡判定樹(shù)優(yōu)化

當(dāng)最大case值與最小case值之差大于255時(shí)，則會(huì)采用判定樹(shù)優(yōu)化，將每個(gè)case值作為一個(gè)節(jié)點(diǎn)，從節(jié)點(diǎn)中找出中間值作為根節(jié)點(diǎn)，以此形成一顆平衡二叉樹(shù)，以每個(gè)節(jié)點(diǎn)為判定值，大于和小于關(guān)系分別對(duì)應(yīng)左子樹(shù)和右子樹(shù)，從而提高查詢(xún)效率。

如果打開(kāi)編譯器體積優(yōu)先，編譯器盡量會(huì)以二叉判定樹(shù)的方式來(lái)降低程序占用體積，如果無(wú)法使用前兩種優(yōu)化方式時(shí)，則需要將switch做成一棵樹(shù)，首先編譯C代碼。

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;
}

判定樹(shù)，通過(guò)增加多條分支結(jié)構(gòu)，從中位數(shù)10開(kāi)始判斷，大于走左子樹(shù)或小于走右子樹(shù)分支，直到遇到符合條件的分支為止，這段匯編代碼編寫(xiě)時(shí)應(yīng)格外注意次序，否則容易寫(xiě)亂套，不論如何本人還是按照編譯器習(xí)慣將其轉(zhuǎn)換為了對(duì)等匯編語(yǔ)句。

????.386p
????.model?flat,stdcall
????option?casemap:none

include?windows.inc
include?kernel32.inc
includelib?kernel32.lib

.data
????InputNumber?DWORD??
????;?排列后?左子樹(shù)大/右子樹(shù)小?666?37?35?[10]?2?3?8

.code
????main?PROC
??????
??????mov?dword?ptr?ds:[InputNumber],40
??????
??????;?先判斷輸入的數(shù)據(jù)是否大于最大分支
??????mov?eax,666
??????cmp?dword?ptr?ds:[InputNumber],eax
??????jg?lop_end

??????;?取出中位數(shù)10作為第一個(gè)判定條件
??????cmp?dword?ptr?ds:[InputNumber],10
??????jg?left
??????je?S10
??????
??????cmp?dword?ptr?ds:[InputNumber],8?????;?對(duì)比8
??????jle?S8
??????
??????cmp?dword?ptr?ds:[InputNumber],7?????;?對(duì)比7
??????jle?S37
??????
??????cmp?dword?ptr?ds:[InputNumber],2?????;?對(duì)比2
??????jle?S2
??????jmp?lop_end
??????
????left:
??????cmp?dword?ptr?ds:[InputNumber],35?????;?對(duì)比35
??????jle?S35
??????
??????cmp?dword?ptr?ds:[InputNumber],37?????;?對(duì)比37
??????jle?S37
??????
??????cmp?dword?ptr?ds:[InputNumber],666????;?對(duì)比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

為了降低判定樹(shù)的高度，在優(yōu)化過(guò)程中，會(huì)檢查代碼是否滿(mǎn)足if-else優(yōu)化，有序線性?xún)?yōu)化，非線性索引優(yōu)化，利用三種優(yōu)化來(lái)降低樹(shù)高度，誰(shuí)的效率高就優(yōu)先使用誰(shuí)，如果三種優(yōu)化都無(wú)法匹配才會(huì)使用判定樹(shù)。

本文作者： 王瑞 本文鏈接： https://www.lyshark.com/post/c44b7f4.html 版權(quán)聲明： 本博客所有文章除特別聲明外，均采用 BY-NC-SA 許可協(xié)議。轉(zhuǎn)載請(qǐng)注明出處！