[Gmp-commit] /home/hgfiles/gmp: (mpz_jacobi): Fixed off-by-one error in use o...

[mercurial at gmplib.org]

details:   /home/hgfiles/gmp/rev/cd9a8ad08a26
changeset: 13626:cd9a8ad08a26
user:      Niels M?ller <nisse at lysator.liu.se>
date:      Wed May 12 22:03:22 2010 +0200
description:
(mpz_jacobi): Fixed off-by-one error in use of scratch space.

diffstat:

 ChangeLog    |   3 +++
 mpz/jacobi.c |  11 ++++++++---
 2 files changed, 11 insertions(+), 3 deletions(-)

diffs (45 lines):

diff -r 6353b0d82503 -r cd9a8ad08a26 ChangeLog
--- a/ChangeLog	Wed May 12 21:04:57 2010 +0200
+++ b/ChangeLog	Wed May 12 22:03:22 2010 +0200
@@ -1,5 +1,8 @@
 2010-05-12  Niels Möller  <nisse at lysator.liu.se>
 
+	* mpz/jacobi.c (mpz_jacobi): Fixed off-by-one error in use of
+	scratch space.
+
 	* tune/common.c (speed_mpz_powm_sec): New function.
 	* tune/speed.h: Declare speed_mpz_powm_sec.
 	* tune/speed.c (routine): Added speed_mpz_powm_sec.
diff -r 6353b0d82503 -r cd9a8ad08a26 mpz/jacobi.c
--- a/mpz/jacobi.c	Wed May 12 21:04:57 2010 +0200
+++ b/mpz/jacobi.c	Wed May 12 22:03:22 2010 +0200
@@ -188,13 +188,18 @@
       if (btwos > 0)
 	{
 	  /* Result size: 2*bsize, extra: asize - bsize + 1 for
-	     quotient, total: asize + bsize + 1 */
+	     quotient, total: asize + bsize + 1. */
 	  ASSERT (atwos == 0);
 
 	  ASSERT_NOCARRY (mpn_rshift (bp, bsrcp, bsize, btwos));
 	  bsize -= bp[bsize-1] == 0;
 
-	  mpn_tdiv_qr (scratch, ap, 0, asrcp, asize, bp, bsize);
+	  /* Note that if the shift eliminated the most significant
+	     limb of b, the quotient gets one limb larger, but the
+	     total storage needed for b and the quotient is unchanged.
+	     To get sufficient space, we put the quotient at bp +
+	     bsize rather than at scratch. */
+	  mpn_tdiv_qr (bp + bsize, ap, 0, asrcp, asize, bp, bsize);
 	}
       else
 	{
@@ -202,7 +207,7 @@
 	    {
 	      /* Result size: bsize, extra: (asize - bsize) + (asize -
 		 bsize + 1) for shifted value, and quotient, total: 2
-		 asize - bsize + 1 */
+		 asize - bsize + 1. */
 	      ASSERT_NOCARRY (mpn_rshift (ap, asrcp, asize, atwos));
 	      mpn_tdiv_qr (ap + asize, ap, 0, ap, asize, bsrcp, bsize);
 	    }