]>
git.ipfire.org Git - thirdparty/gcc.git/blob - libgcc/config/tilepro/softdivide.c
1 /* Division and remainder routines for Tile.
2 Copyright (C) 2011, 2012
3 Free Software Foundation, Inc.
4 Contributed by Walter Lee (walt@tilera.com)
6 This file is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 3, or (at your option) any
11 This file is distributed in the hope that it will be useful, but
12 WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 General Public License for more details.
16 Under Section 7 of GPL version 3, you are granted additional
17 permissions described in the GCC Runtime Library Exception, version
18 3.1, as published by the Free Software Foundation.
20 You should have received a copy of the GNU General Public License and
21 a copy of the GCC Runtime Library Exception along with this program;
22 see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 <http://www.gnu.org/licenses/>. */
26 typedef unsigned uint32_t;
27 typedef long long int64_t;
28 typedef unsigned long long uint64_t;
30 /* Raise signal 8 (SIGFPE) with code 1 (FPE_INTDIV). */
34 asm ("{ raise; moveli zero, 8 + (1 << 6) }");
39 /*__udivsi3 - 32 bit integer unsigned divide */
40 static inline uint32_t __attribute__ ((always_inline
))
41 __udivsi3_inline (uint32_t dividend
, uint32_t divisor
)
43 /* Divide out any power of two factor from dividend and divisor.
44 Note that when dividing by zero the divisor will remain zero,
45 which is all we need to detect that case below. */
46 const int power_of_two_factor
= __insn_ctz (divisor
);
47 divisor
>>= power_of_two_factor
;
48 dividend
>>= power_of_two_factor
;
50 /* Checks for division by power of two or division by zero. */
61 /* Compute (a / b) by repeatedly finding the largest N
62 such that (b << N) <= a. For each such N, set bit N in the
63 quotient, subtract (b << N) from a, and keep going. Think of this as
64 the reverse of the "shift-and-add" that a multiply does. The values
65 of N are precisely those shift counts.
67 Finding N is easy. First, use clz(b) - clz(a) to find the N
68 that lines up the high bit of (b << N) with the high bit of a.
69 Any larger value of N would definitely make (b << N) > a,
72 Then, if (b << N) > a (because it has larger low bits), decrement
73 N by one. This adjustment will definitely make (b << N) less
74 than a, because a's high bit is now one higher than b's. */
76 /* Precomputing the max_ values allows us to avoid a subtract
77 in the inner loop and just right shift by clz(remainder). */
78 const int divisor_clz
= __insn_clz (divisor
);
79 const uint32_t max_divisor
= divisor
<< divisor_clz
;
80 const uint32_t max_qbit
= 1 << divisor_clz
;
82 uint32_t quotient
= 0;
83 uint32_t remainder
= dividend
;
85 while (remainder
>= divisor
)
87 int shift
= __insn_clz (remainder
);
88 uint32_t scaled_divisor
= max_divisor
>> shift
;
89 uint32_t quotient_bit
= max_qbit
>> shift
;
91 int too_big
= (scaled_divisor
> remainder
);
92 scaled_divisor
>>= too_big
;
93 quotient_bit
>>= too_big
;
94 remainder
-= scaled_divisor
;
95 quotient
|= quotient_bit
;
99 #endif /* !__tilegx__ */
102 /* __udivdi3 - 64 bit integer unsigned divide */
103 static inline uint64_t __attribute__ ((always_inline
))
104 __udivdi3_inline (uint64_t dividend
, uint64_t divisor
)
106 /* Divide out any power of two factor from dividend and divisor.
107 Note that when dividing by zero the divisor will remain zero,
108 which is all we need to detect that case below. */
109 const int power_of_two_factor
= __builtin_ctzll (divisor
);
110 divisor
>>= power_of_two_factor
;
111 dividend
>>= power_of_two_factor
;
113 /* Checks for division by power of two or division by zero. */
125 if (((uint32_t) (dividend
>> 32) | ((uint32_t) (divisor
>> 32))) == 0)
127 /* Operands both fit in 32 bits, so use faster 32 bit algorithm. */
128 return __udivsi3_inline ((uint32_t) dividend
, (uint32_t) divisor
);
130 #endif /* !__tilegx__ */
132 /* See algorithm description in __udivsi3 */
134 const int divisor_clz
= __builtin_clzll (divisor
);
135 const uint64_t max_divisor
= divisor
<< divisor_clz
;
136 const uint64_t max_qbit
= 1ULL << divisor_clz
;
138 uint64_t quotient
= 0;
139 uint64_t remainder
= dividend
;
141 while (remainder
>= divisor
)
143 int shift
= __builtin_clzll (remainder
);
144 uint64_t scaled_divisor
= max_divisor
>> shift
;
145 uint64_t quotient_bit
= max_qbit
>> shift
;
147 int too_big
= (scaled_divisor
> remainder
);
148 scaled_divisor
>>= too_big
;
149 quotient_bit
>>= too_big
;
150 remainder
-= scaled_divisor
;
151 quotient
|= quotient_bit
;
158 /* __umodsi3 - 32 bit integer unsigned modulo */
159 static inline uint32_t __attribute__ ((always_inline
))
160 __umodsi3_inline (uint32_t dividend
, uint32_t divisor
)
162 /* Shortcircuit mod by a power of two (and catch mod by zero). */
163 const uint32_t mask
= divisor
- 1;
164 if ((divisor
& mask
) == 0)
171 return dividend
& mask
;
174 /* We compute the remainder (a % b) by repeatedly subtracting off
175 multiples of b from a until a < b. The key is that subtracting
176 off a multiple of b does not affect the result mod b.
178 To make the algorithm run efficiently, we need to subtract
179 off a large multiple of b at each step. We subtract the largest
180 (b << N) that is <= a.
182 Finding N is easy. First, use clz(b) - clz(a) to find the N
183 that lines up the high bit of (b << N) with the high bit of a.
184 Any larger value of N would definitely make (b << N) > a,
187 Then, if (b << N) > a (because it has larger low bits), decrement
188 N by one. This adjustment will definitely make (b << N) less
189 than a, because a's high bit is now one higher than b's. */
190 const uint32_t max_divisor
= divisor
<< __insn_clz (divisor
);
192 uint32_t remainder
= dividend
;
193 while (remainder
>= divisor
)
195 const int shift
= __insn_clz (remainder
);
196 uint32_t scaled_divisor
= max_divisor
>> shift
;
197 scaled_divisor
>>= (scaled_divisor
> remainder
);
198 remainder
-= scaled_divisor
;
203 #endif /* !__tilegx__ */
206 /* __umoddi3 - 64 bit integer unsigned modulo */
207 static inline uint64_t __attribute__ ((always_inline
))
208 __umoddi3_inline (uint64_t dividend
, uint64_t divisor
)
211 if (((uint32_t) (dividend
>> 32) | ((uint32_t) (divisor
>> 32))) == 0)
213 /* Operands both fit in 32 bits, so use faster 32 bit algorithm. */
214 return __umodsi3_inline ((uint32_t) dividend
, (uint32_t) divisor
);
216 #endif /* !__tilegx__ */
218 /* Shortcircuit mod by a power of two (and catch mod by zero). */
219 const uint64_t mask
= divisor
- 1;
220 if ((divisor
& mask
) == 0)
227 return dividend
& mask
;
230 /* See algorithm description in __umodsi3 */
231 const uint64_t max_divisor
= divisor
<< __builtin_clzll (divisor
);
233 uint64_t remainder
= dividend
;
234 while (remainder
>= divisor
)
236 const int shift
= __builtin_clzll (remainder
);
237 uint64_t scaled_divisor
= max_divisor
>> shift
;
238 scaled_divisor
>>= (scaled_divisor
> remainder
);
239 remainder
-= scaled_divisor
;
246 uint32_t __udivsi3 (uint32_t dividend
, uint32_t divisor
);
247 #ifdef L_tile_udivsi3
249 __udivsi3 (uint32_t dividend
, uint32_t divisor
)
252 return __udivsi3_inline (dividend
, divisor
);
253 #else /* !__tilegx__ */
254 uint64_t n
= __udivdi3_inline (((uint64_t) dividend
), ((uint64_t) divisor
));
256 #endif /* !__tilegx__ */
260 #define ABS(x) ((x) >= 0 ? (x) : -(x))
262 int32_t __divsi3 (int32_t dividend
, int32_t divisor
);
264 /* __divsi3 - 32 bit integer signed divide */
266 __divsi3 (int32_t dividend
, int32_t divisor
)
269 uint32_t n
= __udivsi3_inline (ABS (dividend
), ABS (divisor
));
270 #else /* !__tilegx__ */
272 __udivdi3_inline (ABS ((int64_t) dividend
), ABS ((int64_t) divisor
));
273 #endif /* !__tilegx__ */
274 if ((dividend
^ divisor
) < 0)
281 uint64_t __udivdi3 (uint64_t dividend
, uint64_t divisor
);
282 #ifdef L_tile_udivdi3
284 __udivdi3 (uint64_t dividend
, uint64_t divisor
)
286 return __udivdi3_inline (dividend
, divisor
);
290 /*__divdi3 - 64 bit integer signed divide */
291 int64_t __divdi3 (int64_t dividend
, int64_t divisor
);
294 __divdi3 (int64_t dividend
, int64_t divisor
)
296 uint64_t n
= __udivdi3_inline (ABS (dividend
), ABS (divisor
));
297 if ((dividend
^ divisor
) < 0)
304 uint32_t __umodsi3 (uint32_t dividend
, uint32_t divisor
);
305 #ifdef L_tile_umodsi3
307 __umodsi3 (uint32_t dividend
, uint32_t divisor
)
310 return __umodsi3_inline (dividend
, divisor
);
311 #else /* !__tilegx__ */
312 return __umoddi3_inline ((uint64_t) dividend
, (uint64_t) divisor
);
313 #endif /* !__tilegx__ */
318 /* __modsi3 - 32 bit integer signed modulo */
319 int32_t __modsi3 (int32_t dividend
, int32_t divisor
);
322 __modsi3 (int32_t dividend
, int32_t divisor
)
325 uint32_t remainder
= __umodsi3_inline (ABS (dividend
), ABS (divisor
));
326 #else /* !__tilegx__ */
328 __umoddi3_inline (ABS ((int64_t) dividend
), ABS ((int64_t) divisor
));
329 #endif /* !__tilegx__ */
330 return (int32_t) ((dividend
>= 0) ? remainder
: -remainder
);
335 uint64_t __umoddi3 (uint64_t dividend
, uint64_t divisor
);
336 #ifdef L_tile_umoddi3
338 __umoddi3 (uint64_t dividend
, uint64_t divisor
)
340 return __umoddi3_inline (dividend
, divisor
);
345 /* __moddi3 - 64 bit integer signed modulo */
346 int64_t __moddi3 (int64_t dividend
, int64_t divisor
);
349 __moddi3 (int64_t dividend
, int64_t divisor
)
351 uint64_t remainder
= __umoddi3_inline (ABS (dividend
), ABS (divisor
));
352 return (int64_t) ((dividend
>= 0) ? remainder
: -remainder
);