1 /* Copyright 2017 Google Inc. All Rights Reserved. 2 3 Distributed under MIT license. 4 See file LICENSE for detail or copy at https://opensource.org/licenses/MIT 5 */ 6 7 #ifndef BROTLI_ENC_ENCODER_DICT_H_ 8 #define BROTLI_ENC_ENCODER_DICT_H_ 9 10 #include "../common/dictionary.h" 11 #include "../common/platform.h" 12 #include <brotli/shared_dictionary.h> 13 #include <brotli/types.h> 14 #include "compound_dictionary.h" 15 #include "memory.h" 16 #include "static_dict_lut.h" 17 18 #if defined(__cplusplus) || defined(c_plusplus) 19 extern "C" { 20 #endif 21 22 /* 23 Dictionary hierarchy for Encoder: 24 -SharedEncoderDictionary 25 --CompoundDictionary 26 ---PreparedDictionary [up to 15x] 27 = prefix dictionary with precomputed hashes 28 --ContextualEncoderDictionary 29 ---BrotliEncoderDictionary [up to 64x] 30 = for each context, precomputed static dictionary with words + transforms 31 32 Dictionary hiearchy from common: similar, but without precomputed hashes 33 -BrotliSharedDictionary 34 --BrotliDictionary [up to 64x] 35 --BrotliTransforms [up to 64x] 36 --const uint8_t* prefix [up to 15x]: compound dictionaries 37 */ 38 39 typedef struct BrotliTrieNode { 40 uint8_t single; /* if 1, sub is a single node for c instead of 256 */ 41 uint8_t c; 42 uint8_t len_; /* untransformed length */ 43 uint32_t idx_; /* word index + num words * transform index */ 44 uint32_t sub; /* index of sub node(s) in the pool */ 45 } BrotliTrieNode; 46 47 typedef struct BrotliTrie { 48 BrotliTrieNode* pool; 49 size_t pool_capacity; 50 size_t pool_size; 51 BrotliTrieNode root; 52 } BrotliTrie; 53 54 BROTLI_INTERNAL const BrotliTrieNode* BrotliTrieSub(const BrotliTrie* trie, 55 const BrotliTrieNode* node, uint8_t c); 56 /* Dictionary data (words and transforms) for 1 possible context */ 57 typedef struct BrotliEncoderDictionary { 58 const BrotliDictionary* words; 59 uint32_t num_transforms; 60 61 /* cut off for fast encoder */ 62 uint32_t cutoffTransformsCount; 63 uint64_t cutoffTransforms; 64 65 /* from dictionary_hash.h, for fast encoder */ 66 const uint16_t* hash_table_words; 67 const uint8_t* hash_table_lengths; 68 69 /* from static_dict_lut.h, for slow encoder */ 70 const uint16_t* buckets; 71 const DictWord* dict_words; 72 /* Heavy version, for use by slow encoder when there are custom transforms. 73 Contains every possible transformed dictionary word in a trie. It encodes 74 about as fast as the non-heavy encoder but consumes a lot of memory and 75 takes time to build. */ 76 BrotliTrie trie; 77 BROTLI_BOOL has_words_heavy; 78 79 /* Reference to other dictionaries. */ 80 const struct ContextualEncoderDictionary* parent; 81 82 /* Allocated memory, used only when not using the Brotli defaults */ 83 uint16_t* hash_table_data_words_; 84 uint8_t* hash_table_data_lengths_; 85 size_t buckets_alloc_size_; 86 uint16_t* buckets_data_; 87 size_t dict_words_alloc_size_; 88 DictWord* dict_words_data_; 89 BrotliDictionary* words_instance_; 90 } BrotliEncoderDictionary; 91 92 /* Dictionary data for all 64 contexts */ 93 typedef struct ContextualEncoderDictionary { 94 BROTLI_BOOL context_based; 95 uint8_t num_dictionaries; 96 uint8_t context_map[SHARED_BROTLI_NUM_DICTIONARY_CONTEXTS]; 97 const BrotliEncoderDictionary* dict[SHARED_BROTLI_NUM_DICTIONARY_CONTEXTS]; 98 99 /* If num_instances_ is 1, instance_ is used, else dynamic allocation with 100 instances_ is used. */ 101 size_t num_instances_; 102 BrotliEncoderDictionary instance_; 103 BrotliEncoderDictionary* instances_; 104 } ContextualEncoderDictionary; 105 106 static const uint32_t kSharedDictionaryMagic = 0xDEBCEDE1; 107 static const uint32_t kManagedDictionaryMagic = 0xDEBCEDE2; 108 109 typedef struct SharedEncoderDictionary { 110 /* Magic value to distinguish this struct from PreparedDictionary for 111 certain external usages. */ 112 uint32_t magic; 113 114 /* LZ77 prefix, compound dictionary */ 115 CompoundDictionary compound; 116 117 /* Custom static dictionary (optionally context-based) */ 118 ContextualEncoderDictionary contextual; 119 120 /* The maximum quality the dictionary was computed for */ 121 int max_quality; 122 } SharedEncoderDictionary; 123 124 typedef struct ManagedDictionary { 125 uint32_t magic; 126 MemoryManager memory_manager_; 127 uint32_t* dictionary; 128 } ManagedDictionary; 129 130 /* Initializes to the brotli built-in dictionary */ 131 BROTLI_INTERNAL void BrotliInitSharedEncoderDictionary( 132 SharedEncoderDictionary* dict); 133 134 /* Initializes to shared dictionary that will be parsed from 135 encoded_dict. Requires that you keep the encoded_dict buffer 136 around, parts of data will point to it. */ 137 BROTLI_INTERNAL BROTLI_BOOL BrotliInitCustomSharedEncoderDictionary( 138 MemoryManager* m, const uint8_t* encoded_dict, size_t size, 139 int quality, SharedEncoderDictionary* dict); 140 141 BROTLI_INTERNAL void BrotliCleanupSharedEncoderDictionary( 142 MemoryManager* m, SharedEncoderDictionary* dict); 143 144 BROTLI_INTERNAL ManagedDictionary* BrotliCreateManagedDictionary( 145 brotli_alloc_func alloc_func, brotli_free_func free_func, void* opaque); 146 147 BROTLI_INTERNAL void BrotliDestroyManagedDictionary( 148 ManagedDictionary* dictionary); 149 150 #if defined(__cplusplus) || defined(c_plusplus) 151 } /* extern "C" */ 152 #endif 153 154 #endif /* BROTLI_ENC_ENCODER_DICT_H_ */ 155