c++中switch语句的反汇编以及优化

概述

c++的switch语句在汇编层面有着独特的表现形式以及优化方案，这篇文章就带大家一起探索其中的奥秘。本文的代码均使用vs2022中编写并编译。
温馨提示，本文代码较多，建议使用PC进行阅读。建议大家跟着动手操作一遍，更有效果。
我们把switch语句分成了三种情况

• case情况小于4
  
• 线性switch语句
  
• 非线性witch语句
  
• case的情况大于255
  

分成这些情况有助于大家由浅至深理解switch语句的汇编表现形式以及编译器对其的优化。下面我们来逐个情况分析。
case情况小于4

我们先讨论最特殊的情况，先给出源代码：

1. #include <stdio.h>
3. int main(int argc, char argv[])
4. {
5.         int n;
6.         scanf_s("%d", &n);
8.         switch (n)
9.         {
10.         case 12:
11.                 printf("n == 13");
12.                 break;
13.         case 9:
14.                 printf("n == 9");
15.                 break;
16.         case 100:
17.                 printf("n == 100");
18.                 break;
19.         default:
20.                 break;
21.         }
23.         return 0;
24. }

复制代码

代码十分简单，由三种case和一个default组成。在switch处下断点，我们先在debug模式下编译，并查看从switch语句开始处的反汇编代码。

1. 00007FF76CBB19DE 8B 45 04             mov         eax,dword ptr [n]  
2. 00007FF76CBB19E1 89 85 D4 00 00 00    mov         dword ptr [rbp+0D4h],eax  
3. 00007FF76CBB19E7 83 BD D4 00 00 00 09 cmp         dword ptr [rbp+0D4h],9  
4. 00007FF76CBB19EE 74 23                je          __$EncStackInitStart+7Ch (07FF76CBB1A13h)  
5. 00007FF76CBB19F0 83 BD D4 00 00 00 0C cmp         dword ptr [rbp+0D4h],0Ch  
6. 00007FF76CBB19F7 74 0B                je          __$EncStackInitStart+6Dh (07FF76CBB1A04h)  
7. 00007FF76CBB19F9 83 BD D4 00 00 00 64 cmp         dword ptr [rbp+0D4h],64h  
8. 00007FF76CBB1A00 74 20                je          __$EncStackInitStart+8Bh (07FF76CBB1A22h)  
9. 00007FF76CBB1A02 EB 2B                jmp         __$EncStackInitStart+98h (07FF76CBB1A2Fh)  
10. 00007FF76CBB1A04 48 8D 0D 1D 93 00 00 lea         rcx,[string "n == 12" (07FF76CBBAD28h)]  
11. 00007FF76CBB1A0B E8 8A F7 FF FF       call        printf (07FF76CBB119Ah)  
12. 00007FF76CBB1A10 90                   nop  
13. 00007FF76CBB1A11 EB 1C                jmp         __$EncStackInitStart+98h (07FF76CBB1A2Fh)  
14. 00007FF76CBB1A13 48 8D 0D 1A 93 00 00 lea         rcx,[string "n == 9" (07FF76CBBAD34h)]  
15. 00007FF76CBB1A1A E8 7B F7 FF FF       call        printf (07FF76CBB119Ah)  
16. 00007FF76CBB1A1F 90                   nop  
17. 00007FF76CBB1A20 EB 0D                jmp         __$EncStackInitStart+98h (07FF76CBB1A2Fh)  
18. 00007FF76CBB1A22 48 8D 0D 17 93 00 00 lea         rcx,[string "n == 100" (07FF76CBBAD40h)]  
19. 00007FF76CBB1A29 E8 6C F7 FF FF       call        printf (07FF76CBB119Ah)  
20. 00007FF76CBB1A2E 90                   nop  
21. 00007FF76CBB1A2F 33 C0                xor         eax,eax

复制代码

程序要求先从控制台输入n的值，笔者这里输入了200。随后代码运行至switch语句处。从汇编代码中不难发现，在case情况小于4的时候，汇编代码只是将n按顺序与case的情况进行比较，匹配成功则直接跳转到对应的语句块处运行，执行完对应情况的语句之后，使用jmp跳转到整个switch语句的结束地址处。我们把编译模式切换到Release，发现汇编代码依然如此。
再会看汇编代码，我们发现匹配比较的代码集中在一处，各个情况执行的代码又集中在另一处，这其实解释了switch语句的穿透问题，如果不加break语句，就会执行之后所有case语句块。而加上了break之后，每个case的语句块的汇编代码中就多了jmp指令跳转到switch语句块的结束地址处，就不会有穿透问题了。
从汇编代码中来看，switch语句的汇编形式似乎并没有什么特殊之处，release和debug产生的汇编代码也没有什么不同，似乎没有优化之处。但是请注意，这只是switch语句最简单的形式，接下来我们讨论switch语句的第二种形式。
线性switch

先来解释什么是线性switch。如果case中的情况近似满足线性关系时（1，2，3，4，5），这种形式switch语句就是线性switch。比如下面的代码：

1. #include <stdio.h>  
2. int main(int argc, char* argv[]) {
3.         int n = 1;
4.         if (scanf_s("%d", &n) != 1) {
5.                 printf("输入无效，请输入一个整数。\n");
6.                 return 1;
7.         }
8.         switch (n) {
9.         case 1:
10.                 printf("n == 1");
11.                 break;
12.         case 2:
13.                 printf("n == 2");
14.                 break;
15.         case 3:
16.                 printf("n == 3");
17.                 break;
18.         case 5:
19.                 printf("n == 5");
20.                 break;
21.         case 6:
22.                 printf("n == 6");
23.                 break;
24.         case 7:
25.                 printf("n == 7");
26.                 break;
27.         }  
28.         return 0;
29. }

复制代码

代码中的case列表为：1，2，3，5，6，7。近似满足线性关系。依然在switch语句的入口处下断点，编译选项为debug，输入n的值为7。得到从switch语句块开始的反汇编代码如下所示，建议读者先粗略浏览一下代码：

1. 00007FF68EA11A00 8B 45 04             mov         eax,dword ptr [n]  
2. 00007FF68EA11A03 89 85 D4 00 00 00    mov         dword ptr [rbp+0D4h],eax  
3. 00007FF68EA11A09 8B 85 D4 00 00 00    mov         eax,dword ptr [rbp+0D4h]  
4. 00007FF68EA11A0F FF C8                dec         eax  
5. 00007FF68EA11A11 89 85 D4 00 00 00    mov         dword ptr [rbp+0D4h],eax  
6. 00007FF68EA11A17 83 BD D4 00 00 00 06 cmp         dword ptr [rbp+0D4h],6  
7. 00007FF68EA11A1E 77 72                ja          $LN10+0Dh (07FF68EA11A92h)  
8. 00007FF68EA11A20 48 63 85 D4 00 00 00 movsxd      rax,dword ptr [rbp+0D4h]  
9. 00007FF68EA11A27 48 8D 0D D2 E5 FE FF lea         rcx,[__ImageBase (07FF68EA00000h)]  
10. 00007FF68EA11A2E 8B 84 81 C4 1A 01 00 mov         eax,dword ptr [rcx+rax*4+11AC4h]  
11. 00007FF68EA11A35 48 03 C1             add         rax,rcx  
12. 00007FF68EA11A38 FF E0                jmp         rax  
13. 00007FF68EA11A3A 48 8D 0D 0B 93 00 00 lea         rcx,[string "n == 1" (07FF68EA1AD4Ch)]  
14. 00007FF68EA11A41 E8 54 F7 FF FF       call        printf (07FF68EA1119Ah)  
15. 00007FF68EA11A46 90                   nop  
16. 00007FF68EA11A47 EB 49                jmp         $LN10+0Dh (07FF68EA11A92h)  
17. 00007FF68EA11A49 48 8D 0D 04 93 00 00 lea         rcx,[string "n == 2" (07FF68EA1AD54h)]  
18. 00007FF68EA11A50 E8 45 F7 FF FF       call        printf (07FF68EA1119Ah)  
19. 00007FF68EA11A55 90                   nop  
20. 00007FF68EA11A56 EB 3A                jmp         $LN10+0Dh (07FF68EA11A92h)  
21. 00007FF68EA11A58 48 8D 0D FD 92 00 00 lea         rcx,[string "n == 3" (07FF68EA1AD5Ch)]  
22. 00007FF68EA11A5F E8 36 F7 FF FF       call        printf (07FF68EA1119Ah)  
23. 00007FF68EA11A64 90                   nop  
24. 00007FF68EA11A65 EB 2B                jmp         $LN10+0Dh (07FF68EA11A92h)  
25. 00007FF68EA11A67 48 8D 0D F6 92 00 00 lea         rcx,[string "n == 5" (07FF68EA1AD64h)]  
26. 00007FF68EA11A6E E8 27 F7 FF FF       call        printf (07FF68EA1119Ah)  
27. 00007FF68EA11A73 90                   nop  
28. 00007FF68EA11A74 EB 1C                jmp         $LN10+0Dh (07FF68EA11A92h)  
29. 00007FF68EA11A76 48 8D 0D EF 92 00 00 lea         rcx,[string "n == 6" (07FF68EA1AD6Ch)]  
30. 00007FF68EA11A7D E8 18 F7 FF FF       call        printf (07FF68EA1119Ah)  
31. 00007FF68EA11A82 90                   nop  
32. 00007FF68EA11A83 EB 0D                jmp         $LN10+0Dh (07FF68EA11A92h)  
33. 00007FF68EA11A85 48 8D 0D E8 92 00 00 lea         rcx,[string "n == 7" (07FF68EA1AD74h)]  
34. 00007FF68EA11A8C E8 09 F7 FF FF       call        printf (07FF68EA1119Ah)  
35. 00007FF68EA11A91 90                   nop  
36. 00007FF68EA11A92 33 C0                xor         eax,eax

复制代码

这里的汇编代码令人困惑，明明有如此多种case情况，为何汇编代码中没有很多的比较语句，而且为何要让n的值减一，并使用cmp指令让n与一个毫不相干的数字6进行比较。更令人困惑的是，在与6比较完之后，又经过了一系列运算得到一个地址，直接使用jmp指令跳转到那个地址（调试程序之后我们发现跳转到的地址就是正确的case语句块的地址）。接下来为大家解惑。
直接说重点：对于线性switch语句，编译器采用了地址数组的优化方案。编译器将n的值作为下标，用来访问有各个case代码块偏移首地址组成的数组，用访问到的偏移首地址加上模块加载地址的到case语句块的绝对地址，直接jmp过去即可。如下图所示：

注意，与源代码中的case情况相比，编译器添加了一个源代码中不存在case 3的情况，这是为了形式线性的地址数组所做的添加，可以看到case 3语句块的首地址是指向switch语句的结束地址的，这与源代码中不存在case 3的事实相符合。
因为数组下标从0开始，所以对于n要自减一。然后用自减后的n与6进行比较，6是7自减一得到的，代表数组最后一个元素的下标，如果n大于6，直接跳转到switch语句块的结束地址或default语句块的首地址（如果有的话）。

1. 00007FF68EA11A00 8B 45 04             mov         eax,dword ptr [n]
2. 00007FF68EA11A03 89 85 D4 00 00 00    mov         dword ptr [rbp+0D4h],eax
3. 00007FF68EA11A09 8B 85 D4 00 00 00    mov         eax,dword ptr [rbp+0D4h]
4. 00007FF68EA11A0F FF C8                dec         eax
5. 00007FF68EA11A11 89 85 D4 00 00 00    mov         dword ptr [rbp+0D4h],eax
6. 00007FF68EA11A17 83 BD D4 00 00 00 06 cmp         dword ptr [rbp+0D4h],6
7. 00007FF68EA11A1E 77 72                ja          $LN10+0Dh(07FF68EA11A92h)

复制代码

若跳转不成功，则开始计算正确的case语句块的偏移首地址。计算过程如下，首先加载了一个符号名称为__ImageBase的地址，如果了解程序的装载过程就知道这个地址就是当前.exe文件在虚拟地址空间的首地址。随后计算了一条表达式：__ImageBase+n*4+0x11AC4。在这条表达式中，0x11AC4代表地址数组的首地址，该地址是相对于文件起始地址或当前模块的加载地址（在这里为__ImageBase）。我们在内存窗口中定位到该地址处：

图中红色的圈代表地址数组的起始位置（00007FF785FC11A4）和结束位置。观察地址数组，发现它的每个元素占四个字节，共七个元素。这与上文画出的地址数组图情况一致。这也解释了为什么n要乘以4：定位到正确的地址的第一个字节。。表达式还加上了__ImageBase，这是为了定位到正确的case语句块的绝对地址。我们输入的n是7，对应数组中case 7代码块的偏移地址，也就是00001181（因为Intel是小端存储所以逆序），加上模块加载地址后得到了case 7语句块的绝对地址。大家可以用数组中的偏移地址对应一下下图中的指令的地址低两位，就明白是怎么一回事了。

因为最开始给出的汇编代码是在vs2022中的，截图中的汇编代码和内存是在x96中的，所以两者的地址看起来不一样，但原理是一样的。得到绝对地址之后使用无条件跳转指令跳转过去即可。
非线性switch

对于难以形成线性地址地址数组的switch语句，编译器采用了另一种优化方案。先给出程序源代码：

1. #include <stdio.h>
2. int main(int argc, char* argv[]) {
3.         int n = 0;
4.         scanf_s("%d", &n);
5.         switch (n) {
6.         case 1:
7.                 printf("n == 1");
8.                 break;
9.         case 2:
10.                 printf("n == 2");
11.                 break;
12.         case 3:
13.                 printf("n == 3");
14.                 break;
15.         case 5:
16.                 printf("n == 5");
17.                 break;
18.         case 6:
19.                 printf("n == 6");
20.                 break;
21.         case 255:
22.                 printf("n == 255");
23.                 break;
24.         }
25.         return 0;
26. }

复制代码

这份代码中case的情况比较稀疏，如果还像之前一样采用为1到255中case情况创建一个大小为255*4个字节的地址数组，这无疑是十分浪费空间的。为此编译器采用了索引表加地址表的优化方式。
先粗略解释一下这种优化方式。索引表是为访问地址数组提供索引的数组，它的大小为最大case的值减去最小case的值，它存储着地址数组的下标。我们使用n作为下标访问索引表，得到的元素既是地址表数组的下标。随后就是和线性switch一样的计算过程，得到最终的case语句块的绝对地址，使用无条件跳转即可。如下图：

为了避免纸上谈兵，我们在release模式下生成可执行文件，使用x96反汇编看看具体的细节。同样我们只关注switch语句的部分。在这里，我们输入n的值为200。

我们发现，在汇编代码的开始部分，依然是将n的值减一后与0xFE（254）进行比较，若大于则直接跳转到switch语句的结束地址处。
若跳转失败的话，就开始利用n-1访问索引表。为了访问索引表，我们需要取得索引表的起始地址，在这里是用模块加载地址（rdx）加上0x11A0得到的。因为索引表中每个元素大小为1，所以直接加上n的值，得到了正确的元素的地址。我们利用该元素执行和线性switch一样的计算，即可得到正确的case语句块的地址。
在内存中，我们访问索引表的首地址，如下图，可以发现和上图是一样的。索引表的大小是最大case的值减去最小case的值的差。

可以看到，使用这种优化方案，编译器无需为每种case情况都生成一个对应的地址，这大大减小了地址数组的长度。
case的数量大于255

上一章中说过：索引表的元素大小为一个字节，也就是说索引表最多只能表示255中case的情况，如果case的情况数目大于255，编译器又该如何处理呢？
在这种情况下，编译器可采用另一种优化方案——判定树，即将每个case值作为一个节点，找到这些节点的中间值作为根节点，以此形成一棵二叉平衡树，以每个节点为判定值，大于和小于关系分别对应左子树和右子树，这样可以提高效率。
先给出源代码：

1. #include <stdio.h>
2. int main(int argc, char* argv[]) {
3.         int n = 0;
4.         scanf_s("%d", &n);
5.         switch (n) {
6.         case 2:
7.                 printf("n == 2\n");
8.                 break;
9.         case 3:
10.                 printf("n == 3\n");
11.                 break;
12.         case 8:
13.                 printf("n == 8\n");
14.                 break;
15.         case 10:
16.                 printf("n == 10\n");
17.                 break;
18.         case 35:
19.                 printf("n == 35\n");
20.                 break;
21.         case 37:
22.                 printf("n == 37\n");
23.                 break;
24.         case 666:
25.                 printf("n == 666\n");
26.                 break;
27.         default:
28.                 printf("default\n");
29.                 break;
30.         }
31.         return 0;
32. }

复制代码

在release编译选项下生成并输入n的值为37，反汇编后如下图所示：

编译器生成的判定树如下图：

这样看或许不够明显，我们使用IDA得到可视化视图：

这样以来汇编代码就很好理解了。同时应该注意，在优化过程中，检测树的左子树或右子树能否满足if…else…优化、有序线性优化、非线性索引优化，利用这3种优化来降低树的高度。选择优化也是有条件的，那就是选择效率最高，又满足匹配条件的。如果以上3种优化都无法匹配，就会选择使用判定树进行优化。
总结

对于switch的优化还有许多细节没有讲到，希望大家动手体会一下逆向还原的过程，对理解switch的反汇编及优化大有裨益。

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！