[Gmp-commit] /var/hg/gmp: 2 new changesets

[mercurial at gmplib.org]

details:   /var/hg/gmp/rev/427d4f079761
changeset: 17642:427d4f079761
user:      Niels M?ller <nisse at lysator.liu.se>
date:      Wed Jun 13 22:05:46 2018 +0200
description:
mpn_gcd_1: Delete unused code variant for GCD_1_METHOD == 1

And delete the GCD_1_METHOD macro too.

details:   /var/hg/gmp/rev/cdc397f6fa03
changeset: 17643:cdc397f6fa03
user:      Niels M?ller <nisse at lysator.liu.se>
date:      Wed Jun 13 23:04:39 2018 +0200
description:
mpn_gcd_1: Simplify the structure of the remaining code variant.

Delete gotos to the mid-loop strip_u_maybe label.

diffstat:

 ChangeLog           |    7 +++
 mpn/generic/gcd_1.c |  118 +++++++++++++++++++--------------------------------
 2 files changed, 52 insertions(+), 73 deletions(-)

diffs (172 lines):

diff -r 3f2c961bcc41 -r cdc397f6fa03 ChangeLog
--- a/ChangeLog	Sat Jun 02 00:25:48 2018 +0200
+++ b/ChangeLog	Wed Jun 13 23:04:39 2018 +0200
@@ -1,3 +1,10 @@
+2018-06-13  Niels Möller  <nisse at lysator.liu.se>
+
+	* mpn/generic/gcd_1.c (mpn_gcd_1): Delete unused code variant for
+	GCD_1_METHOD == 1, and delete GCD_1_METHOD macro. Simplify the
+	structure of the remaining code variant, without gotos to the
+	mid-loop strip_u_maybe label.
+
 2018-05-29  Torbjörn Granlund  <tg at gmplib.org>
 
 	* configure.ac (x86): Pass more exact arch/tune options for nehalem.
diff -r 3f2c961bcc41 -r cdc397f6fa03 mpn/generic/gcd_1.c
--- a/mpn/generic/gcd_1.c	Sat Jun 02 00:25:48 2018 +0200
+++ b/mpn/generic/gcd_1.c	Wed Jun 13 23:04:39 2018 +0200
@@ -31,10 +31,6 @@
 #include "gmp-impl.h"
 #include "longlong.h"
 
-#ifndef GCD_1_METHOD
-#define GCD_1_METHOD 2
-#endif
-
 /* Does not work for U == 0 or V == 0.  It would be tough to make it work for
    V == 0 since gcd(x,0) = x, and U does not generally fit in an mp_limb_t.
 
@@ -47,6 +43,7 @@
 {
   mp_limb_t      ulimb;
   unsigned long  zero_bits, u_low_zero_bits;
+  int c;
 
   ASSERT (size >= 1);
   ASSERT (vlimb != 0);
@@ -72,69 +69,47 @@
       if (ulimb == 0)
 	goto done;
 
-      goto strip_u_maybe;
+      count_trailing_zeros (c, ulimb);
+      ulimb = (ulimb >> 1) >> c;
+    }
+  else
+    {
+      /* size==1, so up[0]!=0 */
+      count_trailing_zeros (u_low_zero_bits, ulimb);
+      ulimb >>= u_low_zero_bits;
+      zero_bits = MIN (zero_bits, u_low_zero_bits);
+
+      /* make u bigger */
+      if (vlimb > ulimb)
+	MP_LIMB_T_SWAP (ulimb, vlimb);
+
+      /* if u is much bigger than v, reduce using a division rather than
+	 chipping away at it bit-by-bit */
+      if ((ulimb >> 16) > vlimb)
+	{
+	  ulimb %= vlimb;
+	  if (ulimb == 0)
+	    goto done;
+
+	  count_trailing_zeros (c, ulimb);
+	  ulimb = (ulimb >> 1) >> c;
+	}
+      else
+	{
+	  ASSERT (ulimb & 1);
+	  ulimb >>= 1;
+	}
     }
 
-  /* size==1, so up[0]!=0 */
-  count_trailing_zeros (u_low_zero_bits, ulimb);
-  ulimb >>= u_low_zero_bits;
-  zero_bits = MIN (zero_bits, u_low_zero_bits);
-
-  /* make u bigger */
-  if (vlimb > ulimb)
-    MP_LIMB_T_SWAP (ulimb, vlimb);
+  ASSERT (vlimb & 1);
+  vlimb >>= 1;
 
-  /* if u is much bigger than v, reduce using a division rather than
-     chipping away at it bit-by-bit */
-  if ((ulimb >> 16) > vlimb)
-    {
-      ulimb %= vlimb;
-      if (ulimb == 0)
-	goto done;
-      goto strip_u_maybe;
-    }
-
-  ASSERT (ulimb & 1);
-  ASSERT (vlimb & 1);
-
-#if GCD_1_METHOD == 1
+  /* In this loop, we represent the odd numbers ulimb and vlimb
+     without the redundant least significant one bit. This reduction
+     in size by one bit ensures that the high bit of t, below, is set
+     if and only if vlimb > ulimb. */
   while (ulimb != vlimb)
     {
-      ASSERT (ulimb & 1);
-      ASSERT (vlimb & 1);
-
-      if (ulimb > vlimb)
-	{
-	  ulimb -= vlimb;
-	  do
-	    {
-	      ulimb >>= 1;
-	      ASSERT (ulimb != 0);
-	    strip_u_maybe:
-	      ;
-	    }
-	  while ((ulimb & 1) == 0);
-	}
-      else /*  vlimb > ulimb.  */
-	{
-	  vlimb -= ulimb;
-	  do
-	    {
-	      vlimb >>= 1;
-	      ASSERT (vlimb != 0);
-	    }
-	  while ((vlimb & 1) == 0);
-	}
-    }
-#else
-# if GCD_1_METHOD  == 2
-
-  ulimb >>= 1;
-  vlimb >>= 1;
-
-  while (ulimb != vlimb)
-    {
-      int c;
       mp_limb_t t;
       mp_limb_t vgtu;
 
@@ -147,21 +122,18 @@
       /* u <-- |u - v| */
       ulimb = (t ^ vgtu) - vgtu;
 
-      if (0)
-	{
-	strip_u_maybe:
-	  vlimb >>= 1;
-	  t = ulimb;
-	}
       count_trailing_zeros (c, t);
-      ulimb = (ulimb >> c) >> 1;
+      /* We have c <= GMP_LIMB_BITS - 2 here, so that
+
+	   ulimb >>= (c + 1);
+
+	 would be safe. But unlike the addition c + 1, a separate
+	 shift by 1 is independent of c, and can be executed in
+	 parallel with count_trailing_zeros. */
+      ulimb = (ulimb >> 1) >> c;
     }
 
   vlimb = (vlimb << 1) | 1;
-# else
-#  error Unknown GCD_1_METHOD
-# endif
-#endif
 
  done:
   return vlimb << zero_bits;