switch 的汇编语言表示

这个就是依据不同情况来采用不同的实现技术, 一个是用 if-then-else 语句来实现; 再一个就是跳转表实现.

首先讲讲看怎么用跳转表 :

long switch_eg(long x, long y, long z)
{
    long w - 1;
    switch(x){
        case 1:
            w = y * z;
            break;
        case 2:
            w = y / z;
            /*Fall through*/
        case 3:
            w += z;
            break;
        case 5:
        case 6:
            w -= z;
            break;
        default:
            w = 2;
    }
    return w;
}

有些细节要注意 :

case 5 和 case 6 实际上是对应同一段代码的; case 值并不连续; 还有个所谓的 Fall through, 就是说 case 2 完成之后, 它并没有 break 出去, 而是接着处理 case 3.

跳转表

Switch Form switch 表

switch(x){
    case val_0:
        Block 0
    case val_1:
        Block 1
    ......
    case val_n-1:
        Block n-1
}

这个相当于 switch-case 的一个 C 的代码, 然后呢对每一个 case 的处理, 是由一个指令段来处理, 也就是一个 Block 来进行处理.

针对不同的 x 的值, 跳到不同的指令段的入口地址. 我们可以专门创建一个 jump-table, 把你各个 case 下面的处理代码的入口地址放进去, 然后就形成了一个表.

然后我们可以把这个 x 的值作为这个表的下标, 或者说是索引. 然后我们访问这个表的下标, 把这个下标所对应的值取出来, 这个取出来的就是我们跳转的目标地址.

以上就是跳转表的工作原理.

Switch 语句示例 (X86-32)

long switch_eg(long x, long y, long z)
{
    long w - 1;
    switch(x){
        case 1:
            w = y * z;
            break;
        case 2:
            w = y / z;
            /*Fall through*/
        case 3:
            w += z;
            break;
        case 5:
        case 6:
            w -= z;
            break;
        default:
            w = 2;
    }
    return w;
}

还是之前的代码, 我们将其编译为如下汇编代码 :

Setup :

switch_eg:
    pushl %ebp              ; Setup
    movl %esp, %ebp         ; Setup
    pushl %ebx              ; Setup

    movl $1, %ebx           ; w = 1
    movl 8(%ebp), %ebx      ; ebx = x
    movl 12(%ebp), %eax     ; eax = y
    movl 16(%ebp), %ecx     ; ecx = z
    cmpl $6, %edx           ; x : 6
    ja .L61 ; if > goto default
    jmp *.L62(, %edx, 4)    ; goto JTab[x]

我们注意到 ja .L61, 这个 a 后缀表示 above 大于. 但问题是它是什么数据类型的大于呢 ?

这个 a, above 表示的是无符号整数, 但是我们回头看一看, 这里面的数据是 long, lone 类型是 signed, 那么为什么用 ja , 而不是用这个带符号整数的那个判断呢 ?

我们可以把它当作不带符号数来处理, 因为 default 的话就是说这个数大于 6 或者小于等于 0 的话, 它也正好满足, 所以用 ja 是正好. 就是如果你用 ja, 把它作为一个无符号数来处理的话, 等同于你从有符号数角度来看, 大于 6 就会跳到 default 去, 小于 0 也会跳到 default 去.

这里就是说, 这个 ja 代码后面就是 default 情况

如果不满足这个的话, 就 jmp. 注意看这个 jmp *.L62(, %edx, 4), .L62 就是我们刚才说的 jump-table 的起始地址, edx 就是 x, 因为每个地址都是 4 byte, 所以它乘上一个 4. 这个星 * 的意思是告诉汇编器, 我里面取出来的这个数是一个地址, 你就直接把它作为地址跳过去就行了.

这里是说, 如果不满足 default 情况, 就跳到 default 的后面, 也就是各种 case. 只针对这段代码, 其它代码具体情况具体分析.

表结构

表结构就是说, 每一个表项, 就是每一个入口的地址, 也就是每一个跳转的地址占 4 个字节, 基地址是 .L62

无条件跳转指令就是 jmp *.L62(, %edx, 4), 这么跳转相当于把 .L62 作为一个起始地址, .L62 + %edx 4 就是我把表项里面所对应的那个地址取出来. \ 表示这是一个间接跳转, 就是说目标地址存在于内存中, 我从内存中取出来的这个数就是我的目标地址.

文字填空题

jbe 是小于的时候跳转

L3 为 case 1

L4 为 case 2

L9 为 case 3

L6 为 case 5

L6 为 case 6

L8 为 default x <= 0 或者 > 6 或者 x = 4

L12 为 break

x = 0 时, 根据这个间接寻址公式, 就是跳到了 L7 这个基址这里, 也就是跳转表第一个值这里. 而 x = 0 正好是默认情况.

switch_eg:
    pushl %ebp
    movl %esp, %ebp
    pushl %ebx

    movl 8(%ebp), %ebx  ; ebx = x
    mov 12(%ebp), %eax  ; eax = y
    mov 16(%ebp), %ecx  ; ecx = z

    cmpl $6, %ebx
    jbe .L11            ; x < 6 就跳转到 L11

.L11:
    jmp *.L7(, %ebx, 4)

    .section .rodata
.L7:
    .long .L8   ; x = 0
    .long .L3   ; x = 1
    .long .L4   ; x = 2
    .long .L9   ; x = 3
    .long .L8   ; x = 4
    .long .L6   ; x = 5
    .long .L6   ; x = 6
    .text

.L8:
    movl $2, %eax
    popl %ebx
    popl %ebp
    ret

.L6:
    movl $1, %eax
    subl %ecx, %eax
    popl %ebx
    popl %ebp
    ret

.L9:
    movl $1, %eax
    addl %ecx, %eax

.L12:
    popl %ebx
    popl %ebp
    ret

.L4:
    movl %eax, %edx
    sarl $31, %edx
    idivl %ecx
    addl %ecx, %eax
    jmp .L12

.L3:
    imull %ecx, %eax
    popl %ebx
    popl %ebp
    ret

表项内容

.section .rodata
    .align 4

.L62:
    .long .L61  ; x = 0
    .long .L56  ; x = 1
    .long .L57  ; x = 2
    .long .L58  ; x = 3
    .long .L61  ; x = 4
    .long .L60  ; x = 5
    .long .L60  ; x = 6

.L62 表示下面是一段数据

.section, .data 以后再讲, 就是数据段

.L61 就是相对应每一段 case 代码的入口, 整个这个表的起始地址是 .L62.

0 没有, 4 没有, 那就把 0 和 4 都写上 default 呗.

X86-64 下的 switch 语句

基本上与 32 位版本是一样的, 代码地址长度为 64 位

我们也类似地定义了一个 jump-table

.section .rodata
    .align 8
.L62:
    .quad .L55  ; x = 0
    .quad .L50  ; x = 1
    .quad .L51  ; x = 2
    .quad .L52  ; x = 3
    .quad .L55  ; x = 4
    .quad .L54  ; x = 5
    .quad .L54  ; x = 6

表现形式都一样, 无非就是说我每一个表项的宽度是 .q, 8 个字节.

Switch 语句示例 (case 值很稀疏)

/* Return x / 111 if x is multiple && <= 999.   -1 otherwise*/
int div111(int s)
{
    switch(x){
        case 0:     return 0;
        case 111:   return 1;
        case 222:   return 2;
        case 333:   return 3;
        case 444:   return 4;
        case 555:   return 5;
        case 666:   return 6;
        case 777:   return 7;
        case 888:   return 8;
        case 999:   return 9;
        default:    return -1;
    }
}

向这种 case 值比较稀疏的情况, 就不适合使用跳转表了. 因为取值越稀疏, 中间隔得越大, 跳转表就占了太大的空间, 而实际上有效的项没多少, 写了那么多项实际上全是 default.

这样我们只能把它转换成一系列的 if-then-else 语句了. 我们一般以二叉树的结构来组织, 提升性能.