[boost] boost::random overflow bug

From: Samuel Krempp (krempp_at_[hidden])
Date: 2004-08-23 14:07:19

while checking uniform_int.hpp, I spotted 2 weirdnesses in uniform_int.hpp
that almost cancel themselves out, but not to the point that a contrived
example is impossible.

The heart of the problem is this loop :

while(mult <= limit) {
    result += (eng() - bmin) * mult;
    mult *= result_type(brange)+result_type(1); // <-- overflow possible
}

where limit = (range+1)/(brange+1)  
the multiplication is almost always guaranteed not to overflow (that was the
motivation to write the loop that way, I guess), except when 
mult==limit (which is reached when range+1 is a power of brange+1)
in that case, the last multiplication assigns (range+1) to mult.

And range+1 might in fact overflow.

Now, it turns out in cases where range+1 overflows, limit is computed with
special anti-overflow code, and there 's a bizarre condition there that
looks like a bug :
if(_range % result_type(brange)+1 == result_type(brange))
      ++limit;

instead of expected
if(_range % result_type(brange+1) == result_type(brange+1))
      ++limit;

so in the end, most of the time when range==max, limit is assigned the
value :
range/(brange+1) 
instead of (range+1)/(brange+1). So it cancels out the first bug most of the
time (maybe that is the reason for the bizarre code).

but the limit will still be equal to (range+1)/(brange+1) for brange=1 (I'm
not sure how useful a coin-flipper generator would be, but we never
know..), and mult can then be made to wrap and reach 0 in the previous
loop, which loops forever.

I've attached a compilable exemple and suggested patch.
I've thought it over carefully, the patch works in all situations.
after the test on (mult==limit), it's all safe since mult is guaranteed to
be > limit, and thus 
_range/mult will still be < brange+1, so the recursive call at the end is
safe.

-- 
Samuel