clock_bigint/

limbs.rs

//! Limb manipulation utilities for BigInt operations.
//!
//! A limb is a 64-bit unsigned integer. All multi-limb integers use
//! little-endian limb ordering.

use crate::ct;

/// Limb type (64-bit unsigned integer).
pub type Limb = u64;

/// Wide limb type (128-bit for multiplication results).
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct WideLimb {
    /// Low 64 bits.
    pub lo: Limb,
    /// High 64 bits.
    pub hi: Limb,
}

impl WideLimb {
    /// Create a new WideLimb from low and high parts.
    #[inline(always)]
    pub const fn new(lo: Limb, hi: Limb) -> Self {
        Self { lo, hi }
    }
}

/// Add two limbs with carry, returning (sum, carry_out).
///
/// This is the constant-time `adc` (add with carry) operation.
/// `carry_in` should be 0 or 1.
#[inline(always)]
pub fn limb_add_carry(a: Limb, b: Limb, carry_in: Limb) -> (Limb, Limb) {
    let carry_in = carry_in & 1; // Ensure it's 0 or 1
    let sum = a.wrapping_add(b).wrapping_add(carry_in);

    // Constant-time carry calculation:
    // carry_out = (sum < a) OR ((carry_in == 1) AND (sum == a))
    let carry1 = ct::ct_lt(sum, a);
    let carry2 = (carry_in & ct::ct_eq(sum, a)) & 1;
    let carry_out = carry1 | carry2;

    (sum, carry_out)
}

/// Subtract two limbs with borrow, returning (difference, borrow_out).
///
/// This is the constant-time `sbb` (subtract with borrow) operation.
/// `borrow_in` should be 0 or 1.
#[inline(always)]
pub fn limb_sub_borrow(a: Limb, b: Limb, borrow_in: Limb) -> (Limb, Limb) {
    let borrow_in = borrow_in & 1; // Ensure it's 0 or 1
    let diff = a.wrapping_sub(b).wrapping_sub(borrow_in);

    // Constant-time borrow calculation:
    // borrow_out = (a < b) OR ((borrow_in == 1) AND (a == b))
    let borrow1 = ct::ct_lt(a, b);
    let borrow2 = (borrow_in & ct::ct_eq(a, b)) & 1;
    let borrow_out = borrow1 | borrow2;

    (diff, borrow_out)
}

/// Multiply two limbs, returning a 128-bit wide result.
///
/// This performs 64×64→128 bit multiplication.
#[inline(always)]
pub fn limb_mul_wide(a: Limb, b: Limb) -> WideLimb {
    // Use the standard Rust 128-bit multiplication
    let result = (a as u128) * (b as u128);
    WideLimb {
        lo: result as u64,
        hi: (result >> 64) as u64,
    }
}

/// Multiply-accumulate: compute (x + y + carry) returning (sum, carry_out).
///
/// This is used in multiplication algorithms.
#[inline(always)]
pub fn limb_mac(x: Limb, y: Limb, carry: Limb) -> (Limb, Limb) {
    limb_add_carry(x, y, carry)
}

/// Normalize a limb slice by removing leading zeros.
///
/// Returns the number of non-zero limbs (at least 1, even if all are zero).
/// This operation is constant-time aware but may not be fully constant-time
/// due to the need to find the actual length.
pub fn normalize(limbs: &mut [Limb]) -> usize {
    let mut len = limbs.len();

    // Find the first non-zero limb from the end (most significant)
    // We iterate in constant-time fashion but still need to return the actual length
    while len > 1 && limbs[len - 1] == 0 {
        len -= 1;
    }

    len
}

/// Canonicalize a limb slice according to the specification.
///
/// Enforces:
/// 1. Zero: exactly one limb with value 0
/// 2. No leading zeros for nonzero values
/// 3. Minimal length
///
/// Returns the canonical length.
pub fn canonicalize(limbs: &mut [Limb]) -> usize {
    let normalized_len = normalize(limbs);

    // If all limbs are zero, ensure exactly one zero limb
    if normalized_len == 1 && limbs[0] == 0 {
        return 1;
    }

    normalized_len
}

/// Check if a limb slice represents zero.
#[inline(always)]
pub fn is_zero(limbs: &[Limb]) -> bool {
    limbs.iter().all(|&x| x == 0)
}

/// Compare two limb slices in constant time.
///
/// Returns:
/// - 0 if a == b
/// - 1 if a > b
/// - 2 if a < b (encoded as u64 for constant-time)
///
/// Both slices must have the same length.
pub fn ct_compare(a: &[Limb], b: &[Limb]) -> u64 {
    debug_assert_eq!(a.len(), b.len());

    let mut gt = 0u64;
    let mut eq = 1u64;

    // Compare from most significant to least significant
    for i in (0..a.len()).rev() {
        let a_gt_b = ct::ct_gt(a[i], b[i]);
        let a_eq_b = ct::ct_eq(a[i], b[i]);

        // Update gt: if we haven't found a difference yet (eq == 1),
        // and current limb makes a > b, then set gt
        gt = ct::ct_select(eq, a_gt_b, gt);
        eq &= a_eq_b;
    }

    // Return: 0 if equal, 1 if a > b, 2 if a < b
    let lt = eq ^ 1; // 0 if equal, 1 if not equal
    let lt = lt & !gt; // 1 only if a < b

    (lt << 1) | gt
}

#[cfg(all(test, feature = "alloc"))]
mod tests {
    #[cfg(feature = "alloc")]
    use alloc::vec;
    use super::*;

    #[test]
    fn test_limb_add_carry() {
        let (sum, carry) = limb_add_carry(10, 20, 0);
        assert_eq!(sum, 30);
        assert_eq!(carry, 0);

        let (sum, carry) = limb_add_carry(u64::MAX, 1, 0);
        assert_eq!(sum, 0);
        assert_eq!(carry, 1);

        let (sum, carry) = limb_add_carry(u64::MAX, 0, 1);
        assert_eq!(sum, 0);
        assert_eq!(carry, 1);
    }

    #[test]
    fn test_limb_sub_borrow() {
        let (diff, borrow) = limb_sub_borrow(20, 10, 0);
        assert_eq!(diff, 10);
        assert_eq!(borrow, 0);

        let (_diff, borrow) = limb_sub_borrow(10, 20, 0);
        assert_eq!(borrow, 1);

        let (_diff, borrow) = limb_sub_borrow(0, 0, 1);
        assert_eq!(borrow, 1);
    }

    #[test]
    fn test_limb_mul_wide() {
        let result = limb_mul_wide(0xFFFFFFFFFFFFFFFF, 2);
        assert_eq!(result.lo, 0xFFFFFFFFFFFFFFFE);
        assert_eq!(result.hi, 1);

        let result = limb_mul_wide(1 << 32, 1 << 32);
        assert_eq!(result.lo, 0);
        assert_eq!(result.hi, 1);
    }

    #[test]
    fn test_normalize() {
        let mut limbs = vec![1, 0, 0, 0];
        assert_eq!(normalize(&mut limbs), 1);

        let mut limbs = vec![1, 2, 0, 0];
        assert_eq!(normalize(&mut limbs), 2);

        let mut limbs = vec![0, 0, 0, 0];
        assert_eq!(normalize(&mut limbs), 1);
    }

    #[test]
    fn test_is_zero() {
        assert!(is_zero(&[0, 0, 0]));
        assert!(!is_zero(&[1, 0, 0]));
        assert!(!is_zero(&[0, 1, 0]));
    }
}