Tracking Issue for Integer Funnel Shifts

[sayantn]

Feature gate: #![feature(funnel_shifts)]

This is a tracking issue for implementation of funnel shifts on integers.

Funnel shifts are essentially a generalization of bitwise rotations. a.funnel_shl(b, n) means concatenate a and b (with a in the most significant half), creating an integer twice as wide, shifting this to the left by n (taken modulo the bit size of a and b), shifting in zeros, and finally extract the most significant half of the wide integer as the result.

The functions will panic if n >= T::BITS, and the wrapping versions consider n modulo T::BITS. The unchecked variant doesn't do any checks (as the name suggests), and so is unsafe.

a.wrapping_funnel_shl(a, n) is meant to be exactly equivalent to a.rotate_left(n).

Public API

impl {u8, u16, u32, u64, u128, usize} {
    pub const fn funnel_shl(self, rhs: Self, shift: u32) -> Self;
    pub const fn funnel_shr(self, rhs: Self, shift: u32) -> Self;

    pub const fn wrapping_funnel_shl(self, rhs: Self, shift: u32) -> Self;
    pub const fn wrapping_funnel_shr(self, rhs: Self, shift: u32) -> Self;

    pub const unsafe fn unchecked_funnel_shl(self, rhs: Self, shift: u32) -> Self;
    pub const unsafe fn unchecked_funnel_shr(self, rhs: Self, shift: u32) -> Self;
}

Steps / History

A SIMD version of these intrinsics were added in #142078

• ACP: ACP: add funnel shifts libs-team#642
• Implementation
  • Implement Integer funnel shifts #145690
  • core: Implement unchecked_funnel_{shl,shr} #154153
• Final comment period (FCP)¹
• Stabilization PR

Unresolved Questions

• Should we also provide these functions on signed integer types (akin to rotates)?

Footnotes

1. https://std-dev-guide.rust-lang.org/feature-lifecycle/stabilization.html ↩

[clarfonthey]

Just commenting here since it isn't crucial to the implementation but probably worth keeping in mind for stabilisation, but I think that the way these operations work is subtle enough that it's worth putting extra care into documenting them exactly when they're stabilised as primitive methods. In particular, the fact that a zero-shift left returns the LHS and a zero-shift right returns RHS is not immediately intuitive, even though it makes sense.

Basically, I think that we should definitely have these because they're useful primitives for big-integer operations, but we should try to document these very carefully since there are a lot of subtle decisions made that are not immediately clear to someone using them for the first time.

[purplesyringa]

How ready is this for stabilization? I'd love to use this feature, since LLVM doesn't optimize the fallback implementation well (note test cl, 64), and funnel_sh* would be both an ergonomic win and a performance optimization.

[sayantn]

The implementation itself is incomplete, I have not yet added the wrapping and unchecked versions

[purplesyringa]

Makes sense. May I help with that and try to complete the implementation?

[sayantn]

That would be absolutely great!! Thanks. It is just adding the 2 functions, adding some docs and tests (and probably revise the docs as per @clarfonthey 's suggestions)