Incremental Font Transfer

1. Introduction

This section is not normative.

The success of WebFonts is unevenly distributed. This specification allows WebFonts to be used where slow networks, very large fonts, or complex subsetting requirements currently preclude their use. For example, even using WOFF 2 [WOFF2], fonts for CJK languages are too large to be practical.

See the Progressive Font Enrichment: Evaluation Report [PFE-report] for the investigation which led to this specification.

There are two different methods which can be used to incrementally transfer fonts. The first method, Patch Subset, uses a backend server which can generate binary patches to an existing font. The second method, Range Request, utilizes HTTP range requests to load only the parts of the original font that are needed.

The evaluation report found that patch subset was generally more efficient in terms of overall performance and transferred bytes than range request. However, Range Request is simpler to deploy for many uses cases while still providing material improvments to loading performance for large fonts so it is included in this specification as an alternative method.

2. Patch Based Incremental Transfer

2.1. Overview

In the patch subset approach to incremental font transfer a server generates binary patches which a client applies to a subset of the font in order to extend the coverage of that font subset. The server is stateless, it does not maintain any session data for clients between requests. Thus when a client requests the generation of a patch from the server it must fully describe the current subset of the font that it has in a way which allows the server to recreate it.

Generic binary patch algorithms are used which do not need to be aware of the specifics of the font format. Typically a server will produce a patch by generating two font subsets: one which matches what the client currently has and one which matches the extended subset the client desires. A binary patch is then produced between the two subsets.

2.1.1. Font Subset

A subset of a font file is a modified version of the font that contains only the data needed to render a subset of the codepoints in the original font. A subsetted font should be able to render any combination of the codepoints in the subset identically to the original font.

2.2. Data Types

This section lists all of the data types that are used to form the request and response messages sent between the client and server.

2.2.1. Encoding

All data types defined here are encoded into a byte representation for transport using CBOR (Concise Binary Object Representation) [rfc8949]. More information on how each data types should be encoded by CBOR are given in the definition of those data types.

2.2.2. Primitives

2.2.3. ProtocolVersion

An Integer describing the version of this communication protocol being used by a PatchRequest or PatchResponse. This value guides the semantics and interpretation of the fields sent.

This field is for future expansion. There currently is only one valid value, 0.

2.2.4. SparseBitSet

A data structure which compactly stores a set of distinct unsigned integers. The set is represented as a tree where each node has a fixed number of children that recursively sub-divides an interval into equal partitions. A tree of height H with branching factor B can store set membership for integers in the interval [0 to B^H-1] inclusive. The tree is encoded into a ByteString for transport.

To construct the tree T which encodes set S first select the branching factor B (how many children each node has). B can be 4, 8, 16, or 32.

Note: the encoder can use any of the possible branching factors, but it is recommended to use 4 as that has been shown to give the smallest encodings for most sets typically encountered.

Next, determine the height, H, of the tree:

H = ceil(log_B(max(S) + 1))

Next create a tree of height H where all non-leaf nodes have B children. Each node in the tree has a single value composed of B bits. Given a node p which has B children: c₀ ... c_{B - 1} and is in a tree, T, of height H, then:

• D(n) is depth of node n: the number of edges between the root node and n.

• Start(c_i) is the start (inclusive) of the interval covered by c_i :
  Start(c_i) = Start(p) + i * B^{H - D(c_i)}

• End(c_i) is the end (exclusive) of the interval covered by c_i :
  End(c_i) = Start(p) + (i + 1) * B^{H - D(c_i)}

• Start(root node) = 0

• The value of node p is a string of B bits. If its bits are numbered from 0 (least significant) to B - 1 (most significant) then bit i will be 1 if the set S contains at least one member in the interval [Start(c_i), End(c_i)), otherwise bit i will be 0.

• If for node p, End(p) - Start(p) = B, then p will have no children.

The tree is encoded into a bit string. When appending multiple-bit values to the bit string, bits are added in order from least significant bit to most significant bit.

First append 2 bits which encode the branching factor:

Then append the value H - 1 as a 6 bit unsigned integer.

Next the nodes are encoded into the bit string by traversing the nodes of the T in level order and appending the value for each non-zero node to the bit string. If all of the set values covered by a node’s interval are present within set S, then that node can instead be encoded in the bit string as B bits all set to zero. All children of that node must not be encoded.

Lastly the bit string is converted into a ByteString by converting each consecutive group of 8 bits into the next byte of the string. If the number of bits in the bit string is not a multiple of 8, zero bits are appended to the next multiple of 8. The bit with the smallest index in the bit string is the least significant bit in the byte and the bit with the largest index is the most significant bit.

  BitString:
  |- header |- lvl 0 |---- level 1 ----|------- level 2 -----------|
  |         |   n0   |   n1       n2   |   n3       n4       n5    |
  [ 10010000 10000100 10001000 10000000 00100000 01000000 00010000 ]

  Which then becomes the ByteString:
  [
    0b00001001,
    0b00100001,
    0b00010001,
    0b00000001,
    0b00000100,
    0b00000010,
    0b00001000
  ]

  BitString:
  |- header | l0 |- lvl 1 -| l2  |
  |         | n0 | n1 | n2 | n3  |
  [ 00010000 1100 0000 1000 1100 ]

  ByteString:
  [
    0b00001000,
    0b00000011,
    0b00110001
  ]

2.2.5. IntegerList

A data structure which compactly represents a list of non-negative integers from 0 to 2³¹-1. The list is encoded into a ByteString for transport.

There are three steps of encoding/compression: first delta, second zig-zag, and finally UIntBase128. The final ByteString result is simply the concatenation of the individual UIntBase128 encoded bytes.

IntegerList encoding must reject an input list which contains values not in the range 0 to 2³¹-1. Likewise if decoding an IntegerList results in values which are not in the range 0 to 2³¹-1 the list is invalid and must be rejected.

2.2.5.1. Delta Encoding

Delta encoding converts a list of integers to a list of deltas between them.

A list L of n integers L_i0..n-1 is converted into a list of N integers D_i0..n-1 as follows:

• D₀ = L₀

• D_{i = 1..n-1} = L_i - L_i-1

This has the effect of reducing the magnitude of the values, which reduces the number of bytes required in the UIntBase128 encoding, below.

// Note: unsorted
int_list = [23, 43, 12, 3, 67, 68, 69, 0]
delta_list = [23, 20, -31, -9, 64, 1, 1, -69]

2.2.5.2. Zig-Zag Encoding

Zig-Zag encoding reversibly converts signed integers to unsigned integers, using the same number of bits. The entire range of values is supported. This step is required, as the § 2.2.5.3 UIntBase128 Encoding step works on unsigned integers only. The encoding maps positive integer values to even positive integers and negative integer values to odd positive integers. Psuedo code:

encode(n):
  if n >= 0:
    return n * 2
  else:
    return (n * -2) - 1

decode(n) {
  if n & 1:
    return -((n + 1) / 2)
  else:
    return n / 2

delta_list = [23, 20, -31, -9, 64, 1, 1, -69]
zig_zag_encoded_list = [46, 40, 61, 17, 128, 2, 2, 137]

2.2.5.3. UIntBase128 Encoding

UIntBase128 is a variable length encoding of unsigned integers, suitable for values up to 2³²-1. A UIntBase128 encoded number is a sequence of bytes for which the most significant bit is set for all but the last byte, and clear for the last byte. The number itself is base 128 encoded in the lower 7 bits of each byte. Thus, a decoding procedure for a UIntBase128 is: start with value = 0. Consume a byte, setting value = old value times 128 + (byte bitwise-and 127). Repeat last step until the most significant bit of byte is false.

UIntBase128 encoding format allows a possibility of sub-optimal encoding, where e.g. the same numerical value can be represented with variable number of bytes (utilizing leading zeros). For example, the value 63 could be encoded as either one byte 0x3F or two (or more) bytes: [0x80, 0x3f]. An encoder must not allow this to happen and *MUST* produce shortest possible encoding. A decoder *MUST* reject the font file if it encounters a UIntBase128-encoded value with leading zeros (a value that starts with the byte 0x80), if UIntBase128-encoded sequence is longer than 5 bytes, or if a UIntBase128-encoded value exceeds 2³²-1. Pseudo-code:

bool ReadUIntBase128( data, *result ) {
  UInt32 accum = 0;

  for (i = 0; i < 5; i++) {
    UInt8 data_byte = data.getNextUInt8();

    // No leading 0’s
    if (i == 0 && data_byte == 0x80) return false;

    // If any of top 7 bits are set then << 7 would overflow
    if (accum & 0xFE000000) return false;

    *accum = (accum << 7) | (data_byte & 0x7F);

    // Spin until most significant bit of data byte is false
    if ((data_byte & 0x80) == 0) {
      *result = accum;
      return true;
    }
  }
  // UIntBase128 sequence exceeds 5 bytes
  return false;
}

Value       Output Bytes
0           00000000
1           00000001
2           00000010
3           00000011
127         01111111
128         10000001 00000000
255         10000001 01111111
16256       11111111 00000000
2080768     11111111 10000000 00000000
266338304   11111111 10000000 10000000 00000000
4294967295  10001111 11111111 11111111 11111111 01111111

zig_zag_encoded_list = [46, 40, 61, 17, 128, 2, 2, 137]
bytes = [2E 28 3D 11 81 00 02 02 81 09]
         └┘ └┘ └┘ └┘ └───┘ └┘ └┘ └───┘

2.2.6. SortedIntegerList

A data structure which compactly represents a sorted list of ascending non-negative integers (0 to 2³²-1). The list is encoded into a ByteString for transport.

This is a variation on IntegerList with better compression. Sorted lists only use two steps of encoding/compression: first deltas and then UIntBase128. The § 2.2.5.2 Zig-Zag Encoding step is skipped. This allows twice the range in UIntBase128, so that single bytes may be used more often.

SortedIntegerList encoding must reject an input list which contains values not in the range 0 to 2³²-1. Likewise if decoding an IntegerList results in values which are not in the range 0 to 2³²-1 the list is invalid and must be rejected.

2.2.7. RangeList

A RangeList encodes a set of non-negative integers (0 to 2³²-1). The set is encoded as a list of disjoint intervals. Each interval is represented by two integers, a start (inclusive) and end (inclusive).

A RangeList is a list of n pairs [min_i0..n-1, max_i0..n-1]. The list must be non-decreasing, i.e. min_i=1..n-1 >= max_i-1.

To encode this list, we convert it to a list L of 2n integers, where L_2i = min_i and L_2i+1 = max_i for i = 0..n-1.

L is a sorted list of integers, so § 2.2.6 SortedIntegerList is used to encode it as a ByteString.

range_list = [3, 10], [13, 268]
int_list = [3, 10, 13, 268]
delta_list = [3, 7, 3, 255]
bytes = [03 07 03 81 7F]

2.2.8. AxisSpace

Stores a set of intervals on one or more open type variation axes [opentype-variations]. Encoded as a CBOR map (major type 5). The key in each pair is an axis tag. It is encoded as a ByteString containing exactly 4 ASCII characters. The value in each pair is an ArrayOf<AxisInterval> § 2.3.2 AxisInterval. The list of intervals for a distinct axis tag must be disjoint.

2.2.9. Objects

Objects are data structures comprised of key and value pairs. Objects are encoded via CBOR as maps (major type 5). Each key and value pair is encoded as a single map entry. Keys are always unsigned integers and are encoded using major type 0. Values are encoded using the encoding specified by the type of the value.

All fields in an object are optional and do not need to have an associated value. Conversely when decoding and object fields may be present which are not specified in the schema. The decoder must ignore without error any key and value pairs where the key is not recognized.

There are several types of object used, each type is defined by a schema in § 2.3 Object Schemas. The schema for a type specifies for each field:

• A human readable name for the field. For reference only, not used in the encoding.

• A unsigned integer id for the field. This is used as the key in the encoding.

• The type of the value stored in this field. Can be any of the types defined in § 2.2 Data Types including object types.

2.3. Object Schemas

2.3.1. CompressedSet

Encodes a set of unsigned integers. The set is not ordered and does not allow duplicates. Members of the set are encoded into either a SparseBitSet or a RangeList. To obtain the final set the members of the sparse bit set and the list of ranges are unioned together.

2.3.2. AxisInterval

AxisInterval defines an interval (from start to end inclusive) on some variable axis in a font.

For an AxisInterval object to be well formed:

• start must be set.

• end is optional, must be greater than start. If end is not set then this interval is a single point, start.

2.3.3. PatchRequest

For a PatchRequest object to be well formed:

• protocol_version must be set to 0.

• accept_patch_format can include any of the values listed in § 2.8 Patch Formats.

• If either of indices_have or indices_needed is set to a non-empty set then ordering_checksum must be set.

• If codepoints_have or indices_have is set to a non-empty set then original_font_checksum and base_checksum must be set.

• connection_speed can be any of the values listed in § 2.9 Connection Speeds.

2.3.4. PatchResponse

For a PatchResponse object to be well formed:

• protocol_version must be set to 0.

• patch_format can be any of the values listed § 2.8 Patch Formats

• Only one of patch or replacement may be set.

• If either patch or replacement is set then patch_format, patched_checksum, and original_font_checksum must be set.

• If codepoint_ordering is set then ordering_checksum must be set.

2.4. Client

2.4.1. Client State

The client will need to maintain at minimum the following state for each font file being incrementally transferred:

• Font subset: a byte array containing the binary data for the most recent version of the subset of the font being incrementally transferred. For a new font this is initialized to empty byte array.

• Original font checksum: the most recent value of PatchResponse.original_font_checksum received from the server for this font.

• Codepoint Reordering Map: The most recent § 2.7 Codepoint Reordering received from the server for this font.

• Codepoint Reordering Checksum: The most recent PatchResponse.ordering_checksum for this font.

• Original Font Axis Space: the variations axis space that the original font covers. Supplied by PatchResponse.original_axis_space.

• Subset Axis Space: the most recent variations axis space that the subsetted font covers. Supplied by PatchResponse.subset_axis_space.

2.4.2. Extending the Font Subset

A client extends its font subset to cover additional codepoints by making HTTP requests to a Patch Subset server. The HTTP request must use either the GET or POST method:

• If sent as a POST request the post body will be a single PatchRequest object encoded via CBOR.

• If sent as a GET request the client will include a single query parameter, request:
  the value is a single PatchRequest object encoded via CBOR and then base64url encoding [rfc4648].

For both POST and GET requests the path of the request identifies the specific font. All requests must be made over HTTPS.

The fields of the PatchRequest object should be set as follows:

• protocol_version: set to 0.

• accept_patch_format: set to the list of § 2.8 Patch Formats that this client is capable of decoding. Must contain at least one format.

• codepoints_have: set to exactly the set of codepoints that the current font subset contains data for. If the current font subset is an empty byte array this field is left unset. If the client has a codepoint ordering for this font then this field should not be set.

• codepoints_needed: set to the set of codepoints that the client wants to add to its font subset. If the client has a codepoint ordering for this font then this field should not be set.

• indices_have: encodes the set of additional codepoints that the current font subset contains data for. The codepoint values are transformed to indices by applying § 2.7 Codepoint Reordering to each codepoint value. If the client does not have a codepoint ordering for this font then this field should not be set.

• indices_needed: encodes the set of codepoints that the client wants to add to its font subset. The codepoint values are transformed to indices by applying § 2.7 Codepoint Reordering to each codepoint value. If the client does not have a codepoint ordering for this font then this field should not be set.

• axis_space_have: set to the current value of subset_axis_space saved in the state for this font.

• axis_space_needed: set to the intervals of each variable axis in the original font that the client wants to add to its font subset. If the client wants an entire axis from the original font then that axis should not be listed.

• ordering_checksum: If either of indices_have or indices_needed is set then this must be set to the current value of ordering_checksum saved in the state for this font.

• original_font_checksum: Set to saved value for original_font_checksum in the state for this font. If there is no saved value leave this field unset.

• base_checksum: Set to the checksum of the font subset byte array saved in the state for this font. See: § 2.6 Computing Checksums.

• connection_speed: Can be optionally set by the client to a value from § 2.9 Connection Speeds by finding the value that corresponds to the client’s average round trip time.

2.4.3. Handling PatchResponse

If a server is able to succsessfully process a PatchRequest it will respond with HTTP status code 200 and the body of the response will be a 4 byte magic number (0x49, 0x46, 0x54, 0x20) followed by a single PatchResponse object encoded via CBOR. The client should interpret and process the fields of the object as follows:

1. If field replacement is set then: the byte array in this field is a binary patch in the format specified by patch_format. Apply the binary patch to a base which is an empty byte array. Replace the saved font subset with the result of the patch application.

2. If field patch is set then: the byte array in this field is a binary patch in the format specified by patch_format. Apply the binary patch to the saved font subset. Replace the saved font subset with the result of the patch application.

3. If either replacement or patch is set then: compute the checksum of the font subset produced by the patch application in steps 1 or 2. If the computed checksum is not equal to patched_checksum this is a recoverable error. Follow the procedure in § 2.4.4 Client Side Checksum Mismatch. Otherwise update the saved original font checksum with the value in original_font_checksum.

4. If fields codepoint_ordering and ordering_checksum are set then update the saved codepoint ordering and checksum with the new values specified by these two fields. If neither replacement nor patch are set, then the client should resend the request that triggered this response but use the new codepoint ordering provided in this response.

5. If original_axis_space is set then update the saved original axis space with the value specified in this field.

6. If subset_axis_space is set then update the saved subset axis space with the value specified in this field.

2.4.4. Client Side Checksum Mismatch

If the the checksum of the font subset computed by the client does not match the patched_checksum in the server’s response then the client should:

1. Discard all currently saved state for this font.

2. Resend the request. Set the codepoints_needed field to the union of the codepoints in the discarded font subset and the set of code points the the previous request was trying to add.

2.5. Server: Responding to a PatchRequest

If the server receives a well formed PatchRequest over HTTPS that was populated according to the requirements in § 2.4.2 Extending the Font Subset then it should respond with HTTP status code 200. The first 4 bytes of the response must be set to 0x49, 0x46, 0x54, 0x20 ("IFT " encoded as ASCII) followed by a single PatchResponse object encoded via CBOR.

The path in the request identifies the specific font that a patch is desired for. From the request object the server can produce two codepoint sets:

1. Codepoints the client has: formed by the union of the codepoint sets specified by codepoints_have and indices_have. The indices in indices_have must be mapped to codepoints by the application of the codepoint reordering with a checksum matching ordering_checksum.

2. Codepoints the client needs: formed by the union of the codepoint sets specified by codepoints_needed and indices_needed. The indices in indices_needed must be mapped to codepoints by the application of the codepoint reordering with a checksum matching ordering_checksum.

Likewise, the server can produce two variable axis spaces:

1. Axis space the client has: provided by axis_space_have. If any axes in the font are not specified in axis_space_have then for those axes add their entire interval from the original font.

2. Axis space the client needs: provided by axis_space_needed. If any axes in the font are not specified in axis_space_needed then for those axes add their entire interval from the original font.

If the server does not recognize the codepoint ordering used by the client, it must respond with a response that will cause the client to update it’s codepoint ordering to one the server will recognize via the process described in § 2.4.3 Handling PatchResponse and not include any patch. That is the patch and replacement fields must not be set.

Otherwise when the response is applied by the client following the process in § 2.4.3 Handling PatchResponse to a font subset with checksum base_checksum it must result in an extended font subset:

• That contains data for at least the union of the set of codepoints needed and the sets of codepoints the client already has.

• That contains a variation axis space that covers at least the union of the axis space the client has and the axis space the client needs.

Additionally:

• The format of the patch in the either the patch or replace fields must be one of those listed in accept_patch_format.

• The value of original_font_checksum must be set to the checksum of the original font. The checksum value must computed by the procedure in § 2.6 Computing Checksums.

• If the set of codepoints the client has is empty the response must set the codepoint_ordering and ordering_checksum fields following § 2.7 Codepoint Reordering.

• If the set of codepoints the client has is empty and the original font has variation axes, the response must set the original_axis_space fields to the axis space covered by the original font.

• If patch or replacement fields are set and the original font has variation axes, the response must set the subset_axis_space field to the axis space covered by the font subset.

• If accept_patch_format contains any unrecognized patch formats the server should ignore the unrecognized ones. Likewise if connection_speed contains any unrecognized connection speeds the server should ignore the unrecognized ones.

Note: the server can optionally use the client’s provided connection speed to inform how many extra codepoints should be sent. For example on slower connections it may be more performant to send extra codepoints if they can prevent a future request from needing to be sent.

Note: the server can respond with either a patch or a replacement but should try to produce a patch where possible. Replacement’s should only be used in situations where the server is unable to recreate the client’s state in order to generate a patch against it.

Possible error responses:

• If the request is malformed the server may instead respond with http status code 400 to indicate an error.

• If the requested font is not recognized by the server it may respond with http status code 404 to indicate a not found error.

2.6. Computing Checksums

64 bit checksums of byte strings are computed using the fast hash algorithm. A python like pseudo code version of the algorithm is presented below:

# Constant values come fast hash: https://github.com/ztanml/fast-hash
SEED = 0x11743e80f437ffe6
M = 0x880355f21e6d1965

mix(value):
  value = value ^ (value >> 23)
  value = value * 0x2127599bf4325c37
  value = value ^ (value >> 47)
  return value

fast_hash(byte[] data):
  # When casting byte arrays into unsigned 64 bit integers the bytes are in little
  # endian order. That is the smallest index is the least significant byte.
  uint64 hash = SEED ^ (length(data) * M)
  for (i = 0; i <= length(data) - 8; i += 8)
    hash = (hash ^ mix((uint64) data[i:i+8])) * M

  remaining = length(data) % 8
  if not remaining:
    return mix(hash)

  uint64 last_value = (uint64) concat(data[length(data) - remaining:],
                                      [0] * (8 - remaining))
  return mix((hash ^ mix(last_value)) * M)

To ensure checksums are consistent across all platforms, all integers during the computation must be in little endian order.

Note: a C implementation of fast hash can be found here.

2.7. Codepoint Reordering

A codepoint reordering for a font defines a function which maps unicode codepoint values from the font to a continuous space of [0, number of codepoints in the font). This transformation is intended to reduce the cost of representing codepoint sets.

A codepoint ordering is encoded into a CompressedList. The list must contain all unicode codepoints that are supported by the font. The index of a particular unicode codepoint in the list is the new value for that codepoint.

A server is free to choose any codepoint ordering, but should try to pick one that will minimize the size of encoded codepoint sets for that font.

2.7.1. Codepoint Reordering Checksum

A checksum of a codepoint reordering can be computed as follows:

SEED = 0x11743e80f437ffe6
M = 0x880355f21e6d1965

mix(value):
  value = value ^ (value >> 23)
  value = value * 0x2127599bf4325c37
  value = value ^ (value >> 47)
  return value

fast_hash_ordering(uint64[] ordering):
  uint64 hash = SEED ^ (length(ordering) * 8 * M)
  for i in ordering:
    hash = (hash ^ mix(ordering[i])) * M

  return mix(hash)

To ensure checksums are consistent across all platforms, all integers during the computation must be in little endian order.

2.8. Patch Formats

The following patch formats may be used by the server to create binary diffs between a source file and a target file:

2.9. Connection Speeds

The following connection speed values can be used:

3. Range Request Incremental Transfer

The specification for range request based incremental transfer is currently being drafted and is located in a separate document: Incremental Font Transfer via Range Request

4. Declaring Incremental Fonts

CSS stylesheets (or HTML or SVG content using stylesheets) can specify that incremental font transfer can be used for a particular font URL by using the "supports" syntax in the 'src:' attribute of a font face:

@font-face {
  ...
  src: url(a_font.ttf) format(truetype supports incremental);
}

An incrementally transferred font must be in a raw format such as truetype or opentype.

5. Negotiating Incremental Font Transfer

For the initial request for a font the client should assume that the server supports the patch subset based method and send a PatchRequest via HTTP GET according to the requirements in § 2.4.2 Extending the Font Subset.

If the server does support the patch subset protocol it should respond appropriately following the instructions in the patch subset section. However, if the server does not support the patch subset protocol it should ignore the additional HTTP GET parameters and instead just begin sending the umodified font file.

If the client receives a response where the first 4 bytes of the body are 0x49, 0x46, 0x54, 0x20 that indicates it contains a PatchResponse. Follow the instructions in § 2.4.3 Handling PatchResponse to handle the response and all future requests should use the patch subset approach over POST.

Otherwise the client should follow the instructions in the Range Request section and all future extension requests should be sent according the the Range Request specificiation.

Privacy Considerations

No Privacy issues have been raised against this document

Security Considerations

No Security issues have been raised against this document