.BR File Format – Commands and distances

Brotli compressed file

The data of a compressed meta-block (see stream and meta-blocks) is a series of commands. Each command is an insert-and-copy length code with its extra bits, that many literals, then (unless the meta-block is complete) a distance code with its extra bits. Block switch commands for each category may come before any symbol of that category. This page follows RFC 7932, sections 4 to 6 and 8.

Insert-and-copy length codes

The 704 symbols are arranged in cells of 64. Within a cell, the insert length code is the cell’s first insert code + (symbol >> 3) & 7, and the copy length code is its first copy code + symbol & 7.

SymbolsInsert codesCopy codesDistance
0 to 630 to 70 to 7Implied code 0 (the last distance)
64 to 1270 to 78 to 15Implied code 0
128 to 1910 to 70 to 7Coded
192 to 2550 to 78 to 15Coded
256 to 3198 to 150 to 7Coded
320 to 3838 to 158 to 15Coded
384 to 4470 to 716 to 23Coded
448 to 51116 to 230 to 7Coded
512 to 5758 to 1516 to 23Coded
576 to 63916 to 238 to 15Coded
640 to 70316 to 2316 to 23Coded

Insert and copy lengths

CodeInsert: extra bits, lengthsCopy: extra bits, lengths
00, 00, 2
10, 10, 3
20, 20, 4
30, 30, 5
40, 40, 6
50, 50, 7
61, 6–70, 8
71, 8–90, 9
82, 10–131, 10–11
92, 14–171, 12–13
103, 18–252, 14–17
113, 26–332, 18–21
124, 34–493, 22–29
134, 50–653, 30–37
145, 66–974, 38–53
155, 98–1294, 54–69
166, 130–1935, 70–101
177, 194–3215, 102–133
188, 322–5776, 134–197
199, 578–10897, 198–325
2010, 1090–21138, 326–581
2112, 2114–62099, 582–1093
2214, 6210–2259310, 1094–2117
2324, 22594–1679980924, 2118–16779333

The insert extra bits come before the copy extra bits.

Block switches and block counts

When a category has more than one block type, a block switch is a block type code and a block count. Block type code 0 means the type before the current one, 1 means current + 1 (wrapping), and n ≥ 2 means type n − 2. Block counts:

CodeExtra bitsRangeCodeExtra bitsRange
021–4135145–176
125–8145177–208
229–12155209–240
3213–16166241–304
4317–24176305–368
5325–32187369–496
6333–40198497–752
7341–48209753–1264
8449–6421101265–2288
9465–8022112289–4336
10481–9623124337–8432
11497–11224138433–16624
125113–144252416625–16793840

Distances

The last four distances are kept in a ring buffer, set to 16, 15, 11 and 4 at the start of the stream (4 is the last). Codes 0 to 15 refer to it:

CodeDistanceCodeDistance
0Last8Last − 3
1Second to last9Last + 3
2Third to last10Second to last − 1
3Fourth to last11Second to last + 1
4Last − 112Second to last − 2
5Last + 113Second to last + 2
6Last − 214Second to last − 3
7Last + 215Second to last + 3

Codes 16 to 15 + NDIRECT are the distances 1 to NDIRECT. Higher codes have extra bits; with d = code − NDIRECT − 16:

ndistbits = 1 + (d >> (NPOSTFIX + 1))
hcode     = d >> NPOSTFIX
lcode     = d & ((1 << NPOSTFIX) − 1)
offset    = ((2 + (hcode & 1)) << ndistbits) − 4
distance  = ((offset + extra) << NPOSTFIX) + lcode + NDIRECT + 1

Distance code 0 does not change the ring buffer; every other distance that is not a dictionary reference is pushed into it.

Static dictionary references

A distance larger than the maximum allowed (the smaller of the window size and the bytes produced so far) refers to Brotli’s built-in dictionary of 122,784 bytes: words of 4 to 24 bytes, grouped by length. With copy length len:

word_id      = distance − (max allowed distance + 1)
index        = word_id & ((1 << NDBITS[len]) − 1)
transform_id = word_id >> NDBITS[len]

The word is transformed by one of 121 transforms (adding a prefix and suffix, changing case, cutting letters from the start or end) and copied to the output. A transform ID of 121 or more is invalid.

Length4567891011121314
NDBITS10101111101010101099
Length15161718192021222324
NDBITS8778776655

The dictionary and the transform list are in the RFC’s appendices; the dictionary’s CRC-32 is 5136CB04.