isl_int_sioimath.c

   1 #include <malloc.h>
   2 #include <string.h>
   3
   4 #include <isl_int.h>
   5
   6 extern int isl_sioimath_decode(isl_sioimath val, int32_t *small, mp_int *big);
   7 extern int isl_sioimath_decode_big(isl_sioimath val, mp_int *big);
   8 extern int isl_sioimath_decode_small(isl_sioimath val, int32_t *small);
   9
  10 extern isl_sioimath isl_sioimath_encode_small(int32_t val);
  11 extern isl_sioimath isl_sioimath_encode_big(mp_int val);
  12 extern int isl_sioimath_is_small(isl_sioimath val);
  13 extern int isl_sioimath_is_big(isl_sioimath val);
  14 extern int32_t isl_sioimath_get_small(isl_sioimath val);
  15 extern mp_int isl_sioimath_get_big(isl_sioimath val);
  16
  17 extern void isl_siomath_uint32_to_digits(uint32_t num, mp_digit *digits,
  18         mp_size *used);
  19 extern void isl_siomath_ulong_to_digits(unsigned long num, mp_digit *digits,
  20         mp_size *used);
  21 extern void isl_siomath_uint64_to_digits(uint64_t num, mp_digit *digits,
  22         mp_size *used);
  23
  24 extern mp_int isl_sioimath_bigarg_src(isl_sioimath arg,
  25         isl_sioimath_scratchspace_t *scratch);
  26 extern mp_int isl_sioimath_siarg_src(signed long arg,
  27         isl_sioimath_scratchspace_t *scratch);
  28 extern mp_int isl_sioimath_si64arg_src(int64_t arg,
  29         isl_sioimath_scratchspace_t *scratch);
  30 extern mp_int isl_sioimath_uiarg_src(unsigned long arg,
  31         isl_sioimath_scratchspace_t *scratch);
  32 extern mp_int isl_sioimath_reinit_big(isl_sioimath_ptr ptr);
  33 extern void isl_sioimath_set_small(isl_sioimath_ptr ptr, int32_t val);
  34 extern void isl_sioimath_set_int32(isl_sioimath_ptr ptr, int32_t val);
  35 extern void isl_sioimath_set_int64(isl_sioimath_ptr ptr, int64_t val);
  36 extern void isl_sioimath_promote(isl_sioimath_ptr dst);
  37 extern void isl_sioimath_try_demote(isl_sioimath_ptr dst);
  38
  39 extern void isl_sioimath_init(isl_sioimath_ptr dst);
  40 extern void isl_sioimath_clear(isl_sioimath_ptr dst);
  41 extern void isl_sioimath_set(isl_sioimath_ptr dst, isl_sioimath_src val);
  42 extern void isl_sioimath_set_si(isl_sioimath_ptr dst, long val);
  43 extern void isl_sioimath_set_ui(isl_sioimath_ptr dst, unsigned long val);
  44 extern int isl_sioimath_fits_slong(isl_sioimath_src val);
  45 extern long isl_sioimath_get_si(isl_sioimath_src val);
  46 extern int isl_sioimath_fits_ulong(isl_sioimath_src val);
  47 extern unsigned long isl_sioimath_get_ui(isl_sioimath_src val);
  48 extern double isl_sioimath_get_d(isl_sioimath_src val);
  49 extern char *isl_sioimath_get_str(isl_sioimath_src val);
  50 extern void isl_sioimath_abs(isl_sioimath_ptr dst, isl_sioimath_src arg);
  51 extern void isl_sioimath_neg(isl_sioimath_ptr dst, isl_sioimath_src arg);
  52 extern void isl_sioimath_swap(isl_sioimath_ptr lhs, isl_sioimath_ptr rhs);
  53 extern void isl_sioimath_add_ui(isl_sioimath_ptr dst, isl_sioimath lhs,
  54         unsigned long rhs);
  55 extern void isl_sioimath_sub_ui(isl_sioimath_ptr dst, isl_sioimath lhs,
  56         unsigned long rhs);
  57
  58 extern void isl_sioimath_add(isl_sioimath_ptr dst, isl_sioimath_src lhs,
  59         isl_sioimath_src rhs);
  60 extern void isl_sioimath_sub(isl_sioimath_ptr dst, isl_sioimath_src lhs,
  61         isl_sioimath_src rhs);
  62 extern void isl_sioimath_mul(isl_sioimath_ptr dst, isl_sioimath_src lhs,
  63         isl_sioimath_src rhs);
  64 extern void isl_sioimath_mul_2exp(isl_sioimath_ptr dst, isl_sioimath lhs,
  65         unsigned long rhs);
  66 extern void isl_sioimath_mul_si(isl_sioimath_ptr dst, isl_sioimath lhs,
  67         signed long rhs);
  68 extern void isl_sioimath_mul_ui(isl_sioimath_ptr dst, isl_sioimath lhs,
  69         unsigned long rhs);
  70 extern void isl_sioimath_pow_ui(isl_sioimath_ptr dst, isl_sioimath_src lhs,
  71         unsigned long rhs);
  72 extern void isl_sioimath_addmul(isl_sioimath_ptr dst, isl_sioimath_src lhs,
  73         isl_sioimath_src rhs);
  74 extern void isl_sioimath_addmul_ui(isl_sioimath_ptr dst, isl_sioimath_src lhs,
  75         unsigned long rhs);
  76 extern void isl_sioimath_submul(isl_sioimath_ptr dst, isl_sioimath_src lhs,
  77         isl_sioimath_src rhs);
  78 extern 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  */
  84 static 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  */
 103 inline void 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  */
 125 void 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
 151 extern void isl_sioimath_tdiv_q(isl_sioimath_ptr dst, isl_sioimath_src lhs,
 152         isl_sioimath_src rhs);
 153 extern void isl_sioimath_tdiv_q_ui(isl_sioimath_ptr dst, isl_sioimath_src lhs,
 154         unsigned long rhs);
 155 extern void isl_sioimath_cdiv_q(isl_sioimath_ptr dst, isl_sioimath_src lhs,
 156         isl_sioimath_src rhs);
 157 extern void isl_sioimath_fdiv_q(isl_sioimath_ptr dst, isl_sioimath_src lhs,
 158         isl_sioimath_src rhs);
 159 extern void isl_sioimath_fdiv_q_ui(isl_sioimath_ptr dst, isl_sioimath_src lhs,
 160         unsigned long rhs);
 161 extern void isl_sioimath_fdiv_r(isl_sioimath_ptr dst, isl_sioimath_src lhs,
 162         isl_sioimath_src rhs);
 163
 164 /* Parse a number from a string.
 165  * If it has less than 10 characters then it will fit into the small
 166  * representation (i.e. strlen("2147483647")). Otherwise, let IMath parse it.
 167  */
 168 void isl_sioimath_read(isl_sioimath_ptr dst, const char *str)
 169 {
 170         int32_t small;
 171
 172         if (strlen(str) < 10) {
 173                 small = strtol(str, NULL, 10);
 174                 isl_sioimath_set_small(dst, small);
 175                 return;
 176         }
 177
 178         mp_int_read_string(isl_sioimath_reinit_big(dst), 10, str);
 179         isl_sioimath_try_demote(dst);
 180 }
 181
 182 extern int isl_sioimath_sgn(isl_sioimath_src arg);
 183 extern int isl_sioimath_cmp(isl_sioimath_src lhs, isl_sioimath_src rhs);
 184 extern int isl_sioimath_cmp_si(isl_sioimath_src lhs, signed long rhs);
 185 extern int isl_sioimath_abs_cmp(isl_sioimath_src lhs, isl_sioimath_src rhs);
 186 extern int isl_sioimath_is_divisible_by(isl_sioimath_src lhs,
 187         isl_sioimath_src rhs);
 188
 189 extern uint32_t isl_sioimath_hash(isl_sioimath_src arg, uint32_t hash);
 190 extern size_t isl_sioimath_sizeinbase(isl_sioimath_src arg, int base);
 191 extern void isl_sioimath_print(FILE *out, isl_sioimath_src i, int width);
 192
 193 /* Print an isl_int to FILE*. Adds space padding to the left until at least
 194  * width characters are printed.
 195  */
 196 void isl_sioimath_print(FILE *out, isl_sioimath_src i, int width)
 197 {
 198         size_t len;
 199         int32_t small;
 200         mp_int big;
 201         char *buf;
 202
 203         if (isl_sioimath_decode_small(i, &small)) {
 204                 fprintf(out, "%*" PRIi32, width, small);
 205                 return;
 206         }
 207
 208         big = isl_sioimath_get_big(i);
 209         len = mp_int_string_len(big, 10);
 210         buf = malloc(len);
 211         mp_int_to_string(big, 10, buf, len);
 212         fprintf(out, "%*s", width, buf);
 213         free(buf);
 214 }
 215
 216 /* Print a number to stdout. Meant for debugging.
 217  */
 218 void isl_sioimath_dump(isl_sioimath_src arg)
 219 {
 220         isl_sioimath_print(stdout, arg, 0);
 221 }