kc3-lang/harfbuzz/docs/repacker.md

Branch

Download

Introduction

Several tables in the opentype format are formed internally by a graph of subtables. Parent node’s reference their children through the use of positive offsets, which are typically 16 bits wide. Since offsets are always positive this forms a directed acyclic graph. For storage in the font file the graph must be given a topological ordering and then the subtables packed in serial according to that ordering. Since 16 bit offsets have a maximum value of 65,535 if the distance between a parent subtable and a child is more then 65,535 bytes then it’s not possible for the offset to encode that edge.

For many fonts with complex layout rules (such as Arabic) it’s not unusual for the tables containing layout rules (GSUB/GPOS) to be larger than 65kb. As a result these types of fonts are susceptible to offset overflows when serializing to the binary font format.

Offset overflows can happen for a variety of reasons and require different strategies to resolve:

In general there isn’t a simple solution to produce an optimal topological ordering for a given graph. Finding an ordering which doesn’t overflow is a NP hard problem. Existing solutions use heuristics which attempt a combination of the above strategies to attempt to find a non-overflowing configuration.

The harfbuzz subsetting library includes a repacking algorithm which is used to resolve offset overflows that are present in the subsetted tables it produces. This document provides a deep dive into how the harfbuzz repacking algorithm works.

Other implementations exist, such as in fontTools, however these are not covered in this document.

Foundations

There’s four key pieces to the harfbuzz approach:

High Level Algorithm

def repack(graph):
  graph.topological_sort()

  if (graph.will_overflow())
    preprocess(graph)
    assign_spaces(graph)
    graph.topological_sort()

  while (overflows = graph.will_overflow()):
    for overflow in overflows:
      apply_offset_resolution_strategy (overflow, graph)
    graph.topological_sort()

The actual code for this processing loop can be found in the function hb_resolve_overflows () of hb-repacker.hh.

Topological Sorting Algorithms

The harfbuzz repacker uses two different algorithms for topological sorting:

Kahn’s algorithm is approximately twice as fast as the shortest distance sort so that is attempted first (only on the first topological sort). If it fails to eliminate overflows then shortest distance sort will be used for all subsequent topological sorting operations.

Shortest Distance Sort

This algorithm orders the nodes based on total distance to each node. Nodes with a shorter distance are ordered first.

The “weight” of an edge is the sum of the size of the sub-table being pointed to plus 2^16 for a 16 bit offset and 2^32 for a 32 bit offset.

The distance of a node is the sum of all weights along the shortest path from the root to that node plus a priority modifier (used to change where nodes are placed by moving increasing or decreasing the effective distance). Ties between nodes with the same distance are broken based on the order of the offset in the sub table bytes.

The shortest distance to each node is determined using Djikstra’s algorithm. Then the topological ordering is produce by applying a modified version of Kahn’s algorithm that uses a priority queue based on the shortest distance to each node.

Optimizing the Sorting

The topological sorting operation is the core of the repacker and is run on each iteration so it needs to be as fast as possible. There’s a few things that are done to speed up subsequent sorting operations:

Caching these values allows the repacker to avoid recalculating them for the full graph on each iteration.

The other important factor to speed is a fast priority queue which is a core datastructure to the topological sorting algorithm. Currently a basic heap based queue is used. Heap based queue’s don’t support fast priority decreases, but that can be worked around by just adding redundant entries to the priority queue and filtering the older ones out when poppping off entries. This is based on the recommendations in a study of the practical performance of priority queues in Dijkstra’s algorithm

Special Handling of 32 bit Offsets

If a graph contains multiple 32 bit offsets then the shortest distance sorting will be likely be suboptimal. For example consider the case where a graph contains two 32 bit offsets that each point to a subgraph which are not connected to each other. The shortest distance sort will interleave the subtables of the two subgraphs, potentially resulting in overflows. Since each of these subgraphs are independent of each other, and 32 bit offsets can point extremely long distances a better strategy is to pack the first subgraph in it’s entirety and then have the second subgraph packed after with the 32 bit offset pointing over the first subgraph. For example given the graph:

a--- b -- d -- f
 \
  \_ c -- e -- g

Where the links from a to b and a to c are 32 bit offsets, the shortest distance sort would be:

a, b, c, d, e, f, g

If nodes d and e have a combined size greater than 65kb then the offset from d to f will overflow. A better ordering is:

a, b, d, f, c, e, g

The ability for 32 bit offsets to point long distances is utilized to jump over the subgraph of b which gives the remaining 16 bit offsets a better chance of not overflowing.

The above is an ideal situation where the subgraphs are disconnected from each other, in practice this is often not this case. So this idea can be generalized as follows:

If there is a subgraph that is only reachable from one or more 32 bit offsets, then:

The sorting algorithm incorporates this via a “space” modifier that can be applied to nodes in the graph. By default all nodes are treated as being in space zero. If a node is given a non-zero space, n, then the computed distance to the node will be modified by adding n * 2^32. This will cause that node and it’s descendants to be packed between all nodes in space n-1 and space n+1. Resulting in a topological sort like:

| space 0 subtables | space 1 subtables | .... | space n subtables |

The assign_spaces() step in the high level algorithm is responsible for identifying independent subgraphs and assigning unique spaces to each one. More information on the space assignment can be found in the next section.

Graph Preprocessing

For certain table types we can preprocess and modify the graph structure to reduce the occurences of overflows. Currently the repacker implements preprocessing only for GPOS and GSUB tables.

GSUB/GPOS Table Splitting

The GSUB/GPOS preprocessor scans each lookup subtable and determines if the subtable’s children are so large that no overflow resolution is possible (for example a single subtable that exceeds 65kb cannot be pointed over). When such cases are detected table splitting is invoked:

Table splitting must be aware of the underlying format of each subtable type and thus needs custom code for each subtable type. Currently subtable splitting is only supported for GPOS subtable types.

GSUB/GPOS Extension Lookup Promotion

In GSUB/GPOS tables lookups can be regular lookups which use 16 bit offsets to the children subtables or extension lookups which use 32 bit offsets to the children subtables. If the sub graph of all regular lookups is too large then it can be difficult to find an overflow free configuration. This can be remedied by promoting one or more regular lookups to extension lookups.

During preprocessing the graph is scanned to determine the size of the subgraph of regular lookups. If the graph is found to be too big then the analysis finds a set of lookups to promote to reduce the subgraph size. Lastly the graph is modified to convert those lookups to extension lookups.

Offset Resolution Strategies

Space Assignment

The goal of space assignment is to find connected subgraphs that are only reachable via 32 bit offsets and then assign each such subgraph to a unique non-zero space. The algorithm is roughly:

  1. Collect the set, S, of nodes that are children of 32 bit offsets.

  2. Do a directed traversal from each node in S and collect all encountered nodes into set T. Mark all nodes in the graph that are not in T as being in space 0.

  3. Set next_space = 1.

  4. While set S is not empty:

    a. Pick a node n in set S then perform an undirected graph traversal and find the set Q of 

    nodes that are reachable from `n`.

    b. During traversal if a node, m, has a edge to a node in space 0 then m must be duplicated 

    to disconnect it from space 0.

    d. Remove all nodes in Q from S and assign all nodes in Q to next_space.

    c. Increment next_space by one.

Manual Iterative Resolutions

For each overflow in each iteration the algorithm will attempt to apply offset overflow resolution strategies to eliminate the overflow. The type of strategy applied is dependent on the characteristics of the overflowing link:

Test Cases

The harfbuzz repacker has tests defined using generic graphs: https://github.com/harfbuzz/harfbuzz/blob/main/src/test-repacker.cc

Future Improvements

Currently for GPOS tables the repacker implementation is sufficient to handle both subsetting and the general case of font compilation repacking. However for GSUB the repacker is only sufficient for subsetting related overflows. To enable general case repacking of GSUB, support for splitting of GSUB subtables will need to be added. Other table types such as COLRv1 shouldn’t require table splitting due to the wide use of 24 bit offsets throughout the table.

Beyond subtable splitting there are a couple of “nice to have” improvements, but these are not required to support the general case:

Source

Download

kmx.io     mail     discord kmxgit v0.4.0