Skip to main content

harfrust/ot/lookup/
coverage.rs

1//! Coverage and class definition tables, reduced to the arrays they search.
2
3use super::Offsets;
4use crate::budget::{Budget, Exhausted};
5use crate::ot::layout::MAX_CONTEXT_LENGTH;
6use crate::set_digest::SetDigest;
7use alloc::boxed::Box;
8use core::cmp::Ordering;
9use read_fonts::tables::layout::{
10    self, ClassRangeRecord, ClassRangeRecord2, CoverageTable, RangeRecord, RangeRecord2,
11};
12use read_fonts::types::{BigEndian, GlyphId, GlyphId16, GlyphId24, Uint24};
13use read_fonts::{FontRead, ReadError};
14
15/// A coverage per context glyph, parsed eagerly only for short contexts.
16///
17/// Arrays longer than [`MAX_CONTEXT_LENGTH`] are read on demand. Overlapping
18/// subtables can otherwise multiply a small font into large allocations and
19/// parsing work.
20pub(crate) enum CoverageArray<'a> {
21    Cached(Box<[Coverage<'a>]>),
22    Uncached(Offsets<'a>),
23}
24
25impl Default for CoverageArray<'_> {
26    fn default() -> Self {
27        Self::Cached(Box::default())
28    }
29}
30
31impl<'a> CoverageArray<'a> {
32    pub fn new(offsets: Offsets<'a>, budget: &Budget) -> Result<Self, Exhausted> {
33        if offsets.len() > MAX_CONTEXT_LENGTH {
34            return Ok(Self::Uncached(offsets));
35        }
36        budget.work(offsets.len())?;
37        budget.alloc::<Coverage>(offsets.len())?;
38        Ok(Self::Cached(
39            (0..offsets.len())
40                .map(|index| read_coverage(&offsets, index))
41                .collect(),
42        ))
43    }
44
45    pub fn len(&self) -> usize {
46        match self {
47            Self::Cached(coverages) => coverages.len(),
48            Self::Uncached(offsets) => offsets.len(),
49        }
50    }
51
52    pub fn is_empty(&self) -> bool {
53        self.len() == 0
54    }
55
56    /// Missing or unreadable coverages cover no glyphs, in either form.
57    #[inline]
58    pub fn get(&self, index: usize) -> Coverage<'a> {
59        match self {
60            Self::Cached(coverages) => coverages.get(index).copied().unwrap_or_default(),
61            Self::Uncached(offsets) => read_coverage(offsets, index),
62        }
63    }
64}
65
66/// The coverage at `index` of `offsets`, which is empty if it is null or
67/// can't be read. Kept out of line so that the cached arrays of short
68/// contexts, which are nearly all of them, inline into the matchers.
69#[inline(never)]
70fn read_coverage<'a>(offsets: &Offsets<'a>, index: usize) -> Coverage<'a> {
71    offsets.data(index).map_or(Coverage::None, |data| {
72        Coverage::new(CoverageTable::read(data))
73    })
74}
75
76/// The position of `gid` among sorted ranges of glyphs.
77#[inline]
78fn find_range<T, G: PartialOrd>(ranges: &[T], gid: G, bounds: impl Fn(&T) -> (G, G)) -> Option<&T> {
79    ranges
80        .binary_search_by(|range| {
81            let (start, end) = bounds(range);
82            if end < gid {
83                Ordering::Less
84            } else if start > gid {
85                Ordering::Greater
86            } else {
87                Ordering::Equal
88            }
89        })
90        .ok()
91        .map(|index| &ranges[index])
92}
93
94/// A coverage table: the glyphs it covers, each with a coverage index.
95#[derive(Clone, Copy, Default)]
96pub(crate) enum Coverage<'a> {
97    /// A null or unreadable table, which covers nothing.
98    #[default]
99    None,
100    /// Sorted glyphs, each covered at its position.
101    Glyphs(&'a [BigEndian<GlyphId16>]),
102    /// Sorted glyph ranges, each with the index of its first glyph.
103    Ranges(&'a [RangeRecord]),
104    /// Sorted 24-bit glyphs.
105    Glyphs24(&'a [BigEndian<GlyphId24>]),
106    /// Sorted 24-bit glyph ranges.
107    Ranges24(&'a [RangeRecord2]),
108}
109
110impl<'a> Coverage<'a> {
111    pub fn new(table: Result<CoverageTable<'a>, ReadError>) -> Self {
112        match table {
113            Ok(CoverageTable::Format1(table)) => Self::Glyphs(table.glyph_array()),
114            Ok(CoverageTable::Format2(table)) => Self::Ranges(table.range_records()),
115            Ok(CoverageTable::Format3(table)) => Self::Glyphs24(table.glyph_array()),
116            Ok(CoverageTable::Format4(table)) => Self::Ranges24(table.range_records()),
117            Err(_) => Self::None,
118        }
119    }
120
121    /// A coverage that must be present, or `None` if it can't be read.
122    pub fn required(table: Result<CoverageTable<'a>, ReadError>) -> Option<Self> {
123        Some(Self::new(table)).filter(|coverage| !coverage.is_none())
124    }
125
126    pub fn is_none(&self) -> bool {
127        matches!(self, Self::None)
128    }
129
130    /// The coverage, or `None` if the table is missing.
131    pub fn present(&self) -> Option<&Self> {
132        (!self.is_none()).then_some(self)
133    }
134
135    /// The coverage index of `gid`, if it is covered.
136    #[inline(always)]
137    pub fn get(&self, gid: impl Into<GlyphId>) -> Option<u32> {
138        let gid = gid.into();
139        match self {
140            Self::None => None,
141            Self::Glyphs(glyphs) => {
142                let gid = GlyphId16::try_from(gid).ok()?;
143                glyphs
144                    .binary_search(&gid.into())
145                    .ok()
146                    .map(|index| index as u32)
147            }
148            Self::Ranges(ranges) => {
149                let gid = GlyphId16::try_from(gid).ok()?;
150                let range = find_range(ranges, gid, |r| (r.start_glyph_id(), r.end_glyph_id()))?;
151                // Subtract first so the index can't overflow on the way.
152                range
153                    .start_coverage_index()
154                    .checked_add(gid.to_u16() - range.start_glyph_id().to_u16())
155                    .map(u32::from)
156            }
157            Self::Glyphs24(_) | Self::Ranges24(_) => self.get_wide(gid),
158        }
159    }
160
161    // The 24-bit formats share one call, which keeps the inlined lookups
162    // of the original formats as small as they were.
163    #[inline(never)]
164    fn get_wide(&self, gid: GlyphId) -> Option<u32> {
165        match self {
166            Self::Glyphs24(glyphs) => glyphs24_index(glyphs, gid),
167            Self::Ranges24(ranges) => ranges24_index(ranges, gid),
168            _ => None,
169        }
170    }
171
172    /// The cost of looking up a glyph: the number of bits in the length of
173    /// the array searched.
174    pub fn cost(&self) -> u32 {
175        let bits = |len: usize| u32::BITS - (len as u32).leading_zeros();
176        match self {
177            Self::None => 0,
178            Self::Glyphs(glyphs) => bits(glyphs.len()),
179            Self::Ranges(ranges) => bits(ranges.len()),
180            Self::Glyphs24(glyphs) => bits(glyphs.len()),
181            Self::Ranges24(ranges) => bits(ranges.len()),
182        }
183    }
184
185    pub fn covers(&self, gid: impl Into<GlyphId>) -> bool {
186        self.get(gid).is_some()
187    }
188
189    /// The glyphs covered, or every glyph if the table is missing.
190    pub fn digest(&self, budget: &Budget) -> Result<SetDigest, Exhausted> {
191        let mut digest = SetDigest::new();
192        match self {
193            Self::None => return Ok(SetDigest::full()),
194            Self::Glyphs(glyphs) => {
195                budget.work(glyphs.len())?;
196                for glyph in *glyphs {
197                    digest.add(glyph.get().into());
198                }
199            }
200            Self::Ranges(ranges) => {
201                budget.work(ranges.len())?;
202                for range in *ranges {
203                    digest.add_range(range.start_glyph_id().into(), range.end_glyph_id().into());
204                }
205            }
206            Self::Glyphs24(glyphs) => {
207                budget.work(glyphs.len())?;
208                for glyph in *glyphs {
209                    digest.add(glyph.get().to_u32());
210                }
211            }
212            Self::Ranges24(ranges) => {
213                budget.work(ranges.len())?;
214                for range in *ranges {
215                    digest.add_range(
216                        range.start_glyph_id().to_u32(),
217                        range.end_glyph_id().to_u32(),
218                    );
219                }
220            }
221        }
222        Ok(digest)
223    }
224}
225
226fn glyphs24_index(glyphs: &[BigEndian<GlyphId24>], gid: GlyphId) -> Option<u32> {
227    let gid = GlyphId24::checked_new(gid.to_u32())?;
228    glyphs
229        .binary_search(&gid.into())
230        .ok()
231        .map(|index| index as u32)
232}
233
234fn ranges24_index(ranges: &[RangeRecord2], gid: GlyphId) -> Option<u32> {
235    let gid = gid.to_u32();
236    let range = find_range(ranges, gid, |r| {
237        (r.start_glyph_id().to_u32(), r.end_glyph_id().to_u32())
238    })?;
239    let index = range
240        .start_coverage_index()
241        .to_u32()
242        .checked_add(gid - range.start_glyph_id().to_u32())?;
243    (index <= Uint24::MAX.to_u32()).then_some(index)
244}
245
246/// A class definition table: the class of each glyph, 0 if unlisted.
247#[derive(Clone, Copy, Default)]
248pub(crate) enum ClassDef<'a> {
249    /// A null or unreadable table, which puts every glyph in class 0.
250    #[default]
251    None,
252    /// The classes of consecutive glyphs from `start`.
253    Array {
254        start: u16,
255        classes: &'a [BigEndian<u16>],
256    },
257    /// Sorted glyph ranges, each with a class.
258    Ranges(&'a [ClassRangeRecord]),
259    /// The 24-bit classes of consecutive glyphs from a 24-bit `start`.
260    Array24 {
261        start: u32,
262        classes: &'a [BigEndian<Uint24>],
263    },
264    /// Sorted 24-bit glyph ranges.
265    Ranges24(&'a [ClassRangeRecord2]),
266}
267
268impl<'a> ClassDef<'a> {
269    pub fn new(table: Result<layout::ClassDef<'a>, ReadError>) -> Self {
270        match table {
271            Ok(layout::ClassDef::Format1(table)) => Self::Array {
272                start: table.start_glyph_id().to_u16(),
273                classes: table.class_value_array(),
274            },
275            Ok(layout::ClassDef::Format2(table)) => Self::Ranges(table.class_range_records()),
276            Ok(layout::ClassDef::Format3(table)) => Self::Array24 {
277                start: table.start_glyph_id().to_u32(),
278                classes: table.class_value_array(),
279            },
280            Ok(layout::ClassDef::Format4(table)) => Self::Ranges24(table.class_range_records()),
281            Err(_) => Self::None,
282        }
283    }
284
285    pub fn is_none(&self) -> bool {
286        matches!(self, Self::None)
287    }
288
289    /// The class of `gid`.
290    #[inline(always)]
291    pub fn get(&self, gid: impl Into<GlyphId>) -> u32 {
292        let gid = gid.into();
293        match self {
294            Self::None => 0,
295            Self::Array { start, classes } => gid
296                .to_u32()
297                .checked_sub(u32::from(*start))
298                .and_then(|index| classes.get(index as usize))
299                .map_or(0, |class| class.get().into()),
300            Self::Ranges(ranges) => GlyphId16::try_from(gid)
301                .ok()
302                .and_then(|gid| find_range(ranges, gid, |r| (r.start_glyph_id(), r.end_glyph_id())))
303                .map_or(0, |range| range.class().into()),
304            Self::Array24 { .. } | Self::Ranges24(_) => self.get_wide(gid),
305        }
306    }
307
308    #[inline(never)]
309    fn get_wide(&self, gid: GlyphId) -> u32 {
310        match self {
311            Self::Array24 { start, classes } => array24_class(*start, classes, gid),
312            Self::Ranges24(ranges) => ranges24_class(ranges, gid),
313            _ => 0,
314        }
315    }
316
317    /// The cost of looking up a glyph, which decides which subtable gets
318    /// the glyph-info class cache.
319    pub fn cost(&self) -> u32 {
320        let bits = |len: usize| u32::BITS - (len as u32).leading_zeros();
321        match self {
322            Self::None => 0,
323            Self::Array { .. } | Self::Array24 { .. } => 1,
324            Self::Ranges(ranges) => bits(ranges.len()),
325            Self::Ranges24(ranges) => bits(ranges.len()),
326        }
327    }
328
329    /// Adds the glyphs of `class` to `digest`. Class 0 holds every glyph not
330    /// listed, so it adds all of them.
331    pub fn add_class_to(
332        &self,
333        digest: &mut SetDigest,
334        class: u32,
335        budget: &Budget,
336    ) -> Result<(), Exhausted> {
337        if class == 0 {
338            *digest = SetDigest::full();
339            return Ok(());
340        }
341        match self {
342            Self::None => {}
343            Self::Array { start, classes } => {
344                budget.work(classes.len())?;
345                for (index, value) in classes.iter().enumerate() {
346                    if u32::from(value.get()) == class {
347                        digest.add(u32::from(start.saturating_add(index as u16)));
348                    }
349                }
350            }
351            Self::Ranges(ranges) => {
352                budget.work(ranges.len())?;
353                for range in *ranges {
354                    if u32::from(range.class()) == class {
355                        budget.work(
356                            usize::from(range.end_glyph_id().to_u16())
357                                .saturating_sub(usize::from(range.start_glyph_id().to_u16()))
358                                + 1,
359                        )?;
360                        for glyph in range.start_glyph_id().to_u16()..=range.end_glyph_id().to_u16()
361                        {
362                            digest.add(u32::from(glyph));
363                        }
364                    }
365                }
366            }
367            Self::Array24 { start, classes } => {
368                budget.work(classes.len())?;
369                for (index, value) in classes.iter().enumerate() {
370                    if value.get().to_u32() == class {
371                        digest.add(start.saturating_add(index as u32));
372                    }
373                }
374            }
375            Self::Ranges24(ranges) => {
376                budget.work(ranges.len())?;
377                for range in *ranges {
378                    if u32::from(range.class()) == class {
379                        budget.work(
380                            (range.end_glyph_id().to_u32())
381                                .saturating_sub(range.start_glyph_id().to_u32())
382                                as usize
383                                + 1,
384                        )?;
385                        for glyph in range.start_glyph_id().to_u32()..=range.end_glyph_id().to_u32()
386                        {
387                            digest.add(glyph);
388                        }
389                    }
390                }
391            }
392        }
393        Ok(())
394    }
395}
396
397fn array24_class(start: u32, classes: &[BigEndian<Uint24>], gid: GlyphId) -> u32 {
398    gid.to_u32()
399        .checked_sub(start)
400        .and_then(|index| classes.get(index as usize))
401        .map_or(0, |class| class.get().to_u32())
402}
403
404fn ranges24_class(ranges: &[ClassRangeRecord2], gid: GlyphId) -> u32 {
405    let gid = gid.to_u32();
406    find_range(ranges, gid, |r| {
407        (r.start_glyph_id().to_u32(), r.end_glyph_id().to_u32())
408    })
409    .map_or(0, |range| range.class().into())
410}
411
412#[cfg(test)]
413mod tests {
414    use super::*;
415    use alloc::vec::Vec;
416    use read_fonts::FontData;
417
418    /// Data holding 16-bit offsets followed by `tables`. `None` is a null
419    /// offset and `Some(at)` points `at` bytes into `tables`.
420    fn offsets_then(offsets: &[Option<u16>], tables: &[u8]) -> Vec<u8> {
421        let base = (offsets.len() * 2) as u16;
422        let mut bytes: Vec<u8> = offsets
423            .iter()
424            .flat_map(|offset| offset.map_or(0, |at| base + at).to_be_bytes())
425            .collect();
426        bytes.extend_from_slice(tables);
427        bytes
428    }
429
430    fn array<'a>(bytes: &'a [u8], count: usize, budget: &Budget) -> CoverageArray<'a> {
431        let offsets = Offsets::new(FontData::new(bytes), 0..count * 2, 2);
432        CoverageArray::new(offsets, budget).unwrap()
433    }
434
435    #[test]
436    fn class_range_expansion_is_charged() {
437        let words: [u16; 5] = [2, 1, 0, u16::MAX, 1];
438        let bytes: Vec<_> = words.into_iter().flat_map(u16::to_be_bytes).collect();
439        let class = ClassDef::new(layout::ClassDef::read(FontData::new(&bytes)));
440        let mut digest = SetDigest::new();
441        assert_eq!(
442            class.add_class_to(&mut digest, 1, &Budget::new(10, 0)),
443            Err(Exhausted)
444        );
445        assert!(!digest.may_have(0));
446        class
447            .add_class_to(&mut digest, 1, &Budget::new(65_537, 0))
448            .unwrap();
449        assert!(digest.may_have(u32::from(u16::MAX)));
450    }
451
452    #[test]
453    fn coverage_arrays_keep_long_contexts_without_parsing_every_offset() {
454        // Two format 1 coverages, of glyphs 42 and 43.
455        let tables = [0, 1, 0, 1, 0, 42, 0, 1, 0, 1, 0, 43];
456        for count in [MAX_CONTEXT_LENGTH, MAX_CONTEXT_LENGTH + 1, 20_000] {
457            // Many entries can alias the same coverage in a tiny font.
458            let mut offsets = alloc::vec![Some(0); count];
459            offsets[count - 1] = Some(6);
460            let bytes = offsets_then(&offsets, &tables);
461            let budget = Budget::for_table_bytes(bytes.len());
462            let coverages = array(&bytes, count, &budget);
463            assert_eq!(coverages.len(), count);
464            assert!(!coverages.is_empty());
465            assert_eq!(coverages.get(0).get(42u32), Some(0));
466            assert_eq!(coverages.get(count - 1).get(43u32), Some(0));
467            assert!(!coverages.get(count - 1).covers(42u32));
468            assert!(coverages.get(count).is_none());
469            assert_eq!(
470                matches!(coverages, CoverageArray::Cached(_)),
471                count <= MAX_CONTEXT_LENGTH,
472            );
473        }
474    }
475
476    #[test]
477    fn cached_and_uncached_arrays_handle_unreadable_coverages_the_same_way() {
478        let tables = [0, 1, 0, 1, 0, 42];
479        for count in [MAX_CONTEXT_LENGTH, MAX_CONTEXT_LENGTH + 1] {
480            let mut offsets = alloc::vec![Some(0); count];
481            // Null, out of bounds, and an unsupported coverage format.
482            offsets[0] = None;
483            offsets[1] = Some(u16::MAX - (count * 2) as u16);
484            offsets[2] = Some(1);
485            let bytes = offsets_then(&offsets, &tables);
486            let budget = Budget::for_table_bytes(bytes.len());
487            let coverages = array(&bytes, count, &budget);
488            for index in [0, 1, 2, count] {
489                let coverage = coverages.get(index);
490                assert!(coverage.is_none());
491                assert!(!coverage.covers(42u32));
492                assert!(coverage.digest(&Budget::new(0, 0)).unwrap().may_have(42));
493            }
494            assert_eq!(coverages.get(3).get(42u32), Some(0));
495        }
496    }
497
498    #[test]
499    fn empty_coverage_arrays_cover_nothing() {
500        for coverages in [CoverageArray::default(), array(&[], 0, &Budget::new(0, 0))] {
501            assert!(coverages.is_empty());
502            assert_eq!(coverages.len(), 0);
503            assert!(coverages.get(0).is_none());
504        }
505    }
506}