An alternative to just adding overflow handling might be to add to C/C++
a portable assembler language, like the C-- language developed by Simon
Peyton Jones, see <http://www.dcs.gla.ac.uk/~simonpj/c--.html>.

  I have not followed the development of this language for some time, but
perhaps it can provide an input.

  Hans Aberg   * Anti-spam: Remove "REMOVE." from email address.
               * Email: Hans Aberg <haberg@REMOVE.member.ams.org>
               * Home Page: <http://www.matematik.su.se/~haberg/>
               * AMS member listing: <http://www.ams.org/cml/>
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

abrahams@motu.com wrote:
> ... on machines
> where the "do and detect" mechanism can be implemented (and this is an even
> narrower class than I previously thought in light of the undefined behavior
> mentioned above) ...

The class is not that narrow; most implementations do exactly what you'd
probably expect them to do. At worst, they produce a different number
than you might expect, but they're very unlikely to format your hard
disk. The effects of my suggestion would include removing that small
possibility, at least for the affected code.


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <35FF59F2.8B68DB3F@wizard.net>,
  "James Russell Kuyper Jr." <kuyper@wizard.net> wrote:

> You're depending there upon a conversion which produces implementation
> -specific results. However, in general you can expect negative values to
> be converted to large positive values, which will often not produce the
> desired effect.

As Mr. Williams (I think) pointed out in a different post, conversion of
signed to unsigned long is well-defined by the standard and not
implementation- specific. As you and he have also pointed out, my original
test gives different results from yours - incorrect ones. I've since amended
my test, but whether my amended test is more efficient than yours is *surely*
implementation-dependent!

-Dave

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

<abrahams@motu.com> wrote:
>In article <35FF1C83.41C6@wizard.net>,
>  James Kuyper <kuyper@wizard.net> wrote:
>> > Under the "As-if" rule, a compiler is allowed to make operations as
>> > fast as possible as long as the semantics of the program aren't
>> > changed. I don't believe any change to the standard is warranted
>> > here. The first method is allowed to be optimized into the second,
>> > internally.
>>
>> No it isn't; they have radically different semantics. "predict and
>> avoid" never executes the expression that would otherwise overflow, the
>> "do and detect" method does.
>
>The addition of two built-in integer types has no externally observable
>semantics. It doesn't matter whether the addition is actually ever performed
>or not, only whether the results are stored.

A conforming implementation may trap overflow of addition, even
of unsigned values.

Section 1.9 [intro.execution] of the C++ IS mentions in paragraph 15:

   On a machine in which overflows produce an exception...
   the implementation cannot rewrite this expression [involving
   ints, because the rewritten expression] ... would produce an
   exception while the original expression would not.

The C standard has similar language.  Also, this from 5 [expr]:

   -5- If during the evaluation of an expression, the result is not
   mathematically defined or not in the range of representable values
   for its type, the behavior is undefined, unless such an expression
   is a constant expression (expr.const), in which case the program is
   ill-formed.

(Fortunately, left-shift operations on unsigned values are safe.)

--
Nathan Myers
ncm@nospam.cantrip.org  http://www.cantrip.org/
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <6todj3$s1u$1@nnrp1.dejanews.com>,
  markw65@my-dejanews.com wrote:
>
> In article <6tmlcg$sje$1@nnrp1.dejanews.com>,
>   abrahams@motu.com wrote:
> >bool AdditionWillOverflow( const unsigned long a, const unsigned long b )
> >{
> >  return a > ~b;
> >}
> >
>  [snip]
> >
> > I got over my laziness. This works just fine:
> >
> > bool AdditionWillOverflow( const long a, const long b )
> > {
> >   return AdditionWillOverflow( static_cast<unsigned long>(a),
> > static_cast<unsigned_long>(b) );
> > }
> >
>
> Actually, no it doesnt. It just checks whether adding the corresponding
> unsigned integers will carry. Which is not a very useful operation on signed
> numbers.

Alright, let's start by noting that adding signed integers of the
same size and different signs can never overflow. If they're the
same sign, the test above should work correctly.

So try this:
[Warning: untested code, I might have slipped a bit somewhere]

    // Note: Changed signature from const long to long.
    // They are passed by value!
    bool AdditionWillOverflow(long a, long b)
    {
        return ((a<0) == (b<0)) && (a > ~b);
    }

--
AllanW@my-dejanews.com is a "Spam Magnet" -- never read.
Please reply in USENET only, sorry.

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

I wrote:
> > I'm not sure that your code is correct, but it is certainly more expensive

James Kuyper <kuyper@wizard.net> wrote:
> I think it is; do you see a problem?

No, I don't, and I apologize for my vague implication that there might have
been a mistake.

The reason I posted the unsigned version, I've discovered, is that I was
referring to an implementation I wrote of double-precision arithmetic. My
implementation stores all but the most significant segment of a multiple-
precision number as unsigned long. I think this works best for many reasons,
not least because overflow detection is cheap. Whether there's a really cheap
overflow test for signed numbers may not be so important after all.

-Dave

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <35FF1C83.41C6@wizard.net>, James Kuyper <kuyper@wizard.net> wrote:
>For signed integers it's not guaranteed to work under the standard. It
>depends upon how negative integers are stored, which is
>implementation-defined.

  So it sounds as though one should have new type (perhaps in connection
with a new "binary" type) in which one can ensure that signed numbers are
two's complement.

  Hans Aberg   * Anti-spam: Remove "REMOVE." from email address.
               * Email: Hans Aberg <haberg@REMOVE.member.ams.org>
               * Home Page: <http://www.matematik.su.se/~haberg/>
               * AMS member listing: <http://www.ams.org/cml/>
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

abrahams@motu.com wrote:
>
> In article <35FF59F2.8B68DB3F@wizard.net>,
>   "James Russell Kuyper Jr." <kuyper@wizard.net> wrote:
>
> > You're depending there upon a conversion which produces implementation
> > -specific results. However, in general you can expect negative values to
> > be converted to large positive values, which will often not produce the
> > desired effect.
>
> As Mr. Williams (I think) pointed out in a different post, conversion of
> signed to unsigned long is well-defined by the standard and not

Yes, I mis-stated the problem, something which I've corrected in a
different post.

> implementation- specific. As you and he have also pointed out, my original
> test gives different results from yours - incorrect ones. I've since amended
> my test, but whether my amended test is more efficient than yours is *surely*
> implementation-dependent!

Simultaneity is even more of a problem in newsgroups than in relativity
:-(. I'm not sure whether I've seen your final amended version, or only
an intermediate step. I don't know whether you've seen the latest of my
responses on this issue; it's not the one that your message is a reply
to.

The latest version I've seen of your condition is

 ( x > 0 ) == ( y > 0 ) && (unsigned long)x > ~(unsigned long)y

That version still doesn't work; it misses all of the actual overflows
in the region a>0 && b>0, because it implicitly tests versus ULONG_MAX
rather than against LONG_MAX. Typically, ULONG_MAX >= 2*(unsigned
long)LONG_MAX (I think that's guaranteed, but I've forgotten where the
relevant clauses in the staandard are located), so your condition can't
be triggered in that region. It also misses all of the overflows in the
region a<0 && b<0, which overflow LONG_MIN.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <3602D74C.A8B00807@wizard.net>, James Russell Kuyper Jr.
<kuyper@wizard.net> writes
>Typically, ULONG_MAX >= 2*(unsigned
>long)LONG_MAX (I think that's guaranteed, but I've forgotten where the
>relevant clauses in the staandard are located), so your condition can't
>be triggered in that region.

Typically, yes (well almost, you forgot +1), required? No.  Two things
are required of unsigned types
1) They meet the minimum specified range
2) They can represent the positive range (including 0) of the
corresponding signed type.


Francis Glassborow      Chair of Association of C & C++ Users
64 Southfield Rd
Oxford OX4 1PA          +44(0)1865 246490
All opinions are mine and do not represent those of any organisation
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Francis Glassborow wrote:
>
> In article <3602D74C.A8B00807@wizard.net>, James Russell Kuyper Jr.
> <kuyper@wizard.net> writes
> >Typically, ULONG_MAX >= 2*(unsigned
> >long)LONG_MAX (I think that's guaranteed, but I've forgotten where the
> >relevant clauses in the staandard are located), so your condition can't
> >be triggered in that region.
>
> Typically, yes (well almost, you forgot +1), required? No. ...

I didn't forget the +1, I was stating the condition which rendered his
overflow test useless, not the condition which defines the
signed-unsigned relationship.

> ... Two things
> are required of unsigned types
> 1) They meet the minimum specified range
> 2) They can represent the positive range (including 0) of the
> corresponding signed type.

The standard also says that they must take up the same amount of
storage. However, it doesn't require that either type uses all of the
bits in the bytes it takes up.


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

AllanW@my-dejanews.com wrote:
> In article <6todj3$s1u$1@nnrp1.dejanews.com>,
>   markw65@my-dejanews.com wrote:
> >
> > In article <6tmlcg$sje$1@nnrp1.dejanews.com>,
> >   abrahams@motu.com wrote:
> > >bool AdditionWillOverflow( const unsigned long a, const unsigned long b )
> > >{
> > >  return a > ~b;
> > >}
> > >
> >  [snip]
> > >
> > > I got over my laziness. This works just fine:
> > >
> > > bool AdditionWillOverflow( const long a, const long b )
> > > {
> > >   return AdditionWillOverflow( static_cast<unsigned long>(a),
> > > static_cast<unsigned_long>(b) );
> > > }
> > >
> >
> > Actually, no it doesnt. It just checks whether adding the corresponding
> > unsigned integers will carry. Which is not a very useful operation on signed
> > numbers.
>
> Alright, let's start by noting that adding signed integers of the
> same size and different signs can never overflow. If they're the
> same sign, the test above should work correctly.

No it doesn't. It implicitly tests against ULONG_MAX, instead of
LONG_MAX.

> So try this:
> [Warning: untested code, I might have slipped a bit somewhere]
>
>     // Note: Changed signature from const long to long.
>     // They are passed by value!
>     bool AdditionWillOverflow(long a, long b)
>     {
>         return ((a<0) == (b<0)) && (a > ~b);
>     }

AdditionWillOverflow(0L,0L) is 1, and so is
AdditionWillOverflow(LONG_MAX/2,LONG_MAX/2+1). It still doesn't catch
any of the negative overflows. Try again.

If nothing else, these exchanges have shown that:
1. Writing code which correctly predicts overflow is tricky. That argues
in favor of making the prediction method part of the standard.

2. The proposed expressions are getting to be as complicated as the
expression which I believe is correct:

 a>0 ? b>LONG_MAX-a : b<LONG_MIN-a

An expression that complicated (particularly since there are several
equivalent expressions) is not likely to be detected by the compiler as
being equivalent to an overflow check. As a result, compilers are
unlikely to optimize:

 if(a>0 ? b>LONG_MAX-a : b<LONG_MIN-a)
  /* overflow handling code. */;
 else
  c = a+b;

down to the equivalent of (for example):

 load a into register 1
 load b into register 2
 add register 2 to register 1
 if overflow flag is set, jump to overflow_handling_code
 store register 1 in c
        jump to overflow_end
 overflow_handling_code:
 ...
 overflow_end:

Therefore, a more direct way of getting them to produce such code should
be made available.


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Nathan Myers wrote:
>
> A conforming implementation may trap overflow of addition, even
> of unsigned values.

At least for C, there is no such thing as overflow for unsigned values:

 A computation involving unsigned operands can never overflow,
 because a result that cannot be represented by the resulting
 unsigned integer type is reduced modulo the number that is one
 greater than the largest value that can be represented by the
 resulting unsigned integer type.

(C9X FCD 6.2.5p9 similar text appears in C90).

-Larry Jones

I just can't identify with that kind of work ethic. -- Calvin
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

abrahams@motu.com wrote:
>
> In article <haberg-1509981216380001@sl74.modempool.kth.se>,
>   haberg@REMOVE.matematik.su.se (Hans Aberg) wrote:
> >
> > In article <35FC7F56.1CFB@wizard.net>, James Kuyper <kuyper@wizard.net> wrote:
> > >There are two basic ways to handle the possibility of overflow. The
> > >first is "predict and avoid".
> > ...
> > In article <6tjscc$k9i$1@nnrp1.dejanews.com>, abrahams@motu.com wrote:
> > >... the appropriate test for unsigned numbers:
> > >
> > >if ( a > ~b ) { /* handle overflow */ }
> > >
> > >On most architectures the above test ought to work for signed numbers, too.

No, it won't. For one thing, it only tests one boundary, whereas signed
integers need to worry about going below LONG_MIN, as well as going
above LONG_MAX.

> >   This is the metod I think most want to avoid, as the code becomes messy
> > having potential for being slow. The more efficient version presented by
> > <abrahams@motu.com> has the problem it does not express what one wants to
> > program, and this is a sign of that the language does not have the
> > capacity of expressing what the programmer has in mind.
>
> One wonderful thing about C++ is that you can write facilities to express
> almost anything readably. In this case, a simple function works:
>
> bool AdditionWillOverflow( const unsigned long a, const unsigned long b)
> {
>   return a > ~b;
> }
>
> >   As <abrahams@motu.com> points out, one cannot be sure it works for
> > signed numbers.
>
> I didn't point that out, I was just leaving a little wiggle room because I was
> too lazy to look up the rules in the standard.
>
> >: I have not checked it in detail, but it seems me the
> > standard should fix those details for signed numbers, so that one knows
> > how overflows are handled.
>
> I got over my laziness. This works just fine:
>
> bool AdditionWillOverflow( const long a, const long b )
> {
>   return AdditionWillOverflow( static_cast<unsigned long>(a),
> static_cast<unsigned_long>(b) );
> }

You're depending there upon a conversion which produces implementation
-specific results. However, in general you can expect negative values to
be converted to large positive values, which will often not produce the
desired effect.

I wrote test code comparing that expression with mine:
-----------------------------------------------------------------------
#include <cstdio>
#include <climits>
bool AdditionWillOverflow(const long a, const long b)
{
    return a>0 ? b>LONG_MAX-a : b<LONG_MIN-a;
}

bool AdditionWillOverflow(const unsigned long a, const unsigned long b)
{
    return a > ~b;
}

int main(void)
{
    long list[]={LONG_MIN, LONG_MIN/2-1, LONG_MIN/2, 0,
        LONG_MAX/2, LONG_MAX/2+1, LONG_MAX};
    int i,j;
#define N    (int)(sizeof(list)/sizeof(list[0]))
    for(i=0; i<N; i++){
        for(j=0; j<N; j++){
     printf("%d %d:", AdditionWillOverflow(list[i], list[j]),
               AdditionWillOverflow(static_cast<unsigned long>(list[i]),
               static_cast<unsigned long>(list[j]) ));
            printf("%20ld+%20ld=%20ld\n", list[i],
list[j],                list[i]+list[j]);
        }
    }

    return 0;
}
-----------------------------------------------------------------------
And I obtained the following output:

1 1:         -2147483648+         -2147483648=                   0
1 1:         -2147483648+         -1073741825=          1073741823
1 1:         -2147483648+         -1073741824=          1073741824
0 0:         -2147483648+                   0=         -2147483648
0 0:         -2147483648+          1073741823=         -1073741825
0 0:         -2147483648+          1073741824=         -1073741824
0 0:         -2147483648+          2147483647=                  -1
1 1:         -1073741825+         -2147483648=          1073741823
1 1:         -1073741825+         -1073741825=          2147483646
1 1:         -1073741825+         -1073741824=          2147483647
0 0:         -1073741825+                   0=         -1073741825
0 0:         -1073741825+          1073741823=                  -2
0 0:         -1073741825+          1073741824=                  -1
0 1:         -1073741825+          2147483647=          1073741822
1 1:         -1073741824+         -2147483648=          1073741824
1 1:         -1073741824+         -1073741825=          2147483647
0 1:         -1073741824+         -1073741824=         -2147483648
0 0:         -1073741824+                   0=         -1073741824
0 0:         -1073741824+          1073741823=                  -1
0 1:         -1073741824+          1073741824=                   0
0 1:         -1073741824+          2147483647=          1073741823
0 0:                   0+         -2147483648=         -2147483648
0 0:                   0+         -1073741825=         -1073741825
0 0:                   0+         -1073741824=         -1073741824
0 0:                   0+                   0=                   0
0 0:                   0+          1073741823=          1073741823
0 0:                   0+          1073741824=          1073741824
0 0:                   0+          2147483647=          2147483647
0 0:          1073741823+         -2147483648=         -1073741825
0 0:          1073741823+         -1073741825=                  -2
0 0:          1073741823+         -1073741824=                  -1
0 0:          1073741823+                   0=          1073741823
0 0:          1073741823+          1073741823=          2147483646
0 0:          1073741823+          1073741824=          2147483647
1 0:          1073741823+          2147483647=         -1073741826
0 0:          1073741824+         -2147483648=         -1073741824
0 0:          1073741824+         -1073741825=                  -1
0 1:          1073741824+         -1073741824=                   0
0 0:          1073741824+                   0=          1073741824
0 0:          1073741824+          1073741823=          2147483647
1 0:          1073741824+          1073741824=         -2147483648
1 0:          1073741824+          2147483647=         -1073741825
0 0:          2147483647+         -2147483648=                  -1
0 1:          2147483647+         -1073741825=          1073741822
0 1:          2147483647+         -1073741824=          1073741823
0 0:          2147483647+                   0=          2147483647
1 0:          2147483647+          1073741823=         -1073741826
1 0:          2147483647+          1073741824=         -1073741825
1 0:          2147483647+          2147483647=                  -2

The two expressions produce different results, and mine correctly
predicts the cases that overflow.


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

James Kuyper wrote:
>
> The second method is "do and detect". This can't be done in current
> C/C++ code, but it can be done on many platforms using assembler. With
> the proposal detailed below, this could be done in C/C++ using the
> following code:
>
>         c = a+b;
>         if(__overflow()){
>                 /* Handle the overflow */
>         }
>
> The __overflow() would be replaced, on implementations that can do so,
> by inline code that tests the overflow flag. This drops the overhead
> to a single comparison, which is still enough to double the exection
> time on some platforms.
> I believe this can be done in a non-portable way using asm() on some
> implementations. However, I think it's legitimate to ask for a
> portable way of accessing this feature.

I don't know if it's intrinsic in the nature of ints vs. floats, or if
I'm just used to the x86 world. There, one is most concerned about
overflow (not to mention other numeric exceptions) when dealing with
floating point arithmetic. And one of the features that IEEE floating
point has is the ability to produce "infinity" in response to an
overflow, which is often a good way to handle it. One advantage of this
is that it allows a complicated expression to be written naturally, with
a single test at the end, since "infinity" will remain "infinity" unless
you divide by it, in which case it correctly becomes zero.

There may be situations where this handling is inappropriate, but it is
part of IEEE, and it would be a shame if a future C++ standard gave some
access to overflow detection without providing some means of handling
"sticky" errors. Without this ability, you'd have to test after every
binary operation.

--

Ciao,
Paul


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

abrahams@motu.com wrote:
>
> James Kuyper <kuyper@wizard.net> wrote:
>
> > There are two basic ways to handle the possibility of overflow. The
> > first is "predict and avoid". Example:
> >
> >       if(a>0 ? b>LONG_MAX-a : b<LONG_MIN-a){
> >               /* Avoid overflow       */
> >       }else c = a+b;
> >
> > However, this method is fairly expensive: the overhead for
> > this example is 2 comparisons and 1 subtraction, for a single addition.
>
> I'm not sure that your code is correct, but it is certainly more expensive

I think it is; do you see a problem?

> than the appropriate test for unsigned numbers:
>
> if ( a > ~b ) { /* handle overflow */ }

As usual, unsigned numbers are simpler; there's only one limit to worry
about, and ULONG_MAX-b is guaranteed to be identical to ~b. I thought
about including an unsigned example, but I figured the signed case was
sufficient, and more instructive.



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <35FF1C83.41C6@wizard.net>,
  James Kuyper <kuyper@wizard.net> wrote:
> > I got over my laziness. This works just fine:

> [Slightly more complicated code, equivalent to above.]

> > Really, one ought to get over one's own laziness and check the standard to
> > see if there's a way to accomodate one's needs before proposing that it be
> > changed, much less presuming that it needs to be "fixed"!

> For signed integers it's not guaranteed to work under the standard. It
> depends upon how negative integers are stored, which is
> implementation-defined.

The behaviour of the code as written _is_ guaranteed by the standard, in the
sense that it is implementation independant. It just doesnt test for overflow
(see my previous post).

Conversion of a signed number to an unsigned one is well defined. Regardless
of the underlying representation of the signed integer, negative ints get
mapped to 2^n + i (ie the result of converting a negative integer to unsigned
is exactly what you would get by reinterpreting the bit pattern of a 2s
complement signed number).

Mark Williams

-----=3D=3D Posted via Deja News, The Leader in Internet Discussion =3D=3D=
-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <6tp2vu$mfo$1@nnrp1.dejanews.com>, abrahams@motu.com wrote:

> The addition of two built-in integer types has no externally observable
> semantics. It doesn't matter whether the addition is actually ever performed
> or not, only whether the results are stored.

Usually there is no observable behavior. But an overflow produces
"undefined behavior" and that can be anything, and it can be observable.
If I write

   INT_MAX + 1;

I produce undefined behavior. Of course, the compiler is free to optimise
it away, and on the compiler I currently use there is no observable
behavior. But it IS not portable.


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <christian.bau-1709981117350001@christian-mac.isltd.insignia.com>,
  christian.bau@isltd.insignia.com (Christian Bau) wrote:
>
> In article <6tp2vu$mfo$1@nnrp1.dejanews.com>, abrahams@motu.com wrote:
>
> > The addition of two built-in integer types has no externally observable
> > semantics. It doesn't matter whether the addition is actually ever performed
> > or not, only whether the results are stored.
>
> Usually there is no observable behavior. But an overflow produces
> "undefined behavior" and that can be anything, and it can be observable.

Once again, I have been careless. Probably I have shot my credibility on this
topic and should quit the thread for now ;). Still, I assert that on machines
where the "do and detect" mechanism can be implemented (and this is an even
narrower class than I previously thought in light of the undefined behavior
mentioned above), the "detect and do" mechanism can be optimized to identical
code. That is, of course, unless you want to somehow exploit the undefined
behavior that results from "do and detect".

-Dave

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <35FC7F56.1CFB@wizard.net>, James Kuyper <kuyper@wizard.net> wrote:

> The second method is "do and detect". This can't be done in current
> C/C++ code, but it can be done on many platforms using assembler. With
> the proposal detailed below, this could be done in C/C++ using the
> following code:
>
>         c = a+b;
>         if(__overflow()){
>                 /* Handle the overflow */
>         }
>
> The __overflow() would be replaced, on implementations that can do so,
> by inline code that tests the overflow flag. This drops the overhead to
> a single comparison, which is still enough to double the exection time
> on some platforms.
> I believe this can be done in a non-portable way using asm() on some
> implementations. However, I think it's legitimate to ask for a portable
> way of accessing this feature.

The following might fit better:

   if (__overflow (c = a+b)) { /* Handle the overflow */ }

   On an implementation where the compiler accepts this, the expression
__overflow (c = a+b) is equivalent to (c = a+b, 0) if the left hand
expression was evaluated completely without any overflow and equivalent to
(c = a+b, 1) otherwise. Any subexpression that produces an overflow will
yield an unspecified value, but no undefined behavior. It is unspecified
whether side effects that are produced after an overflow happens will
occur or not.

Obviously this wording is far from perfect. But it is much more specific
about where overflows have to be detected. For the example above, a
compiler should be able to produce code as good as any assembler
programmer could.


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <35FC7F56.1CFB@wizard.net>, James Kuyper <kuyper@wizard.net> wrote:
>There are two basic ways to handle the possibility of overflow. The
>first is "predict and avoid".
...
In article <6tjscc$k9i$1@nnrp1.dejanews.com>, abrahams@motu.com wrote:
>... the appropriate test for unsigned numbers:
>
>if ( a > ~b ) { /* handle overflow */ }
>
>On most architectures the above test ought to work for signed numbers, too.

  This is the metod I think most want to avoid, as the code becomes messy
having potential for being slow. The more efficient version presented by
<abrahams@motu.com> has the problem it does not express what one wants to
program, and this is a sign of that the language does not have the
capacity of expressing what the programmer has in mind.

  As <abrahams@motu.com> points out, one cannot be sure it works for
signed numbers: I have not checked it in detail, but it seems me the
standard should fix those details for signed numbers, so that one knows
how overflows are handled.

  For example, signed and unsigned addition of fixed size integers are the
same, only the underlying bits differ. One needs also to think on how the
overflows behave in the case when chained together to multiprecision
numbers. (I cannot tell the details straight off.)

  In my view, the different integer types of C and C++ should be labelled
as fixed size binary types with different binary and arithmetic
operations, and not as integer types: So, with this view, there is only
one 32-bit type on a 32-bit machine, not two, signed and unsigned int.
Then one has various operations on this type: Right/left shifts with
under/overflow, rotation, signed/unsigned arithmetic with overflow, and
logical bit operations.

  The way C/C++ are right now, one can perhaps go not that way,
introducing such a more complicated type, but this is the picture I have
in my mind. Otherwise, a more advanced binary type could also be such that
it ensures that bitfields are implemented as bits of a word; this is
slower, but some applications require that one knows the binary
implementation. It would suffice with one type "binary<unsigned k>", where
k is the number of bits; the compiler would choose the appropriate number
of words to put it into as a consecutive bit-field.

>The second method is "do and detect". This can't be done in current
>C/C++ code, but it can be done on many platforms using assembler.

  I think variations of this is what one should have: It has the potential
for creating fast code, as the problem can be put onto the CPU, in as much
as it has the capacity of doing it.

> With
>the proposal detailed below, this could be done in C/C++ using the
>following code:
>
>        c = a+b;
>        if(__overflow()){
>                /* Handle the overflow */
>        }

  In the variations I suggested, one might have a function
    pair<T, T> add(T, T)
where T is a fixed size integer type. Then the code might look
    c = add(a, b);
    if (c.second) ...    // Handle overflow.
With a new binary type one might have it look like:
    c = a + b;
    if (c.second) ...    // Handle overflow.

  In C++, one might use exceptions. Then the code might look
    try {
        c = a + b;          // Binary type throws exception if overflow.
    }
    catch (binary_add x) {  // Put overflow into x and handle exception.
        ...
    }
This might be OK if there is no overhead when exceptions are not thrown,
and if cases with overflows are allowed to be slower. (This is the case of
an multiprecision Integer type which should substitute as an "int" for
numbers small enough to fit into a word.)

  Hans Aberg   * Anti-spam: Remove "REMOVE." from email address.
               * Email: Hans Aberg <haberg@REMOVE.member.ams.org>
               * Home Page: <http://www.matematik.su.se/~haberg/>
               * AMS member listing: <http://www.ams.org/cml/>


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <haberg-1509981216380001@sl74.modempool.kth.se>,
  haberg@REMOVE.matematik.su.se (Hans Aberg) wrote:
>
> In article <35FC7F56.1CFB@wizard.net>, James Kuyper <kuyper@wizard.net> wrote:
> >There are two basic ways to handle the possibility of overflow. The
> >first is "predict and avoid".
> ...
> In article <6tjscc$k9i$1@nnrp1.dejanews.com>, abrahams@motu.com wrote:
> >... the appropriate test for unsigned numbers:
> >
> >if ( a > ~b ) { /* handle overflow */ }
> >
> >On most architectures the above test ought to work for signed numbers, too.
>
>   This is the metod I think most want to avoid, as the code becomes messy
> having potential for being slow. The more efficient version presented by
> <abrahams@motu.com> has the problem it does not express what one wants to
> program, and this is a sign of that the language does not have the
> capacity of expressing what the programmer has in mind.

One wonderful thing about C++ is that you can write facilities to express
almost anything readably. In this case, a simple function works:

bool AdditionWillOverflow( const unsigned long a, const unsigned long b )
{
  return a > ~b;
}

>   As <abrahams@motu.com> points out, one cannot be sure it works for
> signed numbers.

I didn't point that out, I was just leaving a little wiggle room because I was
too lazy to look up the rules in the standard.

>: I have not checked it in detail, but it seems me the
> standard should fix those details for signed numbers, so that one knows
> how overflows are handled.

I got over my laziness. This works just fine:

bool AdditionWillOverflow( const long a, const long b )
{
  return AdditionWillOverflow( static_cast<unsigned long>(a),
static_cast<unsigned_long>(b) );
}

Really, one ought to get over one's own laziness and check the standard to
see if there's a way to accomodate one's needs before proposing that it be
changed, much less presuming that it needs to be "fixed"!


> >The second method is "do and detect". This can't be done in current
> >C/C++ code, but it can be done on many platforms using assembler.
>
>   I think variations of this is what one should have: It has the potential
> for creating fast code, as the problem can be put onto the CPU, in as much
> as it has the capacity of doing it.

Under the "As-if" rule, a compiler is allowed to make operations as fast as
possible as long as the semantics of the program aren't changed. I don't
believe any change to the standard is warranted here. The first method is
allowed to be optimized into the second, internally.

-Dave

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <6tmlcg$sje$1@nnrp1.dejanews.com>,
  abrahams@motu.com wrote:
>bool AdditionWillOverflow( const unsigned long a, const unsigned long b )
>{
>  return a > ~b;
>}
>
 [snip]
>
> I got over my laziness. This works just fine:
>
> bool AdditionWillOverflow( const long a, const long b )
> {
>   return AdditionWillOverflow( static_cast<unsigned long>(a),
> static_cast<unsigned_long>(b) );
> }
>

Actually, no it doesnt. It just checks whether adding the corresponding
unsigned integers will carry. Which is not a very useful operation on signed
numbers.

eg AdditionWillOverflow(1, -1) returns true, when there is clearly no overflow
(but of course 1 + 0xffff...fff does generate a carry).

Mark Williams



-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

abrahams@motu.com wrote:
>
> In article <haberg-1509981216380001@sl74.modempool.kth.se>,
>   haberg@REMOVE.matematik.su.se (Hans Aberg) wrote:

> > In article <35FC7F56.1CFB@wizard.net>, James Kuyper <kuyper@wizard.net> wrote:
> > >There are two basic ways to handle the possibility of overflow. The
> > >first is "predict and avoid".
> > ...
> > In article <6tjscc$k9i$1@nnrp1.dejanews.com>, abrahams@motu.com wrote:
> > >... the appropriate test for unsigned numbers:
> > >
> > >if ( a > ~b ) { /* handle overflow */ }

> > >On most architectures the above test ought to work for signed numbers, too.
 ...
> >   As <abrahams@motu.com> points out, one cannot be sure it works for
> > signed numbers.

> I didn't point that out, I was just leaving a little wiggle room because I was
> too lazy to look up the rules in the standard.

> >: I have not checked it in detail, but it seems me the
> > standard should fix those details for signed numbers, so that one knows
> > how overflows are handled.

> I got over my laziness. This works just fine:

[Slightly more complicated code, equivalent to above.]

> Really, one ought to get over one's own laziness and check the standard to
> see if there's a way to accomodate one's needs before proposing that it be
> changed, much less presuming that it needs to be "fixed"!

For signed integers it's not guaranteed to work under the standard. It
depends upon how negative integers are stored, which is
implementation-defined.

[Back to me:]
> > >The second method is "do and detect". This can't be done in current
> > >C/C++ code, but it can be done on many platforms using assembler.
> >
> >   I think variations of this is what one should have: It has the potential
> > for creating fast code, as the problem can be put onto the CPU, in as much
> > as it has the capacity of doing it.
>
> Under the "As-if" rule, a compiler is allowed to make operations as fast as
> possible as long as the semantics of the program aren't changed. I don't
> believe any change to the standard is warranted here. The first method is
> allowed to be optimized into the second, internally.

No it isn't; they have radically different semantics. "predict and
avoid" never executes the expression that would otherwise overflow, the
"do and detect" method does. Furthermore, the "do and detect" method
examines a condition that has no equivalent under the current C/C++
standards. Any form of that idea requires a change or an extension to
the standards.


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <6todj3$s1u$1@nnrp1.dejanews.com>,
  markw65@my-dejanews.com wrote:

> In article <6tmlcg$sje$1@nnrp1.dejanews.com>,
>   abrahams@motu.com (lazily) wrote:
> > I got over my laziness. This works just fine:
 <snip>
> Actually, no it doesnt. It just checks whether adding the corresponding
> unsigned integers will carry. Which is not a very useful operation on signed
> numbers.

Brain fault! Of course Mr. Williams is correct. You have to check that the
numbers have the same sign first.

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <35FF1C83.41C6@wizard.net>,
  James Kuyper <kuyper@wizard.net> wrote:
> > Under the "As-if" rule, a compiler is allowed to make operations as fast as
> > possible as long as the semantics of the program aren't changed. I don't
> > believe any change to the standard is warranted here. The first method is
> > allowed to be optimized into the second, internally.
>
> No it isn't; they have radically different semantics. "predict and
> avoid" never executes the expression that would otherwise overflow, the
> "do and detect" method does.

The addition of two built-in integer types has no externally observable
semantics. It doesn't matter whether the addition is actually ever performed
or not, only whether the results are stored.

> Furthermore, the "do and detect" method
> examines a condition that has no equivalent under the current C/C++
> standards. Any form of that idea requires a change or an extension to
> the standards.

Not so. Maybe this example will better illustrate my point:

long DoAdditionAndDetect( long x, long y )
{
  long result = x + y;
  // Corrected detection (see another post):
  if ( ( x > 0 ) == ( y > 0 ) && (unsigned long)x > ~(unsigned long)y )
     throw overflow();
  return result;
}

The compiler is free to optimize the detection above into a check of some
internal overflow flag. Of course, one could argue that compilers will never
be that smart. I'm inclined to agree that such an optimization is unlikely.
However, I would be extremely reluctant to add a core language feature to the
standard which is not actually portable (as you pointed out, some
implementations might not be able to support your __overflow extension).

-Dave

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Hans Aberg wrote in the "Multiprecision numerics" thread on
comp.std.c++:
...
>   Please note that I have not specified how the implementation of such
> features should be supported in C++:

That's been one of the problems. It helps to be more specific. See
below.

>   One way to go would be to review how C++ could better support the things
> that can be done at an assembler level (giving access to overflows and the
> like). ...

For example, I didn't realise that this was one of the options you
wanted us to consider. The desire to handle overflows properly is far
more basic and far more widespread than the need to do multiprecision
numerics, and I could even support such a proposal. I've cross-posted to
comp.std.c, since the need is just about as great in C as in C++.
However, the proposal needs to be much more specific. I'll put one
together and informal one for you:

(Very basic review, just to establish context:)
There are two basic ways to handle the possibility of overflow. The
first is "predict and avoid". Example:

 if(a>0 ? b>LONG_MAX-a : b<LONG_MIN-a){
  /* Avoid overflow */
 }else c = a+b;

This can always be implemented in C/C++ code, and any decent compiler
should implement it just about as efficiently as equivalent hand-crafted
assembler. However, this method is fairly expensive: the overhead for
this example is 2 comparisons and 1 subtraction, for a single addition.

The second method is "do and detect". This can't be done in current
C/C++ code, but it can be done on many platforms using assembler. With
the proposal detailed below, this could be done in C/C++ using the
following code:

 c = a+b;
 if(__overflow()){
  /* Handle the overflow */
 }

The __overflow() would be replaced, on implementations that can do so,
by inline code that tests the overflow flag. This drops the overhead to
a single comparison, which is still enough to double the exection time
on some platforms.
I believe this can be done in a non-portable way using asm() on some
implementations. However, I think it's legitimate to ask for a portable
way of accessing this feature.

On some platforms, I have no idea how many, the "do and detect" method
cannot be implemented as described. However, it can be emulated using a
variant of the "predict and avoid" method. Some users will not want to
accept the higher cost of that strategy; other users will want to handle
overflow safely, regardless of the cost. Therefore, there should be a
macro, indicating that overflow detection is directly implemented, to
allow conditional compilation of such code. I nominate
_OVERFLOW_DETECTABLE as the name.

I'll tentatively suggest <limits.h> as the site for the #define of that
macro, and for the following declaration:

 bool __overflow();

__overflow() returns 1 if the last arithmetic (numeric?) operation
preceeding it overflowed, and 0 otherwise. Alternative: it's 1 if any
arithmetic operation in the preceeding statement overflowed. This
description probably needs to be improved, to handle expressions such
as:

 array[i] = a+b;
 mystruct->member = a+b;

The LHS of those statements contain hidden pointer additions that might
themselves trigger overflow, and which are permitted to occur after the
additions which occur on the RHS. I can't decide whether __overflow()
should include or exclude those pointer overflows; they'll usually
result (on decent operation systems) in memory violations anyway.
However, making such a distinction will make the idea harder to
implement.

#ifndef _OVERFLOW_DETECTABLE, then __overflow() requires that the last
preceeding arithmetic operation be instrumented with something like the
"predict and avoid" method, to emulate overflow detection.

To protect many statements at once, another method would be useful: Add
a new #pragma named __signal_overflow which can be turned on and off.
While active, all arithmetic operations must be compiled to raise() an
appropriate signal. At the start of a translation unit, it should of
course be off. In C++, throw(overflow_error) would be more appropriate;
I like this idea a lot better than the signal method. Inherently, either
of these is a less well-controlled feature than __overflow().

Whenever __overflow() or __signal_overflow are active, the affected
arithmetic expressions would no longer have undefined behavior if they
overflow. Instead they would throw(), raise(), or produce
implementation-defined (or perhaps unspecified) values, as appropriate.
On platforms where overflow is inherently more dangerous than that, an
implementation must use the "predict and avoid" strategy.

==============================================================================
That was not intended to be a formal proposal, because the C++ standard
is finished, and the C9X standard is closed to changes of this
magnitude. However, if you would like to see something like this
implemented, start asking implementors to consider it now. When, several
years from now, formal discussions are started on the next version of
the standard, there will be some basis for judging the merits of the
change. That's why I wrote it using names from the namespace reserved to
implementations.


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

James Kuyper <kuyper@wizard.net> wrote:

> There are two basic ways to handle the possibility of overflow. The
> first is "predict and avoid". Example:
>
>  if(a>0 ? b>LONG_MAX-a : b<LONG_MIN-a){
>   /* Avoid overflow */
>  }else c = a+b;
>
> However, this method is fairly expensive: the overhead for
> this example is 2 comparisons and 1 subtraction, for a single addition.

I'm not sure that your code is correct, but it is certainly more expensive
than the appropriate test for unsigned numbers:

if ( a > ~b ) { /* handle overflow */ }

On most architectures the above test ought to work for signed numbers, too.

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]