1 ///////////////////////////////////////////////////////////////////////////////
3 /// \file lzma_encoder.c
4 /// \brief LZMA encoder
6 // Copyright (C) 1999-2006 Igor Pavlov
7 // Copyright (C) 2007 Lasse Collin
9 // This library is free software; you can redistribute it and/or
10 // modify it under the terms of the GNU Lesser General Public
11 // License as published by the Free Software Foundation; either
12 // version 2.1 of the License, or (at your option) any later version.
14 // This library is distributed in the hope that it will be useful,
15 // but WITHOUT ANY WARRANTY; without even the implied warranty of
16 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 // Lesser General Public License for more details.
19 ///////////////////////////////////////////////////////////////////////////////
21 #include "lzma2_encoder.h"
22 #include "lzma_encoder_private.h"
31 literal_matched(lzma_range_encoder *rc, probability *subcoder,
32 uint32_t match_byte, uint32_t symbol)
34 uint32_t offset = 0x100;
35 symbol += UINT32_C(1) << 8;
39 const uint32_t match_bit = match_byte & offset;
40 const uint32_t subcoder_index
41 = offset + match_bit + (symbol >> 8);
42 const uint32_t bit = (symbol >> 7) & 1;
43 rc_bit(rc, &subcoder[subcoder_index], bit);
46 offset &= ~(match_byte ^ symbol);
48 } while (symbol < (UINT32_C(1) << 16));
53 literal(lzma_coder *coder, lzma_mf *mf, uint32_t position)
55 // Locate the literal byte to be encoded and the subcoder.
56 const uint8_t cur_byte = mf->buffer[
57 mf->read_pos - mf->read_ahead];
58 probability *subcoder = literal_subcoder(coder->literal,
59 coder->literal_context_bits, coder->literal_pos_mask,
60 position, mf->buffer[mf->read_pos - mf->read_ahead - 1]);
62 if (is_literal_state(coder->state)) {
63 // Previous LZMA-symbol was a literal. Encode a normal
64 // literal without a match byte.
65 rc_bittree(&coder->rc, subcoder, 8, cur_byte);
67 // Previous LZMA-symbol was a match. Use the last byte of
68 // the match as a "match byte". That is, compare the bits
69 // of the current literal and the match byte.
70 const uint8_t match_byte = mf->buffer[
71 mf->read_pos - coder->reps[0] - 1
73 literal_matched(&coder->rc, subcoder, match_byte, cur_byte);
76 update_literal(coder->state);
85 length_update_prices(lzma_length_encoder *lc, const uint32_t pos_state)
87 const uint32_t table_size = lc->table_size;
88 lc->counters[pos_state] = table_size;
90 const uint32_t a0 = rc_bit_0_price(lc->choice);
91 const uint32_t a1 = rc_bit_1_price(lc->choice);
92 const uint32_t b0 = a1 + rc_bit_0_price(lc->choice2);
93 const uint32_t b1 = a1 + rc_bit_1_price(lc->choice2);
94 uint32_t *const prices = lc->prices[pos_state];
97 for (i = 0; i < table_size && i < LEN_LOW_SYMBOLS; ++i)
98 prices[i] = a0 + rc_bittree_price(lc->low[pos_state],
101 for (; i < table_size && i < LEN_LOW_SYMBOLS + LEN_MID_SYMBOLS; ++i)
102 prices[i] = b0 + rc_bittree_price(lc->mid[pos_state],
103 LEN_MID_BITS, i - LEN_LOW_SYMBOLS);
105 for (; i < table_size; ++i)
106 prices[i] = b1 + rc_bittree_price(lc->high, LEN_HIGH_BITS,
107 i - LEN_LOW_SYMBOLS - LEN_MID_SYMBOLS);
114 length(lzma_range_encoder *rc, lzma_length_encoder *lc,
115 const uint32_t pos_state, uint32_t len, const bool fast_mode)
117 assert(len <= MATCH_LEN_MAX);
118 len -= MATCH_LEN_MIN;
120 if (len < LEN_LOW_SYMBOLS) {
121 rc_bit(rc, &lc->choice, 0);
122 rc_bittree(rc, lc->low[pos_state], LEN_LOW_BITS, len);
124 rc_bit(rc, &lc->choice, 1);
125 len -= LEN_LOW_SYMBOLS;
127 if (len < LEN_MID_SYMBOLS) {
128 rc_bit(rc, &lc->choice2, 0);
129 rc_bittree(rc, lc->mid[pos_state], LEN_MID_BITS, len);
131 rc_bit(rc, &lc->choice2, 1);
132 len -= LEN_MID_SYMBOLS;
133 rc_bittree(rc, lc->high, LEN_HIGH_BITS, len);
137 // Only getoptimum uses the prices so don't update the table when
140 if (--lc->counters[pos_state] == 0)
141 length_update_prices(lc, pos_state);
150 match(lzma_coder *coder, const uint32_t pos_state,
151 const uint32_t distance, const uint32_t len)
153 update_match(coder->state);
155 length(&coder->rc, &coder->match_len_encoder, pos_state, len,
158 const uint32_t pos_slot = get_pos_slot(distance);
159 const uint32_t len_to_pos_state = get_len_to_pos_state(len);
160 rc_bittree(&coder->rc, coder->pos_slot[len_to_pos_state],
161 POS_SLOT_BITS, pos_slot);
163 if (pos_slot >= START_POS_MODEL_INDEX) {
164 const uint32_t footer_bits = (pos_slot >> 1) - 1;
165 const uint32_t base = (2 | (pos_slot & 1)) << footer_bits;
166 const uint32_t pos_reduced = distance - base;
168 if (pos_slot < END_POS_MODEL_INDEX) {
169 // Careful here: base - pos_slot - 1 can be -1, but
170 // rc_bittree_reverse starts at probs[1], not probs[0].
171 rc_bittree_reverse(&coder->rc,
172 coder->pos_special + base - pos_slot - 1,
173 footer_bits, pos_reduced);
175 rc_direct(&coder->rc, pos_reduced >> ALIGN_BITS,
176 footer_bits - ALIGN_BITS);
178 &coder->rc, coder->pos_align,
179 ALIGN_BITS, pos_reduced & ALIGN_MASK);
180 ++coder->align_price_count;
184 coder->reps[3] = coder->reps[2];
185 coder->reps[2] = coder->reps[1];
186 coder->reps[1] = coder->reps[0];
187 coder->reps[0] = distance;
188 ++coder->match_price_count;
197 rep_match(lzma_coder *coder, const uint32_t pos_state,
198 const uint32_t rep, const uint32_t len)
201 rc_bit(&coder->rc, &coder->is_rep0[coder->state], 0);
203 &coder->is_rep0_long[coder->state][pos_state],
206 const uint32_t distance = coder->reps[rep];
207 rc_bit(&coder->rc, &coder->is_rep0[coder->state], 1);
210 rc_bit(&coder->rc, &coder->is_rep1[coder->state], 0);
212 rc_bit(&coder->rc, &coder->is_rep1[coder->state], 1);
213 rc_bit(&coder->rc, &coder->is_rep2[coder->state],
217 coder->reps[3] = coder->reps[2];
219 coder->reps[2] = coder->reps[1];
222 coder->reps[1] = coder->reps[0];
223 coder->reps[0] = distance;
227 update_short_rep(coder->state);
229 length(&coder->rc, &coder->rep_len_encoder, pos_state, len,
231 update_long_rep(coder->state);
241 encode_symbol(lzma_coder *coder, lzma_mf *mf,
242 uint32_t back, uint32_t len, uint32_t position)
244 const uint32_t pos_state = position & coder->pos_mask;
246 if (back == UINT32_MAX) {
247 // Literal i.e. eight-bit byte
250 &coder->is_match[coder->state][pos_state], 0);
251 literal(coder, mf, position);
253 // Some type of match
255 &coder->is_match[coder->state][pos_state], 1);
257 if (back < REP_DISTANCES) {
258 // It's a repeated match i.e. the same distance
259 // has been used earlier.
260 rc_bit(&coder->rc, &coder->is_rep[coder->state], 1);
261 rep_match(coder, pos_state, back, len);
264 rc_bit(&coder->rc, &coder->is_rep[coder->state], 0);
265 match(coder, pos_state, back - REP_DISTANCES, len);
269 assert(mf->read_ahead >= len);
270 mf->read_ahead -= len;
275 encode_init(lzma_coder *coder, lzma_mf *mf)
277 assert(mf_position(mf) == 0);
279 if (mf->read_pos == mf->read_limit) {
280 if (mf->action == LZMA_RUN)
281 return false; // We cannot do anything.
283 // We are finishing (we cannot get here when flushing).
284 assert(mf->write_pos == mf->read_pos);
285 assert(mf->action == LZMA_FINISH);
287 // Do the actual initialization. The first LZMA symbol must
288 // always be a literal.
291 rc_bit(&coder->rc, &coder->is_match[0][0], 0);
292 rc_bittree(&coder->rc, coder->literal[0], 8, mf->buffer[0]);
295 // Initialization is done (except if empty file).
296 coder->is_initialized = true;
303 encode_eopm(lzma_coder *coder, uint32_t position)
305 const uint32_t pos_state = position & coder->pos_mask;
306 rc_bit(&coder->rc, &coder->is_match[coder->state][pos_state], 1);
307 rc_bit(&coder->rc, &coder->is_rep[coder->state], 0);
308 match(coder, pos_state, UINT32_MAX, MATCH_LEN_MIN);
312 /// Number of bytes that a single encoding loop in lzma_lzma_encode() can
313 /// consume from the dictionary. This limit comes from lzma_lzma_optimum()
314 /// and may need to be updated if that function is significantly modified.
315 #define LOOP_INPUT_MAX (OPTS + 1)
319 lzma_lzma_encode(lzma_coder *restrict coder, lzma_mf *restrict mf,
320 uint8_t *restrict out, size_t *restrict out_pos,
321 size_t out_size, uint32_t limit)
323 // Initialize the stream if no data has been encoded yet.
324 if (!coder->is_initialized && !encode_init(coder, mf))
327 // Get the lowest bits of the uncompressed offset from the LZ layer.
328 uint32_t position = mf_position(mf);
331 // Encode pending bits, if any. Calling this before encoding
332 // the next symbol is needed only with plain LZMA, since
333 // LZMA2 always provides big enough buffer to flush
334 // everything out from the range encoder. For the same reason,
335 // rc_encode() never returns true when this function is used
336 // as part of LZMA2 encoder.
337 if (rc_encode(&coder->rc, out, out_pos, out_size)) {
338 assert(limit == UINT32_MAX);
342 // With LZMA2 we need to take care that compressed size of
343 // a chunk doesn't get too big.
345 if (limit != UINT32_MAX
346 && (mf->read_pos - mf->read_ahead >= limit
347 || *out_pos + rc_pending(&coder->rc)
352 // Check that there is some input to process.
353 if (mf->read_pos >= mf->read_limit) {
354 if (mf->action == LZMA_RUN)
357 if (mf->read_ahead == 0)
361 // Get optimal match (repeat position and length).
362 // Value ranges for pos:
363 // - [0, REP_DISTANCES): repeated match
364 // - [REP_DISTANCES, UINT32_MAX):
365 // match at (pos - REP_DISTANCES)
366 // - UINT32_MAX: not a match but a literal
367 // Value ranges for len:
368 // - [MATCH_LEN_MIN, MATCH_LEN_MAX]
372 if (coder->fast_mode)
373 lzma_lzma_optimum_fast(coder, mf, &back, &len);
375 lzma_lzma_optimum_normal(
376 coder, mf, &back, &len, position);
378 encode_symbol(coder, mf, back, len, position);
383 if (!coder->is_flushed) {
384 coder->is_flushed = true;
386 // We don't support encoding plain LZMA streams without EOPM,
387 // and LZMA2 doesn't use EOPM at LZMA level.
388 if (limit == UINT32_MAX)
389 encode_eopm(coder, position);
391 // Flush the remaining bytes from the range encoder.
392 rc_flush(&coder->rc);
394 // Copy the remaining bytes to the output buffer. If there
395 // isn't enough output space, we will copy out the remaining
396 // bytes on the next call to this function by using
397 // the rc_encode() call in the encoding loop above.
398 if (rc_encode(&coder->rc, out, out_pos, out_size)) {
399 assert(limit == UINT32_MAX);
404 // Make it ready for the next LZMA2 chunk.
405 coder->is_flushed = false;
407 return LZMA_STREAM_END;
412 lzma_encode(lzma_coder *restrict coder, lzma_mf *restrict mf,
413 uint8_t *restrict out, size_t *restrict out_pos,
416 // Plain LZMA has no support for sync-flushing.
417 if (unlikely(mf->action == LZMA_SYNC_FLUSH))
418 return LZMA_OPTIONS_ERROR;
420 return lzma_lzma_encode(coder, mf, out, out_pos, out_size, UINT32_MAX);
429 is_options_valid(const lzma_options_lzma *options)
431 // Validate some of the options. LZ encoder validates nice_len too
432 // but we need a valid value here earlier.
433 return is_lclppb_valid(options)
434 && options->nice_len >= MATCH_LEN_MIN
435 && options->nice_len <= MATCH_LEN_MAX
436 && (options->mode == LZMA_MODE_FAST
437 || options->mode == LZMA_MODE_NORMAL);
442 set_lz_options(lzma_lz_options *lz_options, const lzma_options_lzma *options)
444 // LZ encoder initialization does the validation for these so we
445 // don't need to validate here.
446 lz_options->before_size = OPTS;
447 lz_options->dict_size = options->dict_size;
448 lz_options->after_size = LOOP_INPUT_MAX;
449 lz_options->match_len_max = MATCH_LEN_MAX;
450 lz_options->nice_len = options->nice_len;
451 lz_options->match_finder = options->mf;
452 lz_options->depth = options->depth;
453 lz_options->preset_dict = options->preset_dict;
454 lz_options->preset_dict_size = options->preset_dict_size;
460 length_encoder_reset(lzma_length_encoder *lencoder,
461 const uint32_t num_pos_states, const bool fast_mode)
463 bit_reset(lencoder->choice);
464 bit_reset(lencoder->choice2);
466 for (size_t pos_state = 0; pos_state < num_pos_states; ++pos_state) {
467 bittree_reset(lencoder->low[pos_state], LEN_LOW_BITS);
468 bittree_reset(lencoder->mid[pos_state], LEN_MID_BITS);
471 bittree_reset(lencoder->high, LEN_HIGH_BITS);
474 for (size_t pos_state = 0; pos_state < num_pos_states;
476 length_update_prices(lencoder, pos_state);
483 lzma_lzma_encoder_reset(lzma_coder *coder, const lzma_options_lzma *options)
485 if (!is_options_valid(options))
486 return LZMA_OPTIONS_ERROR;
488 coder->pos_mask = (1U << options->pb) - 1;
489 coder->literal_context_bits = options->lc;
490 coder->literal_pos_mask = (1U << options->lp) - 1;
493 rc_reset(&coder->rc);
497 for (size_t i = 0; i < REP_DISTANCES; ++i)
500 literal_init(coder->literal, options->lc, options->lp);
503 for (size_t i = 0; i < STATES; ++i) {
504 for (size_t j = 0; j <= coder->pos_mask; ++j) {
505 bit_reset(coder->is_match[i][j]);
506 bit_reset(coder->is_rep0_long[i][j]);
509 bit_reset(coder->is_rep[i]);
510 bit_reset(coder->is_rep0[i]);
511 bit_reset(coder->is_rep1[i]);
512 bit_reset(coder->is_rep2[i]);
515 for (size_t i = 0; i < FULL_DISTANCES - END_POS_MODEL_INDEX; ++i)
516 bit_reset(coder->pos_special[i]);
519 for (size_t i = 0; i < LEN_TO_POS_STATES; ++i)
520 bittree_reset(coder->pos_slot[i], POS_SLOT_BITS);
522 bittree_reset(coder->pos_align, ALIGN_BITS);
525 length_encoder_reset(&coder->match_len_encoder,
526 1U << options->pb, coder->fast_mode);
528 length_encoder_reset(&coder->rep_len_encoder,
529 1U << options->pb, coder->fast_mode);
531 // Price counts are incremented every time appropriate probabilities
532 // are changed. price counts are set to zero when the price tables
533 // are updated, which is done when the appropriate price counts have
534 // big enough value, and lzma_mf.read_ahead == 0 which happens at
535 // least every OPTS (a few thousand) possible price count increments.
537 // By resetting price counts to UINT32_MAX / 2, we make sure that the
538 // price tables will be initialized before they will be used (since
539 // the value is definitely big enough), and that it is OK to increment
540 // price counts without risk of integer overflow (since UINT32_MAX / 2
541 // is small enough). The current code doesn't increment price counts
542 // before initializing price tables, but it maybe done in future if
543 // we add support for saving the state between LZMA2 chunks.
544 coder->match_price_count = UINT32_MAX / 2;
545 coder->align_price_count = UINT32_MAX / 2;
547 coder->opts_end_index = 0;
548 coder->opts_current_index = 0;
555 lzma_lzma_encoder_create(lzma_coder **coder_ptr, lzma_allocator *allocator,
556 const lzma_options_lzma *options, lzma_lz_options *lz_options)
558 // Allocate lzma_coder if it wasn't already allocated.
559 if (*coder_ptr == NULL) {
560 *coder_ptr = lzma_alloc(sizeof(lzma_coder), allocator);
561 if (*coder_ptr == NULL)
562 return LZMA_MEM_ERROR;
565 lzma_coder *coder = *coder_ptr;
567 // Set compression mode. We haven't validates the options yet,
568 // but it's OK here, since nothing bad happens with invalid
569 // options in the code below, and they will get rejected by
570 // lzma_lzma_encoder_reset() call at the end of this function.
571 switch (options->mode) {
573 coder->fast_mode = true;
576 case LZMA_MODE_NORMAL: {
577 coder->fast_mode = false;
579 // Set dist_table_size.
580 // Round the dictionary size up to next 2^n.
581 uint32_t log_size = 0;
582 while ((UINT32_C(1) << log_size) < options->dict_size)
585 coder->dist_table_size = log_size * 2;
587 // Length encoders' price table size
588 coder->match_len_encoder.table_size
589 = options->nice_len + 1 - MATCH_LEN_MIN;
590 coder->rep_len_encoder.table_size
591 = options->nice_len + 1 - MATCH_LEN_MIN;
596 return LZMA_OPTIONS_ERROR;
599 // We don't need to write the first byte as literal if there is
600 // a non-empty preset dictionary. encode_init() wouldn't even work
601 // if there is a non-empty preset dictionary, because encode_init()
602 // assumes that position is zero and previous byte is also zero.
603 coder->is_initialized = options->preset_dict != NULL
604 && options->preset_dict_size > 0;
605 coder->is_flushed = false;
607 set_lz_options(lz_options, options);
609 return lzma_lzma_encoder_reset(coder, options);
614 lzma_encoder_init(lzma_lz_encoder *lz, lzma_allocator *allocator,
615 const void *options, lzma_lz_options *lz_options)
617 lz->code = &lzma_encode;
618 return lzma_lzma_encoder_create(
619 &lz->coder, allocator, options, lz_options);
624 lzma_lzma_encoder_init(lzma_next_coder *next, lzma_allocator *allocator,
625 const lzma_filter_info *filters)
627 return lzma_lz_encoder_init(
628 next, allocator, filters, &lzma_encoder_init);
633 lzma_lzma_encoder_memusage(const void *options)
635 if (!is_options_valid(options))
638 lzma_lz_options lz_options;
639 set_lz_options(&lz_options, options);
641 const uint64_t lz_memusage = lzma_lz_encoder_memusage(&lz_options);
642 if (lz_memusage == UINT64_MAX)
645 return (uint64_t)(sizeof(lzma_coder)) + lz_memusage;
650 lzma_lzma_lclppb_encode(const lzma_options_lzma *options, uint8_t *byte)
652 if (!is_lclppb_valid(options))
655 *byte = (options->pb * 5 + options->lp) * 9 + options->lc;
656 assert(*byte <= (4 * 5 + 4) * 9 + 8);
662 #ifdef HAVE_ENCODER_LZMA1
664 lzma_lzma_props_encode(const void *options, uint8_t *out)
666 const lzma_options_lzma *const opt = options;
668 if (lzma_lzma_lclppb_encode(opt, out))
669 return LZMA_PROG_ERROR;
671 integer_write_32(out + 1, opt->dict_size);
678 extern LZMA_API(lzma_bool)
679 lzma_mode_is_supported(lzma_mode mode)
681 return mode == LZMA_MODE_FAST || mode == LZMA_MODE_NORMAL;