extract out shared isl_schedule_node_grandparent
[isl.git] / isl_test_int.c
bloba996411fd55079d15b21fcb09565fe2913f37a89
1 /*
2 * Copyright 2015 INRIA Paris-Rocquencourt
4 * Use of this software is governed by the MIT license
6 * Written by Michael Kruse, INRIA Paris-Rocquencourt,
7 * Domaine de Voluceau, Rocquenqourt, B.P. 105,
8 * 78153 Le Chesnay Cedex France
9 */
11 #include <assert.h>
12 #include <stdio.h>
13 #include <isl_int.h>
15 #define ARRAY_SIZE(array) (sizeof(array)/sizeof(*array))
17 #ifdef USE_SMALL_INT_OPT
18 /* Test whether small and big representation of the same number have the same
19 * hash.
21 static void int_test_hash(isl_int val)
23 uint32_t demotedhash, promotedhash;
24 isl_int demoted, promoted;
26 isl_int_init(demoted);
27 isl_int_set(demoted, val);
29 isl_int_init(promoted);
30 isl_int_set(promoted, val);
32 isl_sioimath_try_demote(demoted);
33 isl_sioimath_promote(promoted);
35 assert(isl_int_eq(demoted, promoted));
37 demotedhash = isl_int_hash(demoted, 0);
38 promotedhash = isl_int_hash(promoted, 0);
39 assert(demotedhash == promotedhash);
41 isl_int_clear(demoted);
42 isl_int_clear(promoted);
45 struct {
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" },
62 static void int_test_single_value()
64 int i;
66 for (i = 0; i < ARRAY_SIZE(int_single_value_tests); i += 1) {
67 isl_int val;
69 isl_int_init(val);
70 isl_int_read(val, int_single_value_tests[i].val);
72 (*int_single_value_tests[i].fn)(val);
74 isl_int_clear(val);
78 static void invoke_alternate_representations_2args(char *arg1, char *arg2,
79 void (*fn)(isl_int, isl_int))
81 int j;
82 isl_int int1, int2;
84 isl_int_init(int1);
85 isl_int_init(int2);
87 for (j = 0; j < 4; ++j) {
88 isl_int_read(int1, arg1);
89 isl_int_read(int2, arg2);
91 if (j & 1)
92 isl_sioimath_promote(int1);
93 else
94 isl_sioimath_try_demote(int1);
96 if (j & 2)
97 isl_sioimath_promote(int2);
98 else
99 isl_sioimath_try_demote(int2);
101 (*fn)(int1, int2);
104 isl_int_clear(int1);
105 isl_int_clear(int2);
108 static void invoke_alternate_representations_3args(char *arg1, char *arg2,
109 char *arg3, void (*fn)(isl_int, isl_int, isl_int))
111 int j;
112 isl_int int1, int2, int3;
114 isl_int_init(int1);
115 isl_int_init(int2);
116 isl_int_init(int3);
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);
123 if (j & 1)
124 isl_sioimath_promote(int1);
125 else
126 isl_sioimath_try_demote(int1);
128 if (j & 2)
129 isl_sioimath_promote(int2);
130 else
131 isl_sioimath_try_demote(int2);
133 if (j & 4)
134 isl_sioimath_promote(int3);
135 else
136 isl_sioimath_try_demote(int3);
138 (*fn)(int1, int2, int3);
141 isl_int_clear(int1);
142 isl_int_clear(int2);
143 isl_int_clear(int3);
145 #else /* USE_SMALL_INT_OPT */
147 static void int_test_single_value()
151 static void invoke_alternate_representations_2args(char *arg1, char *arg2,
152 void (*fn)(isl_int, isl_int))
154 isl_int int1, int2;
156 isl_int_init(int1);
157 isl_int_init(int2);
159 isl_int_read(int1, arg1);
160 isl_int_read(int2, arg2);
162 (*fn)(int1, int2);
164 isl_int_clear(int1);
165 isl_int_clear(int2);
168 static void invoke_alternate_representations_3args(char *arg1, char *arg2,
169 char *arg3, void (*fn)(isl_int, isl_int, isl_int))
171 isl_int int1, int2, int3;
173 isl_int_init(int1);
174 isl_int_init(int2);
175 isl_int_init(int3);
177 isl_int_read(int1, arg1);
178 isl_int_read(int2, arg2);
179 isl_int_read(int3, arg3);
181 (*fn)(int1, int2, int3);
183 isl_int_clear(int1);
184 isl_int_clear(int2);
185 isl_int_clear(int3);
187 #endif /* USE_SMALL_INT_OPT */
189 static void int_test_neg(isl_int expected, isl_int arg)
191 isl_int result;
192 isl_int_init(result);
194 isl_int_neg(result, arg);
195 assert(isl_int_eq(result, expected));
197 isl_int_neg(result, expected);
198 assert(isl_int_eq(result, arg));
200 isl_int_clear(result);
203 static void int_test_abs(isl_int expected, isl_int arg)
205 isl_int result;
206 isl_int_init(result);
208 isl_int_abs(result, arg);
209 assert(isl_int_eq(result, expected));
211 isl_int_clear(result);
214 struct {
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" },
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" },
234 static void int_test_divexact(isl_int expected, isl_int lhs, isl_int rhs)
236 isl_int result;
237 unsigned long rhsulong;
239 if (isl_int_sgn(rhs) == 0)
240 return;
242 isl_int_init(result);
244 isl_int_divexact(result, lhs, rhs);
245 assert(isl_int_eq(expected, result));
247 isl_int_tdiv_q(result, lhs, rhs);
248 assert(isl_int_eq(expected, result));
250 isl_int_fdiv_q(result, lhs, rhs);
251 assert(isl_int_eq(expected, result));
253 isl_int_cdiv_q(result, lhs, rhs);
254 assert(isl_int_eq(expected, result));
256 if (isl_int_fits_ulong(rhs)) {
257 rhsulong = isl_int_get_ui(rhs);
259 isl_int_divexact_ui(result, lhs, rhsulong);
260 assert(isl_int_eq(expected, result));
262 isl_int_fdiv_q_ui(result, lhs, rhsulong);
263 assert(isl_int_eq(expected, result));
265 isl_int_cdiv_q_ui(result, lhs, rhsulong);
266 assert(isl_int_eq(expected, result));
269 isl_int_clear(result);
272 static void int_test_mul(isl_int expected, isl_int lhs, isl_int rhs)
274 isl_int result;
275 isl_int_init(result);
277 isl_int_mul(result, lhs, rhs);
278 assert(isl_int_eq(expected, result));
280 if (isl_int_fits_ulong(rhs)) {
281 unsigned long rhsulong = isl_int_get_ui(rhs);
283 isl_int_mul_ui(result, lhs, rhsulong);
284 assert(isl_int_eq(expected, result));
287 if (isl_int_fits_slong(rhs)) {
288 unsigned long rhsslong = isl_int_get_si(rhs);
290 isl_int_mul_si(result, lhs, rhsslong);
291 assert(isl_int_eq(expected, result));
294 isl_int_clear(result);
297 /* Use a triple that satisfies 'product = factor1 * factor2' to check the
298 * operations mul, divexact, tdiv, fdiv and cdiv.
300 static void int_test_product(isl_int product, isl_int factor1, isl_int factor2)
302 int_test_divexact(factor1, product, factor2);
303 int_test_divexact(factor2, product, factor1);
305 int_test_mul(product, factor1, factor2);
306 int_test_mul(product, factor2, factor1);
309 static void int_test_add(isl_int expected, isl_int lhs, isl_int rhs)
311 isl_int result;
312 isl_int_init(result);
314 isl_int_add(result, lhs, rhs);
315 assert(isl_int_eq(expected, result));
317 isl_int_clear(result);
320 static void int_test_sub(isl_int expected, isl_int lhs, isl_int rhs)
322 isl_int result;
323 isl_int_init(result);
325 isl_int_sub(result, lhs, rhs);
326 assert(isl_int_eq(expected, result));
328 isl_int_clear(result);
331 /* Use a triple that satisfies 'sum = term1 + term2' to check the operations add
332 * and sub.
334 static void int_test_sum(isl_int sum, isl_int term1, isl_int term2)
336 int_test_sub(term1, sum, term2);
337 int_test_sub(term2, sum, term1);
339 int_test_add(sum, term1, term2);
340 int_test_add(sum, term2, term1);
343 static void int_test_fdiv(isl_int expected, isl_int lhs, isl_int rhs)
345 unsigned long rhsulong;
346 isl_int result;
347 isl_int_init(result);
349 isl_int_fdiv_q(result, lhs, rhs);
350 assert(isl_int_eq(expected, result));
352 if (isl_int_fits_ulong(rhs)) {
353 rhsulong = isl_int_get_ui(rhs);
355 isl_int_fdiv_q_ui(result, lhs, rhsulong);
356 assert(isl_int_eq(expected, result));
359 isl_int_clear(result);
362 static void int_test_cdiv(isl_int expected, isl_int lhs, isl_int rhs)
364 unsigned long rhsulong;
365 isl_int result;
366 isl_int_init(result);
368 isl_int_cdiv_q(result, lhs, rhs);
369 assert(isl_int_eq(expected, result));
371 if (isl_int_fits_ulong(rhs)) {
372 rhsulong = isl_int_get_ui(rhs);
374 isl_int_cdiv_q_ui(result, lhs, rhsulong);
375 assert(isl_int_eq(expected, result));
378 isl_int_clear(result);
381 static void int_test_tdiv(isl_int expected, isl_int lhs, isl_int rhs)
383 isl_int result;
384 isl_int_init(result);
386 isl_int_tdiv_q(result, lhs, rhs);
387 assert(isl_int_eq(expected, result));
389 isl_int_clear(result);
392 static void int_test_fdiv_r(isl_int expected, isl_int lhs, isl_int rhs)
394 isl_int result;
395 isl_int_init(result);
397 isl_int_fdiv_r(result, lhs, rhs);
398 assert(isl_int_eq(expected, result));
400 isl_int_clear(result);
403 static void int_test_gcd(isl_int expected, isl_int lhs, isl_int rhs)
405 isl_int result;
406 isl_int_init(result);
408 isl_int_gcd(result, lhs, rhs);
409 assert(isl_int_eq(expected, result));
411 isl_int_gcd(result, rhs, lhs);
412 assert(isl_int_eq(expected, result));
414 isl_int_clear(result);
417 static void int_test_lcm(isl_int expected, isl_int lhs, isl_int rhs)
419 isl_int result;
420 isl_int_init(result);
422 isl_int_lcm(result, lhs, rhs);
423 assert(isl_int_eq(expected, result));
425 isl_int_lcm(result, rhs, lhs);
426 assert(isl_int_eq(expected, result));
428 isl_int_clear(result);
431 static int sgn(int val)
433 if (val > 0)
434 return 1;
435 if (val < 0)
436 return -1;
437 return 0;
440 static void int_test_cmp(int exp, isl_int lhs, isl_int rhs)
442 long rhslong;
444 assert(exp == sgn(isl_int_cmp(lhs, rhs)));
446 if (isl_int_fits_slong(rhs)) {
447 rhslong = isl_int_get_si(rhs);
448 assert(exp == sgn(isl_int_cmp_si(lhs, rhslong)));
452 /* Test the comparison relations over two numbers.
453 * expected is the sign (1, 0 or -1) of 'lhs - rhs'.
455 static void int_test_cmps(isl_int expected, isl_int lhs, isl_int rhs)
457 int exp;
458 isl_int diff;
460 exp = isl_int_get_si(expected);
462 isl_int_init(diff);
463 isl_int_sub(diff, lhs, rhs);
464 assert(exp == isl_int_sgn(diff));
465 isl_int_clear(diff);
467 int_test_cmp(exp, lhs, rhs);
468 int_test_cmp(-exp, rhs, lhs);
471 static void int_test_abs_cmp(isl_int expected, isl_int lhs, isl_int rhs)
473 int exp;
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)));
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".
483 static void int_test_divisible(isl_int expected, isl_int lhs, isl_int rhs)
485 int exp;
487 exp = isl_int_get_si(expected);
488 assert(isl_int_is_divisible_by(lhs, rhs) == exp);
491 struct {
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" },
501 { &int_test_sum, "2147483647", "1073741823", "1073741824" },
502 { &int_test_sum, "-2147483648", "-1073741824", "-1073741824" },
504 { &int_test_sum, "2147483648", "2147483647", "1" },
505 { &int_test_sum, "-2147483648", "-2147483647", "-1" },
507 { &int_test_product, "0", "0", "0" },
508 { &int_test_product, "0", "0", "1" },
509 { &int_test_product, "1", "1", "1" },
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" },
516 { &int_test_product, "2147483648", "65536", "32768" },
517 { &int_test_product, "-2147483648", "65536", "-32768" },
519 { &int_test_product,
520 "4611686014132420609", "2147483647", "2147483647" },
521 { &int_test_product,
522 "-4611686014132420609", "-2147483647", "2147483647" },
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" },
533 { &int_test_product, "85070591730234615847396907784232501249",
534 "9223372036854775807", "9223372036854775807" },
535 { &int_test_product, "-85070591730234615847396907784232501249",
536 "-9223372036854775807", "9223372036854775807" },
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" },
547 { &int_test_product, "340282366920938463426481119284349108225",
548 "18446744073709551615", "18446744073709551615" },
549 { &int_test_product, "-340282366920938463426481119284349108225",
550 "-18446744073709551615", "18446744073709551615" },
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" },
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" },
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" },
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" },
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" },
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" },
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" },
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" },
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" },
644 /* Tests the isl_int_* function to give the expected results. Tests are
645 * grouped by the number of arguments they take.
647 * If small integer optimization is enabled, we also test whether the results
648 * are the same in small and big representation.
650 int main()
652 int i;
654 int_test_single_value();
656 for (i = 0; i < ARRAY_SIZE(int_unary_tests); i += 1) {
657 invoke_alternate_representations_2args(
658 int_unary_tests[i].expected, int_unary_tests[i].arg,
659 int_unary_tests[i].fn);
662 for (i = 0; i < ARRAY_SIZE(int_binary_tests); i += 1) {
663 invoke_alternate_representations_3args(
664 int_binary_tests[i].expected, int_binary_tests[i].lhs,
665 int_binary_tests[i].rhs, int_binary_tests[i].fn);
668 return 0;