gmp-impl.h
上传用户:qaz666999
上传日期:2022-08-06
资源大小:2570k
文件大小:174k
- #endif
- #ifndef mpn_decr_u
- #define mpn_decr_u(p,incr)
- do {
- mp_limb_t __x;
- mp_ptr __p = (p);
- if (__builtin_constant_p (incr) && (incr) == 1)
- {
- while ((*(__p++))-- == 0)
- ;
- }
- else
- {
- __x = *__p;
- *__p = __x - (incr);
- if (__x < (incr))
- while ((*(++__p))-- == 0)
- ;
- }
- } while (0)
- #endif
- #endif
- #if GMP_NAIL_BITS >= 1
- #ifndef mpn_incr_u
- #define mpn_incr_u(p,incr)
- do {
- mp_limb_t __x;
- mp_ptr __p = (p);
- if (__builtin_constant_p (incr) && (incr) == 1)
- {
- do
- {
- __x = (*__p + 1) & GMP_NUMB_MASK;
- *__p++ = __x;
- }
- while (__x == 0);
- }
- else
- {
- __x = (*__p + (incr));
- *__p++ = __x & GMP_NUMB_MASK;
- if (__x >> GMP_NUMB_BITS != 0)
- {
- do
- {
- __x = (*__p + 1) & GMP_NUMB_MASK;
- *__p++ = __x;
- }
- while (__x == 0);
- }
- }
- } while (0)
- #endif
- #ifndef mpn_decr_u
- #define mpn_decr_u(p,incr)
- do {
- mp_limb_t __x;
- mp_ptr __p = (p);
- if (__builtin_constant_p (incr) && (incr) == 1)
- {
- do
- {
- __x = *__p;
- *__p++ = (__x - 1) & GMP_NUMB_MASK;
- }
- while (__x == 0);
- }
- else
- {
- __x = *__p - (incr);
- *__p++ = __x & GMP_NUMB_MASK;
- if (__x >> GMP_NUMB_BITS != 0)
- {
- do
- {
- __x = *__p;
- *__p++ = (__x - 1) & GMP_NUMB_MASK;
- }
- while (__x == 0);
- }
- }
- } while (0)
- #endif
- #endif
- #ifndef MPN_INCR_U
- #if WANT_ASSERT
- #define MPN_INCR_U(ptr, size, n)
- do {
- ASSERT ((size) >= 1);
- ASSERT_NOCARRY (mpn_add_1 (ptr, ptr, size, n));
- } while (0)
- #else
- #define MPN_INCR_U(ptr, size, n) mpn_incr_u (ptr, n)
- #endif
- #endif
- #ifndef MPN_DECR_U
- #if WANT_ASSERT
- #define MPN_DECR_U(ptr, size, n)
- do {
- ASSERT ((size) >= 1);
- ASSERT_NOCARRY (mpn_sub_1 (ptr, ptr, size, n));
- } while (0)
- #else
- #define MPN_DECR_U(ptr, size, n) mpn_decr_u (ptr, n)
- #endif
- #endif
- /* Structure for conversion between internal binary format and
- strings in base 2..36. */
- struct bases
- {
- /* Number of digits in the conversion base that always fits in an mp_limb_t.
- For example, for base 10 on a machine where a mp_limb_t has 32 bits this
- is 9, since 10**9 is the largest number that fits into a mp_limb_t. */
- int chars_per_limb;
- /* log(2)/log(conversion_base) */
- double chars_per_bit_exactly;
- /* base**chars_per_limb, i.e. the biggest number that fits a word, built by
- factors of base. Exception: For 2, 4, 8, etc, big_base is log2(base),
- i.e. the number of bits used to represent each digit in the base. */
- mp_limb_t big_base;
- /* A GMP_LIMB_BITS bit approximation to 1/big_base, represented as a
- fixed-point number. Instead of dividing by big_base an application can
- choose to multiply by big_base_inverted. */
- mp_limb_t big_base_inverted;
- };
- #define mp_bases __MPN(bases)
- __GMP_DECLSPEC extern const struct bases mp_bases[257];
- /* For power of 2 bases this is exact. For other bases the result is either
- exact or one too big.
- To be exact always it'd be necessary to examine all the limbs of the
- operand, since numbers like 100..000 and 99...999 generally differ only
- in the lowest limb. It'd be possible to examine just a couple of high
- limbs to increase the probability of being exact, but that doesn't seem
- worth bothering with. */
- #define MPN_SIZEINBASE(result, ptr, size, base)
- do {
- int __lb_base, __cnt;
- size_t __totbits;
-
- ASSERT ((size) >= 0);
- ASSERT ((base) >= 2);
- ASSERT ((base) < numberof (mp_bases));
-
- /* Special case for X == 0. */
- if ((size) == 0)
- (result) = 1;
- else
- {
- /* Calculate the total number of significant bits of X. */
- count_leading_zeros (__cnt, (ptr)[(size)-1]);
- __totbits = (size_t) (size) * GMP_NUMB_BITS - (__cnt - GMP_NAIL_BITS);
-
- if (POW2_P (base))
- {
- __lb_base = mp_bases[base].big_base;
- (result) = (__totbits + __lb_base - 1) / __lb_base;
- }
- else
- (result) = (size_t)
- (__totbits * mp_bases[base].chars_per_bit_exactly) + 1;
- }
- } while (0)
- /* eliminate mp_bases lookups for base==16 */
- #define MPN_SIZEINBASE_16(result, ptr, size)
- do {
- int __cnt;
- mp_size_t __totbits;
-
- ASSERT ((size) >= 0);
-
- /* Special case for X == 0. */
- if ((size) == 0)
- (result) = 1;
- else
- {
- /* Calculate the total number of significant bits of X. */
- count_leading_zeros (__cnt, (ptr)[(size)-1]);
- __totbits = (size_t) (size) * GMP_NUMB_BITS - (__cnt - GMP_NAIL_BITS);
- (result) = (__totbits + 4 - 1) / 4;
- }
- } while (0)
- /* bit count to limb count, rounding up */
- #define BITS_TO_LIMBS(n) (((n) + (GMP_NUMB_BITS - 1)) / GMP_NUMB_BITS)
- /* MPN_SET_UI sets an mpn (ptr, cnt) to given ui. MPZ_FAKE_UI creates fake
- mpz_t from ui. The zp argument must have room for LIMBS_PER_ULONG limbs
- in both cases (LIMBS_PER_ULONG is also defined here.) */
- #if BITS_PER_ULONG <= GMP_NUMB_BITS /* need one limb per ulong */
- #define LIMBS_PER_ULONG 1
- #define MPN_SET_UI(zp, zn, u)
- (zp)[0] = (u);
- (zn) = ((zp)[0] != 0);
- #define MPZ_FAKE_UI(z, zp, u)
- (zp)[0] = (u);
- PTR (z) = (zp);
- SIZ (z) = ((zp)[0] != 0);
- ASSERT_CODE (ALLOC (z) = 1);
- #else /* need two limbs per ulong */
- #define LIMBS_PER_ULONG 2
- #define MPN_SET_UI(zp, zn, u)
- (zp)[0] = (u) & GMP_NUMB_MASK;
- (zp)[1] = (u) >> GMP_NUMB_BITS;
- (zn) = ((zp)[1] != 0 ? 2 : (zp)[0] != 0 ? 1 : 0);
- #define MPZ_FAKE_UI(z, zp, u)
- (zp)[0] = (u) & GMP_NUMB_MASK;
- (zp)[1] = (u) >> GMP_NUMB_BITS;
- SIZ (z) = ((zp)[1] != 0 ? 2 : (zp)[0] != 0 ? 1 : 0);
- PTR (z) = (zp);
- ASSERT_CODE (ALLOC (z) = 2);
- #endif
- #if HAVE_HOST_CPU_FAMILY_x86
- #define TARGET_REGISTER_STARVED 1
- #else
- #define TARGET_REGISTER_STARVED 0
- #endif
- /* LIMB_HIGHBIT_TO_MASK(n) examines the high bit of a limb value and turns 1
- or 0 there into a limb 0xFF..FF or 0 respectively.
- On most CPUs this is just an arithmetic right shift by GMP_LIMB_BITS-1,
- but C99 doesn't guarantee signed right shifts are arithmetic, so we have
- a little compile-time test and a fallback to a "? :" form. The latter is
- necessary for instance on Cray vector systems.
- Recent versions of gcc (eg. 3.3) will in fact optimize a "? :" like this
- to an arithmetic right shift anyway, but it's good to get the desired
- shift on past versions too (in particular since an important use of
- LIMB_HIGHBIT_TO_MASK is in udiv_qrnnd_preinv). */
- #define LIMB_HIGHBIT_TO_MASK(n)
- (((mp_limb_signed_t) -1 >> 1) < 0
- ? (mp_limb_signed_t) (n) >> (GMP_LIMB_BITS - 1)
- : (n) & GMP_LIMB_HIGHBIT ? MP_LIMB_T_MAX : CNST_LIMB(0))
- /* Use a library function for invert_limb, if available. */
- #define mpn_invert_limb __MPN(invert_limb)
- __GMP_DECLSPEC mp_limb_t mpn_invert_limb __GMP_PROTO ((mp_limb_t)) ATTRIBUTE_CONST;
- #if ! defined (invert_limb) && HAVE_NATIVE_mpn_invert_limb
- #define invert_limb(invxl,xl)
- do {
- (invxl) = mpn_invert_limb (xl);
- } while (0)
- #endif
- #ifndef invert_limb
- #define invert_limb(invxl,xl)
- do {
- mp_limb_t dummy;
- ASSERT ((xl) != 0);
- udiv_qrnnd (invxl, dummy, ~(xl), ~CNST_LIMB(0), xl);
- } while (0)
- #endif
- #define invert_pi1(dinv, d1, d0)
- do {
- mp_limb_t v, p, t1, t0, mask;
- invert_limb (v, d1);
- p = d1 * v;
- p += d0;
- if (p < d0)
- {
- v--;
- mask = -(p >= d1);
- p -= d1;
- v += mask;
- p -= mask & d1;
- }
- umul_ppmm (t1, t0, d0, v);
- p += t1;
- if (p < t1)
- {
- v--;
- if (UNLIKELY (p >= d1))
- {
- if (p > d1 || t0 >= d0)
- v--;
- }
- }
- (dinv).inv32 = v;
- } while (0)
- #ifndef udiv_qrnnd_preinv
- #define udiv_qrnnd_preinv udiv_qrnnd_preinv3
- #endif
- /* Divide the two-limb number in (NH,,NL) by D, with DI being the largest
- limb not larger than (2**(2*GMP_LIMB_BITS))/D - (2**GMP_LIMB_BITS).
- If this would yield overflow, DI should be the largest possible number
- (i.e., only ones). For correct operation, the most significant bit of D
- has to be set. Put the quotient in Q and the remainder in R. */
- #define udiv_qrnnd_preinv1(q, r, nh, nl, d, di)
- do {
- mp_limb_t _q, _ql, _r;
- mp_limb_t _xh, _xl;
- ASSERT ((d) != 0);
- umul_ppmm (_q, _ql, (nh), (di));
- _q += (nh); /* Compensate, di is 2**GMP_LIMB_BITS too small */
- umul_ppmm (_xh, _xl, _q, (d));
- sub_ddmmss (_xh, _r, (nh), (nl), _xh, _xl);
- if (_xh != 0)
- {
- sub_ddmmss (_xh, _r, _xh, _r, 0, (d));
- _q += 1;
- if (_xh != 0)
- {
- _r -= (d);
- _q += 1;
- }
- }
- if (_r >= (d))
- {
- _r -= (d);
- _q += 1;
- }
- (r) = _r;
- (q) = _q;
- } while (0)
- /* Like udiv_qrnnd_preinv, but branch-free. */
- #define udiv_qrnnd_preinv2(q, r, nh, nl, d, di)
- do {
- mp_limb_t _n2, _n10, _nmask, _nadj, _q1;
- mp_limb_t _xh, _xl;
- _n2 = (nh);
- _n10 = (nl);
- _nmask = LIMB_HIGHBIT_TO_MASK (_n10);
- _nadj = _n10 + (_nmask & (d));
- umul_ppmm (_xh, _xl, di, _n2 - _nmask);
- add_ssaaaa (_xh, _xl, _xh, _xl, _n2, _nadj);
- _q1 = ~_xh;
- umul_ppmm (_xh, _xl, _q1, d);
- add_ssaaaa (_xh, _xl, _xh, _xl, nh, nl);
- _xh -= (d); /* xh = 0 or -1 */
- (r) = _xl + ((d) & _xh);
- (q) = _xh - _q1;
- } while (0)
- /* Like udiv_qrnnd_preinv2, but for for any value D. DNORM is D shifted left
- so that its most significant bit is set. LGUP is ceil(log2(D)). */
- #define udiv_qrnnd_preinv2gen(q, r, nh, nl, d, di, dnorm, lgup)
- do {
- mp_limb_t _n2, _n10, _nmask, _nadj, _q1;
- mp_limb_t _xh, _xl;
- _n2 = ((nh) << (GMP_LIMB_BITS - (lgup))) + ((nl) >> 1 >> (l - 1));
- _n10 = (nl) << (GMP_LIMB_BITS - (lgup));
- _nmask = LIMB_HIGHBIT_TO_MASK (_n10);
- _nadj = _n10 + (_nmask & (dnorm));
- umul_ppmm (_xh, _xl, di, _n2 - _nmask);
- add_ssaaaa (_xh, _xl, _xh, _xl, _n2, _nadj);
- _q1 = ~_xh;
- umul_ppmm (_xh, _xl, _q1, d);
- add_ssaaaa (_xh, _xl, _xh, _xl, nh, nl);
- _xh -= (d);
- (r) = _xl + ((d) & _xh);
- (q) = _xh - _q1;
- } while (0)
- /* udiv_qrnnd_preinv3 -- Based on work by Niels M鰈ler and Torbj鰎n Granlund.
- We write things strangely below, to help gcc. A more straightforward
- version:
- _r = (nl) - _qh * (d);
- _t = _r + (d);
- if (_r >= _ql)
- {
- _qh--;
- _r = _t;
- }
- For one operation shorter critical path, one may want to use this form:
- _p = _qh * (d)
- _s = (nl) + (d);
- _r = (nl) - _p;
- _t = _s - _p;
- if (_r >= _ql)
- {
- _qh--;
- _r = _t;
- }
- */
- #define udiv_qrnnd_preinv3(q, r, nh, nl, d, di)
- do {
- mp_limb_t _qh, _ql, _r;
- umul_ppmm (_qh, _ql, (nh), (di));
- if (__builtin_constant_p (nl) && (nl) == 0)
- _qh += (nh) + 1;
- else
- add_ssaaaa (_qh, _ql, _qh, _ql, (nh) + 1, (nl));
- _r = (nl) - _qh * (d);
- if (_r > _ql) /* both > and >= should be OK */
- {
- _r += (d);
- _qh--;
- }
- if (UNLIKELY (_r >= (d)))
- {
- _r -= (d);
- _qh++;
- }
- (r) = _r;
- (q) = _qh;
- } while (0)
- /* Compute r = nh*B mod d, where di is the inverse of d. */
- #define udiv_rnd_preinv(r, nh, d, di)
- do {
- mp_limb_t _qh, _ql, _r;
- umul_ppmm (_qh, _ql, (nh), (di));
- _qh += (nh) + 1;
- _r = - _qh * (d);
- if (_r > _ql)
- _r += (d);
- (r) = _r;
- } while (0)
- /* Compute quotient the quotient and remainder for n / d. Requires d
- >= B^2 / 2 and n < d B. di is the inverse
- floor ((B^3 - 1) / (d0 + d1 B)) - B.
- NOTE: Output variables are updated multiple times. Only some inputs
- and outputs may overlap.
- */
- #define udiv_qr_3by2(q, r1, r0, n2, n1, n0, d1, d0, dinv)
- do {
- mp_limb_t _q0, _t1, _t0, _mask;
- umul_ppmm ((q), _q0, (n2), (dinv));
- add_ssaaaa ((q), _q0, (q), _q0, (n2), (n1));
-
- /* Compute the two most significant limbs of n - q'd */
- (r1) = (n1) - (d1) * (q);
- (r0) = (n0);
- sub_ddmmss ((r1), (r0), (r1), (r0), (d1), (d0));
- umul_ppmm (_t1, _t0, (d0), (q));
- sub_ddmmss ((r1), (r0), (r1), (r0), _t1, _t0);
- (q)++;
-
- /* Conditionally adjust q and the remainders */
- _mask = - (mp_limb_t) ((r1) >= _q0);
- (q) += _mask;
- add_ssaaaa ((r1), (r0), (r1), (r0), _mask & (d1), _mask & (d0));
- if (UNLIKELY ((r1) >= (d1)))
- {
- if ((r1) > (d1) || (r0) >= (d0))
- {
- (q)++;
- sub_ddmmss ((r1), (r0), (r1), (r0), (d1), (d0));
- }
- }
- } while (0)
- #ifndef mpn_preinv_divrem_1 /* if not done with cpuvec in a fat binary */
- #define mpn_preinv_divrem_1 __MPN(preinv_divrem_1)
- __GMP_DECLSPEC mp_limb_t mpn_preinv_divrem_1 __GMP_PROTO ((mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t, int));
- #endif
- /* USE_PREINV_DIVREM_1 is whether to use mpn_preinv_divrem_1, as opposed to the
- plain mpn_divrem_1. The default is yes, since the few CISC chips where
- preinv is not good have defines saying so. */
- #ifndef USE_PREINV_DIVREM_1
- #define USE_PREINV_DIVREM_1 1
- #endif
- #if USE_PREINV_DIVREM_1
- #define MPN_DIVREM_OR_PREINV_DIVREM_1(qp,xsize,ap,size,d,dinv,shift)
- mpn_preinv_divrem_1 (qp, xsize, ap, size, d, dinv, shift)
- #else
- #define MPN_DIVREM_OR_PREINV_DIVREM_1(qp,xsize,ap,size,d,dinv,shift)
- mpn_divrem_1 (qp, xsize, ap, size, d)
- #endif
- #ifndef PREINV_MOD_1_TO_MOD_1_THRESHOLD
- #define PREINV_MOD_1_TO_MOD_1_THRESHOLD 10
- #endif
- /* This selection may seem backwards. The reason mpn_mod_1 typically takes
- over for larger sizes is that it uses the mod_1_1 function. */
- #define MPN_MOD_OR_PREINV_MOD_1(src,size,divisor,inverse)
- (BELOW_THRESHOLD (size, PREINV_MOD_1_TO_MOD_1_THRESHOLD)
- ? mpn_preinv_mod_1 (src, size, divisor, inverse)
- : mpn_mod_1 (src, size, divisor))
- #ifndef mpn_mod_34lsub1 /* if not done with cpuvec in a fat binary */
- #define mpn_mod_34lsub1 __MPN(mod_34lsub1)
- __GMP_DECLSPEC mp_limb_t mpn_mod_34lsub1 __GMP_PROTO ((mp_srcptr, mp_size_t)) __GMP_ATTRIBUTE_PURE;
- #endif
- /* DIVEXACT_1_THRESHOLD is at what size to use mpn_divexact_1, as opposed to
- plain mpn_divrem_1. Likewise BMOD_1_TO_MOD_1_THRESHOLD for
- mpn_modexact_1_odd against plain mpn_mod_1. On most CPUs divexact and
- modexact are faster at all sizes, so the defaults are 0. Those CPUs
- where this is not right have a tuned threshold. */
- #ifndef DIVEXACT_1_THRESHOLD
- #define DIVEXACT_1_THRESHOLD 0
- #endif
- #ifndef BMOD_1_TO_MOD_1_THRESHOLD
- #define BMOD_1_TO_MOD_1_THRESHOLD 10
- #endif
- #ifndef mpn_divexact_1 /* if not done with cpuvec in a fat binary */
- #define mpn_divexact_1 __MPN(divexact_1)
- __GMP_DECLSPEC void mpn_divexact_1 __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_limb_t));
- #endif
- #define MPN_DIVREM_OR_DIVEXACT_1(dst, src, size, divisor)
- do {
- if (BELOW_THRESHOLD (size, DIVEXACT_1_THRESHOLD))
- ASSERT_NOCARRY (mpn_divrem_1 (dst, (mp_size_t) 0, src, size, divisor));
- else
- {
- ASSERT (mpn_mod_1 (src, size, divisor) == 0);
- mpn_divexact_1 (dst, src, size, divisor);
- }
- } while (0)
- #ifndef mpn_modexact_1c_odd /* if not done with cpuvec in a fat binary */
- #define mpn_modexact_1c_odd __MPN(modexact_1c_odd)
- __GMP_DECLSPEC mp_limb_t mpn_modexact_1c_odd __GMP_PROTO ((mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t)) __GMP_ATTRIBUTE_PURE;
- #endif
- #if HAVE_NATIVE_mpn_modexact_1_odd
- #define mpn_modexact_1_odd __MPN(modexact_1_odd)
- __GMP_DECLSPEC mp_limb_t mpn_modexact_1_odd __GMP_PROTO ((mp_srcptr, mp_size_t, mp_limb_t)) __GMP_ATTRIBUTE_PURE;
- #else
- #define mpn_modexact_1_odd(src,size,divisor)
- mpn_modexact_1c_odd (src, size, divisor, CNST_LIMB(0))
- #endif
- #define MPN_MOD_OR_MODEXACT_1_ODD(src,size,divisor)
- (BELOW_THRESHOLD (size, BMOD_1_TO_MOD_1_THRESHOLD)
- ? mpn_modexact_1_odd (src, size, divisor)
- : mpn_mod_1 (src, size, divisor))
- /* binvert_limb() sets inv to the multiplicative inverse of n modulo
- 2^GMP_NUMB_BITS, ie. satisfying inv*n == 1 mod 2^GMP_NUMB_BITS.
- n must be odd (otherwise such an inverse doesn't exist).
- This is not to be confused with invert_limb(), which is completely
- different.
- The table lookup gives an inverse with the low 8 bits valid, and each
- multiply step doubles the number of bits. See Jebelean "An algorithm for
- exact division" end of section 4 (reference in gmp.texi).
- Possible enhancement: Could use UHWtype until the last step, if half-size
- multiplies are faster (might help under _LONG_LONG_LIMB).
- Alternative: As noted in Granlund and Montgomery "Division by Invariant
- Integers using Multiplication" (reference in gmp.texi), n itself gives a
- 3-bit inverse immediately, and could be used instead of a table lookup.
- A 4-bit inverse can be obtained effectively from xoring bits 1 and 2 into
- bit 3, for instance with (((n + 2) & 4) << 1) ^ n. */
- #define binvert_limb_table __gmp_binvert_limb_table
- __GMP_DECLSPEC extern const unsigned char binvert_limb_table[128];
- #define binvert_limb(inv,n)
- do {
- mp_limb_t __n = (n);
- mp_limb_t __inv;
- ASSERT ((__n & 1) == 1);
-
- __inv = binvert_limb_table[(__n/2) & 0x7F]; /* 8 */
- if (GMP_NUMB_BITS > 8) __inv = 2 * __inv - __inv * __inv * __n;
- if (GMP_NUMB_BITS > 16) __inv = 2 * __inv - __inv * __inv * __n;
- if (GMP_NUMB_BITS > 32) __inv = 2 * __inv - __inv * __inv * __n;
-
- if (GMP_NUMB_BITS > 64)
- {
- int __invbits = 64;
- do {
- __inv = 2 * __inv - __inv * __inv * __n;
- __invbits *= 2;
- } while (__invbits < GMP_NUMB_BITS);
- }
-
- ASSERT ((__inv * __n & GMP_NUMB_MASK) == 1);
- (inv) = __inv & GMP_NUMB_MASK;
- } while (0)
- #define modlimb_invert binvert_limb /* backward compatibility */
- /* Multiplicative inverse of 3, modulo 2^GMP_NUMB_BITS.
- Eg. 0xAAAAAAAB for 32 bits, 0xAAAAAAAAAAAAAAAB for 64 bits.
- GMP_NUMB_MAX/3*2+1 is right when GMP_NUMB_BITS is even, but when it's odd
- we need to start from GMP_NUMB_MAX>>1. */
- #define MODLIMB_INVERSE_3 (((GMP_NUMB_MAX >> (GMP_NUMB_BITS % 2)) / 3) * 2 + 1)
- /* ceil(GMP_NUMB_MAX/3) and ceil(2*GMP_NUMB_MAX/3).
- These expressions work because GMP_NUMB_MAX%3 != 0 for all GMP_NUMB_BITS. */
- #define GMP_NUMB_CEIL_MAX_DIV3 (GMP_NUMB_MAX / 3 + 1)
- #define GMP_NUMB_CEIL_2MAX_DIV3 ((GMP_NUMB_MAX>>1) / 3 + 1 + GMP_NUMB_HIGHBIT)
- /* Set r to -a mod d. a>=d is allowed. Can give r>d. All should be limbs.
- It's not clear whether this is the best way to do this calculation.
- Anything congruent to -a would be fine for the one limb congruence
- tests. */
- #define NEG_MOD(r, a, d)
- do {
- ASSERT ((d) != 0);
- ASSERT_LIMB (a);
- ASSERT_LIMB (d);
-
- if ((a) <= (d))
- {
- /* small a is reasonably likely */
- (r) = (d) - (a);
- }
- else
- {
- unsigned __twos;
- mp_limb_t __dnorm;
- count_leading_zeros (__twos, d);
- __twos -= GMP_NAIL_BITS;
- __dnorm = (d) << __twos;
- (r) = ((a) <= __dnorm ? __dnorm : 2*__dnorm) - (a);
- }
-
- ASSERT_LIMB (r);
- } while (0)
- /* A bit mask of all the least significant zero bits of n, or -1 if n==0. */
- #define LOW_ZEROS_MASK(n) (((n) & -(n)) - 1)
- /* ULONG_PARITY sets "p" to 1 if there's an odd number of 1 bits in "n", or
- to 0 if there's an even number. "n" should be an unsigned long and "p"
- an int. */
- #if defined (__GNUC__) && ! defined (NO_ASM) && HAVE_HOST_CPU_alpha_CIX
- #define ULONG_PARITY(p, n)
- do {
- int __p;
- __asm__ ("ctpop %1, %0" : "=r" (__p) : "r" (n));
- (p) = __p & 1;
- } while (0)
- #endif
- /* Cray intrinsic _popcnt. */
- #ifdef _CRAY
- #define ULONG_PARITY(p, n)
- do {
- (p) = _popcnt (n) & 1;
- } while (0)
- #endif
- #if defined (__GNUC__) && ! defined (__INTEL_COMPILER)
- && ! defined (NO_ASM) && defined (__ia64)
- /* unsigned long is either 32 or 64 bits depending on the ABI, zero extend
- to a 64 bit unsigned long long for popcnt */
- #define ULONG_PARITY(p, n)
- do {
- unsigned long long __n = (unsigned long) (n);
- int __p;
- __asm__ ("popcnt %0 = %1" : "=r" (__p) : "r" (__n));
- (p) = __p & 1;
- } while (0)
- #endif
- #if defined (__GNUC__) && ! defined (__INTEL_COMPILER)
- && ! defined (NO_ASM) && HAVE_HOST_CPU_FAMILY_x86
- #if __GMP_GNUC_PREREQ (3,1)
- #define __GMP_qm "=Qm"
- #define __GMP_q "=Q"
- #else
- #define __GMP_qm "=qm"
- #define __GMP_q "=q"
- #endif
- #define ULONG_PARITY(p, n)
- do {
- char __p;
- unsigned long __n = (n);
- __n ^= (__n >> 16);
- __asm__ ("xorb %h1, %b1nt"
- "setpo %0"
- : __GMP_qm (__p), __GMP_q (__n)
- : "1" (__n));
- (p) = __p;
- } while (0)
- #endif
- #if ! defined (ULONG_PARITY)
- #define ULONG_PARITY(p, n)
- do {
- unsigned long __n = (n);
- int __p = 0;
- do
- {
- __p ^= 0x96696996L >> (__n & 0x1F);
- __n >>= 5;
- }
- while (__n != 0);
-
- (p) = __p & 1;
- } while (0)
- #endif
- /* 3 cycles on 604 or 750 since shifts and rlwimi's can pair. gcc (as of
- version 3.1 at least) doesn't seem to know how to generate rlwimi for
- anything other than bit-fields, so use "asm". */
- #if defined (__GNUC__) && ! defined (NO_ASM)
- && HAVE_HOST_CPU_FAMILY_powerpc && GMP_LIMB_BITS == 32
- #define BSWAP_LIMB(dst, src)
- do {
- mp_limb_t __bswapl_src = (src);
- mp_limb_t __tmp1 = __bswapl_src >> 24; /* low byte */
- mp_limb_t __tmp2 = __bswapl_src << 24; /* high byte */
- __asm__ ("rlwimi %0, %2, 24, 16, 23" /* 2nd low */
- : "=r" (__tmp1) : "0" (__tmp1), "r" (__bswapl_src));
- __asm__ ("rlwimi %0, %2, 8, 8, 15" /* 3nd high */
- : "=r" (__tmp2) : "0" (__tmp2), "r" (__bswapl_src));
- (dst) = __tmp1 | __tmp2; /* whole */
- } while (0)
- #endif
- /* bswap is available on i486 and up and is fast. A combination rorw $8 /
- roll $16 / rorw $8 is used in glibc for plain i386 (and in the linux
- kernel with xchgb instead of rorw), but this is not done here, because
- i386 means generic x86 and mixing word and dword operations will cause
- partial register stalls on P6 chips. */
- #if defined (__GNUC__) && ! defined (NO_ASM)
- && HAVE_HOST_CPU_FAMILY_x86 && ! HAVE_HOST_CPU_i386
- && GMP_LIMB_BITS == 32
- #define BSWAP_LIMB(dst, src)
- do {
- __asm__ ("bswap %0" : "=r" (dst) : "0" (src));
- } while (0)
- #endif
- #if defined (__GNUC__) && ! defined (NO_ASM)
- && defined (__amd64__) && GMP_LIMB_BITS == 64
- #define BSWAP_LIMB(dst, src)
- do {
- __asm__ ("bswap %q0" : "=r" (dst) : "0" (src));
- } while (0)
- #endif
- #if defined (__GNUC__) && ! defined (__INTEL_COMPILER)
- && ! defined (NO_ASM) && defined (__ia64) && GMP_LIMB_BITS == 64
- #define BSWAP_LIMB(dst, src)
- do {
- __asm__ ("mux1 %0 = %1, @rev" : "=r" (dst) : "r" (src));
- } while (0)
- #endif
- /* As per glibc. */
- #if defined (__GNUC__) && ! defined (NO_ASM)
- && HAVE_HOST_CPU_FAMILY_m68k && GMP_LIMB_BITS == 32
- #define BSWAP_LIMB(dst, src)
- do {
- mp_limb_t __bswapl_src = (src);
- __asm__ ("ror%.w %#8, %0nt"
- "swap %0nt"
- "ror%.w %#8, %0"
- : "=d" (dst)
- : "0" (__bswapl_src));
- } while (0)
- #endif
- #if ! defined (BSWAP_LIMB)
- #if GMP_LIMB_BITS == 8
- #define BSWAP_LIMB(dst, src)
- do { (dst) = (src); } while (0)
- #endif
- #if GMP_LIMB_BITS == 16
- #define BSWAP_LIMB(dst, src)
- do {
- (dst) = ((src) << 8) + ((src) >> 8);
- } while (0)
- #endif
- #if GMP_LIMB_BITS == 32
- #define BSWAP_LIMB(dst, src)
- do {
- (dst) =
- ((src) << 24)
- + (((src) & 0xFF00) << 8)
- + (((src) >> 8) & 0xFF00)
- + ((src) >> 24);
- } while (0)
- #endif
- #if GMP_LIMB_BITS == 64
- #define BSWAP_LIMB(dst, src)
- do {
- (dst) =
- ((src) << 56)
- + (((src) & 0xFF00) << 40)
- + (((src) & 0xFF0000) << 24)
- + (((src) & 0xFF000000) << 8)
- + (((src) >> 8) & 0xFF000000)
- + (((src) >> 24) & 0xFF0000)
- + (((src) >> 40) & 0xFF00)
- + ((src) >> 56);
- } while (0)
- #endif
- #endif
- #if ! defined (BSWAP_LIMB)
- #define BSWAP_LIMB(dst, src)
- do {
- mp_limb_t __bswapl_src = (src);
- mp_limb_t __dst = 0;
- int __i;
- for (__i = 0; __i < BYTES_PER_MP_LIMB; __i++)
- {
- __dst = (__dst << 8) | (__bswapl_src & 0xFF);
- __bswapl_src >>= 8;
- }
- (dst) = __dst;
- } while (0)
- #endif
- /* Apparently lwbrx might be slow on some PowerPC chips, so restrict it to
- those we know are fast. */
- #if defined (__GNUC__) && ! defined (NO_ASM)
- && GMP_LIMB_BITS == 32 && HAVE_LIMB_BIG_ENDIAN
- && (HAVE_HOST_CPU_powerpc604
- || HAVE_HOST_CPU_powerpc604e
- || HAVE_HOST_CPU_powerpc750
- || HAVE_HOST_CPU_powerpc7400)
- #define BSWAP_LIMB_FETCH(limb, src)
- do {
- mp_srcptr __blf_src = (src);
- mp_limb_t __limb;
- __asm__ ("lwbrx %0, 0, %1"
- : "=r" (__limb)
- : "r" (__blf_src),
- "m" (*__blf_src));
- (limb) = __limb;
- } while (0)
- #endif
- #if ! defined (BSWAP_LIMB_FETCH)
- #define BSWAP_LIMB_FETCH(limb, src) BSWAP_LIMB (limb, *(src))
- #endif
- /* On the same basis that lwbrx might be slow, restrict stwbrx to those we
- know are fast. FIXME: Is this necessary? */
- #if defined (__GNUC__) && ! defined (NO_ASM)
- && GMP_LIMB_BITS == 32 && HAVE_LIMB_BIG_ENDIAN
- && (HAVE_HOST_CPU_powerpc604
- || HAVE_HOST_CPU_powerpc604e
- || HAVE_HOST_CPU_powerpc750
- || HAVE_HOST_CPU_powerpc7400)
- #define BSWAP_LIMB_STORE(dst, limb)
- do {
- mp_ptr __dst = (dst);
- mp_limb_t __limb = (limb);
- __asm__ ("stwbrx %1, 0, %2"
- : "=m" (*__dst)
- : "r" (__limb),
- "r" (__dst));
- } while (0)
- #endif
- #if ! defined (BSWAP_LIMB_STORE)
- #define BSWAP_LIMB_STORE(dst, limb) BSWAP_LIMB (*(dst), limb)
- #endif
- /* Byte swap limbs from {src,size} and store at {dst,size}. */
- #define MPN_BSWAP(dst, src, size)
- do {
- mp_ptr __dst = (dst);
- mp_srcptr __src = (src);
- mp_size_t __size = (size);
- mp_size_t __i;
- ASSERT ((size) >= 0);
- ASSERT (MPN_SAME_OR_SEPARATE_P (dst, src, size));
- CRAY_Pragma ("_CRI ivdep");
- for (__i = 0; __i < __size; __i++)
- {
- BSWAP_LIMB_FETCH (*__dst, __src);
- __dst++;
- __src++;
- }
- } while (0)
- /* Byte swap limbs from {dst,size} and store in reverse order at {src,size}. */
- #define MPN_BSWAP_REVERSE(dst, src, size)
- do {
- mp_ptr __dst = (dst);
- mp_size_t __size = (size);
- mp_srcptr __src = (src) + __size - 1;
- mp_size_t __i;
- ASSERT ((size) >= 0);
- ASSERT (! MPN_OVERLAP_P (dst, size, src, size));
- CRAY_Pragma ("_CRI ivdep");
- for (__i = 0; __i < __size; __i++)
- {
- BSWAP_LIMB_FETCH (*__dst, __src);
- __dst++;
- __src--;
- }
- } while (0)
- /* No processor claiming to be SPARC v9 compliant seems to
- implement the POPC instruction. Disable pattern for now. */
- #if 0
- #if defined __GNUC__ && defined __sparc_v9__ && GMP_LIMB_BITS == 64
- #define popc_limb(result, input)
- do {
- DItype __res;
- __asm__ ("popc %1,%0" : "=r" (result) : "rI" (input));
- } while (0)
- #endif
- #endif
- #if defined (__GNUC__) && ! defined (NO_ASM) && HAVE_HOST_CPU_alpha_CIX
- #define popc_limb(result, input)
- do {
- __asm__ ("ctpop %1, %0" : "=r" (result) : "r" (input));
- } while (0)
- #endif
- /* Cray intrinsic. */
- #ifdef _CRAY
- #define popc_limb(result, input)
- do {
- (result) = _popcnt (input);
- } while (0)
- #endif
- #if defined (__GNUC__) && ! defined (__INTEL_COMPILER)
- && ! defined (NO_ASM) && defined (__ia64) && GMP_LIMB_BITS == 64
- #define popc_limb(result, input)
- do {
- __asm__ ("popcnt %0 = %1" : "=r" (result) : "r" (input));
- } while (0)
- #endif
- /* Cool population count of an mp_limb_t.
- You have to figure out how this works, We won't tell you!
- The constants could also be expressed as:
- 0x55... = [2^N / 3] = [(2^N-1)/3]
- 0x33... = [2^N / 5] = [(2^N-1)/5]
- 0x0f... = [2^N / 17] = [(2^N-1)/17]
- (N is GMP_LIMB_BITS, [] denotes truncation.) */
- #if ! defined (popc_limb) && GMP_LIMB_BITS == 8
- #define popc_limb(result, input)
- do {
- mp_limb_t __x = (input);
- __x -= (__x >> 1) & MP_LIMB_T_MAX/3;
- __x = ((__x >> 2) & MP_LIMB_T_MAX/5) + (__x & MP_LIMB_T_MAX/5);
- __x = ((__x >> 4) + __x) & MP_LIMB_T_MAX/17;
- (result) = __x & 0xff;
- } while (0)
- #endif
- #if ! defined (popc_limb) && GMP_LIMB_BITS == 16
- #define popc_limb(result, input)
- do {
- mp_limb_t __x = (input);
- __x -= (__x >> 1) & MP_LIMB_T_MAX/3;
- __x = ((__x >> 2) & MP_LIMB_T_MAX/5) + (__x & MP_LIMB_T_MAX/5);
- __x = ((__x >> 4) + __x) & MP_LIMB_T_MAX/17;
- __x = ((__x >> 8) + __x);
- (result) = __x & 0xff;
- } while (0)
- #endif
- #if ! defined (popc_limb) && GMP_LIMB_BITS == 32
- #define popc_limb(result, input)
- do {
- mp_limb_t __x = (input);
- __x -= (__x >> 1) & MP_LIMB_T_MAX/3;
- __x = ((__x >> 2) & MP_LIMB_T_MAX/5) + (__x & MP_LIMB_T_MAX/5);
- __x = ((__x >> 4) + __x) & MP_LIMB_T_MAX/17;
- __x = ((__x >> 8) + __x);
- __x = ((__x >> 16) + __x);
- (result) = __x & 0xff;
- } while (0)
- #endif
- #if ! defined (popc_limb) && GMP_LIMB_BITS == 64
- #define popc_limb(result, input)
- do {
- mp_limb_t __x = (input);
- __x -= (__x >> 1) & MP_LIMB_T_MAX/3;
- __x = ((__x >> 2) & MP_LIMB_T_MAX/5) + (__x & MP_LIMB_T_MAX/5);
- __x = ((__x >> 4) + __x) & MP_LIMB_T_MAX/17;
- __x = ((__x >> 8) + __x);
- __x = ((__x >> 16) + __x);
- __x = ((__x >> 32) + __x);
- (result) = __x & 0xff;
- } while (0)
- #endif
- /* Define stuff for longlong.h. */
- #if HAVE_ATTRIBUTE_MODE
- typedef unsigned int UQItype __attribute__ ((mode (QI)));
- typedef int SItype __attribute__ ((mode (SI)));
- typedef unsigned int USItype __attribute__ ((mode (SI)));
- typedef int DItype __attribute__ ((mode (DI)));
- typedef unsigned int UDItype __attribute__ ((mode (DI)));
- #else
- typedef unsigned char UQItype;
- typedef long SItype;
- typedef unsigned long USItype;
- #if HAVE_LONG_LONG
- typedef long long int DItype;
- typedef unsigned long long int UDItype;
- #else /* Assume `long' gives us a wide enough type. Needed for hppa2.0w. */
- typedef long int DItype;
- typedef unsigned long int UDItype;
- #endif
- #endif
- typedef mp_limb_t UWtype;
- typedef unsigned int UHWtype;
- #define W_TYPE_SIZE GMP_LIMB_BITS
- /* Define ieee_double_extract and _GMP_IEEE_FLOATS.
- Bit field packing is "implementation defined" according to C99, which
- leaves us at the compiler's mercy here. For some systems packing is
- defined in the ABI (eg. x86). In any case so far it seems universal that
- little endian systems pack from low to high, and big endian from high to
- low within the given type.
- Within the fields we rely on the integer endianness being the same as the
- float endianness, this is true everywhere we know of and it'd be a fairly
- strange system that did anything else. */
- #if HAVE_DOUBLE_IEEE_LITTLE_SWAPPED
- #define _GMP_IEEE_FLOATS 1
- union ieee_double_extract
- {
- struct
- {
- gmp_uint_least32_t manh:20;
- gmp_uint_least32_t exp:11;
- gmp_uint_least32_t sig:1;
- gmp_uint_least32_t manl:32;
- } s;
- double d;
- };
- #endif
- #if HAVE_DOUBLE_IEEE_LITTLE_ENDIAN
- #define _GMP_IEEE_FLOATS 1
- union ieee_double_extract
- {
- struct
- {
- gmp_uint_least32_t manl:32;
- gmp_uint_least32_t manh:20;
- gmp_uint_least32_t exp:11;
- gmp_uint_least32_t sig:1;
- } s;
- double d;
- };
- #endif
- #if HAVE_DOUBLE_IEEE_BIG_ENDIAN
- #define _GMP_IEEE_FLOATS 1
- union ieee_double_extract
- {
- struct
- {
- gmp_uint_least32_t sig:1;
- gmp_uint_least32_t exp:11;
- gmp_uint_least32_t manh:20;
- gmp_uint_least32_t manl:32;
- } s;
- double d;
- };
- #endif
- /* Use (4.0 * ...) instead of (2.0 * ...) to work around buggy compilers
- that don't convert ulong->double correctly (eg. SunOS 4 native cc). */
- #define MP_BASE_AS_DOUBLE (4.0 * ((mp_limb_t) 1 << (GMP_NUMB_BITS - 2)))
- /* Maximum number of limbs it will take to store any `double'.
- We assume doubles have 53 mantissa bits. */
- #define LIMBS_PER_DOUBLE ((53 + GMP_NUMB_BITS - 2) / GMP_NUMB_BITS + 1)
- __GMP_DECLSPEC int __gmp_extract_double __GMP_PROTO ((mp_ptr, double));
- #define mpn_get_d __gmpn_get_d
- __GMP_DECLSPEC double mpn_get_d __GMP_PROTO ((mp_srcptr, mp_size_t, mp_size_t, long)) __GMP_ATTRIBUTE_PURE;
- /* DOUBLE_NAN_INF_ACTION executes code a_nan if x is a NaN, or executes
- a_inf if x is an infinity. Both are considered unlikely values, for
- branch prediction. */
- #if _GMP_IEEE_FLOATS
- #define DOUBLE_NAN_INF_ACTION(x, a_nan, a_inf)
- do {
- union ieee_double_extract u;
- u.d = (x);
- if (UNLIKELY (u.s.exp == 0x7FF))
- {
- if (u.s.manl == 0 && u.s.manh == 0)
- { a_inf; }
- else
- { a_nan; }
- }
- } while (0)
- #endif
- #if HAVE_DOUBLE_VAX_D || HAVE_DOUBLE_VAX_G || HAVE_DOUBLE_CRAY_CFP
- /* no nans or infs in these formats */
- #define DOUBLE_NAN_INF_ACTION(x, a_nan, a_inf)
- do { } while (0)
- #endif
- #ifndef DOUBLE_NAN_INF_ACTION
- /* Unknown format, try something generic.
- NaN should be "unordered", so x!=x.
- Inf should be bigger than DBL_MAX. */
- #define DOUBLE_NAN_INF_ACTION(x, a_nan, a_inf)
- do {
- {
- if (UNLIKELY ((x) != (x)))
- { a_nan; }
- else if (UNLIKELY ((x) > DBL_MAX || (x) < -DBL_MAX))
- { a_inf; }
- }
- } while (0)
- #endif
- /* On m68k, x86 and amd64, gcc (and maybe other compilers) can hold doubles
- in the coprocessor, which means a bigger exponent range than normal, and
- depending on the rounding mode, a bigger mantissa than normal. (See
- "Disappointments" in the gcc manual.) FORCE_DOUBLE stores and fetches
- "d" through memory to force any rounding and overflows to occur.
- On amd64, and on x86s with SSE2, gcc (depending on options) uses the xmm
- registers, where there's no such extra precision and no need for the
- FORCE_DOUBLE. We don't bother to detect this since the present uses for
- FORCE_DOUBLE are only in test programs and default generic C code.
- Not quite sure that an "automatic volatile" will use memory, but it does
- in gcc. An asm("":"=m"(d):"0"(d)) can't be used to trick gcc, since
- apparently matching operands like "0" are only allowed on a register
- output. gcc 3.4 warns about this, though in fact it and past versions
- seem to put the operand through memory as hoped. */
- #if (HAVE_HOST_CPU_FAMILY_m68k || HAVE_HOST_CPU_FAMILY_x86
- || defined (__amd64__))
- #define FORCE_DOUBLE(d)
- do { volatile double __gmp_force = (d); (d) = __gmp_force; } while (0)
- #else
- #define FORCE_DOUBLE(d) do { } while (0)
- #endif
- __GMP_DECLSPEC extern int __gmp_junk;
- __GMP_DECLSPEC extern const int __gmp_0;
- __GMP_DECLSPEC void __gmp_exception __GMP_PROTO ((int)) ATTRIBUTE_NORETURN;
- __GMP_DECLSPEC void __gmp_divide_by_zero __GMP_PROTO ((void)) ATTRIBUTE_NORETURN;
- __GMP_DECLSPEC void __gmp_sqrt_of_negative __GMP_PROTO ((void)) ATTRIBUTE_NORETURN;
- __GMP_DECLSPEC void __gmp_invalid_operation __GMP_PROTO ((void)) ATTRIBUTE_NORETURN;
- #define GMP_ERROR(code) __gmp_exception (code)
- #define DIVIDE_BY_ZERO __gmp_divide_by_zero ()
- #define SQRT_OF_NEGATIVE __gmp_sqrt_of_negative ()
- #if defined _LONG_LONG_LIMB
- #if __GMP_HAVE_TOKEN_PASTE
- #define CNST_LIMB(C) ((mp_limb_t) C##LL)
- #else
- #define CNST_LIMB(C) ((mp_limb_t) C/**/LL)
- #endif
- #else /* not _LONG_LONG_LIMB */
- #if __GMP_HAVE_TOKEN_PASTE
- #define CNST_LIMB(C) ((mp_limb_t) C##L)
- #else
- #define CNST_LIMB(C) ((mp_limb_t) C/**/L)
- #endif
- #endif /* _LONG_LONG_LIMB */
- /* Stuff used by mpn/generic/perfsqr.c and mpz/prime_p.c */
- #if GMP_NUMB_BITS == 2
- #define PP 0x3 /* 3 */
- #define PP_FIRST_OMITTED 5
- #endif
- #if GMP_NUMB_BITS == 4
- #define PP 0xF /* 3 x 5 */
- #define PP_FIRST_OMITTED 7
- #endif
- #if GMP_NUMB_BITS == 8
- #define PP 0x69 /* 3 x 5 x 7 */
- #define PP_FIRST_OMITTED 11
- #endif
- #if GMP_NUMB_BITS == 16
- #define PP 0x3AA7 /* 3 x 5 x 7 x 11 x 13 */
- #define PP_FIRST_OMITTED 17
- #endif
- #if GMP_NUMB_BITS == 32
- #define PP 0xC0CFD797L /* 3 x 5 x 7 x 11 x ... x 29 */
- #define PP_INVERTED 0x53E5645CL
- #define PP_FIRST_OMITTED 31
- #endif
- #if GMP_NUMB_BITS == 64
- #define PP CNST_LIMB(0xE221F97C30E94E1D) /* 3 x 5 x 7 x 11 x ... x 53 */
- #define PP_INVERTED CNST_LIMB(0x21CFE6CFC938B36B)
- #define PP_FIRST_OMITTED 59
- #endif
- #ifndef PP_FIRST_OMITTED
- #define PP_FIRST_OMITTED 3
- #endif
- /* BIT1 means a result value in bit 1 (second least significant bit), with a
- zero bit representing +1 and a one bit representing -1. Bits other than
- bit 1 are garbage. These are meant to be kept in "int"s, and casts are
- used to ensure the expressions are "int"s even if a and/or b might be
- other types.
- JACOBI_TWOS_U_BIT1 and JACOBI_RECIP_UU_BIT1 are used in mpn_jacobi_base
- and their speed is important. Expressions are used rather than
- conditionals to accumulate sign changes, which effectively means XORs
- instead of conditional JUMPs. */
- /* (a/0), with a signed; is 1 if a=+/-1, 0 otherwise */
- #define JACOBI_S0(a) (((a) == 1) | ((a) == -1))
- /* (a/0), with a unsigned; is 1 if a=+/-1, 0 otherwise */
- #define JACOBI_U0(a) ((a) == 1)
- /* (a/0), with a given by low and size;
- is 1 if a=+/-1, 0 otherwise */
- #define JACOBI_LS0(alow,asize)
- (((asize) == 1 || (asize) == -1) && (alow) == 1)
- /* (a/0), with a an mpz_t;
- fetch of low limb always valid, even if size is zero */
- #define JACOBI_Z0(a) JACOBI_LS0 (PTR(a)[0], SIZ(a))
- /* (0/b), with b unsigned; is 1 if b=1, 0 otherwise */
- #define JACOBI_0U(b) ((b) == 1)
- /* (0/b), with b unsigned; is 1 if b=+/-1, 0 otherwise */
- #define JACOBI_0S(b) ((b) == 1 || (b) == -1)
- /* (0/b), with b given by low and size; is 1 if b=+/-1, 0 otherwise */
- #define JACOBI_0LS(blow,bsize)
- (((bsize) == 1 || (bsize) == -1) && (blow) == 1)
- /* Convert a bit1 to +1 or -1. */
- #define JACOBI_BIT1_TO_PN(result_bit1)
- (1 - ((int) (result_bit1) & 2))
- /* (2/b), with b unsigned and odd;
- is (-1)^((b^2-1)/8) which is 1 if b==1,7mod8 or -1 if b==3,5mod8 and
- hence obtained from (b>>1)^b */
- #define JACOBI_TWO_U_BIT1(b)
- ((int) (((b) >> 1) ^ (b)))
- /* (2/b)^twos, with b unsigned and odd */
- #define JACOBI_TWOS_U_BIT1(twos, b)
- ((int) ((twos) << 1) & JACOBI_TWO_U_BIT1 (b))
- /* (2/b)^twos, with b unsigned and odd */
- #define JACOBI_TWOS_U(twos, b)
- (JACOBI_BIT1_TO_PN (JACOBI_TWOS_U_BIT1 (twos, b)))
- /* (-1/b), with b odd (signed or unsigned);
- is (-1)^((b-1)/2) */
- #define JACOBI_N1B_BIT1(b)
- ((int) (b))
- /* (a/b) effect due to sign of a: signed/unsigned, b odd;
- is (-1/b) if a<0, or +1 if a>=0 */
- #define JACOBI_ASGN_SU_BIT1(a, b)
- ((((a) < 0) << 1) & JACOBI_N1B_BIT1(b))
- /* (a/b) effect due to sign of b: signed/signed;
- is -1 if a and b both negative, +1 otherwise */
- #define JACOBI_BSGN_SS_BIT1(a, b)
- ((((a)<0) & ((b)<0)) << 1)
- /* (a/b) effect due to sign of b: signed/mpz;
- is -1 if a and b both negative, +1 otherwise */
- #define JACOBI_BSGN_SZ_BIT1(a, b)
- JACOBI_BSGN_SS_BIT1 (a, SIZ(b))
- /* (a/b) effect due to sign of b: mpz/signed;
- is -1 if a and b both negative, +1 otherwise */
- #define JACOBI_BSGN_ZS_BIT1(a, b)
- JACOBI_BSGN_SZ_BIT1 (b, a)
- /* (a/b) reciprocity to switch to (b/a), a,b both unsigned and odd;
- is (-1)^((a-1)*(b-1)/4), which means +1 if either a,b==1mod4, or -1 if
- both a,b==3mod4, achieved in bit 1 by a&b. No ASSERT()s about a,b odd
- because this is used in a couple of places with only bit 1 of a or b
- valid. */
- #define JACOBI_RECIP_UU_BIT1(a, b)
- ((int) ((a) & (b)))
- /* Strip low zero limbs from {b_ptr,b_size} by incrementing b_ptr and
- decrementing b_size. b_low should be b_ptr[0] on entry, and will be
- updated for the new b_ptr. result_bit1 is updated according to the
- factors of 2 stripped, as per (a/2). */
- #define JACOBI_STRIP_LOW_ZEROS(result_bit1, a, b_ptr, b_size, b_low)
- do {
- ASSERT ((b_size) >= 1);
- ASSERT ((b_low) == (b_ptr)[0]);
-
- while (UNLIKELY ((b_low) == 0))
- {
- (b_size)--;
- ASSERT ((b_size) >= 1);
- (b_ptr)++;
- (b_low) = *(b_ptr);
-
- ASSERT (((a) & 1) != 0);
- if ((GMP_NUMB_BITS % 2) == 1)
- (result_bit1) ^= JACOBI_TWO_U_BIT1(a);
- }
- } while (0)
- /* Set a_rem to {a_ptr,a_size} reduced modulo b, either using mod_1 or
- modexact_1_odd, but in either case leaving a_rem<b. b must be odd and
- unsigned. modexact_1_odd effectively calculates -a mod b, and
- result_bit1 is adjusted for the factor of -1.
- The way mpn_modexact_1_odd sometimes bases its remainder on a_size and
- sometimes on a_size-1 means if GMP_NUMB_BITS is odd we can't know what
- factor to introduce into result_bit1, so for that case use mpn_mod_1
- unconditionally.
- FIXME: mpn_modexact_1_odd is more efficient, so some way to get it used
- for odd GMP_NUMB_BITS would be good. Perhaps it could mung its result,
- or not skip a divide step, or something. */
- #define JACOBI_MOD_OR_MODEXACT_1_ODD(result_bit1, a_rem, a_ptr, a_size, b)
- do {
- mp_srcptr __a_ptr = (a_ptr);
- mp_size_t __a_size = (a_size);
- mp_limb_t __b = (b);
-
- ASSERT (__a_size >= 1);
- ASSERT (__b & 1);
-
- if ((GMP_NUMB_BITS % 2) != 0
- || ABOVE_THRESHOLD (__a_size, BMOD_1_TO_MOD_1_THRESHOLD))
- {
- (a_rem) = mpn_mod_1 (__a_ptr, __a_size, __b);
- }
- else
- {
- (result_bit1) ^= JACOBI_N1B_BIT1 (__b);
- (a_rem) = mpn_modexact_1_odd (__a_ptr, __a_size, __b);
- }
- } while (0)
- /* Matrix multiplication */
- #define mpn_matrix22_mul __MPN(matrix22_mul)
- __GMP_DECLSPEC void mpn_matrix22_mul __GMP_PROTO ((mp_ptr, mp_ptr, mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_srcptr, mp_srcptr, mp_srcptr, mp_size_t, mp_ptr));
- #define mpn_matrix22_mul_strassen __MPN(matrix22_mul_strassen)
- __GMP_DECLSPEC void mpn_matrix22_mul_strassen __GMP_PROTO ((mp_ptr, mp_ptr, mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_srcptr, mp_srcptr, mp_srcptr, mp_size_t, mp_ptr));
- #define mpn_matrix22_mul_itch __MPN(matrix22_mul_itch)
- __GMP_DECLSPEC mp_size_t mpn_matrix22_mul_itch __GMP_PROTO ((mp_size_t, mp_size_t));
- #ifndef MATRIX22_STRASSEN_THRESHOLD
- #define MATRIX22_STRASSEN_THRESHOLD 30
- #endif
- /* HGCD definitions */
- /* Extract one numb, shifting count bits left
- ________ ________
- |___xh___||___xl___|
- |____r____|
- >count <
- The count includes any nail bits, so it should work fine if count
- is computed using count_leading_zeros. If GMP_NAIL_BITS > 0, all of
- xh, xl and r include nail bits. Must have 0 < count < GMP_LIMB_BITS.
- FIXME: Omit masking with GMP_NUMB_MASK, and let callers do that for
- those calls where the count high bits of xh may be non-zero.
- */
- #define MPN_EXTRACT_NUMB(count, xh, xl)
- ((((xh) << ((count) - GMP_NAIL_BITS)) & GMP_NUMB_MASK) |
- ((xl) >> (GMP_LIMB_BITS - (count))))
- /* The matrix non-negative M = (u, u'; v,v') keeps track of the
- reduction (a;b) = M (alpha; beta) where alpha, beta are smaller
- than a, b. The determinant must always be one, so that M has an
- inverse (v', -u'; -v, u). Elements always fit in GMP_NUMB_BITS - 1
- bits. */
- struct hgcd_matrix1
- {
- mp_limb_t u[2][2];
- };
- #define mpn_hgcd2 __MPN (hgcd2)
- __GMP_DECLSPEC int mpn_hgcd2 __GMP_PROTO ((mp_limb_t, mp_limb_t, mp_limb_t, mp_limb_t, struct hgcd_matrix1 *));
- #define mpn_hgcd_mul_matrix1_vector __MPN (hgcd_mul_matrix1_vector)
- __GMP_DECLSPEC mp_size_t mpn_hgcd_mul_matrix1_vector __GMP_PROTO ((const struct hgcd_matrix1 *, mp_ptr, mp_srcptr, mp_ptr, mp_size_t));
- #define mpn_hgcd_mul_matrix1_inverse_vector __MPN (hgcd_mul_matrix1_inverse_vector)
- __GMP_DECLSPEC mp_size_t mpn_hgcd_mul_matrix1_inverse_vector __GMP_PROTO ((const struct hgcd_matrix1 *, mp_ptr, mp_srcptr, mp_ptr, mp_size_t));
- struct hgcd_matrix
- {
- mp_size_t alloc; /* for sanity checking only */
- mp_size_t n;
- mp_ptr p[2][2];
- };
- #define MPN_HGCD_MATRIX_INIT_ITCH(n) (4 * ((n+1)/2 + 1))
- #define mpn_hgcd_matrix_init __MPN (hgcd_matrix_init)
- __GMP_DECLSPEC void mpn_hgcd_matrix_init __GMP_PROTO ((struct hgcd_matrix *, mp_size_t, mp_ptr));
- #define mpn_hgcd_matrix_mul __MPN (hgcd_matrix_mul)
- __GMP_DECLSPEC void mpn_hgcd_matrix_mul __GMP_PROTO ((struct hgcd_matrix *, const struct hgcd_matrix *, mp_ptr));
- #define mpn_hgcd_matrix_adjust __MPN (hgcd_matrix_adjust)
- __GMP_DECLSPEC mp_size_t mpn_hgcd_matrix_adjust __GMP_PROTO ((struct hgcd_matrix *, mp_size_t, mp_ptr, mp_ptr, mp_size_t, mp_ptr));
- #define mpn_hgcd_itch __MPN (hgcd_itch)
- __GMP_DECLSPEC mp_size_t mpn_hgcd_itch __GMP_PROTO ((mp_size_t));
- #define mpn_hgcd __MPN (hgcd)
- __GMP_DECLSPEC mp_size_t mpn_hgcd __GMP_PROTO ((mp_ptr, mp_ptr, mp_size_t, struct hgcd_matrix *, mp_ptr));
- #define MPN_HGCD_LEHMER_ITCH(n) (n)
- #define mpn_hgcd_lehmer __MPN (hgcd_lehmer)
- __GMP_DECLSPEC mp_size_t mpn_hgcd_lehmer __GMP_PROTO ((mp_ptr, mp_ptr, mp_size_t, struct hgcd_matrix *, mp_ptr));
- /* Needs storage for the quotient */
- #define MPN_GCD_SUBDIV_STEP_ITCH(n) (n)
- #define mpn_gcd_subdiv_step __MPN(gcd_subdiv_step)
- __GMP_DECLSPEC mp_size_t mpn_gcd_subdiv_step __GMP_PROTO ((mp_ptr, mp_size_t *, mp_ptr, mp_ptr, mp_size_t, mp_ptr));
- #define MPN_GCD_LEHMER_N_ITCH(n) (n)
- #define mpn_gcd_lehmer_n __MPN(gcd_lehmer_n)
- __GMP_DECLSPEC mp_size_t mpn_gcd_lehmer_n __GMP_PROTO ((mp_ptr, mp_ptr, mp_ptr, mp_size_t, mp_ptr));
- #define mpn_gcdext_subdiv_step __MPN(gcdext_subdiv_step)
- __GMP_DECLSPEC mp_size_t mpn_gcdext_subdiv_step __GMP_PROTO ((mp_ptr, mp_size_t *, mp_ptr, mp_size_t *, mp_ptr, mp_ptr, mp_size_t, mp_ptr, mp_ptr, mp_size_t *, mp_ptr, mp_ptr));
- #define MPN_GCDEXT_LEHMER_N_ITCH(n) (4*(n) + 3)
- #define mpn_gcdext_lehmer_n __MPN(gcdext_lehmer_n)
- __GMP_DECLSPEC mp_size_t mpn_gcdext_lehmer_n __GMP_PROTO ((mp_ptr, mp_ptr, mp_size_t *, mp_ptr, mp_ptr, mp_size_t, mp_ptr));
- /* 4*(an + 1) + 4*(bn + 1) + an */
- #define MPN_GCDEXT_LEHMER_ITCH(an, bn) (5*(an) + 4*(bn) + 8)
- #ifndef HGCD_THRESHOLD
- #define HGCD_THRESHOLD 400
- #endif
- #ifndef GCD_DC_THRESHOLD
- #define GCD_DC_THRESHOLD 1000
- #endif
- #ifndef GCDEXT_DC_THRESHOLD
- #define GCDEXT_DC_THRESHOLD 600
- #endif
- /* Definitions for mpn_set_str and mpn_get_str */
- struct powers
- {
- mp_ptr p; /* actual power value */
- mp_size_t n; /* # of limbs at p */
- mp_size_t shift; /* weight of lowest limb, in limb base B */
- size_t digits_in_base; /* number of corresponding digits */
- int base;
- };
- typedef struct powers powers_t;
- #define mpn_dc_set_str_powtab_alloc(n) ((n) + GMP_LIMB_BITS)
- #define mpn_dc_set_str_itch(n) ((n) + GMP_LIMB_BITS)
- #define mpn_dc_get_str_powtab_alloc(n) ((n) + 2 * GMP_LIMB_BITS)
- #define mpn_dc_get_str_itch(n) ((n) + GMP_LIMB_BITS)
- #define mpn_dc_set_str __MPN(dc_set_str)
- __GMP_DECLSPEC mp_size_t mpn_dc_set_str __GMP_PROTO ((mp_ptr, const unsigned char *, size_t, const powers_t *, mp_ptr));
- #define mpn_bc_set_str __MPN(bc_set_str)
- __GMP_DECLSPEC mp_size_t mpn_bc_set_str __GMP_PROTO ((mp_ptr, const unsigned char *, size_t, int));
- #define mpn_set_str_compute_powtab __MPN(set_str_compute_powtab)
- __GMP_DECLSPEC void mpn_set_str_compute_powtab __GMP_PROTO ((powers_t *, mp_ptr, mp_size_t, int));
- /* __GMPF_BITS_TO_PREC applies a minimum 53 bits, rounds upwards to a whole
- limb and adds an extra limb. __GMPF_PREC_TO_BITS drops that extra limb,
- hence giving back the user's size in bits rounded up. Notice that
- converting prec->bits->prec gives an unchanged value. */
- #define __GMPF_BITS_TO_PREC(n)
- ((mp_size_t) ((__GMP_MAX (53, n) + 2 * GMP_NUMB_BITS - 1) / GMP_NUMB_BITS))
- #define __GMPF_PREC_TO_BITS(n)
- ((mp_bitcnt_t) (n) * GMP_NUMB_BITS - GMP_NUMB_BITS)
- __GMP_DECLSPEC extern mp_size_t __gmp_default_fp_limb_precision;
- /* Set n to the number of significant digits an mpf of the given _mp_prec
- field, in the given base. This is a rounded up value, designed to ensure
- there's enough digits to reproduce all the guaranteed part of the value.
- There are prec many limbs, but the high might be only "1" so forget it
- and just count prec-1 limbs into chars. +1 rounds that upwards, and a
- further +1 is because the limbs usually won't fall on digit boundaries.
- FIXME: If base is a power of 2 and the bits per digit divides
- GMP_LIMB_BITS then the +2 is unnecessary. This happens always for
- base==2, and in base==16 with the current 32 or 64 bit limb sizes. */
- #define MPF_SIGNIFICANT_DIGITS(n, base, prec)
- do {
- ASSERT (base >= 2 && base < numberof (mp_bases));
- (n) = 2 + (size_t) ((((size_t) (prec) - 1) * GMP_NUMB_BITS)
- * mp_bases[(base)].chars_per_bit_exactly);
- } while (0)
- /* Decimal point string, from the current C locale. Needs <langinfo.h> for
- nl_langinfo and constants, preferably with _GNU_SOURCE defined to get
- DECIMAL_POINT from glibc, and needs <locale.h> for localeconv, each under
- their respective #if HAVE_FOO_H.
- GLIBC recommends nl_langinfo because getting only one facet can be
- faster, apparently. */
- /* DECIMAL_POINT seems to need _GNU_SOURCE defined to get it from glibc. */
- #if HAVE_NL_LANGINFO && defined (DECIMAL_POINT)
- #define GMP_DECIMAL_POINT (nl_langinfo (DECIMAL_POINT))
- #endif
- /* RADIXCHAR is deprecated, still in unix98 or some such. */
- #if HAVE_NL_LANGINFO && defined (RADIXCHAR) && ! defined (GMP_DECIMAL_POINT)
- #define GMP_DECIMAL_POINT (nl_langinfo (RADIXCHAR))
- #endif
- /* localeconv is slower since it returns all locale stuff */
- #if HAVE_LOCALECONV && ! defined (GMP_DECIMAL_POINT)
- #define GMP_DECIMAL_POINT (localeconv()->decimal_point)
- #endif
- #if ! defined (GMP_DECIMAL_POINT)
- #define GMP_DECIMAL_POINT (".")
- #endif
- #define DOPRNT_CONV_FIXED 1
- #define DOPRNT_CONV_SCIENTIFIC 2
- #define DOPRNT_CONV_GENERAL 3
- #define DOPRNT_JUSTIFY_NONE 0
- #define DOPRNT_JUSTIFY_LEFT 1
- #define DOPRNT_JUSTIFY_RIGHT 2
- #define DOPRNT_JUSTIFY_INTERNAL 3
- #define DOPRNT_SHOWBASE_YES 1
- #define DOPRNT_SHOWBASE_NO 2
- #define DOPRNT_SHOWBASE_NONZERO 3
- struct doprnt_params_t {
- int base; /* negative for upper case */
- int conv; /* choices above */
- const char *expfmt; /* exponent format */
- int exptimes4; /* exponent multiply by 4 */
- char fill; /* character */
- int justify; /* choices above */
- int prec; /* prec field, or -1 for all digits */
- int showbase; /* choices above */
- int showpoint; /* if radix point always shown */
- int showtrailing; /* if trailing zeros wanted */
- char sign; /* '+', ' ', or ' ' */
- int width; /* width field */
- };
- #if _GMP_H_HAVE_VA_LIST
- __GMP_DECLSPEC typedef int (*doprnt_format_t) __GMP_PROTO ((void *, const char *, va_list));
- __GMP_DECLSPEC typedef int (*doprnt_memory_t) __GMP_PROTO ((void *, const char *, size_t));
- __GMP_DECLSPEC typedef int (*doprnt_reps_t) __GMP_PROTO ((void *, int, int));
- __GMP_DECLSPEC typedef int (*doprnt_final_t) __GMP_PROTO ((void *));
- struct doprnt_funs_t {
- doprnt_format_t format;
- doprnt_memory_t memory;
- doprnt_reps_t reps;
- doprnt_final_t final; /* NULL if not required */
- };
- extern const struct doprnt_funs_t __gmp_fprintf_funs;
- extern const struct doprnt_funs_t __gmp_sprintf_funs;
- extern const struct doprnt_funs_t __gmp_snprintf_funs;
- extern const struct doprnt_funs_t __gmp_obstack_printf_funs;
- extern const struct doprnt_funs_t __gmp_ostream_funs;
- /* "buf" is a __gmp_allocate_func block of "alloc" many bytes. The first
- "size" of these have been written. "alloc > size" is maintained, so
- there's room to store a ' ' at the end. "result" is where the
- application wants the final block pointer. */
- struct gmp_asprintf_t {
- char **result;
- char *buf;
- size_t size;
- size_t alloc;
- };
- #define GMP_ASPRINTF_T_INIT(d, output)
- do {
- (d).result = (output);
- (d).alloc = 256;
- (d).buf = (char *) (*__gmp_allocate_func) ((d).alloc);
- (d).size = 0;
- } while (0)
- /* If a realloc is necessary, use twice the size actually required, so as to
- avoid repeated small reallocs. */
- #define GMP_ASPRINTF_T_NEED(d, n)
- do {
- size_t alloc, newsize, newalloc;
- ASSERT ((d)->alloc >= (d)->size + 1);
-
- alloc = (d)->alloc;
- newsize = (d)->size + (n);
- if (alloc <= newsize)
- {
- newalloc = 2*newsize;
- (d)->alloc = newalloc;
- (d)->buf = __GMP_REALLOCATE_FUNC_TYPE ((d)->buf,
- alloc, newalloc, char);
- }
- } while (0)
- __GMP_DECLSPEC int __gmp_asprintf_memory __GMP_PROTO ((struct gmp_asprintf_t *, const char *, size_t));
- __GMP_DECLSPEC int __gmp_asprintf_reps __GMP_PROTO ((struct gmp_asprintf_t *, int, int));
- __GMP_DECLSPEC int __gmp_asprintf_final __GMP_PROTO ((struct gmp_asprintf_t *));
- /* buf is where to write the next output, and size is how much space is left
- there. If the application passed size==0 then that's what we'll have
- here, and nothing at all should be written. */
- struct gmp_snprintf_t {
- char *buf;
- size_t size;
- };
- /* Add the bytes printed by the call to the total retval, or bail out on an
- error. */
- #define DOPRNT_ACCUMULATE(call)
- do {
- int __ret;
- __ret = call;
- if (__ret == -1)
- goto error;
- retval += __ret;
- } while (0)
- #define DOPRNT_ACCUMULATE_FUN(fun, params)
- do {
- ASSERT ((fun) != NULL);
- DOPRNT_ACCUMULATE ((*(fun)) params);
- } while (0)
- #define DOPRNT_FORMAT(fmt, ap)
- DOPRNT_ACCUMULATE_FUN (funs->format, (data, fmt, ap))
- #define DOPRNT_MEMORY(ptr, len)
- DOPRNT_ACCUMULATE_FUN (funs->memory, (data, ptr, len))
- #define DOPRNT_REPS(c, n)
- DOPRNT_ACCUMULATE_FUN (funs->reps, (data, c, n))
- #define DOPRNT_STRING(str) DOPRNT_MEMORY (str, strlen (str))
- #define DOPRNT_REPS_MAYBE(c, n)
- do {
- if ((n) != 0)
- DOPRNT_REPS (c, n);
- } while (0)
- #define DOPRNT_MEMORY_MAYBE(ptr, len)
- do {
- if ((len) != 0)
- DOPRNT_MEMORY (ptr, len);
- } while (0)
- __GMP_DECLSPEC int __gmp_doprnt __GMP_PROTO ((const struct doprnt_funs_t *, void *, const char *, va_list));
- __GMP_DECLSPEC int __gmp_doprnt_integer __GMP_PROTO ((const struct doprnt_funs_t *, void *, const struct doprnt_params_t *, const char *));
- #define __gmp_doprnt_mpf __gmp_doprnt_mpf2
- __GMP_DECLSPEC int __gmp_doprnt_mpf __GMP_PROTO ((const struct doprnt_funs_t *, void *, const struct doprnt_params_t *, const char *, mpf_srcptr));
- __GMP_DECLSPEC int __gmp_replacement_vsnprintf __GMP_PROTO ((char *, size_t, const char *, va_list));
- #endif /* _GMP_H_HAVE_VA_LIST */
- typedef int (*gmp_doscan_scan_t) __GMP_PROTO ((void *, const char *, ...));
- typedef void *(*gmp_doscan_step_t) __GMP_PROTO ((void *, int));
- typedef int (*gmp_doscan_get_t) __GMP_PROTO ((void *));
- typedef int (*gmp_doscan_unget_t) __GMP_PROTO ((int, void *));
- struct gmp_doscan_funs_t {
- gmp_doscan_scan_t scan;
- gmp_doscan_step_t step;
- gmp_doscan_get_t get;
- gmp_doscan_unget_t unget;
- };
- extern const struct gmp_doscan_funs_t __gmp_fscanf_funs;
- extern const struct gmp_doscan_funs_t __gmp_sscanf_funs;
- #if _GMP_H_HAVE_VA_LIST
- __GMP_DECLSPEC int __gmp_doscan __GMP_PROTO ((const struct gmp_doscan_funs_t *, void *, const char *, va_list));
- #endif
- /* For testing and debugging. */
- #define MPZ_CHECK_FORMAT(z)
- do {
- ASSERT_ALWAYS (SIZ(z) == 0 || PTR(z)[ABSIZ(z) - 1] != 0);
- ASSERT_ALWAYS (ALLOC(z) >= ABSIZ(z));
- ASSERT_ALWAYS_MPN (PTR(z), ABSIZ(z));
- } while (0)
- #define MPQ_CHECK_FORMAT(q)
- do {
- MPZ_CHECK_FORMAT (mpq_numref (q));
- MPZ_CHECK_FORMAT (mpq_denref (q));
- ASSERT_ALWAYS (SIZ(mpq_denref(q)) >= 1);
-
- if (SIZ(mpq_numref(q)) == 0)
- {
- /* should have zero as 0/1 */
- ASSERT_ALWAYS (SIZ(mpq_denref(q)) == 1
- && PTR(mpq_denref(q))[0] == 1);
- }
- else
- {
- /* should have no common factors */
- mpz_t g;
- mpz_init (g);
- mpz_gcd (g, mpq_numref(q), mpq_denref(q));
- ASSERT_ALWAYS (mpz_cmp_ui (g, 1) == 0);
- mpz_clear (g);
- }
- } while (0)
- #define MPF_CHECK_FORMAT(f)
- do {
- ASSERT_ALWAYS (PREC(f) >= __GMPF_BITS_TO_PREC(53));
- ASSERT_ALWAYS (ABSIZ(f) <= PREC(f)+1);
- if (SIZ(f) == 0)
- ASSERT_ALWAYS (EXP(f) == 0);
- if (SIZ(f) != 0)
- ASSERT_ALWAYS (PTR(f)[ABSIZ(f) - 1] != 0);
- } while (0)
- #define MPZ_PROVOKE_REALLOC(z)
- do { ALLOC(z) = ABSIZ(z); } while (0)
- /* Enhancement: The "mod" and "gcd_1" functions below could have
- __GMP_ATTRIBUTE_PURE, but currently (gcc 3.3) that's not supported on
- function pointers, only actual functions. It probably doesn't make much
- difference to the gmp code, since hopefully we arrange calls so there's
- no great need for the compiler to move things around. */
- #if WANT_FAT_BINARY && (HAVE_HOST_CPU_FAMILY_x86 || HAVE_HOST_CPU_FAMILY_x86_64)
- /* NOTE: The function pointers in this struct are also in CPUVEC_FUNCS_LIST
- in mpn/x86/x86-defs.m4. Be sure to update that when changing here. */
- struct cpuvec_t {
- DECL_add_n ((*add_n));
- DECL_addmul_1 ((*addmul_1));
- DECL_copyd ((*copyd));
- DECL_copyi ((*copyi));
- DECL_divexact_1 ((*divexact_1));
- DECL_divexact_by3c ((*divexact_by3c));
- DECL_divrem_1 ((*divrem_1));
- DECL_gcd_1 ((*gcd_1));
- DECL_lshift ((*lshift));
- DECL_mod_1 ((*mod_1));
- DECL_mod_34lsub1 ((*mod_34lsub1));
- DECL_modexact_1c_odd ((*modexact_1c_odd));
- DECL_mul_1 ((*mul_1));
- DECL_mul_basecase ((*mul_basecase));
- DECL_preinv_divrem_1 ((*preinv_divrem_1));
- DECL_preinv_mod_1 ((*preinv_mod_1));
- DECL_rshift ((*rshift));
- DECL_sqr_basecase ((*sqr_basecase));
- DECL_sub_n ((*sub_n));
- DECL_submul_1 ((*submul_1));
- int initialized;
- mp_size_t mul_toom22_threshold;
- mp_size_t mul_toom33_threshold;
- mp_size_t sqr_toom2_threshold;
- mp_size_t sqr_toom3_threshold;
- };
- __GMP_DECLSPEC extern struct cpuvec_t __gmpn_cpuvec;
- #endif /* x86 fat binary */
- __GMP_DECLSPEC void __gmpn_cpuvec_init __GMP_PROTO ((void));
- /* Get a threshold "field" from __gmpn_cpuvec, running __gmpn_cpuvec_init()
- if that hasn't yet been done (to establish the right values). */
- #define CPUVEC_THRESHOLD(field)
- ((LIKELY (__gmpn_cpuvec.initialized) ? 0 : (__gmpn_cpuvec_init (), 0)),
- __gmpn_cpuvec.field)
- #if HAVE_NATIVE_mpn_add_nc
- #define mpn_add_nc __MPN(add_nc)
- __GMP_DECLSPEC mp_limb_t mpn_add_nc __GMP_PROTO ((mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, mp_limb_t));
- #else
- static inline
- mp_limb_t
- mpn_add_nc (mp_ptr rp, mp_srcptr up, mp_srcptr vp, mp_size_t n, mp_limb_t ci)
- {
- mp_limb_t co;
- co = mpn_add_n (rp, up, vp, n);
- co += mpn_add_1 (rp, rp, n, ci);
- return co;
- }
- #endif
- #if HAVE_NATIVE_mpn_sub_nc
- #define mpn_sub_nc __MPN(sub_nc)
- __GMP_DECLSPEC mp_limb_t mpn_sub_nc __GMP_PROTO ((mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, mp_limb_t));
- #else
- static inline mp_limb_t
- mpn_sub_nc (mp_ptr rp, mp_srcptr up, mp_srcptr vp, mp_size_t n, mp_limb_t ci)
- {
- mp_limb_t co;
- co = mpn_sub_n (rp, up, vp, n);
- co += mpn_sub_1 (rp, rp, n, ci);
- return co;
- }
- #endif
- static inline int
- mpn_zero_p (mp_srcptr ap, mp_size_t n)
- {
- mp_size_t i;
- for (i = n - 1; i >= 0; i--)
- {
- if (ap[i] != 0)
- return 0;
- }
- return 1;
- }
- #if TUNE_PROGRAM_BUILD
- /* Some extras wanted when recompiling some .c files for use by the tune
- program. Not part of a normal build.
- It's necessary to keep these thresholds as #defines (just to an
- identically named variable), since various defaults are established based
- on #ifdef in the .c files. For some this is not so (the defaults are
- instead established above), but all are done this way for consistency. */
- #undef MUL_TOOM22_THRESHOLD
- #define MUL_TOOM22_THRESHOLD mul_toom22_threshold
- extern mp_size_t mul_toom22_threshold;
- #undef MUL_TOOM33_THRESHOLD
- #define MUL_TOOM33_THRESHOLD mul_toom33_threshold
- extern mp_size_t mul_toom33_threshold;
- #undef MUL_TOOM44_THRESHOLD
- #define MUL_TOOM44_THRESHOLD mul_toom44_threshold
- extern mp_size_t mul_toom44_threshold;
- #undef MUL_TOOM6H_THRESHOLD
- #define MUL_TOOM6H_THRESHOLD mul_toom6h_threshold
- extern mp_size_t mul_toom6h_threshold;
- #undef MUL_TOOM8H_THRESHOLD
- #define MUL_TOOM8H_THRESHOLD mul_toom8h_threshold
- extern mp_size_t mul_toom8h_threshold;
- #undef MUL_TOOM32_TO_TOOM43_THRESHOLD
- #define MUL_TOOM32_TO_TOOM43_THRESHOLD mul_toom32_to_toom43_threshold
- extern mp_size_t mul_toom32_to_toom43_threshold;
- #undef MUL_TOOM32_TO_TOOM53_THRESHOLD
- #define MUL_TOOM32_TO_TOOM53_THRESHOLD mul_toom32_to_toom53_threshold
- extern mp_size_t mul_toom32_to_toom53_threshold;
- #undef MUL_TOOM42_TO_TOOM53_THRESHOLD
- #define MUL_TOOM42_TO_TOOM53_THRESHOLD mul_toom42_to_toom53_threshold
- extern mp_size_t mul_toom42_to_toom53_threshold;
- #undef MUL_TOOM42_TO_TOOM63_THRESHOLD
- #define MUL_TOOM42_TO_TOOM63_THRESHOLD mul_toom42_to_toom63_threshold
- extern mp_size_t mul_toom42_to_toom63_threshold;
- #undef MUL_FFT_THRESHOLD
- #define MUL_FFT_THRESHOLD mul_fft_threshold
- extern mp_size_t mul_fft_threshold;
- #undef MUL_FFT_MODF_THRESHOLD
- #define MUL_FFT_MODF_THRESHOLD mul_fft_modf_threshold
- extern mp_size_t mul_fft_modf_threshold;
- #undef MUL_FFT_TABLE
- #define MUL_FFT_TABLE { 0 }
- #undef MUL_FFT_TABLE3
- #define MUL_FFT_TABLE3 { {0,0} }
- /* A native mpn_sqr_basecase is not tuned and SQR_BASECASE_THRESHOLD should
- remain as zero (always use it). */
- #if ! HAVE_NATIVE_mpn_sqr_basecase
- #undef SQR_BASECASE_THRESHOLD
- #define SQR_BASECASE_THRESHOLD sqr_basecase_threshold
- extern mp_size_t sqr_basecase_threshold;
- #endif
- #if TUNE_PROGRAM_BUILD_SQR
- #undef SQR_TOOM2_THRESHOLD
- #define SQR_TOOM2_THRESHOLD SQR_TOOM2_MAX_GENERIC
- #else
- #undef SQR_TOOM2_THRESHOLD
- #define SQR_TOOM2_THRESHOLD sqr_toom2_threshold
- extern mp_size_t sqr_toom2_threshold;
- #endif
- #undef SQR_TOOM3_THRESHOLD
- #define SQR_TOOM3_THRESHOLD sqr_toom3_threshold
- extern mp_size_t sqr_toom3_threshold;
- #undef SQR_TOOM4_THRESHOLD
- #define SQR_TOOM4_THRESHOLD sqr_toom4_threshold
- extern mp_size_t sqr_toom4_threshold;
- #undef SQR_TOOM6_THRESHOLD
- #define SQR_TOOM6_THRESHOLD sqr_toom6_threshold
- extern mp_size_t sqr_toom6_threshold;
- #undef SQR_TOOM8_THRESHOLD
- #define SQR_TOOM8_THRESHOLD sqr_toom8_threshold
- extern mp_size_t sqr_toom8_threshold;
- #undef SQR_FFT_THRESHOLD
- #define SQR_FFT_THRESHOLD sqr_fft_threshold
- extern mp_size_t sqr_fft_threshold;
- #undef SQR_FFT_MODF_THRESHOLD
- #define SQR_FFT_MODF_THRESHOLD sqr_fft_modf_threshold
- extern mp_size_t sqr_fft_modf_threshold;
- #undef SQR_FFT_TABLE
- #define SQR_FFT_TABLE { 0 }
- #undef SQR_FFT_TABLE3
- #define SQR_FFT_TABLE3 { {0,0} }
- #undef MULLO_BASECASE_THRESHOLD
- #define MULLO_BASECASE_THRESHOLD mullo_basecase_threshold
- extern mp_size_t mullo_basecase_threshold;
- #undef MULLO_DC_THRESHOLD
- #define MULLO_DC_THRESHOLD mullo_dc_threshold
- extern mp_size_t mullo_dc_threshold;
- #undef MULLO_MUL_N_THRESHOLD
- #define MULLO_MUL_N_THRESHOLD mullo_mul_n_threshold
- extern mp_size_t mullo_mul_n_threshold;
- #undef DC_DIV_QR_THRESHOLD
- #define DC_DIV_QR_THRESHOLD dc_div_qr_threshold
- extern mp_size_t dc_div_qr_threshold;
- #undef DC_DIVAPPR_Q_THRESHOLD
- #define DC_DIVAPPR_Q_THRESHOLD dc_divappr_q_threshold
- extern mp_size_t dc_divappr_q_threshold;
- #undef DC_BDIV_Q_THRESHOLD
- #define DC_BDIV_Q_THRESHOLD dc_bdiv_q_threshold
- extern mp_size_t dc_bdiv_q_threshold;
- #undef DC_BDIV_QR_THRESHOLD
- #define DC_BDIV_QR_THRESHOLD dc_bdiv_qr_threshold
- extern mp_size_t dc_bdiv_qr_threshold;
- #undef MU_DIV_QR_THRESHOLD
- #define MU_DIV_QR_THRESHOLD mu_div_qr_threshold
- extern mp_size_t mu_div_qr_threshold;
- #undef MU_DIVAPPR_Q_THRESHOLD
- #define MU_DIVAPPR_Q_THRESHOLD mu_divappr_q_threshold
- extern mp_size_t mu_divappr_q_threshold;
- #undef MUPI_DIV_QR_THRESHOLD
- #define MUPI_DIV_QR_THRESHOLD mupi_div_qr_threshold
- extern mp_size_t mupi_div_qr_threshold;
- #undef MU_BDIV_QR_THRESHOLD
- #define MU_BDIV_QR_THRESHOLD mu_bdiv_qr_threshold
- extern mp_size_t mu_bdiv_qr_threshold;
- #undef MU_BDIV_Q_THRESHOLD
- #define MU_BDIV_Q_THRESHOLD mu_bdiv_q_threshold
- extern mp_size_t mu_bdiv_q_threshold;
- #undef INV_MULMOD_BNM1_THRESHOLD
- #define INV_MULMOD_BNM1_THRESHOLD inv_mulmod_bnm1_threshold
- extern mp_size_t inv_mulmod_bnm1_threshold;
- #undef INV_NEWTON_THRESHOLD
- #define INV_NEWTON_THRESHOLD inv_newton_threshold
- extern mp_size_t inv_newton_threshold;
- #undef INV_APPR_THRESHOLD
- #define INV_APPR_THRESHOLD inv_appr_threshold
- extern mp_size_t inv_appr_threshold;
- #undef BINV_NEWTON_THRESHOLD
- #define BINV_NEWTON_THRESHOLD binv_newton_threshold
- extern mp_size_t binv_newton_threshold;
- #undef REDC_1_TO_REDC_2_THRESHOLD
- #define REDC_1_TO_REDC_2_THRESHOLD redc_1_to_redc_2_threshold
- extern mp_size_t redc_1_to_redc_2_threshold;
- #undef REDC_2_TO_REDC_N_THRESHOLD
- #define REDC_2_TO_REDC_N_THRESHOLD redc_2_to_redc_n_threshold
- extern mp_size_t redc_2_to_redc_n_threshold;
- #undef REDC_1_TO_REDC_N_THRESHOLD
- #define REDC_1_TO_REDC_N_THRESHOLD redc_1_to_redc_n_threshold
- extern mp_size_t redc_1_to_redc_n_threshold;
- #undef MATRIX22_STRASSEN_THRESHOLD
- #define MATRIX22_STRASSEN_THRESHOLD matrix22_strassen_threshold
- extern mp_size_t matrix22_strassen_threshold;
- #undef HGCD_THRESHOLD
- #define HGCD_THRESHOLD hgcd_threshold
- extern mp_size_t hgcd_threshold;
- #undef GCD_DC_THRESHOLD
- #define GCD_DC_THRESHOLD gcd_dc_threshold
- extern mp_size_t gcd_dc_threshold;
- #undef GCDEXT_DC_THRESHOLD
- #define GCDEXT_DC_THRESHOLD gcdext_dc_threshold
- extern mp_size_t gcdext_dc_threshold;
- #undef DIVREM_1_NORM_THRESHOLD
- #define DIVREM_1_NORM_THRESHOLD divrem_1_norm_threshold
- extern mp_size_t divrem_1_norm_threshold;
- #undef DIVREM_1_UNNORM_THRESHOLD
- #define DIVREM_1_UNNORM_THRESHOLD divrem_1_unnorm_threshold
- extern mp_size_t divrem_1_unnorm_threshold;
- #undef MOD_1_NORM_THRESHOLD
- #define MOD_1_NORM_THRESHOLD mod_1_norm_threshold
- extern mp_size_t mod_1_norm_threshold;
- #undef MOD_1_UNNORM_THRESHOLD
- #define MOD_1_UNNORM_THRESHOLD mod_1_unnorm_threshold
- extern mp_size_t mod_1_unnorm_threshold;
- #undef MOD_1N_TO_MOD_1_1_THRESHOLD
- #define MOD_1N_TO_MOD_1_1_THRESHOLD mod_1n_to_mod_1_1_threshold
- extern mp_size_t mod_1n_to_mod_1_1_threshold;
- #undef MOD_1U_TO_MOD_1_1_THRESHOLD
- #define MOD_1U_TO_MOD_1_1_THRESHOLD mod_1u_to_mod_1_1_threshold
- extern mp_size_t mod_1u_to_mod_1_1_threshold;
- #undef MOD_1_1_TO_MOD_1_2_THRESHOLD
- #define MOD_1_1_TO_MOD_1_2_THRESHOLD mod_1_1_to_mod_1_2_threshold
- extern mp_size_t mod_1_1_to_mod_1_2_threshold;
- #undef MOD_1_2_TO_MOD_1_4_THRESHOLD
- #define MOD_1_2_TO_MOD_1_4_THRESHOLD mod_1_2_to_mod_1_4_threshold
- extern mp_size_t mod_1_2_to_mod_1_4_threshold;
- #undef PREINV_MOD_1_TO_MOD_1_THRESHOLD
- #define PREINV_MOD_1_TO_MOD_1_THRESHOLD preinv_mod_1_to_mod_1_threshold
- extern mp_size_t preinv_mod_1_to_mod_1_threshold;
- #if ! UDIV_PREINV_ALWAYS
- #undef DIVREM_2_THRESHOLD
- #define DIVREM_2_THRESHOLD divrem_2_threshold
- extern mp_size_t divrem_2_threshold;
- #endif
- #undef MULMOD_BNM1_THRESHOLD
- #define MULMOD_BNM1_THRESHOLD mulmod_bnm1_threshold
- extern mp_size_t mulmod_bnm1_threshold;
- #undef SQRMOD_BNM1_THRESHOLD
- #define SQRMOD_BNM1_THRESHOLD sqrmod_bnm1_threshold
- extern mp_size_t sqrmod_bnm1_threshold;
- #undef GET_STR_DC_THRESHOLD
- #define GET_STR_DC_THRESHOLD get_str_dc_threshold
- extern mp_size_t get_str_dc_threshold;
- #undef GET_STR_PRECOMPUTE_THRESHOLD
- #define GET_STR_PRECOMPUTE_THRESHOLD get_str_precompute_threshold
- extern mp_size_t get_str_precompute_threshold;
- #undef SET_STR_DC_THRESHOLD
- #define SET_STR_DC_THRESHOLD set_str_dc_threshold
- extern mp_size_t set_str_dc_threshold;
- #undef SET_STR_PRECOMPUTE_THRESHOLD
- #define SET_STR_PRECOMPUTE_THRESHOLD set_str_precompute_threshold
- extern mp_size_t set_str_precompute_threshold;
- #undef FFT_TABLE_ATTRS
- #define FFT_TABLE_ATTRS
- extern mp_size_t mpn_fft_table[2][MPN_FFT_TABLE_SIZE];
- #define FFT_TABLE3_SIZE 2000 /* generous space for tuning */
- extern struct fft_table_nk mpn_fft_table3[2][FFT_TABLE3_SIZE];
- /* Sizes the tune program tests up to, used in a couple of recompilations. */
- #undef MUL_TOOM22_THRESHOLD_LIMIT
- #undef MUL_TOOM33_THRESHOLD_LIMIT
- #undef MULLO_BASECASE_THRESHOLD_LIMIT
- #undef SQR_TOOM3_THRESHOLD_LIMIT
- #define SQR_TOOM2_MAX_GENERIC 200
- #define MUL_TOOM22_THRESHOLD_LIMIT 700
- #define MUL_TOOM33_THRESHOLD_LIMIT 700
- #define SQR_TOOM3_THRESHOLD_LIMIT 400
- #define MUL_TOOM44_THRESHOLD_LIMIT 1000
- #define SQR_TOOM4_THRESHOLD_LIMIT 1000
- #define MUL_TOOM6H_THRESHOLD_LIMIT 1100
- #define SQR_TOOM6_THRESHOLD_LIMIT 1100
- #define MUL_TOOM8H_THRESHOLD_LIMIT 1200
- #define SQR_TOOM8_THRESHOLD_LIMIT 1200
- #define MULLO_BASECASE_THRESHOLD_LIMIT 200
- #define GET_STR_THRESHOLD_LIMIT 150
- #endif /* TUNE_PROGRAM_BUILD */
- #if defined (__cplusplus)
- }
- #endif
- /* FIXME: Make these itch functions less conservative. Also consider making
- them dependent on just 'an', and compute the allocation directly from 'an'
- instead of via n. */
- /* toom22/toom2: Scratch need is 2*(an + k), k is the recursion depth.
- k is ths smallest k such that
- ceil(an/2^k) < MUL_TOOM22_THRESHOLD.
- which implies that
- k = bitsize of floor ((an-1)/(MUL_TOOM22_THRESHOLD-1))
- = 1 + floor (log_2 (floor ((an-1)/(MUL_TOOM22_THRESHOLD-1))))
- */
- #define mpn_toom22_mul_itch(an, bn)
- (2 * ((an) + GMP_NUMB_BITS))
- #define mpn_toom2_sqr_itch(an)
- (2 * ((an) + GMP_NUMB_BITS))
- /* Can probably be trimmed to 2 an + O(log an). */
- #define mpn_toom33_mul_itch(an, bn)
- ((5 * (an) >> 1) + GMP_NUMB_BITS)
- #define mpn_toom3_sqr_itch(an)
- ((5 * (an) >> 1) + GMP_NUMB_BITS)
- #define mpn_toom44_mul_itch(an, bn)
- (3 * (an) + GMP_NUMB_BITS)
- #define mpn_toom4_sqr_itch(an)
- (3 * (an) + GMP_NUMB_BITS)
- #define mpn_toom6_sqr_itch(n)
- ( ((n) - SQR_TOOM6_THRESHOLD)*2 +
- MAX(SQR_TOOM6_THRESHOLD*2 + GMP_NUMB_BITS*6,
- mpn_toom4_sqr_itch(SQR_TOOM6_THRESHOLD)) )
- #define mpn_toom6_mul_n_itch(n)
- ( ((n) - MUL_TOOM6H_THRESHOLD)*2 +
- MAX(MUL_TOOM6H_THRESHOLD*2 + GMP_NUMB_BITS*6,
- mpn_toom44_mul_itch(MUL_TOOM6H_THRESHOLD,MUL_TOOM6H_THRESHOLD)) )
- static inline mp_size_t
- mpn_toom6h_mul_itch (mp_size_t an, mp_size_t bn) {
- mp_size_t estimatedN;
- estimatedN = (an + bn) / (size_t) 10 + 1;
- return mpn_toom6_mul_n_itch (estimatedN * 6);
- }
- #define mpn_toom8_sqr_itch(n)
- ( (((n)*15)>>3) - ((SQR_TOOM8_THRESHOLD*15)>>3) +
- MAX(((SQR_TOOM8_THRESHOLD*15)>>3) + GMP_NUMB_BITS*6,
- mpn_toom6_sqr_itch(SQR_TOOM8_THRESHOLD)) )
- #define mpn_toom8_mul_n_itch(n)
- ( (((n)*15)>>3) - ((MUL_TOOM8H_THRESHOLD*15)>>3) +
- MAX(((MUL_TOOM8H_THRESHOLD*15)>>3) + GMP_NUMB_BITS*6,
- mpn_toom6_mul_n_itch(MUL_TOOM8H_THRESHOLD)) )
- static inline mp_size_t
- mpn_toom8h_mul_itch (mp_size_t an, mp_size_t bn) {
- mp_size_t estimatedN;
- estimatedN = (an + bn) / (size_t) 14 + 1;
- return mpn_toom8_mul_n_itch (estimatedN * 8);
- }
- static inline mp_size_t
- mpn_toom32_mul_itch (mp_size_t an, mp_size_t bn)
- {
- mp_size_t n = 1 + (2 * an >= 3 * bn ? (an - 1) / (size_t) 3 : (bn - 1) >> 1);
- mp_size_t itch = 2 * n + 1;
- return itch;
- }
- static inline mp_size_t
- mpn_toom42_mul_itch (mp_size_t an, mp_size_t bn)
- {
- mp_size_t n = an >= 2 * bn ? (an + 3) >> 2 : (bn + 1) >> 1;
- return 6 * n + 3;
- }
- static inline mp_size_t
- mpn_toom43_mul_itch (mp_size_t an, mp_size_t bn)
- {
- mp_size_t n = 1 + (3 * an >= 4 * bn ? (an - 1) >> 2 : (bn - 1) / (size_t) 3);
- return 6*n + 4;
- }
- static inline mp_size_t
- mpn_toom52_mul_itch (mp_size_t an, mp_size_t bn)
- {
- mp_size_t n = 1 + (2 * an >= 5 * bn ? (an - 1) / (size_t) 5 : (bn - 1) >> 1);
- return 6*n + 4;
- }
- static inline mp_size_t
- mpn_toom53_mul_itch (mp_size_t an, mp_size_t bn)
- {
- mp_size_t n = 1 + (3 * an >= 5 * bn ? (an - 1) / (size_t) 5 : (bn - 1) / (size_t) 3);
- return 10 * n + 10;
- }
- static inline mp_size_t
- mpn_toom62_mul_itch (mp_size_t an, mp_size_t bn)
- {
- mp_size_t n = 1 + (an >= 3 * bn ? (an - 1) / (size_t) 6 : (bn - 1) >> 1);
- return 10 * n + 10;
- }
- static inline mp_size_t
- mpn_toom63_mul_itch (mp_size_t an, mp_size_t bn)
- {
- mp_size_t n = 1 + (an >= 2 * bn ? (an - 1) / (size_t) 6 : (bn - 1) / (size_t) 3);
- return 9 * n + 3;
- }
- #if 0
- #define mpn_fft_mul mpn_mul_fft_full
- #else
- #define mpn_fft_mul mpn_nussbaumer_mul
- #endif
- #ifdef __cplusplus
- /* A little helper for a null-terminated __gmp_allocate_func string.
- The destructor ensures it's freed even if an exception is thrown.
- The len field is needed by the destructor, and can be used by anyone else
- to avoid a second strlen pass over the data.
- Since our input is a C string, using strlen is correct. Perhaps it'd be
- more C++-ish style to use std::char_traits<char>::length, but char_traits
- isn't available in gcc 2.95.4. */
- class gmp_allocated_string {
- public:
- char *str;
- size_t len;
- gmp_allocated_string(char *arg)
- {
- str = arg;
- len = std::strlen (str);
- }
- ~gmp_allocated_string()
- {
- (*__gmp_free_func) (str, len+1);
- }
- };
- std::istream &__gmpz_operator_in_nowhite (std::istream &, mpz_ptr, char);
- int __gmp_istream_set_base (std::istream &, char &, bool &, bool &);
- void __gmp_istream_set_digits (std::string &, std::istream &, char &, bool &, int);
- void __gmp_doprnt_params_from_ios (struct doprnt_params_t *p, std::ios &o);
- std::ostream& __gmp_doprnt_integer_ostream (std::ostream &o, struct doprnt_params_t *p, char *s);
- extern const struct doprnt_funs_t __gmp_asprintf_funs_noformat;
- #endif /* __cplusplus */
- #endif /* __GMP_IMPL_H__ */