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