Bitwise Rotation of Integers

I think FixedWidthInteger should support bitwise rotation. While the implementation for such rotates is small, there are some non-obvious wrinkles, and there's no guarantee that they'll compile down to rotate instructions in Onone. Ideally they'd be implemented as wrappers over llvm intrinsics.

You can currrently implement rotations as:

extension FixedWidthInteger {
  func rotatedLeft(by n: Int) -> Self {
    let bitPattern = Magnitude(truncatingIfNeeded: self)
    return if n >= 0 {
      Self(truncatingIfNeeded: bitPattern &<< n | bitPattern &>> (.bitWidth &- n))
    } else {
      rotatedRight(by: -n)
    }
  }
  func rotatedRight(by n: Int) -> Self {
    let bitPattern = Magnitude(truncatingIfNeeded: self)
    return if n >= 0 {
      Self(truncatingIfNeeded: bitPattern &>> n | bitPattern &<< (.bitWidth &- n))
    } else {
      rotatedLeft(by: -n)
    }
  }
  mutating func rotateLeft(by n: Int) {
    self = rotatedLeft(by: n)
  }
  mutating func rotateRight(by n: Int) {
    self = rotatedRight(by: n)
  }
}

Note that you need to convert to and from Self.Magnitude to handle signed integers, and use masking shifts to enable optimization down to rotate instructions.

You could also implement these as free functions:

func rotateLeft<T: FixedWidthInteger>(_ n: T, by k: Int) -> T {
  let bitPattern = T.Magnitude(truncatingIfNeeded: n)
  return if k >= 0 {
    T(truncatedIfNeeded: bitPattern &<< k| bitPattern &>> (T.bitWidth &- k))
  } else {
    rotateRight(n, by: -k)
  }
}
func rotateRight<T: FixedWidthInteger>(_n: T, by k: Int) -> T {
  let bitPattern = T.Magnitude(truncatingIfNeeded: n)
  return if k >= 0 {
    T(truncatedIfNeeded: bitPattern &>> k | bitPattern &<< (T.bitWidth &- k))
  } else {
    rotateLeft(n, by: -k)
  }
}

But I'm leaning towards the method versions.

If the methods versions were to be added to the standard library, would they need to be requirements with default implementations to guarantee they're lowered to down to rotate instructions, or could they be implemented purely as extensions?

1 Like

Note that this operation is available on main in Numerics' new IntegerUtilties module, which will be tagged in a release sometime this fall.

Guaranteeing that they are lowered to rotate instructions, even in Onone, doesn't really seem necessary. Rotates tend to be fairly rare in generic contexts, and in concrete contexts we get the codegen that we'd like to have. It would be nice to have, but it's probably not worth adding a new protocol requirement for, which is what you'd likely have to do. LLVM does a good job of recognizing the two-shifts idiom to build a rotate instruction in release builds.

I think adding it to the standard library may also make some sense, as part of a group of lower-level bitwise operations, like bitfield extract and insert.

4 Likes