Content deleted Content added
m →Typical implementation: <source lang="c"> |
Combine examples under a single section |
||
| (27 intermediate revisions by 20 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==
Line 7 ⟶ 9:
# 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
<
...
y
goto next
/* start of branch table */
next: goto codebad; /* x= 0 (invalid) */
Line 17 ⟶ 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 47 ⟶ 49:
==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 to the program counter.
; 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 95 ⟶ 99:
/* Convert first argument to 0-3 integer (modulus) */
value =
/* Call appropriate function (func0 thru func3) */
Line 102 ⟶ 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 114 ⟶ 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 129 ⟶ 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==
Line 135 ⟶ 139:
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
# 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==
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]]
| |||