From: Markus <markus@...>
Date: 2004-08-28T01:30:24+09:00
Subject: [PATCH] Subtle bug in bignum.c

All --

    I'm posting this here because ruby-core and the bug 
    form do not seem to be working for me.

          -- MQR


I have found a rather subtle bug in the bitwise operators defined in
bignum.c, caused, I believe, by uninitialized bits in the
RBIGNUM()->sign.  I have a patch which fixes the problem but, as with my
previous patches, someone cleverer than I am (hi Matz!) may have a much
better way of fixing it. 

TO DEMONSTRATE THE PROBLEM:

Run the following script.  It should produce no output (and occasionally
this is what happens).  But frequently, the values of a and b differ. 
This should not happen, but it does.  I have reproduced the problem on
several different machines, running several different flavors of linux. 

The fact that the problem doesn't occur all the time, or even every time
through the loop, and that the extent to which it occurs it can be
affected by running other programs to "rough up" memory between tests
led me to believe that it was an uninitializateion problem.

10.times {
    (0x10000..0x20000).each { |i|
        a = (i*-12345) & 0xFFFFFFFF
        b = (i*-12345) & 0xFFFFFFFF
        print "#{i.to_s(2)}  #{a.to_s(2)}  #{b.to_s(2)}\n" if a != b
        }
    }

A similar problem can b shown with bitwise-or


10.times {
    (0x10000..0x20000).each { |i|
        a = (i*-12345) | 0
        b = (i*-12345) | 0
        print "#{i.to_s(2)}  #{a.to_s(2)}  #{{b.to_s(2)}\n" if a != b
        }
    }


But the problem does NOT occur with bitwise-xor:

10.times {
    (0x10000..0x20000).each { |i|
        a = (i*-12345) ^ 0
        b = (i*-12345) ^ 0
        print "#{i.to_s(2)}  #{a.to_s(2)}  #{{b.to_s(2)}\n" if a != b
        }
    }


MY PATCH:

Looking at the code for the three bitwise ops, I noticed that xor
protected itself from RBIGNUM()->sign having values other than 0 or 1,
but the other ops did not.  So I tried this patch (copying code from the
bitwise-xor routine to bitwise-and and bitwise-or):

--- ruby-1.8.1.org/bignum.c	2003-12-22 02:25:49.000000000 -0700
+++ ruby-1.8.1/bignum.c	2004-08-25 11:33:08.000000000 -0700
@@ -1645,6 +1645,8 @@
 	ds2 = BDIGITS(y);
 	sign = RBIGNUM(x)->sign;
     }
+    RBIGNUM(x)->sign = RBIGNUM(x)->sign?1:0;
+    RBIGNUM(y)->sign = RBIGNUM(y)->sign?1:0;
     z = bignew(l2, RBIGNUM(x)->sign || RBIGNUM(y)->sign);
     zds = BDIGITS(z);
 
@@ -1701,6 +1703,8 @@
 	ds2 = BDIGITS(y);
 	sign = RBIGNUM(x)->sign;
     }
+    RBIGNUM(x)->sign = RBIGNUM(x)->sign?1:0;
+    RBIGNUM(y)->sign = RBIGNUM(y)->sign?1:0;
     z = bignew(l2, RBIGNUM(x)->sign && RBIGNUM(y)->sign);
     zds = BDIGITS(z);
 

This fixed the problem, at least in so far as the symptoms went away. 
It may fix it correctly, if everything else only looks at the lowest bit
of RBIGNUM()->sign, or it might be a false step if the real design
intent is for RBIGNUM()->sign to always be either 0 or 1.

In any case, someone more knowledgeable than I am in these matters
should look at it (someone who at least knows C?).  I have not, for
example, figured out why the || and && don't "mask away" the problem, as
I thought they were always supposed to return either 0 or 1--meaning
that it might be an optimizer problem.

I used GCC 3.2.2 & 3.3.2 when compiling ruby, from otherwise unmodified
1.8.1 sources.  I looked in CVS and saw no post 1.8.1 changes that
appeared relevant.
 
-- Markus (MQR) Roberts