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 */ 21 static 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 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" }, 60 }; 61 62 static 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 78 static 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 else 94 isl_sioimath_try_demote(int1); 95 96 if (j & 2) 97 isl_sioimath_promote(int2); 98 else 99 isl_sioimath_try_demote(int2); 100 101 (*fn)(int1, int2); 102 } 103 104 isl_int_clear(int1); 105 isl_int_clear(int2); 106 } 107 108 static 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 else 126 isl_sioimath_try_demote(int1); 127 128 if (j & 2) 129 isl_sioimath_promote(int2); 130 else 131 isl_sioimath_try_demote(int2); 132 133 if (j & 4) 134 isl_sioimath_promote(int3); 135 else 136 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 147 static void int_test_single_value() 148 { 149 } 150 151 static 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 168 static 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 189 static 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 203 static 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 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" }, 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 234 static 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 272 static 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 */ 300 static 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 309 static 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 320 static 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 */ 334 static 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 343 static 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 362 static 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 381 static 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 392 static 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 403 static 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 417 static 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 431 static int sgn(int val) 432 { 433 if (val > 0) 434 return 1; 435 if (val < 0) 436 return -1; 437 return 0; 438 } 439 440 static 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 */ 455 static 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 471 static 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 */ 483 static 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 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" }, 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 */ 650 int 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