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