]>
Commit | Line | Data |
---|---|---|
1da177e4 LT |
1 | /* $Id: sdiv.S,v 1.6 1996/10/02 17:37:00 davem Exp $ |
2 | * sdiv.S: This routine was taken from glibc-1.09 and is covered | |
3 | * by the GNU Library General Public License Version 2. | |
4 | */ | |
5 | ||
6 | ||
7 | /* This file is generated from divrem.m4; DO NOT EDIT! */ | |
8 | /* | |
9 | * Division and remainder, from Appendix E of the Sparc Version 8 | |
10 | * Architecture Manual, with fixes from Gordon Irlam. | |
11 | */ | |
12 | ||
13 | /* | |
14 | * Input: dividend and divisor in %o0 and %o1 respectively. | |
15 | * | |
16 | * m4 parameters: | |
17 | * .div name of function to generate | |
18 | * div div=div => %o0 / %o1; div=rem => %o0 % %o1 | |
19 | * true true=true => signed; true=false => unsigned | |
20 | * | |
21 | * Algorithm parameters: | |
22 | * N how many bits per iteration we try to get (4) | |
23 | * WORDSIZE total number of bits (32) | |
24 | * | |
25 | * Derived constants: | |
26 | * TOPBITS number of bits in the top decade of a number | |
27 | * | |
28 | * Important variables: | |
29 | * Q the partial quotient under development (initially 0) | |
30 | * R the remainder so far, initially the dividend | |
31 | * ITER number of main division loop iterations required; | |
32 | * equal to ceil(log2(quotient) / N). Note that this | |
33 | * is the log base (2^N) of the quotient. | |
34 | * V the current comparand, initially divisor*2^(ITER*N-1) | |
35 | * | |
36 | * Cost: | |
37 | * Current estimate for non-large dividend is | |
38 | * ceil(log2(quotient) / N) * (10 + 7N/2) + C | |
39 | * A large dividend is one greater than 2^(31-TOPBITS) and takes a | |
40 | * different path, as the upper bits of the quotient must be developed | |
41 | * one bit at a time. | |
42 | */ | |
43 | ||
44 | ||
45 | .globl .div | |
46 | .div: | |
47 | ! compute sign of result; if neither is negative, no problem | |
48 | orcc %o1, %o0, %g0 ! either negative? | |
49 | bge 2f ! no, go do the divide | |
50 | xor %o1, %o0, %g2 ! compute sign in any case | |
51 | ||
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: | |
61 | ||
62 | ! Ready to divide. Compute size of quotient; scale comparand. | |
63 | orcc %o1, %g0, %o5 | |
64 | bne 1f | |
65 | mov %o0, %o3 | |
66 | ||
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 | |
72 | ||
73 | 1: | |
74 | cmp %o3, %o5 ! if %o1 exceeds %o0, done | |
75 | blu Lgot_result ! (and algorithm fails otherwise) | |
76 | clr %o2 | |
77 | ||
78 | sethi %hi(1 << (32 - 4 - 1)), %g1 | |
79 | ||
80 | cmp %o3, %g1 | |
81 | blu Lnot_really_big | |
82 | clr %o4 | |
83 | ||
84 | ! Here the dividend is >= 2**(31-N) or so. We must be careful here, | |
85 | ! as our usual N-at-a-shot divide step will cause overflow and havoc. | |
86 | ! The number of bits in the result here is N*ITER+SC, where SC <= N. | |
87 | ! Compute ITER in an unorthodox manner: know we need to shift V into | |
88 | ! the top decade: so do not even bother to compare to R. | |
89 | 1: | |
90 | cmp %o5, %g1 | |
91 | bgeu 3f | |
92 | mov 1, %g7 | |
93 | ||
94 | sll %o5, 4, %o5 | |
95 | ||
96 | b 1b | |
97 | add %o4, 1, %o4 | |
98 | ||
99 | ! Now compute %g7. | |
100 | 2: | |
101 | addcc %o5, %o5, %o5 | |
102 | bcc Lnot_too_big | |
103 | add %g7, 1, %g7 | |
104 | ||
105 | ! We get here if the %o1 overflowed while shifting. | |
106 | ! This means that %o3 has the high-order bit set. | |
107 | ! Restore %o5 and subtract from %o3. | |
108 | sll %g1, 4, %g1 ! high order bit | |
109 | srl %o5, 1, %o5 ! rest of %o5 | |
110 | add %o5, %g1, %o5 | |
111 | ||
112 | b Ldo_single_div | |
113 | sub %g7, 1, %g7 | |
114 | ||
115 | Lnot_too_big: | |
116 | 3: | |
117 | cmp %o5, %o3 | |
118 | blu 2b | |
119 | nop | |
120 | ||
121 | be Ldo_single_div | |
122 | nop | |
123 | /* NB: these are commented out in the V8-Sparc manual as well */ | |
124 | /* (I do not understand this) */ | |
125 | ! %o5 > %o3: went too far: back up 1 step | |
126 | ! srl %o5, 1, %o5 | |
127 | ! dec %g7 | |
128 | ! do single-bit divide steps | |
129 | ! | |
130 | ! We have to be careful here. We know that %o3 >= %o5, so we can do the | |
131 | ! first divide step without thinking. BUT, the others are conditional, | |
132 | ! and are only done if %o3 >= 0. Because both %o3 and %o5 may have the high- | |
133 | ! order bit set in the first step, just falling into the regular | |
134 | ! division loop will mess up the first time around. | |
135 | ! So we unroll slightly... | |
136 | Ldo_single_div: | |
137 | subcc %g7, 1, %g7 | |
138 | bl Lend_regular_divide | |
139 | nop | |
140 | ||
141 | sub %o3, %o5, %o3 | |
142 | mov 1, %o2 | |
143 | ||
144 | b Lend_single_divloop | |
145 | nop | |
146 | Lsingle_divloop: | |
147 | sll %o2, 1, %o2 | |
148 | ||
149 | bl 1f | |
150 | srl %o5, 1, %o5 | |
151 | ! %o3 >= 0 | |
152 | sub %o3, %o5, %o3 | |
153 | ||
154 | b 2f | |
155 | add %o2, 1, %o2 | |
156 | 1: ! %o3 < 0 | |
157 | add %o3, %o5, %o3 | |
158 | sub %o2, 1, %o2 | |
159 | 2: | |
160 | Lend_single_divloop: | |
161 | subcc %g7, 1, %g7 | |
162 | bge Lsingle_divloop | |
163 | tst %o3 | |
164 | ||
165 | b,a Lend_regular_divide | |
166 | ||
167 | Lnot_really_big: | |
168 | 1: | |
169 | sll %o5, 4, %o5 | |
170 | cmp %o5, %o3 | |
171 | bleu 1b | |
172 | addcc %o4, 1, %o4 | |
173 | ||
174 | be Lgot_result | |
175 | sub %o4, 1, %o4 | |
176 | ||
177 | tst %o3 ! set up for initial iteration | |
178 | Ldivloop: | |
179 | sll %o2, 4, %o2 | |
180 | ! depth 1, accumulated bits 0 | |
181 | bl L.1.16 | |
182 | srl %o5,1,%o5 | |
183 | ! remainder is positive | |
184 | subcc %o3,%o5,%o3 | |
185 | ! depth 2, accumulated bits 1 | |
186 | bl L.2.17 | |
187 | srl %o5,1,%o5 | |
188 | ! remainder is positive | |
189 | subcc %o3,%o5,%o3 | |
190 | ! depth 3, accumulated bits 3 | |
191 | bl L.3.19 | |
192 | srl %o5,1,%o5 | |
193 | ! remainder is positive | |
194 | subcc %o3,%o5,%o3 | |
195 | ! depth 4, accumulated bits 7 | |
196 | bl L.4.23 | |
197 | srl %o5,1,%o5 | |
198 | ! remainder is positive | |
199 | subcc %o3,%o5,%o3 | |
200 | b 9f | |
201 | add %o2, (7*2+1), %o2 | |
202 | ||
203 | L.4.23: | |
204 | ! remainder is negative | |
205 | addcc %o3,%o5,%o3 | |
206 | b 9f | |
207 | add %o2, (7*2-1), %o2 | |
208 | ||
209 | L.3.19: | |
210 | ! remainder is negative | |
211 | addcc %o3,%o5,%o3 | |
212 | ! depth 4, accumulated bits 5 | |
213 | bl L.4.21 | |
214 | srl %o5,1,%o5 | |
215 | ! remainder is positive | |
216 | subcc %o3,%o5,%o3 | |
217 | b 9f | |
218 | add %o2, (5*2+1), %o2 | |
219 | ||
220 | L.4.21: | |
221 | ! remainder is negative | |
222 | addcc %o3,%o5,%o3 | |
223 | b 9f | |
224 | add %o2, (5*2-1), %o2 | |
225 | ||
226 | L.2.17: | |
227 | ! remainder is negative | |
228 | addcc %o3,%o5,%o3 | |
229 | ! depth 3, accumulated bits 1 | |
230 | bl L.3.17 | |
231 | srl %o5,1,%o5 | |
232 | ! remainder is positive | |
233 | subcc %o3,%o5,%o3 | |
234 | ! depth 4, accumulated bits 3 | |
235 | bl L.4.19 | |
236 | srl %o5,1,%o5 | |
237 | ! remainder is positive | |
238 | subcc %o3,%o5,%o3 | |
239 | b 9f | |
240 | add %o2, (3*2+1), %o2 | |
241 | ||
242 | L.4.19: | |
243 | ! remainder is negative | |
244 | addcc %o3,%o5,%o3 | |
245 | b 9f | |
246 | add %o2, (3*2-1), %o2 | |
247 | ||
248 | ||
249 | L.3.17: | |
250 | ! remainder is negative | |
251 | addcc %o3,%o5,%o3 | |
252 | ! depth 4, accumulated bits 1 | |
253 | bl L.4.17 | |
254 | srl %o5,1,%o5 | |
255 | ! remainder is positive | |
256 | subcc %o3,%o5,%o3 | |
257 | b 9f | |
258 | add %o2, (1*2+1), %o2 | |
259 | ||
260 | L.4.17: | |
261 | ! remainder is negative | |
262 | addcc %o3,%o5,%o3 | |
263 | b 9f | |
264 | add %o2, (1*2-1), %o2 | |
265 | ||
266 | L.1.16: | |
267 | ! remainder is negative | |
268 | addcc %o3,%o5,%o3 | |
269 | ! depth 2, accumulated bits -1 | |
270 | bl L.2.15 | |
271 | srl %o5,1,%o5 | |
272 | ! remainder is positive | |
273 | subcc %o3,%o5,%o3 | |
274 | ! depth 3, accumulated bits -1 | |
275 | bl L.3.15 | |
276 | srl %o5,1,%o5 | |
277 | ! remainder is positive | |
278 | subcc %o3,%o5,%o3 | |
279 | ! depth 4, accumulated bits -1 | |
280 | bl L.4.15 | |
281 | srl %o5,1,%o5 | |
282 | ! remainder is positive | |
283 | subcc %o3,%o5,%o3 | |
284 | b 9f | |
285 | add %o2, (-1*2+1), %o2 | |
286 | ||
287 | L.4.15: | |
288 | ! remainder is negative | |
289 | addcc %o3,%o5,%o3 | |
290 | b 9f | |
291 | add %o2, (-1*2-1), %o2 | |
292 | ||
293 | L.3.15: | |
294 | ! remainder is negative | |
295 | addcc %o3,%o5,%o3 | |
296 | ! depth 4, accumulated bits -3 | |
297 | bl L.4.13 | |
298 | srl %o5,1,%o5 | |
299 | ! remainder is positive | |
300 | subcc %o3,%o5,%o3 | |
301 | b 9f | |
302 | add %o2, (-3*2+1), %o2 | |
303 | ||
304 | L.4.13: | |
305 | ! remainder is negative | |
306 | addcc %o3,%o5,%o3 | |
307 | b 9f | |
308 | add %o2, (-3*2-1), %o2 | |
309 | ||
310 | L.2.15: | |
311 | ! remainder is negative | |
312 | addcc %o3,%o5,%o3 | |
313 | ! depth 3, accumulated bits -3 | |
314 | bl L.3.13 | |
315 | srl %o5,1,%o5 | |
316 | ! remainder is positive | |
317 | subcc %o3,%o5,%o3 | |
318 | ! depth 4, accumulated bits -5 | |
319 | bl L.4.11 | |
320 | srl %o5,1,%o5 | |
321 | ! remainder is positive | |
322 | subcc %o3,%o5,%o3 | |
323 | b 9f | |
324 | add %o2, (-5*2+1), %o2 | |
325 | ||
326 | L.4.11: | |
327 | ! remainder is negative | |
328 | addcc %o3,%o5,%o3 | |
329 | b 9f | |
330 | add %o2, (-5*2-1), %o2 | |
331 | ||
332 | L.3.13: | |
333 | ! remainder is negative | |
334 | addcc %o3,%o5,%o3 | |
335 | ! depth 4, accumulated bits -7 | |
336 | bl L.4.9 | |
337 | srl %o5,1,%o5 | |
338 | ! remainder is positive | |
339 | subcc %o3,%o5,%o3 | |
340 | b 9f | |
341 | add %o2, (-7*2+1), %o2 | |
342 | ||
343 | L.4.9: | |
344 | ! remainder is negative | |
345 | addcc %o3,%o5,%o3 | |
346 | b 9f | |
347 | add %o2, (-7*2-1), %o2 | |
348 | ||
349 | 9: | |
350 | Lend_regular_divide: | |
351 | subcc %o4, 1, %o4 | |
352 | bge Ldivloop | |
353 | tst %o3 | |
354 | ||
355 | bl,a Lgot_result | |
356 | ! non-restoring fixup here (one instruction only!) | |
357 | sub %o2, 1, %o2 | |
358 | ||
359 | Lgot_result: | |
360 | ! check to see if answer should be < 0 | |
361 | tst %g2 | |
362 | bl,a 1f | |
363 | sub %g0, %o2, %o2 | |
364 | 1: | |
365 | retl | |
366 | mov %o2, %o0 | |
367 | ||
368 | .globl .div_patch | |
369 | .div_patch: | |
370 | sra %o0, 0x1f, %o2 | |
371 | wr %o2, 0x0, %y | |
372 | nop | |
373 | nop | |
374 | nop | |
375 | sdivcc %o0, %o1, %o0 | |
376 | bvs,a 1f | |
377 | xnor %o0, %g0, %o0 | |
378 | 1: retl | |
379 | nop |