# Dividivu.asm

(Difference between revisions)
 Revision as of 20:23, 6 September 2008 (view source)Mr z (Talk | contribs) (→Examples)← Older edit Revision as of 20:29, 6 September 2008 (view source)Mr z (Talk | contribs) (→Notes)Newer edit → Line 19: Line 19: = Notes = = 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.

+ + 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]].

= Source Code = = Source Code =

# Functions Provided

Entry pointFunction providedNotes
DIVIDivide two signed integers / fixed-pt numbersNumerator in register, denominator and fractional point fixed in ROM.
DIVI.1Numerator and denominator in registers, fractional point fixed in ROM.
DIVI.2Numerator, denominator and fractional point in registers.
DIVUDivide two unsigned integers / fixed-pt numbersNumerator in register, denominator and fractional point fixed in ROM.
DIVU.1Numerator and denominator in registers, fractional point fixed in ROM.
DIVU.2Numerator, denominator and fractional point in registers.

See source code below for calling convention.

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

;; ======================================================================== ;;
;;  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                                                      ;;
;;                                                                          ;;
;;  OUTPUTS                                                                 ;;
;;      R0    Remainder, left-shifted                                       ;;
;;      R1    Clobbered                                                     ;;
;;      R2    Clobbered                                                     ;;
;;      R3    Quotient                                                      ;;
;;      R4    Unmodified                                                    ;;
;;                                                                          ;;
;;  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                                              ;;
;; ======================================================================== ;;
```