+++ /dev/null
-/* NOLINT(build/header_guard) */\r
-/* Copyright 2013 Google Inc. All Rights Reserved.\r
-\r
- Distributed under MIT license.\r
- See file LICENSE for detail or copy at https://opensource.org/licenses/MIT\r
-*/\r
-\r
-/* template parameters: EXPORT_FN, FN */\r
-\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, 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 = 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 pos_end = position + num_bytes;\r
- const size_t store_end = num_bytes >= FN(StoreLookahead)() ?\r
- position + num_bytes - FN(StoreLookahead)() + 1 : position;\r
-\r
- /* For speed up heuristics for random data. */\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 + 100;\r
-\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_code_delta = 0;\r
- sr.distance = 0;\r
- sr.score = kMinScore;\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 = 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_code_delta = 0;\r
- sr2.distance = 0;\r
- sr2.score = kMinScore;\r
- max_distance = BROTLI_MIN(size_t, position + 1, max_backward_limit);\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
- ++insert_length;\r
- sr = sr2;\r
- if (++delayed_backward_references_in_row < 4 &&\r
- position + FN(HashTypeLength)() < pos_end) {\r
- continue;\r
- }\r
- }\r
- break;\r
- }\r
- apply_random_heuristics =\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 short-codes,\r
- and the minimum offset is 1. */\r
- size_t distance_code =\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++, ¶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
- 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
- ++position;\r
- /* If we have not seen matches for a long time, we can skip some\r
- match lookups. Unsuccessful match lookups are very very expensive\r
- and this kind of a heuristic speeds up compression quite\r
- a lot. */\r
- if (position > apply_random_heuristics) {\r
- /* Going through uncompressible data, jump. */\r
- if (position >\r
- apply_random_heuristics + 4 * random_heuristics_window_size) {\r
- /* It is quite a long time since we saw a copy, so we assume\r
- that this data is not compressible, and store hashes less\r
- often. Hashes of non compressible data are less likely to\r
- turn out to be useful in the future, too, so we store less of\r
- them to not to flood out the hash table of good compressible\r
- data. */\r
- const size_t kMargin =\r
- BROTLI_MAX(size_t, FN(StoreLookahead)() - 1, 4);\r
- size_t pos_jump =\r
- BROTLI_MIN(size_t, position + 16, pos_end - kMargin);\r
- for (; position < pos_jump; position += 4) {\r
- FN(Store)(hasher, ringbuffer, ringbuffer_mask, position);\r
- insert_length += 4;\r
- }\r
- } else {\r
- const size_t kMargin =\r
- BROTLI_MAX(size_t, FN(StoreLookahead)() - 1, 2);\r
- size_t pos_jump =\r
- BROTLI_MIN(size_t, position + 8, pos_end - kMargin);\r
- for (; position < pos_jump; position += 2) {\r
- FN(Store)(hasher, ringbuffer, ringbuffer_mask, position);\r
- insert_length += 2;\r
- }\r
- }\r
- }\r
- }\r
- }\r
- insert_length += pos_end - position;\r
- *last_insert_len = insert_length;\r
- *num_commands += (size_t)(commands - orig_commands);\r
-}\r
projects / mirror_edk2.git / blobdiff