detecting integer overflow

[Skarmander]

Re: detecting integer overflow

Skarmander wrote:[color=blue]
> Skarmander wrote:
> <snip>[color=green]
>> Compare the intN_least_t types.
>>[/color]
> Better yet, compare the int_leastN_t types.
>[/color]
Or better *still*, compare the int_fastN_t types!

Excuse me, I'm suffering from caffeine deficiency. I'll remedy this with a
pot of tea.

S.

[jacob navia]

Re: detecting integer overflow

Keith Thompson a écrit :[color=blue]
> Skarmander <invalid@dontma ilme.com> writes:
>
> On many (most?) platforms, an overflow check can be done fairly
> efficiently, typically by checking a status flag after the operation.[/color]

Yes. We are in 2005, almost 2006. Please let's be realistic.
Even embedded CPUs today have of course an overflow flag reporting
after addition and multiplication. .. I would be surprised if we
would find ONE cpu that doesn't have it.
[color=blue]
> A programmer doing the checks manually isn't likely to be able to do
> this reliably.
>[/color]

This is the crucial point. You just can't do it. If each multiplication
and addition has to be tested you just can't write numerical software.
[color=blue]
> Another problem, of course, is deciding what to do if the check fails.
>[/color]

The lcc-win32 solution is quite simple: just call a function providing
the source code coordinates. This function by default exists the program
but the user can override it by defining his/her own one.

jacob

[robertwessel2@yahoo.com]

Re: detecting integer overflow


jacob navia wrote:[color=blue]
> Yes. We are in 2005, almost 2006. Please let's be realistic.
> Even embedded CPUs today have of course an overflow flag reporting
> after addition and multiplication. .. I would be surprised if we
> would find ONE cpu that doesn't have it.[/color]


That's a rather stronger statement than is justified.

Alpha allows (optional) traps on integer add/subtract/multiply
overflows, but has no overflow flag. MIPS allows traps on adds and
subtracts (but no flag). ARM has an (optional) overflow flag, but it's
not set by the multiply instructions. S/360 (zSeries) and PPC can set
an overflow condition code on adds and subtracts, or take a trap, but
not on multiplications . PA-RISC can trap on addition and subtraction,
and can trap on multiplication with a special multi-instruction
sequence. SPARC has the traditional condition code for add and
subtract, but not for multiply. IPF and PIC provide niether traps or
flags for integer arithmetic.

Most vector ISA extensions have very limited, if any, support for
integer overflows during vector operations.

I'm guessing you're surprised?

[Chris Torek]

Re: detecting integer overflow

>Keith Thompson a écrit :[color=blue][color=green]
>> On many (most?) platforms, an overflow check can be done fairly
>> efficiently, typically by checking a status flag after the operation.[/color][/color]

In article <439538a3$0$201 73$8fcfb975@new s.wanadoo.fr>
jacob navia <jacob@jacob.re mcomp.fr> wrote:[color=blue]
>Yes. We are in 2005, almost 2006. Please let's be realistic.
>Even embedded CPUs today have of course an overflow flag reporting
>after addition and multiplication. .. I would be surprised if we
>would find ONE cpu that doesn't have it.[/color]

MIPS CPUs do not have overflow flags. In fact, there are no
flags at all. To compute whether register A is less than
register B, you use the "slt" -- Set Less Than -- instruction
to put the result of the comparison in a third register. Thus,
the straightforward (and correct) C code to implement wide
arithmetic:

/* "mw" = "multiword" (64 or more bit integers, unsigned) */
/* use "inline" in C99 */
void add_mw(struct mw *result, struct mw *a, struct mw *b) {
result->lo = a->lo + b->lo;
result->hi = a->hi + b->hi + (result->lo < a->lo);
}

compiles to (e.g., and commenting for the obvious loads and stores):

# get inputs into t0/a2 and t1/a3 (lo/hi)
# outputs in v0/v1 (lo/hi)
addu v0,t0,t1
slt t1,t0,t1
addu v1,a2,a3
addu v1,v1,t1
# store result at 0(a0) and 4(a0)

if I have the argument order right (I have no idea whether I do,
I have not used MIPS assembly since the late 1980s). This is not
merely an almost-literal translation translation of the C code,
but also about the best you can do (on the R2000 and R3000 anyway;
the R4000 onward are 64-bit). (I cannot even remember how many
registers are assigned to the "t"s vs "v"s, just that there were
four "a"s for up to four arguments.)

(The CPU has separate instructions, e.g., "addi" vs "addiu" to
add an immediate value, either signed -- which traps on overflow
-- or unsigned. See http://en.wikipedia.org/wiki/MIPS_architecture
for additional examples.)

Overflow flags (or instructions) do not solve the problem for
narrow and bitfield types, of course: adding two 4-bit fields
may produce a 5-bit result. Of course, we can code for that
easily, too:

result = a + b;
if (result & ~0xf) ... overflow ...

Again, all this works much more nicely in Ada. There are plenty
of Ada compilers out there, including a GNU version, for everyone
who wants to write in Ada.
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.

[Randy Howard]

Re: detecting integer overflow

jacob navia wrote
(in article <439538a3$0$201 73$8fcfb975@new s.wanadoo.fr>):
[color=blue]
> Yes. We are in 2005, almost 2006. Please let's be realistic.[/color]

Here it comes, wait for it...
[color=blue]
> Even embedded CPUs today have of course an overflow flag reporting
> after addition and multiplication. .. I would be surprised if we
> would find ONE cpu that doesn't have it.[/color]

This is going to hurt.


--
Randy Howard (2reply remove FOOBAR)
"The power of accurate observation is called cynicism by those
who have not got it." - George Bernard Shaw

[Mark McIntyre]

Re: detecting integer overflow

On 5 Dec 2005 23:45:01 -0800, in comp.lang.c ,
"robertwessel2@ yahoo.com" <robertwessel2@ yahoo.com> wrote:
[color=blue]
>
>jacob navia wrote:[color=green]
>>I would be surprised if we
>> would find ONE cpu that doesn't have it.[/color]
>
>
>Alpha allows (optional) traps on integer add/subtract/multiply
>overflows, but has no overflow flag. MIPS allows traps on adds and
>subtracts (but no flag). ARM has an (optional) overflow flag, but it's
>not set by the multiply instructions. S/360 (zSeries) and PPC can set
>an overflow condition code on adds and subtracts, or take a trap, but
>not on multiplications . PA-RISC can trap on addition and subtraction,
>and can trap on multiplication with a special multi-instruction
>sequence. SPARC has the traditional condition code for add and
>subtract, but not for multiply. IPF and PIC provide niether traps or
>flags for integer arithmetic.
>
>Most vector ISA extensions have very limited, if any, support for
>integer overflows during vector operations.
>
>I'm guessing you're surprised?[/color]

I'm not. Neither am I surprised that Jacob posted what he did - he
apparently has very little experience outside the wintel world, but
doesn't seem to realise this.

----== Posted via Newsfeeds.Com - Unlimited-Unrestricted-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----

[jacob navia]

Re: detecting integer overflow

robertwessel2@y ahoo.com a écrit :[color=blue]
> jacob navia wrote:
>[color=green]
>>Yes. We are in 2005, almost 2006. Please let's be realistic.
>>Even embedded CPUs today have of course an overflow flag reporting
>>after addition and multiplication. .. I would be surprised if we
>>would find ONE cpu that doesn't have it.[/color]
>
>
>
> That's a rather stronger statement than is justified.
>
> I'm guessing you're surprised?
>[/color]

Yes, how many brain dead machines...

In any case this is OK, people using those machines can always do

#pragma STDC integeroverflow (off)

or the compiler can state in the documentation that overflow catching
does not work.

What is important is that we stop levelling by the lowest possible
common feature, and try to improve the language definition allowing for
machines that do not have the feature to run.

If the C standard allows for a very fine definition of the floating
point flags environment, I do not see why integers would not be allowed
the same properties!

What happens in the FPU that has no flags???

Well, the compiler can issue bogus functions or return always
zero, etc. Nonetheless the FPU flags are in the standard.
jacob

[jacob navia]

Re: detecting integer overflow

Randy Howard a écrit :[color=blue]
> jacob navia wrote
> (in article <439538a3$0$201 73$8fcfb975@new s.wanadoo.fr>):
>
>[color=green]
>>Yes. We are in 2005, almost 2006. Please let's be realistic.[/color]
>
>
> Here it comes, wait for it...
>
>[color=green]
>>Even embedded CPUs today have of course an overflow flag reporting
>>after addition and multiplication. .. I would be surprised if we
>>would find ONE cpu that doesn't have it.[/color]
>
>
> This is going to hurt.
>
>[/color]

Well, apparently it hurted so much that you forgot
the rest of the message ???

:-)

jacob

[jacob navia]

Re: detecting integer overflow

Mark McIntyre a écrit :[color=blue]
> On 5 Dec 2005 23:45:01 -0800, in comp.lang.c ,
> "robertwessel2@ yahoo.com" <robertwessel2@ yahoo.com> wrote:
>
>[color=green]
>>jacob navia wrote:
>>[color=darkred]
>>>I would be surprised if we
>>>would find ONE cpu that doesn't have it.[/color]
>>
>>
>>Alpha allows (optional) traps on integer add/subtract/multiply
>>overflows, but has no overflow flag. MIPS allows traps on adds and
>>subtracts (but no flag). ARM has an (optional) overflow flag, but it's
>>not set by the multiply instructions. S/360 (zSeries) and PPC can set
>>an overflow condition code on adds and subtracts, or take a trap, but
>>not on multiplications . PA-RISC can trap on addition and subtraction,
>>and can trap on multiplication with a special multi-instruction
>>sequence. SPARC has the traditional condition code for add and
>>subtract, but not for multiply. IPF and PIC provide niether traps or
>>flags for integer arithmetic.
>>
>>Most vector ISA extensions have very limited, if any, support for
>>integer overflows during vector operations.
>>
>>I'm guessing you're surprised?[/color]
>
>
> I'm not. Neither am I surprised that Jacob posted what he did - he
> apparently has very little experience outside the wintel world, but
> doesn't seem to realise this.
>[/color]

Maybe, I have done in the last year only some DSP assembly,
and my 68000 experience is very rusty.

Who cares? I am not "the guru", and when I stand corrected
I feel no shame to acknowledge that I was wrong.

Whats the point in discussing if you want to be always right?

jacob

[Randy Howard]

Re: detecting integer overflow

jacob navia wrote
(in article <43955c4f$0$292 21$8fcfb975@new s.wanadoo.fr>):
[color=blue]
> Randy Howard a écrit :[color=green]
>> jacob navia wrote
>> (in article <439538a3$0$201 73$8fcfb975@new s.wanadoo.fr>):
>>
>>[color=darkred]
>>> Yes. We are in 2005, almost 2006. Please let's be realistic.[/color]
>>
>>
>> Here it comes, wait for it...
>>
>>[color=darkred]
>>> Even embedded CPUs today have of course an overflow flag reporting
>>> after addition and multiplication. .. I would be surprised if we
>>> would find ONE cpu that doesn't have it.[/color]
>>
>>
>> This is going to hurt.
>>
>>[/color]
>
> Well, apparently it hurted so much that you forgot
> the rest of the message ???[/color]

What's a "hurted"?

At any rate, the other responses to this thread have already
demonstrated the point sufficiently. Are you now "surprised" ?

--
Randy Howard (2reply remove FOOBAR)
"The power of accurate observation is called cynicism by those
who have not got it." - George Bernard Shaw

[RSoIsCaIrLiIoA]

Re: detecting integer overflow

On Mon, 05 Dec 2005 18:56:39 +0100, jacob navia
<jacob@jacob.re mcomp.fr> wrote:[color=blue]
>junky_fellow@y ahoo.co.in wrote:[color=green]
>> Is there any way by which the overflow during addition of two integers
>> may
>> be detected ?
>>
>> eg.
>>
>> suppose we have three unsigned integers, a ,b, c.
>> we are doing a check like
>> if ((a +b) > c)
>> do something;
>> else
>> do something else.
>>
>> If addition of a and b genearates overflow, the check may fail even if
>> a + b is larger than c.
>> How can we avoid such conditions from failure ?
>>
>> Thanx in advance for any help ....
>>[/color]
>As many posters have replied here, you *can* test for overflow
>yourself. What bothers me, is that the language does not enforce this
>even if it is a break of the standard, as Jack Klein has noted in
>this same thread.
>
>The lcc-win32 compiler tests for overflow with a command line
>switch. This wasn't very difficult to do, and the impact
>in the run time is minimal, in any case not even measurable
>for a normal application in a PC environment.
>
>OF COURSE there are other environments where each microsecond counts
>and where the quality of the results doesn't matter so much...
>
>For *those* environments the language stdandard *could* make an
>exception, for instance
>
>#pragma STDC intergeroverflo w(off)
>
>or similar.
>
>But in a normal case, integer overflow is a serious error,
>an error that is very difficult to catch if not done at the
>compiler level. You think you could have an overflow *here* or
>*there* but actually you got an overflow in a completely unexpected
>place!
>
>
>The code generated is not specially clever. Here is the code for this
>program:
>int main(void)
>{
> int a = 0x7fffffff,b=0x 7fffffff;
> int c = a*b;
>}
>
>For the relevant line we get this:
>; 4 int c = a*b;
> .line 4
> movl -4(%ebp),%edi ; put a in edi
> imull -8(%ebp),%edi ; multiply by b
> jno _$L2 ; if no overflow continue at L2
> pusha ; OVERFLOW save all regs
> pushl $4 ; push the line number
> pushl $main__labelnam e ; push the name of the function
> call __overflow ; call the exception handler
> addl $8,%esp ; restore stack
> popa ; restore all regs
>_$L2: go on
>
>The overflow handler is prototyped as:[/color]
[color=blue]
>void __overflow(char *function name, int line);[/color]

i like that. I like to imagine too ... :)
it will be more useful if the programmer can set in the compiler, the
errors that want to see in the "runtime programme" (e.g. overflow
errors, memory leak, out of bound in writing array etc)
and there is reserved memory (e.g. 100kb) *structured like in a queue*
where the "handler " write the error that find and where the error is.

Then, at the end of programme, the memory is written down in a file:
error_programm_ name.txt

So i read error_programm_ name.txt for see if all is ok
while all you don't know what is "going wrong" and "where"
[color=blue]
>Other mechanisms could be considered, and the generated code *could*
>be better. I have found that in PC environnments, where lcc-win32 runs,
>this is absolutely not measurable for normal applications...
>
>jacob[/color]

Buon Natale a tutti