Faster Horse

C++ Font Subsetter: Fast, Flexible, and Secure
behdad, January 2018
This document: goo.gl/Qy3Eqc
Slides: goo.gl/QWZctq
Video: goo.gl/XbLa4X
PUBLIC DOCUMENT

Table of contents

Motivation

Definition

Scope

Usecases

Webfont delivery

Production of limited fonts

Optimizing for specific systems

Instantiating a variable font

Subsetting the variation space

Webfont streaming

Subsetting for printing

Prior Art

pyftsubset

sfntly

ots

otfcc

Design

Appendix

Pyftsubset performance limitations

Motivation

There is a need for a fast, flexible, and secure C++ font subsetter for a variety of use-cases. This document is about the scope, design, and planning of implementing that. This is the first time I’m writing a design document for something before writing a line of code, and I decided what better way than doing that fully in the open.

I like to think that I have become really good at design, but I have over-engineered things in the past (looking at you, FriBidi 0.19!), so if it looks like I am doing that in any part, please raise that. Every aspect of the design must have a reasonable justification.

Definition

Subsetting is the operation of taking a font file and producing an output font file that behaves like the original but reduced to only support a subset of the functionality of the input, based on a subsetting specification, for the purpose of reducing font file size or to enable use of the font with (older) software (including PostScript printers or file formats, like PDF) that cannot use certain features of the input font without conversion.

When speaking of font subsetting, most commonly people mean subsetting the set of supported characters, or loosely speaking, the glyph set. That is one aspect of subsetting. Other possible aspects include: subsetting the set of OpenType features, OpenType language systems, reducing general features like presence of hinting instructions or embedded bitmaps, dropping unnecessary cmap subtables, reducing or converting for different types of color fonts (CBDT/CBLC, sbix, COLR/CPAL, SVG), support for different outline formats (glyf, CFF, CFF2), support for alternate shaping systems like AAT or Graphite, support for glyph names, support for OpenType variations, subsetting of OpenType variation space to certain axes or a subset of the input design space, or instantiating a variable font to a static instance.

I understand some of the above features might better be called conversion or optimization, but we overlook that categorization in the rest of this document.

Scope

The subsetter will operate on, and produce, SFNT-like font objects. This includes first and foremost OpenType outline fonts (glyf, CFF, CFF2), but all of the following are also in scope, though with extremely varying priorities: OpenType embedded bitmaps, TrueType, TrueType collections, OpenType collections, OpenType color fonts, AAT fonts, Graphite fonts.

​
What is not in scope is dramatically different (and obsolete) font formats like Type 1, bare CFF, BDF, PCF, FON, etc.

Also not in scope is wrapper formats like EOT, WOFF, and WOFF2. While the wrapper formats are used in many use-cases where a subsetter is used, there is no synergy in combining them. Moreover, both are trivial conversions using externally available C libraries, so there is no reason to pull them into this API. Finally, generating those is drastically slower than subsetting, so, again, there is no performance gain to be had by combining them.

Usecases

Common use-cases for subsetting include:

Webfont delivery

Fonts are routinely subset to reduce Unicode / glyph set to serve smaller fonts to webfont users. Webfonts are also commonly optimized based on the client’s user agent. This is the primary use case of this subsetter and as such supported and of highest priority.

Production of limited fonts

Many font producers have embraced a workflow of producing a full-featured fonts (sometimes called “Pro”) and then use subsetting to produce limited-functionality versions, with limited glyph-sets or OpenType features. This, while not the main goal of this subsetter, is still considered in scope and supported.

Optimizing for specific systems

Subsetting can also be used to optimize fonts for a specific system. For example, fonts for use with Android or Apple systems can drop hinting-related information to save bytes. This is a supported use case.

Instantiating a variable font

Reducing a variable font to a static font representing one point in the design space is useful for embedding fonts in PDF or to serve webfonts or offline fonts to older systems like Windows 7. This is a supported use case.

Subsetting the variation space

This is the generalized version of instantiating a variable font, but requires very different implementation. While in scope, this is of much lower priority.

Webfont streaming

Over the past few years, Google, Monotype, and Adobe Typekit have all produced JavaScript-based solutions for partial / streaming delivery of webfonts. Microsoft has implemented such feature at the operating-system-level. There is active discussion at the W3C WebFonts Working Group to take on font streaming as their next project now that WOFF2 is out of the door. A super fast font subsetter can be useful for many possible streaming scenarios, like sending binary deltas of fonts subset to increasingly-growing character sets. This, while still an evolving target, is in scope of this project.

Subsetting for printing

Printing use-cases are much more varied as they need to 1. Support older, legacy, font formats like Type1, as well as produce output for use with older, legacy, systems like PostScript printers. This is in direct conflict with the scope of this subsetter and as such not supported.

We recognize the importance of this use case however. Chrome, Firefox, LibreOffice, Android, Linux desktop, and other systems all need this. Many clients have been using the C++ sfntly library (some through the Skia graphics library), while Linux desktop has mainly been using cairo / Qt graphics libraries (by GNOME / KDE desktops respectively). Of those solutions, the subsetting code in cairo is the most robust and complete, and I recommend that code be salvaged into a separate library for broader use. But that is a separate project and out of scope for this document.

Performance

Performance characteristics are of utmost importance to the scope and guide design. In particular, it is highly desirable that subsetting performance grow sublinearly with the number of glyphs in the input font. As such, any solution that first loads the font into objects is not suitable.

Prior Art

There exist many solutions to read and write fonts already. There also existing various font subsetters of varying feature sets. Here are the ones most relevant to this project:

pyftsubset

The most featureful Open Source font subsetter is the fonttools subsetter, also known as pyftsubset. We will use pyftsubset as a model to design this subsetter, and will try to keep feature and interface compatibility with that. The main difference is that fonttools and as such pyftsubset is implemented in Python, which is both slow, and not suitable for C++-based codebases like browsers.

I developed pyftsubset in 2013 and drastically optimized it over the years. It is in use in Google Fonts to subset fonts on the fly, as well as by various font designers / foundries for font production purposes. I have, however, concluded that pyftsubset has reached the limits of performance possible with Python and with fonttools’s current design (loading fonts, operating, saving). Hence, this project. (See appendix TODO.)

Fonttools also provides a limited variable font instancer, called fontTools.varLib.mutator. Mutator also suffers from the same performance and programming-language limitations as pyftsubset. The functionality of that instancer will also be implemented in this project.

sfntly

This is a very simple subsetter. Does not support complex layout (GSUB/GPOS), nor CFF. Unmaintained codebase, ported to C++ from Java by Chromium team for use in printing via Skia integration.

ots

This is an “OpenType Sanitizer”. It also decodes WOFF and WOFF2 into SFNT. It suffers from reading entire font file into memory, plus, a host of other issues. Originally was developed by Chromium developers who were not font experts. These days is maintained by Khaled Hosny (who is).

otfcc

This is the new cool kid around the block for reading / writing font files. It’s fast, has a clean code base, and (hyper-?)actively developed. However, this is modeled as a read-font, modify, write sequence as well, which has the same performance problems, no matter how fast the reading is.

Design

We draw from two projects for design: pyftsubset for user-facing API and functionality, and HarfBuzz for internal design, font access, and implementation. That is, the code will live in the HarfBuzz codebase, such that it has access to internals of HarfBuzz, so as to reuse the font access and other infrastructure already implemented there. Below I highlight some of the benefits of doing so.

HarfBuzz design

Background

There used to be “Old HarfBuzz”, which was written in C and would parse GSUB/GPOS/GDEF tables into allocated memory structures. I started rewriting it into what we call HarfBuzz today in December 2006.

The high-level goals for the rewrite were security, stability, robustness, performance, portability, and thread-safety. The design hinged on two decisions:
​

Later on, the following also became key security advantage:
​

More to be written in a separate design document.

Subsetter design

The subsetter will build on the existing HarfBuzz source code. It will live in the same source files, and the main entry point, hb_subset(), will reside in a new libharfbuzz-subset.so.

The pyftsusbset API works by taking an options object that contains all input parameters to the subsetter other than the font itself. It also takes a logging object. In the C++ version I like to break up options into two objects: a hb_subset_specification_t and a hb_subset_profile_t. The specification will include the set of characters / glyphs, layout feature tags, name table IDs, etc, whereas the profile will contain other options, like “disable hinting”, “drop glyph names”, etc.

Internally, the specification and profile are then compiled into a hb_subset_plan_t, which is font specific. This is similar to the hb_ot_shape_plan_t object, and includes all information that can be pre-computed before the actual subset byte-gathering starts.

The actual subsetting happens in one go, where bytes from the source font are read and bytes for the output font are written, one table at a time. This combines the _prune_pre_subset(), _subset_glyphs(), and _prune_post_subset() stages of pyftsubset all in one operation. This is desirable because, unlike pyftsubset, in hb-subset we want the source font face data to remain immutable; and because unlike pyftsubset, we don’t actually have a objectified in-memory representation of the font file: we work with the input bytes directly, so there is no easy way to manipulate, just to serialize new data.

The actual serialization API / machinery is to be designed. There is some precedent already. Check hb_serialize_context_t. I think we can extend / build on top of that.

Planning

In the first phase we replicate functionality of pyftsubset for the most common tables. That is, variation-space subsetting and more esoteric tables will be left out, while character-/glyph-set subsetting and various optimizations (dropping hints, glyph names, etc) are included. The rest of this document involves this phase only, which should take about one year to complete.

Milestones

Infrastructure & containers (SFNT, TTC / OTC)

In HarfBuzz we do not use C++ standard library. As such, we have to implement our own basic data structures and algorithms. We have a decent set-of-integers implementation now, that is efficient and scalable. That’s in hb-set-private.hh. That will be used in the subsetter extensively. We also need, but do not have, an efficient hash-map. This should support integral keys, as well as key types that implement ->has() and ->equal(). I’m not convinced that we would need to expose this in the API, so initially this can be just a template type in hb-dict-private.hh. I think we need to expose an integer-to-integer version though, to be used in the API to pass back to user glyph-id or other mappings to the user after subsetting. Or maybe that’s not needed. To be done as needed. It would be easier to write a really good hash-map from the beginning, instead of hacking one and change it later. Also, make it save the hash of the objects internally such that resizing will not rehash all objects contained. We do not use C++ constructors/destructors most of the time, and use init()/fini() pairs instead. Just follow idioms from existing code-base.

Next step would be to implement serialization and composition of an SFNT from a map of table-tag -> blobs. The TTC version should by default (always actually) share tables that have same blob. Add hb_blob_hash() and hb_blob_equal() for this. Model the API on hb_segment_properties_hash / equal(). Probably need to add hb_set_hash() as well.

hb_subset_specification_t, hb_subset_profile_t, hb_subset_plan_t, hb_subset_t

Next we sketch these types and will expand them as needed during the rest of development.

Compiling the subset plan includes the _closure_glyphs() part of pyftsubset as well as any other things that need to be precomputed (set of tables to include, set of glyphs, set of lookups, set of name table entries, etc.) The _closure_glyphs() already exists in HarfBuzz, but is not as complete as the pyftsubset version and needs to be brought up to date. In particular, the support for cur_glyphs is not implemented in HarfBuzz. Search for that in pyftsubset. The rest (collecting name table entries, etc) need to be added.

TrueType’ish OpenType (head, OS/2, cmap, hhea/hmtx, glyf, loca, name, post, vhea/vmtx, kern)

Next we implement serialization of the TrueType tables. Some are trivial: copy entire table, then modify it based on shape plan (head, OS/2). Others depend on glyph-set, so will loop over all glyphs and copy data for the ones in the subset (glyf, loca, post, hhea/hmtx, vhea/vmtx). Some are more involved (cmap). Etc. Each table has its own considerations, but these tables are fairly simple.

OpenType Layout (GSUB / GPOS / GDEF)

These pose particular difficulties compared to previous tables. TODO

PostScript-flavored OpenType (CFF, VORG)

TODO LATER

OpenType Variations (STAT / avar / fvar / MVAR / gvar / HVAR / VVAR)

TODO LATER

Performance

CPU time && memory.

Appendix

Pyftsubset performance limitations

TODO