http://wiki.intellivision.us/index.php?title=Fastdivu.asm&feed=atom&action=history
Fastdivu.asm - Revision history
2024-03-29T11:03:27Z
Revision history for this page on the wiki
MediaWiki 1.30.0
http://wiki.intellivision.us/index.php?title=Fastdivu.asm&diff=14786&oldid=prev
Mr z: Protected "Fastdivu.asm" ([edit=autoconfirmed] (indefinite) [move=autoconfirmed] (indefinite))
2010-12-04T08:21:02Z
<p>Protected "<a href="/index.php/Fastdivu.asm" title="Fastdivu.asm">Fastdivu.asm</a>" ([edit=autoconfirmed] (indefinite) [move=autoconfirmed] (indefinite))</p>
<table class="diff diff-contentalign-left" data-mw="interface">
<tr style="vertical-align: top;" lang="en">
<td colspan="1" style="background-color: white; color:black; text-align: center;">← Older revision</td>
<td colspan="1" style="background-color: white; color:black; text-align: center;">Revision as of 08:21, 4 December 2010</td>
</tr><tr><td colspan="2" style="text-align: center;" lang="en"><div class="mw-diff-empty">(No difference)</div>
</td></tr></table>
Mr z
http://wiki.intellivision.us/index.php?title=Fastdivu.asm&diff=2947&oldid=prev
Mr z: /* Functions Provided */
2008-09-06T20:51:00Z
<p><span dir="auto"><span class="autocomment">Functions Provided</span></span></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr style="vertical-align: top;" lang="en">
<td colspan="2" style="background-color: white; color:black; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: white; color:black; text-align: center;">Revision as of 20:51, 6 September 2008</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l4" >Line 4:</td>
<td colspan="2" class="diff-lineno">Line 4:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><CENTER><TABLE BORDER><TR><TH>Entry point</TH><TH>Function provided</TH><TH>Notes</TH></TR></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><CENTER><TABLE BORDER><TR><TH>Entry point</TH><TH>Function provided</TH><TH>Notes</TH></TR></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><TR><TD>FASTDIVU</TD><TD ROWSPAN=3>Divide two unsigned integers / fixed-<del class="diffchange diffchange-inline">pt </del>numbers</TD><TD>Numerator in register, denominator and fractional point fixed in ROM.</TD></TR></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><TR><TD>FASTDIVU</TD><TD ROWSPAN=3>Divide two unsigned integers / <ins class="diffchange diffchange-inline">[[Fixed Point Arithmetic|</ins>fixed-<ins class="diffchange diffchange-inline">point]] </ins>numbers</TD><TD>Numerator in register, denominator and fractional point fixed in ROM.</TD></TR></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><TR><TD>FASTDIVU.1</TD><TD>Numerator and denominator in registers, fractional point fixed in ROM.</TD></TR></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><TR><TD>FASTDIVU.1</TD><TD>Numerator and denominator in registers, fractional point fixed in ROM.</TD></TR></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><TR><TD>FASTDIVU.2</TD><TD>Numerator, denominator and fractional point in registers.</TD></TR></TABLE></CENTER></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><TR><TD>FASTDIVU.2</TD><TD>Numerator, denominator and fractional point in registers.</TD></TR></TABLE></CENTER></div></td></tr>
</table>
Mr z
http://wiki.intellivision.us/index.php?title=Fastdivu.asm&diff=2941&oldid=prev
Mr z: /* Notes */
2008-09-06T20:28:57Z
<p><span dir="auto"><span class="autocomment">Notes</span></span></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr style="vertical-align: top;" lang="en">
<td colspan="2" style="background-color: white; color:black; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: white; color:black; text-align: center;">Revision as of 20:28, 6 September 2008</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l17" >Line 17:</td>
<td colspan="2" class="diff-lineno">Line 17:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>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.<br \><br \></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>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.<br \><br \></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">If you are dividing by a power of 2, consider [[Introducing_the_Instruction_Set_Part_4#Using_Shifts_for_Division_by_Powers_of_Two|using shifts instead]].<br \><br \></ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>= Source Code =</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>= Source Code =</div></td></tr>
</table>
Mr z
http://wiki.intellivision.us/index.php?title=Fastdivu.asm&diff=2940&oldid=prev
Mr z: /* Notes */
2008-09-06T20:26:47Z
<p><span dir="auto"><span class="autocomment">Notes</span></span></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr style="vertical-align: top;" lang="en">
<td colspan="2" style="background-color: white; color:black; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: white; color:black; text-align: center;">Revision as of 20:26, 6 September 2008</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l16" >Line 16:</td>
<td colspan="2" class="diff-lineno">Line 16:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>= Notes =</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>= Notes =</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>If you need more general divide functionality, please use [[dividivu.asm]] instead.</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">This function requires both numerator and denominator to be positive and less than 0x8000.  </ins>If you need more general divide functionality, please use [[dividivu.asm]] instead.<ins class="diffchange diffchange-inline"><br \><br \></ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>= Source Code =</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>= Source Code =</div></td></tr>
</table>
Mr z
http://wiki.intellivision.us/index.php?title=Fastdivu.asm&diff=2939&oldid=prev
Mr z at 20:25, 6 September 2008
2008-09-06T20:25:19Z
<p></p>
<p><b>New page</b></p><div>[[Category:Programming]] [[Category:Library]]<br />
<br />
= Functions Provided =<br />
<br />
<CENTER><TABLE BORDER><TR><TH>Entry point</TH><TH>Function provided</TH><TH>Notes</TH></TR><br />
<TR><TD>FASTDIVU</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><br />
<TR><TD>FASTDIVU.1</TD><TD>Numerator and denominator in registers, fractional point fixed in ROM.</TD></TR><br />
<TR><TD>FASTDIVU.2</TD><TD>Numerator, denominator and fractional point in registers.</TD></TR></TABLE></CENTER><br />
<br /><br /><br />
See source code below for calling convention.<br /><br /><br />
<br />
= Examples =<br />
<br />
(todo... please contribute!)<br />
<br />
= Notes =<br />
<br />
If you need more general divide functionality, please use [[dividivu.asm]] instead.<br />
<br />
= Source Code =<br />
<br />
<pre><br />
;* ======================================================================== *;<br />
;* These routines are placed into the public domain by their author. All *;<br />
;* copyright rights are hereby relinquished on the routines and data in *;<br />
;* this file. -- Joseph Zbiciak, 2008 *;<br />
;* ======================================================================== *;<br />
<br />
;; ======================================================================== ;;<br />
;; FASTDIVU Divide two unsigned integers / fixed-pt numbers ;;<br />
;; FASTDIVU.1 Alternate entry point: denominator in register ;;<br />
;; FASTDIVU.2 Alternate entry point: all parameters in registers ;;<br />
;; ;;<br />
;; AUTHOR ;;<br />
;; Joseph Zbiciak <intvnut AT gmail.com> ;;<br />
;; ;;<br />
;; REVISION HISTORY ;;<br />
;; 27-Sep-2001 Wrote fast version, shaving another ~200 cycles. ;;<br />
;; ;;<br />
;; INPUTS for FASTDIVU ;;<br />
;; R0 Numerator ;;<br />
;; R5 Pointer to invocation record, followed by return address. ;;<br />
;; Denominator 1 DECLE ;;<br />
;; Fractional point 1 DECLE ;;<br />
;; ;;<br />
;; INPUTS for FASTDIVU.1 ;;<br />
;; R0 Numerator ;;<br />
;; R1 Denominator ;;<br />
;; R5 Pointer to invocation record, followed by return address. ;;<br />
;; Fractional point 1 DECLE ;;<br />
;; ;;<br />
;; INPUTS for FASTDIVU.2 ;;<br />
;; R0 Numerator ;;<br />
;; R1 Denominator ;;<br />
;; R2 Fraction ;;<br />
;; R5 Return address ;;<br />
;; ;;<br />
;; OUTPUTS ;;<br />
;; R0 Remainder, left-shifted ;;<br />
;; R1 Clobbered ;;<br />
;; R2 Clobbered ;;<br />
;; R3 Quotient ;;<br />
;; R4 Unmodified ;;<br />
;; R5 Return address ;;<br />
;; ;;<br />
;; NOTES ;;<br />
;; Both numerator and denominator MUST be positive, and less than ;;<br />
;; 0x8000. This code may loop indefinitely if this is not heeded. ;;<br />
;; ;;<br />
;; The remainder returned in R0 isn't directly usable. This code ;;<br />
;; can be modified to return a proper remainder by recording the ;;<br />
;; number of left-shifts applied to the denominator in the norm ;;<br />
;; loop, and applying that number of right-shifts to the remainder. ;;<br />
;; Storing R2 after the normalization loop works for integer ;;<br />
;; division (fractional point == 0) only. ;;<br />
;; ;;<br />
;; This code can perform fixed-point divide between two fixed point ;;<br />
;; numbers, yielding a fixed-point result. Given the numerator's ;;<br />
;; fractional point X, the denominator's fractional point Y, and ;;<br />
;; the desired fractional point Z, the required argument F for ;;<br />
;; this divide is: F = Z + Y - X. ;;<br />
;; ;;<br />
;; This divide rounds towards zero. All remainders are rounded down. ;;<br />
;; ;;<br />
;; TECHNIQUES ;;<br />
;; Left-shifting method on numerator allows calculating fractional ;;<br />
;; quotients as well as integer quotients. ;;<br />
;; ;;<br />
;; CODESIZE ;;<br />
;; 28 words ;;<br />
;; ;;<br />
;; CYCLES ;;<br />
;; Worst case analysis: ;;<br />
;; ;;<br />
;; For FASTDIVU, cycles = 456 + 46*k, where k is # of quotient bits. ;;<br />
;; The number of quotient bits 'k' is given by this equation: ;;<br />
;; ;;<br />
;; k = ceil(log2(num)) - floor(log2(den)) + fractional_bits. ;;<br />
;; ;;<br />
;; Subtract 8 cycles for FASTDIVU.1. ;;<br />
;; Subtract 16 cycles for FASTDIVU.2. ;;<br />
;; ;;<br />
;; A worst-case divide with 15 quotient bits should take no more ;;<br />
;; than 1146 cycles. (The actual cycle count will depend on the ;;<br />
;; relative magnitude of the numbers being divided.) ;;<br />
;; ;;<br />
;; ======================================================================== ;;<br />
FASTDIVU PROC <br />
<br />
MVI@ R5, R1 ; 8 Denominator<br />
@@1: MVI@ R5, R2 ; 8 Fractional point<br />
@@2: ; Alt. entry: All args in regs <br />
CLRR R3 ; 6 Start w/ quotient == 0.<br />
;----<br />
; 22<br />
<br />
;; ------------------------------------------------------------ ;;<br />
;; Normalize the divisor relative to the dividend. We want ;;<br />
;; to shift the denominator left as far as we can without ;;<br />
;; making it larger than the numerator. We achieve this by ;;<br />
;; shifting it one position too far, then backing off. ;;<br />
;; ------------------------------------------------------------ ;;<br />
<br />
@@norm: INCR R2 ; 6 \<br />
SLL R1, 1 ; 6 |-- General normalize: Shift<br />
CMPR R1, R0 ; 6 / until denom > numer.<br />
BC @@norm ; 9/7<br />
;------<br />
; 27*k - 2<br />
; 22 <br />
;------<br />
; 27*k + 20<br />
;====== Assume max K of 15<br />
; 425 (worst case)<br />
<br />
<br />
@@over: SLR R1, 1 ; 6 Back off by one. <br />
CMPR R3, R2 ; 6 Is our divide loop iter count<br />
; at least 1? (Note R3==0)<br />
BLE @@zero ; 7/9 NO: Return zero.<br />
INCR PC ; 7 Do first iter of divide<br />
;------<br />
; 26 (worst case)<br />
; 425 (worst case)<br />
;====== <br />
; 451 (worst case)<br />
<br />
;; ------------------------------------------------------------ ;;<br />
;; Perform the divide. We iteratively subtract off our ;;<br />
;; divisor from the dividend *IF* the dividend is greater or ;;<br />
;; or equal to the divisor, and set the corresponding bit in ;;<br />
;; the quotient. If the dividend is smaller than the divisor, ;;<br />
;; we clear the corresponding quotient bit. Next, we left- ;;<br />
;; shift the dividend and calculate the next quotient bit. ;;<br />
;; ------------------------------------------------------------ ;;<br />
<br />
@@div: SLL R0, 1 ; 6 Shift numerator left 1<br />
@@div1st: CMPR R1, R0 ; 6 Is numerator >= denominator ?<br />
BNC @@b0 ; 7/9 NO: Quotient bit is 0<br />
<br />
@@b1: RLC R3, 1 ; 6 YES: Quotient bit is 1<br />
SUBR R1, R0 ; 6<br />
DECR R2 ; 6<br />
BNEQ @@div ; 9/7 Iterate for all quotient bits<br />
;------<br />
; 46*k - 2<br />
@@zero: JR R5 ; 7 Return!<br />
; 451<br />
;======<br />
; 456 + 46*k worst case.<br />
<br />
@@b0: SLL R3, 1 ; 6 NO: Quotient bit is 0<br />
DECR R2 ; 6<br />
BNEQ @@div ; 9/7 Iterate for all quotient bits<br />
;------<br />
; 42*k - 2<br />
@@done: JR R5 ; 7 Return!<br />
; 451<br />
;======<br />
; 456 + 42*k <br />
<br />
ENDP <br />
<br />
;; ======================================================================== ;;<br />
;; End of File: fastdivu.asm ;;<br />
;; ======================================================================== ;;<br />
</pre></div>
Mr z