首页 > 逆向调试 > 编译器对switch case结构的优化

编译器对switch case结构的优化

在使用IDA分析Crack Me的时候,发现IDA对switch case结构的分析很是清晰,还发现了一个jump table for switch statement,也就是所谓的跳转表了,是编译器优化的结果。对于case分支的值是连续的那种,所有分支的跳转地址都会存入一个数组之中,然后通过case的值来寻址,如果值超出边界则直接跳到default分支所在地址。

.text:004010EA                 align 4
.text:004010EC off_4010EC      dd offset loc_401038    ; DATA XREF: _wmain+31
.text:004010EC                 dd offset loc_40104B    ; jump table for switch statement
.text:004010EC                 dd offset loc_40105E
.text:004010EC                 dd offset loc_401071
.text:004010EC                 dd offset loc_401084
.text:004010EC                 dd offset loc_401097
.text:004010EC                 dd offset loc_4010AA
.text:004010EC                 dd offset loc_4010BD
.text:00401000                 push    ecx
.text:00401001                 push    esi
.text:00401002                 lea     eax, [esp+8+var_4]
.text:00401006                 push    eax
.text:00401007                 push    offset Format   ; "%d"
.text:0040100C                 mov     [esp+10h+var_4], 0
.text:00401014                 call    ds:scanf
.text:0040101A                 mov     eax, [esp+10h+var_4]
.text:0040101E                 mov     esi, ds:putchar
.text:00401024                 dec     eax
.text:00401025                 add     esp, 8
.text:00401028                 cmp     eax, 7          ; switch 8 cases
.text:0040102B                 ja      loc_4010D0      ; default
.text:00401031                 jmp     ds:off_4010EC[eax*4] ; switch jump

如果case分支的值之间有一定的间隔,但是差距又不是很大,则会先生成一个数组(可能比较大),先通过switch的变量当做下标在一个数组中取得对应的值,然后把这个值当做下标再在跳转地址表中取得对应的地址。
编译器对switch case结构的优化 jumptable

如果case分支的部分值之间有一定的间隔,而又有一些分支的值没有规律,比如很大,且分布不均匀等。那么分布均匀的那一部分将采用两级跳转表的形式,而其他分支则采用简单的比较判断方式。

如果case分支值没有规律,则会采用二叉树查找的方式进行优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include "stdafx.h"
#include <stdio.h>
 
int _tmain(int argc, _TCHAR* argv[])
{
	int nMax = 0;
	scanf("%d", &nMax);
 
	switch (nMax)
	{
	case 1:
		putchar('1');
		break;
 
	case 256:
		putchar('2');
		break;
 
	case 3:
		putchar('3');
		break;
 
	case 999:
		putchar('4');
		break;
 
	case 512:
		putchar('5');
		break;
 
	case 0x0FFFFFFF:
		putchar('6');
		break;
 
	case 10000:
		putchar('7');
		break;
 
	case 0:
		putchar('8');
		break;
 
	default:
		printf("default");
	}
	putchar('\n');
 
	return 0;
}

IDA Pro中的截图:
编译器switch case优化,二叉树

.text:00401000 _wmain          proc near               ; CODE XREF: ___tmainCRTStartup+10A
.text:00401000
.text:00401000 var_4           = dword ptr -4
.text:00401000
.text:00401000                 push    ecx
.text:00401001                 push    esi
.text:00401002                 lea     eax, [esp+8+var_4]
.text:00401006                 push    eax
.text:00401007                 push    offset Format   ; "%d"
.text:0040100C                 mov     [esp+10h+var_4], 0
.text:00401014                 call    ds:scanf
.text:0040101A                 mov     eax, [esp+10h+var_4]
.text:0040101E                 mov     esi, ds:putchar
.text:00401024                 add     esp, 8
.text:00401027                 cmp     eax, 200h
.text:0040102C                 jg      short loc_4010A7
.text:0040102E                 jz      short loc_401094
.text:00401030                 cmp     eax, 3
.text:00401033                 jg      short loc_40107A
.text:00401035                 jz      short loc_401067
.text:00401037                 sub     eax, 0
.text:0040103A                 jz      short loc_401054
.text:0040103C                 sub     eax, 1
.text:0040103F                 jnz     short loc_4010BC
.text:00401041                 push    31h             ; Ch
.text:00401043                 call    esi ; putchar
.text:00401045                 add     esp, 4
.text:00401048                 push    0Ah             ; Ch
.text:0040104A                 call    esi ; putchar
.text:0040104C                 add     esp, 4
.text:0040104F                 xor     eax, eax
.text:00401051                 pop     esi
.text:00401052                 pop     ecx
.text:00401053                 retn
.text:00401054 ; ---------------------------------------------------------------------------
.text:00401054
.text:00401054 loc_401054:                             ; CODE XREF: _wmain+3A
.text:00401054                 push    38h             ; Ch
.text:00401056                 call    esi ; putchar
.text:00401058                 add     esp, 4
.text:0040105B                 push    0Ah             ; Ch
.text:0040105D                 call    esi ; putchar
.text:0040105F                 add     esp, 4
.text:00401062                 xor     eax, eax
.text:00401064                 pop     esi
.text:00401065                 pop     ecx
.text:00401066                 retn
.text:00401067 ; ---------------------------------------------------------------------------
.text:00401067
.text:00401067 loc_401067:                             ; CODE XREF: _wmain+35
.text:00401067                 push    33h             ; Ch
.text:00401069                 call    esi ; putchar
.text:0040106B                 add     esp, 4
.text:0040106E                 push    0Ah             ; Ch
.text:00401070                 call    esi ; putchar
.text:00401072                 add     esp, 4
.text:00401075                 xor     eax, eax
.text:00401077                 pop     esi
.text:00401078                 pop     ecx
.text:00401079                 retn
.text:0040107A ; ---------------------------------------------------------------------------
.text:0040107A
.text:0040107A loc_40107A:                             ; CODE XREF: _wmain+33
.text:0040107A                 cmp     eax, 100h
.text:0040107F                 jnz     short loc_4010BC
.text:00401081                 push    32h             ; Ch
.text:00401083                 call    esi ; putchar
.text:00401085                 add     esp, 4
.text:00401088                 push    0Ah             ; Ch
.text:0040108A                 call    esi ; putchar
.text:0040108C                 add     esp, 4
.text:0040108F                 xor     eax, eax
.text:00401091                 pop     esi
.text:00401092                 pop     ecx
.text:00401093                 retn
.text:00401094 ; ---------------------------------------------------------------------------
.text:00401094
.text:00401094 loc_401094:                             ; CODE XREF: _wmain+2E
.text:00401094                 push    35h             ; Ch
.text:00401096                 call    esi ; putchar
.text:00401098                 add     esp, 4
.text:0040109B                 push    0Ah             ; Ch
.text:0040109D                 call    esi ; putchar
.text:0040109F                 add     esp, 4
.text:004010A2                 xor     eax, eax
.text:004010A4                 pop     esi
.text:004010A5                 pop     ecx
.text:004010A6                 retn
.text:004010A7 ; ---------------------------------------------------------------------------
.text:004010A7
.text:004010A7 loc_4010A7:                             ; CODE XREF: _wmain+2C
.text:004010A7                 cmp     eax, 3E7h
.text:004010AC                 jz      short loc_4010FC
.text:004010AE                 cmp     eax, 2710h
.text:004010B3                 jz      short loc_4010E9
.text:004010B5                 cmp     eax, 0FFFFFFFh
.text:004010BA                 jz      short loc_4010D6
.text:004010BC
.text:004010BC loc_4010BC:                             ; CODE XREF: _wmain+3F
.text:004010BC                                         ; _wmain+7F
.text:004010BC                 push    offset aDefault ; "default"
.text:004010C1                 call    ds:printf
.text:004010C7                 add     esp, 4
.text:004010CA                 push    0Ah             ; Ch
.text:004010CC                 call    esi ; putchar
.text:004010CE                 add     esp, 4
.text:004010D1                 xor     eax, eax
.text:004010D3                 pop     esi
.text:004010D4                 pop     ecx
.text:004010D5                 retn
.text:004010D6 ; ---------------------------------------------------------------------------
.text:004010D6
.text:004010D6 loc_4010D6:                             ; CODE XREF: _wmain+BA
.text:004010D6                 push    36h             ; Ch
.text:004010D8                 call    esi ; putchar
.text:004010DA                 add     esp, 4
.text:004010DD                 push    0Ah             ; Ch
.text:004010DF                 call    esi ; putchar
.text:004010E1                 add     esp, 4
.text:004010E4                 xor     eax, eax
.text:004010E6                 pop     esi
.text:004010E7                 pop     ecx
.text:004010E8                 retn
.text:004010E9 ; ---------------------------------------------------------------------------
.text:004010E9
.text:004010E9 loc_4010E9:                             ; CODE XREF: _wmain+B3
.text:004010E9                 push    37h             ; Ch
.text:004010EB                 call    esi ; putchar
.text:004010ED                 add     esp, 4
.text:004010F0                 push    0Ah             ; Ch
.text:004010F2                 call    esi ; putchar
.text:004010F4                 add     esp, 4
.text:004010F7                 xor     eax, eax
.text:004010F9                 pop     esi
.text:004010FA                 pop     ecx
.text:004010FB                 retn
.text:004010FC ; ---------------------------------------------------------------------------
.text:004010FC
.text:004010FC loc_4010FC:                             ; CODE XREF: _wmain+AC
.text:004010FC                 push    34h             ; Ch
.text:004010FE                 call    esi ; putchar
.text:00401100                 add     esp, 4
.text:00401103                 push    0Ah             ; Ch
.text:00401105                 call    esi ; putchar
.text:00401107                 add     esp, 4
.text:0040110A                 xor     eax, eax
.text:0040110C                 pop     esi
.text:0040110D                 pop     ecx
.text:0040110E                 retn
.text:0040110E _wmain          endp

简单的画一个二叉树的图就是这个样子:

           512
          /   \
         /     \
        3      999
       / \       \
      /   \       \
     0     256   10000
      \              \
       \              \
        1            0x0FFFFFFF

觉得文章还不错?点击此处对作者进行打赏!


本文地址: 程序人生 >> 编译器对switch case结构的优化
作者:代码疯子(Wins0n) 本站内容如无声明均属原创,转载请保留作者信息与原文链接,谢谢!


更多



  1. 寒璿
    2012年7月25日15:10 | #1

    这个有意思,跳转值不规律的时候居然是二叉查找的。。。没想过

    [回复]

    代码疯子 回复:

    @寒璿, 以前也没想过

    [回复]

  2. 寒璿
    2012年7月25日15:16 | #2

    《C++逆向学习三步走》,这本书链接是404啊,在别的站下载了

    [回复]

    代码疯子 回复:

    @寒璿, 貌似是换空间的时候删掉了,名字是中文的把压缩包搞得无法解压……那个迅雷的是DBank的资源,后来dbank也把规律改了不知道还能不能下

    [回复]

  3. walkingsk
    2012年8月4日17:36 | #3

    敢问LZ用的是哪一款编译器?
    我用VC2010和VC6.0编译后用IDA分析结果都如下图:
    256
    / \
    / \
    / \
    / \
    / \
    / \
    FFFFFFFF 512
    \ \
    \ \
    0 999
    \ \
    1 10000
    \
    3
    我把VC2010、GCC、Intel C++分别编译后的结果上传到了
    http://115.com/file/dp1eligf
    自己看看吧,Intel C++是怎么处理的

    [回复]

    代码疯子 回复:

    @walkingsk,
    1. 我的编译器具体忘了,因为我换了电脑,但是可以保证是如下两个版本之一:
    Visual Studio 2008 专业版
    Visual Studio 2008 专业版(带SP1补丁)
    2. 你提供的下载提示“文件拥有者未分享该文件。”
    3. 我想你看错了,我的参数是0x0FFFFFFF,不是-1哦!我在Visual Studio 2008 专业版重新试了下,Debug就是这样的二叉树。
    ——————-
    你的二叉树之所以是这样,是因为把0x0FFFFFFF看成0xFFFFFFFF

    [回复]

    walkingsk 回复:

    @代码疯子, 额,它要求输入好友昵称、手机、邮箱、QQ号 ……
    我要怎么才能发给你?

    [回复]

  4. walkingsk
    2012年8月4日20:50 | #4

    确实,我看错了,我会重新编译一遍,用更多的编译器,然后开通分享,稍等……

    [回复]

  5. walkingsk
    2012年8月5日08:20 | #5

    好了,我使用VC2010、VC6.0、GCC 4.6.2、Intel C++、Digital Mars C/C++、
    Portable C Compiler六种编译器
    地址:
    http://115.com/file/beiuubx1#switch%20case語句.rar
    不过,不论是GCC还是VC,我的二叉树跟你的还是不一样。

    [回复]

  6. walkingsk
    2012年8月5日11:50 | #6

    下载需要注册,你只需注册一个账号就行了

    [回复]

    代码疯子 回复:

    @walkingsk, 我下载了你的程序看了,的确是不一样。
    不过这样的细节我觉得就必要深究了,有个大概的了解就OK了,呵呵

    [回复]

  7. walkingsk
    2012年8月5日17:53 | #7

    呵呵,你少了个”没有”,没有必要深究

    [回复]

  1. 本文目前尚无任何 trackbacks 和 pingbacks.