isl_test_int.c

   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
 266         isl_int_clear(result);
 267 }
 268
 269 static void int_test_mul(isl_int expected, isl_int lhs, isl_int rhs)
 270 {
 271         isl_int result;
 272         isl_int_init(result);
 273
 274         isl_int_mul(result, lhs, rhs);
 275         assert(isl_int_eq(expected, result));
 276
 277         if (isl_int_fits_ulong(rhs)) {
 278                 unsigned long rhsulong = isl_int_get_ui(rhs);
 279
 280                 isl_int_mul_ui(result, lhs, rhsulong);
 281                 assert(isl_int_eq(expected, result));
 282         }
 283
 284         if (isl_int_fits_slong(rhs)) {
 285                 unsigned long rhsslong = isl_int_get_si(rhs);
 286
 287                 isl_int_mul_si(result, lhs, rhsslong);
 288                 assert(isl_int_eq(expected, result));
 289         }
 290
 291         isl_int_clear(result);
 292 }
 293
 294 /* Use a triple that satisfies 'product = factor1 * factor2' to check the
 295  * operations mul, divexact, tdiv, fdiv and cdiv.
 296  */
 297 static void int_test_product(isl_int product, isl_int factor1, isl_int factor2)
 298 {
 299         int_test_divexact(factor1, product, factor2);
 300         int_test_divexact(factor2, product, factor1);
 301
 302         int_test_mul(product, factor1, factor2);
 303         int_test_mul(product, factor2, factor1);
 304 }
 305
 306 static void int_test_add(isl_int expected, isl_int lhs, isl_int rhs)
 307 {
 308         isl_int result;
 309         isl_int_init(result);
 310
 311         isl_int_add(result, lhs, rhs);
 312         assert(isl_int_eq(expected, result));
 313
 314         isl_int_clear(result);
 315 }
 316
 317 static void int_test_sub(isl_int expected, isl_int lhs, isl_int rhs)
 318 {
 319         isl_int result;
 320         isl_int_init(result);
 321
 322         isl_int_sub(result, lhs, rhs);
 323         assert(isl_int_eq(expected, result));
 324
 325         isl_int_clear(result);
 326 }
 327
 328 /* Use a triple that satisfies 'sum = term1 + term2' to check the operations add
 329  * and sub.
 330  */
 331 static void int_test_sum(isl_int sum, isl_int term1, isl_int term2)
 332 {
 333         int_test_sub(term1, sum, term2);
 334         int_test_sub(term2, sum, term1);
 335
 336         int_test_add(sum, term1, term2);
 337         int_test_add(sum, term2, term1);
 338 }
 339
 340 static void int_test_fdiv(isl_int expected, isl_int lhs, isl_int rhs)
 341 {
 342         unsigned long rhsulong;
 343         isl_int result;
 344         isl_int_init(result);
 345
 346         isl_int_fdiv_q(result, lhs, rhs);
 347         assert(isl_int_eq(expected, result));
 348
 349         if (isl_int_fits_ulong(rhs)) {
 350                 rhsulong = isl_int_get_ui(rhs);
 351
 352                 isl_int_fdiv_q_ui(result, lhs, rhsulong);
 353                 assert(isl_int_eq(expected, result));
 354         }
 355
 356         isl_int_clear(result);
 357 }
 358
 359 static void int_test_cdiv(isl_int expected, isl_int lhs, isl_int rhs)
 360 {
 361         isl_int result;
 362         isl_int_init(result);
 363
 364         isl_int_cdiv_q(result, lhs, rhs);
 365         assert(isl_int_eq(expected, result));
 366
 367         isl_int_clear(result);
 368 }
 369
 370 static void int_test_tdiv(isl_int expected, isl_int lhs, isl_int rhs)
 371 {
 372         isl_int result;
 373         isl_int_init(result);
 374
 375         isl_int_tdiv_q(result, lhs, rhs);
 376         assert(isl_int_eq(expected, result));
 377
 378         isl_int_clear(result);
 379 }
 380
 381 static void int_test_fdiv_r(isl_int expected, isl_int lhs, isl_int rhs)
 382 {
 383         isl_int result;
 384         isl_int_init(result);
 385
 386         isl_int_fdiv_r(result, lhs, rhs);
 387         assert(isl_int_eq(expected, result));
 388
 389         isl_int_clear(result);
 390 }
 391
 392 static void int_test_gcd(isl_int expected, isl_int lhs, isl_int rhs)
 393 {
 394         isl_int result;
 395         isl_int_init(result);
 396
 397         isl_int_gcd(result, lhs, rhs);
 398         assert(isl_int_eq(expected, result));
 399
 400         isl_int_gcd(result, rhs, lhs);
 401         assert(isl_int_eq(expected, result));
 402
 403         isl_int_clear(result);
 404 }
 405
 406 static void int_test_lcm(isl_int expected, isl_int lhs, isl_int rhs)
 407 {
 408         isl_int result;
 409         isl_int_init(result);
 410
 411         isl_int_lcm(result, lhs, rhs);
 412         assert(isl_int_eq(expected, result));
 413
 414         isl_int_lcm(result, rhs, lhs);
 415         assert(isl_int_eq(expected, result));
 416
 417         isl_int_clear(result);
 418 }
 419
 420 static int sgn(int val)
 421 {
 422         if (val > 0)
 423                 return 1;
 424         if (val < 0)
 425                 return -1;
 426         return 0;
 427 }
 428
 429 static void int_test_cmp(int exp, isl_int lhs, isl_int rhs)
 430 {
 431         long rhslong;
 432
 433         assert(exp == sgn(isl_int_cmp(lhs, rhs)));
 434
 435         if (isl_int_fits_slong(rhs)) {
 436                 rhslong = isl_int_get_si(rhs);
 437                 assert(exp == sgn(isl_int_cmp_si(lhs, rhslong)));
 438         }
 439 }
 440
 441 /* Test the comparison relations over two numbers.
 442  * expected is the sign (1, 0 or -1) of 'lhs - rhs'.
 443  */
 444 static void int_test_cmps(isl_int expected, isl_int lhs, isl_int rhs)
 445 {
 446         int exp;
 447         isl_int diff;
 448
 449         exp = isl_int_get_si(expected);
 450
 451         isl_int_init(diff);
 452         isl_int_sub(diff, lhs, rhs);
 453         assert(exp == isl_int_sgn(diff));
 454         isl_int_clear(diff);
 455
 456         int_test_cmp(exp, lhs, rhs);
 457         int_test_cmp(-exp, rhs, lhs);
 458 }
 459
 460 static void int_test_abs_cmp(isl_int expected, isl_int lhs, isl_int rhs)
 461 {
 462         int exp;
 463
 464         exp = isl_int_get_si(expected);
 465         assert(exp == sgn(isl_int_abs_cmp(lhs, rhs)));
 466         assert(-exp == sgn(isl_int_abs_cmp(rhs, lhs)));
 467 }
 468
 469 struct {
 470         void (*fn)(isl_int, isl_int, isl_int);
 471         char *expected, *lhs, *rhs;
 472 } int_binary_tests[] = {
 473         { &int_test_sum, "0", "0", "0" },
 474         { &int_test_sum, "1", "1", "0" },
 475         { &int_test_sum, "2", "1", "1" },
 476         { &int_test_sum, "-1", "0", "-1" },
 477         { &int_test_sum, "-2", "-1", "-1" },
 478
 479         { &int_test_sum, "2147483647", "1073741823", "1073741824" },
 480         { &int_test_sum, "-2147483648", "-1073741824", "-1073741824" },
 481
 482         { &int_test_sum, "2147483648", "2147483647", "1" },
 483         { &int_test_sum, "-2147483648", "-2147483647", "-1" },
 484
 485         { &int_test_product, "0", "0", "0" },
 486         { &int_test_product, "0", "0", "1" },
 487         { &int_test_product, "1", "1", "1" },
 488
 489         { &int_test_product, "6", "2", "3" },
 490         { &int_test_product, "-6", "2", "-3" },
 491         { &int_test_product, "-6", "-2", "3" },
 492         { &int_test_product, "6", "-2", "-3" },
 493
 494         { &int_test_product, "2147483648", "65536", "32768" },
 495         { &int_test_product, "-2147483648", "65536", "-32768" },
 496
 497         { &int_test_product,
 498           "4611686014132420609", "2147483647", "2147483647" },
 499         { &int_test_product,
 500           "-4611686014132420609", "-2147483647", "2147483647" },
 501
 502         { &int_test_product,
 503           "4611686016279904256", "2147483647", "2147483648" },
 504         { &int_test_product,
 505           "-4611686016279904256", "-2147483647", "2147483648" },
 506         { &int_test_product,
 507           "-4611686016279904256", "2147483647", "-2147483648" },
 508         { &int_test_product,
 509           "4611686016279904256", "-2147483647", "-2147483648" },
 510
 511         { &int_test_product, "85070591730234615847396907784232501249",
 512           "9223372036854775807", "9223372036854775807" },
 513         { &int_test_product, "-85070591730234615847396907784232501249",
 514           "-9223372036854775807", "9223372036854775807" },
 515
 516         { &int_test_product, "85070591730234615856620279821087277056",
 517           "9223372036854775807", "9223372036854775808" },
 518         { &int_test_product, "-85070591730234615856620279821087277056",
 519           "-9223372036854775807", "9223372036854775808" },
 520         { &int_test_product, "-85070591730234615856620279821087277056",
 521           "9223372036854775807", "-9223372036854775808" },
 522         { &int_test_product, "85070591730234615856620279821087277056",
 523           "-9223372036854775807", "-9223372036854775808" },
 524
 525         { &int_test_product, "340282366920938463426481119284349108225",
 526           "18446744073709551615", "18446744073709551615" },
 527         { &int_test_product, "-340282366920938463426481119284349108225",
 528           "-18446744073709551615", "18446744073709551615" },
 529
 530         { &int_test_product, "340282366920938463444927863358058659840",
 531           "18446744073709551615", "18446744073709551616" },
 532         { &int_test_product, "-340282366920938463444927863358058659840",
 533           "-18446744073709551615", "18446744073709551616" },
 534         { &int_test_product, "-340282366920938463444927863358058659840",
 535           "18446744073709551615", "-18446744073709551616" },
 536         { &int_test_product, "340282366920938463444927863358058659840",
 537           "-18446744073709551615", "-18446744073709551616" },
 538
 539         { &int_test_fdiv, "0", "1", "2" },
 540         { &int_test_fdiv_r, "1", "1", "3" },
 541         { &int_test_fdiv, "-1", "-1", "2" },
 542         { &int_test_fdiv_r, "2", "-1", "3" },
 543         { &int_test_fdiv, "-1", "1", "-2" },
 544         { &int_test_fdiv_r, "-2", "1", "-3" },
 545         { &int_test_fdiv, "0", "-1", "-2" },
 546         { &int_test_fdiv_r, "-1", "-1", "-3" },
 547
 548         { &int_test_cdiv, "1", "1", "2" },
 549         { &int_test_cdiv, "0", "-1", "2" },
 550         { &int_test_cdiv, "0", "1", "-2" },
 551         { &int_test_cdiv, "1", "-1", "-2" },
 552
 553         { &int_test_tdiv, "0", "1", "2" },
 554         { &int_test_tdiv, "0", "-1", "2" },
 555         { &int_test_tdiv, "0", "1", "-2" },
 556         { &int_test_tdiv, "0", "-1", "-2" },
 557
 558         { &int_test_gcd, "0", "0", "0" },
 559         { &int_test_lcm, "0", "0", "0" },
 560         { &int_test_gcd, "7", "0", "7" },
 561         { &int_test_lcm, "0", "0", "7" },
 562         { &int_test_gcd, "1", "1", "1" },
 563         { &int_test_lcm, "1", "1", "1" },
 564         { &int_test_gcd, "1", "1", "-1" },
 565         { &int_test_lcm, "1", "1", "-1" },
 566         { &int_test_gcd, "1", "-1", "-1" },
 567         { &int_test_lcm, "1", "-1", "-1" },
 568         { &int_test_gcd, "3", "6", "9" },
 569         { &int_test_lcm, "18", "6", "9" },
 570         { &int_test_gcd, "1", "14", "2147483647" },
 571         { &int_test_lcm, "15032385529", "7", "2147483647" },
 572         { &int_test_gcd, "2", "6", "-2147483648" },
 573         { &int_test_lcm, "6442450944", "6", "-2147483648" },
 574         { &int_test_gcd, "1", "6", "9223372036854775807" },
 575         { &int_test_lcm, "55340232221128654842", "6", "9223372036854775807" },
 576         { &int_test_gcd, "2", "6", "-9223372036854775808" },
 577         { &int_test_lcm, "27670116110564327424", "6", "-9223372036854775808" },
 578         { &int_test_gcd, "1", "18446744073709551616", "18446744073709551615" },
 579         { &int_test_lcm, "340282366920938463444927863358058659840",
 580           "18446744073709551616", "18446744073709551615" },
 581
 582         { &int_test_cmps, "0", "0", "0" },
 583         { &int_test_abs_cmp, "0", "0", "0" },
 584         { &int_test_cmps, "1", "1", "0" },
 585         { &int_test_abs_cmp, "1", "1", "0" },
 586         { &int_test_cmps, "-1", "-1", "0" },
 587         { &int_test_abs_cmp, "1", "-1", "0" },
 588         { &int_test_cmps, "-1", "-1", "1" },
 589         { &int_test_abs_cmp, "0", "-1", "1" },
 590
 591         { &int_test_cmps, "-1", "5", "2147483647" },
 592         { &int_test_abs_cmp, "-1", "5", "2147483647" },
 593         { &int_test_cmps, "1", "5", "-2147483648" },
 594         { &int_test_abs_cmp, "-1", "5", "-2147483648" },
 595         { &int_test_cmps, "-1", "5", "9223372036854775807" },
 596         { &int_test_abs_cmp, "-1", "5", "9223372036854775807" },
 597         { &int_test_cmps, "1", "5", "-9223372036854775809" },
 598         { &int_test_abs_cmp, "-1", "5", "-9223372036854775809" },
 599 };
 600
 601 /* Tests the isl_int_* function to give the expected results. Tests are
 602  * grouped by the number of arguments they take.
 603  *
 604  * If small integer optimization is enabled, we also test whether the results
 605  * are the same in small and big representation.
 606  */
 607 int main()
 608 {
 609         int i;
 610
 611         int_test_single_value();
 612
 613         for (i = 0; i < ARRAY_SIZE(int_unary_tests); i += 1) {
 614                 invoke_alternate_representations_2args(
 615                     int_unary_tests[i].expected, int_unary_tests[i].arg,
 616                     int_unary_tests[i].fn);
 617         }
 618
 619         for (i = 0; i < ARRAY_SIZE(int_binary_tests); i += 1) {
 620                 invoke_alternate_representations_3args(
 621                     int_binary_tests[i].expected, int_binary_tests[i].lhs,
 622                     int_binary_tests[i].rhs, int_binary_tests[i].fn);
 623         }
 624
 625         return 0;
 626 }