In the upcoming 1.1 version of the Å-machine, multiplication needs to fail if it overflows, rather than wrapping around. Which means the 6502 implementation needs to detect this overflow.
Currently, 16-bit multiplication is handled by this mul16 subroutine:
mul16
; input quot, denom
; output numer
; clobbers quot, denom, y
.(
lda #0
sta numer
sta numer+1
ldy #16
loop
lsr denom+1
ror denom
bcc nobit
lda numer
clc
adc quot
sta numer
lda numer+1
adc quot+1
sta numer+1
nobit
asl quot
rol quot+1
dey
bne loop
rts
.)
(Where numer, denom, and quot are two-byte blocks in the zero page.)
This seems to be standard bitwise long multiplication. There will be overflow if the high byte of the result doesn’t fit in numer+1, which happens if the adc quot+1 instruction right before sta numer+1 ever sets the carry flag.
Normally, when this subroutine returns, the zero flag will always be set, because of the bne loop. Which means if the carry flag is set right after adc quot+1, we can clear the zero flag and rts; the caller will then know from that flag that the result is not good and should be discarded.
Does this all make sense? Is there a more elegant way to do it?
Oh wow, there’s a lot of data here! I’m not sure I have enough 6502 experience to interpret these—I don’t know how to evaluate cycles versus bytes.
In this case, signed or unsigned doesn’t matter, since it will only ever be used with 14-bit unsigned inputs; and the full 32-bit result doesn’t matter, we only need a 16-bit result and “does it overflow”. (The output sometimes is treated as a 16-bit value instead of a 14-bit one, but not often.)
Is there an algorithm among these that’s obviously best under those requirements?
omult16.a sounds like an excellent fit for your scenario.
Evaluating cycles vs bytes is about understanding what’s important in your application. If multiplications must be as fast as possible, and size doesn’t matter, you won’t mind using up say 2 KB more RAM on a multiplication routine to make it twice as fast.
When Ozmoo is built for (a possibly unexpanded) C64, the code size must be kept small, as all RAM we use on code is RAM we can’t use for story data. In the end this means a bigger interpreter needs to swap more, and more games will become unplayable. Still, we try to strike a balance, allowing parts of the interpreter to be a bit bigger than absolutely necessary, to make it execute Z-code faster, to decode and print text faster etc. On the other hand, when built for C128, a few extra KB of code isn’t a big deal, so we’ll allow code that’s only used on C128 to be a bit more wasteful with RAM, if it means it gets faster.
The total size of Ozmoo on C64 is about 11-13 KB, in standard configuration. The multiplication routine takes up 66 bytes, which I think makes sense. In a typical text adventure, multiplication isn’t used that much. Reading and performing one (not overly complicated) Z-code instruction typically takes about 500 cycles.A lot of that time is spent reading and decoding the instruction and the arguments. If a multiplication adds say 600 cycles of processing, that’s okay. We’re not willing to spend 1000 bytes extra on code to make it twice as fast.
Whenever we happen to know one of the factors at compile time, we use shifts instead of calling a generic multiplication routine, as this is faster. E.g. each entry in the object tree is 9 bytes (in version 1-3). Instead of calling a generic multiplication routine to multiply the object number by 9, we shift it three positions to the left (each shift doubles the value), then add the object number. Sometimes this makes the code bigger, but it makes such a big difference in performance, that we think it’s worth it.
omult16.a does seem ideal for this circumstance! My only concern is, can it actually detect overflow? The comments put question marks on that, and if this person who’s clearly an expert on 6502 multiplication algorithms isn’t sure, I suspect my very limited 6502 experience won’t be enough to figure it out either.
I’ve implemented it in the meantime, and it’s passed every test case I’ve thrown at it. So for now, I’m happy to include this in the upcoming Å-machine 1.1.0! If it does actually fail in some weird edge case, then we can fix that in a future patch.
I put it in my test suite. After more than three million random multiplications, my test harness hasn’t detected a single failure.
My tests use rotating masks so it’s multiplying 1 bit x 1 bit, 1 bit x 2 bits .. 1 bit x 16 bits, 2 bits x 1 bit, 2 bits x 2 bits .. 16 bits x 16 bits, repeat with new random numbers, indefinitely
Note: This is what my test suite does for each multiplication:
Make a multiplication using mult50 (16 bit x 16 bit => 32 bit).
Make the same multiplication using mult6
If both algorithms say the result is larger than 16 bits, test succeeded!
If the algorithms disagree on whether the result is larger than 16 bits, test failed!
If both algorithms say the result fits in 16 bits, compare the results. If they are the same, test succeeded! If not, test failed!
What it doesn’t currently test, is whether the lower 16 bits of the result is the same for the two algorithms, in the case when the full result is larger than 16 bits. Does this matter for your application? (I think this would fail, and you’d need to switch to 16x16=>32 bit algorithm to have it work)
I’ve switched to omult6.a, and it seems to be working for now. The places where this routine is invoked:
The MUL_NUM opcode multiplies any two 14-bit numbers. It explicitly checks for overflow and fails if it happens (or if the top two bits of the result aren’t 00).
Divs with relative width or height (“height: 50%”) multiply that percentage by the screen width (and then divide by 100). Neither of these is allowed to exceed 255, so overflow is impossible.
Parsing numbers multiplies the intermediate result by 10 as it reads each digit. Before calling mul16, it checks if the upper word is ≥ the upper word of 1639+256 (because 16383 is the maximum parsable number); if so, it doesn’t try the multiplication. This means the maximum possible multiplication is 1894 (= 1639 + 255) × 10, which doesn’t overflow.
The progress bar code is complicated and I don’t really understand how it works. But it stores 0 in the high bytes of both operands before calling mul16, so overflow is impossible.
The CSS parser repeatedly multiplies its intermediate value by 10 when parsing heights and widths. There’s no overflow check here; the interpreter just assumes authors won’t ask for a div with height 99999em. These values should never exceed 100[1] (an absolute width or height can’t be more than the screen dimensions, a percentage can’t be more than 100) so it’s not hard to add a check here; the question is, what should happen if it fails? I don’t have an answer for that. I guess just…not multiply and continue onward looking for a unit?
So I think we’re good!
Or rather should never exceed max(100, screen width, screen height) which is currently always 100 ↩︎
I filed an issue in Toby’s repo. He has identified the problem with omult16, stopped claiming that it signals all overflows using carry, and created a patched version of it, called omult33.
I think omult6 is still a good fit for Dialog, so no reason to replace it.