CryptoSwift/Sources/CryptoSwift/CS_BigInt/Subtraction.swift

//
//  Subtraction.swift
//  CS.BigInt
//
//  Created by Károly Lőrentey on 2016-01-03.
//  Copyright © 2016-2017 Károly Lőrentey.
//

extension CS.BigUInt {
    //MARK: Subtraction

    /// Subtract `word` from this integer in place, returning a flag indicating if the operation
    /// caused an arithmetic overflow. `word` is shifted `shift` words to the left before being subtracted.
    ///
    /// - Note: If the result indicates an overflow, then `self` becomes the two's complement of the absolute difference.
    /// - Complexity: O(count)
    internal mutating func subtractWordReportingOverflow(_ word: Word, shiftedBy shift: Int = 0) -> Bool {
        precondition(shift >= 0)
        var carry: Word = word
        var i = shift
        let count = self.count
        while carry > 0 && i < count {
            let (d, c) = self[i].subtractingReportingOverflow(carry)
            self[i] = d
            carry = (c ? 1 : 0)
            i += 1
        }
        return carry > 0
    }

    /// Subtract `word` from this integer, returning the difference and a flag that is true if the operation
    /// caused an arithmetic overflow. `word` is shifted `shift` words to the left before being subtracted.
    ///
    /// - Note: If `overflow` is true, then the returned value is the two's complement of the absolute difference.
    /// - Complexity: O(count)
    internal func subtractingWordReportingOverflow(_ word: Word, shiftedBy shift: Int = 0) -> (partialValue: CS.BigUInt, overflow: Bool) {
        var result = self
        let overflow = result.subtractWordReportingOverflow(word, shiftedBy: shift)
        return (result, overflow)
    }

    /// Subtract a digit `d` from this integer in place.
    /// `d` is shifted `shift` digits to the left before being subtracted.
    ///
    /// - Requires: self >= d * 2^shift
    /// - Complexity: O(count)
    internal mutating func subtractWord(_ word: Word, shiftedBy shift: Int = 0) {
        let overflow = subtractWordReportingOverflow(word, shiftedBy: shift)
        precondition(!overflow)
    }

    /// Subtract a digit `d` from this integer and return the result.
    /// `d` is shifted `shift` digits to the left before being subtracted.
    ///
    /// - Requires: self >= d * 2^shift
    /// - Complexity: O(count)
    internal func subtractingWord(_ word: Word, shiftedBy shift: Int = 0) -> CS.BigUInt {
        var result = self
        result.subtractWord(word, shiftedBy: shift)
        return result
    }

    /// Subtract `other` from this integer in place, and return a flag indicating if the operation caused an
    /// arithmetic overflow. `other` is shifted `shift` digits to the left before being subtracted.
    ///
    /// - Note: If the result indicates an overflow, then `self` becomes the twos' complement of the absolute difference.
    /// - Complexity: O(count)
    public mutating func subtractReportingOverflow(_ b: CS.BigUInt, shiftedBy shift: Int = 0) -> Bool {
        precondition(shift >= 0)
        var carry = false
        var bi = 0
        let bc = b.count
        let count = self.count
        while bi < bc || (shift + bi < count && carry) {
            let ai = shift + bi
            let (d, c) = self[ai].subtractingReportingOverflow(b[bi])
            if carry {
                let (d2, c2) = d.subtractingReportingOverflow(1)
                self[ai] = d2
                carry = c || c2
            }
            else {
                self[ai] = d
                carry = c
            }
            bi += 1
        }
        return carry
    }

    /// Subtract `other` from this integer, returning the difference and a flag indicating arithmetic overflow.
    /// `other` is shifted `shift` digits to the left before being subtracted.
    ///
    /// - Note: If `overflow` is true, then the result value is the twos' complement of the absolute value of the difference.
    /// - Complexity: O(count)
    public func subtractingReportingOverflow(_ other: CS.BigUInt, shiftedBy shift: Int) -> (partialValue: CS.BigUInt, overflow: Bool) {
        var result = self
        let overflow = result.subtractReportingOverflow(other, shiftedBy: shift)
        return (result, overflow)
    }
    
    /// Subtracts `other` from `self`, returning the result and a flag indicating arithmetic overflow.
    ///
    /// - Note: When the operation overflows, then `partialValue` is the twos' complement of the absolute value of the difference.
    /// - Complexity: O(count)
    public func subtractingReportingOverflow(_ other: CS.BigUInt) -> (partialValue: CS.BigUInt, overflow: Bool) {
        return self.subtractingReportingOverflow(other, shiftedBy: 0)
    }
    
    /// Subtract `other` from this integer in place.
    /// `other` is shifted `shift` digits to the left before being subtracted.
    ///
    /// - Requires: self >= other * 2^shift
    /// - Complexity: O(count)
    public mutating func subtract(_ other: CS.BigUInt, shiftedBy shift: Int = 0) {
        let overflow = subtractReportingOverflow(other, shiftedBy: shift)
        precondition(!overflow)
    }

    /// Subtract `b` from this integer, and return the difference.
    /// `b` is shifted `shift` digits to the left before being subtracted.
    ///
    /// - Requires: self >= b * 2^shift
    /// - Complexity: O(count)
    public func subtracting(_ other: CS.BigUInt, shiftedBy shift: Int = 0) -> CS.BigUInt {
        var result = self
        result.subtract(other, shiftedBy: shift)
        return result
    }

    /// Decrement this integer by one.
    ///
    /// - Requires: !isZero
    /// - Complexity: O(count)
    public mutating func decrement(shiftedBy shift: Int = 0) {
        self.subtract(1, shiftedBy: shift)
    }

    /// Subtract `b` from `a` and return the result.
    ///
    /// - Requires: a >= b
    /// - Complexity: O(a.count)
    public static func -(a: CS.BigUInt, b: CS.BigUInt) -> CS.BigUInt {
        return a.subtracting(b)
    }

    /// Subtract `b` from `a` and store the result in `a`.
    ///
    /// - Requires: a >= b
    /// - Complexity: O(a.count)
    public static func -=(a: inout CS.BigUInt, b: CS.BigUInt) {
        a.subtract(b)
    }
}

extension CS.BigInt {
    public mutating func negate() {
        guard !magnitude.isZero else { return }
        self.sign = self.sign == .plus ? .minus : .plus
    }

    /// Subtract `b` from `a` and return the result.
    public static func -(a: CS.BigInt, b: CS.BigInt) -> CS.BigInt {
        return a + -b
    }

    /// Subtract `b` from `a` in place.
    public static func -=(a: inout CS.BigInt, b: CS.BigInt) { a = a - b }
}