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        Self { 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        Self { 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}
83
84#[cfg(test)]
85mod tests {
86    use super::*;
87    use ark_std::{vec, vec::Vec};
88
89    #[test]
90    fn test_bit_iterator_be() {
91        // Test with a simple case of a single 64-bit integer: 0b1010
92        let data = [0b1010u64];
93        let mut iter = BitIteratorBE::new(&data);
94
95        // The iterator should return the bits in big-endian order
96        // The first 60 bits are zeros
97        for _ in 0..60 {
98            assert_eq!(iter.next(), Some(false));
99        }
100        assert_eq!(iter.next(), Some(true)); // 3rd bit
101        assert_eq!(iter.next(), Some(false)); // 2nd bit
102        assert_eq!(iter.next(), Some(true)); // 1st bit
103        assert_eq!(iter.next(), Some(false)); // 0th bit
104        assert_eq!(iter.next(), None); // End of iteration
105
106        // Test with the without_leading_zeros method
107        let data = [0b0000_0000_0000_0000_0000_0000_0000_1010u64];
108        let iter: Vec<bool> = BitIteratorBE::without_leading_zeros(&data).collect();
109        assert_eq!(iter, vec![true, false, true, false]); // Only the significant bits
110
111        // Test with all zeros
112        let data = [0u64];
113        let iter: Vec<bool> = BitIteratorBE::without_leading_zeros(&data).collect();
114        assert!(iter.is_empty()); // Should be empty because all bits are zeros
115    }
116
117    #[test]
118    fn test_bit_iterator_le() {
119        // Test with a simple case of a single 64-bit integer: 0b1010
120        let data = [0b1010u64];
121        let mut iter = BitIteratorLE::new(&data);
122
123        // The iterator should return the bits in little-endian order
124        assert_eq!(iter.next(), Some(false)); // 0th bit
125        assert_eq!(iter.next(), Some(true)); // 1st bit
126        assert_eq!(iter.next(), Some(false)); // 2nd bit
127        assert_eq!(iter.next(), Some(true)); // 3rd bit
128        for _ in 4..64 {
129            assert_eq!(iter.next(), Some(false)); // The remaining bits are zeros
130        }
131        assert_eq!(iter.next(), None); // End of iteration
132
133        // Test with the without_trailing_zeros method
134        let data = [0b0000_0000_0000_0000_0000_0000_0000_1010u64];
135        let iter: Vec<bool> = BitIteratorLE::without_trailing_zeros(&data).collect();
136        assert_eq!(iter, vec![false, true, false, true]); // Only the significant bits
137
138        // Test with all zeros
139        let data = [0u64];
140        let iter: Vec<bool> = BitIteratorLE::without_trailing_zeros(&data).collect();
141        assert!(iter.is_empty()); // Should be empty because all bits are zeros
142    }
143
144    #[test]
145    fn test_bit_iterator_be_multiple_integers() {
146        // Test with multiple 64-bit integers: [0b1010, 0b1111]
147        let data = [0b1010u64, 0b1111u64];
148        let mut iter = BitIteratorBE::new(&data);
149
150        // First integer (0b1111) in big-endian order
151        for _ in 0..60 {
152            assert_eq!(iter.next(), Some(false));
153        }
154        assert_eq!(iter.next(), Some(true));
155        assert_eq!(iter.next(), Some(true));
156        assert_eq!(iter.next(), Some(true));
157        assert_eq!(iter.next(), Some(true));
158
159        // Second integer (0b1010) in big-endian order
160        for _ in 0..60 {
161            assert_eq!(iter.next(), Some(false));
162        }
163        assert_eq!(iter.next(), Some(true));
164        assert_eq!(iter.next(), Some(false));
165        assert_eq!(iter.next(), Some(true));
166        assert_eq!(iter.next(), Some(false));
167        assert_eq!(iter.next(), None); // End of iteration
168    }
169
170    #[test]
171    fn test_bit_iterator_le_multiple_integers() {
172        // Test with multiple 64-bit integers: [0b1010, 0b1111]
173        let data = [0b1010u64, 0b1111u64];
174        let mut iter = BitIteratorLE::new(&data);
175
176        // First integer (0b1010) in little-endian order
177        assert_eq!(iter.next(), Some(false));
178        assert_eq!(iter.next(), Some(true));
179        assert_eq!(iter.next(), Some(false));
180        assert_eq!(iter.next(), Some(true));
181        for _ in 4..64 {
182            assert_eq!(iter.next(), Some(false));
183        }
184
185        // Second integer (0b1111) in little-endian order
186        assert_eq!(iter.next(), Some(true));
187        assert_eq!(iter.next(), Some(true));
188        assert_eq!(iter.next(), Some(true));
189        assert_eq!(iter.next(), Some(true));
190        for _ in 4..64 {
191            assert_eq!(iter.next(), Some(false));
192        }
193        assert_eq!(iter.next(), None); // End of iteration
194    }
195}
ark_ff/bits.rs

ark_ff/
bits.rs
