bittle/
number.rs

1//! [Bits] associated types for primitive numbers.
2
3use core::iter::FusedIterator;
4use core::marker::PhantomData;
5
6use crate::bits::Bits;
7use crate::bits_mut::BitsMut;
8use crate::bits_owned::BitsOwned;
9use crate::endian::{DefaultEndian, Endian};
10
11mod sealed {
12    use core::ops::{BitOrAssign, BitXorAssign};
13
14    /// Basic numerical trait for the plumbing of a bit set. This ensures that only
15    /// primitive types can be used as the basis of a bit set backed by an array,
16    /// like `[u64; 4]` and not `[[u32; 2]; 4]`.
17    pub trait Number: Copy + BitXorAssign + BitOrAssign + Eq {
18        const ZEROS: Self;
19        const ONES: Self;
20        const BITS: u32;
21        const BIT_RIGHT: Self;
22        const BIT_LEFT: Self;
23
24        fn count_ones(self) -> u32;
25        fn count_zeros(self) -> u32;
26        fn trailing_ones(self) -> u32;
27        fn leading_ones(self) -> u32;
28        fn trailing_zeros(self) -> u32;
29        fn leading_zeros(self) -> u32;
30        fn wrapping_shl(self, index: u32) -> Self;
31        fn wrapping_shr(self, index: u32) -> Self;
32    }
33}
34
35pub(crate) use self::sealed::Number;
36
37macro_rules! number {
38    ($ty:ty) => {
39        impl Number for $ty {
40            const ONES: $ty = !0;
41            const ZEROS: $ty = 0;
42            const BITS: u32 = <$ty>::BITS;
43            const BIT_RIGHT: $ty = 1 as $ty;
44            const BIT_LEFT: $ty = !(<$ty>::MAX >> 1);
45
46            #[inline]
47            fn count_ones(self) -> u32 {
48                <$ty>::count_ones(self)
49            }
50
51            #[inline]
52            fn count_zeros(self) -> u32 {
53                <$ty>::count_zeros(self)
54            }
55
56            #[inline]
57            fn trailing_ones(self) -> u32 {
58                <$ty>::trailing_ones(self)
59            }
60
61            #[inline]
62            fn leading_ones(self) -> u32 {
63                <$ty>::leading_ones(self)
64            }
65
66            #[inline]
67            fn trailing_zeros(self) -> u32 {
68                <$ty>::trailing_zeros(self)
69            }
70
71            #[inline]
72            fn leading_zeros(self) -> u32 {
73                <$ty>::leading_zeros(self)
74            }
75
76            #[inline]
77            fn wrapping_shl(self, index: u32) -> Self {
78                <$ty>::wrapping_shl(self, index)
79            }
80
81            #[inline]
82            fn wrapping_shr(self, index: u32) -> Self {
83                <$ty>::wrapping_shr(self, index)
84            }
85        }
86
87        impl crate::bits::Sealed for $ty {}
88
89        impl Bits for $ty {
90            type IterOnes<'a> = IterOnes<Self, DefaultEndian> where Self: 'a;
91            type IterOnesIn<'a, E> = IterOnes<Self, E> where Self: 'a, E: Endian;
92            type IterZeros<'a> = IterZeros<Self, DefaultEndian> where Self: 'a;
93            type IterZerosIn<'a, E> = IterZeros<Self, E> where Self: 'a, E: Endian;
94
95            #[inline]
96            fn count_ones(&self) -> u32 {
97                <$ty>::count_ones(*self)
98            }
99
100            #[inline]
101            fn count_zeros(&self) -> u32 {
102                <$ty>::count_zeros(*self)
103            }
104
105            #[inline]
106            fn bits_capacity(&self) -> u32 {
107                <Self as Number>::BITS
108            }
109
110            #[inline]
111            fn all_zeros(&self) -> bool {
112                <$ty as Number>::ZEROS == *self
113            }
114
115            #[inline]
116            fn all_ones(&self) -> bool {
117                <$ty as Number>::ONES == *self
118            }
119
120            #[inline]
121            fn test_bit(&self, index: u32) -> bool {
122                self.test_bit_in::<DefaultEndian>(index)
123            }
124
125            #[inline]
126            fn test_bit_in<E>(&self, index: u32) -> bool
127            where
128                E: Endian,
129            {
130                *self & E::mask::<Self>(index) != 0
131            }
132
133            #[inline]
134            fn iter_ones(&self) -> Self::IterOnes<'_> {
135                IterOnes::new(*self)
136            }
137
138            #[inline]
139            fn iter_ones_in<E>(&self) -> Self::IterOnesIn<'_, E>
140            where
141                E: Endian,
142            {
143                IterOnes::new(*self)
144            }
145
146            #[inline]
147            fn iter_zeros(&self) -> Self::IterZeros<'_> {
148                IterZeros::new(*self)
149            }
150
151            #[inline]
152            fn iter_zeros_in<E>(&self) -> Self::IterZerosIn<'_, E>
153            where
154                E: Endian,
155            {
156                IterZeros::new(*self)
157            }
158        }
159
160        impl BitsMut for $ty {
161            #[inline]
162            fn set_bit_in<E>(&mut self, index: u32)
163            where
164                E: Endian,
165            {
166                *self |= E::mask::<Self>(index);
167            }
168
169            #[inline]
170            fn set_bit(&mut self, index: u32) {
171                self.set_bit_in::<DefaultEndian>(index);
172            }
173
174            #[inline]
175            fn clear_bit_in<E>(&mut self, index: u32)
176            where
177                E: Endian,
178            {
179                *self &= !E::mask::<Self>(index);
180            }
181
182            #[inline]
183            fn clear_bit(&mut self, index: u32) {
184                self.clear_bit_in::<DefaultEndian>(index);
185            }
186
187            #[inline]
188            fn union_assign(&mut self, other: &Self) {
189                *self |= other;
190            }
191
192            #[inline]
193            fn conjunction_assign(&mut self, other: &Self) {
194                *self &= other;
195            }
196
197            #[inline]
198            fn difference_assign(&mut self, other: &Self) {
199                *self &= !other;
200            }
201
202            #[inline]
203            fn symmetric_difference_assign(&mut self, other: &Self) {
204                *self ^= other;
205            }
206
207            #[inline]
208            fn clear_bits(&mut self) {
209                *self = <$ty as Number>::ZEROS;
210            }
211        }
212
213        impl BitsOwned for $ty {
214            const BITS: u32 = <$ty as Number>::BITS;
215            const ZEROS: Self = <$ty as Number>::ZEROS;
216            const ONES: Self = <$ty as Number>::ONES;
217
218            type IntoIterOnes = IterOnes<Self, DefaultEndian>;
219            type IntoIterOnesIn<E> = IterOnes<Self, E> where E: Endian;
220            type IntoIterZeros = IterZeros<Self, DefaultEndian>;
221            type IntoIterZerosIn<E> = IterZeros<Self, E> where E: Endian;
222
223            #[inline]
224            fn zeros() -> Self {
225                <$ty as Number>::ZEROS
226            }
227
228            #[inline]
229            fn ones() -> Self {
230                <$ty as Number>::ONES
231            }
232
233            #[inline]
234            fn with_bit(self, bit: u32) -> Self {
235                self.with_bit_in::<DefaultEndian>(bit)
236            }
237
238            #[inline]
239            fn with_bit_in<E>(self, bit: u32) -> Self
240            where
241                E: Endian,
242            {
243                self | E::mask::<Self>(bit)
244            }
245
246            #[inline]
247            fn without_bit(self, bit: u32) -> Self {
248                self.without_bit_in::<DefaultEndian>(bit)
249            }
250
251            #[inline]
252            fn without_bit_in<E>(self, bit: u32) -> Self
253            where
254                E: Endian,
255            {
256                self & !E::mask::<Self>(bit)
257            }
258
259            #[inline]
260            fn union(self, other: Self) -> Self {
261                self | other
262            }
263
264            #[inline]
265            fn conjunction(self, other: Self) -> Self {
266                self & other
267            }
268
269            #[inline]
270            fn difference(self, other: Self) -> Self {
271                self & !other
272            }
273
274            #[inline]
275            fn symmetric_difference(self, other: Self) -> Self {
276                self ^ other
277            }
278
279            #[inline]
280            fn into_iter_ones(self) -> Self::IntoIterOnes {
281                IterOnes::new(self)
282            }
283
284            #[inline]
285            fn into_iter_ones_in<E>(self) -> Self::IntoIterOnesIn<E>
286            where
287                E: Endian,
288            {
289                IterOnes::new(self)
290            }
291
292            #[inline]
293            fn into_iter_zeros(self) -> Self::IntoIterZeros {
294                IterZeros::new(self)
295            }
296
297            #[inline]
298            fn into_iter_zeros_in<E>(self) -> Self::IntoIterZerosIn<E>
299            where
300                E: Endian,
301            {
302                IterZeros::new(self)
303            }
304        }
305    };
306}
307
308number!(usize);
309number!(isize);
310number!(u8);
311number!(i8);
312number!(u16);
313number!(i16);
314number!(u32);
315number!(i32);
316number!(u64);
317number!(i64);
318number!(u128);
319number!(i128);
320
321/// An iterator over ones in a primitive number.
322#[derive(Clone)]
323#[repr(transparent)]
324pub struct IterOnes<T, E> {
325    bits: T,
326    _shift: PhantomData<E>,
327}
328
329impl<T, E> IterOnes<T, E> {
330    #[inline]
331    const fn new(bits: T) -> Self {
332        Self {
333            bits,
334            _shift: PhantomData,
335        }
336    }
337}
338
339/// Iterator over ones.
340///
341/// # Examples
342///
343/// ```
344/// use bittle::Bits;
345///
346/// let n: u8 = bittle::set![0, 4];
347/// assert!(n.iter_ones().eq([0, 4]));
348/// ```
349impl<T, E> Iterator for IterOnes<T, E>
350where
351    T: Number,
352    E: Endian,
353{
354    type Item = u32;
355
356    #[inline]
357    fn next(&mut self) -> Option<Self::Item> {
358        if self.bits == T::ZEROS {
359            return None;
360        }
361
362        let index = E::zeros(self.bits);
363        self.bits ^= E::mask::<T>(index);
364        Some(index)
365    }
366}
367
368/// Double ended iterator over ones.
369///
370/// # Examples
371///
372/// ```
373/// use bittle::Bits;
374///
375/// let n: u8 = bittle::set![0, 4];
376/// assert!(n.iter_ones().rev().eq([4, 0]));
377/// ```
378impl<T, E> DoubleEndedIterator for IterOnes<T, E>
379where
380    T: Number,
381    E: Endian,
382{
383    #[inline]
384    fn next_back(&mut self) -> Option<Self::Item> {
385        if self.bits == T::ZEROS {
386            return None;
387        }
388
389        let index = T::BITS.wrapping_sub(E::zeros_rev(self.bits).wrapping_add(1));
390
391        self.bits ^= E::mask::<T>(index);
392        Some(index)
393    }
394}
395
396/// Exact size iterator over ones.
397///
398/// # Examples
399///
400/// ```
401/// use bittle::Bits;
402///
403/// let n: u8 = bittle::set![0, 4];
404/// assert_eq!(n.iter_ones().len(), 2);
405/// ```
406impl<T, E> ExactSizeIterator for IterOnes<T, E>
407where
408    T: Number,
409    E: Endian,
410{
411    #[inline]
412    fn len(&self) -> usize {
413        self.bits.count_ones() as usize
414    }
415}
416
417impl<T, E> FusedIterator for IterOnes<T, E>
418where
419    T: Number,
420    E: Endian,
421{
422}
423
424/// An iterator over zeros in a primitive number.
425#[derive(Clone)]
426#[repr(transparent)]
427pub struct IterZeros<T, E> {
428    bits: T,
429    _shift: PhantomData<E>,
430}
431
432impl<T, E> IterZeros<T, E> {
433    #[inline]
434    const fn new(bits: T) -> Self {
435        Self {
436            bits,
437            _shift: PhantomData,
438        }
439    }
440}
441
442/// Iterator over zeros.
443///
444/// # Examples
445///
446/// ```
447/// use bittle::Bits;
448///
449/// let n: u8 = bittle::set![0, 4, 6];
450/// assert!(n.iter_zeros().eq([1, 2, 3, 5, 7]));
451/// ```
452impl<T, E> Iterator for IterZeros<T, E>
453where
454    T: Number,
455    E: Endian,
456{
457    type Item = u32;
458
459    #[inline]
460    fn next(&mut self) -> Option<Self::Item> {
461        if self.bits == T::ONES {
462            return None;
463        }
464
465        let index = E::ones(self.bits);
466        self.bits |= E::mask::<T>(index);
467        Some(index)
468    }
469}
470
471/// Exact size iterator over zeros.
472///
473/// # Examples
474///
475/// ```
476/// use bittle::Bits;
477///
478/// let n: u8 = bittle::set![0, 4];
479/// assert_eq!(n.iter_zeros().len(), 6);
480/// ```
481impl<T, E> ExactSizeIterator for IterZeros<T, E>
482where
483    T: Number,
484    E: Endian,
485{
486    #[inline]
487    fn len(&self) -> usize {
488        self.bits.count_zeros() as usize
489    }
490}
491
492/// Double ended iterator over zeros.
493///
494/// # Examples
495///
496/// ```
497/// use bittle::Bits;
498///
499/// let n: u8 = bittle::set![0, 4, 6];
500/// assert!(n.iter_zeros().rev().eq([7, 5, 3, 2, 1]));
501/// ```
502impl<T, E> DoubleEndedIterator for IterZeros<T, E>
503where
504    T: Number,
505    E: Endian,
506{
507    #[inline]
508    fn next_back(&mut self) -> Option<Self::Item> {
509        if self.bits == T::ONES {
510            return None;
511        }
512
513        let index = T::BITS.wrapping_sub(E::ones_rev(self.bits).wrapping_add(1));
514        self.bits |= E::mask::<T>(index);
515        Some(index)
516    }
517}
518
519impl<T, E> FusedIterator for IterZeros<T, E>
520where
521    T: Number,
522    E: Endian,
523{
524}
bittle/number.rs

bittle/
number.rs
