ark_ff/
bits.rs

1/// Iterates over a slice of `u64` in *big-endian* order.
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
32            Some(self.s.as_ref()[part] & (1 << bit) > 0)
33        }
34    }
35}
36
37/// Iterates over a slice of `u64` in *little-endian* order.
38#[derive(Debug)]
39pub struct BitIteratorLE<Slice: AsRef<[u64]>> {
40    s: Slice,
41    n: usize,
42    max_len: usize,
43}
44
45impl<Slice: AsRef<[u64]>> BitIteratorLE<Slice> {
46    pub fn new(s: Slice) -> Self {
47        let n = 0;
48        let max_len = s.as_ref().len() * 64;
49        BitIteratorLE { s, n, max_len }
50    }
51
52    /// Construct an iterator that automatically skips any trailing zeros.
53    /// That is, it skips all zeros after the most-significant one.
54    pub fn without_trailing_zeros(s: Slice) -> impl Iterator<Item = bool> {
55        let mut first_trailing_zero = 0;
56        for (i, limb) in s.as_ref().iter().enumerate().rev() {
57            first_trailing_zero = i * 64 + (64 - limb.leading_zeros()) as usize;
58            if *limb != 0 {
59                break;
60            }
61        }
62        let mut iter = Self::new(s);
63        iter.max_len = first_trailing_zero;
64        iter
65    }
66}
67
68impl<Slice: AsRef<[u64]>> Iterator for BitIteratorLE<Slice> {
69    type Item = bool;
70
71    fn next(&mut self) -> Option<bool> {
72        if self.n == self.max_len {
73            None
74        } else {
75            let part = self.n / 64;
76            let bit = self.n - (64 * part);
77            self.n += 1;
78
79            Some(self.s.as_ref()[part] & (1 << bit) > 0)
80        }
81    }
82}
ark_ff/bits.rs

ark_ff/
bits.rs
