Yes, that's the table! And using BIT to test the input could well be a win - with the loop unrolled, it can be a bit immediate, if you have that instruction. But if you're doing an in-place x10, you can LSR the bignum's byte in-place: you'll be updating it from the accumulator when you're done, so no harm in modifying it. Just possibly copying it to zero page first would be a win.

I don't. Remember I live in the mid-70s. (For me, the modern 6502s are the ones with ROR!)


The buffers holding these numbers are allocated in the heap, so to use LSR in-place I'd need to use self-modifying code. (Which I'm not entirely ruling out, but it's definitely additional complexity because ROM etc.) But copying to the ZP and LSRing it there sounds like it would work great. (I actually suspect that, because all values will be in the heap, I'm going to have tons of zero page space available, so I'm definitely not worrying about that right now.)

_________________
Curt J. Sampson - github.com/0cjs

I don't have the tools to test it here, and I am more than a little rusty with 6502 code. But maybe something like this:


Each byte that gets processed modifies two bytes of the result. But we need the original value of the next byte. So it keeps two bytes of the input in srcLow/srcHigh. accLow/accHigh is the accumulator used to build each byte of the result. At the end of processing each byte, accHigh becomes the initial value of accLow for the next byte. The table is 10*2^n - 1 to save a clc on each bit - we know that carry is set.

(edit) and I am clearly confused. It does not modify the next byte of the number yet - that's what accHigh gets copied to accLow is for. So there's no need for srcHigh. But copying the byte that we're working on does mean we don't need to pretend that we've got lsr (zp),y.

reusing the known-to-be-set carry is a nice trick!

In case anybody gets enthusiastic enough about this to start assembling code, here are my test cases. (And do let me know if you see any coverage missing.)


The expected output is calculated for each test using standard Python 3 functions, along the lines of:

These cases include both signed and unsigned multiplies (as explained earlier in this thread, the current routine doesn't know the difference, only the caller does), but I don't see any particular reason off-hand to support unsigned if that makes life more difficult.

Of course, if you don't already have a testing framework in which to plop these cases, you may find it easier just to grab 0cjs/8bitdev from GitHub and just replace my routine in src/bigint.a65 with your own. The test cases are in src/bigint_test.py, and anything you print() will be shown if the test case fails. (You can force failure with assert False.)

_________________
Curt J. Sampson - github.com/0cjs

Possibly better: take your byte, make sure there's another copy somewhere in memory (free if you've just copied it into accumulator from elsewhere), shift left twice (so you have original value ×4), add the other copy (giving you original value ×5), shift left once more (yielding original value ×10). Instead of saving a temporary ×2 value, you simply access the original value twice.

But yeah, this still requires shifting the entire number, which is fine if it's a byte or two, but expensive on an arbitrarily big int. The other approach outlined a few posts above is probably best for bigints.

_________________
Retro 6k

Unfortunately in my application I am working on the original number, rather than a copy of it, as this multiply is used while building the original number (from a string of ASCII digits) in the first place.

That said, this was a really worthwhile comment. Not only did it remind me that I should always continue to think about alternate ways of doing things (using copy ×2 ×2 add ×2 instead of ×2 copy ×2 ×2 add), but it also caused me to reexamine my buffer usage in the current routine and realize that I could incorporate the copy into the first multiply loop and delete the second loop that did the copy:


(The diff is perhaps not totally easy to read: after the sta (buf0ptr),y in the first loop, which stores the shifted byte back into the source buffer I add just sta (bufSptr),y to store that same byte in the scratch buffer, and then entirely delete very similar second loop.)

This reduces the code size from 55 to 48 bytes (7 fewer bytes, 13% improvement) and also reduces the execution time by 11% (1 byte 109→97 cycles, 2 bytes 200→178, 255 bytes 24741→21936 cycles). Since the multiply is the majority of the work in reading a bigint from an ASCII string, that translates into a 10% speedup in reading numbers, which is pretty sweet for such a simple change.

_________________
Curt J. Sampson - github.com/0cjs