Overload Swift's generic masking shifts

[oscbyspro]

So I noticed that my non-power-of-two modulo operation was incorrect. On the road to fixing it, I also discovered that 's generic masking bitshift is also broken for unsigned integers with non-power-of-two bit widths. It fails when the shift is negative and Self is unsigned because it converts the shift using Self(truncatingIfNeeded:). While I can fix the former, I can't do much about the latter. You may file this issue under: masking shifts are dumb.

[oscbyspro]

Here's a solution that should work for all bit widths:

@inlinable public static func &<<=(lhs: inout Self, rhs: some BinaryInteger) {
    lhs.bitshiftLeftUnchecked(by: Self.maskingByBitWidth(rhs))
}

@inlinable public static func &<<(lhs: Self, rhs: some BinaryInteger) -> Self {
    var lhs = lhs; lhs &<<= rhs; return lhs
}

@inlinable public static func &>>=(lhs: inout Self, rhs: some BinaryInteger) {
    lhs.bitshiftRightUnchecked(by: Self.maskingByBitWidth(rhs))
}

@inlinable public static func &>>(lhs: Self, rhs: some BinaryInteger) -> Self {
    var lhs = lhs; lhs &>>= rhs; return lhs
}

/// Returns `other` modulo `Self.bitWidth`.
@inlinable static func maskingByBitWidth<T>(_ other: T) -> Int where T: BinaryInteger {
    //=--------------------------------------=
    if  Self.bitWidth.isPowerOf2 {
        return Int(bitPattern: other._lowWord) & (Self.bitWidth &- 1)
    //=--------------------------------------=
    }   else if Self.bitWidth >= other.bitWidth {
        let minus: Bool = other < (0 as T)
        let divisor   = UInt(bitPattern: Self.bitWidth)
        let magnitude = Magnitude(truncatingIfNeeded: other.magnitude)
        let remainder = Int(bitPattern: magnitude % divisor)
        return Int(bitPattern: minus ? Self.bitWidth - remainder : remainder)
    //=--------------------------------------=
    }   else {
        let minus: Bool = other < (0 as T)
        let divisor   = T.Magnitude(truncatingIfNeeded: Self .bitWidth )
        let magnitude = T.Magnitude(truncatingIfNeeded: other.magnitude)
        let remainder = Int(bitPattern: (magnitude % divisor)._lowWord )
        return Int(bitPattern: minus ? Self.bitWidth - remainder : remainder)
    }
}

[oscbyspro]

Hm, I suppose I may have to overload FixedWidthInteger because overloads on ANKFullWidth would not be available in an opaque context, since the original methods are not customizable (protocol extensions sans requirements). That leaves a hole for generic algorithms written without ANK but used with ANK. It's the best I can do on my end, however.

Note: Using Numberick's double-width model avoids this problem.

[oscbyspro]

I solved the concrete (non-opaque) context in f13acf2.

[oscbyspro]

Hm. It can also modeled as an N x 1 modulo operation of BinaryInteger.Words 🧐

[oscbyspro]

Here's my new and improved solution (which is simpler, faster and stdlib compatible):

• Fix masking shifts by negative multiples of non-power-of-two bit widths #148

extension BinaryInteger {

    /// Returns `self` modulo `self.bitWidth`.
    @inlinable func moduloBitWidth() -> Int where Self: FixedWidthInteger {
        self.moduloBitWidth(of: Self.self)
    }
    
    /// Returns `self` modulo `other.bitWidth`.
    @inlinable func moduloBitWidth(of other: (some FixedWidthInteger).Type) -> Int {
        Int(bitPattern: self.modulo(UInt(bitPattern: other.bitWidth)))
    }
    
    /// Returns `self` modulo `modulus`.
    @inlinable func modulo(_ modulus: UInt) -> UInt {
        //=--------------------------------------=
        if  modulus.isPowerOf2 {
            return self._lowWord & (modulus &- 1)
        }
        //=--------------------------------------=
        let minus = Self.isSigned && self < (0 as Self)
        var residue = (0 as UInt)
        
        for word in self.magnitude.words.reversed() {
            residue = modulus.dividingFullWidth(HL(residue, word)).remainder
        }
        
        return (minus && !residue.isZero) ? (modulus &- residue) : (residue)
    }
}

[oscbyspro]

One problem of overriding FixedWidthInteger's masking bit shift is that the residue must be computed twice. Once to losslessly convert the generic shift argument, and once to perform the masking shift. It would be nice if FixedWidthInteger had a bitshift[Left|Right]Unchecked(by: Int) method.

[oscbyspro]

Hm. I could also override the shift in the context of ANKFixedWidthInteger and blame any faults on the fruit. As mentioned before, I have to draw the line somewhere because you can trivially create a context in which my overload does not exist by writing an algorithm in a file that does not import ANK and then using it in a file that does. This is because the generic masking shifts are not customization points.

[oscbyspro]

The following works, but masking duplicates the operation:

extension FixedWidthInteger {
    
    @_semantics("optimize.sil.specialize.generic.partial.never")
    @_transparent public static func &<<=(lhs: inout Self, rhs: some BinaryInteger) {
        lhs = lhs &<< rhs
    }
    
    @_semantics("optimize.sil.specialize.generic.partial.never")
    @_transparent public static func &<<(lhs: Self, rhs: some BinaryInteger) -> Self {
        lhs &<< Self(_truncatingBits: rhs.modulo(UInt(bitPattern: Self.bitWidth)))
    }
    
    @_semantics("optimize.sil.specialize.generic.partial.never")
    @_transparent public static func &>>=(lhs: inout Self, rhs: some BinaryInteger) {
        lhs = lhs &>> rhs
    }
    
    @_semantics("optimize.sil.specialize.generic.partial.never")
    @_transparent public static func &>>(lhs: Self, rhs: some BinaryInteger) -> Self {
        lhs &>> Self(_truncatingBits: rhs.modulo(UInt(bitPattern: Self.bitWidth)))
    }
}

[oscbyspro]

Hm. Maybe I'll add requirements to ANKFixedWidthInteger and override the methods on ANKFullWidth. That way I don't make any changes to things that currently work, like core integers. In that case, using non-power-of-two bit widths in the context of FixedWidthInteger is basically agreeing to stdlib behavior.