Re: Good way to write integer overflow checks?
On 10/11/13 07:15, Alf P. Steinbach wrote:
On 10.11.2013 02:34, Sam wrote:
Alf P. Steinbach writes:
This code is in support of some API functionality:
[code]
inline
auto can_inflate( gdi::Rect const& r, int const dx, int const dy )
-> bool
{
CPPX_XASSERT( INT_MIN/2 < dx && dx < INT_MAX/2 );
CPPX_XASSERT( INT_MIN/2 < dy && dy < INT_MAX/2 );
typedef unsigned long Unsigned_long;
auto const msb = ULONG_MAX - (ULONG_MAX >> 1);
return
(r.left & msb) == ((Unsigned_long( r.left ) - dx) & msb) &&
(r.top & msb) == ((Unsigned_long( r.top ) - dy) & msb) &&
(r.right & msb) == ((Unsigned_long( r.right ) + dx) & msb) &&
(r.bottom & msb) == ((Unsigned_long( r.bottom ) + dy) & msb);
}
[/code]
Can this be written in an even gooder way, for bestest possible code?
Disclaimer: the code has not been tested or even called.
Yes, it can be. A more generic algorithm, for any signed int type:
template<typename signed_int_t>
signed_int_t add_with_overflow_check(signed_int_t a, signed_int_t b)
{
signed_int_t c=a+b;
if (b > 0)
{
if (c < a)
do_whatever_you_want_when_you_overflow();
}
else
{
if (c > a)
do_whatever_you_want_when_you_overflow();
}
return c;
}
Your C++ homework assignment consists of three parts:
1. Explain why the above code works
Hm, that's a tough one!
It is not "tough" - as you have noticed yourself, it does /not/ work.
I agree that something in this direction is how things ideally should
work, in part because I think that the optimizations that are enabled by
the formal signed overflow UB are both marginal, often radically
unexpected, and generally easy to achieve by more explicit means.
It does not matter what you think in this matter - it was established
long ago that you are wrong, and that neither C or C++ standards groups,
not compiler implementers, nor most developers follow your ideas here.
You are, of course, welcome to your opinions and can use "-fwrapv" if
you want - but it won't change the rest of the C++ world.
However, with the C++ standard as it is (as of C++11) this code is not
formally portable, and worse, it /should not be/ practically portable to
environments where "-ftrapv" is used with the g++ compiler.
The code is portable. It is undefined behaviour on all platforms.
(With some compilers, and some flag options, it happens to give a
particular type of behaviour - but /any/ behaviour is consistent with
/undefined/ behaviour.) As it stands, the code asks for nasal daemons -
it might happen to give a check for signed overflow in some
circumstances, but that's just luck.
So, I tried
your code with MinGW g++ 4.7.2, and the code appears to detect the
overflow even with the "-ftrapv" option specified, where the overflow
should be trapped. Apparently that is a COMPILER BUG. :-(
In the great majority of cases where people think they have found a
"COMPILER BUG", they are wrong. This is one of them. It is, IMHO, a
documentation "bug" - the gcc manual could be much clearer here.
The "-ftrapv" option does not stop signed overflow from being undefined
behaviour. This means that you are not guaranteed traps on overflows -
but you /might/ get them. It is dependent on many things, including the
types of optimisation, the target, the knowledge the compiler has (i.e.,
does it /know/ there is always an overflow, or never an overflow), etc.
At best, -ftrapv is a debugging aid - it can lead to significantly worse
code, but help spot some types of program error.
Oh, and "int(-1/2u)" is undefined behaviour.
[code]
#include <stdexcept>
void do_whatever_you_want_when_you_overflow()
{
throw std::runtime_error( "integer overflow");
}
template<typename signed_int_t>
signed_int_t add_with_overflow_check(signed_int_t a, signed_int_t b)
{
signed_int_t c=a+b;
if (b > 0)
{
if (c < a)
do_whatever_you_want_when_you_overflow();
}
else
{
if (c > a)
do_whatever_you_want_when_you_overflow();
}
return c;
}
#include <iostream>
#include <stdlib.h>
using namespace std;
auto main() -> int
{
try
{
int const x = add_with_overflow_check<int>( int(-1/2u), 1 );
cout << x << endl;
return EXIT_SUCCESS;
}
catch( exception const& x )
{
cerr << "!" << x.what() << endl;
}
catch( ... )
{
cerr << "!unknown exception." << endl;
}
return EXIT_FAILURE;
}
[/code]
[example]
[D:\dev\test]
version g++
g++ (GCC) 4.7.2
[D:\dev\test]
g++ foo.cpp -fno-wrapv -ftrapv
[D:\dev\test]
a
!integer overflow
[D:\dev\test]
_
[/code]
Apparently the lack of any trapping here means that MinGW g++ is
UNRELIABLE in this respect, i.e. that using "-ftrapv" with g++ is not a
reliable way to catch this kind of error (in the usual cases where the
overflow is an error, not intentional) in debug builds.
-ftrapv has never been "reliable" in this way - it is a debugging aid
sometimes, but that's all.
2. Implement a version for any unsigned int type
I'm sorry, but that question doesn't make much sense to me.
If you look at the code I posted originally, it shows one way to
leverage the well-defined'ness of unsigned arithmetic to detect overflow
reliably -- if not as elegant as I'd wished it to be, which is what I
asked about.
So, what's the problem there?
3. Use template specialization and std::numeric_limits to implement a
template that will work for any signed or unsigned int type
I think the apparent MinGW compiler bug for question (1) has to be dealt
with first, lest we get into compiler make and version sniffing. Then,
to make use of such a template practical, I think one would need
suitable integer wrapper types with no implicit narrowing, test suites
that demonstrate convincingly that this introduces no bugs and no added
inefficiency, and examples that demonstrate that one would not easily
use it incorrectly. This seems to be a pretty big effort?
Cheers,
- Alf