read_fonts/collections/int_set/
input_bit_stream.rs

Help
1//! Reads individual bits from a array of bytes.
2
3use super::sparse_bit_set::BranchFactor;
4
5pub(crate) struct InputBitStream<'a, const BF: u8> {
6    data: &'a [u8],
7    byte_index: usize,
8    sub_index: u32,
9}
10
11impl<const BF: u8> Iterator for InputBitStream<'_, BF> {
12    type Item = u32;
13    fn next(&mut self) -> Option<Self::Item> {
14        match BF {
15            2 | 4 => {
16                let mask = (1 << BF) - 1;
17                let byte = self.data.get(self.byte_index)?;
18                let val = (*byte as u32 & (mask << self.sub_index)) >> self.sub_index;
19                self.sub_index = (self.sub_index + BF as u32) % 8;
20                if self.sub_index == 0 {
21                    self.byte_index += 1;
22                }
23                Some(val)
24            }
25            8 => {
26                let r = self.data.get(self.byte_index).map(|v| *v as u32)?;
27                self.byte_index += 1;
28                Some(r)
29            }
30
31            32 => {
32                let b1 = self.data.get(self.byte_index).map(|v| *v as u32)?;
33                let b2 = self.data.get(self.byte_index + 1).map(|v| *v as u32)?;
34                let b3 = self.data.get(self.byte_index + 2).map(|v| *v as u32)?;
35                let b4 = self.data.get(self.byte_index + 3).map(|v| *v as u32)?;
36                self.byte_index += 4;
37                Some(b1 | (b2 << 8) | (b3 << 16) | (b4 << 24))
38            }
39            _ => panic!("Unsupported branch factor."),
40        }
41    }
42}
43
44impl<'a, const BF: u8> InputBitStream<'a, BF> {
45    /// Decodes and returns the branch factor and height encoded in the header byte.
46    ///
47    /// See: <https://w3c.github.io/IFT/Overview.html#sparse-bit-set-decoding>
48    /// Returns None if the stream does not have enough remaining bits.
49    #[allow(clippy::unusual_byte_groupings)] // Used to separate bit values into units used in the set encoding.
50    pub(crate) fn decode_header(data: &'a [u8]) -> Option<(BranchFactor, u8)> {
51        let first_byte = data.first()?;
52        let bf_bits = 0b0_00000_11 & first_byte;
53        let depth_bits = (0b0_11111_00 & first_byte) >> 2;
54
55        let branch_factor = match bf_bits {
56            0b00 => BranchFactor::Two,
57            0b01 => BranchFactor::Four,
58            0b10 => BranchFactor::Eight,
59            0b11 => BranchFactor::ThirtyTwo,
60            _ => panic!("Invalid branch factor encoding."),
61        };
62
63        Some((branch_factor, depth_bits))
64    }
65
66    pub(crate) fn from(data: &'a [u8]) -> Self {
67        Self {
68            data,
69            byte_index: 1,
70            sub_index: 0,
71        }
72    }
73
74    /// Skips the given number of nodes, returns true if this did not overrun the data buffer.
75    pub(crate) fn skip_nodes(&mut self, n: u32) -> bool {
76        match BF {
77            2 | 4 => {
78                let bit_index = self.sub_index + n * (BF as u32);
79                self.byte_index += (bit_index / 8) as usize;
80                self.sub_index = bit_index % 8;
81            }
82            8 => {
83                self.byte_index += n as usize;
84            }
85
86            32 => {
87                self.byte_index += 4 * (n as usize);
88            }
89            _ => panic!("Unsupported branch factor."),
90        };
91
92        self.bytes_consumed() <= self.data.len()
93    }
94
95    /// Returns the number of bytes consumed so far (including partially consumed).
96    pub(crate) fn bytes_consumed(&self) -> usize {
97        self.byte_index + if self.sub_index > 0 { 1 } else { 0 }
98    }
99}
100
101#[cfg(test)]
102#[allow(clippy::unusual_byte_groupings)]
103mod test {
104    use super::*;
105
106    #[test]
107    fn read_header() {
108        assert_eq!(
109            Some((BranchFactor::Two, 25u8)),
110            InputBitStream::<2>::decode_header(&[0b1_11001_00u8])
111        );
112
113        assert_eq!(
114            Some((BranchFactor::Four, 0u8)),
115            InputBitStream::<2>::decode_header(&[0b1_00000_01u8])
116        );
117
118        assert_eq!(
119            Some((BranchFactor::Eight, 31u8)),
120            InputBitStream::<2>::decode_header(&[0b1_11111_10u8])
121        );
122
123        assert_eq!(
124            Some((BranchFactor::ThirtyTwo, 9u8)),
125            InputBitStream::<2>::decode_header(&[0b1_01001_11u8])
126        );
127    }
128
129    #[test]
130    fn read_2() {
131        let mut stream = InputBitStream::<2>::from(&[0b00000000, 0b11_10_01_00, 0b00_01_10_11]);
132        assert_eq!(stream.bytes_consumed(), 1); // Initially one byte consumed for the header.
133
134        assert_eq!(stream.next(), Some(0b00));
135        assert_eq!(stream.bytes_consumed(), 2);
136        assert_eq!(stream.next(), Some(0b01));
137        assert_eq!(stream.next(), Some(0b10));
138        assert_eq!(stream.next(), Some(0b11));
139        assert_eq!(stream.bytes_consumed(), 2);
140
141        assert_eq!(stream.next(), Some(0b11));
142        assert_eq!(stream.bytes_consumed(), 3);
143        assert_eq!(stream.next(), Some(0b10));
144        assert_eq!(stream.next(), Some(0b01));
145        assert_eq!(stream.next(), Some(0b00));
146        assert_eq!(stream.bytes_consumed(), 3);
147
148        assert_eq!(stream.next(), None);
149
150        let mut stream = InputBitStream::<2>::from(&[]);
151        assert_eq!(stream.next(), None);
152    }
153
154    #[test]
155    fn skip_2() {
156        let mut stream = InputBitStream::<2>::from(&[0b00000000, 0b11_10_01_00, 0b00_01_10_11]);
157        assert_eq!(stream.bytes_consumed(), 1); // Initially one byte consumed for the header.
158
159        assert!(stream.skip_nodes(1));
160        assert_eq!(stream.bytes_consumed(), 2);
161        assert!(stream.skip_nodes(2));
162        assert_eq!(stream.bytes_consumed(), 2);
163        assert!(stream.skip_nodes(1));
164        assert_eq!(stream.bytes_consumed(), 2);
165
166        assert!(stream.skip_nodes(1));
167        assert_eq!(stream.bytes_consumed(), 3);
168        assert!(stream.skip_nodes(3));
169        assert_eq!(stream.bytes_consumed(), 3);
170        assert!(!stream.skip_nodes(1));
171    }
172
173    #[test]
174    fn skip_2_unaligned() {
175        let mut stream = InputBitStream::<2>::from(&[0b00000000, 0b11_10_01_00, 0b00_01_10_11]);
176        assert_eq!(stream.bytes_consumed(), 1); // Initially one byte consumed for the header.
177
178        assert!(stream.skip_nodes(3));
179        assert_eq!(stream.bytes_consumed(), 2);
180
181        assert!(stream.skip_nodes(3));
182        assert_eq!(stream.bytes_consumed(), 3);
183
184        assert!(!stream.skip_nodes(3));
185    }
186
187    #[test]
188    fn read_4() {
189        let mut stream = InputBitStream::<4>::from(&[0b00000000, 0b1110_0100, 0b0001_1011]);
190        assert_eq!(stream.bytes_consumed(), 1);
191
192        assert_eq!(stream.next(), Some(0b0100));
193        assert_eq!(stream.bytes_consumed(), 2);
194        assert_eq!(stream.next(), Some(0b1110));
195        assert_eq!(stream.bytes_consumed(), 2);
196
197        assert_eq!(stream.next(), Some(0b1011));
198        assert_eq!(stream.bytes_consumed(), 3);
199        assert_eq!(stream.next(), Some(0b0001));
200        assert_eq!(stream.bytes_consumed(), 3);
201
202        assert_eq!(stream.next(), None);
203
204        let mut stream = InputBitStream::<4>::from(&[]);
205        assert_eq!(stream.next(), None);
206    }
207
208    #[test]
209    fn skip_4() {
210        let mut stream = InputBitStream::<4>::from(&[0b00000000, 0b1110_0100, 0b0001_1011]);
211        assert_eq!(stream.bytes_consumed(), 1); // Initially one byte consumed for the header.
212
213        assert!(stream.skip_nodes(1));
214        assert_eq!(stream.bytes_consumed(), 2);
215        assert!(stream.skip_nodes(1));
216        assert_eq!(stream.bytes_consumed(), 2);
217
218        assert!(stream.skip_nodes(2));
219        assert_eq!(stream.bytes_consumed(), 3);
220
221        assert!(!stream.skip_nodes(1));
222    }
223
224    #[test]
225    fn read_8() {
226        let mut stream = InputBitStream::<8>::from(&[0b00000000, 0b11100100, 0b00011011]);
227        assert_eq!(stream.bytes_consumed(), 1);
228        assert_eq!(stream.next(), Some(0b11100100));
229        assert_eq!(stream.bytes_consumed(), 2);
230        assert_eq!(stream.next(), Some(0b00011011));
231        assert_eq!(stream.bytes_consumed(), 3);
232        assert_eq!(stream.next(), None);
233
234        let mut stream = InputBitStream::<8>::from(&[]);
235        assert_eq!(stream.next(), None);
236    }
237
238    #[test]
239    fn skip_8() {
240        let mut stream = InputBitStream::<8>::from(&[0b00000000, 0b11100100, 0b00011011]);
241        assert_eq!(stream.bytes_consumed(), 1);
242
243        assert!(stream.skip_nodes(1));
244        assert_eq!(stream.bytes_consumed(), 2);
245        assert!(stream.skip_nodes(1));
246        assert_eq!(stream.bytes_consumed(), 3);
247        assert!(!stream.skip_nodes(1));
248
249        let mut stream = InputBitStream::<8>::from(&[0b00000000, 0b11100100, 0b00011011]);
250        assert_eq!(stream.bytes_consumed(), 1);
251
252        assert!(stream.skip_nodes(2));
253        assert_eq!(stream.bytes_consumed(), 3);
254        assert!(!stream.skip_nodes(1));
255    }
256
257    #[test]
258    fn read_32() {
259        let mut stream = InputBitStream::<32>::from(&[
260            0b00000000, 0b00000000, 0b11111111, 0b11100100, 0b00011011,
261        ]);
262
263        assert_eq!(stream.bytes_consumed(), 1);
264        assert_eq!(stream.next(), Some(0b00011011_11100100_11111111_00000000));
265        assert_eq!(stream.bytes_consumed(), 5);
266        assert_eq!(stream.next(), None);
267
268        let mut stream = InputBitStream::<32>::from(&[
269            0b00000000, 0b00000000, 0b11111111, 0b11100100, 0b00011011, 0b00000001,
270        ]);
271        assert_eq!(stream.next(), Some(0b00011011_11100100_11111111_00000000));
272        assert_eq!(stream.next(), None);
273
274        let mut stream = InputBitStream::<32>::from(&[]);
275        assert_eq!(stream.next(), None);
276    }
277
278    #[test]
279    fn skip_32() {
280        let mut stream = InputBitStream::<32>::from(&[
281            0b00000000, 0b00000000, 0b11111111, 0b11100100, 0b00011011,
282        ]);
283
284        assert_eq!(stream.bytes_consumed(), 1);
285
286        assert!(stream.skip_nodes(1));
287        assert_eq!(stream.bytes_consumed(), 5);
288        assert!(!stream.skip_nodes(1));
289    }
290}
read_fonts/collections/int_set/input_bit_stream.rs

read_fonts/collections/int_set/
input_bit_stream.rs
