1#include <stdlib.h>
2#include "../include/cloog/cloog.h"
3
4#define ALLOC(type) (type*)malloc(sizeof(type))
5#define ALLOCN(type,n) (type*)malloc((n)*sizeof(type))
6
7#if defined(CLOOG_INT_INT) || \
8    defined(CLOOG_INT_LONG) || \
9    defined(CLOOG_INT_LONG_LONG)
10
11cloog_int_t cloog_gcd(cloog_int_t a, cloog_int_t b)
12{
13	while (a) {
14		cloog_int_t t = b % a;
15		b = a;
16		a = t;
17	}
18	if (b < 0)
19		b = -b;
20	return b;
21}
22
23#endif
24
25struct cloog_vec *cloog_vec_alloc(unsigned size)
26{
27	int i;
28	struct cloog_vec *vec;
29
30	vec = ALLOC(struct cloog_vec);
31	if (!vec)
32		return NULL;
33
34	vec->p = ALLOCN(cloog_int_t, size);
35	if (!vec->p)
36		goto error;
37	vec->size = size;
38
39	for (i = 0; i < size; ++i)
40		cloog_int_init(vec->p[i]);
41
42	return vec;
43error:
44	free(vec);
45	return NULL;
46}
47
48void cloog_vec_free(struct cloog_vec *vec)
49{
50	int i;
51
52	if (!vec)
53		return;
54
55	for (i = 0; i < vec->size; ++i)
56		cloog_int_clear(vec->p[i]);
57	free(vec->p);
58	free(vec);
59}
60
61void cloog_vec_dump(struct cloog_vec *vec)
62{
63	int i;
64
65	for (i = 0; i < vec->size; ++i) {
66		cloog_int_print(stderr, vec->p[i]);
67		fprintf(stderr, " ");
68	}
69	fprintf(stderr, "\n");
70}
71
72int cloog_seq_first_non_zero(cloog_int_t *p, unsigned len)
73{
74	int i;
75
76	for (i = 0; i < len; ++i)
77		if (!cloog_int_is_zero(p[i]))
78			return i;
79	return -1;
80}
81
82void cloog_seq_neg(cloog_int_t *dst, cloog_int_t *src, unsigned len)
83{
84	int i;
85	for (i = 0; i < len; ++i)
86		cloog_int_neg(dst[i], src[i]);
87}
88
89void cloog_seq_cpy(cloog_int_t *dst, cloog_int_t *src, unsigned len)
90{
91	int i;
92	for (i = 0; i < len; ++i)
93		cloog_int_set(dst[i], src[i]);
94}
95
96static void cloog_seq_scale_down(cloog_int_t *dst, cloog_int_t *src, cloog_int_t m, unsigned len)
97{
98	int i;
99	for (i = 0; i < len; ++i)
100		cloog_int_divexact(dst[i], src[i], m);
101}
102
103void cloog_seq_combine(cloog_int_t *dst, cloog_int_t m1, cloog_int_t *src1,
104			cloog_int_t m2, cloog_int_t *src2, unsigned len)
105{
106	int i;
107	cloog_int_t tmp;
108
109	cloog_int_init(tmp);
110	for (i = 0; i < len; ++i) {
111		cloog_int_mul(tmp, m1, src1[i]);
112		cloog_int_addmul(tmp, m2, src2[i]);
113		cloog_int_set(dst[i], tmp);
114	}
115	cloog_int_clear(tmp);
116}
117
118static int cloog_seq_abs_min_non_zero(cloog_int_t *p, unsigned len)
119{
120	int i, min = cloog_seq_first_non_zero(p, len);
121	if (min < 0)
122		return -1;
123	for (i = min + 1; i < len; ++i) {
124		if (cloog_int_is_zero(p[i]))
125			continue;
126		if (cloog_int_abs_lt(p[i], p[min]))
127			min = i;
128	}
129	return min;
130}
131
132void cloog_seq_gcd(cloog_int_t *p, unsigned len, cloog_int_t *gcd)
133{
134	int i, min = cloog_seq_abs_min_non_zero(p, len);
135
136	if (min < 0) {
137		cloog_int_set_si(*gcd, 0);
138		return;
139	}
140	cloog_int_abs(*gcd, p[min]);
141	for (i = 0; cloog_int_cmp_si(*gcd, 1) > 0 && i < len; ++i) {
142		if (i == min)
143			continue;
144		if (cloog_int_is_zero(p[i]))
145			continue;
146		cloog_int_gcd(*gcd, *gcd, p[i]);
147	}
148}
149
150int cloog_seq_is_neg(cloog_int_t *p1, cloog_int_t *p2, unsigned len)
151{
152	int i;
153
154	for (i = 0; i < len; ++i) {
155		if (cloog_int_abs_ne(p1[i], p2[i]))
156			return 0;
157		if (cloog_int_is_zero(p1[i]))
158			continue;
159		if (cloog_int_eq(p1[i], p2[i]))
160			return 0;
161	}
162	return 1;
163}
164
165void cloog_seq_normalize(cloog_int_t *p, unsigned len)
166{
167	cloog_int_t gcd;
168
169	if (len == 0)
170		return;
171
172	cloog_int_init(gcd);
173	cloog_seq_gcd(p, len, &gcd);
174	if (!cloog_int_is_zero(gcd) && !cloog_int_is_one(gcd))
175		cloog_seq_scale_down(p, p, gcd, len);
176	cloog_int_clear(gcd);
177}
178