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