1// Copyright (c) 2011 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "gsub.h"
6
7#include <limits>
8#include <vector>
9
10#include "gdef.h"
11#include "gpos.h"
12#include "layout.h"
13#include "maxp.h"
14
15// GSUB - The Glyph Substitution Table
16// http://www.microsoft.com/typography/otspec/gsub.htm
17
18namespace {
19
20// The GSUB header size
21const size_t kGsubHeaderSize = 4 + 3 * 2;
22
23enum GSUB_TYPE {
24  GSUB_TYPE_SINGLE = 1,
25  GSUB_TYPE_MULTIPLE = 2,
26  GSUB_TYPE_ALTERNATE = 3,
27  GSUB_TYPE_LIGATURE = 4,
28  GSUB_TYPE_CONTEXT = 5,
29  GSUB_TYPE_CHANGING_CONTEXT = 6,
30  GSUB_TYPE_EXTENSION_SUBSTITUTION = 7,
31  GSUB_TYPE_REVERSE_CHAINING_CONTEXT_SINGLE = 8,
32  GSUB_TYPE_RESERVED = 9
33};
34
35// Lookup type parsers.
36bool ParseSingleSubstitution(const ots::OpenTypeFile *file,
37                             const uint8_t *data, const size_t length);
38bool ParseMutipleSubstitution(const ots::OpenTypeFile *file,
39                              const uint8_t *data, const size_t length);
40bool ParseAlternateSubstitution(const ots::OpenTypeFile *file,
41                                const uint8_t *data, const size_t length);
42bool ParseLigatureSubstitution(const ots::OpenTypeFile *file,
43      const uint8_t *data, const size_t length);
44bool ParseContextSubstitution(const ots::OpenTypeFile *file,
45                              const uint8_t *data, const size_t length);
46bool ParseChainingContextSubstitution(const ots::OpenTypeFile *file,
47                                      const uint8_t *data,
48                                      const size_t length);
49bool ParseExtensionSubstitution(const ots::OpenTypeFile *file,
50                                const uint8_t *data, const size_t length);
51bool ParseReverseChainingContextSingleSubstitution(
52    const ots::OpenTypeFile *file, const uint8_t *data, const size_t length);
53
54const ots::LookupSubtableParser::TypeParser kGsubTypeParsers[] = {
55  {GSUB_TYPE_SINGLE, ParseSingleSubstitution},
56  {GSUB_TYPE_MULTIPLE, ParseMutipleSubstitution},
57  {GSUB_TYPE_ALTERNATE, ParseAlternateSubstitution},
58  {GSUB_TYPE_LIGATURE, ParseLigatureSubstitution},
59  {GSUB_TYPE_CONTEXT, ParseContextSubstitution},
60  {GSUB_TYPE_CHANGING_CONTEXT, ParseChainingContextSubstitution},
61  {GSUB_TYPE_EXTENSION_SUBSTITUTION, ParseExtensionSubstitution},
62  {GSUB_TYPE_REVERSE_CHAINING_CONTEXT_SINGLE,
63    ParseReverseChainingContextSingleSubstitution}
64};
65
66const ots::LookupSubtableParser kGsubLookupSubtableParser = {
67  arraysize(kGsubTypeParsers),
68  GSUB_TYPE_EXTENSION_SUBSTITUTION, kGsubTypeParsers
69};
70
71// Lookup Type 1:
72// Single Substitution Subtable
73bool ParseSingleSubstitution(const ots::OpenTypeFile *file,
74                             const uint8_t *data, const size_t length) {
75  ots::Buffer subtable(data, length);
76
77  uint16_t format = 0;
78  uint16_t offset_coverage = 0;
79
80  if (!subtable.ReadU16(&format) ||
81      !subtable.ReadU16(&offset_coverage)) {
82    return OTS_FAILURE();
83  }
84
85  const uint16_t num_glyphs = file->maxp->num_glyphs;
86  if (format == 1) {
87    // Parse SingleSubstFormat1
88    int16_t delta_glyph_id = 0;
89    if (!subtable.ReadS16(&delta_glyph_id)) {
90      return OTS_FAILURE();
91    }
92    if (std::abs(delta_glyph_id) >= num_glyphs) {
93      return OTS_FAILURE();
94    }
95  } else if (format == 2) {
96    // Parse SingleSubstFormat2
97    uint16_t glyph_count = 0;
98    if (!subtable.ReadU16(&glyph_count)) {
99      return OTS_FAILURE();
100    }
101    if (glyph_count > num_glyphs) {
102      return OTS_FAILURE();
103    }
104    for (unsigned i = 0; i < glyph_count; ++i) {
105      uint16_t substitute = 0;
106      if (!subtable.ReadU16(&substitute)) {
107        return OTS_FAILURE();
108      }
109      if (substitute >= num_glyphs) {
110        OTS_WARNING("too large substitute: %u", substitute);
111        return OTS_FAILURE();
112      }
113    }
114  } else {
115    return OTS_FAILURE();
116  }
117
118  if (offset_coverage < subtable.offset() || offset_coverage >= length) {
119    return OTS_FAILURE();
120  }
121  if (!ots::ParseCoverageTable(data + offset_coverage,
122                               length - offset_coverage, num_glyphs)) {
123    return OTS_FAILURE();
124  }
125
126  return true;
127}
128
129bool ParseSequenceTable(const uint8_t *data, const size_t length,
130                        const uint16_t num_glyphs) {
131  ots::Buffer subtable(data, length);
132
133  uint16_t glyph_count = 0;
134  if (!subtable.ReadU16(&glyph_count)) {
135    return OTS_FAILURE();
136  }
137  if (glyph_count > num_glyphs) {
138    return OTS_FAILURE();
139  }
140  for (unsigned i = 0; i < glyph_count; ++i) {
141    uint16_t substitute = 0;
142    if (!subtable.ReadU16(&substitute)) {
143      return OTS_FAILURE();
144    }
145    if (substitute >= num_glyphs) {
146      return OTS_FAILURE();
147    }
148  }
149
150  return true;
151}
152
153// Lookup Type 2:
154// Multiple Substitution Subtable
155bool ParseMutipleSubstitution(const ots::OpenTypeFile *file,
156                              const uint8_t *data, const size_t length) {
157  ots::Buffer subtable(data, length);
158
159  uint16_t format = 0;
160  uint16_t offset_coverage = 0;
161  uint16_t sequence_count = 0;
162
163  if (!subtable.ReadU16(&format) ||
164      !subtable.ReadU16(&offset_coverage) ||
165      !subtable.ReadU16(&sequence_count)) {
166    return OTS_FAILURE();
167  }
168
169  if (format != 1) {
170    return OTS_FAILURE();
171  }
172
173  const uint16_t num_glyphs = file->maxp->num_glyphs;
174  const unsigned sequence_end = static_cast<unsigned>(6) +
175      sequence_count * 2;
176  if (sequence_end > std::numeric_limits<uint16_t>::max()) {
177    return OTS_FAILURE();
178  }
179  for (unsigned i = 0; i < sequence_count; ++i) {
180    uint16_t offset_sequence = 0;
181    if (!subtable.ReadU16(&offset_sequence)) {
182      return OTS_FAILURE();
183    }
184    if (offset_sequence < sequence_end || offset_sequence >= length) {
185      return OTS_FAILURE();
186    }
187    if (!ParseSequenceTable(data + offset_sequence, length - offset_sequence,
188                            num_glyphs)) {
189      return OTS_FAILURE();
190    }
191  }
192
193  if (offset_coverage < sequence_end || offset_coverage >= length) {
194    return OTS_FAILURE();
195  }
196  if (!ots::ParseCoverageTable(data + offset_coverage,
197                               length - offset_coverage, num_glyphs)) {
198    return OTS_FAILURE();
199  }
200
201  return true;
202}
203
204bool ParseAlternateSetTable(const uint8_t *data, const size_t length,
205                            const uint16_t num_glyphs) {
206  ots::Buffer subtable(data, length);
207
208  uint16_t glyph_count = 0;
209  if (!subtable.ReadU16(&glyph_count)) {
210    return OTS_FAILURE();
211  }
212  if (glyph_count > num_glyphs) {
213    return OTS_FAILURE();
214  }
215  for (unsigned i = 0; i < glyph_count; ++i) {
216    uint16_t alternate = 0;
217    if (!subtable.ReadU16(&alternate)) {
218      return OTS_FAILURE();
219    }
220    if (alternate >= num_glyphs) {
221      OTS_WARNING("too arge alternate: %u", alternate);
222      return OTS_FAILURE();
223    }
224  }
225  return true;
226}
227
228// Lookup Type 3:
229// Alternate Substitution Subtable
230bool ParseAlternateSubstitution(const ots::OpenTypeFile *file,
231                                const uint8_t *data, const size_t length) {
232  ots::Buffer subtable(data, length);
233
234  uint16_t format = 0;
235  uint16_t offset_coverage = 0;
236  uint16_t alternate_set_count = 0;
237
238  if (!subtable.ReadU16(&format) ||
239      !subtable.ReadU16(&offset_coverage) ||
240      !subtable.ReadU16(&alternate_set_count)) {
241    return OTS_FAILURE();
242  }
243
244  if (format != 1) {
245    return OTS_FAILURE();
246  }
247
248  const uint16_t num_glyphs = file->maxp->num_glyphs;
249  const unsigned alternate_set_end = static_cast<unsigned>(6) +
250      alternate_set_count * 2;
251  if (alternate_set_end > std::numeric_limits<uint16_t>::max()) {
252    return OTS_FAILURE();
253  }
254  for (unsigned i = 0; i < alternate_set_count; ++i) {
255    uint16_t offset_alternate_set = 0;
256    if (!subtable.ReadU16(&offset_alternate_set)) {
257      return OTS_FAILURE();
258    }
259    if (offset_alternate_set < alternate_set_end ||
260        offset_alternate_set >= length) {
261      return OTS_FAILURE();
262    }
263    if (!ParseAlternateSetTable(data + offset_alternate_set,
264                                length - offset_alternate_set,
265                                num_glyphs)) {
266      return OTS_FAILURE();
267    }
268  }
269
270  if (offset_coverage < alternate_set_end || offset_coverage >= length) {
271    return OTS_FAILURE();
272  }
273  if (!ots::ParseCoverageTable(data + offset_coverage,
274                               length - offset_coverage, num_glyphs)) {
275    return OTS_FAILURE();
276  }
277
278  return true;
279}
280
281bool ParseLigatureTable(const uint8_t *data, const size_t length,
282                        const uint16_t num_glyphs) {
283  ots::Buffer subtable(data, length);
284
285  uint16_t lig_glyph = 0;
286  uint16_t comp_count = 0;
287
288  if (!subtable.ReadU16(&lig_glyph) ||
289      !subtable.ReadU16(&comp_count)) {
290    return OTS_FAILURE();
291  }
292
293  if (lig_glyph >= num_glyphs) {
294    OTS_WARNING("too large lig_glyph: %u", lig_glyph);
295    return OTS_FAILURE();
296  }
297  if (comp_count == 0 || comp_count > num_glyphs) {
298    return OTS_FAILURE();
299  }
300  for (unsigned i = 0; i < comp_count - static_cast<unsigned>(1); ++i) {
301    uint16_t component = 0;
302    if (!subtable.ReadU16(&component)) {
303      return OTS_FAILURE();
304    }
305    if (component >= num_glyphs) {
306      return OTS_FAILURE();
307    }
308  }
309
310  return true;
311}
312
313bool ParseLigatureSetTable(const uint8_t *data, const size_t length,
314                           const uint16_t num_glyphs) {
315  ots::Buffer subtable(data, length);
316
317  uint16_t ligature_count = 0;
318
319  if (!subtable.ReadU16(&ligature_count)) {
320    return OTS_FAILURE();
321  }
322
323  const unsigned ligature_end = static_cast<unsigned>(2) + ligature_count * 2;
324  if (ligature_end > std::numeric_limits<uint16_t>::max()) {
325    return OTS_FAILURE();
326  }
327  for (unsigned i = 0; i < ligature_count; ++i) {
328    uint16_t offset_ligature = 0;
329    if (!subtable.ReadU16(&offset_ligature)) {
330      return OTS_FAILURE();
331    }
332    if (offset_ligature < ligature_end || offset_ligature >= length) {
333      return OTS_FAILURE();
334    }
335    if (!ParseLigatureTable(data + offset_ligature, length - offset_ligature,
336                            num_glyphs)) {
337      return OTS_FAILURE();
338    }
339  }
340
341  return true;
342}
343
344// Lookup Type 4:
345// Ligature Substitution Subtable
346bool ParseLigatureSubstitution(const ots::OpenTypeFile *file,
347                               const uint8_t *data, const size_t length) {
348  ots::Buffer subtable(data, length);
349
350  uint16_t format = 0;
351  uint16_t offset_coverage = 0;
352  uint16_t lig_set_count = 0;
353
354  if (!subtable.ReadU16(&format) ||
355      !subtable.ReadU16(&offset_coverage) ||
356      !subtable.ReadU16(&lig_set_count)) {
357    return OTS_FAILURE();
358  }
359
360  if (format != 1) {
361    return OTS_FAILURE();
362  }
363
364  const uint16_t num_glyphs = file->maxp->num_glyphs;
365  const unsigned ligature_set_end = static_cast<unsigned>(6) +
366      lig_set_count * 2;
367  if (ligature_set_end > std::numeric_limits<uint16_t>::max()) {
368    return OTS_FAILURE();
369  }
370  for (unsigned i = 0; i < lig_set_count; ++i) {
371    uint16_t offset_ligature_set = 0;
372    if (!subtable.ReadU16(&offset_ligature_set)) {
373      return OTS_FAILURE();
374    }
375    if (offset_ligature_set < ligature_set_end ||
376        offset_ligature_set >= length) {
377      return OTS_FAILURE();
378    }
379    if (!ParseLigatureSetTable(data + offset_ligature_set,
380                               length - offset_ligature_set, num_glyphs)) {
381      return OTS_FAILURE();
382    }
383  }
384
385  if (offset_coverage < ligature_set_end || offset_coverage >= length) {
386    return OTS_FAILURE();
387  }
388  if (!ots::ParseCoverageTable(data + offset_coverage,
389                               length - offset_coverage, num_glyphs)) {
390    return OTS_FAILURE();
391  }
392
393  return true;
394}
395
396// Lookup Type 5:
397// Contextual Substitution Subtable
398bool ParseContextSubstitution(const ots::OpenTypeFile *file,
399                              const uint8_t *data, const size_t length) {
400  return ots::ParseContextSubtable(data, length, file->maxp->num_glyphs,
401                                   file->gsub->num_lookups);
402}
403
404// Lookup Type 6:
405// Chaining Contextual Substitution Subtable
406bool ParseChainingContextSubstitution(const ots::OpenTypeFile *file,
407                                      const uint8_t *data,
408                                      const size_t length) {
409  return ots::ParseChainingContextSubtable(data, length,
410                                           file->maxp->num_glyphs,
411                                           file->gsub->num_lookups);
412}
413
414// Lookup Type 7:
415// Extension Substition
416bool ParseExtensionSubstitution(const ots::OpenTypeFile *file,
417                                const uint8_t *data, const size_t length) {
418  return ots::ParseExtensionSubtable(file, data, length,
419                                     &kGsubLookupSubtableParser);
420}
421
422// Lookup Type 8:
423// Reverse Chaining Contexual Single Substitution Subtable
424bool ParseReverseChainingContextSingleSubstitution(
425    const ots::OpenTypeFile *file, const uint8_t *data, const size_t length) {
426  ots::Buffer subtable(data, length);
427
428  uint16_t format = 0;
429  uint16_t offset_coverage = 0;
430
431  if (!subtable.ReadU16(&format) ||
432      !subtable.ReadU16(&offset_coverage)) {
433    return OTS_FAILURE();
434  }
435
436  const uint16_t num_glyphs = file->maxp->num_glyphs;
437
438  uint16_t backtrack_glyph_count = 0;
439  if (!subtable.ReadU16(&backtrack_glyph_count)) {
440    return OTS_FAILURE();
441  }
442  if (backtrack_glyph_count > num_glyphs) {
443    return OTS_FAILURE();
444  }
445  std::vector<uint16_t> offsets_backtrack;
446  offsets_backtrack.reserve(backtrack_glyph_count);
447  for (unsigned i = 0; i < backtrack_glyph_count; ++i) {
448    uint16_t offset = 0;
449    if (!subtable.ReadU16(&offset)) {
450      return OTS_FAILURE();
451    }
452    offsets_backtrack.push_back(offset);
453  }
454
455  uint16_t lookahead_glyph_count = 0;
456  if (!subtable.ReadU16(&lookahead_glyph_count)) {
457    return OTS_FAILURE();
458  }
459  if (lookahead_glyph_count > num_glyphs) {
460    return OTS_FAILURE();
461  }
462  std::vector<uint16_t> offsets_lookahead;
463  offsets_lookahead.reserve(lookahead_glyph_count);
464  for (unsigned i = 0; i < lookahead_glyph_count; ++i) {
465    uint16_t offset = 0;
466    if (!subtable.ReadU16(&offset)) {
467      return OTS_FAILURE();
468    }
469    offsets_lookahead.push_back(offset);
470  }
471
472  uint16_t glyph_count = 0;
473  if (!subtable.ReadU16(&glyph_count)) {
474    return OTS_FAILURE();
475  }
476  if (glyph_count > num_glyphs) {
477    return OTS_FAILURE();
478  }
479  for (unsigned i = 0; i < glyph_count; ++i) {
480    uint16_t substitute = 0;
481    if (!subtable.ReadU16(&substitute)) {
482      return OTS_FAILURE();
483    }
484    if (substitute >= num_glyphs) {
485      return OTS_FAILURE();
486    }
487  }
488
489  const unsigned substitute_end = static_cast<unsigned>(10) +
490      (backtrack_glyph_count + lookahead_glyph_count + glyph_count) * 2;
491  if (substitute_end > std::numeric_limits<uint16_t>::max()) {
492    return OTS_FAILURE();
493  }
494
495  if (offset_coverage < substitute_end || offset_coverage >= length) {
496    return OTS_FAILURE();
497  }
498  if (!ots::ParseCoverageTable(data + offset_coverage,
499                               length - offset_coverage, num_glyphs)) {
500    return OTS_FAILURE();
501  }
502
503  for (unsigned i = 0; i < backtrack_glyph_count; ++i) {
504    if (offsets_backtrack[i] < substitute_end ||
505        offsets_backtrack[i] >= length) {
506      return OTS_FAILURE();
507    }
508    if (!ots::ParseCoverageTable(data + offsets_backtrack[i],
509                                 length - offsets_backtrack[i], num_glyphs)) {
510      return OTS_FAILURE();
511    }
512  }
513
514  for (unsigned i = 0; i < lookahead_glyph_count; ++i) {
515    if (offsets_lookahead[i] < substitute_end ||
516        offsets_lookahead[i] >= length) {
517      return OTS_FAILURE();
518    }
519    if (!ots::ParseCoverageTable(data + offsets_lookahead[i],
520                                 length - offsets_lookahead[i], num_glyphs)) {
521      return OTS_FAILURE();
522    }
523  }
524
525  return true;
526}
527
528}  // namespace
529
530#define DROP_THIS_TABLE \
531  do { file->gsub->data = 0; file->gsub->length = 0; } while (0)
532
533namespace ots {
534
535// As far as I checked, following fonts contain invalid values in GSUB table.
536// OTS will drop their GSUB table.
537//
538// # too large substitute (value is 0xFFFF)
539// kaiu.ttf
540// mingliub2.ttf
541// mingliub1.ttf
542// mingliub0.ttf
543// GraublauWeb.otf
544// GraublauWebBold.otf
545//
546// # too large alternate (value is 0xFFFF)
547// ManchuFont.ttf
548//
549// # bad offset to lang sys table (NULL offset)
550// DejaVuMonoSansBold.ttf
551// DejaVuMonoSansBoldOblique.ttf
552// DejaVuMonoSansOblique.ttf
553// DejaVuSansMono-BoldOblique.ttf
554// DejaVuSansMono-Oblique.ttf
555// DejaVuSansMono-Bold.ttf
556//
557// # bad start coverage index
558// GenBasBI.ttf
559// GenBasI.ttf
560// AndBasR.ttf
561// GenBkBasI.ttf
562// CharisSILR.ttf
563// CharisSILBI.ttf
564// CharisSILI.ttf
565// CharisSILB.ttf
566// DoulosSILR.ttf
567// CharisSILBI.ttf
568// GenBkBasB.ttf
569// GenBkBasR.ttf
570// GenBkBasBI.ttf
571// GenBasB.ttf
572// GenBasR.ttf
573//
574// # glyph range is overlapping
575// KacstTitleL.ttf
576// KacstDecorative.ttf
577// KacstTitle.ttf
578// KacstArt.ttf
579// KacstPoster.ttf
580// KacstQurn.ttf
581// KacstDigital.ttf
582// KacstBook.ttf
583// KacstFarsi.ttf
584
585bool ots_gsub_parse(OpenTypeFile *file, const uint8_t *data, size_t length) {
586  // Parsing gsub table requires |file->maxp->num_glyphs|
587  if (!file->maxp) {
588    return OTS_FAILURE();
589  }
590
591  Buffer table(data, length);
592
593  OpenTypeGSUB *gsub = new OpenTypeGSUB;
594  file->gsub = gsub;
595
596  uint32_t version = 0;
597  uint16_t offset_script_list = 0;
598  uint16_t offset_feature_list = 0;
599  uint16_t offset_lookup_list = 0;
600  if (!table.ReadU32(&version) ||
601      !table.ReadU16(&offset_script_list) ||
602      !table.ReadU16(&offset_feature_list) ||
603      !table.ReadU16(&offset_lookup_list)) {
604    return OTS_FAILURE();
605  }
606
607  if (version != 0x00010000) {
608    OTS_WARNING("bad GSUB version");
609    DROP_THIS_TABLE;
610    return true;
611  }
612  if ((offset_script_list < kGsubHeaderSize ||
613       offset_script_list >= length) ||
614      (offset_feature_list < kGsubHeaderSize ||
615       offset_feature_list >= length) ||
616      (offset_lookup_list < kGsubHeaderSize ||
617       offset_lookup_list >= length)) {
618    OTS_WARNING("bad offset in GSUB header");
619    DROP_THIS_TABLE;
620    return true;
621  }
622
623  if (!ParseLookupListTable(file, data + offset_lookup_list,
624                            length - offset_lookup_list,
625                            &kGsubLookupSubtableParser,
626                            &gsub->num_lookups)) {
627    OTS_WARNING("faild to parse lookup list table");
628    DROP_THIS_TABLE;
629    return true;
630  }
631
632  uint16_t num_features = 0;
633  if (!ParseFeatureListTable(data + offset_feature_list,
634                             length - offset_feature_list, gsub->num_lookups,
635                             &num_features)) {
636    OTS_WARNING("faild to parse feature list table");
637    DROP_THIS_TABLE;
638    return true;
639  }
640
641  if (!ParseScriptListTable(data + offset_script_list,
642                            length - offset_script_list, num_features)) {
643    OTS_WARNING("faild to parse script list table");
644    DROP_THIS_TABLE;
645    return true;
646  }
647
648  gsub->data = data;
649  gsub->length = length;
650  return true;
651}
652
653bool ots_gsub_should_serialise(OpenTypeFile *file) {
654  const bool needed_tables_dropped =
655      (file->gdef && file->gdef->data == NULL) ||
656      (file->gpos && file->gpos->data == NULL);
657  return file->gsub != NULL && file->gsub->data != NULL
658      && !needed_tables_dropped;
659}
660
661bool ots_gsub_serialise(OTSStream *out, OpenTypeFile *file) {
662  if (!out->Write(file->gsub->data, file->gsub->length)) {
663    return OTS_FAILURE();
664  }
665
666  return true;
667}
668
669void ots_gsub_free(OpenTypeFile *file) {
670  delete file->gsub;
671}
672
673}  // namespace ots
674
675