BR file format: stream and meta-blocks

A Brotli stream is a sequence of bits, packed into bytes from the least significant bit up, as in Deflate. Bit patterns below are written as in RFC 7932: read from right to left. This page follows RFC 7932; the commands inside a meta-block are on commands and distances.

Window size

The stream starts with WBITS, 1 to 7 bits. The window is (1 << WBITS) − 16 bytes.

WBITS	Bits	WBITS	Bits
10	`0100001`	18	`0011`
11	`0110001`	19	`0101`
12	`1000001`	20	`0111`
13	`1010001`	21	`1001`
14	`1100001`	22	`1011`
15	`1110001`	23	`1101`
16	`0`	24	`1111`
17	`0000001`

0010001 is invalid. (A later “large window” extension uses it; it is not part of RFC 7932.)

Meta-block header

Field	Bits	Meaning
`ISLAST`	1	1 for the last meta-block.
`ISLASTEMPTY`	1	Only if `ISLAST`: 1 means the meta-block is empty and the stream ends here.
`MNIBBLES`	2	`00` → 4, `01` → 5, `10` → 6, `11` → 0 (a metadata block, below).
`MLEN − 1`	`MNIBBLES` × 4	Uncompressed length of the meta-block, 1 to 16,777,216. With more than 4 nibbles, the last nibble must not be 0.
`ISUNCOMPRESSED`	1	Only if not `ISLAST`: 1 means the data is stored. The reader skips to the next byte boundary (the skipped bits must be 0), and `MLEN` bytes follow.

Metadata blocks

With MNIBBLES 0: a reserved bit (0), MSKIPBYTES (2 bits, 0 to 3), then MSKIPLEN − 1 in MSKIPBYTES × 8 bits (the highest byte not 0 when there is more than one). Then skip to a byte boundary and skip MSKIPLEN bytes (none when MSKIPBYTES is 0). Metadata produces no output.

Compressed meta-block header

Otherwise, after the header comes, in order:

For each of the three categories, literals (L), insert-and-copy lengths (I) and distances (D): NBLTYPES (1 to 256), and if more than 1, a prefix code for block types, a prefix code for block counts, and the first block count.
NPOSTFIX, 2 bits, and NDIRECT = 4 bits << NPOSTFIX: the distance code parameters.
A context mode, 2 bits, for each literal block type.
NTREESL (1 to 256) and, if more than 1, the literal context map (64 entries per literal block type).
NTREESD (1 to 256) and, if more than 1, the distance context map (4 entries per distance block type).
NTREESL prefix codes for literals (256 symbols), NBLTYPESI for insert-and-copy lengths (704 symbols) and NTREESD for distances (16 + NDIRECT + 48 << NPOSTFIX symbols).
The commands, until MLEN bytes have been produced.

Counts from 1 to 256

Value	Bits
1	`0`
2	`0001`
3 to 4	`x0011`
5 to 8	`xx0101`
9 to 16	`xxx0111`
17 to 32	`xxxx1001`
33 to 64	`xxxxx1011`
65 to 128	`xxxxxx1101`
129 to 256	`xxxxxxx1111`

Used for NBLTYPESL, NBLTYPESI, NBLTYPESD, NTREESL and NTREESD.

Prefix codes

Every Huffman (prefix) code starts with 2 bits, HSKIP.

Simple code (HSKIP = 1): NSYM − 1 in 2 bits, then NSYM symbols of the alphabet’s bit width. With 4 symbols, one more bit chooses between lengths 2, 2, 2, 2 and 1, 2, 3, 3. With 1 symbol it takes no bits to code.
Complex code (HSKIP 0, 2 or 3): code lengths of the code length alphabet, in the order 1, 2, 3, 4, 0, 5, 17, 6, 16, 7, 8, 9, 10, 11, 12, 13, 14, 15, skipping the first HSKIP. Each is written with a fixed code: 0 = 00, 1 = 0111, 2 = 011, 3 = 10, 4 = 01, 5 = 1111. Then the symbol code lengths, coded with that code: 0 to 15 are lengths; 16 repeats the previous non-zero length 3 to 6 times (2 extra bits), 17 repeats zero 3 to 10 times (3 extra bits). The previous length starts as 8.

Context modes

A literal’s prefix code is chosen by a context ID (0 to 63) worked out from the two bytes before it, by the mode of its block type:

Mode	Name	Context from p1 (last byte) and p2
`0`	LSB6	The low 6 bits of p1.
`1`	MSB6	The high 6 bits of p1.
`2`	UTF8	Lookup tables for p1 and p2 that tell letters, digits, spaces and punctuation apart.
`3`	Signed	Lookup tables that bucket p1 and p2 as signed values by size.

The lookup tables are listed in section 7.1 of the RFC. A distance’s context is its copy length: 2 → 0, 3 → 1, 4 → 2, 5 or more → 3.

Context maps

A context map maps (block type, context ID) to a prefix code index. It is written as: RLEMAX flag (1 bit; if 1, 4 bits of RLEMAX − 1), a prefix code over NTREES + RLEMAX symbols, the entries (symbol 0 is a 0; 1 to RLEMAX are runs of zeros of 2ⁿ plus n extra bits; higher symbols are the value minus RLEMAX), then an IMTF bit: if 1, undo a move-to-front transform on the entries.

.BR File Format – Stream and meta-blocks