Portable safe unsigned integer arithmetic

Question

tl;dr The purpose of the code is to allow writing

constexpr auto x = std::uint16_t { UINT16_MAX };
constexpr auto y = std::uint16_t { UINT16_MAX };
static_assert(multiply(x, y) == 1u, "broken math");

in a portable way that won't invoke undefined behavior. If that is enough for you to understand the problem at hand, you are welcome to skip the first two sections and jump straight to the section titled “Code for Review”.

Otherwise, the section titled “Problem Statement” explains why simply writing x * y would not have done the trick and the section “Proposed Solution” provides background information about the implementation of the multiply function I'm asking review for.

Problem Statement

In a recent discussion about a question on another Stack Exchange site, I was made aware that seemingly innocent arithmetic expressions of unsigned integral types in C++ can easily invoke undefined behavior.

const auto x = std::uint16_t { UINT16_MAX };
const auto y = std::uint16_t { UINT16_MAX };
std::cout << x * y << '\n';  // undefined behavior on 32 bit platforms

On my system, it prints -131071 when the intuitively expected result would be \$(2^{16}-1)^2\bmod{2^{16}}=65\,535^2\bmod{65\,536}=4\,294\,836\,225\bmod{65\,536}=1\$.

Fortunately, GCC catches the problem at compile-time

main.cxx:10:20: warning: integer overflow in expression [-Woverflow]
   std::cout << x * y << '\n';

and (after the example is changed to use run-time expressions), compiling with -fsanitize=undefined makes the program trap at run-time.

main.cxx:10:20: runtime error: signed integer overflow: 65535 * 65535 cannot be represented in type 'int'

The reason for the undefined behavior is that § 5 ¶ 10.5 of the C++ standard (quoting N4140) mandates that integral promotion shall be performed on the operands of an expression. § 4.5 specifies that an integral type of rank less than int shall be promoted to signed int if it can hold all its values or to unsigned int otherwise.

In the case of the above example – assuming that int has 32 bits – it can certainly hold all values of an std::uint16_t, so x and y are converted to int without loss. Now, however, the multiplication is carried out using signed arithmetic and this invokes undefined behavior as the result of the multiplication cannot be represented in a two's complement 32 bit integer and signed overflow is undefined in C++. As an additional surprise, since not requested explicitly, no conversion back to std::uint16_t is performed and therefore no wrapping modulo \$2^{16}\$ occurs.

At least in my experience, arithmetic involving unsigned types narrower than 32 bits seems to be rarely used so the problem doesn't show up very often today. However, if implementations would ever upgrade to 64 bit ints, I'd expect massive code breaks all over the place because many programs rely on std::uint32_t for arithmetic modulo \$2^{32}\$ as it is frequently needed in hashing and coding applications.

A straight-forward remedy for this problem is not apparent. Explicitly converting the operands to unsigned int and the result back to std::uintX_t would only work on systems where int is at least \$X\$ bits. On other systems, the conversion to unsigned int would truncate, leading to wrong results. Since no promotion would have happened on those systems anyway, the builtin behavior would have been correct there. One solution could be to perform all arithmetic in terms of std::uintmax_t and explicitly convert the results back but that might incur undesirable overhead if std::uintmax_t is not the most efficient type to operate on.

Proposed Solution

I wrote a small library to perform arithmetic on any arithmetic type (except bool for which I couldn't figure out sensible semantics) in a safe and portable way. Its main feature is a function template called promote that converts a value of type \$T\$ into a value of type \$U\$ according to the following rules. (Note that these are not the promotion rules specified in the C++ standard or the function would be pointless.)

• If \$T\$ is a signed / unsigned integer other than bool
  • and \$T\$ is of rank less than int, \$U\$ is signed int / unsigned int
  • and otherwise \$U\$ is the same as \$T\$.
• Otherwise, if \$T\$ is a floating-point type, \$U\$ is the same as \$T\$.
• Otherwise, the function does not participate in overload resolution.

This allows writing the following code, which – to my best knowledge – is safe.

const auto x = std::uint16_t { UINT16_MAX };
const auto y = std::uint16_t { UINT16_MAX };
std::cout << promote(x) * promote(y) << '\n';  // prints 4294836225 on 32 bit platforms

It is not portable yet, however, as the result will only be wrapped on platforms where int is narrower than 32 bits (unlikely today).

Therefore, the library also provides the multiply function that will convert the result back to the argument types after performing the operation on the promoted values.

const auto x = std::uint16_t { UINT16_MAX };
const auto y = std::uint16_t { UINT16_MAX };
std::cout << multiply(x, y) << '\n';  // always prints 1

Similar functions are provided for all builtin operations. The ones for bit-wise operations are only defined for unsigned integral arguments. Shift operations only accept non-negative shift amounts. Support for negative shift amounts would have been possible but might have introduced non-zero overhead. The goal of the library is to provide portable wrappers around the builtin arithmetic operations, not to extend them. Such extensions can be built atop of the library if needed.

While currently I'm only aware of issues with unsigned integral types, the library also handles signed integers and floating-point types through the same interface to support generic code.

Code for Review

#ifndef PROMOTION_HXX
#define PROMOTION_HXX

#include <type_traits>

namespace promotion
{

  namespace detail
  {

    template <typename T, typename = void>
    struct make_promoted;

    // We don't know how to deal with `bool`.
    template <>
    struct make_promoted<bool>
    {
    };

    // Signed integers promote to `signed int` or to themselves, if their rank
    // is already greater or equal to the rank of `signed int`.
    template <typename T>
    struct make_promoted<T, std::enable_if_t<std::is_integral<T>::value && std::is_signed<T>::value>>
    {
      static constexpr auto small = (sizeof(T) < sizeof(signed int));
      using type = std::conditional_t<small, signed int, T>;
    };

    // Unsigned integers promote to `unsigned int` or to themselves, if their
    // rank is already greater or equal to the rank of `unsigned int`.
    template <typename T>
    struct make_promoted<T, std::enable_if_t<std::is_integral<T>::value && std::is_unsigned<T>::value>>
    {
      static constexpr auto small = (sizeof(T) < sizeof(unsigned int));
      using type = std::conditional_t<small, unsigned int, T>;
    };

    // Floating-point types always promote to themselves.
    template <typename T>
    struct make_promoted<T, std::enable_if_t<std::is_floating_point<T>::value>>
    {
      using type = T;
    };

    template <typename T>
    using make_promoted_t = typename make_promoted<T>::type;

    template <typename T>
    constexpr bool
    allow_bitwise() noexcept
    {
      return std::is_integral<T>::value
        && std::is_unsigned<T>::value
        && !std::is_same<bool, T>::value;
    }

    template <typename T>
    using bitwise_t = std::enable_if_t<allow_bitwise<T>(), T>;

  }  // namespace detail


  template <typename T>
  constexpr detail::make_promoted_t<T>
  promote(const T value) noexcept
  {
    return value;
  }

  template <typename T>
  constexpr auto
  add(const T lhs, const T rhs) noexcept
    -> decltype(T(promote(lhs) + promote(rhs)))
  {
    return T(promote(lhs) + promote(rhs));
  }

  template <typename T>
  constexpr auto
  subtract(const T lhs, const T rhs) noexcept
    -> decltype(T(promote(lhs) - promote(rhs)))
  {
    return T(promote(lhs) - promote(rhs));
  }

  template <typename T>
  constexpr auto
  multiply(const T lhs, const T rhs) noexcept
    -> decltype(T(promote(lhs) * promote(rhs)))
  {
    return T(promote(lhs) * promote(rhs));
  }

  template <typename T>
  constexpr auto
  divide(const T lhs, const T rhs) noexcept
    -> decltype(T(promote(lhs) / promote(rhs)))
  {
    return T(promote(lhs) / promote(rhs));
  }

  template <typename T>
  constexpr auto
  bit_and(const T lhs, const T rhs) noexcept
    -> decltype(detail::bitwise_t<T>(promote(lhs) & promote(rhs)))
  {
    return T(promote(lhs) & promote(rhs));
  }

  template <typename T>
  constexpr auto
  bit_or(const T lhs, const T rhs) noexcept
    -> decltype(detail::bitwise_t<T>(promote(lhs) | promote(rhs)))
  {
    return T(promote(lhs) | promote(rhs));
  }

  template <typename T>
  constexpr auto
  bit_xor(const T lhs, const T rhs) noexcept
    -> decltype(detail::bitwise_t<T>(promote(lhs) ^ promote(rhs)))
  {
    return T(promote(lhs) ^ promote(rhs));
  }

  template <typename T>
  constexpr auto
  bit_not(const T value) noexcept
    -> decltype(detail::bitwise_t<T>(~promote(value)))
  {
    return T(~promote(value));
  }

  template <typename T>
  constexpr auto
  shift_left(const T value, const unsigned amount) noexcept
    -> decltype(detail::bitwise_t<T>(promote(value) << amount))
  {
    return T(promote(value) << amount);
  }

  template <typename T>
  constexpr auto
  shift_right(const T value, const unsigned amount) noexcept
    -> decltype(detail::bitwise_t<T>(promote(value) >> amount))
  {
    return T(promote(value) >> amount);
  }

}  // namespace promotion

#endif  // #ifndef PROMOTION_HXX

Concerns

I'm looking for comments on all aspects of the code. In particular:

• Is the reasoning behind the implemented solution correct?
• Is it implemented correctly?
• Is the interface as convenient as possible and general enough for usage in generic code or could it be improved?
• Is the implementation zero-overhead?
• Could the quality-of-implementation be improved?
• Are all public functions SFINAE friendly?
• Should I handle bool differently?
• Could it be implemented with less repetition?

Answer 1

I would rename add, etc. to plus, minus, multiplies and divides to match the functor names from <functional>, as you've done for the bit variants. You could also consider adding variants for comparisons (equal_to...) and logical operations (logical_and...) You could also provide a void specialization to allow the type to be deduced. So promotion::add could be passed to std::transform without specifying the type. That would probably require turning the functions into functors (i.e, classes).

One thing I find annoying is this: -> decltype(T(promote(lhs) + promote(rhs))). It's not necessary with C++14 return type deduction. So it just adds noise. Actually, is auto even necessary here? You're constructing a T so just make the return type T.

On on a similar note, I would also remove const from the parameters. Either pass by const& or by value. In all three options, you can't modify the caller's arguments, but the const just adds noise.

And one note (not a suggestion), you could replace typename with class. It's less typing and what library devs do.

  template <class T>
  constexpr T add(T lhs, T rhs) noexcept
  {
    return T(promote(lhs) + promote(rhs));
  }