Return to Revisions

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 error 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 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. 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 the 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
  • 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 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?