4 * A compressor that produces output compatible with the LZMS compression format.
8 * Copyright (C) 2013, 2014 Eric Biggers
10 * This file is part of wimlib, a library for working with WIM files.
12 * wimlib is free software; you can redistribute it and/or modify it under the
13 * terms of the GNU General Public License as published by the Free
14 * Software Foundation; either version 3 of the License, or (at your option)
17 * wimlib is distributed in the hope that it will be useful, but WITHOUT ANY
18 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
19 * A PARTICULAR PURPOSE. See the GNU General Public License for more
22 * You should have received a copy of the GNU General Public License
23 * along with wimlib; if not, see http://www.gnu.org/licenses/.
30 #include "wimlib/compress_common.h"
31 #include "wimlib/compressor_ops.h"
32 #include "wimlib/endianness.h"
33 #include "wimlib/error.h"
34 #include "wimlib/lz_mf.h"
35 #include "wimlib/lz_repsearch.h"
36 #include "wimlib/lzms.h"
37 #include "wimlib/util.h"
43 /* Stucture used for writing raw bits as a series of 16-bit little endian coding
44 * units. This starts at the *end* of the compressed data buffer and proceeds
46 struct lzms_output_bitstream {
48 /* Bits that haven't yet been written to the output buffer. */
51 /* Number of bits currently held in @bitbuf. */
54 /* Pointer to one past the next position in the compressed data buffer
55 * at which to output a 16-bit coding unit. */
58 /* Pointer to the beginning of the output buffer. (The "end" when
59 * writing backwards!) */
63 /* Stucture used for range encoding (raw version). This starts at the
64 * *beginning* of the compressed data buffer and proceeds forward. */
65 struct lzms_range_encoder_raw {
67 /* A 33-bit variable that holds the low boundary of the current range.
68 * The 33rd bit is needed to catch carries. */
71 /* Size of the current range. */
74 /* Next 16-bit coding unit to output. */
77 /* Number of 16-bit coding units whose output has been delayed due to
78 * possible carrying. The first such coding unit is @cache; all
79 * subsequent such coding units are 0xffff. */
82 /* Pointer to the beginning of the output buffer. */
85 /* Pointer to the position in the output buffer at which the next coding
86 * unit must be written. */
89 /* Pointer just past the end of the output buffer. */
93 /* Structure used for range encoding. This wraps around `struct
94 * lzms_range_encoder_raw' to use and maintain probability entries. */
95 struct lzms_range_encoder {
97 /* Pointer to the raw range encoder, which has no persistent knowledge
98 * of probabilities. Multiple lzms_range_encoder's share the same
99 * lzms_range_encoder_raw. */
100 struct lzms_range_encoder_raw *rc;
102 /* Bits recently encoded by this range encoder. This is used as an
103 * index into @prob_entries. */
106 /* Bitmask for @state to prevent its value from exceeding the number of
107 * probability entries. */
110 /* Probability entries being used for this range encoder. */
111 struct lzms_probability_entry prob_entries[LZMS_MAX_NUM_STATES];
114 /* Structure used for Huffman encoding. */
115 struct lzms_huffman_encoder {
117 /* Bitstream to write Huffman-encoded symbols and verbatim bits to.
118 * Multiple lzms_huffman_encoder's share the same lzms_output_bitstream.
120 struct lzms_output_bitstream *os;
122 /* Number of symbols that have been written using this code far. Reset
123 * to 0 whenever the code is rebuilt. */
124 u32 num_syms_written;
126 /* When @num_syms_written reaches this number, the Huffman code must be
130 /* Number of symbols in the represented Huffman code. */
133 /* Running totals of symbol frequencies. These are diluted slightly
134 * whenever the code is rebuilt. */
135 u32 sym_freqs[LZMS_MAX_NUM_SYMS];
137 /* The length, in bits, of each symbol in the Huffman code. */
138 u8 lens[LZMS_MAX_NUM_SYMS];
140 /* The codeword of each symbol in the Huffman code. */
141 u32 codewords[LZMS_MAX_NUM_SYMS];
144 /* Internal compression parameters */
145 struct lzms_compressor_params {
146 u32 min_match_length;
147 u32 nice_match_length;
148 u32 max_search_depth;
149 u32 optim_array_length;
152 /* State of the LZMS compressor */
153 struct lzms_compressor {
155 /* Internal compression parameters */
156 struct lzms_compressor_params params;
158 /* Data currently being compressed */
162 /* Lempel-Ziv match-finder */
165 /* Temporary space to store found matches */
166 struct lz_match *matches;
168 /* Per-position data for near-optimal parsing */
169 struct lzms_mc_pos_data *optimum;
170 struct lzms_mc_pos_data *optimum_end;
172 /* Raw range encoder which outputs to the beginning of the compressed
173 * data buffer, proceeding forwards */
174 struct lzms_range_encoder_raw rc;
176 /* Bitstream which outputs to the end of the compressed data buffer,
177 * proceeding backwards */
178 struct lzms_output_bitstream os;
181 struct lzms_range_encoder main_range_encoder;
182 struct lzms_range_encoder match_range_encoder;
183 struct lzms_range_encoder lz_match_range_encoder;
184 struct lzms_range_encoder lz_repeat_match_range_encoders[LZMS_NUM_RECENT_OFFSETS - 1];
185 struct lzms_range_encoder delta_match_range_encoder;
186 struct lzms_range_encoder delta_repeat_match_range_encoders[LZMS_NUM_RECENT_OFFSETS - 1];
188 /* Huffman encoders */
189 struct lzms_huffman_encoder literal_encoder;
190 struct lzms_huffman_encoder lz_offset_encoder;
191 struct lzms_huffman_encoder length_encoder;
192 struct lzms_huffman_encoder delta_power_encoder;
193 struct lzms_huffman_encoder delta_offset_encoder;
195 /* Used for preprocessing */
196 s32 last_target_usages[65536];
198 #define LZMS_NUM_FAST_LENGTHS 256
199 /* Table: length => length slot for small lengths */
200 u8 length_slot_fast[LZMS_NUM_FAST_LENGTHS];
202 /* Table: length => current cost for small match lengths */
203 u32 length_cost_fast[LZMS_NUM_FAST_LENGTHS];
205 #define LZMS_NUM_FAST_OFFSETS 32768
206 /* Table: offset => offset slot for small offsets */
207 u8 offset_slot_fast[LZMS_NUM_FAST_OFFSETS];
211 * Match chooser position data:
213 * An array of these structures is used during the near-optimal match-choosing
214 * algorithm. They correspond to consecutive positions in the window and are
215 * used to keep track of the cost to reach each position, and the match/literal
216 * choices that need to be chosen to reach that position.
218 struct lzms_mc_pos_data {
220 /* The cost, in bits, of the lowest-cost path that has been found to
221 * reach this position. This can change as progressively lower cost
222 * paths are found to reach this position. */
224 #define MC_INFINITE_COST UINT32_MAX
226 /* The match or literal that was taken to reach this position. This can
227 * change as progressively lower cost paths are found to reach this
230 * This variable is divided into two bitfields.
233 * Low bits are 1, high bits are the literal.
235 * Explicit offset matches:
236 * Low bits are the match length, high bits are the offset plus 2.
238 * Repeat offset matches:
239 * Low bits are the match length, high bits are the queue index.
242 #define MC_OFFSET_SHIFT 32
243 #define MC_LEN_MASK (((u64)1 << MC_OFFSET_SHIFT) - 1)
245 /* The LZMS adaptive state that exists at this position. This is filled
246 * in lazily, only after the minimum-cost path to this position is
249 * Note: the way we handle this adaptive state in the "minimum-cost"
250 * parse is actually only an approximation. It's possible for the
251 * globally optimal, minimum cost path to contain a prefix, ending at a
252 * position, where that path prefix is *not* the minimum cost path to
253 * that position. This can happen if such a path prefix results in a
254 * different adaptive state which results in lower costs later. We do
255 * not solve this problem; we only consider the lowest cost to reach
256 * each position, which seems to be an acceptable approximation.
258 * Note: this adaptive state also does not include the probability
259 * entries or current Huffman codewords. Those aren't maintained
260 * per-position and are only updated occassionally. */
261 struct lzms_adaptive_state {
262 struct lzms_lz_lru_queues lru;
266 u8 lz_repeat_match_state[LZMS_NUM_RECENT_OFFSETS - 1];
271 lzms_init_fast_slots(struct lzms_compressor *c)
273 /* Create table mapping small lengths to length slots. */
274 for (unsigned slot = 0, i = 0; i < LZMS_NUM_FAST_LENGTHS; i++) {
275 while (i >= lzms_length_slot_base[slot + 1])
277 c->length_slot_fast[i] = slot;
280 /* Create table mapping small offsets to offset slots. */
281 for (unsigned slot = 0, i = 0; i < LZMS_NUM_FAST_OFFSETS; i++) {
282 while (i >= lzms_offset_slot_base[slot + 1])
284 c->offset_slot_fast[i] = slot;
288 static inline unsigned
289 lzms_get_length_slot_fast(const struct lzms_compressor *c, u32 length)
291 if (likely(length < LZMS_NUM_FAST_LENGTHS))
292 return c->length_slot_fast[length];
294 return lzms_get_length_slot(length);
297 static inline unsigned
298 lzms_get_offset_slot_fast(const struct lzms_compressor *c, u32 offset)
300 if (offset < LZMS_NUM_FAST_OFFSETS)
301 return c->offset_slot_fast[offset];
303 return lzms_get_offset_slot(offset);
306 /* Initialize the output bitstream @os to write backwards to the specified
307 * compressed data buffer @out that is @out_limit 16-bit integers long. */
309 lzms_output_bitstream_init(struct lzms_output_bitstream *os,
310 le16 *out, size_t out_limit)
314 os->next = out + out_limit;
319 * Write some bits, contained in the low @num_bits bits of @bits (ordered from
320 * high-order to low-order), to the output bitstream @os.
322 * @max_num_bits is a compile-time constant that specifies the maximum number of
323 * bits that can ever be written at this call site.
326 lzms_output_bitstream_put_varbits(struct lzms_output_bitstream *os,
327 u32 bits, unsigned num_bits,
328 unsigned max_num_bits)
330 LZMS_ASSERT(num_bits <= 48);
332 /* Add the bits to the bit buffer variable. */
333 os->bitcount += num_bits;
334 os->bitbuf = (os->bitbuf << num_bits) | bits;
336 /* Check whether any coding units need to be written. */
337 while (os->bitcount >= 16) {
341 /* Write a coding unit, unless it would underflow the buffer. */
342 if (os->next != os->begin)
343 *--os->next = cpu_to_le16(os->bitbuf >> os->bitcount);
345 /* Optimization for call sites that never write more than 16
347 if (max_num_bits <= 16)
352 /* Use when @num_bits is a compile-time constant. Otherwise use
353 * lzms_output_bitstream_put_bits(). */
355 lzms_output_bitstream_put_bits(struct lzms_output_bitstream *os,
356 u32 bits, unsigned num_bits)
358 lzms_output_bitstream_put_varbits(os, bits, num_bits, num_bits);
361 /* Flush the output bitstream, ensuring that all bits written to it have been
362 * written to memory. Returns %true if all bits have been output successfully,
363 * or %false if an overrun occurred. */
365 lzms_output_bitstream_flush(struct lzms_output_bitstream *os)
367 if (os->next == os->begin)
370 if (os->bitcount != 0)
371 *--os->next = cpu_to_le16(os->bitbuf << (16 - os->bitcount));
376 /* Initialize the range encoder @rc to write forwards to the specified
377 * compressed data buffer @out that is @out_limit 16-bit integers long. */
379 lzms_range_encoder_raw_init(struct lzms_range_encoder_raw *rc,
380 le16 *out, size_t out_limit)
383 rc->range = 0xffffffff;
388 rc->end = out + out_limit;
392 * Attempt to flush bits from the range encoder.
394 * Note: this is based on the public domain code for LZMA written by Igor
395 * Pavlov. The only differences in this function are that in LZMS the bits must
396 * be output in 16-bit coding units instead of 8-bit coding units, and that in
397 * LZMS the first coding unit is not ignored by the decompressor, so the encoder
398 * cannot output a dummy value to that position.
400 * The basic idea is that we're writing bits from @rc->low to the output.
401 * However, due to carrying, the writing of coding units with value 0xffff, as
402 * well as one prior coding unit, must be delayed until it is determined whether
406 lzms_range_encoder_raw_shift_low(struct lzms_range_encoder_raw *rc)
408 if ((u32)(rc->low) < 0xffff0000 ||
409 (u32)(rc->low >> 32) != 0)
411 /* Carry not needed (rc->low < 0xffff0000), or carry occurred
412 * ((rc->low >> 32) != 0, a.k.a. the carry bit is 1). */
414 if (likely(rc->next >= rc->begin)) {
415 if (rc->next != rc->end)
416 *rc->next++ = cpu_to_le16(rc->cache +
417 (u16)(rc->low >> 32));
422 } while (--rc->cache_size != 0);
424 rc->cache = (rc->low >> 16) & 0xffff;
427 rc->low = (rc->low & 0xffff) << 16;
431 lzms_range_encoder_raw_normalize(struct lzms_range_encoder_raw *rc)
433 if (rc->range <= 0xffff) {
435 lzms_range_encoder_raw_shift_low(rc);
440 lzms_range_encoder_raw_flush(struct lzms_range_encoder_raw *rc)
442 for (unsigned i = 0; i < 4; i++)
443 lzms_range_encoder_raw_shift_low(rc);
444 return rc->next != rc->end;
447 /* Encode the next bit using the range encoder (raw version).
449 * @prob is the chance out of LZMS_PROBABILITY_MAX that the next bit is 0. */
451 lzms_range_encoder_raw_encode_bit(struct lzms_range_encoder_raw *rc,
454 lzms_range_encoder_raw_normalize(rc);
456 u32 bound = (rc->range >> LZMS_PROBABILITY_BITS) * prob;
465 /* Encode a bit using the specified range encoder. This wraps around
466 * lzms_range_encoder_raw_encode_bit() to handle using and updating the
467 * appropriate state and probability entry. */
469 lzms_range_encode_bit(struct lzms_range_encoder *enc, int bit)
471 struct lzms_probability_entry *prob_entry;
474 /* Load the probability entry corresponding to the current state. */
475 prob_entry = &enc->prob_entries[enc->state];
477 /* Update the state based on the next bit. */
478 enc->state = ((enc->state << 1) | bit) & enc->mask;
480 /* Get the probability that the bit is 0. */
481 prob = lzms_get_probability(prob_entry);
483 /* Update the probability entry. */
484 lzms_update_probability_entry(prob_entry, bit);
486 /* Encode the bit. */
487 lzms_range_encoder_raw_encode_bit(enc->rc, bit, prob);
490 /* Called when an adaptive Huffman code needs to be rebuilt. */
492 lzms_rebuild_huffman_code(struct lzms_huffman_encoder *enc)
494 make_canonical_huffman_code(enc->num_syms,
495 LZMS_MAX_CODEWORD_LEN,
500 /* Dilute the frequencies. */
501 for (unsigned i = 0; i < enc->num_syms; i++) {
502 enc->sym_freqs[i] >>= 1;
503 enc->sym_freqs[i] += 1;
505 enc->num_syms_written = 0;
508 /* Encode a symbol using the specified Huffman encoder. */
510 lzms_huffman_encode_symbol(struct lzms_huffman_encoder *enc, unsigned sym)
512 lzms_output_bitstream_put_varbits(enc->os,
515 LZMS_MAX_CODEWORD_LEN);
516 ++enc->sym_freqs[sym];
517 if (++enc->num_syms_written == enc->rebuild_freq)
518 lzms_rebuild_huffman_code(enc);
522 lzms_update_fast_length_costs(struct lzms_compressor *c);
524 /* Encode a match length. */
526 lzms_encode_length(struct lzms_compressor *c, u32 length)
529 unsigned num_extra_bits;
532 slot = lzms_get_length_slot_fast(c, length);
534 extra_bits = length - lzms_length_slot_base[slot];
535 num_extra_bits = lzms_extra_length_bits[slot];
537 lzms_huffman_encode_symbol(&c->length_encoder, slot);
538 if (c->length_encoder.num_syms_written == 0)
539 lzms_update_fast_length_costs(c);
541 lzms_output_bitstream_put_varbits(c->length_encoder.os,
542 extra_bits, num_extra_bits, 30);
545 /* Encode an LZ match offset. */
547 lzms_encode_lz_offset(struct lzms_compressor *c, u32 offset)
550 unsigned num_extra_bits;
553 slot = lzms_get_offset_slot_fast(c, offset);
555 extra_bits = offset - lzms_offset_slot_base[slot];
556 num_extra_bits = lzms_extra_offset_bits[slot];
558 lzms_huffman_encode_symbol(&c->lz_offset_encoder, slot);
559 lzms_output_bitstream_put_varbits(c->lz_offset_encoder.os,
560 extra_bits, num_extra_bits, 30);
563 /* Encode a literal byte. */
565 lzms_encode_literal(struct lzms_compressor *c, unsigned literal)
567 /* Main bit: 0 = a literal, not a match. */
568 lzms_range_encode_bit(&c->main_range_encoder, 0);
570 /* Encode the literal using the current literal Huffman code. */
571 lzms_huffman_encode_symbol(&c->literal_encoder, literal);
574 /* Encode an LZ repeat offset match. */
576 lzms_encode_lz_repeat_offset_match(struct lzms_compressor *c,
577 u32 length, unsigned rep_index)
581 /* Main bit: 1 = a match, not a literal. */
582 lzms_range_encode_bit(&c->main_range_encoder, 1);
584 /* Match bit: 0 = an LZ match, not a delta match. */
585 lzms_range_encode_bit(&c->match_range_encoder, 0);
587 /* LZ match bit: 1 = repeat offset, not an explicit offset. */
588 lzms_range_encode_bit(&c->lz_match_range_encoder, 1);
590 /* Encode the repeat offset index. A 1 bit is encoded for each index
591 * passed up. This sequence of 1 bits is terminated by a 0 bit, or
592 * automatically when (LZMS_NUM_RECENT_OFFSETS - 1) 1 bits have been
594 for (i = 0; i < rep_index; i++)
595 lzms_range_encode_bit(&c->lz_repeat_match_range_encoders[i], 1);
597 if (i < LZMS_NUM_RECENT_OFFSETS - 1)
598 lzms_range_encode_bit(&c->lz_repeat_match_range_encoders[i], 0);
600 /* Encode the match length. */
601 lzms_encode_length(c, length);
604 /* Encode an LZ explicit offset match. */
606 lzms_encode_lz_explicit_offset_match(struct lzms_compressor *c,
607 u32 length, u32 offset)
609 /* Main bit: 1 = a match, not a literal. */
610 lzms_range_encode_bit(&c->main_range_encoder, 1);
612 /* Match bit: 0 = an LZ match, not a delta match. */
613 lzms_range_encode_bit(&c->match_range_encoder, 0);
615 /* LZ match bit: 0 = explicit offset, not a repeat offset. */
616 lzms_range_encode_bit(&c->lz_match_range_encoder, 0);
618 /* Encode the match offset. */
619 lzms_encode_lz_offset(c, offset);
621 /* Encode the match length. */
622 lzms_encode_length(c, length);
626 lzms_encode_item(struct lzms_compressor *c, u64 mc_item_data)
628 u32 len = mc_item_data & MC_LEN_MASK;
629 u32 offset_data = mc_item_data >> MC_OFFSET_SHIFT;
632 lzms_encode_literal(c, offset_data);
633 else if (offset_data < LZMS_NUM_RECENT_OFFSETS)
634 lzms_encode_lz_repeat_offset_match(c, len, offset_data);
636 lzms_encode_lz_explicit_offset_match(c, len, offset_data - LZMS_OFFSET_OFFSET);
639 /* Encode a list of matches and literals chosen by the parsing algorithm. */
641 lzms_encode_item_list(struct lzms_compressor *c,
642 struct lzms_mc_pos_data *cur_optimum_ptr)
644 struct lzms_mc_pos_data *end_optimum_ptr;
648 /* The list is currently in reverse order (last item to first item).
650 end_optimum_ptr = cur_optimum_ptr;
651 saved_item = cur_optimum_ptr->mc_item_data;
654 cur_optimum_ptr -= item & MC_LEN_MASK;
655 saved_item = cur_optimum_ptr->mc_item_data;
656 cur_optimum_ptr->mc_item_data = item;
657 } while (cur_optimum_ptr != c->optimum);
659 /* Walk the list of items from beginning to end, encoding each item. */
661 lzms_encode_item(c, cur_optimum_ptr->mc_item_data);
662 cur_optimum_ptr += (cur_optimum_ptr->mc_item_data) & MC_LEN_MASK;
663 } while (cur_optimum_ptr != end_optimum_ptr);
666 /* Each bit costs 1 << LZMS_COST_SHIFT units. */
667 #define LZMS_COST_SHIFT 6
669 /*#define LZMS_RC_COSTS_USE_FLOATING_POINT*/
672 lzms_rc_costs[LZMS_PROBABILITY_MAX + 1];
674 #ifdef LZMS_RC_COSTS_USE_FLOATING_POINT
679 lzms_do_init_rc_costs(void)
681 /* Fill in a table that maps range coding probabilities needed to code a
682 * bit X (0 or 1) to the number of bits (scaled by a constant factor, to
683 * handle fractional costs) needed to code that bit X.
685 * Consider the range of the range decoder. To eliminate exactly half
686 * the range (logical probability of 0.5), we need exactly 1 bit. For
687 * lower probabilities we need more bits and for higher probabilities we
688 * need fewer bits. In general, a logical probability of N will
689 * eliminate the proportion 1 - N of the range; this information takes
690 * log2(1 / N) bits to encode.
692 * The below loop is simply calculating this number of bits for each
693 * possible probability allowed by the LZMS compression format, but
694 * without using real numbers. To handle fractional probabilities, each
695 * cost is multiplied by (1 << LZMS_COST_SHIFT). These techniques are
696 * based on those used by LZMA.
698 * Note that in LZMS, a probability x really means x / 64, and 0 / 64 is
699 * really interpreted as 1 / 64 and 64 / 64 is really interpreted as
702 for (u32 i = 0; i <= LZMS_PROBABILITY_MAX; i++) {
707 else if (prob == LZMS_PROBABILITY_MAX)
708 prob = LZMS_PROBABILITY_MAX - 1;
710 #ifdef LZMS_RC_COSTS_USE_FLOATING_POINT
711 lzms_rc_costs[i] = log2((double)LZMS_PROBABILITY_MAX / prob) *
712 (1 << LZMS_COST_SHIFT);
716 for (u32 j = 0; j < LZMS_COST_SHIFT; j++) {
719 while (w >= ((u32)1 << 16)) {
724 lzms_rc_costs[i] = (LZMS_PROBABILITY_BITS << LZMS_COST_SHIFT) -
731 lzms_init_rc_costs(void)
733 static pthread_once_t once = PTHREAD_ONCE_INIT;
735 pthread_once(&once, lzms_do_init_rc_costs);
738 /* Return the cost to range-encode the specified bit from the specified state.*/
740 lzms_rc_bit_cost(const struct lzms_range_encoder *enc, u8 cur_state, int bit)
745 prob_zero = enc->prob_entries[cur_state].num_recent_zero_bits;
748 prob_correct = prob_zero;
750 prob_correct = LZMS_PROBABILITY_MAX - prob_zero;
752 return lzms_rc_costs[prob_correct];
755 /* Return the cost to Huffman-encode the specified symbol. */
757 lzms_huffman_symbol_cost(const struct lzms_huffman_encoder *enc, unsigned sym)
759 return (u32)enc->lens[sym] << LZMS_COST_SHIFT;
762 /* Return the cost to encode the specified literal byte. */
764 lzms_literal_cost(const struct lzms_compressor *c, unsigned literal,
765 const struct lzms_adaptive_state *state)
767 return lzms_rc_bit_cost(&c->main_range_encoder, state->main_state, 0) +
768 lzms_huffman_symbol_cost(&c->literal_encoder, literal);
771 /* Update the table that directly provides the costs for small lengths. */
773 lzms_update_fast_length_costs(struct lzms_compressor *c)
779 for (len = 1; len < LZMS_NUM_FAST_LENGTHS; len++) {
781 while (len >= lzms_length_slot_base[slot + 1]) {
783 cost = (u32)(c->length_encoder.lens[slot] +
784 lzms_extra_length_bits[slot]) << LZMS_COST_SHIFT;
787 c->length_cost_fast[len] = cost;
791 /* Return the cost to encode the specified match length, which must be less than
792 * LZMS_NUM_FAST_LENGTHS. */
794 lzms_fast_length_cost(const struct lzms_compressor *c, u32 length)
796 LZMS_ASSERT(length < LZMS_NUM_FAST_LENGTHS);
797 return c->length_cost_fast[length];
800 /* Return the cost to encode the specified LZ match offset. */
802 lzms_lz_offset_cost(const struct lzms_compressor *c, u32 offset)
804 unsigned slot = lzms_get_offset_slot_fast(c, offset);
806 return (u32)(c->lz_offset_encoder.lens[slot] +
807 lzms_extra_offset_bits[slot]) << LZMS_COST_SHIFT;
811 * Consider coding the match at repeat offset index @rep_idx. Consider each
812 * length from the minimum (2) to the full match length (@rep_len).
815 lzms_consider_lz_repeat_offset_match(const struct lzms_compressor *c,
816 struct lzms_mc_pos_data *cur_optimum_ptr,
817 u32 rep_len, unsigned rep_idx)
824 base_cost = cur_optimum_ptr->cost;
826 base_cost += lzms_rc_bit_cost(&c->main_range_encoder,
827 cur_optimum_ptr->state.main_state, 1);
829 base_cost += lzms_rc_bit_cost(&c->match_range_encoder,
830 cur_optimum_ptr->state.match_state, 0);
832 base_cost += lzms_rc_bit_cost(&c->lz_match_range_encoder,
833 cur_optimum_ptr->state.lz_match_state, 1);
835 for (i = 0; i < rep_idx; i++)
836 base_cost += lzms_rc_bit_cost(&c->lz_repeat_match_range_encoders[i],
837 cur_optimum_ptr->state.lz_repeat_match_state[i], 1);
839 if (i < LZMS_NUM_RECENT_OFFSETS - 1)
840 base_cost += lzms_rc_bit_cost(&c->lz_repeat_match_range_encoders[i],
841 cur_optimum_ptr->state.lz_repeat_match_state[i], 0);
845 cost = base_cost + lzms_fast_length_cost(c, len);
846 if (cost < (cur_optimum_ptr + len)->cost) {
847 (cur_optimum_ptr + len)->mc_item_data =
848 ((u64)rep_idx << MC_OFFSET_SHIFT) | len;
849 (cur_optimum_ptr + len)->cost = cost;
851 } while (++len <= rep_len);
855 * Consider coding each match in @matches as an explicit offset match.
857 * @matches must be sorted by strictly increasing length and strictly increasing
858 * offset. This is guaranteed by the match-finder.
860 * We consider each length from the minimum (2) to the longest
861 * (matches[num_matches - 1].len). For each length, we consider only the
862 * smallest offset for which that length is available. Although this is not
863 * guaranteed to be optimal due to the possibility of a larger offset costing
864 * less than a smaller offset to code, this is a very useful heuristic.
867 lzms_consider_lz_explicit_offset_matches(const struct lzms_compressor *c,
868 struct lzms_mc_pos_data *cur_optimum_ptr,
869 const struct lz_match matches[],
878 base_cost = cur_optimum_ptr->cost;
880 base_cost += lzms_rc_bit_cost(&c->main_range_encoder,
881 cur_optimum_ptr->state.main_state, 1);
883 base_cost += lzms_rc_bit_cost(&c->match_range_encoder,
884 cur_optimum_ptr->state.match_state, 0);
886 base_cost += lzms_rc_bit_cost(&c->lz_match_range_encoder,
887 cur_optimum_ptr->state.lz_match_state, 0);
891 position_cost = base_cost + lzms_lz_offset_cost(c, matches[i].offset);
893 cost = position_cost + lzms_fast_length_cost(c, len);
894 if (cost < (cur_optimum_ptr + len)->cost) {
895 (cur_optimum_ptr + len)->mc_item_data =
896 ((u64)(matches[i].offset + LZMS_OFFSET_OFFSET)
897 << MC_OFFSET_SHIFT) | len;
898 (cur_optimum_ptr + len)->cost = cost;
900 } while (++len <= matches[i].len);
901 } while (++i != num_matches);
905 lzms_init_adaptive_state(struct lzms_adaptive_state *state)
909 lzms_init_lz_lru_queues(&state->lru);
910 state->main_state = 0;
911 state->match_state = 0;
912 state->lz_match_state = 0;
913 for (i = 0; i < LZMS_NUM_RECENT_OFFSETS - 1; i++)
914 state->lz_repeat_match_state[i] = 0;
918 lzms_update_main_state(struct lzms_adaptive_state *state, int is_match)
920 state->main_state = ((state->main_state << 1) | is_match) % LZMS_NUM_MAIN_STATES;
924 lzms_update_match_state(struct lzms_adaptive_state *state, int is_delta)
926 state->match_state = ((state->match_state << 1) | is_delta) % LZMS_NUM_MATCH_STATES;
930 lzms_update_lz_match_state(struct lzms_adaptive_state *state, int is_repeat_offset)
932 state->lz_match_state = ((state->lz_match_state << 1) | is_repeat_offset) % LZMS_NUM_LZ_MATCH_STATES;
936 lzms_update_lz_repeat_match_state(struct lzms_adaptive_state *state, int rep_idx)
940 for (i = 0; i < rep_idx; i++)
941 state->lz_repeat_match_state[i] =
942 ((state->lz_repeat_match_state[i] << 1) | 1) %
943 LZMS_NUM_LZ_REPEAT_MATCH_STATES;
945 if (i < LZMS_NUM_RECENT_OFFSETS - 1)
946 state->lz_repeat_match_state[i] =
947 ((state->lz_repeat_match_state[i] << 1) | 0) %
948 LZMS_NUM_LZ_REPEAT_MATCH_STATES;
952 * The main near-optimal parsing routine.
954 * Briefly, the algorithm does an approximate minimum-cost path search to find a
955 * "near-optimal" sequence of matches and literals to output, based on the
956 * current cost model. The algorithm steps forward, position by position (byte
957 * by byte), and updates the minimum cost path to reach each later position that
958 * can be reached using a match or literal from the current position. This is
959 * essentially Dijkstra's algorithm in disguise: the graph nodes are positions,
960 * the graph edges are possible matches/literals to code, and the cost of each
961 * edge is the estimated number of bits that will be required to output the
962 * corresponding match or literal. But one difference is that we actually
963 * compute the lowest-cost path in pieces, where each piece is terminated when
964 * there are no choices to be made.
968 * - This does not output any delta matches.
970 * - The costs of literals and matches are estimated using the range encoder
971 * states and the semi-adaptive Huffman codes. Except for range encoding
972 * states, costs are assumed to be constant throughout a single run of the
973 * parsing algorithm, which can parse up to @optim_array_length bytes of data.
974 * This introduces a source of inaccuracy because the probabilities and
975 * Huffman codes can change over this part of the data.
978 lzms_near_optimal_parse(struct lzms_compressor *c)
980 const u8 *window_ptr;
981 const u8 *window_end;
982 struct lzms_mc_pos_data *cur_optimum_ptr;
983 struct lzms_mc_pos_data *end_optimum_ptr;
987 unsigned rep_max_idx;
994 window_ptr = c->cur_window;
995 window_end = window_ptr + c->cur_window_size;
997 lzms_init_adaptive_state(&c->optimum[0].state);
1000 /* Start building a new list of items, which will correspond to the next
1001 * piece of the overall minimum-cost path. */
1003 cur_optimum_ptr = c->optimum;
1004 cur_optimum_ptr->cost = 0;
1005 end_optimum_ptr = cur_optimum_ptr;
1007 /* States should currently be consistent with the encoders. */
1008 LZMS_ASSERT(cur_optimum_ptr->state.main_state == c->main_range_encoder.state);
1009 LZMS_ASSERT(cur_optimum_ptr->state.match_state == c->match_range_encoder.state);
1010 LZMS_ASSERT(cur_optimum_ptr->state.lz_match_state == c->lz_match_range_encoder.state);
1011 for (i = 0; i < LZMS_NUM_RECENT_OFFSETS - 1; i++)
1012 LZMS_ASSERT(cur_optimum_ptr->state.lz_repeat_match_state[i] ==
1013 c->lz_repeat_match_range_encoders[i].state);
1015 if (window_ptr == window_end)
1018 /* The following loop runs once for each per byte in the window, except
1019 * in a couple shortcut cases. */
1022 /* Find explicit offset matches with the current position. */
1023 num_matches = lz_mf_get_matches(c->mf, c->matches);
1027 * Find the longest repeat offset match with the current
1032 * - Only search for repeat offset matches if the
1033 * match-finder already found at least one match.
1035 * - Only consider the longest repeat offset match. It
1036 * seems to be rare for the optimal parse to include a
1037 * repeat offset match that doesn't have the longest
1038 * length (allowing for the possibility that not all
1039 * of that length is actually used).
1041 if (likely(window_ptr - c->cur_window >= LZMS_MAX_INIT_RECENT_OFFSET)) {
1042 BUILD_BUG_ON(LZMS_NUM_RECENT_OFFSETS != 3);
1043 rep_max_len = lz_repsearch3(window_ptr,
1044 window_end - window_ptr,
1045 cur_optimum_ptr->state.lru.recent_offsets,
1052 /* If there's a very long repeat offset match,
1053 * choose it immediately. */
1054 if (rep_max_len >= c->params.nice_match_length) {
1056 lz_mf_skip_positions(c->mf, rep_max_len - 1);
1057 window_ptr += rep_max_len;
1059 if (cur_optimum_ptr != c->optimum)
1060 lzms_encode_item_list(c, cur_optimum_ptr);
1062 lzms_encode_lz_repeat_offset_match(c, rep_max_len,
1065 c->optimum[0].state = cur_optimum_ptr->state;
1067 lzms_update_main_state(&c->optimum[0].state, 1);
1068 lzms_update_match_state(&c->optimum[0].state, 0);
1069 lzms_update_lz_match_state(&c->optimum[0].state, 1);
1070 lzms_update_lz_repeat_match_state(&c->optimum[0].state,
1073 c->optimum[0].state.lru.upcoming_offset =
1074 c->optimum[0].state.lru.recent_offsets[rep_max_idx];
1076 for (i = rep_max_idx; i < LZMS_NUM_RECENT_OFFSETS; i++)
1077 c->optimum[0].state.lru.recent_offsets[i] =
1078 c->optimum[0].state.lru.recent_offsets[i + 1];
1080 lzms_update_lz_lru_queue(&c->optimum[0].state.lru);
1084 /* If reaching any positions for the first time,
1085 * initialize their costs to "infinity". */
1086 while (end_optimum_ptr < cur_optimum_ptr + rep_max_len)
1087 (++end_optimum_ptr)->cost = MC_INFINITE_COST;
1089 /* Consider coding a repeat offset match. */
1090 lzms_consider_lz_repeat_offset_match(c, cur_optimum_ptr,
1091 rep_max_len, rep_max_idx);
1094 longest_len = c->matches[num_matches - 1].len;
1096 /* If there's a very long explicit offset match, choose
1097 * it immediately. */
1098 if (longest_len >= c->params.nice_match_length) {
1100 lz_mf_skip_positions(c->mf, longest_len - 1);
1101 window_ptr += longest_len;
1103 if (cur_optimum_ptr != c->optimum)
1104 lzms_encode_item_list(c, cur_optimum_ptr);
1106 lzms_encode_lz_explicit_offset_match(c, longest_len,
1107 c->matches[num_matches - 1].offset);
1109 c->optimum[0].state = cur_optimum_ptr->state;
1111 lzms_update_main_state(&c->optimum[0].state, 1);
1112 lzms_update_match_state(&c->optimum[0].state, 0);
1113 lzms_update_lz_match_state(&c->optimum[0].state, 0);
1115 c->optimum[0].state.lru.upcoming_offset =
1116 c->matches[num_matches - 1].offset;
1118 lzms_update_lz_lru_queue(&c->optimum[0].state.lru);
1122 /* If reaching any positions for the first time,
1123 * initialize their costs to "infinity". */
1124 while (end_optimum_ptr < cur_optimum_ptr + longest_len)
1125 (++end_optimum_ptr)->cost = MC_INFINITE_COST;
1127 /* Consider coding an explicit offset match. */
1128 lzms_consider_lz_explicit_offset_matches(c, cur_optimum_ptr,
1129 c->matches, num_matches);
1131 /* No matches found. The only choice at this position
1132 * is to code a literal. */
1134 if (end_optimum_ptr == cur_optimum_ptr)
1135 (++end_optimum_ptr)->cost = MC_INFINITE_COST;
1138 /* Consider coding a literal.
1140 * To avoid an extra unpredictable brench, actually checking the
1141 * preferability of coding a literal is integrated into the
1142 * adaptive state update code below. */
1143 literal = *window_ptr++;
1144 cost = cur_optimum_ptr->cost +
1145 lzms_literal_cost(c, literal, &cur_optimum_ptr->state);
1147 /* Advance to the next position. */
1150 /* The lowest-cost path to the current position is now known.
1151 * Finalize the adaptive state that results from taking this
1152 * lowest-cost path. */
1154 if (cost < cur_optimum_ptr->cost) {
1156 cur_optimum_ptr->cost = cost;
1157 cur_optimum_ptr->mc_item_data = ((u64)literal << MC_OFFSET_SHIFT) | 1;
1159 cur_optimum_ptr->state = (cur_optimum_ptr - 1)->state;
1161 lzms_update_main_state(&cur_optimum_ptr->state, 0);
1163 cur_optimum_ptr->state.lru.upcoming_offset = 0;
1166 len = cur_optimum_ptr->mc_item_data & MC_LEN_MASK;
1167 offset_data = cur_optimum_ptr->mc_item_data >> MC_OFFSET_SHIFT;
1169 cur_optimum_ptr->state = (cur_optimum_ptr - len)->state;
1171 lzms_update_main_state(&cur_optimum_ptr->state, 1);
1172 lzms_update_match_state(&cur_optimum_ptr->state, 0);
1174 if (offset_data >= LZMS_NUM_RECENT_OFFSETS) {
1176 /* Explicit offset LZ match */
1178 lzms_update_lz_match_state(&cur_optimum_ptr->state, 0);
1180 cur_optimum_ptr->state.lru.upcoming_offset =
1181 offset_data - LZMS_OFFSET_OFFSET;
1183 /* Repeat offset LZ match */
1185 lzms_update_lz_match_state(&cur_optimum_ptr->state, 1);
1186 lzms_update_lz_repeat_match_state(&cur_optimum_ptr->state,
1189 cur_optimum_ptr->state.lru.upcoming_offset =
1190 cur_optimum_ptr->state.lru.recent_offsets[offset_data];
1192 for (i = offset_data; i < LZMS_NUM_RECENT_OFFSETS; i++)
1193 cur_optimum_ptr->state.lru.recent_offsets[i] =
1194 cur_optimum_ptr->state.lru.recent_offsets[i + 1];
1198 lzms_update_lz_lru_queue(&cur_optimum_ptr->state.lru);
1201 * This loop will terminate when either of the following
1202 * conditions is true:
1204 * (1) cur_optimum_ptr == end_optimum_ptr
1206 * There are no paths that extend beyond the current
1207 * position. In this case, any path to a later position
1208 * must pass through the current position, so we can go
1209 * ahead and choose the list of items that led to this
1212 * (2) cur_optimum_ptr == c->optimum_end
1214 * This bounds the number of times the algorithm can step
1215 * forward before it is guaranteed to start choosing items.
1216 * This limits the memory usage. It also guarantees that
1217 * the parser will not go too long without updating the
1218 * probability tables.
1220 * Note: no check for end-of-window is needed because
1221 * end-of-window will trigger condition (1).
1223 if (cur_optimum_ptr == end_optimum_ptr ||
1224 cur_optimum_ptr == c->optimum_end)
1226 c->optimum[0].state = cur_optimum_ptr->state;
1231 /* Output the current list of items that constitute the minimum-cost
1232 * path to the current position. */
1233 lzms_encode_item_list(c, cur_optimum_ptr);
1238 lzms_init_range_encoder(struct lzms_range_encoder *enc,
1239 struct lzms_range_encoder_raw *rc, u32 num_states)
1243 LZMS_ASSERT(is_power_of_2(num_states));
1244 enc->mask = num_states - 1;
1245 for (u32 i = 0; i < num_states; i++) {
1246 enc->prob_entries[i].num_recent_zero_bits = LZMS_INITIAL_PROBABILITY;
1247 enc->prob_entries[i].recent_bits = LZMS_INITIAL_RECENT_BITS;
1252 lzms_init_huffman_encoder(struct lzms_huffman_encoder *enc,
1253 struct lzms_output_bitstream *os,
1255 unsigned rebuild_freq)
1258 enc->num_syms_written = 0;
1259 enc->rebuild_freq = rebuild_freq;
1260 enc->num_syms = num_syms;
1261 for (unsigned i = 0; i < num_syms; i++)
1262 enc->sym_freqs[i] = 1;
1264 make_canonical_huffman_code(enc->num_syms,
1265 LZMS_MAX_CODEWORD_LEN,
1271 /* Prepare the LZMS compressor for compressing a block of data. */
1273 lzms_prepare_compressor(struct lzms_compressor *c, const u8 *udata, u32 ulen,
1274 le16 *cdata, u32 clen16)
1276 unsigned num_offset_slots;
1278 /* Copy the uncompressed data into the @c->cur_window buffer. */
1279 memcpy(c->cur_window, udata, ulen);
1280 c->cur_window_size = ulen;
1282 /* Initialize the raw range encoder (writing forwards). */
1283 lzms_range_encoder_raw_init(&c->rc, cdata, clen16);
1285 /* Initialize the output bitstream for Huffman symbols and verbatim bits
1286 * (writing backwards). */
1287 lzms_output_bitstream_init(&c->os, cdata, clen16);
1289 /* Calculate the number of offset slots required. */
1290 num_offset_slots = lzms_get_offset_slot(ulen - 1) + 1;
1292 /* Initialize a Huffman encoder for each alphabet. */
1293 lzms_init_huffman_encoder(&c->literal_encoder, &c->os,
1294 LZMS_NUM_LITERAL_SYMS,
1295 LZMS_LITERAL_CODE_REBUILD_FREQ);
1297 lzms_init_huffman_encoder(&c->lz_offset_encoder, &c->os,
1299 LZMS_LZ_OFFSET_CODE_REBUILD_FREQ);
1301 lzms_init_huffman_encoder(&c->length_encoder, &c->os,
1303 LZMS_LENGTH_CODE_REBUILD_FREQ);
1305 lzms_init_huffman_encoder(&c->delta_offset_encoder, &c->os,
1307 LZMS_DELTA_OFFSET_CODE_REBUILD_FREQ);
1309 lzms_init_huffman_encoder(&c->delta_power_encoder, &c->os,
1310 LZMS_NUM_DELTA_POWER_SYMS,
1311 LZMS_DELTA_POWER_CODE_REBUILD_FREQ);
1313 /* Initialize range encoders, all of which wrap around the same
1314 * lzms_range_encoder_raw. */
1315 lzms_init_range_encoder(&c->main_range_encoder,
1316 &c->rc, LZMS_NUM_MAIN_STATES);
1318 lzms_init_range_encoder(&c->match_range_encoder,
1319 &c->rc, LZMS_NUM_MATCH_STATES);
1321 lzms_init_range_encoder(&c->lz_match_range_encoder,
1322 &c->rc, LZMS_NUM_LZ_MATCH_STATES);
1324 for (unsigned i = 0; i < ARRAY_LEN(c->lz_repeat_match_range_encoders); i++)
1325 lzms_init_range_encoder(&c->lz_repeat_match_range_encoders[i],
1326 &c->rc, LZMS_NUM_LZ_REPEAT_MATCH_STATES);
1328 lzms_init_range_encoder(&c->delta_match_range_encoder,
1329 &c->rc, LZMS_NUM_DELTA_MATCH_STATES);
1331 for (unsigned i = 0; i < ARRAY_LEN(c->delta_repeat_match_range_encoders); i++)
1332 lzms_init_range_encoder(&c->delta_repeat_match_range_encoders[i],
1333 &c->rc, LZMS_NUM_DELTA_REPEAT_MATCH_STATES);
1335 /* Set initial length costs for lengths < LZMS_NUM_FAST_LENGTHS. */
1336 lzms_update_fast_length_costs(c);
1339 /* Flush the output streams, prepare the final compressed data, and return its
1342 * A return value of 0 indicates that the data could not be compressed to fit in
1343 * the available space. */
1345 lzms_finalize(struct lzms_compressor *c, u8 *cdata, size_t csize_avail)
1347 size_t num_forwards_bytes;
1348 size_t num_backwards_bytes;
1350 /* Flush both the forwards and backwards streams, and make sure they
1351 * didn't cross each other and start overwriting each other's data. */
1352 if (!lzms_output_bitstream_flush(&c->os))
1355 if (!lzms_range_encoder_raw_flush(&c->rc))
1358 if (c->rc.next > c->os.next)
1361 /* Now the compressed buffer contains the data output by the forwards
1362 * bitstream, then empty space, then data output by the backwards
1363 * bitstream. Move the data output by the backwards bitstream to be
1364 * adjacent to the data output by the forward bitstream, and calculate
1365 * the compressed size that this results in. */
1366 num_forwards_bytes = (u8*)c->rc.next - (u8*)cdata;
1367 num_backwards_bytes = ((u8*)cdata + csize_avail) - (u8*)c->os.next;
1369 memmove(cdata + num_forwards_bytes, c->os.next, num_backwards_bytes);
1371 return num_forwards_bytes + num_backwards_bytes;
1374 /* Set internal compression parameters for the specified compression level and
1375 * maximum window size. */
1377 lzms_build_params(unsigned int compression_level,
1378 struct lzms_compressor_params *params)
1380 /* Allow length 2 matches if the compression level is sufficiently high.
1382 if (compression_level >= 45)
1383 params->min_match_length = 2;
1385 params->min_match_length = 3;
1387 /* Scale nice_match_length and max_search_depth with the compression
1388 * level. But to allow an optimization on length cost calculations,
1389 * don't allow nice_match_length to exceed LZMS_NUM_FAST_LENGTH. */
1390 params->nice_match_length = ((u64)compression_level * 32) / 50;
1391 if (params->nice_match_length < params->min_match_length)
1392 params->nice_match_length = params->min_match_length;
1393 if (params->nice_match_length > LZMS_NUM_FAST_LENGTHS)
1394 params->nice_match_length = LZMS_NUM_FAST_LENGTHS;
1395 params->max_search_depth = compression_level;
1397 params->optim_array_length = 1024;
1400 /* Given the internal compression parameters and maximum window size, build the
1401 * Lempel-Ziv match-finder parameters. */
1403 lzms_build_mf_params(const struct lzms_compressor_params *lzms_params,
1404 u32 max_window_size, struct lz_mf_params *mf_params)
1406 memset(mf_params, 0, sizeof(*mf_params));
1408 /* Choose an appropriate match-finding algorithm. */
1409 if (max_window_size <= 2097152)
1410 mf_params->algorithm = LZ_MF_BINARY_TREES;
1411 else if (max_window_size <= 33554432)
1412 mf_params->algorithm = LZ_MF_LCP_INTERVAL_TREE;
1414 mf_params->algorithm = LZ_MF_LINKED_SUFFIX_ARRAY;
1416 mf_params->max_window_size = max_window_size;
1417 mf_params->min_match_len = lzms_params->min_match_length;
1418 mf_params->max_search_depth = lzms_params->max_search_depth;
1419 mf_params->nice_match_len = lzms_params->nice_match_length;
1423 lzms_free_compressor(void *_c);
1426 lzms_get_needed_memory(size_t max_block_size, unsigned int compression_level)
1428 struct lzms_compressor_params params;
1429 struct lz_mf_params mf_params;
1432 if (max_block_size >= INT32_MAX)
1435 lzms_build_params(compression_level, ¶ms);
1436 lzms_build_mf_params(¶ms, max_block_size, &mf_params);
1438 size += sizeof(struct lzms_compressor);
1441 size += max_block_size;
1444 size += lz_mf_get_needed_memory(mf_params.algorithm, max_block_size);
1447 size += min(params.max_search_depth, params.nice_match_length) *
1448 sizeof(struct lz_match);
1451 size += (params.optim_array_length + params.nice_match_length) *
1452 sizeof(struct lzms_mc_pos_data);
1458 lzms_create_compressor(size_t max_block_size, unsigned int compression_level,
1461 struct lzms_compressor *c;
1462 struct lzms_compressor_params params;
1463 struct lz_mf_params mf_params;
1465 if (max_block_size >= INT32_MAX)
1466 return WIMLIB_ERR_INVALID_PARAM;
1468 lzms_build_params(compression_level, ¶ms);
1469 lzms_build_mf_params(¶ms, max_block_size, &mf_params);
1470 if (!lz_mf_params_valid(&mf_params))
1471 return WIMLIB_ERR_INVALID_PARAM;
1473 c = CALLOC(1, sizeof(struct lzms_compressor));
1479 c->cur_window = MALLOC(max_block_size);
1483 c->mf = lz_mf_alloc(&mf_params);
1487 c->matches = MALLOC(min(params.max_search_depth,
1488 params.nice_match_length) *
1489 sizeof(struct lz_match));
1493 c->optimum = MALLOC((params.optim_array_length +
1494 params.nice_match_length) *
1495 sizeof(struct lzms_mc_pos_data));
1498 c->optimum_end = &c->optimum[params.optim_array_length];
1502 lzms_init_rc_costs();
1504 lzms_init_fast_slots(c);
1510 lzms_free_compressor(c);
1511 return WIMLIB_ERR_NOMEM;
1515 lzms_compress(const void *uncompressed_data, size_t uncompressed_size,
1516 void *compressed_data, size_t compressed_size_avail, void *_c)
1518 struct lzms_compressor *c = _c;
1520 /* Don't bother compressing extremely small inputs. */
1521 if (uncompressed_size < 4)
1524 /* Cap the available compressed size to a 32-bit integer and round it
1525 * down to the nearest multiple of 2. */
1526 if (compressed_size_avail > UINT32_MAX)
1527 compressed_size_avail = UINT32_MAX;
1528 if (compressed_size_avail & 1)
1529 compressed_size_avail--;
1531 /* Initialize the compressor structures. */
1532 lzms_prepare_compressor(c, uncompressed_data, uncompressed_size,
1533 compressed_data, compressed_size_avail / 2);
1535 /* Preprocess the uncompressed data. */
1536 lzms_x86_filter(c->cur_window, c->cur_window_size,
1537 c->last_target_usages, false);
1539 /* Load the window into the match-finder. */
1540 lz_mf_load_window(c->mf, c->cur_window, c->cur_window_size);
1542 /* Compute and encode a literal/match sequence that decompresses to the
1543 * preprocessed data. */
1544 lzms_near_optimal_parse(c);
1546 /* Return the compressed data size or 0. */
1547 return lzms_finalize(c, compressed_data, compressed_size_avail);
1551 lzms_free_compressor(void *_c)
1553 struct lzms_compressor *c = _c;
1556 FREE(c->cur_window);
1564 const struct compressor_ops lzms_compressor_ops = {
1565 .get_needed_memory = lzms_get_needed_memory,
1566 .create_compressor = lzms_create_compressor,
1567 .compress = lzms_compress,
1568 .free_compressor = lzms_free_compressor,