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
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
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
);
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()
66 for (i
= 0; i
< ARRAY_SIZE(int_single_value_tests
); i
+= 1) {
70 isl_int_read(val
, int_single_value_tests
[i
].val
);
72 (*int_single_value_tests
[i
].fn
)(val
);
78 static void invoke_alternate_representations_2args(char *arg1
, char *arg2
,
79 void (*fn
)(isl_int
, isl_int
))
87 for (j
= 0; j
< 4; ++j
) {
88 isl_int_read(int1
, arg1
);
89 isl_int_read(int2
, arg2
);
92 isl_sioimath_promote(int1
);
94 isl_sioimath_try_demote(int1
);
97 isl_sioimath_promote(int2
);
99 isl_sioimath_try_demote(int2
);
108 static void invoke_alternate_representations_3args(char *arg1
, char *arg2
,
109 char *arg3
, void (*fn
)(isl_int
, isl_int
, isl_int
))
112 isl_int int1
, int2
, 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
);
124 isl_sioimath_promote(int1
);
126 isl_sioimath_try_demote(int1
);
129 isl_sioimath_promote(int2
);
131 isl_sioimath_try_demote(int2
);
134 isl_sioimath_promote(int3
);
136 isl_sioimath_try_demote(int3
);
138 (*fn
)(int1
, int2
, 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
))
159 isl_int_read(int1
, arg1
);
160 isl_int_read(int2
, arg2
);
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
;
177 isl_int_read(int1
, arg1
);
178 isl_int_read(int2
, arg2
);
179 isl_int_read(int3
, arg3
);
181 (*fn
)(int1
, int2
, int3
);
187 #endif /* USE_SMALL_INT_OPT */
189 static void int_test_neg(isl_int expected
, isl_int arg
)
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
)
206 isl_int_init(result
);
208 isl_int_abs(result
, arg
);
209 assert(isl_int_eq(result
, expected
));
211 isl_int_clear(result
);
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
)
237 unsigned long rhsulong
;
239 if (isl_int_sgn(rhs
) == 0)
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
)
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
)
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
)
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
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
;
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
;
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
)
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
)
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
)
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
)
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
)
440 static void int_test_cmp(int exp
, isl_int lhs
, isl_int rhs
)
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
)
460 exp
= isl_int_get_si(expected
);
463 isl_int_sub(diff
, lhs
, rhs
);
464 assert(exp
== isl_int_sgn(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
)
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
)
487 exp
= isl_int_get_si(expected
);
488 assert(isl_int_is_divisible_by(lhs
, rhs
) == exp
);
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" },
520 "4611686014132420609", "2147483647", "2147483647" },
522 "-4611686014132420609", "-2147483647", "2147483647" },
525 "4611686016279904256", "2147483647", "2147483648" },
527 "-4611686016279904256", "-2147483647", "2147483648" },
529 "-4611686016279904256", "2147483647", "-2147483648" },
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.
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
);