;* ======================================================================== *;
;*  The routines and data in this file (fastdivu.asm) are dedicated to the  *;
;*  public domain via the Creative Commons CC0 v1.0 license by its author,  *;
;*  Joseph Zbiciak.                                                         *;
;*                                                                          *;
;*          https://creativecommons.org/publicdomain/zero/1.0/              *;
;* ======================================================================== *;

;; ======================================================================== ;;
;;  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                                              ;;
;; ======================================================================== ;;
