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
02-11 05:00