Lines Matching +full:input +full:- +full:depth
1 // SPDX-License-Identifier: 0BSD
26 /// LZ-based encoder e.g. LZMA
37 /// \brief Moves the data in the input window to free space for new data
39 /// mf->buffer is a sliding input window, which keeps mf->keep_size_before
40 /// bytes of input history available all the time. Now and then we need to
47 // Align the move to a multiple of 16 bytes. Some LZ-based encoders in move_window()
48 // like LZMA use the lowest bits of mf->read_pos to know the in move_window()
51 assert(mf->read_pos > mf->keep_size_before); in move_window()
53 = (mf->read_pos - mf->keep_size_before) & ~UINT32_C(15); in move_window()
55 assert(mf->write_pos > move_offset); in move_window()
56 const size_t move_size = mf->write_pos - move_offset; in move_window()
58 assert(move_offset + move_size <= mf->size); in move_window()
60 memmove(mf->buffer, mf->buffer + move_offset, move_size); in move_window()
62 mf->offset += move_offset; in move_window()
63 mf->read_pos -= move_offset; in move_window()
64 mf->read_limit -= move_offset; in move_window()
65 mf->write_pos -= move_offset; in move_window()
71 /// \brief Tries to fill the input window (mf->buffer)
73 /// If we are the last encoder in the chain, our input data is in in[].
75 /// write its output to mf->buffer.
84 assert(coder->mf.read_pos <= coder->mf.write_pos); in fill_window()
87 if (coder->mf.read_pos >= coder->mf.size - coder->mf.keep_size_after) in fill_window()
88 move_window(&coder->mf); in fill_window()
93 size_t write_pos = coder->mf.write_pos; in fill_window()
95 if (coder->next.code == NULL) { in fill_window()
97 lzma_bufcpy(in, in_pos, in_size, coder->mf.buffer, in fill_window()
98 &write_pos, coder->mf.size); in fill_window()
104 ret = coder->next.code(coder->next.coder, allocator, in fill_window()
106 coder->mf.buffer, &write_pos, in fill_window()
107 coder->mf.size, action); in fill_window()
110 coder->mf.write_pos = write_pos; in fill_window()
116 memzero(coder->mf.buffer + write_pos, LZMA_MEMCMPLEN_EXTRA); in fill_window()
119 // the encoder to process all the input (that is, read_pos is allowed in fill_window()
125 coder->mf.action = action; in fill_window()
126 coder->mf.read_limit = coder->mf.write_pos; in fill_window()
128 } else if (coder->mf.write_pos > coder->mf.keep_size_after) { in fill_window()
130 // only little new input, there may be too little input in fill_window()
132 coder->mf.read_limit = coder->mf.write_pos in fill_window()
133 - coder->mf.keep_size_after; in fill_window()
137 if (coder->mf.pending > 0 in fill_window()
138 && coder->mf.read_pos < coder->mf.read_limit) { in fill_window()
139 // Match finder may update coder->pending and expects it to in fill_window()
141 const uint32_t pending = coder->mf.pending; in fill_window()
142 coder->mf.pending = 0; in fill_window()
146 assert(coder->mf.read_pos >= pending); in fill_window()
147 coder->mf.read_pos -= pending; in fill_window()
150 // mf_skip(), since we don't want to touch mf->read_ahead. in fill_window()
151 coder->mf.skip(&coder->mf, pending); in fill_window()
169 // Read more data to coder->mf.buffer if needed. in lz_encode()
170 if (coder->mf.action == LZMA_RUN && coder->mf.read_pos in lz_encode()
171 >= coder->mf.read_limit) in lz_encode()
176 const lzma_ret ret = coder->lz.code(coder->lz.coder, in lz_encode()
177 &coder->mf, out, out_pos, out_size); in lz_encode()
182 coder->mf.action = LZMA_RUN; in lz_encode()
198 if (!IS_ENC_DICT_SIZE_VALID(lz_options->dict_size) in lz_encoder_prepare()
199 || lz_options->nice_len > lz_options->match_len_max) in lz_encoder_prepare()
202 mf->keep_size_before = lz_options->before_size + lz_options->dict_size; in lz_encoder_prepare()
204 mf->keep_size_after = lz_options->after_size in lz_encoder_prepare()
205 + lz_options->match_len_max; in lz_encoder_prepare()
214 // - Several variables in lzma_mf have to be changed from uint32_t in lz_encoder_prepare()
216 // - Memory usage calculation needs something too, e.g. use uint64_t in lz_encoder_prepare()
217 // for mf->size. in lz_encoder_prepare()
218 uint32_t reserve = lz_options->dict_size / 2; in lz_encoder_prepare()
222 reserve += (lz_options->before_size + lz_options->match_len_max in lz_encoder_prepare()
223 + lz_options->after_size) / 2 + (UINT32_C(1) << 19); in lz_encoder_prepare()
225 const uint32_t old_size = mf->size; in lz_encoder_prepare()
226 mf->size = mf->keep_size_before + reserve + mf->keep_size_after; in lz_encoder_prepare()
230 if (mf->buffer != NULL && old_size != mf->size) { in lz_encoder_prepare()
231 lzma_free(mf->buffer, allocator); in lz_encoder_prepare()
232 mf->buffer = NULL; in lz_encoder_prepare()
236 mf->match_len_max = lz_options->match_len_max; in lz_encoder_prepare()
237 mf->nice_len = lz_options->nice_len; in lz_encoder_prepare()
246 // would need to be careful to use 64-bit types in various places in lz_encoder_prepare()
247 // (size_t could do since we would need bigger than 32-bit address in lz_encoder_prepare()
254 mf->cyclic_size = lz_options->dict_size + 1; in lz_encoder_prepare()
257 switch (lz_options->match_finder) { in lz_encoder_prepare()
260 mf->find = &lzma_mf_hc3_find; in lz_encoder_prepare()
261 mf->skip = &lzma_mf_hc3_skip; in lz_encoder_prepare()
266 mf->find = &lzma_mf_hc4_find; in lz_encoder_prepare()
267 mf->skip = &lzma_mf_hc4_skip; in lz_encoder_prepare()
272 mf->find = &lzma_mf_bt2_find; in lz_encoder_prepare()
273 mf->skip = &lzma_mf_bt2_skip; in lz_encoder_prepare()
278 mf->find = &lzma_mf_bt3_find; in lz_encoder_prepare()
279 mf->skip = &lzma_mf_bt3_skip; in lz_encoder_prepare()
284 mf->find = &lzma_mf_bt4_find; in lz_encoder_prepare()
285 mf->skip = &lzma_mf_bt4_skip; in lz_encoder_prepare()
293 // Calculate the sizes of mf->hash and mf->son. in lz_encoder_prepare()
300 = mf_get_hash_bytes(lz_options->match_finder); in lz_encoder_prepare()
301 assert(hash_bytes <= mf->nice_len); in lz_encoder_prepare()
303 const bool is_bt = (lz_options->match_finder & 0x10) != 0; in lz_encoder_prepare()
309 // Round dictionary size up to the next 2^n - 1 so it can in lz_encoder_prepare()
311 hs = lz_options->dict_size - 1; in lz_encoder_prepare()
321 hs = (UINT32_C(1) << 24) - 1; in lz_encoder_prepare()
327 mf->hash_mask = hs; in lz_encoder_prepare()
336 if (mf->hash_bytes > 4) in lz_encoder_prepare()
340 const uint32_t old_hash_count = mf->hash_count; in lz_encoder_prepare()
341 const uint32_t old_sons_count = mf->sons_count; in lz_encoder_prepare()
342 mf->hash_count = hs; in lz_encoder_prepare()
343 mf->sons_count = mf->cyclic_size; in lz_encoder_prepare()
345 mf->sons_count *= 2; in lz_encoder_prepare()
349 if (old_hash_count != mf->hash_count in lz_encoder_prepare()
350 || old_sons_count != mf->sons_count) { in lz_encoder_prepare()
351 lzma_free(mf->hash, allocator); in lz_encoder_prepare()
352 mf->hash = NULL; in lz_encoder_prepare()
354 lzma_free(mf->son, allocator); in lz_encoder_prepare()
355 mf->son = NULL; in lz_encoder_prepare()
359 mf->depth = lz_options->depth; in lz_encoder_prepare()
360 if (mf->depth == 0) { in lz_encoder_prepare()
362 mf->depth = 16 + mf->nice_len / 2; in lz_encoder_prepare()
364 mf->depth = 4 + mf->nice_len / 4; in lz_encoder_prepare()
376 if (mf->buffer == NULL) { in lz_encoder_init()
380 mf->buffer = lzma_alloc(mf->size + LZMA_MEMCMPLEN_EXTRA, in lz_encoder_init()
382 if (mf->buffer == NULL) in lz_encoder_init()
388 memzero(mf->buffer + mf->size, LZMA_MEMCMPLEN_EXTRA); in lz_encoder_init()
391 // Use cyclic_size as initial mf->offset. This allows in lz_encoder_init()
395 mf->offset = mf->cyclic_size; in lz_encoder_init()
396 mf->read_pos = 0; in lz_encoder_init()
397 mf->read_ahead = 0; in lz_encoder_init()
398 mf->read_limit = 0; in lz_encoder_init()
399 mf->write_pos = 0; in lz_encoder_init()
400 mf->pending = 0; in lz_encoder_init()
404 // possible on 32-bit CPU.) in lz_encoder_init()
405 if (mf->hash_count > SIZE_MAX / sizeof(uint32_t) in lz_encoder_init()
406 || mf->sons_count > SIZE_MAX / sizeof(uint32_t)) in lz_encoder_init()
411 // is zero, we can use lzma_alloc_zero() or memzero() for mf->hash. in lz_encoder_init()
413 // We don't need to initialize mf->son, but not doing that may in lz_encoder_init()
417 // actually compressed: most of the mf->son won't get actually in lz_encoder_init()
420 if (mf->hash == NULL) { in lz_encoder_init()
421 mf->hash = lzma_alloc_zero(mf->hash_count * sizeof(uint32_t), in lz_encoder_init()
423 mf->son = lzma_alloc(mf->sons_count * sizeof(uint32_t), in lz_encoder_init()
426 if (mf->hash == NULL || mf->son == NULL) { in lz_encoder_init()
427 lzma_free(mf->hash, allocator); in lz_encoder_init()
428 mf->hash = NULL; in lz_encoder_init()
430 lzma_free(mf->son, allocator); in lz_encoder_init()
431 mf->son = NULL; in lz_encoder_init()
437 for (uint32_t i = 0; i < mf->hash_count; ++i) in lz_encoder_init()
438 mf->hash[i] = EMPTY_HASH_VALUE; in lz_encoder_init()
440 memzero(mf->hash, mf->hash_count * sizeof(uint32_t)); in lz_encoder_init()
443 mf->cyclic_pos = 0; in lz_encoder_init()
446 if (lz_options->preset_dict != NULL in lz_encoder_init()
447 && lz_options->preset_dict_size > 0) { in lz_encoder_init()
450 mf->write_pos = my_min(lz_options->preset_dict_size, mf->size); in lz_encoder_init()
451 memcpy(mf->buffer, lz_options->preset_dict in lz_encoder_init()
452 + lz_options->preset_dict_size - mf->write_pos, in lz_encoder_init()
453 mf->write_pos); in lz_encoder_init()
454 mf->action = LZMA_SYNC_FLUSH; in lz_encoder_init()
455 mf->skip(mf, mf->write_pos); in lz_encoder_init()
458 mf->action = LZMA_RUN; in lz_encoder_init()
491 lzma_next_end(&coder->next, allocator); in lz_encoder_end()
493 lzma_free(coder->mf.son, allocator); in lz_encoder_end()
494 lzma_free(coder->mf.hash, allocator); in lz_encoder_end()
495 lzma_free(coder->mf.buffer, allocator); in lz_encoder_end()
497 if (coder->lz.end != NULL) in lz_encoder_end()
498 coder->lz.end(coder->lz.coder, allocator); in lz_encoder_end()
500 lzma_free(coder->lz.coder, allocator); in lz_encoder_end()
514 if (coder->lz.options_update == NULL) in lz_encoder_update()
517 return_if_error(coder->lz.options_update( in lz_encoder_update()
518 coder->lz.coder, reversed_filters)); in lz_encoder_update()
521 &coder->next, allocator, reversed_filters + 1); in lz_encoder_update()
532 if (coder->next.code == NULL && coder->lz.set_out_limit != NULL) in lz_encoder_set_out_limit()
533 return coder->lz.set_out_limit( in lz_encoder_set_out_limit()
534 coder->lz.coder, uncomp_size, out_limit); in lz_encoder_set_out_limit()
554 lzma_coder *coder = next->coder; in lzma_lz_encoder_init()
560 next->coder = coder; in lzma_lz_encoder_init()
561 next->code = &lz_encode; in lzma_lz_encoder_init()
562 next->end = &lz_encoder_end; in lzma_lz_encoder_init()
563 next->update = &lz_encoder_update; in lzma_lz_encoder_init()
564 next->set_out_limit = &lz_encoder_set_out_limit; in lzma_lz_encoder_init()
566 coder->lz.coder = NULL; in lzma_lz_encoder_init()
567 coder->lz.code = NULL; in lzma_lz_encoder_init()
568 coder->lz.end = NULL; in lzma_lz_encoder_init()
569 coder->lz.options_update = NULL; in lzma_lz_encoder_init()
570 coder->lz.set_out_limit = NULL; in lzma_lz_encoder_init()
575 coder->mf.buffer = NULL; in lzma_lz_encoder_init()
576 coder->mf.size = 0; in lzma_lz_encoder_init()
577 coder->mf.hash = NULL; in lzma_lz_encoder_init()
578 coder->mf.son = NULL; in lzma_lz_encoder_init()
579 coder->mf.hash_count = 0; in lzma_lz_encoder_init()
580 coder->mf.sons_count = 0; in lzma_lz_encoder_init()
582 coder->next = LZMA_NEXT_CODER_INIT; in lzma_lz_encoder_init()
585 // Initialize the LZ-based encoder. in lzma_lz_encoder_init()
587 return_if_error(lz_init(&coder->lz, allocator, in lzma_lz_encoder_init()
590 // Setup the size information into coder->mf and deallocate in lzma_lz_encoder_init()
592 if (lz_encoder_prepare(&coder->mf, allocator, &lz_options)) in lzma_lz_encoder_init()
597 if (lz_encoder_init(&coder->mf, allocator, &lz_options)) in lzma_lz_encoder_init()
601 return lzma_next_filter_init(&coder->next, allocator, filters + 1); in lzma_lz_encoder_init()