Commit | Line | Data |
---|---|---|
ad787160 C |
1 | |
2 | /* | |
3 | * Copyright (c) 1992, 1993 | |
4 | * The Regents of the University of California. All rights reserved. | |
5 | * | |
6 | * This software was developed by the Computer Systems Engineering group | |
7 | * at Lawrence Berkeley Laboratory under DARPA contract BG 91-66 and | |
8 | * contributed to Berkeley. | |
9 | * | |
10 | * Redistribution and use in source and binary forms, with or without | |
11 | * modification, are permitted provided that the following conditions | |
12 | * are met: | |
13 | * 1. Redistributions of source code must retain the above copyright | |
14 | * notice, this list of conditions and the following disclaimer. | |
15 | * 2. Redistributions in binary form must reproduce the above copyright | |
16 | * notice, this list of conditions and the following disclaimer in the | |
17 | * documentation and/or other materials provided with the distribution. | |
18 | * 3. All advertising materials mentioning features or use of this software | |
19 | * must display the following acknowledgement: | |
20 | * This product includes software developed by the University of | |
21 | * California, Berkeley and its contributors. | |
22 | * 4. Neither the name of the University nor the names of its contributors | |
23 | * may be used to endorse or promote products derived from this software | |
24 | * without specific prior written permission. | |
25 | * | |
26 | * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS `AS IS' AND | |
27 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
28 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | |
29 | * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE | |
30 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | |
31 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | |
32 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |
33 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | |
34 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | |
35 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | |
36 | * SUCH DAMAGE. | |
37 | * | |
38 | * from: $Header: divrem.m4,v 1.4 92/06/25 13:23:57 torek Exp $ | |
39 | */ | |
40 | ||
41 | /* | |
42 | * Division and remainder, from Appendix E of the Sparc Version 8 | |
43 | * Architecture Manual, with fixes from Gordon Irlam. | |
44 | */ | |
45 | ||
46 | #if defined(LIBC_SCCS) && !defined(lint) | |
47 | .asciz "@(#)divrem.m4 8.1 (Berkeley) 6/4/93" | |
48 | #endif /* LIBC_SCCS and not lint */ | |
49 | ||
50 | /* | |
51 | * Input: dividend and divisor in %o0 and %o1 respectively. | |
52 | * | |
53 | * m4 parameters: | |
54 | * .div name of function to generate | |
55 | * div div=div => %o0 / %o1; div=rem => %o0 % %o1 | |
56 | * true true=true => signed; true=false => unsigned | |
57 | * | |
58 | * Algorithm parameters: | |
59 | * N how many bits per iteration we try to get (4) | |
60 | * WORDSIZE total number of bits (32) | |
61 | * | |
62 | * Derived constants: | |
63 | * TWOSUPN 2^N, for label generation (m4 exponentiation currently broken) | |
64 | * TOPBITS number of bits in the top decade of a number | |
65 | * | |
66 | * Important variables: | |
67 | * Q the partial quotient under development (initially 0) | |
68 | * R the remainder so far, initially the dividend | |
69 | * ITER number of main division loop iterations required; | |
70 | * equal to ceil(log2(quotient) / N). Note that this | |
71 | * is the log base (2^N) of the quotient. | |
72 | * V the current comparand, initially divisor*2^(ITER*N-1) | |
73 | * | |
74 | * Cost: | |
75 | * Current estimate for non-large dividend is | |
76 | * ceil(log2(quotient) / N) * (10 + 7N/2) + C | |
77 | * A large dividend is one greater than 2^(31-TOPBITS) and takes a | |
78 | * different path, as the upper bits of the quotient must be developed | |
79 | * one bit at a time. | |
80 | */ | |
81 | ||
82 | ||
83 | ||
84 | ||
85 | ||
86 | ||
87 | ||
88 | ||
89 | ||
90 | ||
91 | ||
92 | ||
93 | ||
94 | /* m4 reminder: d => if a is b, then c, else d */ | |
95 | ||
96 | ||
97 | ||
98 | ||
99 | /* | |
100 | * This is the recursive definition for developing quotient digits. | |
101 | * | |
102 | * Parameters: | |
103 | * $1 the current depth, 1 <= $1 <= 4 | |
104 | * $2 the current accumulation of quotient bits | |
105 | * 4 max depth | |
106 | * | |
107 | * We add a new bit to $2 and either recurse or insert the bits in | |
108 | * the quotient. %o3, %o2, and %o5 are inputs and outputs as defined above; | |
109 | * the condition codes are expected to reflect the input %o3, and are | |
110 | * modified to reflect the output %o3. | |
111 | */ | |
112 | ||
113 | ||
114 | #include "DEFS.h" | |
115 | #include <machine/trap.h> | |
116 | ||
117 | FUNC(.div) | |
118 | ! compute sign of result; if neither is negative, no problem | |
119 | orcc %o1, %o0, %g0 ! either negative? | |
120 | bge 2f ! no, go do the divide | |
121 | xor %o1, %o0, %g6 ! compute sign in any case | |
122 | tst %o1 | |
123 | bge 1f | |
124 | tst %o0 | |
125 | ! %o1 is definitely negative; %o0 might also be negative | |
126 | bge 2f ! if %o0 not negative... | |
127 | neg %o1 ! in any case, make %o1 nonneg | |
128 | 1: ! %o0 is negative, %o1 is nonnegative | |
129 | neg %o0 ! make %o0 nonnegative | |
130 | 2: | |
131 | ||
132 | ! Ready to divide. Compute size of quotient; scale comparand. | |
133 | orcc %o1, %g0, %o5 | |
134 | bnz 1f | |
135 | mov %o0, %o3 | |
136 | ||
137 | ! Divide by zero trap. If it returns, return 0 (about as | |
138 | ! wrong as possible, but that is what SunOS does...). | |
139 | t ST_DIV0 | |
140 | retl | |
141 | clr %o0 | |
142 | ||
143 | 1: | |
144 | cmp %o3, %o5 ! if %o1 exceeds %o0, done | |
145 | blu Lgot_result ! (and algorithm fails otherwise) | |
146 | clr %o2 | |
147 | sethi %hi(1 << (32 - 4 - 1)), %g1 | |
148 | cmp %o3, %g1 | |
149 | blu Lnot_really_big | |
150 | clr %o4 | |
151 | ||
152 | ! Here the dividend is >= 2^(31-N) or so. We must be careful here, | |
153 | ! as our usual N-at-a-shot divide step will cause overflow and havoc. | |
154 | ! The number of bits in the result here is N*ITER+SC, where SC <= N. | |
155 | ! Compute ITER in an unorthodox manner: know we need to shift V into | |
156 | ! the top decade: so do not even bother to compare to R. | |
157 | 1: | |
158 | cmp %o5, %g1 | |
159 | bgeu 3f | |
160 | mov 1, %g7 | |
161 | sll %o5, 4, %o5 | |
162 | b 1b | |
163 | inc %o4 | |
164 | ||
165 | ! Now compute %g7. | |
166 | 2: addcc %o5, %o5, %o5 | |
167 | bcc Lnot_too_big | |
168 | inc %g7 | |
169 | ||
170 | ! We get here if the %o1 overflowed while shifting. | |
171 | ! This means that %o3 has the high-order bit set. | |
172 | ! Restore %o5 and subtract from %o3. | |
173 | sll %g1, 4, %g1 ! high order bit | |
174 | srl %o5, 1, %o5 ! rest of %o5 | |
175 | add %o5, %g1, %o5 | |
176 | b Ldo_single_div | |
177 | dec %g7 | |
178 | ||
179 | Lnot_too_big: | |
180 | 3: cmp %o5, %o3 | |
181 | blu 2b | |
182 | nop | |
183 | be Ldo_single_div | |
184 | nop | |
185 | /* NB: these are commented out in the V8-Sparc manual as well */ | |
186 | /* (I do not understand this) */ | |
187 | ! %o5 > %o3: went too far: back up 1 step | |
188 | ! srl %o5, 1, %o5 | |
189 | ! dec %g7 | |
190 | ! do single-bit divide steps | |
191 | ! | |
192 | ! We have to be careful here. We know that %o3 >= %o5, so we can do the | |
193 | ! first divide step without thinking. BUT, the others are conditional, | |
194 | ! and are only done if %o3 >= 0. Because both %o3 and %o5 may have the high- | |
195 | ! order bit set in the first step, just falling into the regular | |
196 | ! division loop will mess up the first time around. | |
197 | ! So we unroll slightly... | |
198 | Ldo_single_div: | |
199 | deccc %g7 | |
200 | bl Lend_regular_divide | |
201 | nop | |
202 | sub %o3, %o5, %o3 | |
203 | mov 1, %o2 | |
204 | b Lend_single_divloop | |
205 | nop | |
206 | Lsingle_divloop: | |
207 | sll %o2, 1, %o2 | |
208 | bl 1f | |
209 | srl %o5, 1, %o5 | |
210 | ! %o3 >= 0 | |
211 | sub %o3, %o5, %o3 | |
212 | b 2f | |
213 | inc %o2 | |
214 | 1: ! %o3 < 0 | |
215 | add %o3, %o5, %o3 | |
216 | dec %o2 | |
217 | 2: | |
218 | Lend_single_divloop: | |
219 | deccc %g7 | |
220 | bge Lsingle_divloop | |
221 | tst %o3 | |
222 | b,a Lend_regular_divide | |
223 | ||
224 | Lnot_really_big: | |
225 | 1: | |
226 | sll %o5, 4, %o5 | |
227 | cmp %o5, %o3 | |
228 | bleu 1b | |
229 | inccc %o4 | |
230 | be Lgot_result | |
231 | dec %o4 | |
232 | ||
233 | tst %o3 ! set up for initial iteration | |
234 | Ldivloop: | |
235 | sll %o2, 4, %o2 | |
236 | ! depth 1, accumulated bits 0 | |
237 | bl L.1.16 | |
238 | srl %o5,1,%o5 | |
239 | ! remainder is positive | |
240 | subcc %o3,%o5,%o3 | |
241 | ! depth 2, accumulated bits 1 | |
242 | bl L.2.17 | |
243 | srl %o5,1,%o5 | |
244 | ! remainder is positive | |
245 | subcc %o3,%o5,%o3 | |
246 | ! depth 3, accumulated bits 3 | |
247 | bl L.3.19 | |
248 | srl %o5,1,%o5 | |
249 | ! remainder is positive | |
250 | subcc %o3,%o5,%o3 | |
251 | ! depth 4, accumulated bits 7 | |
252 | bl L.4.23 | |
253 | srl %o5,1,%o5 | |
254 | ! remainder is positive | |
255 | subcc %o3,%o5,%o3 | |
256 | b 9f | |
257 | add %o2, (7*2+1), %o2 | |
258 | ||
259 | L.4.23: | |
260 | ! remainder is negative | |
261 | addcc %o3,%o5,%o3 | |
262 | b 9f | |
263 | add %o2, (7*2-1), %o2 | |
264 | ||
265 | ||
266 | L.3.19: | |
267 | ! remainder is negative | |
268 | addcc %o3,%o5,%o3 | |
269 | ! depth 4, accumulated bits 5 | |
270 | bl L.4.21 | |
271 | srl %o5,1,%o5 | |
272 | ! remainder is positive | |
273 | subcc %o3,%o5,%o3 | |
274 | b 9f | |
275 | add %o2, (5*2+1), %o2 | |
276 | ||
277 | L.4.21: | |
278 | ! remainder is negative | |
279 | addcc %o3,%o5,%o3 | |
280 | b 9f | |
281 | add %o2, (5*2-1), %o2 | |
282 | ||
283 | ||
284 | ||
285 | L.2.17: | |
286 | ! remainder is negative | |
287 | addcc %o3,%o5,%o3 | |
288 | ! depth 3, accumulated bits 1 | |
289 | bl L.3.17 | |
290 | srl %o5,1,%o5 | |
291 | ! remainder is positive | |
292 | subcc %o3,%o5,%o3 | |
293 | ! depth 4, accumulated bits 3 | |
294 | bl L.4.19 | |
295 | srl %o5,1,%o5 | |
296 | ! remainder is positive | |
297 | subcc %o3,%o5,%o3 | |
298 | b 9f | |
299 | add %o2, (3*2+1), %o2 | |
300 | ||
301 | L.4.19: | |
302 | ! remainder is negative | |
303 | addcc %o3,%o5,%o3 | |
304 | b 9f | |
305 | add %o2, (3*2-1), %o2 | |
306 | ||
307 | ||
308 | L.3.17: | |
309 | ! remainder is negative | |
310 | addcc %o3,%o5,%o3 | |
311 | ! depth 4, accumulated bits 1 | |
312 | bl L.4.17 | |
313 | srl %o5,1,%o5 | |
314 | ! remainder is positive | |
315 | subcc %o3,%o5,%o3 | |
316 | b 9f | |
317 | add %o2, (1*2+1), %o2 | |
318 | ||
319 | L.4.17: | |
320 | ! remainder is negative | |
321 | addcc %o3,%o5,%o3 | |
322 | b 9f | |
323 | add %o2, (1*2-1), %o2 | |
324 | ||
325 | ||
326 | ||
327 | ||
328 | L.1.16: | |
329 | ! remainder is negative | |
330 | addcc %o3,%o5,%o3 | |
331 | ! depth 2, accumulated bits -1 | |
332 | bl L.2.15 | |
333 | srl %o5,1,%o5 | |
334 | ! remainder is positive | |
335 | subcc %o3,%o5,%o3 | |
336 | ! depth 3, accumulated bits -1 | |
337 | bl L.3.15 | |
338 | srl %o5,1,%o5 | |
339 | ! remainder is positive | |
340 | subcc %o3,%o5,%o3 | |
341 | ! depth 4, accumulated bits -1 | |
342 | bl L.4.15 | |
343 | srl %o5,1,%o5 | |
344 | ! remainder is positive | |
345 | subcc %o3,%o5,%o3 | |
346 | b 9f | |
347 | add %o2, (-1*2+1), %o2 | |
348 | ||
349 | L.4.15: | |
350 | ! remainder is negative | |
351 | addcc %o3,%o5,%o3 | |
352 | b 9f | |
353 | add %o2, (-1*2-1), %o2 | |
354 | ||
355 | ||
356 | L.3.15: | |
357 | ! remainder is negative | |
358 | addcc %o3,%o5,%o3 | |
359 | ! depth 4, accumulated bits -3 | |
360 | bl L.4.13 | |
361 | srl %o5,1,%o5 | |
362 | ! remainder is positive | |
363 | subcc %o3,%o5,%o3 | |
364 | b 9f | |
365 | add %o2, (-3*2+1), %o2 | |
366 | ||
367 | L.4.13: | |
368 | ! remainder is negative | |
369 | addcc %o3,%o5,%o3 | |
370 | b 9f | |
371 | add %o2, (-3*2-1), %o2 | |
372 | ||
373 | ||
374 | ||
375 | L.2.15: | |
376 | ! remainder is negative | |
377 | addcc %o3,%o5,%o3 | |
378 | ! depth 3, accumulated bits -3 | |
379 | bl L.3.13 | |
380 | srl %o5,1,%o5 | |
381 | ! remainder is positive | |
382 | subcc %o3,%o5,%o3 | |
383 | ! depth 4, accumulated bits -5 | |
384 | bl L.4.11 | |
385 | srl %o5,1,%o5 | |
386 | ! remainder is positive | |
387 | subcc %o3,%o5,%o3 | |
388 | b 9f | |
389 | add %o2, (-5*2+1), %o2 | |
390 | ||
391 | L.4.11: | |
392 | ! remainder is negative | |
393 | addcc %o3,%o5,%o3 | |
394 | b 9f | |
395 | add %o2, (-5*2-1), %o2 | |
396 | ||
397 | ||
398 | L.3.13: | |
399 | ! remainder is negative | |
400 | addcc %o3,%o5,%o3 | |
401 | ! depth 4, accumulated bits -7 | |
402 | bl L.4.9 | |
403 | srl %o5,1,%o5 | |
404 | ! remainder is positive | |
405 | subcc %o3,%o5,%o3 | |
406 | b 9f | |
407 | add %o2, (-7*2+1), %o2 | |
408 | ||
409 | L.4.9: | |
410 | ! remainder is negative | |
411 | addcc %o3,%o5,%o3 | |
412 | b 9f | |
413 | add %o2, (-7*2-1), %o2 | |
414 | ||
415 | ||
416 | ||
417 | ||
418 | 9: | |
419 | Lend_regular_divide: | |
420 | deccc %o4 | |
421 | bge Ldivloop | |
422 | tst %o3 | |
423 | bl,a Lgot_result | |
424 | ! non-restoring fixup here (one instruction only!) | |
425 | dec %o2 | |
426 | ||
427 | ||
428 | Lgot_result: | |
429 | ! check to see if answer should be < 0 | |
430 | tst %g6 | |
431 | bl,a 1f | |
432 | neg %o2 | |
433 | 1: | |
434 | retl | |
435 | mov %o2, %o0 |