//! Subtraction operations for BigInt.
//!
//! Implements constant-time subtraction using the `sbb` (subtract with borrow) algorithm
//! as specified in the Arithmetic Algorithm Specification.

use crate::error::Result;
use crate::limbs::{ct_compare, limb_sub_borrow};
use crate::types::BigIntCore;

#[cfg(feature = "alloc")]
use crate::types::BigInt;

/// Subtract two BigInt magnitudes (a - b).
///
/// Returns (result, borrow_out) where borrow_out indicates if result is negative.
#[cfg(feature = "alloc")]
pub fn sub_magnitude(a: &BigInt, b: &BigInt, result: &mut BigInt) -> Result<bool> {
    let n = a.limb_count().max(b.limb_count());
    result.ensure_capacity(n)?;

    let a_limbs = a.limbs();
    let b_limbs = b.limbs();
    let result_limbs = result.limbs_mut();

    let mut borrow = 0u64;

    // Subtract limbs from least significant to most significant
    // Execute full loop for constant-time behavior
    for i in 0..n {
        let a_val = if i < a_limbs.len() { a_limbs[i] } else { 0 };
        let b_val = if i < b_limbs.len() { b_limbs[i] } else { 0 };

        let (diff, borrow_out) = limb_sub_borrow(a_val, b_val, borrow);
        if i < result_limbs.len() {
            result_limbs[i] = diff;
        }
        borrow = borrow_out;
    }

    let is_negative = borrow != 0;

    // If result is negative, compute two's complement
    if is_negative {
        // Two's complement: invert all bits and add 1
        for i in 0..n {
            if i < result_limbs.len() {
                result_limbs[i] = !result_limbs[i];
            }
        }

        // Add 1 to complete two's complement
        let mut carry = 1u64;
        for i in 0..n {
            if i < result_limbs.len() {
                let (sum, carry_out) = crate::limbs::limb_add_carry(result_limbs[i], 0, carry);
                result_limbs[i] = sum;
                carry = carry_out;
            }
        }
    }

    result.canonicalize()?;
    Ok(is_negative)
}

/// Subtract two BigInt values (a - b).
#[cfg(feature = "alloc")]
pub fn sub(a: &BigInt, b: &BigInt) -> Result<BigInt> {
    // Handle zero cases
    if b.is_zero() {
        return Ok(a.clone());
    }
    if a.is_zero() {
        let mut result = b.clone();
        result.set_sign(!b.sign()); // Negate b
        return Ok(result);
    }

    // Compare magnitudes to determine result sign
    let cmp = ct_compare(a.limbs(), b.limbs());
    let a_gt_b = (cmp & 1) != 0;
    let a_eq_b = cmp == 0;

    if a_eq_b {
        // Equal magnitudes: result is zero
        let max_limbs = a.max_limbs().max(b.max_limbs());
        return Ok(BigInt::new(max_limbs));
    }

    let max_limbs = a.max_limbs().max(b.max_limbs());
    let mut result = BigInt::new(max_limbs);

    let is_negative = if a_gt_b {
        // a > b: compute a - b
        sub_magnitude(a, b, &mut result)?
    } else {
        // a < b: compute b - a, result will be negative
        sub_magnitude(b, a, &mut result)?
    };

    // Determine final sign
    let final_sign = if a.sign() == b.sign() {
        // Same sign: if a > b, keep sign; if a < b, flip sign
        if a_gt_b { a.sign() } else { !a.sign() }
    } else {
        // Opposite signs: if a is positive and a > b, result positive
        // if a is negative and a > b, result negative
        if a_gt_b { a.sign() } else { b.sign() }
    };

    result.set_sign(final_sign ^ is_negative);
    Ok(result)
}

/// In-place subtraction for dynamic BigInt.
#[cfg(feature = "alloc")]
pub fn sub_assign(a: &mut BigInt, b: &BigInt) -> Result<()> {
    let result = sub(a, b)?;
    *a = result;
    Ok(())
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_sub_simple() {
        let a = BigInt::from_u64(20, 10);
        let b = BigInt::from_u64(10, 10);
        let result = sub(&a, &b).unwrap();
        assert_eq!(result.limbs()[0], 10);
        assert!(!result.sign());
    }

    #[test]
    fn test_sub_with_borrow() {
        let a = BigInt::from_u64(10, 10);
        let b = BigInt::from_u64(20, 10);
        let result = sub(&a, &b).unwrap();
        // Result should be negative
        assert!(result.sign() || result.is_zero());
    }
}
