#![no_std]
#![deny(unsafe_code)]
pub mod montgomery;
pub mod simd;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[repr(C, align(32))]
pub struct U256(pub [u64; 4]);
impl U256 {
pub const ZERO: Self = U256([0, 0, 0, 0]);
pub const ONE: Self = U256([1, 0, 0, 0]);
#[inline(always)]
pub const fn from_limbs(limbs: [u64; 4]) -> Self {
U256(limbs)
}
#[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])
}
#[inline(always)]
pub fn wrapping_mul(&self, rhs: &Self) -> Self {
let a = self.0;
let b = rhs.0;
let mut res = [0u64; 4];
for i in 0..4 {
let mut carry: u64 = 0;
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;
}
}
U256(res)
}
#[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);
let (sub1, _) = self.0[3].overflowing_sub(rhs.0[3]);
let (sub2, _) = sub1.overflowing_sub(borrow);
result[3] = sub2;
U256(result)
}
}
#[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::*;
#[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);
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]);
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));
}
#[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]);
assert_eq!(a.wrapping_sub(&b), U256::from_limbs([u64::MAX, 0, 0, 0]));
}
#[test]
fn test_subtraction_underflow_wraps() {
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);
}
#[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]
fn test_multiplication_regression_mid_limb_carry() {
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);
assert_eq!(res, U256::from_limbs([0, 0, 0, 1]));
}
#[test]
fn test_multiplication_max_value_squared() {
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() {
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() {
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);
}
}