From 178c482e12c00111c9a45fd569cc871d11358e5b Mon Sep 17 00:00:00 2001 From: Karl Berry Date: Sat, 19 Oct 2024 07:07:02 -0700 Subject: [PATCH] autoupdate --- lib/mini-gmp.c | 95 ++++++++++++++++++++++++++++++++------------------ lib/mini-gmp.h | 1 + 2 files changed, 63 insertions(+), 33 deletions(-) diff --git a/lib/mini-gmp.c b/lib/mini-gmp.c index c580a8fc02..c97dc7e6cf 100644 --- a/lib/mini-gmp.c +++ b/lib/mini-gmp.c @@ -2706,6 +2706,66 @@ mpn_gcd_11 (mp_limb_t u, mp_limb_t v) return u << shift; } +mp_size_t +mpn_gcd (mp_ptr rp, mp_ptr up, mp_size_t un, mp_ptr vp, mp_size_t vn) +{ + assert (un >= vn); + assert (vn > 0); + assert (!GMP_MPN_OVERLAP_P (up, un, vp, vn)); + assert (vp[vn-1] > 0); + assert ((up[0] | vp[0]) & 1); + + if (un > vn) + mpn_div_qr (NULL, up, un, vp, vn); + + un = mpn_normalized_size (up, vn); + if (un == 0) + { + mpn_copyi (rp, vp, vn); + return vn; + } + + if (!(vp[0] & 1)) + MPN_PTR_SWAP (up, un, vp, vn); + + while (un > 1 || vn > 1) + { + int shift; + assert (vp[0] & 1); + + while (up[0] == 0) + { + up++; + un--; + } + gmp_ctz (shift, up[0]); + if (shift > 0) + { + gmp_assert_nocarry (mpn_rshift(up, up, un, shift)); + un -= (up[un-1] == 0); + } + + if (un < vn) + MPN_PTR_SWAP (up, un, vp, vn); + else if (un == vn) + { + int c = mpn_cmp (up, vp, un); + if (c == 0) + { + mpn_copyi (rp, up, un); + return un; + } + else if (c < 0) + MP_PTR_SWAP (up, vp); + } + + gmp_assert_nocarry (mpn_sub (up, up, un, vp, vn)); + un = mpn_normalized_size (up, un); + } + rp[0] = mpn_gcd_11 (up[0], vp[0]); + return 1; +} + unsigned long mpz_gcd_ui (mpz_t g, const mpz_t u, unsigned long v) { @@ -2765,42 +2825,11 @@ mpz_gcd (mpz_t g, const mpz_t u, const mpz_t v) if (tu->_mp_size < tv->_mp_size) mpz_swap (tu, tv); - mpz_tdiv_r (tu, tu, tv); - if (tu->_mp_size == 0) - { - mpz_swap (g, tv); - } - else - for (;;) - { - int c; - - mpz_make_odd (tu); - c = mpz_cmp (tu, tv); - if (c == 0) - { - mpz_swap (g, tu); - break; - } - if (c < 0) - mpz_swap (tu, tv); + tu->_mp_size = mpn_gcd (tu->_mp_d, tu->_mp_d, tu->_mp_size, tv->_mp_d, tv->_mp_size); + mpz_mul_2exp (g, tu, gz); - if (tv->_mp_size == 1) - { - mp_limb_t *gp; - - mpz_tdiv_r (tu, tu, tv); - gp = MPZ_REALLOC (g, 1); /* gp = mpz_limbs_modify (g, 1); */ - *gp = mpn_gcd_11 (tu->_mp_d[0], tv->_mp_d[0]); - - g->_mp_size = *gp != 0; /* mpz_limbs_finish (g, 1); */ - break; - } - mpz_sub (tu, tu, tv); - } mpz_clear (tu); mpz_clear (tv); - mpz_mul_2exp (g, g, gz); } void diff --git a/lib/mini-gmp.h b/lib/mini-gmp.h index 59c24cf511..f28cb360ce 100644 --- a/lib/mini-gmp.h +++ b/lib/mini-gmp.h @@ -105,6 +105,7 @@ void mpn_mul_n (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t); void mpn_sqr (mp_ptr, mp_srcptr, mp_size_t); int mpn_perfect_square_p (mp_srcptr, mp_size_t); mp_size_t mpn_sqrtrem (mp_ptr, mp_ptr, mp_srcptr, mp_size_t); +mp_size_t mpn_gcd (mp_ptr, mp_ptr, mp_size_t, mp_ptr, mp_size_t); mp_limb_t mpn_lshift (mp_ptr, mp_srcptr, mp_size_t, unsigned int); mp_limb_t mpn_rshift (mp_ptr, mp_srcptr, mp_size_t, unsigned int); -- 2.39.5