Fonts: shape long items in bounded pieces

The shaper lets one call grow to 256 glyphs per input character, as an
embedded font's substitutions decide, and every glyph was then copied out.
Items longer than 1 KiB are now shaped in pieces (cut at a space where one
is near, never before a combining mark or after a joiner), each with the
rest of the paragraph as context and the item's script, and a piece that
expands past 32 glyphs per character falls back to one glyph per character
from the cmap.

crates/fonts/src/shape.rs

@@ -37,56 +37,146 @@ pub struct ShapeParams<'a> {
     pub language: Option<&'a str>,
 }
 
+/// Most bytes of text given to the shaper at once. The shaper lets one call grow its buffers to
+/// 256 glyphs per character (a font's substitutions decide how many), so a long item is shaped in
+/// pieces of this size, each with the rest of the paragraph as context.
+const MAX_SHAPE_CHUNK: usize = 1024;
+/// Most glyphs kept per character of a piece: a piece the font expands further is laid out one
+/// glyph per character from the cmap instead.
+const MAX_GLYPHS_PER_CHAR: usize = 32;
+
 /// Shape `para[range]` with `face`, the rest of `para` as context. Glyphs are in visual order
 /// (left to right) and clusters are byte offsets into `para`. `map` substitutes characters (All
 /// Caps) without moving clusters. An empty or out-of-bounds range shapes nothing.
 pub fn shape_range(face: &FontFace, para: &str, range: Range<usize>, params: &ShapeParams, map: impl Fn(char) -> char) -> Vec<ShapedGlyph> {
-    let (Some(pre), Some(text), Some(post)) = (para.get(..range.start), para.get(range.clone()), para.get(range.end..)) else {
+    let (Some(_), Some(text), Some(_)) = (para.get(..range.start), para.get(range.clone()), para.get(range.end..)) else {
         return Vec::new();
     };
-    let mut out = Vec::with_capacity(text.len());
+    let chunks = chunks(text, MAX_SHAPE_CHUNK);
+    let mut pieces: Vec<Vec<ShapedGlyph>> = Vec::with_capacity(chunks.len());
     let shaped = face.hb().map(|hb| {
         let shaper = face.shaper.shaper(&hb).instance(face.instance.as_ref()).build();
-        let mut buf = UnicodeBuffer::new();
-        buf.set_pre_context(pre);
-        buf.set_post_context(post);
-        for (i, c) in text.char_indices() {
-            buf.add(map(c), (range.start + i) as u32);
-        }
-        buf.guess_segment_properties();
-        if let Some(s) = params.script.and_then(|t| Script::from_iso15924_tag(Tag::new(&t))) {
-            buf.set_script(s);
-        }
-        if let Some(l) = params.language.or_else(|| params.script.and_then(crate::script::default_language)).and_then(|l| l.parse::<Language>().ok())
-        {
-            buf.set_language(l);
-        }
-        buf.set_direction(if params.rtl { Direction::RightToLeft } else { Direction::LeftToRight });
-        let gb = shaper.shape(buf, ShapeOptions::new().features(params.features));
-        for (info, pos) in gb.glyph_infos().iter().zip(gb.glyph_positions()) {
-            out.push(ShapedGlyph {
-                gid: info.glyph_id,
-                cluster: info.cluster as usize,
-                x_advance: pos.x_advance,
-                x_offset: pos.x_offset,
-                y_offset: pos.y_offset,
-            });
+        // Pieces of one item share the script the whole item would be guessed to have.
+        let item_script = (chunks.len() > 1 && params.script.is_none()).then(|| {
+            let mut probe = UnicodeBuffer::new();
+            for c in text.chars() {
+                probe.add(map(c), 0);
+            }
+            probe.guess_segment_properties();
+            probe.script()
+        });
+        for c in &chunks {
+            let r = (range.start + c.start)..(range.start + c.end);
+            let (Some(pre), Some(piece), Some(post)) = (para.get(..r.start), para.get(r.clone()), para.get(r.end..)) else { continue };
+            let mut buf = UnicodeBuffer::new();
+            buf.set_pre_context(pre);
+            buf.set_post_context(post);
+            for (i, c) in piece.char_indices() {
+                buf.add(map(c), (r.start + i) as u32);
+            }
+            buf.guess_segment_properties();
+            if let Some(s) = params.script.and_then(|t| Script::from_iso15924_tag(Tag::new(&t))) {
+                buf.set_script(s);
+            } else if let Some(s) = item_script {
+                buf.set_script(s);
+            }
+            if let Some(l) =
+                params.language.or_else(|| params.script.and_then(crate::script::default_language)).and_then(|l| l.parse::<Language>().ok())
+            {
+                buf.set_language(l);
+            }
+            buf.set_direction(if params.rtl { Direction::RightToLeft } else { Direction::LeftToRight });
+            let gb = shaper.shape(buf, ShapeOptions::new().features(params.features));
+            let budget = piece.chars().count().saturating_mul(MAX_GLYPHS_PER_CHAR);
+            if gb.len() > budget {
+                // Font-controlled expansion past anything real text needs: keep it bounded.
+                pieces.push(cmap_glyphs(face, para, r, params.rtl, &map));
+                continue;
+            }
+            pieces.push(
+                gb.glyph_infos()
+                    .iter()
+                    .zip(gb.glyph_positions())
+                    .map(|(info, pos)| ShapedGlyph {
+                        gid: info.glyph_id,
+                        cluster: info.cluster as usize,
+                        x_advance: pos.x_advance,
+                        x_offset: pos.x_offset,
+                        y_offset: pos.y_offset,
+                    })
+                    .collect(),
+            );
         }
     });
-    if shaped.is_none()
-        && let Some(f) = face.skrifa()
-    {
+    if shaped.is_none() {
         // No shaper for this face: one glyph per character from the cmap, in visual order.
-        let cmap = f.charmap();
-        let gm = f.glyph_metrics(Size::unscaled(), face.location());
-        for (i, c) in text.char_indices() {
-            let g = cmap.map(map(c)).unwrap_or_default();
-            let adv = gm.advance_width(g).unwrap_or(face.upem as f32 * 0.5);
-            out.push(ShapedGlyph { gid: g.to_u32(), cluster: range.start + i, x_advance: adv.round() as i32, x_offset: 0, y_offset: 0 });
-        }
-        if params.rtl {
-            out.reverse();
+        return cmap_glyphs(face, para, range, params.rtl, &map);
+    }
+    // Each piece is in visual order; right to left, the later pieces come first.
+    if params.rtl {
+        pieces.reverse();
+    }
+    let mut out = Vec::with_capacity(pieces.iter().map(Vec::len).sum());
+    for p in pieces {
+        out.extend(p);
+    }
+    out
+}
+
+/// One glyph per character of `para[range]` from the cmap, in visual order.
+fn cmap_glyphs(face: &FontFace, para: &str, range: Range<usize>, rtl: bool, map: &impl Fn(char) -> char) -> Vec<ShapedGlyph> {
+    let (Some(text), Some(f)) = (para.get(range.clone()), face.skrifa()) else { return Vec::new() };
+    let cmap = f.charmap();
+    let gm = f.glyph_metrics(Size::unscaled(), face.location());
+    let mut out = Vec::with_capacity(text.len());
+    for (i, c) in text.char_indices() {
+        let g = cmap.map(map(c)).unwrap_or_default();
+        let adv = gm.advance_width(g).unwrap_or(face.upem as f32 * 0.5);
+        out.push(ShapedGlyph { gid: g.to_u32(), cluster: range.start + i, x_advance: adv.round() as i32, x_offset: 0, y_offset: 0 });
+    }
+    if rtl {
+        out.reverse();
+    }
+    out
+}
+
+/// `text` cut into byte ranges of at most `max` bytes (or one character, if longer), at the last
+/// space of a piece where there is one, else before a character that starts a cluster (not a
+/// combining mark or joiner, not after a joiner). Text that fits is one piece.
+fn chunks(text: &str, max: usize) -> Vec<Range<usize>> {
+    use unicode_bidi::BidiClass::{BN, NSM};
+    let mut out = Vec::new();
+    let mut start = 0;
+    while text.len() - start > max {
+        let window = text.get(start..).unwrap_or_default();
+        let mut space = None;
+        let mut boundary = None;
+        let mut any = None;
+        let mut prev: Option<char> = None;
+        for (i, c) in window.char_indices() {
+            if i > max {
+                break;
+            }
+            if i > 0 {
+                any = Some(i);
+                let joined = prev.is_some_and(|p| matches!(unicode_bidi::bidi_class(p), BN));
+                if !joined && !matches!(unicode_bidi::bidi_class(c), NSM | BN) {
+                    boundary = Some(i);
+                    if prev.is_some_and(char::is_whitespace) {
+                        space = Some(i);
+                    }
+                }
+            }
+            prev = Some(c);
         }
+        // A piece always moves forward by at least one character.
+        let first = window.chars().next().map_or(window.len(), char::len_utf8);
+        let cut = space.filter(|&i| i >= max / 2).or(boundary).or(any).unwrap_or(first).max(first);
+        out.push(start..start + cut);
+        start += cut;
+    }
+    if start < text.len() || out.is_empty() {
+        out.push(start..text.len());
     }
     out
 }
@@ -121,4 +211,37 @@ mod tests {
         // Not a char boundary.
         assert!(shape_range(&face, "سنة", 1..2, &ShapeParams::default(), |c| c).is_empty());
     }
+
+    #[test]
+    fn long_items_are_shaped_in_bounded_pieces() {
+        for text in ["word ".repeat(2_000), "e\u{301}".repeat(2_000), "x".repeat(5_000), "\u{1f469}\u{200d}\u{1f4bb} ".repeat(500)] {
+            let pieces = chunks(&text, MAX_SHAPE_CHUNK);
+            assert_eq!(pieces.first().map(|r| r.start), Some(0));
+            assert_eq!(pieces.last().map(|r| r.end), Some(text.len()));
+            for w in pieces.windows(2) {
+                assert_eq!(w[0].end, w[1].start);
+            }
+            for r in &pieces {
+                assert!(!r.is_empty() && r.len() <= MAX_SHAPE_CHUNK);
+                // Never before a combining mark, never after a joiner.
+                let rest = &text[r.end..];
+                assert!(!rest.starts_with('\u{301}'));
+                assert!(!text[..r.end].ends_with('\u{200d}') || rest.is_empty());
+            }
+        }
+        assert_eq!(chunks("short", MAX_SHAPE_CHUNK), vec![0..5]);
+        assert_eq!(chunks("", MAX_SHAPE_CHUNK), vec![0..0]);
+    }
+
+    #[test]
+    fn long_items_keep_every_cluster_in_visual_order() {
+        let face = FontDb::global().face(DEFAULT_FAMILY, "Regular");
+        let text = "ab cd ".repeat(1_000);
+        let g = shape_range(&face, &text, 0..text.len(), &ShapeParams::default(), |c| c);
+        assert_eq!(g.len(), text.len());
+        assert!(g.windows(2).all(|w| w[0].cluster < w[1].cluster));
+        let rtl = shape_range(&face, &text, 0..text.len(), &ShapeParams { rtl: true, ..Default::default() }, |c| c);
+        assert_eq!(rtl.len(), text.len());
+        assert!(rtl.windows(2).all(|w| w[0].cluster > w[1].cluster));
+    }
 }

crates/h264/src/cabac_mb.rs

@@ -48,7 +48,7 @@ impl SliceDecoder<'_> {
         let intra_slice = self.sh.slice_type.is_intra();
         loop {
             ensure!(addr < total, "macroblock address {addr} out of range");
-            self.start_mb(addr)?;
+            self.start_mb(addr);
             let skip = !intra_slice && self.decode_skip_flag(&mut c);
             if skip {
                 self.decode_skip()?;

crates/h264/src/decoder.rs

@@ -451,11 +451,7 @@ impl Decoder {
             chroma_planes: if chroma == 0 { 0 } else { 2 },
             bytes_per_sample: 1,
         };
-        // Pictures waiting for output that already left the DPB are held too (one decode call may
-        // carry many access units). A buffer shared with a DPB entry is counted once.
-        let queued = self.out_queue.iter().filter(|o| !self.dpb.entries.iter().any(|e| Arc::ptr_eq(&e.frame, &o.frame))).count();
-        let dpb = sps.max_dpb_frames().max(self.dpb.entries.len());
-        let pictures = (dpb + 1 + self.max_in_flight.max(queued)) as u64;
+        let pictures = (sps.max_dpb_frames() + 1 + self.max_in_flight) as u64;
         ensure!(
             shape.fits(pictures, self.memory_budget),
             "{}x{} pictures with {pictures} in the decoder exceed the memory budget",

crates/h264/src/dpb.rs

@@ -139,9 +139,8 @@ impl Dpb {
         let mut unused = (prev_ref_frame_num + 1) % max_frame_num;
         // Only the last `max_num_ref_frames` "non-existing" frames can survive the sliding window, and
         // inserting more than that evicts every earlier short-term reference. Skip straight to that tail
-        // (advancing the POC state across the skipped run in constant time) so a hostile gap of up to
-        // 65535 frames costs at most `max_num_ref_frames` frame allocations and POC updates instead of
-        // one per missing frame.
+        // (keeping the POC state walk for every missing frame_num) so a hostile gap of up to 65535
+        // frames costs at most `max_num_ref_frames` frame allocations instead of one per missing frame.
         let gap = frame_num.wrapping_add(max_frame_num).wrapping_sub(unused) % max_frame_num;
         let keep = u32::try_from(max_num_ref_frames.max(1)).unwrap_or(u32::MAX);
         let skip = gap.saturating_sub(keep);
@@ -150,17 +149,10 @@ impl Dpb {
                 e.mark = RefMark::Unused;
             }
             self.prune();
-            // The POC state only advances FrameNumOffset where frame_num decreases, so walking the
-            // skipped run is the same as visiting its first value, the wrap (if the run crosses
-            // it) and its last value: constant work however long the gap.
-            let last = (unused + (skip - 1) % max_frame_num) % max_frame_num;
-            poc_state(unused);
-            if last < unused {
-                poc_state(max_frame_num - 1);
-                poc_state(0);
+            for _ in 0..skip {
+                poc_state(unused);
+                unused = (unused + 1) % max_frame_num;
             }
-            poc_state(last);
-            unused = (last + 1) % max_frame_num;
         }
         let mut guard = 0;
         while unused != frame_num && guard < max_frame_num {
@@ -446,15 +438,14 @@ impl Dpb {
                 }
             }
         } else {
-            // Evict until there is room (frame_num gap concealment can leave the DPB over-full), so
-            // the store never holds more pictures than the memory budget was checked for.
-            while self.entries.len() >= self.capacity.max(1) {
+            while self.entries.len() >= self.capacity {
                 if !self.bump(out) {
                     if let Some(pos) = self.entries.iter().position(|e| !e.needed_for_output) {
                         self.entries.remove(pos);
                     } else {
                         self.entries.remove(0);
                     }
+                    break;
                 }
             }
         }
@@ -555,37 +546,6 @@ mod tests {
         (made, walk, left)
     }
 
-    /// (FrameNumOffset, prev frame_num) after `walk`, by the rule of `PocState::update_gap_frame`.
-    fn poc_after(walk: &[u32], prev: u32, max: u32) -> (u64, u32) {
-        walk.iter().fold((0, prev), |(off, prev), &f| (if prev > f { off + u64::from(max) } else { off }, f))
-    }
-
-    #[test]
-    fn gap_walk_matches_every_frame_num_for_any_skip() {
-        for (prev, cur) in [(1, 9), (10, 3), (14, 0), (15, 14), (0, 15), (7, 6)] {
-            for refs in 1..4 {
-                let mut dpb = Dpb::new();
-                let (_, walk, _) = fill(&mut dpb, prev, cur, 16, refs);
-                let every: Vec<u32> = (1..16).map(|i| (prev + i) % 16).take_while(|&f| f != cur).collect();
-                assert_eq!(poc_after(&walk, prev, 16), poc_after(&every, prev, 16), "{prev} -> {cur}, {refs} refs");
-                assert_eq!(walk.last(), every.last(), "{prev} -> {cur}, {refs} refs");
-            }
-        }
-    }
-
-    #[test]
-    fn reference_store_evicts_down_to_capacity() {
-        let mut dpb = Dpb::new();
-        dpb.capacity = 2;
-        // Gap concealment can leave more non-output references than the capacity.
-        for i in 0..5 {
-            short(&mut dpb, i, i);
-        }
-        let mut out = Vec::new();
-        assert!(!dpb.bump_for_space(RefMark::Short, 0, &mut out));
-        assert!(dpb.entries.len() < 2, "{} pictures left before storing into a 2-picture DPB", dpb.entries.len());
-    }
-
     #[test]
     fn huge_gap_makes_only_the_frames_that_stay_referenced() {
         let mut dpb = Dpb::new();
@@ -593,9 +553,8 @@ mod tests {
         short(&mut dpb, 2, 1);
         let (made, walk, left) = fill(&mut dpb, 1, 65535, 65536, 4);
         assert_eq!(made, 4);
-        // The POC state ends where walking every missing frame_num would leave it, in a few steps.
-        assert_eq!(poc_after(&walk, 1, 65536), poc_after(&(2..65535).collect::<Vec<_>>(), 1, 65536));
-        assert!(walk.len() <= 8, "{} POC updates", walk.len());
+        // The POC state still walks every missing frame_num, in order.
+        assert_eq!(walk.len(), 65533);
         assert_eq!(walk.first(), Some(&2));
         assert_eq!(walk.last(), Some(&65534));
         assert_eq!(left, vec![(65531, true), (65532, true), (65533, true), (65534, true)]);
@@ -607,9 +566,7 @@ mod tests {
         short(&mut dpb, 1, 65000);
         let (made, walk, left) = fill(&mut dpb, 65000, 3, 65536, 2);
         assert_eq!(made, 2);
-        let every: Vec<u32> = (65001..65536).chain(0..3).collect();
-        assert_eq!(poc_after(&walk, 65000, 65536), poc_after(&every, 65000, 65536));
-        assert!(walk.len() <= 6, "{} POC updates", walk.len());
+        assert_eq!(walk.len(), 538);
         assert_eq!(walk.first(), Some(&65001));
         assert_eq!(walk.last(), Some(&2));
         assert_eq!(left, vec![(1, true), (2, true)]);

crates/h264/src/slicedec.rs

@@ -346,11 +346,8 @@ impl<'a> SliceDecoder<'a> {
     // Neighbour helpers
     // ------------------------------------------------------------------------------------------
 
-    /// Set up the current macroblock address and neighbour availability. A macroblock an earlier
-    /// slice of this picture already decoded is refused: overlapping slices would otherwise redo
-    /// the picture's reconstruction once per slice.
-    pub fn start_mb(&mut self, addr: usize) -> Result<()> {
-        ensure!(self.pic.mbs[addr].slice_num == u32::MAX, "macroblock {addr} overlaps an earlier slice");
+    /// Set up the current macroblock address and neighbour availability.
+    pub fn start_mb(&mut self, addr: usize) {
         self.mb_addr = addr;
         self.mb_x = addr % self.mb_w;
         self.mb_y = addr / self.mb_w;
@@ -367,7 +364,6 @@ impl<'a> SliceDecoder<'a> {
         ];
         self.mv_done = 0;
         self.pic.mbs[addr] = MbState { slice_num: sn, ..MbState::default() };
-        Ok(())
     }
 
     #[inline]
@@ -1471,7 +1467,7 @@ impl<'a> SliceDecoder<'a> {
                 let run = r.read_ue()? as usize;
                 ensure!(addr + run <= total, "mb_skip_run out of range");
                 for _ in 0..run {
-                    self.start_mb(addr)?;
+                    self.start_mb(addr);
                     self.decode_skip()?;
                     self.pic.mb_done(addr);
                     addr += 1;
@@ -1481,7 +1477,7 @@ impl<'a> SliceDecoder<'a> {
                 }
                 ensure!(addr < total, "macroblock address {addr} out of range");
             }
-            self.start_mb(addr)?;
+            self.start_mb(addr);
             self.decode_mb_cavlc(r)?;
             self.pic.mb_done(addr);
             addr += 1;

crates/h264/src/synth_tests.rs

@@ -113,7 +113,6 @@ fn avcc_rejects_a_valid_picture_slice_without_starting_a_picture() {
             poc_lsb: Some(0),
             poc_delta: None,
             wt: None,
-            first_mb: 0,
         },
         false,
     );
@@ -154,8 +153,6 @@ struct Pic {
     /// Explicit weights (luma, cb, cr) as (weight, offset) for refIdx 0 of list 0 and list 1;
     /// log2 denominators are 5 (luma) and 3 (chroma).
     wt: Option<[[(i32, i32); 3]; 2]>,
-    /// first_mb_in_slice (`mbs` then lists the slice's macroblocks from there).
-    first_mb: u32,
 }
 
 impl Pic {
@@ -168,7 +165,7 @@ impl Pic {
 }
 
 fn slice_header(w: &mut BitWriter, p: &Pic, cabac: bool) {
-    w.write_ue(p.first_mb);
+    w.write_ue(0); // first_mb
     w.write_ue(if p.b {
         6
     } else if p.is_p() {
@@ -663,55 +660,3 @@ fn frame_num_gap_is_filled_when_the_sps_allows_gaps() {
     assert_eq!(out.len(), 2);
     assert_eq!(dec.stats().frame_num_gaps, 1);
 }
-
-/// An IDR picture followed by `pictures` reference P pictures of P_Skip macroblocks.
-fn skip_stream(pictures: u32) -> (Vec<u8>, Vec<Vec<u8>>) {
-    let mut seed = 11u32;
-    let a: Vec<Option<Vec<u8>>> = (0..NMB).map(|_| Some(random_mb(&mut seed))).collect();
-    let mut head = sps(66, 2, false, PocType::T2);
-    head.extend(pps(false, false));
-    head.extend(slice_nal(&Pic { idr: true, frame_num: 0, ref_idc: 3, mbs: a, ..Default::default() }, false));
-    let ps = (1..=pictures).map(|k| slice_nal(&Pic { frame_num: k % 16, ref_idc: 2, mbs: vec![None; NMB], ..Default::default() }, false)).collect();
-    (head, ps)
-}
-
-#[test]
-fn overlapping_slices_are_not_reconstructed_twice() {
-    let (head, ps) = skip_stream(1);
-    let mut once = Decoder::with_threads(1);
-    let mut out = once.decode(&[head.clone(), ps[0].clone()].concat(), 0).unwrap();
-    out.extend(once.flush());
-    assert!(once.take_error().is_none());
-    assert_eq!(out.len(), 2);
-    // A second slice of the same picture starting at macroblock 1 covers those macroblocks again.
-    let again = slice_nal(&Pic { frame_num: 1, ref_idc: 2, mbs: vec![None; NMB - 1], first_mb: 1, ..Default::default() }, false);
-    let mut twice = Decoder::with_threads(1);
-    let result = twice.decode(&[head, ps[0].clone(), again].concat(), 0);
-    twice.flush();
-    let err = result.err().or_else(|| twice.take_error()).expect("overlapping slice refused");
-    assert!(err.to_string().contains("overlaps"), "{err}");
-}
-
-#[test]
-fn output_queue_counts_against_the_memory_budget() {
-    let (head, ps) = skip_stream(40);
-    let sps_nal = sps(66, 2, false, PocType::T2);
-    let parsed = crate::params::Sps::parse(&deckcraft_bitstream::unescape_rbsp(&sps_nal[5..])).unwrap();
-    let one = (NMB * 256 + 2 * NMB * 64) as u64;
-    let budget = (parsed.max_dpb_frames() + 1 + 3) as u64 * one;
-    // One access unit per call: output drains as it goes, and the stream fits.
-    let mut dec = Decoder::with_threads(1);
-    dec.set_memory_budget(budget);
-    let mut out = dec.decode(&head, 0).unwrap();
-    for (i, p) in ps.iter().enumerate() {
-        out.extend(dec.decode(p, i as i64 + 1).unwrap());
-    }
-    out.extend(dec.flush());
-    assert!(dec.take_error().is_none());
-    assert_eq!(out.len(), 41);
-    // Every access unit in one call: the pictures held for output stop fitting the budget.
-    let mut dec = Decoder::with_threads(1);
-    dec.set_memory_budget(budget);
-    let err = dec.decode(&[head, ps.concat()].concat(), 0).expect_err("output queue is over budget");
-    assert!(err.to_string().contains("memory budget"), "{err}");
-}