id,summary,reporter,owner,description,type,status,milestone,component,version,severity,resolution,keywords,cc
650,Invalid code used for add w/ overflow checking,nobody,jmaurer,"{{{
Discovered while working on our (Microsoft) C++ 
compiler:

This is an e-mail thread about the bug we ran into.  
The current Microsoft VC++ compiler does not causes 
this to return incorrect values, but there is no 
guarantee that this will be the case in the future as 
we produce better optimizations.

If you need to contact me about this, my e-mail is 
alex.thaman@microsoft.com.

> FYI - this bug exists in at least versions of boost 
>= 1.27.0 
> (including the current one).  Please see below for 
details.  It's a 
> little unclear to us what the purpose of this 
function is, but it 
> appears to be doing a signed add and handling 
overflow conditions, but 
> it's doing to overflow detection incorrectly.
>
> Thanks,
> -Alex Thaman (Microsoft)
>
> _____________________________________________
> From: Russell Hadley
> Sent: Friday, June 09, 2006 3:00 PM
> To: Alex Thaman; Arjun Bijanki; Andy Rich
> Subject: RE: boost bug
>
> Just a slight spin on this: For the current boost 
sources we aren't 
> making a transformation in the compiler which 
exposes the reliance on 
> signed arithmetic overflow/underflow - this was 
exposed in an older 
> version - but potentially we could. It is a much 
safer practice to 
> test the ranges of the inputs to an arithmetic 
expression if there is 
> a danger of overflow rather than the output.  The 
compiler can 
> potentially reorder any signed integer arithmetic 
(algebraically) with 
> out respect for signed overflow/underflow so 
outputs have undefined 
> semantics for that case.  (off the cuff ex: cast 
the inputs to 
> unsigned and check their ranges.)
>
> Thanks.
>
> -R
>
> _____________________________________________
> From: Alex Thaman
> Sent: Friday, June 09, 2006 1:53 PM
> To: Arjun Bijanki
> Cc: Russell Hadley
> Subject: boost bug
>
> We ran into a bug in boost.  In
> conformance\3rdPartyLibs\boost_1_2*_0
\boost\random\detail\const_mod.hp
> p, there is a function called add_signed (do_add in 
version > 1.27.0).  
> It has the following code:
>
>   template<>
>   struct do_add<true>
>   {
>     template<class IntType>
>     static IntType add(IntType m, IntType x, 
IntType c)
>     {
>       x += (c-m);
>       if(x < 0)
>         x += m;
>       return x;
>     }
>   };
>
> The problem is that it is relying on an overflow in 
their logic to 
> calculate the correct value.  This is undefined in 
most cases, and the 
> optimizer does some logic here by calculating 
intermediate values and 
> using them and avoiding the overflow that this test 
is expecting.  It 
> is pretty clear that they depend on overflow 
behavior if you just do a 
> quick refactor of this code:
>
> If (x + (c - m) < 0) return x + c
> Else return x + c - m
>
> Thanks,
> -Alex

}}}",Bugs,closed,,random,None,Showstopper,Fixed,,