Outline StoreRange in the new experimental hasher PiperOrigin-RevId: 979429901
diff --git a/c/enc/backward_references_inc_opt.h b/c/enc/backward_references_inc_opt.h index 02e1f4f..9e1ef64 100644 --- a/c/enc/backward_references_inc_opt.h +++ b/c/enc/backward_references_inc_opt.h
@@ -113,7 +113,7 @@ 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, + LookupCompoundDictionaryMatchOpt(¶ms->dictionary.compound, ringbuffer, ringbuffer_mask, dist_cache, position, max_length, dictionary_start, params->dist.max_distance, &sr); } @@ -144,7 +144,7 @@ max_distance, dictionary_start + gap, params->dist.max_distance, &sr2); if (ENABLE_COMPOUND_DICTIONARY) { - LookupCompoundDictionaryMatch( + LookupCompoundDictionaryMatchOpt( ¶ms->dictionary.compound, ringbuffer, ringbuffer_mask, dist_cache, position + 1, max_length, dictionary_start, params->dist.max_distance, &sr2);
diff --git a/c/enc/compound_dictionary.c b/c/enc/compound_dictionary.c index 878b6bc..23166c8 100644 --- a/c/enc/compound_dictionary.c +++ b/c/enc/compound_dictionary.c
@@ -205,6 +205,17 @@ compound->chunk_source[index] = (const uint8_t*)BROTLI_UNALIGNED_LOAD_PTR((const uint8_t**)tail); } + { + PreparedDictionaryView* view = &compound->chunk_views[index]; + view->slot_offsets = slot_offsets; + view->heads = heads; + view->items = items; + view->source = compound->chunk_source[index]; + view->source_size = dictionary->source_size; + view->hash_shift = 64u - dictionary->bucket_bits; + view->slot_mask = (~((uint32_t)0U)) >> (32 - dictionary->slot_bits); + view->hash_mask = (~((uint64_t)0U)) >> (64 - dictionary->hash_bits); + } } compound->num_chunks++; return BROTLI_TRUE;
diff --git a/c/enc/compound_dictionary.h b/c/enc/compound_dictionary.h index 686f92f..240a7f9 100644 --- a/c/enc/compound_dictionary.h +++ b/c/enc/compound_dictionary.h
@@ -51,12 +51,28 @@ BROTLI_INTERNAL void DestroyPreparedDictionary(MemoryManager* m, PreparedDictionary* dictionary); +/* A derived view of a PreparedDictionary, optimized for faster lookup. Used by + * the optimized H59 hasher. Its fields are a pure function of + * PreparedDictionary's so we can generate it at attach time. */ +typedef struct PreparedDictionaryView { + const uint32_t* slot_offsets; + const uint16_t* heads; + const uint32_t* items; + const uint8_t* source; + uint32_t source_size; + uint32_t hash_shift; /* 64 - bucket_bits */ + uint32_t slot_mask; + uint64_t hash_mask; +} PreparedDictionaryView; + typedef struct CompoundDictionary { /* LZ77 prefix, compound dictionary */ size_t num_chunks; size_t total_size; /* Client instances. */ const PreparedDictionary* chunks[SHARED_BROTLI_MAX_COMPOUND_DICTS + 1]; + /* TODO: const? */ + PreparedDictionaryView chunk_views[SHARED_BROTLI_MAX_COMPOUND_DICTS + 1]; const uint8_t* chunk_source[SHARED_BROTLI_MAX_COMPOUND_DICTS + 1]; size_t chunk_offsets[SHARED_BROTLI_MAX_COMPOUND_DICTS + 1];
diff --git a/c/enc/hash.h b/c/enc/hash.h index 5cca3c1..c88a6c5 100644 --- a/c/enc/hash.h +++ b/c/enc/hash.h
@@ -292,7 +292,7 @@ #undef HASHER #define HASHER() H59 -#include "hash_longest_match_simd_inc.h" /* NOLINT(build/include) */ +#include "hash_longest_match_simd_opt_inc.h" /* NOLINT(build/include) */ #undef HASHER #define HASHER() H68 @@ -751,6 +751,121 @@ return total_found; } +static BROTLI_INLINE void FindCompoundDictionaryMatchOpt( + const PreparedDictionaryView* self, const uint8_t* BROTLI_RESTRICT data, + const size_t ring_buffer_mask, const int* BROTLI_RESTRICT distance_cache, + const size_t cur_ix, const size_t max_length, const size_t distance_offset, + const size_t max_distance, HasherSearchResult* BROTLI_RESTRICT out) { + const uint32_t source_size = self->source_size; + const size_t boundary = distance_offset - source_size; + const uint32_t hash_shift = self->hash_shift; + const uint32_t slot_mask = self->slot_mask; + const uint64_t hash_mask = self->hash_mask; + + const uint32_t* slot_offsets = self->slot_offsets; + const uint16_t* heads = self->heads; + const uint32_t* items = self->items; + const uint8_t* source = self->source; + + const size_t cur_ix_masked = cur_ix & ring_buffer_mask; + score_t best_score = out->score; + size_t best_len = out->len; + size_t i; + const uint64_t h = + (BROTLI_UNALIGNED_LOAD64LE(&data[cur_ix_masked]) & hash_mask) * + kPreparedDictionaryHashMul64Long; + const uint32_t key = (uint32_t)(h >> hash_shift); + const uint32_t slot = key & slot_mask; + const uint32_t head = heads[key]; + const uint32_t* BROTLI_RESTRICT chain = &items[slot_offsets[slot] + head]; + uint32_t item = (head == 0xFFFF) ? 1 : 0; + + BROTLI_DCHECK(cur_ix_masked + max_length <= ring_buffer_mask + 1); + + for (i = 0; i < 4; ++i) { + const size_t distance = (size_t)distance_cache[i]; + size_t offset; + size_t limit; + size_t len; + if (distance <= boundary || distance > distance_offset) continue; + offset = distance_offset - distance; + limit = source_size - offset; + limit = limit > max_length ? max_length : limit; + len = FindMatchLengthWithLimit(&source[offset], &data[cur_ix_masked], + limit); + if (len >= 2) { + score_t score = BackwardReferenceScoreUsingLastDistance(len); + if (best_score < score) { + if (i != 0) score -= BackwardReferencePenaltyUsingLastDistance(i); + if (best_score < score) { + best_score = score; + if (len > best_len) best_len = len; + out->len = len; + out->len_code_delta = 0; + out->distance = distance; + out->score = best_score; + } + } + } + } + /* we require matches of len >4, so increase best_len to 3, so we can compare + * 4 bytes all the time. */ + if (best_len < 3) { + best_len = 3; + } + while (item == 0) { + size_t offset; + size_t distance; + size_t limit; + item = *chain; + chain++; + offset = item & 0x7FFFFFFF; + item &= 0x80000000; + distance = distance_offset - offset; + limit = source_size - offset; + limit = (limit > max_length) ? max_length : limit; + if (distance > max_distance) continue; + if (cur_ix_masked + best_len > ring_buffer_mask || best_len >= limit || + /* compare 4 bytes ending at best_len + 1 */ + BrotliUnalignedRead32(&data[cur_ix_masked + best_len - 3]) != + BrotliUnalignedRead32(&source[offset + best_len - 3])) { + continue; + } + { + const size_t len = FindMatchLengthWithLimit(&source[offset], + &data[cur_ix_masked], + limit); + if (len >= 4) { + score_t score = BackwardReferenceScore(len, distance); + if (best_score < score) { + best_score = score; + best_len = len; + out->len = best_len; + out->len_code_delta = 0; + out->distance = distance; + out->score = best_score; + } + } + } + } +} + +static BROTLI_INLINE void LookupCompoundDictionaryMatchOpt( + const CompoundDictionary* addon, const uint8_t* BROTLI_RESTRICT data, + const size_t ring_buffer_mask, const int* BROTLI_RESTRICT distance_cache, + const size_t cur_ix, const size_t max_length, + const size_t max_ring_buffer_distance, const size_t max_distance, + HasherSearchResult* sr) { + size_t base_offset = max_ring_buffer_distance + 1 + addon->total_size - 1; + size_t d; + for (d = 0; d < addon->num_chunks; ++d) { + FindCompoundDictionaryMatchOpt( + &addon->chunk_views[d], data, ring_buffer_mask, + distance_cache, cur_ix, max_length, + base_offset - addon->chunk_offsets[d], max_distance, sr); + } +} + #if defined(__cplusplus) || defined(c_plusplus) } /* extern "C" */ #endif
diff --git a/c/enc/hash_longest_match_simd_opt_inc.h b/c/enc/hash_longest_match_simd_opt_inc.h new file mode 100644 index 0000000..8a1cc8a --- /dev/null +++ b/c/enc/hash_longest_match_simd_opt_inc.h
@@ -0,0 +1,278 @@ +/* NOLINT(build/header_guard) */ +/* Copyright 2010 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 */ +/* A (forgetful) hash table to the data seen by the compressor, to + help create backward references to previous data. + This is a hash map of fixed size (bucket_size_) to a ring buffer of + fixed size (block_size_). The ring buffer contains the last block_size_ + index positions of the given hash key in the compressed data. */ +#define HashLongestMatch HASHER() +#define TAG_HASH_BITS 8 +#define TAG_HASH_MASK ((1 << TAG_HASH_BITS) - 1) +static BROTLI_INLINE size_t FN(HashTypeLength)(void) { return 4; } +static BROTLI_INLINE size_t FN(StoreLookahead)(void) { return 4; } +/* HashBytes is the function that chooses the bucket to place the address in. */ +static uint32_t FN(HashBytes)( + const uint8_t* BROTLI_RESTRICT data, const int shift) { + uint32_t h = BROTLI_UNALIGNED_LOAD32LE(data) * kHashMul32; + /* The higher bits contain more mixture from the multiplication, + so we take our results from there. */ + return (uint32_t)(h >> shift); +} +typedef struct HashLongestMatch { + /* Number of hash buckets. */ + size_t bucket_size_; + /* Only block_size_ newest backward references are kept, + and the older are forgotten. */ + size_t block_size_; + /* Left-shift for computing hash bucket index from hash value. */ + int hash_shift_; + /* Mask for accessing entries in a block (in a ring-buffer manner). */ + uint32_t block_mask_; + int block_bits_; + int num_last_distances_to_check_; + /* Shortcuts. */ + HasherCommon* common_; + /* --- Dynamic size members --- */ + /* Number of entries in a particular bucket. */ + uint16_t* num_; /* uint16_t[bucket_size]; */ + uint8_t* tags_; + /* Buckets containing block_size_ of backward references. */ + uint32_t* buckets_; /* uint32_t[bucket_size * block_size]; */ +} HashLongestMatch; +static void FN(Initialize)( + HasherCommon* common, HashLongestMatch* BROTLI_RESTRICT self, + const BrotliEncoderParams* params) { + self->common_ = common; + BROTLI_UNUSED(params); + self->hash_shift_ = 32 - common->params.bucket_bits - TAG_HASH_BITS; + self->bucket_size_ = (size_t)1 << common->params.bucket_bits; + self->block_size_ = (size_t)1 << common->params.block_bits; + self->block_mask_ = (uint32_t)(self->block_size_ - 1); + self->num_ = (uint16_t*)common->extra[0]; + self->tags_ = (uint8_t*)common->extra[1]; + self->buckets_ = (uint32_t*)common->extra[2]; + self->block_bits_ = common->params.block_bits; + self->num_last_distances_to_check_ = + common->params.num_last_distances_to_check; +} +static void FN(Prepare)( + HashLongestMatch* BROTLI_RESTRICT self, BROTLI_BOOL one_shot, + size_t input_size, const uint8_t* BROTLI_RESTRICT data) { + uint16_t* BROTLI_RESTRICT num = self->num_; + /* Partial preparation is 100 times slower (per socket). */ + size_t partial_prepare_threshold = self->bucket_size_ >> 6; + if (one_shot && input_size <= partial_prepare_threshold) { + size_t i; + for (i = 0; i < input_size; ++i) { + const uint32_t hash = FN(HashBytes)(&data[i], self->hash_shift_); + const uint32_t key = hash >> TAG_HASH_BITS; + num[key] = 65535; + } + } else { + /* Set all the bytes of num to 255, which makes each uint16_t 65535. */ + memset(num, 255, self->bucket_size_ * sizeof(num[0])); + } +} +static BROTLI_INLINE void FN(HashMemAllocInBytes)( + const BrotliEncoderParams* params, BROTLI_BOOL one_shot, + size_t input_size, size_t* alloc_size) { + size_t bucket_size = (size_t)1 << params->hasher.bucket_bits; + size_t block_size = (size_t)1 << params->hasher.block_bits; + BROTLI_UNUSED(one_shot); + BROTLI_UNUSED(input_size); + alloc_size[0] = sizeof(uint16_t) * bucket_size; + alloc_size[1] = sizeof(uint8_t) * bucket_size * block_size; + alloc_size[2] = sizeof(uint32_t) * bucket_size * block_size; +} +/* Look at 4 bytes at &data[ix & mask]. + Compute a hash from these, and store the value of ix at that position. */ +static BROTLI_INLINE void FN(Store)( + HashLongestMatch* BROTLI_RESTRICT self, const uint8_t* BROTLI_RESTRICT data, + const size_t mask, const size_t ix) { + uint16_t* BROTLI_RESTRICT num = self->num_; + uint8_t* BROTLI_RESTRICT tags = self->tags_; + uint32_t* BROTLI_RESTRICT buckets = self->buckets_; + const size_t hash = FN(HashBytes)(&data[ix & mask], self->hash_shift_); + const size_t key = hash >> TAG_HASH_BITS; + const uint8_t tag = hash & TAG_HASH_MASK; + const size_t minor_ix = num[key] & self->block_mask_; + const size_t offset = minor_ix + (key << self->block_bits_); + --num[key]; + buckets[offset] = (uint32_t)ix; + tags[offset] = tag; +} +static BROTLI_MAYBE_INLINE BROTLI_NOINLINE void FN(StoreRange)( + HashLongestMatch* BROTLI_RESTRICT self, const uint8_t* BROTLI_RESTRICT data, + const size_t mask, const size_t ix_start, const size_t ix_end) { + size_t i; + for (i = ix_start; i < ix_end; ++i) { + FN(Store)(self, data, mask, i); + } +} +static BROTLI_INLINE void FN(StitchToPreviousBlock)( + HashLongestMatch* BROTLI_RESTRICT self, + size_t num_bytes, size_t position, const uint8_t* ringbuffer, + size_t ringbuffer_mask) { + if (num_bytes >= FN(HashTypeLength)() - 1 && position >= 3) { + /* Prepare the hashes for three last bytes of the last write. + These could not be calculated before, since they require knowledge + of both the previous and the current block. */ + FN(Store)(self, ringbuffer, ringbuffer_mask, position - 3); + FN(Store)(self, ringbuffer, ringbuffer_mask, position - 2); + FN(Store)(self, ringbuffer, ringbuffer_mask, position - 1); + } +} +static BROTLI_INLINE void FN(PrepareDistanceCache)( + HashLongestMatch* BROTLI_RESTRICT self, + int* BROTLI_RESTRICT distance_cache) { + PrepareDistanceCache(distance_cache, self->num_last_distances_to_check_); +} + +/* Find a longest backward match of &data[cur_ix] up to the length of + max_length and stores the position cur_ix in the hash table. + REQUIRES: FN(PrepareDistanceCache) must be invoked for current distance cache + values; if this method is invoked repeatedly with the same distance + cache values, it is enough to invoke FN(PrepareDistanceCache) once. + Does not look for matches longer than max_length. + Does not look for matches further away than max_backward. + Writes the best match into |out|. + |out|->score is updated only if a better match is found. */ +static BROTLI_INLINE void FN(FindLongestMatch)( + HashLongestMatch* BROTLI_RESTRICT self, + const BrotliEncoderDictionary* dictionary, + const uint8_t* BROTLI_RESTRICT data, const size_t ring_buffer_mask, + const int* BROTLI_RESTRICT distance_cache, const size_t cur_ix, + const size_t max_length, const size_t max_backward, + const size_t dictionary_distance, const size_t max_distance, + HasherSearchResult* BROTLI_RESTRICT out) { + uint16_t* BROTLI_RESTRICT num = self->num_; + uint32_t* BROTLI_RESTRICT buckets = self->buckets_; + uint8_t* BROTLI_RESTRICT tags = self->tags_; + const size_t cur_ix_masked = cur_ix & ring_buffer_mask; + /* Don't accept a short copy from far away. */ + score_t min_score = out->score; + score_t best_score = out->score; + size_t best_len = out->len; + size_t i; + /* Precalculate the hash key and prefetch the bucket. */ + const uint32_t hash = + FN(HashBytes)(&data[cur_ix_masked], self->hash_shift_); + const uint32_t key = hash >> TAG_HASH_BITS; + uint32_t* BROTLI_RESTRICT bucket = &buckets[key << self->block_bits_]; + uint8_t* BROTLI_RESTRICT tag_bucket = &tags[key << self->block_bits_]; + PREFETCH_L1(bucket); + PREFETCH_L1(tag_bucket); + if (self->block_bits_ > 4) PREFETCH_L1(bucket + 16); + out->len = 0; + out->len_code_delta = 0; + + BROTLI_DCHECK(cur_ix_masked + max_length <= ring_buffer_mask + 1); + + /* Try last distance first. */ + for (i = 0; i < (size_t)self->num_last_distances_to_check_; ++i) { + const size_t backward = (size_t)distance_cache[i]; + size_t prev_ix = (size_t)(cur_ix - backward); + if (prev_ix >= cur_ix) { + continue; + } + if (BROTLI_PREDICT_FALSE(backward > max_backward)) { + continue; + } + prev_ix &= ring_buffer_mask; + + if (cur_ix_masked + best_len > ring_buffer_mask) { + break; + } + if (prev_ix + best_len > ring_buffer_mask || + data[cur_ix_masked + best_len] != data[prev_ix + best_len]) { + continue; + } + { + const size_t len = FindMatchLengthWithLimit(&data[prev_ix], + &data[cur_ix_masked], + max_length); + if (len >= 3 || (len == 2 && i < 2)) { + /* Comparing for >= 2 does not change the semantics, but just saves for + a few unnecessary binary logarithms in backward reference score, + since we are not interested in such short matches. */ + score_t score = BackwardReferenceScoreUsingLastDistance(len); + if (best_score < score) { + if (i != 0) score -= BackwardReferencePenaltyUsingLastDistance(i); + if (best_score < score) { + best_score = score; + best_len = len; + out->len = best_len; + out->distance = backward; + out->score = best_score; + } + } + } + } + } + /* we require matches of len >4, so increase best_len to 3, so we can compare + * 4 bytes all the time. */ + if (best_len < 3) { + best_len = 3; + } + { + const uint8_t tag = hash & TAG_HASH_MASK; + const size_t head = (num[key] + 1) & self->block_mask_; + uint64_t matches = + GetMatchingTagMask(self->block_size_ / 16, tag, tag_bucket, head); + /* Mask off any matches from uninitialized tags. */ + uint16_t n = 65535 - num[key]; + uint64_t block_has_unused_slots = self->block_size_ > n; + uint64_t mask = (block_has_unused_slots << (n & (64 - 1))) - 1; + matches &= mask; + for (; matches > 0; matches &= (matches - 1)) { + const size_t rb_index = + (head + (size_t)BROTLI_TZCNT64(matches)) & self->block_mask_; + size_t prev_ix = bucket[rb_index]; + const size_t backward = cur_ix - prev_ix; + if (BROTLI_PREDICT_FALSE(backward > max_backward)) { + break; + } + prev_ix &= ring_buffer_mask; + if (cur_ix_masked + best_len > ring_buffer_mask) { + break; + } + if (prev_ix + best_len > ring_buffer_mask || + /* compare 4 bytes ending at best_len + 1 */ + BrotliUnalignedRead32(&data[cur_ix_masked + best_len - 3]) != + BrotliUnalignedRead32(&data[prev_ix + best_len - 3])) { + continue; + } + { + const size_t len = FindMatchLengthWithLimit(&data[prev_ix], + &data[cur_ix_masked], + max_length); + if (len >= 4) { + /* Comparing for >= 3 does not change the semantics, but just saves + for a few unnecessary binary logarithms in backward reference + score, since we are not interested in such short matches. */ + score_t score = BackwardReferenceScore(len, backward); + if (best_score < score) { + best_score = score; + best_len = len; + out->len = best_len; + out->distance = backward; + out->score = best_score; + } + } + } + } + bucket[num[key] & self->block_mask_] = (uint32_t)cur_ix; + tag_bucket[num[key] & self->block_mask_] = tag; + --num[key]; + } + if (min_score == out->score) { + SearchInStaticDictionary(dictionary, + self->common_, &data[cur_ix_masked], max_length, dictionary_distance, + max_distance, out, BROTLI_FALSE); + } +} +#undef HashLongestMatch