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