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

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).

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.