返回介绍

20.1 跳转表与分支语句

发布于 2024-10-11 21:05:48 字数 7815 浏览 0 评论 0 收藏 0

C 语言的 switch 语句经常成为编译器优化的目标。这类优化的目的是将分支变量与一个有效的 case 标号以最有效的方式进行匹配。通常,实现匹配的方法取决于 switch 语句的 case 标号的形式。如果 case 标号十分分散,如在下面的例子中:

switch (value) {  
   case 1:  
      //code executed when value == 1  
      break;  
   case 211:  
      //code executed when value == 211  
      break;  
   case 295:  
      //code executed when value == 295  
      break;  
   case 462:  
      //code executed when value == 462  
      break;  
   case 1093:  
      //code executed when value == 1093  
      break;  
   case 1839:  
      //code executed when value == 1839  
      break;  
}

这时,大多数编译器会生成代码,进行二进制搜索1 ,将分支变量与某种情形(case)相匹配。

1. 对于算法分析爱好者来说,这表示分支变量在 log2 N 操作后匹配,这里的 N 是 switch 语句中情形的数量。

如果 case 标号非常集中,甚至是按顺序排列,如下所示:

switch (value) {  
   case 1:  
      //code executed when value == 1  
      break;  
   case 2:  
      //code executed when value == 2  
      break;  
   case 3:  
      //code executed when value == 3  
      break;  
   case 4:  
      //code executed when value == 4  
      break;  
   case 5:  
      //code executed when value == 5  
      break;  
   case 6:  
      //code executed when value == 6  
      break;  
}

这时,编译器通常会通过执行一次表查找2 ,将分支变量与相关情形的地址相匹配,以解析分支变量。

2. 同样,对于算法分析爱好者来说,使用表查找可以通过一项操作(可以从算法类中撤销)找到目标情形,这也叫做常量时间或 O(1) 。

一个 switch 语句的编译示例如下所示,它根据连续的情形 1~12 匹配分支变量:

    .text:00401155         mov     edx, [ebp+arg_0]  
➊  .text:00401158         cmp     edx, 0Ch        ; switch 13 cases  
    .text:0040115B         ja      ➎loc_4011F1      ; default  
    .text:0040115B                                   ; jumptable 00401161 case 0  
    .text:00401161         jmp     ds:off_401168[edx*4] ; switch jump  
    .text:00401161 ; ---------------------------------------------------------------  
➋  .text:00401168 off_401168 dd offset ➋loc_4011F1  ; DATA XREF: sub_401150+11 ↑r  
    .text:00401168         dd offset loc_40119C ; jump table for switch statement  
    .text:00401168         dd offset loc_4011A1  
    .text:00401168         dd offset loc_4011A6  
    .text:00401168         dd offset loc_4011AB  
    .text:00401168         dd offset loc_4011B3  
    .text:00401168         dd offset loc_4011BB  
    .text:00401168         dd offset loc_4011C3  
    .text:00401168         dd offset loc_4011CB  
    .text:00401168         dd offset loc_4011D3  
    .text:00401168         dd offset loc_4011DB  
    .text:00401168         dd offset loc_4011E3  
    .text:00401168         dd offset loc_4011EB  
    .text:0040119C ; ---------------------------------------------------------------  
    .text:0040119C  
    .text:0040119C loc_40119C:                 ; CODE XREF: sub_401150+11 ↑j  
    .text:0040119C                             ; DATA XREF: sub_401150:off_401168 ↑o  
➌  .text:0040119C         mov     eax, [ebp+arg_4] ; jumptable 00401161 case 1

这个示例使用 IDA 能够完全理解的 Borland 命令行编译器编译。IDA 在分析阶段插入的注释充分说明 IDA 清楚地知道:这是一个 switch 语句。在这个例子中,我们注意到,IDA 能够识别代码中的分支测试(➊)、跳转表(➋)和按值确定的各情形(➌)。

在使用跳转表解析分支情形时,需要注意的是,前一个示例中的表包含 13 个条目,而据我们所知, switch 语句仅测试情形 1~12 。在这种情况下,编译器选择包含一个用于情形 0 的条目,而不是把 0 当做特例处理。情形 0(➍)的目标与 1~12(➎)以外的其他值的目标相同。

最后,我们需要注意对分支变量所执行的测试的本质。对于不熟悉 x86 指令集的读者来说,测试➊及随后行中的相关跳转似乎仅仅将大于 12 的值排除在外,而没有考虑到负值。如果是这样,那么可能会造成灾难性的后果,因为在跳转表中使用负值可能会导致无法预料的结果。不过, ja (向上跳转)指令在进行比较时,将比较值作为无符号值处理。因此,-1( 0xFFFFFFFF )被看做 4294967295 ,这个值要远大于 12 ,因而不在跳转表的有效索引值的范围之内。

使用 Microsoft Visual C++编译上面的源代码,可以得到下面的反汇编代码清单:

   .text:004013D5             mov     ecx, [ebp+var_8]  
   .text:004013D8           ➊sub ecx, 1  
   .text:004013DB             mov     [ebp+var_8], ecx  
   .text:004013DE             cmp  [ebp+var_8],  ➋0Bh ; switch 12 cases  
   .text:004013E2             ja l oc_40146E      ; jumptable 004013EB default case  
   .text:004013E8             mov     edx, [ebp+var_8]  
   .text:004013EB             jmp  ds:off_401478[edx*4] ; switch jump  
   .text:004013F2  
➍ .text:004013F2 loc_4013F2:                          ; DATA XREF:  
   .text:off_401478?o  
   .text:004013F2             mov     eax, [ebp+arg_4] ; jumptable 004013EB   ➎case 0  
   ... ; REMAINDER OF FUNCTION EXCLUDED FOR BREVITY  
   .text:00401477             retn  
   .text:00401477 sub_4013B0 endp  
   .text:00401477 ; -------------------------------------------------------------  
➌ .text:00401478 off_401478 dd offset  ➍loc_4013F2  ; DATA XREF: sub_4013B0+3B↓r  
   .text:00401478             dd offset loc_4013FA  ; j ump table for switch statement  
   .text:00401478             dd offset loc_401402  
   .text:00401478             dd offset loc_40140A  
   .text:00401478             dd offset loc_401415  
   .text:00401478             dd offset loc_401420  
   .text:00401478             dd offset loc_40142B  
   .text:00401478             dd offset loc_401436  
   .text:00401478             dd offset loc_401441  
   .text:00401478             dd offset loc_40144C  
   .text:00401478             dd offset loc_401458  
   .text:00401478             dd offset loc_401464

将这段代码与由 Borland 编译器生成的代码进行比较,可以发现几个不同之处。一个明显的不同是跳转表的位置发生了变化,它紧靠在包含 switch 语句的函数后面(而使用 Borland 编译器生成的代码却将跳转表嵌入到函数之中)。除了更清楚地区分代码和数据外,以这种方式移动跳转表的位置不会给程序的行为造成任何影响。尽管代码的布局不同,但 IDA 仍然能够为 switch 语句的关键功能提供注释,包括情形数以及与每种情形相关的代码块。

有关 switch 语句的一些实施细节包括:分支变量(这里为 var_8 )不断递减(➊),有效值由 11 减至 0(➋),这使得 IDA 可以直接将变量用作跳转表索引(➌),而不需要为不使用的情形 0 创建一个哑插槽(dummy slot )。因此,跳转表中的第一个条目(或者零索引条目)(➍)实际上引用的是分支情形 1 的代码。

我们以下面由 gcc 生成的代码结束 switch 语句的比较:

    .text:004011FA          ➊cmp        [ebp+arg_0], 0Ch ; switch 13 cases  
    .text:004011FE            ja       ➌loc_40129D      ; jumptable 00401210 case 0  
    .text:00401204            mov        eax, [ebp+arg_0]  
    .text:00401207            shl        eax, 2  
    .text:0040120A          ➎mov      ➋eax,  ds:off_402010[eax]  
    .text:00401210          ➎jmp        eax             ; switch jump  
    .text:00401212  
    .text:00401212  ➍loc_401212:                          ; DATA XREF:  
    .rdata:off_402010 o  
    .text:00401212            mov     eax, [ebp+arg_4] ; jumptable 00401210 case 1  
    ... ; REMAINDER OF .text SECTION EXCLUDED FOR BREVITY  
➋  .rdata:00402010 off_402010 dd off set ➌loc_40129D  ; DATA XREF: sub_4011ED+1D ↑r
    .rdata:00402010           dd offset  ➍loc_401212;jump table for switch statement
    .rdata:00402010           dd offset loc_40121D  
    .rdata:00402010           dd offset loc_401225  
    .rdata:00402010           dd offset loc_40122D  
    .rdata:00402010           dd offset loc_40123C  
    .rdata:00402010           dd offset loc_40124B  
    .rdata:00402010           dd offset loc_40125A  
    .rdata:00402010           dd offset loc_401265  
    .rdata:00402010           dd offset loc_401270  
    .rdata:00402010           dd offset loc_40127B  
    .rdata:00402010           dd offset loc_401287  
    .rdata:00402010           dd offset loc_401293

这段代码与前面的 Borland 代码存在一些相似之处,它也有 12 种情形(➊)和包含 13 个条目的跳转表(➋),并使用一个指针指向跳转表的情形 0 插槽中的默认情形(➌)。和在 Borland 代码中一样,情形 1 处理程序(➍)的地址可以在跳转表中的索引 1 处找到。gcc 代码与前面代码的明显差异包括:执行跳转(➎)的风格不同;跳转表存储在二进制文件的只读数据( .rdata )节,从而将和 switch 语句有关的代码与执行 switch 语句所需的数据隔离开来。与其他两个示例一样,IDA 能够找到并注释 switch 语句的关键元素。

这里需要指出的是,将源代码编译成汇编语言,并没有唯一正确的方法。熟悉由某一特定的编译器生成的代码,并不能保证你能够识别使用一种截然不同的编译器(或者是相同编译器系列的不同版本)编译的高级结构。更重要的是,不能仅仅因为 IDA 无法生成注释,就断定某段代码不是 switch 语句。和你一样,IDA 也更加熟悉某些编译器的输出。你不能完全依赖 IDA 的分析功能来识别常用的代码和数据结构,而应随时准备应用你掌握的技能:对给定汇编语言的了解、你的编译器知识以及正确解释一个反汇编代码清单的搜索技巧。

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
    原文