c/enc/encoder_dict.h

/* Copyright 2017 Google Inc. All Rights Reserved.

   Distributed under MIT license.
   See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
*/

#ifndef BROTLI_ENC_ENCODER_DICT_H_
#define BROTLI_ENC_ENCODER_DICT_H_

#include "../common/dictionary.h"
#include "../common/platform.h"
#include <brotli/shared_dictionary.h>
#include <brotli/types.h>
#include "./compound_dictionary.h"
#include "./memory.h"
#include "./static_dict_lut.h"

#if defined(__cplusplus) || defined(c_plusplus)
extern "C" {
#endif

/*
Dictionary hierarchy for Encoder:
-SharedEncoderDictionary
--CompoundDictionary
---PreparedDictionary [up to 15x]
   = prefix dictionary with precomputed hashes
--ContextualEncoderDictionary
---BrotliEncoderDictionary [up to 64x]
   = for each context, precomputed static dictionary with words + transforms

Dictionary hiearchy from common: similar, but without precomputed hashes
-BrotliSharedDictionary
--BrotliDictionary [up to 64x]
--BrotliTransforms [up to 64x]
--const uint8_t* prefix [up to 15x]: compound dictionaries
*/

typedef struct BrotliTrieNode {
  uint8_t single;  /* if 1, sub is a single node for c instead of 256 */
  uint8_t c;
  uint8_t len_;  /* untransformed length */
  uint32_t idx_;  /* word index + num words * transform index */
  uint32_t sub;  /* index of sub node(s) in the pool */
} BrotliTrieNode;

typedef struct BrotliTrie {
  BrotliTrieNode* pool;
  size_t pool_capacity;
  size_t pool_size;
  BrotliTrieNode root;
} BrotliTrie;

BROTLI_INTERNAL const BrotliTrieNode* BrotliTrieSub(const BrotliTrie* trie,
    const BrotliTrieNode* node, uint8_t c);
/* Dictionary data (words and transforms) for 1 possible context */
typedef struct BrotliEncoderDictionary {
  const BrotliDictionary* words;
  uint32_t num_transforms;

  /* cut off for fast encoder */
  uint32_t cutoffTransformsCount;
  uint64_t cutoffTransforms;

  /* from dictionary_hash.h, for fast encoder */
  const uint16_t* hash_table_words;
  const uint8_t* hash_table_lengths;

  /* from static_dict_lut.h, for slow encoder */
  const uint16_t* buckets;
  const DictWord* dict_words;
  /* Heavy version, for use by slow encoder when there are custom transforms.
     Contains every possible transformed dictionary word in a trie. It encodes
     about as fast as the non-heavy encoder but consumes a lot of memory and
     takes time to build. */
  BrotliTrie trie;
  BROTLI_BOOL has_words_heavy;

  /* Reference to other dictionaries. */
  const struct ContextualEncoderDictionary* parent;

  /* Allocated memory, used only when not using the Brotli defaults */
  uint16_t* hash_table_data_words_;
  uint8_t* hash_table_data_lengths_;
  size_t buckets_alloc_size_;
  uint16_t* buckets_data_;
  size_t dict_words_alloc_size_;
  DictWord* dict_words_data_;
  BrotliDictionary* words_instance_;
} BrotliEncoderDictionary;

/* Dictionary data for all 64 contexts */
typedef struct ContextualEncoderDictionary {
  BROTLI_BOOL context_based;
  uint8_t num_dictionaries;
  uint8_t context_map[SHARED_BROTLI_NUM_DICTIONARY_CONTEXTS];
  const BrotliEncoderDictionary* dict[SHARED_BROTLI_NUM_DICTIONARY_CONTEXTS];

  /* If num_instances_ is 1, instance_ is used, else dynamic allocation with
     instances_ is used. */
  size_t num_instances_;
  BrotliEncoderDictionary instance_;
  BrotliEncoderDictionary* instances_;
} ContextualEncoderDictionary;

static const uint32_t kSharedDictionaryMagic = 0xDEBCEDE1;
static const uint32_t kManagedDictionaryMagic = 0xDEBCEDE2;

typedef struct SharedEncoderDictionary {
  /* Magic value to distinguish this struct from PreparedDictionary for
     certain external usages. */
  uint32_t magic;

  /* LZ77 prefix, compound dictionary */
  CompoundDictionary compound;

  /* Custom static dictionary (optionally context-based) */
  ContextualEncoderDictionary contextual;

  /* The maximum quality the dictionary was computed for */
  int max_quality;
} SharedEncoderDictionary;

typedef struct ManagedDictionary {
  uint32_t magic;
  MemoryManager memory_manager_;
  uint32_t* dictionary;
} ManagedDictionary;

/* Initializes to the brotli built-in dictionary */
BROTLI_INTERNAL void BrotliInitSharedEncoderDictionary(
    SharedEncoderDictionary* dict);

/* Initializes to shared dictionary that will be parsed from
   encoded_dict. Requires that you keep the encoded_dict buffer
   around, parts of data will point to it. */
BROTLI_INTERNAL BROTLI_BOOL BrotliInitCustomSharedEncoderDictionary(
    MemoryManager* m, const uint8_t* encoded_dict, size_t size,
    int quality, SharedEncoderDictionary* dict);

BROTLI_INTERNAL void BrotliCleanupSharedEncoderDictionary(
    MemoryManager* m, SharedEncoderDictionary* dict);

BROTLI_INTERNAL ManagedDictionary* BrotliCreateManagedDictionary(
    brotli_alloc_func alloc_func, brotli_free_func free_func, void* opaque);

BROTLI_INTERNAL void BrotliDestroyManagedDictionary(
    ManagedDictionary* dictionary);

#if defined(__cplusplus) || defined(c_plusplus)
}  /* extern "C" */
#endif

#endif  /* BROTLI_ENC_ENCODER_DICT_H_ */