Tracking Issue for `saturating_bit_shifts`

[kellerkindt]

Split of bit shifts from #87920 into its own feature, so it can be discussed and stabilized independently.

The feature gate for the issue is #![feature(saturating_bit_shifts)].

See original discussion here: #87920 (comment)

About tracking issues

Tracking issues are used to record the overall progress of implementation.
They are also used as hubs connecting to other relevant issues, e.g., bugs or open design questions.
A tracking issue is however not meant for large scale discussion, questions, or bug reports about a feature.
Instead, open a dedicated issue for the specific matter and add the relevant feature gate label.

Steps

• Implement it Implement saturating_shl and saturating_shr on ints #103441
• Discuss correctness of implementation
• Stabilization PR (see instructions on rustc-dev-guide)

Unresolved Questions

Can anyone confirm that this is the expected behavior for saturating bit shift operations?

Implementation history

[martinthomson]

In looking at this, the range of options presented seem to miss a real option. The draft RFC I've read seems to suggest that shifting a bit off either end of the value produces a value of zero, that is:

assert_eq!(0b1000_0000_u8 << 1, 0_u8);
assert_eq!(1_u8 >> 1, 0_u8);

This makes sense for a right shift, but less so for a left shift.

The typical definition for shifting operations for a << b is $a * 2^b\text{ mod }2^n$ where $n$ is the number of bits in the operand. That is, the usual shift multiplies then truncates. Using that definition, I believe that a saturating left shift would be defined as $\text{min}(a * 2^b, 2^n-1)$. Therefore, you would have:

assert_eq!(0b1000_0000_u8 << 1, u8::MAX);

There are a number of cases where I've needed this specific interpretation. For example, a lot of network protocols rely on left shifts of various sorts, where the shift increases over time. While it might be reasonable to expect calling code to take responsibility for capping values, it is imperative that an overflow doesn't cause the value to suddenly truncate to zero or a much smaller value. It is therefore unsafe to simply run max(a << b, cap), because the shift might have overflowed such that (a << b) < cap. A saturating shift that saturates at uNN::MAX would avoid this problem.

That leads to an implementation as follows:

// Noting that this is not real code because there is no trait for `leading_zeros()` or `MAX`.
// This would probably need to be a macro (ugh).
fn saturating_shl<T: Shl>(a: T, b: u32) -> T {
    if a.leading_zeros() <= b {
        a << b
    } else {
        T::MAX
    }
}

The question of what to do for signed types is a little more difficult to reason about.

You could use the same code for left shift, more or less, casting the signed value to unsigned value, shifting, then casting back. That results in a value of -1 for any overflowing left shift. That would be consistent with a twos-complement representation of the unsigned maximum.

OR, you could view the shift as a multiplication as above and proceed from first principles. That would lead to saturating at iNN::MAX for positive values and iNN::MIN for negative values, as follows:

fn saturating_shl<T: Shl>(a: T, b: u32) -> T {
    if a < 0 {
        if a.leading_ones() < b {
            a << b
        } else {
            T::MIN
        }
    } else {
        if a.leading_zeros() < b {
            a << b
        } else {
            T::MAX
        }
    }
}

(This implementation would also work for unsigned types, so it is the more general form, I guess.)

By either same logic, and accounting for the fact that right shifts for signed values extend the sign bit, that means that a saturating right shift would return -1 for negative operands and 0 otherwise (or (x.signum()-1)/2). The effect is that right shift already saturates, so it doesn't need a special implementation.