Integer Overflow

[robertwessel2]

Le 30/12/10 22:26, tm a crit :







If you write

_overflow(expression)

overflow will be checked only in the last operation of
"expression". Outside this construct things remain as they are
now.

If you think that the cost of testing for overflow
is too expenseive just produce wrong results very fast




Mmmm I know of no processor that does what you propose.
Can you give me an exaple?

S/360 and its descendents can generate a trap on some overflows
(masked by a user accessible bit in the PSW).

 

[Ben Bacarisse]

Le 30/12/10 20:47, Seebs a écrit :

Then, it is very easy, just SPLIT your number in two
of those 4 slots and add them in parallel, then see if the
high parts overflow.

It's not quite as easy as that because there is no carry from the
low-order part of this split add operation, but it is of course possible
to code an overflow test for this processor. In fact, I think there is
an instruction to help so there is no need to do a split add.

All this is moot now, since I was commenting on a plan that seemed to
rely heavily on reading the processor's arithmetic flags.

I think that any plan that has a well-defined scope for the overflow
checking will be easier to implement on peculiar architectures. I'll
review what you wrote about _overfow(<expression>).

<snip>

 

[BartC]

Quite a lot, I think there's at least one chip where the obvious way
to read the status register is a privileged operation which can trap to
the OS in some cases. Hmm. Seem to recall there was something like
this that happened if you swapped the 68000 in an early Amiga out for
a 68010.

You don't need to read the status register.

The 68K has the BVS instruction to branch on overflow, just like the x86's
JO.

And it seems to have (looking at the instruction set for the first time in
decades) TRAPV to manually trigger an interrupt on overflow.

So it has most of the support needed to implement _overflow(expr), but at
some cost.

 

[Seebs]

Am I, now?

No, Seebs is right. On the 68000 there was a single unprivileged
instruction (MOVE SR,_ea_ ...) to read the entire 16 bit status
register, including both the user and supervisor parts. There was no
instruction to read only the unprivileged part.

Exactly.

Thus, any code which ran on the 68000 *had* to use the now-privileged
instruction.

User access to the
suppervisor flag presents certain problems, particularly with
virtualization. On the 68010 and later, that was changed so that the
*existing* 68000 instruction became privileged, and a *new*
instruction (MOVE CCR,_ea_ ...)was added that read only the
unprivileged part (still returned a 16 bit result, just with the high
byte cleared).
Yes.

Systems upgrading from the 68000 to the 68010 needed either changes in
user code to use the new instruction, or OS support to trap and
emulate the now privileged instruction.

Or, if you were on the Amiga, where you basically ran privileged anyway,
grab a little 1KB executable someone produced which added a trap
handler that ran the other instruction. The machine ran enough faster
overall to make up for the cost.

-s

 

[Seebs]

You don't need to read the status register.

Sure. But the question was whether there was anything cheaper than
doing so.

-s

 

[Ben Bacarisse]

Le 30/12/10 18:59, Ben Bacarisse a écrit :

Le 30/12/10 14:34, Ben Bacarisse a écrit :
This raises the question of what the 'last operation' is. You've shown

c = a + b;
if (_overflow()) ...

as the canonical example of this feature, but the "last operation" is
the conversion of the value of 'a + b' to the type of 'c'. This
operation may be the one I want to test for overflow. How does the
compiler know which overflow (the addition or the conversion) I am
interested in?

<snip>

In the example c is int, as b and c. That can't overflow.

Different is
short c;
int b,a;

c =a+b

can overflow (as you say) in a+b AND in the assignment. In that
case you should separate the operations for instance

if (!overflow(a+b)) {
if (_overflow(c=a+b))
// error
}
else // error

I was asking about something I though you were proposing -- an
_overflow() "intrinsic" that returned the overflow result of the "last
operation". This is a concept that you seemed to think was
self-evident[1] but which you now seem to have abandoned.

Not at all. That is why I said above that you have to separate the
addition from the assignment. Overflow detection is NOT sticky,
i.e. it only tells you the overflow of the LAST operation.

That seems a shame. Since overflow detection is now "scoped" (it only
happens, I presume, inside a call to _overflow) I think it would be
more helpful if it *were* sticky so that

_overflow(x = y * z + w)

returns 1 if any of the operations in the expression overflow.

Again:
short c = (int)b+(int)a;

There are two operations here: "+" and "=".

To know which overflowed we do first the addition

if (!_overflow(b+a))

If that NOT overflows, THEN we test the assignment.

So, presumably, in the case where the assignment can't overflow
(i.e. going back to your original case where all variables where ints)
to set c to a + b whist checking for overflow one has to write:

if (!_overflow(a + b)) c = a + b;

?

Repeating the expression like that looks a little clumsy and error
prone.

I'd favour something more like Keith's proposal (sorry, Keith, I may
have got the details wrong) where the overflow is signalled "out of
band":

bool ovfl;
c = _overflow_checked(a + b, &ovfl);

No. And if there is no flag it emulates the flag in software.

If so, I'll start the whole thing again by

Overflow returns the state of the last operation:
1 if the last operation overflowed, zero if it didn't.

But limited to the evaluation of 'expr'? I am still not clear if

c = a + b;
if (_overflow()) ...

is allowed or not.

Semantics of _overflow()

(1) Operations in the virtual C machine as specified by the
standard can be scheduled in any order between sequence points
if that reordering doesn't affect the outcome as specified
by the programmer

(2) After scheduling operations, they are executed one after the other.
There is a LAST operation then. THAT operation sets the result of
_overflow.

What about x++ and x += e? Is the last operation the addition or the
assignment? What about function calls? Is the last operation the last
arithmetic operation performed by the function, or is it the return
operation? If it is the return, can that overflow?

The user should isolate operations to avoid ambiguities or
false negatives.

Sepantics of
#pragma overflowcheck on/off
Each of the 4 operations in +,-,*,/ are tested for overflow if
signed data is used. If any operation overflows a special
function is called with the line number and file name where
the faulty operation is detected.

The user can redefine the default, compiler provided function.
That default function looks like this:

_overflowHandler(unsigned linenum, char *fileName,...)
{
fprint(stderr,"Overflow at %s line %u\n",fileName,linenum);
abort();
}

I have been repeating that since the beginning but there is no
way that people here seem to understand

The above is new to me. I originally commented on a different proposal.

Even since then, you seem to have changed your mind about the value
checking conversions. I don't think there is, yet, a clear and stable
proposal for anyone to get behind.

 

[Keith Thompson]

If you write

_overflow(expression)

overflow will be checked only in the last operation of
"expression". Outside this construct things remain as they are
now.

Then how is the _overflow(expression) form any better than the
_overflow() form you had previously?

If you think that the cost of testing for overflow
is too expenseive just produce wrong results very fast

Right, because anyone who says anything critical about your ideas must
obviously be a big fan of wrong results. (That was sarcasm.)

 

[Keith Thompson]

Jacob is quite fixated on "this is what is easy to implement, so this
is what I want to implement. My spec would be:

The function _overflow () is declared as int _overflow (int x). It
returns a value of 0 or 1.

Some suggestions.

First, using int as the argument type seems arbitrary. Since
_overflow() is going to require compiler magic anyway, I suggest
*not* treating it as if it were an ordinary function, and allowing
any arithmetic type (or at least any signed integer type) as the
argument. We don't want _overflow(LONG_MAX - 1) to return true.

_overflow could even be a unary operator (perhaps spelled _Overflow for
consistency with other added keywords). In that case, the argument
(actually operand) would usually be a parenthesized expression, but that
wouldn't be part of the syntax.

Second, we might consider having it return _Bool rather than int
(or not, since there's ample precedent in the standard library for
boolean functions returning int).

Finally, as I've pointed out, this discards the result of the
expression. That's not a fatal flaw; we can use
_overflow(var = <expr>);
if we want the result.

[...]

 

[Nick]

Le 30/12/10 23:39, Nick a écrit :

I am not sure of that. There is an awful lot of code that assumes that
int b;
char a;

a = b;

People think that the lower 8 bits of the integer will be in a
after the assignment. Yes, some compiler emit warnings in
"checking" mode, but still there could be a lot of cases where
people just take the lower 8 (or 16 or 32) using an
assignment.

Yes, but in the new proposal checking only takes place when you are
wrapping it. So most of the time it wouldn't be a problem. If you made
it work so that an explicit cast disabled the check (which seems to me
to be in the spirit of C) all would be fine.

a=b+c would never check
_overflow(a=b+c) would check if b+c overflowed or if bits were lost on
assignment
_overflow(a=(char)(b+c)) would only check the addition.

So. If you write a+b and your calculation overflows you
DO NOT LIKE to be warned about it and prefer to go on
with wrong results?

No. You know I'm trying to help here, and putting stupid words in my
mouth and attacking them is not the way to encourage me.

Obviously the wrong results will be calculated with
maximum speed... the only thing that counts here.
Ditto.

Or not?

No, you thundering buffoon. I /like/ the idea of being able to check
for overflow in particular cases. But when I do I want to be able to
check for any and all overflows, without having to break a simple
addition and assignment into two calculations involving an intermediate
variable of a particular and carefully chosen type.

 

[tm]

The way it's done now (on x86 anyway) makes sense. An overflow from unsigned
arithmetic is not that much of a calamity. And software that is worried
about it can just check the flag.

If an overflow interrupt was possible, then it would need to be maskable.

Of course

After all, would you want an interrupt when the carry flag was set?

There must be a clear destinction between computations
with and without overflow check.

Almost
certainly not. But a carry flag would signal overflow of unsigned arithmetic
(even if C chooses to pretend that such an overflow is impossible).

Every C extension must keep the current behavior.

But not via an interrupt routine, surely, since it would slow it down by
several hundred times.

I was not precise enough. The transition from fixed size
arithmetic to unlimited precision arithmetic could
possibly benefit from an overflow interrupt. Many
unlimited precision libraries use fixed size arithmetic
for small numbers and change to the unlimited representation
when the numbers are bigger.

BTW: I wrote a library for unlimited precision arithmetic
for Seed7. The Seed7 unlimited precision library has no
fixed size representation for small numbers, because I
think that a unique representation is better compared
to two representations and a (costly) overflow detection.


Greetings Thomas Mertes

--
Seed7 Homepage: http://seed7.sourceforge.net
Seed7 - The extensible programming language: User defined statements
and operators, abstract data types, templates without special
syntax, OO with interfaces and multiple dispatch, statically typed,
interpreted or compiled, portable, runs under linux/unix/windows.

 

[tm]

So you would think, floating point errors already do.

Exactly, I just want the same technic for overflow
detection also.


Greetings Thomas Mertes

--
Seed7 Homepage: http://seed7.sourceforge.net
Seed7 - The extensible programming language: User defined statements
and operators, abstract data types, templates without special
syntax, OO with interfaces and multiple dispatch, statically typed,
interpreted or compiled, portable, runs under linux/unix/windows.

 

[tm]

[...]

If you write

overflow will be checked only in the last operation of
"expression". Outside this construct things remain as they are
now.

Then how is the _overflow(expression) form any better than the
_overflow() form you had previously?

Zero cost overflow detection (no costs as long as no
overflow occurs) with interrupts is impossible when an
overflow flag needs to be checked after every expression.

I think that a proposal to do overflow detection in C
should allow zero cost overflow detection when the
hardware allows it.


Greetings Thomas Mertes

--
Seed7 Homepage: http://seed7.sourceforge.net
Seed7 - The extensible programming language: User defined statements
and operators, abstract data types, templates without special
syntax, OO with interfaces and multiple dispatch, statically typed,
interpreted or compiled, portable, runs under linux/unix/windows.

 

[Keith Thompson]

Besides, I am scared about overflows in casts since a lot of code out
there assumes that

char c = (int) a;

takes the lower 8 bits of the integer without any trap...
At the beginning of the discussion I thought narrowing casts should
be included but thinking it over it could be really a problem.

If plain char is unsigned, the result is well defined. If plain
char is signed, the result is implementation-defined (or an
implementation-defined signal is raised).

The objective should be to give something practical, that does NOT
disturb existing code.

Um, existing code doesn't invoke _overflow().

 

[tm]

$ gcc -ansi -pedantic -Wall -Wextra -m32 -ftrapv test.c

I just rediscovered the -ftrapv option of gcc and started
some tests with it. I compiled my Seed7 interpreter and
found a place where I did

base = (bigdigittype) -(signedbigdigittype) base;

This line overflows when 'base' has all bits set.
The option -ftrapv causes an abort signal. I had to
change the line to

base = -base;

to avoid a signed integer overflow (base is an unsigned
value). So the - operator is used although base is an
unsigned value. Funny becaused I introduced the casts
to silent some warnings I got from a C compiler (not gcc).


Greetings Thomas Mertes

--
Seed7 Homepage: http://seed7.sourceforge.net
Seed7 - The extensible programming language: User defined statements
and operators, abstract data types, templates without special
syntax, OO with interfaces and multiple dispatch, statically typed,
interpreted or compiled, portable, runs under linux/unix/windows.

 

[tm]

Ref: C++ SafeInt. It's already been done, questions already answered.

http://msdn.microsoft.com/en-us/library/dd570023.aspx

Is this a protable C++ solution or a M$ only solution?


Greetings Thomas Mertes

--
Seed7 Homepage: http://seed7.sourceforge.net
Seed7 - The extensible programming language: User defined statements
and operators, abstract data types, templates without special
syntax, OO with interfaces and multiple dispatch, statically typed,
interpreted or compiled, portable, runs under linux/unix/windows.

 

[robertwessel2]

Is this a protable C++ solution or a M$ only solution?

It originated in MS, but is now available under their OSS-ish Ms-PL
license:

http://safeint.codeplex.com/

The documentation claims that with optimization turned on, the
overhead is about 8%, albeit under unspecified conditions (and
apparently using the MS compiler).

Interestingly, this discussion had prompted me to sketch out the
outline of something similar, and even start writing some code. This
is worth at least looking at.

 

[Edward A. Falk]

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.

I agree with them. The vast, vast majority of the time, integer
addition does not generate an overflow, and the vast, vast majority
of the cases where it does are not handled by the software. What
would you have the system do? Crash the program? Set errno, which
would almost certainly be ignored?

And how should this be implemented? Implement a hardware trap? How
many cpus even support this? Test for overflow in code after every
add or subtract?

All of these implementations and all of these handlers would be
wasting a great number of cpu cycles, all for a case which is
almost never handled anyway.

If a programmer *wants* to check for overflow, there are very
easy ways to do it in code.

C was designed to be fast, not to be bullet-proof.

 

[Keith Thompson]

I agree with them. The vast, vast majority of the time, integer
addition does not generate an overflow, and the vast, vast majority
of the cases where it does are not handled by the software. What
would you have the system do? Crash the program? Set errno, which
would almost certainly be ignored?

And how should this be implemented? Implement a hardware trap? How
many cpus even support this? Test for overflow in code after every
add or subtract?

All of these implementations and all of these handlers would be
wasting a great number of cpu cycles, all for a case which is
almost never handled anyway.

There is precedent for this in other languages. All your questions can,
in principle, be answered. For example, Ada requires an exception to be
raised if an arithmetic operation overflows (and allows the check to be
suppressed).

I'm not suggesting that C should become Ada, but the existence of open
questions doesn't by itself mean overflow checking shouldn't be added to
the language.

If a programmer *wants* to check for overflow, there are very
easy ways to do it in code.

Are there really?

I know of no *easy* way to implement the following function in
portable C:

int mul(int x, int y, int *overflow);
/* If the multiplication x * y overflows,
* returns an implementation-defined result and sets
* *overflow to 1; otherwise returns x * y and sets
* *overflow to 0.
*/

C was designed to be fast, not to be bullet-proof.

Furthermore, if overflow checking were in the language, it would
be visible to the compiler, which could eliminate some checks if
it can prove that an overflow cannot occur.

 

[Malcolm McLean]

I agree with them.  The vast, vast majority of the time, integer
addition does not generate an overflow, and the vast, vast majority
of the cases where it does are not handled by the software.  What
would you have the system do?  Crash the program?  Set errno, which
would almost certainly be ignored?

Crash the program. A error message is usually better than wrong
results.

 

[Marcin Grzegorczyk]

I just rediscovered the -ftrapv option of gcc and started
some tests with it. I compiled my Seed7 interpreter and
found a place where I did

base = (bigdigittype) -(signedbigdigittype) base;

This line overflows when 'base' has all bits set.
The option -ftrapv causes an abort signal. I had to
change the line to

base = -base;

to avoid a signed integer overflow (base is an unsigned
value). So the - operator is used although base is an
unsigned value. Funny becaused I introduced the casts
to silent some warnings I got from a C compiler (not gcc).

I think if you used just

base = (bigdigittype)-base;

it might also convince the compiler you know what you are doing. When I
did that many years ago, it worked for GCC (version 3.something, with
the -Wextra option (which was called -W back then) enabled) and
Borland's free Win32 compiler (v.5.5.1 IIRC), although in the case of
the latter it also, surprisingly, prevented the statement from being
optimized for size.