Is there a clean way to write overflowing adds?

help
1

Is there a better, cleaner, or more natural way to handle arithmetic allowing for overflows? I need to do a significant number of arithmetic operations and bit manipulations, and I am worried that constructs like the example in the code below will be very difficult to read and maintain.

fn main() {
    // I need to calculate u32:MAX + 2 + 1, ignoring overflows.
    // Is there a better or more natural way?
    let i: u32 = u32::MAX;
    let j = i.overflowing_add(2).0.overflowing_add(1).0;
    println!("1 + 1 = {}", j);
}

Output:
1 + 1 = 2

As an aside, it seems like overflowing_add() is really std::intrinsics::add_with_overflow(), returning a two-element tuple. I don't see a way to short-circuit this without dipping into assembly. Is the rustc compiler clever enough to optimize out the second element of the tuple if I never use it?

(intrinsics.rs - source)

3 Likes
2

Maybe you are looking for u32::wrapping_add?

7 Likes
3

By the way, is there a way in C to do an overflowing_add?

1 Like
4

Some tedious depending on the number of constants, but you can

use core::num::Wrapping;
fn main() {
    let i = Wrapping(u32::MAX);
    let one = Wrapping(1);
    let two = Wrapping(2);
    let j = (i + one + two).0;
    println!("1 + 1 = {}", j);
}
3 Likes
5

Thanks, @jbe -- u32::wrapping_add() works much better and does what I need.

fn main() {
    let i: u32 = u32::MAX;
    let j = i.wrapping_add(2).wrapping_add(1);
    println!("1 + 1 = {}", j);
}

In C, if I wanted to test explicitly for an overflow I would use 64 bit add and check the high 32 bits for zero or not zero, which could be executed neatly in hardware with one test and branch machine instruction. (I would reserve 64 bits, but use a pointer to 32 bits and add one to peek into the overflow.) In this case (for Rust), I am getting lost in the docs being disjoint. (Methods, traits, macros, and sometimes non-obvious side effects -- too many rabbit holes to go down.)

6

I guess there are no such functions like overflowing_add in libc? How about 3rd party libraries? It should be possible with inline assembler. Or maybe there is something in one of the newer C standards?

7

Speaking for myself, for low-level operations I will put an optimized expression into a #define and not worry about externalities. I would keep the define close to where it is used (same c file, or maybe the header file), and obscurely named so it doesn't collide with anything else, and reinvent the wheel the next time I needed such a thing. For assembly I would use a flag register and conditional jumps, but that would be very particular to whatever the hardware is.

8

I thought on something that works cross-platform, which is actually a nice thing that we have it in std Rust!

9

They're compiler builtins, not part of libc: https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html & https://clang.llvm.org/docs/LanguageExtensions.html#checked-arithmetic-builtins.

1 Like
10 
bool overflowing_add(unsigned a, unsigned b, unsigned &c)
{
    c = a + b;
    return c < a;
}

Generates same code as the builtin for me :slight_smile: (C++, didn't want to use C).

1 Like
11

Note however that in C++ this only works for unsigned number, where overflow is defined. For signed ones, AFAIK, you have to check explicitly whether the overflow is about to come.

12

Haven't tested it thoroughly, but maybe something like:

bool overflowing_add(int a, int b, int &c) {
    c = a + b;
    if (b >= 0) return c < a;
    else return c > a;
}

But it's not as beautiful as @tczajka's example anymore.

Edit: It won't work, see discussion below!

13

This line is UB if the overflow happens.

3 Likes
14

C scares me

15

:scream:

I guess calling something "undefined behavior" in C is usually different from when you call something UB in Rust? Can the "undefined behavior" in C affect anything else than the result of the integer computation? I don't think so, but the term "undefined behavior" is a bit vague here.

Also note Rust's reference regarding behavior considered unsafe:

The Rust compiler does not consider the following behaviors unsafe, though a programmer may (should) find them undesirable, unexpected, or erroneous.

Anyway, I'm very surprised that signed integer overflows in C are not defined as always wrapping around. A quick Wikipedia check confirms that, but does anyone have a more authoritative link on (signed) integer overflows being undefined in C?

I'm asking because a friend of mine was thinking the Rust rules on interger overflows (panicking in debug-mode, but wrapping around in release-mode) were somewhat awkward. But it looks like it's C is the language with not-well-defined behavior here while Rust just exhibits different (but well-defined) behavior regarding whether in debug-mode or release-mode.

So do I understand right that in Rust signed integer overflows are defined as overflowing in regard two's complement wrapping or causing a panic in debug mode, while in C signed integer overflows are not well-defined? The Rust reference book regarding integer overflow gives only an example with u8 but talks about "two's complement wrapping".

When you’re compiling in release mode with the --release flag, Rust does not include checks for integer overflow that cause panics. Instead, if overflow occurs, Rust performs two’s complement wrapping. In short, values greater than the maximum value the type can hold “wrap around” to the minimum of the values the type can hold. In the case of a u8, the value 256 becomes 0, the value 257 becomes 1, and so on. The program won’t panic, but the variable will have a value that probably isn’t what you were expecting it to have. Relying on integer overflow’s wrapping behavior is considered an error.

Isn't two's complement wrapping only applicable in case of signed numbers? How would the wrapping be called for unsigned numbers? Modular arithmetic? Does the reference need to be updated as in saying:

Instead, if overflow occurs, Rust performs two’s complement wrapping (add this: in case of signed integers and modular arithmetic in case of unsigned integers.)

16

It's modular arithmetic both ways. Two's complement is attractive in part because modular arithmetic is the same operation on the signed and unsigned versions. Every signed integer is congruent to the corresponding unsigned integer, bitwise. The only interpreted difference in that context is the span of congruent numbers used.

You could have a similar scheme where a number was considered negative if the highest two bits were 1 instead of the highest bit, for example; the range of values for an 8-bit number of this sort would be -64..192.

1 Like
17

I would say that in case of u8 there is no two's complement (unless you cast to an i8 later).

Hmmm, you're right. I should have said: Modulo operation.

But that still doesn't mean that when I only use u8's, there is any two's complement (unless I interpret values that way, but that's an arbitrary assumption, as I could also interpret values as an u3).

18

There is; the two's complement of 3_u8 is 253_u8, which is congruent to -3 (mod 256).

1 Like
19

I can't follow you. I meant u3 (as in a 3 bit unsigned integer), and not u8. It was just meant as an (arguably bad) example for "just interpreting the numbers in a particular way".

My point is: When no negative numbers are involved, then there is no two's complement. Two's complement is for representing signed integers.

P.S.: Maybe it's a matter of terminology and "two's complement" also specifically defines the operations on the bit-wise level already, disregarding the interpretation. So perhaps you are right.

20

It was just a coincidence that I used 3 and had nothing to do with your u3 comment.

And sorry, but that's not true. The two's complement of x gives the number congruent to -x, whether working with signed or unsigned numbers.

For another u8 example, the two's complement of 128 is 128, which is congruent to -128. And for i8, the two's complement of -128 is -128, which is congruent to 128.

This generalizes to any interpretation of the bits that corresponds to modular congruences (e.g. my two-high-bits example).