nostd_bv/traits/
bits.rs

1use super::BitsMut;
2use crate::storage::{Address, BlockType};
3use crate::BitVec;
4use alloc::{boxed::Box, vec::Vec};
5
6/// Read-only bit vector operations.
7///
8/// Minimal complete definition is:
9///
10///   - [`bit_len`] and
11///   - [`get_block`] or [`get_bit`].
12///
13/// Note that [`get_block`] in terms of [`get_bit`] is inefficient, and thus
14/// you should implement [`get_block`] directly if possible.
15///
16/// [`bit_len`]: #method.bit_len
17/// [`get_bit`]: #method.get_bit
18/// [`get_block`]: #method.get_block
19pub trait Bits {
20    /// The underlying block type used to store the bits of the vector.
21    type Block: BlockType;
22
23    /// The length of the slice in bits.
24    fn bit_len(&self) -> u64;
25
26    /// The length of the slice in blocks.
27    fn block_len(&self) -> usize {
28        Self::Block::ceil_div_nbits(self.bit_len())
29    }
30
31    /// Gets the bit at `position`
32    ///
33    /// The default implementation calls `get_block` and masks out the
34    /// correct bit.
35    ///
36    /// # Panics
37    ///
38    /// Panics if `position` is out of bounds.
39    fn get_bit(&self, position: u64) -> bool {
40        assert!(position < self.bit_len(), "Bits::get_bit: out of bounds");
41
42        let address = Address::new::<Self::Block>(position);
43        let block = self.get_raw_block(address.block_index);
44        block.get_bit(address.bit_offset)
45    }
46
47    /// Gets the block at `position`, masked as necessary.
48    ///
49    /// The bits are laid out `Block::nbits()` per block, with the notional
50    /// zeroth bit in the least significant position. If `self.bit_len()` is
51    /// not a multiple of `Block::nbits()` then the last block will
52    /// contain extra zero bits that are not part of the bit vector.
53    ///
54    /// The default implementation calls [`get_raw_block`](#method.get_raw_block),
55    /// but you can override with something more efficient, for example if masking
56    /// is unnecessary.
57    ///
58    /// # Panics
59    ///
60    /// Panics if `position` is out of bounds.
61    fn get_block(&self, position: usize) -> Self::Block {
62        assert!(
63            position < self.block_len(),
64            "Bits::get_block: out of bounds ({}/{})",
65            position,
66            self.block_len()
67        );
68
69        let first_bit = Self::Block::mul_nbits(position);
70        let bit_count = Self::Block::block_bits(self.bit_len(), position);
71
72        let mut result = Self::Block::zero();
73        let mut mask = Self::Block::one();
74
75        for i in 0..bit_count as u64 {
76            if self.get_bit(first_bit + i) {
77                result = result | mask;
78            }
79            mask = mask << 1;
80        }
81
82        result
83    }
84
85    /// Gets the block at `position`, without masking.
86    ///
87    /// The default implementation of this method just delegates to [`get_block`](#method
88    /// .get_block), which means it in fact does mask out extraneous bits. However, particular
89    /// implementors may override this method to provide a more efficient implementation when
90    /// one is possible.
91    ///
92    /// # Panics
93    ///
94    /// Panics if `position` is out of bounds.
95    fn get_raw_block(&self, position: usize) -> Self::Block {
96        self.get_block(position)
97    }
98
99    /// Gets `count` bits starting at bit index `start`, interpreted as a
100    /// little-endian integer.
101    ///
102    /// # Panics
103    ///
104    /// Panics if the bit span goes out of bounds.
105    fn get_bits(&self, start: u64, count: usize) -> Self::Block {
106        let limit = start + count as u64;
107        assert!(limit <= self.bit_len(), "Bits::get_bits: out of bounds");
108
109        let address = Address::new::<Self::Block>(start);
110        let margin = Self::Block::nbits() - address.bit_offset;
111
112        if margin >= count {
113            let block = self.get_raw_block(address.block_index);
114            return block.get_bits(address.bit_offset, count);
115        }
116
117        let extra = count - margin;
118
119        let block1 = self.get_raw_block(address.block_index);
120        let block2 = self.get_raw_block(address.block_index + 1);
121
122        let low_bits = block1.get_bits(address.bit_offset, margin);
123        let high_bits = block2.get_bits(0, extra);
124
125        (high_bits << margin) | low_bits
126    }
127
128    /// Copies the bits into a new allocated [`BitVec`].
129    ///
130    /// [`BitVec`]: ../struct.BitVec.html
131    fn to_bit_vec(&self) -> BitVec<Self::Block> {
132        BitVec::from_bits(self)
133    }
134}
135
136/// Gets a block using `get_raw_block` and then masks it appropriately.
137/// This can be used to implement `get_block` in terms of `get_raw_block`.
138pub(crate) fn get_masked_block<T: Bits>(bits: T, position: usize) -> T::Block {
139    let block_bits = T::Block::block_bits(bits.bit_len(), position);
140    bits.get_raw_block(position).get_bits(0, block_bits)
141}
142
143impl<T: Bits + ?Sized> Bits for &T {
144    type Block = T::Block;
145
146    fn bit_len(&self) -> u64 {
147        T::bit_len(*self)
148    }
149
150    fn block_len(&self) -> usize {
151        T::block_len(*self)
152    }
153
154    fn get_bit(&self, position: u64) -> bool {
155        T::get_bit(*self, position)
156    }
157
158    fn get_block(&self, position: usize) -> Self::Block {
159        T::get_block(*self, position)
160    }
161
162    fn get_raw_block(&self, position: usize) -> Self::Block {
163        T::get_raw_block(*self, position)
164    }
165
166    fn get_bits(&self, start: u64, count: usize) -> Self::Block {
167        T::get_bits(*self, start, count)
168    }
169}
170
171impl<T: Bits + ?Sized> Bits for &mut T {
172    type Block = T::Block;
173
174    fn bit_len(&self) -> u64 {
175        T::bit_len(*self)
176    }
177
178    fn block_len(&self) -> usize {
179        T::block_len(*self)
180    }
181
182    fn get_bit(&self, position: u64) -> bool {
183        T::get_bit(*self, position)
184    }
185
186    fn get_block(&self, position: usize) -> Self::Block {
187        T::get_block(*self, position)
188    }
189
190    fn get_raw_block(&self, position: usize) -> Self::Block {
191        T::get_raw_block(*self, position)
192    }
193
194    fn get_bits(&self, start: u64, count: usize) -> Self::Block {
195        T::get_bits(*self, start, count)
196    }
197}
198
199impl<Block: BlockType> Bits for Box<dyn Bits<Block = Block>> {
200    type Block = Block;
201
202    fn bit_len(&self) -> u64 {
203        (**self).bit_len()
204    }
205
206    fn block_len(&self) -> usize {
207        (**self).block_len()
208    }
209
210    fn get_bit(&self, position: u64) -> bool {
211        (**self).get_bit(position)
212    }
213
214    fn get_block(&self, position: usize) -> Self::Block {
215        (**self).get_block(position)
216    }
217
218    fn get_raw_block(&self, position: usize) -> Self::Block {
219        (**self).get_raw_block(position)
220    }
221
222    fn get_bits(&self, start: u64, count: usize) -> Self::Block {
223        (**self).get_bits(start, count)
224    }
225}
226
227impl<Block: BlockType> Bits for Box<dyn BitsMut<Block = Block>> {
228    type Block = Block;
229
230    fn bit_len(&self) -> u64 {
231        (**self).bit_len()
232    }
233
234    fn block_len(&self) -> usize {
235        (**self).block_len()
236    }
237
238    fn get_bit(&self, position: u64) -> bool {
239        (**self).get_bit(position)
240    }
241
242    fn get_block(&self, position: usize) -> Self::Block {
243        (**self).get_block(position)
244    }
245
246    fn get_raw_block(&self, position: usize) -> Self::Block {
247        (**self).get_raw_block(position)
248    }
249
250    fn get_bits(&self, start: u64, count: usize) -> Self::Block {
251        (**self).get_bits(start, count)
252    }
253}
254
255impl<Block: BlockType> Bits for [Block] {
256    type Block = Block;
257
258    fn bit_len(&self) -> u64 {
259        Block::mul_nbits(self.len())
260    }
261
262    fn block_len(&self) -> usize {
263        self.len()
264    }
265
266    fn get_bit(&self, position: u64) -> bool {
267        let address = Address::new::<Block>(position);
268        self[address.block_index].get_bit(address.bit_offset)
269    }
270
271    fn get_block(&self, position: usize) -> Block {
272        self[position]
273    }
274}
275
276impl<Block: BlockType> Bits for Vec<Block> {
277    type Block = Block;
278
279    fn bit_len(&self) -> u64 {
280        <[Block]>::bit_len(self)
281    }
282
283    fn block_len(&self) -> usize {
284        <[Block]>::block_len(self)
285    }
286
287    fn get_bit(&self, position: u64) -> bool {
288        <[Block]>::get_bit(self, position)
289    }
290
291    fn get_block(&self, position: usize) -> Block {
292        <[Block]>::get_block(self, position)
293    }
294
295    fn get_raw_block(&self, position: usize) -> Block {
296        <[Block]>::get_raw_block(self, position)
297    }
298}
299
300impl Bits for [bool] {
301    type Block = u8; // This is bogus
302
303    #[inline]
304    fn bit_len(&self) -> u64 {
305        self.len() as u64
306    }
307
308    #[inline]
309    fn get_bit(&self, position: u64) -> bool {
310        self[position.to_usize().expect("Vec<bool>::get_bit: overflow")]
311    }
312}
313
314impl Bits for Vec<bool> {
315    type Block = u8;
316
317    #[inline]
318    fn bit_len(&self) -> u64 {
319        self.as_slice().bit_len()
320    }
321
322    #[inline]
323    fn get_bit(&self, position: u64) -> bool {
324        self.as_slice().get_bit(position)
325    }
326}
nostd_bv/traits/bits.rs

nostd_bv/traits/
bits.rs
