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
  42 struct {
  43         void (*fn)(isl_int);
  44         char *val;
  45 } int_single_value_tests[] = {
  46         { &int_test_hash, "0" },
  47         { &int_test_hash, "1" },
  48         { &int_test_hash, "-1" },
  49         { &int_test_hash, "23" },
  50         { &int_test_hash, "-23" },
  51         { &int_test_hash, "107" },
  52         { &int_test_hash, "32768" },
  53         { &int_test_hash, "2147483647" },
  54         { &int_test_hash, "-2147483647" },
  55         { &int_test_hash, "2147483648" },
  56         { &int_test_hash, "-2147483648" },
  57 };
  58
  59 static void int_test_single_value()
  60 {
  61         int i;
  62
  63         for (i = 0; i < ARRAY_SIZE(int_single_value_tests); i += 1) {
  64                 isl_int val;
  65
  66                 isl_int_init(val);
  67                 isl_int_read(val, int_single_value_tests[i].val);
  68
  69                 (*int_single_value_tests[i].fn)(val);
  70
  71                 isl_int_clear(val);
  72         }
  73 }
  74
  75 static void invoke_alternate_representations_2args(char *arg1, char *arg2,
  76         void (*fn)(isl_int, isl_int))
  77 {
  78         int j;
  79         isl_int int1, int2;
  80
  81         isl_int_init(int1);
  82         isl_int_init(int2);
  83
  84         for (j = 0; j < 4; ++j) {
  85                 isl_int_read(int1, arg1);
  86                 isl_int_read(int2, arg2);
  87
  88                 if (j & 1)
  89                         isl_sioimath_promote(&int1);
  90                 else
  91                         isl_sioimath_try_demote(&int1);
  92
  93                 if (j & 2)
  94                         isl_sioimath_promote(&int2);
  95                 else
  96                         isl_sioimath_try_demote(&int2);
  97
  98                 (*fn)(int1, int2);
  99         }
 100
 101         isl_int_clear(int1);
 102         isl_int_clear(int2);
 103 }
 104
 105 static void invoke_alternate_representations_3args(char *arg1, char *arg2,
 106         char *arg3, void (*fn)(isl_int, isl_int, isl_int))
 107 {
 108         int j;
 109         isl_int int1, int2, int3;
 110
 111         isl_int_init(int1);
 112         isl_int_init(int2);
 113         isl_int_init(int3);
 114
 115         for (j = 0; j < 8; ++j) {
 116                 isl_int_read(int1, arg1);
 117                 isl_int_read(int2, arg2);
 118                 isl_int_read(int3, arg3);
 119
 120                 if (j & 1)
 121                         isl_sioimath_promote(&int1);
 122                 else
 123                         isl_sioimath_try_demote(&int1);
 124
 125                 if (j & 2)
 126                         isl_sioimath_promote(&int2);
 127                 else
 128                         isl_sioimath_try_demote(&int2);
 129
 130                 if (j & 4)
 131                         isl_sioimath_promote(&int3);
 132                 else
 133                         isl_sioimath_try_demote(&int3);
 134
 135                 (*fn)(int1, int2, int3);
 136         }
 137
 138         isl_int_clear(int1);
 139         isl_int_clear(int2);
 140         isl_int_clear(int3);
 141 }
 142 #else  /* USE_SMALL_INT_OPT */
 143
 144 static void int_test_single_value()
 145 {
 146 }
 147
 148 static void invoke_alternate_representations_2args(char *arg1, char *arg2,
 149         void (*fn)(isl_int, isl_int))
 150 {
 151         isl_int int1, int2;
 152
 153         isl_int_init(int1);
 154         isl_int_init(int2);
 155
 156         isl_int_read(int1, arg1);
 157         isl_int_read(int2, arg2);
 158
 159         (*fn)(int1, int2);
 160
 161         isl_int_clear(int1);
 162         isl_int_clear(int2);
 163 }
 164
 165 static void invoke_alternate_representations_3args(char *arg1, char *arg2,
 166         char *arg3, void (*fn)(isl_int, isl_int, isl_int))
 167 {
 168         isl_int int1, int2, int3;
 169
 170         isl_int_init(int1);
 171         isl_int_init(int2);
 172         isl_int_init(int3);
 173
 174         isl_int_read(int1, arg1);
 175         isl_int_read(int2, arg2);
 176         isl_int_read(int3, arg3);
 177
 178         (*fn)(int1, int2, int3);
 179
 180         isl_int_clear(int1);
 181         isl_int_clear(int2);
 182         isl_int_clear(int3);
 183 }
 184 #endif /* USE_SMALL_INT_OPT */
 185
 186 static void int_test_neg(isl_int expected, isl_int arg)
 187 {
 188         isl_int result;
 189         isl_int_init(result);
 190
 191         isl_int_neg(result, arg);
 192         assert(isl_int_eq(result, expected));
 193
 194         isl_int_neg(result, expected);
 195         assert(isl_int_eq(result, arg));
 196
 197         isl_int_clear(result);
 198 }
 199
 200 static void int_test_abs(isl_int expected, isl_int arg)
 201 {
 202         isl_int result;
 203         isl_int_init(result);
 204
 205         isl_int_abs(result, arg);
 206         assert(isl_int_eq(result, expected));
 207
 208         isl_int_clear(result);
 209 }
 210
 211 struct {
 212         void (*fn)(isl_int, isl_int);
 213         char *expected, *arg;
 214 } int_unary_tests[] = {
 215         { &int_test_neg, "0", "0" },
 216         { &int_test_neg, "-1", "1" },
 217         { &int_test_neg, "-2147483647", "2147483647" },
 218         { &int_test_neg, "-2147483648", "2147483648" },
 219         { &int_test_neg, "-9223372036854775807", "9223372036854775807" },
 220         { &int_test_neg, "-9223372036854775808", "9223372036854775808" },
 221
 222         { &int_test_abs, "0", "0" },
 223         { &int_test_abs, "1", "1" },
 224         { &int_test_abs, "1", "-1" },
 225         { &int_test_abs, "2147483647", "2147483647" },
 226         { &int_test_abs, "2147483648", "-2147483648" },
 227         { &int_test_abs, "9223372036854775807", "9223372036854775807" },
 228         { &int_test_abs, "9223372036854775808", "-9223372036854775808" },
 229 };
 230
 231 static void int_test_divexact(isl_int expected, isl_int lhs, isl_int rhs)
 232 {
 233         isl_int result;
 234         unsigned long rhsulong;
 235
 236         if (isl_int_sgn(rhs) == 0)
 237                 return;
 238
 239         isl_int_init(result);
 240
 241         isl_int_divexact(result, lhs, rhs);
 242         assert(isl_int_eq(expected, result));
 243
 244         isl_int_tdiv_q(result, lhs, rhs);
 245         assert(isl_int_eq(expected, result));
 246
 247         isl_int_fdiv_q(result, lhs, rhs);
 248         assert(isl_int_eq(expected, result));
 249
 250         isl_int_cdiv_q(result, lhs, rhs);
 251         assert(isl_int_eq(expected, result));
 252
 253         if (isl_int_fits_ulong(rhs)) {
 254                 rhsulong = isl_int_get_ui(rhs);
 255
 256                 isl_int_divexact_ui(result, lhs, rhsulong);
 257                 assert(isl_int_eq(expected, result));
 258
 259                 isl_int_fdiv_q_ui(result, lhs, rhsulong);
 260                 assert(isl_int_eq(expected, result));
 261         }
 262
 263         isl_int_clear(result);
 264 }
 265
 266 static void int_test_mul(isl_int expected, isl_int lhs, isl_int rhs)
 267 {
 268         isl_int result;
 269         isl_int_init(result);
 270
 271         isl_int_mul(result, lhs, rhs);
 272         assert(isl_int_eq(expected, result));
 273
 274         if (isl_int_fits_ulong(rhs)) {
 275                 unsigned long rhsulong = isl_int_get_ui(rhs);
 276
 277                 isl_int_mul_ui(result, lhs, rhsulong);
 278                 assert(isl_int_eq(expected, result));
 279         }
 280
 281         if (isl_int_fits_slong(rhs)) {
 282                 unsigned long rhsslong = isl_int_get_si(rhs);
 283
 284                 isl_int_mul_si(result, lhs, rhsslong);
 285                 assert(isl_int_eq(expected, result));
 286         }
 287
 288         isl_int_clear(result);
 289 }
 290
 291 /* Use a triple that satisfies 'product = factor1 * factor2' to check the
 292  * operations mul, divexact, tdiv, fdiv and cdiv.
 293  */
 294 static void int_test_product(isl_int product, isl_int factor1, isl_int factor2)
 295 {
 296         int_test_divexact(factor1, product, factor2);
 297         int_test_divexact(factor2, product, factor1);
 298
 299         int_test_mul(product, factor1, factor2);
 300         int_test_mul(product, factor2, factor1);
 301 }
 302
 303 static void int_test_add(isl_int expected, isl_int lhs, isl_int rhs)
 304 {
 305         isl_int result;
 306         isl_int_init(result);
 307
 308         isl_int_add(result, lhs, rhs);
 309         assert(isl_int_eq(expected, result));
 310
 311         isl_int_clear(result);
 312 }
 313
 314 static void int_test_sub(isl_int expected, isl_int lhs, isl_int rhs)
 315 {
 316         isl_int result;
 317         isl_int_init(result);
 318
 319         isl_int_sub(result, lhs, rhs);
 320         assert(isl_int_eq(expected, result));
 321
 322         isl_int_clear(result);
 323 }
 324
 325 /* Use a triple that satisfies 'sum = term1 + term2' to check the operations add
 326  * and sub.
 327  */
 328 static void int_test_sum(isl_int sum, isl_int term1, isl_int term2)
 329 {
 330         int_test_sub(term1, sum, term2);
 331         int_test_sub(term2, sum, term1);
 332
 333         int_test_add(sum, term1, term2);
 334         int_test_add(sum, term2, term1);
 335 }
 336
 337 static void int_test_fdiv(isl_int expected, isl_int lhs, isl_int rhs)
 338 {
 339         unsigned long rhsulong;
 340         isl_int result;
 341         isl_int_init(result);
 342
 343         isl_int_fdiv_q(result, lhs, rhs);
 344         assert(isl_int_eq(expected, result));
 345
 346         if (isl_int_fits_ulong(rhs)) {
 347                 rhsulong = isl_int_get_ui(rhs);
 348
 349                 isl_int_fdiv_q_ui(result, lhs, rhsulong);
 350                 assert(isl_int_eq(expected, result));
 351         }
 352
 353         isl_int_clear(result);
 354 }
 355
 356 static void int_test_cdiv(isl_int expected, isl_int lhs, isl_int rhs)
 357 {
 358         isl_int result;
 359         isl_int_init(result);
 360
 361         isl_int_cdiv_q(result, lhs, rhs);
 362         assert(isl_int_eq(expected, result));
 363
 364         isl_int_clear(result);
 365 }
 366
 367 static void int_test_tdiv(isl_int expected, isl_int lhs, isl_int rhs)
 368 {
 369         isl_int result;
 370         isl_int_init(result);
 371
 372         isl_int_tdiv_q(result, lhs, rhs);
 373         assert(isl_int_eq(expected, result));
 374
 375         isl_int_clear(result);
 376 }
 377
 378 static void int_test_fdiv_r(isl_int expected, isl_int lhs, isl_int rhs)
 379 {
 380         isl_int result;
 381         isl_int_init(result);
 382
 383         isl_int_fdiv_r(result, lhs, rhs);
 384         assert(isl_int_eq(expected, result));
 385
 386         isl_int_clear(result);
 387 }
 388
 389 static void int_test_gcd(isl_int expected, isl_int lhs, isl_int rhs)
 390 {
 391         isl_int result;
 392         isl_int_init(result);
 393
 394         isl_int_gcd(result, lhs, rhs);
 395         assert(isl_int_eq(expected, result));
 396
 397         isl_int_gcd(result, rhs, lhs);
 398         assert(isl_int_eq(expected, result));
 399
 400         isl_int_clear(result);
 401 }
 402
 403 static void int_test_lcm(isl_int expected, isl_int lhs, isl_int rhs)
 404 {
 405         isl_int result;
 406         isl_int_init(result);
 407
 408         isl_int_lcm(result, lhs, rhs);
 409         assert(isl_int_eq(expected, result));
 410
 411         isl_int_lcm(result, rhs, lhs);
 412         assert(isl_int_eq(expected, result));
 413
 414         isl_int_clear(result);
 415 }
 416
 417 static int sgn(int val)
 418 {
 419         if (val > 0)
 420                 return 1;
 421         if (val < 0)
 422                 return -1;
 423         return 0;
 424 }
 425
 426 static void int_test_cmp(int exp, isl_int lhs, isl_int rhs)
 427 {
 428         long rhslong;
 429
 430         assert(exp == sgn(isl_int_cmp(lhs, rhs)));
 431
 432         if (isl_int_fits_slong(rhs)) {
 433                 rhslong = isl_int_get_si(rhs);
 434                 assert(exp == sgn(isl_int_cmp_si(lhs, rhslong)));
 435         }
 436 }
 437
 438 /* Test the comparison relations over two numbers.
 439  * expected is the sign (1, 0 or -1) of 'lhs - rhs'.
 440  */
 441 static void int_test_cmps(isl_int expected, isl_int lhs, isl_int rhs)
 442 {
 443         int exp;
 444         isl_int diff;
 445
 446         exp = isl_int_get_si(expected);
 447
 448         isl_int_init(diff);
 449         isl_int_sub(diff, lhs, rhs);
 450         assert(exp == isl_int_sgn(diff));
 451         isl_int_clear(diff);
 452
 453         int_test_cmp(exp, lhs, rhs);
 454         int_test_cmp(-exp, rhs, lhs);
 455 }
 456
 457 static void int_test_abs_cmp(isl_int expected, isl_int lhs, isl_int rhs)
 458 {
 459         int exp;
 460
 461         exp = isl_int_get_si(expected);
 462         assert(exp == sgn(isl_int_abs_cmp(lhs, rhs)));
 463         assert(-exp == sgn(isl_int_abs_cmp(rhs, lhs)));
 464 }
 465
 466 struct {
 467         void (*fn)(isl_int, isl_int, isl_int);
 468         char *expected, *lhs, *rhs;
 469 } int_binary_tests[] = {
 470         { &int_test_sum, "0", "0", "0" },
 471         { &int_test_sum, "1", "1", "0" },
 472         { &int_test_sum, "2", "1", "1" },
 473         { &int_test_sum, "-1", "0", "-1" },
 474         { &int_test_sum, "-2", "-1", "-1" },
 475
 476         { &int_test_sum, "2147483647", "1073741823", "1073741824" },
 477         { &int_test_sum, "-2147483648", "-1073741824", "-1073741824" },
 478
 479         { &int_test_sum, "2147483648", "2147483647", "1" },
 480         { &int_test_sum, "-2147483648", "-2147483647", "-1" },
 481
 482         { &int_test_product, "0", "0", "0" },
 483         { &int_test_product, "0", "0", "1" },
 484         { &int_test_product, "1", "1", "1" },
 485
 486         { &int_test_product, "6", "2", "3" },
 487         { &int_test_product, "-6", "2", "-3" },
 488         { &int_test_product, "-6", "-2", "3" },
 489         { &int_test_product, "6", "-2", "-3" },
 490
 491         { &int_test_product, "2147483648", "65536", "32768" },
 492         { &int_test_product, "-2147483648", "65536", "-32768" },
 493
 494         { &int_test_product,
 495           "4611686014132420609", "2147483647", "2147483647" },
 496         { &int_test_product,
 497           "-4611686014132420609", "-2147483647", "2147483647" },
 498
 499         { &int_test_product,
 500           "4611686016279904256", "2147483647", "2147483648" },
 501         { &int_test_product,
 502           "-4611686016279904256", "-2147483647", "2147483648" },
 503         { &int_test_product,
 504           "-4611686016279904256", "2147483647", "-2147483648" },
 505         { &int_test_product,
 506           "4611686016279904256", "-2147483647", "-2147483648" },
 507
 508         { &int_test_product, "85070591730234615847396907784232501249",
 509           "9223372036854775807", "9223372036854775807" },
 510         { &int_test_product, "-85070591730234615847396907784232501249",
 511           "-9223372036854775807", "9223372036854775807" },
 512
 513         { &int_test_product, "85070591730234615856620279821087277056",
 514           "9223372036854775807", "9223372036854775808" },
 515         { &int_test_product, "-85070591730234615856620279821087277056",
 516           "-9223372036854775807", "9223372036854775808" },
 517         { &int_test_product, "-85070591730234615856620279821087277056",
 518           "9223372036854775807", "-9223372036854775808" },
 519         { &int_test_product, "85070591730234615856620279821087277056",
 520           "-9223372036854775807", "-9223372036854775808" },
 521
 522         { &int_test_product, "340282366920938463426481119284349108225",
 523           "18446744073709551615", "18446744073709551615" },
 524         { &int_test_product, "-340282366920938463426481119284349108225",
 525           "-18446744073709551615", "18446744073709551615" },
 526
 527         { &int_test_product, "340282366920938463444927863358058659840",
 528           "18446744073709551615", "18446744073709551616" },
 529         { &int_test_product, "-340282366920938463444927863358058659840",
 530           "-18446744073709551615", "18446744073709551616" },
 531         { &int_test_product, "-340282366920938463444927863358058659840",
 532           "18446744073709551615", "-18446744073709551616" },
 533         { &int_test_product, "340282366920938463444927863358058659840",
 534           "-18446744073709551615", "-18446744073709551616" },
 535
 536         { &int_test_fdiv, "0", "1", "2" },
 537         { &int_test_fdiv_r, "1", "1", "3" },
 538         { &int_test_fdiv, "-1", "-1", "2" },
 539         { &int_test_fdiv_r, "2", "-1", "3" },
 540         { &int_test_fdiv, "-1", "1", "-2" },
 541         { &int_test_fdiv_r, "-2", "1", "-3" },
 542         { &int_test_fdiv, "0", "-1", "-2" },
 543         { &int_test_fdiv_r, "-1", "-1", "-3" },
 544
 545         { &int_test_cdiv, "1", "1", "2" },
 546         { &int_test_cdiv, "0", "-1", "2" },
 547         { &int_test_cdiv, "0", "1", "-2" },
 548         { &int_test_cdiv, "1", "-1", "-2" },
 549
 550         { &int_test_tdiv, "0", "1", "2" },
 551         { &int_test_tdiv, "0", "-1", "2" },
 552         { &int_test_tdiv, "0", "1", "-2" },
 553         { &int_test_tdiv, "0", "-1", "-2" },
 554
 555         { &int_test_gcd, "0", "0", "0" },
 556         { &int_test_lcm, "0", "0", "0" },
 557         { &int_test_gcd, "7", "0", "7" },
 558         { &int_test_lcm, "0", "0", "7" },
 559         { &int_test_gcd, "1", "1", "1" },
 560         { &int_test_lcm, "1", "1", "1" },
 561         { &int_test_gcd, "1", "1", "-1" },
 562         { &int_test_lcm, "1", "1", "-1" },
 563         { &int_test_gcd, "1", "-1", "-1" },
 564         { &int_test_lcm, "1", "-1", "-1" },
 565         { &int_test_gcd, "3", "6", "9" },
 566         { &int_test_lcm, "18", "6", "9" },
 567         { &int_test_gcd, "1", "14", "2147483647" },
 568         { &int_test_lcm, "15032385529", "7", "2147483647" },
 569         { &int_test_gcd, "2", "6", "-2147483648" },
 570         { &int_test_lcm, "6442450944", "6", "-2147483648" },
 571         { &int_test_gcd, "1", "6", "9223372036854775807" },
 572         { &int_test_lcm, "55340232221128654842", "6", "9223372036854775807" },
 573         { &int_test_gcd, "2", "6", "-9223372036854775808" },
 574         { &int_test_lcm, "27670116110564327424", "6", "-9223372036854775808" },
 575         { &int_test_gcd, "1", "18446744073709551616", "18446744073709551615" },
 576         { &int_test_lcm, "340282366920938463444927863358058659840",
 577           "18446744073709551616", "18446744073709551615" },
 578
 579         { &int_test_cmps, "0", "0", "0" },
 580         { &int_test_abs_cmp, "0", "0", "0" },
 581         { &int_test_cmps, "1", "1", "0" },
 582         { &int_test_abs_cmp, "1", "1", "0" },
 583         { &int_test_cmps, "-1", "-1", "0" },
 584         { &int_test_abs_cmp, "1", "-1", "0" },
 585         { &int_test_cmps, "-1", "-1", "1" },
 586         { &int_test_abs_cmp, "0", "-1", "1" },
 587
 588         { &int_test_cmps, "-1", "5", "2147483647" },
 589         { &int_test_abs_cmp, "-1", "5", "2147483647" },
 590         { &int_test_cmps, "1", "5", "-2147483648" },
 591         { &int_test_abs_cmp, "-1", "5", "-2147483648" },
 592         { &int_test_cmps, "-1", "5", "9223372036854775807" },
 593         { &int_test_abs_cmp, "-1", "5", "9223372036854775807" },
 594         { &int_test_cmps, "1", "5", "-9223372036854775809" },
 595         { &int_test_abs_cmp, "-1", "5", "-9223372036854775809" },
 596 };
 597
 598 /* Tests the isl_int_* function to give the expected results. Tests are
 599  * grouped by the number of arguments they take.
 600  *
 601  * If small integer optimization is enabled, we also test whether the results
 602  * are the same in small and big representation.
 603  */
 604 int main()
 605 {
 606         int i;
 607
 608         int_test_single_value();
 609
 610         for (i = 0; i < ARRAY_SIZE(int_unary_tests); i += 1) {
 611                 invoke_alternate_representations_2args(
 612                     int_unary_tests[i].expected, int_unary_tests[i].arg,
 613                     int_unary_tests[i].fn);
 614         }
 615
 616         for (i = 0; i < ARRAY_SIZE(int_binary_tests); i += 1) {
 617                 invoke_alternate_representations_3args(
 618                     int_binary_tests[i].expected, int_binary_tests[i].lhs,
 619                     int_binary_tests[i].rhs, int_binary_tests[i].fn);
 620         }
 621
 622         return 0;
 623 }