224 lines · c
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 of82 * 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 small168 * 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 least196 * 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