kc3-lang/brotli/enc/encode.cc

• Show log

  Commit

• Hash : dbb53e64
  Author :
  Date : 2016-01-27T09:50:39
  

  Use a hash-to-binary-tree data structure for quality 11 as suggested by Issue #180.
  

Download

• enc/encode.cc

• /* Copyright 2013 Google Inc. All Rights Reserved.
  
     Distributed under MIT license.
     See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
  */
  
  // Implementation of Brotli compressor.
  
  #include "./encode.h"
  
  #include <algorithm>
  #include <cstring>
  #include <limits>
  
  #include "./backward_references.h"
  #include "./bit_cost.h"
  #include "./block_splitter.h"
  #include "./brotli_bit_stream.h"
  #include "./cluster.h"
  #include "./context.h"
  #include "./metablock.h"
  #include "./transform.h"
  #include "./compress_fragment.h"
  #include "./compress_fragment_two_pass.h"
  #include "./entropy_encode.h"
  #include "./fast_log.h"
  #include "./hash.h"
  #include "./histogram.h"
  #include "./prefix.h"
  #include "./utf8_util.h"
  #include "./write_bits.h"
  
  namespace brotli {
  
  static const int kMinQualityForBlockSplit = 4;
  static const int kMinQualityForContextModeling = 5;
  static const int kMinQualityForOptimizeHistograms = 4;
  // For quality 2 there is no block splitting, so we buffer at most this much
  // literals and commands.
  static const int kMaxNumDelayedSymbols = 0x2fff;
  
  #define COPY_ARRAY(dst, src) memcpy(dst, src, sizeof(src));
  
  void RecomputeDistancePrefixes(Command* cmds,
                                 size_t num_commands,
                                 uint32_t num_direct_distance_codes,
                                 uint32_t distance_postfix_bits) {
    if (num_direct_distance_codes == 0 && distance_postfix_bits == 0) {
      return;
    }
    for (size_t i = 0; i < num_commands; ++i) {
      Command* cmd = &cmds[i];
      if (cmd->copy_len_ > 0 && cmd->cmd_prefix_ >= 128) {
        PrefixEncodeCopyDistance(cmd->DistanceCode(),
                                 num_direct_distance_codes,
                                 distance_postfix_bits,
                                 &cmd->dist_prefix_,
                                 &cmd->dist_extra_);
      }
    }
  }
  
  /* Wraps 64-bit input position to 32-bit ringbuffer position preserving
     "not-a-first-lap" feature. */
  uint32_t WrapPosition(uint64_t position) {
    uint32_t result = static_cast<uint32_t>(position);
    if (position > (1u << 30)) {
      result = (result & ((1u << 30) - 1)) | (1u << 30);
    }
    return result;
  }
  
  uint8_t* BrotliCompressor::GetBrotliStorage(size_t size) {
    if (storage_size_ < size) {
      delete[] storage_;
      storage_ = new uint8_t[size];
      storage_size_ = size;
    }
    return storage_;
  }
  
  size_t MaxHashTableSize(int quality) {
    return quality == 0 ? 1 << 15 : 1 << 17;
  }
  
  size_t HashTableSize(size_t max_table_size, size_t input_size) {
    size_t htsize = 256;
    while (htsize < max_table_size && htsize < input_size) {
      htsize <<= 1;
    }
    return htsize;
  }
  
  int* BrotliCompressor::GetHashTable(int quality,
                                      size_t input_size,
                                      size_t* table_size) {
    // Use smaller hash table when input.size() is smaller, since we
    // fill the table, incurring O(hash table size) overhead for
    // compression, and if the input is short, we won't need that
    // many hash table entries anyway.
    const size_t max_table_size = MaxHashTableSize(quality);
    assert(max_table_size >= 256);
    size_t htsize = HashTableSize(max_table_size, input_size);
  
    int* table;
    if (htsize <= sizeof(small_table_) / sizeof(small_table_[0])) {
      table = small_table_;
    } else {
      if (large_table_ == NULL) {
        large_table_ = new int[max_table_size];
      }
      table = large_table_;
    }
  
    *table_size = htsize;
    memset(table, 0, htsize * sizeof(*table));
    return table;
  }
  
  void EncodeWindowBits(int lgwin, uint8_t* last_byte, uint8_t* last_byte_bits) {
    if (lgwin == 16) {
      *last_byte = 0;
      *last_byte_bits = 1;
    } else if (lgwin == 17) {
      *last_byte = 1;
      *last_byte_bits = 7;
    } else if (lgwin > 17) {
      *last_byte = static_cast<uint8_t>(((lgwin - 17) << 1) | 1);
      *last_byte_bits = 4;
    } else {
      *last_byte = static_cast<uint8_t>(((lgwin - 8) << 4) | 1);
      *last_byte_bits = 7;
    }
  }
  
  // Initializes the command and distance prefix codes for the first block.
  void InitCommandPrefixCodes(uint8_t cmd_depths[128],
                              uint16_t cmd_bits[128],
                              uint8_t cmd_code[512],
                              size_t* cmd_code_numbits) {
    static const uint8_t kDefaultCommandDepths[128] = {
      0, 4, 4, 5, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8,
      0, 0, 0, 4, 4, 4, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7,
      7, 7, 10, 10, 10, 10, 10, 10, 0, 4, 4, 5, 5, 5, 6, 6,
      7, 8, 8, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
      5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      6, 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4,
      4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 6, 7, 7, 7, 8, 10,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
    };
    static const uint16_t kDefaultCommandBits[128] = {
      0,   0,   8,   9,   3,  35,   7,   71,
      39, 103,  23,  47, 175, 111, 239,   31,
      0,   0,   0,   4,  12,   2,  10,    6,
      13,  29,  11,  43,  27,  59,  87,   55,
      15,  79, 319, 831, 191, 703, 447,  959,
      0,  14,   1,  25,   5,  21,  19,   51,
      119, 159,  95, 223, 479, 991,  63,  575,
      127, 639, 383, 895, 255, 767, 511, 1023,
      14, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      27, 59, 7, 39, 23, 55, 30, 1, 17, 9, 25, 5, 0, 8, 4, 12,
      2, 10, 6, 21, 13, 29, 3, 19, 11, 15, 47, 31, 95, 63, 127, 255,
      767, 2815, 1791, 3839, 511, 2559, 1535, 3583, 1023, 3071, 2047, 4095,
    };
    COPY_ARRAY(cmd_depths, kDefaultCommandDepths);
    COPY_ARRAY(cmd_bits, kDefaultCommandBits);
  
    // Initialize the pre-compressed form of the command and distance prefix
    // codes.
    static const uint8_t kDefaultCommandCode[] = {
      0xff, 0x77, 0xd5, 0xbf, 0xe7, 0xde, 0xea, 0x9e, 0x51, 0x5d, 0xde, 0xc6,
      0x70, 0x57, 0xbc, 0x58, 0x58, 0x58, 0xd8, 0xd8, 0x58, 0xd5, 0xcb, 0x8c,
      0xea, 0xe0, 0xc3, 0x87, 0x1f, 0x83, 0xc1, 0x60, 0x1c, 0x67, 0xb2, 0xaa,
      0x06, 0x83, 0xc1, 0x60, 0x30, 0x18, 0xcc, 0xa1, 0xce, 0x88, 0x54, 0x94,
      0x46, 0xe1, 0xb0, 0xd0, 0x4e, 0xb2, 0xf7, 0x04, 0x00,
    };
    static const int kDefaultCommandCodeNumBits = 448;
    COPY_ARRAY(cmd_code, kDefaultCommandCode);
    *cmd_code_numbits = kDefaultCommandCodeNumBits;
  }
  
  BrotliCompressor::BrotliCompressor(BrotliParams params)
      : params_(params),
        hashers_(new Hashers()),
        input_pos_(0),
        num_commands_(0),
        num_literals_(0),
        last_insert_len_(0),
        last_flush_pos_(0),
        last_processed_pos_(0),
        prev_byte_(0),
        prev_byte2_(0),
        storage_size_(0),
        storage_(0),
        large_table_(NULL),
        cmd_code_numbits_(0),
        command_buf_(NULL),
        literal_buf_(NULL) {
    // Sanitize params.
    params_.quality = std::max(0, params_.quality);
    if (params_.lgwin < kMinWindowBits) {
      params_.lgwin = kMinWindowBits;
    } else if (params_.lgwin > kMaxWindowBits) {
      params_.lgwin = kMaxWindowBits;
    }
    if (params_.quality <= 1) {
      params_.lgblock = params_.lgwin;
    } else if (params_.quality < kMinQualityForBlockSplit) {
      params_.lgblock = 14;
    } else if (params_.lgblock == 0) {
      params_.lgblock = 16;
      if (params_.quality >= 9 && params_.lgwin > params_.lgblock) {
        params_.lgblock = std::min(21, params_.lgwin);
      }
    } else {
      params_.lgblock = std::min(kMaxInputBlockBits,
                                 std::max(kMinInputBlockBits, params_.lgblock));
    }
  
    // Initialize input and literal cost ring buffers.
    // We allocate at least lgwin + 1 bits for the ring buffer so that the newly
    // added block fits there completely and we still get lgwin bits and at least
    // read_block_size_bits + 1 bits because the copy tail length needs to be
    // smaller than ringbuffer size.
    int ringbuffer_bits = std::max(params_.lgwin + 1, params_.lgblock + 1);
    ringbuffer_ = new RingBuffer(ringbuffer_bits, params_.lgblock);
  
    commands_ = 0;
    cmd_alloc_size_ = 0;
  
    // Initialize last byte with stream header.
    EncodeWindowBits(params_.lgwin, &last_byte_, &last_byte_bits_);
  
    // Initialize distance cache.
    dist_cache_[0] = 4;
    dist_cache_[1] = 11;
    dist_cache_[2] = 15;
    dist_cache_[3] = 16;
    // Save the state of the distance cache in case we need to restore it for
    // emitting an uncompressed block.
    memcpy(saved_dist_cache_, dist_cache_, sizeof(dist_cache_));
  
    if (params_.quality == 0) {
      InitCommandPrefixCodes(cmd_depths_, cmd_bits_,
                             cmd_code_, &cmd_code_numbits_);
    } else if (params_.quality == 1) {
      command_buf_ = new uint32_t[kCompressFragmentTwoPassBlockSize];
      literal_buf_ = new uint8_t[kCompressFragmentTwoPassBlockSize];
    }
  
    // Initialize hashers.
    hash_type_ = std::min(10, params_.quality);
    hashers_->Init(hash_type_);
  }
  
  BrotliCompressor::~BrotliCompressor() {
    delete[] storage_;
    free(commands_);
    delete ringbuffer_;
    delete hashers_;
    delete[] large_table_;
    delete[] command_buf_;
    delete[] literal_buf_;
  }
  
  void BrotliCompressor::CopyInputToRingBuffer(const size_t input_size,
                                               const uint8_t* input_buffer) {
    ringbuffer_->Write(input_buffer, input_size);
    input_pos_ += input_size;
  
    // TL;DR: If needed, initialize 7 more bytes in the ring buffer to make the
    // hashing not depend on uninitialized data. This makes compression
    // deterministic and it prevents uninitialized memory warnings in Valgrind.
    // Even without erasing, the output would be valid (but nondeterministic).
    //
    // Background information: The compressor stores short (at most 8 bytes)
    // substrings of the input already read in a hash table, and detects
    // repetitions by looking up such substrings in the hash table. If it
    // can find a substring, it checks whether the substring is really there
    // in the ring buffer (or it's just a hash collision). Should the hash
    // table become corrupt, this check makes sure that the output is
    // still valid, albeit the compression ratio would be bad.
    //
    // The compressor populates the hash table from the ring buffer as it's
    // reading new bytes from the input. However, at the last few indexes of
    // the ring buffer, there are not enough bytes to build full-length
    // substrings from. Since the hash table always contains full-length
    // substrings, we erase with dummy 0s here to make sure that those
    // substrings will contain 0s at the end instead of uninitialized
    // data.
    //
    // Please note that erasing is not necessary (because the
    // memory region is already initialized since he ring buffer
    // has a `tail' that holds a copy of the beginning,) so we
    // skip erasing if we have already gone around at least once in
    // the ring buffer.
    size_t pos = ringbuffer_->position();
    // Only clear during the first round of ringbuffer writes. On
    // subsequent rounds data in the ringbuffer would be affected.
    if (pos <= ringbuffer_->mask()) {
      // This is the first time when the ring buffer is being written.
      // We clear 7 bytes just after the bytes that have been copied from
      // the input buffer.
      //
      // The ringbuffer has a "tail" that holds a copy of the beginning,
      // but only once the ring buffer has been fully written once, i.e.,
      // pos <= mask. For the first time, we need to write values
      // in this tail (where index may be larger than mask), so that
      // we have exactly defined behavior and don't read un-initialized
      // memory. Due to performance reasons, hashing reads data using a
      // LOAD64, which can go 7 bytes beyond the bytes written in the
      // ringbuffer.
      memset(ringbuffer_->start() + pos, 0, 7);
    }
  }
  
  void BrotliCompressor::BrotliSetCustomDictionary(
      const size_t size, const uint8_t* dict) {
    CopyInputToRingBuffer(size, dict);
    last_flush_pos_ = size;
    last_processed_pos_ = size;
    if (size > 0) {
      prev_byte_ = dict[size - 1];
    }
    if (size > 1) {
      prev_byte2_ = dict[size - 2];
    }
    hashers_->PrependCustomDictionary(hash_type_, params_.lgwin, size, dict);
  }
  
  bool BrotliCompressor::WriteBrotliData(const bool is_last,
                                         const bool force_flush,
                                         size_t* out_size,
                                         uint8_t** output) {
    const uint64_t delta = input_pos_ - last_processed_pos_;
    const uint8_t* data = ringbuffer_->start();
    const uint32_t mask = ringbuffer_->mask();
  
    if (delta > input_block_size()) {
      return false;
    }
    const uint32_t bytes = static_cast<uint32_t>(delta);
  
    if (params_.quality <= 1) {
      if (delta == 0 && !is_last) {
        // We have no new input data and we don't have to finish the stream, so
        // nothing to do.
        *out_size = 0;
        return true;
      }
      const size_t max_out_size = 2 * bytes + 500;
      uint8_t* storage = GetBrotliStorage(max_out_size);
      storage[0] = last_byte_;
      size_t storage_ix = last_byte_bits_;
      size_t table_size;
      int* table = GetHashTable(params_.quality, bytes, &table_size);
      if (params_.quality == 0) {
        BrotliCompressFragmentFast(
            &data[WrapPosition(last_processed_pos_) & mask],
            bytes, is_last,
            table, table_size,
            cmd_depths_, cmd_bits_,
            &cmd_code_numbits_, cmd_code_,
            &storage_ix, storage);
      } else {
        BrotliCompressFragmentTwoPass(
            &data[WrapPosition(last_processed_pos_) & mask],
            bytes, is_last,
            command_buf_, literal_buf_,
            table, table_size,
            &storage_ix, storage);
      }
      last_byte_ = storage[storage_ix >> 3];
      last_byte_bits_ = storage_ix & 7u;
      last_processed_pos_ = input_pos_;
      *output = &storage[0];
      *out_size = storage_ix >> 3;
      return true;
    }
  
    // Theoretical max number of commands is 1 per 2 bytes.
    size_t newsize = num_commands_ + bytes / 2 + 1;
    if (newsize > cmd_alloc_size_) {
      // Reserve a bit more memory to allow merging with a next block
      // without realloc: that would impact speed.
      newsize += (bytes / 4) + 16;
      cmd_alloc_size_ = newsize;
      commands_ =
          static_cast<Command*>(realloc(commands_, sizeof(Command) * newsize));
    }
  
    CreateBackwardReferences(bytes, WrapPosition(last_processed_pos_),
                             is_last, data, mask,
                             params_.quality,
                             params_.lgwin,
                             hashers_,
                             hash_type_,
                             dist_cache_,
                             &last_insert_len_,
                             &commands_[num_commands_],
                             &num_commands_,
                             &num_literals_);
  
    size_t max_length = std::min<size_t>(mask + 1, 1u << kMaxInputBlockBits);
    if (!is_last && !force_flush &&
        (params_.quality >= kMinQualityForBlockSplit ||
         (num_literals_ + num_commands_ < kMaxNumDelayedSymbols)) &&
        input_pos_ + input_block_size() <= last_flush_pos_ + max_length) {
      // Merge with next input block. Everything will happen later.
      last_processed_pos_ = input_pos_;
      *out_size = 0;
      return true;
    }
  
    // Create the last insert-only command.
    if (last_insert_len_ > 0) {
      brotli::Command cmd(last_insert_len_);
      commands_[num_commands_++] = cmd;
      num_literals_ += last_insert_len_;
      last_insert_len_ = 0;
    }
  
    WriteMetaBlockInternal(is_last, out_size, output);
    return true;
  }
  
  // Decide about the context map based on the ability of the prediction
  // ability of the previous byte UTF8-prefix on the next byte. The
  // prediction ability is calculated as shannon entropy. Here we need
  // shannon entropy instead of 'BitsEntropy' since the prefix will be
  // encoded with the remaining 6 bits of the following byte, and
  // BitsEntropy will assume that symbol to be stored alone using Huffman
  // coding.
  void ChooseContextMap(int quality,
                        uint32_t* bigram_histo,
                        size_t* num_literal_contexts,
                        const uint32_t** literal_context_map) {
    uint32_t monogram_histo[3] = { 0 };
    uint32_t two_prefix_histo[6] = { 0 };
    size_t total = 0;
    for (size_t i = 0; i < 9; ++i) {
      total += bigram_histo[i];
      monogram_histo[i % 3] += bigram_histo[i];
      size_t j = i;
      if (j >= 6) {
        j -= 6;
      }
      two_prefix_histo[j] += bigram_histo[i];
    }
    size_t dummy;
    double entropy1 = ShannonEntropy(monogram_histo, 3, &dummy);
    double entropy2 = (ShannonEntropy(two_prefix_histo, 3, &dummy) +
                       ShannonEntropy(two_prefix_histo + 3, 3, &dummy));
    double entropy3 = 0;
    for (size_t k = 0; k < 3; ++k) {
      entropy3 += ShannonEntropy(bigram_histo + 3 * k, 3, &dummy);
    }
  
    assert(total != 0);
    double scale = 1.0 / static_cast<double>(total);
    entropy1 *= scale;
    entropy2 *= scale;
    entropy3 *= scale;
  
    static const uint32_t kStaticContextMapContinuation[64] = {
      1, 1, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    };
    static const uint32_t kStaticContextMapSimpleUTF8[64] = {
      0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    };
    if (quality < 7) {
      // 3 context models is a bit slower, don't use it at lower qualities.
      entropy3 = entropy1 * 10;
    }
    // If expected savings by symbol are less than 0.2 bits, skip the
    // context modeling -- in exchange for faster decoding speed.
    if (entropy1 - entropy2 < 0.2 &&
        entropy1 - entropy3 < 0.2) {
      *num_literal_contexts = 1;
    } else if (entropy2 - entropy3 < 0.02) {
      *num_literal_contexts = 2;
      *literal_context_map = kStaticContextMapSimpleUTF8;
    } else {
      *num_literal_contexts = 3;
      *literal_context_map = kStaticContextMapContinuation;
    }
  }
  
  void DecideOverLiteralContextModeling(const uint8_t* input,
                                        size_t start_pos,
                                        size_t length,
                                        size_t mask,
                                        int quality,
                                        ContextType* literal_context_mode,
                                        size_t* num_literal_contexts,
                                        const uint32_t** literal_context_map) {
    if (quality < kMinQualityForContextModeling || length < 64) {
      return;
    }
    // Gather bigram data of the UTF8 byte prefixes. To make the analysis of
    // UTF8 data faster we only examine 64 byte long strides at every 4kB
    // intervals.
    const size_t end_pos = start_pos + length;
    uint32_t bigram_prefix_histo[9] = { 0 };
    for (; start_pos + 64 <= end_pos; start_pos += 4096) {
        static const int lut[4] = { 0, 0, 1, 2 };
      const size_t stride_end_pos = start_pos + 64;
      int prev = lut[input[start_pos & mask] >> 6] * 3;
      for (size_t pos = start_pos + 1; pos < stride_end_pos; ++pos) {
        const uint8_t literal = input[pos & mask];
        ++bigram_prefix_histo[prev + lut[literal >> 6]];
        prev = lut[literal >> 6] * 3;
      }
    }
    *literal_context_mode = CONTEXT_UTF8;
    ChooseContextMap(quality, &bigram_prefix_histo[0], num_literal_contexts,
                     literal_context_map);
  }
  
  void BrotliCompressor::WriteMetaBlockInternal(const bool is_last,
                                                size_t* out_size,
                                                uint8_t** output) {
    if (!is_last && input_pos_ == last_flush_pos_) {
      // We have no new input data and we don't have to finish the stream, so
      // nothing to do.
      *out_size = 0;
      return;
    }
    assert(input_pos_ >= last_flush_pos_);
    assert(input_pos_ > last_flush_pos_ || is_last);
    assert(input_pos_ - last_flush_pos_ <= 1u << 24);
    const uint32_t bytes = static_cast<uint32_t>(input_pos_ - last_flush_pos_);
    const uint8_t* data = ringbuffer_->start();
    const uint32_t mask = ringbuffer_->mask();
    const size_t max_out_size = 2 * bytes + 500;
    uint8_t* storage = GetBrotliStorage(max_out_size);
    storage[0] = last_byte_;
    size_t storage_ix = last_byte_bits_;
  
    bool uncompressed = false;
    if (num_commands_ < (bytes >> 8) + 2) {
      if (num_literals_ > 0.99 * static_cast<double>(bytes)) {
        uint32_t literal_histo[256] = { 0 };
        static const uint32_t kSampleRate = 13;
        static const double kMinEntropy = 7.92;
        const double bit_cost_threshold =
            static_cast<double>(bytes) * kMinEntropy / kSampleRate;
        size_t t = (bytes + kSampleRate - 1) / kSampleRate;
        uint32_t pos = static_cast<uint32_t>(last_flush_pos_);
        for (size_t i = 0; i < t; i++) {
          ++literal_histo[data[pos & mask]];
          pos += kSampleRate;
        }
        if (BitsEntropy(literal_histo, 256) > bit_cost_threshold) {
          uncompressed = true;
        }
      }
    }
  
    if (bytes == 0) {
      // Write the ISLAST and ISEMPTY bits.
      WriteBits(2, 3, &storage_ix, &storage[0]);
      storage_ix = (storage_ix + 7u) & ~7u;
    } else if (uncompressed) {
      // Restore the distance cache, as its last update by
      // CreateBackwardReferences is now unused.
      memcpy(dist_cache_, saved_dist_cache_, sizeof(dist_cache_));
      StoreUncompressedMetaBlock(is_last, data,
                                 WrapPosition(last_flush_pos_), mask, bytes,
                                 &storage_ix,
                                 &storage[0]);
    } else {
      uint32_t num_direct_distance_codes = 0;
      uint32_t distance_postfix_bits = 0;
      if (params_.quality > 9 && params_.mode == BrotliParams::MODE_FONT) {
        num_direct_distance_codes = 12;
        distance_postfix_bits = 1;
        RecomputeDistancePrefixes(commands_,
                                  num_commands_,
                                  num_direct_distance_codes,
                                  distance_postfix_bits);
      }
      if (params_.quality == 2) {
        StoreMetaBlockFast(data, WrapPosition(last_flush_pos_),
                           bytes, mask, is_last,
                           commands_, num_commands_,
                           &storage_ix,
                           &storage[0]);
      } else if (params_.quality < kMinQualityForBlockSplit) {
        StoreMetaBlockTrivial(data, WrapPosition(last_flush_pos_),
                              bytes, mask, is_last,
                              commands_, num_commands_,
                              &storage_ix,
                              &storage[0]);
      } else {
        MetaBlockSplit mb;
        ContextType literal_context_mode = CONTEXT_UTF8;
        if (params_.quality <= 9) {
          size_t num_literal_contexts = 1;
          const uint32_t* literal_context_map = NULL;
          DecideOverLiteralContextModeling(data, WrapPosition(last_flush_pos_),
                                           bytes, mask,
                                           params_.quality,
                                           &literal_context_mode,
                                           &num_literal_contexts,
                                           &literal_context_map);
          if (literal_context_map == NULL) {
            BuildMetaBlockGreedy(data, WrapPosition(last_flush_pos_), mask,
                                 commands_, num_commands_,
                                 &mb);
          } else {
            BuildMetaBlockGreedyWithContexts(data, WrapPosition(last_flush_pos_),
                                             mask,
                                             prev_byte_, prev_byte2_,
                                             literal_context_mode,
                                             num_literal_contexts,
                                             literal_context_map,
                                             commands_, num_commands_,
                                             &mb);
          }
        } else {
          if (!IsMostlyUTF8(
              data, WrapPosition(last_flush_pos_), mask, bytes, kMinUTF8Ratio)) {
            literal_context_mode = CONTEXT_SIGNED;
          }
          BuildMetaBlock(data, WrapPosition(last_flush_pos_), mask,
                         prev_byte_, prev_byte2_,
                         commands_, num_commands_,
                         literal_context_mode,
                         &mb);
        }
        if (params_.quality >= kMinQualityForOptimizeHistograms) {
          OptimizeHistograms(num_direct_distance_codes,
                             distance_postfix_bits,
                             &mb);
        }
        StoreMetaBlock(data, WrapPosition(last_flush_pos_), bytes, mask,
                       prev_byte_, prev_byte2_,
                       is_last,
                       num_direct_distance_codes,
                       distance_postfix_bits,
                       literal_context_mode,
                       commands_, num_commands_,
                       mb,
                       &storage_ix,
                       &storage[0]);
      }
      if (bytes + 4 < (storage_ix >> 3)) {
        // Restore the distance cache and last byte.
        memcpy(dist_cache_, saved_dist_cache_, sizeof(dist_cache_));
        storage[0] = last_byte_;
        storage_ix = last_byte_bits_;
        StoreUncompressedMetaBlock(is_last, data,
                                   WrapPosition(last_flush_pos_), mask,
                                   bytes, &storage_ix, &storage[0]);
      }
    }
    last_byte_ = storage[storage_ix >> 3];
    last_byte_bits_ = storage_ix & 7u;
    last_flush_pos_ = input_pos_;
    last_processed_pos_ = input_pos_;
    prev_byte_ = data[(static_cast<uint32_t>(last_flush_pos_) - 1) & mask];
    prev_byte2_ = data[(static_cast<uint32_t>(last_flush_pos_) - 2) & mask];
    num_commands_ = 0;
    num_literals_ = 0;
    // Save the state of the distance cache in case we need to restore it for
    // emitting an uncompressed block.
    memcpy(saved_dist_cache_, dist_cache_, sizeof(dist_cache_));
    *output = &storage[0];
    *out_size = storage_ix >> 3;
  }
  
  bool BrotliCompressor::WriteMetaBlock(const size_t input_size,
                                        const uint8_t* input_buffer,
                                        const bool is_last,
                                        size_t* encoded_size,
                                        uint8_t* encoded_buffer) {
    CopyInputToRingBuffer(input_size, input_buffer);
    size_t out_size = 0;
    uint8_t* output;
    if (!WriteBrotliData(is_last, /* force_flush = */ true, &out_size, &output) ||
        out_size > *encoded_size) {
      return false;
    }
    if (out_size > 0) {
      memcpy(encoded_buffer, output, out_size);
    }
    *encoded_size = out_size;
    return true;
  }
  
  bool BrotliCompressor::WriteMetadata(const size_t input_size,
                                       const uint8_t* input_buffer,
                                       const bool is_last,
                                       size_t* encoded_size,
                                       uint8_t* encoded_buffer) {
    if (input_size > (1 << 24) || input_size + 6 > *encoded_size) {
      return false;
    }
    uint64_t hdr_buffer_data[2];
    uint8_t* hdr_buffer = reinterpret_cast<uint8_t*>(&hdr_buffer_data[0]);
    size_t storage_ix = last_byte_bits_;
    hdr_buffer[0] = last_byte_;
    WriteBits(1, 0, &storage_ix, hdr_buffer);
    WriteBits(2, 3, &storage_ix, hdr_buffer);
    WriteBits(1, 0, &storage_ix, hdr_buffer);
    if (input_size == 0) {
      WriteBits(2, 0, &storage_ix, hdr_buffer);
      *encoded_size = (storage_ix + 7u) >> 3;
      memcpy(encoded_buffer, hdr_buffer, *encoded_size);
    } else {
      uint32_t nbits = (input_size == 1) ? 0 : (Log2FloorNonZero(
          static_cast<uint32_t>(input_size) - 1) + 1);
      uint32_t nbytes = (nbits + 7) / 8;
      WriteBits(2, nbytes, &storage_ix, hdr_buffer);
      WriteBits(8 * nbytes, input_size - 1, &storage_ix, hdr_buffer);
      size_t hdr_size = (storage_ix + 7u) >> 3;
      memcpy(encoded_buffer, hdr_buffer, hdr_size);
      memcpy(&encoded_buffer[hdr_size], input_buffer, input_size);
      *encoded_size = hdr_size + input_size;
    }
    if (is_last) {
      encoded_buffer[(*encoded_size)++] = 3;
    }
    last_byte_ = 0;
    last_byte_bits_ = 0;
    return true;
  }
  
  bool BrotliCompressor::FinishStream(
      size_t* encoded_size, uint8_t* encoded_buffer) {
    return WriteMetaBlock(0, NULL, true, encoded_size, encoded_buffer);
  }
  
  int BrotliCompressBuffer(BrotliParams params,
                           size_t input_size,
                           const uint8_t* input_buffer,
                           size_t* encoded_size,
                           uint8_t* encoded_buffer) {
    if (*encoded_size == 0) {
      // Output buffer needs at least one byte.
      return 0;
    }
    BrotliMemIn in(input_buffer, input_size);
    BrotliMemOut out(encoded_buffer, *encoded_size);
    if (!BrotliCompress(params, &in, &out)) {
      return 0;
    }
    *encoded_size = out.position();
    return 1;
  }
  
  bool BrotliInIsFinished(BrotliIn* r) {
    size_t read_bytes;
    return r->Read(0, &read_bytes) == NULL;
  }
  
  const uint8_t* BrotliInReadAndCheckEnd(const size_t block_size,
                                         BrotliIn* r,
                                         size_t* bytes_read,
                                         bool* is_last) {
    *bytes_read = 0;
    const uint8_t* data = reinterpret_cast<const uint8_t*>(
        r->Read(block_size, bytes_read));
    assert((data == NULL) == (*bytes_read == 0));
    *is_last = BrotliInIsFinished(r);
    return data;
  }
  
  bool CopyOneBlockToRingBuffer(BrotliIn* r,
                                BrotliCompressor* compressor,
                                size_t* bytes_read,
                                bool* is_last) {
    const size_t block_size = compressor->input_block_size();
    const uint8_t* data = BrotliInReadAndCheckEnd(block_size, r,
                                                  bytes_read, is_last);
    if (data == NULL) {
      return *is_last;
    }
    compressor->CopyInputToRingBuffer(*bytes_read, data);
  
    // Read more bytes until block_size is filled or an EOF (data == NULL) is
    // received. This is useful to get deterministic compressed output for the
    // same input no matter how r->Read splits the input to chunks.
    for (size_t remaining = block_size - *bytes_read; remaining > 0; ) {
      size_t more_bytes_read = 0;
      data = BrotliInReadAndCheckEnd(remaining, r, &more_bytes_read, is_last);
      if (data == NULL) {
        return *is_last;
      }
      compressor->CopyInputToRingBuffer(more_bytes_read, data);
      *bytes_read += more_bytes_read;
      remaining -= more_bytes_read;
    }
    return true;
  }
  
  
  int BrotliCompress(BrotliParams params, BrotliIn* in, BrotliOut* out) {
    return BrotliCompressWithCustomDictionary(0, 0, params, in, out);
  }
  
  // Reads the provided input in 'block_size' blocks. Only the last read can be
  // smaller than 'block_size'.
  class BrotliBlockReader {
   public:
    explicit BrotliBlockReader(size_t block_size)
        : block_size_(block_size), buf_(NULL) {}
    ~BrotliBlockReader() { delete[] buf_; }
  
    const uint8_t* Read(BrotliIn* in, size_t* bytes_read, bool* is_last) {
      *bytes_read = 0;
      const uint8_t* data = BrotliInReadAndCheckEnd(block_size_, in,
                                                    bytes_read, is_last);
      if (data == NULL || *bytes_read == block_size_ || *is_last) {
        // If we could get the whole block in one read, or it is the last block,
        // we just return the pointer to the data without copying.
        return data;
      }
      // If the data comes in smaller chunks, we need to copy it into an internal
      // buffer until we get a whole block or reach the last chunk.
      if (buf_ == NULL) {
        buf_ = new uint8_t[block_size_];
      }
      memcpy(buf_, data, *bytes_read);
      do {
        size_t cur_bytes_read = 0;
        data = BrotliInReadAndCheckEnd(block_size_ - *bytes_read, in,
                                       &cur_bytes_read, is_last);
        if (data == NULL) {
          return *is_last ? buf_ : NULL;
        }
        memcpy(&buf_[*bytes_read], data, cur_bytes_read);
        *bytes_read += cur_bytes_read;
      } while (*bytes_read < block_size_ && !*is_last);
      return buf_;
    }
  
   private:
    const size_t block_size_;
    uint8_t* buf_;
  };
  
  int BrotliCompressWithCustomDictionary(size_t dictsize, const uint8_t* dict,
                                         BrotliParams params,
                                         BrotliIn* in, BrotliOut* out) {
    if (params.quality <= 1) {
      const int quality = std::max(0, params.quality);
      const int lgwin = std::min(kMaxWindowBits,
                                 std::max(kMinWindowBits, params.lgwin));
      uint8_t* storage = NULL;
      int* table = NULL;
      uint32_t* command_buf = NULL;
      uint8_t* literal_buf = NULL;
      uint8_t cmd_depths[128];
      uint16_t cmd_bits[128];
      uint8_t cmd_code[512];
      size_t cmd_code_numbits;
      if (quality == 0) {
        InitCommandPrefixCodes(cmd_depths, cmd_bits, cmd_code, &cmd_code_numbits);
      }
      uint8_t last_byte;
      uint8_t last_byte_bits;
      EncodeWindowBits(lgwin, &last_byte, &last_byte_bits);
      BrotliBlockReader r(1u << lgwin);
      int ok = 1;
      bool is_last = false;
      while (ok && !is_last) {
        // Read next block of input.
        size_t bytes;
        const uint8_t* data = r.Read(in, &bytes, &is_last);
        if (data == NULL) {
          if (!is_last) {
            ok = 0;
            break;
          }
          assert(bytes == 0);
        }
        // Set up output storage.
        const size_t max_out_size = 2 * bytes + 500;
        if (storage == NULL) {
          storage = new uint8_t[max_out_size];
        }
        storage[0] = last_byte;
        size_t storage_ix = last_byte_bits;
        // Set up hash table.
        size_t htsize = HashTableSize(MaxHashTableSize(quality), bytes);
        if (table == NULL) {
          table = new int[htsize];
        }
        memset(table, 0, htsize * sizeof(table[0]));
        // Set up command and literal buffers for two pass mode.
        if (quality == 1 && command_buf == NULL) {
          size_t buf_size = std::min(bytes, kCompressFragmentTwoPassBlockSize);
          command_buf = new uint32_t[buf_size];
          literal_buf = new uint8_t[buf_size];
        }
        // Do the actual compression.
        if (quality == 0) {
          BrotliCompressFragmentFast(data, bytes, is_last, table, htsize,
                                     cmd_depths, cmd_bits,
                                     &cmd_code_numbits, cmd_code,
                                     &storage_ix, storage);
        } else {
          BrotliCompressFragmentTwoPass(data, bytes, is_last,
                                        command_buf, literal_buf,
                                        table, htsize,
                                        &storage_ix, storage);
        }
        // Save last bytes to stitch it together with the next output block.
        last_byte = storage[storage_ix >> 3];
        last_byte_bits = storage_ix & 7u;
        // Write output block.
        size_t out_bytes = storage_ix >> 3;
        if (out_bytes > 0 && !out->Write(storage, out_bytes)) {
          ok = 0;
          break;
        }
      }
      delete[] storage;
      delete[] table;
      delete[] command_buf;
      delete[] literal_buf;
      return ok;
    }
  
    size_t in_bytes = 0;
    size_t out_bytes = 0;
    uint8_t* output;
    bool final_block = false;
    BrotliCompressor compressor(params);
    if (dictsize != 0) compressor.BrotliSetCustomDictionary(dictsize, dict);
    while (!final_block) {
      if (!CopyOneBlockToRingBuffer(in, &compressor, &in_bytes, &final_block)) {
        return false;
      }
      out_bytes = 0;
      if (!compressor.WriteBrotliData(final_block,
                                      /* force_flush = */ false,
                                      &out_bytes, &output)) {
        return false;
      }
      if (out_bytes > 0 && !out->Write(output, out_bytes)) {
        return false;
      }
    }
    return true;
  }
  
  
  }  // namespace brotli
  

Download