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