Pointer-bit binary integer bit counts

[oscbyspro]

All binary integer bit counts fit in a signed machine per protocol. This also means that Shift\<T> could be made to fit in a signed machine word. Larger types are wasteful and may require more complicated validation. Arbitrary shifts are also naturally based on major/minor machine word distances. As such, it might make sense to rework how sizes and shifts are represented in memory. A size model would still need the ability to represent infinity, but it is simple enough to reinterpret negative values as infinite. Perhaps something like the following:

@frozen public struct Count: BitCastable, Comparable {

    @usableFromInline let base: IX

    @inlinable public init(raw source: UX.BitPattern) {
        self.base = IX(raw: source)
    }

    @inlinable public func load(as type: IX.BitPattern.Type) -> IX.BitPattern {
        self.base.load(as: IX.BitPattern.self)
    }

    @inlinable public var isInfinite: Bool {
        Bool(self.base.appendix)
    }

    @inlinable public func natural() -> Optional<IX> {
        if  self.isInfinite {
            return nil

        }   else {
            return self.base
        }
    }

    @inlinable public static func ==(lhs: Self, rhs: Self) -> Bool {
        lhs.base == rhs.base
    }

    @inlinable public static func < (lhs: Self, rhs: Self) -> Bool {
        UX(raw: lhs.base) < UX(raw: rhs.base)
    }
}

Comparisons are important, but I'm not sure I want to include arithmetic. I suspect it's easier to just bit cast relative values.

[oscbyspro]

This would also encode the 0...IX.max-or-infinite invariant in the type system.

[oscbyspro]

Data integer bit counts would still return IX, whereas binary integer bit counts would return Size. With this approach, I could also add BinaryInteger/entropy() without feeling like it's a coincidence hack.

[oscbyspro]

A 1 word size model would be a magnitude, but it would not be an unsigned binary integer because it would have 4 edges.

[oscbyspro]

Hm. It seems like DoubleInt benefits quite a bit from this and some related pointer-bit Shift\<T> changes I'm prototyping. Edit: there are some ergonomic struggles about it, but I suppose I have to make it work given how much better it appears to be.

[oscbyspro]

Hm. I wonder what the best pointer-bit Shift\<T> representation is. I could wrap a signed word, an unsigned word, or I could wrap a Size and try the orders of infinity thingy. Like, an infinite Shift\<T> could represent some value near log2(T.max+1) for some infinite T.

On reason I'm considering the infinity stuff is because of how annoying it is to generically test masking shifts. Arbitrary binary integers don't have those because I considered their masking shifts to be foot guns, but a Size based Shift\<T> might be the closest thing to reasonable arbitrary masking behavior. An infinite Shift\<T> would also let me hoist stuff like inverse() to any binary integer shift.

[oscbyspro]

Alternatively, I could perhaps add a Count associated type to BinaryInteger and make it so all SystemsInteger types accept and return IX/UX values while InfiniInt\<T> uses UXL counts. That way everything is a binary integer (yay!). Arbitrary precision integers are always going to be moderately paced so maybe a future 2-word small-storage is good enough for its purposes.

protocol BinaryInteger {

    associatedtype Count: BinaryInteger

    static var size: Count { get }

    func count(_ bit: Bit) -> Count // etc...
}

protocol SystemsInteger: BinaryInteger where Count == IX {

}

struct Shift<Value> { 

    let distance: Value.Count
}

[oscbyspro]

Hm. IX is good for interoperability but there's also merit in Count: UnsignedInteger overflow semantics.

[oscbyspro]

I suspect the associated type is best. Zzz. The requirement machine is the final boss of every RPG ever.

[oscbyspro]

Hm. I suppose the dilemma is that a common concrete type makes generic code simpler, but an associated type doesn't. Meanwhile, the concrete type is not suited for arithmetic whereas the associated type is.

[oscbyspro]

Another consideration is that an infinite binary integer cannot represent an infinite power of 2. I would like infinite binary integer sizes to follow such bit counting rules, but that seems difficult. I have thought about requiring a binary integer bit-mask instead of a binary integer bit-size (#33), but would make bit counting methods subject to overflow. A dedicated bit count model could interpret the infinite inverse of zero differently, however.

Count: [0, IX.max] or [∞ - IX.max, ∞] where ∞ is log2(UXL.max + 1)

[oscbyspro]

One benefit of the Count approach is the bit counting methods of InfiniInt\<T> can be moved to DataInt\<T>.

[oscbyspro]

Count.infinity is guaranteed to be past the end of every binary integer bit pattern, which might be useful.

[oscbyspro]

Here goes prototype 42 or somesuch. I'm so vexed with the vast solution space.

[oscbyspro]

I haven't written any relevant benchmarks yet, and the following is obviously not the best way of measuring it, but this pointer-bit change makes it so all tests in DoubleIntKitTests complete in 1.5s rather than 6.7s in release mode. It's nice.