Branch data     Line data    Source code

       1                 :             : // Copyright (c) 2021-2022 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 <climits>
       9                 :             : #include <concepts>
      10                 :             : #include <limits>
      11                 :             : #include <optional>
      12                 :             : #include <type_traits>
      13                 :             : 
      14                 :             : template <class T>
      15                 :   563178094 : [[nodiscard]] bool AdditionOverflow(const T i, const T j) noexcept
      16                 :             : {
      17                 :             :     static_assert(std::is_integral<T>::value, "Integral required.");
      18                 :             :     if constexpr (std::numeric_limits<T>::is_signed) {
      19   [ +  +  +  +  :     9171954 :         return (i > 0 && j > std::numeric_limits<T>::max() - i) ||
                   +  + ]
      20         [ +  + ]:        2860 :                (i < 0 && j < std::numeric_limits<T>::min() - i);
      21                 :             :     }
      22                 :   554006140 :     return std::numeric_limits<T>::max() - i < j;
      23                 :             : }
      24                 :             : 
      25                 :             : template <class T>
      26                 :   563035544 : [[nodiscard]] std::optional<T> CheckedAdd(const T i, const T j) noexcept
      27                 :             : {
      28         [ +  + ]:   563035544 :     if (AdditionOverflow(i, j)) {
      29                 :        1467 :         return std::nullopt;
      30                 :             :     }
      31                 :   563034077 :     return i + j;
      32                 :             : }
      33                 :             : 
      34                 :             : template <class T>
      35                 :    24802928 : [[nodiscard]] T SaturatingAdd(const T i, const T j) noexcept
      36                 :             : {
      37                 :             :     if constexpr (std::numeric_limits<T>::is_signed) {
      38   [ +  +  +  + ]:    24801538 :         if (i > 0 && j > std::numeric_limits<T>::max() - i) {
      39                 :             :             return std::numeric_limits<T>::max();
      40                 :             :         }
      41   [ +  +  +  + ]:     1541139 :         if (i < 0 && j < std::numeric_limits<T>::min() - i) {
      42                 :             :             return std::numeric_limits<T>::min();
      43                 :             :         }
      44                 :             :     } else {
      45         [ +  + ]:        1390 :         if (std::numeric_limits<T>::max() - i < j) {
      46                 :             :             return std::numeric_limits<T>::max();
      47                 :             :         }
      48                 :             :     }
      49                 :    24675923 :     return i + j;
      50                 :             : }
      51                 :             : 
      52                 :             : /**
      53                 :             :  * @brief Left bit shift with overflow checking.
      54                 :             :  * @param input The input value to be left shifted.
      55                 :             :  * @param shift The number of bits to left shift.
      56                 :             :  * @return (input * 2^shift) or nullopt if it would not fit in the return type.
      57                 :             :  */
      58                 :             : template <std::integral T>
      59                 :         792 : constexpr std::optional<T> CheckedLeftShift(T input, unsigned shift) noexcept
      60                 :             : {
      61   [ +  +  +  + ]:         792 :     if (shift == 0 || input == 0) return input;
      62                 :             :     // Avoid undefined c++ behaviour if shift is >= number of bits in T.
      63         [ +  + ]:         298 :     if (shift >= sizeof(T) * CHAR_BIT) return std::nullopt;
      64                 :             :     // If input << shift is too big to fit in T, return nullopt.
      65         [ +  + ]:         146 :     if (input > (std::numeric_limits<T>::max() >> shift)) return std::nullopt;
      66         [ +  + ]:          72 :     if (input < (std::numeric_limits<T>::min() >> shift)) return std::nullopt;
      67                 :          34 :     return input << shift;
      68                 :             : }
      69                 :             : 
      70                 :             : /**
      71                 :             :  * @brief Left bit shift with safe minimum and maximum values.
      72                 :             :  * @param input The input value to be left shifted.
      73                 :             :  * @param shift The number of bits to left shift.
      74                 :             :  * @return (input * 2^shift) clamped to fit between the lowest and highest
      75                 :             :  *         representable values of the type T.
      76                 :             :  */
      77                 :             : template <std::integral T>
      78                 :         396 : constexpr T SaturatingLeftShift(T input, unsigned shift) noexcept
      79                 :             : {
      80         [ +  + ]:         396 :     if (auto result{CheckedLeftShift(input, shift)}) return *result;
      81                 :             :     // If input << shift is too big to fit in T, return biggest positive or negative
      82                 :             :     // number that fits.
      83         [ +  + ]:         101 :     return input < 0 ? std::numeric_limits<T>::min() : std::numeric_limits<T>::max();
      84                 :             : }
      85                 :             : 
      86                 :             : #endif // BITCOIN_UTIL_OVERFLOW_H