fp/vector/
mod.rs

1pub mod inner;
2
3mod fp_wrapper;
4mod impl_fqslice;
5mod impl_fqslicemut;
6mod impl_fqvector;
7mod iter;
8
9pub use fp_wrapper::*;
10#[cfg(feature = "proptest")]
11pub use impl_fqvector::arbitrary;
12pub use inner::*;
13
14#[cfg(test)]
15pub(super) mod tests {
16    use itertools::Itertools;
17    use proptest::prelude::*;
18
19    use super::{arbitrary::MAX_LEN as MAX_TEST_VEC_LEN, inner::FqVector};
20    use crate::{
21        field::{Field, element::FieldElement, fp::F2},
22        limb,
23    };
24
25    pub struct VectorDiffEntry<F: Field> {
26        pub index: usize,
27        pub left: FieldElement<F>,
28        pub right: FieldElement<F>,
29    }
30
31    impl<F: Field> FqVector<F> {
32        pub fn diff_list(&self, other: &[FieldElement<F>]) -> Vec<VectorDiffEntry<F>> {
33            assert!(self.len() == other.len());
34            let mut result = Vec::new();
35            #[allow(clippy::needless_range_loop)]
36            for index in 0..self.len() {
37                let left = self.entry(index);
38                let right = other[index].clone();
39                if left != right {
40                    result.push(VectorDiffEntry { index, left, right });
41                }
42            }
43            result
44        }
45
46        pub fn diff_vec(&self, other: &Self) -> Vec<VectorDiffEntry<F>> {
47            assert!(self.len() == other.len());
48            let mut result = Vec::new();
49            for index in 0..self.len() {
50                let left = self.entry(index);
51                let right = other.entry(index);
52                if left != right {
53                    result.push(VectorDiffEntry { index, left, right });
54                }
55            }
56            result
57        }
58
59        pub fn format_diff(diff: Vec<VectorDiffEntry<F>>) -> String {
60            let data_formatter =
61                diff.iter()
62                    .format_with("\n ", |VectorDiffEntry { index, left, right }, f| {
63                        f(&format_args!("  At index {index}: {left}!={right}"))
64                    });
65            format!("{data_formatter}")
66        }
67
68        pub fn assert_list_eq(&self, other: &[FieldElement<F>]) {
69            let diff = self.diff_list(other);
70            if diff.is_empty() {
71                return;
72            }
73            panic!(
74                "assert {} == {:?}\n{}",
75                self,
76                other,
77                Self::format_diff(diff)
78            );
79        }
80
81        pub fn assert_vec_eq(&self, other: &Self) {
82            let diff = self.diff_vec(other);
83            if diff.is_empty() {
84                return;
85            }
86            panic!(
87                "assert {} == {:?}\n{}",
88                self,
89                other,
90                Self::format_diff(diff)
91            );
92        }
93    }
94
95    /// An arbitrary (field, dimension) pair
96    fn arb_field_dim<F: Field>() -> impl Strategy<Value = (F, usize)> {
97        (any::<F>(), 0..=MAX_TEST_VEC_LEN)
98    }
99
100    /// The start and end positions of an arbitrary slice of a vector of length `dimension`
101    fn arb_slice(dimension: usize) -> impl Strategy<Value = (usize, usize)> {
102        (0..=dimension).prop_flat_map(move |first| (Just(first), first..=dimension))
103    }
104
105    prop_compose! {
106        /// An arbitrary pair of slices of a vector of length `dimension` _that have the same length_
107        fn arb_slice_pair(dimension: usize)
108            (len in 0..=dimension)
109            (len in Just(len), first in 0..=dimension - len, second in 0..=dimension - len)
110            -> [(usize, usize); 2]
111        {
112            [(first, first + len), (second, second + len)]
113        }
114    }
115
116    /// An arbitrary vector of length `dimension` containing values in the field `fq`. The tests
117    /// take in a `Vec` instead of an `FqVector` directly because they will usually apply some
118    /// operation on both the `FqVector` and the original `Vec` and then compare the results.
119    fn arb_element_vec<F: Field>(
120        fq: F,
121        dimension: usize,
122    ) -> impl Strategy<Value = Vec<FieldElement<F>>> {
123        proptest::collection::vec(fq.arb_element(), dimension)
124    }
125
126    /// A pair of a field `fq` and a vector containing values in that field. In other words, a
127    /// vector over `fq`.
128    pub fn arb_vec<F: Field>() -> impl Strategy<Value = (F, Vec<FieldElement<F>>)> {
129        arb_field_dim().prop_flat_map(|(fq, dim)| (Just(fq), arb_element_vec(fq, dim)))
130    }
131
132    /// An Fq vector together with valid slice indices
133    fn arb_vec_and_slice<F: Field>()
134    -> impl Strategy<Value = (F, Vec<FieldElement<F>>, (usize, usize))> {
135        arb_field_dim()
136            .prop_flat_map(|(fq, dim)| (Just(fq), arb_element_vec(fq, dim), arb_slice(dim)))
137    }
138
139    /// A pair of vectors of the same length over the same field
140    fn arb_vec_pair<F: Field>()
141    -> impl Strategy<Value = (F, Vec<FieldElement<F>>, Vec<FieldElement<F>>)> {
142        arb_field_dim().prop_flat_map(|(fq, dim)| {
143            (Just(fq), arb_element_vec(fq, dim), arb_element_vec(fq, dim))
144        })
145    }
146
147    /// A pair of vectors of the same length over the same field, together with valid slice indices
148    fn arb_vec_pair_and_slice<F: Field>() -> impl Strategy<
149        Value = (
150            F,
151            Vec<FieldElement<F>>,
152            Vec<FieldElement<F>>,
153            (usize, usize),
154        ),
155    > {
156        arb_field_dim().prop_flat_map(|(fq, dim)| {
157            (
158                Just(fq),
159                arb_element_vec(fq, dim),
160                arb_element_vec(fq, dim),
161                arb_slice(dim),
162            )
163        })
164    }
165
166    /// A pair of vectors of the same length over the same field, together with a mask (in the sense
167    /// of [`FqVector::add_masked`] and [`FqVector::add_unmasked`])
168    fn arb_vec_pair_and_mask<F: Field>()
169    -> impl Strategy<Value = (F, Vec<FieldElement<F>>, Vec<FieldElement<F>>, Vec<usize>)> {
170        any::<F>()
171            .prop_flat_map(|fq| (Just(fq), arb_slice(MAX_TEST_VEC_LEN)))
172            .prop_flat_map(|(fq, (dim_small, dim_large))| {
173                (
174                    Just(fq),
175                    arb_element_vec(fq, dim_small),
176                    arb_element_vec(fq, dim_large),
177                    proptest::collection::vec(0..dim_large, dim_small),
178                )
179            })
180    }
181
182    macro_rules! vector_tests {
183        ($field:ty) => {
184    proptest! {
185        #![proptest_config(ProptestConfig {
186            max_shrink_time: 30_000,
187            max_shrink_iters: 1_000_000,
188            .. ProptestConfig::default()
189        })]
190
191        // These "incompatible_fields" tests would lend themselves nicely to a macro, but it's
192        // currently impossible to define the necessary macro inside another. See
193        // https://github.com/rust-lang/rust/issues/35853.
194        #[test]
195        fn test_incompatible_fields_assign((fq1, fq2) in (any::<$field>(), any::<$field>())) {
196            if fq1 != fq2 {
197                let panic = std::panic::catch_unwind(|| {
198                    FqVector::new(fq1, 10).assign(&FqVector::new(fq2, 10))
199                });
200                prop_assert!(panic.is_err());
201            }
202        }
203
204        #[test]
205        fn test_incompatible_fields_assign_partial((fq1, fq2) in (any::<$field>(), any::<$field>())) {
206            if fq1 != fq2 {
207                let panic = std::panic::catch_unwind(|| {
208                    FqVector::new(fq1, 10).assign_partial(&FqVector::new(fq2, 10))
209                });
210                prop_assert!(panic.is_err());
211            }
212        }
213
214        #[test]
215        fn test_incompatible_fields_add((fq1, fq2) in (any::<$field>(), any::<$field>())) {
216            if fq1 != fq2 {
217                let panic = std::panic::catch_unwind(|| {
218                    FqVector::new(fq1, 10).add(&FqVector::new(fq2, 10), fq2.one())
219                });
220                prop_assert!(panic.is_err());
221            }
222        }
223
224        #[test]
225        fn test_incompatible_fields_add_offset((fq1, fq2) in (any::<$field>(), any::<$field>())) {
226            if fq1 != fq2 {
227                let panic = std::panic::catch_unwind(|| {
228                    FqVector::new(fq1, 10).add_offset(&FqVector::new(fq2, 10), fq2.one(), 5)
229                });
230                prop_assert!(panic.is_err());
231            }
232        }
233
234        #[test]
235        fn test_incompatible_fields_add_truncate((fq1, fq2) in (any::<$field>(), any::<$field>())) {
236            if fq1 != fq2 {
237                let panic = std::panic::catch_unwind(|| {
238                    FqVector::new(fq1, 10).add_truncate(&FqVector::new(fq2, 10), fq2.one())
239                });
240                prop_assert!(panic.is_err());
241            }
242        }
243
244        #[test]
245        fn test_incompatible_fields_sign_rule((fq1, fq2) in (any::<$field>(), any::<$field>())) {
246            if fq1 != fq2 {
247                let panic = std::panic::catch_unwind(|| {
248                    FqVector::new(fq1, 10).sign_rule(&FqVector::new(fq2, 10))
249                });
250                prop_assert!(panic.is_err());
251            }
252        }
253
254        #[test]
255        fn test_incompatible_fields_add_carry((fq1, fq2) in (any::<$field>(), any::<$field>())) {
256            if fq1 != fq2 {
257                let panic = std::panic::catch_unwind(|| {
258                    FqVector::new(fq1, 10).add_carry::<FqVector<_>>(&FqVector::new(fq2, 10), fq2.one(), &mut [])
259                });
260                prop_assert!(panic.is_err());
261            }
262        }
263
264        #[test]
265        fn test_serialize((fq, v_arr) in arb_vec::<$field>()) {
266            use std::io::{Seek, Cursor};
267
268            let v = FqVector::from_slice(fq, &v_arr);
269
270            let mut cursor = Cursor::new(Vec::<u8>::new());
271            v.to_bytes(&mut cursor).unwrap();
272            cursor.rewind().unwrap();
273
274            let w = FqVector::from_bytes(v.fq(), v.len(), &mut cursor).unwrap();
275            v.assert_vec_eq(&w);
276        }
277
278        #[test]
279        fn test_add((fq, mut v_arr, w_arr) in arb_vec_pair::<$field>()) {
280            let mut v = FqVector::from_slice(fq, &v_arr);
281            let w = FqVector::from_slice(fq, &w_arr);
282
283            v.add(&w, fq.one());
284
285            for (v_element, w_element) in v_arr.iter_mut().zip(w_arr.iter()) {
286                *v_element += *w_element;
287            }
288            v.assert_list_eq(&v_arr);
289        }
290
291        #[test]
292        fn test_add_offset((fq, mut v_arr, w_arr, (slice_start, slice_end), offset) in
293            arb_field_dim::<$field>().prop_flat_map(|(fq, dim)| {
294                (Just(fq), arb_element_vec(fq, dim), arb_element_vec(fq, dim), arb_slice(dim), any::<prop::sample::Index>())
295            })
296        ) {
297            let mut v = FqVector::from_slice(fq, &v_arr);
298            let w = FqVector::from_slice(fq, &w_arr);
299
300            let mut v_slice = v.slice_mut(slice_start, slice_end);
301            let w_slice = w.slice(slice_start, slice_end);
302
303            let slice_len = w_slice.len();
304            let real_offset = if slice_len > 0 { offset.index(slice_len) } else { 0 };
305
306            v_slice.add_offset(w_slice, fq.one(), real_offset);
307
308            for (v_element, w_element) in v_arr.iter_mut()
309                .zip(w_arr.iter())
310                .skip(slice_start)
311                .take(slice_len)
312                .skip(real_offset)
313            {
314                *v_element += *w_element;
315            }
316            v.assert_list_eq(&v_arr);
317        }
318
319        #[test]
320        fn test_scale((fq, mut v_arr, c) in arb_field_dim::<$field>().prop_flat_map(|(fq, dim)| {
321            (Just(fq), arb_element_vec(fq, dim), fq.arb_element())
322        })) {
323            let mut v = FqVector::from_slice(fq, &v_arr);
324            v.scale(c);
325            for entry in &mut v_arr {
326                *entry *= c;
327            }
328            v.assert_list_eq(&v_arr);
329        }
330
331        #[test]
332        fn test_scale_slice((fq, mut v_arr, (slice_start, slice_end), c) in
333            arb_field_dim::<$field>().prop_flat_map(|(fq, dim)| {
334                (Just(fq), arb_element_vec(fq, dim), arb_slice(dim), fq.arb_element())
335            })
336        ) {
337            let mut v = FqVector::from_slice(fq, &v_arr);
338            v.slice_mut(slice_start, slice_end).scale(c);
339
340            for entry in &mut v_arr[slice_start..slice_end] {
341                *entry *= c;
342            }
343            v.assert_list_eq(&v_arr);
344        }
345
346        #[test]
347        fn test_entry((fq, v_arr) in arb_vec::<$field>()) {
348            let v = FqVector::from_slice(fq, &v_arr);
349
350            let mut diffs = Vec::new();
351            for (i, val) in v.iter().enumerate() {
352                if v.entry(i) != val {
353                    diffs.push((i, val, v.entry(i)));
354                }
355            }
356            prop_assert_eq!(diffs, []);
357        }
358
359        #[test]
360        fn test_entry_slice((fq, v_arr, (slice_start, slice_end)) in arb_vec_and_slice::<$field>()) {
361            let v = FqVector::from_slice(fq, &v_arr);
362            let v = v.slice(slice_start, slice_end);
363            println!(
364                "slice_start: {slice_start}, slice_end: {slice_end}, slice: {v}"
365                );
366
367            let mut diffs = Vec::new();
368            for i in 0..v.len() {
369                if v.entry(i) != v_arr[i + slice_start] {
370                    diffs.push((i, v_arr[i + slice_start], v.entry(i)));
371                }
372            }
373            prop_assert_eq!(diffs, []);
374        }
375
376        #[test]
377        fn test_set_entry((fq, v_arr) in arb_vec::<$field>()) {
378            let mut v = FqVector::new(fq, v_arr.len());
379
380            for (i, &val) in v_arr.iter().enumerate() {
381                v.set_entry(i, val);
382            }
383            v.assert_list_eq(&v_arr);
384        }
385
386        #[test]
387        fn test_set_entry_slice((fq, v_arr, (slice_start, slice_end)) in arb_vec_and_slice::<$field>()) {
388            let dim = v_arr.len();
389            let mut v = FqVector::new(fq, dim);
390            let mut v = v.slice_mut(slice_start, slice_end);
391
392            let v_slice = &v_arr[slice_start..slice_end];
393            for (i, &val) in v_slice.iter().enumerate() {
394                v.set_entry(i, val);
395            }
396            let v = v.as_slice();
397
398            let mut diffs = Vec::new();
399            for (i, &val) in v_slice.iter().enumerate() {
400                if v.entry(i) != val {
401                    diffs.push((i, val, v.entry(i)));
402                }
403            }
404            prop_assert_eq!(diffs, []);
405        }
406
407        #[test]
408        fn test_set_to_zero_slice((fq, mut v_arr, (slice_start, slice_end)) in arb_vec_and_slice::<$field>()) {
409            println!("slice_start : {slice_start}, slice_end : {slice_end}");
410            let mut v = FqVector::from_slice(fq, &v_arr);
411
412            v.slice_mut(slice_start, slice_end).set_to_zero();
413            prop_assert!(v.slice(slice_start, slice_end).is_zero());
414
415            for entry in &mut v_arr[slice_start..slice_end] {
416                *entry = fq.zero();
417            }
418            v.assert_list_eq(&v_arr);
419        }
420
421        #[test]
422        fn test_add_slice_to_slice((fq, mut v_arr, w_arr, (slice_start, slice_end)) in arb_vec_pair_and_slice::<$field>()) {
423            let mut v = FqVector::from_slice(fq, &v_arr);
424            let w = FqVector::from_slice(fq, &w_arr);
425
426            v.slice_mut(slice_start, slice_end)
427                .add(w.slice(slice_start, slice_end), fq.one());
428
429            for i in slice_start..slice_end {
430                v_arr[i] += w_arr[i];
431            }
432            v.assert_list_eq(&v_arr);
433        }
434
435        #[test]
436        fn test_assign((fq, v_arr, w_arr) in arb_vec_pair::<$field>()) {
437            let mut v = FqVector::from_slice(fq, &v_arr);
438            let w = FqVector::from_slice(fq, &w_arr);
439
440            v.assign(&w);
441            v.assert_vec_eq(&w);
442        }
443
444        #[test]
445        fn test_assign_partial((fq, v_arr, w_arr) in arb_vec_pair::<$field>()) {
446            let dim = v_arr.len();
447            let mut v = FqVector::from_slice(fq, &v_arr);
448            let w = FqVector::from_slice(fq, &w_arr[0..(dim / 2)]);
449
450            v.assign_partial(&w);
451            prop_assert!(v.slice(dim / 2, dim).is_zero());
452            prop_assert_eq!(v.len(), dim);
453            v.slice(0, dim / 2).to_owned().assert_vec_eq(&w);
454        }
455
456        #[test]
457        fn test_assign_slice_to_slice((fq, mut v_arr, w_arr, (slice_start, slice_end)) in arb_vec_pair_and_slice::<$field>()) {
458            let mut v = FqVector::from_slice(fq, &v_arr);
459            let w = FqVector::from_slice(fq, &w_arr);
460
461            v.slice_mut(slice_start, slice_end)
462                .assign(w.slice(slice_start, slice_end));
463            v_arr[slice_start..slice_end].clone_from_slice(&w_arr[slice_start..slice_end]);
464            v.assert_list_eq(&v_arr);
465        }
466
467        #[test]
468        fn test_add_shift((fq, mut v_arr, w_arr, [(slice1_start, slice1_end), (slice2_start, slice2_end)])
469            in arb_field_dim::<$field>().prop_flat_map(|(fq, dim)| {
470                (
471                    Just(fq),
472                    arb_element_vec(fq, dim),
473                    arb_element_vec(fq, dim),
474                    arb_slice_pair(dim),
475                )
476            })
477        ) {
478            let mut v = FqVector::from_slice(fq, &v_arr);
479            let w = FqVector::from_slice(fq, &w_arr);
480
481            v.slice_mut(slice1_start, slice1_end)
482                .add(w.slice(slice2_start, slice2_end), fq.one());
483
484            for (v_element, w_element) in v_arr[slice1_start..slice1_end]
485                .iter_mut()
486                .zip(w_arr[slice2_start..slice2_end].iter())
487            {
488                *v_element += *w_element;
489            }
490            v.assert_list_eq(&v_arr);
491        }
492
493        #[test]
494        fn test_add_masked((fq, mut v_small, v_big, mask) in arb_vec_pair_and_mask::<$field>()) {
495            let mut v = FqVector::from_slice(fq, &v_small);
496            let w = FqVector::from_slice(fq, &v_big);
497
498            v.as_slice_mut().add_masked(w.as_slice(), fq.one(), &mask);
499
500            for (i, x) in v_small.iter_mut().enumerate() {
501                *x += v_big[mask[i]];
502            }
503
504            v.assert_list_eq(&v_small);
505        }
506
507        #[test]
508        fn test_add_unmasked((fq, v_small, mut v_big, mask) in arb_vec_pair_and_mask::<$field>()) {
509            let mut v = FqVector::from_slice(fq, &v_big);
510            let w = FqVector::from_slice(fq, &v_small);
511
512            v.as_slice_mut().add_unmasked(w.as_slice(), fq.one(), &mask);
513            for (i, &x) in v_small.iter().enumerate() {
514                v_big[mask[i]] += x;
515            }
516            v.assert_list_eq(&v_big);
517        }
518
519        #[test]
520        fn test_iterator_slice((p, v_arr, (slice_start, slice_end)) in arb_vec_and_slice::<$field>()) {
521            let v = FqVector::from_slice(p, &v_arr);
522            let v = v.slice(slice_start, slice_end);
523
524            let w = v.iter();
525            let mut counter = 0;
526            for (i, x) in w.enumerate() {
527                prop_assert_eq!(v.entry(i), x);
528                counter += 1;
529            }
530            prop_assert_eq!(counter, v.len());
531        }
532
533        #[test]
534        fn test_iterator_skip((p, v_arr, num_skip) in arb_field_dim::<$field>().prop_flat_map(|(p, dim)| {
535            (Just(p), arb_element_vec(p, dim), 0..=dim)
536        })) {
537            let v = FqVector::from_slice(p, &v_arr);
538
539            let mut w = v.iter();
540            w.skip_n(num_skip);
541            let mut counter = 0;
542            for (i, x) in w.enumerate() {
543                prop_assert_eq!(v.entry(i + num_skip), x);
544                counter += 1;
545            }
546
547            prop_assert_eq!(counter, v.len() - num_skip);
548        }
549
550        #[test]
551        fn test_iterator((p, v_arr) in arb_vec::<$field>()) {
552            let v = FqVector::from_slice(p, &v_arr);
553
554            let w = v.iter();
555            let mut counter = 0;
556            for (i, x) in w.enumerate() {
557                prop_assert_eq!(v.entry(i), x);
558                counter += 1;
559            }
560            prop_assert_eq!(counter, v.len());
561        }
562
563        #[test]
564        fn test_iter_nonzero_empty((p, dimension) in arb_field_dim::<$field>()) {
565            let v = FqVector::new(p, dimension);
566            prop_assert_eq!(v.iter_nonzero().next(), None);
567        }
568
569        #[test]
570        fn test_iter_nonzero((fq, v_arr, (slice_start, slice_end)) in arb_vec_and_slice::<$field>()) {
571            use std::fmt::Write;
572
573            let v = FqVector::from_slice(fq, &v_arr);
574
575            println!("v: {v}");
576            println!("v_arr: {v_arr:?}");
577            let result: Vec<_> = v.slice(slice_start, slice_end).iter_nonzero().collect();
578            let comparison_result: Vec<_> = v_arr[slice_start..slice_end]
579                .iter()
580                .copied()
581                .enumerate()
582                .filter(|&(_, x)| x != fq.zero())
583                .collect();
584
585            let mut i = 0;
586            let mut j = 0;
587            let mut diffs_str = String::new();
588            while i < result.len() && j < comparison_result.len() {
589                if result[i] != comparison_result[j] {
590                    if result[i].0 < comparison_result[j].0 {
591                        let _ = write!(
592                            diffs_str,
593                            "\n({:?}) present in result, missing from comparison_result",
594                            result[i]
595                        );
596                        i += 1;
597                    } else {
598                        let _ = write!(
599                            diffs_str,
600                            "\n({:?}) present in comparison_result, missing from result",
601                            comparison_result[j]
602                        );
603                        j += 1;
604                    }
605                } else {
606                    i += 1;
607                    j += 1;
608                }
609            }
610            // for i in 0 .. std::cmp::min(result.len(), comparison_result.len()) {
611            //     println!("res : {:?}, comp : {:?}", result[i], comparison_result[i]);
612            // }
613            prop_assert!(diffs_str.is_empty(), "{}", diffs_str);
614        }
615    }
616};
617    }
618
619    /// For a given field type generic over a prime type, and a given prime type, run our tests for
620    /// vectors over that field.
621    macro_rules! test_prime {
622        ($fq:tt, $p:tt) => {
623            paste::paste! {
624                mod [<$p:lower>] {
625                    use super::*;
626                    use crate::prime::$p;
627
628                    vector_tests!($fq<$p>);
629                }
630            }
631        };
632    }
633
634    // For a given field type generic over a prime type, run our tests for it over P2, P3, P5, P7,
635    // as well as ValidPrime. Note that this macro makes assumptions about the path to the field
636    // type within the crate.
637    macro_rules! test_field {
638        ($fq:tt) => {
639            paste::paste! {
640                mod [<$fq:lower>] {
641                    use super::*;
642                    use crate::field::[<$fq:lower>]::$fq;
643
644                    test_prime!($fq, ValidPrime);
645                    test_prime!($fq, P2);
646                    cfg_if::cfg_if! { if #[cfg(feature = "odd-primes")] {
647                        test_prime!($fq, P3);
648                        test_prime!($fq, P5);
649                        test_prime!($fq, P7);
650                    }}
651                }
652            }
653        };
654    }
655
656    test_field!(Fp);
657    test_field!(SmallFq);
658
659    #[test]
660    fn test_sign_rule_limb() {
661        assert!(limb::sign_rule(1, 0b10) == 1);
662        assert!(limb::sign_rule(0b10, 1) == 0);
663        assert!(limb::sign_rule(0x84012c02, 0x6b920241) == 1);
664        assert!(limb::sign_rule(0x6b920241, 0x84012c02) == 0);
665    }
666
667    #[test]
668    #[ignore]
669    fn test_sign_rule() {
670        let mut in1 = FqVector::new(F2, 128);
671        let mut in2 = FqVector::new(F2, 128);
672        let tests = [
673            (
674                0x181e20846a820820,
675                0x2122a1a08c1a0069,
676                0xe30140608100e540,
677                0xd2180e4350008004,
678                false,
679                false,
680            ),
681            (
682                0x2090400020017044,
683                0xa04e0802080000e1,
684                0x18298a0a85080089,
685                0x050020311030411a,
686                false,
687                false,
688            ),
689            (
690                0x082080022408d510,
691                0x538a000802078210,
692                0x2355308c4a920002,
693                0x00058130800000a2,
694                true,
695                true,
696            ),
697            (
698                0x33a0824922050704,
699                0x00400520a0800404,
700                0x00090836000a980b,
701                0x4801d005064b9840,
702                false,
703                false,
704            ),
705            (
706                0x290c14040154a01b,
707                0x38014102810a0245,
708                0x0093281a620a1060,
709                0x029014cd0684080a,
710                true,
711                true,
712            ),
713            (
714                0x240255b490b0e040,
715                0x0815414130548881,
716                0x8ad4880a00000416,
717                0xb660a4b84cab002c,
718                true,
719                true,
720            ),
721            (
722                0x010c000060840540,
723                0x8008001480104028,
724                0x8842938396233a31,
725                0x5e20400311059a41,
726                true,
727                true,
728            ),
729            (
730                0x02012141008e5081,
731                0x2829060241920a00,
732                0xe0208a1a47102310,
733                0x051240010e6c4008,
734                false,
735                false,
736            ),
737            (
738                0x200812011081880f,
739                0x100661c082625864,
740                0x48840c76c03a2380,
741                0x861088274000060a,
742                false,
743                false,
744            ),
745            (
746                0x84000f5490449008,
747                0x00891820f4623401,
748                0x107490a964b802a4,
749                0x40024487008800b0,
750                false,
751                false,
752            ),
753            (
754                0x080448a2db282c41,
755                0x2c100011e00097dd,
756                0x0131024124844028,
757                0x8329600202440002,
758                false,
759                false,
760            ),
761            (
762                0x441c60a208c2e206,
763                0x00a4210b50049281,
764                0x0842020160091158,
765                0x48131424846a6868,
766                true,
767                true,
768            ),
769            (
770                0xc2743ad490a21411,
771                0x0150221280868050,
772                0x1082402043040888,
773                0xdc070000021128a0,
774                true,
775                true,
776            ),
777            (
778                0x0614030849072140,
779                0x0e7a710422002540,
780                0x300904418240c422,
781                0x80850ccad8a10200,
782                false,
783                true,
784            ),
785            (
786                0x90080028402bc624,
787                0x215002cf204840a0,
788                0x6373f01012001042,
789                0x420b111008350859,
790                false,
791                true,
792            ),
793            (
794                0x4220c41100513301,
795                0x332c050498c21102,
796                0x0c0c206c8a008044,
797                0xc0024840461484d0,
798                true,
799                false,
800            ),
801            (
802                0x0353a04b08000010,
803                0x3e00045295202851,
804                0x60040810a42a1284,
805                0x001d680860800080,
806                true,
807                false,
808            ),
809            (
810                0x084801c0c2100581,
811                0x1820090035001080,
812                0x3111121b0522185c,
813                0x01404209002c080c,
814                true,
815                false,
816            ),
817            (
818                0x414800000823a20e,
819                0x008074081080a214,
820                0x1a12852095d040c0,
821                0x8119003425575408,
822                false,
823                true,
824            ),
825            (
826                0x210c730112098440,
827                0x01c0b106111483d0,
828                0x920004486810020c,
829                0xb614405084c30004,
830                true,
831                true,
832            ),
833            (
834                0x60210168b8802094,
835                0x2a10021a4b08420c,
836                0x1554000102241028,
837                0x04048d0000349000,
838                true,
839                true,
840            ),
841            (
842                0x81200240041188c8,
843                0x148008c1c6220818,
844                0x0082a92c10000010,
845                0x0050500800100084,
846                true,
847                false,
848            ),
849            (
850                0x4593105c94090408,
851                0x820029daa0026830,
852                0x1864242101429200,
853                0x1822060103290348,
854                true,
855                false,
856            ),
857            (
858                0x551a0002870e6000,
859                0x0040a00040353a00,
860                0x200409c110101589,
861                0x28870e620a488442,
862                true,
863                false,
864            ),
865            (
866                0x8a0200806440124b,
867                0x9c6000904e824800,
868                0x5150404003022c84,
869                0x2014452420012031,
870                true,
871                false,
872            ),
873            (
874                0x840216c970c02c10,
875                0x16490c8222011000,
876                0x4a6040120034800b,
877                0x09008001d4166827,
878                false,
879                true,
880            ),
881            (
882                0x042040900809589c,
883                0x4102064021804040,
884                0x98903b221480a523,
885                0x964840081847130e,
886                false,
887                false,
888            ),
889            (
890                0xa005ed201240a002,
891                0x580903106014a842,
892                0x16680288c4321521,
893                0x2030400608021010,
894                true,
895                true,
896            ),
897            (
898                0x405008860b020123,
899                0x2100052200602aee,
900                0xb809422040018014,
901                0x0a21a20090041001,
902                true,
903                true,
904            ),
905            (
906                0x3108541538030498,
907                0x014302a04a20a081,
908                0x0080806005804804,
909                0xdc00700020cc405c,
910                true,
911                true,
912            ),
913            (
914                0x6020490087030a00,
915                0x008a11c320049998,
916                0x069512591824a091,
917                0x4a300a0808002006,
918                true,
919                true,
920            ),
921            (
922                0x206e90b404108a02,
923                0x4a0408221400b022,
924                0x0580040201607498,
925                0x0131d21d80080b08,
926                false,
927                false,
928            ),
929            (
930                0x84811204041e00bd,
931                0x011410092c824801,
932                0x0162802203216100,
933                0xd8200844514c8040,
934                false,
935                false,
936            ),
937            (
938                0x0020000005800845,
939                0x4c19021081244589,
940                0x56026e803008012a,
941                0x916081a350103000,
942                true,
943                true,
944            ),
945            (
946                0x407050c08808e102,
947                0x1102095040020904,
948                0x000187005245184c,
949                0x28104485228804e3,
950                true,
951                true,
952            ),
953            (
954                0x6d20550000808446,
955                0x4008211019808425,
956                0x804e20c004212381,
957                0x02305c0542603848,
958                false,
959                false,
960            ),
961            (
962                0x8010400016110202,
963                0x5a40a22409e0220c,
964                0x04e20103604a3980,
965                0x80181142f20a9103,
966                false,
967                true,
968            ),
969            (
970                0x002c12089073280e,
971                0x80c8680090b66020,
972                0xd8c12d02488850a0,
973                0x010217794101901c,
974                false,
975                true,
976            ),
977            (
978                0x290c01102e12800c,
979                0x4c881498c852154e,
980                0x86c0142101a810b2,
981                0x31420a2623a40091,
982                false,
983                true,
984            ),
985            (
986                0xe08400012018c888,
987                0x020204c23b0a1010,
988                0x0301230249420426,
989                0x01340a3084204282,
990                false,
991                true,
992            ),
993            (
994                0x4038ea62022e8480,
995                0x4098130044062cf8,
996                0x2400009810006028,
997                0xb200606800900100,
998                true,
999                true,
1000            ),
1001            (
1002                0x502000190002d410,
1003                0x0438100a01024d00,
1004                0x2217c2025085020a,
1005                0xa302e11110002008,
1006                false,
1007                false,
1008            ),
1009            (
1010                0x4200400240411212,
1011                0xb816804201c00229,
1012                0x94401924308a01c8,
1013                0x41203911e0009114,
1014                true,
1015                true,
1016            ),
1017            (
1018                0x00181012e8048110,
1019                0xa040200b8c000504,
1020                0xe2c08424148b3621,
1021                0x04a6473461be288b,
1022                false,
1023                false,
1024            ),
1025            (
1026                0x118930450a104281,
1027                0x601aa1629118e100,
1028                0x0072c190b1208908,
1029                0x8125461c400018cd,
1030                false,
1031                true,
1032            ),
1033            (
1034                0x6420649001148862,
1035                0xb8140a29851b311c,
1036                0x93c9180820881088,
1037                0x014040400a000040,
1038                true,
1039                true,
1040            ),
1041            (
1042                0x080622a043c60190,
1043                0x2103c10f04000312,
1044                0x1120404098087809,
1045                0x00000090f8918000,
1046                false,
1047                false,
1048            ),
1049            (
1050                0xc19e4204800b0b88,
1051                0x008040504c102020,
1052                0x3000844216406441,
1053                0x4e450203006dc014,
1054                false,
1055                false,
1056            ),
1057            (
1058                0xc0204c082c200c01,
1059                0x13046c600e0044c1,
1060                0x01cb111600005240,
1061                0x8012028130c18800,
1062                false,
1063                false,
1064            ),
1065            (
1066                0x80e1850014a56020,
1067                0x20055110c8011012,
1068                0x240422904200918e,
1069                0x10d02c21213442a0,
1070                true,
1071                true,
1072            ),
1073        ];
1074        let mut diffs = Vec::new();
1075        for &(in1_limb1, in1_limb2, in2_limb1, in2_limb2, res1, res2) in tests.iter() {
1076            in1.limbs_mut()[1] = in1_limb1;
1077            in1.limbs_mut()[0] = in1_limb2;
1078            in2.limbs_mut()[1] = in2_limb1;
1079            in2.limbs_mut()[0] = in2_limb2;
1080            let test_res1 = in1.sign_rule(&in2);
1081            let test_res2 = in2.sign_rule(&in1);
1082            let res = (res1, res2);
1083            let test_res = (test_res1, test_res2);
1084            let tuple = (in1_limb1, in1_limb2, in2_limb1, in2_limb2);
1085            let popcnts = (
1086                in1_limb1.count_ones() % 2,
1087                in1_limb2.count_ones() % 2,
1088                in2_limb1.count_ones() % 2,
1089                in2_limb2.count_ones() % 2,
1090            );
1091            if res != test_res {
1092                diffs.push((tuple, popcnts, res, test_res))
1093            }
1094        }
1095        if !diffs.is_empty() {
1096            let formatter = diffs
1097                .iter()
1098                .format_with("\n", |(tuple, popcnts, res, test_res), f| {
1099                    f(&format_args!(
1100                        "   Inputs: {tuple:x?}\n      expected {res:?}, got {test_res:?}. \
1101                         popcnts: {popcnts:?}"
1102                    ))
1103                });
1104            panic!("\nFailed test cases:\n {formatter}");
1105        }
1106    }
1107}
fp/vector/mod.rs

fp/vector/
mod.rs
