; FILENAME: LDIV.S
; DESCRIPTION: Long unsigned divide using
only one 32 bit CPU register and
;
a bit-wise long division.
;
Written in 1993 by COSMIC (France)
;
Divide routine (see label divide:) rewritten
; AUTHOR: James
Wiebe
; DATE:
Monday, August 7, 1995
;
; - 1st operand, dividend in E:D, 2nd
operand, divisor, pointed to by Z
; - result returned in E:D
;had put t_ for "test" in front of user hook names
.public c_ldiv, c_lmod
.public c_ludv, c_lumd
;
; unsigned modulus
;
c_lumd:
pshm k,y,x
; save Y,X
ais #-12
; more room
tsy
; address stack
bset 1,y,#255 ;
flag for remainder
bra unext ; go ahead
;
; signed modulus
;
c_lmod:
pshm k,y,x
; save Y,X
ais #-16
; more room
tsy
; address stack
ste 0,y ; sign of result
bset 1,y,#255 ;
flag for remainder
bra next ;
go ahead
;
; unsigned division
;
c_ludv:
pshm k,y,x
; save Y,X
ais #-12
; more room
tsy
; address stack
clr 1,y ; flag for quotient
unext:
bsr divide ; common division
ais #12
; clean up stack
pulm k,y,x
; restore Y,X
rts
; and return
;
; signed division
;
c_ldiv:
pshm k,y,x
; save Y,X
ais #-16
; more room
tsy
; address stack
ste 0,y ; sign of result
clr 1,y ; flag for quotient
next:
tste
; test sign
bpl sok1 ;
positive, ok
come
; otherwise
negd
; invert
bne sok1
adde #1
sok1:
ste 2,y ; in place
std 4,y
ldd 2,z ; load divisor
lde 0,z
bpl sok2 ;
positive ok
com 0,y ; sign of result
come
; invert
negd
; long word
bne sok2
adde #1
sok2:
tyz
; divisor addressed by Z
aiz #12
ste 0,z ; in memory
std 2,z
lde 2,y
; restore dividend for divide -- JW
ldd 4,y
bsr divide ; common division
tst 0,y ; sign of result
bpl sok3
come
; invert
negd
bne sok3
adde #1
sok3:
ais #16
; clean up stack
pulm k,y,x
; restore Y,X
rts
; and return
; ***********************************************************************
; *SUBROUTINE: DIVIDE
; *
; *inputs: Dividend, ie Numerator
(N) in E:D
; *
Divisor (S) pointed to by Z
; *
Flag for quotient or remainder in 1(Y)
; *
; *register and memory use:
; *
Working (W) register and remainder in E:D.
; *
Quotient at 2(Y) and 4(Y) on stack.
; *
Numerator at 6(Y) and 8(Y) for working purposes.
; *
Loop counter at 10(Y).
; *
; *outputs: Quotient or remainder in
E:D, as flagged by mainline
; *
; *notes: H/LOW stands
for High/Low Order Word
; *
W is for intermediate stages in the long division algorithm;
; *
becomes the remainder (R).
; *
; ***********************************************************************
divide:
clrw 2,y ;clear
up some space for the quotient
clrw 4,y ;
lots and lots of space (32 bits needed)
; break down problem into cases of
0 HOWs (and LOWs where applicable)
tstw 0,z
bne big_s ;HOW of
divisor has to be used
; S HOW is 0
tstw 2,z ;S
LOW
bne small_s
rts
;S LOW is 0 -- return due to 0 divisor
small_s:
;divide by 16 bits
ldx 2,z
;get S LOW for non0_n (idiv) and big_n (ediv) below
tste
;N HOW
bne big_n
; N HOW is 0
tstd
;N LOW
bne non0_n
; whole N is 0 -- Q already cleared
above
; clear remainder -- will go in e:d,
but e:d is already 0 due to 0 N
jmp doneld ;return with
Q <- 0, R <- 0
non0_n:
;do 16 bit by 16 bit divide
idiv
stx 4,y
;make a 32-bit quotient
; e is already 0, for a 32 bit remainder
jmp doneld
big_n:
;small S -- do 32 bit by 16 bit divide
; save N on the stack in case we still
need it
ste 6,y
std 8,y
ediv
;damn -- have to handle > 16 bit quotients specially.
bvc it_fit
; quotient larger than 16 bits -- restore
operands
lde 6,y
;only put in memory for full problem
ldd 8,y
; divisor pointed to by z (x was changed)
bra fullprob ;we have the full problem
with S less than 16 bits.
it_fit:
;the quotient is less than 16 bits
stx 4,y
;make a 32-bit quotient
clre
;remainder will always be less than S, all in d.
bra doneld
big_s:
; definitely divide by
more than 16 bits -- don't need to test S LOW.
; now break the problem
down into how HOWs compare
cpe 0,z
;HOWs
bcc n_gte ;use for
unsigned greater than or equal
; here N HOW < S HOW, so Q is 0, R is
N; stays in e:d; Q all set.
bra doneld ;takes care
of case in which N is zero
n_gte:
;N greater than or equal to S
bhi fullprob ;we have the full problem
with N > S, both > 16 bits
; here N HOW = S HOW, so we have to
look at the LOWs.
cpd 2,z
bcc lowNgte
; here N LOW < S LOW so Q is 0,
R is N; stays in e:d; Q all set.
bra doneld
lowNgte:
;N greater than or equal to S by only the LOW
bhi lowNgt
; here N LOW = S LOW, so Q=1, R is
0
incw 4,y ;make
Q=1
clre
;set R to 0
clrd
bra doneld
lowNgt:
; here N LOW > S LOW with equal
HOWs, so Q=1, R=N-S
incw 4,y ;make
Q equal to 1
subd 2,z ;only
the LOWs differ.
clre
;clear HOW of Remainder
bra doneld
fullprob:
; here we use E:D for W, a working
register for the intermediate long
; division steps.
; 6(Y) and 8(Y) will hold N
; we shift N into W and see if it is
big enough for S. If it is, we shift
; a 1 into Q. Otherwise, we leave the
0 that we shifted into Q.
; when we are done, W (E:D) will hold
R.
ste 6,y
std 8,y
; iterate 32 times: use 10(Y) as a
loop counter
clra
adda #32
staa 10,y ;set up
loop counter byte
clre
;set up Work register
clrd
long_div:
dec 10,y
aslw 4,y ;open
up bit position in Q
rolw 2,y
aslw 8,y ;take
advantage of the carry bit to cross word boundary
rolw 6,y ;carry
bit will go to W
rold
;bit into W
role
; is S <= W ?
cpe 0,z
;HOWs
bhi subastep ;W is greater than S
in the HOWs -- subtr.
beq cpWS_LOW ;have to compare LOWs
; W is less than S in the HOWs, check
to see if branches are done
bra tst32shf
cpWS_LOW:
cpd 2,z
;LOWs
bhi subastep ;W is greater than S
in the LOWs -- subtr.
beq zero_W ;if equal,
new W is zero
; W is less than S in the LOWs, check
to see if branches are done.
bra tst32shf
zero_W:
clre
clrd
incw 4,y ;S
went into W (just) -- set LObit in Q
bra tst32shf
subastep:
;subract S from W
subd 2,z
sbce 0,z ;use
the carry to subtract the borrow if necessary
incw 4,y ;S
went into W -- set LObit of Q
tst32shf:
tst 10,y ;done
if zero
bgt long_div ;if done, don't branch
back
doneld:
;remainder is naturally in E:D, Q in memory.
tst 1,y
; which called for, quo or rem?
bne rem
lde 2,y
; if quo, load it
ldd 4,y
rem:
rts
;
.end
back
Here's the pseudo-code:
FILENAME: LUDVS.TXT
(S for shift)
DESCRIPTION: Pseudo-code long unsigned
divide using only one 32 bit
CPU register and a bit-wise long division.
AUTHOR:
Jim Wiebe
DATE:
Monday, August 7, 1995
Assumptions: only one 32 bit CPU register
can
do 32 bit compare to memory
can
do 16 bit subtract from 32 bit
Variables: Dividend
N Working register W (will become R)
Divisor
S Shifts
F
Quotient
Q
Remainder
R
(Note that the letter O is not
used as a variable anywhere in
this pseudo-code,
so if you see a symbol like it, it's a zero.
'0' is zero and 'O'
is the letter, and they look only slightly
different in
my editor)
if S = 0 then
signal a divide-by-zero error
else if N = 0 then
Q <- 0
R <- 0
else if N = S then
Q <- 1
R <- 0
else if N < S then
Q <- 0
R <- N
else
* At this point, dividend is
greater than divisor
if N <= 64K-1 then
Q <- N/S
* 16 bit divide
R <- rem(N/S)
* -- we have this instruction
else if S <= 64K-1 then
Q <- N/S
* 32 bit divide by 16 bits.
R <- rem(N/S)
* -- we have this instruction, too.
else
* N and S are each larger
than 16 bits
* results of this: Q will
always be 16 bits or less here
* therefore, we can right
away shift left by 16 bits before beginning
* so, put HO 16 bits of
N into W right away, and shift out only
* LO 16 bits, or word,
of N into W. F is 16 right away.
* only W and R, the final
remainder may be greater than 16 bits,
* because the divisor
is greater than 16 bits.
* the only 32 bit register
we need is for W.
Q <- 0
F <- 16
W <- high order word
of N
N <- low order word
of N
begin until loop
begin until loop
shift N left
into W
shift 0 (zero)
left into Q
F <- F
+ 1
until W >= S
or F = 32
if W >= S then
W <- W
- S
LOBit of Q
<- 1
until F = 32
R <- W
back
First posted Oct 14, 2003