Efficient way to JMP or JSR to an address stored somewhere else?

Question

I'd like to JSR or JMP (preferably JMP as it's 3 cycles cheaper) to an address stored somewhere else in memory, the address of which is itself indexed.

I came up with the following self-modifying code (which I know is sometimes not regarded as good practice):

    ldx #2
    lda storedAddresses, x
    sta selfModify + 1
    inx
    lda storedAddresses, x
    sta selfModify + 2

.selfModify
    jmp selfModify   // jmp (or jsr) to $BEEF

...

.storedAddresses
    .byte $AB    // lo byte of address1
    .byte $CD    // hi byte of address1
    .byte $EF    // lo byte of address2
    .byte $BE    // hi byte of address2

$BEEF: // do something...

Is there a more efficient way to achieve this?

Answer 1

You could also use the Stack and RTS. This is code I use to reference an indexed jump table containing subroutine addresses:

    ldy #$nn                            // [2]      load jump address offset
    lda f40.CONCODEH,y                  // [4]      get control code handler address hi-byte
    pha                                 // [3]      push to Stack
    lda f40.CONCODEL,y                  // [4]      get control code handler address lo-byte
    pha                                 // [3]      push to Stack
    rts                                 // [6]      return via control code handler

Note that the addresses have to be decremented by 1 because RTS increments it automatically. Example table:

CONCODEL:   .pc = * "CONCODEL"      // Control character handler lo-bytes
            .byte <setcolr-1,<shftmode-1,<shftmode-1,<linefeed-1,<cargrtrn-1
CONCODEH:   .pc = * "CONCODEH"      // Control character handler hi-bytes
            .byte >setcolr-1,>shftmode-1,>shftmode-1,>linefeed-1,>cargrtrn-1,

Answer 2

I came up with the following self-modifying code (which I know is sometimes not regarded as good practice):

So don't modify, but use an indirect JMP

    LDX   #whateverindex*2     *     Index to be used
    LDA   AddressTable,X       * 3/4 Low byte target address
    STA   IndirectPTR          * 2/3 Store to pointer (+1/1 if not in ZP)
    LDA   AddressTable+1,X     * 3/4 High byte target address
    STA   IndirectPTR+1        * 2/3 Store to pointer (+1/1 if not in ZP)
    JMP   (IndirectPTR)        * 3/5 Do the jump

It's 4 byte longer than going via stack, but one clock less (if the pointer resides in ZP).

Answer 3

Place a sequence of JMP instructions, possibly along with other small bits of code, within a single page. One may then use something like:

    lda jumpTable,x
    sta patch1+1
patch1:
    jmp jumps

jumps:
jproc1: jmp proc1
jproc2a: lda #0
        jmp proc2
jproc2b: lda #1
        jmp proc2
jproc2: jmp proc2

jumpTable:
    .byte <jproc1, <jproc2a, <jproc2b, <jproc1, <jproc1, <jproc3

Note that if multiple spots in the jump table should identify the same routine, they may all springboard off the same jump instruction, and that it's possible to include little bits of code within the jump table if the whole thing fits in a page.

One could use an indirect jump instruction rather than a jmp at location patch1, and then simply list addresses rather than jump instructons starting at jumps. This would save a byte per entry, and also save a cycle at execution time, but would forego the ability to insert tiny bits of code within the jump table itself which can often be very useful if multiple entries in the jump table should have behaviors that should match except for one small detail.

Note that even in situations where this approach would end up requiring a an "extra" jump, the three cycles necessary to execute an extra JMP instruction will be far cheaper than the load and store necessary to handle the second byte from a table of two-byte jump addresses.

Answer 4

The usual reason to want to do this is jump tables.[1] So let's assume we're doing that, and compare the performance of a few different ideas.

The setup: we have an integer from 0 to N-1 stored in a register. We want to JMP or JSR to one of N possible addresses.

We're tracking cycle count (and whether it's constant), code size and how it varies with N, register/stack/zp usage, the maximum value of N, whether we modify inline code (to be avoided when running from ROM; calling code we constructed in zp is assumed to be fine), whether we can trivially replace JMP with JSR, and any usage-specific optimizations.

Branches are assumed to be taken or not taken with equal frequency. Cycle counts are for NMOS 6502s unless using 65C02-specific instructions.

Idea 1: Big table of JMPs

table:
        .align $100
        JMP addr0
        JMP addr1
        JMP addr2
        [...]

idea1:  // index in A
        [4]   STA tmp+1 // multiply A by 3
        [2]   ASL A     // we know A<128 so ASL will clear the carry
tmp:    [2]   ADC #$00  // self-modified
        [4]   STA jmp+1
jmp:    [3]   JMP table // self-modified

Table must lie on a page boundary for the multiplication to calculate the low byte correctly. Replace JMP table with JSR table to return whence we came afterwards.

Optimization: the final entry in the table can be the start of a routine instead of a jump.

Cycles: 4+2+2+4+3+3=18. Constant time: yes. Stack used: 0. ZP used: 0. Index in A. Other regs clobbered: none. Self-modifying: yes. JSR capable: yes. Size: N*3+12 bytes. Max N: 85.

Idea 1a: same as idea 1 except we have a lookup table of offsets instead of doing multiplication

This also allows the table to not need to start at the beginning of a page (it still must not cross a page boundary). For cycle counting we'll assume lookup does not cross a page boundary either.

table:
        JMP addr0
        JMP addr1
        JMP addr2
        [...]
lookup:
        .byte <table, <table+3, <table+6, [...]

idea1a: // index in X
       [4]   LDA lookup,X
       [4]   STA jmp+1
jmp:   [3]   JMP table // self-modified

Cycles: 4+4+3+3=14. Constant time: yes. Stack used: 0. ZP used: 0. Index in X (or Y). Other regs clobbered: A. Self-modifying: yes. JSR capable: yes. Size: N*4+9 bytes. Max N: 85.

Optimization: any of the JMPs in the table can be replaced with the routine itself, not just the last one, subject to the table fitting in a single page.

Idea 1b: As idea 1, but pad the table

This means we're multiplying by 4 not 3, and is the same size as the lookup version, but now max N is only 64.

table:
        .align $100
        JMP addr0; NOP
        JMP addr1; NOP
        JMP addr2; NOP
        [...]

idea1b: // index in A
       [2]   ASL A
       [2]   ASL A
       [4]   STA jmp+1
jmp:   [3]   JMP table // self-modified

Cycles: 2+2+4+3=14. Constant time: yes. Stack used: 0. ZP used: 0. Index in A. Other regs clobbered: none. Self-modifying: yes. JSR capable: yes. Size: N*4+8 bytes. Max N: 64.

Optimization: perhaps you can squeeze some routines into 4 bytes?

Idea 2: Push return address on the stack and RTS

The address pushed must be one less than the desired location for arcane reasons.

tablelo:
        .byte <addr0-1
        .byte <addr1-1
        .byte <addr2-1
        [...]
tablehi:
        .byte >addr0-1
        .byte >addr1-1
        .byte >addr2-1
        [...]

idea2: // index in X
       [4]   LDA tablehi,X
       [3]   PHA
       [4]   LDA tablelo,X
       [3]   PHA
       [6]   RTS

Cycles: 4+3+4+3+6=20. Constant time: yes. Stack used: 2. ZP used: 0. Index in X (or Y). Other regs clobbered: A. Self-modifying: no. JSR capable: no. Size: N*2+9 bytes. Max N: 256.

Optimization: if you can ensure all your destinations lie within a single page (taking the off-by-one into account) then replacing LDA tablehi,X with a constant load saves two cycles.

Idea 3: Store address into JMP instruction

tablelo:
        .byte <addr0
        .byte <addr1
        .byte <addr2
        [...]
tablehi:
        .byte >addr0
        .byte >addr1
        .byte >addr2
        [...]

idea3:
        [4]   LDA tablelo,X
        [4]   STA jmp+1
        [4]   LDA tablehi,X
        [4]   STA jmp+2
jmp:    [3]   JMP $0000 // self-modified

Cycles: 4+4+4+4+3=19. Constant time: yes. Stack used: 0. ZP used: 0. Index in X (or Y). Other regs clobbered: A. Self-modifying: yes. JSR capable: yes. Size: N*2+15 bytes. Max N: 256.

Idea 3a: Store address into zero page JMP instruction

tablelo:
        .byte <addr0
        .byte <addr1
        .byte <addr2
        [...]
tablehi:
        .byte >addr0
        .byte >addr1
        .byte >addr2
        [...]

idea3a_init:
        LDA #$4C // JMP opcode
        STA zp
        RTS

idea3a:
        [4]   LDA tablelo,X
        [3]   STA zp+1
        [4]   LDA tablehi,X
        [3]   STA zp+2
        [3]   JMP zp

Cycles: 4+3+4+3+3+3=20. Constant time: yes. Stack used: 0. ZP used: 3. Index in X (or Y): Other regs clobbered: A. Self-modifying: no. JSR capable: yes. Size: N*2+13+5 bytes. Max N: 256.

Idea 3b: As idea 3, but all destinations are in a single page

tablelo:
        .byte <addr0
        .byte <addr1
        .byte <addr2
        [...]

idea3b:
        [4]   LDA tablelo,X
        [4]   STA jmp+1
jmp:    [3]   JMP addr0 // self-modified

Cycles: 4+4+3=11. Constant time: yes. Stack used: 0. ZP used: 0. Index in X (or Y). Other regs clobbered: A. Self-modifying: yes. JSR capable: yes. Size: N*1+9 bytes. Max N: 256.

Idea 4: Use indirect jump instruction

table:
        .align $100
        .word addr0
        .word addr1
        .word addr2
        [...]

idea4: // index in A
       [2]   ASL A
       [4]   STA jmp+1
jmp:   [5/6] JMP (table) // self-modified

Cycles: 2+4+5=11. Constant time: yes. Stack used: 0. ZP used: 0. Index in A. Other regs clobbered: none. Self-modifying: yes. JSR capable: no. Size: N*2+7 bytes. Max N: 128.

Note that due to a bug on NMOS 6502s, the indirect jump instruction reads the incorrect address if it straddles a page boundary. This is no issue for us as the table must start on a page boundary anyway. The bug was corrected on the 65C02 at the cost of one extra cycle.

Idea 4a: As idea 4, but allow N>128 by having two tables

table0:
        .align $100
        .word addr0
        .word addr1
        .word addr2
        [...]
table128:
        .align $100
        .word addr128
        .word addr129
        .word addr130
        [...]
        
idea4a: // index in A
       [2]   ASL A
       [2/3] BCS msbset
       [4]   STA jmp+1
jmp:   [5/6] JMP (table0)   // self-modified
msbset:[4]   STA jmp2+1
jmp2:  [5/6] JMP (table128) // self-modified

Cycles: 2+2.5+4+5=13.5. Constant time: no. Stack used: 0. ZP used: 0. Index in A. Other regs clobbered: none. Self-modifying: yes. JSR capable: no. Size: N*2+15 bytes. Max N: 256.

Idea 4b: Use indirect jump instruction in zero page

table:
        .align $100
        .word addr0
        .word addr1
        .word addr2
        [...]

idea4b_init:
        LDA #$6C // JMP indirect opcode
        STA zp
        LDA #>table // high byte of table
        STA zp+2
        RTS
        
idea4b: // index in A
       [2] ASL A
       [4] STA zp+1
       [3] JMP zp

Cycles: 2+4+3+5=14. Constant time: yes. Stack used: 0. ZP used: 3. Index in A. Other regs clobbered: none. Self-modifying: no. JSR capable: yes. Size: N*2+9+6 bytes. Max N: 128.

Idea 5: Use 65C02 indexed indirect jump instruction

table:
        .word addr1
        .word addr2
        .word addr3
        [...]

idea5: // index in A
       [2] ASL A
       [2] TAX
       [6] JMP (table,X)

Cycles: 2+2+6=10. Constant time: yes. Stack used: 0. ZP used: 0. Index in A. Other regs clobbered: X. Self-modifying: no. JSR capable: no. Size: N*2+5 bytes. Max N: 128. 65C02 only.

Idea 5a: As idea 5, but split the table into even and odd entries to avoid a shift and to allow N>128

tableeven:
        .word addr0
        .word addr2
        .word addr4
        [...]
tableodd:
        .word addr1
        .word addr3
        .word addr5
        [...]

idea5a: // index in A (or X)
       [2]   TAX (or TXA)
       [2]   AND #1
       [2/3] BEQ even
       [6]   JMP (tableeven,X)
even:  [6]   JMP (tableodd-1,X)

Cycles: 2+2+2.5+6=12.5. Stack used: 0. ZP used: 0. Index in A (or X). Other regs clobbered: X (or A). Self-modifying: no. JSR capable: no. Size: N*2+11 bytes. Max N: 256. 65C02 only.

Idea 5b: As idea 5a, but split the table into high and low instead of even and odd

table0:
        .word addr0
        .word addr1
        .word addr2
        [...]
table128:
        .word addr128
        .word addr129
        .word addr130
        [...]
idea6: // index in A
       [2]   ASL A
       [2]   TAX
       [2/3] BCS msbset
       [6]   JMP (table0,X)
msbset:[6]   JMP (table128,X)

Cycles: 2+2+2.5+6=12.5. Constant time: no. Stack used: 0. ZP used: 0. Index in A. Other regs clobbered: X. Self-modifying: no. JSR capable: no. Size: N*2+10 bytes. Max N: 256. 65C02 only.

Results table

Idea	Cycles	Const	Size	max N	65C02	Self-mod	JSR	Stack	ZP	Index	Clobbered
1	18	yes	N*3+12	85	no	yes	yes	0	0	A	none
1a	14	yes	N*4+9	85	no	yes	yes	0	0	X/Y	A
1b	14	yes	N*4+8	64	no	yes	yes	0	0	A	none
2	20	yes	N*2+9	256	no	no	no	2	0	X/Y	A
3	19	yes	N*2+15	256	no	yes	yes	0	0	X/Y	A
3a	20	yes	N*2+18	256	no	no	yes	0	3	X/Y	A
3b	11	yes	N*1+9	256	no	yes	yes	0	0	X/Y	A
4	11	yes[2]	N*2+7	128	no	yes	no	0	0	A	none
4a	13.5	no	N*2+15	256	no	yes	no	0	0	A	none
4b	14	yes[2]	N*2+15	128	no	no	yes	0	3	A	none
5	10	yes	N*2+5	128	yes	no	no	0	0	A	X
5a	12.5	no	N*2+11	256	yes	no	no	0	0	A/X	X/A
5b	12.5	no	N*2+10	256	yes	no	no	0	0	A	X

Conclusions: there's no one "best" idea, it depends what your constraints are.

• Idea 5 is the clear winner on 65C02 (this is why the 65C02 has an indexed jump instruction!), and 5b is slightly better than 5a if you need N>128.
• Idea 4 is often best if you don't mind self-modifying code (and have N<=128).
• Idea 2 is the most well-known "trick" and has few gotchas, but is tied for slowest.
• Idea 3a is about as good as idea 2 if you need ROMable code but prefer zp usage to stack usage, or need to JSR instead of JMP, but idea 4b beats it for N<=128.
• Idea 3b is basically idea 1a with the optimization applied; it's a special case but great if you can pull it off.
• Idea 1 and variants are most useful when N is small.

A JSR/RTS pair can be replaced with two JMPs (saving six cycles, but using two extra bytes) if the routine is called from only a single place. This makes the option of replacing JMP with JSR less important.

[1] The second most common reason to want to do this is to provide hooks for your ROM-based OS routines to be patched or otherwise redirected at runtime.

[2] One extra cycle on 65C02. Sometimes this matters!