.
[glibc/pb-stable.git] / sysdeps / sparc / sparc32 / rem.S
blobeffacee0d015b574333b7c529bf6a01941e7057b
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  *  .rem        name of function to generate
12  *  rem         rem=div => %o0 / %o1; rem=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 <sysdep.h>
41 #include <sys/trap.h>
43 ENTRY(.rem)
44         ! compute sign of result; if neither is negative, no problem
45         orcc    %o1, %o0, %g0   ! either negative?
46         bge     2f                      ! no, go do the divide
47         mov     %o0, %g3                ! sign of remainder matches %o0
48         tst     %o1
49         bge     1f
50         tst     %o0
51         ! %o1 is definitely negative; %o0 might also be negative
52         bge     2f                      ! if %o0 not negative...
53         sub     %g0, %o1, %o1   ! in any case, make %o1 nonneg
54 1:      ! %o0 is negative, %o1 is nonnegative
55         sub     %g0, %o0, %o0   ! make %o0 nonnegative
58         ! Ready to divide.  Compute size of quotient; scale comparand.
59         orcc    %o1, %g0, %o5
60         bne     1f
61         mov     %o0, %o3
63                 ! Divide by zero trap.  If it returns, return 0 (about as
64                 ! wrong as possible, but that is what SunOS does...).
65                 ta      ST_DIV0
66                 retl
67                 clr     %o0
70         cmp     %o3, %o5                        ! if %o1 exceeds %o0, done
71         blu     LOC(got_result)         ! (and algorithm fails otherwise)
72         clr     %o2
73         sethi   %hi(1 << (32 - 4 - 1)), %g1
74         cmp     %o3, %g1
75         blu     LOC(not_really_big)
76         clr     %o4
78         ! Here the dividend is >= 2**(31-N) or so.  We must be careful here,
79         ! as our usual N-at-a-shot divide step will cause overflow and havoc.
80         ! The number of bits in the result here is N*ITER+SC, where SC <= N.
81         ! Compute ITER in an unorthodox manner: know we need to shift V into
82         ! the top decade: so do not even bother to compare to R.
83         1:
84                 cmp     %o5, %g1
85                 bgeu    3f
86                 mov     1, %g2
87                 sll     %o5, 4, %o5
88                 b       1b
89                 add     %o4, 1, %o4
91         ! Now compute %g2.
92         2:      addcc   %o5, %o5, %o5
93                 bcc     LOC(not_too_big)
94                 add     %g2, 1, %g2
96                 ! We get here if the %o1 overflowed while shifting.
97                 ! This means that %o3 has the high-order bit set.
98                 ! Restore %o5 and subtract from %o3.
99                 sll     %g1, 4, %g1     ! high order bit
100                 srl     %o5, 1, %o5             ! rest of %o5
101                 add     %o5, %g1, %o5
102                 b       LOC(do_single_div)
103                 sub     %g2, 1, %g2
105         LOC(not_too_big):
106         3:      cmp     %o5, %o3
107                 blu     2b
108                 nop
109                 be      LOC(do_single_div)
110                 nop
111         /* NB: these are commented out in the V8-Sparc manual as well */
112         /* (I do not understand this) */
113         ! %o5 > %o3: went too far: back up 1 step
114         !       srl     %o5, 1, %o5
115         !       dec     %g2
116         ! do single-bit divide steps
117         !
118         ! We have to be careful here.  We know that %o3 >= %o5, so we can do the
119         ! first divide step without thinking.  BUT, the others are conditional,
120         ! and are only done if %o3 >= 0.  Because both %o3 and %o5 may have the high-
121         ! order bit set in the first step, just falling into the regular
122         ! division loop will mess up the first time around.
123         ! So we unroll slightly...
124         LOC(do_single_div):
125                 subcc   %g2, 1, %g2
126                 bl      LOC(end_regular_divide)
127                 nop
128                 sub     %o3, %o5, %o3
129                 mov     1, %o2
130                 b       LOC(end_single_divloop)
131                 nop
132         LOC(single_divloop):
133                 sll     %o2, 1, %o2
134                 bl      1f
135                 srl     %o5, 1, %o5
136                 ! %o3 >= 0
137                 sub     %o3, %o5, %o3
138                 b       2f
139                 add     %o2, 1, %o2
140         1:      ! %o3 < 0
141                 add     %o3, %o5, %o3
142                 sub     %o2, 1, %o2
143         2:
144         LOC(end_single_divloop):
145                 subcc   %g2, 1, %g2
146                 bge     LOC(single_divloop)
147                 tst     %o3
148                 b,a     LOC(end_regular_divide)
150 LOC(not_really_big):
152         sll     %o5, 4, %o5
153         cmp     %o5, %o3
154         bleu    1b
155         addcc   %o4, 1, %o4
156         be      LOC(got_result)
157         sub     %o4, 1, %o4
159         tst     %o3     ! set up for initial iteration
160 LOC(divloop):
161         sll     %o2, 4, %o2
162                 ! depth 1, accumulated bits 0
163         bl      LOC(1.16)
164         srl     %o5,1,%o5
165         ! remainder is positive
166         subcc   %o3,%o5,%o3
167                         ! depth 2, accumulated bits 1
168         bl      LOC(2.17)
169         srl     %o5,1,%o5
170         ! remainder is positive
171         subcc   %o3,%o5,%o3
172                         ! depth 3, accumulated bits 3
173         bl      LOC(3.19)
174         srl     %o5,1,%o5
175         ! remainder is positive
176         subcc   %o3,%o5,%o3
177                         ! depth 4, accumulated bits 7
178         bl      LOC(4.23)
179         srl     %o5,1,%o5
180         ! remainder is positive
181         subcc   %o3,%o5,%o3
182                 b       9f
183                 add     %o2, (7*2+1), %o2
184         
185 LOC(4.23):
186         ! remainder is negative
187         addcc   %o3,%o5,%o3
188                 b       9f
189                 add     %o2, (7*2-1), %o2
190         
191         
192 LOC(3.19):
193         ! remainder is negative
194         addcc   %o3,%o5,%o3
195                         ! depth 4, accumulated bits 5
196         bl      LOC(4.21)
197         srl     %o5,1,%o5
198         ! remainder is positive
199         subcc   %o3,%o5,%o3
200                 b       9f
201                 add     %o2, (5*2+1), %o2
202         
203 LOC(4.21):
204         ! remainder is negative
205         addcc   %o3,%o5,%o3
206                 b       9f
207                 add     %o2, (5*2-1), %o2
208         
209         
210         
211 LOC(2.17):
212         ! remainder is negative
213         addcc   %o3,%o5,%o3
214                         ! depth 3, accumulated bits 1
215         bl      LOC(3.17)
216         srl     %o5,1,%o5
217         ! remainder is positive
218         subcc   %o3,%o5,%o3
219                         ! depth 4, accumulated bits 3
220         bl      LOC(4.19)
221         srl     %o5,1,%o5
222         ! remainder is positive
223         subcc   %o3,%o5,%o3
224                 b       9f
225                 add     %o2, (3*2+1), %o2
226         
227 LOC(4.19):
228         ! remainder is negative
229         addcc   %o3,%o5,%o3
230                 b       9f
231                 add     %o2, (3*2-1), %o2
232         
233         
234 LOC(3.17):
235         ! remainder is negative
236         addcc   %o3,%o5,%o3
237                         ! depth 4, accumulated bits 1
238         bl      LOC(4.17)
239         srl     %o5,1,%o5
240         ! remainder is positive
241         subcc   %o3,%o5,%o3
242                 b       9f
243                 add     %o2, (1*2+1), %o2
244         
245 LOC(4.17):
246         ! remainder is negative
247         addcc   %o3,%o5,%o3
248                 b       9f
249                 add     %o2, (1*2-1), %o2
250         
251         
252         
253         
254 LOC(1.16):
255         ! remainder is negative
256         addcc   %o3,%o5,%o3
257                         ! depth 2, accumulated bits -1
258         bl      LOC(2.15)
259         srl     %o5,1,%o5
260         ! remainder is positive
261         subcc   %o3,%o5,%o3
262                         ! depth 3, accumulated bits -1
263         bl      LOC(3.15)
264         srl     %o5,1,%o5
265         ! remainder is positive
266         subcc   %o3,%o5,%o3
267                         ! depth 4, accumulated bits -1
268         bl      LOC(4.15)
269         srl     %o5,1,%o5
270         ! remainder is positive
271         subcc   %o3,%o5,%o3
272                 b       9f
273                 add     %o2, (-1*2+1), %o2
274         
275 LOC(4.15):
276         ! remainder is negative
277         addcc   %o3,%o5,%o3
278                 b       9f
279                 add     %o2, (-1*2-1), %o2
280         
281         
282 LOC(3.15):
283         ! remainder is negative
284         addcc   %o3,%o5,%o3
285                         ! depth 4, accumulated bits -3
286         bl      LOC(4.13)
287         srl     %o5,1,%o5
288         ! remainder is positive
289         subcc   %o3,%o5,%o3
290                 b       9f
291                 add     %o2, (-3*2+1), %o2
292         
293 LOC(4.13):
294         ! remainder is negative
295         addcc   %o3,%o5,%o3
296                 b       9f
297                 add     %o2, (-3*2-1), %o2
298         
299         
300         
301 LOC(2.15):
302         ! remainder is negative
303         addcc   %o3,%o5,%o3
304                         ! depth 3, accumulated bits -3
305         bl      LOC(3.13)
306         srl     %o5,1,%o5
307         ! remainder is positive
308         subcc   %o3,%o5,%o3
309                         ! depth 4, accumulated bits -5
310         bl      LOC(4.11)
311         srl     %o5,1,%o5
312         ! remainder is positive
313         subcc   %o3,%o5,%o3
314                 b       9f
315                 add     %o2, (-5*2+1), %o2
316         
317 LOC(4.11):
318         ! remainder is negative
319         addcc   %o3,%o5,%o3
320                 b       9f
321                 add     %o2, (-5*2-1), %o2
322         
323         
324 LOC(3.13):
325         ! remainder is negative
326         addcc   %o3,%o5,%o3
327                         ! depth 4, accumulated bits -7
328         bl      LOC(4.9)
329         srl     %o5,1,%o5
330         ! remainder is positive
331         subcc   %o3,%o5,%o3
332                 b       9f
333                 add     %o2, (-7*2+1), %o2
334         
335 LOC(4.9):
336         ! remainder is negative
337         addcc   %o3,%o5,%o3
338                 b       9f
339                 add     %o2, (-7*2-1), %o2
340         
341         
342         
343         
344         9:
345 LOC(end_regular_divide):
346         subcc   %o4, 1, %o4
347         bge     LOC(divloop)
348         tst     %o3
349         bl,a    LOC(got_result)
350         ! non-restoring fixup here (one instruction only!)
351         add     %o3, %o1, %o3
354 LOC(got_result):
355         ! check to see if answer should be < 0
356         tst     %g3
357         bl,a    1f
358         sub %g0, %o3, %o3
360         retl
361         mov %o3, %o0
363 END(.rem)