670 lines · c
1/*2 * Copyright 2015 INRIA Paris-Rocquencourt3 *4 * Use of this software is governed by the MIT license5 *6 * Written by Michael Kruse, INRIA Paris-Rocquencourt,7 * Domaine de Voluceau, Rocquenqourt, B.P. 105,8 * 78153 Le Chesnay Cedex France9 */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_OPT18/* Test whether small and big representation of the same number have the same19 * 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(demoted);33 isl_sioimath_promote(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(int1);93 else94 isl_sioimath_try_demote(int1);95 96 if (j & 2)97 isl_sioimath_promote(int2);98 else99 isl_sioimath_try_demote(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(int1);125 else126 isl_sioimath_try_demote(int1);127 128 if (j & 2)129 isl_sioimath_promote(int2);130 else131 isl_sioimath_try_demote(int2);132 133 if (j & 4)134 isl_sioimath_promote(int3);135 else136 isl_sioimath_try_demote(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 the298 * 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(factor1, product, factor2);303 int_test_divexact(factor2, product, factor1);304 305 int_test_mul(product, factor1, factor2);306 int_test_mul(product, factor2, 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 add332 * and sub.333 */334static void int_test_sum(isl_int sum, isl_int term1, isl_int term2)335{336 int_test_sub(term1, sum, term2);337 int_test_sub(term2, sum, term1);338 339 int_test_add(sum, term1, term2);340 int_test_add(sum, term2, 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, 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 are645 * grouped by the number of arguments they take.646 *647 * If small integer optimization is enabled, we also test whether the results648 * 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 int_unary_tests[i].expected, int_unary_tests[i].arg,659 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 int_binary_tests[i].expected, int_binary_tests[i].lhs,665 int_binary_tests[i].rhs, int_binary_tests[i].fn);666 }667 668 return 0;669}670