4 * A compressor that produces output compatible with the LZX compression format.
8 * Copyright (C) 2012, 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/.
28 * This file contains a compressor for the LZX ("Lempel-Ziv eXtended")
29 * compression format, as used in the WIM (Windows IMaging) file format.
31 * Two different parsing algorithms are implemented: "near-optimal" and "lazy".
32 * "Near-optimal" is significantly slower than "lazy", but results in a better
33 * compression ratio. The "near-optimal" algorithm is used at the default
36 * This file may need some slight modifications to be used outside of the WIM
37 * format. In particular, in other situations the LZX block header might be
38 * slightly different, and a sliding window rather than a fixed-size window
41 * Note: LZX is a compression format derived from DEFLATE, the format used by
42 * zlib and gzip. Both LZX and DEFLATE use LZ77 matching and Huffman coding.
43 * Certain details are quite similar, such as the method for storing Huffman
44 * codes. However, the main differences are:
46 * - LZX preprocesses the data to attempt to make x86 machine code slightly more
47 * compressible before attempting to compress it further.
49 * - LZX uses a "main" alphabet which combines literals and matches, with the
50 * match symbols containing a "length header" (giving all or part of the match
51 * length) and an "offset slot" (giving, roughly speaking, the order of
52 * magnitude of the match offset).
54 * - LZX does not have static Huffman blocks (that is, the kind with preset
55 * Huffman codes); however it does have two types of dynamic Huffman blocks
56 * ("verbatim" and "aligned").
58 * - LZX has a minimum match length of 2 rather than 3. Length 2 matches can be
59 * useful, but generally only if the parser is smart about choosing them.
61 * - In LZX, offset slots 0 through 2 actually represent entries in an LRU queue
62 * of match offsets. This is very useful for certain types of files, such as
63 * binary files that have repeating records.
70 #include "wimlib/compress_common.h"
71 #include "wimlib/compressor_ops.h"
72 #include "wimlib/endianness.h"
73 #include "wimlib/error.h"
74 #include "wimlib/lz_mf.h"
75 #include "wimlib/lz_repsearch.h"
76 #include "wimlib/lzx.h"
77 #include "wimlib/util.h"
82 #define LZX_OPTIM_ARRAY_LENGTH 4096
84 #define LZX_DIV_BLOCK_SIZE 32768
86 #define LZX_CACHE_PER_POS 8
88 #define LZX_MAX_MATCHES_PER_POS (LZX_MAX_MATCH_LEN - LZX_MIN_MATCH_LEN + 1)
90 #define LZX_CACHE_LEN (LZX_DIV_BLOCK_SIZE * (LZX_CACHE_PER_POS + 1))
92 struct lzx_compressor;
94 /* Codewords for the LZX Huffman codes. */
95 struct lzx_codewords {
96 u32 main[LZX_MAINCODE_MAX_NUM_SYMBOLS];
97 u32 len[LZX_LENCODE_NUM_SYMBOLS];
98 u32 aligned[LZX_ALIGNEDCODE_NUM_SYMBOLS];
101 /* Codeword lengths (in bits) for the LZX Huffman codes.
102 * A zero length means the corresponding codeword has zero frequency. */
104 u8 main[LZX_MAINCODE_MAX_NUM_SYMBOLS];
105 u8 len[LZX_LENCODE_NUM_SYMBOLS];
106 u8 aligned[LZX_ALIGNEDCODE_NUM_SYMBOLS];
109 /* Estimated cost, in bits, to output each symbol in the LZX Huffman codes. */
111 u8 main[LZX_MAINCODE_MAX_NUM_SYMBOLS];
112 u8 len[LZX_LENCODE_NUM_SYMBOLS];
113 u8 aligned[LZX_ALIGNEDCODE_NUM_SYMBOLS];
116 /* Codewords and lengths for the LZX Huffman codes. */
118 struct lzx_codewords codewords;
119 struct lzx_lens lens;
122 /* Symbol frequency counters for the LZX Huffman codes. */
124 u32 main[LZX_MAINCODE_MAX_NUM_SYMBOLS];
125 u32 len[LZX_LENCODE_NUM_SYMBOLS];
126 u32 aligned[LZX_ALIGNEDCODE_NUM_SYMBOLS];
129 /* Intermediate LZX match/literal format */
132 /* Bits 0 - 9: Main symbol
133 * Bits 10 - 17: Length symbol
134 * Bits 18 - 22: Number of extra offset bits
135 * Bits 23+ : Extra offset bits */
139 /* Internal compression parameters */
140 struct lzx_compressor_params {
141 u32 (*choose_items_for_block)(struct lzx_compressor *, u32, u32);
142 u32 num_optim_passes;
143 enum lz_mf_algo mf_algo;
144 u32 min_match_length;
145 u32 nice_match_length;
146 u32 max_search_depth;
150 * Match chooser position data:
152 * An array of these structures is used during the near-optimal match-choosing
153 * algorithm. They correspond to consecutive positions in the window and are
154 * used to keep track of the cost to reach each position, and the match/literal
155 * choices that need to be chosen to reach that position.
157 struct lzx_mc_pos_data {
159 /* The cost, in bits, of the lowest-cost path that has been found to
160 * reach this position. This can change as progressively lower cost
161 * paths are found to reach this position. */
163 #define MC_INFINITE_COST UINT32_MAX
165 /* The match or literal that was taken to reach this position. This can
166 * change as progressively lower cost paths are found to reach this
169 * This variable is divided into two bitfields.
172 * Low bits are 1, high bits are the literal.
174 * Explicit offset matches:
175 * Low bits are the match length, high bits are the offset plus 2.
177 * Repeat offset matches:
178 * Low bits are the match length, high bits are the queue index.
181 #define MC_OFFSET_SHIFT 9
182 #define MC_LEN_MASK ((1 << MC_OFFSET_SHIFT) - 1)
184 /* The state of the LZX recent match offsets queue at this position.
185 * This is filled in lazily, only after the minimum-cost path to this
188 * Note: the way we handle this adaptive state in the "minimum-cost"
189 * parse is actually only an approximation. It's possible for the
190 * globally optimal, minimum cost path to contain a prefix, ending at a
191 * position, where that path prefix is *not* the minimum cost path to
192 * that position. This can happen if such a path prefix results in a
193 * different adaptive state which results in lower costs later. We do
194 * not solve this problem; we only consider the lowest cost to reach
195 * each position, which seems to be an acceptable approximation. */
196 struct lzx_lru_queue queue _aligned_attribute(16);
198 } _aligned_attribute(16);
200 /* State of the LZX compressor */
201 struct lzx_compressor {
203 /* Internal compression parameters */
204 struct lzx_compressor_params params;
206 /* The preprocessed buffer of data being compressed */
209 /* Number of bytes of data to be compressed, which is the number of
210 * bytes of data in @cur_window that are actually valid. */
213 /* log2 order of the LZX window size for LZ match offset encoding
214 * purposes. Will be >= LZX_MIN_WINDOW_ORDER and <=
215 * LZX_MAX_WINDOW_ORDER.
217 * Note: 1 << @window_order is normally equal to @max_window_size,
218 * a.k.a. the allocated size of @cur_window, but it will be greater than
219 * @max_window_size in the event that the compressor was created with a
220 * non-power-of-2 block size. (See lzx_get_window_order().) */
221 unsigned window_order;
223 /* Number of symbols in the main alphabet. This depends on
224 * @window_order, since @window_order determines the maximum possible
225 * offset. It does not, however, depend on the *actual* size of the
226 * current data buffer being processed, which might be less than 1 <<
228 unsigned num_main_syms;
230 /* Lempel-Ziv match-finder */
233 /* Match-finder wrapper functions and data for near-optimal parsing.
235 * When doing more than one match-choosing pass over the data, matches
236 * found by the match-finder are cached to achieve a slight speedup when
237 * the same matches are needed on subsequent passes. This is suboptimal
238 * because different matches may be preferred with different cost
239 * models, but it is a very worthwhile speedup. */
240 unsigned (*get_matches_func)(struct lzx_compressor *, const struct lz_match **);
241 void (*skip_bytes_func)(struct lzx_compressor *, unsigned n);
242 u32 match_window_pos;
243 u32 match_window_end;
244 struct lz_match *cached_matches;
245 struct lz_match *cache_ptr;
246 struct lz_match *cache_limit;
248 /* Position data for near-optimal parsing. */
249 struct lzx_mc_pos_data optimum[LZX_OPTIM_ARRAY_LENGTH + LZX_MAX_MATCH_LEN];
251 /* The cost model currently being used for near-optimal parsing. */
252 struct lzx_costs costs;
254 /* The current match offset LRU queue. */
255 struct lzx_lru_queue queue;
257 /* Frequency counters for the current block. */
258 struct lzx_freqs freqs;
260 /* The Huffman codes for the current and previous blocks. */
261 struct lzx_codes codes[2];
263 /* Which 'struct lzx_codes' is being used for the current block. The
264 * other was used for the previous block (if this isn't the first
266 unsigned int codes_index;
268 /* Dummy lengths that are always 0. */
269 struct lzx_lens zero_lens;
271 /* Matches/literals that were chosen for the current block. */
272 struct lzx_item chosen_items[LZX_DIV_BLOCK_SIZE];
274 /* Table mapping match offset => offset slot for small offsets */
275 #define LZX_NUM_FAST_OFFSETS 32768
276 u8 offset_slot_fast[LZX_NUM_FAST_OFFSETS];
280 * Structure to keep track of the current state of sending bits to the
281 * compressed output buffer.
283 * The LZX bitstream is encoded as a sequence of 16-bit coding units.
285 struct lzx_output_bitstream {
287 /* Bits that haven't yet been written to the output buffer. */
290 /* Number of bits currently held in @bitbuf. */
293 /* Pointer to the start of the output buffer. */
296 /* Pointer to the position in the output buffer at which the next coding
297 * unit should be written. */
300 /* Pointer past the end of the output buffer. */
305 * Initialize the output bitstream.
308 * The output bitstream structure to initialize.
310 * The buffer being written to.
312 * Size of @buffer, in bytes.
315 lzx_init_output(struct lzx_output_bitstream *os, void *buffer, u32 size)
320 os->next = os->start;
321 os->end = os->start + size / sizeof(le16);
325 * Write some bits to the output bitstream.
327 * The bits are given by the low-order @num_bits bits of @bits. Higher-order
328 * bits in @bits cannot be set. At most 17 bits can be written at once.
330 * @max_num_bits is a compile-time constant that specifies the maximum number of
331 * bits that can ever be written at the call site. Currently, it is used to
332 * optimize away the conditional code for writing a second 16-bit coding unit
333 * when writing fewer than 17 bits.
335 * If the output buffer space is exhausted, then the bits will be ignored, and
336 * lzx_flush_output() will return 0 when it gets called.
339 lzx_write_varbits(struct lzx_output_bitstream *os,
340 const u32 bits, const unsigned int num_bits,
341 const unsigned int max_num_bits)
343 /* This code is optimized for LZX, which never needs to write more than
344 * 17 bits at once. */
345 LZX_ASSERT(num_bits <= 17);
346 LZX_ASSERT(num_bits <= max_num_bits);
347 LZX_ASSERT(os->bitcount <= 15);
349 /* Add the bits to the bit buffer variable. @bitcount will be at most
350 * 15, so there will be just enough space for the maximum possible
351 * @num_bits of 17. */
352 os->bitcount += num_bits;
353 os->bitbuf = (os->bitbuf << num_bits) | bits;
355 /* Check whether any coding units need to be written. */
356 if (os->bitcount >= 16) {
360 /* Write a coding unit, unless it would overflow the buffer. */
361 if (os->next != os->end)
362 *os->next++ = cpu_to_le16(os->bitbuf >> os->bitcount);
364 /* If writing 17 bits, a second coding unit might need to be
365 * written. But because 'max_num_bits' is a compile-time
366 * constant, the compiler will optimize away this code at most
368 if (max_num_bits == 17 && os->bitcount == 16) {
369 if (os->next != os->end)
370 *os->next++ = cpu_to_le16(os->bitbuf);
376 /* Use when @num_bits is a compile-time constant. Otherwise use
377 * lzx_write_varbits(). */
379 lzx_write_bits(struct lzx_output_bitstream *os,
380 const u32 bits, const unsigned int num_bits)
382 lzx_write_varbits(os, bits, num_bits, num_bits);
386 * Flush the last coding unit to the output buffer if needed. Return the total
387 * number of bytes written to the output buffer, or 0 if an overflow occurred.
390 lzx_flush_output(struct lzx_output_bitstream *os)
392 if (os->next == os->end)
395 if (os->bitcount != 0)
396 *os->next++ = cpu_to_le16(os->bitbuf << (16 - os->bitcount));
398 return (const u8 *)os->next - (const u8 *)os->start;
401 /* Build the main, length, and aligned offset Huffman codes used in LZX.
403 * This takes as input the frequency tables for each code and produces as output
404 * a set of tables that map symbols to codewords and codeword lengths. */
406 lzx_make_huffman_codes(const struct lzx_freqs *freqs, struct lzx_codes *codes,
407 unsigned num_main_syms)
409 make_canonical_huffman_code(num_main_syms,
410 LZX_MAX_MAIN_CODEWORD_LEN,
413 codes->codewords.main);
415 make_canonical_huffman_code(LZX_LENCODE_NUM_SYMBOLS,
416 LZX_MAX_LEN_CODEWORD_LEN,
419 codes->codewords.len);
421 make_canonical_huffman_code(LZX_ALIGNEDCODE_NUM_SYMBOLS,
422 LZX_MAX_ALIGNED_CODEWORD_LEN,
425 codes->codewords.aligned);
429 lzx_compute_precode_items(const u8 lens[restrict],
430 const u8 prev_lens[restrict],
431 const unsigned num_lens,
432 u32 precode_freqs[restrict],
433 unsigned precode_items[restrict])
442 itemptr = precode_items;
445 /* Find the next run of codeword lengths. */
447 /* len = the length being repeated */
448 len = lens[run_start];
450 run_end = run_start + 1;
452 /* Fast case for a single length. */
453 if (likely(run_end == num_lens || len != lens[run_end])) {
454 delta = prev_lens[run_start] - len;
457 precode_freqs[delta]++;
463 /* Extend the run. */
466 } while (run_end != num_lens && len == lens[run_end]);
471 /* Symbol 18: RLE 20 to 51 zeroes at a time. */
472 while ((run_end - run_start) >= 20) {
473 extra_bits = min((run_end - run_start) - 20, 0x1f);
475 *itemptr++ = 18 | (extra_bits << 5);
476 run_start += 20 + extra_bits;
479 /* Symbol 17: RLE 4 to 19 zeroes at a time. */
480 if ((run_end - run_start) >= 4) {
481 extra_bits = min((run_end - run_start) - 4, 0xf);
483 *itemptr++ = 17 | (extra_bits << 5);
484 run_start += 4 + extra_bits;
488 /* A run of nonzero lengths. */
490 /* Symbol 19: RLE 4 to 5 of any length at a time. */
491 while ((run_end - run_start) >= 4) {
492 extra_bits = (run_end - run_start) > 4;
493 delta = prev_lens[run_start] - len;
497 precode_freqs[delta]++;
498 *itemptr++ = 19 | (extra_bits << 5) | (delta << 6);
499 run_start += 4 + extra_bits;
503 /* Output any remaining lengths without RLE. */
504 while (run_start != run_end) {
505 delta = prev_lens[run_start] - len;
508 precode_freqs[delta]++;
512 } while (run_start != num_lens);
514 return itemptr - precode_items;
518 * Output a Huffman code in the compressed form used in LZX.
520 * The Huffman code is represented in the output as a logical series of codeword
521 * lengths from which the Huffman code, which must be in canonical form, can be
524 * The codeword lengths are themselves compressed using a separate Huffman code,
525 * the "precode", which contains a symbol for each possible codeword length in
526 * the larger code as well as several special symbols to represent repeated
527 * codeword lengths (a form of run-length encoding). The precode is itself
528 * constructed in canonical form, and its codeword lengths are represented
529 * literally in 20 4-bit fields that immediately precede the compressed codeword
530 * lengths of the larger code.
532 * Furthermore, the codeword lengths of the larger code are actually represented
533 * as deltas from the codeword lengths of the corresponding code in the previous
537 * Bitstream to which to write the compressed Huffman code.
539 * The codeword lengths, indexed by symbol, in the Huffman code.
541 * The codeword lengths, indexed by symbol, in the corresponding Huffman
542 * code in the previous block, or all zeroes if this is the first block.
544 * The number of symbols in the Huffman code.
547 lzx_write_compressed_code(struct lzx_output_bitstream *os,
548 const u8 lens[restrict],
549 const u8 prev_lens[restrict],
552 u32 precode_freqs[LZX_PRECODE_NUM_SYMBOLS];
553 u8 precode_lens[LZX_PRECODE_NUM_SYMBOLS];
554 u32 precode_codewords[LZX_PRECODE_NUM_SYMBOLS];
555 unsigned precode_items[num_lens];
556 unsigned num_precode_items;
557 unsigned precode_item;
558 unsigned precode_sym;
561 for (i = 0; i < LZX_PRECODE_NUM_SYMBOLS; i++)
562 precode_freqs[i] = 0;
564 /* Compute the "items" (RLE / literal tokens and extra bits) with which
565 * the codeword lengths in the larger code will be output. */
566 num_precode_items = lzx_compute_precode_items(lens,
572 /* Build the precode. */
573 make_canonical_huffman_code(LZX_PRECODE_NUM_SYMBOLS,
574 LZX_MAX_PRE_CODEWORD_LEN,
575 precode_freqs, precode_lens,
578 /* Output the lengths of the codewords in the precode. */
579 for (i = 0; i < LZX_PRECODE_NUM_SYMBOLS; i++)
580 lzx_write_bits(os, precode_lens[i], LZX_PRECODE_ELEMENT_SIZE);
582 /* Output the encoded lengths of the codewords in the larger code. */
583 for (i = 0; i < num_precode_items; i++) {
584 precode_item = precode_items[i];
585 precode_sym = precode_item & 0x1F;
586 lzx_write_varbits(os, precode_codewords[precode_sym],
587 precode_lens[precode_sym],
588 LZX_MAX_PRE_CODEWORD_LEN);
589 if (precode_sym >= 17) {
590 if (precode_sym == 17) {
591 lzx_write_bits(os, precode_item >> 5, 4);
592 } else if (precode_sym == 18) {
593 lzx_write_bits(os, precode_item >> 5, 5);
595 lzx_write_bits(os, (precode_item >> 5) & 1, 1);
596 precode_sym = precode_item >> 6;
597 lzx_write_varbits(os, precode_codewords[precode_sym],
598 precode_lens[precode_sym],
599 LZX_MAX_PRE_CODEWORD_LEN);
605 /* Output a match or literal. */
607 lzx_write_item(struct lzx_output_bitstream *os, struct lzx_item item,
608 unsigned ones_if_aligned, const struct lzx_codes *codes)
610 u64 data = item.data;
611 unsigned main_symbol;
613 unsigned num_extra_bits;
616 main_symbol = data & 0x3FF;
618 lzx_write_varbits(os, codes->codewords.main[main_symbol],
619 codes->lens.main[main_symbol],
620 LZX_MAX_MAIN_CODEWORD_LEN);
622 if (main_symbol < LZX_NUM_CHARS) /* Literal? */
625 len_symbol = (data >> 10) & 0xFF;
627 if (len_symbol != LZX_LENCODE_NUM_SYMBOLS) {
628 lzx_write_varbits(os, codes->codewords.len[len_symbol],
629 codes->lens.len[len_symbol],
630 LZX_MAX_LEN_CODEWORD_LEN);
633 num_extra_bits = (data >> 18) & 0x1F;
634 if (num_extra_bits == 0) /* Small offset or repeat offset match? */
637 extra_bits = data >> 23;
639 /*if (block_type == LZX_BLOCKTYPE_ALIGNED && num_extra_bits >= 3) {*/
640 if ((num_extra_bits & ones_if_aligned) >= 3) {
642 /* Aligned offset blocks: The low 3 bits of the extra offset
643 * bits are Huffman-encoded using the aligned offset code. The
644 * remaining bits are output literally. */
646 lzx_write_varbits(os, extra_bits >> 3, num_extra_bits - 3, 14);
648 lzx_write_varbits(os, codes->codewords.aligned[extra_bits & 7],
649 codes->lens.aligned[extra_bits & 7],
650 LZX_MAX_ALIGNED_CODEWORD_LEN);
652 /* Verbatim blocks, or fewer than 3 extra bits: All extra
653 * offset bits are output literally. */
654 lzx_write_varbits(os, extra_bits, num_extra_bits, 17);
659 * Write all matches and literal bytes (which were precomputed) in an LZX
660 * compressed block to the output bitstream in the final compressed
664 * The output bitstream.
666 * The chosen type of the LZX compressed block (LZX_BLOCKTYPE_ALIGNED or
667 * LZX_BLOCKTYPE_VERBATIM).
669 * The array of matches/literals to output.
671 * Number of matches/literals to output (length of @items).
673 * The main, length, and aligned offset Huffman codes for the current
674 * LZX compressed block.
677 lzx_write_items(struct lzx_output_bitstream *os, int block_type,
678 const struct lzx_item items[], u32 num_items,
679 const struct lzx_codes *codes)
681 unsigned ones_if_aligned = 0U - (block_type == LZX_BLOCKTYPE_ALIGNED);
683 for (u32 i = 0; i < num_items; i++)
684 lzx_write_item(os, items[i], ones_if_aligned, codes);
687 /* Write an LZX aligned offset or verbatim block to the output bitstream. */
689 lzx_write_compressed_block(int block_type,
691 unsigned window_order,
692 unsigned num_main_syms,
693 struct lzx_item * chosen_items,
694 u32 num_chosen_items,
695 const struct lzx_codes * codes,
696 const struct lzx_lens * prev_lens,
697 struct lzx_output_bitstream * os)
699 LZX_ASSERT(block_type == LZX_BLOCKTYPE_ALIGNED ||
700 block_type == LZX_BLOCKTYPE_VERBATIM);
702 /* The first three bits indicate the type of block and are one of the
703 * LZX_BLOCKTYPE_* constants. */
704 lzx_write_bits(os, block_type, 3);
706 /* Output the block size.
708 * The original LZX format seemed to always encode the block size in 3
709 * bytes. However, the implementation in WIMGAPI, as used in WIM files,
710 * uses the first bit to indicate whether the block is the default size
711 * (32768) or a different size given explicitly by the next 16 bits.
713 * By default, this compressor uses a window size of 32768 and therefore
714 * follows the WIMGAPI behavior. However, this compressor also supports
715 * window sizes greater than 32768 bytes, which do not appear to be
716 * supported by WIMGAPI. In such cases, we retain the default size bit
717 * to mean a size of 32768 bytes but output non-default block size in 24
718 * bits rather than 16. The compatibility of this behavior is unknown
719 * because WIMs created with chunk size greater than 32768 can seemingly
720 * only be opened by wimlib anyway. */
721 if (block_size == LZX_DEFAULT_BLOCK_SIZE) {
722 lzx_write_bits(os, 1, 1);
724 lzx_write_bits(os, 0, 1);
726 if (window_order >= 16)
727 lzx_write_bits(os, block_size >> 16, 8);
729 lzx_write_bits(os, block_size & 0xFFFF, 16);
732 /* If it's an aligned offset block, output the aligned offset code. */
733 if (block_type == LZX_BLOCKTYPE_ALIGNED) {
734 for (int i = 0; i < LZX_ALIGNEDCODE_NUM_SYMBOLS; i++) {
735 lzx_write_bits(os, codes->lens.aligned[i],
736 LZX_ALIGNEDCODE_ELEMENT_SIZE);
740 /* Output the main code (two parts). */
741 lzx_write_compressed_code(os, codes->lens.main,
744 lzx_write_compressed_code(os, codes->lens.main + LZX_NUM_CHARS,
745 prev_lens->main + LZX_NUM_CHARS,
746 num_main_syms - LZX_NUM_CHARS);
748 /* Output the length code. */
749 lzx_write_compressed_code(os, codes->lens.len,
751 LZX_LENCODE_NUM_SYMBOLS);
753 /* Output the compressed matches and literals. */
754 lzx_write_items(os, block_type, chosen_items, num_chosen_items, codes);
757 /* Don't allow matches to span the end of an LZX block. */
758 static inline unsigned
759 maybe_truncate_matches(struct lz_match matches[], unsigned num_matches,
760 struct lzx_compressor *c)
762 if (c->match_window_end < c->cur_window_size && num_matches != 0) {
763 u32 limit = c->match_window_end - c->match_window_pos;
765 if (limit >= LZX_MIN_MATCH_LEN) {
767 unsigned i = num_matches - 1;
769 if (matches[i].len >= limit) {
770 matches[i].len = limit;
772 /* Truncation might produce multiple
773 * matches with length 'limit'. Keep at
786 lzx_get_matches_fillcache_singleblock(struct lzx_compressor *c,
787 const struct lz_match **matches_ret)
789 struct lz_match *cache_ptr;
790 struct lz_match *matches;
791 unsigned num_matches;
793 cache_ptr = c->cache_ptr;
794 matches = cache_ptr + 1;
795 if (likely(cache_ptr <= c->cache_limit)) {
796 num_matches = lz_mf_get_matches(c->mf, matches);
797 cache_ptr->len = num_matches;
798 c->cache_ptr = matches + num_matches;
802 c->match_window_pos++;
803 *matches_ret = matches;
808 lzx_get_matches_fillcache_multiblock(struct lzx_compressor *c,
809 const struct lz_match **matches_ret)
811 struct lz_match *cache_ptr;
812 struct lz_match *matches;
813 unsigned num_matches;
815 cache_ptr = c->cache_ptr;
816 matches = cache_ptr + 1;
817 if (likely(cache_ptr <= c->cache_limit)) {
818 num_matches = lz_mf_get_matches(c->mf, matches);
819 num_matches = maybe_truncate_matches(matches, num_matches, c);
820 cache_ptr->len = num_matches;
821 c->cache_ptr = matches + num_matches;
825 c->match_window_pos++;
826 *matches_ret = matches;
831 lzx_get_matches_usecache(struct lzx_compressor *c,
832 const struct lz_match **matches_ret)
834 struct lz_match *cache_ptr;
835 struct lz_match *matches;
836 unsigned num_matches;
838 cache_ptr = c->cache_ptr;
839 matches = cache_ptr + 1;
840 if (cache_ptr <= c->cache_limit) {
841 num_matches = cache_ptr->len;
842 c->cache_ptr = matches + num_matches;
846 c->match_window_pos++;
847 *matches_ret = matches;
852 lzx_get_matches_usecache_nocheck(struct lzx_compressor *c,
853 const struct lz_match **matches_ret)
855 struct lz_match *cache_ptr;
856 struct lz_match *matches;
857 unsigned num_matches;
859 cache_ptr = c->cache_ptr;
860 matches = cache_ptr + 1;
861 num_matches = cache_ptr->len;
862 c->cache_ptr = matches + num_matches;
863 c->match_window_pos++;
864 *matches_ret = matches;
869 lzx_get_matches_nocache_singleblock(struct lzx_compressor *c,
870 const struct lz_match **matches_ret)
872 struct lz_match *matches;
873 unsigned num_matches;
875 matches = c->cache_ptr;
876 num_matches = lz_mf_get_matches(c->mf, matches);
877 c->match_window_pos++;
878 *matches_ret = matches;
883 lzx_get_matches_nocache_multiblock(struct lzx_compressor *c,
884 const struct lz_match **matches_ret)
886 struct lz_match *matches;
887 unsigned num_matches;
889 matches = c->cache_ptr;
890 num_matches = lz_mf_get_matches(c->mf, matches);
891 num_matches = maybe_truncate_matches(matches, num_matches, c);
892 c->match_window_pos++;
893 *matches_ret = matches;
898 * Find matches at the next position in the window.
900 * This uses a wrapper function around the underlying match-finder.
902 * Returns the number of matches found and sets *matches_ret to point to the
903 * matches array. The matches will be sorted by strictly increasing length and
906 static inline unsigned
907 lzx_get_matches(struct lzx_compressor *c,
908 const struct lz_match **matches_ret)
910 return (*c->get_matches_func)(c, matches_ret);
914 lzx_skip_bytes_fillcache(struct lzx_compressor *c, unsigned n)
916 struct lz_match *cache_ptr;
918 cache_ptr = c->cache_ptr;
919 c->match_window_pos += n;
920 lz_mf_skip_positions(c->mf, n);
921 if (cache_ptr <= c->cache_limit) {
925 } while (--n && cache_ptr <= c->cache_limit);
927 c->cache_ptr = cache_ptr;
931 lzx_skip_bytes_usecache(struct lzx_compressor *c, unsigned n)
933 struct lz_match *cache_ptr;
935 cache_ptr = c->cache_ptr;
936 c->match_window_pos += n;
937 if (cache_ptr <= c->cache_limit) {
939 cache_ptr += 1 + cache_ptr->len;
940 } while (--n && cache_ptr <= c->cache_limit);
942 c->cache_ptr = cache_ptr;
946 lzx_skip_bytes_usecache_nocheck(struct lzx_compressor *c, unsigned n)
948 struct lz_match *cache_ptr;
950 cache_ptr = c->cache_ptr;
951 c->match_window_pos += n;
953 cache_ptr += 1 + cache_ptr->len;
955 c->cache_ptr = cache_ptr;
959 lzx_skip_bytes_nocache(struct lzx_compressor *c, unsigned n)
961 c->match_window_pos += n;
962 lz_mf_skip_positions(c->mf, n);
966 * Skip the specified number of positions in the window (don't search for
969 * This uses a wrapper function around the underlying match-finder.
972 lzx_skip_bytes(struct lzx_compressor *c, unsigned n)
974 return (*c->skip_bytes_func)(c, n);
977 /* Tally, and optionally record, the specified literal byte. */
979 lzx_declare_literal(struct lzx_compressor *c, unsigned literal,
980 struct lzx_item **next_chosen_item)
982 unsigned main_symbol = literal;
984 c->freqs.main[main_symbol]++;
986 if (next_chosen_item) {
987 *(*next_chosen_item)++ = (struct lzx_item) {
993 /* Tally, and optionally record, the specified repeat offset match. */
995 lzx_declare_repeat_offset_match(struct lzx_compressor *c,
996 unsigned len, unsigned rep_index,
997 struct lzx_item **next_chosen_item)
1000 unsigned main_symbol;
1001 unsigned len_symbol;
1003 if (len - LZX_MIN_MATCH_LEN < LZX_NUM_PRIMARY_LENS) {
1004 len_header = len - LZX_MIN_MATCH_LEN;
1005 len_symbol = LZX_LENCODE_NUM_SYMBOLS;
1007 len_header = LZX_NUM_PRIMARY_LENS;
1008 len_symbol = len - LZX_MIN_MATCH_LEN - LZX_NUM_PRIMARY_LENS;
1009 c->freqs.len[len_symbol]++;
1012 main_symbol = LZX_NUM_CHARS + ((rep_index << 3) | len_header);
1014 c->freqs.main[main_symbol]++;
1016 if (next_chosen_item) {
1017 *(*next_chosen_item)++ = (struct lzx_item) {
1018 .data = (u64)main_symbol | ((u64)len_symbol << 10),
1023 /* Tally, and optionally record, the specified explicit offset match. */
1025 lzx_declare_explicit_offset_match(struct lzx_compressor *c, unsigned len, u32 offset,
1026 struct lzx_item **next_chosen_item)
1028 unsigned len_header;
1029 unsigned main_symbol;
1030 unsigned len_symbol;
1031 unsigned offset_slot;
1032 unsigned num_extra_bits;
1035 if (len - LZX_MIN_MATCH_LEN < LZX_NUM_PRIMARY_LENS) {
1036 len_header = len - LZX_MIN_MATCH_LEN;
1037 len_symbol = LZX_LENCODE_NUM_SYMBOLS;
1039 len_header = LZX_NUM_PRIMARY_LENS;
1040 len_symbol = len - LZX_MIN_MATCH_LEN - LZX_NUM_PRIMARY_LENS;
1041 c->freqs.len[len_symbol]++;
1044 offset_slot = lzx_get_offset_slot_raw(offset + LZX_OFFSET_OFFSET);
1046 main_symbol = LZX_NUM_CHARS + ((offset_slot << 3) | len_header);
1048 c->freqs.main[main_symbol]++;
1050 if (offset_slot >= 8)
1051 c->freqs.aligned[(offset + LZX_OFFSET_OFFSET) & 7]++;
1053 if (next_chosen_item) {
1055 num_extra_bits = lzx_extra_offset_bits[offset_slot];
1057 extra_bits = (offset + LZX_OFFSET_OFFSET) -
1058 lzx_offset_slot_base[offset_slot];
1060 *(*next_chosen_item)++ = (struct lzx_item) {
1061 .data = (u64)main_symbol |
1062 ((u64)len_symbol << 10) |
1063 ((u64)num_extra_bits << 18) |
1064 ((u64)extra_bits << 23),
1069 /* Tally, and optionally record, the specified match or literal. */
1071 lzx_declare_item(struct lzx_compressor *c, u32 mc_item_data,
1072 struct lzx_item **next_chosen_item)
1074 u32 len = mc_item_data & MC_LEN_MASK;
1075 u32 offset_data = mc_item_data >> MC_OFFSET_SHIFT;
1078 lzx_declare_literal(c, offset_data, next_chosen_item);
1079 else if (offset_data < LZX_NUM_RECENT_OFFSETS)
1080 lzx_declare_repeat_offset_match(c, len, offset_data,
1083 lzx_declare_explicit_offset_match(c, len,
1084 offset_data - LZX_OFFSET_OFFSET,
1089 lzx_record_item_list(struct lzx_compressor *c,
1090 struct lzx_mc_pos_data *cur_optimum_ptr,
1091 struct lzx_item **next_chosen_item)
1093 struct lzx_mc_pos_data *end_optimum_ptr;
1097 /* The list is currently in reverse order (last item to first item).
1099 end_optimum_ptr = cur_optimum_ptr;
1100 saved_item = cur_optimum_ptr->mc_item_data;
1103 cur_optimum_ptr -= item & MC_LEN_MASK;
1104 saved_item = cur_optimum_ptr->mc_item_data;
1105 cur_optimum_ptr->mc_item_data = item;
1106 } while (cur_optimum_ptr != c->optimum);
1108 /* Walk the list of items from beginning to end, tallying and recording
1111 lzx_declare_item(c, cur_optimum_ptr->mc_item_data, next_chosen_item);
1112 cur_optimum_ptr += (cur_optimum_ptr->mc_item_data) & MC_LEN_MASK;
1113 } while (cur_optimum_ptr != end_optimum_ptr);
1117 lzx_tally_item_list(struct lzx_compressor *c, struct lzx_mc_pos_data *cur_optimum_ptr)
1119 /* Since we're just tallying the items, we don't need to reverse the
1120 * list. Processing the items in reverse order is fine. */
1122 lzx_declare_item(c, cur_optimum_ptr->mc_item_data, NULL);
1123 cur_optimum_ptr -= (cur_optimum_ptr->mc_item_data & MC_LEN_MASK);
1124 } while (cur_optimum_ptr != c->optimum);
1127 /* Tally, and optionally (if next_chosen_item != NULL) record, in order, all
1128 * items in the current list of items found by the match-chooser. */
1130 lzx_declare_item_list(struct lzx_compressor *c, struct lzx_mc_pos_data *cur_optimum_ptr,
1131 struct lzx_item **next_chosen_item)
1133 if (next_chosen_item)
1134 lzx_record_item_list(c, cur_optimum_ptr, next_chosen_item);
1136 lzx_tally_item_list(c, cur_optimum_ptr);
1139 /* Set the cost model @c->costs from the Huffman codeword lengths specified in
1142 * The cost model and codeword lengths are almost the same thing, but the
1143 * Huffman codewords with length 0 correspond to symbols with zero frequency
1144 * that still need to be assigned actual costs. The specific values assigned
1145 * are arbitrary, but they should be fairly high (near the maximum codeword
1146 * length) to take into account the fact that uses of these symbols are expected
1149 lzx_set_costs(struct lzx_compressor *c, const struct lzx_lens * lens)
1154 for (i = 0; i < c->num_main_syms; i++)
1155 c->costs.main[i] = lens->main[i] ? lens->main[i] : 15;
1158 for (i = 0; i < LZX_LENCODE_NUM_SYMBOLS; i++)
1159 c->costs.len[i] = lens->len[i] ? lens->len[i] : 15;
1161 /* Aligned offset code */
1162 for (i = 0; i < LZX_ALIGNEDCODE_NUM_SYMBOLS; i++)
1163 c->costs.aligned[i] = lens->aligned[i] ? lens->aligned[i] : 7;
1166 /* Set default LZX Huffman symbol costs to bootstrap the iterative optimization
1169 lzx_set_default_costs(struct lzx_costs * costs, unsigned num_main_syms)
1173 /* Main code (part 1): Literal symbols */
1174 for (i = 0; i < LZX_NUM_CHARS; i++)
1177 /* Main code (part 2): Match header symbols */
1178 for (; i < num_main_syms; i++)
1179 costs->main[i] = 10;
1182 for (i = 0; i < LZX_LENCODE_NUM_SYMBOLS; i++)
1185 /* Aligned offset code */
1186 for (i = 0; i < LZX_ALIGNEDCODE_NUM_SYMBOLS; i++)
1187 costs->aligned[i] = 3;
1190 /* Return the cost, in bits, to output a literal byte using the specified cost
1193 lzx_literal_cost(unsigned literal, const struct lzx_costs * costs)
1195 return costs->main[literal];
1198 /* Return the cost, in bits, to output a match of the specified length and
1199 * offset slot using the specified cost model. Does not take into account
1200 * extra offset bits. */
1202 lzx_match_cost_raw(unsigned len, unsigned offset_slot,
1203 const struct lzx_costs *costs)
1206 unsigned len_header;
1207 unsigned main_symbol;
1209 if (len - LZX_MIN_MATCH_LEN < LZX_NUM_PRIMARY_LENS) {
1210 len_header = len - LZX_MIN_MATCH_LEN ;
1213 len_header = LZX_NUM_PRIMARY_LENS;
1215 /* Account for length symbol. */
1216 cost = costs->len[len - LZX_MIN_MATCH_LEN - LZX_NUM_PRIMARY_LENS];
1219 /* Account for main symbol. */
1220 main_symbol = LZX_NUM_CHARS + ((offset_slot << 3) | len_header);
1221 cost += costs->main[main_symbol];
1226 /* Equivalent to lzx_match_cost_raw(), but assumes the length is small enough
1227 * that it doesn't require a length symbol. */
1229 lzx_match_cost_raw_smalllen(unsigned len, unsigned offset_slot,
1230 const struct lzx_costs *costs)
1232 LZX_ASSERT(len < LZX_MIN_MATCH_LEN + LZX_NUM_PRIMARY_LENS);
1233 return costs->main[LZX_NUM_CHARS +
1234 ((offset_slot << 3) | (len - LZX_MIN_MATCH_LEN))];
1238 * Consider coding the match at repeat offset index @rep_idx. Consider each
1239 * length from the minimum (2) to the full match length (@rep_len).
1242 lzx_consider_repeat_offset_match(struct lzx_compressor *c,
1243 struct lzx_mc_pos_data *cur_optimum_ptr,
1244 unsigned rep_len, unsigned rep_idx)
1246 u32 base_cost = cur_optimum_ptr->cost;
1250 #if 1 /* Optimized version */
1252 if (rep_len < LZX_MIN_MATCH_LEN + LZX_NUM_PRIMARY_LENS) {
1253 /* All lengths being considered are small. */
1257 lzx_match_cost_raw_smalllen(len, rep_idx, &c->costs);
1258 if (cost < (cur_optimum_ptr + len)->cost) {
1259 (cur_optimum_ptr + len)->mc_item_data =
1260 (rep_idx << MC_OFFSET_SHIFT) | len;
1261 (cur_optimum_ptr + len)->cost = cost;
1263 } while (++len <= rep_len);
1265 /* Some lengths being considered are small, and some are big.
1266 * Start with the optimized loop for small lengths, then switch
1267 * to the optimized loop for big lengths. */
1271 lzx_match_cost_raw_smalllen(len, rep_idx, &c->costs);
1272 if (cost < (cur_optimum_ptr + len)->cost) {
1273 (cur_optimum_ptr + len)->mc_item_data =
1274 (rep_idx << MC_OFFSET_SHIFT) | len;
1275 (cur_optimum_ptr + len)->cost = cost;
1277 } while (++len < LZX_MIN_MATCH_LEN + LZX_NUM_PRIMARY_LENS);
1279 /* The main symbol is now fixed. */
1280 base_cost += c->costs.main[LZX_NUM_CHARS +
1281 ((rep_idx << 3) | LZX_NUM_PRIMARY_LENS)];
1284 c->costs.len[len - LZX_MIN_MATCH_LEN -
1285 LZX_NUM_PRIMARY_LENS];
1286 if (cost < (cur_optimum_ptr + len)->cost) {
1287 (cur_optimum_ptr + len)->mc_item_data =
1288 (rep_idx << MC_OFFSET_SHIFT) | len;
1289 (cur_optimum_ptr + len)->cost = cost;
1291 } while (++len <= rep_len);
1294 #else /* Unoptimized version */
1299 lzx_match_cost_raw(len, rep_idx, &c->costs);
1300 if (cost < (cur_optimum_ptr + len)->cost) {
1301 (cur_optimum_ptr + len)->mc_item_data =
1302 (rep_idx << MC_OFFSET_SHIFT) | len;
1303 (cur_optimum_ptr + len)->cost = cost;
1305 } while (++len <= rep_len);
1310 * Consider coding each match in @matches as an explicit offset match.
1312 * @matches must be sorted by strictly increasing length and strictly
1313 * increasing offset. This is guaranteed by the match-finder.
1315 * We consider each length from the minimum (2) to the longest
1316 * (matches[num_matches - 1].len). For each length, we consider only
1317 * the smallest offset for which that length is available. Although
1318 * this is not guaranteed to be optimal due to the possibility of a
1319 * larger offset costing less than a smaller offset to code, this is a
1320 * very useful heuristic.
1323 lzx_consider_explicit_offset_matches(struct lzx_compressor *c,
1324 struct lzx_mc_pos_data *cur_optimum_ptr,
1325 const struct lz_match matches[],
1326 unsigned num_matches)
1328 LZX_ASSERT(num_matches > 0);
1332 unsigned offset_slot;
1338 #if 1 /* Optimized version */
1340 if (matches[num_matches - 1].offset < LZX_NUM_FAST_OFFSETS) {
1343 * Offset is small; the offset slot can be looked up directly in
1344 * c->offset_slot_fast.
1346 * Additional optimizations:
1348 * - Since the offset is small, it falls in the exponential part
1349 * of the offset slot bases and the number of extra offset
1350 * bits can be calculated directly as (offset_slot >> 1) - 1.
1352 * - Just consider the number of extra offset bits; don't
1353 * account for the aligned offset code. Usually this has
1354 * almost no effect on the compression ratio.
1356 * - Start out in a loop optimized for small lengths. When the
1357 * length becomes high enough that a length symbol will be
1358 * needed, jump into a loop optimized for big lengths.
1361 LZX_ASSERT(offset_slot <= 37); /* for extra bits formula */
1366 offset_slot = c->offset_slot_fast[matches[i].offset];
1367 position_cost = cur_optimum_ptr->cost +
1368 ((offset_slot >> 1) - 1);
1369 offset_data = matches[i].offset + LZX_OFFSET_OFFSET;
1371 if (len >= LZX_MIN_MATCH_LEN + LZX_NUM_PRIMARY_LENS)
1373 cost = position_cost +
1374 lzx_match_cost_raw_smalllen(len, offset_slot,
1376 if (cost < (cur_optimum_ptr + len)->cost) {
1377 (cur_optimum_ptr + len)->cost = cost;
1378 (cur_optimum_ptr + len)->mc_item_data =
1379 (offset_data << MC_OFFSET_SHIFT) | len;
1381 } while (++len <= matches[i].len);
1382 } while (++i != num_matches);
1387 offset_slot = c->offset_slot_fast[matches[i].offset];
1389 position_cost = cur_optimum_ptr->cost +
1390 ((offset_slot >> 1) - 1) +
1391 c->costs.main[LZX_NUM_CHARS +
1392 ((offset_slot << 3) |
1393 LZX_NUM_PRIMARY_LENS)];
1394 offset_data = matches[i].offset + LZX_OFFSET_OFFSET;
1396 cost = position_cost +
1397 c->costs.len[len - LZX_MIN_MATCH_LEN -
1398 LZX_NUM_PRIMARY_LENS];
1399 if (cost < (cur_optimum_ptr + len)->cost) {
1400 (cur_optimum_ptr + len)->cost = cost;
1401 (cur_optimum_ptr + len)->mc_item_data =
1402 (offset_data << MC_OFFSET_SHIFT) | len;
1404 } while (++len <= matches[i].len);
1405 } while (++i != num_matches);
1410 offset_data = matches[i].offset + LZX_OFFSET_OFFSET;
1411 offset_slot = lzx_get_offset_slot_raw(offset_data);
1412 position_cost = cur_optimum_ptr->cost +
1413 lzx_extra_offset_bits[offset_slot];
1415 cost = position_cost +
1416 lzx_match_cost_raw(len, offset_slot, &c->costs);
1417 if (cost < (cur_optimum_ptr + len)->cost) {
1418 (cur_optimum_ptr + len)->cost = cost;
1419 (cur_optimum_ptr + len)->mc_item_data =
1420 (offset_data << MC_OFFSET_SHIFT) | len;
1422 } while (++len <= matches[i].len);
1423 } while (++i != num_matches);
1426 #else /* Unoptimized version */
1428 unsigned num_extra_bits;
1433 offset_data = matches[i].offset + LZX_OFFSET_OFFSET;
1434 position_cost = cur_optimum_ptr->cost;
1435 offset_slot = lzx_get_offset_slot_raw(offset_data);
1436 num_extra_bits = lzx_extra_offset_bits[offset_slot];
1437 if (num_extra_bits >= 3) {
1438 position_cost += num_extra_bits - 3;
1439 position_cost += c->costs.aligned[offset_data & 7];
1441 position_cost += num_extra_bits;
1444 cost = position_cost +
1445 lzx_match_cost_raw(len, offset_slot, &c->costs);
1446 if (cost < (cur_optimum_ptr + len)->cost) {
1447 (cur_optimum_ptr + len)->cost = cost;
1448 (cur_optimum_ptr + len)->mc_item_data =
1449 (offset_data << MC_OFFSET_SHIFT) | len;
1451 } while (++len <= matches[i].len);
1452 } while (++i != num_matches);
1457 * Search for repeat offset matches with the current position.
1459 static inline unsigned
1460 lzx_repsearch(const u8 * const strptr, const u32 bytes_remaining,
1461 const struct lzx_lru_queue *queue, unsigned *rep_max_idx_ret)
1463 BUILD_BUG_ON(LZX_NUM_RECENT_OFFSETS != 3);
1464 return lz_repsearch3(strptr, min(bytes_remaining, LZX_MAX_MATCH_LEN),
1465 queue->R, rep_max_idx_ret);
1469 * The main near-optimal parsing routine.
1471 * Briefly, the algorithm does an approximate minimum-cost path search to find a
1472 * "near-optimal" sequence of matches and literals to output, based on the
1473 * current cost model. The algorithm steps forward, position by position (byte
1474 * by byte), and updates the minimum cost path to reach each later position that
1475 * can be reached using a match or literal from the current position. This is
1476 * essentially Dijkstra's algorithm in disguise: the graph nodes are positions,
1477 * the graph edges are possible matches/literals to code, and the cost of each
1478 * edge is the estimated number of bits that will be required to output the
1479 * corresponding match or literal. But one difference is that we actually
1480 * compute the lowest-cost path in pieces, where each piece is terminated when
1481 * there are no choices to be made.
1483 * This function will run this algorithm on the portion of the window from
1484 * &c->cur_window[c->match_window_pos] to &c->cur_window[c->match_window_end].
1486 * On entry, c->queue must be the current state of the match offset LRU queue,
1487 * and c->costs must be the current cost model to use for Huffman symbols.
1489 * On exit, c->queue will be the state that the LRU queue would be in if the
1490 * chosen items were to be coded.
1492 * If next_chosen_item != NULL, then all items chosen will be recorded (saved in
1493 * the chosen_items array). Otherwise, all items chosen will only be tallied
1494 * (symbol frequencies tallied in c->freqs).
1497 lzx_optim_pass(struct lzx_compressor *c, struct lzx_item **next_chosen_item)
1499 const u8 *block_end;
1500 struct lzx_lru_queue *begin_queue;
1501 const u8 *window_ptr;
1502 struct lzx_mc_pos_data *cur_optimum_ptr;
1503 struct lzx_mc_pos_data *end_optimum_ptr;
1504 const struct lz_match *matches;
1505 unsigned num_matches;
1506 unsigned longest_len;
1507 unsigned rep_max_len;
1508 unsigned rep_max_idx;
1514 block_end = &c->cur_window[c->match_window_end];
1515 begin_queue = &c->queue;
1517 /* Start building a new list of items, which will correspond to the next
1518 * piece of the overall minimum-cost path.
1520 * *begin_queue is the current state of the match offset LRU queue. */
1522 window_ptr = &c->cur_window[c->match_window_pos];
1524 if (window_ptr == block_end) {
1525 c->queue = *begin_queue;
1529 cur_optimum_ptr = c->optimum;
1530 cur_optimum_ptr->cost = 0;
1531 cur_optimum_ptr->queue = *begin_queue;
1533 end_optimum_ptr = cur_optimum_ptr;
1535 /* The following loop runs once for each per byte in the window, except
1536 * in a couple shortcut cases. */
1539 /* Find explicit offset matches with the current position. */
1540 num_matches = lzx_get_matches(c, &matches);
1544 * Find the longest repeat offset match with the current
1549 * - Only search for repeat offset matches if the
1550 * match-finder already found at least one match.
1552 * - Only consider the longest repeat offset match. It
1553 * seems to be rare for the optimal parse to include a
1554 * repeat offset match that doesn't have the longest
1555 * length (allowing for the possibility that not all
1556 * of that length is actually used).
1558 rep_max_len = lzx_repsearch(window_ptr,
1559 block_end - window_ptr,
1560 &cur_optimum_ptr->queue,
1564 /* If there's a very long repeat offset match,
1565 * choose it immediately. */
1566 if (rep_max_len >= c->params.nice_match_length) {
1568 swap(cur_optimum_ptr->queue.R[0],
1569 cur_optimum_ptr->queue.R[rep_max_idx]);
1570 begin_queue = &cur_optimum_ptr->queue;
1572 cur_optimum_ptr += rep_max_len;
1573 cur_optimum_ptr->mc_item_data =
1574 (rep_max_idx << MC_OFFSET_SHIFT) |
1577 lzx_skip_bytes(c, rep_max_len - 1);
1581 /* If reaching any positions for the first time,
1582 * initialize their costs to "infinity". */
1583 while (end_optimum_ptr < cur_optimum_ptr + rep_max_len)
1584 (++end_optimum_ptr)->cost = MC_INFINITE_COST;
1586 /* Consider coding a repeat offset match. */
1587 lzx_consider_repeat_offset_match(c,
1593 longest_len = matches[num_matches - 1].len;
1595 /* If there's a very long explicit offset match, choose
1596 * it immediately. */
1597 if (longest_len >= c->params.nice_match_length) {
1599 cur_optimum_ptr->queue.R[2] =
1600 cur_optimum_ptr->queue.R[1];
1601 cur_optimum_ptr->queue.R[1] =
1602 cur_optimum_ptr->queue.R[0];
1603 cur_optimum_ptr->queue.R[0] =
1604 matches[num_matches - 1].offset;
1605 begin_queue = &cur_optimum_ptr->queue;
1607 offset_data = matches[num_matches - 1].offset +
1609 cur_optimum_ptr += longest_len;
1610 cur_optimum_ptr->mc_item_data =
1611 (offset_data << MC_OFFSET_SHIFT) |
1614 lzx_skip_bytes(c, longest_len - 1);
1618 /* If reaching any positions for the first time,
1619 * initialize their costs to "infinity". */
1620 while (end_optimum_ptr < cur_optimum_ptr + longest_len)
1621 (++end_optimum_ptr)->cost = MC_INFINITE_COST;
1623 /* Consider coding an explicit offset match. */
1624 lzx_consider_explicit_offset_matches(c, cur_optimum_ptr,
1625 matches, num_matches);
1627 /* No matches found. The only choice at this position
1628 * is to code a literal. */
1630 if (end_optimum_ptr == cur_optimum_ptr) {
1632 /* Optimization for single literals. */
1633 if (likely(cur_optimum_ptr == c->optimum)) {
1634 lzx_declare_literal(c, *window_ptr++,
1636 if (window_ptr == block_end) {
1637 c->queue = cur_optimum_ptr->queue;
1643 (++end_optimum_ptr)->cost = MC_INFINITE_COST;
1647 /* Consider coding a literal.
1649 * To avoid an extra unpredictable brench, actually checking the
1650 * preferability of coding a literal is integrated into the
1651 * queue update code below. */
1652 literal = *window_ptr++;
1653 cost = cur_optimum_ptr->cost + lzx_literal_cost(literal, &c->costs);
1655 /* Advance to the next position. */
1658 /* The lowest-cost path to the current position is now known.
1659 * Finalize the recent offsets queue that results from taking
1660 * this lowest-cost path. */
1662 if (cost < cur_optimum_ptr->cost) {
1663 /* Literal: queue remains unchanged. */
1664 cur_optimum_ptr->cost = cost;
1665 cur_optimum_ptr->mc_item_data = (literal << MC_OFFSET_SHIFT) | 1;
1666 cur_optimum_ptr->queue = (cur_optimum_ptr - 1)->queue;
1668 /* Match: queue update is needed. */
1669 len = cur_optimum_ptr->mc_item_data & MC_LEN_MASK;
1670 offset_data = cur_optimum_ptr->mc_item_data >> MC_OFFSET_SHIFT;
1671 if (offset_data >= LZX_NUM_RECENT_OFFSETS) {
1672 /* Explicit offset match: offset is inserted at front */
1673 cur_optimum_ptr->queue.R[0] = offset_data - LZX_OFFSET_OFFSET;
1674 cur_optimum_ptr->queue.R[1] = (cur_optimum_ptr - len)->queue.R[0];
1675 cur_optimum_ptr->queue.R[2] = (cur_optimum_ptr - len)->queue.R[1];
1677 /* Repeat offset match: offset is swapped to front */
1678 cur_optimum_ptr->queue = (cur_optimum_ptr - len)->queue;
1679 swap(cur_optimum_ptr->queue.R[0],
1680 cur_optimum_ptr->queue.R[offset_data]);
1685 * This loop will terminate when either of the following
1686 * conditions is true:
1688 * (1) cur_optimum_ptr == end_optimum_ptr
1690 * There are no paths that extend beyond the current
1691 * position. In this case, any path to a later position
1692 * must pass through the current position, so we can go
1693 * ahead and choose the list of items that led to this
1696 * (2) cur_optimum_ptr == &c->optimum[LZX_OPTIM_ARRAY_LENGTH]
1698 * This bounds the number of times the algorithm can step
1699 * forward before it is guaranteed to start choosing items.
1700 * This limits the memory usage. But
1701 * LZX_OPTIM_ARRAY_LENGTH is high enough that on most
1702 * inputs this limit is never reached.
1704 * Note: no check for end-of-block is needed because
1705 * end-of-block will trigger condition (1).
1707 if (cur_optimum_ptr == end_optimum_ptr ||
1708 cur_optimum_ptr == &c->optimum[LZX_OPTIM_ARRAY_LENGTH])
1710 begin_queue = &cur_optimum_ptr->queue;
1715 /* Choose the current list of items that constitute the minimum-cost
1716 * path to the current position. */
1717 lzx_declare_item_list(c, cur_optimum_ptr, next_chosen_item);
1721 /* Fast heuristic scoring for lazy parsing: how "good" is this match? */
1722 static inline unsigned
1723 lzx_explicit_offset_match_score(unsigned len, u32 adjusted_offset)
1725 unsigned score = len;
1727 if (adjusted_offset < 2048)
1730 if (adjusted_offset < 1024)
1736 static inline unsigned
1737 lzx_repeat_offset_match_score(unsigned len, unsigned slot)
1744 lzx_choose_lazy_items_for_block(struct lzx_compressor *c,
1745 u32 block_start_pos, u32 block_size)
1747 const u8 *window_ptr;
1748 const u8 *block_end;
1750 struct lz_match *matches;
1751 unsigned num_matches;
1753 u32 cur_offset_data;
1755 unsigned rep_max_len;
1756 unsigned rep_max_idx;
1759 unsigned prev_score;
1760 u32 prev_offset_data;
1762 struct lzx_item *next_chosen_item;
1764 window_ptr = &c->cur_window[block_start_pos];
1765 block_end = window_ptr + block_size;
1766 matches = c->cached_matches;
1768 next_chosen_item = c->chosen_items;
1771 prev_offset_data = 0;
1774 while (window_ptr != block_end) {
1776 /* Find explicit offset matches with the current position. */
1777 num_matches = lz_mf_get_matches(mf, matches);
1780 if (num_matches == 0 ||
1781 (matches[num_matches - 1].len == 3 &&
1782 matches[num_matches - 1].offset >= 8192 - LZX_OFFSET_OFFSET &&
1783 matches[num_matches - 1].offset != c->queue.R[0] &&
1784 matches[num_matches - 1].offset != c->queue.R[1] &&
1785 matches[num_matches - 1].offset != c->queue.R[2]))
1787 /* No match found, or the only match found was a distant
1788 * length 3 match. Output the previous match if there
1789 * is one; otherwise output a literal. */
1792 skip_len = prev_len - 2;
1793 goto output_prev_match;
1795 lzx_declare_literal(c, *(window_ptr - 1),
1801 /* Find the longest repeat offset match with the current
1803 if (likely(block_end - (window_ptr - 1) >= 2)) {
1804 rep_max_len = lzx_repsearch((window_ptr - 1),
1805 block_end - (window_ptr - 1),
1806 &c->queue, &rep_max_idx);
1811 cur_len = matches[num_matches - 1].len;
1812 cur_offset_data = matches[num_matches - 1].offset + LZX_OFFSET_OFFSET;
1813 cur_score = lzx_explicit_offset_match_score(cur_len, cur_offset_data);
1815 /* Select the better of the explicit and repeat offset matches. */
1816 if (rep_max_len >= 3 &&
1817 (rep_score = lzx_repeat_offset_match_score(rep_max_len,
1818 rep_max_idx)) >= cur_score)
1820 cur_len = rep_max_len;
1821 cur_offset_data = rep_max_idx;
1822 cur_score = rep_score;
1825 if (unlikely(cur_len > block_end - (window_ptr - 1))) {
1826 /* Nearing end of block. */
1827 cur_len = block_end - (window_ptr - 1);
1829 lzx_declare_literal(c, *(window_ptr - 1), &next_chosen_item);
1835 if (prev_len == 0 || cur_score > prev_score) {
1836 /* No previous match, or the current match is better
1837 * than the previous match.
1839 * If there's a previous match, then output a literal in
1842 * In both cases, if the current match is very long,
1843 * then output it immediately. Otherwise, attempt a
1844 * lazy match by waiting to see if there's a better
1845 * match at the next position. */
1848 lzx_declare_literal(c, *(window_ptr - 2), &next_chosen_item);
1851 prev_offset_data = cur_offset_data;
1852 prev_score = cur_score;
1854 if (prev_len >= c->params.nice_match_length) {
1855 skip_len = prev_len - 1;
1856 goto output_prev_match;
1861 /* Current match is not better than the previous match, so
1862 * output the previous match. */
1864 skip_len = prev_len - 2;
1867 if (prev_offset_data < LZX_NUM_RECENT_OFFSETS) {
1868 lzx_declare_repeat_offset_match(c, prev_len,
1871 swap(c->queue.R[0], c->queue.R[prev_offset_data]);
1873 lzx_declare_explicit_offset_match(c, prev_len,
1874 prev_offset_data - LZX_OFFSET_OFFSET,
1876 c->queue.R[2] = c->queue.R[1];
1877 c->queue.R[1] = c->queue.R[0];
1878 c->queue.R[0] = prev_offset_data - LZX_OFFSET_OFFSET;
1880 lz_mf_skip_positions(mf, skip_len);
1881 window_ptr += skip_len;
1885 return next_chosen_item - c->chosen_items;
1888 /* Given the frequencies of symbols in an LZX-compressed block and the
1889 * corresponding Huffman codes, return LZX_BLOCKTYPE_ALIGNED or
1890 * LZX_BLOCKTYPE_VERBATIM if an aligned offset or verbatim block, respectively,
1891 * will take fewer bits to output. */
1893 lzx_choose_verbatim_or_aligned(const struct lzx_freqs * freqs,
1894 const struct lzx_codes * codes)
1896 unsigned aligned_cost = 0;
1897 unsigned verbatim_cost = 0;
1899 /* A verbatim block require 3 bits in each place that an aligned symbol
1901 for (unsigned i = 0; i < LZX_ALIGNEDCODE_NUM_SYMBOLS; i++) {
1902 verbatim_cost += 3 * freqs->aligned[i];
1903 aligned_cost += codes->lens.aligned[i] * freqs->aligned[i];
1906 /* Account for output of the aligned offset code. */
1907 aligned_cost += LZX_ALIGNEDCODE_ELEMENT_SIZE * LZX_ALIGNEDCODE_NUM_SYMBOLS;
1909 if (aligned_cost < verbatim_cost)
1910 return LZX_BLOCKTYPE_ALIGNED;
1912 return LZX_BLOCKTYPE_VERBATIM;
1915 /* Near-optimal parsing */
1917 lzx_choose_near_optimal_items_for_block(struct lzx_compressor *c,
1918 u32 block_start_pos, u32 block_size)
1920 u32 num_passes_remaining = c->params.num_optim_passes;
1921 struct lzx_lru_queue orig_queue;
1922 struct lzx_item *next_chosen_item;
1923 struct lzx_item **next_chosen_item_ptr;
1925 /* Choose appropriate match-finder wrapper functions. */
1926 if (num_passes_remaining > 1) {
1927 if (block_size == c->cur_window_size)
1928 c->get_matches_func = lzx_get_matches_fillcache_singleblock;
1930 c->get_matches_func = lzx_get_matches_fillcache_multiblock;
1931 c->skip_bytes_func = lzx_skip_bytes_fillcache;
1933 if (block_size == c->cur_window_size)
1934 c->get_matches_func = lzx_get_matches_nocache_singleblock;
1936 c->get_matches_func = lzx_get_matches_nocache_multiblock;
1937 c->skip_bytes_func = lzx_skip_bytes_nocache;
1940 /* No matches will extend beyond the end of the block. */
1941 c->match_window_end = block_start_pos + block_size;
1943 /* The first optimization pass will use a default cost model. Each
1944 * additional optimization pass will use a cost model computed from the
1947 * To improve performance we only generate the array containing the
1948 * matches and literals in intermediate form on the final pass. For
1949 * earlier passes, tallying symbol frequencies is sufficient. */
1950 lzx_set_default_costs(&c->costs, c->num_main_syms);
1952 next_chosen_item_ptr = NULL;
1953 orig_queue = c->queue;
1955 /* Reset the match-finder wrapper. */
1956 c->match_window_pos = block_start_pos;
1957 c->cache_ptr = c->cached_matches;
1959 if (num_passes_remaining == 1) {
1960 /* Last pass: actually generate the items. */
1961 next_chosen_item = c->chosen_items;
1962 next_chosen_item_ptr = &next_chosen_item;
1965 /* Choose the items. */
1966 lzx_optim_pass(c, next_chosen_item_ptr);
1968 if (num_passes_remaining > 1) {
1969 /* This isn't the last pass. */
1971 /* Make the Huffman codes from the symbol frequencies. */
1972 lzx_make_huffman_codes(&c->freqs, &c->codes[c->codes_index],
1975 /* Update symbol costs. */
1976 lzx_set_costs(c, &c->codes[c->codes_index].lens);
1978 /* Reset symbol frequencies. */
1979 memset(&c->freqs, 0, sizeof(c->freqs));
1981 /* Reset the match offset LRU queue to what it was at
1982 * the beginning of the block. */
1983 c->queue = orig_queue;
1985 /* Choose appopriate match-finder wrapper functions. */
1986 if (c->cache_ptr <= c->cache_limit) {
1987 c->get_matches_func = lzx_get_matches_usecache_nocheck;
1988 c->skip_bytes_func = lzx_skip_bytes_usecache_nocheck;
1990 c->get_matches_func = lzx_get_matches_usecache;
1991 c->skip_bytes_func = lzx_skip_bytes_usecache;
1994 } while (--num_passes_remaining);
1996 /* Return the number of items chosen. */
1997 return next_chosen_item - c->chosen_items;
2001 * Choose the matches/literals with which to output the block of data beginning
2002 * at '&c->cur_window[block_start_pos]' and extending for 'block_size' bytes.
2004 * The frequences of the Huffman symbols in the block will be tallied in
2007 * 'c->queue' must specify the state of the queue at the beginning of this block.
2008 * This function will update it to the state of the queue at the end of this
2011 * Returns the number of matches/literals that were chosen and written to
2012 * 'c->chosen_items' in the 'struct lzx_item' intermediate representation.
2015 lzx_choose_items_for_block(struct lzx_compressor *c,
2016 u32 block_start_pos, u32 block_size)
2018 return (*c->params.choose_items_for_block)(c, block_start_pos, block_size);
2021 /* Initialize c->offset_slot_fast. */
2023 lzx_init_offset_slot_fast(struct lzx_compressor *c)
2027 for (u32 offset = 0; offset < LZX_NUM_FAST_OFFSETS; offset++) {
2029 while (offset + LZX_OFFSET_OFFSET >= lzx_offset_slot_base[slot + 1])
2032 c->offset_slot_fast[offset] = slot;
2036 /* Set internal compression parameters for the specified compression level and
2037 * maximum window size. */
2039 lzx_build_params(unsigned int compression_level, u32 max_window_size,
2040 struct lzx_compressor_params *lzx_params)
2042 if (compression_level < 25) {
2044 /* Fast compression: Use lazy parsing. */
2046 lzx_params->choose_items_for_block = lzx_choose_lazy_items_for_block;
2047 lzx_params->num_optim_passes = 1;
2049 /* When lazy parsing, the hash chain match-finding algorithm is
2050 * fastest unless the window is too large.
2052 * TODO: something like hash arrays would actually be better
2053 * than binary trees on large windows. */
2054 if (max_window_size <= 262144)
2055 lzx_params->mf_algo = LZ_MF_HASH_CHAINS;
2057 lzx_params->mf_algo = LZ_MF_BINARY_TREES;
2059 /* When lazy parsing, don't bother with length 2 matches. */
2060 lzx_params->min_match_length = 3;
2062 /* Scale nice_match_length and max_search_depth with the
2063 * compression level. */
2064 lzx_params->nice_match_length = 25 + compression_level * 2;
2065 lzx_params->max_search_depth = 25 + compression_level;
2068 /* Normal / high compression: Use near-optimal parsing. */
2070 lzx_params->choose_items_for_block = lzx_choose_near_optimal_items_for_block;
2072 /* Set a number of optimization passes appropriate for the
2073 * compression level. */
2075 lzx_params->num_optim_passes = 1;
2077 if (compression_level >= 40)
2078 lzx_params->num_optim_passes++;
2080 /* Use more optimization passes for higher compression levels.
2081 * But the more passes there are, the less they help --- so
2082 * don't add them linearly. */
2083 if (compression_level >= 70) {
2084 lzx_params->num_optim_passes++;
2085 if (compression_level >= 100)
2086 lzx_params->num_optim_passes++;
2087 if (compression_level >= 150)
2088 lzx_params->num_optim_passes++;
2089 if (compression_level >= 200)
2090 lzx_params->num_optim_passes++;
2091 if (compression_level >= 300)
2092 lzx_params->num_optim_passes++;
2095 /* When doing near-optimal parsing, the hash chain match-finding
2096 * algorithm is good if the window size is small and we're only
2097 * doing one optimization pass. Otherwise, the binary tree
2098 * algorithm is the way to go. */
2099 if (max_window_size <= 32768 && lzx_params->num_optim_passes == 1)
2100 lzx_params->mf_algo = LZ_MF_HASH_CHAINS;
2102 lzx_params->mf_algo = LZ_MF_BINARY_TREES;
2104 /* When doing near-optimal parsing, allow length 2 matches if
2105 * the compression level is sufficiently high. */
2106 if (compression_level >= 45)
2107 lzx_params->min_match_length = 2;
2109 lzx_params->min_match_length = 3;
2111 /* Scale nice_match_length and max_search_depth with the
2112 * compression level. */
2113 lzx_params->nice_match_length = min(((u64)compression_level * 32) / 50,
2115 lzx_params->max_search_depth = min(((u64)compression_level * 50) / 50,
2120 /* Given the internal compression parameters and maximum window size, build the
2121 * Lempel-Ziv match-finder parameters. */
2123 lzx_build_mf_params(const struct lzx_compressor_params *lzx_params,
2124 u32 max_window_size, struct lz_mf_params *mf_params)
2126 memset(mf_params, 0, sizeof(*mf_params));
2128 mf_params->algorithm = lzx_params->mf_algo;
2129 mf_params->max_window_size = max_window_size;
2130 mf_params->min_match_len = lzx_params->min_match_length;
2131 mf_params->max_match_len = LZX_MAX_MATCH_LEN;
2132 mf_params->max_search_depth = lzx_params->max_search_depth;
2133 mf_params->nice_match_len = lzx_params->nice_match_length;
2137 lzx_free_compressor(void *_c);
2140 lzx_get_needed_memory(size_t max_block_size, unsigned int compression_level)
2142 struct lzx_compressor_params params;
2144 unsigned window_order;
2145 u32 max_window_size;
2147 window_order = lzx_get_window_order(max_block_size);
2148 if (window_order == 0)
2150 max_window_size = max_block_size;
2152 lzx_build_params(compression_level, max_window_size, ¶ms);
2154 size += sizeof(struct lzx_compressor);
2157 size += max_window_size;
2160 size += lz_mf_get_needed_memory(params.mf_algo, max_window_size);
2162 /* cached_matches */
2163 if (params.num_optim_passes > 1)
2164 size += LZX_CACHE_LEN * sizeof(struct lz_match);
2166 size += LZX_MAX_MATCHES_PER_POS * sizeof(struct lz_match);
2171 lzx_create_compressor(size_t max_block_size, unsigned int compression_level,
2174 struct lzx_compressor *c;
2175 struct lzx_compressor_params params;
2176 struct lz_mf_params mf_params;
2177 unsigned window_order;
2178 u32 max_window_size;
2180 window_order = lzx_get_window_order(max_block_size);
2181 if (window_order == 0)
2182 return WIMLIB_ERR_INVALID_PARAM;
2183 max_window_size = max_block_size;
2185 lzx_build_params(compression_level, max_window_size, ¶ms);
2186 lzx_build_mf_params(¶ms, max_window_size, &mf_params);
2187 if (!lz_mf_params_valid(&mf_params))
2188 return WIMLIB_ERR_INVALID_PARAM;
2190 c = CALLOC(1, sizeof(struct lzx_compressor));
2195 c->num_main_syms = lzx_get_num_main_syms(window_order);
2196 c->window_order = window_order;
2198 /* The window is allocated as 16-byte aligned to speed up memcpy() and
2199 * enable lzx_e8_filter() optimization on x86_64. */
2200 c->cur_window = ALIGNED_MALLOC(max_window_size, 16);
2204 c->mf = lz_mf_alloc(&mf_params);
2208 if (params.num_optim_passes > 1) {
2209 c->cached_matches = MALLOC(LZX_CACHE_LEN *
2210 sizeof(struct lz_match));
2211 if (!c->cached_matches)
2213 c->cache_limit = c->cached_matches + LZX_CACHE_LEN -
2214 (LZX_MAX_MATCHES_PER_POS + 1);
2216 c->cached_matches = MALLOC(LZX_MAX_MATCHES_PER_POS *
2217 sizeof(struct lz_match));
2218 if (!c->cached_matches)
2222 lzx_init_offset_slot_fast(c);
2228 lzx_free_compressor(c);
2229 return WIMLIB_ERR_NOMEM;
2233 lzx_compress(const void *uncompressed_data, size_t uncompressed_size,
2234 void *compressed_data, size_t compressed_size_avail, void *_c)
2236 struct lzx_compressor *c = _c;
2237 struct lzx_output_bitstream os;
2238 u32 num_chosen_items;
2239 const struct lzx_lens *prev_lens;
2240 u32 block_start_pos;
2244 /* Don't bother compressing very small inputs. */
2245 if (uncompressed_size < 100)
2248 /* The input data must be preprocessed. To avoid changing the original
2249 * input data, copy it to a temporary buffer. */
2250 memcpy(c->cur_window, uncompressed_data, uncompressed_size);
2251 c->cur_window_size = uncompressed_size;
2253 /* Preprocess the data. */
2254 lzx_do_e8_preprocessing(c->cur_window, c->cur_window_size);
2256 /* Load the window into the match-finder. */
2257 lz_mf_load_window(c->mf, c->cur_window, c->cur_window_size);
2259 /* Initialize the match offset LRU queue. */
2260 lzx_lru_queue_init(&c->queue);
2262 /* Initialize the output bitstream. */
2263 lzx_init_output(&os, compressed_data, compressed_size_avail);
2265 /* Compress the data block by block.
2267 * TODO: The compression ratio could be slightly improved by performing
2268 * data-dependent block splitting instead of using fixed-size blocks.
2269 * Doing so well is a computationally hard problem, however. */
2270 block_start_pos = 0;
2272 prev_lens = &c->zero_lens;
2274 /* Compute the block size. */
2275 block_size = min(LZX_DIV_BLOCK_SIZE,
2276 uncompressed_size - block_start_pos);
2278 /* Reset symbol frequencies. */
2279 memset(&c->freqs, 0, sizeof(c->freqs));
2281 /* Prepare the matches/literals for the block. */
2282 num_chosen_items = lzx_choose_items_for_block(c,
2286 /* Make the Huffman codes from the symbol frequencies. */
2287 lzx_make_huffman_codes(&c->freqs, &c->codes[c->codes_index],
2290 /* Choose the best block type.
2292 * Note: we currently don't consider uncompressed blocks. */
2293 block_type = lzx_choose_verbatim_or_aligned(&c->freqs,
2294 &c->codes[c->codes_index]);
2296 /* Write the compressed block to the output buffer. */
2297 lzx_write_compressed_block(block_type,
2303 &c->codes[c->codes_index],
2307 /* The current codeword lengths become the previous lengths. */
2308 prev_lens = &c->codes[c->codes_index].lens;
2309 c->codes_index ^= 1;
2311 block_start_pos += block_size;
2313 } while (block_start_pos != uncompressed_size);
2315 return lzx_flush_output(&os);
2319 lzx_free_compressor(void *_c)
2321 struct lzx_compressor *c = _c;
2324 ALIGNED_FREE(c->cur_window);
2326 FREE(c->cached_matches);
2331 const struct compressor_ops lzx_compressor_ops = {
2332 .get_needed_memory = lzx_get_needed_memory,
2333 .create_compressor = lzx_create_compressor,
2334 .compress = lzx_compress,
2335 .free_compressor = lzx_free_compressor,