Add saturating_shl and saturating_shr for ints

[kellerkindt]

Proposal

Problem statement

There is wrapping_shr and wrapping_shl a well as overflowing_shr and oveflowing_shl but no saturating_shl and saturating_shr.

So on the one hand, this is for completion purposes. But I also think this should be implemented before the Saturating type is stabilized ... if the effort is reasonable.

Motivating examples or use cases

I am working on this mostly to get a Saturating type stabilized with more or less feature parity to the Wrapping type.

Solution sketch

Will reopen rust-lang/rust#103441

Alternatives

Doing nothing and stabilize the Saturating type without saturating_shl / saturating_shr.

Links and related work

• wrapping_shr
• wrapping_shl
• overflowing_shr
• oveflowing_shl

What happens now?

This issue is part of the libs-api team API change proposal process. Once this issue is filed the libs-api team will review open proposals as capability becomes available. Current response times do not have a clear estimate, but may be up to several months.

Possible responses

The libs team may respond in various different ways. First, the team will consider the problem (this doesn't require any concrete solution or alternatives to have been proposed):

• We think this problem seems worth solving, and the standard library might be the right place to solve it.
• We think that this probably doesn't belong in the standard library.

Second, if there's a concrete solution:

• We think this specific solution looks roughly right, approved, you or someone else should implement this. (Further review will still happen on the subsequent implementation PR.)
• We're not sure this is the right solution, and the alternatives or other materials don't give us enough information to be sure about that. Here are some questions we have that aren't answered, or rough ideas about alternatives we'd want to see discussed.

[Amanieu]

We discussed this in the libs-api meeting last week and we are open to adding these functions but there were concerns about the lack of a clear motivating example for how these functions could be used. There were also concerns that the exact semantics of saturating shifts aren't clear.

---

With that said, I've spent some time thinking over this and there's only one reasonable definition of a saturating operation: it involves performing the operation with infinite precision and then saturating the result to fit into the destination type. In the case of saturating_shl, the operation is multiplication by 2^shift, and in the case of saturating_shr the operation is division by 2^n and rounding to -infinity (negative numbers saturate to -1, positive numbers to 0).

[Amanieu]

We discussed this in the libs-api meeting today but did not come to a consensus. Some clear use case examples would help.

[kellerkindt]

Hi, thanks for looking into it. The reason for this proposal is to get the Saturating type to somewhere close to feature parity to the Wrapping type before stabilizing it. Both types use their respective integer functions under the hood (like here).

Personally, I only have use cases for the simple arithmetic operations like addition, subtraction and multiplication.

[the8472]

I don't think feature parity is a prerequisite for stabilization. Methods could be added later if someone actually needs them.

[Amanieu]

The main issue with saturating shifts is that it's not clear whether the result is saturated (1u8 << 1000 saturates to 255) or the shift amount (1u8 << 1000 saturates to 0). Perhaps it would help to have separate methods for each case?

[pitaj]

Add an outsider, it's pretty intuitive to me that any "saturating" operation applies to the result, not the operands.

[cuviper]

Add an outsider, it's pretty intuitive to me that any "saturating" operation applies to the result, not the operands.

Do you also think that about checked/overflowing/wrapping shifts? Because all of those apply to the shift amount, not the result. Yes, that's often confusing, but that's what we have nonetheless.

[pitaj]

I see. That's a very good point then. On the one hand, people will often expect the following to be equal:

foo.saturating_mul(2)
foo.saturating_shl(1)

But people will also expect saturating_shl to behave like wrapping_shl and co.

I suppose the reason that wrapping_shl and co behave this way is because a shift right will never overflow, which also applies to saturating_shr.

[CAD97]

I personally think it's more useful for saturating_sh[lr] to be consistent with the other methods and refer to the shift operand saturating instead of the shift result... except that the "mathematically useful" definition wants .sat_shl(BITS) == 0, not .sat_shl(BITS) == .shl(BITS - 1). It doesn't particularly help that the signed .saturating_shr is actually isomorphic to the "mathematically useful" version...

This is one of those cases where the Saturating type is most useful, actually, to disambiguate between whether Saturating(n) << m (if bits would be shifted out, produce MAX), n << Saturating(m) (if shift amount would overflow, shift by BITS - 1 instead), or n.checked_shl(m).unwrap_or(0) is actually the desired semantics.

Keep in mind that even overflowing_sh[lr] refers to overflowing the shift value, not whether bits are shifted out of the result value. (Given a time machine, I'd remove the Wrapping(n) << m impl of n.wrapping_shl(m); it's applying wrapping semantics to the wrong value!)

.saturating.sh[lr] (with shift amount saturates semantics) probably deserve to exist, but like .wrapping_sh[lr] have a note that you might want .rotate_{left|right} instead, they would need a note explaining what exactly the saturating semantics are, as well as how to get the other potentially desired semantics.

(Did Euclid happen to discuss ring arithmetic shifts, so we can justify calling the "mathematically useful" version .sh[lr]_euclid (half-joking)? In analogy to {div|rem}_euclid being the "mathematically useful" definition.)

semantics	impl
shift checking	if m < BITS { Some(n << m) } else { None }
shift wrapping	n << m.rem_euclid(BITS)
shift saturating	n << m.clamp(0, BITS - 1)
result checking	if m < n.leading_zeros() { Some(n << m) } else { None }
result wrapping	n.rotate_left(m.rem_euclid(BITS))
result saturating	if m < n.leading_zeros() { n << m } else { -1 as _ }
signed result saturating	if m < n.trailing_zeros() { n >> m } else if n < 0 { -1 } else { 0 }
result truncating	if m < BITS { n << m } else { 0 }
signed result truncating1	if m < BITS { n >> m } else if n < 0 { -1 } else { 0 }

Footnotes

1. I'm defining "result truncating" as doing the operation in infinite precision and then truncating to the bits that fit in the output range. This works unambiguously for unsigned types, but doesn't quite work perfectly for signed types. If there's a good definition of shl for signed ints that doesn't rely on doing the operation in unsigned space, though, I don't know it. ↩

[scottmcm]

I think the current definitions of shifts were a mistake, in retrospect. Picking the "this is efficient on x86" definition over the "this makes sense" definition is usually not what Rust does for the default.

But saturating_sh[lr] ought -- if it exists -- to be consistent with wrapping_sh[lr] and checked_sh[lr] and overflowing_sh[lr], because doing anything else is more confusing.

---

Drastic idea: What if we did an edition change?

We could add new ShiftLeft/ShiftRight traits, and use those in the new edition. They'd use the ">> n is the same as doing >> 1 n times" definition, and there's manual masking or unchecked_shl for people who really need something faster than that. (Maybe only take unsigned RHSs too.)

Or just add .shift_left(u32)+.shift_right(u32) methods that do the logical thing, and encourage those instead.

[programmerjake]

semantics impl
shift checking if m < BITS { Some(n << m) } else { None }
shift wrapping n << m.rem_euclid(BITS)
shift saturating n << m.clamp(0, BITS - 1)
result checking if m < n.leading_zeros() { Some(n << m) } else { None }
result wrapping n.rotate_left(m.rem_euclid(BITS))

that's not what's generally accepted to be wrapping-result. rotate is basically never a substitute for shifting. wrapping generally means the value is computed to infinite precision and then reduced mod 2BITS, with signed results computing the mod operation to provide balanced results rather than strictly positive. this is equivalent to shifting then extracting the lower BITS-bits, so shift amounts as big or bigger than BITS always return 0.

result saturating if m < n.leading_zeros() { n << m } else { -1 as _ }

this is wrong because: 0 << anything == 0

1. I'm defining "result truncating" as doing the operation in infinite precision and then truncating to the bits that fit in the output range. This works unambiguously for unsigned types, but doesn't quite work perfectly for signed types. If there's a good definition of shl for signed ints that doesn't rely on doing the operation in unsigned space, though, I don't know it. ↩

there is, it's the definition i gave for wrapping result

[boomshroom]

The current "wrapping" shift behavior is unintuitive. Every other wrapping or saturating operator applies to the result rather than the inputs, which is important for modular arithmetic. Shift is the only one that applies the rules to the inputs.

Personally, I'd expect either 255_u8.wrapping_shl(8) or 255_u8.saturating_shl(8) to equal 0, but I'm not sure which would be a better candidate. Given how saturating normally works, any positive number would probably give the greatest positive value on overflow, any negative number would give the the minimal signed value, and 0 would always give 0. For right shifting, I have a "saturating_shr" on signed integers defined as self >> (shift.min(N - 1)). I've also found use for a "bidirectional shift" where a negative result shifts the opposite direction. Saturating the operand only makes sense for signed right-shifts since that would properly copy the sign bit across the whole register giving 0 if positive and -1 if negative.

Ultimately, x >> y should be equivalent to x / (2.pow(y)) (though not really because x / y is broken and it's really x.div_euclid(2.pow(y))), and x << y equivalent to x.wrapping_mul(2.pow(y)). There is the convenience where even if 2.pow(-y) isn't representable, -y and x * 2.pow(-y) are, which enables the concept of a "bi-directional shift", though from my observations, such a shift can be very slow.

Also like division, there's also x.rem_euclid(2.pow(y)) which should be representable more cheaply as x & ((1 << y) - 1), though this doesn't work if the shift is out of range or if y is negative.

So a full wrapping euclidean div_mod of x by 2^y would be

fn shift_mask(x: i32, y: i32) -> (i32, i32) {
    match y {
        ..=-32 => (0, 0),
        -31..=-1 => (x << -y, 0),
        0 => (x, 0),
        1..=31 => (x >> y, x & (1 << y).wrapping_sub(1)),
        32.. => (x >> 31, x),
    }
}

Without including versions that return a wider type than the inputs, this seems to be the most mathematically useful form of shifting, but also seems to be fairly slow. Unless the efficiency was a deal-breaker, the behavior of the two halves of this function would be useful to have available, either in bi-directional form with a signed shift or in uni-directional form with an unsigned shift.

[EDIT] While phrased in mathematical language, these functions are particularly useful extracting signed bitfields, with the bidirectional one being for when the bitfields can have variable length.

[joshtriplett]

We took another run at this 🚴 bikeshed in today's libs-api meeting, and the existence of unbounded_shl/unbounded_shr came up. Given the existence of the unbounded methods, we're happy to approve the saturating methods with the proposed semantic of saturating the value.