1 /*
2  * Division and remainder, from Appendix E of the Sparc Version 8
3  * Architecture Manual, with fixes from Gordon Irlam.
4  */
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  */
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
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
75         ', `    DEVELOP_QUOTIENT_BITS(incr(\$1), `eval(2*\$2+1)')')
76 L.\$1.eval(2**N+\$2):
77         ! remainder is negative
79         ifelse(\$1, N,
80         `       b       9f
82         ', `    DEVELOP_QUOTIENT_BITS(incr(\$1), `eval(2*\$2-1)')')
83         ifelse(\$1, 1, `9:')')dnl
85 #include "DEFS.h"
86 #ifdef __svr4__
87 #include <sys/trap.h>
88 #else
89 #include <machine/trap.h>
90 #endif
92 FUNC(NAME)
93 ifelse(S, `true',
94 `       ! compute sign of result; if neither is negative, no problem
95         orcc    divisor, dividend, %g0  ! either negative?
96         bge     2f                      ! no, go do the divide
97 ifelse(OP, `div',
98 `       xor     divisor, dividend, SIGN ! compute sign in any case',
99 `       mov     dividend, SIGN          ! sign of remainder matches dividend')
100         tst     divisor
101         bge     1f
102         tst     dividend
103         ! divisor is definitely negative; dividend might also be negative
104         bge     2f                      ! if dividend not negative...
105         sub     %g0, divisor, divisor   ! in any case, make divisor nonneg
106 1:      ! dividend is negative, divisor is nonnegative
107         sub     %g0, dividend, dividend ! make dividend nonnegative
108 2:
109 ')
110         ! Ready to divide.  Compute size of quotient; scale comparand.
111         orcc    divisor, %g0, V
112         bne     1f
113         mov     dividend, R
115                 ! Divide by zero trap.  If it returns, return 0 (about as
116                 ! wrong as possible, but that is what SunOS does...).
117                 ta      ST_DIV0
118                 retl
119                 clr     %o0
121 1:
122         cmp     R, V                    ! if divisor exceeds dividend, done
123         blu     Lgot_result             ! (and algorithm fails otherwise)
124         clr     Q
125         sethi   %hi(1 << (WORDSIZE - TOPBITS - 1)), T
126         cmp     R, T
127         blu     Lnot_really_big
128         clr     ITER
130         ! `Here the dividend is >= 2**(31-N) or so.  We must be careful here,
131         ! as our usual N-at-a-shot divide step will cause overflow and havoc.
132         ! The number of bits in the result here is N*ITER+SC, where SC <= N.
133         ! Compute ITER in an unorthodox manner: know we need to shift V into
134         ! the top decade: so do not even bother to compare to R.'
135         1:
136                 cmp     V, T
137                 bgeu    3f
138                 mov     1, SC
139                 sll     V, N, V
140                 b       1b
143         ! Now compute SC.
144         2:      addcc   V, V, V
145                 bcc     Lnot_too_big
148                 ! We get here if the divisor overflowed while shifting.
149                 ! This means that R has the high-order bit set.
150                 ! Restore V and subtract from R.
151                 sll     T, TOPBITS, T   ! high order bit
152                 srl     V, 1, V         ! rest of V
154                 b       Ldo_single_div
155                 sub     SC, 1, SC
157         Lnot_too_big:
158         3:      cmp     V, R
159                 blu     2b
160                 nop
161                 be      Ldo_single_div
162                 nop
163         /* NB: these are commented out in the V8-Sparc manual as well */
164         /* (I do not understand this) */
165         ! V > R: went too far: back up 1 step
166         !       srl     V, 1, V
167         !       dec     SC
168         ! do single-bit divide steps
169         !
170         ! We have to be careful here.  We know that R >= V, so we can do the
171         ! first divide step without thinking.  BUT, the others are conditional,
172         ! and are only done if R >= 0.  Because both R and V may have the high-
173         ! order bit set in the first step, just falling into the regular
174         ! division loop will mess up the first time around.
175         ! So we unroll slightly...
176         Ldo_single_div:
177                 subcc   SC, 1, SC
178                 bl      Lend_regular_divide
179                 nop
180                 sub     R, V, R
181                 mov     1, Q
182                 b       Lend_single_divloop
183                 nop
184         Lsingle_divloop:
185                 sll     Q, 1, Q
186                 bl      1f
187                 srl     V, 1, V
188                 ! R >= 0
189                 sub     R, V, R
190                 b       2f
192         1:      ! R < 0
194                 sub     Q, 1, Q
195         2:
196         Lend_single_divloop:
197                 subcc   SC, 1, SC
198                 bge     Lsingle_divloop
199                 tst     R
200                 b,a     Lend_regular_divide
202 Lnot_really_big:
203 1:
204         sll     V, N, V
205         cmp     V, R
206         bleu    1b
208         be      Lgot_result
209         sub     ITER, 1, ITER
211         tst     R       ! set up for initial iteration
212 Ldivloop:
213         sll     Q, N, Q
214         DEVELOP_QUOTIENT_BITS(1, 0)
215 Lend_regular_divide:
216         subcc   ITER, 1, ITER
217         bge     Ldivloop
218         tst     R
219         bl,a    Lgot_result
220         ! non-restoring fixup here (one instruction only!)
221 ifelse(OP, `div',
222 `       sub     Q, 1, Q
223 ', `    add     R, divisor, R
224 ')
226 Lgot_result:
227 ifelse(S, `true',
228 `       ! check to see if answer should be < 0
229         tst     SIGN
230         bl,a    1f
231         ifelse(OP, `div', `sub %g0, Q, Q', `sub %g0, R, R')
232 1:')
233         retl
234         ifelse(OP, `div', `mov Q, %o0', `mov R, %o0')