Content deleted Content added
Help needed: Shifting |
Combine examples under a single section |
||
| (40 intermediate revisions by 26 users not shown) | |||
Line 1:
{{short description|Method of transferring program control to another part of a program}}
In [[computer programming]], a '''branch table''' or '''jump table''' is a method of transferring program control ([[Branch (computer science)|branching]]) to another part of a program (or a different program that may have been dynamically loaded) using a table of branch or jump [[Instruction (computer science)|instruction]]s. 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.▼
{{original research|date=November 2016}}
▲In [[computer programming]], a '''branch table''' or '''jump table''' is a method of transferring program control ([[Branch (computer science)|branching]]) to another part of a program (or a different program that may have been dynamically loaded) using a table of branch or jump [[Instruction (computer science)|instruction]]s. 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
==Typical implementation==
A branch table consists of a serial list of [[unconditional branch]] instructions that is branched into using an [[Offset (computer science)|offset]] created by [[multiple (mathematics)|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]] [[Instruction (computer science)|instruction]]s 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 [[Data validation|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 (computer science)|offset]] into the branch table. This usually involves multiplying or [[Bit shift#Bit shifts|shifting]]
# 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]] [[Processor register|register]] (unless, in some [[instruction set]]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
<syntaxhighlight lang="c">
... validate x
goto next + y; /* branch into 'table' of branch instructions */
/* start of branch table */
next: goto codebad; /* x= 0 (invalid) */
Line 16 ⟶ 19:
... rest of branch table
codebad: /* deal with invalid input */
</syntaxhighlight>
==Alternative implementation using addresses==
Another method of implementing a branch table is with an [[Array data structure|array]] of [[Pointer (computer programming)|pointers]] from which the required [[Function (computing)|function's]] address is retrieved.
The resulting list of pointers to functions is almost identical to direct [[threaded code]], and is conceptually similar to a [[control table]].
Line 31 ⟶ 35:
* [[Embedded system|embedded]] programming
* [[operating system]] development. In many operating systems, both [[system call]]s and [[Library (computer science)|library]] functions may be referenced by an [[integer]] index into a branch table.
* some [[computer architecture]]s such as [[IBM/360]]
==Advantages==
Line 40 ⟶ 44:
* [[algorithmic efficiency|Algorithmic]] and code efficiency (data need only be [[Code|encode]]d 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 (computer science)|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
In addition, calling functions by number (the index into the table)
==Disadvantages==
* Extra level of [[indirection]], which incurs a usually small performance hit.
* Restrictions in some programming languages,
==Example==
=== 8-bit Microchip PIC assembly language ===
A simple example of branch table use in the 8-bit [[PIC microcontroller|Microchip PIC]] assembly language is:
<
movf INDEX,W ;
addwf PCL,F ; add it
; 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 ;
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
;
return
index_one
...
</syntaxhighlight>
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.
==
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>
Line 92 ⟶ 98:
int value;
/* Convert first argument to 0-3 integer (
value = atoi(argv[1]) % 4;
/* Call appropriate function (func0 thru func3) */
Line 103 ⟶ 106:
return 0;
}
</syntaxhighlight>
==
[[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.
<pre>
declare lab (10) label;
declare x fixed binary;
Line 115 ⟶ 118:
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.
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
* First, test for search key=1000 and perform appropriate branch.
Line 130 ⟶ 133:
===Computed GoTo===
While the technique is now known as 'branch tables', early compiler users called the implementation '[[Computed goto|computed GoTo]]', referring to the instruction found in the Fortran series of compilers.<ref name="GNU">{{cite web|url=
==Creating the index for the branch table==
Where there is no obvious integer value available for a
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
# Convert the [[raw data]] character to its numeric equivalent (example [[ASCII]] 'A' ==> 65 decimal, 0x41 hexadecimal)
# 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
If no validation is required, and only upper case is used, the size of the array may be as small as (26 ==Other uses of technique==
Although the technique of branching using a branch table is most frequently
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]]s or [[Just-in-time compilation|JIT]] compilers in [[loop unrolling]]. ==See also==
* [[Dispatch table]] a branch table by another name used for [[late binding]]
* [[Function pointer]] arrays of addresses to functions as used in branch tables
* [[Indirect branch]]
* [[Lookup table]] an array of items to be matched, sometimes holding pre-calculated results
* [[Switch statement]] a high level language conditional statement that may generate a branch table
Line 155 ⟶ 161:
==External links==
{{Commonscat}}
*
*
* [http://www.eventhelix.com/realtimemantra/Basics/CToAssemblyTranslation3.htm] Example code generated by 'Switch/Case' branch table in C, versus IF/ELSE.▼
*
▲*
*
{{DEFAULTSORT:Branch Table}}
Line 165 ⟶ 172:
[[Category:Conditional constructs]]
[[Category:Articles with example C code]]
[[Category:Control flow]]
| |||