What's the best C++ way to multiply unsigned integers modularly safely?

Question

Let's say that you are using <cstdint> and types like std::uint8_t and std::uint16_t, and want to do operations like += and *= on them. You'd like arithmetic on these numbers to wrap around modularly, like typical in C/C++. This ordinarily works, and you find experimentally works with std::uint8_t, std::uint32_t and std::uint64_t, but not std::uint16_t.

Specifically, multiplication with std::uint16_t sometimes fails spectacularly, with optimized builds producing all kinds of weird results. The reason? Undefined behavior due to signed integer overflow. The compiler is optimizing based upon the assumption that undefined behavior does not occur, and so starts pruning chunks of code from your program. The specific undefined behavior is the following:

std::uint16_t x = UINT16_C(0xFFFF);
x *= x;

The reason is C++'s promotion rules and the fact that you, like almost everyone else these days, are using a platform on which std::numeric_limits<int>::digits == 31. That is, int is 32-bit (digits counts bits but not the sign bit). x gets promoted to signed int, despite being unsigned, and 0xFFFF * 0xFFFF overflows for 32-bit signed arithmetic.

Demo of the general problem:

// Compile on a recent version of clang and run it:
// clang++ -std=c++11 -O3 -Wall -fsanitize=undefined stdint16.cpp -o stdint16

#include <cinttypes>
#include <cstdint>
#include <cstdio>

int main()
{
     std::uint8_t a =  UINT8_MAX; a *= a; // OK
    std::uint16_t b = UINT16_MAX; b *= b; // undefined!
    std::uint32_t c = UINT32_MAX; c *= c; // OK
    std::uint64_t d = UINT64_MAX; d *= d; // OK

    std::printf("%02" PRIX8 " %04" PRIX16 " %08" PRIX32 " %016" PRIX64 "\n",
        a, b, c, d);

    return 0;
}

You'll get a nice error:

main.cpp:11:55: runtime error: signed integer overflow: 65535 * 65535
    cannot be represented in type 'int'

The way to avoid this, of course, is to cast to at least unsigned int before multiplying. Only the exact case where the number of bits of the unsigned type exactly equals half the number of bits of int is problematic. Any smaller would result in the multiplication being unable to overflow, as with std::uint8_t; any larger would result in the type exactly mapping to one of the promotion ranks, as with std::uint64_t matching unsigned long or unsigned long long depending on platform.

But this really sucks: it requires knowing which type is problematic based upon the size of int on the current platform. Is there some better way by which undefined behavior with unsigned integer multiplication can be avoided without #if mazes?

Answer 1

Some template metaprogramming with SFINAE, perhaps.

#include <type_traits>

template <typename T, typename std::enable_if<std::is_unsigned<T>::value && (sizeof(T) <= sizeof(unsigned int)) , int>::type = 0>
T safe_multiply(T a, T b) {
    return (unsigned int)a * (unsigned int)b;
}

template <typename T, typename std::enable_if<std::is_unsigned<T>::value && (sizeof(T) > sizeof(unsigned int)) , int>::type = 0>
T safe_multiply(T a, T b) {
    return a * b;
}

Demo.

Edit: simpler:

template <typename T, typename std::enable_if<std::is_unsigned<T>::value, int>::type = 0>
T safe_multiply(T a, T b) {
    typedef typename std::make_unsigned<decltype(+a)>::type typ;
    return (typ)a * (typ)b;
}

Demo.

Answer 2

Here's a relatively simple solution, which forces a promotion to unsigned int instead of int for unsigned type narrower than an int. I don't think any code is generated by promote, or at least no more code than the standard integer promotion; it will just force multiplication etc. to use unsigned ops instead of signed ones:

#include <type_traits>
// Promote to unsigned if standard arithmetic promotion loses unsignedness
template<typename integer> 
using promoted =
  typename std::conditional<std::numeric_limits<decltype(integer() + 0)>::is_signed,
                            unsigned,
                            integer>::type;

// function for template deduction
template<typename integer>
constexpr promoted<integer> promote(integer x) { return x; }

// Quick test
#include <cstdint>
#include <iostream>
#include <limits>
int main() {
  uint8_t i8 = std::numeric_limits<uint8_t>::max(); 
  uint16_t i16 = std::numeric_limits<uint16_t>::max(); 
  uint32_t i32 = std::numeric_limits<uint32_t>::max(); 
  uint64_t i64 = std::numeric_limits<uint64_t>::max();
  i8 *= promote(i8);
  i16 *= promote(i16);
  i32 *= promote(i32);
  i64 *= promote(i64);

  std::cout << " 8: " << static_cast<int>(i8) << std::endl
            << "16: " << i16 << std::endl
            << "32: " << i32 << std::endl
            << "64: " << i64 << std::endl;
  return 0;
}

Answer 3

This article regarding a C solution to the case of uint32_t * uint32_t multiplication on a system in which int is 64 bits has a really simple solution that I hadn't thought of: 32 bit unsigned multiply on 64 bit causing undefined behavior?

That solution, translated to my problem, is simple:

// C++
static_cast<std::uint16_t>(1U * x * x)
// C
(uint16_t) (1U * x * x)

Simply involving 1U in the left side of the chain of arithmetic operations like that will promote the first parameter to the larger rank of unsigned int and std::uint16_t, then so on down the chain. The promotion will ensure that the answer is both unsigned and that the requested bits remain present. The final cast then reduces it back to the desired type.

This is really simple and elegant, and I wish I had thought of it a year ago. Thank you to everyone who responded before.