A few minor compressor cleanups
[wimlib] / src / lzx-compress.c
1 /*
2  * lzx-compress.c
3  *
4  * A compressor that produces output compatible with the LZX compression format.
5  */
6
7 /*
8  * Copyright (C) 2012, 2013, 2014 Eric Biggers
9  *
10  * This file is part of wimlib, a library for working with WIM files.
11  *
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)
15  * any later version.
16  *
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
20  * details.
21  *
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/.
24  */
25
26
27 /*
28  * This file contains a compressor for the LZX ("Lempel-Ziv eXtended")
29  * compression format, as used in the WIM (Windows IMaging) file format.
30  *
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
34  * compression level.
35  *
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
39  * might be required.
40  *
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:
45  *
46  * - LZX preprocesses the data to attempt to make x86 machine code slightly more
47  *   compressible before attempting to compress it further.
48  *
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).
53  *
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").
57  *
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.
60  *
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.
64  */
65
66 #ifdef HAVE_CONFIG_H
67 #  include "config.h"
68 #endif
69
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"
78
79 #include <string.h>
80 #include <limits.h>
81
82 #define LZX_OPTIM_ARRAY_LENGTH  4096
83
84 #define LZX_DIV_BLOCK_SIZE      32768
85
86 #define LZX_CACHE_PER_POS       8
87
88 #define LZX_MAX_MATCHES_PER_POS (LZX_MAX_MATCH_LEN - LZX_MIN_MATCH_LEN + 1)
89
90 #define LZX_CACHE_LEN (LZX_DIV_BLOCK_SIZE * (LZX_CACHE_PER_POS + 1))
91
92 struct lzx_compressor;
93
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];
99 };
100
101 /* Codeword lengths (in bits) for the LZX Huffman codes.
102  * A zero length means the corresponding codeword has zero frequency.  */
103 struct lzx_lens {
104         u8 main[LZX_MAINCODE_MAX_NUM_SYMBOLS];
105         u8 len[LZX_LENCODE_NUM_SYMBOLS];
106         u8 aligned[LZX_ALIGNEDCODE_NUM_SYMBOLS];
107 };
108
109 /* Estimated cost, in bits, to output each symbol in the LZX Huffman codes.  */
110 struct lzx_costs {
111         u8 main[LZX_MAINCODE_MAX_NUM_SYMBOLS];
112         u8 len[LZX_LENCODE_NUM_SYMBOLS];
113         u8 aligned[LZX_ALIGNEDCODE_NUM_SYMBOLS];
114 };
115
116 /* Codewords and lengths for the LZX Huffman codes.  */
117 struct lzx_codes {
118         struct lzx_codewords codewords;
119         struct lzx_lens lens;
120 };
121
122 /* Symbol frequency counters for the LZX Huffman codes.  */
123 struct lzx_freqs {
124         u32 main[LZX_MAINCODE_MAX_NUM_SYMBOLS];
125         u32 len[LZX_LENCODE_NUM_SYMBOLS];
126         u32 aligned[LZX_ALIGNEDCODE_NUM_SYMBOLS];
127 };
128
129 /* Intermediate LZX match/literal format  */
130 struct lzx_item {
131
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  */
136         u64 data;
137 };
138
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;
147 };
148
149 /*
150  * Match chooser position data:
151  *
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.
156  */
157 struct lzx_mc_pos_data {
158
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.  */
162         u32 cost;
163 #define MC_INFINITE_COST UINT32_MAX
164
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
167          * position.
168          *
169          * This variable is divided into two bitfields.
170          *
171          * Literals:
172          *      Low bits are 1, high bits are the literal.
173          *
174          * Explicit offset matches:
175          *      Low bits are the match length, high bits are the offset plus 2.
176          *
177          * Repeat offset matches:
178          *      Low bits are the match length, high bits are the queue index.
179          */
180         u32 mc_item_data;
181 #define MC_OFFSET_SHIFT 9
182 #define MC_LEN_MASK ((1 << MC_OFFSET_SHIFT) - 1)
183
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
186          * position is found.
187          *
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);
197
198 } _aligned_attribute(16);
199
200 /* State of the LZX compressor  */
201 struct lzx_compressor {
202
203         /* Internal compression parameters  */
204         struct lzx_compressor_params params;
205
206         /* The preprocessed buffer of data being compressed  */
207         u8 *cur_window;
208
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.  */
211         u32 cur_window_size;
212
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.
216          *
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;
222
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 <<
227          * @window_order.  */
228         unsigned num_main_syms;
229
230         /* Lempel-Ziv match-finder  */
231         struct lz_mf *mf;
232
233         /* Match-finder wrapper functions and data for near-optimal parsing.
234          *
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;
247
248         /* Position data for near-optimal parsing.  */
249         struct lzx_mc_pos_data optimum[LZX_OPTIM_ARRAY_LENGTH + LZX_MAX_MATCH_LEN];
250
251         /* The cost model currently being used for near-optimal parsing.  */
252         struct lzx_costs costs;
253
254         /* The current match offset LRU queue.  */
255         struct lzx_lru_queue queue;
256
257         /* Frequency counters for the current block.  */
258         struct lzx_freqs freqs;
259
260         /* The Huffman codes for the current and previous blocks.  */
261         struct lzx_codes codes[2];
262
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
265          * block).  */
266         unsigned int codes_index;
267
268         /* Dummy lengths that are always 0.  */
269         struct lzx_lens zero_lens;
270
271         /* Matches/literals that were chosen for the current block.  */
272         struct lzx_item chosen_items[LZX_DIV_BLOCK_SIZE];
273
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];
277 };
278
279 /*
280  * Structure to keep track of the current state of sending bits to the
281  * compressed output buffer.
282  *
283  * The LZX bitstream is encoded as a sequence of 16-bit coding units.
284  */
285 struct lzx_output_bitstream {
286
287         /* Bits that haven't yet been written to the output buffer.  */
288         u32 bitbuf;
289
290         /* Number of bits currently held in @bitbuf.  */
291         u32 bitcount;
292
293         /* Pointer to the start of the output buffer.  */
294         le16 *start;
295
296         /* Pointer to the position in the output buffer at which the next coding
297          * unit should be written.  */
298         le16 *next;
299
300         /* Pointer past the end of the output buffer.  */
301         le16 *end;
302 };
303
304 /*
305  * Initialize the output bitstream.
306  *
307  * @os
308  *      The output bitstream structure to initialize.
309  * @buffer
310  *      The buffer being written to.
311  * @size
312  *      Size of @buffer, in bytes.
313  */
314 static void
315 lzx_init_output(struct lzx_output_bitstream *os, void *buffer, u32 size)
316 {
317         os->bitbuf = 0;
318         os->bitcount = 0;
319         os->start = buffer;
320         os->next = os->start;
321         os->end = os->start + size / sizeof(le16);
322 }
323
324 /*
325  * Write some bits to the output bitstream.
326  *
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.
329  *
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.
334  *
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.
337  */
338 static inline void
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)
342 {
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);
348
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;
354
355         /* Check whether any coding units need to be written.  */
356         if (os->bitcount >= 16) {
357
358                 os->bitcount -= 16;
359
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);
363
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
367                  * call sites.  */
368                 if (max_num_bits == 17 && os->bitcount == 16) {
369                         if (os->next != os->end)
370                                 *os->next++ = cpu_to_le16(os->bitbuf);
371                         os->bitcount = 0;
372                 }
373         }
374 }
375
376 /* Use when @num_bits is a compile-time constant.  Otherwise use
377  * lzx_write_varbits().  */
378 static inline void
379 lzx_write_bits(struct lzx_output_bitstream *os,
380                const u32 bits, const unsigned int num_bits)
381 {
382         lzx_write_varbits(os, bits, num_bits, num_bits);
383 }
384
385 /*
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.
388  */
389 static u32
390 lzx_flush_output(struct lzx_output_bitstream *os)
391 {
392         if (os->next == os->end)
393                 return 0;
394
395         if (os->bitcount != 0)
396                 *os->next++ = cpu_to_le16(os->bitbuf << (16 - os->bitcount));
397
398         return (const u8 *)os->next - (const u8 *)os->start;
399 }
400
401 /* Build the main, length, and aligned offset Huffman codes used in LZX.
402  *
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.  */
405 static void
406 lzx_make_huffman_codes(const struct lzx_freqs *freqs, struct lzx_codes *codes,
407                        unsigned num_main_syms)
408 {
409         make_canonical_huffman_code(num_main_syms,
410                                     LZX_MAX_MAIN_CODEWORD_LEN,
411                                     freqs->main,
412                                     codes->lens.main,
413                                     codes->codewords.main);
414
415         make_canonical_huffman_code(LZX_LENCODE_NUM_SYMBOLS,
416                                     LZX_MAX_LEN_CODEWORD_LEN,
417                                     freqs->len,
418                                     codes->lens.len,
419                                     codes->codewords.len);
420
421         make_canonical_huffman_code(LZX_ALIGNEDCODE_NUM_SYMBOLS,
422                                     LZX_MAX_ALIGNED_CODEWORD_LEN,
423                                     freqs->aligned,
424                                     codes->lens.aligned,
425                                     codes->codewords.aligned);
426 }
427
428 static unsigned
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])
434 {
435         unsigned *itemptr;
436         unsigned run_start;
437         unsigned run_end;
438         unsigned extra_bits;
439         int delta;
440         u8 len;
441
442         itemptr = precode_items;
443         run_start = 0;
444         do {
445                 /* Find the next run of codeword lengths.  */
446
447                 /* len = the length being repeated  */
448                 len = lens[run_start];
449
450                 run_end = run_start + 1;
451
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;
455                         if (delta < 0)
456                                 delta += 17;
457                         precode_freqs[delta]++;
458                         *itemptr++ = delta;
459                         run_start++;
460                         continue;
461                 }
462
463                 /* Extend the run.  */
464                 do {
465                         run_end++;
466                 } while (run_end != num_lens && len == lens[run_end]);
467
468                 if (len == 0) {
469                         /* Run of zeroes.  */
470
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);
474                                 precode_freqs[18]++;
475                                 *itemptr++ = 18 | (extra_bits << 5);
476                                 run_start += 20 + extra_bits;
477                         }
478
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);
482                                 precode_freqs[17]++;
483                                 *itemptr++ = 17 | (extra_bits << 5);
484                                 run_start += 4 + extra_bits;
485                         }
486                 } else {
487
488                         /* A run of nonzero lengths. */
489
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;
494                                 if (delta < 0)
495                                         delta += 17;
496                                 precode_freqs[19]++;
497                                 precode_freqs[delta]++;
498                                 *itemptr++ = 19 | (extra_bits << 5) | (delta << 6);
499                                 run_start += 4 + extra_bits;
500                         }
501                 }
502
503                 /* Output any remaining lengths without RLE.  */
504                 while (run_start != run_end) {
505                         delta = prev_lens[run_start] - len;
506                         if (delta < 0)
507                                 delta += 17;
508                         precode_freqs[delta]++;
509                         *itemptr++ = delta;
510                         run_start++;
511                 }
512         } while (run_start != num_lens);
513
514         return itemptr - precode_items;
515 }
516
517 /*
518  * Output a Huffman code in the compressed form used in LZX.
519  *
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
522  * reconstructed.
523  *
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.
531  *
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
534  * block.
535  *
536  * @os:
537  *      Bitstream to which to write the compressed Huffman code.
538  * @lens:
539  *      The codeword lengths, indexed by symbol, in the Huffman code.
540  * @prev_lens:
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.
543  * @num_lens:
544  *      The number of symbols in the Huffman code.
545  */
546 static void
547 lzx_write_compressed_code(struct lzx_output_bitstream *os,
548                           const u8 lens[restrict],
549                           const u8 prev_lens[restrict],
550                           unsigned num_lens)
551 {
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;
559         unsigned i;
560
561         for (i = 0; i < LZX_PRECODE_NUM_SYMBOLS; i++)
562                 precode_freqs[i] = 0;
563
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,
567                                                       prev_lens,
568                                                       num_lens,
569                                                       precode_freqs,
570                                                       precode_items);
571
572         /* Build the precode.  */
573         make_canonical_huffman_code(LZX_PRECODE_NUM_SYMBOLS,
574                                     LZX_MAX_PRE_CODEWORD_LEN,
575                                     precode_freqs, precode_lens,
576                                     precode_codewords);
577
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);
581
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);
594                         } else {
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);
600                         }
601                 }
602         }
603 }
604
605 /* Output a match or literal.  */
606 static inline void
607 lzx_write_item(struct lzx_output_bitstream *os, struct lzx_item item,
608                unsigned ones_if_aligned, const struct lzx_codes *codes)
609 {
610         u64 data = item.data;
611         unsigned main_symbol;
612         unsigned len_symbol;
613         unsigned num_extra_bits;
614         u32 extra_bits;
615
616         main_symbol = data & 0x3FF;
617
618         lzx_write_varbits(os, codes->codewords.main[main_symbol],
619                           codes->lens.main[main_symbol],
620                           LZX_MAX_MAIN_CODEWORD_LEN);
621
622         if (main_symbol < LZX_NUM_CHARS)  /* Literal?  */
623                 return;
624
625         len_symbol = (data >> 10) & 0xFF;
626
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);
631         }
632
633         num_extra_bits = (data >> 18) & 0x1F;
634         if (num_extra_bits == 0)  /* Small offset or repeat offset match?  */
635                 return;
636
637         extra_bits = data >> 23;
638
639         /*if (block_type == LZX_BLOCKTYPE_ALIGNED && num_extra_bits >= 3) {*/
640         if ((num_extra_bits & ones_if_aligned) >= 3) {
641
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.  */
645
646                 lzx_write_varbits(os, extra_bits >> 3, num_extra_bits - 3, 14);
647
648                 lzx_write_varbits(os, codes->codewords.aligned[extra_bits & 7],
649                                   codes->lens.aligned[extra_bits & 7],
650                                   LZX_MAX_ALIGNED_CODEWORD_LEN);
651         } else {
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);
655         }
656 }
657
658 /*
659  * Write all matches and literal bytes (which were precomputed) in an LZX
660  * compressed block to the output bitstream in the final compressed
661  * representation.
662  *
663  * @os
664  *      The output bitstream.
665  * @block_type
666  *      The chosen type of the LZX compressed block (LZX_BLOCKTYPE_ALIGNED or
667  *      LZX_BLOCKTYPE_VERBATIM).
668  * @items
669  *      The array of matches/literals to output.
670  * @num_items
671  *      Number of matches/literals to output (length of @items).
672  * @codes
673  *      The main, length, and aligned offset Huffman codes for the current
674  *      LZX compressed block.
675  */
676 static void
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)
680 {
681         unsigned ones_if_aligned = 0U - (block_type == LZX_BLOCKTYPE_ALIGNED);
682
683         for (u32 i = 0; i < num_items; i++)
684                 lzx_write_item(os, items[i], ones_if_aligned, codes);
685 }
686
687 /* Write an LZX aligned offset or verbatim block to the output bitstream.  */
688 static void
689 lzx_write_compressed_block(int block_type,
690                            u32 block_size,
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)
698 {
699         LZX_ASSERT(block_type == LZX_BLOCKTYPE_ALIGNED ||
700                    block_type == LZX_BLOCKTYPE_VERBATIM);
701
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);
705
706         /* Output the block size.
707          *
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.
712          *
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);
723         } else {
724                 lzx_write_bits(os, 0, 1);
725
726                 if (window_order >= 16)
727                         lzx_write_bits(os, block_size >> 16, 8);
728
729                 lzx_write_bits(os, block_size & 0xFFFF, 16);
730         }
731
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);
737                 }
738         }
739
740         /* Output the main code (two parts).  */
741         lzx_write_compressed_code(os, codes->lens.main,
742                                   prev_lens->main,
743                                   LZX_NUM_CHARS);
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);
747
748         /* Output the length code.  */
749         lzx_write_compressed_code(os, codes->lens.len,
750                                   prev_lens->len,
751                                   LZX_LENCODE_NUM_SYMBOLS);
752
753         /* Output the compressed matches and literals.  */
754         lzx_write_items(os, block_type, chosen_items, num_chosen_items, codes);
755 }
756
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)
761 {
762         if (c->match_window_end < c->cur_window_size && num_matches != 0) {
763                 u32 limit = c->match_window_end - c->match_window_pos;
764
765                 if (limit >= LZX_MIN_MATCH_LEN) {
766
767                         unsigned i = num_matches - 1;
768                         do {
769                                 if (matches[i].len >= limit) {
770                                         matches[i].len = limit;
771
772                                         /* Truncation might produce multiple
773                                          * matches with length 'limit'.  Keep at
774                                          * most 1.  */
775                                         num_matches = i + 1;
776                                 }
777                         } while (i--);
778                 } else {
779                         num_matches = 0;
780                 }
781         }
782         return num_matches;
783 }
784
785 static unsigned
786 lzx_get_matches_fillcache_singleblock(struct lzx_compressor *c,
787                                       const struct lz_match **matches_ret)
788 {
789         struct lz_match *cache_ptr;
790         struct lz_match *matches;
791         unsigned num_matches;
792
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;
799         } else {
800                 num_matches = 0;
801         }
802         c->match_window_pos++;
803         *matches_ret = matches;
804         return num_matches;
805 }
806
807 static unsigned
808 lzx_get_matches_fillcache_multiblock(struct lzx_compressor *c,
809                                      const struct lz_match **matches_ret)
810 {
811         struct lz_match *cache_ptr;
812         struct lz_match *matches;
813         unsigned num_matches;
814
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;
822         } else {
823                 num_matches = 0;
824         }
825         c->match_window_pos++;
826         *matches_ret = matches;
827         return num_matches;
828 }
829
830 static unsigned
831 lzx_get_matches_usecache(struct lzx_compressor *c,
832                          const struct lz_match **matches_ret)
833 {
834         struct lz_match *cache_ptr;
835         struct lz_match *matches;
836         unsigned num_matches;
837
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;
843         } else {
844                 num_matches = 0;
845         }
846         c->match_window_pos++;
847         *matches_ret = matches;
848         return num_matches;
849 }
850
851 static unsigned
852 lzx_get_matches_usecache_nocheck(struct lzx_compressor *c,
853                                  const struct lz_match **matches_ret)
854 {
855         struct lz_match *cache_ptr;
856         struct lz_match *matches;
857         unsigned num_matches;
858
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;
865         return num_matches;
866 }
867
868 static unsigned
869 lzx_get_matches_nocache_singleblock(struct lzx_compressor *c,
870                                     const struct lz_match **matches_ret)
871 {
872         struct lz_match *matches;
873         unsigned num_matches;
874
875         matches = c->cache_ptr;
876         num_matches = lz_mf_get_matches(c->mf, matches);
877         c->match_window_pos++;
878         *matches_ret = matches;
879         return num_matches;
880 }
881
882 static unsigned
883 lzx_get_matches_nocache_multiblock(struct lzx_compressor *c,
884                                    const struct lz_match **matches_ret)
885 {
886         struct lz_match *matches;
887         unsigned num_matches;
888
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;
894         return num_matches;
895 }
896
897 /*
898  * Find matches at the next position in the window.
899  *
900  * This uses a wrapper function around the underlying match-finder.
901  *
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
904  * offset.
905  */
906 static inline unsigned
907 lzx_get_matches(struct lzx_compressor *c, const struct lz_match **matches_ret)
908 {
909         return (*c->get_matches_func)(c, matches_ret);
910 }
911
912 static void
913 lzx_skip_bytes_fillcache(struct lzx_compressor *c, unsigned n)
914 {
915         struct lz_match *cache_ptr;
916
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) {
921                 do {
922                         cache_ptr->len = 0;
923                         cache_ptr += 1;
924                 } while (--n && cache_ptr <= c->cache_limit);
925         }
926         c->cache_ptr = cache_ptr;
927 }
928
929 static void
930 lzx_skip_bytes_usecache(struct lzx_compressor *c, unsigned n)
931 {
932         struct lz_match *cache_ptr;
933
934         cache_ptr = c->cache_ptr;
935         c->match_window_pos += n;
936         if (cache_ptr <= c->cache_limit) {
937                 do {
938                         cache_ptr += 1 + cache_ptr->len;
939                 } while (--n && cache_ptr <= c->cache_limit);
940         }
941         c->cache_ptr = cache_ptr;
942 }
943
944 static void
945 lzx_skip_bytes_usecache_nocheck(struct lzx_compressor *c, unsigned n)
946 {
947         struct lz_match *cache_ptr;
948
949         cache_ptr = c->cache_ptr;
950         c->match_window_pos += n;
951         do {
952                 cache_ptr += 1 + cache_ptr->len;
953         } while (--n);
954         c->cache_ptr = cache_ptr;
955 }
956
957 static void
958 lzx_skip_bytes_nocache(struct lzx_compressor *c, unsigned n)
959 {
960         c->match_window_pos += n;
961         lz_mf_skip_positions(c->mf, n);
962 }
963
964 /*
965  * Skip the specified number of positions in the window (don't search for
966  * matches at them).
967  *
968  * This uses a wrapper function around the underlying match-finder.
969  */
970 static inline void
971 lzx_skip_bytes(struct lzx_compressor *c, unsigned n)
972 {
973         return (*c->skip_bytes_func)(c, n);
974 }
975
976 /* Tally, and optionally record, the specified literal byte.  */
977 static inline void
978 lzx_declare_literal(struct lzx_compressor *c, unsigned literal,
979                     struct lzx_item **next_chosen_item)
980 {
981         unsigned main_symbol = literal;
982
983         c->freqs.main[main_symbol]++;
984
985         if (next_chosen_item) {
986                 *(*next_chosen_item)++ = (struct lzx_item) {
987                         .data = main_symbol,
988                 };
989         }
990 }
991
992 /* Tally, and optionally record, the specified repeat offset match.  */
993 static inline void
994 lzx_declare_repeat_offset_match(struct lzx_compressor *c,
995                                 unsigned len, unsigned rep_index,
996                                 struct lzx_item **next_chosen_item)
997 {
998         unsigned len_header;
999         unsigned main_symbol;
1000         unsigned len_symbol;
1001
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;
1005         } else {
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]++;
1009         }
1010
1011         main_symbol = LZX_NUM_CHARS + ((rep_index << 3) | len_header);
1012
1013         c->freqs.main[main_symbol]++;
1014
1015         if (next_chosen_item) {
1016                 *(*next_chosen_item)++ = (struct lzx_item) {
1017                         .data = (u64)main_symbol | ((u64)len_symbol << 10),
1018                 };
1019         }
1020 }
1021
1022 /* Tally, and optionally record, the specified explicit offset match.  */
1023 static inline void
1024 lzx_declare_explicit_offset_match(struct lzx_compressor *c, unsigned len, u32 offset,
1025                                   struct lzx_item **next_chosen_item)
1026 {
1027         unsigned len_header;
1028         unsigned main_symbol;
1029         unsigned len_symbol;
1030         unsigned offset_slot;
1031         unsigned num_extra_bits;
1032         u32 extra_bits;
1033
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;
1037         } else {
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]++;
1041         }
1042
1043         offset_slot = lzx_get_offset_slot_raw(offset + LZX_OFFSET_OFFSET);
1044
1045         main_symbol = LZX_NUM_CHARS + ((offset_slot << 3) | len_header);
1046
1047         c->freqs.main[main_symbol]++;
1048
1049         if (offset_slot >= 8)
1050                 c->freqs.aligned[(offset + LZX_OFFSET_OFFSET) & 7]++;
1051
1052         if (next_chosen_item) {
1053
1054                 num_extra_bits = lzx_extra_offset_bits[offset_slot];
1055
1056                 extra_bits = (offset + LZX_OFFSET_OFFSET) -
1057                              lzx_offset_slot_base[offset_slot];
1058
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),
1064                 };
1065         }
1066 }
1067
1068 /* Tally, and optionally record, the specified match or literal.  */
1069 static inline void
1070 lzx_declare_item(struct lzx_compressor *c, u32 mc_item_data,
1071                  struct lzx_item **next_chosen_item)
1072 {
1073         u32 len = mc_item_data & MC_LEN_MASK;
1074         u32 offset_data = mc_item_data >> MC_OFFSET_SHIFT;
1075
1076         if (len == 1)
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,
1080                                                 next_chosen_item);
1081         else
1082                 lzx_declare_explicit_offset_match(c, len,
1083                                                   offset_data - LZX_OFFSET_OFFSET,
1084                                                   next_chosen_item);
1085 }
1086
1087 static inline void
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)
1091 {
1092         struct lzx_mc_pos_data *end_optimum_ptr;
1093         u32 saved_item;
1094         u32 item;
1095
1096         /* The list is currently in reverse order (last item to first item).
1097          * Reverse it.  */
1098         end_optimum_ptr = cur_optimum_ptr;
1099         saved_item = cur_optimum_ptr->mc_item_data;
1100         do {
1101                 item = saved_item;
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);
1106
1107         /* Walk the list of items from beginning to end, tallying and recording
1108          * each item.  */
1109         do {
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);
1113 }
1114
1115 static inline void
1116 lzx_tally_item_list(struct lzx_compressor *c, struct lzx_mc_pos_data *cur_optimum_ptr)
1117 {
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.  */
1120         do {
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);
1124 }
1125
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.  */
1128 static void
1129 lzx_declare_item_list(struct lzx_compressor *c, struct lzx_mc_pos_data *cur_optimum_ptr,
1130                       struct lzx_item **next_chosen_item)
1131 {
1132         if (next_chosen_item)
1133                 lzx_record_item_list(c, cur_optimum_ptr, next_chosen_item);
1134         else
1135                 lzx_tally_item_list(c, cur_optimum_ptr);
1136 }
1137
1138 /* Set the cost model @c->costs from the Huffman codeword lengths specified in
1139  * @lens.
1140  *
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
1146  * to be rare.  */
1147 static void
1148 lzx_set_costs(struct lzx_compressor *c, const struct lzx_lens * lens)
1149 {
1150         unsigned i;
1151
1152         /* Main code  */
1153         for (i = 0; i < c->num_main_syms; i++)
1154                 c->costs.main[i] = lens->main[i] ? lens->main[i] : 15;
1155
1156         /* Length code  */
1157         for (i = 0; i < LZX_LENCODE_NUM_SYMBOLS; i++)
1158                 c->costs.len[i] = lens->len[i] ? lens->len[i] : 15;
1159
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;
1163 }
1164
1165 /* Set default LZX Huffman symbol costs to bootstrap the iterative optimization
1166  * algorithm.  */
1167 static void
1168 lzx_set_default_costs(struct lzx_costs * costs, unsigned num_main_syms)
1169 {
1170         unsigned i;
1171
1172         /* Main code (part 1): Literal symbols  */
1173         for (i = 0; i < LZX_NUM_CHARS; i++)
1174                 costs->main[i] = 8;
1175
1176         /* Main code (part 2): Match header symbols  */
1177         for (; i < num_main_syms; i++)
1178                 costs->main[i] = 10;
1179
1180         /* Length code  */
1181         for (i = 0; i < LZX_LENCODE_NUM_SYMBOLS; i++)
1182                 costs->len[i] = 8;
1183
1184         /* Aligned offset code  */
1185         for (i = 0; i < LZX_ALIGNEDCODE_NUM_SYMBOLS; i++)
1186                 costs->aligned[i] = 3;
1187 }
1188
1189 /* Return the cost, in bits, to output a literal byte using the specified cost
1190  * model.  */
1191 static inline u32
1192 lzx_literal_cost(unsigned literal, const struct lzx_costs * costs)
1193 {
1194         return costs->main[literal];
1195 }
1196
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.  */
1200 static inline u32
1201 lzx_match_cost_raw(unsigned len, unsigned offset_slot,
1202                    const struct lzx_costs *costs)
1203 {
1204         u32 cost;
1205         unsigned len_header;
1206         unsigned main_symbol;
1207
1208         if (len - LZX_MIN_MATCH_LEN < LZX_NUM_PRIMARY_LENS) {
1209                 len_header = len - LZX_MIN_MATCH_LEN;
1210                 cost = 0;
1211         } else {
1212                 len_header = LZX_NUM_PRIMARY_LENS;
1213
1214                 /* Account for length symbol.  */
1215                 cost = costs->len[len - LZX_MIN_MATCH_LEN - LZX_NUM_PRIMARY_LENS];
1216         }
1217
1218         /* Account for main symbol.  */
1219         main_symbol = LZX_NUM_CHARS + ((offset_slot << 3) | len_header);
1220         cost += costs->main[main_symbol];
1221
1222         return cost;
1223 }
1224
1225 /* Equivalent to lzx_match_cost_raw(), but assumes the length is small enough
1226  * that it doesn't require a length symbol.  */
1227 static inline u32
1228 lzx_match_cost_raw_smalllen(unsigned len, unsigned offset_slot,
1229                             const struct lzx_costs *costs)
1230 {
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))];
1234 }
1235
1236 /*
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).
1239  */
1240 static inline void
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)
1244 {
1245         u32 base_cost = cur_optimum_ptr->cost;
1246         u32 cost;
1247         unsigned len;
1248
1249 #if 1   /* Optimized version */
1250
1251         if (rep_len < LZX_MIN_MATCH_LEN + LZX_NUM_PRIMARY_LENS) {
1252                 /* All lengths being considered are small.  */
1253                 len = 2;
1254                 do {
1255                         cost = base_cost +
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;
1261                         }
1262                 } while (++len <= rep_len);
1263         } else {
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.  */
1267                 len = 2;
1268                 do {
1269                         cost = base_cost +
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;
1275                         }
1276                 } while (++len < LZX_MIN_MATCH_LEN + LZX_NUM_PRIMARY_LENS);
1277
1278                 /* The main symbol is now fixed.  */
1279                 base_cost += c->costs.main[LZX_NUM_CHARS +
1280                                            ((rep_idx << 3) | LZX_NUM_PRIMARY_LENS)];
1281                 do {
1282                         cost = base_cost +
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;
1289                         }
1290                 } while (++len <= rep_len);
1291         }
1292
1293 #else   /* Unoptimized version  */
1294
1295         len = 2;
1296         do {
1297                 cost = base_cost +
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;
1303                 }
1304         } while (++len <= rep_len);
1305 #endif
1306 }
1307
1308 /*
1309  * Consider coding each match in @matches as an explicit offset match.
1310  *
1311  * @matches must be sorted by strictly increasing length and strictly
1312  * increasing offset.  This is guaranteed by the match-finder.
1313  *
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.
1320  */
1321 static inline void
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)
1326 {
1327         LZX_ASSERT(num_matches > 0);
1328
1329         unsigned i;
1330         unsigned len;
1331         unsigned offset_slot;
1332         u32 position_cost;
1333         u32 cost;
1334         u32 offset_data;
1335
1336
1337 #if 1   /* Optimized version */
1338
1339         if (matches[num_matches - 1].offset < LZX_NUM_FAST_OFFSETS) {
1340
1341                 /*
1342                  * Offset is small; the offset slot can be looked up directly in
1343                  * c->offset_slot_fast.
1344                  *
1345                  * Additional optimizations:
1346                  *
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.
1350                  *
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.
1354                  *
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.
1358                  */
1359
1360                 LZX_ASSERT(offset_slot <= 37); /* for extra bits formula  */
1361
1362                 len = 2;
1363                 i = 0;
1364                 do {
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;
1369                         do {
1370                                 if (len >= LZX_MIN_MATCH_LEN + LZX_NUM_PRIMARY_LENS)
1371                                         goto biglen;
1372                                 cost = position_cost +
1373                                        lzx_match_cost_raw_smalllen(len, offset_slot,
1374                                                                    &c->costs);
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;
1379                                 }
1380                         } while (++len <= matches[i].len);
1381                 } while (++i != num_matches);
1382
1383                 return;
1384
1385                 do {
1386                         offset_slot = c->offset_slot_fast[matches[i].offset];
1387         biglen:
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;
1394                         do {
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;
1402                                 }
1403                         } while (++len <= matches[i].len);
1404                 } while (++i != num_matches);
1405         } else {
1406                 len = 2;
1407                 i = 0;
1408                 do {
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];
1413                         do {
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;
1420                                 }
1421                         } while (++len <= matches[i].len);
1422                 } while (++i != num_matches);
1423         }
1424
1425 #else   /* Unoptimized version */
1426
1427         unsigned num_extra_bits;
1428
1429         len = 2;
1430         i = 0;
1431         do {
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];
1439                 } else {
1440                         position_cost += num_extra_bits;
1441                 }
1442                 do {
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;
1449                         }
1450                 } while (++len <= matches[i].len);
1451         } while (++i != num_matches);
1452 #endif
1453 }
1454
1455 /*
1456  * Search for repeat offset matches with the current position.
1457  */
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)
1461 {
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);
1465 }
1466
1467 /*
1468  * The main near-optimal parsing routine.
1469  *
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.
1481  *
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].
1484  *
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.
1487  *
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.
1490  *
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).
1494  */
1495 static void
1496 lzx_optim_pass(struct lzx_compressor *c, struct lzx_item **next_chosen_item)
1497 {
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;
1508         unsigned literal;
1509         unsigned len;
1510         u32 cost;
1511         u32 offset_data;
1512
1513         block_end = &c->cur_window[c->match_window_end];
1514         begin_queue = &c->queue;
1515 begin:
1516         /* Start building a new list of items, which will correspond to the next
1517          * piece of the overall minimum-cost path.
1518          *
1519          * *begin_queue is the current state of the match offset LRU queue.  */
1520
1521         window_ptr = &c->cur_window[c->match_window_pos];
1522
1523         if (window_ptr == block_end) {
1524                 c->queue = *begin_queue;
1525                 return;
1526         }
1527
1528         cur_optimum_ptr = c->optimum;
1529         cur_optimum_ptr->cost = 0;
1530         cur_optimum_ptr->queue = *begin_queue;
1531
1532         end_optimum_ptr = cur_optimum_ptr;
1533
1534         /* The following loop runs once for each per byte in the window, except
1535          * in a couple shortcut cases.  */
1536         for (;;) {
1537
1538                 /* Find explicit offset matches with the current position.  */
1539                 num_matches = lzx_get_matches(c, &matches);
1540
1541                 if (num_matches) {
1542                         /*
1543                          * Find the longest repeat offset match with the current
1544                          * position.
1545                          *
1546                          * Heuristics:
1547                          *
1548                          * - Only search for repeat offset matches if the
1549                          *   match-finder already found at least one match.
1550                          *
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).
1556                          */
1557                         rep_max_len = lzx_repsearch(window_ptr,
1558                                                     block_end - window_ptr,
1559                                                     &cur_optimum_ptr->queue,
1560                                                     &rep_max_idx);
1561
1562                         if (rep_max_len) {
1563                                 /* If there's a very long repeat offset match,
1564                                  * choose it immediately.  */
1565                                 if (rep_max_len >= c->params.nice_match_length) {
1566
1567                                         swap(cur_optimum_ptr->queue.R[0],
1568                                              cur_optimum_ptr->queue.R[rep_max_idx]);
1569                                         begin_queue = &cur_optimum_ptr->queue;
1570
1571                                         cur_optimum_ptr += rep_max_len;
1572                                         cur_optimum_ptr->mc_item_data =
1573                                                 (rep_max_idx << MC_OFFSET_SHIFT) |
1574                                                 rep_max_len;
1575
1576                                         lzx_skip_bytes(c, rep_max_len - 1);
1577                                         break;
1578                                 }
1579
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;
1584
1585                                 /* Consider coding a repeat offset match.  */
1586                                 lzx_consider_repeat_offset_match(c,
1587                                                                  cur_optimum_ptr,
1588                                                                  rep_max_len,
1589                                                                  rep_max_idx);
1590                         }
1591
1592                         longest_len = matches[num_matches - 1].len;
1593
1594                         /* If there's a very long explicit offset match, choose
1595                          * it immediately.  */
1596                         if (longest_len >= c->params.nice_match_length) {
1597
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;
1605
1606                                 offset_data = matches[num_matches - 1].offset +
1607                                               LZX_OFFSET_OFFSET;
1608                                 cur_optimum_ptr += longest_len;
1609                                 cur_optimum_ptr->mc_item_data =
1610                                         (offset_data << MC_OFFSET_SHIFT) |
1611                                         longest_len;
1612
1613                                 lzx_skip_bytes(c, longest_len - 1);
1614                                 break;
1615                         }
1616
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;
1621
1622                         /* Consider coding an explicit offset match.  */
1623                         lzx_consider_explicit_offset_matches(c, cur_optimum_ptr,
1624                                                              matches, num_matches);
1625                 } else {
1626                         /* No matches found.  The only choice at this position
1627                          * is to code a literal.  */
1628
1629                         if (end_optimum_ptr == cur_optimum_ptr) {
1630                         #if 1
1631                                 /* Optimization for single literals.  */
1632                                 if (likely(cur_optimum_ptr == c->optimum)) {
1633                                         lzx_declare_literal(c, *window_ptr++,
1634                                                             next_chosen_item);
1635                                         if (window_ptr == block_end) {
1636                                                 c->queue = cur_optimum_ptr->queue;
1637                                                 return;
1638                                         }
1639                                         continue;
1640                                 }
1641                         #endif
1642                                 (++end_optimum_ptr)->cost = MC_INFINITE_COST;
1643                         }
1644                 }
1645
1646                 /* Consider coding a literal.
1647
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);
1653
1654                 /* Advance to the next position.  */
1655                 cur_optimum_ptr++;
1656
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.  */
1660
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;
1666                 } else {
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];
1675                         } else {
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]);
1680                         }
1681                 }
1682
1683                 /*
1684                  * This loop will terminate when either of the following
1685                  * conditions is true:
1686                  *
1687                  * (1) cur_optimum_ptr == end_optimum_ptr
1688                  *
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
1693                  *      position.
1694                  *
1695                  * (2) cur_optimum_ptr == &c->optimum[LZX_OPTIM_ARRAY_LENGTH]
1696                  *
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.
1702                  *
1703                  * Note: no check for end-of-block is needed because
1704                  * end-of-block will trigger condition (1).
1705                  */
1706                 if (cur_optimum_ptr == end_optimum_ptr ||
1707                     cur_optimum_ptr == &c->optimum[LZX_OPTIM_ARRAY_LENGTH])
1708                 {
1709                         begin_queue = &cur_optimum_ptr->queue;
1710                         break;
1711                 }
1712         }
1713
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);
1717         goto begin;
1718 }
1719
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)
1723 {
1724         unsigned score = len;
1725
1726         if (adjusted_offset < 2048)
1727                 score++;
1728
1729         if (adjusted_offset < 1024)
1730                 score++;
1731
1732         return score;
1733 }
1734
1735 static inline unsigned
1736 lzx_repeat_offset_match_score(unsigned len, unsigned slot)
1737 {
1738         return len + 3;
1739 }
1740
1741 /* Lazy parsing  */
1742 static u32
1743 lzx_choose_lazy_items_for_block(struct lzx_compressor *c,
1744                                 u32 block_start_pos, u32 block_size)
1745 {
1746         const u8 *window_ptr;
1747         const u8 *block_end;
1748         struct lz_mf *mf;
1749         struct lz_match *matches;
1750         unsigned num_matches;
1751         unsigned cur_len;
1752         u32 cur_offset_data;
1753         unsigned cur_score;
1754         unsigned rep_max_len;
1755         unsigned rep_max_idx;
1756         unsigned rep_score;
1757         unsigned prev_len;
1758         unsigned prev_score;
1759         u32 prev_offset_data;
1760         unsigned skip_len;
1761         struct lzx_item *next_chosen_item;
1762
1763         window_ptr = &c->cur_window[block_start_pos];
1764         block_end = window_ptr + block_size;
1765         matches = c->cached_matches;
1766         mf = c->mf;
1767         next_chosen_item = c->chosen_items;
1768
1769         prev_len = 0;
1770         prev_offset_data = 0;
1771         prev_score = 0;
1772
1773         while (window_ptr != block_end) {
1774
1775                 /* Find explicit offset matches with the current position.  */
1776                 num_matches = lz_mf_get_matches(mf, matches);
1777                 window_ptr++;
1778
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]))
1785                 {
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.  */
1789
1790                 no_match_found:
1791
1792                         if (prev_len) {
1793                                 skip_len = prev_len - 2;
1794                                 goto output_prev_match;
1795                         } else {
1796                                 lzx_declare_literal(c, *(window_ptr - 1),
1797                                                     &next_chosen_item);
1798                                 continue;
1799                         }
1800                 }
1801
1802                 /* Find the longest repeat offset match with the current
1803                  * position.  */
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);
1808                 } else {
1809                         rep_max_len = 0;
1810                 }
1811
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);
1815
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)
1820                 {
1821                         cur_len = rep_max_len;
1822                         cur_offset_data = rep_max_idx;
1823                         cur_score = rep_score;
1824                 }
1825
1826                 if (unlikely(cur_len > block_end - (window_ptr - 1))) {
1827                         /* Nearing end of block.  */
1828                         cur_len = block_end - (window_ptr - 1);
1829                         if (cur_len < 3)
1830                                 goto no_match_found;
1831                 }
1832
1833                 if (prev_len == 0 || cur_score > prev_score) {
1834                         /* No previous match, or the current match is better
1835                          * than the previous match.
1836                          *
1837                          * If there's a previous match, then output a literal in
1838                          * its place.
1839                          *
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.  */
1844
1845                         if (prev_len)
1846                                 lzx_declare_literal(c, *(window_ptr - 2), &next_chosen_item);
1847
1848                         prev_len = cur_len;
1849                         prev_offset_data = cur_offset_data;
1850                         prev_score = cur_score;
1851
1852                         if (prev_len >= c->params.nice_match_length) {
1853                                 skip_len = prev_len - 1;
1854                                 goto output_prev_match;
1855                         }
1856                         continue;
1857                 }
1858
1859                 /* Current match is not better than the previous match, so
1860                  * output the previous match.  */
1861
1862                 skip_len = prev_len - 2;
1863
1864         output_prev_match:
1865                 if (prev_offset_data < LZX_NUM_RECENT_OFFSETS) {
1866                         lzx_declare_repeat_offset_match(c, prev_len,
1867                                                         prev_offset_data,
1868                                                         &next_chosen_item);
1869                         swap(c->queue.R[0], c->queue.R[prev_offset_data]);
1870                 } else {
1871                         lzx_declare_explicit_offset_match(c, prev_len,
1872                                                           prev_offset_data - LZX_OFFSET_OFFSET,
1873                                                           &next_chosen_item);
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;
1877                 }
1878                 lz_mf_skip_positions(mf, skip_len);
1879                 window_ptr += skip_len;
1880                 prev_len = 0;
1881         }
1882
1883         return next_chosen_item - c->chosen_items;
1884 }
1885
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.  */
1890 static int
1891 lzx_choose_verbatim_or_aligned(const struct lzx_freqs * freqs,
1892                                const struct lzx_codes * codes)
1893 {
1894         u32 aligned_cost = 0;
1895         u32 verbatim_cost = 0;
1896
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];
1902         }
1903
1904         /* Account for output of the aligned offset code.  */
1905         aligned_cost += LZX_ALIGNEDCODE_ELEMENT_SIZE * LZX_ALIGNEDCODE_NUM_SYMBOLS;
1906
1907         if (aligned_cost < verbatim_cost)
1908                 return LZX_BLOCKTYPE_ALIGNED;
1909         else
1910                 return LZX_BLOCKTYPE_VERBATIM;
1911 }
1912
1913 /* Near-optimal parsing  */
1914 static u32
1915 lzx_choose_near_optimal_items_for_block(struct lzx_compressor *c,
1916                                         u32 block_start_pos, u32 block_size)
1917 {
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;
1922
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;
1927                 else
1928                         c->get_matches_func = lzx_get_matches_fillcache_multiblock;
1929                 c->skip_bytes_func = lzx_skip_bytes_fillcache;
1930         } else {
1931                 if (block_size == c->cur_window_size)
1932                         c->get_matches_func = lzx_get_matches_nocache_singleblock;
1933                 else
1934                         c->get_matches_func = lzx_get_matches_nocache_multiblock;
1935                 c->skip_bytes_func = lzx_skip_bytes_nocache;
1936         }
1937
1938         /* No matches will extend beyond the end of the block.  */
1939         c->match_window_end = block_start_pos + block_size;
1940
1941         /* The first optimization pass will use a default cost model.  Each
1942          * additional optimization pass will use a cost model computed from the
1943          * previous pass.
1944          *
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);
1949
1950         next_chosen_item_ptr = NULL;
1951         orig_queue = c->queue;
1952         do {
1953                 /* Reset the match-finder wrapper.  */
1954                 c->match_window_pos = block_start_pos;
1955                 c->cache_ptr = c->cached_matches;
1956
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;
1961                 }
1962
1963                 /* Choose the items.  */
1964                 lzx_optim_pass(c, next_chosen_item_ptr);
1965
1966                 if (num_passes_remaining > 1) {
1967                         /* This isn't the last pass.  */
1968
1969                         /* Make the Huffman codes from the symbol frequencies.  */
1970                         lzx_make_huffman_codes(&c->freqs, &c->codes[c->codes_index],
1971                                                c->num_main_syms);
1972
1973                         /* Update symbol costs.  */
1974                         lzx_set_costs(c, &c->codes[c->codes_index].lens);
1975
1976                         /* Reset symbol frequencies.  */
1977                         memset(&c->freqs, 0, sizeof(c->freqs));
1978
1979                         /* Reset the match offset LRU queue to what it was at
1980                          * the beginning of the block.  */
1981                         c->queue = orig_queue;
1982
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;
1987                         } else {
1988                                 c->get_matches_func = lzx_get_matches_usecache;
1989                                 c->skip_bytes_func = lzx_skip_bytes_usecache;
1990                         }
1991                 }
1992         } while (--num_passes_remaining);
1993
1994         /* Return the number of items chosen.  */
1995         return next_chosen_item - c->chosen_items;
1996 }
1997
1998 /*
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.
2001  *
2002  * The frequences of the Huffman symbols in the block will be tallied in
2003  * 'c->freqs'.
2004  *
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
2007  * block.
2008  *
2009  * Returns the number of matches/literals that were chosen and written to
2010  * 'c->chosen_items' in the 'struct lzx_item' intermediate representation.
2011  */
2012 static u32
2013 lzx_choose_items_for_block(struct lzx_compressor *c,
2014                            u32 block_start_pos, u32 block_size)
2015 {
2016         return (*c->params.choose_items_for_block)(c, block_start_pos, block_size);
2017 }
2018
2019 /* Initialize c->offset_slot_fast.  */
2020 static void
2021 lzx_init_offset_slot_fast(struct lzx_compressor *c)
2022 {
2023         u8 slot = 0;
2024
2025         for (u32 offset = 0; offset < LZX_NUM_FAST_OFFSETS; offset++) {
2026
2027                 while (offset + LZX_OFFSET_OFFSET >= lzx_offset_slot_base[slot + 1])
2028                         slot++;
2029
2030                 c->offset_slot_fast[offset] = slot;
2031         }
2032 }
2033
2034 /* Set internal compression parameters for the specified compression level and
2035  * maximum window size.  */
2036 static void
2037 lzx_build_params(unsigned int compression_level, u32 max_window_size,
2038                  struct lzx_compressor_params *lzx_params)
2039 {
2040         if (compression_level < 25) {
2041
2042                 /* Fast compression: Use lazy parsing.  */
2043
2044                 lzx_params->choose_items_for_block = lzx_choose_lazy_items_for_block;
2045                 lzx_params->num_optim_passes = 1;
2046
2047                 /* When lazy parsing, the hash chain match-finding algorithm is
2048                  * fastest unless the window is too large.
2049                  *
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;
2054                 else
2055                         lzx_params->mf_algo = LZ_MF_BINARY_TREES;
2056
2057                 /* When lazy parsing, don't bother with length 2 matches.  */
2058                 lzx_params->min_match_length = 3;
2059
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;
2064         } else {
2065
2066                 /* Normal / high compression: Use near-optimal parsing.  */
2067
2068                 lzx_params->choose_items_for_block = lzx_choose_near_optimal_items_for_block;
2069
2070                 /* Set a number of optimization passes appropriate for the
2071                  * compression level.  */
2072
2073                 lzx_params->num_optim_passes = 1;
2074
2075                 if (compression_level >= 40)
2076                         lzx_params->num_optim_passes++;
2077
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++;
2091                 }
2092
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;
2099                 else
2100                         lzx_params->mf_algo = LZ_MF_BINARY_TREES;
2101
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;
2106                 else
2107                         lzx_params->min_match_length = 3;
2108
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,
2112                                                     LZX_MAX_MATCH_LEN);
2113                 lzx_params->max_search_depth = min(((u64)compression_level * 50) / 50,
2114                                                    LZX_MAX_MATCH_LEN);
2115         }
2116 }
2117
2118 /* Given the internal compression parameters and maximum window size, build the
2119  * Lempel-Ziv match-finder parameters.  */
2120 static void
2121 lzx_build_mf_params(const struct lzx_compressor_params *lzx_params,
2122                     u32 max_window_size, struct lz_mf_params *mf_params)
2123 {
2124         memset(mf_params, 0, sizeof(*mf_params));
2125
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;
2132 }
2133
2134 static void
2135 lzx_free_compressor(void *_c);
2136
2137 static u64
2138 lzx_get_needed_memory(size_t max_block_size, unsigned int compression_level)
2139 {
2140         struct lzx_compressor_params params;
2141         u64 size = 0;
2142         unsigned window_order;
2143         u32 max_window_size;
2144
2145         window_order = lzx_get_window_order(max_block_size);
2146         if (window_order == 0)
2147                 return 0;
2148         max_window_size = max_block_size;
2149
2150         lzx_build_params(compression_level, max_window_size, &params);
2151
2152         size += sizeof(struct lzx_compressor);
2153
2154         /* cur_window */
2155         size += max_window_size;
2156
2157         /* mf */
2158         size += lz_mf_get_needed_memory(params.mf_algo, max_window_size);
2159
2160         /* cached_matches */
2161         if (params.num_optim_passes > 1)
2162                 size += LZX_CACHE_LEN * sizeof(struct lz_match);
2163         else
2164                 size += LZX_MAX_MATCHES_PER_POS * sizeof(struct lz_match);
2165         return size;
2166 }
2167
2168 static int
2169 lzx_create_compressor(size_t max_block_size, unsigned int compression_level,
2170                       void **c_ret)
2171 {
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;
2177
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;
2182
2183         lzx_build_params(compression_level, max_window_size, &params);
2184         lzx_build_mf_params(&params, max_window_size, &mf_params);
2185         if (!lz_mf_params_valid(&mf_params))
2186                 return WIMLIB_ERR_INVALID_PARAM;
2187
2188         c = CALLOC(1, sizeof(struct lzx_compressor));
2189         if (!c)
2190                 goto oom;
2191
2192         c->params = params;
2193         c->num_main_syms = lzx_get_num_main_syms(window_order);
2194         c->window_order = window_order;
2195
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);
2199         if (!c->cur_window)
2200                 goto oom;
2201
2202         c->mf = lz_mf_alloc(&mf_params);
2203         if (!c->mf)
2204                 goto oom;
2205
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)
2210                         goto oom;
2211                 c->cache_limit = c->cached_matches + LZX_CACHE_LEN -
2212                                  (LZX_MAX_MATCHES_PER_POS + 1);
2213         } else {
2214                 c->cached_matches = MALLOC(LZX_MAX_MATCHES_PER_POS *
2215                                            sizeof(struct lz_match));
2216                 if (!c->cached_matches)
2217                         goto oom;
2218         }
2219
2220         lzx_init_offset_slot_fast(c);
2221
2222         *c_ret = c;
2223         return 0;
2224
2225 oom:
2226         lzx_free_compressor(c);
2227         return WIMLIB_ERR_NOMEM;
2228 }
2229
2230 static size_t
2231 lzx_compress(const void *uncompressed_data, size_t uncompressed_size,
2232              void *compressed_data, size_t compressed_size_avail, void *_c)
2233 {
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;
2239         u32 block_size;
2240         int block_type;
2241
2242         /* Don't bother compressing very small inputs.  */
2243         if (uncompressed_size < 100)
2244                 return 0;
2245
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;
2250
2251         /* Preprocess the data.  */
2252         lzx_do_e8_preprocessing(c->cur_window, c->cur_window_size);
2253
2254         /* Load the window into the match-finder.  */
2255         lz_mf_load_window(c->mf, c->cur_window, c->cur_window_size);
2256
2257         /* Initialize the match offset LRU queue.  */
2258         lzx_lru_queue_init(&c->queue);
2259
2260         /* Initialize the output bitstream.  */
2261         lzx_init_output(&os, compressed_data, compressed_size_avail);
2262
2263         /* Compress the data block by block.
2264          *
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;
2269         c->codes_index = 0;
2270         prev_lens = &c->zero_lens;
2271         do {
2272                 /* Compute the block size.  */
2273                 block_size = min(LZX_DIV_BLOCK_SIZE,
2274                                  uncompressed_size - block_start_pos);
2275
2276                 /* Reset symbol frequencies.  */
2277                 memset(&c->freqs, 0, sizeof(c->freqs));
2278
2279                 /* Prepare the matches/literals for the block.  */
2280                 num_chosen_items = lzx_choose_items_for_block(c,
2281                                                               block_start_pos,
2282                                                               block_size);
2283
2284                 /* Make the Huffman codes from the symbol frequencies.  */
2285                 lzx_make_huffman_codes(&c->freqs, &c->codes[c->codes_index],
2286                                        c->num_main_syms);
2287
2288                 /* Choose the best block type.
2289                  *
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]);
2293
2294                 /* Write the compressed block to the output buffer.  */
2295                 lzx_write_compressed_block(block_type,
2296                                            block_size,
2297                                            c->window_order,
2298                                            c->num_main_syms,
2299                                            c->chosen_items,
2300                                            num_chosen_items,
2301                                            &c->codes[c->codes_index],
2302                                            prev_lens,
2303                                            &os);
2304
2305                 /* The current codeword lengths become the previous lengths.  */
2306                 prev_lens = &c->codes[c->codes_index].lens;
2307                 c->codes_index ^= 1;
2308
2309                 block_start_pos += block_size;
2310
2311         } while (block_start_pos != uncompressed_size);
2312
2313         return lzx_flush_output(&os);
2314 }
2315
2316 static void
2317 lzx_free_compressor(void *_c)
2318 {
2319         struct lzx_compressor *c = _c;
2320
2321         if (c) {
2322                 ALIGNED_FREE(c->cur_window);
2323                 lz_mf_free(c->mf);
2324                 FREE(c->cached_matches);
2325                 FREE(c);
2326         }
2327 }
2328
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,
2334 };