[HN Gopher] Multiplying and Dividing on the 6502 (2021)
___________________________________________________________________
Multiplying and Dividing on the 6502 (2021)
Author : ibobev
Score : 70 points
Date : 2022-06-28 18:59 UTC (4 hours ago)
(HTM) web link (llx.com)
(TXT) w3m dump (llx.com)
| OnlyMortal wrote:
| This might be of interest...
|
| https://archive.org/details/dr_dobbs_journal_vol_01/page/n20...
|
| Wozniak floating point code.
| jacquesm wrote:
| 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
| ddingus wrote:
| 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.
| kbelder wrote:
| 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.
| ddingus wrote:
| 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!
| krylon wrote:
| 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?
| shellac wrote:
| 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)
| logicalshift wrote:
| 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.
| kevin_thibedeau wrote:
| Hardware mul/div is still not universal on new products.
| sophacles wrote:
| 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?
| cbm-vic-20 wrote:
| 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.
| kjs3 wrote:
| 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?
| dietrichepp wrote:
| 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.
| cbm-vic-20 wrote:
| 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.
| dietrichepp wrote:
| 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).
| kbelder wrote:
| I learned C on a C compiler for the c64.
|
| https://archive.org/details/Super-C_1986_Abacus
| ksherlock wrote:
| 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.
| pcwalton wrote:
| 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.
| adamius wrote:
| 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.
| microtherion wrote:
| 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.
| Turing_Machine wrote:
| There were numerous compilers for the 6502.
| kjs3 wrote:
| 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?
| buescher wrote:
| 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.
| dwheeler wrote:
| 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/
| buescher wrote:
| 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.
| sllabres wrote:
| 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. :)
| kjs3 wrote:
| 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.
| diydsp wrote:
| > (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
| djmips wrote:
| My contribution there. :)
|
| https://codebase64.org/doku.php?id=base:8bit_multiplication_...
| kstrauser wrote:
| 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'!
___________________________________________________________________
(page generated 2022-06-28 23:01 UTC)