Home | History | Annotate | Line # | Download | only in dist 
      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