What is a jump table?

Question

Can someone explain the mechanics of a jump table and why is would be needed in embedded systems?

Answer 1

From Wikipedia:

In computer programming, a branch table (sometimes known as a jump table) is a term used to describe an efficient method of transferring program control (branching) to another part of a program (or a different program that may have been dynamically loaded) using a table of branch instructions. The branch table construction is commonly used when programming in assembly language but may also be generated by a compiler.

A branch table consists of a serial list of unconditional branch instructions that is branched into using an offset created by multiplying a sequential index by the instruction length (the number of bytes in memory occupied by each branch instruction). It makes use of the fact that machine code instructions for branching have a fixed length and can be executed extremely efficiently by most hardware, and is most useful when dealing with raw data values that may be easily converted to sequential index values. Given such data, a branch table can be extremely efficient; it usually consists of the following steps: optionally validating the input data to ensure it is acceptable; transforming the data into an offset into the branch table, this usually involves multiplying or shifting it to take into account the instruction length; and branching to an address made up of the base of the table and the generated offset: this often involves an addition of the offset onto the program counter register.

Answer 2

A jump table is described here, but briefly, it's an array of addresses the CPU should jump to based on certain conditions. As an example, a C switch statement is often implemented as a jump table where each jump entry will go to a particular "case" label.

In embedded systems, where memory usage is at a premium, many constructs are better served by using a jump table instead of more memory-intensive methods (like a massive if-else-if).

Answer 3

Wikipedia sums it up pretty well:

In computer programming, a branch table (sometimes known as a jump table) is a term used to describe an efficient method of transferring program control (branching) to another part of a program (or a different program that may have been dynamically loaded) using a table of branch instructions. The branch table construction is commonly used when programming in assembly language but may also be generated by a compiler.

... Use of branch tables and other raw data encoding was common in the early days of computing when memory was expensive, CPUs were slower and compact data representation and efficient choice of alternatives were important. Nowadays, they are commonly used in embedded programming and operating system development.

In other words, it's a useful construct to use when your system is extremely memory and/or CPU limited, as is often the case in an embedded platform.

Answer 4

Jump tables, more often known as a Branch table, are usually used only by the machine.

The compiler creates a list of all labels in a assembly program and links all labels to a a memory location. A jump table pretty much is a reference card to where, a function or variable or what ever the label maybe, is stored in memory.

So as a function executes, on finishing it jumps back to it's previous memory location or jumps to the next function, etc.

And If your talking about what I think you are, you don't just need them in embedded systems but in any type of compiled/interpreted environment.

Brian Gianforcaro

Answer 5

A jump table can be either an array of pointers to functions or an array of machine code jump instructions. If you have a relatively static set of functions (such as system calls or virtual functions for a class) then you can create this table once and call the functions using a simple index into the array. This would mean retrieving the pointer and calling a function or jumping to the machine code depending on the type of table used.

The benefits of doing this in embedded programming are:

1. Indexes are more memory efficient than machine code or pointers, so there is a potential for memory savings in constrained environments.
2. For any particular function the index will remain stable and changing the function merely requires swapping out the function pointer.

If does cost you a tiny bit of performance for accessing the table, but this is no worse than any other virtual function call.

Answer 6

A jump table, also known as a branch table, is a series of instructions, all unconditionally branching to another point in code.

You can think of them as a switch (or select) statement where all the cases are filled:

MyJump(int c)
{
   switch(state)
   {
      case 0:
         goto func0label;
      case 1:
         goto func1label;
      case 2:
         goto func2label;
   }
}

Note that there's no return - the code that it jumps to will execute the return, and it will jump back to wherever myjump was called.

This is useful for state machines where you execute certain code based on the state variable. There are many, many other uses, but this is one of the main uses.

It's used where you don't want to waste time fiddling with the stack, and want to save code space. It is especially of use in interrupt handlers where speed is extremely important, and the peripheral that caused the interrupt is only known by a single variable. This is similar to the vector table in processors with interrupt controllers.

One use would be taking a $0.60 microcontroller and generating a composite (TV) signal for video applications. the micro isn't powerful - in fact it's just barely fast enough to write each scan line. A jump table would be used to draw characters, because it would take too long to load a bitmap from memory, and use a for() loop to shove the bitmap out. Instead there's a separate jump to the letter and scan line, and then 8 or so instructions that actually write the data directly to the port.