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 ceil(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_ceil(__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         isl_seq_neg(aff->v->el + 1, aff->v->el + 1, aff->v->size - 1);
 380         aff->ls = isl_local_space_add_div(aff->ls, isl_vec_copy(aff->v));
 381         if (!aff->ls)
 382                 goto error;
 383
 384         ctx = isl_aff_get_ctx(aff);
 385         size = aff->v->size;
 386         isl_vec_free(aff->v);
 387         aff->v = isl_vec_alloc(ctx, size + 1);
 388         aff->v = isl_vec_clr(aff->v);
 389         if (!aff->v)
 390                 goto error;
 391         isl_int_set_si(aff->v->el[0], 1);
 392         isl_int_set_si(aff->v->el[size], -1);
 393
 394         return aff;
 395 error:
 396         isl_aff_free(aff);
 397         return NULL;
 398 }
 399
 400 /* Apply the expansion computed by isl_merge_divs.
 401  * The expansion itself is given by "exp" while the resulting
 402  * list of divs is given by "div".
 403  */
 404 __isl_give isl_aff *isl_aff_expand_divs( __isl_take isl_aff *aff,
 405         __isl_take isl_mat *div, int *exp)
 406 {
 407         int i, j;
 408         int old_n_div;
 409         int new_n_div;
 410         int offset;
 411
 412         aff = isl_aff_cow(aff);
 413         if (!aff || !div)
 414                 goto error;
 415
 416         old_n_div = isl_local_space_dim(aff->ls, isl_dim_div);
 417         new_n_div = isl_mat_rows(div);
 418         if (new_n_div < old_n_div)
 419                 isl_die(isl_mat_get_ctx(div), isl_error_invalid,
 420                         "not an expansion", goto error);
 421
 422         aff->v = isl_vec_extend(aff->v, aff->v->size + new_n_div - old_n_div);
 423         if (!aff->v)
 424                 goto error;
 425
 426         offset = 1 + isl_local_space_offset(aff->ls, isl_dim_div);
 427         j = old_n_div - 1;
 428         for (i = new_n_div - 1; i >= 0; --i) {
 429                 if (j >= 0 && exp[j] == i) {
 430                         if (i != j)
 431                                 isl_int_swap(aff->v->el[offset + i],
 432                                              aff->v->el[offset + j]);
 433                         j--;
 434                 } else
 435                         isl_int_set_si(aff->v->el[offset + i], 0);
 436         }
 437
 438         aff->ls = isl_local_space_replace_divs(aff->ls, isl_mat_copy(div));
 439         if (!aff->ls)
 440                 goto error;
 441         isl_mat_free(div);
 442         return aff;
 443 error:
 444         isl_aff_free(aff);
 445         isl_mat_free(div);
 446         return NULL;
 447 }
 448
 449 /* Add two affine expressions that live in the same local space.
 450  */
 451 static __isl_give isl_aff *add_expanded(__isl_take isl_aff *aff1,
 452         __isl_take isl_aff *aff2)
 453 {
 454         isl_int gcd, f;
 455
 456         aff1 = isl_aff_cow(aff1);
 457         if (!aff1 || !aff2)
 458                 goto error;
 459
 460         aff1->v = isl_vec_cow(aff1->v);
 461         if (!aff1->v)
 462                 goto error;
 463
 464         isl_int_init(gcd);
 465         isl_int_init(f);
 466         isl_int_gcd(gcd, aff1->v->el[0], aff2->v->el[0]);
 467         isl_int_divexact(f, aff2->v->el[0], gcd);
 468         isl_seq_scale(aff1->v->el + 1, aff1->v->el + 1, f, aff1->v->size - 1);
 469         isl_int_divexact(f, aff1->v->el[0], gcd);
 470         isl_seq_addmul(aff1->v->el + 1, f, aff2->v->el + 1, aff1->v->size - 1);
 471         isl_int_divexact(f, aff2->v->el[0], gcd);
 472         isl_int_mul(aff1->v->el[0], aff1->v->el[0], f);
 473         isl_int_clear(f);
 474         isl_int_clear(gcd);
 475
 476         isl_aff_free(aff2);
 477         return aff1;
 478 error:
 479         isl_aff_free(aff1);
 480         isl_aff_free(aff2);
 481         return NULL;
 482 }
 483
 484 __isl_give isl_aff *isl_aff_add(__isl_take isl_aff *aff1,
 485         __isl_take isl_aff *aff2)
 486 {
 487         isl_ctx *ctx;
 488         int *exp1 = NULL;
 489         int *exp2 = NULL;
 490         isl_mat *div;
 491
 492         if (!aff1 || !aff2)
 493                 goto error;
 494
 495         ctx = isl_aff_get_ctx(aff1);
 496         if (!isl_dim_equal(aff1->ls->dim, aff2->ls->dim))
 497                 isl_die(ctx, isl_error_invalid,
 498                         "spaces don't match", goto error);
 499
 500         if (aff1->ls->div->n_row == 0 && aff2->ls->div->n_row == 0)
 501                 return add_expanded(aff1, aff2);
 502
 503         exp1 = isl_alloc_array(ctx, int, aff1->ls->div->n_row);
 504         exp2 = isl_alloc_array(ctx, int, aff2->ls->div->n_row);
 505         if (!exp1 || !exp2)
 506                 goto error;
 507
 508         div = isl_merge_divs(aff1->ls->div, aff2->ls->div, exp1, exp2);
 509         aff1 = isl_aff_expand_divs(aff1, isl_mat_copy(div), exp1);
 510         aff2 = isl_aff_expand_divs(aff2, div, exp2);
 511         free(exp1);
 512         free(exp2);
 513
 514         return add_expanded(aff1, aff2);
 515 error:
 516         free(exp1);
 517         free(exp2);
 518         isl_aff_free(aff1);
 519         isl_aff_free(aff2);
 520         return NULL;
 521 }
 522
 523 __isl_give isl_aff *isl_aff_sub(__isl_take isl_aff *aff1,
 524         __isl_take isl_aff *aff2)
 525 {
 526         return isl_aff_add(aff1, isl_aff_neg(aff2));
 527 }
 528
 529 __isl_give isl_aff *isl_aff_scale(__isl_take isl_aff *aff, isl_int f)
 530 {
 531         isl_int gcd;
 532
 533         if (isl_int_is_one(f))
 534                 return aff;
 535
 536         aff = isl_aff_cow(aff);
 537         if (!aff)
 538                 return NULL;
 539         aff->v = isl_vec_cow(aff->v);
 540         if (!aff->v)
 541                 return isl_aff_free(aff);
 542
 543         isl_int_init(gcd);
 544         isl_int_gcd(gcd, aff->v->el[0], f);
 545         isl_int_divexact(aff->v->el[0], aff->v->el[0], gcd);
 546         isl_int_divexact(gcd, f, gcd);
 547         isl_seq_scale(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
 548         isl_int_clear(gcd);
 549
 550         return aff;
 551 }
 552
 553 __isl_give isl_aff *isl_aff_scale_down(__isl_take isl_aff *aff, isl_int f)
 554 {
 555         isl_int gcd;
 556
 557         if (isl_int_is_one(f))
 558                 return aff;
 559
 560         aff = isl_aff_cow(aff);
 561         if (!aff)
 562                 return NULL;
 563         aff->v = isl_vec_cow(aff->v);
 564         if (!aff->v)
 565                 return isl_aff_free(aff);
 566
 567         isl_int_init(gcd);
 568         isl_seq_gcd(aff->v->el + 1, aff->v->size - 1, &gcd);
 569         isl_int_gcd(gcd, gcd, f);
 570         isl_seq_scale_down(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
 571         isl_int_divexact(gcd, f, gcd);
 572         isl_int_mul(aff->v->el[0], aff->v->el[0], gcd);
 573         isl_int_clear(gcd);
 574
 575         return aff;
 576 }