Avoiding unsigned overflow during multiplications using a max limit - how to define the limit value?

Question

I need to compute recursively an integer number represented by an unsigned int down a tree. Each node is associated with an integer value calculated recursively by multiplying the numbers of its children. The leaves have each a non-calculated static number, each being > 0.

The problem is frequent overflows. Actually, I am not interested when the result is a high number. I am OK if the result I obtain just tell me the value is > SOME_BIG_VALUE for instance (I don't need the real value in such a case).

My idea is to use the value 0 (otherwise never used) as a convention for any "high number" and

//when multiplying a and b each being <= SOME_BIG_VALUE, there is no overflow
unsigned c = a*b; 
// add a check 
if (c > SOME_BIG_VALUE)
   c = 0;

What is the cleanest way to define SOME_BIG_VALUE with its highest possible value for avoiding overflow ?

I consider using the definition :

#DEFINE SOME_BIG_VALUE unsigned(sqrt(UINT_MAX));

But it looks kind of dirty, isn't it ?

I know that in most case, unsigned are represented by 32 or 64 bits but I am not sure it is guaranteed. If it is I can check in which configuration we are and create define SOME_BIG_VALUE respectively to 2^16-1 ou 2^32-1.

Answer 1

Avoiding unsigned overflow a * b

Many approaches involve finding the square root of UINT_MAX or UINT_MAX + 1.

OP's sqrt test

This is certainly reasonable when the ((unsigned) sqrt(UINT_MAX)) is somehow coded to only evaluate once.

// Somewhat convoluted.
#define SOME_BIG_VALUE ((unsigned) sqrt(UINT_MAX))
static unsigned big_value = 0;
if (big_value == 0) {
  big_value = SOME_BIG_VALUE;
}
if (a > big_value || b > big_value) {
  // Potential overflow
}

A more pedantic approach could use:

#define SOME_BIG_VALUE ((unsigned) sqrt((UINT_MAX/2 + 1)*2.0) - 1) so the sqrt() is more likely exact as (UINT_MAX/2 + 1)*2.0 is a exact floating point power-of-2, the number of value bits in unsigned is very commonly even and even weak quality sqrt() get the root of even power-of-2 exactly right.

Bit width test

#define UINT_BITS (sizeof(unsigned)*CHAR_BITS)
#define SOME_BIG_VALUE ((1u << (UINT_BITS/2)) - 1)
if (a > SOME_BIG_VALUE || b > SOME_BIG_VALUE) {
  // Potential overflow
}

There are ways to handle an odd sizeof(unsigned)*CHAR_BITS or unsigned with padding (see below), yet the above works for common implementations.

Bit width UINT_MAX (even if unsigned has padding):

// https://stackoverflow.com/a/4589384/2410359  
/* Number of value bits in inttype_MAX, or in any (1<<k)-1 where 0 <= k < 2040 */  
#define IMAX_BITS(m) ((m)/((m)%255+1) / 255%255*8 + 7-86/((m)%255+12))
// Value bit width of UINT_MAX (handles padded types).
#define UINT_BITS IMAX_BITS(UINT_MAX)

C2X has UINT_WIDTH for the value-bit-width.

Run time check

if (a > 0 && b > UINT_MAX/a) {
  // a * b will overflow.
}

Wider math

#if ULLONG_MAX/UINT_MAX > UINT_MAX
  unsigned long long prod = a;
  prod *= b;
  if (prod > UINT_MAX) {
    // Overflow
 

Answer 2

If your compiler supports an overflow-checking builtin you should use that: __builtin_umul_overflow in GCC and Clang; check the documentation for other compilers.

unsigned c; 
if (__builtin_umul_overflow(a, b, &c)) {
    c = 0;
}