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_get_denominator(__isl_keep isl_aff *aff, isl_int *v)
 147 {
 148         if (!aff)
 149                 return -1;
 150         isl_int_set(*v, aff->v->el[0]);
 151         return 0;
 152 }
 153
 154 int isl_aff_get_constant(__isl_keep isl_aff *aff, isl_int *v)
 155 {
 156         if (!aff)
 157                 return -1;
 158         isl_int_set(*v, aff->v->el[1]);
 159         return 0;
 160 }
 161
 162 int isl_aff_get_coefficient(__isl_keep isl_aff *aff,
 163         enum isl_dim_type type, int pos, isl_int *v)
 164 {
 165         if (!aff)
 166                 return -1;
 167
 168         if (pos >= isl_local_space_dim(aff->ls, type))
 169                 isl_die(aff->v->ctx, isl_error_invalid,
 170                         "position out of bounds", return -1);
 171
 172         pos += isl_local_space_offset(aff->ls, type);
 173         isl_int_set(*v, aff->v->el[1 + pos]);
 174
 175         return 0;
 176 }
 177
 178 __isl_give isl_aff *isl_aff_set_denominator(__isl_take isl_aff *aff, isl_int v)
 179 {
 180         aff = isl_aff_cow(aff);
 181         if (!aff)
 182                 return NULL;
 183
 184         aff->v = isl_vec_cow(aff->v);
 185         if (!aff->v)
 186                 return isl_aff_free(aff);
 187
 188         isl_int_set(aff->v->el[0], v);
 189
 190         return aff;
 191 }
 192
 193 __isl_give isl_aff *isl_aff_set_constant(__isl_take isl_aff *aff, isl_int v)
 194 {
 195         aff = isl_aff_cow(aff);
 196         if (!aff)
 197                 return NULL;
 198
 199         aff->v = isl_vec_cow(aff->v);
 200         if (!aff->v)
 201                 return isl_aff_free(aff);
 202
 203         isl_int_set(aff->v->el[1], v);
 204
 205         return aff;
 206 }
 207
 208 __isl_give isl_aff *isl_aff_add_constant(__isl_take isl_aff *aff, isl_int v)
 209 {
 210         if (isl_int_is_zero(v))
 211                 return aff;
 212
 213         aff = isl_aff_cow(aff);
 214         if (!aff)
 215                 return NULL;
 216
 217         aff->v = isl_vec_cow(aff->v);
 218         if (!aff->v)
 219                 return isl_aff_free(aff);
 220
 221         isl_int_addmul(aff->v->el[1], aff->v->el[0], v);
 222
 223         return aff;
 224 }
 225
 226 __isl_give isl_aff *isl_aff_add_constant_si(__isl_take isl_aff *aff, int v)
 227 {
 228         isl_int t;
 229
 230         isl_int_init(t);
 231         isl_int_set_si(t, v);
 232         aff = isl_aff_add_constant(aff, t);
 233         isl_int_clear(t);
 234
 235         return aff;
 236 }
 237
 238 __isl_give isl_aff *isl_aff_set_constant_si(__isl_take isl_aff *aff, int v)
 239 {
 240         aff = isl_aff_cow(aff);
 241         if (!aff)
 242                 return NULL;
 243
 244         aff->v = isl_vec_cow(aff->v);
 245         if (!aff->v)
 246                 return isl_aff_free(aff);
 247
 248         isl_int_set_si(aff->v->el[1], v);
 249
 250         return aff;
 251 }
 252
 253 __isl_give isl_aff *isl_aff_set_coefficient(__isl_take isl_aff *aff,
 254         enum isl_dim_type type, int pos, isl_int v)
 255 {
 256         if (!aff)
 257                 return NULL;
 258
 259         if (pos >= isl_local_space_dim(aff->ls, type))
 260                 isl_die(aff->v->ctx, isl_error_invalid,
 261                         "position out of bounds", return isl_aff_free(aff));
 262
 263         aff = isl_aff_cow(aff);
 264         if (!aff)
 265                 return NULL;
 266
 267         aff->v = isl_vec_cow(aff->v);
 268         if (!aff->v)
 269                 return isl_aff_free(aff);
 270
 271         pos += isl_local_space_offset(aff->ls, type);
 272         isl_int_set(aff->v->el[1 + pos], v);
 273
 274         return aff;
 275 }
 276
 277 __isl_give isl_aff *isl_aff_set_coefficient_si(__isl_take isl_aff *aff,
 278         enum isl_dim_type type, int pos, int v)
 279 {
 280         if (!aff)
 281                 return NULL;
 282
 283         if (pos >= isl_local_space_dim(aff->ls, type))
 284                 isl_die(aff->v->ctx, isl_error_invalid,
 285                         "position out of bounds", return isl_aff_free(aff));
 286
 287         aff = isl_aff_cow(aff);
 288         if (!aff)
 289                 return NULL;
 290
 291         aff->v = isl_vec_cow(aff->v);
 292         if (!aff->v)
 293                 return isl_aff_free(aff);
 294
 295         pos += isl_local_space_offset(aff->ls, type);
 296         isl_int_set_si(aff->v->el[1 + pos], v);
 297
 298         return aff;
 299 }
 300
 301 __isl_give isl_aff *isl_aff_add_coefficient(__isl_take isl_aff *aff,
 302         enum isl_dim_type type, int pos, isl_int v)
 303 {
 304         if (!aff)
 305                 return NULL;
 306
 307         if (pos >= isl_local_space_dim(aff->ls, type))
 308                 isl_die(aff->v->ctx, isl_error_invalid,
 309                         "position out of bounds", return isl_aff_free(aff));
 310
 311         aff = isl_aff_cow(aff);
 312         if (!aff)
 313                 return NULL;
 314
 315         aff->v = isl_vec_cow(aff->v);
 316         if (!aff->v)
 317                 return isl_aff_free(aff);
 318
 319         pos += isl_local_space_offset(aff->ls, type);
 320         isl_int_addmul(aff->v->el[1 + pos], aff->v->el[0], v);
 321
 322         return aff;
 323 }
 324
 325 __isl_give isl_aff *isl_aff_add_coefficient_si(__isl_take isl_aff *aff,
 326         enum isl_dim_type type, int pos, int v)
 327 {
 328         isl_int t;
 329
 330         isl_int_init(t);
 331         isl_int_set_si(t, v);
 332         aff = isl_aff_add_coefficient(aff, type, pos, t);
 333         isl_int_clear(t);
 334
 335         return aff;
 336 }
 337
 338 __isl_give isl_div *isl_aff_get_div(__isl_keep isl_aff *aff, int pos)
 339 {
 340         if (!aff)
 341                 return NULL;
 342
 343         return isl_local_space_get_div(aff->ls, pos);
 344 }
 345
 346 __isl_give isl_aff *isl_aff_neg(__isl_take isl_aff *aff)
 347 {
 348         aff = isl_aff_cow(aff);
 349         if (!aff)
 350                 return NULL;
 351         aff->v = isl_vec_cow(aff->v);
 352         if (!aff->v)
 353                 return isl_aff_free(aff);
 354
 355         isl_seq_neg(aff->v->el + 1, aff->v->el + 1, aff->v->size - 1);
 356
 357         return aff;
 358 }
 359
 360 /* Given f, return floor(f).
 361  * If f is an integer expression, then just return f.
 362  * Otherwise, create a new div d = [f] and return the expression d.
 363  */
 364 __isl_give isl_aff *isl_aff_floor(__isl_take isl_aff *aff)
 365 {
 366         int size;
 367         isl_ctx *ctx;
 368
 369         if (!aff)
 370                 return NULL;
 371
 372         if (isl_int_is_one(aff->v->el[0]))
 373                 return aff;
 374
 375         aff = isl_aff_cow(aff);
 376         if (!aff)
 377                 return NULL;
 378
 379         aff->ls = isl_local_space_add_div(aff->ls, isl_vec_copy(aff->v));
 380         if (!aff->ls)
 381                 return isl_aff_free(aff);
 382
 383         ctx = isl_aff_get_ctx(aff);
 384         size = aff->v->size;
 385         isl_vec_free(aff->v);
 386         aff->v = isl_vec_alloc(ctx, size + 1);
 387         aff->v = isl_vec_clr(aff->v);
 388         if (!aff->v)
 389                 return isl_aff_free(aff);
 390         isl_int_set_si(aff->v->el[0], 1);
 391         isl_int_set_si(aff->v->el[size], 1);
 392
 393         return aff;
 394 }
 395
 396 /* Given f, return ceil(f).
 397  * If f is an integer expression, then just return f.
 398  * Otherwise, create a new div d = [-f] and return the expression -d.
 399  */
 400 __isl_give isl_aff *isl_aff_ceil(__isl_take isl_aff *aff)
 401 {
 402         if (!aff)
 403                 return NULL;
 404
 405         if (isl_int_is_one(aff->v->el[0]))
 406                 return aff;
 407
 408         aff = isl_aff_neg(aff);
 409         aff = isl_aff_floor(aff);
 410         aff = isl_aff_neg(aff);
 411
 412         return aff;
 413 }
 414
 415 /* Apply the expansion computed by isl_merge_divs.
 416  * The expansion itself is given by "exp" while the resulting
 417  * list of divs is given by "div".
 418  */
 419 __isl_give isl_aff *isl_aff_expand_divs( __isl_take isl_aff *aff,
 420         __isl_take isl_mat *div, int *exp)
 421 {
 422         int i, j;
 423         int old_n_div;
 424         int new_n_div;
 425         int offset;
 426
 427         aff = isl_aff_cow(aff);
 428         if (!aff || !div)
 429                 goto error;
 430
 431         old_n_div = isl_local_space_dim(aff->ls, isl_dim_div);
 432         new_n_div = isl_mat_rows(div);
 433         if (new_n_div < old_n_div)
 434                 isl_die(isl_mat_get_ctx(div), isl_error_invalid,
 435                         "not an expansion", goto error);
 436
 437         aff->v = isl_vec_extend(aff->v, aff->v->size + new_n_div - old_n_div);
 438         if (!aff->v)
 439                 goto error;
 440
 441         offset = 1 + isl_local_space_offset(aff->ls, isl_dim_div);
 442         j = old_n_div - 1;
 443         for (i = new_n_div - 1; i >= 0; --i) {
 444                 if (j >= 0 && exp[j] == i) {
 445                         if (i != j)
 446                                 isl_int_swap(aff->v->el[offset + i],
 447                                              aff->v->el[offset + j]);
 448                         j--;
 449                 } else
 450                         isl_int_set_si(aff->v->el[offset + i], 0);
 451         }
 452
 453         aff->ls = isl_local_space_replace_divs(aff->ls, isl_mat_copy(div));
 454         if (!aff->ls)
 455                 goto error;
 456         isl_mat_free(div);
 457         return aff;
 458 error:
 459         isl_aff_free(aff);
 460         isl_mat_free(div);
 461         return NULL;
 462 }
 463
 464 /* Add two affine expressions that live in the same local space.
 465  */
 466 static __isl_give isl_aff *add_expanded(__isl_take isl_aff *aff1,
 467         __isl_take isl_aff *aff2)
 468 {
 469         isl_int gcd, f;
 470
 471         aff1 = isl_aff_cow(aff1);
 472         if (!aff1 || !aff2)
 473                 goto error;
 474
 475         aff1->v = isl_vec_cow(aff1->v);
 476         if (!aff1->v)
 477                 goto error;
 478
 479         isl_int_init(gcd);
 480         isl_int_init(f);
 481         isl_int_gcd(gcd, aff1->v->el[0], aff2->v->el[0]);
 482         isl_int_divexact(f, aff2->v->el[0], gcd);
 483         isl_seq_scale(aff1->v->el + 1, aff1->v->el + 1, f, aff1->v->size - 1);
 484         isl_int_divexact(f, aff1->v->el[0], gcd);
 485         isl_seq_addmul(aff1->v->el + 1, f, aff2->v->el + 1, aff1->v->size - 1);
 486         isl_int_divexact(f, aff2->v->el[0], gcd);
 487         isl_int_mul(aff1->v->el[0], aff1->v->el[0], f);
 488         isl_int_clear(f);
 489         isl_int_clear(gcd);
 490
 491         isl_aff_free(aff2);
 492         return aff1;
 493 error:
 494         isl_aff_free(aff1);
 495         isl_aff_free(aff2);
 496         return NULL;
 497 }
 498
 499 __isl_give isl_aff *isl_aff_add(__isl_take isl_aff *aff1,
 500         __isl_take isl_aff *aff2)
 501 {
 502         isl_ctx *ctx;
 503         int *exp1 = NULL;
 504         int *exp2 = NULL;
 505         isl_mat *div;
 506
 507         if (!aff1 || !aff2)
 508                 goto error;
 509
 510         ctx = isl_aff_get_ctx(aff1);
 511         if (!isl_dim_equal(aff1->ls->dim, aff2->ls->dim))
 512                 isl_die(ctx, isl_error_invalid,
 513                         "spaces don't match", goto error);
 514
 515         if (aff1->ls->div->n_row == 0 && aff2->ls->div->n_row == 0)
 516                 return add_expanded(aff1, aff2);
 517
 518         exp1 = isl_alloc_array(ctx, int, aff1->ls->div->n_row);
 519         exp2 = isl_alloc_array(ctx, int, aff2->ls->div->n_row);
 520         if (!exp1 || !exp2)
 521                 goto error;
 522
 523         div = isl_merge_divs(aff1->ls->div, aff2->ls->div, exp1, exp2);
 524         aff1 = isl_aff_expand_divs(aff1, isl_mat_copy(div), exp1);
 525         aff2 = isl_aff_expand_divs(aff2, div, exp2);
 526         free(exp1);
 527         free(exp2);
 528
 529         return add_expanded(aff1, aff2);
 530 error:
 531         free(exp1);
 532         free(exp2);
 533         isl_aff_free(aff1);
 534         isl_aff_free(aff2);
 535         return NULL;
 536 }
 537
 538 __isl_give isl_aff *isl_aff_sub(__isl_take isl_aff *aff1,
 539         __isl_take isl_aff *aff2)
 540 {
 541         return isl_aff_add(aff1, isl_aff_neg(aff2));
 542 }
 543
 544 __isl_give isl_aff *isl_aff_scale(__isl_take isl_aff *aff, isl_int f)
 545 {
 546         isl_int gcd;
 547
 548         if (isl_int_is_one(f))
 549                 return aff;
 550
 551         aff = isl_aff_cow(aff);
 552         if (!aff)
 553                 return NULL;
 554         aff->v = isl_vec_cow(aff->v);
 555         if (!aff->v)
 556                 return isl_aff_free(aff);
 557
 558         isl_int_init(gcd);
 559         isl_int_gcd(gcd, aff->v->el[0], f);
 560         isl_int_divexact(aff->v->el[0], aff->v->el[0], gcd);
 561         isl_int_divexact(gcd, f, gcd);
 562         isl_seq_scale(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
 563         isl_int_clear(gcd);
 564
 565         return aff;
 566 }
 567
 568 __isl_give isl_aff *isl_aff_scale_down(__isl_take isl_aff *aff, isl_int f)
 569 {
 570         isl_int gcd;
 571
 572         if (isl_int_is_one(f))
 573                 return aff;
 574
 575         aff = isl_aff_cow(aff);
 576         if (!aff)
 577                 return NULL;
 578         aff->v = isl_vec_cow(aff->v);
 579         if (!aff->v)
 580                 return isl_aff_free(aff);
 581
 582         isl_int_init(gcd);
 583         isl_seq_gcd(aff->v->el + 1, aff->v->size - 1, &gcd);
 584         isl_int_gcd(gcd, gcd, f);
 585         isl_seq_scale_down(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
 586         isl_int_divexact(gcd, f, gcd);
 587         isl_int_mul(aff->v->el[0], aff->v->el[0], gcd);
 588         isl_int_clear(gcd);
 589
 590         return aff;
 591 }