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 /*
 129  * Let d = dst[pos] and s = src[pos]
 130  * dst is replaced by |s| dst - sgn(s)d src
 131  */
 132 void isl_seq_elim(isl_int *dst, isl_int *src, unsigned pos, unsigned len,
 133                   isl_int *m)
 134 {
 135         isl_int a;
 136         isl_int b;
 137
 138         if (isl_int_is_zero(dst[pos]))
 139                 return;
 140
 141         isl_int_init(a);
 142         isl_int_init(b);
 143
 144         isl_int_gcd(a, src[pos], dst[pos]);
 145         isl_int_divexact(b, dst[pos], a);
 146         if (isl_int_is_pos(src[pos]))
 147                 isl_int_neg(b, b);
 148         isl_int_divexact(a, src[pos], a);
 149         isl_int_abs(a, a);
 150         isl_seq_combine(dst, a, dst, b, src, len);
 151
 152         if (m)
 153                 isl_int_mul(*m, *m, a);
 154
 155         isl_int_clear(a);
 156         isl_int_clear(b);
 157 }
 158
 159 int isl_seq_eq(isl_int *p1, isl_int *p2, unsigned len)
 160 {
 161         int i;
 162         for (i = 0; i < len; ++i)
 163                 if (isl_int_ne(p1[i], p2[i]))
 164                         return 0;
 165         return 1;
 166 }
 167
 168 int isl_seq_cmp(isl_int *p1, isl_int *p2, unsigned len)
 169 {
 170         int i;
 171         int cmp;
 172         for (i = 0; i < len; ++i)
 173                 if ((cmp = isl_int_cmp(p1[i], p2[i])) != 0)
 174                         return cmp;
 175         return 0;
 176 }
 177
 178 int isl_seq_is_neg(isl_int *p1, isl_int *p2, unsigned len)
 179 {
 180         int i;
 181
 182         for (i = 0; i < len; ++i) {
 183                 if (isl_int_abs_ne(p1[i], p2[i]))
 184                         return 0;
 185                 if (isl_int_is_zero(p1[i]))
 186                         continue;
 187                 if (isl_int_eq(p1[i], p2[i]))
 188                         return 0;
 189         }
 190         return 1;
 191 }
 192
 193 int isl_seq_first_non_zero(isl_int *p, unsigned len)
 194 {
 195         int i;
 196
 197         for (i = 0; i < len; ++i)
 198                 if (!isl_int_is_zero(p[i]))
 199                         return i;
 200         return -1;
 201 }
 202
 203 int isl_seq_last_non_zero(isl_int *p, unsigned len)
 204 {
 205         int i;
 206
 207         for (i = len - 1; i >= 0; --i)
 208                 if (!isl_int_is_zero(p[i]))
 209                         return i;
 210         return -1;
 211 }
 212
 213 void isl_seq_abs_max(isl_int *p, unsigned len, isl_int *max)
 214 {
 215         int i;
 216
 217         isl_int_set_si(*max, 0);
 218
 219         for (i = 0; i < len; ++i)
 220                 if (isl_int_abs_gt(p[i], *max))
 221                         isl_int_abs(*max, p[i]);
 222 }
 223
 224 int isl_seq_abs_min_non_zero(isl_int *p, unsigned len)
 225 {
 226         int i, min = isl_seq_first_non_zero(p, len);
 227         if (min < 0)
 228                 return -1;
 229         for (i = min + 1; i < len; ++i) {
 230                 if (isl_int_is_zero(p[i]))
 231                         continue;
 232                 if (isl_int_abs_lt(p[i], p[min]))
 233                         min = i;
 234         }
 235         return min;
 236 }
 237
 238 void isl_seq_gcd(isl_int *p, unsigned len, isl_int *gcd)
 239 {
 240         int i, min = isl_seq_abs_min_non_zero(p, len);
 241
 242         if (min < 0) {
 243                 isl_int_set_si(*gcd, 0);
 244                 return;
 245         }
 246         isl_int_abs(*gcd, p[min]);
 247         for (i = 0; isl_int_cmp_si(*gcd, 1) > 0 && i < len; ++i) {
 248                 if (i == min)
 249                         continue;
 250                 if (isl_int_is_zero(p[i]))
 251                         continue;
 252                 isl_int_gcd(*gcd, *gcd, p[i]);
 253         }
 254 }
 255
 256 void isl_seq_normalize(struct isl_ctx *ctx, isl_int *p, unsigned len)
 257 {
 258         if (len == 0)
 259                 return;
 260         isl_seq_gcd(p, len, &ctx->normalize_gcd);
 261         if (!isl_int_is_zero(ctx->normalize_gcd) &&
 262             !isl_int_is_one(ctx->normalize_gcd))
 263                 isl_seq_scale_down(p, p, ctx->normalize_gcd, len);
 264 }
 265
 266 void isl_seq_lcm(isl_int *p, unsigned len, isl_int *lcm)
 267 {
 268         int i;
 269
 270         if (len == 0) {
 271                 isl_int_set_si(*lcm, 1);
 272                 return;
 273         }
 274         isl_int_set(*lcm, p[0]);
 275         for (i = 1; i < len; ++i)
 276                 isl_int_lcm(*lcm, *lcm, p[i]);
 277 }
 278
 279 void isl_seq_inner_product(isl_int *p1, isl_int *p2, unsigned len,
 280                            isl_int *prod)
 281 {
 282         int i;
 283         if (len == 0) {
 284                 isl_int_set_si(*prod, 0);
 285                 return;
 286         }
 287         isl_int_mul(*prod, p1[0], p2[0]);
 288         for (i = 1; i < len; ++i)
 289                 isl_int_addmul(*prod, p1[i], p2[i]);
 290 }
 291
 292 uint32_t isl_seq_hash(isl_int *p, unsigned len, uint32_t hash)
 293 {
 294         int i;
 295         for (i = 0; i < len; ++i) {
 296                 if (isl_int_is_zero(p[i]))
 297                         continue;
 298                 hash *= 16777619;
 299                 hash ^= (i & 0xFF);
 300                 hash = isl_int_hash(p[i], hash);
 301         }
 302         return hash;
 303 }
 304
 305 /* Given two affine expressions "p" of length p_len (including the
 306  * denominator and the constant term) and "subs" of length subs_len,
 307  * plug in "subs" for the variable at position "pos".
 308  * The variables of "subs" and "p" are assumed to match up to subs_len,
 309  * but "p" may have additional variables.
 310  * "v" is an initialized isl_int that can be used internally.
 311  *
 312  * In particular, if "p" represents the expression
 313  *
 314  *      (a i + g)/m
 315  *
 316  * with i the variable at position "pos" and "subs" represents the expression
 317  *
 318  *      f/d
 319  *
 320  * then the result represents the expression
 321  *
 322  *      (a f + d g)/(m d)
 323  *
 324  */
 325 void isl_seq_substitute(isl_int *p, int pos, isl_int *subs,
 326         int p_len, int subs_len, isl_int v)
 327 {
 328         isl_int_set(v, p[1 + pos]);
 329         isl_int_set_si(p[1 + pos], 0);
 330         isl_seq_combine(p + 1, subs[0], p + 1, v, subs + 1, subs_len - 1);
 331         isl_seq_scale(p + subs_len, p + subs_len, subs[0], p_len - subs_len);
 332         isl_int_mul(p[0], p[0], subs[0]);
 333 }
 334
 335 uint32_t isl_seq_get_hash(isl_int *p, unsigned len)
 336 {
 337         uint32_t hash = isl_hash_init();
 338
 339         return isl_seq_hash(p, len, hash);
 340 }
 341
 342 uint32_t isl_seq_get_hash_bits(isl_int *p, unsigned len, unsigned bits)
 343 {
 344         uint32_t hash;
 345
 346         hash = isl_seq_get_hash(p, len);
 347         return isl_hash_bits(hash, bits);
 348 }
 349
 350 void isl_seq_dump(isl_int *p, unsigned len)
 351 {
 352         int i;
 353
 354         for (i = 0; i < len; ++i) {
 355                 if (i)
 356                         fprintf(stderr, " ");
 357                 isl_int_print(stderr, p[i], 0);
 358         }
 359         fprintf(stderr, "\n");
 360 }