slowmath is a header-only C++ library providing checked arithmetic operations.
#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);
}
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.
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 overflowsquare_checked()
: throws std::system_error
on overflowtry_square()
: returns a value/error-code aggregatesquare_failfast()
: checks for overflow using gsl_Assert()
Header file: <slowmath/arithmetic.hpp>
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.
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.
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.
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;
};
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.
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).
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 |
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.
[1] safe-math in https://github.com/nemequ/portable-snippets
by Evan Nemerson
[2] Boost.SafeNumerics by Robert Ramey
[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
Code licensed under the Boost Software License.