//===--- 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 has twice the bit width of its base type.
///
/// You can use the `DoubleWidth` type to continue calculations with the result
/// of a full width arithmetic operation. Normally, when you perform a full
/// width operation, the result is a tuple of the high and low parts of the
/// result.
///
///     let a = 2241543570477705381
///     let b = 186319822866995413
///     let c = a.multipliedFullWidth(by: b)
///     // c == (high: 22640526660490081, low: 7959093232766896457)
///
/// The tuple `c` can't be used in any further comparisons or calculations. To
/// use this value, create a `DoubleWidth` instance from the result. You can
/// use the `DoubleWidth` instance in the same way that you would use any other
/// integer type.
///
///     let d = DoubleWidth(a.multipliedFullWidth(by: b))
///     // d == 417644001000058515200174966092417353
///
///     // Check the calculation:
///     print(d / DoubleWidth(a) == b)
///     // Prints "true"
///
///     if d > Int.max {
///         print("Too big to be an 'Int'!")
///     } else {
///         print("Small enough to fit in an 'Int'")
///     }
///     // Prints "Too big to be an 'Int'!"
///
/// The `DoubleWidth` type is not intended as a replacement for a variable-width
/// integer type. Nesting `DoubleWidth` instances, in particular, may result in
/// undesirable performance.
@_fixed_layout // FIXME(sil-serialize-all)
public struct DoubleWidth<Base : FixedWidthInteger> :
  _ExpressibleByBuiltinIntegerLiteral
  where Base.Magnitude : UnsignedInteger,
  Base.Words : Collection, Base.Magnitude.Words : Collection {

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

#if _endian(big)
  @_versioned // FIXME(sil-serialize-all)
  internal var _storage: (high: High, low: Low)
#else
  @_versioned // FIXME(sil-serialize-all)
  internal var _storage: (low: Low, high: High)
#endif

  /// The high part of the value.
  @_inlineable // FIXME(sil-serialize-all)
  @_transparent
  public var high: High {
    return _storage.high
  }

  /// The low part of the value.
  @_inlineable // FIXME(sil-serialize-all)
  @_transparent
  public var low: Low {
    return _storage.low
  }

  /// Creates a new instance from the given tuple of high and low parts.
  ///
  /// - Parameter value: The tuple to use as the source of the new instance's
  ///   high and low parts.
  @_inlineable // FIXME(sil-serialize-all)
  @_transparent
  public init(_ value: (high: High, low: Low)) {
#if _endian(big)
    self._storage = (high: value.0, low: value.1)
#else
    self._storage = (low: value.1, high: value.0)
#endif
  }

  // We expect users to invoke the public initializer above as demonstrated in
  // the documentation (that is, by passing in the result of a full width
  // operation).
  //
  // Internally, we'll need to create new instances by supplying high and low
  // parts directly; ((double parentheses)) greatly impair readability,
  // especially when nested:
  //
  //   DoubleWidth<DoubleWidth>((DoubleWidth((0, 0)), DoubleWidth((0, 0))))
  //
  // For that reason, we'll include an internal initializer that takes two
  // separate arguments.
  @_inlineable // FIXME(sil-serialize-all)
  @_versioned
  @_transparent
  internal init(_ _high: High, _ low: Low) {
    self.init((_high, low))
  }

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

extension DoubleWidth : CustomStringConvertible {
  @_inlineable // FIXME(sil-serialize-all)
  public var description: String {
    return String(self, radix: 10)
  }
}

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

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

  @_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 : Hashable {
  @_inlineable // FIXME(sil-serialize-all)
  public var hashValue: Int {
    return _hashValue(for: self)
  }

  @_inlineable // FIXME(sil-serialize-all)
  public func _hash(into hasher: inout _Hasher) {
    hasher.append(low)
    hasher.append(high)
  }
}

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

  @_inlineable // FIXME(sil-serialize-all)
  public var magnitude: Magnitude {
    let result = Magnitude(Low(truncatingIfNeeded: _storage.high), _storage.low)
    if Base.isSigned && _storage.high < (0 as High) {
      return ~result &+ 1
    } else {
      return result
    }
  }

  @_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 DoubleWidth.isSigned || source >= 0 else { return nil }
    
    // Is 'source' entirely representable in Low?
    if let low = Low(exactly: source.magnitude) {
      self.init(source < (0 as T) ? (~0, ~low &+ 1) : (0, low))
    } else {
      // At this point we know source.bitWidth > Base.bitWidth, or else we
      // would've taken the first branch.
      let lowInT = source & T(~0 as Low)
      let highInT = source >> Low.bitWidth
      
      let low = Low(lowInT)
      guard let high = High(exactly: highInT) else { return nil }
      self.init(high, low)
    }
  }
}

extension DoubleWidth : FixedWidthInteger {
  @_fixed_layout // FIXME(sil-serialize-all)
  public struct Words : Collection {
    @_fixed_layout // FIXME(sil-serialize-all)
    public enum _IndexValue {
      case low(Low.Words.Index)
      case high(High.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: High.Words
    public var _low: Low.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
  }

  @_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 High.bitWidth + Low.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 = DoubleWidth.isSigned &&
      (self < (0 as DoubleWidth)) != (rhs < (0 as DoubleWidth))
    let didCarry = isNegative
      ? carry != ~(0 as DoubleWidth)
      : carry != (0 as DoubleWidth)
    let hadPositiveOverflow =
      DoubleWidth.isSigned && !isNegative && product.leadingZeroBitCount == 0

    return (result, didCarry || hadPositiveOverflow)
  }

  @_inlineable // FIXME(sil-serialize-all)
  public func quotientAndRemainder(
    dividingBy other: DoubleWidth
  ) -> (quotient: DoubleWidth, remainder: DoubleWidth) {
    let (quotient, remainder) =
      Magnitude._divide(self.magnitude, by: other.magnitude)
    guard DoubleWidth.isSigned else {
      return (DoubleWidth(quotient), DoubleWidth(remainder))
    }
    let isNegative = (self.high < (0 as High)) != (other.high < (0 as High))
    let quotient_ = isNegative
      ? quotient == DoubleWidth.min.magnitude
        ? DoubleWidth.min
        : 0 - DoubleWidth(quotient)
      : DoubleWidth(quotient)
    let remainder_ = self.high < (0 as High)
      ? 0 - DoubleWidth(remainder)
      : DoubleWidth(remainder)
    return (quotient_, remainder_)
  }

  @_inlineable // FIXME(sil-serialize-all)
  public func dividedReportingOverflow(
    by other: DoubleWidth
  ) -> (partialValue: DoubleWidth, overflow: Bool) {
    if other == (0 as DoubleWidth) { return (self, true) }
    if DoubleWidth.isSigned && other == -1 && 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 as DoubleWidth) { return (self, true) }
    if DoubleWidth.isSigned && other == -1 && self == .min { return (0, 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 as DoubleWidth), lowComplement)
    } else {
      return (high, low)
    }
  }

  @_inlineable // FIXME(sil-serialize-all)
  public func dividingFullWidth(
    _ dividend: (high: DoubleWidth, low: DoubleWidth.Magnitude)
  ) -> (quotient: DoubleWidth, remainder: DoubleWidth) {
    let other = DoubleWidth<DoubleWidth>(dividend)
    let (quotient, remainder) =
      Magnitude._divide(other.magnitude, by: self.magnitude)
    guard DoubleWidth.isSigned else {
      return (DoubleWidth(quotient), DoubleWidth(remainder))
    }
    let isNegative =
      (self.high < (0 as High)) != (other.high.high < (0 as High))
    let quotient_ = isNegative
      ? quotient == DoubleWidth.min.magnitude
        ? DoubleWidth.min
        : 0 - DoubleWidth(quotient)
      : DoubleWidth(quotient)
    let remainder_ = other.high.high < (0 as High)
      ? 0 - DoubleWidth(remainder)
      : DoubleWidth(remainder)
    return (quotient_, remainder_)
  }

% 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 DoubleWidth.isSigned && 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
    }

    lhs &<<= rhs
  }
  
  @_inlineable // FIXME(sil-serialize-all)
  public static func >>=(lhs: inout DoubleWidth, rhs: DoubleWidth) {
    if DoubleWidth.isSigned && 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
    }

    lhs &>>= rhs
  }

  /// Returns this value "masked" by its bit width.
  ///
  /// "Masking" notionally involves repeatedly incrementing or decrementing this
  /// value by `self.bitWidth` until the result is contained in the range
  /// `0..<self.bitWidth`.
  @_inlineable // FIXME(sil-serialize-all)
  @_versioned
  @_transparent
  internal func _masked() -> DoubleWidth {
    // FIXME(integers): test types with bit widths that aren't powers of 2
    if DoubleWidth.bitWidth.nonzeroBitCount == 1 {
      return self & DoubleWidth(DoubleWidth.bitWidth &- 1)
    }
    if DoubleWidth.isSigned && self._storage.high < (0 as High) {
      return self % DoubleWidth(DoubleWidth.bitWidth) + self
    }
    return self % DoubleWidth(DoubleWidth.bitWidth)
  }

  @_inlineable // FIXME(sil-serialize-all)
  public static func &<<=(lhs: inout DoubleWidth, rhs: DoubleWidth) {
    let rhs = rhs._masked()

    guard rhs._storage.low < Base.bitWidth else {
      lhs._storage.high = High(
        truncatingIfNeeded: lhs._storage.low &<<
          (rhs._storage.low &- Low(Base.bitWidth)))
      lhs._storage.low = 0
      return
    }

    guard rhs._storage.low != (0 as Low) else { return }
    lhs._storage.high &<<= High(rhs._storage.low)
    lhs._storage.high |= High(
      truncatingIfNeeded: lhs._storage.low &>>
        (Low(Base.bitWidth) &- rhs._storage.low))
    lhs._storage.low &<<= rhs._storage.low
  }
  
  @_inlineable // FIXME(sil-serialize-all)
  public static func &>>=(lhs: inout DoubleWidth, rhs: DoubleWidth) {
    let rhs = rhs._masked()

    guard rhs._storage.low < Base.bitWidth else {
      lhs._storage.low = Low(
        truncatingIfNeeded: lhs._storage.high &>>
          High(rhs._storage.low &- Low(Base.bitWidth)))
      lhs._storage.high = lhs._storage.high < (0 as High) ? ~0 : 0
      return
    }

    guard rhs._storage.low != (0 as Low) else { return }
    lhs._storage.low &>>= rhs._storage.low
    lhs._storage.low |= Low(
      truncatingIfNeeded: lhs._storage.high &<<
        High(Low(Base.bitWidth) &- rhs._storage.low))
    lhs._storage.high &>>= High(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(Low.bitWidth))
  }

  @_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 leadingZeroBitCount: Int {
    return high == (0 as High)
      ? High.bitWidth + low.leadingZeroBitCount
      : high.leadingZeroBitCount
  }

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

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

  @_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 {
  /// Returns the quotient and remainder after dividing a triple-width magnitude
  /// `lhs` by a double-width magnitude `rhs`.
  ///
  /// This operation is conceptually that described by Burnikel and Ziegler
  /// (1998).
  @_inlineable // FIXME(sil-serialize-all)
  @_versioned
  internal static func _divide(
    _ lhs: (high: Low, mid: Low, low: Low), by rhs: Magnitude
  ) -> (quotient: Low, remainder: Magnitude) {
    // The following invariants are guaranteed to hold by dividingFullWidth or
    // quotientAndRemainder before this method is invoked:
    _sanityCheck(lhs.high != (0 as Low))
    _sanityCheck(rhs.leadingZeroBitCount == 0)
    _sanityCheck(Magnitude(lhs.high, lhs.mid) < rhs)

    // Estimate the quotient.
    var quotient = lhs.high == rhs.high
      ? Low.max
      : rhs.high.dividingFullWidth((lhs.high, lhs.mid)).quotient
    // Compute quotient * rhs.
    // TODO: This could be performed more efficiently.
    var product =
      DoubleWidth<Magnitude>(
        0, Magnitude(quotient.multipliedFullWidth(by: rhs.low)))
    let (x, y) = quotient.multipliedFullWidth(by: rhs.high)
    product += DoubleWidth<Magnitude>(Magnitude(0, x), Magnitude(y, 0))
    // Compute the remainder after decrementing quotient as necessary.
    var remainder =
      DoubleWidth<Magnitude>(
        Magnitude(0, lhs.high), Magnitude(lhs.mid, lhs.low))
    while remainder < product {
      quotient = quotient &- 1
      remainder += DoubleWidth<Magnitude>(0, rhs)
    }
    remainder -= product

    return (quotient, remainder.low)
  }

  /// Returns the quotient and remainder after dividing a quadruple-width
  /// magnitude `lhs` by a double-width magnitude `rhs`.
  @_inlineable // FIXME(sil-serialize-all)
  @_versioned
  internal static func _divide(
    _ lhs: DoubleWidth<Magnitude>, by rhs: Magnitude
  ) -> (quotient: Magnitude, remainder: Magnitude) {
    guard _fastPath(rhs > (0 as Magnitude)) else {
      fatalError("Division by zero")
    }
    guard _fastPath(rhs >= lhs.high) else {
      fatalError("Division results in an overflow")
    }

    if lhs.high == (0 as Magnitude) {
      return lhs.low.quotientAndRemainder(dividingBy: rhs)
    }

    if rhs.high == (0 as Low) {
      let a = lhs.high.high % rhs.low
      let b = a == (0 as Low)
        ? lhs.high.low % rhs.low
        : rhs.low.dividingFullWidth((a, lhs.high.low)).remainder
      let (x, c) = b == (0 as Low)
        ? lhs.low.high.quotientAndRemainder(dividingBy: rhs.low)
        : rhs.low.dividingFullWidth((b, lhs.low.high))
      let (y, d) = c == (0 as Low)
        ? lhs.low.low.quotientAndRemainder(dividingBy: rhs.low)
        : rhs.low.dividingFullWidth((c, lhs.low.low))
      return (Magnitude(x, y), Magnitude(0, d))
    }

    // Left shift both rhs and lhs, then divide and right shift the remainder.
    let shift = rhs.leadingZeroBitCount
    let rhs = rhs &<< shift
    let lhs = lhs &<< shift
    if lhs.high.high == (0 as Low)
      && Magnitude(lhs.high.low, lhs.low.high) < rhs {
      let (quotient, remainder) =
        Magnitude._divide((lhs.high.low, lhs.low.high, lhs.low.low), by: rhs)
      return (Magnitude(0, quotient), remainder &>> shift)
    }
    let (x, a) =
      Magnitude._divide((lhs.high.high, lhs.high.low, lhs.low.high), by: rhs)
    let (y, b) =
      Magnitude._divide((a.high, a.low, lhs.low.low), by: rhs)
    return (Magnitude(x, y), b &>> shift)
  }

  /// Returns the quotient and remainder after dividing a double-width
  /// magnitude `lhs` by a double-width magnitude `rhs`.
  @_inlineable // FIXME(sil-serialize-all)
  @_versioned
  internal static func _divide(
    _ lhs: Magnitude, by rhs: Magnitude
  ) -> (quotient: Magnitude, remainder: Magnitude) {
    guard _fastPath(rhs > (0 as Magnitude)) else {
      fatalError("Division by zero")
    }
    guard rhs < lhs else {
      if _fastPath(rhs > lhs) { return (0, lhs) }
      return (1, 0)
    }

    if lhs.high == (0 as Low) {
      let (quotient, remainder) =
        lhs.low.quotientAndRemainder(dividingBy: rhs.low)
      return (Magnitude(quotient), Magnitude(remainder))
    }

    if rhs.high == (0 as Low) {
      let (x, a) = lhs.high.quotientAndRemainder(dividingBy: rhs.low)
      let (y, b) = a == (0 as Low)
        ? lhs.low.quotientAndRemainder(dividingBy: rhs.low)
        : rhs.low.dividingFullWidth((a, lhs.low))
      return (Magnitude(x, y), Magnitude(0, b))
    }

    // Left shift both rhs and lhs, then divide and right shift the remainder.
    let shift = rhs.leadingZeroBitCount
    let rhs = rhs &<< shift
    let high = (lhs &>> (Magnitude.bitWidth &- shift)).low
    let lhs = lhs &<< shift
    let (quotient, remainder) =
      Magnitude._divide((high, lhs.high, lhs.low), by: rhs)
    return (Magnitude(0, quotient), remainder &>> shift)
  }
}

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