Branch table

In computer programming, a branch table or jump table is a 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 or jump instructions. It is a form of multiway branch. The branch table construction is commonly used when programming in assembly language but may also be generated by a compiler, especially when implementing an optimized switch statement where known, small ranges are involved with few gaps.

Typical implementation

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 relies on 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 3 steps:

optionally validating the input data to ensure it is acceptable (this may occur without cost as part of the next step, if the input is a single byte and a 256 byte translate table is used to directly obtain the offset below). Also, if there is no doubt about the values of the input, this step can be omitted.
transform the data into an offset into the branch table. This usually involves multiplying or shifting (effectively multiplying by a power of 2) it to take into account the instruction length. If a static translate table is used, this multiplying can be performed manually or by the compiler, without any run time cost.
branching to an address made up of the base address of the branch table plus the just generated offset. This sometimes involves an addition of the offset onto the program counter register (unless, in some instruction sets, the branch instruction allows an extra index register). This final address usually points to one of a sequence of unconditional branch instructions, or the instruction immediately beyond them (saving one entry in the table).

The following pseudocode illustrates the concept

 ...  validate x                   /* transform x to 0 (invalid) or 1,2,3, according to value..)    */
       y  = x*4;                   /* multiply by branch instruction length (e.g. 4 )               */
       goto next(y);               /* branch into 'table' of branch instructions                    */
 /* start of branch table */
 next: goto codebad;               /* x= 0  (invalid)                                               */
       goto codeone;               /* x= 1                                                          */
       goto codetwo;               /* x= 2                                                          */
 ... rest of branch table
 codebad:                          /* deal with invalid input                                       */

Alternative implementation using addresses

Another method of implementing a branch table is with an array of pointers from which the required function's address is retrieved. This method is also more recently known under such different names as "dispatch table" or "virtual method table" but essentially performing exactly the same purpose. This pointer function method can result in saving one machine instruction, and avoids the indirect jump (to one of the branch instructions).

The resulting list of pointers to functions is almost identical to direct threaded code, and is conceptually similar to a control table.

The actual method used to implement a branch table is usually based on:

the architecture of the processor on which the code is to be executed,
whether it is a compiled or interpreted language and
whether late binding is involved or not.

History

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 still used in:

embedded programming
operating system development. In many operating systems, both system calls and library functions may be referenced by an integer index into a branch table.
some computer architectures such as IBM/360 use branch tables for dispatching interrupts

Advantages

Advantages of branch tables include:

compact code structure (despite repeated branch opcodes)
reduced source statements (versus repetitive If statements)
reduced requirement to test return codes individually (if used at call site to determine subsequent program flow)
Algorithmic and code efficiency (data need only be encoded once and branch table code is usually compact), and the potential to attain high data compression ratios. For example, when compressing country names to country codes, a string such as "Central African Republic" can be compressed to a single index, resulting in large savings – particularly when the string appears many times. In addition, this same index can be used to access related data in separate tables, reducing storage requirements further.

For library functions, where they may be referenced by an integer:

improve compatibility with subsequent software versions. If the code of a function and the address of its entry point is changed, only the branch instruction in the branch table needs to be adjusted; application software compiled against the library, or for the operating system, does not need modification.

In addition, calling functions by number (the index into the table) can sometimes be useful in some cases in normal application programming.

Disadvantages

Extra level of indirection
Restrictions in some programming languages (although there are usually alternative ways of implementing the basic concept of multiway branching).

Example

A simple example of branch table use in the 8-bit Microchip PIC assembly language is:

     movf    INDEX,W     ; move the index value into the W (working) register from memory
     addwf   PCL,F       ; add it to the program counter. each PIC instruction is one byte
                         ; so there is no need to perform any multiplication. 
                         ; Most architectures will transform the index in some way before 
                         ; adding it to the program counter

 table                   ; the branch table begins here with this label
     goto    index_zero  ; each of these goto instructions is an unconditional branch
     goto    index_one   ; of code
     goto    index_two
     goto    index_three

 index_zero
     ; code is added here to perform whatever action is required when INDEX = zero
     return

 index_one
 ...

Note: this code will work only if PCL < (table + index_last). To ensure this condition we may use an "org" directive. And if GOTO (PIC18F for example) is 2 bytes, this limits the number of table entries to less than 128.

Jump table example in C

Another simple example, this time demonstrating a jump table rather than a mere branch table. This allows program blocks outside of the currently active procedure/function to be called:

#include <stdio.h>
#include <stdlib.h>

typedef void (*Handler)(void);    /* A pointer to a handler function */

/* The functions */
void func3 (void) { printf( "3\n" ); }
void func2 (void) { printf( "2\n" ); }
void func1 (void) { printf( "1\n" ); }
void func0 (void) { printf( "0\n" ); }

Handler jump_table[4] = {func0, func1, func2, func3};

int main (int argc, char **argv) {
    int value;

    /* Convert first argument to 0-3 integer (modulus) */
    value = ((atoi(argv[1]) % 4) + 4) % 4;

    /* Call appropriate function (func0 thru func3) */
    jump_table[value]();

    return 0;
}

Jump table example in PL/I

PL/I implements a jump table as an array of label variables. These may be initialized in an unusual way by using a subscripted statement label. PL/I label variables are not simply the address of the statement, but usually contain additional information on the state of the code block to which they belong. Without the unusual initialization, this could also be coded with calls and an array of entry variables.

    declare lab (10) label;
    declare x fixed binary;
    goto lab(x);
  lab(1): /* code for choice 1 */ ;
    ...
  lab(2): /* code for choice 2 */ ;
    ...

Compiler generated branch tables

Programmers frequently leave the decision of whether or not to create a branch table to the compiler, believing that it is perfectly capable of making the correct choice from the known search keys. This may be true for optimizing compilers for relatively simple cases where the range of search keys is limited. However, compilers are not as intelligent as humans and cannot have a deep knowledge of 'context', believing that a range of possible search key integer values such as 1, 2, 4, 6, 7, 20, 23, 40, 42, 50 & 1000 would generate a branch table with an excessively large number of empty entries (900+) for very little advantage. (A good optimizing compiler may then presort the values and generate code for a binary chop search, as a 'second best' option.) In fact, the application may be highly "time critical" and memory requirement may not really be an issue at all.^[1]

However, a little 'common sense' can transform this particular case, and many other similar cases, to a simple two-step process with very large potential savings – while still eventually leaving the ultimate choice to the compiler – but 'assisting its decision' considerably:

First, test for search key=1000 and perform appropriate branch.
Allow the compiler to 'choose' to generate a branch table on the remaining search keys (1-50).

Variations along similar lines can be used in cases where there are two sets of short ranges with a large gap between ranges.

Computed GoTo

While the technique is now known as 'branch tables', early compiler users called the implementation 'computed GoTo', referring to the instruction found in the Fortran series of compilers.^[2]^[3] The instruction was eventually deprecated in Fortran 90 (in favour of SELECT & CASE statements at the source level).^[4]

Creating the index for the branch table

Where there is no obvious integer value available for a branch table it can nevertheless be created from a search key (or part of a search key) by some form of arithmetic transformation, or could simply be the row number of a database or the entry number in an array containing the search key found during earlier validation of the key.

A hash table may be required to form the index in some cases. However, for single byte input values such as A-Z (or the first byte of a longer key), the contents of the byte itself (raw data) can be used in a two-step, "trivial hash function",^[5] process to obtain a final index for a branch table with zero gaps.

Convert the raw data character to its numeric equivalent (example ASCII 'A' ==> 65 decimal, 0x41 hexadecimal)
Use the numeric integer value as index into a 256 byte array, to obtain a second index (invalid entries 0; representing gaps, otherwise 1, 2, 3 etc.)

The array would be no larger than (256 x 2) bytes – to hold all possible 16-bit unsigned (short) integers. If no validation is required, and only upper case is used, the size of the array may be as small as (26 x 2) = 52 bytes.

Other uses of technique

Although the technique of branching using a branch table is most frequently utilized solely for the purpose of altering program flow – to jump to a program label that is an unconditional branch – the same technique can be used for other purposes. For example, it can be used to select a starting point in a sequence of repeated instructions where drop through is the norm and intentional. This can be used for example by optimizing compilers or JIT compilers in loop unrolling.

References

↑
↑ Coon, Ty (1991-06-02). "Using and Porting GNU Fortran". ASSIGN and GOTO. Free Software Foundation. Retrieved 2009-04-10.
↑ Thomas, R.E. (1976-04-29). "FORTRAN Compilers and Loaders". ACD: Engineering Paper No 42. ACD. Retrieved 2009-04-10.
↑ "A Brief Introduction to Fortran 90". Decremental/Deprecated/Redundant Features. Retrieved 2009-04-10.
↑ Hash_function#Trivial_hash_function

External links

Example of branch table in Wikibooks for IBM S/360
Examples of, and arguments for, Jump Tables via Function Pointer Arrays in C/C++
Example code generated by 'Switch/Case' branch table in C, versus IF/ELSE.
Example code generated for array indexing if structure size is divisible by powers of 2 or otherwise.
"Arrays of Pointers to Functions" by Nigel Jones

This article is issued from Wikipedia - version of the Monday, December 21, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.