mbeutel/slowmath

Checked arithmetic for C++

slowmath

slowmath is a header-only C++ library providing checked arithmetic operations.

Contents

• Introduction
  • Example usage
  • Motivation
  • Why slowmath?
• Reference
  • Integer arithmetic
  • Floating-point environment
• Supported platforms
• Dependencies
• Use and installation
• Alternatives
• References
• License

Introduction

Example usage

#include <slowmath/arithmetic.hpp>

std::size_t computeBufferSize(std::size_t numElements, std::size_t elementSize)
{
    // Throws `std::system_error` with `std::errc::value_too_large` on overflow.
    return slowmath::multiply_checked(numElements, elementSize);
}

Motivation

C++ is infamous for the abundance of undefined behavior (UB) in the language and standard library specification. Perhaps most notably, signed integer overflow is undefined in C++. This defeats many naïve attempts at guarding against overflow:

// bad code
int faultyCheckedAdd(int a, int b)
{
    assert(!(a > 0 && b > 0 && a + b < 0)   // Idea: if both values have equal sign, and if adding them
        && !(a < 0 && b < 0 && a + b > 0)); // changes the sign, the value must have overflown.
    return a + b;
}

The author of this snippet intuitively wanted to exploit the fact that most hardware implementation of signed integers wrap around on overflow. However, this doesn't work as expected: signed integer overflow is undefined, hence the compiler may legally assume it never happens. As a consequence, some compilers will simply elide the naïve overflow check:

faultyCheckedAdd(int, int):
        lea     eax, [rdi+rsi]
        ret

The goal of this library is to provide a set of common arithmetic routines with UB-free overflow checks.

Why slowmath?

Other libraries for checked arithmetic in C and C++ exist, but none of them quite works the way I want.

slowmath was built with the following goals in mind:

• Checked arithmetic operations for the existing integer types, not a new set of integer types with checked operations.

  Checking all arithmetic operations for overflow during testing is a reasonable demand, but for that I recommend using UndefinedBehaviorSanitizer.

  If you really want every operation to be checked even in production code, you probably want to use Boost.SafeNumerics.

• Generic routines.
  I want a single function template multiply_checked() rather than a host of functions with type-encoded names like UIntPtrMult() or psnip_safe_int16_mul().

• constexpr support.
  All checked arithmetic routines should be constexpr; an overflow in a compile-time computation should be a compile-time error.

• Portable code.
  Most hardware implementations have support for detecting integer overflow, e.g. x86 sets the overflow flag if an overflow occurs. But as John Regehr points out, it is surprisingly difficult to get compilers to generate efficient code for overflow checks. The most reliable way to get efficient codegen is to use compiler intrinsics or platform-specific libraries. The downside is that these are not portable and typically not constexpr.

  slowmath favors portability over efficiency; we want efficient codegen where possible, but there should always be a portable ISO C++-compliant fallback.

• Precondition checks.
  Many arithmetic operations have preconditions, e.g. division requires that the divisor be ≠ 0. Unlike overflows, precondition violations are always programmer errors. All arithmetic functions in slowmath check their preconditions with gsl_Expects().

• Flexible error handling.
  For arithmetic operations that can fail, slowmath provides functions with different error handling semantics:

  • square(): does not check for overflow
  • square_checked(): throws std::system_error on overflow
  • try_square(): returns a value/error-code aggregate
  • square_failfast(): checks for overflow using gsl_Assert()

Reference

Integer arithmetic

Header file: <slowmath/arithmetic.hpp>

• Basic arithmetic operations: addition, subtraction, multiplication, division, modulo
• Extended arithmetic operations: square, exponentiation, rounding, logarithm
• Factorization: greatest common divisor, least common multiple, integer factorization
• Bit operations: shift left, shift right

All integer arithmetic operations expect their arguments to be either of integral type other than bool, or of type std::integral_constant<T, V> where T is an integral type other than bool.

Most arithmetic operations come in different versions with different error handling semantics:

• Arithmetic operations without prefixes or suffixes (e.g. square()) check their preconditions with gsl_Expects() and perform no further overflow checks.

  Example:

  int numBuckets(int numElements, int bucketSize)
  {
      // Fails precondition check if `bucketSize == 0`.
      return slowmath::ratio_ceili(numElements, bucketSize);
  }

• Arithmetic operations with a _checked suffix (e.g. square_checked()) check their preconditions with gsl_Expects() and throw an exception of type std::system_error with error std::errc::value_too_large on overflow.

  Example:

  int main(void)
  try
  {
      int vectorSize;
      if (std::cin >> vectorSize)
      {
          // Throws `std::system_error` on overflow.
          int matrixSize = slowmath::square_checked(vectorSize);
          ...
      }
  }
  catch (std::runtime_error const& e)
  {
      std::cerr << "Error: " << e.what() << '\n';
      return 1;
  }

• Arithmetic operations with a try_ prefix (e.g. try_square()) check their preconditions with gsl_Expects() and return an object of type slowmath::arithmetic_result<>, which is defined as

  template <typename T>
  struct arithmetic_result
  {
      T value;
      std::errc ec; // `ec == std::errc{ }` if operation succeeded
  };

  Example:

  int main(void)
  {
      int vectorSize;
      if (std::cin >> vectorSize)
      {
          slowmath::arithmetic_result<int> matrixSizeR = slowmath::try_square(vectorSize);
          if (matrixSizeR.ec != std::errc{ })
          {
              std::cerr << "Error: vector size too large (integer overflow)\n";
              return 1;
          }
          int matrixSize = matrixSizeR.value;
          ...
      }
  }

• Arithmetic operations with a _failfast suffix (e.g. square_failfast()) check their preconditions with gsl_Expects() and use gsl_Assert() to check for overflow.

Basic arithmetic operations

function	preconditions	result
absi(a) absi_checked(a) absi_failfast(a) try_absi(a)	a ∊ ℤ	|a|
negate_checked(a) negate_failfast(a) try_negate(a)	a ∊ ℤ	-a
add_checked(a,b) add_failfast(a,b) try_add(a,b)	a,b ∊ ℤ	a + b
subtract_checked(a,b) subtract_failfast(a,b) try_subtract(a,b)	a,b ∊ ℤ	a - b
multiply_checked(a,b) multiply_failfast(a,b) try_multiply(a,b)	a,b ∊ ℤ	a ∙ b
divide(n,d) divide_checked(n,d) divide_failfast(n,d) try_divide(n,d)	n,d ∊ ℤ, d ≠ 0	n ÷ d
modulo(n,d) modulo_checked(n,d) modulo_failfast(n,d) try_modulo(n,d)	n,d ∊ ℤ, d ≠ 0	n mod d

The types of both arguments of each add, subtract, multiply, divide, and modulo operation must have identical signedness.

Extended arithmetic operations

function	preconditions	result
square(a) square_checked(a) square_failfast(a) try_square(a)	a ∊ ℤ	a²
powi(b,e) powi_checked(b,e) powi_failfast(b,e) try_powi(b,e)	b ∊ ℤ, e ∊ ℕ₀	bᵉ
floori(x,d)	x ∊ ℕ₀, d ∊ ℕ, d ≠ 0	⌊x ÷ d⌋ ∙ d
ceili(x,d) ceili_checked(x,d) ceili_failfast(x,d) try_ceili(x,d)	x ∊ ℕ₀, d ∊ ℕ, d ≠ 0	⌈x ÷ d⌉ ∙ d
ratio_floori(n,d)	n ∊ ℕ₀, d ∊ ℕ, d ≠ 0	⌊n ÷ d⌋
ratio_ceili(n,d)	n ∊ ℕ₀, d ∊ ℕ, d ≠ 0	⌈n ÷ d⌉
log_floori(x,b)	x,b ∊ ℕ, x > 0, b > 1	⌊log x ÷ log b⌋
log_ceili(x,b)	x,b ∊ ℕ, x > 0, b > 1	⌈log x ÷ log b⌉

The types of both arguments of each floori, ceili, ratio_floori, ratio_ceil, log_floori, and log_ceil operation must have identical signedness.

Factorization

function	preconditions	result
gcd_checked(a, b) gcd_failfast(a, b) try_gcd(a, b)	a,b ∊ ℤ	greatest common divisor of a and b
lcm_checked(a, b) lcm_failfast(a, b) try_lcm(a, b)	a,b ∊ ℤ	least common multiple of a and b
factorize_floori<E>(x,b)	x,b ∊ ℕ, x > 0, b > 1	(r,e) such that x = bᵉ + r with r ≥ 0 minimal
factorize_ceili<E>(x,b) factorize_ceili_checked<E>(x,b) factorize_ceili_failfast<E>(x,b) try_factorize_ceili<E>(x,b)	x,b ∊ ℕ, x > 0, b > 1	(r,e) such that x = bᵉ - r with r ≥ 0 minimal
factorize_floori<E>(x,a,b)	x,a,b ∊ ℕ, x > 0, a,b > 1, a ≠ b	(r,i,j) such that x = aⁱ ∙ bʲ + r with r ≥ 0 minimal
factorize_ceili<E>(x,a,b) factorize_ceili_checked<E>(x,a,b) factorize_ceili_failfast<E>(x,a,b) try_factorize_ceili<E>(x,a,b)	x,a,b ∊ ℕ, x > 0, a,b > 1, a ≠ b	(r,i,j) such that x = aⁱ ∙ bʲ - r with r ≥ 0 minimal

The types of all function arguments of each gcd, lcm, factorize_floori, and factorize_ceili operation must have identical signedness.

Like std::gcd() and std::lcm(), the functions gcd_checked(), gcd_failfast(), try_gcd(), lcm_checked(), lcm_failfast() and try_lcm() are supported only for C++17 and higher.

The factorize family of functions require a template type argument E that indicates which type to use to store factor exponents. They return a value of the aggregate type slowmath::factorization<V, E, N> defined as

template <typename V, typename E, int NumFactors>
struct factorization;
template <typename V, typename E>
struct factorization<V, E, 1>
{
    V remainder;
    E exponent1;

    constexpr friend bool operator ==(factorization const&, factorization const&) noexcept;
    constexpr friend bool operator !=(factorization const&, factorization const&) noexcept;
};
template <typename V, typename E>
struct factorization<V, E, 2>
{
    V remainder;
    E exponent1;
    E exponent2;

    constexpr friend bool operator ==(factorization const&, factorization const&) noexcept;
    constexpr friend bool operator !=(factorization const&, factorization const&) noexcept;
};

Bit operations

function	preconditions	result
shift_left(x, s) shift_left_checked(x, s) shift_left_failfast(x, s) try_shift_left(x, s)	x,s ∊ ℕ₀	x ∙ 2ˢ (i.e. x left-shifted by s bits)
shift_right(x, s) shift_right_checked(x, s) shift_right_failfast(x, s) try_shift_right(x, s)	x,s ∊ ℕ₀	⌊x ÷ 2ˢ⌋ (i.e. x right-shifted by s bits)

Note: The result of right-shifting negative numbers with the built-in arithmetic shift operator is valid but implementation-dependent. Unlike the built-in shift operator, shift_right() does not support negative operands.

Floating-point environment

Header file: <slowmath/fenv.hpp>

---

void fe_set_trapping_exceptions(int excepts);

Sets hardware exception traps for the floating-point exceptions specified by the given mask value.

The admissible mask values are defined as FE_* in standard header <cfenv>.
If an exception flag bit is set, the corresponding exception will be trapped; if the bit is clear, the exception will be masked.

---

int fe_get_trapping_exceptions(void);

Returns the bitmask of all floating-point exceptions for which trapping is currently enabled.

The admissible mask values are defined as FE_* in standard header <cfenv>.

---

Floating-point exceptions are usually silent, i.e. they only set an exception state in the floating-point unit but do not affect the flow of execution. Using fe_set_trapping_exceptions(), the FPU can be configured to trigger a hardware exception for certain floating-point exceptions, which raises a SIGFPE signal on POSIX platforms or a SEH exception on Windows.

Example:

#include <slowmath/fenv.hpp>

int main(void)
{
    // Configure FPU to generate hardware exception on division by 0.
    slowmath::fe_set_trapping_exceptions(FE_DIVBYZERO);

    // Run program.
    ...
}

Note that, if the compiler is configured to perform aggressive floating-point optimizations, floating-point exceptions may be raised at seemingly unrelated points in the code, or may not be raised at all. For the highest fidelity in error diagnosis, configure your compiler to perform only IEEE-754-conforming floating-point optimizations (cf. compiler options for MSVC, GCC, Clang, ICC, NVCC).

Supported platforms

The checked arithmetic operations in <slowmath/arithmetic.hpp> should work with every compliant C++14 compiler and have no platform dependencies.

The floating-point environment operations in <slowmath/fenv.hpp> are currently implemented for Windows, Linux, and MacOS.

slowmath is continuously tested with the following compilers and platforms:

Compiler	OS	Platforms	Versions
GCC	Linux, MacOS	x64	10 and newer
Clang	Linux	x64	12 and newer
MSVC (Visual Studio)	Windows	x86, x64	19.2 (VS 2019) and newer
Clang	Windows	x64	as supplied with VS
AppleClang (Xcode)	MacOS	x64	13.1.6 and newer
NVCC (CUDA Toolkit)	Linux, Windows	x64	11.8 and newer

Dependencies

• gsl-lite
• for unit tests: Catch2

Use and installation

slowmath comes with a CMake package config file that exports a target slowmath::slowmath to which you can link your CMake target:

find_package(slowmath 0.4 REQUIRED)

add_executable(my_proj "main.cpp")
target_link_libraries(my_proj PRIVATE slowmath::slowmath)

It can also be configured manually:

git clone [email protected]:mbeutel/slowmath.git
cd slowmath
mkdir build
cd build
cmake ..

To use the slowmath build directory as a CMake package, specify -Dslowmath_DIR:FILEPATH=<slowmath-dir>/build on the command line when configuring your project with CMake.

Alternatives

[1] safe-math in https://github.com/nemequ/portable-snippets by Evan Nemerson
[2] Boost.SafeNumerics by Robert Ramey

References

[1] SEI CERT C Coding Standard, Rule 04. Integers (INT). The implementation of slowmath mostly follows the techniques presented here.
[2] W. Dietz et al., Understanding Integer Overflow in C/C++, 2015
[3] cppreference.com, Undefined behavior
[4] Project Nayuki, Undefined behavior in C and C++ programs

License

Code licensed under the Boost Software License.

slowmath's Issues

Perhaps use ``/`_nothrow`/`_failfast` instead of `_or_throw`/``/`try_`?

...thereby making the throwing variant the default, which might make sense because numeric overflows are usually not precondition violations.

Inspired by WIL:
https://github.com/microsoft/wil/wiki/safe_cast

Add standard math functions with precondition checking

For example:

double
sqrt(double x)
{
    gsl_Expects(x >= 0);
    return std::sqrt(x);
}

Add missing tests

A lot of tests are currently missing (cf. comments in the test sources).

`log_floori()` and `log_ceili()` can be implemented more efficiently

Both log_floori() and log_ceili() can probably be implemented more efficiently with base-2 logarithms (i.e. with bit_scan_reverse()).

Improve codegen for runtime checks

Use std::is_constant_evaluated() to get improved codegen in case of runtime execution by conditionally using GCC's and Clang's intrinsics. Assess if optimal codegen can be achieved with MSVC on Windows without resorting to assembly code; perhaps by using IntSafe.h?

Add more CI: code coverage, static analysis

We should have automated code coverage testing, and also run some static code analysis.

Add documentation

Document "slowmath" using Sphinx (cf. https://www.sphinx-doc.org/en/master/, https://devblogs.microsoft.com/cppblog/clear-functional-c-documentation-with-sphinx-breathe-doxygen-cmake/). Don't bother with Doxygen and Breathe, just write plain Sphinx.

Can `factorize_ceili()` be rewritten such that no overflow can occur?

The two overloads of factorize_floori() always succeed (provided the preconditions hold) because they were carefully written to avoid any possible overflow. However, both factorize_ceili() overloads can currently overflow. I suspect that factorize_ceili() could also be reformulated such that no overflow can occur overflows occur in fewer cases (e.g. the related log_ceili() is overflow-free).

Efficiency of `powi()`

The implementation of powi() attempts to achieve 𝒪(log(N)) rather than the 𝒪(N) of a naïve implementation (multiplying factors in a loop). But is this actually faster? Is any compiler capable of compiling bit_scan_reverse() as BSR? Can this be forced with an intrinsic (guarded by std::is_constant_evaluated())?