C++17 saturating integer (arithmetic) type library

Question

I wrote a C++ library to provide extra signed and unsigned integer types that saturate in overflow situations. It's in proof of concept stage and I'd love to get some feedback on it.

A short usage demo (usable in Compiler Explorer):

#include <cstddef>
#include <cstdint>
#include "saturating_types.hpp"
uint8_t x[] { 101, 27, 3, 95 };
int main () {
 uint_sat8_t s = 25;
 for (auto& v : x) {
 s -= v;
 } // s == 0
 s++; // s == 1
 for (const auto& v : x) {
 s *= v;
 }
 volatile unsigned j = s; // s == 255
}

The library:

/**@file
 * @brief Always saturating integer types.
 *
 * Some assumptions and notes:
 * - The operators are 'viral', adding a saturating type and any other returns another saturating type.
 * - Divide by zero clips the value to max()
 * - Tries to avoid the normal promotion rules
 * - The separate `add`, `substract`, etc functions can be used to define extra external operators
 * returning saturated types.
 *
 * TODO: Further test and improve algorithms (hardware specific functions / reduce branching?)
 * TODO: Enforce integral types where needed
 * TODO: Enforce maximum base type size.
 * TODO: Enhance interaction with floating point types
 * TODO: Add toggle for `return_type` of operators (viral-ness)
 */
#pragma once
#include <cstdint>
#include <limits>
#include <utility>
#include <type_traits>
namespace {
 // Helpers to convert small types to the next size up:
 template <typename T, typename U, size_t S = (sizeof(T) > sizeof(U) ? sizeof(T) : sizeof(U)), bool B = std::is_unsigned<T>::value> struct next_up {};
 template <typename T, typename U> struct next_up<T, U, 1, false> { typedef int type; };
 template <typename T, typename U> struct next_up<T, U, 1, true> { typedef unsigned type; };
 template <typename T, typename U> struct next_up<T, U, 2, false> { typedef int type; };
 template <typename T, typename U> struct next_up<T, U, 2, true> { typedef unsigned type; };
 template <typename T, typename U> struct next_up<T, U, 4, false> { typedef int64_t type; };
 template <typename T, typename U> struct next_up<T, U, 4, true> { typedef uint64_t type; };
#ifdef __SIZEOF_INT128__
 template <typename T, typename U> struct next_up<T, U, 8, false> { typedef __int128_t type; };
 template <typename T, typename U> struct next_up<T, U, 8, true> { typedef __uint128_t type; };
#endif
 /** Base template for a saturating integer or unsigned integer. */
 template <typename T, typename TNOTUSED = typename std::enable_if<std::is_integral<T>::value, T>::type>
 class xint_sat_t {
 public:
 typedef xint_sat_t<T> return_type; ///< This is what the operators return
 /** Create a new zero-initialized saturated type. */
 constexpr xint_sat_t() : value{0} {}
 /**
 * Create a new saturating type based on a given value.
 * @param val Initial value will be clamped to fit T
 */
 template <typename U>
 constexpr xint_sat_t(const U& val) : value{clamp(val)} {}
 /** Conversion back to the base type */
 constexpr operator const T&() const { return value; }
 constexpr operator T&() { return value; }
 /**
 * Add `other` to this value and return a new saturating type.
 * @param other Value to add to this one
 * @return New saturating type
 */
 template <typename U>
 constexpr return_type __attribute__((pure)) add(const U& other) const {
 if constexpr (std::is_unsigned<T>::value) {
 if constexpr (std::is_unsigned<U>::value) {
 const auto temp = (typename next_up<T, U>::type)value + other;
 return {
 temp > std::numeric_limits<T>::max()
 ? std::numeric_limits<T>::max()
 : (T)temp
 };
 // Branchless version, seems to compile down to exactly the same thing in GCC
 // auto temp = value + other;
 // temp |= -(temp < value);
 // return { temp };
 // Slower:
 // const auto temp = value + (T)other;
 // return { (temp < value) ? std::numeric_limits<T>::max() : temp };
 } else {
 if (other < 0) {
 if constexpr (sizeof(U) > 4) {
 const uint64_t temp = -other;
 return {
 (value > temp) ? (T)(value - temp) : 0
 };
 } else {
 const unsigned temp = -other;
 return {
 (value > temp) ? (T)(value - temp) : 0
 };
 }
 } else {
 const auto temp = (typename next_up<T, U>::type)value + other;
 return {
 temp > std::numeric_limits<T>::max()
 ? std::numeric_limits<T>::max()
 : (T)temp
 };
 }
 }
 } else {
 const auto temp = (typename next_up<T, U>::type)value + other;
 return {
 temp > std::numeric_limits<T>::max()
 ? std::numeric_limits<T>::max()
 : (temp < std::numeric_limits<T>::min()
 ? std::numeric_limits<T>::min()
 : (T)temp)
 };
 }
 }
 /**
 * Substract `other` from this value and return a new saturating type.
 * @param other Value to substract from this one
 * @return New saturating type
 */
 template <typename U>
 constexpr return_type __attribute__((pure)) substract(const U& other) const {
 if constexpr (std::is_unsigned<T>::value) {
 if constexpr (std::is_unsigned<U>::value) {
 return {
 other > value
 ? 0
 : (T)(value - other)
 };
 } else {
 if (other < 0) {
 const auto temp = (typename next_up<T, U>::type)(-other) + value;
 return {
 temp > std::numeric_limits<T>::max()
 ? std::numeric_limits<T>::max()
 : (T)temp
 };
 } else {
 return {
 value > other
 ? (T)(value - other)
 : 0
 };
 }
 }
 } else {
 const auto temp = (typename next_up<T, U>::type)value - other;
 return {
 temp > std::numeric_limits<T>::max()
 ? std::numeric_limits<T>::max()
 : (temp < std::numeric_limits<T>::min()
 ? std::numeric_limits<T>::min()
 : (T)temp)
 };
 }
 }
 /**
 * Multiply this value with `other` and return a new saturating type.
 * @param other Multiplication factor
 * @return New saturating type
 */
 template <typename U>
 constexpr return_type __attribute__((pure)) multiply(const U& other) const {
 if constexpr (std::is_unsigned<T>::value) {
 if constexpr (std::is_unsigned<U>::value) {
 const auto temp = (typename next_up<T, U>::type)value * other;
 return {
 temp > std::numeric_limits<T>::max()
 ? std::numeric_limits<T>::max()
 : (T)temp
 };
 } else {
 if (other < 0) {
 return 0;
 } else {
 const auto temp = (typename next_up<T, U>::type)value * other;
 return {
 temp > std::numeric_limits<T>::max()
 ? std::numeric_limits<T>::max()
 : (T)temp
 };
 }
 }
 } else {
 const auto temp = (typename next_up<T, U>::type)value * other;
 return {
 temp > std::numeric_limits<T>::max()
 ? std::numeric_limits<T>::max()
 : (temp < std::numeric_limits<T>::min()
 ? std::numeric_limits<T>::min()
 : (T)temp)
 };
 }
 }
 /**
 * Divide this by `other` and return a new saturating type.
 * @param other Division factor
 * @return New saturating type
 */
 template <typename U>
 constexpr return_type __attribute__((pure)) divide(const U& other) const {
 if (other == 0) {
 return std::numeric_limits<T>::max();
 } else {
 return value / other;
 }
 }
 constexpr auto& operator++() {
 if (value < std::numeric_limits<T>::max() - 1) ++value;
 return *this;
 }
 constexpr auto operator++(int) {
 xint_sat_t<T> temp { value };
 if (value < std::numeric_limits<T>::max() - 1) ++value;
 return std::move(temp);
 }
 constexpr auto& operator--() {
 if (value > std::numeric_limits<T>::min() + 1) --value;
 return *this;
 }
 constexpr auto operator--(int) {
 xint_sat_t<T> temp { value };
 if (value > std::numeric_limits<T>::min() + 1) --value;
 return std::move(temp);
 }
 template <typename U> constexpr auto& operator= (const U& other) { value = clamp(other); return *this; }
 template <typename U> constexpr decltype(auto) __attribute__((pure)) operator+(const U& other) const { return add(other); }
 template <typename U> constexpr decltype(auto) __attribute__((pure)) operator-(const U& other) const { return substract(other); }
 template <typename U> constexpr decltype(auto) __attribute__((pure)) operator*(const U& other) const { return multiply(other); }
 template <typename U> constexpr decltype(auto) __attribute__((pure)) operator/(const U& other) const { return divide(other); }
 template <typename U> constexpr return_type __attribute__((pure)) operator%(const U& other) const { return value % other; }
 template <typename U> constexpr auto& operator+=(const U& other) { value = add(other); return *this; }
 template <typename U> constexpr auto& operator-=(const U& other) { value = substract(other); return *this; }
 template <typename U> constexpr auto& operator*=(const U& other) { value = multiply(other); return *this; }
 template <typename U> constexpr auto& operator/=(const U& other) { value = divide(other); return *this; }
 template <typename U> constexpr auto& operator%=(const U& other) { value %= other; return *this; }
 private:
 T value;
 template <typename U>
 constexpr T clamp(const U& val) const {
 if constexpr (std::is_unsigned<T>::value == std::is_unsigned<U>::value && sizeof(U) <= sizeof(T)) {
 return val;
 } else {
 return (val < std::numeric_limits<T>::lowest())
 ? std::numeric_limits<T>::lowest()
 : (val > std::numeric_limits<T>::max()
 ? std::numeric_limits<T>::max()
 : val);
 }
 }
 };
}
typedef xint_sat_t<int8_t> int_sat8_t;
typedef xint_sat_t<uint8_t> uint_sat8_t;
typedef xint_sat_t<int16_t> int_sat16_t;
typedef xint_sat_t<uint16_t> uint_sat16_t;
typedef xint_sat_t<int32_t> int_sat32_t;
typedef xint_sat_t<uint32_t> uint_sat32_t;
typedef xint_sat_t<int64_t> int_sat64_t;
typedef xint_sat_t<uint64_t> uint_sat64_t;

As promised below a link to the updated version: https://github.com/StefanHamminga/saturating

• hoffmale: This immediately reminded me of this talk (yes, it's in D, not C++, but the conceptual design should be portable). Maybe you can get some value from it. Also, what would be the expected behavior for int_sat8_t a = -128; int_sat8_t b = -a;? Usual 2s complement says b should be -128, with "overflow protection" this could be 127 instead (but that would require to overload the unary monus operator).
• Stefan: Interesting... Iogically int_sat8_t b = -1 * (-128) would (and does) result in 127. Would there be a mathematical reason not to expect this result?
• hoffmale: Well, the only reason I could think to not expect this result would be int_sat8_t c = -b; assert(a == c); (with the fix, a == -128 and c == -127). That said, not fixing the unary minus operator would be inconsistent with multiplying by -1, and that operation already has this behavior. That said, it makes multiplication non-cumulative ((-1) * (-1) * (-128) == 1 * (-128) == -128, (-1) * (-128) * (-1) == 127 * (-1) == -127). Such is the price for overflow protection. (Or one could simply make -128 an invalid value, kinda like NaN, sidestepping the problem).

Answer 1

Refactor the limits

There's quite a lot of repetition of std::numeric_limits<T>::max() and std::numeric_limits<T>::min(). It would make sense to define

static const T min_val = std::numeric_limits<T>::min();
static const T max_val = std::numeric_limits<T>::max();

Or, we could make those limits be template parameters instead, which allows us to define saturating types with non-default limits:

/** A saturating integer value. */
template
 <typename T,
 std::enable_if_t<std::is_integral_v<T> T> min = std::numeric_limits<T>::min(),
 std::enable_if_t<std::is_integral_v<T> T> max = std::numeric_limits<T>::max()>
class xint_sat_t
{
public:
 // We don't need return_type - just use xint_sat_t directly
 // (T, min and max will be inferred).
 static const T min_val = min;
 static const T max_val = max;

If we take this approach, we'll need operator= that accepts a T alone, otherwise assignments would need values constructed with matching min and max.

Specialize type traits

If we want our new type to behave as a normal value type, it's worthwhile to specialize the type traits:

namespace std
{
 <template typename T, T min, T max>
 constexpr is_unsigned<xint_sat_t<T, min, max>> {
 return is_unsigned<T>();
 }
}

Other candidates for specialization include std::is_signed, std::is_integral, std::is_arithmetic (if we also specialize std::numeric_limits), std::is_exact and so on - the pattern is mostly to forward to the specialization for T, as above.

A cast is required in clamp()

If I try to assign a uint_sat8_t to a uint_sat32_t variable, I get an error from mismatched ?: arguments. The fix is to cast to T:

 return
 val < min_val ? min_val
 : val > max_val ? max_val
 : static_cast<T>(val);

Don't move return values

Instead of this:

 constexpr xint_sat_t operator++(int) {
 xint_sat_t temp { value };
 if (value < max_val - 1) ++value;
 return std::move(temp);
 }

We should simply return by value, and trust in return value optimization (which the std::move() may inhibit):

 constexpr xint_sat_t operator++(int) {
 xint_sat_t temp { value };
 if (value < max_val - 1) ++value;
 return temp;
 }

I think the test should be value < max_val there, given that the limit seems to be inclusive everywhere else.

Consider using compiler builtins

With GCC, we can test for overflow without having to promote to a wider type:

// pass by value should be as efficient as passing T by value
constexpr xint_sat_t __attribute__((pure)) add(xint_sat_t other) const
{
 T result;
 if (std::is_signed_v<xint_sat_t> && other < 0) {
 return (__builtin_add_overflow(value, other.value, &result) || result < min_val)
 ? min_val
 : result;
 } else {
 return (__builtin_add_overflow(value, other.value, &result) || result > max_val)
 ? max_val
 : result;
 }
}

It's probably not too hard to make implementations that use these builtins (and similar functions for other compilers) where available, and hand-crafted code otherwise. It might be worth standardizing on one interface to add_with _overflow() and implementing that per-compiler. That would solve the problem that the public methods add(), subtract() sound like mutators. (And I noticed a wee typo - substract() should be subtract() before that modification.)

Make the main() a proper self-test

The main function can be a much more comprehensive test - and instead of commenting the expectations, it should actively test them, returning non-zero if any fail.

Negative infinity

Should division of a negative quantity by zero result in the max value? Perhaps it should saturate at the min value instead? (That's an open question - you get to decide the interface, but at least be clear that you thought of this).

• Toby Speight: I've used the _v and _t type traits rather than ::value and ::type to make shorter lines, since we're in C++17. That might be just a preference, but it's probably worth mentioning.
• Toby Speight: Another post-script thought - we probably never need to promote to a wider type, if we can assume a 2s-complement platform, because we could reinterpret_cast both operands to std::make_unsigned_t<T> values, perform the operation in unsigned space (where overflow is defined) and then cast back to T after checking for overflow.
• Stefan: First off: Thanks for the very complete reply! I like your suggestion to take min and max as a template argument, applied that. Combining that with the builtin actually requires to keep the generic versions as well (if constexpr solves that nicely though). The builtins also seem to produce less optimal code in cases there the next_up type is the native size. I've added conditionals for that. The clamp bug is solved, well spotted. I've removed the move() call. I've also taken your advice and converted everything to _v and _t. -n / 0 now clamps to min, it was indeed an omission.
• Stefan: About the wider type promotion: I think it's not that big of a deal (based on the assembly) for the types < native, but I'll study and compare your idea, thanks! I'll put the library up on GitHub and post the link back here later.
• Toby Speight: Will the link be very much later? We're still waiting...

Answer 2

Please don't use compiler intrinsics, as they limit your code to a specific compiler. In your case, I know that MSVC will not be able to compile your code, because of __attribute__((pure)) and so on. What you did with __int128_t is IMO ok, but you seem to not use it apart for next_up.

1. Don't name variables that you won't use: S, B, TNOTUSED, ...

2. Prefer using aliases to typedef, although this is not really important.

3. Use the standard library better.

   • (sizeof(T) > sizeof(U) ? sizeof(T) : sizeof(U)) can become std::max(sizeof(T), sizeof(U))

   • Prefer to use the _v and _t aliases instead of ::value and typename /*...*/::type.

   • clamp can be replaced by std::clamp (although you could provide a small wrapper function to not repeat the same function arguments over and over again).

4. I could override xint_sat_t's SFINAE by providing explicitly a second template argument. You can make std::enable_if_t's return type a pointer and set it to nullptr.

5. You seem to use a lot of common type traits everywhere, std::numeric_limits, std::is_unsigned and so on. Consider storing their values in a static constexpr private variable instead.

6. Provide a next_up_t for less typing, like the standard library. :)

7. Consider marking your functions noexcept.

8. I don't see why you need return_type. Maybe for the semantics, but you could have just used xint_sat_t instead.

9. You forgot to overload some operators, like unary minus and the comparison operators.

10. You are inhibiting NRVO by std::moveing lvalues. Please don't and let the compiler optimize the copy away. :)

11. Why are you using decltype(auto) for every non-assignment operator's return type, except for the modulo? Consistency?

12. uint64_t relies on non-standard library implementation details. Use std::uint64_t instead. Same for the others.

13. You might want to add an explicit constructor to convert from a higher precision type to a lower precision one.

14. You should specialize some standard library type traits for better compatibility.