6

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?

3
  • 7
    So why not use the Indirect Jump?
    – Justme
    Jan 19 at 11:20
  • 2
    The main gain lies in having separate tables for the low and high bytes of your jump targets, which you can also use in your approach. Then the self-modifying approach has the same number of cycles as the indirect jmp version and one cycle less than the RTS method. RTS method and indirect JMP are shorter in code though. Your approach is good if code is in RAM, you need to be fast, and have no ZP addresses available.
    – Peter B.
    Jan 19 at 16:44
  • 1
    This is basically what Forth does in its indirect threaded code. It just generates a bunch of addresses and you save one byte for every JSR.
    – cup
    Feb 1 at 7:49
16

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,
7
  • I was thinking exactly the same, but didn't know how to formulate the idea in words as it was a bit of a guess. Thanks I'll look into it more !
    – Pixel
    Jan 19 at 11:31
  • 2
    @Eight-BitGuru it works a treat, but I noticed that I need to set it to ADDRESS-1 because on RTS the PC is increased by 1. Thank you.
    – Pixel
    Jan 19 at 13:32
  • 3
    @Pixel Another way to do this is to use PHP RTI instead of RTS. RTI doesn't do the extra increment of the PC. This method is a little slower but results in cleaner assembly, hence easier to debug.
    – Chromatix
    Jan 19 at 18:34
  • 1
    RTI restores .P from the stack as well as the PC.
    – LawrenceC
    Jan 19 at 22:05
  • 1
    @LawrenceC Which is why you precede it with PHP.
    – Chromatix
    Jan 20 at 0:16
7

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

1
5

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.

8
  • Interesting alternative, I like the flexibility of adding additional code in the branches. You should add that the code between jumps and jumptable needs to be on the same page to make it work with just changing the lowbyte of patch1.
    – Peter B.
    Jan 20 at 10:19
  • Just asking: In the example shouldn't it called "sta patch1+1"? Jan 20 at 14:26
  • 1
    @supercat I like the 'lo-byte-only' table idea - I have other data tables like this but oddly in 40 years of writing 6502 I never made the cognitive link to a 1-page subroutine address jump table. As I mostly write VIC-20 cartridge ROM code I'll use the indirect jump (through a ZP vector) rather than the self-modifying variant. Old dogs and new tricks, eh? ;) Jan 20 at 15:55
  • 2
    @Eight-BitGuru: Even when using the ZP vector jump approach, placing all of the jump targets within a page and devoting a byte to hold the upper byte of the target address is still a good technique. Using a three-cycle store and a five-cycle indirect JMP would only cost one cycle more than using a four-cycle store and three-cycle JMP. Too bad there's no ZP-indirect form of JMP. I wonder how the silicon cost of the existing design would compare with the silicon cost of having all multi-byte opcodes use the same eight addressing modes, processed by the same logic, and implement JMP by...
    – supercat
    Jan 20 at 17:00
  • 1
    ...having it process its address the same way LDA would, but treat the fetched byte as the next opcode and have it latch the address being accessed as a program-counter value? There's enough opcode space to assign eight opcodes to all multi-byte non-branch instructions, and I would think having all such instructions process addressing modes identically would be no more expensive than having instructions like BIT placed at weird spots.
    – supercat
    Jan 20 at 17:05
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!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.