diff options
Diffstat (limited to 'Build/source/libs/gmp/gmp-src/mpz')
156 files changed, 1591 insertions, 1150 deletions
diff --git a/Build/source/libs/gmp/gmp-src/mpz/2fac_ui.c b/Build/source/libs/gmp/gmp-src/mpz/2fac_ui.c index 37e6c468bc8..141a0a7ebc8 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/2fac_ui.c +++ b/Build/source/libs/gmp/gmp-src/mpz/2fac_ui.c @@ -2,7 +2,7 @@ Contributed to the GNU project by Marco Bodrato. -Copyright 2012 Free Software Foundation, Inc. +Copyright 2012, 2015, 2018 Free Software Foundation, Inc. This file is part of the GNU MP Library. @@ -30,7 +30,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" #define FACTOR_LIST_STORE(P, PR, MAX_PR, VEC, I) \ @@ -67,10 +66,11 @@ mpz_2fac_ui (mpz_ptr x, unsigned long n) mpz_mul_2exp (x, x, count); } else { /* n is odd */ if (n <= ODD_DOUBLEFACTORIAL_TABLE_LIMIT) { - PTR (x)[0] = __gmp_odd2fac_table[n >> 1]; - SIZ (x) = 1; + MPZ_NEWALLOC (x, 1)[0] = __gmp_odd2fac_table[n >> 1]; + SIZ (x) = 1; } else if (BELOW_THRESHOLD (n, FAC_2DSC_THRESHOLD)) { /* odd basecase, */ - mp_limb_t *factors, prod, max_prod, j; + mp_limb_t *factors, prod, max_prod; + mp_size_t j; TMP_SDECL; /* FIXME: we might alloc a fixed amount 1+FAC_2DSC_THRESHOLD/FACTORS_PER_LIMB */ diff --git a/Build/source/libs/gmp/gmp-src/mpz/Makefile.am b/Build/source/libs/gmp/gmp-src/mpz/Makefile.am index 3ff60ac2e9f..a5e1f57200b 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/Makefile.am +++ b/Build/source/libs/gmp/gmp-src/mpz/Makefile.am @@ -54,14 +54,15 @@ libmpz_la_SOURCES = aors.h aors_ui.h fits_s.h mul_i.h \ invert.c ior.c iset.c iset_d.c iset_si.c iset_str.c iset_ui.c \ jacobi.c kronsz.c kronuz.c kronzs.c kronzu.c \ lcm.c lcm_ui.c limbs_read.c limbs_write.c limbs_modify.c limbs_finish.c \ - lucnum_ui.c lucnum2_ui.c mfac_uiui.c millerrabin.c \ + lucnum_ui.c lucnum2_ui.c lucmod.c mfac_uiui.c millerrabin.c \ mod.c mul.c mul_2exp.c mul_si.c mul_ui.c n_pow_ui.c neg.c nextprime.c \ oddfac_1.c \ out_raw.c out_str.c perfpow.c perfsqr.c popcount.c pow_ui.c powm.c \ powm_sec.c powm_ui.c pprime_p.c prodlimbs.c primorial_ui.c random.c random2.c \ realloc.c realloc2.c remove.c roinit_n.c root.c rootrem.c rrandomb.c \ scan0.c scan1.c set.c set_d.c set_f.c set_q.c set_si.c set_str.c \ - set_ui.c setbit.c size.c sizeinbase.c sqrt.c sqrtrem.c sub.c sub_ui.c \ + set_ui.c setbit.c size.c sizeinbase.c sqrt.c sqrtrem.c stronglucas.c \ + sub.c sub_ui.c \ swap.c tdiv_ui.c tdiv_q.c tdiv_q_2exp.c tdiv_q_ui.c tdiv_qr.c \ tdiv_qr_ui.c tdiv_r.c tdiv_r_2exp.c tdiv_r_ui.c tstbit.c ui_pow_ui.c \ ui_sub.c urandomb.c urandomm.c xor.c diff --git a/Build/source/libs/gmp/gmp-src/mpz/abs.c b/Build/source/libs/gmp/gmp-src/mpz/abs.c index 81c6b632668..0cfbc49ae4c 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/abs.c +++ b/Build/source/libs/gmp/gmp-src/mpz/abs.c @@ -30,7 +30,6 @@ see https://www.gnu.org/licenses/. */ #define __GMP_FORCE_mpz_abs 1 -#include "gmp.h" #include "gmp-impl.h" void diff --git a/Build/source/libs/gmp/gmp-src/mpz/and.c b/Build/source/libs/gmp/gmp-src/mpz/and.c index 5aa01a71da1..5d345477589 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/and.c +++ b/Build/source/libs/gmp/gmp-src/mpz/and.c @@ -1,7 +1,7 @@ /* mpz_and -- Logical and. -Copyright 1991, 1993, 1994, 1996, 1997, 2000, 2001, 2003, 2005, 2012 Free -Software Foundation, Inc. +Copyright 1991, 1993, 1994, 1996, 1997, 2000, 2001, 2003, 2005, 2012, +2015-2018 Free Software Foundation, Inc. This file is part of the GNU MP Library. @@ -29,7 +29,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" void @@ -40,49 +39,47 @@ mpz_and (mpz_ptr res, mpz_srcptr op1, mpz_srcptr op2) mp_ptr res_ptr; mp_size_t res_size; mp_size_t i; - TMP_DECL; - TMP_MARK; op1_size = SIZ(op1); op2_size = SIZ(op2); + if (op1_size < op2_size) + { + MPZ_SRCPTR_SWAP (op1, op2); + MP_SIZE_T_SWAP (op1_size, op2_size); + } + op1_ptr = PTR(op1); op2_ptr = PTR(op2); - if (op1_size >= 0) + if (op2_size >= 0) { - if (op2_size >= 0) - { - res_size = MIN (op1_size, op2_size); - /* First loop finds the size of the result. */ - for (i = res_size - 1; i >= 0; i--) - if ((op1_ptr[i] & op2_ptr[i]) != 0) - break; - res_size = i + 1; - - /* Handle allocation, now then we know exactly how much space is - needed for the result. */ - res_ptr = MPZ_REALLOC (res, res_size); - /* Don't re-read op1_ptr and op2_ptr. Since res_size <= - MIN(op1_size, op2_size), res is not changed when op1 - is identical to res or op2 is identical to res. */ - - SIZ(res) = res_size; - if (LIKELY (res_size != 0)) - mpn_and_n (res_ptr, op1_ptr, op2_ptr, res_size); - return; - } - else /* op2_size < 0 */ - { - /* Fall through to the code at the end of the function. */ - } + /* First loop finds the size of the result. */ + for (i = op2_size; --i >= 0;) + if ((op1_ptr[i] & op2_ptr[i]) != 0) + { + res_size = i + 1; + /* Handle allocation, now then we know exactly how much space is + needed for the result. */ + /* Don't re-read op1_ptr and op2_ptr. Since res_size <= + MIN(op1_size, op2_size), res is not changed when op1 + is identical to res or op2 is identical to res. */ + SIZ (res) = res_size; + mpn_and_n (MPZ_NEWALLOC (res, res_size), op1_ptr, op2_ptr, res_size); + return; + } + + SIZ (res) = 0; } else { - if (op2_size < 0) + TMP_DECL; + + op2_size = -op2_size; + TMP_MARK; + if (op1_size < 0) { mp_ptr opx, opy; - mp_limb_t cy; /* Both operands are negative, so will be the result. -((-OP1) & (-OP2)) = -(~(OP1 - 1) & ~(OP2 - 1)) = @@ -95,10 +92,6 @@ mpz_and (mpz_ptr res, mpz_srcptr op1, mpz_srcptr op2) would get carry into the zero-limb in this situation... */ op1_size = -op1_size; - op2_size = -op2_size; - - if (op1_size > op2_size) - MPN_SRCPTR_SWAP (op1_ptr, op1_size, op2_ptr, op2_size); TMP_ALLOC_LIMBS_2 (opx, op1_size, opy, op2_size); mpn_sub_1 (opx, op1_ptr, op1_size, (mp_limb_t) 1); @@ -107,7 +100,7 @@ mpz_and (mpz_ptr res, mpz_srcptr op1, mpz_srcptr op2) mpn_sub_1 (opy, op2_ptr, op2_size, (mp_limb_t) 1); op2_ptr = opy; - res_ptr = MPZ_REALLOC (res, 1 + op2_size); + res_ptr = MPZ_NEWALLOC (res, 1 + op2_size); /* Don't re-read OP1_PTR and OP2_PTR. They point to temporary space--never to the space PTR(res) used to point to before reallocation. */ @@ -115,130 +108,115 @@ mpz_and (mpz_ptr res, mpz_srcptr op1, mpz_srcptr op2) MPN_COPY (res_ptr + op1_size, op2_ptr + op1_size, op2_size - op1_size); mpn_ior_n (res_ptr, op1_ptr, op2_ptr, op1_size); + TMP_FREE; res_size = op2_size; - cy = mpn_add_1 (res_ptr, res_ptr, res_size, (mp_limb_t) 1); - res_ptr[res_size] = cy; - res_size += (cy != 0); + res_ptr[res_size] = 0; + MPN_INCR_U (res_ptr, res_size + 1, (mp_limb_t) 1); + res_size += res_ptr[res_size]; SIZ(res) = -res_size; - TMP_FREE; - return; } else { - /* We should compute -OP1 & OP2. Swap OP1 and OP2 and fall - through to the code that handles OP1 & -OP2. */ - MPN_SRCPTR_SWAP (op1_ptr, op1_size, op2_ptr, op2_size); - } - - } - - { #if ANDNEW - mp_size_t op2_lim; - mp_size_t count; - - /* OP2 must be negated as with infinite precision. - - Scan from the low end for a non-zero limb. The first non-zero - limb is simply negated (two's complement). Any subsequent - limbs are one's complemented. Of course, we don't need to - handle more limbs than there are limbs in the other, positive - operand as the result for those limbs is going to become zero - anyway. */ - - /* Scan for the least significant non-zero OP2 limb, and zero the - result meanwhile for those limb positions. (We will surely - find a non-zero limb, so we can write the loop with one - termination condition only.) */ - for (i = 0; op2_ptr[i] == 0; i++) - res_ptr[i] = 0; - op2_lim = i; - - op2_size = -op2_size; - - if (op1_size <= op2_size) - { - /* The ones-extended OP2 is >= than the zero-extended OP1. - RES_SIZE <= OP1_SIZE. Find the exact size. */ - for (i = op1_size - 1; i > op2_lim; i--) - if ((op1_ptr[i] & ~op2_ptr[i]) != 0) - break; - res_size = i + 1; - for (i = res_size - 1; i > op2_lim; i--) - res_ptr[i] = op1_ptr[i] & ~op2_ptr[i]; - res_ptr[op2_lim] = op1_ptr[op2_lim] & -op2_ptr[op2_lim]; - /* Yes, this *can* happen! */ - MPN_NORMALIZE (res_ptr, res_size); - } - else - { - /* The ones-extended OP2 is < than the zero-extended OP1. - RES_SIZE == OP1_SIZE, since OP1 is normalized. */ - res_size = op1_size; - MPN_COPY (res_ptr + op2_size, op1_ptr + op2_size, op1_size - op2_size); - for (i = op2_size - 1; i > op2_lim; i--) - res_ptr[i] = op1_ptr[i] & ~op2_ptr[i]; - res_ptr[op2_lim] = op1_ptr[op2_lim] & -op2_ptr[op2_lim]; - } - - SIZ(res) = res_size; + mp_size_t op2_lim; + mp_size_t count; + + /* OP2 must be negated as with infinite precision. + + Scan from the low end for a non-zero limb. The first non-zero + limb is simply negated (two's complement). Any subsequent + limbs are one's complemented. Of course, we don't need to + handle more limbs than there are limbs in the other, positive + operand as the result for those limbs is going to become zero + anyway. */ + + /* Scan for the least significant non-zero OP2 limb, and zero the + result meanwhile for those limb positions. (We will surely + find a non-zero limb, so we can write the loop with one + termination condition only.) */ + for (i = 0; op2_ptr[i] == 0; i++) + res_ptr[i] = 0; + op2_lim = i; + + if (op1_size <= op2_size) + { + /* The ones-extended OP2 is >= than the zero-extended OP1. + RES_SIZE <= OP1_SIZE. Find the exact size. */ + for (i = op1_size - 1; i > op2_lim; i--) + if ((op1_ptr[i] & ~op2_ptr[i]) != 0) + break; + res_size = i + 1; + for (i = res_size - 1; i > op2_lim; i--) + res_ptr[i] = op1_ptr[i] & ~op2_ptr[i]; + res_ptr[op2_lim] = op1_ptr[op2_lim] & -op2_ptr[op2_lim]; + /* Yes, this *can* happen! */ + MPN_NORMALIZE (res_ptr, res_size); + } + else + { + /* The ones-extended OP2 is < than the zero-extended OP1. + RES_SIZE == OP1_SIZE, since OP1 is normalized. */ + res_size = op1_size; + MPN_COPY (res_ptr + op2_size, op1_ptr + op2_size, op1_size - op2_size); + for (i = op2_size - 1; i > op2_lim; i--) + res_ptr[i] = op1_ptr[i] & ~op2_ptr[i]; + res_ptr[op2_lim] = op1_ptr[op2_lim] & -op2_ptr[op2_lim]; + } #else - /* OP1 is positive and zero-extended, - OP2 is negative and ones-extended. - The result will be positive. - OP1 & -OP2 = OP1 & ~(OP2 - 1). */ - - mp_ptr opx; - - op2_size = -op2_size; - opx = TMP_ALLOC_LIMBS (op2_size); - mpn_sub_1 (opx, op2_ptr, op2_size, (mp_limb_t) 1); - op2_ptr = opx; - - if (op1_size > op2_size) - { - /* The result has the same size as OP1, since OP1 is normalized - and longer than the ones-extended OP2. */ - res_size = op1_size; - - /* Handle allocation, now then we know exactly how much space is - needed for the result. */ - res_ptr = MPZ_REALLOC (res, res_size); - /* Don't re-read OP1_PTR or OP2_PTR. Since res_size = op1_size, - op1 is not changed if it is identical to res. - OP2_PTR points to temporary space. */ - - MPN_COPY (res_ptr + op2_size, op1_ptr + op2_size, res_size - op2_size); - mpn_andn_n (res_ptr, op1_ptr, op2_ptr, op2_size); - - SIZ(res) = res_size; - } - else - { - /* Find out the exact result size. Ignore the high limbs of OP2, - OP1 is zero-extended and would make the result zero. */ - for (i = op1_size - 1; i >= 0; i--) - if ((op1_ptr[i] & ~op2_ptr[i]) != 0) - break; - res_size = i + 1; - - /* Handle allocation, now then we know exactly how much space is - needed for the result. */ - res_ptr = MPZ_REALLOC (res, res_size); - /* Don't re-read OP1_PTR. Since res_size <= op1_size, - op1 is not changed if it is identical to res. - Don't re-read OP2_PTR. It points to temporary space--never - to the space PTR(res) used to point to before reallocation. */ - - if (LIKELY (res_size != 0)) - mpn_andn_n (res_ptr, op1_ptr, op2_ptr, res_size); - - SIZ(res) = res_size; - } + /* OP1 is positive and zero-extended, + OP2 is negative and ones-extended. + The result will be positive. + OP1 & -OP2 = OP1 & ~(OP2 - 1). */ + + mp_ptr opx; + + opx = TMP_ALLOC_LIMBS (op2_size); + mpn_sub_1 (opx, op2_ptr, op2_size, (mp_limb_t) 1); + op2_ptr = opx; + + if (op1_size > op2_size) + { + /* The result has the same size as OP1, since OP1 is normalized + and longer than the ones-extended OP2. */ + res_size = op1_size; + + /* Handle allocation, now then we know exactly how much space is + needed for the result. */ + res_ptr = MPZ_NEWALLOC (res, res_size); + /* Don't re-read OP1_PTR or OP2_PTR. Since res_size = op1_size, + op1 is not changed if it is identical to res. + OP2_PTR points to temporary space. */ + + mpn_andn_n (res_ptr, op1_ptr, op2_ptr, op2_size); + MPN_COPY (res_ptr + op2_size, op1_ptr + op2_size, res_size - op2_size); + } + else + { + /* Find out the exact result size. Ignore the high limbs of OP2, + OP1 is zero-extended and would make the result zero. */ + res_size = 0; + for (i = op1_size; --i >= 0;) + if ((op1_ptr[i] & ~op2_ptr[i]) != 0) + { + res_size = i + 1; + /* Handle allocation, now then we know exactly how much + space is needed for the result. */ + /* Don't re-read OP1_PTR. Since res_size <= op1_size, + op1 is not changed if it is identical to res. Don't + re-read OP2_PTR. It points to temporary space--never + to the space PTR(res) used to point to before + reallocation. */ + mpn_andn_n (MPZ_NEWALLOC (res, res_size), op1_ptr, op2_ptr, res_size); + + break; + } + } #endif - } - TMP_FREE; + SIZ(res) = res_size; + TMP_FREE; + } + } } diff --git a/Build/source/libs/gmp/gmp-src/mpz/aors.h b/Build/source/libs/gmp/gmp-src/mpz/aors.h index 4d22754b23b..722d480532e 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/aors.h +++ b/Build/source/libs/gmp/gmp-src/mpz/aors.h @@ -29,7 +29,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" diff --git a/Build/source/libs/gmp/gmp-src/mpz/aors_ui.h b/Build/source/libs/gmp/gmp-src/mpz/aors_ui.h index 2e3c481ab70..ba65af3bfde 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/aors_ui.h +++ b/Build/source/libs/gmp/gmp-src/mpz/aors_ui.h @@ -1,8 +1,8 @@ /* mpz_add_ui, mpz_sub_ui -- Add or subtract an mpz_t and an unsigned one-word integer. -Copyright 1991, 1993, 1994, 1996, 1999-2002, 2004, 2012, 2013 Free Software -Foundation, Inc. +Copyright 1991, 1993, 1994, 1996, 1999-2002, 2004, 2012, 2013, 2015 +Free Software Foundation, Inc. This file is part of the GNU MP Library. @@ -30,7 +30,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" @@ -80,7 +79,7 @@ FUNCTION (mpz_ptr w, mpz_srcptr u, unsigned long int vval) usize = SIZ (u); if (usize == 0) { - PTR (w)[0] = vval; + MPZ_NEWALLOC (w, 1)[0] = vval; SIZ (w) = VARIATION_NEG (vval != 0); return; } diff --git a/Build/source/libs/gmp/gmp-src/mpz/aorsmul.c b/Build/source/libs/gmp/gmp-src/mpz/aorsmul.c index bf012c965ce..57b06b3a559 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/aorsmul.c +++ b/Build/source/libs/gmp/gmp-src/mpz/aorsmul.c @@ -28,7 +28,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" diff --git a/Build/source/libs/gmp/gmp-src/mpz/aorsmul_i.c b/Build/source/libs/gmp/gmp-src/mpz/aorsmul_i.c index 07af0a4efe1..73f986e8ad3 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/aorsmul_i.c +++ b/Build/source/libs/gmp/gmp-src/mpz/aorsmul_i.c @@ -32,7 +32,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" diff --git a/Build/source/libs/gmp/gmp-src/mpz/array_init.c b/Build/source/libs/gmp/gmp-src/mpz/array_init.c index 0a6880ab0f9..df97f34bc44 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/array_init.c +++ b/Build/source/libs/gmp/gmp-src/mpz/array_init.c @@ -28,7 +28,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" void diff --git a/Build/source/libs/gmp/gmp-src/mpz/bin_ui.c b/Build/source/libs/gmp/gmp-src/mpz/bin_ui.c index c24b21724c1..bab3e076989 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/bin_ui.c +++ b/Build/source/libs/gmp/gmp-src/mpz/bin_ui.c @@ -1,6 +1,6 @@ -/* mpz_bin_ui - compute n over k. +/* mpz_bin_ui(RESULT, N, K) -- Set RESULT to N over K. -Copyright 1998-2002, 2012, 2013 Free Software Foundation, Inc. +Copyright 1998-2002, 2012, 2013, 2015, 2017-2018 Free Software Foundation, Inc. This file is part of the GNU MP Library. @@ -28,10 +28,302 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" -#include "longlong.h" +/* How many special cases? Minimum is 2: 0 and 1; + * also 3 {0,1,2} and 5 {0,1,2,3,4} are implemented. + */ +#define APARTAJ_KALKULOJ 2 + +/* Whether to use (1) or not (0) the function mpz_bin_uiui whenever + * the operands fit. + */ +#define UZU_BIN_UIUI 0 + +/* Whether to use a shortcut to precompute the product of four + * elements (1), or precompute only the product of a couple (0). + * + * In both cases the precomputed product is then updated with some + * linear operations to obtain the product of the next four (1) + * [or two (0)] operands. + */ +#define KVAROPE 1 + +static void +posmpz_init (mpz_ptr r) +{ + mp_ptr rp; + ASSERT (SIZ (r) > 0); + rp = SIZ (r) + MPZ_REALLOC (r, SIZ (r) + 2); + *rp = 0; + *++rp = 0; +} + +/* Equivalent to mpz_add_ui (r, r, in), but faster when + 0 < SIZ (r) < ALLOC (r) and limbs above SIZ (r) contain 0. */ +static void +posmpz_inc_ui (mpz_ptr r, unsigned long in) +{ +#if BITS_PER_ULONG > GMP_NUMB_BITS + mpz_add_ui (r, r, in); +#else + ASSERT (SIZ (r) > 0); + MPN_INCR_U (PTR (r), SIZ (r) + 1, in); + SIZ (r) += (PTR (r)[SIZ (r)] != 0); +#endif +} + +/* Equivalent to mpz_sub_ui (r, r, in), but faster when + 0 < SIZ (r) and we know in advance that the result is positive. */ +static void +posmpz_dec_ui (mpz_ptr r, unsigned long in) +{ +#if BITS_PER_ULONG > GMP_NUMB_BITS + mpz_sub_ui (r, r, in); +#else + ASSERT (mpz_cmp_ui (r, in) >= 0); + MPN_DECR_U (PTR (r), SIZ (r), in); + SIZ (r) -= (PTR (r)[SIZ (r)-1] == 0); +#endif +} + +/* Equivalent to mpz_tdiv_q_2exp (r, r, 1), but faster when + 0 < SIZ (r) and we know in advance that the result is positive. */ +static void +posmpz_rsh1 (mpz_ptr r) +{ + mp_ptr rp; + mp_size_t rn; + + rn = SIZ (r); + rp = PTR (r); + ASSERT (rn > 0); + mpn_rshift (rp, rp, rn, 1); + SIZ (r) -= rp[rn - 1] == 0; +} + +/* Computes r = n(n+(2*k-1))/2 + It uses a sqare instead of a product, computing + r = ((n+k-1)^2 + n - (k-1)^2)/2 + As a side effect, sets t = n+k-1 + */ +static void +mpz_hmul_nbnpk (mpz_ptr r, mpz_srcptr n, unsigned long int k, mpz_ptr t) +{ + ASSERT (k > 0 && SIZ(n) > 0); + --k; + mpz_add_ui (t, n, k); + mpz_mul (r, t, t); + mpz_add (r, r, n); + posmpz_rsh1 (r); + if (LIKELY (k <= (1UL << (BITS_PER_ULONG / 2)))) + posmpz_dec_ui (r, (k + (k & 1))*(k >> 1)); + else + { + mpz_t tmp; + mpz_init_set_ui (tmp, (k + (k & 1))); + mpz_mul_ui (tmp, tmp, k >> 1); + mpz_sub (r, r, tmp); + mpz_clear (tmp); + } +} + +#if KVAROPE +static void +rek_raising_fac4 (mpz_ptr r, mpz_ptr p, mpz_ptr P, unsigned long int k, unsigned long int lk, mpz_ptr t) +{ + if (k - lk < 5) + { + do { + posmpz_inc_ui (p, 4*k+2); + mpz_addmul_ui (P, p, 4*k); + posmpz_dec_ui (P, k); + mpz_mul (r, r, P); + } while (--k > lk); + } + else + { + mpz_t lt; + unsigned long int m; + + m = ((k + lk) >> 1) + 1; + rek_raising_fac4 (r, p, P, k, m, t); + + posmpz_inc_ui (p, 4*m+2); + mpz_addmul_ui (P, p, 4*m); + posmpz_dec_ui (P, m); + if (t == NULL) + { + mpz_init_set (lt, P); + t = lt; + } + else + { + ALLOC (lt) = 0; + mpz_set (t, P); + } + rek_raising_fac4 (t, p, P, m - 1, lk, NULL); + + mpz_mul (r, r, t); + mpz_clear (lt); + } +} + +/* Computes (n+1)(n+2)...(n+k)/2^(k/2 +k/4) using the helper function + rek_raising_fac4, and exploiting an idea inspired by a piece of + code that Fredrik Johansson wrote and by a comment by Niels Möller. + + Assume k = 4i then compute: + p = (n+1)(n+4i)/2 - i + (n+1+1)(n+4i)/2 = p + i + (n+4i)/2 + (n+1+1)(n+4i-1)/2 = p + i + ((n+4i)-(n+1+1))/2 = p + i + (n-n+4i-2)/2 = p + 3i-1 + P = (p + i)*(p+3i-1)/2 = (n+1)(n+2)(n+4i-1)(n+4i)/8 + n' = n + 2 + i' = i - 1 + (n'-1)(n')(n'+4i'+1)(n'+4i'+2)/8 = P + (n'-1)(n'+4i'+2)/2 - i' - 1 = p + (n'-1+2)(n'+4i'+2)/2 - i' - 1 = p + (n'+4i'+2) + (n'-1+2)(n'+4i'+2-2)/2 - i' - 1 = p + (n'+4i'+2) - (n'-1+2) = p + 4i' + 1 + (n'-1+2)(n'+4i'+2-2)/2 - i' = p + 4i' + 2 + p' = p + 4i' + 2 = (n'+1)(n'+4i')/2 - i' + p' - 4i' - 2 = p + (p' - 4i' - 2 + i)*(p' - 4i' - 2+3i-1)/2 = P + (p' - 4i' - 2 + i' + 1)*(p' - 4i' - 2 + 3i' + 3 - 1)/2 = P + (p' - 3i' - 1)*(p' - i')/2 = P + (p' - 3i' - 1 + 4i' + 1)*(p' - i' + 4i' - 1)/2 = P + (4i' + 1)*(p' - i')/2 + (p' - 3i' - 1 + 4i' + 1)*(4i' - 1)/2 + (p' + i')*(p' + 3i' - 1)/2 = P + (4i')*(p' + p')/2 + (p' - i' - (p' + i'))/2 + (p' + i')*(p' + 3i' - 1)/2 = P + 4i'p' + (p' - i' - p' - i')/2 + (p' + i')*(p' + 3i' - 1)/2 = P + 4i'p' - i' + P' = P + 4i'p' - i' + + And compute the product P * P' * P" ... + */ + +static void +mpz_raising_fac4 (mpz_ptr r, mpz_ptr n, unsigned long int k, mpz_ptr t, mpz_ptr p) +{ + ASSERT ((k >= APARTAJ_KALKULOJ) && (APARTAJ_KALKULOJ > 0)); + posmpz_init (n); + posmpz_inc_ui (n, 1); + SIZ (r) = 0; + if (k & 1) + { + mpz_set (r, n); + posmpz_inc_ui (n, 1); + } + k >>= 1; + if (APARTAJ_KALKULOJ < 2 && k == 0) + return; + + mpz_hmul_nbnpk (p, n, k, t); + posmpz_init (p); + + if (k & 1) + { + if (SIZ (r)) + mpz_mul (r, r, p); + else + mpz_set (r, p); + posmpz_inc_ui (p, k - 1); + } + k >>= 1; + if (APARTAJ_KALKULOJ < 4 && k == 0) + return; + + mpz_hmul_nbnpk (t, p, k, n); + if (SIZ (r)) + mpz_mul (r, r, t); + else + mpz_set (r, t); + + if (APARTAJ_KALKULOJ > 8 || k > 1) + { + posmpz_dec_ui (p, k); + rek_raising_fac4 (r, p, t, k - 1, 0, n); + } +} + +#else /* KVAROPE */ + +static void +rek_raising_fac (mpz_ptr r, mpz_ptr n, unsigned long int k, unsigned long int lk, mpz_ptr t1, mpz_ptr t2) +{ + /* Should the threshold depend on SIZ (n) ? */ + if (k - lk < 10) + { + do { + posmpz_inc_ui (n, k); + mpz_mul (r, r, n); + --k; + } while (k > lk); + } + else + { + mpz_t t3; + unsigned long int m; + + m = ((k + lk) >> 1) + 1; + rek_raising_fac (r, n, k, m, t1, t2); + + posmpz_inc_ui (n, m); + if (t1 == NULL) + { + mpz_init_set (t3, n); + t1 = t3; + } + else + { + ALLOC (t3) = 0; + mpz_set (t1, n); + } + rek_raising_fac (t1, n, m - 1, lk, t2, NULL); + + mpz_mul (r, r, t1); + mpz_clear (t3); + } +} + +/* Computes (n+1)(n+2)...(n+k)/2^(k/2) using the helper function + rek_raising_fac, and exploiting an idea inspired by a piece of + code that Fredrik Johansson wrote. + + Force an even k = 2i then compute: + p = (n+1)(n+2i)/2 + i' = i - 1 + p == (n+1)(n+2i'+2)/2 + p' = p + i' == (n+2)(n+2i'+1)/2 + n' = n + 1 + p'== (n'+1)(n'+2i')/2 == (n+1 +1)(n+2i -1)/2 + + And compute the product p * p' * p" ... +*/ + +static void +mpz_raising_fac (mpz_ptr r, mpz_ptr n, unsigned long int k, mpz_ptr t, mpz_ptr p) +{ + unsigned long int hk; + ASSERT ((k >= APARTAJ_KALKULOJ) && (APARTAJ_KALKULOJ > 1)); + mpz_add_ui (n, n, 1); + hk = k >> 1; + mpz_hmul_nbnpk (p, n, hk, t); + + if ((k & 1) != 0) + { + mpz_add_ui (t, t, hk + 1); + mpz_mul (r, t, p); + } + else + { + mpz_set (r, p); + } + + if ((APARTAJ_KALKULOJ > 3) || (hk > 1)) + { + posmpz_init (p); + rek_raising_fac (r, p, hk - 1, 0, t, n); + } +} +#endif /* KVAROPE */ /* This is a poor implementation. Look at bin_uiui.c for improvement ideas. In fact consider calling mpz_bin_uiui() when the arguments fit, leaving @@ -40,21 +332,10 @@ see https://www.gnu.org/licenses/. */ The identity bin(n,k) = (-1)^k * bin(-n+k-1,k) can be found in Knuth vol 1 section 1.2.6 part G. */ - -#define DIVIDE() \ - do { \ - ASSERT (SIZ(r) > 0); \ - MPN_DIVREM_OR_DIVEXACT_1 (PTR(r), PTR(r), (mp_size_t) SIZ(r), kacc); \ - SIZ(r) -= (PTR(r)[SIZ(r)-1] == 0); \ - } while (0) - void mpz_bin_ui (mpz_ptr r, mpz_srcptr n, unsigned long int k) { mpz_t ni; - mp_limb_t i; - mpz_t nacc; - mp_limb_t kacc; mp_size_t negate; if (SIZ (n) < 0) @@ -83,7 +364,6 @@ mpz_bin_ui (mpz_ptr r, mpz_srcptr n, unsigned long int k) /* Now wanting bin(ni+k,k), with ni positive, and "negate" is the sign (0 for positive, 1 for negative). */ - SIZ (r) = 1; PTR (r)[0] = 1; /* Rewrite bin(n,k) as bin(n,n-k) if that is smaller. In this case it's whether ni+k-k < k meaning ni<k, and if so change to denominator ni+k-k @@ -96,48 +376,84 @@ mpz_bin_ui (mpz_ptr r, mpz_srcptr n, unsigned long int k) mpz_set_ui (ni, tmp); } - kacc = 1; - mpz_init_set_ui (nacc, 1L); - - for (i = 1; i <= k; i++) + if (k < APARTAJ_KALKULOJ) { - mp_limb_t k1, k0; - -#if 0 - mp_limb_t nacclow; - int c; - - nacclow = PTR(nacc)[0]; - for (c = 0; (((kacc | nacclow) & 1) == 0); c++) + if (k == 0) { - kacc >>= 1; - nacclow >>= 1; + SIZ (r) = 1; + MPZ_NEWALLOC (r, 1)[0] = 1; } - mpz_div_2exp (nacc, nacc, c); -#endif - - mpz_add_ui (ni, ni, 1L); - mpz_mul (nacc, nacc, ni); - umul_ppmm (k1, k0, kacc, i << GMP_NAIL_BITS); - if (k1 != 0) +#if APARTAJ_KALKULOJ > 2 + else if (k == 2) { - /* Accumulator overflow. Perform bignum step. */ - mpz_mul (r, r, nacc); - SIZ (nacc) = 1; PTR (nacc)[0] = 1; - DIVIDE (); - kacc = i; + mpz_add_ui (ni, ni, 1); + mpz_mul (r, ni, ni); + mpz_add (r, r, ni); + posmpz_rsh1 (r); + } +#endif +#if APARTAJ_KALKULOJ > 3 + else if (k > 2) + { /* k = 3, 4 */ + mpz_add_ui (ni, ni, 2); /* n+1 */ + mpz_mul (r, ni, ni); /* (n+1)^2 */ + mpz_sub_ui (r, r, 1); /* (n+1)^2-1 */ + if (k == 3) + { + mpz_mul (r, r, ni); /* ((n+1)^2-1)(n+1) = n(n+1)(n+2) */ + /* mpz_divexact_ui (r, r, 6); /\* 6=3<<1; div_by3 ? *\/ */ + mpn_pi1_bdiv_q_1 (PTR(r), PTR(r), SIZ(r), 3, GMP_NUMB_MASK/3*2+1, 1); + MPN_NORMALIZE_NOT_ZERO (PTR(r), SIZ(r)); + } + else /* k = 4 */ + { + mpz_add (ni, ni, r); /* (n+1)^2+n */ + mpz_mul (r, ni, ni); /* ((n+1)^2+n)^2 */ + mpz_sub_ui (r, r, 1); /* ((n+1)^2+n)^2-1 = n(n+1)(n+2)(n+3) */ + /* mpz_divexact_ui (r, r, 24); /\* 24=3<<3; div_by3 ? *\/ */ + mpn_pi1_bdiv_q_1 (PTR(r), PTR(r), SIZ(r), 3, GMP_NUMB_MASK/3*2+1, 3); + MPN_NORMALIZE_NOT_ZERO (PTR(r), SIZ(r)); + } } +#endif else - { - /* Save new products in accumulators to keep accumulating. */ - kacc = k0 >> GMP_NAIL_BITS; + { /* k = 1 */ + mpz_add_ui (r, ni, 1); } } +#if UZU_BIN_UIUI + else if (mpz_cmp_ui (ni, ULONG_MAX - k) <= 0) + { + mpz_bin_uiui (r, mpz_get_ui (ni) + k, k); + } +#endif + else + { + mp_limb_t count; + mpz_t num, den; - mpz_mul (r, r, nacc); - DIVIDE (); - SIZ(r) = (SIZ(r) ^ -negate) + negate; + mpz_init (num); + mpz_init (den); + +#if KVAROPE + mpz_raising_fac4 (num, ni, k, den, r); + popc_limb (count, k); + ASSERT (k - (k >> 1) - (k >> 2) - count >= 0); + mpz_tdiv_q_2exp (num, num, k - (k >> 1) - (k >> 2) - count); +#else + mpz_raising_fac (num, ni, k, den, r); + popc_limb (count, k); + ASSERT (k - (k >> 1) - count >= 0); + mpz_tdiv_q_2exp (num, num, k - (k >> 1) - count); +#endif + + mpz_oddfac_1(den, k, 0); - mpz_clear (nacc); + mpz_divexact(r, num, den); + mpz_clear (num); + mpz_clear (den); + } mpz_clear (ni); + + SIZ(r) = (SIZ(r) ^ -negate) + negate; } diff --git a/Build/source/libs/gmp/gmp-src/mpz/bin_uiui.c b/Build/source/libs/gmp/gmp-src/mpz/bin_uiui.c index 94a9dc5c75d..b77628fdfc2 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/bin_uiui.c +++ b/Build/source/libs/gmp/gmp-src/mpz/bin_uiui.c @@ -2,7 +2,7 @@ Contributed to the GNU project by Torbjorn Granlund and Marco Bodrato. -Copyright 2010-2012 Free Software Foundation, Inc. +Copyright 2010-2012, 2015-2018 Free Software Foundation, Inc. This file is part of the GNU MP Library. @@ -30,12 +30,11 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" #include "longlong.h" #ifndef BIN_GOETGHELUCK_THRESHOLD -#define BIN_GOETGHELUCK_THRESHOLD 1000 +#define BIN_GOETGHELUCK_THRESHOLD 512 #endif #ifndef BIN_UIUI_ENABLE_SMALLDC #define BIN_UIUI_ENABLE_SMALLDC 1 @@ -110,58 +109,69 @@ mul3 (mp_limb_t m) static mp_limb_t mul4 (mp_limb_t m) { - mp_limb_t m01 = (m + 0) * (m + 1) >> 1; - mp_limb_t m23 = (m + 2) * (m + 3) >> 1; - return m01 * m23; + mp_limb_t m03 = (m + 0) * (m + 3) >> 1; + return m03 * (m03 + 1); /* mul2 (m03) ? */ } static mp_limb_t mul5 (mp_limb_t m) { - mp_limb_t m012 = (m + 0) * (m + 1) * (m + 2) >> 1; - mp_limb_t m34 = (m + 3) * (m + 4) >> 1; - return m012 * m34; + mp_limb_t m03 = (m + 0) * (m + 3) >> 1; + mp_limb_t m034 = m03 * (m + 4); + return (m03 + 1) * m034; } static mp_limb_t mul6 (mp_limb_t m) { - mp_limb_t m01 = (m + 0) * (m + 1); - mp_limb_t m23 = (m + 2) * (m + 3); - mp_limb_t m45 = (m + 4) * (m + 5) >> 1; - mp_limb_t m0123 = m01 * m23 >> 3; - return m0123 * m45; + mp_limb_t m05 = (m + 0) * (m + 5); + mp_limb_t m1234 = (m05 + 5) * (m05 + 5) >> 3; + return m1234 * (m05 >> 1); } static mp_limb_t mul7 (mp_limb_t m) { - mp_limb_t m01 = (m + 0) * (m + 1); - mp_limb_t m23 = (m + 2) * (m + 3); - mp_limb_t m456 = (m + 4) * (m + 5) * (m + 6) >> 1; - mp_limb_t m0123 = m01 * m23 >> 3; - return m0123 * m456; + mp_limb_t m05 = (m + 0) * (m + 5); + mp_limb_t m1234 = (m05 + 5) * (m05 + 5) >> 3; + mp_limb_t m056 = m05 * (m + 6) >> 1; + return m1234 * m056; } static mp_limb_t mul8 (mp_limb_t m) { - mp_limb_t m01 = (m + 0) * (m + 1); - mp_limb_t m23 = (m + 2) * (m + 3); - mp_limb_t m45 = (m + 4) * (m + 5); - mp_limb_t m67 = (m + 6) * (m + 7); - mp_limb_t m0123 = m01 * m23 >> 3; - mp_limb_t m4567 = m45 * m67 >> 3; - return m0123 * m4567; + mp_limb_t m07 = (m + 0) * (m + 7); + mp_limb_t m0257 = m07 * (m07 + 10) >> 3; + mp_limb_t m1346 = m07 + 9 + m0257; + return m0257 * m1346; +} + +/* +static mp_limb_t +mul9 (mp_limb_t m) +{ + return (m + 8) * mul8 (m) ; } +static mp_limb_t +mul10 (mp_limb_t m) +{ + mp_limb_t m09 = (m + 0) * (m + 9); + mp_limb_t m18 = (m09 >> 1) + 4; + mp_limb_t m0369 = m09 * (m09 + 18) >> 3; + mp_limb_t m2457 = m09 * 2 + 35 + m0369; + return ((m0369 * m2457) >> 1) * m18; +} +*/ + typedef mp_limb_t (* mulfunc_t) (mp_limb_t); -static const mulfunc_t mulfunc[] = {mul1,mul2,mul3,mul4,mul5,mul6,mul7,mul8}; +static const mulfunc_t mulfunc[] = {mul1,mul2,mul3,mul4,mul5,mul6,mul7,mul8 /* ,mul9,mul10 */}; #define M (numberof(mulfunc)) /* Number of factors-of-2 removed by the corresponding mulN function. */ -static const unsigned char tcnttab[] = {0, 1, 1, 2, 2, 4, 4, 6}; +static const unsigned char tcnttab[] = {0, 1, 1, 2, 2, 4, 4, 6 /*,6,8*/}; #if 1 /* This variant is inaccurate but share the code with other functions. */ @@ -176,11 +186,11 @@ static const unsigned char tcnttab[] = {0, 1, 1, 2, 2, 4, 4, 6}; static const unsigned long ftab[] = #if GMP_NUMB_BITS == 64 /* 1 to 8 factors per iteration */ - {CNST_LIMB(0xffffffffffffffff),CNST_LIMB(0x100000000),0x32cbfe,0x16a0b,0x24c4,0xa16,0x34b,0x1b2 /*,0xdf,0x8d */}; + {CNST_LIMB(0xffffffffffffffff),CNST_LIMB(0x16a09e667),0x32cbfc,0x16a08,0x24c0,0xa11,0x345,0x1ab /*,0xe9,0x8e */}; #endif #if GMP_NUMB_BITS == 32 /* 1 to 7 factors per iteration */ - {0xffffffff,0x10000,0x801,0x16b,0x71,0x42,0x26 /* ,0x1e */}; + {0xffffffff,0x16a09,0x7ff,0x168,0x6f,0x3d,0x20 /* ,0x17 */}; #endif #define MAXFACS(max,l) \ @@ -199,11 +209,10 @@ static const mp_limb_t facinv[] = { ONE_LIMB_ODD_FACTORIAL_INVERSES_TABLE }; static void mpz_bdiv_bin_uiui (mpz_ptr r, unsigned long int n, unsigned long int k) { - int nmax, kmax, nmaxnow, numfac; + unsigned nmax, kmax, nmaxnow, numfac; mp_ptr np, kp; mp_size_t nn, kn, alloc; mp_limb_t i, j, t, iii, jjj, cy, dinv; - mp_bitcnt_t i2cnt, j2cnt; int cnt; mp_size_t maxn; TMP_DECL; @@ -216,9 +225,8 @@ mpz_bdiv_bin_uiui (mpz_ptr r, unsigned long int n, unsigned long int k) /* FIXME: This allocation might be insufficient, but is usually way too large. */ alloc = SOME_THRESHOLD - 1 + MAX (3 * maxn / 2, SOME_THRESHOLD); - alloc = MIN (alloc, k) + 1; - np = TMP_ALLOC_LIMBS (alloc); - kp = TMP_ALLOC_LIMBS (SOME_THRESHOLD + 1); + alloc = MIN (alloc, (mp_size_t) k) + 1; + TMP_ALLOC_LIMBS_2 (np, alloc, kp, SOME_THRESHOLD + 1); MAXFACS (nmax, n); ASSERT (nmax <= M); @@ -230,10 +238,6 @@ mpz_bdiv_bin_uiui (mpz_ptr r, unsigned long int n, unsigned long int k) np[0] = 1; nn = 1; - i2cnt = 0; /* total low zeros in dividend */ - j2cnt = __gmp_fac2cnt_table[ODD_FACTORIAL_TABLE_LIMIT / 2 - 1]; - /* total low zeros in divisor */ - numfac = 1; j = ODD_FACTORIAL_TABLE_LIMIT + 1; jjj = ODD_FACTORIAL_TABLE_MAX; @@ -252,7 +256,6 @@ mpz_bdiv_bin_uiui (mpz_ptr r, unsigned long int n, unsigned long int k) j += kmax; /* number of factors used */ count_trailing_zeros (cnt, jjj); /* count low zeros */ jjj >>= cnt; /* remove remaining low zeros */ - j2cnt += tcnttab[kmax - 1] + cnt; /* update low zeros count */ cy = mpn_mul_1 (kp, kp, kn, jjj); /* accumulate new factors */ kp[kn] = cy; kn += cy != 0; @@ -268,7 +271,6 @@ mpz_bdiv_bin_uiui (mpz_ptr r, unsigned long int n, unsigned long int k) i += nmaxnow; /* number of factors used */ count_trailing_zeros (cnt, iii); /* count low zeros */ iii >>= cnt; /* remove remaining low zeros */ - i2cnt += tcnttab[nmaxnow - 1] + cnt; /* update low zeros count */ cy = mpn_mul_1 (np, np, nn, iii); /* accumulate new factors */ np[nn] = cy; nn += cy != 0; @@ -281,6 +283,7 @@ mpz_bdiv_bin_uiui (mpz_ptr r, unsigned long int n, unsigned long int k) nn += (np[nn - 1] >= kp[kn - 1]); nn -= kn; mpn_sbpi1_bdiv_q (np, np, nn, kp, MIN(kn,nn), -dinv); + mpn_neg (np, np, nn); if (kmax == 0) break; @@ -290,11 +293,14 @@ mpz_bdiv_bin_uiui (mpz_ptr r, unsigned long int n, unsigned long int k) j += kmax; /* number of factors used */ count_trailing_zeros (cnt, jjj); /* count low zeros */ jjj >>= cnt; /* remove remaining low zeros */ - j2cnt += tcnttab[kmax - 1] + cnt; /* update low zeros count */ } /* Put back the right number of factors of 2. */ - cnt = i2cnt - j2cnt; + popc_limb (cnt, n - k); + popc_limb (j, k); + cnt += j; + popc_limb (j, n); + cnt -= j; if (cnt != 0) { ASSERT (cnt < GMP_NUMB_BITS); /* can happen, but not for intended use */ @@ -314,44 +320,51 @@ mpz_bdiv_bin_uiui (mpz_ptr r, unsigned long int n, unsigned long int k) static void mpz_smallk_bin_uiui (mpz_ptr r, unsigned long int n, unsigned long int k) { - int nmax, numfac; + unsigned nmax, numfac; mp_ptr rp; mp_size_t rn, alloc; mp_limb_t i, iii, cy; - mp_bitcnt_t i2cnt, cnt; - - count_leading_zeros (cnt, (mp_limb_t) n); - cnt = GMP_LIMB_BITS - cnt; - alloc = cnt * k / GMP_NUMB_BITS + 3; /* FIXME: ensure rounding is enough. */ - rp = MPZ_NEWALLOC (r, alloc); + unsigned i2cnt, cnt; MAXFACS (nmax, n); nmax = MIN (nmax, M); i = n - k + 1; - nmax = MIN (nmax, k); + i2cnt = __gmp_fac2cnt_table[k / 2 - 1]; /* low zeros count */ + if (nmax >= k) + { + MPZ_NEWALLOC (r, 1) [0] = mulfunc[k - 1] (i) * facinv[k - 2] >> + (i2cnt - tcnttab[k - 1]); + SIZ(r) = 1; + return; + } + + count_leading_zeros (cnt, (mp_limb_t) n); + cnt = GMP_LIMB_BITS - cnt; + alloc = cnt * k / GMP_NUMB_BITS + 3; /* FIXME: ensure rounding is enough. */ + rp = MPZ_NEWALLOC (r, alloc); + rp[0] = mulfunc[nmax - 1] (i); rn = 1; i += nmax; /* number of factors used */ - i2cnt = tcnttab[nmax - 1]; /* low zeros count */ + i2cnt -= tcnttab[nmax - 1]; /* low zeros count */ numfac = k - nmax; - while (numfac != 0) + do { nmax = MIN (nmax, numfac); iii = mulfunc[nmax - 1] (i); i += nmax; /* number of factors used */ - i2cnt += tcnttab[nmax - 1]; /* update low zeros count */ + i2cnt -= tcnttab[nmax - 1]; /* update low zeros count */ cy = mpn_mul_1 (rp, rp, rn, iii); /* accumulate new factors */ rp[rn] = cy; rn += cy != 0; numfac -= nmax; - } + } while (numfac != 0); ASSERT (rn < alloc); - mpn_pi1_bdiv_q_1 (rp, rp, rn, __gmp_oddfac_table[k], facinv[k - 2], - __gmp_fac2cnt_table[k / 2 - 1] - i2cnt); + mpn_pi1_bdiv_q_1 (rp, rp, rn, __gmp_oddfac_table[k], facinv[k - 2], i2cnt); /* A two-fold, branch-free normalisation is possible :*/ /* rn -= rp[rn - 1] == 0; */ /* rn -= rp[rn - 1] == 0; */ @@ -485,7 +498,8 @@ mpz_smallkdc_bin_uiui (mpz_ptr r, unsigned long int n, unsigned long int k) ++__i; \ if (((sieve)[__index] & __mask) == 0) \ { \ - (prime) = id_to_n(__i) + mp_limb_t prime; \ + prime = id_to_n(__i) #define LOOP_ON_SIEVE_BEGIN(prime,start,end,off,sieve) \ do { \ @@ -502,7 +516,7 @@ mpz_smallkdc_bin_uiui (mpz_ptr r, unsigned long int n, unsigned long int k) } \ __mask = __mask << 1 | __mask >> (GMP_LIMB_BITS-1); \ __index += __mask & 1; \ - } while (__i <= __max_i) \ + } while (__i <= __max_i) #define LOOP_ON_SIEVE_END \ LOOP_ON_SIEVE_STOP; \ @@ -556,24 +570,29 @@ primesieve_size (mp_limb_t n) { return n_to_bit(n) / GMP_LIMB_BITS + 1; } } \ } while (0) -/* Returns an approximation of the sqare root of x. * - * It gives: x <= limb_apprsqrt (x) ^ 2 < x * 9/4 */ +/* Returns an approximation of the sqare root of x. + * It gives: + * limb_apprsqrt (x) ^ 2 <= x < (limb_apprsqrt (x)+1) ^ 2 + * or + * x <= limb_apprsqrt (x) ^ 2 <= x * 9/8 + */ static mp_limb_t limb_apprsqrt (mp_limb_t x) { int s; ASSERT (x > 2); - count_leading_zeros (s, x - 1); - s = GMP_LIMB_BITS - 1 - s; - return (CNST_LIMB(1) << (s >> 1)) + (CNST_LIMB(1) << ((s - 1) >> 1)); + count_leading_zeros (s, x); + s = (GMP_LIMB_BITS - s) >> 1; + return ((CNST_LIMB(1) << s) + (x >> s)) >> 1; } static void mpz_goetgheluck_bin_uiui (mpz_ptr r, unsigned long int n, unsigned long int k) { mp_limb_t *sieve, *factors, count; - mp_limb_t prod, max_prod, j; + mp_limb_t prod, max_prod; + mp_size_t j; TMP_DECL; ASSERT (BIN_GOETGHELUCK_THRESHOLD >= 13); @@ -602,38 +621,30 @@ mpz_goetgheluck_bin_uiui (mpz_ptr r, unsigned long int n, unsigned long int k) { mp_limb_t s; - { - mp_limb_t prime; - s = limb_apprsqrt(n); - s = n_to_bit (s); - LOOP_ON_SIEVE_BEGIN (prime, n_to_bit (5), s, 0,sieve); - COUNT_A_PRIME (prime, n, k, prod, max_prod, factors, j); - LOOP_ON_SIEVE_END; - s++; - } + s = limb_apprsqrt(n); + s = n_to_bit (s); + ASSERT (bit_to_n (s+1) * bit_to_n (s+1) > n); + ASSERT (s <= n_to_bit (n >> 1)); + LOOP_ON_SIEVE_BEGIN (prime, n_to_bit (5), s, 0,sieve); + COUNT_A_PRIME (prime, n, k, prod, max_prod, factors, j); + LOOP_ON_SIEVE_STOP; ASSERT (max_prod <= GMP_NUMB_MAX / 2); max_prod <<= 1; - ASSERT (bit_to_n (s) * bit_to_n (s) > n); - ASSERT (s <= n_to_bit (n >> 1)); - { - mp_limb_t prime; - LOOP_ON_SIEVE_BEGIN (prime, s, n_to_bit (n >> 1), 0,sieve); - SH_COUNT_A_PRIME (prime, n, k, prod, max_prod, factors, j); - LOOP_ON_SIEVE_END; - } + LOOP_ON_SIEVE_CONTINUE (prime, n_to_bit (n >> 1),sieve); + SH_COUNT_A_PRIME (prime, n, k, prod, max_prod, factors, j); + LOOP_ON_SIEVE_END; + max_prod >>= 1; } /* Store primes from (n-k)+1 to n */ ASSERT (n_to_bit (n - k) < n_to_bit (n)); - { - mp_limb_t prime; - LOOP_ON_SIEVE_BEGIN (prime, n_to_bit (n - k) + 1, n_to_bit (n), 0,sieve); - FACTOR_LIST_STORE (prime, prod, max_prod, factors, j); - LOOP_ON_SIEVE_END; - } + + LOOP_ON_SIEVE_BEGIN (prime, n_to_bit (n - k) + 1, n_to_bit (n), 0,sieve); + FACTOR_LIST_STORE (prime, prod, max_prod, factors, j); + LOOP_ON_SIEVE_END; if (LIKELY (j != 0)) { @@ -642,7 +653,7 @@ mpz_goetgheluck_bin_uiui (mpz_ptr r, unsigned long int n, unsigned long int k) } else { - PTR (r)[0] = prod; + MPZ_NEWALLOC (r, 1)[0] = prod; SIZ (r) = 1; } TMP_FREE; @@ -677,10 +688,10 @@ mpz_bin_uiui (mpz_ptr r, unsigned long int n, unsigned long int k) /* Rewrite bin(n,k) as bin(n,n-k) if that is smaller. */ k = MIN (k, n - k); if (k < 2) { - PTR(r)[0] = k ? n : 1; /* 1 + ((-k) & (n-1)); */ + MPZ_NEWALLOC (r, 1)[0] = k ? n : 1; /* 1 + ((-k) & (n-1)); */ SIZ(r) = 1; } else if (n <= ODD_FACTORIAL_EXTTABLE_LIMIT) { /* k >= 2, n >= 4 */ - PTR(r)[0] = bc_bin_uiui (n, k); + MPZ_NEWALLOC (r, 1)[0] = bc_bin_uiui (n, k); SIZ(r) = 1; } else if (k <= ODD_FACTORIAL_TABLE_LIMIT) mpz_smallk_bin_uiui (r, n, k); diff --git a/Build/source/libs/gmp/gmp-src/mpz/cdiv_q.c b/Build/source/libs/gmp/gmp-src/mpz/cdiv_q.c index 32e3200a8d5..f19eb74ab8e 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/cdiv_q.c +++ b/Build/source/libs/gmp/gmp-src/mpz/cdiv_q.c @@ -29,7 +29,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" void diff --git a/Build/source/libs/gmp/gmp-src/mpz/cdiv_q_ui.c b/Build/source/libs/gmp/gmp-src/mpz/cdiv_q_ui.c index 63608c90438..269d9a3e988 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/cdiv_q_ui.c +++ b/Build/source/libs/gmp/gmp-src/mpz/cdiv_q_ui.c @@ -32,7 +32,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" unsigned long int diff --git a/Build/source/libs/gmp/gmp-src/mpz/cdiv_qr.c b/Build/source/libs/gmp/gmp-src/mpz/cdiv_qr.c index 45e9a2774cc..bc9b8927320 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/cdiv_qr.c +++ b/Build/source/libs/gmp/gmp-src/mpz/cdiv_qr.c @@ -29,7 +29,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" void diff --git a/Build/source/libs/gmp/gmp-src/mpz/cdiv_qr_ui.c b/Build/source/libs/gmp/gmp-src/mpz/cdiv_qr_ui.c index 1ccfbbe7fd2..0c11fb636cf 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/cdiv_qr_ui.c +++ b/Build/source/libs/gmp/gmp-src/mpz/cdiv_qr_ui.c @@ -3,8 +3,8 @@ always fit into the return type, the negative of the true remainder is returned. -Copyright 1994-1996, 1999, 2001, 2002, 2004, 2012 Free Software Foundation, -Inc. +Copyright 1994-1996, 1999, 2001, 2002, 2004, 2012, 2015 Free Software +Foundation, Inc. This file is part of the GNU MP Library. @@ -32,7 +32,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" unsigned long int @@ -108,7 +107,7 @@ mpz_cdiv_qr_ui (mpz_ptr quot, mpz_ptr rem, mpz_srcptr dividend, unsigned long in rl = divisor - rl; } - PTR(rem)[0] = rl; + MPZ_NEWALLOC (rem, 1)[0] = rl; SIZ(rem) = -(rl != 0); } qn = nn - (qp[nn - 1] == 0); diff --git a/Build/source/libs/gmp/gmp-src/mpz/cdiv_r.c b/Build/source/libs/gmp/gmp-src/mpz/cdiv_r.c index 9cebab3e061..83c624a4de0 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/cdiv_r.c +++ b/Build/source/libs/gmp/gmp-src/mpz/cdiv_r.c @@ -29,7 +29,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" void diff --git a/Build/source/libs/gmp/gmp-src/mpz/cdiv_r_ui.c b/Build/source/libs/gmp/gmp-src/mpz/cdiv_r_ui.c index 68fb149c461..84d51dba1ac 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/cdiv_r_ui.c +++ b/Build/source/libs/gmp/gmp-src/mpz/cdiv_r_ui.c @@ -3,8 +3,8 @@ always fit into the return type, the negative of the true remainder is returned. -Copyright 1994-1996, 2001, 2002, 2004, 2005, 2012 Free Software Foundation, -Inc. +Copyright 1994-1996, 2001, 2002, 2004, 2005, 2012, 2015 Free Software +Foundation, Inc. This file is part of the GNU MP Library. @@ -32,7 +32,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" unsigned long int @@ -101,7 +100,7 @@ mpz_cdiv_r_ui (mpz_ptr rem, mpz_srcptr dividend, unsigned long int divisor) if (ns >= 0) rl = divisor - rl; - PTR(rem)[0] = rl; + MPZ_NEWALLOC (rem, 1)[0] = rl; SIZ(rem) = -1; } } diff --git a/Build/source/libs/gmp/gmp-src/mpz/cdiv_ui.c b/Build/source/libs/gmp/gmp-src/mpz/cdiv_ui.c index 1f7f6e3c1ba..e1a1c49b650 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/cdiv_ui.c +++ b/Build/source/libs/gmp/gmp-src/mpz/cdiv_ui.c @@ -32,7 +32,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" unsigned long int diff --git a/Build/source/libs/gmp/gmp-src/mpz/cfdiv_q_2exp.c b/Build/source/libs/gmp/gmp-src/mpz/cfdiv_q_2exp.c index 366d6aa7046..413ea363d6a 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/cfdiv_q_2exp.c +++ b/Build/source/libs/gmp/gmp-src/mpz/cfdiv_q_2exp.c @@ -29,7 +29,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" @@ -53,7 +52,7 @@ cfdiv_q_2exp (mpz_ptr w, mpz_srcptr u, mp_bitcnt_t cnt, int dir) if (wsize <= 0) { /* u < 2**cnt, so result 1, 0 or -1 according to rounding */ - PTR(w)[0] = 1; + MPZ_NEWALLOC (w, 1)[0] = 1; SIZ(w) = (usize == 0 || (usize ^ dir) < 0 ? 0 : dir); return; } diff --git a/Build/source/libs/gmp/gmp-src/mpz/cfdiv_r_2exp.c b/Build/source/libs/gmp/gmp-src/mpz/cfdiv_r_2exp.c index 4941822b285..fedb97dc5cc 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/cfdiv_r_2exp.c +++ b/Build/source/libs/gmp/gmp-src/mpz/cfdiv_r_2exp.c @@ -28,7 +28,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" diff --git a/Build/source/libs/gmp/gmp-src/mpz/clear.c b/Build/source/libs/gmp/gmp-src/mpz/clear.c index d1541e91c95..f8c38a2e8b0 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/clear.c +++ b/Build/source/libs/gmp/gmp-src/mpz/clear.c @@ -30,11 +30,11 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" void mpz_clear (mpz_ptr x) { - __GMP_FREE_FUNC_LIMBS (PTR (x), ALLOC(x)); + if (ALLOC (x)) + __GMP_FREE_FUNC_LIMBS (PTR (x), ALLOC(x)); } diff --git a/Build/source/libs/gmp/gmp-src/mpz/clears.c b/Build/source/libs/gmp/gmp-src/mpz/clears.c index dac98873814..7ac257a1cc8 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/clears.c +++ b/Build/source/libs/gmp/gmp-src/mpz/clears.c @@ -29,7 +29,6 @@ GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ #include <stdarg.h> -#include "gmp.h" #include "gmp-impl.h" void @@ -39,11 +38,13 @@ mpz_clears (mpz_ptr x, ...) va_start (ap, x); - while (x != NULL) + do { - __GMP_FREE_FUNC_LIMBS (PTR (x), ALLOC(x)); + if (ALLOC (x)) + __GMP_FREE_FUNC_LIMBS (PTR (x), ALLOC (x)); x = va_arg (ap, mpz_ptr); } + while (x != NULL); va_end (ap); } diff --git a/Build/source/libs/gmp/gmp-src/mpz/clrbit.c b/Build/source/libs/gmp/gmp-src/mpz/clrbit.c index 2475efe1e5b..8b3c8549ee7 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/clrbit.c +++ b/Build/source/libs/gmp/gmp-src/mpz/clrbit.c @@ -28,7 +28,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" void diff --git a/Build/source/libs/gmp/gmp-src/mpz/cmp.c b/Build/source/libs/gmp/gmp-src/mpz/cmp.c index b8a5eaa7657..a97b0043a3f 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/cmp.c +++ b/Build/source/libs/gmp/gmp-src/mpz/cmp.c @@ -30,7 +30,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" int diff --git a/Build/source/libs/gmp/gmp-src/mpz/cmp_d.c b/Build/source/libs/gmp/gmp-src/mpz/cmp_d.c index 45926d6d547..b5b5e8b77e4 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/cmp_d.c +++ b/Build/source/libs/gmp/gmp-src/mpz/cmp_d.c @@ -34,7 +34,6 @@ see https://www.gnu.org/licenses/. */ #include <float.h> /* for DBL_MAX */ #endif -#include "gmp.h" #include "gmp-impl.h" diff --git a/Build/source/libs/gmp/gmp-src/mpz/cmp_si.c b/Build/source/libs/gmp/gmp-src/mpz/cmp_si.c index 86251f436ad..23296c863b4 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/cmp_si.c +++ b/Build/source/libs/gmp/gmp-src/mpz/cmp_si.c @@ -29,7 +29,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" int diff --git a/Build/source/libs/gmp/gmp-src/mpz/cmp_ui.c b/Build/source/libs/gmp/gmp-src/mpz/cmp_ui.c index 46fdd4e8011..4b40ab7a0ad 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/cmp_ui.c +++ b/Build/source/libs/gmp/gmp-src/mpz/cmp_ui.c @@ -29,7 +29,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" int diff --git a/Build/source/libs/gmp/gmp-src/mpz/cmpabs.c b/Build/source/libs/gmp/gmp-src/mpz/cmpabs.c index 5685776abe9..14f0dc95c82 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/cmpabs.c +++ b/Build/source/libs/gmp/gmp-src/mpz/cmpabs.c @@ -30,7 +30,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" diff --git a/Build/source/libs/gmp/gmp-src/mpz/cmpabs_d.c b/Build/source/libs/gmp/gmp-src/mpz/cmpabs_d.c index a4b95d26aa3..d2431cc927d 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/cmpabs_d.c +++ b/Build/source/libs/gmp/gmp-src/mpz/cmpabs_d.c @@ -34,7 +34,6 @@ see https://www.gnu.org/licenses/. */ #include <float.h> /* for DBL_MAX */ #endif -#include "gmp.h" #include "gmp-impl.h" diff --git a/Build/source/libs/gmp/gmp-src/mpz/cmpabs_ui.c b/Build/source/libs/gmp/gmp-src/mpz/cmpabs_ui.c index fceef6bbacc..6deffb3be5a 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/cmpabs_ui.c +++ b/Build/source/libs/gmp/gmp-src/mpz/cmpabs_ui.c @@ -29,7 +29,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" int diff --git a/Build/source/libs/gmp/gmp-src/mpz/com.c b/Build/source/libs/gmp/gmp-src/mpz/com.c index 66d69ce8b24..c5d22b08b78 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/com.c +++ b/Build/source/libs/gmp/gmp-src/mpz/com.c @@ -1,8 +1,8 @@ /* mpz_com(mpz_ptr dst, mpz_ptr src) -- Assign the bit-complemented value of SRC to DST. -Copyright 1991, 1993, 1994, 1996, 2001, 2003, 2012 Free Software Foundation, -Inc. +Copyright 1991, 1993, 1994, 1996, 2001, 2003, 2012, 2015 Free Software +Foundation, Inc. This file is part of the GNU MP Library. @@ -30,7 +30,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" void @@ -49,7 +48,7 @@ mpz_com (mpz_ptr dst, mpz_srcptr src) if (UNLIKELY (size == 0)) { /* special case, as mpn_add_1 wants size!=0 */ - PTR (dst)[0] = 1; + MPZ_NEWALLOC (dst, 1)[0] = 1; SIZ (dst) = -1; } else diff --git a/Build/source/libs/gmp/gmp-src/mpz/combit.c b/Build/source/libs/gmp/gmp-src/mpz/combit.c index b6d1daa09ee..0a2987564a2 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/combit.c +++ b/Build/source/libs/gmp/gmp-src/mpz/combit.c @@ -28,7 +28,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" void diff --git a/Build/source/libs/gmp/gmp-src/mpz/cong.c b/Build/source/libs/gmp/gmp-src/mpz/cong.c index 1855b5052ac..5d2d835f205 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/cong.c +++ b/Build/source/libs/gmp/gmp-src/mpz/cong.c @@ -28,7 +28,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" #include "longlong.h" diff --git a/Build/source/libs/gmp/gmp-src/mpz/cong_2exp.c b/Build/source/libs/gmp/gmp-src/mpz/cong_2exp.c index 8e78b173787..9de9645d783 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/cong_2exp.c +++ b/Build/source/libs/gmp/gmp-src/mpz/cong_2exp.c @@ -28,7 +28,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" diff --git a/Build/source/libs/gmp/gmp-src/mpz/cong_ui.c b/Build/source/libs/gmp/gmp-src/mpz/cong_ui.c index a9729d9a858..6f86c2327bc 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/cong_ui.c +++ b/Build/source/libs/gmp/gmp-src/mpz/cong_ui.c @@ -28,7 +28,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" #include "longlong.h" diff --git a/Build/source/libs/gmp/gmp-src/mpz/dive_ui.c b/Build/source/libs/gmp/gmp-src/mpz/dive_ui.c index 8a1b5a31ff8..c859b96197f 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/dive_ui.c +++ b/Build/source/libs/gmp/gmp-src/mpz/dive_ui.c @@ -28,7 +28,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" void diff --git a/Build/source/libs/gmp/gmp-src/mpz/divegcd.c b/Build/source/libs/gmp/gmp-src/mpz/divegcd.c index 3cb181c3195..dc236c3044a 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/divegcd.c +++ b/Build/source/libs/gmp/gmp-src/mpz/divegcd.c @@ -31,7 +31,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" #include "longlong.h" @@ -98,10 +97,10 @@ mpz_divexact_limb (mpz_ptr q, mpz_srcptr a, mp_limb_t d) qp = MPZ_REALLOC (q, abs_size); - mpn_divexact_1 (qp, PTR(a), abs_size, d); + MPN_DIVREM_OR_DIVEXACT_1 (qp, PTR(a), abs_size, d); abs_size -= (qp[abs_size-1] == 0); - SIZ(q) = (size>0 ? abs_size : -abs_size); + SIZ(q) = (size > 0 ? abs_size : -abs_size); } void diff --git a/Build/source/libs/gmp/gmp-src/mpz/divexact.c b/Build/source/libs/gmp/gmp-src/mpz/divexact.c index e9354715299..83368192583 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/divexact.c +++ b/Build/source/libs/gmp/gmp-src/mpz/divexact.c @@ -32,9 +32,7 @@ GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" -#include "longlong.h" void mpz_divexact (mpz_ptr quot, mpz_srcptr num, mpz_srcptr den) @@ -74,7 +72,7 @@ mpz_divexact (mpz_ptr quot, mpz_srcptr num, mpz_srcptr den) if (quot == num || quot == den) qp = TMP_ALLOC_LIMBS (qn); else - qp = MPZ_REALLOC (quot, qn); + qp = MPZ_NEWALLOC (quot, qn); np = PTR(num); dp = PTR(den); @@ -83,7 +81,7 @@ mpz_divexact (mpz_ptr quot, mpz_srcptr num, mpz_srcptr den) MPN_NORMALIZE (qp, qn); if (qp != PTR(quot)) - MPN_COPY (MPZ_REALLOC (quot, qn), qp, qn); + MPN_COPY (MPZ_NEWALLOC (quot, qn), qp, qn); SIZ(quot) = (SIZ(num) ^ SIZ(den)) >= 0 ? qn : -qn; diff --git a/Build/source/libs/gmp/gmp-src/mpz/divis.c b/Build/source/libs/gmp/gmp-src/mpz/divis.c index cd9d406846b..35429a750d7 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/divis.c +++ b/Build/source/libs/gmp/gmp-src/mpz/divis.c @@ -28,7 +28,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" int diff --git a/Build/source/libs/gmp/gmp-src/mpz/divis_2exp.c b/Build/source/libs/gmp/gmp-src/mpz/divis_2exp.c index db6cfa44339..4ecb0c013d3 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/divis_2exp.c +++ b/Build/source/libs/gmp/gmp-src/mpz/divis_2exp.c @@ -28,7 +28,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" diff --git a/Build/source/libs/gmp/gmp-src/mpz/divis_ui.c b/Build/source/libs/gmp/gmp-src/mpz/divis_ui.c index 41ff5f0b84e..b24c7dc74b0 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/divis_ui.c +++ b/Build/source/libs/gmp/gmp-src/mpz/divis_ui.c @@ -28,7 +28,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" #include "longlong.h" diff --git a/Build/source/libs/gmp/gmp-src/mpz/dump.c b/Build/source/libs/gmp/gmp-src/mpz/dump.c index 282be34db70..6135ddd4efd 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/dump.c +++ b/Build/source/libs/gmp/gmp-src/mpz/dump.c @@ -35,7 +35,6 @@ see https://www.gnu.org/licenses/. */ #include <stdio.h> #include <string.h> /* for strlen */ -#include "gmp.h" #include "gmp-impl.h" void diff --git a/Build/source/libs/gmp/gmp-src/mpz/export.c b/Build/source/libs/gmp/gmp-src/mpz/export.c index bc4c4df976a..2dacd691b72 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/export.c +++ b/Build/source/libs/gmp/gmp-src/mpz/export.c @@ -29,7 +29,6 @@ GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ #include <stdio.h> /* for NULL */ -#include "gmp.h" #include "gmp-impl.h" #include "longlong.h" diff --git a/Build/source/libs/gmp/gmp-src/mpz/fac_ui.c b/Build/source/libs/gmp/gmp-src/mpz/fac_ui.c index e0932272ff6..db3cfeee33a 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/fac_ui.c +++ b/Build/source/libs/gmp/gmp-src/mpz/fac_ui.c @@ -2,7 +2,8 @@ Contributed to the GNU project by Marco Bodrato. -Copyright 1991, 1993-1995, 2000-2003, 2011, 2012 Free Software Foundation, Inc. +Copyright 1991, 1993-1995, 2000-2003, 2011, 2012, 2015 Free Software +Foundation, Inc. This file is part of the GNU MP Library. @@ -30,7 +31,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" #define FACTOR_LIST_STORE(P, PR, MAX_PR, VEC, I) \ @@ -60,7 +60,7 @@ mpz_fac_ui (mpz_ptr x, unsigned long n) if (n < numberof (table)) { - PTR (x)[0] = table[n]; + MPZ_NEWALLOC (x, 1)[0] = table[n]; SIZ (x) = 1; } else if (BELOW_THRESHOLD (n, FAC_ODD_THRESHOLD)) diff --git a/Build/source/libs/gmp/gmp-src/mpz/fdiv_q.c b/Build/source/libs/gmp/gmp-src/mpz/fdiv_q.c index 5713b905b2a..f17023e10ce 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/fdiv_q.c +++ b/Build/source/libs/gmp/gmp-src/mpz/fdiv_q.c @@ -29,7 +29,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" void diff --git a/Build/source/libs/gmp/gmp-src/mpz/fdiv_q_ui.c b/Build/source/libs/gmp/gmp-src/mpz/fdiv_q_ui.c index 7899992d049..539f95183b9 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/fdiv_q_ui.c +++ b/Build/source/libs/gmp/gmp-src/mpz/fdiv_q_ui.c @@ -30,7 +30,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" unsigned long int diff --git a/Build/source/libs/gmp/gmp-src/mpz/fdiv_qr.c b/Build/source/libs/gmp/gmp-src/mpz/fdiv_qr.c index 36cfd367add..a0a6166dd62 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/fdiv_qr.c +++ b/Build/source/libs/gmp/gmp-src/mpz/fdiv_qr.c @@ -29,7 +29,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" void diff --git a/Build/source/libs/gmp/gmp-src/mpz/fdiv_qr_ui.c b/Build/source/libs/gmp/gmp-src/mpz/fdiv_qr_ui.c index c8435a423c4..984ca1c7291 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/fdiv_qr_ui.c +++ b/Build/source/libs/gmp/gmp-src/mpz/fdiv_qr_ui.c @@ -1,8 +1,8 @@ /* mpz_fdiv_qr_ui -- Division rounding the quotient towards -infinity. The remainder gets the same sign as the denominator. -Copyright 1994-1996, 1999, 2001, 2002, 2004, 2012 Free Software Foundation, -Inc. +Copyright 1994-1996, 1999, 2001, 2002, 2004, 2012, 2015 Free Software +Foundation, Inc. This file is part of the GNU MP Library. @@ -30,7 +30,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" unsigned long int @@ -62,8 +61,7 @@ mpz_fdiv_qr_ui (mpz_ptr quot, mpz_ptr rem, mpz_srcptr dividend, unsigned long in mp_ptr rp; mp_size_t rn; - MPZ_REALLOC (rem, 2); - rp = PTR(rem); + rp = MPZ_REALLOC (rem, 2); if (nn == 1) /* tdiv_qr requirements; tested above for 0 */ { @@ -107,7 +105,7 @@ mpz_fdiv_qr_ui (mpz_ptr quot, mpz_ptr rem, mpz_srcptr dividend, unsigned long in rl = divisor - rl; } - PTR(rem)[0] = rl; + MPZ_NEWALLOC (rem, 1)[0] = rl; SIZ(rem) = rl != 0; } qn = nn - (qp[nn - 1] == 0); diff --git a/Build/source/libs/gmp/gmp-src/mpz/fdiv_r.c b/Build/source/libs/gmp/gmp-src/mpz/fdiv_r.c index 35f2789b14c..c7a3c8ea846 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/fdiv_r.c +++ b/Build/source/libs/gmp/gmp-src/mpz/fdiv_r.c @@ -29,7 +29,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" void diff --git a/Build/source/libs/gmp/gmp-src/mpz/fdiv_r_ui.c b/Build/source/libs/gmp/gmp-src/mpz/fdiv_r_ui.c index 98dd56c6f22..f2df8a85d0b 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/fdiv_r_ui.c +++ b/Build/source/libs/gmp/gmp-src/mpz/fdiv_r_ui.c @@ -1,8 +1,8 @@ /* mpz_fdiv_r_ui -- Division rounding the quotient towards -infinity. The remainder gets the same sign as the denominator. -Copyright 1994-1996, 2001, 2002, 2004, 2005, 2012 Free Software Foundation, -Inc. +Copyright 1994-1996, 2001, 2002, 2004, 2005, 2012, 2015 Free Software +Foundation, Inc. This file is part of the GNU MP Library. @@ -30,7 +30,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" unsigned long int @@ -99,7 +98,7 @@ mpz_fdiv_r_ui (mpz_ptr rem, mpz_srcptr dividend, unsigned long int divisor) if (ns < 0) rl = divisor - rl; - PTR(rem)[0] = rl; + MPZ_NEWALLOC (rem, 1)[0] = rl; SIZ(rem) = 1; } } diff --git a/Build/source/libs/gmp/gmp-src/mpz/fdiv_ui.c b/Build/source/libs/gmp/gmp-src/mpz/fdiv_ui.c index 532ee2cbec5..f0aacdb65bd 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/fdiv_ui.c +++ b/Build/source/libs/gmp/gmp-src/mpz/fdiv_ui.c @@ -30,7 +30,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" unsigned long int diff --git a/Build/source/libs/gmp/gmp-src/mpz/fib2_ui.c b/Build/source/libs/gmp/gmp-src/mpz/fib2_ui.c index ddf456f5802..ea2622711e0 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/fib2_ui.c +++ b/Build/source/libs/gmp/gmp-src/mpz/fib2_ui.c @@ -1,6 +1,6 @@ /* mpz_fib2_ui -- calculate Fibonacci numbers. -Copyright 2001, 2012, 2014 Free Software Foundation, Inc. +Copyright 2001, 2012, 2014, 2015 Free Software Foundation, Inc. This file is part of the GNU MP Library. @@ -29,7 +29,6 @@ GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ #include <stdio.h> -#include "gmp.h" #include "gmp-impl.h" @@ -41,9 +40,9 @@ mpz_fib2_ui (mpz_ptr fn, mpz_ptr fnsub1, unsigned long n) if (n <= FIB_TABLE_LIMIT) { - PTR(fn)[0] = FIB_TABLE (n); + MPZ_NEWALLOC (fn, 1)[0] = FIB_TABLE (n); SIZ(fn) = (n != 0); /* F[0]==0, others are !=0 */ - PTR(fnsub1)[0] = FIB_TABLE ((int) n - 1); + MPZ_NEWALLOC (fnsub1, 1)[0] = FIB_TABLE ((int) n - 1); SIZ(fnsub1) = (n != 1); /* F[1-1]==0, others are !=0 */ return; } diff --git a/Build/source/libs/gmp/gmp-src/mpz/fib_ui.c b/Build/source/libs/gmp/gmp-src/mpz/fib_ui.c index f591c08501f..a65f3c9e7a2 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/fib_ui.c +++ b/Build/source/libs/gmp/gmp-src/mpz/fib_ui.c @@ -1,6 +1,6 @@ /* mpz_fib_ui -- calculate Fibonacci numbers. -Copyright 2000-2002, 2005, 2012, 2014 Free Software Foundation, Inc. +Copyright 2000-2002, 2005, 2012, 2014, 2015 Free Software Foundation, Inc. This file is part of the GNU MP Library. @@ -29,7 +29,6 @@ GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ #include <stdio.h> -#include "gmp.h" #include "gmp-impl.h" #include "longlong.h" @@ -65,7 +64,7 @@ mpz_fib_ui (mpz_ptr fn, unsigned long n) if (n <= FIB_TABLE_LIMIT) { - PTR(fn)[0] = FIB_TABLE (n); + MPZ_NEWALLOC (fn, 1)[0] = FIB_TABLE (n); SIZ(fn) = (n != 0); /* F[0]==0, others are !=0 */ return; } diff --git a/Build/source/libs/gmp/gmp-src/mpz/fits_s.h b/Build/source/libs/gmp/gmp-src/mpz/fits_s.h index e7f21d1b2bd..9fd6a0b633e 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/fits_s.h +++ b/Build/source/libs/gmp/gmp-src/mpz/fits_s.h @@ -28,7 +28,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" diff --git a/Build/source/libs/gmp/gmp-src/mpz/fits_uint.c b/Build/source/libs/gmp/gmp-src/mpz/fits_uint.c index a37e291b6ed..6becc8bf99d 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/fits_uint.c +++ b/Build/source/libs/gmp/gmp-src/mpz/fits_uint.c @@ -30,5 +30,4 @@ see https://www.gnu.org/licenses/. */ #define __GMP_FORCE_mpz_fits_uint_p 1 -#include "gmp.h" #include "gmp-impl.h" diff --git a/Build/source/libs/gmp/gmp-src/mpz/fits_ulong.c b/Build/source/libs/gmp/gmp-src/mpz/fits_ulong.c index fa40eb56710..c70886bbbca 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/fits_ulong.c +++ b/Build/source/libs/gmp/gmp-src/mpz/fits_ulong.c @@ -30,5 +30,4 @@ see https://www.gnu.org/licenses/. */ #define __GMP_FORCE_mpz_fits_ulong_p 1 -#include "gmp.h" #include "gmp-impl.h" diff --git a/Build/source/libs/gmp/gmp-src/mpz/fits_ushort.c b/Build/source/libs/gmp/gmp-src/mpz/fits_ushort.c index 7f6f907821b..16873d61d62 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/fits_ushort.c +++ b/Build/source/libs/gmp/gmp-src/mpz/fits_ushort.c @@ -30,5 +30,4 @@ see https://www.gnu.org/licenses/. */ #define __GMP_FORCE_mpz_fits_ushort_p 1 -#include "gmp.h" #include "gmp-impl.h" diff --git a/Build/source/libs/gmp/gmp-src/mpz/gcd.c b/Build/source/libs/gmp/gmp-src/mpz/gcd.c index 87c6a8f17b7..9557155f9ab 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/gcd.c +++ b/Build/source/libs/gmp/gmp-src/mpz/gcd.c @@ -1,7 +1,7 @@ /* mpz/gcd.c: Calculate the greatest common divisor of two integers. -Copyright 1991, 1993, 1994, 1996, 2000-2002, 2005, 2010 Free Software -Foundation, Inc. +Copyright 1991, 1993, 1994, 1996, 2000-2002, 2005, 2010, 2015, 2016 +Free Software Foundation, Inc. This file is part of the GNU MP Library. @@ -29,7 +29,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" #include "longlong.h" @@ -57,8 +56,8 @@ mpz_gcd (mpz_ptr g, mpz_srcptr u, mpz_srcptr v) SIZ (g) = vsize; if (g == v) return; - MPZ_REALLOC (g, vsize); - MPN_COPY (PTR (g), vp, vsize); + tp = MPZ_NEWALLOC (g, vsize); + MPN_COPY (tp, vp, vsize); return; } @@ -68,34 +67,34 @@ mpz_gcd (mpz_ptr g, mpz_srcptr u, mpz_srcptr v) SIZ (g) = usize; if (g == u) return; - MPZ_REALLOC (g, usize); - MPN_COPY (PTR (g), up, usize); + tp = MPZ_NEWALLOC (g, usize); + MPN_COPY (tp, up, usize); return; } if (usize == 1) { SIZ (g) = 1; - PTR (g)[0] = mpn_gcd_1 (vp, vsize, up[0]); + MPZ_NEWALLOC (g, 1)[0] = mpn_gcd_1 (vp, vsize, up[0]); return; } if (vsize == 1) { SIZ(g) = 1; - PTR (g)[0] = mpn_gcd_1 (up, usize, vp[0]); + MPZ_NEWALLOC (g, 1)[0] = mpn_gcd_1 (up, usize, vp[0]); return; } TMP_MARK; /* Eliminate low zero bits from U and V and move to temporary storage. */ - while (*up == 0) - up++; - u_zero_limbs = up - PTR(u); - usize -= u_zero_limbs; - count_trailing_zeros (u_zero_bits, *up); tp = up; + while (*tp == 0) + tp++; + u_zero_limbs = tp - up; + usize -= u_zero_limbs; + count_trailing_zeros (u_zero_bits, *tp); up = TMP_ALLOC_LIMBS (usize); if (u_zero_bits != 0) { @@ -105,12 +104,12 @@ mpz_gcd (mpz_ptr g, mpz_srcptr u, mpz_srcptr v) else MPN_COPY (up, tp, usize); - while (*vp == 0) - vp++; - v_zero_limbs = vp - PTR (v); - vsize -= v_zero_limbs; - count_trailing_zeros (v_zero_bits, *vp); tp = vp; + while (*tp == 0) + tp++; + v_zero_limbs = tp - vp; + vsize -= v_zero_limbs; + count_trailing_zeros (v_zero_bits, *tp); vp = TMP_ALLOC_LIMBS (vsize); if (v_zero_bits != 0) { @@ -125,15 +124,13 @@ mpz_gcd (mpz_ptr g, mpz_srcptr u, mpz_srcptr v) g_zero_limbs = v_zero_limbs; g_zero_bits = v_zero_bits; } - else if (u_zero_limbs < v_zero_limbs) - { - g_zero_limbs = u_zero_limbs; - g_zero_bits = u_zero_bits; - } - else /* Equal. */ + else { g_zero_limbs = u_zero_limbs; - g_zero_bits = MIN (u_zero_bits, v_zero_bits); + if (u_zero_limbs < v_zero_limbs) + g_zero_bits = u_zero_bits; + else /* Equal. */ + g_zero_bits = MIN (u_zero_bits, v_zero_bits); } /* Call mpn_gcd. The 2nd argument must not have more bits than the 1st. */ @@ -147,19 +144,19 @@ mpz_gcd (mpz_ptr g, mpz_srcptr u, mpz_srcptr v) { mp_limb_t cy_limb; gsize += (vp[vsize - 1] >> (GMP_NUMB_BITS - g_zero_bits)) != 0; - MPZ_REALLOC (g, gsize); - MPN_ZERO (PTR (g), g_zero_limbs); + tp = MPZ_NEWALLOC (g, gsize); + MPN_ZERO (tp, g_zero_limbs); - tp = PTR(g) + g_zero_limbs; + tp = tp + g_zero_limbs; cy_limb = mpn_lshift (tp, vp, vsize, g_zero_bits); if (cy_limb != 0) tp[vsize] = cy_limb; } else { - MPZ_REALLOC (g, gsize); - MPN_ZERO (PTR (g), g_zero_limbs); - MPN_COPY (PTR (g) + g_zero_limbs, vp, vsize); + tp = MPZ_NEWALLOC (g, gsize); + MPN_ZERO (tp, g_zero_limbs); + MPN_COPY (tp + g_zero_limbs, vp, vsize); } SIZ (g) = gsize; diff --git a/Build/source/libs/gmp/gmp-src/mpz/gcd_ui.c b/Build/source/libs/gmp/gmp-src/mpz/gcd_ui.c index e26d03f64a9..ee5bff81c57 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/gcd_ui.c +++ b/Build/source/libs/gmp/gmp-src/mpz/gcd_ui.c @@ -1,6 +1,6 @@ /* mpz_gcd_ui -- Calculate the greatest common divisor of two integers. -Copyright 1994, 1996, 1999-2004 Free Software Foundation, Inc. +Copyright 1994, 1996, 1999-2004, 2015 Free Software Foundation, Inc. This file is part of the GNU MP Library. @@ -29,7 +29,6 @@ GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ #include <stdio.h> /* for NULL */ -#include "gmp.h" #include "gmp-impl.h" unsigned long int @@ -64,7 +63,7 @@ mpz_gcd_ui (mpz_ptr w, mpz_srcptr u, unsigned long int v) { if (u != w) { - MPZ_REALLOC (w, un); + MPZ_NEWALLOC (w, un); MPN_COPY (PTR(w), PTR(u), un); } SIZ(w) = un; @@ -78,7 +77,7 @@ mpz_gcd_ui (mpz_ptr w, mpz_srcptr u, unsigned long int v) if (w != NULL) { - PTR(w)[0] = res; + MPZ_NEWALLOC (w, 1)[0] = res; SIZ(w) = res != 0; } return res; diff --git a/Build/source/libs/gmp/gmp-src/mpz/gcdext.c b/Build/source/libs/gmp/gmp-src/mpz/gcdext.c index 01b1f8379ae..b1f73c255c0 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/gcdext.c +++ b/Build/source/libs/gmp/gmp-src/mpz/gcdext.c @@ -1,8 +1,8 @@ /* mpz_gcdext(g, s, t, a, b) -- Set G to gcd(a, b), and S and T such that g = as + bt. -Copyright 1991, 1993-1997, 2000, 2001, 2005, 2011, 2012 Free Software -Foundation, Inc. +Copyright 1991, 1993-1997, 2000, 2001, 2005, 2011, 2012, 2015 Free +Software Foundation, Inc. This file is part of the GNU MP Library. @@ -31,7 +31,6 @@ GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ #include <stdio.h> /* for NULL */ -#include "gmp.h" #include "gmp-impl.h" void @@ -51,6 +50,8 @@ mpz_gcdext (mpz_ptr g, mpz_ptr s, mpz_ptr t, mpz_srcptr a, mpz_srcptr b) asize = ABSIZ (a); bsize = ABSIZ (b); + ASSERT (s != NULL); + if (asize < bsize) { MPZ_SRCPTR_SWAP (a, b); @@ -63,28 +64,32 @@ mpz_gcdext (mpz_ptr g, mpz_ptr s, mpz_ptr t, mpz_srcptr a, mpz_srcptr b) /* g = |a|, s = sgn(a), t = 0. */ ssize = SIZ (a) >= 0 ? (asize != 0) : -1; - gp = MPZ_REALLOC (g, asize); - MPN_COPY (gp, PTR (a), asize); - SIZ (g) = asize; - + if (g != NULL) + { + /* If g == a, then ALLOC(g) == ALLOC(a) >= asize, i.e. + the next MPZ_NEWALLOC returns the old PTR(a) .*/ + gp = MPZ_NEWALLOC (g, asize); + MPN_COPY (gp, PTR (a), asize); + SIZ (g) = asize; + } if (t != NULL) SIZ (t) = 0; if (s != NULL) { SIZ (s) = ssize; - PTR (s)[0] = 1; + MPZ_NEWALLOC (s, 1)[0] = 1; } return; } TMP_MARK; - TMP_ALLOC_LIMBS_2 (tmp_ap, asize, tmp_bp, bsize); + TMP_ALLOC_LIMBS_2 (tmp_gp, bsize, tmp_sp, asize + bsize + bsize + 1); + tmp_bp = tmp_sp + bsize + 1; + tmp_ap = tmp_bp + bsize; MPN_COPY (tmp_ap, PTR (a), asize); MPN_COPY (tmp_bp, PTR (b), bsize); - TMP_ALLOC_LIMBS_2 (tmp_gp, bsize, tmp_sp, bsize + 1); - gsize = mpn_gcdext (tmp_gp, tmp_sp, &tmp_ssize, tmp_ap, asize, tmp_bp, bsize); ssize = ABS (tmp_ssize); @@ -93,17 +98,20 @@ mpz_gcdext (mpz_ptr g, mpz_ptr s, mpz_ptr t, mpz_srcptr a, mpz_srcptr b) if (t != NULL) { mpz_t x; - __mpz_struct gtmp, stmp; + mpz_t gtmp, stmp; + + PTR (gtmp) = tmp_gp; + SIZ (gtmp) = gsize; - PTR (>mp) = tmp_gp; - SIZ (>mp) = gsize; + PTR (stmp) = tmp_sp; + SIZ (stmp) = tmp_ssize; - PTR (&stmp) = tmp_sp; - SIZ (&stmp) = tmp_ssize; + ASSERT (ssize <= bsize); /* ssize*2 + asize + 1 <= asize + bsize*2 + 1 */ + PTR (x) = tmp_sp + ssize; + ALLOC (x) = ssize + asize + 1; - MPZ_TMP_INIT (x, ssize + asize + 1); - mpz_mul (x, &stmp, a); - mpz_sub (x, >mp, x); + mpz_mul (x, stmp, a); + mpz_sub (x, gtmp, x); mpz_divexact (t, x, b); } @@ -111,14 +119,17 @@ mpz_gcdext (mpz_ptr g, mpz_ptr s, mpz_ptr t, mpz_srcptr a, mpz_srcptr b) { mp_ptr sp; - sp = MPZ_REALLOC (s, ssize); + sp = MPZ_NEWALLOC (s, ssize); MPN_COPY (sp, tmp_sp, ssize); SIZ (s) = tmp_ssize; } - gp = MPZ_REALLOC (g, gsize); - MPN_COPY (gp, tmp_gp, gsize); - SIZ (g) = gsize; + if (g != NULL) + { + gp = MPZ_NEWALLOC (g, gsize); + MPN_COPY (gp, tmp_gp, gsize); + SIZ (g) = gsize; + } TMP_FREE; } diff --git a/Build/source/libs/gmp/gmp-src/mpz/get_d.c b/Build/source/libs/gmp/gmp-src/mpz/get_d.c index ac653c5ba01..61d4e3612ed 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/get_d.c +++ b/Build/source/libs/gmp/gmp-src/mpz/get_d.c @@ -28,7 +28,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" double diff --git a/Build/source/libs/gmp/gmp-src/mpz/get_d_2exp.c b/Build/source/libs/gmp/gmp-src/mpz/get_d_2exp.c index 96314851bf8..beb364a5f37 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/get_d_2exp.c +++ b/Build/source/libs/gmp/gmp-src/mpz/get_d_2exp.c @@ -28,7 +28,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" #include "longlong.h" diff --git a/Build/source/libs/gmp/gmp-src/mpz/get_si.c b/Build/source/libs/gmp/gmp-src/mpz/get_si.c index 6e9752636b2..c65be2e0ae8 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/get_si.c +++ b/Build/source/libs/gmp/gmp-src/mpz/get_si.c @@ -28,7 +28,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" signed long int diff --git a/Build/source/libs/gmp/gmp-src/mpz/get_str.c b/Build/source/libs/gmp/gmp-src/mpz/get_str.c index 08c7cd73710..c00a9a33d19 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/get_str.c +++ b/Build/source/libs/gmp/gmp-src/mpz/get_str.c @@ -4,8 +4,8 @@ result. If STRING is not NULL, the caller must ensure enough space is available to store the result. -Copyright 1991, 1993, 1994, 1996, 2000-2002, 2005, 2012 Free Software -Foundation, Inc. +Copyright 1991, 1993, 1994, 1996, 2000-2002, 2005, 2012, 2017 Free +Software Foundation, Inc. This file is part of the GNU MP Library. @@ -34,7 +34,6 @@ GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ #include <string.h> /* for strlen */ -#include "gmp.h" #include "gmp-impl.h" #include "longlong.h" @@ -50,26 +49,23 @@ mpz_get_str (char *res_str, int base, mpz_srcptr x) int i; TMP_DECL; - if (base >= 0) + num_to_text = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"; + if (base > 1) { - num_to_text = "0123456789abcdefghijklmnopqrstuvwxyz"; - if (base <= 1) - base = 10; - else if (base > 36) - { - num_to_text = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"; - if (base > 62) - return NULL; - } + if (base <= 36) + num_to_text = "0123456789abcdefghijklmnopqrstuvwxyz"; + else if (UNLIKELY (base > 62)) + return NULL; + } + else if (base > -2) + { + base = 10; } else { base = -base; - if (base <= 1) - base = 10; - else if (base > 36) + if (UNLIKELY (base > 36)) return NULL; - num_to_text = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"; } /* allocate string for the user if necessary */ @@ -78,7 +74,7 @@ mpz_get_str (char *res_str, int base, mpz_srcptr x) /* digits, null terminator, possible minus sign */ MPN_SIZEINBASE (alloc_size, PTR(x), ABS(x_size), base); alloc_size += 1 + (x_size<0); - res_str = (char *) (*__gmp_allocate_func) (alloc_size); + res_str = __GMP_ALLOCATE_FUNC_TYPE (alloc_size, char); } return_str = res_str; diff --git a/Build/source/libs/gmp/gmp-src/mpz/get_ui.c b/Build/source/libs/gmp/gmp-src/mpz/get_ui.c index ca97788b745..2d7ea4e61d4 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/get_ui.c +++ b/Build/source/libs/gmp/gmp-src/mpz/get_ui.c @@ -30,5 +30,4 @@ see https://www.gnu.org/licenses/. */ #define __GMP_FORCE_mpz_get_ui 1 -#include "gmp.h" #include "gmp-impl.h" diff --git a/Build/source/libs/gmp/gmp-src/mpz/getlimbn.c b/Build/source/libs/gmp/gmp-src/mpz/getlimbn.c index c531f7e61f6..d34d764d647 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/getlimbn.c +++ b/Build/source/libs/gmp/gmp-src/mpz/getlimbn.c @@ -30,5 +30,4 @@ see https://www.gnu.org/licenses/. */ #define __GMP_FORCE_mpz_getlimbn 1 -#include "gmp.h" #include "gmp-impl.h" diff --git a/Build/source/libs/gmp/gmp-src/mpz/hamdist.c b/Build/source/libs/gmp/gmp-src/mpz/hamdist.c index 146769c3945..1dfb7b88ff3 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/hamdist.c +++ b/Build/source/libs/gmp/gmp-src/mpz/hamdist.c @@ -28,7 +28,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" diff --git a/Build/source/libs/gmp/gmp-src/mpz/import.c b/Build/source/libs/gmp/gmp-src/mpz/import.c index 9072830afee..e40b5ed5779 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/import.c +++ b/Build/source/libs/gmp/gmp-src/mpz/import.c @@ -29,7 +29,6 @@ GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ #include <stdio.h> -#include "gmp.h" #include "gmp-impl.h" diff --git a/Build/source/libs/gmp/gmp-src/mpz/init.c b/Build/source/libs/gmp/gmp-src/mpz/init.c index addbdbdedbd..b85a2da2585 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/init.c +++ b/Build/source/libs/gmp/gmp-src/mpz/init.c @@ -1,6 +1,7 @@ /* mpz_init() -- Make a new multiple precision number with value 0. -Copyright 1991, 1993-1995, 2000-2002, 2012 Free Software Foundation, Inc. +Copyright 1991, 1993-1995, 2000-2002, 2012, 2015 Free Software +Foundation, Inc. This file is part of the GNU MP Library. @@ -28,18 +29,13 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" void -mpz_init (mpz_ptr x) +mpz_init (mpz_ptr x) __GMP_NOTHROW { - ALLOC (x) = 1; - PTR (x) = __GMP_ALLOCATE_FUNC_LIMBS (1); + static const mp_limb_t dummy_limb=0xc1a0; + ALLOC (x) = 0; + PTR (x) = (mp_ptr) &dummy_limb; SIZ (x) = 0; - -#ifdef __CHECKER__ - /* let the low limb look initialized, for the benefit of mpz_get_ui etc */ - PTR (x)[0] = 0; -#endif } diff --git a/Build/source/libs/gmp/gmp-src/mpz/init2.c b/Build/source/libs/gmp/gmp-src/mpz/init2.c index b942e499d62..fcbaa66dbf5 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/init2.c +++ b/Build/source/libs/gmp/gmp-src/mpz/init2.c @@ -30,7 +30,6 @@ see https://www.gnu.org/licenses/. */ #include <stdlib.h> #include <stdio.h> -#include "gmp.h" #include "gmp-impl.h" void @@ -53,9 +52,4 @@ mpz_init2 (mpz_ptr x, mp_bitcnt_t bits) PTR(x) = __GMP_ALLOCATE_FUNC_LIMBS (new_alloc); ALLOC(x) = new_alloc; SIZ(x) = 0; - -#ifdef __CHECKER__ - /* let the low limb look initialized, for the benefit of mpz_get_ui etc */ - PTR(x)[0] = 0; -#endif } diff --git a/Build/source/libs/gmp/gmp-src/mpz/inits.c b/Build/source/libs/gmp/gmp-src/mpz/inits.c index 68457e0fb29..1660744e665 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/inits.c +++ b/Build/source/libs/gmp/gmp-src/mpz/inits.c @@ -29,29 +29,25 @@ GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ #include <stdarg.h> -#include "gmp.h" #include "gmp-impl.h" void -mpz_inits (mpz_ptr x, ...) +mpz_inits (mpz_ptr x, ...) __GMP_NOTHROW { + static const mp_limb_t dummy_limb=0xc1a0; va_list ap; va_start (ap, x); - while (x != NULL) + do { - ALLOC (x) = 1; - PTR (x) = __GMP_ALLOCATE_FUNC_LIMBS (1); + ALLOC (x) = 0; + PTR (x) = (mp_ptr) &dummy_limb; SIZ (x) = 0; -#ifdef __CHECKER__ - /* let the low limb look initialized, for the benefit of mpz_get_ui etc */ - PTR (x)[0] = 0; -#endif - x = va_arg (ap, mpz_ptr); } + while (x != NULL); va_end (ap); } diff --git a/Build/source/libs/gmp/gmp-src/mpz/inp_raw.c b/Build/source/libs/gmp/gmp-src/mpz/inp_raw.c index b7994a3604b..378c42bb4e7 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/inp_raw.c +++ b/Build/source/libs/gmp/gmp-src/mpz/inp_raw.c @@ -29,7 +29,6 @@ GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ #include <stdio.h> -#include "gmp.h" #include "gmp-impl.h" diff --git a/Build/source/libs/gmp/gmp-src/mpz/inp_str.c b/Build/source/libs/gmp/gmp-src/mpz/inp_str.c index 474bc68435f..0756055be02 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/inp_str.c +++ b/Build/source/libs/gmp/gmp-src/mpz/inp_str.c @@ -36,7 +36,6 @@ see https://www.gnu.org/licenses/. */ #include <stdio.h> #include <ctype.h> -#include "gmp.h" #include "gmp-impl.h" #include "longlong.h" @@ -84,7 +83,7 @@ mpz_inp_str_nowhite (mpz_ptr x, FILE *stream, int base, int c, size_t nread) /* For bases > 36, use the collating sequence 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz. */ digit_value += 208; - if (base > 62) + if (UNLIKELY (base > 62)) return 0; /* too large base */ } @@ -132,7 +131,7 @@ mpz_inp_str_nowhite (mpz_ptr x, FILE *stream, int base, int c, size_t nread) } alloc_size = 100; - str = (char *) (*__gmp_allocate_func) (alloc_size); + str = __GMP_ALLOCATE_FUNC_TYPE (alloc_size, char); str_size = 0; while (c != EOF) @@ -145,7 +144,7 @@ mpz_inp_str_nowhite (mpz_ptr x, FILE *stream, int base, int c, size_t nread) { size_t old_alloc_size = alloc_size; alloc_size = alloc_size * 3 / 2; - str = (char *) (*__gmp_reallocate_func) (str, old_alloc_size, alloc_size); + str = __GMP_REALLOCATE_FUNC_TYPE (str, old_alloc_size, alloc_size, char); } str[str_size++] = dig; c = getc (stream); @@ -163,7 +162,7 @@ mpz_inp_str_nowhite (mpz_ptr x, FILE *stream, int base, int c, size_t nread) else { LIMBS_PER_DIGIT_IN_BASE (xsize, str_size, base); - MPZ_REALLOC (x, xsize); + MPZ_NEWALLOC (x, xsize); /* Convert the byte array in base BASE to our bignum format. */ xsize = mpn_set_str (PTR (x), (unsigned char *) str, str_size, base); diff --git a/Build/source/libs/gmp/gmp-src/mpz/invert.c b/Build/source/libs/gmp/gmp-src/mpz/invert.c index 09cdd9a121a..5532d137c72 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/invert.c +++ b/Build/source/libs/gmp/gmp-src/mpz/invert.c @@ -30,7 +30,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" int diff --git a/Build/source/libs/gmp/gmp-src/mpz/ior.c b/Build/source/libs/gmp/gmp-src/mpz/ior.c index 5c181f04c4c..32f304278c9 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/ior.c +++ b/Build/source/libs/gmp/gmp-src/mpz/ior.c @@ -1,7 +1,7 @@ /* mpz_ior -- Logical inclusive or. -Copyright 1991, 1993, 1994, 1996, 1997, 2000, 2001, 2005, 2012, 2013 Free -Software Foundation, Inc. +Copyright 1991, 1993, 1994, 1996, 1997, 2000, 2001, 2005, 2012, 2013, +2015-2018 Free Software Foundation, Inc. This file is part of the GNU MP Library. @@ -29,7 +29,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" void @@ -40,76 +39,49 @@ mpz_ior (mpz_ptr res, mpz_srcptr op1, mpz_srcptr op2) mp_ptr res_ptr; mp_size_t res_size; mp_size_t i; - TMP_DECL; - TMP_MARK; op1_size = SIZ(op1); op2_size = SIZ(op2); + if (op1_size < op2_size) + { + MPZ_SRCPTR_SWAP (op1, op2); + MP_SIZE_T_SWAP (op1_size, op2_size); + } + op1_ptr = PTR(op1); - op2_ptr = PTR(op2); res_ptr = PTR(res); - if (op1_size >= 0) + if (op2_size >= 0) { - if (op2_size >= 0) - { - if (op1_size >= op2_size) - { - if (ALLOC(res) < op1_size) - { - res_ptr = MPZ_REALLOC (res, op1_size); - /* No overlapping possible: op1_ptr = PTR(op1); */ - op2_ptr = PTR(op2); - } - - if (res_ptr != op1_ptr) - MPN_COPY (res_ptr + op2_size, op1_ptr + op2_size, - op1_size - op2_size); - if (LIKELY (op2_size != 0)) - mpn_ior_n (res_ptr, op1_ptr, op2_ptr, op2_size); - res_size = op1_size; - } - else - { - if (ALLOC(res) < op2_size) - { - res_ptr = MPZ_REALLOC (res, op2_size); - op1_ptr = PTR(op1); - /* No overlapping possible: op2_ptr = PTR(op2); */ - } - - if (res_ptr != op2_ptr) - MPN_COPY (res_ptr + op1_size, op2_ptr + op1_size, - op2_size - op1_size); - if (LIKELY (op1_size != 0)) - mpn_ior_n (res_ptr, op1_ptr, op2_ptr, op1_size); - res_size = op2_size; - } - - SIZ(res) = res_size; - return; - } - else /* op2_size < 0 */ + if (res_ptr != op1_ptr) { - /* Fall through to the code at the end of the function. */ + res_ptr = MPZ_REALLOC (res, op1_size); + /* No overlapping possible: op1_ptr = PTR(op1); */ + MPN_COPY (res_ptr + op2_size, op1_ptr + op2_size, + op1_size - op2_size); } + if (LIKELY (op2_size != 0)) + mpn_ior_n (res_ptr, op1_ptr, PTR(op2), op2_size); + + SIZ(res) = op1_size; } else { - if (op2_size < 0) + mp_ptr opx; + TMP_DECL; + + TMP_MARK; + if (op1_size < 0) { - mp_ptr opx, opy; + mp_ptr opy; /* Both operands are negative, so will be the result. -((-OP1) | (-OP2)) = -(~(OP1 - 1) | ~(OP2 - 1)) = = ~(~(OP1 - 1) | ~(OP2 - 1)) + 1 = = ((OP1 - 1) & (OP2 - 1)) + 1 */ - op1_size = -op1_size; - op2_size = -op2_size; - - res_size = MIN (op1_size, op2_size); + res_size = -op1_size; /* Possible optimization: Decrease mpn_sub precision, as we won't use the entire res of both. */ @@ -117,19 +89,19 @@ mpz_ior (mpz_ptr res, mpz_srcptr op1, mpz_srcptr op2) mpn_sub_1 (opx, op1_ptr, res_size, (mp_limb_t) 1); op1_ptr = opx; - mpn_sub_1 (opy, op2_ptr, res_size, (mp_limb_t) 1); + mpn_sub_1 (opy, PTR(op2), res_size, (mp_limb_t) 1); op2_ptr = opy; /* First loop finds the size of the result. */ - for (i = res_size - 1; i >= 0; i--) + for (i = res_size; --i >= 0;) if ((op1_ptr[i] & op2_ptr[i]) != 0) break; res_size = i + 1; + res_ptr = MPZ_NEWALLOC (res, res_size + 1); + if (res_size != 0) { - res_ptr = MPZ_NEWALLOC (res, res_size + 1); - /* Second loop computes the real result. */ mpn_and_n (res_ptr, op1_ptr, op2_ptr, res_size); @@ -144,87 +116,69 @@ mpz_ior (mpz_ptr res, mpz_srcptr op1, mpz_srcptr op2) } SIZ(res) = -res_size; - TMP_FREE; - return; } else { - /* We should compute -OP1 | OP2. Swap OP1 and OP2 and fall - through to the code that handles OP1 | -OP2. */ - MPZ_SRCPTR_SWAP (op1, op2); - MPN_SRCPTR_SWAP (op1_ptr,op1_size, op2_ptr,op2_size); + mp_limb_t cy; + mp_size_t count; + + /* Operand 2 negative, so will be the result. + -(OP1 | (-OP2)) = -(OP1 | ~(OP2 - 1)) = + = ~(OP1 | ~(OP2 - 1)) + 1 = + = (~OP1 & (OP2 - 1)) + 1 */ + + op2_size = -op2_size; + + res_ptr = MPZ_REALLOC (res, op2_size); + op1_ptr = PTR(op1); + + opx = TMP_ALLOC_LIMBS (op2_size); + mpn_sub_1 (opx, PTR(op2), op2_size, (mp_limb_t) 1); + op2_ptr = opx; + op2_size -= op2_ptr[op2_size - 1] == 0; + + if (op1_size >= op2_size) + { + /* We can just ignore the part of OP1 that stretches above OP2, + because the result limbs are zero there. */ + + /* First loop finds the size of the result. */ + for (i = op2_size; --i >= 0;) + if ((~op1_ptr[i] & op2_ptr[i]) != 0) + break; + res_size = i + 1; + count = res_size; + } + else + { + res_size = op2_size; + + /* Copy the part of OP2 that stretches above OP1, to RES. */ + MPN_COPY (res_ptr + op1_size, op2_ptr + op1_size, op2_size - op1_size); + count = op1_size; + } + + if (res_size != 0) + { + /* Second loop computes the real result. */ + if (LIKELY (count != 0)) + mpn_andn_n (res_ptr, op2_ptr, op1_ptr, count); + + cy = mpn_add_1 (res_ptr, res_ptr, res_size, (mp_limb_t) 1); + if (cy) + { + res_ptr[res_size] = cy; + ++res_size; + } + } + else + { + res_ptr[0] = 1; + res_size = 1; + } + + SIZ(res) = -res_size; } + TMP_FREE; } - - { - mp_ptr opx; - mp_limb_t cy; - mp_size_t res_alloc; - mp_size_t count; - - /* Operand 2 negative, so will be the result. - -(OP1 | (-OP2)) = -(OP1 | ~(OP2 - 1)) = - = ~(OP1 | ~(OP2 - 1)) + 1 = - = (~OP1 & (OP2 - 1)) + 1 */ - - op2_size = -op2_size; - - res_alloc = op2_size; - - opx = TMP_ALLOC_LIMBS (op2_size); - mpn_sub_1 (opx, op2_ptr, op2_size, (mp_limb_t) 1); - op2_ptr = opx; - op2_size -= op2_ptr[op2_size - 1] == 0; - - if (ALLOC(res) < res_alloc) - { - _mpz_realloc (res, res_alloc); - op1_ptr = PTR(op1); - /* op2_ptr points to temporary space. */ - res_ptr = PTR(res); - } - - if (op1_size >= op2_size) - { - /* We can just ignore the part of OP1 that stretches above OP2, - because the result limbs are zero there. */ - - /* First loop finds the size of the result. */ - for (i = op2_size - 1; i >= 0; i--) - if ((~op1_ptr[i] & op2_ptr[i]) != 0) - break; - res_size = i + 1; - count = res_size; - } - else - { - res_size = op2_size; - - /* Copy the part of OP2 that stretches above OP1, to RES. */ - MPN_COPY (res_ptr + op1_size, op2_ptr + op1_size, op2_size - op1_size); - count = op1_size; - } - - if (res_size != 0) - { - /* Second loop computes the real result. */ - if (LIKELY (count != 0)) - mpn_andn_n (res_ptr, op2_ptr, op1_ptr, count); - - cy = mpn_add_1 (res_ptr, res_ptr, res_size, (mp_limb_t) 1); - if (cy) - { - res_ptr[res_size] = cy; - res_size++; - } - } - else - { - res_ptr[0] = 1; - res_size = 1; - } - - SIZ(res) = -res_size; - } - TMP_FREE; } diff --git a/Build/source/libs/gmp/gmp-src/mpz/iset.c b/Build/source/libs/gmp/gmp-src/mpz/iset.c index 0fd6e8f9dd8..252cada2978 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/iset.c +++ b/Build/source/libs/gmp/gmp-src/mpz/iset.c @@ -30,7 +30,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" void @@ -43,17 +42,11 @@ mpz_init_set (mpz_ptr w, mpz_srcptr u) size = ABS (usize); ALLOC (w) = MAX (size, 1); - PTR (w) = __GMP_ALLOCATE_FUNC_LIMBS (ALLOC (w)); + wp = __GMP_ALLOCATE_FUNC_LIMBS (ALLOC (w)); - wp = PTR (w); + PTR (w) = wp; up = PTR (u); MPN_COPY (wp, up, size); SIZ (w) = usize; - -#ifdef __CHECKER__ - /* let the low limb look initialized, for the benefit of mpz_get_ui etc */ - if (size == 0) - wp[0] = 0; -#endif } diff --git a/Build/source/libs/gmp/gmp-src/mpz/iset_d.c b/Build/source/libs/gmp/gmp-src/mpz/iset_d.c index 2c5b23ab9c9..5d04a6fd9e6 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/iset_d.c +++ b/Build/source/libs/gmp/gmp-src/mpz/iset_d.c @@ -1,7 +1,7 @@ /* mpz_init_set_d(integer, val) -- Initialize and assign INTEGER with a double value VAL. -Copyright 1996, 2000, 2001, 2012 Free Software Foundation, Inc. +Copyright 1996, 2000, 2001, 2012, 2015 Free Software Foundation, Inc. This file is part of the GNU MP Library. @@ -29,14 +29,15 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" void mpz_init_set_d (mpz_ptr dest, double val) { - ALLOC (dest) = 1; - PTR (dest) = __GMP_ALLOCATE_FUNC_LIMBS (1); + static const mp_limb_t dummy_limb=0xc1a0; + + ALLOC (dest) = 0; SIZ (dest) = 0; + PTR (dest) = (mp_ptr) &dummy_limb; mpz_set_d (dest, val); } diff --git a/Build/source/libs/gmp/gmp-src/mpz/iset_si.c b/Build/source/libs/gmp/gmp-src/mpz/iset_si.c index 0844972280f..7179cb0ad12 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/iset_si.c +++ b/Build/source/libs/gmp/gmp-src/mpz/iset_si.c @@ -29,7 +29,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" void diff --git a/Build/source/libs/gmp/gmp-src/mpz/iset_str.c b/Build/source/libs/gmp/gmp-src/mpz/iset_str.c index 47798dd68b0..2df12f9a014 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/iset_str.c +++ b/Build/source/libs/gmp/gmp-src/mpz/iset_str.c @@ -31,22 +31,17 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" int mpz_init_set_str (mpz_ptr x, const char *str, int base) { - ALLOC (x) = 1; - PTR (x) = __GMP_ALLOCATE_FUNC_LIMBS (1); + static const mp_limb_t dummy_limb=0xc1a0; + ALLOC (x) = 0; + PTR (x) = (mp_ptr) &dummy_limb; /* if str has no digits mpz_set_str leaves x->_mp_size unset */ SIZ (x) = 0; -#ifdef __CHECKER__ - /* let the low limb look initialized, for the benefit of mpz_get_ui etc */ - PTR (x)[0] = 0; -#endif - return mpz_set_str (x, str, base); } diff --git a/Build/source/libs/gmp/gmp-src/mpz/iset_ui.c b/Build/source/libs/gmp/gmp-src/mpz/iset_ui.c index 55da84fcd44..22a8e151cbb 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/iset_ui.c +++ b/Build/source/libs/gmp/gmp-src/mpz/iset_ui.c @@ -29,7 +29,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" void diff --git a/Build/source/libs/gmp/gmp-src/mpz/jacobi.c b/Build/source/libs/gmp/gmp-src/mpz/jacobi.c index 397fe11c9bb..cd556d78446 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/jacobi.c +++ b/Build/source/libs/gmp/gmp-src/mpz/jacobi.c @@ -29,7 +29,6 @@ GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ #include <stdio.h> -#include "gmp.h" #include "gmp-impl.h" #include "longlong.h" diff --git a/Build/source/libs/gmp/gmp-src/mpz/kronsz.c b/Build/source/libs/gmp/gmp-src/mpz/kronsz.c index 1fb6e075b63..92cc971fedb 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/kronsz.c +++ b/Build/source/libs/gmp/gmp-src/mpz/kronsz.c @@ -28,7 +28,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" #include "longlong.h" diff --git a/Build/source/libs/gmp/gmp-src/mpz/kronuz.c b/Build/source/libs/gmp/gmp-src/mpz/kronuz.c index ca88250de59..ba5c6dd3137 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/kronuz.c +++ b/Build/source/libs/gmp/gmp-src/mpz/kronuz.c @@ -28,7 +28,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" #include "longlong.h" diff --git a/Build/source/libs/gmp/gmp-src/mpz/kronzs.c b/Build/source/libs/gmp/gmp-src/mpz/kronzs.c index 695cd0f283e..1f63f15bd2c 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/kronzs.c +++ b/Build/source/libs/gmp/gmp-src/mpz/kronzs.c @@ -28,7 +28,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" #include "longlong.h" diff --git a/Build/source/libs/gmp/gmp-src/mpz/kronzu.c b/Build/source/libs/gmp/gmp-src/mpz/kronzu.c index f57f92e8ba1..b4fbf791d8f 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/kronzu.c +++ b/Build/source/libs/gmp/gmp-src/mpz/kronzu.c @@ -28,7 +28,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" #include "longlong.h" diff --git a/Build/source/libs/gmp/gmp-src/mpz/lcm.c b/Build/source/libs/gmp/gmp-src/mpz/lcm.c index 805f6710775..2807ef7eb6b 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/lcm.c +++ b/Build/source/libs/gmp/gmp-src/mpz/lcm.c @@ -28,7 +28,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" void diff --git a/Build/source/libs/gmp/gmp-src/mpz/lcm_ui.c b/Build/source/libs/gmp/gmp-src/mpz/lcm_ui.c index 362d183b428..1f199b71ac5 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/lcm_ui.c +++ b/Build/source/libs/gmp/gmp-src/mpz/lcm_ui.c @@ -28,7 +28,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" #include "longlong.h" diff --git a/Build/source/libs/gmp/gmp-src/mpz/limbs_finish.c b/Build/source/libs/gmp/gmp-src/mpz/limbs_finish.c index ebf6dea2907..a02839d5cec 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/limbs_finish.c +++ b/Build/source/libs/gmp/gmp-src/mpz/limbs_finish.c @@ -28,7 +28,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" void diff --git a/Build/source/libs/gmp/gmp-src/mpz/limbs_modify.c b/Build/source/libs/gmp/gmp-src/mpz/limbs_modify.c index bafd7d88a0e..a778b6e6c9f 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/limbs_modify.c +++ b/Build/source/libs/gmp/gmp-src/mpz/limbs_modify.c @@ -28,7 +28,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" mp_ptr diff --git a/Build/source/libs/gmp/gmp-src/mpz/limbs_read.c b/Build/source/libs/gmp/gmp-src/mpz/limbs_read.c index 6c14f18d459..705f0c1e187 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/limbs_read.c +++ b/Build/source/libs/gmp/gmp-src/mpz/limbs_read.c @@ -28,7 +28,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" mp_srcptr diff --git a/Build/source/libs/gmp/gmp-src/mpz/limbs_write.c b/Build/source/libs/gmp/gmp-src/mpz/limbs_write.c index 605cb5e3a36..b116ad05dd3 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/limbs_write.c +++ b/Build/source/libs/gmp/gmp-src/mpz/limbs_write.c @@ -28,7 +28,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" mp_ptr diff --git a/Build/source/libs/gmp/gmp-src/mpz/lucmod.c b/Build/source/libs/gmp/gmp-src/mpz/lucmod.c new file mode 100644 index 00000000000..0dad48cb09f --- /dev/null +++ b/Build/source/libs/gmp/gmp-src/mpz/lucmod.c @@ -0,0 +1,127 @@ +/* mpz_lucas_mod -- Helper function for the strong Lucas + primality test. + + THE FUNCTIONS IN THIS FILE ARE FOR INTERNAL USE ONLY. THEY'RE ALMOST + CERTAIN TO BE SUBJECT TO INCOMPATIBLE CHANGES OR DISAPPEAR COMPLETELY IN + FUTURE GNU MP RELEASES. + +Copyright 2018 Free Software Foundation, Inc. + +Contributed by Marco Bodrato. + +This file is part of the GNU MP Library. + +The GNU MP Library is free software; you can redistribute it and/or modify +it under the terms of either: + + * the GNU Lesser General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your + option) any later version. + +or + + * the GNU General Public License as published by the Free Software + Foundation; either version 2 of the License, or (at your option) any + later version. + +or both in parallel, as here. + +The GNU MP Library is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY +or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received copies of the GNU General Public License and the +GNU Lesser General Public License along with the GNU MP Library. If not, +see https://www.gnu.org/licenses/. */ + +#include "gmp-impl.h" + +/* Computes V_{k+1}, Q^{k+1} (mod n) for the Lucas' sequence */ +/* with P=1, Q=Q; k = n>>b0. */ +/* Requires n > 4; b0 > 0; -2*Q must not overflow a long. */ +/* If U_{k+1}==0 (mod n) or V_{k+1}==0 (mod n), it returns 1, */ +/* otherwise it returns 0 and sets V=V_{k+1} and Qk=Q^{k+1}. */ +/* V will never grow beyond SIZ(n), Qk not beyond 2*SIZ(n). */ +int +mpz_lucas_mod (mpz_ptr V, mpz_ptr Qk, long Q, + mp_bitcnt_t b0, mpz_srcptr n, mpz_ptr T1, mpz_ptr T2) +{ + mp_bitcnt_t bs; + int res; + + ASSERT (b0 > 0); + ASSERT (SIZ (n) > 1 || SIZ (n) > 0 && PTR (n) [0] > 4); + + mpz_set_ui (V, 1); /* U1 = 1 */ + bs = mpz_sizeinbase (n, 2) - 2; + if (UNLIKELY (bs < b0)) + { + /* n = 2^b0 - 1, should we use Lucas-Lehmer instead? */ + ASSERT (bs == b0 - 2); + mpz_set_si (Qk, Q); + return 0; + } + mpz_set_ui (Qk, 1); /* U2 = 1 */ + + do + { + /* We use the iteration suggested in "Elementary Number Theory" */ + /* by Peter Hackman (November 1, 2009), section "L.XVII Scalar */ + /* Formulas", from http://hackmat.se/kurser/TATM54/booktot.pdf */ + /* U_{2k} = 2*U_{k+1}*U_k - P*U_k^2 */ + /* U_{2k+1} = U_{k+1}^2 - Q*U_k^2 */ + /* U_{2k+2} = P*U_{k+1}^2 - 2*Q*U_{k+1}*U_k */ + /* We note that U_{2k+2} = P*U_{2k+1} - Q*U_{2k} */ + /* The formulas are specialized for P=1, and only squares: */ + /* U_{2k} = U_{k+1}^2 - |U_{k+1} - U_k|^2 */ + /* U_{2k+1} = U_{k+1}^2 - Q*U_k^2 */ + /* U_{2k+2} = U_{2k+1} - Q*U_{2k} */ + mpz_mul (T1, Qk, Qk); /* U_{k+1}^2 */ + mpz_sub (Qk, V, Qk); /* |U_{k+1} - U_k| */ + mpz_mul (T2, Qk, Qk); /* |U_{k+1} - U_k|^2 */ + mpz_mul (Qk, V, V); /* U_k^2 */ + mpz_sub (T2, T1, T2); /* U_{k+1}^2 - (U_{k+1} - U_k)^2 */ + if (Q > 0) /* U_{k+1}^2 - Q U_k^2 = U_{2k+1} */ + mpz_submul_ui (T1, Qk, Q); + else + mpz_addmul_ui (T1, Qk, NEG_CAST (unsigned long, Q)); + + /* A step k->k+1 is performed if the bit in $n$ is 1 */ + if (mpz_tstbit (n, bs)) + { + /* U_{2k+2} = U_{2k+1} - Q*U_{2k} */ + mpz_mul_si (T2, T2, Q); + mpz_sub (T2, T1, T2); + mpz_swap (T1, T2); + } + mpz_tdiv_r (Qk, T1, n); + mpz_tdiv_r (V, T2, n); + } while (--bs >= b0); + + res = SIZ (Qk) == 0; + if (!res) { + mpz_mul_si (T1, V, -2*Q); + mpz_add (T1, Qk, T1); /* V_k = U_k - 2Q*U_{k-1} */ + mpz_tdiv_r (V, T1, n); + res = SIZ (V) == 0; + if (!res && b0 > 1) { + /* V_k and Q^k will be needed for further check, compute them. */ + /* FIXME: Here we compute V_k^2 and store V_k, but the former */ + /* will be recomputed by the calling function, shoul we store */ + /* that instead? */ + mpz_mul (T2, T1, T1); /* V_k^2 */ + mpz_mul (T1, Qk, Qk); /* P^2 U_k^2 = U_k^2 */ + mpz_sub (T2, T2, T1); + ASSERT (SIZ (T2) == 0 || PTR (T2) [0] % 4 == 0); + mpz_tdiv_q_2exp (T2, T2, 2); /* (V_k^2 - P^2 U_k^2) / 4 */ + if (Q > 0) /* (V_k^2 - (P^2 -4Q) U_k^2) / 4 = Q^k */ + mpz_addmul_ui (T2, T1, Q); + else + mpz_submul_ui (T2, T1, NEG_CAST (unsigned long, Q)); + mpz_tdiv_r (Qk, T2, n); + } + } + + return res; +} diff --git a/Build/source/libs/gmp/gmp-src/mpz/lucnum2_ui.c b/Build/source/libs/gmp/gmp-src/mpz/lucnum2_ui.c index f8e4fb356f0..3cc3d7b758d 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/lucnum2_ui.c +++ b/Build/source/libs/gmp/gmp-src/mpz/lucnum2_ui.c @@ -1,6 +1,7 @@ /* mpz_lucnum2_ui -- calculate Lucas numbers. -Copyright 2001, 2003, 2005, 2012 Free Software Foundation, Inc. +Copyright 2001, 2003, 2005, 2012, 2015, 2016, 2018 Free Software +Foundation, Inc. This file is part of the GNU MP Library. @@ -29,7 +30,6 @@ GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ #include <stdio.h> -#include "gmp.h" #include "gmp-impl.h" @@ -50,11 +50,11 @@ mpz_lucnum2_ui (mpz_ptr ln, mpz_ptr lnsub1, unsigned long n) mp_limb_t f1 = FIB_TABLE ((int) n - 1); /* L[n] = F[n] + 2F[n-1] */ - PTR(ln)[0] = f + 2*f1; + MPZ_NEWALLOC (ln, 1)[0] = f + 2*f1; SIZ(ln) = 1; /* L[n-1] = 2F[n] - F[n-1], but allow for L[-1]=-1 */ - PTR(lnsub1)[0] = (n == 0 ? 1 : 2*f - f1); + MPZ_NEWALLOC (lnsub1, 1)[0] = (n == 0 ? 1 : 2*f - f1); SIZ(lnsub1) = (n == 0 ? -1 : 1); return; @@ -64,8 +64,8 @@ mpz_lucnum2_ui (mpz_ptr ln, mpz_ptr lnsub1, unsigned long n) size = MPN_FIB2_SIZE (n); f1p = TMP_ALLOC_LIMBS (size); - lp = MPZ_REALLOC (ln, size+1); - l1p = MPZ_REALLOC (lnsub1, size+1); + lp = MPZ_NEWALLOC (ln, size+1); + l1p = MPZ_NEWALLOC (lnsub1, size+1); size = mpn_fib2_ui (l1p, f1p, n); @@ -80,8 +80,12 @@ mpz_lucnum2_ui (mpz_ptr ln, mpz_ptr lnsub1, unsigned long n) SIZ(ln) = size + (c != 0); /* L[n-1] = 2F[n] - F[n-1] */ +#if HAVE_NATIVE_mpn_rsblsh1_n + c = mpn_rsblsh1_n (l1p, f1p, l1p, size); +#else c = mpn_lshift (l1p, l1p, size, 1); c -= mpn_sub_n (l1p, l1p, f1p, size); +#endif ASSERT ((mp_limb_signed_t) c >= 0); l1p[size] = c; SIZ(lnsub1) = size + (c != 0); diff --git a/Build/source/libs/gmp/gmp-src/mpz/lucnum_ui.c b/Build/source/libs/gmp/gmp-src/mpz/lucnum_ui.c index d1fe6b54cef..4213bb790c9 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/lucnum_ui.c +++ b/Build/source/libs/gmp/gmp-src/mpz/lucnum_ui.c @@ -1,6 +1,6 @@ /* mpz_lucnum_ui -- calculate Lucas number. -Copyright 2001, 2003, 2005, 2011, 2012 Free Software Foundation, Inc. +Copyright 2001, 2003, 2005, 2011, 2012, 2015, 2016 Free Software Foundation, Inc. This file is part of the GNU MP Library. @@ -29,7 +29,6 @@ GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ #include <stdio.h> -#include "gmp.h" #include "gmp-impl.h" @@ -68,7 +67,7 @@ mpz_lucnum_ui (mpz_ptr ln, unsigned long n) if (n <= FIB_TABLE_LUCNUM_LIMIT) { /* L[n] = F[n] + 2F[n-1] */ - PTR(ln)[0] = FIB_TABLE(n) + 2 * FIB_TABLE ((int) n - 1); + MPZ_NEWALLOC (ln, 1)[0] = FIB_TABLE(n) + 2 * FIB_TABLE ((int) n - 1); SIZ(ln) = 1; return; } @@ -77,7 +76,7 @@ mpz_lucnum_ui (mpz_ptr ln, unsigned long n) since square or mul used below might need an extra limb over the true size */ lalloc = MPN_FIB2_SIZE (n) + 2; - lp = MPZ_REALLOC (ln, lalloc); + lp = MPZ_NEWALLOC (ln, lalloc); TMP_MARK; xalloc = lalloc; diff --git a/Build/source/libs/gmp/gmp-src/mpz/mfac_uiui.c b/Build/source/libs/gmp/gmp-src/mpz/mfac_uiui.c index 3ea36bce9d2..8595a9bc3b6 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/mfac_uiui.c +++ b/Build/source/libs/gmp/gmp-src/mpz/mfac_uiui.c @@ -2,7 +2,7 @@ Contributed to the GNU project by Marco Bodrato. -Copyright 2012, 2013 Free Software Foundation, Inc. +Copyright 2012, 2013, 2015, 2016 Free Software Foundation, Inc. This file is part of the GNU MP Library. @@ -30,7 +30,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" /*************************************************************/ @@ -59,9 +58,9 @@ mpz_mfac_uiui (mpz_ptr x, unsigned long n, unsigned long m) ASSERT (m != 0); if ((n < 3) | (n - 3 < m - 1)) { /* (n < 3 || n - 1 <= m || m == 0) */ - PTR (x)[0] = n + (n == 0); + MPZ_NEWALLOC (x, 1)[0] = n + (n == 0); SIZ (x) = 1; - } else { /* m < n - 1 < GMP_NUMB_MAX */ + } else { /* 0 < m < n - 1 < GMP_NUMB_MAX */ mp_limb_t g, sn; mpz_t t; @@ -94,7 +93,8 @@ mpz_mfac_uiui (mpz_ptr x, unsigned long n, unsigned long m) } } else { /* m >= 3, gcd(n,m) = 1 */ mp_limb_t *factors; - mp_limb_t prod, max_prod, j; + mp_limb_t prod, max_prod; + mp_size_t j; TMP_DECL; sn = n / m + 1; diff --git a/Build/source/libs/gmp/gmp-src/mpz/millerrabin.c b/Build/source/libs/gmp/gmp-src/mpz/millerrabin.c index 1dab971c1ab..1f5d482605b 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/millerrabin.c +++ b/Build/source/libs/gmp/gmp-src/mpz/millerrabin.c @@ -5,12 +5,22 @@ reps is the number of internal passes of the probabilistic algorithm. Knuth indicates that 25 passes are reasonable. + With the current implementation, the first 24 MR-tests are substituted by a + Baillie-PSW probable prime test. + + This implementation the Baillie-PSW test was checked up to 19*2^46, + for smaller values no MR-test is performed, regardless of reps, and + 2 ("surely prime") is returned if the number was not proved composite. + + If GMP_BPSW_NOFALSEPOSITIVES_UPTO_64BITS is defined as non-zero, + the code assumes that the Baillie-PSW test was checked up to 2^64. + THE FUNCTIONS IN THIS FILE ARE FOR INTERNAL USE ONLY. THEY'RE ALMOST CERTAIN TO BE SUBJECT TO INCOMPATIBLE CHANGES OR DISAPPEAR COMPLETELY IN FUTURE GNU MP RELEASES. -Copyright 1991, 1993, 1994, 1996-2002, 2005, 2014 Free Software -Foundation, Inc. +Copyright 1991, 1993, 1994, 1996-2002, 2005, 2014, 2018, 2019 Free +Software Foundation, Inc. Contributed by John Amanatides. @@ -40,83 +50,167 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" -static int millerrabin (mpz_srcptr, mpz_srcptr, +#ifndef GMP_BPSW_NOFALSEPOSITIVES_UPTO_64BITS +#define GMP_BPSW_NOFALSEPOSITIVES_UPTO_64BITS 0 +#endif + +static int millerrabin (mpz_srcptr, mpz_ptr, mpz_ptr, mpz_srcptr, unsigned long int); int mpz_millerrabin (mpz_srcptr n, int reps) { - int r; - mpz_t nm1, nm3, x, y, q; + mpz_t nm, x, y, q; unsigned long int k; gmp_randstate_t rstate; int is_prime; TMP_DECL; TMP_MARK; - MPZ_TMP_INIT (nm1, SIZ (n) + 1); - mpz_sub_ui (nm1, n, 1L); + ASSERT (SIZ (n) > 0); + MPZ_TMP_INIT (nm, SIZ (n) + 1); + mpz_tdiv_q_2exp (nm, n, 1); MPZ_TMP_INIT (x, SIZ (n) + 1); MPZ_TMP_INIT (y, 2 * SIZ (n)); /* mpz_powm_ui needs excessive memory!!! */ + MPZ_TMP_INIT (q, SIZ (n)); - /* Perform a Fermat test. */ - mpz_set_ui (x, 210L); - mpz_powm (y, x, nm1, n); - if (mpz_cmp_ui (y, 1L) != 0) + /* Find q and k, where q is odd and n = 1 + 2**k * q. */ + k = mpz_scan1 (nm, 0L); + mpz_tdiv_q_2exp (q, nm, k); + ++k; + + /* BPSW test */ + mpz_set_ui (x, 2); + is_prime = millerrabin (n, x, y, q, k) && mpz_stronglucas (n, x, y); + + if (is_prime) { - TMP_FREE; - return 0; + if ( +#if GMP_BPSW_NOFALSEPOSITIVES_UPTO_64BITS + /* Consider numbers up to 2^64 that pass the BPSW test as primes. */ +#if GMP_NUMB_BITS <= 64 + SIZ (n) <= 64 / GMP_NUMB_BITS +#else + 0 +#endif +#if 64 % GMP_NUMB_BITS != 0 + || SIZ (n) - 64 / GMP_NUMB_BITS == (PTR (n) [64 / GMP_NUMB_BITS] < CNST_LIMB(1) << 64 % GMP_NUMB_BITS) +#endif +#else + /* Consider numbers up to 19*2^46 that pass the BPSW test as primes. + This implementation was tested up to 19*2^46 = 2^50+2^47+2^46 */ + /* 2^4 < 19 = 0b10011 < 2^5 */ +#define GMP_BPSW_LIMB_CONST CNST_LIMB(19) +#define GMP_BPSW_BITS_CONST (LOG2C(19) - 1) +#define GMP_BPSW_BITS_LIMIT (46 + GMP_BPSW_BITS_CONST) + +#define GMP_BPSW_LIMBS_LIMIT (GMP_BPSW_BITS_LIMIT / GMP_NUMB_BITS) +#define GMP_BPSW_BITS_MOD (GMP_BPSW_BITS_LIMIT % GMP_NUMB_BITS) + +#if GMP_NUMB_BITS <= GMP_BPSW_BITS_LIMIT + SIZ (n) <= GMP_BPSW_LIMBS_LIMIT +#else + 0 +#endif +#if GMP_BPSW_BITS_MOD >= GMP_BPSW_BITS_CONST + || SIZ (n) - GMP_BPSW_LIMBS_LIMIT == (PTR (n) [GMP_BPSW_LIMBS_LIMIT] < GMP_BPSW_LIMB_CONST << (GMP_BPSW_BITS_MOD - GMP_BPSW_BITS_CONST)) +#else +#if GMP_BPSW_BITS_MOD != 0 + || SIZ (n) - GMP_BPSW_LIMBS_LIMIT == (PTR (n) [GMP_BPSW_LIMBS_LIMIT] < GMP_BPSW_LIMB_CONST >> (GMP_BPSW_BITS_CONST - GMP_BPSW_BITS_MOD)) +#else +#if GMP_NUMB_BITS > GMP_BPSW_BITS_CONST + || SIZ (nm) - GMP_BPSW_LIMBS_LIMIT + 1 == (PTR (nm) [GMP_BPSW_LIMBS_LIMIT - 1] < GMP_BPSW_LIMB_CONST << (GMP_NUMB_BITS - 1 - GMP_BPSW_BITS_CONST)) +#endif +#endif +#endif + +#undef GMP_BPSW_BITS_LIMIT +#undef GMP_BPSW_LIMB_CONST +#undef GMP_BPSW_BITS_CONST +#undef GMP_BPSW_LIMBS_LIMIT +#undef GMP_BPSW_BITS_MOD + +#endif + ) + is_prime = 2; + else + { + reps -= 24; + if (reps > 0) + { + /* (n-5)/2 */ + mpz_sub_ui (nm, nm, 2L); + ASSERT (mpz_cmp_ui (nm, 1L) >= 0); + + gmp_randinit_default (rstate); + + do + { + /* 3 to (n-1)/2 inclusive, don't want 1, 0 or 2 */ + mpz_urandomm (x, rstate, nm); + mpz_add_ui (x, x, 3L); + + is_prime = millerrabin (n, x, y, q, k); + } while (--reps > 0 && is_prime); + + gmp_randclear (rstate); + } + } } + TMP_FREE; + return is_prime; +} - MPZ_TMP_INIT (q, SIZ (n)); - - /* Find q and k, where q is odd and n = 1 + 2**k * q. */ - k = mpz_scan1 (nm1, 0L); - mpz_tdiv_q_2exp (q, nm1, k); +static int +mod_eq_m1 (mpz_srcptr x, mpz_srcptr m) +{ + mp_size_t ms; + mp_srcptr mp, xp; - /* n-3 */ - MPZ_TMP_INIT (nm3, SIZ (n) + 1); - mpz_sub_ui (nm3, n, 3L); - ASSERT (mpz_cmp_ui (nm3, 1L) >= 0); + ms = SIZ (m); + if (SIZ (x) != ms) + return 0; + ASSERT (ms > 0); - gmp_randinit_default (rstate); + mp = PTR (m); + xp = PTR (x); + ASSERT ((mp[0] - 1) == (mp[0] ^ 1)); /* n is odd */ - is_prime = 1; - for (r = 0; r < reps && is_prime; r++) + if ((*xp ^ CNST_LIMB(1) ^ *mp) != CNST_LIMB(0)) /* xp[0] != mp[0] - 1 */ + return 0; + else { - /* 2 to n-2 inclusive, don't want 1, 0 or -1 */ - mpz_urandomm (x, rstate, nm3); - mpz_add_ui (x, x, 2L); + int cmp; - is_prime = millerrabin (n, nm1, x, y, q, k); - } + --ms; + ++xp; + ++mp; - gmp_randclear (rstate); + MPN_CMP (cmp, xp, mp, ms); - TMP_FREE; - return is_prime; + return cmp == 0; + } } static int -millerrabin (mpz_srcptr n, mpz_srcptr nm1, mpz_ptr x, mpz_ptr y, +millerrabin (mpz_srcptr n, mpz_ptr x, mpz_ptr y, mpz_srcptr q, unsigned long int k) { unsigned long int i; mpz_powm (y, x, q, n); - if (mpz_cmp_ui (y, 1L) == 0 || mpz_cmp (y, nm1) == 0) + if (mpz_cmp_ui (y, 1L) == 0 || mod_eq_m1 (y, n)) return 1; for (i = 1; i < k; i++) { mpz_powm_ui (y, y, 2L, n); - if (mpz_cmp (y, nm1) == 0) + if (mod_eq_m1 (y, n)) return 1; /* y == 1 means that the previous y was a non-trivial square root of 1 (mod n). y == 0 means that n is a power of the base. diff --git a/Build/source/libs/gmp/gmp-src/mpz/mod.c b/Build/source/libs/gmp/gmp-src/mpz/mod.c index f2de0f97831..ab5cdb16df5 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/mod.c +++ b/Build/source/libs/gmp/gmp-src/mpz/mod.c @@ -29,7 +29,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" void diff --git a/Build/source/libs/gmp/gmp-src/mpz/mul.c b/Build/source/libs/gmp/gmp-src/mpz/mul.c index c4389158e29..d72c93e177d 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/mul.c +++ b/Build/source/libs/gmp/gmp-src/mpz/mul.c @@ -1,7 +1,7 @@ /* mpz_mul -- Multiply two integers. -Copyright 1991, 1993, 1994, 1996, 2000, 2001, 2005, 2009, 2011, 2012 Free -Software Foundation, Inc. +Copyright 1991, 1993, 1994, 1996, 2000, 2001, 2005, 2009, 2011, 2012, +2015 Free Software Foundation, Inc. This file is part of the GNU MP Library. @@ -30,7 +30,6 @@ GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ #include <stdio.h> /* for NULL */ -#include "gmp.h" #include "gmp-impl.h" @@ -104,13 +103,14 @@ mpz_mul (mpz_ptr w, mpz_srcptr u, mpz_srcptr v) wsize = usize + vsize; if (ALLOC (w) < wsize) { - if (wp == up || wp == vp) - { - free_me = wp; - free_me_size = ALLOC (w); - } - else - (*__gmp_free_func) (wp, (size_t) ALLOC (w) * GMP_LIMB_BYTES); + if (ALLOC (w) != 0) + if (wp == up || wp == vp) + { + free_me = wp; + free_me_size = ALLOC (w); + } + else + (*__gmp_free_func) (wp, (size_t) ALLOC (w) * GMP_LIMB_BYTES); ALLOC (w) = wsize; wp = __GMP_ALLOCATE_FUNC_LIMBS (wsize); diff --git a/Build/source/libs/gmp/gmp-src/mpz/mul_2exp.c b/Build/source/libs/gmp/gmp-src/mpz/mul_2exp.c index f02fef7ee23..6144d0d19d1 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/mul_2exp.c +++ b/Build/source/libs/gmp/gmp-src/mpz/mul_2exp.c @@ -29,7 +29,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" void diff --git a/Build/source/libs/gmp/gmp-src/mpz/mul_i.h b/Build/source/libs/gmp/gmp-src/mpz/mul_i.h index 486a8fd63e6..65c9c2ffc3d 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/mul_i.h +++ b/Build/source/libs/gmp/gmp-src/mpz/mul_i.h @@ -30,7 +30,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" @@ -97,7 +96,7 @@ FUNCTION (mpz_ptr prod, mpz_srcptr mult, tp[size + 1] = cy; size += 2; MPN_NORMALIZE_NOT_ZERO (tp, size); /* too general, need to trim one or two limb */ - pp = MPZ_REALLOC (prod, size); + pp = MPZ_NEWALLOC (prod, size); MPN_COPY (pp, tp, size); TMP_FREE; } diff --git a/Build/source/libs/gmp/gmp-src/mpz/n_pow_ui.c b/Build/source/libs/gmp/gmp-src/mpz/n_pow_ui.c index 6c3febe2375..cf293f5405f 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/n_pow_ui.c +++ b/Build/source/libs/gmp/gmp-src/mpz/n_pow_ui.c @@ -4,7 +4,7 @@ CERTAIN TO BE SUBJECT TO INCOMPATIBLE CHANGES OR DISAPPEAR COMPLETELY IN FUTURE GNU MP RELEASES. -Copyright 2001, 2002, 2005, 2012 Free Software Foundation, Inc. +Copyright 2001, 2002, 2005, 2012, 2015 Free Software Foundation, Inc. This file is part of the GNU MP Library. @@ -32,7 +32,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" #include "longlong.h" @@ -183,7 +182,7 @@ mpz_n_pow_ui (mpz_ptr r, mp_srcptr bp, mp_size_t bsize, unsigned long int e) /* b^0 == 1, including 0^0 == 1 */ if (e == 0) { - PTR(r)[0] = 1; + MPZ_NEWALLOC (r, 1)[0] = 1; SIZ(r) = 1; return; } @@ -372,7 +371,7 @@ mpz_n_pow_ui (mpz_ptr r, mp_srcptr bp, mp_size_t bsize, unsigned long int e) ralloc = (bsize*GMP_NUMB_BITS - cnt + GMP_NAIL_BITS) * e / GMP_NUMB_BITS + 5; TRACE (printf ("ralloc %ld, from bsize=%ld blimb=0x%lX cnt=%d\n", ralloc, bsize, blimb, cnt)); - rp = MPZ_REALLOC (r, ralloc + rtwos_limbs); + rp = MPZ_NEWALLOC (r, ralloc + rtwos_limbs); /* Low zero limbs resulting from powers of 2. */ MPN_ZERO (rp, rtwos_limbs); diff --git a/Build/source/libs/gmp/gmp-src/mpz/neg.c b/Build/source/libs/gmp/gmp-src/mpz/neg.c index eb46ab7f785..7f3fbcfa271 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/neg.c +++ b/Build/source/libs/gmp/gmp-src/mpz/neg.c @@ -30,7 +30,6 @@ see https://www.gnu.org/licenses/. */ #define __GMP_FORCE_mpz_neg 1 -#include "gmp.h" #include "gmp-impl.h" void diff --git a/Build/source/libs/gmp/gmp-src/mpz/nextprime.c b/Build/source/libs/gmp/gmp-src/mpz/nextprime.c index 1493054695c..1a0b5b6b0b4 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/nextprime.c +++ b/Build/source/libs/gmp/gmp-src/mpz/nextprime.c @@ -30,7 +30,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" #include "longlong.h" @@ -81,7 +80,7 @@ mpz_nextprime (mpz_ptr p, mpz_srcptr n) TMP_SMARK; /* Compute residues modulo small odd primes */ - moduli = TMP_SALLOC_TYPE (prime_limit * sizeof moduli[0], unsigned short); + moduli = TMP_SALLOC_TYPE (prime_limit, unsigned short); for (;;) { @@ -89,7 +88,7 @@ mpz_nextprime (mpz_ptr p, mpz_srcptr n) prime = 3; for (i = 0; i < prime_limit; i++) { - moduli[i] = mpz_fdiv_ui (p, prime); + moduli[i] = mpz_tdiv_ui (p, prime); prime += primegap[i]; } diff --git a/Build/source/libs/gmp/gmp-src/mpz/oddfac_1.c b/Build/source/libs/gmp/gmp-src/mpz/oddfac_1.c index cf0bff06505..9c99d1e494d 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/oddfac_1.c +++ b/Build/source/libs/gmp/gmp-src/mpz/oddfac_1.c @@ -7,7 +7,7 @@ IT IS ONLY SAFE TO REACH IT THROUGH DOCUMENTED INTERFACES. IN FACT, IT IS ALMOST GUARANTEED THAT IT WILL CHANGE OR DISAPPEAR IN A FUTURE GNU MP RELEASE. -Copyright 2010-2012 Free Software Foundation, Inc. +Copyright 2010-2012, 2015-2017 Free Software Foundation, Inc. This file is part of the GNU MP Library. @@ -35,7 +35,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" #include "longlong.h" @@ -69,7 +68,8 @@ see https://www.gnu.org/licenses/. */ ++__i; \ if (((sieve)[__index] & __mask) == 0) \ { \ - (prime) = id_to_n(__i) + mp_limb_t prime; \ + prime = id_to_n(__i) #define LOOP_ON_SIEVE_BEGIN(prime,start,end,off,sieve) \ do { \ @@ -86,7 +86,7 @@ see https://www.gnu.org/licenses/. */ } \ __mask = __mask << 1 | __mask >> (GMP_LIMB_BITS-1); \ __index += __mask & 1; \ - } while (__i <= __max_i) \ + } while (__i <= __max_i) #define LOOP_ON_SIEVE_END \ LOOP_ON_SIEVE_STOP; \ @@ -115,20 +115,24 @@ primesieve_size (mp_limb_t n) { return n_to_bit(n) / GMP_LIMB_BITS + 1; } #endif /*********************************************************/ -/* Section mswing: 2-multiswing factorial */ +/* Section mswing: 2-multiswing factorial */ /*********************************************************/ -/* Returns an approximation of the sqare root of x. * - * It gives: x <= limb_apprsqrt (x) ^ 2 < x * 9/4 */ +/* Returns an approximation of the sqare root of x. + * It gives: + * limb_apprsqrt (x) ^ 2 <= x < (limb_apprsqrt (x)+1) ^ 2 + * or + * x <= limb_apprsqrt (x) ^ 2 <= x * 9/8 + */ static mp_limb_t limb_apprsqrt (mp_limb_t x) { int s; ASSERT (x > 2); - count_leading_zeros (s, x - 1); - s = GMP_LIMB_BITS - 1 - s; - return (CNST_LIMB(1) << (s >> 1)) + (CNST_LIMB(1) << ((s - 1) >> 1)); + count_leading_zeros (s, x); + s = (GMP_LIMB_BITS - s) >> 1; + return ((CNST_LIMB(1) << s) + (x >> s)) >> 1; } #if 0 @@ -189,7 +193,7 @@ mpz_2multiswing_1 (mpz_ptr x, mp_limb_t n, mp_ptr sieve, mp_ptr factors) mp_limb_t prod, max_prod; mp_size_t j; - ASSERT (n >= 26); + ASSERT (n > 25); j = 0; prod = -(n & 1); @@ -203,41 +207,31 @@ mpz_2multiswing_1 (mpz_ptr x, mp_limb_t n, mp_ptr sieve, mp_ptr factors) /* Swing primes from 5 to n/3 */ { - mp_limb_t s; + mp_limb_t s, l_max_prod; - { - mp_limb_t prime; - - s = limb_apprsqrt(n); - ASSERT (s >= 5); - s = n_to_bit (s); - LOOP_ON_SIEVE_BEGIN (prime, n_to_bit (5), s, 0,sieve); - SWING_A_PRIME (prime, n, prod, max_prod, factors, j); - LOOP_ON_SIEVE_END; - s++; - } + s = limb_apprsqrt(n); + ASSERT (s >= 5); + s = n_to_bit (s); + ASSERT (bit_to_n (s+1) * bit_to_n (s+1) > n); + ASSERT (s < n_to_bit (n / 3)); + LOOP_ON_SIEVE_BEGIN (prime, n_to_bit (5), s, 0,sieve); + SWING_A_PRIME (prime, n, prod, max_prod, factors, j); + LOOP_ON_SIEVE_STOP; ASSERT (max_prod <= GMP_NUMB_MAX / 3); - ASSERT (bit_to_n (s) * bit_to_n (s) > n); - ASSERT (s <= n_to_bit (n / 3)); - { - mp_limb_t prime; - mp_limb_t l_max_prod = max_prod * 3; - LOOP_ON_SIEVE_BEGIN (prime, s, n_to_bit (n/3), 0, sieve); - SH_SWING_A_PRIME (prime, n, prod, l_max_prod, factors, j); - LOOP_ON_SIEVE_END; - } - } + l_max_prod = max_prod * 3; - /* Store primes from (n+1)/2 to n */ - { - mp_limb_t prime; - LOOP_ON_SIEVE_BEGIN (prime, n_to_bit (n >> 1) + 1, n_to_bit (n), 0,sieve); - FACTOR_LIST_STORE (prime, prod, max_prod, factors, j); + LOOP_ON_SIEVE_CONTINUE (prime, n_to_bit (n/3), sieve); + SH_SWING_A_PRIME (prime, n, prod, l_max_prod, factors, j); LOOP_ON_SIEVE_END; } + /* Store primes from (n+1)/2 to n */ + LOOP_ON_SIEVE_BEGIN (prime, n_to_bit (n >> 1) + 1, n_to_bit (n), 0,sieve); + FACTOR_LIST_STORE (prime, prod, max_prod, factors, j); + LOOP_ON_SIEVE_END; + if (LIKELY (j != 0)) { factors[j++] = prod; @@ -245,6 +239,7 @@ mpz_2multiswing_1 (mpz_ptr x, mp_limb_t n, mp_ptr sieve, mp_ptr factors) } else { + ASSERT (ALLOC (x) > 0); PTR (x)[0] = prod; SIZ (x) = 1; } @@ -286,11 +281,11 @@ void mpz_oddfac_1 (mpz_ptr x, mp_limb_t n, unsigned flag) { ASSERT (n <= GMP_NUMB_MAX); - ASSERT (flag == 0 || (flag == 1 && n > ODD_FACTORIAL_TABLE_LIMIT && ABOVE_THRESHOLD (n, FAC_DSC_THRESHOLD))); + ASSERT (flag == 0 || (flag == 1 && n > ODD_DOUBLEFACTORIAL_TABLE_LIMIT + 1 && ABOVE_THRESHOLD (n, FAC_DSC_THRESHOLD))); if (n <= ODD_FACTORIAL_TABLE_LIMIT) { - PTR (x)[0] = __gmp_oddfac_table[n]; + MPZ_NEWALLOC (x, 1)[0] = __gmp_oddfac_table[n]; SIZ (x) = 1; } else if (n <= ODD_DOUBLEFACTORIAL_TABLE_LIMIT + 1) @@ -415,8 +410,8 @@ mpz_oddfac_1 (mpz_ptr x, mp_limb_t n, unsigned flag) ASSERT (ns <= size); cy = mpn_mul (px, square, size, PTR(mswing), ns); /* n!= n$ * floor(n/2)!^2 */ - TMP_FREE; SIZ(x) = nx - (cy == 0); + TMP_FREE; } while (s != 0); TMP_FREE; } diff --git a/Build/source/libs/gmp/gmp-src/mpz/out_raw.c b/Build/source/libs/gmp/gmp-src/mpz/out_raw.c index 3b6b0b7cb5d..b9fd086d20e 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/out_raw.c +++ b/Build/source/libs/gmp/gmp-src/mpz/out_raw.c @@ -29,7 +29,6 @@ GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ #include <stdio.h> -#include "gmp.h" #include "gmp-impl.h" #include "longlong.h" diff --git a/Build/source/libs/gmp/gmp-src/mpz/out_str.c b/Build/source/libs/gmp/gmp-src/mpz/out_str.c index 6c97039c64b..b1d8ae86b77 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/out_str.c +++ b/Build/source/libs/gmp/gmp-src/mpz/out_str.c @@ -1,8 +1,8 @@ /* mpz_out_str(stream, base, integer) -- Output to STREAM the multi prec. integer INTEGER in base BASE. -Copyright 1991, 1993, 1994, 1996, 2001, 2005, 2011, 2012 Free Software -Foundation, Inc. +Copyright 1991, 1993, 1994, 1996, 2001, 2005, 2011, 2012, 2017 Free +Software Foundation, Inc. This file is part of the GNU MP Library. @@ -31,7 +31,6 @@ GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ #include <stdio.h> -#include "gmp.h" #include "gmp-impl.h" #include "longlong.h" @@ -50,26 +49,23 @@ mpz_out_str (FILE *stream, int base, mpz_srcptr x) if (stream == 0) stream = stdout; - if (base >= 0) + num_to_text = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"; + if (base > 1) { - num_to_text = "0123456789abcdefghijklmnopqrstuvwxyz"; - if (base <= 1) - base = 10; - else if (base > 36) - { - num_to_text = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"; - if (base > 62) + if (base <= 36) + num_to_text = "0123456789abcdefghijklmnopqrstuvwxyz"; + else if (UNLIKELY (base > 62)) return 0; - } + } + else if (base > -2) + { + base = 10; } else { base = -base; - if (base <= 1) - base = 10; - else if (base > 36) + if (UNLIKELY (base > 36)) return 0; - num_to_text = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"; } written = 0; diff --git a/Build/source/libs/gmp/gmp-src/mpz/perfpow.c b/Build/source/libs/gmp/gmp-src/mpz/perfpow.c index 72ff3c89ac4..9bbb497b119 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/perfpow.c +++ b/Build/source/libs/gmp/gmp-src/mpz/perfpow.c @@ -29,7 +29,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" int diff --git a/Build/source/libs/gmp/gmp-src/mpz/perfsqr.c b/Build/source/libs/gmp/gmp-src/mpz/perfsqr.c index 534f10ff563..c2ac924a870 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/perfsqr.c +++ b/Build/source/libs/gmp/gmp-src/mpz/perfsqr.c @@ -31,5 +31,4 @@ see https://www.gnu.org/licenses/. */ #define __GMP_FORCE_mpz_perfect_square_p 1 -#include "gmp.h" #include "gmp-impl.h" diff --git a/Build/source/libs/gmp/gmp-src/mpz/popcount.c b/Build/source/libs/gmp/gmp-src/mpz/popcount.c index 06f0f0b3a26..e9a85bbd981 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/popcount.c +++ b/Build/source/libs/gmp/gmp-src/mpz/popcount.c @@ -31,5 +31,4 @@ see https://www.gnu.org/licenses/. */ #define __GMP_FORCE_mpz_popcount 1 -#include "gmp.h" #include "gmp-impl.h" diff --git a/Build/source/libs/gmp/gmp-src/mpz/pow_ui.c b/Build/source/libs/gmp/gmp-src/mpz/pow_ui.c index 4891e978774..8bafaa73b05 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/pow_ui.c +++ b/Build/source/libs/gmp/gmp-src/mpz/pow_ui.c @@ -28,7 +28,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" void diff --git a/Build/source/libs/gmp/gmp-src/mpz/powm.c b/Build/source/libs/gmp/gmp-src/mpz/powm.c index 4d13da7396f..f1bf8e36472 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/powm.c +++ b/Build/source/libs/gmp/gmp-src/mpz/powm.c @@ -2,8 +2,8 @@ Contributed to the GNU project by Torbjorn Granlund. -Copyright 1991, 1993, 1994, 1996, 1997, 2000-2002, 2005, 2008, 2009, 2011, 2012 -Free Software Foundation, Inc. +Copyright 1991, 1993, 1994, 1996, 1997, 2000-2002, 2005, 2008, 2009, +2011, 2012, 2015, 2019 Free Software Foundation, Inc. This file is part of the GNU MP Library. @@ -32,7 +32,6 @@ GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" #include "longlong.h" @@ -86,7 +85,7 @@ mpz_powm (mpz_ptr r, mpz_srcptr b, mpz_srcptr e, mpz_srcptr m) /* b^0 mod m, b is anything and m is non-zero. Result is 1 mod m, i.e., 1 or 0 depending on if m = 1. */ SIZ(r) = n != 1 || mp[0] != 1; - PTR(r)[0] = 1; + MPZ_NEWALLOC (r, 1)[0] = 1; TMP_FREE; /* we haven't really allocated anything here */ return; } @@ -126,11 +125,11 @@ mpz_powm (mpz_ptr r, mpz_srcptr b, mpz_srcptr e, mpz_srcptr m) rn = n; MPN_NORMALIZE (rp, rn); - if (SIZ(b) < 0 && rn != 0) + if (rn != 0 && SIZ(b) < 0) { mpn_sub (rp, mp, n, rp, rn); rn = n; - MPN_NORMALIZE (rp, rn); + MPN_NORMALIZE_NOT_ZERO (rp, rn); } } else @@ -139,7 +138,7 @@ mpz_powm (mpz_ptr r, mpz_srcptr b, mpz_srcptr e, mpz_srcptr m) { mpn_sub (rp, mp, n, bp, bn); rn = n; - rn -= (rp[rn - 1] == 0); + MPN_NORMALIZE_NOT_ZERO (rp, rn); } else { @@ -275,7 +274,7 @@ mpz_powm (mpz_ptr r, mpz_srcptr b, mpz_srcptr e, mpz_srcptr m) } ret: - MPZ_REALLOC (r, rn); + MPZ_NEWALLOC (r, rn); SIZ(r) = rn; MPN_COPY (PTR(r), rp, rn); diff --git a/Build/source/libs/gmp/gmp-src/mpz/powm_sec.c b/Build/source/libs/gmp/gmp-src/mpz/powm_sec.c index 98644ca4963..a2581a8a48b 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/powm_sec.c +++ b/Build/source/libs/gmp/gmp-src/mpz/powm_sec.c @@ -2,8 +2,8 @@ Contributed to the GNU project by Torbjorn Granlund. -Copyright 1991, 1993, 1994, 1996, 1997, 2000-2002, 2005, 2008, 2009, 2012 Free -Software Foundation, Inc. +Copyright 1991, 1993, 1994, 1996, 1997, 2000-2002, 2005, 2008, 2009, +2012, 2015 Free Software Foundation, Inc. This file is part of the GNU MP Library. @@ -32,7 +32,6 @@ GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" @@ -60,7 +59,7 @@ mpz_powm_sec (mpz_ptr r, mpz_srcptr b, mpz_srcptr e, mpz_srcptr m) /* b^0 mod m, b is anything and m is non-zero. Result is 1 mod m, i.e., 1 or 0 depending on if m = 1. */ SIZ(r) = n != 1 || mp[0] != 1; - PTR(r)[0] = 1; + MPZ_NEWALLOC (r, 1)[0] = 1; return; } DIVIDE_BY_ZERO; @@ -76,9 +75,8 @@ mpz_powm_sec (mpz_ptr r, mpz_srcptr b, mpz_srcptr e, mpz_srcptr m) } TMP_MARK; - tp = TMP_ALLOC_LIMBS (n + mpn_sec_powm_itch (bn, en * GMP_NUMB_BITS, n)); - - rp = tp; tp += n; + TMP_ALLOC_LIMBS_2 (rp, n, + tp, mpn_sec_powm_itch (bn, en * GMP_NUMB_BITS, n)); bp = PTR(b); ep = PTR(e); @@ -96,7 +94,7 @@ mpz_powm_sec (mpz_ptr r, mpz_srcptr b, mpz_srcptr e, mpz_srcptr m) MPN_NORMALIZE (rp, rn); } - MPZ_REALLOC (r, rn); + MPZ_NEWALLOC (r, rn); SIZ(r) = rn; MPN_COPY (PTR(r), rp, rn); diff --git a/Build/source/libs/gmp/gmp-src/mpz/powm_ui.c b/Build/source/libs/gmp/gmp-src/mpz/powm_ui.c index e04bb0ad711..23d3ed8b163 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/powm_ui.c +++ b/Build/source/libs/gmp/gmp-src/mpz/powm_ui.c @@ -2,8 +2,8 @@ Contributed to the GNU project by Torbjörn Granlund. -Copyright 1991, 1993, 1994, 1996, 1997, 2000-2002, 2005, 2008, 2009, 2011-2013 -Free Software Foundation, Inc. +Copyright 1991, 1993, 1994, 1996, 1997, 2000-2002, 2005, 2008, 2009, +2011-2013, 2015 Free Software Foundation, Inc. This file is part of the GNU MP Library. @@ -32,7 +32,6 @@ GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" #include "longlong.h" @@ -59,11 +58,7 @@ see https://www.gnu.org/licenses/. */ static void mod (mp_ptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn, gmp_pi1_t *dinv, mp_ptr tp) { - mp_ptr qp; - TMP_DECL; - TMP_MARK; - - qp = tp; + mp_ptr qp = tp; if (dn == 1) { @@ -90,14 +85,20 @@ mod (mp_ptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn, gmp_pi1_t *dinv, mp_pt /* We need to allocate separate remainder area, since mpn_mu_div_qr does not handle overlap between the numerator and remainder areas. FIXME: Make it handle such overlap. */ - mp_ptr rp = TMP_BALLOC_LIMBS (dn); - mp_size_t itch = mpn_mu_div_qr_itch (nn, dn, 0); - mp_ptr scratch = TMP_BALLOC_LIMBS (itch); + mp_ptr rp, scratch; + mp_size_t itch; + TMP_DECL; + TMP_MARK; + + itch = mpn_mu_div_qr_itch (nn, dn, 0); + rp = TMP_BALLOC_LIMBS (dn); + scratch = TMP_BALLOC_LIMBS (itch); + mpn_mu_div_qr (qp, rp, np, nn, dp, dn, scratch); MPN_COPY (np, rp, dn); - } - TMP_FREE; + TMP_FREE; + } } /* Compute t = a mod m, a is defined by (ap,an), m is defined by (mp,mn), and @@ -109,8 +110,7 @@ reduce (mp_ptr tp, mp_srcptr ap, mp_size_t an, mp_srcptr mp, mp_size_t mn, gmp_p TMP_DECL; TMP_MARK; - rp = TMP_ALLOC_LIMBS (an); - scratch = TMP_ALLOC_LIMBS (an - mn + 1); + TMP_ALLOC_LIMBS_2 (rp, an, scratch, an - mn + 1); MPN_COPY (rp, ap, an); mod (rp, an, mp, mn, dinv, scratch); MPN_COPY (tp, rp, mn); @@ -136,12 +136,17 @@ mpz_powm_ui (mpz_ptr r, mpz_srcptr b, unsigned long int el, mpz_srcptr m) if (UNLIKELY (mn == 0)) DIVIDE_BY_ZERO; - if (el == 0) + if (el <= 1) { + if (el == 1) + { + mpz_mod (r, b, m); + return; + } /* Exponent is zero, result is 1 mod M, i.e., 1 or 0 depending on if M equals 1. */ - SIZ(r) = (mn == 1 && mp[0] == 1) ? 0 : 1; - PTR(r)[0] = 1; + SIZ(r) = mn != 1 || mp[0] != 1; + MPZ_NEWALLOC (r, 1)[0] = 1; return; } @@ -183,9 +188,7 @@ mpz_powm_ui (mpz_ptr r, mpz_srcptr b, unsigned long int el, mpz_srcptr m) return; } - tp = TMP_ALLOC_LIMBS (2 * mn + 1); - xp = TMP_ALLOC_LIMBS (mn); - scratch = TMP_ALLOC_LIMBS (mn + 1); + TMP_ALLOC_LIMBS_3 (xp, mn, scratch, mn + 1, tp, 2 * mn + 1); MPN_COPY (xp, bp, bn); xn = bn; @@ -195,16 +198,7 @@ mpz_powm_ui (mpz_ptr r, mpz_srcptr b, unsigned long int el, mpz_srcptr m) e = (e << c) << 1; /* shift the exp bits to the left, lose msb */ c = GMP_LIMB_BITS - 1 - c; - if (c == 0) - { - /* If m is already normalized (high bit of high limb set), and b is - the same size, but a bigger value, and e==1, then there's no - modular reductions done and we can end up with a result out of - range at the end. */ - if (xn == mn && mpn_cmp (xp, mp, mn) >= 0) - mpn_sub_n (xp, xp, mp, mn); - } - else + ASSERT (c != 0); /* el > 1 */ { /* Main loop. */ do @@ -253,17 +247,12 @@ mpz_powm_ui (mpz_ptr r, mpz_srcptr b, unsigned long int el, mpz_srcptr m) cy = mpn_lshift (tp, xp, xn, m_zero_cnt); tp[xn] = cy; xn += cy != 0; - if (xn < mn) - { - MPN_COPY (xp, tp, xn); - } - else + if (xn >= mn) { mod (tp, xn, mp, mn, &dinv, scratch); - MPN_COPY (xp, tp, mn); xn = mn; } - mpn_rshift (xp, xp, xn, m_zero_cnt); + mpn_rshift (xp, tp, xn, m_zero_cnt); } MPN_NORMALIZE (xp, xn); @@ -274,7 +263,7 @@ mpz_powm_ui (mpz_ptr r, mpz_srcptr b, unsigned long int el, mpz_srcptr m) xn = mn; MPN_NORMALIZE (xp, xn); } - MPZ_REALLOC (r, xn); + MPZ_NEWALLOC (r, xn); SIZ (r) = xn; MPN_COPY (PTR(r), xp, xn); diff --git a/Build/source/libs/gmp/gmp-src/mpz/pprime_p.c b/Build/source/libs/gmp/gmp-src/mpz/pprime_p.c index f3d38a08210..b8a21c2e270 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/pprime_p.c +++ b/Build/source/libs/gmp/gmp-src/mpz/pprime_p.c @@ -6,7 +6,8 @@ positive is (1/4)**reps, where reps is the number of internal passes of the probabilistic algorithm. Knuth indicates that 25 passes are reasonable. -Copyright 1991, 1993, 1994, 1996-2002, 2005 Free Software Foundation, Inc. +Copyright 1991, 1993, 1994, 1996-2002, 2005, 2015, 2016 Free Software +Foundation, Inc. This file is part of the GNU MP Library. @@ -34,7 +35,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" #include "longlong.h" @@ -55,10 +55,12 @@ mpz_probab_prime_p (mpz_srcptr n, int reps) /* Handle small and negative n. */ if (mpz_cmp_ui (n, 1000000L) <= 0) { - int is_prime; if (mpz_cmpabs_ui (n, 1000000L) <= 0) { - is_prime = isprime (mpz_get_ui (n)); + int is_prime; + unsigned long n0; + n0 = mpz_get_ui (n); + is_prime = n0 & (n0 > 1) ? isprime (n0) : n0 == 2; return is_prime ? 2 : 0; } /* Negative number. Negate and fall out. */ @@ -68,7 +70,7 @@ mpz_probab_prime_p (mpz_srcptr n, int reps) } /* If n is now even, it is not a prime. */ - if ((mpz_get_ui (n) & 1) == 0) + if (mpz_even_p (n)) return 0; #if defined (PP) @@ -150,15 +152,15 @@ isprime (unsigned long int t) { unsigned long int q, r, d; - if (t < 3 || (t & 1) == 0) - return t == 2; + ASSERT (t >= 3 && (t & 1) != 0); - for (d = 3, r = 1; r != 0; d += 2) - { + d = 3; + do { q = t / d; r = t - q * d; if (q < d) return 1; - } + d += 2; + } while (r != 0); return 0; } diff --git a/Build/source/libs/gmp/gmp-src/mpz/primorial_ui.c b/Build/source/libs/gmp/gmp-src/mpz/primorial_ui.c index 7a964a1f19b..27039198cdc 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/primorial_ui.c +++ b/Build/source/libs/gmp/gmp-src/mpz/primorial_ui.c @@ -2,7 +2,7 @@ Contributed to the GNU project by Marco Bodrato. -Copyright 2012 Free Software Foundation, Inc. +Copyright 2012, 2015, 2016 Free Software Foundation, Inc. This file is part of the GNU MP Library. @@ -30,7 +30,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" /* TODO: Remove duplicated constants / macros / static functions... @@ -56,7 +55,8 @@ see https://www.gnu.org/licenses/. */ ++__i; \ if (((sieve)[__index] & __mask) == 0) \ { \ - (prime) = id_to_n(__i) + mp_limb_t prime; \ + prime = id_to_n(__i) #define LOOP_ON_SIEVE_BEGIN(prime,start,end,off,sieve) \ do { \ @@ -73,7 +73,7 @@ see https://www.gnu.org/licenses/. */ } \ __mask = __mask << 1 | __mask >> (GMP_LIMB_BITS-1); \ __index += __mask & 1; \ - } while (__i <= __max_i) \ + } while (__i <= __max_i) #define LOOP_ON_SIEVE_END \ LOOP_ON_SIEVE_STOP; \ @@ -108,24 +108,22 @@ primesieve_size (mp_limb_t n) { return n_to_bit(n) / GMP_LIMB_BITS + 1; } void mpz_primorial_ui (mpz_ptr x, unsigned long n) { - static const mp_limb_t table[] = { 1, 1, 2, 6, 6 }; - ASSERT (n <= GMP_NUMB_MAX); - if (n < numberof (table)) + if (n < 5) { - PTR (x)[0] = table[n]; + MPZ_NEWALLOC (x, 1)[0] = (066211 >> (n*3)) & 7; SIZ (x) = 1; } else { mp_limb_t *sieve, *factors; - mp_size_t size; + mp_size_t size, j; mp_limb_t prod; - mp_limb_t j; TMP_DECL; - size = 1 + n / GMP_NUMB_BITS + n / (2*GMP_NUMB_BITS); + size = n / GMP_NUMB_BITS; + size = size + (size >> 1) + 1; ASSERT (size >= primesieve_size (n)); sieve = MPZ_NEWALLOC (x, size); size = (gmp_primesieve (sieve, n) + 1) / log_n_max (n) + 1; @@ -135,20 +133,20 @@ mpz_primorial_ui (mpz_ptr x, unsigned long n) j = 0; - prod = table[numberof (table)-1]; + prod = 6; /* Store primes from 5 to n */ { - mp_limb_t prime, max_prod; + mp_limb_t max_prod; max_prod = GMP_NUMB_MAX / n; - LOOP_ON_SIEVE_BEGIN (prime, n_to_bit(numberof (table)), n_to_bit (n), 0, sieve); + LOOP_ON_SIEVE_BEGIN (prime, n_to_bit(5), n_to_bit (n), 0, sieve); FACTOR_LIST_STORE (prime, prod, max_prod, factors, j); LOOP_ON_SIEVE_END; } - if (LIKELY (j != 0)) + if (j != 0) { factors[j++] = prod; mpz_prodlimbs (x, factors, j); diff --git a/Build/source/libs/gmp/gmp-src/mpz/prodlimbs.c b/Build/source/libs/gmp/gmp-src/mpz/prodlimbs.c index 8d84bcb4353..23f06a15b51 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/prodlimbs.c +++ b/Build/source/libs/gmp/gmp-src/mpz/prodlimbs.c @@ -35,7 +35,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" /*********************************************************/ diff --git a/Build/source/libs/gmp/gmp-src/mpz/random.c b/Build/source/libs/gmp/gmp-src/mpz/random.c index 1dca3a93cdd..1a1e5157b4b 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/random.c +++ b/Build/source/libs/gmp/gmp-src/mpz/random.c @@ -28,7 +28,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" void diff --git a/Build/source/libs/gmp/gmp-src/mpz/random2.c b/Build/source/libs/gmp/gmp-src/mpz/random2.c index 7f9e5f28e8b..2c72540c1c3 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/random2.c +++ b/Build/source/libs/gmp/gmp-src/mpz/random2.c @@ -2,7 +2,8 @@ long runs of consecutive ones and zeros in the binary representation. Meant for testing of other MP routines. -Copyright 1991, 1993, 1994, 1996, 2001, 2012 Free Software Foundation, Inc. +Copyright 1991, 1993, 1994, 1996, 2001, 2012, 2015 Free Software +Foundation, Inc. This file is part of the GNU MP Library. @@ -30,7 +31,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" void @@ -42,7 +42,7 @@ mpz_random2 (mpz_ptr x, mp_size_t size) abs_size = ABS (size); if (abs_size != 0) { - xp = MPZ_REALLOC (x, abs_size); + xp = MPZ_NEWALLOC (x, abs_size); mpn_random2 (xp, abs_size); } diff --git a/Build/source/libs/gmp/gmp-src/mpz/realloc.c b/Build/source/libs/gmp/gmp-src/mpz/realloc.c index 3d2755ca0a1..bb55bf6834a 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/realloc.c +++ b/Build/source/libs/gmp/gmp-src/mpz/realloc.c @@ -1,6 +1,7 @@ /* _mpz_realloc -- make the mpz_t have NEW_ALLOC digits allocated. -Copyright 1991, 1993-1995, 2000, 2001, 2008 Free Software Foundation, Inc. +Copyright 1991, 1993-1995, 2000, 2001, 2008, 2015 Free Software +Foundation, Inc. This file is part of the GNU MP Library. @@ -30,7 +31,6 @@ see https://www.gnu.org/licenses/. */ #include <stdlib.h> #include <stdio.h> -#include "gmp.h" #include "gmp-impl.h" void * @@ -58,14 +58,21 @@ _mpz_realloc (mpz_ptr m, mp_size_t new_alloc) } } - mp = __GMP_REALLOCATE_FUNC_LIMBS (PTR(m), ALLOC(m), new_alloc); - PTR(m) = mp; - ALLOC(m) = new_alloc; + if (ALLOC (m) == 0) + { + mp = __GMP_ALLOCATE_FUNC_LIMBS (new_alloc); + } + else + { + mp = __GMP_REALLOCATE_FUNC_LIMBS (PTR (m), ALLOC (m), new_alloc); - /* Don't create an invalid number; if the current value doesn't fit after - reallocation, clear it to 0. */ - if (ABSIZ(m) > new_alloc) - SIZ(m) = 0; + /* Don't create an invalid number; if the current value doesn't fit after + reallocation, clear it to 0. */ + if (UNLIKELY (ABSIZ (m) > new_alloc)) + SIZ (m) = 0; + } + PTR (m) = mp; + ALLOC(m) = new_alloc; return (void *) mp; } diff --git a/Build/source/libs/gmp/gmp-src/mpz/realloc2.c b/Build/source/libs/gmp/gmp-src/mpz/realloc2.c index 3ccfaab1f06..53503394255 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/realloc2.c +++ b/Build/source/libs/gmp/gmp-src/mpz/realloc2.c @@ -1,6 +1,6 @@ /* mpz_realloc2 -- change allocated data size. -Copyright 2001, 2002, 2008 Free Software Foundation, Inc. +Copyright 2001, 2002, 2008, 2015 Free Software Foundation, Inc. This file is part of the GNU MP Library. @@ -30,7 +30,6 @@ see https://www.gnu.org/licenses/. */ #include <stdlib.h> #include <stdio.h> -#include "gmp.h" #include "gmp-impl.h" void @@ -50,11 +49,19 @@ mpz_realloc2 (mpz_ptr m, mp_bitcnt_t bits) } } - PTR(m) = __GMP_REALLOCATE_FUNC_LIMBS (PTR(m), ALLOC(m), new_alloc); - ALLOC(m) = new_alloc; + if (ALLOC (m) == 0) + { + PTR (m) = __GMP_ALLOCATE_FUNC_LIMBS (new_alloc); + } + else + { + PTR (m) = __GMP_REALLOCATE_FUNC_LIMBS (PTR(m), ALLOC(m), new_alloc); - /* Don't create an invalid number; if the current value doesn't fit after - reallocation, clear it to 0. */ - if (ABSIZ(m) > new_alloc) - SIZ(m) = 0; + /* Don't create an invalid number; if the current value doesn't fit after + reallocation, clear it to 0. */ + if (ABSIZ(m) > new_alloc) + SIZ(m) = 0; + } + + ALLOC(m) = new_alloc; } diff --git a/Build/source/libs/gmp/gmp-src/mpz/remove.c b/Build/source/libs/gmp/gmp-src/mpz/remove.c index 3d293587383..a6551214d96 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/remove.c +++ b/Build/source/libs/gmp/gmp-src/mpz/remove.c @@ -28,7 +28,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" mp_bitcnt_t diff --git a/Build/source/libs/gmp/gmp-src/mpz/roinit_n.c b/Build/source/libs/gmp/gmp-src/mpz/roinit_n.c index 137dbda83c6..91254663490 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/roinit_n.c +++ b/Build/source/libs/gmp/gmp-src/mpz/roinit_n.c @@ -28,7 +28,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" mpz_srcptr diff --git a/Build/source/libs/gmp/gmp-src/mpz/root.c b/Build/source/libs/gmp/gmp-src/mpz/root.c index 31eb440b4f2..7119bbc3a57 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/root.c +++ b/Build/source/libs/gmp/gmp-src/mpz/root.c @@ -30,7 +30,6 @@ GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ #include <stdio.h> /* for NULL */ -#include "gmp.h" #include "gmp-impl.h" int @@ -65,7 +64,7 @@ mpz_root (mpz_ptr root, mpz_srcptr u, unsigned long int nth) /* FIXME: Perhaps disallow root == NULL */ if (root != NULL && u != root) - rootp = MPZ_REALLOC (root, rootn); + rootp = MPZ_NEWALLOC (root, rootn); else rootp = TMP_ALLOC_LIMBS (rootn); diff --git a/Build/source/libs/gmp/gmp-src/mpz/rootrem.c b/Build/source/libs/gmp/gmp-src/mpz/rootrem.c index ac4a1e030af..67953dbe650 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/rootrem.c +++ b/Build/source/libs/gmp/gmp-src/mpz/rootrem.c @@ -30,7 +30,6 @@ GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ #include <stdio.h> /* for NULL */ -#include "gmp.h" #include "gmp-impl.h" void @@ -66,12 +65,12 @@ mpz_rootrem (mpz_ptr root, mpz_ptr rem, mpz_srcptr u, unsigned long int nth) /* FIXME: Perhaps disallow root == NULL */ if (root != NULL && u != root) - rootp = MPZ_REALLOC (root, rootn); + rootp = MPZ_NEWALLOC (root, rootn); else rootp = TMP_ALLOC_LIMBS (rootn); if (u != rem) - remp = MPZ_REALLOC (rem, un); + remp = MPZ_NEWALLOC (rem, un); else remp = TMP_ALLOC_LIMBS (un); diff --git a/Build/source/libs/gmp/gmp-src/mpz/rrandomb.c b/Build/source/libs/gmp/gmp-src/mpz/rrandomb.c index 8b1803c6baa..39546a6bcd4 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/rrandomb.c +++ b/Build/source/libs/gmp/gmp-src/mpz/rrandomb.c @@ -30,7 +30,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" static void gmp_rrandomb (mp_ptr, gmp_randstate_t, mp_bitcnt_t); diff --git a/Build/source/libs/gmp/gmp-src/mpz/scan0.c b/Build/source/libs/gmp/gmp-src/mpz/scan0.c index de24595cfe9..4b0f1ef2b44 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/scan0.c +++ b/Build/source/libs/gmp/gmp-src/mpz/scan0.c @@ -28,7 +28,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" #include "longlong.h" diff --git a/Build/source/libs/gmp/gmp-src/mpz/scan1.c b/Build/source/libs/gmp/gmp-src/mpz/scan1.c index e6b759e2beb..d09614701c9 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/scan1.c +++ b/Build/source/libs/gmp/gmp-src/mpz/scan1.c @@ -28,7 +28,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" #include "longlong.h" diff --git a/Build/source/libs/gmp/gmp-src/mpz/set.c b/Build/source/libs/gmp/gmp-src/mpz/set.c index 9d7d58c8d03..7789af37793 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/set.c +++ b/Build/source/libs/gmp/gmp-src/mpz/set.c @@ -1,6 +1,6 @@ /* mpz_set (dest_integer, src_integer) -- Assign DEST_INTEGER from SRC_INTEGER. -Copyright 1991, 1993-1995, 2000, 2012 Free Software Foundation, Inc. +Copyright 1991, 1993-1995, 2000, 2012, 2015 Free Software Foundation, Inc. This file is part of the GNU MP Library. @@ -28,7 +28,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" @@ -41,7 +40,7 @@ mpz_set (mpz_ptr w, mpz_srcptr u) usize = SIZ(u); size = ABS (usize); - wp = MPZ_REALLOC (w, size); + wp = MPZ_NEWALLOC (w, size); up = PTR(u); diff --git a/Build/source/libs/gmp/gmp-src/mpz/set_d.c b/Build/source/libs/gmp/gmp-src/mpz/set_d.c index d40ee726d23..8cbda1164ed 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/set_d.c +++ b/Build/source/libs/gmp/gmp-src/mpz/set_d.c @@ -1,6 +1,6 @@ /* mpz_set_d(integer, val) -- Assign INTEGER with a double value VAL. -Copyright 1995, 1996, 2000-2003, 2006 Free Software Foundation, Inc. +Copyright 1995, 1996, 2000-2003, 2006, 2015 Free Software Foundation, Inc. This file is part of the GNU MP Library. @@ -34,7 +34,6 @@ see https://www.gnu.org/licenses/. */ #include <float.h> /* for DBL_MAX */ #endif -#include "gmp.h" #include "gmp-impl.h" @@ -62,13 +61,10 @@ mpz_set_d (mpz_ptr r, double d) rn = __gmp_extract_double (tp, d); - if (ALLOC(r) < rn) - _mpz_realloc (r, rn); - if (rn <= 0) rn = 0; - rp = PTR (r); + rp = MPZ_NEWALLOC (r, rn); switch (rn) { diff --git a/Build/source/libs/gmp/gmp-src/mpz/set_f.c b/Build/source/libs/gmp/gmp-src/mpz/set_f.c index 4eb98198371..b3ecc0be056 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/set_f.c +++ b/Build/source/libs/gmp/gmp-src/mpz/set_f.c @@ -1,6 +1,6 @@ /* mpz_set_f (dest_integer, src_float) -- Assign DEST_INTEGER from SRC_FLOAT. -Copyright 1996, 2001, 2012 Free Software Foundation, Inc. +Copyright 1996, 2001, 2012, 2016 Free Software Foundation, Inc. This file is part of the GNU MP Library. @@ -28,7 +28,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" @@ -47,7 +46,7 @@ mpz_set_f (mpz_ptr w, mpf_srcptr u) return; } - wp = MPZ_REALLOC (w, exp); + wp = MPZ_NEWALLOC (w, exp); up = PTR(u); size = SIZ (u); diff --git a/Build/source/libs/gmp/gmp-src/mpz/set_q.c b/Build/source/libs/gmp/gmp-src/mpz/set_q.c index 2627e822980..2280247bf72 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/set_q.c +++ b/Build/source/libs/gmp/gmp-src/mpz/set_q.c @@ -31,5 +31,4 @@ see https://www.gnu.org/licenses/. */ #define __GMP_FORCE_mpz_set_q 1 -#include "gmp.h" #include "gmp-impl.h" diff --git a/Build/source/libs/gmp/gmp-src/mpz/set_si.c b/Build/source/libs/gmp/gmp-src/mpz/set_si.c index 1370368332e..973aef8ba5a 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/set_si.c +++ b/Build/source/libs/gmp/gmp-src/mpz/set_si.c @@ -1,6 +1,7 @@ /* mpz_set_si(dest,val) -- Assign DEST with a small value VAL. -Copyright 1991, 1993-1995, 2000-2002, 2012 Free Software Foundation, Inc. +Copyright 1991, 1993-1995, 2000-2002, 2012, 2015 Free Software +Foundation, Inc. This file is part of the GNU MP Library. @@ -28,7 +29,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" void @@ -39,7 +39,7 @@ mpz_set_si (mpz_ptr dest, signed long int val) vl = (mp_limb_t) ABS_CAST (unsigned long int, val); - PTR (dest)[0] = vl & GMP_NUMB_MASK; + MPZ_NEWALLOC (dest, 1)[0] = vl & GMP_NUMB_MASK; size = vl != 0; #if GMP_NAIL_BITS != 0 diff --git a/Build/source/libs/gmp/gmp-src/mpz/set_str.c b/Build/source/libs/gmp/gmp-src/mpz/set_str.c index 848d2136a0a..26c102b460e 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/set_str.c +++ b/Build/source/libs/gmp/gmp-src/mpz/set_str.c @@ -35,7 +35,6 @@ see https://www.gnu.org/licenses/. */ #include <string.h> #include <ctype.h> -#include "gmp.h" #include "gmp-impl.h" #include "longlong.h" @@ -59,7 +58,7 @@ mpz_set_str (mpz_ptr x, const char *str, int base) /* For bases > 36, use the collating sequence 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz. */ digit_value += 208; - if (base > 62) + if (UNLIKELY (base > 62)) return -1; /* too large base */ } @@ -121,7 +120,7 @@ mpz_set_str (mpz_ptr x, const char *str, int base) if (!isspace (c)) { int dig = digit_value[c]; - if (dig >= base) + if (UNLIKELY (dig >= base)) { TMP_FREE; return -1; @@ -134,7 +133,7 @@ mpz_set_str (mpz_ptr x, const char *str, int base) str_size = s - begs; LIMBS_PER_DIGIT_IN_BASE (xsize, str_size, base); - MPZ_REALLOC (x, xsize); + MPZ_NEWALLOC (x, xsize); /* Convert the byte array in base BASE to our bignum format. */ xsize = mpn_set_str (PTR (x), (unsigned char *) begs, str_size, base); diff --git a/Build/source/libs/gmp/gmp-src/mpz/set_ui.c b/Build/source/libs/gmp/gmp-src/mpz/set_ui.c index f36754cd59b..12e95d170f8 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/set_ui.c +++ b/Build/source/libs/gmp/gmp-src/mpz/set_ui.c @@ -1,7 +1,7 @@ /* mpz_set_ui(integer, val) -- Assign INTEGER with a small value VAL. -Copyright 1991, 1993-1995, 2001, 2002, 2004, 2012 Free Software Foundation, -Inc. +Copyright 1991, 1993-1995, 2001, 2002, 2004, 2012, 2015 Free Software +Foundation, Inc. This file is part of the GNU MP Library. @@ -29,7 +29,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" void @@ -37,7 +36,7 @@ mpz_set_ui (mpz_ptr dest, unsigned long int val) { mp_size_t size; - PTR (dest)[0] = val & GMP_NUMB_MASK; + MPZ_NEWALLOC (dest, 1)[0] = val & GMP_NUMB_MASK; size = val != 0; #if BITS_PER_ULONG > GMP_NUMB_BITS /* avoid warnings about shift amount */ diff --git a/Build/source/libs/gmp/gmp-src/mpz/setbit.c b/Build/source/libs/gmp/gmp-src/mpz/setbit.c index 3c2c139f987..228a564b2b2 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/setbit.c +++ b/Build/source/libs/gmp/gmp-src/mpz/setbit.c @@ -29,7 +29,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" void diff --git a/Build/source/libs/gmp/gmp-src/mpz/size.c b/Build/source/libs/gmp/gmp-src/mpz/size.c index 2b324c34230..b8aa59ec2af 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/size.c +++ b/Build/source/libs/gmp/gmp-src/mpz/size.c @@ -31,5 +31,4 @@ see https://www.gnu.org/licenses/. */ #define __GMP_FORCE_mpz_size 1 -#include "gmp.h" #include "gmp-impl.h" diff --git a/Build/source/libs/gmp/gmp-src/mpz/sizeinbase.c b/Build/source/libs/gmp/gmp-src/mpz/sizeinbase.c index 0f3851ea861..7a1bd016124 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/sizeinbase.c +++ b/Build/source/libs/gmp/gmp-src/mpz/sizeinbase.c @@ -30,7 +30,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" #include "longlong.h" diff --git a/Build/source/libs/gmp/gmp-src/mpz/sqrt.c b/Build/source/libs/gmp/gmp-src/mpz/sqrt.c index 0272319b3c9..74d2f757884 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/sqrt.c +++ b/Build/source/libs/gmp/gmp-src/mpz/sqrt.c @@ -1,7 +1,7 @@ /* mpz_sqrt(root, u) -- Set ROOT to floor(sqrt(U)). -Copyright 1991, 1993, 1994, 1996, 2000, 2001, 2005, 2012 Free Software -Foundation, Inc. +Copyright 1991, 1993, 1994, 1996, 2000, 2001, 2005, 2012, 2015 Free +Software Foundation, Inc. This file is part of the GNU MP Library. @@ -30,7 +30,6 @@ GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ #include <stdio.h> /* for NULL */ -#include "gmp.h" #include "gmp-impl.h" void @@ -42,7 +41,7 @@ mpz_sqrt (mpz_ptr root, mpz_srcptr op) op_size = SIZ (op); if (UNLIKELY (op_size <= 0)) { - if (op_size < 0) + if (UNLIKELY (op_size < 0)) SQRT_OF_NEGATIVE; SIZ(root) = 0; return; diff --git a/Build/source/libs/gmp/gmp-src/mpz/sqrtrem.c b/Build/source/libs/gmp/gmp-src/mpz/sqrtrem.c index 63a06eb0b7b..a580d95910d 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/sqrtrem.c +++ b/Build/source/libs/gmp/gmp-src/mpz/sqrtrem.c @@ -1,8 +1,8 @@ /* mpz_sqrtrem(root,rem,x) -- Set ROOT to floor(sqrt(X)) and REM to the remainder, i.e. X - ROOT**2. -Copyright 1991, 1993, 1994, 1996, 2000, 2001, 2005, 2011, 2012 Free Software -Foundation, Inc. +Copyright 1991, 1993, 1994, 1996, 2000, 2001, 2005, 2011, 2012, 2015 Free +Software Foundation, Inc. This file is part of the GNU MP Library. @@ -30,7 +30,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" void @@ -42,14 +41,15 @@ mpz_sqrtrem (mpz_ptr root, mpz_ptr rem, mpz_srcptr op) op_size = SIZ (op); if (UNLIKELY (op_size <= 0)) { - if (op_size < 0) + if (UNLIKELY (op_size < 0)) SQRT_OF_NEGATIVE; SIZ(root) = 0; SIZ(rem) = 0; return; } - rem_ptr = MPZ_REALLOC (rem, op_size); + /* No-op if rem == op */ + rem_ptr = MPZ_NEWALLOC (rem, op_size); /* The size of the root is accurate after this simple calculation. */ root_size = (op_size + 1) / 2; diff --git a/Build/source/libs/gmp/gmp-src/mpz/stronglucas.c b/Build/source/libs/gmp/gmp-src/mpz/stronglucas.c new file mode 100644 index 00000000000..350dd2a48e9 --- /dev/null +++ b/Build/source/libs/gmp/gmp-src/mpz/stronglucas.c @@ -0,0 +1,178 @@ +/* mpz_stronglucas(n, t1, t2) -- An implementation of the strong Lucas + primality test on n, using parameters as suggested by the BPSW test. + + THE FUNCTIONS IN THIS FILE ARE FOR INTERNAL USE ONLY. THEY'RE ALMOST + CERTAIN TO BE SUBJECT TO INCOMPATIBLE CHANGES OR DISAPPEAR COMPLETELY IN + FUTURE GNU MP RELEASES. + +Copyright 2018 Free Software Foundation, Inc. + +Contributed by Marco Bodrato. + +This file is part of the GNU MP Library. + +The GNU MP Library is free software; you can redistribute it and/or modify +it under the terms of either: + + * the GNU Lesser General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your + option) any later version. + +or + + * the GNU General Public License as published by the Free Software + Foundation; either version 2 of the License, or (at your option) any + later version. + +or both in parallel, as here. + +The GNU MP Library is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY +or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received copies of the GNU General Public License and the +GNU Lesser General Public License along with the GNU MP Library. If not, +see https://www.gnu.org/licenses/. */ + +#include "gmp-impl.h" +#include "longlong.h" + +/* Returns an approximation of the sqare root of x. + * It gives: + * limb_apprsqrt (x) ^ 2 <= x < (limb_apprsqrt (x)+1) ^ 2 + * or + * x <= limb_apprsqrt (x) ^ 2 <= x * 9/8 + */ +static mp_limb_t +limb_apprsqrt (mp_limb_t x) +{ + int s; + + ASSERT (x > 2); + count_leading_zeros (s, x); + s = (GMP_LIMB_BITS - s) >> 1; + return ((CNST_LIMB(1) << s) + (x >> s)) >> 1; +} + +/* Performs strong Lucas' test on x, with parameters suggested */ +/* for the BPSW test. Qk and V are passed to recycle variables. */ +/* Requires GCD (x,6) = 1.*/ +int +mpz_stronglucas (mpz_srcptr x, mpz_ptr V, mpz_ptr Qk) +{ + mp_bitcnt_t b0; + mpz_t n; + mp_limb_t D; /* The absolute value is stored. */ + long Q; + mpz_t T1, T2; + + /* Test on the absolute value. */ + mpz_roinit_n (n, PTR (x), ABSIZ (x)); + + ASSERT (mpz_odd_p (n)); + /* ASSERT (mpz_gcd_ui (NULL, n, 6) == 1); */ +#if GMP_NUMB_BITS % 16 == 0 + /* (2^12 - 1) | (2^{GMP_NUMB_BITS*3/4} - 1) */ + D = mpn_mod_34lsub1 (PTR (n), SIZ (n)); + /* (2^12 - 1) = 3^2 * 5 * 7 * 13 */ + ASSERT (D % 3 != 0 && D % 5 != 0 && D % 7 != 0); + if ((D % 5 & 2) != 0) + /* (5/n) = -1, iff n = 2 or 3 (mod 5) */ + /* D = 5; Q = -1 */ + return mpn_strongfibo (PTR (n), SIZ (n), PTR (V)); + else if (! POW2_P (D % 7)) + /* (-7/n) = -1, iff n = 3,5 or 6 (mod 7) */ + D = 7; /* Q = 2 */ + /* (9/n) = -1, never: 9 = 3^2 */ + else if (mpz_kronecker_ui (n, 11) == -1) + /* (-11/n) = (n/11) */ + D = 11; /* Q = 3 */ + else if ((((D % 13 - (D % 13 >> 3)) & 7) > 4) || + (((D % 13 - (D % 13 >> 3)) & 7) == 2)) + /* (13/n) = -1, iff n = 2,5,6,7,8 or 11 (mod 13) */ + D = 13; /* Q = -3 */ + else if (D % 3 == 2) + /* (-15/n) = (n/15) = (n/5)*(n/3) */ + /* Here, (n/5) = 1, and */ + /* (n/3) = -1, iff n = 2 (mod 3) */ + D = 15; /* Q = 4 */ +#if GMP_NUMB_BITS % 32 == 0 + /* (2^24 - 1) | (2^{GMP_NUMB_BITS*3/4} - 1) */ + /* (2^24 - 1) = (2^12 - 1) * 17 * 241 */ + else if (! POW2_P (D % 17) && ! POW2_P (17 - D % 17)) + D = 17; /* Q = -4 */ +#endif +#else + if (mpz_kronecker_ui (n, 5) == -1) + return mpn_strongfibo (PTR (n), SIZ (n), PTR (V)); +#endif + else + { + mp_limb_t tl; + mp_limb_t maxD; + int jac_bit1; + + if (UNLIKELY (mpz_perfect_square_p (n))) + return 0; /* A square is composite. */ + + /* Check Ds up to square root (in case, n is prime) + or avoid overflows */ + if (SIZ (n) == 1) + maxD = limb_apprsqrt (* PTR (n)); + else if (BITS_PER_ULONG >= GMP_NUMB_BITS && SIZ (n) == 2) + mpn_sqrtrem (&maxD, (mp_ptr) NULL, PTR (n), 2); + else + maxD = GMP_NUMB_MAX; + maxD = MIN (maxD, ULONG_MAX); + + D = GMP_NUMB_BITS % 16 == 0 ? (GMP_NUMB_BITS % 32 == 0 ? 17 : 15) : 5; + + /* Search a D such that (D/n) = -1 in the sequence 5,-7,9,-11,.. */ + /* For those Ds we have (D/n) = (n/|D|) */ + /* FIXME: Should we loop only on prime Ds? */ + /* The only interesting composite D is 15. */ + do + { + if (UNLIKELY (D >= maxD)) + return 1; + D += 2; + jac_bit1 = 0; + JACOBI_MOD_OR_MODEXACT_1_ODD (jac_bit1, tl, PTR (n), SIZ (n), D); + if (UNLIKELY (tl == 0)) + return 0; + } + while (mpn_jacobi_base (tl, D, jac_bit1) == 1); + } + + /* D= P^2 - 4Q; P = 1; Q = (1-D)/4 */ + Q = (D & 2) ? (D >> 2) + 1 : -(long) (D >> 2); + /* ASSERT (mpz_si_kronecker ((D & 2) ? NEG_CAST (long, D) : D, n) == -1); */ + + /* n-(D/n) = n+1 = d*2^{b0}, with d = (n>>b0) | 1 */ + b0 = mpz_scan0 (n, 0); + + mpz_init (T1); + mpz_init (T2); + + /* If Ud != 0 && Vd != 0 */ + if (mpz_lucas_mod (V, Qk, Q, b0, n, T1, T2) == 0) + if (LIKELY (--b0 != 0)) + do + { + /* V_{2k} <- V_k ^ 2 - 2Q^k */ + mpz_mul (T2, V, V); + mpz_submul_ui (T2, Qk, 2); + mpz_tdiv_r (V, T2, n); + if (SIZ (V) == 0 || UNLIKELY (--b0 == 0)) + break; + /* Q^{2k} = (Q^k)^2 */ + mpz_mul (T2, Qk, Qk); + mpz_tdiv_r (Qk, T2, n); + } while (1); + + mpz_clear (T1); + mpz_clear (T2); + + return (b0 != 0); +} diff --git a/Build/source/libs/gmp/gmp-src/mpz/swap.c b/Build/source/libs/gmp/gmp-src/mpz/swap.c index e5ef2673f38..255fac0823c 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/swap.c +++ b/Build/source/libs/gmp/gmp-src/mpz/swap.c @@ -28,7 +28,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" void diff --git a/Build/source/libs/gmp/gmp-src/mpz/tdiv_q.c b/Build/source/libs/gmp/gmp-src/mpz/tdiv_q.c index 38528f35bfb..8c5001df155 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/tdiv_q.c +++ b/Build/source/libs/gmp/gmp-src/mpz/tdiv_q.c @@ -29,7 +29,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" #include "longlong.h" @@ -38,7 +37,7 @@ mpz_tdiv_q (mpz_ptr quot, mpz_srcptr num, mpz_srcptr den) { mp_size_t ql; mp_size_t ns, ds, nl, dl; - mp_ptr np, dp, qp; + mp_ptr np, dp, qp, tp; TMP_DECL; ns = SIZ (num); @@ -59,7 +58,6 @@ mpz_tdiv_q (mpz_ptr quot, mpz_srcptr num, mpz_srcptr den) qp = MPZ_REALLOC (quot, ql); TMP_MARK; - np = PTR (num); dp = PTR (den); /* Copy denominator to temporary space if it overlaps with the quotient. */ @@ -70,21 +68,17 @@ mpz_tdiv_q (mpz_ptr quot, mpz_srcptr num, mpz_srcptr den) MPN_COPY (tp, dp, dl); dp = tp; } + + tp = TMP_ALLOC_LIMBS (nl + 1); + np = PTR (num); /* Copy numerator to temporary space if it overlaps with the quotient. */ if (np == qp) { - mp_ptr tp; - tp = TMP_ALLOC_LIMBS (nl + 1); MPN_COPY (tp, np, nl); /* Overlap dividend and scratch. */ - mpn_div_q (qp, tp, nl, dp, dl, tp); - } - else - { - mp_ptr tp; - tp = TMP_ALLOC_LIMBS (nl + 1); - mpn_div_q (qp, np, nl, dp, dl, tp); + np = tp; } + mpn_div_q (qp, np, nl, dp, dl, tp); ql -= qp[ql - 1] == 0; diff --git a/Build/source/libs/gmp/gmp-src/mpz/tdiv_q_2exp.c b/Build/source/libs/gmp/gmp-src/mpz/tdiv_q_2exp.c index 9ffcaf2bbbe..c6b9bd0244f 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/tdiv_q_2exp.c +++ b/Build/source/libs/gmp/gmp-src/mpz/tdiv_q_2exp.c @@ -30,7 +30,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" void diff --git a/Build/source/libs/gmp/gmp-src/mpz/tdiv_q_ui.c b/Build/source/libs/gmp/gmp-src/mpz/tdiv_q_ui.c index 88e90825290..a11c51efb63 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/tdiv_q_ui.c +++ b/Build/source/libs/gmp/gmp-src/mpz/tdiv_q_ui.c @@ -30,7 +30,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" unsigned long int diff --git a/Build/source/libs/gmp/gmp-src/mpz/tdiv_qr.c b/Build/source/libs/gmp/gmp-src/mpz/tdiv_qr.c index ab9a37dae9c..eda95010363 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/tdiv_qr.c +++ b/Build/source/libs/gmp/gmp-src/mpz/tdiv_qr.c @@ -30,7 +30,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" #include "longlong.h" diff --git a/Build/source/libs/gmp/gmp-src/mpz/tdiv_qr_ui.c b/Build/source/libs/gmp/gmp-src/mpz/tdiv_qr_ui.c index 4f667abe07d..4e1c9fa0ac4 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/tdiv_qr_ui.c +++ b/Build/source/libs/gmp/gmp-src/mpz/tdiv_qr_ui.c @@ -2,8 +2,8 @@ Set QUOT to DIVIDEND / SHORT_DIVISOR and REM to DIVIDEND mod SHORT_DIVISOR. -Copyright 1991, 1993, 1994, 1996, 1998, 2001, 2002, 2004, 2012 Free Software -Foundation, Inc. +Copyright 1991, 1993, 1994, 1996, 1998, 2001, 2002, 2004, 2012, 2015 +Free Software Foundation, Inc. This file is part of the GNU MP Library. @@ -31,7 +31,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" unsigned long int @@ -68,7 +67,7 @@ mpz_tdiv_qr_ui (mpz_ptr quot, mpz_ptr rem, mpz_srcptr dividend, unsigned long in SIZ(quot) = 0; rl = np[0]; SIZ(rem) = ns >= 0 ? 1 : -1; - PTR(rem)[0] = rl; + MPZ_NEWALLOC (rem, 1)[0] = rl; return rl; } @@ -90,10 +89,8 @@ mpz_tdiv_qr_ui (mpz_ptr quot, mpz_ptr rem, mpz_srcptr dividend, unsigned long in SIZ(rem) = 0; else { - /* Store the single-limb remainder. We don't check if there's space - for just one limb, since no function ever makes zero space. */ SIZ(rem) = ns >= 0 ? 1 : -1; - PTR(rem)[0] = rl; + MPZ_NEWALLOC (rem, 1)[0] = rl; } qn = nn - (qp[nn - 1] == 0); } diff --git a/Build/source/libs/gmp/gmp-src/mpz/tdiv_r.c b/Build/source/libs/gmp/gmp-src/mpz/tdiv_r.c index d9cb38c3232..c76275e53a4 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/tdiv_r.c +++ b/Build/source/libs/gmp/gmp-src/mpz/tdiv_r.c @@ -29,7 +29,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" #include "longlong.h" @@ -37,32 +36,32 @@ void mpz_tdiv_r (mpz_ptr rem, mpz_srcptr num, mpz_srcptr den) { mp_size_t ql; - mp_size_t ns, ds, nl, dl; + mp_size_t ns, nl, dl; mp_ptr np, dp, qp, rp; TMP_DECL; ns = SIZ (num); - ds = SIZ (den); nl = ABS (ns); - dl = ABS (ds); + dl = ABSIZ (den); ql = nl - dl + 1; if (UNLIKELY (dl == 0)) DIVIDE_BY_ZERO; - rp = MPZ_REALLOC (rem, dl); - if (ql <= 0) { if (num != rem) { + SIZ (rem) = ns; + rp = MPZ_NEWALLOC (rem, nl); np = PTR (num); MPN_COPY (rp, np, nl); - SIZ (rem) = SIZ (num); } return; } + rp = MPZ_REALLOC (rem, dl); + TMP_MARK; qp = TMP_ALLOC_LIMBS (ql); np = PTR (num); diff --git a/Build/source/libs/gmp/gmp-src/mpz/tdiv_r_2exp.c b/Build/source/libs/gmp/gmp-src/mpz/tdiv_r_2exp.c index e21d90fecd5..96a81f7fc49 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/tdiv_r_2exp.c +++ b/Build/source/libs/gmp/gmp-src/mpz/tdiv_r_2exp.c @@ -28,7 +28,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" void @@ -54,22 +53,21 @@ mpz_tdiv_r_2exp (mpz_ptr res, mpz_srcptr in, mp_bitcnt_t cnt) } else { - res_size = limb_cnt; - MPN_NORMALIZE (in_ptr, res_size); + MPN_NORMALIZE (in_ptr, limb_cnt); - MPZ_REALLOC (res, res_size); + MPZ_REALLOC (res, limb_cnt); - limb_cnt = res_size; + res_size = limb_cnt; } } else { /* The input operand is smaller than 2**CNT. We perform a no-op, apart from that we might need to copy IN to RES. */ - res_size = in_size; - MPZ_REALLOC (res, res_size); + limb_cnt = in_size; + MPZ_REALLOC (res, limb_cnt); - limb_cnt = res_size; + res_size = limb_cnt; } if (res != in) diff --git a/Build/source/libs/gmp/gmp-src/mpz/tdiv_r_ui.c b/Build/source/libs/gmp/gmp-src/mpz/tdiv_r_ui.c index 30addd6db79..f3da8efae85 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/tdiv_r_ui.c +++ b/Build/source/libs/gmp/gmp-src/mpz/tdiv_r_ui.c @@ -1,8 +1,8 @@ /* mpz_tdiv_r_ui(rem, dividend, divisor_limb) -- Set REM to DIVDEND mod DIVISOR_LIMB. -Copyright 1991, 1993, 1994, 1996, 1998, 2001, 2002, 2004, 2005, 2012 Free -Software Foundation, Inc. +Copyright 1991, 1993, 1994, 1996, 1998, 2001, 2002, 2004, 2005, 2012, +2015 Free Software Foundation, Inc. This file is part of the GNU MP Library. @@ -30,7 +30,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" unsigned long int @@ -64,11 +63,11 @@ mpz_tdiv_r_ui (mpz_ptr rem, mpz_srcptr dividend, unsigned long int divisor) { rl = np[0]; SIZ(rem) = ns >= 0 ? 1 : -1; - PTR(rem)[0] = rl; + MPZ_NEWALLOC (rem, 1)[0] = rl; return rl; } - rp = MPZ_REALLOC (rem, 2); + rp = MPZ_NEWALLOC (rem, 2); TMP_MARK; dp[0] = divisor & GMP_NUMB_MASK; @@ -88,10 +87,8 @@ mpz_tdiv_r_ui (mpz_ptr rem, mpz_srcptr dividend, unsigned long int divisor) SIZ(rem) = 0; else { - /* Store the single-limb remainder. We don't check if there's space - for just one limb, since no function ever makes zero space. */ SIZ(rem) = ns >= 0 ? 1 : -1; - PTR(rem)[0] = rl; + MPZ_NEWALLOC (rem, 1)[0] = rl; } } diff --git a/Build/source/libs/gmp/gmp-src/mpz/tdiv_ui.c b/Build/source/libs/gmp/gmp-src/mpz/tdiv_ui.c index 328d67fdf88..4618599d8ff 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/tdiv_ui.c +++ b/Build/source/libs/gmp/gmp-src/mpz/tdiv_ui.c @@ -29,7 +29,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" #include "longlong.h" diff --git a/Build/source/libs/gmp/gmp-src/mpz/tstbit.c b/Build/source/libs/gmp/gmp-src/mpz/tstbit.c index db3d75a64f9..48725d45e6f 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/tstbit.c +++ b/Build/source/libs/gmp/gmp-src/mpz/tstbit.c @@ -28,7 +28,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" diff --git a/Build/source/libs/gmp/gmp-src/mpz/ui_pow_ui.c b/Build/source/libs/gmp/gmp-src/mpz/ui_pow_ui.c index a4f23c56555..87f2d3a762b 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/ui_pow_ui.c +++ b/Build/source/libs/gmp/gmp-src/mpz/ui_pow_ui.c @@ -28,7 +28,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" diff --git a/Build/source/libs/gmp/gmp-src/mpz/ui_sub.c b/Build/source/libs/gmp/gmp-src/mpz/ui_sub.c index 579a3007954..1d0edb9372b 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/ui_sub.c +++ b/Build/source/libs/gmp/gmp-src/mpz/ui_sub.c @@ -1,6 +1,6 @@ /* mpz_ui_sub -- Subtract an unsigned one-word integer and an mpz_t. -Copyright 2002, 2004 Free Software Foundation, Inc. +Copyright 2002, 2004, 2015 Free Software Foundation, Inc. This file is part of the GNU MP Library. @@ -28,7 +28,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" void @@ -52,11 +51,8 @@ mpz_ui_sub (mpz_ptr w, unsigned long int uval, mpz_srcptr v) } #endif - vp = PTR(v); vn = SIZ(v); - wp = PTR(w); - if (vn > 1) { wp = MPZ_REALLOC (w, vn); @@ -64,24 +60,22 @@ mpz_ui_sub (mpz_ptr w, unsigned long int uval, mpz_srcptr v) mpn_sub_1 (wp, vp, vn, (mp_limb_t) uval); wn = -(vn - (wp[vn - 1] == 0)); } - else if (vn == 1) + else if (vn >= 0) { - if (uval >= vp[0]) + mp_limb_t vp0; + vp0 = PTR (v)[0] & - (mp_limb_t) vn; + wp = MPZ_NEWALLOC (w, 1); + if (uval >= vp0) { - wp[0] = uval - vp[0]; + wp[0] = uval - vp0; wn = wp[0] != 0; } else { - wp[0] = vp[0] - uval; + wp[0] = vp0 - uval; wn = -1; } } - else if (vn == 0) - { - wp[0] = uval; - wn = uval != 0; - } else /* (vn < 0) */ { vn = -vn; diff --git a/Build/source/libs/gmp/gmp-src/mpz/urandomb.c b/Build/source/libs/gmp/gmp-src/mpz/urandomb.c index f1295699b3f..fcaea218859 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/urandomb.c +++ b/Build/source/libs/gmp/gmp-src/mpz/urandomb.c @@ -30,7 +30,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" void diff --git a/Build/source/libs/gmp/gmp-src/mpz/urandomm.c b/Build/source/libs/gmp/gmp-src/mpz/urandomm.c index 434359cdd76..df73935d2e1 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/urandomm.c +++ b/Build/source/libs/gmp/gmp-src/mpz/urandomm.c @@ -2,7 +2,7 @@ integer in the range 0 to N-1, using STATE as the random state previously initialized by a call to gmp_randinit(). -Copyright 2000, 2002, 2012 Free Software Foundation, Inc. +Copyright 2000, 2002, 2012, 2015 Free Software Foundation, Inc. This file is part of the GNU MP Library. @@ -30,7 +30,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" #include "longlong.h" /* for count_leading_zeros */ @@ -40,8 +39,9 @@ see https://www.gnu.org/licenses/. */ void mpz_urandomm (mpz_ptr rop, gmp_randstate_t rstate, mpz_srcptr n) { - mp_ptr rp, np, nlast; + mp_ptr rp, np; mp_size_t nbits, size; + mp_limb_t nh; int count; int pow2; int cmp; @@ -51,19 +51,13 @@ mpz_urandomm (mpz_ptr rop, gmp_randstate_t rstate, mpz_srcptr n) if (UNLIKELY (size == 0)) DIVIDE_BY_ZERO; - nlast = &PTR (n)[size - 1]; + np = PTR (n); + nh = np[size - 1]; /* Detect whether n is a power of 2. */ - pow2 = POW2_P (*nlast); - if (pow2 != 0) - for (np = PTR (n); np < nlast; np++) - if (*np != 0) - { - pow2 = 0; /* Mark n as `not a power of two'. */ - break; - } - - count_leading_zeros (count, *nlast); + pow2 = POW2_P (nh) && (size == 1 || mpn_zero_p (np, size - 1)); + + count_leading_zeros (count, nh); nbits = size * GMP_NUMB_BITS - (count - GMP_NAIL_BITS) - pow2; if (nbits == 0) /* nbits == 0 means that n was == 1. */ { @@ -72,7 +66,6 @@ mpz_urandomm (mpz_ptr rop, gmp_randstate_t rstate, mpz_srcptr n) } TMP_MARK; - np = PTR (n); if (rop == n) { mp_ptr tp; @@ -83,7 +76,7 @@ mpz_urandomm (mpz_ptr rop, gmp_randstate_t rstate, mpz_srcptr n) /* Here the allocated size can be one too much if n is a power of (2^GMP_NUMB_BITS) but it's convenient for using mpn_cmp below. */ - rp = MPZ_REALLOC (rop, size); + rp = MPZ_NEWALLOC (rop, size); /* Clear last limb to prevent the case in which size is one too much. */ rp[size - 1] = 0; diff --git a/Build/source/libs/gmp/gmp-src/mpz/xor.c b/Build/source/libs/gmp/gmp-src/mpz/xor.c index cd701000d56..5ec657a5227 100644 --- a/Build/source/libs/gmp/gmp-src/mpz/xor.c +++ b/Build/source/libs/gmp/gmp-src/mpz/xor.c @@ -1,7 +1,7 @@ /* mpz_xor -- Logical xor. -Copyright 1991, 1993, 1994, 1996, 1997, 2000, 2001, 2005, 2012 Free Software -Foundation, Inc. +Copyright 1991, 1993, 1994, 1996, 1997, 2000, 2001, 2005, 2012, +2015-2018 Free Software Foundation, Inc. This file is part of the GNU MP Library. @@ -29,7 +29,6 @@ You should have received copies of the GNU General Public License and the GNU Lesser General Public License along with the GNU MP Library. If not, see https://www.gnu.org/licenses/. */ -#include "gmp.h" #include "gmp-impl.h" void @@ -38,70 +37,45 @@ mpz_xor (mpz_ptr res, mpz_srcptr op1, mpz_srcptr op2) mp_srcptr op1_ptr, op2_ptr; mp_size_t op1_size, op2_size; mp_ptr res_ptr; - mp_size_t res_size, res_alloc; - TMP_DECL; + mp_size_t res_size; - TMP_MARK; op1_size = SIZ(op1); op2_size = SIZ(op2); + if (op1_size < op2_size) + { + MPZ_SRCPTR_SWAP (op1, op2); + MP_SIZE_T_SWAP (op1_size, op2_size); + } + op1_ptr = PTR(op1); - op2_ptr = PTR(op2); res_ptr = PTR(res); - if (op1_size >= 0) + if (op2_size >= 0) { - if (op2_size >= 0) - { - if (op1_size >= op2_size) - { - if (ALLOC(res) < op1_size) - { - _mpz_realloc (res, op1_size); - /* No overlapping possible: op1_ptr = PTR(op1); */ - op2_ptr = PTR(op2); - res_ptr = PTR(res); - } - - if (res_ptr != op1_ptr) - MPN_COPY (res_ptr + op2_size, op1_ptr + op2_size, - op1_size - op2_size); - if (LIKELY (op2_size != 0)) - mpn_xor_n (res_ptr, op1_ptr, op2_ptr, op2_size); - res_size = op1_size; - } - else - { - if (ALLOC(res) < op2_size) - { - _mpz_realloc (res, op2_size); - op1_ptr = PTR(op1); - /* No overlapping possible: op2_ptr = PTR(op2); */ - res_ptr = PTR(res); - } - - if (res_ptr != op2_ptr) - MPN_COPY (res_ptr + op1_size, op2_ptr + op1_size, - op2_size - op1_size); - if (LIKELY (op1_size != 0)) - mpn_xor_n (res_ptr, op1_ptr, op2_ptr, op1_size); - res_size = op2_size; - } - - MPN_NORMALIZE (res_ptr, res_size); - SIZ(res) = res_size; - return; - } - else /* op2_size < 0 */ + if (res_ptr != op1_ptr) { - /* Fall through to the code at the end of the function. */ + res_ptr = MPZ_REALLOC (res, op1_size); + MPN_COPY (res_ptr + op2_size, op1_ptr + op2_size, + op1_size - op2_size); } + if (LIKELY (op2_size != 0)) + mpn_xor_n (res_ptr, op1_ptr, PTR(op2), op2_size); + res_size = op1_size; + + MPN_NORMALIZE (res_ptr, res_size); + SIZ(res) = res_size; } else { - if (op2_size < 0) + mp_ptr opx; + TMP_DECL; + + op2_size = -op2_size; + TMP_MARK; + if (op1_size < 0) { - mp_ptr opx, opy; + mp_ptr opy; /* Both operands are negative, the result will be positive. (-OP1) ^ (-OP2) = @@ -109,7 +83,6 @@ mpz_xor (mpz_ptr res, mpz_srcptr op1, mpz_srcptr op2) = (OP1 - 1) ^ (OP2 - 1) */ op1_size = -op1_size; - op2_size = -op2_size; /* Possible optimization: Decrease mpn_sub precision, as we won't use the entire res of both. */ @@ -117,78 +90,57 @@ mpz_xor (mpz_ptr res, mpz_srcptr op1, mpz_srcptr op2) mpn_sub_1 (opx, op1_ptr, op1_size, (mp_limb_t) 1); op1_ptr = opx; - mpn_sub_1 (opy, op2_ptr, op2_size, (mp_limb_t) 1); + mpn_sub_1 (opy, PTR(op2), op2_size, (mp_limb_t) 1); op2_ptr = opy; - if (op1_size > op2_size) - MPN_SRCPTR_SWAP (op1_ptr,op1_size, op2_ptr,op2_size); - - res_alloc = op2_size; - res_ptr = MPZ_REALLOC (res, res_alloc); + res_ptr = MPZ_NEWALLOC (res, op2_size); + /* Don't re-read OP1_PTR and OP2_PTR. They point to temporary + space--never to the space PTR(res) used to point to before + reallocation. */ MPN_COPY (res_ptr + op1_size, op2_ptr + op1_size, op2_size - op1_size); mpn_xor_n (res_ptr, op1_ptr, op2_ptr, op1_size); + TMP_FREE; res_size = op2_size; MPN_NORMALIZE (res_ptr, res_size); SIZ(res) = res_size; - TMP_FREE; - return; } else { - /* We should compute -OP1 ^ OP2. Swap OP1 and OP2 and fall - through to the code that handles OP1 ^ -OP2. */ - MPZ_SRCPTR_SWAP (op1, op2); - MPN_SRCPTR_SWAP (op1_ptr,op1_size, op2_ptr,op2_size); - } - } + /* Operand 2 negative, so will be the result. + -(OP1 ^ (-OP2)) = -(OP1 ^ ~(OP2 - 1)) = + = ~(OP1 ^ ~(OP2 - 1)) + 1 = + = (OP1 ^ (OP2 - 1)) + 1 */ - { - mp_ptr opx; - mp_limb_t cy; - - /* Operand 2 negative, so will be the result. - -(OP1 ^ (-OP2)) = -(OP1 ^ ~(OP2 - 1)) = - = ~(OP1 ^ ~(OP2 - 1)) + 1 = - = (OP1 ^ (OP2 - 1)) + 1 */ - - op2_size = -op2_size; - - opx = TMP_ALLOC_LIMBS (op2_size); - mpn_sub_1 (opx, op2_ptr, op2_size, (mp_limb_t) 1); - op2_ptr = opx; - - res_alloc = MAX (op1_size, op2_size) + 1; - if (ALLOC(res) < res_alloc) - { - _mpz_realloc (res, res_alloc); - op1_ptr = PTR(op1); - /* op2_ptr points to temporary space. */ - res_ptr = PTR(res); - } - - if (op1_size > op2_size) - { - MPN_COPY (res_ptr + op2_size, op1_ptr + op2_size, op1_size - op2_size); - mpn_xor_n (res_ptr, op1_ptr, op2_ptr, op2_size); - res_size = op1_size; - } - else - { - MPN_COPY (res_ptr + op1_size, op2_ptr + op1_size, op2_size - op1_size); - if (LIKELY (op1_size != 0)) - mpn_xor_n (res_ptr, op1_ptr, op2_ptr, op1_size); - res_size = op2_size; - } + res_size = MAX (op1_size, op2_size); + res_ptr = MPZ_REALLOC (res, res_size + 1); + op1_ptr = PTR(op1); - cy = mpn_add_1 (res_ptr, res_ptr, res_size, (mp_limb_t) 1); - res_ptr[res_size] = cy; - res_size += (cy != 0); + opx = TMP_ALLOC_LIMBS (op2_size); + mpn_sub_1 (opx, PTR(op2), op2_size, (mp_limb_t) 1); + op2_ptr = opx; - MPN_NORMALIZE (res_ptr, res_size); - SIZ(res) = -res_size; - TMP_FREE; - } + if (res_size == op1_size) + { + MPN_COPY (res_ptr + op2_size, op1_ptr + op2_size, op1_size - op2_size); + mpn_xor_n (res_ptr, op1_ptr, op2_ptr, op2_size); + } + else + { + MPN_COPY (res_ptr + op1_size, op2_ptr + op1_size, op2_size - op1_size); + if (LIKELY (op1_size != 0)) + mpn_xor_n (res_ptr, op1_ptr, op2_ptr, op1_size); + } + TMP_FREE; + + res_ptr[res_size] = 0; + MPN_INCR_U (res_ptr, res_size + 1, (mp_limb_t) 1); + res_size += res_ptr[res_size]; + + MPN_NORMALIZE_NOT_ZERO (res_ptr, res_size); + SIZ(res) = -res_size; + } + } } |