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