« back to all changes in this revision
Viewing changes to thirdparty/brotli/c/dec/decode.c
- browse files at revision 3576
- compare with another revision
- download diff
- download tarball
- view history from revision 3576
- Committer: Jose Fonseca
- Date: 2018-04-05 10:04:29 UTC
- Revision ID: git-v1:da5c63cc6f90b1a407bb25b0d9ec7867346088e2
brotli: Update to 1.0.2.
- files added:
- thirdparty/brotli/README
- thirdparty/brotli/c
- thirdparty/brotli/c/common
- thirdparty/brotli/c/dec
- thirdparty/brotli/c/enc
- thirdparty/brotli/c/fuzz
- thirdparty/brotli/c/include
- thirdparty/brotli/c/include/brotli
- thirdparty/brotli/c/tools
- files removed:
- thirdparty/brotli/common
- thirdparty/brotli/dec
- thirdparty/brotli/enc
- files modified:
- CMakeLists.txt
added
removed
thirdparty/brotli/c/dec/decode.c
1
/* Copyright 2013 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
#include <brotli/decode.h>
8
9
#ifdef __ARM_NEON__
10
#include <arm_neon.h>
11
#endif
12
13
#include <stdlib.h> /* free, malloc */
14
#include <string.h> /* memcpy, memset */
15
16
#include "../common/constants.h"
17
#include "../common/dictionary.h"
18
#include "../common/version.h"
19
#include "./bit_reader.h"
20
#include "./context.h"
21
#include "./huffman.h"
22
#include "./port.h"
23
#include "./prefix.h"
24
#include "./state.h"
25
#include "./transform.h"
26
27
#if defined(__cplusplus) || defined(c_plusplus)
28
extern "C" {
29
#endif
30
31
#define BROTLI_FAILURE(CODE) (BROTLI_DUMP(), CODE)
32
33
#define BROTLI_LOG_UINT(name) \
34
BROTLI_LOG(("[%s] %s = %lu\n", __func__, #name, (unsigned long)(name)))
35
#define BROTLI_LOG_ARRAY_INDEX(array_name, idx) \
36
BROTLI_LOG(("[%s] %s[%lu] = %lu\n", __func__, #array_name, \
37
(unsigned long)(idx), (unsigned long)array_name[idx]))
38
39
#define HUFFMAN_TABLE_BITS 8U
40
#define HUFFMAN_TABLE_MASK 0xff
41
42
/* We need the slack region for the following reasons:
43
- doing up to two 16-byte copies for fast backward copying
44
- inserting transformed dictionary word (5 prefix + 24 base + 8 suffix) */
45
static const uint32_t kRingBufferWriteAheadSlack = 42;
46
47
static const uint8_t kCodeLengthCodeOrder[BROTLI_CODE_LENGTH_CODES] = {
48
1, 2, 3, 4, 0, 5, 17, 6, 16, 7, 8, 9, 10, 11, 12, 13, 14, 15,
49
};
50
51
/* Static prefix code for the complex code length code lengths. */
52
static const uint8_t kCodeLengthPrefixLength[16] = {
53
2, 2, 2, 3, 2, 2, 2, 4, 2, 2, 2, 3, 2, 2, 2, 4,
54
};
55
56
static const uint8_t kCodeLengthPrefixValue[16] = {
57
0, 4, 3, 2, 0, 4, 3, 1, 0, 4, 3, 2, 0, 4, 3, 5,
58
};
59
60
BROTLI_BOOL BrotliDecoderSetParameter(
61
BrotliDecoderState* state, BrotliDecoderParameter p, uint32_t value) {
62
switch (p) {
63
case BROTLI_DECODER_PARAM_DISABLE_RING_BUFFER_REALLOCATION:
64
state->canny_ringbuffer_allocation = !!value ? 0 : 1;
65
return BROTLI_TRUE;
66
67
default: return BROTLI_FALSE;
68
}
69
}
70
71
BrotliDecoderState* BrotliDecoderCreateInstance(
72
brotli_alloc_func alloc_func, brotli_free_func free_func, void* opaque) {
73
BrotliDecoderState* state = 0;
74
if (!alloc_func && !free_func) {
75
state = (BrotliDecoderState*)malloc(sizeof(BrotliDecoderState));
76
} else if (alloc_func && free_func) {
77
state = (BrotliDecoderState*)alloc_func(opaque, sizeof(BrotliDecoderState));
78
}
79
if (state == 0) {
80
BROTLI_DUMP();
81
return 0;
82
}
83
BrotliDecoderStateInitWithCustomAllocators(
84
state, alloc_func, free_func, opaque);
85
return state;
86
}
87
88
/* Deinitializes and frees BrotliDecoderState instance. */
89
void BrotliDecoderDestroyInstance(BrotliDecoderState* state) {
90
if (!state) {
91
return;
92
} else {
93
brotli_free_func free_func = state->free_func;
94
void* opaque = state->memory_manager_opaque;
95
BrotliDecoderStateCleanup(state);
96
free_func(opaque, state);
97
}
98
}
99
100
/* Saves error code and converts it to BrotliDecoderResult */
101
static BROTLI_NOINLINE BrotliDecoderResult SaveErrorCode(
102
BrotliDecoderState* s, BrotliDecoderErrorCode e) {
103
s->error_code = (int)e;
104
switch (e) {
105
case BROTLI_DECODER_SUCCESS:
106
return BROTLI_DECODER_RESULT_SUCCESS;
107
case BROTLI_DECODER_NEEDS_MORE_INPUT:
108
return BROTLI_DECODER_RESULT_NEEDS_MORE_INPUT;
109
case BROTLI_DECODER_NEEDS_MORE_OUTPUT:
110
return BROTLI_DECODER_RESULT_NEEDS_MORE_OUTPUT;
111
default:
112
return BROTLI_DECODER_RESULT_ERROR;
113
}
114
}
115
116
/* Decodes a number in the range [9..24], by reading 1 - 7 bits.
117
Precondition: bit-reader accumulator has at least 7 bits. */
118
static uint32_t DecodeWindowBits(BrotliBitReader* br) {
119
uint32_t n;
120
BrotliTakeBits(br, 1, &n);
121
if (n == 0) {
122
return 16;
123
}
124
BrotliTakeBits(br, 3, &n);
125
if (n != 0) {
126
return 17 + n;
127
}
128
BrotliTakeBits(br, 3, &n);
129
if (n != 0) {
130
return 8 + n;
131
}
132
return 17;
133
}
134
135
static BROTLI_INLINE void memmove16(uint8_t* dst, uint8_t* src) {
136
#if defined(__ARM_NEON__)
137
vst1q_u8(dst, vld1q_u8(src));
138
#else
139
uint32_t buffer[4];
140
memcpy(buffer, src, 16);
141
memcpy(dst, buffer, 16);
142
#endif
143
}
144
145
/* Decodes a number in the range [0..255], by reading 1 - 11 bits. */
146
static BROTLI_NOINLINE BrotliDecoderErrorCode DecodeVarLenUint8(
147
BrotliDecoderState* s, BrotliBitReader* br, uint32_t* value) {
148
uint32_t bits;
149
switch (s->substate_decode_uint8) {
150
case BROTLI_STATE_DECODE_UINT8_NONE:
151
if (BROTLI_PREDICT_FALSE(!BrotliSafeReadBits(br, 1, &bits))) {
152
return BROTLI_DECODER_NEEDS_MORE_INPUT;
153
}
154
if (bits == 0) {
155
*value = 0;
156
return BROTLI_DECODER_SUCCESS;
157
}
158
/* No break, transit to the next state. */
159
160
case BROTLI_STATE_DECODE_UINT8_SHORT:
161
if (BROTLI_PREDICT_FALSE(!BrotliSafeReadBits(br, 3, &bits))) {
162
s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_SHORT;
163
return BROTLI_DECODER_NEEDS_MORE_INPUT;
164
}
165
if (bits == 0) {
166
*value = 1;
167
s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_NONE;
168
return BROTLI_DECODER_SUCCESS;
169
}
170
/* Use output value as a temporary storage. It MUST be persisted. */
171
*value = bits;
172
/* No break, transit to the next state. */
173
174
case BROTLI_STATE_DECODE_UINT8_LONG:
175
if (BROTLI_PREDICT_FALSE(!BrotliSafeReadBits(br, *value, &bits))) {
176
s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_LONG;
177
return BROTLI_DECODER_NEEDS_MORE_INPUT;
178
}
179
*value = (1U << *value) + bits;
180
s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_NONE;
181
return BROTLI_DECODER_SUCCESS;
182
183
default:
184
return
185
BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE);
186
}
187
}
188
189
/* Decodes a metablock length and flags by reading 2 - 31 bits. */
190
static BrotliDecoderErrorCode BROTLI_NOINLINE DecodeMetaBlockLength(
191
BrotliDecoderState* s, BrotliBitReader* br) {
192
uint32_t bits;
193
int i;
194
for (;;) {
195
switch (s->substate_metablock_header) {
196
case BROTLI_STATE_METABLOCK_HEADER_NONE:
197
if (!BrotliSafeReadBits(br, 1, &bits)) {
198
return BROTLI_DECODER_NEEDS_MORE_INPUT;
199
}
200
s->is_last_metablock = bits ? 1 : 0;
201
s->meta_block_remaining_len = 0;
202
s->is_uncompressed = 0;
203
s->is_metadata = 0;
204
if (!s->is_last_metablock) {
205
s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NIBBLES;
206
break;
207
}
208
s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_EMPTY;
209
/* No break, transit to the next state. */
210
211
case BROTLI_STATE_METABLOCK_HEADER_EMPTY:
212
if (!BrotliSafeReadBits(br, 1, &bits)) {
213
return BROTLI_DECODER_NEEDS_MORE_INPUT;
214
}
215
if (bits) {
216
s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE;
217
return BROTLI_DECODER_SUCCESS;
218
}
219
s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NIBBLES;
220
/* No break, transit to the next state. */
221
222
case BROTLI_STATE_METABLOCK_HEADER_NIBBLES:
223
if (!BrotliSafeReadBits(br, 2, &bits)) {
224
return BROTLI_DECODER_NEEDS_MORE_INPUT;
225
}
226
s->size_nibbles = (uint8_t)(bits + 4);
227
s->loop_counter = 0;
228
if (bits == 3) {
229
s->is_metadata = 1;
230
s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_RESERVED;
231
break;
232
}
233
s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_SIZE;
234
/* No break, transit to the next state. */
235
236
case BROTLI_STATE_METABLOCK_HEADER_SIZE:
237
i = s->loop_counter;
238
for (; i < (int)s->size_nibbles; ++i) {
239
if (!BrotliSafeReadBits(br, 4, &bits)) {
240
s->loop_counter = i;
241
return BROTLI_DECODER_NEEDS_MORE_INPUT;
242
}
243
if (i + 1 == s->size_nibbles && s->size_nibbles > 4 && bits == 0) {
244
return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_EXUBERANT_NIBBLE);
245
}
246
s->meta_block_remaining_len |= (int)(bits << (i * 4));
247
}
248
s->substate_metablock_header =
249
BROTLI_STATE_METABLOCK_HEADER_UNCOMPRESSED;
250
/* No break, transit to the next state. */
251
252
case BROTLI_STATE_METABLOCK_HEADER_UNCOMPRESSED:
253
if (!s->is_last_metablock) {
254
if (!BrotliSafeReadBits(br, 1, &bits)) {
255
return BROTLI_DECODER_NEEDS_MORE_INPUT;
256
}
257
s->is_uncompressed = bits ? 1 : 0;
258
}
259
++s->meta_block_remaining_len;
260
s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE;
261
return BROTLI_DECODER_SUCCESS;
262
263
case BROTLI_STATE_METABLOCK_HEADER_RESERVED:
264
if (!BrotliSafeReadBits(br, 1, &bits)) {
265
return BROTLI_DECODER_NEEDS_MORE_INPUT;
266
}
267
if (bits != 0) {
268
return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_RESERVED);
269
}
270
s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_BYTES;
271
/* No break, transit to the next state. */
272
273
case BROTLI_STATE_METABLOCK_HEADER_BYTES:
274
if (!BrotliSafeReadBits(br, 2, &bits)) {
275
return BROTLI_DECODER_NEEDS_MORE_INPUT;
276
}
277
if (bits == 0) {
278
s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE;
279
return BROTLI_DECODER_SUCCESS;
280
}
281
s->size_nibbles = (uint8_t)bits;
282
s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_METADATA;
283
/* No break, transit to the next state. */
284
285
case BROTLI_STATE_METABLOCK_HEADER_METADATA:
286
i = s->loop_counter;
287
for (; i < (int)s->size_nibbles; ++i) {
288
if (!BrotliSafeReadBits(br, 8, &bits)) {
289
s->loop_counter = i;
290
return BROTLI_DECODER_NEEDS_MORE_INPUT;
291
}
292
if (i + 1 == s->size_nibbles && s->size_nibbles > 1 && bits == 0) {
293
return BROTLI_FAILURE(
294
BROTLI_DECODER_ERROR_FORMAT_EXUBERANT_META_NIBBLE);
295
}
296
s->meta_block_remaining_len |= (int)(bits << (i * 8));
297
}
298
++s->meta_block_remaining_len;
299
s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE;
300
return BROTLI_DECODER_SUCCESS;
301
302
default:
303
return
304
BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE);
305
}
306
}
307
}
308
309
/* Decodes the Huffman code.
310
This method doesn't read data from the bit reader, BUT drops the amount of
311
bits that correspond to the decoded symbol.
312
bits MUST contain at least 15 (BROTLI_HUFFMAN_MAX_CODE_LENGTH) valid bits. */
313
static BROTLI_INLINE uint32_t DecodeSymbol(uint32_t bits,
314
const HuffmanCode* table,
315
BrotliBitReader* br) {
316
table += bits & HUFFMAN_TABLE_MASK;
317
if (table->bits > HUFFMAN_TABLE_BITS) {
318
uint32_t nbits = table->bits - HUFFMAN_TABLE_BITS;
319
BrotliDropBits(br, HUFFMAN_TABLE_BITS);
320
table += table->value;
321
table += (bits >> HUFFMAN_TABLE_BITS) & BitMask(nbits);
322
}
323
BrotliDropBits(br, table->bits);
324
return table->value;
325
}
326
327
/* Reads and decodes the next Huffman code from bit-stream.
328
This method peeks 16 bits of input and drops 0 - 15 of them. */
329
static BROTLI_INLINE uint32_t ReadSymbol(const HuffmanCode* table,
330
BrotliBitReader* br) {
331
return DecodeSymbol(BrotliGet16BitsUnmasked(br), table, br);
332
}
333
334
/* Same as DecodeSymbol, but it is known that there is less than 15 bits of
335
input are currently available. */
336
static BROTLI_NOINLINE BROTLI_BOOL SafeDecodeSymbol(
337
const HuffmanCode* table, BrotliBitReader* br, uint32_t* result) {
338
uint32_t val;
339
uint32_t available_bits = BrotliGetAvailableBits(br);
340
if (available_bits == 0) {
341
if (table->bits == 0) {
342
*result = table->value;
343
return BROTLI_TRUE;
344
}
345
return BROTLI_FALSE; /* No valid bits at all. */
346
}
347
val = (uint32_t)BrotliGetBitsUnmasked(br);
348
table += val & HUFFMAN_TABLE_MASK;
349
if (table->bits <= HUFFMAN_TABLE_BITS) {
350
if (table->bits <= available_bits) {
351
BrotliDropBits(br, table->bits);
352
*result = table->value;
353
return BROTLI_TRUE;
354
} else {
355
return BROTLI_FALSE; /* Not enough bits for the first level. */
356
}
357
}
358
if (available_bits <= HUFFMAN_TABLE_BITS) {
359
return BROTLI_FALSE; /* Not enough bits to move to the second level. */
360
}
361
362
/* Speculatively drop HUFFMAN_TABLE_BITS. */
363
val = (val & BitMask(table->bits)) >> HUFFMAN_TABLE_BITS;
364
available_bits -= HUFFMAN_TABLE_BITS;
365
table += table->value + val;
366
if (available_bits < table->bits) {
367
return BROTLI_FALSE; /* Not enough bits for the second level. */
368
}
369
370
BrotliDropBits(br, HUFFMAN_TABLE_BITS + table->bits);
371
*result = table->value;
372
return BROTLI_TRUE;
373
}
374
375
static BROTLI_INLINE BROTLI_BOOL SafeReadSymbol(
376
const HuffmanCode* table, BrotliBitReader* br, uint32_t* result) {
377
uint32_t val;
378
if (BROTLI_PREDICT_TRUE(BrotliSafeGetBits(br, 15, &val))) {
379
*result = DecodeSymbol(val, table, br);
380
return BROTLI_TRUE;
381
}
382
return SafeDecodeSymbol(table, br, result);
383
}
384
385
/* Makes a look-up in first level Huffman table. Peeks 8 bits. */
386
static BROTLI_INLINE void PreloadSymbol(int safe,
387
const HuffmanCode* table,
388
BrotliBitReader* br,
389
uint32_t* bits,
390
uint32_t* value) {
391
if (safe) {
392
return;
393
}
394
table += BrotliGetBits(br, HUFFMAN_TABLE_BITS);
395
*bits = table->bits;
396
*value = table->value;
397
}
398
399
/* Decodes the next Huffman code using data prepared by PreloadSymbol.
400
Reads 0 - 15 bits. Also peeks 8 following bits. */
401
static BROTLI_INLINE uint32_t ReadPreloadedSymbol(const HuffmanCode* table,
402
BrotliBitReader* br,
403
uint32_t* bits,
404
uint32_t* value) {
405
uint32_t result = *value;
406
if (BROTLI_PREDICT_FALSE(*bits > HUFFMAN_TABLE_BITS)) {
407
uint32_t val = BrotliGet16BitsUnmasked(br);
408
const HuffmanCode* ext = table + (val & HUFFMAN_TABLE_MASK) + *value;
409
uint32_t mask = BitMask((*bits - HUFFMAN_TABLE_BITS));
410
BrotliDropBits(br, HUFFMAN_TABLE_BITS);
411
ext += (val >> HUFFMAN_TABLE_BITS) & mask;
412
BrotliDropBits(br, ext->bits);
413
result = ext->value;
414
} else {
415
BrotliDropBits(br, *bits);
416
}
417
PreloadSymbol(0, table, br, bits, value);
418
return result;
419
}
420
421
static BROTLI_INLINE uint32_t Log2Floor(uint32_t x) {
422
uint32_t result = 0;
423
while (x) {
424
x >>= 1;
425
++result;
426
}
427
return result;
428
}
429
430
/* Reads (s->symbol + 1) symbols.
431
Totally 1..4 symbols are read, 1..10 bits each.
432
The list of symbols MUST NOT contain duplicates.
433
*/
434
static BrotliDecoderErrorCode ReadSimpleHuffmanSymbols(
435
uint32_t alphabet_size, BrotliDecoderState* s) {
436
/* max_bits == 1..10; symbol == 0..3; 1..40 bits will be read. */
437
BrotliBitReader* br = &s->br;
438
uint32_t max_bits = Log2Floor(alphabet_size - 1);
439
uint32_t i = s->sub_loop_counter;
440
uint32_t num_symbols = s->symbol;
441
while (i <= num_symbols) {
442
uint32_t v;
443
if (BROTLI_PREDICT_FALSE(!BrotliSafeReadBits(br, max_bits, &v))) {
444
s->sub_loop_counter = i;
445
s->substate_huffman = BROTLI_STATE_HUFFMAN_SIMPLE_READ;
446
return BROTLI_DECODER_NEEDS_MORE_INPUT;
447
}
448
if (v >= alphabet_size) {
449
return
450
BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_SIMPLE_HUFFMAN_ALPHABET);
451
}
452
s->symbols_lists_array[i] = (uint16_t)v;
453
BROTLI_LOG_UINT(s->symbols_lists_array[i]);
454
++i;
455
}
456
457
for (i = 0; i < num_symbols; ++i) {
458
uint32_t k = i + 1;
459
for (; k <= num_symbols; ++k) {
460
if (s->symbols_lists_array[i] == s->symbols_lists_array[k]) {
461
return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_SIMPLE_HUFFMAN_SAME);
462
}
463
}
464
}
465
466
return BROTLI_DECODER_SUCCESS;
467
}
468
469
/* Process single decoded symbol code length:
470
A) reset the repeat variable
471
B) remember code length (if it is not 0)
472
C) extend corresponding index-chain
473
D) reduce the Huffman space
474
E) update the histogram
475
*/
476
static BROTLI_INLINE void ProcessSingleCodeLength(uint32_t code_len,
477
uint32_t* symbol, uint32_t* repeat, uint32_t* space,
478
uint32_t* prev_code_len, uint16_t* symbol_lists,
479
uint16_t* code_length_histo, int* next_symbol) {
480
*repeat = 0;
481
if (code_len != 0) { /* code_len == 1..15 */
482
symbol_lists[next_symbol[code_len]] = (uint16_t)(*symbol);
483
next_symbol[code_len] = (int)(*symbol);
484
*prev_code_len = code_len;
485
*space -= 32768U >> code_len;
486
code_length_histo[code_len]++;
487
BROTLI_LOG(("[ReadHuffmanCode] code_length[%d] = %d\n", *symbol, code_len));
488
}
489
(*symbol)++;
490
}
491
492
/* Process repeated symbol code length.
493
A) Check if it is the extension of previous repeat sequence; if the decoded
494
value is not BROTLI_REPEAT_PREVIOUS_CODE_LENGTH, then it is a new
495
symbol-skip
496
B) Update repeat variable
497
C) Check if operation is feasible (fits alphabet)
498
D) For each symbol do the same operations as in ProcessSingleCodeLength
499
500
PRECONDITION: code_len == BROTLI_REPEAT_PREVIOUS_CODE_LENGTH or
501
code_len == BROTLI_REPEAT_ZERO_CODE_LENGTH
502
*/
503
static BROTLI_INLINE void ProcessRepeatedCodeLength(uint32_t code_len,
504
uint32_t repeat_delta, uint32_t alphabet_size, uint32_t* symbol,
505
uint32_t* repeat, uint32_t* space, uint32_t* prev_code_len,
506
uint32_t* repeat_code_len, uint16_t* symbol_lists,
507
uint16_t* code_length_histo, int* next_symbol) {
508
uint32_t old_repeat;
509
uint32_t extra_bits = 3; /* for BROTLI_REPEAT_ZERO_CODE_LENGTH */
510
uint32_t new_len = 0; /* for BROTLI_REPEAT_ZERO_CODE_LENGTH */
511
if (code_len == BROTLI_REPEAT_PREVIOUS_CODE_LENGTH) {
512
new_len = *prev_code_len;
513
extra_bits = 2;
514
}
515
if (*repeat_code_len != new_len) {
516
*repeat = 0;
517
*repeat_code_len = new_len;
518
}
519
old_repeat = *repeat;
520
if (*repeat > 0) {
521
*repeat -= 2;
522
*repeat <<= extra_bits;
523
}
524
*repeat += repeat_delta + 3U;
525
repeat_delta = *repeat - old_repeat;
526
if (*symbol + repeat_delta > alphabet_size) {
527
BROTLI_DUMP();
528
*symbol = alphabet_size;
529
*space = 0xFFFFF;
530
return;
531
}
532
BROTLI_LOG(("[ReadHuffmanCode] code_length[%d..%d] = %d\n",
533
*symbol, *symbol + repeat_delta - 1, *repeat_code_len));
534
if (*repeat_code_len != 0) {
535
unsigned last = *symbol + repeat_delta;
536
int next = next_symbol[*repeat_code_len];
537
do {
538
symbol_lists[next] = (uint16_t)*symbol;
539
next = (int)*symbol;
540
} while (++(*symbol) != last);
541
next_symbol[*repeat_code_len] = next;
542
*space -= repeat_delta << (15 - *repeat_code_len);
543
code_length_histo[*repeat_code_len] =
544
(uint16_t)(code_length_histo[*repeat_code_len] + repeat_delta);
545
} else {
546
*symbol += repeat_delta;
547
}
548
}
549
550
/* Reads and decodes symbol codelengths. */
551
static BrotliDecoderErrorCode ReadSymbolCodeLengths(
552
uint32_t alphabet_size, BrotliDecoderState* s) {
553
BrotliBitReader* br = &s->br;
554
uint32_t symbol = s->symbol;
555
uint32_t repeat = s->repeat;
556
uint32_t space = s->space;
557
uint32_t prev_code_len = s->prev_code_len;
558
uint32_t repeat_code_len = s->repeat_code_len;
559
uint16_t* symbol_lists = s->symbol_lists;
560
uint16_t* code_length_histo = s->code_length_histo;
561
int* next_symbol = s->next_symbol;
562
if (!BrotliWarmupBitReader(br)) {
563
return BROTLI_DECODER_NEEDS_MORE_INPUT;
564
}
565
while (symbol < alphabet_size && space > 0) {
566
const HuffmanCode* p = s->table;
567
uint32_t code_len;
568
if (!BrotliCheckInputAmount(br, BROTLI_SHORT_FILL_BIT_WINDOW_READ)) {
569
s->symbol = symbol;
570
s->repeat = repeat;
571
s->prev_code_len = prev_code_len;
572
s->repeat_code_len = repeat_code_len;
573
s->space = space;
574
return BROTLI_DECODER_NEEDS_MORE_INPUT;
575
}
576
BrotliFillBitWindow16(br);
577
p += BrotliGetBitsUnmasked(br) &
578
BitMask(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH);
579
BrotliDropBits(br, p->bits); /* Use 1..5 bits */
580
code_len = p->value; /* code_len == 0..17 */
581
if (code_len < BROTLI_REPEAT_PREVIOUS_CODE_LENGTH) {
582
ProcessSingleCodeLength(code_len, &symbol, &repeat, &space,
583
&prev_code_len, symbol_lists, code_length_histo, next_symbol);
584
} else { /* code_len == 16..17, extra_bits == 2..3 */
585
uint32_t extra_bits =
586
(code_len == BROTLI_REPEAT_PREVIOUS_CODE_LENGTH) ? 2 : 3;
587
uint32_t repeat_delta =
588
(uint32_t)BrotliGetBitsUnmasked(br) & BitMask(extra_bits);
589
BrotliDropBits(br, extra_bits);
590
ProcessRepeatedCodeLength(code_len, repeat_delta, alphabet_size,
591
&symbol, &repeat, &space, &prev_code_len, &repeat_code_len,
592
symbol_lists, code_length_histo, next_symbol);
593
}
594
}
595
s->space = space;
596
return BROTLI_DECODER_SUCCESS;
597
}
598
599
static BrotliDecoderErrorCode SafeReadSymbolCodeLengths(
600
uint32_t alphabet_size, BrotliDecoderState* s) {
601
BrotliBitReader* br = &s->br;
602
BROTLI_BOOL get_byte = BROTLI_FALSE;
603
while (s->symbol < alphabet_size && s->space > 0) {
604
const HuffmanCode* p = s->table;
605
uint32_t code_len;
606
uint32_t available_bits;
607
uint32_t bits = 0;
608
if (get_byte && !BrotliPullByte(br)) return BROTLI_DECODER_NEEDS_MORE_INPUT;
609
get_byte = BROTLI_FALSE;
610
available_bits = BrotliGetAvailableBits(br);
611
if (available_bits != 0) {
612
bits = (uint32_t)BrotliGetBitsUnmasked(br);
613
}
614
p += bits & BitMask(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH);
615
if (p->bits > available_bits) {
616
get_byte = BROTLI_TRUE;
617
continue;
618
}
619
code_len = p->value; /* code_len == 0..17 */
620
if (code_len < BROTLI_REPEAT_PREVIOUS_CODE_LENGTH) {
621
BrotliDropBits(br, p->bits);
622
ProcessSingleCodeLength(code_len, &s->symbol, &s->repeat, &s->space,
623
&s->prev_code_len, s->symbol_lists, s->code_length_histo,
624
s->next_symbol);
625
} else { /* code_len == 16..17, extra_bits == 2..3 */
626
uint32_t extra_bits = code_len - 14U;
627
uint32_t repeat_delta = (bits >> p->bits) & BitMask(extra_bits);
628
if (available_bits < p->bits + extra_bits) {
629
get_byte = BROTLI_TRUE;
630
continue;
631
}
632
BrotliDropBits(br, p->bits + extra_bits);
633
ProcessRepeatedCodeLength(code_len, repeat_delta, alphabet_size,
634
&s->symbol, &s->repeat, &s->space, &s->prev_code_len,
635
&s->repeat_code_len, s->symbol_lists, s->code_length_histo,
636
s->next_symbol);
637
}
638
}
639
return BROTLI_DECODER_SUCCESS;
640
}
641
642
/* Reads and decodes 15..18 codes using static prefix code.
643
Each code is 2..4 bits long. In total 30..72 bits are used. */
644
static BrotliDecoderErrorCode ReadCodeLengthCodeLengths(BrotliDecoderState* s) {
645
BrotliBitReader* br = &s->br;
646
uint32_t num_codes = s->repeat;
647
unsigned space = s->space;
648
uint32_t i = s->sub_loop_counter;
649
for (; i < BROTLI_CODE_LENGTH_CODES; ++i) {
650
const uint8_t code_len_idx = kCodeLengthCodeOrder[i];
651
uint32_t ix;
652
uint32_t v;
653
if (BROTLI_PREDICT_FALSE(!BrotliSafeGetBits(br, 4, &ix))) {
654
uint32_t available_bits = BrotliGetAvailableBits(br);
655
if (available_bits != 0) {
656
ix = BrotliGetBitsUnmasked(br) & 0xF;
657
} else {
658
ix = 0;
659
}
660
if (kCodeLengthPrefixLength[ix] > available_bits) {
661
s->sub_loop_counter = i;
662
s->repeat = num_codes;
663
s->space = space;
664
s->substate_huffman = BROTLI_STATE_HUFFMAN_COMPLEX;
665
return BROTLI_DECODER_NEEDS_MORE_INPUT;
666
}
667
}
668
v = kCodeLengthPrefixValue[ix];
669
BrotliDropBits(br, kCodeLengthPrefixLength[ix]);
670
s->code_length_code_lengths[code_len_idx] = (uint8_t)v;
671
BROTLI_LOG_ARRAY_INDEX(s->code_length_code_lengths, code_len_idx);
672
if (v != 0) {
673
space = space - (32U >> v);
674
++num_codes;
675
++s->code_length_histo[v];
676
if (space - 1U >= 32U) {
677
/* space is 0 or wrapped around */
678
break;
679
}
680
}
681
}
682
if (!(num_codes == 1 || space == 0)) {
683
return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_CL_SPACE);
684
}
685
return BROTLI_DECODER_SUCCESS;
686
}
687
688
/* Decodes the Huffman tables.
689
There are 2 scenarios:
690
A) Huffman code contains only few symbols (1..4). Those symbols are read
691
directly; their code lengths are defined by the number of symbols.
692
For this scenario 4 - 45 bits will be read.
693
694
B) 2-phase decoding:
695
B.1) Small Huffman table is decoded; it is specified with code lengths
696
encoded with predefined entropy code. 32 - 74 bits are used.
697
B.2) Decoded table is used to decode code lengths of symbols in resulting
698
Huffman table. In worst case 3520 bits are read.
699
*/
700
static BrotliDecoderErrorCode ReadHuffmanCode(uint32_t alphabet_size,
701
HuffmanCode* table,
702
uint32_t* opt_table_size,
703
BrotliDecoderState* s) {
704
BrotliBitReader* br = &s->br;
705
/* Unnecessary masking, but might be good for safety. */
706
alphabet_size &= 0x3ff;
707
/* State machine */
708
for (;;) {
709
switch (s->substate_huffman) {
710
case BROTLI_STATE_HUFFMAN_NONE:
711
if (!BrotliSafeReadBits(br, 2, &s->sub_loop_counter)) {
712
return BROTLI_DECODER_NEEDS_MORE_INPUT;
713
}
714
BROTLI_LOG_UINT(s->sub_loop_counter);
715
/* The value is used as follows:
716
1 for simple code;
717
0 for no skipping, 2 skips 2 code lengths, 3 skips 3 code lengths */
718
if (s->sub_loop_counter != 1) {
719
s->space = 32;
720
s->repeat = 0; /* num_codes */
721
memset(&s->code_length_histo[0], 0, sizeof(s->code_length_histo[0]) *
722
(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH + 1));
723
memset(&s->code_length_code_lengths[0], 0,
724
sizeof(s->code_length_code_lengths));
725
s->substate_huffman = BROTLI_STATE_HUFFMAN_COMPLEX;
726
continue;
727
}
728
/* No break, transit to the next state. */
729
730
case BROTLI_STATE_HUFFMAN_SIMPLE_SIZE:
731
/* Read symbols, codes & code lengths directly. */
732
if (!BrotliSafeReadBits(br, 2, &s->symbol)) { /* num_symbols */
733
s->substate_huffman = BROTLI_STATE_HUFFMAN_SIMPLE_SIZE;
734
return BROTLI_DECODER_NEEDS_MORE_INPUT;
735
}
736
s->sub_loop_counter = 0;
737
/* No break, transit to the next state. */
738
case BROTLI_STATE_HUFFMAN_SIMPLE_READ: {
739
BrotliDecoderErrorCode result =
740
ReadSimpleHuffmanSymbols(alphabet_size, s);
741
if (result != BROTLI_DECODER_SUCCESS) {
742
return result;
743
}
744
/* No break, transit to the next state. */
745
}
746
case BROTLI_STATE_HUFFMAN_SIMPLE_BUILD: {
747
uint32_t table_size;
748
if (s->symbol == 3) {
749
uint32_t bits;
750
if (!BrotliSafeReadBits(br, 1, &bits)) {
751
s->substate_huffman = BROTLI_STATE_HUFFMAN_SIMPLE_BUILD;
752
return BROTLI_DECODER_NEEDS_MORE_INPUT;
753
}
754
s->symbol += bits;
755
}
756
BROTLI_LOG_UINT(s->symbol);
757
table_size = BrotliBuildSimpleHuffmanTable(
758
table, HUFFMAN_TABLE_BITS, s->symbols_lists_array, s->symbol);
759
if (opt_table_size) {
760
*opt_table_size = table_size;
761
}
762
s->substate_huffman = BROTLI_STATE_HUFFMAN_NONE;
763
return BROTLI_DECODER_SUCCESS;
764
}
765
766
/* Decode Huffman-coded code lengths. */
767
case BROTLI_STATE_HUFFMAN_COMPLEX: {
768
uint32_t i;
769
BrotliDecoderErrorCode result = ReadCodeLengthCodeLengths(s);
770
if (result != BROTLI_DECODER_SUCCESS) {
771
return result;
772
}
773
BrotliBuildCodeLengthsHuffmanTable(s->table,
774
s->code_length_code_lengths,
775
s->code_length_histo);
776
memset(&s->code_length_histo[0], 0, sizeof(s->code_length_histo));
777
for (i = 0; i <= BROTLI_HUFFMAN_MAX_CODE_LENGTH; ++i) {
778
s->next_symbol[i] = (int)i - (BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1);
779
s->symbol_lists[s->next_symbol[i]] = 0xFFFF;
780
}
781
782
s->symbol = 0;
783
s->prev_code_len = BROTLI_INITIAL_REPEATED_CODE_LENGTH;
784
s->repeat = 0;
785
s->repeat_code_len = 0;
786
s->space = 32768;
787
s->substate_huffman = BROTLI_STATE_HUFFMAN_LENGTH_SYMBOLS;
788
/* No break, transit to the next state. */
789
}
790
case BROTLI_STATE_HUFFMAN_LENGTH_SYMBOLS: {
791
uint32_t table_size;
792
BrotliDecoderErrorCode result = ReadSymbolCodeLengths(alphabet_size, s);
793
if (result == BROTLI_DECODER_NEEDS_MORE_INPUT) {
794
result = SafeReadSymbolCodeLengths(alphabet_size, s);
795
}
796
if (result != BROTLI_DECODER_SUCCESS) {
797
return result;
798
}
799
800
if (s->space != 0) {
801
BROTLI_LOG(("[ReadHuffmanCode] space = %d\n", s->space));
802
return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_HUFFMAN_SPACE);
803
}
804
table_size = BrotliBuildHuffmanTable(
805
table, HUFFMAN_TABLE_BITS, s->symbol_lists, s->code_length_histo);
806
if (opt_table_size) {
807
*opt_table_size = table_size;
808
}
809
s->substate_huffman = BROTLI_STATE_HUFFMAN_NONE;
810
return BROTLI_DECODER_SUCCESS;
811
}
812
813
default:
814
return
815
BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE);
816
}
817
}
818
}
819
820
/* Decodes a block length by reading 3..39 bits. */
821
static BROTLI_INLINE uint32_t ReadBlockLength(const HuffmanCode* table,
822
BrotliBitReader* br) {
823
uint32_t code;
824
uint32_t nbits;
825
code = ReadSymbol(table, br);
826
nbits = kBlockLengthPrefixCode[code].nbits; /* nbits == 2..24 */
827
return kBlockLengthPrefixCode[code].offset + BrotliReadBits(br, nbits);
828
}
829
830
/* WARNING: if state is not BROTLI_STATE_READ_BLOCK_LENGTH_NONE, then
831
reading can't be continued with ReadBlockLength. */
832
static BROTLI_INLINE BROTLI_BOOL SafeReadBlockLength(
833
BrotliDecoderState* s, uint32_t* result, const HuffmanCode* table,
834
BrotliBitReader* br) {
835
uint32_t index;
836
if (s->substate_read_block_length == BROTLI_STATE_READ_BLOCK_LENGTH_NONE) {
837
if (!SafeReadSymbol(table, br, &index)) {
838
return BROTLI_FALSE;
839
}
840
} else {
841
index = s->block_length_index;
842
}
843
{
844
uint32_t bits;
845
uint32_t nbits = kBlockLengthPrefixCode[index].nbits; /* nbits == 2..24 */
846
if (!BrotliSafeReadBits(br, nbits, &bits)) {
847
s->block_length_index = index;
848
s->substate_read_block_length = BROTLI_STATE_READ_BLOCK_LENGTH_SUFFIX;
849
return BROTLI_FALSE;
850
}
851
*result = kBlockLengthPrefixCode[index].offset + bits;
852
s->substate_read_block_length = BROTLI_STATE_READ_BLOCK_LENGTH_NONE;
853
return BROTLI_TRUE;
854
}
855
}
856
857
/* Transform:
858
1) initialize list L with values 0, 1,... 255
859
2) For each input element X:
860
2.1) let Y = L[X]
861
2.2) remove X-th element from L
862
2.3) prepend Y to L
863
2.4) append Y to output
864
865
In most cases max(Y) <= 7, so most of L remains intact.
866
To reduce the cost of initialization, we reuse L, remember the upper bound
867
of Y values, and reinitialize only first elements in L.
868
869
Most of input values are 0 and 1. To reduce number of branches, we replace
870
inner for loop with do-while.
871
*/
872
static BROTLI_NOINLINE void InverseMoveToFrontTransform(
873
uint8_t* v, uint32_t v_len, BrotliDecoderState* state) {
874
/* Reinitialize elements that could have been changed. */
875
uint32_t i = 1;
876
uint32_t upper_bound = state->mtf_upper_bound;
877
uint32_t* mtf = &state->mtf[1]; /* Make mtf[-1] addressable. */
878
uint8_t* mtf_u8 = (uint8_t*)mtf;
879
/* Load endian-aware constant. */
880
const uint8_t b0123[4] = {0, 1, 2, 3};
881
uint32_t pattern;
882
memcpy(&pattern, &b0123, 4);
883
884
/* Initialize list using 4 consequent values pattern. */
885
mtf[0] = pattern;
886
do {
887
pattern += 0x04040404; /* Advance all 4 values by 4. */
888
mtf[i] = pattern;
889
i++;
890
} while (i <= upper_bound);
891
892
/* Transform the input. */
893
upper_bound = 0;
894
for (i = 0; i < v_len; ++i) {
895
int index = v[i];
896
uint8_t value = mtf_u8[index];
897
upper_bound |= v[i];
898
v[i] = value;
899
mtf_u8[-1] = value;
900
do {
901
index--;
902
mtf_u8[index + 1] = mtf_u8[index];
903
} while (index >= 0);
904
}
905
/* Remember amount of elements to be reinitialized. */
906
state->mtf_upper_bound = upper_bound >> 2;
907
}
908
909
/* Decodes a series of Huffman table using ReadHuffmanCode function. */
910
static BrotliDecoderErrorCode HuffmanTreeGroupDecode(
911
HuffmanTreeGroup* group, BrotliDecoderState* s) {
912
if (s->substate_tree_group != BROTLI_STATE_TREE_GROUP_LOOP) {
913
s->next = group->codes;
914
s->htree_index = 0;
915
s->substate_tree_group = BROTLI_STATE_TREE_GROUP_LOOP;
916
}
917
while (s->htree_index < group->num_htrees) {
918
uint32_t table_size;
919
BrotliDecoderErrorCode result =
920
ReadHuffmanCode(group->alphabet_size, s->next, &table_size, s);
921
if (result != BROTLI_DECODER_SUCCESS) return result;
922
group->htrees[s->htree_index] = s->next;
923
s->next += table_size;
924
++s->htree_index;
925
}
926
s->substate_tree_group = BROTLI_STATE_TREE_GROUP_NONE;
927
return BROTLI_DECODER_SUCCESS;
928
}
929
930
/* Decodes a context map.
931
Decoding is done in 4 phases:
932
1) Read auxiliary information (6..16 bits) and allocate memory.
933
In case of trivial context map, decoding is finished at this phase.
934
2) Decode Huffman table using ReadHuffmanCode function.
935
This table will be used for reading context map items.
936
3) Read context map items; "0" values could be run-length encoded.
937
4) Optionally, apply InverseMoveToFront transform to the resulting map.
938
*/
939
static BrotliDecoderErrorCode DecodeContextMap(uint32_t context_map_size,
940
uint32_t* num_htrees,
941
uint8_t** context_map_arg,
942
BrotliDecoderState* s) {
943
BrotliBitReader* br = &s->br;
944
BrotliDecoderErrorCode result = BROTLI_DECODER_SUCCESS;
945
946
switch ((int)s->substate_context_map) {
947
case BROTLI_STATE_CONTEXT_MAP_NONE:
948
result = DecodeVarLenUint8(s, br, num_htrees);
949
if (result != BROTLI_DECODER_SUCCESS) {
950
return result;
951
}
952
(*num_htrees)++;
953
s->context_index = 0;
954
BROTLI_LOG_UINT(context_map_size);
955
BROTLI_LOG_UINT(*num_htrees);
956
*context_map_arg = (uint8_t*)BROTLI_ALLOC(s, (size_t)context_map_size);
957
if (*context_map_arg == 0) {
958
return BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_CONTEXT_MAP);
959
}
960
if (*num_htrees <= 1) {
961
memset(*context_map_arg, 0, (size_t)context_map_size);
962
return BROTLI_DECODER_SUCCESS;
963
}
964
s->substate_context_map = BROTLI_STATE_CONTEXT_MAP_READ_PREFIX;
965
/* No break, continue to next state. */
966
case BROTLI_STATE_CONTEXT_MAP_READ_PREFIX: {
967
uint32_t bits;
968
/* In next stage ReadHuffmanCode uses at least 4 bits, so it is safe
969
to peek 4 bits ahead. */
970
if (!BrotliSafeGetBits(br, 5, &bits)) {
971
return BROTLI_DECODER_NEEDS_MORE_INPUT;
972
}
973
if ((bits & 1) != 0) { /* Use RLE for zeros. */
974
s->max_run_length_prefix = (bits >> 1) + 1;
975
BrotliDropBits(br, 5);
976
} else {
977
s->max_run_length_prefix = 0;
978
BrotliDropBits(br, 1);
979
}
980
BROTLI_LOG_UINT(s->max_run_length_prefix);
981
s->substate_context_map = BROTLI_STATE_CONTEXT_MAP_HUFFMAN;
982
/* No break, continue to next state. */
983
}
984
case BROTLI_STATE_CONTEXT_MAP_HUFFMAN:
985
result = ReadHuffmanCode(*num_htrees + s->max_run_length_prefix,
986
s->context_map_table, NULL, s);
987
if (result != BROTLI_DECODER_SUCCESS) return result;
988
s->code = 0xFFFF;
989
s->substate_context_map = BROTLI_STATE_CONTEXT_MAP_DECODE;
990
/* No break, continue to next state. */
991
case BROTLI_STATE_CONTEXT_MAP_DECODE: {
992
uint32_t context_index = s->context_index;
993
uint32_t max_run_length_prefix = s->max_run_length_prefix;
994
uint8_t* context_map = *context_map_arg;
995
uint32_t code = s->code;
996
BROTLI_BOOL skip_preamble = (code != 0xFFFF);
997
while (context_index < context_map_size || skip_preamble) {
998
if (!skip_preamble) {
999
if (!SafeReadSymbol(s->context_map_table, br, &code)) {
1000
s->code = 0xFFFF;
1001
s->context_index = context_index;
1002
return BROTLI_DECODER_NEEDS_MORE_INPUT;
1003
}
1004
BROTLI_LOG_UINT(code);
1005
1006
if (code == 0) {
1007
context_map[context_index++] = 0;
1008
continue;
1009
}
1010
if (code > max_run_length_prefix) {
1011
context_map[context_index++] =
1012
(uint8_t)(code - max_run_length_prefix);
1013
continue;
1014
}
1015
} else {
1016
skip_preamble = BROTLI_FALSE;
1017
}
1018
/* RLE sub-stage. */
1019
{
1020
uint32_t reps;
1021
if (!BrotliSafeReadBits(br, code, &reps)) {
1022
s->code = code;
1023
s->context_index = context_index;
1024
return BROTLI_DECODER_NEEDS_MORE_INPUT;
1025
}
1026
reps += 1U << code;
1027
BROTLI_LOG_UINT(reps);
1028
if (context_index + reps > context_map_size) {
1029
return
1030
BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_CONTEXT_MAP_REPEAT);
1031
}
1032
do {
1033
context_map[context_index++] = 0;
1034
} while (--reps);
1035
}
1036
}
1037
/* No break, continue to next state. */
1038
}
1039
case BROTLI_STATE_CONTEXT_MAP_TRANSFORM: {
1040
uint32_t bits;
1041
if (!BrotliSafeReadBits(br, 1, &bits)) {
1042
s->substate_context_map = BROTLI_STATE_CONTEXT_MAP_TRANSFORM;
1043
return BROTLI_DECODER_NEEDS_MORE_INPUT;
1044
}
1045
if (bits != 0) {
1046
InverseMoveToFrontTransform(*context_map_arg, context_map_size, s);
1047
}
1048
s->substate_context_map = BROTLI_STATE_CONTEXT_MAP_NONE;
1049
return BROTLI_DECODER_SUCCESS;
1050
}
1051
default:
1052
return
1053
BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE);
1054
}
1055
}
1056
1057
/* Decodes a command or literal and updates block type ring-buffer.
1058
Reads 3..54 bits. */
1059
static BROTLI_INLINE BROTLI_BOOL DecodeBlockTypeAndLength(
1060
int safe, BrotliDecoderState* s, int tree_type) {
1061
uint32_t max_block_type = s->num_block_types[tree_type];
1062
const HuffmanCode* type_tree = &s->block_type_trees[
1063
tree_type * BROTLI_HUFFMAN_MAX_SIZE_258];
1064
const HuffmanCode* len_tree = &s->block_len_trees[
1065
tree_type * BROTLI_HUFFMAN_MAX_SIZE_26];
1066
BrotliBitReader* br = &s->br;
1067
uint32_t* ringbuffer = &s->block_type_rb[tree_type * 2];
1068
uint32_t block_type;
1069
1070
/* Read 0..15 + 3..39 bits */
1071
if (!safe) {
1072
block_type = ReadSymbol(type_tree, br);
1073
s->block_length[tree_type] = ReadBlockLength(len_tree, br);
1074
} else {
1075
BrotliBitReaderState memento;
1076
BrotliBitReaderSaveState(br, &memento);
1077
if (!SafeReadSymbol(type_tree, br, &block_type)) return BROTLI_FALSE;
1078
if (!SafeReadBlockLength(s, &s->block_length[tree_type], len_tree, br)) {
1079
s->substate_read_block_length = BROTLI_STATE_READ_BLOCK_LENGTH_NONE;
1080
BrotliBitReaderRestoreState(br, &memento);
1081
return BROTLI_FALSE;
1082
}
1083
}
1084
1085
if (block_type == 1) {
1086
block_type = ringbuffer[1] + 1;
1087
} else if (block_type == 0) {
1088
block_type = ringbuffer[0];
1089
} else {
1090
block_type -= 2;
1091
}
1092
if (block_type >= max_block_type) {
1093
block_type -= max_block_type;
1094
}
1095
ringbuffer[0] = ringbuffer[1];
1096
ringbuffer[1] = block_type;
1097
return BROTLI_TRUE;
1098
}
1099
1100
static BROTLI_INLINE void DetectTrivialLiteralBlockTypes(
1101
BrotliDecoderState* s) {
1102
size_t i;
1103
for (i = 0; i < 8; ++i) s->trivial_literal_contexts[i] = 0;
1104
for (i = 0; i < s->num_block_types[0]; i++) {
1105
size_t offset = i << BROTLI_LITERAL_CONTEXT_BITS;
1106
size_t error = 0;
1107
size_t sample = s->context_map[offset];
1108
size_t j;
1109
for (j = 0; j < (1u << BROTLI_LITERAL_CONTEXT_BITS);) {
1110
BROTLI_REPEAT(4, error |= s->context_map[offset + j++] ^ sample;)
1111
}
1112
if (error == 0) {
1113
s->trivial_literal_contexts[i >> 5] |= 1u << (i & 31);
1114
}
1115
}
1116
}
1117
1118
static BROTLI_INLINE void PrepareLiteralDecoding(BrotliDecoderState* s) {
1119
uint8_t context_mode;
1120
size_t trivial;
1121
uint32_t block_type = s->block_type_rb[1];
1122
uint32_t context_offset = block_type << BROTLI_LITERAL_CONTEXT_BITS;
1123
s->context_map_slice = s->context_map + context_offset;
1124
trivial = s->trivial_literal_contexts[block_type >> 5];
1125
s->trivial_literal_context = (trivial >> (block_type & 31)) & 1;
1126
s->literal_htree = s->literal_hgroup.htrees[s->context_map_slice[0]];
1127
context_mode = s->context_modes[block_type];
1128
s->context_lookup1 = &kContextLookup[kContextLookupOffsets[context_mode]];
1129
s->context_lookup2 = &kContextLookup[kContextLookupOffsets[context_mode + 1]];
1130
}
1131
1132
/* Decodes the block type and updates the state for literal context.
1133
Reads 3..54 bits. */
1134
static BROTLI_INLINE BROTLI_BOOL DecodeLiteralBlockSwitchInternal(
1135
int safe, BrotliDecoderState* s) {
1136
if (!DecodeBlockTypeAndLength(safe, s, 0)) {
1137
return BROTLI_FALSE;
1138
}
1139
PrepareLiteralDecoding(s);
1140
return BROTLI_TRUE;
1141
}
1142
1143
static void BROTLI_NOINLINE DecodeLiteralBlockSwitch(BrotliDecoderState* s) {
1144
DecodeLiteralBlockSwitchInternal(0, s);
1145
}
1146
1147
static BROTLI_BOOL BROTLI_NOINLINE SafeDecodeLiteralBlockSwitch(
1148
BrotliDecoderState* s) {
1149
return DecodeLiteralBlockSwitchInternal(1, s);
1150
}
1151
1152
/* Block switch for insert/copy length.
1153
Reads 3..54 bits. */
1154
static BROTLI_INLINE BROTLI_BOOL DecodeCommandBlockSwitchInternal(
1155
int safe, BrotliDecoderState* s) {
1156
if (!DecodeBlockTypeAndLength(safe, s, 1)) {
1157
return BROTLI_FALSE;
1158
}
1159
s->htree_command = s->insert_copy_hgroup.htrees[s->block_type_rb[3]];
1160
return BROTLI_TRUE;
1161
}
1162
1163
static void BROTLI_NOINLINE DecodeCommandBlockSwitch(BrotliDecoderState* s) {
1164
DecodeCommandBlockSwitchInternal(0, s);
1165
}
1166
static BROTLI_BOOL BROTLI_NOINLINE SafeDecodeCommandBlockSwitch(
1167
BrotliDecoderState* s) {
1168
return DecodeCommandBlockSwitchInternal(1, s);
1169
}
1170
1171
/* Block switch for distance codes.
1172
Reads 3..54 bits. */
1173
static BROTLI_INLINE BROTLI_BOOL DecodeDistanceBlockSwitchInternal(
1174
int safe, BrotliDecoderState* s) {
1175
if (!DecodeBlockTypeAndLength(safe, s, 2)) {
1176
return BROTLI_FALSE;
1177
}
1178
s->dist_context_map_slice = s->dist_context_map +
1179
(s->block_type_rb[5] << BROTLI_DISTANCE_CONTEXT_BITS);
1180
s->dist_htree_index = s->dist_context_map_slice[s->distance_context];
1181
return BROTLI_TRUE;
1182
}
1183
1184
static void BROTLI_NOINLINE DecodeDistanceBlockSwitch(BrotliDecoderState* s) {
1185
DecodeDistanceBlockSwitchInternal(0, s);
1186
}
1187
1188
static BROTLI_BOOL BROTLI_NOINLINE SafeDecodeDistanceBlockSwitch(
1189
BrotliDecoderState* s) {
1190
return DecodeDistanceBlockSwitchInternal(1, s);
1191
}
1192
1193
static size_t UnwrittenBytes(const BrotliDecoderState* s, BROTLI_BOOL wrap) {
1194
size_t pos = wrap && s->pos > s->ringbuffer_size ?
1195
(size_t)s->ringbuffer_size : (size_t)(s->pos);
1196
size_t partial_pos_rb = (s->rb_roundtrips * (size_t)s->ringbuffer_size) + pos;
1197
return partial_pos_rb - s->partial_pos_out;
1198
}
1199
1200
/* Dumps output.
1201
Returns BROTLI_DECODER_NEEDS_MORE_OUTPUT only if there is more output to push
1202
and either ring-buffer is as big as window size, or |force| is true.
1203
*/
1204
static BrotliDecoderErrorCode BROTLI_NOINLINE WriteRingBuffer(
1205
BrotliDecoderState* s, size_t* available_out, uint8_t** next_out,
1206
size_t* total_out, BROTLI_BOOL force) {
1207
uint8_t* start =
1208
s->ringbuffer + (s->partial_pos_out & (size_t)s->ringbuffer_mask);
1209
size_t to_write = UnwrittenBytes(s, BROTLI_TRUE);
1210
size_t num_written = *available_out;
1211
if (num_written > to_write) {
1212
num_written = to_write;
1213
}
1214
if (s->meta_block_remaining_len < 0) {
1215
return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_BLOCK_LENGTH_1);
1216
}
1217
if (next_out && !*next_out) {
1218
*next_out = start;
1219
} else {
1220
if (next_out) {
1221
memcpy(*next_out, start, num_written);
1222
*next_out += num_written;
1223
}
1224
}
1225
*available_out -= num_written;
1226
BROTLI_LOG_UINT(to_write);
1227
BROTLI_LOG_UINT(num_written);
1228
s->partial_pos_out += num_written;
1229
if (total_out) {
1230
*total_out = s->partial_pos_out;
1231
}
1232
if (num_written < to_write) {
1233
if (s->ringbuffer_size == (1 << s->window_bits) || force) {
1234
return BROTLI_DECODER_NEEDS_MORE_OUTPUT;
1235
} else {
1236
return BROTLI_DECODER_SUCCESS;
1237
}
1238
}
1239
/* Wrap ring buffer only if it has reached its maximal size. */
1240
if (s->ringbuffer_size == (1 << s->window_bits) &&
1241
s->pos >= s->ringbuffer_size) {
1242
s->pos -= s->ringbuffer_size;
1243
s->rb_roundtrips++;
1244
s->should_wrap_ringbuffer = (size_t)s->pos != 0 ? 1 : 0;
1245
}
1246
return BROTLI_DECODER_SUCCESS;
1247
}
1248
1249
static void BROTLI_NOINLINE WrapRingBuffer(BrotliDecoderState* s) {
1250
if (s->should_wrap_ringbuffer) {
1251
memcpy(s->ringbuffer, s->ringbuffer_end, (size_t)s->pos);
1252
s->should_wrap_ringbuffer = 0;
1253
}
1254
}
1255
1256
/* Allocates ring-buffer.
1257
1258
s->ringbuffer_size MUST be updated by BrotliCalculateRingBufferSize before
1259
this function is called.
1260
1261
Last two bytes of ring-buffer are initialized to 0, so context calculation
1262
could be done uniformly for the first two and all other positions.
1263
*/
1264
static BROTLI_BOOL BROTLI_NOINLINE BrotliEnsureRingBuffer(
1265
BrotliDecoderState* s) {
1266
uint8_t* old_ringbuffer = s->ringbuffer;
1267
if (s->ringbuffer_size == s->new_ringbuffer_size) {
1268
return BROTLI_TRUE;
1269
}
1270
1271
s->ringbuffer = (uint8_t*)BROTLI_ALLOC(s, (size_t)(s->new_ringbuffer_size) +
1272
kRingBufferWriteAheadSlack);
1273
if (s->ringbuffer == 0) {
1274
/* Restore previous value. */
1275
s->ringbuffer = old_ringbuffer;
1276
return BROTLI_FALSE;
1277
}
1278
s->ringbuffer[s->new_ringbuffer_size - 2] = 0;
1279
s->ringbuffer[s->new_ringbuffer_size - 1] = 0;
1280
1281
if (!!old_ringbuffer) {
1282
memcpy(s->ringbuffer, old_ringbuffer, (size_t)s->pos);
1283
BROTLI_FREE(s, old_ringbuffer);
1284
}
1285
1286
s->ringbuffer_size = s->new_ringbuffer_size;
1287
s->ringbuffer_mask = s->new_ringbuffer_size - 1;
1288
s->ringbuffer_end = s->ringbuffer + s->ringbuffer_size;
1289
1290
return BROTLI_TRUE;
1291
}
1292
1293
static BrotliDecoderErrorCode BROTLI_NOINLINE CopyUncompressedBlockToOutput(
1294
size_t* available_out, uint8_t** next_out, size_t* total_out,
1295
BrotliDecoderState* s) {
1296
/* TODO: avoid allocation for single uncompressed block. */
1297
if (!BrotliEnsureRingBuffer(s)) {
1298
return BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_RING_BUFFER_1);
1299
}
1300
1301
/* State machine */
1302
for (;;) {
1303
switch (s->substate_uncompressed) {
1304
case BROTLI_STATE_UNCOMPRESSED_NONE: {
1305
int nbytes = (int)BrotliGetRemainingBytes(&s->br);
1306
if (nbytes > s->meta_block_remaining_len) {
1307
nbytes = s->meta_block_remaining_len;
1308
}
1309
if (s->pos + nbytes > s->ringbuffer_size) {
1310
nbytes = s->ringbuffer_size - s->pos;
1311
}
1312
/* Copy remaining bytes from s->br.buf_ to ring-buffer. */
1313
BrotliCopyBytes(&s->ringbuffer[s->pos], &s->br, (size_t)nbytes);
1314
s->pos += nbytes;
1315
s->meta_block_remaining_len -= nbytes;
1316
if (s->pos < 1 << s->window_bits) {
1317
if (s->meta_block_remaining_len == 0) {
1318
return BROTLI_DECODER_SUCCESS;
1319
}
1320
return BROTLI_DECODER_NEEDS_MORE_INPUT;
1321
}
1322
s->substate_uncompressed = BROTLI_STATE_UNCOMPRESSED_WRITE;
1323
/* No break, continue to next state */
1324
}
1325
case BROTLI_STATE_UNCOMPRESSED_WRITE: {
1326
BrotliDecoderErrorCode result;
1327
result = WriteRingBuffer(
1328
s, available_out, next_out, total_out, BROTLI_FALSE);
1329
if (result != BROTLI_DECODER_SUCCESS) {
1330
return result;
1331
}
1332
if (s->ringbuffer_size == 1 << s->window_bits) {
1333
s->max_distance = s->max_backward_distance;
1334
}
1335
s->substate_uncompressed = BROTLI_STATE_UNCOMPRESSED_NONE;
1336
break;
1337
}
1338
}
1339
}
1340
BROTLI_DCHECK(0); /* Unreachable */
1341
}
1342
1343
/* Calculates the smallest feasible ring buffer.
1344
1345
If we know the data size is small, do not allocate more ring buffer
1346
size than needed to reduce memory usage.
1347
1348
When this method is called, metablock size and flags MUST be decoded.
1349
*/
1350
static void BROTLI_NOINLINE BrotliCalculateRingBufferSize(
1351
BrotliDecoderState* s) {
1352
int window_size = 1 << s->window_bits;
1353
int new_ringbuffer_size = window_size;
1354
/* We need at least 2 bytes of ring buffer size to get the last two
1355
bytes for context from there */
1356
int min_size = s->ringbuffer_size ? s->ringbuffer_size : 1024;
1357
int output_size;
1358
1359
/* If maximum is already reached, no further extension is retired. */
1360
if (s->ringbuffer_size == window_size) {
1361
return;
1362
}
1363
1364
/* Metadata blocks does not touch ring buffer. */
1365
if (s->is_metadata) {
1366
return;
1367
}
1368
1369
if (!s->ringbuffer) {
1370
output_size = 0;
1371
} else {
1372
output_size = s->pos;
1373
}
1374
output_size += s->meta_block_remaining_len;
1375
min_size = min_size < output_size ? output_size : min_size;
1376
1377
if (!!s->canny_ringbuffer_allocation) {
1378
/* Reduce ring buffer size to save memory when server is unscrupulous.
1379
In worst case memory usage might be 1.5x bigger for a short period of
1380
ring buffer reallocation.*/
1381
while ((new_ringbuffer_size >> 1) >= min_size) {
1382
new_ringbuffer_size >>= 1;
1383
}
1384
}
1385
1386
s->new_ringbuffer_size = new_ringbuffer_size;
1387
}
1388
1389
/* Reads 1..256 2-bit context modes. */
1390
static BrotliDecoderErrorCode ReadContextModes(BrotliDecoderState* s) {
1391
BrotliBitReader* br = &s->br;
1392
int i = s->loop_counter;
1393
1394
while (i < (int)s->num_block_types[0]) {
1395
uint32_t bits;
1396
if (!BrotliSafeReadBits(br, 2, &bits)) {
1397
s->loop_counter = i;
1398
return BROTLI_DECODER_NEEDS_MORE_INPUT;
1399
}
1400
s->context_modes[i] = (uint8_t)(bits << 1);
1401
BROTLI_LOG_ARRAY_INDEX(s->context_modes, i);
1402
i++;
1403
}
1404
return BROTLI_DECODER_SUCCESS;
1405
}
1406
1407
static BROTLI_INLINE void TakeDistanceFromRingBuffer(BrotliDecoderState* s) {
1408
if (s->distance_code == 0) {
1409
--s->dist_rb_idx;
1410
s->distance_code = s->dist_rb[s->dist_rb_idx & 3];
1411
/* Compensate double distance-ring-buffer roll for dictionary items. */
1412
s->distance_context = 1;
1413
} else {
1414
int distance_code = s->distance_code << 1;
1415
/* kDistanceShortCodeIndexOffset has 2-bit values from LSB: */
1416
/* 3, 2, 1, 0, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2 */
1417
const uint32_t kDistanceShortCodeIndexOffset = 0xaaafff1b;
1418
/* kDistanceShortCodeValueOffset has 2-bit values from LSB: */
1419
/*-0, 0,-0, 0,-1, 1,-2, 2,-3, 3,-1, 1,-2, 2,-3, 3 */
1420
const uint32_t kDistanceShortCodeValueOffset = 0xfa5fa500;
1421
int v = (s->dist_rb_idx +
1422
(int)(kDistanceShortCodeIndexOffset >> distance_code)) & 0x3;
1423
s->distance_code = s->dist_rb[v];
1424
v = (int)(kDistanceShortCodeValueOffset >> distance_code) & 0x3;
1425
if ((distance_code & 0x3) != 0) {
1426
s->distance_code += v;
1427
} else {
1428
s->distance_code -= v;
1429
if (s->distance_code <= 0) {
1430
/* A huge distance will cause a BROTLI_FAILURE() soon. */
1431
/* This is a little faster than failing here. */
1432
s->distance_code = 0x0fffffff;
1433
}
1434
}
1435
}
1436
}
1437
1438
static BROTLI_INLINE BROTLI_BOOL SafeReadBits(
1439
BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) {
1440
if (n_bits != 0) {
1441
return BrotliSafeReadBits(br, n_bits, val);
1442
} else {
1443
*val = 0;
1444
return BROTLI_TRUE;
1445
}
1446
}
1447
1448
/* Precondition: s->distance_code < 0 */
1449
static BROTLI_INLINE BROTLI_BOOL ReadDistanceInternal(
1450
int safe, BrotliDecoderState* s, BrotliBitReader* br) {
1451
int distval;
1452
BrotliBitReaderState memento;
1453
HuffmanCode* distance_tree = s->distance_hgroup.htrees[s->dist_htree_index];
1454
if (!safe) {
1455
s->distance_code = (int)ReadSymbol(distance_tree, br);
1456
} else {
1457
uint32_t code;
1458
BrotliBitReaderSaveState(br, &memento);
1459
if (!SafeReadSymbol(distance_tree, br, &code)) {
1460
return BROTLI_FALSE;
1461
}
1462
s->distance_code = (int)code;
1463
}
1464
/* Convert the distance code to the actual distance by possibly */
1465
/* looking up past distances from the s->ringbuffer. */
1466
s->distance_context = 0;
1467
if ((s->distance_code & ~0xf) == 0) {
1468
TakeDistanceFromRingBuffer(s);
1469
--s->block_length[2];
1470
return BROTLI_TRUE;
1471
}
1472
distval = s->distance_code - (int)s->num_direct_distance_codes;
1473
if (distval >= 0) {
1474
uint32_t nbits;
1475
int postfix;
1476
int offset;
1477
if (!safe && (s->distance_postfix_bits == 0)) {
1478
nbits = ((uint32_t)distval >> 1) + 1;
1479
offset = ((2 + (distval & 1)) << nbits) - 4;
1480
s->distance_code = (int)s->num_direct_distance_codes + offset +
1481
(int)BrotliReadBits(br, nbits);
1482
} else {
1483
/* This branch also works well when s->distance_postfix_bits == 0 */
1484
uint32_t bits;
1485
postfix = distval & s->distance_postfix_mask;
1486
distval >>= s->distance_postfix_bits;
1487
nbits = ((uint32_t)distval >> 1) + 1;
1488
if (safe) {
1489
if (!SafeReadBits(br, nbits, &bits)) {
1490
s->distance_code = -1; /* Restore precondition. */
1491
BrotliBitReaderRestoreState(br, &memento);
1492
return BROTLI_FALSE;
1493
}
1494
} else {
1495
bits = BrotliReadBits(br, nbits);
1496
}
1497
offset = ((2 + (distval & 1)) << nbits) - 4;
1498
s->distance_code = (int)s->num_direct_distance_codes +
1499
((offset + (int)bits) << s->distance_postfix_bits) + postfix;
1500
}
1501
}
1502
s->distance_code = s->distance_code - BROTLI_NUM_DISTANCE_SHORT_CODES + 1;
1503
--s->block_length[2];
1504
return BROTLI_TRUE;
1505
}
1506
1507
static BROTLI_INLINE void ReadDistance(
1508
BrotliDecoderState* s, BrotliBitReader* br) {
1509
ReadDistanceInternal(0, s, br);
1510
}
1511
1512
static BROTLI_INLINE BROTLI_BOOL SafeReadDistance(
1513
BrotliDecoderState* s, BrotliBitReader* br) {
1514
return ReadDistanceInternal(1, s, br);
1515
}
1516
1517
static BROTLI_INLINE BROTLI_BOOL ReadCommandInternal(
1518
int safe, BrotliDecoderState* s, BrotliBitReader* br, int* insert_length) {
1519
uint32_t cmd_code;
1520
uint32_t insert_len_extra = 0;
1521
uint32_t copy_length;
1522
CmdLutElement v;
1523
BrotliBitReaderState memento;
1524
if (!safe) {
1525
cmd_code = ReadSymbol(s->htree_command, br);
1526
} else {
1527
BrotliBitReaderSaveState(br, &memento);
1528
if (!SafeReadSymbol(s->htree_command, br, &cmd_code)) {
1529
return BROTLI_FALSE;
1530
}
1531
}
1532
v = kCmdLut[cmd_code];
1533
s->distance_code = v.distance_code;
1534
s->distance_context = v.context;
1535
s->dist_htree_index = s->dist_context_map_slice[s->distance_context];
1536
*insert_length = v.insert_len_offset;
1537
if (!safe) {
1538
if (BROTLI_PREDICT_FALSE(v.insert_len_extra_bits != 0)) {
1539
insert_len_extra = BrotliReadBits(br, v.insert_len_extra_bits);
1540
}
1541
copy_length = BrotliReadBits(br, v.copy_len_extra_bits);
1542
} else {
1543
if (!SafeReadBits(br, v.insert_len_extra_bits, &insert_len_extra) ||
1544
!SafeReadBits(br, v.copy_len_extra_bits, ©_length)) {
1545
BrotliBitReaderRestoreState(br, &memento);
1546
return BROTLI_FALSE;
1547
}
1548
}
1549
s->copy_length = (int)copy_length + v.copy_len_offset;
1550
--s->block_length[1];
1551
*insert_length += (int)insert_len_extra;
1552
return BROTLI_TRUE;
1553
}
1554
1555
static BROTLI_INLINE void ReadCommand(
1556
BrotliDecoderState* s, BrotliBitReader* br, int* insert_length) {
1557
ReadCommandInternal(0, s, br, insert_length);
1558
}
1559
1560
static BROTLI_INLINE BROTLI_BOOL SafeReadCommand(
1561
BrotliDecoderState* s, BrotliBitReader* br, int* insert_length) {
1562
return ReadCommandInternal(1, s, br, insert_length);
1563
}
1564
1565
static BROTLI_INLINE BROTLI_BOOL CheckInputAmount(
1566
int safe, BrotliBitReader* const br, size_t num) {
1567
if (safe) {
1568
return BROTLI_TRUE;
1569
}
1570
return BrotliCheckInputAmount(br, num);
1571
}
1572
1573
#define BROTLI_SAFE(METHOD) \
1574
{ \
1575
if (safe) { \
1576
if (!Safe##METHOD) { \
1577
result = BROTLI_DECODER_NEEDS_MORE_INPUT; \
1578
goto saveStateAndReturn; \
1579
} \
1580
} else { \
1581
METHOD; \
1582
} \
1583
}
1584
1585
static BROTLI_INLINE BrotliDecoderErrorCode ProcessCommandsInternal(
1586
int safe, BrotliDecoderState* s) {
1587
int pos = s->pos;
1588
int i = s->loop_counter;
1589
BrotliDecoderErrorCode result = BROTLI_DECODER_SUCCESS;
1590
BrotliBitReader* br = &s->br;
1591
1592
if (!CheckInputAmount(safe, br, 28)) {
1593
result = BROTLI_DECODER_NEEDS_MORE_INPUT;
1594
goto saveStateAndReturn;
1595
}
1596
if (!safe) {
1597
BROTLI_UNUSED(BrotliWarmupBitReader(br));
1598
}
1599
1600
/* Jump into state machine. */
1601
if (s->state == BROTLI_STATE_COMMAND_BEGIN) {
1602
goto CommandBegin;
1603
} else if (s->state == BROTLI_STATE_COMMAND_INNER) {
1604
goto CommandInner;
1605
} else if (s->state == BROTLI_STATE_COMMAND_POST_DECODE_LITERALS) {
1606
goto CommandPostDecodeLiterals;
1607
} else if (s->state == BROTLI_STATE_COMMAND_POST_WRAP_COPY) {
1608
goto CommandPostWrapCopy;
1609
} else {
1610
return BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE);
1611
}
1612
1613
CommandBegin:
1614
if (safe) {
1615
s->state = BROTLI_STATE_COMMAND_BEGIN;
1616
}
1617
if (!CheckInputAmount(safe, br, 28)) { /* 156 bits + 7 bytes */
1618
s->state = BROTLI_STATE_COMMAND_BEGIN;
1619
result = BROTLI_DECODER_NEEDS_MORE_INPUT;
1620
goto saveStateAndReturn;
1621
}
1622
if (BROTLI_PREDICT_FALSE(s->block_length[1] == 0)) {
1623
BROTLI_SAFE(DecodeCommandBlockSwitch(s));
1624
goto CommandBegin;
1625
}
1626
/* Read the insert/copy length in the command */
1627
BROTLI_SAFE(ReadCommand(s, br, &i));
1628
BROTLI_LOG(("[ProcessCommandsInternal] pos = %d insert = %d copy = %d\n",
1629
pos, i, s->copy_length));
1630
if (i == 0) {
1631
goto CommandPostDecodeLiterals;
1632
}
1633
s->meta_block_remaining_len -= i;
1634
1635
CommandInner:
1636
if (safe) {
1637
s->state = BROTLI_STATE_COMMAND_INNER;
1638
}
1639
/* Read the literals in the command */
1640
if (s->trivial_literal_context) {
1641
uint32_t bits;
1642
uint32_t value;
1643
PreloadSymbol(safe, s->literal_htree, br, &bits, &value);
1644
do {
1645
if (!CheckInputAmount(safe, br, 28)) { /* 162 bits + 7 bytes */
1646
s->state = BROTLI_STATE_COMMAND_INNER;
1647
result = BROTLI_DECODER_NEEDS_MORE_INPUT;
1648
goto saveStateAndReturn;
1649
}
1650
if (BROTLI_PREDICT_FALSE(s->block_length[0] == 0)) {
1651
BROTLI_SAFE(DecodeLiteralBlockSwitch(s));
1652
PreloadSymbol(safe, s->literal_htree, br, &bits, &value);
1653
if (!s->trivial_literal_context) goto CommandInner;
1654
}
1655
if (!safe) {
1656
s->ringbuffer[pos] =
1657
(uint8_t)ReadPreloadedSymbol(s->literal_htree, br, &bits, &value);
1658
} else {
1659
uint32_t literal;
1660
if (!SafeReadSymbol(s->literal_htree, br, &literal)) {
1661
result = BROTLI_DECODER_NEEDS_MORE_INPUT;
1662
goto saveStateAndReturn;
1663
}
1664
s->ringbuffer[pos] = (uint8_t)literal;
1665
}
1666
--s->block_length[0];
1667
BROTLI_LOG_ARRAY_INDEX(s->ringbuffer, pos);
1668
++pos;
1669
if (BROTLI_PREDICT_FALSE(pos == s->ringbuffer_size)) {
1670
s->state = BROTLI_STATE_COMMAND_INNER_WRITE;
1671
--i;
1672
goto saveStateAndReturn;
1673
}
1674
} while (--i != 0);
1675
} else {
1676
uint8_t p1 = s->ringbuffer[(pos - 1) & s->ringbuffer_mask];
1677
uint8_t p2 = s->ringbuffer[(pos - 2) & s->ringbuffer_mask];
1678
do {
1679
const HuffmanCode* hc;
1680
uint8_t context;
1681
if (!CheckInputAmount(safe, br, 28)) { /* 162 bits + 7 bytes */
1682
s->state = BROTLI_STATE_COMMAND_INNER;
1683
result = BROTLI_DECODER_NEEDS_MORE_INPUT;
1684
goto saveStateAndReturn;
1685
}
1686
if (BROTLI_PREDICT_FALSE(s->block_length[0] == 0)) {
1687
BROTLI_SAFE(DecodeLiteralBlockSwitch(s));
1688
if (s->trivial_literal_context) goto CommandInner;
1689
}
1690
context = s->context_lookup1[p1] | s->context_lookup2[p2];
1691
BROTLI_LOG_UINT(context);
1692
hc = s->literal_hgroup.htrees[s->context_map_slice[context]];
1693
p2 = p1;
1694
if (!safe) {
1695
p1 = (uint8_t)ReadSymbol(hc, br);
1696
} else {
1697
uint32_t literal;
1698
if (!SafeReadSymbol(hc, br, &literal)) {
1699
result = BROTLI_DECODER_NEEDS_MORE_INPUT;
1700
goto saveStateAndReturn;
1701
}
1702
p1 = (uint8_t)literal;
1703
}
1704
s->ringbuffer[pos] = p1;
1705
--s->block_length[0];
1706
BROTLI_LOG_UINT(s->context_map_slice[context]);
1707
BROTLI_LOG_ARRAY_INDEX(s->ringbuffer, pos & s->ringbuffer_mask);
1708
++pos;
1709
if (BROTLI_PREDICT_FALSE(pos == s->ringbuffer_size)) {
1710
s->state = BROTLI_STATE_COMMAND_INNER_WRITE;
1711
--i;
1712
goto saveStateAndReturn;
1713
}
1714
} while (--i != 0);
1715
}
1716
BROTLI_LOG_UINT(s->meta_block_remaining_len);
1717
if (BROTLI_PREDICT_FALSE(s->meta_block_remaining_len <= 0)) {
1718
s->state = BROTLI_STATE_METABLOCK_DONE;
1719
goto saveStateAndReturn;
1720
}
1721
1722
CommandPostDecodeLiterals:
1723
if (safe) {
1724
s->state = BROTLI_STATE_COMMAND_POST_DECODE_LITERALS;
1725
}
1726
if (s->distance_code >= 0) {
1727
/* Implicit distance case. */
1728
s->distance_context = s->distance_code ? 0 : 1;
1729
--s->dist_rb_idx;
1730
s->distance_code = s->dist_rb[s->dist_rb_idx & 3];
1731
} else {
1732
/* Read distance code in the command, unless it was implicitly zero. */
1733
if (BROTLI_PREDICT_FALSE(s->block_length[2] == 0)) {
1734
BROTLI_SAFE(DecodeDistanceBlockSwitch(s));
1735
}
1736
BROTLI_SAFE(ReadDistance(s, br));
1737
}
1738
BROTLI_LOG(("[ProcessCommandsInternal] pos = %d distance = %d\n",
1739
pos, s->distance_code));
1740
if (s->max_distance != s->max_backward_distance) {
1741
s->max_distance =
1742
(pos < s->max_backward_distance) ? pos : s->max_backward_distance;
1743
}
1744
i = s->copy_length;
1745
/* Apply copy of LZ77 back-reference, or static dictionary reference if
1746
the distance is larger than the max LZ77 distance */
1747
if (s->distance_code > s->max_distance) {
1748
int address = s->distance_code - s->max_distance - 1;
1749
if (i >= BROTLI_MIN_DICTIONARY_WORD_LENGTH &&
1750
i <= BROTLI_MAX_DICTIONARY_WORD_LENGTH) {
1751
int offset = (int)s->dictionary->offsets_by_length[i];
1752
uint32_t shift = s->dictionary->size_bits_by_length[i];
1753
int mask = (int)BitMask(shift);
1754
int word_idx = address & mask;
1755
int transform_idx = address >> shift;
1756
/* Compensate double distance-ring-buffer roll. */
1757
s->dist_rb_idx += s->distance_context;
1758
offset += word_idx * i;
1759
if (BROTLI_PREDICT_FALSE(!s->dictionary->data)) {
1760
return BROTLI_FAILURE(BROTLI_DECODER_ERROR_DICTIONARY_NOT_SET);
1761
}
1762
if (transform_idx < kNumTransforms) {
1763
const uint8_t* word = &s->dictionary->data[offset];
1764
int len = i;
1765
if (transform_idx == 0) {
1766
memcpy(&s->ringbuffer[pos], word, (size_t)len);
1767
BROTLI_LOG(("[ProcessCommandsInternal] dictionary word: [%.*s]\n",
1768
len, word));
1769
} else {
1770
len = TransformDictionaryWord(
1771
&s->ringbuffer[pos], word, len, transform_idx);
1772
BROTLI_LOG(("[ProcessCommandsInternal] dictionary word: [%.*s],"
1773
" transform_idx = %d, transformed: [%.*s]\n",
1774
i, word, transform_idx, len, &s->ringbuffer[pos]));
1775
}
1776
pos += len;
1777
s->meta_block_remaining_len -= len;
1778
if (pos >= s->ringbuffer_size) {
1779
/*s->partial_pos_rb += (size_t)s->ringbuffer_size;*/
1780
s->state = BROTLI_STATE_COMMAND_POST_WRITE_1;
1781
goto saveStateAndReturn;
1782
}
1783
} else {
1784
BROTLI_LOG(("Invalid backward reference. pos: %d distance: %d "
1785
"len: %d bytes left: %d\n",
1786
pos, s->distance_code, i, s->meta_block_remaining_len));
1787
return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_TRANSFORM);
1788
}
1789
} else {
1790
BROTLI_LOG(("Invalid backward reference. pos: %d distance: %d "
1791
"len: %d bytes left: %d\n",
1792
pos, s->distance_code, i, s->meta_block_remaining_len));
1793
return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_DICTIONARY);
1794
}
1795
} else {
1796
int src_start = (pos - s->distance_code) & s->ringbuffer_mask;
1797
uint8_t* copy_dst = &s->ringbuffer[pos];
1798
uint8_t* copy_src = &s->ringbuffer[src_start];
1799
int dst_end = pos + i;
1800
int src_end = src_start + i;
1801
/* update the recent distances cache */
1802
s->dist_rb[s->dist_rb_idx & 3] = s->distance_code;
1803
++s->dist_rb_idx;
1804
s->meta_block_remaining_len -= i;
1805
/* There are 32+ bytes of slack in the ring-buffer allocation.
1806
Also, we have 16 short codes, that make these 16 bytes irrelevant
1807
in the ring-buffer. Let's copy over them as a first guess.
1808
*/
1809
memmove16(copy_dst, copy_src);
1810
if (src_end > pos && dst_end > src_start) {
1811
/* Regions intersect. */
1812
goto CommandPostWrapCopy;
1813
}
1814
if (dst_end >= s->ringbuffer_size || src_end >= s->ringbuffer_size) {
1815
/* At least one region wraps. */
1816
goto CommandPostWrapCopy;
1817
}
1818
pos += i;
1819
if (i > 16) {
1820
if (i > 32) {
1821
memcpy(copy_dst + 16, copy_src + 16, (size_t)(i - 16));
1822
} else {
1823
/* This branch covers about 45% cases.
1824
Fixed size short copy allows more compiler optimizations. */
1825
memmove16(copy_dst + 16, copy_src + 16);
1826
}
1827
}
1828
}
1829
BROTLI_LOG_UINT(s->meta_block_remaining_len);
1830
if (s->meta_block_remaining_len <= 0) {
1831
/* Next metablock, if any */
1832
s->state = BROTLI_STATE_METABLOCK_DONE;
1833
goto saveStateAndReturn;
1834
} else {
1835
goto CommandBegin;
1836
}
1837
CommandPostWrapCopy:
1838
{
1839
int wrap_guard = s->ringbuffer_size - pos;
1840
while (--i >= 0) {
1841
s->ringbuffer[pos] =
1842
s->ringbuffer[(pos - s->distance_code) & s->ringbuffer_mask];
1843
++pos;
1844
if (BROTLI_PREDICT_FALSE(--wrap_guard == 0)) {
1845
s->state = BROTLI_STATE_COMMAND_POST_WRITE_2;
1846
goto saveStateAndReturn;
1847
}
1848
}
1849
}
1850
if (s->meta_block_remaining_len <= 0) {
1851
/* Next metablock, if any */
1852
s->state = BROTLI_STATE_METABLOCK_DONE;
1853
goto saveStateAndReturn;
1854
} else {
1855
goto CommandBegin;
1856
}
1857
1858
saveStateAndReturn:
1859
s->pos = pos;
1860
s->loop_counter = i;
1861
return result;
1862
}
1863
1864
#undef BROTLI_SAFE
1865
1866
static BROTLI_NOINLINE BrotliDecoderErrorCode ProcessCommands(
1867
BrotliDecoderState* s) {
1868
return ProcessCommandsInternal(0, s);
1869
}
1870
1871
static BROTLI_NOINLINE BrotliDecoderErrorCode SafeProcessCommands(
1872
BrotliDecoderState* s) {
1873
return ProcessCommandsInternal(1, s);
1874
}
1875
1876
BrotliDecoderResult BrotliDecoderDecompress(
1877
size_t encoded_size, const uint8_t* encoded_buffer, size_t* decoded_size,
1878
uint8_t* decoded_buffer) {
1879
BrotliDecoderState s;
1880
BrotliDecoderResult result;
1881
size_t total_out = 0;
1882
size_t available_in = encoded_size;
1883
const uint8_t* next_in = encoded_buffer;
1884
size_t available_out = *decoded_size;
1885
uint8_t* next_out = decoded_buffer;
1886
BrotliDecoderStateInit(&s);
1887
result = BrotliDecoderDecompressStream(
1888
&s, &available_in, &next_in, &available_out, &next_out, &total_out);
1889
*decoded_size = total_out;
1890
BrotliDecoderStateCleanup(&s);
1891
if (result != BROTLI_DECODER_RESULT_SUCCESS) {
1892
result = BROTLI_DECODER_RESULT_ERROR;
1893
}
1894
return result;
1895
}
1896
1897
/* Invariant: input stream is never overconsumed:
1898
* invalid input implies that the whole stream is invalid -> any amount of
1899
input could be read and discarded
1900
* when result is "needs more input", then at least one more byte is REQUIRED
1901
to complete decoding; all input data MUST be consumed by decoder, so
1902
client could swap the input buffer
1903
* when result is "needs more output" decoder MUST ensure that it doesn't
1904
hold more than 7 bits in bit reader; this saves client from swapping input
1905
buffer ahead of time
1906
* when result is "success" decoder MUST return all unused data back to input
1907
buffer; this is possible because the invariant is hold on enter
1908
*/
1909
BrotliDecoderResult BrotliDecoderDecompressStream(
1910
BrotliDecoderState* s, size_t* available_in, const uint8_t** next_in,
1911
size_t* available_out, uint8_t** next_out, size_t* total_out) {
1912
BrotliDecoderErrorCode result = BROTLI_DECODER_SUCCESS;
1913
BrotliBitReader* br = &s->br;
1914
/* Ensure that *total_out is set, even if no data will ever be pushed out. */
1915
if (total_out) {
1916
*total_out = s->partial_pos_out;
1917
}
1918
/* Do not try to process further in a case of unrecoverable error. */
1919
if ((int)s->error_code < 0) {
1920
return BROTLI_DECODER_RESULT_ERROR;
1921
}
1922
if (*available_out && (!next_out || !*next_out)) {
1923
return SaveErrorCode(
1924
s, BROTLI_FAILURE(BROTLI_DECODER_ERROR_INVALID_ARGUMENTS));
1925
}
1926
if (!*available_out) next_out = 0;
1927
if (s->buffer_length == 0) { /* Just connect bit reader to input stream. */
1928
br->avail_in = *available_in;
1929
br->next_in = *next_in;
1930
} else {
1931
/* At least one byte of input is required. More than one byte of input may
1932
be required to complete the transaction -> reading more data must be
1933
done in a loop -> do it in a main loop. */
1934
result = BROTLI_DECODER_NEEDS_MORE_INPUT;
1935
br->next_in = &s->buffer.u8[0];
1936
}
1937
/* State machine */
1938
for (;;) {
1939
if (result != BROTLI_DECODER_SUCCESS) { /* Error, needs more input/output */
1940
if (result == BROTLI_DECODER_NEEDS_MORE_INPUT) {
1941
if (s->ringbuffer != 0) { /* Pro-actively push output. */
1942
BrotliDecoderErrorCode intermediate_result = WriteRingBuffer(s,
1943
available_out, next_out, total_out, BROTLI_TRUE);
1944
/* WriteRingBuffer checks s->meta_block_remaining_len validity. */
1945
if ((int)intermediate_result < 0) {
1946
result = intermediate_result;
1947
break;
1948
}
1949
}
1950
if (s->buffer_length != 0) { /* Used with internal buffer. */
1951
if (br->avail_in == 0) { /* Successfully finished read transaction. */
1952
/* Accumulator contains less than 8 bits, because internal buffer
1953
is expanded byte-by-byte until it is enough to complete read. */
1954
s->buffer_length = 0;
1955
/* Switch to input stream and restart. */
1956
result = BROTLI_DECODER_SUCCESS;
1957
br->avail_in = *available_in;
1958
br->next_in = *next_in;
1959
continue;
1960
} else if (*available_in != 0) {
1961
/* Not enough data in buffer, but can take one more byte from
1962
input stream. */
1963
result = BROTLI_DECODER_SUCCESS;
1964
s->buffer.u8[s->buffer_length] = **next_in;
1965
s->buffer_length++;
1966
br->avail_in = s->buffer_length;
1967
(*next_in)++;
1968
(*available_in)--;
1969
/* Retry with more data in buffer. */
1970
continue;
1971
}
1972
/* Can't finish reading and no more input.*/
1973
break;
1974
} else { /* Input stream doesn't contain enough input. */
1975
/* Copy tail to internal buffer and return. */
1976
*next_in = br->next_in;
1977
*available_in = br->avail_in;
1978
while (*available_in) {
1979
s->buffer.u8[s->buffer_length] = **next_in;
1980
s->buffer_length++;
1981
(*next_in)++;
1982
(*available_in)--;
1983
}
1984
break;
1985
}
1986
/* Unreachable. */
1987
}
1988
1989
/* Fail or needs more output. */
1990
1991
if (s->buffer_length != 0) {
1992
/* Just consumed the buffered input and produced some output. Otherwise
1993
it would result in "needs more input". Reset internal buffer.*/
1994
s->buffer_length = 0;
1995
} else {
1996
/* Using input stream in last iteration. When decoder switches to input
1997
stream it has less than 8 bits in accumulator, so it is safe to
1998
return unused accumulator bits there. */
1999
BrotliBitReaderUnload(br);
2000
*available_in = br->avail_in;
2001
*next_in = br->next_in;
2002
}
2003
break;
2004
}
2005
switch (s->state) {
2006
case BROTLI_STATE_UNINITED:
2007
/* Prepare to the first read. */
2008
if (!BrotliWarmupBitReader(br)) {
2009
result = BROTLI_DECODER_NEEDS_MORE_INPUT;
2010
break;
2011
}
2012
/* Decode window size. */
2013
s->window_bits = DecodeWindowBits(br); /* Reads 1..7 bits. */
2014
BROTLI_LOG_UINT(s->window_bits);
2015
if (s->window_bits == 9) {
2016
/* Value 9 is reserved for future use. */
2017
result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_WINDOW_BITS);
2018
break;
2019
}
2020
/* Maximum distance, see section 9.1. of the spec. */
2021
s->max_backward_distance = (1 << s->window_bits) - BROTLI_WINDOW_GAP;
2022
2023
/* Allocate memory for both block_type_trees and block_len_trees. */
2024
s->block_type_trees = (HuffmanCode*)BROTLI_ALLOC(s,
2025
sizeof(HuffmanCode) * 3 *
2026
(BROTLI_HUFFMAN_MAX_SIZE_258 + BROTLI_HUFFMAN_MAX_SIZE_26));
2027
if (s->block_type_trees == 0) {
2028
result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_BLOCK_TYPE_TREES);
2029
break;
2030
}
2031
s->block_len_trees =
2032
s->block_type_trees + 3 * BROTLI_HUFFMAN_MAX_SIZE_258;
2033
2034
s->state = BROTLI_STATE_METABLOCK_BEGIN;
2035
/* No break, continue to next state */
2036
case BROTLI_STATE_METABLOCK_BEGIN:
2037
BrotliDecoderStateMetablockBegin(s);
2038
BROTLI_LOG_UINT(s->pos);
2039
s->state = BROTLI_STATE_METABLOCK_HEADER;
2040
/* No break, continue to next state */
2041
case BROTLI_STATE_METABLOCK_HEADER:
2042
result = DecodeMetaBlockLength(s, br); /* Reads 2 - 31 bits. */
2043
if (result != BROTLI_DECODER_SUCCESS) {
2044
break;
2045
}
2046
BROTLI_LOG_UINT(s->is_last_metablock);
2047
BROTLI_LOG_UINT(s->meta_block_remaining_len);
2048
BROTLI_LOG_UINT(s->is_metadata);
2049
BROTLI_LOG_UINT(s->is_uncompressed);
2050
if (s->is_metadata || s->is_uncompressed) {
2051
if (!BrotliJumpToByteBoundary(br)) {
2052
result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_PADDING_1);
2053
break;
2054
}
2055
}
2056
if (s->is_metadata) {
2057
s->state = BROTLI_STATE_METADATA;
2058
break;
2059
}
2060
if (s->meta_block_remaining_len == 0) {
2061
s->state = BROTLI_STATE_METABLOCK_DONE;
2062
break;
2063
}
2064
BrotliCalculateRingBufferSize(s);
2065
if (s->is_uncompressed) {
2066
s->state = BROTLI_STATE_UNCOMPRESSED;
2067
break;
2068
}
2069
s->loop_counter = 0;
2070
s->state = BROTLI_STATE_HUFFMAN_CODE_0;
2071
break;
2072
case BROTLI_STATE_UNCOMPRESSED: {
2073
result = CopyUncompressedBlockToOutput(
2074
available_out, next_out, total_out, s);
2075
if (result != BROTLI_DECODER_SUCCESS) {
2076
break;
2077
}
2078
s->state = BROTLI_STATE_METABLOCK_DONE;
2079
break;
2080
}
2081
case BROTLI_STATE_METADATA:
2082
for (; s->meta_block_remaining_len > 0; --s->meta_block_remaining_len) {
2083
uint32_t bits;
2084
/* Read one byte and ignore it. */
2085
if (!BrotliSafeReadBits(br, 8, &bits)) {
2086
result = BROTLI_DECODER_NEEDS_MORE_INPUT;
2087
break;
2088
}
2089
}
2090
if (result == BROTLI_DECODER_SUCCESS) {
2091
s->state = BROTLI_STATE_METABLOCK_DONE;
2092
}
2093
break;
2094
case BROTLI_STATE_HUFFMAN_CODE_0:
2095
if (s->loop_counter >= 3) {
2096
s->state = BROTLI_STATE_METABLOCK_HEADER_2;
2097
break;
2098
}
2099
/* Reads 1..11 bits. */
2100
result = DecodeVarLenUint8(s, br, &s->num_block_types[s->loop_counter]);
2101
if (result != BROTLI_DECODER_SUCCESS) {
2102
break;
2103
}
2104
s->num_block_types[s->loop_counter]++;
2105
BROTLI_LOG_UINT(s->num_block_types[s->loop_counter]);
2106
if (s->num_block_types[s->loop_counter] < 2) {
2107
s->loop_counter++;
2108
break;
2109
}
2110
s->state = BROTLI_STATE_HUFFMAN_CODE_1;
2111
/* No break, continue to next state */
2112
case BROTLI_STATE_HUFFMAN_CODE_1: {
2113
int tree_offset = s->loop_counter * BROTLI_HUFFMAN_MAX_SIZE_258;
2114
result = ReadHuffmanCode(s->num_block_types[s->loop_counter] + 2,
2115
&s->block_type_trees[tree_offset], NULL, s);
2116
if (result != BROTLI_DECODER_SUCCESS) break;
2117
s->state = BROTLI_STATE_HUFFMAN_CODE_2;
2118
/* No break, continue to next state */
2119
}
2120
case BROTLI_STATE_HUFFMAN_CODE_2: {
2121
int tree_offset = s->loop_counter * BROTLI_HUFFMAN_MAX_SIZE_26;
2122
result = ReadHuffmanCode(BROTLI_NUM_BLOCK_LEN_SYMBOLS,
2123
&s->block_len_trees[tree_offset], NULL, s);
2124
if (result != BROTLI_DECODER_SUCCESS) break;
2125
s->state = BROTLI_STATE_HUFFMAN_CODE_3;
2126
/* No break, continue to next state */
2127
}
2128
case BROTLI_STATE_HUFFMAN_CODE_3: {
2129
int tree_offset = s->loop_counter * BROTLI_HUFFMAN_MAX_SIZE_26;
2130
if (!SafeReadBlockLength(s, &s->block_length[s->loop_counter],
2131
&s->block_len_trees[tree_offset], br)) {
2132
result = BROTLI_DECODER_NEEDS_MORE_INPUT;
2133
break;
2134
}
2135
BROTLI_LOG_UINT(s->block_length[s->loop_counter]);
2136
s->loop_counter++;
2137
s->state = BROTLI_STATE_HUFFMAN_CODE_0;
2138
break;
2139
}
2140
case BROTLI_STATE_METABLOCK_HEADER_2: {
2141
uint32_t bits;
2142
if (!BrotliSafeReadBits(br, 6, &bits)) {
2143
result = BROTLI_DECODER_NEEDS_MORE_INPUT;
2144
break;
2145
}
2146
s->distance_postfix_bits = bits & BitMask(2);
2147
bits >>= 2;
2148
s->num_direct_distance_codes = BROTLI_NUM_DISTANCE_SHORT_CODES +
2149
(bits << s->distance_postfix_bits);
2150
BROTLI_LOG_UINT(s->num_direct_distance_codes);
2151
BROTLI_LOG_UINT(s->distance_postfix_bits);
2152
s->distance_postfix_mask = (int)BitMask(s->distance_postfix_bits);
2153
s->context_modes =
2154
(uint8_t*)BROTLI_ALLOC(s, (size_t)s->num_block_types[0]);
2155
if (s->context_modes == 0) {
2156
result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_CONTEXT_MODES);
2157
break;
2158
}
2159
s->loop_counter = 0;
2160
s->state = BROTLI_STATE_CONTEXT_MODES;
2161
/* No break, continue to next state */
2162
}
2163
case BROTLI_STATE_CONTEXT_MODES:
2164
result = ReadContextModes(s);
2165
if (result != BROTLI_DECODER_SUCCESS) {
2166
break;
2167
}
2168
s->state = BROTLI_STATE_CONTEXT_MAP_1;
2169
/* No break, continue to next state */
2170
case BROTLI_STATE_CONTEXT_MAP_1:
2171
result = DecodeContextMap(
2172
s->num_block_types[0] << BROTLI_LITERAL_CONTEXT_BITS,
2173
&s->num_literal_htrees, &s->context_map, s);
2174
if (result != BROTLI_DECODER_SUCCESS) {
2175
break;
2176
}
2177
DetectTrivialLiteralBlockTypes(s);
2178
s->state = BROTLI_STATE_CONTEXT_MAP_2;
2179
/* No break, continue to next state */
2180
case BROTLI_STATE_CONTEXT_MAP_2:
2181
{
2182
uint32_t num_distance_codes = s->num_direct_distance_codes +
2183
((2 * BROTLI_MAX_DISTANCE_BITS) << s->distance_postfix_bits);
2184
BROTLI_BOOL allocation_success = BROTLI_TRUE;
2185
result = DecodeContextMap(
2186
s->num_block_types[2] << BROTLI_DISTANCE_CONTEXT_BITS,
2187
&s->num_dist_htrees, &s->dist_context_map, s);
2188
if (result != BROTLI_DECODER_SUCCESS) {
2189
break;
2190
}
2191
allocation_success &= BrotliDecoderHuffmanTreeGroupInit(
2192
s, &s->literal_hgroup, BROTLI_NUM_LITERAL_SYMBOLS,
2193
s->num_literal_htrees);
2194
allocation_success &= BrotliDecoderHuffmanTreeGroupInit(
2195
s, &s->insert_copy_hgroup, BROTLI_NUM_COMMAND_SYMBOLS,
2196
s->num_block_types[1]);
2197
allocation_success &= BrotliDecoderHuffmanTreeGroupInit(
2198
s, &s->distance_hgroup, num_distance_codes,
2199
s->num_dist_htrees);
2200
if (!allocation_success) {
2201
return SaveErrorCode(s,
2202
BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_TREE_GROUPS));
2203
}
2204
}
2205
s->loop_counter = 0;
2206
s->state = BROTLI_STATE_TREE_GROUP;
2207
/* No break, continue to next state */
2208
case BROTLI_STATE_TREE_GROUP:
2209
{
2210
HuffmanTreeGroup* hgroup = NULL;
2211
switch (s->loop_counter) {
2212
case 0:
2213
hgroup = &s->literal_hgroup;
2214
break;
2215
case 1:
2216
hgroup = &s->insert_copy_hgroup;
2217
break;
2218
case 2:
2219
hgroup = &s->distance_hgroup;
2220
break;
2221
default:
2222
return SaveErrorCode(s, BROTLI_FAILURE(
2223
BROTLI_DECODER_ERROR_UNREACHABLE));
2224
}
2225
result = HuffmanTreeGroupDecode(hgroup, s);
2226
}
2227
if (result != BROTLI_DECODER_SUCCESS) break;
2228
s->loop_counter++;
2229
if (s->loop_counter >= 3) {
2230
PrepareLiteralDecoding(s);
2231
s->dist_context_map_slice = s->dist_context_map;
2232
s->htree_command = s->insert_copy_hgroup.htrees[0];
2233
if (!BrotliEnsureRingBuffer(s)) {
2234
result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_RING_BUFFER_2);
2235
break;
2236
}
2237
s->state = BROTLI_STATE_COMMAND_BEGIN;
2238
}
2239
break;
2240
case BROTLI_STATE_COMMAND_BEGIN:
2241
case BROTLI_STATE_COMMAND_INNER:
2242
case BROTLI_STATE_COMMAND_POST_DECODE_LITERALS:
2243
case BROTLI_STATE_COMMAND_POST_WRAP_COPY:
2244
result = ProcessCommands(s);
2245
if (result == BROTLI_DECODER_NEEDS_MORE_INPUT) {
2246
result = SafeProcessCommands(s);
2247
}
2248
break;
2249
case BROTLI_STATE_COMMAND_INNER_WRITE:
2250
case BROTLI_STATE_COMMAND_POST_WRITE_1:
2251
case BROTLI_STATE_COMMAND_POST_WRITE_2:
2252
result = WriteRingBuffer(
2253
s, available_out, next_out, total_out, BROTLI_FALSE);
2254
if (result != BROTLI_DECODER_SUCCESS) {
2255
break;
2256
}
2257
WrapRingBuffer(s);
2258
if (s->ringbuffer_size == 1 << s->window_bits) {
2259
s->max_distance = s->max_backward_distance;
2260
}
2261
if (s->state == BROTLI_STATE_COMMAND_POST_WRITE_1) {
2262
if (s->meta_block_remaining_len == 0) {
2263
/* Next metablock, if any */
2264
s->state = BROTLI_STATE_METABLOCK_DONE;
2265
} else {
2266
s->state = BROTLI_STATE_COMMAND_BEGIN;
2267
}
2268
break;
2269
} else if (s->state == BROTLI_STATE_COMMAND_POST_WRITE_2) {
2270
s->state = BROTLI_STATE_COMMAND_POST_WRAP_COPY;
2271
} else { /* BROTLI_STATE_COMMAND_INNER_WRITE */
2272
if (s->loop_counter == 0) {
2273
if (s->meta_block_remaining_len == 0) {
2274
s->state = BROTLI_STATE_METABLOCK_DONE;
2275
} else {
2276
s->state = BROTLI_STATE_COMMAND_POST_DECODE_LITERALS;
2277
}
2278
break;
2279
}
2280
s->state = BROTLI_STATE_COMMAND_INNER;
2281
}
2282
break;
2283
case BROTLI_STATE_METABLOCK_DONE:
2284
if (s->meta_block_remaining_len < 0) {
2285
result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_BLOCK_LENGTH_2);
2286
break;
2287
}
2288
BrotliDecoderStateCleanupAfterMetablock(s);
2289
if (!s->is_last_metablock) {
2290
s->state = BROTLI_STATE_METABLOCK_BEGIN;
2291
break;
2292
}
2293
if (!BrotliJumpToByteBoundary(br)) {
2294
result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_PADDING_2);
2295
break;
2296
}
2297
if (s->buffer_length == 0) {
2298
BrotliBitReaderUnload(br);
2299
*available_in = br->avail_in;
2300
*next_in = br->next_in;
2301
}
2302
s->state = BROTLI_STATE_DONE;
2303
/* No break, continue to next state */
2304
case BROTLI_STATE_DONE:
2305
if (s->ringbuffer != 0) {
2306
result = WriteRingBuffer(
2307
s, available_out, next_out, total_out, BROTLI_TRUE);
2308
if (result != BROTLI_DECODER_SUCCESS) {
2309
break;
2310
}
2311
}
2312
return SaveErrorCode(s, result);
2313
}
2314
}
2315
return SaveErrorCode(s, result);
2316
}
2317
2318
BROTLI_BOOL BrotliDecoderHasMoreOutput(const BrotliDecoderState* s) {
2319
/* After unrecoverable error remaining output is considered nonsensical. */
2320
if ((int)s->error_code < 0) {
2321
return BROTLI_FALSE;
2322
}
2323
return TO_BROTLI_BOOL(
2324
s->ringbuffer != 0 && UnwrittenBytes(s, BROTLI_FALSE) != 0);
2325
}
2326
2327
const uint8_t* BrotliDecoderTakeOutput(BrotliDecoderState* s, size_t* size) {
2328
uint8_t* result = 0;
2329
size_t available_out = *size ? *size : 1u << 24;
2330
size_t requested_out = available_out;
2331
BrotliDecoderErrorCode status;
2332
if ((s->ringbuffer == 0) || ((int)s->error_code < 0)) {
2333
*size = 0;
2334
return 0;
2335
}
2336
WrapRingBuffer(s);
2337
status = WriteRingBuffer(s, &available_out, &result, 0, BROTLI_TRUE);
2338
/* Either WriteRingBuffer returns those "success" codes... */
2339
if (status == BROTLI_DECODER_SUCCESS ||
2340
status == BROTLI_DECODER_NEEDS_MORE_OUTPUT) {
2341
*size = requested_out - available_out;
2342
} else {
2343
/* ... or stream is broken. Normally this should be caught by
2344
BrotliDecoderDecompressStream, this is just a safeguard. */
2345
if ((int)status < 0) SaveErrorCode(s, status);
2346
*size = 0;
2347
result = 0;
2348
}
2349
return result;
2350
}
2351
2352
BROTLI_BOOL BrotliDecoderIsUsed(const BrotliDecoderState* s) {
2353
return TO_BROTLI_BOOL(s->state != BROTLI_STATE_UNINITED ||
2354
BrotliGetAvailableBits(&s->br) != 0);
2355
}
2356
2357
BROTLI_BOOL BrotliDecoderIsFinished(const BrotliDecoderState* s) {
2358
return TO_BROTLI_BOOL(s->state == BROTLI_STATE_DONE) &&
2359
!BrotliDecoderHasMoreOutput(s);
2360
}
2361
2362
BrotliDecoderErrorCode BrotliDecoderGetErrorCode(const BrotliDecoderState* s) {
2363
return (BrotliDecoderErrorCode)s->error_code;
2364
}
2365
2366
const char* BrotliDecoderErrorString(BrotliDecoderErrorCode c) {
2367
switch (c) {
2368
#define BROTLI_ERROR_CODE_CASE_(PREFIX, NAME, CODE) \
2369
case BROTLI_DECODER ## PREFIX ## NAME: return #NAME;
2370
#define BROTLI_NOTHING_
2371
BROTLI_DECODER_ERROR_CODES_LIST(BROTLI_ERROR_CODE_CASE_, BROTLI_NOTHING_)
2372
#undef BROTLI_ERROR_CODE_CASE_
2373
#undef BROTLI_NOTHING_
2374
default: return "INVALID";
2375
}
2376
}
2377
2378
uint32_t BrotliDecoderVersion() {
2379
return BROTLI_VERSION;
2380
}
2381
2382
#if defined(__cplusplus) || defined(c_plusplus)
2383
} /* extern "C" */
2384
#endif
Loggerhead is a web-based interface for Breezy
Version: 2.0.1