• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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   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 
52 typedef 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 
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 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 
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