1 use super::group::{ 2 BitMaskWord, NonZeroBitMaskWord, BITMASK_ITER_MASK, BITMASK_MASK, BITMASK_STRIDE, 3 }; 4 5 /// A bit mask which contains the result of a `Match` operation on a `Group` and 6 /// allows iterating through them. 7 /// 8 /// The bit mask is arranged so that low-order bits represent lower memory 9 /// addresses for group match results. 10 /// 11 /// For implementation reasons, the bits in the set may be sparsely packed with 12 /// groups of 8 bits representing one element. If any of these bits are non-zero 13 /// then this element is considered to true in the mask. If this is the 14 /// case, `BITMASK_STRIDE` will be 8 to indicate a divide-by-8 should be 15 /// performed on counts/indices to normalize this difference. `BITMASK_MASK` is 16 /// similarly a mask of all the actually-used bits. 17 /// 18 /// To iterate over a bit mask, it must be converted to a form where only 1 bit 19 /// is set per element. This is done by applying `BITMASK_ITER_MASK` on the 20 /// mask bits. 21 #[derive(Copy, Clone)] 22 pub(crate) struct BitMask(pub(crate) BitMaskWord); 23 24 #[allow(clippy::use_self)] 25 impl BitMask { 26 /// Returns a new `BitMask` with all bits inverted. 27 #[inline] 28 #[must_use] 29 #[allow(dead_code)] invert(self) -> Self30 pub(crate) fn invert(self) -> Self { 31 BitMask(self.0 ^ BITMASK_MASK) 32 } 33 34 /// Returns a new `BitMask` with the lowest bit removed. 35 #[inline] 36 #[must_use] remove_lowest_bit(self) -> Self37 fn remove_lowest_bit(self) -> Self { 38 BitMask(self.0 & (self.0 - 1)) 39 } 40 41 /// Returns whether the `BitMask` has at least one set bit. 42 #[inline] any_bit_set(self) -> bool43 pub(crate) fn any_bit_set(self) -> bool { 44 self.0 != 0 45 } 46 47 /// Returns the first set bit in the `BitMask`, if there is one. 48 #[inline] lowest_set_bit(self) -> Option<usize>49 pub(crate) fn lowest_set_bit(self) -> Option<usize> { 50 if let Some(nonzero) = NonZeroBitMaskWord::new(self.0) { 51 Some(Self::nonzero_trailing_zeros(nonzero)) 52 } else { 53 None 54 } 55 } 56 57 /// Returns the number of trailing zeroes in the `BitMask`. 58 #[inline] trailing_zeros(self) -> usize59 pub(crate) fn trailing_zeros(self) -> usize { 60 // ARM doesn't have a trailing_zeroes instruction, and instead uses 61 // reverse_bits (RBIT) + leading_zeroes (CLZ). However older ARM 62 // versions (pre-ARMv7) don't have RBIT and need to emulate it 63 // instead. Since we only have 1 bit set in each byte on ARM, we can 64 // use swap_bytes (REV) + leading_zeroes instead. 65 if cfg!(target_arch = "arm") && BITMASK_STRIDE % 8 == 0 { 66 self.0.swap_bytes().leading_zeros() as usize / BITMASK_STRIDE 67 } else { 68 self.0.trailing_zeros() as usize / BITMASK_STRIDE 69 } 70 } 71 72 /// Same as above but takes a `NonZeroBitMaskWord`. 73 #[inline] nonzero_trailing_zeros(nonzero: NonZeroBitMaskWord) -> usize74 fn nonzero_trailing_zeros(nonzero: NonZeroBitMaskWord) -> usize { 75 if cfg!(target_arch = "arm") && BITMASK_STRIDE % 8 == 0 { 76 // SAFETY: A byte-swapped non-zero value is still non-zero. 77 let swapped = unsafe { NonZeroBitMaskWord::new_unchecked(nonzero.get().swap_bytes()) }; 78 swapped.leading_zeros() as usize / BITMASK_STRIDE 79 } else { 80 nonzero.trailing_zeros() as usize / BITMASK_STRIDE 81 } 82 } 83 84 /// Returns the number of leading zeroes in the `BitMask`. 85 #[inline] leading_zeros(self) -> usize86 pub(crate) fn leading_zeros(self) -> usize { 87 self.0.leading_zeros() as usize / BITMASK_STRIDE 88 } 89 } 90 91 impl IntoIterator for BitMask { 92 type Item = usize; 93 type IntoIter = BitMaskIter; 94 95 #[inline] into_iter(self) -> BitMaskIter96 fn into_iter(self) -> BitMaskIter { 97 // A BitMask only requires each element (group of bits) to be non-zero. 98 // However for iteration we need each element to only contain 1 bit. 99 BitMaskIter(BitMask(self.0 & BITMASK_ITER_MASK)) 100 } 101 } 102 103 /// Iterator over the contents of a `BitMask`, returning the indices of set 104 /// bits. 105 #[derive(Clone)] 106 pub(crate) struct BitMaskIter(pub(crate) BitMask); 107 108 impl Iterator for BitMaskIter { 109 type Item = usize; 110 111 #[inline] next(&mut self) -> Option<usize>112 fn next(&mut self) -> Option<usize> { 113 let bit = self.0.lowest_set_bit()?; 114 self.0 = self.0.remove_lowest_bit(); 115 Some(bit) 116 } 117 } 118