isl_seq.c

   1 /*
   2  * Copyright 2008-2009 Katholieke Universiteit Leuven
   3  * Copyright 2011      INRIA Saclay
   4  *
   5  * Use of this software is governed by the MIT license
   6  *
   7  * Written by Sven Verdoolaege, K.U.Leuven, Departement
   8  * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
   9  */
  10
  11 #include <isl_ctx_private.h>
  12 #include <isl_seq.h>
  13
  14 void isl_seq_clr(isl_int *p, unsigned len)
  15 {
  16         int i;
  17         for (i = 0; i < len; ++i)
  18                 isl_int_set_si(p[i], 0);
  19 }
  20
  21 void isl_seq_set_si(isl_int *p, int v, unsigned len)
  22 {
  23         int i;
  24         for (i = 0; i < len; ++i)
  25                 isl_int_set_si(p[i], v);
  26 }
  27
  28 void isl_seq_set(isl_int *p, isl_int v, unsigned len)
  29 {
  30         int i;
  31         for (i = 0; i < len; ++i)
  32                 isl_int_set(p[i], v);
  33 }
  34
  35 void isl_seq_neg(isl_int *dst, isl_int *src, unsigned len)
  36 {
  37         int i;
  38         for (i = 0; i < len; ++i)
  39                 isl_int_neg(dst[i], src[i]);
  40 }
  41
  42 void isl_seq_cpy(isl_int *dst, isl_int *src, unsigned len)
  43 {
  44         int i;
  45         for (i = 0; i < len; ++i)
  46                 isl_int_set(dst[i], src[i]);
  47 }
  48
  49 void isl_seq_submul(isl_int *dst, isl_int f, isl_int *src, unsigned len)
  50 {
  51         int i;
  52         for (i = 0; i < len; ++i)
  53                 isl_int_submul(dst[i], f, src[i]);
  54 }
  55
  56 void isl_seq_addmul(isl_int *dst, isl_int f, isl_int *src, unsigned len)
  57 {
  58         int i;
  59         for (i = 0; i < len; ++i)
  60                 isl_int_addmul(dst[i], f, src[i]);
  61 }
  62
  63 void isl_seq_swp_or_cpy(isl_int *dst, isl_int *src, unsigned len)
  64 {
  65         int i;
  66         for (i = 0; i < len; ++i)
  67                 isl_int_swap_or_set(dst[i], src[i]);
  68 }
  69
  70 void isl_seq_scale(isl_int *dst, isl_int *src, isl_int m, unsigned len)
  71 {
  72         int i;
  73         for (i = 0; i < len; ++i)
  74                 isl_int_mul(dst[i], src[i], m);
  75 }
  76
  77 void isl_seq_scale_down(isl_int *dst, isl_int *src, isl_int m, unsigned len)
  78 {
  79         int i;
  80         for (i = 0; i < len; ++i)
  81                 isl_int_divexact(dst[i], src[i], m);
  82 }
  83
  84 void isl_seq_cdiv_q(isl_int *dst, isl_int *src, isl_int m, unsigned len)
  85 {
  86         int i;
  87         for (i = 0; i < len; ++i)
  88                 isl_int_cdiv_q(dst[i], src[i], m);
  89 }
  90
  91 void isl_seq_fdiv_q(isl_int *dst, isl_int *src, isl_int m, unsigned len)
  92 {
  93         int i;
  94         for (i = 0; i < len; ++i)
  95                 isl_int_fdiv_q(dst[i], src[i], m);
  96 }
  97
  98 void isl_seq_fdiv_r(isl_int *dst, isl_int *src, isl_int m, unsigned len)
  99 {
 100         int i;
 101         for (i = 0; i < len; ++i)
 102                 isl_int_fdiv_r(dst[i], src[i], m);
 103 }
 104
 105 void isl_seq_combine(isl_int *dst, isl_int m1, isl_int *src1,
 106                         isl_int m2, isl_int *src2, unsigned len)
 107 {
 108         int i;
 109         isl_int tmp;
 110
 111         if (dst == src1 && isl_int_is_one(m1)) {
 112                 if (isl_int_is_zero(m2))
 113                         return;
 114                 for (i = 0; i < len; ++i)
 115                         isl_int_addmul(src1[i], m2, src2[i]);
 116                 return;
 117         }
 118
 119         isl_int_init(tmp);
 120         for (i = 0; i < len; ++i) {
 121                 isl_int_mul(tmp, m1, src1[i]);
 122                 isl_int_addmul(tmp, m2, src2[i]);
 123                 isl_int_set(dst[i], tmp);
 124         }
 125         isl_int_clear(tmp);
 126 }
 127
 128 /* Eliminate element "pos" from "dst" using "src".
 129  * In particular, let d = dst[pos] and s = src[pos], then
 130  * dst is replaced by (|s| dst - sgn(s)d src)/gcd(s,d),
 131  * such that dst[pos] is zero after the elimination.
 132  * If "m" is not NULL, then *m is multiplied by |s|/gcd(s,d).
 133  * That is, it is multiplied by the same factor as "dst".
 134  */
 135 void isl_seq_elim(isl_int *dst, isl_int *src, unsigned pos, unsigned len,
 136                   isl_int *m)
 137 {
 138         isl_int a;
 139         isl_int b;
 140
 141         if (isl_int_is_zero(dst[pos]))
 142                 return;
 143
 144         isl_int_init(a);
 145         isl_int_init(b);
 146
 147         isl_int_gcd(a, src[pos], dst[pos]);
 148         isl_int_divexact(b, dst[pos], a);
 149         if (isl_int_is_pos(src[pos]))
 150                 isl_int_neg(b, b);
 151         isl_int_divexact(a, src[pos], a);
 152         isl_int_abs(a, a);
 153         isl_seq_combine(dst, a, dst, b, src, len);
 154
 155         if (m)
 156                 isl_int_mul(*m, *m, a);
 157
 158         isl_int_clear(a);
 159         isl_int_clear(b);
 160 }
 161
 162 int isl_seq_eq(isl_int *p1, isl_int *p2, unsigned len)
 163 {
 164         int i;
 165         for (i = 0; i < len; ++i)
 166                 if (isl_int_ne(p1[i], p2[i]))
 167                         return 0;
 168         return 1;
 169 }
 170
 171 int isl_seq_cmp(isl_int *p1, isl_int *p2, unsigned len)
 172 {
 173         int i;
 174         int cmp;
 175         for (i = 0; i < len; ++i)
 176                 if ((cmp = isl_int_cmp(p1[i], p2[i])) != 0)
 177                         return cmp;
 178         return 0;
 179 }
 180
 181 int isl_seq_is_neg(isl_int *p1, isl_int *p2, unsigned len)
 182 {
 183         int i;
 184
 185         for (i = 0; i < len; ++i) {
 186                 if (isl_int_abs_ne(p1[i], p2[i]))
 187                         return 0;
 188                 if (isl_int_is_zero(p1[i]))
 189                         continue;
 190                 if (isl_int_eq(p1[i], p2[i]))
 191                         return 0;
 192         }
 193         return 1;
 194 }
 195
 196 int isl_seq_first_non_zero(isl_int *p, unsigned len)
 197 {
 198         int i;
 199
 200         for (i = 0; i < len; ++i)
 201                 if (!isl_int_is_zero(p[i]))
 202                         return i;
 203         return -1;
 204 }
 205
 206 int isl_seq_last_non_zero(isl_int *p, unsigned len)
 207 {
 208         int i;
 209
 210         for (i = len - 1; i >= 0; --i)
 211                 if (!isl_int_is_zero(p[i]))
 212                         return i;
 213         return -1;
 214 }
 215
 216 void isl_seq_abs_max(isl_int *p, unsigned len, isl_int *max)
 217 {
 218         int i;
 219
 220         isl_int_set_si(*max, 0);
 221
 222         for (i = 0; i < len; ++i)
 223                 if (isl_int_abs_gt(p[i], *max))
 224                         isl_int_abs(*max, p[i]);
 225 }
 226
 227 int isl_seq_abs_min_non_zero(isl_int *p, unsigned len)
 228 {
 229         int i, min = isl_seq_first_non_zero(p, len);
 230         if (min < 0)
 231                 return -1;
 232         for (i = min + 1; i < len; ++i) {
 233                 if (isl_int_is_zero(p[i]))
 234                         continue;
 235                 if (isl_int_abs_lt(p[i], p[min]))
 236                         min = i;
 237         }
 238         return min;
 239 }
 240
 241 void isl_seq_gcd(isl_int *p, unsigned len, isl_int *gcd)
 242 {
 243         int i, min = isl_seq_abs_min_non_zero(p, len);
 244
 245         if (min < 0) {
 246                 isl_int_set_si(*gcd, 0);
 247                 return;
 248         }
 249         isl_int_abs(*gcd, p[min]);
 250         for (i = 0; isl_int_cmp_si(*gcd, 1) > 0 && i < len; ++i) {
 251                 if (i == min)
 252                         continue;
 253                 if (isl_int_is_zero(p[i]))
 254                         continue;
 255                 isl_int_gcd(*gcd, *gcd, p[i]);
 256         }
 257 }
 258
 259 void isl_seq_normalize(struct isl_ctx *ctx, isl_int *p, unsigned len)
 260 {
 261         if (len == 0)
 262                 return;
 263         isl_seq_gcd(p, len, &ctx->normalize_gcd);
 264         if (!isl_int_is_zero(ctx->normalize_gcd) &&
 265             !isl_int_is_one(ctx->normalize_gcd))
 266                 isl_seq_scale_down(p, p, ctx->normalize_gcd, len);
 267 }
 268
 269 void isl_seq_lcm(isl_int *p, unsigned len, isl_int *lcm)
 270 {
 271         int i;
 272
 273         if (len == 0) {
 274                 isl_int_set_si(*lcm, 1);
 275                 return;
 276         }
 277         isl_int_set(*lcm, p[0]);
 278         for (i = 1; i < len; ++i)
 279                 isl_int_lcm(*lcm, *lcm, p[i]);
 280 }
 281
 282 void isl_seq_inner_product(isl_int *p1, isl_int *p2, unsigned len,
 283                            isl_int *prod)
 284 {
 285         int i;
 286         if (len == 0) {
 287                 isl_int_set_si(*prod, 0);
 288                 return;
 289         }
 290         isl_int_mul(*prod, p1[0], p2[0]);
 291         for (i = 1; i < len; ++i)
 292                 isl_int_addmul(*prod, p1[i], p2[i]);
 293 }
 294
 295 uint32_t isl_seq_hash(isl_int *p, unsigned len, uint32_t hash)
 296 {
 297         int i;
 298         for (i = 0; i < len; ++i) {
 299                 if (isl_int_is_zero(p[i]))
 300                         continue;
 301                 hash *= 16777619;
 302                 hash ^= (i & 0xFF);
 303                 hash = isl_int_hash(p[i], hash);
 304         }
 305         return hash;
 306 }
 307
 308 /* Given two affine expressions "p" of length p_len (including the
 309  * denominator and the constant term) and "subs" of length subs_len,
 310  * plug in "subs" for the variable at position "pos".
 311  * The variables of "subs" and "p" are assumed to match up to subs_len,
 312  * but "p" may have additional variables.
 313  * "v" is an initialized isl_int that can be used internally.
 314  *
 315  * In particular, if "p" represents the expression
 316  *
 317  *      (a i + g)/m
 318  *
 319  * with i the variable at position "pos" and "subs" represents the expression
 320  *
 321  *      f/d
 322  *
 323  * then the result represents the expression
 324  *
 325  *      (a f + d g)/(m d)
 326  *
 327  */
 328 void isl_seq_substitute(isl_int *p, int pos, isl_int *subs,
 329         int p_len, int subs_len, isl_int v)
 330 {
 331         isl_int_set(v, p[1 + pos]);
 332         isl_int_set_si(p[1 + pos], 0);
 333         isl_seq_combine(p + 1, subs[0], p + 1, v, subs + 1, subs_len - 1);
 334         isl_seq_scale(p + subs_len, p + subs_len, subs[0], p_len - subs_len);
 335         isl_int_mul(p[0], p[0], subs[0]);
 336 }
 337
 338 uint32_t isl_seq_get_hash(isl_int *p, unsigned len)
 339 {
 340         uint32_t hash = isl_hash_init();
 341
 342         return isl_seq_hash(p, len, hash);
 343 }
 344
 345 uint32_t isl_seq_get_hash_bits(isl_int *p, unsigned len, unsigned bits)
 346 {
 347         uint32_t hash;
 348
 349         hash = isl_seq_get_hash(p, len);
 350         return isl_hash_bits(hash, bits);
 351 }
 352
 353 void isl_seq_dump(isl_int *p, unsigned len)
 354 {
 355         int i;
 356
 357         for (i = 0; i < len; ++i) {
 358                 if (i)
 359                         fprintf(stderr, " ");
 360                 isl_int_print(stderr, p[i], 0);
 361         }
 362         fprintf(stderr, "\n");
 363 }