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