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