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