Fastdivu.asm
Functions Provided
| Entry point | Function provided | Notes |
|---|---|---|
| FASTDIVU | Divide two unsigned integers / fixed-point numbers | Numerator in register, denominator and fractional point fixed in ROM. |
| FASTDIVU.1 | Numerator and denominator in registers, fractional point fixed in ROM. | |
| FASTDIVU.2 | Numerator, denominator and fractional point in registers. |
See source code below for calling convention.
Examples
(todo... please contribute!)
Notes
This function requires both numerator and denominator to be positive and less than 0x8000. If you need more general divide functionality, please use dividivu.asm instead.
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 *;
;* ======================================================================== *;
;; ======================================================================== ;;
;; FASTDIVU Divide two unsigned integers / fixed-pt numbers ;;
;; FASTDIVU.1 Alternate entry point: denominator in register ;;
;; FASTDIVU.2 Alternate entry point: all parameters in registers ;;
;; ;;
;; AUTHOR ;;
;; Joseph Zbiciak <intvnut AT gmail.com> ;;
;; ;;
;; REVISION HISTORY ;;
;; 27-Sep-2001 Wrote fast version, shaving another ~200 cycles. ;;
;; ;;
;; INPUTS for FASTDIVU ;;
;; R0 Numerator ;;
;; R5 Pointer to invocation record, followed by return address. ;;
;; Denominator 1 DECLE ;;
;; Fractional point 1 DECLE ;;
;; ;;
;; INPUTS for FASTDIVU.1 ;;
;; R0 Numerator ;;
;; R1 Denominator ;;
;; R5 Pointer to invocation record, followed by return address. ;;
;; Fractional point 1 DECLE ;;
;; ;;
;; INPUTS for FASTDIVU.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 ;;
;; Both numerator and denominator MUST be positive, and less than ;;
;; 0x8000. This code may loop indefinitely if this is not heeded. ;;
;; ;;
;; 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. All remainders are rounded down. ;;
;; ;;
;; TECHNIQUES ;;
;; Left-shifting method on numerator allows calculating fractional ;;
;; quotients as well as integer quotients. ;;
;; ;;
;; CODESIZE ;;
;; 28 words ;;
;; ;;
;; CYCLES ;;
;; Worst case analysis: ;;
;; ;;
;; For FASTDIVU, cycles = 456 + 46*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 FASTDIVU.1. ;;
;; Subtract 16 cycles for FASTDIVU.2. ;;
;; ;;
;; A worst-case divide with 15 quotient bits should take no more ;;
;; than 1146 cycles. (The actual cycle count will depend on the ;;
;; relative magnitude of the numbers being divided.) ;;
;; ;;
;; ======================================================================== ;;
FASTDIVU 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.
;----
; 22
;; ------------------------------------------------------------ ;;
;; 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: INCR R2 ; 6 \
SLL R1, 1 ; 6 |-- General normalize: Shift
CMPR R1, R0 ; 6 / until denom > numer.
BC @@norm ; 9/7
;------
; 27*k - 2
; 22
;------
; 27*k + 20
;====== Assume max K of 15
; 425 (worst case)
@@over: SLR R1, 1 ; 6 Back off by one.
CMPR R3, R2 ; 6 Is our divide loop iter count
; at least 1? (Note R3==0)
BLE @@zero ; 7/9 NO: Return zero.
INCR PC ; 7 Do first iter of divide
;------
; 26 (worst case)
; 425 (worst case)
;======
; 451 (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: SLL R0, 1 ; 6 Shift numerator left 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
;------
; 46*k - 2
@@zero: JR R5 ; 7 Return!
; 451
;======
; 456 + 46*k worst case.
@@b0: SLL R3, 1 ; 6 NO: Quotient bit is 0
DECR R2 ; 6
BNEQ @@div ; 9/7 Iterate for all quotient bits
;------
; 42*k - 2
@@done: JR R5 ; 7 Return!
; 451
;======
; 456 + 42*k
ENDP
;; ======================================================================== ;;
;; End of File: fastdivu.asm ;;
;; ======================================================================== ;;
