1use 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
15pub(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 #[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#[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#[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#[derive(Clone, Copy, Default)]
96pub(crate) enum Coverage<'a> {
97 #[default]
99 None,
100 Glyphs(&'a [BigEndian<GlyphId16>]),
102 Ranges(&'a [RangeRecord]),
104 Glyphs24(&'a [BigEndian<GlyphId24>]),
106 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 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 pub fn present(&self) -> Option<&Self> {
132 (!self.is_none()).then_some(self)
133 }
134
135 #[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 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 #[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 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 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#[derive(Clone, Copy, Default)]
248pub(crate) enum ClassDef<'a> {
249 #[default]
251 None,
252 Array {
254 start: u16,
255 classes: &'a [BigEndian<u16>],
256 },
257 Ranges(&'a [ClassRangeRecord]),
259 Array24 {
261 start: u32,
262 classes: &'a [BigEndian<Uint24>],
263 },
264 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 #[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 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 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 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 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 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 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}