switch
- 线性处理
24: int nIndex = 0; 01377EBE C7 45 F8 00 00 00 00 mov dword ptr [nIndex],0 25: scanf("%d", &nIndex); 01377EC5 8D 45 F8 lea eax,[nIndex] 01377EC8 50 push eax 01377EC9 68 50 AE 42 01 push offset string "%d" (0142AE50h) 01377ECE E8 1A 9A FF FF call _scanf (013718EDh) 01377ED3 83 C4 08 add esp,8 26: switch(nIndex) 01377ED6 8B 45 F8 mov eax,dword ptr [nIndex] 01377ED9 89 85 30 FF FF FF mov dword ptr [ebp-0D0h],eax 01377EDF 8B 8D 30 FF FF FF mov ecx,dword ptr [ebp-0D0h] 01377EE5 83 E9 01 sub ecx,1 //调整switch参数,对应地址表索引 01377EE8 89 8D 30 FF FF FF mov dword ptr [ebp-0D0h],ecx 01377EEE 83 BD 30 FF FF FF 06 cmp dword ptr [ebp-0D0h],6 01377EF5 77 65 ja $LN9+0Dh (01377F5Ch) //大于6,即switch内变量大于7,不存在case,跳出。 01377EF7 8B 95 30 FF FF FF mov edx,dword ptr [ebp-0D0h] 01377EFD FF 24 95 A0 7F 37 01 jmp dword ptr [edx*4+1377FA0h] //跳转到线性地址表 27: { 28: case 1: 29: printf("nIndex == 1"); 01377F04 …… 30: break; 01377F11 EB 49 jmp $LN9+0Dh (01377F5Ch) 31: case 2: 32: printf("nIndex == 2"); 01377F13 …… 33: break; 01377F20 EB 3A jmp $LN9+0Dh (01377F5Ch) 34: case 3: 35: printf("nIndex == 3"); 01377F22 …… 36: break; 01377F2F EB 2B jmp $LN9+0Dh (01377F5Ch) 37: case 5: 38: printf("nIndex == 5"); 01377F31 …… 39: break; 01377F3E EB 1C jmp $LN9+0Dh (01377F5Ch) 40: case 6: 41: printf("nIndex == 6"); 01377F40 …… 42: break; 01377F4D EB 0D jmp $LN9+0Dh (01377F5Ch) 43: case 7: 44: printf("nIndex == 7"); 01377F4F 68 C0 AE 42 01 push offset string "nIndex == 7" (0142AEC0h) 01377F54 E8 0C 95 FF FF call _printf (01371465h) 01377F59 83 C4 04 add esp,4 45: break;
地址表:
0x01377FA0 04 7f 37 01 ..7.//case:1 index=0
0x01377FA4 13 7f 37 01 ..7.//case:2 index=1
0x01377FA8 22 7f 37 01 ".7.//case:3 index=2
0x01377FAC 5c 7f 37 01 \.7.//end index=3
0x01377FB0 31 7f 37 01 1.7.//case:5 index=4
0x01377FB4 40 7f 37 01 @.7.//case:6 index=5
0x01377FB8 4f 7f 37 01 O.7.//case:7 index=6
- if···else方式处理
6: int i = 1; 0137802E C7 45 F8 01 00 00 00 mov dword ptr [i],1 7: scanf("%d", &i); 01378035 8D 45 F8 lea eax,[i] 01378038 50 push eax 01378039 68 50 AE 42 01 push offset string "%d" (0142AE50h) 0137803E E8 AA 98 FF FF call _scanf (013718EDh) 01378043 83 C4 08 add esp,8 8: switch(i){//进行switch比较,跳到不同的case块内,(所有的case块在一起,如果没有break,即不产生jmp跳出,则会向下顺序执行) 01378046 8B 45 F8 mov eax,dword ptr [i] 01378049 89 85 30 FF FF FF mov dword ptr [ebp-0D0h],eax 0137804F 83 BD 30 FF FF FF 01 cmp dword ptr [ebp-0D0h],1 01378056 74 14 je test_switch_if+5Ch (0137806Ch) 01378058 83 BD 30 FF FF FF 03 cmp dword ptr [ebp-0D0h],3 0137805F 74 1A je test_switch_if+6Bh (0137807Bh) 01378061 83 BD 30 FF FF FF 64 cmp dword ptr [ebp-0D0h],64h 01378068 74 20 je test_switch_if+7Ah (0137808Ah) 0137806A EB 2B jmp test_switch_if+87h (01378097h) 9: case 1: 10: printf("i == 1"); 0137806C 68 54 AE 42 01 push offset string "i == 1" (0142AE54h) 01378071 E8 EF 93 FF FF call _printf (01371465h) 01378076 83 C4 04 add esp,4 11: break; 01378079 EB 1C jmp test_switch_if+87h (01378097h) 12: case 3: 13: printf("i == 3"); 0137807B …… 14: break; 01378088 EB 0D jmp test_switch_if+87h (01378097h) 15: case 100: 16: printf("i == 100"); 0137808A …… 17: break;
- 非线性处理
52: int i = 0; 0137812E C7 45 F8 00 00 00 00 mov dword ptr [i],0 53: scanf("%d", &i); 01378135 8D 45 F8 lea eax,[i] 01378138 50 push eax 01378139 68 50 AE 42 01 push offset string "%d" (0142AE50h) 0137813E E8 AA 97 FF FF call _scanf (013718EDh) 01378143 83 C4 08 add esp,8 54: switch(i){ 01378146 8B 45 F8 mov eax,dword ptr [i] 01378149 89 85 30 FF FF FF mov dword ptr [ebp-0D0h],eax 0137814F 8B 8D 30 FF FF FF mov ecx,dword ptr [ebp-0D0h] 01378155 83 E9 01 sub ecx,1 01378158 89 8D 30 FF FF FF mov dword ptr [ebp-0D0h],ecx 0137815E 83 BD 30 FF FF FF 0E cmp dword ptr [ebp-0D0h],0Eh 01378165 77 6C ja $LN9+0Dh (013781D3h) 01378167 8B 95 30 FF FF FF mov edx,dword ptr [ebp-0D0h] 0137816D 0F B6 82 2C 82 37 01 movzx eax,byte ptr [edx+137822Ch] //在索引表中取索引 01378174 FF 24 85 10 82 37 01 jmp dword ptr [eax*4+1378210h] 55: case 1: 56: printf("i == 1"); 0137817B 68 54 AE 42 01 push offset string "i == 1" (0142AE54h) 01378180 E8 E0 92 FF FF call _printf (01371465h) 01378185 83 C4 04 add esp,4 57: break; 01378188 EB 49 jmp $LN9+0Dh (013781D3h) 58: case 2: 59: printf("i == 2"); 0137818A …… 60: break; 01378197 EB 3A jmp $LN9+0Dh (013781D3h) 61: case 3: 62: printf("i == 3"); 01378199 …… 63: break; 013781A6 EB 2B jmp $LN9+0Dh (013781D3h) 64: case 5: 65: printf("i == 5"); 013781A8 …… 66: break; 013781B5 EB 1C jmp $LN9+0Dh (013781D3h) 67: case 6: 68: printf("i == 6"); 013781B7 …… 69: break; 013781C4 EB 0D jmp $LN9+0Dh (013781D3h) 70: case 15: 71: printf("i == 15"); 013781C6 …… 72: break;
索引表(0-255),索引为1字节
0x0137822C 00 01 02 06 .... 0x01378230 03 04 06 06 .... 0x01378234 06 06 06 06 .... 0x01378238 06 06 05
地址表
0x01378210 7b 81 37 01 {?7. 0x01378214 8a 81 37 01 ??7. 0x01378218 99 81 37 01 ??7. 0x0137821C a8 81 37 01 ??7. 0x01378220 b7 81 37 01 ??7. 0x01378224 c6 81 37 01 ??7. 0x01378228 d3 81 37 01 ??7.
- 平衡树处理
最大优化(优选大小) (/O1)--体积优先
判定树:
81: switch(i){ 00D4AB6F 8B 45 FC mov eax,dword ptr [i] 00D4AB72 59 pop ecx 00D4AB73 59 pop ecx 00D4AB74 83 F8 23 cmp eax,23h 00D4AB77 7F 3B jg test_switch_tree+5Eh (0D4ABB4h) 00D4AB79 74 32 je test_switch_tree+57h (0D4ABADh) 00D4AB7B 48 dec eax //减一 不影响CF, 00D4AB7C 83 E8 01 sub eax,1 //减一 影响CF 00D4AB7F 74 25 je test_switch_tree+50h (0D4ABA6h) //case:2 00D4AB81 83 E8 01 sub eax,1 00D4AB84 74 19 je test_switch_tree+49h (0D4AB9Fh) //case:3 00D4AB86 83 E8 05 sub eax,5 00D4AB89 74 0D je test_switch_tree+42h (0D4AB98h) //case:8 00D4AB8B 48 dec eax 00D4AB8C 83 E8 01 sub eax,1 00D4AB8F 75 36 jne test_switch_tree+71h (0D4ABC7h) //default 91: case 10: 92: printf("i == 10\n"); 00D4AB91 B8 18 AF DF 00 mov eax,offset string "i == 10\n" (0DFAF18h) 93: break; 00D4AB96 EB 49 jmp test_switch_tree+8Bh (0D4ABE1h) 88: case 8: 89: printf("i == 8\n"); 00D4AB98 B8 0C AF DF 00 mov eax,offset string "i == 8\n" (0DFAF0Ch) 90: break; 00D4AB9D EB 42 jmp test_switch_tree+8Bh (0D4ABE1h) 85: case 3: 86: printf("i == 3\n"); 00D4AB9F B8 00 AF DF 00 mov eax,offset string "i == 3\n" (0DFAF00h) 87: break; 00D4ABA4 EB 3B jmp test_switch_tree+8Bh (0D4ABE1h) 82: case 2: 83: printf("i == 2\n"); 00D4ABA6 B8 F4 AE DF 00 mov eax,offset string "i == 2\n" (0DFAEF4h) 84: break; 00D4ABAB EB 34 jmp test_switch_tree+8Bh (0D4ABE1h) 94: case 35: 95: printf("i == 35\n"); 00D4ABAD B8 24 AF DF 00 mov eax,offset string "i == 35\n" (0DFAF24h) 96: break; 00D4ABB2 EB 2D jmp test_switch_tree+8Bh (0D4ABE1h) 81: switch(i){ 00D4ABB4 83 F8 25 cmp eax,25h 00D4ABB7 74 23 je test_switch_tree+86h (0D4ABDCh) //case:37 00D4ABB9 3D 9A 02 00 00 cmp eax,29Ah 00D4ABBE 74 15 je test_switch_tree+7Fh (0D4ABD5h) //case:666 00D4ABC0 3D 10 27 00 00 cmp eax,2710h 00D4ABC5 74 07 je test_switch_tree+78h (0D4ABCEh) //case:10000 106: default: 107: printf("default\n"); 00D4ABC7 B8 58 AF DF 00 mov eax,offset string "default\n" (0DFAF58h) 00D4ABCC EB 13 jmp test_switch_tree+8Bh (0D4ABE1h) 103: case 10000: 104: printf("i == 10000\n"); 00D4ABCE B8 48 AF DF 00 mov eax,offset string "i == 10000\n" (0DFAF48h) 105: break; 00D4ABD3 EB 0C jmp test_switch_tree+8Bh (0D4ABE1h) 99: break; 100: case 666: 101: printf("i == 666\n"); 00D4ABD5 B8 3C AF DF 00 mov eax,offset string "i == 666\n" (0DFAF3Ch) 102: break; 00D4ABDA EB 05 jmp test_switch_tree+8Bh (0D4ABE1h) 97: case 37: 98: printf("i == 37\n"); 00D4ABDC B8 30 AF DF 00 mov eax,offset string "i == 37\n" (0DFAF30h) 108: break;
为了降低树的高度,在树的优化过程中,检测树的左子树或右子树能否满足if else优化、有序线性优化、非线性索引优化,利用这三种优化来降低树高度。
选择哪种优化也是有顺序的,谁的效率最高,又满足其匹配条件,就可以被优先使用。以上三种优化都无法匹配,就会选择使用判定树。
79: int i = 8; 013782AE C7 45 F8 08 00 00 00 mov dword ptr [i],8 80: scanf("%d", &i); 013782B5 8D 45 F8 lea eax,[i] 013782B8 50 push eax 013782B9 68 50 AE 42 01 push offset string "%d" (0142AE50h) 013782BE E8 2A 96 FF FF call _scanf (013718EDh) 013782C3 83 C4 08 add esp,8 81: switch(i){ 013782C6 8B 45 F8 mov eax,dword ptr [i] 013782C9 89 85 30 FF FF FF mov dword ptr [ebp-0D0h],eax 013782CF 83 BD 30 FF FF FF 23 cmp dword ptr [ebp-0D0h],23h 013782D6 7F 36 jg test_switch_tree+7Eh (0137830Eh) //大于35,处理case:37,666,10000 013782D8 83 BD 30 FF FF FF 23 cmp dword ptr [ebp-0D0h],23h 013782DF 0F 84 88 00 00 00 je $LN7+0Fh (0137836Dh) //case:35 013782E5 8B 8D 30 FF FF FF mov ecx,dword ptr [ebp-0D0h] 013782EB 83 E9 02 sub ecx,2 013782EE 89 8D 30 FF FF FF mov dword ptr [ebp-0D0h],ecx 013782F4 83 BD 30 FF FF FF 08 cmp dword ptr [ebp-0D0h],8 //处理case:2,3,8,10 013782FB 0F 87 A8 00 00 00 ja $LN7+4Bh (013783A9h) 01378301 8B 95 30 FF FF FF mov edx,dword ptr [ebp-0D0h] 01378307 FF 24 95 F4 83 37 01 jmp dword ptr [edx*4+13783F4h] //使用地址表 0137830E 83 BD 30 FF FF FF 25 cmp dword ptr [ebp-0D0h],25h 01378315 74 65 je $LN7+1Eh (0137837Ch) //case:37 01378317 81 BD 30 FF FF FF 9A 02 00 00 cmp dword ptr [ebp-0D0h],29Ah 01378321 74 68 je $LN7+2Dh (0137838Bh) //case:6666 01378323 81 BD 30 FF FF FF 10 27 00 00 cmp dword ptr [ebp-0D0h],2710h 0137832D 74 6B je $LN7+3Ch (0137839Ah) //case:10000 0137832F EB 78 jmp $LN7+4Bh (013783A9h) //default 82: case 2: 83: printf("i == 2\n"); 01378331 68 F4 AE 42 01 push offset string "i == 2\n" (0142AEF4h) 01378336 E8 2A 91 FF FF call _printf (01371465h) 0137833B 83 C4 04 add esp,4 84: break; 0137833E EB 76 jmp $LN7+58h (013783B6h) 85: case 3: 86: printf("i == 3\n"); 01378340 68 00 AF 42 01 push offset string "i == 3\n" (0142AF00h) 01378345 E8 1B 91 FF FF call _printf (01371465h) 0137834A 83 C4 04 add esp,4 87: break; 0137834D EB 67 jmp $LN7+58h (013783B6h) 88: case 8: 89: printf("i == 8\n"); 0137834F 68 0C AF 42 01 push offset string "i == 8\n" (0142AF0Ch) 01378354 E8 0C 91 FF FF call _printf (01371465h) 01378359 83 C4 04 add esp,4 90: break; 0137835C EB 58 jmp $LN7+58h (013783B6h) 91: case 10: 92: printf("i == 10\n"); 0137835E 68 18 AF 42 01 push offset string "i == 10\n" (0142AF18h) 91: case 10: 92: printf("i == 10\n"); 01378363 E8 FD 90 FF FF call _printf (01371465h) 01378368 83 C4 04 add esp,4 93: break; 0137836B EB 49 jmp $LN7+58h (013783B6h) 94: case 35: 95: printf("i == 35\n"); 0137836D 68 24 AF 42 01 push offset string "i == 35\n" (0142AF24h) 01378372 E8 EE 90 FF FF call _printf (01371465h) 01378377 83 C4 04 add esp,4 96: break; 0137837A EB 3A jmp $LN7+58h (013783B6h) 97: case 37: 98: printf("i == 37\n"); 0137837C 68 30 AF 42 01 push offset string "i == 37\n" (0142AF30h) 01378381 E8 DF 90 FF FF call _printf (01371465h) 01378386 83 C4 04 add esp,4 99: break; 01378389 EB 2B jmp $LN7+58h (013783B6h) 100: case 666: 101: printf("i == 666\n"); 0137838B 68 3C AF 42 01 push offset string "i == 666\n" (0142AF3Ch) 01378390 E8 D0 90 FF FF call _printf (01371465h) 01378395 83 C4 04 add esp,4 102: break; 01378398 EB 1C jmp $LN7+58h (013783B6h) 103: case 10000: 104: printf("i == 10000\n"); 0137839A 68 48 AF 42 01 push offset string "i == 10000\n" (0142AF48h) 0137839F E8 C1 90 FF FF call _printf (01371465h) 013783A4 83 C4 04 add esp,4 105: break; 013783A7 EB 0D jmp $LN7+58h (013783B6h) 106: default: 107: printf("default\n"); 013783A9 68 58 AF 42 01 push offset string "default\n" (0142AF58h) 013783AE E8 B2 90 FF FF call _printf (01371465h) 013783B3 83 C4 04 add esp,4 108: break;
地址表
0x013783F4 31 83 37 01 1?7.//case:2 0x013783F8 40 83 37 01 @?7.//case:3 0x013783FC a9 83 37 01 ??7.//default 0x01378400 a9 83 37 01 ??7.//default 0x01378404 a9 83 37 01 ??7.//default 0x01378408 a9 83 37 01 ??7.//default 0x0137840C 4f 83 37 01 O?7.//case:8 0x01378410 a9 83 37 01 ??7.//default 0x01378414 5e 83 37 01 ^?7.//case:10