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