Jump Tables

[muchtolearn]

I have not found this term and would like to know what it is.
I have done a google search and wiki but find their definition
does not me any wiser.

1) Could someone give a clear definition of what is
2) And also a clear example (programming) of how it
is used.

I would like 65816 example, but if not 6502 will suffice.

[GARTHWILSON]

You can start with a routine number, for example in the range of 0 to $1F, shift it left one time to double it (or only allow even numbers 0-$3E to start with), and use that number in X as an index into a jump table, and do an absolute indexed indirect jump, JMP (Table,X) which you'll find on the 65c02 and '816 but not the old NMOS 6502. The '816 also has a JSR (addr,X). It makes it easier to get to the right routine in a situation for example where you want to increment or decrement the index in a loop, and if a condition is met, you jump to the appropriate routine. Another example would be if you want to be able to change the addresses of the target routines without having to change the routine numbers. Then the jump table would be something like:

Code: Select all

Table:  DWL  <Routine00>,  <Routine01>,  <Routine02>,  <Routine03>
        DWL  <Routine04>,  <Routine05>,  <Routine06>,  <Routine07>
                               . . .                                 ; (cut some out to shorten the example)
        DWL  <Routine1C>,  <Routine1D>,  <Routine1E>,  <Routine1F>

(DWL in the C32 assembler I use is "Define Word, Low byte first".) In each case, replace "<RoutineXX>" with the actual name of the routine.

[BigDumbDinosaur]

GARTHWILSON wrote:

Code: Select all

Table:  DWL  <Routine00>,  <Routine01>,  <Routine02>,  <Routine03>
        DWL  <Routine04>,  <Routine05>,  <Routine06>,  <Routine07>
                               . . .                                 ; (cut some out to shorten the example)
        DWL  <Routine1C>,  <Routine1D>,  <Routine1E>,  <Routine1F>

(DWL in the C32 assembler I use is "Define Word, Low byte first".) In each case, replace "<RoutineXX>" with the actual name of the routine.

In MOS Technology-compliant assemblers, the .WORD directive would be used.

[GARTHWILSON]

BigDumbDinosaur wrote:

In MOS Technology-compliant assemblers, the .WORD directive would be used.

Thanks. Reviewing the last project I did with the 2500AD assembler (in 1993), I see it uses WORD also (with no dot). I had a jump table in that for keys pressed. Some functions used pairs of simultaneously pressed keys, so their respective bits went into the formation of the index. There were also two different control panel orientations, and changing only required accessing the other table, according to a single bit in the user configuration in the EEPROM. C32 and 2500AD are both professional-grade macro assemblers. I think the 2500AD one cost my employer $375 in the late 1980's, and C32 cost me $99 in 1994, and it's still being sold for that price.

[BigDumbDinosaur]

muchtolearn wrote:

I have not found this term and would like to know what it is.
I have done a google search and wiki but find their definition
does not me any wiser.

1) Could someone give a clear definition of what is
2) And also a clear example (programming) of how it
is used.

I would like 65816 example, but if not 6502 will suffice.

A jump table is a list of addresses of routines in a program. Use of a jump table in assembly language is very much like the ON GOTO verb in BASIC. Generating a jump table in 6502 assembly language is the same whether using the 65C02 pr the 65C816. Here's an example of a jump table from the firmware in my POC V1 65C816 computer:

Code: Select all

;	S-record processing jump table...
;
lsrextab .word monlsrs0        ;S0
         .word monlsrs1        ;S1
         .word monlsrut        ;S2 (not implemented)
         .word monlsrut        ;S3 (not implemented)
         .word monlsrut        ;S4 (not implemented)
         .word monlsrs5        ;S5
         .word monlsrut        ;S6 (undefined)
         .word monlsrut        ;S7 (not implemented)
         .word monlsrut        ;S8 (not implemented)
         .word monlsrs9        ;S9

Each label after the .WORD directive is a function involved with processing Motorola S-records. As the assembler parses this table it will generate a series of addresses in little-endian format. The code to select and execute a particular function would be as follows:

Code: Select all

         lda rectype           ;record type
         asl A                 ;generate index
         tax
         jmp (lsrextab,x)      ;process record type

In the above, the record type is 0, 1, 2 3, etc. The ASL A instruction is an arithmetic left shift that has the effect of doubling the value in the accumulator, necessary since the table entries are 16 bit values. The JMP (<addr>,X) instruction is implemented in the 65C02 and 65C816, but not the NMOS processors.

Speaking of the 65C816, the equivalent to BASIC's ON GOSUB verb is easily implemented:

Code: Select all

         lda rectype           ;record type
         asl A                 ;generate index
         tax
         jsr (lsrextab,x)      ;process record type

If the S-record processing functions were subroutines, that is how they would be called by index. JSR (<addr>,X) is unique to the 65C816.

Hope this helps you.

[Aslak3]

What about literal jump tables? I've seen this used as well:

Code: Select all

routine1:     jmp myroutine1
routine2:     jmp myroutine2

User code then does:

Code: Select all

              jsr routine1
              ....

This mechanism is nice because you can jsr to a label (the address of which does not change) which takes you to a build-specific routine address. Less CPU overhead then a table of vectors, but of course you have the extra byte per routine for the jmp opcode.

[GARTHWILSON]

The '816 does also have JSR (addr,X). (There's no JSR (addr) though, so you'd have to precede it with LDX #0 if that's what you want.)

[Aslak3]

FWIW wikipedia covers both branch/jump and vector/address tables and describes them both in nice abstract terms:

https://en.wikipedia.org/wiki/Branch_table

From the OP the question is clearly about branch tables, not vector tables. Hence me trying to explain that concept in addition to vector tables, which have been nicely described here.

[whartung]

Aslak3 wrote:

What about literal jump tables? I've seen this used as well:

Code: Select all

routine1:     jmp myroutine1
routine2:     jmp myroutine2

User code then does:

Code: Select all

              jsr routine1
              ....

This mechanism is nice because you can jsr to a label (the address of which does not change) which takes you to a build-specific routine address. Less CPU overhead then a table of vectors, but of course you have the extra byte per routine for the jmp opcode.

Yea, but, frankly, this is fundamentally different.

I'd consider this more of a vectored JSR than a jump table. This is typically seen in things like operating systems and what not where they defined public, known entry points, but at those spots are just JMPs to the real code. This allows the underlying code to change and move while the published entry points remain stable for 3rd party code.

The Jump Table, as mentioned here, and portrayed above, tends to be more similar to the the BASIC ON GOTO statement.

Code: Select all

10 PRINT "1. Create Thing"
20 PRINT "2. Edit Thing"
30 PRINT "3. Delete Thing"
40 PRINT "4. Quit"
50 INPUT "Enter command #", I
60 ON I GOTO 100, 200, 300, 400
100 REM Do create
  ...
200 REM Do edit
  ...
300 REM Do delete
  ...
400 REM Do quit

The '816 addressing modes make Jump Tables much easier and idiomatic in the '816 than the '02.

[muchtolearn]

I need to to be simplistic in order to understand the concet.
So far I have got this.

A jump table is a list of addresses of routines in a program. Use of a jump table in assembly language is very much like the ON GOTO verb in BASIC.

Now I refer to this code:
It is from Prince of Persia

org org
12

13 jmp boot3
14 jmp cls
15 jmp lay
16 jmp fastlay
17 jmp layrsave
18

19 jmp lrcls
20 jmp fastmask
21 jmp fastblack
22 jmp peel
23 jmp getwidth
24

25 jmp copyscrnMM
26 jmp copyscrnAA
27 jmp SETFASTAUX
28 jmp SETFASTMAIN
29 jmp copyscrnMA
30

31 jmp copyscrnAM
32 jmp INVERTY
33

According to the website, this is a jump table right?
My understanding is why would you do it this way instead of writing out the routine in full?
(Unless you referring to it on a number of times)

And also if it were in source code (machine language) would that be different entirely?
(Do you include all the JMPs or just the address (routine)?

[GARTHWILSON]

Normally a jump table would not have the JMP instructions, only the addresses.

Put

Code: Select all

 and 

around your code to keep the forum software from removing your extra spaces. It will also make the code monospaced, as it should be. (They didn't do anything here because I checked the "Disable BBCode" box. Make sure you don't have it checked.)

[muchtolearn]

So how do you recognise Jump Tables looking through code?

[GARTHWILSON]

muchtolearn wrote:

So how do you recognise Jump Tables looking through code?

If it's source code, it will look something like our examples above. If it's assembled code, you're out of luck. That's one reason disassemblers do so poorly. Tables, data mixed in with program material, etc. get them all confusilated.

[BigEd]

While most of the time the things we speak of as jump tables are just tables of addresses, we should be generous in our use of language, and allow also these lists of JMP instructions to be called jump tables. Similarly, if there were a pair of tables, one comprising the high and the other the low bytes, that would be about the same thing conceptually, although of course it would be accessed differently. It's also common enough to jump by pushing an address and then using RTS, in which case the addresses are off by one. Conceptually, all the same thing.

A good reason for having a jump table is late binding: you can assemble a piece of code which can jump to a given function even if the code for that function is not yet assembled and the lengths of surrounding pieces of code is not yet known. You have a fixed point as a rendezvous. Your development can be more flexible. In fact the jump table could be fixed up even after the calling code is loaded, when the called code is loaded.

[BigEd]

Speaking of Prince of Persia, this thread might be of interest:
http://stardot.org.uk/forums/viewtopic.php?f=53&t=13079
It's a port of PoP to the Beeb, a work in progress.