[ruby-core:55740] numeric.c - fix_mul - comment on RubyCore[8825] and a recent patch by charliesome

[ruby-core:55740] numeric.c - fix_mul - comment on RubyCore[8825] and a recent patch by charliesome

[colinwb2 .]

[-- Attachment #1: Type: text/plain, Size: 4657 bytes --]

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)&&((n)>=-SQRT_LONG_MAX))
to
#define FIT_SQRT_LONG(n) (((n)<SQRT_LONG_MAX)&&((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)&&((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
...
}

[-- Attachment #2: Type: text/html, Size: 5387 bytes --]