Catching integer overflow

[Keith Thompson]

[...]
I don't know. Integer overflow doesn't seem serious enough to warrant
hardware support.
[...]

You'd rather have wrong answers quickly?

Yes. Integer operations need to be fast. Overflow checking should be
optional, perhaps during development only.

[...]

Well, luckily for you, C does require overflow checking for operations
on signed integers, and mandates well-defined behavior when the checks
fail, and zero run-time overhead when they don't.

About which C you talking about?
The C89 Ansi C standard states:
The handling of overflow, divide check and other exceptions
in expression evaluation is not defined by the language.
Most existing implementations of C ignore overflow in
evaluation of signed integral expressions and assignments,
but this behavior is not guaranteed.

Sorry, I guess I was being more suble than I thought I was.

The paragraph I wrote above, starting with "Well, luckily for you", is
completely and deliberately false. I followed it with:

But you might want to verify that information. I though it was
more important to post a followup quickly than to get it right.

I was trying (apparently not completely successfully) to make a point
about the attitude that getting *quick* answers is more important than
getting *correct* answers, and drawing a parallel between performing
arithmetic without checking for overflow, and posting followups
without checking for accuracy.

 

[Keith Thompson]

[...]
I don't know. Integer overflow doesn't seem serious enough to warrant
hardware support.
[...]

You'd rather have wrong answers quickly?

...
Well, luckily for you, C does require overflow checking for operations
on signed integers...

But you might want to verify that information.  I though it was more
important to post a followup quickly than to get it right.

We may be talking at cross purposes. It seems you are saying I posted
incorrect information?

No, that's not what I was saying at all, and I apologize if I gave
that impression.

The incorrect information I was alluding to was the result of an
overflowing computation. My intent was to question the attitude that
getting this incorrect information as quickly as possible is more
important that detecting the fact that it's incorrect.

And yes, the fact that overflow detection has some significant
run-time overhead is a real issue.

[snip]

 

[jacob navia]

The incorrect information I was alluding to was the result of an
overflowing computation. My intent was to question the attitude that
getting this incorrect information as quickly as possible is more
important that detecting the fact that it's incorrect.

And yes, the fact that overflow detection has some significant
run-time overhead is a real issue.

lcc-win features this extension since at least 6-7 years...


The run time overhead is almost nothing, since it reduces to

o 1 more instruction (jump if overflow)
o in 99.999% of the case the jump is not taken.

If the compiler puts the overflow code at the end of the function,
in the x86 a forward jump will correctly be predicted as not taken...

The overhead is really minimal!

 

[robertwessel2]

Whether machines in general have an interrupt
setting to automatically trap signed integer overflow, without using
an explicit instruction per arithmetic operation, perhaps someone can
enlighten us.

Basically the answer is no. x86 basically does not, although there
are a couple of one instruction ways of detecting an overflow (JO and
INTO, the latter generating a trap). S/360..zSeries has a mode bit
which allows signed arithmetic instructions to generate traps (there
are separate unsigned instructions), although it's an all or nothing
thing, and is almost never turned on. Nor does it really cover all
situations, in that some instructions don't really generate overflows
in the sense that C would like them (for example, many of the multiply
and divide instructions). Alpha, IPF, 6502, Z-80, PIC, 8051, and ARM,
just to name a few off the top of my head, all do not provide from
trapping signed integer arithmetic, although most of them do provide
some way of detecting an overflow, sometime easy (like checking a flag
on x86), or sometimes rather more painfully (like on Alpha where you
basically have to do the overflow check manually).

In fact the only other machine I can think of that at least partially
implemented such a feature is the CDC-6600.

An interesting point of comparison is IEEE floating point, where that
facility *is* provided (by NaNs of various types) by every machine
that claims an even half baked implementation of the standard (which
is basically everything these days). It’s mostly ignored by the vast
majority of programmers.

 

[Ben Bacarisse]

As far as I can see the -ftrapv option seems to use
checks for the (x86) overflow flag and terminates the
program on overflow.

I did not find that a signal is raised or a callback
function is activated when an integer overflow occurs.

This has gone way off topic now, but on my system a signal is raised.
You are severely limited in what you can do in portable C in such
cases (which is what might be topical here) but it is possible that
you can to something on the system you are using.

Can you confirm this?

No, but it is possible the flag does something quite different on your
system. It was silly of me to replay at all -- any answer will go way
off topic for c.l.c. You need to find out if the mechanism is useful
on the platforms you intend to support by posting in other groups like
comp.unix.programmer.

 

[thomas.mertes]

This has gone way off topic now, but on my system a signal is raised.

For floating point exceptions the SIGFPE signal is raised.
I use a handler for the SIGFPE signal which contains a
siglongjmp() to jump to the exception handler.
If a signal is raised with -ftrapv I could handle integer
overflows the same way as floating point exceptions.
So far for a non portable solution.

You are severely limited in what you can do in portable C in such
cases (which is what might be topical here) but it is possible that
you can to something on the system you are using.


No, but it is possible the flag does something quite different on your
system.  It was silly of me to replay at all -- any answer will go way
off topic for c.l.c.  You need to find out if the mechanism is useful
on the platforms you intend to support by posting in other groups like
comp.unix.programmer.

Thank you.

By the way: How would a portable solution to recognize
overflows for, let's say 32 bit signed integers, look like?

Which expression should be used instead of a+b,
a-b, a*b and a/b ?

Probably something like:
overflow_would_happen_add(a,b) ? raise_exception() : a+b

but how is overflow_would_happen_add() defined?

Naturally a maximum performance portable solution is best.

I am happy with every help. Thank's in advance.

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.

 

[Kapteyn's Star]

For floating point exceptions the SIGFPE signal is raised.
I use a handler for the SIGFPE signal which contains a
siglongjmp() to jump to the exception handler.
If a signal is raised with -ftrapv I could handle integer
overflows the same way as floating point exceptions.
So far for a non portable solution.


Thank you.

By the way: How would a portable solution to recognize
overflows for, let's say 32 bit signed integers, look like?

Which expression should be used instead of a+b,
a-b, a*b and a/b ?

Probably something like:
overflow_would_happen_add(a,b) ? raise_exception() : a+b

but how is overflow_would_happen_add() defined?

Naturally a maximum performance portable solution is best.

I am happy with every help. Thank's in advance.

Thomas, may be this code?

int add_i(int x, int y, int *sum)
{
if (((x > 0 && y > 0) && ((INT_MAX - x) < y)) ||
((x < 0 && y < 0) && ((INT_MIN - x) > y)))
{
return 1;
}
else
{
*sum = x + y;
}
return 0;
}

 

[Boon]

Today's hardware does so many things.
Is it really impossible to tell the (x86) processor
to interupt when the overflow flag is set?

Your question seems appropriate for comp.lang.asm.x86

 

[thomas.mertes]

Thomas, may be this code?

int add_i(int x, int y, int *sum)
{
    if (((x > 0 && y > 0) && ((INT_MAX - x) < y)) ||
        ((x < 0 && y < 0) && ((INT_MIN - x) > y)))
    {
        return 1;
    }
    else
    {
        *sum = x + y;
    }
    return 0;

}

Since the C code would be generated by the Seed7 compiler,
I would probably try to inline this function.
Besides this, your idea is good.

I think the number of instructions can be reduced with:

int add_i (int x, int y)
{
int sum = x + y;
if ((x > 0 && y > 0 && sum < 0) ||
(x < 0 && y < 0 && sum > 0))) {
raise_exception();
} else {
return(sum)
}
}

I am not sure if this solution needs two's complement
representation to work.

Maybe someone has an idea to optimize this further.

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.

 

[Bart]

On 18 Jul., 14:23, Kapteyn's Star

...

Since the C code would be generated by the Seed7 compiler,
I would probably try to inline this function.
Besides this, your idea is good.

I think the number of instructions can be reduced with:

int add_i (int x, int y)
  {
    int sum = x + y;
    if ((x > 0 && y > 0 && sum < 0) ||
        (x < 0 && y < 0 && sum > 0))) {
      raise_exception();
    } else {
      return(sum)
    }
  }

What happened to the no-overhead requirement?

The above code uses at least 10 extra operations instead of one, a
possible extra intermediate result, and one or two jumps. And that's
for inline code. Sounds like quite an overhead to me...

Ok, this code is not yet optimised, but as it is it's likely to slow C
down to the level of interpreted code; and that's interpreted code
with the overflow check (in the form of jmp ov,somewhere) built-in!

 

[santosh]

Since the C code would be generated by the Seed7 compiler,
I would probably try to inline this function.
Besides this, your idea is good.

I think the number of instructions can be reduced with:

int add_i (int x, int y)
{
int sum = x + y;

No. If x + y would overflow you need to detect this before such an event
in C. You above statement will send the program into undefined
behaviour upon overflow so that your further statements could do
anything. The whole *point* of doing this in pure C at considerable
computational cost is to keep it portable *and* to detect an overflow
before the event.

if ((x > 0 && y > 0 && sum < 0) ||
(x < 0 && y < 0 && sum > 0))) {
raise_exception();
} else {
return(sum)
}
}

I am not sure if this solution needs two's complement
representation to work.

Yes.

<snip>

 

[Bart]

(e-mail address removed) wrote:

No. If x + y would overflow you need to detect this before such an event
in C. You above statement will send the program into undefined
behaviour upon overflow so that your further statements could do
anything.

Yes, but we all know that the worst thing likely to happen, is the
wrong value in sum.

After all, in many (most?) processors the overflow flag is tested /
after/ the operation, not before, which would make things difficult...

I think you have to read between the lines in the C standard if you
don't want to become completely paranoid about these things.

 

[santosh]

Yes, but we all know that the worst thing likely to happen, is the
wrong value in sum.

This is not a maximally portable assumption.

After all, in many (most?) processors the overflow flag is tested /
after/ the operation, not before, which would make things difficult...

I think you have to read between the lines in the C standard if you
don't want to become completely paranoid about these things.

If the OP is willing to sacrifice some portability then a least overhead
method is an inline asm statement that test the processor's overflow
flag. Does the OP anticipate his language being used on platform's
without any hardware support to detect overflow or to be compiled with
a compiler without support for inline assembler.

 

[Kapteyn's Star]

Since the C code would be generated by the Seed7 compiler,
I would probably try to inline this function.
Besides this, your idea is good.

I think the number of instructions can be reduced with:

int add_i (int x, int y)
{
int sum = x + y;
if ((x > 0 && y > 0 && sum < 0) ||
(x < 0 && y < 0 && sum > 0))) {
raise_exception();
} else {
return(sum)
}
}

I am not sure if this solution needs two's complement
representation to work.

Im sorry Thomas, i don't really know what two's complement is. I
understand that its a way to represent signed numbers but i dont know
how is exacty works. in fact i only found about INT_MAX and INT_MIN
just ysterday.

 

[santosh]

Kapteyn's Star wrote:

Please snip material which either does not contextually contribute to
your article (both to your reply and to the quoted text), or are is
supposed to be snipped when replying like signatures (unless you happen
to specifically comment on them).

Im sorry Thomas, i don't really know what two's complement is. I
understand that its a way to represent signed numbers but i dont know
how is exacty works. in fact i only found about INT_MAX and INT_MIN
just ysterday.

Maybe these links will help.

<http://mathforum.org/library/drmath/sets/select/dm_twos_complement.html>
<http://www.cs.cornell.edu/~tomf/notes/cps104/twoscomp.html>
<http://academic.evergreen.edu/projects/biophysics/technotes/program/2s_comp.htm>

 

[thomas.mertes]

What happened to the no-overhead requirement?

Nothing. It is still the preferred solution.
I just want to explore all possibilities.

The above code uses at least 10 extra operations instead of one, a
possible extra intermediate result, and one or two jumps. And that's
for inline code. Sounds like quite an overhead to me...

Yes, this is quite an overhead. Such an overhead should not
be forced on the users by default.

Ok, this code is not yet optimised, but as it is it's likely to slow C
down to the level of interpreted code; and that's interpreted code
with the overflow check (in the form of jmp ov,somewhere) built-in!

If I decide to implement integer overflow detection
for Seed7 there will be several alternate implementations:

- Use some (now unknown) feature to have zero overhead.
- Maybe the next C standard will contain something.
- Use the -ftrapv feature of gcc.
- Use some other compiler feature like accessing the
overflow flag.
- Maybe a solution with inline assembler.
- Use some semi portable solution (which may assume a
two's complement representation).
- A 100% portable solution which assumes that the computer
explodes if an integer overflow occurs.

Which of this solutions is used, would be decided with
feature tests. Such feature tests can be done when
installing Seed7 (The Seed7 interpreter and its runtime
library are delivered as C source).
When the Seed7 compiler generates C it can use the results
of this feature tests to generate the C program.

Currently the Seed7 compiler already uses some feature
tests to conditionally generate code.
It contains code like

if not USE_SIGSETJMP then
writeln(c_prog, "signal(SIGFPE, handle_fpe_signal);");
end if;

which generates code conditionally.

It is my intention to make it possible to turn the
integer overflow check on and off. Maybe it makes sense
when every program contains some pragma to decide if it
wants an integer overflow check.

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.

 

[Ben Bacarisse]

I think the number of instructions can be reduced with:

int add_i (int x, int y)
{
int sum = x + y;
if ((x > 0 && y > 0 && sum < 0) ||
(x < 0 && y < 0 && sum > 0))) {
raise_exception();
} else {
return(sum)
}
}

This is not portable because you don't know what the x + y will have
done. Of course, you may not be aiming for portable output from your
translator...

 

[Kapteyn's Star]

Kapteyn's Star wrote:

Please snip material which either does not contextually contribute to
your article (both to your reply and to the quoted text), or are is
supposed to be snipped when replying like signatures (unless you
happen to specifically comment on them).
OK.


Maybe these links will help.

<http://www.cs.cornell.edu/~tomf/notes/cps104/twoscomp.html>

<http://academic.evergreen.edu/projects/biophysics/technotes/program/2s_comp.htm>

All are very intersting. Thanks very much.

 

[thomas.mertes]

This is not portable because you don't know what the x + y will have
done.  Of course, you may not be aiming for portable output from your
translator...

Exactly. The output of the Seed7 to C translator will
probably not be portable.

The Seed7 compiler (which compiles to C) aims to compile
portable Seed7 programs. Perhaps this goal can be reached
by compiling a Seed7 program to different C programs.
This depends on the C compiler and the operating system.
That way the C program generated by the Seed7 compiler
is not portable as it is tailored to one C compiler and
one operating system. At the same time the associated
Seed7 program can be 100% portable.

BTW: The call of the C compiler is encapsulated in the
Seed7 compiler. This makes sense, since the generated
C program would not get an award for pretty code.

To come back to the topic of catching integer overflow.
I am searching for all solutions to the problem in
the range:

more portable <-------> more performance

Solutions which work only for some machines/compilers
are interesting if they provide better performance than
a more portable version.

What algorithms for overflow recognizing integer
operations do you suggest?

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.

 

[Bart]

Nothing. It is still the preferred solution.
I just want to explore all possibilities.


Yes, this is quite an overhead. Such an overhead should not
be forced on the users by default.

Actually it is not as slow as I thought. A quick test gave a 3x
slowdown.

If I decide to implement integer overflow detection
for Seed7 there will be several alternate implementations:

 - Use some (now unknown) feature to have zero overhead.
 - Maybe the next C standard will contain something.

That's a long wait. Even longer to get something implemented.

 - Use the -ftrapv feature of gcc.
 - Use some other compiler feature like accessing the
   overflow flag.
 - Maybe a solution with inline assembler.

For little overhead I think you can't beat a "jmp ov,traphandler" type
of inline asm, tailored for each target.

 - Use some semi portable solution (which may assume a
   two's complement representation).
 - A 100% portable solution which assumes that the computer
   explodes if an integer overflow occurs.

Trust me the computer will not explode. Not unless you wired the
overflow flag to a detonator and some dynamite.

Which of this solutions is used, would be decided with
feature tests.

Actually I've just added this integer overflow test to one of my
interpreters. I used the "jo traphandler" solution for x86. It
resulted in a slowdown of some 1% for code which did nothing but
integer adds. I was only testing but I think now I'll keep it in! It
might pick up extra bugs.

Thanks for the idea.