oxinum-int 0.1.0

//! Two's-complement bitwise operations on [`BigInt`]:
//! `BitAnd`/`BitOr`/`BitXor`/`Not`/`Shl`/`Shr`.
//!
//! # Two's-complement semantics
//!
//! `BigInt` represents an infinite-precision signed integer. For bitwise
//! operations we use the mathematical two's-complement model: every value has
//! an infinite conceptual bit string. Positive numbers are padded with infinite
//! zeros on the left; negative numbers are padded with infinite ones (their
//! mathematical two's-complement of their magnitude never terminates).
//!
//! ## Algorithm overview
//!
//! For `&`, `|`, `^` on `BigInt`:
//! 1. Choose `nlimbs = max(|a|.limbs, |b|.limbs) + 1` (the extra limb absorbs
//!    the sign-extension and prevents the result from crossing back through
//!    the sign boundary for most cases).
//! 2. Convert both operands to their two's-complement limb vectors of length
//!    `nlimbs` via [`to_twos_complement`].
//! 3. Apply the operation limb-wise.
//! 4. Decode the result back to a `BigInt` via [`from_twos_complement`].
//!
//! ## `Not`
//!
//! The mathematical rule is `!x = -(x) - 1`:
//! - `!0 = -1`
//! - `!5 = -6`
//! - `!(-1) = 0`
//! - `!(-6) = 5`
//!
//! ## Arithmetic right shift
//!
//! `>>` is **arithmetic** (sign-extending) shift — it equals floor division by
//! `2^k`. For `k >= 64*limbs` the result is `0` (positive) or `-1` (negative).
//!
//! For negative `self = -m` (m > 0):
//! ```text
//! floor(-m / 2^k) = -ceil(m / 2^k) = -(((m - 1) >> k) + 1)
//! ```

use super::int::BigInt;
use super::uint::BigUint;
use core::ops::{BitAnd, BitOr, BitXor, Not, Shl, Shr};
use oxinum_core::Sign;

// ---------------------------------------------------------------------------
// Two's-complement helpers
// ---------------------------------------------------------------------------

/// Convert `n` to its two's-complement representation as a `Vec<u64>` of
/// exactly `nlimbs` limbs (little-endian).
///
/// - `n >= 0`: copy `n.magnitude().as_limbs()`, zero-pad to `nlimbs`.
/// - `n < 0` (value = `-m`, m > 0): pad `m` to `nlimbs`, then negate in
///   two's complement (flip all bits, add 1 with carry).
fn to_twos_complement(n: &BigInt, nlimbs: usize) -> Vec<u64> {
    let mag = n.magnitude().as_limbs();
    let mut out = vec![0u64; nlimbs];
    // Copy the magnitude limbs (they fit because nlimbs >= mag.len()).
    let copy_len = mag.len().min(nlimbs);
    out[..copy_len].copy_from_slice(&mag[..copy_len]);

    if n.is_negative() {
        // Negate in two's complement: flip all bits then add 1.
        for limb in out.iter_mut() {
            *limb = !*limb;
        }
        // Add 1 with carry propagation.
        let mut carry: u64 = 1;
        for limb in out.iter_mut() {
            let (v, c) = limb.overflowing_add(carry);
            *limb = v;
            carry = c as u64;
            if carry == 0 {
                break;
            }
        }
        // Any remaining carry means we overflowed nlimbs; since the
        // true mathematical value is exact, this can only happen if
        // m == 0 (which is forbidden for negative BigInt by the canonical-zero
        // invariant) or if nlimbs is absurdly small.
    }
    out
}

/// Decode a two's-complement limb vector (little-endian) back to a `BigInt`.
///
/// Sign is determined by the MSB of `limbs[n-1]`. For a positive result,
/// the limbs are directly the magnitude. For a negative result, the magnitude
/// is recovered by two's-complement negation of the limb vector.
fn from_twos_complement(limbs: &[u64]) -> BigInt {
    if limbs.is_empty() {
        return BigInt::zero();
    }
    let top = limbs[limbs.len() - 1];
    if top >> 63 == 0 {
        // Non-negative: the limbs *are* the magnitude.
        BigInt::from_parts(Sign::Positive, BigUint::from_le_limbs(limbs))
    } else {
        // Negative: recover magnitude via two's-complement negation.
        let mut neg: Vec<u64> = limbs.to_vec();
        for v in neg.iter_mut() {
            *v = !*v;
        }
        let mut carry: u64 = 1;
        for v in neg.iter_mut() {
            let (nv, c) = v.overflowing_add(carry);
            *v = nv;
            carry = c as u64;
            if carry == 0 {
                break;
            }
        }
        BigInt::from_parts(Sign::Negative, BigUint::from_le_limbs(&neg))
    }
}

// ---------------------------------------------------------------------------
// Core binary-op helper
// ---------------------------------------------------------------------------

/// Apply a bitwise binary op to two `BigInt` values under two's-complement.
#[inline]
fn bigint_binop<F>(lhs: &BigInt, rhs: &BigInt, op: F) -> BigInt
where
    F: Fn(u64, u64) -> u64,
{
    let llen = lhs.magnitude().as_limbs().len();
    let rlen = rhs.magnitude().as_limbs().len();
    // Extra limb absorbs sign-extension noise for all finite pairs.
    let nlimbs = llen.max(rlen) + 1;
    let ltc = to_twos_complement(lhs, nlimbs);
    let rtc = to_twos_complement(rhs, nlimbs);
    let result: Vec<u64> = ltc
        .iter()
        .zip(rtc.iter())
        .map(|(&a, &b)| op(a, b))
        .collect();
    from_twos_complement(&result)
}

// ---------------------------------------------------------------------------
// BitAnd for BigInt
// ---------------------------------------------------------------------------

impl BitAnd<&BigInt> for &BigInt {
    type Output = BigInt;
    #[inline]
    fn bitand(self, rhs: &BigInt) -> BigInt {
        bigint_binop(self, rhs, |a, b| a & b)
    }
}

impl BitAnd<BigInt> for BigInt {
    type Output = BigInt;
    #[inline]
    fn bitand(self, rhs: BigInt) -> BigInt {
        bigint_binop(&self, &rhs, |a, b| a & b)
    }
}

impl BitAnd<&BigInt> for BigInt {
    type Output = BigInt;
    #[inline]
    fn bitand(self, rhs: &BigInt) -> BigInt {
        bigint_binop(&self, rhs, |a, b| a & b)
    }
}

impl BitAnd<BigInt> for &BigInt {
    type Output = BigInt;
    #[inline]
    fn bitand(self, rhs: BigInt) -> BigInt {
        bigint_binop(self, &rhs, |a, b| a & b)
    }
}

// ---------------------------------------------------------------------------
// BitOr for BigInt
// ---------------------------------------------------------------------------

impl BitOr<&BigInt> for &BigInt {
    type Output = BigInt;
    #[inline]
    fn bitor(self, rhs: &BigInt) -> BigInt {
        bigint_binop(self, rhs, |a, b| a | b)
    }
}

impl BitOr<BigInt> for BigInt {
    type Output = BigInt;
    #[inline]
    fn bitor(self, rhs: BigInt) -> BigInt {
        bigint_binop(&self, &rhs, |a, b| a | b)
    }
}

impl BitOr<&BigInt> for BigInt {
    type Output = BigInt;
    #[inline]
    fn bitor(self, rhs: &BigInt) -> BigInt {
        bigint_binop(&self, rhs, |a, b| a | b)
    }
}

impl BitOr<BigInt> for &BigInt {
    type Output = BigInt;
    #[inline]
    fn bitor(self, rhs: BigInt) -> BigInt {
        bigint_binop(self, &rhs, |a, b| a | b)
    }
}

// ---------------------------------------------------------------------------
// BitXor for BigInt
// ---------------------------------------------------------------------------

impl BitXor<&BigInt> for &BigInt {
    type Output = BigInt;
    #[inline]
    fn bitxor(self, rhs: &BigInt) -> BigInt {
        bigint_binop(self, rhs, |a, b| a ^ b)
    }
}

impl BitXor<BigInt> for BigInt {
    type Output = BigInt;
    #[inline]
    fn bitxor(self, rhs: BigInt) -> BigInt {
        bigint_binop(&self, &rhs, |a, b| a ^ b)
    }
}

impl BitXor<&BigInt> for BigInt {
    type Output = BigInt;
    #[inline]
    fn bitxor(self, rhs: &BigInt) -> BigInt {
        bigint_binop(&self, rhs, |a, b| a ^ b)
    }
}

impl BitXor<BigInt> for &BigInt {
    type Output = BigInt;
    #[inline]
    fn bitxor(self, rhs: BigInt) -> BigInt {
        bigint_binop(self, &rhs, |a, b| a ^ b)
    }
}

// ---------------------------------------------------------------------------
// Not for BigInt  — !x = -(x) - 1
// ---------------------------------------------------------------------------

impl Not for BigInt {
    type Output = BigInt;

    fn not(self) -> BigInt {
        if self.is_negative() {
            // self = -m (m > 0); !self = m - 1 (= -(-m) - 1 = m - 1 >= 0)
            let m = self.magnitude().clone();
            let one = BigUint::one();
            match m.checked_sub(&one) {
                Some(result) => BigInt::from_parts(Sign::Positive, result),
                // m was 1 (i.e., self = -1), so m - 1 = 0.
                None => BigInt::zero(),
            }
        } else {
            // self >= 0; !self = -(self + 1) = -(self.mag + 1)
            let mag_plus_one = self.magnitude() + &BigUint::one();
            BigInt::from_parts(Sign::Negative, mag_plus_one)
        }
    }
}

impl Not for &BigInt {
    type Output = BigInt;

    #[inline]
    fn not(self) -> BigInt {
        self.clone().not()
    }
}

// ---------------------------------------------------------------------------
// Shl for BigInt — left shift: sign preserved, magnitude shifted left
// ---------------------------------------------------------------------------

impl Shl<u64> for BigInt {
    type Output = BigInt;

    fn shl(self, k: u64) -> BigInt {
        if self.is_zero() || k == 0 {
            return self;
        }
        let sign = self.sign();
        let shifted_mag = self.magnitude().shl_bits(k);
        BigInt::from_parts(sign, shifted_mag)
    }
}

impl Shl<u64> for &BigInt {
    type Output = BigInt;

    #[inline]
    fn shl(self, k: u64) -> BigInt {
        self.clone().shl(k)
    }
}

// ---------------------------------------------------------------------------
// Shr for BigInt — ARITHMETIC right shift (floor division by 2^k)
//
// For self >= 0: equivalent to BigUint shr (logical shift on magnitude).
// For self = -m (m > 0): floor(-m / 2^k) = -(((m - 1) >> k) + 1)
// ---------------------------------------------------------------------------

impl Shr<u64> for BigInt {
    type Output = BigInt;

    fn shr(self, k: u64) -> BigInt {
        if k == 0 {
            return self;
        }
        if self.is_negative() {
            let m = self.magnitude().clone();
            // (m - 1) >> k; if k >= bit_length(m - 1) the result is 0.
            let m_minus_one = m.checked_sub(&BigUint::one()).unwrap_or_else(BigUint::zero);
            let shifted = m_minus_one.shr_bits(k);
            // Result = -(shifted + 1)
            let mag = &shifted + &BigUint::one();
            BigInt::from_parts(Sign::Negative, mag)
        } else {
            // Non-negative: logical shift on magnitude.
            BigInt::from_parts(Sign::Positive, self.magnitude().shr_bits(k))
        }
    }
}

impl Shr<u64> for &BigInt {
    type Output = BigInt;

    #[inline]
    fn shr(self, k: u64) -> BigInt {
        self.clone().shr(k)
    }
}

// ---------------------------------------------------------------------------
// Internal unit tests
// ---------------------------------------------------------------------------

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

    fn bi(v: i64) -> BigInt {
        BigInt::from(v)
    }

    fn bu(v: u64) -> BigUint {
        BigUint::from_u64(v)
    }

    #[test]
    fn not_basic() {
        assert_eq!(!bi(0), bi(-1));
        assert_eq!(!bi(5), bi(-6));
        assert_eq!(!bi(-1), bi(0));
        assert_eq!(!bi(-6), bi(5));
    }

    #[test]
    fn not_double_negation() {
        for v in [-1000i64, -1, 0, 1, 1000] {
            let n = bi(v);
            assert_eq!(!!n.clone(), n, "!!n == n failed for {v}");
        }
    }

    #[test]
    fn and_neg_one_with_ff() {
        // -1 in two's complement has all bits 1; -1 & x == x.
        let neg1 = bi(-1);
        let ff = bi(0xFF);
        assert_eq!(&neg1 & &ff, ff);
    }

    #[test]
    fn or_neg_one_is_neg_one() {
        let neg1 = bi(-1);
        let ff = bi(0xFF);
        assert_eq!(&neg1 | &ff, neg1);
    }

    #[test]
    fn xor_self_is_zero() {
        let neg1 = bi(-1);
        assert_eq!(&neg1 ^ &neg1, BigInt::zero());
        let x = bi(-12345);
        assert_eq!(&x ^ &x, BigInt::zero());
    }

    #[test]
    fn shr_negative_floor_div() {
        assert_eq!(bi(-8) >> 1u64, bi(-4));
        assert_eq!(bi(-7) >> 1u64, bi(-4));
        assert_eq!(bi(-1) >> 1u64, bi(-1));
        assert_eq!(bi(-1) >> 100u64, bi(-1));
        assert_eq!(bi(7) >> 1u64, bi(3));
    }

    #[test]
    fn shl_signed() {
        assert_eq!(bi(1) << 4u64, bi(16));
        assert_eq!(bi(-1) << 4u64, bi(-16));
        assert_eq!(bi(0) << 100u64, BigInt::zero());
    }

    #[test]
    fn to_twos_complement_positive() {
        let n = bi(5);
        let tc = to_twos_complement(&n, 2);
        assert_eq!(tc, vec![5, 0]);
    }

    #[test]
    fn to_twos_complement_negative_one() {
        let n = bi(-1);
        let tc = to_twos_complement(&n, 2);
        // -1 in two's complement: all bits 1.
        assert_eq!(tc, vec![u64::MAX, u64::MAX]);
    }

    #[test]
    fn from_twos_complement_roundtrip() {
        for v in [-1i128, -2, -128, 0, 1, 127, 1000] {
            let n = BigInt::from(v);
            let tc = to_twos_complement(&n, 4);
            let back = from_twos_complement(&tc);
            assert_eq!(back, n, "roundtrip failed for {v}");
        }
    }

    #[test]
    fn de_morgan_and_to_or() {
        // !(a & b) == !a | !b
        let pairs: &[(i64, i64)] = &[
            (0, 0),
            (5, 3),
            (-5, 3),
            (5, -3),
            (-5, -3),
            (-1, 0xFF),
            (i64::MAX, i64::MIN),
        ];
        for &(av, bv) in pairs {
            let a = bi(av);
            let b = bi(bv);
            let lhs = !(&a & &b);
            let rhs = !a.clone() | !b.clone();
            assert_eq!(lhs, rhs, "De Morgan failed for ({av}, {bv})");
        }
    }

    #[test]
    fn de_morgan_or_to_and() {
        // !(a | b) == !a & !b
        let pairs: &[(i64, i64)] = &[(0, 0), (5, 3), (-5, 3), (5, -3), (-5, -3), (-1, 0xFF)];
        for &(av, bv) in pairs {
            let a = bi(av);
            let b = bi(bv);
            let lhs = !(&a | &b);
            let rhs = !a.clone() & !b.clone();
            assert_eq!(lhs, rhs, "De Morgan (or→and) failed for ({av}, {bv})");
        }
    }

    #[test]
    fn i128_cross_val_bitwise_and_shifts() {
        let vals: &[i128] = &[
            0,
            1,
            -1,
            127,
            -128,
            1000,
            -1000,
            i64::MAX as i128,
            i64::MIN as i128,
        ];
        for &i in vals {
            let a = BigInt::from(i);
            // NOT
            assert_eq!(!a.clone(), BigInt::from(!i), "!{i} mismatch");
            // Shifts with small non-negative j
            for j in 0i128..20 {
                let b = BigInt::from(j);
                assert_eq!(&a & &b, BigInt::from(i & j), "{i} & {j} mismatch");
                assert_eq!(&a | &b, BigInt::from(i | j), "{i} | {j} mismatch");
                assert_eq!(&a ^ &b, BigInt::from(i ^ j), "{i} ^ {j} mismatch");
                assert_eq!(
                    a.clone() >> (j as u64),
                    BigInt::from(i >> j),
                    "{i} >> {j} mismatch"
                );
            }
            for &j in vals {
                assert_eq!(
                    &a & &BigInt::from(j),
                    BigInt::from(i & j),
                    "{i} & {j} mismatch"
                );
                assert_eq!(
                    &a | &BigInt::from(j),
                    BigInt::from(i | j),
                    "{i} | {j} mismatch"
                );
                assert_eq!(
                    &a ^ &BigInt::from(j),
                    BigInt::from(i ^ j),
                    "{i} ^ {j} mismatch"
                );
            }
        }
    }

    #[test]
    fn xor_identity_and_complement() {
        // x ^ 0 == x
        for v in [-5i64, -1, 0, 1, 5] {
            let n = bi(v);
            assert_eq!(&n ^ &BigInt::zero(), n.clone());
            // x ^ x == 0
            assert_eq!(&n ^ &n, BigInt::zero());
            // x ^ -1 == !x  (since -1 is all-ones in two's complement)
            let all_ones = bi(-1);
            assert_eq!(&n ^ &all_ones, !n.clone());
        }
    }

    #[test]
    fn shr_positive_matches_biguint_shr() {
        let mag = BigUint::from_u64(1234567890);
        let n = BigInt::from_parts(Sign::Positive, mag.clone());
        for k in [0u64, 1, 7, 15, 31, 63, 64, 65] {
            let expected = BigInt::from_parts(Sign::Positive, mag.shr_bits(k));
            assert_eq!(n.clone() >> k, expected, "positive shr mismatch for k={k}");
        }
    }

    #[test]
    fn bu_unused() {
        // Ensure the bu() helper doesn't trigger unused-function warnings by
        // using it in at least one test.
        assert_eq!(bu(42), BigUint::from_u64(42));
    }
}