Lines Matching +full:implicit +full:- +full:fall +full:- +full:through
43 - doing up to two 16-byte copies for fast backward copying
44 - inserting transformed dictionary word:
63 if (state->state != BROTLI_STATE_UNINITED) return BROTLI_FALSE; in BrotliDecoderSetParameter()
66 state->canny_ringbuffer_allocation = !!value ? 0 : 1; in BrotliDecoderSetParameter()
70 state->large_window = TO_BROTLI_BOOL(!!value); in BrotliDecoderSetParameter()
106 brotli_free_func free_func = state->free_func; in BrotliDecoderDestroyInstance()
107 void* opaque = state->memory_manager_opaque; in BrotliDecoderDestroyInstance()
116 s->error_code = (int)e; in SaveErrorCode()
132 /* Decodes WBITS by reading 1 - 7 bits, or 0x11 for "Large Window Brotli".
133 Precondition: bit-reader accumulator has at least 8 bits. */
137 BROTLI_BOOL large_window = s->large_window; in DecodeWindowBits()
138 s->large_window = BROTLI_FALSE; in DecodeWindowBits()
141 s->window_bits = 16; in DecodeWindowBits()
146 s->window_bits = 17 + n; in DecodeWindowBits()
156 s->large_window = BROTLI_TRUE; in DecodeWindowBits()
163 s->window_bits = 8 + n; in DecodeWindowBits()
166 s->window_bits = 17; in DecodeWindowBits()
180 /* Decodes a number in the range [0..255], by reading 1 - 11 bits. */
184 switch (s->substate_decode_uint8) { in DecodeVarLenUint8()
193 /* Fall through. */ in DecodeVarLenUint8()
197 s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_SHORT; in DecodeVarLenUint8()
202 s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_NONE; in DecodeVarLenUint8()
207 /* Fall through. */ in DecodeVarLenUint8()
211 s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_LONG; in DecodeVarLenUint8()
215 s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_NONE; in DecodeVarLenUint8()
224 /* Decodes a metablock length and flags by reading 2 - 31 bits. */
230 switch (s->substate_metablock_header) { in DecodeMetaBlockLength()
235 s->is_last_metablock = bits ? 1 : 0; in DecodeMetaBlockLength()
236 s->meta_block_remaining_len = 0; in DecodeMetaBlockLength()
237 s->is_uncompressed = 0; in DecodeMetaBlockLength()
238 s->is_metadata = 0; in DecodeMetaBlockLength()
239 if (!s->is_last_metablock) { in DecodeMetaBlockLength()
240 s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NIBBLES; in DecodeMetaBlockLength()
243 s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_EMPTY; in DecodeMetaBlockLength()
244 /* Fall through. */ in DecodeMetaBlockLength()
251 s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE; in DecodeMetaBlockLength()
254 s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NIBBLES; in DecodeMetaBlockLength()
255 /* Fall through. */ in DecodeMetaBlockLength()
261 s->size_nibbles = (uint8_t)(bits + 4); in DecodeMetaBlockLength()
262 s->loop_counter = 0; in DecodeMetaBlockLength()
264 s->is_metadata = 1; in DecodeMetaBlockLength()
265 s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_RESERVED; in DecodeMetaBlockLength()
268 s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_SIZE; in DecodeMetaBlockLength()
269 /* Fall through. */ in DecodeMetaBlockLength()
272 i = s->loop_counter; in DecodeMetaBlockLength()
273 for (; i < (int)s->size_nibbles; ++i) { in DecodeMetaBlockLength()
275 s->loop_counter = i; in DecodeMetaBlockLength()
278 if (i + 1 == (int)s->size_nibbles && s->size_nibbles > 4 && in DecodeMetaBlockLength()
282 s->meta_block_remaining_len |= (int)(bits << (i * 4)); in DecodeMetaBlockLength()
284 s->substate_metablock_header = in DecodeMetaBlockLength()
286 /* Fall through. */ in DecodeMetaBlockLength()
289 if (!s->is_last_metablock) { in DecodeMetaBlockLength()
293 s->is_uncompressed = bits ? 1 : 0; in DecodeMetaBlockLength()
295 ++s->meta_block_remaining_len; in DecodeMetaBlockLength()
296 s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE; in DecodeMetaBlockLength()
306 s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_BYTES; in DecodeMetaBlockLength()
307 /* Fall through. */ in DecodeMetaBlockLength()
314 s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE; in DecodeMetaBlockLength()
317 s->size_nibbles = (uint8_t)bits; in DecodeMetaBlockLength()
318 s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_METADATA; in DecodeMetaBlockLength()
319 /* Fall through. */ in DecodeMetaBlockLength()
322 i = s->loop_counter; in DecodeMetaBlockLength()
323 for (; i < (int)s->size_nibbles; ++i) { in DecodeMetaBlockLength()
325 s->loop_counter = i; in DecodeMetaBlockLength()
328 if (i + 1 == (int)s->size_nibbles && s->size_nibbles > 1 && in DecodeMetaBlockLength()
333 s->meta_block_remaining_len |= (int)(bits << (i * 8)); in DecodeMetaBlockLength()
335 ++s->meta_block_remaining_len; in DecodeMetaBlockLength()
336 s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE; in DecodeMetaBlockLength()
356 uint32_t nbits = BROTLI_HC_FAST_LOAD_BITS(table) - HUFFMAN_TABLE_BITS; in DecodeSymbol()
366 /* Reads and decodes the next Huffman code from bit-stream.
367 This method peeks 16 bits of input and drops 0 - 15 of them. */
404 available_bits -= HUFFMAN_TABLE_BITS; in SafeDecodeSymbol()
425 /* Makes a look-up in first level Huffman table. Peeks 8 bits. */
441 Reads 0 - 15 bits. Also peeks 8 following bits. */
450 uint32_t mask = BitMask((*bits - HUFFMAN_TABLE_BITS)); in ReadPreloadedSymbol()
472 /* Reads (s->symbol + 1) symbols.
479 BrotliBitReader* br = &s->br; in ReadSimpleHuffmanSymbols()
480 BrotliMetablockHeaderArena* h = &s->arena.header; in ReadSimpleHuffmanSymbols()
481 uint32_t max_bits = Log2Floor(alphabet_size_max - 1); in ReadSimpleHuffmanSymbols()
482 uint32_t i = h->sub_loop_counter; in ReadSimpleHuffmanSymbols()
483 uint32_t num_symbols = h->symbol; in ReadSimpleHuffmanSymbols()
487 h->sub_loop_counter = i; in ReadSimpleHuffmanSymbols()
488 h->substate_huffman = BROTLI_STATE_HUFFMAN_SIMPLE_READ; in ReadSimpleHuffmanSymbols()
495 h->symbols_lists_array[i] = (uint16_t)v; in ReadSimpleHuffmanSymbols()
496 BROTLI_LOG_UINT(h->symbols_lists_array[i]); in ReadSimpleHuffmanSymbols()
503 if (h->symbols_lists_array[i] == h->symbols_lists_array[k]) { in ReadSimpleHuffmanSymbols()
515 C) extend corresponding index-chain
527 *space -= 32768U >> code_len; in ProcessSingleCodeLength()
538 symbol-skip
563 *repeat -= 2; in ProcessRepeatedCodeLength()
567 repeat_delta = *repeat - old_repeat; in ProcessRepeatedCodeLength()
575 (int)*symbol, (int)(*symbol + repeat_delta - 1), (int)*repeat_code_len)); in ProcessRepeatedCodeLength()
584 *space -= repeat_delta << (15 - *repeat_code_len); in ProcessRepeatedCodeLength()
595 BrotliBitReader* br = &s->br; in ReadSymbolCodeLengths()
596 BrotliMetablockHeaderArena* h = &s->arena.header; in ReadSymbolCodeLengths()
597 uint32_t symbol = h->symbol; in ReadSymbolCodeLengths()
598 uint32_t repeat = h->repeat; in ReadSymbolCodeLengths()
599 uint32_t space = h->space; in ReadSymbolCodeLengths()
600 uint32_t prev_code_len = h->prev_code_len; in ReadSymbolCodeLengths()
601 uint32_t repeat_code_len = h->repeat_code_len; in ReadSymbolCodeLengths()
602 uint16_t* symbol_lists = h->symbol_lists; in ReadSymbolCodeLengths()
603 uint16_t* code_length_histo = h->code_length_histo; in ReadSymbolCodeLengths()
604 int* next_symbol = h->next_symbol; in ReadSymbolCodeLengths()
609 const HuffmanCode* p = h->table; in ReadSymbolCodeLengths()
613 h->symbol = symbol; in ReadSymbolCodeLengths()
614 h->repeat = repeat; in ReadSymbolCodeLengths()
615 h->prev_code_len = prev_code_len; in ReadSymbolCodeLengths()
616 h->repeat_code_len = repeat_code_len; in ReadSymbolCodeLengths()
617 h->space = space; in ReadSymbolCodeLengths()
639 h->space = space; in ReadSymbolCodeLengths()
645 BrotliBitReader* br = &s->br; in SafeReadSymbolCodeLengths()
646 BrotliMetablockHeaderArena* h = &s->arena.header; in SafeReadSymbolCodeLengths()
648 while (h->symbol < alphabet_size && h->space > 0) { in SafeReadSymbolCodeLengths()
649 const HuffmanCode* p = h->table; in SafeReadSymbolCodeLengths()
669 ProcessSingleCodeLength(code_len, &h->symbol, &h->repeat, &h->space, in SafeReadSymbolCodeLengths()
670 &h->prev_code_len, h->symbol_lists, h->code_length_histo, in SafeReadSymbolCodeLengths()
671 h->next_symbol); in SafeReadSymbolCodeLengths()
673 uint32_t extra_bits = code_len - 14U; in SafeReadSymbolCodeLengths()
682 &h->symbol, &h->repeat, &h->space, &h->prev_code_len, in SafeReadSymbolCodeLengths()
683 &h->repeat_code_len, h->symbol_lists, h->code_length_histo, in SafeReadSymbolCodeLengths()
684 h->next_symbol); in SafeReadSymbolCodeLengths()
693 BrotliBitReader* br = &s->br; in ReadCodeLengthCodeLengths()
694 BrotliMetablockHeaderArena* h = &s->arena.header; in ReadCodeLengthCodeLengths()
695 uint32_t num_codes = h->repeat; in ReadCodeLengthCodeLengths()
696 unsigned space = h->space; in ReadCodeLengthCodeLengths()
697 uint32_t i = h->sub_loop_counter; in ReadCodeLengthCodeLengths()
710 h->sub_loop_counter = i; in ReadCodeLengthCodeLengths()
711 h->repeat = num_codes; in ReadCodeLengthCodeLengths()
712 h->space = space; in ReadCodeLengthCodeLengths()
713 h->substate_huffman = BROTLI_STATE_HUFFMAN_COMPLEX; in ReadCodeLengthCodeLengths()
719 h->code_length_code_lengths[code_len_idx] = (uint8_t)v; in ReadCodeLengthCodeLengths()
720 BROTLI_LOG_ARRAY_INDEX(h->code_length_code_lengths, code_len_idx); in ReadCodeLengthCodeLengths()
722 space = space - (32U >> v); in ReadCodeLengthCodeLengths()
724 ++h->code_length_histo[v]; in ReadCodeLengthCodeLengths()
725 if (space - 1U >= 32U) { in ReadCodeLengthCodeLengths()
741 For this scenario 4 - 49 bits will be read.
743 B) 2-phase decoding:
745 encoded with predefined entropy code. 32 - 74 bits are used.
753 BrotliBitReader* br = &s->br; in ReadHuffmanCode()
754 BrotliMetablockHeaderArena* h = &s->arena.header; in ReadHuffmanCode()
757 switch (h->substate_huffman) { in ReadHuffmanCode()
759 if (!BrotliSafeReadBits(br, 2, &h->sub_loop_counter)) { in ReadHuffmanCode()
762 BROTLI_LOG_UINT(h->sub_loop_counter); in ReadHuffmanCode()
766 if (h->sub_loop_counter != 1) { in ReadHuffmanCode()
767 h->space = 32; in ReadHuffmanCode()
768 h->repeat = 0; /* num_codes */ in ReadHuffmanCode()
769 memset(&h->code_length_histo[0], 0, sizeof(h->code_length_histo[0]) * in ReadHuffmanCode()
771 memset(&h->code_length_code_lengths[0], 0, in ReadHuffmanCode()
772 sizeof(h->code_length_code_lengths)); in ReadHuffmanCode()
773 h->substate_huffman = BROTLI_STATE_HUFFMAN_COMPLEX; in ReadHuffmanCode()
776 /* Fall through. */ in ReadHuffmanCode()
780 if (!BrotliSafeReadBits(br, 2, &h->symbol)) { /* num_symbols */ in ReadHuffmanCode()
781 h->substate_huffman = BROTLI_STATE_HUFFMAN_SIMPLE_SIZE; in ReadHuffmanCode()
784 h->sub_loop_counter = 0; in ReadHuffmanCode()
785 /* Fall through. */ in ReadHuffmanCode()
794 /* Fall through. */ in ReadHuffmanCode()
798 if (h->symbol == 3) { in ReadHuffmanCode()
801 h->substate_huffman = BROTLI_STATE_HUFFMAN_SIMPLE_BUILD; in ReadHuffmanCode()
804 h->symbol += bits; in ReadHuffmanCode()
806 BROTLI_LOG_UINT(h->symbol); in ReadHuffmanCode()
808 table, HUFFMAN_TABLE_BITS, h->symbols_lists_array, h->symbol); in ReadHuffmanCode()
812 h->substate_huffman = BROTLI_STATE_HUFFMAN_NONE; in ReadHuffmanCode()
816 /* Decode Huffman-coded code lengths. */ in ReadHuffmanCode()
823 BrotliBuildCodeLengthsHuffmanTable(h->table, in ReadHuffmanCode()
824 h->code_length_code_lengths, in ReadHuffmanCode()
825 h->code_length_histo); in ReadHuffmanCode()
826 memset(&h->code_length_histo[0], 0, sizeof(h->code_length_histo)); in ReadHuffmanCode()
828 h->next_symbol[i] = (int)i - (BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1); in ReadHuffmanCode()
829 h->symbol_lists[h->next_symbol[i]] = 0xFFFF; in ReadHuffmanCode()
832 h->symbol = 0; in ReadHuffmanCode()
833 h->prev_code_len = BROTLI_INITIAL_REPEATED_CODE_LENGTH; in ReadHuffmanCode()
834 h->repeat = 0; in ReadHuffmanCode()
835 h->repeat_code_len = 0; in ReadHuffmanCode()
836 h->space = 32768; in ReadHuffmanCode()
837 h->substate_huffman = BROTLI_STATE_HUFFMAN_LENGTH_SYMBOLS; in ReadHuffmanCode()
839 /* Fall through. */ in ReadHuffmanCode()
852 if (h->space != 0) { in ReadHuffmanCode()
853 BROTLI_LOG(("[ReadHuffmanCode] space = %d\n", (int)h->space)); in ReadHuffmanCode()
857 table, HUFFMAN_TABLE_BITS, h->symbol_lists, h->code_length_histo); in ReadHuffmanCode()
861 h->substate_huffman = BROTLI_STATE_HUFFMAN_NONE; in ReadHuffmanCode()
888 if (s->substate_read_block_length == BROTLI_STATE_READ_BLOCK_LENGTH_NONE) { in SafeReadBlockLength()
893 index = s->block_length_index; in SafeReadBlockLength()
900 s->block_length_index = index; in SafeReadBlockLength()
901 s->substate_read_block_length = BROTLI_STATE_READ_BLOCK_LENGTH_SUFFIX; in SafeReadBlockLength()
905 s->substate_read_block_length = BROTLI_STATE_READ_BLOCK_LENGTH_NONE; in SafeReadBlockLength()
914 2.2) remove X-th element from L
923 inner for loop with do-while. */
928 uint32_t upper_bound = state->mtf_upper_bound; in InverseMoveToFrontTransform()
929 uint32_t* mtf = &state->mtf[1]; /* Make mtf[-1] addressable. */ in InverseMoveToFrontTransform()
931 /* Load endian-aware constant. */ in InverseMoveToFrontTransform()
951 mtf_u8[-1] = value; in InverseMoveToFrontTransform()
953 index--; in InverseMoveToFrontTransform()
958 state->mtf_upper_bound = upper_bound >> 2; in InverseMoveToFrontTransform()
964 BrotliMetablockHeaderArena* h = &s->arena.header; in HuffmanTreeGroupDecode()
965 if (h->substate_tree_group != BROTLI_STATE_TREE_GROUP_LOOP) { in HuffmanTreeGroupDecode()
966 h->next = group->codes; in HuffmanTreeGroupDecode()
967 h->htree_index = 0; in HuffmanTreeGroupDecode()
968 h->substate_tree_group = BROTLI_STATE_TREE_GROUP_LOOP; in HuffmanTreeGroupDecode()
970 while (h->htree_index < group->num_htrees) { in HuffmanTreeGroupDecode()
972 BrotliDecoderErrorCode result = ReadHuffmanCode(group->alphabet_size_max, in HuffmanTreeGroupDecode()
973 group->alphabet_size_limit, h->next, &table_size, s); in HuffmanTreeGroupDecode()
975 group->htrees[h->htree_index] = h->next; in HuffmanTreeGroupDecode()
976 h->next += table_size; in HuffmanTreeGroupDecode()
977 ++h->htree_index; in HuffmanTreeGroupDecode()
979 h->substate_tree_group = BROTLI_STATE_TREE_GROUP_NONE; in HuffmanTreeGroupDecode()
989 3) Read context map items; "0" values could be run-length encoded.
995 BrotliBitReader* br = &s->br; in DecodeContextMap()
997 BrotliMetablockHeaderArena* h = &s->arena.header; in DecodeContextMap()
999 switch ((int)h->substate_context_map) { in DecodeContextMap()
1006 h->context_index = 0; in DecodeContextMap()
1018 h->substate_context_map = BROTLI_STATE_CONTEXT_MAP_READ_PREFIX; in DecodeContextMap()
1019 /* Fall through. */ in DecodeContextMap()
1029 h->max_run_length_prefix = (bits >> 1) + 1; in DecodeContextMap()
1032 h->max_run_length_prefix = 0; in DecodeContextMap()
1035 BROTLI_LOG_UINT(h->max_run_length_prefix); in DecodeContextMap()
1036 h->substate_context_map = BROTLI_STATE_CONTEXT_MAP_HUFFMAN; in DecodeContextMap()
1038 /* Fall through. */ in DecodeContextMap()
1041 uint32_t alphabet_size = *num_htrees + h->max_run_length_prefix; in DecodeContextMap()
1043 h->context_map_table, NULL, s); in DecodeContextMap()
1045 h->code = 0xFFFF; in DecodeContextMap()
1046 h->substate_context_map = BROTLI_STATE_CONTEXT_MAP_DECODE; in DecodeContextMap()
1048 /* Fall through. */ in DecodeContextMap()
1051 uint32_t context_index = h->context_index; in DecodeContextMap()
1052 uint32_t max_run_length_prefix = h->max_run_length_prefix; in DecodeContextMap()
1054 uint32_t code = h->code; in DecodeContextMap()
1058 if (!SafeReadSymbol(h->context_map_table, br, &code)) { in DecodeContextMap()
1059 h->code = 0xFFFF; in DecodeContextMap()
1060 h->context_index = context_index; in DecodeContextMap()
1071 (uint8_t)(code - max_run_length_prefix); in DecodeContextMap()
1077 /* RLE sub-stage. */ in DecodeContextMap()
1081 h->code = code; in DecodeContextMap()
1082 h->context_index = context_index; in DecodeContextMap()
1093 } while (--reps); in DecodeContextMap()
1097 /* Fall through. */ in DecodeContextMap()
1102 h->substate_context_map = BROTLI_STATE_CONTEXT_MAP_TRANSFORM; in DecodeContextMap()
1108 h->substate_context_map = BROTLI_STATE_CONTEXT_MAP_NONE; in DecodeContextMap()
1118 /* Decodes a command or literal and updates block type ring-buffer.
1122 uint32_t max_block_type = s->num_block_types[tree_type]; in DecodeBlockTypeAndLength()
1123 const HuffmanCode* type_tree = &s->block_type_trees[ in DecodeBlockTypeAndLength()
1125 const HuffmanCode* len_tree = &s->block_len_trees[ in DecodeBlockTypeAndLength()
1127 BrotliBitReader* br = &s->br; in DecodeBlockTypeAndLength()
1128 uint32_t* ringbuffer = &s->block_type_rb[tree_type * 2]; in DecodeBlockTypeAndLength()
1137 s->block_length[tree_type] = ReadBlockLength(len_tree, br); in DecodeBlockTypeAndLength()
1142 if (!SafeReadBlockLength(s, &s->block_length[tree_type], len_tree, br)) { in DecodeBlockTypeAndLength()
1143 s->substate_read_block_length = BROTLI_STATE_READ_BLOCK_LENGTH_NONE; in DecodeBlockTypeAndLength()
1154 block_type -= 2; in DecodeBlockTypeAndLength()
1157 block_type -= max_block_type; in DecodeBlockTypeAndLength()
1167 for (i = 0; i < 8; ++i) s->trivial_literal_contexts[i] = 0; in DetectTrivialLiteralBlockTypes()
1168 for (i = 0; i < s->num_block_types[0]; i++) { in DetectTrivialLiteralBlockTypes()
1171 size_t sample = s->context_map[offset]; in DetectTrivialLiteralBlockTypes()
1174 BROTLI_REPEAT(4, error |= s->context_map[offset + j++] ^ sample;) in DetectTrivialLiteralBlockTypes()
1177 s->trivial_literal_contexts[i >> 5] |= 1u << (i & 31); in DetectTrivialLiteralBlockTypes()
1185 uint32_t block_type = s->block_type_rb[1]; in PrepareLiteralDecoding()
1187 s->context_map_slice = s->context_map + context_offset; in PrepareLiteralDecoding()
1188 trivial = s->trivial_literal_contexts[block_type >> 5]; in PrepareLiteralDecoding()
1189 s->trivial_literal_context = (trivial >> (block_type & 31)) & 1; in PrepareLiteralDecoding()
1190 s->literal_htree = s->literal_hgroup.htrees[s->context_map_slice[0]]; in PrepareLiteralDecoding()
1191 context_mode = s->context_modes[block_type] & 3; in PrepareLiteralDecoding()
1192 s->context_lookup = BROTLI_CONTEXT_LUT(context_mode); in PrepareLiteralDecoding()
1222 s->htree_command = s->insert_copy_hgroup.htrees[s->block_type_rb[3]]; in DecodeCommandBlockSwitchInternal()
1242 s->dist_context_map_slice = s->dist_context_map + in DecodeDistanceBlockSwitchInternal()
1243 (s->block_type_rb[5] << BROTLI_DISTANCE_CONTEXT_BITS); in DecodeDistanceBlockSwitchInternal()
1244 s->dist_htree_index = s->dist_context_map_slice[s->distance_context]; in DecodeDistanceBlockSwitchInternal()
1258 size_t pos = wrap && s->pos > s->ringbuffer_size ? in UnwrittenBytes()
1259 (size_t)s->ringbuffer_size : (size_t)(s->pos); in UnwrittenBytes()
1260 size_t partial_pos_rb = (s->rb_roundtrips * (size_t)s->ringbuffer_size) + pos; in UnwrittenBytes()
1261 return partial_pos_rb - s->partial_pos_out; in UnwrittenBytes()
1266 and either ring-buffer is as big as window size, or |force| is true. */
1271 s->ringbuffer + (s->partial_pos_out & (size_t)s->ringbuffer_mask); in WriteRingBuffer()
1277 if (s->meta_block_remaining_len < 0) { in WriteRingBuffer()
1288 *available_out -= num_written; in WriteRingBuffer()
1291 s->partial_pos_out += num_written; in WriteRingBuffer()
1293 *total_out = s->partial_pos_out; in WriteRingBuffer()
1296 if (s->ringbuffer_size == (1 << s->window_bits) || force) { in WriteRingBuffer()
1303 if (s->ringbuffer_size == (1 << s->window_bits) && in WriteRingBuffer()
1304 s->pos >= s->ringbuffer_size) { in WriteRingBuffer()
1305 s->pos -= s->ringbuffer_size; in WriteRingBuffer()
1306 s->rb_roundtrips++; in WriteRingBuffer()
1307 s->should_wrap_ringbuffer = (size_t)s->pos != 0 ? 1 : 0; in WriteRingBuffer()
1313 if (s->should_wrap_ringbuffer) { in WrapRingBuffer()
1314 memcpy(s->ringbuffer, s->ringbuffer_end, (size_t)s->pos); in WrapRingBuffer()
1315 s->should_wrap_ringbuffer = 0; in WrapRingBuffer()
1319 /* Allocates ring-buffer.
1321 s->ringbuffer_size MUST be updated by BrotliCalculateRingBufferSize before
1324 Last two bytes of ring-buffer are initialized to 0, so context calculation
1328 uint8_t* old_ringbuffer = s->ringbuffer; in BrotliEnsureRingBuffer()
1329 if (s->ringbuffer_size == s->new_ringbuffer_size) { in BrotliEnsureRingBuffer()
1333 s->ringbuffer = (uint8_t*)BROTLI_DECODER_ALLOC(s, in BrotliEnsureRingBuffer()
1334 (size_t)(s->new_ringbuffer_size) + kRingBufferWriteAheadSlack); in BrotliEnsureRingBuffer()
1335 if (s->ringbuffer == 0) { in BrotliEnsureRingBuffer()
1337 s->ringbuffer = old_ringbuffer; in BrotliEnsureRingBuffer()
1340 s->ringbuffer[s->new_ringbuffer_size - 2] = 0; in BrotliEnsureRingBuffer()
1341 s->ringbuffer[s->new_ringbuffer_size - 1] = 0; in BrotliEnsureRingBuffer()
1344 memcpy(s->ringbuffer, old_ringbuffer, (size_t)s->pos); in BrotliEnsureRingBuffer()
1348 s->ringbuffer_size = s->new_ringbuffer_size; in BrotliEnsureRingBuffer()
1349 s->ringbuffer_mask = s->new_ringbuffer_size - 1; in BrotliEnsureRingBuffer()
1350 s->ringbuffer_end = s->ringbuffer + s->ringbuffer_size; in BrotliEnsureRingBuffer()
1365 switch (s->substate_uncompressed) { in CopyUncompressedBlockToOutput()
1367 int nbytes = (int)BrotliGetRemainingBytes(&s->br); in CopyUncompressedBlockToOutput()
1368 if (nbytes > s->meta_block_remaining_len) { in CopyUncompressedBlockToOutput()
1369 nbytes = s->meta_block_remaining_len; in CopyUncompressedBlockToOutput()
1371 if (s->pos + nbytes > s->ringbuffer_size) { in CopyUncompressedBlockToOutput()
1372 nbytes = s->ringbuffer_size - s->pos; in CopyUncompressedBlockToOutput()
1374 /* Copy remaining bytes from s->br.buf_ to ring-buffer. */ in CopyUncompressedBlockToOutput()
1375 BrotliCopyBytes(&s->ringbuffer[s->pos], &s->br, (size_t)nbytes); in CopyUncompressedBlockToOutput()
1376 s->pos += nbytes; in CopyUncompressedBlockToOutput()
1377 s->meta_block_remaining_len -= nbytes; in CopyUncompressedBlockToOutput()
1378 if (s->pos < 1 << s->window_bits) { in CopyUncompressedBlockToOutput()
1379 if (s->meta_block_remaining_len == 0) { in CopyUncompressedBlockToOutput()
1384 s->substate_uncompressed = BROTLI_STATE_UNCOMPRESSED_WRITE; in CopyUncompressedBlockToOutput()
1386 /* Fall through. */ in CopyUncompressedBlockToOutput()
1395 if (s->ringbuffer_size == 1 << s->window_bits) { in CopyUncompressedBlockToOutput()
1396 s->max_distance = s->max_backward_distance; in CopyUncompressedBlockToOutput()
1398 s->substate_uncompressed = BROTLI_STATE_UNCOMPRESSED_NONE; in CopyUncompressedBlockToOutput()
1414 int window_size = 1 << s->window_bits; in BrotliCalculateRingBufferSize()
1418 int min_size = s->ringbuffer_size ? s->ringbuffer_size : 1024; in BrotliCalculateRingBufferSize()
1422 if (s->ringbuffer_size == window_size) { in BrotliCalculateRingBufferSize()
1427 if (s->is_metadata) { in BrotliCalculateRingBufferSize()
1431 if (!s->ringbuffer) { in BrotliCalculateRingBufferSize()
1434 output_size = s->pos; in BrotliCalculateRingBufferSize()
1436 output_size += s->meta_block_remaining_len; in BrotliCalculateRingBufferSize()
1439 if (!!s->canny_ringbuffer_allocation) { in BrotliCalculateRingBufferSize()
1448 s->new_ringbuffer_size = new_ringbuffer_size; in BrotliCalculateRingBufferSize()
1451 /* Reads 1..256 2-bit context modes. */
1453 BrotliBitReader* br = &s->br; in ReadContextModes()
1454 int i = s->loop_counter; in ReadContextModes()
1456 while (i < (int)s->num_block_types[0]) { in ReadContextModes()
1459 s->loop_counter = i; in ReadContextModes()
1462 s->context_modes[i] = (uint8_t)bits; in ReadContextModes()
1463 BROTLI_LOG_ARRAY_INDEX(s->context_modes, i); in ReadContextModes()
1470 int offset = s->distance_code - 3; in TakeDistanceFromRingBuffer()
1471 if (s->distance_code <= 3) { in TakeDistanceFromRingBuffer()
1472 /* Compensate double distance-ring-buffer roll for dictionary items. */ in TakeDistanceFromRingBuffer()
1473 s->distance_context = 1 >> s->distance_code; in TakeDistanceFromRingBuffer()
1474 s->distance_code = s->dist_rb[(s->dist_rb_idx - offset) & 3]; in TakeDistanceFromRingBuffer()
1475 s->dist_rb_idx -= s->distance_context; in TakeDistanceFromRingBuffer()
1479 int base = s->distance_code - 10; in TakeDistanceFromRingBuffer()
1480 if (s->distance_code < 10) { in TakeDistanceFromRingBuffer()
1481 base = s->distance_code - 4; in TakeDistanceFromRingBuffer()
1485 /* Unpack one of six 4-bit values. */ in TakeDistanceFromRingBuffer()
1486 delta = ((0x605142 >> (4 * base)) & 0xF) - 3; in TakeDistanceFromRingBuffer()
1487 s->distance_code = s->dist_rb[(s->dist_rb_idx + index_delta) & 0x3] + delta; in TakeDistanceFromRingBuffer()
1488 if (s->distance_code <= 0) { in TakeDistanceFromRingBuffer()
1491 s->distance_code = 0x7FFFFFFF; in TakeDistanceFromRingBuffer()
1522 NDIRECT (0..120) ... are encoded in the meta-block header...
1529 [ xcode = dcode - NDIRECT - 16 ]
1538 ... to get the actual value of the parameter NDIRECT, left-shift this
1539 four-bit number by NPOSTFIX bits ...
1547 postfix = xcode & ((1 << NPOSTFIX) - 1)
1548 range_start = 2 * (1 << ndistbits - 1 - 1)
1552 NB: ndistbits >= 1 -> range_start >= 0
1554 NB: extra -1 offset in range_start formula covers the absence of
1558 In other words, xcode has the following binary structure - XXXHPPP:
1559 - XXX represent the number of extra distance bits
1560 - H selects upper / lower range of distances
1561 - PPP represent "postfix"
1577 NDISTBITS and OFFSET could be pre-calculated, as NDIRECT and NPOSTFIX could
1578 change only once per meta-block.
1584 BrotliMetablockBodyArena* b = &s->arena.body; in CalculateDistanceLut()
1585 uint32_t npostfix = s->distance_postfix_bits; in CalculateDistanceLut()
1586 uint32_t ndirect = s->num_direct_distance_codes; in CalculateDistanceLut()
1587 uint32_t alphabet_size_limit = s->distance_hgroup.alphabet_size_limit; in CalculateDistanceLut()
1598 b->dist_extra_bits[i] = 0; in CalculateDistanceLut()
1599 b->dist_offset[i] = j + 1; in CalculateDistanceLut()
1605 uint32_t base = ndirect + ((((2 + half) << bits) - 4) << npostfix) + 1; in CalculateDistanceLut()
1608 b->dist_extra_bits[i] = (uint8_t)bits; in CalculateDistanceLut()
1609 b->dist_offset[i] = base + j; in CalculateDistanceLut()
1617 /* Precondition: s->distance_code < 0. */
1620 BrotliMetablockBodyArena* b = &s->arena.body; in ReadDistanceInternal()
1624 HuffmanCode* distance_tree = s->distance_hgroup.htrees[s->dist_htree_index]; in ReadDistanceInternal()
1633 --s->block_length[2]; in ReadDistanceInternal()
1635 looking up past distances from the s->dist_rb. */ in ReadDistanceInternal()
1636 s->distance_context = 0; in ReadDistanceInternal()
1638 s->distance_code = (int)code; in ReadDistanceInternal()
1643 bits = BrotliReadBits32(br, b->dist_extra_bits[code]); in ReadDistanceInternal()
1645 if (!SafeReadBits32(br, b->dist_extra_bits[code], &bits)) { in ReadDistanceInternal()
1646 ++s->block_length[2]; in ReadDistanceInternal()
1651 s->distance_code = in ReadDistanceInternal()
1652 (int)(b->dist_offset[code] + (bits << s->distance_postfix_bits)); in ReadDistanceInternal()
1674 cmd_code = ReadSymbol(s->htree_command, br); in ReadCommandInternal()
1677 if (!SafeReadSymbol(s->htree_command, br, &cmd_code)) { in ReadCommandInternal()
1682 s->distance_code = v.distance_code; in ReadCommandInternal()
1683 s->distance_context = v.context; in ReadCommandInternal()
1684 s->dist_htree_index = s->dist_context_map_slice[s->distance_context]; in ReadCommandInternal()
1698 s->copy_length = (int)copy_length + v.copy_len_offset; in ReadCommandInternal()
1699 --s->block_length[1]; in ReadCommandInternal()
1736 int pos = s->pos; in ProcessCommandsInternal()
1737 int i = s->loop_counter; in ProcessCommandsInternal()
1739 BrotliBitReader* br = &s->br; in ProcessCommandsInternal()
1750 if (s->state == BROTLI_STATE_COMMAND_BEGIN) { in ProcessCommandsInternal()
1752 } else if (s->state == BROTLI_STATE_COMMAND_INNER) { in ProcessCommandsInternal()
1754 } else if (s->state == BROTLI_STATE_COMMAND_POST_DECODE_LITERALS) { in ProcessCommandsInternal()
1756 } else if (s->state == BROTLI_STATE_COMMAND_POST_WRAP_COPY) { in ProcessCommandsInternal()
1764 s->state = BROTLI_STATE_COMMAND_BEGIN; in ProcessCommandsInternal()
1767 s->state = BROTLI_STATE_COMMAND_BEGIN; in ProcessCommandsInternal()
1771 if (BROTLI_PREDICT_FALSE(s->block_length[1] == 0)) { in ProcessCommandsInternal()
1778 pos, i, s->copy_length)); in ProcessCommandsInternal()
1782 s->meta_block_remaining_len -= i; in ProcessCommandsInternal()
1786 s->state = BROTLI_STATE_COMMAND_INNER; in ProcessCommandsInternal()
1789 if (s->trivial_literal_context) { in ProcessCommandsInternal()
1792 PreloadSymbol(safe, s->literal_htree, br, &bits, &value); in ProcessCommandsInternal()
1795 s->state = BROTLI_STATE_COMMAND_INNER; in ProcessCommandsInternal()
1799 if (BROTLI_PREDICT_FALSE(s->block_length[0] == 0)) { in ProcessCommandsInternal()
1801 PreloadSymbol(safe, s->literal_htree, br, &bits, &value); in ProcessCommandsInternal()
1802 if (!s->trivial_literal_context) goto CommandInner; in ProcessCommandsInternal()
1805 s->ringbuffer[pos] = in ProcessCommandsInternal()
1806 (uint8_t)ReadPreloadedSymbol(s->literal_htree, br, &bits, &value); in ProcessCommandsInternal()
1809 if (!SafeReadSymbol(s->literal_htree, br, &literal)) { in ProcessCommandsInternal()
1813 s->ringbuffer[pos] = (uint8_t)literal; in ProcessCommandsInternal()
1815 --s->block_length[0]; in ProcessCommandsInternal()
1816 BROTLI_LOG_ARRAY_INDEX(s->ringbuffer, pos); in ProcessCommandsInternal()
1818 if (BROTLI_PREDICT_FALSE(pos == s->ringbuffer_size)) { in ProcessCommandsInternal()
1819 s->state = BROTLI_STATE_COMMAND_INNER_WRITE; in ProcessCommandsInternal()
1820 --i; in ProcessCommandsInternal()
1823 } while (--i != 0); in ProcessCommandsInternal()
1825 uint8_t p1 = s->ringbuffer[(pos - 1) & s->ringbuffer_mask]; in ProcessCommandsInternal()
1826 uint8_t p2 = s->ringbuffer[(pos - 2) & s->ringbuffer_mask]; in ProcessCommandsInternal()
1831 s->state = BROTLI_STATE_COMMAND_INNER; in ProcessCommandsInternal()
1835 if (BROTLI_PREDICT_FALSE(s->block_length[0] == 0)) { in ProcessCommandsInternal()
1837 if (s->trivial_literal_context) goto CommandInner; in ProcessCommandsInternal()
1839 context = BROTLI_CONTEXT(p1, p2, s->context_lookup); in ProcessCommandsInternal()
1841 hc = s->literal_hgroup.htrees[s->context_map_slice[context]]; in ProcessCommandsInternal()
1853 s->ringbuffer[pos] = p1; in ProcessCommandsInternal()
1854 --s->block_length[0]; in ProcessCommandsInternal()
1855 BROTLI_LOG_UINT(s->context_map_slice[context]); in ProcessCommandsInternal()
1856 BROTLI_LOG_ARRAY_INDEX(s->ringbuffer, pos & s->ringbuffer_mask); in ProcessCommandsInternal()
1858 if (BROTLI_PREDICT_FALSE(pos == s->ringbuffer_size)) { in ProcessCommandsInternal()
1859 s->state = BROTLI_STATE_COMMAND_INNER_WRITE; in ProcessCommandsInternal()
1860 --i; in ProcessCommandsInternal()
1863 } while (--i != 0); in ProcessCommandsInternal()
1865 BROTLI_LOG_UINT(s->meta_block_remaining_len); in ProcessCommandsInternal()
1866 if (BROTLI_PREDICT_FALSE(s->meta_block_remaining_len <= 0)) { in ProcessCommandsInternal()
1867 s->state = BROTLI_STATE_METABLOCK_DONE; in ProcessCommandsInternal()
1873 s->state = BROTLI_STATE_COMMAND_POST_DECODE_LITERALS; in ProcessCommandsInternal()
1875 if (s->distance_code >= 0) { in ProcessCommandsInternal()
1876 /* Implicit distance case. */ in ProcessCommandsInternal()
1877 s->distance_context = s->distance_code ? 0 : 1; in ProcessCommandsInternal()
1878 --s->dist_rb_idx; in ProcessCommandsInternal()
1879 s->distance_code = s->dist_rb[s->dist_rb_idx & 3]; in ProcessCommandsInternal()
1882 if (BROTLI_PREDICT_FALSE(s->block_length[2] == 0)) { in ProcessCommandsInternal()
1888 pos, s->distance_code)); in ProcessCommandsInternal()
1889 if (s->max_distance != s->max_backward_distance) { in ProcessCommandsInternal()
1890 s->max_distance = in ProcessCommandsInternal()
1891 (pos < s->max_backward_distance) ? pos : s->max_backward_distance; in ProcessCommandsInternal()
1893 i = s->copy_length; in ProcessCommandsInternal()
1894 /* Apply copy of LZ77 back-reference, or static dictionary reference if in ProcessCommandsInternal()
1896 if (s->distance_code > s->max_distance) { in ProcessCommandsInternal()
1900 if (s->distance_code > BROTLI_MAX_ALLOWED_DISTANCE) { in ProcessCommandsInternal()
1903 pos, s->distance_code, i, s->meta_block_remaining_len)); in ProcessCommandsInternal()
1908 int address = s->distance_code - s->max_distance - 1; in ProcessCommandsInternal()
1909 const BrotliDictionary* words = s->dictionary; in ProcessCommandsInternal()
1910 const BrotliTransforms* transforms = s->transforms; in ProcessCommandsInternal()
1911 int offset = (int)s->dictionary->offsets_by_length[i]; in ProcessCommandsInternal()
1912 uint32_t shift = s->dictionary->size_bits_by_length[i]; in ProcessCommandsInternal()
1917 /* Compensate double distance-ring-buffer roll. */ in ProcessCommandsInternal()
1918 s->dist_rb_idx += s->distance_context; in ProcessCommandsInternal()
1920 if (BROTLI_PREDICT_FALSE(!words->data)) { in ProcessCommandsInternal()
1923 if (transform_idx < (int)transforms->num_transforms) { in ProcessCommandsInternal()
1924 const uint8_t* word = &words->data[offset]; in ProcessCommandsInternal()
1926 if (transform_idx == transforms->cutOffTransforms[0]) { in ProcessCommandsInternal()
1927 memcpy(&s->ringbuffer[pos], word, (size_t)len); in ProcessCommandsInternal()
1931 len = BrotliTransformDictionaryWord(&s->ringbuffer[pos], word, len, in ProcessCommandsInternal()
1935 i, word, transform_idx, len, &s->ringbuffer[pos])); in ProcessCommandsInternal()
1938 s->meta_block_remaining_len -= len; in ProcessCommandsInternal()
1939 if (pos >= s->ringbuffer_size) { in ProcessCommandsInternal()
1940 s->state = BROTLI_STATE_COMMAND_POST_WRITE_1; in ProcessCommandsInternal()
1946 pos, s->distance_code, i, s->meta_block_remaining_len)); in ProcessCommandsInternal()
1952 pos, s->distance_code, i, s->meta_block_remaining_len)); in ProcessCommandsInternal()
1956 int src_start = (pos - s->distance_code) & s->ringbuffer_mask; in ProcessCommandsInternal()
1957 uint8_t* copy_dst = &s->ringbuffer[pos]; in ProcessCommandsInternal()
1958 uint8_t* copy_src = &s->ringbuffer[src_start]; in ProcessCommandsInternal()
1962 s->dist_rb[s->dist_rb_idx & 3] = s->distance_code; in ProcessCommandsInternal()
1963 ++s->dist_rb_idx; in ProcessCommandsInternal()
1964 s->meta_block_remaining_len -= i; in ProcessCommandsInternal()
1965 /* There are 32+ bytes of slack in the ring-buffer allocation. in ProcessCommandsInternal()
1967 in the ring-buffer. Let's copy over them as a first guess. */ in ProcessCommandsInternal()
1973 if (dst_end >= s->ringbuffer_size || src_end >= s->ringbuffer_size) { in ProcessCommandsInternal()
1980 memcpy(copy_dst + 16, copy_src + 16, (size_t)(i - 16)); in ProcessCommandsInternal()
1988 BROTLI_LOG_UINT(s->meta_block_remaining_len); in ProcessCommandsInternal()
1989 if (s->meta_block_remaining_len <= 0) { in ProcessCommandsInternal()
1991 s->state = BROTLI_STATE_METABLOCK_DONE; in ProcessCommandsInternal()
1998 int wrap_guard = s->ringbuffer_size - pos; in ProcessCommandsInternal()
1999 while (--i >= 0) { in ProcessCommandsInternal()
2000 s->ringbuffer[pos] = in ProcessCommandsInternal()
2001 s->ringbuffer[(pos - s->distance_code) & s->ringbuffer_mask]; in ProcessCommandsInternal()
2003 if (BROTLI_PREDICT_FALSE(--wrap_guard == 0)) { in ProcessCommandsInternal()
2004 s->state = BROTLI_STATE_COMMAND_POST_WRITE_2; in ProcessCommandsInternal()
2009 if (s->meta_block_remaining_len <= 0) { in ProcessCommandsInternal()
2011 s->state = BROTLI_STATE_METABLOCK_DONE; in ProcessCommandsInternal()
2018 s->pos = pos; in ProcessCommandsInternal()
2019 s->loop_counter = i; in ProcessCommandsInternal()
2059 - invalid input implies that the whole stream is invalid -> any amount of
2061 - when result is "needs more input", then at least one more byte is REQUIRED
2064 - when result is "needs more output" decoder MUST ensure that it doesn't
2067 - when result is "success" decoder MUST return all unused data back to input
2073 BrotliBitReader* br = &s->br; in BrotliDecoderDecompressStream()
2076 *total_out = s->partial_pos_out; in BrotliDecoderDecompressStream()
2079 if ((int)s->error_code < 0) { in BrotliDecoderDecompressStream()
2087 if (s->buffer_length == 0) { /* Just connect bit reader to input stream. */ in BrotliDecoderDecompressStream()
2088 br->avail_in = *available_in; in BrotliDecoderDecompressStream()
2089 br->next_in = *next_in; in BrotliDecoderDecompressStream()
2092 be required to complete the transaction -> reading more data must be in BrotliDecoderDecompressStream()
2093 done in a loop -> do it in a main loop. */ in BrotliDecoderDecompressStream()
2095 br->next_in = &s->buffer.u8[0]; in BrotliDecoderDecompressStream()
2102 if (s->ringbuffer != 0) { /* Pro-actively push output. */ in BrotliDecoderDecompressStream()
2105 /* WriteRingBuffer checks s->meta_block_remaining_len validity. */ in BrotliDecoderDecompressStream()
2111 if (s->buffer_length != 0) { /* Used with internal buffer. */ in BrotliDecoderDecompressStream()
2112 if (br->avail_in == 0) { in BrotliDecoderDecompressStream()
2115 is expanded byte-by-byte until it is enough to complete read. */ in BrotliDecoderDecompressStream()
2116 s->buffer_length = 0; in BrotliDecoderDecompressStream()
2119 br->avail_in = *available_in; in BrotliDecoderDecompressStream()
2120 br->next_in = *next_in; in BrotliDecoderDecompressStream()
2126 s->buffer.u8[s->buffer_length] = **next_in; in BrotliDecoderDecompressStream()
2127 s->buffer_length++; in BrotliDecoderDecompressStream()
2128 br->avail_in = s->buffer_length; in BrotliDecoderDecompressStream()
2130 (*available_in)--; in BrotliDecoderDecompressStream()
2138 *next_in = br->next_in; in BrotliDecoderDecompressStream()
2139 *available_in = br->avail_in; in BrotliDecoderDecompressStream()
2141 s->buffer.u8[s->buffer_length] = **next_in; in BrotliDecoderDecompressStream()
2142 s->buffer_length++; in BrotliDecoderDecompressStream()
2144 (*available_in)--; in BrotliDecoderDecompressStream()
2153 if (s->buffer_length != 0) { in BrotliDecoderDecompressStream()
2156 s->buffer_length = 0; in BrotliDecoderDecompressStream()
2162 *available_in = br->avail_in; in BrotliDecoderDecompressStream()
2163 *next_in = br->next_in; in BrotliDecoderDecompressStream()
2167 switch (s->state) { in BrotliDecoderDecompressStream()
2179 if (s->large_window) { in BrotliDecoderDecompressStream()
2180 s->state = BROTLI_STATE_LARGE_WINDOW_BITS; in BrotliDecoderDecompressStream()
2183 s->state = BROTLI_STATE_INITIALIZE; in BrotliDecoderDecompressStream()
2187 if (!BrotliSafeReadBits(br, 6, &s->window_bits)) { in BrotliDecoderDecompressStream()
2191 if (s->window_bits < BROTLI_LARGE_MIN_WBITS || in BrotliDecoderDecompressStream()
2192 s->window_bits > BROTLI_LARGE_MAX_WBITS) { in BrotliDecoderDecompressStream()
2196 s->state = BROTLI_STATE_INITIALIZE; in BrotliDecoderDecompressStream()
2197 /* Fall through. */ in BrotliDecoderDecompressStream()
2200 BROTLI_LOG_UINT(s->window_bits); in BrotliDecoderDecompressStream()
2202 s->max_backward_distance = (1 << s->window_bits) - BROTLI_WINDOW_GAP; in BrotliDecoderDecompressStream()
2205 s->block_type_trees = (HuffmanCode*)BROTLI_DECODER_ALLOC(s, in BrotliDecoderDecompressStream()
2208 if (s->block_type_trees == 0) { in BrotliDecoderDecompressStream()
2212 s->block_len_trees = in BrotliDecoderDecompressStream()
2213 s->block_type_trees + 3 * BROTLI_HUFFMAN_MAX_SIZE_258; in BrotliDecoderDecompressStream()
2215 s->state = BROTLI_STATE_METABLOCK_BEGIN; in BrotliDecoderDecompressStream()
2216 /* Fall through. */ in BrotliDecoderDecompressStream()
2220 BROTLI_LOG_UINT(s->pos); in BrotliDecoderDecompressStream()
2221 s->state = BROTLI_STATE_METABLOCK_HEADER; in BrotliDecoderDecompressStream()
2222 /* Fall through. */ in BrotliDecoderDecompressStream()
2225 result = DecodeMetaBlockLength(s, br); /* Reads 2 - 31 bits. */ in BrotliDecoderDecompressStream()
2229 BROTLI_LOG_UINT(s->is_last_metablock); in BrotliDecoderDecompressStream()
2230 BROTLI_LOG_UINT(s->meta_block_remaining_len); in BrotliDecoderDecompressStream()
2231 BROTLI_LOG_UINT(s->is_metadata); in BrotliDecoderDecompressStream()
2232 BROTLI_LOG_UINT(s->is_uncompressed); in BrotliDecoderDecompressStream()
2233 if (s->is_metadata || s->is_uncompressed) { in BrotliDecoderDecompressStream()
2239 if (s->is_metadata) { in BrotliDecoderDecompressStream()
2240 s->state = BROTLI_STATE_METADATA; in BrotliDecoderDecompressStream()
2243 if (s->meta_block_remaining_len == 0) { in BrotliDecoderDecompressStream()
2244 s->state = BROTLI_STATE_METABLOCK_DONE; in BrotliDecoderDecompressStream()
2248 if (s->is_uncompressed) { in BrotliDecoderDecompressStream()
2249 s->state = BROTLI_STATE_UNCOMPRESSED; in BrotliDecoderDecompressStream()
2252 s->state = BROTLI_STATE_BEFORE_COMPRESSED_METABLOCK_HEADER; in BrotliDecoderDecompressStream()
2253 /* Fall through. */ in BrotliDecoderDecompressStream()
2256 BrotliMetablockHeaderArena* h = &s->arena.header; in BrotliDecoderDecompressStream()
2257 s->loop_counter = 0; in BrotliDecoderDecompressStream()
2259 h->sub_loop_counter = 0; in BrotliDecoderDecompressStream()
2261 h->symbol_lists = in BrotliDecoderDecompressStream()
2262 &h->symbols_lists_array[BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1]; in BrotliDecoderDecompressStream()
2263 h->substate_huffman = BROTLI_STATE_HUFFMAN_NONE; in BrotliDecoderDecompressStream()
2264 h->substate_tree_group = BROTLI_STATE_TREE_GROUP_NONE; in BrotliDecoderDecompressStream()
2265 h->substate_context_map = BROTLI_STATE_CONTEXT_MAP_NONE; in BrotliDecoderDecompressStream()
2266 s->state = BROTLI_STATE_HUFFMAN_CODE_0; in BrotliDecoderDecompressStream()
2268 /* Fall through. */ in BrotliDecoderDecompressStream()
2271 if (s->loop_counter >= 3) { in BrotliDecoderDecompressStream()
2272 s->state = BROTLI_STATE_METABLOCK_HEADER_2; in BrotliDecoderDecompressStream()
2276 result = DecodeVarLenUint8(s, br, &s->num_block_types[s->loop_counter]); in BrotliDecoderDecompressStream()
2280 s->num_block_types[s->loop_counter]++; in BrotliDecoderDecompressStream()
2281 BROTLI_LOG_UINT(s->num_block_types[s->loop_counter]); in BrotliDecoderDecompressStream()
2282 if (s->num_block_types[s->loop_counter] < 2) { in BrotliDecoderDecompressStream()
2283 s->loop_counter++; in BrotliDecoderDecompressStream()
2286 s->state = BROTLI_STATE_HUFFMAN_CODE_1; in BrotliDecoderDecompressStream()
2287 /* Fall through. */ in BrotliDecoderDecompressStream()
2290 uint32_t alphabet_size = s->num_block_types[s->loop_counter] + 2; in BrotliDecoderDecompressStream()
2291 int tree_offset = s->loop_counter * BROTLI_HUFFMAN_MAX_SIZE_258; in BrotliDecoderDecompressStream()
2293 &s->block_type_trees[tree_offset], NULL, s); in BrotliDecoderDecompressStream()
2295 s->state = BROTLI_STATE_HUFFMAN_CODE_2; in BrotliDecoderDecompressStream()
2297 /* Fall through. */ in BrotliDecoderDecompressStream()
2301 int tree_offset = s->loop_counter * BROTLI_HUFFMAN_MAX_SIZE_26; in BrotliDecoderDecompressStream()
2303 &s->block_len_trees[tree_offset], NULL, s); in BrotliDecoderDecompressStream()
2305 s->state = BROTLI_STATE_HUFFMAN_CODE_3; in BrotliDecoderDecompressStream()
2307 /* Fall through. */ in BrotliDecoderDecompressStream()
2310 int tree_offset = s->loop_counter * BROTLI_HUFFMAN_MAX_SIZE_26; in BrotliDecoderDecompressStream()
2311 if (!SafeReadBlockLength(s, &s->block_length[s->loop_counter], in BrotliDecoderDecompressStream()
2312 &s->block_len_trees[tree_offset], br)) { in BrotliDecoderDecompressStream()
2316 BROTLI_LOG_UINT(s->block_length[s->loop_counter]); in BrotliDecoderDecompressStream()
2317 s->loop_counter++; in BrotliDecoderDecompressStream()
2318 s->state = BROTLI_STATE_HUFFMAN_CODE_0; in BrotliDecoderDecompressStream()
2328 s->state = BROTLI_STATE_METABLOCK_DONE; in BrotliDecoderDecompressStream()
2333 for (; s->meta_block_remaining_len > 0; --s->meta_block_remaining_len) { in BrotliDecoderDecompressStream()
2342 s->state = BROTLI_STATE_METABLOCK_DONE; in BrotliDecoderDecompressStream()
2352 s->distance_postfix_bits = bits & BitMask(2); in BrotliDecoderDecompressStream()
2354 s->num_direct_distance_codes = bits << s->distance_postfix_bits; in BrotliDecoderDecompressStream()
2355 BROTLI_LOG_UINT(s->num_direct_distance_codes); in BrotliDecoderDecompressStream()
2356 BROTLI_LOG_UINT(s->distance_postfix_bits); in BrotliDecoderDecompressStream()
2357 s->context_modes = in BrotliDecoderDecompressStream()
2358 (uint8_t*)BROTLI_DECODER_ALLOC(s, (size_t)s->num_block_types[0]); in BrotliDecoderDecompressStream()
2359 if (s->context_modes == 0) { in BrotliDecoderDecompressStream()
2363 s->loop_counter = 0; in BrotliDecoderDecompressStream()
2364 s->state = BROTLI_STATE_CONTEXT_MODES; in BrotliDecoderDecompressStream()
2366 /* Fall through. */ in BrotliDecoderDecompressStream()
2373 s->state = BROTLI_STATE_CONTEXT_MAP_1; in BrotliDecoderDecompressStream()
2374 /* Fall through. */ in BrotliDecoderDecompressStream()
2378 s->num_block_types[0] << BROTLI_LITERAL_CONTEXT_BITS, in BrotliDecoderDecompressStream()
2379 &s->num_literal_htrees, &s->context_map, s); in BrotliDecoderDecompressStream()
2384 s->state = BROTLI_STATE_CONTEXT_MAP_2; in BrotliDecoderDecompressStream()
2385 /* Fall through. */ in BrotliDecoderDecompressStream()
2388 uint32_t npostfix = s->distance_postfix_bits; in BrotliDecoderDecompressStream()
2389 uint32_t ndirect = s->num_direct_distance_codes; in BrotliDecoderDecompressStream()
2394 if (s->large_window) { in BrotliDecoderDecompressStream()
2402 s->num_block_types[2] << BROTLI_DISTANCE_CONTEXT_BITS, in BrotliDecoderDecompressStream()
2403 &s->num_dist_htrees, &s->dist_context_map, s); in BrotliDecoderDecompressStream()
2408 s, &s->literal_hgroup, BROTLI_NUM_LITERAL_SYMBOLS, in BrotliDecoderDecompressStream()
2409 BROTLI_NUM_LITERAL_SYMBOLS, s->num_literal_htrees); in BrotliDecoderDecompressStream()
2411 s, &s->insert_copy_hgroup, BROTLI_NUM_COMMAND_SYMBOLS, in BrotliDecoderDecompressStream()
2412 BROTLI_NUM_COMMAND_SYMBOLS, s->num_block_types[1]); in BrotliDecoderDecompressStream()
2414 s, &s->distance_hgroup, distance_alphabet_size_max, in BrotliDecoderDecompressStream()
2415 distance_alphabet_size_limit, s->num_dist_htrees); in BrotliDecoderDecompressStream()
2420 s->loop_counter = 0; in BrotliDecoderDecompressStream()
2421 s->state = BROTLI_STATE_TREE_GROUP; in BrotliDecoderDecompressStream()
2423 /* Fall through. */ in BrotliDecoderDecompressStream()
2427 switch (s->loop_counter) { in BrotliDecoderDecompressStream()
2428 case 0: hgroup = &s->literal_hgroup; break; in BrotliDecoderDecompressStream()
2429 case 1: hgroup = &s->insert_copy_hgroup; break; in BrotliDecoderDecompressStream()
2430 case 2: hgroup = &s->distance_hgroup; break; in BrotliDecoderDecompressStream()
2436 s->loop_counter++; in BrotliDecoderDecompressStream()
2437 if (s->loop_counter < 3) { in BrotliDecoderDecompressStream()
2440 s->state = BROTLI_STATE_BEFORE_COMPRESSED_METABLOCK_BODY; in BrotliDecoderDecompressStream()
2442 /* Fall through. */ in BrotliDecoderDecompressStream()
2446 s->dist_context_map_slice = s->dist_context_map; in BrotliDecoderDecompressStream()
2447 s->htree_command = s->insert_copy_hgroup.htrees[0]; in BrotliDecoderDecompressStream()
2453 s->state = BROTLI_STATE_COMMAND_BEGIN; in BrotliDecoderDecompressStream()
2454 /* Fall through. */ in BrotliDecoderDecompressStream()
2457 /* Fall through. */ in BrotliDecoderDecompressStream()
2459 /* Fall through. */ in BrotliDecoderDecompressStream()
2461 /* Fall through. */ in BrotliDecoderDecompressStream()
2470 /* Fall through. */ in BrotliDecoderDecompressStream()
2472 /* Fall through. */ in BrotliDecoderDecompressStream()
2480 if (s->ringbuffer_size == 1 << s->window_bits) { in BrotliDecoderDecompressStream()
2481 s->max_distance = s->max_backward_distance; in BrotliDecoderDecompressStream()
2483 if (s->state == BROTLI_STATE_COMMAND_POST_WRITE_1) { in BrotliDecoderDecompressStream()
2484 if (s->meta_block_remaining_len == 0) { in BrotliDecoderDecompressStream()
2486 s->state = BROTLI_STATE_METABLOCK_DONE; in BrotliDecoderDecompressStream()
2488 s->state = BROTLI_STATE_COMMAND_BEGIN; in BrotliDecoderDecompressStream()
2491 } else if (s->state == BROTLI_STATE_COMMAND_POST_WRITE_2) { in BrotliDecoderDecompressStream()
2492 s->state = BROTLI_STATE_COMMAND_POST_WRAP_COPY; in BrotliDecoderDecompressStream()
2494 if (s->loop_counter == 0) { in BrotliDecoderDecompressStream()
2495 if (s->meta_block_remaining_len == 0) { in BrotliDecoderDecompressStream()
2496 s->state = BROTLI_STATE_METABLOCK_DONE; in BrotliDecoderDecompressStream()
2498 s->state = BROTLI_STATE_COMMAND_POST_DECODE_LITERALS; in BrotliDecoderDecompressStream()
2502 s->state = BROTLI_STATE_COMMAND_INNER; in BrotliDecoderDecompressStream()
2507 if (s->meta_block_remaining_len < 0) { in BrotliDecoderDecompressStream()
2512 if (!s->is_last_metablock) { in BrotliDecoderDecompressStream()
2513 s->state = BROTLI_STATE_METABLOCK_BEGIN; in BrotliDecoderDecompressStream()
2520 if (s->buffer_length == 0) { in BrotliDecoderDecompressStream()
2522 *available_in = br->avail_in; in BrotliDecoderDecompressStream()
2523 *next_in = br->next_in; in BrotliDecoderDecompressStream()
2525 s->state = BROTLI_STATE_DONE; in BrotliDecoderDecompressStream()
2526 /* Fall through. */ in BrotliDecoderDecompressStream()
2529 if (s->ringbuffer != 0) { in BrotliDecoderDecompressStream()
2544 if ((int)s->error_code < 0) { in BrotliDecoderHasMoreOutput()
2548 s->ringbuffer != 0 && UnwrittenBytes(s, BROTLI_FALSE) != 0); in BrotliDecoderHasMoreOutput()
2556 if ((s->ringbuffer == 0) || ((int)s->error_code < 0)) { in BrotliDecoderTakeOutput()
2565 *size = requested_out - available_out; in BrotliDecoderTakeOutput()
2577 return TO_BROTLI_BOOL(s->state != BROTLI_STATE_UNINITED || in BrotliDecoderIsUsed()
2578 BrotliGetAvailableBits(&s->br) != 0); in BrotliDecoderIsUsed()
2582 return TO_BROTLI_BOOL(s->state == BROTLI_STATE_DONE) && in BrotliDecoderIsFinished()
2587 return (BrotliDecoderErrorCode)s->error_code; in BrotliDecoderGetErrorCode()