DoubleWidth.swift.gyb

//===--- 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
  where Base.Words : Collection, Base.Magnitude.Words : Collection {

  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 struct Words : Collection {
    public enum _IndexValue {
      case low(Base.Magnitude.Words.Index)
      case high(Base.Words.Index)
    }
    
    public struct Index : Comparable {
      public var _value: _IndexValue

      public init(_ _value: _IndexValue) { self._value = _value }

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

      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

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

    public var startIndex: Index {
      return Index(.low(_low.startIndex))
    }

    public var endIndex: Index {
      return Index(.high(_high.endIndex))
    }
    
    public var count: Int {
      if Base.bitWidth < UInt.bitWidth { return 1 }
      return Int(_low.count) + Int(_high.count)
    }
  
    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)))
      }
    }
  
    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]
      }
    }
  }

  public var words: Words {
    return Words(self)
  }

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