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