Add an experimental new hasher. PiperOrigin-RevId: 975395376
diff --git a/c/enc/backward_references.c b/c/enc/backward_references.c index b5c818d..018591e 100644 --- a/c/enc/backward_references.c +++ b/c/enc/backward_references.c
@@ -182,6 +182,11 @@ #include "backward_references_inc.h" #undef HASHER +#define HASHER() H59 +/* NOLINTNEXTLINE(build/include) */ +#include "backward_references_inc_opt.h" +#undef HASHER + #define HASHER() H68 /* NOLINTNEXTLINE(build/include) */ #include "backward_references_inc.h" @@ -234,6 +239,10 @@ /* NOLINTNEXTLINE(build/include) */ #include "backward_references_inc.h" #undef HASHER +#define HASHER() H59 +/* NOLINTNEXTLINE(build/include) */ +#include "backward_references_inc_opt.h" +#undef HASHER #define HASHER() H68 /* NOLINTNEXTLINE(build/include) */ #include "backward_references_inc.h" @@ -268,6 +277,7 @@ CASE_(6) #if defined(BROTLI_MAX_SIMD_QUALITY) CASE_(58) + CASE_(59) CASE_(68) #endif CASE_(40)
diff --git a/c/enc/backward_references_inc_opt.h b/c/enc/backward_references_inc_opt.h new file mode 100644 index 0000000..02e1f4f --- /dev/null +++ b/c/enc/backward_references_inc_opt.h
@@ -0,0 +1,242 @@ +/* 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: EXPORT_FN, FN */ + +static BROTLI_NOINLINE void EXPORT_FN(CreateBackwardReferences)( + size_t num_bytes, size_t position, + const uint8_t* ringbuffer, size_t ringbuffer_mask, + ContextLut literal_context_lut, const BrotliEncoderParams* params, + Hasher* hasher, int* dist_cache, size_t* last_insert_len, + Command* commands, size_t* num_commands, size_t* num_literals) { + HASHER()* privat = &hasher->privat.FN(_); + /* Set maximum distance, see section 9.1. of the spec. */ + const size_t max_backward_limit = BROTLI_MAX_BACKWARD_LIMIT(params->lgwin); + const size_t position_offset = params->stream_offset; + + 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; + const size_t gap = params->dictionary.compound.total_size; + + /* Minimum score to accept a backward reference. */ + const score_t kMinScore = BROTLI_SCORE_BASE + 100; + + FN(PrepareDistanceCache)(privat, dist_cache); + + size_t next_base64_pos = pos_end; + if (params->base64_mode && + hasher->common.num_base64_regions < params->max_base64_regions) { + next_base64_pos = + FindNextBase64Trigger(ringbuffer, ringbuffer_mask, position, pos_end); + } + while (position + FN(HashTypeLength)() < pos_end) { + if (position >= next_base64_pos) { + /* Find where it ends */ + size_t scan_pos = position + kBase64TriggerLen; + size_t first_equal_pos = 0; + while (scan_pos < pos_end) { + uint8_t c = ringbuffer[scan_pos & ringbuffer_mask]; + if (IsBase64Char(c)) { + if (first_equal_pos != 0) { + scan_pos = first_equal_pos; + break; + } + scan_pos++; + } else if (c == '=') { + if (first_equal_pos == 0) { + first_equal_pos = scan_pos; + } + scan_pos++; + } else { + break; + } + } + /* Jump directly to the end of base64 block */ + /* Skip the ';base64,' trigger */ + size_t start_pos = position + kBase64TriggerLen; + size_t length = scan_pos - start_pos; + /* Exclude '=' characters from the flat 6-bit entropy block */ + while (length > 0 && + ringbuffer[(start_pos + length - 1) & ringbuffer_mask] == '=') { + length--; + } + if (length > 0) { + hasher->common.base64_regions[hasher->common.num_base64_regions] + .start_literal_pos = start_pos; + hasher->common.base64_regions[hasher->common.num_base64_regions] + .length = length; + hasher->common.num_base64_regions++; + } + insert_length += (scan_pos - position); + position = scan_pos; + if (hasher->common.num_base64_regions < params->max_base64_regions) { + next_base64_pos = FindNextBase64Trigger(ringbuffer, ringbuffer_mask, + position, pos_end); + } else { + next_base64_pos = pos_end; + } + continue; + } + size_t max_length = pos_end - position; + size_t max_distance = BROTLI_MIN(size_t, position, max_backward_limit); + size_t dictionary_start = BROTLI_MIN(size_t, + position + position_offset, max_backward_limit); + HasherSearchResult sr; + int dict_id = 0; + uint8_t p1 = 0; + uint8_t p2 = 0; + if (params->dictionary.contextual.context_based) { + p1 = position >= 1 ? + ringbuffer[(size_t)(position - 1) & ringbuffer_mask] : 0; + p2 = position >= 2 ? + ringbuffer[(size_t)(position - 2) & ringbuffer_mask] : 0; + dict_id = params->dictionary.contextual.context_map[ + BROTLI_CONTEXT(p1, p2, literal_context_lut)]; + } + sr.len = 0; + sr.len_code_delta = 0; + sr.distance = 0; + sr.score = kMinScore; + FN(FindLongestMatch)(privat, params->dictionary.contextual.dict[dict_id], + ringbuffer, ringbuffer_mask, dist_cache, position, max_length, + max_distance, dictionary_start + gap, params->dist.max_distance, &sr); + if (ENABLE_COMPOUND_DICTIONARY) { + LookupCompoundDictionaryMatch(¶ms->dictionary.compound, ringbuffer, + ringbuffer_mask, dist_cache, position, max_length, + dictionary_start, params->dist.max_distance, &sr); + } + if (sr.score > kMinScore) { + /* 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 = 175; + HasherSearchResult sr2; + sr2.len = params->quality < MIN_QUALITY_FOR_EXTENSIVE_REFERENCE_SEARCH ? + BROTLI_MIN(size_t, sr.len - 1, max_length) : 0; + sr2.len_code_delta = 0; + sr2.distance = 0; + sr2.score = kMinScore; + max_distance = BROTLI_MIN(size_t, position + 1, max_backward_limit); + dictionary_start = BROTLI_MIN(size_t, + position + 1 + position_offset, max_backward_limit); + if (params->dictionary.contextual.context_based) { + p2 = p1; + p1 = ringbuffer[position & ringbuffer_mask]; + dict_id = params->dictionary.contextual.context_map[ + BROTLI_CONTEXT(p1, p2, literal_context_lut)]; + } + FN(FindLongestMatch)(privat, + params->dictionary.contextual.dict[dict_id], + ringbuffer, ringbuffer_mask, dist_cache, position + 1, max_length, + max_distance, dictionary_start + gap, params->dist.max_distance, + &sr2); + if (ENABLE_COMPOUND_DICTIONARY) { + LookupCompoundDictionaryMatch( + ¶ms->dictionary.compound, ringbuffer, + ringbuffer_mask, dist_cache, position + 1, max_length, + dictionary_start, params->dist.max_distance, &sr2); + } + if (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; + dictionary_start = BROTLI_MIN(size_t, + position + position_offset, max_backward_limit); + { + /* The first 16 codes are special short-codes, + and the minimum offset is 1. */ + size_t distance_code = ComputeDistanceCode( + sr.distance, dictionary_start + gap, dist_cache); + if ((sr.distance <= (dictionary_start + gap)) && 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; + FN(PrepareDistanceCache)(privat, dist_cache); + } + InitCommand(commands++, ¶ms->dist, insert_length, + sr.len, sr.len_code_delta, 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. + Avoid hash poisoning with RLE data. */ + { + size_t range_start = position + 2; + size_t range_end = BROTLI_MIN(size_t, position + sr.len, store_end); + if (sr.distance < (sr.len >> 2)) { + range_start = BROTLI_MIN(size_t, range_end, BROTLI_MAX(size_t, + range_start, position + sr.len - (sr.distance << 2))); + } + FN(StoreRange)(privat, ringbuffer, ringbuffer_mask, range_start, + range_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)(privat, 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)(privat, ringbuffer, ringbuffer_mask, position); + insert_length += 2; + } + } + } + } + } + insert_length += pos_end - position; + *last_insert_len = insert_length; + *num_commands += (size_t)(commands - orig_commands); +}
diff --git a/c/enc/encode.c b/c/enc/encode.c index ac62a14..bf13e08 100644 --- a/c/enc/encode.c +++ b/c/enc/encode.c
@@ -118,6 +118,11 @@ state->params.simd_hasher = (BrotliEncoderSimdHasher)value; return BROTLI_TRUE; + case BROTLI_PARAM_HASHER_OPT: + if ((value != 0) && (value != 1)) return BROTLI_FALSE; + state->params.hasher_opt = TO_BROTLI_BOOL(value); + return BROTLI_TRUE; + default: return BROTLI_FALSE; } } @@ -709,6 +714,7 @@ params->base64_mode = (int)BROTLI_DEFAULT_BASE64_MODE; params->max_base64_regions = BROTLI_DEFAULT_MAX_BASE64_REGIONS; params->simd_hasher = BROTLI_DEFAULT_SIMD_HASHER; + params->hasher_opt = BROTLI_FALSE; params->dist.distance_postfix_bits = 0; params->dist.num_direct_distance_codes = 0; params->dist.alphabet_size_max =
diff --git a/c/enc/hash.h b/c/enc/hash.h index e0b51c4..5cca3c1 100644 --- a/c/enc/hash.h +++ b/c/enc/hash.h
@@ -291,6 +291,10 @@ #include "hash_longest_match_simd_inc.h" /* NOLINT(build/include) */ #undef HASHER +#define HASHER() H59 +#include "hash_longest_match_simd_inc.h" /* NOLINT(build/include) */ +#undef HASHER + #define HASHER() H68 #include "hash_longest_match64_simd_inc.h" /* NOLINT(build/include) */ #undef HASHER @@ -389,7 +393,7 @@ #if defined(BROTLI_MAX_SIMD_QUALITY) #define FOR_SIMPLE_HASHERS(H) \ - H(2) H(3) H(4) H(5) H(6) H(40) H(41) H(42) H(54) H(58) H(68) + H(2) H(3) H(4) H(5) H(6) H(40) H(41) H(42) H(54) H(58) H(59) H(68) #else #define FOR_SIMPLE_HASHERS(H) \ H(2) H(3) H(4) H(5) H(6) H(40) H(41) H(42) H(54)
diff --git a/c/enc/params.h b/c/enc/params.h index b34eb4b..45d873c 100644 --- a/c/enc/params.h +++ b/c/enc/params.h
@@ -44,6 +44,7 @@ int base64_mode; size_t max_base64_regions; BrotliEncoderSimdHasher simd_hasher; + BROTLI_BOOL hasher_opt; } BrotliEncoderParams; #endif /* BROTLI_ENC_PARAMS_H_ */
diff --git a/c/enc/quality.h b/c/enc/quality.h index 2b399be..b3d2bed 100644 --- a/c/enc/quality.h +++ b/c/enc/quality.h
@@ -128,14 +128,17 @@ - q04: h54 (longest_match_quickly), b20, l7 | for large files - q05: h58 (longest_match_simd ), b14, l4 + - q05: h59 (longest_match_simd_opt), b14, l4 - q05: h68 (longest_match64_simd ), b15, l5 | for large files - q05: h40 (forgetful_chain ), b15, l4 | for small window - q06: h58 (longest_match_simd ), b14, l4 + - q06: h59 (longest_match_simd_opt), b14, l4 - q06: h68 (longest_match64_simd ), b15, l5 | for large files - q06: h40 (forgetful_chain ), b15, l4 | for small window - q07: h58 (longest_match_simd ), b15, l4 + - q07: h59 (longest_match_simd_opt), b15, l4 - q07: h68 (longest_match64_simd ), b15, l5 | for large files - q07: h41 (forgetful_chain ), b15, l4 | for small window @@ -193,7 +196,8 @@ /* TODO(eustas): often previous setting (H6) is faster and denser; consider adding an option to use it. */ #if defined(BROTLI_MAX_SIMD_QUALITY) - hparams->type = ShouldUseSimdHasher(params) ? 58 : 5; + hparams->type = + ShouldUseSimdHasher(params) ? (params->hasher_opt ? 59 : 58) : 5; #else hparams->type = 5; #endif
diff --git a/c/include/brotli/encode.h b/c/include/brotli/encode.h index 076025e..a18a245 100644 --- a/c/include/brotli/encode.h +++ b/c/include/brotli/encode.h
@@ -261,7 +261,13 @@ * Controls whether the encoder uses SIMD hashers. * See ::BrotliEncoderSimdHasher for options. */ - BROTLI_PARAM_SIMD_HASHER = 12 + BROTLI_PARAM_SIMD_HASHER = 12, + /** + * Engage optimized hasher. + * + * When enabled (1), engages H59 instead of H58. + */ + BROTLI_PARAM_HASHER_OPT = 13 } BrotliEncoderParameter; /**
diff --git a/docs/encode.h.3 b/docs/encode.h.3 index c24fb97..dc6003c 100644 --- a/docs/encode.h.3 +++ b/docs/encode.h.3
@@ -362,6 +362,9 @@ .TP \fB\fIBROTLI_PARAM_SIMD_HASHER \fP\fP SIMD hasher usage mode\&. Controls whether the encoder uses SIMD hashers\&. See \fBBrotliEncoderSimdHasher\fP for options\&. +.TP +\fB\fIBROTLI_PARAM_HASHER_OPT \fP\fP +Engage optimized hasher\&. When enabled (1), engages H59 instead of H58\&. .SS "enum \fBBrotliEncoderSimdHasher\fP" .PP
diff --git a/setup.py b/setup.py index 6ed1838..b326304 100644 --- a/setup.py +++ b/setup.py
@@ -254,6 +254,7 @@ "c/enc/backward_references.h", "c/enc/backward_references_hq.h", "c/enc/backward_references_inc.h", + "c/enc/backward_references_inc_opt.h", "c/enc/bit_cost.h", "c/enc/bit_cost_inc.h", "c/enc/block_encoder_inc.h",