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