Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Integer Overflow

Reply
Thread Tools

Integer Overflow

 
 
BGB
Guest
Posts: n/a
 
      12-29-2010
On 12/28/2010 10:41 PM, BGB wrote:
> On 12/28/2010 2:46 PM, Keith Thompson wrote:
>> BGB<(E-Mail Removed)> 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, ...).
>


correction (brain dump...):
__thread is for GCC for, __declspec(thread) is for MSVC, grr...
typically, I wrap stuff like this in macros anyways though...

 
Reply With Quote
 
 
 
 
jacob navia
Guest
Posts: n/a
 
      12-29-2010
Le 28/12/10 22:46, Keith Thompson a écrit :
> BGB<(E-Mail Removed)> 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.
>

lcc-win proposes:

int a,b,c;
// ...
c = a+b;
if (_overflow()) {
}

What's wrong with that?

In i386asm:
addl %eax,%ecx
jo _overflowhandler
 
Reply With Quote
 
 
 
 
BGB
Guest
Posts: n/a
 
      12-29-2010
On 12/28/2010 11:31 PM, jacob navia wrote:
> Le 28/12/10 22:46, Keith Thompson a écrit :
>> BGB<(E-Mail Removed)> 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.
>>

> lcc-win proposes:
>
> int a,b,c;
> // ...
> c = a+b;
> if (_overflow()) {
> }
>
> What's wrong with that?
>
> In i386asm:
> addl %eax,%ecx
> jo _overflowhandler


issues:
no pure C implementation is possible (while still preserving semantics);
it may carry costs on architectures which do not provide this by default
(arithmetic isn't safe unless the optimizer notes that one doesn't
capture the state);
since these status codes can only apply to a single operation at a time,
little is gained by using a raw operator;
....

providing a special intrinsic to wrap the addition allows similar to be
done without requiring this.


in my case, early on I had also added additional semantics to C to add a
new feature: geometric vector math.

however, after realizing the costs of using the feature in this form, I
switched to using intrinsics instead, since they could provide an API
which would work on existing compilers with only a modest increase in
typing.


more so, defining something like, say:
#define suAddInt32(a, b) ((a)+(b))
#define suStatusOvfP() _overflow()

would be... trivial...


similarly, I also use a standard-C-friendly interface for dynamic types
and OO facilities as well, since again this avoids compiler-specific
features...

it is really no different from wrapping any compiler specific keywords
or annotations in macros so that they may be stripped out in standard C.

for example, I could have stuff in my code like:

typedef struct FooObj_s *FooObj __declspec(dytname("_foo_obj_t"));
typedef __variant_this FooObj FooThis;
....

or, also valid:
typedef [dytname("_foo_obj_t") this] struct FooObj_s *FooObj;


but, I found it preferable to wrap a lot of this in generic macros, say:

typedef struct FooObj_s *FooObj dytname("_foo_obj_t");
typedef dycThisT(FooObj) FooThis;

which allow the preprocessor to strip a lot out, and without necessarily
exposing standard C compilers to a lot of my extensions and IDL and
reflection-related metadata...


much like a few simple macros allow me to both make use of
__declspec(dllimport) and __declspec(dllexport) without compromising my
ability to build my code on Linux and via both MSVC and GCC in addition
to using my own tools, ...


I hope the reasoning for this is understood...

 
Reply With Quote
 
jacob navia
Guest
Posts: n/a
 
      12-29-2010
Le 29/12/10 09:18, BGB a écrit :
> On 12/28/2010 11:31 PM, jacob navia wrote:


>> lcc-win proposes:
>>
>> int a,b,c;
>> // ...
>> c = a+b;
>> if (_overflow()) {
>> }
>>
>> What's wrong with that?
>>
>> In i386asm:
>> addl %eax,%ecx
>> jo _overflowhandler

>
> issues:
> no pure C implementation is possible (while still preserving semantics);


Yes.
But for the implementing a+b there is no pure c implementation either.
It is clear that at *some* level C must meet assembly.

> it may carry costs on architectures which do not provide this by default
> (arithmetic isn't safe unless the optimizer notes that one doesn't
> capture the state);


There is no processor that hasn't an overflow flag. And if
you happen to run in a weird processor without it, you can always
write it in C...

> since these status codes can only apply to a single operation at a time,
> little is gained by using a raw operator;


Yes, you have to split your statements to figure out which operation
overflowed, if you are interested in that.

> ...
>
> providing a special intrinsic to wrap the addition allows similar to be
> done without requiring this.
>


That's the same actually:

#define myProtectedAddition(result,op1,op2) result=op1+op2,_overflow()

>
> in my case, early on I had also added additional semantics to C to add a
> new feature: geometric vector math.
>
> however, after realizing the costs of using the feature in this form, I
> switched to using intrinsics instead, since they could provide an API
> which would work on existing compilers with only a modest increase in
> typing.
>


That's what I propose: _overflow() is an intrinsic.
>
> more so, defining something like, say:
> #define suAddInt32(a, b) ((a)+(b))
> #define suStatusOvfP() _overflow()
>
> would be... trivial...
>

Yes

[snip]

>
> I hope the reasoning for this is understood...
>


Yes, but that is not about checking for overflow. Now tell me:

How does your compiler handle it then?

 
Reply With Quote
 
BartC
Guest
Posts: n/a
 
      12-29-2010
"arnuld" <(E-Mail Removed)> wrote in message
news:4d19b83a$0$23763$(E-Mail Removed)...

> 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


That exercise will fail on the (high+low)/2 expression when high+low is
likely to exceed around two billion.

As the articles says, this was unlikely when the code was created (and even
now, would only apply to an int-array size of 4MB or more).

The answer is simply to use a more appropriate int-size, as trying to mess
about with overflow detection in code like this is a waste of time. (Suppose
you *do* detect that high+low overflows, then what, try and reinvent some
way of doing 33-bit arithmetic?

And what would happen if high and low were unsigned; in that case the
results would go wrong when high+low exceeded about four billion, but this
time that would be well-defined!)

If no wider arithmetic was available, then it would simplest (in this
example), to just impose an upper limit on how big an array can be searched.

I think overflow detection (ie. detecting it after the event) is more useful
when implementing some higher arithmetic routines, rather than for general
use.

--
Bartc

 
Reply With Quote
 
BartC
Guest
Posts: n/a
 
      12-29-2010

"pete" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) m...
> BartC wrote:
>> "arnuld" <(E-Mail Removed)> wrote in message


>>> nearly.html

>>
>> That exercise will fail on the (high+low)/2 expression when high+low is
>> likely to exceed around two billion.
>>


>> If no wider arithmetic was available, then it would simplest

>
> No it wouldn't.
>
>> (in this example),

>
> This is simpler: (high - low) / 2 + low


>> to just impose an upper limit on how big an array can be searched.


> A bit of analysis, is worth a byte of program.


Well, it would be simpler than rewriting code (that has been proved correct,
apparently). Especially if the routine is inside someone else's binary
library.

Although even with that fix, it might still not be possible to search the
maximum possible array size, depending on the type of a.length, so limits
could still be advisable (but at a more reasonable two billion elements
rather than one).

And specifying a range of inputs to a routine, over which it is guaranteed
to work properly, might still be a useful thing to do.

--
Bartc


 
Reply With Quote
 
jacob navia
Guest
Posts: n/a
 
      12-29-2010
Le 29/12/10 15:34, christian.bau a écrit :
> On Dec 29, 6:31 am, jacob navia<(E-Mail Removed)> wrote:
>
>> lcc-win proposes:
>>
>> int a,b,c;
>> // ...
>> c = a+b;
>> if (_overflow()) {
>>
>> }
>>
>> What's wrong with that?

>
> So what about this:
>
> c = a + b + c;
> if (_overflow()) {
> }
>


This is invalid since you do not know where the
overflow happened. The correct way is:
c = c+b;
if (_overflow()) goto error;
c += a;
if (_overflow()) goto error;

This becomes quickly tedious. That is whty lcc win allows you to
specify
#pragma overflowcheck on/off

> How is that going to work? Or c = f () + g () ?
>

c = f();
tmp = g();
if (c+= tmp,_overflow()) goto error;

> What _precisely_ is the semantics of the "_overflow" function?


It returns 1 if the last operation overflowed, zero if not.
Concerned operations: signed +,-,*, and /.


What
> about this one:
>
> c = a + b;
> error = (_overflow() | (c + 3 == x));

if a+b overflowed or c+3 is equal to x error is 1, otherwise is zero
what else you expect?
>
> Keep in mind that I wrote | and not ||.
>


If the right hand is evaluated before the intrinsic the new operation
will overwrite any overflow flag from the last one.

All this problems can be avoided if you use the #pragma overflowcheck
form.

What bothers me is that you seem so upset that I offer a SOLUTION
instead of just allowing UB. Maybe you can offer a BETTER solution?

I am all ears.

jacob

 
Reply With Quote
 
jacob navia
Guest
Posts: n/a
 
      12-29-2010
Some people here aren't aware of the problems overflow can produce. Just
remember the calloc example

Many implementations of calloc(count size) just multiply count*size
ignoring overflow with catastrophic results. We had a discussion about
that in comp.lang.c

jacob
 
Reply With Quote
 
BGB
Guest
Posts: n/a
 
      12-29-2010
On 12/29/2010 10:44 AM, jacob navia wrote:
> Some people here aren't aware of the problems overflow can produce. Just
> remember the calloc example
>
> Many implementations of calloc(count size) just multiply count*size
> ignoring overflow with catastrophic results. We had a discussion about
> that in comp.lang.c
>


if one has an overflow here, then one already has much greater problems
than having an overflow here...

> jacob


 
Reply With Quote
 
Jorgen Grahn
Guest
Posts: n/a
 
      12-29-2010
On Tue, 2010-12-28, Keith Thompson wrote:
> BGB <(E-Mail Removed)> 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.


I'd suggest simply moving to C++ for the situations where you need to
fail explicitly rather than suffer the silent overflow. The mechanism
is there already -- and so is operator overloading, to make it
readable.

This was after all one of the reasons C++ got created in the first
place.

/Jorgen

--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
integer or long overflow... deancoo C++ 11 03-05-2005 11:13 PM
integer overflow Ashutosh Iddya C Programming 25 04-24-2004 06:16 PM
hhow to detect overflow in integer calculation John Black C++ 1 04-15-2004 05:28 AM
unsigned integer overflow behaviour bartek C++ 3 02-06-2004 09:47 PM
Integer overflow Enrico 'Trippo' Porreca C Programming 9 08-24-2003 10:24 AM



Advertisments