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)
21extern "C" {
22#endif
23
24typedef enum {
25 BROTLI_STATE_UNINITED,
26 BROTLI_STATE_LARGE_WINDOW_BITS,
27 BROTLI_STATE_INITIALIZE,
28 BROTLI_STATE_METABLOCK_BEGIN,
29 BROTLI_STATE_METABLOCK_HEADER,
30 BROTLI_STATE_METABLOCK_HEADER_2,
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
52typedef enum {
53 BROTLI_STATE_METABLOCK_HEADER_NONE,
54 BROTLI_STATE_METABLOCK_HEADER_EMPTY,
55 BROTLI_STATE_METABLOCK_HEADER_NIBBLES,
56 BROTLI_STATE_METABLOCK_HEADER_SIZE,
57 BROTLI_STATE_METABLOCK_HEADER_UNCOMPRESSED,
58 BROTLI_STATE_METABLOCK_HEADER_RESERVED,
59 BROTLI_STATE_METABLOCK_HEADER_BYTES,
60 BROTLI_STATE_METABLOCK_HEADER_METADATA
61} BrotliRunningMetablockHeaderState;
62
63typedef enum {
64 BROTLI_STATE_UNCOMPRESSED_NONE,
65 BROTLI_STATE_UNCOMPRESSED_WRITE
66} BrotliRunningUncompressedState;
67
68typedef enum {
69 BROTLI_STATE_TREE_GROUP_NONE,
70 BROTLI_STATE_TREE_GROUP_LOOP
71} BrotliRunningTreeGroupState;
72
73typedef 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
81typedef 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
90typedef enum {
91 BROTLI_STATE_DECODE_UINT8_NONE,
92 BROTLI_STATE_DECODE_UINT8_SHORT,
93 BROTLI_STATE_DECODE_UINT8_LONG
94} BrotliRunningDecodeUint8State;
95
96typedef enum {
97 BROTLI_STATE_READ_BLOCK_LENGTH_NONE,
98 BROTLI_STATE_READ_BLOCK_LENGTH_SUFFIX
99} BrotliRunningReadBlockLengthState;
100
101struct 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 substate_metablock_header;
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
234typedef struct BrotliDecoderStateStruct BrotliDecoderStateInternal;
235#define BrotliDecoderState BrotliDecoderStateInternal
236
237BROTLI_INTERNAL BROTLI_BOOL BrotliDecoderStateInit(BrotliDecoderState* s,
238 brotli_alloc_func alloc_func, brotli_free_func free_func, void* opaque);
239BROTLI_INTERNAL void BrotliDecoderStateCleanup(BrotliDecoderState* s);
240BROTLI_INTERNAL void BrotliDecoderStateMetablockBegin(BrotliDecoderState* s);
241BROTLI_INTERNAL void BrotliDecoderStateCleanupAfterMetablock(
242 BrotliDecoderState* s);
243BROTLI_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