Which means Commodore 64, Apple ][, Atari 2600, Acorn Atom, NES…inspired, of course, by this topic.
I’m working on the 6502 Å-machine interpreter, and my inexperience with 6502 assembly is really showing. I’m currently working on this block of code, which is run when entering a div:
ldx divsp ; Div stack pointer
lda opermsb+0 ; Most significant byte of operand 0
sta divstk,x ; Div stack
lda operlsb+0 ; Least significant byte of operand 0
sta divstk+1,x
inx
inx
stx divsp
asl
rol opermsb+0
asl
rol opermsb+0
asl
rol opermsb+0
;clc
adc stybase
sta phydata
lda opermsb+0
adc stybase+1
sta phydata+1
I can’t figure out what this ASL - ROL - ASL - ROL - ASL - ROL sequence is doing. I know it’s messing with the bits of the operand, but what happens when you interleave them like this?
This treats accumulator as the lowbyte and opermsb+0 as the highbyte of a 16-bit number, and shifts this number three steps to the left, i.e. multiplies it by 8.
ASL shifts a 0-bit in at the bottom of a value and shifts the top bit of the value out into the carry. ROL shifts the carry in at the bottom of a value and shifts the top bit out into the carry.
At the end, if we’re sure the original number was small enough that we can’t get an overflow (i.e. the result can’t be bigger than what fits in 16 bits), we know that the carry is clear, thus we can skip clc before the addition.
Since multiplication isn’t supported in hardware on 6502, one will typically use shift operations instead, when speed is important and one of the factors is known in advance. E.g. an entry in the object table is 14 bytes long in z5. Instead of calling a generic multiplication routine with the value and 14 as the parameters, you can:
shift the value three times (Now we have the original value x8)
subtract the original value from this (Now we have the original value x7)
shift the value one more time (Now we have the original value x14)
Ahh, that makes sense! This interpreter stores style class information in structs seven bytes long; I’m guessing those structs are padded out to eight bytes for simplicity, so this is taking the index of a struct, multiplying it by eight (23), then adding it to stybase (start of the struct array?) and putting the 16-bit result in phydata (start of the current struct?).
Yes, it performs: phydata = stybase + 8 * oper0
(where oper0 consists of an LSB (least significant byte) and MSB (most significant byte), which are stored in two different arrays, because it’s faster to access them that way)
Not much to add to what Fredrik wrote, but regarding the structure padding, a non uncommon way to optimize things on 6502 is to unpack “arrays of structs” into “structs of arrays”.
Say you have an array with 50 elements that each contain a 16 bit pointer, and two 8 bit variables, instead of storing that as 50 times 4 bytes, you could have 4 arrays of 50 elements:
Low byte of the pointer
High byte of the pointer
first 8 bit variable
second 8 bit variable
This way you can access any element just with X or Y indexed access without multiplying.
Obviously that’s only useful if you are going to have no more than 256 elements, and if all the sizes are known at compile time.
I think once I finally wrap my head around all the opcode mnemonics, I’ll get a lot faster at all of this. I have the advantage of experience with assembly on other systems (though generally ones with a lot of registers, like MIPS or the Z-machine); having only A, X, and Y is a bit of a change! Thankfully Linus commented his 6502 assembly a lot more than his C.
I felt very smart when I finally figured out the purpose of BIT yesterday. The C64 Å-machine interpreter has a “register” (is there a better short name for “byte in the zero page”?) called stflag that records whether it’s currently in a status area: $00 for nothing, $FF for the top status bar (supported), $80 for the inline status bar (not supported). It took me ages to figure out why these values specifically—it’s because they can both be created without any immediates (decrement $00 to get $FF, rotate $00 with the carry flag set to get $80), and can then be tested with BIT. N will be set if any status bar is active, and V will be set if it’s a supported one.
Size optimization on the 6502 is a compounding thing: Since relative branches are encoded on a single byte you can only go that far forward or backward, so as soon as a routine grows you start having to use JMP instead of Bcc… which in turn makes the code larger so you end up doing inverted tests to branch over a JMP that can actually go where you want to go.
So every time you can reduce by one byte here, one byte there, you increase the change you can turn a JMP into a Bcc (by ensure state flags are stable of course), which in turn can be a large enough change that you can convert some more, remove the inverted branches, etc…
You also often see things like the RTS statement is actually in the middle of the routine so the exit can be reached relatively from any point in the routine.
Anyone want to guess how long it took me to realize that PHY and PLY didn’t exist on the 6502 today (and thus my code including PHY and PLY would hang the emulator)? It was too long.
What I need to do is:
lda (hdbase), 1 ; Look at the first byte of the header
bne v1 ; If it's not zero, then this is a version 1.x story file
…but without affecting Y or C.
So I ended up with this abomination:
.(
php ; Save the flags, since C is used to choose instruction variant
tya ; PHY/PLY don't exist on the 6502, so we have to use A
pha
ldy #1
lda (hdbase),y ; Header byte 0: major version
bne v1
pla
tay
plp ; Restore the flags
jmp op_en_lv_st ; Version 0.x = enter/leave status
v1
pla
tay
plp ; Don't leave the flags lying around on the stack
jmp op_bstyle ; Version 1.x = body style
.)
This is definitely a lot of wasted cycles, but this isn’t a very frequent operation, so hopefully it’s fine for now. If someone who actually knows 6502 assembly wants to optimize it, pull requests are always welcome!
It’s one of those microprocessors with very few registers (A, X, Y, and that’s about it), so there are separate instructions for TAY (Transfer A to Y), TYA, TAX, and TXA. As far as I know there’s no way to copy X into Y or vice versa without clobbering A.
As someone used to machines with a lot more registers (at least 16 of them), trying to keep the values of my three registers intact while doing any sort of calculation is a nightmare! I thought I could PHY (PusH Y onto the stack) and PLY (PulL Y from the stack) for the brief moment I need to store something else in there, but no…
php
lda hdbase
clc
adc #1
sta check_addr+1
lda hdbase+1
adc #0
sta check_addr+2
plp
check_addr
lda $1234
bne v1
Uses only the A register and some self-modifying code to avoid having to touch Y.
On my 6502 Z machine, the header is always loaded at a fixed address in memory, so the equivalent for me would be just lda $1001 or lda HEADER+1
Edited to add php/plp since your constraints included “don’t modify the carry flag” and at this point I can’t say this is any better than your solution.
The constraints of “don’t touch carry flag but the answer has to be in the zero flag” are fairly limiting since both the load and transfer instructions affect the Z flag.
sty yrestore+1
ldy #1
lda (hdbase),y ; Z contains result we care about
php
yrestore
ldy #$12 ; this modifies Z
plp ; restore original Z result from above
is another option that avoids ZP use but is still self-modifying code. If you didn’t need to preserve the carry flag, you could leave out the php and replace the plp with cmp #$00 or whatever header value you cared about.
