Multiplying and Dividing on the 6502 (2021) | Hacker News Reader

Multiplying and Dividing on the 6502 (2021)

llx.com

89 pointsibobev45 comments

> (The above routine is based on some code I found on a Commodore-64-related web page, which, unfortunately, I haven't been able locate again. The method doesn't seem to have been widely known among Apple II programmers.)

Here's one possible source from an excellent website that includes many more 6502 algorithms!

https://codebase64.org/doku.php?id=base:6502_6510_maths

My contribution there. :)

https://codebase64.org/doku.php?id=base:8bit_multiplication_...

My favorite commentary on this is from https://codebase64.org/doku.php?id=base:kernal_floating_poin... :

> Numerous advantages are gained improving the speed of the multiply. Routines that rely on it can be copied from the ROM and pointed to the new routine to improve performance. The following example relies on the Steve Judd's fast multiplication and reduces the number of cycles to multiply from around 2300 to little over 1400.

That's a nice speed increase from 435 multiplies/sec to 714 ops/sec. It's downright spritely!

There's also a faster log function that

> executes in around 13000 cycles, where the built-in routine takes 19000.

...jumping from 53 to 77 ops/sec. Smokin'!

Often, on this chip you want to come up with a very specific dedicated purpose multiply that's fast and that gives you enough precision to do the work.

The other tricks are all worth learning, cordic, shifts, look up tables and the other tricks we use when add shifts and rotates and bit opps are the only thing the CPU can do.

Right. I remember on the C64 using, for instance, y * 40 + x for screen positioning, since it had a 40 column screen.

Since y * 40 is (y * 8) + (y * 32), you'd take x, left-shift three times, save the result, shift left two more times, and add the two together. Pretty fast. You'd do stuff like this everywhere you knew the coefficients in advance.

Bingo! I did the same on an Atari.

Also, a lookup table for the Y address, plus a fixed X address can get bitmaps blitted to the screen quickly.

For special case graphics, just code in the addresses, unroll the loop and use index X or Y to handle screen positioning.

     LDX XPOS
     LDA IMAGE0
     STA SCREEN0, X
     LDA IMAGE1
     STA SCREEN1, X
     LDA IMAGE2
     STA SCREEN2, X

. . .

No multiply needed. Y addresses either coded at fixed position, or generated at runtime based on some event and or when there is time to compute it all off screen.

Trade RAM for speed!

Sigh... I remember doing a lot of this stuff as a teenager, looking forward to the day when I'd be getting paid to do it. But by the time I got paid to do stuff, there was no market for this kind of low-level optimization any more. Shame.

I hear ya!

Today, I mostly do it for fun on my old Apple machine. It is enjoyable to see what can be done. 1Mhz is actually quite a lot when one looks at the resolution and overall task to complete. And where to put it?

Things like having the game run at 30Hz or 15Hz so more can be computed in game, in real time. Then, when it comes to drawing everything, often a simple screen clear, or page flip then draw does not make sense. Two screens takes too much RAM, etc...

Single buffer, draw fast, only draw deltas, using XOR, all add up!

Getting paid?

I have done some assembly for money on Propeller chips, PIC, AVR, and the like. There are times in embedded land where doing these fun things pays off and makes sense.

For what it is worth, a little fun can be had for income, but not much.

The 6809 had a 'mul' instruction:

https://atjs.mbnet.fi/mc6809/Information/6809.htm

8x8 unsigned. I started out programming assembler on the KIM, then moved to the Dragon 32 which had a 6809 and then back to the BBC micro again, which in almost every way felt like a huge step forward and in that one way felt like a step back, the lack of 8x8 multiply in hardware. Here is a very neat (and pretty quick) multiplication routine:

http://www.txbobsc.com/aal/1986/aal8603.html

I'm surprised that the 6809 MUL instruction seems to have a fixed execution time (11 cycles, if I am interpreting the specs correctly). This implies to me that it might be heavily based on look-up tables, yet the 6809 surely had very limited die space for that

Barrelshifter!

Would I be very wrong to suspect that early RISC CPUs forced programmers and compilers to pull similar stunts? The major difference was probably that RISC systems had compilers, while on the 6502, it was BASIC or assembly. So programmers might not have noticed?

There were numerous compilers for the 6502.

I'll remember well UCSD Pascal https://en.wikipedia.org/wiki/UCSD_Pascal especially as compiling on a system with one floppy drive required 5-6 changes of the floppy disk even for a 'hello world'. So one would think twice before starting the compiler only to find a simple syntax error after a minute or two. :)

Absolutely true, there were and are MANY compilers for the 6502.

However, the 6502 was a challenge to implement high-level languages on, IF you also wanted speed and small code size. But since the 6502s were slow compared to modern chips, and could only address 64KiB directly, you typically also wanted speed and small size.

I posted some links to some approaches here: https://dwheeler.com/6502/

I always thought Action! was very crisply tailored to these small systems. It turns out to have been a port of a language called Micro-SPL from the Xerox Alto that (originally) targeted the Alto microcode directly.

Atalan and Plasma look nice.

Sure...they were amazingly widespread machines back in the day so lots of people took a whack at a 6502 compiler (at college if nothing else). But how many could take on non-trivial programs and emit code that would be considered production level? I know Apple Pascal was supposed to be pretty good, but what else?

I am pretty sure there were at least a couple of commercial games and applications written in valFORTH on the Atari 800. Possibly Action! also; for some reason I thought Paperclip was written in Action! but apparently not. There were a lot of magazine games and utilities written in Action!, though.

Hardware mul/div is still not universal on new products.

RISC-V doesn't have hardware mul/div in it's baseline spec. There's a "Zmmul" extension that adds mul, and the full "M" extension which includes mul/div. Technically, those extensions are optional, but I think most current hardware implementations include them.

That's...very weird I guess? Hardware mul/div requires so little chip real-estate relative to the whole die these days, and has such obvious advantage, why did they make it optional?

The point of the baseline spec, as far as I know, is to make a modern chip design that even the smallest fab or ASIC can build on its own.

I wrote almost nothing but assembly for ten years (mid 80s to mid 90s) and I think I can count on one hand the number of times I actually needed a generalized multiplication/division instruction. Heck, even square root could be done with repeated subtraction which could be Good Enough(TM), or maybe a lookup table.

The SeRV implementation of RISC-V fits into 200 4-LUTs on an ICE40 FPGA. If your FPGA doesn't have a multiplier, how many 4-LUTs do you need to build a 32x32 multiplier? I'm guessing the answer is comparable to 200.

Ah, you're right. I'm thinking in terms of transistors, not LUTs.

I think the case is even stronger if you're counting in transistors, because FPGAs usually come with multipliers built in, but bare silicon wafers don't. A CPU such as a 6502 or an Intersil 6100 (a PDP-8 on a chip) costs on the order of 4000 transistors. I suspect SeRV would be about the same size, maybe a bit smaller. How many transistors do you need for a 32-bit multiplier?

IIUC this is because:

* mul/div take a lot of transistors and may not be a single or fixed cycle instruction.

* A lot of embedded systems don't really need those instructions anyway - they just encode discrete state machines or do something like networking that doesn't need * or / for operation.

* less transistors means the chips are cheaper, and single (or fixed) cycles per instruction means hard real-time is simpler to reason about.

Is that correct?

Yes, the first generation of SPARC and MIPS processors also lacked multiply and divide. Processors are still made without multiply and divide.

I think we should look at the culture of programming around architectures like SPARC and MIPS and what kind of assumptions the designers had about how people would program them. Even though you could find compilers for 6502, and you could write assembly for MIPS and SPARC, assembly programming was de rigueur for 6502 and it was not for MIPS and SPARC. 6502 systems are typically cheap and have small amounts of memory, and the architecture is a bit weird if your targeting a C compiler (inconvenient 256 byte stack, for example). MIPS and SPARC systems didn't appear until the late 1980s, they tended to have much larger amounts of memory, and it was assumed that you would use C (or something else).

SPARC and MIPS may have also omitted the multiply instruction in an attempt to make it so the processor could execute one operation per cycle for nearly every instruction.

The successor to the 6502, the 65816 (both of which are still currently available as new parts from WDC) is a lot more compiler-friendly than the 6502, but is still pretty weird by "real" RISC standards.

The 65816 has stack-relative addressing, and a relocatable direct page which can act as a sort of frame pointer, but it's still a far cry from being compiler-friendly. Severe annoyances include the painful lack of registers, having 8 and 16 bit be a global mode switch instead of just specifying the size in the instruction, lack of a barrel shifter, and the near/far pointer distinction. There's a reason why there have never been successful ports of GCC or LLVM to that architecture, even out of tree.

That's a little less true about LLVM. https://llvm-mos.org/wiki/Welcome They seem fairly sure that llvm can be convinced to support a 6502 target.

As for gcc, I'm fairly sure gcc has at least one out-of-tree but yeah perhaps the code wasn't as good as hand rolled.

I know that some retail games for the SNES were written in C, so there are one or two C compilers out there. I'm curious what the history is for 65C816 compilers (besides the one you can get from WDC).

I learned C on a C compiler for the c64.

https://archive.org/details/Super-C_1986_Abacus

The WDC C compiler was originally known as Zardoz C. ORCA/C (For the Apple IIgs) was eventually ported to run on MPW (Macintosh Programmer's Workshop) and used for some SNES development as well. Apple had a C compiler (APW C) for the Apple IIgs and cross development on MPW. 2500 AD Software bought up by Avocet Systems in 1997) had a 65816 C cross compiler as well.

Ancient Land of YS was programmed by me mostly using APW C with assembly used for graphics routines. Thanks for the info on Zardoz. I always wondered what became of it - it was my favorite.

I used Zardoz C to make the original FIFA soccer on the Super Nintendo. Of course there was a lot of hand rolled assembly but a lot of the UI and some parts of the game were written using Zardoz. The ability to use the DP as the base for local variables meant the code generation wasn't too terrible.

For 6502s, Interpreters were much more common, with BASIC of course the most popular. Even ostensibly "compiled" languages often targeted something in between, e.g. UCSD Pascal targeted a virtual machine, and FORTH compiled typically to some sort of jump table.

One of the joys of moving from the 6502 BBC micro to the Acorn Archimedes was the Acorn RISC machine had a multiply. It felt like cheating.

(They used ARM2 which added MUL and MLA - multiply with accumulate)

Yes and no. Regardless of what early RISCs lacked relative to the 6502 (and other contemporaries), they were generally much fast overall, operated on wider words (32 v 8 bit) and had access to vastly larger memories. So there were often analogous workarounds, but different in details. For example, replacing calculating sine with a lookup table is much easier and more accurate when you can toss it someplace in your 16MB or whatever of memory rather than try and shoehorn it into 64k.

The main difference between the ARM1 (which was never sold in any quantity) and the ARM2 was the addition of the multiply instruction (and the multiply and accumulate instruction). They were the only multi-cycle arithmetic operation they had, and what's more you couldn't load arbitrary constants into a register with the MOV instruction or use constants with the multiply instruction itself so they were still a bit inconvenient as well as comparatively slow.

But you could write:

  MOV R1, #3
  MUL R0, R0, R1

In spite of the limitations, this gave the instruction set a certain 68000 quality to it (except much faster for a given clock speed).

To multiply the number in R0 by 3, which was pretty convenient. The ARM had a thing called the barrel shifter though, which let you add an arbitrary shift to the last operand of any arithmetic operation. All arithmetic ops take 1 processor cycle, so you could write this instead to multiply by 3 in a single cycle:

  ADD R0, R0, R0, LSL #1

Ie, add R0 to itself multiplied by 2. Constant divisions could be constructed with the SUB instruction too. Some constants required multiple instructions (but I think the maximum was something like 4 or 5 instructions for any constant? I wrote an assembler that could figure this out for you automatically in the mid-90s so I used to know for sure).

This is basically a single-instruction version of the 6502 trick (handy, because the first OS for the ARM was a hurried port of a 6502 operating system), which sort of fits with the ARM's original inspiration as being a 32-bit version of the 6502. As each instruction completes in one CPU cycle, the ARM could have fairly monstrous integer performance for the mid to late 80s if you knew how to program it.

Forget early RISC, the DEC Alpha didn't have a divide instruction - I only learnt that a few days ago.

This might be of interest…

https://archive.org/details/dr_dobbs_journal_vol_01/page/n20...

Wozniak floating point code.

I thought the whole reason why Apple ended up using a Microsoft BASIC implementation for the Apple II was that Woz didn't write floating-point routines. Am I missing something here?

Apparently he did.

I took an interest due to the C64.

> Easy: Just write the binary equivalent of the constant, and look for the 1 bits

I love that there was a time when "just write the binary equivalent" was the easy solution.

Reply on news.ycombinator.com