Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(1)

Unified Diff: third_party/brotli/enc/backward_references_inc.h

Issue 2537133002: Update brotli to v1.0.0-snapshot. (Closed)
Patch Set: Fixed typo Created 4 years ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « third_party/brotli/enc/backward_references.cc ('k') | third_party/brotli/enc/bit_cost.h » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: third_party/brotli/enc/backward_references_inc.h
diff --git a/third_party/brotli/enc/backward_references_inc.h b/third_party/brotli/enc/backward_references_inc.h
new file mode 100644
index 0000000000000000000000000000000000000000..e4d4cd07847b3d3d6b7ae4faad0beb9ea87d761e
--- /dev/null
+++ b/third_party/brotli/enc/backward_references_inc.h
@@ -0,0 +1,147 @@
+/* NOLINT(build/header_guard) */
+/* Copyright 2013 Google Inc. All Rights Reserved.
+
+ Distributed under MIT license.
+ See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
+*/
+
+/* template parameters: FN */
+
+#define Hasher HASHER()
+
+static BROTLI_NOINLINE void FN(CreateBackwardReferences)(
+ MemoryManager* m, size_t num_bytes, size_t position, BROTLI_BOOL is_last,
+ const uint8_t* ringbuffer, size_t ringbuffer_mask,
+ const BrotliEncoderParams* params, Hasher* hasher, int* dist_cache,
+ size_t* last_insert_len, Command* commands, size_t* num_commands,
+ size_t* num_literals) {
+ /* Set maximum distance, see section 9.1. of the spec. */
+ const size_t max_backward_limit = MaxBackwardLimit(params->lgwin);
+
+ const Command* const orig_commands = commands;
+ size_t insert_length = *last_insert_len;
+ const size_t pos_end = position + num_bytes;
+ const size_t store_end = num_bytes >= FN(StoreLookahead)() ?
+ position + num_bytes - FN(StoreLookahead)() + 1 : position;
+
+ /* For speed up heuristics for random data. */
+ const size_t random_heuristics_window_size =
+ LiteralSpreeLengthForSparseSearch(params);
+ size_t apply_random_heuristics = position + random_heuristics_window_size;
+
+ /* Minimum score to accept a backward reference. */
+ const score_t kMinScore = BROTLI_SCORE_BASE + 400;
+
+ FN(Init)(m, hasher, ringbuffer, params, position, num_bytes, is_last);
+ if (BROTLI_IS_OOM(m)) return;
+ FN(StitchToPreviousBlock)(hasher, num_bytes, position,
+ ringbuffer, ringbuffer_mask);
+
+ while (position + FN(HashTypeLength)() < pos_end) {
+ size_t max_length = pos_end - position;
+ size_t max_distance = BROTLI_MIN(size_t, position, max_backward_limit);
+ HasherSearchResult sr;
+ sr.len = 0;
+ sr.len_x_code = 0;
+ sr.distance = 0;
+ sr.score = kMinScore;
+ if (FN(FindLongestMatch)(hasher, ringbuffer, ringbuffer_mask, dist_cache,
+ position, max_length, max_distance, &sr)) {
+ /* Found a match. Let's look for something even better ahead. */
+ int delayed_backward_references_in_row = 0;
+ --max_length;
+ for (;; --max_length) {
+ const score_t cost_diff_lazy = 700;
+ BROTLI_BOOL is_match_found;
+ HasherSearchResult sr2;
+ sr2.len = params->quality < MIN_QUALITY_FOR_EXTENSIVE_REFERENCE_SEARCH ?
+ BROTLI_MIN(size_t, sr.len - 1, max_length) : 0;
+ sr2.len_x_code = 0;
+ sr2.distance = 0;
+ sr2.score = kMinScore;
+ max_distance = BROTLI_MIN(size_t, position + 1, max_backward_limit);
+ is_match_found = FN(FindLongestMatch)(hasher, ringbuffer,
+ ringbuffer_mask, dist_cache, position + 1, max_length, max_distance,
+ &sr2);
+ if (is_match_found && sr2.score >= sr.score + cost_diff_lazy) {
+ /* Ok, let's just write one byte for now and start a match from the
+ next byte. */
+ ++position;
+ ++insert_length;
+ sr = sr2;
+ if (++delayed_backward_references_in_row < 4 &&
+ position + FN(HashTypeLength)() < pos_end) {
+ continue;
+ }
+ }
+ break;
+ }
+ apply_random_heuristics =
+ position + 2 * sr.len + random_heuristics_window_size;
+ max_distance = BROTLI_MIN(size_t, position, max_backward_limit);
+ {
+ /* The first 16 codes are special short-codes,
+ and the minimum offset is 1. */
+ size_t distance_code =
+ ComputeDistanceCode(sr.distance, max_distance, dist_cache);
+ if (sr.distance <= max_distance && distance_code > 0) {
+ dist_cache[3] = dist_cache[2];
+ dist_cache[2] = dist_cache[1];
+ dist_cache[1] = dist_cache[0];
+ dist_cache[0] = (int)sr.distance;
+ }
+ InitCommand(commands++, insert_length, sr.len, sr.len ^ sr.len_x_code,
+ distance_code);
+ }
+ *num_literals += insert_length;
+ insert_length = 0;
+ /* Put the hash keys into the table, if there are enough bytes left.
+ Depending on the hasher implementation, it can push all positions
+ in the given range or only a subset of them. */
+ FN(StoreRange)(hasher, ringbuffer, ringbuffer_mask, position + 2,
+ BROTLI_MIN(size_t, position + sr.len, store_end));
+ position += sr.len;
+ } else {
+ ++insert_length;
+ ++position;
+ /* If we have not seen matches for a long time, we can skip some
+ match lookups. Unsuccessful match lookups are very very expensive
+ and this kind of a heuristic speeds up compression quite
+ a lot. */
+ if (position > apply_random_heuristics) {
+ /* Going through uncompressible data, jump. */
+ if (position >
+ apply_random_heuristics + 4 * random_heuristics_window_size) {
+ /* It is quite a long time since we saw a copy, so we assume
+ that this data is not compressible, and store hashes less
+ often. Hashes of non compressible data are less likely to
+ turn out to be useful in the future, too, so we store less of
+ them to not to flood out the hash table of good compressible
+ data. */
+ const size_t kMargin =
+ BROTLI_MAX(size_t, FN(StoreLookahead)() - 1, 4);
+ size_t pos_jump =
+ BROTLI_MIN(size_t, position + 16, pos_end - kMargin);
+ for (; position < pos_jump; position += 4) {
+ FN(Store)(hasher, ringbuffer, ringbuffer_mask, position);
+ insert_length += 4;
+ }
+ } else {
+ const size_t kMargin =
+ BROTLI_MAX(size_t, FN(StoreLookahead)() - 1, 2);
+ size_t pos_jump =
+ BROTLI_MIN(size_t, position + 8, pos_end - kMargin);
+ for (; position < pos_jump; position += 2) {
+ FN(Store)(hasher, ringbuffer, ringbuffer_mask, position);
+ insert_length += 2;
+ }
+ }
+ }
+ }
+ }
+ insert_length += pos_end - position;
+ *last_insert_len = insert_length;
+ *num_commands += (size_t)(commands - orig_commands);
+}
+
+#undef Hasher
« no previous file with comments | « third_party/brotli/enc/backward_references.cc ('k') | third_party/brotli/enc/bit_cost.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698