--- /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: 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
+ const uint8_t* ringbuffer, size_t ringbuffer_mask,\r
+ const BrotliEncoderParams* params, Hasher* 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
+\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
+\r
+ /* Minimum score to accept a backward reference. */\r
+ const score_t kMinScore = BROTLI_SCORE_BASE + 400;\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
+\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.distance = 0;\r
+ sr.score = kMinScore;\r
+ if (FN(FindLongestMatch)(hasher, ringbuffer, ringbuffer_mask, dist_cache,\r
+ position, max_length, max_distance, &sr)) {\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
+ 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.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
+ /* 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 shortcodes,\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
+ 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
+ }\r
+ InitCommand(commands++, insert_length, sr.len, sr.len ^ sr.len_x_code,\r
+ 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
+ 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
+\r
+#undef Hasher\r
projects / mirror_edk2.git / blobdiff