divrem.m4 revision 1.2 1 /* $NetBSD: divrem.m4,v 1.2 2002/10/27 18:41:27 chs Exp $ */
2
3 /*
4 * Copyright (c) 1992, 1993
5 * The Regents of the University of California. All rights reserved.
6 *
7 * This software was developed by the Computer Systems Engineering group
8 * at Lawrence Berkeley Laboratory under DARPA contract BG 91-66 and
9 * contributed to Berkeley.
10 *
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
13 * are met:
14 * 1. Redistributions of source code must retain the above copyright
15 * notice, this list of conditions and the following disclaimer.
16 * 2. Redistributions in binary form must reproduce the above copyright
17 * notice, this list of conditions and the following disclaimer in the
18 * documentation and/or other materials provided with the distribution.
19 * 3. All advertising materials mentioning features or use of this software
20 * must display the following acknowledgement:
21 * This product includes software developed by the University of
22 * California, Berkeley and its contributors.
23 * 4. Neither the name of the University nor the names of its contributors
24 * may be used to endorse or promote products derived from this software
25 * without specific prior written permission.
26 *
27 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
28 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
29 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
30 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
31 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
32 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
33 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
34 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
35 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
36 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
37 * SUCH DAMAGE.
38 *
39 * from: Header: divrem.m4,v 1.4 92/06/25 13:23:57 torek Exp
40 */
41
42 /*
43 * Division and remainder, from Appendix E of the Sparc Version 8
44 * Architecture Manual, with fixes from Gordon Irlam.
45 */
46
47 #if defined(LIBC_SCCS)
48 RCSID("$NetBSD: divrem.m4,v 1.2 2002/10/27 18:41:27 chs Exp $")
49 #endif
50
51 /*
52 * Input: dividend and divisor in %o0 and %o1 respectively.
53 *
54 * m4 parameters:
55 * NAME name of function to generate
56 * OP OP=div => %o0 / %o1; OP=rem => %o0 % %o1
57 * S S=true => signed; S=false => unsigned
58 *
59 * Algorithm parameters:
60 * N how many bits per iteration we try to get (4)
61 * WORDSIZE total number of bits (32)
62 *
63 * Derived constants:
64 * TWOSUPN 2^N, for label generation (m4 exponentiation currently broken)
65 * TOPBITS number of bits in the top `decade' of a number
66 *
67 * Important variables:
68 * Q the partial quotient under development (initially 0)
69 * R the remainder so far, initially the dividend
70 * ITER number of main division loop iterations required;
71 * equal to ceil(log2(quotient) / N). Note that this
72 * is the log base (2^N) of the quotient.
73 * V the current comparand, initially divisor*2^(ITER*N-1)
74 *
75 * Cost:
76 * Current estimate for non-large dividend is
77 * ceil(log2(quotient) / N) * (10 + 7N/2) + C
78 * A large dividend is one greater than 2^(31-TOPBITS) and takes a
79 * different path, as the upper bits of the quotient must be developed
80 * one bit at a time.
81 */
82
83 define(N, `4')
84 define(TWOSUPN, `16')
85 define(WORDSIZE, `32')
86 define(TOPBITS, eval(WORDSIZE - N*((WORDSIZE-1)/N)))
87
88 define(dividend, `%o0')
89 define(divisor, `%o1')
90 define(Q, `%o2')
91 define(R, `%o3')
92 define(ITER, `%o4')
93 define(V, `%o5')
94
95 /* m4 reminder: ifelse(a,b,c,d) => if a is b, then c, else d */
96 define(T, `%g1')
97 define(SC, `%g5')
98 ifelse(S, `true', `define(SIGN, `%g6')')
99
100 /*
101 * This is the recursive definition for developing quotient digits.
102 *
103 * Parameters:
104 * $1 the current depth, 1 <= $1 <= N
105 * $2 the current accumulation of quotient bits
106 * N max depth
107 *
108 * We add a new bit to $2 and either recurse or insert the bits in
109 * the quotient. R, Q, and V are inputs and outputs as defined above;
110 * the condition codes are expected to reflect the input R, and are
111 * modified to reflect the output R.
112 */
113 define(DEVELOP_QUOTIENT_BITS,
114 ` ! depth $1, accumulated bits $2
115 bl L.$1.eval(TWOSUPN+$2)
116 srl V,1,V
117 ! remainder is positive
118 subcc R,V,R
119 ifelse($1, N,
120 ` b 9f
121 add Q, ($2*2+1), Q
122 ', ` DEVELOP_QUOTIENT_BITS(incr($1), `eval(2*$2+1)')')
123 L.$1.eval(TWOSUPN+$2):
124 ! remainder is negative
125 addcc R,V,R
126 ifelse($1, N,
127 ` b 9f
128 add Q, ($2*2-1), Q
129 ', ` DEVELOP_QUOTIENT_BITS(incr($1), `eval(2*$2-1)')')
130 ifelse($1, 1, `9:')')
131
132 #include <machine/asm.h>
133 #include <machine/trap.h>
134
135 FUNC(NAME)
136 ifelse(S, `true',
137 ` ! compute sign of result; if neither is negative, no problem
138 orcc divisor, dividend, %g0 ! either negative?
139 bge 2f ! no, go do the divide
140 ifelse(OP, `div',
141 `xor divisor, dividend, SIGN',
142 `mov dividend, SIGN') ! compute sign in any case
143 tst divisor
144 bge 1f
145 tst dividend
146 ! divisor is definitely negative; dividend might also be negative
147 bge 2f ! if dividend not negative...
148 neg divisor ! in any case, make divisor nonneg
149 1: ! dividend is negative, divisor is nonnegative
150 neg dividend ! make dividend nonnegative
151 2:
152 ')
153 ! Ready to divide. Compute size of quotient; scale comparand.
154 orcc divisor, %g0, V
155 bnz 1f
156 mov dividend, R
157
158 ! Divide by zero trap. If it returns, return 0 (about as
159 ! wrong as possible, but that is what SunOS does...).
160 t ST_DIV0
161 retl
162 clr %o0
163
164 1:
165 cmp R, V ! if divisor exceeds dividend, done
166 blu Lgot_result ! (and algorithm fails otherwise)
167 clr Q
168 sethi %hi(1 << (WORDSIZE - TOPBITS - 1)), T
169 cmp R, T
170 blu Lnot_really_big
171 clr ITER
172
173 ! `Here the dividend is >= 2^(31-N) or so. We must be careful here,
174 ! as our usual N-at-a-shot divide step will cause overflow and havoc.
175 ! The number of bits in the result here is N*ITER+SC, where SC <= N.
176 ! Compute ITER in an unorthodox manner: know we need to shift V into
177 ! the top decade: so do not even bother to compare to R.'
178 1:
179 cmp V, T
180 bgeu 3f
181 mov 1, SC
182 sll V, N, V
183 b 1b
184 inc ITER
185
186 ! Now compute SC.
187 2: addcc V, V, V
188 bcc Lnot_too_big
189 inc SC
190
191 ! We get here if the divisor overflowed while shifting.
192 ! This means that R has the high-order bit set.
193 ! Restore V and subtract from R.
194 sll T, TOPBITS, T ! high order bit
195 srl V, 1, V ! rest of V
196 add V, T, V
197 b Ldo_single_div
198 dec SC
199
200 Lnot_too_big:
201 3: cmp V, R
202 blu 2b
203 nop
204 be Ldo_single_div
205 nop
206 /* NB: these are commented out in the V8-Sparc manual as well */
207 /* (I do not understand this) */
208 ! V > R: went too far: back up 1 step
209 ! srl V, 1, V
210 ! dec SC
211 ! do single-bit divide steps
212 !
213 ! We have to be careful here. We know that R >= V, so we can do the
214 ! first divide step without thinking. BUT, the others are conditional,
215 ! and are only done if R >= 0. Because both R and V may have the high-
216 ! order bit set in the first step, just falling into the regular
217 ! division loop will mess up the first time around.
218 ! So we unroll slightly...
219 Ldo_single_div:
220 deccc SC
221 bl Lend_regular_divide
222 nop
223 sub R, V, R
224 mov 1, Q
225 b Lend_single_divloop
226 nop
227 Lsingle_divloop:
228 sll Q, 1, Q
229 bl 1f
230 srl V, 1, V
231 ! R >= 0
232 sub R, V, R
233 b 2f
234 inc Q
235 1: ! R < 0
236 add R, V, R
237 dec Q
238 2:
239 Lend_single_divloop:
240 deccc SC
241 bge Lsingle_divloop
242 tst R
243 b,a Lend_regular_divide
244
245 Lnot_really_big:
246 1:
247 sll V, N, V
248 cmp V, R
249 bleu 1b
250 inccc ITER
251 be Lgot_result
252 dec ITER
253
254 tst R ! set up for initial iteration
255 Ldivloop:
256 sll Q, N, Q
257 DEVELOP_QUOTIENT_BITS(1, 0)
258 Lend_regular_divide:
259 deccc ITER
260 bge Ldivloop
261 tst R
262 bl,a Lgot_result
263 ! non-restoring fixup here (one instruction only!)
264 ifelse(OP, `div',
265 ` dec Q
266 ', ` add R, divisor, R
267 ')
268
269 Lgot_result:
270 ifelse(S, `true',
271 ` ! check to see if answer should be < 0
272 tst SIGN
273 bl,a 1f
274 ifelse(OP, `div', `neg Q', `neg R')
275 1:')
276 retl
277 ifelse(OP, `div', `mov Q, %o0', `mov R, %o0')
278