stdlib/public/core/DoubleWidth.swift.gyb - third_party/swift - Git at Google

 //===--- DoubleWidth.swift.gyb --------------------------------*- swift -*-===//
 //
 // This source file is part of the Swift.org open source project
 //
 // Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
 // Licensed under Apache License v2.0 with Runtime Library Exception
 //
 // See https://swift.org/LICENSE.txt for license information
 // See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
 //
 //===----------------------------------------------------------------------===//

 /// A fixed-width integer that is twice the size of its base type.
 @_fixed_layout // FIXME(sil-serialize-all)
 public struct DoubleWidth<Base : FixedWidthInteger> : _ExpressibleByBuiltinIntegerLiteral
   where Base.Words : Collection, Base.Magnitude.Words : Collection {

   public typealias High = Base
   public typealias Low = Base.Magnitude

   @_versioned // FIXME(sil-serialize-all)
   internal var _storage: (high: Base, low: Base.Magnitude)

   @_inlineable // FIXME(sil-serialize-all)
   public var high: High {
     return _storage.high
   }

   @_inlineable // FIXME(sil-serialize-all)
   public var low: Low {
     return _storage.low
   }

   @_inlineable // FIXME(sil-serialize-all)
   public // @testable
   init(_ _value: (High, Low)) {
     self._storage = (high: _value.0, low: _value.1)
   }

   @_inlineable // FIXME(sil-serialize-all)
   public init() {
     self.init((0, 0))
   }
 }

 extension DoubleWidth: Comparable {
   @_inlineable // FIXME(sil-serialize-all)
   public static func ==(lhs: DoubleWidth, rhs: DoubleWidth) -> Bool {
     return (lhs._storage.high == rhs._storage.high) &&
       (lhs._storage.low == rhs._storage.low)
   }

   @_inlineable // FIXME(sil-serialize-all)
   public static func <(lhs: DoubleWidth, rhs: DoubleWidth) -> Bool {
     if lhs._storage.high < rhs._storage.high {
       return true
     }
     if lhs._storage.high > rhs._storage.high {
       return false
     }
     return lhs._storage.low < rhs._storage.low
   }
 }


 extension DoubleWidth: Numeric {
   public typealias Magnitude = DoubleWidth<Low>

   @_inlineable // FIXME(sil-serialize-all)
   public var magnitude: DoubleWidth<Low> {
     if Base.isSigned && _storage.high < (0 as High) {
       return self == .min
         ? DoubleWidth.max.magnitude &+ 1
         : (0 - self).magnitude
     }
     return DoubleWidth<Low>((
       _storage.high.magnitude, _storage.low.magnitude))
   }

   @_inlineable // FIXME(sil-serialize-all)
   @_versioned // FIXME(sil-serialize-all)
   internal init(_ _magnitude: Magnitude) {
     self.init((High(_magnitude._storage.high), _magnitude._storage.low))
   }

   @_inlineable // FIXME(sil-serialize-all)
   public init<T : BinaryInteger>(_ source: T) {
     guard let result = DoubleWidth<Base>(exactly: source) else {
       _preconditionFailure("Value is outside the representable range")
     }
     self = result
   }

   @_inlineable // FIXME(sil-serialize-all)
   public init?<T : BinaryInteger>(exactly source: T) {
     // Can't represent a negative 'source' if Base is unsigned
     guard source >= 0 || DoubleWidth.isSigned else { return nil }

     // Is 'source' is entirely representable in Low?
     if let low = Low(exactly: source.magnitude) {
       if source < (0 as T) {
         self.init((~0, ~low + 1))
       } else {
         self.init((0, low))
       }
     } else {
       // At this point we know source's bitWidth > Base.bitWidth, or else
       // we would've taken the first branch.
       let lowInT = source & T(~0 as Low)
       let highInT = source >> High.bitWidth

       let low = Low(lowInT.magnitude)
       guard let high = High(exactly: highInT) else { return nil }
       self.init((high, low))
     }
   }
 }

 extension DoubleWidth {
   @_inlineable // FIXME(sil-serialize-all)
   public init<T : BinaryFloatingPoint>(_ source: T) {
     fatalError()
   }

   @_inlineable // FIXME(sil-serialize-all)
   public init?<T : BinaryFloatingPoint>(exactly source: T) {
     fatalError()
   }

   @_inlineable // FIXME(sil-serialize-all)
   public init<T : BinaryFloatingPoint>(_ source: T)
     where T.RawSignificand : FixedWidthInteger
   {
     _precondition(source.isFinite, "Can't create a DoubleWidth from a non-finite value")
     self.init(exactly: source.rounded(.towardZero))!
   }

   @_inlineable // FIXME(sil-serialize-all)
   public init?<T : BinaryFloatingPoint>(exactly source: T)
     where T.RawSignificand : FixedWidthInteger
   {
     // Need a finite value
     guard source.isFinite else { return nil }

     // Don't need to go further with zero.
     if source.isZero {
       self.init(0)
       return
     }

     // Need a value with a non-negative exponent
     guard source.exponent >= 0 else { return nil }

     typealias Raw = T.RawSignificand
     let bitPattern = source.significandBitPattern |
       ((1 as Raw) &<< Raw(T.significandBitCount))
     let offset = T.significandBitCount - Int(source.exponent)

     // FIXME: spurious compile error when 'where' clause above is removed:
     // error: non-nominal type 'T.RawSignificand' does not support explicit initialization
     let fractionPart: Raw = bitPattern &<< Raw(Raw.bitWidth - offset)
     guard fractionPart == (0 as Raw) else {
       return nil
     }

     let integerPart: Raw = bitPattern &>> Raw(offset)

     // Should have caught any actual zero values above
     _sanityCheck(integerPart > (0 as Raw))

     if source.sign == .minus {
       if !DoubleWidth.isSigned || integerPart &- 1 > DoubleWidth.max {
         return nil
       }
       // Have to juggle, or else the intermediate step of creating a value
       // with Self.min's magnitude will overflow. It's okay to use wrapping
       // subtraction because integerPart > 0.
       self.init(integerPart &- 1)
       self = 0 &- self &- 1
     } else {
       self.init(exactly: integerPart)
     }
   }
 }

 extension DoubleWidth: FixedWidthInteger {
   @_fixed_layout // FIXME(sil-serialize-all)
   public struct Words : Collection {
     public enum _IndexValue {
       case low(Base.Magnitude.Words.Index)
       case high(Base.Words.Index)
     }

     @_fixed_layout // FIXME(sil-serialize-all)
     public struct Index : Comparable {
       public var _value: _IndexValue

       @_inlineable // FIXME(sil-serialize-all)
       public init(_ _value: _IndexValue) { self._value = _value }

       @_inlineable // FIXME(sil-serialize-all)
       public static func ==(lhs: Index, rhs: Index) -> Bool {
         switch (lhs._value, rhs._value) {
         case let (.low(l), .low(r)): return l == r
         case let (.high(l), .high(r)): return l == r
         default: return false
         }
       }

       @_inlineable // FIXME(sil-serialize-all)
       public static func <(lhs: Index, rhs: Index) -> Bool {
         switch (lhs._value, rhs._value) {
         case let (.low(l), .low(r)): return l < r
         case (.low(_), .high(_)): return true
         case (.high(_), .low(_)): return false
         case let (.high(l), .high(r)): return l < r
         }
       }
     }

     public var _high: Base.Words
     public var _low: Base.Magnitude.Words

     @_inlineable // FIXME(sil-serialize-all)
     public init(_ value: DoubleWidth<Base>) {
       // multiples of word-size only
       guard Base.bitWidth == Base.Magnitude.bitWidth &&
         (UInt.bitWidth % Base.bitWidth == 0 ||
         Base.bitWidth % UInt.bitWidth == 0) else {
         fatalError("Access to words is not supported on this type")
       }
       self._high = value._storage.high.words
       self._low = value._storage.low.words
       _sanityCheck(!_low.isEmpty)
     }

     @_inlineable // FIXME(sil-serialize-all)
     public var startIndex: Index {
       return Index(.low(_low.startIndex))
     }

     @_inlineable // FIXME(sil-serialize-all)
     public var endIndex: Index {
       return Index(.high(_high.endIndex))
     }

     @_inlineable // FIXME(sil-serialize-all)
     public var count: Int {
       if Base.bitWidth < UInt.bitWidth { return 1 }
       return Int(_low.count) + Int(_high.count)
     }

     @_inlineable // FIXME(sil-serialize-all)
     public func index(after i: Index) -> Index {
       switch i._value {
       case let .low(li):
         if Base.bitWidth < UInt.bitWidth {
           return Index(.high(_high.endIndex))
         }
         let next = _low.index(after: li)
         if next == _low.endIndex {
           return Index(.high(_high.startIndex))
         }
         return Index(.low(next))
       case let .high(hi):
         return Index(.high(_high.index(after: hi)))
       }
     }

     @_inlineable // FIXME(sil-serialize-all)
     public subscript(_ i: Index) -> UInt {
       if Base.bitWidth < UInt.bitWidth {
         _precondition(i == Index(.low(_low.startIndex)), "Invalid index")
         _sanityCheck(2 * Base.bitWidth <= UInt.bitWidth)
         return _low.first! | (_high.first! &<< Base.bitWidth._lowWord)
       }
       switch i._value {
       case let .low(li): return _low[li]
       case let .high(hi): return _high[hi]
       }
     }
   }

   @_inlineable // FIXME(sil-serialize-all)
   public var words: Words {
     return Words(self)
   }

   @_inlineable // FIXME(sil-serialize-all)
   public static var isSigned: Bool {
     return Base.isSigned
   }

   // fixed width
   //
   @_inlineable // FIXME(sil-serialize-all)
   public static var max: DoubleWidth {
     return self.init((High.max, Low.max))
   }

   @_inlineable // FIXME(sil-serialize-all)
   public static var min: DoubleWidth {
     return self.init((High.min, Low.min))
   }

   @_inlineable // FIXME(sil-serialize-all)
   public static var bitWidth: Int {
     return 2 * Base.bitWidth
   }

 % for (operator, name) in [('+', 'adding'), ('-', 'subtracting')]:
 %   highAffectedByLowOverflow = 'Base.max' if operator == '+' else 'Base.min'
   @_inlineable // FIXME(sil-serialize-all)
   public func ${name}ReportingOverflow(_ rhs: DoubleWidth)
     -> (partialValue: DoubleWidth, overflow: Bool) {
     let (low, lowOverflow) =
       _storage.low.${name}ReportingOverflow(rhs._storage.low)
     let (high, highOverflow) =
       _storage.high.${name}ReportingOverflow(rhs._storage.high)
     let result = (high &${operator} (lowOverflow ? 1 : 0), low)
     let overflow = highOverflow ||
       high == ${highAffectedByLowOverflow} && lowOverflow
     return (partialValue: DoubleWidth(result), overflow: overflow)
   }
 % end

   @_inlineable // FIXME(sil-serialize-all)
   public func multipliedReportingOverflow(
     by rhs: DoubleWidth
   ) -> (partialValue: DoubleWidth, overflow: Bool) {
     let (carry, product) = multipliedFullWidth(by: rhs)
     let result = DoubleWidth(truncatingIfNeeded: product)

     let isNegative = (self < (0 as DoubleWidth)) != (rhs < (0 as DoubleWidth))
     let didCarry = isNegative
       ? carry != ~(0 as DoubleWidth)
       : carry != (0 as DoubleWidth)
     let hadPositiveOverflow = !isNegative &&
       DoubleWidth.isSigned && product.leadingZeroBitCount == 0

     return (result, didCarry || hadPositiveOverflow)
   }

   // Specialize for the most popular types.
   @_specialize(where Base == Int)
   @_specialize(where Base == UInt)
   @_specialize(where Base == Int64)
   @_specialize(where Base == UInt64)
   @_inlineable // FIXME(sil-serialize-all)
   public func quotientAndRemainder(dividingBy other: DoubleWidth)
     -> (quotient: DoubleWidth, remainder: DoubleWidth) {
     let isNegative = (self < (0 as DoubleWidth)) != (other < (0 as DoubleWidth))

     let rhs = other.magnitude
     var q = self.magnitude

     // Bail if |other| > |self|
     if rhs.leadingZeroBitCount < q.leadingZeroBitCount {
       return (0, self)
     }

     // Calculate the number of bits before q and rhs line up,
     // we can skip that many bits of iteration.
     let initialOffset = q.leadingZeroBitCount +
       (DoubleWidth.bitWidth - rhs.leadingZeroBitCount) - 1

     // Start with remainder capturing the high bits of q.
     // (These need to be smart shifts, as initialOffset can be > q.bitWidth)
     var r = q >> Magnitude(DoubleWidth.bitWidth - initialOffset)
     q <<= Magnitude(initialOffset)

     let highBit = ~(~0 >> 1) as Magnitude
     for _ in initialOffset..<DoubleWidth.bitWidth {
       r <<= 1
       if q & highBit != (0 as Magnitude) {
         r += 1 as Magnitude
       }
       q <<= 1

       if r >= rhs {
         q |= 1
         r -= rhs
       }
     }

     // Sign of remainder matches dividend
     let remainder = self < (0 as DoubleWidth)
       ? 0 - DoubleWidth(r)
       : DoubleWidth(r)

     if isNegative {
       return (0 - DoubleWidth(q), remainder)
     } else {
       return (DoubleWidth(q), remainder)
     }
   }

   @_inlineable // FIXME(sil-serialize-all)
   public func dividedReportingOverflow(by other: DoubleWidth)
     -> (partialValue: DoubleWidth, overflow: Bool) {
     if other == (0 as DoubleWidth) ||
       (DoubleWidth.isSigned && other == (-1 as Int) && self == .min)
     {
       return (self, true)
     }

     return (quotientAndRemainder(dividingBy: other).quotient, false)
   }

   @_inlineable // FIXME(sil-serialize-all)
   public func remainderReportingOverflow(dividingBy other: DoubleWidth)
     -> (partialValue: DoubleWidth, overflow: Bool) {
     if other == 0 ||
       (DoubleWidth.isSigned && other == -1 && self == .min)
     {
       return (self, true)
     }

     return (quotientAndRemainder(dividingBy: other).remainder, false)
   }

   @_inlineable // FIXME(sil-serialize-all)
   public func multipliedFullWidth(by other: DoubleWidth)
     -> (high: DoubleWidth, low: DoubleWidth.Magnitude) {
     let isNegative = DoubleWidth.isSigned &&
       (self < (0 as DoubleWidth)) != (other < (0 as DoubleWidth))

     func mul(_ x: Low, _ y: Low) -> (partial: Low, carry: Low) {
       let (high, low) = x.multipliedFullWidth(by: y)
       return (low, high)
     }

     func sum(_ x: Low, _ y: Low, _ z: Low) -> (partial: Low, carry: Low) {
       let (sum1, overflow1) = x.addingReportingOverflow(y)
       let (sum2, overflow2) = sum1.addingReportingOverflow(z)
       let carry: Low = (overflow1 ? 1 : 0) + (overflow2 ? 1 : 0)
       return (sum2, carry)
     }

     let lhs = self.magnitude
     let rhs = other.magnitude

     let a = mul(rhs._storage.low, lhs._storage.low)
     let b = mul(rhs._storage.low, lhs._storage.high)
     let c = mul(rhs._storage.high, lhs._storage.low)
     let d = mul(rhs._storage.high, lhs._storage.high)

     let mid1 = sum(a.carry, b.partial, c.partial)
     let mid2 = sum(b.carry, c.carry, d.partial)

     let low = DoubleWidth<Low>((mid1.partial, a.partial))
     let high = DoubleWidth((
       High(mid2.carry + d.carry), mid1.carry + mid2.partial
     ))

     if isNegative {
       let (lowComplement, overflow) = (~low).addingReportingOverflow(1)
       return (~high + (overflow ? 1 : 0), lowComplement)
     } else {
       return (high, low)
     }
   }

   @_inlineable // FIXME(sil-serialize-all)
   public func dividingFullWidth(
     _ dividend: (high: DoubleWidth, low: DoubleWidth.Magnitude)
   ) -> (quotient: DoubleWidth, remainder: DoubleWidth) {
     let lhs = DoubleWidth<DoubleWidth<Base>>(dividend)
     let rhs = DoubleWidth<DoubleWidth<Base>>(self)
     let (quotient, remainder) = lhs.quotientAndRemainder(dividingBy: rhs)

     // FIXME(integers): check for overflow of quotient and remainder
     return (DoubleWidth(quotient.low), DoubleWidth(remainder.low))
   }

 % for operator in ['&', '|', '^']:
   @_inlineable // FIXME(sil-serialize-all)
   public static func ${operator}=(
     lhs: inout DoubleWidth, rhs: DoubleWidth
   ) {
     lhs._storage.low ${operator}= rhs._storage.low
     lhs._storage.high ${operator}= rhs._storage.high
   }
 % end

   @_inlineable // FIXME(sil-serialize-all)
   public static func <<=(lhs: inout DoubleWidth, rhs: DoubleWidth) {
     if rhs < (0 as DoubleWidth) {
       lhs >>= 0 - rhs
       return
     }

     // Shift is larger than this type's bit width.
     if rhs._storage.high != (0 as High) ||
       rhs._storage.low >= DoubleWidth.bitWidth
     {
       lhs = 0
       return
     }

     // Shift is exactly the width of `Base`, so low -> high.
     if rhs._storage.low == Base.bitWidth {
       lhs = DoubleWidth((High(truncatingIfNeeded: lhs._storage.low), 0))
       return
     }

     lhs &<<= rhs
   }

   @_inlineable // FIXME(sil-serialize-all)
   public static func >>=(lhs: inout DoubleWidth, rhs: DoubleWidth) {
     if rhs < (0 as DoubleWidth) {
       lhs <<= 0 - rhs
       return
     }

     // Shift is larger than this type's bit width.
     if rhs._storage.high != (0 as High) ||
       rhs._storage.low >= DoubleWidth.bitWidth
     {
       lhs = lhs < (0 as DoubleWidth) ? ~0 : 0
       return
     }

     // Shift is exactly the width of `Base`, so high -> low.
     if rhs._storage.low == Base.bitWidth {
       lhs = DoubleWidth((
         lhs < (0 as DoubleWidth) ? ~0 : 0,
         Low(truncatingIfNeeded: lhs._storage.high)
       ))
       return
     }

     lhs &>>= rhs
   }

   @_inlineable // FIXME(sil-serialize-all)
   public static func &<<=(lhs: inout DoubleWidth, rhs: DoubleWidth) {
     // Need to use smart shifts here, since rhs can be > Base.bitWidth
     let rhs = rhs & DoubleWidth(DoubleWidth.bitWidth - 1)

     lhs._storage.high <<= High(rhs._storage.low)

     let lowInHigh = Base.bitWidth > rhs._storage.low
       ? lhs._storage.low >> (numericCast(Base.bitWidth) - rhs._storage.low)
       : lhs._storage.low << (rhs._storage.low - numericCast(Base.bitWidth))
     lhs._storage.high |= High(truncatingIfNeeded: lowInHigh)

     lhs._storage.low <<= rhs._storage.low
   }

   @_inlineable // FIXME(sil-serialize-all)
   public static func &>>=(lhs: inout DoubleWidth, rhs: DoubleWidth) {
     // Need to use smart shifts here, since rhs can be > Base.bitWidth
     let rhs = rhs & DoubleWidth(DoubleWidth.bitWidth - 1)

     lhs._storage.low >>= rhs._storage.low

     let highInLow = Base.bitWidth > rhs._storage.low
       ? lhs._storage.high << (numericCast(Base.bitWidth) - rhs._storage.low)
       : lhs._storage.high >> (rhs._storage.low - numericCast(Base.bitWidth))
     lhs._storage.low |= Low(truncatingIfNeeded: highInLow)

     lhs._storage.high >>= High(truncatingIfNeeded: rhs._storage.low)
   }

 %{
 binaryOperators = [
   ('+', 'adding', '_', '+'),
   ('-', 'subtracting', '_', '-'),
   ('*', 'multiplied', 'by', '*'),
   ('/', 'divided', 'by', '/'),
   ('%', 'remainder', 'dividingBy', '/'),
 ]
 }%
 % for (operator, name, firstArg, kind) in binaryOperators:

   // FIXME(integers): remove this once the operators are back to Numeric
   @_inlineable // FIXME(sil-serialize-all)
   public static func ${operator} (
     lhs: DoubleWidth, rhs: DoubleWidth
   ) -> DoubleWidth {
     var lhs = lhs
     lhs ${operator}= rhs
     return lhs
   }

 %   argumentLabel = (firstArg + ':') if firstArg != '_' else ''
   @_inlineable // FIXME(sil-serialize-all)
   public static func ${operator}=(
     lhs: inout DoubleWidth, rhs: DoubleWidth
   ) {
     let (result, overflow) = lhs.${name}ReportingOverflow(${argumentLabel}rhs)
     _precondition(!overflow, "Overflow in ${operator}=")
     lhs = result
   }
 % end

   @_inlineable // FIXME(sil-serialize-all)
   public init(_truncatingBits bits: UInt) {
     _storage.low = Low(_truncatingBits: bits)
     _storage.high = High(_truncatingBits: bits >> UInt(Base.bitWidth))
   }

   // other
   //
   @_inlineable // FIXME(sil-serialize-all)
   public init(_builtinIntegerLiteral _x: _MaxBuiltinIntegerType) {
     var _x = _x
     self = DoubleWidth()

     // If we can capture the entire literal in a single Int64, stop there.
     // This avoids some potential deep recursion due to literal expressions in
     // other DoubleWidth methods.
     let (_value, _overflow) = Builtin.s_to_s_checked_trunc_Int2048_Int64(_x)
     if !Bool(_overflow) {
       self = DoubleWidth(Int64(_value))
       return
     }

     // Convert all but the most significant 64 bits as unsigned integers.
     let _shift = Builtin.sext_Int64_Int2048((64 as Int64)._value)
     let lowWordCount = (bitWidth - 1) / 64
     for i in 0..<lowWordCount {
       let value =
         DoubleWidth(UInt64(Builtin.s_to_u_checked_trunc_Int2048_Int64(_x).0))
           &<< DoubleWidth(i * 64)
       self |= value
       _x = Builtin.ashr_Int2048(_x, _shift)
     }

     // Finally, convert the most significant 64 bits and check for overflow.
     let overflow: Bool
     if Base.isSigned {
       let (_value, _overflow) = Builtin.s_to_s_checked_trunc_Int2048_Int64(_x)
       self |= DoubleWidth(Int64(_value)) &<< DoubleWidth(lowWordCount * 64)
       overflow = Bool(_overflow)
     } else {
       let (_value, _overflow) = Builtin.s_to_u_checked_trunc_Int2048_Int64(_x)
       self |= DoubleWidth(UInt64(_value)) &<< DoubleWidth(lowWordCount * 64)
       overflow = Bool(_overflow)
     }
     _precondition(!overflow, "Literal integer out of range for this type")
   }

   @_inlineable // FIXME(sil-serialize-all)
   public var description: String {
     return "(\(_storage.high), \(_storage.low))"
   }

   @_inlineable // FIXME(sil-serialize-all)
   public var leadingZeroBitCount: Int {
     return high == (0 as High)
       ? Base.bitWidth + low.leadingZeroBitCount
       : high.leadingZeroBitCount
   }

   @_inlineable // FIXME(sil-serialize-all)
   public var trailingZeroBitCount: Int {
     return low == (0 as Low)
       ? Base.bitWidth + high.trailingZeroBitCount
       : low.trailingZeroBitCount
   }

   @_inlineable // FIXME(sil-serialize-all)
   public var nonzeroBitCount: Int {
     return high.nonzeroBitCount + low.nonzeroBitCount
   }

   @_inlineable // FIXME(sil-serialize-all)
   public var hashValue: Int {
     return _mixInt(high.hashValue) ^ low.hashValue
   }

   @_inlineable // FIXME(sil-serialize-all)
   @_transparent
   public var byteSwapped: DoubleWidth {
     return DoubleWidth((
       High(truncatingIfNeeded: low.byteSwapped),
       Low(truncatingIfNeeded: high.byteSwapped)
     ))
   }
 }

 extension DoubleWidth : UnsignedInteger where Base : UnsignedInteger {}

 extension DoubleWidth : SignedNumeric, SignedInteger
   where Base : SignedInteger {}
	//===--- DoubleWidth.swift.gyb --------------------------------- swift --===//
	//
	// This source file is part of the Swift.org open source project
	//
	// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
	// Licensed under Apache License v2.0 with Runtime Library Exception
	//
	// See https://swift.org/LICENSE.txt for license information
	// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
	//
	//===----------------------------------------------------------------------===//

	/// A fixed-width integer that is twice the size of its base type.
	@_fixed_layout // FIXME(sil-serialize-all)
	public struct DoubleWidth<Base : FixedWidthInteger> : _ExpressibleByBuiltinIntegerLiteral
	where Base.Words : Collection, Base.Magnitude.Words : Collection {

	public typealias High = Base
	public typealias Low = Base.Magnitude

	@_versioned // FIXME(sil-serialize-all)
	internal var _storage: (high: Base, low: Base.Magnitude)

	@_inlineable // FIXME(sil-serialize-all)
	public var high: High {
	return _storage.high
	}

	@_inlineable // FIXME(sil-serialize-all)
	public var low: Low {
	return _storage.low
	}

	@_inlineable // FIXME(sil-serialize-all)
	public // @testable
	init(_ _value: (High, Low)) {
	self._storage = (high: _value.0, low: _value.1)
	}

	@_inlineable // FIXME(sil-serialize-all)
	public init() {
	self.init((0, 0))
	}
	}

	extension DoubleWidth: Comparable {
	@_inlineable // FIXME(sil-serialize-all)
	public static func ==(lhs: DoubleWidth, rhs: DoubleWidth) -> Bool {
	return (lhs._storage.high == rhs._storage.high) &&
	(lhs._storage.low == rhs._storage.low)
	}

	@_inlineable // FIXME(sil-serialize-all)
	public static func <(lhs: DoubleWidth, rhs: DoubleWidth) -> Bool {
	if lhs._storage.high < rhs._storage.high {
	return true
	}
	if lhs._storage.high > rhs._storage.high {
	return false
	}
	return lhs._storage.low < rhs._storage.low
	}
	}


	extension DoubleWidth: Numeric {
	public typealias Magnitude = DoubleWidth<Low>

	@_inlineable // FIXME(sil-serialize-all)
	public var magnitude: DoubleWidth<Low> {
	if Base.isSigned && _storage.high < (0 as High) {
	return self == .min
	? DoubleWidth.max.magnitude &+ 1
	: (0 - self).magnitude
	}
	return DoubleWidth<Low>((
	_storage.high.magnitude, _storage.low.magnitude))
	}

	@_inlineable // FIXME(sil-serialize-all)
	@_versioned // FIXME(sil-serialize-all)
	internal init(_ _magnitude: Magnitude) {
	self.init((High(_magnitude._storage.high), _magnitude._storage.low))
	}

	@_inlineable // FIXME(sil-serialize-all)
	public init<T : BinaryInteger>(_ source: T) {
	guard let result = DoubleWidth<Base>(exactly: source) else {
	_preconditionFailure("Value is outside the representable range")
	}
	self = result
	}

	@_inlineable // FIXME(sil-serialize-all)
	public init?<T : BinaryInteger>(exactly source: T) {
	// Can't represent a negative 'source' if Base is unsigned
	guard source >= 0 \|\| DoubleWidth.isSigned else { return nil }

	// Is 'source' is entirely representable in Low?
	if let low = Low(exactly: source.magnitude) {
	if source < (0 as T) {
	self.init((~0, ~low + 1))
	} else {
	self.init((0, low))
	}
	} else {
	// At this point we know source's bitWidth > Base.bitWidth, or else
	// we would've taken the first branch.
	let lowInT = source & T(~0 as Low)
	let highInT = source >> High.bitWidth

	let low = Low(lowInT.magnitude)
	guard let high = High(exactly: highInT) else { return nil }
	self.init((high, low))
	}
	}
	}

	extension DoubleWidth {
	@_inlineable // FIXME(sil-serialize-all)
	public init<T : BinaryFloatingPoint>(_ source: T) {
	fatalError()
	}

	@_inlineable // FIXME(sil-serialize-all)
	public init?<T : BinaryFloatingPoint>(exactly source: T) {
	fatalError()
	}

	@_inlineable // FIXME(sil-serialize-all)
	public init<T : BinaryFloatingPoint>(_ source: T)
	where T.RawSignificand : FixedWidthInteger
	{
	_precondition(source.isFinite, "Can't create a DoubleWidth from a non-finite value")
	self.init(exactly: source.rounded(.towardZero))!
	}

	@_inlineable // FIXME(sil-serialize-all)
	public init?<T : BinaryFloatingPoint>(exactly source: T)
	where T.RawSignificand : FixedWidthInteger
	{
	// Need a finite value
	guard source.isFinite else { return nil }

	// Don't need to go further with zero.
	if source.isZero {
	self.init(0)
	return
	}

	// Need a value with a non-negative exponent
	guard source.exponent >= 0 else { return nil }

	typealias Raw = T.RawSignificand
	let bitPattern = source.significandBitPattern \|
	((1 as Raw) &<< Raw(T.significandBitCount))
	let offset = T.significandBitCount - Int(source.exponent)

	// FIXME: spurious compile error when 'where' clause above is removed:
	// error: non-nominal type 'T.RawSignificand' does not support explicit initialization
	let fractionPart: Raw = bitPattern &<< Raw(Raw.bitWidth - offset)
	guard fractionPart == (0 as Raw) else {
	return nil
	}

	let integerPart: Raw = bitPattern &>> Raw(offset)

	// Should have caught any actual zero values above
	_sanityCheck(integerPart > (0 as Raw))

	if source.sign == .minus {
	if !DoubleWidth.isSigned \|\| integerPart &- 1 > DoubleWidth.max {
	return nil
	}
	// Have to juggle, or else the intermediate step of creating a value
	// with Self.min's magnitude will overflow. It's okay to use wrapping
	// subtraction because integerPart > 0.
	self.init(integerPart &- 1)
	self = 0 &- self &- 1
	} else {
	self.init(exactly: integerPart)
	}
	}
	}

	extension DoubleWidth: FixedWidthInteger {
	@_fixed_layout // FIXME(sil-serialize-all)
	public struct Words : Collection {
	public enum _IndexValue {
	case low(Base.Magnitude.Words.Index)
	case high(Base.Words.Index)
	}

	@_fixed_layout // FIXME(sil-serialize-all)
	public struct Index : Comparable {
	public var _value: _IndexValue

	@_inlineable // FIXME(sil-serialize-all)
	public init(_ _value: _IndexValue) { self._value = _value }

	@_inlineable // FIXME(sil-serialize-all)
	public static func ==(lhs: Index, rhs: Index) -> Bool {
	switch (lhs._value, rhs._value) {
	case let (.low(l), .low(r)): return l == r
	case let (.high(l), .high(r)): return l == r
	default: return false
	}
	}

	@_inlineable // FIXME(sil-serialize-all)
	public static func <(lhs: Index, rhs: Index) -> Bool {
	switch (lhs._value, rhs._value) {
	case let (.low(l), .low(r)): return l < r
	case (.low(_), .high(_)): return true
	case (.high(_), .low(_)): return false
	case let (.high(l), .high(r)): return l < r
	}
	}
	}

	public var _high: Base.Words
	public var _low: Base.Magnitude.Words

	@_inlineable // FIXME(sil-serialize-all)
	public init(_ value: DoubleWidth<Base>) {
	// multiples of word-size only
	guard Base.bitWidth == Base.Magnitude.bitWidth &&
	(UInt.bitWidth % Base.bitWidth == 0 \|\|
	Base.bitWidth % UInt.bitWidth == 0) else {
	fatalError("Access to words is not supported on this type")
	}
	self._high = value._storage.high.words
	self._low = value._storage.low.words
	_sanityCheck(!_low.isEmpty)
	}

	@_inlineable // FIXME(sil-serialize-all)
	public var startIndex: Index {
	return Index(.low(_low.startIndex))
	}

	@_inlineable // FIXME(sil-serialize-all)
	public var endIndex: Index {
	return Index(.high(_high.endIndex))
	}

	@_inlineable // FIXME(sil-serialize-all)
	public var count: Int {
	if Base.bitWidth < UInt.bitWidth { return 1 }
	return Int(_low.count) + Int(_high.count)
	}

	@_inlineable // FIXME(sil-serialize-all)
	public func index(after i: Index) -> Index {
	switch i._value {
	case let .low(li):
	if Base.bitWidth < UInt.bitWidth {
	return Index(.high(_high.endIndex))
	}
	let next = _low.index(after: li)
	if next == _low.endIndex {
	return Index(.high(_high.startIndex))
	}
	return Index(.low(next))
	case let .high(hi):
	return Index(.high(_high.index(after: hi)))
	}
	}

	@_inlineable // FIXME(sil-serialize-all)
	public subscript(_ i: Index) -> UInt {
	if Base.bitWidth < UInt.bitWidth {
	_precondition(i == Index(.low(_low.startIndex)), "Invalid index")
	_sanityCheck(2 * Base.bitWidth <= UInt.bitWidth)
	return _low.first! \| (_high.first! &<< Base.bitWidth._lowWord)
	}
	switch i._value {
	case let .low(li): return _low[li]
	case let .high(hi): return _high[hi]
	}
	}
	}

	@_inlineable // FIXME(sil-serialize-all)
	public var words: Words {
	return Words(self)
	}

	@_inlineable // FIXME(sil-serialize-all)
	public static var isSigned: Bool {
	return Base.isSigned
	}

	// fixed width
	//
	@_inlineable // FIXME(sil-serialize-all)
	public static var max: DoubleWidth {
	return self.init((High.max, Low.max))
	}

	@_inlineable // FIXME(sil-serialize-all)
	public static var min: DoubleWidth {
	return self.init((High.min, Low.min))
	}

	@_inlineable // FIXME(sil-serialize-all)
	public static var bitWidth: Int {
	return 2 * Base.bitWidth
	}

	% for (operator, name) in [('+', 'adding'), ('-', 'subtracting')]:
	% highAffectedByLowOverflow = 'Base.max' if operator == '+' else 'Base.min'
	@_inlineable // FIXME(sil-serialize-all)
	public func ${name}ReportingOverflow(_ rhs: DoubleWidth)
	-> (partialValue: DoubleWidth, overflow: Bool) {
	let (low, lowOverflow) =
	_storage.low.${name}ReportingOverflow(rhs._storage.low)
	let (high, highOverflow) =
	_storage.high.${name}ReportingOverflow(rhs._storage.high)
	let result = (high &${operator} (lowOverflow ? 1 : 0), low)
	let overflow = highOverflow \|\|
	high == ${highAffectedByLowOverflow} && lowOverflow
	return (partialValue: DoubleWidth(result), overflow: overflow)
	}
	% end

	@_inlineable // FIXME(sil-serialize-all)
	public func multipliedReportingOverflow(
	by rhs: DoubleWidth
	) -> (partialValue: DoubleWidth, overflow: Bool) {
	let (carry, product) = multipliedFullWidth(by: rhs)
	let result = DoubleWidth(truncatingIfNeeded: product)

	let isNegative = (self < (0 as DoubleWidth)) != (rhs < (0 as DoubleWidth))
	let didCarry = isNegative
	? carry != ~(0 as DoubleWidth)
	: carry != (0 as DoubleWidth)
	let hadPositiveOverflow = !isNegative &&
	DoubleWidth.isSigned && product.leadingZeroBitCount == 0

	return (result, didCarry \|\| hadPositiveOverflow)
	}

	// Specialize for the most popular types.
	@_specialize(where Base == Int)
	@_specialize(where Base == UInt)
	@_specialize(where Base == Int64)
	@_specialize(where Base == UInt64)
	@_inlineable // FIXME(sil-serialize-all)
	public func quotientAndRemainder(dividingBy other: DoubleWidth)
	-> (quotient: DoubleWidth, remainder: DoubleWidth) {
	let isNegative = (self < (0 as DoubleWidth)) != (other < (0 as DoubleWidth))

	let rhs = other.magnitude
	var q = self.magnitude

	// Bail if \|other\| > \|self\|
	if rhs.leadingZeroBitCount < q.leadingZeroBitCount {
	return (0, self)
	}

	// Calculate the number of bits before q and rhs line up,
	// we can skip that many bits of iteration.
	let initialOffset = q.leadingZeroBitCount +
	(DoubleWidth.bitWidth - rhs.leadingZeroBitCount) - 1

	// Start with remainder capturing the high bits of q.
	// (These need to be smart shifts, as initialOffset can be > q.bitWidth)
	var r = q >> Magnitude(DoubleWidth.bitWidth - initialOffset)
	q <<= Magnitude(initialOffset)

	let highBit = ~(~0 >> 1) as Magnitude
	for _ in initialOffset..<DoubleWidth.bitWidth {
	r <<= 1
	if q & highBit != (0 as Magnitude) {
	r += 1 as Magnitude
	}
	q <<= 1

	if r >= rhs {
	q \|= 1
	r -= rhs
	}
	}

	// Sign of remainder matches dividend
	let remainder = self < (0 as DoubleWidth)
	? 0 - DoubleWidth(r)
	: DoubleWidth(r)

	if isNegative {
	return (0 - DoubleWidth(q), remainder)
	} else {
	return (DoubleWidth(q), remainder)
	}
	}

	@_inlineable // FIXME(sil-serialize-all)
	public func dividedReportingOverflow(by other: DoubleWidth)
	-> (partialValue: DoubleWidth, overflow: Bool) {
	if other == (0 as DoubleWidth) \|\|
	(DoubleWidth.isSigned && other == (-1 as Int) && self == .min)
	{
	return (self, true)
	}

	return (quotientAndRemainder(dividingBy: other).quotient, false)
	}

	@_inlineable // FIXME(sil-serialize-all)
	public func remainderReportingOverflow(dividingBy other: DoubleWidth)
	-> (partialValue: DoubleWidth, overflow: Bool) {
	if other == 0 \|\|
	(DoubleWidth.isSigned && other == -1 && self == .min)
	{
	return (self, true)
	}

	return (quotientAndRemainder(dividingBy: other).remainder, false)
	}

	@_inlineable // FIXME(sil-serialize-all)
	public func multipliedFullWidth(by other: DoubleWidth)
	-> (high: DoubleWidth, low: DoubleWidth.Magnitude) {
	let isNegative = DoubleWidth.isSigned &&
	(self < (0 as DoubleWidth)) != (other < (0 as DoubleWidth))

	func mul(_ x: Low, _ y: Low) -> (partial: Low, carry: Low) {
	let (high, low) = x.multipliedFullWidth(by: y)
	return (low, high)
	}

	func sum(_ x: Low, _ y: Low, _ z: Low) -> (partial: Low, carry: Low) {
	let (sum1, overflow1) = x.addingReportingOverflow(y)
	let (sum2, overflow2) = sum1.addingReportingOverflow(z)
	let carry: Low = (overflow1 ? 1 : 0) + (overflow2 ? 1 : 0)
	return (sum2, carry)
	}

	let lhs = self.magnitude
	let rhs = other.magnitude

	let a = mul(rhs._storage.low, lhs._storage.low)
	let b = mul(rhs._storage.low, lhs._storage.high)
	let c = mul(rhs._storage.high, lhs._storage.low)
	let d = mul(rhs._storage.high, lhs._storage.high)

	let mid1 = sum(a.carry, b.partial, c.partial)
	let mid2 = sum(b.carry, c.carry, d.partial)

	let low = DoubleWidth<Low>((mid1.partial, a.partial))
	let high = DoubleWidth((
	High(mid2.carry + d.carry), mid1.carry + mid2.partial
	))

	if isNegative {
	let (lowComplement, overflow) = (~low).addingReportingOverflow(1)
	return (~high + (overflow ? 1 : 0), lowComplement)
	} else {
	return (high, low)
	}
	}

	@_inlineable // FIXME(sil-serialize-all)
	public func dividingFullWidth(
	_ dividend: (high: DoubleWidth, low: DoubleWidth.Magnitude)
	) -> (quotient: DoubleWidth, remainder: DoubleWidth) {
	let lhs = DoubleWidth<DoubleWidth<Base>>(dividend)
	let rhs = DoubleWidth<DoubleWidth<Base>>(self)
	let (quotient, remainder) = lhs.quotientAndRemainder(dividingBy: rhs)

	// FIXME(integers): check for overflow of quotient and remainder
	return (DoubleWidth(quotient.low), DoubleWidth(remainder.low))
	}

	% for operator in ['&', '\|', '^']:
	@_inlineable // FIXME(sil-serialize-all)
	public static func ${operator}=(
	lhs: inout DoubleWidth, rhs: DoubleWidth
	) {
	lhs._storage.low ${operator}= rhs._storage.low
	lhs._storage.high ${operator}= rhs._storage.high
	}
	% end

	@_inlineable // FIXME(sil-serialize-all)
	public static func <<=(lhs: inout DoubleWidth, rhs: DoubleWidth) {
	if rhs < (0 as DoubleWidth) {
	lhs >>= 0 - rhs
	return
	}

	// Shift is larger than this type's bit width.
	if rhs._storage.high != (0 as High) \|\|
	rhs._storage.low >= DoubleWidth.bitWidth
	{
	lhs = 0
	return
	}

	// Shift is exactly the width of `Base`, so low -> high.
	if rhs._storage.low == Base.bitWidth {
	lhs = DoubleWidth((High(truncatingIfNeeded: lhs._storage.low), 0))
	return
	}

	lhs &<<= rhs
	}

	@_inlineable // FIXME(sil-serialize-all)
	public static func >>=(lhs: inout DoubleWidth, rhs: DoubleWidth) {
	if rhs < (0 as DoubleWidth) {
	lhs <<= 0 - rhs
	return
	}

	// Shift is larger than this type's bit width.
	if rhs._storage.high != (0 as High) \|\|
	rhs._storage.low >= DoubleWidth.bitWidth
	{
	lhs = lhs < (0 as DoubleWidth) ? ~0 : 0
	return
	}

	// Shift is exactly the width of `Base`, so high -> low.
	if rhs._storage.low == Base.bitWidth {
	lhs = DoubleWidth((
	lhs < (0 as DoubleWidth) ? ~0 : 0,
	Low(truncatingIfNeeded: lhs._storage.high)
	))
	return
	}

	lhs &>>= rhs
	}

	@_inlineable // FIXME(sil-serialize-all)
	public static func &<<=(lhs: inout DoubleWidth, rhs: DoubleWidth) {
	// Need to use smart shifts here, since rhs can be > Base.bitWidth
	let rhs = rhs & DoubleWidth(DoubleWidth.bitWidth - 1)

	lhs._storage.high <<= High(rhs._storage.low)

	let lowInHigh = Base.bitWidth > rhs._storage.low
	? lhs._storage.low >> (numericCast(Base.bitWidth) - rhs._storage.low)
	: lhs._storage.low << (rhs._storage.low - numericCast(Base.bitWidth))
	lhs._storage.high \|= High(truncatingIfNeeded: lowInHigh)

	lhs._storage.low <<= rhs._storage.low
	}

	@_inlineable // FIXME(sil-serialize-all)
	public static func &>>=(lhs: inout DoubleWidth, rhs: DoubleWidth) {
	// Need to use smart shifts here, since rhs can be > Base.bitWidth
	let rhs = rhs & DoubleWidth(DoubleWidth.bitWidth - 1)

	lhs._storage.low >>= rhs._storage.low

	let highInLow = Base.bitWidth > rhs._storage.low
	? lhs._storage.high << (numericCast(Base.bitWidth) - rhs._storage.low)
	: lhs._storage.high >> (rhs._storage.low - numericCast(Base.bitWidth))
	lhs._storage.low \|= Low(truncatingIfNeeded: highInLow)

	lhs._storage.high >>= High(truncatingIfNeeded: rhs._storage.low)
	}

	%{
	binaryOperators = [
	('+', 'adding', '_', '+'),
	('-', 'subtracting', '_', '-'),
	('', 'multiplied', 'by', ''),
	('/', 'divided', 'by', '/'),
	('%', 'remainder', 'dividingBy', '/'),
	]
	}%
	% for (operator, name, firstArg, kind) in binaryOperators:

	// FIXME(integers): remove this once the operators are back to Numeric
	@_inlineable // FIXME(sil-serialize-all)
	public static func ${operator} (
	lhs: DoubleWidth, rhs: DoubleWidth
	) -> DoubleWidth {
	var lhs = lhs
	lhs ${operator}= rhs
	return lhs
	}

	% argumentLabel = (firstArg + ':') if firstArg != '_' else ''
	@_inlineable // FIXME(sil-serialize-all)
	public static func ${operator}=(
	lhs: inout DoubleWidth, rhs: DoubleWidth
	) {
	let (result, overflow) = lhs.${name}ReportingOverflow(${argumentLabel}rhs)
	_precondition(!overflow, "Overflow in ${operator}=")
	lhs = result
	}
	% end

	@_inlineable // FIXME(sil-serialize-all)
	public init(_truncatingBits bits: UInt) {
	_storage.low = Low(_truncatingBits: bits)
	_storage.high = High(_truncatingBits: bits >> UInt(Base.bitWidth))
	}

	// other
	//
	@_inlineable // FIXME(sil-serialize-all)
	public init(_builtinIntegerLiteral _x: _MaxBuiltinIntegerType) {
	var _x = _x
	self = DoubleWidth()

	// If we can capture the entire literal in a single Int64, stop there.
	// This avoids some potential deep recursion due to literal expressions in
	// other DoubleWidth methods.
	let (_value, _overflow) = Builtin.s_to_s_checked_trunc_Int2048_Int64(_x)
	if !Bool(_overflow) {
	self = DoubleWidth(Int64(_value))
	return
	}

	// Convert all but the most significant 64 bits as unsigned integers.
	let _shift = Builtin.sext_Int64_Int2048((64 as Int64)._value)
	let lowWordCount = (bitWidth - 1) / 64
	for i in 0..<lowWordCount {
	let value =
	DoubleWidth(UInt64(Builtin.s_to_u_checked_trunc_Int2048_Int64(_x).0))
	&<< DoubleWidth(i * 64)
	self \|= value
	_x = Builtin.ashr_Int2048(_x, _shift)
	}

	// Finally, convert the most significant 64 bits and check for overflow.
	let overflow: Bool
	if Base.isSigned {
	let (_value, _overflow) = Builtin.s_to_s_checked_trunc_Int2048_Int64(_x)
	self \|= DoubleWidth(Int64(_value)) &<< DoubleWidth(lowWordCount * 64)
	overflow = Bool(_overflow)
	} else {
	let (_value, _overflow) = Builtin.s_to_u_checked_trunc_Int2048_Int64(_x)
	self \|= DoubleWidth(UInt64(_value)) &<< DoubleWidth(lowWordCount * 64)
	overflow = Bool(_overflow)
	}
	_precondition(!overflow, "Literal integer out of range for this type")
	}

	@_inlineable // FIXME(sil-serialize-all)
	public var description: String {
	return "(\(_storage.high), \(_storage.low))"
	}

	@_inlineable // FIXME(sil-serialize-all)
	public var leadingZeroBitCount: Int {
	return high == (0 as High)
	? Base.bitWidth + low.leadingZeroBitCount
	: high.leadingZeroBitCount
	}

	@_inlineable // FIXME(sil-serialize-all)
	public var trailingZeroBitCount: Int {
	return low == (0 as Low)
	? Base.bitWidth + high.trailingZeroBitCount
	: low.trailingZeroBitCount
	}

	@_inlineable // FIXME(sil-serialize-all)
	public var nonzeroBitCount: Int {
	return high.nonzeroBitCount + low.nonzeroBitCount
	}

	@_inlineable // FIXME(sil-serialize-all)
	public var hashValue: Int {
	return _mixInt(high.hashValue) ^ low.hashValue
	}

	@_inlineable // FIXME(sil-serialize-all)
	@_transparent
	public var byteSwapped: DoubleWidth {
	return DoubleWidth((
	High(truncatingIfNeeded: low.byteSwapped),
	Low(truncatingIfNeeded: high.byteSwapped)
	))
	}
	}

	extension DoubleWidth : UnsignedInteger where Base : UnsignedInteger {}

	extension DoubleWidth : SignedNumeric, SignedInteger
	where Base : SignedInteger {}