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