See file LICENSE for detail or copy at https://opensource.org/licenses/MIT\r
*/\r
\r
-/* template parameters: FN */\r
+/* template parameters: EXPORT_FN, FN */\r
\r
-#define Hasher HASHER()\r
-\r
-static BROTLI_NOINLINE void FN(CreateBackwardReferences)(\r
- MemoryManager* m, size_t num_bytes, size_t position, BROTLI_BOOL is_last,\r
+static BROTLI_NOINLINE void EXPORT_FN(CreateBackwardReferences)(\r
+ size_t num_bytes, size_t position,\r
const uint8_t* ringbuffer, size_t ringbuffer_mask,\r
- const BrotliEncoderParams* params, Hasher* hasher, int* dist_cache,\r
+ const BrotliEncoderParams* params, HasherHandle hasher, int* dist_cache,\r
size_t* last_insert_len, Command* commands, size_t* num_commands,\r
size_t* num_literals) {\r
/* Set maximum distance, see section 9.1. of the spec. */\r
- const size_t max_backward_limit = MaxBackwardLimit(params->lgwin);\r
+ const size_t max_backward_limit = BROTLI_MAX_BACKWARD_LIMIT(params->lgwin);\r
\r
const Command* const orig_commands = commands;\r
size_t insert_length = *last_insert_len;\r
const size_t random_heuristics_window_size =\r
LiteralSpreeLengthForSparseSearch(params);\r
size_t apply_random_heuristics = position + random_heuristics_window_size;\r
+ const size_t gap = 0;\r
\r
/* Minimum score to accept a backward reference. */\r
- const score_t kMinScore = BROTLI_SCORE_BASE + 400;\r
+ const score_t kMinScore = BROTLI_SCORE_BASE + 100;\r
\r
- FN(Init)(m, hasher, ringbuffer, params, position, num_bytes, is_last);\r
- if (BROTLI_IS_OOM(m)) return;\r
- FN(StitchToPreviousBlock)(hasher, num_bytes, position,\r
- ringbuffer, ringbuffer_mask);\r
+ FN(PrepareDistanceCache)(hasher, dist_cache);\r
\r
while (position + FN(HashTypeLength)() < pos_end) {\r
size_t max_length = pos_end - position;\r
size_t max_distance = BROTLI_MIN(size_t, position, max_backward_limit);\r
HasherSearchResult sr;\r
sr.len = 0;\r
- sr.len_x_code = 0;\r
+ sr.len_code_delta = 0;\r
sr.distance = 0;\r
sr.score = kMinScore;\r
- if (FN(FindLongestMatch)(hasher, ringbuffer, ringbuffer_mask, dist_cache,\r
- position, max_length, max_distance, &sr)) {\r
+ FN(FindLongestMatch)(hasher, ¶ms->dictionary,\r
+ ringbuffer, ringbuffer_mask, dist_cache, position,\r
+ max_length, max_distance, gap,\r
+ params->dist.max_distance, &sr);\r
+ if (sr.score > kMinScore) {\r
/* Found a match. Let's look for something even better ahead. */\r
int delayed_backward_references_in_row = 0;\r
--max_length;\r
for (;; --max_length) {\r
- const score_t cost_diff_lazy = 700;\r
- BROTLI_BOOL is_match_found;\r
+ const score_t cost_diff_lazy = 175;\r
HasherSearchResult sr2;\r
sr2.len = params->quality < MIN_QUALITY_FOR_EXTENSIVE_REFERENCE_SEARCH ?\r
BROTLI_MIN(size_t, sr.len - 1, max_length) : 0;\r
- sr2.len_x_code = 0;\r
+ sr2.len_code_delta = 0;\r
sr2.distance = 0;\r
sr2.score = kMinScore;\r
max_distance = BROTLI_MIN(size_t, position + 1, max_backward_limit);\r
- is_match_found = FN(FindLongestMatch)(hasher, ringbuffer,\r
- ringbuffer_mask, dist_cache, position + 1, max_length, max_distance,\r
- &sr2);\r
- if (is_match_found && sr2.score >= sr.score + cost_diff_lazy) {\r
+ FN(FindLongestMatch)(hasher, ¶ms->dictionary,\r
+ ringbuffer, ringbuffer_mask, dist_cache, position + 1, max_length,\r
+ max_distance, gap, params->dist.max_distance, &sr2);\r
+ if (sr2.score >= sr.score + cost_diff_lazy) {\r
/* Ok, let's just write one byte for now and start a match from the\r
next byte. */\r
++position;\r
position + 2 * sr.len + random_heuristics_window_size;\r
max_distance = BROTLI_MIN(size_t, position, max_backward_limit);\r
{\r
- /* The first 16 codes are special shortcodes,\r
+ /* The first 16 codes are special short-codes,\r
and the minimum offset is 1. */\r
size_t distance_code =\r
- ComputeDistanceCode(sr.distance, max_distance, dist_cache);\r
- if (sr.distance <= max_distance && distance_code > 0) {\r
+ ComputeDistanceCode(sr.distance, max_distance + gap, dist_cache);\r
+ if ((sr.distance <= (max_distance + gap)) && distance_code > 0) {\r
dist_cache[3] = dist_cache[2];\r
dist_cache[2] = dist_cache[1];\r
dist_cache[1] = dist_cache[0];\r
dist_cache[0] = (int)sr.distance;\r
+ FN(PrepareDistanceCache)(hasher, dist_cache);\r
}\r
- InitCommand(commands++, insert_length, sr.len, sr.len ^ sr.len_x_code,\r
- distance_code);\r
+ InitCommand(commands++, ¶ms->dist, insert_length,\r
+ sr.len, sr.len_code_delta, distance_code);\r
}\r
*num_literals += insert_length;\r
insert_length = 0;\r
/* Put the hash keys into the table, if there are enough bytes left.\r
Depending on the hasher implementation, it can push all positions\r
- in the given range or only a subset of them. */\r
- FN(StoreRange)(hasher, ringbuffer, ringbuffer_mask, position + 2,\r
- BROTLI_MIN(size_t, position + sr.len, store_end));\r
+ in the given range or only a subset of them.\r
+ Avoid hash poisoning with RLE data. */\r
+ {\r
+ size_t range_start = position + 2;\r
+ size_t range_end = BROTLI_MIN(size_t, position + sr.len, store_end);\r
+ if (sr.distance < (sr.len >> 2)) {\r
+ range_start = BROTLI_MIN(size_t, range_end, BROTLI_MAX(size_t,\r
+ range_start, position + sr.len - (sr.distance << 2)));\r
+ }\r
+ FN(StoreRange)(hasher, ringbuffer, ringbuffer_mask, range_start,\r
+ range_end);\r
+ }\r
position += sr.len;\r
} else {\r
++insert_length;\r
*last_insert_len = insert_length;\r
*num_commands += (size_t)(commands - orig_commands);\r
}\r
-\r
-#undef Hasher\r