Jump table: Difference between revisions

From NESdev Wiki
Jump to navigationJump to search
m (→‎Indirect jumping: linked to Wikipedia:reentrant)
No edit summary
Line 1: Line 1:
A jump table is a table of code addresses, meant to be indexed by a selector value. For example, a game script might specify an action to be performed via an index, which is then used to select a routine from a jump table of available scripting actions. The alternative to a jump table is a long string of comparisons with each possible selector value. This approach is tedious to set up and maintain, and slow:
A jump table is a table of code addresses, meant to be indexed by a selector value. For example, a game script might specify an action to be performed via an index, which is then used to select a routine from a jump table of available scripting actions. The alternative to a jump table is a long string of comparisons with each possible selector value. This approach is tedious to set up and maintain, and slow:


; Jumps to routine selected by A
<source lang="6502tasm">
do_action:
; Jumps to routine selected by A
        cmp #0
do_action:
        bne not0
      cmp #0
        jmp action0
      bne not0
not0:  cmp #1
      jmp action0
        bne not1
not0:  cmp #1
        jmp action1
      bne not1
not1:  cmp #2
      jmp action1
        bne not2
not1:  cmp #2
        jmp action2
      bne not2
not2:  ...
      jmp action2
not2:  ...
</source>


== Indirect jumping ==
== Indirect jumping ==
The NES doesn't have a JMP (addr,X) instruction, as other members of the 65xx family do. If it had one, a jump table would be trivial to implement, as in the following 65C02/Hu6280/65C816 code:
The NES doesn't have a JMP (addr,X) instruction, as other members of the 65xx family do. If it had one, a jump table would be trivial to implement, as in the following 65C02/Hu6280/65C816 code:


; Jumps to routine selected by A, from 0 to 127. High bit of A is ignored.
<source lang="6502tasm">
do_action:
; Jumps to routine selected by A, from 0 to 127. High bit of A is ignored.
        asl a          ; A = A * 2
do_action:
        tax
      asl a          ; A = A * 2
        jmp (table,x)
      tax
      jmp (table,x)
table:
 
        .word action0, action1, action2 ; ...
table:
      .word action0, action1, action2 ; ...
</source>


The NES does support a JMP (addr) instruction, so a jump table can be implemented by copying the address to a temporary variable, then jumping through it:
The NES does support a JMP (addr) instruction, so a jump table can be implemented by copying the address to a temporary variable, then jumping through it:


; Jumps to routine selected by A, from 0 to 127. High bit of A is ignored.
<source lang="6502tasm">
do_action:
; Jumps to routine selected by A, from 0 to 127. High bit of A is ignored.
        asl a
do_action:
        tax
      asl a
        lda table,x
      tax
        sta temp
      lda table,x
        lda table+1,x
      sta temp
        sta temp+1
      lda table+1,x
        jmp (temp)
      sta temp+1
      jmp (temp)
</source>


To call a routine via a selector, load the selector into A, then JSR do_action. This will then JMP to the appropriate routine, which will eventually RTS back to the routine that did JSR do_action. Essentially, you have JSR do_action, which then does JMP routine, which then does RTS; the JMP in the middle has no effect on the call stack. Note that the above code cannot be used without a JSR to it, since without that it's just a glorified JMP. That is, do_action must never be inlined in the code that uses it; it must always be called with JSR like a normal routine.
To call a routine via a selector, load the selector into A, then JSR do_action. This will then JMP to the appropriate routine, which will eventually RTS back to the routine that did JSR do_action. Essentially, you have JSR do_action, which then does JMP routine, which then does RTS; the JMP in the middle has no effect on the call stack. Note that the above code cannot be used without a JSR to it, since without that it's just a glorified JMP. That is, do_action must never be inlined in the code that uses it; it must always be called with JSR like a normal routine.
Line 48: Line 54:
Even though RTI is meant for returning from an interrupt, it happens to be simpler to use for this technique, since it doesn't adjust the address it pulls from the stack:
Even though RTI is meant for returning from an interrupt, it happens to be simpler to use for this technique, since it doesn't adjust the address it pulls from the stack:


do_action:
<source lang="6502tasm">
        asl a
do_action:
        tax
      asl a
        lda table+1,x ; high byte first
      tax
        pha
      lda table+1,x ; high byte first
        lda table,x
      pha
        pha
      lda table,x
        php
      pha
        rti
      php
      rti
</source>


RTS is more tricky, because it adds one to the address it pulls from the stack. This requires that every entry in the jump table have one subtracted from it. This could be done by the code, but it's tedious because the low byte must be decremented first, while the high byte needs to be pushed first. Thus, it's preferable to simply subtract one from each entry in the assembly source text:
RTS is more tricky, because it adds one to the address it pulls from the stack. This requires that every entry in the jump table have one subtracted from it. This could be done by the code, but it's tedious because the low byte must be decremented first, while the high byte needs to be pushed first. Thus, it's preferable to simply subtract one from each entry in the assembly source text:


do_action:
<source lang="6502tasm">
        asl a
do_action:
        tax
      asl a
        lda table+1,x
      tax
        pha
      lda table+1,x
        lda table,x
      pha
        pha
      lda table,x
        rts
      pha
      rts
table:
 
        .word action0-1, action1-1, action2-1 ; ...
table:
      .word action0-1, action1-1, action2-1 ; ...
</source>


The only benefit of the RTS version is that it's three clock cycles faster than the RTI version, due to not having to push the flags. Unless speed is critical, the RTI version is preferable because it doesn't require adjusting every entry in the table. Forgetting a -1 could result in hard-to-find bugs in the RTS version.
The only benefit of the RTS version is that it's three clock cycles faster than the RTI version, due to not having to push the flags. Unless speed is critical, the RTI version is preferable because it doesn't require adjusting every entry in the table. Forgetting a -1 could result in hard-to-find bugs in the RTS version.

Revision as of 09:25, 24 August 2013

A jump table is a table of code addresses, meant to be indexed by a selector value. For example, a game script might specify an action to be performed via an index, which is then used to select a routine from a jump table of available scripting actions. The alternative to a jump table is a long string of comparisons with each possible selector value. This approach is tedious to set up and maintain, and slow:

<source lang="6502tasm">

Jumps to routine selected by A

do_action:

      cmp #0
      bne not0
      jmp action0

not0: cmp #1

      bne not1
      jmp action1

not1: cmp #2

      bne not2
      jmp action2

not2: ... </source>

Indirect jumping

The NES doesn't have a JMP (addr,X) instruction, as other members of the 65xx family do. If it had one, a jump table would be trivial to implement, as in the following 65C02/Hu6280/65C816 code:

<source lang="6502tasm">

Jumps to routine selected by A, from 0 to 127. High bit of A is ignored.

do_action:

      asl a           ; A = A * 2
      tax
      jmp (table,x)

table:

      .word action0, action1, action2 ; ...

</source>

The NES does support a JMP (addr) instruction, so a jump table can be implemented by copying the address to a temporary variable, then jumping through it:

<source lang="6502tasm">

Jumps to routine selected by A, from 0 to 127. High bit of A is ignored.

do_action:

      asl a
      tax
      lda table,x
      sta temp
      lda table+1,x
      sta temp+1
      jmp (temp)

</source>

To call a routine via a selector, load the selector into A, then JSR do_action. This will then JMP to the appropriate routine, which will eventually RTS back to the routine that did JSR do_action. Essentially, you have JSR do_action, which then does JMP routine, which then does RTS; the JMP in the middle has no effect on the call stack. Note that the above code cannot be used without a JSR to it, since without that it's just a glorified JMP. That is, do_action must never be inlined in the code that uses it; it must always be called with JSR like a normal routine.

This routine has a significant limitation: if it's used by the game code and from an interrupt, perhaps the music driver, it can fail. The use of temp, a global variable, prevents the routine from being reentrant. If the game code were in the middle of a call to do_action, and had already written temp, but then an interrupt occurs and its code then calls do_action, it will overwrite the value in temp. Then, after the interrupt handler returns and resumes the interrupted code, temp won't have the value expected by the original call to do_action. To overcome this, the stack must be used.

Stack-based dispatch

Main article: RTS Trick

RTI and RTS allow use of the stack for holding the temporary address. These are normally used to return to some calling/interrupted code, but at their core they pull an address from the stack then jump to it. This is the behavior we need. We push the address on the stack, then execute RTI or RTS to jump to it. It's roundabout, but it solves the interrupt problem.

Even though RTI is meant for returning from an interrupt, it happens to be simpler to use for this technique, since it doesn't adjust the address it pulls from the stack:

<source lang="6502tasm"> do_action:

      asl a
      tax
      lda table+1,x ; high byte first
      pha
      lda table,x
      pha
      php
      rti

</source>

RTS is more tricky, because it adds one to the address it pulls from the stack. This requires that every entry in the jump table have one subtracted from it. This could be done by the code, but it's tedious because the low byte must be decremented first, while the high byte needs to be pushed first. Thus, it's preferable to simply subtract one from each entry in the assembly source text:

<source lang="6502tasm"> do_action:

      asl a
      tax
      lda table+1,x
      pha
      lda table,x
      pha
      rts

table:

      .word action0-1, action1-1, action2-1 ; ...

</source>

The only benefit of the RTS version is that it's three clock cycles faster than the RTI version, due to not having to push the flags. Unless speed is critical, the RTI version is preferable because it doesn't require adjusting every entry in the table. Forgetting a -1 could result in hard-to-find bugs in the RTS version.