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