detecting integer overflow

[junky_fellow@yahoo.co.in]

Is there any way by which the overflow during addition of two integers
may
be detected ?

eg.

suppose we have three unsigned integers, a ,b, c.
we are doing a check like
if ((a +b) > c)
do something;
else
do something else.

If addition of a and b genearates overflow, the check may fail even if
a + b is larger than c.
How can we avoid such conditions from failure ?

Thanx in advance for any help ....

[Chris Williams]

Re: detecting integer overflow

junky_fellow@ya hoo.co.in wrote:[color=blue]
> Is there any way by which the overflow during addition of two integers
> may
> be detected ?[/color]

By the standard, I would personally guess that the state of an
overflown integer is undefined. On most PCs though I would imagine that
the result will always be less than the lower of the two values
added--which would be a way to test.

if ((c = (a + b)) > (a < b ? a : b)) {
....
}
else { /* overflowed! */
....
}

I'm just saying this off the top of my head, and you shouldn't trust it
until you've tested throroughly though.

[Saif]

Re: detecting integer overflow

junky_fellow@ya hoo.co.in wrote:[color=blue]
> Is there any way by which the overflow during addition of two integers
> may
> be detected ?
>
> eg.
>
> suppose we have three unsigned integers, a ,b, c.
> we are doing a check like
> if ((a +b) > c)
> do something;
> else
> do something else.
>
> If addition of a and b genearates overflow, the check may fail even if
> a + b is larger than c.
> How can we avoid such conditions from failure ?[/color]

If the intention is just to avoid a situation like the one mentioned, a
quick approach could be to promote the type of the variables from int
to double or float just inside the comparison by using an explicit
typecast.

if (((double)a+b) > c)
do something;
else
do something else;

Of course a float can overflow too, but it is not likely to happen when
two or more integers are added.

[Anand]

Re: detecting integer overflow

junky_fellow@ya hoo.co.in wrote:[color=blue]
> Is there any way by which the overflow during addition of two integers
> may
> be detected ?
>
> eg.
>
> suppose we have three unsigned integers, a ,b, c.
> we are doing a check like
> if ((a +b) > c)
> do something;
> else
> do something else.
>
> If addition of a and b genearates overflow, the check may fail even if
> a + b is larger than c.
> How can we avoid such conditions from failure ?
>
> Thanx in advance for any help ....
>[/color]
Most of the PCs I've worked with wraps the integer (so you could test it
for wrapping around.) But the standard clearly states that integer
overflow is an UB. So it could result in a trap(or "Nasal Demons".)

So one way to check in the conforming way, you could do the following.

assuming INT type.. (can be extended to any type)

/* 0 -> No overflow after adding a & b
non-0 -> Overflow!!!

Checks *only* for Overflow.
_So any -ve number returns 0._


Overflow : a + b > INT_MAX (for all a > 0 and b > 0 )
Since we can't safely do (a+b) (as it might result in overflow),
we change the inequalities as : b > INT_MAX - a

*/

inline int isSumOverFlow(i nt a, int b)
{
return a > 0 && b > 0 && b > (INT_MAX - a);
}


--
(Welcome) http://www.ungerhu.com/jxh/clc.welcome.txt
(clc FAQ) http://www.eskimo.com/~scs/C-faq/top.html

[Jack Klein]

Re: detecting integer overflow

On 4 Dec 2005 23:41:03 -0800, "junky_fellow@y ahoo.co.in"
<junky_fellow@y ahoo.co.in> wrote in comp.lang.c:
[color=blue]
> Is there any way by which the overflow during addition of two integers
> may
> be detected ?[/color]

According to the C standard, overflow during operations with any of
the signed integer types causes undefined behavior. Once you invoke
undefined behavior, the C language no longer places any requirements
on the results. So for signed integer types, there is no standard way
to detect overflow after the fact.
[color=blue]
> eg.
>
> suppose we have three unsigned integers, a ,b, c.
> we are doing a check like
> if ((a +b) > c)
> do something;
> else
> do something else.[/color]

The unsigned integer types, on the other hand, can't actually overflow
or underflow. The behavior is well defined. If the result of an
operation on unsigned types is outside the range of the type, the
value is adjusted by adding or subtracting (maximum value of the type
+ 1) until the result is within range.
[color=blue]
> If addition of a and b genearates overflow, the check may fail even if
> a + b is larger than c.
> How can we avoid such conditions from failure ?
>
> Thanx in advance for any help ....[/color]

The best method is to perform the check before performing the
operation. The constants defined in <limits.h> can help.

Consider the signed integer types first. If the two values have
opposite sign, no overflow is possible with addition. The only
possibility is if both are positive or both negative. That doesn't
help much for unsigned types, which are always positive or 0, and
never negative.

bool will_overflow(u nsigned a, unsigned b)
{
if ((UINT_MAX - a) > b)
{
return true;
}
else
{
return false;
}
}

Similar logic can be performed for other types. UINT_MAX and related
macros are defined in <limits.h>.

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.l earn.c-c++

http://www.contrib.andrew.cmu.edu/~ajo/docs/FAQ-acllc.html

[pete]

Re: detecting integer overflow

Chris Williams wrote:[color=blue]
>
> junky_fellow@ya hoo.co.in wrote:[color=green]
> > Is there any way by which the overflow
> > during addition of two integers may be detected ?[/color]
>
> By the standard, I would personally guess that the state of an
> overflown integer is undefined.
> On most PCs though I would imagine that
> the result will always be less than the lower of the two values
> added--which would be a way to test.
>
> if ((c = (a + b)) > (a < b ? a : b)) {
> ...
> }
> else { /* overflowed! */
> ...
> }
>
> I'm just saying this off the top of my head,
> and you shouldn't trust it
> until you've tested throroughly though.[/color]

Tested or not, code like that,
prevents a C program from being defined.

--
pete

[pete]

Re: detecting integer overflow

pete wrote:[color=blue]
>
> Chris Williams wrote:[color=green]
> >
> > junky_fellow@ya hoo.co.in wrote:[color=darkred]
> > > Is there any way by which the overflow
> > > during addition of two integers may be detected ?[/color]
> >
> > By the standard, I would personally guess that the state of an
> > overflown integer is undefined.
> > On most PCs though I would imagine that
> > the result will always be less than the lower of the two values
> > added--which would be a way to test.
> >
> > if ((c = (a + b)) > (a < b ? a : b)) {
> > ...
> > }
> > else { /* overflowed! */
> > ...
> > }
> >
> > I'm just saying this off the top of my head,
> > and you shouldn't trust it
> > until you've tested throroughly though.[/color]
>
> Tested or not, code like that,
> prevents a C program from being defined.[/color]

I made a mistake.
I missed that a,b and c are unsigned.

--
pete

[pete]

Re: detecting integer overflow

junky_fellow@ya hoo.co.in wrote:[color=blue]
>
> Is there any way by which the overflow during addition of two integers
> may
> be detected ?
>
> eg.
>
> suppose we have three unsigned integers, a ,b, c.
> we are doing a check like
> if ((a +b) > c)
> do something;
> else
> do something else.
>
> If addition of a and b genearates overflow, the check may fail even if
> a + b is larger than c.
> How can we avoid such conditions from failure ?[/color]

For unsigned types, if (a + b > a),
then that means that (a + b) didn't wrap around.

--
pete

[pete]

Re: detecting integer overflow

pete wrote:[color=blue]
>
> junky_fellow@ya hoo.co.in wrote:[color=green]
> >
> > Is there any way by which the overflow during addition of two integers
> > may
> > be detected ?
> >
> > eg.
> >
> > suppose we have three unsigned integers, a ,b, c.
> > we are doing a check like
> > if ((a +b) > c)
> > do something;
> > else
> > do something else.
> >
> > If addition of a and b genearates overflow,
> > the check may fail even if
> > a + b is larger than c.
> > How can we avoid such conditions from failure ?[/color]
>
> For unsigned types, if (a + b > a),
> then that means that (a + b) didn't wrap around.[/color]

Better make that: if (a + b >= a),
then that means that (a + b) didn't wrap around.

--
pete

[Anand]

Re: detecting integer overflow

Anand wrote:[color=blue]
> junky_fellow@ya hoo.co.in wrote:
>[color=green]
>> Is there any way by which the overflow during addition of two integers
>> may
>> be detected ?
>>
>> eg.
>>
>> suppose we have three unsigned integers, a ,b, c.
>> we are doing a check like
>> if ((a +b) > c)
>> do something;
>> else
>> do something else.
>>
>> If addition of a and b genearates overflow, the check may fail even if
>> a + b is larger than c.
>> How can we avoid such conditions from failure ?
>>
>> Thanx in advance for any help ....
>>[/color]
> Most of the PCs I've worked with wraps the integer (so you could test it
> for wrapping around.) But the standard clearly states that integer
> overflow is an UB. So it could result in a trap(or "Nasal Demons".)
>[/color]
Sorry missed the "unsigned int" in the OP.
Here's the copy and paste from Annexure H:
| C's unsigned integer types are "modulo" in the language-independent
| arithmetic (LIA−1) sense in that overflows or out-of-bounds results
| silently wrap. An implementation that defines signed integer types as
| also being modulo need not detect integer overflow, in which case,
| only integer divide-by-zero need be detected.

[jacob navia]

Re: detecting integer overflow

junky_fellow@ya hoo.co.in wrote:[color=blue]
> Is there any way by which the overflow during addition of two integers
> may
> be detected ?
>
> eg.
>
> suppose we have three unsigned integers, a ,b, c.
> we are doing a check like
> if ((a +b) > c)
> do something;
> else
> do something else.
>
> If addition of a and b genearates overflow, the check may fail even if
> a + b is larger than c.
> How can we avoid such conditions from failure ?
>
> Thanx in advance for any help ....
>[/color]
As many posters have replied here, you *can* test for overflow
yourself. What bothers me, is that the language does not enforce this
even if it is a break of the standard, as Jack Klein has noted in
this same thread.

The lcc-win32 compiler tests for overflow with a command line
switch. This wasn't very difficult to do, and the impact
in the run time is minimal, in any case not even measurable
for a normal application in a PC environment.

OF COURSE there are other environments where each microsecond counts
and where the quality of the results doesn't matter so much...

For *those* environments the language stdandard *could* make an
exception, for instance

#pragma STDC intergeroverflo w(off)

or similar.

But in a normal case, integer overflow is a serious error,
an error that is very difficult to catch if not done at the
compiler level. You think you could have an overflow *here* or
*there* but actually you got an overflow in a completely unexpected
place!


The code generated is not specially clever. Here is the code for this
program:
int main(void)
{
int a = 0x7fffffff,b=0x 7fffffff;
int c = a*b;
}

For the relevant line we get this:
; 4 int c = a*b;
.line 4
movl -4(%ebp),%edi ; put a in edi
imull -8(%ebp),%edi ; multiply by b
jno _$L2 ; if no overflow continue at L2
pusha ; OVERFLOW save all regs
pushl $4 ; push the line number
pushl $main__labelnam e ; push the name of the function
call __overflow ; call the exception handler
addl $8,%esp ; restore stack
popa ; restore all regs
_$L2: go on

The overflow handler is prototyped as:

void __overflow(char *function name, int line);

Other mechanisms could be considered, and the generated code *could*
be better. I have found that in PC environnments, where lcc-win32 runs,
this is absolutely not measurable for normal applications...

jacob

[Skarmander]

Re: detecting integer overflow

jacob navia wrote:[color=blue]
> junky_fellow@ya hoo.co.in wrote:[color=green]
>> Is there any way by which the overflow during addition of two integers
>> may
>> be detected ?
>>
>> eg.
>>
>> suppose we have three unsigned integers, a ,b, c.
>> we are doing a check like
>> if ((a +b) > c)
>> do something;
>> else
>> do something else.
>>
>> If addition of a and b genearates overflow, the check may fail even if
>> a + b is larger than c.
>> How can we avoid such conditions from failure ?
>>
>> Thanx in advance for any help ....
>>[/color]
> As many posters have replied here, you *can* test for overflow
> yourself. What bothers me, is that the language does not enforce this
> even if it is a break of the standard, as Jack Klein has noted in
> this same thread.
>[/color]
It does not do this for the same reason that all other undefined behavior is
not necessarily diagnosed: to avoid constraining implementations .

If an implementation generates a hardware trap on overflow, for example, and
there is nothing a C program or compiler can do to modify this behavior in
the slightest, there is little to gain from making provisions in the
standard about it.

If defined behavior is necessary on such platforms, two integer calculations
have to be performed for every single one to be checked. It would obviously
be ill-advised for the standard to mandate this.
[color=blue]
> The lcc-win32 compiler tests for overflow with a command line
> switch. This wasn't very difficult to do, and the impact
> in the run time is minimal, in any case not even measurable
> for a normal application in a PC environment.
>
> OF COURSE there are other environments where each microsecond counts
> and where the quality of the results doesn't matter so much...
>[/color]
Or where the C compiler is not expected to guarantee the quality of the
results, but other methods are employed.
[color=blue]
> For *those* environments the language stdandard *could* make an
> exception, for instance
>
> #pragma STDC intergeroverflo w(off)
>
> or similar.
>[/color]
This same could be done for many language features that trigger UB, giving
well-defined behavior for constructs unless a pragma was defined. The only
fly in the ointment is that some checks would be very cheap on most
platforms (integer overflow) while others could be impossible to check
without degrading performance to nonexistent levels on some platforms
(making sure the aliasing rules are not broken).

In the end, that's just not what C is about.
[color=blue]
> But in a normal case, integer overflow is a serious error,
> an error that is very difficult to catch if not done at the
> compiler level. You think you could have an overflow *here* or
> *there* but actually you got an overflow in a completely unexpected
> place!
>[/color]
And the same is true for accessing null pointers, uninitialized variables,
defining duplicate external symbols, accessing freed memory and a myriad
other things that the standard could mandate well-defined behavior for, but
deliberately doesn't. Many languages safer than C have been created in
response to this, but C persists.

In C, it is always the programmer's responsibility to make sure
platform-defined limits are not exceeded, and the programmer's
responsibility to explicitly check for them if it cannot be guaranteed. The
programmer may even choose to exploit their platform's known behavior
despite it being left undefined by the standard, and sacrifice portability
for performance. The merits of this are debatable, of course.

[snip x86 code][color=blue]
> Other mechanisms could be considered, and the generated code *could*
> be better. I have found that in PC environnments, where lcc-win32 runs,
> this is absolutely not measurable for normal applications...
>[/color]
And I'm sure the lcc overflow detection is a valuable help to Win32
programmers. But from a practical and philosophical standpoint, the standard
can't include it. You could argue that it's so cheap and portable that it
ought to be done on every platform, but I don't know if that's true, and I'm
not on the committee.

S.

[Keith Thompson]

Re: detecting integer overflow

Skarmander <invalid@dontma ilme.com> writes:[color=blue]
> jacob navia wrote:[/color]
[...][color=blue][color=green]
>> As many posters have replied here, you *can* test for overflow
>> yourself. What bothers me, is that the language does not enforce this
>> even if it is a break of the standard, as Jack Klein has noted in
>> this same thread.
>>[/color]
> It does not do this for the same reason that all other undefined
> behavior is not necessarily diagnosed: to avoid constraining
> implementations .
>
> If an implementation generates a hardware trap on overflow, for
> example, and there is nothing a C program or compiler can do to modify
> this behavior in the slightest, there is little to gain from making
> provisions in the standard about it.
>
> If defined behavior is necessary on such platforms, two integer
> calculations have to be performed for every single one to be
> checked. It would obviously be ill-advised for the standard to mandate
> this.[/color]

The problem, though, is that C doesn't *let* you do efficient overflow
checks.

On many (most?) platforms, an overflow check can be done fairly
efficiently, typically by checking a status flag after the operation.
It's likely to be more expensive than performing the operation without
checking for overflow, but cheaper and cleaner than doing the check in
pure C (by pre-checking the operands before performing the operation).
Furthermore, if overflow checking were built into the language, the
compiler could in many cases determine that a check isn't necessary
because it knows something about the possible values of the operands.
A programmer doing the checks manually isn't likely to be able to do
this reliably.

Another problem, of course, is deciding what to do if the check fails.

(The counterargument to this is, "If you want Ada, you know where to
find it.")

--
Keith Thompson (The_Other_Keit h) kst-u@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Skarmander]

Re: detecting integer overflow

Keith Thompson wrote:[color=blue]
> Skarmander <invalid@dontma ilme.com> writes:[color=green]
>> jacob navia wrote:[/color]
> [...][color=green][color=darkred]
>>> As many posters have replied here, you *can* test for overflow
>>> yourself. What bothers me, is that the language does not enforce this
>>> even if it is a break of the standard, as Jack Klein has noted in
>>> this same thread.
>>>[/color]
>> It does not do this for the same reason that all other undefined
>> behavior is not necessarily diagnosed: to avoid constraining
>> implementations .
>>
>> If an implementation generates a hardware trap on overflow, for
>> example, and there is nothing a C program or compiler can do to modify
>> this behavior in the slightest, there is little to gain from making
>> provisions in the standard about it.
>>
>> If defined behavior is necessary on such platforms, two integer
>> calculations have to be performed for every single one to be
>> checked. It would obviously be ill-advised for the standard to mandate
>> this.[/color]
>
> The problem, though, is that C doesn't *let* you do efficient overflow
> checks.
>[/color]
True. There would be merit to a feature that allowed you to check whether an
expression will overflow, without having to explicitly write a subtraction
or division (which is less clear to boot, and you may even get it wrong).
[color=blue]
> On many (most?) platforms, an overflow check can be done fairly
> efficiently, typically by checking a status flag after the operation.
> It's likely to be more expensive than performing the operation without
> checking for overflow, but cheaper and cleaner than doing the check in
> pure C (by pre-checking the operands before performing the operation).[/color]
[color=blue]
> Furthermore, if overflow checking were built into the language, the
> compiler could in many cases determine that a check isn't necessary
> because it knows something about the possible values of the operands.
> A programmer doing the checks manually isn't likely to be able to do
> this reliably.
>[/color]
That's true, but note that if the compiler does know about the values of the
operands, it can often optimize the conditional of a generic overflow check
away as well. Obviously this is harder to do than optimizing away an
explicit overflow check, but still.
[color=blue]
> Another problem, of course, is deciding what to do if the check fails.
>[/color]
That's easy; throw an exception. Except that C doesn't have those.

You could simply define a magic macro OVERFLOW_EVAL(x ) or suchlike that
evaluates x, and then evaluates to a boolean value indicating whether the
expression overflowed. Programmers who want overflow checks can then wrap
their calculations in this macro, and deal with them explicitly.

Another possibility is to provide overflow-safe integer types. The obvious
objection against that is again that there is no explicit way to handle the
overflow condition. You could kludge it by defining a HAS_OVERFLOW(x) macro
that evaluates whether a given overflow-safe integer overflowed (similar to
NaN and Inf for floating-point) but then compilers have to jump through
hoops to get the overflow information to where it's needed.

Third and finally, C could provide a new block structure specifically for
dealing with overflow exceptions, but this is very unlikely to be
implemented before general exceptions -- which are in turn unlikely to be
implemented.
[color=blue]
> (The counterargument to this is, "If you want Ada, you know where to
> find it.")
>[/color]
Not necessarily. I'm reminded of the carry bit. Most implementations have a
carry bit, allowing you to implement greater precision arithmetic and take
advantage of several calculation tricks you simply cannot express in C.

For obvious reasons it would not pay off for C to provide access to such a
bit; if you want assembler, you know where to get it. Overflow is a
different matter, though: it is always possible to define a check for it,
some platforms may allow very efficient versions of it, and no platforms
will have a check that's slower than what the programmer already can come up
with.

Compare the intN_least_t types.

S.

[Skarmander]

Re: detecting integer overflow

Skarmander wrote:
<snip>[color=blue]
> Compare the intN_least_t types.
>[/color]
Better yet, compare the int_leastN_t types.

S.