?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Add ICU message format support
[chromium-blink-merge.git] / third_party / brotli / dec / decode.c
blob674dbfb5667f1f53e96f86bf007995ebe323966c
1 /* Copyright 2013 Google Inc. All Rights Reserved.
2
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
6
7 http://www.apache.org/licenses/LICENSE-2.0
8
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.
14 */
15
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"
27
28 #if defined(__cplusplus) || defined(c_plusplus)
29 extern "C" {
30 #endif
31
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
42
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;
50
51 #define HUFFMAN_TABLE_BITS 8
52 #define HUFFMAN_TABLE_MASK 0xff
53
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,
57 };
58
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
62 };
63
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
66 };
67
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;
73 }
74 }
75
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);
84 }
85 }
86 return 0;
87 }
88
89 /* Advances the bit reader position to the next byte boundary and verifies
90 that any skipped bits are set to zero. */
91 static BROTLI_INLINE int JumpToByteBoundary(BrotliBitReader* br) {
92 uint32_t new_bit_pos = (br->bit_pos_ + 7) & (uint32_t)(~7UL);
93 uint32_t pad_bits = BrotliReadBits(br, (int)(new_bit_pos - br->bit_pos_));
94 return pad_bits == 0;
95 }
96
97 static int DecodeMetaBlockLength(BrotliBitReader* br,
98 int* meta_block_length,
99 int* input_end,
100 int* is_metadata,
101 int* is_uncompressed) {
102 int size_nibbles;
103 int size_bytes;
104 int i;
105 *input_end = (int)BrotliReadBits(br, 1);
106 *meta_block_length = 0;
107 *is_uncompressed = 0;
108 *is_metadata = 0;
109 if (*input_end && BrotliReadBits(br, 1)) {
110 return 1;
111 }
112 size_nibbles = (int)BrotliReadBits(br, 2) + 4;
113 if (size_nibbles == 7) {
114 *is_metadata = 1;
115 /* Verify reserved bit. */
116 if (BrotliReadBits(br, 1) != 0) {
117 return 0;
118 }
119 size_bytes = (int)BrotliReadBits(br, 2);
120 if (size_bytes == 0) {
121 return 1;
122 }
123 for (i = 0; i < size_bytes; ++i) {
124 int next_byte = (int)BrotliReadBits(br, 8);
125 if (i + 1 == size_bytes && size_bytes > 1 && next_byte == 0) {
126 return 0;
127 }
128 *meta_block_length |= next_byte << (i * 8);
129 }
130 } else {
131 for (i = 0; i < size_nibbles; ++i) {
132 int next_nibble = (int)BrotliReadBits(br, 4);
133 if (i + 1 == size_nibbles && size_nibbles > 4 && next_nibble == 0) {
134 return 0;
135 }
136 *meta_block_length |= next_nibble << (i * 4);
137 }
138 }
139 ++(*meta_block_length);
140 if (!*input_end && !*is_metadata) {
141 *is_uncompressed = (int)BrotliReadBits(br, 1);
142 }
143 return 1;
144 }
145
146 /* Decodes the next Huffman code from bit-stream. */
147 static BROTLI_INLINE int ReadSymbol(const HuffmanCode* table,
148 BrotliBitReader* br) {
149 int nbits;
150 BrotliFillBitWindow(br);
151 table += (int)(br->val_ >> br->bit_pos_) & HUFFMAN_TABLE_MASK;
152 nbits = table->bits - HUFFMAN_TABLE_BITS;
153 if (nbits > 0) {
154 br->bit_pos_ += HUFFMAN_TABLE_BITS;
155 table += table->value;
156 table += (int)(br->val_ >> br->bit_pos_) & ((1 << nbits) - 1);
157 }
158 br->bit_pos_ += table->bits;
159 return table->value;
160 }
161
162 static void PrintUcharVector(const uint8_t* v, int len) {
163 while (len-- > 0) printf(" %d", *v++);
164 printf("\n");
165 }
166
167 static BrotliResult ReadHuffmanCodeLengths(
168 const uint8_t* code_length_code_lengths,
169 int num_symbols, uint8_t* code_lengths,
170 BrotliState* s) {
171 BrotliBitReader* br = &s->br;
172 switch (s->sub_state[1]) {
173 case BROTLI_STATE_SUB_HUFFMAN_LENGTH_BEGIN:
174 s->symbol = 0;
175 s->prev_code_len = kDefaultCodeLength;
176 s->repeat = 0;
177 s->repeat_code_len = 0;
178 s->space = 32768;
179
180 if (!BrotliBuildHuffmanTable(s->table, 5,
181 code_length_code_lengths,
182 CODE_LENGTH_CODES)) {
183 printf("[ReadHuffmanCodeLengths] Building code length tree failed: ");
184 PrintUcharVector(code_length_code_lengths, CODE_LENGTH_CODES);
185 return BROTLI_RESULT_ERROR;
186 }
187 s->sub_state[1] = BROTLI_STATE_SUB_HUFFMAN_LENGTH_SYMBOLS;
188 /* No break, continue to next state. */
189 case BROTLI_STATE_SUB_HUFFMAN_LENGTH_SYMBOLS:
190 while (s->symbol < num_symbols && s->space > 0) {
191 const HuffmanCode* p = s->table;
192 uint8_t code_len;
193 if (!BrotliReadMoreInput(br)) {
194 return BROTLI_RESULT_NEEDS_MORE_INPUT;
195 }
196 BrotliFillBitWindow(br);
197 p += (br->val_ >> br->bit_pos_) & 31;
198 br->bit_pos_ += p->bits;
199 code_len = (uint8_t)p->value;
200 if (code_len < kCodeLengthRepeatCode) {
201 s->repeat = 0;
202 code_lengths[s->symbol++] = code_len;
203 if (code_len != 0) {
204 s->prev_code_len = code_len;
205 s->space -= 32768 >> code_len;
206 }
207 } else {
208 const int extra_bits = code_len - 14;
209 int old_repeat;
210 int repeat_delta;
211 uint8_t new_len = 0;
212 if (code_len == kCodeLengthRepeatCode) {
213 new_len = s->prev_code_len;
214 }
215 if (s->repeat_code_len != new_len) {
216 s->repeat = 0;
217 s->repeat_code_len = new_len;
218 }
219 old_repeat = s->repeat;
220 if (s->repeat > 0) {
221 s->repeat -= 2;
222 s->repeat <<= extra_bits;
223 }
224 s->repeat += (int)BrotliReadBits(br, extra_bits) + 3;
225 repeat_delta = s->repeat - old_repeat;
226 if (s->symbol + repeat_delta > num_symbols) {
227 return BROTLI_RESULT_ERROR;
228 }
229 memset(&code_lengths[s->symbol], s->repeat_code_len,
230 (size_t)repeat_delta);
231 s->symbol += repeat_delta;
232 if (s->repeat_code_len != 0) {
233 s->space -= repeat_delta << (15 - s->repeat_code_len);
234 }
235 }
236 }
237 if (s->space != 0) {
238 printf("[ReadHuffmanCodeLengths] s->space = %d\n", s->space);
239 return BROTLI_RESULT_ERROR;
240 }
241 memset(&code_lengths[s->symbol], 0, (size_t)(num_symbols - s->symbol));
242 s->sub_state[1] = BROTLI_STATE_SUB_NONE;
243 return BROTLI_RESULT_SUCCESS;
244 default:
245 return BROTLI_RESULT_ERROR;
246 }
247 return BROTLI_RESULT_ERROR;
248 }
249
250 static BrotliResult ReadHuffmanCode(int alphabet_size,
251 HuffmanCode* table,
252 int* opt_table_size,
253 BrotliState* s) {
254 BrotliBitReader* br = &s->br;
255 BrotliResult result = BROTLI_RESULT_SUCCESS;
256 int table_size = 0;
257 /* State machine */
258 for (;;) {
259 switch(s->sub_state[1]) {
260 case BROTLI_STATE_SUB_NONE:
261 if (!BrotliReadMoreInput(br)) {
262 return BROTLI_RESULT_NEEDS_MORE_INPUT;
263 }
264 s->code_lengths =
265 (uint8_t*)BrotliSafeMalloc((uint64_t)alphabet_size,
266 sizeof(*s->code_lengths));
267 if (s->code_lengths == NULL) {
268 return BROTLI_RESULT_ERROR;
269 }
270 /* simple_code_or_skip is used as follows:
271 1 for simple code;
272 0 for no skipping, 2 skips 2 code lengths, 3 skips 3 code lengths */
273 s->simple_code_or_skip = (int)BrotliReadBits(br, 2);
274 BROTLI_LOG_UINT(s->simple_code_or_skip);
275 if (s->simple_code_or_skip == 1) {
276 /* Read symbols, codes & code lengths directly. */
277 int i;
278 int max_bits_counter = alphabet_size - 1;
279 int max_bits = 0;
280 int symbols[4] = { 0 };
281 const int num_symbols = (int)BrotliReadBits(br, 2) + 1;
282 while (max_bits_counter) {
283 max_bits_counter >>= 1;
284 ++max_bits;
285 }
286 memset(s->code_lengths, 0, (size_t)alphabet_size);
287 for (i = 0; i < num_symbols; ++i) {
288 symbols[i] = (int)BrotliReadBits(br, max_bits);
289 if (symbols[i] >= alphabet_size) {
290 return BROTLI_RESULT_ERROR;
291 }
292 s->code_lengths[symbols[i]] = 2;
293 }
294 s->code_lengths[symbols[0]] = 1;
295 switch (num_symbols) {
296 case 1:
297 break;
298 case 3:
299 if ((symbols[0] == symbols[1]) ||
300 (symbols[0] == symbols[2]) ||
301 (symbols[1] == symbols[2])) {
302 return BROTLI_RESULT_ERROR;
303 }
304 break;
305 case 2:
306 if (symbols[0] == symbols[1]) {
307 return BROTLI_RESULT_ERROR;
308 }
309 s->code_lengths[symbols[1]] = 1;
310 break;
311 case 4:
312 if ((symbols[0] == symbols[1]) ||
313 (symbols[0] == symbols[2]) ||
314 (symbols[0] == symbols[3]) ||
315 (symbols[1] == symbols[2]) ||
316 (symbols[1] == symbols[3]) ||
317 (symbols[2] == symbols[3])) {
318 return BROTLI_RESULT_ERROR;
319 }
320 if (BrotliReadBits(br, 1)) {
321 s->code_lengths[symbols[2]] = 3;
322 s->code_lengths[symbols[3]] = 3;
323 } else {
324 s->code_lengths[symbols[0]] = 2;
325 }
326 break;
327 }
328 BROTLI_LOG_UINT(num_symbols);
329 s->sub_state[1] = BROTLI_STATE_SUB_HUFFMAN_DONE;
330 break;
331 } else { /* Decode Huffman-coded code lengths. */
332 int i;
333 int space = 32;
334 int num_codes = 0;
335 /* Static Huffman code for the code length code lengths */
336 static const HuffmanCode huff[16] = {
337 {2, 0}, {2, 4}, {2, 3}, {3, 2}, {2, 0}, {2, 4}, {2, 3}, {4, 1},
338 {2, 0}, {2, 4}, {2, 3}, {3, 2}, {2, 0}, {2, 4}, {2, 3}, {4, 5},
339 };
340 for (i = 0; i < CODE_LENGTH_CODES; i++) {
341 s->code_length_code_lengths[i] = 0;
342 }
343 for (i = s->simple_code_or_skip;
344 i < CODE_LENGTH_CODES && space > 0; ++i) {
345 const int code_len_idx = kCodeLengthCodeOrder[i];
346 const HuffmanCode* p = huff;
347 uint8_t v;
348 BrotliFillBitWindow(br);
349 p += (br->val_ >> br->bit_pos_) & 15;
350 br->bit_pos_ += p->bits;
351 v = (uint8_t)p->value;
352 s->code_length_code_lengths[code_len_idx] = v;
353 BROTLI_LOG_ARRAY_INDEX(s->code_length_code_lengths, code_len_idx);
354 if (v != 0) {
355 space -= (32 >> v);
356 ++num_codes;
357 }
358 }
359 if (!(num_codes == 1 || space == 0)) {
360 return BROTLI_RESULT_ERROR;
361 }
362 s->sub_state[1] = BROTLI_STATE_SUB_HUFFMAN_LENGTH_BEGIN;
363 }
364 /* No break, go to next state */
365 case BROTLI_STATE_SUB_HUFFMAN_LENGTH_BEGIN:
366 case BROTLI_STATE_SUB_HUFFMAN_LENGTH_SYMBOLS:
367 result = ReadHuffmanCodeLengths(s->code_length_code_lengths,
368 alphabet_size, s->code_lengths, s);
369 if (result != BROTLI_RESULT_SUCCESS) return result;
370 s->sub_state[1] = BROTLI_STATE_SUB_HUFFMAN_DONE;
371 /* No break, go to next state */
372 case BROTLI_STATE_SUB_HUFFMAN_DONE:
373 table_size = BrotliBuildHuffmanTable(table, HUFFMAN_TABLE_BITS,
374 s->code_lengths, alphabet_size);
375 if (table_size == 0) {
376 printf("[ReadHuffmanCode] BuildHuffmanTable failed: ");
377 PrintUcharVector(s->code_lengths, alphabet_size);
378 return BROTLI_RESULT_ERROR;
379 }
380 free(s->code_lengths);
381 s->code_lengths = NULL;
382 if (opt_table_size) {
383 *opt_table_size = table_size;
384 }
385 s->sub_state[1] = BROTLI_STATE_SUB_NONE;
386 return result;
387 default:
388 return BROTLI_RESULT_ERROR; /* unknown state */
389 }
390 }
391
392 return BROTLI_RESULT_ERROR;
393 }
394
395 static BROTLI_INLINE int ReadBlockLength(const HuffmanCode* table,
396 BrotliBitReader* br) {
397 int code;
398 int nbits;
399 code = ReadSymbol(table, br);
400 nbits = kBlockLengthPrefixCode[code].nbits;
401 return kBlockLengthPrefixCode[code].offset + (int)BrotliReadBits(br, nbits);
402 }
403
404 static int TranslateShortCodes(int code, int* ringbuffer, int index) {
405 int val;
406 if (code < NUM_DISTANCE_SHORT_CODES) {
407 index += kDistanceShortCodeIndexOffset[code];
408 index &= 3;
409 val = ringbuffer[index] + kDistanceShortCodeValueOffset[code];
410 } else {
411 val = code - NUM_DISTANCE_SHORT_CODES + 1;
412 }
413 return val;
414 }
415
416 static void InverseMoveToFrontTransform(uint8_t* v, int v_len) {
417 uint8_t mtf[256];
418 int i;
419 for (i = 0; i < 256; ++i) {
420 mtf[i] = (uint8_t)i;
421 }
422 for (i = 0; i < v_len; ++i) {
423 uint8_t index = v[i];
424 uint8_t value = mtf[index];
425 v[i] = value;
426 for (; index; --index) {
427 mtf[index] = mtf[index - 1];
428 }
429 mtf[0] = value;
430 }
431 }
432
433 static BrotliResult HuffmanTreeGroupDecode(HuffmanTreeGroup* group,
434 BrotliState* s) {
435 switch (s->sub_state[0]) {
436 case BROTLI_STATE_SUB_NONE:
437 s->next = group->codes;
438 s->htree_index = 0;
439 s->sub_state[0] = BROTLI_STATE_SUB_TREE_GROUP;
440 /* No break, continue to next state. */
441 case BROTLI_STATE_SUB_TREE_GROUP:
442 while (s->htree_index < group->num_htrees) {
443 int table_size;
444 BrotliResult result =
445 ReadHuffmanCode(group->alphabet_size, s->next, &table_size, s);
446 if (result != BROTLI_RESULT_SUCCESS) return result;
447 group->htrees[s->htree_index] = s->next;
448 s->next += table_size;
449 if (table_size == 0) {
450 return BROTLI_RESULT_ERROR;
451 }
452 ++s->htree_index;
453 }
454 s->sub_state[0] = BROTLI_STATE_SUB_NONE;
455 return BROTLI_RESULT_SUCCESS;
456 default:
457 return BROTLI_RESULT_ERROR; /* unknown state */
458 }
459
460 return BROTLI_RESULT_ERROR;
461 }
462
463 static BrotliResult DecodeContextMap(int context_map_size,
464 int* num_htrees,
465 uint8_t** context_map,
466 BrotliState* s) {
467 BrotliBitReader* br = &s->br;
468 BrotliResult result = BROTLI_RESULT_SUCCESS;
469 int use_rle_for_zeros;
470
471 switch(s->sub_state[0]) {
472 case BROTLI_STATE_SUB_NONE:
473 if (!BrotliReadMoreInput(br)) {
474 return BROTLI_RESULT_NEEDS_MORE_INPUT;
475 }
476 *num_htrees = DecodeVarLenUint8(br) + 1;
477
478 s->context_index = 0;
479
480 BROTLI_LOG_UINT(context_map_size);
481 BROTLI_LOG_UINT(*num_htrees);
482
483 *context_map = (uint8_t*)malloc((size_t)context_map_size);
484 if (*context_map == 0) {
485 return BROTLI_RESULT_ERROR;
486 }
487 if (*num_htrees <= 1) {
488 memset(*context_map, 0, (size_t)context_map_size);
489 return BROTLI_RESULT_SUCCESS;
490 }
491
492 use_rle_for_zeros = (int)BrotliReadBits(br, 1);
493 if (use_rle_for_zeros) {
494 s->max_run_length_prefix = (int)BrotliReadBits(br, 4) + 1;
495 } else {
496 s->max_run_length_prefix = 0;
497 }
498 s->context_map_table = (HuffmanCode*)malloc(
499 BROTLI_HUFFMAN_MAX_TABLE_SIZE * sizeof(*s->context_map_table));
500 if (s->context_map_table == NULL) {
501 return BROTLI_RESULT_ERROR;
502 }
503 s->sub_state[0] = BROTLI_STATE_SUB_CONTEXT_MAP_HUFFMAN;
504 /* No break, continue to next state. */
505 case BROTLI_STATE_SUB_CONTEXT_MAP_HUFFMAN:
506 result = ReadHuffmanCode(*num_htrees + s->max_run_length_prefix,
507 s->context_map_table, NULL, s);
508 if (result != BROTLI_RESULT_SUCCESS) return result;
509 s->sub_state[0] = BROTLI_STATE_SUB_CONTEXT_MAPS;
510 /* No break, continue to next state. */
511 case BROTLI_STATE_SUB_CONTEXT_MAPS:
512 while (s->context_index < context_map_size) {
513 int code;
514 if (!BrotliReadMoreInput(br)) {
515 return BROTLI_RESULT_NEEDS_MORE_INPUT;
516 }
517 code = ReadSymbol(s->context_map_table, br);
518 if (code == 0) {
519 (*context_map)[s->context_index] = 0;
520 ++s->context_index;
521 } else if (code <= s->max_run_length_prefix) {
522 int reps = 1 + (1 << code) + (int)BrotliReadBits(br, code);
523 while (--reps) {
524 if (s->context_index >= context_map_size) {
525 return BROTLI_RESULT_ERROR;
526 }
527 (*context_map)[s->context_index] = 0;
528 ++s->context_index;
529 }
530 } else {
531 (*context_map)[s->context_index] =
532 (uint8_t)(code - s->max_run_length_prefix);
533 ++s->context_index;
534 }
535 }
536 if (BrotliReadBits(br, 1)) {
537 InverseMoveToFrontTransform(*context_map, context_map_size);
538 }
539 free(s->context_map_table);
540 s->context_map_table = NULL;
541 s->sub_state[0] = BROTLI_STATE_SUB_NONE;
542 return BROTLI_RESULT_SUCCESS;
543 default:
544 return BROTLI_RESULT_ERROR; /* unknown state */
545 }
546
547 return BROTLI_RESULT_ERROR;
548 }
549
550 static BROTLI_INLINE void DecodeBlockType(const int max_block_type,
551 const HuffmanCode* trees,
552 int tree_type,
553 int* block_types,
554 int* ringbuffers,
555 int* indexes,
556 BrotliBitReader* br) {
557 int* ringbuffer = ringbuffers + tree_type * 2;
558 int* index = indexes + tree_type;
559 int type_code =
560 ReadSymbol(&trees[tree_type * BROTLI_HUFFMAN_MAX_TABLE_SIZE], br);
561 int block_type;
562 if (type_code == 0) {
563 block_type = ringbuffer[*index & 1];
564 } else if (type_code == 1) {
565 block_type = ringbuffer[(*index - 1) & 1] + 1;
566 } else {
567 block_type = type_code - 2;
568 }
569 if (block_type >= max_block_type) {
570 block_type -= max_block_type;
571 }
572 block_types[tree_type] = block_type;
573 ringbuffer[(*index) & 1] = block_type;
574 ++(*index);
575 }
576
577 /* Decodes the block type and updates the state for literal context. */
578 static BROTLI_INLINE void DecodeBlockTypeWithContext(BrotliState* s,
579 BrotliBitReader* br) {
580 DecodeBlockType(s->num_block_types[0],
581 s->block_type_trees, 0,
582 s->block_type, s->block_type_rb,
583 s->block_type_rb_index, br);
584 s->block_length[0] = ReadBlockLength(s->block_len_trees, br);
585 s->context_offset = s->block_type[0] << kLiteralContextBits;
586 s->context_map_slice = s->context_map + s->context_offset;
587 s->literal_htree_index = s->context_map_slice[0];
588 s->context_mode = s->context_modes[s->block_type[0]];
589 s->context_lookup_offset1 = kContextLookupOffsets[s->context_mode];
590 s->context_lookup_offset2 = kContextLookupOffsets[s->context_mode + 1];
591 }
592
593 /* Copy len bytes from src to dst. It can write up to ten extra bytes
594 after the end of the copy.
595
596 The main part of this loop is a simple copy of eight bytes at a time until
597 we've copied (at least) the requested amount of bytes. However, if dst and
598 src are less than eight bytes apart (indicating a repeating pattern of
599 length < 8), we first need to expand the pattern in order to get the correct
600 results. For instance, if the buffer looks like this, with the eight-byte
601 <src> and <dst> patterns marked as intervals:
602
603 abxxxxxxxxxxxx
604 [------] src
605 [------] dst
606
607 a single eight-byte copy from <src> to <dst> will repeat the pattern once,
608 after which we can move <dst> two bytes without moving <src>:
609
610 ababxxxxxxxxxx
611 [------] src
612 [------] dst
613
614 and repeat the exercise until the two no longer overlap.
615
616 This allows us to do very well in the special case of one single byte
617 repeated many times, without taking a big hit for more general cases.
618
619 The worst case of extra writing past the end of the match occurs when
620 dst - src == 1 and len == 1; the last copy will read from byte positions
621 [0..7] and write to [4..11], whereas it was only supposed to write to
622 position 1. Thus, ten excess bytes.
623 */
624 static BROTLI_INLINE void IncrementalCopyFastPath(
625 uint8_t* dst, const uint8_t* src, int len) {
626 if (src < dst) {
627 while (dst - src < 8) {
628 UNALIGNED_MOVE64(dst, src);
629 len -= (int)(dst - src);
630 dst += dst - src;
631 }
632 }
633 while (len > 0) {
634 UNALIGNED_COPY64(dst, src);
635 src += 8;
636 dst += 8;
637 len -= 8;
638 }
639 }
640
641 BrotliResult CopyUncompressedBlockToOutput(BrotliOutput output,
642 int pos,
643 BrotliState* s) {
644 const int rb_size = s->ringbuffer_mask + 1;
645 uint8_t* ringbuffer_end = s->ringbuffer + rb_size;
646 int rb_pos = pos & s->ringbuffer_mask;
647 int br_pos = s->br.pos_ & BROTLI_IBUF_MASK;
648 uint32_t remaining_bits;
649 int num_read;
650 int num_written;
651
652 /* State machine */
653 for (;;) {
654 switch (s->sub_state[0]) {
655 case BROTLI_STATE_SUB_NONE:
656 /* For short lengths copy byte-by-byte */
657 if (s->meta_block_remaining_len < 8 || s->br.bit_pos_ +
658 (uint32_t)(s->meta_block_remaining_len << 3) < s->br.bit_end_pos_) {
659 s->sub_state[0] = BROTLI_STATE_SUB_UNCOMPRESSED_SHORT;
660 break;
661 }
662 if (s->br.bit_end_pos_ < 64) {
663 return BROTLI_RESULT_ERROR;
664 }
665 /*
666 * Copy remaining 0-4 in 32-bit case or 0-8 bytes in the 64-bit case
667 * from s->br.val_ to ringbuffer.
668 */
669 #if (BROTLI_USE_64_BITS)
670 remaining_bits = 64;
671 #else
672 remaining_bits = 32;
673 #endif
674 while (s->br.bit_pos_ < remaining_bits) {
675 s->ringbuffer[rb_pos] = (uint8_t)(s->br.val_ >> s->br.bit_pos_);
676 s->br.bit_pos_ += 8;
677 ++rb_pos;
678 --s->meta_block_remaining_len;
679 }
680
681 /* Copy remaining bytes from s->br.buf_ to ringbuffer. */
682 s->nbytes = (int)(s->br.bit_end_pos_ - s->br.bit_pos_) >> 3;
683 if (br_pos + s->nbytes > BROTLI_IBUF_MASK) {
684 int tail = BROTLI_IBUF_MASK + 1 - br_pos;
685 memcpy(&s->ringbuffer[rb_pos], &s->br.buf_[br_pos], (size_t)tail);
686 s->nbytes -= tail;
687 rb_pos += tail;
688 s->meta_block_remaining_len -= tail;
689 br_pos = 0;
690 }
691 memcpy(&s->ringbuffer[rb_pos], &s->br.buf_[br_pos], (size_t)s->nbytes);
692 rb_pos += s->nbytes;
693 s->meta_block_remaining_len -= s->nbytes;
694
695 s->partially_written = 0;
696 s->sub_state[0] = BROTLI_STATE_SUB_UNCOMPRESSED_WRITE_1;
697 /* No break, continue to next state */
698 case BROTLI_STATE_SUB_UNCOMPRESSED_WRITE_1:
699 /* If we wrote past the logical end of the ringbuffer, copy the tail of
700 the ringbuffer to its beginning and flush the ringbuffer to the
701 output. */
702 if (rb_pos >= rb_size) {
703 num_written = BrotliWrite(output,
704 s->ringbuffer + s->partially_written,
705 (size_t)(rb_size - s->partially_written));
706 if (num_written < 0) {
707 return BROTLI_RESULT_ERROR;
708 }
709 s->partially_written += num_written;
710 if (s->partially_written < rb_size) {
711 return BROTLI_RESULT_NEEDS_MORE_OUTPUT;
712 }
713 rb_pos -= rb_size;
714 s->meta_block_remaining_len += rb_size;
715 memcpy(s->ringbuffer, ringbuffer_end, (size_t)rb_pos);
716 }
717 s->sub_state[0] = BROTLI_STATE_SUB_UNCOMPRESSED_FILL;
718 break;
719 case BROTLI_STATE_SUB_UNCOMPRESSED_SHORT:
720 while (s->meta_block_remaining_len > 0) {
721 if (!BrotliReadMoreInput(&s->br)) {
722 return BROTLI_RESULT_NEEDS_MORE_INPUT;
723 }
724 s->ringbuffer[rb_pos++] = (uint8_t)BrotliReadBits(&s->br, 8);
725 if (rb_pos == rb_size) {
726 s->partially_written = 0;
727 s->sub_state[0] = BROTLI_STATE_SUB_UNCOMPRESSED_WRITE_2;
728 break;
729 }
730 s->meta_block_remaining_len--;
731 }
732 if (s->sub_state[0] == BROTLI_STATE_SUB_UNCOMPRESSED_SHORT) {
733 s->sub_state[0] = BROTLI_STATE_SUB_NONE;
734 return BROTLI_RESULT_SUCCESS;
735 }
736 /* No break, if state is updated, continue to next state */
737 case BROTLI_STATE_SUB_UNCOMPRESSED_WRITE_2:
738 num_written = BrotliWrite(output, s->ringbuffer + s->partially_written,
739 (size_t)(rb_size - s->partially_written));
740 if (num_written < 0) {
741 return BROTLI_RESULT_ERROR;
742 }
743 s->partially_written += num_written;
744 if (s->partially_written < rb_size) {
745 return BROTLI_RESULT_NEEDS_MORE_OUTPUT;
746 }
747 rb_pos = 0;
748 s->meta_block_remaining_len--;
749 s->sub_state[0] = BROTLI_STATE_SUB_UNCOMPRESSED_SHORT;
750 break;
751 case BROTLI_STATE_SUB_UNCOMPRESSED_FILL:
752 /* If we have more to copy than the remaining size of the ringbuffer,
753 then we first fill the ringbuffer from the input and then flush the
754 ringbuffer to the output */
755 if (rb_pos + s->meta_block_remaining_len >= rb_size) {
756 s->nbytes = rb_size - rb_pos;
757 if (BrotliRead(s->br.input_, &s->ringbuffer[rb_pos],
758 (size_t)s->nbytes) < s->nbytes) {
759 return BROTLI_RESULT_NEEDS_MORE_INPUT;
760 }
761 s->partially_written = 0;
762 s->sub_state[0] = BROTLI_STATE_SUB_UNCOMPRESSED_WRITE_3;
763 } else {
764 s->sub_state[0] = BROTLI_STATE_SUB_UNCOMPRESSED_COPY;
765 break;
766 }
767 /* No break, continue to next state */
768 case BROTLI_STATE_SUB_UNCOMPRESSED_WRITE_3:
769 num_written = BrotliWrite(output, s->ringbuffer + s->partially_written,
770 (size_t)(rb_size - s->partially_written));
771 if (num_written < 0) {
772 return BROTLI_RESULT_ERROR;
773 }
774 s->partially_written += num_written;
775 if (s->partially_written < rb_size) {
776 return BROTLI_RESULT_NEEDS_MORE_OUTPUT;
777 }
778 s->meta_block_remaining_len -= s->nbytes;
779 rb_pos = 0;
780 s->sub_state[0] = BROTLI_STATE_SUB_UNCOMPRESSED_FILL;
781 break;
782 case BROTLI_STATE_SUB_UNCOMPRESSED_COPY:
783 /* Copy straight from the input onto the ringbuffer. The ringbuffer will
784 be flushed to the output at a later time. */
785 num_read = BrotliRead(s->br.input_, &s->ringbuffer[rb_pos],
786 (size_t)s->meta_block_remaining_len);
787 s->meta_block_remaining_len -= num_read;
788 if (s->meta_block_remaining_len > 0) {
789 return BROTLI_RESULT_NEEDS_MORE_INPUT;
790 }
791
792 /* Restore the state of the bit reader. */
793 BrotliInitBitReader(&s->br, s->br.input_, s->br.finish_);
794 s->sub_state[0] = BROTLI_STATE_SUB_UNCOMPRESSED_WARMUP;
795 /* No break, continue to next state */
796 case BROTLI_STATE_SUB_UNCOMPRESSED_WARMUP:
797 if (!BrotliWarmupBitReader(&s->br)) {
798 return BROTLI_RESULT_NEEDS_MORE_INPUT;
799 }
800 s->sub_state[0] = BROTLI_STATE_SUB_NONE;
801 return BROTLI_RESULT_SUCCESS;
802 break;
803 default:
804 return BROTLI_RESULT_ERROR; /* Unknown state */
805 }
806 }
807 return BROTLI_RESULT_ERROR;
808 }
809
810 BrotliResult BrotliDecompressedSize(size_t encoded_size,
811 const uint8_t* encoded_buffer,
812 size_t* decoded_size) {
813 int i;
814 uint64_t val = 0;
815 int bit_pos = 0;
816 int is_last;
817 int is_uncompressed = 0;
818 int size_nibbles;
819 int meta_block_len = 0;
820 if (encoded_size == 0) {
821 return BROTLI_RESULT_ERROR;
822 }
823 /* Look at the first 8 bytes, it is enough to decode the length of the first
824 meta-block. */
825 for (i = 0; (size_t)i < encoded_size && i < 8; ++i) {
826 val |= (uint64_t)encoded_buffer[i] << (8 * i);
827 }
828 /* Skip the window bits. */
829 bit_pos += (val & 1) ? 4 : 1;
830 /* Decode the ISLAST bit. */
831 is_last = (val >> bit_pos) & 1;
832 ++bit_pos;
833 if (is_last) {
834 /* Decode the ISEMPTY bit, if it is set to 1, we are done. */
835 if ((val >> bit_pos) & 1) {
836 *decoded_size = 0;
837 return BROTLI_RESULT_SUCCESS;
838 }
839 ++bit_pos;
840 }
841 /* Decode the length of the first meta-block. */
842 size_nibbles = (int)((val >> bit_pos) & 3) + 4;
843 bit_pos += 2;
844 for (i = 0; i < size_nibbles; ++i) {
845 meta_block_len |= (int)((val >> bit_pos) & 0xf) << (4 * i);
846 bit_pos += 4;
847 }
848 ++meta_block_len;
849 if (is_last) {
850 /* If this meta-block is the only one, we are done. */
851 *decoded_size = (size_t)meta_block_len;
852 return BROTLI_RESULT_SUCCESS;
853 }
854 is_uncompressed = (val >> bit_pos) & 1;
855 ++bit_pos;
856 if (is_uncompressed) {
857 /* If the first meta-block is uncompressed, we skip it and look at the
858 first two bits (ISLAST and ISEMPTY) of the next meta-block, and if
859 both are set to 1, we have a stream with an uncompressed meta-block
860 followed by an empty one, so the decompressed size is the size of the
861 first meta-block. */
862 size_t offset = (size_t)((bit_pos + 7) >> 3) + (size_t)meta_block_len;
863 if (offset < encoded_size && ((encoded_buffer[offset] & 3) == 3)) {
864 *decoded_size = (size_t)meta_block_len;
865 return BROTLI_RESULT_SUCCESS;
866 }
867 }
868 return BROTLI_RESULT_ERROR;
869 }
870
871 BrotliResult BrotliDecompressBuffer(size_t encoded_size,
872 const uint8_t* encoded_buffer,
873 size_t* decoded_size,
874 uint8_t* decoded_buffer) {
875 BrotliMemInput memin;
876 BrotliInput in = BrotliInitMemInput(encoded_buffer, encoded_size, &memin);
877 BrotliMemOutput mout;
878 BrotliOutput out = BrotliInitMemOutput(decoded_buffer, *decoded_size, &mout);
879 BrotliResult success = BrotliDecompress(in, out);
880 *decoded_size = mout.pos;
881 return success;
882 }
883
884 BrotliResult BrotliDecompress(BrotliInput input, BrotliOutput output) {
885 BrotliState s;
886 BrotliResult result;
887 BrotliStateInit(&s);
888 result = BrotliDecompressStreaming(input, output, 1, &s);
889 if (result == BROTLI_RESULT_NEEDS_MORE_INPUT) {
890 /* Not ok: it didn't finish even though this is a non-streaming function. */
891 result = BROTLI_RESULT_ERROR;
892 }
893 BrotliStateCleanup(&s);
894 return result;
895 }
896
897 BrotliResult BrotliDecompressBufferStreaming(size_t* available_in,
898 const uint8_t** next_in,
899 int finish,
900 size_t* available_out,
901 uint8_t** next_out,
902 size_t* total_out,
903 BrotliState* s) {
904 BrotliResult result;
905 BrotliMemInput memin;
906 BrotliInput in = BrotliInitMemInput(*next_in, *available_in, &memin);
907 BrotliMemOutput memout;
908 BrotliOutput out = BrotliInitMemOutput(*next_out, *available_out, &memout);
909
910 result = BrotliDecompressStreaming(in, out, finish, s);
911
912 /* The current implementation reads everything, so 0 bytes are available. */
913 *next_in += memin.pos;
914 *available_in -= memin.pos;
915
916 /* Update the output position to where we write next. */
917 *next_out += memout.pos;
918 *available_out -= memout.pos;
919 *total_out += memout.pos;
920
921 return result;
922 }
923
924 BrotliResult BrotliDecompressStreaming(BrotliInput input, BrotliOutput output,
925 int finish, BrotliState* s) {
926 uint8_t context;
927 int pos = s->pos;
928 int i = s->loop_counter;
929 BrotliResult result = BROTLI_RESULT_SUCCESS;
930 BrotliBitReader* br = &s->br;
931 int initial_remaining_len;
932 int bytes_copied;
933 int num_written;
934
935 /* We need the slack region for the following reasons:
936 - always doing two 8-byte copies for fast backward copying
937 - transforms
938 - flushing the input s->ringbuffer when decoding uncompressed blocks */
939 static const int kRingBufferWriteAheadSlack = 128 + BROTLI_READ_SIZE;
940
941 s->br.finish_ = finish;
942
943 /* State machine */
944 for (;;) {
945 if (result != BROTLI_RESULT_SUCCESS) {
946 if (result == BROTLI_RESULT_NEEDS_MORE_INPUT && finish) {
947 printf("Unexpected end of input. State: %d\n", s->state);
948 result = BROTLI_RESULT_ERROR;
949 }
950 break; /* Fail, or partial data. */
951 }
952
953 switch (s->state) {
954 case BROTLI_STATE_UNINITED:
955 pos = 0;
956 s->input_end = 0;
957 s->window_bits = 0;
958 s->max_distance = 0;
959 s->dist_rb[0] = 16;
960 s->dist_rb[1] = 15;
961 s->dist_rb[2] = 11;
962 s->dist_rb[3] = 4;
963 s->dist_rb_idx = 0;
964 s->prev_byte1 = 0;
965 s->prev_byte2 = 0;
966 s->block_type_trees = NULL;
967 s->block_len_trees = NULL;
968
969 BrotliInitBitReader(br, input, finish);
970
971 s->state = BROTLI_STATE_BITREADER_WARMUP;
972 /* No break, continue to next state */
973 case BROTLI_STATE_BITREADER_WARMUP:
974 if (!BrotliWarmupBitReader(br)) {
975 result = BROTLI_RESULT_NEEDS_MORE_INPUT;
976 break;
977 }
978 /* Decode window size. */
979 s->window_bits = DecodeWindowBits(br);
980 s->max_backward_distance = (1 << s->window_bits) - 16;
981
982 s->ringbuffer_size = 1 << s->window_bits;
983 s->ringbuffer_mask = s->ringbuffer_size - 1;
984 s->ringbuffer = (uint8_t*)malloc((size_t)(s->ringbuffer_size +
985 kRingBufferWriteAheadSlack +
986 kMaxDictionaryWordLength));
987 if (!s->ringbuffer) {
988 result = BROTLI_RESULT_ERROR;
989 break;
990 }
991 s->ringbuffer_end = s->ringbuffer + s->ringbuffer_size;
992
993 s->block_type_trees = (HuffmanCode*)malloc(
994 3 * BROTLI_HUFFMAN_MAX_TABLE_SIZE * sizeof(HuffmanCode));
995 s->block_len_trees = (HuffmanCode*)malloc(
996 3 * BROTLI_HUFFMAN_MAX_TABLE_SIZE * sizeof(HuffmanCode));
997 if (s->block_type_trees == NULL || s->block_len_trees == NULL) {
998 result = BROTLI_RESULT_ERROR;
999 break;
1000 }
1001
1002 s->state = BROTLI_STATE_METABLOCK_BEGIN;
1003 /* No break, continue to next state */
1004 case BROTLI_STATE_METABLOCK_BEGIN:
1005 if (!BrotliReadMoreInput(br)) {
1006 result = BROTLI_RESULT_NEEDS_MORE_INPUT;
1007 break;
1008 }
1009 if (s->input_end) {
1010 s->partially_written = 0;
1011 s->state = BROTLI_STATE_DONE;
1012 break;
1013 }
1014 s->meta_block_remaining_len = 0;
1015 s->block_length[0] = 1 << 28;
1016 s->block_length[1] = 1 << 28;
1017 s->block_length[2] = 1 << 28;
1018 s->block_type[0] = 0;
1019 s->num_block_types[0] = 1;
1020 s->num_block_types[1] = 1;
1021 s->num_block_types[2] = 1;
1022 s->block_type_rb[0] = 0;
1023 s->block_type_rb[1] = 1;
1024 s->block_type_rb[2] = 0;
1025 s->block_type_rb[3] = 1;
1026 s->block_type_rb[4] = 0;
1027 s->block_type_rb[5] = 1;
1028 s->block_type_rb_index[0] = 0;
1029 s->context_map = NULL;
1030 s->context_modes = NULL;
1031 s->dist_context_map = NULL;
1032 s->context_offset = 0;
1033 s->context_map_slice = NULL;
1034 s->literal_htree_index = 0;
1035 s->dist_context_offset = 0;
1036 s->dist_context_map_slice = NULL;
1037 s->dist_htree_index = 0;
1038 s->context_lookup_offset1 = 0;
1039 s->context_lookup_offset2 = 0;
1040 for (i = 0; i < 3; ++i) {
1041 s->hgroup[i].codes = NULL;
1042 s->hgroup[i].htrees = NULL;
1043 }
1044 s->state = BROTLI_STATE_METABLOCK_HEADER_1;
1045 /* No break, continue to next state */
1046 case BROTLI_STATE_METABLOCK_HEADER_1:
1047 if (!BrotliReadMoreInput(br)) {
1048 result = BROTLI_RESULT_NEEDS_MORE_INPUT;
1049 break;
1050 }
1051 BROTLI_LOG_UINT(pos);
1052 if (!DecodeMetaBlockLength(br,
1053 &s->meta_block_remaining_len,
1054 &s->input_end,
1055 &s->is_metadata,
1056 &s->is_uncompressed)) {
1057 result = BROTLI_RESULT_ERROR;
1058 break;
1059 }
1060 BROTLI_LOG_UINT(s->meta_block_remaining_len);
1061 if (s->is_metadata) {
1062 if (!JumpToByteBoundary(&s->br)) {
1063 result = BROTLI_RESULT_ERROR;
1064 break;
1065 }
1066 s->state = BROTLI_STATE_METADATA;
1067 break;
1068 }
1069 if (s->meta_block_remaining_len == 0) {
1070 s->state = BROTLI_STATE_METABLOCK_DONE;
1071 break;
1072 }
1073 if (s->is_uncompressed) {
1074 if (!JumpToByteBoundary(&s->br)) {
1075 result = BROTLI_RESULT_ERROR;
1076 break;
1077 }
1078 s->state = BROTLI_STATE_UNCOMPRESSED;
1079 break;
1080 }
1081 i = 0;
1082 s->state = BROTLI_STATE_HUFFMAN_CODE_0;
1083 break;
1084 case BROTLI_STATE_UNCOMPRESSED:
1085 initial_remaining_len = s->meta_block_remaining_len;
1086 /* pos is given as argument since s->pos is only updated at the end. */
1087 result = CopyUncompressedBlockToOutput(output, pos, s);
1088 if (result == BROTLI_RESULT_NEEDS_MORE_OUTPUT) {
1089 break;
1090 }
1091 bytes_copied = initial_remaining_len - s->meta_block_remaining_len;
1092 pos += bytes_copied;
1093 if (bytes_copied > 0) {
1094 s->prev_byte2 = bytes_copied == 1 ? s->prev_byte1 :
1095 s->ringbuffer[(pos - 2) & s->ringbuffer_mask];
1096 s->prev_byte1 = s->ringbuffer[(pos - 1) & s->ringbuffer_mask];
1097 }
1098 if (result != BROTLI_RESULT_SUCCESS) break;
1099 s->state = BROTLI_STATE_METABLOCK_DONE;
1100 break;
1101 case BROTLI_STATE_METADATA:
1102 for (; s->meta_block_remaining_len > 0; --s->meta_block_remaining_len) {
1103 if (!BrotliReadMoreInput(&s->br)) {
1104 result = BROTLI_RESULT_NEEDS_MORE_INPUT;
1105 break;
1106 }
1107 /* Read one byte and ignore it. */
1108 BrotliReadBits(&s->br, 8);
1109 }
1110 s->state = BROTLI_STATE_METABLOCK_DONE;
1111 break;
1112 case BROTLI_STATE_HUFFMAN_CODE_0:
1113 if (i >= 3) {
1114 BROTLI_LOG_UINT(s->num_block_types[0]);
1115 BROTLI_LOG_UINT(s->num_block_types[1]);
1116 BROTLI_LOG_UINT(s->num_block_types[2]);
1117 BROTLI_LOG_UINT(s->block_length[0]);
1118 BROTLI_LOG_UINT(s->block_length[1]);
1119 BROTLI_LOG_UINT(s->block_length[2]);
1120
1121 s->state = BROTLI_STATE_METABLOCK_HEADER_2;
1122 break;
1123 }
1124 s->num_block_types[i] = DecodeVarLenUint8(br) + 1;
1125 s->state = BROTLI_STATE_HUFFMAN_CODE_1;
1126 /* No break, continue to next state */
1127 case BROTLI_STATE_HUFFMAN_CODE_1:
1128 if (s->num_block_types[i] >= 2) {
1129 result = ReadHuffmanCode(s->num_block_types[i] + 2,
1130 &s->block_type_trees[i * BROTLI_HUFFMAN_MAX_TABLE_SIZE],
1131 NULL, s);
1132 if (result != BROTLI_RESULT_SUCCESS) break;
1133 s->state = BROTLI_STATE_HUFFMAN_CODE_2;
1134 } else {
1135 i++;
1136 s->state = BROTLI_STATE_HUFFMAN_CODE_0;
1137 break;
1138 }
1139 /* No break, continue to next state */
1140 case BROTLI_STATE_HUFFMAN_CODE_2:
1141 result = ReadHuffmanCode(kNumBlockLengthCodes,
1142 &s->block_len_trees[i * BROTLI_HUFFMAN_MAX_TABLE_SIZE],
1143 NULL, s);
1144 if (result != BROTLI_RESULT_SUCCESS) break;
1145 s->block_length[i] = ReadBlockLength(
1146 &s->block_len_trees[i * BROTLI_HUFFMAN_MAX_TABLE_SIZE], br);
1147 s->block_type_rb_index[i] = 1;
1148 i++;
1149 s->state = BROTLI_STATE_HUFFMAN_CODE_0;
1150 break;
1151 case BROTLI_STATE_METABLOCK_HEADER_2:
1152 if (!BrotliReadMoreInput(br)) {
1153 result = BROTLI_RESULT_NEEDS_MORE_INPUT;
1154 break;
1155 }
1156 s->distance_postfix_bits = (int)BrotliReadBits(br, 2);
1157 s->num_direct_distance_codes = NUM_DISTANCE_SHORT_CODES +
1158 ((int)BrotliReadBits(br, 4) << s->distance_postfix_bits);
1159 s->distance_postfix_mask = (1 << s->distance_postfix_bits) - 1;
1160 s->num_distance_codes = (s->num_direct_distance_codes +
1161 (48 << s->distance_postfix_bits));
1162 s->context_modes = (uint8_t*)malloc((size_t)s->num_block_types[0]);
1163 if (s->context_modes == 0) {
1164 result = BROTLI_RESULT_ERROR;
1165 break;
1166 }
1167 for (i = 0; i < s->num_block_types[0]; ++i) {
1168 s->context_modes[i] = (uint8_t)(BrotliReadBits(br, 2) << 1);
1169 BROTLI_LOG_ARRAY_INDEX(s->context_modes, i);
1170 }
1171 BROTLI_LOG_UINT(s->num_direct_distance_codes);
1172 BROTLI_LOG_UINT(s->distance_postfix_bits);
1173 s->state = BROTLI_STATE_CONTEXT_MAP_1;
1174 /* No break, continue to next state */
1175 case BROTLI_STATE_CONTEXT_MAP_1:
1176 result = DecodeContextMap(s->num_block_types[0] << kLiteralContextBits,
1177 &s->num_literal_htrees, &s->context_map, s);
1178
1179 s->trivial_literal_context = 1;
1180 for (i = 0; i < s->num_block_types[0] << kLiteralContextBits; i++) {
1181 if (s->context_map[i] != i >> kLiteralContextBits) {
1182 s->trivial_literal_context = 0;
1183 break;
1184 }
1185 }
1186
1187 if (result != BROTLI_RESULT_SUCCESS) break;
1188 s->state = BROTLI_STATE_CONTEXT_MAP_2;
1189 /* No break, continue to next state */
1190 case BROTLI_STATE_CONTEXT_MAP_2:
1191 result = DecodeContextMap(s->num_block_types[2] << kDistanceContextBits,
1192 &s->num_dist_htrees, &s->dist_context_map, s);
1193 if (result != BROTLI_RESULT_SUCCESS) break;
1194
1195 BrotliHuffmanTreeGroupInit(&s->hgroup[0], kNumLiteralCodes,
1196 s->num_literal_htrees);
1197 BrotliHuffmanTreeGroupInit(&s->hgroup[1], kNumInsertAndCopyCodes,
1198 s->num_block_types[1]);
1199 BrotliHuffmanTreeGroupInit(&s->hgroup[2], s->num_distance_codes,
1200 s->num_dist_htrees);
1201 i = 0;
1202 s->state = BROTLI_STATE_TREE_GROUP;
1203 /* No break, continue to next state */
1204 case BROTLI_STATE_TREE_GROUP:
1205 result = HuffmanTreeGroupDecode(&s->hgroup[i], s);
1206 if (result != BROTLI_RESULT_SUCCESS) break;
1207 i++;
1208
1209 if (i >= 3) {
1210 s->context_map_slice = s->context_map;
1211 s->dist_context_map_slice = s->dist_context_map;
1212 s->context_mode = s->context_modes[s->block_type[0]];
1213 s->context_lookup_offset1 = kContextLookupOffsets[s->context_mode];
1214 s->context_lookup_offset2 =
1215 kContextLookupOffsets[s->context_mode + 1];
1216 s->htree_command = s->hgroup[1].htrees[0];
1217
1218 s->state = BROTLI_STATE_BLOCK_BEGIN;
1219 break;
1220 }
1221
1222 break;
1223 case BROTLI_STATE_BLOCK_BEGIN:
1224 /* Block decoding is the inner loop, jumping with goto makes it 3% faster */
1225 BlockBegin:
1226 if (!BrotliReadMoreInput(br)) {
1227 result = BROTLI_RESULT_NEEDS_MORE_INPUT;
1228 break;
1229 }
1230 if (s->meta_block_remaining_len <= 0) {
1231 /* Protect pos from overflow, wrap it around at every GB of input. */
1232 pos &= 0x3fffffff;
1233
1234 /* Next metablock, if any */
1235 s->state = BROTLI_STATE_METABLOCK_DONE;
1236 break;
1237 }
1238
1239 if (s->block_length[1] == 0) {
1240 DecodeBlockType(s->num_block_types[1],
1241 s->block_type_trees, 1,
1242 s->block_type, s->block_type_rb,
1243 s->block_type_rb_index, br);
1244 s->block_length[1] = ReadBlockLength(
1245 &s->block_len_trees[BROTLI_HUFFMAN_MAX_TABLE_SIZE], br);
1246 s->htree_command = s->hgroup[1].htrees[s->block_type[1]];
1247 }
1248 --s->block_length[1];
1249 s->cmd_code = ReadSymbol(s->htree_command, br);
1250 s->range_idx = s->cmd_code >> 6;
1251 if (s->range_idx >= 2) {
1252 s->range_idx -= 2;
1253 s->distance_code = -1;
1254 } else {
1255 s->distance_code = 0;
1256 }
1257 s->insert_code =
1258 kInsertRangeLut[s->range_idx] + ((s->cmd_code >> 3) & 7);
1259 s->copy_code = kCopyRangeLut[s->range_idx] + (s->cmd_code & 7);
1260 s->insert_length = kInsertLengthPrefixCode[s->insert_code].offset +
1261 (int)BrotliReadBits(br,
1262 kInsertLengthPrefixCode[s->insert_code].nbits);
1263 s->copy_length = kCopyLengthPrefixCode[s->copy_code].offset +
1264 (int)BrotliReadBits(br, kCopyLengthPrefixCode[s->copy_code].nbits);
1265 BROTLI_LOG_UINT(s->insert_length);
1266 BROTLI_LOG_UINT(s->copy_length);
1267 BROTLI_LOG_UINT(s->distance_code);
1268
1269 i = 0;
1270 s->state = BROTLI_STATE_BLOCK_INNER;
1271 /* No break, go to next state */
1272 case BROTLI_STATE_BLOCK_INNER:
1273 if (s->trivial_literal_context) {
1274 while (i < s->insert_length) {
1275 if (!BrotliReadMoreInput(br)) {
1276 result = BROTLI_RESULT_NEEDS_MORE_INPUT;
1277 break;
1278 }
1279 if (s->block_length[0] == 0) {
1280 DecodeBlockTypeWithContext(s, br);
1281 }
1282
1283 s->ringbuffer[pos & s->ringbuffer_mask] = (uint8_t)ReadSymbol(
1284 s->hgroup[0].htrees[s->literal_htree_index], br);
1285
1286 --s->block_length[0];
1287 BROTLI_LOG_UINT(s->literal_htree_index);
1288 BROTLI_LOG_ARRAY_INDEX(s->ringbuffer, pos & s->ringbuffer_mask);
1289 if ((pos & s->ringbuffer_mask) == s->ringbuffer_mask) {
1290 s->partially_written = 0;
1291 s->state = BROTLI_STATE_BLOCK_INNER_WRITE;
1292 break;
1293 }
1294 /* Modifications to this code shold be reflected in
1295 BROTLI_STATE_BLOCK_INNER_WRITE case */
1296 ++pos;
1297 ++i;
1298 }
1299 } else {
1300 while (i < s->insert_length) {
1301 if (!BrotliReadMoreInput(br)) {
1302 result = BROTLI_RESULT_NEEDS_MORE_INPUT;
1303 break;
1304 }
1305 if (s->block_length[0] == 0) {
1306 DecodeBlockTypeWithContext(s, br);
1307 }
1308
1309 context =
1310 (kContextLookup[s->context_lookup_offset1 + s->prev_byte1] |
1311 kContextLookup[s->context_lookup_offset2 + s->prev_byte2]);
1312 BROTLI_LOG_UINT(context);
1313 s->literal_htree_index = s->context_map_slice[context];
1314 --s->block_length[0];
1315 s->prev_byte2 = s->prev_byte1;
1316 s->prev_byte1 = (uint8_t)ReadSymbol(
1317 s->hgroup[0].htrees[s->literal_htree_index], br);
1318 s->ringbuffer[pos & s->ringbuffer_mask] = s->prev_byte1;
1319 BROTLI_LOG_UINT(s->literal_htree_index);
1320 BROTLI_LOG_ARRAY_INDEX(s->ringbuffer, pos & s->ringbuffer_mask);
1321 if ((pos & s->ringbuffer_mask) == s->ringbuffer_mask) {
1322 s->partially_written = 0;
1323 s->state = BROTLI_STATE_BLOCK_INNER_WRITE;
1324 break;
1325 }
1326 /* Modifications to this code shold be reflected in
1327 BROTLI_STATE_BLOCK_INNER_WRITE case */
1328 ++pos;
1329 ++i;
1330 }
1331 }
1332 if (result != BROTLI_RESULT_SUCCESS ||
1333 s->state == BROTLI_STATE_BLOCK_INNER_WRITE) break;
1334
1335 s->meta_block_remaining_len -= s->insert_length;
1336 if (s->meta_block_remaining_len <= 0) {
1337 s->state = BROTLI_STATE_METABLOCK_DONE;
1338 break;
1339 } else if (s->distance_code < 0) {
1340 s->state = BROTLI_STATE_BLOCK_DISTANCE;
1341 } else {
1342 s->state = BROTLI_STATE_BLOCK_POST;
1343 break;
1344 }
1345 /* No break, go to next state */
1346 case BROTLI_STATE_BLOCK_DISTANCE:
1347 if (!BrotliReadMoreInput(br)) {
1348 result = BROTLI_RESULT_NEEDS_MORE_INPUT;
1349 break;
1350 }
1351 assert(s->distance_code < 0);
1352
1353 if (s->block_length[2] == 0) {
1354 DecodeBlockType(s->num_block_types[2],
1355 s->block_type_trees, 2,
1356 s->block_type, s->block_type_rb,
1357 s->block_type_rb_index, br);
1358 s->block_length[2] = ReadBlockLength(
1359 &s->block_len_trees[2 * BROTLI_HUFFMAN_MAX_TABLE_SIZE], br);
1360 s->dist_context_offset = s->block_type[2] << kDistanceContextBits;
1361 s->dist_context_map_slice =
1362 s->dist_context_map + s->dist_context_offset;
1363 }
1364 --s->block_length[2];
1365 context = (uint8_t)(s->copy_length > 4 ? 3 : s->copy_length - 2);
1366 s->dist_htree_index = s->dist_context_map_slice[context];
1367 s->distance_code =
1368 ReadSymbol(s->hgroup[2].htrees[s->dist_htree_index], br);
1369 if (s->distance_code >= s->num_direct_distance_codes) {
1370 int nbits;
1371 int postfix;
1372 int offset;
1373 s->distance_code -= s->num_direct_distance_codes;
1374 postfix = s->distance_code & s->distance_postfix_mask;
1375 s->distance_code >>= s->distance_postfix_bits;
1376 nbits = (s->distance_code >> 1) + 1;
1377 offset = ((2 + (s->distance_code & 1)) << nbits) - 4;
1378 s->distance_code = s->num_direct_distance_codes +
1379 ((offset + (int)BrotliReadBits(br, nbits)) <<
1380 s->distance_postfix_bits) + postfix;
1381 }
1382 s->state = BROTLI_STATE_BLOCK_POST;
1383 /* No break, go to next state */
1384 case BROTLI_STATE_BLOCK_POST:
1385 if (!BrotliReadMoreInput(br)) {
1386 result = BROTLI_RESULT_NEEDS_MORE_INPUT;
1387 break;
1388 }
1389 /* Convert the distance code to the actual distance by possibly */
1390 /* looking up past distnaces from the s->ringbuffer. */
1391 s->distance =
1392 TranslateShortCodes(s->distance_code, s->dist_rb, s->dist_rb_idx);
1393 if (s->distance < 0) {
1394 result = BROTLI_RESULT_ERROR;
1395 break;
1396 }
1397 BROTLI_LOG_UINT(s->distance);
1398
1399 if (pos < s->max_backward_distance &&
1400 s->max_distance != s->max_backward_distance) {
1401 s->max_distance = pos;
1402 } else {
1403 s->max_distance = s->max_backward_distance;
1404 }
1405
1406 s->copy_dst = &s->ringbuffer[pos & s->ringbuffer_mask];
1407
1408 if (s->distance > s->max_distance) {
1409 if (s->copy_length >= kMinDictionaryWordLength &&
1410 s->copy_length <= kMaxDictionaryWordLength) {
1411 int offset = kBrotliDictionaryOffsetsByLength[s->copy_length];
1412 int word_id = s->distance - s->max_distance - 1;
1413 int shift = kBrotliDictionarySizeBitsByLength[s->copy_length];
1414 int mask = (1 << shift) - 1;
1415 int word_idx = word_id & mask;
1416 int transform_idx = word_id >> shift;
1417 offset += word_idx * s->copy_length;
1418 if (transform_idx < kNumTransforms) {
1419 const uint8_t* word = &kBrotliDictionary[offset];
1420 int len = TransformDictionaryWord(
1421 s->copy_dst, word, s->copy_length, transform_idx);
1422 s->copy_dst += len;
1423 pos += len;
1424 s->meta_block_remaining_len -= len;
1425 if (s->copy_dst >= s->ringbuffer_end) {
1426 s->partially_written = 0;
1427 num_written = BrotliWrite(output, s->ringbuffer,
1428 (size_t)s->ringbuffer_size);
1429 if (num_written < 0) {
1430 result = BROTLI_RESULT_ERROR;
1431 break;
1432 }
1433 s->partially_written += num_written;
1434 if (s->partially_written < s->ringbuffer_size) {
1435 result = BROTLI_RESULT_NEEDS_MORE_OUTPUT;
1436 s->state = BROTLI_STATE_BLOCK_POST_WRITE_1;
1437 break;
1438 }
1439 /* Modifications to this code shold be reflected in
1440 BROTLI_STATE_BLOCK_POST_WRITE_1 case */
1441 memcpy(s->ringbuffer, s->ringbuffer_end,
1442 (size_t)(s->copy_dst - s->ringbuffer_end));
1443 }
1444 } else {
1445 printf("Invalid backward reference. pos: %d distance: %d "
1446 "len: %d bytes left: %d\n",
1447 pos, s->distance, s->copy_length,
1448 s->meta_block_remaining_len);
1449 result = BROTLI_RESULT_ERROR;
1450 break;
1451 }
1452 } else {
1453 printf("Invalid backward reference. pos: %d distance: %d "
1454 "len: %d bytes left: %d\n", pos, s->distance, s->copy_length,
1455 s->meta_block_remaining_len);
1456 result = BROTLI_RESULT_ERROR;
1457 break;
1458 }
1459 } else {
1460 if (s->distance_code > 0) {
1461 s->dist_rb[s->dist_rb_idx & 3] = s->distance;
1462 ++s->dist_rb_idx;
1463 }
1464
1465 if (s->copy_length > s->meta_block_remaining_len) {
1466 printf("Invalid backward reference. pos: %d distance: %d "
1467 "len: %d bytes left: %d\n", pos, s->distance, s->copy_length,
1468 s->meta_block_remaining_len);
1469 result = BROTLI_RESULT_ERROR;
1470 break;
1471 }
1472
1473 s->copy_src =
1474 &s->ringbuffer[(pos - s->distance) & s->ringbuffer_mask];
1475
1476 #if (defined(__x86_64__) || defined(_M_X64))
1477 if (s->copy_src + s->copy_length <= s->ringbuffer_end &&
1478 s->copy_dst + s->copy_length < s->ringbuffer_end) {
1479 if (s->copy_length <= 16 && s->distance >= 8) {
1480 UNALIGNED_COPY64(s->copy_dst, s->copy_src);
1481 UNALIGNED_COPY64(s->copy_dst + 8, s->copy_src + 8);
1482 } else {
1483 IncrementalCopyFastPath(s->copy_dst, s->copy_src, s->copy_length);
1484 }
1485 pos += s->copy_length;
1486 s->meta_block_remaining_len -= s->copy_length;
1487 s->copy_length = 0;
1488 }
1489 #endif
1490 /* Modifications to this loop shold be reflected in
1491 BROTLI_STATE_BLOCK_POST_WRITE_2 case */
1492 for (i = 0; i < s->copy_length; ++i) {
1493 s->ringbuffer[pos & s->ringbuffer_mask] =
1494 s->ringbuffer[(pos - s->distance) & s->ringbuffer_mask];
1495 if ((pos & s->ringbuffer_mask) == s->ringbuffer_mask) {
1496 s->partially_written = 0;
1497 num_written = BrotliWrite(output, s->ringbuffer,
1498 (size_t)s->ringbuffer_size);
1499 if (num_written < 0) {
1500 result = BROTLI_RESULT_ERROR;
1501 break;
1502 }
1503 s->partially_written += num_written;
1504 if (s->partially_written < s->ringbuffer_size) {
1505 result = BROTLI_RESULT_NEEDS_MORE_OUTPUT;
1506 s->state = BROTLI_STATE_BLOCK_POST_WRITE_2;
1507 break;
1508 }
1509 }
1510 ++pos;
1511 --s->meta_block_remaining_len;
1512 }
1513 if (result == BROTLI_RESULT_NEEDS_MORE_OUTPUT) {
1514 break;
1515 }
1516 }
1517 /* No break, continue to next state */
1518 case BROTLI_STATE_BLOCK_POST_CONTINUE:
1519 /* When we get here, we must have inserted at least one literal and */
1520 /* made a copy of at least length two, therefore accessing the last 2 */
1521 /* bytes is valid. */
1522 s->prev_byte1 = s->ringbuffer[(pos - 1) & s->ringbuffer_mask];
1523 s->prev_byte2 = s->ringbuffer[(pos - 2) & s->ringbuffer_mask];
1524 s->state = BROTLI_STATE_BLOCK_BEGIN;
1525 goto BlockBegin;
1526 case BROTLI_STATE_BLOCK_INNER_WRITE:
1527 case BROTLI_STATE_BLOCK_POST_WRITE_1:
1528 case BROTLI_STATE_BLOCK_POST_WRITE_2:
1529 num_written = BrotliWrite(
1530 output, s->ringbuffer + s->partially_written,
1531 (size_t)(s->ringbuffer_size - s->partially_written));
1532 if (num_written < 0) {
1533 result = BROTLI_RESULT_ERROR;
1534 break;
1535 }
1536 s->partially_written += num_written;
1537 if (s->partially_written < s->ringbuffer_size) {
1538 result = BROTLI_RESULT_NEEDS_MORE_OUTPUT;
1539 break;
1540 }
1541 if (s->state == BROTLI_STATE_BLOCK_POST_WRITE_1) {
1542 memcpy(s->ringbuffer, s->ringbuffer_end,
1543 (size_t)(s->copy_dst - s->ringbuffer_end));
1544 s->state = BROTLI_STATE_BLOCK_POST_CONTINUE;
1545 } else if (s->state == BROTLI_STATE_BLOCK_POST_WRITE_2) {
1546 /* The tail of "i < s->copy_length" loop. */
1547 ++pos;
1548 --s->meta_block_remaining_len;
1549 ++i;
1550 /* Reenter the loop. */
1551 for (; i < s->copy_length; ++i) {
1552 s->ringbuffer[pos & s->ringbuffer_mask] =
1553 s->ringbuffer[(pos - s->distance) & s->ringbuffer_mask];
1554 if ((pos & s->ringbuffer_mask) == s->ringbuffer_mask) {
1555 s->partially_written = 0;
1556 num_written = BrotliWrite(output, s->ringbuffer,
1557 (size_t)s->ringbuffer_size);
1558 if (num_written < 0) {
1559 result = BROTLI_RESULT_ERROR;
1560 break;
1561 }
1562 s->partially_written += num_written;
1563 if (s->partially_written < s->ringbuffer_size) {
1564 result = BROTLI_RESULT_NEEDS_MORE_OUTPUT;
1565 break;
1566 }
1567 }
1568 ++pos;
1569 --s->meta_block_remaining_len;
1570 }
1571 if (result == BROTLI_RESULT_NEEDS_MORE_OUTPUT) {
1572 break;
1573 }
1574 s->state = BROTLI_STATE_BLOCK_POST_CONTINUE;
1575 } else { /* BROTLI_STATE_BLOCK_INNER_WRITE */
1576 /* The tail of "i < s->insert_length" loop. */
1577 ++pos;
1578 ++i;
1579 s->state = BROTLI_STATE_BLOCK_INNER;
1580 }
1581 break;
1582 case BROTLI_STATE_METABLOCK_DONE:
1583 if (s->context_modes != 0) {
1584 free(s->context_modes);
1585 s->context_modes = NULL;
1586 }
1587 if (s->context_map != 0) {
1588 free(s->context_map);
1589 s->context_map = NULL;
1590 }
1591 if (s->dist_context_map != 0) {
1592 free(s->dist_context_map);
1593 s->dist_context_map = NULL;
1594 }
1595 for (i = 0; i < 3; ++i) {
1596 BrotliHuffmanTreeGroupRelease(&s->hgroup[i]);
1597 s->hgroup[i].codes = NULL;
1598 s->hgroup[i].htrees = NULL;
1599 }
1600 s->state = BROTLI_STATE_METABLOCK_BEGIN;
1601 break;
1602 case BROTLI_STATE_DONE:
1603 if (s->ringbuffer != 0) {
1604 num_written = BrotliWrite(
1605 output, s->ringbuffer + s->partially_written,
1606 (size_t)((pos & s->ringbuffer_mask) - s->partially_written));
1607 if (num_written < 0) {
1608 result = BROTLI_RESULT_ERROR;
1609 }
1610 s->partially_written += num_written;
1611 if (s->partially_written < (pos & s->ringbuffer_mask)) {
1612 result = BROTLI_RESULT_NEEDS_MORE_OUTPUT;
1613 break;
1614 }
1615 }
1616 if (!JumpToByteBoundary(&s->br)) {
1617 result = BROTLI_RESULT_ERROR;
1618 }
1619 return result;
1620 default:
1621 printf("Unknown state %d\n", s->state);
1622 result = BROTLI_RESULT_ERROR;
1623 }
1624 }
1625
1626 s->pos = pos;
1627 s->loop_counter = i;
1628 return result;
1629 }
1630
1631 #if defined(__cplusplus) || defined(c_plusplus)
1632 } /* extern "C" */
1633 #endif