Bug #4248: r30483 might cause underflow

• Status: Rejected
• Assignee: -
• Target version: -
• ruby -v: ruby 1.9.3dev (2011-01-07 trunk 30456) [i686-linux]

[mame (Yusuke Endoh)]

=begin
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
  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 [e-mail]
=end

[matz (Yukihiro Matsumoto)]

=begin
Hi,

In message "Re: [ruby-core:34218] [Ruby 1.9-Bug#4248][Open] r30483 might cause underflow"
on Fri, 7 Jan 2011 21:21:00 +0900, Yusuke Endoh [e-mail] writes:

|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
|> 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" ?

The following is the problem case given from Ray:

def mul(len)
x = (1<<len) - 1
y = (1<<len) - 1
return x * y
end
puts '%X' % mul(2240)

=end

[mame (Yusuke Endoh)]

• Status changed from Open to Rejected

=begin
Hi,

2011/1/8 Yukihiro Matsumoto [e-mail]:

The following is the problem case given from Ray:

def mul(len)
x = (1<<len) - 1
y = (1<<len) - 1
return x * y
end
puts '%X' % mul(2240)

Thank you. I'll add a test case based on the code.

And, my suspicion was wrong; mrkn noted me that the patch does NOT
cause underflow since t3 = (xh+xl)(yh+yl) >= xhyh + xl*yl = t1 + t2.
So I'm withdrawing this ticket. Sorry.

--
Yusuke Endoh [e-mail]
=end