| //===--- 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 { |
| var result = 0 |
| result = _combineHashValues(result, _storage.high.hashValue) |
| result = _combineHashValues(result, _storage.low.hashValue) |
| return result |
| } |
| } |
| |
| 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 {} |