1 // Copyright (c) 2021-present The Bitcoin Core 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 BITCOIN_UTIL_OVERFLOW_H
6 #define BITCOIN_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 <std::integral T>
17 [[nodiscard]] bool AdditionOverflow(const T i, const T j) noexcept
18 {
19 if constexpr (std::numeric_limits<T>::is_signed) {
20 return (i > 0 && j > std::numeric_limits<T>::max() - i) ||
21 (i < 0 && j < std::numeric_limits<T>::min() - i);
22 }
23 return std::numeric_limits<T>::max() - i < j;
24 }
25 26 template <class T>
27 [[nodiscard]] std::optional<T> CheckedAdd(const T i, const T j) noexcept
28 {
29 if (AdditionOverflow(i, j)) {
30 return std::nullopt;
31 }
32 return i + j;
33 }
34 35 template <std::unsigned_integral T, std::unsigned_integral U>
36 [[nodiscard]] constexpr bool TrySub(T& i, const U j) noexcept
37 {
38 if (i < T{j}) return false;
39 i -= T{j};
40 return true;
41 }
42 43 template <std::integral T>
44 [[nodiscard]] T SaturatingAdd(const T i, const T j) noexcept
45 {
46 if constexpr (std::numeric_limits<T>::is_signed) {
47 if (i > 0 && j > std::numeric_limits<T>::max() - i) {
48 return std::numeric_limits<T>::max();
49 }
50 if (i < 0 && j < std::numeric_limits<T>::min() - i) {
51 return std::numeric_limits<T>::min();
52 }
53 } else {
54 if (std::numeric_limits<T>::max() - i < j) {
55 return std::numeric_limits<T>::max();
56 }
57 }
58 return i + j;
59 }
60 61 /**
62 * @brief Integer ceiling division (for unsigned values).
63 *
64 * Computes the smallest integer q such that q * divisor >= dividend.
65 * Both dividend and divisor must be unsigned, and divisor must be non-zero.
66 *
67 * The implementation avoids overflow that can occur with `(dividend + divisor - 1) / divisor`.
68 */
69 template <std::unsigned_integral Dividend, std::unsigned_integral Divisor>
70 [[nodiscard]] constexpr auto CeilDiv(const Dividend dividend, const Divisor divisor)
71 {
72 assert(divisor > 0);
73 return dividend / divisor + (dividend % divisor != 0);
74 }
75 76 /**
77 * @brief Left bit shift with overflow checking.
78 * @param input The input value to be left shifted.
79 * @param shift The number of bits to left shift.
80 * @return (input * 2^shift) or nullopt if it would not fit in the return type.
81 */
82 template <std::integral T>
83 constexpr std::optional<T> CheckedLeftShift(T input, unsigned shift) noexcept
84 {
85 if (shift == 0 || input == 0) return input;
86 // Avoid undefined c++ behaviour if shift is >= number of bits in T.
87 if (shift >= sizeof(T) * CHAR_BIT) return std::nullopt;
88 // If input << shift is too big to fit in T, return nullopt.
89 if (input > (std::numeric_limits<T>::max() >> shift)) return std::nullopt;
90 if (input < (std::numeric_limits<T>::min() >> shift)) return std::nullopt;
91 return input << shift;
92 }
93 94 /**
95 * @brief Left bit shift with safe minimum and maximum values.
96 * @param input The input value to be left shifted.
97 * @param shift The number of bits to left shift.
98 * @return (input * 2^shift) clamped to fit between the lowest and highest
99 * representable values of the type T.
100 */
101 template <std::integral T>
102 constexpr T SaturatingLeftShift(T input, unsigned shift) noexcept
103 {
104 if (auto result{CheckedLeftShift(input, shift)}) return *result;
105 // If input << shift is too big to fit in T, return biggest positive or negative
106 // number that fits.
107 return input < 0 ? std::numeric_limits<T>::min() : std::numeric_limits<T>::max();
108 }
109 110 #endif // BITCOIN_UTIL_OVERFLOW_H
111