Implement a Jump Table on the 6502
I’ve been working on a game project for the Nintendo Entertainment System (NES) in 6502 assembly, and I’ve had situations where I need to jump to a specific function depending on a variable’s specific value. For example, the game engine has several logic functions, one for each state in my game’s finite state machine, and I want the appropriate logic function called during the appropriate game state.
I could have written this as a long series of CMP
instructions which
check for the various state values and then jump off to the right
logic functions. But this has several negative effects: It’s a long
morass of code which is hard to understand, debug, and, ultimately,
change.
Instead, I implemented a jump table. I create a table of memory locations with entries pointing to each of the logic functions. My main engine logic function takes the game state variable and determines the table index of the appropriate function. It then jumps to that function. Spoiler alert: Hence the name, “jump table.”
We can implement this using instructions from the original 6502 instruction set; it doesn’t rely on any of the 65C02’s added instructions. And more importantly for me, it works on the stripped-down variant of the 6502 used in the NES.
Let’s look at an example using 6502 assembly code. I’ll use asm6-style
syntax—I’m using a fork of this assembler for my game project. In this
example, we’ll have a gamestate
variable which will call one of three
functions (SetZero
, SetOne
, SetTwo
) which load a value into the
accumulator. The function called will depend on whether gamestate
is
$00
, $01
, or $02
respectively. (Obviously this is a contrived
example, but the technique can be used in a variety of situations.)
; Define the game state variable that specifies which
; function is called. In a NES ROM, you would use an
; .enum $0000 block to specify this would go at the
; beginning of CPU memory.
gamestate .dsb 1
; Define the memory address where we'll jump to. As memory
; locations are 16-bit, we need 2 bytes of RAM.
vector .dsb 2
; End declaration of RAM variables
; Set a test game state value. In an actual game, you could
; use constants rather than a hard-coded value.
; (Try loading $01 and $02 into A and storing in gamestate and
; see which function is called.)
LDA #$00
STA gamestate
EngineLogic:
; We take the gamestate and shift it left to get the index in
; the logic_functions table.
; Total cycles: 26-28 cycles depending if page boundaries are
; crossed when loading from logic_functions.
LDA gamestate
ASL A
TAX
LDA logic_functions, X
STA vector
LDA logic_functions+1, X
STA vector+1
JMP (vector)
FinishEngineLogic:
; We'll just jmp back to EngineLogic so we endlessly loop. In
; an actual game we'd probably return from the NMI. And then
; on the next NMI we'd find out the next engine logic function
; to call and call it appropriately.
JMP EngineLogic
SetZero:
LDA #$00
JMP FinishEngineLogic
SetOne:
LDA #$01
JMP FinishEngineLogic
SetTwo:
LDA #$02
JMP FinishEngineLogic
; Table of functions which will get called. As memory
; addresses are 16-bit, you need a word for each location,
; hence the .dw directive.
logic_functions:
.dw SetZero, SetOne, SetTwo
What’s the advantage of the jump table? It creates a single
authoritative source of what logic function is called given the
gamestate
variable. Using CMP
instructions, we aren’t bound to
keep all our comparisons together. We could strew them throughout our
code, which would violate The Pragmatic Programmer’s DRY principle:
Every piece of knowledge must have a single, unambiguous, authoritative representation within a system.
Using a jump table, we automatically keep the list of called functions together, and we only have one piece of code which determines the appropriate table index, retrieves the function address, and then jumps to it.
But how fast is it? In comparison, we could write the equivalent code in
EngineLogic
using CMP
instructions:
EngineLogic:
LDA gamestate
BEQ SetZero
CMP #$01
BEQ SetOne
CMP #$02
BEQ SetTwo
This only uses 13–19 cycles depending on if page boundaries are crossed calling
SetZero
, SetOne
, or SetTwo
, but note the cycle count increases by 4–6
cycles for each comparison and branch added.
In contrast, the jump table’s cycle count doesn’t increase as more options are added. So if we needed to go to one of 6+ different functions, the jump table would be more efficient.
Adding a new function to the jump table is a snap: Simply add it at the
end of the logic_functions
table, and if the gamestate
variable is
the appropriate value, it’ll automatically get called.
I’m using this basic technique throughout my project. If you don’t use the
indirect jump (JMP (vector)
), you can even use it to retrieve data stored in
a table: I use variations of this technique to retrieve which screen needs to be
shown at various points in the game, what prices are for goods at various
in-game shops, and so on.