Eventual undefined behaviour

[Thad Smith]

Spiros Bousbouras wrote, On 15/09/07 14:23:

+ve is a fairly well known abbreviation for positive in England and I
suspect a number of other countries. I'll let you work out what -ve is.

I'm guessing that you mean positive voltage, instead of a positive
number. This assumes that the value represents a voltage.

As Keith suggests, "saturates" (v.i.) is a reasonable substitute, but it
doesn't work for the negative case. The straight-forward rewording
would be to limit the value to the range maximum and minimum.

 

[Keith Thompson]

I'm guessing that you mean positive voltage, instead of a positive
number. This assumes that the value represents a voltage.

Why would you assume that it refers to a voltage? The "ve" comes from
the last two letters of the words "negative" and "positive".

As Keith suggests, "saturates" (v.i.) is a reasonable substitute, but
it doesn't work for the negative case. The straight-forward rewording
would be to limit the value to the range maximum and minimum.

Flash Gordon can explain what he meant, but it seemed clear enough to
me (though terse): expressions whose results would exceed INT_MAX
yield INT_MAX, and expressions whose results would be less than
INT_MIN yield INT_MIN. I don't see why it doesn't work for the
negative case.

 

[Richard Bos]

Why would you assume that it refers to a voltage? The "ve" comes from
the last two letters of the words "negative" and "positive".

Because outside electrics, there's really not much need to abbreviate
positive and negative to plussive and minussive.

Richard

 

[Flash Gordon]

Keith Thompson wrote, On 17/09/07 04:49:

Why would you assume that it refers to a voltage? The "ve" comes from
the last two letters of the words "negative" and "positive".

I agree. I'm not even original in using them like that.

Flash Gordon can explain what he meant, but it seemed clear enough to
me (though terse): expressions whose results would exceed INT_MAX
yield INT_MAX, and expressions whose results would be less than
INT_MIN yield INT_MIN. I don't see why it doesn't work for the
negative case.

This is indeed what I meant and it is behaviour some DSPs can be set to
because it is very useful behaviour in signal processing.

 

[CBFalconer]

Keith Thompson wrote:
.... snip ...


This is indeed what I meant and it is behaviour some DSPs can be
set to because it is very useful behaviour in signal processing.

While it may be useful for SOME input schemes, in general it loses
the ability to detect and correct overflows (note the correct). In
addition, it effectively converts the extreme values into overflow
signals, with no correction available.

 

[Flash Gordon]

CBFalconer wrote, On 17/09/07 10:54:

While it may be useful for SOME input schemes, in general it loses
the ability to detect and correct overflows (note the correct). In
addition, it effectively converts the extreme values into overflow
signals, with no correction available.

I did not say it solves every problem only that it is very useful. I did
not even say how often it is very useful, but I will correct that, there
are a lot of situations in which it is very useful. This is why the chip
manufacturers provide this. One typical instance where it is useful is
if you are producing a signal which will be sent to a speaker, limiting
will distort the sound where wrapping is likely to wreck the speaker.
The same applies to any other control system where you will be producing
magnetic fields to deflect something (even an electron beam in a TV),
limiting will give you distorted output where wrapping will wreck
things. Do you want your dolby surround sound processor to wreck your
expensive speakers (and maybe the power amp as well) but come up with a
nice little message, or do you want it to prevent any damage?

The processor *may* also set an overflow flag and so avoid loosing the
information. I can't remember if the processors I used did this or not,
but it could certainly be done.

 

[Bart van Ingen Schenau]

While it may be useful for SOME input schemes, in general it loses
the ability to detect and correct overflows (note the correct).

I don't see how that behaviour limits your ability to detect and correct
overflows.
Overflowing a signed integer results in UB, so you would have to catch
the possible overflow before it occurs anyway. Or do you advocate the
we should limit our portability to platforms where it is documented
that overflow results in a wrap-around?

Bart v Ingen Schenau

 

[Mark McIntyre]

Why would you assume that it refers to a voltage? The "ve" comes from
the last two letters of the words "negative" and "positive".

Because outside electrics, there's really not much need to abbreviate
positive and negative to plussive and minussive.[/QUOTE]

Huh? I do it all the time.
--
Mark McIntyre

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it."
--Brian Kernighan

 

[CBFalconer]

CBFalconer wrote, On 17/09/07 10:54:
.... snip ...

The processor *may* also set an overflow flag and so avoid
loosing the information. I can't remember if the processors I
used did this or not, but it could certainly be done.

The point is that the information to perform the recovery has been
lost once the value overflows to a MAX or a MIN value. Recovery
requires the original operands, which are no longer available. For
addition, overflow with a separate signal and a modulo result
allows addition (or subtraction) of a constant to regain the
correct answer. None of this prevents the whole business being C
std compatible.

None of this is negating anything you said, it is just a factor for
users to keep in mind.

 

[CBFalconer]

I don't see how that behaviour limits your ability to detect and
correct overflows. Overflowing a signed integer results in UB,
so you would have to catch the possible overflow before it occurs
anyway. Or do you advocate the we should limit our portability to
platforms where it is documented that overflow results in a
wrap-around?

For an example, take the following code, which returns a correct
value at all times for +ve inputs, but does the relatively rapid
int addition rather than long addition (most of the time). The
code ASSUMES modulo overload action and that LONG_MAX > INT_MAX. I
am NOT recommending using this code.

long add(int a, int b) { /* not portable */
int c

c = a + b;
if ((c < a) || (c < b)) /* overflow detected */
return (long)a + (long)b;
else return c;
} /* NOT RECOMMENDED CODE */

Also see my reply to Flash Gordon.

 

[Charlie Gordon]

I don't see how that behaviour limits your ability to detect and correct
overflows.
Overflowing a signed integer results in UB, so you would have to catch
the possible overflow before it occurs anyway. Or do you advocate the
we should limit our portability to platforms where it is documented
that overflow results in a wrap-around?

Its usefulness is hampered by the fact that it cannot be relied upon. As
was stated upthread, signed integer overflow is UB even if you know the
particulars of your hardware target. It would be much more useful for
programmers if it was implementation defined and could be tested at the
preprocessor phase.

 

[Keith Thompson]

Its usefulness is hampered by the fact that it cannot be relied upon. As
was stated upthread, signed integer overflow is UB even if you know the
particulars of your hardware target. It would be much more useful for
programmers if it was implementation defined and could be tested at the
preprocessor phase.

An implementation is free to define the behavior of constructs whose
behavior is not defined by the standard.

Making the behavior on integer overflow implementation-defined would
require the standard to specify which behaviors are permitted (and
require the implementation to document which it chooses). It would
probably kill optimizations like reducing this:

int func(int x) { return x < x+1; }

to a constant 1.

 

[Flash Gordon]

Charlie Gordon wrote, On 18/09/07 07:34:

Its usefulness is hampered by the fact that it cannot be relied upon. As
was stated upthread, signed integer overflow is UB even if you know the
particulars of your hardware target. It would be much more useful for
programmers if it was implementation defined and could be tested at the
preprocessor phase.

Agreed. I only brought up this behaviour that some processors can
implement as an example of behaviour which most people would not expect
that *is* supported by real HW for good reasons. None of my code has
actually relied on it because I've not been doing things where it is
useful, and if I did it I *know* the code would be highly unportable.

 

[Charlie Gordon]

For an example, take the following code, which returns a correct
value at all times for +ve inputs, but does the relatively rapid
int addition rather than long addition (most of the time). The
code ASSUMES modulo overload action and that LONG_MAX > INT_MAX. I
am NOT recommending using this code.

long add(int a, int b) { /* not portable */
int c

c = a + b;
if ((c < a) || (c < b)) /* overflow detected */
return (long)a + (long)b;
else return c;
} /* NOT RECOMMENDED CODE */

No, I'm afraid this does not account for all supported architectures.
If signed integer addition is performed with saturation, the "overflow" will
go undetected by your code, and the incorrect, saturated value will be
returned.
More generally, you invoke undefined behaviour on signed integer overflow
ass soon as you do c = a + b with inappropriate values of a and b.

A more effective solution is this:

#include <stdint.h>

long add(int a, int b) {
if (a >= 0)
return (b <= INT_MAX - a) ? a + b : (long)a + b;
else
return (b >= INT_MIN - a) ? a + b : (long)a + b;
}

It is only slightly less efficient than yours, but should work on all
platforms for all input.

 

[CBFalconer]

No, I'm afraid this does not account for all supported
architectures. If signed integer addition is performed with
saturation, the "overflow" will go undetected by your code, and
the incorrect, saturated value will be returned.

You didn't bother to read the ASSUMPTIONS I specified above.

 

[Spiros Bousbouras]

No, I'm afraid this does not account for all supported architectures.
If signed integer addition is performed with saturation, the "overflow" will
go undetected by your code, and the incorrect, saturated value will be
returned.

CBFalconer said that his code is only intended for when int
arithmetic is performed with wraparound.

More generally, you invoke undefined behaviour on signed integer overflow
ass soon as you do c = a + b with inappropriate values of a and b.

A more effective solution is this:

#include <stdint.h>

long add(int a, int b) {
if (a >= 0)
return (b <= INT_MAX - a) ? a + b : (long)a + b;
else
return (b >= INT_MIN - a) ? a + b : (long)a + b;

}

It is only slightly less efficient than yours, but should work on all
platforms for all input.

If you are adopting CBFalconer's assumption that LONG_MAX >
INT_MAX then your code will work ; if you assume just what
the standard says and nothing more then your code can also
produce undefined behaviour.

 

[Bart van Ingen Schenau]

For an example, take the following code, which returns a correct
value at all times for +ve inputs, but does the relatively rapid
int addition rather than long addition (most of the time). The
code ASSUMES modulo overload action and that LONG_MAX > INT_MAX.

So, the portability of this code is limited to systems where it is
documented that overflow results in wraparound.
Are you saying that, because your assumption does not hold for
saturating arithmetic, saturation is not useful or that you can't take
proper measures against overflow?

I am NOT recommending using this code.

long add(int a, int b) { /* not portable */
int c

c = a + b;
if ((c < a) || (c < b)) /* overflow detected */
return (long)a + (long)b;
else return c;
} /* NOT RECOMMENDED CODE */

Here is a more portable version:

long add(int a, int b) { /* portable */
#if LONG_MAX >= 2L*INT_MAX
    if (a >= 0)
        return (b <= INT_MAX - a) ? a + b : (long)a + b;
    else
        return (b >= INT_MIN - a) ? a + b : (long)a + b;
#else
    if (a >= 0)
        return (b <= LONG_MAX - a) ? (long)a + b : (unsigned long)a + b;
    else
        return (b >= LONG_MIN - a) ? (long)a + b : (unsigned long)a + b;
#endif
}

Bart v Ingen Schenau

 

[Charlie Gordon]

You didn't bother to read the ASSUMPTIONS I specified above.

I did, but the terms "modulo overload action" do not mean anything to me.
It also matters that, unlike your other assumption LONG_MAX > INT_MAX,
behaviour on overflow cannot be tested at compile time, nor safely at run
time. A solution that does not make such an assumption is definitely
preferable, especally if it is comparably efficient.

It is also highly unlikely that the long addition performed at all times be
less efficient than testing and branching... but the code above was only
there for illustrative purposes, an not recommended ;-)

 

[Charlie Gordon]

CBFalconer said that his code is only intended for when int
arithmetic is performed with wraparound.

Sorry about that, I read too fast.

If you are adopting CBFalconer's assumption that LONG_MAX >
INT_MAX then your code will work ; if you assume just what
the standard says and nothing more then your code can also
produce undefined behaviour.

Of course that assumption is also mine. If LONG_MAX == INT_MAX, then we
have to specify what we want this function to return. Saturation is trivial
to implement, modulo wrap around is more tricky.

 

[Charlie Gordon]

So, the portability of this code is limited to systems where it is
documented that overflow results in wraparound.
Are you saying that, because your assumption does not hold for
saturating arithmetic, saturation is not useful or that you can't take
proper measures against overflow?


Here is a more portable version:

long add(int a, int b) { /* portable */
#if LONG_MAX >= 2L*INT_MAX

Writing the test this way is neither needed not advisable:
if LONG_MAX == INT_MAX, the expression 2L*INT_MAX overflows.
The definition of possible integer representations in the Standard specifies
value bits and binary representation: INT_MAX is a power of 2 minus 1.
Just testint LONG_MAX > INT_MAX would suffice.

if (a >= 0)
return (b <= INT_MAX - a) ? a + b : (long)a + b;
else
return (b >= INT_MIN - a) ? a + b : (long)a + b;

That's my proposal.

#else
if (a >= 0)
return (b <= LONG_MAX - a) ? (long)a + b : (unsigned long)a + b;
else
return (b >= LONG_MIN - a) ? (long)a + b : (unsigned long)a + b;

This does not work. Casting a as unsigned long forces the computation to use
unsigned arithmetics, which is fine, but the return statement will have to
convert the result back to a long: c99 6.3.1.3p3 "the new type is signed
and the value cannot be represented in it; either the result is
implementation-defined or an implementation-defined signal is raised."

We know there is an overflow is these cases, we just have to decide what
behaviour we want for add in case of long overflow:

#if INT_MAX == LONG_MAX
#if OVERFLOW_SATURATE
if (a >= 0)
return (b <= LONG_MAX - a) ? a + b : LONG_MAX;
else
return (b >= LONG_MIN - a) ? a + b : LONG_MIN;
#elif OVERFLOW_WRAP_AROUND && LONG_MIN < -LONG_MAX
if (a >= 0) {
if (b <= LONG_MAX - a) {
return a + b;
} else {
unsigned long s = (unsigned long)a + b;
if (s == (unsigned long)LONG_MIN)
return LONG_MIN;
else
return -(long)-s;
}
} else {
return (b >= LONG_MIN - a) ? a + b :
(unsigned long)a + b;
}
#else
#error "unsupported configuration"
#endif

#endif

As a matter of fact, what is or was the behaviour of non 2s-complement
hardware on signed integer overflow ?