Difference between a lookup table and a jump table

Question

I know that jump tables are mainly used to create switch statements in assembly:

int a = 5;
switch (a){
  case 5:
  ...
   break;
  ...
} 

In this case, jump is just a pointer to a memory address which has instructions to do case 5 work.

If i'm not mistaking, a lookup table has pre calculated results in an array? so instead of writing code to calculate them you just return the array index? Sort of like a HashMap.

Above two sound very similar to me, are they basically the same thing? One points to instructions and the other returns pre calculated results?

Answer 1

If i'm not mistaking, a lookup table has pre calculated results in an array? so instead of writing code to calculate them you just return the array index? Sort of like a HashMap.

Correct. What's stored at that index could be data, or a pointer to data, or a pointer to a function etc etc.

A jump table is simply a look-up table where each index corresponds to a function, most commonly implemented in C as an array of function pointers.

Answer 2

Jump tables are, as you mention, native code that's arranged in a way that's easy to jump to depending on integer values. If the jump table is comprised of just short jump instructions, you can multiply your switch value by 3 and add the offset of the first entry in the table and jump (JMP or CALL) to it.

Lookup tables on the other hand are just raw data. It's still stored in a packed format so you can access it through a linear operation on your index (size * index + offset), but to make use of it you use an indirect move (MOV dest, [expression]) instead of physically jumping to it.

Keep in mind that lookup tables are just an optimization, albeit a huge one, you can load values into registers with a jump table as well. This is an is-a relationship.

Answer 3

What happens under the hood is up the compiler. But you're right on your observations. Here is a snippet demonstrating what compilers often do to switch statements:

#include <stdio.h>

void foo(void) { printf("foo\n"); }
void bar(void) { printf("bar\n"); }

int main(void)
{
    // Array of size 2 of pointer to function without arguments returning void
    // Yes, declaring function pointers is not intuitive...
    void (*f[2])(void);

    f[0] = foo;
    f[1] = bar;

    int x;
    printf("Enter a number (0 or 1): ");
    scanf("%d", &x);

    printf("Using switch\n");
    switch(x) {
    case 0: foo(); break;
    case 1: bar(); break;
    }

    printf("Using array of function pointers\n");
    f[x]();
}