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