jump table
   HOME

TheInfoList



OR:

In
computer programming Computer programming is the process of performing a particular computation (or more generally, accomplishing a specific computing result), usually by designing and building an executable computer program. Programming involves tasks such as anal ...
, 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 In computer programming, assembly language (or assembler language, or symbolic machine code), often referred to simply as Assembly and commonly abbreviated as ASM or asm, is any low-level programming language with a very strong correspondence be ...
but may also be generated by
compiler In computing, a compiler is a computer program that Translator (computing), translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily ...
s, especially when implementing optimized
switch statement In computer programming languages, a switch statement is a type of selection control mechanism used to allow the value of a variable or expression to change the control flow of program execution via search and map. Switch statements function s ...
s whose values are densely packed together.


Typical implementation

A branch table consists of a serial list of unconditional branch instructions that is branched into using an offset created by
multiplying Multiplication (often denoted by the Multiplication sign, cross symbol , by the mid-line #Notation and terminology, dot operator , by juxtaposition, or, on computers, by an asterisk ) is one of the four Elementary arithmetic, elementary Op ...
a
sequential In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in mo ...
index by the instruction length (the number of bytes in memory occupied by each branch instruction). It relies on the fact that
machine code In computer programming Computer programming is the process of performing a particular computation (or more generally, accomplishing a specific computing result), usually by designing and building an executable computer program. Programm ...
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 Raw data, also known as primary data, are ''data'' (e.g., numbers, instrument readings, figures, etc.) collected from a source. In the context of examinations, the raw data might be described as a raw score (after test scores). If a scientist ...
values that may be easily converted to
sequential In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in mo ...
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 Addition (usually signified by the Plus and minus signs#Plus sign, plus symbol ) is one of the four basic Operation (mathematics), operations of arithmetic, the other three being subtraction, multiplication and Division (mathematics), division. ...
of the offset onto the
program counter The program counter (PC), commonly called the instruction pointer (IP) in Intel x86 and Itanium microprocessors, and sometimes called the instruction address register (IAR), the instruction counter, or just part of the instruction sequencer, is ...
register Register or registration may refer to: Arts entertainment, and media Music * Register (music) A register is the "height" or range of a note, set of pitches or pitch classes, melody A melody (from Greek language, Greek μελῳ ...
(unless, in some
instruction set In computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied sci ...
s, 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 An array is a systematic arrangement of similar objects, usually in rows and columns. Things called an array include: {{TOC right Music * In twelve-tone The twelve-tone technique—also known as dodecaphony, twelve-tone serialism, and ( ...
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 In computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied scienc ...
" or "
virtual method table In computer programming, a virtual method table (VMT), virtual function table, virtual call table, dispatch table, vtable, or vftable is a mechanism used in a programming language to support dynamic dispatch (or Run time (program lifecycle phase ...
" 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 In computer science, threaded code is a programming technique where the Source code, 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 ...
, and is conceptually similar to a
control table Control tables are array data structure, 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 c ...
. 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 In computing, late binding or dynamic linkage—though not an identical process to Dynamic linker, dynamically linking imported code Library (computing), libraries—is a computer programming mechanism in which the Method (computer programming), ...
is involved or not.


History

Use of branch tables and other
raw data Raw data, also known as primary data, are ''data'' (e.g., numbers, instrument readings, figures, etc.) collected from a source. In the context of examinations, the raw data might be described as a raw score (after test scores). If a scientist ...
encoding was common in the early days of computing when
memory Memory is the faculty of the mind by which data or information is Encoding (memory), encoded, stored, and retrieved when needed. It is the retention of information over time for the purpose of influencing future action. If Foresight (psycholo ...
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 An operating system (OS) is system software that manages computer hardware, software resources, and provides common daemon (computing), services for computer programs. Time-sharing operating systems scheduler (computing), schedule tasks for ef ...
development. In many operating systems, both
system call In computing, a system call (commonly abbreviated to syscall) is the programmatic way in which a computer program requests a service from the operating system on which it is executed. This may include hardware-related services (for example, acc ...
s and
library A library is a collection of materials, books or media that are accessible for use and not just for display purposes. A library provides physical (hard copies) or digital access (soft copies) materials, and may be a physical location or a vir ...
functions may be referenced by an
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language of ...
index into a branch table. * some
computer architecture In computer engineering, computer architecture is a description of the structure of a computer system made from component parts. It can sometimes be a high-level description that ignores details of the implementation. At a more detailed level, the ...
s such as
IBM/360 The IBM System/360 (S/360) is a family of mainframe computer systems that was announced by IBM on April 7, 1964, and delivered between 1965 and 1978. It was the first family of computers designed to cover both commercial and scientific applicat ...
use branch tables for dispatching
interrupt In digital computers, an interrupt (sometimes referred to as a trap) is a request for the processor to ''interrupt'' currently executing code (when permitted), so that the event can be processed in a timely manner. If the request is accepted ...
s


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 In programming, a spot of a function (programming), function or subroutine is the location (line of code) where the function is called (or may be called, through dynamic dispatch). A call site is where zero or more argument (programming), arguments ...
to determine subsequent
program flow In computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied scie ...
) * Algorithmic and code efficiency (data need only be
encode The Encyclopedia of DNA Elements (ENCODE) is a public research project which aims to identify functional elements in the human genome. ENCODE also supports further biomedical research by "generating community resources of genomics data, software, ...
d once and branch table code is usually compact), and the potential to attain high
data compression In information theory, data compression, source coding, or bit-rate reduction is the process of encoding information using fewer bits than the original representation. Any particular compression is either Lossy compression, lossy or Lossless com ...
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 A library is a collection of materials, books or media that are accessible for use and not just for display purposes. A library provides physical (hard copies) or digital access (soft copies) materials, and may be a physical location or a vir ...
functions, where they may be referenced by an
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language of ...
: * improve compatibility with subsequent software versions. If the code of a function and the address of its
entry point In computer programming Computer programming is the process of performing a particular computation (or more generally, accomplishing a specific computing result), usually by designing and building an executable computer program. Programmin ...
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 In computer programming, indirection (also called dereferencing) is the ability to reference something using a name, reference, or container instead of the value itself. The most common form of indirection is the act of manipulating a value throug ...
, which incurs a usually small performance hit. * 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 #include typedef void (*Handler)(void); /* A pointer to a handler function */ /* The functions */ void func3 (void) void func2 (void) void func1 (void) void func0 (void) Handler jump_table = ; int main (int argc, char **argv)


Jump table example in PL/I

PL/I PL/I (Programming Language One, pronounced and sometimes written PL/1) is a Procedural programming, procedural, imperative programming, imperative computer programming language developed and published by IBM. It is designed for scientific, eng ...
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 Memory is the faculty of the mind by which data or information is Encoding (memory), encoded, stored, and retrieved when needed. It is the retention of information over time for the purpose of influencing future action. If Foresight (psycholo ...
requirement may not really be an issue at all. 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 GoTo (goto, GOTO, GO TO or other case combinations, depending on the programming language) is a statement found in many computer programming language A programming language is a system of notation for writing computer program, computer prog ...
', referring to the instruction found in the Fortran series of compilers. The instruction was eventually deprecated in Fortran 90 (in favour of SELECT & CASE statements at the source level).


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 In computing, a hash table, also known as hash map, is a data structure that implements an associative array or dictionary. It is an abstract data type that maps Unique key, keys to Value (computer science), values. A hash table uses a hash ...
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 Raw data, also known as primary data, are ''data'' (e.g., numbers, instrument readings, figures, etc.) collected from a source. In the context of examinations, the raw data might be described as a raw score (after test scores). If a scientist ...
) can be used in a two-step, "
trivial hash function Index mapping (or direct addressing, or a trivial hash function A hash function is any Function (mathematics), function that can be used to map data (computing), data of arbitrary size to fixed-size values. The values returned by a hash functi ...
", process to obtain a final index for a branch table with zero gaps. # Convert the
raw data Raw data, also known as primary data, are ''data'' (e.g., numbers, instrument readings, figures, etc.) collected from a source. In the context of examinations, the raw data might be described as a raw score (after test scores). If a scientist ...
character to its numeric equivalent (example
ASCII ASCII ( ), abbreviated from American Standard Code for Information Interchange, is a character encoding standard for electronic communication. ASCII codes represent text in computers, telecommunications equipment, and other devices. Because of ...
'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 compiler In computing, an optimizing compiler is a compiler that tries to minimize or maximize some attributes of an executable computer program. Common requirements are to minimize a computer program, program's execution time, memory (computers), memory f ...
s or JIT compilers in
loop unrolling 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 file, binary size, which is an approach known as space–time tradeoff. The tran ...
.


See also

*
Dispatch table In computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied scienc ...
a branch table by another name used for
late binding In computing, late binding or dynamic linkage—though not an identical process to Dynamic linker, dynamically linking imported code Library (computing), libraries—is a computer programming mechanism in which the Method (computer programming), ...
*
Function pointer A function pointer, also called a subroutine pointer or procedure pointer, is a pointer (computer programming), pointer that points to a function. As opposed to referencing a data value, a function pointer points to executable code within memory. ...
arrays of addresses to functions as used in branch tables *
Indirect branch An indirect branch (also known as a computed jump, indirect jump and register-indirect jump) is a type of program control instruction present in some machine language In computer programming, machine code is any low-level programming lan ...
*
Lookup table In computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied scien ...
an array of items to be matched, sometimes holding pre-calculated results *
Switch statement In computer programming languages, a switch statement is a type of selection control mechanism used to allow the value of a variable or expression to change the control flow of program execution via search and map. Switch statements function s ...
a high level language conditional statement that may generate a branch table *
Virtual method table In computer programming, a virtual method table (VMT), virtual function table, virtual call table, dispatch table, vtable, or vftable is a mechanism used in a programming language to support dynamic dispatch (or Run time (program lifecycle phase ...
a branch table by another name with dynamically assigned pointers for dispatching (see Dispatch table)


References


External links



Example of branch table in
Wikibooks Wikibooks (previously called ''Wikimedia Free Textbook Project'' and ''Wikimedia-Textbooks'') is a wiki-based Wikimedia project hosted by the Wikimedia Foundation for the creation of free content digital textbooks and annotated texts that anyo ...
for
IBM S/360 The IBM System/360 (S/360) is a family of mainframe computer A mainframe computer, informally called a mainframe or big iron, is a computer A computer is a machine that can be programmed to carry out sequences of arithmetic or l ...


Examples of, and arguments for, Jump Tables via Function Pointer Arrays in C (programming language), C/
C++ C++ (pronounced "C plus plus") is a high-level general-purpose programming language In computer software, a general-purpose programming language (GPL) is a programming language for building software in a wide variety of application Domain (so ...


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 {{DEFAULTSORT:Branch Table Computer performance Conditional constructs Articles with example C code Control flow