summaryrefslogtreecommitdiff
path: root/Build/source/libs/gmp/gmp-src/mpn/generic/gcd.c
diff options
context:
space:
mode:
Diffstat (limited to 'Build/source/libs/gmp/gmp-src/mpn/generic/gcd.c')
-rw-r--r--Build/source/libs/gmp/gmp-src/mpn/generic/gcd.c130
1 files changed, 43 insertions, 87 deletions
diff --git a/Build/source/libs/gmp/gmp-src/mpn/generic/gcd.c b/Build/source/libs/gmp/gmp-src/mpn/generic/gcd.c
index b14e1ad888f..3f92cbf0d1f 100644
--- a/Build/source/libs/gmp/gmp-src/mpn/generic/gcd.c
+++ b/Build/source/libs/gmp/gmp-src/mpn/generic/gcd.c
@@ -1,6 +1,6 @@
/* mpn/gcd.c: mpn_gcd for gcd of two odd integers.
-Copyright 1991, 1993-1998, 2000-2005, 2008, 2010, 2012 Free Software
+Copyright 1991, 1993-1998, 2000-2005, 2008, 2010, 2012, 2019 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"
@@ -77,61 +76,6 @@ gcd_hook (void *p, mp_srcptr gp, mp_size_t gn,
ctx->gn = gn;
}
-#if GMP_NAIL_BITS > 0
-/* Nail supports should be easy, replacing the sub_ddmmss with nails
- * logic. */
-#error Nails not supported.
-#endif
-
-/* Use binary algorithm to compute G <-- GCD (U, V) for usize, vsize == 2.
- Both U and V must be odd. */
-static inline mp_size_t
-gcd_2 (mp_ptr gp, mp_srcptr up, mp_srcptr vp)
-{
- mp_limb_t u0, u1, v0, v1;
- mp_size_t gn;
-
- u0 = up[0];
- u1 = up[1];
- v0 = vp[0];
- v1 = vp[1];
-
- ASSERT (u0 & 1);
- ASSERT (v0 & 1);
-
- /* Check for u0 != v0 needed to ensure that argument to
- * count_trailing_zeros is non-zero. */
- while (u1 != v1 && u0 != v0)
- {
- unsigned long int r;
- if (u1 > v1)
- {
- sub_ddmmss (u1, u0, u1, u0, v1, v0);
- count_trailing_zeros (r, u0);
- u0 = ((u1 << (GMP_NUMB_BITS - r)) & GMP_NUMB_MASK) | (u0 >> r);
- u1 >>= r;
- }
- else /* u1 < v1. */
- {
- sub_ddmmss (v1, v0, v1, v0, u1, u0);
- count_trailing_zeros (r, v0);
- v0 = ((v1 << (GMP_NUMB_BITS - r)) & GMP_NUMB_MASK) | (v0 >> r);
- v1 >>= r;
- }
- }
-
- gp[0] = u0, gp[1] = u1, gn = 1 + (u1 != 0);
-
- /* If U == V == GCD, done. Otherwise, compute GCD (V, |U - V|). */
- if (u1 == v1 && u0 == v0)
- return gn;
-
- v0 = (u0 == v0) ? ((u1 > v1) ? u1-v1 : v1-u1) : ((u0 > v0) ? u0-v0 : v0-u0);
- gp[0] = mpn_gcd_1 (gp, gn, v0);
-
- return 1;
-}
-
mp_size_t
mpn_gcd (mp_ptr gp, mp_ptr up, mp_size_t usize, mp_ptr vp, mp_size_t n)
{
@@ -273,37 +217,49 @@ mpn_gcd (mp_ptr gp, mp_ptr up, mp_size_t usize, mp_ptr vp, mp_size_t n)
ASSERT(up[n-1] | vp[n-1]);
- if (n == 1)
- {
- *gp = mpn_gcd_1(up, 1, vp[0]);
- ctx.gn = 1;
- goto done;
- }
-
- /* Due to the calling convention for mpn_gcd, at most one can be
- even. */
-
- if (! (up[0] & 1))
+ /* Due to the calling convention for mpn_gcd, at most one can be even. */
+ if ((up[0] & 1) == 0)
MP_PTR_SWAP (up, vp);
-
- ASSERT (up[0] & 1);
-
- if (vp[0] == 0)
- {
- *gp = mpn_gcd_1 (up, 2, vp[1]);
- ctx.gn = 1;
- goto done;
- }
- else if (! (vp[0] & 1))
- {
- int r;
- count_trailing_zeros (r, vp[0]);
- vp[0] = ((vp[1] << (GMP_NUMB_BITS - r)) & GMP_NUMB_MASK) | (vp[0] >> r);
- vp[1] >>= r;
- }
-
- ctx.gn = gcd_2(gp, up, vp);
-
+ ASSERT ((up[0] & 1) != 0);
+
+ {
+ mp_limb_t u0, u1, v0, v1;
+ mp_double_limb_t g;
+
+ u0 = up[0];
+ v0 = vp[0];
+
+ if (n == 1)
+ {
+ int cnt;
+ count_trailing_zeros (cnt, v0);
+ *gp = mpn_gcd_11 (u0, v0 >> cnt);
+ ctx.gn = 1;
+ goto done;
+ }
+
+ v1 = vp[1];
+ if (UNLIKELY (v0 == 0))
+ {
+ v0 = v1;
+ v1 = 0;
+ /* FIXME: We could invoke a mpn_gcd_21 here, just like mpn_gcd_22 could
+ when this situation occurs internally. */
+ }
+ if ((v0 & 1) == 0)
+ {
+ int cnt;
+ count_trailing_zeros (cnt, v0);
+ v0 = ((v1 << (GMP_NUMB_BITS - cnt)) & GMP_NUMB_MASK) | (v0 >> cnt);
+ v1 >>= cnt;
+ }
+
+ u1 = up[1];
+ g = mpn_gcd_22 (u1, u0, v1, v0);
+ gp[0] = g.d0;
+ gp[1] = g.d1;
+ ctx.gn = 1 + (g.d1 > 0);
+ }
done:
TMP_FREE;
return ctx.gn;