55#define GMP_LIMB_BITS (sizeof(mp_limb_t) * CHAR_BIT)
57#define GMP_LIMB_MAX (~ (mp_limb_t) 0)
58#define GMP_LIMB_HIGHBIT ((mp_limb_t) 1 << (GMP_LIMB_BITS - 1))
60#define GMP_HLIMB_BIT ((mp_limb_t) 1 << (GMP_LIMB_BITS / 2))
61#define GMP_LLIMB_MASK (GMP_HLIMB_BIT - 1)
63#define GMP_ULONG_BITS (sizeof(uIntMpz) * CHAR_BIT)
64#define GMP_ULONG_HIGHBIT ((uIntMpz) 1 << (GMP_ULONG_BITS - 1))
66#define GMP_ABS(x) ((x) >= 0 ? (x) : -(x))
67#define GMP_NEG_CAST(T,x) (-((T)((x) + 1) - 1))
69#define GMP_MIN(a, b) ((a) < (b) ? (a) : (b))
70#define GMP_MAX(a, b) ((a) > (b) ? (a) : (b))
72#define GMP_CMP(a,b) (((a) > (b)) - ((a) < (b)))
74#define gmp_assert_nocarry(x) do { \
75 mp_limb_t __cy = (x); \
79#define gmp_clz(count, x) do { \
80 mp_limb_t __clz_x = (x); \
83 (__clz_x & ((mp_limb_t) 0xff << (GMP_LIMB_BITS - 8))) == 0; \
86 for (; (__clz_x & GMP_LIMB_HIGHBIT) == 0; __clz_c++) \
91#define gmp_ctz(count, x) do { \
92 mp_limb_t __ctz_x = (x); \
93 unsigned __ctz_c = 0; \
94 gmp_clz (__ctz_c, __ctz_x & - __ctz_x); \
95 (count) = GMP_LIMB_BITS - 1 - __ctz_c; \
98#define gmp_add_ssaaaa(sh, sl, ah, al, bh, bl) \
102 (sh) = (ah) + (bh) + (__x < (al)); \
106#define gmp_sub_ddmmss(sh, sl, ah, al, bh, bl) \
110 (sh) = (ah) - (bh) - ((al) < (bl)); \
114#define gmp_umul_ppmm(w1, w0, u, v) \
116 mp_limb_t __x0, __x1, __x2, __x3; \
117 unsigned __ul, __vl, __uh, __vh; \
118 mp_limb_t __u = (u), __v = (v); \
120 __ul = __u & GMP_LLIMB_MASK; \
121 __uh = __u >> (GMP_LIMB_BITS / 2); \
122 __vl = __v & GMP_LLIMB_MASK; \
123 __vh = __v >> (GMP_LIMB_BITS / 2); \
125 __x0 = (mp_limb_t) __ul * __vl; \
126 __x1 = (mp_limb_t) __ul * __vh; \
127 __x2 = (mp_limb_t) __uh * __vl; \
128 __x3 = (mp_limb_t) __uh * __vh; \
130 __x1 += __x0 >> (GMP_LIMB_BITS / 2); \
133 __x3 += GMP_HLIMB_BIT; \
135 (w1) = __x3 + (__x1 >> (GMP_LIMB_BITS / 2)); \
136 (w0) = (__x1 << (GMP_LIMB_BITS / 2)) + (__x0 & GMP_LLIMB_MASK); \
139#define gmp_udiv_qrnnd_preinv(q, r, nh, nl, d, di) \
141 mp_limb_t _qh, _ql, _r, _mask; \
142 gmp_umul_ppmm (_qh, _ql, (nh), (di)); \
143 gmp_add_ssaaaa (_qh, _ql, _qh, _ql, (nh) + 1, (nl)); \
144 _r = (nl) - _qh * (d); \
145 _mask = -(mp_limb_t) (_r > _ql); \
158#define gmp_udiv_qr_3by2(q, r1, r0, n2, n1, n0, d1, d0, dinv) \
160 mp_limb_t _q0, _t1, _t0, _mask; \
161 gmp_umul_ppmm ((q), _q0, (n2), (dinv)); \
162 gmp_add_ssaaaa ((q), _q0, (q), _q0, (n2), (n1)); \
165 (r1) = (n1) - (d1) * (q); \
166 gmp_sub_ddmmss ((r1), (r0), (r1), (n0), (d1), (d0)); \
167 gmp_umul_ppmm (_t1, _t0, (d0), (q)); \
168 gmp_sub_ddmmss ((r1), (r0), (r1), (r0), _t1, _t0); \
172 _mask = - (mp_limb_t) ((r1) >= _q0); \
174 gmp_add_ssaaaa ((r1), (r0), (r1), (r0), _mask & (d1), _mask & (d0)); \
177 if ((r1) > (d1) || (r0) >= (d0)) \
180 gmp_sub_ddmmss ((r1), (r0), (r1), (r0), (d1), (d0)); \
186#define MP_LIMB_T_SWAP(x, y) \
188 mp_limb_t __mp_limb_t_swap__tmp = (x); \
190 (y) = __mp_limb_t_swap__tmp; \
192#define MP_SIZE_T_SWAP(x, y) \
194 mp_size_t __mp_size_t_swap__tmp = (x); \
196 (y) = __mp_size_t_swap__tmp; \
198#define MP_BITCNT_T_SWAP(x,y) \
200 mp_bitcnt_t __mp_bitcnt_t_swap__tmp = (x); \
202 (y) = __mp_bitcnt_t_swap__tmp; \
204#define MP_PTR_SWAP(x, y) \
206 mp_ptr __mp_ptr_swap__tmp = (x); \
208 (y) = __mp_ptr_swap__tmp; \
210#define MP_SRCPTR_SWAP(x, y) \
212 mp_srcptr __mp_srcptr_swap__tmp = (x); \
214 (y) = __mp_srcptr_swap__tmp; \
217#define MPN_PTR_SWAP(xp,xs, yp,ys) \
219 MP_PTR_SWAP (xp, yp); \
220 MP_SIZE_T_SWAP (xs, ys); \
222#define MPN_SRCPTR_SWAP(xp,xs, yp,ys) \
224 MP_SRCPTR_SWAP (xp, yp); \
225 MP_SIZE_T_SWAP (xs, ys); \
228#define MPZ_PTR_SWAP(x, y) \
230 mpz_ptr __mpz_ptr_swap__tmp = (x); \
232 (y) = __mpz_ptr_swap__tmp; \
234#define MPZ_SRCPTR_SWAP(x, y) \
236 mpz_srcptr __mpz_srcptr_swap__tmp = (x); \
238 (y) = __mpz_srcptr_swap__tmp; \
246gmp_die (
const char *msg)
248 fprintf (stderr,
"%s\n", msg);
253gmp_default_alloc (
size_t size)
261 gmp_die(
"gmp_default_alloc: Virtual memory exhausted.");
267gmp_default_realloc (
void *old,
size_t old_size,
size_t new_size)
273 p = realloc (old, new_size);
276 gmp_die(
"gmp_default_realloc: Virtual memory exhausted.");
282gmp_default_free (
void *p,
size_t size)
288static void * (*gmp_allocate_func) (size_t) = gmp_default_alloc;
289static void * (*gmp_reallocate_func) (
void *, size_t, size_t) = gmp_default_realloc;
290static void (*gmp_free_func) (
void *, size_t) = gmp_default_free;
294 void *(**realloc_func) (
void *,
size_t,
size_t),
295 void (**free_func) (
void *,
size_t))
298 *alloc_func = gmp_allocate_func;
301 *realloc_func = gmp_reallocate_func;
304 *free_func = gmp_free_func;
309 void *(*realloc_func) (
void *,
size_t,
size_t),
310 void (*free_func) (
void *,
size_t))
313 alloc_func = gmp_default_alloc;
315 realloc_func = gmp_default_realloc;
317 free_func = gmp_default_free;
319 gmp_allocate_func = alloc_func;
320 gmp_reallocate_func = realloc_func;
321 gmp_free_func = free_func;
324#define gmp_xalloc(size) ((*gmp_allocate_func)((size)))
325#define gmp_free(p) ((*gmp_free_func) ((p), 0))
337 return (
mp_ptr) (*gmp_reallocate_func) (old, 0, size *
sizeof (
mp_limb_t));
347 for (i = 0; i < n; i++)
364 return ap[n] > bp[n] ? 1 : -1;
373 return an < bn ? -1 : 1;
381 while (n > 0 && xp[n-1] == 0)
389 return mpn_normalized_size (rp, n) == 0;
424 for (i = 0, cy = 0; i < n; i++)
427 a = ap[i]; b = bp[i];
446 cy =
mpn_add_1 (rp + bn, ap + bn, an - bn, cy);
477 for (i = 0, cy = 0; i < n; i++)
480 a = ap[i]; b = bp[i];
498 cy =
mpn_sub_1 (rp + bn, ap + bn, an - bn, cy);
516 cl = (lpl < cl) + hpl;
539 cl = (lpl < cl) + hpl;
565 cl = (lpl < cl) + hpl;
628 retval = low_limb >> tnc;
629 high_limb = (low_limb << cnt);
634 *--rp = high_limb | (low_limb >> tnc);
635 high_limb = (low_limb << cnt);
655 retval = (high_limb << tnc);
656 low_limb = high_limb >> cnt;
661 *rp++ = low_limb | (high_limb << tnc);
662 low_limb = high_limb >> cnt;
676 assert (0 <= i && i <= un );
837 m -= ((r > u1) | ((r == u1) & (tl > u0)));
862 inv->
d1 = d << shift;
892 mpn_div_qr_1_invert (inv, dp[0]);
894 mpn_div_qr_2_invert (inv, dp[1], dp[0]);
928 tp = gmp_xalloc_limbs (nn);
948 return r >> inv->
shift;
957 if ((d & (d-1)) == 0)
976 mpn_div_qr_1_invert (&inv, d);
977 return mpn_div_qr_1_preinv (qp, np, nn, &inv);
998 tp = gmp_xalloc_limbs (nn);
1040 mpn_div_qr_2_invert (&inv,
d1,
d0);
1041 mpn_div_qr_2_preinv (qp, rp, np, nn, &inv);
1046mpn_div_qr_pi1 (
mp_ptr qp,
1075 if (n1 ==
d1 && n0 ==
d0)
1095 n1 +=
d1 +
mpn_add_n (np + i, np + i, dp, dn - 1);
1117 np[0] = mpn_div_qr_1_preinv (qp, np, nn, inv);
1119 mpn_div_qr_2_preinv (qp, np, np, nn, inv);
1125 assert (inv->
d1 == dp[dn-1]);
1126 assert (inv->
d0 == dp[dn-2]);
1135 mpn_div_qr_pi1 (qp, np, nn, nh, dp, dn, inv->
di);
1151 mpn_div_qr_invert (&inv, dp, dn);
1152 if (dn > 2 && inv.
shift > 0)
1154 tp = gmp_xalloc_limbs (dn);
1158 mpn_div_qr_preinv (qp, np, nn, dp, dn, &inv);
1166mpn_base_power_of_two_p (
unsigned b)
1198 for (exp = 1, p = b; p <= m; exp++)
1223 sn = ((un - 1) *
GMP_LIMB_BITS + mpn_limb_size_in_base_2 (up[un-1])
1226 mask = (1U << bits) - 1;
1228 for (i = 0, j = sn, shift = 0; j-- > 0;)
1230 unsigned char digit = up[i] >> shift;
1237 digit |= up[i] << (bits - shift);
1239 sp[j] = digit & mask;
1247mpn_limb_get_str (
unsigned char *sp,
mp_limb_t w,
1251 for (i = 0; w > 0; i++)
1256 l = w << binv->
shift;
1268mpn_get_str_other (
unsigned char *sp,
1276 mpn_div_qr_1_invert (&binv, base);
1283 mpn_div_qr_1_invert (&bbinv, info->
bb);
1289 w = mpn_div_qr_1_preinv (up, up, un, &bbinv);
1290 un -= (up[un-1] == 0);
1291 done = mpn_limb_get_str (sp + sn, w, &binv);
1293 for (sn += done; done < info->
exp; done++)
1298 sn += mpn_limb_get_str (sp + sn, up[0], &binv);
1301 for (i = 0; 2*i + 1 < sn; i++)
1303 unsigned char t = sp[i];
1304 sp[i] = sp[sn - i - 1];
1317 assert (up[un-1] > 0);
1319 bits = mpn_base_power_of_two_p (base);
1321 return mpn_get_str_bits (sp, bits, up, un);
1326 mpn_get_base_info (&info, base);
1327 return mpn_get_str_other (sp, base, &info, up, un);
1332mpn_set_str_bits (
mp_ptr rp,
const unsigned char *sp,
size_t sn,
1339 for (j = sn, rn = 0, shift = 0; j-- > 0; )
1354 rp[rn++] = (
mp_limb_t) sp[j] >> (bits - shift);
1358 rn = mpn_normalized_size (rp, rn);
1365mpn_set_str_other (
mp_ptr rp,
const unsigned char *sp,
size_t sn,
1375 k = 1 + (sn - 1) % info->
exp;
1380 w = w * b + sp[j++];
1384 for (rn = 1; j < sn;)
1389 for (k = 1; k < info->
exp; k++)
1390 w = w * b + sp[j++];
1410 bits = mpn_base_power_of_two_p (base);
1412 return mpn_set_str_bits (rp, sp, sn, bits);
1417 mpn_get_base_info (&info, base);
1418 return mpn_set_str_other (rp, sp, sn, base, &info);
1427 static const mp_limb_t dummy_limb = 0xc1a0;
1431 r->_mp_d = (
mp_ptr) &dummy_limb;
1441 bits -= (bits != 0);
1446 r->_mp_d = gmp_xalloc_limbs (rn);
1462 r->_mp_d = gmp_xrealloc_limbs (r->_mp_d, size);
1464 r->_mp_d = gmp_xalloc_limbs (size);
1465 r->_mp_alloc = size;
1467 if (
GMP_ABS (r->_mp_size) > size)
1474#define MPZ_REALLOC(z,n) ((n) > (z)->_mp_alloc \
1475 ? mpz_realloc(z,n) \
1516 r->_mp_size = x->_mp_size;
1559 return (us == (us > 0));
1565 if (u->_mp_size < 0)
1567 return -1 - (long) ((u->_mp_d[0] - 1) & ~GMP_LIMB_HIGHBIT);
1569 return (
long) (
mpz_get_ui (u) & ~GMP_LIMB_HIGHBIT);
1575 return u->_mp_size == 0 ? 0 : u->_mp_d[0];
1587 if (n >= 0 && n <
GMP_ABS (u->_mp_size))
1622 xn = mpn_normalized_size (x->_mp_d,
GMP_ABS (xs));
1623 x->_mp_size = xs < 0 ? -xn : xn;
1649 if (x != x || x == x * 0.5)
1666 for (rn = 1; x >= B; rn++)
1685 r->_mp_size = sign ? - rn : rn;
1709 x = B*x + u->_mp_d[--un];
1711 if (u->_mp_size < 0)
1735 for (i = 1; i < xn; i++)
1742 for (i = xn; i-- > 0;)
1761 if (x->_mp_size < 0)
1782 return GMP_CMP (u->_mp_size, 0);
1794 else if (usize >= 0)
1820 return (asize < bsize) ? -1 : 1;
1821 else if (asize >= 0)
1822 return mpn_cmp (a->_mp_d, b->_mp_d, asize);
1824 return mpn_cmp (b->_mp_d, a->_mp_d, -asize);
1830 if (
GMP_ABS (u->_mp_size) > 1)
1839 return mpn_cmp4 (u->_mp_d,
GMP_ABS (u->_mp_size),
1840 v->_mp_d,
GMP_ABS (v->_mp_size));
1847 r->_mp_size =
GMP_ABS (r->_mp_size);
1854 r->_mp_size = -r->_mp_size;
1906 if (an == 1 && a->_mp_d[0] < b)
1908 rp[0] = b - a->_mp_d[0];
1914 return mpn_normalized_size (rp, an);
1921 if (a->_mp_size >= 0)
1922 r->_mp_size = mpz_abs_add_ui (r, a, b);
1924 r->_mp_size = -mpz_abs_sub_ui (r, a, b);
1930 if (a->_mp_size < 0)
1931 r->_mp_size = -mpz_abs_add_ui (r, a, b);
1933 r->_mp_size = mpz_abs_sub_ui (r, a, b);
1939 if (b->_mp_size < 0)
1940 r->_mp_size = mpz_abs_add_ui (r, b, a);
1942 r->_mp_size = -mpz_abs_sub_ui (r, b, a);
1960 cy =
mpn_add (rp, a->_mp_d, an, b->_mp_d, bn);
1975 cmp = mpn_cmp4 (a->_mp_d, an, b->_mp_d, bn);
1980 return mpn_normalized_size (rp, an);
1986 return -mpn_normalized_size (rp, bn);
1997 if ( (a->_mp_size ^ b->_mp_size) >= 0)
1998 rn = mpz_abs_add (r, a, b);
2000 rn = mpz_abs_sub (r, a, b);
2002 r->_mp_size = a->_mp_size >= 0 ? rn : - rn;
2010 if ( (a->_mp_size ^ b->_mp_size) >= 0)
2011 rn = mpz_abs_sub (r, a, b);
2013 rn = mpz_abs_add (r, a, b);
2015 r->_mp_size = a->_mp_size >= 0 ? rn : - rn;
2041 if (us == 0 || v == 0)
2054 r->_mp_size = (us < 0) ? - un : un;
2068 if (un == 0 || vn == 0)
2074 sign = (un ^ vn) < 0;
2083 mpn_mul (tp, u->_mp_d, un, v->_mp_d, vn);
2085 mpn_mul (tp, v->_mp_d, vn, u->_mp_d, un);
2088 rn -= tp[rn-1] == 0;
2090 t->_mp_size = sign ? - rn : rn;
2113 rn = un + limbs + (shift > 0);
2126 r->_mp_size = (u->_mp_size < 0) ? - rn : rn;
2183 gmp_die(
"mpz_div_qr: Divide by zero.");
2246 mpn_div_qr (qp, np, nn, d->_mp_d, dn);
2250 qn -= (qp[qn-1] == 0);
2252 tq->_mp_size = qs < 0 ? -qn : qn;
2254 rn = mpn_normalized_size (np, dn);
2255 tr->_mp_size = ns < 0 ? - rn : rn;
2370 || (u->_mp_d[limb_cnt]
2383 mpn_rshift (qp, u->_mp_d + limb_cnt, qn, bit_index);
2384 qn -= qp[qn - 1] == 0;
2388 mpn_copyi (qp, u->_mp_d + limb_cnt, qn);
2409 if (us == 0 || bit_index == 0)
2432 for (i = un; i < rn - 1; i++)
2452 rp[rn-1] = u->_mp_d[rn-1] & mask;
2466 rn = mpn_normalized_size (rp, rn);
2467 r->_mp_size = us < 0 ? -rn : rn;
2561 rl = mpn_div_qr_1 (qp, n->_mp_d, qn, d);
2565 rs = (ns < 0) ? -rs : rs;
2583 qn -= (qp[qn-1] == 0);
2584 assert (qn == 0 || qp[qn-1] > 0);
2586 q->_mp_size = (ns < 0) ? - qn : qn;
2677 return mpz_div_qr_ui (NULL, NULL, n, d,
GMP_DIV_TRUNC) == 0;
2687 assert ( (u | v) > 0);
2702 while ( (v & 1) == 0)
2712 while ( (u & 1) == 0);
2719 while ( (v & 1) == 0);
2739 v = mpn_gcd_11 (mpn_div_qr_1 (NULL, u->_mp_d, un, v), v);
2749mpz_make_odd (
mpz_t r)
2753 assert (r->_mp_size > 0);
2755 shift = mpn_common_scan (r->_mp_d[0], 0, r->_mp_d, 0, 0);
2767 if (u->_mp_size == 0)
2772 if (v->_mp_size == 0)
2782 uz = mpz_make_odd (tu);
2784 vz = mpz_make_odd (tv);
2787 if (tu->_mp_size < tv->_mp_size)
2791 if (tu->_mp_size == 0)
2810 if (tv->_mp_size == 1)
2827 mpz_t tu, tv, s0, s1, t0, t1;
2831 if (u->_mp_size == 0)
2843 if (v->_mp_size == 0)
2863 uz = mpz_make_odd (tu);
2865 vz = mpz_make_odd (tv);
2872 if (tu->_mp_size < tv->_mp_size)
2910 if (tu->_mp_size > 0)
2913 shift = mpz_make_odd (tu);
2936 shift = mpz_make_odd (tv);
2946 shift = mpz_make_odd (tu);
2987 if (u->_mp_size < 0)
2989 if (v->_mp_size < 0)
3011 if (u->_mp_size == 0 || v->_mp_size == 0)
3030 if (v == 0 || u->_mp_size == 0)
3059 if (tr->_mp_size < 0)
3061 if (m->_mp_size >= 0)
3119 gmp_die (
"mpz_powm: Zero modulo.");
3128 mpn_div_qr_invert (&minv, mp, mn);
3137 tp = gmp_xalloc_limbs (mn);
3144 if (e->_mp_size < 0)
3147 gmp_die (
"mpz_powm: Negative exponent and non-invertible base.");
3154 bn = base->_mp_size;
3157 mpn_div_qr_preinv (NULL, base->_mp_d, base->_mp_size, mp, mn, &minv);
3164 if (b->_mp_size < 0)
3170 base->_mp_size = mpn_normalized_size (base->_mp_d, bn);
3185 if (tr->_mp_size > mn)
3187 mpn_div_qr_preinv (NULL, tr->_mp_d, tr->_mp_size, mp, mn, &minv);
3188 tr->_mp_size = mpn_normalized_size (tr->_mp_d, mn);
3196 if (tr->_mp_size >= mn)
3199 mpn_div_qr_preinv (NULL, tr->_mp_d, tr->_mp_size, mp, mn, &minv);
3200 tr->_mp_size = mpn_normalized_size (tr->_mp_d, mn);
3225 if ((~z & sgn) != 0)
3226 gmp_die (
"mpz_rootrem: Negative argument, with even root.");
3228 gmp_die (
"mpz_rootrem: Zeroth root.");
3286 res = r->_mp_size == 0;
3308 if (u->_mp_size <= 0)
3309 return (u->_mp_size == 0);
3320 assert (p [n-1] != 0);
3331 assert (p [n-1] != 0);
3337 assert (s->_mp_size == (n+1)/2);
3365 k = (k <= n) ? n - k : 0;
3406#define GMP_PRIME_PRODUCT \
3407 (3UL*5UL*7UL*11UL*13UL*17UL*19UL*23UL*29UL)
3410#define GMP_PRIME_MASK 0xc96996dcUL
3428 assert (n->_mp_size != 0);
3450 nm1->_mp_size = mpz_abs_sub_ui (nm1, n, 1);
3454 for (j = 0, is_prime = 1; is_prime & (j < reps); j++)
3464 is_prime = gmp_millerrabin (n, nm1, y, q, k);
3511 if (limb_index >= dn)
3515 w = d->_mp_d[limb_index];
3516 bit = (w >>
shift) & 1;
3524 while (--limb_index >= 0)
3525 if (d->_mp_d[limb_index] > 0)
3543 if (limb_index >= dn)
3550 dp[limb_index] = bit;
3551 for (i = dn; i < limb_index; i++)
3553 dn = limb_index + 1;
3561 cy =
mpn_add_1 (dp + limb_index, dp + limb_index, dn - limb_index, bit);
3569 d->_mp_size = (d->_mp_size < 0) ? - dn : dn;
3585 assert (limb_index < dn);
3588 dn - limb_index, bit));
3589 dn = mpn_normalized_size (dp, dn);
3590 d->_mp_size = (d->_mp_size < 0) ? - dn : dn;
3598 if (d->_mp_size >= 0)
3599 mpz_abs_add_bit (d, bit_index);
3601 mpz_abs_sub_bit (d, bit_index);
3610 if (d->_mp_size >= 0)
3611 mpz_abs_sub_bit (d, bit_index);
3613 mpz_abs_add_bit (d, bit_index);
3620 if (
mpz_tstbit (d, bit_index) ^ (d->_mp_size < 0))
3621 mpz_abs_sub_bit (d, bit_index);
3623 mpz_abs_add_bit (d, bit_index);
3656 uc = u->_mp_size < 0;
3657 vc = v->_mp_size < 0;
3675 ul = (up[i] ^ ux) + uc;
3678 vl = (vp[i] ^ vx) + vc;
3681 rl = ( (ul & vl) ^ rx) + rc;
3690 ul = (up[i] ^ ux) + uc;
3693 rl = ( (ul & vx) ^ rx) + rc;
3700 rn = mpn_normalized_size (rp, rn);
3702 r->_mp_size = rx ? -rn : rn;
3728 uc = u->_mp_size < 0;
3729 vc = v->_mp_size < 0;
3748 ul = (up[i] ^ ux) + uc;
3751 vl = (vp[i] ^ vx) + vc;
3754 rl = ( (ul | vl) ^ rx) + rc;
3763 ul = (up[i] ^ ux) + uc;
3766 rl = ( (ul | vx) ^ rx) + rc;
3773 rn = mpn_normalized_size (rp, rn);
3775 r->_mp_size = rx ? -rn : rn;
3801 uc = u->_mp_size < 0;
3802 vc = v->_mp_size < 0;
3817 ul = (up[i] ^ ux) + uc;
3820 vl = (vp[i] ^ vx) + vc;
3823 rl = (ul ^ vl ^ rx) + rc;
3832 ul = (up[i] ^ ux) + uc;
3835 rl = (ul ^ ux) + rc;
3842 un = mpn_normalized_size (rp, un);
3844 r->_mp_size = rx ? -un : un;
3853 for (c = 0; x > 0; x >>= 16)
3855 unsigned w = ((x >> 1) & 0x5555) + (x & 0x5555);
3856 w = ((w >> 2) & 0x3333) + (w & 0x3333);
3857 w = ((w >> 4) & 0x0f0f) + (w & 0x0f0f);
3858 w = (w >> 8) + (w & 0x00ff);
3870 for (c = 0, i = 0; i < n; i++)
3871 c += gmp_popcount_limb (p[i]);
3903 comp = - (uc = vc = (un < 0));
3917 for (i = 0, c = 0; i < vn; i++)
3919 ul = (up[i] ^ comp) + uc;
3922 vl = (vp[i] ^ comp) + vc;
3925 c += gmp_popcount_limb (ul ^ vl);
3931 ul = (up[i] ^ comp) + uc;
3934 c += gmp_popcount_limb (ul ^ comp);
3954 return (us >= 0 ? ~(
mp_bitcnt_t) 0 : starting_bit);
3960 if (starting_bit != 0)
3973 return mpn_common_scan (limb, i, up, un, ux);
4002 return mpn_common_scan (limb, i, up, un, ux);
4019 assert (base <= 36);
4027 bits = (un - 1) *
GMP_LIMB_BITS + mpn_limb_size_in_base_2 (up[un-1]);
4033 return (bits + 1) / 2;
4035 return (bits + 2) / 3;
4037 return (bits + 3) / 4;
4039 return (bits + 4) / 5;
4044 tp = gmp_xalloc_limbs (un);
4046 mpn_div_qr_1_invert (&bi, base);
4052 mpn_div_qr_1_preinv (tp, tp, un, &bi);
4053 un -= (tp[un-1] == 0);
4071 digits =
"0123456789abcdefghijklmnopqrstuvwxyz";
4076 digits =
"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
4098 if (u->_mp_size < 0)
4101 bits = mpn_base_power_of_two_p (base);
4105 sn = i + mpn_get_str_bits ((
unsigned char *) sp + i, bits, u->_mp_d, un);
4111 mpn_get_base_info (&info, base);
4112 tp = gmp_xalloc_limbs (un);
4115 sn = i + mpn_get_str_other ((
unsigned char *) sp + i, base, &info, tp, un);
4120 sp[i] = digits[(
unsigned char) sp[i]];
4136 assert (base == 0 || (base >= 2 && base <= 36));
4138 while (isspace( (
unsigned char) *sp))
4141 sign = (*sp ==
'-');
4148 if (sp[1] ==
'x' || sp[1] ==
'X')
4153 else if (sp[1] ==
'b' || sp[1] ==
'B')
4170 dp = (
unsigned char *)
gmp_xalloc (strlen (sp));
4172 for (dn = 0; *sp; sp++)
4176 if (isspace ((
unsigned char) *sp))
4178 else if (*sp >=
'0' && *sp <=
'9')
4180 else if (*sp >=
'a' && *sp <=
'z')
4181 digit = *sp -
'a' + 10;
4182 else if (*sp >=
'A' && *sp <=
'Z')
4183 digit = *sp -
'A' + 10;
4187 if (digit >= (
unsigned) base)
4203 bits = mpn_base_power_of_two_p (base);
4209 rn = mpn_set_str_bits (rp, dp, dn, bits);
4214 mpn_get_base_info (&info, base);
4215 alloc = (dn + info.
exp - 1) / info.
exp;
4217 rn = mpn_set_str_other (rp, dp, dn, base, &info);
4220 rn -= rp[rn-1] == 0;
4222 assert (rn <= alloc);
4225 r->_mp_size = sign ? - rn : rn;
4245 len = fwrite (str, 1, len, stream);
4252gmp_detect_endian (
void)
4254 static const int i = 2;
4255 const unsigned char *p = (
const unsigned char *) &i;
4262 size_t nails,
const void *src)
4264 const unsigned char *p;
4265 ptrdiff_t word_step;
4278 gmp_die (
"mpz_import: Nails not supported.");
4280 assert (order == 1 || order == -1);
4281 assert (endian >= -1 && endian <= 1);
4284 endian = gmp_detect_endian ();
4286 p = (
unsigned char *) src;
4288 word_step = (order != endian) ? 2 * size : 0;
4294 p += size * (count - 1);
4295 word_step = - word_step;
4305 for (limb = 0, bytes = 0, i = 0; count > 0; count--, p += word_step)
4308 for (j = 0; j < size; j++, p -= (ptrdiff_t) endian)
4310 limb |= (
mp_limb_t) *p << (bytes++ * CHAR_BIT);
4319 assert (i + (bytes > 0) == rn);
4323 i = mpn_normalized_size (rp, i);
4329mpz_export (
void *r,
size_t *countp,
int order,
size_t size,
int endian,
4330 size_t nails,
const mpz_t u)
4336 gmp_die (
"mpz_import: Nails not supported.");
4338 assert (order == 1 || order == -1);
4339 assert (endian >= -1 && endian <= 1);
4340 assert (size > 0 || u->_mp_size == 0);
4348 ptrdiff_t word_step;
4359 limb = u->_mp_d[un-1];
4364 k++; limb >>= CHAR_BIT;
4365 }
while (limb != 0);
4367 count = (k + (un-1) *
sizeof (
mp_limb_t) + size - 1) / size;
4373 endian = gmp_detect_endian ();
4375 p = (
unsigned char *) r;
4377 word_step = (order != endian) ? 2 * size : 0;
4383 p += size * (count - 1);
4384 word_step = - word_step;
4391 for (bytes = 0, i = 0, k = 0; k < count; k++, p += word_step)
4394 for (j = 0; j < size; j++, p -= (ptrdiff_t) endian)
4399 limb = u->_mp_d[i++];
4408 assert (k == count);
#define GMP_ULONG_HIGHBIT
void mpz_and(mpz_t r, const mpz_t u, const mpz_t v)
uIntMpz mpz_tdiv_q_ui(mpz_t q, const mpz_t n, uIntMpz d)
void mpz_clrbit(mpz_t d, mp_bitcnt_t bit_index)
uIntMpz mpz_fdiv_ui(const mpz_t n, uIntMpz d)
uIntMpz mpz_cdiv_r_ui(mpz_t r, const mpz_t n, uIntMpz d)
void mpz_sqrtrem(mpz_t s, mpz_t r, const mpz_t u)
int mpz_fits_ulong_p(const mpz_t u)
mp_size_t mpn_set_str(mp_ptr rp, const unsigned char *sp, size_t sn, int base)
void mpz_tdiv_q_2exp(mpz_t r, const mpz_t u, mp_bitcnt_t cnt)
#define gmp_udiv_qr_3by2(q, r1, r0, n2, n1, n0, d1, d0, dinv)
void mpz_tdiv_r(mpz_t r, const mpz_t n, const mpz_t d)
void mpz_ui_sub(mpz_t r, uIntMpz a, const mpz_t b)
void mpz_sub_ui(mpz_t r, const mpz_t a, uIntMpz b)
#define gmp_clz(count, x)
void mpn_copyd(mp_ptr d, mp_srcptr s, mp_size_t n)
void mpz_pow_ui(mpz_t r, const mpz_t b, uIntMpz e)
int mpz_cmpabs(const mpz_t u, const mpz_t v)
int mpz_set_str(mpz_t r, const char *sp, int base)
void mpz_realloc2(mpz_t x, mp_bitcnt_t n)
uIntMpz mpz_fdiv_q_ui(mpz_t q, const mpz_t n, uIntMpz d)
void mpn_copyi(mp_ptr d, mp_srcptr s, mp_size_t n)
mp_limb_t mpn_add_1(mp_ptr rp, mp_srcptr ap, mp_size_t n, mp_limb_t b)
#define gmp_umul_ppmm(w1, w0, u, v)
int mpz_perfect_square_p(const mpz_t u)
intMpz mpz_get_si(const mpz_t u)
int mpz_init_set_str(mpz_t r, const char *sp, int base)
mp_bitcnt_t mpz_popcount(const mpz_t u)
#define MPZ_SRCPTR_SWAP(x, y)
int mpz_cmp_si(const mpz_t u, intMpz v)
mp_limb_t mpn_mul_1(mp_ptr rp, mp_srcptr up, mp_size_t n, mp_limb_t vl)
void mpz_lcm_ui(mpz_t r, const mpz_t u, uIntMpz v)
#define MPZ_PTR_SWAP(x, y)
void mpz_init2(mpz_t r, mp_bitcnt_t bits)
#define GMP_NEG_CAST(T, x)
mp_limb_t mpn_neg(mp_ptr rp, mp_srcptr up, mp_size_t n)
void mpz_init_set(mpz_t r, const mpz_t x)
void mpz_set_ui(mpz_t r, uIntMpz x)
void mpz_cdiv_q_2exp(mpz_t r, const mpz_t u, mp_bitcnt_t cnt)
uIntMpz mpz_fdiv_qr_ui(mpz_t q, mpz_t r, const mpz_t n, uIntMpz d)
#define gmp_ctz(count, x)
void mpz_tdiv_r_2exp(mpz_t r, const mpz_t u, mp_bitcnt_t cnt)
void mpz_combit(mpz_t d, mp_bitcnt_t bit_index)
void mpz_mod(mpz_t r, const mpz_t n, const mpz_t d)
#define MPZ_REALLOC(z, n)
void mpz_limbs_finish(mpz_t x, mp_size_t xs)
void mpz_add(mpz_t r, const mpz_t a, const mpz_t b)
void mpn_mul_n(mp_ptr rp, mp_srcptr ap, mp_srcptr bp, mp_size_t n)
uIntMpz mpz_tdiv_r_ui(mpz_t r, const mpz_t n, uIntMpz d)
#define MP_LIMB_T_SWAP(x, y)
mp_bitcnt_t mpn_scan1(mp_srcptr ptr, mp_bitcnt_t bit)
void mpz_cdiv_q(mpz_t q, const mpz_t n, const mpz_t d)
void mpz_fdiv_q_2exp(mpz_t r, const mpz_t u, mp_bitcnt_t cnt)
mp_limb_t mpn_rshift(mp_ptr rp, mp_srcptr up, mp_size_t n, unsigned int cnt)
void mpz_powm_ui(mpz_t r, const mpz_t b, uIntMpz elimb, const mpz_t m)
int mpz_divisible_p(const mpz_t n, const mpz_t d)
mp_srcptr mpz_limbs_read(mpz_srcptr x)
#define gmp_udiv_qrnnd_preinv(q, r, nh, nl, d, di)
int mpz_fits_slong_p(const mpz_t u)
int mpz_cmpabs_ui(const mpz_t u, uIntMpz v)
void mpz_submul_ui(mpz_t r, const mpz_t u, uIntMpz v)
void mpz_import(mpz_t r, size_t count, int order, size_t size, int endian, size_t nails, const void *src)
void mpz_abs(mpz_t r, const mpz_t u)
size_t mpz_sizeinbase(const mpz_t u, int base)
mp_limb_t mpn_sub_n(mp_ptr rp, mp_srcptr ap, mp_srcptr bp, mp_size_t n)
void mpz_setbit(mpz_t d, mp_bitcnt_t bit_index)
#define gmp_assert_nocarry(x)
mp_limb_t mpn_add_n(mp_ptr rp, mp_srcptr ap, mp_srcptr bp, mp_size_t n)
void mpz_gcd(mpz_t g, const mpz_t u, const mpz_t v)
mp_bitcnt_t mpz_scan1(const mpz_t u, mp_bitcnt_t starting_bit)
void mpz_set_si(mpz_t r, intMpz x)
void mpz_addmul(mpz_t r, const mpz_t u, const mpz_t v)
void mpz_cdiv_r_2exp(mpz_t r, const mpz_t u, mp_bitcnt_t cnt)
void mpz_fdiv_q(mpz_t q, const mpz_t n, const mpz_t d)
void mp_set_memory_functions(void *(*alloc_func)(size_t), void *(*realloc_func)(void *, size_t, size_t), void(*free_func)(void *, size_t))
int mpz_congruent_p(const mpz_t a, const mpz_t b, const mpz_t m)
uIntMpz mpz_cdiv_ui(const mpz_t n, uIntMpz d)
#define MP_PTR_SWAP(x, y)
uIntMpz mpz_gcd_ui(mpz_t g, const mpz_t u, uIntMpz v)
void mpz_powm(mpz_t r, const mpz_t b, const mpz_t e, const mpz_t m)
int mpz_invert(mpz_t r, const mpz_t u, const mpz_t m)
mp_bitcnt_t mpn_scan0(mp_srcptr ptr, mp_bitcnt_t bit)
uIntMpz mpz_get_ui(const mpz_t u)
void mpn_sqr(mp_ptr rp, mp_srcptr ap, mp_size_t n)
void mpz_init_set_si(mpz_t r, intMpz x)
void mpz_ui_pow_ui(mpz_t r, uIntMpz blimb, uIntMpz e)
void mpz_addmul_ui(mpz_t r, const mpz_t u, uIntMpz v)
#define GMP_PRIME_PRODUCT
uIntMpz mpz_fdiv_r_ui(mpz_t r, const mpz_t n, uIntMpz d)
void mpz_init_set_ui(mpz_t r, uIntMpz x)
uIntMpz mpz_mod_ui(mpz_t r, const mpz_t n, uIntMpz d)
mp_limb_t mpn_sub(mp_ptr rp, mp_srcptr ap, mp_size_t an, mp_srcptr bp, mp_size_t bn)
#define MP_BITCNT_T_SWAP(x, y)
mpz_srcptr mpz_roinit_n(mpz_t x, mp_srcptr xp, mp_size_t xs)
double mpz_get_d(const mpz_t u)
#define MPN_SRCPTR_SWAP(xp, xs, yp, ys)
int mpn_cmp(mp_srcptr ap, mp_srcptr bp, mp_size_t n)
void mpz_ior(mpz_t r, const mpz_t u, const mpz_t v)
uIntMpz mpz_cdiv_qr_ui(mpz_t q, mpz_t r, const mpz_t n, uIntMpz d)
void mpz_mul(mpz_t r, const mpz_t u, const mpz_t v)
int mpz_cmpabs_d(const mpz_t x, double d)
mp_bitcnt_t mpz_scan0(const mpz_t u, mp_bitcnt_t starting_bit)
size_t mpn_get_str(unsigned char *sp, int base, mp_ptr up, mp_size_t un)
mp_limb_t mpn_lshift(mp_ptr rp, mp_srcptr up, mp_size_t n, unsigned int cnt)
int mpz_sgn(const mpz_t u)
void mpz_sqrt(mpz_t s, const mpz_t u)
int mpz_cmp_ui(const mpz_t u, uIntMpz v)
uIntMpz mpz_tdiv_ui(const mpz_t n, uIntMpz d)
char * mpz_get_str(char *sp, int base, const mpz_t u)
void mpz_fdiv_r(mpz_t r, const mpz_t n, const mpz_t d)
void mpn_zero(mp_ptr rp, mp_size_t n)
mp_ptr mpz_limbs_modify(mpz_t x, mp_size_t n)
void mpz_set_d(mpz_t r, double x)
mp_limb_t mpn_submul_1(mp_ptr rp, mp_srcptr up, mp_size_t n, mp_limb_t vl)
mp_size_t mpn_sqrtrem(mp_ptr sp, mp_ptr rp, mp_srcptr p, mp_size_t n)
int mpn_zero_p(mp_srcptr rp, mp_size_t n)
void mpz_tdiv_qr(mpz_t q, mpz_t r, const mpz_t n, const mpz_t d)
void mpz_com(mpz_t r, const mpz_t u)
void mpz_cdiv_r(mpz_t r, const mpz_t n, const mpz_t d)
int mpz_tstbit(const mpz_t d, mp_bitcnt_t bit_index)
void mpn_com(mp_ptr rp, mp_srcptr up, mp_size_t n)
void mpz_swap(mpz_t u, mpz_t v)
mp_limb_t mpn_mul(mp_ptr rp, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
mp_limb_t mpn_sub_1(mp_ptr rp, mp_srcptr ap, mp_size_t n, mp_limb_t b)
mp_bitcnt_t mpz_hamdist(const mpz_t u, const mpz_t v)
void mpz_lcm(mpz_t r, const mpz_t u, const mpz_t v)
void mpz_fdiv_r_2exp(mpz_t r, const mpz_t u, mp_bitcnt_t cnt)
void mpz_init_set_d(mpz_t r, double x)
int mpz_probab_prime_p(const mpz_t n, int reps)
void * mpz_export(void *r, size_t *countp, int order, size_t size, int endian, size_t nails, const mpz_t u)
int mpz_divisible_ui_p(const mpz_t n, uIntMpz d)
void mpz_sub(mpz_t r, const mpz_t a, const mpz_t b)
size_t mpz_out_str(FILE *stream, int base, const mpz_t x)
void mpz_gcdext(mpz_t g, mpz_t s, mpz_t t, const mpz_t u, const mpz_t v)
void mp_get_memory_functions(void *(**alloc_func)(size_t), void *(**realloc_func)(void *, size_t, size_t), void(**free_func)(void *, size_t))
void mpz_bin_uiui(mpz_t r, uIntMpz n, uIntMpz k)
const int mp_bits_per_limb
void mpz_fac_ui(mpz_t x, uIntMpz n)
mp_limb_t mpn_invert_3by2(mp_limb_t u1, mp_limb_t u0)
void mpz_add_ui(mpz_t r, const mpz_t a, uIntMpz b)
mp_limb_t mpn_add(mp_ptr rp, mp_srcptr ap, mp_size_t an, mp_srcptr bp, mp_size_t bn)
void mpz_mul_si(mpz_t r, const mpz_t u, intMpz v)
uIntMpz mpz_tdiv_qr_ui(mpz_t q, mpz_t r, const mpz_t n, uIntMpz d)
size_t mpz_size(const mpz_t u)
mp_ptr mpz_limbs_write(mpz_t x, mp_size_t n)
void mpz_set(mpz_t r, const mpz_t x)
void mpz_neg(mpz_t r, const mpz_t u)
void mpz_mul_2exp(mpz_t r, const mpz_t u, mp_bitcnt_t bits)
void mpz_fdiv_qr(mpz_t q, mpz_t r, const mpz_t n, const mpz_t d)
mp_limb_t mpn_addmul_1(mp_ptr rp, mp_srcptr up, mp_size_t n, mp_limb_t vl)
void mpz_rootrem(mpz_t x, mpz_t r, const mpz_t y, uIntMpz z)
void mpz_mul_ui(mpz_t r, const mpz_t u, uIntMpz v)
int mpn_perfect_square_p(mp_srcptr p, mp_size_t n)
void mpz_divexact(mpz_t q, const mpz_t n, const mpz_t d)
void mpz_xor(mpz_t r, const mpz_t u, const mpz_t v)
void mpz_tdiv_q(mpz_t q, const mpz_t n, const mpz_t d)
mp_limb_t mpz_getlimbn(const mpz_t u, mp_size_t n)
int mpz_cmp(const mpz_t a, const mpz_t b)
int mpz_cmp_d(const mpz_t x, double d)
void mpz_submul(mpz_t r, const mpz_t u, const mpz_t v)
int mpz_root(mpz_t x, const mpz_t y, uIntMpz z)
#define MP_SIZE_T_SWAP(x, y)
uIntMpz mpz_cdiv_q_ui(mpz_t q, const mpz_t n, uIntMpz d)
void mpz_divexact_ui(mpz_t q, const mpz_t n, uIntMpz d)
void mpz_cdiv_qr(mpz_t q, mpz_t r, const mpz_t n, const mpz_t d)
mp_bitcnt_t mpn_popcount(mp_srcptr p, mp_size_t n)
unsigned long long uIntMpz
const mp_limb_t * mp_srcptr
#define mpn_invert_limb(x)