1#![no_std]
2#![deny(unsafe_code)]
3pub mod montgomery;
13pub mod simd;
14
15#[derive(Debug, Clone, Copy, PartialEq, Eq)]
23#[repr(C, align(32))]
24pub struct U256(pub [u64; 4]);
25
26impl U256 {
27 pub const ZERO: Self = U256([0, 0, 0, 0]);
29
30 pub const ONE: Self = U256([1, 0, 0, 0]);
32
33 #[inline(always)]
36 pub const fn from_limbs(limbs: [u64; 4]) -> Self {
37 U256(limbs)
38 }
39
40 #[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 #[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 for i in 0..4 {
75 let mut carry: u64 = 0;
76 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 }
90
91 U256(res)
92 }
93
94 #[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 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#[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 #[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 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 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 #[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 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 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 #[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]
241 fn test_multiplication_regression_mid_limb_carry() {
242 let a = U256::from_limbs([0, 1u64 << 32, 0, 0]); let b = U256::from_limbs([0, 1u64 << 32, 0, 0]); let res = a.wrapping_mul(&b);
245 assert_eq!(res, U256::from_limbs([0, 0, 0, 1]));
248 }
249
250 #[test]
251 fn test_multiplication_max_value_squared() {
252 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 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 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}