Dividivu.asm
Functions Provided
| Entry point | Function provided | Notes |
|---|---|---|
| DIVI | Divide two signed integers / fixed-point numbers | Numerator in register, denominator and fractional point fixed in ROM. |
| DIVI.1 | Numerator and denominator in registers, fractional point fixed in ROM. | |
| DIVI.2 | Numerator, denominator and fractional point in registers. | |
| DIVU | Divide two unsigned integers / fixed-point numbers | Numerator in register, denominator and fractional point fixed in ROM. |
| DIVU.1 | Numerator and denominator in registers, fractional point fixed in ROM. | |
| DIVU.2 | Numerator, denominator and fractional point in registers. |
See source code below for calling convention.
Examples
(todo... please contribute!)
Notes
If all of your operands are positive and less than 0x8000, you may consider using fastdivu.asm instead, since it is noticeably faster.
If you are dividing by a power of 2, consider using shifts instead.
Source Code
;* ======================================================================== *;
;* These routines are placed into the public domain by their author. All *;
;* copyright rights are hereby relinquished on the routines and data in *;
;* this file. -- Joseph Zbiciak, 2008 *;
;* ======================================================================== *;
;; ======================================================================== ;;
;; DIVI Divide two signed integers / fixed-pt numbers ;;
;; DIVI.1 Alternate entry point: denominator in register ;;
;; DIVI.2 Alternate entry point: all parameters in registers ;;
;; DIVU Divide two unsigned integers / fixed-pt numbers ;;
;; DIVU.1 Alternate entry point: denominator in register ;;
;; DIVU.2 Alternate entry point: all parameters in registers ;;
;; ;;
;; AUTHOR ;;
;; Joseph Zbiciak <intvnut AT gmail.com> ;;
;; ;;
;; REVISION HISTORY ;;
;; 25-Sep-2001 Initial Revision ;;
;; 27-Sep-2001 Rewrote normalization, shaving ~150 cycles. ;;
;; ;;
;; INPUTS for DIVI, DIVU ;;
;; R0 Numerator ;;
;; R5 Pointer to invocation record, followed by return address. ;;
;; Denominator 1 DECLE ;;
;; Fractional point 1 DECLE ;;
;; ;;
;; INPUTS for DIVI.1, DIVU.1 ;;
;; R0 Numerator ;;
;; R1 Denominator ;;
;; R5 Pointer to invocation record, followed by return address. ;;
;; Fractional point 1 DECLE ;;
;; ;;
;; INPUTS for DIVI.2, DIVU.2 ;;
;; R0 Numerator ;;
;; R1 Denominator ;;
;; R2 Fraction ;;
;; R5 Return address ;;
;; ;;
;; OUTPUTS ;;
;; R0 Remainder, left-shifted ;;
;; R1 Clobbered ;;
;; R2 Clobbered ;;
;; R3 Quotient ;;
;; R4 Unmodified ;;
;; R5 Return address ;;
;; ;;
;; NOTES ;;
;; The remainder returned in R0 isn't directly usable. This code ;;
;; can be modified to return a proper remainder by recording the ;;
;; number of left-shifts applied to the denominator in the norm ;;
;; loop, and applying that number of right-shifts to the remainder. ;;
;; Storing R2 after the normalization loop works for integer ;;
;; division (fractional point == 0) only. ;;
;; ;;
;; This code can perform fixed-point divide between two fixed point ;;
;; numbers, yielding a fixed-point result. Given the numerator's ;;
;; fractional point X, the denominator's fractional point Y, and ;;
;; the desired fractional point Z, the required argument F for ;;
;; this divide is: F = Z + Y - X. ;;
;; ;;
;; This divide rounds towards zero. In other words, for signed ;;
;; division, both -1/2 == 0 and 1/2 == 0. For unsigned division, ;;
;; all remainders are rounded down. ;;
;; ;;
;; TECHNIQUES ;;
;; Left-shifting method on numerator allows calculating fractional ;;
;; quotients as well as integer quotients. ;;
;; ;;
;; Negative numerators and denominators are handled by making both ;;
;; numerator and denominator positive up-front, and then negating ;;
;; the result if necessary. (This step is obviously omitted in the ;;
;; case of an unsigned divide.) ;;
;; ;;
;; CODESIZE ;;
;; 72 words. ;;
;; ;;
;; 6 words may be shaved by omitting DIVU. ;;
;; 20 words may be shaved by omitting DIVI. ;;
;; ;;
;; CYCLES ;;
;; Worst case analysis: ;;
;; ;;
;; For DIVI, cycles = 601 + 53*k, where k is # of quotient bits. ;;
;; For DIVU, cycles = 552 + 53*k, where k is # of quotient bits. ;;
;; The number of quotient bits 'k' is given by this equation: ;;
;; ;;
;; k = ceil(log2(num)) - floor(log2(den)) + fractional_bits. ;;
;; ;;
;; Subtract 8 cycles for DIVI.1 or DIVU.1. ;;
;; Subtract 16 cycles for DIVI.2 or DIVU.2. ;;
;; ;;
;; A worst-case divide with 16 quotient bits that are all 1s should ;;
;; take no more than 1448 cycles. (The actual cycle count will ;;
;; depend on the relative magnitude of the numbers being divided.) ;;
;; ;;
;; ======================================================================== ;;
DIVU PROC
MVI@ R5, R1 ; 8 Denominator
@@1: MVI@ R5, R2 ; 8 Fractional point
@@2: ; Alt. entry: All args in regs
CLRR R3 ; 6 Start w/ quotient == 0.
PSHR R3 ; 9 Sign of result == positive
B DIVI.norm ; 9 Reuse divi code for divide
;======
; 40
ENDP
DIVI PROC
MVI@ R5, R1 ; 8 Denominator
@@1: MVI@ R5, R2 ; 8 Fractional point
@@2: ; Alt. entry: All args in regs
CLRR R3 ; 6 Start w/ quotient == 0.
;; ------------------------------------------------------------ ;;
;; Record sign of result, and make num, den positive. ;;
;; ------------------------------------------------------------ ;;
XORR R1, R0 ; 6 \
PSHR R0 ; 9 |-- Record sign of result
XORR R1, R0 ; 6 / on the stack.
TSTR R0 ; 6 \
BEQ @@zero ; 7/9 |__ Make numerator positive
BPL @@npos ; 7/9 |
NEGR R0 ; 6 /
@@npos:
TSTR R1 ; 6 \
BEQ @@zero ; 7/9 |__ Make denominator positive
BPL @@dpos ; 7/9 |
NEGR R1 ; 6 /
@@dpos: ;------
; 95 (worst case: both negative)
; 87 (typical: both positive)
; 58 (best case: numerator zero)
;======
; 95 (worst case: both negative)
;; ------------------------------------------------------------ ;;
;; Normalize the divisor relative to the dividend. We want ;;
;; to shift the denominator left as far as we can without ;;
;; making it larger than the numerator. We achieve this by ;;
;; shifting it one position too far, then backing off. ;;
;; ------------------------------------------------------------ ;;
@@norm: TSTR R1 ; 6 Is bit 15 of denominator set?
BMI @@norm3 ; 7/9 Yes: Do very special norm.
TSTR R0 ; 6 Is bit 15 of numerator set?
BPL @@norm1 ; 9/7 If not, do general normalize.
; Otherwise, do special normalize.
@@norm2: INCR R2 ; 6 \
SLLC R1, 1 ; 6 |-- Special normalize: Shift
BNC @@norm2 ; 9/7 / until bit falls off top.
;------
; 21*k - 2
B @@over ; 9
; 26
;------
; 21*k + 20
;====== Assume max K of 16
; 369 (worst case)
@@norm1: INCR R2 ; 6 \
SLL R1, 1 ; 6 |-- General normalize: Shift
CMPR R1, R0 ; 6 / until denom > numer.
BC @@norm1 ; 9/7
;------
; 27*k - 2
; 28
;====== Assume max K of 15
; 431 (worst case)
@@over: RRC R1, 1 ; 6 Back off by one.
INCR PC ; 6 Skip INCR below
@@norm3: INCR R2 ; 6 Very special norm...
CMPR R3, R2 ; 6 Is our divide loop iter count
; at least 1? (Note R3==0)
BLE @@zero ; 7/9 NO: Return zero.
B @@div1st ; 9 Do first iter of divide
;------
; 34 (worst case)
; 95 (worst case)
; 431 (worst case)
;======
; 560 (worst case)
;; ------------------------------------------------------------ ;;
;; Perform the divide. We iteratively subtract off our ;;
;; divisor from the dividend *IF* the dividend is greater or ;;
;; or equal to the divisor, and set the corresponding bit in ;;
;; the quotient. If the dividend is smaller than the divisor, ;;
;; we clear the corresponding quotient bit. Next, we left- ;;
;; shift the dividend and calculate the next quotient bit. ;;
;; ------------------------------------------------------------ ;;
@@div: SLLC R0, 1 ; 6 Shift numerator left 1
BC @@b1 ; 7/9 If overflow, force bit 1.
@@div1st: CMPR R1, R0 ; 6 Is numerator >= denominator ?
BNC @@b0 ; 7/9 NO: Quotient bit is 0
@@b1: RLC R3, 1 ; 6 YES: Quotient bit is 1
SUBR R1, R0 ; 6
DECR R2 ; 6
BNEQ @@div ; 9/7 Iterate for all quotient bits
;------
; 53*k - 2
B @@divdone ; 9
;------
; 53*k + 7
@@b0: SLL R3, 1 ; 6 NO: Quotient bit is 0
DECR R2 ; 6
BNEQ @@div ; 9/7 Iterate for all quotient bits
;------
; 49*k - 2
;======
; 567 + 53*k worst case.
@@divdone:
;; ------------------------------------------------------------ ;;
;; Now apply the sign to the result. The sign is in the MSB ;;
;; of the word we saved earlier on the stack. For unsigned ;;
;; divides, the value saved on the stack is zero. ;;
;; ------------------------------------------------------------ ;;
@@zero: PULR R1 ; 8
TSTR R1 ; 6
BPL @@qpos ; 7/9
NEGR R3 ; 6
@@qpos: ;------
; 27 (worst case)
; 567 + 53*k (worst case)
;======
; 594 + 53*k (worst case)
@@done: JR R5 ; 7 Return. R3 = R0 / R1
;======
; 601 + 53*k (worst case)
ENDP
;; ======================================================================== ;;
;; End of File: dividivu.asm ;;
;; ======================================================================== ;;
