Velocity Reviews > Integer Overflow

# Integer Overflow

Keith Thompson
Guest
Posts: n/a

 12-29-2010
jacob navia <(E-Mail Removed)> writes:
> Le 29/12/10 23:20, jacob navia a écrit :
>> Le 29/12/10 22:51, Keith Thompson a écrit :
>>> jacob navia<(E-Mail Removed)> writes:
>>>> 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?

>
> 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?

--
Keith Thompson (The_Other_Keith) http://www.velocityreviews.com/forums/(E-Mail Removed) <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

jacob navia
Guest
Posts: n/a

 12-29-2010
Le 30/12/10 00:23, Keith Thompson a écrit :
>> 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?
>

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
Guest
Posts: n/a

 12-29-2010
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
Guest
Posts: n/a

 12-29-2010
jacob navia <(E-Mail Removed)> writes:
> Le 29/12/10 22:51, Keith Thompson a écrit :
>> jacob navia<(E-Mail Removed)> writes:
>>> 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.

>> Pointer arithmetic?

>
> Should be detected of course. If

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?

>> What *exactly*
>> does "the last operation" mean?
>>

>
> 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 <(E-Mail Removed)>:

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

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

jacob navia
Guest
Posts: n/a

 12-29-2010
Le 30/12/10 00:19, Keith Thompson a écrit :
> "BartC"<(E-Mail Removed)> writes:
>> "jacob navia"<(E-Mail Removed)> wrote in message
>> news:ifgbpi\$e9i\$(E-Mail Removed)...
>>> Le 29/12/10 22:45, Keith Thompson a écrit :

>>
>>>> And even if you're right, are you sure that all CPUs' overflow
>>>> flags behave the same way as the x86 overflow flag?
>>>>
>>>
>>> I haven't come around a processor that couldn't test for overflow.
>>>
>>> Maybe there are some micro-controllers that do not have that, but...
>>>
>>> who cares?

>>
>> Exactly. Why do languages have to care about the lowest common denominator
>> in processors?

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

>> I think C spreads itself too thinly. And if C implementations for
>> micro-controllers can have their own special, targeted version of the
>> language, why can't desktop versions?

>
> 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
Guest
Posts: n/a

 12-30-2010
jacob navia <(E-Mail Removed)> writes:
> Le 29/12/10 22:45, Keith Thompson a Ã©crit :
>> jacob navia<(E-Mail Removed)> writes:
>> [...]
>>> 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
<(E-Mail Removed)> 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 (The_Other_Keith) (E-Mail Removed) <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

Keith Thompson
Guest
Posts: n/a

 12-30-2010
jacob navia <(E-Mail Removed)> writes:
> Le 30/12/10 00:19, Keith Thompson a écrit :
>> "BartC"<(E-Mail Removed)> writes:
>>> "jacob navia"<(E-Mail Removed)> wrote in message
>>> news:ifgbpi\$e9i\$(E-Mail Removed)...
>>>> Le 29/12/10 22:45, Keith Thompson a écrit :
>>>
>>>>> And even if you're right, are you sure that all CPUs' overflow
>>>>> flags behave the same way as the x86 overflow flag?
>>>>>
>>>>
>>>> I haven't come around a processor that couldn't test for overflow.
>>>>
>>>> Maybe there are some micro-controllers that do not have that, but...
>>>>
>>>> who cares?
>>>
>>> Exactly. Why do languages have to care about the lowest common denominator
>>> in processors?

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

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

[...]
>> 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.

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

BGB
Guest
Posts: n/a

 12-30-2010
On 12/29/2010 5:48 PM, Keith Thompson wrote:
> jacob navia<(E-Mail Removed)> writes:
>> Le 30/12/10 00:19, Keith Thompson a écrit :
>>> "BartC"<(E-Mail Removed)> writes:
>>>> "jacob navia"<(E-Mail Removed)> wrote in message
>>>> news:ifgbpi\$e9i\$(E-Mail Removed)...
>>>>> Le 29/12/10 22:45, Keith Thompson a écrit :
>>>>
>>>>>> And even if you're right, are you sure that all CPUs' overflow
>>>>>> flags behave the same way as the x86 overflow flag?
>>>>>>
>>>>>
>>>>> I haven't come around a processor that couldn't test for overflow.
>>>>>
>>>>> Maybe there are some micro-controllers that do not have that, but...
>>>>>
>>>>> who cares?
>>>>
>>>> Exactly. Why do languages have to care about the lowest common denominator
>>>> in processors?
>>>
>>> So that we can write portable code by following the C standard.

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

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
Guest
Posts: n/a

 12-30-2010
On 12/29/2010 4:47 PM, jacob navia wrote:
> 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.
>

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
Guest
Posts: n/a

 12-30-2010
Le 30/12/10 01:29, Keith Thompson a Ã©crit :
> jacob navia<(E-Mail Removed)> writes:
>> Le 29/12/10 22:45, Keith Thompson a Ã©crit :
>>> jacob navia<(E-Mail Removed)> writes:
>>> [...]
>>>> 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
> <(E-Mail Removed)> 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.