hyper-u256 0.1.0

Arithmétique 256-bit ultra-rapide en no_std avec optimisation SIMD et zéro allocation pour les corps finis et la cryptographie.
Documentation
#![no_std]
#![deny(unsafe_code)]
//! # hyper-u256
//!
//! Bibliothèque `no_std`, zéro allocation, pour l'arithmétique sur des
//! entiers non signés 256 bits (`U256`).
//!
//! Toutes les opérations sont **wrapping** (arithmétique modulaire mod 2²⁵⁶),
//! déterministes et n'utilisent aucune branche dépendant des données
//! sensibles (utile en contexte cryptographique).

pub mod montgomery;
pub mod simd;

/// Entier 256-bit non signé représenté sur 4 mots de 64-bit (Little-Endian).
///
/// `self.0[0]` contient les bits `0..64`, `self.0[3]` contient les bits
/// `192..256`.
///
/// Aligné sur 32 octets pour maximiser l'efficacité du cache et des
/// registres AVX/SIMD du CPU.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[repr(C, align(32))]
pub struct U256(pub [u64; 4]);

impl U256 {
    /// Constante Zéro.
    pub const ZERO: Self = U256([0, 0, 0, 0]);

    /// Constante Un.
    pub const ONE: Self = U256([1, 0, 0, 0]);

    /// Création à partir de 4 mots u64 (Little-Endian : `limbs[0]` = bits
    /// de poids faible).
    #[inline(always)]
    pub const fn from_limbs(limbs: [u64; 4]) -> Self {
        U256(limbs)
    }

    /// Addition 256-bit déterministe avec propagation de la retenue (Overflow).
    ///
    /// Le résultat est tronqué mod 2²⁵⁶ (sémantique "wrapping" standard) :
    /// tout débordement au-delà du 4ème mot est silencieusement abandonné.
    ///
    /// Utilise `overflowing_add` sous le capot pour une traduction directe
    /// en instructions ASM CPU (ADC).
    #[inline(always)]
    pub fn wrapping_add(&self, rhs: &Self) -> Self {
        let (r0, c0) = self.0[0].overflowing_add(rhs.0[0]);
        let (r1, c1) = carrying_add(self.0[1], rhs.0[1], c0);
        let (r2, c2) = carrying_add(self.0[2], rhs.0[2], c1);
        let (r3, _) = carrying_add(self.0[3], rhs.0[3], c2);

        U256([r0, r1, r2, r3])
    }

    /// Multiplication 256-bit x 256-bit -> 256-bit (tronquée mod 2²⁵⁶).
    ///
    /// Implémentation "schoolbook" (Comba), colonne par colonne, avec
    /// propagation complète de la retenue à *chaque* produit partiel.
    /// Zéro allocation, zéro mémoire heap, 100% dans les registres CPU.
    ///
    /// Toute contribution qui dépasserait le bit 255 (c'est-à-dire les
    /// produits partiels `a[i] * b[j]` avec `i + j >= 4`, ainsi que la
    /// retenue finale de la dernière colonne) est abandonnée, conformément
    /// à la sémantique "wrapping" (résultat mod 2²⁵⁶).
    #[inline(always)]
    pub fn wrapping_mul(&self, rhs: &Self) -> Self {
        let a = self.0;
        let b = rhs.0;
        let mut res = [0u64; 4];

        // Boucle externe déroulée par le compilateur (4 itérations fixes).
        for i in 0..4 {
            let mut carry: u64 = 0;
            // On ne calcule que les colonnes idx = i + j < 4 : au-delà,
            // la contribution vaut au moins 2^256 et sort du résultat.
            for j in 0..(4 - i) {
                let idx = i + j;
                let prod = (a[i] as u128) * (b[j] as u128)
                    + (res[idx] as u128)
                    + (carry as u128);
                res[idx] = prod as u64;
                carry = (prod >> 64) as u64;
            }
            // Le `carry` restant après j = 3-i correspondrait à une
            // contribution au-delà du bit 255 : abandonné intentionnellement
            // (résultat "wrapping" mod 2^256).
        }

        U256(res)
    }

    /// Soustraction 256-bit déterministe avec propagation de l'emprunt (Borrow).
    ///
    /// Le résultat est tronqué mod 2²⁵⁶ : si `rhs > self`, le résultat
    /// "boucle" (comportement identique à `u64::wrapping_sub`).
    #[inline(always)]
    pub fn wrapping_sub(&self, rhs: &Self) -> Self {
        let mut result = [0u64; 4];
        let mut borrow = 0u64;

        macro_rules! sub_step {
            ($i:expr) => {
                let (sub1, b1) = self.0[$i].overflowing_sub(rhs.0[$i]);
                let (sub2, b2) = sub1.overflowing_sub(borrow);
                result[$i] = sub2;
                borrow = (b1 as u64) + (b2 as u64);
            };
        }

        sub_step!(0);
        sub_step!(1);
        sub_step!(2);

        // Dernier mot : pas besoin de mettre à jour `borrow`, il ne sera
        // plus utilisé (résultat wrapping, l'emprunt final est abandonné).
        let (sub1, _) = self.0[3].overflowing_sub(rhs.0[3]);
        let (sub2, _) = sub1.overflowing_sub(borrow);
        result[3] = sub2;

        U256(result)
    }
}

// Helper inline pour addition avec retenue sans branchement (Branchless).
#[inline(always)]
fn carrying_add(a: u64, b: u64, carry: bool) -> (u64, bool) {
    let (sum1, c1) = a.overflowing_add(b);
    let (sum2, c2) = sum1.overflowing_add(carry as u64);
    (sum2, c1 | c2)
}

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

    // ---------------------------------------------------------------
    // Addition
    // ---------------------------------------------------------------

    #[test]
    fn test_addition_simple() {
        let a = U256::from_limbs([1, 0, 0, 0]);
        let b = U256::from_limbs([2, 0, 0, 0]);
        assert_eq!(a.wrapping_add(&b), U256::from_limbs([3, 0, 0, 0]));
    }

    #[test]
    fn test_addition_carry_single_limb() {
        let a = U256::from_limbs([u64::MAX, 0, 0, 0]);
        let b = U256::from_limbs([1, 0, 0, 0]);
        let res = a.wrapping_add(&b);

        // Doit faire un overflow propre du 1er limb vers le 2ème limb.
        assert_eq!(res, U256::from_limbs([0, 1, 0, 0]));
    }

    #[test]
    fn test_addition_carry_propagates_through_all_limbs() {
        let a = U256::from_limbs([u64::MAX, u64::MAX, u64::MAX, u64::MAX]);
        let b = U256::from_limbs([1, 0, 0, 0]);
        // 2^256 - 1 + 1 = 2^256 -> wrap à 0.
        assert_eq!(a.wrapping_add(&b), U256::ZERO);
    }

    #[test]
    fn test_addition_is_commutative() {
        let a = U256::from_limbs([0x1111, 0x2222, 0x3333, 0x4444]);
        let b = U256::from_limbs([0xAAAA, 0xBBBB, 0xCCCC, 0xDDDD]);
        assert_eq!(a.wrapping_add(&b), b.wrapping_add(&a));
    }

    // ---------------------------------------------------------------
    // Soustraction
    // ---------------------------------------------------------------

    #[test]
    fn test_subtraction_simple() {
        let a = U256::from_limbs([5, 0, 0, 0]);
        let b = U256::from_limbs([3, 0, 0, 0]);
        assert_eq!(a.wrapping_sub(&b), U256::from_limbs([2, 0, 0, 0]));
    }

    #[test]
    fn test_subtraction_with_borrow_single_limb() {
        let a = U256::from_limbs([0, 1, 0, 0]);
        let b = U256::from_limbs([1, 0, 0, 0]);
        // 2^64 - 1 = 0xFFFF...FFFF sur le premier limb, 0 sur le second.
        assert_eq!(a.wrapping_sub(&b), U256::from_limbs([u64::MAX, 0, 0, 0]));
    }

    #[test]
    fn test_subtraction_underflow_wraps() {
        // 0 - 1 = 2^256 - 1 (tous les limbs à MAX).
        let a = U256::ZERO;
        let b = U256::ONE;
        assert_eq!(
            a.wrapping_sub(&b),
            U256::from_limbs([u64::MAX, u64::MAX, u64::MAX, u64::MAX])
        );
    }

    #[test]
    fn test_subtraction_is_inverse_of_addition() {
        let a = U256::from_limbs([0x1111, 0x2222, 0x3333, 0x4444]);
        let b = U256::from_limbs([0xAAAA, 0xBBBB, 0xCCCC, 0xDDDD]);
        let sum = a.wrapping_add(&b);
        assert_eq!(sum.wrapping_sub(&b), a);
    }

    // ---------------------------------------------------------------
    // Multiplication
    // ---------------------------------------------------------------

    #[test]
    fn test_multiplication_simple() {
        let a = U256::from_limbs([10, 0, 0, 0]);
        let b = U256::from_limbs([5, 0, 0, 0]);
        assert_eq!(a.wrapping_mul(&b), U256::from_limbs([50, 0, 0, 0]));
    }

    #[test]
    fn test_multiplication_by_zero() {
        let a = U256::from_limbs([0x1111, 0x2222, 0x3333, 0x4444]);
        assert_eq!(a.wrapping_mul(&U256::ZERO), U256::ZERO);
    }

    #[test]
    fn test_multiplication_identity() {
        let a = U256::from_limbs([0x1111, 0x2222, 0x3333, 0x4444]);
        assert_eq!(a.wrapping_mul(&U256::ONE), a);
    }

    /// Test de non-régression : ce cas précis (2^96 * 2^96 = 2^192)
    /// faisait échouer une ancienne implémentation qui perdait les
    /// retenues (carries) des produits partiels de poids fort, sans
    /// jamais paniquer ni signaler d'erreur — le résultat était juste
    /// silencieusement faux ([0,0,0,0] au lieu de 2^192).
    #[test]
    fn test_multiplication_regression_mid_limb_carry() {
        let a = U256::from_limbs([0, 1u64 << 32, 0, 0]); // 2^96
        let b = U256::from_limbs([0, 1u64 << 32, 0, 0]); // 2^96
        let res = a.wrapping_mul(&b);
        // 2^96 * 2^96 = 2^192 -> le bit 192 est le bit de poids faible du
        // 4ème mot (limb[3] couvre les bits 192..256), donc limb[3] = 1.
        assert_eq!(res, U256::from_limbs([0, 0, 0, 1]));
    }

    #[test]
    fn test_multiplication_max_value_squared() {
        // (2^64 - 1)^2 = 2^128 - 2^65 + 1
        let a = U256::from_limbs([u64::MAX, 0, 0, 0]);
        let res = a.wrapping_mul(&a);
        assert_eq!(res, U256::from_limbs([1, 0xFFFFFFFFFFFFFFFE, 0, 0]));
    }

    #[test]
    fn test_multiplication_full_width_values() {
        // Valeurs vérifiées indépendamment (arithmétique 256-bit exacte,
        // résultat tronqué mod 2^256).
        let a = U256::from_limbs([
            0x5555666677778888,
            0x1111222233334444,
            0xFEDCBA9876543210,
            0x0123456789ABCDEF,
        ]);
        let b = U256::from_limbs([
            0x1111111111111111,
            0x9999888877776666,
            0x0123456789ABCDEF,
            0x9876543210ABCDEF,
        ]);
        let expected = U256::from_limbs([
            0xE93E92C5F8091908,
            0xCA8641FDBA98789A,
            0x2D351AED596DD7A5,
            0x26F6071A6E3217E5,
        ]);
        assert_eq!(a.wrapping_mul(&b), expected);
    }

    #[test]
    fn test_multiplication_is_commutative() {
        let a = U256::from_limbs([0x5555666677778888, 0x1111222233334444, 0xFEDCBA9876543210, 0x0123456789ABCDEF]);
        let b = U256::from_limbs([0x1111111111111111, 0x9999888877776666, 0x0123456789ABCDEF, 0x9876543210ABCDEF]);
        assert_eq!(a.wrapping_mul(&b), b.wrapping_mul(&a));
    }

    #[test]
    fn test_multiplication_overflow_wraps_mod_2_256() {
        // 2^255 * 2 = 2^256 -> wrap à 0.
        let a = U256::from_limbs([0, 0, 0, 1u64 << 63]);
        let b = U256::from_limbs([2, 0, 0, 0]);
        assert_eq!(a.wrapping_mul(&b), U256::ZERO);
    }
}