1 /* Copyright 2015 Google Inc. All Rights Reserved.
3 Distributed under MIT license.
4 See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
7 /* Brotli state for partial streaming decoding. */
9 #ifndef BROTLI_DEC_STATE_H_
10 #define BROTLI_DEC_STATE_H_
12 #include "../common/constants.h"
13 #include "../common/types.h"
14 #include "./bit_reader.h"
15 #include "./huffman.h"
18 #if defined(__cplusplus) || defined(c_plusplus)
23 BROTLI_STATE_UNINITED
,
24 BROTLI_STATE_METABLOCK_BEGIN
,
25 BROTLI_STATE_METABLOCK_HEADER
,
26 BROTLI_STATE_METABLOCK_HEADER_2
,
27 BROTLI_STATE_CONTEXT_MODES
,
28 BROTLI_STATE_COMMAND_BEGIN
,
29 BROTLI_STATE_COMMAND_INNER
,
30 BROTLI_STATE_COMMAND_POST_DECODE_LITERALS
,
31 BROTLI_STATE_COMMAND_POST_WRAP_COPY
,
32 BROTLI_STATE_UNCOMPRESSED
,
33 BROTLI_STATE_METADATA
,
34 BROTLI_STATE_COMMAND_INNER_WRITE
,
35 BROTLI_STATE_METABLOCK_DONE
,
36 BROTLI_STATE_COMMAND_POST_WRITE_1
,
37 BROTLI_STATE_COMMAND_POST_WRITE_2
,
38 BROTLI_STATE_HUFFMAN_CODE_0
,
39 BROTLI_STATE_HUFFMAN_CODE_1
,
40 BROTLI_STATE_HUFFMAN_CODE_2
,
41 BROTLI_STATE_HUFFMAN_CODE_3
,
42 BROTLI_STATE_CONTEXT_MAP_1
,
43 BROTLI_STATE_CONTEXT_MAP_2
,
44 BROTLI_STATE_TREE_GROUP
,
49 BROTLI_STATE_METABLOCK_HEADER_NONE
,
50 BROTLI_STATE_METABLOCK_HEADER_EMPTY
,
51 BROTLI_STATE_METABLOCK_HEADER_NIBBLES
,
52 BROTLI_STATE_METABLOCK_HEADER_SIZE
,
53 BROTLI_STATE_METABLOCK_HEADER_UNCOMPRESSED
,
54 BROTLI_STATE_METABLOCK_HEADER_RESERVED
,
55 BROTLI_STATE_METABLOCK_HEADER_BYTES
,
56 BROTLI_STATE_METABLOCK_HEADER_METADATA
57 } BrotliRunningMetablockHeaderState
;
60 BROTLI_STATE_UNCOMPRESSED_NONE
,
61 BROTLI_STATE_UNCOMPRESSED_WRITE
62 } BrotliRunningUncompressedState
;
65 BROTLI_STATE_TREE_GROUP_NONE
,
66 BROTLI_STATE_TREE_GROUP_LOOP
67 } BrotliRunningTreeGroupState
;
70 BROTLI_STATE_CONTEXT_MAP_NONE
,
71 BROTLI_STATE_CONTEXT_MAP_READ_PREFIX
,
72 BROTLI_STATE_CONTEXT_MAP_HUFFMAN
,
73 BROTLI_STATE_CONTEXT_MAP_DECODE
,
74 BROTLI_STATE_CONTEXT_MAP_TRANSFORM
75 } BrotliRunningContextMapState
;
78 BROTLI_STATE_HUFFMAN_NONE
,
79 BROTLI_STATE_HUFFMAN_SIMPLE_SIZE
,
80 BROTLI_STATE_HUFFMAN_SIMPLE_READ
,
81 BROTLI_STATE_HUFFMAN_SIMPLE_BUILD
,
82 BROTLI_STATE_HUFFMAN_COMPLEX
,
83 BROTLI_STATE_HUFFMAN_LENGTH_SYMBOLS
84 } BrotliRunningHuffmanState
;
87 BROTLI_STATE_DECODE_UINT8_NONE
,
88 BROTLI_STATE_DECODE_UINT8_SHORT
,
89 BROTLI_STATE_DECODE_UINT8_LONG
90 } BrotliRunningDecodeUint8State
;
93 BROTLI_STATE_READ_BLOCK_LENGTH_NONE
,
94 BROTLI_STATE_READ_BLOCK_LENGTH_SUFFIX
95 } BrotliRunningReadBlockLengthState
;
97 struct BrotliDecoderStateStruct
{
98 BrotliRunningState state
;
100 /* This counter is reused for several disjoint loops. */
105 brotli_alloc_func alloc_func
;
106 brotli_free_func free_func
;
107 void* memory_manager_opaque
;
109 /* Temporary storage for remaining input. */
114 uint32_t buffer_length
;
117 int max_backward_distance
;
118 int max_backward_distance_minus_custom_dict_size
;
125 uint32_t sub_loop_counter
;
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
;
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 int distance_context
;
145 int meta_block_remaining_len
;
146 uint32_t block_length_index
;
147 uint32_t block_length
[3];
148 uint32_t num_block_types
[3];
149 uint32_t block_type_rb
[6];
150 uint32_t distance_postfix_bits
;
151 uint32_t num_direct_distance_codes
;
152 int distance_postfix_mask
;
153 uint32_t num_dist_htrees
;
154 uint8_t* dist_context_map
;
155 HuffmanCode
* literal_htree
;
156 uint8_t dist_htree_index
;
157 uint32_t repeat_code_len
;
158 uint32_t prev_code_len
;
163 /* For partial write operations */
164 size_t rb_roundtrips
; /* How many times we went around the ringbuffer */
165 size_t partial_pos_out
; /* How much output to the user in total (<= rb) */
167 /* For ReadHuffmanCode */
172 HuffmanCode table
[32];
173 /* List of of symbol chains. */
174 uint16_t* symbol_lists
;
175 /* Storage from symbol_lists. */
176 uint16_t symbols_lists_array
[BROTLI_HUFFMAN_MAX_CODE_LENGTH
+ 1 +
177 BROTLI_NUM_COMMAND_SYMBOLS
];
178 /* Tails of symbol chains. */
180 uint8_t code_length_code_lengths
[BROTLI_CODE_LENGTH_CODES
];
181 /* Population counts for the code lengths */
182 uint16_t code_length_histo
[16];
184 /* For HuffmanTreeGroupDecode */
188 /* For DecodeContextMap */
189 uint32_t context_index
;
190 uint32_t max_run_length_prefix
;
192 HuffmanCode context_map_table
[BROTLI_HUFFMAN_MAX_SIZE_272
];
194 /* For InverseMoveToFrontTransform */
195 uint32_t mtf_upper_bound
;
196 uint8_t mtf
[256 + 4];
198 /* For custom dictionaries */
199 const uint8_t* custom_dict
;
200 int custom_dict_size
;
202 /* less used attributes are in the end of this struct */
203 /* States inside function calls */
204 BrotliRunningMetablockHeaderState substate_metablock_header
;
205 BrotliRunningTreeGroupState substate_tree_group
;
206 BrotliRunningContextMapState substate_context_map
;
207 BrotliRunningUncompressedState substate_uncompressed
;
208 BrotliRunningHuffmanState substate_huffman
;
209 BrotliRunningDecodeUint8State substate_decode_uint8
;
210 BrotliRunningReadBlockLengthState substate_read_block_length
;
212 uint8_t is_last_metablock
;
213 uint8_t is_uncompressed
;
215 uint8_t size_nibbles
;
216 uint32_t window_bits
;
218 uint32_t num_literal_htrees
;
219 uint8_t* context_map
;
220 uint8_t* context_modes
;
222 uint32_t trivial_literal_contexts
[8]; /* 256 bits */
225 typedef struct BrotliDecoderStateStruct BrotliDecoderStateInternal
;
226 #define BrotliDecoderState BrotliDecoderStateInternal
228 BROTLI_INTERNAL
void BrotliDecoderStateInit(BrotliDecoderState
* s
);
229 BROTLI_INTERNAL
void BrotliDecoderStateInitWithCustomAllocators(
230 BrotliDecoderState
* s
, brotli_alloc_func alloc_func
,
231 brotli_free_func free_func
, void* opaque
);
232 BROTLI_INTERNAL
void BrotliDecoderStateCleanup(BrotliDecoderState
* s
);
233 BROTLI_INTERNAL
void BrotliDecoderStateMetablockBegin(BrotliDecoderState
* s
);
234 BROTLI_INTERNAL
void BrotliDecoderStateCleanupAfterMetablock(
235 BrotliDecoderState
* s
);
236 BROTLI_INTERNAL
void BrotliDecoderHuffmanTreeGroupInit(
237 BrotliDecoderState
* s
, HuffmanTreeGroup
* group
, uint32_t alphabet_size
,
239 BROTLI_INTERNAL
void BrotliDecoderHuffmanTreeGroupRelease(
240 BrotliDecoderState
* s
, HuffmanTreeGroup
* group
);
242 #if defined(__cplusplus) || defined(c_plusplus)
246 #endif /* BROTLI_DEC_STATE_H_ */