Velocity Reviews > signed integer overflow

# signed integer overflow

REH
Guest
Posts: n/a

 08-14-2005

<(E-Mail Removed)> wrote in message
news:(E-Mail Removed) oups.com...
> REH wrote:
>> Well, efficiency is relative, [...]

>
> Well if you are willing to perform divisions, then indeed it most
> certainly is!

My point was under many circumstances, that won't matter. People spend way
to much time worrying about speed before it is even an issue. If, for
example, a real-time system can meet all of its scheduled dead-lines with
the required amount of reserved processor time, then what does it matter if
it takes twice as long as it could without the checks? Or, take a
command-line tool executed from the shell. Whether it takes 1ms or 100ms,
it is still "instantaneous" to the user.

>
>> [...] but I am currently only concerned with it
>> being correct and standard compliant. For unsigned multiplication, I am
>> currently do something like (ignoring 0 for the example):
>>
>> a = b * c;
>> if (c != a / b)
>> overflow();

>
> That's fine except for when b is zero.

Yes, reread what I wrote above.

>
> if (0 != b && a/b != c) overflow ();
>
> If you want to skip the cost of the division in many cases, then:
>
> #define HALF_WAY (1 << (sizeof (unsigned)+1)/2)
> if ((b|c) >= HALF_WAY &&
> ((b >= HALF_WAY && c >= HALF_WAY) || (0 != b && a/b != c)))
> overflow ();
>
> And of course you can go further by simulating the multiply as 4
> smaller multiplies and then checking the high multiply then the sum of
> the other 3 for overflow.
>
> All this for what can be done in basically 1 to 3 more instructions in
> most assembly languages.
>

I prefer simpler, easy to read code. I worry about speed when its an issue.
I don't plan to use this code in generating an FFT. For such code, with a
lot going on in tight loops, it would probably matter. In many other types
of code, I doubt you would notice any difference.

REH

Keith Thompson
Guest
Posts: n/a

 08-14-2005
"REH" <(E-Mail Removed)> writes:
> "CBFalconer" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed)...
>> REH wrote:
>>> "CBFalconer" <(E-Mail Removed)> wrote in message
>>>

>> Yes it is. But the information you need is there in <limits.h>.
>> You will find div(), ldiv(), and lldiv useful. Of course the
>> proper way to do it is for the actual object code to trap
>> overflows, which is ridiculously easy on the x86 at least, and most
>> grown up computer architectures, including the DS9000. On the x86
>> it only involves an INTO instruction. The standard only says that
>> the overflow action is implementation defined.
>>

>
> Yes, but I am trying to do it without resorting to assembly language because
> my code must run on various platforms and processors. So, I am trying to
> avoid causing a trap condition or undefined behavior. Of course, now that I
> know the possible formats is quite limited, and not open-ended as I had
> feared, it's not that bad. Well, not that bad yet. In the future, I want
> to expand the code to handle floating points. Which, I believe, could get
> messy...

If speed isn't too much of a concern, you might consider using an
arbitrary-precision arithmetic package, perhaps GNU MP.

--
Keith Thompson (The_Other_Keith) http://www.velocityreviews.com/forums/(E-Mail Removed) <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

Lawrence Kirby
Guest
Posts: n/a

 08-15-2005
On Sat, 13 Aug 2005 20:09:35 +0000, CBFalconer wrote:

> REH wrote:
>> "CBFalconer" <(E-Mail Removed)> wrote in message
>>>
>>> No need to guess. For any integer type, the limiting values are
>>> available in <limits.h>.

>>
>> Thanks, CB, but just knowing the limits does not make it trivial to
>> determine whether a given arithmetic operation will overflow.

>
> Yes it does. A preliminary calculation with one operand and the
> limit will yield the maximum value for the other operand, so you
> can avoid an overflow with a single comparison.
>
> if (a > 0) {
> if (b > 0)
> if (a > (MAX_INT - b)) overflow();
> }
> else if (a < 0) {
> if (b < 0)
> if (a < (MIN_INT - b)) overflow();
> }
> etc.

This seems overly complex, (testing overflow on a+b) how about:

if (b >= 0) {
if (a > MAX_INT - b) overflow();
} else {
if (a < MIN_INT - b) overflow();
}

or
overflow = (a >= 0) ? b > MAX_INT-a : b < MIN_INT-a;

For testing overflow of a-b that changes to:

if (b >= 0) {
if (a < MIN_INT + b) overflow();
} else {
if (a > MAX_INT + b) overflow();
}

These do work when MIN_INT < -MAX_INT.

Testing for multiplication oveflow is certainly trickier to do fully on
signed values with the possibility of MIN_INT < -MAX_INT, and MAX_UINT ==
MAX_INT. Any code that might calculate MIN_INT/-1 needs to be looked at
carefully.

Lawrence

cs
Guest
Posts: n/a

 08-16-2005
On Sat, 13 Aug 2005 14:41:24 GMT, "REH" <(E-Mail Removed)> wrote:
>I asked this on c.l.c++, but they suggested you folks may be better able to
>
>Basically, I am trying to write code to detect overflows in signed integer
>math. I am trying to make it as efficient as possible without resorting to
>assembly language, and without causing undefined behavior. That, of course,
>means catching the overflow before it happens.

is it just for unsigned? or for signed too?
;int over()
over:
mov eax, 0
ret

y=a+b;
if(over()) overflow();

or
if( (y=a+b), over()) overflow();
if( (z=a-b), over()) overflow();

Alexei A. Frounze
Guest
Posts: n/a

 08-17-2005
"cs" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
....
> is it just for unsigned? or for signed too?
> ;int over()
> over:
> mov eax, 0
> ret
>
> y=a+b;
> if(over()) overflow();
>
> or
> if( (y=a+b), over()) overflow();
> if( (z=a-b), over()) overflow();

It's for unsigned only. You need to check the OVerflow flag instead of CarrY
when adding/subtracting signed integers on x86. And it's trickier when one
operand is signed but the other isn't.

Alex

Alexei A. Frounze
Guest
Posts: n/a

 08-17-2005
"Eric Sosman" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
....
> As a practical matter, you can probably rely on integers
> using two's complement with no trap representations. Other
> schemes are allowed by the Standard and have been used in
> real computers, but those designs have become as rare as the
> ivory-billed woodpecker, if not the dodo.

Quite right. There's no reason to implement signed numbers as 1's complement
or sign+magnitude. The same full adder circuit will deliver the correct sum
(or difference, if properly wired for subtraction) for both unsigned and 2's
complement signed numbers. The only thing I can think of where the 1's
complement or sign+magnitude scheme would be employed (both these schemes
are practically equivalent in their inefficiency, though 1's complement is
somewhat closer to 2's complement) is when this stuff is already implemented
in some floating point unit like one IEEE-754-compliant (whose floating
point types have the sign+magnitude representation) and integer math is
derived from it for free (well, except for slowness). But that's usually
something stupid to do. The thing is, integer signed
procedures are all very simple. Even multiplication of signed 2's complement
numbers can be done directly using the Booth's algorithm, which is very
efficient in hardware and with one extra bit in operands (this bit is
normally hidden in hardware) it can produce products for unsigned*unsigned,
signed*signed, and unsigned*signed forms of the MUL (or whatever)
instruction.

> (Besides, where are
> you going to find test systems of all six architectural flavors,
> five exceedingly rare if they exist at all?) Go ahead and
> assume asymmetrical two's complement, and insert

I've never seen 1's complemented and sign+module implementations myself.
Their time has gone.

Btw, regarding the padding bits... Do I correctly understand that the
padding bits must not be between sign bit and the others making up the
magnitude/value, i.e. MSB->PPPSVVV<-LSB?

Alex

CBFalconer
Guest
Posts: n/a

 08-18-2005
"Alexei A. Frounze" wrote:
>

.... snip ...
>
> I've never seen 1's complemented and sign+module implementations
> myself. Their time has gone.

You see sign-magnitude all the time in the floating point package.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the

Alexei A. Frounze
Guest
Posts: n/a

 08-18-2005
"CBFalconer" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> "Alexei A. Frounze" wrote:
> > I've never seen 1's complemented and sign+module implementations
> > myself. Their time has gone.

>
> You see sign-magnitude all the time in the floating point package.

There -- yes, but not in integers.

Alex