# Is there an efficient way to swap 2 nibbles of a UInt64?

I have a `UInt64` value that I want to treat like a 16-element vector of 4-bit values. The only operation I actually need to perform is element swapping.

That is, the bits masked by `0xf << (4 * j)` and the bits masked by `0xf << (4 * k)` need to be swapped with each other, where `j` and `k` are values in `0 ..< 16`. This will be done several times for different values of `j` and `k`.

I can cobble together something rather messy with shifts and masks, but I’m wondering if there’s an elegant / efficient / magical way to do this.

Would I just be way better off extracting the values into a buffer of `UInt8` instead, and repacking them after doing the swaps?

5 Likes

Maybe a `Nybbles` `RandomAccessCollection` would be useful, but a subscript is not too messy I think.

``````public extension BinaryInteger {
/// The nybbles of this integer, from least significant to most.
subscript(nybble index: Self) -> Self {
get { self >> (index * 4) & 0xF }
set {
let index = index * 4
let selfWithEmptyNybble = self & ~(0xF << index)
self = selfWithEmptyNybble | (newValue & 0xF) << index
}
}
``````
``````var nybbles: UInt64 = 0x13579BDF

XCTAssertEqual(
(0...7).map { nybbles[nybble: \$0] } .reversed(),
[1, 3, 5, 7, 9, 0xB, 0xD, 0xF]
)

nybbles[nybble: 4] = 0
XCTAssertEqual(nybbles, 0x13509BDF)
nybbles[nybble: 1] = 0xDADFACE // 🥸
XCTAssertEqual(nybbles, 0x13509BEF)
``````
2 Likes

Unpacking into a buffer of UInt8 doesn't really make this any easier, so I think I would just write out the shifts, something like:

``````extension FixedWidthInteger {
func nibblesSwapped(_ j: Int, _ k: Int) -> Self {
let j = 4*j
let k = 4*k
precondition(j >= 0 && j < bitWidth)
precondition(k >= 0 && k < bitWidth)
let jNibble = self >> j & 0xf
let kNibble = self >> k & 0xf
let cleared = self & ~(0xf << j | 0xf << k)
return cleared | kNibble << j | jNibble << k
}
}
``````

This generates quite simple code when specialized, especially if the indices are constants:

``````func foo(a: UInt64) -> UInt64 {
a.nibblesSwapped(2, 7)
}

output.foo(a: Swift.UInt64) -> Swift.UInt64:
mov     rax, rdi
movabs  rcx, -4026535681 // 0xffff_ffff_0fff_f0ff
and     rcx, rdi         // clear nibbles 2 and 7 of a
mov     rdx, rdi
shr     rdx, 20          // move nibble 7 to 2, garbage elsewhere
and     edx, 3840        // isolate new nibble 2
and     eax, 3840        // isolate new nibble 7
shl     rax, 20          // move new nibble 7 into place
or      rax, rcx         // reassemble
or      rax, rdx
ret
``````

It's possible to do even slightly better, but this is really pretty good for most usage. If you're going to do more than just swaps, then writing nibble accessors seems reasonable to me, and should generate the same code.

7 Likes

What's the reason to extend `FixedWidthInteger` instead of `BinaryInteger`? I tried `extension BinaryInteger` and it works.

What's the purpose of having `BinaryInteger` and `FixedWidthInteger`?

Should be `0 ..< 16`?

It's just less clearly a useful operation on `BinaryInteger`. Nothing prevents you from implementing it, though, as you discovered.

1 Like

Actually, this default `swapAt` from `MutableCollection` might be performant enough.

``````var integer = 0xABC
integer.nybbles.swapAt(2, 1)
XCTAssertEqual(integer, 0xBAC)
``````
``````public extension FixedWidthInteger {
init<Integer>(_ nybbles: Nybbles<Integer>) {
self.init(nybbles.integer)
}

var nybbles: Nybbles<Self> {
get { .init(integer: self) }
set { self = newValue.integer }
}
}

/// The nybbles of an integer, from least significant to most.
public struct Nybbles<Integer: FixedWidthInteger>: Hashable {
fileprivate var integer: Integer
}

// MARK: - MutableCollection
extension Nybbles: MutableCollection {
public typealias Index = Int

public var startIndex: Index { 0 }
public var endIndex: Index { Integer.bitWidth / 4 }

public subscript(index: Index) -> Integer {
get { integer >> (index * 4) & 0xF  }
set {
let index = index * 4
integer &= ~(0xF << index)
integer |= (newValue & 0xF) << index
}
}

public func index(after index: Index) -> Index {
index + 1
}
}
``````
5 Likes

Yep, it generates very reasonable code.

1 Like  I can't understand why this mutates `integer` itself. In trying to figure this out, I see that this `init` is unused:

Edit: ok I see how this work: `FixedWidthInteger.nibbles` is a computed property with a `setter` that store the `newValue.integer` back into the variable itself. I wonder if it's possible to eliminate this shim and directly make `FixedWidthInteger`: `MutableCollection`?

Also, with only `func index(after:)`, does it have to advance index one at a time? Can it be improved to advance index directly? Can it be both `MutableCollection & RandomAccessCollection`, like an Array?

Edit 2: so `func index(after:)` is never call?

``````    public func index(after index: Index) -> Index {
print("+++++++ in \(#function), index =", index)
return index + 1
}
``````

nothing is printed. Is it possibly it's actually calling some other default implementation method to do indexing?

also, I can just add `RandomAccessCollection` without adding anything:

``````extension Nybbles: MutableCollection, RandomAccessCollection {
...
}
``````

compile and run just fine.

My "instrumented copy:
``````public extension FixedWidthInteger {
//    init<Integer>(_ nybbles: Nybbles<Integer>) {
//        print("In \(#function)")
//        self.init(nybbles.integer)
//    }

var nybbles: Nybbles<Self> {
get {
print("in nybbles.get")
return .init(integer: self)
}
set {
print("in nybbles.set")
self = newValue.integer
}
}
}

/// The nybbles of an integer, from least significant to most.
public struct Nybbles<Integer: FixedWidthInteger>: Hashable {
fileprivate var integer: Integer
}

// MARK: - MutableCollection
extension Nybbles: MutableCollection/*, RandomAccessCollection*/ {
public typealias Index = Int

public var startIndex: Index { 0 }
public var endIndex: Index { Integer.bitWidth / 4 }

public subscript(index: Index) -> Integer {
get { integer >> (index * 4) & 0xF  }
set {
let index = index * 4
integer &= ~(0xF << index)
integer |= (newValue & 0xF) << index
}
}

public func index(after index: Index) -> Index {
print("+++++++ in \(#function), index =", index)
return index + 1
}
}

print("creating `var integer`")
var integer = 0xABC
integer.nybbles.swapAt(2, 0)
print("===== after swapAt()")
``````

You could (sort of—you'd have to add it to all the types, not the protocol), but you'd have to pick a single amount of bits to iterate by, and you might not always want that to be 4.

What does that mean?

Yes. I thought you had to manually implement `index(before:)` but I was wrong. (You still need `init()` for `RangeReplaceableCollection` though.)

``````/// All zeros.
public init() {
integer = 0
}
``````

I only see you implement:

``````  public func index(after index: Index) -> Index {
index + 1
}
``````

so I thought it only advance the index sequentially by 1 at a time. So to access the element at position 7, the collection has to call this `index(after:)` 7 times.

But I put a `print` inside the method and there is no print out show up, so this method is not called to do the `swapAt(_:_:)`. It must be using something else to access the element? What does it use to do indexing?

Aha, so it can be this:

``````extension Nybbles: MutableCollection, RandomAccessCollection, RangeReplaceableCollection {
public typealias Index = Int

/// All zeros.
public init() {
integer = 0
}

...
}
``````

So is this enough to make it most efficient to do `swapAt(_:_:)`?

I am guessing due to:

``````public typealias Index = Int
``````

there must be conditional conformance for `MutableCollection, RandomAccessCollection, RangeReplaceableCollection` implemented all the necessary indexing operation for `Index = Int`?

But if this is the case, why need to implement:

``````  public func index(after index: Index) -> Index {
index + 1
}
``````

Do not make this conform to `RangeReplaceableCollection`: `RRC` implies the collection is resizeable, which this is not. It can be `RandomAccessCollection` and `MutableCollection`, but not `RRC`.

The default implementation of `swapAt` is exactly what you think it would be:

``````  @inlinable
public mutating func swapAt(_ i: Index, _ j: Index) {
guard i != j else { return }
let tmp = self[i]
self[i] = self[j]
self[j] = tmp
}
``````

Note that this relies only on `Index.==` and `self.subscript` (both `get` and `set`). There's no need to move the `Index`. This is because an `Index` is the thing you pass to a subscript.

`index(after:)` is required by `Collection`, and it is used to move from one `Index` to the next. The reason you don't need the other methods in your case is because there is special magic for `RandomAccessCollection` in the case that `Index` is `Strideable`, with a `Stride` type of `Int`, and where your `Indices` type is the default. `Int` as an `Index` type meets these guarantees. In fact, in the above code you don't even need `func index(after:)` if you conform to `RandomAccessCollection`. You only need it for the earlier collection types.

5 Likes

Thank you! This explain a lot. I learn a great deal about collection. This is knowledge that I've not seen written down anywhere.

What's I just learned:

• When `Index` is `Strideable` like `Int` here, all the indexing requirements are implemented in `RandomAccessCollection`.
• As you explained, `swapAt(_:_:)` only uses `==` and subscript, that's why `index(after:)` is not called.
• I just realize: Swift subscript is just a computed property that take parameters!
2 Likes

i never thought about it that way, but you are right…

(aside: does anyone know if the compiler treats the owned/guaranteed passing conventions differently between the two?)

1 Like

They have the same defaults: guaranteed or inout self, guaranteed parameters for subscripts, owned newValue.

4 Likes

Close, but subscripts can't be named, so they're uglier than methods and aren't accessible directly as closures. There is no way to get this syntax

``````var integer: UInt64 = 0x123
integer.nybbles = 0 // integer == 0x120
let nybbles = integer.nybbles
nybbles = 0 // integer == 0x100

``````

``````integer[nybble: index] = nybble
// Swift doesn't even have a type to reference the get/set pair.
``````

without a separate subscriptable type, or a hack. I very much wish we had named subscripts but C# never got them implemented either so I don't think people understand the value in them. (More than the closure problem, which properties also have, it's largely about accurate naming. Swift subscripts are like Objective-C methods in that the first parameter has to combine the name of the things you're getting, with their index. When you've got something like `array.elements[index: index]`, it's a win to be able to simplify to `array[index]`, but it doesn't scale.)

We don't even have set-only properties over here, or a way to built-in way to grab a computed property's get/set pair (key paths are still appreciated), so I have zero hope.

``````public extension BinaryInteger {
var nybbles: ValueSubscript<Self, Int, Self> {
mutating get {
.init(
&self,
get: { integer in
{ index in
integer >> (index * 4) & 0xF
}
},
set: { integer, index, newValue in
let index = index * 4
let integerWithEmptyNybble = integer & ~(0xF << index)
integer = integerWithEmptyNybble | (newValue & 0xF) << index
}
)
}
}
}
``````
``````/// An emulation of the missing Swift feature of named subscripts.
/// - Note: Argument labels are not supported.
public struct ValueSubscript<Root, Index, Value> {
public typealias Pointer = UnsafeMutablePointer<Root>
public typealias Get = (Root) -> (Index) -> Value
public typealias Set = (inout Root, Index, Value) -> Void

public var pointer: Pointer
public var get: Get
public var set: Set
}

public extension ValueSubscript {
init(
_ pointer: Pointer,
get: @escaping Get,
set: @escaping Set
) {
self.pointer = pointer
self.get = get
self.set = set
}

subscript(index: Index) -> Value {
get { get(pointer.pointee)(index) }
nonmutating set { set(&pointer.pointee, index, newValue) }
}
}
``````
1 Like
``````var integer: UInt64 = 0x123
integer.nybbles = 0 // integer == 0x120
let nybbles = integer.nybbles
nybbles = 0 // integer == 0x100
``````

You can't do this with methods either. It's true that there's no general way to refer to a subscript without calling one of its accessors, though. (Even in a key path the indexes must be provided.)

What's the difference? It's exactly the same at call site:

``````var integer = 0xABC
print(integer.nybbles)
``````

If I add this to `ValueSubscript`:

``````    func swapAt(_ i: Index, _ j: Index) {
let tmp = self[i]
self[i] = self[j]
self[j] = tmp
}
``````

It's the same as before:

``````integer.nybbles.swapAt(2, 0)
``````

What is this? Can you show before/after sample?