Brotli format change: improved encoding of Huffman codes
This change removes the redundant HCLEN, HLENINC and HLEN
fields from the encoding of the complex Huffman codes and
derives these from an invariant of the code length sequence.
Based on a patch by Robert Obryk.
diff --git a/brotli/brotlispec.txt b/brotli/brotlispec.txt
index 5a32a2d..9bad7ba 100644
--- a/brotli/brotlispec.txt
+++ b/brotli/brotlispec.txt
@@ -48,7 +48,7 @@
* 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, and hence
- can be used in data communications or similar structures
+ can be used in data communications or similar structures,
such as Unix filters;
* Compresses data with efficiency comparable to the best
currently available general-purpose compression methods,
@@ -62,9 +62,8 @@
1.2. Intended audience
- This specification is intended for use by implementors of software
- to compress data into "brotli" format and/or decompress data from
- "brotli" format.
+ This specification is intended for use by software implementers
+ to compress data into and/or decompress data from "brotli" format.
The text of the specification assumes a basic background in
programming at the level of bits and other primitive data
@@ -88,7 +87,7 @@
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
+ the specifications presented here. A compliant compressor must
produce data sets that conform to all the specifications presented
here.
@@ -97,7 +96,7 @@
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
which store a character on a number of bits different from eight.
- See below, for the numbering of bits within a byte.
+ See below for the numbering of bits within a byte.
String: a sequence of arbitrary bytes.
@@ -135,7 +134,7 @@
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
- in below, as a sequence of data elements of various bit
+ below as a sequence of data elements of various bit
lengths, not a sequence of bytes. We must therefore specify
how to pack these data elements into bytes to form the final
compressed byte sequence:
@@ -161,7 +160,7 @@
2. Compressed representation overview
A compressed data set consists of a header and a series of meta-
- blocks, corresponding to successive meta-blocks of input data. The
+ blocks corresponding to successive meta-blocks of input data. The
meta-block sizes are limited to bytes and the maximum meta-block size
is 268,435,456 bytes.
@@ -209,7 +208,7 @@
(IaC0, L0, L1, L2, D0)(IaC1, D1)(IaC2, L3, L4, D2)(IaC3, L5, D3)
The meta-block here has 4 commands, and each three types of symbols
- within these commands can be rearranged into for example the
+ within these commands can be rearranged for example into the
following logical block structure:
[IaC0, IaC1][IaC2, IaC3] <-- block types 0 and 1
@@ -243,16 +242,16 @@
Each type of value (insert-and-copy lengths, literals and distances)
can be encoded with any Huffman tree from a collection of Huffman
trees of the same kind appearing in the meta-block header. The
- particual Huffman tree used can depend on two factors: the block type
+ particular Huffman tree used can depend on two factors: the block type
of the block the value appears in, and the context of the value. In
the case of the literals, the context is the previous two bytes in
the input data, and in the case of distances, the context is the copy
length from the same command. For insert-and-copy lengths, no context
is used and the Huffman tree depends only on the block type (in fact,
the index of the Huffman tree is the block type number). In the case
- of literals and distances, the context is mapped to a context id in
+ of literals and distances, the context is mapped to a context ID in
the rage [0, 63] for literals and [0, 3] for distances and the matrix
- of the Huffman tree indices for each block type and context id,
+ of the Huffman tree indices for each block type and context ID,
called the context map, is encoded in a compact form in the meta-
block header.
@@ -405,8 +404,8 @@
Huffman 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 length codes,
+ literal codes the alphabet size is 256. For insert-and-copy
+ length codes the alphabet size is 704. For block length codes,
the alphabet size is 26. For distance codes, block type codes and
the Huffman codes used in compressing the context map, the
alphabet size is dynamic and is based on other parameters.
@@ -488,7 +487,8 @@
A code length of 0 indicates that the corresponding symbol in the
alphabet will not occur in the compressed data, and should not
participate in the Huffman code construction algorithm given
- earlier.
+ earlier. A complex Huffman code must have at least two non-zero
+ code lengths.
The bit lengths of the Huffman code over the code length alphabet
are compressed with the following static Huffman code:
@@ -506,52 +506,32 @@
follows:
1 bit: 0, indicating a complex Huffman code
- 4 bits: HCLEN, # of code length codes - 3
1 bit : HSKIP, if 1, skip over first two code length codes
- (HCLEN + 3 - 2 * HSKIP) code lengths for symbols in the code
- length alphabet given just above, in the order: 1, 2, 3,
- 4, 0, 17, 5, 6, 16, 7, 8, 9, 10, 11, 12, 13, 14, 15
-
- If HSKIP is 1, code lengths of code length symbols 1 and
- 2 are implicit zeros. Code lengths of code length symbols
- beyond the (HCLEN + 4)th in the ordering above are also
- implicit zeros.
+ Code lengths for symbols in the code length alphabet given
+ just above, in the order: 1, 2, 3, 4, 0, 17, 5, 6, 16, 7,
+ 8, 9, 10, 11, 12, 13, 14, 15
The code lengths of code length symbols are between 0 and
5 and they are represented with 2 - 5 bits according to
the static Huffman code above. A code length of 0 means
the corresponding code length symbol is not used.
- 1 bit: HLENINC, if 1, the number of code length symbols is
- encoded next
-
- 7-8 bits: HLEN, # of code length symbols, with the following
- encoding: values 4 - 67 with bit pattern 0xxxxxx,
- values 68 - 195 with bit pattern 1xxxxxxx, appears
- only if HLENINC = 1
+ If HSKIP is 1, code lengths of code length symbols 1 and
+ 2 are implicit zeros and are not present in the code
+ lengths sequence above. If there are at least two non-
+ zero code lengths, any trailing zero code lengths are
+ omitted, i.e. the last code length in the sequence must
+ be non-zero. In this case the sum of (32 >> code length)
+ over all the non-zero code lengths must equal to 32.
Sequence of code lengths symbols, encoded using the code
- length Huffman code. The number of code length symbols
- is either HLEN (in case of HLENINC = 1), or as many as is
- needed to assign a code length to each symbol in the
- alphabet (i.e. the alphabet size minus the sum of all the
- repeat lengths defined by extra bits of code length
- symbols 16 and 17). In case of HLENINC = 1, all symbols
- not assigned a code length have implicit code length 0.
-
- 3.6. Validity of the Huffman code
-
- There are two kinds of valid Huffman codes:
- * Huffman code that contains one symbol of length 1, and
- * Full canonical Huffman code.
-
- A decoder can check if the Huffman code is full by using integer
- arithmetic, by computing if the sum of (32768 right-shifted by
- code-length) over the non-zero code lengths leads to a total sum
- of 32768. However, if there is only one non-zero code-length, it
- shall have an implicit code length of one and the code is
- considered valid.
+ length Huffman 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 equal to
+ 32768.
4. Encoding of distances
@@ -568,11 +548,11 @@
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 additonal
+ distance, we need the sequence of past distances and two additional
parameters, the number of "postfix bits", denoted by NPOSTFIX, and
the number of direct distance codes, denoted by NDIRECT. Both of
these parameters are encoded in the meta-block header. We will also
- use the folowing derived parameter:
+ use the following derived parameter:
POSTFIX_MASK = ((1 << NPOSTFIX) - 1)
@@ -711,7 +691,7 @@
First, look up the cell with the 64 value range containing the
insert-and-copy length code, this gives the insert length code and
- and the copy length code ranges, both 8 values long. The copy length
+ the copy length code ranges, both 8 values long. The copy length
code within its range is determined by the lowest 3 bits of the
insert-and-copy length code, and the insert length code within its
range is determined by bits 3-5 (counted from the LSB) of the insert-
@@ -738,7 +718,7 @@
0 - 255. The second last and last block types are initialized with 0
and 1, respectively, at the beginning of each meta-block.
- The first block type of each block category must be 0, and the block
+ The first block type of each block category must be 0 and the block
type of the first block switch command is therefore not encoded in
the compressed data.
@@ -783,13 +763,13 @@
7. Context modeling
As described in Section 2, the Huffman tree used to encode a literal
- byte or a distance code depends on the context id and the block type.
- This section specifies how to compute the context id for a particular
+ byte or a distance code depends on the context ID and the block type.
+ 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 <context id, block type> pair to the index of a Huffman
+ maps a <context ID, block type> pair to the index of a Huffman
tree in the array of literal and distance Huffman trees.
- 7.1. Context modes and context id lookup for literals
+ 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
@@ -864,8 +844,8 @@
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
- Given p1 = last decoded byte, and p2 = second last decoded byte,
- the context ids can be computed as follows:
+ Given p1 is the last decoded byte and p2 is the second last
+ decoded byte the context IDs can be computed as follows:
For LSB6 : Context ID = p1 & 0x3f
For MSB6 : Context ID = p1 >> 2
@@ -875,14 +855,14 @@
The context modes LSB6, MSB6, UTF8, and Signed are denoted by
integers 0, 1, 2, 3.
- The context mode is defined for each literal block type, and they
- are stored in a consequtive array of bits in the meta-block
+ The 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
+ 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,
+ 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
@@ -898,7 +878,7 @@
CMAPL[0..(64 * NBLTYPESL - 1)] and CMAPD[0..(4 * NBLTYPESD - 1)].
The index of the Huffman tree for encoding a literal or distance
- code with context id "cid" and block type "bltype" is
+ code with context ID "cid" and block type "bltype" is
index of literal Huffman tree = CMAPL[bltype * 64 + cid]
@@ -946,7 +926,7 @@
At any given point during decoding the compressed data, a reference
to a duplicated string in the output produced so far has a maximum
- backward distance value, which is the minumum of the window size and
+ backward distance value, which is the minimum of the window size and
the number of output bytes produced. However, decoding a distance
from the input stream, as described in section 4, can produce
distances that are greater than this maximum allowed value. The
@@ -994,7 +974,7 @@
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 secions.
+ previous sections.
9.1. Format of the stream header
@@ -1013,7 +993,7 @@
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
+ 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:
@@ -1214,7 +1194,7 @@
read block length using HTREE_BLEN_L and set BLEN_L
decrement BLEN_L
look up context mode CMODE[BTYPE_L]
- compute context id, CIDL from last two bytes of output
+ compute context ID, CIDL from last two bytes of output
read literal using HTREEL[CMAPL[64 * BTYPE_L + CIDL]]
copy literal to output stream
if number of output bytes produced in the loop is MLEN
@@ -1226,7 +1206,7 @@
read block type using HTREE_BTYPE_D and set BTYPE_D
read block length using HTREE_BLEN_D and set BLEN_D
decrement BLEN_D
- compute context id, CIDD from CLEN
+ compute context ID, CIDD from CLEN
read distance code with HTREED[CMAPD[4 * BTYPE_D + CIDD]]
compute distance by distance short code substitution
move backwards distance bytes in the output stream, and
@@ -1237,12 +1217,12 @@
while not ISLAST
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
+ previous meta-block, i.e. the backward distance may cross one or
more meta-block boundaries. However a backward copy distance
- cannot refer past the beginning of the output stream, and it can
- not be greater than the window size, any such distance must be
- interpreted as a reference to a static dictionary word. Note also
- that the referenced string may overlap the current position; for
+ cannot refer past the beginning of the output stream and it can
+ not be greater than the window size; any such distance must be
+ 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
output stream.
diff --git a/brotli/dec/decode.c b/brotli/dec/decode.c
index bf60336..4dcaf9c 100644
--- a/brotli/dec/decode.c
+++ b/brotli/dec/decode.c
@@ -147,11 +147,10 @@
BrotliBitReader* br) {
int ok = 0;
int symbol;
- int max_symbol;
- int decode_number_of_code_length_codes;
int prev_code_len = kDefaultCodeLength;
int repeat = 0;
int repeat_length = 0;
+ int space = 32768;
HuffmanTree tree;
if (!BrotliHuffmanTreeBuildImplicit(&tree, code_length_code_lengths,
@@ -165,28 +164,10 @@
printf("[ReadHuffmanCodeLengths] Unexpected end of input.\n");
return 0;
}
- decode_number_of_code_length_codes = BrotliReadBits(br, 1);
- BROTLI_LOG_UINT(decode_number_of_code_length_codes);
- if (decode_number_of_code_length_codes) {
- if (BrotliReadBits(br, 1)) {
- max_symbol = 68 + BrotliReadBits(br, 7);
- } else {
- max_symbol = 4 + BrotliReadBits(br, 6);
- }
- if (max_symbol > num_symbols) {
- printf("[ReadHuffmanCodeLengths] max_symbol > num_symbols (%d vs %d)\n",
- max_symbol, num_symbols);
- goto End;
- }
- } else {
- max_symbol = num_symbols;
- }
- BROTLI_LOG_UINT(max_symbol);
symbol = 0;
- while (symbol + repeat < num_symbols) {
+ while (symbol + repeat < num_symbols && space > 0) {
int code_len;
- if (max_symbol-- == 0) break;
if (!BrotliReadMoreInput(br)) {
printf("[ReadHuffmanCodeLengths] Unexpected end of input.\n");
goto End;
@@ -206,17 +187,32 @@
}
if (code_len < kCodeLengthRepeatCode) {
code_lengths[symbol++] = code_len;
- if (code_len != 0) prev_code_len = code_len;
+ if (code_len != 0) {
+ prev_code_len = code_len;
+ space -= 32768 >> code_len;
+ }
} else {
const int extra_bits = code_len - 14;
+ int i = repeat;
if (repeat > 0) {
repeat -= 2;
repeat <<= extra_bits;
}
repeat += BrotliReadBits(br, extra_bits) + 3;
- repeat_length = (code_len == kCodeLengthRepeatCode ? prev_code_len : 0);
+ if (code_len == kCodeLengthRepeatCode) {
+ repeat_length = prev_code_len;
+ for (; i < repeat; ++i) {
+ space -= 32768 >> repeat_length;
+ }
+ } else {
+ repeat_length = 0;
+ }
}
}
+ if (space != 0) {
+ printf("[ReadHuffmanCodeLengths] space = %d\n", space);
+ goto End;
+ }
if (symbol + repeat > num_symbols) {
printf("[ReadHuffmanCodeLengths] symbol + repeat > num_symbols "
"(%d + %d vs %d)\n", symbol, repeat, num_symbols);
@@ -286,12 +282,9 @@
} else { /* Decode Huffman-coded code lengths. */
int i;
uint8_t code_length_code_lengths[CODE_LENGTH_CODES] = { 0 };
- const int num_codes = BrotliReadBits(br, 4) + 3;
- BROTLI_LOG_UINT(num_codes);
- if (num_codes > CODE_LENGTH_CODES) {
- return 0;
- }
- for (i = BrotliReadBits(br, 1) * 2; i < num_codes; ++i) {
+ int space = 32;
+ for (i = BrotliReadBits(br, 1) * 2;
+ i < CODE_LENGTH_CODES && space > 0; ++i) {
int code_len_idx = kCodeLengthCodeOrder[i];
int v = BrotliReadBits(br, 2);
if (v == 1) {
@@ -311,6 +304,9 @@
}
code_length_code_lengths[code_len_idx] = v;
BROTLI_LOG_ARRAY_INDEX(code_length_code_lengths, code_len_idx);
+ if (v != 0) {
+ space -= (32 >> v);
+ }
}
ok = ReadHuffmanCodeLengths(code_length_code_lengths, alphabet_size,
code_lengths, br);
diff --git a/brotli/enc/backward_references.cc b/brotli/enc/backward_references.cc
index 71554fe..0e7f89b 100644
--- a/brotli/enc/backward_references.cc
+++ b/brotli/enc/backward_references.cc
@@ -87,7 +87,7 @@
// If we are not inserting any symbols, inserting one is more
// expensive than if we were inserting symbols anyways.
if (insert_length < 1) {
- cost_diff_lazy += 1.0;
+ cost_diff_lazy += 0.97;
}
// Add bias to slightly avoid lazy matching.
cost_diff_lazy += 2.0 + delayed_backward_references_in_row * 0.2;
diff --git a/brotli/enc/bit_cost.h b/brotli/enc/bit_cost.h
index 5d6ef0f..c769455 100644
--- a/brotli/enc/bit_cost.h
+++ b/brotli/enc/bit_cost.h
@@ -104,7 +104,7 @@
template<int kSize>
double PopulationCost(const Histogram<kSize>& histogram) {
if (histogram.total_count_ == 0) {
- return 11;
+ return 12;
}
int count = 0;
for (int i = 0; i < kSize && count < 5; ++i) {
@@ -113,10 +113,10 @@
}
}
if (count == 1) {
- return 11;
+ return 12;
}
if (count == 2) {
- return 19 + histogram.total_count_;
+ return 20 + histogram.total_count_;
}
uint8_t depth[kSize] = { 0 };
CreateHuffmanTree(&histogram.data_[0], kSize, 15, depth);
@@ -125,7 +125,9 @@
bits += histogram.data_[i] * depth[i];
}
if (count == 3) {
- bits += 27;
+ bits += 28;
+ } else if (count == 4) {
+ bits += 37;
} else {
bits += HuffmanBitCost(depth, kSize);
}
diff --git a/brotli/enc/encode.cc b/brotli/enc/encode.cc
index 7d54dbe..8e497fa 100644
--- a/brotli/enc/encode.cc
+++ b/brotli/enc/encode.cc
@@ -122,12 +122,20 @@
};
// Throw away trailing zeros:
int codes_to_store = kCodeLengthCodes;
- for (; codes_to_store > 3; --codes_to_store) {
+ for (; codes_to_store > 0; --codes_to_store) {
if (code_length_bitdepth[kStorageOrder[codes_to_store - 1]] != 0) {
break;
}
}
- WriteBits(4, codes_to_store - 3, storage_ix, storage);
+ int num_codes = 0;
+ for (int i = 0; i < codes_to_store; ++i) {
+ if (code_length_bitdepth[kStorageOrder[i]] != 0) {
+ ++num_codes;
+ }
+ }
+ if (num_codes == 1) {
+ codes_to_store = kCodeLengthCodes;
+ }
const int skip_two_first =
code_length_bitdepth[kStorageOrder[0]] == 0 &&
code_length_bitdepth[kStorageOrder[1]] == 0;
@@ -229,40 +237,8 @@
EntropyCode<kCodeLengthCodes> huffman_tree_entropy;
BuildEntropyCode(huffman_tree_histogram, 5, kCodeLengthCodes,
&huffman_tree_entropy);
- Histogram<kCodeLengthCodes> trimmed_histogram = huffman_tree_histogram;
- uint8_t* last_code = &huffman_tree[huffman_tree_size - 1];
- while (*last_code == 0 || *last_code >= 17) {
- trimmed_histogram.Remove(*last_code--);
- }
- int trimmed_size = trimmed_histogram.total_count_;
- bool write_length = false;
- if (trimmed_size >= 4 && trimmed_size <= 195 &&
- trimmed_size < huffman_tree_size) {
- EntropyCode<kCodeLengthCodes> trimmed_entropy;
- BuildEntropyCode(trimmed_histogram, 5, kCodeLengthCodes, &trimmed_entropy);
- int huffman_bit_cost = HuffmanTreeBitCost(huffman_tree_histogram,
- huffman_tree_entropy);
- int trimmed_bit_cost = HuffmanTreeBitCost(trimmed_histogram,
- trimmed_entropy);;
- trimmed_bit_cost += (trimmed_size < 68 ? 7 : 8);
- if (trimmed_bit_cost < huffman_bit_cost) {
- write_length = true;
- huffman_tree_size = trimmed_size;
- huffman_tree_entropy = trimmed_entropy;
- }
- }
-
StoreHuffmanTreeOfHuffmanTreeToBitMask(
&huffman_tree_entropy.depth_[0], storage_ix, storage);
- WriteBits(1, write_length, storage_ix, storage);
- if (write_length) {
- WriteBits(1, huffman_tree_size >= 68, storage_ix, storage);
- if (huffman_tree_size < 68) {
- WriteBits(6, huffman_tree_size - 4, storage_ix, storage);
- } else {
- WriteBits(7, huffman_tree_size - 68, storage_ix, storage);
- }
- }
StoreHuffmanTreeToBitMask(&huffman_tree[0], &huffman_tree_extra_bits[0],
huffman_tree_size, huffman_tree_entropy,
storage_ix, storage);
@@ -322,9 +298,13 @@
int cur_dist = (*cmds)[i].copy_distance_;
if (cur_dist == 0) break;
int dist_code = cur_dist + 16;
+ int limits[16] = { 0, 4, 10, 11,
+ 6, 6, 11, 11,
+ 11, 11, 11, 11,
+ 12, 12, 12, 12 };
for (int k = 0; k < 16; ++k) {
// Only accept more popular choices.
- if (cur_dist < 11 && ((k >= 2 && k < 4) || k >= 6)) {
+ if (cur_dist < limits[k]) {
// Typically unpopular ranges, don't replace a short distance
// with them.
continue;
diff --git a/brotli/enc/entropy_encode.cc b/brotli/enc/entropy_encode.cc
index ad9f0f5..e4c6b20 100644
--- a/brotli/enc/entropy_encode.cc
+++ b/brotli/enc/entropy_encode.cc
@@ -352,6 +352,12 @@
}
i += reps;
}
+ // Throw away trailing zeros.
+ for (; *huffman_tree_size > 0; --(*huffman_tree_size)) {
+ if (tree[*huffman_tree_size - 1] > 0 && tree[*huffman_tree_size - 1] < 17) {
+ break;
+ }
+ }
}
namespace {