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 } 364