OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libgcc/] [config/] [tilepro/] [softdivide.c] - Blame information for rev 734

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 734 jeremybenn
/* Division and remainder routines for Tile.
2
   Copyright (C) 2011, 2012
3
   Free Software Foundation, Inc.
4
   Contributed by Walter Lee (walt@tilera.com)
5
 
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
9
   later version.
10
 
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.
15
 
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.
19
 
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/>.  */
24
 
25
typedef int int32_t;
26
typedef unsigned uint32_t;
27
typedef long long int64_t;
28
typedef unsigned long long uint64_t;
29
 
30
/* Raise signal 8 (SIGFPE) with code 1 (FPE_INTDIV).  */
31
static inline void
32
raise_intdiv (void)
33
{
34
  asm ("{ raise; moveli zero, 8 + (1 << 6) }");
35
}
36
 
37
 
38
#ifndef __tilegx__
39
/*__udivsi3 - 32 bit integer unsigned divide  */
40
static inline uint32_t __attribute__ ((always_inline))
41
__udivsi3_inline (uint32_t dividend, uint32_t divisor)
42
{
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;
49
 
50
  /* Checks for division by power of two or division by zero.  */
51
  if (divisor <= 1)
52
    {
53
      if (divisor == 0)
54
        {
55
          raise_intdiv ();
56
          return 0;
57
        }
58
      return dividend;
59
    }
60
 
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.
66
 
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,
70
     which is too big.
71
 
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.  */
75
 
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;
81
 
82
  uint32_t quotient = 0;
83
  uint32_t remainder = dividend;
84
 
85
  while (remainder >= divisor)
86
    {
87
      int shift = __insn_clz (remainder);
88
      uint32_t scaled_divisor = max_divisor >> shift;
89
      uint32_t quotient_bit = max_qbit >> shift;
90
 
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;
96
    }
97
  return quotient;
98
}
99
#endif /* !__tilegx__ */
100
 
101
 
102
/* __udivdi3 - 64 bit integer unsigned divide  */
103
static inline uint64_t __attribute__ ((always_inline))
104
__udivdi3_inline (uint64_t dividend, uint64_t divisor)
105
{
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;
112
 
113
  /* Checks for division by power of two or division by zero.  */
114
  if (divisor <= 1)
115
    {
116
      if (divisor == 0)
117
        {
118
          raise_intdiv ();
119
          return 0;
120
        }
121
      return dividend;
122
    }
123
 
124
#ifndef __tilegx__
125
  if (((uint32_t) (dividend >> 32) | ((uint32_t) (divisor >> 32))) == 0)
126
    {
127
      /* Operands both fit in 32 bits, so use faster 32 bit algorithm.  */
128
      return __udivsi3_inline ((uint32_t) dividend, (uint32_t) divisor);
129
    }
130
#endif /* !__tilegx__ */
131
 
132
  /* See algorithm description in __udivsi3  */
133
 
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;
137
 
138
  uint64_t quotient = 0;
139
  uint64_t remainder = dividend;
140
 
141
  while (remainder >= divisor)
142
    {
143
      int shift = __builtin_clzll (remainder);
144
      uint64_t scaled_divisor = max_divisor >> shift;
145
      uint64_t quotient_bit = max_qbit >> shift;
146
 
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;
152
    }
153
  return quotient;
154
}
155
 
156
 
157
#ifndef __tilegx__
158
/* __umodsi3 - 32 bit integer unsigned modulo  */
159
static inline uint32_t __attribute__ ((always_inline))
160
__umodsi3_inline (uint32_t dividend, uint32_t divisor)
161
{
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)
165
    {
166
      if (divisor == 0)
167
        {
168
          raise_intdiv ();
169
          return 0;
170
        }
171
      return dividend & mask;
172
    }
173
 
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.
177
 
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.
181
 
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,
185
     which is too big.
186
 
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);
191
 
192
  uint32_t remainder = dividend;
193
  while (remainder >= divisor)
194
    {
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;
199
    }
200
 
201
  return remainder;
202
}
203
#endif /* !__tilegx__ */
204
 
205
 
206
/* __umoddi3 - 64 bit integer unsigned modulo  */
207
static inline uint64_t __attribute__ ((always_inline))
208
__umoddi3_inline (uint64_t dividend, uint64_t divisor)
209
{
210
#ifndef __tilegx__
211
  if (((uint32_t) (dividend >> 32) | ((uint32_t) (divisor >> 32))) == 0)
212
    {
213
      /* Operands both fit in 32 bits, so use faster 32 bit algorithm.  */
214
      return __umodsi3_inline ((uint32_t) dividend, (uint32_t) divisor);
215
    }
216
#endif /* !__tilegx__ */
217
 
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)
221
    {
222
      if (divisor == 0)
223
        {
224
          raise_intdiv ();
225
          return 0;
226
        }
227
      return dividend & mask;
228
    }
229
 
230
  /* See algorithm description in __umodsi3  */
231
  const uint64_t max_divisor = divisor << __builtin_clzll (divisor);
232
 
233
  uint64_t remainder = dividend;
234
  while (remainder >= divisor)
235
    {
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;
240
    }
241
 
242
  return remainder;
243
}
244
 
245
 
246
uint32_t __udivsi3 (uint32_t dividend, uint32_t divisor);
247
#ifdef L_tile_udivsi3
248
uint32_t
249
__udivsi3 (uint32_t dividend, uint32_t divisor)
250
{
251
#ifndef __tilegx__
252
  return __udivsi3_inline (dividend, divisor);
253
#else /* !__tilegx__ */
254
  uint64_t n = __udivdi3_inline (((uint64_t) dividend), ((uint64_t) divisor));
255
  return (uint32_t) n;
256
#endif /* !__tilegx__ */
257
}
258
#endif
259
 
260
#define ABS(x) ((x) >= 0 ? (x) : -(x))
261
 
262
int32_t __divsi3 (int32_t dividend, int32_t divisor);
263
#ifdef L_tile_divsi3
264
/* __divsi3 - 32 bit integer signed divide  */
265
int32_t
266
__divsi3 (int32_t dividend, int32_t divisor)
267
{
268
#ifndef __tilegx__
269
  uint32_t n = __udivsi3_inline (ABS (dividend), ABS (divisor));
270
#else /* !__tilegx__ */
271
  uint64_t n =
272
    __udivdi3_inline (ABS ((int64_t) dividend), ABS ((int64_t) divisor));
273
#endif /* !__tilegx__ */
274
  if ((dividend ^ divisor) < 0)
275
    n = -n;
276
  return (int32_t) n;
277
}
278
#endif
279
 
280
 
281
uint64_t __udivdi3 (uint64_t dividend, uint64_t divisor);
282
#ifdef L_tile_udivdi3
283
uint64_t
284
__udivdi3 (uint64_t dividend, uint64_t divisor)
285
{
286
  return __udivdi3_inline (dividend, divisor);
287
}
288
#endif
289
 
290
/*__divdi3 - 64 bit integer signed divide  */
291
int64_t __divdi3 (int64_t dividend, int64_t divisor);
292
#ifdef L_tile_divdi3
293
int64_t
294
__divdi3 (int64_t dividend, int64_t divisor)
295
{
296
  uint64_t n = __udivdi3_inline (ABS (dividend), ABS (divisor));
297
  if ((dividend ^ divisor) < 0)
298
    n = -n;
299
  return (int64_t) n;
300
}
301
#endif
302
 
303
 
304
uint32_t __umodsi3 (uint32_t dividend, uint32_t divisor);
305
#ifdef L_tile_umodsi3
306
uint32_t
307
__umodsi3 (uint32_t dividend, uint32_t divisor)
308
{
309
#ifndef __tilegx__
310
  return __umodsi3_inline (dividend, divisor);
311
#else /* !__tilegx__ */
312
  return __umoddi3_inline ((uint64_t) dividend, (uint64_t) divisor);
313
#endif /* !__tilegx__ */
314
}
315
#endif
316
 
317
 
318
/* __modsi3 - 32 bit integer signed modulo  */
319
int32_t __modsi3 (int32_t dividend, int32_t divisor);
320
#ifdef L_tile_modsi3
321
int32_t
322
__modsi3 (int32_t dividend, int32_t divisor)
323
{
324
#ifndef __tilegx__
325
  uint32_t remainder = __umodsi3_inline (ABS (dividend), ABS (divisor));
326
#else /* !__tilegx__ */
327
  uint64_t remainder =
328
    __umoddi3_inline (ABS ((int64_t) dividend), ABS ((int64_t) divisor));
329
#endif /* !__tilegx__ */
330
  return (int32_t) ((dividend >= 0) ? remainder : -remainder);
331
}
332
#endif
333
 
334
 
335
uint64_t __umoddi3 (uint64_t dividend, uint64_t divisor);
336
#ifdef L_tile_umoddi3
337
uint64_t
338
__umoddi3 (uint64_t dividend, uint64_t divisor)
339
{
340
  return __umoddi3_inline (dividend, divisor);
341
}
342
#endif
343
 
344
 
345
/* __moddi3 - 64 bit integer signed modulo  */
346
int64_t __moddi3 (int64_t dividend, int64_t divisor);
347
#ifdef L_tile_moddi3
348
int64_t
349
__moddi3 (int64_t dividend, int64_t divisor)
350
{
351
  uint64_t remainder = __umoddi3_inline (ABS (dividend), ABS (divisor));
352
  return (int64_t) ((dividend >= 0) ? remainder : -remainder);
353
}
354
#endif

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.