Zero-Cost Well-Defined Signed Integer Overflow In C++

The other day someone posted about how undefined behaviors are getting wild. The post turned out to be someone not knowing that you can't check for undefined behavior after already invoking undefined behavior. That's a normal footgun in C/C++, nothing to be ashamed about. It's not your fault. Those languages and everyone who works on them hate you and humanity too. They are the cause of a large part of our societal suffering. They are clearly ontologically evil. As a moral person, you must vocally and publicly acknowledge this evil and spend whatever free time you have proselytizing safe alternatives on the internet and if you don't, well, I'm suspicious of you.

For the oppressed who must write secure code in C/C++ but don't want to think about signed integer overflow, let alone undefined signed integer overflow, you can always use the "-wrapv" compiler option. You'll be free to focus on what you're actually building.

If you don't have access to "-wrapv" then C++ has a regressive feature called operator overloading that allows one to implement a "SafeSigned" type that emulates a signed integer that doesn't invoke undefined behavior on overflow during arithmetic. The trick is to use an unsigned integer to store a signed integer in two's complement form. This works because unsigned integer overflow in C++ is well-defined. Addition and subtraction are zero-cost, while the portable implementation of multiplication and division are zero-cost with an optimizing compiler. Operator overloading is technically a garbage feature that makes it literally impossible to understand what code is doing but, hey, if you're going to use a garbage language then might as well use a garbage feature, am I right?

The following is the code from the original post now ported to use the SafeSigned helper class. Compile it with "-O3". Now your code to check for overflow after the fact won't get magically deleted by that pesky compiler. This code is safe and secure. Oh, sorry, here's the entire command line, I forgot, I'm talking to mac users here: "c++ -O3 -std=c++17 file.cpp"

(This is just a joke, I love Rust, please don't kill me or my family)

// c++11 except for optional

#include <algorithm>
#include <limits>
#include <optional>
#include <type_traits>

template<class Int>
class SafeSigned {
  static_assert(std::is_signed<int>::value, "Argument type must be signed");

  using underlying_type = typename std::make_unsigned<Int>::type;
  underlying_type _storage;

  SafeSigned(underlying_type a)
    : _storage(a) {}

  template<class Uint>
  static bool is_neg(Uint a) {
    auto signed_boundary = std::numeric_limits<Uint>::max() / 2 + 1;
    return a >= signed_boundary;
  }

  template<class Uint, class Uint2>
  static Uint signext(Uint2 a) {
    if (is_neg(a)) {
      return static_cast<Uint>(0) - (-a);
    } else {
      return a;
    }
  }

  underlying_type _is_neg() const {
    return is_neg(_storage);
  }

  underlying_type _abs() const {
    if (_is_neg()) {
      return -_storage;
    }
    return _storage;
  }

  template<class Int2>
  static typename std::make_unsigned<Int2>::type iabs(Int2 a) {
    using ut = typename std::make_unsigned<Int2>::type;
    auto ret = static_cast<ut>(a);
    return a < 0 ? -ret : ret;
  }

public:
  SafeSigned() = delete;

  template<class Int2, class = typename std::enable_if<std::is_signed<Int2>::value &&
                                                       std::is_integral<Int2>::value>::type>
  bool operator <(const Int2 & other) const {
    using out = typename std::make_unsigned<Int2>::type;
    using ct = decltype(static_cast<underlying_type>(0) + static_cast<out>(0));
    auto a = signext<ct>(_storage);
    auto b = signext<ct>(other);

    if (is_neg(a) == is_neg(b)) {
      return a < b;
    } else {
      return is_neg(a);
    }
  }

  template<class Int2, class Int3 = decltype(static_cast<Int>(0) + static_cast<Int2>(0)),
           class = typename std::enable_if<std::is_signed<Int2>::value &&
                                           std::is_integral<Int2>::value>::type>
  SafeSigned<Int3> operator *(const Int2 & other) const {

    auto raw = _abs() * iabs(other);

    if (_is_neg() != (other < 0)) {
      raw = -raw;
    }

    return SafeSigned<Int3>(raw);
  }

  template<class Int2, class Int3 = decltype(static_cast<Int>(0) + static_cast<Int2>(0)),
           class = typename std::enable_if<std::is_signed<Int2>::value &&
                                           std::is_integral<Int2>::value>::type>
  SafeSigned<Int3> operator /(const Int2 & other) const {

    auto raw = _abs() / iabs(other);

    if (_is_neg() != (other < 0)) {
      raw = -raw;
    }

    return SafeSigned<Int3>(raw);
  }

  std::optional<Int> get() const {
    auto usmax = static_cast<underlying_type>(std::numeric_limits<Int>::max());
    auto usmin = static_cast<underlying_type>(std::numeric_limits<Int>::min());

    // this is for when our C++ compiler represents signed
    // integers differently than we do
    // if the C++ compiler uses twos complement this can be no-op
    if ((_is_neg() && _storage < usmin) ||
        (!_is_neg() && _storage > usmax)) {
      return std::nullopt;
    }

    // This is implementation-defined behavior
    // on < C++20, so we double check that it
    // does the right thing after.
    auto ret = static_cast<Int>(_storage);
    if (static_cast<underlying_type>(ret) != _storage) {
      return std::nullopt;
    }

    return ret;
  }

  template<class Int2>
  friend std::optional<SafeSigned<Int2>> make_safe_signed(Int2);
};

template<class Int>
std::optional<SafeSigned<Int>> make_safe_signed(Int a) {
  using ut = typename SafeSigned<Int>::underlying_type;
  ut comp_value = static_cast<ut>(a);

  // this is for when our C++ compiler represents signed
  // integers differently than we do
  // if the C++ compiler uses twos complement this can be no-op
  auto signed_boundary = std::numeric_limits<ut>::max() / 2 + 1;
  if ((a >= 0 && comp_value >= signed_boundary) ||
      (a < 0 && comp_value < signed_boundary)) {
    return std::nullopt;
  }

  return SafeSigned<int>(comp_value);
}

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

uint8_t tab[0x1ff + 1];

uint8_t f(int32_t x__)
{
  auto x_ = make_safe_signed(x__);
  if (!x_ || *x_ < 0)
    return 0;
  auto x = *x_;
  auto i_ = (x * 0x1ff / 0xffff).get();
  if (!i_)
    return 0;
  auto i = *i_;
  if (i >= 0 && ((uint32_t) i) < sizeof(tab)) {
    printf("tab[%d] looks safe because %d is between [0;%d[\n", i, i, (int)sizeof(tab));
    return tab[i];
  }

  return 0;
}

int main(int ac, char **av)
{
  (void) ac;
  return f(atoi(av[1]));
}
Edit
Pub: 10 Dec 2022 20:00 UTC
Edit: 10 Dec 2022 20:01 UTC
Views: 12275