Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/tools/polly/lib/External/isl/isl_int_sioimath.h
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Copyright 2015 INRIA Paris-Rocquencourt
3
 *
4
 * Use of this software is governed by the MIT license
5
 *
6
 * Written by Michael Kruse, INRIA Paris-Rocquencourt,
7
 * Domaine de Voluceau, Rocquenqourt, B.P. 105,
8
 * 78153 Le Chesnay Cedex France
9
 */
10
#ifndef ISL_INT_SIOIMATH_H
11
#define ISL_INT_SIOIMATH_H
12
13
#include <inttypes.h>
14
#include <limits.h>
15
#include <stdint.h>
16
#include <stdlib.h>
17
18
#include <isl_imath.h>
19
#include <isl/hash.h>
20
21
40.8M
#define ARRAY_SIZE(array) (sizeof(array)/sizeof(*array))
22
23
/* Visual Studio before VS2015 does not support the inline keyword when
24
 * compiling in C mode because it was introduced in C99 which it does not
25
 * officially support.  Instead, it has a proprietary extension using __inline.
26
 */
27
#if defined(_MSC_VER) && (_MSC_VER < 1900)
28
#define inline __inline
29
#endif
30
31
/* The type to represent integers optimized for small values. It is either a
32
 * pointer to an mp_int ( = mpz_t*; big representation) or an int32_t (small
33
 * represenation) with a discriminator at the least significant bit. In big
34
 * representation it will be always zero because of heap alignment. It is set
35
 * to 1 for small representation and use the 32 most significant bits for the
36
 * int32_t.
37
 *
38
 * Structure on 64 bit machines, with 8-byte aligment (3 bits):
39
 *
40
 * Big representation:
41
 * MSB                                                          LSB
42
 * |------------------------------------------------------------000
43
 * |                            mpz_t*                            |
44
 * |                           != NULL                            |
45
 *
46
 * Small representation:
47
 * MSB                           32                             LSB
48
 * |------------------------------|00000000000000000000000000000001
49
 * |          int32_t             |
50
 * |  2147483647 ... -2147483647  |
51
 *                                                                ^
52
 *                                                                |
53
 *                                                        discriminator bit
54
 *
55
 * On 32 bit machines isl_sioimath type is blown up to 8 bytes, i.e.
56
 * isl_sioimath is guaranteed to be at least 8 bytes. This is to ensure the
57
 * int32_t can be hidden in that type without data loss. In the future we might
58
 * optimize this to use 31 hidden bits in a 32 bit pointer. We may also use 63
59
 * bits on 64 bit machines, but this comes with the cost of additional overflow
60
 * checks because there is no standardized 128 bit integer we could expand to.
61
 *
62
 * We use native integer types and avoid union structures to avoid assumptions
63
 * on the machine's endianness.
64
 *
65
 * This implementation makes the following assumptions:
66
 * - long can represent any int32_t
67
 * - mp_small is signed long
68
 * - mp_usmall is unsigned long
69
 * - adresses returned by malloc are aligned to 2-byte boundaries (leastmost
70
 *   bit is zero)
71
 */
72
#if UINT64_MAX > UINTPTR_MAX
73
typedef uint64_t isl_sioimath;
74
#else
75
typedef uintptr_t isl_sioimath;
76
#endif
77
78
/* The negation of the smallest possible number in int32_t, INT32_MIN
79
 * (0x80000000u, -2147483648), cannot be represented in an int32_t, therefore
80
 * every operation that may produce this value needs to special-case it.
81
 * The operations are:
82
 * abs(INT32_MIN)
83
 * -INT32_MIN   (negation)
84
 * -1 * INT32_MIN (multiplication)
85
 * INT32_MIN/-1 (any division: divexact, fdiv, cdiv, tdiv)
86
 * To avoid checking these cases, we exclude INT32_MIN from small
87
 * representation.
88
 */
89
908M
#define ISL_SIOIMATH_SMALL_MIN (-INT32_MAX)
90
91
/* Largest possible number in small representation */
92
903M
#define ISL_SIOIMATH_SMALL_MAX INT32_MAX
93
94
/* Used for function parameters the function modifies. */
95
typedef isl_sioimath *isl_sioimath_ptr;
96
97
/* Used for function parameters that are read-only. */
98
typedef isl_sioimath isl_sioimath_src;
99
100
/* Return whether the argument is stored in small representation.
101
 */
102
inline int isl_sioimath_is_small(isl_sioimath val)
103
6.48G
{
104
6.48G
  return val & 0x00000001;
105
6.48G
}
106
107
/* Return whether the argument is stored in big representation.
108
 */
109
inline int isl_sioimath_is_big(isl_sioimath val)
110
1.86G
{
111
1.86G
  return !isl_sioimath_is_small(val);
112
1.86G
}
113
114
/* Get the number of an isl_int in small representation. Result is undefined if
115
 * val is not stored in that format.
116
 */
117
inline int32_t isl_sioimath_get_small(isl_sioimath val)
118
4.18G
{
119
4.18G
  return val >> 32;
120
4.18G
}
121
122
/* Get the number of an in isl_int in big representation. Result is undefined if
123
 * val is not stored in that format.
124
 */
125
inline mp_int isl_sioimath_get_big(isl_sioimath val)
126
250M
{
127
250M
  return (mp_int)(uintptr_t) val;
128
250M
}
129
130
/* Return 1 if val is stored in small representation and store its value to
131
 * small. We rely on the compiler to optimize the isl_sioimath_get_small such
132
 * that the shift is moved into the branch that executes in case of small
133
 * representation. If there is no such branch, then a single shift is still
134
 * cheaper than introducing branching code.
135
 */
136
inline int isl_sioimath_decode_small(isl_sioimath val, int32_t *small)
137
3.34G
{
138
3.34G
  *small = isl_sioimath_get_small(val);
139
3.34G
  return isl_sioimath_is_small(val);
140
3.34G
}
141
142
/* Return 1 if val is stored in big representation and store its value to big.
143
 */
144
inline int isl_sioimath_decode_big(isl_sioimath val, mp_int *big)
145
95.4M
{
146
95.4M
  *big = isl_sioimath_get_big(val);
147
95.4M
  return isl_sioimath_is_big(val);
148
95.4M
}
149
150
/* Encode a small representation into an isl_int.
151
 */
152
inline isl_sioimath isl_sioimath_encode_small(int32_t val)
153
2.13G
{
154
2.13G
  return ((isl_sioimath) val) << 32 | 0x00000001;
155
2.13G
}
156
157
/* Encode a big representation.
158
 */
159
inline isl_sioimath isl_sioimath_encode_big(mp_int val)
160
31.7M
{
161
31.7M
  return (isl_sioimath)(uintptr_t) val;
162
31.7M
}
163
164
/* A common situation is to call an IMath function with at least one argument
165
 * that is currently in small representation or an integer parameter, i.e. a big
166
 * representation of the same number is required. Promoting the original
167
 * argument comes with multiple problems, such as modifying a read-only
168
 * argument, the responsibility of deallocation and the execution cost. Instead,
169
 * we make a copy by 'faking' the IMath internal structure.
170
 *
171
 * We reserve the maximum number of required digits on the stack to avoid heap
172
 * allocations.
173
 *
174
 * mp_digit can be uint32_t or uint16_t. This code must work for little and big
175
 * endian digits. The structure for an uint64_t argument and 32-bit mp_digits is
176
 * sketched below.
177
 *
178
 * |----------------------------|
179
 *            uint64_t
180
 *
181
 * |-------------||-------------|
182
 *    mp_digit        mp_digit
183
 *    digits[1]       digits[0]
184
 * Most sig digit  Least sig digit
185
 */
186
typedef struct {
187
  mpz_t big;
188
  mp_digit digits[(sizeof(uintmax_t) + sizeof(mp_digit) - 1) /
189
                  sizeof(mp_digit)];
190
} isl_sioimath_scratchspace_t;
191
192
/* Convert a native integer to IMath's digit representation. A native integer
193
 * might be big- or little endian, but IMath always stores the least significant
194
 * digit in the lowest array indices.  memcpy therefore is not possible.
195
 *
196
 * We also have to consider that long and mp_digit can be of different sizes,
197
 * depending on the compiler (LP64, LLP64) and IMath's USE_64BIT_WORDS. This
198
 * macro should work for all of them.
199
 *
200
 * "used" is set to the number of written digits. It must be minimal (IMath
201
 * checks zeroness using the used field), but always at least one.  Also note
202
 * that the result of num>>(sizeof(num)*CHAR_BIT) is undefined.
203
 */
204
#define ISL_SIOIMATH_TO_DIGITS(num, digits, used)                              \
205
68.5M
  
do 68.5M
{ \
206
68.5M
    int i = 0;                                                     \
207
69.6M
    do {                                                           \
208
69.6M
      (digits)[i] =                                          \
209
69.6M
          ((num) >> (sizeof(mp_digit) * CHAR_BIT * i));      \
210
69.6M
      i += 1;                                                \
211
69.6M
      if (i >= (sizeof(num) + sizeof(mp_digit) - 1) /        \
212
69.6M
                   sizeof(mp_digit))                         \
213
68.3M
        break;                                         \
214
1.30M
      
if (1.30M
((num) >> (sizeof(mp_digit) * CHAR_BIT * i)) == 01.30M
) \
215
187k
        break;                                         \
216
68.5M
    } while (1);                                                   \
217
68.5M
    (used) = i;                                                    \
218
68.5M
  } while (0)
219
220
inline void isl_siomath_uint32_to_digits(uint32_t num, mp_digit *digits,
221
  mp_size *used)
222
67.2M
{
223
67.2M
  ISL_SIOIMATH_TO_DIGITS(num, digits, *used);
224
67.2M
}
225
226
inline void isl_siomath_ulong_to_digits(unsigned long num, mp_digit *digits,
227
  mp_size *used)
228
13.3k
{
229
13.3k
  ISL_SIOIMATH_TO_DIGITS(num, digits, *used);
230
13.3k
}
231
232
inline void isl_siomath_uint64_to_digits(uint64_t num, mp_digit *digits,
233
  mp_size *used)
234
1.29M
{
235
1.29M
  ISL_SIOIMATH_TO_DIGITS(num, digits, *used);
236
1.29M
}
237
238
/* Get the IMath representation of an isl_int without modifying it.
239
 * For the case it is not in big representation yet, pass some scratch space we
240
 * can use to store the big representation in.
241
 * In order to avoid requiring init and free on the scratch space, we directly
242
 * modify the internal representation.
243
 *
244
 * The name derives from its indented use: getting the big representation of an
245
 * input (src) argument.
246
 */
247
inline mp_int isl_sioimath_bigarg_src(isl_sioimath arg,
248
  isl_sioimath_scratchspace_t *scratch)
249
95.4M
{
250
95.4M
  mp_int big;
251
95.4M
  int32_t small;
252
95.4M
  uint32_t num;
253
95.4M
254
95.4M
  if (isl_sioimath_decode_big(arg, &big))
255
55.9M
    return big;
256
95.4M
257
39.5M
  small = isl_sioimath_get_small(arg);
258
39.5M
  scratch->big.digits = scratch->digits;
259
39.5M
  scratch->big.alloc = ARRAY_SIZE(scratch->digits);
260
39.5M
  if (
small >= 039.5M
) {
261
37.1M
    scratch->big.sign = MP_ZPOS;
262
37.1M
    num = small;
263
39.5M
  } else {
264
2.36M
    scratch->big.sign = MP_NEG;
265
2.36M
    num = -small;
266
2.36M
  }
267
39.5M
268
39.5M
  isl_siomath_uint32_to_digits(num, scratch->digits, &scratch->big.used);
269
39.5M
  return &scratch->big;
270
95.4M
}
271
272
/* Create a temporary IMath mp_int for a signed long.
273
 */
274
inline mp_int isl_sioimath_siarg_src(signed long arg,
275
  isl_sioimath_scratchspace_t *scratch)
276
0
{
277
0
  unsigned long num;
278
0
279
0
  scratch->big.digits = scratch->digits;
280
0
  scratch->big.alloc = ARRAY_SIZE(scratch->digits);
281
0
  if (
arg >= 00
) {
282
0
    scratch->big.sign = MP_ZPOS;
283
0
    num = arg;
284
0
  } else {
285
0
    scratch->big.sign = MP_NEG;
286
0
    num = (arg == LONG_MIN) ? 
((unsigned long) LONG_MAX) + 10
:
-arg0
;
287
0
  }
288
0
289
0
  isl_siomath_ulong_to_digits(num, scratch->digits, &scratch->big.used);
290
0
  return &scratch->big;
291
0
}
292
293
/* Create a temporary IMath mp_int for an int64_t.
294
 */
295
inline mp_int isl_sioimath_si64arg_src(int64_t arg,
296
  isl_sioimath_scratchspace_t *scratch)
297
1.29M
{
298
1.29M
  uint64_t num;
299
1.29M
300
1.29M
  scratch->big.digits = scratch->digits;
301
1.29M
  scratch->big.alloc = ARRAY_SIZE(scratch->digits);
302
1.29M
  if (
arg >= 01.29M
) {
303
738k
    scratch->big.sign = MP_ZPOS;
304
738k
    num = arg;
305
1.29M
  } else {
306
555k
    scratch->big.sign = MP_NEG;
307
555k
    num = (arg == INT64_MIN) ? 
((uint64_t) INT64_MAX) + 10
:
-arg555k
;
308
555k
  }
309
1.29M
310
1.29M
  isl_siomath_uint64_to_digits(num, scratch->digits, &scratch->big.used);
311
1.29M
  return &scratch->big;
312
1.29M
}
313
314
/* Create a temporary IMath mp_int for an unsigned long.
315
 */
316
inline mp_int isl_sioimath_uiarg_src(unsigned long arg,
317
  isl_sioimath_scratchspace_t *scratch)
318
13.3k
{
319
13.3k
  scratch->big.digits = scratch->digits;
320
13.3k
  scratch->big.alloc = ARRAY_SIZE(scratch->digits);
321
13.3k
  scratch->big.sign = MP_ZPOS;
322
13.3k
323
13.3k
  isl_siomath_ulong_to_digits(arg, scratch->digits, &scratch->big.used);
324
13.3k
  return &scratch->big;
325
13.3k
}
326
327
/* Ensure big representation. Does not preserve the current number.
328
 * Callers may use the fact that the value _is_ preserved if the presentation
329
 * was big before.
330
 */
331
inline mp_int isl_sioimath_reinit_big(isl_sioimath_ptr ptr)
332
54.4M
{
333
54.4M
  if (isl_sioimath_is_small(*ptr))
334
31.6M
    *ptr = isl_sioimath_encode_big(mp_int_alloc());
335
54.4M
  return isl_sioimath_get_big(*ptr);
336
54.4M
}
337
338
/* Set ptr to a number in small representation.
339
 */
340
inline void isl_sioimath_set_small(isl_sioimath_ptr ptr, int32_t val)
341
1.77G
{
342
1.77G
  if (isl_sioimath_is_big(*ptr))
343
25.8M
    mp_int_free(isl_sioimath_get_big(*ptr));
344
1.77G
  *ptr = isl_sioimath_encode_small(val);
345
1.77G
}
346
347
/* Set ptr to val, choosing small representation if possible.
348
 */
349
inline void isl_sioimath_set_int32(isl_sioimath_ptr ptr, int32_t val)
350
0
{
351
0
  if (
ISL_SIOIMATH_SMALL_MIN0
<= val && 0
val <= 0
ISL_SIOIMATH_SMALL_MAX0
) {
352
0
    isl_sioimath_set_small(ptr, val);
353
0
    return;
354
0
  }
355
0
356
0
  mp_int_init_value(isl_sioimath_reinit_big(ptr), val);
357
0
}
358
359
/* Assign an int64_t number using small representation if possible.
360
 */
361
inline void isl_sioimath_set_int64(isl_sioimath_ptr ptr, int64_t val)
362
720M
{
363
720M
  if (
ISL_SIOIMATH_SMALL_MIN720M
<= val && 720M
val <= 719M
ISL_SIOIMATH_SMALL_MAX719M
) {
364
718M
    isl_sioimath_set_small(ptr, val);
365
718M
    return;
366
718M
  }
367
720M
368
1.29M
  isl_sioimath_scratchspace_t scratch;
369
1.29M
  mp_int_copy(isl_sioimath_si64arg_src(val, &scratch),
370
1.29M
      isl_sioimath_reinit_big(ptr));
371
1.29M
}
372
373
/* Convert to big representation while preserving the current number.
374
 */
375
inline void isl_sioimath_promote(isl_sioimath_ptr dst)
376
0
{
377
0
  int32_t small;
378
0
379
0
  if (isl_sioimath_is_big(*dst))
380
0
    return;
381
0
382
0
  small = isl_sioimath_get_small(*dst);
383
0
  mp_int_set_value(isl_sioimath_reinit_big(dst), small);
384
0
}
385
386
/* Convert to small representation while preserving the current number. Does
387
 * nothing if dst doesn't fit small representation.
388
 */
389
inline void isl_sioimath_try_demote(isl_sioimath_ptr dst)
390
44.5M
{
391
44.5M
  mp_small small;
392
44.5M
393
44.5M
  if (isl_sioimath_is_small(*dst))
394
0
    return;
395
44.5M
396
44.5M
  
if (44.5M
mp_int_to_int(isl_sioimath_get_big(*dst), &small) != MP_OK44.5M
)
397
8.32M
    return;
398
44.5M
399
36.2M
  
if (36.2M
ISL_SIOIMATH_SMALL_MIN36.2M
<= small && 36.2M
small <= 31.2M
ISL_SIOIMATH_SMALL_MAX31.2M
)
400
22.6M
    isl_sioimath_set_small(dst, small);
401
44.5M
}
402
403
/* Initialize an isl_int. The implicit value is 0 in small representation.
404
 */
405
inline void isl_sioimath_init(isl_sioimath_ptr dst)
406
363M
{
407
363M
  *dst = isl_sioimath_encode_small(0);
408
363M
}
409
410
/* Free the resources taken by an isl_int.
411
 */
412
inline void isl_sioimath_clear(isl_sioimath_ptr dst)
413
363M
{
414
363M
  if (isl_sioimath_is_small(*dst))
415
357M
    return;
416
363M
417
5.78M
  mp_int_free(isl_sioimath_get_big(*dst));
418
5.78M
}
419
420
/* Copy the value of one isl_int to another.
421
 */
422
inline void isl_sioimath_set(isl_sioimath_ptr dst, isl_sioimath_src val)
423
576M
{
424
576M
  if (
isl_sioimath_is_small(val)576M
) {
425
569M
    isl_sioimath_set_small(dst, isl_sioimath_get_small(val));
426
569M
    return;
427
569M
  }
428
576M
429
7.35M
  mp_int_copy(isl_sioimath_get_big(val), isl_sioimath_reinit_big(dst));
430
7.35M
}
431
432
/* Store a signed long into an isl_int.
433
 */
434
inline void isl_sioimath_set_si(isl_sioimath_ptr dst, long val)
435
151M
{
436
151M
  if (
ISL_SIOIMATH_SMALL_MIN151M
<= val && 151M
val <= 151M
ISL_SIOIMATH_SMALL_MAX151M
) {
437
151M
    isl_sioimath_set_small(dst, val);
438
151M
    return;
439
151M
  }
440
151M
441
0
  mp_int_set_value(isl_sioimath_reinit_big(dst), val);
442
0
}
443
444
/* Store an unsigned long into an isl_int.
445
 */
446
inline void isl_sioimath_set_ui(isl_sioimath_ptr dst, unsigned long val)
447
6.36k
{
448
6.36k
  if (
val <= 6.36k
ISL_SIOIMATH_SMALL_MAX6.36k
) {
449
6.36k
    isl_sioimath_set_small(dst, val);
450
6.36k
    return;
451
6.36k
  }
452
6.36k
453
0
  mp_int_set_uvalue(isl_sioimath_reinit_big(dst), val);
454
0
}
455
456
/* Return whether a number can be represented by a signed long.
457
 */
458
inline int isl_sioimath_fits_slong(isl_sioimath_src val)
459
2.50k
{
460
2.50k
  mp_small dummy;
461
2.50k
462
2.50k
  if (isl_sioimath_is_small(val))
463
2.50k
    return 1;
464
2.50k
465
0
  return mp_int_to_int(isl_sioimath_get_big(val), &dummy) == MP_OK;
466
2.50k
}
467
468
/* Return a number as signed long. Result is undefined if the number cannot be
469
 * represented as long.
470
 */
471
inline long isl_sioimath_get_si(isl_sioimath_src val)
472
3.15k
{
473
3.15k
  mp_small result;
474
3.15k
475
3.15k
  if (isl_sioimath_is_small(val))
476
3.15k
    return isl_sioimath_get_small(val);
477
3.15k
478
0
  mp_int_to_int(isl_sioimath_get_big(val), &result);
479
0
  return result;
480
3.15k
}
481
482
/* Return whether a number can be represented as unsigned long.
483
 */
484
inline int isl_sioimath_fits_ulong(isl_sioimath_src val)
485
6.03k
{
486
6.03k
  mp_usmall dummy;
487
6.03k
488
6.03k
  if (isl_sioimath_is_small(val))
489
6.03k
    return isl_sioimath_get_small(val) >= 0;
490
6.03k
491
0
  return mp_int_to_uint(isl_sioimath_get_big(val), &dummy) == MP_OK;
492
6.03k
}
493
494
/* Return a number as unsigned long. Result is undefined if the number cannot be
495
 * represented as unsigned long.
496
 */
497
inline unsigned long isl_sioimath_get_ui(isl_sioimath_src val)
498
6.03k
{
499
6.03k
  mp_usmall result;
500
6.03k
501
6.03k
  if (isl_sioimath_is_small(val))
502
6.03k
    return isl_sioimath_get_small(val);
503
6.03k
504
0
  mp_int_to_uint(isl_sioimath_get_big(val), &result);
505
0
  return result;
506
6.03k
}
507
508
/* Return a number as floating point value.
509
 */
510
inline double isl_sioimath_get_d(isl_sioimath_src val)
511
0
{
512
0
  mp_int big;
513
0
  double result = 0;
514
0
  int i;
515
0
516
0
  if (isl_sioimath_is_small(val))
517
0
    return isl_sioimath_get_small(val);
518
0
519
0
  big = isl_sioimath_get_big(val);
520
0
  for (i = 0; 
i < big->used0
;
++i0
)
521
0
    
result = result * (double) ((uintmax_t) 0
MP_DIGIT_MAX0
+ 1) +
522
0
             (double) big->digits[i];
523
0
524
0
  if (big->sign == MP_NEG)
525
0
    result = -result;
526
0
527
0
  return result;
528
0
}
529
530
/* Format a number as decimal string.
531
 *
532
 * The largest possible string from small representation is 12 characters
533
 * ("-2147483647").
534
 */
535
inline char *isl_sioimath_get_str(isl_sioimath_src val)
536
16.8k
{
537
16.8k
  char *result;
538
16.8k
539
16.8k
  if (
isl_sioimath_is_small(val)16.8k
) {
540
15.4k
    result = malloc(12);
541
15.4k
    snprintf(result, 12, "%" PRIi32, isl_sioimath_get_small(val));
542
15.4k
    return result;
543
15.4k
  }
544
16.8k
545
1.43k
  return impz_get_str(NULL, 10, isl_sioimath_get_big(val));
546
16.8k
}
547
548
/* Return the absolute value.
549
 */
550
inline void isl_sioimath_abs(isl_sioimath_ptr dst, isl_sioimath_src arg)
551
29.5M
{
552
29.5M
  if (
isl_sioimath_is_small(arg)29.5M
) {
553
29.0M
    isl_sioimath_set_small(dst, labs(isl_sioimath_get_small(arg)));
554
29.0M
    return;
555
29.0M
  }
556
29.5M
557
461k
  mp_int_abs(isl_sioimath_get_big(arg), isl_sioimath_reinit_big(dst));
558
461k
}
559
560
/* Return the negation of a number.
561
 */
562
inline void isl_sioimath_neg(isl_sioimath_ptr dst, isl_sioimath_src arg)
563
202M
{
564
202M
  if (
isl_sioimath_is_small(arg)202M
) {
565
201M
    isl_sioimath_set_small(dst, -isl_sioimath_get_small(arg));
566
201M
    return;
567
201M
  }
568
202M
569
802k
  mp_int_neg(isl_sioimath_get_big(arg), isl_sioimath_reinit_big(dst));
570
802k
}
571
572
/* Swap two isl_ints.
573
 *
574
 * isl_sioimath can be copied bytewise; nothing depends on its address. It can
575
 * also be stored in a CPU register.
576
 */
577
inline void isl_sioimath_swap(isl_sioimath_ptr lhs, isl_sioimath_ptr rhs)
578
68.2M
{
579
68.2M
  isl_sioimath tmp = *lhs;
580
68.2M
  *lhs = *rhs;
581
68.2M
  *rhs = tmp;
582
68.2M
}
583
584
/* Add an unsigned long to the number.
585
 *
586
 * On LP64 unsigned long exceeds the range of an int64_t, therefore we check in
587
 * advance whether small representation possibly overflows.
588
 */
589
inline void isl_sioimath_add_ui(isl_sioimath_ptr dst, isl_sioimath lhs,
590
  unsigned long rhs)
591
584k
{
592
584k
  int32_t smalllhs;
593
584k
  isl_sioimath_scratchspace_t lhsscratch;
594
584k
595
584k
  if (isl_sioimath_decode_small(lhs, &smalllhs) &&
596
584k
      
(rhs <= (uint64_t) INT64_MAX - (uint64_t) 515k
ISL_SIOIMATH_SMALL_MAX515k
)) {
597
515k
    isl_sioimath_set_int64(dst, (int64_t) smalllhs + rhs);
598
515k
    return;
599
515k
  }
600
584k
601
69.5k
  impz_add_ui(isl_sioimath_reinit_big(dst),
602
69.5k
      isl_sioimath_bigarg_src(lhs, &lhsscratch), rhs);
603
69.5k
  isl_sioimath_try_demote(dst);
604
69.5k
}
605
606
/* Subtract an unsigned long.
607
 *
608
 * On LP64 unsigned long exceeds the range of an int64_t.  If
609
 * ISL_SIOIMATH_SMALL_MIN-rhs>=INT64_MIN we can do the calculation using int64_t
610
 * without risking an overflow.
611
 */
612
inline void isl_sioimath_sub_ui(isl_sioimath_ptr dst, isl_sioimath lhs,
613
        unsigned long rhs)
614
669k
{
615
669k
  int32_t smalllhs;
616
669k
  isl_sioimath_scratchspace_t lhsscratch;
617
669k
618
669k
  if (isl_sioimath_decode_small(lhs, &smalllhs) &&
619
669k
      
(rhs < (uint64_t) INT64_MIN - (uint64_t) 568k
ISL_SIOIMATH_SMALL_MIN568k
)) {
620
568k
    isl_sioimath_set_int64(dst, (int64_t) smalllhs - rhs);
621
568k
    return;
622
568k
  }
623
669k
624
101k
  impz_sub_ui(isl_sioimath_reinit_big(dst),
625
101k
      isl_sioimath_bigarg_src(lhs, &lhsscratch), rhs);
626
101k
  isl_sioimath_try_demote(dst);
627
101k
}
628
629
/* Sum of two isl_ints.
630
 */
631
inline void isl_sioimath_add(isl_sioimath_ptr dst, isl_sioimath_src lhs,
632
  isl_sioimath_src rhs)
633
283M
{
634
283M
  isl_sioimath_scratchspace_t scratchlhs, scratchrhs;
635
283M
  int32_t smalllhs, smallrhs;
636
283M
637
283M
  if (isl_sioimath_decode_small(lhs, &smalllhs) &&
638
283M
      
isl_sioimath_decode_small(rhs, &smallrhs)272M
) {
639
270M
    isl_sioimath_set_int64(
640
270M
        dst, (int64_t) smalllhs + (int64_t) smallrhs);
641
270M
    return;
642
270M
  }
643
283M
644
13.2M
  mp_int_add(isl_sioimath_bigarg_src(lhs, &scratchlhs),
645
13.2M
      isl_sioimath_bigarg_src(rhs, &scratchrhs),
646
13.2M
      isl_sioimath_reinit_big(dst));
647
13.2M
  isl_sioimath_try_demote(dst);
648
13.2M
}
649
650
/* Subtract two isl_ints.
651
 */
652
inline void isl_sioimath_sub(isl_sioimath_ptr dst, isl_sioimath_src lhs,
653
  isl_sioimath_src rhs)
654
8.32M
{
655
8.32M
  isl_sioimath_scratchspace_t scratchlhs, scratchrhs;
656
8.32M
  int32_t smalllhs, smallrhs;
657
8.32M
658
8.32M
  if (isl_sioimath_decode_small(lhs, &smalllhs) &&
659
8.32M
      
isl_sioimath_decode_small(rhs, &smallrhs)7.96M
) {
660
7.84M
    isl_sioimath_set_int64(
661
7.84M
        dst, (int64_t) smalllhs - (int64_t) smallrhs);
662
7.84M
    return;
663
7.84M
  }
664
8.32M
665
482k
  mp_int_sub(isl_sioimath_bigarg_src(lhs, &scratchlhs),
666
482k
      isl_sioimath_bigarg_src(rhs, &scratchrhs),
667
482k
      isl_sioimath_reinit_big(dst));
668
482k
  isl_sioimath_try_demote(dst);
669
482k
}
670
671
/* Multiply two isl_ints.
672
 */
673
inline void isl_sioimath_mul(isl_sioimath_ptr dst, isl_sioimath_src lhs,
674
  isl_sioimath_src rhs)
675
455M
{
676
455M
  isl_sioimath_scratchspace_t scratchlhs, scratchrhs;
677
455M
  int32_t smalllhs, smallrhs;
678
455M
679
455M
  if (isl_sioimath_decode_small(lhs, &smalllhs) &&
680
455M
      
isl_sioimath_decode_small(rhs, &smallrhs)439M
) {
681
431M
    isl_sioimath_set_int64(
682
431M
        dst, (int64_t) smalllhs * (int64_t) smallrhs);
683
431M
    return;
684
431M
  }
685
455M
686
24.2M
  mp_int_mul(isl_sioimath_bigarg_src(lhs, &scratchlhs),
687
24.2M
      isl_sioimath_bigarg_src(rhs, &scratchrhs),
688
24.2M
      isl_sioimath_reinit_big(dst));
689
24.2M
  isl_sioimath_try_demote(dst);
690
24.2M
}
691
692
/* Shift lhs by rhs bits to the left and store the result in dst. Effectively,
693
 * this operation computes 'lhs * 2^rhs'.
694
 */
695
inline void isl_sioimath_mul_2exp(isl_sioimath_ptr dst, isl_sioimath lhs,
696
  unsigned long rhs)
697
6.03k
{
698
6.03k
  isl_sioimath_scratchspace_t scratchlhs;
699
6.03k
  int32_t smalllhs;
700
6.03k
701
6.03k
  if (
isl_sioimath_decode_small(lhs, &smalllhs) && 6.03k
(rhs <= 32ul)6.03k
) {
702
2.09k
    isl_sioimath_set_int64(dst, ((int64_t) smalllhs) << rhs);
703
2.09k
    return;
704
2.09k
  }
705
6.03k
706
3.94k
  mp_int_mul_pow2(isl_sioimath_bigarg_src(lhs, &scratchlhs), rhs,
707
3.94k
      isl_sioimath_reinit_big(dst));
708
3.94k
}
709
710
/* Multiply an isl_int and a signed long.
711
 */
712
inline void isl_sioimath_mul_si(isl_sioimath_ptr dst, isl_sioimath lhs,
713
  signed long rhs)
714
367
{
715
367
  isl_sioimath_scratchspace_t scratchlhs, scratchrhs;
716
367
  int32_t smalllhs;
717
367
718
367
  if (
isl_sioimath_decode_small(lhs, &smalllhs) && 367
(rhs > LONG_MIN)367
&&
719
367
      
(labs(rhs) <= UINT32_MAX)367
) {
720
367
    isl_sioimath_set_int64(dst, (int64_t) smalllhs * (int64_t) rhs);
721
367
    return;
722
367
  }
723
367
724
0
  mp_int_mul(isl_sioimath_bigarg_src(lhs, &scratchlhs),
725
0
      isl_sioimath_siarg_src(rhs, &scratchrhs),
726
0
      isl_sioimath_reinit_big(dst));
727
0
  isl_sioimath_try_demote(dst);
728
0
}
729
730
/* Multiply an isl_int and an unsigned long.
731
 */
732
inline void isl_sioimath_mul_ui(isl_sioimath_ptr dst, isl_sioimath lhs,
733
  unsigned long rhs)
734
230k
{
735
230k
  isl_sioimath_scratchspace_t scratchlhs, scratchrhs;
736
230k
  int32_t smalllhs;
737
230k
738
230k
  if (
isl_sioimath_decode_small(lhs, &smalllhs) && 230k
(rhs <= UINT32_MAX)220k
) {
739
220k
    isl_sioimath_set_int64(dst, (int64_t) smalllhs * (int64_t) rhs);
740
220k
    return;
741
220k
  }
742
230k
743
9.65k
  mp_int_mul(isl_sioimath_bigarg_src(lhs, &scratchlhs),
744
9.65k
      isl_sioimath_uiarg_src(rhs, &scratchrhs),
745
9.65k
      isl_sioimath_reinit_big(dst));
746
9.65k
  isl_sioimath_try_demote(dst);
747
9.65k
}
748
749
/* Compute the power of an isl_int to an unsigned long.
750
 * Always let IMath do it; the result is unlikely to be small except in some
751
 * special cases.
752
 * Note: 0^0 == 1
753
 */
754
inline void isl_sioimath_pow_ui(isl_sioimath_ptr dst, isl_sioimath_src lhs,
755
  unsigned long rhs)
756
0
{
757
0
  isl_sioimath_scratchspace_t scratchlhs, scratchrhs;
758
0
  int32_t smalllhs;
759
0
760
0
  switch (rhs) {
761
0
  case 0:
762
0
    isl_sioimath_set_small(dst, 1);
763
0
    return;
764
0
  case 1:
765
0
    isl_sioimath_set(dst, lhs);
766
0
    return;
767
0
  case 2:
768
0
    isl_sioimath_mul(dst, lhs, lhs);
769
0
    return;
770
0
  }
771
0
772
0
  
if (0
isl_sioimath_decode_small(lhs, &smalllhs)0
) {
773
0
    switch (smalllhs) {
774
0
    case 0:
775
0
      isl_sioimath_set_small(dst, 0);
776
0
      return;
777
0
    case 1:
778
0
      isl_sioimath_set_small(dst, 1);
779
0
      return;
780
0
    case 2:
781
0
      isl_sioimath_set_small(dst, 1);
782
0
      isl_sioimath_mul_2exp(dst, *dst, rhs);
783
0
      return;
784
0
    default:
785
0
      if (
(0
MP_SMALL_MIN0
<= rhs) &&
(rhs <= 0
MP_SMALL_MAX0
)) {
786
0
        mp_int_expt_value(smalllhs, rhs,
787
0
            isl_sioimath_reinit_big(dst));
788
0
        isl_sioimath_try_demote(dst);
789
0
        return;
790
0
      }
791
0
    }
792
0
  }
793
0
794
0
  mp_int_expt_full(isl_sioimath_bigarg_src(lhs, &scratchlhs),
795
0
      isl_sioimath_uiarg_src(rhs, &scratchrhs),
796
0
      isl_sioimath_reinit_big(dst));
797
0
  isl_sioimath_try_demote(dst);
798
0
}
799
800
/* Fused multiply-add.
801
 */
802
inline void isl_sioimath_addmul(isl_sioimath_ptr dst, isl_sioimath_src lhs,
803
  isl_sioimath_src rhs)
804
276M
{
805
276M
  isl_sioimath tmp;
806
276M
  isl_sioimath_init(&tmp);
807
276M
  isl_sioimath_mul(&tmp, lhs, rhs);
808
276M
  isl_sioimath_add(dst, *dst, tmp);
809
276M
  isl_sioimath_clear(&tmp);
810
276M
}
811
812
/* Fused multiply-add with an unsigned long.
813
 */
814
inline void isl_sioimath_addmul_ui(isl_sioimath_ptr dst, isl_sioimath_src lhs,
815
  unsigned long rhs)
816
5.12k
{
817
5.12k
  isl_sioimath tmp;
818
5.12k
  isl_sioimath_init(&tmp);
819
5.12k
  isl_sioimath_mul_ui(&tmp, lhs, rhs);
820
5.12k
  isl_sioimath_add(dst, *dst, tmp);
821
5.12k
  isl_sioimath_clear(&tmp);
822
5.12k
}
823
824
/* Fused multiply-subtract.
825
 */
826
inline void isl_sioimath_submul(isl_sioimath_ptr dst, isl_sioimath_src lhs,
827
  isl_sioimath_src rhs)
828
7.83M
{
829
7.83M
  isl_sioimath tmp;
830
7.83M
  isl_sioimath_init(&tmp);
831
7.83M
  isl_sioimath_mul(&tmp, lhs, rhs);
832
7.83M
  isl_sioimath_sub(dst, *dst, tmp);
833
7.83M
  isl_sioimath_clear(&tmp);
834
7.83M
}
835
836
/* Fused multiply-add with an unsigned long.
837
 */
838
inline void isl_sioimath_submul_ui(isl_sioimath_ptr dst, isl_sioimath_src lhs,
839
  unsigned long rhs)
840
180
{
841
180
  isl_sioimath tmp;
842
180
  isl_sioimath_init(&tmp);
843
180
  isl_sioimath_mul_ui(&tmp, lhs, rhs);
844
180
  isl_sioimath_sub(dst, *dst, tmp);
845
180
  isl_sioimath_clear(&tmp);
846
180
}
847
848
void isl_sioimath_gcd(isl_sioimath_ptr dst, isl_sioimath_src lhs,
849
          isl_sioimath_src rhs);
850
void isl_sioimath_lcm(isl_sioimath_ptr dst, isl_sioimath_src lhs,
851
          isl_sioimath_src rhs);
852
853
/* Divide lhs by rhs, rounding to zero (Truncate).
854
 */
855
inline void isl_sioimath_tdiv_q(isl_sioimath_ptr dst, isl_sioimath_src lhs,
856
  isl_sioimath_src rhs)
857
64.4M
{
858
64.4M
  isl_sioimath_scratchspace_t lhsscratch, rhsscratch;
859
64.4M
  int32_t lhssmall, rhssmall;
860
64.4M
861
64.4M
  if (isl_sioimath_decode_small(lhs, &lhssmall) &&
862
64.4M
      
isl_sioimath_decode_small(rhs, &rhssmall)61.6M
) {
863
60.9M
    isl_sioimath_set_small(dst, lhssmall / rhssmall);
864
60.9M
    return;
865
60.9M
  }
866
64.4M
867
3.51M
  mp_int_div(isl_sioimath_bigarg_src(lhs, &lhsscratch),
868
3.51M
      isl_sioimath_bigarg_src(rhs, &rhsscratch),
869
3.51M
      isl_sioimath_reinit_big(dst), NULL);
870
3.51M
  isl_sioimath_try_demote(dst);
871
3.51M
  return;
872
64.4M
}
873
874
/* Divide lhs by an unsigned long rhs, rounding to zero (Truncate).
875
 */
876
inline void isl_sioimath_tdiv_q_ui(isl_sioimath_ptr dst, isl_sioimath_src lhs,
877
  unsigned long rhs)
878
215k
{
879
215k
  isl_sioimath_scratchspace_t lhsscratch, rhsscratch;
880
215k
  int32_t lhssmall;
881
215k
882
215k
  if (
isl_sioimath_is_small(lhs) && 215k
(rhs <= (unsigned long) INT32_MAX)204k
) {
883
204k
    lhssmall = isl_sioimath_get_small(lhs);
884
204k
    isl_sioimath_set_small(dst, lhssmall / (int32_t) rhs);
885
204k
    return;
886
204k
  }
887
215k
888
11.0k
  
if (11.0k
rhs <= 11.0k
MP_SMALL_MAX11.0k
) {
889
11.0k
    mp_int_div_value(isl_sioimath_bigarg_src(lhs, &lhsscratch), rhs,
890
11.0k
        isl_sioimath_reinit_big(dst), NULL);
891
11.0k
    isl_sioimath_try_demote(dst);
892
11.0k
    return;
893
11.0k
  }
894
11.0k
895
0
  mp_int_div(isl_sioimath_bigarg_src(lhs, &lhsscratch),
896
0
      isl_sioimath_uiarg_src(rhs, &rhsscratch),
897
0
      isl_sioimath_reinit_big(dst), NULL);
898
0
  isl_sioimath_try_demote(dst);
899
0
}
900
901
/* Divide lhs by rhs, rounding to positive infinity (Ceil).
902
 */
903
inline void isl_sioimath_cdiv_q(isl_sioimath_ptr dst, isl_sioimath_src lhs,
904
  isl_sioimath_src rhs)
905
283k
{
906
283k
  int32_t lhssmall, rhssmall;
907
283k
  isl_sioimath_scratchspace_t lhsscratch, rhsscratch;
908
283k
  int32_t q;
909
283k
910
283k
  if (isl_sioimath_decode_small(lhs, &lhssmall) &&
911
283k
      
isl_sioimath_decode_small(rhs, &rhssmall)229k
) {
912
229k
    if (
(lhssmall >= 0) && 229k
(rhssmall >= 0)147k
)
913
147k
      q = ((int64_t) lhssmall + (int64_t) rhssmall - 1) /
914
147k
          rhssmall;
915
82.0k
    else 
if (82.0k
(lhssmall < 0) && 82.0k
(rhssmall < 0)82.0k
)
916
0
      q = ((int64_t) lhssmall + (int64_t) rhssmall + 1) /
917
0
          rhssmall;
918
82.0k
    else
919
82.0k
      q = lhssmall / rhssmall;
920
229k
    isl_sioimath_set_small(dst, q);
921
229k
    return;
922
229k
  }
923
283k
924
53.5k
  impz_cdiv_q(isl_sioimath_reinit_big(dst),
925
53.5k
      isl_sioimath_bigarg_src(lhs, &lhsscratch),
926
53.5k
      isl_sioimath_bigarg_src(rhs, &rhsscratch));
927
53.5k
  isl_sioimath_try_demote(dst);
928
53.5k
}
929
930
/* Compute the division of lhs by a rhs of type unsigned long, rounding towards
931
 * positive infinity (Ceil).
932
 */
933
inline void isl_sioimath_cdiv_q_ui(isl_sioimath_ptr dst, isl_sioimath_src lhs,
934
  unsigned long rhs)
935
367
{
936
367
  isl_sioimath_scratchspace_t lhsscratch, rhsscratch;
937
367
  int32_t lhssmall, q;
938
367
939
367
  if (
isl_sioimath_decode_small(lhs, &lhssmall) && 367
(rhs <= INT32_MAX)367
) {
940
367
    if (lhssmall >= 0)
941
155
      q = ((int64_t) lhssmall + ((int64_t) rhs - 1)) /
942
155
          (int64_t) rhs;
943
367
    else
944
212
      q = lhssmall / (int32_t) rhs;
945
367
    isl_sioimath_set_small(dst, q);
946
367
    return;
947
367
  }
948
367
949
0
  impz_cdiv_q(isl_sioimath_reinit_big(dst),
950
0
      isl_sioimath_bigarg_src(lhs, &lhsscratch),
951
0
      isl_sioimath_uiarg_src(rhs, &rhsscratch));
952
0
  isl_sioimath_try_demote(dst);
953
0
}
954
955
/* Divide lhs by rhs, rounding to negative infinity (Floor).
956
 */
957
inline void isl_sioimath_fdiv_q(isl_sioimath_ptr dst, isl_sioimath_src lhs,
958
  isl_sioimath_src rhs)
959
1.02M
{
960
1.02M
  isl_sioimath_scratchspace_t lhsscratch, rhsscratch;
961
1.02M
  int32_t lhssmall, rhssmall;
962
1.02M
  int32_t q;
963
1.02M
964
1.02M
  if (isl_sioimath_decode_small(lhs, &lhssmall) &&
965
1.02M
      
isl_sioimath_decode_small(rhs, &rhssmall)835k
) {
966
820k
    if (
(lhssmall < 0) && 820k
(rhssmall >= 0)211k
)
967
211k
      q = ((int64_t) lhssmall - ((int64_t) rhssmall - 1)) /
968
211k
          rhssmall;
969
608k
    else 
if (608k
(lhssmall >= 0) && 608k
(rhssmall < 0)608k
)
970
0
      q = ((int64_t) lhssmall - ((int64_t) rhssmall + 1)) /
971
0
          rhssmall;
972
608k
    else
973
608k
      q = lhssmall / rhssmall;
974
820k
    isl_sioimath_set_small(dst, q);
975
820k
    return;
976
820k
  }
977
1.02M
978
203k
  impz_fdiv_q(isl_sioimath_reinit_big(dst),
979
203k
      isl_sioimath_bigarg_src(lhs, &lhsscratch),
980
203k
      isl_sioimath_bigarg_src(rhs, &rhsscratch));
981
203k
  isl_sioimath_try_demote(dst);
982
203k
}
983
984
/* Compute the division of lhs by a rhs of type unsigned long, rounding towards
985
 * negative infinity (Floor).
986
 */
987
inline void isl_sioimath_fdiv_q_ui(isl_sioimath_ptr dst, isl_sioimath_src lhs,
988
  unsigned long rhs)
989
47.1k
{
990
47.1k
  isl_sioimath_scratchspace_t lhsscratch, rhsscratch;
991
47.1k
  int32_t lhssmall, q;
992
47.1k
993
47.1k
  if (
isl_sioimath_decode_small(lhs, &lhssmall) && 47.1k
(rhs <= INT32_MAX)43.4k
) {
994
43.4k
    if (lhssmall >= 0)
995
37.8k
      q = (uint32_t) lhssmall / rhs;
996
43.4k
    else
997
5.60k
      q = ((int64_t) lhssmall - ((int64_t) rhs - 1)) /
998
5.60k
          (int64_t) rhs;
999
43.4k
    isl_sioimath_set_small(dst, q);
1000
43.4k
    return;
1001
43.4k
  }
1002
47.1k
1003
3.66k
  impz_fdiv_q(isl_sioimath_reinit_big(dst),
1004
3.66k
      isl_sioimath_bigarg_src(lhs, &lhsscratch),
1005
3.66k
      isl_sioimath_uiarg_src(rhs, &rhsscratch));
1006
3.66k
  isl_sioimath_try_demote(dst);
1007
3.66k
}
1008
1009
/* Get the remainder of: lhs divided by rhs rounded towards negative infinite
1010
 * (Floor).
1011
 */
1012
inline void isl_sioimath_fdiv_r(isl_sioimath_ptr dst, isl_sioimath_src lhs,
1013
  isl_sioimath_src rhs)
1014
120k
{
1015
120k
  isl_sioimath_scratchspace_t lhsscratch, rhsscratch;
1016
120k
  int64_t lhssmall, rhssmall;
1017
120k
  int32_t r;
1018
120k
1019
120k
  if (
isl_sioimath_is_small(lhs) && 120k
isl_sioimath_is_small(rhs)117k
) {
1020
112k
    lhssmall = isl_sioimath_get_small(lhs);
1021
112k
    rhssmall = isl_sioimath_get_small(rhs);
1022
112k
    r = (rhssmall + lhssmall % rhssmall) % rhssmall;
1023
112k
    isl_sioimath_set_small(dst, r);
1024
112k
    return;
1025
112k
  }
1026
120k
1027
7.24k
  impz_fdiv_r(isl_sioimath_reinit_big(dst),
1028
7.24k
      isl_sioimath_bigarg_src(lhs, &lhsscratch),
1029
7.24k
      isl_sioimath_bigarg_src(rhs, &rhsscratch));
1030
7.24k
  isl_sioimath_try_demote(dst);
1031
7.24k
}
1032
1033
void isl_sioimath_read(isl_sioimath_ptr dst, const char *str);
1034
1035
/* Return:
1036
 *   +1 for a positive number
1037
 *   -1 for a negative number
1038
 *    0 if the number is zero
1039
 */
1040
inline int isl_sioimath_sgn(isl_sioimath_src arg)
1041
1.18G
{
1042
1.18G
  int32_t small;
1043
1.18G
1044
1.18G
  if (isl_sioimath_decode_small(arg, &small))
1045
1.17G
    return (small > 0) - (small < 0);
1046
1.18G
1047
11.7M
  return mp_int_compare_zero(isl_sioimath_get_big(arg));
1048
1.18G
}
1049
1050
/* Return:
1051
 *   +1 if lhs > rhs
1052
 *   -1 if lhs < rhs
1053
 *    0 if lhs = rhs
1054
 */
1055
inline int isl_sioimath_cmp(isl_sioimath_src lhs, isl_sioimath_src rhs)
1056
137M
{
1057
137M
  isl_sioimath_scratchspace_t lhsscratch, rhsscratch;
1058
137M
  int32_t lhssmall, rhssmall;
1059
137M
1060
137M
  if (isl_sioimath_decode_small(lhs, &lhssmall) &&
1061
137M
      isl_sioimath_decode_small(rhs, &rhssmall))
1062
137M
    return (lhssmall > rhssmall) - (lhssmall < rhssmall);
1063
137M
1064
453k
  
if (453k
isl_sioimath_decode_small(rhs, &rhssmall)453k
)
1065
157k
    return mp_int_compare_value(
1066
157k
        isl_sioimath_bigarg_src(lhs, &lhsscratch), rhssmall);
1067
453k
1068
296k
  
if (296k
isl_sioimath_decode_small(lhs, &lhssmall)296k
)
1069
33.8k
    return -mp_int_compare_value(
1070
33.8k
               isl_sioimath_bigarg_src(rhs, &rhsscratch), lhssmall);
1071
296k
1072
262k
  return mp_int_compare(
1073
262k
      isl_sioimath_get_big(lhs), isl_sioimath_get_big(rhs));
1074
137M
}
1075
1076
/* As isl_sioimath_cmp, but with signed long rhs.
1077
 */
1078
inline int isl_sioimath_cmp_si(isl_sioimath_src lhs, signed long rhs)
1079
125M
{
1080
125M
  int32_t lhssmall;
1081
125M
1082
125M
  if (isl_sioimath_decode_small(lhs, &lhssmall))
1083
122M
    return (lhssmall > rhs) - (lhssmall < rhs);
1084
125M
1085
3.05M
  return mp_int_compare_value(isl_sioimath_get_big(lhs), rhs);
1086
125M
}
1087
1088
/* Return:
1089
 *   +1 if |lhs| > |rhs|
1090
 *   -1 if |lhs| < |rhs|
1091
 *    0 if |lhs| = |rhs|
1092
 */
1093
inline int isl_sioimath_abs_cmp(isl_sioimath_src lhs, isl_sioimath_src rhs)
1094
39.4M
{
1095
39.4M
  isl_sioimath_scratchspace_t lhsscratch, rhsscratch;
1096
39.4M
  int32_t lhssmall, rhssmall;
1097
39.4M
1098
39.4M
  if (isl_sioimath_decode_small(lhs, &lhssmall) &&
1099
39.4M
      
isl_sioimath_decode_small(rhs, &rhssmall)36.7M
) {
1100
36.4M
    lhssmall = labs(lhssmall);
1101
36.4M
    rhssmall = labs(rhssmall);
1102
36.4M
    return (lhssmall > rhssmall) - (lhssmall < rhssmall);
1103
36.4M
  }
1104
39.4M
1105
3.01M
  return mp_int_compare_unsigned(
1106
3.01M
      isl_sioimath_bigarg_src(lhs, &lhsscratch),
1107
3.01M
      isl_sioimath_bigarg_src(rhs, &rhsscratch));
1108
39.4M
}
1109
1110
/* Return whether lhs is divisible by rhs.
1111
 * In particular, can rhs be multiplied by some integer to result in lhs?
1112
 * If rhs is zero, then this means lhs has to be zero too.
1113
 */
1114
inline int isl_sioimath_is_divisible_by(isl_sioimath_src lhs,
1115
          isl_sioimath_src rhs)
1116
4.17M
{
1117
4.17M
  isl_sioimath_scratchspace_t lhsscratch, rhsscratch;
1118
4.17M
  int32_t lhssmall, rhssmall;
1119
4.17M
  mpz_t rem;
1120
4.17M
  int cmp;
1121
4.17M
1122
4.17M
  if (isl_sioimath_sgn(rhs) == 0)
1123
0
    return isl_sioimath_sgn(lhs) == 0;
1124
4.17M
1125
4.17M
  
if (4.17M
isl_sioimath_decode_small(lhs, &lhssmall) &&
1126
4.10M
      isl_sioimath_decode_small(rhs, &rhssmall))
1127
4.09M
    return lhssmall % rhssmall == 0;
1128
4.17M
1129
72.7k
  
if (72.7k
isl_sioimath_decode_small(rhs, &rhssmall)72.7k
)
1130
54.1k
    return mp_int_divisible_value(
1131
54.1k
        isl_sioimath_bigarg_src(lhs, &lhsscratch), rhssmall);
1132
72.7k
1133
18.6k
  mp_int_init(&rem);
1134
18.6k
  mp_int_div(isl_sioimath_bigarg_src(lhs, &lhsscratch),
1135
18.6k
      isl_sioimath_bigarg_src(rhs, &rhsscratch), NULL, &rem);
1136
18.6k
  cmp = mp_int_compare_zero(&rem);
1137
18.6k
  mp_int_clear(&rem);
1138
18.6k
  return cmp == 0;
1139
4.17M
}
1140
1141
/* Return a hash code of an isl_sioimath.
1142
 * The hash code for a number in small and big representation must be identical
1143
 * on the same machine because small representation if not obligatory if fits.
1144
 */
1145
inline uint32_t isl_sioimath_hash(isl_sioimath_src arg, uint32_t hash)
1146
27.9M
{
1147
27.9M
  int32_t small;
1148
27.9M
  int i;
1149
27.9M
  uint32_t num;
1150
27.9M
  mp_digit digits[(sizeof(uint32_t) + sizeof(mp_digit) - 1) /
1151
27.9M
                  sizeof(mp_digit)];
1152
27.9M
  mp_size used;
1153
27.9M
  const unsigned char *digitdata = (const unsigned char *) &digits;
1154
27.9M
1155
27.9M
  if (
isl_sioimath_decode_small(arg, &small)27.9M
) {
1156
27.6M
    if (small < 0)
1157
14.0M
      isl_hash_byte(hash, 0xFF);
1158
27.6M
    num = labs(small);
1159
27.6M
1160
27.6M
    isl_siomath_uint32_to_digits(num, digits, &used);
1161
138M
    for (i = 0; 
i < used * sizeof(mp_digit)138M
;
i += 1110M
)
1162
110M
      isl_hash_byte(hash, digitdata[i]);
1163
27.6M
    return hash;
1164
27.6M
  }
1165
27.9M
1166
263k
  return isl_imath_hash(isl_sioimath_get_big(arg), hash);
1167
27.9M
}
1168
1169
/* Return the number of digits in a number of the given base or more, i.e. the
1170
 * string length without sign and null terminator.
1171
 *
1172
 * Current implementation for small representation returns the maximal number
1173
 * of binary digits in that representation, which can be much larger than the
1174
 * smallest possible solution.
1175
 */
1176
inline size_t isl_sioimath_sizeinbase(isl_sioimath_src arg, int base)
1177
3.47k
{
1178
3.47k
  int32_t small;
1179
3.47k
1180
3.47k
  if (isl_sioimath_decode_small(arg, &small))
1181
3.37k
    return sizeof(int32_t) * CHAR_BIT - 1;
1182
3.47k
1183
105
  return impz_sizeinbase(isl_sioimath_get_big(arg), base);
1184
3.47k
}
1185
1186
void isl_sioimath_print(FILE *out, isl_sioimath_src i, int width);
1187
void isl_sioimath_dump(isl_sioimath_src arg);
1188
1189
typedef isl_sioimath isl_int[1];
1190
92.8M
#define isl_int_init(i)     isl_sioimath_init((i))
1191
78.4M
#define isl_int_clear(i)    isl_sioimath_clear((i))
1192
1193
577M
#define isl_int_set(r, i)   isl_sioimath_set((r), *(i))
1194
153M
#define isl_int_set_si(r, i)    isl_sioimath_set_si((r), i)
1195
12.7k
#define isl_int_set_ui(r, i)    isl_sioimath_set_ui((r), i)
1196
2.50k
#define isl_int_fits_slong(r)   isl_sioimath_fits_slong(*(r))
1197
3.15k
#define isl_int_get_si(r)   isl_sioimath_get_si(*(r))
1198
6.03k
#define isl_int_fits_ulong(r)   isl_sioimath_fits_ulong(*(r))
1199
6.03k
#define isl_int_get_ui(r)   isl_sioimath_get_ui(*(r))
1200
0
#define isl_int_get_d(r)    isl_sioimath_get_d(*(r))
1201
16.8k
#define isl_int_get_str(r)    isl_sioimath_get_str(*(r))
1202
56.7M
#define isl_int_abs(r, i)   isl_sioimath_abs((r), *(i))
1203
210M
#define isl_int_neg(r, i)   isl_sioimath_neg((r), *(i))
1204
46.6M
#define isl_int_swap(i, j)    isl_sioimath_swap((i), (j))
1205
25.4M
#define isl_int_swap_or_set(i, j) isl_sioimath_swap((i), (j))
1206
584k
#define isl_int_add_ui(r, i, j)   isl_sioimath_add_ui((r), *(i), j)
1207
670k
#define isl_int_sub_ui(r, i, j)   isl_sioimath_sub_ui((r), *(i), j)
1208
1209
7.21M
#define isl_int_add(r, i, j)    isl_sioimath_add((r), *(i), *(j))
1210
489k
#define isl_int_sub(r, i, j)    isl_sioimath_sub((r), *(i), *(j))
1211
266M
#define isl_int_mul(r, i, j)    isl_sioimath_mul((r), *(i), *(j))
1212
6.03k
#define isl_int_mul_2exp(r, i, j) isl_sioimath_mul_2exp((r), *(i), j)
1213
367
#define isl_int_mul_si(r, i, j)   isl_sioimath_mul_si((r), *(i), j)
1214
405k
#define isl_int_mul_ui(r, i, j)   isl_sioimath_mul_ui((r), *(i), j)
1215
0
#define isl_int_pow_ui(r, i, j)   isl_sioimath_pow_ui((r), *(i), j)
1216
276M
#define isl_int_addmul(r, i, j)   isl_sioimath_addmul((r), *(i), *(j))
1217
10.2k
#define isl_int_addmul_ui(r, i, j)  isl_sioimath_addmul_ui((r), *(i), j)
1218
7.85M
#define isl_int_submul(r, i, j)   isl_sioimath_submul((r), *(i), *(j))
1219
360
#define isl_int_submul_ui(r, i, j)  isl_sioimath_submul_ui((r), *(i), j)
1220
1221
30.5M
#define isl_int_gcd(r, i, j)    isl_sioimath_gcd((r), *(i), *(j))
1222
9.47M
#define isl_int_lcm(r, i, j)    isl_sioimath_lcm((r), *(i), *(j))
1223
64.4M
#define isl_int_divexact(r, i, j) isl_sioimath_tdiv_q((r), *(i), *(j))
1224
215k
#define isl_int_divexact_ui(r, i, j)  isl_sioimath_tdiv_q_ui((r), *(i), j)
1225
0
#define isl_int_tdiv_q(r, i, j)   isl_sioimath_tdiv_q((r), *(i), *(j))
1226
253k
#define isl_int_cdiv_q(r, i, j)   isl_sioimath_cdiv_q((r), *(i), *(j))
1227
613
#define isl_int_cdiv_q_ui(r, i, j)  isl_sioimath_cdiv_q_ui((r), *(i), j)
1228
1.12M
#define isl_int_fdiv_q(r, i, j)   isl_sioimath_fdiv_q((r), *(i), *(j))
1229
121k
#define isl_int_fdiv_r(r, i, j)   isl_sioimath_fdiv_r((r), *(i), *(j))
1230
47.1k
#define isl_int_fdiv_q_ui(r, i, j)  isl_sioimath_fdiv_q_ui((r), *(i), j)
1231
1232
9.97k
#define isl_int_read(r, s)    isl_sioimath_read((r), s)
1233
1.18G
#define isl_int_sgn(i)      isl_sioimath_sgn(*(i))
1234
23.4M
#define isl_int_cmp(i, j)   isl_sioimath_cmp(*(i), *(j))
1235
125M
#define isl_int_cmp_si(i, si)   isl_sioimath_cmp_si(*(i), si)
1236
1.07M
#define isl_int_eq(i, j)    (isl_sioimath_cmp(*(i), *(j)) == 0)
1237
104M
#define isl_int_ne(i, j)    (isl_sioimath_cmp(*(i), *(j)) != 0)
1238
8.96M
#define isl_int_lt(i, j)    (isl_sioimath_cmp(*(i), *(j)) < 0)
1239
39.7k
#define isl_int_le(i, j)    (isl_sioimath_cmp(*(i), *(j)) <= 0)
1240
124k
#define isl_int_gt(i, j)    (isl_sioimath_cmp(*(i), *(j)) > 0)
1241
37.9k
#define isl_int_ge(i, j)    (isl_sioimath_cmp(*(i), *(j)) >= 0)
1242
741k
#define isl_int_abs_cmp(i, j)   isl_sioimath_abs_cmp(*(i), *(j))
1243
44.2k
#define isl_int_abs_eq(i, j)    (isl_sioimath_abs_cmp(*(i), *(j)) == 0)
1244
699k
#define isl_int_abs_ne(i, j)    (isl_sioimath_abs_cmp(*(i), *(j)) != 0)
1245
36.7M
#define isl_int_abs_lt(i, j)    (isl_sioimath_abs_cmp(*(i), *(j)) < 0)
1246
617k
#define isl_int_abs_gt(i, j)    (isl_sioimath_abs_cmp(*(i), *(j)) > 0)
1247
622k
#define isl_int_abs_ge(i, j)    (isl_sioimath_abs_cmp(*(i), *(j)) >= 0)
1248
4.17M
#define isl_int_is_divisible_by(i, j) isl_sioimath_is_divisible_by(*(i), *(j))
1249
1250
27.9M
#define isl_int_hash(v, h)    isl_sioimath_hash(*(v), h)
1251
16.8k
#define isl_int_free_str(s)   free(s)
1252
0
#define isl_int_print(out, i, width)  isl_sioimath_print(out, *(i), width)
1253
1254
#endif /* ISL_INT_SIOIMATH_H */