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 Stabilize funnel_shifts (including const) #161015

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)

[JulianKnodt]

I was wondering whether this compiles down to specific intrinsics in LLVM?

I was trying to compute the average of two u8s, which is a carrying add followed by rcr,
When compiling carrying_add with a funnel_shift (see here)

I was hoping it would compile to this

(I saw this thread crystal-lang/crystal#11841, as reference)