Unsigned integer overflow detection

Discussion in 'C++' started by Raymond, Aug 20, 2007.

  1. Raymond

    Raymond Guest

    Source:
    http://moryton.blogspot.com/2007/08/detecting-overflowunderflow-when.html

    Example from source:

    char unsigned augend (255);
    char unsigned const addend (255);
    char unsigned const sum (augend + addend);

    if (sum < augend)
    {
    std::puts ("Overflowed!");
    }

    sum = augend + addend
    sum = 255 + 255
    sum = 510 modulo 256 // Behind the scenes.
    sum = 254

    Does it touch any implementation defined or undefined behaviour, or was
    that specific to signed integers (on some platforms)?

    What other methods are there for detecting unsigned integer overflow
    and/or underflow in C++?
     
    Raymond, Aug 20, 2007
    #1
    1. Advertising

  2. * Raymond:
    > Source:
    > http://moryton.blogspot.com/2007/08/detecting-overflowunderflow-when.html
    >
    > Example from source:
    >
    > char unsigned augend (255);
    > char unsigned const addend (255);
    > char unsigned const sum (augend + addend);
    >
    > if (sum < augend)
    > {
    > std::puts ("Overflowed!");
    > }
    >
    > sum = augend + addend
    > sum = 255 + 255
    > sum = 510 modulo 256 // Behind the scenes.
    > sum = 254
    >
    > Does it touch any implementation defined or undefined behaviour, or was
    > that specific to signed integers (on some platforms)?


    In C++ unsigned integer arithmetic is defined as modulo 2^n, where n is
    the number of bits.


    > What other methods are there for detecting unsigned integer overflow
    > and/or underflow in C++?


    Generally you don't.

    If you want range checking you can check if your compiler provides range
    checking for signed integer types, or you can implement a range-checked
    integer type as a class, like

    class CheckedInt
    {
    private:
    int myValue;
    public:
    CheckedInt( int v = 0 ): myValue( v ) {}

    int intValue() const { return myValue; }

    CheckedInt operator+( CheckedInt const& other ) const
    {
    int const a = intValue();
    int const b = other.intValue();
    int const result = a + b;

    // Assuming two's complement form:
    if( (a < 0) == (b < 0) && (result < 0) != (a < 0) )
    {
    throw std::something_blah_blah();
    }
    return result;
    }
    };

    Quite possibly there are existing such classes freely available on the
    net -- Google (and please report results of that search here! :) ).

    Cheers, & hth.,

    - Alf

    --
    A: Because it messes up the order in which people normally read text.
    Q: Why is it such a bad thing?
    A: Top-posting.
    Q: What is the most annoying thing on usenet and in e-mail?
     
    Alf P. Steinbach, Aug 20, 2007
    #2
    1. Advertising

  3. On Aug 20, 9:56 pm, Raymond <> wrote:
    > Source:http://moryton.blogspot.com/2007/08/detecting-overflowunderflow-when....
    >
    > Example from source:
    >
    > char unsigned augend (255);
    > char unsigned const addend (255);
    > char unsigned const sum (augend + addend);
    >
    > if (sum < augend)
    > {
    > std::puts ("Overflowed!");
    >
    > }
    >
    > sum = augend + addend
    > sum = 255 + 255
    > sum = 510 modulo 256 // Behind the scenes.
    > sum = 254
    >
    > Does it touch any implementation defined or undefined behaviour, or was
    > that specific to signed integers (on some platforms)?
    >

    3.9.1(4): Unsigned integers, declared unsigned, shall obey the laws of
    arithmetic modulo 2^n where n is the number of bits in the value
    representation of that particular size of integer

    Footnote: This implies that unsigned arithmetic does not 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.

    Thus the only implementation-defined aspect in your example is the
    value of 'n'. A 'char' is not necessarily 8 bit entity, and hence n
    neednot be 8.

    > What other methods are there for detecting unsigned integer overflow
    > and/or underflow in C++?


    There are no overflows possible for unsigned integer arithmetic. The
    question of "underflow" doesnot arise since it is "unsigned"
    arithmetic.

    -N
     
    Neelesh Bodas, Aug 20, 2007
    #3
  4. Raymond wrote:
    > Source:
    > http://moryton.blogspot.com/2007/08/detecting-overflowunderflow-when.html
    >
    > Example from source:
    >
    > char unsigned augend (255);
    > char unsigned const addend (255);
    > char unsigned const sum (augend + addend);
    >
    > if (sum < augend)
    > {
    > std::puts ("Overflowed!");
    > }
    >
    > sum = augend + addend
    > sum = 255 + 255
    > sum = 510 modulo 256 // Behind the scenes.
    > sum = 254
    >
    > Does it touch any implementation defined or undefined behaviour, or
    > was that specific to signed integers (on some platforms)?


    No, the behaviour is well-defined. All arithmetic operations with
    unsigned values work modulo 2^N, where N is the number of bits in
    the representation of the number.

    >
    > What other methods are there for detecting unsigned integer overflow
    > and/or underflow in C++?


    If you look in the archives (use Google Groups interface, e.g.), you
    should find that unsigned does not overflow. There is no such thing
    as "underflow" AFA integers are concerned, IIUIC.

    There is no way to "detect" it in the current language. There is only
    a way to "predict" it:

    unsigned a = UINT_MAX - 2, b = UINT_MAX - 3; // or whatever
    if (UINT_MAX - a < b)
    std::cout << "Adding " << a << " to " << b
    << " would \"overflow\"\n";

    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
     
    Victor Bazarov, Aug 20, 2007
    #4
  5. * Neelesh Bodas:
    >
    > There are no overflows possible for unsigned integer arithmetic. The
    > question of "underflow" doesnot arise since it is "unsigned"
    > arithmetic.


    Just a nit, but at least as far as the terminology I've been exposed to
    (for some decades), "underflow" is strictly a non-integer representation
    phenomenon. Integers just overflow, whether that's towards positive or
    negative infinity. I.e., "overflow" and "underflow" refer to the
    absolute value, not the sign.

    --
    A: Because it messes up the order in which people normally read text.
    Q: Why is it such a bad thing?
    A: Top-posting.
    Q: What is the most annoying thing on usenet and in e-mail?
     
    Alf P. Steinbach, Aug 20, 2007
    #5
  6. On Aug 20, 10:24 pm, "Alf P. Steinbach" <> wrote:
    > * Neelesh Bodas:
    >
    >
    >
    > > There are no overflows possible for unsigned integer arithmetic. The
    > > question of "underflow" doesnot arise since it is "unsigned"
    > > arithmetic.

    >
    > Just a nit, but at least as far as the terminology I've been exposed to
    > (for some decades), "underflow" is strictly a non-integer representation
    > phenomenon. Integers just overflow, whether that's towards positive or
    > negative infinity. I.e., "overflow" and "underflow" refer to the
    > absolute value, not the sign.
    >


    Agreed. (But had to refer to wikipedia for that !!). so that would
    make a very small change in my reply:
    The question of "underflow" doesnot arise since it is unsigned
    "integer" arithmetic

    (Just a slip-of-quote) :)
    -N
     
    Neelesh Bodas, Aug 20, 2007
    #6
  7. Raymond

    Raymond Guest

    Alf P. Steinbach wrote:
    > * Raymond:
    >> Source:
    >> http://moryton.blogspot.com/2007/08/detecting-overflowunderflow-when.html
    >>
    >> Does it touch any implementation defined or undefined behaviour, or
    >> was that specific to signed integers (on some platforms)?

    >
    > In C++ unsigned integer arithmetic is defined as modulo 2^n, where n is
    > the number of bits.


    Yes, correct, but in my haste I left out *why* I felt unsure/asked these
    questions, and I think I found the part that I had read before; section
    1.9 15, where overflows triggering exceptions are mentioned with regards
    to integers, or signed integers if the example is to be taken literally.

    > If you want range checking you can check if your compiler provides range
    > checking for signed integer types, or you can implement a range-checked
    > integer type as a class, like
    >
    > Quite possibly there are existing such classes freely available on the
    > net -- Google (and please report results of that search here! :) ).


    There is only so much time one can spend searching before beginning to
    think again..

    Anyway, thanks, but I think you made this a lot more complex than it
    needed to be, at least for me. Existing classes? Perhaps, but for such
    a small problem, that doesn't sound like the solution for me.

    It wasn't easy for me to find something concrete on this subject, and I
    tried finding other solutions after this one. The paper on Stroustrup's
    page, also linked to from the article, only dealt with signed integers,
    as your example did.
     
    Raymond, Aug 20, 2007
    #7
  8. Raymond

    Raymond Guest

    Victor Bazarov wrote:
    > Raymond wrote:
    >> Does it touch any implementation defined or undefined behaviour, or
    >> was that specific to signed integers (on some platforms)?

    >
    > No, the behaviour is well-defined. All arithmetic operations with
    > unsigned values work modulo 2^N, where N is the number of bits in
    > the representation of the number.


    Yes.

    >> What other methods are there for detecting unsigned integer overflow
    >> and/or underflow in C++?

    >
    > If you look in the archives (use Google Groups interface, e.g.), you
    > should find that unsigned does not overflow. There is no such thing
    > as "underflow" AFA integers are concerned, IIUIC.


    My current point of view on this; an overflow comes from adding too
    much; an "underflow" comes from subtracting too much. An overflow in the
    general sense does not explain whether too much was added or subtracted,
    just that information was lost; it doesn't include how it happened.

    > There is no way to "detect" it in the current language. There is only
    > a way to "predict" it:
    >
    > unsigned a = UINT_MAX - 2, b = UINT_MAX - 3; // or whatever
    > if (UINT_MAX - a < b)
    > std::cout << "Adding " << a << " to " << b
    > << " would \"overflow\"\n";


    What do you mean? The source code I linked to detects it fine, and it
    appears to be fully portable. No need to think about the underlying
    binary interpretation of signed integers, or exceptions either apparently.
     
    Raymond, Aug 20, 2007
    #8
  9. Raymond

    Raymond Guest

    Neelesh Bodas wrote:
    > On Aug 20, 9:56 pm, Raymond <> wrote:
    >> Source:http://moryton.blogspot.com/2007/08/detecting-overflowunderflow-when....
    >>
    >> Does it touch any implementation defined or undefined behaviour, or was
    >> that specific to signed integers (on some platforms)?
    >>

    > 3.9.1(4): Unsigned integers, declared unsigned, shall obey the laws of
    > arithmetic modulo 2^n where n is the number of bits in the value
    > representation of that particular size of integer
    >
    > Footnote: This implies that unsigned arithmetic does not 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.


    Yes.

    > Thus the only implementation-defined aspect in your example is the
    > value of 'n'. A 'char' is not necessarily 8 bit entity, and hence n
    > neednot be 8.


    As mentioned in the article too, I might add, but we're busy people. :)

    >> What other methods are there for detecting unsigned integer overflow
    >> and/or underflow in C++?

    >
    > There are no overflows possible for unsigned integer arithmetic. The
    > question of "underflow" doesnot arise since it is "unsigned"
    > arithmetic.


    Yes, but if you wanted to detect an overflow, then there is an overflow,
    because it is now defined as adding too much, resulting in loss of
    information due to a limited container. Same goes for underflow.
     
    Raymond, Aug 20, 2007
    #9
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. bartek
    Replies:
    3
    Views:
    3,135
    bartek
    Feb 6, 2004
  2. Eric Sosman
    Replies:
    1
    Views:
    504
    Eric Sosman
    May 13, 2010
  3. Keith Thompson
    Replies:
    2
    Views:
    757
    Seebs
    May 13, 2010
  4. joe
    Replies:
    23
    Views:
    936
    Seungbeom Kim
    Sep 13, 2010
  5. pozz
    Replies:
    12
    Views:
    791
    Tim Rentsch
    Mar 20, 2011
Loading...

Share This Page