[Gmp-commit] /home/hgfiles/gmp: (mpn_mulmod_bnm1): Fixed non-recursive case t...

[mercurial at gmplib.org]

details:   /home/hgfiles/gmp/rev/4cd499b57d36
changeset: 13021:4cd499b57d36
user:      Niels M?ller <nisse at lysator.liu.se>
date:      Thu Dec 10 13:16:39 2009 +0100
description:
(mpn_mulmod_bnm1): Fixed non-recursive case to not write beyond end of result area.

diffstat:

 ChangeLog                 |   5 +++++
 mpn/generic/mulmod_bnm1.c |  31 ++++++++++++++++++-------------
 2 files changed, 23 insertions(+), 13 deletions(-)

diffs (55 lines):

diff -r 6dafd7951ee5 -r 4cd499b57d36 ChangeLog
--- a/ChangeLog	Wed Dec 09 22:57:02 2009 +0100
+++ b/ChangeLog	Thu Dec 10 13:16:39 2009 +0100
@@ -1,3 +1,8 @@
+2009-12-10  Niels Möller  <nisse at lysator.liu.se>
+
+	* mpn/generic/mulmod_bnm1.c (mpn_mulmod_bnm1): Fixed non-recursive
+	case to not write beyond end of result area.
+
 2009-12-09  Torbjorn Granlund  <tege at gmplib.org>
 
 	* tune/speed.h (SPEED_ROUTINE_MPN_MULMOD_BNM1_CALL): New macro, made
diff -r 6dafd7951ee5 -r 4cd499b57d36 mpn/generic/mulmod_bnm1.c
--- a/mpn/generic/mulmod_bnm1.c	Wed Dec 09 22:57:02 2009 +0100
+++ b/mpn/generic/mulmod_bnm1.c	Thu Dec 10 13:16:39 2009 +0100
@@ -93,21 +93,26 @@
 
   if ((rn & 1) != 0 || BELOW_THRESHOLD (rn, MULMOD_BNM1_THRESHOLD))
     {
-      if (UNLIKELY (bn < rn)) /* May happen only for misuse or _very_
-				 unbalanced operands */
+      /* FIXME: We depend on an >= bn, this should be an official
+	 requirement. */
+      ASSERT (bn <= an);
+      if (UNLIKELY (bn < rn))
 	{
-	  MPN_COPY (tp, bp, bn);
-	  MPN_ZERO (tp + bn, rn - bn);
-	  bp = tp;
+	  if (UNLIKELY (an + bn <= rn))
+	    {
+	      mpn_mul (rp, ap, an, bp, bn);
+	      MPN_ZERO (rp + an + bn, rn - (an + bn));
+	    }
+	  else
+	    {
+	      mp_limb_t cy;
+	      mpn_mul (tp, ap, an, bp, bn);
+	      cy = mpn_add (rp, tp, rn, tp + rn, an + bn - rn);
+	      MPN_INCR_U (rp, rn, cy);
+	    }
 	}
-      ASSERT (ALLOW_MISUSE || (an >= rn) );
-      if (ALLOW_MISUSE && UNLIKELY (an < rn) )
-	{
-	  MPN_COPY (tp + rn, ap, an);
-	  MPN_ZERO (tp + rn + an, rn - an);
-	  ap = tp + rn;
-	}
-      mpn_bc_mulmod_bnm1 (rp, ap, bp, rn, rp);
+      else
+	mpn_bc_mulmod_bnm1 (rp, ap, bp, rn, tp);
     }
   else
     {