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?
Maybe a NybblesRandomAccessCollection 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
}
}
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.
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
}
}
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:
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))
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.)
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.
@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 Indexis 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.
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) }
}
}
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.)
I can't understand why this mutates