1 /* Copyright 2015 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 /* Brotli state for partial streaming decoding. */ 8 9 #ifndef BROTLI_DEC_STATE_H_ 10 #define BROTLI_DEC_STATE_H_ 11 12 #include "../common/constants.h" 13 #include "../common/dictionary.h" 14 #include "../common/platform.h" 15 #include "../common/transform.h" 16 #include <brotli/types.h> 17 #include "./bit_reader.h" 18 #include "./huffman.h" 19 20 #if defined(__cplusplus) || defined(c_plusplus) 21 extern "C" { 22 #endif 23 24 typedef enum { 25 BROTLI_STATE_UNINITED, 26 BROTLI_STATE_LARGE_WINDOW_BITS, 27 BROTLI_STATE_INITIALIZE, 28 BROTLI_STATE_METABLOCK_BEGIN, 29 BROTLI_STATE_METABLOCK_HEADER, 30 BROTLI_STATE_METABLOCK_HEADER_2, 31 BROTLI_STATE_CONTEXT_MODES, 32 BROTLI_STATE_COMMAND_BEGIN, 33 BROTLI_STATE_COMMAND_INNER, 34 BROTLI_STATE_COMMAND_POST_DECODE_LITERALS, 35 BROTLI_STATE_COMMAND_POST_WRAP_COPY, 36 BROTLI_STATE_UNCOMPRESSED, 37 BROTLI_STATE_METADATA, 38 BROTLI_STATE_COMMAND_INNER_WRITE, 39 BROTLI_STATE_METABLOCK_DONE, 40 BROTLI_STATE_COMMAND_POST_WRITE_1, 41 BROTLI_STATE_COMMAND_POST_WRITE_2, 42 BROTLI_STATE_HUFFMAN_CODE_0, 43 BROTLI_STATE_HUFFMAN_CODE_1, 44 BROTLI_STATE_HUFFMAN_CODE_2, 45 BROTLI_STATE_HUFFMAN_CODE_3, 46 BROTLI_STATE_CONTEXT_MAP_1, 47 BROTLI_STATE_CONTEXT_MAP_2, 48 BROTLI_STATE_TREE_GROUP, 49 BROTLI_STATE_DONE 50 } BrotliRunningState; 51 52 typedef enum { 53 BROTLI_STATE_METABLOCK_HEADER_NONE, 54 BROTLI_STATE_METABLOCK_HEADER_EMPTY, 55 BROTLI_STATE_METABLOCK_HEADER_NIBBLES, 56 BROTLI_STATE_METABLOCK_HEADER_SIZE, 57 BROTLI_STATE_METABLOCK_HEADER_UNCOMPRESSED, 58 BROTLI_STATE_METABLOCK_HEADER_RESERVED, 59 BROTLI_STATE_METABLOCK_HEADER_BYTES, 60 BROTLI_STATE_METABLOCK_HEADER_METADATA 61 } BrotliRunningMetablockHeaderState; 62 63 typedef enum { 64 BROTLI_STATE_UNCOMPRESSED_NONE, 65 BROTLI_STATE_UNCOMPRESSED_WRITE 66 } BrotliRunningUncompressedState; 67 68 typedef enum { 69 BROTLI_STATE_TREE_GROUP_NONE, 70 BROTLI_STATE_TREE_GROUP_LOOP 71 } BrotliRunningTreeGroupState; 72 73 typedef enum { 74 BROTLI_STATE_CONTEXT_MAP_NONE, 75 BROTLI_STATE_CONTEXT_MAP_READ_PREFIX, 76 BROTLI_STATE_CONTEXT_MAP_HUFFMAN, 77 BROTLI_STATE_CONTEXT_MAP_DECODE, 78 BROTLI_STATE_CONTEXT_MAP_TRANSFORM 79 } BrotliRunningContextMapState; 80 81 typedef enum { 82 BROTLI_STATE_HUFFMAN_NONE, 83 BROTLI_STATE_HUFFMAN_SIMPLE_SIZE, 84 BROTLI_STATE_HUFFMAN_SIMPLE_READ, 85 BROTLI_STATE_HUFFMAN_SIMPLE_BUILD, 86 BROTLI_STATE_HUFFMAN_COMPLEX, 87 BROTLI_STATE_HUFFMAN_LENGTH_SYMBOLS 88 } BrotliRunningHuffmanState; 89 90 typedef enum { 91 BROTLI_STATE_DECODE_UINT8_NONE, 92 BROTLI_STATE_DECODE_UINT8_SHORT, 93 BROTLI_STATE_DECODE_UINT8_LONG 94 } BrotliRunningDecodeUint8State; 95 96 typedef enum { 97 BROTLI_STATE_READ_BLOCK_LENGTH_NONE, 98 BROTLI_STATE_READ_BLOCK_LENGTH_SUFFIX 99 } BrotliRunningReadBlockLengthState; 100 101 struct BrotliDecoderStateStruct { 102 BrotliRunningState state; 103 104 /* This counter is reused for several disjoint loops. */ 105 int loop_counter; 106 107 BrotliBitReader br; 108 109 brotli_alloc_func alloc_func; 110 brotli_free_func free_func; 111 void* memory_manager_opaque; 112 113 /* Temporary storage for remaining input. */ 114 union { 115 uint64_t u64; 116 uint8_t u8[8]; 117 } buffer; 118 uint32_t buffer_length; 119 120 int pos; 121 int max_backward_distance; 122 int max_distance; 123 int ringbuffer_size; 124 int ringbuffer_mask; 125 int dist_rb_idx; 126 int dist_rb[4]; 127 int error_code; 128 uint32_t sub_loop_counter; 129 uint8_t* ringbuffer; 130 uint8_t* ringbuffer_end; 131 HuffmanCode* htree_command; 132 const uint8_t* context_lookup; 133 uint8_t* context_map_slice; 134 uint8_t* dist_context_map_slice; 135 136 /* This ring buffer holds a few past copy distances that will be used by 137 some special distance codes. */ 138 HuffmanTreeGroup literal_hgroup; 139 HuffmanTreeGroup insert_copy_hgroup; 140 HuffmanTreeGroup distance_hgroup; 141 HuffmanCode* block_type_trees; 142 HuffmanCode* block_len_trees; 143 /* This is true if the literal context map histogram type always matches the 144 block type. It is then not needed to keep the context (faster decoding). */ 145 int trivial_literal_context; 146 /* Distance context is actual after command is decoded and before distance is 147 computed. After distance computation it is used as a temporary variable. */ 148 int distance_context; 149 int meta_block_remaining_len; 150 uint32_t block_length_index; 151 uint32_t block_length[3]; 152 uint32_t num_block_types[3]; 153 uint32_t block_type_rb[6]; 154 uint32_t distance_postfix_bits; 155 uint32_t num_direct_distance_codes; 156 int distance_postfix_mask; 157 uint32_t num_dist_htrees; 158 uint8_t* dist_context_map; 159 HuffmanCode* literal_htree; 160 uint8_t dist_htree_index; 161 uint32_t repeat_code_len; 162 uint32_t prev_code_len; 163 164 int copy_length; 165 int distance_code; 166 167 /* For partial write operations. */ 168 size_t rb_roundtrips; /* how many times we went around the ring-buffer */ 169 size_t partial_pos_out; /* how much output to the user in total */ 170 171 /* For ReadHuffmanCode. */ 172 uint32_t symbol; 173 uint32_t repeat; 174 uint32_t space; 175 176 HuffmanCode table[32]; 177 /* List of heads of symbol chains. */ 178 uint16_t* symbol_lists; 179 /* Storage from symbol_lists. */ 180 uint16_t symbols_lists_array[BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1 + 181 BROTLI_NUM_COMMAND_SYMBOLS]; 182 /* Tails of symbol chains. */ 183 int next_symbol[32]; 184 uint8_t code_length_code_lengths[BROTLI_CODE_LENGTH_CODES]; 185 /* Population counts for the code lengths. */ 186 uint16_t code_length_histo[16]; 187 188 /* For HuffmanTreeGroupDecode. */ 189 int htree_index; 190 HuffmanCode* next; 191 192 /* For DecodeContextMap. */ 193 uint32_t context_index; 194 uint32_t max_run_length_prefix; 195 uint32_t code; 196 HuffmanCode context_map_table[BROTLI_HUFFMAN_MAX_SIZE_272]; 197 198 /* For InverseMoveToFrontTransform. */ 199 uint32_t mtf_upper_bound; 200 uint32_t mtf[64 + 1]; 201 202 /* Less used attributes are at the end of this struct. */ 203 204 /* States inside function calls. */ 205 BrotliRunningMetablockHeaderState substate_metablock_header; 206 BrotliRunningTreeGroupState substate_tree_group; 207 BrotliRunningContextMapState substate_context_map; 208 BrotliRunningUncompressedState substate_uncompressed; 209 BrotliRunningHuffmanState substate_huffman; 210 BrotliRunningDecodeUint8State substate_decode_uint8; 211 BrotliRunningReadBlockLengthState substate_read_block_length; 212 213 unsigned int is_last_metablock : 1; 214 unsigned int is_uncompressed : 1; 215 unsigned int is_metadata : 1; 216 unsigned int should_wrap_ringbuffer : 1; 217 unsigned int canny_ringbuffer_allocation : 1; 218 unsigned int large_window : 1; 219 unsigned int size_nibbles : 8; 220 uint32_t window_bits; 221 222 int new_ringbuffer_size; 223 224 uint32_t num_literal_htrees; 225 uint8_t* context_map; 226 uint8_t* context_modes; 227 228 const BrotliDictionary* dictionary; 229 const BrotliTransforms* transforms; 230 231 uint32_t trivial_literal_contexts[8]; /* 256 bits */ 232 }; 233 234 typedef struct BrotliDecoderStateStruct BrotliDecoderStateInternal; 235 #define BrotliDecoderState BrotliDecoderStateInternal 236 237 BROTLI_INTERNAL BROTLI_BOOL BrotliDecoderStateInit(BrotliDecoderState* s, 238 brotli_alloc_func alloc_func, brotli_free_func free_func, void* opaque); 239 BROTLI_INTERNAL void BrotliDecoderStateCleanup(BrotliDecoderState* s); 240 BROTLI_INTERNAL void BrotliDecoderStateMetablockBegin(BrotliDecoderState* s); 241 BROTLI_INTERNAL void BrotliDecoderStateCleanupAfterMetablock( 242 BrotliDecoderState* s); 243 BROTLI_INTERNAL BROTLI_BOOL BrotliDecoderHuffmanTreeGroupInit( 244 BrotliDecoderState* s, HuffmanTreeGroup* group, uint32_t alphabet_size, 245 uint32_t max_symbol, uint32_t ntrees); 246 247 #define BROTLI_DECODER_ALLOC(S, L) S->alloc_func(S->memory_manager_opaque, L) 248 249 #define BROTLI_DECODER_FREE(S, X) { \ 250 S->free_func(S->memory_manager_opaque, X); \ 251 X = NULL; \ 252 } 253 254 #if defined(__cplusplus) || defined(c_plusplus) 255 } /* extern "C" */ 256 #endif 257 258 #endif /* BROTLI_DEC_STATE_H_ */ 259