Added brotli enc/ and tools/ directories.

third_party/brotli/enc/encode_parallel.cc

Index: third_party/brotli/enc/encode_parallel.cc
diff --git a/third_party/brotli/enc/encode_parallel.cc b/third_party/brotli/enc/encode_parallel.cc
new file mode 100644
index 0000000000000000000000000000000000000000..cbad975415dacfdcfd571c429d4fd528777721e9
--- /dev/null
+++ b/third_party/brotli/enc/encode_parallel.cc
@@ -0,0 +1,279 @@
+/* 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 parallel Brotli compressor.
+
+#include "./encode_parallel.h"
+
+#include <algorithm>
+#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 "./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 {
+
+namespace {
+
+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() && cmd->cmd_prefix_ >= 128) {
+      PrefixEncodeCopyDistance(cmd->DistanceCode(),
+                               num_direct_distance_codes,
+                               distance_postfix_bits,
+                               &cmd->dist_prefix_,
+                               &cmd->dist_extra_);
+    }
+  }
+}
+
+bool WriteMetaBlockParallel(const BrotliParams& params,
+                            const uint32_t input_size,
+                            const uint8_t* input_buffer,
+                            const uint32_t prefix_size,
+                            const uint8_t* prefix_buffer,
+                            const bool is_first,
+                            const bool is_last,
+                            size_t* encoded_size,
+                            uint8_t* encoded_buffer) {
+  if (input_size == 0) {
+    return false;
+  }
+
+  // Copy prefix + next input block into a continuous area.
+  uint32_t input_pos = prefix_size;
+  // CreateBackwardReferences reads up to 3 bytes past the end of input if the
+  // mask points past the end of input.
+  // FindMatchLengthWithLimit could do another 8 bytes look-forward.
+  std::vector<uint8_t> input(prefix_size + input_size + 4 + 8);
+  memcpy(&input[0], prefix_buffer, prefix_size);
+  memcpy(&input[input_pos], input_buffer, input_size);
+  // Since we don't have a ringbuffer, masking is a no-op.
+  // We use one less bit than the full range because some of the code uses
+  // mask + 1 as the size of the ringbuffer.
+  const uint32_t mask = std::numeric_limits<uint32_t>::max() >> 1;
+
+  uint8_t prev_byte = input_pos > 0 ? input[(input_pos - 1) & mask] : 0;
+  uint8_t prev_byte2 = input_pos > 1 ? input[(input_pos - 2) & mask] : 0;
+
+  // Decide about UTF8 mode.
+  static const double kMinUTF8Ratio = 0.75;
+  bool utf8_mode = IsMostlyUTF8(&input[0], input_pos, mask, input_size,
+                                kMinUTF8Ratio);
+
+  // Initialize hashers.
+  int hash_type = std::min(10, params.quality);
+  Hashers* hashers = new Hashers();
+  hashers->Init(hash_type);
+
+  // Compute backward references.
+  size_t last_insert_len = 0;
+  size_t num_commands = 0;
+  size_t num_literals = 0;
+  int dist_cache[4] = { -4, -4, -4, -4 };
+  Command* commands = static_cast<Command*>(
+      malloc(sizeof(Command) * ((input_size + 1) >> 1)));
+  if (commands == 0) {
+    delete hashers;
+    return false;
+  }
+  CreateBackwardReferences(
+      input_size, input_pos, is_last,
+      &input[0], mask,
+      params.quality,
+      params.lgwin,
+      hashers,
+      hash_type,
+      dist_cache,
+      &last_insert_len,
+      commands,
+      &num_commands,
+      &num_literals);
+  delete hashers;
+  if (last_insert_len > 0) {
+    commands[num_commands++] = Command(last_insert_len);
+    num_literals += last_insert_len;
+  }
+  assert(num_commands != 0);
+
+  // Build the meta-block.
+  MetaBlockSplit mb;
+  uint32_t num_direct_distance_codes =
+      params.mode == BrotliParams::MODE_FONT ? 12 : 0;
+  uint32_t distance_postfix_bits =
+      params.mode == BrotliParams::MODE_FONT ? 1 : 0;
+  ContextType literal_context_mode = utf8_mode ? CONTEXT_UTF8 : CONTEXT_SIGNED;
+  RecomputeDistancePrefixes(commands, num_commands,
+                            num_direct_distance_codes,
+                            distance_postfix_bits);
+  if (params.quality <= 9) {
+    BuildMetaBlockGreedy(&input[0], input_pos, mask,
+                         commands, num_commands,
+                         &mb);
+  } else {
+    BuildMetaBlock(&input[0], input_pos, mask,
+                   prev_byte, prev_byte2,
+                   commands, num_commands,
+                   literal_context_mode,
+                   &mb);
+  }
+
+  // Set up the temporary output storage.
+  const size_t max_out_size = 2 * input_size + 500;
+  std::vector<uint8_t> storage(max_out_size);
+  uint8_t first_byte = 0;
+  size_t first_byte_bits = 0;
+  if (is_first) {
+    if (params.lgwin == 16) {
+      first_byte = 0;
+      first_byte_bits = 1;
+    } else if (params.lgwin == 17) {
+      first_byte = 1;
+      first_byte_bits = 7;
+    } else {
+      first_byte = static_cast<uint8_t>(((params.lgwin - 17) << 1) | 1);
+      first_byte_bits = 4;
+    }
+  }
+  storage[0] = static_cast<uint8_t>(first_byte);
+  size_t storage_ix = first_byte_bits;
+
+  // Store the meta-block to the temporary output.
+  StoreMetaBlock(&input[0], input_pos, input_size, 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]);
+  free(commands);
+
+  // If this is not the last meta-block, store an empty metadata
+  // meta-block so that the meta-block will end at a byte boundary.
+  if (!is_last) {
+    StoreSyncMetaBlock(&storage_ix, &storage[0]);
+  }
+
+  // If the compressed data is too large, fall back to an uncompressed
+  // meta-block.
+  size_t output_size = storage_ix >> 3;
+  if (input_size + 4 < output_size) {
+    storage[0] = static_cast<uint8_t>(first_byte);
+    storage_ix = first_byte_bits;
+    StoreUncompressedMetaBlock(is_last, &input[0], input_pos, mask,
+                               input_size,
+                               &storage_ix, &storage[0]);
+    output_size = storage_ix >> 3;
+  }
+
+  // Copy the temporary output with size-check to the output.
+  if (output_size > *encoded_size) {
+    return false;
+  }
+  memcpy(encoded_buffer, &storage[0], output_size);
+  *encoded_size = output_size;
+  return true;
+}
+
+}  // namespace
+
+int BrotliCompressBufferParallel(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;
+  } else  if (input_size == 0) {
+    encoded_buffer[0] = 6;
+    *encoded_size = 1;
+    return 1;
+  }
+
+  // Sanitize params.
+  if (params.lgwin < kMinWindowBits) {
+    params.lgwin = kMinWindowBits;
+  } else if (params.lgwin > kMaxWindowBits) {
+    params.lgwin = kMaxWindowBits;
+  }
+  if (params.lgblock == 0) {
+    params.lgblock = 16;
+    if (params.quality >= 9 && params.lgwin > params.lgblock) {
+      params.lgblock = std::min(21, params.lgwin);
+    }
+  } else if (params.lgblock < kMinInputBlockBits) {
+    params.lgblock = kMinInputBlockBits;
+  } else if (params.lgblock > kMaxInputBlockBits) {
+    params.lgblock = kMaxInputBlockBits;
+  }
+  size_t max_input_block_size = 1 << params.lgblock;
+  size_t max_prefix_size = 1u << params.lgwin;
+
+  std::vector<std::vector<uint8_t> > compressed_pieces;
+
+  // Compress block-by-block independently.
+  for (size_t pos = 0; pos < input_size; ) {
+    uint32_t input_block_size =
+        static_cast<uint32_t>(std::min(max_input_block_size, input_size - pos));
+    uint32_t prefix_size =
+        static_cast<uint32_t>(std::min(max_prefix_size, pos));
+    size_t out_size = input_block_size + (input_block_size >> 3) + 1024;
+    std::vector<uint8_t> out(out_size);
+    if (!WriteMetaBlockParallel(params,
+                                input_block_size,
+                                &input_buffer[pos],
+                                prefix_size,
+                                &input_buffer[pos - prefix_size],
+                                pos == 0,
+                                pos + input_block_size == input_size,
+                                &out_size,
+                                &out[0])) {
+      return false;
+    }
+    out.resize(out_size);
+    compressed_pieces.push_back(out);
+    pos += input_block_size;
+  }
+
+  // Piece together the output.
+  size_t out_pos = 0;
+  for (size_t i = 0; i < compressed_pieces.size(); ++i) {
+    const std::vector<uint8_t>& out = compressed_pieces[i];
+    if (out_pos + out.size() > *encoded_size) {
+      return false;
+    }
+    memcpy(&encoded_buffer[out_pos], &out[0], out.size());
+    out_pos += out.size();
+  }
+  *encoded_size = out_pos;
+
+  return true;
+}
+
+}  // namespace brotli