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