Index: third_party/brotli/enc/compress_fragment.cc |
diff --git a/third_party/brotli/enc/compress_fragment.cc b/third_party/brotli/enc/compress_fragment.cc |
deleted file mode 100644 |
index 5620112ac020158bc63e0582a46bf9b3c35de18e..0000000000000000000000000000000000000000 |
--- a/third_party/brotli/enc/compress_fragment.cc |
+++ /dev/null |
@@ -1,701 +0,0 @@ |
-/* Copyright 2015 Google Inc. All Rights Reserved. |
- |
- Distributed under MIT license. |
- See file LICENSE for detail or copy at https://opensource.org/licenses/MIT |
-*/ |
- |
-// Function for fast encoding of an input fragment, independently from the input |
-// history. This function uses one-pass processing: when we find a backward |
-// match, we immediately emit the corresponding command and literal codes to |
-// the bit stream. |
-// |
-// Adapted from the CompressFragment() function in |
-// https://github.com/google/snappy/blob/master/snappy.cc |
- |
-#include "./compress_fragment.h" |
- |
-#include <algorithm> |
-#include <cstring> |
- |
-#include "./brotli_bit_stream.h" |
-#include "./entropy_encode.h" |
-#include "./fast_log.h" |
-#include "./find_match_length.h" |
-#include "./port.h" |
-#include "./types.h" |
-#include "./write_bits.h" |
- |
-namespace brotli { |
- |
-// kHashMul32 multiplier has these properties: |
-// * The multiplier must be odd. Otherwise we may lose the highest bit. |
-// * No long streaks of 1s or 0s. |
-// * There is no effort to ensure that it is a prime, the oddity is enough |
-// for this use. |
-// * The number has been tuned heuristically against compression benchmarks. |
-static const uint32_t kHashMul32 = 0x1e35a7bd; |
- |
-static inline uint32_t Hash(const uint8_t* p, size_t shift) { |
- const uint64_t h = (BROTLI_UNALIGNED_LOAD64(p) << 24) * kHashMul32; |
- return static_cast<uint32_t>(h >> shift); |
-} |
- |
-static inline uint32_t HashBytesAtOffset(uint64_t v, int offset, size_t shift) { |
- assert(offset >= 0); |
- assert(offset <= 3); |
- const uint64_t h = ((v >> (8 * offset)) << 24) * kHashMul32; |
- return static_cast<uint32_t>(h >> shift); |
-} |
- |
-static inline int IsMatch(const uint8_t* p1, const uint8_t* p2) { |
- return (BROTLI_UNALIGNED_LOAD32(p1) == BROTLI_UNALIGNED_LOAD32(p2) && |
- p1[4] == p2[4]); |
-} |
- |
-// Builds a literal prefix code into "depths" and "bits" based on the statistics |
-// of the "input" string and stores it into the bit stream. |
-// Note that the prefix code here is built from the pre-LZ77 input, therefore |
-// we can only approximate the statistics of the actual literal stream. |
-// Moreover, for long inputs we build a histogram from a sample of the input |
-// and thus have to assign a non-zero depth for each literal. |
-static void BuildAndStoreLiteralPrefixCode(const uint8_t* input, |
- const size_t input_size, |
- uint8_t depths[256], |
- uint16_t bits[256], |
- size_t* storage_ix, |
- uint8_t* storage) { |
- uint32_t histogram[256] = { 0 }; |
- size_t histogram_total; |
- if (input_size < (1 << 15)) { |
- for (size_t i = 0; i < input_size; ++i) { |
- ++histogram[input[i]]; |
- } |
- histogram_total = input_size; |
- for (size_t i = 0; i < 256; ++i) { |
- // We weigh the first 11 samples with weight 3 to account for the |
- // balancing effect of the LZ77 phase on the histogram. |
- const uint32_t adjust = 2 * std::min(histogram[i], 11u); |
- histogram[i] += adjust; |
- histogram_total += adjust; |
- } |
- } else { |
- static const size_t kSampleRate = 29; |
- for (size_t i = 0; i < input_size; i += kSampleRate) { |
- ++histogram[input[i]]; |
- } |
- histogram_total = (input_size + kSampleRate - 1) / kSampleRate; |
- for (size_t i = 0; i < 256; ++i) { |
- // We add 1 to each population count to avoid 0 bit depths (since this is |
- // only a sample and we don't know if the symbol appears or not), and we |
- // weigh the first 11 samples with weight 3 to account for the balancing |
- // effect of the LZ77 phase on the histogram (more frequent symbols are |
- // more likely to be in backward references instead as literals). |
- const uint32_t adjust = 1 + 2 * std::min(histogram[i], 11u); |
- histogram[i] += adjust; |
- histogram_total += adjust; |
- } |
- } |
- BuildAndStoreHuffmanTreeFast(histogram, histogram_total, |
- /* max_bits = */ 8, |
- depths, bits, storage_ix, storage); |
-} |
- |
-// Builds a command and distance prefix code (each 64 symbols) into "depth" and |
-// "bits" based on "histogram" and stores it into the bit stream. |
-static void BuildAndStoreCommandPrefixCode(const uint32_t histogram[128], |
- uint8_t depth[128], |
- uint16_t bits[128], |
- size_t* storage_ix, |
- uint8_t* storage) { |
- // Tree size for building a tree over 64 symbols is 2 * 64 + 1. |
- static const size_t kTreeSize = 129; |
- HuffmanTree tree[kTreeSize]; |
- CreateHuffmanTree(histogram, 64, 15, tree, depth); |
- CreateHuffmanTree(&histogram[64], 64, 14, tree, &depth[64]); |
- // We have to jump through a few hoopes here in order to compute |
- // the command bits because the symbols are in a different order than in |
- // the full alphabet. This looks complicated, but having the symbols |
- // in this order in the command bits saves a few branches in the Emit* |
- // functions. |
- uint8_t cmd_depth[64]; |
- uint16_t cmd_bits[64]; |
- memcpy(cmd_depth, depth, 24); |
- memcpy(cmd_depth + 24, depth + 40, 8); |
- memcpy(cmd_depth + 32, depth + 24, 8); |
- memcpy(cmd_depth + 40, depth + 48, 8); |
- memcpy(cmd_depth + 48, depth + 32, 8); |
- memcpy(cmd_depth + 56, depth + 56, 8); |
- ConvertBitDepthsToSymbols(cmd_depth, 64, cmd_bits); |
- memcpy(bits, cmd_bits, 48); |
- memcpy(bits + 24, cmd_bits + 32, 16); |
- memcpy(bits + 32, cmd_bits + 48, 16); |
- memcpy(bits + 40, cmd_bits + 24, 16); |
- memcpy(bits + 48, cmd_bits + 40, 16); |
- memcpy(bits + 56, cmd_bits + 56, 16); |
- ConvertBitDepthsToSymbols(&depth[64], 64, &bits[64]); |
- { |
- // Create the bit length array for the full command alphabet. |
- uint8_t cmd_depth[704] = { 0 }; |
- memcpy(cmd_depth, depth, 8); |
- memcpy(cmd_depth + 64, depth + 8, 8); |
- memcpy(cmd_depth + 128, depth + 16, 8); |
- memcpy(cmd_depth + 192, depth + 24, 8); |
- memcpy(cmd_depth + 384, depth + 32, 8); |
- for (size_t i = 0; i < 8; ++i) { |
- cmd_depth[128 + 8 * i] = depth[40 + i]; |
- cmd_depth[256 + 8 * i] = depth[48 + i]; |
- cmd_depth[448 + 8 * i] = depth[56 + i]; |
- } |
- StoreHuffmanTree(cmd_depth, 704, tree, storage_ix, storage); |
- } |
- StoreHuffmanTree(&depth[64], 64, tree, storage_ix, storage); |
-} |
- |
-// REQUIRES: insertlen < 6210 |
-inline void EmitInsertLen(size_t insertlen, |
- const uint8_t depth[128], |
- const uint16_t bits[128], |
- uint32_t histo[128], |
- size_t* storage_ix, |
- uint8_t* storage) { |
- if (insertlen < 6) { |
- const size_t code = insertlen + 40; |
- WriteBits(depth[code], bits[code], storage_ix, storage); |
- ++histo[code]; |
- } else if (insertlen < 130) { |
- insertlen -= 2; |
- const uint32_t nbits = Log2FloorNonZero(insertlen) - 1u; |
- const size_t prefix = insertlen >> nbits; |
- const size_t inscode = (nbits << 1) + prefix + 42; |
- WriteBits(depth[inscode], bits[inscode], storage_ix, storage); |
- WriteBits(nbits, insertlen - (prefix << nbits), storage_ix, storage); |
- ++histo[inscode]; |
- } else if (insertlen < 2114) { |
- insertlen -= 66; |
- const uint32_t nbits = Log2FloorNonZero(insertlen); |
- const size_t code = nbits + 50; |
- WriteBits(depth[code], bits[code], storage_ix, storage); |
- WriteBits(nbits, insertlen - (1 << nbits), storage_ix, storage); |
- ++histo[code]; |
- } else { |
- WriteBits(depth[61], bits[61], storage_ix, storage); |
- WriteBits(12, insertlen - 2114, storage_ix, storage); |
- ++histo[21]; |
- } |
-} |
- |
-inline void EmitLongInsertLen(size_t insertlen, |
- const uint8_t depth[128], |
- const uint16_t bits[128], |
- uint32_t histo[128], |
- size_t* storage_ix, |
- uint8_t* storage) { |
- if (insertlen < 22594) { |
- WriteBits(depth[62], bits[62], storage_ix, storage); |
- WriteBits(14, insertlen - 6210, storage_ix, storage); |
- ++histo[22]; |
- } else { |
- WriteBits(depth[63], bits[63], storage_ix, storage); |
- WriteBits(24, insertlen - 22594, storage_ix, storage); |
- ++histo[23]; |
- } |
-} |
- |
-inline void EmitCopyLen(size_t copylen, |
- const uint8_t depth[128], |
- const uint16_t bits[128], |
- uint32_t histo[128], |
- size_t* storage_ix, |
- uint8_t* storage) { |
- if (copylen < 10) { |
- WriteBits(depth[copylen + 14], bits[copylen + 14], storage_ix, storage); |
- ++histo[copylen + 14]; |
- } else if (copylen < 134) { |
- copylen -= 6; |
- const uint32_t nbits = Log2FloorNonZero(copylen) - 1u; |
- const size_t prefix = copylen >> nbits; |
- const size_t code = (nbits << 1) + prefix + 20; |
- WriteBits(depth[code], bits[code], storage_ix, storage); |
- WriteBits(nbits, copylen - (prefix << nbits), storage_ix, storage); |
- ++histo[code]; |
- } else if (copylen < 2118) { |
- copylen -= 70; |
- const uint32_t nbits = Log2FloorNonZero(copylen); |
- const size_t code = nbits + 28; |
- WriteBits(depth[code], bits[code], storage_ix, storage); |
- WriteBits(nbits, copylen - (1 << nbits), storage_ix, storage); |
- ++histo[code]; |
- } else { |
- WriteBits(depth[39], bits[39], storage_ix, storage); |
- WriteBits(24, copylen - 2118, storage_ix, storage); |
- ++histo[47]; |
- } |
-} |
- |
-inline void EmitCopyLenLastDistance(size_t copylen, |
- const uint8_t depth[128], |
- const uint16_t bits[128], |
- uint32_t histo[128], |
- size_t* storage_ix, |
- uint8_t* storage) { |
- if (copylen < 12) { |
- WriteBits(depth[copylen - 4], bits[copylen - 4], storage_ix, storage); |
- ++histo[copylen - 4]; |
- } else if (copylen < 72) { |
- copylen -= 8; |
- const uint32_t nbits = Log2FloorNonZero(copylen) - 1; |
- const size_t prefix = copylen >> nbits; |
- const size_t code = (nbits << 1) + prefix + 4; |
- WriteBits(depth[code], bits[code], storage_ix, storage); |
- WriteBits(nbits, copylen - (prefix << nbits), storage_ix, storage); |
- ++histo[code]; |
- } else if (copylen < 136) { |
- copylen -= 8; |
- const size_t code = (copylen >> 5) + 30; |
- WriteBits(depth[code], bits[code], storage_ix, storage); |
- WriteBits(5, copylen & 31, storage_ix, storage); |
- WriteBits(depth[64], bits[64], storage_ix, storage); |
- ++histo[code]; |
- ++histo[64]; |
- } else if (copylen < 2120) { |
- copylen -= 72; |
- const uint32_t nbits = Log2FloorNonZero(copylen); |
- const size_t code = nbits + 28; |
- WriteBits(depth[code], bits[code], storage_ix, storage); |
- WriteBits(nbits, copylen - (1 << nbits), storage_ix, storage); |
- WriteBits(depth[64], bits[64], storage_ix, storage); |
- ++histo[code]; |
- ++histo[64]; |
- } else { |
- WriteBits(depth[39], bits[39], storage_ix, storage); |
- WriteBits(24, copylen - 2120, storage_ix, storage); |
- WriteBits(depth[64], bits[64], storage_ix, storage); |
- ++histo[47]; |
- ++histo[64]; |
- } |
-} |
- |
-inline void EmitDistance(size_t distance, |
- const uint8_t depth[128], |
- const uint16_t bits[128], |
- uint32_t histo[128], |
- size_t* storage_ix, uint8_t* storage) { |
- distance += 3; |
- const uint32_t nbits = Log2FloorNonZero(distance) - 1u; |
- const size_t prefix = (distance >> nbits) & 1; |
- const size_t offset = (2 + prefix) << nbits; |
- const size_t distcode = 2 * (nbits - 1) + prefix + 80; |
- WriteBits(depth[distcode], bits[distcode], storage_ix, storage); |
- WriteBits(nbits, distance - offset, storage_ix, storage); |
- ++histo[distcode]; |
-} |
- |
-inline void EmitLiterals(const uint8_t* input, const size_t len, |
- const uint8_t depth[256], const uint16_t bits[256], |
- size_t* storage_ix, uint8_t* storage) { |
- for (size_t j = 0; j < len; j++) { |
- const uint8_t lit = input[j]; |
- WriteBits(depth[lit], bits[lit], storage_ix, storage); |
- } |
-} |
- |
-// REQUIRES: len <= 1 << 20. |
-static void StoreMetaBlockHeader( |
- size_t len, bool is_uncompressed, size_t* storage_ix, uint8_t* storage) { |
- // ISLAST |
- WriteBits(1, 0, storage_ix, storage); |
- if (len <= (1U << 16)) { |
- // MNIBBLES is 4 |
- WriteBits(2, 0, storage_ix, storage); |
- WriteBits(16, len - 1, storage_ix, storage); |
- } else { |
- // MNIBBLES is 5 |
- WriteBits(2, 1, storage_ix, storage); |
- WriteBits(20, len - 1, storage_ix, storage); |
- } |
- // ISUNCOMPRESSED |
- WriteBits(1, is_uncompressed, storage_ix, storage); |
-} |
- |
-static void UpdateBits(size_t n_bits, |
- uint32_t bits, |
- size_t pos, |
- uint8_t *array) { |
- while (n_bits > 0) { |
- size_t byte_pos = pos >> 3; |
- size_t n_unchanged_bits = pos & 7; |
- size_t n_changed_bits = std::min(n_bits, 8 - n_unchanged_bits); |
- size_t total_bits = n_unchanged_bits + n_changed_bits; |
- uint32_t mask = (~((1 << total_bits) - 1)) | ((1 << n_unchanged_bits) - 1); |
- uint32_t unchanged_bits = array[byte_pos] & mask; |
- uint32_t changed_bits = bits & ((1 << n_changed_bits) - 1); |
- array[byte_pos] = |
- static_cast<uint8_t>((changed_bits << n_unchanged_bits) | |
- unchanged_bits); |
- n_bits -= n_changed_bits; |
- bits >>= n_changed_bits; |
- pos += n_changed_bits; |
- } |
-} |
- |
-static void RewindBitPosition(const size_t new_storage_ix, |
- size_t* storage_ix, uint8_t* storage) { |
- const size_t bitpos = new_storage_ix & 7; |
- const size_t mask = (1u << bitpos) - 1; |
- storage[new_storage_ix >> 3] &= static_cast<uint8_t>(mask); |
- *storage_ix = new_storage_ix; |
-} |
- |
-static bool ShouldMergeBlock(const uint8_t* data, size_t len, |
- const uint8_t* depths) { |
- size_t histo[256] = { 0 }; |
- static const size_t kSampleRate = 43; |
- for (size_t i = 0; i < len; i += kSampleRate) { |
- ++histo[data[i]]; |
- } |
- const size_t total = (len + kSampleRate - 1) / kSampleRate; |
- double r = (FastLog2(total) + 0.5) * static_cast<double>(total) + 200; |
- for (size_t i = 0; i < 256; ++i) { |
- r -= static_cast<double>(histo[i]) * (depths[i] + FastLog2(histo[i])); |
- } |
- return r >= 0.0; |
-} |
- |
-inline bool ShouldUseUncompressedMode(const uint8_t* metablock_start, |
- const uint8_t* next_emit, |
- const size_t insertlen, |
- const uint8_t literal_depths[256]) { |
- const size_t compressed = static_cast<size_t>(next_emit - metablock_start); |
- if (compressed * 50 > insertlen) { |
- return false; |
- } |
- static const double kAcceptableLossForUncompressibleSpeedup = 0.02; |
- static const double kMinEntropy = |
- 8 * (1.0 - kAcceptableLossForUncompressibleSpeedup); |
- uint32_t sum = 0; |
- for (int i = 0; i < 256; ++i) { |
- const uint32_t n = literal_depths[i]; |
- sum += n << (15 - n); |
- } |
- return sum > static_cast<uint32_t>((1 << 15) * kMinEntropy); |
-} |
- |
-static void EmitUncompressedMetaBlock(const uint8_t* begin, const uint8_t* end, |
- const size_t storage_ix_start, |
- size_t* storage_ix, uint8_t* storage) { |
- const size_t len = static_cast<size_t>(end - begin); |
- RewindBitPosition(storage_ix_start, storage_ix, storage); |
- StoreMetaBlockHeader(len, 1, storage_ix, storage); |
- *storage_ix = (*storage_ix + 7u) & ~7u; |
- memcpy(&storage[*storage_ix >> 3], begin, len); |
- *storage_ix += len << 3; |
- storage[*storage_ix >> 3] = 0; |
-} |
- |
-void BrotliCompressFragmentFast(const uint8_t* input, size_t input_size, |
- bool is_last, |
- int* table, size_t table_size, |
- uint8_t cmd_depth[128], uint16_t cmd_bits[128], |
- size_t* cmd_code_numbits, uint8_t* cmd_code, |
- size_t* storage_ix, uint8_t* storage) { |
- if (input_size == 0) { |
- assert(is_last); |
- WriteBits(1, 1, storage_ix, storage); // islast |
- WriteBits(1, 1, storage_ix, storage); // isempty |
- *storage_ix = (*storage_ix + 7u) & ~7u; |
- return; |
- } |
- |
- // "next_emit" is a pointer to the first byte that is not covered by a |
- // previous copy. Bytes between "next_emit" and the start of the next copy or |
- // the end of the input will be emitted as literal bytes. |
- const uint8_t* next_emit = input; |
- // Save the start of the first block for position and distance computations. |
- const uint8_t* base_ip = input; |
- |
- static const size_t kFirstBlockSize = 3 << 15; |
- static const size_t kMergeBlockSize = 1 << 16; |
- |
- const uint8_t* metablock_start = input; |
- size_t block_size = std::min(input_size, kFirstBlockSize); |
- size_t total_block_size = block_size; |
- // Save the bit position of the MLEN field of the meta-block header, so that |
- // we can update it later if we decide to extend this meta-block. |
- size_t mlen_storage_ix = *storage_ix + 3; |
- StoreMetaBlockHeader(block_size, 0, storage_ix, storage); |
- // No block splits, no contexts. |
- WriteBits(13, 0, storage_ix, storage); |
- |
- uint8_t lit_depth[256] = { 0 }; |
- uint16_t lit_bits[256] = { 0 }; |
- BuildAndStoreLiteralPrefixCode(input, block_size, lit_depth, lit_bits, |
- storage_ix, storage); |
- |
- // Store the pre-compressed command and distance prefix codes. |
- for (size_t i = 0; i + 7 < *cmd_code_numbits; i += 8) { |
- WriteBits(8, cmd_code[i >> 3], storage_ix, storage); |
- } |
- WriteBits(*cmd_code_numbits & 7, cmd_code[*cmd_code_numbits >> 3], |
- storage_ix, storage); |
- |
- emit_commands: |
- // Initialize the command and distance histograms. We will gather |
- // statistics of command and distance codes during the processing |
- // of this block and use it to update the command and distance |
- // prefix codes for the next block. |
- uint32_t cmd_histo[128] = { |
- 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, |
- 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, |
- 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, |
- 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, |
- 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, |
- 1, 1, 1, 1, 0, 0, 0, 0, |
- }; |
- |
- // "ip" is the input pointer. |
- const uint8_t* ip = input; |
- assert(table_size); |
- assert(table_size <= (1u << 31)); |
- assert((table_size & (table_size - 1)) == 0); // table must be power of two |
- const size_t shift = 64u - Log2FloorNonZero(table_size); |
- assert(table_size - 1 == static_cast<size_t>( |
- MAKE_UINT64_T(0xFFFFFFFF, 0xFFFFFF) >> shift)); |
- const uint8_t* ip_end = input + block_size; |
- |
- int last_distance = -1; |
- const size_t kInputMarginBytes = 16; |
- const size_t kMinMatchLen = 5; |
- if (PREDICT_TRUE(block_size >= kInputMarginBytes)) { |
- // For the last block, we need to keep a 16 bytes margin so that we can be |
- // sure that all distances are at most window size - 16. |
- // For all other blocks, we only need to keep a margin of 5 bytes so that |
- // we don't go over the block size with a copy. |
- const size_t len_limit = std::min(block_size - kMinMatchLen, |
- input_size - kInputMarginBytes); |
- const uint8_t* ip_limit = input + len_limit; |
- |
- for (uint32_t next_hash = Hash(++ip, shift); ; ) { |
- assert(next_emit < ip); |
- // Step 1: Scan forward in the input looking for a 5-byte-long match. |
- // If we get close to exhausting the input then goto emit_remainder. |
- // |
- // Heuristic match skipping: If 32 bytes are scanned with no matches |
- // found, start looking only at every other byte. If 32 more bytes are |
- // scanned, look at every third byte, etc.. When a match is found, |
- // immediately go back to looking at every byte. This is a small loss |
- // (~5% performance, ~0.1% density) for compressible data due to more |
- // bookkeeping, but for non-compressible data (such as JPEG) it's a huge |
- // win since the compressor quickly "realizes" the data is incompressible |
- // and doesn't bother looking for matches everywhere. |
- // |
- // The "skip" variable keeps track of how many bytes there are since the |
- // last match; dividing it by 32 (ie. right-shifting by five) gives the |
- // number of bytes to move ahead for each iteration. |
- uint32_t skip = 32; |
- |
- const uint8_t* next_ip = ip; |
- const uint8_t* candidate; |
- do { |
- ip = next_ip; |
- uint32_t hash = next_hash; |
- assert(hash == Hash(ip, shift)); |
- uint32_t bytes_between_hash_lookups = skip++ >> 5; |
- next_ip = ip + bytes_between_hash_lookups; |
- if (PREDICT_FALSE(next_ip > ip_limit)) { |
- goto emit_remainder; |
- } |
- next_hash = Hash(next_ip, shift); |
- candidate = ip - last_distance; |
- if (IsMatch(ip, candidate)) { |
- if (PREDICT_TRUE(candidate < ip)) { |
- table[hash] = static_cast<int>(ip - base_ip); |
- break; |
- } |
- } |
- candidate = base_ip + table[hash]; |
- assert(candidate >= base_ip); |
- assert(candidate < ip); |
- |
- table[hash] = static_cast<int>(ip - base_ip); |
- } while (PREDICT_TRUE(!IsMatch(ip, candidate))); |
- |
- // Step 2: Emit the found match together with the literal bytes from |
- // "next_emit" to the bit stream, and then see if we can find a next macth |
- // immediately afterwards. Repeat until we find no match for the input |
- // without emitting some literal bytes. |
- uint64_t input_bytes; |
- |
- { |
- // We have a 5-byte match at ip, and we need to emit bytes in |
- // [next_emit, ip). |
- const uint8_t* base = ip; |
- size_t matched = 5 + FindMatchLengthWithLimit( |
- candidate + 5, ip + 5, static_cast<size_t>(ip_end - ip) - 5); |
- ip += matched; |
- int distance = static_cast<int>(base - candidate); /* > 0 */ |
- size_t insert = static_cast<size_t>(base - next_emit); |
- assert(0 == memcmp(base, candidate, matched)); |
- if (PREDICT_TRUE(insert < 6210)) { |
- EmitInsertLen(insert, cmd_depth, cmd_bits, cmd_histo, |
- storage_ix, storage); |
- } else if (ShouldUseUncompressedMode(metablock_start, next_emit, insert, |
- lit_depth)) { |
- EmitUncompressedMetaBlock(metablock_start, base, mlen_storage_ix - 3, |
- storage_ix, storage); |
- input_size -= static_cast<size_t>(base - input); |
- input = base; |
- next_emit = input; |
- goto next_block; |
- } else { |
- EmitLongInsertLen(insert, cmd_depth, cmd_bits, cmd_histo, |
- storage_ix, storage); |
- } |
- EmitLiterals(next_emit, insert, lit_depth, lit_bits, |
- storage_ix, storage); |
- if (distance == last_distance) { |
- WriteBits(cmd_depth[64], cmd_bits[64], storage_ix, storage); |
- ++cmd_histo[64]; |
- } else { |
- EmitDistance(static_cast<size_t>(distance), cmd_depth, cmd_bits, |
- cmd_histo, storage_ix, storage); |
- last_distance = distance; |
- } |
- EmitCopyLenLastDistance(matched, cmd_depth, cmd_bits, cmd_histo, |
- storage_ix, storage); |
- |
- next_emit = ip; |
- if (PREDICT_FALSE(ip >= ip_limit)) { |
- goto emit_remainder; |
- } |
- // We could immediately start working at ip now, but to improve |
- // compression we first update "table" with the hashes of some positions |
- // within the last copy. |
- input_bytes = BROTLI_UNALIGNED_LOAD64(ip - 3); |
- uint32_t prev_hash = HashBytesAtOffset(input_bytes, 0, shift); |
- table[prev_hash] = static_cast<int>(ip - base_ip - 3); |
- prev_hash = HashBytesAtOffset(input_bytes, 1, shift); |
- table[prev_hash] = static_cast<int>(ip - base_ip - 2); |
- prev_hash = HashBytesAtOffset(input_bytes, 2, shift); |
- table[prev_hash] = static_cast<int>(ip - base_ip - 1); |
- |
- uint32_t cur_hash = HashBytesAtOffset(input_bytes, 3, shift); |
- candidate = base_ip + table[cur_hash]; |
- table[cur_hash] = static_cast<int>(ip - base_ip); |
- } |
- |
- while (IsMatch(ip, candidate)) { |
- // We have a 5-byte match at ip, and no need to emit any literal bytes |
- // prior to ip. |
- const uint8_t* base = ip; |
- size_t matched = 5 + FindMatchLengthWithLimit( |
- candidate + 5, ip + 5, static_cast<size_t>(ip_end - ip) - 5); |
- ip += matched; |
- last_distance = static_cast<int>(base - candidate); /* > 0 */ |
- assert(0 == memcmp(base, candidate, matched)); |
- EmitCopyLen(matched, cmd_depth, cmd_bits, cmd_histo, |
- storage_ix, storage); |
- EmitDistance(static_cast<size_t>(last_distance), cmd_depth, cmd_bits, |
- cmd_histo, storage_ix, storage); |
- |
- next_emit = ip; |
- if (PREDICT_FALSE(ip >= ip_limit)) { |
- goto emit_remainder; |
- } |
- // We could immediately start working at ip now, but to improve |
- // compression we first update "table" with the hashes of some positions |
- // within the last copy. |
- input_bytes = BROTLI_UNALIGNED_LOAD64(ip - 3); |
- uint32_t prev_hash = HashBytesAtOffset(input_bytes, 0, shift); |
- table[prev_hash] = static_cast<int>(ip - base_ip - 3); |
- prev_hash = HashBytesAtOffset(input_bytes, 1, shift); |
- table[prev_hash] = static_cast<int>(ip - base_ip - 2); |
- prev_hash = HashBytesAtOffset(input_bytes, 2, shift); |
- table[prev_hash] = static_cast<int>(ip - base_ip - 1); |
- |
- uint32_t cur_hash = HashBytesAtOffset(input_bytes, 3, shift); |
- candidate = base_ip + table[cur_hash]; |
- table[cur_hash] = static_cast<int>(ip - base_ip); |
- } |
- |
- next_hash = Hash(++ip, shift); |
- } |
- } |
- |
- emit_remainder: |
- assert(next_emit <= ip_end); |
- input += block_size; |
- input_size -= block_size; |
- block_size = std::min(input_size, kMergeBlockSize); |
- |
- // Decide if we want to continue this meta-block instead of emitting the |
- // last insert-only command. |
- if (input_size > 0 && |
- total_block_size + block_size <= (1 << 20) && |
- ShouldMergeBlock(input, block_size, lit_depth)) { |
- assert(total_block_size > (1 << 16)); |
- // Update the size of the current meta-block and continue emitting commands. |
- // We can do this because the current size and the new size both have 5 |
- // nibbles. |
- total_block_size += block_size; |
- UpdateBits(20, static_cast<uint32_t>(total_block_size - 1), |
- mlen_storage_ix, storage); |
- goto emit_commands; |
- } |
- |
- // Emit the remaining bytes as literals. |
- if (next_emit < ip_end) { |
- const size_t insert = static_cast<size_t>(ip_end - next_emit); |
- if (PREDICT_TRUE(insert < 6210)) { |
- EmitInsertLen(insert, cmd_depth, cmd_bits, cmd_histo, |
- storage_ix, storage); |
- EmitLiterals(next_emit, insert, lit_depth, lit_bits, storage_ix, storage); |
- } else if (ShouldUseUncompressedMode(metablock_start, next_emit, insert, |
- lit_depth)) { |
- EmitUncompressedMetaBlock(metablock_start, ip_end, mlen_storage_ix - 3, |
- storage_ix, storage); |
- } else { |
- EmitLongInsertLen(insert, cmd_depth, cmd_bits, cmd_histo, |
- storage_ix, storage); |
- EmitLiterals(next_emit, insert, lit_depth, lit_bits, |
- storage_ix, storage); |
- } |
- } |
- next_emit = ip_end; |
- |
-next_block: |
- // If we have more data, write a new meta-block header and prefix codes and |
- // then continue emitting commands. |
- if (input_size > 0) { |
- metablock_start = input; |
- block_size = std::min(input_size, kFirstBlockSize); |
- total_block_size = block_size; |
- // Save the bit position of the MLEN field of the meta-block header, so that |
- // we can update it later if we decide to extend this meta-block. |
- mlen_storage_ix = *storage_ix + 3; |
- StoreMetaBlockHeader(block_size, 0, storage_ix, storage); |
- // No block splits, no contexts. |
- WriteBits(13, 0, storage_ix, storage); |
- memset(lit_depth, 0, sizeof(lit_depth)); |
- memset(lit_bits, 0, sizeof(lit_bits)); |
- BuildAndStoreLiteralPrefixCode(input, block_size, lit_depth, lit_bits, |
- storage_ix, storage); |
- BuildAndStoreCommandPrefixCode(cmd_histo, cmd_depth, cmd_bits, |
- storage_ix, storage); |
- goto emit_commands; |
- } |
- |
- if (is_last) { |
- WriteBits(1, 1, storage_ix, storage); // islast |
- WriteBits(1, 1, storage_ix, storage); // isempty |
- *storage_ix = (*storage_ix + 7u) & ~7u; |
- } else { |
- // If this is not the last block, update the command and distance prefix |
- // codes for the next block and store the compressed forms. |
- cmd_code[0] = 0; |
- *cmd_code_numbits = 0; |
- BuildAndStoreCommandPrefixCode(cmd_histo, cmd_depth, cmd_bits, |
- cmd_code_numbits, cmd_code); |
- } |
-} |
- |
-} // namespace brotli |