Dividivu.asm
dividivu.asm
Functions Provided
| Entry point | Function provided | Notes |
|---|---|---|
| DIVI | Divide two signed integers / fixed-pt 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-pt 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.
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 ;;
;; ======================================================================== ;;
