Difference between revisions of "Fastdivu.asm"

From Intellivision Wiki
Jump to: navigation, search
m (Notes)
(Notes)
Line 17: Line 17:
  
 
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 \>
 
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 \>
 +
 +
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 \>
  
 
= Source Code =
 
= Source Code =

Revision as of 20:28, 6 September 2008


Functions Provided

Entry pointFunction providedNotes
FASTDIVUDivide two unsigned integers / fixed-pt numbersNumerator in register, denominator and fractional point fixed in ROM.
FASTDIVU.1Numerator and denominator in registers, fractional point fixed in ROM.
FASTDIVU.2Numerator, 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                                              ;;
;; ======================================================================== ;;