1
#![deny(missing_docs)]
2

            
3
//! `kern` table parsing.
4
//!
5
//! <https://learn.microsoft.com/en-us/typography/opentype/spec/kern>
6

            
7
use tinyvec::TinyVec;
8

            
9
use crate::{
10
    binary::{
11
        read::{ReadArray, ReadBinary, ReadBinaryDep, ReadCtxt, ReadFrom, ReadScope},
12
        I16Be, U16Be, U8,
13
    },
14
    context::Glyph,
15
    error::ParseError,
16
    glyph_position::TextDirection,
17
    gpos::{Info, Placement},
18
    scripts::horizontal_text_direction,
19
};
20

            
21
use super::aat::{
22
    VecTable, CLASS_CODE_DELETED, CLASS_CODE_EOT, CLASS_CODE_OOB, DELETED_GLYPH, MAX_OPS,
23
};
24

            
25
/// `kern` Kerning Table.
26
#[derive(Clone, Copy)]
27
pub struct KernTable<'a> {
28
    version: KernTableVersion,
29
    /// Number of subtables in the kerning table.
30
    table_count: u32,
31
    data: &'a [u8],
32
}
33

            
34
#[derive(Clone, Copy)]
35
enum KernTableVersion {
36
    /// Version of the kerning table, as defined in OpenType.
37
    KernTableVersion0,
38
    /// Version of the kerning table, as defined in Apple Advanced Typography.
39
    /// Contains extensions that are not supported in OpenType.
40
    KernTableVersion1,
41
}
42

            
43
/// Kerning data.
44
enum KernData<'a> {
45
    /// Format 0 kerning data (pairs).
46
    Format0(KernFormat0<'a>),
47
    /// Format 1 kerning data (state table).
48
    Format1(KernFormat1<'a>),
49
    /// Format 2 kerning data (2D array).
50
    Format2(KernFormat2<'a>),
51
    /// Format 3 kerning data (2D array).
52
    Format3(KernFormat3<'a>),
53
}
54

            
55
/// Format 0 kerning data (pairs).
56
struct KernFormat0<'a> {
57
    /// Array of KernPair records.
58
    kern_pairs: ReadArray<'a, KernPair>, // [nPairs]: KernPair,
59
}
60

            
61
/// Format 1 kerning data (state table).
62
struct KernFormat1<'a> {
63
    class_table: ClassTableFormat1<'a>,
64
    state_array: StateArray<'a>,
65
    entry_table: VecTable<ContextualEntry>,
66
    value_table: ValueTable<'a>,
67
}
68

            
69
struct StateArray<'a> {
70
    state_size: u16,
71
    offset: u16,
72
    states: Vec<ReadArray<'a, U8>>,
73
}
74

            
75
/// Format 2 kerning data (2D array).
76
struct KernFormat2<'a> {
77
    left_table: ClassTableFormat2<'a>,
78
    right_table: ClassTableFormat2<'a>,
79
    kerning_array: &'a [u8], // ReadArray<'a, I16Be>,
80
}
81

            
82
/// Format 3 kerning data (2D array).
83
struct KernFormat3<'a> {
84
    kern_value_table: ReadArray<'a, I16Be>,
85
    left_class_table: ReadArray<'a, U8>,
86
    right_class_table: ReadArray<'a, U8>,
87
    right_class_count: usize,
88
    kern_index_table: ReadArray<'a, U8>,
89
}
90

            
91
/// Kerning value for glyph pair.
92
struct KernPair {
93
    /// The glyph index for the left-hand glyph in the kerning pair.
94
    left: u16,
95
    /// The glyph index for the right-hand glyph in the kerning pair.
96
    right: u16,
97
    /// The kerning value for the above pair, in font design units. If this value is greater than
98
    /// zero, the characters will be moved apart. If this value is less than zero, the character
99
    /// will be moved closer together.
100
    value: i16,
101
}
102

            
103
/// Format 1 glyph class table.
104
struct ClassTableFormat1<'a> {
105
    /// Glyph index of the first glyph in the class table.
106
    first_glyph: u16,
107
    /// The class codes (indexed by glyph index minus first_glyph).
108
    class_array: ReadArray<'a, U8>,
109
}
110

            
111
/// Format 2 glyph class table.
112
struct ClassTableFormat2<'a> {
113
    /// First glyph in class range.
114
    first_glyph: u16,
115
    values: ReadArray<'a, U16Be>,
116
}
117

            
118
/// Sub-table within `kern` table.
119
struct KernSubtable<'a> {
120
    coverage: KernCoverage,
121
    data: KernData<'a>,
122
}
123

            
124
enum KernCoverage {
125
    KernCoverageVersion0(u16),
126
    KernCoverageVersion1(u16),
127
}
128

            
129
impl ReadBinary for KernTable<'_> {
130
    type HostType<'a> = KernTable<'a>;
131

            
132
14688
    fn read<'a>(ctxt: &mut ReadCtxt<'a>) -> Result<Self::HostType<'a>, ParseError> {
133
14688
        let version = match ctxt.read_u16be()? {
134
14688
            0 => KernTableVersion::KernTableVersion0,
135
            1 => {
136
                let _padding = ctxt.read_u16be()?;
137
                KernTableVersion::KernTableVersion1
138
            }
139
            _ => return Err(ParseError::BadVersion),
140
        };
141
14688
        let table_count = match version {
142
14688
            KernTableVersion::KernTableVersion0 => u32::from(ctxt.read_u16be()?),
143
            KernTableVersion::KernTableVersion1 => ctxt.read_u32be()?,
144
        };
145
14688
        let data = ctxt.scope().data();
146
14688
        let kern = KernTable {
147
14688
            version,
148
14688
            table_count,
149
14688
            data,
150
14688
        };
151

            
152
        // Validate the sub-tables can be read.
153
        // Note that the sub-table `length` field can't be trusted as the very widely used
154
        // OpenSans font has an invalid value for this field. Avoid its use where possible.
155
        // https://github.com/fonttools/fonttools/issues/314#issuecomment-118116527
156
14688
        kern.sub_tables().try_for_each(|table| table.map(drop))?;
157

            
158
14688
        Ok(kern)
159
14688
    }
160
}
161

            
162
impl<'a> KernTable<'a> {
163
    /// Iterate over the sub-tables of this `kern` table.
164
23004
    fn sub_tables(&self) -> impl Iterator<Item = Result<KernSubtable<'a>, ParseError>> + 'a {
165
23004
        let mut ctxt = ReadScope::new(self.data).ctxt();
166
23004
        let version = self.version;
167

            
168
23004
        (0..self.table_count).map(move |_| {
169
23004
            let start = ctxt.scope();
170
23004
            match version {
171
                KernTableVersion::KernTableVersion0 => {
172
23004
                    let _version = ctxt.read_u16be()?;
173
23004
                    let length = usize::from(ctxt.read_u16be()?);
174
23004
                    let coverage = ctxt.read_u16be()?;
175
23004
                    let format = coverage >> 8;
176
23004
                    let data = match format {
177
23004
                        0 => Self::read_format0(&mut ctxt).map(KernData::Format0)?,
178
                        2 => Self::read_format2(&mut ctxt, start, length).map(KernData::Format2)?,
179
                        _ => return Err(ParseError::BadValue),
180
                    };
181

            
182
23004
                    Ok(KernSubtable {
183
23004
                        coverage: KernCoverage::KernCoverageVersion0(coverage),
184
23004
                        data,
185
23004
                    })
186
                }
187
                KernTableVersion::KernTableVersion1 => {
188
                    let length = usize::try_from(ctxt.read_u32be()?)?;
189
                    let coverage = ctxt.read_u16be()?;
190
                    let _tuple_index = ctxt.read_u16be()?;
191
                    let format = coverage & 0x00FF;
192
                    let data = match format {
193
                        0 => Self::read_format0(&mut ctxt).map(KernData::Format0)?,
194
                        1 => Self::read_format1(&mut ctxt, length).map(KernData::Format1)?,
195
                        2 => Self::read_format2(&mut ctxt, start, length).map(KernData::Format2)?,
196
                        3 => Self::read_format3(&mut ctxt, length).map(KernData::Format3)?,
197
                        _ => return Err(ParseError::BadValue),
198
                    };
199

            
200
                    Ok(KernSubtable {
201
                        coverage: KernCoverage::KernCoverageVersion1(coverage),
202
                        data,
203
                    })
204
                }
205
            }
206
23004
        })
207
23004
    }
208

            
209
    // Format 0 is the only sub-table format supported by Windows.
210
23004
    fn read_format0(ctxt: &mut ReadCtxt<'a>) -> Result<KernFormat0<'a>, ParseError> {
211
23004
        let n_pairs = ctxt.read_u16be()?;
212
23004
        let _search_range = ctxt.read_u16be()?;
213
23004
        let _entry_selector = ctxt.read_u16be()?;
214
23004
        let _range_shift = ctxt.read_u16be()?;
215
23004
        let kern_pairs = ctxt.read_array(usize::from(n_pairs))?; // [nPairs]: KernPair,
216

            
217
23004
        Ok(KernFormat0 { kern_pairs })
218
23004
    }
219

            
220
    fn read_format1(ctxt: &mut ReadCtxt<'a>, length: usize) -> Result<KernFormat1<'a>, ParseError> {
221
        // Per the spec, state table offsets are from the beginning of the state table, and _not_
222
        // from the beginning of the subtable (like in format 2).
223
        let sub_body_length = length.checked_sub(8).ok_or(ParseError::BadEof)?;
224
        let mut sub_ctxt = ctxt.read_scope(sub_body_length)?.ctxt();
225
        let start = sub_ctxt.scope();
226

            
227
        // StateHeader
228
        let state_size = sub_ctxt.read_u16be()?;
229
        let class_table_offset = sub_ctxt.read_u16be()?;
230
        let state_array_offset = sub_ctxt.read_u16be()?;
231
        let entry_table_offset = sub_ctxt.read_u16be()?;
232

            
233
        let value_table_offset = sub_ctxt.read_u16be()?;
234

            
235
        let class_table = start
236
            .offset(usize::from(class_table_offset))
237
            .read::<ClassTableFormat1<'_>>()?;
238

            
239
        // The _non-extended_ AAT state tables seem to differ from their extended counterpart,
240
        // in that the `new_state` value in the entry table is not a state number (like in `morx`),
241
        // but an offset from the beginning of the state table to the new state.
242
        //
243
        // We handle this by storing the `state_size` and `state_array_offset`, then using it to
244
        // compute the state number. It is probably easier to just store the state array as a
245
        // 1-dimensional array, but this approach is consistent with `morx` and makes it simpler to
246
        // generalise the state table methods (future work).
247
        let state_array = start
248
            .offset(usize::from(state_array_offset))
249
            .read_dep::<StateArray<'_>>((state_size, state_array_offset))?;
250

            
251
        let entry_table = start
252
            .offset(usize::from(entry_table_offset))
253
            .read::<VecTable<ContextualEntry>>()?;
254

            
255
        // Likewise, the `value_offset` value in the entry table is an offset from the beginning
256
        // of the state table.
257
        let value_table = ValueTable {
258
            offset: value_table_offset,
259
            values: start.offset(usize::from(value_table_offset)).data(),
260
        };
261

            
262
        Ok(KernFormat1 {
263
            class_table,
264
            state_array,
265
            entry_table,
266
            value_table,
267
        })
268
    }
269

            
270
    fn read_format2(
271
        ctxt: &mut ReadCtxt<'a>,
272
        start: ReadScope<'a>,
273
        length: usize,
274
    ) -> Result<KernFormat2<'a>, ParseError> {
275
        let _row_width = ctxt.read_u16be()?;
276
        let left_class_offset = ctxt.read_u16be()?;
277
        let right_class_offset = ctxt.read_u16be()?;
278
        let kerning_array_offset = usize::from(ctxt.read_u16be()?);
279

            
280
        let left_table = start
281
            .offset(usize::from(left_class_offset))
282
            .read::<ClassTableFormat2<'_>>()?;
283
        let right_table = start
284
            .offset(usize::from(right_class_offset))
285
            .read::<ClassTableFormat2<'_>>()?;
286
        // The kerning array is a 2-dimensional array of kerning values, with each row in the array
287
        // representing one left-hand glyph class, and each column representing one right-hand glyph
288
        // class.
289
        //
290
        // In order to compute the size of the kerning array without the (possibly unreliable)
291
        // subtable `length` field, we need to multiply the number of left-hand classes by the
292
        // number of right-hand classes. The `row_width` field presumably gives us the number of
293
        // right-hand classes, but there isn't a way to obtain the number of left-hand classes
294
        // without scanning the left-hand class table for the largest class number.
295
        //
296
        // As such, use the subtable `length` field. There appear to be _very_ few fonts in the
297
        // wild that use format 2 any way.
298
        let kerning_array_length = length
299
            .checked_sub(kerning_array_offset)
300
            .ok_or(ParseError::BadEof)?;
301
        let kerning_array = start
302
            .offset(kerning_array_offset)
303
            .ctxt()
304
            .read_slice(kerning_array_length)?;
305

            
306
        Ok(KernFormat2 {
307
            left_table,
308
            right_table,
309
            kerning_array,
310
        })
311
    }
312

            
313
    fn read_format3(ctxt: &mut ReadCtxt<'a>, length: usize) -> Result<KernFormat3<'a>, ParseError> {
314
        // Assume that `length` can be trusted. Subtable format 3 is specific to `kern` version 1;
315
        // unlike version 0, it stores its subtable length as a uint32. As such, the issues that
316
        // affect version 0 (see comment on OpenSans above) shouldn't occur.
317
        //
318
        // Use `length` to establish a sub-context from which the format 3 sub-subtables are read.
319
        // This is to guard against a situation where `length` > sum_length_of_subsubtables, which
320
        // occurs in Apple's Skia font and causes a mis-read of subsequent sub-tables.
321
        let sub_body_length = length.checked_sub(8).ok_or(ParseError::BadEof)?;
322
        let mut sub_ctxt = ctxt.read_scope(sub_body_length)?.ctxt();
323

            
324
        let glyph_count = usize::from(sub_ctxt.read_u16be()?);
325
        let kern_value_count = usize::from(sub_ctxt.read_u8()?);
326
        let left_class_count = usize::from(sub_ctxt.read_u8()?);
327
        let right_class_count = usize::from(sub_ctxt.read_u8()?);
328
        let _flags = sub_ctxt.read_u8()?;
329

            
330
        let kern_value_table = sub_ctxt.read_array(kern_value_count)?;
331
        let left_class_table = sub_ctxt.read_array(glyph_count)?;
332
        let right_class_table = sub_ctxt.read_array(glyph_count)?;
333
        let kern_index_table = sub_ctxt.read_array(left_class_count * right_class_count)?;
334

            
335
        Ok(KernFormat3 {
336
            kern_value_table,
337
            left_class_table,
338
            right_class_table,
339
            right_class_count,
340
            kern_index_table,
341
        })
342
    }
343

            
344
    /// Create an owned version of this `kern` table.
345
14688
    pub fn to_owned(&self) -> owned::KernTable {
346
14688
        owned::KernTable {
347
14688
            version: self.version,
348
14688
            table_count: self.table_count,
349
14688
            data: Box::from(self.data),
350
14688
        }
351
14688
    }
352
}
353

            
354
impl<'a> From<&'a owned::KernTable> for KernTable<'a> {
355
    fn from(kern: &'a owned::KernTable) -> Self {
356
        KernTable {
357
            version: kern.version,
358
            table_count: kern.table_count,
359
            data: &kern.data,
360
        }
361
    }
362
}
363

            
364
impl KernSubtable<'_> {
365
    /// True if table has horizontal data, false if vertical.
366
8316
    fn is_horizontal(&self) -> bool {
367
8316
        match self.coverage {
368
8316
            KernCoverage::KernCoverageVersion0(c) => c & 1 != 0,
369
            KernCoverage::KernCoverageVersion1(c) => c & 0x8000 == 0,
370
        }
371
8316
    }
372

            
373
    /// If true the table has minimum values, otherwise the table has kerning values.
374
108
    fn is_minimum(&self) -> bool {
375
108
        match self.coverage {
376
108
            KernCoverage::KernCoverageVersion0(c) => c & (1 << 1) != 0,
377
            KernCoverage::KernCoverageVersion1(_) => false,
378
        }
379
108
    }
380

            
381
    /// Is kerning is perpendicular to the flow of the text.
382
16632
    fn is_cross_stream(&self) -> bool {
383
16632
        match self.coverage {
384
16632
            KernCoverage::KernCoverageVersion0(c) => c & (1 << 2) != 0,
385
            KernCoverage::KernCoverageVersion1(c) => c & 0x4000 != 0,
386
        }
387
16632
    }
388

            
389
    /// True if the value in this table should replace the value currently being accumulated.
390
108
    fn is_override(&self) -> bool {
391
108
        match self.coverage {
392
108
            KernCoverage::KernCoverageVersion0(c) => c & (1 << 3) != 0,
393
            KernCoverage::KernCoverageVersion1(_) => false,
394
        }
395
108
    }
396

            
397
    /// True if table has variation kerning values.
398
    #[allow(unused)]
399
    fn has_variation(&self) -> bool {
400
        match self.coverage {
401
            KernCoverage::KernCoverageVersion0(_) => false,
402
            KernCoverage::KernCoverageVersion1(c) => c & 0x2000 != 0,
403
        }
404
    }
405
}
406

            
407
impl KernPair {
408
65124
    fn search_key(&self) -> u32 {
409
65124
        (u32::from(self.left) << 16) | u32::from(self.right)
410
65124
    }
411
}
412

            
413
impl ReadFrom for KernPair {
414
    type ReadType = (U16Be, U16Be, I16Be);
415

            
416
65232
    fn read_from((left, right, value): (u16, u16, i16)) -> Self {
417
65232
        KernPair { left, right, value }
418
65232
    }
419
}
420

            
421
impl ReadBinaryDep for StateArray<'_> {
422
    type Args<'a> = (u16, u16);
423
    type HostType<'a> = StateArray<'a>;
424

            
425
    fn read_dep<'a>(
426
        ctxt: &mut ReadCtxt<'a>,
427
        (state_size, offset): (u16, u16),
428
    ) -> Result<Self::HostType<'a>, ParseError> {
429
        let mut state_array: Vec<ReadArray<'a, U8>> = Vec::new();
430

            
431
        loop {
432
            match ctxt.read_array::<U8>(usize::from(state_size)) {
433
                Ok(array) => state_array.push(array),
434
                Err(ParseError::BadEof) => break,
435
                Err(err) => return Err(err),
436
            }
437
        }
438

            
439
        Ok(StateArray {
440
            state_size,
441
            offset,
442
            states: state_array,
443
        })
444
    }
445
}
446

            
447
impl ReadBinary for ClassTableFormat1<'_> {
448
    type HostType<'a> = ClassTableFormat1<'a>;
449

            
450
    fn read<'a>(ctxt: &mut ReadCtxt<'a>) -> Result<Self::HostType<'a>, ParseError> {
451
        let first_glyph = ctxt.read_u16be()?;
452
        let n_glyphs = ctxt.read_u16be()?;
453
        let class_array = ctxt.read_array(usize::from(n_glyphs))?;
454

            
455
        Ok(ClassTableFormat1 {
456
            first_glyph,
457
            class_array,
458
        })
459
    }
460
}
461

            
462
impl ReadBinary for ClassTableFormat2<'_> {
463
    type HostType<'a> = ClassTableFormat2<'a>;
464

            
465
    fn read<'a>(ctxt: &mut ReadCtxt<'a>) -> Result<Self::HostType<'a>, ParseError> {
466
        let first_glyph = ctxt.read_u16be()?;
467
        let n_glyphs = ctxt.read_u16be()?;
468
        let values = ctxt.read_array(usize::from(n_glyphs))?;
469

            
470
        Ok(ClassTableFormat2 {
471
            first_glyph,
472
            values,
473
        })
474
    }
475
}
476

            
477
struct ContextualEntry {
478
    new_state: u16,
479
    flags: u16,
480
}
481

            
482
impl ContextualEntry {
483
    /// Push: if set, push this glyph on the kerning stack.
484
    fn push(&self) -> bool {
485
        self.flags & 0x8000 != 0
486
    }
487

            
488
    /// If set, don't advance to the next glyph before going to the new state.
489
    fn dont_advance(&self) -> bool {
490
        self.flags & 0x4000 != 0
491
    }
492

            
493
    /// ValueOffset: byte offset from the beginning of the subtable to the value table for the
494
    /// glyphs on the kerning stack.
495
    fn value_offset(&self) -> u16 {
496
        self.flags & 0x3FFF
497
    }
498
}
499

            
500
impl ReadFrom for ContextualEntry {
501
    type ReadType = (U16Be, U16Be);
502

            
503
    fn read_from((new_state, flags): (u16, u16)) -> Self {
504
        ContextualEntry { new_state, flags }
505
    }
506
}
507

            
508
struct ValueTable<'a> {
509
    offset: u16,
510
    values: &'a [u8],
511
}
512

            
513
struct ContextualContext<'a> {
514
    max_ops: isize,
515
    infos: &'a mut [Info],
516
    new_state: u16,
517
    stack: TinyVec<[usize; 8]>,
518
}
519

            
520
impl<'a> ContextualContext<'a> {
521
    fn new(infos: &'a mut [Info], new_state: u16) -> ContextualContext<'a> {
522
        ContextualContext {
523
            max_ops: MAX_OPS,
524
            infos,
525
            new_state,
526
            stack: TinyVec::new(),
527
        }
528
    }
529

            
530
    fn process(
531
        &mut self,
532
        is_cross_stream: bool,
533
        subtable: &KernFormat1<'_>,
534
    ) -> Result<(), ParseError> {
535
        let mut i = 0;
536
        while i <= self.infos.len() {
537
            let class = match self.infos.get(i) {
538
                Some(info) => {
539
                    let glyph_id = info.get_glyph_index();
540
                    if glyph_id == DELETED_GLYPH {
541
                        CLASS_CODE_DELETED
542
                    } else {
543
                        subtable
544
                            .class_table
545
                            .get(glyph_id)
546
                            .map(u16::from)
547
                            .unwrap_or(CLASS_CODE_OOB)
548
                    }
549
                }
550
                None => CLASS_CODE_EOT,
551
            };
552

            
553
            let entry_table_index = subtable
554
                .state_array
555
                .get(class, self.new_state)
556
                .ok_or(ParseError::BadIndex)?;
557

            
558
            let entry = subtable
559
                .entry_table
560
                .0
561
                .get(usize::from(entry_table_index))
562
                .ok_or(ParseError::BadIndex)?;
563

            
564
            self.new_state = entry.new_state;
565

            
566
            if entry.push() {
567
                if class == CLASS_CODE_EOT {
568
                    // `i` points to one past the buffer, so don't push it.
569
                } else if self.stack.last() == Some(&i) {
570
                    // When DONT_ADVANCE == true, avoid pushing the same index twice.
571
                } else {
572
                    self.stack.push(i)
573
                }
574
            }
575

            
576
            let mut value_offset = entry.value_offset();
577
            if value_offset != 0 {
578
                'stack: loop {
579
                    let value = subtable
580
                        .value_table
581
                        .get(value_offset)
582
                        .ok_or(ParseError::BadIndex)?;
583

            
584
                    let popped_i = match self.stack.pop() {
585
                        Some(popped_i) => popped_i,
586
                        None => break 'stack, // Stack underflow.
587
                    };
588

            
589
                    let info = &mut self.infos[popped_i];
590
                    let kerning = value.kerning();
591
                    if is_cross_stream {
592
                        // Not in the spec but in the example at the bottom of the page.
593
                        // Seems to be a special flag that resets cross-stream kerning.
594
                        if kerning == -0x8000 {
595
                            info.reset_cross_stream = true;
596
                            info.placement = match info.placement {
597
                                Placement::Distance(dx, _dy) => Placement::Distance(dx, 0),
598
                                _ => Placement::None,
599
                            }
600
                        } else if !info.reset_cross_stream {
601
                            info.placement.combine_distance(0, i32::from(kerning));
602
                        }
603
                    } else {
604
                        info.kerning += kerning;
605
                        info.placement.combine_distance(i32::from(kerning), 0);
606
                    }
607

            
608
                    if value.end_of_list() {
609
                        break 'stack;
610
                    }
611

            
612
                    value_offset = value_offset
613
                        .checked_add(u16::try_from(size_of::<i16>())?)
614
                        .ok_or(ParseError::BadIndex)?;
615
                }
616
            }
617

            
618
            if class == CLASS_CODE_EOT {
619
                break;
620
            }
621

            
622
            self.max_ops -= 1;
623
            if !entry.dont_advance() || self.max_ops <= 0 {
624
                i += 1;
625
            }
626
        }
627

            
628
        Ok(())
629
    }
630
}
631

            
632
impl KernData<'_> {
633
    /// Lookup the kerning for a pair of glyphs. Not applicable to format 1.
634
35964
    fn lookup(&self, left: u16, right: u16) -> Option<i16> {
635
35964
        match self {
636
35964
            KernData::Format0(x) => {
637
                // The KernPair records must be ordered by combining the left and right values to
638
                // form an unsigned 32-bit integer (left as the high-order word), then ordering
639
                // records numerically using these combined values.
640
35964
                let needle = (u32::from(left) << 16) | u32::from(right);
641
35964
                x.kern_pairs
642
65124
                    .binary_search_by(|pair| pair.search_key().cmp(&needle))
643
35964
                    .ok()
644
35964
                    .and_then(|index| x.kern_pairs.get_item(index))
645
35964
                    .map(|pair| pair.value)
646
            }
647
            KernData::Format1(_) => None,
648
            KernData::Format2(x) => {
649
                // Get the class of the left/right glyphs, then lookup the kerning value
650
                let left_class = x.left_table.get(left)?;
651
                let right_class = x.right_table.get(right)?;
652

            
653
                // The values in the right class table are stored pre-multiplied by the number of
654
                // bytes in a single kerning value, and the values in the left class table are
655
                // stored pre-multiplied by the number of bytes in one row. This eliminates a need
656
                // to multiply the row and column values together to determine the location of the
657
                // kerning value.
658
                ReadScope::new(x.kerning_array)
659
                    .offset(usize::from(left_class) + usize::from(right_class))
660
                    .read::<I16Be>()
661
                    .ok()
662
            }
663
            KernData::Format3(x) => {
664
                // Suppose you have two glyphs, L and R, and you wish to determine the kerning
665
                // value. You can do so using this pseudo-expression:
666
                // value = kernValue[kernIndex[leftClass[L] * rightClassCount + rightClass[R]]].
667
                let left_class = x.left_class_table.get_item(usize::from(left))?;
668
                let right_class = x.right_class_table.get_item(usize::from(right))?;
669
                let kern_index = x.kern_index_table.get_item(
670
                    usize::from(left_class) * x.right_class_count + usize::from(right_class),
671
                )?;
672
                x.kern_value_table.get_item(usize::from(kern_index))
673
            }
674
        }
675
35964
    }
676

            
677
    /// Apply state-table-based kerning to an entire glyph buffer. Only applicable to format 1.
678
    fn apply_format_1(&self, is_cross_stream: bool, infos: &mut [Info]) -> Result<(), ParseError> {
679
        match self {
680
            KernData::Format1(x) => {
681
                let mut context = ContextualContext::new(infos, x.state_array.offset);
682
                context.process(is_cross_stream, x)
683
            }
684
            _ => Ok(()),
685
        }
686
    }
687

            
688
    /// Indicates a format 1 subtable.
689
8316
    fn is_format_1(&self) -> bool {
690
8316
        matches!(self, KernData::Format1(_))
691
8316
    }
692
}
693

            
694
/// Apply kerning to an array of positioned glyphs.
695
8316
pub fn apply(
696
8316
    kern: &KernTable<'_>,
697
8316
    script_tag: u32,
698
8316
    infos: &mut [Info],
699
8316
) -> Result<bool, ParseError> {
700
8316
    let mut has_cross_stream = false;
701

            
702
8316
    if infos.is_empty() {
703
        return Ok(has_cross_stream);
704
8316
    }
705

            
706
8316
    let reverse_infos = horizontal_text_direction(script_tag) == TextDirection::RightToLeft;
707
8316
    if reverse_infos {
708
1026
        infos.reverse();
709
7290
    }
710

            
711
8316
    for sub_table in kern.sub_tables() {
712
8316
        let sub_table = sub_table?;
713
8316
        apply_sub_table(&sub_table, infos)?;
714
8316
        has_cross_stream |= sub_table.is_cross_stream();
715
    }
716

            
717
8316
    if has_cross_stream {
718
        accumulate_cross_stream_offsets(infos);
719
8316
    }
720

            
721
8316
    if reverse_infos {
722
1026
        infos.reverse();
723
7290
    }
724

            
725
8316
    Ok(has_cross_stream)
726
8316
}
727

            
728
8316
fn apply_sub_table(sub_table: &KernSubtable<'_>, infos: &mut [Info]) -> Result<(), ParseError> {
729
8316
    let kern_data = &sub_table.data;
730
8316
    if kern_data.is_format_1() {
731
        if !sub_table.is_horizontal() {
732
            // TODO: Support vertical kerning.
733
            return Ok(());
734
        }
735

            
736
        kern_data.apply_format_1(sub_table.is_cross_stream(), infos)
737
    } else {
738
8316
        if !sub_table.is_horizontal() || sub_table.is_cross_stream() {
739
            // TODO: Support vertical kerning; cross-stream kerning.
740
            return Ok(());
741
8316
        }
742

            
743
8316
        let mut iter = infos.iter_mut();
744
8316
        let Some(mut left) = iter.next() else {
745
            return Ok(());
746
        };
747

            
748
44280
        for right in iter {
749
35964
            if let Some(value) = kern_data.lookup(left.get_glyph_index(), right.get_glyph_index()) {
750
108
                left.kerning = if sub_table.is_override() {
751
                    value
752
108
                } else if sub_table.is_minimum() {
753
                    left.kerning.min(value)
754
                } else {
755
108
                    left.kerning + value
756
                }
757
35856
            }
758
35964
            left = right;
759
        }
760

            
761
8316
        Ok(())
762
    }
763
8316
}
764

            
765
fn accumulate_cross_stream_offsets(infos: &mut [Info]) {
766
    let mut iter = infos.iter_mut();
767
    let Some(mut left) = iter.next() else {
768
        return;
769
    };
770

            
771
    for right in iter {
772
        if let Placement::Distance(_dx, dy) = left.placement {
773
            if !right.reset_cross_stream {
774
                right.placement.combine_distance(0, dy);
775
            }
776
        }
777
        left = right;
778
    }
779
}
780

            
781
impl ClassTableFormat1<'_> {
782
    fn get(&self, glyph_id: u16) -> Option<u8> {
783
        let index = glyph_id.checked_sub(self.first_glyph).map(usize::from)?;
784
        self.class_array.get_item(index)
785
    }
786
}
787

            
788
impl ClassTableFormat2<'_> {
789
    fn get(&self, glyph_id: u16) -> Option<u16> {
790
        let index = glyph_id.checked_sub(self.first_glyph).map(usize::from)?;
791
        self.values.get_item(index)
792
    }
793
}
794

            
795
impl StateArray<'_> {
796
    fn get(&self, class: u16, new_state: u16) -> Option<u8> {
797
        let row_index = new_state.checked_sub(self.offset)? / self.state_size;
798

            
799
        self.states
800
            .get(usize::from(row_index))
801
            .and_then(|s| s.get_item(usize::from(class)))
802
    }
803
}
804

            
805
impl ValueTable<'_> {
806
    fn get(&self, value_offset: u16) -> Option<Value> {
807
        let index = value_offset.checked_sub(self.offset).map(usize::from)?;
808

            
809
        ReadScope::new(self.values)
810
            .offset(index)
811
            .read::<I16Be>()
812
            .map(Value)
813
            .ok()
814
    }
815
}
816

            
817
struct Value(i16);
818

            
819
impl Value {
820
    /// From Apple's `kern` spec: The end of the list is marked by an odd value whose exact
821
    /// interpretation is determined by the `coverage` field in the subtable header.
822
    ///
823
    /// There is nothing of that sort in the `coverage` field, but the example in the spec implies
824
    /// that this "odd value" is the kerning value's low bit.
825
    fn end_of_list(&self) -> bool {
826
        self.0 & 1 == 1
827
    }
828

            
829
    /// The kerning value, which is the raw value with the low bit masked away.
830
    fn kerning(&self) -> i16 {
831
        self.0 & !1
832
    }
833
}
834

            
835
/// Version of `kern` table that holds owned data
836
pub mod owned {
837
    use super::KernTableVersion;
838

            
839
    /// `kern` Kerning Table (owned version).
840
    pub struct KernTable {
841
        pub(super) version: KernTableVersion,
842
        /// Number of subtables in the kerning table.
843
        pub(super) table_count: u32,
844
        pub(super) data: Box<[u8]>,
845
    }
846

            
847
    impl KernTable {
848
        /// Creates an instance of [KernTable][super::KernTable] that borrows its data from this table.
849
31005
        pub fn as_borrowed(&self) -> super::KernTable<'_> {
850
31005
            super::KernTable {
851
31005
                version: self.version,
852
31005
                table_count: self.table_count,
853
31005
                data: &self.data[..],
854
31005
            }
855
31005
        }
856
    }
857
}
858

            
859
#[cfg(test)]
860
mod tests {
861
    use crate::{
862
        tables::{FontTableProvider, OpenTypeFont},
863
        tag,
864
        tests::read_fixture,
865
    };
866

            
867
    use super::*;
868

            
869
    #[test]
870
    fn parse() {
871
        let font_buffer = read_fixture("tests/fonts/opentype/OpenSans-Regular.ttf");
872
        let otf = ReadScope::new(&font_buffer)
873
            .read::<OpenTypeFont<'_>>()
874
            .unwrap();
875
        let table_provider = otf.table_provider(0).expect("error reading font file");
876

            
877
        let kern_data = table_provider
878
            .read_table_data(tag::KERN)
879
            .expect("unable to read kern data");
880
        let kern = ReadScope::new(&kern_data)
881
            .read::<KernTable<'_>>()
882
            .expect("unable to parse kern table");
883

            
884
        let subtables = kern
885
            .sub_tables()
886
            .collect::<Result<Vec<_>, _>>()
887
            .expect("error iterating sub-tables");
888

            
889
        assert_eq!(subtables.len(), 1);
890
        let sub_table = &subtables[0];
891
        assert!(sub_table.is_horizontal());
892
        assert!(!sub_table.is_minimum());
893
        let sub_table_data = &sub_table.data;
894
        // 'W' and 'A'
895
        let kerning = sub_table_data.lookup(58, 36);
896
        assert_eq!(kerning, Some(-82));
897
    }
898
}