[Gmp-commit] /home/hgfiles/gmp: New macro udiv_qr_3by2

[mercurial at gmplib.org]

details:   /home/hgfiles/gmp/rev/ba40eb1b4ff0
changeset: 13059:ba40eb1b4ff0
user:      Niels M?ller <nisse at lysator.liu.se>
date:      Sun Dec 13 22:23:34 2009 +0100
description:
New macro udiv_qr_3by2

diffstat:

 ChangeLog                  |   5 +++++
 gmp-impl.h                 |  33 +++++++++++++++++++++++++++++++++
 mpn/generic/sbpi1_div_qr.c |  29 ++---------------------------
 3 files changed, 40 insertions(+), 27 deletions(-)

diffs (101 lines):

diff -r 31471fab0deb -r ba40eb1b4ff0 ChangeLog
--- a/ChangeLog	Sun Dec 13 21:05:54 2009 +0100
+++ b/ChangeLog	Sun Dec 13 22:23:34 2009 +0100
@@ -1,3 +1,8 @@
+2009-12-13  Niels Möller  <nisse at lysator.liu.se>
+
+	* gmp-impl.h (udiv_qr_3by2): New macro.
+	* mpn/generic/sbpi1_div_qr.c (mpn_sbpi1_div_qr): Use udiv_qr_3by2.
+
 2009-12-13  Torbjorn Granlund  <tege at gmplib.org>
 
 	* mpn/generic/dcpi1_divappr_q.c (mpn_dcpi1_divappr_q): Avoid a buffer
diff -r 31471fab0deb -r ba40eb1b4ff0 gmp-impl.h
--- a/gmp-impl.h	Sun Dec 13 21:05:54 2009 +0100
+++ b/gmp-impl.h	Sun Dec 13 22:23:34 2009 +0100
@@ -2656,6 +2656,39 @@
     (r) = _r;								\
   } while (0)
 
+/* Compute quotient the quotient and remainder for n / d. Requires d
+   >= B^2 / 2 and n < d B. di is the inverse
+
+     floor ((B^3 - 1) / (d0 + d1 B)) - B.
+*/
+#define udiv_qr_3by2(q, r1, r0, n2, n1, n0, d1, d0, di)			\
+  do {									\
+    mp_limb_t _q1, _q0, _r1, _r0, _t1, _t0, _mask;			\
+    umul_ppmm (_q1, _q0, (n2), (dinv));					\
+    add_ssaaaa (_q1, _q0, _q1, _q0, (n2), (n1));			\
+									\
+    /* Compute the two most significant limbs of n - q'd */		\
+    _r1 = (n1) - _q1 * (d1);						\
+    sub_ddmmss (_r1, _r0, _r1, (n0), (d1), (d0));			\
+    umul_ppmm (_t1, _t0, _q1, (d0));					\
+    sub_ddmmss (_r1, _r0, _r1, _r0, _t1, _t0);				\
+    _q1++;								\
+									\
+    /* Conditionally adjust q and the remainders */			\
+    _mask = - (mp_limb_t) (_r1 >= _q0);					\
+    _q1 += _mask;							\
+    add_ssaaaa (_r1, _r0, _r1, _r0, _mask & (d1), _mask & (d0));	\
+    if (UNLIKELY (_r1 >= (d1)))						\
+      {									\
+	if (_r1 > (d1) || _r0 >= (d0))					\
+	  {								\
+	    _q1++;							\
+	    sub_ddmmss (_r1, _r0, _r1, _r0, (d1), (d0));		\
+	  }								\
+      }									\
+    (q) = _q1; (r1) = _r1; (r0) = _r0;					\
+  } while (0)
+
 #ifndef mpn_preinv_divrem_1  /* if not done with cpuvec in a fat binary */
 #define   mpn_preinv_divrem_1 __MPN(preinv_divrem_1)
 __GMP_DECLSPEC mp_limb_t mpn_preinv_divrem_1 __GMP_PROTO ((mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_limb_t, mp_limb_t, int));
diff -r 31471fab0deb -r ba40eb1b4ff0 mpn/generic/sbpi1_div_qr.c
--- a/mpn/generic/sbpi1_div_qr.c	Sun Dec 13 21:05:54 2009 +0100
+++ b/mpn/generic/sbpi1_div_qr.c	Sun Dec 13 22:23:34 2009 +0100
@@ -40,9 +40,7 @@
   mp_limb_t n1, n0;
   mp_limb_t d1, d0;
   mp_limb_t cy, cy1;
-  mp_limb_t q, q0;
-  mp_limb_t t1, t0;
-  mp_limb_t mask;
+  mp_limb_t q;
 
   ASSERT (dn > 2);
   ASSERT (nn >= dn);
@@ -76,30 +74,7 @@
 	}
       else
 	{
-	  umul_ppmm (q, q0, n1, dinv);
-	  add_ssaaaa (q, q0, q, q0, n1, np[1]);
-
-	  /* Compute the two most significant limbs of n - q'd */
-	  n1 = np[1] - d1 * q;
-	  n0 = np[0];
-	  sub_ddmmss (n1, n0, n1, n0, d1, d0);
-	  umul_ppmm (t1, t0, d0, q);
-	  sub_ddmmss (n1, n0, n1, n0, t1, t0);
-	  q++;
-
-	  /* Conditionally adjust q and the remainders */
-	  mask = - (mp_limb_t) (n1 >= q0);
-	  q += mask;
-	  add_ssaaaa (n1, n0, n1, n0, mask & d1, mask & d0);
-
-	  if (UNLIKELY (n1 >= d1))
-	    {
-	      if (n1 > d1 || n0 >= d0)
-		{
-		  q++;
-		  sub_ddmmss (n1, n0, n1, n0, d1, d0);
-		}
-	    }
+	  udiv_qr_3by2 (q, n1, n0, n1, np[1], np[0], d1, d0, dinv);
 
 	  cy = mpn_submul_1 (np - dn, dp, dn, q);