isl_aff.c

   1 /*
   2  * Copyright 2011      INRIA Saclay
   3  *
   4  * Use of this software is governed by the GNU LGPLv2.1 license
   5  *
   6  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
   7  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
   8  * 91893 Orsay, France
   9  */
  10
  11 #include <isl_aff_private.h>
  12 #include <isl_local_space_private.h>
  13 #include <isl_mat_private.h>
  14 #include <isl/seq.h>
  15
  16 __isl_give isl_aff *isl_aff_alloc_vec(__isl_take isl_local_space *ls,
  17         __isl_take isl_vec *v)
  18 {
  19         isl_aff *aff;
  20
  21         if (!ls || !v)
  22                 goto error;
  23
  24         aff = isl_calloc_type(v->ctx, struct isl_aff);
  25         if (!aff)
  26                 goto error;
  27
  28         aff->ref = 1;
  29         aff->ls = ls;
  30         aff->v = v;
  31
  32         return aff;
  33 error:
  34         isl_local_space_free(ls);
  35         isl_vec_free(v);
  36         return NULL;
  37 }
  38
  39 __isl_give isl_aff *isl_aff_alloc(__isl_take isl_local_space *ls)
  40 {
  41         isl_ctx *ctx;
  42         isl_vec *v;
  43         unsigned total;
  44
  45         if (!ls)
  46                 return NULL;
  47
  48         ctx = isl_local_space_get_ctx(ls);
  49         if (!isl_local_space_divs_known(ls))
  50                 isl_die(ctx, isl_error_invalid, "local space has unknown divs",
  51                         goto error);
  52
  53         total = isl_local_space_dim(ls, isl_dim_all);
  54         v = isl_vec_alloc(ctx, 1 + 1 + total);
  55         return isl_aff_alloc_vec(ls, v);
  56 error:
  57         isl_local_space_free(ls);
  58         return NULL;
  59 }
  60
  61 __isl_give isl_aff *isl_aff_zero(__isl_take isl_local_space *ls)
  62 {
  63         isl_aff *aff;
  64
  65         aff = isl_aff_alloc(ls);
  66         if (!aff)
  67                 return NULL;
  68
  69         isl_int_set_si(aff->v->el[0], 1);
  70         isl_seq_clr(aff->v->el + 1, aff->v->size - 1);
  71
  72         return aff;
  73 }
  74
  75 __isl_give isl_aff *isl_aff_copy(__isl_keep isl_aff *aff)
  76 {
  77         if (!aff)
  78                 return NULL;
  79
  80         aff->ref++;
  81         return aff;
  82 }
  83
  84 __isl_give isl_aff *isl_aff_dup(__isl_keep isl_aff *aff)
  85 {
  86         if (!aff)
  87                 return NULL;
  88
  89         return isl_aff_alloc_vec(isl_local_space_copy(aff->ls),
  90                                  isl_vec_copy(aff->v));
  91 }
  92
  93 __isl_give isl_aff *isl_aff_cow(__isl_take isl_aff *aff)
  94 {
  95         if (!aff)
  96                 return NULL;
  97
  98         if (aff->ref == 1)
  99                 return aff;
 100         aff->ref--;
 101         return isl_aff_dup(aff);
 102 }
 103
 104 void *isl_aff_free(__isl_take isl_aff *aff)
 105 {
 106         if (!aff)
 107                 return NULL;
 108
 109         if (--aff->ref > 0)
 110                 return NULL;
 111
 112         isl_local_space_free(aff->ls);
 113         isl_vec_free(aff->v);
 114
 115         free(aff);
 116
 117         return NULL;
 118 }
 119
 120 isl_ctx *isl_aff_get_ctx(__isl_keep isl_aff *aff)
 121 {
 122         return aff ? isl_local_space_get_ctx(aff->ls) : NULL;
 123 }
 124
 125 int isl_aff_dim(__isl_keep isl_aff *aff, enum isl_dim_type type)
 126 {
 127         return aff ? isl_local_space_dim(aff->ls, type) : 0;
 128 }
 129
 130 __isl_give isl_dim *isl_aff_get_dim(__isl_keep isl_aff *aff)
 131 {
 132         return aff ? isl_local_space_get_dim(aff->ls) : NULL;
 133 }
 134
 135 __isl_give isl_local_space *isl_aff_get_local_space(__isl_keep isl_aff *aff)
 136 {
 137         return aff ? isl_local_space_copy(aff->ls) : NULL;
 138 }
 139
 140 const char *isl_aff_get_dim_name(__isl_keep isl_aff *aff,
 141         enum isl_dim_type type, unsigned pos)
 142 {
 143         return aff ? isl_local_space_get_dim_name(aff->ls, type, pos) : 0;
 144 }
 145
 146 int isl_aff_plain_is_zero(__isl_keep isl_aff *aff)
 147 {
 148         if (!aff)
 149                 return -1;
 150
 151         return isl_seq_first_non_zero(aff->v->el + 1, aff->v->size - 1) < 0;
 152 }
 153
 154 int isl_aff_plain_is_equal(__isl_keep isl_aff *aff1, __isl_keep isl_aff *aff2)
 155 {
 156         int equal;
 157
 158         if (!aff1 || !aff2)
 159                 return -1;
 160
 161         equal = isl_local_space_is_equal(aff1->ls, aff2->ls);
 162         if (equal < 0 || !equal)
 163                 return equal;
 164
 165         return isl_vec_is_equal(aff1->v, aff2->v);
 166 }
 167
 168 int isl_aff_get_denominator(__isl_keep isl_aff *aff, isl_int *v)
 169 {
 170         if (!aff)
 171                 return -1;
 172         isl_int_set(*v, aff->v->el[0]);
 173         return 0;
 174 }
 175
 176 int isl_aff_get_constant(__isl_keep isl_aff *aff, isl_int *v)
 177 {
 178         if (!aff)
 179                 return -1;
 180         isl_int_set(*v, aff->v->el[1]);
 181         return 0;
 182 }
 183
 184 int isl_aff_get_coefficient(__isl_keep isl_aff *aff,
 185         enum isl_dim_type type, int pos, isl_int *v)
 186 {
 187         if (!aff)
 188                 return -1;
 189
 190         if (pos >= isl_local_space_dim(aff->ls, type))
 191                 isl_die(aff->v->ctx, isl_error_invalid,
 192                         "position out of bounds", return -1);
 193
 194         pos += isl_local_space_offset(aff->ls, type);
 195         isl_int_set(*v, aff->v->el[1 + pos]);
 196
 197         return 0;
 198 }
 199
 200 __isl_give isl_aff *isl_aff_set_denominator(__isl_take isl_aff *aff, isl_int v)
 201 {
 202         aff = isl_aff_cow(aff);
 203         if (!aff)
 204                 return NULL;
 205
 206         aff->v = isl_vec_cow(aff->v);
 207         if (!aff->v)
 208                 return isl_aff_free(aff);
 209
 210         isl_int_set(aff->v->el[0], v);
 211
 212         return aff;
 213 }
 214
 215 __isl_give isl_aff *isl_aff_set_constant(__isl_take isl_aff *aff, isl_int v)
 216 {
 217         aff = isl_aff_cow(aff);
 218         if (!aff)
 219                 return NULL;
 220
 221         aff->v = isl_vec_cow(aff->v);
 222         if (!aff->v)
 223                 return isl_aff_free(aff);
 224
 225         isl_int_set(aff->v->el[1], v);
 226
 227         return aff;
 228 }
 229
 230 __isl_give isl_aff *isl_aff_add_constant(__isl_take isl_aff *aff, isl_int v)
 231 {
 232         if (isl_int_is_zero(v))
 233                 return aff;
 234
 235         aff = isl_aff_cow(aff);
 236         if (!aff)
 237                 return NULL;
 238
 239         aff->v = isl_vec_cow(aff->v);
 240         if (!aff->v)
 241                 return isl_aff_free(aff);
 242
 243         isl_int_addmul(aff->v->el[1], aff->v->el[0], v);
 244
 245         return aff;
 246 }
 247
 248 __isl_give isl_aff *isl_aff_add_constant_si(__isl_take isl_aff *aff, int v)
 249 {
 250         isl_int t;
 251
 252         isl_int_init(t);
 253         isl_int_set_si(t, v);
 254         aff = isl_aff_add_constant(aff, t);
 255         isl_int_clear(t);
 256
 257         return aff;
 258 }
 259
 260 __isl_give isl_aff *isl_aff_set_constant_si(__isl_take isl_aff *aff, int v)
 261 {
 262         aff = isl_aff_cow(aff);
 263         if (!aff)
 264                 return NULL;
 265
 266         aff->v = isl_vec_cow(aff->v);
 267         if (!aff->v)
 268                 return isl_aff_free(aff);
 269
 270         isl_int_set_si(aff->v->el[1], v);
 271
 272         return aff;
 273 }
 274
 275 __isl_give isl_aff *isl_aff_set_coefficient(__isl_take isl_aff *aff,
 276         enum isl_dim_type type, int pos, isl_int v)
 277 {
 278         if (!aff)
 279                 return NULL;
 280
 281         if (pos >= isl_local_space_dim(aff->ls, type))
 282                 isl_die(aff->v->ctx, isl_error_invalid,
 283                         "position out of bounds", return isl_aff_free(aff));
 284
 285         aff = isl_aff_cow(aff);
 286         if (!aff)
 287                 return NULL;
 288
 289         aff->v = isl_vec_cow(aff->v);
 290         if (!aff->v)
 291                 return isl_aff_free(aff);
 292
 293         pos += isl_local_space_offset(aff->ls, type);
 294         isl_int_set(aff->v->el[1 + pos], v);
 295
 296         return aff;
 297 }
 298
 299 __isl_give isl_aff *isl_aff_set_coefficient_si(__isl_take isl_aff *aff,
 300         enum isl_dim_type type, int pos, int v)
 301 {
 302         if (!aff)
 303                 return NULL;
 304
 305         if (pos >= isl_local_space_dim(aff->ls, type))
 306                 isl_die(aff->v->ctx, isl_error_invalid,
 307                         "position out of bounds", return isl_aff_free(aff));
 308
 309         aff = isl_aff_cow(aff);
 310         if (!aff)
 311                 return NULL;
 312
 313         aff->v = isl_vec_cow(aff->v);
 314         if (!aff->v)
 315                 return isl_aff_free(aff);
 316
 317         pos += isl_local_space_offset(aff->ls, type);
 318         isl_int_set_si(aff->v->el[1 + pos], v);
 319
 320         return aff;
 321 }
 322
 323 __isl_give isl_aff *isl_aff_add_coefficient(__isl_take isl_aff *aff,
 324         enum isl_dim_type type, int pos, isl_int v)
 325 {
 326         if (!aff)
 327                 return NULL;
 328
 329         if (pos >= isl_local_space_dim(aff->ls, type))
 330                 isl_die(aff->v->ctx, isl_error_invalid,
 331                         "position out of bounds", return isl_aff_free(aff));
 332
 333         aff = isl_aff_cow(aff);
 334         if (!aff)
 335                 return NULL;
 336
 337         aff->v = isl_vec_cow(aff->v);
 338         if (!aff->v)
 339                 return isl_aff_free(aff);
 340
 341         pos += isl_local_space_offset(aff->ls, type);
 342         isl_int_addmul(aff->v->el[1 + pos], aff->v->el[0], v);
 343
 344         return aff;
 345 }
 346
 347 __isl_give isl_aff *isl_aff_add_coefficient_si(__isl_take isl_aff *aff,
 348         enum isl_dim_type type, int pos, int v)
 349 {
 350         isl_int t;
 351
 352         isl_int_init(t);
 353         isl_int_set_si(t, v);
 354         aff = isl_aff_add_coefficient(aff, type, pos, t);
 355         isl_int_clear(t);
 356
 357         return aff;
 358 }
 359
 360 __isl_give isl_div *isl_aff_get_div(__isl_keep isl_aff *aff, int pos)
 361 {
 362         if (!aff)
 363                 return NULL;
 364
 365         return isl_local_space_get_div(aff->ls, pos);
 366 }
 367
 368 __isl_give isl_aff *isl_aff_neg(__isl_take isl_aff *aff)
 369 {
 370         aff = isl_aff_cow(aff);
 371         if (!aff)
 372                 return NULL;
 373         aff->v = isl_vec_cow(aff->v);
 374         if (!aff->v)
 375                 return isl_aff_free(aff);
 376
 377         isl_seq_neg(aff->v->el + 1, aff->v->el + 1, aff->v->size - 1);
 378
 379         return aff;
 380 }
 381
 382 /* Given f, return floor(f).
 383  * If f is an integer expression, then just return f.
 384  * Otherwise, create a new div d = [f] and return the expression d.
 385  */
 386 __isl_give isl_aff *isl_aff_floor(__isl_take isl_aff *aff)
 387 {
 388         int size;
 389         isl_ctx *ctx;
 390
 391         if (!aff)
 392                 return NULL;
 393
 394         if (isl_int_is_one(aff->v->el[0]))
 395                 return aff;
 396
 397         aff = isl_aff_cow(aff);
 398         if (!aff)
 399                 return NULL;
 400
 401         aff->ls = isl_local_space_add_div(aff->ls, isl_vec_copy(aff->v));
 402         if (!aff->ls)
 403                 return isl_aff_free(aff);
 404
 405         ctx = isl_aff_get_ctx(aff);
 406         size = aff->v->size;
 407         isl_vec_free(aff->v);
 408         aff->v = isl_vec_alloc(ctx, size + 1);
 409         aff->v = isl_vec_clr(aff->v);
 410         if (!aff->v)
 411                 return isl_aff_free(aff);
 412         isl_int_set_si(aff->v->el[0], 1);
 413         isl_int_set_si(aff->v->el[size], 1);
 414
 415         return aff;
 416 }
 417
 418 /* Given f, return ceil(f).
 419  * If f is an integer expression, then just return f.
 420  * Otherwise, create a new div d = [-f] and return the expression -d.
 421  */
 422 __isl_give isl_aff *isl_aff_ceil(__isl_take isl_aff *aff)
 423 {
 424         if (!aff)
 425                 return NULL;
 426
 427         if (isl_int_is_one(aff->v->el[0]))
 428                 return aff;
 429
 430         aff = isl_aff_neg(aff);
 431         aff = isl_aff_floor(aff);
 432         aff = isl_aff_neg(aff);
 433
 434         return aff;
 435 }
 436
 437 /* Apply the expansion computed by isl_merge_divs.
 438  * The expansion itself is given by "exp" while the resulting
 439  * list of divs is given by "div".
 440  */
 441 __isl_give isl_aff *isl_aff_expand_divs( __isl_take isl_aff *aff,
 442         __isl_take isl_mat *div, int *exp)
 443 {
 444         int i, j;
 445         int old_n_div;
 446         int new_n_div;
 447         int offset;
 448
 449         aff = isl_aff_cow(aff);
 450         if (!aff || !div)
 451                 goto error;
 452
 453         old_n_div = isl_local_space_dim(aff->ls, isl_dim_div);
 454         new_n_div = isl_mat_rows(div);
 455         if (new_n_div < old_n_div)
 456                 isl_die(isl_mat_get_ctx(div), isl_error_invalid,
 457                         "not an expansion", goto error);
 458
 459         aff->v = isl_vec_extend(aff->v, aff->v->size + new_n_div - old_n_div);
 460         if (!aff->v)
 461                 goto error;
 462
 463         offset = 1 + isl_local_space_offset(aff->ls, isl_dim_div);
 464         j = old_n_div - 1;
 465         for (i = new_n_div - 1; i >= 0; --i) {
 466                 if (j >= 0 && exp[j] == i) {
 467                         if (i != j)
 468                                 isl_int_swap(aff->v->el[offset + i],
 469                                              aff->v->el[offset + j]);
 470                         j--;
 471                 } else
 472                         isl_int_set_si(aff->v->el[offset + i], 0);
 473         }
 474
 475         aff->ls = isl_local_space_replace_divs(aff->ls, isl_mat_copy(div));
 476         if (!aff->ls)
 477                 goto error;
 478         isl_mat_free(div);
 479         return aff;
 480 error:
 481         isl_aff_free(aff);
 482         isl_mat_free(div);
 483         return NULL;
 484 }
 485
 486 /* Add two affine expressions that live in the same local space.
 487  */
 488 static __isl_give isl_aff *add_expanded(__isl_take isl_aff *aff1,
 489         __isl_take isl_aff *aff2)
 490 {
 491         isl_int gcd, f;
 492
 493         aff1 = isl_aff_cow(aff1);
 494         if (!aff1 || !aff2)
 495                 goto error;
 496
 497         aff1->v = isl_vec_cow(aff1->v);
 498         if (!aff1->v)
 499                 goto error;
 500
 501         isl_int_init(gcd);
 502         isl_int_init(f);
 503         isl_int_gcd(gcd, aff1->v->el[0], aff2->v->el[0]);
 504         isl_int_divexact(f, aff2->v->el[0], gcd);
 505         isl_seq_scale(aff1->v->el + 1, aff1->v->el + 1, f, aff1->v->size - 1);
 506         isl_int_divexact(f, aff1->v->el[0], gcd);
 507         isl_seq_addmul(aff1->v->el + 1, f, aff2->v->el + 1, aff1->v->size - 1);
 508         isl_int_divexact(f, aff2->v->el[0], gcd);
 509         isl_int_mul(aff1->v->el[0], aff1->v->el[0], f);
 510         isl_int_clear(f);
 511         isl_int_clear(gcd);
 512
 513         isl_aff_free(aff2);
 514         return aff1;
 515 error:
 516         isl_aff_free(aff1);
 517         isl_aff_free(aff2);
 518         return NULL;
 519 }
 520
 521 __isl_give isl_aff *isl_aff_add(__isl_take isl_aff *aff1,
 522         __isl_take isl_aff *aff2)
 523 {
 524         isl_ctx *ctx;
 525         int *exp1 = NULL;
 526         int *exp2 = NULL;
 527         isl_mat *div;
 528
 529         if (!aff1 || !aff2)
 530                 goto error;
 531
 532         ctx = isl_aff_get_ctx(aff1);
 533         if (!isl_dim_equal(aff1->ls->dim, aff2->ls->dim))
 534                 isl_die(ctx, isl_error_invalid,
 535                         "spaces don't match", goto error);
 536
 537         if (aff1->ls->div->n_row == 0 && aff2->ls->div->n_row == 0)
 538                 return add_expanded(aff1, aff2);
 539
 540         exp1 = isl_alloc_array(ctx, int, aff1->ls->div->n_row);
 541         exp2 = isl_alloc_array(ctx, int, aff2->ls->div->n_row);
 542         if (!exp1 || !exp2)
 543                 goto error;
 544
 545         div = isl_merge_divs(aff1->ls->div, aff2->ls->div, exp1, exp2);
 546         aff1 = isl_aff_expand_divs(aff1, isl_mat_copy(div), exp1);
 547         aff2 = isl_aff_expand_divs(aff2, div, exp2);
 548         free(exp1);
 549         free(exp2);
 550
 551         return add_expanded(aff1, aff2);
 552 error:
 553         free(exp1);
 554         free(exp2);
 555         isl_aff_free(aff1);
 556         isl_aff_free(aff2);
 557         return NULL;
 558 }
 559
 560 __isl_give isl_aff *isl_aff_sub(__isl_take isl_aff *aff1,
 561         __isl_take isl_aff *aff2)
 562 {
 563         return isl_aff_add(aff1, isl_aff_neg(aff2));
 564 }
 565
 566 __isl_give isl_aff *isl_aff_scale(__isl_take isl_aff *aff, isl_int f)
 567 {
 568         isl_int gcd;
 569
 570         if (isl_int_is_one(f))
 571                 return aff;
 572
 573         aff = isl_aff_cow(aff);
 574         if (!aff)
 575                 return NULL;
 576         aff->v = isl_vec_cow(aff->v);
 577         if (!aff->v)
 578                 return isl_aff_free(aff);
 579
 580         isl_int_init(gcd);
 581         isl_int_gcd(gcd, aff->v->el[0], f);
 582         isl_int_divexact(aff->v->el[0], aff->v->el[0], gcd);
 583         isl_int_divexact(gcd, f, gcd);
 584         isl_seq_scale(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
 585         isl_int_clear(gcd);
 586
 587         return aff;
 588 }
 589
 590 __isl_give isl_aff *isl_aff_scale_down(__isl_take isl_aff *aff, isl_int f)
 591 {
 592         isl_int gcd;
 593
 594         if (isl_int_is_one(f))
 595                 return aff;
 596
 597         aff = isl_aff_cow(aff);
 598         if (!aff)
 599                 return NULL;
 600         aff->v = isl_vec_cow(aff->v);
 601         if (!aff->v)
 602                 return isl_aff_free(aff);
 603
 604         isl_int_init(gcd);
 605         isl_seq_gcd(aff->v->el + 1, aff->v->size - 1, &gcd);
 606         isl_int_gcd(gcd, gcd, f);
 607         isl_seq_scale_down(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
 608         isl_int_divexact(gcd, f, gcd);
 609         isl_int_mul(aff->v->el[0], aff->v->el[0], gcd);
 610         isl_int_clear(gcd);
 611
 612         return aff;
 613 }
 614
 615 __isl_give isl_aff *isl_aff_scale_down_ui(__isl_take isl_aff *aff, unsigned f)
 616 {
 617         isl_int v;
 618
 619         if (f == 1)
 620                 return aff;
 621
 622         isl_int_init(v);
 623         isl_int_set_ui(v, f);
 624         aff = isl_aff_scale_down(aff, v);
 625         isl_int_clear(v);
 626
 627         return aff;
 628 }