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