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, const struct lz_match **matches_ret)
909 return (*c->get_matches_func)(c, matches_ret);
913 lzx_skip_bytes_fillcache(struct lzx_compressor *c, unsigned n)
915 struct lz_match *cache_ptr;
917 cache_ptr = c->cache_ptr;
918 c->match_window_pos += n;
919 lz_mf_skip_positions(c->mf, n);
920 if (cache_ptr <= c->cache_limit) {
924 } while (--n && cache_ptr <= c->cache_limit);
926 c->cache_ptr = cache_ptr;
930 lzx_skip_bytes_usecache(struct lzx_compressor *c, unsigned n)
932 struct lz_match *cache_ptr;
934 cache_ptr = c->cache_ptr;
935 c->match_window_pos += n;
936 if (cache_ptr <= c->cache_limit) {
938 cache_ptr += 1 + cache_ptr->len;
939 } while (--n && cache_ptr <= c->cache_limit);
941 c->cache_ptr = cache_ptr;
945 lzx_skip_bytes_usecache_nocheck(struct lzx_compressor *c, unsigned n)
947 struct lz_match *cache_ptr;
949 cache_ptr = c->cache_ptr;
950 c->match_window_pos += n;
952 cache_ptr += 1 + cache_ptr->len;
954 c->cache_ptr = cache_ptr;
958 lzx_skip_bytes_nocache(struct lzx_compressor *c, unsigned n)
960 c->match_window_pos += n;
961 lz_mf_skip_positions(c->mf, n);
965 * Skip the specified number of positions in the window (don't search for
968 * This uses a wrapper function around the underlying match-finder.
971 lzx_skip_bytes(struct lzx_compressor *c, unsigned n)
973 return (*c->skip_bytes_func)(c, n);
976 /* Tally, and optionally record, the specified literal byte. */
978 lzx_declare_literal(struct lzx_compressor *c, unsigned literal,
979 struct lzx_item **next_chosen_item)
981 unsigned main_symbol = literal;
983 c->freqs.main[main_symbol]++;
985 if (next_chosen_item) {
986 *(*next_chosen_item)++ = (struct lzx_item) {
992 /* Tally, and optionally record, the specified repeat offset match. */
994 lzx_declare_repeat_offset_match(struct lzx_compressor *c,
995 unsigned len, unsigned rep_index,
996 struct lzx_item **next_chosen_item)
999 unsigned main_symbol;
1000 unsigned len_symbol;
1002 if (len - LZX_MIN_MATCH_LEN < LZX_NUM_PRIMARY_LENS) {
1003 len_header = len - LZX_MIN_MATCH_LEN;
1004 len_symbol = LZX_LENCODE_NUM_SYMBOLS;
1006 len_header = LZX_NUM_PRIMARY_LENS;
1007 len_symbol = len - LZX_MIN_MATCH_LEN - LZX_NUM_PRIMARY_LENS;
1008 c->freqs.len[len_symbol]++;
1011 main_symbol = LZX_NUM_CHARS + ((rep_index << 3) | len_header);
1013 c->freqs.main[main_symbol]++;
1015 if (next_chosen_item) {
1016 *(*next_chosen_item)++ = (struct lzx_item) {
1017 .data = (u64)main_symbol | ((u64)len_symbol << 10),
1022 /* Tally, and optionally record, the specified explicit offset match. */
1024 lzx_declare_explicit_offset_match(struct lzx_compressor *c, unsigned len, u32 offset,
1025 struct lzx_item **next_chosen_item)
1027 unsigned len_header;
1028 unsigned main_symbol;
1029 unsigned len_symbol;
1030 unsigned offset_slot;
1031 unsigned num_extra_bits;
1034 if (len - LZX_MIN_MATCH_LEN < LZX_NUM_PRIMARY_LENS) {
1035 len_header = len - LZX_MIN_MATCH_LEN;
1036 len_symbol = LZX_LENCODE_NUM_SYMBOLS;
1038 len_header = LZX_NUM_PRIMARY_LENS;
1039 len_symbol = len - LZX_MIN_MATCH_LEN - LZX_NUM_PRIMARY_LENS;
1040 c->freqs.len[len_symbol]++;
1043 offset_slot = lzx_get_offset_slot_raw(offset + LZX_OFFSET_OFFSET);
1045 main_symbol = LZX_NUM_CHARS + ((offset_slot << 3) | len_header);
1047 c->freqs.main[main_symbol]++;
1049 if (offset_slot >= 8)
1050 c->freqs.aligned[(offset + LZX_OFFSET_OFFSET) & 7]++;
1052 if (next_chosen_item) {
1054 num_extra_bits = lzx_extra_offset_bits[offset_slot];
1056 extra_bits = (offset + LZX_OFFSET_OFFSET) -
1057 lzx_offset_slot_base[offset_slot];
1059 *(*next_chosen_item)++ = (struct lzx_item) {
1060 .data = (u64)main_symbol |
1061 ((u64)len_symbol << 10) |
1062 ((u64)num_extra_bits << 18) |
1063 ((u64)extra_bits << 23),
1068 /* Tally, and optionally record, the specified match or literal. */
1070 lzx_declare_item(struct lzx_compressor *c, u32 mc_item_data,
1071 struct lzx_item **next_chosen_item)
1073 u32 len = mc_item_data & MC_LEN_MASK;
1074 u32 offset_data = mc_item_data >> MC_OFFSET_SHIFT;
1077 lzx_declare_literal(c, offset_data, next_chosen_item);
1078 else if (offset_data < LZX_NUM_RECENT_OFFSETS)
1079 lzx_declare_repeat_offset_match(c, len, offset_data,
1082 lzx_declare_explicit_offset_match(c, len,
1083 offset_data - LZX_OFFSET_OFFSET,
1088 lzx_record_item_list(struct lzx_compressor *c,
1089 struct lzx_mc_pos_data *cur_optimum_ptr,
1090 struct lzx_item **next_chosen_item)
1092 struct lzx_mc_pos_data *end_optimum_ptr;
1096 /* The list is currently in reverse order (last item to first item).
1098 end_optimum_ptr = cur_optimum_ptr;
1099 saved_item = cur_optimum_ptr->mc_item_data;
1102 cur_optimum_ptr -= item & MC_LEN_MASK;
1103 saved_item = cur_optimum_ptr->mc_item_data;
1104 cur_optimum_ptr->mc_item_data = item;
1105 } while (cur_optimum_ptr != c->optimum);
1107 /* Walk the list of items from beginning to end, tallying and recording
1110 lzx_declare_item(c, cur_optimum_ptr->mc_item_data, next_chosen_item);
1111 cur_optimum_ptr += (cur_optimum_ptr->mc_item_data) & MC_LEN_MASK;
1112 } while (cur_optimum_ptr != end_optimum_ptr);
1116 lzx_tally_item_list(struct lzx_compressor *c, struct lzx_mc_pos_data *cur_optimum_ptr)
1118 /* Since we're just tallying the items, we don't need to reverse the
1119 * list. Processing the items in reverse order is fine. */
1121 lzx_declare_item(c, cur_optimum_ptr->mc_item_data, NULL);
1122 cur_optimum_ptr -= (cur_optimum_ptr->mc_item_data & MC_LEN_MASK);
1123 } while (cur_optimum_ptr != c->optimum);
1126 /* Tally, and optionally (if next_chosen_item != NULL) record, in order, all
1127 * items in the current list of items found by the match-chooser. */
1129 lzx_declare_item_list(struct lzx_compressor *c, struct lzx_mc_pos_data *cur_optimum_ptr,
1130 struct lzx_item **next_chosen_item)
1132 if (next_chosen_item)
1133 lzx_record_item_list(c, cur_optimum_ptr, next_chosen_item);
1135 lzx_tally_item_list(c, cur_optimum_ptr);
1138 /* Set the cost model @c->costs from the Huffman codeword lengths specified in
1141 * The cost model and codeword lengths are almost the same thing, but the
1142 * Huffman codewords with length 0 correspond to symbols with zero frequency
1143 * that still need to be assigned actual costs. The specific values assigned
1144 * are arbitrary, but they should be fairly high (near the maximum codeword
1145 * length) to take into account the fact that uses of these symbols are expected
1148 lzx_set_costs(struct lzx_compressor *c, const struct lzx_lens * lens)
1153 for (i = 0; i < c->num_main_syms; i++)
1154 c->costs.main[i] = lens->main[i] ? lens->main[i] : 15;
1157 for (i = 0; i < LZX_LENCODE_NUM_SYMBOLS; i++)
1158 c->costs.len[i] = lens->len[i] ? lens->len[i] : 15;
1160 /* Aligned offset code */
1161 for (i = 0; i < LZX_ALIGNEDCODE_NUM_SYMBOLS; i++)
1162 c->costs.aligned[i] = lens->aligned[i] ? lens->aligned[i] : 7;
1165 /* Set default LZX Huffman symbol costs to bootstrap the iterative optimization
1168 lzx_set_default_costs(struct lzx_costs * costs, unsigned num_main_syms)
1172 /* Main code (part 1): Literal symbols */
1173 for (i = 0; i < LZX_NUM_CHARS; i++)
1176 /* Main code (part 2): Match header symbols */
1177 for (; i < num_main_syms; i++)
1178 costs->main[i] = 10;
1181 for (i = 0; i < LZX_LENCODE_NUM_SYMBOLS; i++)
1184 /* Aligned offset code */
1185 for (i = 0; i < LZX_ALIGNEDCODE_NUM_SYMBOLS; i++)
1186 costs->aligned[i] = 3;
1189 /* Return the cost, in bits, to output a literal byte using the specified cost
1192 lzx_literal_cost(unsigned literal, const struct lzx_costs * costs)
1194 return costs->main[literal];
1197 /* Return the cost, in bits, to output a match of the specified length and
1198 * offset slot using the specified cost model. Does not take into account
1199 * extra offset bits. */
1201 lzx_match_cost_raw(unsigned len, unsigned offset_slot,
1202 const struct lzx_costs *costs)
1205 unsigned len_header;
1206 unsigned main_symbol;
1208 if (len - LZX_MIN_MATCH_LEN < LZX_NUM_PRIMARY_LENS) {
1209 len_header = len - LZX_MIN_MATCH_LEN;
1212 len_header = LZX_NUM_PRIMARY_LENS;
1214 /* Account for length symbol. */
1215 cost = costs->len[len - LZX_MIN_MATCH_LEN - LZX_NUM_PRIMARY_LENS];
1218 /* Account for main symbol. */
1219 main_symbol = LZX_NUM_CHARS + ((offset_slot << 3) | len_header);
1220 cost += costs->main[main_symbol];
1225 /* Equivalent to lzx_match_cost_raw(), but assumes the length is small enough
1226 * that it doesn't require a length symbol. */
1228 lzx_match_cost_raw_smalllen(unsigned len, unsigned offset_slot,
1229 const struct lzx_costs *costs)
1231 LZX_ASSERT(len < LZX_MIN_MATCH_LEN + LZX_NUM_PRIMARY_LENS);
1232 return costs->main[LZX_NUM_CHARS +
1233 ((offset_slot << 3) | (len - LZX_MIN_MATCH_LEN))];
1237 * Consider coding the match at repeat offset index @rep_idx. Consider each
1238 * length from the minimum (2) to the full match length (@rep_len).
1241 lzx_consider_repeat_offset_match(struct lzx_compressor *c,
1242 struct lzx_mc_pos_data *cur_optimum_ptr,
1243 unsigned rep_len, unsigned rep_idx)
1245 u32 base_cost = cur_optimum_ptr->cost;
1249 #if 1 /* Optimized version */
1251 if (rep_len < LZX_MIN_MATCH_LEN + LZX_NUM_PRIMARY_LENS) {
1252 /* All lengths being considered are small. */
1256 lzx_match_cost_raw_smalllen(len, rep_idx, &c->costs);
1257 if (cost < (cur_optimum_ptr + len)->cost) {
1258 (cur_optimum_ptr + len)->mc_item_data =
1259 (rep_idx << MC_OFFSET_SHIFT) | len;
1260 (cur_optimum_ptr + len)->cost = cost;
1262 } while (++len <= rep_len);
1264 /* Some lengths being considered are small, and some are big.
1265 * Start with the optimized loop for small lengths, then switch
1266 * to the optimized loop for big lengths. */
1270 lzx_match_cost_raw_smalllen(len, rep_idx, &c->costs);
1271 if (cost < (cur_optimum_ptr + len)->cost) {
1272 (cur_optimum_ptr + len)->mc_item_data =
1273 (rep_idx << MC_OFFSET_SHIFT) | len;
1274 (cur_optimum_ptr + len)->cost = cost;
1276 } while (++len < LZX_MIN_MATCH_LEN + LZX_NUM_PRIMARY_LENS);
1278 /* The main symbol is now fixed. */
1279 base_cost += c->costs.main[LZX_NUM_CHARS +
1280 ((rep_idx << 3) | LZX_NUM_PRIMARY_LENS)];
1283 c->costs.len[len - LZX_MIN_MATCH_LEN -
1284 LZX_NUM_PRIMARY_LENS];
1285 if (cost < (cur_optimum_ptr + len)->cost) {
1286 (cur_optimum_ptr + len)->mc_item_data =
1287 (rep_idx << MC_OFFSET_SHIFT) | len;
1288 (cur_optimum_ptr + len)->cost = cost;
1290 } while (++len <= rep_len);
1293 #else /* Unoptimized version */
1298 lzx_match_cost_raw(len, rep_idx, &c->costs);
1299 if (cost < (cur_optimum_ptr + len)->cost) {
1300 (cur_optimum_ptr + len)->mc_item_data =
1301 (rep_idx << MC_OFFSET_SHIFT) | len;
1302 (cur_optimum_ptr + len)->cost = cost;
1304 } while (++len <= rep_len);
1309 * Consider coding each match in @matches as an explicit offset match.
1311 * @matches must be sorted by strictly increasing length and strictly
1312 * increasing offset. This is guaranteed by the match-finder.
1314 * We consider each length from the minimum (2) to the longest
1315 * (matches[num_matches - 1].len). For each length, we consider only
1316 * the smallest offset for which that length is available. Although
1317 * this is not guaranteed to be optimal due to the possibility of a
1318 * larger offset costing less than a smaller offset to code, this is a
1319 * very useful heuristic.
1322 lzx_consider_explicit_offset_matches(struct lzx_compressor *c,
1323 struct lzx_mc_pos_data *cur_optimum_ptr,
1324 const struct lz_match matches[],
1325 unsigned num_matches)
1327 LZX_ASSERT(num_matches > 0);
1331 unsigned offset_slot;
1337 #if 1 /* Optimized version */
1339 if (matches[num_matches - 1].offset < LZX_NUM_FAST_OFFSETS) {
1342 * Offset is small; the offset slot can be looked up directly in
1343 * c->offset_slot_fast.
1345 * Additional optimizations:
1347 * - Since the offset is small, it falls in the exponential part
1348 * of the offset slot bases and the number of extra offset
1349 * bits can be calculated directly as (offset_slot >> 1) - 1.
1351 * - Just consider the number of extra offset bits; don't
1352 * account for the aligned offset code. Usually this has
1353 * almost no effect on the compression ratio.
1355 * - Start out in a loop optimized for small lengths. When the
1356 * length becomes high enough that a length symbol will be
1357 * needed, jump into a loop optimized for big lengths.
1360 LZX_ASSERT(offset_slot <= 37); /* for extra bits formula */
1365 offset_slot = c->offset_slot_fast[matches[i].offset];
1366 position_cost = cur_optimum_ptr->cost +
1367 ((offset_slot >> 1) - 1);
1368 offset_data = matches[i].offset + LZX_OFFSET_OFFSET;
1370 if (len >= LZX_MIN_MATCH_LEN + LZX_NUM_PRIMARY_LENS)
1372 cost = position_cost +
1373 lzx_match_cost_raw_smalllen(len, offset_slot,
1375 if (cost < (cur_optimum_ptr + len)->cost) {
1376 (cur_optimum_ptr + len)->cost = cost;
1377 (cur_optimum_ptr + len)->mc_item_data =
1378 (offset_data << MC_OFFSET_SHIFT) | len;
1380 } while (++len <= matches[i].len);
1381 } while (++i != num_matches);
1386 offset_slot = c->offset_slot_fast[matches[i].offset];
1388 position_cost = cur_optimum_ptr->cost +
1389 ((offset_slot >> 1) - 1) +
1390 c->costs.main[LZX_NUM_CHARS +
1391 ((offset_slot << 3) |
1392 LZX_NUM_PRIMARY_LENS)];
1393 offset_data = matches[i].offset + LZX_OFFSET_OFFSET;
1395 cost = position_cost +
1396 c->costs.len[len - LZX_MIN_MATCH_LEN -
1397 LZX_NUM_PRIMARY_LENS];
1398 if (cost < (cur_optimum_ptr + len)->cost) {
1399 (cur_optimum_ptr + len)->cost = cost;
1400 (cur_optimum_ptr + len)->mc_item_data =
1401 (offset_data << MC_OFFSET_SHIFT) | len;
1403 } while (++len <= matches[i].len);
1404 } while (++i != num_matches);
1409 offset_data = matches[i].offset + LZX_OFFSET_OFFSET;
1410 offset_slot = lzx_get_offset_slot_raw(offset_data);
1411 position_cost = cur_optimum_ptr->cost +
1412 lzx_extra_offset_bits[offset_slot];
1414 cost = position_cost +
1415 lzx_match_cost_raw(len, offset_slot, &c->costs);
1416 if (cost < (cur_optimum_ptr + len)->cost) {
1417 (cur_optimum_ptr + len)->cost = cost;
1418 (cur_optimum_ptr + len)->mc_item_data =
1419 (offset_data << MC_OFFSET_SHIFT) | len;
1421 } while (++len <= matches[i].len);
1422 } while (++i != num_matches);
1425 #else /* Unoptimized version */
1427 unsigned num_extra_bits;
1432 offset_data = matches[i].offset + LZX_OFFSET_OFFSET;
1433 position_cost = cur_optimum_ptr->cost;
1434 offset_slot = lzx_get_offset_slot_raw(offset_data);
1435 num_extra_bits = lzx_extra_offset_bits[offset_slot];
1436 if (num_extra_bits >= 3) {
1437 position_cost += num_extra_bits - 3;
1438 position_cost += c->costs.aligned[offset_data & 7];
1440 position_cost += num_extra_bits;
1443 cost = position_cost +
1444 lzx_match_cost_raw(len, offset_slot, &c->costs);
1445 if (cost < (cur_optimum_ptr + len)->cost) {
1446 (cur_optimum_ptr + len)->cost = cost;
1447 (cur_optimum_ptr + len)->mc_item_data =
1448 (offset_data << MC_OFFSET_SHIFT) | len;
1450 } while (++len <= matches[i].len);
1451 } while (++i != num_matches);
1456 * Search for repeat offset matches with the current position.
1458 static inline unsigned
1459 lzx_repsearch(const u8 * const strptr, const u32 bytes_remaining,
1460 const struct lzx_lru_queue *queue, unsigned *rep_max_idx_ret)
1462 BUILD_BUG_ON(LZX_NUM_RECENT_OFFSETS != 3);
1463 return lz_repsearch3(strptr, min(bytes_remaining, LZX_MAX_MATCH_LEN),
1464 queue->R, rep_max_idx_ret);
1468 * The main near-optimal parsing routine.
1470 * Briefly, the algorithm does an approximate minimum-cost path search to find a
1471 * "near-optimal" sequence of matches and literals to output, based on the
1472 * current cost model. The algorithm steps forward, position by position (byte
1473 * by byte), and updates the minimum cost path to reach each later position that
1474 * can be reached using a match or literal from the current position. This is
1475 * essentially Dijkstra's algorithm in disguise: the graph nodes are positions,
1476 * the graph edges are possible matches/literals to code, and the cost of each
1477 * edge is the estimated number of bits that will be required to output the
1478 * corresponding match or literal. But one difference is that we actually
1479 * compute the lowest-cost path in pieces, where each piece is terminated when
1480 * there are no choices to be made.
1482 * This function will run this algorithm on the portion of the window from
1483 * &c->cur_window[c->match_window_pos] to &c->cur_window[c->match_window_end].
1485 * On entry, c->queue must be the current state of the match offset LRU queue,
1486 * and c->costs must be the current cost model to use for Huffman symbols.
1488 * On exit, c->queue will be the state that the LRU queue would be in if the
1489 * chosen items were to be coded.
1491 * If next_chosen_item != NULL, then all items chosen will be recorded (saved in
1492 * the chosen_items array). Otherwise, all items chosen will only be tallied
1493 * (symbol frequencies tallied in c->freqs).
1496 lzx_optim_pass(struct lzx_compressor *c, struct lzx_item **next_chosen_item)
1498 const u8 *block_end;
1499 struct lzx_lru_queue *begin_queue;
1500 const u8 *window_ptr;
1501 struct lzx_mc_pos_data *cur_optimum_ptr;
1502 struct lzx_mc_pos_data *end_optimum_ptr;
1503 const struct lz_match *matches;
1504 unsigned num_matches;
1505 unsigned longest_len;
1506 unsigned rep_max_len;
1507 unsigned rep_max_idx;
1513 block_end = &c->cur_window[c->match_window_end];
1514 begin_queue = &c->queue;
1516 /* Start building a new list of items, which will correspond to the next
1517 * piece of the overall minimum-cost path.
1519 * *begin_queue is the current state of the match offset LRU queue. */
1521 window_ptr = &c->cur_window[c->match_window_pos];
1523 if (window_ptr == block_end) {
1524 c->queue = *begin_queue;
1528 cur_optimum_ptr = c->optimum;
1529 cur_optimum_ptr->cost = 0;
1530 cur_optimum_ptr->queue = *begin_queue;
1532 end_optimum_ptr = cur_optimum_ptr;
1534 /* The following loop runs once for each per byte in the window, except
1535 * in a couple shortcut cases. */
1538 /* Find explicit offset matches with the current position. */
1539 num_matches = lzx_get_matches(c, &matches);
1543 * Find the longest repeat offset match with the current
1548 * - Only search for repeat offset matches if the
1549 * match-finder already found at least one match.
1551 * - Only consider the longest repeat offset match. It
1552 * seems to be rare for the optimal parse to include a
1553 * repeat offset match that doesn't have the longest
1554 * length (allowing for the possibility that not all
1555 * of that length is actually used).
1557 rep_max_len = lzx_repsearch(window_ptr,
1558 block_end - window_ptr,
1559 &cur_optimum_ptr->queue,
1563 /* If there's a very long repeat offset match,
1564 * choose it immediately. */
1565 if (rep_max_len >= c->params.nice_match_length) {
1567 swap(cur_optimum_ptr->queue.R[0],
1568 cur_optimum_ptr->queue.R[rep_max_idx]);
1569 begin_queue = &cur_optimum_ptr->queue;
1571 cur_optimum_ptr += rep_max_len;
1572 cur_optimum_ptr->mc_item_data =
1573 (rep_max_idx << MC_OFFSET_SHIFT) |
1576 lzx_skip_bytes(c, rep_max_len - 1);
1580 /* If reaching any positions for the first time,
1581 * initialize their costs to "infinity". */
1582 while (end_optimum_ptr < cur_optimum_ptr + rep_max_len)
1583 (++end_optimum_ptr)->cost = MC_INFINITE_COST;
1585 /* Consider coding a repeat offset match. */
1586 lzx_consider_repeat_offset_match(c,
1592 longest_len = matches[num_matches - 1].len;
1594 /* If there's a very long explicit offset match, choose
1595 * it immediately. */
1596 if (longest_len >= c->params.nice_match_length) {
1598 cur_optimum_ptr->queue.R[2] =
1599 cur_optimum_ptr->queue.R[1];
1600 cur_optimum_ptr->queue.R[1] =
1601 cur_optimum_ptr->queue.R[0];
1602 cur_optimum_ptr->queue.R[0] =
1603 matches[num_matches - 1].offset;
1604 begin_queue = &cur_optimum_ptr->queue;
1606 offset_data = matches[num_matches - 1].offset +
1608 cur_optimum_ptr += longest_len;
1609 cur_optimum_ptr->mc_item_data =
1610 (offset_data << MC_OFFSET_SHIFT) |
1613 lzx_skip_bytes(c, longest_len - 1);
1617 /* If reaching any positions for the first time,
1618 * initialize their costs to "infinity". */
1619 while (end_optimum_ptr < cur_optimum_ptr + longest_len)
1620 (++end_optimum_ptr)->cost = MC_INFINITE_COST;
1622 /* Consider coding an explicit offset match. */
1623 lzx_consider_explicit_offset_matches(c, cur_optimum_ptr,
1624 matches, num_matches);
1626 /* No matches found. The only choice at this position
1627 * is to code a literal. */
1629 if (end_optimum_ptr == cur_optimum_ptr) {
1631 /* Optimization for single literals. */
1632 if (likely(cur_optimum_ptr == c->optimum)) {
1633 lzx_declare_literal(c, *window_ptr++,
1635 if (window_ptr == block_end) {
1636 c->queue = cur_optimum_ptr->queue;
1642 (++end_optimum_ptr)->cost = MC_INFINITE_COST;
1646 /* Consider coding a literal.
1648 * To avoid an extra unpredictable brench, actually checking the
1649 * preferability of coding a literal is integrated into the
1650 * queue update code below. */
1651 literal = *window_ptr++;
1652 cost = cur_optimum_ptr->cost + lzx_literal_cost(literal, &c->costs);
1654 /* Advance to the next position. */
1657 /* The lowest-cost path to the current position is now known.
1658 * Finalize the recent offsets queue that results from taking
1659 * this lowest-cost path. */
1661 if (cost < cur_optimum_ptr->cost) {
1662 /* Literal: queue remains unchanged. */
1663 cur_optimum_ptr->cost = cost;
1664 cur_optimum_ptr->mc_item_data = (literal << MC_OFFSET_SHIFT) | 1;
1665 cur_optimum_ptr->queue = (cur_optimum_ptr - 1)->queue;
1667 /* Match: queue update is needed. */
1668 len = cur_optimum_ptr->mc_item_data & MC_LEN_MASK;
1669 offset_data = cur_optimum_ptr->mc_item_data >> MC_OFFSET_SHIFT;
1670 if (offset_data >= LZX_NUM_RECENT_OFFSETS) {
1671 /* Explicit offset match: offset is inserted at front */
1672 cur_optimum_ptr->queue.R[0] = offset_data - LZX_OFFSET_OFFSET;
1673 cur_optimum_ptr->queue.R[1] = (cur_optimum_ptr - len)->queue.R[0];
1674 cur_optimum_ptr->queue.R[2] = (cur_optimum_ptr - len)->queue.R[1];
1676 /* Repeat offset match: offset is swapped to front */
1677 cur_optimum_ptr->queue = (cur_optimum_ptr - len)->queue;
1678 swap(cur_optimum_ptr->queue.R[0],
1679 cur_optimum_ptr->queue.R[offset_data]);
1684 * This loop will terminate when either of the following
1685 * conditions is true:
1687 * (1) cur_optimum_ptr == end_optimum_ptr
1689 * There are no paths that extend beyond the current
1690 * position. In this case, any path to a later position
1691 * must pass through the current position, so we can go
1692 * ahead and choose the list of items that led to this
1695 * (2) cur_optimum_ptr == &c->optimum[LZX_OPTIM_ARRAY_LENGTH]
1697 * This bounds the number of times the algorithm can step
1698 * forward before it is guaranteed to start choosing items.
1699 * This limits the memory usage. But
1700 * LZX_OPTIM_ARRAY_LENGTH is high enough that on most
1701 * inputs this limit is never reached.
1703 * Note: no check for end-of-block is needed because
1704 * end-of-block will trigger condition (1).
1706 if (cur_optimum_ptr == end_optimum_ptr ||
1707 cur_optimum_ptr == &c->optimum[LZX_OPTIM_ARRAY_LENGTH])
1709 begin_queue = &cur_optimum_ptr->queue;
1714 /* Choose the current list of items that constitute the minimum-cost
1715 * path to the current position. */
1716 lzx_declare_item_list(c, cur_optimum_ptr, next_chosen_item);
1720 /* Fast heuristic scoring for lazy parsing: how "good" is this match? */
1721 static inline unsigned
1722 lzx_explicit_offset_match_score(unsigned len, u32 adjusted_offset)
1724 unsigned score = len;
1726 if (adjusted_offset < 2048)
1729 if (adjusted_offset < 1024)
1735 static inline unsigned
1736 lzx_repeat_offset_match_score(unsigned len, unsigned slot)
1743 lzx_choose_lazy_items_for_block(struct lzx_compressor *c,
1744 u32 block_start_pos, u32 block_size)
1746 const u8 *window_ptr;
1747 const u8 *block_end;
1749 struct lz_match *matches;
1750 unsigned num_matches;
1752 u32 cur_offset_data;
1754 unsigned rep_max_len;
1755 unsigned rep_max_idx;
1758 unsigned prev_score;
1759 u32 prev_offset_data;
1761 struct lzx_item *next_chosen_item;
1763 window_ptr = &c->cur_window[block_start_pos];
1764 block_end = window_ptr + block_size;
1765 matches = c->cached_matches;
1767 next_chosen_item = c->chosen_items;
1770 prev_offset_data = 0;
1773 while (window_ptr != block_end) {
1775 /* Find explicit offset matches with the current position. */
1776 num_matches = lz_mf_get_matches(mf, matches);
1779 if (num_matches == 0 ||
1780 (matches[num_matches - 1].len == 3 &&
1781 matches[num_matches - 1].offset >= 8192 - LZX_OFFSET_OFFSET &&
1782 matches[num_matches - 1].offset != c->queue.R[0] &&
1783 matches[num_matches - 1].offset != c->queue.R[1] &&
1784 matches[num_matches - 1].offset != c->queue.R[2]))
1786 /* No match found, or the only match found was a distant
1787 * length 3 match. Output the previous match if there
1788 * is one; otherwise output a literal. */
1793 skip_len = prev_len - 2;
1794 goto output_prev_match;
1796 lzx_declare_literal(c, *(window_ptr - 1),
1802 /* Find the longest repeat offset match with the current
1804 if (likely(block_end - (window_ptr - 1) >= 2)) {
1805 rep_max_len = lzx_repsearch((window_ptr - 1),
1806 block_end - (window_ptr - 1),
1807 &c->queue, &rep_max_idx);
1812 cur_len = matches[num_matches - 1].len;
1813 cur_offset_data = matches[num_matches - 1].offset + LZX_OFFSET_OFFSET;
1814 cur_score = lzx_explicit_offset_match_score(cur_len, cur_offset_data);
1816 /* Select the better of the explicit and repeat offset matches. */
1817 if (rep_max_len >= 3 &&
1818 (rep_score = lzx_repeat_offset_match_score(rep_max_len,
1819 rep_max_idx)) >= cur_score)
1821 cur_len = rep_max_len;
1822 cur_offset_data = rep_max_idx;
1823 cur_score = rep_score;
1826 if (unlikely(cur_len > block_end - (window_ptr - 1))) {
1827 /* Nearing end of block. */
1828 cur_len = block_end - (window_ptr - 1);
1830 goto no_match_found;
1833 if (prev_len == 0 || cur_score > prev_score) {
1834 /* No previous match, or the current match is better
1835 * than the previous match.
1837 * If there's a previous match, then output a literal in
1840 * In both cases, if the current match is very long,
1841 * then output it immediately. Otherwise, attempt a
1842 * lazy match by waiting to see if there's a better
1843 * match at the next position. */
1846 lzx_declare_literal(c, *(window_ptr - 2), &next_chosen_item);
1849 prev_offset_data = cur_offset_data;
1850 prev_score = cur_score;
1852 if (prev_len >= c->params.nice_match_length) {
1853 skip_len = prev_len - 1;
1854 goto output_prev_match;
1859 /* Current match is not better than the previous match, so
1860 * output the previous match. */
1862 skip_len = prev_len - 2;
1865 if (prev_offset_data < LZX_NUM_RECENT_OFFSETS) {
1866 lzx_declare_repeat_offset_match(c, prev_len,
1869 swap(c->queue.R[0], c->queue.R[prev_offset_data]);
1871 lzx_declare_explicit_offset_match(c, prev_len,
1872 prev_offset_data - LZX_OFFSET_OFFSET,
1874 c->queue.R[2] = c->queue.R[1];
1875 c->queue.R[1] = c->queue.R[0];
1876 c->queue.R[0] = prev_offset_data - LZX_OFFSET_OFFSET;
1878 lz_mf_skip_positions(mf, skip_len);
1879 window_ptr += skip_len;
1883 return next_chosen_item - c->chosen_items;
1886 /* Given the frequencies of symbols in an LZX-compressed block and the
1887 * corresponding Huffman codes, return LZX_BLOCKTYPE_ALIGNED or
1888 * LZX_BLOCKTYPE_VERBATIM if an aligned offset or verbatim block, respectively,
1889 * will take fewer bits to output. */
1891 lzx_choose_verbatim_or_aligned(const struct lzx_freqs * freqs,
1892 const struct lzx_codes * codes)
1894 u32 aligned_cost = 0;
1895 u32 verbatim_cost = 0;
1897 /* A verbatim block requires 3 bits in each place that an aligned symbol
1898 * would be used in an aligned offset block. */
1899 for (unsigned i = 0; i < LZX_ALIGNEDCODE_NUM_SYMBOLS; i++) {
1900 verbatim_cost += 3 * freqs->aligned[i];
1901 aligned_cost += codes->lens.aligned[i] * freqs->aligned[i];
1904 /* Account for output of the aligned offset code. */
1905 aligned_cost += LZX_ALIGNEDCODE_ELEMENT_SIZE * LZX_ALIGNEDCODE_NUM_SYMBOLS;
1907 if (aligned_cost < verbatim_cost)
1908 return LZX_BLOCKTYPE_ALIGNED;
1910 return LZX_BLOCKTYPE_VERBATIM;
1913 /* Near-optimal parsing */
1915 lzx_choose_near_optimal_items_for_block(struct lzx_compressor *c,
1916 u32 block_start_pos, u32 block_size)
1918 u32 num_passes_remaining = c->params.num_optim_passes;
1919 struct lzx_lru_queue orig_queue;
1920 struct lzx_item *next_chosen_item;
1921 struct lzx_item **next_chosen_item_ptr;
1923 /* Choose appropriate match-finder wrapper functions. */
1924 if (num_passes_remaining > 1) {
1925 if (block_size == c->cur_window_size)
1926 c->get_matches_func = lzx_get_matches_fillcache_singleblock;
1928 c->get_matches_func = lzx_get_matches_fillcache_multiblock;
1929 c->skip_bytes_func = lzx_skip_bytes_fillcache;
1931 if (block_size == c->cur_window_size)
1932 c->get_matches_func = lzx_get_matches_nocache_singleblock;
1934 c->get_matches_func = lzx_get_matches_nocache_multiblock;
1935 c->skip_bytes_func = lzx_skip_bytes_nocache;
1938 /* No matches will extend beyond the end of the block. */
1939 c->match_window_end = block_start_pos + block_size;
1941 /* The first optimization pass will use a default cost model. Each
1942 * additional optimization pass will use a cost model computed from the
1945 * To improve performance we only generate the array containing the
1946 * matches and literals in intermediate form on the final pass. For
1947 * earlier passes, tallying symbol frequencies is sufficient. */
1948 lzx_set_default_costs(&c->costs, c->num_main_syms);
1950 next_chosen_item_ptr = NULL;
1951 orig_queue = c->queue;
1953 /* Reset the match-finder wrapper. */
1954 c->match_window_pos = block_start_pos;
1955 c->cache_ptr = c->cached_matches;
1957 if (num_passes_remaining == 1) {
1958 /* Last pass: actually generate the items. */
1959 next_chosen_item = c->chosen_items;
1960 next_chosen_item_ptr = &next_chosen_item;
1963 /* Choose the items. */
1964 lzx_optim_pass(c, next_chosen_item_ptr);
1966 if (num_passes_remaining > 1) {
1967 /* This isn't the last pass. */
1969 /* Make the Huffman codes from the symbol frequencies. */
1970 lzx_make_huffman_codes(&c->freqs, &c->codes[c->codes_index],
1973 /* Update symbol costs. */
1974 lzx_set_costs(c, &c->codes[c->codes_index].lens);
1976 /* Reset symbol frequencies. */
1977 memset(&c->freqs, 0, sizeof(c->freqs));
1979 /* Reset the match offset LRU queue to what it was at
1980 * the beginning of the block. */
1981 c->queue = orig_queue;
1983 /* Choose appopriate match-finder wrapper functions. */
1984 if (c->cache_ptr <= c->cache_limit) {
1985 c->get_matches_func = lzx_get_matches_usecache_nocheck;
1986 c->skip_bytes_func = lzx_skip_bytes_usecache_nocheck;
1988 c->get_matches_func = lzx_get_matches_usecache;
1989 c->skip_bytes_func = lzx_skip_bytes_usecache;
1992 } while (--num_passes_remaining);
1994 /* Return the number of items chosen. */
1995 return next_chosen_item - c->chosen_items;
1999 * Choose the matches/literals with which to output the block of data beginning
2000 * at '&c->cur_window[block_start_pos]' and extending for 'block_size' bytes.
2002 * The frequences of the Huffman symbols in the block will be tallied in
2005 * 'c->queue' must specify the state of the queue at the beginning of this block.
2006 * This function will update it to the state of the queue at the end of this
2009 * Returns the number of matches/literals that were chosen and written to
2010 * 'c->chosen_items' in the 'struct lzx_item' intermediate representation.
2013 lzx_choose_items_for_block(struct lzx_compressor *c,
2014 u32 block_start_pos, u32 block_size)
2016 return (*c->params.choose_items_for_block)(c, block_start_pos, block_size);
2019 /* Initialize c->offset_slot_fast. */
2021 lzx_init_offset_slot_fast(struct lzx_compressor *c)
2025 for (u32 offset = 0; offset < LZX_NUM_FAST_OFFSETS; offset++) {
2027 while (offset + LZX_OFFSET_OFFSET >= lzx_offset_slot_base[slot + 1])
2030 c->offset_slot_fast[offset] = slot;
2034 /* Set internal compression parameters for the specified compression level and
2035 * maximum window size. */
2037 lzx_build_params(unsigned int compression_level, u32 max_window_size,
2038 struct lzx_compressor_params *lzx_params)
2040 if (compression_level < 25) {
2042 /* Fast compression: Use lazy parsing. */
2044 lzx_params->choose_items_for_block = lzx_choose_lazy_items_for_block;
2045 lzx_params->num_optim_passes = 1;
2047 /* When lazy parsing, the hash chain match-finding algorithm is
2048 * fastest unless the window is too large.
2050 * TODO: something like hash arrays would actually be better
2051 * than binary trees on large windows. */
2052 if (max_window_size <= 262144)
2053 lzx_params->mf_algo = LZ_MF_HASH_CHAINS;
2055 lzx_params->mf_algo = LZ_MF_BINARY_TREES;
2057 /* When lazy parsing, don't bother with length 2 matches. */
2058 lzx_params->min_match_length = 3;
2060 /* Scale nice_match_length and max_search_depth with the
2061 * compression level. */
2062 lzx_params->nice_match_length = 25 + compression_level * 2;
2063 lzx_params->max_search_depth = 25 + compression_level;
2066 /* Normal / high compression: Use near-optimal parsing. */
2068 lzx_params->choose_items_for_block = lzx_choose_near_optimal_items_for_block;
2070 /* Set a number of optimization passes appropriate for the
2071 * compression level. */
2073 lzx_params->num_optim_passes = 1;
2075 if (compression_level >= 40)
2076 lzx_params->num_optim_passes++;
2078 /* Use more optimization passes for higher compression levels.
2079 * But the more passes there are, the less they help --- so
2080 * don't add them linearly. */
2081 if (compression_level >= 70) {
2082 lzx_params->num_optim_passes++;
2083 if (compression_level >= 100)
2084 lzx_params->num_optim_passes++;
2085 if (compression_level >= 150)
2086 lzx_params->num_optim_passes++;
2087 if (compression_level >= 200)
2088 lzx_params->num_optim_passes++;
2089 if (compression_level >= 300)
2090 lzx_params->num_optim_passes++;
2093 /* When doing near-optimal parsing, the hash chain match-finding
2094 * algorithm is good if the window size is small and we're only
2095 * doing one optimization pass. Otherwise, the binary tree
2096 * algorithm is the way to go. */
2097 if (max_window_size <= 32768 && lzx_params->num_optim_passes == 1)
2098 lzx_params->mf_algo = LZ_MF_HASH_CHAINS;
2100 lzx_params->mf_algo = LZ_MF_BINARY_TREES;
2102 /* When doing near-optimal parsing, allow length 2 matches if
2103 * the compression level is sufficiently high. */
2104 if (compression_level >= 45)
2105 lzx_params->min_match_length = 2;
2107 lzx_params->min_match_length = 3;
2109 /* Scale nice_match_length and max_search_depth with the
2110 * compression level. */
2111 lzx_params->nice_match_length = min(((u64)compression_level * 32) / 50,
2113 lzx_params->max_search_depth = min(((u64)compression_level * 50) / 50,
2118 /* Given the internal compression parameters and maximum window size, build the
2119 * Lempel-Ziv match-finder parameters. */
2121 lzx_build_mf_params(const struct lzx_compressor_params *lzx_params,
2122 u32 max_window_size, struct lz_mf_params *mf_params)
2124 memset(mf_params, 0, sizeof(*mf_params));
2126 mf_params->algorithm = lzx_params->mf_algo;
2127 mf_params->max_window_size = max_window_size;
2128 mf_params->min_match_len = lzx_params->min_match_length;
2129 mf_params->max_match_len = LZX_MAX_MATCH_LEN;
2130 mf_params->max_search_depth = lzx_params->max_search_depth;
2131 mf_params->nice_match_len = lzx_params->nice_match_length;
2135 lzx_free_compressor(void *_c);
2138 lzx_get_needed_memory(size_t max_block_size, unsigned int compression_level)
2140 struct lzx_compressor_params params;
2142 unsigned window_order;
2143 u32 max_window_size;
2145 window_order = lzx_get_window_order(max_block_size);
2146 if (window_order == 0)
2148 max_window_size = max_block_size;
2150 lzx_build_params(compression_level, max_window_size, ¶ms);
2152 size += sizeof(struct lzx_compressor);
2155 size += max_window_size;
2158 size += lz_mf_get_needed_memory(params.mf_algo, max_window_size);
2160 /* cached_matches */
2161 if (params.num_optim_passes > 1)
2162 size += LZX_CACHE_LEN * sizeof(struct lz_match);
2164 size += LZX_MAX_MATCHES_PER_POS * sizeof(struct lz_match);
2169 lzx_create_compressor(size_t max_block_size, unsigned int compression_level,
2172 struct lzx_compressor *c;
2173 struct lzx_compressor_params params;
2174 struct lz_mf_params mf_params;
2175 unsigned window_order;
2176 u32 max_window_size;
2178 window_order = lzx_get_window_order(max_block_size);
2179 if (window_order == 0)
2180 return WIMLIB_ERR_INVALID_PARAM;
2181 max_window_size = max_block_size;
2183 lzx_build_params(compression_level, max_window_size, ¶ms);
2184 lzx_build_mf_params(¶ms, max_window_size, &mf_params);
2185 if (!lz_mf_params_valid(&mf_params))
2186 return WIMLIB_ERR_INVALID_PARAM;
2188 c = CALLOC(1, sizeof(struct lzx_compressor));
2193 c->num_main_syms = lzx_get_num_main_syms(window_order);
2194 c->window_order = window_order;
2196 /* The window is allocated as 16-byte aligned to speed up memcpy() and
2197 * enable lzx_e8_filter() optimization on x86_64. */
2198 c->cur_window = ALIGNED_MALLOC(max_window_size, 16);
2202 c->mf = lz_mf_alloc(&mf_params);
2206 if (params.num_optim_passes > 1) {
2207 c->cached_matches = MALLOC(LZX_CACHE_LEN *
2208 sizeof(struct lz_match));
2209 if (!c->cached_matches)
2211 c->cache_limit = c->cached_matches + LZX_CACHE_LEN -
2212 (LZX_MAX_MATCHES_PER_POS + 1);
2214 c->cached_matches = MALLOC(LZX_MAX_MATCHES_PER_POS *
2215 sizeof(struct lz_match));
2216 if (!c->cached_matches)
2220 lzx_init_offset_slot_fast(c);
2226 lzx_free_compressor(c);
2227 return WIMLIB_ERR_NOMEM;
2231 lzx_compress(const void *uncompressed_data, size_t uncompressed_size,
2232 void *compressed_data, size_t compressed_size_avail, void *_c)
2234 struct lzx_compressor *c = _c;
2235 struct lzx_output_bitstream os;
2236 u32 num_chosen_items;
2237 const struct lzx_lens *prev_lens;
2238 u32 block_start_pos;
2242 /* Don't bother compressing very small inputs. */
2243 if (uncompressed_size < 100)
2246 /* The input data must be preprocessed. To avoid changing the original
2247 * input data, copy it to a temporary buffer. */
2248 memcpy(c->cur_window, uncompressed_data, uncompressed_size);
2249 c->cur_window_size = uncompressed_size;
2251 /* Preprocess the data. */
2252 lzx_do_e8_preprocessing(c->cur_window, c->cur_window_size);
2254 /* Load the window into the match-finder. */
2255 lz_mf_load_window(c->mf, c->cur_window, c->cur_window_size);
2257 /* Initialize the match offset LRU queue. */
2258 lzx_lru_queue_init(&c->queue);
2260 /* Initialize the output bitstream. */
2261 lzx_init_output(&os, compressed_data, compressed_size_avail);
2263 /* Compress the data block by block.
2265 * TODO: The compression ratio could be slightly improved by performing
2266 * data-dependent block splitting instead of using fixed-size blocks.
2267 * Doing so well is a computationally hard problem, however. */
2268 block_start_pos = 0;
2270 prev_lens = &c->zero_lens;
2272 /* Compute the block size. */
2273 block_size = min(LZX_DIV_BLOCK_SIZE,
2274 uncompressed_size - block_start_pos);
2276 /* Reset symbol frequencies. */
2277 memset(&c->freqs, 0, sizeof(c->freqs));
2279 /* Prepare the matches/literals for the block. */
2280 num_chosen_items = lzx_choose_items_for_block(c,
2284 /* Make the Huffman codes from the symbol frequencies. */
2285 lzx_make_huffman_codes(&c->freqs, &c->codes[c->codes_index],
2288 /* Choose the best block type.
2290 * Note: we currently don't consider uncompressed blocks. */
2291 block_type = lzx_choose_verbatim_or_aligned(&c->freqs,
2292 &c->codes[c->codes_index]);
2294 /* Write the compressed block to the output buffer. */
2295 lzx_write_compressed_block(block_type,
2301 &c->codes[c->codes_index],
2305 /* The current codeword lengths become the previous lengths. */
2306 prev_lens = &c->codes[c->codes_index].lens;
2307 c->codes_index ^= 1;
2309 block_start_pos += block_size;
2311 } while (block_start_pos != uncompressed_size);
2313 return lzx_flush_output(&os);
2317 lzx_free_compressor(void *_c)
2319 struct lzx_compressor *c = _c;
2322 ALIGNED_FREE(c->cur_window);
2324 FREE(c->cached_matches);
2329 const struct compressor_ops lzx_compressor_ops = {
2330 .get_needed_memory = lzx_get_needed_memory,
2331 .create_compressor = lzx_create_compressor,
2332 .compress = lzx_compress,
2333 .free_compressor = lzx_free_compressor,