6502.org • View topic

View unanswered posts | View active topics

Board index » 6502.org Users Forum » Programming

All times are UTC

Jump Tables

Page 1 of 1

[ 15 posts ]

Previous topic | Next topic

Author

Message

muchtolearn

Post subject: Jump Tables

Posted: Tue Sep 05, 2017 2:01 am

Joined: Tue May 03, 2016 6:54 am
Posts: 14

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.

Top

GARTHWILSON

Post subject: Re: Jump Tables

Posted: Tue Sep 05, 2017 4:07 am

Joined: Fri Aug 30, 2002 1:09 am
Posts: 8544
Location: Southern California

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:

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.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

Top

BigDumbDinosaur

Post subject: Re: Jump Tables

Posted: Tue Sep 05, 2017 4:19 am

Joined: Thu May 28, 2009 9:46 pm
Posts: 8507
Location: Midwestern USA

GARTHWILSON wrote:

Code:

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.

_________________
x86? We ain't got no x86. We don't NEED no stinking x86!

Top

GARTHWILSON

Post subject: Re: Jump Tables

Posted: Tue Sep 05, 2017 4:28 am

Joined: Fri Aug 30, 2002 1:09 am
Posts: 8544
Location: Southern California

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.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

Top

BigDumbDinosaur

Post subject: Re: Jump Tables

Posted: Tue Sep 05, 2017 4:37 am

Joined: Thu May 28, 2009 9:46 pm
Posts: 8507
Location: Midwestern USA

muchtolearn wrote:

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:

;   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:

         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:

         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.

_________________
x86? We ain't got no x86. We don't NEED no stinking x86!

Last edited by BigDumbDinosaur on Mon May 30, 2022 8:15 am, edited 1 time in total.

Top

Aslak3

Post subject: Re: Jump Tables

Posted: Tue Sep 05, 2017 3:08 pm

Joined: Mon Aug 05, 2013 10:43 pm
Posts: 258
Location: Southampton, UK

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

Code:

routine1:     jmp myroutine1
routine2:     jmp myroutine2

User code then does:

Code:

              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.

_________________
8 bit fun and games: https://www.aslak.net/

Top

GARTHWILSON

Post subject: Re: Jump Tables

Posted: Tue Sep 05, 2017 7:19 pm

Joined: Fri Aug 30, 2002 1:09 am
Posts: 8544
Location: Southern California

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.)

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

Top

Aslak3

Post subject: Re: Jump Tables

Posted: Tue Sep 05, 2017 7:32 pm

Joined: Mon Aug 05, 2013 10:43 pm
Posts: 258
Location: Southampton, UK

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.

_________________
8 bit fun and games: https://www.aslak.net/

Top

whartung

Post subject: Re: Jump Tables

Posted: Wed Sep 06, 2017 12:09 am

Joined: Sat Dec 13, 2003 3:37 pm
Posts: 1004

Aslak3 wrote:

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

Code:

routine1:     jmp myroutine1
routine2:     jmp myroutine2

User code then does:

Code:

              jsr routine1
              ....

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:

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

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

Top

muchtolearn

Post subject: Re: Jump Tables

Posted: Wed Sep 06, 2017 1:59 am

Joined: Tue May 03, 2016 6:54 am
Posts: 14

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)?

Top

GARTHWILSON

Post subject: Re: Jump Tables

Posted: Wed Sep 06, 2017 2:49 am

Joined: Fri Aug 30, 2002 1:09 am
Posts: 8544
Location: Southern California

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

Put [code] and [/code] 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.)

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

Top

muchtolearn

Post subject: Re: Jump Tables

Posted: Wed Sep 06, 2017 3:15 am

Joined: Tue May 03, 2016 6:54 am
Posts: 14

So how do you recognise Jump Tables looking through code?

Top

GARTHWILSON

Post subject: Re: Jump Tables

Posted: Wed Sep 06, 2017 4:58 am

Joined: Fri Aug 30, 2002 1:09 am
Posts: 8544
Location: Southern California

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. :lol:

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

Top

BigEd

Post subject: Re: Jump Tables

Posted: Wed Sep 06, 2017 1:11 pm

Joined: Thu Dec 11, 2008 1:28 pm
Posts: 10986
Location: England

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.

Top

BigEd

Post subject: Re: Jump Tables

Posted: Wed Sep 06, 2017 2:54 pm

Joined: Thu Dec 11, 2008 1:28 pm
Posts: 10986
Location: England

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.

Top

Page 1 of 1

[ 15 posts ]

Board index » 6502.org Users Forum » Programming

All times are UTC

Who is online

Users browsing this forum: No registered users and 29 guests

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum