1#include <stdlib.h>
2#include <string.h>
3
4#include <isl_int.h>
5
6extern int isl_sioimath_decode(isl_sioimath val, int32_t *small, mp_int *big);
7extern int isl_sioimath_decode_big(isl_sioimath val, mp_int *big);
8extern int isl_sioimath_decode_small(isl_sioimath val, int32_t *small);
9
10extern isl_sioimath isl_sioimath_encode_small(int32_t val);
11extern isl_sioimath isl_sioimath_encode_big(mp_int val);
12extern int isl_sioimath_is_small(isl_sioimath val);
13extern int isl_sioimath_is_big(isl_sioimath val);
14extern int32_t isl_sioimath_get_small(isl_sioimath val);
15extern mp_int isl_sioimath_get_big(isl_sioimath val);
16
17extern void isl_siomath_uint32_to_digits(uint32_t num, mp_digit *digits,
18	mp_size *used);
19extern void isl_siomath_ulong_to_digits(unsigned long num, mp_digit *digits,
20	mp_size *used);
21extern void isl_siomath_uint64_to_digits(uint64_t num, mp_digit *digits,
22	mp_size *used);
23
24extern mp_int isl_sioimath_bigarg_src(isl_sioimath arg,
25	isl_sioimath_scratchspace_t *scratch);
26extern mp_int isl_sioimath_siarg_src(signed long arg,
27	isl_sioimath_scratchspace_t *scratch);
28extern mp_int isl_sioimath_si64arg_src(int64_t arg,
29	isl_sioimath_scratchspace_t *scratch);
30extern mp_int isl_sioimath_uiarg_src(unsigned long arg,
31	isl_sioimath_scratchspace_t *scratch);
32extern mp_int isl_sioimath_reinit_big(isl_sioimath_ptr ptr);
33extern void isl_sioimath_set_small(isl_sioimath_ptr ptr, int32_t val);
34extern void isl_sioimath_set_int32(isl_sioimath_ptr ptr, int32_t val);
35extern void isl_sioimath_set_int64(isl_sioimath_ptr ptr, int64_t val);
36extern void isl_sioimath_promote(isl_sioimath_ptr dst);
37extern void isl_sioimath_try_demote(isl_sioimath_ptr dst);
38
39extern void isl_sioimath_init(isl_sioimath_ptr dst);
40extern void isl_sioimath_clear(isl_sioimath_ptr dst);
41extern void isl_sioimath_set(isl_sioimath_ptr dst, isl_sioimath_src val);
42extern void isl_sioimath_set_si(isl_sioimath_ptr dst, long val);
43extern void isl_sioimath_set_ui(isl_sioimath_ptr dst, unsigned long val);
44extern int isl_sioimath_fits_slong(isl_sioimath_src val);
45extern long isl_sioimath_get_si(isl_sioimath_src val);
46extern int isl_sioimath_fits_ulong(isl_sioimath_src val);
47extern unsigned long isl_sioimath_get_ui(isl_sioimath_src val);
48extern double isl_sioimath_get_d(isl_sioimath_src val);
49extern char *isl_sioimath_get_str(isl_sioimath_src val);
50extern void isl_sioimath_abs(isl_sioimath_ptr dst, isl_sioimath_src arg);
51extern void isl_sioimath_neg(isl_sioimath_ptr dst, isl_sioimath_src arg);
52extern void isl_sioimath_swap(isl_sioimath_ptr lhs, isl_sioimath_ptr rhs);
53extern void isl_sioimath_add_ui(isl_sioimath_ptr dst, isl_sioimath lhs,
54	unsigned long rhs);
55extern void isl_sioimath_sub_ui(isl_sioimath_ptr dst, isl_sioimath lhs,
56	unsigned long rhs);
57
58extern void isl_sioimath_add(isl_sioimath_ptr dst, isl_sioimath_src lhs,
59	isl_sioimath_src rhs);
60extern void isl_sioimath_sub(isl_sioimath_ptr dst, isl_sioimath_src lhs,
61	isl_sioimath_src rhs);
62extern void isl_sioimath_mul(isl_sioimath_ptr dst, isl_sioimath_src lhs,
63	isl_sioimath_src rhs);
64extern void isl_sioimath_mul_2exp(isl_sioimath_ptr dst, isl_sioimath lhs,
65	unsigned long rhs);
66extern void isl_sioimath_mul_si(isl_sioimath_ptr dst, isl_sioimath lhs,
67	signed long rhs);
68extern void isl_sioimath_mul_ui(isl_sioimath_ptr dst, isl_sioimath lhs,
69	unsigned long rhs);
70extern void isl_sioimath_pow_ui(isl_sioimath_ptr dst, isl_sioimath_src lhs,
71	unsigned long rhs);
72extern void isl_sioimath_addmul(isl_sioimath_ptr dst, isl_sioimath_src lhs,
73	isl_sioimath_src rhs);
74extern void isl_sioimath_addmul_ui(isl_sioimath_ptr dst, isl_sioimath_src lhs,
75	unsigned long rhs);
76extern void isl_sioimath_submul(isl_sioimath_ptr dst, isl_sioimath_src lhs,
77	isl_sioimath_src rhs);
78extern void isl_sioimath_submul_ui(isl_sioimath_ptr dst, isl_sioimath_src lhs,
79	unsigned long rhs);
80
81/* Implements the Euclidean algorithm to compute the greatest common divisor of
82 * two values in small representation.
83 */
84static uint32_t isl_sioimath_smallgcd(int32_t lhs, int32_t rhs)
85{
86	uint32_t dividend, divisor, remainder;
87
88	dividend = labs(lhs);
89	divisor = labs(rhs);
90	while (divisor) {
91		remainder = dividend % divisor;
92		dividend = divisor;
93		divisor = remainder;
94	}
95
96	return dividend;
97}
98
99/* Compute the greatest common divisor.
100 *
101 * Per GMP convention, gcd(0,0)==0 and otherwise always positive.
102 */
103void isl_sioimath_gcd(isl_sioimath_ptr dst, isl_sioimath_src lhs,
104	isl_sioimath_src rhs)
105{
106	int32_t lhssmall, rhssmall;
107	uint32_t smallgcd;
108	isl_sioimath_scratchspace_t scratchlhs, scratchrhs;
109
110	if (isl_sioimath_decode_small(lhs, &lhssmall) &&
111	    isl_sioimath_decode_small(rhs, &rhssmall)) {
112		smallgcd = isl_sioimath_smallgcd(lhssmall, rhssmall);
113		isl_sioimath_set_small(dst, smallgcd);
114		return;
115	}
116
117	impz_gcd(isl_sioimath_reinit_big(dst),
118	    isl_sioimath_bigarg_src(lhs, &scratchlhs),
119	    isl_sioimath_bigarg_src(rhs, &scratchrhs));
120	isl_sioimath_try_demote(dst);
121}
122
123/* Compute the lowest common multiple of two numbers.
124 */
125void isl_sioimath_lcm(isl_sioimath_ptr dst, isl_sioimath_src lhs,
126	isl_sioimath_src rhs)
127{
128	int32_t lhssmall, rhssmall;
129	uint32_t smallgcd;
130	uint64_t multiple;
131	isl_sioimath_scratchspace_t scratchlhs, scratchrhs;
132
133	if (isl_sioimath_decode_small(lhs, &lhssmall) &&
134	    isl_sioimath_decode_small(rhs, &rhssmall)) {
135		if (lhssmall == 0 || rhssmall == 0) {
136			isl_sioimath_set_small(dst, 0);
137			return;
138		}
139		smallgcd = isl_sioimath_smallgcd(lhssmall, rhssmall);
140		multiple = (uint64_t) abs(lhssmall) * (uint64_t) abs(rhssmall);
141		isl_sioimath_set_int64(dst, multiple / smallgcd);
142		return;
143	}
144
145	impz_lcm(isl_sioimath_reinit_big(dst),
146	    isl_sioimath_bigarg_src(lhs, &scratchlhs),
147	    isl_sioimath_bigarg_src(rhs, &scratchrhs));
148	isl_sioimath_try_demote(dst);
149}
150
151extern void isl_sioimath_tdiv_q(isl_sioimath_ptr dst, isl_sioimath_src lhs,
152	isl_sioimath_src rhs);
153extern void isl_sioimath_tdiv_q_ui(isl_sioimath_ptr dst, isl_sioimath_src lhs,
154	unsigned long rhs);
155extern void isl_sioimath_cdiv_q(isl_sioimath_ptr dst, isl_sioimath_src lhs,
156	isl_sioimath_src rhs);
157extern void isl_sioimath_cdiv_q_ui(isl_sioimath_ptr dst, isl_sioimath_src lhs,
158	unsigned long rhs);
159extern void isl_sioimath_fdiv_q(isl_sioimath_ptr dst, isl_sioimath_src lhs,
160	isl_sioimath_src rhs);
161extern void isl_sioimath_fdiv_q_ui(isl_sioimath_ptr dst, isl_sioimath_src lhs,
162	unsigned long rhs);
163extern void isl_sioimath_fdiv_r(isl_sioimath_ptr dst, isl_sioimath_src lhs,
164	isl_sioimath_src rhs);
165
166/* Parse a number from a string.
167 * If it has less than 10 characters then it will fit into the small
168 * representation (i.e. strlen("2147483647")). Otherwise, let IMath parse it.
169 */
170void isl_sioimath_read(isl_sioimath_ptr dst, const char *str)
171{
172	int32_t small;
173
174	if (strlen(str) < 10) {
175		small = strtol(str, NULL, 10);
176		isl_sioimath_set_small(dst, small);
177		return;
178	}
179
180	mp_int_read_string(isl_sioimath_reinit_big(dst), 10, str);
181	isl_sioimath_try_demote(dst);
182}
183
184extern int isl_sioimath_sgn(isl_sioimath_src arg);
185extern int isl_sioimath_cmp(isl_sioimath_src lhs, isl_sioimath_src rhs);
186extern int isl_sioimath_cmp_si(isl_sioimath_src lhs, signed long rhs);
187extern int isl_sioimath_abs_cmp(isl_sioimath_src lhs, isl_sioimath_src rhs);
188extern int isl_sioimath_is_divisible_by(isl_sioimath_src lhs,
189	isl_sioimath_src rhs);
190
191extern uint32_t isl_sioimath_hash(isl_sioimath_src arg, uint32_t hash);
192extern size_t isl_sioimath_sizeinbase(isl_sioimath_src arg, int base);
193extern void isl_sioimath_print(FILE *out, isl_sioimath_src i, int width);
194
195/* Print an isl_int to FILE*. Adds space padding to the left until at least
196 * width characters are printed.
197 */
198void isl_sioimath_print(FILE *out, isl_sioimath_src i, int width)
199{
200	size_t len;
201	int32_t small;
202	mp_int big;
203	char *buf;
204
205	if (isl_sioimath_decode_small(i, &small)) {
206		fprintf(out, "%*" PRIi32, width, small);
207		return;
208	}
209
210	big = isl_sioimath_get_big(i);
211	len = mp_int_string_len(big, 10);
212	buf = malloc(len);
213	mp_int_to_string(big, 10, buf, len);
214	fprintf(out, "%*s", width, buf);
215	free(buf);
216}
217
218/* Print a number to stdout. Meant for debugging.
219 */
220void isl_sioimath_dump(isl_sioimath_src arg)
221{
222	isl_sioimath_print(stdout, arg, 0);
223}
224