Skip to main content

utils/parser/
bits.rs

1use crate::number::UnsignedInteger;
2use crate::parser::{Leaf, LeafResult, ParseError};
3use std::marker::PhantomData;
4
5#[derive(Copy, Clone)]
6pub struct BitmaskParser<U: UnsignedInteger> {
7    bytes: &'static [u8; 2],
8    _phantom: PhantomData<U>,
9}
10impl<'i, U: UnsignedInteger> Leaf<'i> for BitmaskParser<U> {
11    type Output = (U, u32);
12
13    #[inline(always)]
14    fn parse(&self, input: &'i [u8]) -> LeafResult<'i, Self::Output> {
15        let [zero, one] = *self.bytes;
16        let (mut value, mut len) = (U::ZERO, 0);
17
18        // Bits are inserted at the top so every shift is constant
19        while len + 8 <= U::BITS
20            && let Some(&chunk) = input[len as usize..].first_chunk()
21            && let Some(packed) = pack(chunk, zero, one)
22        {
23            // Shift twice as u8 can't be shifted by 8 at once
24            value = (value >> 4 >> 4) | (U::from(packed) << (U::BITS - 8));
25            len += 8;
26        }
27        while let Some(&byte) = input.get(len as usize)
28            && (byte == zero || byte == one)
29        {
30            if len == U::BITS {
31                return Err((
32                    ParseError::ExpectedLessItems(U::BITS as usize),
33                    &input[len as usize..],
34                ));
35            }
36            value = (value >> 1) | (U::from(byte == one) << (U::BITS - 1));
37            len += 1;
38        }
39
40        if len == 0 {
41            return Err((ParseError::ExpectedOneOfBytes(self.bytes), input));
42        }
43
44        Ok(((value >> (U::BITS - len), len), &input[len as usize..]))
45    }
46}
47
48#[inline]
49fn pack(chunk: [u8; 8], zero: u8, one: u8) -> Option<u8> {
50    const LOW_BITS: u64 = 0x0101_0101_0101_0101;
51    let xor = zero ^ one;
52
53    // XORing with `zero` turns valid bytes into either 0 or `zero ^ one`
54    let difference = u64::from_le_bytes(chunk) ^ (u64::from(zero) * LOW_BITS);
55    let ones = (difference >> xor.trailing_zeros()) & LOW_BITS;
56    if difference != ones * u64::from(xor) {
57        return None;
58    }
59
60    // Multiply the low bits of each byte into a single u8
61    Some((ones.wrapping_mul(0x0102_0408_1020_4080) >> 56) as u8)
62}
63
64/// [`Leaf`] parser for strings made of two different bytes, packed into a bitmask.
65///
66/// Bytes in the input matching the first provided byte are mapped to 0 bits, and bytes matching the
67/// second provided byte are mapped to 1 bits.
68///
69/// The first input byte is put in the least significant bit. Returns the bitmask and its length, or
70/// an error if the string is empty or too long for the integer type.
71///
72/// # Examples
73/// ```
74/// # use utils::parser::{self, Leaf};
75/// let parser = parser::bitmask::<u8>(b".#");
76/// assert_eq!(
77///     parser.parse(b"#.###. abc"),
78///     Ok(((0b011101, 6), &b" abc"[..]))
79/// );
80/// assert_eq!(
81///     parser.parse(b".##...##"),
82///     Ok(((0b11000110, 8), &b""[..]))
83/// );
84/// assert!(parser.parse(b"abc").is_err());
85/// assert!(parser.parse(b"#########").is_err());
86///
87/// let parser = parser::bitmask::<u64>(b".#");
88/// assert_eq!(
89///     parser.parse(b".##...####.....######.......######## 123"),
90///     Ok(((0b111111110000000111111000001111000110, 36), &b" 123"[..]))
91/// );
92/// ```
93#[inline]
94#[must_use]
95pub fn bitmask<U: UnsignedInteger>(bytes: &'static [u8; 2]) -> BitmaskParser<U> {
96    BitmaskParser {
97        bytes,
98        _phantom: PhantomData,
99    }
100}
101
102#[derive(Copy, Clone)]
103pub struct BitmaskExactParser<const N: usize, U: UnsignedInteger> {
104    bytes: &'static [u8; 2],
105    _phantom: PhantomData<U>,
106}
107impl<'i, const N: usize, U: UnsignedInteger> Leaf<'i> for BitmaskExactParser<N, U> {
108    type Output = U;
109
110    #[inline(always)]
111    fn parse(&self, input: &'i [u8]) -> LeafResult<'i, Self::Output> {
112        let [zero, one] = *self.bytes;
113        if let Some((bytes, remaining)) = input.split_first_chunk::<N>()
114            && let Some(value) = pack_exact(bytes, zero, one)
115        {
116            return Ok((value, remaining));
117        }
118
119        let valid = input.iter().take_while(|&&b| b == zero || b == one).count();
120        Err((ParseError::ExpectedOneOfBytes(self.bytes), &input[valid..]))
121    }
122}
123
124#[inline]
125#[expect(clippy::cast_possible_truncation)]
126fn pack_exact<const N: usize, U: UnsignedInteger>(bytes: &[u8; N], zero: u8, one: u8) -> Option<U> {
127    let mut value = U::ZERO;
128    for (i, chunk) in bytes.chunks(8).enumerate() {
129        let mut padded = [zero; 8];
130        padded[..chunk.len()].copy_from_slice(chunk);
131        value |= U::from(pack(padded, zero, one)?) << (i * 8) as u32;
132    }
133    Some(value)
134}
135
136/// [`Leaf`] parser for [`bitmask`] strings exactly `N` long.
137///
138/// # Examples
139/// ```
140/// # use utils::parser::{self, Leaf};
141/// let parser = parser::bitmask_n::<10, u16>(b".#");
142/// assert_eq!(
143///     parser.parse(b"#.###....# abc"),
144///     Ok((0b10_0001_1101, &b" abc"[..]))
145/// );
146/// assert_eq!(
147///     parser.parse(b"#.###....##"),
148///     Ok((0b10_0001_1101, &b"#"[..]))
149/// );
150/// assert!(parser.parse(b"#.###....").is_err());
151/// assert!(parser.parse(b"#.###x...#").is_err());
152/// ```
153#[inline]
154#[must_use]
155pub fn bitmask_n<const N: usize, U: UnsignedInteger>(
156    bytes: &'static [u8; 2],
157) -> BitmaskExactParser<N, U> {
158    const {
159        assert!(N > 0 && N <= U::BITS as usize);
160    }
161    BitmaskExactParser {
162        bytes,
163        _phantom: PhantomData,
164    }
165}