/
►
RFC 7932
Internet Engineering Task Force (IETF) J. Alakuijala
Request for Comments:
7932 Z. Szabadka
Category: Informational Google, Inc.
ISSN: 2070-1721 July 2016
Brotli Compressed Data Format
Abstract This specification defines a lossless compressed data format that
compresses data using a combination of the LZ77 algorithm and Huffman
coding, with efficiency comparable to the best currently available
general-purpose compression methods.
Status of This Memo This document is not an Internet Standards Track specification; it is
published for informational purposes.
This document is a product of the Internet Engineering Task Force
(IETF). It has been approved for publication by the Internet
Engineering Steering Group (IESG). Not all documents approved by the
IESG are a candidate for any level of Internet Standard; see
Section 2 of RFC 7841 .
Information about the current status of this document, any errata,
and how to provide feedback on it may be obtained at
http://www.rfc-editor.org/info/rfc7932 .
Copyright Notice Copyright (c) 2016 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(
http://trustee.ietf.org/license-info ) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
Table of Contents 1. Introduction ....................................................3
1.1. Purpose ....................................................3
1.2. Intended Audience ..........................................3
1.3. Scope ......................................................4
1.4. Compliance .................................................4
1.5. Definitions of Terms and Conventions Used ..................4
1.5.1. Packing into Bytes ..................................5
2. Compressed Representation Overview ..............................6
3. Compressed Representation of Prefix Codes ......................10
3.1. Introduction to Prefix Coding .............................10
3.2. Use of Prefix Coding in the Brotli Format .................11
3.3. Alphabet Sizes ............................................13
3.4. Simple Prefix Codes .......................................14
3.5. Complex Prefix Codes ......................................15
4. Encoding of Distances ..........................................17
5. Encoding of Literal Insertion Lengths and Copy Lengths .........19
6. Encoding of Block-Switch Commands ..............................22
7. Context Modeling ...............................................23
7.1. Context Modes and Context ID Lookup for Literals ..........23
7.2. Context ID for Distances ..................................26
7.3. Encoding of the Context Map ...............................26
8. Static Dictionary ..............................................28
9. Compressed Data Format .........................................31
9.1. Format of the Stream Header ...............................31
9.2. Format of the Meta-Block Header ...........................32
9.3. Format of the Meta-Block Data .............................35
10. Decoding Algorithm ............................................36
11. Considerations for Compressor Implementations .................38
11.1. Trivial Compressor .......................................39
11.2. Aligning Compressed Meta-Blocks to Byte Boundaries .......39
11.3. Creating Self-Contained Parts within the
Compressed Data ..........................................40
12. Security Considerations .......................................41
13. IANA Considerations ...........................................42
14. Informative References ........................................43
Appendix A . Static Dictionary Data ................................44
Appendix B . List of Word Transformations .........................124
Appendix C . Computing CRC-32 Check Values ........................127
Appendix D . Source Code ..........................................127
Acknowledgments ..................................................127
Authors' Addresses ...............................................128
1. Introduction
The purpose of this specification is to define a lossless compressed
data format that:
* is independent of CPU type, operating system, file system, and
character set; hence, it can be used for interchange.
* can be produced or consumed, even for an arbitrarily long,
sequentially presented input data stream, using only an a
priori bounded amount of intermediate storage; hence, it can be
used in data communications or similar structures, such as Unix
filters.
* compresses data with a compression ratio comparable to the best
currently available general-purpose compression methods, in
particular, considerably better than the gzip program.
* decompresses much faster than current LZMA implementations.
The data format defined by this specification does not attempt to:
* allow random access to compressed data.
* compress specialized data (e.g., raster graphics) as densely as
the best currently available specialized algorithms.
This document is the authoritative specification of the brotli
compressed data format. It defines the set of valid brotli
compressed data streams and a decoder algorithm that produces the
uncompressed data stream from a valid brotli compressed data stream.
1.2. Intended Audience This specification is intended for use by software implementers to
compress data into and/or decompress data from the brotli format.
The text of the specification assumes a basic background in
programming at the level of bits and other primitive data
representations. Familiarity with the technique of Huffman coding is
helpful but not required.
This specification uses (heavily) the notations and terminology
introduced in the DEFLATE format specification [
RFC1951 ]. For the
sake of completeness, we always include the whole text of the
relevant parts of
RFC 1951 ; therefore, familiarity with the DEFLATE
format is helpful but not required.
The compressed data format defined in this specification is an
integral part of the WOFF File Format 2.0 [WOFF2]; therefore, this
specification is also intended for implementers of WOFF 2.0
compressors and decompressors.
This document specifies a method for representing a sequence of bytes
as a (usually shorter) sequence of bits and a method for packing the
latter bit sequence into bytes.
1.4. Compliance Unless otherwise indicated below, a compliant decompressor must be
able to accept and decompress any data set that conforms to all the
specifications presented here. A compliant compressor must produce
data sets that conform to all the specifications presented here.
1.5. Definitions of Terms and Conventions Used Byte: 8 bits stored or transmitted as a unit (same as an octet). For
this specification, a byte is exactly 8 bits, even on machines that
store a character on a number of bits different from eight. See
below for the numbering of bits within a byte.
String: a sequence of arbitrary bytes.
Bytes stored within a computer do not have a "bit order", since they
are always treated as a unit. However, a byte considered as an
integer between 0 and 255 does have a most and least significant bit
(lsb), and since we write numbers with the most significant digit on
the left, we also write bytes with the most significant bit (msb) on
the left. In the diagrams below, we number the bits of a byte so
that bit 0 is the least significant bit, i.e., the bits are numbered:
+--------+
|76543210|
+--------+
Within a computer, a number may occupy multiple bytes. All multi-
byte numbers in the format described here are stored with the least
significant byte first (at the lower memory address). For example,
the decimal number 520 is stored as:
0 1
+--------+--------+
|00001000|00000010|
+--------+--------+
^ ^
| |
| + more significant byte = 2 * 256
+ less significant byte = 8
1.5.1. Packing into Bytes This document does not address the issue of the order in which bits
of a byte are transmitted on a bit-sequential medium, since the final
data format described here is byte rather than bit oriented.
However, we describe the compressed block format below as a sequence
of data elements of various bit lengths, not a sequence of bytes.
Therefore, we must specify how to pack these data elements into bytes
to form the final compressed byte sequence:
* Data elements are packed into bytes in order of increasing bit
number within the byte, i.e., starting with the least
significant bit of the byte.
* Data elements other than prefix codes are packed starting with
the least significant bit of the data element. These are
referred to here as "integer values" and are considered
unsigned.
* Prefix codes are packed starting with the most significant bit
of the code.
In other words, if one were to print out the compressed data as a
sequence of bytes, starting with the first byte at the *right* margin
and proceeding to the *left*, with the most significant bit of each
byte on the left as usual, one would be able to parse the result from
right to left, with fixed-width elements in the correct msb-to-lsb
order and prefix codes in bit-reversed order (i.e., with the first
bit of the code in the relative lsb position).
As an example, consider packing the following data elements into a
sequence of 3 bytes: 3-bit integer value 6, 4-bit integer value 2,
prefix code 110, prefix code 10, 12-bit integer value 3628.
byte 2 byte 1 byte 0
+--------+--------+--------+
|11100010|11000101|10010110|
+--------+--------+--------+
^ ^ ^ ^ ^
| | | | |
| | | | +------ integer value 6
| | | +---------- integer value 2
| | +-------------- prefix code 110
| +---------------- prefix code 10
+----------------------------- integer value 3628
2. Compressed Representation Overview A compressed data set consists of a header and a series of meta-
blocks. Each meta-block decompresses to a sequence of 0 to
16,777,216 (16 MiB) uncompressed bytes. The final uncompressed data
is the concatenation of the uncompressed sequences from each meta-
block.
The header contains the size of the sliding window that was used
during compression. The decompressor must retain at least that
amount of uncompressed data prior to the current position in the
stream, in order to be able to decompress what follows. The sliding
window size is a power of two, minus 16, where the power is in the
range of 10 to 24. The possible sliding window sizes range from 1
KiB - 16 B to 16 MiB - 16 B.
Each meta-block is compressed using a combination of the LZ77
algorithm (Lempel-Ziv 1977, [LZ77]) and Huffman coding. The result
of Huffman coding is referred to here as a "prefix code". The prefix
codes for each meta-block are independent of those for previous or
subsequent meta-blocks; the LZ77 algorithm may use a reference to a
duplicated string occurring in a previous meta-block, up to the
sliding window size of uncompressed bytes before. In addition, in
the brotli format, a string reference may instead refer to a static
dictionary entry.
Each meta-block consists of two parts: a meta-block header that
describes the representation of the compressed data part and a
compressed data part. The compressed data consists of a series of
commands. Each command consists of two parts: a sequence of literal
bytes (of strings that have not been detected as duplicated within
the sliding window) and a pointer to a duplicated string, which is
represented as a pair <length, backward distance>. There can be zero
literal bytes in the command. The minimum length of the string to be
contains the number of uncompressed bytes and the indication that the
meta-block is uncompressed. An uncompressed meta-block cannot be the
last meta-block.
A meta-block may also be empty, which generates no uncompressed data
at all. An empty meta-block may contain metadata information as
bytes starting on byte boundaries, which are not part of either the
sliding window or the uncompressed data. Thus, these metadata bytes
cannot be used to create matching strings in subsequent meta-blocks
and are not used as context bytes for literals.
3. Compressed Representation of Prefix Codes
3.1. Introduction to Prefix Coding Prefix coding represents symbols from an a priori known alphabet by
bit sequences (codes), one code for each symbol, in a manner such
that different symbols may be represented by bit sequences of
different lengths, but a parser can always parse an encoded string
unambiguously symbol-by-symbol.
We define a prefix code in terms of a binary tree in which the two
edges descending from each non-leaf node are labeled 0 and 1, and in
which the leaf nodes correspond one-for-one with (are labeled with)
the symbols of the alphabet. The code for a symbol is the sequence
of 0's and 1's on the edges leading from the root to the leaf labeled
with that symbol. For example:
/\ Symbol Code
0 1 ------ ----
/ \ A 00
/\ B B 1
0 1 C 011
/ \ D 010
A /\
0 1
/ \
D C
A parser can decode the next symbol from the compressed stream by
walking down the tree from the root, at each step choosing the edge
corresponding to the next compressed data bit.
Given an alphabet with known symbol frequencies, the Huffman
algorithm allows the construction of an optimal prefix code (one that
represents strings with those symbol frequencies using the fewest
bits of any possible prefix codes for that alphabet). Such a prefix
code is called a Huffman code. (See [HUFFMAN] for additional
information on Huffman codes.)
In the brotli format, note that the prefix codes for the various
alphabets must not exceed certain maximum code lengths. This
constraint complicates the algorithm for computing code lengths from
symbol frequencies. Again, see [HUFFMAN] for details.
3.2. Use of Prefix Coding in the Brotli Format The prefix codes used for each alphabet in the brotli format are
canonical prefix codes, which have two additional rules:
* All codes of a given bit length have lexicographically
consecutive values, in the same order as the symbols they
represent;
* Shorter codes lexicographically precede longer codes.
We could recode the example above to follow this rule as follows,
assuming that the order of the alphabet is ABCD:
Symbol Code
------ ----
A 10
B 0
C 110
D 111
That is, 0 precedes 10, which precedes 11x, and 110 and 111 are
lexicographically consecutive.
Given this rule, we can define the canonical prefix code for an
alphabet just by giving the bit lengths of the codes for each symbol
of the alphabet in order; this is sufficient to determine the actual
codes. In our example, the code is completely defined by the
sequence of bit lengths (2, 1, 3, 3). The following algorithm
generates the codes as integers, intended to be read from most to
least significant bit. The code lengths are initially in
tree[I].Len; the codes are produced in tree[I].Code.
1) Count the number of codes for each code length. Let
bl_count[N] be the number of codes of length N, N >= 1.
Step 3 produces the following code values:
Symbol Length Code
------ ------ ----
A 3 010
B 3 011
C 3 100
D 3 101
E 3 110
F 2 00
G 4 1110
H 4 1111
3.3. Alphabet Sizes Prefix codes are used for different purposes in the brotli format,
and each purpose has a different alphabet size. For literal codes,
the alphabet size is 256. For insert-and-copy length codes, the
alphabet size is 704. For block count codes, the alphabet size is
26. For distance codes, block type codes, and the prefix codes used
in compressing the context map, the alphabet size is dynamic and is
based on parameters defined in later sections. The following table
summarizes the alphabet sizes for the various prefix codes and the
sections of this document in which they are defined.
+-----------------+-------------------------+------------+
| Prefix Code | Alphabet Size | Definition |
+-----------------+-------------------------+------------+
| literal | 256 | |
+-----------------+-------------------------+------------+
| distance | 16 + NDIRECT + |
Section 4 |
| | (48 << NPOSTFIX) | |
+-----------------+-------------------------+------------+
| insert-and-copy | 704 |
Section 5 |
| length | | |
+-----------------+-------------------------+------------+
| block count | 26 |
Section 6 |
+-----------------+-------------------------+------------+
| block type | NBLTYPESx + 2, |
Section 6 |
| | (where x is I, L, or D) | |
+-----------------+-------------------------+------------+
| context map | NTREESx + RLEMAXx |
Section 7 |
| | (where x is L or D) | |
+-----------------+-------------------------+------------+
3.4. Simple Prefix Codes The first two bits of the compressed representation of each prefix
code distinguish between simple and complex prefix codes. If this
value is 1, then a simple prefix code follows as described in this
section. Otherwise, a complex prefix code follows as described in
Section 3.5 .
A simple prefix code can have up to four symbols with non-zero code
length. The format of the simple prefix code is as follows:
2 bits: value of 1 indicates a simple prefix code
2 bits: NSYM - 1, where NSYM = number of symbols coded
NSYM symbols, each encoded using ALPHABET_BITS bits
1 bit: tree-select, present only for NSYM = 4
The value of ALPHABET_BITS depends on the alphabet of the prefix
code: it is the smallest number of bits that can represent all
symbols in the alphabet. For example, for the alphabet of literal
bytes, ALPHABET_BITS is 8. The value of each of the NSYM symbols
above is the value of the ALPHABET_BITS width integer value. If the
integer value is greater than or equal to the alphabet size, or the
value is identical to a previous value, then the stream should be
rejected as invalid.
Note that the NSYM symbols may not be presented in sorted order.
Prefix codes of the same bit length must be assigned to the symbols
in sorted order.
The (non-zero) code lengths of the symbols can be reconstructed as
follows:
* if NSYM = 1, the code length for the one symbol is zero -- when
encoding this symbol in the compressed data stream using this
prefix code, no actual bits are emitted. Similarly, when
decoding a symbol using this prefix code, no bits are read and
the one symbol is returned.
* if NSYM = 2, both symbols have code length 1.
* if NSYM = 3, the code lengths for the symbols are 1, 2, 2 in
the order they appear in the representation of the simple
prefix code.
* if NSYM = 4, the code lengths (in order of symbols decoded)
depend on the tree-select bit: 2, 2, 2, 2 (tree-select bit 0),
or 1, 2, 3, 3 (tree-select bit 1).
3.5. Complex Prefix Codes A complex prefix code is a canonical prefix code, defined by the
sequence of code lengths, as discussed in
Section 3.2 . For even
greater compactness, the code length sequences themselves are
compressed using a prefix code. The alphabet for code lengths is as
follows:
0..15: Represent code lengths of 0..15
16: Copy the previous non-zero code length 3..6 times.
The next 2 bits indicate repeat length
(0 = 3, ... , 3 = 6)
If this is the first code length, or all previous
code lengths are zero, a code length of 8 is
repeated 3..6 times.
A repeated code length code of 16 modifies the
repeat count of the previous one as follows:
repeat count = (4 * (repeat count - 2)) +
(3..6 on the next 2 bits)
Example: Codes 7, 16 (+2 bits 11), 16 (+2 bits 10)
will expand to 22 code lengths of 7
(1 + 4 * (6 - 2) + 5)
17: Repeat a code length of 0 for 3..10 times.
The next 3 bits indicate repeat length
(0 = 3, ... , 7 = 10)
A repeated code length code of 17 modifies the
repeat count of the previous one as follows:
repeat count = (8 * (repeat count - 2)) +
(3..10 on the next 3 bits)
Note that a code of 16 that follows an immediately preceding 16
modifies the previous repeat count, which becomes the new repeat
count. The same is true for a 17 following a 17. A sequence of
three or more 16 codes in a row or three of more 17 codes in a row is
possible, modifying the count each time. Only the final repeat count
is used. The modification only applies if the same code follows. A
16 repeat does not modify an immediately preceding 17 count nor vice
versa.
A code length of 0 indicates that the corresponding symbol in the
alphabet will not occur in the compressed data, and it should not
participate in the prefix code construction algorithm given earlier.
A complex prefix code must have at least two non-zero code lengths.
all literal values with equal probability. In this case the
single symbol is 16, which repeats the previous length. The
previous length is taken to be 8 before any code length code
lengths are read.
o Sequence of code length symbols, which is at most the size of the
alphabet, encoded using the code length prefix code. Any trailing
0 or 17 must be omitted, i.e., the last encoded code length symbol
must be between 1 and 16. The sum of (32768 >> code length) over
all the non-zero code lengths in the alphabet, including those
encoded using repeat code(s) of 16, must be equal to 32768. If
the number of times to repeat the previous length or repeat a zero
length would result in more lengths in total than the number of
symbols in the alphabet, then the stream should be rejected as
invalid.
4. Encoding of Distances As described in
Section 2 , one component of a compressed meta-block
is a sequence of backward distances. In this section, we provide the
details to the encoding of distances.
Each distance in the compressed data part of a meta-block is
represented with a pair <distance code, extra bits>. The distance
code and the extra bits are encoded back-to-back, the distance code
is encoded using a prefix code over the distance alphabet, while the
extra bits value is encoded as a fixed-width integer value. The
number of extra bits can be 0..24, and it is dependent on the
distance code.
To convert a distance code and associated extra bits to a backward
distance, we need the sequence of past distances and two additional
parameters: the number of "postfix bits", denoted by NPOSTFIX (0..3),
and the number of direct distance codes, denoted by NDIRECT (0..120).
Both of these parameters are encoded in the meta-block header. We
will also use the following derived parameter:
POSTFIX_MASK = (1 << NPOSTFIX) - 1
The first 16 distance symbols are special symbols that reference past
distances as follows:
0: last distance
1: second-to-last distance
2: third-to-last distance
3: fourth-to-last distance
4: last distance - 1
5: last distance + 1
6: last distance - 2
7: last distance + 2
8: last distance - 3
9: last distance + 3
10: second-to-last distance - 1
11: second-to-last distance + 1
12: second-to-last distance - 2
13: second-to-last distance + 2
14: second-to-last distance - 3
15: second-to-last distance + 3
The ring buffer of the four last distances is initialized by the
values 16, 15, 11, and 4 (i.e., the fourth-to-last is set to 16, the
third-to-last to 15, the second-to-last to 11, and the last distance
to 4) at the beginning of the *stream* (as opposed to the beginning
of the meta-block), and it is not reset at meta-block boundaries.
When a distance symbol 0 appears, the distance it represents (i.e.,
the last distance in the sequence of distances) is not pushed to the
ring buffer of last distances; in other words, the expression
"second-to-last distance" means the second-to-last distance that was
not represented by a 0 distance symbol (and similar for "third-to-
last distance" and "fourth-to-last distance"). Similarly, distances
that represent static dictionary words (see
Section 8 ) are not pushed
to the ring buffer of last distances.
If a special distance symbol resolves to a zero or negative value,
the stream should be rejected as invalid.
If NDIRECT is greater than zero, then the next NDIRECT distance
symbols, from 16 to 15 + NDIRECT, represent distances from 1 to
NDIRECT. Neither the special distance symbols nor the NDIRECT direct
distance symbols are followed by any extra bits.
Distance symbols 16 + NDIRECT and greater all have extra bits, where
the number of extra bits for a distance symbol "dcode" is given by
the following formula:
ndistbits = 1 + ((dcode - NDIRECT - 16) >> (NPOSTFIX + 1))
The maximum number of extra bits is 24; therefore, the size of the
distance symbol alphabet is (16 + NDIRECT + (48 << NPOSTFIX)).
Given a distance symbol "dcode" (>= 16 + NDIRECT), and extra bits
"dextra", the backward distance is given by the following formula:
hcode = (dcode - NDIRECT - 16) >> NPOSTFIX
lcode = (dcode - NDIRECT - 16) & POSTFIX_MASK
offset = ((2 + (hcode & 1)) << ndistbits) - 4
distance = ((offset + dextra) << NPOSTFIX) + lcode + NDIRECT + 1
5. Encoding of Literal Insertion Lengths and Copy Lengths As described in
Section 2 , the literal insertion lengths and backward
copy lengths are encoded using a single prefix code. This section
provides the details to this encoding.
Each <insertion length, copy length> pair in the compressed data part
of a meta-block is represented with the following triplet:
<insert-and-copy length code, insert extra bits, copy extra bits>
The insert-and-copy length code, the insert extra bits, and the copy
extra bits are encoded back-to-back, the insert-and-copy length code
is encoded using a prefix code over the insert-and-copy length code
alphabet, while the extra bits values are encoded as fixed-width
integer values. The number of insert and copy extra bits can be
0..24, and they are dependent on the insert-and-copy length code.
Some of the insert-and-copy length codes also express the fact that
the distance symbol of the distance in the same command is 0, i.e.,
the distance component of the command is the same as that of the
previous command. In this case, the distance code and extra bits for
the distance are omitted from the compressed data stream.
6. Encoding of Block-Switch Commands As described in
Section 2 , a block-switch command is a pair <block
type, block count>. These are encoded in the compressed data part of
the meta-block, right before the start of each new block of a
particular block category.
Each block type in the compressed data is represented with a block
type code, encoded using a prefix code over the block type code
alphabet. A block type symbol 0 means that the new block type is the
same as the type of the previous block from the same block category,
i.e., the block type that preceded the current type, while a block
type symbol 1 means that the new block type equals the current block
type plus one. If the current block type is the maximal possible,
then a block type symbol of 1 results in wrapping to a new block type
of 0. Block type symbols 2..257 represent block types 0..255,
respectively. The previous and current block types are initialized
to 1 and 0, respectively, at the end of the meta-block header.
Since the first block type of each block category is 0, the block
type of the first block-switch command is not encoded in the
compressed data. If a block category has only one block type, the
block count of the first block-switch command is also omitted from
the compressed data; otherwise, it is encoded in the meta-block
header.
Since the end of the meta-block is detected by the number of
uncompressed bytes produced, the block counts for any of the three
categories need not count down to exactly zero at the end of the
meta-block.
The number of different block types in each block category, denoted
by NBLTYPESL, NBLTYPESI, and NBLTYPESD for literals, insert-and-copy
lengths, and distances, respectively, is encoded in the meta-block
header, and it must equal to the largest block type plus one in that
block category. In other words, the set of literal, insert-and-copy
length, and distance block types must be [0..NBLTYPESL-1],
[0..NBLTYPESI-1], and [0..NBLTYPESD-1], respectively. From this it
follows that the alphabet size of literal, insert-and-copy length,
and distance block type codes is NBLTYPESL + 2, NBLTYPESI + 2, and
NBLTYPESD + 2, respectively.
Each block count in the compressed data is represented with a pair
<block count code, extra bits>. The block count code and the extra
bits are encoded back-to-back, the block count code is encoded using
a prefix code over the block count code alphabet, while the extra
bits value is encoded as a fixed-width integer value. The number of
extra bits can be 0..24, and it is dependent on the block count code.
The symbols of the block count code alphabet along with the number of
extra bits and the range of block counts are as follows:
Extra Extra Extra
Code Bits Lengths Code Bits Lengths Code Bits Lengths
---- ---- ------- ---- ---- ------- ---- ---- -------
0 2 1..4 9 4 65..80 18 7 369..496
1 2 5..8 10 4 81..96 19 8 497..752
2 2 9..12 11 4 97..112 20 9 753..1264
3 2 13..16 12 5 113..144 21 10 1265..2288
4 3 17..24 13 5 145..176 22 11 2289..4336
5 3 25..32 14 5 177..208 23 12 4337..8432
6 3 33..40 15 5 209..240 24 13 8433..16624
7 3 41..48 16 6 241..304 25 24 16625..16793840
8 4 49..64 17 6 305..368
The first block-switch command of each block category is special in
the sense that it is encoded in the meta-block header, and as
described earlier, the block type code is omitted since it is an
implicit zero.
7. Context Modeling As described in
Section 2 , the prefix tree used to encode a literal
byte or a distance code depends on the block type and the context ID.
This section specifies how to compute the context ID for a particular
literal and distance code and how to encode the context map that maps
a <block type, context ID> pair to the index of a prefix code in the
array of literal and distance prefix codes.
7.1. Context Modes and Context ID Lookup for Literals The context for encoding the next literal is defined by the last two
bytes in the stream (p1, p2, where p1 is the most recent byte),
regardless of whether these bytes are produced by uncompressed meta-
blocks, backward references, static dictionary references, or by
literal insertions. At the start of the stream, p1 and p2 are
initialized to zero.
There are four methods, called context modes, to compute the Context
ID:
* LSB6, where the Context ID is the value of six least
significant bits of p1,
* MSB6, where the Context ID is the value of six most significant
bits of p1,
Lut2 :=
0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7
The lengths and the CRC-32 check values (see
Appendix C ) of each of
these tables as a sequence of bytes are as follows:
Table Length CRC-32
----- ------ ------
Lut0 256 0x8e91efb7
Lut1 256 0xd01a32f4
Lut2 256 0x0dd7a0d6
Given p1 is the last uncompressed byte and p2 is the second-to-last
uncompressed byte, the context IDs can be computed as follows:
For LSB6: Context ID = p1 & 0x3f
For MSB6: Context ID = p1 >> 2
For UTF8: Context ID = Lut0[p1] | Lut1[p2]
For Signed: Context ID = (Lut2[p1] << 3) | Lut2[p2]
From the lookup tables defined above and the operations to compute
the context IDs, we can see that context IDs for literals are in the
range of 0..63.
The context modes LSB6, MSB6, UTF8, and Signed are denoted by
integers 0, 1, 2, 3.
A context mode is defined for each literal block type and they are
stored in a consecutive array of bits in the meta-block header,
always two bits per block type.
7.2. Context ID for Distances The context for encoding a distance code is defined by the copy
length corresponding to the distance. The context IDs are 0, 1, 2,
and 3 for copy lengths 2, 3, 4, and more than 4, respectively.
7.3. Encoding of the Context Map There are two context maps, one for literals and one for distances.
The size of the context map is 64 * NBLTYPESL for literals, and 4 *
NBLTYPESD for distances. Each value in the context map is an integer
between 0 and 255, indicating the index of the prefix code to be used
when encoding the next literal or distance.
The context maps are two-dimensional matrices, encoded as one-
dimensional arrays:
CMAPL[0..(64 * NBLTYPESL - 1)]
CMAPD[0..(4 * NBLTYPESD - 1)]
The index of the prefix code for encoding a literal or distance code
with block type, BTYPE_x, and context ID, CIDx, is:
index of literal prefix code = CMAPL[64 * BTYPE_L + CIDL]
index of distance prefix code = CMAPD[4 * BTYPE_D + CIDD]
The values of the context map are encoded with the combination of run
length encoding for zero values and prefix coding. Let RLEMAX denote
the number of run length codes and NTREES denote the maximum value in
the context map plus one. NTREES must equal the number of different
values in the context map; in other words, the different values in
the context map must be the [0..NTREES-1] interval. The alphabet of
the prefix code has the following RLEMAX + NTREES symbols:
0: value zero
1: repeat a zero 2 to 3 times, read 1 bit for repeat length
2: repeat a zero 4 to 7 times, read 2 bits for repeat length
...
RLEMAX: repeat a zero (1 << RLEMAX) to (1 << (RLEMAX+1))-1
times, read RLEMAX bits for repeat length
RLEMAX + 1: value 1
...
RLEMAX + NTREES - 1: value NTREES - 1
If RLEMAX = 0, the run length coding is not used and the symbols of
the alphabet are directly the values in the context map. We can now
define the format of the context map (the same format is used for
literal and distance context maps):
1..5 bits: RLEMAX, 0 is encoded with one 0 bit, and values 1..16
are encoded with bit pattern xxxx1 (so 01001 is 5)
Prefix code with alphabet size NTREES + RLEMAX
Context map size values encoded with the above prefix code and run
length coding for zero values. If a run length would result in
more lengths in total than the size of the context map, then
the stream should be rejected as invalid.
1 bit: IMTF bit, if set, we do an inverse move-to-front transform
on the values in the context map to get the prefix code
indexes.
Note that RLEMAX may be larger than the value necessary to represent
the longest sequence of zero values. Also, the NTREES value is
encoded right before the context map as described in
Section 9.2 .
We define the inverse move-to-front transform used in this
specification by the following C language function:
void InverseMoveToFrontTransform(uint8_t* v, int v_len) {
uint8_t mtf[256];
int i;
for (i = 0; i < 256; ++i) {
mtf[i] = (uint8_t)i;
}
for (i = 0; i < v_len; ++i) {
uint8_t index = v[i];
uint8_t value = mtf[index];
v[i] = value;
for (; index; --index) {
mtf[index] = mtf[index - 1];
}
mtf[0] = value;
}
}
Note that the inverse move-to-front transform will not produce values
outside the [0..NTREES-1] interval.
8. Static Dictionary At any given point during decoding the compressed data, a reference
to a duplicated string in the uncompressed data produced so far has a
maximum backward distance value, which is the minimum of the window
size and the number of uncompressed bytes produced. However,
decoding a distance from the compressed stream, as described in
Section 4 , can produce distances that are greater than this maximum
allowed value. In this case, the distance is treated as a reference
to a word in the static dictionary given in
Appendix A . The copy
length for a static dictionary reference must be between 4 and 24.
The static dictionary has three parts:
* DICT[0..DICTSIZE], an array of bytes
* DOFFSET[0..24], an array of byte-offset values for each length
* NDBITS[0..24], an array of bit-depth values for each length
The number of static dictionary words for a given length is:
NWORDS[length] = 0 (if length < 4)
NWORDS[length] = (1 << NDBITS[length]) (if length >= 4)
DOFFSET and DICTSIZE are defined by the following recursion:
DOFFSET[0] = 0
DOFFSET[length + 1] = DOFFSET[length] + length * NWORDS[length]
DICTSIZE = DOFFSET[24] + 24 * NWORDS[24]
The offset of a word within the DICT array for a given length and
index is:
offset(length, index) = DOFFSET[length] + index * length
Each static dictionary word has 121 different forms, given by
applying a word transformation to a base word in the DICT array. The
list of word transformations is given in
Appendix B . The static
dictionary word for a <length, distance> pair can be reconstructed as
follows:
word_id = distance - (max allowed distance + 1)
index = word_id % NWORDS[length]
base_word = DICT[offset(length, index)..offset(length, index+1)-1]
transform_id = word_id >> NDBITS[length]
The string copied to the uncompressed stream is computed by applying
the transformation to the base dictionary word. If transform_id is
greater than 120, or the length is smaller than 4 or greater than 24,
then the compressed stream should be rejected as invalid.
We define the FermentFirst and FermentAll transforms used in this
specification by the following C language functions:
int Ferment(uint8_t* word, int word_len, int pos) {
if (word[pos] < 192) {
if (word[pos] >= 97 and word[pos] <= 122) {
word[pos] = word[pos] ^ 32;
}
return 1;
} else if (word[pos] < 224) {
if (pos + 1 < word_len) {
word[pos + 1] = word[pos + 1] ^ 32;
}
return 2;
} else {
if (pos + 2 < word_len) {
word[pos + 2] = word[pos + 2] ^ 5;
}
return 3;
}
}
void FermentFirst(uint8_t* word, int word_len) {
if (word_len > 0) {
Ferment(word, word_len, 0);
}
}
void FermentAll(uint8_t* word, int word_len) {
int i = 0;
while (i < word_len) {
i += Ferment(word, word_len, i);
}
}
Appendix B contains the list of transformations by specifying the
prefix, elementary transform and suffix components of each of them.
Note that the OmitFirst8 elementary transform is not used in the list
of transformations. The strings in
Appendix B are in C-string format
with respect to escape (backslash) characters.
The maximum number of additional bytes that a transform may add to a
base word is 13. Since the largest base word is 24 bytes long, a
buffer of 38 bytes is sufficient to store any transformed words
(counting a terminating zero byte).
9. Compressed Data Format In this section, we describe the format of the compressed data set in
terms of the format of the individual data items described in the
previous sections.
9.1. Format of the Stream Header The stream header has only the following one field:
1..7 bits: WBITS, a value in the range 10..24, encoded with the
following variable-length code (as it appears in the
compressed data, where the bits are parsed from right
to left):
Value Bit Pattern
----- -----------
10 0100001
11 0110001
12 1000001
13 1010001
14 1100001
15 1110001
16 0
17 0000001
18 0011
19 0101
20 0111
21 1001
22 1011
23 1101
24 1111
Note that bit pattern 0010001 is invalid and must not
be used.
The size of the sliding window, which is the maximum value of any
non-dictionary reference backward distance, is given by the following
formula:
window size = (1 << WBITS) - 16
9.2. Format of the Meta-Block Header A compliant compressed data set has at least one meta-block. Each
meta-block contains a header with information about the uncompressed
length of the meta-block, and a bit signaling if the meta-block is
the last one. The format of the meta-block header is the following:
1 bit: ISLAST, set to 1 if this is the last meta-block
1 bit: ISLASTEMPTY, if set to 1, the meta-block is empty; this
field is only present if ISLAST bit is set -- if it is 1,
then the meta-block and the brotli stream ends at that
bit, with any remaining bits in the last byte of the
compressed stream filled with zeros (if the fill bits are
not zero, then the stream should be rejected as invalid)
2 bits: MNIBBLES, number of nibbles to represent the uncompressed
length, encoded with the following fixed-length code:
Value Bit Pattern
----- -----------
0 11
4 00
5 01
6 10
If MNIBBLES is 0, the meta-block is empty, i.e., it does
not generate any uncompressed data. In this case, the
rest of the meta-block has the following format:
1 bit: reserved, must be zero
2 bits: MSKIPBYTES, number of bytes to represent
metadata length
MSKIPBYTES * 8 bits: MSKIPLEN - 1, where MSKIPLEN is
the number of metadata bytes; this field is
only present if MSKIPBYTES is positive;
otherwise, MSKIPLEN is 0 (if MSKIPBYTES is
greater than 1, and the last byte is all
zeros, then the stream should be rejected as
invalid)
0..7 bits: fill bits until the next byte boundary,
must be all zeros
MSKIPLEN bytes of metadata, not part of the
uncompressed data or the sliding window
Block count code + extra bits for first insert-and-copy block
count, appears only if NBLTYPESI >= 2
1..11 bits: NBLTYPESD, number of distance block types, encoded
with the same variable-length code as above
Prefix code over the block type code alphabet for distance
block types, appears only if NBLTYPESD >= 2
Prefix code over the block count code alphabet for distance
block counts, appears only if NBLTYPESD >= 2
Block count code + extra bits for first distance block count,
appears only if NBLTYPESD >= 2
2 bits: NPOSTFIX, parameter used in the distance coding
4 bits: four most significant bits of NDIRECT, to get the actual
value of the parameter NDIRECT, left-shift this four-bit
number by NPOSTFIX bits
NBLTYPESL * 2 bits: context mode for each literal block type
1..11 bits: NTREESL, number of literal prefix trees, encoded with
the same variable-length code as NBLTYPESL
Literal context map, encoded as described in
Section 7.3 ,
appears only if NTREESL >= 2; otherwise, the context map has
only zero values
1..11 bits: NTREESD, number of distance prefix trees, encoded with
the same variable-length code as NBLTYPESD
Distance context map, encoded as described in
Section 7.3 ,
appears only if NTREESD >= 2; otherwise, the context map has
only zero values
NTREESL prefix codes for literals
NBLTYPESI prefix codes for insert-and-copy lengths
NTREESD prefix codes for distances
9.3. Format of the Meta-Block Data The compressed data part of a meta-block consists of a series of
commands. Each command has the following format:
Block type code for next insert-and-copy block type, appears only
if NBLTYPESI >= 2 and the previous insert-and-copy block count
is zero
Block count code + extra bits for next insert-and-copy block
count, appears only if NBLTYPESI >= 2 and the previous insert-
and-copy block count is zero
Insert-and-copy length, encoded as in
Section 5 , using the insert-
and-copy length prefix code with the current insert-and-copy
block type index
Insert length number of literals, with the following format:
Block type code for next literal block type, appears only if
NBLTYPESL >= 2 and the previous literal block count is zero
Block count code + extra bits for next literal block count,
appears only if NBLTYPESL >= 2 and the previous literal
block count is zero
Next byte of the uncompressed data, encoded with the literal
prefix code with the index determined by the previous two
bytes of the uncompressed data, the current literal block
type, and the context map, as described in
Section 7.3 Block type code for next distance block type, appears only if
NBLTYPESD >= 2 and the previous distance block count is zero
Block count code + extra bits for next distance block count,
appears only if NBLTYPESD >= 2 and the previous distance block
count is zero
Distance code, encoded as in
Section 4 , using the distance prefix
code with the index determined by the copy length, the current
distance block type, and the distance context map, as described
in
Section 7.3 , appears only if the distance code is not an
implicit 0, as indicated by the insert-and-copy length code
The number of commands in the meta-block is such that the sum of the
uncompressed bytes produced (i.e., the number of literals inserted
plus the number of bytes copied from past data or generated from the
static dictionary) over all the commands gives the uncompressed
length, MLEN encoded in the meta-block header.
If the total number of uncompressed bytes produced after the insert
part of the last command equals MLEN, then the copy length of the
last command is ignored and will not produce any uncompressed output.
In this case, the copy length of the last command can have any value.
In any other case, if the number of literals to insert, the copy
length, or the resulting dictionary word length would cause MLEN to
be exceeded, then the stream should be rejected as invalid.
If the last command of the last non-empty meta-block does not end on
a byte boundary, the unused bits in the last byte must be zeros.
10. Decoding Algorithm The decoding algorithm that produces the uncompressed data is as
follows:
read window size
do
read ISLAST bit
if ISLAST
read ISLASTEMPTY bit
if ISLASTEMPTY
break from loop
read MNIBBLES
if MNIBBLES is zero
verify reserved bit is zero
read MSKIPLEN
skip any bits up to the next byte boundary
skip MSKIPLEN bytes
continue to the next meta-block
else
read MLEN
if not ISLAST
read ISUNCOMPRESSED bit
if ISUNCOMPRESSED
skip any bits up to the next byte boundary
copy MLEN bytes of compressed data as literals
continue to the next meta-block
if distance code is implicit zero from insert-and-copy code
set backward distance to the last distance
else
if BLEN_D is zero
read block type using HTREE_BTYPE_D and set BTYPE_D
save previous block type
read block count using HTREE_BLEN_D and set BLEN_D
decrement BLEN_D
compute context ID, CIDD from CLEN
read distance code using HTREED[CMAPD[4*BTYPE_D + CIDD]]
compute distance by distance short code substitution
if distance code is not zero,
and distance is not a static dictionary reference,
push distance to the ring buffer of last distances
if distance is less than the max allowed distance plus one
move backwards distance bytes in the uncompressed data,
and copy CLEN bytes from this position to
the uncompressed stream
else
look up the static dictionary word, transform the word as
directed, and copy the result to the uncompressed stream
while number of uncompressed bytes for this meta-block < MLEN
while not ISLAST
If the stream ends before the completion of the last meta-block, then
the stream should be rejected as invalid.
Note that a duplicated string reference may refer to a string in a
previous meta-block, i.e., the backward distance may cross one or
more meta-block boundaries. However, a backward copy distance will
not refer past the beginning of the uncompressed stream or the window
size; any such distance is interpreted as a reference to a static
dictionary word. Also, note that the referenced string may overlap
the current position, for example, if the last 2 bytes decoded have
values X and Y, a string reference with <length = 5, distance = 2>
adds X,Y,X,Y,X to the uncompressed stream.
11. Considerations for Compressor Implementations Since the intent of this document is to define the brotli compressed
data format without reference to any particular compression
algorithm, the material in this section is not part of the definition
of the format, and a compressor need not follow it in order to be
compliant.
11.1. Trivial Compressor In this section, we present a very simple algorithm that produces a
valid brotli stream representing an arbitrary sequence of
uncompressed bytes in the form of the following C++ language
function.
string BrotliCompressTrivial(const string& u) {
if (u.empty()) {
return string(1, 6);
}
int i;
string c;
c.append(1, 12);
for (i = 0; i + 65535 < u.size(); i += 65536) {
c.append(1, 248);
c.append(1, 255);
c.append(1, 15);
c.append(&u[i], 65536);
}
if (i < u.size()) {
int r = u.size() - i - 1;
c.append(1, (r & 31) << 3);
c.append(1, r >> 5);
c.append(1, 8 + (r >> 13));
c.append(&u[i], r + 1);
}
c.append(1, 3);
return c;
}
Note that this simple algorithm does not actually compress data, that
is, the brotli representation will always be bigger than the
original, but it shows that every sequence of N uncompressed bytes
can be represented with a valid brotli stream that is not longer than
N + (3 * (N >> 16) + 5) bytes.
11.2. Aligning Compressed Meta-Blocks to Byte Boundaries As described in
Section 9 , only those meta-blocks that immediately
follow an uncompressed meta-block or a metadata meta-block are
guaranteed to start on a byte boundary. In some applications, it
might be required that every non-metadata meta-block starts on a byte
boundary. This can be achieved by appending an empty metadata meta-
block after every non-metadata meta-block that does not end on a byte
boundary.
11.3. Creating Self-Contained Parts within the Compressed Data In some encoder implementations, it might be required to make a
sequence of bytes within a brotli stream self-contained, that is,
such that they can be decompressed independently from previous parts
of the compressed data. This is a useful feature for three reasons.
First, if a large compressed file is damaged, it is possible to
recover some of the file after the damage. Second, it is useful when
doing differential transfer of compressed data. If a sequence of
uncompressed bytes is unchanged and compressed independently from
previous data, then the compressed representation may also be
unchanged and can therefore be transferred very cheaply. Third, if
sequences of uncompressed bytes are compressed independently, it
allows for parallel compression of these byte sequences within the
same file, in addition to parallel compression of multiple files.
Given two sequences of uncompressed bytes, U0 and U1, we will now
describe how to create two sequences of compressed bytes, C0 and C1,
such that the concatenation of C0 and C1 is a valid brotli stream,
and that C0 and C1 (together with the first byte of C0 that contains
the window size) can be decompressed independently from each other to
U0 and U1.
When compressing the byte sequence U0 to produce C0, we can use any
compressor that works on the complete set of uncompressed bytes U0,
with the following two changes. First, the ISLAST bit of the last
meta-block of C0 must not be set. Second, C0 must end at a byte-
boundary, which can be ensured by appending an empty metadata meta-
block to it, as in
Section 11.2 .
When compressing the byte sequence U1 to produce C1, we can use any
compressor that starts a new meta-block at the beginning of U1 within
the U0+U1 input stream, with the following two changes. First,
backward distances in C1 must not refer to static dictionary words or
uncompressed bytes in U0. Even if a sequence of bytes in U1 would
match a static dictionary word, or a sequence of bytes that overlaps
U0, the compressor must represent this sequence of bytes with a
combination of literal insertions and backward references to bytes in
U1 instead. Second, the ring buffer of last four distances must be
replenished first with distances in C1 before using it to encode
other distances in C1. Note that both compressors producing C0 and
C1 have to use the same window size, but the stream header is emitted
only by the compressor that produces C0.
Note that this method can be easily generalized to more than two
sequences of uncompressed bytes.
12. Security Considerations As with any compressed file formats, decompressor implementations
should handle all compressed data byte sequences, not only those that
conform to this specification, where non-conformant compressed data
sequences should be rejected as invalid.
A possible attack against a system containing a decompressor
implementation (e.g., a web browser) is to exploit a buffer overflow
triggered by invalid compressed data. Therefore, decompressor
implementations should perform bounds-checking for each memory access
that result from values decoded from the compressed stream and
derivatives thereof.
Another possible attack against a system containing a decompressor
implementation is to provide it (either valid or invalid) compressed
data that can make the decompressor system's resource consumption
(CPU, memory, or storage) to be disproportionately large compared to
the size of the compressed data. In addition to the size of the
compressed data, the amount of CPU, memory, and storage required to
decompress a single compressed meta-block within a brotli stream is
controlled by the following two parameters: the size of the
uncompressed meta-block, which is encoded at the start of the
compressed meta-block, and the size of the sliding window, which is
encoded at the start of the brotli stream. Decompressor
implementations in systems where memory or storage is constrained
should perform a sanity-check on these two parameters. The
uncompressed meta-block size that was decoded from the compressed
stream should be compared against either a hard limit, given by the
system's constraints or some expectation about the uncompressed data,
or against a certain multiple of the size of the compressed data. If
the uncompressed meta-block size is determined to be too high, the
compressed data should be rejected. Likewise, when the complete
uncompressed stream is kept in the system containing the decompressor
implementation, the total uncompressed size of the stream should be
checked before decompressing each additional meta-block. If the size
of the sliding window that was decoded from the start of the
compressed stream is greater than a certain soft limit, then the
decompressor implementation should, at first, allocate a smaller
sliding window that fits the first uncompressed meta-block, and
afterwards, before decompressing each additional meta-block, it
should increase the size of the sliding window until the sliding
window size specified in the compressed data is reached.
Correspondingly, possible attacks against a system containing a
compressor implementation (e.g., a web server) are to exploit a
buffer overflow or cause disproportionately large resource
consumption by providing, e.g., uncompressible data. As described in
Section 11.1 , an output buffer of
S(N) = N + (3 * (N >> 16) + 5)
bytes is sufficient to hold a valid compressed brotli stream
representing an arbitrary sequence of N uncompressed bytes.
Therefore, compressor implementations should allocate at least S(N)
bytes of output buffer before compressing N bytes of data with
unknown compressibility and should perform bounds-checking for each
write into this output buffer. If their output buffer is full,
compressor implementations should revert to the trivial compression
algorithm described in
Section 11.1 . The resource consumption of a
compressor implementation for a particular input data depends mostly
on the algorithm used to find backward matches and on the algorithm
used to construct context maps and prefix codes and only to a lesser
extent on the input data itself. If the system containing a
compressor implementation is overloaded, a possible way to reduce
resource usage is to switch to more simple algorithms for backward
reference search and prefix code construction, or to fall back to the
trivial compression algorithm described in
Section 11.1 .
A possible attack against a system that sends compressed data over an
encrypted channel is the following. An attacker who can repeatedly
mix arbitrary (attacker-supplied) data with secret data (passwords,
cookies) and observe the length of the ciphertext can potentially
reconstruct the secret data. To protect against this kind of attack,
applications should not mix sensitive data with non-sensitive,
potentially attacker-supplied data in the same compressed stream.
13. IANA Considerations The "HTTP Content Coding Registry" has been updated with the
registration below:
+-------+-------------------------------------+------------+
| Name | Description | Reference |
+-------+-------------------------------------+------------+
| br | Brotli Compressed Data Format |
RFC 7932 |
+-------+-------------------------------------+------------+
14. Informative References [HUFFMAN] Huffman, D. A., "A Method for the Construction of Minimum
Redundancy Codes", Proceedings of the Institute of Radio
Engineers, September 1952, Vol. 40, No. 9, pp. 1098-1101.
[LZ77] Ziv, J. and A. Lempel, "A Universal Algorithm for
Sequential Data Compression", IEEE Transactions on
Information Theory, Vol. 23, No. 3, pp. 337-343,
DOI 10.1109/TIT.1977.1055714, May 1977,
<
https://www.cs.duke.edu/courses/spring03/cps296.5/papers/ ziv_lempel_1977_universal_algorithm.pdf>.
[
RFC1951 ] Deutsch, P., "DEFLATE Compressed Data Format Specification
version 1.3",
RFC 1951 , DOI 10.17487/
RFC1951 , May 1996,
<
http://www.rfc-editor.org/info/rfc1951 >.
[WOFF2] Levantovsky, V., Ed., and R. Levien, Ed., "WOFF File
Format 2.0", W3C Candidate Recommendation, March 2016,
<
http://www.w3.org/TR/WOFF2/ >.
Appendix A . Static Dictionary Data The hexadecimal form of the DICT array is the following, where the
length is 122,784 bytes and the CRC-32 of the byte sequence is
0x5136cb04.
74696d65646f776e6c6966656c6566746261636b636f64656461746173686f77
6f6e6c7973697465636974796f70656e6a7573746c696b6566726565776f726b
74657874796561726f766572626f64796c6f7665666f726d626f6f6b706c6179
6c6976656c696e6568656c70686f6d65736964656d6f7265776f72646c6f6e67
7468656d7669657766696e64706167656461797366756c6c686561647465726d
656163686172656166726f6d747275656d61726b61626c6575706f6e68696768
646174656c616e646e6577736576656e6e65787463617365626f7468706f7374
757365646d61646568616e6468657265776861746e616d654c696e6b626c6f67
73697a656261736568656c646d616b656d61696e757365722729202b686f6c64
656e6473776974684e65777372656164776572657369676e74616b6568617665
67616d657365656e63616c6c7061746877656c6c706c75736d656e7566696c6d
706172746a6f696e746869736c697374676f6f646e6565647761797377657374
6a6f62736d696e64616c736f6c6f676f72696368757365736c6173747465616d
61726d79666f6f646b696e6777696c6c65617374776172646265737466697265
506167656b6e6f77617761792e706e676d6f76657468616e6c6f616467697665
73656c666e6f74656d756368666565646d616e79726f636b69636f6e6f6e6365
6c6f6f6b6869646564696564486f6d6572756c65686f7374616a6178696e666f
636c75626c6177736c65737368616c66736f6d65737563687a6f6e6531303025
6f6e65736361726554696d6572616365626c7565666f75727765656b66616365
686f706567617665686172646c6f73747768656e7061726b6b65707470617373
73686970726f6f6d48544d4c706c616e54797065646f6e65736176656b656570
666c61676c696e6b736f6c6466697665746f6f6b72617465746f776e6a756d70
746875736461726b6361726466696c6566656172737461796b696c6c74686174
66616c6c6175746f657665722e636f6d74616c6b73686f70766f746564656570
6d6f6465726573747475726e626f726e62616e6466656c6c726f736575726c28
736b696e726f6c65636f6d6561637473616765736d656574676f6c642e6a7067
6974656d7661727966656c747468656e73656e6464726f7056696577636f7079
312e30223c2f613e73746f70656c73656c696573746f75727061636b2e676966
706173746373733f677261796d65616e2667743b7269646573686f746c617465
73616964726f6164766172206665656c6a6f686e7269636b706f727466617374
2755412d646561643c2f623e706f6f7262696c6c74797065552e532e776f6f64
6d7573743270783b496e666f72616e6b7769646577616e7477616c6c6c656164
5b305d3b7061756c776176657375726524282723776169746d61737361726d73
676f65736761696e6c616e6770616964212d2d206c6f636b756e6974726f6f74
77616c6b6669726d77696665786d6c22736f6e6774657374323070786b696e64
726f7773746f6f6c666f6e746d61696c73616665737461726d617073636f7265
7261696e666c6f77626162797370616e736179733470783b3670783b61727473
666f6f747265616c77696b696865617473746570747269706f72672f6c616b65
7765616b746f6c64466f726d6361737466616e7362616e6b7665727972756e73
6a756c797461736b3170783b676f616c67726577736c6f776564676569643d22
736574733570783b2e6a733f3430707869662028736f6f6e736561746e6f6e65
747562657a65726f73656e747265656466616374696e746f676966746861726d
e0a495e0a589e0a4aae0a580e0a4b0e0a4bee0a487e0a49fe0a4b5e0a4bfe0a4
9ce0a58de0a49ee0a4bee0a4aae0a4a8e0a495e0a4bee0a4b0e0a58de0a4b0e0
a4b5e0a4bee0a488e0a4b8e0a495e0a58de0a4b0e0a4bfe0a4afe0a4a4e0a4be
The number of words for each length is given by the following bit-
depth array:
NDBITS := 0, 0, 0, 0, 10, 10, 11, 11, 10, 10,
10, 10, 10, 9, 9, 8, 7, 7, 8, 7,
7, 6, 6, 5, 5
Appendix B . List of Word Transformations The string literals are in C format, with respect to the use of
backslash escape characters.
In order to generate a length and check value, the transforms can be
converted to a series of bytes, where each transform is the prefix
sequence of bytes plus a terminating zero byte, a single-byte value
identifying the transform, and the suffix sequence of bytes plus a
terminating zero. The value for the transforms are 0 for Identity, 1
for FermentFirst, 2 for FermentAll, 3 to 11 for OmitFirst1 to
OmitFirst9, and 12 to 20 for OmitLast1 to OmitLast9. The byte
sequences that represent the 121 transforms are then concatenated to
a single sequence of bytes. The length of that sequence is 648
bytes, and the CRC-32 is 0x3d965f81.
ID Prefix Transform Suffix
-- ------ --------- ------
0 "" Identity ""
1 "" Identity " "
2 " " Identity " "
3 "" OmitFirst1 ""
4 "" FermentFirst " "
5 "" Identity " the "
6 " " Identity ""
7 "s " Identity " "
8 "" Identity " of "
9 "" FermentFirst ""
10 "" Identity " and "
11 "" OmitFirst2 ""
12 "" OmitLast1 ""
13 ", " Identity " "
14 "" Identity ", "
15 " " FermentFirst " "
16 "" Identity " in "
17 "" Identity " to "
18 "e " Identity " "
115 " " FermentAll "."
116 "" FermentAll "='"
117 " " FermentAll ". "
118 " " FermentFirst "=\""
119 " " FermentAll "='"
120 " " FermentFirst "='"
Appendix C . Computing CRC-32 Check Values For the purpose of this specification, we define the CRC-32 check
value of a byte sequence with the following C language function:
uint32_t CRC32(const uint8_t* v, const int len) {
const uint32_t poly = 0xedb88320UL;
uint32_t crc, c;
int i, k;
crc = 0xffffffffUL;
for (i = 0; i < len; ++i) {
c = (crc ^ v[i]) & 0xff;
for (k = 0; k < 8; k++) c = c & 1 ? poly ^ (c >> 1) : c >> 1;
crc = c ^ (crc >> 8);
}
return crc ^ 0xffffffffUL;
}
Source code for a C language implementation of a brotli-compliant
compressor and decompressor is available in the brotli open-source
project <
https://github.com/google/brotli >.
Acknowledgments
The authors would like to thank Mark Adler, Eugene Kliuchnikov,
Robert Obryk, Thomas Pickert, Joe Tsai, and Lode Vandevenne for
providing helpful review comments, validating the specification by
writing an independent decompressor, and suggesting improvements to
the format and the text of the specification.
Authors' Addresses