backward_references_inc.h revision a629289e3297bcfd25648293df3e1d6dfd59df24 
1/* NOLINT(build/header_guard) */
2/* Copyright 2013 Google Inc. All Rights Reserved.
3
4   Distributed under MIT license.
5   See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
6*/
7
8/* template parameters: EXPORT_FN, FN */
9
10static BROTLI_NOINLINE void EXPORT_FN(CreateBackwardReferences)(
11    const BrotliDictionary* dictionary,
12    const uint16_t* dictionary_hash, size_t num_bytes, size_t position,
13    const uint8_t* ringbuffer, size_t ringbuffer_mask,
14    const BrotliEncoderParams* params, HasherHandle hasher, int* dist_cache,
15    size_t* last_insert_len, Command* commands, size_t* num_commands,
16    size_t* num_literals) {
17  /* Set maximum distance, see section 9.1. of the spec. */
18  const size_t max_backward_limit = BROTLI_MAX_BACKWARD_LIMIT(params->lgwin);
19
20  const Command* const orig_commands = commands;
21  size_t insert_length = *last_insert_len;
22  const size_t pos_end = position + num_bytes;
23  const size_t store_end = num_bytes >= FN(StoreLookahead)() ?
24      position + num_bytes - FN(StoreLookahead)() + 1 : position;
25
26  /* For speed up heuristics for random data. */
27  const size_t random_heuristics_window_size =
28      LiteralSpreeLengthForSparseSearch(params);
29  size_t apply_random_heuristics = position + random_heuristics_window_size;
30  const size_t gap = 0;
31
32  /* Minimum score to accept a backward reference. */
33  const score_t kMinScore = BROTLI_SCORE_BASE + 100;
34
35  FN(PrepareDistanceCache)(hasher, dist_cache);
36
37  while (position + FN(HashTypeLength)() < pos_end) {
38    size_t max_length = pos_end - position;
39    size_t max_distance = BROTLI_MIN(size_t, position, max_backward_limit);
40    HasherSearchResult sr;
41    sr.len = 0;
42    sr.len_code_delta = 0;
43    sr.distance = 0;
44    sr.score = kMinScore;
45    FN(FindLongestMatch)(hasher, dictionary, dictionary_hash, ringbuffer,
46                         ringbuffer_mask, dist_cache, position,
47                         max_length, max_distance, gap, &sr);
48    if (sr.score > kMinScore) {
49      /* Found a match. Let's look for something even better ahead. */
50      int delayed_backward_references_in_row = 0;
51      --max_length;
52      for (;; --max_length) {
53        const score_t cost_diff_lazy = 175;
54        HasherSearchResult sr2;
55        sr2.len = params->quality < MIN_QUALITY_FOR_EXTENSIVE_REFERENCE_SEARCH ?
56            BROTLI_MIN(size_t, sr.len - 1, max_length) : 0;
57        sr2.len_code_delta = 0;
58        sr2.distance = 0;
59        sr2.score = kMinScore;
60        max_distance = BROTLI_MIN(size_t, position + 1, max_backward_limit);
61        FN(FindLongestMatch)(hasher, dictionary, dictionary_hash, ringbuffer,
62                             ringbuffer_mask, dist_cache, position + 1,
63                             max_length, max_distance, gap, &sr2);
64        if (sr2.score >= sr.score + cost_diff_lazy) {
65          /* Ok, let's just write one byte for now and start a match from the
66             next byte. */
67          ++position;
68          ++insert_length;
69          sr = sr2;
70          if (++delayed_backward_references_in_row < 4 &&
71              position + FN(HashTypeLength)() < pos_end) {
72            continue;
73          }
74        }
75        break;
76      }
77      apply_random_heuristics =
78          position + 2 * sr.len + random_heuristics_window_size;
79      max_distance = BROTLI_MIN(size_t, position, max_backward_limit);
80      {
81        /* The first 16 codes are special short-codes,
82           and the minimum offset is 1. */
83        size_t distance_code =
84            ComputeDistanceCode(sr.distance, max_distance + gap, dist_cache);
85        if ((sr.distance <= (max_distance + gap)) && distance_code > 0) {
86          dist_cache[3] = dist_cache[2];
87          dist_cache[2] = dist_cache[1];
88          dist_cache[1] = dist_cache[0];
89          dist_cache[0] = (int)sr.distance;
90          FN(PrepareDistanceCache)(hasher, dist_cache);
91        }
92        InitCommand(commands++, insert_length, sr.len, sr.len_code_delta,
93            distance_code);
94      }
95      *num_literals += insert_length;
96      insert_length = 0;
97      /* Put the hash keys into the table, if there are enough bytes left.
98         Depending on the hasher implementation, it can push all positions
99         in the given range or only a subset of them.
100         Avoid hash poisoning with RLE data. */
101      {
102        size_t range_start = position + 2;
103        size_t range_end = BROTLI_MIN(size_t, position + sr.len, store_end);
104        if (sr.distance < (sr.len >> 2)) {
105          range_start = BROTLI_MIN(size_t, range_end, BROTLI_MAX(size_t,
106              range_start, position + sr.len - (sr.distance << 2)));
107        }
108        FN(StoreRange)(hasher, ringbuffer, ringbuffer_mask, range_start,
109                       range_end);
110      }
111      position += sr.len;
112    } else {
113      ++insert_length;
114      ++position;
115      /* If we have not seen matches for a long time, we can skip some
116         match lookups. Unsuccessful match lookups are very very expensive
117         and this kind of a heuristic speeds up compression quite
118         a lot. */
119      if (position > apply_random_heuristics) {
120        /* Going through uncompressible data, jump. */
121        if (position >
122            apply_random_heuristics + 4 * random_heuristics_window_size) {
123          /* It is quite a long time since we saw a copy, so we assume
124             that this data is not compressible, and store hashes less
125             often. Hashes of non compressible data are less likely to
126             turn out to be useful in the future, too, so we store less of
127             them to not to flood out the hash table of good compressible
128             data. */
129          const size_t kMargin =
130              BROTLI_MAX(size_t, FN(StoreLookahead)() - 1, 4);
131          size_t pos_jump =
132              BROTLI_MIN(size_t, position + 16, pos_end - kMargin);
133          for (; position < pos_jump; position += 4) {
134            FN(Store)(hasher, ringbuffer, ringbuffer_mask, position);
135            insert_length += 4;
136          }
137        } else {
138          const size_t kMargin =
139              BROTLI_MAX(size_t, FN(StoreLookahead)() - 1, 2);
140          size_t pos_jump =
141              BROTLI_MIN(size_t, position + 8, pos_end - kMargin);
142          for (; position < pos_jump; position += 2) {
143            FN(Store)(hasher, ringbuffer, ringbuffer_mask, position);
144            insert_length += 2;
145          }
146        }
147      }
148    }
149  }
150  insert_length += pos_end - position;
151  *last_insert_len = insert_length;
152  *num_commands += (size_t)(commands - orig_commands);
153}
154