state.h (12452B)
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/platform.h" 14 #include <brotli/shared_dictionary.h> 15 #include <brotli/decode.h> 16 #include "bit_reader.h" 17 #include "huffman.h" 18 19 #if defined(__cplusplus) || defined(c_plusplus) 20 extern "C" { 21 #endif 22 23 /* Graphviz diagram that describes state transitions: 24 25 digraph States { 26 graph [compound=true] 27 concentrate=true 28 node [shape="box"] 29 30 UNINITED -> {LARGE_WINDOW_BITS -> INITIALIZE} 31 subgraph cluster_metablock_workflow { 32 style="rounded" 33 label=< <B>METABLOCK CYCLE</B> > 34 METABLOCK_BEGIN -> METABLOCK_HEADER 35 METABLOCK_HEADER:sw -> METADATA 36 METABLOCK_HEADER:s -> UNCOMPRESSED 37 METABLOCK_HEADER:se -> METABLOCK_DONE:ne 38 METADATA:s -> METABLOCK_DONE:w 39 UNCOMPRESSED:s -> METABLOCK_DONE:n 40 METABLOCK_DONE:e -> METABLOCK_BEGIN:e [constraint="false"] 41 } 42 INITIALIZE -> METABLOCK_BEGIN 43 METABLOCK_DONE -> DONE 44 45 subgraph cluster_compressed_metablock { 46 style="rounded" 47 label=< <B>COMPRESSED METABLOCK</B> > 48 49 subgraph cluster_command { 50 style="rounded" 51 label=< <B>HOT LOOP</B> > 52 53 _METABLOCK_DONE_PORT_ [shape=point style=invis] 54 55 { 56 // Set different shape for nodes returning from "compressed metablock". 57 node [shape=invhouse]; CMD_INNER CMD_POST_DECODE_LITERALS; 58 CMD_POST_WRAP_COPY; CMD_INNER_WRITE; CMD_POST_WRITE_1; 59 } 60 61 CMD_BEGIN -> CMD_INNER -> CMD_POST_DECODE_LITERALS -> CMD_POST_WRAP_COPY 62 63 // IO ("write") nodes are not in the hot loop! 64 CMD_INNER_WRITE [style=dashed] 65 CMD_INNER -> CMD_INNER_WRITE 66 CMD_POST_WRITE_1 [style=dashed] 67 CMD_POST_DECODE_LITERALS -> CMD_POST_WRITE_1 68 CMD_POST_WRITE_2 [style=dashed] 69 CMD_POST_WRAP_COPY -> CMD_POST_WRITE_2 70 71 CMD_POST_WRITE_1 -> CMD_BEGIN:s [constraint="false"] 72 CMD_INNER_WRITE -> {CMD_INNER CMD_POST_DECODE_LITERALS} 73 [constraint="false"] 74 CMD_BEGIN:ne -> CMD_POST_DECODE_LITERALS [constraint="false"] 75 CMD_POST_WRAP_COPY -> CMD_BEGIN [constraint="false"] 76 CMD_POST_DECODE_LITERALS -> CMD_BEGIN:ne [constraint="false"] 77 CMD_POST_WRITE_2 -> CMD_POST_WRAP_COPY [constraint="false"] 78 {rank=same; CMD_BEGIN; CMD_INNER; CMD_POST_DECODE_LITERALS; 79 CMD_POST_WRAP_COPY} 80 {rank=same; CMD_INNER_WRITE; CMD_POST_WRITE_1; CMD_POST_WRITE_2} 81 82 {CMD_INNER CMD_POST_DECODE_LITERALS CMD_POST_WRAP_COPY} -> 83 _METABLOCK_DONE_PORT_ [style=invis] 84 {CMD_INNER_WRITE CMD_POST_WRITE_1} -> _METABLOCK_DONE_PORT_ 85 [constraint="false" style=invis] 86 } 87 88 BEFORE_COMPRESSED_METABLOCK_HEADER:s -> HUFFMAN_CODE_0:n 89 HUFFMAN_CODE_0 -> HUFFMAN_CODE_1 -> HUFFMAN_CODE_2 -> HUFFMAN_CODE_3 90 HUFFMAN_CODE_0 -> METABLOCK_HEADER_2 -> CONTEXT_MODES -> CONTEXT_MAP_1 91 CONTEXT_MAP_1 -> CONTEXT_MAP_2 -> TREE_GROUP 92 TREE_GROUP -> BEFORE_COMPRESSED_METABLOCK_BODY:e 93 BEFORE_COMPRESSED_METABLOCK_BODY:s -> CMD_BEGIN:n 94 95 HUFFMAN_CODE_3:e -> HUFFMAN_CODE_0:ne [constraint="false"] 96 {rank=same; HUFFMAN_CODE_0; HUFFMAN_CODE_1; HUFFMAN_CODE_2; HUFFMAN_CODE_3} 97 {rank=same; METABLOCK_HEADER_2; CONTEXT_MODES; CONTEXT_MAP_1; CONTEXT_MAP_2; 98 TREE_GROUP} 99 } 100 METABLOCK_HEADER:e -> BEFORE_COMPRESSED_METABLOCK_HEADER:n 101 102 _METABLOCK_DONE_PORT_ -> METABLOCK_DONE:se 103 [constraint="false" ltail=cluster_command] 104 105 UNINITED [shape=Mdiamond]; 106 DONE [shape=Msquare]; 107 } 108 109 110 */ 111 112 typedef enum { 113 BROTLI_STATE_UNINITED, 114 BROTLI_STATE_LARGE_WINDOW_BITS, 115 BROTLI_STATE_INITIALIZE, 116 BROTLI_STATE_METABLOCK_BEGIN, 117 BROTLI_STATE_METABLOCK_HEADER, 118 BROTLI_STATE_METABLOCK_HEADER_2, 119 BROTLI_STATE_CONTEXT_MODES, 120 BROTLI_STATE_COMMAND_BEGIN, 121 BROTLI_STATE_COMMAND_INNER, 122 BROTLI_STATE_COMMAND_POST_DECODE_LITERALS, 123 BROTLI_STATE_COMMAND_POST_WRAP_COPY, 124 BROTLI_STATE_UNCOMPRESSED, 125 BROTLI_STATE_METADATA, 126 BROTLI_STATE_COMMAND_INNER_WRITE, 127 BROTLI_STATE_METABLOCK_DONE, 128 BROTLI_STATE_COMMAND_POST_WRITE_1, 129 BROTLI_STATE_COMMAND_POST_WRITE_2, 130 BROTLI_STATE_BEFORE_COMPRESSED_METABLOCK_HEADER, 131 BROTLI_STATE_HUFFMAN_CODE_0, 132 BROTLI_STATE_HUFFMAN_CODE_1, 133 BROTLI_STATE_HUFFMAN_CODE_2, 134 BROTLI_STATE_HUFFMAN_CODE_3, 135 BROTLI_STATE_CONTEXT_MAP_1, 136 BROTLI_STATE_CONTEXT_MAP_2, 137 BROTLI_STATE_TREE_GROUP, 138 BROTLI_STATE_BEFORE_COMPRESSED_METABLOCK_BODY, 139 BROTLI_STATE_DONE 140 } BrotliRunningState; 141 142 typedef enum { 143 BROTLI_STATE_METABLOCK_HEADER_NONE, 144 BROTLI_STATE_METABLOCK_HEADER_EMPTY, 145 BROTLI_STATE_METABLOCK_HEADER_NIBBLES, 146 BROTLI_STATE_METABLOCK_HEADER_SIZE, 147 BROTLI_STATE_METABLOCK_HEADER_UNCOMPRESSED, 148 BROTLI_STATE_METABLOCK_HEADER_RESERVED, 149 BROTLI_STATE_METABLOCK_HEADER_BYTES, 150 BROTLI_STATE_METABLOCK_HEADER_METADATA 151 } BrotliRunningMetablockHeaderState; 152 153 typedef enum { 154 BROTLI_STATE_UNCOMPRESSED_NONE, 155 BROTLI_STATE_UNCOMPRESSED_WRITE 156 } BrotliRunningUncompressedState; 157 158 typedef enum { 159 BROTLI_STATE_TREE_GROUP_NONE, 160 BROTLI_STATE_TREE_GROUP_LOOP 161 } BrotliRunningTreeGroupState; 162 163 typedef enum { 164 BROTLI_STATE_CONTEXT_MAP_NONE, 165 BROTLI_STATE_CONTEXT_MAP_READ_PREFIX, 166 BROTLI_STATE_CONTEXT_MAP_HUFFMAN, 167 BROTLI_STATE_CONTEXT_MAP_DECODE, 168 BROTLI_STATE_CONTEXT_MAP_TRANSFORM 169 } BrotliRunningContextMapState; 170 171 typedef enum { 172 BROTLI_STATE_HUFFMAN_NONE, 173 BROTLI_STATE_HUFFMAN_SIMPLE_SIZE, 174 BROTLI_STATE_HUFFMAN_SIMPLE_READ, 175 BROTLI_STATE_HUFFMAN_SIMPLE_BUILD, 176 BROTLI_STATE_HUFFMAN_COMPLEX, 177 BROTLI_STATE_HUFFMAN_LENGTH_SYMBOLS 178 } BrotliRunningHuffmanState; 179 180 typedef enum { 181 BROTLI_STATE_DECODE_UINT8_NONE, 182 BROTLI_STATE_DECODE_UINT8_SHORT, 183 BROTLI_STATE_DECODE_UINT8_LONG 184 } BrotliRunningDecodeUint8State; 185 186 typedef enum { 187 BROTLI_STATE_READ_BLOCK_LENGTH_NONE, 188 BROTLI_STATE_READ_BLOCK_LENGTH_SUFFIX 189 } BrotliRunningReadBlockLengthState; 190 191 /* BrotliDecoderState addon, used for Compound Dictionary functionality. */ 192 typedef struct BrotliDecoderCompoundDictionary { 193 int num_chunks; 194 int total_size; 195 int br_index; 196 int br_offset; 197 int br_length; 198 int br_copied; 199 const uint8_t* chunks[16]; 200 int chunk_offsets[16]; 201 int block_bits; 202 uint8_t block_map[256]; 203 } BrotliDecoderCompoundDictionary; 204 205 typedef struct BrotliMetablockHeaderArena { 206 BrotliRunningTreeGroupState substate_tree_group; 207 BrotliRunningContextMapState substate_context_map; 208 BrotliRunningHuffmanState substate_huffman; 209 210 brotli_reg_t sub_loop_counter; 211 212 brotli_reg_t repeat_code_len; 213 brotli_reg_t prev_code_len; 214 215 /* For ReadHuffmanCode. */ 216 brotli_reg_t symbol; 217 brotli_reg_t repeat; 218 brotli_reg_t space; 219 220 /* Huffman table for "histograms". */ 221 HuffmanCode table[32]; 222 /* List of heads of symbol chains. */ 223 uint16_t* symbol_lists; 224 /* Storage from symbol_lists. */ 225 uint16_t symbols_lists_array[BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1 + 226 BROTLI_NUM_COMMAND_SYMBOLS]; 227 /* Tails of symbol chains. */ 228 int next_symbol[32]; 229 uint8_t code_length_code_lengths[BROTLI_CODE_LENGTH_CODES]; 230 /* Population counts for the code lengths. */ 231 uint16_t code_length_histo[16]; 232 /* TODO(eustas): +2 bytes padding */ 233 234 /* For HuffmanTreeGroupDecode. */ 235 int htree_index; 236 HuffmanCode* next; 237 238 /* For DecodeContextMap. */ 239 brotli_reg_t context_index; 240 brotli_reg_t max_run_length_prefix; 241 brotli_reg_t code; 242 HuffmanCode context_map_table[BROTLI_HUFFMAN_MAX_SIZE_272]; 243 } BrotliMetablockHeaderArena; 244 245 typedef struct BrotliMetablockBodyArena { 246 uint8_t dist_extra_bits[544]; 247 brotli_reg_t dist_offset[544]; 248 } BrotliMetablockBodyArena; 249 250 struct BrotliDecoderStateStruct { 251 BrotliRunningState state; 252 253 /* This counter is reused for several disjoint loops. */ 254 int loop_counter; 255 256 BrotliBitReader br; 257 258 brotli_alloc_func alloc_func; 259 brotli_free_func free_func; 260 void* memory_manager_opaque; 261 262 /* Temporary storage for remaining input. Brotli stream format is designed in 263 a way, that 64 bits are enough to make progress in decoding. */ 264 union { 265 uint64_t u64; 266 uint8_t u8[8]; 267 } buffer; 268 brotli_reg_t buffer_length; 269 270 int pos; 271 int max_backward_distance; 272 int max_distance; 273 int ringbuffer_size; 274 int ringbuffer_mask; 275 int dist_rb_idx; 276 int dist_rb[4]; 277 int error_code; 278 int meta_block_remaining_len; 279 280 uint8_t* ringbuffer; 281 uint8_t* ringbuffer_end; 282 HuffmanCode* htree_command; 283 const uint8_t* context_lookup; 284 uint8_t* context_map_slice; 285 uint8_t* dist_context_map_slice; 286 287 /* This ring buffer holds a few past copy distances that will be used by 288 some special distance codes. */ 289 HuffmanTreeGroup literal_hgroup; 290 HuffmanTreeGroup insert_copy_hgroup; 291 HuffmanTreeGroup distance_hgroup; 292 HuffmanCode* block_type_trees; 293 HuffmanCode* block_len_trees; 294 /* This is true if the literal context map histogram type always matches the 295 block type. It is then not needed to keep the context (faster decoding). */ 296 int trivial_literal_context; 297 /* Distance context is actual after command is decoded and before distance is 298 computed. After distance computation it is used as a temporary variable. */ 299 int distance_context; 300 brotli_reg_t block_length[3]; 301 brotli_reg_t block_length_index; 302 brotli_reg_t num_block_types[3]; 303 brotli_reg_t block_type_rb[6]; 304 brotli_reg_t distance_postfix_bits; 305 brotli_reg_t num_direct_distance_codes; 306 brotli_reg_t num_dist_htrees; 307 uint8_t* dist_context_map; 308 HuffmanCode* literal_htree; 309 310 /* For partial write operations. */ 311 size_t rb_roundtrips; /* how many times we went around the ring-buffer */ 312 size_t partial_pos_out; /* how much output to the user in total */ 313 314 /* For InverseMoveToFrontTransform. */ 315 brotli_reg_t mtf_upper_bound; 316 uint32_t mtf[64 + 1]; 317 318 int copy_length; 319 int distance_code; 320 321 uint8_t dist_htree_index; 322 /* TODO(eustas): +3 bytes padding */ 323 324 /* Less used attributes are at the end of this struct. */ 325 326 brotli_decoder_metadata_start_func metadata_start_func; 327 brotli_decoder_metadata_chunk_func metadata_chunk_func; 328 void* metadata_callback_opaque; 329 330 /* For reporting. */ 331 uint64_t used_input; /* how many bytes of input are consumed */ 332 333 /* States inside function calls. */ 334 BrotliRunningMetablockHeaderState substate_metablock_header; 335 BrotliRunningUncompressedState substate_uncompressed; 336 BrotliRunningDecodeUint8State substate_decode_uint8; 337 BrotliRunningReadBlockLengthState substate_read_block_length; 338 339 int new_ringbuffer_size; 340 /* TODO(eustas): +4 bytes padding */ 341 342 unsigned int is_last_metablock : 1; 343 unsigned int is_uncompressed : 1; 344 unsigned int is_metadata : 1; 345 unsigned int should_wrap_ringbuffer : 1; 346 unsigned int canny_ringbuffer_allocation : 1; 347 unsigned int large_window : 1; 348 unsigned int window_bits : 6; 349 unsigned int size_nibbles : 8; 350 /* TODO(eustas): +12 bits padding */ 351 352 brotli_reg_t num_literal_htrees; 353 uint8_t* context_map; 354 uint8_t* context_modes; 355 356 BrotliSharedDictionary* dictionary; 357 BrotliDecoderCompoundDictionary* compound_dictionary; 358 359 uint32_t trivial_literal_contexts[8]; /* 256 bits */ 360 361 union { 362 BrotliMetablockHeaderArena header; 363 BrotliMetablockBodyArena body; 364 } arena; 365 }; 366 367 typedef struct BrotliDecoderStateStruct BrotliDecoderStateInternal; 368 #define BrotliDecoderState BrotliDecoderStateInternal 369 370 BROTLI_INTERNAL BROTLI_BOOL BrotliDecoderStateInit(BrotliDecoderState* s, 371 brotli_alloc_func alloc_func, brotli_free_func free_func, void* opaque); 372 BROTLI_INTERNAL void BrotliDecoderStateCleanup(BrotliDecoderState* s); 373 BROTLI_INTERNAL void BrotliDecoderStateMetablockBegin(BrotliDecoderState* s); 374 BROTLI_INTERNAL void BrotliDecoderStateCleanupAfterMetablock( 375 BrotliDecoderState* s); 376 BROTLI_INTERNAL BROTLI_BOOL BrotliDecoderHuffmanTreeGroupInit( 377 BrotliDecoderState* s, HuffmanTreeGroup* group, 378 brotli_reg_t alphabet_size_max, brotli_reg_t alphabet_size_limit, 379 brotli_reg_t ntrees); 380 381 #define BROTLI_DECODER_ALLOC(S, L) S->alloc_func(S->memory_manager_opaque, L) 382 383 #define BROTLI_DECODER_FREE(S, X) { \ 384 S->free_func(S->memory_manager_opaque, X); \ 385 X = NULL; \ 386 } 387 388 /* Literal/Command/Distance block size maximum; same as maximum metablock size; 389 used as block size when there is no block switching. */ 390 #define BROTLI_BLOCK_SIZE_CAP (1U << 24) 391 392 #if defined(__cplusplus) || defined(c_plusplus) 393 } /* extern "C" */ 394 #endif 395 396 #endif /* BROTLI_DEC_STATE_H_ */