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
11#include <assert.h>
12#include <stdio.h>
13#include <isl_int.h>
14
15#define ARRAY_SIZE(array) (sizeof(array)/sizeof(*array))
16
17#ifdef USE_SMALL_INT_OPT
18/* Test whether small and big representation of the same number have the same
19 * hash.
20 */
21static void int_test_hash(isl_int val)
22{
23 uint32_t demotedhash, promotedhash;
24 isl_int demoted, promoted;
25
26 isl_int_init(demoted);
27 isl_int_set(demoted, val);
28
29 isl_int_init(promoted);
30 isl_int_set(promoted, val);
31
32 isl_sioimath_try_demote(dst: demoted);
33 isl_sioimath_promote(dst: promoted);
34
35 assert(isl_int_eq(demoted, promoted));
36
37 demotedhash = isl_int_hash(demoted, 0);
38 promotedhash = isl_int_hash(promoted, 0);
39 assert(demotedhash == promotedhash);
40
41 isl_int_clear(demoted);
42 isl_int_clear(promoted);
43}
44
45struct {
46 void (*fn)(isl_int);
47 char *val;
48} int_single_value_tests[] = {
49 { &int_test_hash, "0" },
50 { &int_test_hash, "1" },
51 { &int_test_hash, "-1" },
52 { &int_test_hash, "23" },
53 { &int_test_hash, "-23" },
54 { &int_test_hash, "107" },
55 { &int_test_hash, "32768" },
56 { &int_test_hash, "2147483647" },
57 { &int_test_hash, "-2147483647" },
58 { &int_test_hash, "2147483648" },
59 { &int_test_hash, "-2147483648" },
60};
61
62static void int_test_single_value()
63{
64 int i;
65
66 for (i = 0; i < ARRAY_SIZE(int_single_value_tests); i += 1) {
67 isl_int val;
68
69 isl_int_init(val);
70 isl_int_read(val, int_single_value_tests[i].val);
71
72 (*int_single_value_tests[i].fn)(val);
73
74 isl_int_clear(val);
75 }
76}
77
78static void invoke_alternate_representations_2args(char *arg1, char *arg2,
79 void (*fn)(isl_int, isl_int))
80{
81 int j;
82 isl_int int1, int2;
83
84 isl_int_init(int1);
85 isl_int_init(int2);
86
87 for (j = 0; j < 4; ++j) {
88 isl_int_read(int1, arg1);
89 isl_int_read(int2, arg2);
90
91 if (j & 1)
92 isl_sioimath_promote(dst: int1);
93 else
94 isl_sioimath_try_demote(dst: int1);
95
96 if (j & 2)
97 isl_sioimath_promote(dst: int2);
98 else
99 isl_sioimath_try_demote(dst: int2);
100
101 (*fn)(int1, int2);
102 }
103
104 isl_int_clear(int1);
105 isl_int_clear(int2);
106}
107
108static void invoke_alternate_representations_3args(char *arg1, char *arg2,
109 char *arg3, void (*fn)(isl_int, isl_int, isl_int))
110{
111 int j;
112 isl_int int1, int2, int3;
113
114 isl_int_init(int1);
115 isl_int_init(int2);
116 isl_int_init(int3);
117
118 for (j = 0; j < 8; ++j) {
119 isl_int_read(int1, arg1);
120 isl_int_read(int2, arg2);
121 isl_int_read(int3, arg3);
122
123 if (j & 1)
124 isl_sioimath_promote(dst: int1);
125 else
126 isl_sioimath_try_demote(dst: int1);
127
128 if (j & 2)
129 isl_sioimath_promote(dst: int2);
130 else
131 isl_sioimath_try_demote(dst: int2);
132
133 if (j & 4)
134 isl_sioimath_promote(dst: int3);
135 else
136 isl_sioimath_try_demote(dst: int3);
137
138 (*fn)(int1, int2, int3);
139 }
140
141 isl_int_clear(int1);
142 isl_int_clear(int2);
143 isl_int_clear(int3);
144}
145#else /* USE_SMALL_INT_OPT */
146
147static void int_test_single_value()
148{
149}
150
151static void invoke_alternate_representations_2args(char *arg1, char *arg2,
152 void (*fn)(isl_int, isl_int))
153{
154 isl_int int1, int2;
155
156 isl_int_init(int1);
157 isl_int_init(int2);
158
159 isl_int_read(int1, arg1);
160 isl_int_read(int2, arg2);
161
162 (*fn)(int1, int2);
163
164 isl_int_clear(int1);
165 isl_int_clear(int2);
166}
167
168static void invoke_alternate_representations_3args(char *arg1, char *arg2,
169 char *arg3, void (*fn)(isl_int, isl_int, isl_int))
170{
171 isl_int int1, int2, int3;
172
173 isl_int_init(int1);
174 isl_int_init(int2);
175 isl_int_init(int3);
176
177 isl_int_read(int1, arg1);
178 isl_int_read(int2, arg2);
179 isl_int_read(int3, arg3);
180
181 (*fn)(int1, int2, int3);
182
183 isl_int_clear(int1);
184 isl_int_clear(int2);
185 isl_int_clear(int3);
186}
187#endif /* USE_SMALL_INT_OPT */
188
189static void int_test_neg(isl_int expected, isl_int arg)
190{
191 isl_int result;
192 isl_int_init(result);
193
194 isl_int_neg(result, arg);
195 assert(isl_int_eq(result, expected));
196
197 isl_int_neg(result, expected);
198 assert(isl_int_eq(result, arg));
199
200 isl_int_clear(result);
201}
202
203static void int_test_abs(isl_int expected, isl_int arg)
204{
205 isl_int result;
206 isl_int_init(result);
207
208 isl_int_abs(result, arg);
209 assert(isl_int_eq(result, expected));
210
211 isl_int_clear(result);
212}
213
214struct {
215 void (*fn)(isl_int, isl_int);
216 char *expected, *arg;
217} int_unary_tests[] = {
218 { &int_test_neg, "0", "0" },
219 { &int_test_neg, "-1", "1" },
220 { &int_test_neg, "-2147483647", "2147483647" },
221 { &int_test_neg, "-2147483648", "2147483648" },
222 { &int_test_neg, "-9223372036854775807", "9223372036854775807" },
223 { &int_test_neg, "-9223372036854775808", "9223372036854775808" },
224
225 { &int_test_abs, "0", "0" },
226 { &int_test_abs, "1", "1" },
227 { &int_test_abs, "1", "-1" },
228 { &int_test_abs, "2147483647", "2147483647" },
229 { &int_test_abs, "2147483648", "-2147483648" },
230 { &int_test_abs, "9223372036854775807", "9223372036854775807" },
231 { &int_test_abs, "9223372036854775808", "-9223372036854775808" },
232};
233
234static void int_test_divexact(isl_int expected, isl_int lhs, isl_int rhs)
235{
236 isl_int result;
237 unsigned long rhsulong;
238
239 if (isl_int_sgn(rhs) == 0)
240 return;
241
242 isl_int_init(result);
243
244 isl_int_divexact(result, lhs, rhs);
245 assert(isl_int_eq(expected, result));
246
247 isl_int_tdiv_q(result, lhs, rhs);
248 assert(isl_int_eq(expected, result));
249
250 isl_int_fdiv_q(result, lhs, rhs);
251 assert(isl_int_eq(expected, result));
252
253 isl_int_cdiv_q(result, lhs, rhs);
254 assert(isl_int_eq(expected, result));
255
256 if (isl_int_fits_ulong(rhs)) {
257 rhsulong = isl_int_get_ui(rhs);
258
259 isl_int_divexact_ui(result, lhs, rhsulong);
260 assert(isl_int_eq(expected, result));
261
262 isl_int_fdiv_q_ui(result, lhs, rhsulong);
263 assert(isl_int_eq(expected, result));
264
265 isl_int_cdiv_q_ui(result, lhs, rhsulong);
266 assert(isl_int_eq(expected, result));
267 }
268
269 isl_int_clear(result);
270}
271
272static void int_test_mul(isl_int expected, isl_int lhs, isl_int rhs)
273{
274 isl_int result;
275 isl_int_init(result);
276
277 isl_int_mul(result, lhs, rhs);
278 assert(isl_int_eq(expected, result));
279
280 if (isl_int_fits_ulong(rhs)) {
281 unsigned long rhsulong = isl_int_get_ui(rhs);
282
283 isl_int_mul_ui(result, lhs, rhsulong);
284 assert(isl_int_eq(expected, result));
285 }
286
287 if (isl_int_fits_slong(rhs)) {
288 unsigned long rhsslong = isl_int_get_si(rhs);
289
290 isl_int_mul_si(result, lhs, rhsslong);
291 assert(isl_int_eq(expected, result));
292 }
293
294 isl_int_clear(result);
295}
296
297/* Use a triple that satisfies 'product = factor1 * factor2' to check the
298 * operations mul, divexact, tdiv, fdiv and cdiv.
299 */
300static void int_test_product(isl_int product, isl_int factor1, isl_int factor2)
301{
302 int_test_divexact(expected: factor1, lhs: product, rhs: factor2);
303 int_test_divexact(expected: factor2, lhs: product, rhs: factor1);
304
305 int_test_mul(expected: product, lhs: factor1, rhs: factor2);
306 int_test_mul(expected: product, lhs: factor2, rhs: factor1);
307}
308
309static void int_test_add(isl_int expected, isl_int lhs, isl_int rhs)
310{
311 isl_int result;
312 isl_int_init(result);
313
314 isl_int_add(result, lhs, rhs);
315 assert(isl_int_eq(expected, result));
316
317 isl_int_clear(result);
318}
319
320static void int_test_sub(isl_int expected, isl_int lhs, isl_int rhs)
321{
322 isl_int result;
323 isl_int_init(result);
324
325 isl_int_sub(result, lhs, rhs);
326 assert(isl_int_eq(expected, result));
327
328 isl_int_clear(result);
329}
330
331/* Use a triple that satisfies 'sum = term1 + term2' to check the operations add
332 * and sub.
333 */
334static void int_test_sum(isl_int sum, isl_int term1, isl_int term2)
335{
336 int_test_sub(expected: term1, lhs: sum, rhs: term2);
337 int_test_sub(expected: term2, lhs: sum, rhs: term1);
338
339 int_test_add(expected: sum, lhs: term1, rhs: term2);
340 int_test_add(expected: sum, lhs: term2, rhs: term1);
341}
342
343static void int_test_fdiv(isl_int expected, isl_int lhs, isl_int rhs)
344{
345 unsigned long rhsulong;
346 isl_int result;
347 isl_int_init(result);
348
349 isl_int_fdiv_q(result, lhs, rhs);
350 assert(isl_int_eq(expected, result));
351
352 if (isl_int_fits_ulong(rhs)) {
353 rhsulong = isl_int_get_ui(rhs);
354
355 isl_int_fdiv_q_ui(result, lhs, rhsulong);
356 assert(isl_int_eq(expected, result));
357 }
358
359 isl_int_clear(result);
360}
361
362static void int_test_cdiv(isl_int expected, isl_int lhs, isl_int rhs)
363{
364 unsigned long rhsulong;
365 isl_int result;
366 isl_int_init(result);
367
368 isl_int_cdiv_q(result, lhs, rhs);
369 assert(isl_int_eq(expected, result));
370
371 if (isl_int_fits_ulong(rhs)) {
372 rhsulong = isl_int_get_ui(rhs);
373
374 isl_int_cdiv_q_ui(result, lhs, rhsulong);
375 assert(isl_int_eq(expected, result));
376 }
377
378 isl_int_clear(result);
379}
380
381static void int_test_tdiv(isl_int expected, isl_int lhs, isl_int rhs)
382{
383 isl_int result;
384 isl_int_init(result);
385
386 isl_int_tdiv_q(result, lhs, rhs);
387 assert(isl_int_eq(expected, result));
388
389 isl_int_clear(result);
390}
391
392static void int_test_fdiv_r(isl_int expected, isl_int lhs, isl_int rhs)
393{
394 isl_int result;
395 isl_int_init(result);
396
397 isl_int_fdiv_r(result, lhs, rhs);
398 assert(isl_int_eq(expected, result));
399
400 isl_int_clear(result);
401}
402
403static void int_test_gcd(isl_int expected, isl_int lhs, isl_int rhs)
404{
405 isl_int result;
406 isl_int_init(result);
407
408 isl_int_gcd(result, lhs, rhs);
409 assert(isl_int_eq(expected, result));
410
411 isl_int_gcd(result, rhs, lhs);
412 assert(isl_int_eq(expected, result));
413
414 isl_int_clear(result);
415}
416
417static void int_test_lcm(isl_int expected, isl_int lhs, isl_int rhs)
418{
419 isl_int result;
420 isl_int_init(result);
421
422 isl_int_lcm(result, lhs, rhs);
423 assert(isl_int_eq(expected, result));
424
425 isl_int_lcm(result, rhs, lhs);
426 assert(isl_int_eq(expected, result));
427
428 isl_int_clear(result);
429}
430
431static int sgn(int val)
432{
433 if (val > 0)
434 return 1;
435 if (val < 0)
436 return -1;
437 return 0;
438}
439
440static void int_test_cmp(int exp, isl_int lhs, isl_int rhs)
441{
442 long rhslong;
443
444 assert(exp == sgn(isl_int_cmp(lhs, rhs)));
445
446 if (isl_int_fits_slong(rhs)) {
447 rhslong = isl_int_get_si(rhs);
448 assert(exp == sgn(isl_int_cmp_si(lhs, rhslong)));
449 }
450}
451
452/* Test the comparison relations over two numbers.
453 * expected is the sign (1, 0 or -1) of 'lhs - rhs'.
454 */
455static void int_test_cmps(isl_int expected, isl_int lhs, isl_int rhs)
456{
457 int exp;
458 isl_int diff;
459
460 exp = isl_int_get_si(expected);
461
462 isl_int_init(diff);
463 isl_int_sub(diff, lhs, rhs);
464 assert(exp == isl_int_sgn(diff));
465 isl_int_clear(diff);
466
467 int_test_cmp(exp, lhs, rhs);
468 int_test_cmp(exp: -exp, lhs: rhs, rhs: lhs);
469}
470
471static void int_test_abs_cmp(isl_int expected, isl_int lhs, isl_int rhs)
472{
473 int exp;
474
475 exp = isl_int_get_si(expected);
476 assert(exp == sgn(isl_int_abs_cmp(lhs, rhs)));
477 assert(-exp == sgn(isl_int_abs_cmp(rhs, lhs)));
478}
479
480/* If "expected" is equal to 1, then check that "rhs" divides "lhs".
481 * If "expected" is equal to 0, then check that "rhs" does not divide "lhs".
482 */
483static void int_test_divisible(isl_int expected, isl_int lhs, isl_int rhs)
484{
485 int exp;
486
487 exp = isl_int_get_si(expected);
488 assert(isl_int_is_divisible_by(lhs, rhs) == exp);
489}
490
491struct {
492 void (*fn)(isl_int, isl_int, isl_int);
493 char *expected, *lhs, *rhs;
494} int_binary_tests[] = {
495 { &int_test_sum, "0", "0", "0" },
496 { &int_test_sum, "1", "1", "0" },
497 { &int_test_sum, "2", "1", "1" },
498 { &int_test_sum, "-1", "0", "-1" },
499 { &int_test_sum, "-2", "-1", "-1" },
500
501 { &int_test_sum, "2147483647", "1073741823", "1073741824" },
502 { &int_test_sum, "-2147483648", "-1073741824", "-1073741824" },
503
504 { &int_test_sum, "2147483648", "2147483647", "1" },
505 { &int_test_sum, "-2147483648", "-2147483647", "-1" },
506
507 { &int_test_product, "0", "0", "0" },
508 { &int_test_product, "0", "0", "1" },
509 { &int_test_product, "1", "1", "1" },
510
511 { &int_test_product, "6", "2", "3" },
512 { &int_test_product, "-6", "2", "-3" },
513 { &int_test_product, "-6", "-2", "3" },
514 { &int_test_product, "6", "-2", "-3" },
515
516 { &int_test_product, "2147483648", "65536", "32768" },
517 { &int_test_product, "-2147483648", "65536", "-32768" },
518
519 { &int_test_product,
520 "4611686014132420609", "2147483647", "2147483647" },
521 { &int_test_product,
522 "-4611686014132420609", "-2147483647", "2147483647" },
523
524 { &int_test_product,
525 "4611686016279904256", "2147483647", "2147483648" },
526 { &int_test_product,
527 "-4611686016279904256", "-2147483647", "2147483648" },
528 { &int_test_product,
529 "-4611686016279904256", "2147483647", "-2147483648" },
530 { &int_test_product,
531 "4611686016279904256", "-2147483647", "-2147483648" },
532
533 { &int_test_product, "85070591730234615847396907784232501249",
534 "9223372036854775807", "9223372036854775807" },
535 { &int_test_product, "-85070591730234615847396907784232501249",
536 "-9223372036854775807", "9223372036854775807" },
537
538 { &int_test_product, "85070591730234615856620279821087277056",
539 "9223372036854775807", "9223372036854775808" },
540 { &int_test_product, "-85070591730234615856620279821087277056",
541 "-9223372036854775807", "9223372036854775808" },
542 { &int_test_product, "-85070591730234615856620279821087277056",
543 "9223372036854775807", "-9223372036854775808" },
544 { &int_test_product, "85070591730234615856620279821087277056",
545 "-9223372036854775807", "-9223372036854775808" },
546
547 { &int_test_product, "340282366920938463426481119284349108225",
548 "18446744073709551615", "18446744073709551615" },
549 { &int_test_product, "-340282366920938463426481119284349108225",
550 "-18446744073709551615", "18446744073709551615" },
551
552 { &int_test_product, "340282366920938463444927863358058659840",
553 "18446744073709551615", "18446744073709551616" },
554 { &int_test_product, "-340282366920938463444927863358058659840",
555 "-18446744073709551615", "18446744073709551616" },
556 { &int_test_product, "-340282366920938463444927863358058659840",
557 "18446744073709551615", "-18446744073709551616" },
558 { &int_test_product, "340282366920938463444927863358058659840",
559 "-18446744073709551615", "-18446744073709551616" },
560
561 { &int_test_fdiv, "0", "1", "2" },
562 { &int_test_fdiv_r, "1", "1", "3" },
563 { &int_test_fdiv, "-1", "-1", "2" },
564 { &int_test_fdiv_r, "2", "-1", "3" },
565 { &int_test_fdiv, "-1", "1", "-2" },
566 { &int_test_fdiv_r, "-2", "1", "-3" },
567 { &int_test_fdiv, "0", "-1", "-2" },
568 { &int_test_fdiv_r, "-1", "-1", "-3" },
569
570 { &int_test_cdiv, "1", "1", "2" },
571 { &int_test_cdiv, "0", "-1", "2" },
572 { &int_test_cdiv, "0", "1", "-2" },
573 { &int_test_cdiv, "1", "-1", "-2" },
574
575 { &int_test_cdiv, "1073741824", "2147483647", "2" },
576 { &int_test_cdiv, "1073741824", "2147483648", "2" },
577 { &int_test_cdiv, "-1073741824", "-2147483648", "2" },
578 { &int_test_cdiv, "-1073741823", "-2147483647", "2" },
579
580 { &int_test_tdiv, "0", "1", "2" },
581 { &int_test_tdiv, "0", "-1", "2" },
582 { &int_test_tdiv, "0", "1", "-2" },
583 { &int_test_tdiv, "0", "-1", "-2" },
584
585 { &int_test_gcd, "0", "0", "0" },
586 { &int_test_lcm, "0", "0", "0" },
587 { &int_test_gcd, "7", "0", "7" },
588 { &int_test_lcm, "0", "0", "7" },
589 { &int_test_gcd, "1", "1", "1" },
590 { &int_test_lcm, "1", "1", "1" },
591 { &int_test_gcd, "1", "1", "-1" },
592 { &int_test_lcm, "1", "1", "-1" },
593 { &int_test_gcd, "1", "-1", "-1" },
594 { &int_test_lcm, "1", "-1", "-1" },
595 { &int_test_gcd, "3", "6", "9" },
596 { &int_test_lcm, "18", "6", "9" },
597 { &int_test_gcd, "1", "14", "2147483647" },
598 { &int_test_lcm, "15032385529", "7", "2147483647" },
599 { &int_test_gcd, "2", "6", "-2147483648" },
600 { &int_test_lcm, "6442450944", "6", "-2147483648" },
601 { &int_test_gcd, "1", "6", "9223372036854775807" },
602 { &int_test_lcm, "55340232221128654842", "6", "9223372036854775807" },
603 { &int_test_gcd, "2", "6", "-9223372036854775808" },
604 { &int_test_lcm, "27670116110564327424", "6", "-9223372036854775808" },
605 { &int_test_gcd, "1", "18446744073709551616", "18446744073709551615" },
606 { &int_test_lcm, "340282366920938463444927863358058659840",
607 "18446744073709551616", "18446744073709551615" },
608
609 { &int_test_cmps, "0", "0", "0" },
610 { &int_test_abs_cmp, "0", "0", "0" },
611 { &int_test_cmps, "1", "1", "0" },
612 { &int_test_abs_cmp, "1", "1", "0" },
613 { &int_test_cmps, "-1", "-1", "0" },
614 { &int_test_abs_cmp, "1", "-1", "0" },
615 { &int_test_cmps, "-1", "-1", "1" },
616 { &int_test_abs_cmp, "0", "-1", "1" },
617
618 { &int_test_cmps, "-1", "5", "2147483647" },
619 { &int_test_abs_cmp, "-1", "5", "2147483647" },
620 { &int_test_cmps, "1", "5", "-2147483648" },
621 { &int_test_abs_cmp, "-1", "5", "-2147483648" },
622 { &int_test_cmps, "-1", "5", "9223372036854775807" },
623 { &int_test_abs_cmp, "-1", "5", "9223372036854775807" },
624 { &int_test_cmps, "1", "5", "-9223372036854775809" },
625 { &int_test_abs_cmp, "-1", "5", "-9223372036854775809" },
626
627 { &int_test_divisible, "1", "0", "0" },
628 { &int_test_divisible, "0", "1", "0" },
629 { &int_test_divisible, "0", "2", "0" },
630 { &int_test_divisible, "0", "2147483647", "0" },
631 { &int_test_divisible, "0", "9223372036854775807", "0" },
632 { &int_test_divisible, "1", "0", "1" },
633 { &int_test_divisible, "1", "1", "1" },
634 { &int_test_divisible, "1", "2", "1" },
635 { &int_test_divisible, "1", "2147483647", "1" },
636 { &int_test_divisible, "1", "9223372036854775807", "1" },
637 { &int_test_divisible, "1", "0", "2" },
638 { &int_test_divisible, "0", "1", "2" },
639 { &int_test_divisible, "1", "2", "2" },
640 { &int_test_divisible, "0", "2147483647", "2" },
641 { &int_test_divisible, "0", "9223372036854775807", "2" },
642};
643
644/* Tests the isl_int_* function to give the expected results. Tests are
645 * grouped by the number of arguments they take.
646 *
647 * If small integer optimization is enabled, we also test whether the results
648 * are the same in small and big representation.
649 */
650int main()
651{
652 int i;
653
654 int_test_single_value();
655
656 for (i = 0; i < ARRAY_SIZE(int_unary_tests); i += 1) {
657 invoke_alternate_representations_2args(
658 arg1: int_unary_tests[i].expected, arg2: int_unary_tests[i].arg,
659 fn: int_unary_tests[i].fn);
660 }
661
662 for (i = 0; i < ARRAY_SIZE(int_binary_tests); i += 1) {
663 invoke_alternate_representations_3args(
664 arg1: int_binary_tests[i].expected, arg2: int_binary_tests[i].lhs,
665 arg3: int_binary_tests[i].rhs, fn: int_binary_tests[i].fn);
666 }
667
668 return 0;
669}
670

source code of polly/lib/External/isl/isl_test_int.c