1use super::coverage::Coverage;
4use super::{context, gpos, gsub, CachedLookup, CachedSubtable, IntoKind, SubtableDigests};
5use crate::budget::{Budget, Exhausted};
6use crate::ot::apply::MappingCache;
7use crate::set_digest::SetDigest;
8use alloc::{boxed::Box, vec::Vec};
9use read_fonts::model::Tables;
10use read_fonts::tables::{
11 gpos::{CursivePos, MarkBasePos, MarkLigPos, MarkMarkPos, PairPos, SinglePos},
12 gsub::{
13 AlternateSubst, ExtensionSubstFormat1, LigatureSubst, MultipleSubst,
14 ReverseChainSingleSubst, SingleSubst,
15 },
16 layout::{
17 ChainedSequenceContext, CoverageTable, Lookup, LookupFlag, SelectedLookupList,
18 SequenceContext,
19 },
20};
21use read_fonts::{FontData, FontRead, ReadError, TableProvider};
22
23const MAX_CACHED_SUBTABLES: usize = 8;
25
26const MIN_CACHED_COVERAGE_COST: u32 = 4;
29
30#[derive(Debug, PartialEq, Eq)]
32pub(super) enum BuildError {
33 Invalid,
34 Exhausted,
35}
36
37impl From<ReadError> for BuildError {
38 fn from(_: ReadError) -> Self {
39 Self::Invalid
40 }
41}
42
43impl From<Exhausted> for BuildError {
44 fn from(_: Exhausted) -> Self {
45 Self::Exhausted
46 }
47}
48
49pub(super) fn lookup_count(tables: &Tables, is_subst: bool) -> u16 {
51 let count = if is_subst {
52 tables
53 .gsub()
54 .ok()
55 .and_then(|gsub| gsub.lookup_list().ok())
56 .map(|list| list.lookup_count())
57 } else {
58 tables
59 .gpos()
60 .ok()
61 .and_then(|gpos| gpos.lookup_list().ok())
62 .map(|list| list.lookup_count())
63 };
64 count.unwrap_or_default()
65}
66
67pub(super) fn build_lookup<'a>(
69 tables: &'a Tables,
70 is_subst: bool,
71 index: u16,
72 budget: &Budget,
73) -> Result<CachedLookup<'a>, BuildError> {
74 let (list_data, offset) = if is_subst {
75 lookup_location(&tables.gsub()?.lookup_list()?, index)
76 } else {
77 lookup_location(&tables.gpos()?.lookup_list()?, index)
78 }
79 .ok_or(BuildError::Invalid)?;
80 build_lookup_at(list_data, offset, is_subst, budget)
81}
82
83fn lookup_location<'a, T: FontRead<'a, Args = ()> + 'a>(
85 list: &SelectedLookupList<'a, T>,
86 index: u16,
87) -> Option<(FontData<'a>, usize)> {
88 let index = usize::from(index);
89 let offset = match list {
90 SelectedLookupList::Original(list) => list.lookup_offsets().get(index)?.get().to_u32(),
91 SelectedLookupList::Extended(list) => list.lookup_offsets().get(index)?.get().to_u32(),
92 };
93 Some((list.offset_data(), offset as usize))
94}
95
96pub(super) fn build_lookup_at<'a>(
98 table_data: FontData<'a>,
99 offset: usize,
100 is_subst: bool,
101 budget: &Budget,
102) -> Result<CachedLookup<'a>, BuildError> {
103 budget.work(1)?;
104 let lookup: Lookup<()> =
105 Lookup::read(table_data.split_off(offset).ok_or(BuildError::Invalid)?)?;
106 let count = usize::from(lookup.sub_table_count());
107 budget.work(count)?;
108 budget.alloc::<CachedSubtable>(count)?;
109 let lookup_type = lookup.lookup_type();
110 let flag = lookup.lookup_flag();
111 let mut props = u32::from(flag.to_bits());
112 if flag.to_bits() & LookupFlag::USE_MARK_FILTERING_SET.to_bits() != 0 {
113 props |= u32::from(lookup.mark_filtering_set().unwrap_or_default()) << 16;
114 }
115 let mut cached = CachedLookup {
116 props,
117 is_subst,
118 is_reversed: is_subst && is_reversed(table_data, &lookup, offset).unwrap_or_default(),
119 digest: SetDigest::new(),
120 digest_second: SetDigest::new(),
121 hot_subtable: None,
122 uses_class_cache: false,
123 walk: super::walk_each,
124 subtables: Vec::with_capacity(count),
125 };
126 let mut hot_cost = 0;
127 let mut all_share_second_glyph = true;
128 for (index, subtable_offset) in lookup.subtable_offsets().iter().enumerate() {
129 let source = Source {
130 table_data,
131 offset: offset + subtable_offset.get().to_u32() as usize,
132 is_subst,
133 with_caches: index < MAX_CACHED_SUBTABLES,
134 budget,
135 };
136 let built = match source.build(lookup_type) {
137 Ok(built) => built,
138 Err(BuildError::Invalid) => continue,
139 Err(BuildError::Exhausted) => return Err(BuildError::Exhausted),
140 };
141 all_share_second_glyph &= built.shares_second_glyph;
142 cached.digest.union(&built.subtable.digest);
143 cached.digest_second.union(&built.digest_second);
144 if built.cache_cost > hot_cost {
145 hot_cost = built.cache_cost;
146 cached.hot_subtable = Some(cached.subtables.len());
147 }
148 cached.subtables.push(built.subtable);
149 }
150 cached.uses_class_cache = cached.hot_subtable.is_some();
152 cached.walk = match cached.subtables.len() {
153 1 => super::walk_single,
154 _ if all_share_second_glyph => super::walk_sharing_second_glyph,
155 _ => super::walk_each,
156 };
157 Ok(cached)
158}
159
160fn is_extension(is_subst: bool, lookup_type: u16) -> bool {
161 lookup_type == if is_subst { 7 } else { 9 }
162}
163
164fn is_reversed(table_data: FontData, lookup: &Lookup<()>, lookup_offset: usize) -> Option<bool> {
166 match lookup.lookup_type() {
167 8 => Some(true),
168 7 => {
169 let offset = lookup_offset + lookup.subtable_offsets().first()?.get().to_u32() as usize;
170 let ext = ExtensionSubstFormat1::<()>::read(table_data.split_off(offset)?).ok()?;
171 let ext_type = ext.extension_lookup_type();
172 (!is_extension(true, ext_type)).then_some(ext_type == 8)
173 }
174 _ => Some(false),
175 }
176}
177
178struct BuiltSubtable<'a> {
180 subtable: CachedSubtable<'a>,
181 digest_second: SetDigest,
182 cache_cost: u32,
183 shares_second_glyph: bool,
185}
186
187#[derive(Clone, Copy)]
189struct Source<'a, 'b> {
190 table_data: FontData<'a>,
191 offset: usize,
192 is_subst: bool,
193 with_caches: bool,
194 budget: &'b Budget,
195}
196
197impl<'a> Source<'a, '_> {
198 fn build(self, lookup_type: u16) -> Result<BuiltSubtable<'a>, BuildError> {
199 let data = self
200 .table_data
201 .split_off(self.offset)
202 .ok_or(BuildError::Invalid)?;
203 self.budget.work(1)?;
204 let budget = self.budget;
205 let caches = self.with_caches;
206 match (self.is_subst, lookup_type) {
207 (true, 1) => match SingleSubst::read(data)? {
208 SingleSubst::Format1(t) => self.finish(t.coverage(), gsub::SingleSubst1::new(&t)),
209 SingleSubst::Format2(t) => self.finish(t.coverage(), gsub::SingleSubst2::new(&t)),
210 SingleSubst::Format3(t) => {
211 self.finish(t.coverage(), gsub::SingleSubst1::new_wide(&t))
212 }
213 SingleSubst::Format4(t) => {
214 self.finish(t.coverage(), gsub::SingleSubst2::new_wide(&t))
215 }
216 },
217 (true, 2) => match MultipleSubst::read(data)? {
218 MultipleSubst::Format1(t) => {
219 self.finish(t.coverage(), gsub::MultipleSubst1::new(&t))
220 }
221 MultipleSubst::Format2(t) => {
222 self.finish(t.coverage(), gsub::MultipleSubst1::new_wide(&t))
223 }
224 },
225 (true, 3) => match AlternateSubst::read(data)? {
226 AlternateSubst::Format1(t) => {
227 self.finish(t.coverage(), gsub::AlternateSubst1::new(&t))
228 }
229 AlternateSubst::Format2(t) => {
230 self.finish(t.coverage(), gsub::AlternateSubst1::new_wide(&t))
231 }
232 },
233 (true, 4) => match LigatureSubst::read(data)? {
234 LigatureSubst::Format1(t) => {
235 self.finish(t.coverage(), Some(gsub::LigatureSubst1::new(&t, budget)?))
236 }
237 LigatureSubst::Format2(t) => self.finish(
238 t.coverage(),
239 Some(gsub::LigatureSubst1::new_wide(&t, budget)?),
240 ),
241 },
242 (true, 8) => match ReverseChainSingleSubst::read(data)? {
243 ReverseChainSingleSubst::Format1(t) => {
244 self.finish(t.coverage(), gsub::ReverseChainSubst1::new(&t, budget)?)
245 }
246 ReverseChainSingleSubst::Format2(t) => self.finish(
247 t.coverage(),
248 gsub::ReverseChainSubst1::new_wide(&t, budget)?,
249 ),
250 },
251 (false, 1) => match SinglePos::read(data)? {
252 SinglePos::Format1(t) => self.finish(t.coverage(), gpos::SinglePos1::new(&t)),
253 SinglePos::Format2(t) => self.finish(t.coverage(), gpos::SinglePos2::new(&t)),
254 SinglePos::Format3(t) => self.finish(t.coverage(), gpos::SinglePos1::new_wide(&t)),
255 SinglePos::Format4(t) => self.finish(t.coverage(), gpos::SinglePos2::new_wide(&t)),
256 },
257 (false, 2) => match PairPos::read(data)? {
258 PairPos::Format1(t) => match gpos::PairKern1::new(&t, budget)? {
259 Some(kern) => self.finish(t.coverage(), Some(kern)),
260 None => self.finish(t.coverage(), Some(gpos::PairPos1::new(&t, budget)?)),
261 },
262 PairPos::Format2(t) => self.class_pairs(t.coverage(), gpos::ClassPairs::new(&t)),
263 PairPos::Format3(t) => {
264 self.finish(t.coverage(), Some(gpos::PairPos1::new_wide(&t, budget)?))
265 }
266 PairPos::Format4(t) => {
267 self.class_pairs(t.coverage(), gpos::ClassPairs::new_wide(&t))
268 }
269 },
270 (false, 3) => match CursivePos::read(data)? {
271 CursivePos::Format1(t) => self.finish(t.coverage(), gpos::CursivePos1::new(&t)),
272 CursivePos::Format2(t) => {
273 self.finish(t.coverage(), gpos::CursivePos1::new_wide(&t))
274 }
275 },
276 (false, 4) => match MarkBasePos::read(data)? {
277 MarkBasePos::Format1(t) => {
278 self.finish(t.mark_coverage(), gpos::MarkBasePos1::new(&t))
279 }
280 MarkBasePos::Format2(t) => {
281 self.finish(t.mark_coverage(), gpos::MarkBasePos1::new_wide(&t))
282 }
283 },
284 (false, 5) => match MarkLigPos::read(data)? {
285 MarkLigPos::Format1(t) => {
286 self.finish(t.mark_coverage(), gpos::MarkLigPos1::new(&t))
287 }
288 MarkLigPos::Format2(t) => {
289 self.finish(t.mark_coverage(), gpos::MarkLigPos1::new_wide(&t))
290 }
291 },
292 (false, 6) => match MarkMarkPos::read(data)? {
293 MarkMarkPos::Format1(t) => {
294 self.finish(t.mark1_coverage(), gpos::MarkMarkPos1::new(&t))
295 }
296 MarkMarkPos::Format2(t) => {
297 self.finish(t.mark1_coverage(), gpos::MarkMarkPos1::new_wide(&t))
298 }
299 },
300 (true, 5) | (false, 7) => match SequenceContext::read(data)? {
301 SequenceContext::Format1(t) => {
302 self.finish(t.coverage(), context::ChainContext1::from_plain(&t))
303 }
304 SequenceContext::Format2(t) => self.finish(
305 t.coverage(),
306 Some(context::ChainContext2::from_plain(&t, caches, budget)?),
307 ),
308 SequenceContext::Format3(t) => self.finish(
309 t.coverages().get(0),
310 Some(context::ChainContext3::from_plain(&t, budget)?),
311 ),
312 SequenceContext::Format4(t) => {
313 self.finish(t.coverage(), context::ChainContext1::from_plain_wide(&t))
314 }
315 SequenceContext::Format5(t) => self.finish(
316 t.coverage(),
317 Some(context::ChainContext2::from_plain_wide(&t, caches, budget)?),
318 ),
319 SequenceContext::Format6(t) => self.finish(
320 t.coverages().get(0),
321 Some(context::ChainContext3::from_plain_wide(&t, budget)?),
322 ),
323 },
324 (true, 6) | (false, 8) => match ChainedSequenceContext::read(data)? {
325 ChainedSequenceContext::Format1(t) => {
326 self.finish(t.coverage(), context::ChainContext1::new(&t))
327 }
328 ChainedSequenceContext::Format2(t) => self.finish(
329 t.coverage(),
330 Some(context::ChainContext2::new(&t, caches, budget)?),
331 ),
332 ChainedSequenceContext::Format3(t) => self.finish(
333 t.input_coverages().get(0),
334 Some(context::ChainContext3::new(&t, budget)?),
335 ),
336 ChainedSequenceContext::Format4(t) => {
337 self.finish(t.coverage(), context::ChainContext1::new_wide(&t))
338 }
339 ChainedSequenceContext::Format5(t) => self.finish(
340 t.coverage(),
341 Some(context::ChainContext2::new_wide(&t, caches, budget)?),
342 ),
343 },
344 (true, 7) | (false, 9) => {
345 let ext = ExtensionSubstFormat1::<()>::read(data)?;
346 let ext_type = ext.extension_lookup_type();
347 if is_extension(self.is_subst, ext_type) {
348 return Err(BuildError::Invalid);
349 }
350 let offset = self
351 .offset
352 .checked_add(ext.extension_offset().to_u32() as usize)
353 .ok_or(BuildError::Invalid)?;
354 Source { offset, ..self }.build(ext_type)
355 }
356 _ => Err(BuildError::Invalid),
357 }
358 }
359
360 fn class_pairs(
362 self,
363 coverage: Result<CoverageTable<'a>, ReadError>,
364 pairs: gpos::ClassPairs<'a>,
365 ) -> Result<BuiltSubtable<'a>, BuildError> {
366 let (caches, budget) = (self.with_caches, self.budget);
367 match gpos::PairKern2::new(&pairs, caches, budget)? {
368 Some(kern) => self.finish(coverage, Some(kern)),
369 None => self.finish(coverage, gpos::PairPos2::new(&pairs, caches, budget)?),
370 }
371 }
372
373 fn finish<T: IntoKind<'a> + SubtableDigests<'a>>(
375 self,
376 coverage: Result<CoverageTable<'a>, ReadError>,
377 data: Option<T>,
378 ) -> Result<BuiltSubtable<'a>, BuildError> {
379 let coverage = Coverage::required(coverage).ok_or(BuildError::Invalid)?;
380 let data = data.ok_or(BuildError::Invalid)?;
381 let digest_second = data.digest_second(self.budget)?;
382 let cache_cost = data.cache_cost();
383 let coverage_cache = if self.with_caches
384 && T::CACHES_COVERAGE
385 && coverage.cost() >= MIN_CACHED_COVERAGE_COST
386 {
387 self.budget.alloc::<MappingCache>(1)?;
388 Some(Box::new(MappingCache::new()))
389 } else {
390 None
391 };
392 Ok(BuiltSubtable {
393 subtable: CachedSubtable {
394 kind: data.into_kind(self.budget)?,
395 digest: coverage.digest(self.budget)?,
396 coverage,
397 coverage_cache,
398 fns: T::FNS,
399 apply_sharing: T::FNS.apply_sharing,
400 },
401 shares_second_glyph: T::FNS.shares_second_glyph,
402 digest_second,
403 cache_cost,
404 })
405 }
406}
407
408#[cfg(test)]
409mod tests {
410 use super::*;
411
412 fn repeated_single_subst(count: u16) -> Vec<u8> {
413 let offset = 6 + count * 2;
414 let mut words = alloc::vec![1, 0, count];
415 words.resize(3 + usize::from(count), offset);
416 words.extend_from_slice(&[1, 6, 1, 1, 1, 42]);
418 words.into_iter().flat_map(u16::to_be_bytes).collect()
419 }
420
421 #[test]
422 fn exhaustion_discards_previously_built_subtables() {
423 let data = repeated_single_subst(2);
424 let budget = Budget::new(5, 1 << 20);
427 assert!(matches!(
428 build_lookup_at(FontData::new(&data), 0, true, &budget),
429 Err(BuildError::Exhausted)
430 ));
431 let budget = Budget::new(7, 1 << 20);
432 let lookup = build_lookup_at(FontData::new(&data), 0, true, &budget).unwrap();
433 assert_eq!(lookup.subtables.len(), 2);
434 }
435
436 #[test]
437 fn subtable_storage_is_reserved_before_building() {
438 let data = repeated_single_subst(2);
439 let budget = Budget::new(100, size_of::<CachedSubtable>() * 2 - 1);
440 assert!(matches!(
441 build_lookup_at(FontData::new(&data), 0, true, &budget),
442 Err(BuildError::Exhausted)
443 ));
444 assert_eq!(budget.remaining().0, 97);
445 }
446
447 #[test]
448 fn thousands_of_subtables_are_allowed() {
449 let data = repeated_single_subst(3800);
452 let budget = Budget::new(1 << 20, 16 << 20);
453 let lookup = build_lookup_at(FontData::new(&data), 0, true, &budget).unwrap();
454 assert_eq!(lookup.subtables.len(), 3800);
455 }
456
457 #[test]
458 fn malformed_subtables_do_not_abort_a_lookup() {
459 let mut data = repeated_single_subst(2);
460 data[6..8].copy_from_slice(&u16::MAX.to_be_bytes());
462 let budget = Budget::for_table_bytes(data.len());
463 let lookup = build_lookup_at(FontData::new(&data), 0, true, &budget).unwrap();
464 assert_eq!(lookup.subtables.len(), 1);
465 }
466
467 fn lookup_with_recursive_extension(lookup_type: u16) -> [u8; 16] {
468 let mut data = [0; 16];
469 data[0..2].copy_from_slice(&lookup_type.to_be_bytes());
471 data[4..6].copy_from_slice(&1u16.to_be_bytes());
472 data[6..8].copy_from_slice(&8u16.to_be_bytes());
473 data[8..10].copy_from_slice(&1u16.to_be_bytes());
475 data[10..12].copy_from_slice(&lookup_type.to_be_bytes());
476 data
477 }
478
479 #[test]
480 fn gsub_extension_lookup_cannot_target_extension_lookup() {
481 let data = lookup_with_recursive_extension(7);
482 let lookup = build_lookup_at(
483 FontData::new(&data),
484 0,
485 true,
486 &Budget::for_table_bytes(data.len()),
487 )
488 .unwrap();
489 assert!(lookup.subtables.is_empty());
490 }
491
492 #[test]
493 fn gpos_extension_lookup_cannot_target_extension_lookup() {
494 let data = lookup_with_recursive_extension(9);
495 let lookup = build_lookup_at(
496 FontData::new(&data),
497 0,
498 false,
499 &Budget::for_table_bytes(data.len()),
500 )
501 .unwrap();
502 assert!(lookup.subtables.is_empty());
503 }
504}