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