| blob | 252afd01932dae72e8f2aed97270c6ff0206176f |
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 * .udiv name of function to generate
12 * div div=div => %o0 / %o1; div=rem => %o0 % %o1
13 * false false=true => signed; false=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 __linux__
42 #include <asm/traps.h>
43 #else
44 #ifdef __svr4__
45 #include <sys/trap.h>
46 #else
47 #include <machine/trap.h>
48 #endif
49 #endif
51 FUNC(.udiv)
53 ! Ready to divide. Compute size of quotient; scale comparand.
54 orcc %o1, %g0, %o5
55 bne 1f
56 mov %o0, %o3
58 ! Divide by zero trap. If it returns, return 0 (about as
59 ! wrong as possible, but that is what SunOS does...).
60 ta ST_DIV0
61 retl
62 clr %o0
64 1:
65 cmp %o3, %o5 ! if %o1 exceeds %o0, done
66 blu Lgot_result ! (and algorithm fails otherwise)
67 clr %o2
68 sethi %hi(1 << (32 - 4 - 1)), %g1
69 cmp %o3, %g1
70 blu Lnot_really_big
71 clr %o4
73 ! Here the dividend is >= 2**(31-N) or so. We must be careful here,
74 ! as our usual N-at-a-shot divide step will cause overflow and havoc.
75 ! The number of bits in the result here is N*ITER+SC, where SC <= N.
76 ! Compute ITER in an unorthodox manner: know we need to shift V into
77 ! the top decade: so do not even bother to compare to R.
78 1:
79 cmp %o5, %g1
80 bgeu 3f
81 mov 1, %g7
82 sll %o5, 4, %o5
83 b 1b
84 add %o4, 1, %o4
86 ! Now compute %g7.
87 2: addcc %o5, %o5, %o5
88 bcc Lnot_too_big
89 add %g7, 1, %g7
91 ! We get here if the %o1 overflowed while shifting.
92 ! This means that %o3 has the high-order bit set.
93 ! Restore %o5 and subtract from %o3.
94 sll %g1, 4, %g1 ! high order bit
95 srl %o5, 1, %o5 ! rest of %o5
96 add %o5, %g1, %o5
97 b Ldo_single_div
98 sub %g7, 1, %g7
100 Lnot_too_big:
101 3: cmp %o5, %o3
102 blu 2b
103 nop
104 be Ldo_single_div
105 nop
106 /* NB: these are commented out in the V8-Sparc manual as well */
107 /* (I do not understand this) */
108 ! %o5 > %o3: went too far: back up 1 step
109 ! srl %o5, 1, %o5
110 ! dec %g7
111 ! do single-bit divide steps
112 !
113 ! We have to be careful here. We know that %o3 >= %o5, so we can do the
114 ! first divide step without thinking. BUT, the others are conditional,
115 ! and are only done if %o3 >= 0. Because both %o3 and %o5 may have the high-
116 ! order bit set in the first step, just falling into the regular
117 ! division loop will mess up the first time around.
118 ! So we unroll slightly...
119 Ldo_single_div:
120 subcc %g7, 1, %g7
121 bl Lend_regular_divide
122 nop
123 sub %o3, %o5, %o3
124 mov 1, %o2
125 b Lend_single_divloop
126 nop
127 Lsingle_divloop:
128 sll %o2, 1, %o2
129 bl 1f
130 srl %o5, 1, %o5
131 ! %o3 >= 0
132 sub %o3, %o5, %o3
133 b 2f
134 add %o2, 1, %o2
135 1: ! %o3 < 0
136 add %o3, %o5, %o3
137 sub %o2, 1, %o2
138 2:
139 Lend_single_divloop:
140 subcc %g7, 1, %g7
141 bge Lsingle_divloop
142 tst %o3
143 b,a Lend_regular_divide
145 Lnot_really_big:
146 1:
147 sll %o5, 4, %o5
148 cmp %o5, %o3
149 bleu 1b
150 addcc %o4, 1, %o4
151 be Lgot_result
152 sub %o4, 1, %o4
154 tst %o3 ! set up for initial iteration
155 Ldivloop:
156 sll %o2, 4, %o2
157 ! depth 1, accumulated bits 0
158 bl L.1.16
159 srl %o5,1,%o5
160 ! remainder is positive
161 subcc %o3,%o5,%o3
162 ! depth 2, accumulated bits 1
163 bl L.2.17
164 srl %o5,1,%o5
165 ! remainder is positive
166 subcc %o3,%o5,%o3
167 ! depth 3, accumulated bits 3
168 bl L.3.19
169 srl %o5,1,%o5
170 ! remainder is positive
171 subcc %o3,%o5,%o3
172 ! depth 4, accumulated bits 7
173 bl L.4.23
174 srl %o5,1,%o5
175 ! remainder is positive
176 subcc %o3,%o5,%o3
177 b 9f
178 add %o2, (7*2+1), %o2
180 L.4.23:
181 ! remainder is negative
182 addcc %o3,%o5,%o3
183 b 9f
184 add %o2, (7*2-1), %o2
187 L.3.19:
188 ! remainder is negative
189 addcc %o3,%o5,%o3
190 ! depth 4, accumulated bits 5
191 bl L.4.21
192 srl %o5,1,%o5
193 ! remainder is positive
194 subcc %o3,%o5,%o3
195 b 9f
196 add %o2, (5*2+1), %o2
198 L.4.21:
199 ! remainder is negative
200 addcc %o3,%o5,%o3
201 b 9f
202 add %o2, (5*2-1), %o2
206 L.2.17:
207 ! remainder is negative
208 addcc %o3,%o5,%o3
209 ! depth 3, accumulated bits 1
210 bl L.3.17
211 srl %o5,1,%o5
212 ! remainder is positive
213 subcc %o3,%o5,%o3
214 ! depth 4, accumulated bits 3
215 bl L.4.19
216 srl %o5,1,%o5
217 ! remainder is positive
218 subcc %o3,%o5,%o3
219 b 9f
220 add %o2, (3*2+1), %o2
222 L.4.19:
223 ! remainder is negative
224 addcc %o3,%o5,%o3
225 b 9f
226 add %o2, (3*2-1), %o2
229 L.3.17:
230 ! remainder is negative
231 addcc %o3,%o5,%o3
232 ! depth 4, accumulated bits 1
233 bl L.4.17
234 srl %o5,1,%o5
235 ! remainder is positive
236 subcc %o3,%o5,%o3
237 b 9f
238 add %o2, (1*2+1), %o2
240 L.4.17:
241 ! remainder is negative
242 addcc %o3,%o5,%o3
243 b 9f
244 add %o2, (1*2-1), %o2
249 L.1.16:
250 ! remainder is negative
251 addcc %o3,%o5,%o3
252 ! depth 2, accumulated bits -1
253 bl L.2.15
254 srl %o5,1,%o5
255 ! remainder is positive
256 subcc %o3,%o5,%o3
257 ! depth 3, accumulated bits -1
258 bl L.3.15
259 srl %o5,1,%o5
260 ! remainder is positive
261 subcc %o3,%o5,%o3
262 ! depth 4, accumulated bits -1
263 bl L.4.15
264 srl %o5,1,%o5
265 ! remainder is positive
266 subcc %o3,%o5,%o3
267 b 9f
268 add %o2, (-1*2+1), %o2
270 L.4.15:
271 ! remainder is negative
272 addcc %o3,%o5,%o3
273 b 9f
274 add %o2, (-1*2-1), %o2
277 L.3.15:
278 ! remainder is negative
279 addcc %o3,%o5,%o3
280 ! depth 4, accumulated bits -3
281 bl L.4.13
282 srl %o5,1,%o5
283 ! remainder is positive
284 subcc %o3,%o5,%o3
285 b 9f
286 add %o2, (-3*2+1), %o2
288 L.4.13:
289 ! remainder is negative
290 addcc %o3,%o5,%o3
291 b 9f
292 add %o2, (-3*2-1), %o2
296 L.2.15:
297 ! remainder is negative
298 addcc %o3,%o5,%o3
299 ! depth 3, accumulated bits -3
300 bl L.3.13
301 srl %o5,1,%o5
302 ! remainder is positive
303 subcc %o3,%o5,%o3
304 ! depth 4, accumulated bits -5
305 bl L.4.11
306 srl %o5,1,%o5
307 ! remainder is positive
308 subcc %o3,%o5,%o3
309 b 9f
310 add %o2, (-5*2+1), %o2
312 L.4.11:
313 ! remainder is negative
314 addcc %o3,%o5,%o3
315 b 9f
316 add %o2, (-5*2-1), %o2
319 L.3.13:
320 ! remainder is negative
321 addcc %o3,%o5,%o3
322 ! depth 4, accumulated bits -7
323 bl L.4.9
324 srl %o5,1,%o5
325 ! remainder is positive
326 subcc %o3,%o5,%o3
327 b 9f
328 add %o2, (-7*2+1), %o2
330 L.4.9:
331 ! remainder is negative
332 addcc %o3,%o5,%o3
333 b 9f
334 add %o2, (-7*2-1), %o2
339 9:
340 Lend_regular_divide:
341 subcc %o4, 1, %o4
342 bge Ldivloop
343 tst %o3
344 bl,a Lgot_result
345 ! non-restoring fixup here (one instruction only!)
346 sub %o2, 1, %o2
349 Lgot_result:
351 retl
352 mov %o2, %o0