pathfinder_crypto/algebra/field/
bits.rs

1/// Iterates over a slice of `u64` in *big-endian* order, from arkworks.
2#[derive(Debug)]
3pub struct BitIteratorBE<Slice: AsRef<[u64]>> {
4    s: Slice,
5    n: usize,
6}
7
8impl<Slice: AsRef<[u64]>> BitIteratorBE<Slice> {
9    pub fn new(s: Slice) -> Self {
10        let n = s.as_ref().len() * 64;
11        BitIteratorBE { s, n }
12    }
13
14    /// Construct an iterator that automatically skips any leading zeros.
15    /// That is, it skips all zeros before the most-significant one.
16    pub fn without_leading_zeros(s: Slice) -> impl Iterator<Item = bool> {
17        Self::new(s).skip_while(|b| !b)
18    }
19}
20
21impl<Slice: AsRef<[u64]>> Iterator for BitIteratorBE<Slice> {
22    type Item = bool;
23
24    fn next(&mut self) -> Option<bool> {
25        if self.n == 0 {
26            None
27        } else {
28            self.n -= 1;
29            let part = self.n / 64;
30            let bit = self.n - (64 * part);
31            Some(self.s.as_ref()[part] & (1 << bit) > 0)
32        }
33    }
34}
35
36/// Iterates over a slice of `u64` in *little-endian* order, from arkworks.
37#[derive(Debug)]
38pub struct BitIteratorLE<Slice: AsRef<[u64]>> {
39    s: Slice,
40    n: usize,
41    max_len: usize,
42}
43
44impl<Slice: AsRef<[u64]>> BitIteratorLE<Slice> {
45    pub fn new(s: Slice) -> Self {
46        let n = 0;
47        let max_len = s.as_ref().len() * 64;
48        BitIteratorLE { s, n, max_len }
49    }
50
51    /// Construct an iterator that automatically skips any trailing zeros.
52    /// That is, it skips all zeros after the most-significant one.
53    pub fn without_trailing_zeros(s: Slice) -> impl Iterator<Item = bool> {
54        let mut first_trailing_zero = 0;
55        for (i, limb) in s.as_ref().iter().enumerate().rev() {
56            first_trailing_zero = i * 64 + (64 - limb.leading_zeros()) as usize;
57            if *limb != 0 {
58                break;
59            }
60        }
61        let mut iter = Self::new(s);
62        iter.max_len = first_trailing_zero;
63        iter
64    }
65}
66
67impl<Slice: AsRef<[u64]>> Iterator for BitIteratorLE<Slice> {
68    type Item = bool;
69
70    fn next(&mut self) -> Option<bool> {
71        if self.n == self.max_len {
72            None
73        } else {
74            let part = self.n / 64;
75            let bit = self.n - (64 * part);
76            self.n += 1;
77
78            Some(self.s.as_ref()[part] & (1 << bit) > 0)
79        }
80    }
81}
pathfinder_crypto/algebra/field/bits.rs

pathfinder_crypto/algebra/field/
bits.rs
