How do you check if an arithmetic operation will overflow?

Question

I am coming from looking at Rust and How do I detect unsigned integer multiply overflow? where in Rust they have checked_add, which is implemented like this:

pub const fn checked_add(self, rhs: Self) -> Option<Self> {
  let (a, b) = self.overflowing_add(rhs);
  if unlikely!(b) {None} else {Some(a)}
}

pub const fn overflowing_add(self, rhs: Self) -> (Self, bool) {
  let (a, b) = intrinsics::add_with_overflow(self as $ActualT, rhs as $ActualT);
  (a as Self, b)
}

// can't find where this is implemented...
#[rustc_const_stable(feature = "const_int_overflow", since = "1.40.0")]
pub fn add_with_overflow<T: Copy>(x: T, y: T) -> (T, bool);

If you try adding two u8 large integers, compiler doesn't let you:

fn main() {
  let a: u8 = 255;
  let b: u8 = 255;
  let c = a + b;
  // ^^^^^ attempt to compute `u8::MAX + u8::MAX`, which would overflow
}

How is this done in C? How can I simulate this sort of thing in JavaScript?

For example, in JavaScript. I guess in JavaScript you would check if it hits Infinity, as in Number.MAX_VALUE * 2 == Infinity. But in the case of Rust, how can I simulate this (or in C), using a specific low-level uint data type? (Without resorting to the checked_add helper methods which already solve it). Basically I am wondering how you can tell if it will overflow if the datatypes don't allow you to overflow.

I am working on building a programming language so would like to know how this is implemented.

Specifically right now what I am trying to do is, if you have a function called get_next_power_of_2(u8), it should return a u8 if it fits, otherwise a u16. But not a u16 in all cases. So I am wondering how to first check that it is going to overflow, and if it does, cast to a higher int.

How are you building a programming language? Why does JavaScript matter? Is your programming language an interpreter or are you trying to compile to a native binary using something like LLVM? — Locke, Apr 17 '22 at 04:11
It is unfortunately rather awkward to do correctly in standard C; you have to do things like `if (b > (255 - a))`. If using gcc or a compatible compiler, they provide [overflow-checking builtins](https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html#Integer-Overflow-Builtins) as an extension. — Nate Eldredge, Apr 17 '22 at 05:12
At the lowest level of assembly, it's actually pretty easy because a typical CPU would have an overflow flag which is set automatically by arithmetic instructions. Then you can use this flag for a conditional branch, etc. Unfortunately higher-level languages don't tend to expose this feature very well. — Nate Eldredge, Apr 17 '22 at 05:18

chux - Reinstate Monica · Accepted Answer · 2022-04-17T12:10:23.700

How is this done in C?

When wider math is available, code could use that.

int a,b;
...
int_twice_as_wide product = (int_twice_as_wide) a * b;
if (product < INT_MIN || product > INT_MAX) Handle_Overflow();

With signed integer math, overflow is undefined behavior (UB), so when wider math not readily available, code could perform various pre-tests for + - * / as done here.

For unsigned math, overflow "wraps around" ( a module UINT_MAX + 1). It is easy for + - (below). Division only need to watch for / 0.

unsigned a,b;
...
unsigned sum = a + b;
if (sum < a) Handle_Overflow();

The unsigned * is much like the above referenced signed * code with fewer tests.

bool is_undefined_umult1(unsigned a, unsigned b) {
  if (b > 0) {
    return a > UINT_MAX / b; 
  }
  return false;
}

it should return a u8 if it fits, otherwise a u16. But not a u16 in all cases.

C functions do not return different types depending upon value. Instead consider:

uint16_t unt8_mul(unt8_t a, unt8_t b) {
  return (uint16_t) a * b;
}

For u8 * u8, avoid a * b as on 16-bit systems the multiplication is signed, the product may overflow and incur UB.

score 1 · Answer 2 · answered Apr 17 '22 at 14:10

If you know the sizes of the variables, you also know the maximum & minimum values they can store. In C, you would check if the inverse operation is valid, for example:

#include <stdio.h>

int main()
{

    // max value a 4-byte unsigned int can store is 0xFFFFFFFF
    unsigned int UINT32_MAX = 0xFFFFFFFF;

    // var_1 + var_2 would overflow, 
    // as an unsigned int can't hold 0x100000028 (0xFFFFFFFE + 0x2A)
    unsigned int var_1 = 0xFFFFFFFE;
    unsigned int var_2 = 0x2A;

    // check the inverse operation, which can be stored in memory
    // var_1 + var_2 > UINT32_MAX --> UINT32_MAX - var_2 < var_1
    if (UINT32_MAX - var_2 < var_1) {
        printf("Overflow\n");
    } else {
        printf("No overflow\n");
    }
    return 0;
}

How do you check if an arithmetic operation will overflow?

2 Answers2