clock_curve_math/bigint/

backend_bigint.rs

//! BigInt backend using clock-bigint.

use core::cmp::Ordering;

use clock_bigint::U256;

use crate::ct;

/// BigInt wrapper around clock-bigint's U256.
#[derive(Clone, Copy, Debug)]
pub struct BigInt {
    inner: U256,
}

impl BigInt {
    /// Create a BigInt from u64 limbs (little-endian).
    pub fn from_limbs(limbs: &[u64; 4]) -> Self {
        Self {
            inner: U256::from_limbs(limbs).unwrap(),
        }
    }

    /// Create a BigInt from bytes (little-endian).
    pub fn from_bytes(bytes: &[u8; 32]) -> Self {
        Self {
            inner: U256::from_limbs(&[
                u64::from_le_bytes(bytes[0..8].try_into().unwrap()),
                u64::from_le_bytes(bytes[8..16].try_into().unwrap()),
                u64::from_le_bytes(bytes[16..24].try_into().unwrap()),
                u64::from_le_bytes(bytes[24..32].try_into().unwrap()),
            ])
            .unwrap(),
        }
    }

    /// Create a BigInt from a u64 value.
    pub fn from_u64(value: u64) -> Self {
        Self {
            inner: U256::from_u64(value),
        }
    }

    /// Convert to little-endian bytes.
    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
    }

    /// Get the limbs (little-endian).
    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)
        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;
            }
        }

        // 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)
    }

    /// 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
        if divisor.is_zero() {
            panic!("Division by zero");
        }

        // 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 {
        // For now, use a simple implementation - clock-bigint may have shift functions
        // This is a placeholder
        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 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) as u64
    }

    /// 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
    }
}

impl PartialEq for BigInt {
    fn eq(&self, other: &Self) -> bool {
        self.limbs() == other.limbs()
    }
}

impl Eq for BigInt {}

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