From: "colinwb2 ." Date: 2013-07-02T00:21:40+09:00 Subject: [ruby-core:55740] numeric.c - fix_mul - comment on RubyCore[8825] and a recent patch by charliesome --089e01182deed9ab0e04e074c8a5 Content-Type: text/plain; charset=ISO-8859-1 I've just noticed this comment by charliesome on numeric.c on GitHub: * numeric.c (fix_mul): remove FIT_SQRT_LONG test as it was causing fix_mul to return an incorrect result for -2147483648*-2147483648 on 64 bit platforms * test/ruby/test_integer_comb.rb (class TestIntegerComb): add test case The following suggests an alternative to removing the FIT_SQRT_LONG test. The alternative preserves the original idea in post 8825 of being hopefully somewhat faster (on average), and should cure the overflow bug by deleting one character in the definition of FIT_SQRT_LONG. I was about to post a comment on http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-core/8825 saying it's a very late comment because I first saw post 8825 a few days ago, and that if I understand the intent of the code correctly, then either (1) the code has a bug, or (2) the code could be at least very very slightly improved. I couldn't test my suspicions because I don't have a 64bit platform, so I was going to post a suggestion on Ruby-Core for a test (explaining why), but charliesome's comment seems to confirm that there's a bug. Briefly, we needn't *remove* the FIT_SQRT_LONG test from fix_mul; we can just change the definition of FIT_SQRT_LONG from: #define FIT_SQRT_LONG(n) (((n)=-SQRT_LONG_MAX)) to #define FIT_SQRT_LONG(n) (((n)-SQRT_LONG_MAX)) which preserves the original idea in post 8825 of being hopefully somewhat faster (on average), but which should cure the bug. I think that's all that really needs to be said for now. (Perhaps except that I found post 8825 because about a year ago I found and patched some integer overflow issues in JRuby, for example http://jira.codehaus.org/browse/JRUBY-6612 making some tests specifically for those patches, and about two weeks ago I thought about (and started) devising more general tests to try to detect any "likely" integer overflow problems. As part of that I had a look at fix_mul in numeric.c.) ***** ***** ***** ***** ***** But for completeness, and to make it easier to follow why the change to FIT_SQRT_LONG should work (I'm afraid I can't test it myself), a short explanation follows. (Relevant excerpts from numeric.c are at the end of this post.) Suppose we are using a Ruby for which the following is *not* true: #if SIZEOF_LONG * 2 <= SIZEOF_LONG_LONG Consider these two lines immediately after the "#else" after that: if (FIT_SQRT_LONG(a) && FIT_SQRT_LONG(b)) return LONG2FIX(a*b); (A) Suppose x = y = SQRT_LONG_MAX; if I understand the code correctly then for these (identical) values it's saying that x * y may overflow Fixnums, so use Bignum#*. (B) Suppose x = y = -SQRT_LONG_MAX; if I understand the code correctly then for these (identical) values it's saying that x * y will definitely not overflow Fixnums, so use ordinary C integer multiplication and return the result as a Fixnum. But both (A) and (B) should be returning the same value. So there are two possibilities for the FIT_SQRT_LONG check: (A) the positive integer check in it can be relaxed at least a little; or (B) the negative integer check in it should be more stringent. (From charliesome's comment it seems it's (B) that applies.) Part of the latest version of fix_mul in numeric.c is now: #else if (a == 0) return x; if (MUL_OVERFLOW_FIXNUM_P(a, b)) r = rb_big_mul(rb_int2big(a), rb_int2big(b)); else r = LONG2FIX(a * b); return r; #endif But with the proposed change to FIT_SQRT_LONG it can be changed back to the hopefully somewhat faster (on average): #else if (FIT_SQRT_LONG(a) && FIT_SQRT_LONG(b)) return LONG2FIX(a*b); if (a == 0) return x; if (MUL_OVERFLOW_FIXNUM_P(a, b)) r = rb_big_mul(rb_int2big(a), rb_int2big(b)); else r = LONG2FIX(a * b); return r; #endif ***** Extracts from a very recent version of numeric.c at about line 2700: ... #define SQRT_LONG_MAX ((SIGNED_VALUE)1<<((SIZEOF_LONG*CHAR_BIT-1)/2)) /*tests if N*N would overflow*/ #define FIT_SQRT_LONG(n) (((n)=-SQRT_LONG_MAX)) ... fix_mul(VALUE x, VALUE y) { if (FIXNUM_P(y)) { ... long a, b; ... a = FIX2LONG(x); b = FIX2LONG(y); #if SIZEOF_LONG * 2 <= SIZEOF_LONG_LONG d = (LONG_LONG)a * b; if (FIXABLE(d)) return LONG2FIX(d); return rb_ll2inum(d); #else if (FIT_SQRT_LONG(a) && FIT_SQRT_LONG(b)) return LONG2FIX(a*b); if (a == 0) return x; if (MUL_OVERFLOW_FIXNUM_P(a, b)) r = rb_big_mul(rb_int2big(a), rb_int2big(b)); else r = LONG2FIX(a * b); return r; #endif ... } --089e01182deed9ab0e04e074c8a5 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable I've just noticed this comment by charliesome on numeric.c on GitHub:
* numeric.c (fix_mul): remove FIT_SQRT_LONG test as it was causing fix_mul to return an incorrect result for -2147483648*-2147483648
=A0 = on 64 bit platforms
* test/ruby/test_integer_comb.rb (class TestIntegerComb): add test case
=
The following suggests an alternative to removing the FIT_SQRT_LONG te= st.
The alternative preserves the original idea in post 8825 of being hopefully somewhat faster (on average), and should cure the overflow bugby deleting one character in the definition of FIT_SQRT_LONG.

I wa= s about to post a comment on
http://blade.nagaokaut.ac.jp/cgi-bin/scat= .rb/ruby/ruby-core/8825

saying it's a very late comment because I first saw post 8825 a few= days ago,
and that if I understand the intent of the code correctly, th= en
either (1) the code has a bug,
or (2) the code could be at least v= ery very slightly improved.

I couldn't test my suspicions because I don't have a 64bit plat= form,
so I was going to post a suggestion on Ruby-Core for a test (expla= ining why),
but charliesome's comment seems to confirm that there= 9;s a bug.

Briefly, we needn't *remove* the FIT_SQRT_LONG test from fix_mul;we can just change the definition of FIT_SQRT_LONG from:
#define FIT_S= QRT_LONG(n) (((n)<SQRT_LONG_MAX)&&((n)>=3D-SQRT_LONG_MAX)) to
#define FIT_SQRT_LONG(n) (((n)<SQRT_LONG_MAX)&&((n)>-SQ= RT_LONG_MAX))

which preserves the original idea in post 8825 of bein= g hopefully
somewhat faster (on average), but which should cure the bug= .

I think that's all that really needs to be said for now.

(Pe= rhaps except that I found post 8825 because about a year ago
I found an= d patched some integer overflow issues in JRuby, for example
http://jira.codehaus.org/browse= /JRUBY-6612
making some tests specifically for those patches, and about two weeks agoI thought about (and started) devising more general tests to try
to de= tect any "likely" integer overflow problems.
As part of that I= had a look at fix_mul in numeric.c.)


***** ***** ***** ***** *****
But for completeness, and to make = it easier to follow why the change
to FIT_SQRT_LONG should work (I'm= afraid I can't test it myself),
a short explanation follows.
(Relevant excerpts from numeric.c are at the end of this post.)

Supp= ose we are using a Ruby for which the following is *not* true:
#if SIZEO= F_LONG * 2 <=3D SIZEOF_LONG_LONG

Consider these two lines immedia= tely after the "#else" after that:
=A0=A0=A0 if (FIT_SQRT_LONG(a) && FIT_SQRT_LONG(b))
=A0=A0=A0 = =A0=A0=A0 return LONG2FIX(a*b);

(A) Suppose x =3D y =3D SQRT_LONG_MA= X; if I understand the code correctly
then for these (identical) values = it's saying that
x * y may overflow Fixnums, so use Bignum#*.

(B) Suppose x =3D y =3D= -SQRT_LONG_MAX; if I understand the code correctly
then for these (iden= tical) values it's saying that
x * y will definitely not overflow Fi= xnums,
so use ordinary C integer multiplication and return the result as a Fixnum.=

But both (A) and (B) should be returning the same value.
So ther= e are two possibilities for the FIT_SQRT_LONG check:
(A) the positive in= teger check in it can be relaxed at least a little;
or (B) the negative integer check in it should be more stringent.
(From = charliesome's comment it seems it's (B) that applies.)

Part = of the latest version of fix_mul in numeric.c is now:
#else
=A0=A0=A0= if (a =3D=3D 0) return x;
=A0=A0=A0=A0=A0=A0=A0 if (MUL_OVERFLOW_FIXNUM_P(a, b))
=A0=A0=A0 =A0=A0= =A0 r =3D rb_big_mul(rb_int2big(a), rb_int2big(b));
=A0=A0=A0=A0=A0=A0= =A0 else
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 r =3D LONG2FIX(a * b);
=A0= =A0=A0 return r;
#endif

But with the proposed change to FIT_SQRT_= LONG it can be changed back to
the hopefully somewhat faster (on average):
#else
=A0=A0=A0 if (FIT_S= QRT_LONG(a) && FIT_SQRT_LONG(b))
=A0=A0=A0 =A0=A0=A0 return LONG= 2FIX(a*b);
=A0=A0=A0 if (a =3D=3D 0) return x;
=A0=A0=A0=A0=A0=A0=A0 = if (MUL_OVERFLOW_FIXNUM_P(a, b))
=A0=A0=A0 =A0=A0=A0 r =3D rb_big_mul(rb= _int2big(a), rb_int2big(b));
=A0=A0=A0=A0=A0=A0=A0 else
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 r =3D LONG2= FIX(a * b);
=A0=A0=A0 return r;
#endif


***** Extracts from= a very recent version of numeric.c at about line 2700:
...
#define S= QRT_LONG_MAX ((SIGNED_VALUE)1<<((SIZEOF_LONG*CHAR_BIT-1)/2))
/*tests if N*N would overflow*/
#define FIT_SQRT_LONG(n) (((n)<SQRT_L= ONG_MAX)&&((n)>=3D-SQRT_LONG_MAX))
...
fix_mul(VALUE x, VA= LUE y)
{
=A0=A0=A0 if (FIXNUM_P(y)) {
...
=A0=A0=A0 long a, b;<= br>...
=A0=A0=A0 a =3D FIX2LONG(x);
=A0=A0=A0 b =3D FIX2LONG(y);

#if SIZ= EOF_LONG * 2 <=3D SIZEOF_LONG_LONG
=A0=A0=A0 d =3D (LONG_LONG)a * b;<= br>=A0=A0=A0 if (FIXABLE(d)) return LONG2FIX(d);
=A0=A0=A0 return rb_ll2= inum(d);
#else
=A0=A0=A0 if (FIT_SQRT_LONG(a) && FIT_SQRT_LON= G(b))
=A0=A0=A0 =A0=A0=A0 return LONG2FIX(a*b);
=A0=A0=A0 if (a =3D=3D 0) retu= rn x;
=A0=A0=A0=A0=A0=A0=A0 if (MUL_OVERFLOW_FIXNUM_P(a, b))
=A0=A0= =A0 =A0=A0=A0 r =3D rb_big_mul(rb_int2big(a), rb_int2big(b));
=A0=A0=A0= =A0=A0=A0=A0 else
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 r =3D LONG2FIX(a * b= );
=A0=A0=A0 return r;
#endif
...
}


--089e01182deed9ab0e04e074c8a5--