Fixes: (#468)

* fix slow-down after a long copy (q10-11)
 * more thorough hashing for long ranges (q10-11)
 * minor documentation fixes
 * bazel.io -> bazel.build

7 files changed, 54 insertions, 26 deletions

diff --git a/README.md b/README.md
index 7a63243..53a02eb 100644
--- a/README.md
+++ b/README.md
@@ -27,7 +27,7 @@ If you want to install brotli, use one of the more advanced build systems below.
 
 #### Bazel
 
-See [Bazel](http://www.bazel.io/)
+See [Bazel](http://www.bazel.build/)
 
 #### CMake
 
diff --git a/configure b/configure
index 80bd276..2bc070c 100755
--- a/configure
+++ b/configure
@@ -1,6 +1,6 @@
 #!/bin/bash
 echo "Use Bazel, CMake or Premake5 to generate projects / build files."
-echo "  Bazel: http://www.bazel.io/"
+echo "  Bazel: http://www.bazel.build/"
 echo "  CMake: https://cmake.org/"
 echo "  Premake5: https://premake.github.io/"
 echo "Or simply run 'make' to build and test command line tool."
diff --git a/enc/backward_references.c b/enc/backward_references.c
index bc028b7..a52a7be 100644
--- a/enc/backward_references.c
+++ b/enc/backward_references.c
@@ -368,19 +368,14 @@ static void ComputeDistanceCache(const size_t pos,
   }
 }
 
-static void UpdateNodes(const size_t num_bytes,
-                        const size_t block_start,
-                        const size_t pos,
-                        const uint8_t* ringbuffer,
-                        const size_t ringbuffer_mask,
-                        const BrotliEncoderParams* params,
-                        const size_t max_backward_limit,
-                        const int* starting_dist_cache,
-                        const size_t num_matches,
-                        const BackwardMatch* matches,
-                        const ZopfliCostModel* model,
-                        StartPosQueue* queue,
-                        ZopfliNode* nodes) {
+/* Returns longest copy length. */
+static size_t UpdateNodes(
+    const size_t num_bytes, const size_t block_start, const size_t pos,
+    const uint8_t* ringbuffer, const size_t ringbuffer_mask,
+    const BrotliEncoderParams* params, const size_t max_backward_limit,
+    const int* starting_dist_cache, const size_t num_matches,
+    const BackwardMatch* matches, const ZopfliCostModel* model,
+    StartPosQueue* queue, ZopfliNode* nodes) {
   const size_t cur_ix = block_start + pos;
   const size_t cur_ix_masked = cur_ix & ringbuffer_mask;
   const size_t max_distance = BROTLI_MIN(size_t, cur_ix, max_backward_limit);
@@ -388,6 +383,7 @@ static void UpdateNodes(const size_t num_bytes,
   const size_t max_zopfli_len = MaxZopfliLen(params);
   const size_t max_iters = MaxZopfliCandidates(params);
   size_t min_len;
+  size_t result = 0;
   size_t k;
 
   {
@@ -464,6 +460,7 @@ static void UpdateNodes(const size_t num_bytes,
               ZopfliCostModelGetCommandCost(model, cmdcode);
           if (cost < nodes[pos + l].u.cost) {
             UpdateZopfliNode(nodes, pos, start, l, l, backward, j + 1, cost);
+            result = BROTLI_MAX(size_t, result, l);
           }
           best_len = l;
         }
@@ -512,11 +509,13 @@ static void UpdateNodes(const size_t num_bytes,
               ZopfliCostModelGetCommandCost(model, cmdcode);
           if (cost < nodes[pos + len].u.cost) {
             UpdateZopfliNode(nodes, pos, start, len, len_code, dist, 0, cost);
+            result = BROTLI_MAX(size_t, result, len);
           }
         }
       }
     }
   }
+  return result;
 }
 
 static size_t ComputeShortestPathFromNodes(size_t num_bytes,
@@ -595,13 +594,21 @@ static size_t ZopfliIterate(size_t num_bytes,
   StartPosQueue queue;
   size_t cur_match_pos = 0;
   size_t i;
+  size_t skip_to = 0;
   nodes[0].length = 0;
   nodes[0].u.cost = 0;
   InitStartPosQueue(&queue);
   for (i = 0; i + 3 < num_bytes; i++) {
-    UpdateNodes(num_bytes, position, i, ringbuffer, ringbuffer_mask,
-                params, max_backward_limit, dist_cache, num_matches[i],
-                &matches[cur_match_pos], model, &queue, nodes);
+    if (i >= skip_to) {
+      size_t could_skip = UpdateNodes(num_bytes, position, i, ringbuffer,
+          ringbuffer_mask, params, max_backward_limit, dist_cache,
+          num_matches[i], &matches[cur_match_pos], model, &queue, nodes);
+      if (could_skip > BROTLI_LONG_COPY_QUICK_STEP) {
+        /* Previous copy was very long; no need to scan thoroughly. */
+        skip_to = i + could_skip;
+        InitStartPosQueue(&queue);
+      }
+    }
     cur_match_pos += num_matches[i];
     /* The zopflification can be too slow in case of very long lengths, so in
        such case skip it all, it does not cost a lot of compression ratio. */
@@ -644,14 +651,22 @@ size_t BrotliZopfliComputeShortestPath(MemoryManager* m,
     const size_t max_distance = BROTLI_MIN(size_t, pos, max_backward_limit);
     size_t num_matches = FindAllMatchesH10(hasher, ringbuffer, ringbuffer_mask,
         pos, num_bytes - i, max_distance, params, matches);
+    size_t could_skip;
     if (num_matches > 0 &&
         BackwardMatchLength(&matches[num_matches - 1]) > max_zopfli_len) {
       matches[0] = matches[num_matches - 1];
       num_matches = 1;
     }
-    UpdateNodes(num_bytes, position, i, ringbuffer, ringbuffer_mask,
-                params, max_backward_limit, dist_cache, num_matches, matches,
-                &model, &queue, nodes);
+    could_skip = UpdateNodes(num_bytes, position, i, ringbuffer,
+        ringbuffer_mask, params, max_backward_limit, dist_cache, num_matches,
+        matches, &model, &queue, nodes);
+    if (could_skip > BROTLI_LONG_COPY_QUICK_STEP) {
+       i += could_skip - 1;
+      StoreRangeH10(hasher, ringbuffer, ringbuffer_mask, pos + 1, BROTLI_MIN(
+        size_t, pos + could_skip - 1, store_end));
+      InitStartPosQueue(&queue);
+      continue;
+    }
     if (num_matches == 1 && BackwardMatchLength(&matches[0]) > max_zopfli_len) {
       /* Add the tail of the copy to the hasher. */
       StoreRangeH10(hasher, ringbuffer, ringbuffer_mask, pos + 1, BROTLI_MIN(
diff --git a/enc/hash.h b/enc/hash.h
index 37c5e6e..0d8e61c 100644
--- a/enc/hash.h
+++ b/enc/hash.h
@@ -490,7 +490,16 @@ static BROTLI_INLINE void FN(Store)(HashToBinaryTree* self, const uint8_t *data,
 static BROTLI_INLINE void FN(StoreRange)(HashToBinaryTree* self,
     const uint8_t *data, const size_t mask, const size_t ix_start,
     const size_t ix_end) {
-  size_t i = ix_start + 63 <= ix_end ? ix_end - 63 : ix_start;
+  size_t i = ix_start;
+  size_t j = ix_start;
+  if (ix_start + 63 <= ix_end) {
+    i = ix_end - 63;
+  }
+  if (ix_start + 512 <= i) {
+    for (; j < i; j += 8) {
+      FN(Store)(self, data, mask, j);
+    }
+  }
   for (; i < ix_end; ++i) {
     FN(Store)(self, data, mask, i);
   }
diff --git a/enc/quality.h b/enc/quality.h
index 7634d9c..6dade07 100755
--- a/enc/quality.h
+++ b/enc/quality.h
@@ -48,6 +48,9 @@ static BROTLI_INLINE size_t MaxHashTableSize(int quality) {
 #define MAX_ZOPFLI_LEN_QUALITY_10 150
 #define MAX_ZOPFLI_LEN_QUALITY_11 325
 
+/* Do not thoroughly search when a long copy is found. */
+#define BROTLI_LONG_COPY_QUICK_STEP 16384
+
 static BROTLI_INLINE size_t MaxZopfliLen(const BrotliEncoderParams* params) {
   return params->quality <= 10 ?
       MAX_ZOPFLI_LEN_QUALITY_10 :
diff --git a/include/brotli/encode.h b/include/brotli/encode.h
index 1434b68..4856fda 100755
--- a/include/brotli/encode.h
+++ b/include/brotli/encode.h
@@ -216,16 +216,16 @@ BROTLI_ENC_API BrotliEncoderState* BrotliEncoderCreateInstance(
  */
 BROTLI_ENC_API void BrotliEncoderDestroyInstance(BrotliEncoderState* state);
 
-/** @deprecated Calculates maximum input size that can be processed at once. */
+/* Calculates maximum input size that can be processed at once. */
 BROTLI_DEPRECATED BROTLI_ENC_API size_t BrotliEncoderInputBlockSize(
     BrotliEncoderState* state);
 
-/** @deprecated Copies the given input data to the internal ring buffer. */
+/* Copies the given input data to the internal ring buffer. */
 BROTLI_DEPRECATED BROTLI_ENC_API void BrotliEncoderCopyInputToRingBuffer(
     BrotliEncoderState* state, const size_t input_size,
     const uint8_t* input_buffer);
 
-/** @deprecated Processes the accumulated input. */
+/* Processes the accumulated input. */
 BROTLI_DEPRECATED BROTLI_ENC_API BROTLI_BOOL BrotliEncoderWriteData(
     BrotliEncoderState* state, const BROTLI_BOOL is_last,
     const BROTLI_BOOL force_flush, size_t* out_size, uint8_t** output);
@@ -317,6 +317,7 @@ BROTLI_ENC_API BROTLI_BOOL BrotliEncoderCompress(
  *  -# (optionally) copy input data to internal buffer
  *  -# actually compress data and (optionally) store it to internal buffer
  *  -# (optionally) copy compressed bytes from internal buffer to output stream
+ *
  * Whenever all 3 tasks can't move forward anymore, or error occurs, this
  * method returns the control flow to caller.
  *
diff --git a/include/brotli/types.h b/include/brotli/types.h
index 51a1d3b..f982c64 100755
--- a/include/brotli/types.h
+++ b/include/brotli/types.h
@@ -42,7 +42,7 @@ typedef __int64 int64_t;
  * if (SomeBrotliFunction(encoder, BROTLI_TRUE) &&
  *     !OtherBrotliFunction(decoder, BROTLI_FALSE)) {
  *   bool x = !!YetAnotherBrotliFunction(encoder, TO_BROLTI_BOOL(2 * 2 == 4));
- *   DoSometing(x);
+ *   DoSomething(x);
  * }
  * @endcode
  */