[Telemetry] Reenable unused-import lint check for telemetry.
[chromium-blink-merge.git] / third_party / brotli / dec / decode.c
blob8dc55a085d3a667a4050d1a1a5f67b33e5af811c
1 /* Copyright 2013 Google Inc. All Rights Reserved.
3 Licensed under the Apache License, Version 2.0 (the "License");
4 you may not use this file except in compliance with the License.
5 You may obtain a copy of the License at
7 http://www.apache.org/licenses/LICENSE-2.0
9 Unless required by applicable law or agreed to in writing, software
10 distributed under the License is distributed on an "AS IS" BASIS,
11 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 See the License for the specific language governing permissions and
13 limitations under the License.
16 #include <stdlib.h>
17 #include <stdio.h>
18 #include <string.h>
19 #include "./bit_reader.h"
20 #include "./context.h"
21 #include "./decode.h"
22 #include "./dictionary.h"
23 #include "./transform.h"
24 #include "./huffman.h"
25 #include "./prefix.h"
26 #include "./safe_malloc.h"
28 #if defined(__cplusplus) || defined(c_plusplus)
29 extern "C" {
30 #endif
32 #ifdef BROTLI_DECODE_DEBUG
33 #define BROTLI_LOG_UINT(name) \
34 printf("[%s] %s = %lu\n", __func__, #name, (unsigned long)(name))
35 #define BROTLI_LOG_ARRAY_INDEX(array_name, idx) \
36 printf("[%s] %s[%lu] = %lu\n", __func__, #array_name, \
37 (unsigned long)(idx), (unsigned long)array_name[idx])
38 #else
39 #define BROTLI_LOG_UINT(name)
40 #define BROTLI_LOG_ARRAY_INDEX(array_name, idx)
41 #endif
43 static const uint8_t kDefaultCodeLength = 8;
44 static const uint8_t kCodeLengthRepeatCode = 16;
45 static const int kNumLiteralCodes = 256;
46 static const int kNumInsertAndCopyCodes = 704;
47 static const int kNumBlockLengthCodes = 26;
48 static const int kLiteralContextBits = 6;
49 static const int kDistanceContextBits = 2;
51 #define HUFFMAN_TABLE_BITS 8
52 #define HUFFMAN_TABLE_MASK 0xff
54 #define CODE_LENGTH_CODES 18
55 static const uint8_t kCodeLengthCodeOrder[CODE_LENGTH_CODES] = {
56 1, 2, 3, 4, 0, 5, 17, 6, 16, 7, 8, 9, 10, 11, 12, 13, 14, 15,
59 #define NUM_DISTANCE_SHORT_CODES 16
60 static const int kDistanceShortCodeIndexOffset[NUM_DISTANCE_SHORT_CODES] = {
61 3, 2, 1, 0, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2
64 static const int kDistanceShortCodeValueOffset[NUM_DISTANCE_SHORT_CODES] = {
65 0, 0, 0, 0, -1, 1, -2, 2, -3, 3, -1, 1, -2, 2, -3, 3
68 static BROTLI_INLINE int DecodeWindowBits(BrotliBitReader* br) {
69 if (BrotliReadBits(br, 1)) {
70 return 17 + (int)BrotliReadBits(br, 3);
71 } else {
72 return 16;
76 /* Decodes a number in the range [0..255], by reading 1 - 11 bits. */
77 static BROTLI_INLINE int DecodeVarLenUint8(BrotliBitReader* br) {
78 if (BrotliReadBits(br, 1)) {
79 int nbits = (int)BrotliReadBits(br, 3);
80 if (nbits == 0) {
81 return 1;
82 } else {
83 return (int)BrotliReadBits(br, nbits) + (1 << nbits);
86 return 0;
89 static void DecodeMetaBlockLength(BrotliBitReader* br,
90 int* meta_block_length,
91 int* input_end,
92 int* is_uncompressed) {
93 int size_nibbles;
94 int i;
95 *input_end = (int)BrotliReadBits(br, 1);
96 *meta_block_length = 0;
97 *is_uncompressed = 0;
98 if (*input_end && BrotliReadBits(br, 1)) {
99 return;
101 size_nibbles = (int)BrotliReadBits(br, 2) + 4;
102 for (i = 0; i < size_nibbles; ++i) {
103 *meta_block_length |= (int)BrotliReadBits(br, 4) << (i * 4);
105 ++(*meta_block_length);
106 if (!*input_end) {
107 *is_uncompressed = (int)BrotliReadBits(br, 1);
111 /* Decodes the next Huffman code from bit-stream. */
112 static BROTLI_INLINE int ReadSymbol(const HuffmanCode* table,
113 BrotliBitReader* br) {
114 int nbits;
115 BrotliFillBitWindow(br);
116 table += (int)(br->val_ >> br->bit_pos_) & HUFFMAN_TABLE_MASK;
117 nbits = table->bits - HUFFMAN_TABLE_BITS;
118 if (nbits > 0) {
119 br->bit_pos_ += HUFFMAN_TABLE_BITS;
120 table += table->value;
121 table += (int)(br->val_ >> br->bit_pos_) & ((1 << nbits) - 1);
123 br->bit_pos_ += table->bits;
124 return table->value;
127 static void PrintUcharVector(const uint8_t* v, int len) {
128 while (len-- > 0) printf(" %d", *v++);
129 printf("\n");
132 static BrotliResult ReadHuffmanCodeLengths(
133 const uint8_t* code_length_code_lengths,
134 int num_symbols, uint8_t* code_lengths,
135 BrotliState* s) {
136 BrotliBitReader* br = &s->br;
137 switch (s->sub_state[1]) {
138 case BROTLI_STATE_SUB_HUFFMAN_LENGTH_BEGIN:
139 s->symbol = 0;
140 s->prev_code_len = kDefaultCodeLength;
141 s->repeat = 0;
142 s->repeat_code_len = 0;
143 s->space = 32768;
145 if (!BrotliBuildHuffmanTable(s->table, 5,
146 code_length_code_lengths,
147 CODE_LENGTH_CODES)) {
148 printf("[ReadHuffmanCodeLengths] Building code length tree failed: ");
149 PrintUcharVector(code_length_code_lengths, CODE_LENGTH_CODES);
150 return BROTLI_RESULT_ERROR;
152 s->sub_state[1] = BROTLI_STATE_SUB_HUFFMAN_LENGTH_SYMBOLS;
153 /* No break, continue to next state. */
154 case BROTLI_STATE_SUB_HUFFMAN_LENGTH_SYMBOLS:
155 while (s->symbol < num_symbols && s->space > 0) {
156 const HuffmanCode* p = s->table;
157 uint8_t code_len;
158 if (!BrotliReadMoreInput(br)) {
159 return BROTLI_RESULT_PARTIAL;
161 BrotliFillBitWindow(br);
162 p += (br->val_ >> br->bit_pos_) & 31;
163 br->bit_pos_ += p->bits;
164 code_len = (uint8_t)p->value;
165 if (code_len < kCodeLengthRepeatCode) {
166 s->repeat = 0;
167 code_lengths[s->symbol++] = code_len;
168 if (code_len != 0) {
169 s->prev_code_len = code_len;
170 s->space -= 32768 >> code_len;
172 } else {
173 const int extra_bits = code_len - 14;
174 int old_repeat;
175 int repeat_delta;
176 uint8_t new_len = 0;
177 if (code_len == kCodeLengthRepeatCode) {
178 new_len = s->prev_code_len;
180 if (s->repeat_code_len != new_len) {
181 s->repeat = 0;
182 s->repeat_code_len = new_len;
184 old_repeat = s->repeat;
185 if (s->repeat > 0) {
186 s->repeat -= 2;
187 s->repeat <<= extra_bits;
189 s->repeat += (int)BrotliReadBits(br, extra_bits) + 3;
190 repeat_delta = s->repeat - old_repeat;
191 if (s->symbol + repeat_delta > num_symbols) {
192 return BROTLI_RESULT_ERROR;
194 memset(&code_lengths[s->symbol], s->repeat_code_len,
195 (size_t)repeat_delta);
196 s->symbol += repeat_delta;
197 if (s->repeat_code_len != 0) {
198 s->space -= repeat_delta << (15 - s->repeat_code_len);
202 if (s->space != 0) {
203 printf("[ReadHuffmanCodeLengths] s->space = %d\n", s->space);
204 return BROTLI_RESULT_ERROR;
206 memset(&code_lengths[s->symbol], 0, (size_t)(num_symbols - s->symbol));
207 s->sub_state[1] = BROTLI_STATE_SUB_NONE;
208 return BROTLI_RESULT_SUCCESS;
209 default:
210 return BROTLI_RESULT_ERROR;
212 return BROTLI_RESULT_ERROR;
215 static BrotliResult ReadHuffmanCode(int alphabet_size,
216 HuffmanCode* table,
217 int* opt_table_size,
218 BrotliState* s) {
219 BrotliBitReader* br = &s->br;
220 BrotliResult result = BROTLI_RESULT_SUCCESS;
221 int table_size = 0;
222 /* State machine */
223 for (;;) {
224 switch(s->sub_state[1]) {
225 case BROTLI_STATE_SUB_NONE:
226 if (!BrotliReadMoreInput(br)) {
227 return BROTLI_RESULT_PARTIAL;
229 s->code_lengths =
230 (uint8_t*)BrotliSafeMalloc((uint64_t)alphabet_size,
231 sizeof(*s->code_lengths));
232 if (s->code_lengths == NULL) {
233 return BROTLI_RESULT_ERROR;
235 /* simple_code_or_skip is used as follows:
236 1 for simple code;
237 0 for no skipping, 2 skips 2 code lengths, 3 skips 3 code lengths */
238 s->simple_code_or_skip = (int)BrotliReadBits(br, 2);
239 BROTLI_LOG_UINT(s->simple_code_or_skip);
240 if (s->simple_code_or_skip == 1) {
241 /* Read symbols, codes & code lengths directly. */
242 int i;
243 int max_bits_counter = alphabet_size - 1;
244 int max_bits = 0;
245 int symbols[4] = { 0 };
246 const int num_symbols = (int)BrotliReadBits(br, 2) + 1;
247 while (max_bits_counter) {
248 max_bits_counter >>= 1;
249 ++max_bits;
251 memset(s->code_lengths, 0, (size_t)alphabet_size);
252 for (i = 0; i < num_symbols; ++i) {
253 symbols[i] = (int)BrotliReadBits(br, max_bits) % alphabet_size;
254 s->code_lengths[symbols[i]] = 2;
256 s->code_lengths[symbols[0]] = 1;
257 switch (num_symbols) {
258 case 1:
259 break;
260 case 3:
261 if ((symbols[0] == symbols[1]) ||
262 (symbols[0] == symbols[2]) ||
263 (symbols[1] == symbols[2])) {
264 return BROTLI_RESULT_ERROR;
266 break;
267 case 2:
268 if (symbols[0] == symbols[1]) {
269 return BROTLI_RESULT_ERROR;
271 s->code_lengths[symbols[1]] = 1;
272 break;
273 case 4:
274 if ((symbols[0] == symbols[1]) ||
275 (symbols[0] == symbols[2]) ||
276 (symbols[0] == symbols[3]) ||
277 (symbols[1] == symbols[2]) ||
278 (symbols[1] == symbols[3]) ||
279 (symbols[2] == symbols[3])) {
280 return BROTLI_RESULT_ERROR;
282 if (BrotliReadBits(br, 1)) {
283 s->code_lengths[symbols[2]] = 3;
284 s->code_lengths[symbols[3]] = 3;
285 } else {
286 s->code_lengths[symbols[0]] = 2;
288 break;
290 BROTLI_LOG_UINT(num_symbols);
291 s->sub_state[1] = BROTLI_STATE_SUB_HUFFMAN_DONE;
292 break;
293 } else { /* Decode Huffman-coded code lengths. */
294 int i;
295 int space = 32;
296 int num_codes = 0;
297 /* Static Huffman code for the code length code lengths */
298 static const HuffmanCode huff[16] = {
299 {2, 0}, {2, 4}, {2, 3}, {3, 2}, {2, 0}, {2, 4}, {2, 3}, {4, 1},
300 {2, 0}, {2, 4}, {2, 3}, {3, 2}, {2, 0}, {2, 4}, {2, 3}, {4, 5},
302 for (i = 0; i < CODE_LENGTH_CODES; i++) {
303 s->code_length_code_lengths[i] = 0;
305 for (i = s->simple_code_or_skip;
306 i < CODE_LENGTH_CODES && space > 0; ++i) {
307 const int code_len_idx = kCodeLengthCodeOrder[i];
308 const HuffmanCode* p = huff;
309 uint8_t v;
310 BrotliFillBitWindow(br);
311 p += (br->val_ >> br->bit_pos_) & 15;
312 br->bit_pos_ += p->bits;
313 v = (uint8_t)p->value;
314 s->code_length_code_lengths[code_len_idx] = v;
315 BROTLI_LOG_ARRAY_INDEX(s->code_length_code_lengths, code_len_idx);
316 if (v != 0) {
317 space -= (32 >> v);
318 ++num_codes;
321 if (!(num_codes == 1 || space == 0)) {
322 return BROTLI_RESULT_ERROR;
324 s->sub_state[1] = BROTLI_STATE_SUB_HUFFMAN_LENGTH_BEGIN;
326 /* No break, go to next state */
327 case BROTLI_STATE_SUB_HUFFMAN_LENGTH_BEGIN:
328 case BROTLI_STATE_SUB_HUFFMAN_LENGTH_SYMBOLS:
329 result = ReadHuffmanCodeLengths(s->code_length_code_lengths,
330 alphabet_size, s->code_lengths, s);
331 if (result != BROTLI_RESULT_SUCCESS) return result;
332 s->sub_state[1] = BROTLI_STATE_SUB_HUFFMAN_DONE;
333 /* No break, go to next state */
334 case BROTLI_STATE_SUB_HUFFMAN_DONE:
335 table_size = BrotliBuildHuffmanTable(table, HUFFMAN_TABLE_BITS,
336 s->code_lengths, alphabet_size);
337 if (table_size == 0) {
338 printf("[ReadHuffmanCode] BuildHuffmanTable failed: ");
339 PrintUcharVector(s->code_lengths, alphabet_size);
340 return BROTLI_RESULT_ERROR;
342 free(s->code_lengths);
343 s->code_lengths = NULL;
344 if (opt_table_size) {
345 *opt_table_size = table_size;
347 s->sub_state[1] = BROTLI_STATE_SUB_NONE;
348 return result;
349 default:
350 return BROTLI_RESULT_ERROR; /* unknown state */
354 return BROTLI_RESULT_ERROR;
357 static BROTLI_INLINE int ReadBlockLength(const HuffmanCode* table,
358 BrotliBitReader* br) {
359 int code;
360 int nbits;
361 code = ReadSymbol(table, br);
362 nbits = kBlockLengthPrefixCode[code].nbits;
363 return kBlockLengthPrefixCode[code].offset + (int)BrotliReadBits(br, nbits);
366 static int TranslateShortCodes(int code, int* ringbuffer, int index) {
367 int val;
368 if (code < NUM_DISTANCE_SHORT_CODES) {
369 index += kDistanceShortCodeIndexOffset[code];
370 index &= 3;
371 val = ringbuffer[index] + kDistanceShortCodeValueOffset[code];
372 } else {
373 val = code - NUM_DISTANCE_SHORT_CODES + 1;
375 return val;
378 static void MoveToFront(uint8_t* v, uint8_t index) {
379 uint8_t value = v[index];
380 uint8_t i = index;
381 for (; i; --i) v[i] = v[i - 1];
382 v[0] = value;
385 static void InverseMoveToFrontTransform(uint8_t* v, int v_len) {
386 uint8_t mtf[256];
387 int i;
388 for (i = 0; i < 256; ++i) {
389 mtf[i] = (uint8_t)i;
391 for (i = 0; i < v_len; ++i) {
392 uint8_t index = v[i];
393 v[i] = mtf[index];
394 if (index) MoveToFront(mtf, index);
398 static BrotliResult HuffmanTreeGroupDecode(HuffmanTreeGroup* group,
399 BrotliState* s) {
400 switch (s->sub_state[0]) {
401 case BROTLI_STATE_SUB_NONE:
402 s->next = group->codes;
403 s->htree_index = 0;
404 s->sub_state[0] = BROTLI_STATE_SUB_TREE_GROUP;
405 /* No break, continue to next state. */
406 case BROTLI_STATE_SUB_TREE_GROUP:
407 while (s->htree_index < group->num_htrees) {
408 int table_size;
409 BrotliResult result =
410 ReadHuffmanCode(group->alphabet_size, s->next, &table_size, s);
411 if (result != BROTLI_RESULT_SUCCESS) return result;
412 group->htrees[s->htree_index] = s->next;
413 s->next += table_size;
414 if (table_size == 0) {
415 return BROTLI_RESULT_ERROR;
417 ++s->htree_index;
419 s->sub_state[0] = BROTLI_STATE_SUB_NONE;
420 return BROTLI_RESULT_SUCCESS;
421 default:
422 return BROTLI_RESULT_ERROR; /* unknown state */
425 return BROTLI_RESULT_ERROR;
428 static BrotliResult DecodeContextMap(int context_map_size,
429 int* num_htrees,
430 uint8_t** context_map,
431 BrotliState* s) {
432 BrotliBitReader* br = &s->br;
433 BrotliResult result = BROTLI_RESULT_SUCCESS;
434 int use_rle_for_zeros;
436 switch(s->sub_state[0]) {
437 case BROTLI_STATE_SUB_NONE:
438 if (!BrotliReadMoreInput(br)) {
439 return BROTLI_RESULT_PARTIAL;
441 *num_htrees = DecodeVarLenUint8(br) + 1;
443 s->context_index = 0;
445 BROTLI_LOG_UINT(context_map_size);
446 BROTLI_LOG_UINT(*num_htrees);
448 *context_map = (uint8_t*)malloc((size_t)context_map_size);
449 if (*context_map == 0) {
450 return BROTLI_RESULT_ERROR;
452 if (*num_htrees <= 1) {
453 memset(*context_map, 0, (size_t)context_map_size);
454 return BROTLI_RESULT_SUCCESS;
457 use_rle_for_zeros = (int)BrotliReadBits(br, 1);
458 if (use_rle_for_zeros) {
459 s->max_run_length_prefix = (int)BrotliReadBits(br, 4) + 1;
460 } else {
461 s->max_run_length_prefix = 0;
463 s->context_map_table = (HuffmanCode*)malloc(
464 BROTLI_HUFFMAN_MAX_TABLE_SIZE * sizeof(*s->context_map_table));
465 if (s->context_map_table == NULL) {
466 return BROTLI_RESULT_ERROR;
468 s->sub_state[0] = BROTLI_STATE_SUB_CONTEXT_MAP_HUFFMAN;
469 /* No break, continue to next state. */
470 case BROTLI_STATE_SUB_CONTEXT_MAP_HUFFMAN:
471 result = ReadHuffmanCode(*num_htrees + s->max_run_length_prefix,
472 s->context_map_table, NULL, s);
473 if (result != BROTLI_RESULT_SUCCESS) return result;
474 s->sub_state[0] = BROTLI_STATE_SUB_CONTEXT_MAPS;
475 /* No break, continue to next state. */
476 case BROTLI_STATE_SUB_CONTEXT_MAPS:
477 while (s->context_index < context_map_size) {
478 int code;
479 if (!BrotliReadMoreInput(br)) {
480 return BROTLI_RESULT_PARTIAL;
482 code = ReadSymbol(s->context_map_table, br);
483 if (code == 0) {
484 (*context_map)[s->context_index] = 0;
485 ++s->context_index;
486 } else if (code <= s->max_run_length_prefix) {
487 int reps = 1 + (1 << code) + (int)BrotliReadBits(br, code);
488 while (--reps) {
489 if (s->context_index >= context_map_size) {
490 return BROTLI_RESULT_ERROR;
492 (*context_map)[s->context_index] = 0;
493 ++s->context_index;
495 } else {
496 (*context_map)[s->context_index] =
497 (uint8_t)(code - s->max_run_length_prefix);
498 ++s->context_index;
501 if (BrotliReadBits(br, 1)) {
502 InverseMoveToFrontTransform(*context_map, context_map_size);
504 free(s->context_map_table);
505 s->context_map_table = NULL;
506 s->sub_state[0] = BROTLI_STATE_SUB_NONE;
507 return BROTLI_RESULT_SUCCESS;
508 default:
509 return BROTLI_RESULT_ERROR; /* unknown state */
512 return BROTLI_RESULT_ERROR;
515 static BROTLI_INLINE void DecodeBlockType(const int max_block_type,
516 const HuffmanCode* trees,
517 int tree_type,
518 int* block_types,
519 int* ringbuffers,
520 int* indexes,
521 BrotliBitReader* br) {
522 int* ringbuffer = ringbuffers + tree_type * 2;
523 int* index = indexes + tree_type;
524 int type_code =
525 ReadSymbol(&trees[tree_type * BROTLI_HUFFMAN_MAX_TABLE_SIZE], br);
526 int block_type;
527 if (type_code == 0) {
528 block_type = ringbuffer[*index & 1];
529 } else if (type_code == 1) {
530 block_type = ringbuffer[(*index - 1) & 1] + 1;
531 } else {
532 block_type = type_code - 2;
534 if (block_type >= max_block_type) {
535 block_type -= max_block_type;
537 block_types[tree_type] = block_type;
538 ringbuffer[(*index) & 1] = block_type;
539 ++(*index);
542 /* Decodes the block type and updates the state for literal context. */
543 static BROTLI_INLINE void DecodeBlockTypeWithContext(BrotliState* s,
544 BrotliBitReader* br) {
545 DecodeBlockType(s->num_block_types[0],
546 s->block_type_trees, 0,
547 s->block_type, s->block_type_rb,
548 s->block_type_rb_index, br);
549 s->block_length[0] = ReadBlockLength(s->block_len_trees, br);
550 s->context_offset = s->block_type[0] << kLiteralContextBits;
551 s->context_map_slice = s->context_map + s->context_offset;
552 s->literal_htree_index = s->context_map_slice[0];
553 s->context_mode = s->context_modes[s->block_type[0]];
554 s->context_lookup_offset1 = kContextLookupOffsets[s->context_mode];
555 s->context_lookup_offset2 = kContextLookupOffsets[s->context_mode + 1];
558 /* Copy len bytes from src to dst. It can write up to ten extra bytes
559 after the end of the copy.
561 The main part of this loop is a simple copy of eight bytes at a time until
562 we've copied (at least) the requested amount of bytes. However, if dst and
563 src are less than eight bytes apart (indicating a repeating pattern of
564 length < 8), we first need to expand the pattern in order to get the correct
565 results. For instance, if the buffer looks like this, with the eight-byte
566 <src> and <dst> patterns marked as intervals:
568 abxxxxxxxxxxxx
569 [------] src
570 [------] dst
572 a single eight-byte copy from <src> to <dst> will repeat the pattern once,
573 after which we can move <dst> two bytes without moving <src>:
575 ababxxxxxxxxxx
576 [------] src
577 [------] dst
579 and repeat the exercise until the two no longer overlap.
581 This allows us to do very well in the special case of one single byte
582 repeated many times, without taking a big hit for more general cases.
584 The worst case of extra writing past the end of the match occurs when
585 dst - src == 1 and len == 1; the last copy will read from byte positions
586 [0..7] and write to [4..11], whereas it was only supposed to write to
587 position 1. Thus, ten excess bytes.
589 static BROTLI_INLINE void IncrementalCopyFastPath(
590 uint8_t* dst, const uint8_t* src, int len) {
591 if (src < dst) {
592 while (dst - src < 8) {
593 UNALIGNED_MOVE64(dst, src);
594 len -= (int)(dst - src);
595 dst += dst - src;
598 while (len > 0) {
599 UNALIGNED_COPY64(dst, src);
600 src += 8;
601 dst += 8;
602 len -= 8;
606 BrotliResult CopyUncompressedBlockToOutput(BrotliOutput output,
607 int pos,
608 BrotliState* s) {
609 const int rb_size = s->ringbuffer_mask + 1;
610 uint8_t* ringbuffer_end = s->ringbuffer + rb_size;
611 int rb_pos = pos & s->ringbuffer_mask;
612 int br_pos = s->br.pos_ & BROTLI_IBUF_MASK;
613 uint32_t remaining_bits;
614 int num_read;
616 /* State machine */
617 for (;;) {
618 switch (s->sub_state[0]) {
619 case BROTLI_STATE_SUB_NONE:
620 /* For short lengths copy byte-by-byte */
621 if (s->meta_block_remaining_len < 8 || s->br.bit_pos_ +
622 (uint32_t)(s->meta_block_remaining_len << 3) < s->br.bit_end_pos_) {
623 s->sub_state[0] = BROTLI_STATE_SUB_UNCOMPRESSED_SHORT;
624 break;
626 if (s->br.bit_end_pos_ < 64) {
627 return BROTLI_RESULT_ERROR;
630 * Copy remaining 0-4 in 32-bit case or 0-8 bytes in the 64-bit case
631 * from s->br.val_ to ringbuffer.
633 #if (BROTLI_USE_64_BITS)
634 remaining_bits = 64;
635 #else
636 remaining_bits = 32;
637 #endif
638 while (s->br.bit_pos_ < remaining_bits) {
639 s->ringbuffer[rb_pos] = (uint8_t)(s->br.val_ >> s->br.bit_pos_);
640 s->br.bit_pos_ += 8;
641 ++rb_pos;
642 --s->meta_block_remaining_len;
645 /* Copy remaining bytes from s->br.buf_ to ringbuffer. */
646 s->nbytes = (int)(s->br.bit_end_pos_ - s->br.bit_pos_) >> 3;
647 if (br_pos + s->nbytes > BROTLI_IBUF_MASK) {
648 int tail = BROTLI_IBUF_MASK + 1 - br_pos;
649 memcpy(&s->ringbuffer[rb_pos], &s->br.buf_[br_pos], (size_t)tail);
650 s->nbytes -= tail;
651 rb_pos += tail;
652 s->meta_block_remaining_len -= tail;
653 br_pos = 0;
655 memcpy(&s->ringbuffer[rb_pos], &s->br.buf_[br_pos], (size_t)s->nbytes);
656 rb_pos += s->nbytes;
657 s->meta_block_remaining_len -= s->nbytes;
659 /* If we wrote past the logical end of the ringbuffer, copy the tail of
660 the ringbuffer to its beginning and flush the ringbuffer to the
661 output. */
662 if (rb_pos >= rb_size) {
663 if (BrotliWrite(output, s->ringbuffer, (size_t)rb_size) < rb_size) {
664 return BROTLI_RESULT_ERROR;
666 rb_pos -= rb_size;
667 s->meta_block_remaining_len += rb_size;
668 memcpy(s->ringbuffer, ringbuffer_end, (size_t)rb_pos);
670 s->sub_state[0] = BROTLI_STATE_SUB_UNCOMPRESSED_FILL;
671 break;
672 case BROTLI_STATE_SUB_UNCOMPRESSED_SHORT:
673 while (s->meta_block_remaining_len > 0) {
674 if (!BrotliReadMoreInput(&s->br)) {
675 return BROTLI_RESULT_PARTIAL;
677 s->ringbuffer[rb_pos++] = (uint8_t)BrotliReadBits(&s->br, 8);
678 if (rb_pos == rb_size) {
679 if (BrotliWrite(output, s->ringbuffer, (size_t)rb_size) < rb_size) {
680 return BROTLI_RESULT_ERROR;
682 rb_pos = 0;
684 s->meta_block_remaining_len--;
686 s->sub_state[0] = BROTLI_STATE_SUB_NONE;
687 return BROTLI_RESULT_SUCCESS;
688 case BROTLI_STATE_SUB_UNCOMPRESSED_FILL:
689 /* If we have more to copy than the remaining size of the ringbuffer,
690 then we first fill the ringbuffer from the input and then flush the
691 ringbuffer to the output */
692 while (rb_pos + s->meta_block_remaining_len >= rb_size) {
693 s->nbytes = rb_size - rb_pos;
694 if (BrotliRead(s->br.input_, &s->ringbuffer[rb_pos],
695 (size_t)s->nbytes) < s->nbytes) {
696 return BROTLI_RESULT_PARTIAL;
698 if (BrotliWrite(output, s->ringbuffer, (size_t)rb_size) < s->nbytes) {
699 return BROTLI_RESULT_ERROR;
701 s->meta_block_remaining_len -= s->nbytes;
702 rb_pos = 0;
704 s->sub_state[0] = BROTLI_STATE_SUB_UNCOMPRESSED_COPY;
705 /* No break, continue to next state */
706 case BROTLI_STATE_SUB_UNCOMPRESSED_COPY:
707 /* Copy straight from the input onto the ringbuffer. The ringbuffer will
708 be flushed to the output at a later time. */
709 num_read = BrotliRead(s->br.input_, &s->ringbuffer[rb_pos],
710 (size_t)s->meta_block_remaining_len);
711 s->meta_block_remaining_len -= num_read;
712 if (s->meta_block_remaining_len > 0) {
713 return BROTLI_RESULT_PARTIAL;
716 /* Restore the state of the bit reader. */
717 BrotliInitBitReader(&s->br, s->br.input_, s->br.finish_);
718 s->sub_state[0] = BROTLI_STATE_SUB_UNCOMPRESSED_WARMUP;
719 /* No break, continue to next state */
720 case BROTLI_STATE_SUB_UNCOMPRESSED_WARMUP:
721 if (!BrotliWarmupBitReader(&s->br)) {
722 return BROTLI_RESULT_PARTIAL;
724 s->sub_state[0] = BROTLI_STATE_SUB_NONE;
725 return BROTLI_RESULT_SUCCESS;
726 break;
727 default:
728 return BROTLI_RESULT_ERROR; /* Unknown state */
731 return BROTLI_RESULT_ERROR;
734 BrotliResult BrotliDecompressedSize(size_t encoded_size,
735 const uint8_t* encoded_buffer,
736 size_t* decoded_size) {
737 int i;
738 uint64_t val = 0;
739 int bit_pos = 0;
740 int is_last;
741 int is_uncompressed = 0;
742 int size_nibbles;
743 int meta_block_len = 0;
744 if (encoded_size == 0) {
745 return BROTLI_RESULT_ERROR;
747 /* Look at the first 8 bytes, it is enough to decode the length of the first
748 meta-block. */
749 for (i = 0; (size_t)i < encoded_size && i < 8; ++i) {
750 val |= (uint64_t)encoded_buffer[i] << (8 * i);
752 /* Skip the window bits. */
753 bit_pos += (val & 1) ? 4 : 1;
754 /* Decode the ISLAST bit. */
755 is_last = (val >> bit_pos) & 1;
756 ++bit_pos;
757 if (is_last) {
758 /* Decode the ISEMPTY bit, if it is set to 1, we are done. */
759 if ((val >> bit_pos) & 1) {
760 *decoded_size = 0;
761 return BROTLI_RESULT_SUCCESS;
763 ++bit_pos;
765 /* Decode the length of the first meta-block. */
766 size_nibbles = (int)((val >> bit_pos) & 3) + 4;
767 bit_pos += 2;
768 for (i = 0; i < size_nibbles; ++i) {
769 meta_block_len |= (int)((val >> bit_pos) & 0xf) << (4 * i);
770 bit_pos += 4;
772 ++meta_block_len;
773 if (is_last) {
774 /* If this meta-block is the only one, we are done. */
775 *decoded_size = (size_t)meta_block_len;
776 return BROTLI_RESULT_SUCCESS;
778 is_uncompressed = (val >> bit_pos) & 1;
779 ++bit_pos;
780 if (is_uncompressed) {
781 /* If the first meta-block is uncompressed, we skip it and look at the
782 first two bits (ISLAST and ISEMPTY) of the next meta-block, and if
783 both are set to 1, we have a stream with an uncompressed meta-block
784 followed by an empty one, so the decompressed size is the size of the
785 first meta-block. */
786 size_t offset = (size_t)((bit_pos + 7) >> 3) + (size_t)meta_block_len;
787 if (offset < encoded_size && ((encoded_buffer[offset] & 3) == 3)) {
788 *decoded_size = (size_t)meta_block_len;
789 return BROTLI_RESULT_SUCCESS;
792 return BROTLI_RESULT_ERROR;
795 BrotliResult BrotliDecompressBuffer(size_t encoded_size,
796 const uint8_t* encoded_buffer,
797 size_t* decoded_size,
798 uint8_t* decoded_buffer) {
799 BrotliMemInput memin;
800 BrotliInput in = BrotliInitMemInput(encoded_buffer, encoded_size, &memin);
801 BrotliMemOutput mout;
802 BrotliOutput out = BrotliInitMemOutput(decoded_buffer, *decoded_size, &mout);
803 BrotliResult success = BrotliDecompress(in, out);
804 *decoded_size = mout.pos;
805 return success;
808 BrotliResult BrotliDecompress(BrotliInput input, BrotliOutput output) {
809 BrotliState s;
810 BrotliResult result;
811 BrotliStateInit(&s);
812 result = BrotliDecompressStreaming(input, output, 1, &s);
813 if (result == BROTLI_RESULT_PARTIAL) {
814 /* Not ok: it didn't finish even though this is a non-streaming function. */
815 result = BROTLI_RESULT_ERROR;
817 BrotliStateCleanup(&s);
818 return result;
821 BrotliResult BrotliDecompressBufferStreaming(size_t* available_in,
822 const uint8_t** next_in,
823 int finish,
824 size_t* available_out,
825 uint8_t** next_out,
826 size_t* total_out,
827 BrotliState* s) {
828 BrotliResult result;
829 BrotliMemInput memin;
830 BrotliInput in = BrotliInitMemInput(*next_in, *available_in, &memin);
831 BrotliMemOutput memout;
832 BrotliOutput out = BrotliInitMemOutput(*next_out, *available_out, &memout);
834 result = BrotliDecompressStreaming(in, out, finish, s);
836 /* The current implementation reads everything, so 0 bytes are available. */
837 *next_in += memin.pos;
838 *available_in -= memin.pos;
840 /* Update the output position to where we write next. */
841 *next_out += memout.pos;
842 *available_out -= memout.pos;
843 *total_out += memout.pos;
845 return result;
848 BrotliResult BrotliDecompressStreaming(BrotliInput input, BrotliOutput output,
849 int finish, BrotliState* s) {
850 uint8_t context;
851 int pos = s->pos;
852 int i = s->loop_counter;
853 BrotliResult result = BROTLI_RESULT_SUCCESS;
854 BrotliBitReader* br = &s->br;
855 int initial_remaining_len;
856 int bytes_copied;
858 /* We need the slack region for the following reasons:
859 - always doing two 8-byte copies for fast backward copying
860 - transforms
861 - flushing the input s->ringbuffer when decoding uncompressed blocks */
862 static const int kRingBufferWriteAheadSlack = 128 + BROTLI_READ_SIZE;
864 s->br.finish_ = finish;
866 /* State machine */
867 for (;;) {
868 if (result != BROTLI_RESULT_SUCCESS) {
869 if (result == BROTLI_RESULT_PARTIAL && finish) {
870 printf("Unexpected end of input. State: %d\n", s->state);
871 result = BROTLI_RESULT_ERROR;
873 break; /* Fail, or partial data. */
876 switch (s->state) {
877 case BROTLI_STATE_UNINITED:
878 pos = 0;
879 s->input_end = 0;
880 s->window_bits = 0;
881 s->max_distance = 0;
882 s->dist_rb[0] = 16;
883 s->dist_rb[1] = 15;
884 s->dist_rb[2] = 11;
885 s->dist_rb[3] = 4;
886 s->dist_rb_idx = 0;
887 s->prev_byte1 = 0;
888 s->prev_byte2 = 0;
889 s->block_type_trees = NULL;
890 s->block_len_trees = NULL;
892 BrotliInitBitReader(br, input, finish);
894 s->state = BROTLI_STATE_BITREADER_WARMUP;
895 /* No break, continue to next state */
896 case BROTLI_STATE_BITREADER_WARMUP:
897 if (!BrotliWarmupBitReader(br)) {
898 result = BROTLI_RESULT_PARTIAL;
899 break;
901 /* Decode window size. */
902 s->window_bits = DecodeWindowBits(br);
903 s->max_backward_distance = (1 << s->window_bits) - 16;
905 s->ringbuffer_size = 1 << s->window_bits;
906 s->ringbuffer_mask = s->ringbuffer_size - 1;
907 s->ringbuffer = (uint8_t*)malloc((size_t)(s->ringbuffer_size +
908 kRingBufferWriteAheadSlack +
909 kMaxDictionaryWordLength));
910 if (!s->ringbuffer) {
911 result = BROTLI_RESULT_ERROR;
912 break;
914 s->ringbuffer_end = s->ringbuffer + s->ringbuffer_size;
916 s->block_type_trees = (HuffmanCode*)malloc(
917 3 * BROTLI_HUFFMAN_MAX_TABLE_SIZE * sizeof(HuffmanCode));
918 s->block_len_trees = (HuffmanCode*)malloc(
919 3 * BROTLI_HUFFMAN_MAX_TABLE_SIZE * sizeof(HuffmanCode));
920 if (s->block_type_trees == NULL || s->block_len_trees == NULL) {
921 result = BROTLI_RESULT_ERROR;
922 break;
925 s->state = BROTLI_STATE_METABLOCK_BEGIN;
926 /* No break, continue to next state */
927 case BROTLI_STATE_METABLOCK_BEGIN:
928 if (!BrotliReadMoreInput(br)) {
929 result = BROTLI_RESULT_PARTIAL;
930 break;
932 if (s->input_end) {
933 s->state = BROTLI_STATE_DONE;
934 break;
936 s->meta_block_remaining_len = 0;
937 s->block_length[0] = 1 << 28;
938 s->block_length[1] = 1 << 28;
939 s->block_length[2] = 1 << 28;
940 s->block_type[0] = 0;
941 s->num_block_types[0] = 1;
942 s->num_block_types[1] = 1;
943 s->num_block_types[2] = 1;
944 s->block_type_rb[0] = 0;
945 s->block_type_rb[1] = 1;
946 s->block_type_rb[2] = 0;
947 s->block_type_rb[3] = 1;
948 s->block_type_rb[4] = 0;
949 s->block_type_rb[5] = 1;
950 s->block_type_rb_index[0] = 0;
951 s->context_map = NULL;
952 s->context_modes = NULL;
953 s->dist_context_map = NULL;
954 s->context_offset = 0;
955 s->context_map_slice = NULL;
956 s->literal_htree_index = 0;
957 s->dist_context_offset = 0;
958 s->dist_context_map_slice = NULL;
959 s->dist_htree_index = 0;
960 s->context_lookup_offset1 = 0;
961 s->context_lookup_offset2 = 0;
962 for (i = 0; i < 3; ++i) {
963 s->hgroup[i].codes = NULL;
964 s->hgroup[i].htrees = NULL;
966 s->state = BROTLI_STATE_METABLOCK_HEADER_1;
967 /* No break, continue to next state */
968 case BROTLI_STATE_METABLOCK_HEADER_1:
969 if (!BrotliReadMoreInput(br)) {
970 result = BROTLI_RESULT_PARTIAL;
971 break;
973 BROTLI_LOG_UINT(pos);
974 DecodeMetaBlockLength(br, &s->meta_block_remaining_len,
975 &s->input_end, &s->is_uncompressed);
976 BROTLI_LOG_UINT(s->meta_block_remaining_len);
977 if (s->meta_block_remaining_len == 0) {
978 s->state = BROTLI_STATE_METABLOCK_DONE;
979 break;
981 if (s->is_uncompressed) {
982 BrotliSetBitPos(br, (s->br.bit_pos_ + 7) & (uint32_t)(~7UL));
983 s->state = BROTLI_STATE_UNCOMPRESSED;
984 break;
986 i = 0;
987 s->state = BROTLI_STATE_HUFFMAN_CODE_0;
988 break;
989 case BROTLI_STATE_UNCOMPRESSED:
990 initial_remaining_len = s->meta_block_remaining_len;
991 /* pos is given as argument since s->pos is only updated at the end. */
992 result = CopyUncompressedBlockToOutput(output, pos, s);
993 bytes_copied = initial_remaining_len - s->meta_block_remaining_len;
994 pos += bytes_copied;
995 if (bytes_copied > 0) {
996 s->prev_byte2 = bytes_copied == 1 ? s->prev_byte1 :
997 s->ringbuffer[(pos - 2) & s->ringbuffer_mask];
998 s->prev_byte1 = s->ringbuffer[(pos - 1) & s->ringbuffer_mask];
1000 if (result != BROTLI_RESULT_SUCCESS) break;
1001 s->state = BROTLI_STATE_METABLOCK_DONE;
1002 break;
1003 case BROTLI_STATE_HUFFMAN_CODE_0:
1004 if (i >= 3) {
1005 BROTLI_LOG_UINT(s->num_block_types[0]);
1006 BROTLI_LOG_UINT(s->num_block_types[1]);
1007 BROTLI_LOG_UINT(s->num_block_types[2]);
1008 BROTLI_LOG_UINT(s->block_length[0]);
1009 BROTLI_LOG_UINT(s->block_length[1]);
1010 BROTLI_LOG_UINT(s->block_length[2]);
1012 s->state = BROTLI_STATE_METABLOCK_HEADER_2;
1013 break;
1015 s->num_block_types[i] = DecodeVarLenUint8(br) + 1;
1016 s->state = BROTLI_STATE_HUFFMAN_CODE_1;
1017 /* No break, continue to next state */
1018 case BROTLI_STATE_HUFFMAN_CODE_1:
1019 if (s->num_block_types[i] >= 2) {
1020 result = ReadHuffmanCode(s->num_block_types[i] + 2,
1021 &s->block_type_trees[i * BROTLI_HUFFMAN_MAX_TABLE_SIZE],
1022 NULL, s);
1023 if (result != BROTLI_RESULT_SUCCESS) break;
1024 s->state = BROTLI_STATE_HUFFMAN_CODE_2;
1025 } else {
1026 i++;
1027 s->state = BROTLI_STATE_HUFFMAN_CODE_0;
1028 break;
1030 /* No break, continue to next state */
1031 case BROTLI_STATE_HUFFMAN_CODE_2:
1032 result = ReadHuffmanCode(kNumBlockLengthCodes,
1033 &s->block_len_trees[i * BROTLI_HUFFMAN_MAX_TABLE_SIZE],
1034 NULL, s);
1035 if (result != BROTLI_RESULT_SUCCESS) break;
1036 s->block_length[i] = ReadBlockLength(
1037 &s->block_len_trees[i * BROTLI_HUFFMAN_MAX_TABLE_SIZE], br);
1038 s->block_type_rb_index[i] = 1;
1039 i++;
1040 s->state = BROTLI_STATE_HUFFMAN_CODE_0;
1041 break;
1042 case BROTLI_STATE_METABLOCK_HEADER_2:
1043 if (!BrotliReadMoreInput(br)) {
1044 result = BROTLI_RESULT_PARTIAL;
1045 break;
1047 s->distance_postfix_bits = (int)BrotliReadBits(br, 2);
1048 s->num_direct_distance_codes = NUM_DISTANCE_SHORT_CODES +
1049 ((int)BrotliReadBits(br, 4) << s->distance_postfix_bits);
1050 s->distance_postfix_mask = (1 << s->distance_postfix_bits) - 1;
1051 s->num_distance_codes = (s->num_direct_distance_codes +
1052 (48 << s->distance_postfix_bits));
1053 s->context_modes = (uint8_t*)malloc((size_t)s->num_block_types[0]);
1054 if (s->context_modes == 0) {
1055 result = BROTLI_RESULT_ERROR;
1056 break;
1058 for (i = 0; i < s->num_block_types[0]; ++i) {
1059 s->context_modes[i] = (uint8_t)(BrotliReadBits(br, 2) << 1);
1060 BROTLI_LOG_ARRAY_INDEX(s->context_modes, i);
1062 BROTLI_LOG_UINT(s->num_direct_distance_codes);
1063 BROTLI_LOG_UINT(s->distance_postfix_bits);
1064 s->state = BROTLI_STATE_CONTEXT_MAP_1;
1065 /* No break, continue to next state */
1066 case BROTLI_STATE_CONTEXT_MAP_1:
1067 result = DecodeContextMap(s->num_block_types[0] << kLiteralContextBits,
1068 &s->num_literal_htrees, &s->context_map, s);
1070 s->trivial_literal_context = 1;
1071 for (i = 0; i < s->num_block_types[0] << kLiteralContextBits; i++) {
1072 if (s->context_map[i] != i >> kLiteralContextBits) {
1073 s->trivial_literal_context = 0;
1074 break;
1078 if (result != BROTLI_RESULT_SUCCESS) break;
1079 s->state = BROTLI_STATE_CONTEXT_MAP_2;
1080 /* No break, continue to next state */
1081 case BROTLI_STATE_CONTEXT_MAP_2:
1082 result = DecodeContextMap(s->num_block_types[2] << kDistanceContextBits,
1083 &s->num_dist_htrees, &s->dist_context_map, s);
1084 if (result != BROTLI_RESULT_SUCCESS) break;
1086 BrotliHuffmanTreeGroupInit(&s->hgroup[0], kNumLiteralCodes,
1087 s->num_literal_htrees);
1088 BrotliHuffmanTreeGroupInit(&s->hgroup[1], kNumInsertAndCopyCodes,
1089 s->num_block_types[1]);
1090 BrotliHuffmanTreeGroupInit(&s->hgroup[2], s->num_distance_codes,
1091 s->num_dist_htrees);
1092 i = 0;
1093 s->state = BROTLI_STATE_TREE_GROUP;
1094 /* No break, continue to next state */
1095 case BROTLI_STATE_TREE_GROUP:
1096 result = HuffmanTreeGroupDecode(&s->hgroup[i], s);
1097 if (result != BROTLI_RESULT_SUCCESS) break;
1098 i++;
1100 if (i >= 3) {
1101 s->context_map_slice = s->context_map;
1102 s->dist_context_map_slice = s->dist_context_map;
1103 s->context_mode = s->context_modes[s->block_type[0]];
1104 s->context_lookup_offset1 = kContextLookupOffsets[s->context_mode];
1105 s->context_lookup_offset2 =
1106 kContextLookupOffsets[s->context_mode + 1];
1107 s->htree_command = s->hgroup[1].htrees[0];
1109 s->state = BROTLI_STATE_BLOCK_BEGIN;
1110 break;
1113 break;
1114 case BROTLI_STATE_BLOCK_BEGIN:
1115 /* Block decoding is the inner loop, jumping with goto makes it 3% faster */
1116 BlockBegin:
1117 if (!BrotliReadMoreInput(br)) {
1118 result = BROTLI_RESULT_PARTIAL;
1119 break;
1121 if (s->meta_block_remaining_len <= 0) {
1122 /* Protect pos from overflow, wrap it around at every GB of input. */
1123 pos &= 0x3fffffff;
1125 /* Next metablock, if any */
1126 s->state = BROTLI_STATE_METABLOCK_DONE;
1127 break;
1130 if (s->block_length[1] == 0) {
1131 DecodeBlockType(s->num_block_types[1],
1132 s->block_type_trees, 1,
1133 s->block_type, s->block_type_rb,
1134 s->block_type_rb_index, br);
1135 s->block_length[1] = ReadBlockLength(
1136 &s->block_len_trees[BROTLI_HUFFMAN_MAX_TABLE_SIZE], br);
1137 s->htree_command = s->hgroup[1].htrees[s->block_type[1]];
1139 --s->block_length[1];
1140 s->cmd_code = ReadSymbol(s->htree_command, br);
1141 s->range_idx = s->cmd_code >> 6;
1142 if (s->range_idx >= 2) {
1143 s->range_idx -= 2;
1144 s->distance_code = -1;
1145 } else {
1146 s->distance_code = 0;
1148 s->insert_code =
1149 kInsertRangeLut[s->range_idx] + ((s->cmd_code >> 3) & 7);
1150 s->copy_code = kCopyRangeLut[s->range_idx] + (s->cmd_code & 7);
1151 s->insert_length = kInsertLengthPrefixCode[s->insert_code].offset +
1152 (int)BrotliReadBits(br,
1153 kInsertLengthPrefixCode[s->insert_code].nbits);
1154 s->copy_length = kCopyLengthPrefixCode[s->copy_code].offset +
1155 (int)BrotliReadBits(br, kCopyLengthPrefixCode[s->copy_code].nbits);
1156 BROTLI_LOG_UINT(s->insert_length);
1157 BROTLI_LOG_UINT(s->copy_length);
1158 BROTLI_LOG_UINT(s->distance_code);
1160 i = 0;
1161 s->state = BROTLI_STATE_BLOCK_INNER;
1162 /* No break, go to next state */
1163 case BROTLI_STATE_BLOCK_INNER:
1164 if (s->trivial_literal_context) {
1165 while (i < s->insert_length) {
1166 if (!BrotliReadMoreInput(br)) {
1167 result = BROTLI_RESULT_PARTIAL;
1168 break;
1170 if (s->block_length[0] == 0) {
1171 DecodeBlockTypeWithContext(s, br);
1174 s->ringbuffer[pos & s->ringbuffer_mask] = (uint8_t)ReadSymbol(
1175 s->hgroup[0].htrees[s->literal_htree_index], br);
1177 --s->block_length[0];
1178 BROTLI_LOG_UINT(s->literal_htree_index);
1179 BROTLI_LOG_ARRAY_INDEX(s->ringbuffer, pos & s->ringbuffer_mask);
1180 if ((pos & s->ringbuffer_mask) == s->ringbuffer_mask) {
1181 if (BrotliWrite(output, s->ringbuffer,
1182 (size_t)s->ringbuffer_size) < 0) {
1183 result = BROTLI_RESULT_ERROR;
1184 break;
1187 ++pos;
1188 ++i;
1190 } else {
1191 while (i < s->insert_length) {
1192 if (!BrotliReadMoreInput(br)) {
1193 result = BROTLI_RESULT_PARTIAL;
1194 break;
1196 if (s->block_length[0] == 0) {
1197 DecodeBlockTypeWithContext(s, br);
1200 context =
1201 (kContextLookup[s->context_lookup_offset1 + s->prev_byte1] |
1202 kContextLookup[s->context_lookup_offset2 + s->prev_byte2]);
1203 BROTLI_LOG_UINT(context);
1204 s->literal_htree_index = s->context_map_slice[context];
1205 --s->block_length[0];
1206 s->prev_byte2 = s->prev_byte1;
1207 s->prev_byte1 = (uint8_t)ReadSymbol(
1208 s->hgroup[0].htrees[s->literal_htree_index], br);
1209 s->ringbuffer[pos & s->ringbuffer_mask] = s->prev_byte1;
1210 BROTLI_LOG_UINT(s->literal_htree_index);
1211 BROTLI_LOG_ARRAY_INDEX(s->ringbuffer, pos & s->ringbuffer_mask);
1212 if ((pos & s->ringbuffer_mask) == s->ringbuffer_mask) {
1213 if (BrotliWrite(output, s->ringbuffer,
1214 (size_t)s->ringbuffer_size) < 0) {
1215 result = BROTLI_RESULT_ERROR;
1216 break;
1219 ++pos;
1220 ++i;
1224 if (result != BROTLI_RESULT_SUCCESS) break;
1226 s->meta_block_remaining_len -= s->insert_length;
1227 if (s->meta_block_remaining_len <= 0) {
1228 s->state = BROTLI_STATE_METABLOCK_DONE;
1229 break;
1230 } else if (s->distance_code < 0) {
1231 s->state = BROTLI_STATE_BLOCK_DISTANCE;
1232 } else {
1233 s->state = BROTLI_STATE_BLOCK_POST;
1234 break;
1236 /* No break, go to next state */
1237 case BROTLI_STATE_BLOCK_DISTANCE:
1238 if (!BrotliReadMoreInput(br)) {
1239 result = BROTLI_RESULT_PARTIAL;
1240 break;
1242 assert(s->distance_code < 0);
1244 if (s->block_length[2] == 0) {
1245 DecodeBlockType(s->num_block_types[2],
1246 s->block_type_trees, 2,
1247 s->block_type, s->block_type_rb,
1248 s->block_type_rb_index, br);
1249 s->block_length[2] = ReadBlockLength(
1250 &s->block_len_trees[2 * BROTLI_HUFFMAN_MAX_TABLE_SIZE], br);
1251 s->dist_context_offset = s->block_type[2] << kDistanceContextBits;
1252 s->dist_context_map_slice =
1253 s->dist_context_map + s->dist_context_offset;
1255 --s->block_length[2];
1256 context = (uint8_t)(s->copy_length > 4 ? 3 : s->copy_length - 2);
1257 s->dist_htree_index = s->dist_context_map_slice[context];
1258 s->distance_code =
1259 ReadSymbol(s->hgroup[2].htrees[s->dist_htree_index], br);
1260 if (s->distance_code >= s->num_direct_distance_codes) {
1261 int nbits;
1262 int postfix;
1263 int offset;
1264 s->distance_code -= s->num_direct_distance_codes;
1265 postfix = s->distance_code & s->distance_postfix_mask;
1266 s->distance_code >>= s->distance_postfix_bits;
1267 nbits = (s->distance_code >> 1) + 1;
1268 offset = ((2 + (s->distance_code & 1)) << nbits) - 4;
1269 s->distance_code = s->num_direct_distance_codes +
1270 ((offset + (int)BrotliReadBits(br, nbits)) <<
1271 s->distance_postfix_bits) + postfix;
1273 s->state = BROTLI_STATE_BLOCK_POST;
1274 /* No break, go to next state */
1275 case BROTLI_STATE_BLOCK_POST:
1276 if (!BrotliReadMoreInput(br)) {
1277 result = BROTLI_RESULT_PARTIAL;
1278 break;
1280 /* Convert the distance code to the actual distance by possibly */
1281 /* looking up past distnaces from the s->ringbuffer. */
1282 s->distance =
1283 TranslateShortCodes(s->distance_code, s->dist_rb, s->dist_rb_idx);
1284 if (s->distance < 0) {
1285 result = BROTLI_RESULT_ERROR;
1286 break;
1288 BROTLI_LOG_UINT(s->distance);
1290 if (pos < s->max_backward_distance &&
1291 s->max_distance != s->max_backward_distance) {
1292 s->max_distance = pos;
1293 } else {
1294 s->max_distance = s->max_backward_distance;
1297 s->copy_dst = &s->ringbuffer[pos & s->ringbuffer_mask];
1299 if (s->distance > s->max_distance) {
1300 if (s->copy_length >= kMinDictionaryWordLength &&
1301 s->copy_length <= kMaxDictionaryWordLength) {
1302 int offset = kBrotliDictionaryOffsetsByLength[s->copy_length];
1303 int word_id = s->distance - s->max_distance - 1;
1304 int shift = kBrotliDictionarySizeBitsByLength[s->copy_length];
1305 int mask = (1 << shift) - 1;
1306 int word_idx = word_id & mask;
1307 int transform_idx = word_id >> shift;
1308 offset += word_idx * s->copy_length;
1309 if (transform_idx < kNumTransforms) {
1310 const uint8_t* word = &kBrotliDictionary[offset];
1311 int len = TransformDictionaryWord(
1312 s->copy_dst, word, s->copy_length, transform_idx);
1313 s->copy_dst += len;
1314 pos += len;
1315 s->meta_block_remaining_len -= len;
1316 if (s->copy_dst >= s->ringbuffer_end) {
1317 if (BrotliWrite(output, s->ringbuffer,
1318 (size_t)s->ringbuffer_size) < 0) {
1319 result = BROTLI_RESULT_ERROR;
1320 break;
1322 memcpy(s->ringbuffer, s->ringbuffer_end,
1323 (size_t)(s->copy_dst - s->ringbuffer_end));
1325 } else {
1326 printf("Invalid backward reference. pos: %d distance: %d "
1327 "len: %d bytes left: %d\n",
1328 pos, s->distance, s->copy_length,
1329 s->meta_block_remaining_len);
1330 result = BROTLI_RESULT_ERROR;
1331 break;
1333 } else {
1334 printf("Invalid backward reference. pos: %d distance: %d "
1335 "len: %d bytes left: %d\n", pos, s->distance, s->copy_length,
1336 s->meta_block_remaining_len);
1337 result = BROTLI_RESULT_ERROR;
1338 break;
1340 } else {
1341 if (s->distance_code > 0) {
1342 s->dist_rb[s->dist_rb_idx & 3] = s->distance;
1343 ++s->dist_rb_idx;
1346 if (s->copy_length > s->meta_block_remaining_len) {
1347 printf("Invalid backward reference. pos: %d distance: %d "
1348 "len: %d bytes left: %d\n", pos, s->distance, s->copy_length,
1349 s->meta_block_remaining_len);
1350 result = BROTLI_RESULT_ERROR;
1351 break;
1354 s->copy_src =
1355 &s->ringbuffer[(pos - s->distance) & s->ringbuffer_mask];
1357 #if (defined(__x86_64__) || defined(_M_X64))
1358 if (s->copy_src + s->copy_length <= s->ringbuffer_end &&
1359 s->copy_dst + s->copy_length < s->ringbuffer_end) {
1360 if (s->copy_length <= 16 && s->distance >= 8) {
1361 UNALIGNED_COPY64(s->copy_dst, s->copy_src);
1362 UNALIGNED_COPY64(s->copy_dst + 8, s->copy_src + 8);
1363 } else {
1364 IncrementalCopyFastPath(s->copy_dst, s->copy_src, s->copy_length);
1366 pos += s->copy_length;
1367 s->meta_block_remaining_len -= s->copy_length;
1368 s->copy_length = 0;
1370 #endif
1372 for (i = 0; i < s->copy_length; ++i) {
1373 s->ringbuffer[pos & s->ringbuffer_mask] =
1374 s->ringbuffer[(pos - s->distance) & s->ringbuffer_mask];
1375 if ((pos & s->ringbuffer_mask) == s->ringbuffer_mask) {
1376 if (BrotliWrite(output, s->ringbuffer,
1377 (size_t)s->ringbuffer_size) < 0) {
1378 result = BROTLI_RESULT_ERROR;
1379 break;
1382 ++pos;
1383 --s->meta_block_remaining_len;
1387 /* When we get here, we must have inserted at least one literal and */
1388 /* made a copy of at least length two, therefore accessing the last 2 */
1389 /* bytes is valid. */
1390 s->prev_byte1 = s->ringbuffer[(pos - 1) & s->ringbuffer_mask];
1391 s->prev_byte2 = s->ringbuffer[(pos - 2) & s->ringbuffer_mask];
1392 s->state = BROTLI_STATE_BLOCK_BEGIN;
1393 goto BlockBegin;
1394 case BROTLI_STATE_METABLOCK_DONE:
1395 if (s->context_modes != 0) {
1396 free(s->context_modes);
1397 s->context_modes = NULL;
1399 if (s->context_map != 0) {
1400 free(s->context_map);
1401 s->context_map = NULL;
1403 if (s->dist_context_map != 0) {
1404 free(s->dist_context_map);
1405 s->dist_context_map = NULL;
1407 for (i = 0; i < 3; ++i) {
1408 BrotliHuffmanTreeGroupRelease(&s->hgroup[i]);
1409 s->hgroup[i].codes = NULL;
1410 s->hgroup[i].htrees = NULL;
1412 s->state = BROTLI_STATE_METABLOCK_BEGIN;
1413 break;
1414 case BROTLI_STATE_DONE:
1415 if (s->ringbuffer != 0) {
1416 if (BrotliWrite(output, s->ringbuffer,
1417 (size_t)(pos & s->ringbuffer_mask)) < 0) {
1418 result = BROTLI_RESULT_ERROR;
1421 return result;
1422 default:
1423 printf("Unknown state %d\n", s->state);
1424 result = BROTLI_RESULT_ERROR;
1428 s->pos = pos;
1429 s->loop_counter = i;
1430 return result;
1433 #if defined(__cplusplus) || defined(c_plusplus)
1434 } /* extern "C" */
1435 #endif