Path: news1.icaen!news.uiowa.edu!news1.chicago.cic.net!iagnet.net!204.71.0.61!peerfeed!newsfeed.internetmci.com!arclight.uoregon.edu!platform.uoregon.edu!cie-2.uoregon.edu!nparker
From: nparker@cie-2.uoregon.edu (Neil Parker)
Newsgroups: comp.sys.apple2.programmer
Subject: Re: 32 bit mul & div
Date: 4 Sep 1997 07:10:08 GMT
Organization: University of Oregon Campus Information Exchange
Lines: 125
Message-ID: <5ulmsg$7d3@platform.uoregon.edu>
References: <19970904034300.XAA24485@ladder02.news.aol.com>
NNTP-Posting-Host: cie-2.uoregon.edu
In article Ronald
Kneusel writes:
>Subject says it all. Specifically, I'm looking for 32-bit _signed_
>multiplication and division:
>
>32-bit * 32-bit = 64-bit (or 32-bit ignoring overflow)
>
>32-bit / 32-bit = 32-bit (plus remainder)
>
>I've found 16-bit routines but was wondering if anyone had 32-bit routines
>in 6502 assembly handy.
Here's the 32-bit unsigned division routine. It wants the dividend in
location Q1 (low byte) through Q4 (high byte), and the divisor in locations
D1 through D4. The quotient comes out in locations Q1 through Q4
(replacing the dividend), and the remainder is in locations R1 through R4.
For maximum efficiency, all twelve locations should be on page 0, but this
is not required.
DIV32 LDA #0 ;Init remainder to 0
STA R1
STA R2
STA R3
STA R4
LDX #32 ;Loop over 32 bits
LOOP ASL Q1 ;Shift a bit off the dividend...
ROL Q2
ROL Q3
ROL Q4
ROL R1 ;...and catch it in the remainder
ROL R2
ROL R3
ROL R4
SEC ;Try subtracting divisor from remainder
LDA R1
SBC D1
PHA ;(save result on stack)
LDA R2
SBC D2
PHA
LDA R3
SBC D3
PHA
LDA R4
SBC D4
BCC DISCARD ;Did subtraction succeed?
STA R4 ;If so, result becomes new remainder...
PLA
STA R3
PLA
STA R2
PLA
STA R1
INC Q1 ;...and put a 1 bit in the quotient
BCS NEXT ;(branch always taken)
DISCARD PLA ;Otherwise discard the subtraction
PLA
PLA ;(there's already a 0 bit in the quotient)
NEXT DEX ;Done all 32 bits yet?
BNE LOOP ;If not, go do more
RTS ;Else we're done
And here's the wrapper for doing signed division. This code *does* require
that your memory locations be on page 0.
LDA Q4 ;Save sign of dividend
PHP
EOR D4 ;Compute sign of quotient
PHP
BIT Q4 ;If dividend<0, make it positive
BPL TRYD
LDX #$FC
SEC
NEGQ1 LDA #0
SBC Q4+1,X ;(this only works if Q1..Q4 are on page 0)
STA Q4+1,X
INX
BNE NEGQ1
TRYD BIT D4 ;If divisor<0, make it positive
BPL DODIV
LDX #$FC
SEC
NEGD1 LDA #0
SBC D4+1,X ;(this only works if D1..D4 are on page 0)
STA D4+1,X
INX
BNE NEGD1
DODIV JSR DIV32 ;Do the (unsigned) division
PLP ;If quotient should be <0, make it negative
BPL TRYR
LDX #$FC
SEC
NEGQ2 LDA #0
SBC Q4+1,X ;(this only works if Q1..Q4 are on page 0)
STA Q4+1,X
INX
BNE NEGQ2
TRYR PLP ;Transfer sign of dividend to remainder
BPL DONE
LDX #$FC
SEC
NEGR1 LDA #0
SBC R4+1,X ;(this only works if R1..R4 are on page 0)
STA R4+1,X
INX
BNE NEGR1
DONE RTS
This wrapper implements "toward 0" rounding of signed quotients--that is,
when a negative quotient needs to be rounded, the result closer to 0 is
chosen. The remainder has the sign of the dividend, which guarantees that
the usual division relationship holds:
dividend = quotient*divisor + remainder.
The opposite choice, "floored" rounding (in which the more negative result
is chosen, like Applesoft's INT function), is similar, but requires
slightly different postprocessing of the unsigned result.
- Neil Parker
--
Neil Parker, nparker@{cie-2,cie}.uoregon.edu, http://cie-2.uoregon.edu/~nparker
"Evolution is vastly overrated." -- Ambassador Delenn, _Babylon_5_
Unsolicited commercial e-mail to my address will be discarded unread.