In article <3tebt8$jkn@wcap.centerline.com>,
David Chase <chase@centerline.com> wrote:
>
>> sigbern@ismennt.is (Sigurdur Bernhard Finnsson) writes:
>> >How is it possible in ANSI C++ to detect if an overflow occured
>> >on a binary integer number, the same operation as the Carry bit is for in
>> >assembler?

 See "Software Solutions in C", ed. Schumacher, AP Professional.
CH17  is on extended precision arithmetic in ISO C. (author: me :-)

>
>> The only reliable and portable way to check for mathematical overflow
>> in C or C++ source code is to test before performing an operation
>> whether it will succeed. E.g.,
>>  if( a > 0 && b > 0 && a > MAX - b )
>>      ... result will overflow
>
>That's not the only way at all,

 Excuse me: the writer of the above said "EG". There was no
claim this was the only piece of code that would do the job.

>  unsigned x, y, z, c;
>  ...
>  z = x + y;
>  c = z < x; /* z < y will also work. */

 But only for unsigned. Which is the only reliable way to
do arithmetic anyhow.

 Now try multiplication. And if you're really feeling brave
try division. Thats _really_ tricky with only a single size of operand.

I got it right but gave up trying to optimise it. ISO C is singularly
inefficient at doing big arithmetic :-( A guarrantee there exist two
unsigned types one at least twice the number of bits of the other
would significantly enhance efficiency.

--
        JOHN (MAX) SKALLER,         INTERNET:maxtal@suphys.physics.su.oz.au
 Maxtal Pty Ltd,
        81A Glebe Point Rd, GLEBE   Mem: SA IT/9/22,SC22/WG21
        NSW 2037, AUSTRALIA     Phone: 61-2-566-2189

[This is really about C, unless it causes people working on the
C++ standard to think about the language that they use to define
the basic integer data types.  You might consider using the example
carry-detecting code in an example, since this is not the first time
that this question has come up.]

> sigbern@ismennt.is (Sigurdur Bernhard Finnsson) writes:
> >How is it possible in ANSI C++ to detect if an overflow occured
> >on a binary integer number, the same operation as the Carry bit is for in
> >assembler?

In article <3t3u1c$jk6@engnews2.Eng.Sun.COM>, clamage@Eng.Sun.COM (Steve Clamage) writes:
> In C and C++, arithmetic on unsigned integer types cannot overflow.
> By language definition, unsigned arithmetic on a type with N bits is
> performed modulo 2**N.

> The only reliable and portable way to check for mathematical overflow
> in C or C++ source code is to test before performing an operation
> whether it will succeed. E.g.,
>  if( a > 0 && b > 0 && a > MAX - b )
>      ... result will overflow

That's not the only way at all, and it certainly less efficient than
one alternative.  Note that the carry bit corresponds to so-called
"unsigned overflow", which IS well-defined at the assembly language
level.  If, as you claim, unsigned arithmetic operates within some
modulus 2**N, then this is portable, though if the C/C++ "N" is not
the same as the machine "N", then it will capture a different carry
bit (the one corresponding to the smaller value of N, obviously).

  unsigned x, y, z, c;
  ...
  z = x + y;
  c = z < x; /* z < y will also work. */

This could be implemented in a single instruction, if the compiler
were up to it (IF the compiler register-allocated "c" into a
condition code register!).

Suppose the true value of the sum is equal to 2**N + z.  This corresponds
to those situations where the carry bit is set.  Since we know that x and y
are both less than 2**N, and also greater than zero, we know that if the
carry bit is set, then z is less than either x or y.  This is so because:

  2**N + z = x + y

Subtract y from both sides, you get:

  (2**N - y) + z = x.

But (2**N - y) is greater than zero (and less than 2**N), so we have

  gt0 + z = x

or

  z < x.

Thus, "if carry bit set, then z < x" is shown.
"If z < x, then carry bit set" should be fairly obvious at this
point.

speaking for myself,

David Chase

In article jkn@wcap.centerline.com, chase@centerline.com (David Chase) writes:
>[This is really about C, unless it causes people working on the
>C++ standard to think about the language that they use to define
>the basic integer data types.  You might consider using the example
>carry-detecting code in an example, since this is not the first time
>that this question has come up.]
>
>> sigbern@ismennt.is (Sigurdur Bernhard Finnsson) writes:
>> >How is it possible in ANSI C++ to detect if an overflow occured
>> >on a binary integer number, the same operation as the Carry bit is for in
>> >assembler?
>
>In article <3t3u1c$jk6@engnews2.Eng.Sun.COM>, clamage@Eng.Sun.COM (Steve Clamage) writes:
>> In C and C++, arithmetic on unsigned integer types cannot overflow.
>> By language definition, unsigned arithmetic on a type with N bits is
>> performed modulo 2**N.
>
>> The only reliable and portable way to check for mathematical overflow
>> in C or C++ source code is to test before performing an operation
>> whether it will succeed. E.g.,
>>  if( a > 0 && b > 0 && a > MAX - b )
>>      ... result will overflow
>
>That's not the only way at all, and it certainly less efficient than
>one alternative.  Note that the carry bit corresponds to so-called
>"unsigned overflow", which IS well-defined at the assembly language
>level. If, as you claim, unsigned arithmetic operates within some
>modulus 2**N, then this is portable, though if the C/C++ "N" is not
>the same as the machine "N", then it will capture a different carry
>bit (the one corresponding to the smaller value of N, obviously).
>
>  unsigned x, y, z, c;
>  ...
>  z = x + y;
>  c = z < x; /* z < y will also work. */

Please note the word "portable" in my comment. The original poster said
he wanted to write standard-conforming C++ source code which would not
require modification as it was moved among different platforms.

Next, my "claim" about unsigned arithmetic is part of the definition
of C and C++, as explicitly stated in their respective standards.
Please don't confuse machine arithmetic with the defined meaning of
source code in a particular language. They are different things.

Next, if 'a' and 'b' have unsigned types, the tests against zero are not
needed and my example is equivalent to yours. You can test for overflow
before the addition or after it; for unsigned it doesn't matter.

>This could be implemented in a single instruction, if the compiler
>were up to it (IF the compiler register-allocated "c" into a
>condition code register!).

Boy, have we left portability behind now!

---
Steve Clamage, stephen.clamage@eng.sun.com

> In article jkn@wcap.centerline.com, chase@centerline.com (David Chase) writes:
> >  unsigned x, y, z, c;
> >  ...
> >  z = x + y;
> >  c = z < x; /* z < y will also work. */

In article <3tejac$eed@engnews2.Eng.Sun.COM>, clamage@Eng.Sun.COM (Steve Clamage) writes:
> Please note the word "portable" in my comment. The original poster said
> he wanted to write standard-conforming C++ source code which would not
> require modification as it was moved among different platforms.

Calm down a little bit -- the code I give is portable as well,
and more concise.  It merely requires use of modulo arithmetic.
Concise is better, because (on a good day) compiler writers may
eventually get around to matching these patterns and special-
casing them, and concise patterns are more likely to be remembered
and propagated, and they're easier to match.

> Next, if 'a' and 'b' have unsigned types, the tests against zero are not
> needed and my example is equivalent to yours. You can test for overflow
> before the addition or after it; for unsigned it doesn't matter.

>  if( a > 0 && b > 0 && a > MAX - b )
>      ... result will overflow

Equivalent answers, unlikely to be equivalent code.  Calculating
"a > MAX - b" requires that you construct MAX-b.  Chances are that
will require ONE WHOLE INSTRUCTION! :-)

> >This could be implemented in a single instruction, if the compiler
> >were up to it (IF the compiler register-allocated "c" into a
> >condition code register!).

> Boy, have we left portability behind now!

Given that we're talking about C and C++, we've never left
it.  Quick, what's the standard say this program is supposed
to print?

#include <stdio.h>
main() { printf("%d\n", -3/2) ; }

Is that -2, or -1?  (And if it was so important for efficiency
reasons to leave this unspecified, how come integer division is
often not even implemented in hardware?)

speaking for myself,

David Chase

Hi folks


How is it possible in ANSI C++ to detect if an overflow occured
on a binary integer number, the same operation as the Carry bit is for in
assembler?

I don't want to use inline assembler code because I have to make this
code as system independent as possible.

The main reason for me wanting to do this, is so I can manipulate in a
fast way 64bit integers, or even 96bit integers.  I need to have this
pretty fast, so it would be of great help if you knew instead of some
fast algorithms for such calculations.


With thanks


      ------------------------------------------------------------
     / Sigurdur Bernhard Finnsson /  UNIX is my religion, power /
    / sigbern@ismennt.is         /  and destiny..............  /
   ------------------------------------------------------------

sigbern@ismennt.is (Sigurdur Bernhard Finnsson) writes:


>How is it possible in ANSI C++ to detect if an overflow occured
>on a binary integer number, the same operation as the Carry bit is for in
>assembler?

In C and C++, arithmetic on unsigned integer types cannot overflow.
By language definition, unsigned arithmetic on a type with N bits is
performed modulo 2**N.

The results of overflow with signed arithmetic are undefined. A given
implementation might provide a way for you to test for it, but the
means of testing, if available, will vary among implementations.

The only reliable and portable way to check for mathematical overflow
in C or C++ source code is to test before performing an operation
whether it will succeed. E.g.,
 if( a > 0 && b > 0 && a > MAX - b )
     ... result will overflow

--
Steve Clamage, stephen.clamage@eng.sun.com

>The only reliable and portable way to check for mathematical overflow
>in C or C++ source code is to test before performing an operation
>whether it will succeed. E.g.,
> if( a > 0 && b > 0 && a > MAX - b )
>     ... result will overflow

In some cases, there is another reliable and portable way.  Do the operation
in a manner for which C/C++ guarantee a portable result, and check the result.
For example, if a and b are unsigned, it is always safe in C/C++ to compute
their sum.  A carry occurs if and only if the sum is less than one of the
addends.  Only one addend need be checked.  E.g.,

 unsigned sum = a + b;
 if( sum < a ) {
     ... "carry" was generated from sum.
 }

Arch D. Robison    Kuck & Associates Inc.
robison@kai.com    1906 Fox Drive
217-356-2288       Champaign IL 61820