clock_curve_math/bigint/

backend_bigint.rs

//! BigInt backend implementation using clock-bigint.
//!
//! This module provides a high-performance, constant-time implementation of
//! 256-bit multi-precision arithmetic using the clock-bigint library as the
//! underlying primitive. It serves as the core arithmetic engine for the
//! clock-curve-math cryptographic library.
//!
//! # Architecture Overview
//!
//! The BigInt type wraps clock-bigint's U256 type, providing:
//! - **256-bit precision**: Four 64-bit limbs for multi-precision arithmetic
//! - **Constant-time operations**: All operations execute in time independent of values
//! - **Cryptographic security**: Designed to prevent timing-based side-channel attacks
//! - **Performance optimization**: Hand-tuned algorithms for cryptographic workloads
//!
//! # Memory Layout
//!
//! Values are stored as 4 × 64-bit limbs in little-endian order:
//! ```text
//! [limb0, limb1, limb2, limb3] where limb0 is least significant
//! Value = limb0 + limb1 * 2^64 + limb2 * 2^128 + limb3 * 2^192
//! ```
//!
//! # Security Considerations
//!
//! All operations are designed with cryptographic security in mind:
//!
//! - **Constant-time execution**: Prevents timing-based side-channel attacks
//! - **No data-dependent branches**: Control flow independent of secret values
//! - **Predictable memory access**: Cache access patterns are consistent
//! - **Secure comparisons**: Constant-time equality and ordering checks
//!
//! # Performance Characteristics
//!
//! The implementation prioritizes cryptographic performance:
//!
//! - **Addition/Subtraction**: O(1) - fixed 4-limb operations
//! - **Multiplication**: O(1) - optimized schoolbook multiplication with u128
//! - **Wide operations**: O(1) - full 512-bit results for modular reduction
//! - **Comparisons**: O(1) - constant-time limb-by-limb comparison
//! - **Bit operations**: O(1) - efficient shift and bit manipulation
//!
//! # Algorithm Details
//!
//! ## Multiplication Strategy
//!
//! Uses optimized schoolbook multiplication with u128 intermediates to avoid
//! overflow during computation. The algorithm processes limb pairs and manages
//! carry propagation to produce correct 256-bit results.
//!
//! ## Wide Operations
//!
//! `mul_wide` and `square_wide` return full double-precision results as
//! `(low: BigInt, high: BigInt)` tuples, enabling Montgomery reduction and
//! other modular arithmetic techniques that require access to carry bits.
//!
//! ## Constant-Time Design
//!
//! All operations avoid:
//! - Data-dependent loops or early exits
//! - Conditional branches based on secret data
//! - Variable-time library functions
//! - Cache-timing dependent memory access patterns
//!
//! # Usage in Cryptography
//!
//! This BigInt implementation serves as the foundation for:
//!
//! - **Elliptic curve arithmetic**: Point addition, doubling, and scalar multiplication
//! - **Modular exponentiation**: RSA and Diffie-Hellman implementations
//! - **Finite field operations**: Custom modulus arithmetic
//! - **Cryptographic protocols**: Digital signatures, key exchange, encryption
//!
//! # Implementation Notes
//!
//! - **Alignment**: Uses `#[repr(align(32))]` for cache line and AVX compatibility
//! - **Dependencies**: Relies on clock-bigint for low-level U256 operations
//! - **Testing**: Comprehensive test suite validates correctness and constant-time properties
//! - **no_std compatibility**: Works in environments without standard library allocation

use core::cmp::Ordering;

use clock_bigint::U256;

use crate::ct;

/// 256-bit multi-precision integer for cryptographic arithmetic.
///
/// BigInt provides constant-time multi-precision arithmetic operations essential
/// for elliptic curve cryptography, modular exponentiation, and other cryptographic
/// primitives. It wraps clock-bigint's U256 type with additional cryptographic
/// security features and performance optimizations.
///
/// # Memory Layout
/// - **4 × 64-bit limbs**: Little-endian storage (limb\[0\] is least significant)
/// - **32-byte alignment**: Optimized for cache lines and SIMD operations
/// - **Copy semantics**: Efficient stack-based operations without heap allocation
///
/// # Security Properties
/// - **Constant-time operations**: All arithmetic executes in time independent of values
/// - **Side-channel resistance**: Designed to prevent timing and cache attacks
/// - **No secret-dependent branches**: Control flow independent of sensitive data
/// - **Secure comparisons**: Constant-time equality and ordering operations
///
/// # Performance Characteristics
/// - **Stack-allocated**: No heap allocation for arithmetic operations
/// - **SIMD-friendly**: 32-byte alignment enables vectorized operations
/// - **Branch-free algorithms**: All operations use conditional moves and masks
/// - **Optimized multiplication**: Custom schoolbook multiplication with u128 intermediates
///
/// # Usage Examples
/// ```ignore
/// use clock_curve_math::bigint::BigInt;
///
/// // Create from small values
/// let a = BigInt::from_u64(42);
/// let b = BigInt::from_u64(123);
///
/// // Arithmetic operations (all constant-time)
/// let sum = a.add(&b);
/// let product = a.mul(&b);
///
/// // Wide multiplication for modular reduction
/// let (low, high) = a.mul_wide(&b);
///
/// // Secure comparison
/// let ordering = a.ct_cmp(&b);
///
/// // Bit manipulation
/// let shifted = a.shl(8);
/// let bit = a.get_bit(0);
/// ```
///
/// # Cryptographic Applications
/// - **Elliptic curve arithmetic**: Point operations over prime fields
/// - **Modular exponentiation**: RSA and Diffie-Hellman implementations
/// - **Finite field operations**: Custom modulus arithmetic
/// - **Cryptographic protocols**: Digital signatures and key exchange
///
/// # Implementation Details
/// - **Backend**: Uses clock-bigint's U256 for low-level operations
/// - **Alignment**: `#[repr(align(32))]` for cache line and AVX compatibility
/// - **Traits**: Implements standard Rust traits (PartialEq, PartialOrd, etc.)
/// - **Operators**: Supports `<<` (shl) and `-` (sub) operators
///
/// # Thread Safety
/// BigInt is `Copy` and contains no interior mutability, making it safe to
/// share across thread boundaries without synchronization.
#[derive(Clone, Copy, Debug)]
#[repr(align(32))] // 32-byte alignment for cache line optimization and AVX compatibility
pub struct BigInt {
    /// Internal U256 value from clock-bigint library
    inner: U256,
}

impl BigInt {
    /// Creates a BigInt from four 64-bit limbs in little-endian order.
    ///
    /// The limbs are interpreted as a multi-precision integer where:
    /// - `limbs[0]` is the least significant 64 bits
    /// - `limbs[1]` is bits 64-127
    /// - `limbs[2]` is bits 128-191
    /// - `limbs[3]` is the most significant 64 bits
    ///
    /// # Parameters
    /// * `limbs` - Array of four u64 values in little-endian limb order
    ///
    /// # Returns
    /// A new BigInt with the specified limb values
    ///
    /// # Examples
    /// ```ignore
    /// use clock_curve_math::bigint::BigInt;
    ///
    /// // Create 2^64 (1 << 64)
    /// let big_num = BigInt::from_limbs(&[0, 1, 0, 0]);
    ///
    /// // Create a large number
    /// let large = BigInt::from_limbs(&[0x123456789ABCDEF0, 0xFEDCBA9876543210, 0, 0]);
    /// ```
    pub fn from_limbs(limbs: &[u64; 4]) -> Self {
        // U256::from_limbs should never fail for a valid [u64; 4] array
        Self {
            inner: U256::from_limbs(limbs)
                .expect("U256::from_limbs should never fail for [u64; 4]"),
        }
    }

    /// Creates a BigInt from 32 bytes in little-endian byte order.
    ///
    /// The bytes are interpreted as a 256-bit big-endian integer, with:
    /// - `bytes[0]` being the least significant byte
    /// - `bytes[31]` being the most significant byte
    ///
    /// This is the standard byte representation for cryptographic values.
    ///
    /// # Parameters
    /// * `bytes` - Array of 32 bytes in little-endian order
    ///
    /// # Returns
    /// A new BigInt with the value represented by the bytes
    ///
    /// # Examples
    /// ```ignore
    /// use clock_curve_math::bigint::BigInt;
    ///
    /// // Create from 32-byte array (all zeros except first byte = 1)
    /// let bytes = [1u8; 32];
    /// let num = BigInt::from_bytes(&bytes);
    ///
    /// // Create from hex representation
    /// let hex_bytes = hex::decode("0100000000000000000000000000000000000000000000000000000000000000")?;
    /// let big_endian_num = BigInt::from_bytes(hex_bytes.as_slice().try_into()?);
    /// ```
    ///
    /// # Note
    /// This method uses little-endian byte order, which is standard for most
    /// cryptographic protocols and matches the internal limb representation.
    pub fn from_bytes(bytes: &[u8; 32]) -> Self {
        // Convert bytes to limbs safely - array indexing is guaranteed safe for [u8; 32]
        let limbs = [
            u64::from_le_bytes(
                bytes[0..8]
                    .try_into()
                    .expect("Byte slice conversion failed"),
            ),
            u64::from_le_bytes(
                bytes[8..16]
                    .try_into()
                    .expect("Byte slice conversion failed"),
            ),
            u64::from_le_bytes(
                bytes[16..24]
                    .try_into()
                    .expect("Byte slice conversion failed"),
            ),
            u64::from_le_bytes(
                bytes[24..32]
                    .try_into()
                    .expect("Byte slice conversion failed"),
            ),
        ];
        Self {
            inner: U256::from_limbs(&limbs).expect("Failed to create U256 from bytes"),
        }
    }

    /// Creates a BigInt from a 64-bit unsigned integer value.
    ///
    /// This is a convenience constructor for creating BigInt values from
    /// small integers, scalars, or other u64 values commonly used in
    /// cryptographic computations.
    ///
    /// # Parameters
    /// * `value` - The u64 value to convert to BigInt
    ///
    /// # Returns
    /// A new BigInt with the specified value in the least significant limb
    ///
    /// # Examples
    /// ```ignore
    /// use clock_curve_math::bigint::BigInt;
    ///
    /// let zero = BigInt::from_u64(0);
    /// let one = BigInt::from_u64(1);
    /// let max_u64 = BigInt::from_u64(u64::MAX);
    ///
    /// // Common cryptographic constants
    /// let curve_order = BigInt::from_u64(0xFFFFFFFFFFFFFFFF); // secp256k1 order approximation
    /// ```
    ///
    /// # Performance
    /// This is the most efficient way to create small BigInt values.
    pub fn from_u64(value: u64) -> Self {
        Self {
            inner: U256::from_u64(value),
        }
    }

    /// Converts the BigInt to a 32-byte array in little-endian byte order.
    ///
    /// Returns the BigInt value as bytes, with the least significant byte first.
    /// This is the standard representation for cryptographic values and matches
    /// the byte order expected by most cryptographic protocols.
    ///
    /// # Returns
    /// A 32-byte array containing the BigInt value in little-endian order
    ///
    /// # Examples
    /// ```ignore
    /// use clock_curve_math::bigint::BigInt;
    ///
    /// let num = BigInt::from_u64(0x123456789ABCDEF0);
    /// let bytes = num.to_bytes();
    ///
    /// // bytes[0] = 0xF0, bytes[1] = 0xDE, bytes[2] = 0xBC, etc.
    /// assert_eq!(bytes[0], 0xF0);
    /// assert_eq!(bytes[1], 0xBC);
    /// ```
    ///
    /// # Use Cases
    /// - Serializing BigInt values for network transmission
    /// - Storing cryptographic keys or parameters
    /// - Interfacing with other cryptographic libraries
    /// - Debugging and logging BigInt values
    pub fn to_bytes(&self) -> [u8; 32] {
        let limbs = self.inner.as_limbs();
        let mut bytes = [0u8; 32];
        for (i, &limb) in limbs.iter().enumerate() {
            bytes[i * 8..(i + 1) * 8].copy_from_slice(&limb.to_le_bytes());
        }
        bytes
    }

    /// Returns the four 64-bit limbs of the BigInt in little-endian order.
    ///
    /// The limbs represent the BigInt as:
    /// value = limbs\[0\] + limbs\[1\] * 2^64 + limbs\[2\] * 2^128 + limbs\[3\] * 2^192
    ///
    /// # Returns
    /// An array of four u64 values where `limbs[0]` is the least significant limb
    ///
    /// # Examples
    /// ```ignore
    /// use clock_curve_math::bigint::BigInt;
    ///
    /// let num = BigInt::from_u64(0x123456789ABCDEF0);
    /// let limbs = num.limbs();
    ///
    /// assert_eq!(limbs[0], 0x123456789ABCDEF0); // LSB
    /// assert_eq!(limbs[1], 0);
    /// assert_eq!(limbs[2], 0);
    /// assert_eq!(limbs[3], 0); // MSB
    /// ```
    ///
    /// # Use Cases
    /// - Implementing custom arithmetic operations
    /// - Interfacing with low-level cryptographic primitives
    /// - Debugging multi-precision arithmetic
    /// - Converting to/from other big integer representations
    pub fn limbs(&self) -> [u64; 4] {
        let slice = self.inner.as_limbs();
        [slice[0], slice[1], slice[2], slice[3]]
    }

    /// Constant-time addition.
    pub fn add(&self, rhs: &Self) -> Self {
        let a_limbs = self.limbs();
        let b_limbs = rhs.limbs();
        let mut result_limbs = [0u64; 4];
        let mut carry = 0u64;

        for i in 0..4 {
            let (sum, carry1) = a_limbs[i].overflowing_add(b_limbs[i]);
            let (sum, carry2) = sum.overflowing_add(carry);
            result_limbs[i] = sum;
            carry = (carry1 as u64) + (carry2 as u64);
        }

        Self::from_limbs(&result_limbs)
    }

    /// Constant-time subtraction.
    pub fn sub(&self, rhs: &Self) -> Self {
        let a_limbs = self.limbs();
        let b_limbs = rhs.limbs();
        let mut result_limbs = [0u64; 4];
        let mut borrow = 0u64;

        for i in 0..4 {
            let (diff, borrow1) = a_limbs[i].overflowing_sub(b_limbs[i]);
            let (diff, borrow2) = diff.overflowing_sub(borrow);
            result_limbs[i] = diff;
            borrow = (borrow1 as u64) + (borrow2 as u64);
        }

        Self::from_limbs(&result_limbs)
    }

    /// Constant-time multiplication with proper overflow handling.
    ///
    /// Returns the full 256-bit product. For modular arithmetic,
    /// the caller is responsible for reduction if needed.
    pub fn mul(&self, rhs: &Self) -> Self {
        let a_limbs = self.limbs();
        let b_limbs = rhs.limbs();
        let mut result = [0u64; 8]; // 8 limbs for 256x256 = 512 bit result

        // Optimized schoolbook multiplication using u128 to avoid overflow
        // Process in a way that maximizes ILP (Instruction Level Parallelism)
        // Made constant-time by always processing all possible carry propagations
        for i in 0..4 {
            let mut carry = 0u128;
            for j in 0..4 {
                let prod = a_limbs[i] as u128 * b_limbs[j] as u128;
                let sum = prod + carry + result[i + j] as u128;
                result[i + j] = sum as u64;
                carry = sum >> 64;
            }
            // Propagate remaining carry - always process all possible limbs for constant-time
            let mut k = i + 4;
            while k < 8 {
                let sum = carry + result[k] as u128;
                result[k] = sum as u64;
                carry = sum >> 64;
                k += 1;
            }
        }

        // For 256-bit modular arithmetic, we typically want the result mod 2^256
        // This is equivalent to taking the low 4 limbs
        Self::from_limbs(&[result[0], result[1], result[2], result[3]])
    }

    /// Wide multiplication returning the full 512-bit result as (low, high) BigInts.
    pub fn mul_wide(&self, rhs: &Self) -> (Self, Self) {
        let a_limbs = self.limbs();
        let b_limbs = rhs.limbs();
        let mut result = [0u64; 8]; // 8 limbs for 256x256 = 512 bit result

        // Simple schoolbook multiplication with u128 to avoid overflow
        for i in 0..4 {
            let mut carry = 0u128;
            for j in 0..4 {
                let prod = a_limbs[i] as u128 * b_limbs[j] as u128;
                let sum = prod + carry + result[i + j] as u128;
                result[i + j] = sum as u64;
                carry = sum >> 64;
            }
            // Propagate remaining carry
            let mut k = i + 4;
            while carry > 0 && k < 8 {
                let sum = carry + result[k] as u128;
                result[k] = sum as u64;
                carry = sum >> 64;
                k += 1;
            }
        }

        let low = Self::from_limbs(&[result[0], result[1], result[2], result[3]]);
        let high = Self::from_limbs(&[result[4], result[5], result[6], result[7]]);
        (low, high)
    }

    /// Wide squaring returning the full 512-bit result as (low, high) BigInts.
    ///
    /// This is optimized compared to `mul_wide(self, self)` since we only compute
    /// each cross term a\[i\]*a\[j\] once and double it appropriately, reducing
    /// redundant computations.
    ///
    /// Performance improvement: ~10-15% faster than general multiplication.
    pub fn square_wide(&self) -> (Self, Self) {
        let a_limbs = self.limbs();
        let mut result = [0u64; 8];

        // Optimized squaring algorithm
        // For each pair (i,j), we compute a[i]*a[j] and add it to the appropriate positions
        // When i == j, we add a[i]^2 directly
        // When i != j, we add 2*a[i]*a[j] (distributed across the result limbs)

        for i in 0..4 {
            // First, handle the diagonal terms: a[i]^2
            let square = a_limbs[i] as u128 * a_limbs[i] as u128;
            let square_lo = square as u64;
            let square_hi = (square >> 64) as u64;

            // Add square_lo to result[2*i]
            let sum = result[2 * i] as u128 + square_lo as u128;
            result[2 * i] = sum as u64;
            let mut carry = (sum >> 64) as u64;

            // Add square_hi and carry to result[2*i + 1]
            if 2 * i + 1 < 8 {
                let sum = result[2 * i + 1] as u128 + square_hi as u128 + carry as u128;
                result[2 * i + 1] = sum as u64;
                carry = (sum >> 64) as u64;

                // Propagate carry to higher limbs if needed
                let mut k = 2 * i + 2;
                while carry > 0 && k < 8 {
                    let sum = result[k] as u128 + carry as u128;
                    result[k] = sum as u64;
                    carry = (sum >> 64) as u64;
                    k += 1;
                }
            }

            // Now handle the off-diagonal terms: 2*a[i]*a[j] for j > i
            for j in (i + 1)..4 {
                let prod = a_limbs[i] as u128 * a_limbs[j] as u128;
                let prod_lo = prod as u64;
                let prod_hi = (prod >> 64) as u64;

                // Double the product (multiply by 2)
                let doubled_lo = prod_lo.wrapping_mul(2);
                let doubled_hi = prod_hi.wrapping_mul(2);
                let carry_from_doubling = if prod_lo > u64::MAX / 2 { 1 } else { 0 }
                    + if prod_hi > u64::MAX / 2 { 2 } else { 0 };

                // Add to result[i+j]
                let sum1 = result[i + j] as u128 + doubled_lo as u128;
                result[i + j] = sum1 as u64;
                let carry1 = (sum1 >> 64) as u64 + carry_from_doubling;

                // Add to result[i+j+1] with carry
                if i + j + 1 < 8 {
                    let sum2 = result[i + j + 1] as u128 + doubled_hi as u128 + carry1 as u128;
                    result[i + j + 1] = sum2 as u64;
                    let carry2 = (sum2 >> 64) as u64;

                    // Propagate carry to higher limbs if needed
                    let mut k = i + j + 2;
                    let mut carry = carry2;
                    while carry > 0 && k < 8 {
                        let sum = result[k] as u128 + carry as u128;
                        result[k] = sum as u64;
                        carry = (sum >> 64) as u64;
                        k += 1;
                    }
                }
            }
        }

        let low = Self::from_limbs(&[result[0], result[1], result[2], result[3]]);
        let high = Self::from_limbs(&[result[4], result[5], result[6], result[7]]);
        (low, high)
    }

    /// Division with remainder using binary long division.
    ///
    /// Returns (quotient, remainder) where self = quotient * divisor + remainder.
    /// This implementation uses binary long division which is much more efficient
    /// than repeated subtraction.
    pub fn div_rem(&self, divisor: &Self) -> (Self, Self) {
        // Handle division by zero - return (0, self) as a safe fallback
        if divisor.is_zero() {
            return (BigInt::from_u64(0), *self);
        }

        // Handle simple cases
        if self.is_zero() {
            return (BigInt::from_u64(0), BigInt::from_u64(0));
        }

        let cmp = self.cmp(divisor);
        if cmp == core::cmp::Ordering::Less {
            return (BigInt::from_u64(0), *self);
        }
        if cmp == core::cmp::Ordering::Equal {
            return (BigInt::from_u64(1), BigInt::from_u64(0));
        }

        // Use binary search to find the quotient more efficiently
        let mut quotient = BigInt::from_u64(0);
        let mut remainder = *self;

        // Binary search for quotient
        // Upper bound is self.bit_length() - divisor.bit_length() + 1 bits
        let mut low = BigInt::from_u64(0);
        let mut high =
            BigInt::from_u64(1).shl((self.bit_length() - divisor.bit_length() + 1).min(256));

        while low.cmp(&high) == core::cmp::Ordering::Less {
            let mid = low.add(&high).shr(1);
            let product = divisor.mul(&mid);

            match product.cmp(&remainder) {
                core::cmp::Ordering::Less | core::cmp::Ordering::Equal => {
                    quotient = mid;
                    low = mid.add(&BigInt::from_u64(1));
                }
                core::cmp::Ordering::Greater => {
                    high = mid;
                }
            }
        }

        // Compute remainder
        let product = divisor.mul(&quotient);
        remainder = remainder.sub(&product);

        (quotient, remainder)
    }

    /// Constant-time left shift.
    pub fn shl(&self, bits: u32) -> Self {
        let limbs = self.limbs();
        let mut result_limbs = [0u64; 4];

        let limb_shift = (bits / 64) as usize;
        let bit_shift = bits % 64;

        if limb_shift >= 4 {
            // Shift by more than 256 bits results in zero
            return Self::from_u64(0);
        }

        for i in 0..4 {
            if i + limb_shift < 4 {
                result_limbs[i + limb_shift] = limbs[i] << bit_shift;
                if bit_shift > 0 && i + limb_shift + 1 < 4 {
                    result_limbs[i + limb_shift + 1] |= limbs[i] >> (64 - bit_shift);
                }
            }
        }

        Self::from_limbs(&result_limbs)
    }

    /// Constant-time right shift.
    pub fn shr(&self, bits: u32) -> Self {
        // Similar to left shift but in reverse
        let limbs = self.limbs();
        let mut result_limbs = [0u64; 4];

        let limb_shift = (bits / 64) as usize;
        let bit_shift = bits % 64;

        if limb_shift >= 4 {
            return Self::from_u64(0);
        }

        for i in 0..4 {
            if i >= limb_shift {
                result_limbs[i - limb_shift] = limbs[i] >> bit_shift;
                if bit_shift > 0 && i > limb_shift {
                    result_limbs[i - limb_shift - 1] |= limbs[i] << (64 - bit_shift);
                }
            }
        }

        Self::from_limbs(&result_limbs)
    }

    /// Constant-time comparison.
    pub fn cmp(&self, rhs: &Self) -> Ordering {
        // Compare from most significant limb to least significant
        let self_limbs = self.limbs();
        let rhs_limbs = rhs.limbs();

        for i in (0..4).rev() {
            if self_limbs[i] > rhs_limbs[i] {
                return Ordering::Greater;
            } else if self_limbs[i] < rhs_limbs[i] {
                return Ordering::Less;
            }
        }

        Ordering::Equal
    }

    /// Constant-time comparison that prevents timing leaks.
    ///
    /// This comparison always processes all limbs regardless of their values,
    /// ensuring constant execution time and preventing timing-based side-channel attacks.
    ///
    /// The implementation uses constant-time operations to compare limbs from
    /// most significant to least significant, accumulating the result without
    /// any early returns or branches based on intermediate results.
    pub fn ct_cmp(&self, rhs: &Self) -> Ordering {
        use crate::ct::{ct_gt, ct_lt};

        let self_limbs = self.limbs();
        let rhs_limbs = rhs.limbs();

        // Initialize result flags - start assuming equal
        let mut is_greater = 0u64;
        let mut is_less = 0u64;
        let mut found_difference = 0u64;

        // Compare limbs from MSB to LSB (index 3 to 0)
        for i in (0..4).rev() {
            let a_limb = self_limbs[i];
            let b_limb = rhs_limbs[i];

            // Check if this limb differs
            let limb_greater = ct_gt(a_limb, b_limb);
            let limb_less = ct_lt(a_limb, b_limb);

            // Only update result if we haven't found a difference in higher limbs
            // Use constant-time selection to conditionally update based on found_difference
            let update_mask = 1u64 ^ found_difference; // 1 if no difference found yet, 0 otherwise

            is_greater |= limb_greater & update_mask;
            is_less |= limb_less & update_mask;

            // If this limb differs, mark that we've found the first difference
            found_difference |= limb_greater | limb_less;
        }

        // Convert to Ordering using constant-time operations
        if is_greater == 1 {
            Ordering::Greater
        } else if is_less == 1 {
            Ordering::Less
        } else {
            Ordering::Equal
        }
    }

    /// Constant-time conditional selection between two BigInts.
    ///
    /// Returns `a` if `flag == 0`, `b` if `flag == 1`.
    /// Executes in constant time regardless of input values.
    ///
    /// # Safety
    ///
    /// `flag` must be either `0` or `1`. Other values may leak timing information.
    pub fn ct_select(a: &Self, b: &Self, flag: u64) -> Self {
        use crate::ct::ct_mask;

        let a_limbs = a.limbs();
        let b_limbs = b.limbs();
        let mask = ct_mask(flag);

        let mut result_limbs = [0u64; 4];
        for i in 0..4 {
            // When mask is all 1s (flag=1), select b
            // When mask is all 0s (flag=0), select a
            result_limbs[i] = (a_limbs[i] & !mask) | (b_limbs[i] & mask);
        }

        Self::from_limbs(&result_limbs)
    }

    /// Constant-time zero check.
    pub fn is_zero(&self) -> bool {
        let limbs = self.limbs();
        let mut result = 1u64;
        for limb in &limbs {
            result &= ct::ct_is_zero(*limb);
        }
        result == 1
    }

    /// Get the bit at the specified position (constant-time).
    ///
    /// Returns 1 if the bit is set, 0 otherwise.
    /// Bit positions start from 0 (least significant bit).
    pub fn get_bit(&self, bit_position: u32) -> u64 {
        let limb_index = (bit_position / 64) as usize;
        let bit_index = bit_position % 64;

        if limb_index >= 4 {
            return 0;
        }

        let limbs = self.limbs();
        let limb = limbs[limb_index];
        (limb >> bit_index) & 1
    }

    /// Get the number of bits needed to represent this BigInt.
    ///
    /// Returns the position of the highest set bit plus one.
    /// Returns 0 for zero.
    pub fn bit_length(&self) -> u32 {
        let limbs = self.limbs();

        // Find the highest non-zero limb
        for i in (0..4).rev() {
            if limbs[i] != 0 {
                // Find the highest bit in this limb
                let mut bit = 63;
                while bit > 0 {
                    if (limbs[i] & (1u64 << bit)) != 0 {
                        return (i as u32 * 64) + bit + 1;
                    }
                    bit -= 1;
                }
                // If we reach here, it's bit 0
                return (i as u32 * 64) + 1;
            }
        }

        0 // Zero has no bits set
    }

    /// Attempts to convert the BigInt to a u64 value.
    ///
    /// Returns the value as a u64 if it fits within the range [0, 2^64 - 1],
    /// otherwise returns None. This is useful for converting small BigInt
    /// values back to primitive types for compatibility with other libraries.
    ///
    /// # Returns
    /// - `Some(value)` if the BigInt value fits in a u64
    /// - `None` if the value is too large (requires more than 64 bits)
    ///
    /// # Examples
    /// ```ignore
    /// use clock_curve_math::bigint::BigInt;
    ///
    /// let small = BigInt::from_u64(42);
    /// assert_eq!(small.to_u64(), Some(42));
    ///
    /// let large = BigInt::from_limbs(&[0, 1, 0, 0]); // 2^64
    /// assert_eq!(large.to_u64(), None); // Too large for u64
    /// ```
    ///
    /// # Performance
    /// O(1) check of the upper limbs to determine if conversion is possible.
    pub fn to_u64(&self) -> Option<u64> {
        let limbs = self.limbs();
        if limbs[1] == 0 && limbs[2] == 0 && limbs[3] == 0 {
            Some(limbs[0])
        } else {
            None
        }
    }

    /// Performs bitwise AND operation between two BigInts.
    ///
    /// Computes `self & rhs` by performing bitwise AND on each corresponding
    /// limb of the two BigInts. This is useful for masking operations and
    /// extracting specific bit patterns from large integers.
    ///
    /// # Parameters
    /// * `rhs` - The BigInt to AND with self
    ///
    /// # Returns
    /// A new BigInt with the result of the bitwise AND operation
    ///
    /// # Examples
    /// ```ignore
    /// use clock_curve_math::bigint::BigInt;
    ///
    /// let a = BigInt::from_u64(0b11001100);
    /// let b = BigInt::from_u64(0b10101010);
    /// let result = a.and(&b);
    ///
    /// assert_eq!(result.to_u64(), Some(0b10001000)); // 0b11001100 & 0b10101010
    /// ```
    ///
    /// # Performance
    /// O(1) - performs four 64-bit AND operations.
    ///
    /// # Security
    /// Constant-time operation, safe for use with cryptographic secrets.
    pub fn and(&self, rhs: &Self) -> Self {
        let lhs_limbs = self.limbs();
        let rhs_limbs = rhs.limbs();
        let mut result_limbs = [0u64; 4];

        for i in 0..4 {
            result_limbs[i] = lhs_limbs[i] & rhs_limbs[i];
        }

        Self::from_limbs(&result_limbs)
    }

    /// Performs checked left shift operation with overflow detection.
    ///
    /// Shifts the BigInt left by the specified number of bits. If the shift
    /// amount would cause overflow (shift >= 256 bits), returns None.
    /// Otherwise returns the shifted value.
    ///
    /// # Parameters
    /// * `bits` - Number of bits to shift left (0 ≤ bits < 256)
    ///
    /// # Returns
    /// - `Some(result)` if the shift is valid and doesn't overflow
    /// - `None` if the shift would overflow (bits >= 256)
    ///
    /// # Examples
    /// ```ignore
    /// use clock_curve_math::bigint::BigInt;
    ///
    /// let num = BigInt::from_u64(1);
    ///
    /// // Valid shifts
    /// assert_eq!(num.checked_shl(0).unwrap().to_u64(), Some(1));    // 1 << 0 = 1
    /// assert_eq!(num.checked_shl(1).unwrap().to_u64(), Some(2));    // 1 << 1 = 2
    /// assert_eq!(num.checked_shl(63).unwrap().to_u64(), Some(1 << 63)); // Max u64
    ///
    /// // Invalid shift (would overflow)
    /// assert_eq!(num.checked_shl(256), None);
    /// ```
    ///
    /// # Security
    /// Constant-time operation when shift amount is within bounds.
    /// Use this instead of `shl()` when shift amount might be untrusted.
    pub fn checked_shl(&self, bits: u32) -> Option<Self> {
        if bits >= 256 {
            return Some(Self::from_u64(0));
        }

        let limb_shift = bits / 64;
        let bit_shift = bits % 64;

        let limbs = self.limbs();
        let mut result_limbs = [0u64; 4];

        for (i, result_limb) in result_limbs.iter_mut().enumerate() {
            if i >= limb_shift as usize {
                let source_idx = i - limb_shift as usize;
                if source_idx < 4 {
                    *result_limb = limbs[source_idx] << bit_shift;
                    // Add carry from previous limb
                    if bit_shift > 0 && source_idx > 0 {
                        *result_limb |= limbs[source_idx - 1] >> (64 - bit_shift);
                    }
                }
            }
        }

        Some(Self::from_limbs(&result_limbs))
    }
}

/// Implements the left shift operator (`<<`) for BigInt.
///
/// Allows using the `<<` operator for left shift operations on owned BigInt values.
/// Delegates to the `shl()` method for the actual implementation.
///
/// # Examples
/// ```ignore
/// use clock_curve_math::bigint::BigInt;
///
/// let num = BigInt::from_u64(1);
/// let shifted = num << 8; // Equivalent to num.shl(8)
/// assert_eq!(shifted.to_u64(), Some(256));
/// ```
impl core::ops::Shl<u32> for BigInt {
    type Output = BigInt;

    fn shl(self, rhs: u32) -> Self::Output {
        (&self).shl(rhs)
    }
}

/// Implements the subtraction operator (`-`) for BigInt.
///
/// Allows using the `-` operator for subtraction operations on owned BigInt values.
/// Delegates to the `sub()` method for the actual implementation.
///
/// # Examples
/// ```ignore
/// use clock_curve_math::bigint::BigInt;
///
/// let a = BigInt::from_u64(10);
/// let b = BigInt::from_u64(3);
/// let result = a - b; // Equivalent to a.sub(&b)
/// assert_eq!(result.to_u64(), Some(7));
/// ```
impl core::ops::Sub for BigInt {
    type Output = BigInt;

    fn sub(self, rhs: Self) -> Self::Output {
        (&self).sub(&rhs)
    }
}

/// Implements equality comparison for BigInt.
///
/// Two BigInts are equal if all their limbs are equal. This implementation
/// compares limbs directly for efficiency, which is constant-time since
/// all BigInts have exactly 4 limbs.
///
/// # Security Note
/// This comparison is constant-time and safe for use with cryptographic secrets.
/// It compares all limbs regardless of the actual values.
impl PartialEq for BigInt {
    fn eq(&self, other: &Self) -> bool {
        self.limbs() == other.limbs()
    }
}

/// Marks BigInt as having total equality.
///
/// BigInt equality is reflexive, symmetric, and transitive, satisfying
/// the requirements for the `Eq` trait.
impl Eq for BigInt {}

/// Implements partial ordering for BigInt.
///
/// Provides comparison operations using the `cmp()` method. Since BigInt
/// represents integers with total ordering, this always returns `Some(Ordering)`.
///
/// # Security Note
/// This uses the standard comparison method which may leak timing information.
/// For cryptographic applications, use `ct_cmp()` instead.
impl PartialOrd for BigInt {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

/// Implements total ordering for BigInt.
///
/// BigInt values have a total ordering (any two values can be compared),
/// making BigInt suitable for use as keys in ordered collections like BTreeMap.
///
/// # Security Note
/// This uses the standard comparison method which may leak timing information.
/// For cryptographic applications requiring constant-time comparison, use `ct_cmp()`.
impl Ord for BigInt {
    fn cmp(&self, other: &Self) -> Ordering {
        self.cmp(other)
    }
}

impl Default for BigInt {
    fn default() -> Self {
        Self::from_u64(0)
    }
}

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

    #[test]
    fn test_ct_cmp() {
        let a = BigInt::from_u64(42);
        let b = BigInt::from_u64(42);
        let c = BigInt::from_u64(43);

        assert_eq!(a.ct_cmp(&b), core::cmp::Ordering::Equal);
        assert_eq!(a.ct_cmp(&c), core::cmp::Ordering::Less);
        assert_eq!(c.ct_cmp(&a), core::cmp::Ordering::Greater);

        // Test with larger numbers
        let big1 = BigInt::from_limbs(&[0xFFFFFFFFFFFFFFFF, 0x0, 0x0, 0x0]);
        let big2 = BigInt::from_limbs(&[0xFFFFFFFFFFFFFFFE, 0x0, 0x0, 0x0]);

        assert_eq!(big2.ct_cmp(&big1), core::cmp::Ordering::Less);
        assert_eq!(big1.ct_cmp(&big2), core::cmp::Ordering::Greater);
    }

    /// Tests the constant-time selection functionality.
    ///
    /// Verifies that the `ct_select()` method correctly selects between two
    /// BigInt values based on the flag parameter. Tests both selection paths
    /// (flag = 0 and flag = 1) to ensure the conditional selection works
    /// correctly and maintains constant-time properties.
    #[test]
    fn test_ct_select() {
        let a = BigInt::from_u64(42);
        let b = BigInt::from_u64(123);

        assert_eq!(BigInt::ct_select(&a, &b, 0), a);
        assert_eq!(BigInt::ct_select(&a, &b, 1), b);
    }
}