The routine as presented divides a 15-bit unsigned dividend by a 15-bit unsigned divisor yielding a 15-bit unsigned quotient and 15-bit unsigned remainder. It is fairly trivial to produce a wrapper routine that handles 16-bit signed dividends and divisors yielding 16-bit signed quotients and remainders. That can also be the place where division by zero is handled.
First, a C implementation of the algorithm. I have tested this version by comparing its results to the results of the C '/' and '%' operators for all valid values of dividend and divisor:
Code: Select all
uint16_t uquotient;
uint16_t uremainder;
/*
unsigned divide
The largest possible multiples of the the divisor by a power of 2
are subtracted from the dividend and the corresponding partial quotients
(the powers of 2 by which the divisor is multiplied) are added to the
quotient. Whatever is leftover is the remainder.
*/
void udiv(uint16_t dividend, uint16_t divisor)
{
uint16_t partial_quotient = 1;
uquotient = 0;
// double the divisor until it exceeds the dividend. this is ok
// because the divisor and dividend are no more than 15 bits long
while (divisor < dividend) {
divisor <<= 1;
partial_quotient <<= 1;
}
while (1) {
// halve the divisor until it is less than the dividend
// this yields the largest multiple of the divisor by a power of 2
// that can be subtracted from the dividend with a positive difference
while (dividend < divisor) {
divisor >>= 1;
partial_quotient >>= 1;
if (partial_quotient == 0) goto done;
}
// subtract the multiple of the divisor from the dividend and add
// the corresponding power of 2 (partial quotient) to the quotient
dividend -= divisor;
uquotient += partial_quotient;
}
done:
uremainder = dividend;
}
Code: Select all
rmdr
dend ds 2
dsor ds 2
quot ds 2
pquo ds 2
udiv lda #1
sta pquo
lda #0
sta pquo+1
sta quot
sta quot+1
;; double the divisor until it exceeds the dividend. this is ok
;; because the divisor and dividend are no more than 15 bits long
L0 lda dsor+1
cmp dend+1
bcc L1
bne L2
lda dsor
cmp dend
bcs L2
L1 asl dsor
rol dsor+1
asl pquo
rol pquo+1
jmp L0
;; halve the divisor until it is less than the dividend
;; this yields the largest multiple of the divisor by a power of 2
;; that can be subtracted from the dividend with a positive difference
L2 lda dend+1
cmp dsor+1
bcc L3
bne L4
lda dend
cmp dsor
bcs L4
L3 lsr dsor+1
ror dsor
lsr pquo+1
ror pquo
bne L2
lda pquo+1
bne L2
rts
;; subtract the multiple of the divisor from the dividend and add
;; the corresponding power of 2 (partial quotient) to the quotient
L4 sec
lda dend
sbc dsor
sta dend
lda dend+1
sbc dsor+1
sta dend+1
clc
lda pquo
adc quot
sta quot
lda pquo+1
adc quot+1
sta quot+1
jmp L2
It’s based on an algorithm that was presented by Lance Leventhal in his first edition of 6502 Assembly Language Programming, and includes a division-by-zero check. With simple modifications, 24-bit and larger quantities may be processed.
