[Gmp-commit] /var/hg/gmp: Rewrite tail of function, for n <= 2.

[mercurial at gmplib.org]

details:   /var/hg/gmp/rev/5e446d7c533c
changeset: 17887:5e446d7c533c
user:      Torbjorn Granlund <tg at gmplib.org>
date:      Mon Sep 09 23:38:45 2019 +0200
description:
Rewrite tail of function, for n <= 2.

diffstat:

 mpn/generic/gcd.c |  66 ++++++++++++++++++++++++++++++------------------------
 1 files changed, 37 insertions(+), 29 deletions(-)

diffs (85 lines):

diff -r cf5765234af8 -r 5e446d7c533c mpn/generic/gcd.c
--- a/mpn/generic/gcd.c	Sun Sep 08 21:55:22 2019 +0200
+++ b/mpn/generic/gcd.c	Mon Sep 09 23:38:45 2019 +0200
@@ -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.
@@ -217,37 +217,45 @@
 
   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;
-    }
+  ASSERT ((up[0] & 1) != 0);
 
   {
-    mp_double_limb_t g = mpn_gcd_22 (up[1], up[0], vp[1], vp[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);