Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/brotli/c/dec/state.h @ 2:b50eed0cc0ef upstream

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ADD: MuPDF v1.26.7: the MuPDF source as downloaded by a default build of PyMuPDF 1.26.4. The directory name has changed: no version number in the expanded directory now.
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 15 Sep 2025 11:43:07 +0200
parents
children
comparison
equal deleted inserted replaced
1:1d09e1dec1d9 2:b50eed0cc0ef
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 <brotli/decode.h>
13 #include <brotli/shared_dictionary.h>
14 #include <brotli/types.h>
15
16 #include "../common/constants.h"
17 #include "../common/dictionary.h"
18 #include "../common/platform.h"
19 #include "../common/transform.h"
20 #include "bit_reader.h"
21 #include "huffman.h"
22
23 #if defined(__cplusplus) || defined(c_plusplus)
24 extern "C" {
25 #endif
26
27 /* Graphviz diagram that describes state transitions:
28
29 digraph States {
30 graph [compound=true]
31 concentrate=true
32 node [shape="box"]
33
34 UNINITED -> {LARGE_WINDOW_BITS -> INITIALIZE}
35 subgraph cluster_metablock_workflow {
36 style="rounded"
37 label=< <B>METABLOCK CYCLE</B> >
38 METABLOCK_BEGIN -> METABLOCK_HEADER
39 METABLOCK_HEADER:sw -> METADATA
40 METABLOCK_HEADER:s -> UNCOMPRESSED
41 METABLOCK_HEADER:se -> METABLOCK_DONE:ne
42 METADATA:s -> METABLOCK_DONE:w
43 UNCOMPRESSED:s -> METABLOCK_DONE:n
44 METABLOCK_DONE:e -> METABLOCK_BEGIN:e [constraint="false"]
45 }
46 INITIALIZE -> METABLOCK_BEGIN
47 METABLOCK_DONE -> DONE
48
49 subgraph cluster_compressed_metablock {
50 style="rounded"
51 label=< <B>COMPRESSED METABLOCK</B> >
52
53 subgraph cluster_command {
54 style="rounded"
55 label=< <B>HOT LOOP</B> >
56
57 _METABLOCK_DONE_PORT_ [shape=point style=invis]
58
59 {
60 // Set different shape for nodes returning from "compressed metablock".
61 node [shape=invhouse]; CMD_INNER CMD_POST_DECODE_LITERALS;
62 CMD_POST_WRAP_COPY; CMD_INNER_WRITE; CMD_POST_WRITE_1;
63 }
64
65 CMD_BEGIN -> CMD_INNER -> CMD_POST_DECODE_LITERALS -> CMD_POST_WRAP_COPY
66
67 // IO ("write") nodes are not in the hot loop!
68 CMD_INNER_WRITE [style=dashed]
69 CMD_INNER -> CMD_INNER_WRITE
70 CMD_POST_WRITE_1 [style=dashed]
71 CMD_POST_DECODE_LITERALS -> CMD_POST_WRITE_1
72 CMD_POST_WRITE_2 [style=dashed]
73 CMD_POST_WRAP_COPY -> CMD_POST_WRITE_2
74
75 CMD_POST_WRITE_1 -> CMD_BEGIN:s [constraint="false"]
76 CMD_INNER_WRITE -> {CMD_INNER CMD_POST_DECODE_LITERALS}
77 [constraint="false"]
78 CMD_BEGIN:ne -> CMD_POST_DECODE_LITERALS [constraint="false"]
79 CMD_POST_WRAP_COPY -> CMD_BEGIN [constraint="false"]
80 CMD_POST_DECODE_LITERALS -> CMD_BEGIN:ne [constraint="false"]
81 CMD_POST_WRITE_2 -> CMD_POST_WRAP_COPY [constraint="false"]
82 {rank=same; CMD_BEGIN; CMD_INNER; CMD_POST_DECODE_LITERALS;
83 CMD_POST_WRAP_COPY}
84 {rank=same; CMD_INNER_WRITE; CMD_POST_WRITE_1; CMD_POST_WRITE_2}
85
86 {CMD_INNER CMD_POST_DECODE_LITERALS CMD_POST_WRAP_COPY} ->
87 _METABLOCK_DONE_PORT_ [style=invis]
88 {CMD_INNER_WRITE CMD_POST_WRITE_1} -> _METABLOCK_DONE_PORT_
89 [constraint="false" style=invis]
90 }
91
92 BEFORE_COMPRESSED_METABLOCK_HEADER:s -> HUFFMAN_CODE_0:n
93 HUFFMAN_CODE_0 -> HUFFMAN_CODE_1 -> HUFFMAN_CODE_2 -> HUFFMAN_CODE_3
94 HUFFMAN_CODE_0 -> METABLOCK_HEADER_2 -> CONTEXT_MODES -> CONTEXT_MAP_1
95 CONTEXT_MAP_1 -> CONTEXT_MAP_2 -> TREE_GROUP
96 TREE_GROUP -> BEFORE_COMPRESSED_METABLOCK_BODY:e
97 BEFORE_COMPRESSED_METABLOCK_BODY:s -> CMD_BEGIN:n
98
99 HUFFMAN_CODE_3:e -> HUFFMAN_CODE_0:ne [constraint="false"]
100 {rank=same; HUFFMAN_CODE_0; HUFFMAN_CODE_1; HUFFMAN_CODE_2; HUFFMAN_CODE_3}
101 {rank=same; METABLOCK_HEADER_2; CONTEXT_MODES; CONTEXT_MAP_1; CONTEXT_MAP_2;
102 TREE_GROUP}
103 }
104 METABLOCK_HEADER:e -> BEFORE_COMPRESSED_METABLOCK_HEADER:n
105
106 _METABLOCK_DONE_PORT_ -> METABLOCK_DONE:se
107 [constraint="false" ltail=cluster_command]
108
109 UNINITED [shape=Mdiamond];
110 DONE [shape=Msquare];
111 }
112
113
114 */
115
116 typedef enum {
117 BROTLI_STATE_UNINITED,
118 BROTLI_STATE_LARGE_WINDOW_BITS,
119 BROTLI_STATE_INITIALIZE,
120 BROTLI_STATE_METABLOCK_BEGIN,
121 BROTLI_STATE_METABLOCK_HEADER,
122 BROTLI_STATE_METABLOCK_HEADER_2,
123 BROTLI_STATE_CONTEXT_MODES,
124 BROTLI_STATE_COMMAND_BEGIN,
125 BROTLI_STATE_COMMAND_INNER,
126 BROTLI_STATE_COMMAND_POST_DECODE_LITERALS,
127 BROTLI_STATE_COMMAND_POST_WRAP_COPY,
128 BROTLI_STATE_UNCOMPRESSED,
129 BROTLI_STATE_METADATA,
130 BROTLI_STATE_COMMAND_INNER_WRITE,
131 BROTLI_STATE_METABLOCK_DONE,
132 BROTLI_STATE_COMMAND_POST_WRITE_1,
133 BROTLI_STATE_COMMAND_POST_WRITE_2,
134 BROTLI_STATE_BEFORE_COMPRESSED_METABLOCK_HEADER,
135 BROTLI_STATE_HUFFMAN_CODE_0,
136 BROTLI_STATE_HUFFMAN_CODE_1,
137 BROTLI_STATE_HUFFMAN_CODE_2,
138 BROTLI_STATE_HUFFMAN_CODE_3,
139 BROTLI_STATE_CONTEXT_MAP_1,
140 BROTLI_STATE_CONTEXT_MAP_2,
141 BROTLI_STATE_TREE_GROUP,
142 BROTLI_STATE_BEFORE_COMPRESSED_METABLOCK_BODY,
143 BROTLI_STATE_DONE
144 } BrotliRunningState;
145
146 typedef enum {
147 BROTLI_STATE_METABLOCK_HEADER_NONE,
148 BROTLI_STATE_METABLOCK_HEADER_EMPTY,
149 BROTLI_STATE_METABLOCK_HEADER_NIBBLES,
150 BROTLI_STATE_METABLOCK_HEADER_SIZE,
151 BROTLI_STATE_METABLOCK_HEADER_UNCOMPRESSED,
152 BROTLI_STATE_METABLOCK_HEADER_RESERVED,
153 BROTLI_STATE_METABLOCK_HEADER_BYTES,
154 BROTLI_STATE_METABLOCK_HEADER_METADATA
155 } BrotliRunningMetablockHeaderState;
156
157 typedef enum {
158 BROTLI_STATE_UNCOMPRESSED_NONE,
159 BROTLI_STATE_UNCOMPRESSED_WRITE
160 } BrotliRunningUncompressedState;
161
162 typedef enum {
163 BROTLI_STATE_TREE_GROUP_NONE,
164 BROTLI_STATE_TREE_GROUP_LOOP
165 } BrotliRunningTreeGroupState;
166
167 typedef enum {
168 BROTLI_STATE_CONTEXT_MAP_NONE,
169 BROTLI_STATE_CONTEXT_MAP_READ_PREFIX,
170 BROTLI_STATE_CONTEXT_MAP_HUFFMAN,
171 BROTLI_STATE_CONTEXT_MAP_DECODE,
172 BROTLI_STATE_CONTEXT_MAP_TRANSFORM
173 } BrotliRunningContextMapState;
174
175 typedef enum {
176 BROTLI_STATE_HUFFMAN_NONE,
177 BROTLI_STATE_HUFFMAN_SIMPLE_SIZE,
178 BROTLI_STATE_HUFFMAN_SIMPLE_READ,
179 BROTLI_STATE_HUFFMAN_SIMPLE_BUILD,
180 BROTLI_STATE_HUFFMAN_COMPLEX,
181 BROTLI_STATE_HUFFMAN_LENGTH_SYMBOLS
182 } BrotliRunningHuffmanState;
183
184 typedef enum {
185 BROTLI_STATE_DECODE_UINT8_NONE,
186 BROTLI_STATE_DECODE_UINT8_SHORT,
187 BROTLI_STATE_DECODE_UINT8_LONG
188 } BrotliRunningDecodeUint8State;
189
190 typedef enum {
191 BROTLI_STATE_READ_BLOCK_LENGTH_NONE,
192 BROTLI_STATE_READ_BLOCK_LENGTH_SUFFIX
193 } BrotliRunningReadBlockLengthState;
194
195 /* BrotliDecoderState addon, used for Compound Dictionary functionality. */
196 typedef struct BrotliDecoderCompoundDictionary {
197 int num_chunks;
198 int total_size;
199 int br_index;
200 int br_offset;
201 int br_length;
202 int br_copied;
203 const uint8_t* chunks[16];
204 int chunk_offsets[16];
205 int block_bits;
206 uint8_t block_map[256];
207 } BrotliDecoderCompoundDictionary;
208
209 typedef struct BrotliMetablockHeaderArena {
210 BrotliRunningTreeGroupState substate_tree_group;
211 BrotliRunningContextMapState substate_context_map;
212 BrotliRunningHuffmanState substate_huffman;
213
214 brotli_reg_t sub_loop_counter;
215
216 brotli_reg_t repeat_code_len;
217 brotli_reg_t prev_code_len;
218
219 /* For ReadHuffmanCode. */
220 brotli_reg_t symbol;
221 brotli_reg_t repeat;
222 brotli_reg_t space;
223
224 /* Huffman table for "histograms". */
225 HuffmanCode table[32];
226 /* List of heads of symbol chains. */
227 uint16_t* symbol_lists;
228 /* Storage from symbol_lists. */
229 uint16_t symbols_lists_array[BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1 +
230 BROTLI_NUM_COMMAND_SYMBOLS];
231 /* Tails of symbol chains. */
232 int next_symbol[32];
233 uint8_t code_length_code_lengths[BROTLI_CODE_LENGTH_CODES];
234 /* Population counts for the code lengths. */
235 uint16_t code_length_histo[16];
236 /* TODO(eustas): +2 bytes padding */
237
238 /* For HuffmanTreeGroupDecode. */
239 int htree_index;
240 HuffmanCode* next;
241
242 /* For DecodeContextMap. */
243 brotli_reg_t context_index;
244 brotli_reg_t max_run_length_prefix;
245 brotli_reg_t code;
246 HuffmanCode context_map_table[BROTLI_HUFFMAN_MAX_SIZE_272];
247 } BrotliMetablockHeaderArena;
248
249 typedef struct BrotliMetablockBodyArena {
250 uint8_t dist_extra_bits[544];
251 brotli_reg_t dist_offset[544];
252 } BrotliMetablockBodyArena;
253
254 struct BrotliDecoderStateStruct {
255 BrotliRunningState state;
256
257 /* This counter is reused for several disjoint loops. */
258 int loop_counter;
259
260 BrotliBitReader br;
261
262 brotli_alloc_func alloc_func;
263 brotli_free_func free_func;
264 void* memory_manager_opaque;
265
266 /* Temporary storage for remaining input. Brotli stream format is designed in
267 a way, that 64 bits are enough to make progress in decoding. */
268 union {
269 uint64_t u64;
270 uint8_t u8[8];
271 } buffer;
272 brotli_reg_t buffer_length;
273
274 int pos;
275 int max_backward_distance;
276 int max_distance;
277 int ringbuffer_size;
278 int ringbuffer_mask;
279 int dist_rb_idx;
280 int dist_rb[4];
281 int error_code;
282 int meta_block_remaining_len;
283
284 uint8_t* ringbuffer;
285 uint8_t* ringbuffer_end;
286 HuffmanCode* htree_command;
287 const uint8_t* context_lookup;
288 uint8_t* context_map_slice;
289 uint8_t* dist_context_map_slice;
290
291 /* This ring buffer holds a few past copy distances that will be used by
292 some special distance codes. */
293 HuffmanTreeGroup literal_hgroup;
294 HuffmanTreeGroup insert_copy_hgroup;
295 HuffmanTreeGroup distance_hgroup;
296 HuffmanCode* block_type_trees;
297 HuffmanCode* block_len_trees;
298 /* This is true if the literal context map histogram type always matches the
299 block type. It is then not needed to keep the context (faster decoding). */
300 int trivial_literal_context;
301 /* Distance context is actual after command is decoded and before distance is
302 computed. After distance computation it is used as a temporary variable. */
303 int distance_context;
304 brotli_reg_t block_length[3];
305 brotli_reg_t block_length_index;
306 brotli_reg_t num_block_types[3];
307 brotli_reg_t block_type_rb[6];
308 brotli_reg_t distance_postfix_bits;
309 brotli_reg_t num_direct_distance_codes;
310 brotli_reg_t num_dist_htrees;
311 uint8_t* dist_context_map;
312 HuffmanCode* literal_htree;
313
314 /* For partial write operations. */
315 size_t rb_roundtrips; /* how many times we went around the ring-buffer */
316 size_t partial_pos_out; /* how much output to the user in total */
317
318 /* For InverseMoveToFrontTransform. */
319 brotli_reg_t mtf_upper_bound;
320 uint32_t mtf[64 + 1];
321
322 int copy_length;
323 int distance_code;
324
325 uint8_t dist_htree_index;
326 /* TODO(eustas): +3 bytes padding */
327
328 /* Less used attributes are at the end of this struct. */
329
330 brotli_decoder_metadata_start_func metadata_start_func;
331 brotli_decoder_metadata_chunk_func metadata_chunk_func;
332 void* metadata_callback_opaque;
333
334 /* For reporting. */
335 uint64_t used_input; /* how many bytes of input are consumed */
336
337 /* States inside function calls. */
338 BrotliRunningMetablockHeaderState substate_metablock_header;
339 BrotliRunningUncompressedState substate_uncompressed;
340 BrotliRunningDecodeUint8State substate_decode_uint8;
341 BrotliRunningReadBlockLengthState substate_read_block_length;
342
343 int new_ringbuffer_size;
344 /* TODO(eustas): +4 bytes padding */
345
346 unsigned int is_last_metablock : 1;
347 unsigned int is_uncompressed : 1;
348 unsigned int is_metadata : 1;
349 unsigned int should_wrap_ringbuffer : 1;
350 unsigned int canny_ringbuffer_allocation : 1;
351 unsigned int large_window : 1;
352 unsigned int window_bits : 6;
353 unsigned int size_nibbles : 8;
354 /* TODO(eustas): +12 bits padding */
355
356 brotli_reg_t num_literal_htrees;
357 uint8_t* context_map;
358 uint8_t* context_modes;
359
360 BrotliSharedDictionary* dictionary;
361 BrotliDecoderCompoundDictionary* compound_dictionary;
362
363 uint32_t trivial_literal_contexts[8]; /* 256 bits */
364
365 union {
366 BrotliMetablockHeaderArena header;
367 BrotliMetablockBodyArena body;
368 } arena;
369 };
370
371 typedef struct BrotliDecoderStateStruct BrotliDecoderStateInternal;
372 #define BrotliDecoderState BrotliDecoderStateInternal
373
374 BROTLI_INTERNAL BROTLI_BOOL BrotliDecoderStateInit(BrotliDecoderState* s,
375 brotli_alloc_func alloc_func, brotli_free_func free_func, void* opaque);
376 BROTLI_INTERNAL void BrotliDecoderStateCleanup(BrotliDecoderState* s);
377 BROTLI_INTERNAL void BrotliDecoderStateMetablockBegin(BrotliDecoderState* s);
378 BROTLI_INTERNAL void BrotliDecoderStateCleanupAfterMetablock(
379 BrotliDecoderState* s);
380 BROTLI_INTERNAL BROTLI_BOOL BrotliDecoderHuffmanTreeGroupInit(
381 BrotliDecoderState* s, HuffmanTreeGroup* group,
382 brotli_reg_t alphabet_size_max, brotli_reg_t alphabet_size_limit,
383 brotli_reg_t ntrees);
384
385 #define BROTLI_DECODER_ALLOC(S, L) S->alloc_func(S->memory_manager_opaque, L)
386
387 #define BROTLI_DECODER_FREE(S, X) { \
388 S->free_func(S->memory_manager_opaque, X); \
389 X = NULL; \
390 }
391
392 /* Literal/Command/Distance block size maximum; same as maximum metablock size;
393 used as block size when there is no block switching. */
394 #define BROTLI_BLOCK_SIZE_CAP (1U << 24)
395
396 #if defined(__cplusplus) || defined(c_plusplus)
397 } /* extern "C" */
398 #endif
399
400 #endif /* BROTLI_DEC_STATE_H_ */