+++ /dev/null
-/* NOLINT(build/header_guard) */\r
-/* Copyright 2018 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, JUMP, NUMBUCKETS, MASK, CHUNKLEN */\r
-/* NUMBUCKETS / (MASK + 1) = probability of storing and using hash code. */\r
-/* JUMP = skip bytes for speedup */\r
-\r
-/* Rolling hash for long distance long string matches. Stores one position\r
- per bucket, bucket key is computed over a long region. */\r
-\r
-#define HashRolling HASHER()\r
-\r
-static const uint32_t FN(kRollingHashMul32) = 69069;\r
-static const uint32_t FN(kInvalidPos) = 0xffffffff;\r
-\r
-/* This hasher uses a longer forward length, but returning a higher value here\r
- will hurt compression by the main hasher when combined with a composite\r
- hasher. The hasher tests for forward itself instead. */\r
-static BROTLI_INLINE size_t FN(HashTypeLength)(void) { return 4; }\r
-static BROTLI_INLINE size_t FN(StoreLookahead)(void) { return 4; }\r
-\r
-/* Computes a code from a single byte. A lookup table of 256 values could be\r
- used, but simply adding 1 works about as good. */\r
-static uint32_t FN(HashByte)(uint8_t byte) {\r
- return (uint32_t)byte + 1u;\r
-}\r
-\r
-static uint32_t FN(HashRollingFunctionInitial)(uint32_t state, uint8_t add,\r
- uint32_t factor) {\r
- return (uint32_t)(factor * state + FN(HashByte)(add));\r
-}\r
-\r
-static uint32_t FN(HashRollingFunction)(uint32_t state, uint8_t add,\r
- uint8_t rem, uint32_t factor,\r
- uint32_t factor_remove) {\r
- return (uint32_t)(factor * state +\r
- FN(HashByte)(add) - factor_remove * FN(HashByte)(rem));\r
-}\r
-\r
-typedef struct HashRolling {\r
- uint32_t state;\r
- uint32_t* table;\r
- size_t next_ix;\r
-\r
- uint32_t chunk_len;\r
- uint32_t factor;\r
- uint32_t factor_remove;\r
-} HashRolling;\r
-\r
-static BROTLI_INLINE HashRolling* FN(Self)(HasherHandle handle) {\r
- return (HashRolling*)&(GetHasherCommon(handle)[1]);\r
-}\r
-\r
-static void FN(Initialize)(\r
- HasherHandle handle, const BrotliEncoderParams* params) {\r
- HashRolling* self = FN(Self)(handle);\r
- size_t i;\r
- self->state = 0;\r
- self->next_ix = 0;\r
-\r
- self->factor = FN(kRollingHashMul32);\r
-\r
- /* Compute the factor of the oldest byte to remove: factor**steps modulo\r
- 0xffffffff (the multiplications rely on 32-bit overflow) */\r
- self->factor_remove = 1;\r
- for (i = 0; i < CHUNKLEN; i += JUMP) {\r
- self->factor_remove *= self->factor;\r
- }\r
-\r
- self->table = (uint32_t*)((HasherHandle)self + sizeof(HashRolling));\r
- for (i = 0; i < NUMBUCKETS; i++) {\r
- self->table[i] = FN(kInvalidPos);\r
- }\r
-\r
- BROTLI_UNUSED(params);\r
-}\r
-\r
-static void FN(Prepare)(HasherHandle handle, BROTLI_BOOL one_shot,\r
- size_t input_size, const uint8_t* data) {\r
- HashRolling* self = FN(Self)(handle);\r
- size_t i;\r
- /* Too small size, cannot use this hasher. */\r
- if (input_size < CHUNKLEN) return;\r
- self->state = 0;\r
- for (i = 0; i < CHUNKLEN; i += JUMP) {\r
- self->state = FN(HashRollingFunctionInitial)(\r
- self->state, data[i], self->factor);\r
- }\r
- BROTLI_UNUSED(one_shot);\r
-}\r
-\r
-static BROTLI_INLINE size_t FN(HashMemAllocInBytes)(\r
- const BrotliEncoderParams* params, BROTLI_BOOL one_shot,\r
- size_t input_size) {\r
- return sizeof(HashRolling) + NUMBUCKETS * sizeof(uint32_t);\r
- BROTLI_UNUSED(params);\r
- BROTLI_UNUSED(one_shot);\r
- BROTLI_UNUSED(input_size);\r
-}\r
-\r
-static BROTLI_INLINE void FN(Store)(HasherHandle BROTLI_RESTRICT handle,\r
- const uint8_t* BROTLI_RESTRICT data, const size_t mask, const size_t ix) {\r
- BROTLI_UNUSED(handle);\r
- BROTLI_UNUSED(data);\r
- BROTLI_UNUSED(mask);\r
- BROTLI_UNUSED(ix);\r
-}\r
-\r
-static BROTLI_INLINE void FN(StoreRange)(HasherHandle handle,\r
- const uint8_t* data, const size_t mask, const size_t ix_start,\r
- const size_t ix_end) {\r
- BROTLI_UNUSED(handle);\r
- BROTLI_UNUSED(data);\r
- BROTLI_UNUSED(mask);\r
- BROTLI_UNUSED(ix_start);\r
- BROTLI_UNUSED(ix_end);\r
-}\r
-\r
-static BROTLI_INLINE void FN(StitchToPreviousBlock)(HasherHandle handle,\r
- size_t num_bytes, size_t position, const uint8_t* ringbuffer,\r
- size_t ring_buffer_mask) {\r
- /* In this case we must re-initialize the hasher from scratch from the\r
- current position. */\r
- HashRolling* self = FN(Self)(handle);\r
- size_t position_masked;\r
- size_t available = num_bytes;\r
- if ((position & (JUMP - 1)) != 0) {\r
- size_t diff = JUMP - (position & (JUMP - 1));\r
- available = (diff > available) ? 0 : (available - diff);\r
- position += diff;\r
- }\r
- position_masked = position & ring_buffer_mask;\r
- /* wrapping around ringbuffer not handled. */\r
- if (available > ring_buffer_mask - position_masked) {\r
- available = ring_buffer_mask - position_masked;\r
- }\r
-\r
- FN(Prepare)(handle, BROTLI_FALSE, available,\r
- ringbuffer + (position & ring_buffer_mask));\r
- self->next_ix = position;\r
- BROTLI_UNUSED(num_bytes);\r
-}\r
-\r
-static BROTLI_INLINE void FN(PrepareDistanceCache)(\r
- HasherHandle handle, int* BROTLI_RESTRICT distance_cache) {\r
- BROTLI_UNUSED(handle);\r
- BROTLI_UNUSED(distance_cache);\r
-}\r
-\r
-static BROTLI_INLINE void FN(FindLongestMatch)(HasherHandle handle,\r
- const BrotliEncoderDictionary* dictionary,\r
- const uint8_t* BROTLI_RESTRICT data, const size_t ring_buffer_mask,\r
- const int* BROTLI_RESTRICT distance_cache, const size_t cur_ix,\r
- const size_t max_length, const size_t max_backward, const size_t gap,\r
- const size_t max_distance, HasherSearchResult* BROTLI_RESTRICT out) {\r
- HashRolling* self = FN(Self)(handle);\r
- const size_t cur_ix_masked = cur_ix & ring_buffer_mask;\r
- size_t pos = self->next_ix;\r
-\r
- if ((cur_ix & (JUMP - 1)) != 0) return;\r
-\r
- /* Not enough lookahead */\r
- if (max_length < CHUNKLEN) return;\r
-\r
- for (pos = self->next_ix; pos <= cur_ix; pos += JUMP) {\r
- uint32_t code = self->state & MASK;\r
-\r
- uint8_t rem = data[pos & ring_buffer_mask];\r
- uint8_t add = data[(pos + CHUNKLEN) & ring_buffer_mask];\r
- size_t found_ix = FN(kInvalidPos);\r
-\r
- self->state = FN(HashRollingFunction)(\r
- self->state, add, rem, self->factor, self->factor_remove);\r
-\r
- if (code < NUMBUCKETS) {\r
- found_ix = self->table[code];\r
- self->table[code] = (uint32_t)pos;\r
- if (pos == cur_ix && found_ix != FN(kInvalidPos)) {\r
- /* The cast to 32-bit makes backward distances up to 4GB work even\r
- if cur_ix is above 4GB, despite using 32-bit values in the table. */\r
- size_t backward = (uint32_t)(cur_ix - found_ix);\r
- if (backward <= max_backward) {\r
- const size_t found_ix_masked = found_ix & ring_buffer_mask;\r
- const size_t len = FindMatchLengthWithLimit(&data[found_ix_masked],\r
- &data[cur_ix_masked],\r
- max_length);\r
- if (len >= 4 && len > out->len) {\r
- score_t score = BackwardReferenceScore(len, backward);\r
- if (score > out->score) {\r
- out->len = len;\r
- out->distance = backward;\r
- out->score = score;\r
- out->len_code_delta = 0;\r
- }\r
- }\r
- }\r
- }\r
- }\r
- }\r
-\r
- self->next_ix = cur_ix + JUMP;\r
-\r
- /* NOTE: this hasher does not search in the dictionary. It is used as\r
- backup-hasher, the main hasher already searches in it. */\r
- BROTLI_UNUSED(dictionary);\r
- BROTLI_UNUSED(distance_cache);\r
- BROTLI_UNUSED(gap);\r
- BROTLI_UNUSED(max_distance);\r
-}\r
-\r
-#undef HashRolling\r
projects / mirror_edk2.git / blobdiff