[2011-03]VS2008下反汇编观察switch语句

VS2008下反汇编观察switch语句

                         观察--猜测--实证

 

/********************                       

Author:xichen

Data:2011-03-27

********************/

引言：Switch ，if else语句是在程序设计中使用较为频繁的两种语句，它们实现的功能是相似，都是通过对特定值的判断后执行相应的操作。但是switch和if else执行方式肯定是不同的，这点我们直观地在语句的句式上就可以推断得出的，但是究竟在底层它们是以一种怎样的形式执行的呢？ 这是值得我们探究的一个话题，因为只有了解其底层过程，我们才能够更好地认识，选择使用switch，else if语句。

接下来我将通过在VS2008中进行反汇编观察，分析switch语句的执行机制。在描述之前，为了节省篇幅，也为了描述的方便，做出一个约定：

switch(i)

{

       case 1:....break;

    case 2:....break;

       case 3:....break;

       case 4:....break;

       case 5:....break;

       case 6:....break;

       default:

              ...break；

}

我们约定表示形式为：case序列：1    2   3   4   5   6   x;其中x用来代表default情况；这样描述case语句时较为清爽；

观察：

首先是我们最常见的一种switch语句：case 序列：1 2   3   x;

其汇编代码为：

 

而相应的if else语句汇编代码为：

 

 

 

当我们对比两段汇编代码的时候，实际上并没有本质的区别，if else语句的做法是我们能够想象的到的，而传说中的switch居然也是这么处理的。。。。。

 

我们知道使用switch的情况一般是case较多时，那么为什么是case较多时呢？case较多时回事什么样呢？

 

定义case序列：1 2 3 4 5 6 x;

反汇编代码为：

 

 

汇编代码读起来是很晦涩的，但是也是比较有味道的，我比较喜欢的读法是：

画出寄存器，画出堆栈，然后跟随代码自己修改寄存器的值。

比如执行到ja那句的时候，我的草稿纸上显示eax=i; ecx=i-1; [ebp-0c4h]=i-1;

梳理下上面的代码：[ebp-0c4h]就是一个特定的地址，作为eax和ecx之间的中转站，而sub和cmp两条指令保证了i落在1-6区间中，否则直接jmp到x情况。接下来jmp到一个地址：0aa14b8h+(i-1)*4;

我们猜想：这里应该是到一个地方去了，干什么呢？肯定是找怎么跳到合适的位置去了，很容易猜出，实际上地址是4个字节一个格格，0aa14b8h是一个基地址的东西，而i-1决定从第几个格格取地址。

好，接下来我们看看0aa14b8h这个地址后面装的是什么：

9c 14 aa 00 9e 14 aa 00 a0 14 aa 00 a2 14 aa 00 a4 14 aa 00 a6 14 aa 00

（嘿，小端机呢）

读出来的是00 aa 14 9c| 00 aa 14 9e|00 aa 14 a0|00 aa 14 a2|…

对应的地址恰好是:case 1,2,3,4..的地址值，验证了我们的想法；

呵呵，到这里神清气爽，到此结束了！

？是不是我们的话题到这个就结束了呢？不，远远没有。

 

 

实际上以上我们给出的是我们最常用的方式，就是case的值连续到吐血的那种，可我们在使用switch的时候不可能总是这种方式，如果地址值不连续呢？比如这个极端：

Case序列：1 2 3 4 5 800 x;

汇编代码：

 

对比汇编代码，我们可以看出它没有采用之前的方式，而完全就是类比if else的很简单的cmp,je，这。。。我们刚才明明看到了一个表，一个可以查询地址的表啊？？

写到这里实际上产生了两个问题：

1.为什么编译器要这么做?

2.什么时候这么做呢？

 

我们不先回答问题1，现在只是想从现象到现象的去看这个问题；

出现这种情况的原因是我修改了max值为800，也就是说如果是6就有表出现而一个很大的值就没有表出现，那么什么时候也就是这个很大的值是多少的时候会有表出现呢？

如果限定case起始值是1（实际上不是1，也可以化归为1）：不断的修改最大值，记录MAX-MIN值，最后在我的不断逼近下，得出MAX-MIN=255是临界值，现象是：当MAX是255的时候，出现了跳转表的做法，但是MAX是256的时候是else if的方式，猜想如果保持MAX=256，修改MIN=2的时候应该是什么样子的呢？那个跳转的表，还是直接判断？

实证下：结果是跳转表如约而至（篇幅原因不截图），哈哈，那么到这里是不是可以说或当表的差值（你懂的的差值）小于255的时候就会出现跳转表呢？不，显然这个太过于武断，因为我一直在忽视一个问题，那就是局部疏密程度显然不能够代表整体，也就是说case值的疏密程度，并不完全取决于MAX-MIN的值，下面给出另外一个例子：

Case序列： 100   110 120   130    140    150    x;

实际上它等同于：case序列：0   10   20 30 40 50 x;

 

汇编代码：

 

上面说的表有个类似于基地址的东西，这里居然出现了2个，跳转表好像有，但是好像又不是，这…..

赋予i=120,打个断点跟踪一个值进去观察,首先到地址0aa187ch:

00 06 06 06 06 06 06 06 06 06 01 06 06 06 06 06 06 06 06 06 02 06 06 06 06 06 06 06 06 06 03 06 06 06 06 06 06 06 06 06 04 06……

这是什么？？ 我们观察到120进去之后eax的值变成了00000002，查阅指令知道movzx，..byte是取一个字节，也就是02，好的我们知道我们从这些串串中取出了02，然后呢；看下0aa1860h地址：

43 18 aa 00 45 18 aa 00 47 18 aa 00 49 18 aa 00 4b 18 aa 00 4d 18 aa 00 4f 18 aa 00

[eax*4]=8，数8个字节，取4字节，我们得到00aa1847h,查看下：果然case120的地址，这个过程很熟悉，就像我们在第一次见到跳转表时的样子。把这个过程画一个图：

 

这里可以很清晰的看出，其实这也是一种表的结构，不过是通过先查找序号，再获取地址。为了区别，我们称第一种为单层表，第二种为双层表。

事实上，遇到问题应该多问为什么（我所欠缺的啊）？

那么为什么使用着单层表好好的，又使用双层表了呢？

这是策略的转变，而你知道的：所有的策略，方法我们都可以用一个叫做“算法“的东西称呼之，而算法最基本的两个属性就是时间和空间;

分析：

两个为什么？

从时间角度分析：

从时间角度分析单跳表和双跳表是很easy的事情，从时间考虑很显然双跳表更麻烦，跳了两次才取到地址，如果完全从时间的角度去看，显然会跟我们实际看到的情况不一致，那么就只能从空间的角度分析了

为什么要使用跳转表？

在底层，机器级的执行过程中，CPU的操作有：取值，加（减，乘，除）；

本例中需要用的是加法，取值；我们知道取值是1个机器周期，加法是4个机器周期。

比较switch 和else if，当使用跳转表时，switch大致的机器周期是：4个加法；（sub,cmp,jmp寻址的乘和加）；也就是说无论有多少项，这个已经是最少的机器周期了，而对于else if而言是O(1)，也就是有多少项就有多少次加法。两种情况的交汇点就是4（不够严谨），也就是说只有4以上的case情况switch才有可能更快。这也解释了为什么5个case时switch开始使用跳转表了，但是显然不是绝对的，如果完全是这样，那么case序列：1 2 3 4 5 800时，也应该使用跳转表啊，为什么又使用cmp,je的方式了呢？既然存在了就有它的理由，显然我们需要从空间角度去分析了。

从空间角度分析：

从空间角度分析：

如果case序列： MIN ……MID…..MAX  x;共有n+1项；MID表示某一中间值；

其等价形式：case序列：0…..MID-MIN…MAX-MIN  x;也是共有n+1项；

通过上面的观察，可以给出观察结果：

对于case语句：

n<4时，使用else if方式；

n>=4的时候，如果MAX-MIN<255，则使用跳转表，

否则MAX-MIN>=255 则直接使用else if方式。

跳转表有两种:在vs2008中，如果MIN—MAX中项值分布较为连续时，往往给出单层表。

              相反如果MIN—MAX项值跨度较大时，往往使用双层表。

 

使用单层表时，空间为： 4*(MAX-MIN+1)         （单位byte）

使用双层表时，空间为：4*(n+1)+ (MAX-MIN+1)     （单位byte）

那么对于case序列：1 2 3 4 5 600  x的情况；如果使用单层表，空间为2400byte，显然代价太大了;

对于序列：100  110  120  130  140  150  x；

单层表：4*51=204;  双层表：4*7+51=79，空间大大节省，这一定程度上解释了为什么使用双层表；

那么我们是不是可以做出一个判断，完全从空间上的判断:

选择使用单层表的条件：  4*(MAX-MIN+1)< 4*(n+1)+ (MAX-MIN+1)

è3* (MAX-MIN)<4n+1

 

相应地使用双层表的条件：3* (MAX-MIN)>4n+1

 

验证我们的想法：

实验结果如下： 最右边是序列，描述：表示在n和min值固定的情况下，MAX取的单层表变为双层表的临界值；

选择n=5,MIN=1;    1 2 3 5  11转

选择n=6,MIN=1;    1 2 3 5 9 13转

选择n=7,MIN=1;    1 2 3 5 9 11 14转

选择n=8,MIN=1;    1 2 3 5 9 11 13 15转

选择n=9,MIN=1;    1 2 3 5 9 11 13 14 17转

 

很显然如果单纯地从空间的角度考虑，以上的实验结果是不会出现的，而出现了，说明有些东西是我们没有领悟到的。

 

对于算法，归根结底是时间和空间的博弈，如何在中间选择一个最优的值，冥冥中我觉得会有一个公式，像3次曲线或者跟复杂的曲线一样，指导着编译器做出选择，至于究竟是怎样，站在编译器之外的我，抑或者我们需要更多的实证，当然如果可以，或许当面问MS的天才工程师们……