Skip to main content

hyper_u256/
lib.rs

1#![no_std]
2#![deny(unsafe_code)]
3//! # hyper-u256
4//!
5//! Bibliothèque `no_std`, zéro allocation, pour l'arithmétique sur des
6//! entiers non signés 256 bits (`U256`).
7//!
8//! Toutes les opérations sont **wrapping** (arithmétique modulaire mod 2²⁵⁶),
9//! déterministes et n'utilisent aucune branche dépendant des données
10//! sensibles (utile en contexte cryptographique).
11
12pub mod montgomery;
13pub mod simd;
14
15/// Entier 256-bit non signé représenté sur 4 mots de 64-bit (Little-Endian).
16///
17/// `self.0[0]` contient les bits `0..64`, `self.0[3]` contient les bits
18/// `192..256`.
19///
20/// Aligné sur 32 octets pour maximiser l'efficacité du cache et des
21/// registres AVX/SIMD du CPU.
22#[derive(Debug, Clone, Copy, PartialEq, Eq)]
23#[repr(C, align(32))]
24pub struct U256(pub [u64; 4]);
25
26impl U256 {
27    /// Constante Zéro.
28    pub const ZERO: Self = U256([0, 0, 0, 0]);
29
30    /// Constante Un.
31    pub const ONE: Self = U256([1, 0, 0, 0]);
32
33    /// Création à partir de 4 mots u64 (Little-Endian : `limbs[0]` = bits
34    /// de poids faible).
35    #[inline(always)]
36    pub const fn from_limbs(limbs: [u64; 4]) -> Self {
37        U256(limbs)
38    }
39
40    /// Addition 256-bit déterministe avec propagation de la retenue (Overflow).
41    ///
42    /// Le résultat est tronqué mod 2²⁵⁶ (sémantique "wrapping" standard) :
43    /// tout débordement au-delà du 4ème mot est silencieusement abandonné.
44    ///
45    /// Utilise `overflowing_add` sous le capot pour une traduction directe
46    /// en instructions ASM CPU (ADC).
47    #[inline(always)]
48    pub fn wrapping_add(&self, rhs: &Self) -> Self {
49        let (r0, c0) = self.0[0].overflowing_add(rhs.0[0]);
50        let (r1, c1) = carrying_add(self.0[1], rhs.0[1], c0);
51        let (r2, c2) = carrying_add(self.0[2], rhs.0[2], c1);
52        let (r3, _) = carrying_add(self.0[3], rhs.0[3], c2);
53
54        U256([r0, r1, r2, r3])
55    }
56
57    /// Multiplication 256-bit x 256-bit -> 256-bit (tronquée mod 2²⁵⁶).
58    ///
59    /// Implémentation "schoolbook" (Comba), colonne par colonne, avec
60    /// propagation complète de la retenue à *chaque* produit partiel.
61    /// Zéro allocation, zéro mémoire heap, 100% dans les registres CPU.
62    ///
63    /// Toute contribution qui dépasserait le bit 255 (c'est-à-dire les
64    /// produits partiels `a[i] * b[j]` avec `i + j >= 4`, ainsi que la
65    /// retenue finale de la dernière colonne) est abandonnée, conformément
66    /// à la sémantique "wrapping" (résultat mod 2²⁵⁶).
67    #[inline(always)]
68    pub fn wrapping_mul(&self, rhs: &Self) -> Self {
69        let a = self.0;
70        let b = rhs.0;
71        let mut res = [0u64; 4];
72
73        // Boucle externe déroulée par le compilateur (4 itérations fixes).
74        for i in 0..4 {
75            let mut carry: u64 = 0;
76            // On ne calcule que les colonnes idx = i + j < 4 : au-delà,
77            // la contribution vaut au moins 2^256 et sort du résultat.
78            for j in 0..(4 - i) {
79                let idx = i + j;
80                let prod = (a[i] as u128) * (b[j] as u128)
81                    + (res[idx] as u128)
82                    + (carry as u128);
83                res[idx] = prod as u64;
84                carry = (prod >> 64) as u64;
85            }
86            // Le `carry` restant après j = 3-i correspondrait à une
87            // contribution au-delà du bit 255 : abandonné intentionnellement
88            // (résultat "wrapping" mod 2^256).
89        }
90
91        U256(res)
92    }
93
94    /// Soustraction 256-bit déterministe avec propagation de l'emprunt (Borrow).
95    ///
96    /// Le résultat est tronqué mod 2²⁵⁶ : si `rhs > self`, le résultat
97    /// "boucle" (comportement identique à `u64::wrapping_sub`).
98    #[inline(always)]
99    pub fn wrapping_sub(&self, rhs: &Self) -> Self {
100        let mut result = [0u64; 4];
101        let mut borrow = 0u64;
102
103        macro_rules! sub_step {
104            ($i:expr) => {
105                let (sub1, b1) = self.0[$i].overflowing_sub(rhs.0[$i]);
106                let (sub2, b2) = sub1.overflowing_sub(borrow);
107                result[$i] = sub2;
108                borrow = (b1 as u64) + (b2 as u64);
109            };
110        }
111
112        sub_step!(0);
113        sub_step!(1);
114        sub_step!(2);
115
116        // Dernier mot : pas besoin de mettre à jour `borrow`, il ne sera
117        // plus utilisé (résultat wrapping, l'emprunt final est abandonné).
118        let (sub1, _) = self.0[3].overflowing_sub(rhs.0[3]);
119        let (sub2, _) = sub1.overflowing_sub(borrow);
120        result[3] = sub2;
121
122        U256(result)
123    }
124}
125
126// Helper inline pour addition avec retenue sans branchement (Branchless).
127#[inline(always)]
128fn carrying_add(a: u64, b: u64, carry: bool) -> (u64, bool) {
129    let (sum1, c1) = a.overflowing_add(b);
130    let (sum2, c2) = sum1.overflowing_add(carry as u64);
131    (sum2, c1 | c2)
132}
133
134#[cfg(test)]
135mod tests {
136    use super::*;
137
138    // ---------------------------------------------------------------
139    // Addition
140    // ---------------------------------------------------------------
141
142    #[test]
143    fn test_addition_simple() {
144        let a = U256::from_limbs([1, 0, 0, 0]);
145        let b = U256::from_limbs([2, 0, 0, 0]);
146        assert_eq!(a.wrapping_add(&b), U256::from_limbs([3, 0, 0, 0]));
147    }
148
149    #[test]
150    fn test_addition_carry_single_limb() {
151        let a = U256::from_limbs([u64::MAX, 0, 0, 0]);
152        let b = U256::from_limbs([1, 0, 0, 0]);
153        let res = a.wrapping_add(&b);
154
155        // Doit faire un overflow propre du 1er limb vers le 2ème limb.
156        assert_eq!(res, U256::from_limbs([0, 1, 0, 0]));
157    }
158
159    #[test]
160    fn test_addition_carry_propagates_through_all_limbs() {
161        let a = U256::from_limbs([u64::MAX, u64::MAX, u64::MAX, u64::MAX]);
162        let b = U256::from_limbs([1, 0, 0, 0]);
163        // 2^256 - 1 + 1 = 2^256 -> wrap à 0.
164        assert_eq!(a.wrapping_add(&b), U256::ZERO);
165    }
166
167    #[test]
168    fn test_addition_is_commutative() {
169        let a = U256::from_limbs([0x1111, 0x2222, 0x3333, 0x4444]);
170        let b = U256::from_limbs([0xAAAA, 0xBBBB, 0xCCCC, 0xDDDD]);
171        assert_eq!(a.wrapping_add(&b), b.wrapping_add(&a));
172    }
173
174    // ---------------------------------------------------------------
175    // Soustraction
176    // ---------------------------------------------------------------
177
178    #[test]
179    fn test_subtraction_simple() {
180        let a = U256::from_limbs([5, 0, 0, 0]);
181        let b = U256::from_limbs([3, 0, 0, 0]);
182        assert_eq!(a.wrapping_sub(&b), U256::from_limbs([2, 0, 0, 0]));
183    }
184
185    #[test]
186    fn test_subtraction_with_borrow_single_limb() {
187        let a = U256::from_limbs([0, 1, 0, 0]);
188        let b = U256::from_limbs([1, 0, 0, 0]);
189        // 2^64 - 1 = 0xFFFF...FFFF sur le premier limb, 0 sur le second.
190        assert_eq!(a.wrapping_sub(&b), U256::from_limbs([u64::MAX, 0, 0, 0]));
191    }
192
193    #[test]
194    fn test_subtraction_underflow_wraps() {
195        // 0 - 1 = 2^256 - 1 (tous les limbs à MAX).
196        let a = U256::ZERO;
197        let b = U256::ONE;
198        assert_eq!(
199            a.wrapping_sub(&b),
200            U256::from_limbs([u64::MAX, u64::MAX, u64::MAX, u64::MAX])
201        );
202    }
203
204    #[test]
205    fn test_subtraction_is_inverse_of_addition() {
206        let a = U256::from_limbs([0x1111, 0x2222, 0x3333, 0x4444]);
207        let b = U256::from_limbs([0xAAAA, 0xBBBB, 0xCCCC, 0xDDDD]);
208        let sum = a.wrapping_add(&b);
209        assert_eq!(sum.wrapping_sub(&b), a);
210    }
211
212    // ---------------------------------------------------------------
213    // Multiplication
214    // ---------------------------------------------------------------
215
216    #[test]
217    fn test_multiplication_simple() {
218        let a = U256::from_limbs([10, 0, 0, 0]);
219        let b = U256::from_limbs([5, 0, 0, 0]);
220        assert_eq!(a.wrapping_mul(&b), U256::from_limbs([50, 0, 0, 0]));
221    }
222
223    #[test]
224    fn test_multiplication_by_zero() {
225        let a = U256::from_limbs([0x1111, 0x2222, 0x3333, 0x4444]);
226        assert_eq!(a.wrapping_mul(&U256::ZERO), U256::ZERO);
227    }
228
229    #[test]
230    fn test_multiplication_identity() {
231        let a = U256::from_limbs([0x1111, 0x2222, 0x3333, 0x4444]);
232        assert_eq!(a.wrapping_mul(&U256::ONE), a);
233    }
234
235    /// Test de non-régression : ce cas précis (2^96 * 2^96 = 2^192)
236    /// faisait échouer une ancienne implémentation qui perdait les
237    /// retenues (carries) des produits partiels de poids fort, sans
238    /// jamais paniquer ni signaler d'erreur — le résultat était juste
239    /// silencieusement faux ([0,0,0,0] au lieu de 2^192).
240    #[test]
241    fn test_multiplication_regression_mid_limb_carry() {
242        let a = U256::from_limbs([0, 1u64 << 32, 0, 0]); // 2^96
243        let b = U256::from_limbs([0, 1u64 << 32, 0, 0]); // 2^96
244        let res = a.wrapping_mul(&b);
245        // 2^96 * 2^96 = 2^192 -> le bit 192 est le bit de poids faible du
246        // 4ème mot (limb[3] couvre les bits 192..256), donc limb[3] = 1.
247        assert_eq!(res, U256::from_limbs([0, 0, 0, 1]));
248    }
249
250    #[test]
251    fn test_multiplication_max_value_squared() {
252        // (2^64 - 1)^2 = 2^128 - 2^65 + 1
253        let a = U256::from_limbs([u64::MAX, 0, 0, 0]);
254        let res = a.wrapping_mul(&a);
255        assert_eq!(res, U256::from_limbs([1, 0xFFFFFFFFFFFFFFFE, 0, 0]));
256    }
257
258    #[test]
259    fn test_multiplication_full_width_values() {
260        // Valeurs vérifiées indépendamment (arithmétique 256-bit exacte,
261        // résultat tronqué mod 2^256).
262        let a = U256::from_limbs([
263            0x5555666677778888,
264            0x1111222233334444,
265            0xFEDCBA9876543210,
266            0x0123456789ABCDEF,
267        ]);
268        let b = U256::from_limbs([
269            0x1111111111111111,
270            0x9999888877776666,
271            0x0123456789ABCDEF,
272            0x9876543210ABCDEF,
273        ]);
274        let expected = U256::from_limbs([
275            0xE93E92C5F8091908,
276            0xCA8641FDBA98789A,
277            0x2D351AED596DD7A5,
278            0x26F6071A6E3217E5,
279        ]);
280        assert_eq!(a.wrapping_mul(&b), expected);
281    }
282
283    #[test]
284    fn test_multiplication_is_commutative() {
285        let a = U256::from_limbs([0x5555666677778888, 0x1111222233334444, 0xFEDCBA9876543210, 0x0123456789ABCDEF]);
286        let b = U256::from_limbs([0x1111111111111111, 0x9999888877776666, 0x0123456789ABCDEF, 0x9876543210ABCDEF]);
287        assert_eq!(a.wrapping_mul(&b), b.wrapping_mul(&a));
288    }
289
290    #[test]
291    fn test_multiplication_overflow_wraps_mod_2_256() {
292        // 2^255 * 2 = 2^256 -> wrap à 0.
293        let a = U256::from_limbs([0, 0, 0, 1u64 << 63]);
294        let b = U256::from_limbs([2, 0, 0, 0]);
295        assert_eq!(a.wrapping_mul(&b), U256::ZERO);
296    }
297}