1

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
2

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
3

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
4

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?

5

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

1 Like
6

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
7

Yep, it generates very reasonable code.

1 Like
8

:thinking::face_with_raised_eyebrow: 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
print("Before swapAt():", String(integer, radix: 16))
integer.nybbles.swapAt(2, 0)
print("===== after swapAt()")
print("After swapAt():", String(integer, radix: 16))
9

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
}
10

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
  }
11

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
12

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
13

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
14

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

4 Likes
15

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] = 0 // integer == 0x120
let nybbles = integer.nybbles
nybbles[1] = 0 // integer == 0x100

instead of

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
16 
var integer: UInt64 = 0x123
integer.nybbles[0] = 0 // integer == 0x120
let nybbles = integer.nybbles
nybbles[1] = 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.)

17

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

var integer = 0xABC
print(integer.nybbles[2])

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?