Branch table

Last updated

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 compilers, especially when implementing optimized switch statements whose values are densely packed together. [1]

Contents

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:

  1. 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.
  2. 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.
  3. 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

...validatex/* transform x to 0 (invalid) or 1,2,3, according to value..)    */y=x*4;/* multiply by branch instruction length (e.g. 4 )               */gotonext+y;/* branch into 'table' of branch instructions                    *//* start of branch table */next:gotocodebad;/* x= 0  (invalid)                                               */gotocodeone;/* x= 1                                                          */gotocodetwo;/* x= 2                                                          */...restofbranchtablecodebad:/* 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. Originally known as transfer vector, 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:

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:

Advantages

Advantages of branch tables include:

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

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

Disadvantages

Example

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

movfINDEX,W; Move the index value into the W (working) register from memoryaddwfPCL,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 labelgotoindex_zero; each of these goto instructions is an unconditional branchgotoindex_one; of code.gotoindex_twogotoindex_threeindex_zero; Code is added here to perform whatever action is required when INDEX = zeroreturnindex_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>typedefvoid(*Handler)(void);/* A pointer to a handler function *//* The functions */voidfunc3(void){printf("3\n");}voidfunc2(void){printf("2\n");}voidfunc1(void){printf("1\n");}voidfunc0(void){printf("0\n");}Handlerjump_table[4]={func0,func1,func2,func3};intmain(intargc,char**argv){intvalue;/* Convert first argument to 0-3 integer (modulus) */value=atoi(argv[1])%4;/* Call appropriate function (func0 thru func3) */jump_table[value]();return0;}

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. [2]

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:

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. [3] [4] The instruction was eventually deprecated in Fortran 90 (in favour of SELECT & CASE statements at the source level). [5]

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", process to obtain a final index for a branch table with zero gaps.

  1. Convert the raw data character to its numeric equivalent (example ASCII 'A' ==> 65 decimal, 0x41 hexadecimal)
  2. Use the numeric integer value as the index into a 256 entry 2-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 × 2) bytes to hold 16-bit unsigned (short) integers for all possible 8-bit bytes. If no validation is required, and only upper case is used, the size of the array may be as small as (26 × 2) = 52 bytes.

Other uses of technique

Although the technique of branching using a branch table is most frequently used 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.

See also

Related Research Articles

C is a general-purpose programming language. It was created in the 1970s by Dennis Ritchie and remains very widely used and influential. By design, C's features cleanly reflect the capabilities of the targeted CPUs. It has found lasting use in operating systems code, device drivers, and protocol stacks, but its use in application software has been decreasing. C is commonly used on computer architectures that range from the largest supercomputers to the smallest microcontrollers and embedded systems.

In computer science, control flow is the order in which individual statements, instructions or function calls of an imperative program are executed or evaluated. The emphasis on explicit control flow distinguishes an imperative programming language from a declarative programming language.

In computer science, threaded code is a programming technique where the code has a form that essentially consists entirely of calls to subroutines. It is often used in compilers, which may generate code in that form or be implemented in that form themselves. The code may be processed by an interpreter or it may simply be a sequence of machine code call instructions.

<span class="mw-page-title-main">Atari BASIC</span> Dialect of the BASIC programming language

Atari BASIC is an interpreter for the BASIC programming language that shipped with Atari 8-bit computers. Unlike most American BASICs of the home computer era, Atari BASIC is not a derivative of Microsoft BASIC and differs in significant ways. It includes keywords for Atari-specific features and lacks support for string arrays.

x86 assembly language is the name for the family of assembly languages which provide some level of backward compatibility with CPUs back to the Intel 8008 microprocessor, which was launched in April 1972. It is used to produce object code for the x86 class of processors.

<span class="mw-page-title-main">C syntax</span> Set of rules defining correctly structured programs

The syntax of the C programming language is the set of rules governing writing of software in C. It is designed to allow for programs that are extremely terse, have a close relationship with the resulting object code, and yet provide relatively high-level data abstraction. C was the first widely successful high-level language for portable operating-system development.

<span class="mw-page-title-main">Pointer (computer programming)</span> Object which stores memory addresses in a computer program

In computer science, a pointer is an object in many programming languages that stores a memory address. This can be that of another value located in computer memory, or in some cases, that of memory-mapped computer hardware. A pointer references a location in memory, and obtaining the value stored at that location is known as dereferencing the pointer. As an analogy, a page number in a book's index could be considered a pointer to the corresponding page; dereferencing such a pointer would be done by flipping to the page with the given page number and reading the text found on that page. The actual format and content of a pointer variable is dependent on the underlying computer architecture.

<span class="mw-page-title-main">IBM 1130</span> 16-bit IBM minicomputer introduced in 1965

The IBM 1130 Computing System, introduced in 1965, was IBM's least expensive computer at that time. A binary 16-bit machine, it was marketed to price-sensitive, computing-intensive technical markets, like education and engineering, succeeding the decimal IBM 1620 in that market segment. Typical installations included a 1 megabyte disk drive that stored the operating system, compilers and object programs, with program source generated and maintained on punched cards. Fortran was the most common programming language used, but several others, including APL, were available.

In computer programming, a return statement causes execution to leave the current subroutine and resume at the point in the code immediately after the instruction which called the subroutine, known as its return address. The return address is saved by the calling routine, today usually on the process's call stack or in a register. Return statements in many programming languages allow a function to specify a return value to be passed back to the code that called the function.

Loop unrolling, also known as loop unwinding, is a loop transformation technique that attempts to optimize a program's execution speed at the expense of its binary size, which is an approach known as space–time tradeoff. The transformation can be undertaken manually by the programmer or by an optimizing compiler. On modern processors, loop unrolling is often counterproductive, as the increased code size can cause more cache misses; cf. Duff's device.

The computer programming languages C and Pascal have similar times of origin, influences, and purposes. Both were used to design their own compilers early in their lifetimes. The original Pascal definition appeared in 1969 and a first compiler in 1970. The first version of C appeared in 1972.

In computer programming, a one-pass compiler is a compiler that passes through the parts of each compilation unit only once, immediately translating each part into its final machine code. This is in contrast to a multi-pass compiler which converts the program into one or more intermediate representations in steps between source code and machine code, and which reprocesses the entire compilation unit in each sequential pass.

In computer programming, the term hooking covers a range of techniques used to alter or augment the behaviour of an operating system, of applications, or of other software components by intercepting function calls or messages or events passed between software components. Code that handles such intercepted function calls, events or messages is called a hook.

sizeof is a unary operator in the programming languages C and C++. It generates the storage size of an expression or a data type, measured in the number of char-sized units. Consequently, the construct sizeof (char) is guaranteed to be 1. The actual number of bits of type char is specified by the preprocessor macro CHAR_BIT, defined in the standard include file limits.h. On most modern computing platforms this is eight bits. The result of sizeof has an unsigned integer type that is usually denoted by size_t.

PLANC is a high-level programming language.

This is an overview of Fortran 95 language features. Included are the additional features of TR-15581:Enhanced Data Type Facilities, which have been universally implemented. Old features that have been superseded by new ones are not described – few of those historic features are used in modern programs although most have been retained in the language to maintain backward compatibility. The current standard is Fortran 2023; many of its new features are still being implemented in compilers.

In computer programming, a variable-length array (VLA), also called variable-sized or runtime-sized, is an array data structure whose length is determined at runtime, instead of at compile time. In the language C, the VLA is said to have a variably modified data type that depends on a value.

In programming languages, a label is a sequence of characters that identifies a location within source code. In most languages, labels take the form of an identifier, often followed by a punctuation character. In many high-level languages, the purpose of a label is to act as the destination of a GOTO statement. In assembly language, labels can be used anywhere an address can. Also in Pascal and its derived variations. Some languages, such as Fortran and BASIC, support numeric labels. Labels are also used to identify an entry point into a compiled sequence of statements.

<span class="mw-page-title-main">Control table</span> Data structures that control the execution order of computer commands

Control tables are tables that control the control flow or play a major part in program control. There are no rigid rules about the structure or content of a control table—its qualifying attribute is its ability to direct control flow in some way through "execution" by a processor or interpreter. The design of such tables is sometimes referred to as table-driven design. In some cases, control tables can be specific implementations of finite-state-machine-based automata-based programming. If there are several hierarchical levels of control table they may behave in a manner equivalent to UML state machines

In computer programming, a function, procedure, method, subroutine, routine, or subprogram is a callable unit of software logic that has a well-defined interface and behavior and can be invoked multiple times.

References

  1. Page, Daniel (2009). A Practical Introduction to Computer Architecture. Springer Science & Business Media. p. 479. ISBN   9781848822559.
  2. Jones, Nigel (1 May 1999). "How to Create Jump Tables via Function Pointer Arrays in C and C++". Archived from the original on 12 February 2012. Retrieved 12 July 2008.
  3. "Alternate Entry Points (ENTRY)". Using and Porting GNU Fortran. Free Software Foundation. 2001-06-07. Retrieved 2016-11-25.
  4. Thomas, R.E. (1976-04-29). "FORTRAN Compilers and Loaders". ACD: Engineering Paper No 42. ACD. Retrieved 2009-04-10.
  5. "A Brief Introduction to Fortran 90". Decremental/Deprecated/Redundant Features. Retrieved 2009-04-10.