2 * This m4 code has been taken from The SPARC Architecture Manual Version 8.
8 * dividend -- the thing being divided
9 * divisor -- how many ways to divide it
10 * Important parameters:
11 * N -- how many bits per iteration we try to get
12 * as our current guess:
13 * WORDSIZE -- how many bits altogether we're talking about:
16 * TOPBITS -- how many bits are in the top "decade" of a number:
18 * Important variables are:
19 * Q -- the partial quotient under development -- initially 0
20 * R -- the remainder so far -- initially == the dividend
21 * ITER -- number of iterations of the main division loop which will
22 * be required. Equal to CEIL( lg2(quotient)/4 )
23 * Note that this is log_base_(2ˆ4) of the quotient.
24 * V -- the current comparand -- initially divisor*2ˆ(ITER*4-1)
26 * current estimate for non-large dividend is
27 * CEIL( lg2(quotient) / 4 ) x ( 10 + 74/2 ) + C
28 * a large dividend is one greater than 2ˆ(31-4 ) and takes a
29 * different path, as the upper bits of the quotient must be developed
31 * This uses the m4 and cpp macro preprocessors.
34 * This is the recursive definition of how we develop quotient digits.
35 * It takes three important parameters:
36 * $1 -- the current depth, 1<=$1<=4
37 * $2 -- the current accumulation of quotient bits
39 * We add a new bit to $2 and either recurse or insert the bits in the quotient.
41 * %o3 -- current remainder
42 * %o2 -- current quotient
43 * %o5 -- current comparand
44 * cc -- set on current value of %o3
46 * %o3', %o2', %o5', cc'
48 #include "../assembly.h"
51 DEFINE_COMPILERRT_FUNCTION(__udivsi3)
53 mov 0,%g3 ! result always nonnegative
56 DEFINE_COMPILERRT_FUNCTION(__divsi3)
57 orcc %o1,%o0,%g0 ! are either %o0 or %o1 negative
58 bge divide ! if not, skip this junk
59 xor %o1,%o0,%g3 ! record sign of result in sign of %g3
71 ! Compute size of quotient, scale comparand.
72 orcc %o1,%g0,%o5 ! movcc %o1,%o5
76 sethi %hi(1<<(32-4 -1)),%g1
81 ! Here, the %o0 is >= 2ˆ(31-4) or so. We must be careful here,
82 ! as our usual 4-at-a-shot divide step will cause overflow and havoc.
83 ! The total number of bits in the result here is 4*%o4+%g2, where
85 ! Compute %o4 in an unorthodox manner: know we need to Shift %o5 into
86 ! the top decade: so don't even bother to compare to %o3.
98 ! We're here if the %o1 overflowed when Shifting.
99 ! This means that %o3 has the high-order bit set.
100 ! Restore %o5 and subtract from %o3.
101 sll %g1,4 ,%g1 ! high order bit
102 srl %o5,1,%o5 ! rest of %o5
112 ! %o5 > %o3: went too far: back up 1 step
115 ! do single-bit divide steps
117 ! We have to be careful here. We know that %o3 >= %o5, so we can do the
118 ! first divide step without thinking. BUT, the others are conditional,
119 ! and are only done if %o3 >= 0. Because both %o3 and %o5 may have the high-
120 ! order bit set in the first step, just falling into the regular
121 ! division loop will mess up the first time around.
122 ! So we unroll slightly...
125 bl end_regular_divide
129 b,a end_single_divloop
147 b,a end_regular_divide
158 ! Do the main division iteration
160 ! Fall through into divide loop
163 !depth 1, accumulated bits 0
166 ! remainder is nonnegative
168 !depth 2, accumulated bits 1
171 ! remainder is nonnegative
173 !depth 3, accumulated bits 3
176 ! remainder is nonnegative
178 !depth 4, accumulated bits 7
181 ! remainder is nonnegative
184 add %o2, (7*2+1), %o2
186 ! remainder is negative
189 add %o2, (7*2-1), %o2
191 ! remainder is negative
193 !depth 4, accumulated bits 5
196 ! remainder is nonnegative
199 add %o2, (5*2+1), %o2
201 ! remainder is negative
204 add %o2, (5*2-1), %o2
206 ! remainder is negative
208 !depth 3, accumulated bits 1
211 ! remainder is nonnegative
213 !depth 4, accumulated bits 3
216 ! remainder is nonnegative
219 add %o2, (3*2+1), %o2
221 ! remainder is negative
224 add %o2, (3*2-1), %o2
226 ! remainder is negative
228 !depth 4, accumulated bits 1
231 ! remainder is nonnegative
234 add %o2, (1*2+1), %o2
236 ! remainder is negative
239 add %o2, (1*2-1), %o2
241 ! remainder is negative
243 !depth 2, accumulated bits -1
246 ! remainder is nonnegative
248 !depth 3, accumulated bits -1
251 ! remainder is nonnegative
253 !depth 4, accumulated bits -1
256 ! remainder is nonnegative
259 add %o2, (-1*2+1), %o2
261 ! remainder is negative
264 add %o2, (-1*2-1), %o2
266 ! remainder is negative
268 !depth 4, accumulated bits -3
271 ! remainder is nonnegative
274 add %o2, (-3*2+1), %o2
276 ! remainder is negative
279 add %o2, (-3*2-1), %o2
281 ! remainder is negative
283 !depth 3, accumulated bits -3
286 ! remainder is nonnegative
288 !depth 4, accumulated bits -5
291 ! remainder is nonnegative
294 add %o2, (-5*2+1), %o2
296 ! remainder is negative
299 add %o2, (-5*2-1), %o2
301 ! remainder is negative
303 !depth 4, accumulated bits -7
306 ! remainder is nonnegative
309 add %o2, (-7*2+1), %o2
311 ! remainder is negative
314 add %o2, (-7*2-1), %o2
321 ! non-restoring fixup if remainder < 0, otherwise annulled
326 ! negate for answer < 0, otherwise annulled
327 neg %o2,%o2 ! %o2 <- -%o2
329 retl ! leaf-routine return
330 mov %o2,%o0 ! quotient <- %o2