c语言中的switch指令实质在部分实现上对应着跳转表。通过在程序中维护一个跳转表（类似于void*[LENGTH]），其中存储跳转的目标地址，通过偏移量，以近似O(1)时间复杂度来实现”条件判断“。

我们只需要理解最最基础的跳转表实现，因为在c语言中的switch为了优化，实际上并不全采用跳转表实现。根据我的测试，在GCC环境时有如下情况：

• 当测试的case参数连续性太低，跳转表会退化为二分查找的类if判断语句（时间复杂度大概为O(log(n)）。

  switch(i){
      case -100:
          puts("1");
          break;
      case 12:
          puts("2");
      case 34:
          puts("3");
          break;
      case 47:
          puts("4");
          break;
      
      case 59:
          puts("5");
          break;
      case 600:
          puts("6");
          break;
      default:
          puts("d");
  }

  cmp     edi, 47
  je      .L11
  jg      .L12
  cmp     edi, 12
  je      .L13
  cmp     edi, 34
  jne     .L21

• 如果case的数据不从0开始且足够连续，则编译器会通过偏移量修正并生成跳转表。

​

switch(i){
    case -100:
        puts("1");
        break;
    case -99:
        puts("2");
    case -98:
        puts("3");
        break;
    case -97:
        puts("4");
        break;
    
    case -96:
        puts("5");
        break;
    case -95:
        puts("6");
        break;
    default:
        puts("d");
}

        add     edi, 100	;通过使用偏移进行修正
        cmp     edi, 5
        ja      .L11	
        mov     edi, edi
        jmp     [QWORD PTR .L13[0+rdi*8]]
.L13:
        .quad   .L18
        .quad   .L17
        .quad   .L16
        .quad   .L15
        .quad   .L14
        .quad   .L12

在这里将相对简单的描述在nasm 汇编器和x86-64环境下中实现跳转表。

实际上，Jump Tables (nasm.us)已经讨论过nasm中的jump table实现，但是由于我们的环境为x86-64，并不能正常运行。

为了理解跳转表的实现原理，我们要写一个foo函数，这个函数传入一个int变量，使用switch实现。如果变量为0-3，则返回对应变量，否则返回4。虽然看起来没有必要

//对应c语言源码，编译后的反汇编代码可能不由跳转表实现。
int foo(int i){
int t;
switch(i){
case 0:
	t=0;
	break;
case 1:
	t=1;
	break;
case 2:
	t=2;
	break;
case 3:
	t=3;
	break;

default:
	t=4;
}
return t;
}

对于汇编，我们首先实现每个case代码块和return中的汇编代码。

.T00:
        mov     ebx,0
        jmp     .Done		;break
.T01:
        mov     ebx,1
        jmp     .Done
.T02:
        mov     ebx,2
        jmp     .Done
.T03:
        mov     ebx,3
        jmp     .Done
.Default:
        mov     ebx,4
.Done:
        mov     eax,ebx	;return t;
        ret

接下来我们要实现跳转表的核心——一个存储着各代码块起始地址的数组。

这个数组用以下方式实现

.JumpTable: DQ .T00, .T01, .T02, .T03

值得注意的是，由于使用了DQ指令，这个数组每个元素都为8byte的64位内存地址。

实现switch前半部分。

foo:
        cmp     edi,3
        ja      .Default
        jmp     [.JumpTable+edi*8]

其中jmp [.JumpTable+edi*8]就类似于goto JumpTable[i]。通过偏移量实现。

总代码

section .text
global foo
foo:
        cmp     edi,3
        ja      .Default
        jmp     [.JumpTable+edi*8]
.JumpTable: DQ .T00, .T01, .T02, .T03
.T00:
        mov     ebx,0
        jmp     .Done
.T01:
        mov     ebx,1
        jmp     .Done
.T02:
        mov     ebx,2
        jmp     .Done
.T03:
        mov     ebx,3
        jmp     .Done
.Default:
        mov     ebx,4
.Done:
        mov     eax,ebx
        ret

我们通过nasm -felf64 foo.asm生成object file，随后编写对应程序调用该函数。可以发现程序正确执行。

总结

跳转表仍有局限，但是其比较常见，我认为很有学习的必要。

其他

汇编中，当使用跳转表时，参数为负数时是如何处理的？

​ 在机器码这一层面，并不存在真实的负数，所有的负数都通过补码存储，这意味着如果一个数为负数，则其二进制位的第一位一定为1。当使用cmp指令时，负数一定above整数，进而导致ja跳转直接跳转到default对应汇编代码段中。