From: Yusuke Endoh <redmine@...>
Date: 2011-01-07T21:21:00+09:00
Subject: [ruby-core:34218] [Ruby 1.9-Bug#4248][Open] r30483 might cause underflow

Bug #4248: r30483 might cause underflow
http://redmine.ruby-lang.org/issues/show/4248

Author: Yusuke Endoh
Status: Open, Priority: Normal
ruby -v: ruby 1.9.3dev (2011-01-07 trunk 30456) [i686-linux] 

Hi, matz (or Ray Chason) --

http://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=rev&revision=30483

> Author: matz
> Date: Fri Jan 7 00:17:06 2011 UTC (9 hours, 45 minutes ago)
> Log Message:
> * bignum.c (bigmul1_karatsuba): avoid overflow that make assertion
>   fail in certain case.  this patch is contributed from Ray Chason
>   <chasonr at gmail.com> in personal communication.


I understand the possibility that zds may cause overflow, right?
Do you have the "certain case", or can you disclose the "personal
communication" ?
I suspect that this patch may cause t1's underflow instead of zds,
though it is difficult to create test case...
Anyway, the following patch is conservative, I think.

It may a good idea to consult ruby-core, especially, mrkn before
committing this kind of patch ;-)

# I can realize this commit thanks to ruby-trunk-changes:
# http://d.hatena.ne.jp/nagachika/20110107/ruby_trunk_changes_30480_30483


diff --git a/bignum.c b/bignum.c
index ede0de6..950222b 100644
--- a/bignum.c
+++ b/bignum.c
@@ -2104,7 +2104,7 @@ bigmul1_karatsuba(VALUE x, VALUE y)
      */
 
     /* allocate a result bignum */
-    z = bignew(xn + yn, RBIGNUM_SIGN(x)==RBIGNUM_SIGN(y));
+    z = bignew(xn + yn + 1, RBIGNUM_SIGN(x)==RBIGNUM_SIGN(y));
     zds = BDIGITS(z);
 
     /* t1 <- xh * yh */
@@ -2156,16 +2156,16 @@ bigmul1_karatsuba(VALUE x, VALUE y)
     /* t3 <- xh * yh */
     t3 = bigmul0(xh, yh);
 
-    i = xn + yn - n;
-    /* subtract t1 from t3 */
-    bigsub_core(BDIGITS(t3), big_real_len(t3), BDIGITS(t1), t1n, BDIGITS(t3), big_real_len(t3));
-
-    /* subtract t2 from t3; t3 is now the middle term of the product */
-    if (t2 != Qundef) bigsub_core(BDIGITS(t3), big_real_len(t3), BDIGITS(t2), t2n, BDIGITS(t3), big_real_len(t3));
-
+    i = xn + yn - n + 1;
     /* add t3 to middle bytes of the result (z1) */
     bigadd_core(zds + n, i, BDIGITS(t3), big_real_len(t3), zds + n, i);
 
+    /* subtract t1 from middle bytes of the result (z1) */
+    bigsub_core(zds + n, i, BDIGITS(t1), t1n, zds + n, i);
+
+    /* subtract t2 from middle bytes of the result (z1) */
+    if (t2 != Qundef) bigsub_core(zds + n, i, BDIGITS(t2), t2n, zds + n, i);
+
     return z;
 }
 
-- 
Yusuke Endoh <mame@tsg.ne.jp>


----------------------------------------
http://redmine.ruby-lang.org