Pointer Tables and Jump Tables By Example

[ryanfaescotland]

So I've just finished reading through the (currently) 8 pages of topics here in the Megadrive/Genesis subforum and something that comes up time and time again without explanation is the concept of pointer tables and jump tables. So I thought I’d make this topic to hopefully explain what they are and give a few real world examples.

Here is the issue: I don’t really know what they are! So I’m going to put my understanding of them here but am relying on someone to verify or correct my explanation. I’ll update this post with any corrections and improvements made.

Pointer Tables

This forum post on Zoprha’s Domain looks to be the best explanation of pointer tables I’ve found: http://www.zophar.net/forums/showthread ... nter+table but they are also explained on this NesDev article: http://wiki.nesdev.com/w/index.php/Pointer_table and I’m fairly certain http://www.romhacking.net has some docs on the matter as well although my search proved fruitless (well one article by KingMike on converting SNES 2 byte pointers to 3 byte pointers).

The majority of reading I’ve done explains them in terms of game text and they are used where variable length data is used (such as in game dialog where each sentence is of different length or graphics data that isn’t all a set size).
Imagine, to make things easier for your developers, you keep all your text together in your ROM (ignore actual lengths in this example):

Code: Select all

00600000: “Princess is in another castle#”
00600013: “All your base#”
00600020: “C-c-c-combo breaker#”
00600025: “SNAKE!!!#”

Since there is no fixed length in the text you can't just load in address $00600000 and jump forward $10 for the 2nd phrase, $20 for the 3rd phrase and so on. To allow you to do this create a pointer table that contains all these addresses which is stored elsewhere:

Code: Select all

00300000: $00600000
00300004: $00600013
00300008: $00600020
0030000C: $00600025

Now if you want to refer to your 3rd items of text you can because the pointer table data is fixed with. Just refer to the pointer table’s start address, plus the offset:

Code: Select all

Move.l	#$00300000, A0
Move.l	$08(A0), A1
Move.l	(A1), D0
Do something with D0

Note also I've ended each of the text strings with a #. This is fairly typical since the processor doesn't know where one string ends and the next begins so to let it know you'd have your text loading routine (or graphics) loop round loading in the data at that address until it finds the chosen symbol (doesn't have to be a #).
Jump Tables

When I think of a jump table I just think of a section of code that has multiple jump statements together like this section from Toejam and Earl:

Code: Select all

00001286 48E7 3038                MOVEM.L   D2-D3/A2-A4,-(A7)
0000128A 247C 00026F76            MOVE.L    #$00026F76,A2
00001290 267C 00FF8000            MOVE.L    #$00FF8000,A3
00001296 287C 00026FDA            MOVE.L    #$00026FDA,A4
0000129C 16BC 0060                MOVE.B    #$60,(A3)
000012A0 4EBA F2AA                JSR       $0000054C(pc) (Clear Ram Routine 1)
000012A4 4878 0001                PEA       $0001 
000012A8 42A7                     CLR.L     -(A7)
000012AA 4879 00FF800E            PEA       $00FF800E
000012B0 4EB9 00025900            JSR       $00025900 (VDP Writes Routine 1)
000012B6 4EB9 0003E384            JSR       $0003E384 (RAM Writes Routine 1)
000012BC 4EBA FF1A                JSR       $000011D8(pc) (I/O Routine 1)
000012C0 4EB9 0003F50A            JSR       $0003F50A (I/O Routine 2)
000012C6 4EB9 0003ECFE            JSR       $0003ECFE (Massive Routine 1)

However I no longer think this is the case. In the above example all the jumps are executed in order, going by this StackOverflow article http://stackoverflow.com/questions/6538 ... ump-tables jump tables are actually more like a switch statement. Wikipedia has a pretty good entry on the matter as well where it refers to the process as branch tables: https://en.wikipedia.org/wiki/Branch_table

Does anyone have a real world 68K example of either of these or better explanation? Is my thinking right or terribly, terribly wrong?

[ehaliewicz]

The reason your example is equivalent to a switch statement is because the code in the table uses JSR, so the routines will always return to the next entry in the table.

A simple example of a jump table would be something like this. Sorry it's not a real world example, but the code works.

Code: Select all

	 
    ;; dispatched value is in d0
    ;; 0 == first routine, 1 == second routine, etc
    lsl.l #2, d0 ;; scale to match the size of the table's elements
    move.l d0, a0
    move.l table_1(a0), a0
    jsr (a0)
    ;; return here from called routine
	
table_1:
    dc.l routine_0
    dc.l routine_1
    dc.l routine_2
	
    ;; alternatively, you could jump to literal code in the table
    ;; rather than load the address of the routine
    ;; this is a slower and uses more space at the same time, unless you use smaller branch instructions
    mulu.w #6, d0 ;; scale by 6, as each entry is now 6 bytes (would be 2 or 4 bytes for BRA instructions)
    move.l d0, a0
    lea table_2(a0), a0
    jsr (a0)
    ;; return here after the called routine

table_2:
    jmp routine0
    jmp routine1
    jmp routine2
	
	

[MintyTheCat]

However I no longer think this is the case. In the above example all the jumps are executed in order

You have confused JMP with JSR. The PC is saved prior to loading the address of the routine into the PC and then popped back off when done, i.e. you will see an RTS.

If you are used to high-level languages then this can be forgiven but a pointer to a table, an entry, a string or indeed a memory address that happens to be a section of code are all the same to the Processor.

My advice is to read the 68000PRM.pdf file and do some 68K coding before working on the MD. The Amiga is a good place to learn 68K FYI.
For learning 68K see if you can find some of the 68K books by Ford or Antonakos or Clememnts, e.g.:

http://www.amazon.co.uk/68000-Microproc ... +antanakos

Cheers,

Minty.

[ryanfaescotland]

You have confused JMP with JSR. The PC is saved prior to loading the address of the routine into the PC and then popped back off when done, i.e. you will see an RTS.

I don't think that I have, I've perhaps just not explained it clearly. They are executed in order but (obviously) the code they jump to is executed between them. This happens because of the RTS which puts the execution back to the next JSR instruction once the current one is complete (assuming nothing messes with the stack of course!). In a JMP this wouldn't happen. Note I'm not explaining this because I think you don't know it but because I want to show I do! Are you saying Jump tables only work with explicit JMP instructions and not derivatives like JSR?

If you are used to high-level languages then this can be forgiven but a pointer to a table, an entry, a string or indeed a memory address that happens to be a section of code are all the same to the Processor.

Could you elaborate on this? They are the same to the processor in which way, as in it is all 0's and 1 or as in a pointer is a pointer regardless of what it points to? Surely a Jump Table and a Pointer Table are different things though that just happen to have pointers in common otherwise why do they get differentiated between by people? Does it being the same to the processor mean it isn't important to the person trying to understand it? Genuinely asking.

My advice is to read the 68000PRM.pdf file and do some 68K coding before working on the MD. The Amiga is a good place to learn 68K FYI.
For learning 68K see if you can find some of the 68K books by Ford or Antonakos or Clememnts, e.g.:

http://www.amazon.co.uk/68000-Microproc ... +antanakos

Thanks for the recommendation, I've already got the following books 68000 Assembly Language: Techniques for Building Programs by Donald Krantz and James Stanley and An Introduction to 68000 Assembly Language
by R. A. Penfold and J.W. Penfold. What does this book offer that others don't?

Sadly I've no interest in the Amiga, having grown up with the Megadrive I'm much more interested in how it works and the games on it so would rather learn from it even if it is diving in at the deep end first!

ehaliewicz thanks for your reply as well, it's still a little unclear to me but I think I just need to see more and more examples and eventually it'll sink in.

[ehaliewicz]

Ok, let me try to describe a bit better what's going on

It will probably help if you have Easy68k and step through the code a line at a time.

Code: Select all

	 
example_1:
    ;; load example value into d0, could be any number with any range of entries in the jump table
    ;; different size entries will necessitate different scaling factors
    moveq.l #1, d0	      ;; d0.b == 0b00000001    
    
    ;; each entry is 4 bytes, so scale by 4 to get the correct offset
    lsl.l #2, d0           ;; d0.b == 0b00000100 == 4
    
    move.l d0, a0          ;; a0 == 4
    move.l table_1(a0), a0 ;; load the value at address (table_1+4) into a0
    jsr (a0)               ;; indirect branch to value in a0, which is the address `routine_1`
    
    ;; bsr/jsr saves the current address on the stack, so when routine_1 uses a `RTS` instruction,
    ;; control returns to this location
    
	
table_1:
    dc.l routine_0
    dc.l routine_1
    dc.l routine_2
	
	
example_2:
    moveq.l #1, d0         ;; d0.b == 0b00000001
    
    ;; each entry is 6 bytes now, so scale by 6
    mulu.w #6, d0          ;; d0.b == 0b00000110 == 6 
    
    move.l d0, a0          ;; a0 == 6
    lea table_2(a0), a0    ;; load the address table_2+6 into a0, just the address, not the value at that address (see LEA vs MOVE)
    jsr (a0)               ;; branch to the address table_2+6, which contains the literal code `jmp routine_1`
                           ;; return here after routine_1 uses a `RTS` instruction
    
table_2:
    jmp routine_0
    jmp routine_1
    jmp routine_2

[Natsumi]

if we are strictly on Motorola 68000, the example ehaliewicz gives is wholly useless, and even if you could use said instructions in practice, it still would lead to poor implementation. Instead, here is a 100% real world application of a jumptable, used by me in a program;

Code: Select all

moveq	#0,d0
		move.b	CrashID,d0			; get crash ID to d0 (note: always multiples of two)
		move.w	CrashCodeTable(pc,d0.w),d0	; get offset value to d0
		jsr	CrashCodeTable(pc,d0.w)		; then jump to appropriate code
...
CrashCodeTable:
	dc.w .addresserror-CrashCodeTable
	dc.w .nullerror-CrashCodeTable
	dc.w .nullerror-CrashCodeTable
	dc.w .nullerror-CrashCodeTable
	dc.w .nullerror-CrashCodeTable
	dc.w .nullerror-CrashCodeTable
	dc.w .nullerror-CrashCodeTable
	dc.w .nullerror-CrashCodeTable
	dc.w .nullerror-CrashCodeTable
	dc.w .nullerror-CrashCodeTable
	dc.w .nullerror-CrashCodeTable
	dc.w .nullerror-CrashCodeTable
	dc.w .nullerror-CrashCodeTable

.nullerror	rts		; nothing here

.addresserror; write instruction register. Instruction register holds the first word of the opcode in MC68000
		move.l	Crash_A7,a1			; get crash stack ptr
		lea	irErrorStr(pc),a0		; get SR string
...

Of course, you can use jumptables on plenty of occasions, from fetching data pointers, jumping to code depending on a number, or even getting data stored in an array! it is also good to note, that depending on the size of each element (byte, word, longword, even more), you need to make sure you correctly multiply your offset number to match it. In my example, the data I fetch from RAM is already in multiples of two so I dont have to worry about that.

[ryanfaescotland]

if we are strictly on Motorola 68000, the example ehaliewicz gives is wholly useless, and even if you could use said instructions in practice, it still would lead to poor implementation.

That's fighting talk!

If you are going to be such a harsh critic it would be great to know why you think it is a poor implementation. And even then, a poor implementation that is functional and can be learnt from and improved upon is still better than no example at all.

[Natsumi]

ok then, I'll tell you exactly why.
First and foremost, there is no 'bsr (a0)' in Motorola 68000. I am unsure of later models having it, but I highly doubt, just because 'jsr (a0)' already exists and is good enough way to do so.
Second, 'move.l table_1(a0), a0' is terrible way to do anything. This is because table_1 can ONLY be in 0xFFFF8000-0x00007FFF area in memory, and there is so much better alternative; 'move.l table_1(pc,d0.w),a0', which does the same as two lines in his code, but uses PC relative address (with smaller range, but the table can be located anywhere), and is probably only few cycles slower.
Third, why would you copy Dn to An anyway just to use as index register anyway? Dn has a lot more wider use, and in rare case does using An become more useful (which it can, but not on this case.).

[MintyTheCat]

My mistake, you have JSR in your extract but used the word 'jump' in the explanation. In my head that is the JMP operation which is quite different to the 'jump to subroutine' operation - Assembly tends to do that to you after a while and makes you think in fixed terms all too easily.

If you are used to high-level languages then this can be forgiven but a pointer to a table, an entry, a string or indeed a memory address that happens to be a section of code are all the same to the Processor.

Could you elaborate on this? They are the same to the processor in which way, as in it is all 0's and 1 or as in a pointer is a pointer regardless of what it points to? Surely a Jump Table and a Pointer Table are different things though that just happen to have pointers in common otherwise why do they get differentiated between by people? Does it being the same to the processor mean it isn't important to the person trying to understand it? Genuinely asking.

One and the same as a pointer is a memory address and you are calculating your jump which ultimately leads to a memory address.

I think that you are coming to this from a more high-level programming stand point. You kind of have to forget a lot of that and simply accept Assembly for what it is. If you think too high-level it will trip you up. Granted it is a large shift for some but it boils down to how much Assembly and C you have done and how low-level you have worked in C. I find Assembly and C often to be fairly close but C tends to lie where as the Assembly is always true

Thanks for the recommendation, I've already got the following books ..

That is a good step to have resources to refer to and learn from. The next is to use them.

Sadly I've no interest in the Amiga, having grown up with the Megadrive I'm much more interested in how it works and the games on it so would rather learn from it even if it is diving in at the deep end first!

Ok, if you are coming to this without any prior Assembly experience to the MD then you will simply have to take small but determined steps. See it as a set of goals to attain but you are starting out correctly by referring to existing commercial MD Game ROMs - this is perhaps one of the best ways to get answers about how to use the MD IFF you can understand the Assembly that is.

I mentioned the Amiga as it has a very good set of libraries and tools that will have you doing real 68K in no time. Easy68K is not bad but it is not at all the same as having an actual full OS and computer to play with. the main issue with the MD is that when you come to it there is practically nothing by way of libraries at first until you either write your own or find something that someone else has written.

Having said all of that as Assembly languages go 68K is not bad at all. If you are using GCC you can even try writing some code in C then seeing the resultant Assembly generated and then try to understand what it is doing. You will be seeing lots of frame usage but ignore that for now.

The other thing is that I am pleased to see that you are going the 68K route from the start; you will in the long-run gain a lot more that using C as you will have a much closer and intimate understanding of how your code affects the MD. C is all very well but still it insulates the developer a bit too much. This is not a problem on a modern PPC or ARM processor with plenty of power but for the lowly MD it has an impact

Best of luck with it.

[ryanfaescotland]

Cheers again for the replies guys, especially Natsumi for spelling out the problems. When people are crtical of my code (which obviously never happens) I always try and swallow my pride and use it as an opportunity to learn and improve, hopefully ehaliewicz will view it in the same light!

MintyTheCat, I dare say you are right about still coming to this from a high level language point of view. Something I am consciously trying to avoid but not doing too well by the sounds of it!

Will have a good look over the replies when back from work and try assimilate it all.

[ehaliewicz]

You're right about bsr (a0), my mistake, however pc-relative addressing would have taken more text to explain, and I was going for a simple example of the principle of a jump table, not an optimized or practical real-world example, as already mentioned.

Fourth. He actually branches to pointer data, rather than use the pointer data to jump to appropriate code.

False, the first example branches to the address of code in the table, the second example branches to literal code in the table. Both are variations on the same principle, but are useful for different things, and both work if you change the BSR instruction back to JSR

[Natsumi]

Looking back at it, it indeed was a misinterpretation of the logic on my end. Sorry for the confusion

[MintyTheCat]

MintyTheCat, I dare say you are right about still coming to this from a high level language point of view. Something I am consciously trying to avoid but not doing too well by the sounds of it!

I just boils down to what you are used to. When I was a kid it was all C64s, BASIC and machine-code. I got onto an Amiga when I was 12 and it was not as common to find C compilers then as they were quite expensive so many people used other things based on BASIC and many used Assembly.

There is no merit by beating yourself up as it will only limit you. I feel that we HAVE to make mistakes to learn anything - might be unpopular to think like this these days but still.

I feel that rather than calling it a Pointer-Table simply call it a Routine or Code Table and the other a Table or a Data-Table as in fact they are all simply references to addresses in memory. I personally got more from what a Pointer is having learned Assembly before C and to be honest Pointers make more sense in Assembly than C to me. I cannot count the number of times that Pointers have been misconstrued over the years and some people will even not use them at all - which is odd.