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