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