/* Copyright 2015 Google Inc. All Rights Reserved. Distributed under MIT license. See file LICENSE for detail or copy at https://opensource.org/licenses/MIT */ /* Brotli state for partial streaming decoding. */ #ifndef BROTLI_DEC_STATE_H_ #define BROTLI_DEC_STATE_H_ #include "../common/constants.h" #include "../common/dictionary.h" #include "../common/platform.h" #include #include "../common/transform.h" #include #include "bit_reader.h" #include "huffman.h" #if defined(__cplusplus) || defined(c_plusplus) extern "C" { #endif /* Graphviz diagram that describes state transitions: digraph States { graph [compound=true] concentrate=true node [shape="box"] UNINITED -> {LARGE_WINDOW_BITS -> INITIALIZE} subgraph cluster_metablock_workflow { style="rounded" label=< METABLOCK CYCLE > METABLOCK_BEGIN -> METABLOCK_HEADER METABLOCK_HEADER:sw -> METADATA METABLOCK_HEADER:s -> UNCOMPRESSED METABLOCK_HEADER:se -> METABLOCK_DONE:ne METADATA:s -> METABLOCK_DONE:w UNCOMPRESSED:s -> METABLOCK_DONE:n METABLOCK_DONE:e -> METABLOCK_BEGIN:e [constraint="false"] } INITIALIZE -> METABLOCK_BEGIN METABLOCK_DONE -> DONE subgraph cluster_compressed_metablock { style="rounded" label=< COMPRESSED METABLOCK > subgraph cluster_command { style="rounded" label=< HOT LOOP > _METABLOCK_DONE_PORT_ [shape=point style=invis] { // Set different shape for nodes returning from "compressed metablock". node [shape=invhouse]; CMD_INNER CMD_POST_DECODE_LITERALS; CMD_POST_WRAP_COPY; CMD_INNER_WRITE; CMD_POST_WRITE_1; } CMD_BEGIN -> CMD_INNER -> CMD_POST_DECODE_LITERALS -> CMD_POST_WRAP_COPY // IO ("write") nodes are not in the hot loop! CMD_INNER_WRITE [style=dashed] CMD_INNER -> CMD_INNER_WRITE CMD_POST_WRITE_1 [style=dashed] CMD_POST_DECODE_LITERALS -> CMD_POST_WRITE_1 CMD_POST_WRITE_2 [style=dashed] CMD_POST_WRAP_COPY -> CMD_POST_WRITE_2 CMD_POST_WRITE_1 -> CMD_BEGIN:s [constraint="false"] CMD_INNER_WRITE -> {CMD_INNER CMD_POST_DECODE_LITERALS} [constraint="false"] CMD_BEGIN:ne -> CMD_POST_DECODE_LITERALS [constraint="false"] CMD_POST_WRAP_COPY -> CMD_BEGIN [constraint="false"] CMD_POST_DECODE_LITERALS -> CMD_BEGIN:ne [constraint="false"] CMD_POST_WRITE_2 -> CMD_POST_WRAP_COPY [constraint="false"] {rank=same; CMD_BEGIN; CMD_INNER; CMD_POST_DECODE_LITERALS; CMD_POST_WRAP_COPY} {rank=same; CMD_INNER_WRITE; CMD_POST_WRITE_1; CMD_POST_WRITE_2} {CMD_INNER CMD_POST_DECODE_LITERALS CMD_POST_WRAP_COPY} -> _METABLOCK_DONE_PORT_ [style=invis] {CMD_INNER_WRITE CMD_POST_WRITE_1} -> _METABLOCK_DONE_PORT_ [constraint="false" style=invis] } BEFORE_COMPRESSED_METABLOCK_HEADER:s -> HUFFMAN_CODE_0:n HUFFMAN_CODE_0 -> HUFFMAN_CODE_1 -> HUFFMAN_CODE_2 -> HUFFMAN_CODE_3 HUFFMAN_CODE_0 -> METABLOCK_HEADER_2 -> CONTEXT_MODES -> CONTEXT_MAP_1 CONTEXT_MAP_1 -> CONTEXT_MAP_2 -> TREE_GROUP TREE_GROUP -> BEFORE_COMPRESSED_METABLOCK_BODY:e BEFORE_COMPRESSED_METABLOCK_BODY:s -> CMD_BEGIN:n HUFFMAN_CODE_3:e -> HUFFMAN_CODE_0:ne [constraint="false"] {rank=same; HUFFMAN_CODE_0; HUFFMAN_CODE_1; HUFFMAN_CODE_2; HUFFMAN_CODE_3} {rank=same; METABLOCK_HEADER_2; CONTEXT_MODES; CONTEXT_MAP_1; CONTEXT_MAP_2; TREE_GROUP} } METABLOCK_HEADER:e -> BEFORE_COMPRESSED_METABLOCK_HEADER:n _METABLOCK_DONE_PORT_ -> METABLOCK_DONE:se [constraint="false" ltail=cluster_command] UNINITED [shape=Mdiamond]; DONE [shape=Msquare]; } */ typedef enum { BROTLI_STATE_UNINITED, BROTLI_STATE_LARGE_WINDOW_BITS, BROTLI_STATE_INITIALIZE, BROTLI_STATE_METABLOCK_BEGIN, BROTLI_STATE_METABLOCK_HEADER, BROTLI_STATE_METABLOCK_HEADER_2, BROTLI_STATE_CONTEXT_MODES, BROTLI_STATE_COMMAND_BEGIN, BROTLI_STATE_COMMAND_INNER, BROTLI_STATE_COMMAND_POST_DECODE_LITERALS, BROTLI_STATE_COMMAND_POST_WRAP_COPY, BROTLI_STATE_UNCOMPRESSED, BROTLI_STATE_METADATA, BROTLI_STATE_COMMAND_INNER_WRITE, BROTLI_STATE_METABLOCK_DONE, BROTLI_STATE_COMMAND_POST_WRITE_1, BROTLI_STATE_COMMAND_POST_WRITE_2, BROTLI_STATE_BEFORE_COMPRESSED_METABLOCK_HEADER, BROTLI_STATE_HUFFMAN_CODE_0, BROTLI_STATE_HUFFMAN_CODE_1, BROTLI_STATE_HUFFMAN_CODE_2, BROTLI_STATE_HUFFMAN_CODE_3, BROTLI_STATE_CONTEXT_MAP_1, BROTLI_STATE_CONTEXT_MAP_2, BROTLI_STATE_TREE_GROUP, BROTLI_STATE_BEFORE_COMPRESSED_METABLOCK_BODY, BROTLI_STATE_DONE } BrotliRunningState; typedef enum { BROTLI_STATE_METABLOCK_HEADER_NONE, BROTLI_STATE_METABLOCK_HEADER_EMPTY, BROTLI_STATE_METABLOCK_HEADER_NIBBLES, BROTLI_STATE_METABLOCK_HEADER_SIZE, BROTLI_STATE_METABLOCK_HEADER_UNCOMPRESSED, BROTLI_STATE_METABLOCK_HEADER_RESERVED, BROTLI_STATE_METABLOCK_HEADER_BYTES, BROTLI_STATE_METABLOCK_HEADER_METADATA } BrotliRunningMetablockHeaderState; typedef enum { BROTLI_STATE_UNCOMPRESSED_NONE, BROTLI_STATE_UNCOMPRESSED_WRITE } BrotliRunningUncompressedState; typedef enum { BROTLI_STATE_TREE_GROUP_NONE, BROTLI_STATE_TREE_GROUP_LOOP } BrotliRunningTreeGroupState; typedef enum { BROTLI_STATE_CONTEXT_MAP_NONE, BROTLI_STATE_CONTEXT_MAP_READ_PREFIX, BROTLI_STATE_CONTEXT_MAP_HUFFMAN, BROTLI_STATE_CONTEXT_MAP_DECODE, BROTLI_STATE_CONTEXT_MAP_TRANSFORM } BrotliRunningContextMapState; typedef enum { BROTLI_STATE_HUFFMAN_NONE, BROTLI_STATE_HUFFMAN_SIMPLE_SIZE, BROTLI_STATE_HUFFMAN_SIMPLE_READ, BROTLI_STATE_HUFFMAN_SIMPLE_BUILD, BROTLI_STATE_HUFFMAN_COMPLEX, BROTLI_STATE_HUFFMAN_LENGTH_SYMBOLS } BrotliRunningHuffmanState; typedef enum { BROTLI_STATE_DECODE_UINT8_NONE, BROTLI_STATE_DECODE_UINT8_SHORT, BROTLI_STATE_DECODE_UINT8_LONG } BrotliRunningDecodeUint8State; typedef enum { BROTLI_STATE_READ_BLOCK_LENGTH_NONE, BROTLI_STATE_READ_BLOCK_LENGTH_SUFFIX } BrotliRunningReadBlockLengthState; /* BrotliDecoderState addon, used for Compound Dictionary functionality. */ typedef struct BrotliDecoderCompoundDictionary { int num_chunks; int total_size; int br_index; int br_offset; int br_length; int br_copied; const uint8_t* chunks[16]; int chunk_offsets[16]; int block_bits; uint8_t block_map[256]; } BrotliDecoderCompoundDictionary; typedef struct BrotliMetablockHeaderArena { BrotliRunningTreeGroupState substate_tree_group; BrotliRunningContextMapState substate_context_map; BrotliRunningHuffmanState substate_huffman; uint32_t sub_loop_counter; uint32_t repeat_code_len; uint32_t prev_code_len; /* For ReadHuffmanCode. */ uint32_t symbol; uint32_t repeat; uint32_t space; /* Huffman table for "histograms". */ HuffmanCode table[32]; /* List of heads of symbol chains. */ uint16_t* symbol_lists; /* Storage from symbol_lists. */ uint16_t symbols_lists_array[BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1 + BROTLI_NUM_COMMAND_SYMBOLS]; /* Tails of symbol chains. */ int next_symbol[32]; uint8_t code_length_code_lengths[BROTLI_CODE_LENGTH_CODES]; /* Population counts for the code lengths. */ uint16_t code_length_histo[16]; /* For HuffmanTreeGroupDecode. */ int htree_index; HuffmanCode* next; /* For DecodeContextMap. */ uint32_t context_index; uint32_t max_run_length_prefix; uint32_t code; HuffmanCode context_map_table[BROTLI_HUFFMAN_MAX_SIZE_272]; } BrotliMetablockHeaderArena; typedef struct BrotliMetablockBodyArena { uint8_t dist_extra_bits[544]; uint32_t dist_offset[544]; } BrotliMetablockBodyArena; struct BrotliDecoderStateStruct { BrotliRunningState state; /* This counter is reused for several disjoint loops. */ int loop_counter; BrotliBitReader br; brotli_alloc_func alloc_func; brotli_free_func free_func; void* memory_manager_opaque; /* Temporary storage for remaining input. Brotli stream format is designed in a way, that 64 bits are enough to make progress in decoding. */ union { uint64_t u64; uint8_t u8[8]; } buffer; uint32_t buffer_length; int pos; int max_backward_distance; int max_distance; int ringbuffer_size; int ringbuffer_mask; int dist_rb_idx; int dist_rb[4]; int error_code; uint8_t* ringbuffer; uint8_t* ringbuffer_end; HuffmanCode* htree_command; const uint8_t* context_lookup; uint8_t* context_map_slice; uint8_t* dist_context_map_slice; /* This ring buffer holds a few past copy distances that will be used by some special distance codes. */ HuffmanTreeGroup literal_hgroup; HuffmanTreeGroup insert_copy_hgroup; HuffmanTreeGroup distance_hgroup; HuffmanCode* block_type_trees; HuffmanCode* block_len_trees; /* This is true if the literal context map histogram type always matches the block type. It is then not needed to keep the context (faster decoding). */ int trivial_literal_context; /* Distance context is actual after command is decoded and before distance is computed. After distance computation it is used as a temporary variable. */ int distance_context; int meta_block_remaining_len; uint32_t block_length_index; uint32_t block_length[3]; uint32_t num_block_types[3]; uint32_t block_type_rb[6]; uint32_t distance_postfix_bits; uint32_t num_direct_distance_codes; uint32_t num_dist_htrees; uint8_t* dist_context_map; HuffmanCode* literal_htree; uint8_t dist_htree_index; int copy_length; int distance_code; /* For partial write operations. */ size_t rb_roundtrips; /* how many times we went around the ring-buffer */ size_t partial_pos_out; /* how much output to the user in total */ /* For InverseMoveToFrontTransform. */ uint32_t mtf_upper_bound; uint32_t mtf[64 + 1]; /* Less used attributes are at the end of this struct. */ /* States inside function calls. */ BrotliRunningMetablockHeaderState substate_metablock_header; BrotliRunningUncompressedState substate_uncompressed; BrotliRunningDecodeUint8State substate_decode_uint8; BrotliRunningReadBlockLengthState substate_read_block_length; unsigned int is_last_metablock : 1; unsigned int is_uncompressed : 1; unsigned int is_metadata : 1; unsigned int should_wrap_ringbuffer : 1; unsigned int canny_ringbuffer_allocation : 1; unsigned int large_window : 1; unsigned int size_nibbles : 8; uint32_t window_bits; int new_ringbuffer_size; uint32_t num_literal_htrees; uint8_t* context_map; uint8_t* context_modes; BrotliSharedDictionary* dictionary; BrotliDecoderCompoundDictionary* compound_dictionary; uint32_t trivial_literal_contexts[8]; /* 256 bits */ union { BrotliMetablockHeaderArena header; BrotliMetablockBodyArena body; } arena; }; typedef struct BrotliDecoderStateStruct BrotliDecoderStateInternal; #define BrotliDecoderState BrotliDecoderStateInternal BROTLI_INTERNAL BROTLI_BOOL BrotliDecoderStateInit(BrotliDecoderState* s, brotli_alloc_func alloc_func, brotli_free_func free_func, void* opaque); BROTLI_INTERNAL void BrotliDecoderStateCleanup(BrotliDecoderState* s); BROTLI_INTERNAL void BrotliDecoderStateMetablockBegin(BrotliDecoderState* s); BROTLI_INTERNAL void BrotliDecoderStateCleanupAfterMetablock( BrotliDecoderState* s); BROTLI_INTERNAL BROTLI_BOOL BrotliDecoderHuffmanTreeGroupInit( BrotliDecoderState* s, HuffmanTreeGroup* group, uint32_t alphabet_size_max, uint32_t alphabet_size_limit, uint32_t ntrees); #define BROTLI_DECODER_ALLOC(S, L) S->alloc_func(S->memory_manager_opaque, L) #define BROTLI_DECODER_FREE(S, X) { \ S->free_func(S->memory_manager_opaque, X); \ X = NULL; \ } #if defined(__cplusplus) || defined(c_plusplus) } /* extern "C" */ #endif #endif /* BROTLI_DEC_STATE_H_ */