1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

//! [`UInt`] subtraction modulus operations.

use crate::{Limb, NegMod, UInt};

impl<const LIMBS: usize> UInt<LIMBS> {
    /// Computes `-a mod p` in constant time.
    pub const fn neg_mod(&self, p: &Self) -> Self {
        let mut tmp = [Limb::ZERO; LIMBS];

        // Subtract `a` from `p` to negate. Ignore the final
        // borrow because it cannot underflow; a is guaranteed to
        // be in the field.
        let mut borrow = Limb::ZERO;
        let mut i = 0;

        while i < LIMBS {
            let (l, b) = p.limbs[i].sbb(self.limbs[i], borrow);
            tmp[i] = l;
            borrow = b;

            i += 1;
        }

        // `tmp` could be `p` if `a` was zero. Create a mask that is
        // zero if `a` was zero, and `Limb::MAX` if self was nonzero.
        // FIXME: constant time comparison
        let mut self_or = self.limbs[0];
        let mut i = 1;

        while i < LIMBS {
            self_or = self_or.bitor(self.limbs[i]);
            i += 1;
        }

        let v = if self_or.eq_vartime(&Limb::ZERO) {
            Limb::ONE
        } else {
            Limb::ZERO
        };

        let mask = v.wrapping_sub(Limb::ONE);

        let mut i = 0;

        while i < LIMBS {
            tmp[i] = tmp[i].bitand(mask);
            i += 1;
        }

        UInt::new(tmp)
    }
}

macro_rules! impl_neg_mod {
    ($($size:expr),+) => {
        $(
            impl NegMod for UInt<$size> {
                type Output = Self;

                fn neg_mod(&self, p: &Self) -> Self {
                    debug_assert!(self < p);
                    self.neg_mod(p)
                }
            }
        )+
    };
}

impl_neg_mod!(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12);