Repository: googlefonts/fontations
Pull request #1018 (2024-07-22 23:30:20)

[int-set] Optimize remove_range.
Iterate over only the existing pages contained within the range instead of all possible pages in the range.


Patch:
diff --git a/docs/codegen-tour.md b/docs/codegen-tour.md
index 1686f098..705cbe9d 100644
--- a/docs/codegen-tour.md
+++ b/docs/codegen-tour.md
@@ -66,7 +66,7 @@ generated code.
 
 All of the types which are used in codegen are reexported in the
 [`codegen_prelude`][read-prelude] module; this is glob imported at the top of
-evey generated file.
+every generated file.
 
 We will describe various of these manually implemented types as we encounter
 them throughout this document, but before we get started it is worth touching on
@@ -148,11 +148,11 @@ trait Scalar {
 ```
 
 But this is not currently something we can express with Rust's generics,
-although [it should become possible eventaully](generic-const-exprs).
+although [it should become possible eventually](generic-const-exprs).
 
 In any case: what this lets us do is avoid having two separate sets of types for
 the 'raw' and 'native' cases; we have a single wrapper type that we use anytime
-we want to indicate that a type is in its raw form. This has the additonal
+we want to indicate that a type is in its raw form. This has the additional
 advantage that we can define new types in our generated code that implement
 `Scalar`, and then those types can automatically work with `BigEndian`; this is
 useful for things like custom enums and flags that are defined at various points
@@ -710,7 +710,7 @@ the size and contents of the array:
   specific associated `ValueFormat`.
   ```rust
   table SinglePosFormat2 {
-      // some fields omited
+      // some fields omitted
       value_format: BigEndian<ValueFormat>,
       value_count: BigEndian<u16>,
       #[count($value_count)]
@@ -730,7 +730,7 @@ the size and contents of the array:
 
   ```rust
   table Post {
-      // some fields omited
+      // some fields omitted
       #[count(..)]
       #[since_version(2.0)]
       string_data: VarLenArray<PString<'a>>,
@@ -803,7 +803,7 @@ which we can choose based on the fields present on the table.
 
 In these cases, the `#[compile(..)]` attribute can be used to provide a computed
 value to be written in the place of this field. The provided value can be a
-literal or an expression that evalutes to a value of the field's type.
+literal or an expression that evaluates to a value of the field's type.
 
 If a field has a `#[compile(..)]` attribute, then that field will be omitted in
 the generated struct.
@@ -869,7 +869,7 @@ or that the number of items in a table does not overflow the integer type that
 stores that table's length. Additional validation can be performed on a
 per-field basis by providing a method name to the `#[validate(..)]` attribute;
 this should be an instance method (having a `&self` param) and should also
-accept an additonal 'ctx' argument, of type [`&mut ValidateCtx`][validation-ctx] which is used
+accept an additional 'ctx' argument, of type [`&mut ValidateCtx`][validation-ctx] which is used
 to report errors.
 
 ### <a id="compilation"></a> compilation and [`FontWrite`][]
diff --git a/fauntlet/src/pen.rs b/fauntlet/src/pen.rs
index 3dcd6d3e..c32e838b 100644
--- a/fauntlet/src/pen.rs
+++ b/fauntlet/src/pen.rs
@@ -9,7 +9,7 @@ use skrifa::raw::types::{Pen, PenCommand};
 ///    them with a line if the current point does not match the most recent
 ///    start point.
 ///
-/// 2. The FT CFF loader elminates some, but not all degenerate move/line
+/// 2. The FT CFF loader eliminates some, but not all degenerate move/line
 ///    elements (due to a final scaling step that may introduce new ones).
 ///    Skrifa applies this pass *after* scaling so is more aggressive about
 ///    removing degenerates. This drops unused moves and lines that end at the
@@ -188,7 +188,7 @@ mod tests {
         use PenCommand::*;
         let mut recording = RecordingPen::default();
         let mut pen = RegularizingPen::new(&mut recording, true);
-        // Dropped: superceded by following move
+        // Dropped: superseded by following move
         pen.move_to(1.0, 2.0);
         pen.move_to(4.5, 5.0);
         // Dropped: line to previous move
@@ -225,7 +225,7 @@ mod tests {
         // Two offcurve points with odd deltas
         let offcurve1 = (4.0, 4.0);
         let offcurve2 = (7.0, 9.0);
-        // Implicit oncurve at midpoint beteween offcurves
+        // Implicit oncurve at midpoint between offcurves
         let implicit_oncurve = (
             (offcurve1.0 + offcurve2.0) / 2.0,
             (offcurve1.1 + offcurve2.1) / 2.0,
diff --git a/font-codegen/README.md b/font-codegen/README.md
index 6a57fcc6..98832c04 100644
--- a/font-codegen/README.md
+++ b/font-codegen/README.md
@@ -201,7 +201,7 @@ The following annotations are supported on top-level objects:
   'delta_value_count'.
 - `#[compile(arg)]`: If present, this field will not be included in the compile
   type. The value may be either the literal 'skip', or an expression that
-  evalutes to the field's type: the skip case is only expected in cases where
+  evaluates to the field's type: the skip case is only expected in cases where
   there is a manual `FontWrite` impl, and the field does not make sense on the
   compile type.
 - `#[compile_with(method_name)]`: Specify custom compilation behaviour. This
diff --git a/font-codegen/src/fields.rs b/font-codegen/src/fields.rs
index 70f31a86..584499ea 100644
--- a/font-codegen/src/fields.rs
+++ b/font-codegen/src/fields.rs
@@ -1257,7 +1257,7 @@ impl Field {
                 CustomCompile::Expr(inline_expr) => {
                     // this expects that the type is always some simple scalar,
                     // and does not work if there is an explicit #[compile_type]
-                    // specified; it may need to be revaluated at some point.
+                    // specified; it may need to be reevaluated at some point.
                     let typ = self.typ.cooked_type_tokens();
                     let expr = inline_expr.compile_expr();
                     if !inline_expr.referenced_fields.is_empty() {
diff --git a/font-codegen/src/parsing.rs b/font-codegen/src/parsing.rs
index 52b7fbf7..7960431b 100644
--- a/font-codegen/src/parsing.rs
+++ b/font-codegen/src/parsing.rs
@@ -968,7 +968,7 @@ impl Parse for VariantAttrs {
             let ident = attr.path().get_ident().ok_or_else(|| {
                 syn::Error::new(
                     attr.path().span(),
-                    "attr paths should be a single identifer",
+                    "attr paths should be a single identifier",
                 )
             })?;
             if ident == DOC {
@@ -1041,7 +1041,7 @@ impl Parse for FieldAttrs {
             let ident = attr.path().get_ident().ok_or_else(|| {
                 syn::Error::new(
                     attr.path().span(),
-                    "attr paths should be a single identifer",
+                    "attr paths should be a single identifier",
                 )
             })?;
             if ident == DOC {
@@ -1114,7 +1114,7 @@ impl Parse for TableAttrs {
             let ident = attr.path().get_ident().ok_or_else(|| {
                 syn::Error::new(
                     attr.path().span(),
-                    "attr paths should be a single identifer",
+                    "attr paths should be a single identifier",
                 )
             })?;
             if ident == DOC {
@@ -1160,7 +1160,7 @@ impl Parse for EnumVariantAttrs {
             let ident = attr.path().get_ident().ok_or_else(|| {
                 syn::Error::new(
                     attr.path().span(),
-                    "attr paths should be a single identifer",
+                    "attr paths should be a single identifier",
                 )
             })?;
             if ident == DOC {
diff --git a/font-types/src/pen.rs b/font-types/src/pen.rs
index 08e20339..2b74f981 100644
--- a/font-types/src/pen.rs
+++ b/font-types/src/pen.rs
@@ -1,6 +1,6 @@
 /// Interface for accepting a sequence of path commands.
 ///
-/// This is a general abstraction to unify ouput for processes that decode and/or
+/// This is a general abstraction to unify output for processes that decode and/or
 /// transform outlines.
 ///
 /// /// AbstractPen in Python terms.
diff --git a/font-types/src/raw.rs b/font-types/src/raw.rs
index 1a63e1b8..31852192 100644
--- a/font-types/src/raw.rs
+++ b/font-types/src/raw.rs
@@ -4,7 +4,7 @@
 ///
 /// This is an internal trait for encoding and decoding big-endian bytes.
 ///
-/// You do not need to implement this trait directly; it is an implemention
+/// You do not need to implement this trait directly; it is an implementation
 /// detail of the [`BigEndian`] wrapper.
 pub trait Scalar: Sized {
     /// The raw byte representation of this type.
diff --git a/fuzz/fuzz_targets/fuzz_int_set.rs b/fuzz/fuzz_targets/fuzz_int_set.rs
index bceb824e..56ed84e3 100644
--- a/fuzz/fuzz_targets/fuzz_int_set.rs
+++ b/fuzz/fuzz_targets/fuzz_int_set.rs
@@ -110,7 +110,7 @@ impl Domain<SmallInt> for SmallInt {
 }
 
 /// This is an even integer in the domain of [0, 2048). It's used by the fuzzer
-/// for testing inverted sets + discontinous domains.
+/// for testing inverted sets + discontinuous domains.
 #[derive(Debug, Copy, Clone, PartialEq, PartialOrd, Eq, Ord)]
 struct SmallEvenInt(u32);
 
diff --git a/int-set/src/bitpage.rs b/int-set/src/bitpage.rs
index 57e365e5..824fe67f 100644
--- a/int-set/src/bitpage.rs
+++ b/int-set/src/bitpage.rs
@@ -66,7 +66,7 @@ impl BitPage {
 
     /// Iterator over the members of this page that come after 'value'.
     pub(crate) fn iter_after(&self, value: u32) -> impl DoubleEndedIterator<Item = u32> + '_ {
-        let start_index = self.element_index(value);
+        let start_index = Self::element_index(value);
         self.storage[start_index..]
             .iter()
             .enumerate()
@@ -150,6 +150,13 @@ impl BitPage {
         self.mark_dirty();
     }
 
+    pub(crate) fn clear(&mut self) {
+        for elem in self.storage.iter_mut() {
+            *elem = 0;
+        }
+        self.len.set(0);
+    }
+
     /// Removes (val % page width) from this set.
     pub(crate) fn remove(&mut self, val: u32) -> bool {
         let ret = self.contains(val);
@@ -196,14 +203,14 @@ impl BitPage {
     }
 
     fn element(&self, value: u32) -> &Element {
-        &self.storage[self.element_index(value)]
+        &self.storage[Self::element_index(value)]
     }
 
     fn element_mut(&mut self, value: u32) -> &mut Element {
-        &mut self.storage[self.element_index(value)]
+        &mut self.storage[Self::element_index(value)]
     }
 
-    fn element_index(&self, value: u32) -> usize {
+    const fn element_index(value: u32) -> usize {
         (value as usize & PAGE_MASK as usize) / (ELEM_BITS as usize)
     }
 }
@@ -572,6 +579,25 @@ mod test {
         }
     }
 
+    #[test]
+    fn clear() {
+        let mut zeroes = BitPage::new_zeroes();
+        let mut ones = BitPage::new_ones();
+
+        zeroes.clear();
+        assert_eq!(zeroes.len(), 0);
+        assert_eq!(zeroes.iter().next(), None);
+
+        zeroes.insert_range(10, 300);
+        zeroes.clear();
+        assert_eq!(zeroes.len(), 0);
+        assert_eq!(zeroes.iter().next(), None);
+
+        ones.clear();
+        assert_eq!(ones.len(), 0);
+        assert_eq!(ones.iter().next(), None);
+    }
+
     #[test]
     fn remove_to_empty_page() {
         let mut page = BitPage::new_zeroes();
@@ -725,7 +751,7 @@ mod test {
         check_iter_ranges(vec![400..=511]);
         check_iter_ranges(vec![0..=511]);
 
-        // continutation ranges
+        // continuation ranges
         check_iter_ranges(vec![64..=127]);
         check_iter_ranges(vec![64..=127, 129..=135]);
         check_iter_ranges(vec![64..=135]);
diff --git a/int-set/src/bitset.rs b/int-set/src/bitset.rs
index fba5eaf6..dea4b5e9 100644
--- a/int-set/src/bitset.rs
+++ b/int-set/src/bitset.rs
@@ -4,6 +4,7 @@ use super::bitpage::BitPage;
 use super::bitpage::RangeIter;
 use super::bitpage::PAGE_BITS;
 use std::cell::Cell;
+use std::cmp::min;
 use std::cmp::Ordering;
 use std::hash::Hash;
 
@@ -38,12 +39,12 @@ impl BitSet {
             return;
         }
 
-        let major_start = self.get_major_value(start);
-        let major_end = self.get_major_value(end);
+        let major_start = Self::get_major_value(start);
+        let major_end = Self::get_major_value(end);
 
         for major in major_start..=major_end {
-            let page_start = start.max(self.major_start(major));
-            let page_end = end.min(self.major_start(major) + (PAGE_BITS - 1));
+            let page_start = start.max(Self::major_start(major));
+            let page_end = end.min(Self::major_start(major) + (PAGE_BITS - 1));
             let page = self.ensure_page_for_major_mut(major);
             page.insert_range(page_start, page_end);
         }
@@ -54,7 +55,7 @@ impl BitSet {
     /// iterator of values.
     pub(crate) fn extend_unsorted<U: IntoIterator<Item = u32>>(&mut self, iter: U) {
         for val in iter {
-            let major_value = self.get_major_value(val);
+            let major_value = Self::get_major_value(val);
             let page = self.ensure_page_for_major_mut(major_value);
             page.insert_no_return(val);
         }
@@ -78,7 +79,7 @@ impl BitSet {
         let mut last_page_index: Option<usize> = None;
         let mut last_major_value = u32::MAX;
         for val in iter {
-            let major_value = self.get_major_value(val);
+            let major_value = Self::get_major_value(val);
             if major_value != last_major_value {
                 last_page_index = self.page_index_for_major(major_value);
                 last_major_value = major_value;
@@ -103,16 +104,37 @@ impl BitSet {
             return;
         }
 
-        let major_start = self.get_major_value(start);
-        let major_end = self.get_major_value(end);
+        let start_major = Self::get_major_value(start);
+        let end_major = Self::get_major_value(end);
+        let mut info_index = match self
+            .page_map
+            .binary_search_by(|probe| probe.major_value.cmp(&start_major))
+        {
+            Ok(info_index) => info_index,
+            Err(info_index) => info_index,
+        };
 
-        for major in major_start..=major_end {
-            let page_start = start.max(self.major_start(major));
-            let page_end = end.min(self.major_start(major + 1).wrapping_sub(1));
-            if let Some(page) = self.page_for_major_mut(major) {
-                page.remove_range(page_start, page_end);
+        loop {
+            let Some(info) = self.page_map.get(info_index) else {
+                break;
+            };
+            let Some(page) = self.pages.get_mut(info.index as usize) else {
+                break;
+            };
+
+            if info.major_value > end_major {
+                break;
+            } else if info.major_value == start_major {
+                page.remove_range(start, min(Self::major_end(start_major), end));
+            } else if info.major_value == end_major {
+                page.remove_range(Self::major_start(end_major), end);
+                break;
+            } else {
+                page.clear();
             }
+            info_index += 1;
         }
+
         self.mark_dirty();
     }
 
@@ -178,14 +200,14 @@ impl BitSet {
 
     pub(crate) fn iter(&self) -> impl DoubleEndedIterator<Item = u32> + '_ {
         self.iter_non_empty_pages().flat_map(|(major, page)| {
-            let base = self.major_start(major);
+            let base = Self::major_start(major);
             page.iter().map(move |v| base + v)
         })
     }
 
     /// Iterator over the members of this set that come after 'value'.
     pub(crate) fn iter_after(&self, value: u32) -> impl Iterator<Item = u32> + '_ {
-        let major_value = self.get_major_value(value);
+        let major_value = Self::get_major_value(value);
         let result = self
             .page_map
             .binary_search_by(|probe| probe.major_value.cmp(&major_value));
@@ -208,7 +230,7 @@ impl BitSet {
             page.filter(|_| partial_first_page)
                 .into_iter()
                 .flat_map(move |(page, major)| {
-                    let base = self.major_start(major);
+                    let base = Self::major_start(major);
                     page.iter_after(value).map(move |v| base + v)
                 });
 
@@ -227,7 +249,7 @@ impl BitSet {
             })
             .filter(|(_, page)| !page.is_empty())
             .flat_map(|(major, page)| {
-                let base = self.major_start(major);
+                let base = Self::major_start(major);
                 page.iter().map(move |v| base + v)
             });
 
@@ -458,17 +480,17 @@ impl BitSet {
     }
 
     /// Return the major value (top 23 bits) of the page associated with value.
-    fn get_major_value(&self, value: u32) -> u32 {
+    const fn get_major_value(value: u32) -> u32 {
         value >> PAGE_BITS_LOG_2
     }
 
-    fn major_start(&self, major: u32) -> u32 {
+    const fn major_start(major: u32) -> u32 {
         major << PAGE_BITS_LOG_2
     }
 
-    fn major_end(&self, major: u32) -> u32 {
+    const fn major_end(major: u32) -> u32 {
         // Note: (PAGE_BITS - 1) must be grouped to prevent overflow on addition for the largest page.
-        self.major_start(major) + (PAGE_BITS - 1)
+        Self::major_start(major) + (PAGE_BITS - 1)
     }
 
     /// Returns the index in self.pages (if it exists) for the page with the same major as major_value.
@@ -502,7 +524,7 @@ impl BitSet {
 
     /// Return a reference to the page that 'value' resides in.
     fn page_for(&self, value: u32) -> Option<&BitPage> {
-        let major_value = self.get_major_value(value);
+        let major_value = Self::get_major_value(value);
         let pages_index = self.page_index_for_major(major_value)?;
         self.pages.get(pages_index)
     }
@@ -511,7 +533,7 @@ impl BitSet {
     ///
     /// Insert a new page if it doesn't exist.
     fn page_for_mut(&mut self, value: u32) -> Option<&mut BitPage> {
-        let major_value = self.get_major_value(value);
+        let major_value = Self::get_major_value(value);
         return self.page_for_major_mut(major_value);
     }
 
@@ -525,7 +547,7 @@ impl BitSet {
     ///
     /// Insert a new page if it doesn't exist.
     fn ensure_page_for_mut(&mut self, value: u32) -> &mut BitPage {
-        self.ensure_page_for_major_mut(self.get_major_value(value))
+        self.ensure_page_for_major_mut(Self::get_major_value(value))
     }
 
     // Return a mutable reference to the page with major value equal to major_value.
@@ -582,7 +604,7 @@ impl<'a> BitSetBuilder<'a> {
         // TODO(garretrieger): additional optimization ideas:
         // - Assuming data is sorted accumulate a single element mask and only commit it to the element
         //   once the next value passes the end of the element.
-        let major_value = self.set.get_major_value(val);
+        let major_value = BitSet::get_major_value(val);
         if major_value != self.last_major_value {
             self.last_page_index = self.set.ensure_page_index_for_major(major_value);
             self.last_major_value = major_value;
@@ -678,7 +700,7 @@ impl<'a> BitSetRangeIter<'a> {
     fn next_range(&mut self) -> Option<RangeInclusive<u32>> {
         // TODO(garretrieger): don't recompute page start on each call.
         let page = self.set.page_map.get(self.page_info_index)?;
-        let page_start = self.set.major_start(page.major_value);
+        let page_start = BitSet::major_start(page.major_value);
         self.page_iter
             .as_mut()?
             .next()
@@ -694,7 +716,7 @@ impl<'a> Iterator for BitSetRangeIter<'a> {
         let mut current_range = self.next_range();
         loop {
             let page = self.set.page_map.get(self.page_info_index)?;
-            let page_end = self.set.major_end(page.major_value);
+            let page_end = BitSet::major_end(page.major_value);
 
             let Some(range) = current_range.clone() else {
                 // The current page has no more ranges, but there may be more pages.
@@ -984,13 +1006,50 @@ mod test {
     #[test]
     fn remove_range() {
         let mut bitset = BitSet::empty();
-        bitset.extend([5, 7, 11, 18, 620, 2000]);
-
-        assert_eq!(bitset.len(), 6);
-
+        bitset.extend([5, 7, 11, 18, 511, 620, 1023, 1024, 1200]);
+        assert_eq!(bitset.len(), 9);
         bitset.remove_range(7..=620);
+        assert_eq!(bitset.len(), 4);
+        assert_eq!(
+            bitset.iter().collect::<Vec<u32>>(),
+            vec![5, 1023, 1024, 1200]
+        );
+
+        let mut bitset = BitSet::empty();
+        bitset.extend([5, 7, 11, 18, 511, 620, 1023, 1024, 1200]);
+        bitset.remove_range(7..=1024);
         assert_eq!(bitset.len(), 2);
-        assert_eq!(bitset.iter().collect::<Vec<u32>>(), vec![5, 2000]);
+        assert_eq!(bitset.iter().collect::<Vec<u32>>(), vec![5, 1200]);
+
+        let mut bitset = BitSet::empty();
+        bitset.extend([5, 7, 11, 18, 511, 620, 1023, 1024, 1200]);
+        bitset.remove_range(2000..=2100);
+        assert_eq!(bitset.len(), 9);
+        assert_eq!(
+            bitset.iter().collect::<Vec<u32>>(),
+            vec![5, 7, 11, 18, 511, 620, 1023, 1024, 1200]
+        );
+
+        // Remove all from one page
+        let mut bitset = BitSet::empty();
+        bitset.extend([1001, 1002, 1003, 1004]);
+        bitset.remove_range(1002..=1003);
+        assert!(bitset.contains(1001));
+        assert!(!bitset.contains(1002));
+        assert!(!bitset.contains(1003));
+        assert!(bitset.contains(1004));
+
+        bitset.remove_range(100..=200);
+        assert!(bitset.contains(1001));
+        assert!(!bitset.contains(1002));
+        assert!(!bitset.contains(1003));
+        assert!(bitset.contains(1004));
+
+        bitset.remove_range(100..=1001);
+        assert!(!bitset.contains(1001));
+        assert!(!bitset.contains(1002));
+        assert!(!bitset.contains(1003));
+        assert!(bitset.contains(1004));
     }
 
     #[test]
diff --git a/int-set/src/lib.rs b/int-set/src/lib.rs
index 6df4ae76..4bf0201a 100644
--- a/int-set/src/lib.rs
+++ b/int-set/src/lib.rs
@@ -677,7 +677,7 @@ where
     AllValuesIter: Iterator<Item = u32>,
     T: Domain<T>,
 {
-    /// Iterate the ranges of an exclusive set where the domain is continous.
+    /// Iterate the ranges of an exclusive set where the domain is continuous.
     fn next_exclusive(
         ranges: &mut InclusiveRangeIter,
         min: &mut u32,
@@ -717,7 +717,7 @@ where
         None
     }
 
-    /// Iterate the ranges of an exclusive set where the domain is discontinous.
+    /// Iterate the ranges of an exclusive set where the domain is discontinuous.
     fn next_discontinous(
         all_values: &mut Option<AllValuesIter>,
         set: &'a BitSet,
diff --git a/int-set/src/output_bit_stream.rs b/int-set/src/output_bit_stream.rs
index fff91c1e..42965faa 100644
--- a/int-set/src/output_bit_stream.rs
+++ b/int-set/src/output_bit_stream.rs
@@ -9,7 +9,7 @@ pub(crate) struct OutputBitStream {
 }
 
 impl OutputBitStream {
-    pub(crate) const MAX_HEIGHT: u8 = 32;
+    pub(crate) const MAX_HEIGHT: u8 = 31;
 
     pub(crate) fn new(branch_factor: BranchFactor, height: u8) -> OutputBitStream {
         let mut out = OutputBitStream {
@@ -17,8 +17,8 @@ impl OutputBitStream {
             sub_index: 0,
             branch_factor,
         };
-        if height >= OutputBitStream::MAX_HEIGHT {
-            panic!("Height value exceeds 5 bits.");
+        if height > Self::MAX_HEIGHT {
+            panic!("Height value exceeds maximum for the branch factor.");
         }
         out.write_header(height);
         out
diff --git a/int-set/src/sparse_bit_set.rs b/int-set/src/sparse_bit_set.rs
index dfd9fcf1..8fac0f13 100644
--- a/int-set/src/sparse_bit_set.rs
+++ b/int-set/src/sparse_bit_set.rs
@@ -47,6 +47,12 @@ impl IntSet<u32> {
             return Err(DecodingError);
         };
 
+        if height > branch_factor.max_height() {
+            // TODO(garretrieger): the spec says nothing about this depth limit, we need to update the spec
+            // to match.
+            return Err(DecodingError);
+        }
+
         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),
@@ -74,31 +80,37 @@ impl IntSet<u32> {
 
         while let Some(next) = queue.pop_front() {
             let mut bits = bits.next().ok_or(DecodingError)?;
-
             if bits == 0 {
                 // all bits were zeroes which is a special command to completely fill in
                 // all integers covered by this node.
                 let exp = (height as u32) - next.depth + 1;
+                let node_size = (BF as u64).pow(exp);
                 // TODO(garretrieger): implement special insert_range on the builder as well.
-                builder
-                    .set
-                    .insert_range(next.start..=next.start + (BF as u32).pow(exp) - 1);
+                let start = u32::try_from(next.start).or(Err(DecodingError))?;
+                let end = u32::try_from(next.start + node_size - 1).or(Err(DecodingError))?;
+                builder.set.insert_range(start..=end);
                 continue;
             }
 
+            let exp = height as u32 - next.depth;
+            let next_node_size = (BF as u64).pow(exp);
             loop {
                 let bit_index = bits.trailing_zeros();
                 if bit_index == 32 {
                     break;
                 }
 
+                // 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 {
                     // TODO(garretrieger): further optimize by inserting entire nodes at once (as a bit field).
-                    builder.insert(next.start + bit_index);
+                    let start =
+                        u32::try_from(next.start + bit_index as u64).or(Err(DecodingError))?;
+                    builder.insert(start);
                 } else {
-                    let exp = height as u32 - next.depth;
+                    let start_delta = bit_index as u64 * next_node_size;
                     queue.push_back(NextNode {
-                        start: next.start + bit_index * (BF as u32).pow(exp),
+                        start: next.start + start_delta,
                         depth: next.depth + 1,
                     });
                 }
@@ -126,19 +138,21 @@ impl IntSet<u32> {
             return OutputBitStream::new(BranchFactor::Two, 0).into_bytes();
         };
 
-        if BranchFactor::Two.tree_height_for(max_value) < OutputBitStream::MAX_HEIGHT {
+        if BranchFactor::Two.tree_height_for(max_value) <= BranchFactor::Two.max_height() {
             candidates.push(to_sparse_bit_set_with_bf::<2>(self));
         }
 
-        if BranchFactor::Four.tree_height_for(max_value) < OutputBitStream::MAX_HEIGHT {
+        if BranchFactor::Four.tree_height_for(max_value) <= BranchFactor::Four.max_height() {
             candidates.push(to_sparse_bit_set_with_bf::<4>(self));
         }
 
-        if BranchFactor::Eight.tree_height_for(max_value) < OutputBitStream::MAX_HEIGHT {
+        if BranchFactor::Eight.tree_height_for(max_value) <= BranchFactor::Eight.max_height() {
             candidates.push(to_sparse_bit_set_with_bf::<8>(self));
         }
 
-        if BranchFactor::ThirtyTwo.tree_height_for(max_value) < OutputBitStream::MAX_HEIGHT {
+        if BranchFactor::ThirtyTwo.tree_height_for(max_value)
+            <= BranchFactor::ThirtyTwo.max_height()
+        {
             candidates.push(to_sparse_bit_set_with_bf::<32>(self));
         }
 
@@ -159,6 +173,14 @@ pub fn to_sparse_bit_set_with_bf<const BF: u8>(set: &IntSet<u32>) -> Vec<u8> {
         return OutputBitStream::new(branch_factor, 0).into_bytes();
     };
     let mut height = branch_factor.tree_height_for(max_value);
+    if height > branch_factor.max_height() {
+        if BF == 2 {
+            // Branch factor 2 cannot encode all possible u32 values, so upgrade to a BF4 set in that case.
+            return to_sparse_bit_set_with_bf::<4>(set);
+        }
+        // This shouldn't be reachable for any possible u32 values.
+        panic!("Height value exceeds the maximum for this branch factor.");
+    }
     let mut os = OutputBitStream::new(branch_factor, height);
     let mut nodes: Vec<Node> = vec![];
 
@@ -189,7 +211,7 @@ pub fn to_sparse_bit_set_with_bf<const BF: u8>(set: &IntSet<u32>) -> Vec<u8> {
 struct CreateLayerState<'a> {
     // This is the set of indices which are to be set in the layer above this one
     upper_indices: IntSet<u32>,
-    // Similarily, this is the set of indices in the layer above this one which are fully filled.
+    // Similarly, this is the set of indices in the layer above this one which are fully filled.
     upper_filled_indices: IntSet<u32>,
 
     current_node: Option<Node>,
@@ -239,7 +261,7 @@ impl<'a> CreateLayerState<'a> {
 /// Compute the nodes for a layer of the sparse bit set.
 ///
 /// Computes the nodes needed for the layer which contains the indices in
-/// 'iter'. The new nodes are appeded to 'nodes'. 'iter' must be sorted
+/// 'iter'. The new nodes are appended to 'nodes'. 'iter' must be sorted
 /// in ascending order.
 ///
 /// Returns the set of indices for the layer above.
@@ -310,6 +332,16 @@ impl BranchFactor {
         }
     }
 
+    /// The maximum height that can be used for a given branch factor without the risk of encountering overflows
+    pub(crate) fn max_height(&self) -> u8 {
+        match self {
+            BranchFactor::Two => 31,
+            BranchFactor::Four => 16,
+            BranchFactor::Eight => 11,
+            BranchFactor::ThirtyTwo => 7,
+        }
+    }
+
     fn tree_height_for(&self, max_value: u32) -> u8 {
         // height H, can represent up to (BF^height) - 1
         let mut height: u32 = 0;
@@ -363,7 +395,7 @@ impl BranchFactor {
 }
 
 struct NextNode {
-    start: u32,
+    start: u64,
     depth: u32,
 }
 
@@ -417,6 +449,88 @@ mod test {
             0b00001110, 0b00100001, 0b00010001, 0b00000001, 0b00000100, 0b00000010,
         ];
         assert!(IntSet::<u32>::from_sparse_bit_set(&bytes).is_err());
+
+        // Set with values beyond u32
+        let bytes = [
+            0b0_01000_11, // BF 32, Depth 8
+            0b00000000,
+            0b00000000,
+            0b00000000,
+            0b10000000, // L1
+            0b00000000,
+            0b00000000,
+            0b00000000,
+            0b10000000, // L2
+            0b00000000,
+            0b00000000,
+            0b00000000,
+            0b10000000, // L3
+            0b00000000,
+            0b00000000,
+            0b00000000,
+            0b10000000, // L4
+            0b00000000,
+            0b00000000,
+            0b00000000,
+            0b10000000, // L5
+            0b00000000,
+            0b00000000,
+            0b00000000,
+            0b10000000, // L6
+            0b00000000,
+            0b00000000,
+            0b00000000,
+            0b00000001, // L7
+            0b00000000,
+            0b00000000,
+            0b00000000,
+            0b10000000, // L8
+        ];
+        assert!(IntSet::<u32>::from_sparse_bit_set(&bytes).is_err());
+
+        // Set with values beyond u32
+        let bytes = [
+            0b0_00111_11, // BF 32, Depth 8
+            0b00000000,
+            0b00000000,
+            0b00000000,
+            0b10000000, // L1
+            0b00000000,
+            0b00000000,
+            0b00000000,
+            0b10000000, // L2
+            0b00000000,
+            0b00000000,
+            0b00000000,
+            0b10000000, // L3
+            0b00000000,
+            0b00000000,
+            0b00000000,
+            0b10000000, // L4
+            0b00000000,
+            0b00000000,
+            0b00000000,
+            0b10000000, // L5
+            0b00000000,
+            0b00000000,
+            0b00000000,
+            0b10000000, // L6
+            0b00000000,
+            0b00000000,
+            0b00000000,
+            0b00000001, // L7
+        ];
+        assert!(IntSet::<u32>::from_sparse_bit_set(&bytes).is_err());
+
+        // Set with filled node values beyond u32
+        let bytes = [
+            0b0_00111_11, // BF 32, Depth 8
+            0b00000000,
+            0b00000000,
+            0b00000000,
+            0b00000000,
+        ];
+        assert!(IntSet::<u32>::from_sparse_bit_set(&bytes).is_err());
     }
 
     #[test]
@@ -606,8 +720,29 @@ mod test {
     #[test]
     fn encode_maxu32() {
         let s: IntSet<u32> = [1, u32::MAX].iter().copied().collect();
+
         let bytes = s.to_sparse_bit_set();
         let s_prime = IntSet::<u32>::from_sparse_bit_set(&bytes);
         assert_eq!(s, s_prime.unwrap());
+
+        let s: IntSet<u32> = [1, u32::MAX].iter().copied().collect();
+        let bytes = to_sparse_bit_set_with_bf::<2>(&s);
+        let s_prime = IntSet::<u32>::from_sparse_bit_set(&bytes);
+        assert_eq!(s, s_prime.unwrap());
+
+        let s: IntSet<u32> = [1, u32::MAX].iter().copied().collect();
+        let bytes = to_sparse_bit_set_with_bf::<4>(&s);
+        let s_prime = IntSet::<u32>::from_sparse_bit_set(&bytes);
+        assert_eq!(s, s_prime.unwrap());
+
+        let s: IntSet<u32> = [1, u32::MAX].iter().copied().collect();
+        let bytes = to_sparse_bit_set_with_bf::<8>(&s);
+        let s_prime = IntSet::<u32>::from_sparse_bit_set(&bytes);
+        assert_eq!(s, s_prime.unwrap());
+
+        let s: IntSet<u32> = [1, u32::MAX].iter().copied().collect();
+        let bytes = to_sparse_bit_set_with_bf::<32>(&s);
+        let s_prime = IntSet::<u32>::from_sparse_bit_set(&bytes);
+        assert_eq!(s, s_prime.unwrap());
     }
 }
diff --git a/klippa/src/main.rs b/klippa/src/main.rs
index 81399740..5576fe37 100644
--- a/klippa/src/main.rs
+++ b/klippa/src/main.rs
@@ -1,6 +1,6 @@
 //! binary subset tool
 //!
-//! Takes a font file and a subset input which describes the desired subset, and ouput is a new
+//! Takes a font file and a subset input which describes the desired subset, and output is a new
 //! font file containing only the data specified in the input.
 //!
 
diff --git a/otexplorer/src/main.rs b/otexplorer/src/main.rs
index 943716e0..9d40df0b 100644
--- a/otexplorer/src/main.rs
+++ b/otexplorer/src/main.rs
@@ -204,7 +204,7 @@ mod flags {
     xflags::xflags! {
         /// Explore the contents of binary font files
         ///
-        /// otexplorer can print a textual representation of the the tables in
+        /// otexplorer can print a textual representation of the tables in
         /// a font file, or some subset of those tables.
         ///
         /// In addition to this, the -q option allows the user to provide a query,
diff --git a/resources/raw_tables/head.txt b/resources/raw_tables/head.txt
index 2dacbed8..d9fa6266 100644
--- a/resources/raw_tables/head.txt
+++ b/resources/raw_tables/head.txt
@@ -1,4 +1,4 @@
-# input to the codgen binary tool
+# input to the codegen binary tool
 @table Head <https://docs.microsoft.com/en-us/typography/opentype/spec/head>
     uint16	majorVersion	Major version number of the font header table — set to 1.
     uint16	minorVersion	Minor version number of the font header table — set to 0.
diff --git a/resources/scripts/bump-version.sh b/resources/scripts/bump-version.sh
index 26343109..2155eace 100755
--- a/resources/scripts/bump-version.sh
+++ b/resources/scripts/bump-version.sh
@@ -16,7 +16,7 @@ if [ $# -eq 0 ]; then
   die_with_usage "No arguments provided, must specify crate(s)"
 fi
 
-# bump is the last argument, crate list is everythign else
+# bump is the last argument, crate list is everything else
 bump="${@:$#}"
 set -- "${@:1:$(($#-1))}"
 crates=("$@")
diff --git a/skrifa/src/outline/autohint/script.rs b/skrifa/src/outline/autohint/script.rs
index f0a1b3a6..76e31291 100644
--- a/skrifa/src/outline/autohint/script.rs
+++ b/skrifa/src/outline/autohint/script.rs
@@ -40,7 +40,7 @@ impl ScriptRange {
     }
 }
 
-// These properties ostensibily come from
+// These properties ostensibly come from
 // <https://gitlab.freedesktop.org/freetype/freetype/-/blob/57617782464411201ce7bbc93b086c1b4d7d84a5/src/autofit/afblue.h#L317>
 // but are modified to match those at
 // <https://gitlab.freedesktop.org/freetype/freetype/-/blob/57617782464411201ce7bbc93b086c1b4d7d84a5/src/autofit/aflatin.h#L68>
diff --git a/write-fonts/src/error.rs b/write-fonts/src/error.rs
index 76b48af4..2ba4b66e 100644
--- a/write-fonts/src/error.rs
+++ b/write-fonts/src/error.rs
@@ -17,7 +17,7 @@ pub struct PackingError {
     pub(crate) graph: Arc<Graph>,
 }
 
-/// An error occured while writing this table
+/// An error occurred while writing this table
 #[derive(Debug, Clone)]
 pub enum Error {
     /// The table failed a validation check
diff --git a/write-fonts/src/font_builder.rs b/write-fonts/src/font_builder.rs
index d5c474c7..0c56c632 100644
--- a/write-fonts/src/font_builder.rs
+++ b/write-fonts/src/font_builder.rs
@@ -23,7 +23,7 @@ pub struct FontBuilder<'a> {
 #[derive(Clone, Debug)]
 #[non_exhaustive]
 pub struct BuilderError {
-    /// The tag of the root table where the error occured
+    /// The tag of the root table where the error occurred
     pub tag: Tag,
     /// The underlying error
     pub inner: crate::error::Error,
diff --git a/write-fonts/src/from_obj.rs b/write-fonts/src/from_obj.rs
index 6c65bfb8..e4b77e5f 100644
--- a/write-fonts/src/from_obj.rs
+++ b/write-fonts/src/from_obj.rs
@@ -105,14 +105,14 @@ where
     }
 }
 
-// A blanket impl to cover converting any Option<T> if T is convertable
+// A blanket impl to cover converting any Option<T> if T is convertible
 impl<T: FromObjRef<U>, U> FromObjRef<Option<U>> for Option<T> {
     fn from_obj_ref(from: &Option<U>, data: FontData) -> Self {
         from.as_ref().map(|inner| T::from_obj_ref(inner, data))
     }
 }
 
-// A blanket impl to cover converting any Option<T> if T is convertable
+// A blanket impl to cover converting any Option<T> if T is convertible
 impl<T: FromTableRef<U>, U> FromTableRef<Option<U>> for Option<T> {
     fn from_table_ref(from: &Option<U>) -> Self {
         from.as_ref().map(ToOwnedTable::to_owned_table)
diff --git a/write-fonts/src/graph.rs b/write-fonts/src/graph.rs
index 20af11eb..c9e4b0da 100644
--- a/write-fonts/src/graph.rs
+++ b/write-fonts/src/graph.rs
@@ -230,7 +230,7 @@ impl Graph {
     ///
     /// This is not public API, and you are responsible for ensuring that
     /// the graph is sorted before calling (by calling `pack_objects`, and
-    /// checking that it has succeded).
+    /// checking that it has succeeded).
     pub(crate) fn serialize(&self) -> Vec<u8> {
         fn write_offset(at: &mut [u8], len: OffsetLen, resolved: u32) {
             let at = &mut at[..len as u8 as usize];
@@ -1643,7 +1643,7 @@ mod tests {
         let mut graph = TableWriter::make_graph(&table);
         assert!(
             !graph.basic_sort(),
-            "simple sorting should not resovle this graph"
+            "simple sorting should not resolve this graph"
         );
 
         const BASE_LEN: usize = 10 // GPOS header len
@@ -1719,7 +1719,7 @@ mod tests {
         let mut graph = TableWriter::make_graph(&table);
         assert!(
             !graph.basic_sort(),
-            "simple sorting should not resovle this graph",
+            "simple sorting should not resolve this graph",
         );
 
         // uncomment these two lines if you want to visualize the graph:
diff --git a/write-fonts/src/graph/splitting/mark2base.rs b/write-fonts/src/graph/splitting/mark2base.rs
index 6ac0bd72..79af26d0 100644
--- a/write-fonts/src/graph/splitting/mark2base.rs
+++ b/write-fonts/src/graph/splitting/mark2base.rs
@@ -356,7 +356,7 @@ mod tests {
                             let val = u16_to_i16(i * mark_class_count + j);
                             if include_var_index_tables {
                                 // we want duplicate variation index tables, since it
-                                // poses different challanges when resolving offsets
+                                // poses different challenges when resolving offsets
                                 let var_idx = VariationIndex::new(j, j);
                                 AnchorTable::format_3(val, val, Some(var_idx.into()), None)
                             } else {
diff --git a/write-fonts/src/graph/splitting/pairpos.rs b/write-fonts/src/graph/splitting/pairpos.rs
index cd128a8a..00d8379d 100644
--- a/write-fonts/src/graph/splitting/pairpos.rs
+++ b/write-fonts/src/graph/splitting/pairpos.rs
@@ -169,7 +169,7 @@ fn split_pair_pos_format_2(graph: &mut Graph, subtable: ObjectId) -> Option<Vec<
         .intersects(rgpos::ValueFormat::ANY_DEVICE_OR_VARIDX);
 
     let mut visited = HashSet::new();
-    let mut next_device_offset = 3; // start after coverage + classs defs
+    let mut next_device_offset = 3; // start after coverage + class defs
     for (idx, class1rec) in pp2.class1_records().iter().enumerate() {
         let mut accumulated_delta = class1_record_size;
         coverage_size += estimator.increment_coverage_size(idx as _);
diff --git a/write-fonts/src/offsets.rs b/write-fonts/src/offsets.rs
index f0ad3ac9..a19adeea 100644
--- a/write-fonts/src/offsets.rs
+++ b/write-fonts/src/offsets.rs
@@ -98,7 +98,7 @@ impl<const N: usize, T> NullableOffsetMarker<T, N> {
 
     /// Set the contents of the marker, replacing any existing contents.
     ///
-    /// The argument must be some value; to set the offest to null, use the
+    /// The argument must be some value; to set the offset to null, use the
     /// [`clear`] method.
     ///
     /// [`clear`]: Self::clear
diff --git a/write-fonts/src/tables/glyf/simple.rs b/write-fonts/src/tables/glyf/simple.rs
index 3f89a9d9..9ef8ceab 100644
--- a/write-fonts/src/tables/glyf/simple.rs
+++ b/write-fonts/src/tables/glyf/simple.rs
@@ -989,7 +989,7 @@ mod tests {
                         path.close_path();
                         start_pt = None;
                     }
-                    _ => panic!("Usupported element type {:?}", el_type),
+                    _ => panic!("Unsupported element type {:?}", el_type),
                 }
             }
             paths.push(path);
@@ -1085,7 +1085,7 @@ mod tests {
     }
 
     #[test]
-    fn simple_glyphs_from_kurbo_2_quads_1_line_implictly_closed() {
+    fn simple_glyphs_from_kurbo_2_quads_1_line_implicitly_closed() {
         // same path elements as above 'MQQZ' but with the last_pt_equal_move=false
         // thus this actually contains three segments: 2 quads plus the last implied
         // closing line. There is an additional on-curve point at the end of the path.
diff --git a/write-fonts/src/tables/gvar.rs b/write-fonts/src/tables/gvar.rs
index 03c1a532..d6e4d892 100644
--- a/write-fonts/src/tables/gvar.rs
+++ b/write-fonts/src/tables/gvar.rs
@@ -264,7 +264,7 @@ impl GlyphVariations {
         let mut point_number_counts = IndexMap::new();
         // count how often each set of numbers occurs
         for deltas in &self.variations {
-            // for each set points, get compiled size + number of occurances
+            // for each set points, get compiled size + number of occurrences
             let (_, count) = point_number_counts
                 .entry(&deltas.best_point_packing)
                 .or_insert_with(|| {
diff --git a/write-fonts/src/tables/gvar/iup.rs b/write-fonts/src/tables/gvar/iup.rs
index 420370a4..103b738f 100644
--- a/write-fonts/src/tables/gvar/iup.rs
+++ b/write-fonts/src/tables/gvar/iup.rs
@@ -437,7 +437,7 @@ fn iup_contour_optimize(
         }
 
         let (x, y) = first_delta.to_point().ot_round();
-        // if all deltas are equal than the first is explict and the rest
+        // if all deltas are equal than the first is explicit and the rest
         // are interpolatable
         return Ok(std::iter::once(GlyphDelta::required(x, y))
             .chain(std::iter::repeat(GlyphDelta::optional(x, y)))
diff --git a/write-fonts/src/tables/layout.rs b/write-fonts/src/tables/layout.rs
index 3c97e8ce..dc27ebfb 100644
--- a/write-fonts/src/tables/layout.rs
+++ b/write-fonts/src/tables/layout.rs
@@ -29,7 +29,7 @@ macro_rules! lookup_type {
     };
 }
 
-/// A macro to define a newtype around an exisitng table, that defers all
+/// A macro to define a newtype around an existing table, that defers all
 /// impls to that table.
 ///
 /// We use this to ensure that shared lookup types (Sequence/Chain
diff --git a/write-fonts/src/tables/variations/ivs_builder.rs b/write-fonts/src/tables/variations/ivs_builder.rs
index 9784f530..f8735cec 100644
--- a/write-fonts/src/tables/variations/ivs_builder.rs
+++ b/write-fonts/src/tables/variations/ivs_builder.rs
@@ -345,7 +345,7 @@ impl<'a> Encoder<'a> {
                 continue;
             }
             // as items are combined, we leave `None` in the to_process list.
-            // This ensures that indicies are stable.
+            // This ensures that indices are stable.
             let (Some(mut to_update), Some(to_add)) = (
                 to_process.get_mut(i).and_then(Option::take),
                 to_process.get_mut(j).and_then(Option::take),
@@ -509,7 +509,7 @@ impl RowShape {
             })
     }
 
-    /// Returns a struct that maps the canonical regions to the column indicies
+    /// Returns a struct that maps the canonical regions to the column indices
     /// used in this ItemVariationData.
     fn region_map(&self) -> RegionMap {
         let mut with_idx = self.0.iter().copied().enumerate().collect::<Vec<_>>();
diff --git a/write-fonts/src/validate.rs b/write-fonts/src/validate.rs
index 3dadb055..39a2135c 100644
--- a/write-fonts/src/validate.rs
+++ b/write-fonts/src/validate.rs
@@ -92,7 +92,7 @@ enum LocationElem {
 impl ValidationCtx {
     /// Run the provided closer in the context of a new table.
     ///
-    /// Errors reported in the closure will include the provided identifer
+    /// Errors reported in the closure will include the provided identifier
     /// in their path.
     pub fn in_table(&mut self, name: &'static str, f: impl FnOnce(&mut ValidationCtx)) {
         self.with_elem(LocationElem::Table(name), f);


Test patch:
diff --git a/font-test-data/test_data/README.md b/font-test-data/test_data/README.md
index 12d42730..72d617ca 100644
--- a/font-test-data/test_data/README.md
+++ b/font-test-data/test_data/README.md
@@ -33,7 +33,7 @@ c <points>
 -
 ```
 With the following values:
-* `glyph-id`: the glyph indentifier
+* `glyph-id`: the glyph identifier
 * `font-size`: size in pixels per em. A size of 0 means unscaled
 * `hint-mode`: one of `none`, `full`, `light`, or `light-subpixel`
 * `points`: space separated list of points in `x, y` format