sanisizer
Sanitize sizes to avoid integer overflow
Loading...
Searching...
No Matches
sanisizer Namespace Reference

Sanitize sizes to avoid integer overflow. More...

Classes

struct  Bounded
 Bound the maximum possible value of an integer. More...
 
class  Cast
 Cast an integer in a function call. More...
 
struct  Constant
 Integer constant. More...
 
class  Exact
 Do not cast an integer in a function call. More...
 
struct  is_Bounded
 
struct  is_Bounded< Bounded< Integer_, max_ > >
 
struct  is_Constant
 
struct  is_Constant< Constant< Integer_, value_ > >
 

Functions

template<typename Max_ , Max_ new_max_, typename Value_ >
constexpr auto set_bound (Value_ x)
 
template<typename MaxType_ , typename Value_ >
constexpr auto set_bound_by_type (Value_ x)
 
template<typename Max_ , Max_ new_max_, typename Value_ >
constexpr auto set_bound_unsafe (Value_ x)
 
template<typename MaxType_ , typename Value_ >
constexpr auto set_bound_by_type_unsafe (Value_ x)
 
template<typename Dest_ , typename Value_ >
constexpr Dest_ cap (Value_ x)
 
template<typename Dest_ , typename Value_ >
constexpr bool can_cast (Value_ x)
 
template<typename Dest_ , typename Value_ >
constexpr Dest_ cast (Value_ x)
 
template<typename Left_ , typename Right_ >
constexpr bool is_equal (Left_ left, Right_ right)
 
template<typename Left_ , typename Right_ >
constexpr bool is_less_than (Left_ left, Right_ right)
 
template<typename Left_ , typename Right_ >
constexpr bool is_less_than_or_equal (Left_ left, Right_ right)
 
template<typename Left_ , typename Right_ >
constexpr bool is_greater_than (Left_ left, Right_ right)
 
template<typename Left_ , typename Right_ >
constexpr bool is_greater_than_or_equal (Left_ left, Right_ right)
 
template<typename First_ , typename Second_ >
constexpr auto min (First_ first, Second_ second)
 
template<typename First_ , typename Second_ >
constexpr auto max (First_ first, Second_ second)
 
template<typename Container_ , typename Value_ >
constexpr auto as_size_type (Value_ x)
 
template<class Container_ , typename Value_ , typename ... Args_>
Container_ create (Value_ x, Args_ &&... args)
 
template<class Container_ , typename Value_ , typename ... Args_>
void resize (Container_ &container, Value_ x, Args_ &&... args)
 
template<class Container_ , typename Value_ , typename ... Args_>
void reserve (Container_ &container, Value_ x, Args_ &&... args)
 
template<typename Float_ >
int required_bits_for_float (Float_ x)
 
template<typename Integer_ , typename Float_ >
Integer_ from_float (Float_ x)
 
template<typename Float_ , typename Value_ >
Float_ to_float (Value_ x)
 
template<typename Value_ >
constexpr auto get_value (const Value_ x)
 
template<typename Value_ >
constexpr auto get_max ()
 
template<typename Size_ , typename FirstIndex_ , typename FirstExtent_ , typename SecondIndex_ , typename... Remaining_>
constexpr Size_ nd_offset (FirstIndex_ x1, FirstExtent_ extent1, SecondIndex_ x2, Remaining_... remaining)
 
template<typename Dest_ , typename First_ , typename ... Args_>
constexpr std::optional< Dest_ > product_maybe (First_ first, Args_... more)
 
template<typename Dest_ , typename First_ , typename ... Args_>
constexpr Dest_ product (First_ first, Args_... more)
 
template<typename Dest_ , typename First_ , typename ... Args_>
constexpr Dest_ product_unsafe (First_ first, Args_... more)
 
template<typename Dest_ , typename First_ , typename ... Args_>
constexpr std::optional< Dest_ > sum_maybe (First_ first, Args_... more)
 
template<typename Dest_ , typename First_ , typename ... Args_>
constexpr Dest_ sum (First_ first, Args_... more)
 
template<typename Dest_ , typename Value_ >
Dest_ plus_one (Value_ x)
 
template<typename Integer_ >
Integer_ & increment (Integer_ &x)
 
template<typename Dest_ , typename First_ , typename ... Args_>
constexpr Dest_ sum_unsafe (First_ first, Args_... more)
 

Detailed Description

Sanitize sizes to avoid integer overflow.

Function Documentation

◆ as_size_type()

template<typename Container_ , typename Value_ >
auto sanisizer::as_size_type ( Value_ x)
constexpr

Cast an integer to the size type of a container. This protects against overflow/wraparound when using this integer in the container's constructor or resize()/reserve() methods.

Template Parameters
Container_Container class with a size() method and a constructor that accepts the size as the first argument.
Value_Integer type of the input size.
Parameters
xNon-negative value representing the desired container size.
Returns
x as the container's size's type.

◆ can_cast()

template<typename Dest_ , typename Value_ >
bool sanisizer::can_cast ( Value_ x)
constexpr
Template Parameters
Dest_Integer type of the destination.
Value_Integer type, Bounded or Constant.
Parameters
xRepresentation of an integer value.
Returns
Whether x's value would overflow/wraparound when stored in Dest_.

◆ cap()

template<typename Dest_ , typename Value_ >
Dest_ sanisizer::cap ( Value_ x)
constexpr

Cap a non-negative integer at the largest value of a destination type. This is primarily intended for setting appropriate default values of function arguments and class variables.

Template Parameters
Dest_Integer type of the destination.
Value_Integer, Bounded or Constant.
Parameters
xNon-negative value to be capped.
Returns
x if it can be represented in Dest_, otherwise the maximum value of Dest_.

◆ cast()

template<typename Dest_ , typename Value_ >
Dest_ sanisizer::cast ( Value_ x)
constexpr

Cast a non-negative integer to a destination type, typically the size type of a C-style array or STL container. This avoids accidental overflow/wraparound from an implicit cast when x is used in new or the container's constructor.

Template Parameters
Dest_Integer type of the destination.
Value_Integer type, Bounded or Constant.
Parameters
xNon-negative value to be casted.
Returns
x as a Dest_. An error is thrown if overflow/wraparound would occur.

◆ create()

template<class Container_ , typename Value_ , typename ... Args_>
Container_ sanisizer::create ( Value_ x,
Args_ &&... args )

Create a new container of a specified size. This protects against overflow/wraparound when casting the integer size to the container's size type, see as_size_type() for details.

Template Parameters
Container_Container class with a size() method and a constructor that accepts the size as the first argument.
Value_Integer type of the input size.
Args_Further arguments to pass to the container's constructor.
Parameters
xNon-negative value representing the desired container size.
argsAdditional arguments to pass to the Container_ constructor after the size.
Returns
An instance of the container, constructed to be of size x.

◆ from_float()

template<typename Integer_ , typename Float_ >
Integer_ sanisizer::from_float ( Float_ x)

Cast a non-negative floating-point number to an integer. This checks that the conversion is possible, otherwise it throws an exception. Such a cast is occasionally necessary when floating-point calculations are used to derive the size of a container, number of loop iterations, etc.

Template Parameters
Integer_Integer type.
Float_Floating-point type.
Parameters
xFloating-point number, usually holding some kind of size.
Returns
The value of x as an integer, after truncation.
Exceptions
std::domain_errorThrown if x is negative or non-finite.
std::overflow_errorThrown if x is too large to be stored in Integer_.

◆ get_max()

template<typename Value_ >
auto sanisizer::get_max ( )
constexpr
Template Parameters
Value_Integer type, Bounded, or Constant.
Returns
The maximum value of all instances of Value_.

◆ get_value()

template<typename Value_ >
auto sanisizer::get_value ( const Value_ x)
constexpr
Template Parameters
Value_Integer type, Bounded or Constant.
Parameters
xInteger value or an Bounded about an integer.
Returns
x if it is already an integer, otherwise Bounded::value.

◆ increment()

template<typename Integer_ >
Integer_ & sanisizer::increment ( Integer_ & x)

Convenience wrapper for x = plus_one<Dest_>(x), i.e., ++x with an exception if overflow/wraparound is detected.

Template Parameters
Dest_Integer type of the destination.
Value_Integer type of the value.
Parameters
xNon-negative value. On output, this is incremented by 1.
Returns
Reference to x after increment.

◆ is_equal()

template<typename Left_ , typename Right_ >
bool sanisizer::is_equal ( Left_ left,
Right_ right )
constexpr
Template Parameters
Left_Integer type of the value on the left hand side of the comparison. This may also be a Constant or Bounded.
Right_Integer type of the value on the right hand side of the comparison. This may also be a Constant or Bounded.
Parameters
leftNon-negative value on the left hand side of the comparison.
rightNon-negative value on the right hand side of the comparison.
Returns
Whether left is equal to right.

◆ is_greater_than()

template<typename Left_ , typename Right_ >
bool sanisizer::is_greater_than ( Left_ left,
Right_ right )
constexpr
Template Parameters
Left_Integer type of the value on the left hand side of the comparison. This may also be a Constant or Bounded.
Right_Integer type of the value on the right hand side of the comparison. This may also be a Constant or Bounded.
Parameters
leftNon-negative value on the left hand side of the comparison.
rightNon-negative value on the right hand side of the comparison.
Returns
Whether left is greater than right.

◆ is_greater_than_or_equal()

template<typename Left_ , typename Right_ >
bool sanisizer::is_greater_than_or_equal ( Left_ left,
Right_ right )
constexpr
Template Parameters
Left_Integer type of the value on the left hand side of the comparison. This may also be a Constant or Bounded.
Right_Integer type of the value on the right hand side of the comparison. This may also be a Constant or Bounded.
Parameters
leftNon-negative value on the left hand side of the comparison.
rightNon-negative value on the right hand side of the comparison.
Returns
Whether left is greater than or equal to right.

◆ is_less_than()

template<typename Left_ , typename Right_ >
bool sanisizer::is_less_than ( Left_ left,
Right_ right )
constexpr
Template Parameters
Left_Integer type of the value on the left hand side of the comparison. This may also be a Constant or Bounded.
Right_Integer type of the value on the right hand side of the comparison. This may also be a Constant or Bounded.
Parameters
leftNon-negative value on the left hand side of the comparison.
rightNon-negative value on the right hand side of the comparison.
Returns
Whether left is less than right.

◆ is_less_than_or_equal()

template<typename Left_ , typename Right_ >
bool sanisizer::is_less_than_or_equal ( Left_ left,
Right_ right )
constexpr
Template Parameters
Left_Integer type of the value on the left hand side of the comparison. This may also be a Constant or Bounded.
Right_Integer type of the value on the right hand side of the comparison. This may also be a Constant or Bounded.
Parameters
leftNon-negative value on the left hand side of the comparison.
rightNon-negative value on the right hand side of the comparison.
Returns
Whether left is less than or equal to right.

◆ max()

template<typename First_ , typename Second_ >
auto sanisizer::max ( First_ first,
Second_ second )
constexpr
Template Parameters
First_Integer type of the first value. This may also be a Bounded or Constant.
Second_Integer type of the second value. This may also be a Bounded or Constant.
Parameters
firstFirst non-negative value.
secondSecond non-negative value.
Returns
The larger of first and second, in the larger integer type of First_ and Second_.

◆ min()

template<typename First_ , typename Second_ >
auto sanisizer::min ( First_ first,
Second_ second )
constexpr
Template Parameters
First_Integer type of the first value. This may also be a Bounded or Constant.
Second_Integer type of the second value. This may also be a Bounded or Constant.
Parameters
firstFirst non-negative value.
secondSecond non-negative value.
Returns
The smaller of first and second, in the smaller integer type of First_ and Second_.

◆ nd_offset()

template<typename Size_ , typename FirstIndex_ , typename FirstExtent_ , typename SecondIndex_ , typename... Remaining_>
Size_ sanisizer::nd_offset ( FirstIndex_ x1,
FirstExtent_ extent1,
SecondIndex_ x2,
Remaining_... remaining )
constexpr

Compute offsets for accessing elements in a flattened N-dimensional array (for N > 1). The first dimension is assumed to be the fastest-changing, followed by the second dimension, and so on.

Template Parameters
Size_Integer type to represent the size of the flattened array.
FirstIndex_Type of the index on the first dimension. This may be an integer type, Bounded or Constant. It is assumed that this can be safely cast to Size_, as overflow/wraparound checks should have been performed during array allocation, e.g., via product().
FirstExtent_Type of the extent of the first dimension. This may be an integer type, Bounded or Constant. It is assumed that this can be safely cast to Size_, as overflow/wraparound checks should have been performed during array allocation, e.g., via product().
SecondIndex_Type of the index on the second dimension. This may be an integer type, Bounded or Constant. It is assumed that this can be safely cast to Size_, as overflow/wraparound checks should have been performed during array allocation, e.g., via product().
Remaining_Additional arguments for further dimensions. Each argument should should be either an integer type, Bounded or Constant. It is assumed that all types can be safely cast to Size_, as overflow/wraparound checks should have been performed during array allocation, e.g., product().
Parameters
x1Position on the first dimension.
extent1Extent of the first dimension.
x2Position on the second dimension.
remainingAdditional arguments for further dimensions. These should be (extentP, xQ) pairs where extentP is the extent of the P-th dimension and xQ is the position on the Q = P + 1-th dimension. For example, for a 3-dimensional array, we would expect an extent2 and x3 argument.
Returns
Offset into the array for element (x1, x2, ...).

◆ plus_one()

template<typename Dest_ , typename Value_ >
Dest_ sanisizer::plus_one ( Value_ x)

Convenience wrapper for sum<Dest_>(x, 1), i.e., get_value(x) + 1 with an exception if overflow/wraparound is detected.

Template Parameters
Dest_Integer type of the destination.
Value_Integer type of the value. This may also be a Bounded or Constant.
Parameters
xNon-negative value.
Returns
The value of x plus 1.

◆ product()

template<typename Dest_ , typename First_ , typename ... Args_>
Dest_ sanisizer::product ( First_ first,
Args_... more )
constexpr

Multiply two or more non-negative values, e.g., to compute the size of a flattened N-dimensional array as the product of its dimension extents. If overflow/wraparound in the destination type is detected, an exception is thrown. (See also product_maybe() to return an empty object upon overflow/wraparound.)

For consistency, this function will also check that each input value can be cast to Dest_. This ensures that per-dimension indices/extents can be safely represented as Dest_ in later steps (e.g., nd_offset()). These checks are necessary as the product may fit in Dest_ but not the input values if any one of the inputs is zero.

Template Parameters
Dest_Integer type of the destination.
First_Integer type of the first value. This may be also be a Bounded or Constant.
Args_Integer types of additional values. Any number of these may also be Bounded or Constant.
Parameters
firstNon-negative value to multiply.
moreAdditional non-negative values to multiply.
Returns
Product of all arguments as a Dest_.
Exceptions
std::overflow_errorThrown if an overflow/wraparound would occur.

◆ product_maybe()

template<typename Dest_ , typename First_ , typename ... Args_>
std::optional< Dest_ > sanisizer::product_maybe ( First_ first,
Args_... more )
constexpr

Multiply two or more non-negative values. If overflow/wraparound in the destination type is detected, an empty object is returned. See also product() to throw an exception upon overflow/wraparound.

For consistency, this function will also check that each input value can be cast to Dest_. See product() for more details.

Template Parameters
Dest_Integer type of the destination.
First_Integer type of the first value. This may be also be a Bounded or Constant.
Args_Integer types of additional values. Any number of these may also be Bounded or Constant.
Parameters
firstNon-negative value to multiply.
moreAdditional non-negative values to multiply.
Returns
Product of all arguments as a Dest_.
Exceptions
std::overflow_errorThrown if an overflow/wraparound would occur.

◆ product_unsafe()

template<typename Dest_ , typename First_ , typename ... Args_>
Dest_ sanisizer::product_unsafe ( First_ first,
Args_... more )
constexpr

Unsafe alternative to product() that casts its arguments to Dest_ but does not check for overflow/wraparound. This is more efficent than product() if it is already known that the product will not overflow, e.g., when computing std::size_t offsets into a pre-allocated array.

Template Parameters
Dest_Integer type of the destination.
First_Type of the first multiplication term. This should be an integer type, Bounded or Constant.
Args_Types of additional terms. Each of these should be either an integer type, Bounded or Constant.
Parameters
firstNon-negative term to multiply.
moreAdditional non-negative terms to multiply.
Returns
Product of all arguments as a Dest_.

◆ required_bits_for_float()

template<typename Float_ >
int sanisizer::required_bits_for_float ( Float_ x)
Template Parameters
Float_Floating-point type.
Parameters
xA finite non-negative integer. Specifically, a floating-point number for which the following is true: std::isfinite(x), x >= 0 and x == std::trunc(x).
Returns
Number of bits required to store x exactly in a (two's complement) integer type.

The return value can be compared to std::numeric_limits<Integer_>::digits to determine if Integer_ is large enough to store x.

◆ reserve()

template<class Container_ , typename Value_ , typename ... Args_>
void sanisizer::reserve ( Container_ & container,
Value_ x,
Args_ &&... args )

Reserve a container to the desired size. This protects against overflow/wraparound when casting the integer size to the container's size type, see as_size_type() for details.

In most cases involving std::vector, this protection is not necessary as the size type is unsigned and x would harmlessly wrap around to some smaller non-negative value. The reserved size would be smaller than x but would silently reallocate as necessary upon push_back() or insert() operations beyond that size. However, this function becomes useful when the user wants to ensure that no reallocations occur, either for performance reasons or to maintain iterator/pointer validity.

Template Parameters
Container_Container class with a size() method and a reserve() method that accepts the size as the first argument.
Value_Integer type of the input size.
Args_Further arguments to pass to the container's reserve() method.
Parameters
containerAn existing instance of the container. On return, its allocation is set to x.
xNon-negative value representing the desired container size.
argsAdditional arguments to pass to reserve() after the size.

◆ resize()

template<class Container_ , typename Value_ , typename ... Args_>
void sanisizer::resize ( Container_ & container,
Value_ x,
Args_ &&... args )

Resize a container to the desired size. This protects against overflow/wraparound when casting the integer size to the container's size type, see as_size_type() for details.

Template Parameters
Container_Container class with a size() method and a resize() method that accepts the size as the first argument.
Value_Integer type of the input size.
Args_Further arguments to pass to the container's resize() method.
Parameters
containerAn existing instance of the container. This is resized to size x.
xNon-negative value representing the desired container size.
argsAdditional arguments to pass to resize() after the size.

◆ set_bound()

template<typename Max_ , Max_ new_max_, typename Value_ >
auto sanisizer::set_bound ( Value_ x)
constexpr
Template Parameters
Max_Integer type of the new compile-time maximum.
new_max_The new compile-time maximum.
Value_Integer type, Bounded or Constant.
Parameters
xRepresentation of an integer value.
Returns
x if its maximum value is less than or equal to new_max_. Otherwise, an Bounded that declares this constraint.
Exceptions
std::domain_errorThrown if the value of x is greater than new_max_.

If x is known to be less than or equal to max_, users can call set_bound_unsafe() to avoid the check.

◆ set_bound_by_type()

template<typename MaxType_ , typename Value_ >
auto sanisizer::set_bound_by_type ( Value_ x)
constexpr

Variant of set_bound() that uses the maximum value of an integer type.

Template Parameters
MaxType_Integer type of the new compile-time maximum.
Value_Integer type, Bounded or Constant.
Parameters
xRepresentation of an integer value.
Returns
x if its maximum value is less than or equal to that of MaxType_. Otherwise, an Bounded that declares this constraint.

If x is known to be less than or equal to max_, users can call set_bound_by_type_unsafe() to avoid the check.

◆ set_bound_by_type_unsafe()

template<typename MaxType_ , typename Value_ >
auto sanisizer::set_bound_by_type_unsafe ( Value_ x)
constexpr

Variant of set_bound_unsafe() that uses the maximum value of an integer type.

Template Parameters
MaxType_Integer type of the new compile-time maximum.
Value_Integer type, Bounded or Constant.
Parameters
xRepresentation of an integer value. This should be less than or equal to the maximum value of MaxType_.
Returns
x if its maximum value is less than or equal to that of MaxType_. Otherwise, an Bounded that declares this constraint.

◆ set_bound_unsafe()

template<typename Max_ , Max_ new_max_, typename Value_ >
auto sanisizer::set_bound_unsafe ( Value_ x)
constexpr

Variant of set_bound() that assumes x <= new_max_ and does not throw exceptions.

Template Parameters
Max_Integer type of the new compile-time maximum.
new_max_The new compile-time maximum.
Value_Integer type, Bounded or Constant.
Parameters
xRepresentation of an integer value. This should be no greater than new_max_.
Returns
x if its maximum value is less than or equal to new_max_. Otherwise, an Bounded that declares this constraint.

◆ sum()

template<typename Dest_ , typename First_ , typename ... Args_>
Dest_ sanisizer::sum ( First_ first,
Args_... more )
constexpr

Add two or more non-negative values, e.g., to compute the size of an array that is a concatenation of smaller arrays. If overflow/wraparound in the destination type is detected, an exception is thrown. (See also sum_maybe() to return an empty object upon overflow/wraparound.)

Template Parameters
Dest_Integer type of the destination.
First_Integer type of the first value. This may also be a Bounded or Constant.
Args_Integer types of additional values. Any number of these may also be Bounded or Constant.
Parameters
firstFirst non-negative value to add.
moreAdditional non-negative values to add.
Returns
Sum of all arguments as a Dest_.
Exceptions
std::overflow_errorThrown if an overflow/wraparound occurs at any summation step.

◆ sum_maybe()

template<typename Dest_ , typename First_ , typename ... Args_>
std::optional< Dest_ > sanisizer::sum_maybe ( First_ first,
Args_... more )
constexpr

Add two or more non-negative values. If overflow/wraparound in the destination type is detected, an empty object is returned. (See also sum() to throw an exception upon overflow/wraparound.)

Template Parameters
Dest_Integer type of the destination.
First_Integer type of the first value. This may also be a Bounded or Constant.
Args_Integer types of additional values. Any number of these may also be Bounded or Constant.
Parameters
firstFirst non-negative value to add.
moreAdditional non-negative values to add.
Returns
Sum of all arguments as a Dest_, wrapped in a std::optional. An empty object is returned if overflow/wraparound is detected in the destination type at any step of the summation.

◆ sum_unsafe()

template<typename Dest_ , typename First_ , typename ... Args_>
Dest_ sanisizer::sum_unsafe ( First_ first,
Args_... more )
constexpr

Unsafe alternative to sum() that casts its arguments to Dest_ before summation but does not check for overflow/wraparound. This is more efficent than sum() if it is already known that the sum will not overflow, e.g., when computing std::size_t offsets into a pre-allocated array.

Template Parameters
Dest_Integer type of the destination.
First_Type of the first summation term. This should be an integer type, Bounded or Constant.
Args_Types of additional terms. Each of these should be either an integer type, Bounded or Constant.
Parameters
firstNon-negative term to sum.
moreAdditional non-negative terms to add.
Returns
Sum of all arguments as a Dest_.

◆ to_float()

template<typename Float_ , typename Value_ >
Float_ sanisizer::to_float ( Value_ x)

Cast a non-negative integer into a (IEE-754 compliant) floating-point number. This checks that (i) there is no loss of precision and (ii) all integers smaller than the input can also be represented by the specified floating-point type.

This is motivated by the fact that some environments do not have a dedicated integer type (e.g., Javascript). In such cases, array lengths need to be stored as floating-point values. Our checks ensure that both the array length and all valid array indices can be exactly represented in the floating-point type.

Note that the purpose of this function is to preserve precision rather than to avoid undefined behavior. For IEEE-754 floats, very large integers already have a well-defined cast to positive infinity.

Template Parameters
Float_Floating-point type. This should be one of the IEEE-754 binary formats.
Value_Integer type, Bounded or Constant.
Parameters
xNon-negative integer, usually holding some kind of size.
Returns
The value of x as a floating-point number.
Exceptions
std::overflow_errorThrown if Float_ cannot exactly represent all non-negative integers less than or equal to x.