Jump Table
A jump table is an array of pointers to functions or an array of assembly code jump instructions.
In assembling, jump tables are the most efficient method to handle switch statements with a large number of cases. The jump table is created only once and the required field in the table can be accessed simply by indexing.
Especially in embedded systems, where there is a heavy constraint in available memory, jump tables can be efficient while consuming lesser memory too.
Sample Program
 |
| Fig 1. Sample Program |
The switch has only four cases, hence there is no need for a jump table. The cases are implemented simply as:
 |
| Fig 2. The switch implementation without jump table |
The behavior is almost as expected.
Now, I need a switch with enough cases, to get the attention of the gcc compiler heuristics.
 |
| Fig 3. More cases for the switch |
I have to check the corresponding assembly code generated for the above program, to be sure.
 |
| Fig 4. Lookup table created - PartI |
 |
| Fig 5. Lookup table created - PartII |
It worked, the compiler decided that a jump table is really essential now.
The “mov #1,@r4” line stores the value of variable “i”. There are 8 cases, numbered from 0 to 7. Hence first “i”, i.e, @r4 is compared with 8, for obvious reasons.
Analysing the ‘jump table’
The jump table has been created, starting from the address denoted by the label “.L11”.
The first entry in the table holds label “.L3” which is the starting address of the block of statements under “case 0:”.
The next entry is “.L4”, which is the starting address of the block of statements under “case 1:”.
And so on … Till “case 7:”.
There are 8 “.word”s in the jump table too. Correct!
The line N in the jump table holds the starting address of the block of statements under the corresponding “case N:”. In other words, each line is the offset to be added to “.L11”, to execute the required case statements.
Decoding …
“r15” holds the value to be switched.
”rla r15” rotates left arithmetically the value inside r15, once (multiplication by 2).
Remember that even addressing is required for MSP430 family.
“add #.L11,r15” adds the present value of “r15” (similar to offset), with the address of the label “.L11” (similar to base address).
“r15” now contains the address of the line that lies at the given offset from “.L11”.
After the ”mov @r15,r15” line, “r15” now contains the starting address of a block of statements under the selected “case”.
”br r15” simply branches to the address pointed to by r15.
Clean.
Issues
Suppose there are a very large number of switch cases. Then, this “jump to index” overhead will be much lower than the cost to perform N case comparisons. That is why jump tables are usually preferred.
In situations where the cases are random and spread over a large range, suitable searching methods are needed. Normally, binary search is used. The correct case can then be selected in 3 or 4 steps without performing N comparisons each time.
The “mov #1,@r4” line stores the value of variable “i”. There are 8 cases, numbered from 0 to 7. Hence first “i”, i.e, @r4 is compared with 8, for obvious reasons.
Analysing the ‘jump table’
The jump table has been created, starting from the address denoted by the label “.L11”.
The first entry in the table holds label “.L3” which is the starting address of the block of statements under “case 0:”.
The next entry is “.L4”, which is the starting address of the block of statements under “case 1:”.
And so on … Till “case 7:”.
There are 8 “.word”s in the jump table too. Correct!
The line N in the jump table holds the starting address of the block of statements under the corresponding “case N:”. In other words, each line is the offset to be added to “.L11”, to execute the required case statements.
Decoding …
“r15” holds the value to be switched.
”rla r15” rotates left arithmetically the value inside r15, once (multiplication by 2).
Remember that even addressing is required for MSP430 family.
“add #.L11,r15” adds the present value of “r15” (similar to offset), with the address of the label “.L11” (similar to base address).
“r15” now contains the address of the line that lies at the given offset from “.L11”.
After the ”mov @r15,r15” line, “r15” now contains the starting address of a block of statements under the selected “case”.
”br r15” simply branches to the address pointed to by r15.
Clean.
Issues
- How can you justify that jump tables are friendly to embedded systems?
Suppose there are a very large number of switch cases. Then, this “jump to index” overhead will be much lower than the cost to perform N case comparisons. That is why jump tables are usually preferred.
- Jump tables work only when the case identifiers are consecutive.
In situations where the cases are random and spread over a large range, suitable searching methods are needed. Normally, binary search is used. The correct case can then be selected in 3 or 4 steps without performing N comparisons each time.