sysdeps/sparc/divrem.m4

   1 /*
   2  * Division and remainder, from Appendix E of the Sparc Version 8
   3  * Architecture Manual, with fixes from Gordon Irlam.
   4  */
   5
   6 /*
   7  * Input: dividend and divisor in %o0 and %o1 respectively.
   8  *
   9  * m4 parameters:
  10  *  NAME        name of function to generate
  11  *  OP          OP=div => %o0 / %o1; OP=rem => %o0 % %o1
  12  *  S           S=true => signed; S=false => unsigned
  13  *
  14  * Algorithm parameters:
  15  *  N           how many bits per iteration we try to get (4)
  16  *  WORDSIZE    total number of bits (32)
  17  *
  18  * Derived constants:
  19  *  TOPBITS     number of bits in the top `decade' of a number
  20  *
  21  * Important variables:
  22  *  Q           the partial quotient under development (initially 0)
  23  *  R           the remainder so far, initially the dividend
  24  *  ITER        number of main division loop iterations required;
  25  *              equal to ceil(log2(quotient) / N).  Note that this
  26  *              is the log base (2^N) of the quotient.
  27  *  V           the current comparand, initially divisor*2^(ITER*N-1)
  28  *
  29  * Cost:
  30  *  Current estimate for non-large dividend is
  31  *      ceil(log2(quotient) / N) * (10 + 7N/2) + C
  32  *  A large dividend is one greater than 2^(31-TOPBITS) and takes a
  33  *  different path, as the upper bits of the quotient must be developed
  34  *  one bit at a time.
  35  */
  36
  37 define(N, `4')dnl
  38 define(WORDSIZE, `32')dnl
  39 define(TOPBITS, eval(WORDSIZE - N*((WORDSIZE-1)/N)))dnl
  40 dnl
  41 define(dividend, `%o0')dnl
  42 define(divisor, `%o1')dnl
  43 define(Q, `%o2')dnl
  44 define(R, `%o3')dnl
  45 define(ITER, `%o4')dnl
  46 define(V, `%o5')dnl
  47 dnl
  48 dnl m4 reminder: ifelse(a,b,c,d) => if a is b, then c, else d
  49 define(T, `%g1')dnl
  50 define(SC, `%g7')dnl
  51 ifelse(S, `true', `define(SIGN, `%g6')')dnl
  52
  53 dnl
  54 dnl This is the recursive definition for developing quotient digits.
  55 dnl
  56 dnl Parameters:
  57 dnl  $1 the current depth, 1 <= $1 <= N
  58 dnl  $2 the current accumulation of quotient bits
  59 dnl  N  max depth
  60 dnl
  61 dnl We add a new bit to $2 and either recurse or insert the bits in
  62 dnl the quotient.  R, Q, and V are inputs and outputs as defined above;
  63 dnl the condition codes are expected to reflect the input R, and are
  64 dnl modified to reflect the output R.
  65 dnl
  66 define(DEVELOP_QUOTIENT_BITS,
  67 `       ! depth $1, accumulated bits $2
  68         bl      L.$1.eval(2**N+$2)
  69         srl     V,1,V
  70         ! remainder is positive
  71         subcc   R,V,R
  72         ifelse($1, N,
  73         `       b       9f
  74                 add     Q, ($2*2+1), Q
  75         ', `    DEVELOP_QUOTIENT_BITS(incr($1), `eval(2*$2+1)')')
  76 L.$1.eval(2**N+$2):
  77         ! remainder is negative
  78         addcc   R,V,R
  79         ifelse($1, N,
  80         `       b       9f
  81                 add     Q, ($2*2-1), Q
  82         ', `    DEVELOP_QUOTIENT_BITS(incr($1), `eval(2*$2-1)')')
  83         ifelse($1, 1, `9:')')dnl
  84
  85 #include "sysdep.h"
  86 #ifdef __linux__
  87 #include <asm/traps.h>
  88 #else
  89 #ifdef __svr4__
  90 #include <sys/trap.h>
  91 #else
  92 #include <machine/trap.h>
  93 #endif
  94 #endif
  95
  96 FUNC(NAME)
  97 ifelse(S, `true',
  98 `       ! compute sign of result; if neither is negative, no problem
  99         orcc    divisor, dividend, %g0  ! either negative?
 100         bge     2f                      ! no, go do the divide
 101 ifelse(OP, `div',
 102 `       xor     divisor, dividend, SIGN ! compute sign in any case',
 103 `       mov     dividend, SIGN          ! sign of remainder matches dividend')
 104         tst     divisor
 105         bge     1f
 106         tst     dividend
 107         ! divisor is definitely negative; dividend might also be negative
 108         bge     2f                      ! if dividend not negative...
 109         sub     %g0, divisor, divisor   ! in any case, make divisor nonneg
 110 1:      ! dividend is negative, divisor is nonnegative
 111         sub     %g0, dividend, dividend ! make dividend nonnegative
 112 2:
 113 ')
 114         ! Ready to divide.  Compute size of quotient; scale comparand.
 115         orcc    divisor, %g0, V
 116         bne     1f
 117         mov     dividend, R
 118
 119                 ! Divide by zero trap.  If it returns, return 0 (about as
 120                 ! wrong as possible, but that is what SunOS does...).
 121                 ta      ST_DIV0
 122                 retl
 123                 clr     %o0
 124
 125 1:
 126         cmp     R, V                    ! if divisor exceeds dividend, done
 127         blu     Lgot_result             ! (and algorithm fails otherwise)
 128         clr     Q
 129         sethi   %hi(1 << (WORDSIZE - TOPBITS - 1)), T
 130         cmp     R, T
 131         blu     Lnot_really_big
 132         clr     ITER
 133
 134         ! `Here the dividend is >= 2**(31-N) or so.  We must be careful here,
 135         ! as our usual N-at-a-shot divide step will cause overflow and havoc.
 136         ! The number of bits in the result here is N*ITER+SC, where SC <= N.
 137         ! Compute ITER in an unorthodox manner: know we need to shift V into
 138         ! the top decade: so do not even bother to compare to R.'
 139         1:
 140                 cmp     V, T
 141                 bgeu    3f
 142                 mov     1, SC
 143                 sll     V, N, V
 144                 b       1b
 145                 add     ITER, 1, ITER
 146
 147         ! Now compute SC.
 148         2:      addcc   V, V, V
 149                 bcc     Lnot_too_big
 150                 add     SC, 1, SC
 151
 152                 ! We get here if the divisor overflowed while shifting.
 153                 ! This means that R has the high-order bit set.
 154                 ! Restore V and subtract from R.
 155                 sll     T, TOPBITS, T   ! high order bit
 156                 srl     V, 1, V         ! rest of V
 157                 add     V, T, V
 158                 b       Ldo_single_div
 159                 sub     SC, 1, SC
 160
 161         Lnot_too_big:
 162         3:      cmp     V, R
 163                 blu     2b
 164                 nop
 165                 be      Ldo_single_div
 166                 nop
 167         /* NB: these are commented out in the V8-Sparc manual as well */
 168         /* (I do not understand this) */
 169         ! V > R: went too far: back up 1 step
 170         !       srl     V, 1, V
 171         !       dec     SC
 172         ! do single-bit divide steps
 173         !
 174         ! We have to be careful here.  We know that R >= V, so we can do the
 175         ! first divide step without thinking.  BUT, the others are conditional,
 176         ! and are only done if R >= 0.  Because both R and V may have the high-
 177         ! order bit set in the first step, just falling into the regular
 178         ! division loop will mess up the first time around.
 179         ! So we unroll slightly...
 180         Ldo_single_div:
 181                 subcc   SC, 1, SC
 182                 bl      Lend_regular_divide
 183                 nop
 184                 sub     R, V, R
 185                 mov     1, Q
 186                 b       Lend_single_divloop
 187                 nop
 188         Lsingle_divloop:
 189                 sll     Q, 1, Q
 190                 bl      1f
 191                 srl     V, 1, V
 192                 ! R >= 0
 193                 sub     R, V, R
 194                 b       2f
 195                 add     Q, 1, Q
 196         1:      ! R < 0
 197                 add     R, V, R
 198                 sub     Q, 1, Q
 199         2:
 200         Lend_single_divloop:
 201                 subcc   SC, 1, SC
 202                 bge     Lsingle_divloop
 203                 tst     R
 204                 b,a     Lend_regular_divide
 205
 206 Lnot_really_big:
 207 1:
 208         sll     V, N, V
 209         cmp     V, R
 210         bleu    1b
 211         addcc   ITER, 1, ITER
 212         be      Lgot_result
 213         sub     ITER, 1, ITER
 214
 215         tst     R       ! set up for initial iteration
 216 Ldivloop:
 217         sll     Q, N, Q
 218         DEVELOP_QUOTIENT_BITS(1, 0)
 219 Lend_regular_divide:
 220         subcc   ITER, 1, ITER
 221         bge     Ldivloop
 222         tst     R
 223         bl,a    Lgot_result
 224         ! non-restoring fixup here (one instruction only!)
 225 ifelse(OP, `div',
 226 `       sub     Q, 1, Q
 227 ', `    add     R, divisor, R
 228 ')
 229
 230 Lgot_result:
 231 ifelse(S, `true',
 232 `       ! check to see if answer should be < 0
 233         tst     SIGN
 234         bl,a    1f
 235         ifelse(OP, `div', `sub %g0, Q, Q', `sub %g0, R, R')
 236 1:')
 237         retl
 238         ifelse(OP, `div', `mov Q, %o0', `mov R, %o0')