Repository: googlefonts/fontations
Pull request #1022 (2024-07-23 17:35:27)

[int-set] Add a second version of sparse bit set decode with max set size.
It's very easy to construct a sparse bit set which contains all values in u32, which can be quite slow to decode. Add an alternate decoding method which can be given a maximum set size for callers who want to avoid long decoding times. Use the bounded version in the fuzzer.


Patch:
diff --git a/fuzz/fuzz_targets/fuzz_sparse_bit_set_decode.rs b/fuzz/fuzz_targets/fuzz_sparse_bit_set_decode.rs
index c0251583..22c771b9 100644
--- a/fuzz/fuzz_targets/fuzz_sparse_bit_set_decode.rs
+++ b/fuzz/fuzz_targets/fuzz_sparse_bit_set_decode.rs
@@ -5,5 +5,5 @@ use int_set::IntSet;
 use libfuzzer_sys::fuzz_target;
 
 fuzz_target!(|data: &[u8]| {
-    let _ = IntSet::<u32>::from_sparse_bit_set(data);
+    let _ = IntSet::<u32>::from_sparse_bit_set_bounded(data, 10_000);
 });
diff --git a/int-set/src/sparse_bit_set.rs b/int-set/src/sparse_bit_set.rs
index 8fac0f13..56b20331 100644
--- a/int-set/src/sparse_bit_set.rs
+++ b/int-set/src/sparse_bit_set.rs
@@ -13,7 +13,7 @@ use crate::output_bit_stream::OutputBitStream;
 use crate::BitSet;
 use crate::IntSet;
 
-#[derive(Debug)]
+#[derive(Debug, PartialEq)]
 pub struct DecodingError;
 
 impl Error for DecodingError {}
@@ -41,6 +41,19 @@ impl IntSet<u32> {
     /// Sparse bit sets are a specialized, compact encoding of bit sets defined in the IFT specification:
     /// <https://w3c.github.io/IFT/Overview.html#sparse-bit-set-decoding>
     pub fn from_sparse_bit_set(data: &[u8]) -> Result<IntSet<u32>, DecodingError> {
+        Self::from_sparse_bit_set_bounded(data, u32::MAX as u64 + 1)
+    }
+
+    /// Populate this set with the values obtained from decoding the provided sparse bit set bytes.
+    /// The size (in number of members) of the output set is bounded to be equal to or below the provided max size.
+    /// If the decoded set would contain more members than the limit an error will be returned.
+    ///
+    /// Sparse bit sets are a specialized, compact encoding of bit sets defined in the IFT specification:
+    /// <https://w3c.github.io/IFT/Overview.html#sparse-bit-set-decoding>
+    pub fn from_sparse_bit_set_bounded(
+        data: &[u8],
+        set_size_limit: u64,
+    ) -> Result<IntSet<u32>, DecodingError> {
         // This is a direct port of the decoding algorithm from:
         // <https://w3c.github.io/IFT/Overview.html#sparse-bit-set-decoding>
         let Some((branch_factor, height)) = InputBitStream::<0>::decode_header(data) else {
@@ -54,10 +67,18 @@ impl IntSet<u32> {
         }
 
         let result = match branch_factor {
-            BranchFactor::Two => Self::decode_sparse_bit_set_nodes::<2>(data, height),
-            BranchFactor::Four => Self::decode_sparse_bit_set_nodes::<4>(data, height),
-            BranchFactor::Eight => Self::decode_sparse_bit_set_nodes::<8>(data, height),
-            BranchFactor::ThirtyTwo => Self::decode_sparse_bit_set_nodes::<32>(data, height),
+            BranchFactor::Two => {
+                Self::decode_sparse_bit_set_nodes::<2>(data, height, set_size_limit)
+            }
+            BranchFactor::Four => {
+                Self::decode_sparse_bit_set_nodes::<4>(data, height, set_size_limit)
+            }
+            BranchFactor::Eight => {
+                Self::decode_sparse_bit_set_nodes::<8>(data, height, set_size_limit)
+            }
+            BranchFactor::ThirtyTwo => {
+                Self::decode_sparse_bit_set_nodes::<32>(data, height, set_size_limit)
+            }
         };
 
         result.map(IntSet::<u32>::from_bitset)
@@ -66,6 +87,7 @@ impl IntSet<u32> {
     fn decode_sparse_bit_set_nodes<const BF: u8>(
         data: &[u8],
         height: u8,
+        set_size_limit: u64,
     ) -> Result<BitSet, DecodingError> {
         let mut out = BitSet::empty();
         if height == 0 {
@@ -78,6 +100,7 @@ impl IntSet<u32> {
         let mut queue = VecDeque::<NextNode>::new();
         queue.push_back(NextNode { start: 0, depth: 1 });
 
+        let mut size_count = 0u64;
         while let Some(next) = queue.pop_front() {
             let mut bits = bits.next().ok_or(DecodingError)?;
             if bits == 0 {
@@ -88,11 +111,25 @@ impl IntSet<u32> {
                 // TODO(garretrieger): implement special insert_range on the builder as well.
                 let start = u32::try_from(next.start).or(Err(DecodingError))?;
                 let end = u32::try_from(next.start + node_size - 1).or(Err(DecodingError))?;
+
+                size_count += (end as u64 - start as u64) + 1;
+                if size_count > set_size_limit {
+                    return Err(DecodingError);
+                }
+
                 builder.set.insert_range(start..=end);
                 continue;
             }
 
-            let exp = height as u32 - next.depth;
+            let height = height as u32;
+            if next.depth == height {
+                size_count += bits.count_ones() as u64;
+                if size_count > set_size_limit {
+                    return Err(DecodingError);
+                }
+            }
+
+            let exp = height - next.depth;
             let next_node_size = (BF as u64).pow(exp);
             loop {
                 let bit_index = bits.trailing_zeros();
@@ -102,7 +139,7 @@ impl IntSet<u32> {
 
                 // TODO(garretrieger): possible optimization by having two versions of this loop
                 //                     as next.depth == height has the same value for each of the outer iterations.
-                if next.depth == height as u32 {
+                if next.depth == height {
                     // TODO(garretrieger): further optimize by inserting entire nodes at once (as a bit field).
                     let start =
                         u32::try_from(next.start + bit_index as u64).or(Err(DecodingError))?;
@@ -533,6 +570,51 @@ mod test {
         assert!(IntSet::<u32>::from_sparse_bit_set(&bytes).is_err());
     }
 
+    #[test]
+    fn from_sparse_bit_set_bounded() {
+        let bytes = [0b00001101, 0b00000011, 0b00110001];
+        let mut expected: IntSet<u32> = IntSet::<u32>::empty();
+        expected.insert_range(0..=17);
+
+        assert_eq!(
+            IntSet::<u32>::from_sparse_bit_set_bounded(&bytes, 19).unwrap(),
+            expected
+        );
+        assert_eq!(
+            IntSet::<u32>::from_sparse_bit_set_bounded(&bytes, 18).unwrap(),
+            expected
+        );
+        assert_eq!(
+            IntSet::<u32>::from_sparse_bit_set_bounded(&bytes, 17),
+            Err(DecodingError)
+        );
+        assert_eq!(
+            IntSet::<u32>::from_sparse_bit_set_bounded(&bytes, 16),
+            Err(DecodingError)
+        );
+        assert_eq!(
+            IntSet::<u32>::from_sparse_bit_set_bounded(&bytes, 15),
+            Err(DecodingError)
+        );
+        assert_eq!(
+            IntSet::<u32>::from_sparse_bit_set_bounded(&bytes, 7),
+            Err(DecodingError)
+        );
+        assert_eq!(
+            IntSet::<u32>::from_sparse_bit_set_bounded(&bytes, 1),
+            Err(DecodingError)
+        );
+        assert_eq!(
+            IntSet::<u32>::from_sparse_bit_set_bounded(&bytes, 0),
+            Err(DecodingError)
+        );
+
+        let bytes = [0b00000000];
+        let set = IntSet::<u32>::from_sparse_bit_set_bounded(&bytes, 0).unwrap();
+        let expected: IntSet<u32> = [].iter().copied().collect();
+        assert_eq!(set, expected);
+    }
+
     #[test]
     fn test_tree_height_for() {
         assert_eq!(BranchFactor::Two.tree_height_for(0), 1);
diff --git a/read-fonts/src/tables/layout.rs b/read-fonts/src/tables/layout.rs
index 9b003e58..77438c71 100644
--- a/read-fonts/src/tables/layout.rs
+++ b/read-fonts/src/tables/layout.rs
@@ -44,7 +44,7 @@ pub enum Subtables<'a, T: FontRead<'a>, Ext: ExtensionLookup<'a, T>> {
 }
 
 impl<'a, T: FontRead<'a> + 'a, Ext: ExtensionLookup<'a, T> + 'a> Subtables<'a, T, Ext> {
-    /// create a new subtables array given offests to non-extension subtables
+    /// create a new subtables array given offsets to non-extension subtables
     pub(crate) fn new(offsets: &'a [BigEndian<Offset16>], data: FontData<'a>) -> Self {
         Subtables::Subtable(ArrayOfOffsets::new(offsets, data, ()))
     }


Test patch:
diff --git a/read-fonts/generated/generated_test_records.rs b/read-fonts/generated/generated_test_records.rs
index fae81b23..456e3419 100644
--- a/read-fonts/generated/generated_test_records.rs
+++ b/read-fonts/generated/generated_test_records.rs
@@ -257,13 +257,13 @@ impl<'a> SomeRecord<'a> for ContainsArrays<'a> {
 #[derive(Clone, Debug, Copy, bytemuck :: AnyBitPattern)]
 #[repr(C)]
 #[repr(packed)]
-pub struct ContainsOffests {
+pub struct ContainsOffsets {
     pub off_array_count: BigEndian<u16>,
     pub array_offset: BigEndian<Offset16>,
     pub other_offset: BigEndian<Offset32>,
 }
 
-impl ContainsOffests {
+impl ContainsOffsets {
     pub fn off_array_count(&self) -> u16 {
         self.off_array_count.get()
     }
@@ -292,15 +292,15 @@ impl ContainsOffests {
     }
 }
 
-impl FixedSize for ContainsOffests {
+impl FixedSize for ContainsOffsets {
     const RAW_BYTE_LEN: usize = u16::RAW_BYTE_LEN + Offset16::RAW_BYTE_LEN + Offset32::RAW_BYTE_LEN;
 }
 
 #[cfg(feature = "traversal")]
-impl<'a> SomeRecord<'a> for ContainsOffests {
+impl<'a> SomeRecord<'a> for ContainsOffsets {
     fn traverse(self, data: FontData<'a>) -> RecordResolver<'a> {
         RecordResolver {
-            name: "ContainsOffests",
+            name: "ContainsOffsets",
             get_field: Box::new(move |idx, _data| match idx {
                 0usize => Some(Field::new("off_array_count", self.off_array_count())),
                 1usize => Some(Field::new(
diff --git a/resources/codegen_inputs/test_records.rs b/resources/codegen_inputs/test_records.rs
index 4b3bc6af..359bf20e 100644
--- a/resources/codegen_inputs/test_records.rs
+++ b/resources/codegen_inputs/test_records.rs
@@ -35,7 +35,7 @@ record ContainsArrays<'a> {
     records: [SimpleRecord],
 }
 
-record ContainsOffests {
+record ContainsOffsets {
     #[compile(array_len($array_offset))]
     off_array_count: u16,
     #[read_offset_with($off_array_count)]
diff --git a/write-fonts/generated/generated_test_records.rs b/write-fonts/generated/generated_test_records.rs
index 06ffcaf5..891e2a07 100644
--- a/write-fonts/generated/generated_test_records.rs
+++ b/write-fonts/generated/generated_test_records.rs
@@ -175,13 +175,13 @@ impl FromObjRef<read_fonts::codegen_test::records::ContainsArrays<'_>> for Conta
 
 #[derive(Clone, Debug, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
 #[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
-pub struct ContainsOffests {
+pub struct ContainsOffsets {
     pub array: OffsetMarker<Vec<SimpleRecord>>,
     pub other: OffsetMarker<BasicTable, WIDTH_32>,
 }
 
-impl ContainsOffests {
-    /// Construct a new `ContainsOffests`
+impl ContainsOffsets {
+    /// Construct a new `ContainsOffsets`
     pub fn new(array: Vec<SimpleRecord>, other: BasicTable) -> Self {
         Self {
             array: array.into(),
@@ -190,7 +190,7 @@ impl ContainsOffests {
     }
 }
 
-impl FontWrite for ContainsOffests {
+impl FontWrite for ContainsOffsets {
     #[allow(clippy::unnecessary_cast)]
     fn write_into(&self, writer: &mut TableWriter) {
         (array_len(&self.array).unwrap() as u16).write_into(writer);
@@ -198,13 +198,13 @@ impl FontWrite for ContainsOffests {
         self.other.write_into(writer);
     }
     fn table_type(&self) -> TableType {
-        TableType::Named("ContainsOffests")
+        TableType::Named("ContainsOffsets")
     }
 }
 
-impl Validate for ContainsOffests {
+impl Validate for ContainsOffsets {
     fn validate_impl(&self, ctx: &mut ValidationCtx) {
-        ctx.in_table("ContainsOffests", |ctx| {
+        ctx.in_table("ContainsOffsets", |ctx| {
             ctx.in_field("array", |ctx| {
                 self.array.validate_impl(ctx);
             });
@@ -215,12 +215,12 @@ impl Validate for ContainsOffests {
     }
 }
 
-impl FromObjRef<read_fonts::codegen_test::records::ContainsOffests> for ContainsOffests {
+impl FromObjRef<read_fonts::codegen_test::records::ContainsOffsets> for ContainsOffsets {
     fn from_obj_ref(
-        obj: &read_fonts::codegen_test::records::ContainsOffests,
+        obj: &read_fonts::codegen_test::records::ContainsOffsets,
         offset_data: FontData,
     ) -> Self {
-        ContainsOffests {
+        ContainsOffsets {
             array: obj.array(offset_data).to_owned_obj(offset_data),
             other: obj.other(offset_data).to_owned_table(),
         }
diff --git a/write-fonts/src/codegen_test.rs b/write-fonts/src/codegen_test.rs
index 29a930b2..892d49f2 100644
--- a/write-fonts/src/codegen_test.rs
+++ b/write-fonts/src/codegen_test.rs
@@ -44,7 +44,7 @@ mod records {
         let simple = vec![SimpleRecord::new(6, 32)];
         let contains_arrays = ContainsArrays::new(vec![1, 2, 3], simple.clone());
         let basic = BasicTable::new(simple.clone(), vec![contains_arrays]);
-        let contains_offsets = ContainsOffests::new(simple, basic);
+        let contains_offsets = ContainsOffsets::new(simple, basic);
         assert_eq!(contains_offsets.other.simple_records.len(), 1);
     }
 }