read_fonts/collections/int_set/
sparse_bit_set.rs

1//! Provides serialization of [`IntSet`]'s to a highly compact bitset format as defined in the
2//! IFT specification:
3//!
4//! <https://w3c.github.io/IFT/Overview.html#sparse-bit-set-decoding>
5
6use alloc::{collections::VecDeque, vec::Vec};
7use std::error::Error;
8use std::fmt;
9
10use super::bitset::U32SetBuilder;
11use super::input_bit_stream::InputBitStream;
12use super::output_bit_stream::OutputBitStream;
13use super::IntSet;
14use super::U32Set;
15
16#[derive(Debug, PartialEq)]
17pub struct DecodingError;
18
19impl Error for DecodingError {}
20
21impl fmt::Display for DecodingError {
22    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
23        write!(
24            f,
25            "The input data stream was too short to be a valid sparse bit set."
26        )
27    }
28}
29
30#[derive(Copy, Clone, PartialEq, Eq, Debug)]
31pub(crate) enum BranchFactor {
32    Two,
33    Four,
34    Eight,
35    ThirtyTwo,
36}
37
38impl IntSet<u32> {
39    /// Populate this set with the values obtained from decoding the provided sparse bit set bytes.
40    ///
41    /// Sparse bit sets are a specialized, compact encoding of bit sets defined in the IFT specification:
42    /// <https://w3c.github.io/IFT/Overview.html#sparse-bit-set-decoding>
43    pub fn from_sparse_bit_set(data: &[u8]) -> Result<IntSet<u32>, DecodingError> {
44        Self::from_sparse_bit_set_bounded(data, 0, u32::MAX).map(|(set, _)| set)
45    }
46
47    /// Populate this set with the values obtained from decoding the provided sparse bit set bytes.
48    ///
49    /// During decoding bias will be added to each decoded set members value. The final set will not contain
50    /// any values larger than max_value: any encoded values larger than max_value after the bias is applied
51    /// are ignored.
52    ///
53    /// Sparse bit sets are a specialized, compact encoding of bit sets defined in the IFT specification:
54    /// <https://w3c.github.io/IFT/Overview.html#sparse-bit-set-decoding>
55    pub fn from_sparse_bit_set_bounded(
56        data: &[u8],
57        bias: u32,
58        max_value: u32,
59    ) -> Result<(IntSet<u32>, &[u8]), DecodingError> {
60        Self::from_sparse_bit_set_bounded_with_max_set_size(data, bias, max_value, u32::MAX)
61    }
62
63    /// Populate this set with the values obtained from decoding the provided sparse bit set bytes.
64    ///
65    /// During decoding bias will be added to each decoded set members value. The final set will not contain
66    /// any values larger than max_value: any encoded values larger than max_value after the bias is applied
67    /// are ignored. If the decoded set size exceeds max_set_size, decoding returns [`DecodingError`].
68    ///
69    /// Sparse bit sets are a specialized, compact encoding of bit sets defined in the IFT specification:
70    /// <https://w3c.github.io/IFT/Overview.html#sparse-bit-set-decoding>
71    pub fn from_sparse_bit_set_bounded_with_max_set_size(
72        data: &[u8],
73        bias: u32,
74        max_value: u32,
75        max_set_size: u32,
76    ) -> Result<(IntSet<u32>, &[u8]), DecodingError> {
77        // This is a direct port of the decoding algorithm from:
78        // <https://w3c.github.io/IFT/Overview.html#sparse-bit-set-decoding>
79        let Some((branch_factor, height)) = InputBitStream::<0>::decode_header(data) else {
80            return Err(DecodingError);
81        };
82
83        if height > branch_factor.max_height() {
84            // TODO(garretrieger): the spec says nothing about this depth limit, we need to update the spec
85            // to match.
86            return Err(DecodingError);
87        }
88
89        let result = match branch_factor {
90            BranchFactor::Two => {
91                Self::decode_sparse_bit_set_nodes::<2>(data, height, bias, max_value, max_set_size)
92            }
93            BranchFactor::Four => {
94                Self::decode_sparse_bit_set_nodes::<4>(data, height, bias, max_value, max_set_size)
95            }
96            BranchFactor::Eight => {
97                Self::decode_sparse_bit_set_nodes::<8>(data, height, bias, max_value, max_set_size)
98            }
99            BranchFactor::ThirtyTwo => {
100                Self::decode_sparse_bit_set_nodes::<32>(data, height, bias, max_value, max_set_size)
101            }
102        };
103
104        result.map(|(bitset, data)| (IntSet::<u32>::from_bitset(bitset), data))
105    }
106
107    fn decode_sparse_bit_set_nodes<const BF: u8>(
108        data: &[u8],
109        height: u8,
110        bias: u32,
111        max_value: u32,
112        max_set_size: u32,
113    ) -> Result<(U32Set, &[u8]), DecodingError> {
114        let mut out = U32Set::empty();
115        if height == 0 {
116            // 1 byte was used for the header.
117            return Ok((out, &data[1..]));
118        }
119
120        let mut builder = U32SetBuilder::start(&mut out);
121        let mut bits = InputBitStream::<BF>::from(data);
122        // TODO(garretrieger): estimate initial capacity (maximum is a function of the number of nodes in the bit stream).
123        let mut queue = VecDeque::<NextNode>::new();
124        queue.push_back(NextNode { start: 0, depth: 1 });
125
126        'outer: while let Some(next) = queue.pop_front() {
127            let mut bits = bits.next().ok_or(DecodingError)?;
128            if bits == 0 {
129                // all bits were zeroes which is a special command to completely fill in
130                // all integers covered by this node.
131                let exp = (height as u32) - next.depth + 1;
132                let node_size = (BF as u64).pow(exp);
133
134                let Some(start) = u32::try_from(next.start)
135                    .ok()
136                    .and_then(|start| start.checked_add(bias))
137                    .filter(|start| *start <= max_value)
138                else {
139                    // start is outside the valid range of the set, so skip this range.
140                    continue;
141                };
142
143                let end = u32::try_from(next.start + node_size - 1)
144                    .unwrap_or(u32::MAX)
145                    .saturating_add(bias)
146                    .min(max_value);
147
148                let count = (end as u64) - (start as u64) + 1;
149                if builder.set.len().saturating_add(count) > max_set_size as u64 {
150                    return Err(DecodingError);
151                }
152
153                // TODO(garretrieger): implement special insert_range on the builder as well.
154                builder.set.insert_range(start..=end);
155                continue;
156            }
157
158            let height = height as u32;
159
160            let exp = height - next.depth;
161            let next_node_size = (BF as u64).pow(exp);
162            loop {
163                let bit_index = bits.trailing_zeros();
164                if bit_index == 32 {
165                    break;
166                }
167
168                // TODO(garretrieger): possible optimization by having two versions of this loop
169                //                     as next.depth == height has the same value for each of the outer iterations.
170                if next.depth == height {
171                    // TODO(garretrieger): this has a few branches, is it faster to do all the math in u64
172                    //                     then check only once for > max_value? Will need to check with a benchmark.
173                    let Some(start) = u32::try_from(next.start)
174                        .ok()
175                        .and_then(|start| start.checked_add(bit_index))
176                        .and_then(|start| start.checked_add(bias))
177                        .filter(|start| *start <= max_value)
178                    else {
179                        // At the lowest depth values are encountered in order, so if this is out of range so will be
180                        // all future values. We can break early.
181                        break 'outer;
182                    };
183
184                    if builder.set.len() >= max_set_size as u64 {
185                        return Err(DecodingError);
186                    }
187
188                    // TODO(garretrieger): further optimize by inserting entire nodes at once (as a bit field).
189                    builder.insert(start);
190                } else {
191                    let start_delta = bit_index as u64 * next_node_size;
192                    queue.push_back(NextNode {
193                        start: next.start + start_delta,
194                        depth: next.depth + 1,
195                    });
196                }
197
198                bits &= !(1 << bit_index); // clear the bit that was just read.
199            }
200        }
201
202        builder.finish();
203
204        // If the max value was reached the loop above may have terminated early leaving some unprocessed nodes
205        // in the queue. The loop can only break once we are at the lowest depth which means that each remaining queue node
206        // will consume only one node from the bit stream. Advance the bit stream by the remaining number of nodes to
207        // correctly count the number of bytes consumed.
208        if !bits.skip_nodes(queue.len() as u32) {
209            // We ran out of bits to consume before decoding would have been finished.
210            return Err(DecodingError);
211        }
212
213        Ok((out, &data[bits.bytes_consumed()..]))
214    }
215
216    /// Encode this set as a sparse bit set byte encoding.
217    ///
218    /// Sparse bit sets are a specialized, compact encoding of bit sets defined in the IFT specification:
219    /// <https://w3c.github.io/IFT/Overview.html#sparse-bit-set-decoding>
220    pub fn to_sparse_bit_set(&self) -> Vec<u8> {
221        // TODO(garretrieger): use the heuristic approach from the incxfer
222        // implementation to guess the optimal size. Building the set 4 times
223        // is costly.
224        let mut candidates: Vec<Vec<u8>> = Vec::new();
225
226        let Some(max_value) = self.last() else {
227            return OutputBitStream::new(BranchFactor::Two, 0).into_bytes();
228        };
229
230        if BranchFactor::Two.tree_height_for(max_value) <= BranchFactor::Two.max_height() {
231            candidates.push(to_sparse_bit_set_with_bf::<2>(self));
232        }
233
234        if BranchFactor::Four.tree_height_for(max_value) <= BranchFactor::Four.max_height() {
235            candidates.push(to_sparse_bit_set_with_bf::<4>(self));
236        }
237
238        if BranchFactor::Eight.tree_height_for(max_value) <= BranchFactor::Eight.max_height() {
239            candidates.push(to_sparse_bit_set_with_bf::<8>(self));
240        }
241
242        if BranchFactor::ThirtyTwo.tree_height_for(max_value)
243            <= BranchFactor::ThirtyTwo.max_height()
244        {
245            candidates.push(to_sparse_bit_set_with_bf::<32>(self));
246        }
247
248        candidates.into_iter().min_by_key(|f| f.len()).unwrap()
249    }
250}
251
252/// Encode this set as a sparse bit set byte encoding with a specified branch factor.
253///
254/// Branch factor can be 2, 4, 8 or 32. It's a compile time constant so that optimized decoding implementations
255/// can be generated by the compiler.
256///
257/// Sparse bit sets are a specialized, compact encoding of bit sets defined in the IFT specification:
258/// <https://w3c.github.io/IFT/Overview.html#sparse-bit-set-decoding>
259pub fn to_sparse_bit_set_with_bf<const BF: u8>(set: &IntSet<u32>) -> Vec<u8> {
260    let branch_factor = BranchFactor::from_val(BF);
261    let Some(max_value) = set.last() else {
262        return OutputBitStream::new(branch_factor, 0).into_bytes();
263    };
264    let mut height = branch_factor.tree_height_for(max_value);
265    if height > branch_factor.max_height() {
266        if BF == 2 {
267            // Branch factor 2 cannot encode all possible u32 values, so upgrade to a BF4 set in that case.
268            return to_sparse_bit_set_with_bf::<4>(set);
269        }
270        // This shouldn't be reachable for any possible u32 values.
271        panic!("Height value exceeds the maximum for this branch factor.");
272    }
273    let mut os = OutputBitStream::new(branch_factor, height);
274    let mut nodes: Vec<Node> = Vec::new();
275
276    // We build the nodes that will comprise the bit stream in reverse order
277    // from the last value in the last layer up to the first layer. Then
278    // when generating the final stream the order is reversed.
279    // The reverse order construction is needed since nodes at the lower layer
280    // affect the values in the parent layers.
281    let mut indices = set.clone();
282    let mut filled_indices = IntSet::<u32>::all();
283    while height > 0 {
284        (indices, filled_indices) =
285            create_layer(branch_factor, indices, filled_indices, &mut nodes);
286        height -= 1;
287    }
288
289    for node in nodes.iter().rev() {
290        match node.node_type {
291            NodeType::Standard => os.write_node(node.bits),
292            NodeType::Filled => os.write_node(0),
293            NodeType::Skip => {}
294        };
295    }
296
297    os.into_bytes()
298}
299
300struct CreateLayerState<'a> {
301    // This is the set of indices which are to be set in the layer above this one
302    upper_indices: IntSet<u32>,
303    // Similarly, this is the set of indices in the layer above this one which are fully filled.
304    upper_filled_indices: IntSet<u32>,
305
306    current_node: Option<Node>,
307    current_node_filled_bits: u32,
308    nodes: &'a mut Vec<Node>,
309    child_count: u64,
310    nodes_init_length: u64,
311    branch_factor: BranchFactor,
312}
313
314impl CreateLayerState<'_> {
315    fn commit_current_node(&mut self) {
316        let Some(mut node) = self.current_node.take() else {
317            // noop if there isn't a node to commit.
318            return;
319        };
320        self.upper_indices.insert(node.parent_index);
321
322        if self.current_node_filled_bits == self.branch_factor.u32_mask() {
323            // This node is filled and can thus be represented by a node that is '0'.
324            // It's index is recorded so that the parent node can also check if they are filled.
325            self.upper_filled_indices.insert(node.parent_index);
326            node.node_type = NodeType::Filled;
327
328            if self.nodes_init_length >= self.child_count {
329                // Since this node is filled, find all nodes which are children and set them to be skipped in
330                // the encoding.
331                let children_start_index = self.nodes_init_length.saturating_sub(self.child_count);
332                let children_end_index = self.nodes_init_length;
333                // TODO(garretrieger): this scans all nodes of the previous layer to find those which are children,
334                //   but we can likely limit it to just the children of this node with some extra book keeping.
335                for child in
336                    &mut self.nodes[children_start_index as usize..children_end_index as usize]
337                {
338                    if child.parent_index >= node.parent_index * self.branch_factor.value()
339                        && child.parent_index < (node.parent_index + 1) * self.branch_factor.value()
340                    {
341                        child.node_type = NodeType::Skip;
342                    }
343                }
344            }
345        }
346
347        self.nodes.push(node);
348        self.current_node_filled_bits = 0;
349    }
350}
351
352/// Compute the nodes for a layer of the sparse bit set.
353///
354/// Computes the nodes needed for the layer which contains the indices in
355/// 'iter'. The new nodes are appended to 'nodes'. 'iter' must be sorted
356/// in ascending order.
357///
358/// Returns the set of indices for the layer above.
359fn create_layer(
360    branch_factor: BranchFactor,
361    values: IntSet<u32>,
362    filled_values: IntSet<u32>,
363    nodes: &mut Vec<Node>,
364) -> (IntSet<u32>, IntSet<u32>) {
365    let mut state = CreateLayerState {
366        upper_indices: IntSet::<u32>::empty(),
367        upper_filled_indices: IntSet::<u32>::empty(),
368        current_node: None,
369        current_node_filled_bits: 0,
370        child_count: values.len(),
371        nodes_init_length: nodes.len() as u64,
372        nodes,
373        branch_factor,
374    };
375
376    // The nodes array is produced in reverse order and then reversed before final output.
377    for v in values.iter().rev() {
378        let parent_index = v / branch_factor.value();
379        let prev_parent_index = state
380            .current_node
381            .as_ref()
382            .map_or(parent_index, |node| node.parent_index);
383        if prev_parent_index != parent_index {
384            state.commit_current_node();
385        }
386
387        let current_node = state.current_node.get_or_insert(Node {
388            bits: 0,
389            parent_index,
390            node_type: NodeType::Standard,
391        });
392
393        let mask = 0b1 << (v % branch_factor.value());
394        current_node.bits |= mask;
395        if filled_values.contains(v) {
396            state.current_node_filled_bits |= mask;
397        }
398    }
399
400    state.commit_current_node();
401    (state.upper_indices, state.upper_filled_indices)
402}
403
404enum NodeType {
405    Standard,
406    Filled,
407    Skip,
408}
409
410struct Node {
411    bits: u32,
412    parent_index: u32,
413    node_type: NodeType,
414}
415
416impl BranchFactor {
417    pub(crate) fn value(&self) -> u32 {
418        match self {
419            BranchFactor::Two => 2,
420            BranchFactor::Four => 4,
421            BranchFactor::Eight => 8,
422            BranchFactor::ThirtyTwo => 32,
423        }
424    }
425
426    /// The maximum height that can be used for a given branch factor without the risk of encountering overflows
427    pub(crate) fn max_height(&self) -> u8 {
428        match self {
429            BranchFactor::Two => 31,
430            BranchFactor::Four => 16,
431            BranchFactor::Eight => 11,
432            BranchFactor::ThirtyTwo => 7,
433        }
434    }
435
436    fn tree_height_for(&self, max_value: u32) -> u8 {
437        // height H, can represent up to (BF^height) - 1
438        let mut height: u32 = 0;
439        let mut max_value = max_value;
440        loop {
441            height += 1;
442            max_value >>= self.node_size_log2();
443            if max_value == 0 {
444                break height as u8;
445            }
446        }
447    }
448
449    fn from_val(val: u8) -> BranchFactor {
450        match val {
451            2 => BranchFactor::Two,
452            4 => BranchFactor::Four,
453            8 => BranchFactor::Eight,
454            32 => BranchFactor::ThirtyTwo,
455            // This should never happen as this is only used internally.
456            _ => panic!("Invalid branch factor."),
457        }
458    }
459
460    fn node_size_log2(&self) -> u32 {
461        match self {
462            BranchFactor::Two => 1,
463            BranchFactor::Four => 2,
464            BranchFactor::Eight => 3,
465            BranchFactor::ThirtyTwo => 5,
466        }
467    }
468
469    pub(crate) fn byte_mask(&self) -> u32 {
470        match self {
471            BranchFactor::Two => 0b00000011,
472            BranchFactor::Four => 0b00001111,
473            BranchFactor::Eight => 0b11111111,
474            BranchFactor::ThirtyTwo => 0b11111111,
475        }
476    }
477
478    fn u32_mask(&self) -> u32 {
479        match self {
480            BranchFactor::Two => 0b00000000_00000000_00000000_00000011,
481            BranchFactor::Four => 0b00000000_00000000_00000000_00001111,
482            BranchFactor::Eight => 0b00000000_00000000_00000000_11111111,
483            BranchFactor::ThirtyTwo => 0b11111111_11111111_11111111_11111111,
484        }
485    }
486}
487
488struct NextNode {
489    start: u64,
490    depth: u32,
491}
492
493#[cfg(test)]
494#[allow(clippy::unusual_byte_groupings)]
495mod test {
496    use super::*;
497
498    #[test]
499    fn spec_example_2() {
500        // Test of decoding the example 2 given in the specification.
501        // See: <https://w3c.github.io/IFT/Overview.html#sparse-bit-set-decoding>
502        let bytes = [
503            0b00001110, 0b00100001, 0b00010001, 0b00000001, 0b00000100, 0b00000010, 0b00001000,
504        ];
505
506        let set = IntSet::<u32>::from_sparse_bit_set(&bytes).unwrap();
507        let expected: IntSet<u32> = [2, 33, 323].iter().copied().collect();
508        assert_eq!(set, expected);
509    }
510
511    #[test]
512    fn spec_example_3() {
513        // Test of decoding the example 3 given in the specification.
514        // See: <https://w3c.github.io/IFT/Overview.html#sparse-bit-set-decoding>
515        let bytes = [0b00000000];
516
517        let set = IntSet::<u32>::from_sparse_bit_set(&bytes).unwrap();
518        let expected: IntSet<u32> = [].iter().copied().collect();
519        assert_eq!(set, expected);
520    }
521
522    #[test]
523    fn spec_example_4() {
524        // Test of decoding the example 4 given in the specification.
525        // See: <https://w3c.github.io/IFT/Overview.html#sparse-bit-set-decoding>
526        let bytes = [0b00001101, 0b00000011, 0b00110001];
527
528        let set = IntSet::<u32>::from_sparse_bit_set(&bytes).unwrap();
529
530        let mut expected: IntSet<u32> = IntSet::<u32>::empty();
531        expected.insert_range(0..=17);
532
533        assert_eq!(set, expected);
534    }
535
536    #[test]
537    fn invalid() {
538        // Spec example 2 with one byte missing.
539        let bytes = [
540            0b00001110, 0b00100001, 0b00010001, 0b00000001, 0b00000100, 0b00000010,
541        ];
542        assert!(IntSet::<u32>::from_sparse_bit_set(&bytes).is_err());
543
544        // Max height exceeded.
545        let bytes = [
546            0b0_01000_11, // BF 32, Depth 8
547            0b00000000,
548            0b00000000,
549            0b00000000,
550            0b10000000, // L1
551            0b00000000,
552            0b00000000,
553            0b00000000,
554            0b10000000, // L2
555            0b00000000,
556            0b00000000,
557            0b00000000,
558            0b10000000, // L3
559            0b00000000,
560            0b00000000,
561            0b00000000,
562            0b10000000, // L4
563            0b00000000,
564            0b00000000,
565            0b00000000,
566            0b10000000, // L5
567            0b00000000,
568            0b00000000,
569            0b00000000,
570            0b10000000, // L6
571            0b00000000,
572            0b00000000,
573            0b00000000,
574            0b00000001, // L7
575            0b00000000,
576            0b00000000,
577            0b00000000,
578            0b10000000, // L8
579        ];
580        assert!(IntSet::<u32>::from_sparse_bit_set(&bytes).is_err());
581    }
582
583    #[test]
584    fn invalid_biased_and_bounded() {
585        let bytes = [0b0_00011_01, 0b0000_0011, 0b1111_0011];
586
587        assert!(IntSet::<u32>::from_sparse_bit_set_bounded(&bytes, 0, u32::MAX).is_err());
588        assert!(IntSet::<u32>::from_sparse_bit_set_bounded(&bytes, 0, 20).is_err());
589        assert!(IntSet::<u32>::from_sparse_bit_set_bounded(&bytes, 0, 19).is_err());
590        assert!(IntSet::<u32>::from_sparse_bit_set_bounded(&bytes, 0, 18).is_err());
591        assert!(IntSet::<u32>::from_sparse_bit_set_bounded(&bytes, 0, 15).is_err());
592        assert!(IntSet::<u32>::from_sparse_bit_set_bounded(&bytes, 0, 14).is_err());
593
594        assert!(IntSet::<u32>::from_sparse_bit_set_bounded(&bytes, 1, 20).is_err());
595        assert!(IntSet::<u32>::from_sparse_bit_set_bounded(&bytes, 2, 20).is_err());
596        assert!(IntSet::<u32>::from_sparse_bit_set_bounded(&bytes, 3, 20).is_err());
597        assert!(IntSet::<u32>::from_sparse_bit_set_bounded(&bytes, 6, 20).is_err());
598    }
599
600    #[test]
601    fn larger_than_u32() {
602        // Set with values beyond u32
603        let bytes = [
604            0b0_00111_11, // BF 32, Depth 7
605            0b00000000,
606            0b00000000,
607            0b00000000,
608            0b10000000, // L1
609            0b00000000,
610            0b00000000,
611            0b00000000,
612            0b10000000, // L2
613            0b00000000,
614            0b00000000,
615            0b00000000,
616            0b10000000, // L3
617            0b00000000,
618            0b00000000,
619            0b00000000,
620            0b10000000, // L4
621            0b00000000,
622            0b00000000,
623            0b00000000,
624            0b10000000, // L5
625            0b00000000,
626            0b00000000,
627            0b00000000,
628            0b10000000, // L6
629            0b00000000,
630            0b00000000,
631            0b00000000,
632            0b00000001, // L7
633        ];
634        assert_eq!(
635            IntSet::<u32>::from_sparse_bit_set(&bytes).unwrap(),
636            IntSet::<u32>::empty()
637        );
638
639        // Set with filled node values beyond u32
640        let bytes = [
641            0b0_00111_11, // BF 32, Depth 7
642            0b00000000,
643            0b00000000,
644            0b00000000,
645            0b10000000, // L1
646            0b00000000,
647            0b00000000,
648            0b00000000,
649            0b00000000, // L2
650        ];
651
652        assert_eq!(
653            IntSet::<u32>::from_sparse_bit_set(&bytes).unwrap(),
654            IntSet::<u32>::empty()
655        );
656    }
657
658    #[test]
659    fn from_sparse_bit_set_bounded_with_remaining_data() {
660        let bytes = [0b00001101, 0b00000011, 0b00110001, 0b10101010];
661        let mut expected: IntSet<u32> = IntSet::<u32>::empty();
662        expected.insert_range(0..=17);
663
664        assert_eq!(
665            IntSet::<u32>::from_sparse_bit_set_bounded(&bytes, 0, 19).unwrap(),
666            (expected.clone(), &bytes[3..]),
667        );
668    }
669
670    #[test]
671    fn from_sparse_bit_set_biased_and_bounded() {
672        let bytes = [0b0_00011_01, 0b0000_0011, 0b1111_0011, 0b0000_0001];
673        let mut expected: IntSet<u32> = IntSet::<u32>::empty();
674        expected.insert_range(0..=20);
675
676        assert_eq!(
677            IntSet::<u32>::from_sparse_bit_set_bounded(&bytes, 0, 20).unwrap(),
678            (expected.clone(), &bytes[4..])
679        );
680
681        let mut expected: IntSet<u32> = IntSet::<u32>::empty();
682        expected.insert_range(0..=19);
683        assert_eq!(
684            IntSet::<u32>::from_sparse_bit_set_bounded(&bytes, 0, 19).unwrap(),
685            (expected.clone(), &bytes[4..])
686        );
687
688        let mut expected: IntSet<u32> = IntSet::<u32>::empty();
689        expected.insert_range(1..=20);
690        assert_eq!(
691            IntSet::<u32>::from_sparse_bit_set_bounded(&bytes, 1, 20).unwrap(),
692            (expected.clone(), &bytes[4..])
693        );
694
695        let mut expected: IntSet<u32> = IntSet::<u32>::empty();
696        expected.insert_range(1..=18);
697        assert_eq!(
698            IntSet::<u32>::from_sparse_bit_set_bounded(&bytes, 1, 18).unwrap(),
699            (expected.clone(), &bytes[4..])
700        );
701
702        let mut expected: IntSet<u32> = IntSet::<u32>::empty();
703        expected.insert_range(0..=14);
704        assert_eq!(
705            IntSet::<u32>::from_sparse_bit_set_bounded(&bytes, 0, 14).unwrap(),
706            (expected.clone(), &bytes[4..])
707        );
708
709        let mut expected: IntSet<u32> = IntSet::<u32>::empty();
710        expected.insert_range(6..=20);
711        assert_eq!(
712            IntSet::<u32>::from_sparse_bit_set_bounded(&bytes, 6, 20).unwrap(),
713            (expected.clone(), &bytes[4..])
714        );
715
716        let mut expected: IntSet<u32> = IntSet::<u32>::empty();
717        expected.insert(0);
718        assert_eq!(
719            IntSet::<u32>::from_sparse_bit_set_bounded(&bytes, 0, 0).unwrap(),
720            (expected.clone(), &bytes[4..])
721        );
722
723        assert_eq!(
724            IntSet::<u32>::from_sparse_bit_set_bounded(&bytes, 1, 0).unwrap(),
725            (IntSet::<u32>::empty().clone(), &bytes[4..])
726        );
727
728        let bytes = [0b00000000];
729        let set = IntSet::<u32>::from_sparse_bit_set_bounded(&bytes, 5, 0)
730            .unwrap()
731            .0;
732        assert_eq!(set, IntSet::<u32>::empty());
733    }
734
735    #[test]
736    fn from_sparse_bit_set_bounded_with_max_set_size() {
737        // Case 1: Discrete set with non-continuous ranges (no fill nodes)
738        let non_fill_set: IntSet<u32> = [0, 2, 4, 6, 8, 10].into_iter().collect();
739        let non_fill_bytes = to_sparse_bit_set_with_bf::<4>(&non_fill_set);
740
741        assert!(
742            IntSet::<u32>::from_sparse_bit_set_bounded_with_max_set_size(
743                &non_fill_bytes,
744                0,
745                u32::MAX,
746                6
747            )
748            .is_ok()
749        );
750        assert!(
751            IntSet::<u32>::from_sparse_bit_set_bounded_with_max_set_size(
752                &non_fill_bytes,
753                0,
754                u32::MAX,
755                100
756            )
757            .is_ok()
758        );
759        assert_eq!(
760            IntSet::<u32>::from_sparse_bit_set_bounded_with_max_set_size(
761                &non_fill_bytes,
762                0,
763                u32::MAX,
764                5
765            ),
766            Err(DecodingError)
767        );
768        assert_eq!(
769            IntSet::<u32>::from_sparse_bit_set_bounded_with_max_set_size(
770                &non_fill_bytes,
771                0,
772                u32::MAX,
773                0
774            ),
775            Err(DecodingError)
776        );
777
778        // Case 2: Exact aligned continuous range (0..=63 for BF=8) to ensure fill nodes with no trailing members
779        let fill_set: IntSet<u32> = (0..=63).collect();
780        let fill_bytes = to_sparse_bit_set_with_bf::<8>(&fill_set);
781
782        assert!(
783            IntSet::<u32>::from_sparse_bit_set_bounded_with_max_set_size(
784                &fill_bytes,
785                0,
786                u32::MAX,
787                64
788            )
789            .is_ok()
790        );
791        assert_eq!(
792            IntSet::<u32>::from_sparse_bit_set_bounded_with_max_set_size(
793                &fill_bytes,
794                0,
795                u32::MAX,
796                63
797            ),
798            Err(DecodingError)
799        );
800
801        // Case 3: Empty set
802        let empty_set = IntSet::<u32>::empty();
803        let empty_bytes = to_sparse_bit_set_with_bf::<4>(&empty_set);
804        assert!(
805            IntSet::<u32>::from_sparse_bit_set_bounded_with_max_set_size(
806                &empty_bytes,
807                0,
808                u32::MAX,
809                0
810            )
811            .is_ok()
812        );
813    }
814
815    #[test]
816    fn test_tree_height_for() {
817        assert_eq!(BranchFactor::Two.tree_height_for(0), 1);
818        assert_eq!(BranchFactor::Two.tree_height_for(1), 1);
819        assert_eq!(BranchFactor::Two.tree_height_for(2), 2);
820        assert_eq!(BranchFactor::Two.tree_height_for(117), 7);
821
822        assert_eq!(BranchFactor::Four.tree_height_for(0), 1);
823        assert_eq!(BranchFactor::Four.tree_height_for(3), 1);
824        assert_eq!(BranchFactor::Four.tree_height_for(4), 2);
825        assert_eq!(BranchFactor::Four.tree_height_for(63), 3);
826        assert_eq!(BranchFactor::Four.tree_height_for(64), 4);
827
828        assert_eq!(BranchFactor::Eight.tree_height_for(0), 1);
829        assert_eq!(BranchFactor::Eight.tree_height_for(7), 1);
830        assert_eq!(BranchFactor::Eight.tree_height_for(8), 2);
831        assert_eq!(BranchFactor::Eight.tree_height_for(32767), 5);
832        assert_eq!(BranchFactor::Eight.tree_height_for(32768), 6);
833
834        assert_eq!(BranchFactor::ThirtyTwo.tree_height_for(0), 1);
835        assert_eq!(BranchFactor::ThirtyTwo.tree_height_for(31), 1);
836        assert_eq!(BranchFactor::ThirtyTwo.tree_height_for(32), 2);
837        assert_eq!(BranchFactor::ThirtyTwo.tree_height_for(1_048_575), 4);
838        assert_eq!(BranchFactor::ThirtyTwo.tree_height_for(1_048_576), 5);
839    }
840
841    #[test]
842    fn generate_spec_example_2() {
843        // Test of reproducing the encoding of example 2 given
844        // in the specification. See:
845        // <https://w3c.github.io/IFT/Overview.html#sparse-bit-set-decoding>
846
847        let actual_bytes = to_sparse_bit_set_with_bf::<8>(&[2, 33, 323].iter().copied().collect());
848        let expected_bytes = [
849            0b00001110, 0b00100001, 0b00010001, 0b00000001, 0b00000100, 0b00000010, 0b00001000,
850        ];
851
852        assert_eq!(actual_bytes, expected_bytes);
853    }
854
855    #[test]
856    fn generate_spec_example_3() {
857        // Test of reproducing the encoding of example 3 given
858        // in the specification. See:
859        // <https://w3c.github.io/IFT/Overview.html#sparse-bit-set-decoding>
860
861        let actual_bytes = to_sparse_bit_set_with_bf::<2>(&IntSet::<u32>::empty());
862        let expected_bytes = [0b00000000];
863
864        assert_eq!(actual_bytes, expected_bytes);
865    }
866
867    #[test]
868    fn generate_spec_example_4() {
869        // Test of reproducing the encoding of example 3 given
870        // in the specification. See:
871        // <https://w3c.github.io/IFT/Overview.html#sparse-bit-set-decoding>
872
873        let actual_bytes = to_sparse_bit_set_with_bf::<4>(&(0..=17).collect());
874        let expected_bytes = [0b00001101, 0b0000_0011, 0b0011_0001];
875
876        assert_eq!(actual_bytes, expected_bytes);
877    }
878
879    #[test]
880    fn encode_one_level() {
881        let actual_bytes = to_sparse_bit_set_with_bf::<8>(&[2, 6].iter().copied().collect());
882        let expected_bytes = [0b0_00001_10, 0b01000100];
883        assert_eq!(actual_bytes, expected_bytes);
884    }
885
886    #[test]
887    fn encode_one_level_filled() {
888        let actual_bytes = to_sparse_bit_set_with_bf::<8>(&(0..=7).collect());
889        let expected_bytes = [0b0_00001_10, 0b00000000];
890        assert_eq!(actual_bytes, expected_bytes);
891    }
892
893    #[test]
894    fn encode_two_level_filled() {
895        let actual_bytes = to_sparse_bit_set_with_bf::<8>(&(3..=21).collect());
896        let expected_bytes = [0b0_00010_10, 0b00000111, 0b11111000, 0b00000000, 0b00111111];
897        assert_eq!(actual_bytes, expected_bytes);
898    }
899
900    #[test]
901    fn encode_two_level_not_filled() {
902        let actual_bytes = to_sparse_bit_set_with_bf::<4>(&[0, 4, 8, 12].iter().copied().collect());
903        let expected_bytes = [0b0_00010_01, 0b0001_1111, 0b0001_0001, 0b0000_0001];
904        assert_eq!(actual_bytes, expected_bytes);
905    }
906
907    #[test]
908    fn encode_four_level_filled() {
909        let mut s = IntSet::<u32>::empty();
910        s.insert_range(64..=127); // Filled node on level 3
911        s.insert_range(512..=1023); // Filled node on level 2
912        s.insert(4000);
913
914        let actual_bytes = to_sparse_bit_set_with_bf::<8>(&s);
915        let expected_bytes = [
916            // Header
917            0b0_00100_10,
918            // L1
919            0b10000011,
920            // L2
921            0b00000010,
922            0b00000000,
923            0b01000000,
924            // L3,
925            0b00000000,
926            0b00010000,
927            // L4
928            0b00000001,
929        ];
930        assert_eq!(actual_bytes, expected_bytes);
931    }
932
933    #[test]
934    fn encode_bf32() {
935        let actual_bytes = to_sparse_bit_set_with_bf::<32>(&[2, 31, 323].iter().copied().collect());
936        let expected_bytes = [
937            0b0_00010_11,
938            // node 0
939            0b00000001,
940            0b00000100,
941            0b00000000,
942            0b00000000,
943            // node 1
944            0b00000100,
945            0b00000000,
946            0b00000000,
947            0b10000000,
948            // node 2
949            0b00001000,
950            0b00000000,
951            0b00000000,
952            0b00000000,
953        ];
954
955        assert_eq!(actual_bytes, expected_bytes);
956    }
957
958    #[test]
959    fn round_trip() {
960        let s1: IntSet<u32> = [11, 74, 9358].iter().copied().collect();
961        let mut s2: IntSet<u32> = s1.clone();
962        s2.insert_range(67..=412);
963
964        check_round_trip::<2>(&s1);
965        check_round_trip::<4>(&s1);
966        check_round_trip::<8>(&s1);
967        check_round_trip::<32>(&s1);
968
969        check_round_trip::<2>(&s2);
970        check_round_trip::<4>(&s2);
971        check_round_trip::<8>(&s2);
972        check_round_trip::<32>(&s2);
973    }
974
975    fn check_round_trip<const BF: u8>(s: &IntSet<u32>) {
976        let bytes = to_sparse_bit_set_with_bf::<BF>(s);
977        let s_prime = IntSet::<u32>::from_sparse_bit_set(&bytes).unwrap();
978        assert_eq!(*s, s_prime);
979    }
980
981    #[test]
982    fn find_smallest_bf() {
983        let s: IntSet<u32> = [11, 74, 9358].iter().copied().collect();
984        let bytes = s.to_sparse_bit_set();
985        // BF4
986        assert_eq!(vec![0b0_00111_01], bytes[0..1]);
987
988        let s: IntSet<u32> = [
989            16, 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30,
990        ]
991        .iter()
992        .copied()
993        .collect();
994        let bytes = s.to_sparse_bit_set();
995        // BF32
996        assert_eq!(vec![0b0_00001_11], bytes[0..1]);
997    }
998
999    #[test]
1000    fn encode_maxu32() {
1001        let s: IntSet<u32> = [1, u32::MAX].iter().copied().collect();
1002
1003        let bytes = s.to_sparse_bit_set();
1004        let s_prime = IntSet::<u32>::from_sparse_bit_set(&bytes);
1005        assert_eq!(s, s_prime.unwrap());
1006
1007        let s: IntSet<u32> = [1, u32::MAX].iter().copied().collect();
1008        let bytes = to_sparse_bit_set_with_bf::<2>(&s);
1009        let s_prime = IntSet::<u32>::from_sparse_bit_set(&bytes);
1010        assert_eq!(s, s_prime.unwrap());
1011
1012        let s: IntSet<u32> = [1, u32::MAX].iter().copied().collect();
1013        let bytes = to_sparse_bit_set_with_bf::<4>(&s);
1014        let s_prime = IntSet::<u32>::from_sparse_bit_set(&bytes);
1015        assert_eq!(s, s_prime.unwrap());
1016
1017        let s: IntSet<u32> = [1, u32::MAX].iter().copied().collect();
1018        let bytes = to_sparse_bit_set_with_bf::<8>(&s);
1019        let s_prime = IntSet::<u32>::from_sparse_bit_set(&bytes);
1020        assert_eq!(s, s_prime.unwrap());
1021
1022        let s: IntSet<u32> = [1, u32::MAX].iter().copied().collect();
1023        let bytes = to_sparse_bit_set_with_bf::<32>(&s);
1024        let s_prime = IntSet::<u32>::from_sparse_bit_set(&bytes);
1025        assert_eq!(s, s_prime.unwrap());
1026    }
1027}
read_fonts/collections/int_set/sparse_bit_set.rs

read_fonts/collections/int_set/
sparse_bit_set.rs
