Unix Programming - Detecting under/over flow

Author

Detecting under/over flow

pocmatos@gmail.com

2006-06-11, 1:27 pm

Hi all,

What the best way to detect under/over flow in a program with a lot of
computations?

For example:
#include <iostream>
#include <limits>

using namespace std;

int main() {

int max = std::numeric_limits<int>::max();
int overflow = max + 1;

cout << "initial: " << max << endl << "overflow: " << overflow <<
endl;

return 0;

}

This silently outputs (even by compiling with -Wall using g++):
$ ./overflow
initial: 2147483647
overflow: -2147483648

The nice thing would be to have something like an exception thrown when
this happens since after an overflow, a program which makes use of a
lot of computations is useless after that.

Any ideas on how to detecting these and underflows? (I'm interested
also in non-portable solutions if you know about any)

Thanks,

Paulo Matos

Pascal Bourguignon

2006-06-11, 1:27 pm

pocmatos@gmail.com writes:

> Hi all,
>
> What the best way to detect under/over flow in a program with a lot of
> computations?
>
> For example:
> #include <iostream>
> #include <limits>
>
> using namespace std;
>
> int main() {
>
> int max = std::numeric_limits<int>::max();
> int overflow = max + 1;
>
> cout << "initial: " << max << endl << "overflow: " << overflow <<
> endl;
>
> return 0;
>
> }
>
> This silently outputs (even by compiling with -Wall using g++):
> $ ./overflow
> initial: 2147483647
> overflow: -2147483648
>
> The nice thing would be to have something like an exception thrown when
> this happens since after an overflow, a program which makes use of a
> lot of computations is useless after that.
>
> Any ideas on how to detecting these and underflows? (I'm interested
> also in non-portable solutions if you know about any)

This is not in the C standard. That is, it depends on the compiler
you're using. If by chance, you're using gcc, then you can use this
option:

-ftrapv
This option generates traps for signed overflow on addition,
subtraction, multiplication operations.

There are also options for floating-point overflows; man gcc

--
__Pascal Bourguignon__ http://www.informatimago.com/

"Klingon function calls do not have "parameters" -- they have
"arguments" and they ALWAYS WIN THEM."

Måns Rullgård

2006-06-11, 1:27 pm

Pascal Bourguignon <pjb@informatimago.com> writes:

> pocmatos@gmail.com writes:
>

[...]
[vbcol=seagreen]
>
> This is not in the C standard. That is, it depends on the compiler
> you're using. If by chance, you're using gcc, then you can use this
> option:
>
> -ftrapv
> This option generates traps for signed overflow on addition,
> subtraction, multiplication operations.
>
> There are also options for floating-point overflows; man gcc

Better to design the code such that overflows are not a problem in the
first place. It is likely to run much faster that way.

--
Måns Rullgård
mru@inprovide.com

pocmatos@gmail.com

2006-06-11, 1:27 pm

M=E5ns Rullg=E5rd escreveu:

> Pascal Bourguignon <pjb@informatimago.com> writes:
>
>
> [...]
>
>
> Better to design the code such that overflows are not a problem in the
> first place.

Problem is that in my case overflows don't depend on me. In the
simplest case if I design a calculator which reads from standard input
and user enters 231231290312 + 123123123, you'll surely get an
overflow. Only way out is to check the input and make sure it cannot
overflow. This means in C++ designing a new int type which overloads +,
-, etc and check for overflows on input. This is problematic.

> It is likely to run much faster that way.
>

Faster than using ftrapv and friend options?

> --=20
> M=E5ns Rullg=E5rd
> mru@inprovide.com

dfeustel@mindspring.com

2006-06-11, 1:27 pm

In comp.unix.programmer pocmatos@gmail.com wrote:
> Hi all,
>
> What the best way to detect under/over flow in a program with a lot of
> computations?

In the absence of automatic exceptions being thrown when overflow occurs,
how about using arbitrary precision arithmetic libraries so there are no
overflows?
--
Using OpenBSD with(out) ( X | KDE )?
See Dave's OpenBSD | X | KDE corner at
http://dfeustel.home.mindspring.com !!!

Pascal Bourguignon

2006-06-11, 1:27 pm

pocmatos@gmail.com writes:
> Problem is that in my case overflows don't depend on me. In the
> simplest case if I design a calculator which reads from standard input
> and user enters 231231290312 + 123123123, you'll surely get an
> overflow. Only way out is to check the input and make sure it cannot
> overflow. This means in C++ designing a new int type which overloads +,
> -, etc and check for overflows on input. This is problematic.

This enters the user input validation domain.

You can write methods such as:
validate(operation,operand-1,operand-2)

for example, for + with minimum<0<maximum:

validate(+,a,b) is
// check that minimum<=a+b<=maximum
if a<0 and b<0 then
// a+b<0 ==> a+b<=maximum
// minimum<=a+b <=> minimum-b<=a
if minimum-b>a then will_underflow
else if a>=0 and b>=0 then
// a+b>=0 ==> minimum<=a+b
// a+b<=maximum <=> b<=maximum-a
if b>maximum-a then will_overflow
else if (a<0 and b>=0) or (a>=0 and b<0) then
// minimum<=a<=maximum and minimum<=b<=maximum
// ==> minimum<=a+b<=maximum
// but if a and b could be out of bounds to start with, then you could
// add tests here to ensure the sum is inside the bounds.
fi

>
> Faster than using ftrapv and friend options?

Depends on how trapv is implemented. On 680x0, there's a TRAPV
microinstruction, so the only cost is one more op fetch per arithmetic
operation. It seems that on ix86, gcc -ftrapv generates a function
call, and is more complex, so yes, it would probably be faster to
inline the above tests.

--
__Pascal Bourguignon__ http://www.informatimago.com/

NEW GRAND UNIFIED THEORY DISCLAIMER: The manufacturer may
technically be entitled to claim that this product is
ten-dimensional. However, the consumer is reminded that this
confers no legal rights above and beyond those applicable to
three-dimensional objects, since the seven new dimensions are
"rolled up" into such a small "area" that they cannot be
detected.

Giorgos Keramidas

2006-06-11, 7:19 pm

On 11 Jun 2006 06:28:18 -0700, pocmatos@gmail.com wrote:
> Hi all,
>
> What the best way to detect under/over flow in a program with a
> lot of computations?

Prevent it from happening?

> For example:
> #include <iostream>
> #include <limits>
>
> using namespace std;
>
> int main() {
>
> int max = std::numeric_limits<int>::max();
> int overflow = max + 1;
>
> cout << "initial: " << max << endl <<
> "overflow: " << overflow << endl;
>
> return 0;
>
> }
>
> This silently outputs (even by compiling with -Wall using g++):
> $ ./overflow
> initial: 2147483647
> overflow: -2147483648

I usually check when two numbers `a' and `b' are added, like this:

if (INT_MAX - a < b) {
overflow;
}
a += b;

This way, you can detect the overflow before it happens. In your
case `a' is `overflow' and `b' is 1, so this could be written as:

int overflow = std::numeric_limits<int>::max();
int more = 1;

if (std::numeric_limits<int>::max() - more < overflow)
cerr "Overflowed" << endl;
overflow += more;

Giorgos Keramidas

2006-06-11, 7:19 pm

On 11 Jun 2006 09:59:37 -0700, pocmatos@gmail.com wrote:
> Måns Rullgård escreveu:
>
> Problem is that in my case overflows don't depend on me. In the
> simplest case if I design a calculator which reads from standard input
> and user enters 231231290312 + 123123123, you'll surely get an
> overflow. Only way out is to check the input and make sure it cannot
> overflow. This means in C++ designing a new int type which overloads
> +, -, etc and check for overflows on input. This is problematic.

You shouldn't be using `int' as the base type of a calculator anyway.

There are far better alternatives, which are less likely to cause
problems like overflows. For example, the GMP library:

http://www.swox.com/gmp/

dfeustel@mindspring.com

2006-06-11, 7:19 pm

pocmatos@gmail.com wrote:
> Problem is that in my case overflows don't depend on me. In the
> simplest case if I design a calculator which reads from standard input
> and user enters 231231290312 + 123123123, you'll surely get an
> overflow. Only way out is to check the input and make sure it cannot
> overflow. This means in C++ designing a new int type which overloads +,
> -, etc and check for overflows on input. This is problematic.

If a calculator is what you need, check out calc which has arbitrary
precision arithmetic.
--
Using OpenBSD with(out) ( X | KDE )?
See Dave's OpenBSD | X | KDE corner at
http://dfeustel.home.mindspring.com !!!

u.int.32.t@gmail.com

2006-06-12, 1:25 pm

Giorgos Keramidas wrote:
> I usually check when two numbers `a' and `b' are added, like this:
>
> if (INT_MAX - a < b) {
> overflow;
> }
> a += b;

Thats gonna be some seriously slow code.

Kai-Uwe Bux

2006-06-12, 7:23 pm

u.int.32.t@gmail.com wrote:

>
> Giorgos Keramidas wrote:
>
> Thats gonna be some seriously slow code.

And if a is negative, it has undefined behavior. If you want it to be
correct in all cases, it's going to be much slower.

Best

Kai-Uwe Bux

Brian Raiter

2006-06-12, 7:23 pm

>> if (INT_MAX - a < b) {
>
> Thats gonna be some seriously slow code.

Still, a wrong answer is only marginally improved by being provided quickly.

b

Måns Rullgård

2006-06-12, 7:23 pm

Brian Raiter <breadbox@muppetlabs.com> writes:

>
> Still, a wrong answer is only marginally improved by being provided
> quickly.

True. However, in this particular case, the correct solution is not
always in finding a way to detect the overflow, but to prevent it from
happening in the first place. Then no check will be required, and the
answer will both arrive quickly and be correct. In many cases
involving overflowing arithmetic, simply performing the operations in
a different order is all that is required. Other times, clever use of
known limits to the range of input values can be the solution.

--
Måns Rullgård
mru@inprovide.com

SM Ryan

2006-06-13, 1:31 am

=?iso-8859-1?Q?M=E5ns_Rullg=E5rd?= <mru@inprovide.com> wrote:
# Brian Raiter <breadbox@muppetlabs.com> writes:
#
# >>> if (INT_MAX - a < b) {
# >>> overflow;
# >>> }
# >>> a += b;
# >>
# >> Thats gonna be some seriously slow code.
# >
# > Still, a wrong answer is only marginally improved by being provided
# > quickly.
#
# True. However, in this particular case, the correct solution is not
# always in finding a way to detect the overflow, but to prevent it from
# happening in the first place. Then no check will be required, and the

If the CPU has an overflow flag, use that. If C or whatever
doesn't make an overflow flag visible, change the compiler.

--
SM Ryan http://www.rawbw.com/~wyrmwif/
OOOOOOOOOO! NAVY SEALS!