1016:
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
36:
1004:. 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.
1103:
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
1015:
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
498:
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
1059:
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
175:
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
1027:
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:
1094:
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.
205:, 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).
649:
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.
187:(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.
365:" 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).
1051:', 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).
519:
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.
658:
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:
1067:
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 (
1007:
declare lab (10) label; declare x fixed binary; goto lab(x); lab(1): /* code for choice 1 */ ; ... lab(2): /* code for choice 2 */ ; ...
1090:
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.)
539:
Restrictions in some programming languages, although there are usually alternative ways of implementing the basic concept of multiway branching.
523:
In addition, calling functions by number (the index into the table) can sometimes be useful in some cases in normal application programming.
414:
were slower and compact data representation and efficient choice of alternatives were important. Nowadays, they are commonly still used in:
1187:
79:
190:
branching to an address made up of the base address of the branch table plus the just generated offset. This sometimes involves an
159:
for branching have a fixed length and can be executed extremely efficiently by most hardware, and is most useful when dealing with
46:
152:
index by the instruction length (the number of bytes in memory occupied by each branch instruction). It relies on the fact that
1362:
1039:
Variations along similar lines can be used in cases where there are two sets of short ranges with a large gap between ranges.
108:) to another part of a program (or a different program that may have been dynamically loaded) using a table of branch or jump
1104:
point in a sequence of repeated instructions where drop through is the norm and intentional. This can be used for example by
346:
156:
109:
1357:
167:
index values. Given such data, a branch table can be extremely efficient. It usually consists of the following 3 steps:
61:
504:
432:
57:
180:
141:
105:
1323:
1109:
1337:
1332:
1320:
1204:
515:
improve compatibility with subsequent software versions. If the code of a function and the address of its
487:
145:
1367:
1072:
1021:
443:
1256:
1160:
a branch table by another name with dynamically assigned pointers for dispatching (see
Dispatch table)
1339:
Example code generated for array indexing if structure size is divisible by powers of 2 or otherwise.
1157:
1047:
While the technique is now known as 'branch tables', early compiler users called the implementation '
362:
350:
342:
137:
93:
1105:
549:
1342:
407:
198:
1230:
1183:
1035:
Allow the compiler to 'choose' to generate a branch table on the remaining search keys (1-50).
1020:
search, as a 'second best' option. In fact, the application may be highly "time critical" and
117:
1151:
1134:
495:
424:
125:
1140:
418:
202:
195:
172:
113:
1281:
1125:
1113:
358:
1351:
1048:
373:
369:
1145:
1129:
481:
390:
153:
494:
once and branch table code is usually compact), and the potential to attain high
1017:
533:
516:
428:
1064:
164:
149:
1308:
635:; Code is added here to perform whatever action is required when INDEX = zero
1315:
1311:
1154:
a high level language conditional statement that may generate a branch table
477:
451:
184:
1322:
Examples of, and arguments for, Jump Tables via
Function Pointer Arrays in
262:/* branch into 'table' of branch instructions */
1334:
Example code generated by 'Switch/Case' branch table in C, versus IF/ELSE.
368:
The resulting list of pointers to functions is almost identical to direct
17:
1148:
an array of items to be matched, sometimes holding pre-calculated results
1080:
1068:
403:
357:, this method is also more recently known under such different names as "
191:
160:
121:
379:
The actual method used to implement a branch table is usually based on:
508:
447:
436:
1075:", process to obtain a final index for a branch table with zero gaps.
383:
the architecture of the processor on which the code is to be executed,
116:. The branch table construction is commonly used when programming in
1205:"How to Create Jump Tables via Function Pointer Arrays in C and C++"
64:. Statements consisting only of original research should be removed.
1327:
331:/* deal with invalid input */
307:/* x= 2 */
295:/* x= 1 */
283:/* x= 0 (invalid) */
244:/* multiply by branch instruction length (e.g. 4 ) */
223:/* transform x to 0 (invalid) or 1,2,3, according to value..) */
27:
Method of transferring program control to another part of a program
1208:
1084:
476:
reduced requirement to test return codes individually (if used at
590:; Most architectures will transform the index in some way before
584:; add it to the program counter. Each PIC instruction is one byte
997:
569:; Move the index value into the W (working) register from memory
491:
1032:
First, test for search key=1000 and perform appropriate branch.
411:
29:
608:; each of these goto instructions is an unconditional branch
183:
into the branch table. This usually involves multiplying or
1137:
arrays of addresses to functions as used in branch tables
341:
Another method of implementing a branch table is with an
466:
compact code structure (despite repeated branch opcodes)
406:
encoding was common in the early days of computing when
499:
separate tables, reducing storage requirements further.
53:
1182:. Springer Science & Business Media. p. 479.
939:/* Convert first argument to 0-3 integer (modulus) */
587:; so there is no need to perform any multiplication.
386:
whether it is a compiled or interpreted language and
969:/* Call appropriate function (func0 thru func3) */
548:A simple example of branch table use in the 8-bit
1180:A Practical Introduction to Computer Architecture
209:The following pseudocode illustrates the concept
1344:"Arrays of Pointers to Functions" by Nigel Jones
1024:requirement may not really be an issue at all.
536:, which incurs a usually small performance hit.
1083:character to its numeric equivalent (example
599:; The branch table begins here with this label
507:functions, where they may be referenced by an
469:reduced source statements (versus repetitive
427:development. In many operating systems, both
104:is a method of transferring program control (
8:
140:instructions that is branched into using an
136:A branch table consists of a serial list of
353:address is retrieved. Originally known as
337:Alternative implementation using addresses
128:whose values are densely packed together.
1286:Decremental/Deprecated/Redundant Features
124:, especially when implementing optimized
80:Learn how and when to remove this message
1128:a branch table by another name used for
1087:'A' ==> 65 decimal, 0x41 hexadecimal)
1170:
1055:Creating the index for the branch table
490:and code efficiency (data need only be
163:values that may be easily converted to
1237:. Free Software Foundation. 2001-06-07
1060:during earlier validation of the key.
699:/* A pointer to a handler function */
462:Advantages of branch tables include:
7:
1282:"A Brief Introduction to Fortran 90"
593:; adding it to the program counter.
372:, and is conceptually similar to a
450:use branch tables for dispatching
435:functions may be referenced by an
25:
1231:"Alternate Entry Points (ENTRY)"
1011:Compiler generated branch tables
34:
1257:"FORTRAN Compilers and Loaders"
402:Use of branch tables and other
1071:) can be used in a two-step, "
1000:implements a jump table as an
1:
1235:Using and Porting GNU Fortran
120:but may also be generated by
1261:ACD: Engineering Paper No 42
1310:Example of branch table in
1255:Thomas, R.E. (1976-04-29).
1203:Jones, Nigel (1 May 1999).
265:/* start of branch table */
179:transform the data into an
60:the claims made and adding
1384:
993:Jump table example in PL/I
439:index into a branch table.
1002:array of label variables
660:
554:
480:to determine subsequent
349:from which the required
211:
1099:Other uses of technique
654:Jump table example in C
194:of the offset onto the
1363:Conditional constructs
552:assembly language is:
444:computer architectures
132:Typical implementation
1178:Page, Daniel (2009).
1073:trivial hash function
1358:Computer performance
1158:Virtual method table
1106:optimizing compilers
363:virtual method table
138:unconditional branch
94:computer programming
1211:on 12 February 2012
702:/* The functions */
393:is involved or not.
112:. It is a form of
45:possibly contains
201:(unless, in some
126:switch statements
118:assembly language
90:
89:
82:
47:original research
16:(Redirected from
1375:
1296:
1295:
1293:
1292:
1278:
1272:
1271:
1269:
1268:
1252:
1246:
1245:
1243:
1242:
1227:
1221:
1220:
1218:
1216:
1207:. Archived from
1200:
1194:
1193:
1175:
1152:Switch statement
1135:Function pointer
988:
985:
982:
979:
976:
973:
970:
967:
964:
961:
958:
955:
952:
949:
946:
943:
940:
937:
934:
931:
928:
925:
922:
919:
916:
913:
910:
907:
904:
901:
898:
895:
892:
889:
886:
883:
880:
877:
874:
871:
868:
865:
862:
859:
856:
853:
850:
847:
844:
841:
838:
835:
832:
829:
826:
823:
820:
817:
814:
811:
808:
805:
802:
799:
796:
793:
790:
787:
784:
781:
778:
775:
772:
769:
766:
763:
760:
757:
754:
751:
748:
745:
742:
739:
736:
733:
730:
727:
724:
721:
718:
715:
712:
709:
706:
703:
700:
697:
694:
691:
688:
685:
682:
679:
676:
673:
672:<stdlib.h>
670:
667:
664:
645:
642:
639:
636:
633:
630:
627:
624:
621:
618:
615:
612:
609:
606:
603:
600:
597:
594:
591:
588:
585:
582:
579:
576:
573:
570:
567:
564:
561:
558:
496:data compression
472:
425:operating system
332:
329:
326:
323:
320:
317:
314:
311:
308:
305:
302:
299:
296:
293:
290:
287:
284:
281:
278:
275:
272:
269:
266:
263:
260:
257:
254:
251:
248:
245:
242:
239:
236:
233:
230:
227:
224:
221:
218:
215:
203:instruction sets
85:
78:
74:
71:
65:
62:inline citations
38:
37:
30:
21:
1383:
1382:
1378:
1377:
1376:
1374:
1373:
1372:
1348:
1347:
1305:
1300:
1299:
1290:
1288:
1280:
1279:
1275:
1266:
1264:
1254:
1253:
1249:
1240:
1238:
1229:
1228:
1224:
1214:
1212:
1202:
1201:
1197:
1190:
1177:
1176:
1172:
1167:
1141:Indirect branch
1122:
1101:
1057:
1045:
1013:
1008:
995:
990:
989:
986:
983:
980:
977:
974:
971:
968:
965:
962:
959:
956:
953:
950:
947:
944:
941:
938:
935:
932:
929:
926:
923:
920:
917:
914:
911:
908:
905:
902:
899:
896:
893:
890:
887:
884:
881:
878:
875:
872:
869:
866:
863:
860:
857:
854:
851:
848:
845:
842:
839:
836:
833:
830:
827:
824:
821:
818:
815:
812:
809:
806:
803:
800:
797:
794:
791:
788:
785:
782:
779:
776:
773:
770:
767:
764:
761:
758:
755:
752:
749:
746:
743:
740:
737:
734:
731:
728:
725:
722:
719:
716:
713:
710:
707:
704:
701:
698:
695:
692:
689:
686:
683:
680:
677:
674:
671:
668:
666:<stdio.h>
665:
662:
656:
647:
646:
643:
640:
637:
634:
631:
628:
625:
622:
619:
616:
613:
610:
607:
604:
601:
598:
595:
592:
589:
586:
583:
580:
577:
574:
571:
568:
565:
562:
559:
556:
546:
532:Extra level of
529:
470:
460:
410:was expensive,
400:
355:transfer vector
339:
334:
333:
330:
327:
324:
321:
318:
315:
312:
309:
306:
303:
300:
297:
294:
291:
288:
285:
282:
279:
276:
273:
270:
267:
264:
261:
258:
255:
252:
249:
246:
243:
240:
237:
234:
231:
228:
225:
222:
219:
216:
213:
196:program counter
134:
114:multiway branch
86:
75:
69:
66:
51:
39:
35:
28:
23:
22:
15:
12:
11:
5:
1381:
1379:
1371:
1370:
1365:
1360:
1350:
1349:
1346:
1345:
1340:
1335:
1330:
1318:
1304:
1303:External links
1301:
1298:
1297:
1273:
1247:
1222:
1195:
1188:
1169:
1168:
1166:
1163:
1162:
1161:
1155:
1149:
1143:
1138:
1132:
1126:Dispatch table
1121:
1118:
1114:loop unrolling
1100:
1097:
1092:
1091:
1088:
1056:
1053:
1044:
1041:
1037:
1036:
1033:
1012:
1009:
1006:
994:
991:
661:
655:
652:
555:
545:
542:
541:
540:
537:
528:
525:
521:
520:
501:
500:
485:
474:
467:
459:
456:
455:
454:
440:
422:
399:
396:
395:
394:
387:
384:
359:dispatch table
338:
335:
212:
207:
206:
188:
177:
133:
130:
88:
87:
42:
40:
33:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
1380:
1369:
1366:
1364:
1361:
1359:
1356:
1355:
1353:
1343:
1341:
1338:
1336:
1333:
1331:
1329:
1325:
1321:
1319:
1317:
1313:
1309:
1307:
1306:
1302:
1287:
1283:
1277:
1274:
1262:
1258:
1251:
1248:
1236:
1232:
1226:
1223:
1210:
1206:
1199:
1196:
1191:
1189:9781848822559
1185:
1181:
1174:
1171:
1164:
1159:
1156:
1153:
1150:
1147:
1144:
1142:
1139:
1136:
1133:
1131:
1127:
1124:
1123:
1119:
1117:
1115:
1112:compilers in
1111:
1107:
1098:
1096:
1089:
1086:
1082:
1078:
1077:
1076:
1074:
1070:
1066:
1061:
1054:
1052:
1050:
1049:computed GoTo
1043:Computed GoTo
1042:
1040:
1034:
1031:
1030:
1029:
1025:
1023:
1019:
1010:
1005:
1003:
999:
992:
659:
653:
651:
553:
551:
550:Microchip PIC
543:
538:
535:
531:
530:
527:Disadvantages
526:
524:
518:
514:
513:
512:
510:
506:
497:
493:
489:
486:
483:
479:
475:
468:
465:
464:
463:
457:
453:
449:
445:
441:
438:
434:
430:
426:
423:
420:
417:
416:
415:
413:
409:
405:
397:
392:
388:
385:
382:
381:
380:
377:
375:
374:control table
371:
370:threaded code
366:
364:
360:
356:
352:
348:
344:
336:
210:
204:
200:
197:
193:
189:
186:
182:
178:
174:
170:
169:
168:
166:
162:
158:
155:
151:
147:
143:
139:
131:
129:
127:
123:
119:
115:
111:
107:
103:
99:
95:
84:
81:
73:
70:November 2016
63:
59:
55:
49:
48:
43:This article
41:
32:
31:
19:
1368:Control flow
1289:. Retrieved
1285:
1276:
1265:. Retrieved
1260:
1250:
1239:. Retrieved
1234:
1225:
1213:. Retrieved
1209:the original
1198:
1179:
1173:
1146:Lookup table
1130:late binding
1102:
1093:
1079:Convert the
1062:
1058:
1046:
1038:
1026:
1014:
1001:
996:
657:
648:
547:
522:
502:
482:program flow
461:
429:system calls
401:
391:late binding
378:
367:
354:
340:
208:
157:instructions
154:machine code
135:
110:instructions
101:
98:branch table
97:
91:
76:
67:
44:
1018:binary chop
629:index_three
534:indirection
517:entry point
488:Algorithmic
473:statements)
421:programming
171:optionally
146:multiplying
144:created by
1352:Categories
1291:2009-04-10
1267:2009-04-10
1241:2016-11-25
1165:References
1065:hash table
972:jump_table
864:jump_table
632:index_zero
617:; of code.
605:index_zero
458:Advantages
452:interrupts
351:function's
173:validating
165:sequential
150:sequential
102:jump table
54:improve it
18:Jump table
1316:IBM S/360
1312:Wikibooks
641:index_one
623:index_two
614:index_one
478:call site
122:compilers
106:branching
58:verifying
1120:See also
1081:raw data
1069:raw data
669:#include
663:#include
446:such as
419:embedded
404:raw data
389:whether
347:pointers
217:validate
199:register
192:addition
185:shifting
176:omitted.
161:raw data
1215:12 July
861:Handler
846:"0
807:"1
768:"2
729:"3
687:Handler
675:typedef
544:Example
509:integer
505:library
492:encoded
448:IBM/360
437:integer
433:library
398:History
325:codebad
301:codetwo
289:codeone
277:codebad
52:Please
1186:
1022:memory
978:return
852:"
840:printf
813:"
801:printf
774:"
762:printf
735:"
723:printf
638:return
408:memory
361:" or "
319:branch
181:offset
142:offset
1263:. ACD
1085:ASCII
942:value
933:value
891:func3
885:func2
879:func1
873:func0
825:func0
786:func1
747:func2
708:func3
596:table
572:addwf
560:INDEX
442:some
343:array
322:table
1314:for
1217:2008
1184:ISBN
998:PL/I
954:argv
948:atoi
921:argv
915:char
909:argc
900:main
831:void
822:void
792:void
783:void
753:void
744:void
714:void
705:void
693:void
678:void
626:goto
620:goto
611:goto
602:goto
557:movf
503:For
431:and
412:CPUs
313:rest
298:goto
286:goto
274:goto
268:next
250:next
247:goto
96:, a
1328:C++
1110:JIT
1108:or
975:();
930:int
906:int
897:int
644:...
575:PCL
345:of
310:...
214:...
100:or
92:In
56:by
1354::
1284:.
1259:.
1233:.
1116:.
1063:A
918:**
894:};
855:);
849:\n
816:);
810:\n
777:);
771:\n
738:);
732:\n
696:);
690:)(
511::
471:If
376:.
316:of
148:a
1326:/
1324:C
1294:.
1270:.
1244:.
1219:.
1192:.
987:}
984:;
981:0
966:;
963:4
960:%
957:)
951:(
945:=
936:;
927:{
924:)
912:,
903:(
888:,
882:,
876:,
870:{
867:=
858:}
843:(
837:{
834:)
828:(
819:}
804:(
798:{
795:)
789:(
780:}
765:(
759:{
756:)
750:(
741:}
726:(
720:{
717:)
711:(
684:*
681:(
581:F
578:,
566:W
563:,
484:)
328::
304:;
292:;
280:;
271::
259:;
256:y
253:+
241:;
238:4
235:*
232:x
229:=
226:y
220:x
83:)
77:(
72:)
68:(
50:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.