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