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/enc/encode.cc b/enc/encode.cc
index 7d54dbe..8e497fa 100644
--- a/enc/encode.cc
+++ b/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;