diff options
Diffstat (limited to '')
| -rw-r--r-- | web/server/h2o/libh2o/deps/brotli/enc/brotli_bit_stream.cc | 1127 |
1 files changed, 1127 insertions, 0 deletions
diff --git a/web/server/h2o/libh2o/deps/brotli/enc/brotli_bit_stream.cc b/web/server/h2o/libh2o/deps/brotli/enc/brotli_bit_stream.cc new file mode 100644 index 00000000..69a73fc0 --- /dev/null +++ b/web/server/h2o/libh2o/deps/brotli/enc/brotli_bit_stream.cc @@ -0,0 +1,1127 @@ +/* Copyright 2014 Google Inc. All Rights Reserved. + + Distributed under MIT license. + See file LICENSE for detail or copy at https://opensource.org/licenses/MIT +*/ + +// Brotli bit stream functions to support the low level format. There are no +// compression algorithms here, just the right ordering of bits to match the +// specs. + +#include "./brotli_bit_stream.h" + +#include <algorithm> +#include <cstdlib> +#include <cstring> +#include <limits> +#include <vector> + +#include "./bit_cost.h" +#include "./context.h" +#include "./entropy_encode.h" +#include "./entropy_encode_static.h" +#include "./fast_log.h" +#include "./prefix.h" +#include "./write_bits.h" +namespace brotli { + +namespace { + +// nibblesbits represents the 2 bits to encode MNIBBLES (0-3) +// REQUIRES: length > 0 +// REQUIRES: length <= (1 << 24) +void EncodeMlen(size_t length, uint64_t* bits, + size_t* numbits, uint64_t* nibblesbits) { + assert(length > 0); + assert(length <= (1 << 24)); + length--; // MLEN - 1 is encoded + size_t lg = length == 0 ? 1 : Log2FloorNonZero( + static_cast<uint32_t>(length)) + 1; + assert(lg <= 24); + size_t mnibbles = (lg < 16 ? 16 : (lg + 3)) / 4; + *nibblesbits = mnibbles - 4; + *numbits = mnibbles * 4; + *bits = length; +} + +} // namespace + +void StoreVarLenUint8(size_t n, size_t* storage_ix, uint8_t* storage) { + if (n == 0) { + WriteBits(1, 0, storage_ix, storage); + } else { + WriteBits(1, 1, storage_ix, storage); + size_t nbits = Log2FloorNonZero(n); + WriteBits(3, nbits, storage_ix, storage); + WriteBits(nbits, n - (1 << nbits), storage_ix, storage); + } +} + +void StoreCompressedMetaBlockHeader(bool final_block, + size_t length, + size_t* storage_ix, + uint8_t* storage) { + // Write ISLAST bit. + WriteBits(1, final_block, storage_ix, storage); + // Write ISEMPTY bit. + if (final_block) { + WriteBits(1, 0, storage_ix, storage); + } + + uint64_t lenbits; + size_t nlenbits; + uint64_t nibblesbits; + EncodeMlen(length, &lenbits, &nlenbits, &nibblesbits); + WriteBits(2, nibblesbits, storage_ix, storage); + WriteBits(nlenbits, lenbits, storage_ix, storage); + + if (!final_block) { + // Write ISUNCOMPRESSED bit. + WriteBits(1, 0, storage_ix, storage); + } +} + +void StoreUncompressedMetaBlockHeader(size_t length, + size_t* storage_ix, + uint8_t* storage) { + // Write ISLAST bit. Uncompressed block cannot be the last one, so set to 0. + WriteBits(1, 0, storage_ix, storage); + uint64_t lenbits; + size_t nlenbits; + uint64_t nibblesbits; + EncodeMlen(length, &lenbits, &nlenbits, &nibblesbits); + WriteBits(2, nibblesbits, storage_ix, storage); + WriteBits(nlenbits, lenbits, storage_ix, storage); + // Write ISUNCOMPRESSED bit. + WriteBits(1, 1, storage_ix, storage); +} + +void StoreHuffmanTreeOfHuffmanTreeToBitMask( + const int num_codes, + const uint8_t *code_length_bitdepth, + size_t *storage_ix, + uint8_t *storage) { + static const uint8_t kStorageOrder[kCodeLengthCodes] = { + 1, 2, 3, 4, 0, 5, 17, 6, 16, 7, 8, 9, 10, 11, 12, 13, 14, 15 + }; + // The bit lengths of the Huffman code over the code length alphabet + // are compressed with the following static Huffman code: + // Symbol Code + // ------ ---- + // 0 00 + // 1 1110 + // 2 110 + // 3 01 + // 4 10 + // 5 1111 + static const uint8_t kHuffmanBitLengthHuffmanCodeSymbols[6] = { + 0, 7, 3, 2, 1, 15 + }; + static const uint8_t kHuffmanBitLengthHuffmanCodeBitLengths[6] = { + 2, 4, 3, 2, 2, 4 + }; + + // Throw away trailing zeros: + size_t codes_to_store = kCodeLengthCodes; + if (num_codes > 1) { + for (; codes_to_store > 0; --codes_to_store) { + if (code_length_bitdepth[kStorageOrder[codes_to_store - 1]] != 0) { + break; + } + } + } + size_t skip_some = 0; // skips none. + if (code_length_bitdepth[kStorageOrder[0]] == 0 && + code_length_bitdepth[kStorageOrder[1]] == 0) { + skip_some = 2; // skips two. + if (code_length_bitdepth[kStorageOrder[2]] == 0) { + skip_some = 3; // skips three. + } + } + WriteBits(2, skip_some, storage_ix, storage); + for (size_t i = skip_some; i < codes_to_store; ++i) { + size_t l = code_length_bitdepth[kStorageOrder[i]]; + WriteBits(kHuffmanBitLengthHuffmanCodeBitLengths[l], + kHuffmanBitLengthHuffmanCodeSymbols[l], storage_ix, storage); + } +} + +void StoreHuffmanTreeToBitMask( + const std::vector<uint8_t> &huffman_tree, + const std::vector<uint8_t> &huffman_tree_extra_bits, + const uint8_t *code_length_bitdepth, + const std::vector<uint16_t> &code_length_bitdepth_symbols, + size_t * __restrict storage_ix, + uint8_t * __restrict storage) { + for (size_t i = 0; i < huffman_tree.size(); ++i) { + size_t ix = huffman_tree[i]; + WriteBits(code_length_bitdepth[ix], code_length_bitdepth_symbols[ix], + storage_ix, storage); + // Extra bits + switch (ix) { + case 16: + WriteBits(2, huffman_tree_extra_bits[i], storage_ix, storage); + break; + case 17: + WriteBits(3, huffman_tree_extra_bits[i], storage_ix, storage); + break; + } + } +} + +void StoreSimpleHuffmanTree(const uint8_t* depths, + size_t symbols[4], + size_t num_symbols, + size_t max_bits, + size_t *storage_ix, uint8_t *storage) { + // value of 1 indicates a simple Huffman code + WriteBits(2, 1, storage_ix, storage); + WriteBits(2, num_symbols - 1, storage_ix, storage); // NSYM - 1 + + // Sort + for (size_t i = 0; i < num_symbols; i++) { + for (size_t j = i + 1; j < num_symbols; j++) { + if (depths[symbols[j]] < depths[symbols[i]]) { + std::swap(symbols[j], symbols[i]); + } + } + } + + if (num_symbols == 2) { + WriteBits(max_bits, symbols[0], storage_ix, storage); + WriteBits(max_bits, symbols[1], storage_ix, storage); + } else if (num_symbols == 3) { + WriteBits(max_bits, symbols[0], storage_ix, storage); + WriteBits(max_bits, symbols[1], storage_ix, storage); + WriteBits(max_bits, symbols[2], storage_ix, storage); + } else { + WriteBits(max_bits, symbols[0], storage_ix, storage); + WriteBits(max_bits, symbols[1], storage_ix, storage); + WriteBits(max_bits, symbols[2], storage_ix, storage); + WriteBits(max_bits, symbols[3], storage_ix, storage); + // tree-select + WriteBits(1, depths[symbols[0]] == 1 ? 1 : 0, storage_ix, storage); + } +} + +// num = alphabet size +// depths = symbol depths +void StoreHuffmanTree(const uint8_t* depths, size_t num, + size_t *storage_ix, uint8_t *storage) { + // Write the Huffman tree into the brotli-representation. + std::vector<uint8_t> huffman_tree; + std::vector<uint8_t> huffman_tree_extra_bits; + // TODO: Consider allocating these from stack. + huffman_tree.reserve(256); + huffman_tree_extra_bits.reserve(256); + WriteHuffmanTree(depths, num, &huffman_tree, &huffman_tree_extra_bits); + + // Calculate the statistics of the Huffman tree in brotli-representation. + uint32_t huffman_tree_histogram[kCodeLengthCodes] = { 0 }; + for (size_t i = 0; i < huffman_tree.size(); ++i) { + ++huffman_tree_histogram[huffman_tree[i]]; + } + + int num_codes = 0; + int code = 0; + for (int i = 0; i < kCodeLengthCodes; ++i) { + if (huffman_tree_histogram[i]) { + if (num_codes == 0) { + code = i; + num_codes = 1; + } else if (num_codes == 1) { + num_codes = 2; + break; + } + } + } + + // Calculate another Huffman tree to use for compressing both the + // earlier Huffman tree with. + // TODO: Consider allocating these from stack. + uint8_t code_length_bitdepth[kCodeLengthCodes] = { 0 }; + std::vector<uint16_t> code_length_bitdepth_symbols(kCodeLengthCodes); + CreateHuffmanTree(&huffman_tree_histogram[0], kCodeLengthCodes, + 5, &code_length_bitdepth[0]); + ConvertBitDepthsToSymbols(code_length_bitdepth, kCodeLengthCodes, + &code_length_bitdepth_symbols[0]); + + // Now, we have all the data, let's start storing it + StoreHuffmanTreeOfHuffmanTreeToBitMask(num_codes, code_length_bitdepth, + storage_ix, storage); + + if (num_codes == 1) { + code_length_bitdepth[code] = 0; + } + + // Store the real huffman tree now. + StoreHuffmanTreeToBitMask(huffman_tree, + huffman_tree_extra_bits, + &code_length_bitdepth[0], + code_length_bitdepth_symbols, + storage_ix, storage); +} + + +void BuildAndStoreHuffmanTree(const uint32_t *histogram, + const size_t length, + uint8_t* depth, + uint16_t* bits, + size_t* storage_ix, + uint8_t* storage) { + size_t count = 0; + size_t s4[4] = { 0 }; + for (size_t i = 0; i < length; i++) { + if (histogram[i]) { + if (count < 4) { + s4[count] = i; + } else if (count > 4) { + break; + } + count++; + } + } + + size_t max_bits_counter = length - 1; + size_t max_bits = 0; + while (max_bits_counter) { + max_bits_counter >>= 1; + ++max_bits; + } + + if (count <= 1) { + WriteBits(4, 1, storage_ix, storage); + WriteBits(max_bits, s4[0], storage_ix, storage); + return; + } + + CreateHuffmanTree(histogram, length, 15, depth); + ConvertBitDepthsToSymbols(depth, length, bits); + + if (count <= 4) { + StoreSimpleHuffmanTree(depth, s4, count, max_bits, storage_ix, storage); + } else { + StoreHuffmanTree(depth, length, storage_ix, storage); + } +} + +void BuildAndStoreHuffmanTreeFast(const uint32_t *histogram, + const size_t histogram_total, + const size_t max_bits, + uint8_t* depth, + uint16_t* bits, + size_t* storage_ix, + uint8_t* storage) { + size_t count = 0; + size_t symbols[4] = { 0 }; + size_t length = 0; + size_t total = histogram_total; + while (total != 0) { + if (histogram[length]) { + if (count < 4) { + symbols[count] = length; + } + ++count; + total -= histogram[length]; + } + ++length; + } + + if (count <= 1) { + WriteBits(4, 1, storage_ix, storage); + WriteBits(max_bits, symbols[0], storage_ix, storage); + return; + } + + const size_t max_tree_size = 2 * length + 1; + HuffmanTree* const tree = + static_cast<HuffmanTree*>(malloc(max_tree_size * sizeof(HuffmanTree))); + for (uint32_t count_limit = 1; ; count_limit *= 2) { + HuffmanTree* node = tree; + for (size_t i = length; i != 0;) { + --i; + if (histogram[i]) { + if (PREDICT_TRUE(histogram[i] >= count_limit)) { + *node = HuffmanTree(histogram[i], -1, static_cast<int16_t>(i)); + } else { + *node = HuffmanTree(count_limit, -1, static_cast<int16_t>(i)); + } + ++node; + } + } + const int n = static_cast<int>(node - tree); + std::sort(tree, node, SortHuffmanTree); + // The nodes are: + // [0, n): the sorted leaf nodes that we start with. + // [n]: we add a sentinel here. + // [n + 1, 2n): new parent nodes are added here, starting from + // (n+1). These are naturally in ascending order. + // [2n]: we add a sentinel at the end as well. + // There will be (2n+1) elements at the end. + const HuffmanTree sentinel(std::numeric_limits<int>::max(), -1, -1); + *node++ = sentinel; + *node++ = sentinel; + + int i = 0; // Points to the next leaf node. + int j = n + 1; // Points to the next non-leaf node. + for (int k = n - 1; k > 0; --k) { + int left, right; + if (tree[i].total_count_ <= tree[j].total_count_) { + left = i; + ++i; + } else { + left = j; + ++j; + } + if (tree[i].total_count_ <= tree[j].total_count_) { + right = i; + ++i; + } else { + right = j; + ++j; + } + // The sentinel node becomes the parent node. + node[-1].total_count_ = + tree[left].total_count_ + tree[right].total_count_; + node[-1].index_left_ = static_cast<int16_t>(left); + node[-1].index_right_or_value_ = static_cast<int16_t>(right); + // Add back the last sentinel node. + *node++ = sentinel; + } + SetDepth(tree[2 * n - 1], &tree[0], depth, 0); + // We need to pack the Huffman tree in 14 bits. + // If this was not successful, add fake entities to the lowest values + // and retry. + if (PREDICT_TRUE(*std::max_element(&depth[0], &depth[length]) <= 14)) { + break; + } + } + free(tree); + ConvertBitDepthsToSymbols(depth, length, bits); + if (count <= 4) { + // value of 1 indicates a simple Huffman code + WriteBits(2, 1, storage_ix, storage); + WriteBits(2, count - 1, storage_ix, storage); // NSYM - 1 + + // Sort + for (size_t i = 0; i < count; i++) { + for (size_t j = i + 1; j < count; j++) { + if (depth[symbols[j]] < depth[symbols[i]]) { + std::swap(symbols[j], symbols[i]); + } + } + } + + if (count == 2) { + WriteBits(max_bits, symbols[0], storage_ix, storage); + WriteBits(max_bits, symbols[1], storage_ix, storage); + } else if (count == 3) { + WriteBits(max_bits, symbols[0], storage_ix, storage); + WriteBits(max_bits, symbols[1], storage_ix, storage); + WriteBits(max_bits, symbols[2], storage_ix, storage); + } else { + WriteBits(max_bits, symbols[0], storage_ix, storage); + WriteBits(max_bits, symbols[1], storage_ix, storage); + WriteBits(max_bits, symbols[2], storage_ix, storage); + WriteBits(max_bits, symbols[3], storage_ix, storage); + // tree-select + WriteBits(1, depth[symbols[0]] == 1 ? 1 : 0, storage_ix, storage); + } + } else { + // Complex Huffman Tree + StoreStaticCodeLengthCode(storage_ix, storage); + + // Actual rle coding. + uint8_t previous_value = 8; + for (size_t i = 0; i < length;) { + const uint8_t value = depth[i]; + size_t reps = 1; + for (size_t k = i + 1; k < length && depth[k] == value; ++k) { + ++reps; + } + i += reps; + if (value == 0) { + WriteBits(kZeroRepsDepth[reps], kZeroRepsBits[reps], + storage_ix, storage); + } else { + if (previous_value != value) { + WriteBits(kCodeLengthDepth[value], kCodeLengthBits[value], + storage_ix, storage); + --reps; + } + if (reps < 3) { + while (reps != 0) { + reps--; + WriteBits(kCodeLengthDepth[value], kCodeLengthBits[value], + storage_ix, storage); + } + } else { + reps -= 3; + WriteBits(kNonZeroRepsDepth[reps], kNonZeroRepsBits[reps], + storage_ix, storage); + } + previous_value = value; + } + } + } +} + +size_t IndexOf(const std::vector<uint32_t>& v, uint32_t value) { + size_t i = 0; + for (; i < v.size(); ++i) { + if (v[i] == value) return i; + } + return i; +} + +void MoveToFront(std::vector<uint32_t>* v, size_t index) { + uint32_t value = (*v)[index]; + for (size_t i = index; i != 0; --i) { + (*v)[i] = (*v)[i - 1]; + } + (*v)[0] = value; +} + +std::vector<uint32_t> MoveToFrontTransform(const std::vector<uint32_t>& v) { + if (v.empty()) return v; + uint32_t max_value = *std::max_element(v.begin(), v.end()); + std::vector<uint32_t> mtf(max_value + 1); + for (uint32_t i = 0; i <= max_value; ++i) mtf[i] = i; + std::vector<uint32_t> result(v.size()); + for (size_t i = 0; i < v.size(); ++i) { + size_t index = IndexOf(mtf, v[i]); + assert(index < mtf.size()); + result[i] = static_cast<uint32_t>(index); + MoveToFront(&mtf, index); + } + return result; +} + +// Finds runs of zeros in v_in and replaces them with a prefix code of the run +// length plus extra bits in *v_out and *extra_bits. Non-zero values in v_in are +// shifted by *max_length_prefix. Will not create prefix codes bigger than the +// initial value of *max_run_length_prefix. The prefix code of run length L is +// simply Log2Floor(L) and the number of extra bits is the same as the prefix +// code. +void RunLengthCodeZeros(const std::vector<uint32_t>& v_in, + uint32_t* max_run_length_prefix, + std::vector<uint32_t>* v_out, + std::vector<uint32_t>* extra_bits) { + uint32_t max_reps = 0; + for (size_t i = 0; i < v_in.size();) { + for (; i < v_in.size() && v_in[i] != 0; ++i) ; + uint32_t reps = 0; + for (; i < v_in.size() && v_in[i] == 0; ++i) { + ++reps; + } + max_reps = std::max(reps, max_reps); + } + uint32_t max_prefix = max_reps > 0 ? Log2FloorNonZero(max_reps) : 0; + max_prefix = std::min(max_prefix, *max_run_length_prefix); + *max_run_length_prefix = max_prefix; + for (size_t i = 0; i < v_in.size();) { + if (v_in[i] != 0) { + v_out->push_back(v_in[i] + *max_run_length_prefix); + extra_bits->push_back(0); + ++i; + } else { + uint32_t reps = 1; + for (size_t k = i + 1; k < v_in.size() && v_in[k] == 0; ++k) { + ++reps; + } + i += reps; + while (reps != 0) { + if (reps < (2u << max_prefix)) { + uint32_t run_length_prefix = Log2FloorNonZero(reps); + v_out->push_back(run_length_prefix); + extra_bits->push_back(reps - (1u << run_length_prefix)); + break; + } else { + v_out->push_back(max_prefix); + extra_bits->push_back((1u << max_prefix) - 1u); + reps -= (2u << max_prefix) - 1u; + } + } + } + } +} + +void EncodeContextMap(const std::vector<uint32_t>& context_map, + size_t num_clusters, + size_t* storage_ix, uint8_t* storage) { + StoreVarLenUint8(num_clusters - 1, storage_ix, storage); + + if (num_clusters == 1) { + return; + } + + std::vector<uint32_t> transformed_symbols = MoveToFrontTransform(context_map); + std::vector<uint32_t> rle_symbols; + std::vector<uint32_t> extra_bits; + uint32_t max_run_length_prefix = 6; + RunLengthCodeZeros(transformed_symbols, &max_run_length_prefix, + &rle_symbols, &extra_bits); + HistogramContextMap symbol_histogram; + for (size_t i = 0; i < rle_symbols.size(); ++i) { + symbol_histogram.Add(rle_symbols[i]); + } + bool use_rle = max_run_length_prefix > 0; + WriteBits(1, use_rle, storage_ix, storage); + if (use_rle) { + WriteBits(4, max_run_length_prefix - 1, storage_ix, storage); + } + EntropyCodeContextMap symbol_code; + memset(symbol_code.depth_, 0, sizeof(symbol_code.depth_)); + memset(symbol_code.bits_, 0, sizeof(symbol_code.bits_)); + BuildAndStoreHuffmanTree(symbol_histogram.data_, + num_clusters + max_run_length_prefix, + symbol_code.depth_, symbol_code.bits_, + storage_ix, storage); + for (size_t i = 0; i < rle_symbols.size(); ++i) { + WriteBits(symbol_code.depth_[rle_symbols[i]], + symbol_code.bits_[rle_symbols[i]], + storage_ix, storage); + if (rle_symbols[i] > 0 && rle_symbols[i] <= max_run_length_prefix) { + WriteBits(rle_symbols[i], extra_bits[i], storage_ix, storage); + } + } + WriteBits(1, 1, storage_ix, storage); // use move-to-front +} + +void StoreBlockSwitch(const BlockSplitCode& code, + const size_t block_ix, + size_t* storage_ix, + uint8_t* storage) { + if (block_ix > 0) { + size_t typecode = code.type_code[block_ix]; + WriteBits(code.type_depths[typecode], code.type_bits[typecode], + storage_ix, storage); + } + size_t lencode = code.length_prefix[block_ix]; + WriteBits(code.length_depths[lencode], code.length_bits[lencode], + storage_ix, storage); + WriteBits(code.length_nextra[block_ix], code.length_extra[block_ix], + storage_ix, storage); +} + +void BuildAndStoreBlockSplitCode(const std::vector<uint8_t>& types, + const std::vector<uint32_t>& lengths, + const size_t num_types, + BlockSplitCode* code, + size_t* storage_ix, + uint8_t* storage) { + const size_t num_blocks = types.size(); + std::vector<uint32_t> type_histo(num_types + 2); + std::vector<uint32_t> length_histo(26); + size_t last_type = 1; + size_t second_last_type = 0; + code->type_code.resize(num_blocks); + code->length_prefix.resize(num_blocks); + code->length_nextra.resize(num_blocks); + code->length_extra.resize(num_blocks); + code->type_depths.resize(num_types + 2); + code->type_bits.resize(num_types + 2); + code->length_depths.resize(26); + code->length_bits.resize(26); + for (size_t i = 0; i < num_blocks; ++i) { + size_t type = types[i]; + size_t type_code = (type == last_type + 1 ? 1 : + type == second_last_type ? 0 : + type + 2); + second_last_type = last_type; + last_type = type; + code->type_code[i] = static_cast<uint32_t>(type_code); + if (i != 0) ++type_histo[type_code]; + GetBlockLengthPrefixCode(lengths[i], + &code->length_prefix[i], + &code->length_nextra[i], + &code->length_extra[i]); + ++length_histo[code->length_prefix[i]]; + } + StoreVarLenUint8(num_types - 1, storage_ix, storage); + if (num_types > 1) { + BuildAndStoreHuffmanTree(&type_histo[0], num_types + 2, + &code->type_depths[0], &code->type_bits[0], + storage_ix, storage); + BuildAndStoreHuffmanTree(&length_histo[0], 26, + &code->length_depths[0], &code->length_bits[0], + storage_ix, storage); + StoreBlockSwitch(*code, 0, storage_ix, storage); + } +} + +void StoreTrivialContextMap(size_t num_types, + size_t context_bits, + size_t* storage_ix, + uint8_t* storage) { + StoreVarLenUint8(num_types - 1, storage_ix, storage); + if (num_types > 1) { + size_t repeat_code = context_bits - 1u; + size_t repeat_bits = (1u << repeat_code) - 1u; + size_t alphabet_size = num_types + repeat_code; + std::vector<uint32_t> histogram(alphabet_size); + std::vector<uint8_t> depths(alphabet_size); + std::vector<uint16_t> bits(alphabet_size); + // Write RLEMAX. + WriteBits(1, 1, storage_ix, storage); + WriteBits(4, repeat_code - 1, storage_ix, storage); + histogram[repeat_code] = static_cast<uint32_t>(num_types); + histogram[0] = 1; + for (size_t i = context_bits; i < alphabet_size; ++i) { + histogram[i] = 1; + } + BuildAndStoreHuffmanTree(&histogram[0], alphabet_size, + &depths[0], &bits[0], + storage_ix, storage); + for (size_t i = 0; i < num_types; ++i) { + size_t code = (i == 0 ? 0 : i + context_bits - 1); + WriteBits(depths[code], bits[code], storage_ix, storage); + WriteBits(depths[repeat_code], bits[repeat_code], storage_ix, storage); + WriteBits(repeat_code, repeat_bits, storage_ix, storage); + } + // Write IMTF (inverse-move-to-front) bit. + WriteBits(1, 1, storage_ix, storage); + } +} + +// Manages the encoding of one block category (literal, command or distance). +class BlockEncoder { + public: + BlockEncoder(size_t alphabet_size, + size_t num_block_types, + const std::vector<uint8_t>& block_types, + const std::vector<uint32_t>& block_lengths) + : alphabet_size_(alphabet_size), + num_block_types_(num_block_types), + block_types_(block_types), + block_lengths_(block_lengths), + block_ix_(0), + block_len_(block_lengths.empty() ? 0 : block_lengths[0]), + entropy_ix_(0) {} + + // Creates entropy codes of block lengths and block types and stores them + // to the bit stream. + void BuildAndStoreBlockSwitchEntropyCodes(size_t* storage_ix, + uint8_t* storage) { + BuildAndStoreBlockSplitCode( + block_types_, block_lengths_, num_block_types_, + &block_split_code_, storage_ix, storage); + } + + // Creates entropy codes for all block types and stores them to the bit + // stream. + template<int kSize> + void BuildAndStoreEntropyCodes( + const std::vector<Histogram<kSize> >& histograms, + size_t* storage_ix, uint8_t* storage) { + depths_.resize(histograms.size() * alphabet_size_); + bits_.resize(histograms.size() * alphabet_size_); + for (size_t i = 0; i < histograms.size(); ++i) { + size_t ix = i * alphabet_size_; + BuildAndStoreHuffmanTree(&histograms[i].data_[0], alphabet_size_, + &depths_[ix], &bits_[ix], + storage_ix, storage); + } + } + + // Stores the next symbol with the entropy code of the current block type. + // Updates the block type and block length at block boundaries. + void StoreSymbol(size_t symbol, size_t* storage_ix, uint8_t* storage) { + if (block_len_ == 0) { + ++block_ix_; + block_len_ = block_lengths_[block_ix_]; + entropy_ix_ = block_types_[block_ix_] * alphabet_size_; + StoreBlockSwitch(block_split_code_, block_ix_, storage_ix, storage); + } + --block_len_; + size_t ix = entropy_ix_ + symbol; + WriteBits(depths_[ix], bits_[ix], storage_ix, storage); + } + + // Stores the next symbol with the entropy code of the current block type and + // context value. + // Updates the block type and block length at block boundaries. + template<int kContextBits> + void StoreSymbolWithContext(size_t symbol, size_t context, + const std::vector<uint32_t>& context_map, + size_t* storage_ix, uint8_t* storage) { + if (block_len_ == 0) { + ++block_ix_; + block_len_ = block_lengths_[block_ix_]; + size_t block_type = block_types_[block_ix_]; + entropy_ix_ = block_type << kContextBits; + StoreBlockSwitch(block_split_code_, block_ix_, storage_ix, storage); + } + --block_len_; + size_t histo_ix = context_map[entropy_ix_ + context]; + size_t ix = histo_ix * alphabet_size_ + symbol; + WriteBits(depths_[ix], bits_[ix], storage_ix, storage); + } + + private: + const size_t alphabet_size_; + const size_t num_block_types_; + const std::vector<uint8_t>& block_types_; + const std::vector<uint32_t>& block_lengths_; + BlockSplitCode block_split_code_; + size_t block_ix_; + size_t block_len_; + size_t entropy_ix_; + std::vector<uint8_t> depths_; + std::vector<uint16_t> bits_; +}; + +void JumpToByteBoundary(size_t* storage_ix, uint8_t* storage) { + *storage_ix = (*storage_ix + 7u) & ~7u; + storage[*storage_ix >> 3] = 0; +} + +void StoreMetaBlock(const uint8_t* input, + size_t start_pos, + size_t length, + size_t mask, + uint8_t prev_byte, + uint8_t prev_byte2, + bool is_last, + uint32_t num_direct_distance_codes, + uint32_t distance_postfix_bits, + ContextType literal_context_mode, + const brotli::Command *commands, + size_t n_commands, + const MetaBlockSplit& mb, + size_t *storage_ix, + uint8_t *storage) { + StoreCompressedMetaBlockHeader(is_last, length, storage_ix, storage); + + size_t num_distance_codes = + kNumDistanceShortCodes + num_direct_distance_codes + + (48u << distance_postfix_bits); + + BlockEncoder literal_enc(256, + mb.literal_split.num_types, + mb.literal_split.types, + mb.literal_split.lengths); + BlockEncoder command_enc(kNumCommandPrefixes, + mb.command_split.num_types, + mb.command_split.types, + mb.command_split.lengths); + BlockEncoder distance_enc(num_distance_codes, + mb.distance_split.num_types, + mb.distance_split.types, + mb.distance_split.lengths); + + literal_enc.BuildAndStoreBlockSwitchEntropyCodes(storage_ix, storage); + command_enc.BuildAndStoreBlockSwitchEntropyCodes(storage_ix, storage); + distance_enc.BuildAndStoreBlockSwitchEntropyCodes(storage_ix, storage); + + WriteBits(2, distance_postfix_bits, storage_ix, storage); + WriteBits(4, num_direct_distance_codes >> distance_postfix_bits, + storage_ix, storage); + for (size_t i = 0; i < mb.literal_split.num_types; ++i) { + WriteBits(2, literal_context_mode, storage_ix, storage); + } + + size_t num_literal_histograms = mb.literal_histograms.size(); + if (mb.literal_context_map.empty()) { + StoreTrivialContextMap(num_literal_histograms, kLiteralContextBits, + storage_ix, storage); + } else { + EncodeContextMap(mb.literal_context_map, num_literal_histograms, + storage_ix, storage); + } + + size_t num_dist_histograms = mb.distance_histograms.size(); + if (mb.distance_context_map.empty()) { + StoreTrivialContextMap(num_dist_histograms, kDistanceContextBits, + storage_ix, storage); + } else { + EncodeContextMap(mb.distance_context_map, num_dist_histograms, + storage_ix, storage); + } + + literal_enc.BuildAndStoreEntropyCodes(mb.literal_histograms, + storage_ix, storage); + command_enc.BuildAndStoreEntropyCodes(mb.command_histograms, + storage_ix, storage); + distance_enc.BuildAndStoreEntropyCodes(mb.distance_histograms, + storage_ix, storage); + + size_t pos = start_pos; + for (size_t i = 0; i < n_commands; ++i) { + const Command cmd = commands[i]; + size_t cmd_code = cmd.cmd_prefix_; + uint32_t lennumextra = static_cast<uint32_t>(cmd.cmd_extra_ >> 48); + uint64_t lenextra = cmd.cmd_extra_ & 0xffffffffffffUL; + command_enc.StoreSymbol(cmd_code, storage_ix, storage); + WriteBits(lennumextra, lenextra, storage_ix, storage); + if (mb.literal_context_map.empty()) { + for (size_t j = cmd.insert_len_; j != 0; --j) { + literal_enc.StoreSymbol(input[pos & mask], storage_ix, storage); + ++pos; + } + } else { + for (size_t j = cmd.insert_len_; j != 0; --j) { + size_t context = Context(prev_byte, prev_byte2, literal_context_mode); + uint8_t literal = input[pos & mask]; + literal_enc.StoreSymbolWithContext<kLiteralContextBits>( + literal, context, mb.literal_context_map, storage_ix, storage); + prev_byte2 = prev_byte; + prev_byte = literal; + ++pos; + } + } + pos += cmd.copy_len_; + if (cmd.copy_len_ > 0) { + prev_byte2 = input[(pos - 2) & mask]; + prev_byte = input[(pos - 1) & mask]; + if (cmd.cmd_prefix_ >= 128) { + size_t dist_code = cmd.dist_prefix_; + uint32_t distnumextra = cmd.dist_extra_ >> 24; + uint64_t distextra = cmd.dist_extra_ & 0xffffff; + if (mb.distance_context_map.empty()) { + distance_enc.StoreSymbol(dist_code, storage_ix, storage); + } else { + size_t context = cmd.DistanceContext(); + distance_enc.StoreSymbolWithContext<kDistanceContextBits>( + dist_code, context, mb.distance_context_map, storage_ix, storage); + } + brotli::WriteBits(distnumextra, distextra, storage_ix, storage); + } + } + } + if (is_last) { + JumpToByteBoundary(storage_ix, storage); + } +} + +void BuildHistograms(const uint8_t* input, + size_t start_pos, + size_t mask, + const brotli::Command *commands, + size_t n_commands, + HistogramLiteral* lit_histo, + HistogramCommand* cmd_histo, + HistogramDistance* dist_histo) { + size_t pos = start_pos; + for (size_t i = 0; i < n_commands; ++i) { + const Command cmd = commands[i]; + cmd_histo->Add(cmd.cmd_prefix_); + for (size_t j = cmd.insert_len_; j != 0; --j) { + lit_histo->Add(input[pos & mask]); + ++pos; + } + pos += cmd.copy_len_; + if (cmd.copy_len_ > 0 && cmd.cmd_prefix_ >= 128) { + dist_histo->Add(cmd.dist_prefix_); + } + } +} + +void StoreDataWithHuffmanCodes(const uint8_t* input, + size_t start_pos, + size_t mask, + const brotli::Command *commands, + size_t n_commands, + const uint8_t* lit_depth, + const uint16_t* lit_bits, + const uint8_t* cmd_depth, + const uint16_t* cmd_bits, + const uint8_t* dist_depth, + const uint16_t* dist_bits, + size_t* storage_ix, + uint8_t* storage) { + size_t pos = start_pos; + for (size_t i = 0; i < n_commands; ++i) { + const Command cmd = commands[i]; + const size_t cmd_code = cmd.cmd_prefix_; + const uint32_t lennumextra = static_cast<uint32_t>(cmd.cmd_extra_ >> 48); + const uint64_t lenextra = cmd.cmd_extra_ & 0xffffffffffffUL; + WriteBits(cmd_depth[cmd_code], cmd_bits[cmd_code], storage_ix, storage); + WriteBits(lennumextra, lenextra, storage_ix, storage); + for (size_t j = cmd.insert_len_; j != 0; --j) { + const uint8_t literal = input[pos & mask]; + WriteBits(lit_depth[literal], lit_bits[literal], storage_ix, storage); + ++pos; + } + pos += cmd.copy_len_; + if (cmd.copy_len_ > 0 && cmd.cmd_prefix_ >= 128) { + const size_t dist_code = cmd.dist_prefix_; + const uint32_t distnumextra = cmd.dist_extra_ >> 24; + const uint32_t distextra = cmd.dist_extra_ & 0xffffff; + WriteBits(dist_depth[dist_code], dist_bits[dist_code], + storage_ix, storage); + WriteBits(distnumextra, distextra, storage_ix, storage); + } + } +} + +void StoreMetaBlockTrivial(const uint8_t* input, + size_t start_pos, + size_t length, + size_t mask, + bool is_last, + const brotli::Command *commands, + size_t n_commands, + size_t *storage_ix, + uint8_t *storage) { + StoreCompressedMetaBlockHeader(is_last, length, storage_ix, storage); + + HistogramLiteral lit_histo; + HistogramCommand cmd_histo; + HistogramDistance dist_histo; + + BuildHistograms(input, start_pos, mask, commands, n_commands, + &lit_histo, &cmd_histo, &dist_histo); + + WriteBits(13, 0, storage_ix, storage); + + std::vector<uint8_t> lit_depth(256); + std::vector<uint16_t> lit_bits(256); + std::vector<uint8_t> cmd_depth(kNumCommandPrefixes); + std::vector<uint16_t> cmd_bits(kNumCommandPrefixes); + std::vector<uint8_t> dist_depth(64); + std::vector<uint16_t> dist_bits(64); + + BuildAndStoreHuffmanTree(&lit_histo.data_[0], 256, + &lit_depth[0], &lit_bits[0], + storage_ix, storage); + BuildAndStoreHuffmanTree(&cmd_histo.data_[0], kNumCommandPrefixes, + &cmd_depth[0], &cmd_bits[0], + storage_ix, storage); + BuildAndStoreHuffmanTree(&dist_histo.data_[0], 64, + &dist_depth[0], &dist_bits[0], + storage_ix, storage); + StoreDataWithHuffmanCodes(input, start_pos, mask, commands, + n_commands, &lit_depth[0], &lit_bits[0], + &cmd_depth[0], &cmd_bits[0], + &dist_depth[0], &dist_bits[0], + storage_ix, storage); + if (is_last) { + JumpToByteBoundary(storage_ix, storage); + } +} + +void StoreMetaBlockFast(const uint8_t* input, + size_t start_pos, + size_t length, + size_t mask, + bool is_last, + const brotli::Command *commands, + size_t n_commands, + size_t *storage_ix, + uint8_t *storage) { + StoreCompressedMetaBlockHeader(is_last, length, storage_ix, storage); + + WriteBits(13, 0, storage_ix, storage); + + if (n_commands <= 128) { + uint32_t histogram[256] = { 0 }; + size_t pos = start_pos; + size_t num_literals = 0; + for (size_t i = 0; i < n_commands; ++i) { + const Command cmd = commands[i]; + for (size_t j = cmd.insert_len_; j != 0; --j) { + ++histogram[input[pos & mask]]; + ++pos; + } + num_literals += cmd.insert_len_; + pos += cmd.copy_len_; + } + uint8_t lit_depth[256] = { 0 }; + uint16_t lit_bits[256] = { 0 }; + BuildAndStoreHuffmanTreeFast(histogram, num_literals, + /* max_bits = */ 8, + lit_depth, lit_bits, + storage_ix, storage); + StoreStaticCommandHuffmanTree(storage_ix, storage); + StoreStaticDistanceHuffmanTree(storage_ix, storage); + StoreDataWithHuffmanCodes(input, start_pos, mask, commands, + n_commands, &lit_depth[0], &lit_bits[0], + kStaticCommandCodeDepth, + kStaticCommandCodeBits, + kStaticDistanceCodeDepth, + kStaticDistanceCodeBits, + storage_ix, storage); + } else { + HistogramLiteral lit_histo; + HistogramCommand cmd_histo; + HistogramDistance dist_histo; + BuildHistograms(input, start_pos, mask, commands, n_commands, + &lit_histo, &cmd_histo, &dist_histo); + std::vector<uint8_t> lit_depth(256); + std::vector<uint16_t> lit_bits(256); + std::vector<uint8_t> cmd_depth(kNumCommandPrefixes); + std::vector<uint16_t> cmd_bits(kNumCommandPrefixes); + std::vector<uint8_t> dist_depth(64); + std::vector<uint16_t> dist_bits(64); + BuildAndStoreHuffmanTreeFast(&lit_histo.data_[0], lit_histo.total_count_, + /* max_bits = */ 8, + &lit_depth[0], &lit_bits[0], + storage_ix, storage); + BuildAndStoreHuffmanTreeFast(&cmd_histo.data_[0], cmd_histo.total_count_, + /* max_bits = */ 10, + &cmd_depth[0], &cmd_bits[0], + storage_ix, storage); + BuildAndStoreHuffmanTreeFast(&dist_histo.data_[0], dist_histo.total_count_, + /* max_bits = */ 6, + &dist_depth[0], &dist_bits[0], + storage_ix, storage); + StoreDataWithHuffmanCodes(input, start_pos, mask, commands, + n_commands, &lit_depth[0], &lit_bits[0], + &cmd_depth[0], &cmd_bits[0], + &dist_depth[0], &dist_bits[0], + storage_ix, storage); + } + + if (is_last) { + JumpToByteBoundary(storage_ix, storage); + } +} + +// This is for storing uncompressed blocks (simple raw storage of +// bytes-as-bytes). +void StoreUncompressedMetaBlock(bool final_block, + const uint8_t * __restrict input, + size_t position, size_t mask, + size_t len, + size_t * __restrict storage_ix, + uint8_t * __restrict storage) { + StoreUncompressedMetaBlockHeader(len, storage_ix, storage); + JumpToByteBoundary(storage_ix, storage); + + size_t masked_pos = position & mask; + if (masked_pos + len > mask + 1) { + size_t len1 = mask + 1 - masked_pos; + memcpy(&storage[*storage_ix >> 3], &input[masked_pos], len1); + *storage_ix += len1 << 3; + len -= len1; + masked_pos = 0; + } + memcpy(&storage[*storage_ix >> 3], &input[masked_pos], len); + *storage_ix += len << 3; + + // We need to clear the next 4 bytes to continue to be + // compatible with WriteBits. + brotli::WriteBitsPrepareStorage(*storage_ix, storage); + + // Since the uncompressed block itself may not be the final block, add an + // empty one after this. + if (final_block) { + brotli::WriteBits(1, 1, storage_ix, storage); // islast + brotli::WriteBits(1, 1, storage_ix, storage); // isempty + JumpToByteBoundary(storage_ix, storage); + } +} + +void StoreSyncMetaBlock(size_t * __restrict storage_ix, + uint8_t * __restrict storage) { + // Empty metadata meta-block bit pattern: + // 1 bit: is_last (0) + // 2 bits: num nibbles (3) + // 1 bit: reserved (0) + // 2 bits: metadata length bytes (0) + WriteBits(6, 6, storage_ix, storage); + JumpToByteBoundary(storage_ix, storage); +} + +} // namespace brotli |