Integer Overflow

[Keith Thompson]

Le 29/12/10 23:20, jacob navia a écrit :

Le 29/12/10 22:51, Keith Thompson a écrit :

Le 29/12/10 15:34, christian.bau a écrit :
[...]
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 shift operators? ++?

Included if signed

Ok, why didn't you mention that in the first place?

Sorry that is misleading.

Shift operations should NOT provoke any overflow

The ++ operator should.

Why?

x << 1 is equivalent to x * 2. If you're going to have a mechanism for
detecting arithmetic overflows, why should it treat them differently?

I see you're not proposing a mechanism to detect when *unsigned*
operations "overflow" (i.e., yield results that differ from the pure
mathematical result due to wraparound). Do you think such a mechanism
would be useful?

 

[jacob navia]

Le 30/12/10 00:23, Keith Thompson a écrit :

Why?

x<< 1 is equivalent to x * 2. If you're going to have a mechanism for
detecting arithmetic overflows, why should it treat them differently?

Because overflow means that there is no space in the format of the
result to hold the result of the operation.

When shifting bits it is inevitable to have some bits that "fall off",
and there is no point in assigning them the same significance. This
is NOT an exceptional situation, and if you trap on overflow
when shifting you jsut make the >> or << operation impossible
to realize in most machines!

Besides, I am certain that the overflow flag is universally supported
but not that there is an overflow when shifting bits...

I see you're not proposing a mechanism to detect when *unsigned*
operations "overflow" (i.e., yield results that differ from the pure
mathematical result due to wraparound). Do you think such a mechanism
would be useful?

A cast suffices to transform an unsigned to a signed so if you want
overflow with unsigned just cast...

unsigned a , b , c;

c = (int)b+(int)c;

 

[jacob navia]

Le 30/12/10 00:01, BGB a écrit :

if one doesn't want to depend on CPU status flags as the definition,
then an alternate means of storing them is needed, such as putting them
in a TLS variable or similar...

But why would you want to ignore the hardware flag that is in most
processors?

I mean Mr Thompson says there could be some machines in his attic that
possibly do not have an overflow flag, but in the real world I haven't
seen those very often.

 

[Keith Thompson]

Le 29/12/10 22:51, Keith Thompson a écrit :

Le 29/12/10 15:34, christian.bau a écrit : [...]
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 shift operators? ++?

Included if signed

--?
Included if signed

Conversions?

Overflow should be detected in conversions.

Array indexing?

Depends if the index is signed or not.

What does that mean? I'm referring to the indexing operation itself,
not to the computation of the index.

Should be detected of course. If
0xFFFFE + 0x100 overflows it gives a bad address.

Ok, what does "overflows" mean for a pointer? If a pointer addition
yields an address outside the bounds of the object to which it points,
is that an overflow, or does overflow occur only if the resulting
address is actually invalid? The same applies to array indexing,
which is of course defined in terms of pointer arithmetic.

That is trapped anyway in most machines.

Yes, I know that. That doesn't mean a portable program can respond
to a trapped division by 0. Does your _overflow() or something
similar handle division by 0, or do you only handle overflow?

Oh, and you said "signed"; does that mean it applies only to
integer operations, or does it also cover floating-point?

The last operation. Can't you understand english?

Don't be insulting.

Last operation in this context means any of the four
operations where the operands are signed. I hope
I do not have to explain to you hat "last" means.

Yes, as a matter of fact you do.

Note that it can be impossible to know how the compiler
will schedule operations in complex expressions,
so to have good results it is better to test operations
individually.

And that's exactly what I was asking about. If there are multiple
operations in an expression, and the language doesn't define the
order of evaluation, which one is the "last"? Is it undefined?
Does _overflow() tell you whether one arbitrarily chosen recent
operation overflowed? Is the behavior undefined?

If you're defining a language feature, it's not enough to say that
it *should* be used only in certain simple ways. You need to define
its behavior in all cases, or clearly state the cases in which its
behavior is undefined, unspecified, or implementation-defined.

Another case to consider:

x = y + z; /* might overflow */
puts("hello");
if (_overflow()) {
/* ... */
}

If you're going to remove the no-argument _overflow() and replace
it with something that takes the expression as an argument, you can
ignore this.

[...]

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.

Nobody is upset with you for offering a solution. We are offering
criticisms of the solution you're offering. If you don't want
criticism, I suggest not posting here. (That last was not meant
seriously; what I actually suggest is that you post here *and*
accept criticism.)

I have always accepted good ideas. Mr Bau proposed

int _overflow(int expr);

You would write:

if (_overflow(a+1000)) {
}

for instance. I think that is an even better solution than mine. If
I have time I will implement it.

Yes. I independently proposed the same thing in this thread,
before I read Mr. Bau's article. I also suggested something similar
nearly 4 months ago, in message <[email protected]>:

| Here's a thought:
|
| bool overflowed = false;
| int x = _CHECKED(overflowed, y + z);
| if (overflowed) {
| ...
| }
|
| The idea is that _CHECKED is a macro that takes two arguments,
| an lvalue that refers to a bool object, and a subexpression to be
| evaluated with overflow checking. If an overflow occurs anywhere
| within the expression, the bool is set to true and the resulting
| value is unspecified (but not a trap representation). Otherwise,
| the bool is either set to false or left alone, and the macro
| invocation yields the result of the subexpression. The definition
| of the macro presumably requires compiler magic.

This is more complex than _overflow(expr), but it has the advantage
that it yields the result of the expression *and* tells you whether
it overflowed or not, whereas _overflow(expr) presumably discards
the result of the expression.

I don't expect you to acknowledge that I might have proposed
something useful.

 

[jacob navia]

Le 30/12/10 00:19, Keith Thompson a écrit :

So that we can write portable code by following the C standard.

C doesn't work if there is no floating point Mr Thompson.
That means that if a machine without overflow flag exists, it must be a
very primitive one where C will not run in its standard form either.

Because it's not necessary. Because the cost of losing portability
of standard-conforming code to desktop systems exceeds the benefit
of having different versions of the language for different systems.

We can certainly have *extensions* for particular systems, but the
core language should be portable to a wide range of systems. That's
the whole point of having a language standard.

Sure but it would be better if we could test if overflow occurred isn't it?

Portability is NOT the only reason to write software. ACCURATE RESULTS,
I would say, are even MORE important!

 

[Keith Thompson]

Le 29/12/10 22:45, Keith Thompson a écrit :

There is no processor that hasn't an overflow flag.

[...]

I don't believe this is correct. In fact I seem to recall that
concrete counterexamples have been posted here.

Sure the DeathStar 9000... I know. But in that machine you can
always test for overflow as stated in the FAQ...

As I said, I was not referring to the DeathStar 9000. As it happens,
I still have a saved copy of the relevant article.

On 2009-09-01, in the thread "in standard C it is impossible
to write a correct program. Why?", Phil Carmody in message
<[email protected]> demonstrated that the DEC
Alpha has no overflow flag.

In response, you quoted a section of the DEC Alpha manual
that demonstrated that he was right, and then called him a liar.

Yes, it's possible to detect overflow on the DEC (now HP) Alpha.
But there is no overflow flag. Do you understand the difference
between being able to detect a overflow and having an overflow flag?
You keep claiming that "There is no processor that hasn't an
overflow flag". You are mistaken.

Is there any point in discussing this further with you?

[...]

 

[Keith Thompson]

Le 30/12/10 00:19, Keith Thompson a écrit :

C doesn't work if there is no floating point Mr Thompson.

It's not possible to have a conforming C implementation without
floating-point, but there have been plenty of implementations that
support floating-point in software. (I think there have also been
non-conforming implementations without FP; there's nothing wrong
with that.)

That means that if a machine without overflow flag exists, it must be a
very primitive one where C will not run in its standard form either.

I fail to see how this follows.

DEC Alpha. Again, do you understand the distinction between having
an overflow *flag* and being able to detect overflow? An explicit
flag is not the only possible mechanism. See my other followups.

[...]

Sure but it would be better if we could test if overflow occurred isn't it?
Certainly.

Portability is NOT the only reason to write software. ACCURATE RESULTS,
I would say, are even MORE important!

I agree completely.

You seem to believe that, because I criticize your proposal for
overflow detection, I don't believe accuracy is important. I have
no idea how you arrived at that belief.

 

[BGB]

It's not possible to have a conforming C implementation without
floating-point, but there have been plenty of implementations that
support floating-point in software. (I think there have also been
non-conforming implementations without FP; there's nothing wrong
with that.)

yeah, and I didn't as much use FP until the early 2000s since much prior
to this point, using fixed point was typically actually somewhat faster...

following this, there are still some calculations which are faster in
fixed-point...

but, yeah, C worked fine on typical 386 and 486 systems, and x87 wasn't
a standard feature until the 486DX and Pentium 1...


little would prevent modern C from working now on a 386 or 486SX with
the re-addition of FPU emulation and/or doing every FPU operation via
internal function calls.

or, one could go the other direction and also support a CPU lacking
proper integer math if so needed (say, for example, all integer math is
done via denormalized doubles or similar...).

That means that if a machine without overflow flag exists, it must be a
very primitive one where C will not run in its standard form either.

I fail to see how this follows.

DEC Alpha. Again, do you understand the distinction between having
an overflow *flag* and being able to detect overflow? An explicit
flag is not the only possible mechanism. See my other followups.

yep.

[...]

We can certainly have *extensions* for particular systems, but the
core language should be portable to a wide range of systems. That's
the whole point of having a language standard.

Sure but it would be better if we could test if overflow occurred isn't it?
Certainly.

Portability is NOT the only reason to write software. ACCURATE RESULTS,
I would say, are even MORE important!

I agree completely.

You seem to believe that, because I criticize your proposal for
overflow detection, I don't believe accuracy is important. I have
no idea how you arrived at that belief.

yeah, the basic idea works...

in my case, I just disagree as to the exact mechanism...

there is a cost in adding features which can't also be faked if needed.



it is sort of like adding structs to Java by adding an API which partly
fakes the behavior of structs (requiring certain usage, seemingly silly
mandatory method calls, ...) meanwhile using this as a starting point
for adding actual structs to the underlying VM in a more-or-less
transparent matter.

I actually did something like this...


it is a thin line sometimes between ritual and reality, and between the
form and the function...

in this world of code, if one can mimic the form of something enough,
they can often capture the thing in itself...


or such...

 

[BGB]

Le 30/12/10 00:01, BGB a écrit :

But why would you want to ignore the hardware flag that is in most
processors?

I mean Mr Thompson says there could be some machines in his attic that
possibly do not have an overflow flag, but in the real world I haven't
seen those very often.

one can use something without it necessarily being a part of its
definition...


it is like OpenGL:
OpenGL uses GPUs, and these are important to it having decent performance;
yet, OpenGL is defined in its own terms, and not in terms of the
specific features exported by the specific GPU.

hence, GL could, in principle, be used with a purely software
implementation, or possibly a raytracer, or ...


if it were defined in terms of a thinly wrapped interface for shoving
values into IO ports and jerking off with memory-mapped IO and blits or
similar, it would have had much less general appeal or usefulness...

so, from the POV of a C app, OpenGL is simply yet another C API, as are
the OS facilities, ...


a feature which blatantly circumvents the normal semantics for no good
reason is not nearly as preferable as an option which upholds these
semantics, and an implementation which only permits a few implementation
strategies is not nearly as preferable as one which permits many
strategies...


what if one needs to change something later?
it is not good to needlessly back oneself into a corner.
this way if something important comes up at the last minute, one can
change their plans and there is no real harm done, but if one gets stuck
to something (like inescapable commitments or similar) then one is
screwed over...


or such...

 

[jacob navia]

Le 30/12/10 01:29, Keith Thompson a écrit :

Le 29/12/10 22:45, Keith Thompson a écrit :

[...]
There is no processor that hasn't an overflow flag.
[...]

I don't believe this is correct. In fact I seem to recall that
concrete counterexamples have been posted here.

Sure the DeathStar 9000... I know. But in that machine you can
always test for overflow as stated in the FAQ...

As I said, I was not referring to the DeathStar 9000. As it happens,
I still have a saved copy of the relevant article.

On 2009-09-01, in the thread "in standard C it is impossible
to write a correct program. Why?", Phil Carmody in message
<[email protected]> demonstrated that the DEC
Alpha has no overflow flag.

In response, you quoted a section of the DEC Alpha manual
that demonstrated that he was right, and then called him a liar.

Yes, it's possible to detect overflow on the DEC (now HP) Alpha.
But there is no overflow flag. Do you understand the difference
between being able to detect a overflow and having an overflow flag?
You keep claiming that "There is no processor that hasn't an
overflow flag". You are mistaken.

Is there any point in discussing this further with you?

[...]

No, discussing with you is a waste of time.

I demonstrated that
you can detect the overflow, the central point we are discussing about.
If it is a hardware flag or a software combination of flags is
completely irrelevant. Some processors give the same effect of the
overflow flag by using other flags, this is just irrelevant, we are
discussing that _overflow() can be implemented in any
processor including the now dead dec alpha.

 

[jacob navia]

Le 30/12/10 01:48, Keith Thompson a écrit :

DEC Alpha. Again, do you understand the distinction between having
an overflow *flag* and being able to detect overflow? An explicit
flag is not the only possible mechanism. See my other followups.

You can't read Thompson. I said:

I haven't come around a processor that couldn't test for overflow.

I did not mention any flag. But you go on saying that, even if in
the text you QUOTED I said something different.

 

[jacob navia]

Le 30/12/10 02:00, christian.bau a écrit :

Here is how the N1256 draft defines the left shift operation:

The result of E1<< E2 is E1 left-shifted E2 bit positions; vacated
bits are filled with zeros. If E1 has an unsigned type, the value of
the result is E1 × 2^E2, reduced modulo one more than the maximum
value representable in the result type. If E1 has a signed type and
nonnegative value, and E1 × 2^E2 is representable in the result type,
then that is the resulting value; otherwise, the behavior is
undefined.

So for signed operands your assertion that bits "fall off" and have no
significance is wrong.

???

The sentence you quoted just adds that the behavior is undefined.
(For signed operands if the result make some 1 bits disappear)

So what?

Are you seriously saying that left shifting some bit pattern
should provoke a trap and abort the program?

In many cases (I would say most of them) shift operations
work in bit patterns where the data is not numbers but bits (for
instance flags). This is an usage that is different from
normal arithmetic operations. Hence my proposal does NOT
include shift operations even if the standard classifies
that as UB.

 

[jacob navia]

Le 28/12/10 16:36, Marcin Grzegorczyk a écrit :

#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).

Without telling where the overflow happened that doesn't help at all.

Lcc-win tells the user WHERE in the source code the operation failed.

 

[Ike Naar]

I demonstrated that
you can detect the overflow, the central point we are discussing about.
If it is a hardware flag or a software combination of flags is
completely irrelevant. Some processors give the same effect of the
overflow flag by using other flags, this is just irrelevant, we are
discussing that _overflow() can be implemented in any
processor including the now dead dec alpha.

FYI, the DEC Alpha is not dead.
In fact, I'm using one to send this post!

 

[arnuld]

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

Can you please point me to that specific discussion. Can't seem to find
it.

 

[jacob navia]

Le 30/12/10 11:50, arnuld a écrit :

Can you please point me to that specific discussion. Can't seem to find
it.

For instance

January 7th 2007

http://groups.google.com/group/comp...fr&lnk=gst&q=calloc+overflow#818c59e55205be94

Note how Heathfield and Thompson start arguing that "there is no
overflow" since the arguments are unsigned...

Three years later we repat it all over


Another on august 26th 1998

http://groups.google.com/group/comp...fr&lnk=gst&q=calloc+overflow#8680b57674f440bc

Others like this (Nov 20 2005)
http://groups.google.com/group/comp...fr&lnk=gst&q=calloc+overflow#fc89323251e4ca86
mentions that problem too.

 

[jacob navia]

Le 30/12/10 11:09, Ike Naar a écrit :

FYI, the DEC Alpha is not dead.
In fact, I'm using one to send this post!

The company that built that CPU doesn't exist any more.
The CPU itself is no longer built.

The team that designed it has disappeared.

Obviously, the CPUs that were produced 10 years ago
will go on working. When I say that the 386 is dead
it doesn't mean that some 386 aren't working
somewhere in the world. The last model dates
from 2003.

"Dead" means in this context that no software developers
are working for that machine any more.

In ANY case, the DEC ALPHA CAN detect overflow.

 

[jacob navia]

Le 29/12/10 22:54, BartC a écrit :

OK. It's that clear exactly how _overflow() works. Your docs suggest
that it simply returns the processor's overflow flag, rather than a
separate 'sticky' flag.

In what way does turning on this pragma change that?

In that the FIRST overflow will stop computation telling you
where it failed (file and line)

And what would the new code look like when used as:

if (_overflow(a+b+c))... ?

Undefined since you do not know how the compiler will schedule
operations.

 

[Nick]

Le 30/12/10 11:09, Ike Naar a écrit :

The company that built that CPU doesn't exist any more.
The CPU itself is no longer built.

The team that designed it has disappeared.

Obviously, the CPUs that were produced 10 years ago
will go on working. When I say that the 386 is dead
it doesn't mean that some 386 aren't working
somewhere in the world. The last model dates
from 2003.

Yebbut. The code I'm working on at this minute, which runs on an AMD64,
started life on a 68008 and has been on a 68030 before getting here.

Who's to say what the dominant processor won't be in another 15 years?
And whether it will have an overflow flag /that works just like the
386-derivatives/?

 

[BartC]

Yebbut. The code I'm working on at this minute, which runs on an AMD64,
started life on a 68008 and has been on a 68030 before getting here.

Who's to say what the dominant processor won't be in another 15 years?
And whether it will have an overflow flag /that works just like the
386-derivatives/?

Maybe the overflow flag was dropped from the Dec Alpha *because* no high
language could make use of it.

(Does it still have a carry flag? That tends to be of more use than overflow
for multi-precision arithmetic which I think is mostly unsigned.)