Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C Programming (http://www.velocityreviews.com/forums/f42-c-programming.html)
-   -   Integer Overflow (http://www.velocityreviews.com/forums/t740981-integer-overflow.html)

arnuld 12-28-2010 10:13 AM

Integer Overflow
 

WANTED: How to handle integer overflows (and overflows in general)

#include <stdio.h>
#include <limits.h>
#include <errno.h>


int main(void)
{
int i, j, k;

errno = 0;
j = k = INT_MAX;
i = j + k;

printf("i = %d, errno = %d, ERANGE = %d\n", i, errno, ERANGE);
return 0;
}
===================== OUTPUT ============================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra test.c
[arnuld@dune programs]$ ./a.out
i = -2, errno = 0, ERANGE = 34
[arnuld@dune programs]$



It overflows of course, (OT) gcc does not give any error even when all
flags are on (/OT). errno does not work, its value is still zero after
that overflow. In this case how to check for overflow ? I have checked
FAQs and 20.6b gives a technique to handle this which I have applied down
here, it works fine but I am not sure it will still work if I change line
j = k = INT_MAX to j = k = INT_MIN



int main(void)
{
int i, j, k;

errno = 0;
j = k = INT_MAX;

if(INT_MAX - j < k)
{
printf("Overflow error\n");
i = INT_MAX;
}
else
{
i = j + k;
}


printf("i = %d, errno = %d, ERANGE = %d\n", i, errno, ERANGE);
return 0;
}




NOTE: Came to think of this exercise because of this article that claims
"Nearly all binary searches and mergesorts are broken". Author talsk
about line 6 but I think line 3 will overflow issue if written in C, if
a.length comes out to be greater than INT_MAX.

http://googleresearch.blogspot.com/2...-all-about-it-
nearly.html




--
http://www.lispmachine.wordpress.com

Ike Naar 12-28-2010 11:00 AM

Re: Integer Overflow
 
On 2010-12-28, arnuld <sunrise@invalid.address> wrote:
> I have checked
> FAQs and 20.6b gives a technique to handle this which I have applied down
> here, it works fine but I am not sure it will still work if I change line
> j = k = INT_MAX to j = k = INT_MIN


For reference, the FAQ says:

if(INT_MAX - b < a) {
fputs("int overflow\n", stderr);
return INT_MAX;
}
return a + b;

To check for underflow as well, you'll have to make a
slightly more elaborate test, something like:

if (0 < a && INT_MAX - a < b)
{
return INT_MAX; /* overflow */
}
else if (a < 0 && b < INT_MIN - a)
{
return INT_MIN; /* underflow */
}
else
{
return a + b; /* okay */
}

jacob navia 12-28-2010 11:15 AM

Re: Integer Overflow
 
Le 28/12/10 11:13, arnuld a écrit :
>
> WANTED: How to handle integer overflows (and overflows in general)
>
> #include<stdio.h>
> #include<limits.h>
> #include<errno.h>
>
>
> int main(void)
> {
> int i, j, k;
>
> errno = 0;
> j = k = INT_MAX;
> i = j + k;
>
> printf("i = %d, errno = %d, ERANGE = %d\n", i, errno, ERANGE);
> return 0;
> }
> ===================== OUTPUT ============================
> [arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra test.c
> [arnuld@dune programs]$ ./a.out
> i = -2, errno = 0, ERANGE = 34
> [arnuld@dune programs]$
>
>
>
> It overflows of course, (OT) gcc does not give any error even when all
> flags are on (/OT). errno does not work, its value is still zero after
> that overflow. In this case how to check for overflow ? I have checked
> FAQs and 20.6b gives a technique to handle this which I have applied down
> here, it works fine but I am not sure it will still work if I change line
> j = k = INT_MAX to j = k = INT_MIN
>
>
>
> int main(void)
> {
> int i, j, k;
>
> errno = 0;
> j = k = INT_MAX;
>
> if(INT_MAX - j< k)
> {
> printf("Overflow error\n");
> i = INT_MAX;
> }
> else
> {
> i = j + k;
> }
>
>
> printf("i = %d, errno = %d, ERANGE = %d\n", i, errno, ERANGE);
> return 0;
> }
>
>
>
>
> NOTE: Came to think of this exercise because of this article that claims
> "Nearly all binary searches and mergesorts are broken". Author talsk
> about line 6 but I think line 3 will overflow issue if written in C, if
> a.length comes out to be greater than INT_MAX.
>
> http://googleresearch.blogspot.com/2...-all-about-it-
> nearly.html
>
>
>
>


The lcc-win compiler allows you to check for overflow in all signed
integer operations. I have proposed that this be incorporated into
the C language as a standard but people in comp.std.c seem to prefer
wrong results than "wasting" some cycles in checking overflow.

Note that many other languages based on C (for instance Eiffel) have the
same problem.

You can download the lcc-win compiler at no cost from:

http://www.q-software-solutions.de
or
http://www.cs.virginia.edu/~lcc-win32

jacob

Malcolm McLean 12-28-2010 12:12 PM

Re: Integer Overflow
 
On Dec 28, 10:13*am, arnuld <sunr...@invalid.address> wrote:
> WANTED: How to handle integer overflows (and overflows in general)
>
> NOTE: Came to think of this exercise because of this article that claims
> "Nearly all binary searches and mergesorts are broken".
>

Normally it's inappropriate for general-purpose logic code to have to
worry about overflow.

The real answer is to join the campaign for 64 bit ints. Searchable
arrays of real data aren't going to go above 64 bits any time soon, so
the problem is eliminated.

Eric Sosman 12-28-2010 12:58 PM

Re: Integer Overflow
 
On 12/28/2010 5:13 AM, arnuld wrote:
>
> WANTED: How to handle integer overflows (and overflows in general)


Avoid them. If a conversion or (sub-)expression overflows,
the behavior is undefined -- meaning, among other things, that
it's already too late to "handle" something.

--
Eric Sosman
esosman@ieee-dot-org.invalid

Marcin Grzegorczyk 12-28-2010 03:36 PM

Re: Integer Overflow
 
arnuld wrote:
> #include<stdio.h>
> #include<limits.h>
> #include<errno.h>
>
>
> int main(void)
> {
> int i, j, k;
>
> errno = 0;
> j = k = INT_MAX;
> i = j + k;
>
> printf("i = %d, errno = %d, ERANGE = %d\n", i, errno, ERANGE);
> return 0;
> }
> ===================== OUTPUT ============================
> [arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra test.c
> [arnuld@dune programs]$ ./a.out
> i = -2, errno = 0, ERANGE = 34
> [arnuld@dune programs]$


$ gcc -ansi -pedantic -Wall -Wextra -m32 -ftrapv test.c
$ ./a.out
Aborted
$

As this example illustrates, the compiler is allowed to make signed
overflows cause an exception (in this case, a signal is raised).
--
Marcin Grzegorczyk

BGB 12-28-2010 05:39 PM

Re: Integer Overflow
 
On 12/28/2010 4:15 AM, jacob navia wrote:
> Le 28/12/10 11:13, arnuld a écrit :
>>
>> WANTED: How to handle integer overflows (and overflows in general)
>>
>> #include<stdio.h>
>> #include<limits.h>
>> #include<errno.h>
>>
>>
>> int main(void)
>> {
>> int i, j, k;
>>
>> errno = 0;
>> j = k = INT_MAX;
>> i = j + k;
>>
>> printf("i = %d, errno = %d, ERANGE = %d\n", i, errno, ERANGE);
>> return 0;
>> }
>> ===================== OUTPUT ============================
>> [arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra test.c
>> [arnuld@dune programs]$ ./a.out
>> i = -2, errno = 0, ERANGE = 34
>> [arnuld@dune programs]$
>>
>>
>>
>> It overflows of course, (OT) gcc does not give any error even when all
>> flags are on (/OT). errno does not work, its value is still zero after
>> that overflow. In this case how to check for overflow ? I have checked
>> FAQs and 20.6b gives a technique to handle this which I have applied down
>> here, it works fine but I am not sure it will still work if I change line
>> j = k = INT_MAX to j = k = INT_MIN
>>
>>
>>
>> int main(void)
>> {
>> int i, j, k;
>>
>> errno = 0;
>> j = k = INT_MAX;
>>
>> if(INT_MAX - j< k)
>> {
>> printf("Overflow error\n");
>> i = INT_MAX;
>> }
>> else
>> {
>> i = j + k;
>> }
>>
>>
>> printf("i = %d, errno = %d, ERANGE = %d\n", i, errno, ERANGE);
>> return 0;
>> }
>>
>>
>>
>>
>> NOTE: Came to think of this exercise because of this article that claims
>> "Nearly all binary searches and mergesorts are broken". Author talsk
>> about line 6 but I think line 3 will overflow issue if written in C, if
>> a.length comes out to be greater than INT_MAX.
>>
>> http://googleresearch.blogspot.com/2...-all-about-it-
>> nearly.html
>>
>>
>>
>>

>
> The lcc-win compiler allows you to check for overflow in all signed
> integer operations. I have proposed that this be incorporated into
> the C language as a standard but people in comp.std.c seem to prefer
> wrong results than "wasting" some cycles in checking overflow.
>
> Note that many other languages based on C (for instance Eiffel) have the
> same problem.
>
> You can download the lcc-win compiler at no cost from:
>
> http://www.q-software-solutions.de
> or
> http://www.cs.virginia.edu/~lcc-win32
>


well, one could always do arithmetic via API calls if they wanted
overflow-detecting calls.

for example, hypothetical API calls:
k=suAddInt32(i, j);
if(suStatusOvfP())
...

then, these could be implemented via ordinary calls (C or ASM), or via
macros and compiler intrinsics...


this would also avoid breaking any code which depends on the typical
integer overflow semantics or causing an overhead for operations where
overflow is not of particular interest, and also allows for a pure C
implementation if needed.

or such...

August Karlstrom 12-28-2010 09:10 PM

Re: Integer Overflow
 
On 2010-12-28 12:00, Ike Naar wrote:
> To check for underflow as well,

[...]

You mean negative overflow.

/August

--
The competent programmer is fully aware of the limited size of his own
skull. He therefore approaches his task with full humility, and avoids
clever tricks like the plague. --Edsger Dijkstra

Keith Thompson 12-28-2010 09:46 PM

Re: Integer Overflow
 
BGB <cr88192@hotmail.com> writes:
[...]
> well, one could always do arithmetic via API calls if they wanted
> overflow-detecting calls.
>
> for example, hypothetical API calls:
> k=suAddInt32(i, j);
> if(suStatusOvfP())
> ...
>
> then, these could be implemented via ordinary calls (C or ASM), or via
> macros and compiler intrinsics...


One problem with that particular interface is that the linkage
between the call and the status is IMHO too loose. The C standard's
use of errno suffers from similar problems. For example, in the
presence of threading the implementation has to play tricks to avoid
getting status results from a different thread. In effect, the error
status is a global variable, with all the problems that can cause.

Unfortunately, C doesn't provide a good clean way of doing this.
You might have something like this:

err = suAddInt32(&sum, i, j);
if (err == 0) {
/* ok, sum contains the result */
}
else {
/* something went wrong, err tells you what */
}

Or it could return the sum and store the error code via a pointer
argument.

I'm almost tempted to suggest that adding exception handling to
the language might not be a completely horrible idea.

--
Keith Thompson (The_Other_Keith) kst-u@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

BGB 12-29-2010 05:41 AM

Re: Integer Overflow
 
On 12/28/2010 2:46 PM, Keith Thompson wrote:
> BGB<cr88192@hotmail.com> writes:
> [...]
>> well, one could always do arithmetic via API calls if they wanted
>> overflow-detecting calls.
>>
>> for example, hypothetical API calls:
>> k=suAddInt32(i, j);
>> if(suStatusOvfP())
>> ...
>>
>> then, these could be implemented via ordinary calls (C or ASM), or via
>> macros and compiler intrinsics...

>
> One problem with that particular interface is that the linkage
> between the call and the status is IMHO too loose. The C standard's
> use of errno suffers from similar problems. For example, in the
> presence of threading the implementation has to play tricks to avoid
> getting status results from a different thread. In effect, the error
> status is a global variable, with all the problems that can cause.
>
> Unfortunately, C doesn't provide a good clean way of doing this.
> You might have something like this:
>
> err = suAddInt32(&sum, i, j);
> if (err == 0) {
> /* ok, sum contains the result */
> }
> else {
> /* something went wrong, err tells you what */
> }
>
> Or it could return the sum and store the error code via a pointer
> argument.
>
> I'm almost tempted to suggest that adding exception handling to
> the language might not be a completely horrible idea.
>


one could use thread-local storage for this...

AFAIK pretty much all (common?) OS's with threads also provide for TLS
and similar...

if errno was accessed via a function call, little would stop putting
this in TLS as well (however, as-is, doing so requires using compiler
specific extensions, such as the "__thread" modifier or similar for
MSVC, ...).


this way, one doesn't need to bother with providing a convoluted API to
manage status, ....

for example, AFAIK, OpenGL contexts are often handled via TLS, ...

or such...



All times are GMT. The time now is 09:04 PM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.