[Gmp-commit] /home/hgfiles/gmp: 2 new changesets

[mercurial at gmplib.org]

details:   /home/hgfiles/gmp/rev/ede8c55a4e05
changeset: 13329:ede8c55a4e05
user:      Marco Bodrato <bodrato at mail.dm.unipi.it>
date:      Wed Jan 06 09:24:02 2010 +0100
description:
Toom8: avoid mp_size_t overflow if used for huge operands.

details:   /home/hgfiles/gmp/rev/b18efb1708be
changeset: 13330:b18efb1708be
user:      Marco Bodrato <bodrato at mail.dm.unipi.it>
date:      Wed Jan 06 09:53:32 2010 +0100
description:
Changelog.

diffstat:

 ChangeLog                |   4 ++++
 mpn/generic/toom8h_mul.c |  29 ++++++++++++++++-------------
 2 files changed, 20 insertions(+), 13 deletions(-)

diffs (76 lines):

diff -r b3b1ce7d08fb -r b18efb1708be ChangeLog
--- a/ChangeLog	Wed Jan 06 05:07:16 2010 +0100
+++ b/ChangeLog	Wed Jan 06 09:53:32 2010 +0100
@@ -1,3 +1,7 @@
+2010-01-06 Marco Bodrato <bodrato at mail.dm.unipi.it>
+
+	* mpn/generic/toom8h_mul.c: Avoid overlflows of mp_size_t.
+
 2010-01-06  Torbjorn Granlund  <tege at gmplib.org>
 
 	* tests/mpn/t-div.c: Test mpn_div_q.
diff -r b3b1ce7d08fb -r b18efb1708be mpn/generic/toom8h_mul.c
--- a/mpn/generic/toom8h_mul.c	Wed Jan 06 05:07:16 2010 +0100
+++ b/mpn/generic/toom8h_mul.c	Wed Jan 06 09:53:32 2010 +0100
@@ -107,19 +107,22 @@
 
   /***************************** decomposition *******************************/
 
-  ASSERT( an >= bn );
+  ASSERT (an >= bn);
   /* Can not handle too small operands */
-  ASSERT( bn >= 86 );
-  /* FIXME: assert are estimated with GMP_NUMB_BITS==32 */
+  ASSERT (bn >= 86);
   /* Can not handle too much unbalancement */
-  ASSERT( an*5 <= bn*11 );
+  ASSERT (an*4 <= bn*13);
+  ASSERT (GMP_NUMB_BITS > 12*3 || an*4 <= bn*12);
+  ASSERT (GMP_NUMB_BITS > 11*3 || an*5 <= bn*11);
+  ASSERT (GMP_NUMB_BITS > 10*3 || an*6 <= bn*10);
+  ASSERT (GMP_NUMB_BITS >  9*3 || an*7 <= bn* 9);
 
   /* Limit num/den is a rational number between
      (16/15)^(log(6)/log(2*6-1)) and (16/15)^(log(8)/log(2*8-1))             */
 #define LIMIT_numerator (21)
 #define LIMIT_denominat (20)
 
-  if( LIKELY(an == bn) || an * LIMIT_denominat < LIMIT_numerator * bn ) /* is 8*... < 8*... */
+  if (LIKELY (an == bn) || an * (LIMIT_denominat>>1) < LIMIT_numerator * (bn>>1) ) /* is 8*... < 8*... */
     {
       half = 0;
       n = 1 + ((an - 1)>>3);
@@ -129,25 +132,25 @@
     }
   else
     {
-      if (an * 7 * LIMIT_numerator < LIMIT_denominat * 9 * bn)
+      if (an * 13 < 16 * bn) /* (an*7*LIMIT_numerator<LIMIT_denominat*9*bn) */
 	{ p = 9; q = 8; }
       else if (GMP_NUMB_BITS <= 9*3 ||
-	       an * 7 * LIMIT_denominat < LIMIT_numerator * 9 * bn)
+	       an *(LIMIT_denominat>>1) < (LIMIT_numerator/7*9) * (bn>>1))
 	{ p = 9; q = 7; }
-      else if (an * 3 * LIMIT_numerator < LIMIT_denominat * 5 * bn)
+      else if (an * 10 < 33 * (bn>>1)) /* (an*3*LIMIT_numerator<LIMIT_denominat*5*bn) */
 	{ p =10; q = 7; }
       else if (GMP_NUMB_BITS <= 10*3 ||
-	       an * 3 * LIMIT_denominat < LIMIT_numerator * 5 * bn)
+	       an * (LIMIT_denominat/5) < (LIMIT_numerator/3) * bn)
 	{ p =10; q = 6; }
-      else if (an * 5 * LIMIT_numerator < LIMIT_denominat *11 * bn)
+      else if (an * 6 < 13 * bn) /*(an * 5 * LIMIT_numerator < LIMIT_denominat *11 * bn)*/
 	{ p =11; q = 6; }
       else if (GMP_NUMB_BITS <= 11*3 ||
-	       an * 5 * LIMIT_denominat < LIMIT_numerator *11 * bn)
+	       an * 4 < 9 * bn)
 	{ p =11; q = 5; }
-      else if (an * LIMIT_numerator < LIMIT_denominat * 3 * bn )  /* is 4*... <12*... */
+      else if (an *(LIMIT_numerator/3) < LIMIT_denominat * bn )  /* is 4*... <12*... */
 	{ p =12; q = 5; }
       else if (GMP_NUMB_BITS <= 12*3 ||
-	       an * LIMIT_denominat < LIMIT_numerator * 3 * bn )  /* is 4*... <12*... */
+	       an * 9 < 28 * bn )  /* is 4*... <12*... */
 	{ p =12; q = 4; }
       else
 	{ p =13; q = 4; }