openzeppelin_crypto/arithmetic/
limb.rs

1//! This module contains low-level arithmetic functions for
2//! big integer's limbs.
3
4// Actually cast truncations are a part of the logic here.
5#![allow(clippy::cast_possible_truncation, clippy::cast_lossless)]
6
7use num_traits::ConstOne;
8
9/// A single limb of a big integer represented by 64-bits.
10pub type Limb = u64;
11
12/// Array of [`Limb`]s.
13pub type Limbs<const N: usize> = [Limb; N];
14
15/// A wide limb represented by 128-bits.
16///
17/// Twice larger than [`Limb`].
18pub type WideLimb = u128;
19
20/// Multiply two [`Limb`]'s and return widened result.
21#[inline(always)]
22#[must_use]
23pub const fn widening_mul(a: Limb, b: Limb) -> WideLimb {
24    #[cfg(not(target_family = "wasm"))]
25    {
26        a as WideLimb * b as WideLimb
27    }
28    #[cfg(target_family = "wasm")]
29    {
30        widening_mul_wasm(a, b)
31    }
32}
33
34/// Multiply two [`Limb`]'s and return widened result.
35///
36/// This function is optimized for wasm target, due to inefficiency of
37/// 128-bit multiplication in WebAssembly.
38#[inline(always)]
39#[doc(hidden)]
40#[allow(dead_code)]
41const fn widening_mul_wasm(a: Limb, b: Limb) -> WideLimb {
42    let a_lo = a as u32 as Limb;
43    let a_hi = a >> 32;
44    let b_lo = b as u32 as Limb;
45    let b_hi = b >> 32;
46
47    let lolo = (a_lo * b_lo) as WideLimb;
48    let lohi = ((a_lo * b_hi) as WideLimb) << 32;
49    let hilo = ((a_hi * b_lo) as WideLimb) << 32;
50    let hihi = ((a_hi * b_hi) as WideLimb) << 64;
51    (lolo | hihi) + (lohi + hilo)
52}
53
54/// Calculate `a + b * c`, returning the lower 64 bits of the result and setting
55/// `carry` to the upper 64 bits.
56#[inline(always)]
57#[must_use]
58pub const fn mac(a: Limb, b: Limb, c: Limb) -> (Limb, Limb) {
59    let a = a as WideLimb;
60    let tmp = a + widening_mul(b, c);
61    let carry = (tmp >> Limb::BITS) as Limb;
62    (tmp as Limb, carry)
63}
64
65/// Calculate `a + (b * c) + carry`, returning the least significant digit
66/// and setting carry to the most significant digit.
67#[inline(always)]
68#[must_use]
69pub const fn carrying_mac(
70    a: Limb,
71    b: Limb,
72    c: Limb,
73    carry: Limb,
74) -> (Limb, Limb) {
75    let a = a as WideLimb;
76    let carry = carry as WideLimb;
77    let tmp = a + widening_mul(b, c) + carry;
78    let carry = (tmp >> Limb::BITS) as Limb;
79    (tmp as Limb, carry)
80}
81
82/// Calculate `a = a + b + carry` and return the result and carry.
83#[inline(always)]
84#[must_use]
85pub const fn adc(a: Limb, b: Limb, carry: bool) -> (Limb, bool) {
86    let a = a as WideLimb;
87    let b = b as WideLimb;
88    let carry = carry as WideLimb;
89    let tmp = a + b + carry;
90    let carry = (tmp >> Limb::BITS) != 0;
91    (tmp as Limb, carry)
92}
93
94/// Sets a = a + b + carry, and returns the new carry.
95#[inline(always)]
96pub fn adc_assign(a: &mut Limb, b: Limb, carry: bool) -> bool {
97    let tmp = *a as WideLimb + b as WideLimb + carry as WideLimb;
98    *a = tmp as Limb;
99    let carry = tmp >> Limb::BITS;
100    carry != 0
101}
102
103/// Calculate `a = a - b - borrow` and return the result and borrow.
104#[inline(always)]
105#[must_use]
106pub const fn sbb(a: Limb, b: Limb, borrow: bool) -> (Limb, bool) {
107    let a = a as WideLimb;
108    let b = b as WideLimb;
109    let borrow = borrow as WideLimb;
110    // Protects from overflow, when `a < b + borrow`.
111    let overflow_protection = WideLimb::ONE << Limb::BITS;
112    let tmp = overflow_protection + a - b - borrow;
113    let borrow = tmp >> Limb::BITS == 0;
114    // overflow_protection will be truncated on cast.
115    (tmp as Limb, borrow)
116}
117
118/// Sets a = a - b - borrow, and returns the borrow.
119#[inline(always)]
120pub fn sbb_assign(a: &mut Limb, b: Limb, borrow: bool) -> bool {
121    let (sub, borrow1) = a.overflowing_sub(b);
122    let (sub, borrow2) = sub.overflowing_sub(borrow as Limb);
123    *a = sub;
124    borrow1 | borrow2
125}
126
127#[cfg(test)]
128mod tests {
129    use proptest::prelude::*;
130
131    use super::*;
132
133    #[test]
134    fn check_widening_mul() {
135        proptest!(|(a: Limb, b: Limb)|{
136            let std_mul_result = widening_mul(a, b);
137            let wasm_mul_result = widening_mul_wasm(a, b);
138            prop_assert_eq!(std_mul_result, wasm_mul_result);
139        });
140    }
141}
openzeppelin_crypto/arithmetic/limb.rs

openzeppelin_crypto/arithmetic/
limb.rs
