isl_val.c

   1 /*
   2  * Copyright 2013      Ecole Normale Superieure
   3  *
   4  * Use of this software is governed by the MIT license
   5  *
   6  * Written by Sven Verdoolaege,
   7  * Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
   8  */
   9
  10 #include <isl_int.h>
  11 #include <isl_ctx_private.h>
  12 #include <isl_val_private.h>
  13
  14 /* Allocate an isl_val object with indeterminate value.
  15  */
  16 __isl_give isl_val *isl_val_alloc(isl_ctx *ctx)
  17 {
  18         isl_val *v;
  19
  20         v = isl_alloc_type(ctx, struct isl_val);
  21         if (!v)
  22                 return NULL;
  23
  24         v->ctx = ctx;
  25         isl_ctx_ref(ctx);
  26         v->ref = 1;
  27         isl_int_init(v->n);
  28         isl_int_init(v->d);
  29
  30         return v;
  31 }
  32
  33 /* Return a reference to an isl_val representing zero.
  34  */
  35 __isl_give isl_val *isl_val_zero(isl_ctx *ctx)
  36 {
  37         return isl_val_int_from_si(ctx, 0);
  38 }
  39
  40 /* Return a reference to an isl_val representing one.
  41  */
  42 __isl_give isl_val *isl_val_one(isl_ctx *ctx)
  43 {
  44         return isl_val_int_from_si(ctx, 1);
  45 }
  46
  47 /* Return a reference to an isl_val representing NaN.
  48  */
  49 __isl_give isl_val *isl_val_nan(isl_ctx *ctx)
  50 {
  51         isl_val *v;
  52
  53         v = isl_val_alloc(ctx);
  54         if (!v)
  55                 return NULL;
  56
  57         isl_int_set_si(v->n, 0);
  58         isl_int_set_si(v->d, 0);
  59
  60         return v;
  61 }
  62
  63 /* Change "v" into a NaN.
  64  */
  65 __isl_give isl_val *isl_val_set_nan(__isl_take isl_val *v)
  66 {
  67         if (!v)
  68                 return NULL;
  69         if (isl_val_is_nan(v))
  70                 return v;
  71         v = isl_val_cow(v);
  72         if (!v)
  73                 return NULL;
  74
  75         isl_int_set_si(v->n, 0);
  76         isl_int_set_si(v->d, 0);
  77
  78         return v;
  79 }
  80
  81 /* Return a reference to an isl_val representing +infinity.
  82  */
  83 __isl_give isl_val *isl_val_infty(isl_ctx *ctx)
  84 {
  85         isl_val *v;
  86
  87         v = isl_val_alloc(ctx);
  88         if (!v)
  89                 return NULL;
  90
  91         isl_int_set_si(v->n, 1);
  92         isl_int_set_si(v->d, 0);
  93
  94         return v;
  95 }
  96
  97 /* Return a reference to an isl_val representing -infinity.
  98  */
  99 __isl_give isl_val *isl_val_neginfty(isl_ctx *ctx)
 100 {
 101         isl_val *v;
 102
 103         v = isl_val_alloc(ctx);
 104         if (!v)
 105                 return NULL;
 106
 107         isl_int_set_si(v->n, -1);
 108         isl_int_set_si(v->d, 0);
 109
 110         return v;
 111 }
 112
 113 /* Return a reference to an isl_val representing the integer "i".
 114  */
 115 __isl_give isl_val *isl_val_int_from_si(isl_ctx *ctx, long i)
 116 {
 117         isl_val *v;
 118
 119         v = isl_val_alloc(ctx);
 120         if (!v)
 121                 return NULL;
 122
 123         isl_int_set_si(v->n, i);
 124         isl_int_set_si(v->d, 1);
 125
 126         return v;
 127 }
 128
 129 /* Change the value of "v" to be equal to the integer "i".
 130  */
 131 __isl_give isl_val *isl_val_set_si(__isl_take isl_val *v, long i)
 132 {
 133         if (!v)
 134                 return NULL;
 135         if (isl_val_is_int(v) && isl_int_cmp_si(v->n, i) == 0)
 136                 return v;
 137         v = isl_val_cow(v);
 138         if (!v)
 139                 return NULL;
 140
 141         isl_int_set_si(v->n, i);
 142         isl_int_set_si(v->d, 1);
 143
 144         return v;
 145 }
 146
 147 /* Change the value of "v" to be equal to zero.
 148  */
 149 __isl_give isl_val *isl_val_set_zero(__isl_take isl_val *v)
 150 {
 151         return isl_val_set_si(v, 0);
 152 }
 153
 154 /* Return a reference to an isl_val representing the unsigned integer "u".
 155  */
 156 __isl_give isl_val *isl_val_int_from_ui(isl_ctx *ctx, unsigned long u)
 157 {
 158         isl_val *v;
 159
 160         v = isl_val_alloc(ctx);
 161         if (!v)
 162                 return NULL;
 163
 164         isl_int_set_ui(v->n, u);
 165         isl_int_set_si(v->d, 1);
 166
 167         return v;
 168 }
 169
 170 /* Return a reference to an isl_val representing the integer "n".
 171  */
 172 __isl_give isl_val *isl_val_int_from_isl_int(isl_ctx *ctx, isl_int n)
 173 {
 174         isl_val *v;
 175
 176         v = isl_val_alloc(ctx);
 177         if (!v)
 178                 return NULL;
 179
 180         isl_int_set(v->n, n);
 181         isl_int_set_si(v->d, 1);
 182
 183         return v;
 184 }
 185
 186 /* Return a reference to an isl_val representing the rational value "n"/"d".
 187  * Normalizing the isl_val (if needed) is left to the caller.
 188  */
 189 __isl_give isl_val *isl_val_rat_from_isl_int(isl_ctx *ctx,
 190         isl_int n, isl_int d)
 191 {
 192         isl_val *v;
 193
 194         v = isl_val_alloc(ctx);
 195         if (!v)
 196                 return NULL;
 197
 198         isl_int_set(v->n, n);
 199         isl_int_set(v->d, d);
 200
 201         return v;
 202 }
 203
 204 /* Return a new reference to "v".
 205  */
 206 __isl_give isl_val *isl_val_copy(__isl_keep isl_val *v)
 207 {
 208         if (!v)
 209                 return NULL;
 210
 211         v->ref++;
 212         return v;
 213 }
 214
 215 /* Return a fresh copy of "val".
 216  */
 217 __isl_give isl_val *isl_val_dup(__isl_keep isl_val *val)
 218 {
 219         isl_val *dup;
 220
 221         if (!val)
 222                 return NULL;
 223
 224         dup = isl_val_alloc(isl_val_get_ctx(val));
 225         if (!dup)
 226                 return NULL;
 227
 228         isl_int_set(dup->n, val->n);
 229         isl_int_set(dup->d, val->d);
 230
 231         return dup;
 232 }
 233
 234 /* Return an isl_val that is equal to "val" and that has only
 235  * a single reference.
 236  */
 237 __isl_give isl_val *isl_val_cow(__isl_take isl_val *val)
 238 {
 239         if (!val)
 240                 return NULL;
 241
 242         if (val->ref == 1)
 243                 return val;
 244         val->ref--;
 245         return isl_val_dup(val);
 246 }
 247
 248 /* Free "v" and return NULL.
 249  */
 250 void *isl_val_free(__isl_take isl_val *v)
 251 {
 252         if (!v)
 253                 return NULL;
 254
 255         if (--v->ref > 0)
 256                 return NULL;
 257
 258         isl_ctx_deref(v->ctx);
 259         isl_int_clear(v->n);
 260         isl_int_clear(v->d);
 261         free(v);
 262         return NULL;
 263 }
 264
 265 /* Extract the numerator of a rational value "v" as an integer.
 266  *
 267  * If "v" is not a rational value, then the result is undefined.
 268  */
 269 long isl_val_get_num_si(__isl_keep isl_val *v)
 270 {
 271         if (!v)
 272                 return 0;
 273         if (!isl_val_is_rat(v))
 274                 isl_die(isl_val_get_ctx(v), isl_error_invalid,
 275                         "expecting rational value", return 0);
 276         if (!isl_int_fits_slong(v->n))
 277                 isl_die(isl_val_get_ctx(v), isl_error_invalid,
 278                         "numerator too large", return 0);
 279         return isl_int_get_si(v->n);
 280 }
 281
 282 /* Extract the denominator of a rational value "v" as an integer.
 283  *
 284  * If "v" is not a rational value, then the result is undefined.
 285  */
 286 long isl_val_get_den_si(__isl_keep isl_val *v)
 287 {
 288         if (!v)
 289                 return 0;
 290         if (!isl_val_is_rat(v))
 291                 isl_die(isl_val_get_ctx(v), isl_error_invalid,
 292                         "expecting rational value", return 0);
 293         if (!isl_int_fits_slong(v->d))
 294                 isl_die(isl_val_get_ctx(v), isl_error_invalid,
 295                         "denominator too large", return 0);
 296         return isl_int_get_si(v->d);
 297 }
 298
 299 /* Return an approximation of "v" as a double.
 300  */
 301 double isl_val_get_d(__isl_keep isl_val *v)
 302 {
 303         if (!v)
 304                 return 0;
 305         if (!isl_val_is_rat(v))
 306                 isl_die(isl_val_get_ctx(v), isl_error_invalid,
 307                         "expecting rational value", return 0);
 308         return isl_int_get_d(v->n) / isl_int_get_d(v->d);
 309 }
 310
 311 /* Return the isl_ctx to which "val" belongs.
 312  */
 313 isl_ctx *isl_val_get_ctx(__isl_keep isl_val *val)
 314 {
 315         return val ? val->ctx : NULL;
 316 }
 317
 318 /* Normalize "v".
 319  *
 320  * In particular, make sure that the denominator of a rational value
 321  * is positive and the numerator and denominator do not have any
 322  * common divisors.
 323  *
 324  * This function should not be called by an external user
 325  * since it will only be given normalized values.
 326  */
 327 __isl_give isl_val *isl_val_normalize(__isl_take isl_val *v)
 328 {
 329         isl_ctx *ctx;
 330
 331         if (!v)
 332                 return NULL;
 333         if (isl_val_is_int(v))
 334                 return v;
 335         if (!isl_val_is_rat(v))
 336                 return v;
 337         if (isl_int_is_neg(v->d)) {
 338                 isl_int_neg(v->d, v->d);
 339                 isl_int_neg(v->n, v->n);
 340         }
 341         ctx = isl_val_get_ctx(v);
 342         isl_int_gcd(ctx->normalize_gcd, v->n, v->d);
 343         if (isl_int_is_one(ctx->normalize_gcd))
 344                 return v;
 345         isl_int_divexact(v->n, v->n, ctx->normalize_gcd);
 346         isl_int_divexact(v->d, v->d, ctx->normalize_gcd);
 347         return v;
 348 }
 349
 350 /* Return the opposite of "v".
 351  */
 352 __isl_give isl_val *isl_val_neg(__isl_take isl_val *v)
 353 {
 354         if (!v)
 355                 return NULL;
 356         if (isl_val_is_nan(v))
 357                 return v;
 358         if (isl_val_is_zero(v))
 359                 return v;
 360
 361         v = isl_val_cow(v);
 362         if (!v)
 363                 return NULL;
 364         isl_int_neg(v->n, v->n);
 365
 366         return v;
 367 }
 368
 369 /* Return the absolute value of "v".
 370  */
 371 __isl_give isl_val *isl_val_abs(__isl_take isl_val *v)
 372 {
 373         if (!v)
 374                 return NULL;
 375         if (isl_val_is_nan(v))
 376                 return v;
 377         if (isl_val_is_nonneg(v))
 378                 return v;
 379         return isl_val_neg(v);
 380 }
 381
 382 /* Return the "floor" (greatest integer part) of "v".
 383  * That is, return the result of rounding towards -infinity.
 384  */
 385 __isl_give isl_val *isl_val_floor(__isl_take isl_val *v)
 386 {
 387         if (!v)
 388                 return NULL;
 389         if (isl_val_is_int(v))
 390                 return v;
 391         if (!isl_val_is_rat(v))
 392                 return v;
 393
 394         v = isl_val_cow(v);
 395         if (!v)
 396                 return NULL;
 397         isl_int_fdiv_q(v->n, v->n, v->d);
 398         isl_int_set_si(v->d, 1);
 399
 400         return v;
 401 }
 402
 403 /* Return the "ceiling" of "v".
 404  * That is, return the result of rounding towards +infinity.
 405  */
 406 __isl_give isl_val *isl_val_ceil(__isl_take isl_val *v)
 407 {
 408         if (!v)
 409                 return NULL;
 410         if (isl_val_is_int(v))
 411                 return v;
 412         if (!isl_val_is_rat(v))
 413                 return v;
 414
 415         v = isl_val_cow(v);
 416         if (!v)
 417                 return NULL;
 418         isl_int_cdiv_q(v->n, v->n, v->d);
 419         isl_int_set_si(v->d, 1);
 420
 421         return v;
 422 }
 423
 424 /* Truncate "v".
 425  * That is, return the result of rounding towards zero.
 426  */
 427 __isl_give isl_val *isl_val_trunc(__isl_take isl_val *v)
 428 {
 429         if (!v)
 430                 return NULL;
 431         if (isl_val_is_int(v))
 432                 return v;
 433         if (!isl_val_is_rat(v))
 434                 return v;
 435
 436         v = isl_val_cow(v);
 437         if (!v)
 438                 return NULL;
 439         isl_int_tdiv_q(v->n, v->n, v->d);
 440         isl_int_set_si(v->d, 1);
 441
 442         return v;
 443 }
 444
 445 /* Return 2^v, where v is an integer (that is not too large).
 446  */
 447 __isl_give isl_val *isl_val_2exp(__isl_take isl_val *v)
 448 {
 449         unsigned long exp;
 450         int neg;
 451
 452         v = isl_val_cow(v);
 453         if (!v)
 454                 return NULL;
 455         if (!isl_val_is_int(v))
 456                 isl_die(isl_val_get_ctx(v), isl_error_invalid,
 457                         "can only compute integer powers",
 458                         return isl_val_free(v));
 459         neg = isl_val_is_neg(v);
 460         if (neg)
 461                 isl_int_neg(v->n, v->n);
 462         if (!isl_int_fits_ulong(v->n))
 463                 isl_die(isl_val_get_ctx(v), isl_error_invalid,
 464                         "exponent too large", return isl_val_free(v));
 465         exp = isl_int_get_ui(v->n);
 466         if (neg) {
 467                 isl_int_mul_2exp(v->d, v->d, exp);
 468                 isl_int_set_si(v->n, 1);
 469         } else {
 470                 isl_int_mul_2exp(v->n, v->d, exp);
 471         }
 472
 473         return v;
 474 }
 475
 476 /* Return the minimum of "v1" and "v2".
 477  */
 478 __isl_give isl_val *isl_val_min(__isl_take isl_val *v1, __isl_take isl_val *v2)
 479 {
 480         if (!v1 || !v2)
 481                 goto error;
 482
 483         if (isl_val_is_nan(v1)) {
 484                 isl_val_free(v2);
 485                 return v1;
 486         }
 487         if (isl_val_is_nan(v2)) {
 488                 isl_val_free(v1);
 489                 return v2;
 490         }
 491         if (isl_val_le(v1, v2)) {
 492                 isl_val_free(v2);
 493                 return v1;
 494         } else {
 495                 isl_val_free(v1);
 496                 return v2;
 497         }
 498 error:
 499         isl_val_free(v1);
 500         isl_val_free(v2);
 501         return NULL;
 502 }
 503
 504 /* Return the maximum of "v1" and "v2".
 505  */
 506 __isl_give isl_val *isl_val_max(__isl_take isl_val *v1, __isl_take isl_val *v2)
 507 {
 508         if (!v1 || !v2)
 509                 goto error;
 510
 511         if (isl_val_is_nan(v1)) {
 512                 isl_val_free(v2);
 513                 return v1;
 514         }
 515         if (isl_val_is_nan(v2)) {
 516                 isl_val_free(v1);
 517                 return v2;
 518         }
 519         if (isl_val_ge(v1, v2)) {
 520                 isl_val_free(v2);
 521                 return v1;
 522         } else {
 523                 isl_val_free(v1);
 524                 return v2;
 525         }
 526 error:
 527         isl_val_free(v1);
 528         isl_val_free(v2);
 529         return NULL;
 530 }
 531
 532 /* Return the sum of "v1" and "v2".
 533  */
 534 __isl_give isl_val *isl_val_add(__isl_take isl_val *v1, __isl_take isl_val *v2)
 535 {
 536         if (!v1 || !v2)
 537                 goto error;
 538         if (isl_val_is_nan(v1)) {
 539                 isl_val_free(v2);
 540                 return v1;
 541         }
 542         if (isl_val_is_nan(v2)) {
 543                 isl_val_free(v1);
 544                 return v2;
 545         }
 546         if ((isl_val_is_infty(v1) && isl_val_is_neginfty(v2)) ||
 547             (isl_val_is_neginfty(v1) && isl_val_is_infty(v2))) {
 548                 isl_val_free(v2);
 549                 return isl_val_set_nan(v1);
 550         }
 551         if (isl_val_is_infty(v1) || isl_val_is_neginfty(v1)) {
 552                 isl_val_free(v2);
 553                 return v1;
 554         }
 555         if (isl_val_is_infty(v2) || isl_val_is_neginfty(v2)) {
 556                 isl_val_free(v1);
 557                 return v2;
 558         }
 559         if (isl_val_is_zero(v1)) {
 560                 isl_val_free(v1);
 561                 return v2;
 562         }
 563         if (isl_val_is_zero(v2)) {
 564                 isl_val_free(v2);
 565                 return v1;
 566         }
 567
 568         v1 = isl_val_cow(v1);
 569         if (!v1)
 570                 goto error;
 571         if (isl_val_is_int(v1) && isl_val_is_int(v2))
 572                 isl_int_add(v1->n, v1->n, v2->n);
 573         else {
 574                 if (isl_int_eq(v1->d, v2->d))
 575                         isl_int_add(v1->n, v1->n, v2->n);
 576                 else {
 577                         isl_int_mul(v1->n, v1->n, v2->d);
 578                         isl_int_addmul(v1->n, v2->n, v1->d);
 579                         isl_int_mul(v1->d, v1->d, v2->d);
 580                 }
 581                 v1 = isl_val_normalize(v1);
 582         }
 583         isl_val_free(v2);
 584         return v1;
 585 error:
 586         isl_val_free(v1);
 587         isl_val_free(v2);
 588         return NULL;
 589 }
 590
 591 /* Return the sum of "v1" and "v2".
 592  */
 593 __isl_give isl_val *isl_val_add_ui(__isl_take isl_val *v1, unsigned long v2)
 594 {
 595         if (!v1)
 596                 return NULL;
 597         if (!isl_val_is_rat(v1))
 598                 return v1;
 599         if (v2 == 0)
 600                 return v1;
 601         v1 = isl_val_cow(v1);
 602         if (!v1)
 603                 return NULL;
 604
 605         isl_int_addmul_ui(v1->n, v1->d, v2);
 606
 607         return v1;
 608 }
 609
 610 /* Subtract "v2" from "v1".
 611  */
 612 __isl_give isl_val *isl_val_sub(__isl_take isl_val *v1, __isl_take isl_val *v2)
 613 {
 614         if (!v1 || !v2)
 615                 goto error;
 616         if (isl_val_is_nan(v1)) {
 617                 isl_val_free(v2);
 618                 return v1;
 619         }
 620         if (isl_val_is_nan(v2)) {
 621                 isl_val_free(v1);
 622                 return v2;
 623         }
 624         if ((isl_val_is_infty(v1) && isl_val_is_infty(v2)) ||
 625             (isl_val_is_neginfty(v1) && isl_val_is_neginfty(v2))) {
 626                 isl_val_free(v2);
 627                 return isl_val_set_nan(v1);
 628         }
 629         if (isl_val_is_infty(v1) || isl_val_is_neginfty(v1)) {
 630                 isl_val_free(v2);
 631                 return v1;
 632         }
 633         if (isl_val_is_infty(v2) || isl_val_is_neginfty(v2)) {
 634                 isl_val_free(v1);
 635                 return isl_val_neg(v2);
 636         }
 637         if (isl_val_is_zero(v2)) {
 638                 isl_val_free(v2);
 639                 return v1;
 640         }
 641         if (isl_val_is_zero(v1)) {
 642                 isl_val_free(v1);
 643                 return isl_val_neg(v2);
 644         }
 645
 646         v1 = isl_val_cow(v1);
 647         if (!v1)
 648                 goto error;
 649         if (isl_val_is_int(v1) && isl_val_is_int(v2))
 650                 isl_int_sub(v1->n, v1->n, v2->n);
 651         else {
 652                 if (isl_int_eq(v1->d, v2->d))
 653                         isl_int_sub(v1->n, v1->n, v2->n);
 654                 else {
 655                         isl_int_mul(v1->n, v1->n, v2->d);
 656                         isl_int_submul(v1->n, v2->n, v1->d);
 657                         isl_int_mul(v1->d, v1->d, v2->d);
 658                 }
 659                 v1 = isl_val_normalize(v1);
 660         }
 661         isl_val_free(v2);
 662         return v1;
 663 error:
 664         isl_val_free(v1);
 665         isl_val_free(v2);
 666         return NULL;
 667 }
 668
 669 /* Subtract "v2" from "v1".
 670  */
 671 __isl_give isl_val *isl_val_sub_ui(__isl_take isl_val *v1, unsigned long v2)
 672 {
 673         if (!v1)
 674                 return NULL;
 675         if (!isl_val_is_rat(v1))
 676                 return v1;
 677         if (v2 == 0)
 678                 return v1;
 679         v1 = isl_val_cow(v1);
 680         if (!v1)
 681                 return NULL;
 682
 683         isl_int_submul_ui(v1->n, v1->d, v2);
 684
 685         return v1;
 686 }
 687
 688 /* Return the product of "v1" and "v2".
 689  */
 690 __isl_give isl_val *isl_val_mul(__isl_take isl_val *v1, __isl_take isl_val *v2)
 691 {
 692         if (!v1 || !v2)
 693                 goto error;
 694         if (isl_val_is_nan(v1)) {
 695                 isl_val_free(v2);
 696                 return v1;
 697         }
 698         if (isl_val_is_nan(v2)) {
 699                 isl_val_free(v1);
 700                 return v2;
 701         }
 702         if ((!isl_val_is_rat(v1) && isl_val_is_zero(v2)) ||
 703             (isl_val_is_zero(v1) && !isl_val_is_rat(v2))) {
 704                 isl_val_free(v2);
 705                 return isl_val_set_nan(v1);
 706         }
 707         if (isl_val_is_zero(v1)) {
 708                 isl_val_free(v2);
 709                 return v1;
 710         }
 711         if (isl_val_is_zero(v2)) {
 712                 isl_val_free(v1);
 713                 return v2;
 714         }
 715         if (isl_val_is_infty(v1) || isl_val_is_neginfty(v1)) {
 716                 if (isl_val_is_neg(v2))
 717                         v1 = isl_val_neg(v1);
 718                 isl_val_free(v2);
 719                 return v1;
 720         }
 721         if (isl_val_is_infty(v2) || isl_val_is_neginfty(v2)) {
 722                 if (isl_val_is_neg(v1))
 723                         v2 = isl_val_neg(v2);
 724                 isl_val_free(v1);
 725                 return v2;
 726         }
 727
 728         v1 = isl_val_cow(v1);
 729         if (!v1)
 730                 goto error;
 731         if (isl_val_is_int(v1) && isl_val_is_int(v2))
 732                 isl_int_mul(v1->n, v1->n, v2->n);
 733         else {
 734                 isl_int_mul(v1->n, v1->n, v2->n);
 735                 isl_int_mul(v1->d, v1->d, v2->d);
 736                 v1 = isl_val_normalize(v1);
 737         }
 738         isl_val_free(v2);
 739         return v1;
 740 error:
 741         isl_val_free(v1);
 742         isl_val_free(v2);
 743         return NULL;
 744 }
 745
 746 /* Return the product of "v1" and "v2".
 747  */
 748 __isl_give isl_val *isl_val_mul_ui(__isl_take isl_val *v1, unsigned long v2)
 749 {
 750         if (!v1)
 751                 return NULL;
 752         if (isl_val_is_nan(v1))
 753                 return v1;
 754         if (!isl_val_is_rat(v1)) {
 755                 if (v2 == 0)
 756                         v1 = isl_val_set_nan(v1);
 757                 return v1;
 758         }
 759         if (v2 == 1)
 760                 return v1;
 761         v1 = isl_val_cow(v1);
 762         if (!v1)
 763                 return NULL;
 764
 765         isl_int_mul_ui(v1->n, v1->n, v2);
 766
 767         return isl_val_normalize(v1);
 768 }
 769
 770 /* Divide "v1" by "v2".
 771  */
 772 __isl_give isl_val *isl_val_div(__isl_take isl_val *v1, __isl_take isl_val *v2)
 773 {
 774         if (!v1 || !v2)
 775                 goto error;
 776         if (isl_val_is_nan(v1)) {
 777                 isl_val_free(v2);
 778                 return v1;
 779         }
 780         if (isl_val_is_nan(v2)) {
 781                 isl_val_free(v1);
 782                 return v2;
 783         }
 784         if (isl_val_is_zero(v2) ||
 785             (!isl_val_is_rat(v1) && !isl_val_is_rat(v2))) {
 786                 isl_val_free(v2);
 787                 return isl_val_set_nan(v1);
 788         }
 789         if (isl_val_is_zero(v1)) {
 790                 isl_val_free(v2);
 791                 return v1;
 792         }
 793         if (isl_val_is_infty(v1) || isl_val_is_neginfty(v1)) {
 794                 if (isl_val_is_neg(v2))
 795                         v1 = isl_val_neg(v1);
 796                 isl_val_free(v2);
 797                 return v1;
 798         }
 799         if (isl_val_is_infty(v2) || isl_val_is_neginfty(v2)) {
 800                 isl_val_free(v2);
 801                 return isl_val_set_zero(v1);
 802         }
 803
 804         v1 = isl_val_cow(v1);
 805         if (!v1)
 806                 goto error;
 807         if (isl_val_is_int(v2)) {
 808                 isl_int_mul(v1->d, v1->d, v2->n);
 809                 v1 = isl_val_normalize(v1);
 810         } else {
 811                 isl_int_mul(v1->d, v1->d, v2->n);
 812                 isl_int_mul(v1->n, v1->n, v2->d);
 813                 v1 = isl_val_normalize(v1);
 814         }
 815         isl_val_free(v2);
 816         return v1;
 817 error:
 818         isl_val_free(v1);
 819         isl_val_free(v2);
 820         return NULL;
 821 }
 822
 823 /* Given two integer values "v1" and "v2", check if "v1" is divisible by "v2".
 824  */
 825 int isl_val_is_divisible_by(__isl_keep isl_val *v1, __isl_keep isl_val *v2)
 826 {
 827         if (!v1 || !v2)
 828                 return -1;
 829
 830         if (!isl_val_is_int(v1) || !isl_val_is_int(v2))
 831                 isl_die(isl_val_get_ctx(v1), isl_error_invalid,
 832                         "expecting two integers", return -1);
 833
 834         return isl_int_is_divisible_by(v1->n, v2->n);
 835 }
 836
 837 /* Given two integer values "v1" and "v2", return the residue of "v1"
 838  * modulo "v2".
 839  */
 840 __isl_give isl_val *isl_val_mod(__isl_take isl_val *v1, __isl_take isl_val *v2)
 841 {
 842         if (!v1 || !v2)
 843                 goto error;
 844         if (!isl_val_is_int(v1) || !isl_val_is_int(v2))
 845                 isl_die(isl_val_get_ctx(v1), isl_error_invalid,
 846                         "expecting two integers", goto error);
 847         if (isl_val_is_nonneg(v1) && isl_val_lt(v1, v2)) {
 848                 isl_val_free(v2);
 849                 return v1;
 850         }
 851         v1 = isl_val_cow(v1);
 852         if (!v1)
 853                 goto error;
 854         isl_int_fdiv_r(v1->n, v1->n, v2->n);
 855         isl_val_free(v2);
 856         return v1;
 857 error:
 858         isl_val_free(v1);
 859         isl_val_free(v2);
 860         return NULL;
 861 }
 862
 863 /* Given two integer values, return their greatest common divisor.
 864  */
 865 __isl_give isl_val *isl_val_gcd(__isl_take isl_val *v1, __isl_take isl_val *v2)
 866 {
 867         if (!v1 || !v2)
 868                 goto error;
 869         if (!isl_val_is_int(v1) || !isl_val_is_int(v2))
 870                 isl_die(isl_val_get_ctx(v1), isl_error_invalid,
 871                         "expecting two integers", goto error);
 872         if (isl_val_eq(v1, v2)) {
 873                 isl_val_free(v2);
 874                 return v1;
 875         }
 876         if (isl_val_is_one(v1)) {
 877                 isl_val_free(v2);
 878                 return v1;
 879         }
 880         if (isl_val_is_one(v2)) {
 881                 isl_val_free(v1);
 882                 return v2;
 883         }
 884         v1 = isl_val_cow(v1);
 885         if (!v1)
 886                 goto error;
 887         isl_int_gcd(v1->n, v1->n, v2->n);
 888         isl_val_free(v2);
 889         return v1;
 890 error:
 891         isl_val_free(v1);
 892         isl_val_free(v2);
 893         return NULL;
 894 }
 895
 896 /* Given two integer values v1 and v2, return their greatest common divisor g,
 897  * as well as two integers x and y such that x * v1 + y * v2 = g.
 898  */
 899 __isl_give isl_val *isl_val_gcdext(__isl_take isl_val *v1,
 900         __isl_take isl_val *v2, __isl_give isl_val **x, __isl_give isl_val **y)
 901 {
 902         isl_ctx *ctx;
 903         isl_val *a = NULL, *b = NULL;
 904
 905         if (!x && !y)
 906                 return isl_val_gcd(v1, v2);
 907
 908         if (!v1 || !v2)
 909                 goto error;
 910
 911         ctx = isl_val_get_ctx(v1);
 912         if (!isl_val_is_int(v1) || !isl_val_is_int(v2))
 913                 isl_die(ctx, isl_error_invalid,
 914                         "expecting two integers", goto error);
 915
 916         v1 = isl_val_cow(v1);
 917         a = isl_val_alloc(ctx);
 918         b = isl_val_alloc(ctx);
 919         if (!v1 || !a || !b)
 920                 goto error;
 921         isl_int_gcdext(v1->n, a->n, b->n, v1->n, v2->n);
 922         if (x) {
 923                 isl_int_set_si(a->d, 1);
 924                 *x = a;
 925         } else
 926                 isl_val_free(a);
 927         if (y) {
 928                 isl_int_set_si(b->d, 1);
 929                 *y = b;
 930         } else
 931                 isl_val_free(b);
 932         isl_val_free(v2);
 933         return v1;
 934 error:
 935         isl_val_free(v1);
 936         isl_val_free(v2);
 937         isl_val_free(a);
 938         isl_val_free(b);
 939         if (x)
 940                 *x = NULL;
 941         if (y)
 942                 *y = NULL;
 943         return NULL;
 944 }
 945
 946 /* Does "v" represent an integer value?
 947  */
 948 int isl_val_is_int(__isl_keep isl_val *v)
 949 {
 950         if (!v)
 951                 return -1;
 952
 953         return isl_int_is_one(v->d);
 954 }
 955
 956 /* Does "v" represent a rational value?
 957  */
 958 int isl_val_is_rat(__isl_keep isl_val *v)
 959 {
 960         if (!v)
 961                 return -1;
 962
 963         return !isl_int_is_zero(v->d);
 964 }
 965
 966 /* Does "v" represent NaN?
 967  */
 968 int isl_val_is_nan(__isl_keep isl_val *v)
 969 {
 970         if (!v)
 971                 return -1;
 972
 973         return isl_int_is_zero(v->n) && isl_int_is_zero(v->d);
 974 }
 975
 976 /* Does "v" represent +infinity?
 977  */
 978 int isl_val_is_infty(__isl_keep isl_val *v)
 979 {
 980         if (!v)
 981                 return -1;
 982
 983         return isl_int_is_pos(v->n) && isl_int_is_zero(v->d);
 984 }
 985
 986 /* Does "v" represent -infinity?
 987  */
 988 int isl_val_is_neginfty(__isl_keep isl_val *v)
 989 {
 990         if (!v)
 991                 return -1;
 992
 993         return isl_int_is_neg(v->n) && isl_int_is_zero(v->d);
 994 }
 995
 996 /* Does "v" represent the integer zero?
 997  */
 998 int isl_val_is_zero(__isl_keep isl_val *v)
 999 {
1000         if (!v)
1001                 return -1;
1002
1003         return isl_int_is_zero(v->n) && !isl_int_is_zero(v->d);
1004 }
1005
1006 /* Does "v" represent the integer one?
1007  */
1008 int isl_val_is_one(__isl_keep isl_val *v)
1009 {
1010         if (!v)
1011                 return -1;
1012
1013         return isl_int_eq(v->n, v->d);
1014 }
1015
1016 /* Does "v" represent the integer negative one?
1017  */
1018 int isl_val_is_negone(__isl_keep isl_val *v)
1019 {
1020         if (!v)
1021                 return -1;
1022
1023         return isl_int_is_neg(v->n) && isl_int_abs_eq(v->n, v->d);
1024 }
1025
1026 /* Is "v" (strictly) positive?
1027  */
1028 int isl_val_is_pos(__isl_keep isl_val *v)
1029 {
1030         if (!v)
1031                 return -1;
1032
1033         return isl_int_is_pos(v->n);
1034 }
1035
1036 /* Is "v" (strictly) negative?
1037  */
1038 int isl_val_is_neg(__isl_keep isl_val *v)
1039 {
1040         if (!v)
1041                 return -1;
1042
1043         return isl_int_is_neg(v->n);
1044 }
1045
1046 /* Is "v" non-negative?
1047  */
1048 int isl_val_is_nonneg(__isl_keep isl_val *v)
1049 {
1050         if (!v)
1051                 return -1;
1052
1053         if (isl_val_is_nan(v))
1054                 return 0;
1055
1056         return isl_int_is_nonneg(v->n);
1057 }
1058
1059 /* Is "v" non-positive?
1060  */
1061 int isl_val_is_nonpos(__isl_keep isl_val *v)
1062 {
1063         if (!v)
1064                 return -1;
1065
1066         if (isl_val_is_nan(v))
1067                 return 0;
1068
1069         return isl_int_is_nonpos(v->n);
1070 }
1071
1072 /* Return the sign of "v".
1073  *
1074  * The sign of NaN is undefined.
1075  */
1076 int isl_val_sgn(__isl_keep isl_val *v)
1077 {
1078         if (!v)
1079                 return 0;
1080         if (isl_val_is_zero(v))
1081                 return 0;
1082         if (isl_val_is_pos(v))
1083                 return 1;
1084         return -1;
1085 }
1086
1087 /* Is "v1" (strictly) less than "v2"?
1088  */
1089 int isl_val_lt(__isl_keep isl_val *v1, __isl_keep isl_val *v2)
1090 {
1091         isl_int t;
1092         int lt;
1093
1094         if (!v1 || !v2)
1095                 return -1;
1096         if (isl_val_is_int(v1) && isl_val_is_int(v2))
1097                 return isl_int_lt(v1->n, v2->n);
1098         if (isl_val_is_nan(v1) || isl_val_is_nan(v2))
1099                 return 0;
1100         if (isl_val_eq(v1, v2))
1101                 return 0;
1102         if (isl_val_is_infty(v2))
1103                 return 1;
1104         if (isl_val_is_infty(v1))
1105                 return 0;
1106         if (isl_val_is_neginfty(v1))
1107                 return 1;
1108         if (isl_val_is_neginfty(v2))
1109                 return 0;
1110
1111         isl_int_init(t);
1112         isl_int_mul(t, v1->n, v2->d);
1113         isl_int_submul(t, v2->n, v1->d);
1114         lt = isl_int_is_neg(t);
1115         isl_int_clear(t);
1116
1117         return lt;
1118 }
1119
1120 /* Is "v1" (strictly) greater than "v2"?
1121  */
1122 int isl_val_gt(__isl_keep isl_val *v1, __isl_keep isl_val *v2)
1123 {
1124         return isl_val_lt(v2, v1);
1125 }
1126
1127 /* Is "v1" less than or equal to "v2"?
1128  */
1129 int isl_val_le(__isl_keep isl_val *v1, __isl_keep isl_val *v2)
1130 {
1131         isl_int t;
1132         int le;
1133
1134         if (!v1 || !v2)
1135                 return -1;
1136         if (isl_val_is_int(v1) && isl_val_is_int(v2))
1137                 return isl_int_le(v1->n, v2->n);
1138         if (isl_val_is_nan(v1) || isl_val_is_nan(v2))
1139                 return 0;
1140         if (isl_val_eq(v1, v2))
1141                 return 1;
1142         if (isl_val_is_infty(v2))
1143                 return 1;
1144         if (isl_val_is_infty(v1))
1145                 return 0;
1146         if (isl_val_is_neginfty(v1))
1147                 return 1;
1148         if (isl_val_is_neginfty(v2))
1149                 return 0;
1150
1151         isl_int_init(t);
1152         isl_int_mul(t, v1->n, v2->d);
1153         isl_int_submul(t, v2->n, v1->d);
1154         le = isl_int_is_nonpos(t);
1155         isl_int_clear(t);
1156
1157         return le;
1158 }
1159
1160 /* Is "v1" greater than or equal to "v2"?
1161  */
1162 int isl_val_ge(__isl_keep isl_val *v1, __isl_keep isl_val *v2)
1163 {
1164         return isl_val_le(v2, v1);
1165 }
1166
1167 /* How does "v" compare to "i"?
1168  *
1169  * Return 1 if v is greater, -1 if v is smaller and 0 if v is equal to i.
1170  *
1171  * If v is NaN (or NULL), then the result is undefined.
1172  */
1173 int isl_val_cmp_si(__isl_keep isl_val *v, long i)
1174 {
1175         isl_int t;
1176         int cmp;
1177
1178         if (!v)
1179                 return 0;
1180         if (isl_val_is_int(v))
1181                 return isl_int_cmp_si(v->n, i);
1182         if (isl_val_is_nan(v))
1183                 return 0;
1184         if (isl_val_is_infty(v))
1185                 return 1;
1186         if (isl_val_is_neginfty(v))
1187                 return -1;
1188
1189         isl_int_init(t);
1190         isl_int_mul_si(t, v->d, i);
1191         isl_int_sub(t, v->n, t);
1192         cmp = isl_int_sgn(t);
1193         isl_int_clear(t);
1194
1195         return cmp;
1196 }
1197
1198 /* Is "v1" equal to "v2"?
1199  */
1200 int isl_val_eq(__isl_keep isl_val *v1, __isl_keep isl_val *v2)
1201 {
1202         if (!v1 || !v2)
1203                 return -1;
1204         if (isl_val_is_nan(v1) || isl_val_is_nan(v2))
1205                 return 0;
1206
1207         return isl_int_eq(v1->n, v2->n) && isl_int_eq(v1->d, v2->d);
1208 }
1209
1210 /* Is "v1" different from "v2"?
1211  */
1212 int isl_val_ne(__isl_keep isl_val *v1, __isl_keep isl_val *v2)
1213 {
1214         if (!v1 || !v2)
1215                 return -1;
1216         if (isl_val_is_nan(v1) || isl_val_is_nan(v2))
1217                 return 0;
1218
1219         return isl_int_ne(v1->n, v2->n) || isl_int_ne(v1->d, v2->d);
1220 }
1221
1222 /* Print a textual representation of "v" onto "p".
1223  */
1224 __isl_give isl_printer *isl_printer_print_val(__isl_take isl_printer *p,
1225         __isl_keep isl_val *v)
1226 {
1227         int neg;
1228
1229         if (!p || !v)
1230                 return isl_printer_free(p);
1231
1232         neg = isl_int_is_neg(v->n);
1233         if (neg) {
1234                 p = isl_printer_print_str(p, "-");
1235                 isl_int_neg(v->n, v->n);
1236         }
1237         if (isl_int_is_zero(v->d)) {
1238                 int sgn = isl_int_sgn(v->n);
1239                 p = isl_printer_print_str(p, sgn < 0 ? "-infty" :
1240                                             sgn == 0 ? "NaN" : "infty");
1241         } else
1242                 p = isl_printer_print_isl_int(p, v->n);
1243         if (neg)
1244                 isl_int_neg(v->n, v->n);
1245         if (!isl_int_is_zero(v->d) && !isl_int_is_one(v->d)) {
1246                 p = isl_printer_print_str(p, "/");
1247                 p = isl_printer_print_isl_int(p, v->d);
1248         }
1249
1250         return p;
1251 }