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