Switch's jump table

We all have heard that using a switch() block instead of a long if-else ladder results in faster code. Let us see why it is so. The secret to switch()'s faster code is the use of jump tables. A jump table basically consists of rows of addresses that point to locations in the code section. This table is indexed using the value of the variable specified in switch()'s condition. Every address points to one of the 'case' blocks or the 'default' block. This table is accessed by the CPU's 'Scaled-Index+Displacement' addressing mode. Now let us see what this table looks like:

--[ Basic jump table layout

- Each value in the 'Address' column points to the beginning of a 'case' block.

- Each row is 4 bytes long: standard size of a pointer.

+-------+------------+

| Index | Address    |

+-------+------------+

| 0     | codeloc0   | - 4 bytes

|--------------------|

| 1     | codeloc1   | - 4 bytes

|--------------------|

| 2     | codeloc2   | - 4 bytes

|--------------------|

| 3     | codeloc3   | - 4 bytes

|--------------------|

|...

|...

Let us review what a typical switch() block is made of. Every switch statement requires a value to use as index into the jump table. This value can be either stored in a variable or be generated as the result of an expression. Whatever the case, switch uses this as a number to index into the jump table. This is followed by zero or more case blocks with optional break statements. There may optionally be a default block also. If the break statement is omitted at the end of any case block then control falls-through to the next case block until a break or some other control transfer statement is encountered.

--[ switch() block layout

switch(value)

{

case 0: [break;]

case 1: [break;]

case 2: [break;]

...

[default: ...]

}

--] switch() block layout

In order to understand what exactly is being done with the 'value' and how the jump table is used we must look at the assembly code generated by the compiler. The basic steps done is outlined in the following pseudo-code.

begin switch()

    if value > highest_case_value then

    if default was defined then

        jump to default block

    else

        jump out of switch block

    index := value * scale_factor + addr of jump_table

    jump to code location stored at jump_table[index]

    // case blocks follow sequentially

    // followed by optional default block

end switch()

Let us get into a bit of assembly now. All doubts should be cleared after this.

--[ Disassembly snippets

; ** switch() begins

; switch(iIn)

0041155E mov eax,dword ptr [iIn]

00411561 mov dword ptr [ebp-0DCh],eax

00411567 cmp dword ptr [ebp-0DCh],7

0041156E ja $LN2+4 (4115B2h)

00411570 mov ecx,dword ptr [ebp-0DCh]

00411576 jmp dword ptr (411610h)[ecx*4]

iIn is the variable whose value is used to index into the jump table. The value is moved into eax first. It is then copied to a scratch-pad area and compared with the number 7, which is the highest value used in any of the case statements. If value of iIn is above 7 then control is transferred to the default block via the ja(jump if above) instruction. Notice that compiler has generated an unsigned compare instruction ja(jump if above) instead of jg(jump if greater) even though iIn is an signed variable. This is because the jump table index must always be >=0. If iIn was less than 7 then it is again moved to ecx from the scratch-pad area and the next jump instruction directly jumps to the appropriate case block(!). How did that happen you say? Well, scaled-Index+Displacement addressing mode and indirect jump happened! The ecx register is the index, 4 is the scaling factor because each row of the jump table is 4bytes long and 00411610h is the starting address of the jump table. The jump instruction uses the value at the calculated jump table index as an absolute offset. For example, if iIn was 3 then index = 00411610h + 3*4 = 00411610h + 0Ch = 0041161Ch. Value at 0041161Ch = 00411592. This is nothing but the address of the beginning of 'case 3' block. So the jump instruction transfers control to this block!

; case 0: vUnderConst(); break;

0041157D call vUnderConst (41107Dh)

00411582 jmp $LN2+1Bh (4115C9h)

; case 1: vUnderConst(); break;

00411584 call vUnderConst (41107Dh)

00411589 jmp $LN2+1Bh (4115C9h)

; case 2: vUnderConst(); break;

0041158B call vUnderConst (41107Dh)

00411590 jmp $LN2+1Bh (4115C9h)

; case 3: vUnderConst(); break;

00411592 call vUnderConst (41107Dh)

00411597 jmp $LN2+1Bh (4115C9h)

; case 4: vUnderConst(); break;

00411599 call vUnderConst (41107Dh)

0041159E jmp $LN2+1Bh (4115C9h)

; case 5: vUnderConst(); break;

004115A0 call vUnderConst (41107Dh)

004115A5 jmp $LN2+1Bh (4115C9h)

; case 6: vUnderConst(); break;

004115A7 call vUnderConst (41107Dh)

004115AC jmp $LN2+1Bh (4115C9h)

; case 7: return 0;

004115AE call vUnderConst (41107Dh)

004115B0 jmp $LN2+1Bh (4115C9h)

; default: printf("No such service\n"); break;

004115B2 mov esi,esp

004115B4 push offset string "No such service\n" (41575Ch)

004115B9 call dword ptr [__imp__printf (4182DCh)]

; ** switch() ends

--] Disassembly snippets

--[ Annotated jump table

- Index: Logical index of each row.

- CodeAddr: Location where the row value is stored.

- CodeLoc: Absolute code offsets that point to each of the case blocks.

+-------+------------+-----------+

| Index | CodeAddr   | CodeLoc   |

+-------+------------+-----------+

| 0     | 00411610   | 0041157d  |

|--------------------------------|

| 1     | 00411614   | 00411584  |

|--------------------------------|

| 2     | 00411618   | 0041158b  |

|--------------------------------|

| 3     | 0041161C   | 00411592  |

|--------------------------------|

| 4     | 00411620   | 00411599  |

|--------------------------------|

| 5     | 00411624   | 004115a0  |

|--------------------------------|

| 6     | 00411628   | 004115a7  |

|--------------------------------|

| 7     | 0041162C   | 004115ae  |

|--------------------------------|

--] Annotated jump table

I hope you understood how the switch statement uses a jump table to optimize code when choices are to be made based on multiple condition values. Before we conclude there are some things related to the jump table that is to be mentioned. The above explanation assumed that the case values started from 0 and continued with consecutive numbers until 7. What happens if the case values do not begin from 0? What happens when the case values are not consecutive? At first, it looks like a lot of if-else conditions might have to be generated by the compiler. No, again the jump table comes to our rescue.

The jump table always has entries from index 0 to highest_case_value. It is always zero-based. So for every case value that is not specified in the source code, the jump table entry for that value will point to the switch's 'default' block, if present, or to the statement after the switch block. For example, consider the following source code and the jump table generated.

switch(val)

{

   case 1: break;

   case 6: break;

   case 7: break;

   case 9: break;

   default: printf(“Invalid\n”); break;

}

after_switch: statement x

+-------+------------+-----------+

| Index | CodeAddr   | CodeLoc   |

+-------+------------+-----------+

|   0   | codeaddr0  | default   |

|--------------------------------|

|   1   | 00411614   | 00411584  |

|--------------------------------|

|   2   | 00411618   | 0041158b  |

|--------------------------------|

|   3   | 0041161C   | 00411592  |

|--------------------------------|

|   4   | 00411620   | 00411599  |

|--------------------------------|

|   5   | 00411624   | 004115a0  |

|--------------------------------|

|   6   | 00411628   | 004115a7  |

|--------------------------------|

|   7   | 0041162C   | 004115ae  |

|--------------------------------|