Mr z: Protected "Dividivu.asm" ([edit=autoconfirmed] (indefinite) [move=autoconfirmed] (indefinite))

2010-12-04T08:18:07Z

Protected "Dividivu.asm" ([edit=autoconfirmed] (indefinite) [move=autoconfirmed] (indefinite))

Mr z: /* Functions Provided */

2008-09-06T20:50:10Z

‎Functions Provided

Mr z: /* Notes */

2008-09-06T20:29:00Z

‎Notes

Mr z: /* Examples */

2008-09-06T20:23:42Z

‎Examples

Mr z at 19:49, 6 September 2008

2008-09-06T19:49:18Z

Mr z at 19:37, 6 September 2008

2008-09-06T19:37:36Z

New page

[[Category:Programming]] [[Category:Library]]

= dividivu.asm =

== Functions Provided ==

<CENTER><TABLE BORDER><TR><TH>Entry point</TH><TH>Function provided</TH><TH>Notes</TH></TR>
<TR><TD>DIVI</TD><TD ROWSPAN=3>Divide two signed integers / fixed-pt numbers</TD><TD>Numerator in register, denominator and fractional point fixed in ROM.</TD></TR>
<TR><TD>DIVI.1</TD><TD>Numerator and denominator in registers, fractional point fixed in ROM.</TD></TR>
<TR><TD>DIVI.2</TD><TD>Numerator, denominator and fractional point in registers.</TD></TR>
<TR><TD>DIVU</TD><TD ROWSPAN=3>Divide two unsigned integers / fixed-pt numbers</TD><TD>Numerator in register, denominator and fractional point fixed in ROM.</TD></TR>
<TR><TD>DIVU.1</TD><TD>Numerator and denominator in registers, fractional point fixed in ROM.</TD></TR>
<TR><TD>DIVU.2</TD><TD>Numerator, denominator and fractional point in registers.</TD></TR></TABLE></CENTER>
<br /><br />
See source code below for calling convention.<br /><br />

== Source Code ==

<pre>
;* ======================================================================== *;
;* 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 ;;
;; ======================================================================== ;;
</pre>

@@ Line 19: / Line 19: @@
 = 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 all of your operands are positive and less than 0x8000, you may consider using [[fastdivu.asm]] instead, since it is noticeably faster.<br \><br \>
 = Source Code =

← Older revision		Revision as of 20:23, 6 September 2008
Line 16:		Line 16:

	(todo... please contribute!)		(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.

	= Source Code =		= Source Code =

← Older revision	Revision as of 08:18, 4 December 2010
(No difference)

@@ Line 4: / Line 4: @@
 <CENTER><TABLE BORDER><TR><TH>Entry point</TH><TH>Function provided</TH><TH>Notes</TH></TR>
-<TR><TD>DIVI</TD><TD ROWSPAN=3>Divide two signed integers / fixed-pt numbers</TD><TD>Numerator in register, denominator and fractional point fixed in ROM.</TD></TR>
+<TR><TD>DIVI</TD><TD ROWSPAN=3>Divide two signed integers / [[Fixed Point Arithmetic|fixed-point]] numbers</TD><TD>Numerator in register, denominator and fractional point fixed in ROM.</TD></TR>
 <TR><TD>DIVI.1</TD><TD>Numerator and denominator in registers, fractional point fixed in ROM.</TD></TR>
 <TR><TD>DIVI.2</TD><TD>Numerator, denominator and fractional point in registers.</TD></TR>
-<TR><TD>DIVU</TD><TD ROWSPAN=3>Divide two unsigned integers / fixed-pt numbers</TD><TD>Numerator in register, denominator and fractional point fixed in ROM.</TD></TR>
+<TR><TD>DIVU</TD><TD ROWSPAN=3>Divide two unsigned integers / fixed-point numbers</TD><TD>Numerator in register, denominator and fractional point fixed in ROM.</TD></TR>
 <TR><TD>DIVU.1</TD><TD>Numerator and denominator in registers, fractional point fixed in ROM.</TD></TR>
 <TR><TD>DIVU.2</TD><TD>Numerator, denominator and fractional point in registers.</TD></TR></TABLE></CENTER>