ark_ff/biginteger/
arithmetic.rs

1use ark_std::{vec, vec::Vec};
2
3macro_rules! adc {
4    ($a:expr, $b:expr, &mut $carry:expr$(,)?) => {{
5        let tmp = ($a as u128) + ($b as u128) + ($carry as u128);
6        $carry = (tmp >> 64) as u64;
7        tmp as u64
8    }};
9}
10
11/// Sets a = a + b + carry, and returns the new carry.
12#[inline(always)]
13#[allow(unused_mut)]
14#[doc(hidden)]
15pub fn adc(a: &mut u64, b: u64, carry: u64) -> u64 {
16    let tmp = *a as u128 + b as u128 + carry as u128;
17    *a = tmp as u64;
18    (tmp >> 64) as u64
19}
20
21/// Sets a = a + b + carry, and returns the new carry.
22#[inline(always)]
23#[allow(unused_mut)]
24#[doc(hidden)]
25pub fn adc_for_add_with_carry(a: &mut u64, b: u64, carry: u8) -> u8 {
26    #[cfg(all(target_arch = "x86_64", feature = "asm"))]
27    #[allow(unsafe_code)]
28    unsafe {
29        use core::arch::x86_64::_addcarry_u64;
30        _addcarry_u64(carry, *a, b, a)
31    }
32    #[cfg(not(all(target_arch = "x86_64", feature = "asm")))]
33    {
34        let tmp = *a as u128 + b as u128 + carry as u128;
35        *a = tmp as u64;
36        (tmp >> 64) as u8
37    }
38}
39
40/// Calculate a + b + carry, returning the sum
41#[inline(always)]
42#[doc(hidden)]
43pub fn adc_no_carry(a: u64, b: u64, carry: &mut u64) -> u64 {
44    let tmp = a as u128 + b as u128 + *carry as u128;
45    tmp as u64
46}
47
48#[macro_export]
49macro_rules! sbb {
50    ($a:expr, $b:expr, &mut $borrow:expr$(,)?) => {{
51        let tmp = (1u128 << 64) + ($a as u128) - ($b as u128) - ($borrow as u128);
52        $borrow = if tmp >> 64 == 0 { 1 } else { 0 };
53        tmp as u64
54    }};
55}
56
57/// Sets a = a - b - borrow, and returns the borrow.
58#[inline(always)]
59#[allow(unused_mut)]
60pub(crate) fn sbb(a: &mut u64, b: u64, borrow: u64) -> u64 {
61    let tmp = (1u128 << 64) + (*a as u128) - (b as u128) - (borrow as u128);
62    *a = tmp as u64;
63    (tmp >> 64 == 0) as u64
64}
65
66/// Sets a = a - b - borrow, and returns the borrow.
67#[inline(always)]
68#[allow(unused_mut)]
69#[doc(hidden)]
70pub fn sbb_for_sub_with_borrow(a: &mut u64, b: u64, borrow: u8) -> u8 {
71    #[cfg(all(target_arch = "x86_64", feature = "asm"))]
72    #[allow(unsafe_code)]
73    unsafe {
74        use core::arch::x86_64::_subborrow_u64;
75        _subborrow_u64(borrow, *a, b, a)
76    }
77    #[cfg(not(all(target_arch = "x86_64", feature = "asm")))]
78    {
79        let tmp = (1u128 << 64) + (*a as u128) - (b as u128) - (borrow as u128);
80        *a = tmp as u64;
81        u8::from(tmp >> 64 == 0)
82    }
83}
84
85/// Calculate a + b * c, returning the lower 64 bits of the result and setting
86/// `carry` to the upper 64 bits.
87#[inline(always)]
88#[doc(hidden)]
89pub fn mac(a: u64, b: u64, c: u64, carry: &mut u64) -> u64 {
90    let tmp = (a as u128) + (b as u128 * c as u128);
91    *carry = (tmp >> 64) as u64;
92    tmp as u64
93}
94
95/// Calculate a + b * c, discarding the lower 64 bits of the result and setting
96/// `carry` to the upper 64 bits.
97#[inline(always)]
98#[doc(hidden)]
99pub fn mac_discard(a: u64, b: u64, c: u64, carry: &mut u64) {
100    let tmp = (a as u128) + (b as u128 * c as u128);
101    *carry = (tmp >> 64) as u64;
102}
103
104macro_rules! mac_with_carry {
105    ($a:expr, $b:expr, $c:expr, &mut $carry:expr$(,)?) => {{
106        let tmp = ($a as u128) + ($b as u128 * $c as u128) + ($carry as u128);
107        $carry = (tmp >> 64) as u64;
108        tmp as u64
109    }};
110}
111
112macro_rules! mac {
113    ($a:expr, $b:expr, $c:expr, &mut $carry:expr$(,)?) => {{
114        let tmp = ($a as u128) + ($b as u128 * $c as u128);
115        $carry = (tmp >> 64) as u64;
116        tmp as u64
117    }};
118}
119
120/// Calculate a + (b * c) + carry, returning the least significant digit
121/// and setting carry to the most significant digit.
122#[inline(always)]
123#[doc(hidden)]
124pub fn mac_with_carry(a: u64, b: u64, c: u64, carry: &mut u64) -> u64 {
125    let tmp = (a as u128) + (b as u128 * c as u128) + (*carry as u128);
126    *carry = (tmp >> 64) as u64;
127    tmp as u64
128}
129
130/// Compute the NAF (non-adjacent form) of num
131pub fn find_naf(num: &[u64]) -> Vec<i8> {
132    let is_zero = |num: &[u64]| num.iter().all(|x| *x == 0u64);
133    let is_odd = |num: &[u64]| num[0] & 1 == 1;
134    let sub_noborrow = |num: &mut [u64], z: u64| {
135        let mut other = vec![0u64; num.len()];
136        other[0] = z;
137        let mut borrow = 0;
138
139        for (a, b) in num.iter_mut().zip(other) {
140            borrow = sbb(a, b, borrow);
141        }
142    };
143    let add_nocarry = |num: &mut [u64], z: u64| {
144        let mut other = vec![0u64; num.len()];
145        other[0] = z;
146        let mut carry = 0;
147
148        for (a, b) in num.iter_mut().zip(other) {
149            carry = adc(a, b, carry);
150        }
151    };
152    let div2 = |num: &mut [u64]| {
153        let mut t = 0;
154        for i in num.iter_mut().rev() {
155            let t2 = *i << 63;
156            *i >>= 1;
157            *i |= t;
158            t = t2;
159        }
160    };
161
162    let mut num = num.to_vec();
163    let mut res = vec![];
164
165    while !is_zero(&num) {
166        let z: i8;
167        if is_odd(&num) {
168            z = 2 - (num[0] % 4) as i8;
169            if z >= 0 {
170                sub_noborrow(&mut num, z as u64)
171            } else {
172                add_nocarry(&mut num, (-z) as u64)
173            }
174        } else {
175            z = 0;
176        }
177        res.push(z);
178        div2(&mut num);
179    }
180
181    res
182}
183
184/// We define relaxed NAF as a variant of NAF with a very small tweak.
185///
186/// Note that the cost of scalar multiplication grows with the length of the sequence (for doubling)
187/// plus the Hamming weight of the sequence (for addition, or subtraction).
188///
189/// NAF is optimizing for the Hamming weight only and therefore can be suboptimal.
190/// For example, NAF may generate a sequence (in little-endian) of the form ...0 -1 0 1.
191///
192/// This can be rewritten as ...0 1 1 to avoid one doubling, at the cost that we are making an
193/// exception of non-adjacence for the most significant bit.
194///
195/// Since this representation is no longer a strict NAF, we call it "relaxed NAF".
196pub fn find_relaxed_naf(num: &[u64]) -> Vec<i8> {
197    let mut res = find_naf(num);
198
199    let len = res.len();
200    if res[len - 2] == 0 && res[len - 3] == -1 {
201        res[len - 3] = 1;
202        res[len - 2] = 1;
203        res.resize(len - 1, 0);
204    }
205
206    res
207}
208
209#[test]
210fn test_find_relaxed_naf_usefulness() {
211    let vec = find_naf(&[12u64]);
212    assert_eq!(vec.len(), 5);
213
214    let vec = find_relaxed_naf(&[12u64]);
215    assert_eq!(vec.len(), 4);
216}
217
218#[test]
219fn test_find_relaxed_naf_correctness() {
220    use ark_std::{One, UniformRand, Zero};
221    use num_bigint::BigInt;
222
223    let mut rng = ark_std::test_rng();
224
225    for _ in 0..10 {
226        let num = [
227            u64::rand(&mut rng),
228            u64::rand(&mut rng),
229            u64::rand(&mut rng),
230            u64::rand(&mut rng),
231        ];
232        let relaxed_naf = find_relaxed_naf(&num);
233
234        let test = {
235            let mut sum = BigInt::zero();
236            let mut cur = BigInt::one();
237            for v in relaxed_naf {
238                sum += cur.clone() * v;
239                cur *= 2;
240            }
241            sum
242        };
243
244        let test_expected = {
245            let mut sum = BigInt::zero();
246            let mut cur = BigInt::one();
247            for v in num.iter() {
248                sum += cur.clone() * v;
249                cur <<= 64;
250            }
251            sum
252        };
253
254        assert_eq!(test, test_expected);
255    }
256}
ark_ff/biginteger/arithmetic.rs

ark_ff/biginteger/
arithmetic.rs
