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.
 public struct DoubleWidth<Base : FixedWidthInteger> :
   FixedWidthInteger, _ExpressibleByBuiltinIntegerLiteral {

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

   internal var _storage: (high: Base, low: Base.Magnitude)

   public // @testable
   init(_ _value: (High, Low)) {
     self._storage = (high: _value.0, low: _value.1)
   }

   public var high: High {
     return _storage.high
   }

   public var low: Low {
     return _storage.low
   }

   // Numeric
   //
   public init() {
     self.init((0, 0))
   }

   // BinaryInteger
   //
   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))
   }

   internal init(_ _magnitude: Magnitude) {
     self.init((High(_magnitude._storage.high), _magnitude._storage.low))
   }

   public static func ==(lhs: DoubleWidth, rhs: DoubleWidth) -> Bool {
     return (lhs._storage.high == rhs._storage.high) &&
       (lhs._storage.low == rhs._storage.low)
   }

   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
   }

   public init<T : BinaryInteger>(_ source: T) {
     self.init(exactly: source)!
   }

   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 &>> numericCast(High.bitWidth)

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

   public init<T : FloatingPoint>(_ source: T) {
     fatalError()
   }

   public init?<T : FloatingPoint>(exactly source: T) {
     fatalError()
   }

   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))!
   }

   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)
     }
   }

   public func _word(at n: Int) -> UInt {
     if Base.bitWidth < UInt.bitWidth {
       if UInt.bitWidth % Base.bitWidth != 0 {
         fatalError("word(at:) is not supported on this type")
       }
       if n > 0 {
         // Since `Base` is narrower than word, any non-zero word will give us
         // the correct value here (0 or ~0).
         return _storage.high._word(at: n)
       }
       return _storage.low._word(at: 0) |
         (_storage.high._word(at: 0) << numericCast(Base.bitWidth))
     } else {
       // multiples of word-size only
       if Base.bitWidth % UInt.bitWidth != 0 {
         fatalError("word(at:) is not supported on this type")
       }

       // TODO: move to Int128 just like init(_builtinIntegerLiteral:) ?
       return (n < _storage.low.countRepresentedWords) ?
         _storage.low._word(at: n) :
         _storage.high._word(at: n - _storage.low.countRepresentedWords)
     }
   }

   public static var isSigned: Bool {
     return Base.isSigned
   }

   // fixed width
   //
   public static var max: DoubleWidth {
     return self.init((High.max, Low.max))
   }

   public static var min: DoubleWidth {
     return self.init((High.min, Low.min))
   }

   public static var bitWidth: Int {
     return 2 * Base.bitWidth
   }

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

   public func multipliedReportingOverflow(
     by rhs: DoubleWidth
   ) -> (partialValue: DoubleWidth, overflow: ArithmeticOverflow) {
     let (carry, product) = multipliedFullWidth(by: rhs)
     let result = DoubleWidth(extendingOrTruncating: 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, ArithmeticOverflow(didCarry || hadPositiveOverflow))
   }

   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

     // TODO(performance): Use &>> instead here?
     // Start with remainder capturing the high bits of q.
     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)
     }
   }

   public func dividedReportingOverflow(by other: DoubleWidth)
     -> (partialValue: DoubleWidth, overflow: ArithmeticOverflow) {
     if other == (0 as DoubleWidth) ||
       (DoubleWidth.isSigned && other == (-1 as Int) && self == .min)
     {
       return (self, .overflow)
     }

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

   public func remainderReportingOverflow(dividingBy other: DoubleWidth)
     -> (partialValue: DoubleWidth, overflow: ArithmeticOverflow) {
     if other == 0 ||
       (DoubleWidth.isSigned && other == -1 && self == .min)
     {
       return (self, .overflow)
     }

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

   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 == .overflow ? 1 : 0) +
         (overflow2 == .overflow ? 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 == .overflow ? 1 : 0), lowComplement)
     } else {
       return (high, low)
     }
   }

   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 ['&', '|', '^']:
   public static func ${operator}=(
     lhs: inout DoubleWidth, rhs: DoubleWidth
   ) {
     lhs._storage.low ${operator}= rhs._storage.low
     lhs._storage.high ${operator}= rhs._storage.high
   }
 % end

   public static func <<=(lhs: inout DoubleWidth, rhs: DoubleWidth) {
     if rhs < (0 as DoubleWidth) {
       lhs >>= 0 - rhs
       return
     }

     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(extendingOrTruncating: lhs._storage.low), 0))
       return
     }

     lhs &<<= rhs
   }

   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(extendingOrTruncating: lhs._storage.high)
       ))
       return
     }

     lhs &>>= rhs
   }

   public static func &<<=(lhs: inout DoubleWidth, rhs: DoubleWidth) {
     let rhs = rhs & DoubleWidth(DoubleWidth.bitWidth - 1)

     lhs._storage.high <<= High(rhs._storage.low)
     if Base.bitWidth > rhs._storage.low {
       lhs._storage.high |= High(extendingOrTruncating: lhs._storage.low >>
         (numericCast(Base.bitWidth) - rhs._storage.low))
     } else {
       lhs._storage.high |= High(extendingOrTruncating: lhs._storage.low <<
         (rhs._storage.low - numericCast(Base.bitWidth)))
     }
     lhs._storage.low <<= rhs._storage.low
   }

   public static func &>>=(lhs: inout DoubleWidth, rhs: DoubleWidth) {
     let rhs = rhs & DoubleWidth(DoubleWidth.bitWidth - 1)

     lhs._storage.low >>= rhs._storage.low
     if Base.bitWidth > rhs._storage.low {
       lhs._storage.low |= Low(extendingOrTruncating: lhs._storage.high <<
         numericCast(numericCast(Base.bitWidth) - rhs._storage.low))
     } else {
       lhs._storage.low |= Low(extendingOrTruncating: lhs._storage.high >>
         numericCast(rhs._storage.low - numericCast(Base.bitWidth)))
     }
     lhs._storage.high >>= High(extendingOrTruncating: 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
   public static func ${operator} (
     lhs: DoubleWidth, rhs: DoubleWidth
   ) -> DoubleWidth {
     var lhs = lhs
     lhs ${operator}= rhs
     return lhs
   }

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

   public init(_truncatingBits bits: UInt) {
     _storage.low = Low(_truncatingBits: bits)
     _storage.high = High(_truncatingBits: bits >> UInt(Base.bitWidth))
   }

   // other
   //
   public init(_builtinIntegerLiteral x: _MaxBuiltinIntegerType) {
     // FIXME: This won't work if `x` is out of range for `Int64`
     self.init(Int64(_builtinIntegerLiteral: x))
   }

   public var description: String {
     return "(\(_storage.high), \(_storage.low))"
   }

   public var leadingZeroBitCount: Int {
     return high == (0 as High)
       ? Base.bitWidth + low.leadingZeroBitCount
       : high.leadingZeroBitCount
   }

   public var trailingZeroBitCount: Int {
     return low == (0 as Low)
       ? Base.bitWidth + high.trailingZeroBitCount
       : low.trailingZeroBitCount
   }

   public var nonzeroBitCount: Int {
     return high.nonzeroBitCount + low.nonzeroBitCount
   }

   public var hashValue: Int {
     return _mixInt(high.hashValue) ^ low.hashValue
   }

   @_transparent
   public var byteSwapped: DoubleWidth {
     return DoubleWidth((High(extendingOrTruncating: low.byteSwapped),
       Low(extendingOrTruncating: high.byteSwapped)))
   }
 }

 // FIXME(ABI) (Conditional Conformance):
 // DoubleWidth should conform to SignedInteger where Base : SignedInteger
 extension DoubleWidth where Base : SignedInteger {
   /// Returns the additive inverse of the specified value.
   ///
   /// The negation operator (prefix `-`) returns the additive inverse of its
   /// argument.
   ///
   ///     let x = 21 as DoubleWidth<Int>
   ///     let y = -x
   ///     // y == -21
   ///
   /// The resulting value must be representable in the same type as the
   /// argument. In particular, negating a signed, fixed-width integer type's
   /// minimum results in a value that cannot be represented.
   ///
   ///     let z = -DoubleWidth<Int>.min
   ///     // Overflow error
   ///
   /// - Returns: The additive inverse of this value.
   ///
   /// - SeeAlso: `negate()`
   public static prefix func - (_ operand: DoubleWidth) -> DoubleWidth {
     return 0 - operand
   }

   /// Replaces this value with its additive inverse.
   ///
   /// The following example uses the `negate()` method to negate the value of
   /// an integer `x`:
   ///
   ///     var x = 21 as DoubleWidth<Int>
   ///     x.negate()
   ///     // x == -21
   ///
   /// - SeeAlso: The unary minus operator (`-`).
   public mutating func negate() {
     self = 0 - self
   }
 }
	//===--- 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.
	public struct DoubleWidth<Base : FixedWidthInteger> :
	FixedWidthInteger, _ExpressibleByBuiltinIntegerLiteral {

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

	internal var _storage: (high: Base, low: Base.Magnitude)

	public // @testable
	init(_ _value: (High, Low)) {
	self._storage = (high: _value.0, low: _value.1)
	}

	public var high: High {
	return _storage.high
	}

	public var low: Low {
	return _storage.low
	}

	// Numeric
	//
	public init() {
	self.init((0, 0))
	}

	// BinaryInteger
	//
	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))
	}

	internal init(_ _magnitude: Magnitude) {
	self.init((High(_magnitude._storage.high), _magnitude._storage.low))
	}

	public static func ==(lhs: DoubleWidth, rhs: DoubleWidth) -> Bool {
	return (lhs._storage.high == rhs._storage.high) &&
	(lhs._storage.low == rhs._storage.low)
	}

	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
	}

	public init<T : BinaryInteger>(_ source: T) {
	self.init(exactly: source)!
	}

	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 &>> numericCast(High.bitWidth)

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

	public init<T : FloatingPoint>(_ source: T) {
	fatalError()
	}

	public init?<T : FloatingPoint>(exactly source: T) {
	fatalError()
	}

	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))!
	}

	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)
	}
	}

	public func _word(at n: Int) -> UInt {
	if Base.bitWidth < UInt.bitWidth {
	if UInt.bitWidth % Base.bitWidth != 0 {
	fatalError("word(at:) is not supported on this type")
	}
	if n > 0 {
	// Since `Base` is narrower than word, any non-zero word will give us
	// the correct value here (0 or ~0).
	return _storage.high._word(at: n)
	}
	return _storage.low._word(at: 0) \|
	(_storage.high._word(at: 0) << numericCast(Base.bitWidth))
	} else {
	// multiples of word-size only
	if Base.bitWidth % UInt.bitWidth != 0 {
	fatalError("word(at:) is not supported on this type")
	}

	// TODO: move to Int128 just like init(_builtinIntegerLiteral:) ?
	return (n < _storage.low.countRepresentedWords) ?
	_storage.low._word(at: n) :
	_storage.high._word(at: n - _storage.low.countRepresentedWords)
	}
	}

	public static var isSigned: Bool {
	return Base.isSigned
	}

	// fixed width
	//
	public static var max: DoubleWidth {
	return self.init((High.max, Low.max))
	}

	public static var min: DoubleWidth {
	return self.init((High.min, Low.min))
	}

	public static var bitWidth: Int {
	return 2 * Base.bitWidth
	}

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

	public func multipliedReportingOverflow(
	by rhs: DoubleWidth
	) -> (partialValue: DoubleWidth, overflow: ArithmeticOverflow) {
	let (carry, product) = multipliedFullWidth(by: rhs)
	let result = DoubleWidth(extendingOrTruncating: 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, ArithmeticOverflow(didCarry \|\| hadPositiveOverflow))
	}

	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

	// TODO(performance): Use &>> instead here?
	// Start with remainder capturing the high bits of q.
	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)
	}
	}

	public func dividedReportingOverflow(by other: DoubleWidth)
	-> (partialValue: DoubleWidth, overflow: ArithmeticOverflow) {
	if other == (0 as DoubleWidth) \|\|
	(DoubleWidth.isSigned && other == (-1 as Int) && self == .min)
	{
	return (self, .overflow)
	}

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

	public func remainderReportingOverflow(dividingBy other: DoubleWidth)
	-> (partialValue: DoubleWidth, overflow: ArithmeticOverflow) {
	if other == 0 \|\|
	(DoubleWidth.isSigned && other == -1 && self == .min)
	{
	return (self, .overflow)
	}

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

	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 == .overflow ? 1 : 0) +
	(overflow2 == .overflow ? 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 == .overflow ? 1 : 0), lowComplement)
	} else {
	return (high, low)
	}
	}

	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 ['&', '\|', '^']:
	public static func ${operator}=(
	lhs: inout DoubleWidth, rhs: DoubleWidth
	) {
	lhs._storage.low ${operator}= rhs._storage.low
	lhs._storage.high ${operator}= rhs._storage.high
	}
	% end

	public static func <<=(lhs: inout DoubleWidth, rhs: DoubleWidth) {
	if rhs < (0 as DoubleWidth) {
	lhs >>= 0 - rhs
	return
	}

	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(extendingOrTruncating: lhs._storage.low), 0))
	return
	}

	lhs &<<= rhs
	}

	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(extendingOrTruncating: lhs._storage.high)
	))
	return
	}

	lhs &>>= rhs
	}

	public static func &<<=(lhs: inout DoubleWidth, rhs: DoubleWidth) {
	let rhs = rhs & DoubleWidth(DoubleWidth.bitWidth - 1)

	lhs._storage.high <<= High(rhs._storage.low)
	if Base.bitWidth > rhs._storage.low {
	lhs._storage.high \|= High(extendingOrTruncating: lhs._storage.low >>
	(numericCast(Base.bitWidth) - rhs._storage.low))
	} else {
	lhs._storage.high \|= High(extendingOrTruncating: lhs._storage.low <<
	(rhs._storage.low - numericCast(Base.bitWidth)))
	}
	lhs._storage.low <<= rhs._storage.low
	}

	public static func &>>=(lhs: inout DoubleWidth, rhs: DoubleWidth) {
	let rhs = rhs & DoubleWidth(DoubleWidth.bitWidth - 1)

	lhs._storage.low >>= rhs._storage.low
	if Base.bitWidth > rhs._storage.low {
	lhs._storage.low \|= Low(extendingOrTruncating: lhs._storage.high <<
	numericCast(numericCast(Base.bitWidth) - rhs._storage.low))
	} else {
	lhs._storage.low \|= Low(extendingOrTruncating: lhs._storage.high >>
	numericCast(rhs._storage.low - numericCast(Base.bitWidth)))
	}
	lhs._storage.high >>= High(extendingOrTruncating: 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
	public static func ${operator} (
	lhs: DoubleWidth, rhs: DoubleWidth
	) -> DoubleWidth {
	var lhs = lhs
	lhs ${operator}= rhs
	return lhs
	}

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

	public init(_truncatingBits bits: UInt) {
	_storage.low = Low(_truncatingBits: bits)
	_storage.high = High(_truncatingBits: bits >> UInt(Base.bitWidth))
	}

	// other
	//
	public init(_builtinIntegerLiteral x: _MaxBuiltinIntegerType) {
	// FIXME: This won't work if `x` is out of range for `Int64`
	self.init(Int64(_builtinIntegerLiteral: x))
	}

	public var description: String {
	return "(\(_storage.high), \(_storage.low))"
	}

	public var leadingZeroBitCount: Int {
	return high == (0 as High)
	? Base.bitWidth + low.leadingZeroBitCount
	: high.leadingZeroBitCount
	}

	public var trailingZeroBitCount: Int {
	return low == (0 as Low)
	? Base.bitWidth + high.trailingZeroBitCount
	: low.trailingZeroBitCount
	}

	public var nonzeroBitCount: Int {
	return high.nonzeroBitCount + low.nonzeroBitCount
	}

	public var hashValue: Int {
	return _mixInt(high.hashValue) ^ low.hashValue
	}

	@_transparent
	public var byteSwapped: DoubleWidth {
	return DoubleWidth((High(extendingOrTruncating: low.byteSwapped),
	Low(extendingOrTruncating: high.byteSwapped)))
	}
	}

	// FIXME(ABI) (Conditional Conformance):
	// DoubleWidth should conform to SignedInteger where Base : SignedInteger
	extension DoubleWidth where Base : SignedInteger {
	/// Returns the additive inverse of the specified value.
	///
	/// The negation operator (prefix `-`) returns the additive inverse of its
	/// argument.
	///
	/// let x = 21 as DoubleWidth<Int>
	/// let y = -x
	/// // y == -21
	///
	/// The resulting value must be representable in the same type as the
	/// argument. In particular, negating a signed, fixed-width integer type's
	/// minimum results in a value that cannot be represented.
	///
	/// let z = -DoubleWidth<Int>.min
	/// // Overflow error
	///
	/// - Returns: The additive inverse of this value.
	///
	/// - SeeAlso: `negate()`
	public static prefix func - (_ operand: DoubleWidth) -> DoubleWidth {
	return 0 - operand
	}

	/// Replaces this value with its additive inverse.
	///
	/// The following example uses the `negate()` method to negate the value of
	/// an integer `x`:
	///
	/// var x = 21 as DoubleWidth<Int>
	/// x.negate()
	/// // x == -21
	///
	/// - SeeAlso: The unary minus operator (`-`).
	public mutating func negate() {
	self = 0 - self
	}
	}