Feb 20, 2018
Adding Packed-Boolean Initializers
Now I’ll implement the Sequence-of-arbitrary-words initializer I threatened to make in Part 2.
Although BitArray internally uses a [UInt] for its storage of packed bits, I do not want to enforce that in the public-facing initializer. The user should be able to use any UnsignedInteger type to contain their packed Booleans; I’ll do any repartitioning between their type and UInt during conversion.
Converting a Sequence of words is the same a converting each word separately, then stitching those results together. So let’s start with an initializer to convert single words:
extension BitArray { public init<W: UnsignedInteger>(word: W, bitCount: Int, bitIterationDirection: EndianTraversal) {
precondition(0...word.bitWidth ~= bitCount) let coreWords: WordArray
switch bitIterationDirection {
case .lo2hi:
coreWords = WordArray(word.words)
case .hi2lo:
let (wbwq, wbwr) = word.bitWidth.quotientAndRemainder(dividingBy: Word.bitWidth)
let wordWords = WordArray(word.words)
assert(wbwq + wbwr.signum() == wordWords.count)
let highOrderWordBitCount = wbwr != 0 ? wbwr : wbwq.signum() * Word.bitWidth
let head = BitArray(coreWords: [wordWords.last! << (Word.bitWidth - highOrderWordBitCount)], bitCount: highOrderWordBitCount, bitIterationDirection: .hi2lo)
var tail = BitArray(coreWords: wordWords.dropLast().reversed(), bitCount: Word.bitWidth * (wordWords.count - 1), bitIterationDirection: .hi2lo)
tail.prependHead(head)
coreWords = tail.bits
}
self.init(coreWords: coreWords, bitCount: bitCount, bitIterationDirection: bitIterationDirection)
} //...}
The key is that every BinaryInteger-conforming object, which includes those that conform to UnsignedInteger, must provide an accessor to its binary value. This accessor is an instance-level property named words that is a Sequence of UInt, but secretly must be a Collection instead. The returned words must be from lowest-order to highest, with the bits within going in the same priority.
This format is already near perfect for my needs. It definitely is when the initializer needs to read from the lowest-order bits up. When reading in the other direction, I need to take into account that the highest-order word may not use all of its bits. I handle that by reading that highest-order word and the other words in separate passes then stitch the results together. After collecting the bits in my format, I pass them to my master initializer.
The Sequence-of-arbitrary-words initializer just composes from work I’ve already done and the Standard Library:
{ //... public init<S>(words: S, bitCount: Int, bitIterationDirection: EndianTraversal) where S: Sequence, S.Element: UnsignedInteger {
let bitArraySlivers = words.map { BitArray(word: $0, bitCount: $0.bitWidth, bitIterationDirection: bitIterationDirection) }
var scratch = BitArray(coreWords: [], bitCount: 0, bitIterationDirection: bitIterationDirection)
for s in bitArraySlivers.reversed() {
scratch.prependHead(s)
}
self = scratch.head(bitCount: bitCount)
}}
The big gap between this post and the previous part was because of testing. To fully test the single-word initializer, one of the source types needed to be larger than UInt. I had to make my own, and I got distracted by fully implementing the arithmetic operations. But I don’t need them here; only words needs to be fully functional and everything else can be a stub. I did find a bug while creating said stub, so it wasn’t a complete waste of time:
// An unsigned integer type bigger than any of the standard ones.
struct UInt72: FixedWidthInteger, UnsignedInteger {
// Implementation properties
var high: UInt8
var low: UInt64 // Main initializer
init(highOrderBits hi: UInt8, lowOrderBits lo: UInt64) { (high, low) = (hi, lo) } // FixedWidthInteger secret initializer
init(_truncatingBits bits: UInt) { self.init(highOrderBits: 0, lowOrderBits: UInt64(bits)) } // FixedWidthInteger properties
var byteSwapped: UInt72 {
return UInt72(highOrderBits: UInt8(truncatingIfNeeded: low), lowOrderBits: (low.byteSwapped << 8) | UInt64(high))
}
var leadingZeroBitCount: Int { return high != 0 ? high.leadingZeroBitCount : 8 + low.leadingZeroBitCount }
var nonzeroBitCount: Int { return high.nonzeroBitCount + low.nonzeroBitCount } static var bitWidth: Int { return 72 } // BinaryInteger properties
var trailingZeroBitCount: Int { return low != 0 ? low.trailingZeroBitCount : high.trailingZeroBitCount + 64 }
var words: [UInt] { return Array(low.words) + high.words } // ExpressibleByIntegerLiteral and Hashable support
init(integerLiteral value: UInt) { self.init(_truncatingBits: value) } var hashValue: Int { return String(describing: self).hashValue } // BinaryInteger floating-point initializer
init<T>(_ source: T) where T : BinaryFloatingPoint { fatalError("\(#function) not implemented") } // FixedWidthInteger core math
func addingReportingOverflow(_ rhs: UInt72) -> (partialValue: UInt72, overflow: Bool) {
fatalError("\(#function) not implemented")
}
func dividedReportingOverflow(by rhs: UInt72) -> (partialValue: UInt72, overflow: Bool) {
fatalError("\(#function) not implemented")
}
func dividingFullWidth(_ dividend: (high: UInt72, low: UInt72)) -> (quotient: UInt72, remainder: UInt72) {
fatalError("\(#function) not implemented")
}
func multipliedReportingOverflow(by rhs: UInt72) -> (partialValue: UInt72, overflow: Bool) {
fatalError("\(#function) not implemented")
}
func multipliedFullWidth(by other: UInt72) -> (high: UInt72, low: UInt72) {
fatalError("\(#function) not implemented")
}
func remainderReportingOverflow(dividingBy rhs: UInt72) -> (partialValue: UInt72, overflow: Bool) {
fatalError("\(#function) not implemented")
}
func subtractingReportingOverflow(_ rhs: UInt72) -> (partialValue: UInt72, overflow: Bool) {
fatalError("\(#function) not implemented")
} // BinaryInteger operators
static func %(lhs: UInt72, rhs: UInt72) -> UInt72 {
let results = lhs.remainderReportingOverflow(dividingBy: rhs)
assert(!results.overflow)
return results.partialValue
}
static func *(lhs: UInt72, rhs: UInt72) -> UInt72 {
let results = lhs.multipliedReportingOverflow(by: rhs)
assert(!results.overflow)
return results.partialValue
}
static func +(lhs: UInt72, rhs: UInt72) -> UInt72 {
let results = lhs.addingReportingOverflow(rhs)
assert(!results.overflow)
return results.partialValue
}
static func -(lhs: UInt72, rhs: UInt72) -> UInt72 {
let results = lhs.subtractingReportingOverflow(rhs)
assert(!results.overflow)
return results.partialValue
}
static func /(lhs: UInt72, rhs: UInt72) -> UInt72 {
let results = lhs.dividedReportingOverflow(by: rhs)
assert(!results.overflow)
return results.partialValue
} static func %=(lhs: inout UInt72, rhs: UInt72) { lhs = lhs % rhs }
static func *=(lhs: inout UInt72, rhs: UInt72) { lhs = lhs * rhs }
static func +=(lhs: inout UInt72, rhs: UInt72) { lhs = lhs + rhs }
static func -=(lhs: inout UInt72, rhs: UInt72) { lhs = lhs - rhs }
static func /=(lhs: inout UInt72, rhs: UInt72) { lhs = lhs / rhs }
}
A future update to Swift may require me to add the missing bit-twiddling operators.
