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  * This is a private copy of isl_val_mul for use in the generic
 754  * isl_multi_*_scale_val instantiated for isl_val.
 755  */
 756 __isl_give isl_val *isl_val_scale_val(__isl_take isl_val *v1,
 757         __isl_take isl_val *v2)
 758 {
 759         return isl_val_mul(v1, v2);
 760 }
 761
 762 /* Return the product of "v1" and "v2".
 763  */
 764 __isl_give isl_val *isl_val_mul_ui(__isl_take isl_val *v1, unsigned long v2)
 765 {
 766         if (!v1)
 767                 return NULL;
 768         if (isl_val_is_nan(v1))
 769                 return v1;
 770         if (!isl_val_is_rat(v1)) {
 771                 if (v2 == 0)
 772                         v1 = isl_val_set_nan(v1);
 773                 return v1;
 774         }
 775         if (v2 == 1)
 776                 return v1;
 777         v1 = isl_val_cow(v1);
 778         if (!v1)
 779                 return NULL;
 780
 781         isl_int_mul_ui(v1->n, v1->n, v2);
 782
 783         return isl_val_normalize(v1);
 784 }
 785
 786 /* Divide "v1" by "v2".
 787  */
 788 __isl_give isl_val *isl_val_div(__isl_take isl_val *v1, __isl_take isl_val *v2)
 789 {
 790         if (!v1 || !v2)
 791                 goto error;
 792         if (isl_val_is_nan(v1)) {
 793                 isl_val_free(v2);
 794                 return v1;
 795         }
 796         if (isl_val_is_nan(v2)) {
 797                 isl_val_free(v1);
 798                 return v2;
 799         }
 800         if (isl_val_is_zero(v2) ||
 801             (!isl_val_is_rat(v1) && !isl_val_is_rat(v2))) {
 802                 isl_val_free(v2);
 803                 return isl_val_set_nan(v1);
 804         }
 805         if (isl_val_is_zero(v1)) {
 806                 isl_val_free(v2);
 807                 return v1;
 808         }
 809         if (isl_val_is_infty(v1) || isl_val_is_neginfty(v1)) {
 810                 if (isl_val_is_neg(v2))
 811                         v1 = isl_val_neg(v1);
 812                 isl_val_free(v2);
 813                 return v1;
 814         }
 815         if (isl_val_is_infty(v2) || isl_val_is_neginfty(v2)) {
 816                 isl_val_free(v2);
 817                 return isl_val_set_zero(v1);
 818         }
 819
 820         v1 = isl_val_cow(v1);
 821         if (!v1)
 822                 goto error;
 823         if (isl_val_is_int(v2)) {
 824                 isl_int_mul(v1->d, v1->d, v2->n);
 825                 v1 = isl_val_normalize(v1);
 826         } else {
 827                 isl_int_mul(v1->d, v1->d, v2->n);
 828                 isl_int_mul(v1->n, v1->n, v2->d);
 829                 v1 = isl_val_normalize(v1);
 830         }
 831         isl_val_free(v2);
 832         return v1;
 833 error:
 834         isl_val_free(v1);
 835         isl_val_free(v2);
 836         return NULL;
 837 }
 838
 839 /* Given two integer values "v1" and "v2", check if "v1" is divisible by "v2".
 840  */
 841 int isl_val_is_divisible_by(__isl_keep isl_val *v1, __isl_keep isl_val *v2)
 842 {
 843         if (!v1 || !v2)
 844                 return -1;
 845
 846         if (!isl_val_is_int(v1) || !isl_val_is_int(v2))
 847                 isl_die(isl_val_get_ctx(v1), isl_error_invalid,
 848                         "expecting two integers", return -1);
 849
 850         return isl_int_is_divisible_by(v1->n, v2->n);
 851 }
 852
 853 /* Given two integer values "v1" and "v2", return the residue of "v1"
 854  * modulo "v2".
 855  */
 856 __isl_give isl_val *isl_val_mod(__isl_take isl_val *v1, __isl_take isl_val *v2)
 857 {
 858         if (!v1 || !v2)
 859                 goto error;
 860         if (!isl_val_is_int(v1) || !isl_val_is_int(v2))
 861                 isl_die(isl_val_get_ctx(v1), isl_error_invalid,
 862                         "expecting two integers", goto error);
 863         if (isl_val_is_nonneg(v1) && isl_val_lt(v1, v2)) {
 864                 isl_val_free(v2);
 865                 return v1;
 866         }
 867         v1 = isl_val_cow(v1);
 868         if (!v1)
 869                 goto error;
 870         isl_int_fdiv_r(v1->n, v1->n, v2->n);
 871         isl_val_free(v2);
 872         return v1;
 873 error:
 874         isl_val_free(v1);
 875         isl_val_free(v2);
 876         return NULL;
 877 }
 878
 879 /* Given two integer values, return their greatest common divisor.
 880  */
 881 __isl_give isl_val *isl_val_gcd(__isl_take isl_val *v1, __isl_take isl_val *v2)
 882 {
 883         if (!v1 || !v2)
 884                 goto error;
 885         if (!isl_val_is_int(v1) || !isl_val_is_int(v2))
 886                 isl_die(isl_val_get_ctx(v1), isl_error_invalid,
 887                         "expecting two integers", goto error);
 888         if (isl_val_eq(v1, v2)) {
 889                 isl_val_free(v2);
 890                 return v1;
 891         }
 892         if (isl_val_is_one(v1)) {
 893                 isl_val_free(v2);
 894                 return v1;
 895         }
 896         if (isl_val_is_one(v2)) {
 897                 isl_val_free(v1);
 898                 return v2;
 899         }
 900         v1 = isl_val_cow(v1);
 901         if (!v1)
 902                 goto error;
 903         isl_int_gcd(v1->n, v1->n, v2->n);
 904         isl_val_free(v2);
 905         return v1;
 906 error:
 907         isl_val_free(v1);
 908         isl_val_free(v2);
 909         return NULL;
 910 }
 911
 912 /* Given two integer values v1 and v2, return their greatest common divisor g,
 913  * as well as two integers x and y such that x * v1 + y * v2 = g.
 914  */
 915 __isl_give isl_val *isl_val_gcdext(__isl_take isl_val *v1,
 916         __isl_take isl_val *v2, __isl_give isl_val **x, __isl_give isl_val **y)
 917 {
 918         isl_ctx *ctx;
 919         isl_val *a = NULL, *b = NULL;
 920
 921         if (!x && !y)
 922                 return isl_val_gcd(v1, v2);
 923
 924         if (!v1 || !v2)
 925                 goto error;
 926
 927         ctx = isl_val_get_ctx(v1);
 928         if (!isl_val_is_int(v1) || !isl_val_is_int(v2))
 929                 isl_die(ctx, isl_error_invalid,
 930                         "expecting two integers", goto error);
 931
 932         v1 = isl_val_cow(v1);
 933         a = isl_val_alloc(ctx);
 934         b = isl_val_alloc(ctx);
 935         if (!v1 || !a || !b)
 936                 goto error;
 937         isl_int_gcdext(v1->n, a->n, b->n, v1->n, v2->n);
 938         if (x) {
 939                 isl_int_set_si(a->d, 1);
 940                 *x = a;
 941         } else
 942                 isl_val_free(a);
 943         if (y) {
 944                 isl_int_set_si(b->d, 1);
 945                 *y = b;
 946         } else
 947                 isl_val_free(b);
 948         isl_val_free(v2);
 949         return v1;
 950 error:
 951         isl_val_free(v1);
 952         isl_val_free(v2);
 953         isl_val_free(a);
 954         isl_val_free(b);
 955         if (x)
 956                 *x = NULL;
 957         if (y)
 958                 *y = NULL;
 959         return NULL;
 960 }
 961
 962 /* Does "v" represent an integer value?
 963  */
 964 int isl_val_is_int(__isl_keep isl_val *v)
 965 {
 966         if (!v)
 967                 return -1;
 968
 969         return isl_int_is_one(v->d);
 970 }
 971
 972 /* Does "v" represent a rational value?
 973  */
 974 int isl_val_is_rat(__isl_keep isl_val *v)
 975 {
 976         if (!v)
 977                 return -1;
 978
 979         return !isl_int_is_zero(v->d);
 980 }
 981
 982 /* Does "v" represent NaN?
 983  */
 984 int isl_val_is_nan(__isl_keep isl_val *v)
 985 {
 986         if (!v)
 987                 return -1;
 988
 989         return isl_int_is_zero(v->n) && isl_int_is_zero(v->d);
 990 }
 991
 992 /* Does "v" represent +infinity?
 993  */
 994 int isl_val_is_infty(__isl_keep isl_val *v)
 995 {
 996         if (!v)
 997                 return -1;
 998
 999         return isl_int_is_pos(v->n) && isl_int_is_zero(v->d);
1000 }
1001
1002 /* Does "v" represent -infinity?
1003  */
1004 int isl_val_is_neginfty(__isl_keep isl_val *v)
1005 {
1006         if (!v)
1007                 return -1;
1008
1009         return isl_int_is_neg(v->n) && isl_int_is_zero(v->d);
1010 }
1011
1012 /* Does "v" represent the integer zero?
1013  */
1014 int isl_val_is_zero(__isl_keep isl_val *v)
1015 {
1016         if (!v)
1017                 return -1;
1018
1019         return isl_int_is_zero(v->n) && !isl_int_is_zero(v->d);
1020 }
1021
1022 /* Does "v" represent the integer one?
1023  */
1024 int isl_val_is_one(__isl_keep isl_val *v)
1025 {
1026         if (!v)
1027                 return -1;
1028
1029         return isl_int_eq(v->n, v->d);
1030 }
1031
1032 /* Does "v" represent the integer negative one?
1033  */
1034 int isl_val_is_negone(__isl_keep isl_val *v)
1035 {
1036         if (!v)
1037                 return -1;
1038
1039         return isl_int_is_neg(v->n) && isl_int_abs_eq(v->n, v->d);
1040 }
1041
1042 /* Is "v" (strictly) positive?
1043  */
1044 int isl_val_is_pos(__isl_keep isl_val *v)
1045 {
1046         if (!v)
1047                 return -1;
1048
1049         return isl_int_is_pos(v->n);
1050 }
1051
1052 /* Is "v" (strictly) negative?
1053  */
1054 int isl_val_is_neg(__isl_keep isl_val *v)
1055 {
1056         if (!v)
1057                 return -1;
1058
1059         return isl_int_is_neg(v->n);
1060 }
1061
1062 /* Is "v" non-negative?
1063  */
1064 int isl_val_is_nonneg(__isl_keep isl_val *v)
1065 {
1066         if (!v)
1067                 return -1;
1068
1069         if (isl_val_is_nan(v))
1070                 return 0;
1071
1072         return isl_int_is_nonneg(v->n);
1073 }
1074
1075 /* Is "v" non-positive?
1076  */
1077 int isl_val_is_nonpos(__isl_keep isl_val *v)
1078 {
1079         if (!v)
1080                 return -1;
1081
1082         if (isl_val_is_nan(v))
1083                 return 0;
1084
1085         return isl_int_is_nonpos(v->n);
1086 }
1087
1088 /* Return the sign of "v".
1089  *
1090  * The sign of NaN is undefined.
1091  */
1092 int isl_val_sgn(__isl_keep isl_val *v)
1093 {
1094         if (!v)
1095                 return 0;
1096         if (isl_val_is_zero(v))
1097                 return 0;
1098         if (isl_val_is_pos(v))
1099                 return 1;
1100         return -1;
1101 }
1102
1103 /* Is "v1" (strictly) less than "v2"?
1104  */
1105 int isl_val_lt(__isl_keep isl_val *v1, __isl_keep isl_val *v2)
1106 {
1107         isl_int t;
1108         int lt;
1109
1110         if (!v1 || !v2)
1111                 return -1;
1112         if (isl_val_is_int(v1) && isl_val_is_int(v2))
1113                 return isl_int_lt(v1->n, v2->n);
1114         if (isl_val_is_nan(v1) || isl_val_is_nan(v2))
1115                 return 0;
1116         if (isl_val_eq(v1, v2))
1117                 return 0;
1118         if (isl_val_is_infty(v2))
1119                 return 1;
1120         if (isl_val_is_infty(v1))
1121                 return 0;
1122         if (isl_val_is_neginfty(v1))
1123                 return 1;
1124         if (isl_val_is_neginfty(v2))
1125                 return 0;
1126
1127         isl_int_init(t);
1128         isl_int_mul(t, v1->n, v2->d);
1129         isl_int_submul(t, v2->n, v1->d);
1130         lt = isl_int_is_neg(t);
1131         isl_int_clear(t);
1132
1133         return lt;
1134 }
1135
1136 /* Is "v1" (strictly) greater than "v2"?
1137  */
1138 int isl_val_gt(__isl_keep isl_val *v1, __isl_keep isl_val *v2)
1139 {
1140         return isl_val_lt(v2, v1);
1141 }
1142
1143 /* Is "v1" less than or equal to "v2"?
1144  */
1145 int isl_val_le(__isl_keep isl_val *v1, __isl_keep isl_val *v2)
1146 {
1147         isl_int t;
1148         int le;
1149
1150         if (!v1 || !v2)
1151                 return -1;
1152         if (isl_val_is_int(v1) && isl_val_is_int(v2))
1153                 return isl_int_le(v1->n, v2->n);
1154         if (isl_val_is_nan(v1) || isl_val_is_nan(v2))
1155                 return 0;
1156         if (isl_val_eq(v1, v2))
1157                 return 1;
1158         if (isl_val_is_infty(v2))
1159                 return 1;
1160         if (isl_val_is_infty(v1))
1161                 return 0;
1162         if (isl_val_is_neginfty(v1))
1163                 return 1;
1164         if (isl_val_is_neginfty(v2))
1165                 return 0;
1166
1167         isl_int_init(t);
1168         isl_int_mul(t, v1->n, v2->d);
1169         isl_int_submul(t, v2->n, v1->d);
1170         le = isl_int_is_nonpos(t);
1171         isl_int_clear(t);
1172
1173         return le;
1174 }
1175
1176 /* Is "v1" greater than or equal to "v2"?
1177  */
1178 int isl_val_ge(__isl_keep isl_val *v1, __isl_keep isl_val *v2)
1179 {
1180         return isl_val_le(v2, v1);
1181 }
1182
1183 /* How does "v" compare to "i"?
1184  *
1185  * Return 1 if v is greater, -1 if v is smaller and 0 if v is equal to i.
1186  *
1187  * If v is NaN (or NULL), then the result is undefined.
1188  */
1189 int isl_val_cmp_si(__isl_keep isl_val *v, long i)
1190 {
1191         isl_int t;
1192         int cmp;
1193
1194         if (!v)
1195                 return 0;
1196         if (isl_val_is_int(v))
1197                 return isl_int_cmp_si(v->n, i);
1198         if (isl_val_is_nan(v))
1199                 return 0;
1200         if (isl_val_is_infty(v))
1201                 return 1;
1202         if (isl_val_is_neginfty(v))
1203                 return -1;
1204
1205         isl_int_init(t);
1206         isl_int_mul_si(t, v->d, i);
1207         isl_int_sub(t, v->n, t);
1208         cmp = isl_int_sgn(t);
1209         isl_int_clear(t);
1210
1211         return cmp;
1212 }
1213
1214 /* Is "v1" equal to "v2"?
1215  */
1216 int isl_val_eq(__isl_keep isl_val *v1, __isl_keep isl_val *v2)
1217 {
1218         if (!v1 || !v2)
1219                 return -1;
1220         if (isl_val_is_nan(v1) || isl_val_is_nan(v2))
1221                 return 0;
1222
1223         return isl_int_eq(v1->n, v2->n) && isl_int_eq(v1->d, v2->d);
1224 }
1225
1226 /* Is "v1" different from "v2"?
1227  */
1228 int isl_val_ne(__isl_keep isl_val *v1, __isl_keep isl_val *v2)
1229 {
1230         if (!v1 || !v2)
1231                 return -1;
1232         if (isl_val_is_nan(v1) || isl_val_is_nan(v2))
1233                 return 0;
1234
1235         return isl_int_ne(v1->n, v2->n) || isl_int_ne(v1->d, v2->d);
1236 }
1237
1238 /* Print a textual representation of "v" onto "p".
1239  */
1240 __isl_give isl_printer *isl_printer_print_val(__isl_take isl_printer *p,
1241         __isl_keep isl_val *v)
1242 {
1243         int neg;
1244
1245         if (!p || !v)
1246                 return isl_printer_free(p);
1247
1248         neg = isl_int_is_neg(v->n);
1249         if (neg) {
1250                 p = isl_printer_print_str(p, "-");
1251                 isl_int_neg(v->n, v->n);
1252         }
1253         if (isl_int_is_zero(v->d)) {
1254                 int sgn = isl_int_sgn(v->n);
1255                 p = isl_printer_print_str(p, sgn < 0 ? "-infty" :
1256                                             sgn == 0 ? "NaN" : "infty");
1257         } else
1258                 p = isl_printer_print_isl_int(p, v->n);
1259         if (neg)
1260                 isl_int_neg(v->n, v->n);
1261         if (!isl_int_is_zero(v->d) && !isl_int_is_one(v->d)) {
1262                 p = isl_printer_print_str(p, "/");
1263                 p = isl_printer_print_isl_int(p, v->d);
1264         }
1265
1266         return p;
1267 }
1268
1269 /* Insert "n" dimensions of type "type" at position "first".
1270  *
1271  * This function is only meant to be used in the generic isl_multi_*
1272  * functions which have to deal with base objects that have an associated
1273  * space.  Since an isl_val does not have an associated space, this function
1274  * does not do anything.
1275  */
1276 __isl_give isl_val *isl_val_insert_dims(__isl_take isl_val *v,
1277         enum isl_dim_type type, unsigned first, unsigned n)
1278 {
1279         return v;
1280 }
1281
1282 /* Drop the the "n" first dimensions of type "type" at position "first".
1283  *
1284  * This function is only meant to be used in the generic isl_multi_*
1285  * functions which have to deal with base objects that have an associated
1286  * space.  Since an isl_val does not have an associated space, this function
1287  * does not do anything.
1288  */
1289 __isl_give isl_val *isl_val_drop_dims(__isl_take isl_val *v,
1290         enum isl_dim_type type, unsigned first, unsigned n)
1291 {
1292         return v;
1293 }
1294
1295 /* Change the name of the dimension of type "type" at position "pos" to "s".
1296  *
1297  * This function is only meant to be used in the generic isl_multi_*
1298  * functions which have to deal with base objects that have an associated
1299  * space.  Since an isl_val does not have an associated space, this function
1300  * does not do anything.
1301  */
1302 __isl_give isl_val *isl_val_set_dim_name(__isl_take isl_val *v,
1303         enum isl_dim_type type, unsigned pos, const char *s)
1304 {
1305         return v;
1306 }
1307
1308 /* Reset the domain space of "v" to "space".
1309  *
1310  * This function is only meant to be used in the generic isl_multi_*
1311  * functions which have to deal with base objects that have an associated
1312  * space.  Since an isl_val does not have an associated space, this function
1313  * does not do anything, apart from error handling and cleaning up memory.
1314  */
1315 __isl_give isl_val *isl_val_reset_domain_space(__isl_take isl_val *v,
1316         __isl_take isl_space *space)
1317 {
1318         if (!space)
1319                 return isl_val_free(v);
1320         isl_space_free(space);
1321         return v;
1322 }
1323
1324 /* Reorder the dimensions of the domain of "v" according
1325  * to the given reordering.
1326  *
1327  * This function is only meant to be used in the generic isl_multi_*
1328  * functions which have to deal with base objects that have an associated
1329  * space.  Since an isl_val does not have an associated space, this function
1330  * does not do anything, apart from error handling and cleaning up memory.
1331  */
1332 __isl_give isl_val *isl_val_realign_domain(__isl_take isl_val *v,
1333         __isl_take isl_reordering *r)
1334 {
1335         if (!r)
1336                 return isl_val_free(v);
1337         isl_reordering_free(r);
1338         return v;
1339 }
1340
1341 /* Return an isl_val that is zero on "ls".
1342  *
1343  * This function is only meant to be used in the generic isl_multi_*
1344  * functions which have to deal with base objects that have an associated
1345  * space.  Since an isl_val does not have an associated space, this function
1346  * simply returns a zero isl_val in the same context as "ls".
1347  */
1348 __isl_give isl_val *isl_val_zero_on_domain(__isl_take isl_local_space *ls)
1349 {
1350         isl_ctx *ctx;
1351
1352         if (!ls)
1353                 return NULL;
1354         ctx = isl_local_space_get_ctx(ls);
1355         isl_local_space_free(ls);
1356         return isl_val_zero(ctx);
1357 }
1358
1359 /* Check that the domain space of "v" matches "space".
1360  *
1361  * Return 0 on success and -1 on error.
1362  *
1363  * This function is only meant to be used in the generic isl_multi_*
1364  * functions which have to deal with base objects that have an associated
1365  * space.  Since an isl_val does not have an associated space, this function
1366  * simply returns 0, except if "v" or "space" are NULL.
1367  */
1368 int isl_val_check_match_domain_space(__isl_keep isl_val *v,
1369         __isl_keep isl_space *space)
1370 {
1371         if (!v || !space)
1372                 return -1;
1373         return 0;
1374 }
1375
1376 #undef BASE
1377 #define BASE val
1378
1379 #define NO_GIST
1380 #define NO_IDENTITY
1381 #define NO_FROM_BASE
1382 #include <isl_multi_templ.c>
1383
1384 /* Apply "fn" to each of the elements of "mv" with as second argument "v".
1385  */
1386 static __isl_give isl_multi_val *isl_multi_val_fn_val(
1387         __isl_take isl_multi_val *mv,
1388         __isl_give isl_val *(*fn)(__isl_take isl_val *v1,
1389                                         __isl_take isl_val *v2),
1390         __isl_take isl_val *v)
1391 {
1392         int i;
1393
1394         mv = isl_multi_val_cow(mv);
1395         if (!mv || !v)
1396                 goto error;
1397
1398         for (i = 0; i < mv->n; ++i) {
1399                 mv->p[i] = fn(mv->p[i], isl_val_copy(v));
1400                 if (!mv->p[i])
1401                         goto error;
1402         }
1403
1404         isl_val_free(v);
1405         return mv;
1406 error:
1407         isl_val_free(v);
1408         isl_multi_val_free(mv);
1409         return NULL;
1410 }
1411
1412 /* Add "v" to each of the elements of "mv".
1413  */
1414 __isl_give isl_multi_val *isl_multi_val_add_val(__isl_take isl_multi_val *mv,
1415         __isl_take isl_val *v)
1416 {
1417         if (!v)
1418                 return isl_multi_val_free(mv);
1419         if (isl_val_is_zero(v)) {
1420                 isl_val_free(v);
1421                 return mv;
1422         }
1423         return isl_multi_val_fn_val(mv, &isl_val_add, v);
1424 }
1425
1426 /* Reduce the elements of "mv" modulo "v".
1427  */
1428 __isl_give isl_multi_val *isl_multi_val_mod_val(__isl_take isl_multi_val *mv,
1429         __isl_take isl_val *v)
1430 {
1431         return isl_multi_val_fn_val(mv, &isl_val_mod, v);
1432 }