slowmath

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

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 git@github.com: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.

Name		Name	Last commit message	Last commit date
Latest commit History 89 Commits
assets/css		assets/css
ci		ci
cmake		cmake
extra		extra
include/slowmath		include/slowmath
src		src
test		test
.gitignore		.gitignore
CMakeLists.txt		CMakeLists.txt
LICENSE.txt		LICENSE.txt
README.md		README.md
_config.yml		_config.yml
cpp.hint		cpp.hint
vcpkg.json		vcpkg.json

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Repository files navigation

slowmath

Contents

Introduction

Example usage

Motivation

Why slowmath?

Reference

Integer arithmetic

Basic arithmetic operations

Extended arithmetic operations

Factorization

Bit operations

Floating-point environment

Supported platforms

Dependencies

Use and installation

Alternatives

References

License

About

Releases

Packages

Languages

License

mbeutel/slowmath

Folders and files

Latest commit

History

Repository files navigation

slowmath

Contents

Introduction

Example usage

Motivation

Why slowmath?

Reference

Integer arithmetic

Basic arithmetic operations

Extended arithmetic operations

Factorization

Bit operations

Floating-point environment

Supported platforms

Dependencies

Use and installation

Alternatives

References

License

About

Resources

License

Stars

Watchers

Forks

Releases

Packages 0

Languages

Packages