eccoxide/mp/
limbs.rs

1#![allow(dead_code)]
2
3use super::ct::*;
4
5pub type Limb = u64;
6
7pub type Borrow = u8;
8pub type IBorrow = i8;
9
10pub struct LimbsLE<'a>(pub &'a [Limb]);
11
12pub struct LimbsBE<'a>(pub &'a [Limb]);
13
14impl<'a> LimbsLE<'a> {
15    pub fn len(&self) -> usize {
16        self.0.len()
17    }
18    pub fn iter_from_high(&self) -> core::iter::Rev<std::slice::Iter<'a, u64>> {
19        self.0.iter().rev()
20    }
21
22    pub fn iter_from_low(&self) -> std::slice::Iter<'a, u64> {
23        self.0.iter()
24    }
25}
26
27impl<'a> LimbsBE<'a> {
28    pub fn len(&self) -> usize {
29        self.0.len()
30    }
31    pub fn iter_from_high(&self) -> std::slice::Iter<'a, u64> {
32        self.0.iter()
33    }
34
35    pub fn iter_from_low(&self) -> core::iter::Rev<std::slice::Iter<'a, u64>> {
36        self.0.iter().rev()
37    }
38}
39
40// borrowed from fiat-crypto subborrow routine
41fn limb_subborrow(out1: &mut u64, out2: &mut Borrow, arg1: Borrow, arg2: u64, arg3: u64) -> () {
42    let x1: i128 = ((arg2 as i128) - (arg1 as i128)) - (arg3 as i128);
43    let x2: IBorrow = (x1 >> 64) as IBorrow;
44    let x3: u64 = (x1 & (0xffffffffffffffff as i128)) as u64;
45    *out1 = x3;
46    *out2 = ((0x0 as IBorrow) - (x2 as IBorrow)) as Borrow;
47}
48
49// Check that the value a is less than the value b
50pub fn limbsbe_le<'a, 'b>(a: LimbsBE<'a>, b: LimbsBE<'b>) -> Choice {
51    assert_eq!(a.len(), b.len());
52
53    let mut borrow: Borrow = 0;
54    let mut out = 0u64;
55    for (x, y) in b.iter_from_low().zip(a.iter_from_low()) {
56        let copied_borrow = borrow;
57        limb_subborrow(&mut out, &mut borrow, copied_borrow, *x, *y);
58    }
59    Choice(1 ^ borrow as u64)
60}
61
62pub fn limbsbe_lt<'a, 'b>(a: LimbsBE<'a>, b: LimbsBE<'b>) -> Choice {
63    assert_eq!(a.len(), b.len());
64
65    let mut borrow: Borrow = 0;
66    let mut out = 0u64;
67    for (x, y) in a.iter_from_low().zip(b.iter_from_low()) {
68        let copied_borrow = borrow;
69        limb_subborrow(&mut out, &mut borrow, copied_borrow, *x, *y);
70    }
71    let borrow = borrow as u64;
72    Choice((borrow | borrow.wrapping_neg()) >> 63)
73}
74
75pub fn limbsle_le<'a, 'b>(a: LimbsLE<'a>, b: LimbsLE<'b>) -> Choice {
76    assert_eq!(a.len(), b.len());
77
78    let mut borrow: Borrow = 0;
79    let mut out = 0u64;
80    for (x, y) in b.iter_from_low().zip(a.iter_from_low()) {
81        let copied_borrow = borrow;
82        limb_subborrow(&mut out, &mut borrow, copied_borrow, *x, *y)
83    }
84    Choice(1 ^ borrow as u64)
85}
86
87pub fn limbsle_lt<'a, 'b>(a: LimbsLE<'a>, b: LimbsLE<'b>) -> Choice {
88    assert_eq!(a.len(), b.len());
89
90    let mut borrow: Borrow = 0;
91    let mut out = 0u64;
92    for (x, y) in a.iter_from_low().zip(b.iter_from_low()) {
93        let copied_borrow = borrow;
94        limb_subborrow(&mut out, &mut borrow, copied_borrow, *x, *y);
95    }
96    let borrow = borrow as u64;
97    Choice((borrow | borrow.wrapping_neg()) >> 63)
98}
99
100impl<'a> CtEqual for LimbsLE<'a> {
101    fn ct_eq(&self, b: &Self) -> Choice {
102        self.0.ct_eq(b.0)
103    }
104}
105
106impl<'a> CtEqual for LimbsBE<'a> {
107    fn ct_eq(&self, b: &Self) -> Choice {
108        self.0.ct_eq(b.0)
109    }
110}
111
112impl<'a> CtZero for LimbsLE<'a> {
113    fn ct_zero(&self) -> Choice {
114        self.0.ct_zero()
115    }
116    fn ct_nonzero(&self) -> Choice {
117        self.0.ct_nonzero()
118    }
119}
120
121impl<'a> CtLesser for LimbsLE<'a> {
122    fn ct_lt(a: Self, b: Self) -> Choice {
123        limbsle_lt(a, b)
124    }
125}
126
127impl<'a> CtLesser for LimbsBE<'a> {
128    fn ct_lt(a: Self, b: Self) -> Choice {
129        limbsbe_lt(a, b)
130    }
131}
132
133#[cfg(test)]
134mod tests {
135    use super::*;
136
137    #[test]
138    fn le() {
139        assert_eq!(
140            false,
141            limbsbe_le(
142                LimbsBE(&[1, 0, 0, 0]),
143                LimbsBE(&[0, u64::MAX, u64::MAX, u64::MAX])
144            )
145            .into()
146        );
147        assert_eq!(
148            true,
149            limbsbe_le(LimbsBE(&[1, 2, 3]), LimbsBE(&[1, 2, 3])).into()
150        );
151        assert_eq!(
152            true,
153            limbsbe_le(LimbsBE(&[1, 2, 3]), LimbsBE(&[1, 3, 3])).into()
154        );
155        assert_eq!(
156            true,
157            limbsbe_le(LimbsBE(&[0, 2, 3]), LimbsBE(&[1, 2, 3])).into(),
158        );
159        assert_eq!(
160            false,
161            limbsbe_le(LimbsBE(&[1, 4, 2]), LimbsBE(&[1, 2, 3])).into(),
162        );
163        assert_eq!(
164            false,
165            limbsbe_le(LimbsBE(&[2, 0, 2]), LimbsBE(&[1, 2, 3])).into(),
166        );
167    }
168
169    #[test]
170    fn lt() {
171        assert_eq!(
172            false,
173            limbsbe_le(
174                LimbsBE(&[1, 0, 0, 0]),
175                LimbsBE(&[0, u64::MAX, u64::MAX, u64::MAX])
176            )
177            .into(),
178        );
179        assert_eq!(
180            false,
181            limbsbe_lt(LimbsBE(&[1, 2, 3]), LimbsBE(&[1, 2, 3])).into(),
182        );
183        assert_eq!(
184            true,
185            limbsbe_lt(LimbsBE(&[1, 2, 3]), LimbsBE(&[1, 3, 3])).into(),
186        );
187        assert_eq!(
188            true,
189            limbsbe_lt(LimbsBE(&[0, 2, 3]), LimbsBE(&[1, 2, 3])).into(),
190        );
191        assert_eq!(
192            false,
193            limbsbe_lt(LimbsBE(&[1, 4, 2]), LimbsBE(&[1, 2, 3])).into(),
194        );
195        assert_eq!(
196            false,
197            limbsbe_lt(LimbsBE(&[2, 0, 2]), LimbsBE(&[1, 2, 3])).into(),
198        );
199    }
200}
eccoxide/mp/limbs.rs

eccoxide/mp/
limbs.rs
