C++ 反匯編：關于Switch陳述句的優化措施

流程控制陳述句是C語言中最基本的判斷陳述句，通常我們可以使用IF來構建多分支結構，但同樣可以使用Switch陳述句構建，Switch陳述句針對多分支的優化措施有4種形式，分別是，IF-ELSE優化，有序線性優化，非線性索引優化，平衡判定樹優化，

與IF陳述句結構不同，IF陳述句會在條件跳轉后緊跟陳述句塊，而SWITCH結構則將所有條件跳轉都放置在一起，判斷時需要重點觀察每個條件跳轉指令后面是否跟有陳述句塊，以辨別SWITCH分支結構，

在switch分支數小于4的情況下，編譯器將采用模擬IF-ELSE分支的方式構建SWITCH結構，這樣則無法發揮出SWITCH陳述句的優勢，當分支數大于3并且case的判斷值存在明顯線性關系時，Switch陳述句的優化特性才可以凸顯出來，

有序線性優化: 該優化方式將每個case陳述句塊的地址預先保存在陣列中，并依據此陣列查詢case陳述句塊對應的首地址，

首先代碼生成時會為case陳述句制作一個case地址表陣列，陣列中保存每個ease陳述句塊的首地址，并且下標以0開頭，在進入switch后先進行一次比較，檢查輸入的數值是否大于case值的最大值，

為了達到線性有序，對于沒有case對應的數值，編譯器以switch的結束地址或者default陳述句塊的首地址填充對應的表格項，

case線性地址表是一個有序表，

當switch為一個有序線性組合時，會對其case陳述句塊制作地址表，以減少比較跳轉次數，

在撰寫代碼時，我們無需自己排列case序列，編譯器編譯時會自動進行排序優化，先來撰寫一個簡單的代碼：

int main(int argc, char *argv[])
{
	int index = 0;

	scanf("%d", &index);

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

代碼經過反匯編后，我們可以注意到，首先用戶通過scanf輸入所需要執行的分支，因為分支陳述句下標從0開始，所以需要dec eax減去1，在進入switch陳述句之前，判斷輸入的下標是否高于6，如果高于則直接跳出switch，否則執行ds:[eax*4+0x401348]尋址，

004012B4 | FF15 B8304000            | call dword ptr ds:[<&scanf>]              |
004012BA | 8B45 FC                  | mov eax,dword ptr ss:[ebp-4]              |
004012BD | 83C4 08                  | add esp,8                                 |
004012C0 | 48                       | dec eax                                   | Switch陳述句獲取比例因子,需要減1
004012C1 | 83F8 06                  | cmp eax,6                                 | 首先對比輸入資料是否大于6
004012C4 | 77 6B                    | ja consoleapplication.401331              | 大于則說明Switch分支無對應結構 (則直接跳轉到結束)
004012C6 | FF2485 48134000          | jmp dword ptr ds:[eax*4+0x401348]         | 跳轉到指定代碼段

地址0x401348對應的就是每一個分支的首地址，跳轉后即可看到分支，

非線性索引優化: 如果兩個case值間隔較大，仍然使用switch的結尾地址或default地址代替地址表中缺少的case地址，這樣則會造成極大的空間浪費，

非線性的switch結構，可采用制作索引表的方式進行優化，索引表有兩張，1.case陳述句塊地址表，2.case陳述句塊索引表，

地址表中每一項保存一個case陳述句塊首地址，有幾個case陳述句塊或default陳述句塊，就保存幾項，結束地址在地址表中指揮保存一份，

索引表中保存了地址表中的下標值，索引表最多可容納256項，每項1位元組，所以case值不可超過1位元組，索引表也只能存盤256項索引編號，

在執行時需要通過索引表來查詢地址表，會多出一次查表的程序，因此效率上會有所下降，

004012B4 | FF15 B8304000            | call dword ptr ds:[<&scanf>]              |
004012BA | 8B45 FC                  | mov eax,dword ptr ss:[ebp-4]              |
004012BD | 83C4 08                  | add esp,8                                 |
004012C0 | 48                       | dec eax                                   | Switch陳述句獲取比例因子,需要減1
004012C1 | 3D FE000000              | cmp eax,FE                                | 首先對比輸入資料是否大于254
004012C6 | 0F87 80000000            | ja consoleapplication.40134C              | 跳轉到指定代碼段
004012CC | 0FB680 70134000          | movzx eax,byte ptr ds:[eax+0x401370]      | 從索引表找地址表下標
004012D3 | FF2485 54134000          | jmp dword ptr ds:[eax*4+0x401354]         | 比例因子尋找函式地址

首先movzx eax, byte ptr ds:[eax+0x401370]從索引表中找到地址表下標，

然后通過索引表找到索引值，并帶入jmp dword ptr ds:[eax*4+0x401354]找到地址表中的指定地址，地址表中每一個地址就代表一個分支結構里的函式，

這樣的優勢就是可以節約空間，每一個所以表欄位只占1位元組，如果兩個case差距較大同樣會指向同一個地址表中的地址，地址表相對來說會變得簡單，但這種查詢方式會產生兩次間接記憶體訪問，在效率上遠遠低于線性表方式，

平衡判定樹優化: 當最大case值與最小case值之差大于255時，則會采用判定樹優化，將每個case值作為一個節點，從節點中找出中間值作為根節點，以此形成一顆平衡二叉樹，以每個節點為判定值，大于和小于關系分別對應左子樹和右子樹，從而提高查詢效率，

如果打開編譯器體積優先，編譯器盡量會以二叉判定樹的方式來降低程式占用體積，如果無法使用以上優化方式，則需要將switch做成樹，

int main(int argc, char *argv[])
{
	int index = 0;

	scanf("%d", &index);

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

判定樹反匯編形式，

004012C0 | 83F8 0A                  | cmp eax,A                                 | A:'\n'
004012C3 | 7F 63                    | jg consoleapplication.401328              |
004012C5 | 74 4D                    | je consoleapplication.401314              |
004012C7 | 83E8 02                  | sub eax,2                                 |
004012CA | 74 34                    | je consoleapplication.401300              |
004012CC | 48                       | dec eax                                   |
004012CD | 74 1D                    | je consoleapplication.4012EC              |
004012CF | 83E8 05                  | sub eax,5                                 |
004012D2 | 0F85 97000000            | jne consoleapplication.40136F             |
004012D8 | 68 A0314000              | push consoleapplication.4031A0            | main.cpp:16, 4031A0:"index 8"
004012DD | FF15 B4304000            | call dword ptr ds:[<&printf>]             | main.cpp:20
004012E3 | 83C4 04                  | add esp,4                                 |

判定樹，通過增加多條分支結構，從中位數開始判斷，大于或小于分別走不同的分支，直到遇到函式地址位置，

為了降低數的高度，在優化程序中，會檢查代碼是否滿足if-else優化，有序線性優化，非線性索引優化，利用三種優化來降低樹高度，誰的效率高就優先使用誰，三種優化都無法匹配才會使用判定樹，

標籤：其他

上一篇：程式員薪資倒掛嚴重，只能跳槽換高薪，IT公司為什么不愿加錢留住老員工？

下一篇：Java 圖片裁剪，截取