| blob | dadbb36b0adde1b6d6a58605662ed1c7f0a6ac5e |
1 /* This file is generated from divrem.m4; DO NOT EDIT! */
2 /*
3 * Division and remainder, from Appendix E of the Sparc Version 8
4 * Architecture Manual, with fixes from Gordon Irlam.
5 */
7 /*
8 * Input: dividend and divisor in %o0 and %o1 respectively.
9 *
10 * m4 parameters:
11 * .div name of function to generate
12 * div div=div => %o0 / %o1; div=rem => %o0 % %o1
13 * true true=true => signed; true=false => unsigned
14 *
15 * Algorithm parameters:
16 * N how many bits per iteration we try to get (4)
17 * WORDSIZE total number of bits (32)
18 *
19 * Derived constants:
20 * TOPBITS number of bits in the top decade of a number
21 *
22 * Important variables:
23 * Q the partial quotient under development (initially 0)
24 * R the remainder so far, initially the dividend
25 * ITER number of main division loop iterations required;
26 * equal to ceil(log2(quotient) / N). Note that this
27 * is the log base (2^N) of the quotient.
28 * V the current comparand, initially divisor*2^(ITER*N-1)
29 *
30 * Cost:
31 * Current estimate for non-large dividend is
32 * ceil(log2(quotient) / N) * (10 + 7N/2) + C
33 * A large dividend is one greater than 2^(31-TOPBITS) and takes a
34 * different path, as the upper bits of the quotient must be developed
35 * one bit at a time.
36 */
40 #include "DEFS.h"
41 #ifdef __svr4__
42 #include <sys/trap.h>
43 #else
44 #include <machine/trap.h>
45 #endif
47 FUNC(.div)
48 ! compute sign of result; if neither is negative, no problem
49 orcc %o1, %o0, %g0 ! either negative?
50 bge 2f ! no, go do the divide
51 xor %o1, %o0, %g6 ! compute sign in any case
52 tst %o1
53 bge 1f
54 tst %o0
55 ! %o1 is definitely negative; %o0 might also be negative
56 bge 2f ! if %o0 not negative...
57 sub %g0, %o1, %o1 ! in any case, make %o1 nonneg
58 1: ! %o0 is negative, %o1 is nonnegative
59 sub %g0, %o0, %o0 ! make %o0 nonnegative
60 2:
62 ! Ready to divide. Compute size of quotient; scale comparand.
63 orcc %o1, %g0, %o5
64 bne 1f
65 mov %o0, %o3
67 ! Divide by zero trap. If it returns, return 0 (about as
68 ! wrong as possible, but that is what SunOS does...).
69 ta ST_DIV0
70 retl
71 clr %o0
73 1:
74 cmp %o3, %o5 ! if %o1 exceeds %o0, done
75 blu Lgot_result ! (and algorithm fails otherwise)
76 clr %o2
77 sethi %hi(1 << (32 - 4 - 1)), %g1
78 cmp %o3, %g1
79 blu Lnot_really_big
80 clr %o4
82 ! Here the dividend is >= 2**(31-N) or so. We must be careful here,
83 ! as our usual N-at-a-shot divide step will cause overflow and havoc.
84 ! The number of bits in the result here is N*ITER+SC, where SC <= N.
85 ! Compute ITER in an unorthodox manner: know we need to shift V into
86 ! the top decade: so do not even bother to compare to R.
87 1:
88 cmp %o5, %g1
89 bgeu 3f
90 mov 1, %g7
91 sll %o5, 4, %o5
92 b 1b
93 add %o4, 1, %o4
95 ! Now compute %g7.
96 2: addcc %o5, %o5, %o5
97 bcc Lnot_too_big
98 add %g7, 1, %g7
100 ! We get here if the %o1 overflowed while shifting.
101 ! This means that %o3 has the high-order bit set.
102 ! Restore %o5 and subtract from %o3.
103 sll %g1, 4, %g1 ! high order bit
104 srl %o5, 1, %o5 ! rest of %o5
105 add %o5, %g1, %o5
106 b Ldo_single_div
107 sub %g7, 1, %g7
109 Lnot_too_big:
110 3: cmp %o5, %o3
111 blu 2b
112 nop
113 be Ldo_single_div
114 nop
115 /* NB: these are commented out in the V8-Sparc manual as well */
116 /* (I do not understand this) */
117 ! %o5 > %o3: went too far: back up 1 step
118 ! srl %o5, 1, %o5
119 ! dec %g7
120 ! do single-bit divide steps
121 !
122 ! We have to be careful here. We know that %o3 >= %o5, so we can do the
123 ! first divide step without thinking. BUT, the others are conditional,
124 ! and are only done if %o3 >= 0. Because both %o3 and %o5 may have the high-
125 ! order bit set in the first step, just falling into the regular
126 ! division loop will mess up the first time around.
127 ! So we unroll slightly...
128 Ldo_single_div:
129 subcc %g7, 1, %g7
130 bl Lend_regular_divide
131 nop
132 sub %o3, %o5, %o3
133 mov 1, %o2
134 b Lend_single_divloop
135 nop
136 Lsingle_divloop:
137 sll %o2, 1, %o2
138 bl 1f
139 srl %o5, 1, %o5
140 ! %o3 >= 0
141 sub %o3, %o5, %o3
142 b 2f
143 add %o2, 1, %o2
144 1: ! %o3 < 0
145 add %o3, %o5, %o3
146 sub %o2, 1, %o2
147 2:
148 Lend_single_divloop:
149 subcc %g7, 1, %g7
150 bge Lsingle_divloop
151 tst %o3
152 b,a Lend_regular_divide
154 Lnot_really_big:
155 1:
156 sll %o5, 4, %o5
157 cmp %o5, %o3
158 bleu 1b
159 addcc %o4, 1, %o4
160 be Lgot_result
161 sub %o4, 1, %o4
163 tst %o3 ! set up for initial iteration
164 Ldivloop:
165 sll %o2, 4, %o2
166 ! depth 1, accumulated bits 0
167 bl L.1.16
168 srl %o5,1,%o5
169 ! remainder is positive
170 subcc %o3,%o5,%o3
171 ! depth 2, accumulated bits 1
172 bl L.2.17
173 srl %o5,1,%o5
174 ! remainder is positive
175 subcc %o3,%o5,%o3
176 ! depth 3, accumulated bits 3
177 bl L.3.19
178 srl %o5,1,%o5
179 ! remainder is positive
180 subcc %o3,%o5,%o3
181 ! depth 4, accumulated bits 7
182 bl L.4.23
183 srl %o5,1,%o5
184 ! remainder is positive
185 subcc %o3,%o5,%o3
186 b 9f
187 add %o2, (7*2+1), %o2
189 L.4.23:
190 ! remainder is negative
191 addcc %o3,%o5,%o3
192 b 9f
193 add %o2, (7*2-1), %o2
196 L.3.19:
197 ! remainder is negative
198 addcc %o3,%o5,%o3
199 ! depth 4, accumulated bits 5
200 bl L.4.21
201 srl %o5,1,%o5
202 ! remainder is positive
203 subcc %o3,%o5,%o3
204 b 9f
205 add %o2, (5*2+1), %o2
207 L.4.21:
208 ! remainder is negative
209 addcc %o3,%o5,%o3
210 b 9f
211 add %o2, (5*2-1), %o2
215 L.2.17:
216 ! remainder is negative
217 addcc %o3,%o5,%o3
218 ! depth 3, accumulated bits 1
219 bl L.3.17
220 srl %o5,1,%o5
221 ! remainder is positive
222 subcc %o3,%o5,%o3
223 ! depth 4, accumulated bits 3
224 bl L.4.19
225 srl %o5,1,%o5
226 ! remainder is positive
227 subcc %o3,%o5,%o3
228 b 9f
229 add %o2, (3*2+1), %o2
231 L.4.19:
232 ! remainder is negative
233 addcc %o3,%o5,%o3
234 b 9f
235 add %o2, (3*2-1), %o2
238 L.3.17:
239 ! remainder is negative
240 addcc %o3,%o5,%o3
241 ! depth 4, accumulated bits 1
242 bl L.4.17
243 srl %o5,1,%o5
244 ! remainder is positive
245 subcc %o3,%o5,%o3
246 b 9f
247 add %o2, (1*2+1), %o2
249 L.4.17:
250 ! remainder is negative
251 addcc %o3,%o5,%o3
252 b 9f
253 add %o2, (1*2-1), %o2
258 L.1.16:
259 ! remainder is negative
260 addcc %o3,%o5,%o3
261 ! depth 2, accumulated bits -1
262 bl L.2.15
263 srl %o5,1,%o5
264 ! remainder is positive
265 subcc %o3,%o5,%o3
266 ! depth 3, accumulated bits -1
267 bl L.3.15
268 srl %o5,1,%o5
269 ! remainder is positive
270 subcc %o3,%o5,%o3
271 ! depth 4, accumulated bits -1
272 bl L.4.15
273 srl %o5,1,%o5
274 ! remainder is positive
275 subcc %o3,%o5,%o3
276 b 9f
277 add %o2, (-1*2+1), %o2
279 L.4.15:
280 ! remainder is negative
281 addcc %o3,%o5,%o3
282 b 9f
283 add %o2, (-1*2-1), %o2
286 L.3.15:
287 ! remainder is negative
288 addcc %o3,%o5,%o3
289 ! depth 4, accumulated bits -3
290 bl L.4.13
291 srl %o5,1,%o5
292 ! remainder is positive
293 subcc %o3,%o5,%o3
294 b 9f
295 add %o2, (-3*2+1), %o2
297 L.4.13:
298 ! remainder is negative
299 addcc %o3,%o5,%o3
300 b 9f
301 add %o2, (-3*2-1), %o2
305 L.2.15:
306 ! remainder is negative
307 addcc %o3,%o5,%o3
308 ! depth 3, accumulated bits -3
309 bl L.3.13
310 srl %o5,1,%o5
311 ! remainder is positive
312 subcc %o3,%o5,%o3
313 ! depth 4, accumulated bits -5
314 bl L.4.11
315 srl %o5,1,%o5
316 ! remainder is positive
317 subcc %o3,%o5,%o3
318 b 9f
319 add %o2, (-5*2+1), %o2
321 L.4.11:
322 ! remainder is negative
323 addcc %o3,%o5,%o3
324 b 9f
325 add %o2, (-5*2-1), %o2
328 L.3.13:
329 ! remainder is negative
330 addcc %o3,%o5,%o3
331 ! depth 4, accumulated bits -7
332 bl L.4.9
333 srl %o5,1,%o5
334 ! remainder is positive
335 subcc %o3,%o5,%o3
336 b 9f
337 add %o2, (-7*2+1), %o2
339 L.4.9:
340 ! remainder is negative
341 addcc %o3,%o5,%o3
342 b 9f
343 add %o2, (-7*2-1), %o2
348 9:
349 Lend_regular_divide:
350 subcc %o4, 1, %o4
351 bge Ldivloop
352 tst %o3
353 bl,a Lgot_result
354 ! non-restoring fixup here (one instruction only!)
355 sub %o2, 1, %o2
358 Lgot_result:
359 ! check to see if answer should be < 0
360 tst %g6
361 bl,a 1f
362 sub %g0, %o2, %o2
363 1:
364 retl
365 mov %o2, %o0