#include <string.h>

#include <assert.h>

#include "py/mpz.h"

#if MICROPY_LONGINT_IMPL == MICROPY_LONGINT_IMPL_MPZ

#define DIG_SIZE (MPZ_DIG_SIZE)

#define DIG_MASK ((MPZ_LONG_1 << DIG_SIZE) - 1)

#define DIG_MSB (MPZ_LONG_1 << (DIG_SIZE - 1))

#define DIG_BASE (MPZ_LONG_1 << DIG_SIZE)

STATIC int mpn_cmp(const mpz_dig_t *idig, mp_uint_t ilen, const mpz_dig_t *jdig, mp_uint_t jlen) {

if (ilen < jlen) { return -1; }

if (ilen > jlen) { return 1; }

for (idig += ilen, jdig += ilen; ilen > 0; --ilen) {

mpz_dbl_dig_signed_t cmp = (mpz_dbl_dig_t)*(--idig) - (mpz_dbl_dig_t)*(--jdig);

if (cmp < 0) { return -1; }

if (cmp > 0) { return 1; }

}

return 0;

}

STATIC mp_uint_t mpn_shl(mpz_dig_t *idig, mpz_dig_t *jdig, mp_uint_t jlen, mp_uint_t n) {

mp_uint_t n_whole = (n + DIG_SIZE - 1) / DIG_SIZE;

mp_uint_t n_part = n % DIG_SIZE;

if (n_part == 0) {

n_part = DIG_SIZE;

}

// start from the high end of the digit arrays

idig += jlen + n_whole - 1;

jdig += jlen - 1;

// shift the digits

mpz_dbl_dig_t d = 0;

for (mp_uint_t i = jlen; i > 0; i--, idig--, jdig--) {

d |= *jdig;

*idig = (d >> (DIG_SIZE - n_part)) & DIG_MASK;

d <<= DIG_SIZE;

}

// store remaining bits

*idig = (d >> (DIG_SIZE - n_part)) & DIG_MASK;

idig -= n_whole - 1;

memset(idig, 0, (n_whole - 1) * sizeof(mpz_dig_t));

// work out length of result

jlen += n_whole;

while (jlen != 0 && idig[jlen - 1] == 0) {

jlen--;

}

// return length of result

return jlen;

}

STATIC mp_uint_t mpn_shr(mpz_dig_t *idig, mpz_dig_t *jdig, mp_uint_t jlen, mp_uint_t n) {

mp_uint_t n_whole = n / DIG_SIZE;

mp_uint_t n_part = n % DIG_SIZE;

if (n_whole >= jlen) {

return 0;

}

jdig += n_whole;

jlen -= n_whole;

for (mp_uint_t i = jlen; i > 0; i--, idig++, jdig++) {

mpz_dbl_dig_t d = *jdig;

if (i > 1) {

d |= (mpz_dbl_dig_t)jdig[1] << DIG_SIZE;

}

d >>= n_part;

*idig = d & DIG_MASK;

}

if (idig[-1] == 0) {

jlen--;

}

return jlen;

}

STATIC mp_uint_t mpn_add(mpz_dig_t *idig, const mpz_dig_t *jdig, mp_uint_t jlen, const mpz_dig_t *kdig, mp_uint_t klen) {

mpz_dig_t *oidig = idig;

mpz_dbl_dig_t carry = 0;

jlen -= klen;

for (; klen > 0; --klen, ++idig, ++jdig, ++kdig) {

carry += (mpz_dbl_dig_t)*jdig + (mpz_dbl_dig_t)*kdig;

*idig = carry & DIG_MASK;

carry >>= DIG_SIZE;

}

for (; jlen > 0; --jlen, ++idig, ++jdig) {

carry += *jdig;

*idig = carry & DIG_MASK;

carry >>= DIG_SIZE;

}

if (carry != 0) {

*idig++ = carry;

}

return idig - oidig;

}

STATIC mp_uint_t mpn_sub(mpz_dig_t *idig, const mpz_dig_t *jdig, mp_uint_t jlen, const mpz_dig_t *kdig, mp_uint_t klen) {

mpz_dig_t *oidig = idig;

mpz_dbl_dig_signed_t borrow = 0;

jlen -= klen;

for (; klen > 0; --klen, ++idig, ++jdig, ++kdig) {

borrow += (mpz_dbl_dig_t)*jdig - (mpz_dbl_dig_t)*kdig;

*idig = borrow & DIG_MASK;

borrow >>= DIG_SIZE;

}

for (; jlen > 0; --jlen, ++idig, ++jdig) {

borrow += *jdig;

*idig = borrow & DIG_MASK;

borrow >>= DIG_SIZE;

}

for (--idig; idig >= oidig && *idig == 0; --idig) {

}

return idig + 1 - oidig;

}

STATIC mp_uint_t mpn_remove_trailing_zeros(mpz_dig_t *oidig, mpz_dig_t *idig) {

for (--idig; idig >= oidig && *idig == 0; --idig) {

}

return idig + 1 - oidig;

}

#if MICROPY_OPT_MPZ_BITWISE

STATIC mp_uint_t mpn_and(mpz_dig_t *idig, const mpz_dig_t *jdig, const mpz_dig_t *kdig, mp_uint_t klen) {

mpz_dig_t *oidig = idig;

for (; klen > 0; --klen, ++idig, ++jdig, ++kdig) {

*idig = *jdig & *kdig;

}

return mpn_remove_trailing_zeros(oidig, idig);

}

STATIC mp_uint_t mpn_and_neg(mpz_dig_t *idig, const mpz_dig_t *jdig, mp_uint_t jlen, const mpz_dig_t *kdig, mp_uint_t klen,

mpz_dbl_dig_t carryi, mpz_dbl_dig_t carryj, mpz_dbl_dig_t carryk) {

mpz_dig_t *oidig = idig;

mpz_dig_t imask = (0 == carryi) ? 0 : DIG_MASK;

mpz_dig_t jmask = (0 == carryj) ? 0 : DIG_MASK;

mpz_dig_t kmask = (0 == carryk) ? 0 : DIG_MASK;

for (; jlen > 0; ++idig, ++jdig) {

carryj += *jdig ^ jmask;

carryk += (--klen <= --jlen) ? (*kdig++ ^ kmask) : kmask;

carryi += ((carryj & carryk) ^ imask) & DIG_MASK;

*idig = carryi & DIG_MASK;

carryk >>= DIG_SIZE;

carryj >>= DIG_SIZE;

carryi >>= DIG_SIZE;

}

if (0 != carryi) {

*idig++ = carryi;

}

return mpn_remove_trailing_zeros(oidig, idig);

}

#if MICROPY_OPT_MPZ_BITWISE

STATIC mp_uint_t mpn_or(mpz_dig_t *idig, const mpz_dig_t *jdig, mp_uint_t jlen, const mpz_dig_t *kdig, mp_uint_t klen) {

mpz_dig_t *oidig = idig;

jlen -= klen;

for (; klen > 0; --klen, ++idig, ++jdig, ++kdig) {

*idig = *jdig | *kdig;

}

for (; jlen > 0; --jlen, ++idig, ++jdig) {

*idig = *jdig;

}

return idig - oidig;

}

#if MICROPY_OPT_MPZ_BITWISE

STATIC mp_uint_t mpn_or_neg(mpz_dig_t *idig, const mpz_dig_t *jdig, mp_uint_t jlen, const mpz_dig_t *kdig, mp_uint_t klen,

mpz_dbl_dig_t carryj, mpz_dbl_dig_t carryk) {

mpz_dig_t *oidig = idig;

mpz_dbl_dig_t carryi = 1;

mpz_dig_t jmask = (0 == carryj) ? 0 : DIG_MASK;

mpz_dig_t kmask = (0 == carryk) ? 0 : DIG_MASK;

for (; jlen > 0; ++idig, ++jdig) {

carryj += *jdig ^ jmask;

carryk += (--klen <= --jlen) ? (*kdig++ ^ kmask) : kmask;

carryi += ((carryj | carryk) ^ DIG_MASK) & DIG_MASK;

*idig = carryi & DIG_MASK;

carryk >>= DIG_SIZE;

carryj >>= DIG_SIZE;

carryi >>= DIG_SIZE;

}

if (0 != carryi) {

*idig++ = carryi;

}

return mpn_remove_trailing_zeros(oidig, idig);

}

STATIC mp_uint_t mpn_or_neg(mpz_dig_t *idig, const mpz_dig_t *jdig, mp_uint_t jlen, const mpz_dig_t *kdig, mp_uint_t klen,

mpz_dbl_dig_t carryi, mpz_dbl_dig_t carryj, mpz_dbl_dig_t carryk) {

mpz_dig_t *oidig = idig;

mpz_dig_t imask = (0 == carryi) ? 0 : DIG_MASK;

mpz_dig_t jmask = (0 == carryj) ? 0 : DIG_MASK;

mpz_dig_t kmask = (0 == carryk) ? 0 : DIG_MASK;

for (; jlen > 0; ++idig, ++jdig) {

carryj += *jdig ^ jmask;

carryk += (--klen <= --jlen) ? (*kdig++ ^ kmask) : kmask;

carryi += ((carryj | carryk) ^ imask) & DIG_MASK;

*idig = carryi & DIG_MASK;

carryk >>= DIG_SIZE;

carryj >>= DIG_SIZE;

carryi >>= DIG_SIZE;

}

if (0 != carryi) {

*idig++ = carryi;

}

return mpn_remove_trailing_zeros(oidig, idig);

}

#if MICROPY_OPT_MPZ_BITWISE

STATIC mp_uint_t mpn_xor(mpz_dig_t *idig, const mpz_dig_t *jdig, mp_uint_t jlen, const mpz_dig_t *kdig, mp_uint_t klen) {

mpz_dig_t *oidig = idig;

jlen -= klen;

for (; klen > 0; --klen, ++idig, ++jdig, ++kdig) {

*idig = *jdig ^ *kdig;

}

for (; jlen > 0; --jlen, ++idig, ++jdig) {

*idig = *jdig;

}

return mpn_remove_trailing_zeros(oidig, idig);

}

STATIC mp_uint_t mpn_xor_neg(mpz_dig_t *idig, const mpz_dig_t *jdig, mp_uint_t jlen, const mpz_dig_t *kdig, mp_uint_t klen,

mpz_dbl_dig_t carryi, mpz_dbl_dig_t carryj, mpz_dbl_dig_t carryk) {

mpz_dig_t *oidig = idig;

for (; jlen > 0; ++idig, ++jdig) {

carryj += *jdig + DIG_MASK;

carryk += (--klen <= --jlen) ? (*kdig++ + DIG_MASK) : DIG_MASK;

carryi += (carryj ^ carryk) & DIG_MASK;

*idig = carryi & DIG_MASK;

carryk >>= DIG_SIZE;

carryj >>= DIG_SIZE;

carryi >>= DIG_SIZE;

}

if (0 != carryi) {

*idig++ = carryi;

}

return mpn_remove_trailing_zeros(oidig, idig);

}

STATIC mp_uint_t mpn_mul_dig_add_dig(mpz_dig_t *idig, mp_uint_t ilen, mpz_dig_t dmul, mpz_dig_t dadd) {

mpz_dig_t *oidig = idig;

mpz_dbl_dig_t carry = dadd;

for (; ilen > 0; --ilen, ++idig) {

carry += (mpz_dbl_dig_t)*idig * (mpz_dbl_dig_t)dmul; // will never overflow so long as DIG_SIZE <= 8*sizeof(mpz_dbl_dig_t)/2

*idig = carry & DIG_MASK;

carry >>= DIG_SIZE;

}

if (carry != 0) {

*idig++ = carry;

}

return idig - oidig;

}

STATIC mp_uint_t mpn_mul(mpz_dig_t *idig, mpz_dig_t *jdig, mp_uint_t jlen, mpz_dig_t *kdig, mp_uint_t klen) {

mpz_dig_t *oidig = idig;

mp_uint_t ilen = 0;

for (; klen > 0; --klen, ++idig, ++kdig) {

mpz_dig_t *id = idig;

mpz_dbl_dig_t carry = 0;

mp_uint_t jl = jlen;

for (mpz_dig_t *jd = jdig; jl > 0; --jl, ++jd, ++id) {

carry += (mpz_dbl_dig_t)*id + (mpz_dbl_dig_t)*jd * (mpz_dbl_dig_t)*kdig; // will never overflow so long as DIG_SIZE <= 8*sizeof(mpz_dbl_dig_t)/2

*id = carry & DIG_MASK;

carry >>= DIG_SIZE;

}

if (carry != 0) {

*id++ = carry;

}

ilen = id - oidig;

}

return ilen;

}

STATIC void mpn_div(mpz_dig_t *num_dig, mp_uint_t *num_len, mpz_dig_t *den_dig, mp_uint_t den_len, mpz_dig_t *quo_dig, mp_uint_t *quo_len) {

mpz_dig_t *orig_num_dig = num_dig;

mpz_dig_t *orig_quo_dig = quo_dig;

mpz_dig_t norm_shift = 0;

mpz_dbl_dig_t lead_den_digit;

// handle simple cases

{

int cmp = mpn_cmp(num_dig, *num_len, den_dig, den_len);

if (cmp == 0) {

*num_len = 0;

quo_dig[0] = 1;

*quo_len = 1;

return;

} else if (cmp < 0) {

// numerator remains the same

*quo_len = 0;

return;

}

}

// count number of leading zeros in leading digit of denominator

{

mpz_dig_t d = den_dig[den_len - 1];

while ((d & DIG_MSB) == 0) {

d <<= 1;

++norm_shift;

}

}

// normalise denomenator (leading bit of leading digit is 1)

for (mpz_dig_t *den = den_dig, carry = 0; den < den_dig + den_len; ++den) {

mpz_dig_t d = *den;

*den = ((d << norm_shift) | carry) & DIG_MASK;

carry = d >> (DIG_SIZE - norm_shift);

}

// now need to shift numerator by same amount as denominator

// first, increase length of numerator in case we need more room to shift

num_dig[*num_len] = 0;

++(*num_len);

for (mpz_dig_t *num = num_dig, carry = 0; num < num_dig + *num_len; ++num) {

mpz_dig_t n = *num;

*num = ((n << norm_shift) | carry) & DIG_MASK;

carry = n >> (DIG_SIZE - norm_shift);

}

// cache the leading digit of the denominator

lead_den_digit = den_dig[den_len - 1];

// point num_dig to last digit in numerator

num_dig += *num_len - 1;

// calculate number of digits in quotient

*quo_len = *num_len - den_len;

// point to last digit to store for quotient

quo_dig += *quo_len - 1;

// keep going while we have enough digits to divide

while (*num_len > den_len) {

mpz_dbl_dig_t quo = ((mpz_dbl_dig_t)*num_dig << DIG_SIZE) | num_dig[-1];

// get approximate quotient

quo /= lead_den_digit;

// Multiply quo by den and subtract from num to get remainder.

// We have different code here to handle different compile-time

// configurations of mpz:

//

// 1. DIG_SIZE is stricly less than half the number of bits

// available in mpz_dbl_dig_t. In this case we can use a

// slightly more optimal (in time and space) routine that

// uses the extra bits in mpz_dbl_dig_signed_t to store a

// sign bit.

//

// 2. DIG_SIZE is exactly half the number of bits available in

// mpz_dbl_dig_t. In this (common) case we need to be careful

// not to overflow the borrow variable. And the shifting of

// borrow needs some special logic (it's a shift right with

// round up).

if (DIG_SIZE < 8 * sizeof(mpz_dbl_dig_t) / 2) {

mpz_dbl_dig_signed_t borrow = 0;

for (mpz_dig_t *n = num_dig - den_len, *d = den_dig; n < num_dig; ++n, ++d) {

borrow += (mpz_dbl_dig_t)*n - (mpz_dbl_dig_t)quo * (mpz_dbl_dig_t)*d; // will overflow if DIG_SIZE >= 8*sizeof(mpz_dbl_dig_t)/2

*n = borrow & DIG_MASK;

borrow >>= DIG_SIZE;

}

borrow += *num_dig; // will overflow if DIG_SIZE >= 8*sizeof(mpz_dbl_dig_t)/2

*num_dig = borrow & DIG_MASK;

borrow >>= DIG_SIZE;

// adjust quotient if it is too big

for (; borrow != 0; --quo) {

mpz_dbl_dig_t carry = 0;

for (mpz_dig_t *n = num_dig - den_len, *d = den_dig; n < num_dig; ++n, ++d) {

carry += (mpz_dbl_dig_t)*n + (mpz_dbl_dig_t)*d;

*n = carry & DIG_MASK;

carry >>= DIG_SIZE;

}

carry += *num_dig;

*num_dig = carry & DIG_MASK;

carry >>= DIG_SIZE;

borrow += carry;

}

} else { // DIG_SIZE == 8 * sizeof(mpz_dbl_dig_t) / 2

mpz_dbl_dig_t borrow = 0;

for (mpz_dig_t *n = num_dig - den_len, *d = den_dig; n < num_dig; ++n, ++d) {

mpz_dbl_dig_t x = (mpz_dbl_dig_t)quo * (mpz_dbl_dig_t)(*d);

if (x >= *n || *n - x <= borrow) {

borrow += (mpz_dbl_dig_t)x - (mpz_dbl_dig_t)*n;

*n = (-borrow) & DIG_MASK;

borrow = (borrow >> DIG_SIZE) + ((borrow & DIG_MASK) == 0 ? 0 : 1); // shift-right with round-up

} else {

*n = ((mpz_dbl_dig_t)*n - (mpz_dbl_dig_t)x - (mpz_dbl_dig_t)borrow) & DIG_MASK;

borrow = 0;

}

}

if (borrow >= *num_dig) {

borrow -= (mpz_dbl_dig_t)*num_dig;

*num_dig = (-borrow) & DIG_MASK;

borrow = (borrow >> DIG_SIZE) + ((borrow & DIG_MASK) == 0 ? 0 : 1); // shift-right with round-up

} else {

*num_dig = (*num_dig - borrow) & DIG_MASK;

borrow = 0;

}

// adjust quotient if it is too big

for (; borrow != 0; --quo) {

mpz_dbl_dig_t carry = 0;

for (mpz_dig_t *n = num_dig - den_len, *d = den_dig; n < num_dig; ++n, ++d) {

carry += (mpz_dbl_dig_t)*n + (mpz_dbl_dig_t)*d;

*n = carry & DIG_MASK;

carry >>= DIG_SIZE;

}

carry += (mpz_dbl_dig_t)*num_dig;

*num_dig = carry & DIG_MASK;

carry >>= DIG_SIZE;

//assert(borrow >= carry); // enable this to check the logic

borrow -= carry;

}

}

// store this digit of the quotient

*quo_dig = quo & DIG_MASK;

--quo_dig;

// move down to next digit of numerator

--num_dig;

--(*num_len);

}

// unnormalise denomenator

for (mpz_dig_t *den = den_dig + den_len - 1, carry = 0; den >= den_dig; --den) {

mpz_dig_t d = *den;

*den = ((d >> norm_shift) | carry) & DIG_MASK;

carry = d << (DIG_SIZE - norm_shift);

}

// unnormalise numerator (remainder now)

for (mpz_dig_t *num = orig_num_dig + *num_len - 1, carry = 0; num >= orig_num_dig; --num) {

mpz_dig_t n = *num;

*num = ((n >> norm_shift) | carry) & DIG_MASK;

carry = n << (DIG_SIZE - norm_shift);

}

// strip trailing zeros

while (*quo_len > 0 && orig_quo_dig[*quo_len - 1] == 0) {

--(*quo_len);

}

while (*num_len > 0 && orig_num_dig[*num_len - 1] == 0) {

--(*num_len);

}

}

#define MIN_ALLOC (2)

STATIC const uint8_t log_base2_floor[] = {

0,

0, 1, 1, 2,

2, 2, 2, 3,

3, 3, 3, 3,

3, 3, 3, 4,

4, 4, 4, 4,

4, 4, 4, 4,

4, 4, 4, 4,

4, 4, 4, 5

};

void mpz_init_zero(mpz_t *z) {

z->neg = 0;

z->fixed_dig = 0;

z->alloc = 0;

z->len = 0;

z->dig = NULL;

}

void mpz_init_from_int(mpz_t *z, mp_int_t val) {

mpz_init_zero(z);

mpz_set_from_int(z, val);

}

void mpz_init_fixed_from_int(mpz_t *z, mpz_dig_t *dig, mp_uint_t alloc, mp_int_t val) {

z->neg = 0;

z->fixed_dig = 1;

z->alloc = alloc;

z->len = 0;

z->dig = dig;

mpz_set_from_int(z, val);

}

void mpz_deinit(mpz_t *z) {

if (z != NULL && !z->fixed_dig) {

m_del(mpz_dig_t, z->dig, z->alloc);

}

}

#if 0

these functions are unused

mpz_t *mpz_zero(void) {

mpz_t *z = m_new_obj(mpz_t);

mpz_init_zero(z);

return z;

}

mpz_t *mpz_from_int(mp_int_t val) {

mpz_t *z = mpz_zero();

mpz_set_from_int(z, val);

return z;

}

mpz_t *mpz_from_ll(long long val, bool is_signed) {

mpz_t *z = mpz_zero();

mpz_set_from_ll(z, val, is_signed);

return z;

}

#if MICROPY_PY_BUILTINS_FLOAT

mpz_t *mpz_from_float(mp_float_t val) {

mpz_t *z = mpz_zero();

mpz_set_from_float(z, val);

return z;

}

mpz_t *mpz_from_str(const char *str, mp_uint_t len, bool neg, mp_uint_t base) {

mpz_t *z = mpz_zero();

mpz_set_from_str(z, str, len, neg, base);

return z;

}

STATIC void mpz_free(mpz_t *z) {

if (z != NULL) {

m_del(mpz_dig_t, z->dig, z->alloc);

m_del_obj(mpz_t, z);

}

}

STATIC void mpz_need_dig(mpz_t *z, mp_uint_t need) {

if (need < MIN_ALLOC) {

need = MIN_ALLOC;

}

if (z->dig == NULL || z->alloc < need) {

if (z->fixed_dig) {

// cannot reallocate fixed buffers

assert(0);

return;

}

z->dig = m_renew(mpz_dig_t, z->dig, z->alloc, need);

z->alloc = need;

}

}

STATIC mpz_t *mpz_clone(const mpz_t *src) {

mpz_t *z = m_new_obj(mpz_t);

z->neg = src->neg;

z->fixed_dig = 0;

z->alloc = src->alloc;

z->len = src->len;

if (src->dig == NULL) {

z->dig = NULL;

} else {

z->dig = m_new(mpz_dig_t, z->alloc);

memcpy(z->dig, src->dig, src->alloc * sizeof(mpz_dig_t));

}

return z;

}

void mpz_set(mpz_t *dest, const mpz_t *src) {

mpz_need_dig(dest, src->len);

dest->neg = src->neg;

dest->len = src->len;

memcpy(dest->dig, src->dig, src->len * sizeof(mpz_dig_t));

}

void mpz_set_from_int(mpz_t *z, mp_int_t val) {

if (val == 0) {

z->len = 0;

return;

}

mpz_need_dig(z, MPZ_NUM_DIG_FOR_INT);

mp_uint_t uval;

if (val < 0) {

z->neg = 1;

uval = -val;

} else {

z->neg = 0;

uval = val;

}

z->len = 0;

while (uval > 0) {

z->dig[z->len++] = uval & DIG_MASK;

uval >>= DIG_SIZE;

}

}

void mpz_set_from_ll(mpz_t *z, long long val, bool is_signed) {

mpz_need_dig(z, MPZ_NUM_DIG_FOR_LL);

unsigned long long uval;

if (is_signed && val < 0) {

z->neg = 1;

uval = -val;

} else {

z->neg = 0;

uval = val;

}

z->len = 0;

while (uval > 0) {

z->dig[z->len++] = uval & DIG_MASK;

uval >>= DIG_SIZE;

}

}

#if MICROPY_PY_BUILTINS_FLOAT

void mpz_set_from_float(mpz_t *z, mp_float_t src) {

#if MICROPY_FLOAT_IMPL == MICROPY_FLOAT_IMPL_DOUBLE

typedef uint64_t mp_float_int_t;

#elif MICROPY_FLOAT_IMPL == MICROPY_FLOAT_IMPL_FLOAT

typedef uint32_t mp_float_int_t;

union {

mp_float_t f;

#if MP_ENDIANNESS_LITTLE

struct { mp_float_int_t frc:MP_FLOAT_FRAC_BITS, exp:MP_FLOAT_EXP_BITS, sgn:1; } p;

#else

struct { mp_float_int_t sgn:1, exp:MP_FLOAT_EXP_BITS, frc:MP_FLOAT_FRAC_BITS; } p;

#endif

} u = {src};

z->neg = u.p.sgn;

if (u.p.exp == 0) {

// value == 0 || value < 1

mpz_set_from_int(z, 0);

} else if (u.p.exp == ((1 << MP_FLOAT_EXP_BITS) - 1)) {

// u.p.frc == 0 indicates inf, else NaN

// should be handled by caller

mpz_set_from_int(z, 0);

} else {

const int adj_exp = (int)u.p.exp - MP_FLOAT_EXP_BIAS;

if (adj_exp < 0) {

// value < 1 , truncates to 0

mpz_set_from_int(z, 0);

} else if (adj_exp == 0) {

// 1 <= value < 2 , so truncates to 1

mpz_set_from_int(z, 1);

} else {

// 2 <= value

const int dig_cnt = (adj_exp + 1 + (DIG_SIZE - 1)) / DIG_SIZE;

const unsigned int rem = adj_exp % DIG_SIZE;

int dig_ind, shft;

mp_float_int_t frc = u.p.frc | ((mp_float_int_t)1 << MP_FLOAT_FRAC_BITS);

if (adj_exp < MP_FLOAT_FRAC_BITS) {

shft = 0;

dig_ind = 0;

frc >>= MP_FLOAT_FRAC_BITS - adj_exp;

} else {

shft = (rem - MP_FLOAT_FRAC_BITS) % DIG_SIZE;

dig_ind = (adj_exp - MP_FLOAT_FRAC_BITS) / DIG_SIZE;

}

mpz_need_dig(z, dig_cnt);

z->len = dig_cnt;

if (dig_ind != 0) {

memset(z->dig, 0, dig_ind * sizeof(mpz_dig_t));

}

if (shft != 0) {

z->dig[dig_ind++] = (frc << shft) & DIG_MASK;

frc >>= DIG_SIZE - shft;

}

#if DIG_SIZE < (MP_FLOAT_FRAC_BITS + 1)

while (dig_ind != dig_cnt) {

z->dig[dig_ind++] = frc & DIG_MASK;

frc >>= DIG_SIZE;

}

if (dig_ind != dig_cnt) {

z->dig[dig_ind] = frc;

}

}

}

}

mp_uint_t mpz_set_from_str(mpz_t *z, const char *str, mp_uint_t len, bool neg, mp_uint_t base) {

assert(base < 36);

const char *cur = str;

const char *top = str + len;

mpz_need_dig(z, len * 8 / DIG_SIZE + 1);

if (neg) {

z->neg = 1;

} else {

z->neg = 0;

}

z->len = 0;

for (; cur < top; ++cur) { // XXX UTF8 next char

//mp_uint_t v = char_to_numeric(cur#); // XXX UTF8 get char

mp_uint_t v = *cur;

if ('0' <= v && v <= '9') {

v -= '0';

} else if ('A' <= v && v <= 'Z') {

v -= 'A' - 10;

} else if ('a' <= v && v <= 'z') {

v -= 'a' - 10;

} else {

break;

}

if (v >= base) {

break;

}

z->len = mpn_mul_dig_add_dig(z->dig, z->len, base, v);

}

return cur - str;

}

bool mpz_is_zero(const mpz_t *z) {

return z->len == 0;

}

#if 0

these functions are unused

bool mpz_is_pos(const mpz_t *z) {

return z->len > 0 && z->neg == 0;

}

bool mpz_is_neg(const mpz_t *z) {

return z->len > 0 && z->neg != 0;

}

bool mpz_is_odd(const mpz_t *z) {

return z->len > 0 && (z->dig[0] & 1) != 0;

}

bool mpz_is_even(const mpz_t *z) {

return z->len == 0 || (z->dig[0] & 1) == 0;

}

int mpz_cmp(const mpz_t *z1, const mpz_t *z2) {

// to catch comparison of -0 with +0

if (z1->len == 0 && z2->len == 0) {

return 0;

}

int cmp = (int)z2->neg - (int)z1->neg;

if (cmp != 0) {

return cmp;

}

cmp = mpn_cmp(z1->dig, z1->len, z2->dig, z2->len);

if (z1->neg != 0) {

cmp = -cmp;

}

return cmp;

}

#if 0

mp_int_t mpz_cmp_sml_int(const mpz_t *z, mp_int_t sml_int) {

mp_int_t cmp;

if (z->neg == 0) {

if (sml_int < 0) return 1;

if (sml_int == 0) {

if (z->len == 0) return 0;

return 1;

}

if (z->len == 0) return -1;

assert(sml_int < (1 << DIG_SIZE));

if (z->len != 1) return 1;

cmp = z->dig[0] - sml_int;

} else {

if (sml_int > 0) return -1;

if (sml_int == 0) {

if (z->len == 0) return 0;

return -1;

}

if (z->len == 0) return 1;

assert(sml_int > -(1 << DIG_SIZE));

if (z->len != 1) return -1;

cmp = -z->dig[0] - sml_int;

}

if (cmp < 0) return -1;

if (cmp > 0) return 1;

return 0;

}

#if 0

these functions are unused

mpz_t *mpz_abs(const mpz_t *z) {

mpz_t *z2 = mpz_clone(z);

z2->neg = 0;

return z2;

}