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 int
s, 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 thanbool
- and \$T\$ is of rank less than
int
, \$U\$ issigned int
/unsigned int
- and otherwise \$U\$ is the same as \$T\$.
- and \$T\$ is of rank less than
- 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?