hash_to_binary_tree_inc.h | Explore in Territory

/* NOLINT(build/header_guard) */
/* Copyright 2016 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, BUCKET_BITS, MAX_TREE_COMP_LENGTH,
                        MAX_TREE_SEARCH_DEPTH */

/* A (forgetful) hash table where each hash bucket contains a binary tree of
   sequences whose first 4 bytes share the same hash code.
   Each sequence is MAX_TREE_COMP_LENGTH long and is identified by its starting
   position in the input data. The binary tree is sorted by the lexicographic
   order of the sequences, and it is also a max-heap with respect to the
   starting positions. */

#define HashToBinaryTree …

#define BUCKET_SIZE …

static BROTLI_INLINE size_t FN(HashTypeLength)(void) { … }
static BROTLI_INLINE size_t FN(StoreLookahead)(void) { … }

static uint32_t FN(HashBytes)(const uint8_t* BROTLI_RESTRICT data) { … }

H10;

static void FN(Initialize)(
    HasherCommon* common, HashToBinaryTree* BROTLI_RESTRICT self,
    const BrotliEncoderParams* params) { … }

static void FN(Prepare)
    (HashToBinaryTree* BROTLI_RESTRICT self, BROTLI_BOOL one_shot,
    size_t input_size, const uint8_t* BROTLI_RESTRICT data) { … }

static BROTLI_INLINE void FN(HashMemAllocInBytes)(
    const BrotliEncoderParams* params, BROTLI_BOOL one_shot,
    size_t input_size, size_t* alloc_size) { … }

static BROTLI_INLINE size_t FN(LeftChildIndex)(
    HashToBinaryTree* BROTLI_RESTRICT self,
    const size_t pos) { … }

static BROTLI_INLINE size_t FN(RightChildIndex)(
    HashToBinaryTree* BROTLI_RESTRICT self,
    const size_t pos) { … }

/* Stores the hash of the next 4 bytes and in a single tree-traversal, the
   hash bucket's binary tree is searched for matches and is re-rooted at the
   current position.

   If less than MAX_TREE_COMP_LENGTH data is available, the hash bucket of the
   current position is searched for matches, but the state of the hash table
   is not changed, since we can not know the final sorting order of the
   current (incomplete) sequence.

   This function must be called with increasing cur_ix positions. */
static BROTLI_INLINE BackwardMatch* FN(StoreAndFindMatches)(
    HashToBinaryTree* BROTLI_RESTRICT self, const uint8_t* BROTLI_RESTRICT data,
    const size_t cur_ix, const size_t ring_buffer_mask, const size_t max_length,
    const size_t max_backward, size_t* const BROTLI_RESTRICT best_len,
    BackwardMatch* BROTLI_RESTRICT matches) { … }

/* Finds all backward matches of &data[cur_ix & ring_buffer_mask] up to the
   length of max_length and stores the position cur_ix in the hash table.

   Sets *num_matches to the number of matches found, and stores the found
   matches in matches[0] to matches[*num_matches - 1]. The matches will be
   sorted by strictly increasing length and (non-strictly) increasing
   distance. */
static BROTLI_INLINE size_t FN(FindAllMatches)(
    HashToBinaryTree* BROTLI_RESTRICT self,
    const BrotliEncoderDictionary* dictionary,
    const uint8_t* BROTLI_RESTRICT data,
    const size_t ring_buffer_mask, const size_t cur_ix,
    const size_t max_length, const size_t max_backward,
    const size_t dictionary_distance, const BrotliEncoderParams* params,
    BackwardMatch* matches) { … }

/* Stores the hash of the next 4 bytes and re-roots the binary tree at the
   current sequence, without returning any matches.
   REQUIRES: ix + MAX_TREE_COMP_LENGTH <= end-of-current-block */
static BROTLI_INLINE void FN(Store)(HashToBinaryTree* BROTLI_RESTRICT self,
    const uint8_t* BROTLI_RESTRICT data,
    const size_t mask, const size_t ix) { … }

static BROTLI_INLINE void FN(StoreRange)(HashToBinaryTree* BROTLI_RESTRICT self,
    const uint8_t* BROTLI_RESTRICT data, const size_t mask,
    const size_t ix_start, const size_t ix_end) { … }

static BROTLI_INLINE void FN(StitchToPreviousBlock)(
    HashToBinaryTree* BROTLI_RESTRICT self,
    size_t num_bytes, size_t position, const uint8_t* ringbuffer,
    size_t ringbuffer_mask) { … }

#undef BUCKET_SIZE

#undef HashToBinaryTree
chromium/third_party/brotli/enc/hash_to_binary_tree_inc.h
