Repository: bitcoin/bitcoin
File: src/util/overflow.h (C/C++)

Code before:
 * @param i The input value to be left shifted.
 * @param shift The number of bits to left shift.
 * @return The result of the left shift, or std::nullopt in case of
 *         overflow or negative input value.
 */
template <std::unsigned_integral Output, std::integral Input>
constexpr std::optional<Output> CheckedLeftShift(Input i, unsigned shift) noexcept
{
    if constexpr (std::is_signed_v<Input>) {
        if (i < 0) return std::nullopt;
    }
    if (std::make_unsigned_t<Input>(i) > Output(std::numeric_limits<Output>::max() >> shift)) {
        return std::nullopt;
    }
    return i << shift;
}

/**
 * @brief Left bit shift with safe minimum and maximum values.
 * @param i The input value to be left shifted.
 * @param shift The number of bits to left shift.
 * @return The result of the left shift, with the return value clamped
 *         between zero and the maximum Output value if overflow occurs.
 */
template <std::unsigned_integral Output, std::integral Input>
constexpr Output SaturatingLeftShift(Input i, unsigned shift) noexcept
{
    auto default_value{std::numeric_limits<Output>::max()};
    if constexpr (std::is_signed_v<Input>) {
        if (i < 0) default_value = 0;
    }
    return CheckedLeftShift<Output>(i, shift).value_or(default_value);
}

#endif // BITCOIN_UTIL_OVERFLOW_H


Review comment (bug):
In commit "util: Add integer left shift helpers" (e0a541702def3a4c6cce8e44b6ebe8d608edad4e)

It seems wrong that calling `SaturatingLeftShift` on a negative input can wrap around to 0. The point of saturating operations should be that they don't wrap around, but effectively perform operations with full precision and just clamp the result values. In c++ [left shift](https://en.cppreference.com/w/cpp/language/operator_arithmetic#Bitwise_shift_operators) `i << j` is defined as <em>i * 2<sup>j</sup></em>, so `CheckedLeftShift` and `SaturatingLeftShift` should be able to compute the same thing, but without undefined behavior or wrapping.

It also seems like a footgun that these left shift functions are using different input and output types instead of just using the one type like other functions in this file. Would suggest making new functions more similar to existing functions and writing like:

```c++
template <std::integral T>
constexpr std::optional<T> CheckedLeftShift(T i, unsigned shift) noexcept
{
    if (shift == 0 || i == 0) return i;
    // Avoid undefined c++ behavior if shift is >= number of bits in T.
    if (shift >= sizeof(T) * CHAR_BIT) return std::nullopt;
    // If i << shift is too big to fit in T, return nullopt.
    const auto max{std::numeric_limits<T>::max() >> shift};
    if (i > 0 && i > max) return std::nullopt;
    if (i < 0 && i < -max - 1) return std::nullopt;
    return i << shift;
}

template <std::integral T>
constexpr T SaturatingLeftShift(T i, unsigned shift) noexcept
{
    if (auto result{CheckedLeftShift(i, shift)}) return *result;
    // If i << shift is to big to fit in T, return biggest positive or negative
    // number that fits.
    return i < 0 ? std::numeric_limits<T>::min() : std::numeric_limits<T>::max();
}
```

I didn't test these extensively but did sanity check with:

```c++
    static_assert(SaturatingLeftShift<signed char>(0, 100) ==  0);
    static_assert(SaturatingLeftShift<signed char>(1, 100) ==  127);
    static_assert(SaturatingLeftShift<signed char>(-1, 100) ==  -128);

    static_assert(SaturatingLeftShift<signed char>(3, 2) ==  12);
    static_assert(SaturatingLeftShift<signed char>(-3, 2) ==  -12);

    static_assert(SaturatingLeftShift<signed char>(6, 4) ==  96);
    static_assert(SaturatingLeftShift<signed char>(-6, 4) ==  -96);

    static_assert(SaturatingLeftShift<signed char>(63, 1) ==  126);
    static_assert(SaturatingLeftShift<signed char>(64, 1) ==  127);
    static_assert(SaturatingLeftShift<signed char>(-63, 1) ==  -126);
    static_assert(SaturatingLeftShift<signed char>(-64, 1) ==  -128);
    static_assert(SaturatingLeftShift<signed char>(-65, 1) ==  -128);


    static_assert(SaturatingLeftShift<signed char>(31, 2) ==  124);
    static_assert(SaturatingLeftShift<signed char>(32, 2) ==  127);
    static_assert(SaturatingLeftShift<signed char>(-31, 2) ==  -124);
    static_assert(SaturatingLeftShift<signed char>(-32, 2) ==  -128);
    static_assert(SaturatingLeftShift<signed char>(-33, 2) ==  -128);
```



Code after:
 * @brief Left bit shift with overflow checking.
 * @param input The input value to be left shifted.
 * @param shift The number of bits to left shift.
 * @return (input * 2^shift) or nullopt if it would not fit in the return type.
 */
template <std::integral T>
constexpr std::optional<T> CheckedLeftShift(T input, unsigned shift) noexcept
{
    if (shift == 0 || input == 0) return input;
    // Avoid undefined c++ behaviour if shift is >= number of bits in T.
    if (shift >= sizeof(T) * CHAR_BIT) return std::nullopt;
    // If input << shift is too big to fit in T, return nullopt.
    if (input > (std::numeric_limits<T>::max() >> shift)) return std::nullopt;
    if (input < (std::numeric_limits<T>::min() >> shift)) return std::nullopt;
    return input << shift;
}

/**
 * @brief Left bit shift with safe minimum and maximum values.
 * @param input The input value to be left shifted.
 * @param shift The number of bits to left shift.
 * @return (input * 2^shift) clamped to fit between the lowest and highest
 *         representable values of the type T.
 */
template <std::integral T>
constexpr T SaturatingLeftShift(T input, unsigned shift) noexcept
{
    if (auto result{CheckedLeftShift(input, shift)}) return *result;
    // If input << shift is too big to fit in T, return biggest positive or negative
    // number that fits.
    return input < 0 ? std::numeric_limits<T>::min() : std::numeric_limits<T>::max();
}

#endif // BITCOIN_UTIL_OVERFLOW_H