1 // Copyright (c) 2021-2022 The Limenka developers
2 // Distributed under the MIT software license, see the accompanying
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 5 #ifndef LIMENKA_UTIL_OVERFLOW_H
6 #define LIMENKA_UTIL_OVERFLOW_H
7 8 #include <util/check.h>
9 10 #include <climits>
11 #include <concepts>
12 #include <limits>
13 #include <optional>
14 #include <type_traits>
15 16 template <class T>
17 [[nodiscard]] bool AdditionOverflow(const T i, const T j) noexcept
18 {
19 static_assert(std::is_integral<T>::value, "Integral required.");
20 if constexpr (std::numeric_limits<T>::is_signed) {
21 return (i > 0 && j > std::numeric_limits<T>::max() - i) ||
22 (i < 0 && j < std::numeric_limits<T>::min() - i);
23 }
24 return std::numeric_limits<T>::max() - i < j;
25 }
26 27 template <class T>
28 [[nodiscard]] std::optional<T> CheckedAdd(const T i, const T j) noexcept
29 {
30 if (AdditionOverflow(i, j)) {
31 return std::nullopt;
32 }
33 return i + j;
34 }
35 36 template <class T>
37 [[nodiscard]] T SaturatingAdd(const T i, const T j) noexcept
38 {
39 if constexpr (std::numeric_limits<T>::is_signed) {
40 if (i > 0 && j > std::numeric_limits<T>::max() - i) {
41 return std::numeric_limits<T>::max();
42 }
43 if (i < 0 && j < std::numeric_limits<T>::min() - i) {
44 return std::numeric_limits<T>::min();
45 }
46 } else {
47 if (std::numeric_limits<T>::max() - i < j) {
48 return std::numeric_limits<T>::max();
49 }
50 }
51 return i + j;
52 }
53 54 /**
55 * @brief Integer ceiling division (for non-negative values).
56 *
57 * Computes the smallest integer q such that q * divisor >= dividend.
58 * Both dividend and divisor must be non-negative, and divisor must be non-zero.
59 *
60 * The implementation avoids overflow that can occur with `(dividend + divisor - 1) / divisor`.
61 */
62 template <std::integral Dividend, std::integral Divisor>
63 [[nodiscard]] constexpr auto CeilDiv(const Dividend dividend, const Divisor divisor)
64 {
65 Assert(dividend >= 0 && divisor > 0);
66 return dividend / divisor + (dividend % divisor != 0);
67 }
68 69 /**
70 * @brief Left bit shift with overflow checking.
71 * @param input The input value to be left shifted.
72 * @param shift The number of bits to left shift.
73 * @return (input * 2^shift) or nullopt if it would not fit in the return type.
74 */
75 template <std::integral T>
76 constexpr std::optional<T> CheckedLeftShift(T input, unsigned shift) noexcept
77 {
78 if (shift == 0 || input == 0) return input;
79 // Avoid undefined c++ behaviour if shift is >= number of bits in T.
80 if (shift >= sizeof(T) * CHAR_BIT) return std::nullopt;
81 // If input << shift is too big to fit in T, return nullopt.
82 if (input > (std::numeric_limits<T>::max() >> shift)) return std::nullopt;
83 if (input < (std::numeric_limits<T>::min() >> shift)) return std::nullopt;
84 return input << shift;
85 }
86 87 /**
88 * @brief Left bit shift with safe minimum and maximum values.
89 * @param input The input value to be left shifted.
90 * @param shift The number of bits to left shift.
91 * @return (input * 2^shift) clamped to fit between the lowest and highest
92 * representable values of the type T.
93 */
94 template <std::integral T>
95 constexpr T SaturatingLeftShift(T input, unsigned shift) noexcept
96 {
97 if (auto result{CheckedLeftShift(input, shift)}) return *result;
98 // If input << shift is too big to fit in T, return biggest positive or negative
99 // number that fits.
100 return input < 0 ? std::numeric_limits<T>::min() : std::numeric_limits<T>::max();
101 }
102 103 #endif // LIMENKA_UTIL_OVERFLOW_H
104