Bug #4248
closed
r30483 might cause underflow
Description
=begin
Hi, matz (or Ray Chason) --
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 [email protected]
=end
Updated by matz (Yukihiro Matsumoto) over 14 years ago
=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 [email protected] 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
Updated by mame (Yusuke Endoh) over 14 years ago
- Status changed from Open to Rejected
=begin
Hi,
2011/1/8 Yukihiro Matsumoto [email protected]:
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 [email protected]
=end