struct wimlib_lzx_params: Don't use anonymous union
[wimlib] / src / lzx-compress.c
1 /*
2  * lzx-compress.c
3  *
4  * LZX compression routines
5  */
6
7 /*
8  * Copyright (C) 2012, 2013 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 compression format, as used in
29  * the WIM file format.
30  *
31  * Format
32  * ======
33  *
34  * First, the primary reference for the LZX compression format is the
35  * specification released by Microsoft.
36  *
37  * Second, the comments in lzx-decompress.c provide some more information about
38  * the LZX compression format, including errors in the Microsoft specification.
39  *
40  * Do note that LZX shares many similarities with DEFLATE, the algorithm used by
41  * zlib and gzip.  Both LZX and DEFLATE use LZ77 matching and Huffman coding,
42  * and certain other details are quite similar, such as the method for storing
43  * Huffman codes.  However, some of the main differences are:
44  *
45  * - LZX preprocesses the data before attempting to compress it.
46  * - LZX uses a "main" alphabet which combines literals and matches, with the
47  *   match symbols containing a "length header" (giving all or part of the match
48  *   length) and a "position footer" (giving, roughly speaking, the order of
49  *   magnitude of the match offset).
50  * - LZX does not have static Huffman blocks; however it does have two types of
51  *   dynamic Huffman blocks ("aligned offset" and "verbatim").
52  * - LZX has a minimum match length of 2 rather than 3.
53  * - In LZX, match offsets 0 through 2 actually represent entries in a LRU queue
54  *   of match offsets.
55  *
56  * Algorithms
57  * ==========
58  *
59  * There are actually two distinct overall algorithms implemented here.  We
60  * shall refer to them as the "slow" algorithm and the "fast" algorithm.  The
61  * "slow" algorithm spends more time compressing to achieve a higher compression
62  * ratio compared to the "fast" algorithm.  More details are presented below.
63  *
64  * Slow algorithm
65  * --------------
66  *
67  * The "slow" algorithm to generate LZX-compressed data is roughly as follows:
68  *
69  * 1. Preprocess the input data to translate the targets of x86 call instructions
70  *    to absolute offsets.
71  *
72  * 2. Determine the best known sequence of LZ77 matches ((offset, length) pairs)
73  *    and literal bytes to divide the input into.  Raw match-finding is done
74  *    using a very clever binary tree search based on the "Bt3" algorithm from
75  *    7-Zip.  Parsing, or match-choosing, is solved essentially as a
76  *    minimum-cost path problem, but using a heuristic forward search based on
77  *    the Deflate encoder from 7-Zip rather than a more intuitive backward
78  *    search, the latter of which would naively require that all matches be
79  *    found.  This heuristic search, as well as other heuristics such as limits
80  *    on the matches considered, considerably speed up this part of the
81  *    algorithm, which is the main bottleneck.  Finally, after matches and
82  *    literals are chosen, the needed Huffman codes needed to output them are
83  *    built.
84  *
85  * 3. Up to a certain number of iterations, use the resulting Huffman codes to
86  *    refine a cost model and go back to Step #2 to determine an improved
87  *    sequence of matches and literals.
88  *
89  * 4. Up to a certain depth, try splitting the current block to see if the
90  *    compression ratio can be improved.  This may be the case if parts of the
91  *    input differ greatly from each other and could benefit from different
92  *    Huffman codes.
93  *
94  * 5. Output the resulting block(s) using the match/literal sequences and the
95  *    Huffman codes that were computed for each block.
96  *
97  * Fast algorithm
98  * --------------
99  *
100  * The fast algorithm (and the only one available in wimlib v1.5.1 and earlier)
101  * spends much less time on the main bottlenecks of the compression process ---
102  * that is the match finding, match choosing, and block splitting.  Matches are
103  * found and chosen with hash chains using a greedy parse with one position of
104  * look-ahead.  No block splitting is done; only compressing the full input into
105  * an aligned offset block is considered.
106  *
107  * API
108  * ===
109  *
110  * The old API (retained for backward compatibility) consists of just one function:
111  *
112  *      wimlib_lzx_compress()
113  *
114  * The new compressor has more potential parameters and needs more memory, so
115  * the new API ties up memory allocations and compression parameters into a
116  * context:
117  *
118  *      wimlib_lzx_alloc_context()
119  *      wimlib_lzx_compress2()
120  *      wimlib_lzx_free_context()
121  *
122  * Both wimlib_lzx_compress() and wimlib_lzx_compress2() are designed to
123  * compress an in-memory buffer of up to 32768 bytes.  There is no sliding
124  * window.  This is suitable for the WIM format, which uses fixed-size chunks
125  * that are seemingly always 32768 bytes.  If needed, the compressor potentially
126  * could be extended to support a larger and/or sliding window.
127  *
128  * Both wimlib_lzx_compress() and wimlib_lzx_compress2() return 0 if the data
129  * could not be compressed to less than the size of the uncompressed data.
130  * Again, this is suitable for the WIM format, which stores such data chunks
131  * uncompressed.
132  *
133  * The functions in this API are exported from the library, although this is
134  * only in case other programs happen to have uses for it other than WIM
135  * reading/writing as already handled through the rest of the library.
136  *
137  * Acknowledgments
138  * ===============
139  *
140  * Acknowledgments to several other open-source projects that made it possible
141  * to implement this code:
142  *
143  * - 7-Zip (author: Igor Pavlov), for the binary tree match-finding
144  *   algorithm, the heuristic near-optimal forward match-choosing
145  *   algorithm, and the block splitting algorithm.
146  *
147  * - zlib (author: Jean-loup Gailly and Mark Adler), for the hash table
148  *   match-finding algorithm.
149  *
150  * - lzx-compress (author: Matthew T. Russotto), on which some parts of this
151  *   code were originally based.
152  */
153
154 #ifdef HAVE_CONFIG_H
155 #  include "config.h"
156 #endif
157
158 #include "wimlib.h"
159 #include "wimlib/compress.h"
160 #include "wimlib/error.h"
161 #include "wimlib/lzx.h"
162 #include "wimlib/util.h"
163
164 #ifdef ENABLE_LZX_DEBUG
165 #  include <wimlib/decompress.h>
166 #endif
167
168 #include <string.h>
169
170 /* Experimental parameters not exposed through the API  */
171 #define LZX_PARAM_OPTIM_ARRAY_SIZE      1024
172 #define LZX_PARAM_ACCOUNT_FOR_LRU       1
173 #define LZX_PARAM_DONT_SKIP_MATCHES     0
174 #define LZX_PARAM_USE_EMPIRICAL_DEFAULT_COSTS 1
175
176 /* Currently, this constant can't simply be changed because the code currently
177  * uses a static number of position slots (and may make other assumptions as
178  * well).  */
179 #define LZX_MAX_WINDOW_SIZE     32768
180
181 /* This may be WIM-specific  */
182 #define LZX_DEFAULT_BLOCK_SIZE  32768
183
184 #define LZX_LZ_HASH_BITS        15
185 #define LZX_LZ_HASH_SIZE        (1 << LZX_LZ_HASH_BITS)
186 #define LZX_LZ_HASH_MASK        (LZX_LZ_HASH_SIZE - 1)
187 #define LZX_LZ_HASH_SHIFT       5
188
189 /* Codewords for the LZX main, length, and aligned offset Huffman codes  */
190 struct lzx_codewords {
191         u16 main[LZX_MAINTREE_NUM_SYMBOLS];
192         u16 len[LZX_LENTREE_NUM_SYMBOLS];
193         u16 aligned[LZX_ALIGNEDTREE_NUM_SYMBOLS];
194 };
195
196 /* Lengths for the LZX main, length, and aligned offset Huffman codes  */
197 struct lzx_lens {
198         u8 main[LZX_MAINTREE_NUM_SYMBOLS];
199         u8 len[LZX_LENTREE_NUM_SYMBOLS];
200         u8 aligned[LZX_ALIGNEDTREE_NUM_SYMBOLS];
201 };
202
203 /* The LZX main, length, and aligned offset Huffman codes  */
204 struct lzx_codes {
205         struct lzx_codewords codewords;
206         struct lzx_lens lens;
207 };
208
209 /* Tables for tallying symbol frequencies in the three LZX alphabets  */
210 struct lzx_freqs {
211         freq_t main[LZX_MAINTREE_NUM_SYMBOLS];
212         freq_t len[LZX_LENTREE_NUM_SYMBOLS];
213         freq_t aligned[LZX_ALIGNEDTREE_NUM_SYMBOLS];
214 };
215
216 /* LZX intermediate match/literal format  */
217 struct lzx_match {
218         /* Bit     Description
219          *
220          * 31      1 if a match, 0 if a literal.
221          *
222          * 30-25   position slot.  This can be at most 50, so it will fit in 6
223          *         bits.
224          *
225          * 8-24    position footer.  This is the offset of the real formatted
226          *         offset from the position base.  This can be at most 17 bits
227          *         (since lzx_extra_bits[LZX_NUM_POSITION_SLOTS - 1] is 17).
228          *
229          * 0-7     length of match, minus 2.  This can be at most
230          *         (LZX_MAX_MATCH - 2) == 255, so it will fit in 8 bits.  */
231         u32 data;
232 };
233
234 /* Raw LZ match/literal format: just a length and offset.
235  *
236  * The length is the number of bytes of the match, and the offset is the number
237  * of bytes back in the input the match is from the matched text.
238  *
239  * If @len < LZX_MIN_MATCH, then it's really just a literal byte and @offset is
240  * meaningless.  */
241 struct raw_match {
242         u16 len;
243         u16 offset;
244 };
245
246 /* Specification for a LZX block  */
247 struct lzx_block_spec {
248
249         /* Set to 1 if this block has been split (in two --- we only considser
250          * binary splits).  In such cases the rest of the fields are
251          * unimportant, since the relevant information is rather in the
252          * structures for the sub-blocks.  */
253         u8 is_split : 1;
254
255         /* One of the LZX_BLOCKTYPE_* constants indicating which type of this
256          * block.  */
257         u8 block_type : 2;
258
259         /* 0-based position in the window at which this block starts.  */
260         u16 window_pos;
261
262         /* The number of bytes of uncompressed data this block represents.  */
263         u16 block_size;
264
265         /* The position in the 'chosen_matches' array in the `struct
266          * lzx_compressor' at which the match/literal specifications for
267          * this block begin.  */
268         unsigned chosen_matches_start_pos;
269
270         /* The number of match/literal specifications for this block.  */
271         u16 num_chosen_matches;
272
273         /* Huffman codes for this block.  */
274         struct lzx_codes codes;
275 };
276
277 /*
278  * An array of these structures is used during the match-choosing algorithm.
279  * They correspond to consecutive positions in the window and are used to keep
280  * track of the cost to reach each position, and the match/literal choices that
281  * need to be chosen to reach that position.
282  */
283 struct lzx_optimal {
284         /* The approximate minimum cost, in bits, to reach this position in the
285          * window which has been found so far.  */
286         u32 cost;
287
288         /* The union here is just for clarity, since the fields are used in two
289          * slightly different ways.  Initially, the @prev structure is filled in
290          * first, and links go from later in the window to earlier in the
291          * window.  Later, @next structure is filled in and links go from
292          * earlier in the window to later in the window.  */
293         union {
294                 struct {
295                         /* Position of the start of the match or literal that
296                          * was taken to get to this position in the approximate
297                          * minimum-cost parse.  */
298                         u16 link;
299
300                         /* Offset (as in a LZ (length, offset) pair) of the
301                          * match or literal that was taken to get to this
302                          * position in the approximate minimum-cost parse.  */
303                         u16 match_offset;
304                 } prev;
305                 struct {
306                         /* Position at which the match or literal starting at
307                          * this position ends in the minimum-cost parse.  */
308                         u16 link;
309
310                         /* Offset (as in a LZ (length, offset) pair) of the
311                          * match or literal starting at this position in the
312                          * approximate minimum-cost parse.  */
313                         u16 match_offset;
314                 } next;
315         };
316 #if LZX_PARAM_ACCOUNT_FOR_LRU
317         struct lzx_lru_queue queue;
318 #endif
319 };
320
321 /* State of the LZX compressor  */
322 struct lzx_compressor {
323
324         /* The parameters that were used to create the compressor.  */
325         struct wimlib_lzx_params params;
326
327         /* The buffer of data to be compressed.
328          *
329          * 0xe8 byte preprocessing is done directly on the data here before
330          * further compression.
331          *
332          * Note that this compressor does *not* use a sliding window!!!!
333          * It's not needed in the WIM format, since every chunk is compressed
334          * independently.  This is by design, to allow random access to the
335          * chunks.
336          *
337          * We reserve a few extra bytes to potentially allow reading off the end
338          * of the array in the match-finding code for optimization purposes.
339          */
340         u8 window[LZX_MAX_WINDOW_SIZE + 12];
341
342         /* Number of bytes of data to be compressed, which is the number of
343          * bytes of data in @window that are actually valid.  */
344         unsigned window_size;
345
346         /* The current match offset LRU queue.  */
347         struct lzx_lru_queue queue;
348
349         /* Space for sequence of matches/literals that were chosen.
350          *
351          * Each LZX_MAX_WINDOW_SIZE-sized portion of this array is used for a
352          * different block splitting level.  */
353         struct lzx_match *chosen_matches;
354
355         /* Structures used during block splitting.
356          *
357          * This can be thought of as a binary tree.  block_specs[(1) - 1]
358          * represents to the top-level block (root node), and block_specs[(i*2)
359          * - 1] and block_specs[(i*2+1) - 1] represent the sub-blocks (child
360          * nodes) resulting from a binary split of the block represented by
361          * block_spec[(i) - 1].
362          */
363         struct lzx_block_spec *block_specs;
364
365         /* This is simply filled in with zeroes and used to avoid special-casing
366          * the output of the first compressed Huffman code, which conceptually
367          * has a delta taken from a code with all symbols having zero-length
368          * codewords.  */
369         struct lzx_codes zero_codes;
370
371         /* Slow algorithm only: The current cost model.  */
372         struct lzx_lens costs;
373
374         /* Slow algorithm only:  Table that maps the hash codes for 3 character
375          * sequences to the most recent position that sequence (or a sequence
376          * sharing the same hash code) appeared in the window.  */
377         u16 *hash_tab;
378
379         /* Slow algorithm only:  Table that maps 2-character sequences to the
380          * most recent position that sequence appeared in the window.  */
381         u16 *digram_tab;
382
383         /* Slow algorithm only: Table that contains the logical child pointers
384          * in the binary trees in the match-finding code.
385          *
386          * child_tab[i*2] and child_tab[i*2+1] are the left and right pointers,
387          * respectively, from the binary tree root corresponding to window
388          * position i.  */
389         u16 *child_tab;
390
391         /* Slow algorithm only: Matches that were already found and are saved in
392          * memory for subsequent queries (e.g. when block splitting).  */
393         struct raw_match *cached_matches;
394
395         /* Slow algorithm only: Next position in 'cached_matches' to either
396          * return or fill in.  */
397         unsigned cached_matches_pos;
398
399         /* Slow algorithm only: %true if reading from 'cached_matches'; %false
400          * if writing to 'cached_matches'.  */
401         bool matches_already_found;
402
403         /* Slow algorithm only: Position in window of next match to return.  */
404         unsigned match_window_pos;
405
406         /* Slow algorithm only: No matches returned shall reach past this
407          * position.  */
408         unsigned match_window_end;
409
410         /* Slow algorithm only: Temporary space used for match-choosing
411          * algorithm.
412          *
413          * The size of this array must be at least LZX_MAX_MATCH but otherwise
414          * is arbitrary.  More space simply allows the match-choosing algorithm
415          * to find better matches (depending on the input, as always).  */
416         struct lzx_optimal *optimum;
417
418         /* Slow algorithm only: Variables used by the match-choosing algorithm.
419          *
420          * When matches have been chosen, optimum_cur_idx is set to the position
421          * in the window of the next match/literal to return and optimum_end_idx
422          * is set to the position in the window at the end of the last
423          * match/literal to return.  */
424         u32 optimum_cur_idx;
425         u32 optimum_end_idx;
426 };
427
428 /* Returns the LZX position slot that corresponds to a given formatted offset.
429  *
430  * Logically, this returns the smallest i such that
431  * formatted_offset >= lzx_position_base[i].
432  *
433  * The actual implementation below takes advantage of the regularity of the
434  * numbers in the lzx_position_base array to calculate the slot directly from
435  * the formatted offset without actually looking at the array.
436  */
437 static unsigned
438 lzx_get_position_slot(unsigned formatted_offset)
439 {
440 #if 0
441         /*
442          * Slots 36-49 (formatted_offset >= 262144) can be found by
443          * (formatted_offset/131072) + 34 == (formatted_offset >> 17) + 34;
444          * however, this check for formatted_offset >= 262144 is commented out
445          * because WIM chunks cannot be that large.
446          */
447         if (formatted_offset >= 262144) {
448                 return (formatted_offset >> 17) + 34;
449         } else
450 #endif
451         {
452                 /* Note: this part here only works if:
453                  *
454                  *    2 <= formatted_offset < 655360
455                  *
456                  * It is < 655360 because the frequency of the position bases
457                  * increases starting at the 655360 entry, and it is >= 2
458                  * because the below calculation fails if the most significant
459                  * bit is lower than the 2's place. */
460                 LZX_ASSERT(2 <= formatted_offset  && formatted_offset < 655360);
461                 unsigned mssb_idx = bsr32(formatted_offset);
462                 return (mssb_idx << 1) |
463                         ((formatted_offset >> (mssb_idx - 1)) & 1);
464         }
465 }
466
467 /* Compute the hash code for the next 3-character sequence in the window.  */
468 static unsigned
469 lzx_lz_compute_hash(const u8 *window)
470 {
471         unsigned hash;
472
473         hash = window[0];
474         hash <<= LZX_LZ_HASH_SHIFT;
475         hash ^= window[1];
476         hash <<= LZX_LZ_HASH_SHIFT;
477         hash ^= window[2];
478         return hash & LZX_LZ_HASH_MASK;
479 }
480
481 /* Build the main, length, and aligned offset Huffman codes used in LZX.
482  *
483  * This takes as input the frequency tables for each code and produces as output
484  * a set of tables that map symbols to codewords and lengths.  */
485 static void
486 lzx_make_huffman_codes(const struct lzx_freqs *freqs,
487                        struct lzx_codes *codes)
488 {
489         make_canonical_huffman_code(LZX_MAINTREE_NUM_SYMBOLS,
490                                     LZX_MAX_CODEWORD_LEN,
491                                     freqs->main,
492                                     codes->lens.main,
493                                     codes->codewords.main);
494
495         make_canonical_huffman_code(LZX_LENTREE_NUM_SYMBOLS,
496                                     LZX_MAX_CODEWORD_LEN,
497                                     freqs->len,
498                                     codes->lens.len,
499                                     codes->codewords.len);
500
501         make_canonical_huffman_code(LZX_ALIGNEDTREE_NUM_SYMBOLS, 8,
502                                     freqs->aligned,
503                                     codes->lens.aligned,
504                                     codes->codewords.aligned);
505 }
506
507 /*
508  * Output a LZX match.
509  *
510  * @out:         The bitstream to write the match to.
511  * @block_type:  The type of the LZX block (LZX_BLOCKTYPE_ALIGNED or LZX_BLOCKTYPE_VERBATIM)
512  * @match:       The match.
513  * @codes:       Pointer to a structure that contains the codewords for the
514  *               main, length, and aligned offset Huffman codes.
515  */
516 static void
517 lzx_write_match(struct output_bitstream *out, int block_type,
518                 struct lzx_match match, const struct lzx_codes *codes)
519 {
520         /* low 8 bits are the match length minus 2 */
521         unsigned match_len_minus_2 = match.data & 0xff;
522         /* Next 17 bits are the position footer */
523         unsigned position_footer = (match.data >> 8) & 0x1ffff; /* 17 bits */
524         /* Next 6 bits are the position slot. */
525         unsigned position_slot = (match.data >> 25) & 0x3f;     /* 6 bits */
526         unsigned len_header;
527         unsigned len_footer;
528         unsigned len_pos_header;
529         unsigned main_symbol;
530         unsigned num_extra_bits;
531         unsigned verbatim_bits;
532         unsigned aligned_bits;
533
534         /* If the match length is less than MIN_MATCH (= 2) +
535          * NUM_PRIMARY_LENS (= 7), the length header contains
536          * the match length minus MIN_MATCH, and there is no
537          * length footer.
538          *
539          * Otherwise, the length header contains
540          * NUM_PRIMARY_LENS, and the length footer contains
541          * the match length minus NUM_PRIMARY_LENS minus
542          * MIN_MATCH. */
543         if (match_len_minus_2 < LZX_NUM_PRIMARY_LENS) {
544                 len_header = match_len_minus_2;
545                 /* No length footer-- mark it with a special
546                  * value. */
547                 len_footer = (unsigned)(-1);
548         } else {
549                 len_header = LZX_NUM_PRIMARY_LENS;
550                 len_footer = match_len_minus_2 - LZX_NUM_PRIMARY_LENS;
551         }
552
553         /* Combine the position slot with the length header into
554          * a single symbol that will be encoded with the main
555          * tree. */
556         len_pos_header = (position_slot << 3) | len_header;
557
558         /* The actual main symbol is offset by LZX_NUM_CHARS because
559          * values under LZX_NUM_CHARS are used to indicate a literal
560          * byte rather than a match. */
561         main_symbol = len_pos_header + LZX_NUM_CHARS;
562
563         /* Output main symbol. */
564         bitstream_put_bits(out, codes->codewords.main[main_symbol],
565                            codes->lens.main[main_symbol]);
566
567         /* If there is a length footer, output it using the
568          * length Huffman code. */
569         if (len_footer != (unsigned)(-1)) {
570                 bitstream_put_bits(out, codes->codewords.len[len_footer],
571                                    codes->lens.len[len_footer]);
572         }
573
574         num_extra_bits = lzx_get_num_extra_bits(position_slot);
575
576         /* For aligned offset blocks with at least 3 extra bits, output the
577          * verbatim bits literally, then the aligned bits encoded using the
578          * aligned offset tree.  Otherwise, only the verbatim bits need to be
579          * output. */
580         if ((block_type == LZX_BLOCKTYPE_ALIGNED) && (num_extra_bits >= 3)) {
581
582                 verbatim_bits = position_footer >> 3;
583                 bitstream_put_bits(out, verbatim_bits,
584                                    num_extra_bits - 3);
585
586                 aligned_bits = (position_footer & 7);
587                 bitstream_put_bits(out,
588                                    codes->codewords.aligned[aligned_bits],
589                                    codes->lens.aligned[aligned_bits]);
590         } else {
591                 /* verbatim bits is the same as the position
592                  * footer, in this case. */
593                 bitstream_put_bits(out, position_footer, num_extra_bits);
594         }
595 }
596
597 static unsigned
598 lzx_build_precode(const u8 lens[restrict],
599                   const u8 prev_lens[restrict],
600                   unsigned num_syms,
601                   freq_t precode_freqs[restrict LZX_PRETREE_NUM_SYMBOLS],
602                   u8 output_syms[restrict num_syms],
603                   u8 precode_lens[restrict LZX_PRETREE_NUM_SYMBOLS],
604                   u16 precode_codewords[restrict LZX_PRETREE_NUM_SYMBOLS],
605                   unsigned * num_additional_bits_ret)
606 {
607         unsigned output_syms_idx;
608         unsigned cur_run_len;
609         unsigned i;
610         unsigned len_in_run;
611         unsigned additional_bits;
612         signed char delta;
613         unsigned num_additional_bits = 0;
614
615         memset(precode_freqs, 0,
616                LZX_PRETREE_NUM_SYMBOLS * sizeof(precode_freqs[0]));
617
618         /* Since the code word lengths use a form of RLE encoding, the goal here
619          * is to find each run of identical lengths when going through them in
620          * symbol order (including runs of length 1).  For each run, as many
621          * lengths are encoded using RLE as possible, and the rest are output
622          * literally.
623          *
624          * output_syms[] will be filled in with the length symbols that will be
625          * output, including RLE codes, not yet encoded using the pre-tree.
626          *
627          * cur_run_len keeps track of how many code word lengths are in the
628          * current run of identical lengths.
629          */
630         output_syms_idx = 0;
631         cur_run_len = 1;
632         for (i = 1; i <= num_syms; i++) {
633
634                 if (i != num_syms && lens[i] == lens[i - 1]) {
635                         /* Still in a run--- keep going. */
636                         cur_run_len++;
637                         continue;
638                 }
639
640                 /* Run ended! Check if it is a run of zeroes or a run of
641                  * nonzeroes. */
642
643                 /* The symbol that was repeated in the run--- not to be confused
644                  * with the length *of* the run (cur_run_len) */
645                 len_in_run = lens[i - 1];
646
647                 if (len_in_run == 0) {
648                         /* A run of 0's.  Encode it in as few length
649                          * codes as we can. */
650
651                         /* The magic length 18 indicates a run of 20 + n zeroes,
652                          * where n is an uncompressed literal 5-bit integer that
653                          * follows the magic length. */
654                         while (cur_run_len >= 20) {
655
656                                 additional_bits = min(cur_run_len - 20, 0x1f);
657                                 num_additional_bits += 5;
658                                 precode_freqs[18]++;
659                                 output_syms[output_syms_idx++] = 18;
660                                 output_syms[output_syms_idx++] = additional_bits;
661                                 cur_run_len -= 20 + additional_bits;
662                         }
663
664                         /* The magic length 17 indicates a run of 4 + n zeroes,
665                          * where n is an uncompressed literal 4-bit integer that
666                          * follows the magic length. */
667                         while (cur_run_len >= 4) {
668                                 additional_bits = min(cur_run_len - 4, 0xf);
669                                 num_additional_bits += 4;
670                                 precode_freqs[17]++;
671                                 output_syms[output_syms_idx++] = 17;
672                                 output_syms[output_syms_idx++] = additional_bits;
673                                 cur_run_len -= 4 + additional_bits;
674                         }
675
676                 } else {
677
678                         /* A run of nonzero lengths. */
679
680                         /* The magic length 19 indicates a run of 4 + n
681                          * nonzeroes, where n is a literal bit that follows the
682                          * magic length, and where the value of the lengths in
683                          * the run is given by an extra length symbol, encoded
684                          * with the precode, that follows the literal bit.
685                          *
686                          * The extra length symbol is encoded as a difference
687                          * from the length of the codeword for the first symbol
688                          * in the run in the previous tree.
689                          * */
690                         while (cur_run_len >= 4) {
691                                 additional_bits = (cur_run_len > 4);
692                                 num_additional_bits += 1;
693                                 delta = (signed char)prev_lens[i - cur_run_len] -
694                                         (signed char)len_in_run;
695                                 if (delta < 0)
696                                         delta += 17;
697                                 precode_freqs[19]++;
698                                 precode_freqs[(unsigned char)delta]++;
699                                 output_syms[output_syms_idx++] = 19;
700                                 output_syms[output_syms_idx++] = additional_bits;
701                                 output_syms[output_syms_idx++] = delta;
702                                 cur_run_len -= 4 + additional_bits;
703                         }
704                 }
705
706                 /* Any remaining lengths in the run are outputted without RLE,
707                  * as a difference from the length of that codeword in the
708                  * previous tree. */
709                 while (cur_run_len > 0) {
710                         delta = (signed char)prev_lens[i - cur_run_len] -
711                                 (signed char)len_in_run;
712                         if (delta < 0)
713                                 delta += 17;
714
715                         precode_freqs[(unsigned char)delta]++;
716                         output_syms[output_syms_idx++] = delta;
717                         cur_run_len--;
718                 }
719
720                 cur_run_len = 1;
721         }
722
723         /* Build the precode from the frequencies of the length symbols. */
724
725         make_canonical_huffman_code(LZX_PRETREE_NUM_SYMBOLS,
726                                     LZX_MAX_CODEWORD_LEN,
727                                     precode_freqs, precode_lens,
728                                     precode_codewords);
729
730         if (num_additional_bits_ret)
731                 *num_additional_bits_ret = num_additional_bits;
732
733         return output_syms_idx;
734 }
735
736 /*
737  * Writes a compressed Huffman code to the output, preceded by the precode for
738  * it.
739  *
740  * The Huffman code is represented in the output as a series of path lengths
741  * from which the canonical Huffman code can be reconstructed.  The path lengths
742  * themselves are compressed using a separate Huffman code, the precode, which
743  * consists of LZX_PRETREE_NUM_SYMBOLS (= 20) symbols that cover all possible
744  * code lengths, plus extra codes for repeated lengths.  The path lengths of the
745  * precode precede the path lengths of the larger code and are uncompressed,
746  * consisting of 20 entries of 4 bits each.
747  *
748  * @out:                Bitstream to write the code to.
749  * @lens:               The code lengths for the Huffman code, indexed by symbol.
750  * @prev_lens:          Code lengths for this Huffman code, indexed by symbol,
751  *                      in the *previous block*, or all zeroes if this is the
752  *                      first block.
753  * @num_syms:           The number of symbols in the code.
754  */
755 static void
756 lzx_write_compressed_code(struct output_bitstream *out,
757                           const u8 lens[restrict],
758                           const u8 prev_lens[restrict],
759                           unsigned num_syms)
760 {
761         freq_t precode_freqs[LZX_PRETREE_NUM_SYMBOLS];
762         u8 output_syms[num_syms];
763         u8 precode_lens[LZX_PRETREE_NUM_SYMBOLS];
764         u16 precode_codewords[LZX_PRETREE_NUM_SYMBOLS];
765         unsigned i;
766         unsigned num_output_syms;
767         u8 precode_sym;
768
769         num_output_syms = lzx_build_precode(lens,
770                                             prev_lens,
771                                             num_syms,
772                                             precode_freqs,
773                                             output_syms,
774                                             precode_lens,
775                                             precode_codewords,
776                                             NULL);
777
778         /* Write the lengths of the precode codes to the output. */
779         for (i = 0; i < LZX_PRETREE_NUM_SYMBOLS; i++)
780                 bitstream_put_bits(out, precode_lens[i],
781                                    LZX_PRETREE_ELEMENT_SIZE);
782
783         /* Write the length symbols, encoded with the precode, to the output. */
784
785         for (i = 0; i < num_output_syms; ) {
786                 precode_sym = output_syms[i++];
787
788                 bitstream_put_bits(out, precode_codewords[precode_sym],
789                                    precode_lens[precode_sym]);
790                 switch (precode_sym) {
791                 case 17:
792                         bitstream_put_bits(out, output_syms[i++], 4);
793                         break;
794                 case 18:
795                         bitstream_put_bits(out, output_syms[i++], 5);
796                         break;
797                 case 19:
798                         bitstream_put_bits(out, output_syms[i++], 1);
799                         bitstream_put_bits(out,
800                                            precode_codewords[output_syms[i]],
801                                            precode_lens[output_syms[i]]);
802                         i++;
803                         break;
804                 default:
805                         break;
806                 }
807         }
808 }
809
810 /*
811  * Writes all compressed matches and literal bytes in a LZX block to the the
812  * output bitstream.
813  *
814  * @ostream
815  *      The output bitstream.
816  * @block_type
817  *      The type of the block (LZX_BLOCKTYPE_ALIGNED or LZX_BLOCKTYPE_VERBATIM).
818  * @match_tab
819  *      The array of matches/literals that will be output (length @match_count).
820  * @match_count
821  *      Number of matches/literals to be output.
822  * @codes
823  *      Pointer to a structure that contains the codewords for the main, length,
824  *      and aligned offset Huffman codes.
825  */
826 static void
827 lzx_write_matches_and_literals(struct output_bitstream *ostream,
828                                int block_type,
829                                const struct lzx_match match_tab[],
830                                unsigned match_count,
831                                const struct lzx_codes *codes)
832 {
833         for (unsigned i = 0; i < match_count; i++) {
834                 struct lzx_match match = match_tab[i];
835
836                 /* High bit of the match indicates whether the match is an
837                  * actual match (1) or a literal uncompressed byte (0)  */
838                 if (match.data & 0x80000000) {
839                         /* match */
840                         lzx_write_match(ostream, block_type,
841                                         match, codes);
842                 } else {
843                         /* literal byte */
844                         bitstream_put_bits(ostream,
845                                            codes->codewords.main[match.data],
846                                            codes->lens.main[match.data]);
847                 }
848         }
849 }
850
851
852 static void
853 lzx_assert_codes_valid(const struct lzx_codes * codes)
854 {
855 #ifdef ENABLE_LZX_DEBUG
856         unsigned i;
857
858         for (i = 0; i < LZX_MAINTREE_NUM_SYMBOLS; i++)
859                 LZX_ASSERT(codes->lens.main[i] <= LZX_MAX_CODEWORD_LEN);
860
861         for (i = 0; i < LZX_LENTREE_NUM_SYMBOLS; i++)
862                 LZX_ASSERT(codes->lens.len[i] <= LZX_MAX_CODEWORD_LEN);
863
864         for (i = 0; i < LZX_ALIGNEDTREE_NUM_SYMBOLS; i++)
865                 LZX_ASSERT(codes->lens.aligned[i] <= 8);
866
867         const unsigned tablebits = 10;
868         u16 decode_table[(1 << tablebits) +
869                          (2 * max(LZX_MAINTREE_NUM_SYMBOLS, LZX_LENTREE_NUM_SYMBOLS))]
870                          _aligned_attribute(DECODE_TABLE_ALIGNMENT);
871         LZX_ASSERT(0 == make_huffman_decode_table(decode_table,
872                                                   LZX_MAINTREE_NUM_SYMBOLS,
873                                                   tablebits,
874                                                   codes->lens.main,
875                                                   LZX_MAX_CODEWORD_LEN));
876         LZX_ASSERT(0 == make_huffman_decode_table(decode_table,
877                                                   LZX_LENTREE_NUM_SYMBOLS,
878                                                   tablebits,
879                                                   codes->lens.len,
880                                                   LZX_MAX_CODEWORD_LEN));
881         LZX_ASSERT(0 == make_huffman_decode_table(decode_table,
882                                                   LZX_ALIGNEDTREE_NUM_SYMBOLS,
883                                                   min(tablebits, 6),
884                                                   codes->lens.aligned,
885                                                   8));
886 #endif /* ENABLE_LZX_DEBUG */
887 }
888
889 /* Write a LZX aligned offset or verbatim block to the output.  */
890 static void
891 lzx_write_compressed_block(int block_type,
892                            unsigned block_size,
893                            struct lzx_match * chosen_matches,
894                            unsigned num_chosen_matches,
895                            const struct lzx_codes * codes,
896                            const struct lzx_codes * prev_codes,
897                            struct output_bitstream * ostream)
898 {
899         unsigned i;
900
901         LZX_ASSERT(block_type == LZX_BLOCKTYPE_ALIGNED ||
902                    block_type == LZX_BLOCKTYPE_VERBATIM);
903         LZX_ASSERT(block_size <= LZX_MAX_WINDOW_SIZE);
904         LZX_ASSERT(num_chosen_matches <= LZX_MAX_WINDOW_SIZE);
905         lzx_assert_codes_valid(codes);
906
907         /* The first three bits indicate the type of block and are one of the
908          * LZX_BLOCKTYPE_* constants.  */
909         bitstream_put_bits(ostream, block_type, LZX_BLOCKTYPE_NBITS);
910
911         /* The next bit indicates whether the block size is the default (32768),
912          * indicated by a 1 bit, or whether the block size is given by the next
913          * 16 bits, indicated by a 0 bit.  */
914         if (block_size == LZX_DEFAULT_BLOCK_SIZE) {
915                 bitstream_put_bits(ostream, 1, 1);
916         } else {
917                 bitstream_put_bits(ostream, 0, 1);
918                 bitstream_put_bits(ostream, block_size, LZX_BLOCKSIZE_NBITS);
919         }
920
921         /* Write out lengths of the main code. Note that the LZX specification
922          * incorrectly states that the aligned offset code comes after the
923          * length code, but in fact it is the very first tree to be written
924          * (before the main code).  */
925         if (block_type == LZX_BLOCKTYPE_ALIGNED)
926                 for (i = 0; i < LZX_ALIGNEDTREE_NUM_SYMBOLS; i++)
927                         bitstream_put_bits(ostream, codes->lens.aligned[i],
928                                            LZX_ALIGNEDTREE_ELEMENT_SIZE);
929
930         LZX_DEBUG("Writing main code...");
931
932         /* Write the pre-tree and lengths for the first LZX_NUM_CHARS symbols in
933          * the main code, which are the codewords for literal bytes.  */
934         lzx_write_compressed_code(ostream,
935                                   codes->lens.main,
936                                   prev_codes->lens.main,
937                                   LZX_NUM_CHARS);
938
939         /* Write the pre-tree and lengths for the rest of the main code, which
940          * are the codewords for match headers.  */
941         lzx_write_compressed_code(ostream,
942                                   codes->lens.main + LZX_NUM_CHARS,
943                                   prev_codes->lens.main + LZX_NUM_CHARS,
944                                   LZX_MAINTREE_NUM_SYMBOLS - LZX_NUM_CHARS);
945
946         LZX_DEBUG("Writing length code...");
947
948         /* Write the pre-tree and lengths for the length code.  */
949         lzx_write_compressed_code(ostream,
950                                   codes->lens.len,
951                                   prev_codes->lens.len,
952                                   LZX_LENTREE_NUM_SYMBOLS);
953
954         LZX_DEBUG("Writing matches and literals...");
955
956         /* Write the actual matches and literals.  */
957         lzx_write_matches_and_literals(ostream, block_type,
958                                        chosen_matches, num_chosen_matches,
959                                        codes);
960
961         LZX_DEBUG("Done writing block.");
962 }
963
964 /* Write the LZX block of index @block_number, or write its children recursively
965  * if it is a split block.
966  *
967  * @prev_codes is a pointer to the Huffman codes for the most recent block
968  * written, or all zeroes if this is the first block.
969  *
970  * Return a pointer to the Huffman codes for the last block written.  */
971 static struct lzx_codes *
972 lzx_write_block_recursive(struct lzx_compressor *ctx,
973                           unsigned block_number,
974                           struct lzx_codes * prev_codes,
975                           struct output_bitstream *ostream)
976 {
977         struct lzx_block_spec *spec = &ctx->block_specs[block_number - 1];
978
979         if (spec->is_split) {
980                 prev_codes = lzx_write_block_recursive(ctx, block_number * 2 + 0,
981                                                        prev_codes, ostream);
982                 prev_codes = lzx_write_block_recursive(ctx, block_number * 2 + 1,
983                                                        prev_codes, ostream);
984         } else {
985                 LZX_DEBUG("Writing block #%u (type=%d, size=%u, num_chosen_matches=%u)...",
986                           block_number, spec->block_type, spec->block_size,
987                           spec->num_chosen_matches);
988                 lzx_write_compressed_block(spec->block_type,
989                                            spec->block_size,
990                                            &ctx->chosen_matches[spec->chosen_matches_start_pos],
991                                            spec->num_chosen_matches,
992                                            &spec->codes,
993                                            prev_codes,
994                                            ostream);
995                 prev_codes = &spec->codes;
996         }
997         return prev_codes;
998 }
999
1000 /* Write out the LZX blocks that were computed.  */
1001 static void
1002 lzx_write_all_blocks(struct lzx_compressor *ctx, struct output_bitstream *ostream)
1003 {
1004         lzx_write_block_recursive(ctx, 1, &ctx->zero_codes, ostream);
1005 }
1006
1007 static u32
1008 lzx_record_literal(u8 literal, void *_freqs)
1009 {
1010         struct lzx_freqs *freqs = _freqs;
1011
1012         freqs->main[literal]++;
1013
1014         return (u32)literal;
1015 }
1016
1017 /* Constructs a match from an offset and a length, and updates the LRU queue and
1018  * the frequency of symbols in the main, length, and aligned offset alphabets.
1019  * The return value is a 32-bit number that provides the match in an
1020  * intermediate representation documented below.  */
1021 static u32
1022 lzx_record_match(unsigned match_offset, unsigned match_len,
1023                  void *_freqs, void *_queue)
1024 {
1025         struct lzx_freqs *freqs = _freqs;
1026         struct lzx_lru_queue *queue = _queue;
1027         unsigned position_slot;
1028         unsigned position_footer = 0;
1029         u32 len_header;
1030         u32 len_pos_header;
1031         unsigned len_footer;
1032         unsigned adjusted_match_len;
1033
1034         LZX_ASSERT(match_len >= LZX_MIN_MATCH && match_len <= LZX_MAX_MATCH);
1035
1036         /* If possible, encode this offset as a repeated offset. */
1037         if (match_offset == queue->R0) {
1038                 position_slot = 0;
1039         } else if (match_offset == queue->R1) {
1040                 swap(queue->R0, queue->R1);
1041                 position_slot = 1;
1042         } else if (match_offset == queue->R2) {
1043                 swap(queue->R0, queue->R2);
1044                 position_slot = 2;
1045         } else {
1046                 /* Not a repeated offset. */
1047
1048                 /* offsets of 0, 1, and 2 are reserved for the repeated offset
1049                  * codes, so non-repeated offsets must be encoded as 3+.  The
1050                  * minimum offset is 1, so encode the offsets offset by 2. */
1051                 unsigned formatted_offset = match_offset + 2;
1052
1053                 queue->R2 = queue->R1;
1054                 queue->R1 = queue->R0;
1055                 queue->R0 = match_offset;
1056
1057                 /* The (now-formatted) offset will actually be encoded as a
1058                  * small position slot number that maps to a certain hard-coded
1059                  * offset (position base), followed by a number of extra bits---
1060                  * the position footer--- that are added to the position base to
1061                  * get the original formatted offset. */
1062
1063                 position_slot = lzx_get_position_slot(formatted_offset);
1064                 position_footer = formatted_offset &
1065                                   ((1 << lzx_get_num_extra_bits(position_slot)) - 1);
1066         }
1067
1068         adjusted_match_len = match_len - LZX_MIN_MATCH;
1069
1070
1071         /* The match length must be at least 2, so let the adjusted match length
1072          * be the match length minus 2.
1073          *
1074          * If it is less than 7, the adjusted match length is encoded as a 3-bit
1075          * number offset by 2.  Otherwise, the 3-bit length header is all 1's
1076          * and the actual adjusted length is given as a symbol encoded with the
1077          * length tree, offset by 7.
1078          */
1079         if (adjusted_match_len < LZX_NUM_PRIMARY_LENS) {
1080                 len_header = adjusted_match_len;
1081         } else {
1082                 len_header = LZX_NUM_PRIMARY_LENS;
1083                 len_footer = adjusted_match_len - LZX_NUM_PRIMARY_LENS;
1084                 freqs->len[len_footer]++;
1085         }
1086         len_pos_header = (position_slot << 3) | len_header;
1087
1088         freqs->main[len_pos_header + LZX_NUM_CHARS]++;
1089
1090         /* Equivalent to:
1091          * if (lzx_extra_bits[position_slot] >= 3) */
1092         if (position_slot >= 8)
1093                 freqs->aligned[position_footer & 7]++;
1094
1095         /* Pack the position slot, position footer, and match length into an
1096          * intermediate representation.
1097          *
1098          * bits    description
1099          * ----    -----------------------------------------------------------
1100          *
1101          * 31      1 if a match, 0 if a literal.
1102          *
1103          * 30-25   position slot.  This can be at most 50, so it will fit in 6
1104          *         bits.
1105          *
1106          * 8-24    position footer.  This is the offset of the real formatted
1107          *         offset from the position base.  This can be at most 17 bits
1108          *         (since lzx_extra_bits[LZX_NUM_POSITION_SLOTS - 1] is 17).
1109          *
1110          * 0-7     length of match, offset by 2.  This can be at most
1111          *         (LZX_MAX_MATCH - 2) == 255, so it will fit in 8 bits.  */
1112         return 0x80000000 |
1113                 (position_slot << 25) |
1114                 (position_footer << 8) |
1115                 (adjusted_match_len);
1116 }
1117
1118 /* Set the cost model @ctx->costs from the Huffman codeword lengths specified in
1119  * @lens.
1120  *
1121  * These are basically the same thing, except that the Huffman codewords with
1122  * length 0 correspond to symbols with zero frequency that still need to be
1123  * assigned actual costs.  The specific values assigned are arbitrary, but they
1124  * should be fairly high (near the maximum codeword length) to take into account
1125  * the fact that uses of these symbols are expected to be rare.
1126  */
1127 static void
1128 lzx_set_costs(struct lzx_compressor * ctx, const struct lzx_lens * lens)
1129 {
1130         unsigned i;
1131
1132         memcpy(&ctx->costs, lens, sizeof(struct lzx_lens));
1133
1134         for (i = 0; i < LZX_MAINTREE_NUM_SYMBOLS; i++)
1135                 if (ctx->costs.main[i] == 0)
1136                         ctx->costs.main[i] = ctx->params.alg_params.slow.main_nostat_cost;
1137
1138         for (i = 0; i < LZX_LENTREE_NUM_SYMBOLS; i++)
1139                 if (ctx->costs.len[i] == 0)
1140                         ctx->costs.len[i] = ctx->params.alg_params.slow.len_nostat_cost;
1141
1142         for (i = 0; i < LZX_ALIGNEDTREE_NUM_SYMBOLS; i++)
1143                 if (ctx->costs.aligned[i] == 0)
1144                         ctx->costs.aligned[i] = ctx->params.alg_params.slow.aligned_nostat_cost;
1145 }
1146
1147 static u32
1148 lzx_literal_cost(u8 c, const struct lzx_lens * costs)
1149 {
1150         return costs->main[c];
1151 }
1152
1153 /* Given a (length, offset) pair that could be turned into a valid LZX match as
1154  * well as costs for the codewords in the main, length, and aligned Huffman
1155  * codes, return the approximate number of bits it will take to represent this
1156  * match in the compressed output.  */
1157 static unsigned
1158 lzx_match_cost(unsigned length, unsigned offset, const struct lzx_lens *costs
1159
1160 #if LZX_PARAM_ACCOUNT_FOR_LRU
1161                , struct lzx_lru_queue *queue
1162 #endif
1163         )
1164 {
1165         unsigned position_slot, len_header, main_symbol;
1166         unsigned cost = 0;
1167
1168         /* Calculate position slot and length header, then combine them into the
1169          * main symbol.  */
1170
1171 #if LZX_PARAM_ACCOUNT_FOR_LRU
1172         if (offset == queue->R0) {
1173                 position_slot = 0;
1174         } else if (offset == queue->R1) {
1175                 swap(queue->R0, queue->R1);
1176                 position_slot = 1;
1177         } else if (offset == queue->R2) {
1178                 swap(queue->R0, queue->R2);
1179                 position_slot = 2;
1180         } else
1181 #endif
1182                 position_slot = lzx_get_position_slot(offset + 2);
1183
1184         len_header = min(length - LZX_MIN_MATCH, LZX_NUM_PRIMARY_LENS);
1185         main_symbol = ((position_slot << 3) | len_header) + LZX_NUM_CHARS;
1186
1187         /* Account for main symbol.  */
1188         cost += costs->main[main_symbol];
1189
1190         /* Account for extra position information.  */
1191         unsigned num_extra_bits = lzx_get_num_extra_bits(position_slot);
1192         if (num_extra_bits >= 3) {
1193                 cost += num_extra_bits - 3;
1194                 cost += costs->aligned[(offset + LZX_MIN_MATCH) & 7];
1195         } else {
1196                 cost += num_extra_bits;
1197         }
1198
1199         /* Account for extra length information.  */
1200         if (length - LZX_MIN_MATCH >= LZX_NUM_PRIMARY_LENS)
1201                 cost += costs->len[length - LZX_MIN_MATCH - LZX_NUM_PRIMARY_LENS];
1202
1203         return cost;
1204 }
1205
1206 /* This procedure effectively creates a new binary tree corresponding to the
1207  * current string at the same time that it searches the existing tree nodes for
1208  * matches.  This is the same algorithm as that used in GetMatchesSpec1() in
1209  * 7-Zip, but it is hopefully explained a little more clearly below.  */
1210 static unsigned
1211 lzx_lz_get_matches(const u8 window[restrict],
1212                    const unsigned bytes_remaining,
1213                    const unsigned strstart,
1214                    const unsigned max_length,
1215                    u16 child_tab[restrict],
1216                    unsigned cur_match,
1217                    const unsigned prev_len,
1218                    struct raw_match * const matches)
1219 {
1220         u16 *new_tree_lt_ptr = &child_tab[strstart * 2];
1221         u16 *new_tree_gt_ptr = &child_tab[strstart * 2 + 1];
1222
1223         u16 longest_lt_match_len = 0;
1224         u16 longest_gt_match_len = 0;
1225
1226         /* Maximum number of nodes to walk down before stopping  */
1227         unsigned depth = max_length;
1228
1229         /* Length of longest match found so far  */
1230         unsigned longest_match_len = prev_len;
1231
1232         /* Maximum length of match to return  */
1233         unsigned len_limit = min(bytes_remaining, max_length);
1234
1235         /* Number of matches found so far  */
1236         unsigned num_matches = 0;
1237
1238         for (;;) {
1239
1240                 /* Stop if too many nodes were traversed or if there is no next
1241                  * node  */
1242                 if (depth-- == 0 || cur_match == 0) {
1243                         *new_tree_gt_ptr = 0;
1244                         *new_tree_lt_ptr = 0;
1245                         return num_matches;
1246                 }
1247
1248                 /* Load the pointers to the children of the binary tree node
1249                  * corresponding to the current match  */
1250                 u16 * const cur_match_ptrs = &child_tab[cur_match * 2];
1251
1252                 /* Set up pointers to the current match and to the current
1253                  * string  */
1254                 const u8 * const matchptr = &window[cur_match];
1255                 const u8 * const strptr = &window[strstart];
1256
1257                 /* Determine position at which to start comparing  */
1258                 u16 len = min(longest_lt_match_len,
1259                               longest_gt_match_len);
1260
1261                 if (matchptr[len] == strptr[len]) {
1262
1263                         /* Extend the match as far as possible.  */
1264                         while (++len != len_limit)
1265                                 if (matchptr[len] != strptr[len])
1266                                         break;
1267
1268                         /* Record this match if it is the longest found so far.
1269                          */
1270                         if (len > longest_match_len) {
1271                                 longest_match_len = len;
1272                                 matches[num_matches].len = len;
1273                                 matches[num_matches].offset = strstart - cur_match;
1274                                 num_matches++;
1275
1276                                 if (len == len_limit) {
1277                                         /* Length limit was reached.  Link left pointer
1278                                          * in the new tree with left subtree of current
1279                                          * match tree, and link the right pointer in the
1280                                          * new tree with the right subtree of the
1281                                          * current match tree.  This in effect deletes
1282                                          * the node for the currrent match, which is
1283                                          * desirable because the current match is the
1284                                          * same as the current string up until the
1285                                          * length limit, so in subsequent queries it
1286                                          * will never be preferable to the current
1287                                          * position.  */
1288                                         *new_tree_lt_ptr = cur_match_ptrs[0];
1289                                         *new_tree_gt_ptr = cur_match_ptrs[1];
1290                                         return num_matches;
1291                                 }
1292                         }
1293                 }
1294
1295                 if (matchptr[len] < strptr[len]) {
1296                         /* Case 1:  The current match is lexicographically less
1297                          * than the current string.
1298                          *
1299                          * Since we are searching the binary tree structures, we
1300                          * need to walk down to the *right* subtree of the
1301                          * current match's node to get to a match that is
1302                          * lexicographically *greater* than the current match
1303                          * but still lexicographically *lesser* than the current
1304                          * string.
1305                          *
1306                          * At the same time, we link the entire binary tree
1307                          * corresponding to the current match into the
1308                          * appropriate place in the new binary tree being built
1309                          * for the current string.  */
1310                         *new_tree_lt_ptr = cur_match;
1311                         new_tree_lt_ptr = &cur_match_ptrs[1];
1312                         cur_match = *new_tree_lt_ptr;
1313                         longest_lt_match_len = len;
1314                 } else {
1315                         /* Case 2:  The current match is lexicographically
1316                          * greater than the current string.
1317                          *
1318                          * This is analogous to Case 1 above, but everything
1319                          * happens in the other direction.
1320                          */
1321                         *new_tree_gt_ptr = cur_match;
1322                         new_tree_gt_ptr = &cur_match_ptrs[0];
1323                         cur_match = *new_tree_gt_ptr;
1324                         longest_gt_match_len = len;
1325                 }
1326         }
1327 }
1328
1329 /* Equivalent to lzx_lz_get_matches(), but only updates the tree and doesn't
1330  * return matches.  See that function for details (including comments).  */
1331 static void
1332 lzx_lz_skip_matches(const u8 window[restrict],
1333                     const unsigned bytes_remaining,
1334                     const unsigned strstart,
1335                     const unsigned max_length,
1336                     u16 child_tab[restrict],
1337                     unsigned cur_match,
1338                     const unsigned prev_len)
1339 {
1340         u16 *new_tree_lt_ptr = &child_tab[strstart * 2];
1341         u16 *new_tree_gt_ptr = &child_tab[strstart * 2 + 1];
1342
1343         u16 longest_lt_match_len = 0;
1344         u16 longest_gt_match_len = 0;
1345
1346         unsigned depth = max_length;
1347
1348         unsigned longest_match_len = prev_len;
1349
1350         unsigned len_limit = min(bytes_remaining, max_length);
1351
1352         for (;;) {
1353                 if (depth-- == 0 || cur_match == 0) {
1354                         *new_tree_gt_ptr = 0;
1355                         *new_tree_lt_ptr = 0;
1356                         return;
1357                 }
1358
1359                 u16 * const cur_match_ptrs = &child_tab[cur_match * 2];
1360
1361                 const u8 * const matchptr = &window[cur_match];
1362                 const u8 * const strptr = &window[strstart];
1363
1364                 u16 len = min(longest_lt_match_len,
1365                               longest_gt_match_len);
1366
1367                 if (matchptr[len] == strptr[len]) {
1368                         while (++len != len_limit)
1369                                 if (matchptr[len] != strptr[len])
1370                                         break;
1371
1372                         if (len > longest_match_len) {
1373                                 longest_match_len = len;
1374
1375                                 if (len == len_limit) {
1376                                         *new_tree_lt_ptr = cur_match_ptrs[0];
1377                                         *new_tree_gt_ptr = cur_match_ptrs[1];
1378                                         return;
1379                                 }
1380                         }
1381                 }
1382
1383                 if (matchptr[len] < strptr[len]) {
1384                         *new_tree_lt_ptr = cur_match;
1385                         new_tree_lt_ptr = &cur_match_ptrs[1];
1386                         cur_match = *new_tree_lt_ptr;
1387                         longest_lt_match_len = len;
1388                 } else {
1389                         *new_tree_gt_ptr = cur_match;
1390                         new_tree_gt_ptr = &cur_match_ptrs[0];
1391                         cur_match = *new_tree_gt_ptr;
1392                         longest_gt_match_len = len;
1393                 }
1394         }
1395 }
1396
1397 static unsigned
1398 lzx_lz_get_matches_caching(struct lzx_compressor *ctx,
1399                            struct raw_match **matches_ret);
1400
1401 /* Tell the match-finder to skip the specified number of bytes (@n) in the
1402  * input.  */
1403 static void
1404 lzx_lz_skip_bytes(struct lzx_compressor *ctx, unsigned n)
1405 {
1406
1407 #if LZX_PARAM_DONT_SKIP_MATCHES
1408         /* Option 1: Still cache the matches from the positions skipped.  They
1409          * will then be available in later passes.  */
1410         struct raw_match *matches;
1411         while (n--)
1412                 lzx_lz_get_matches_caching(ctx, &matches);
1413 #else
1414         /* Option 2: Mark the positions skipped as having no matches available,
1415          * but we still need to update the binary tree in case subsequent
1416          * positions have matches at the current position.  */
1417         LZX_ASSERT(n <= ctx->match_window_end - ctx->match_window_pos);
1418         if (ctx->matches_already_found) {
1419                 while (n--) {
1420                         LZX_ASSERT(ctx->cached_matches[ctx->cached_matches_pos].offset ==
1421                                    ctx->match_window_pos);
1422                         ctx->cached_matches_pos += ctx->cached_matches[ctx->cached_matches_pos].len + 1;
1423                         ctx->match_window_pos++;
1424                 }
1425         } else {
1426                 while (n--) {
1427                         if (ctx->params.alg_params.slow.use_len2_matches &&
1428                             ctx->match_window_end - ctx->match_window_pos >= 2) {
1429                                 unsigned c1 = ctx->window[ctx->match_window_pos];
1430                                 unsigned c2 = ctx->window[ctx->match_window_pos + 1];
1431                                 unsigned digram = c1 | (c2 << 8);
1432                                 ctx->digram_tab[digram] = ctx->match_window_pos;
1433                         }
1434                         if (ctx->match_window_end - ctx->match_window_pos >= 3) {
1435                                 unsigned hash;
1436                                 unsigned cur_match;
1437
1438                                 hash = lzx_lz_compute_hash(&ctx->window[ctx->match_window_pos]);
1439
1440                                 cur_match = ctx->hash_tab[hash];
1441                                 ctx->hash_tab[hash] = ctx->match_window_pos;
1442
1443                                 lzx_lz_skip_matches(ctx->window,
1444                                                     ctx->match_window_end - ctx->match_window_pos,
1445                                                     ctx->match_window_pos,
1446                                                     ctx->params.alg_params.slow.num_fast_bytes,
1447                                                     ctx->child_tab,
1448                                                     cur_match, 1);
1449                         }
1450                         ctx->cached_matches[ctx->cached_matches_pos].len = 0;
1451                         ctx->cached_matches[ctx->cached_matches_pos].offset = ctx->match_window_pos;
1452                         ctx->cached_matches_pos++;
1453                         ctx->match_window_pos++;
1454                 }
1455         }
1456 #endif /* !LZX_PARAM_DONT_SKIP_MATCHES */
1457 }
1458
1459 /* Retrieve a list of matches available at the next position in the input.
1460  *
1461  * The return value is the number of matches found, and a pointer to them is
1462  * written to @matches_ret.  The matches will be sorted in order by length.
1463  *
1464  * This is essentially a wrapper around lzx_lz_get_matches() that caches its
1465  * output the first time and also performs the needed hashing.
1466  */
1467 static unsigned
1468 lzx_lz_get_matches_caching(struct lzx_compressor *ctx,
1469                            struct raw_match **matches_ret)
1470 {
1471         unsigned num_matches;
1472         struct raw_match *matches;
1473
1474         LZX_ASSERT(ctx->match_window_end >= ctx->match_window_pos);
1475
1476         matches = &ctx->cached_matches[ctx->cached_matches_pos + 1];
1477
1478         if (ctx->matches_already_found) {
1479                 num_matches = ctx->cached_matches[ctx->cached_matches_pos].len;
1480                 LZX_ASSERT(ctx->cached_matches[ctx->cached_matches_pos].offset == ctx->match_window_pos);
1481
1482                 for (int i = (int)num_matches - 1; i >= 0; i--) {
1483                         if (ctx->match_window_pos + matches[i].len > ctx->match_window_end)
1484                                 matches[i].len = ctx->match_window_end - ctx->match_window_pos;
1485                         else
1486                                 break;
1487                 }
1488         } else {
1489                 unsigned prev_len = 1;
1490                 struct raw_match * matches_ret = &ctx->cached_matches[ctx->cached_matches_pos + 1];
1491                 num_matches = 0;
1492
1493                 if (ctx->params.alg_params.slow.use_len2_matches &&
1494                     ctx->match_window_end - ctx->match_window_pos >= 3) {
1495                         unsigned c1 = ctx->window[ctx->match_window_pos];
1496                         unsigned c2 = ctx->window[ctx->match_window_pos + 1];
1497                         unsigned digram = c1 | (c2 << 8);
1498                         unsigned cur_match;
1499
1500                         cur_match = ctx->digram_tab[digram];
1501                         ctx->digram_tab[digram] = ctx->match_window_pos;
1502                         if (cur_match != 0 &&
1503                             ctx->window[cur_match + 2] != ctx->window[ctx->match_window_pos + 2])
1504                         {
1505                                 matches_ret->len = 2;
1506                                 matches_ret->offset = ctx->match_window_pos - cur_match;
1507                                 matches_ret++;
1508                                 num_matches++;
1509                                 prev_len = 2;
1510                         }
1511                 }
1512                 if (ctx->match_window_end - ctx->match_window_pos >= 3) {
1513                         unsigned hash;
1514                         unsigned cur_match;
1515
1516                         hash = lzx_lz_compute_hash(&ctx->window[ctx->match_window_pos]);
1517
1518                         cur_match = ctx->hash_tab[hash];
1519                         ctx->hash_tab[hash] = ctx->match_window_pos;
1520                         num_matches += lzx_lz_get_matches(ctx->window,
1521                                                           ctx->match_window_end - ctx->match_window_pos,
1522                                                           ctx->match_window_pos,
1523                                                           ctx->params.alg_params.slow.num_fast_bytes,
1524                                                           ctx->child_tab,
1525                                                           cur_match,
1526                                                           prev_len,
1527                                                           matches_ret);
1528                 }
1529
1530                 ctx->cached_matches[ctx->cached_matches_pos].len = num_matches;
1531                 ctx->cached_matches[ctx->cached_matches_pos].offset = ctx->match_window_pos;
1532
1533                 if (num_matches) {
1534                         struct raw_match *longest_match_ptr =
1535                                 &ctx->cached_matches[ctx->cached_matches_pos + 1 +
1536                                                      num_matches - 1];
1537                         u16 len = longest_match_ptr->len;
1538
1539                         /* If the longest match returned by the match-finder
1540                          * reached the number of fast bytes, extend it as much
1541                          * as possible.  */
1542                         if (len == ctx->params.alg_params.slow.num_fast_bytes) {
1543                                 const unsigned maxlen =
1544                                         min(ctx->match_window_end - ctx->match_window_pos,
1545                                             LZX_MAX_MATCH);
1546
1547                                 const u8 * const matchptr =
1548                                         &ctx->window[ctx->match_window_pos - longest_match_ptr->offset];
1549
1550                                 const u8 * const strptr =
1551                                         &ctx->window[ctx->match_window_pos];
1552
1553                                 while (len < maxlen && matchptr[len] == strptr[len])
1554                                         len++;
1555                         }
1556                         longest_match_ptr->len = len;
1557                 }
1558         }
1559         ctx->cached_matches_pos += num_matches + 1;
1560         *matches_ret = matches;
1561
1562 #if 0
1563         printf("\n");
1564         for (unsigned i = 0; i < num_matches; i++)
1565         {
1566                 printf("Len %u Offset %u\n", matches[i].len, matches[i].offset);
1567         }
1568 #endif
1569
1570         for (unsigned i = 0; i < num_matches; i++) {
1571                 LZX_ASSERT(matches[i].len <= LZX_MAX_MATCH);
1572                 if (matches[i].len >= LZX_MIN_MATCH) {
1573                         LZX_ASSERT(matches[i].offset <= ctx->match_window_pos);
1574                         LZX_ASSERT(matches[i].len <= ctx->match_window_end - ctx->match_window_pos);
1575                         LZX_ASSERT(!memcmp(&ctx->window[ctx->match_window_pos],
1576                                            &ctx->window[ctx->match_window_pos - matches[i].offset],
1577                                            matches[i].len));
1578                 }
1579         }
1580
1581         ctx->match_window_pos++;
1582         return num_matches;
1583 }
1584
1585 /*
1586  * Reverse the linked list of near-optimal matches so that they can be returned
1587  * in forwards order.
1588  *
1589  * Returns the first match in the list.
1590  */
1591 static struct raw_match
1592 lzx_lz_reverse_near_optimal_match_list(struct lzx_compressor *ctx,
1593                                        unsigned cur_pos)
1594 {
1595         unsigned prev_link, saved_prev_link;
1596         unsigned prev_match_offset, saved_prev_match_offset;
1597
1598         ctx->optimum_end_idx = cur_pos;
1599
1600         saved_prev_link = ctx->optimum[cur_pos].prev.link;
1601         saved_prev_match_offset = ctx->optimum[cur_pos].prev.match_offset;
1602
1603         do {
1604                 prev_link = saved_prev_link;
1605                 prev_match_offset = saved_prev_match_offset;
1606
1607                 saved_prev_link = ctx->optimum[prev_link].prev.link;
1608                 saved_prev_match_offset = ctx->optimum[prev_link].prev.match_offset;
1609
1610                 ctx->optimum[prev_link].next.link = cur_pos;
1611                 ctx->optimum[prev_link].next.match_offset = prev_match_offset;
1612
1613                 cur_pos = prev_link;
1614         } while (cur_pos != 0);
1615
1616         ctx->optimum_cur_idx = ctx->optimum[0].next.link;
1617
1618         return (struct raw_match)
1619                 { .len = ctx->optimum_cur_idx,
1620                   .offset = ctx->optimum[0].next.match_offset,
1621                 };
1622 }
1623
1624 /*
1625  * lzx_lz_get_near_optimal_match() -
1626  *
1627  * Choose the "best" match or literal to use at the next position in the input.
1628  *
1629  * Unlike a "greedy" parser that always takes the longest match, or even a
1630  * parser with one match/literal look-ahead like zlib, the algorithm used here
1631  * may look ahead many matches/literals to determine the best match/literal to
1632  * output next.  The motivation is that the compression ratio is improved if the
1633  * compressor can do things like use a shorter-than-possible match in order to
1634  * allow a longer match later, and also take into account the Huffman code cost
1635  * model rather than simply assuming that longer is better.  It is not a true
1636  * "optimal" parser, however, since some shortcuts can be taken; for example, if
1637  * a match is very long, the parser just chooses it immediately before too much
1638  * time is wasting considering many different alternatives that are unlikely to
1639  * be better.
1640  *
1641  * This algorithm is based on that used in 7-Zip's DEFLATE encoder.
1642  *
1643  * Each call to this function does one of two things:
1644  *
1645  * 1. Build a near-optimal sequence of matches/literals, up to some point, that
1646  *    will be returned by subsequent calls to this function, then return the
1647  *    first one.
1648  *
1649  * OR
1650  *
1651  * 2. Return the next match/literal previously computed by a call to this
1652  *    function;
1653  *
1654  * This function relies on the following state in the compressor context:
1655  *
1656  *      ctx->window          (read-only: preprocessed data being compressed)
1657  *      ctx->cost            (read-only: cost model to use)
1658  *      ctx->optimum         (internal state; leave uninitialized)
1659  *      ctx->optimum_cur_idx (must set to 0 before first call)
1660  *      ctx->optimum_end_idx (must set to 0 before first call)
1661  *      ctx->hash_tab        (must set to 0 before first call)
1662  *      ctx->cached_matches  (internal state; leave uninitialized)
1663  *      ctx->cached_matches_pos (initialize to 0 before first call; save and
1664  *                               restore value if restarting parse from a
1665  *                               certain position)
1666  *      ctx->match_window_pos (must initialize to position of next match to
1667  *                             return; subsequent calls return subsequent
1668  *                             matches)
1669  *      ctx->match_window_end (must initialize to limit of match-finding region;
1670  *                             subsequent calls use the same limit)
1671  *
1672  * The return value is a (length, offset) pair specifying the match or literal
1673  * chosen.  For literals, length is either 0 or 1 and offset is meaningless.
1674  */
1675 static struct raw_match
1676 lzx_lz_get_near_optimal_match(struct lzx_compressor * ctx)
1677 {
1678 #if 0
1679         /* Testing: literals only  */
1680         ctx->match_window_pos++;
1681         return (struct raw_match) { .len = 0 };
1682 #elif 0
1683         /* Testing: greedy parsing  */
1684         struct raw_match *matches;
1685         unsigned num_matches;
1686         struct raw_match match = {.len = 0};
1687
1688         num_matches = lzx_lz_get_matches_caching(ctx, &matches);
1689         if (num_matches) {
1690                 match = matches[num_matches - 1];
1691                 lzx_lz_skip_bytes(ctx, match.len - 1);
1692         }
1693         return match;
1694 #else
1695         unsigned num_possible_matches;
1696         struct raw_match *possible_matches;
1697         struct raw_match match;
1698         unsigned longest_match_len;
1699         unsigned len, match_idx;
1700
1701         if (ctx->optimum_cur_idx != ctx->optimum_end_idx) {
1702                 /* Case 2: Return the next match/literal already found.  */
1703                 match.len = ctx->optimum[ctx->optimum_cur_idx].next.link -
1704                                     ctx->optimum_cur_idx;
1705                 match.offset = ctx->optimum[ctx->optimum_cur_idx].next.match_offset;
1706
1707                 ctx->optimum_cur_idx = ctx->optimum[ctx->optimum_cur_idx].next.link;
1708                 return match;
1709         }
1710
1711         /* Case 1:  Compute a new list of matches/literals to return.  */
1712
1713         ctx->optimum_cur_idx = 0;
1714         ctx->optimum_end_idx = 0;
1715
1716         /* Get matches at this position.  */
1717         num_possible_matches = lzx_lz_get_matches_caching(ctx, &possible_matches);
1718
1719         /* If no matches found, return literal.  */
1720         if (num_possible_matches == 0)
1721                 return (struct raw_match){ .len = 0 };
1722
1723         /* The matches that were found are sorted by length.  Get the length of
1724          * the longest one.  */
1725         longest_match_len = possible_matches[num_possible_matches - 1].len;
1726
1727         /* Greedy heuristic:  if the longest match that was found is greater
1728          * than the number of fast bytes, return it immediately; don't both
1729          * doing more work.  */
1730         if (longest_match_len > ctx->params.alg_params.slow.num_fast_bytes) {
1731                 lzx_lz_skip_bytes(ctx, longest_match_len - 1);
1732                 return possible_matches[num_possible_matches - 1];
1733         }
1734
1735         /* Calculate the cost to reach the next position by outputting a
1736          * literal.  */
1737 #if LZX_PARAM_ACCOUNT_FOR_LRU
1738         ctx->optimum[0].queue = ctx->queue;
1739         ctx->optimum[1].queue = ctx->optimum[0].queue;
1740 #endif
1741         ctx->optimum[1].cost = lzx_literal_cost(ctx->window[ctx->match_window_pos],
1742                                                 &ctx->costs);
1743         ctx->optimum[1].prev.link = 0;
1744
1745         /* Calculate the cost to reach any position up to and including that
1746          * reached by the longest match, using the shortest (i.e. closest) match
1747          * that reaches each position.  */
1748         match_idx = 0;
1749         BUILD_BUG_ON(LZX_MIN_MATCH != 2);
1750         for (len = LZX_MIN_MATCH; len <= longest_match_len; len++) {
1751
1752                 LZX_ASSERT(match_idx < num_possible_matches);
1753
1754         #if LZX_PARAM_ACCOUNT_FOR_LRU
1755                 ctx->optimum[len].queue = ctx->optimum[0].queue;
1756         #endif
1757                 ctx->optimum[len].prev.link = 0;
1758                 ctx->optimum[len].prev.match_offset = possible_matches[match_idx].offset;
1759                 ctx->optimum[len].cost = lzx_match_cost(len,
1760                                                         possible_matches[match_idx].offset,
1761                                                         &ctx->costs
1762                                                 #if LZX_PARAM_ACCOUNT_FOR_LRU
1763                                                         , &ctx->optimum[len].queue
1764                                                 #endif
1765                                                         );
1766                 if (len == possible_matches[match_idx].len)
1767                         match_idx++;
1768         }
1769
1770         unsigned cur_pos = 0;
1771
1772         /* len_end: greatest index forward at which costs have been calculated
1773          * so far  */
1774         unsigned len_end = longest_match_len;
1775
1776
1777         for (;;) {
1778                 /* Advance to next position.  */
1779                 cur_pos++;
1780
1781                 if (cur_pos == len_end || cur_pos == LZX_PARAM_OPTIM_ARRAY_SIZE)
1782                         return lzx_lz_reverse_near_optimal_match_list(ctx, cur_pos);
1783
1784                 /* retrieve the number of matches available at this position  */
1785                 num_possible_matches = lzx_lz_get_matches_caching(ctx,
1786                                                                   &possible_matches);
1787
1788                 unsigned new_len = 0;
1789
1790                 if (num_possible_matches != 0) {
1791                         new_len = possible_matches[num_possible_matches - 1].len;
1792
1793                         /* Greedy heuristic:  if we found a match greater than
1794                          * the number of fast bytes, stop immediately.  */
1795                         if (new_len > ctx->params.alg_params.slow.num_fast_bytes) {
1796
1797                                 /* Build the list of matches to return and get
1798                                  * the first one.  */
1799                                 match = lzx_lz_reverse_near_optimal_match_list(ctx, cur_pos);
1800
1801                                 /* Append the long match to the end of the list.  */
1802                                 ctx->optimum[cur_pos].next.match_offset =
1803                                         possible_matches[num_possible_matches - 1].offset;
1804                                 ctx->optimum[cur_pos].next.link = cur_pos + new_len;
1805                                 ctx->optimum_end_idx = cur_pos + new_len;
1806
1807                                 /* Skip over the remaining bytes of the long match.  */
1808                                 lzx_lz_skip_bytes(ctx, new_len - 1);
1809
1810                                 /* Return first match in the list  */
1811                                 return match;
1812                         }
1813                 }
1814
1815                 /* Consider proceeding with a literal byte.  */
1816                 u32 cur_cost = ctx->optimum[cur_pos].cost;
1817                 u32 cur_plus_literal_cost = cur_cost +
1818                         lzx_literal_cost(ctx->window[ctx->match_window_pos - 1],
1819                                          &ctx->costs);
1820                 if (cur_plus_literal_cost < ctx->optimum[cur_pos + 1].cost) {
1821                         ctx->optimum[cur_pos + 1].cost = cur_plus_literal_cost;
1822                         ctx->optimum[cur_pos + 1].prev.link = cur_pos;
1823                 #if LZX_PARAM_ACCOUNT_FOR_LRU
1824                         ctx->optimum[cur_pos + 1].queue = ctx->optimum[cur_pos].queue;
1825                 #endif
1826                 }
1827
1828                 if (num_possible_matches == 0)
1829                         continue;
1830
1831                 /* Consider proceeding with a match.  */
1832
1833                 while (len_end < cur_pos + new_len)
1834                         ctx->optimum[++len_end].cost = ~(u32)0;
1835
1836                 match_idx = 0;
1837                 for (len = LZX_MIN_MATCH; len <= new_len; len++) {
1838                         LZX_ASSERT(match_idx < num_possible_matches);
1839                 #if LZX_PARAM_ACCOUNT_FOR_LRU
1840                         struct lzx_lru_queue q = ctx->optimum[cur_pos].queue;
1841                 #endif
1842                         u32 cost = cur_cost + lzx_match_cost(len,
1843                                                              possible_matches[match_idx].offset,
1844                                                              &ctx->costs
1845                                                         #if LZX_PARAM_ACCOUNT_FOR_LRU
1846                                                              , &q
1847                                                         #endif
1848                                                              );
1849
1850                         if (cost < ctx->optimum[cur_pos + len].cost) {
1851                                 ctx->optimum[cur_pos + len].cost = cost;
1852                                 ctx->optimum[cur_pos + len].prev.link = cur_pos;
1853                                 ctx->optimum[cur_pos + len].prev.match_offset =
1854                                                 possible_matches[match_idx].offset;
1855                         #if LZX_PARAM_ACCOUNT_FOR_LRU
1856                                 ctx->optimum[cur_pos + len].queue = q;
1857                         #endif
1858                         }
1859
1860                         if (len == possible_matches[match_idx].len)
1861                                 match_idx++;
1862                 }
1863         }
1864 #endif
1865 }
1866
1867 static unsigned
1868 lzx_huffman_code_output_cost(const u8 lens[restrict],
1869                              const freq_t freqs[restrict],
1870                              unsigned num_syms)
1871 {
1872         unsigned cost = 0;
1873
1874         for (unsigned i = 0; i < num_syms; i++)
1875                 cost += (unsigned)lens[i] * (unsigned)freqs[i];
1876
1877         return cost;
1878 }
1879
1880 /* Return the number of bits required to output the lengths for the specified
1881  * Huffman code in compressed format (encoded with a precode).  */
1882 static unsigned
1883 lzx_code_cost(const u8 lens[], const u8 prev_lens[], unsigned num_syms)
1884 {
1885         u8 output_syms[num_syms];
1886         freq_t precode_freqs[LZX_PRETREE_NUM_SYMBOLS];
1887         u8 precode_lens[LZX_PRETREE_NUM_SYMBOLS];
1888         u16 precode_codewords[LZX_PRETREE_NUM_SYMBOLS];
1889         unsigned cost = 0;
1890         unsigned num_additional_bits;
1891
1892         /* Acount for the lengths of the precode itself.  */
1893         cost += LZX_PRETREE_NUM_SYMBOLS * LZX_PRETREE_ELEMENT_SIZE;
1894
1895         lzx_build_precode(lens, prev_lens, num_syms,
1896                           precode_freqs, output_syms,
1897                           precode_lens, precode_codewords,
1898                           &num_additional_bits);
1899
1900         /* Account for all precode symbols output.  */
1901         cost += lzx_huffman_code_output_cost(precode_lens, precode_freqs,
1902                                              LZX_PRETREE_NUM_SYMBOLS);
1903
1904         /* Account for additional bits.  */
1905         cost += num_additional_bits;
1906
1907         return cost;
1908 }
1909
1910 /* Account for extra bits in the main symbols.  */
1911 static void
1912 lzx_update_mainsym_match_costs(int block_type,
1913                                u8 main_lens[LZX_MAINTREE_NUM_SYMBOLS])
1914 {
1915         unsigned i;
1916
1917         LZX_ASSERT(block_type == LZX_BLOCKTYPE_ALIGNED ||
1918                    block_type == LZX_BLOCKTYPE_VERBATIM);
1919
1920         for (i = LZX_NUM_CHARS; i < LZX_MAINTREE_NUM_SYMBOLS; i++) {
1921                 unsigned position_slot = (i >> 3) & 0x1f;
1922
1923                 /* If it's a verbatim block, add the number of extra bits
1924                  * corresponding to the position slot.
1925                  *
1926                  * If it's an aligned block and there would normally be at least
1927                  * 3 extra bits, count 3 less because they will be output as an
1928                  * aligned offset symbol instead.  */
1929                 unsigned num_extra_bits = lzx_get_num_extra_bits(position_slot);
1930
1931                 if (block_type == LZX_BLOCKTYPE_ALIGNED && num_extra_bits >= 3)
1932                         num_extra_bits -= 3;
1933                 main_lens[i] += num_extra_bits;
1934         }
1935 }
1936
1937 /*
1938  * Compute the costs, in bits, to output a compressed block as aligned offset
1939  * and verbatim.
1940  *
1941  * @block_size
1942  *      Number of bytes of uncompressed data the block represents.
1943  * @codes
1944  *      Huffman codes that will be used when outputting the block.
1945  * @prev_codes
1946  *      Huffman codes for the previous block, or all zeroes if this is the first
1947  *      block.
1948  * @freqs
1949  *      Frequencies of Huffman symbols that will be output in the block.
1950  * @aligned_cost_ret
1951  *      Cost of aligned block will be returned here.
1952  * @verbatim_cost_ret
1953  *      Cost of verbatim block will be returned here.
1954  */
1955 static void
1956 lzx_compute_compressed_block_costs(unsigned block_size,
1957                                    const struct lzx_codes *codes,
1958                                    const struct lzx_codes *prev_codes,
1959                                    const struct lzx_freqs *freqs,
1960                                    unsigned * aligned_cost_ret,
1961                                    unsigned * verbatim_cost_ret)
1962 {
1963         unsigned common_cost = 0;
1964         unsigned aligned_cost = 0;
1965         unsigned verbatim_cost = 0;
1966
1967         u8 updated_main_lens[LZX_MAINTREE_NUM_SYMBOLS];
1968
1969         /* Account for cost of block header.  */
1970         common_cost += LZX_BLOCKTYPE_NBITS;
1971         if (block_size == LZX_DEFAULT_BLOCK_SIZE)
1972                 common_cost += 1;
1973         else
1974                 common_cost += LZX_BLOCKSIZE_NBITS;
1975
1976         /* Account for cost of outputting aligned offset code.  */
1977         aligned_cost += LZX_ALIGNEDTREE_NUM_SYMBOLS * LZX_ALIGNEDTREE_ELEMENT_SIZE;
1978
1979         /* Account for cost of outputting main and length codes.  */
1980         common_cost += lzx_code_cost(codes->lens.main,
1981                                      prev_codes->lens.main,
1982                                      LZX_NUM_CHARS);
1983         common_cost += lzx_code_cost(codes->lens.main + LZX_NUM_CHARS,
1984                                      prev_codes->lens.main + LZX_NUM_CHARS,
1985                                      LZX_MAINTREE_NUM_SYMBOLS - LZX_NUM_CHARS);
1986         common_cost += lzx_code_cost(codes->lens.len,
1987                                      prev_codes->lens.len,
1988                                      LZX_LENTREE_NUM_SYMBOLS);
1989
1990         /* Account for cost to output main, length, and aligned symbols, taking
1991          * into account extra position bits.  */
1992
1993         memcpy(updated_main_lens, codes->lens.main, LZX_MAINTREE_NUM_SYMBOLS);
1994         lzx_update_mainsym_match_costs(LZX_BLOCKTYPE_VERBATIM, updated_main_lens);
1995         verbatim_cost += lzx_huffman_code_output_cost(updated_main_lens,
1996                                                       freqs->main,
1997                                                       LZX_MAINTREE_NUM_SYMBOLS);
1998         memcpy(updated_main_lens, codes->lens.main, LZX_MAINTREE_NUM_SYMBOLS);
1999         lzx_update_mainsym_match_costs(LZX_BLOCKTYPE_ALIGNED, updated_main_lens);
2000         aligned_cost += lzx_huffman_code_output_cost(updated_main_lens,
2001                                                      freqs->main,
2002                                                      LZX_MAINTREE_NUM_SYMBOLS);
2003
2004         common_cost += lzx_huffman_code_output_cost(codes->lens.len,
2005                                                     freqs->len,
2006                                                     LZX_LENTREE_NUM_SYMBOLS);
2007
2008         aligned_cost += lzx_huffman_code_output_cost(codes->lens.aligned,
2009                                                      freqs->aligned,
2010                                                      LZX_ALIGNEDTREE_NUM_SYMBOLS);
2011
2012         *aligned_cost_ret = aligned_cost + common_cost;
2013         *verbatim_cost_ret = verbatim_cost + common_cost;
2014 }
2015
2016 /* Prepare a (nonsplit) compressed block.  */
2017 static unsigned
2018 lzx_prepare_compressed_block(struct lzx_compressor *ctx, unsigned block_number,
2019                              struct lzx_codes *prev_codes)
2020 {
2021         struct lzx_block_spec *spec = &ctx->block_specs[block_number - 1];
2022         unsigned orig_cached_matches_pos = ctx->cached_matches_pos;
2023         struct lzx_lru_queue orig_queue = ctx->queue;
2024         struct lzx_freqs freqs;
2025         unsigned cost;
2026
2027         /* Here's where the real work happens.  The following loop runs one or
2028          * more times, each time using a cost model based on the Huffman codes
2029          * computed from the previous iteration (the first iteration uses a
2030          * default model).  Each iteration of the loop uses a heuristic
2031          * algorithm to divide the block into near-optimal matches/literals from
2032          * beginning to end.  */
2033         LZX_ASSERT(ctx->params.alg_params.slow.num_optim_passes >= 1);
2034         spec->num_chosen_matches = 0;
2035         for (unsigned pass = 0; pass < ctx->params.alg_params.slow.num_optim_passes; pass++)
2036         {
2037                 LZX_DEBUG("Block %u: Match-choosing pass %u of %u",
2038                           block_number, pass + 1,
2039                           ctx->params.alg_params.slow.num_optim_passes);
2040
2041                 /* Reset frequency tables.  */
2042                 memset(&freqs, 0, sizeof(freqs));
2043
2044                 /* Reset match offset LRU queue.  */
2045                 ctx->queue = orig_queue;
2046
2047                 /* Reset match-finding position.  */
2048                 ctx->cached_matches_pos = orig_cached_matches_pos;
2049                 ctx->match_window_pos = spec->window_pos;
2050                 ctx->match_window_end = spec->window_pos + spec->block_size;
2051
2052                 /* Set cost model.  */
2053                 lzx_set_costs(ctx, &spec->codes.lens);
2054
2055                 unsigned window_pos = spec->window_pos;
2056                 unsigned end = window_pos + spec->block_size;
2057
2058                 while (window_pos < end) {
2059                         struct raw_match match;
2060                         struct lzx_match lzx_match;
2061
2062                         match = lzx_lz_get_near_optimal_match(ctx);
2063
2064                         if (match.len >= LZX_MIN_MATCH) {
2065
2066                                 /* Best to output a match here.  */
2067
2068                                 LZX_ASSERT(match.len <= LZX_MAX_MATCH);
2069                                 LZX_ASSERT(!memcmp(&ctx->window[window_pos],
2070                                                    &ctx->window[window_pos - match.offset],
2071                                                    match.len));
2072
2073                                 /* Tally symbol frequencies.  */
2074                                 lzx_match.data = lzx_record_match(match.offset,
2075                                                                   match.len,
2076                                                                   &freqs,
2077                                                                   &ctx->queue);
2078
2079                                 window_pos += match.len;
2080                         } else {
2081                                 /* Best to output a literal here.  */
2082
2083                                 /* Tally symbol frequencies.  */
2084                                 lzx_match.data = lzx_record_literal(ctx->window[window_pos],
2085                                                                     &freqs);
2086
2087                                 window_pos += 1;
2088                         }
2089
2090                         /* If it's the last pass, save the match/literal in
2091                          * intermediate form.  */
2092                         if (pass == ctx->params.alg_params.slow.num_optim_passes - 1) {
2093                                 ctx->chosen_matches[spec->chosen_matches_start_pos +
2094                                                     spec->num_chosen_matches] = lzx_match;
2095
2096                                 spec->num_chosen_matches++;
2097                         }
2098                 }
2099                 LZX_ASSERT(window_pos == end);
2100
2101                 /* Build Huffman codes using the new frequencies.  */
2102                 lzx_make_huffman_codes(&freqs, &spec->codes);
2103
2104                 /* The first time we get here is when the full input has been
2105                  * processed, so the match-finding is done.  */
2106                 ctx->matches_already_found = true;
2107         }
2108
2109         LZX_DEBUG("Block %u: saved %u matches/literals @ %u",
2110                   block_number, spec->num_chosen_matches,
2111                   spec->chosen_matches_start_pos);
2112
2113         unsigned aligned_cost;
2114         unsigned verbatim_cost;
2115
2116         lzx_compute_compressed_block_costs(spec->block_size,
2117                                            &spec->codes,
2118                                            prev_codes,
2119                                            &freqs,
2120                                            &aligned_cost,
2121                                            &verbatim_cost);
2122
2123         /* Choose whether to make the block aligned offset or verbatim.  */
2124         if (aligned_cost < verbatim_cost) {
2125                 spec->block_type = LZX_BLOCKTYPE_ALIGNED;
2126                 cost = aligned_cost;
2127                 LZX_DEBUG("Using aligned block (cost %u vs %u for verbatim)",
2128                           aligned_cost, verbatim_cost);
2129         } else {
2130                 spec->block_type = LZX_BLOCKTYPE_VERBATIM;
2131                 cost = verbatim_cost;
2132                 LZX_DEBUG("Using verbatim block (cost %u vs %u for aligned)",
2133                           verbatim_cost, aligned_cost);
2134         }
2135
2136         LZX_DEBUG("Block %u is %u => %u bytes unsplit.",
2137                   block_number, spec->block_size, cost / 8);
2138
2139         return cost;
2140 }
2141
2142 /*
2143  * lzx_prepare_block_recursive() -
2144  *
2145  * Given a (possibly nonproper) sub-sequence of the preprocessed input, compute
2146  * the LZX block(s) that it should be output as.
2147  *
2148  * This function initially considers the case where the given sub-sequence of
2149  * the preprocessed input be output as a single block.  This block is calculated
2150  * and its cost (number of bits required to output it) is computed.
2151  *
2152  * Then, if @max_split_level is greater than zero, a split into two evenly sized
2153  * subblocks is considered.  The block is recursively split in this way,
2154  * potentially up to the depth specified by @max_split_level.  The cost of the
2155  * split block is compared to the cost of the single block, and the lower cost
2156  * solution is used.
2157  *
2158  * For each compressed output block computed, the sequence of matches/literals
2159  * and the corresponding Huffman codes for the block are produced and saved.
2160  *
2161  * The return value is the approximate number of bits the block (or all
2162  * subblocks, in the case that the split block had lower cost), will take up
2163  * when written to the compressed output.
2164  */
2165 static unsigned
2166 lzx_prepare_block_recursive(struct lzx_compressor * ctx,
2167                             unsigned block_number,
2168                             unsigned max_split_level,
2169                             struct lzx_codes **prev_codes_p)
2170 {
2171         struct lzx_block_spec *spec = &ctx->block_specs[block_number - 1];
2172         unsigned cost;
2173         unsigned orig_cached_matches_pos;
2174         struct lzx_lru_queue orig_queue, nonsplit_queue;
2175         struct lzx_codes *prev_codes = *prev_codes_p;
2176
2177         LZX_DEBUG("Preparing block %u...", block_number);
2178
2179         /* Save positions of chosen and cached matches, and the match offset LRU
2180          * queue, so that they can be restored if splitting is attempted.  */
2181         orig_cached_matches_pos = ctx->cached_matches_pos;
2182         orig_queue = ctx->queue;
2183
2184         /* Consider outputting the input subsequence as a single block.  */
2185         spec->is_split = 0;
2186         cost = lzx_prepare_compressed_block(ctx, block_number, prev_codes);
2187         nonsplit_queue = ctx->queue;
2188
2189         *prev_codes_p = &spec->codes;
2190
2191         /* If the maximum split level is at least one, consider splitting the
2192          * block in two.  */
2193         if (max_split_level--) {
2194
2195                 LZX_DEBUG("Calculating split of block %u...", block_number);
2196
2197                 struct lzx_block_spec *spec1, *spec2;
2198                 unsigned split_cost;
2199
2200                 ctx->cached_matches_pos = orig_cached_matches_pos;
2201                 ctx->queue = orig_queue;
2202
2203                 /* Prepare and get the cost of the first sub-block.  */
2204                 spec1 = &ctx->block_specs[block_number * 2 - 1];
2205                 spec1->codes.lens = spec->codes.lens;
2206                 spec1->window_pos = spec->window_pos;
2207                 spec1->block_size = spec->block_size / 2;
2208                 spec1->chosen_matches_start_pos = spec->chosen_matches_start_pos +
2209                                                   LZX_MAX_WINDOW_SIZE;
2210                 split_cost = lzx_prepare_block_recursive(ctx,
2211                                                          block_number * 2,
2212                                                          max_split_level,
2213                                                          &prev_codes);
2214
2215                 /* Prepare and get the cost of the second sub-block.  */
2216                 spec2 = spec1 + 1;
2217                 spec2->codes.lens = spec->codes.lens;
2218                 spec2->window_pos = spec->window_pos + spec1->block_size;
2219                 spec2->block_size = spec->block_size - spec1->block_size;
2220                 spec2->chosen_matches_start_pos = spec1->chosen_matches_start_pos +
2221                                                   spec1->block_size;
2222                 split_cost += lzx_prepare_block_recursive(ctx,
2223                                                           block_number * 2 + 1,
2224                                                           max_split_level,
2225                                                           &prev_codes);
2226
2227                 /* Compare the cost of the whole block with that of the split
2228                  * block.  Choose the lower cost solution.  */
2229                 if (split_cost < cost) {
2230                         LZX_DEBUG("Splitting block %u is worth it "
2231                                   "(%u => %u bytes).",
2232                                   block_number, cost / 8, split_cost / 8);
2233                         spec->is_split = 1;
2234                         cost = split_cost;
2235                         *prev_codes_p = prev_codes;
2236                 } else {
2237                         LZX_DEBUG("Splitting block %u is NOT worth it "
2238                                   "(%u => %u bytes).",
2239                                   block_number, cost / 8, split_cost / 8);
2240                         ctx->queue = nonsplit_queue;
2241                 }
2242         }
2243
2244         return cost;
2245 }
2246
2247 /* Empirical averages  */
2248 static const u8 lzx_default_mainsym_costs[LZX_MAINTREE_NUM_SYMBOLS] = {
2249         7, 9, 9, 10, 9, 10, 10, 10, 9, 10, 9, 10, 10, 9, 10, 10, 9, 10, 10, 11,
2250         10, 10, 10, 11, 10, 11, 11, 11, 10, 11, 11, 11, 8, 11, 9, 10, 9, 10, 11,
2251         11, 9, 9, 11, 10, 10, 9, 9, 9, 8, 8, 8, 8, 8, 9, 9, 9, 8, 8, 9, 9, 9, 9,
2252         10, 10, 10, 8, 9, 8, 8, 8, 8, 9, 9, 9, 10, 10, 8, 8, 9, 9, 8, 10, 9, 8,
2253         8, 9, 8, 9, 9, 10, 10, 10, 9, 10, 11, 9, 10, 8, 9, 8, 8, 8, 8, 9, 8, 8,
2254         9, 9, 8, 8, 8, 8, 8, 10, 8, 8, 7, 8, 9, 9, 9, 9, 10, 11, 10, 10, 11, 11,
2255         10, 11, 11, 10, 10, 11, 11, 11, 10, 10, 11, 10, 11, 10, 11, 11, 10, 11,
2256         11, 12, 11, 11, 11, 12, 11, 11, 11, 11, 11, 11, 11, 12, 10, 11, 11, 11,
2257         11, 11, 11, 12, 11, 11, 11, 11, 11, 12, 11, 11, 10, 11, 11, 11, 11, 11,
2258         11, 11, 10, 11, 11, 11, 11, 11, 11, 11, 10, 11, 11, 11, 11, 11, 11, 11,
2259         10, 11, 11, 11, 11, 11, 11, 11, 10, 11, 11, 11, 11, 12, 11, 11, 10, 11,
2260         11, 11, 11, 12, 11, 11, 10, 11, 11, 11, 10, 12, 11, 11, 10, 10, 11, 10,
2261         10, 11, 11, 11, 10, 11, 11, 11, 10, 11, 11, 11, 10, 11, 11, 11, 10, 11,
2262         10, 9, 8, 7, 10, 10, 11, 10, 11, 7, 9, 9, 11, 11, 11, 12, 11, 9, 10, 10,
2263         12, 12, 13, 13, 12, 11, 10, 12, 12, 14, 14, 14, 13, 12, 9, 12, 13, 14,
2264         14, 14, 14, 14, 9, 10, 13, 14, 14, 14, 14, 14, 9, 9, 11, 11, 13, 13, 13,
2265         14, 9, 9, 11, 12, 12, 13, 13, 13, 8, 8, 11, 11, 12, 12, 12, 11, 9, 9,
2266         10, 11, 12, 12, 12, 11, 8, 9, 10, 10, 11, 12, 11, 10, 9, 9, 10, 11, 11,
2267         12, 11, 10, 8, 9, 10, 10, 11, 11, 11, 9, 9, 9, 10, 11, 11, 11, 11, 9, 8,
2268         8, 10, 10, 11, 11, 11, 9, 9, 9, 10, 10, 11, 11, 11, 9, 9, 8, 9, 10, 11,
2269         11, 11, 9, 10, 9, 10, 11, 11, 11, 11, 9, 14, 9, 9, 10, 10, 11, 10, 9,
2270         14, 9, 10, 11, 11, 11, 11, 9, 14, 9, 10, 10, 11, 11, 11, 9, 14, 10, 10,
2271         11, 11, 12, 11, 10, 14, 10, 10, 10, 11, 11, 11, 10, 14, 11, 11, 11, 11,
2272         12, 12, 10, 14, 10, 11, 11, 11, 12, 11, 10, 14, 11, 11, 11, 12, 12, 12,
2273         11, 15, 11, 11, 11, 12, 12, 12, 11, 14, 12, 12, 12, 12, 13, 12, 11, 15,
2274         12, 12, 12, 13, 13, 13, 12, 15, 14, 13, 14, 14, 14, 14, 13,
2275 };
2276
2277 /* Empirical averages  */
2278 static const u8 lzx_default_lensym_costs[LZX_LENTREE_NUM_SYMBOLS] = {
2279         5, 5, 5, 5, 5, 6, 5, 5, 6, 7, 7, 7, 8, 8, 7, 8, 9, 9, 9, 9, 10, 9, 9,
2280         10, 9, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 12, 12, 12, 11, 12, 12,
2281         12, 12, 12, 12, 13, 12, 12, 12, 13, 12, 13, 13, 12, 12, 13, 12, 13, 13,
2282         13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 14, 13, 14, 13, 14, 13,
2283         14, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
2284         14, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
2285         14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
2286         14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
2287         14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
2288         14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
2289         14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
2290         14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
2291         14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
2292         14, 14, 14, 14, 14, 14, 14, 14, 14, 10,
2293 };
2294
2295 /*
2296  * Set default symbol costs.
2297  */
2298 static void
2299 lzx_set_default_costs(struct lzx_lens * lens)
2300 {
2301         unsigned i;
2302
2303 #if LZX_PARAM_USE_EMPIRICAL_DEFAULT_COSTS
2304         memcpy(&lens->main, lzx_default_mainsym_costs, LZX_MAINTREE_NUM_SYMBOLS);
2305         memcpy(&lens->len, lzx_default_lensym_costs, LZX_LENTREE_NUM_SYMBOLS);
2306
2307 #else
2308         /* Literal symbols  */
2309         for (i = 0; i < LZX_NUM_CHARS; i++)
2310                 lens->main[i] = 8;
2311
2312         /* Match header symbols  */
2313         for (; i < LZX_MAINTREE_NUM_SYMBOLS; i++)
2314                 lens->main[i] = 10;
2315
2316         /* Length symbols  */
2317         for (i = 0; i < LZX_LENTREE_NUM_SYMBOLS; i++)
2318                 lens->len[i] = 8;
2319 #endif
2320
2321         /* Aligned offset symbols  */
2322         for (i = 0; i < LZX_ALIGNEDTREE_NUM_SYMBOLS; i++)
2323                 lens->aligned[i] = 3;
2324 }
2325
2326 /*
2327  * lzx_prepare_blocks() -
2328  *
2329  * Calculate the blocks to split the preprocessed data into.
2330  *
2331  * Input ---  the preprocessed data:
2332  *
2333  *      ctx->window[]
2334  *      ctx->window_size
2335  *
2336  * Working space:
2337  *      Match finding:
2338  *              ctx->hash_tab
2339  *              ctx->child_tab
2340  *              ctx->cached_matches
2341  *              ctx->cached_matches_pos
2342  *              ctx->matches_already_found
2343  *
2344  *      Block cost modeling:
2345  *              ctx->costs
2346  *              ctx->block_specs (also an output)
2347  *
2348  *      Match choosing:
2349  *              ctx->optimum
2350  *              ctx->optimum_cur_idx
2351  *              ctx->optimum_end_idx
2352  *              ctx->chosen_matches (also an output)
2353  *
2354  * Output --- the block specifications and the corresponding match/literal data:
2355  *
2356  *      ctx->block_specs[]
2357  *      ctx->chosen_matches[]
2358  *
2359  * The return value is the approximate number of bits the compressed data will
2360  * take up.
2361  */
2362 static unsigned
2363 lzx_prepare_blocks(struct lzx_compressor * ctx)
2364 {
2365         /* This function merely does some initializations, then passes control
2366          * to lzx_prepare_block_recursive().  */
2367
2368         /* 1. Initialize match-finding variables.  */
2369
2370         /* Zero all entries in the hash table, indicating that no length-3
2371          * character sequences have been discovered in the input yet.  */
2372         memset(ctx->hash_tab, 0, LZX_LZ_HASH_SIZE * 2 * sizeof(ctx->hash_tab[0]));
2373         if (ctx->params.alg_params.slow.use_len2_matches)
2374                 memset(ctx->digram_tab, 0, 256 * 256 * sizeof(ctx->digram_tab[0]));
2375         /* Note: ctx->child_tab need not be initialized.  */
2376
2377         /* No matches have been found and cached yet.  */
2378         ctx->cached_matches_pos = 0;
2379         ctx->matches_already_found = false;
2380
2381         /* 2. Initialize match-choosing variables.  */
2382         ctx->optimum_cur_idx = 0;
2383         ctx->optimum_end_idx = 0;
2384         /* Note: ctx->optimum need not be initialized.  */
2385         ctx->block_specs[0].chosen_matches_start_pos = 0;
2386
2387         /* 3. Set block 1 (index 0) to represent the entire input data.  */
2388         ctx->block_specs[0].block_size = ctx->window_size;
2389         ctx->block_specs[0].window_pos = 0;
2390
2391         /* 4. Set up a default Huffman symbol cost model for block 1 (index 0).
2392          * The model will be refined later.  */
2393         lzx_set_default_costs(&ctx->block_specs[0].codes.lens);
2394
2395         /* 5. Initialize the match offset LRU queue.  */
2396         ctx->queue = (struct lzx_lru_queue){1, 1, 1};
2397
2398         /* 6. Pass control to recursive procedure.  */
2399         struct lzx_codes * prev_codes = &ctx->zero_codes;
2400         return lzx_prepare_block_recursive(ctx, 1,
2401                                            ctx->params.alg_params.slow.num_split_passes,
2402                                            &prev_codes);
2403 }
2404
2405 /*
2406  * This is the fast version of lzx_prepare_blocks().  This version "quickly"
2407  * prepares a single compressed block containing the entire input.  See the
2408  * description of the "Fast algorithm" at the beginning of this file for more
2409  * information.
2410  *
2411  * Input ---  the preprocessed data:
2412  *
2413  *      ctx->window[]
2414  *      ctx->window_size
2415  *
2416  * Working space:
2417  *      ctx->queue
2418  *
2419  * Output --- the block specifications and the corresponding match/literal data:
2420  *
2421  *      ctx->block_specs[]
2422  *      ctx->chosen_matches[]
2423  */
2424 static void
2425 lzx_prepare_block_fast(struct lzx_compressor * ctx)
2426 {
2427         unsigned num_matches;
2428         struct lzx_freqs freqs;
2429         struct lzx_block_spec *spec;
2430
2431         /* Parameters to hash chain LZ match finder  */
2432         static const struct lz_params lzx_lz_params = {
2433                 /* LZX_MIN_MATCH == 2, but 2-character matches are rarely
2434                  * useful; the minimum match for compression is set to 3
2435                  * instead. */
2436                 .min_match      = 3,
2437                 .max_match      = LZX_MAX_MATCH,
2438                 .good_match     = LZX_MAX_MATCH,
2439                 .nice_match     = LZX_MAX_MATCH,
2440                 .max_chain_len  = LZX_MAX_MATCH,
2441                 .max_lazy_match = LZX_MAX_MATCH,
2442                 .too_far        = 4096,
2443         };
2444
2445         /* Initialize symbol frequencies and match offset LRU queue.  */
2446         memset(&freqs, 0, sizeof(struct lzx_freqs));
2447         ctx->queue = (struct lzx_lru_queue){ 1, 1, 1 };
2448
2449         /* Determine series of matches/literals to output.  */
2450         num_matches = lz_analyze_block(ctx->window,
2451                                        ctx->window_size,
2452                                        (u32*)ctx->chosen_matches,
2453                                        lzx_record_match,
2454                                        lzx_record_literal,
2455                                        &freqs,
2456                                        &ctx->queue,
2457                                        &freqs,
2458                                        &lzx_lz_params);
2459
2460
2461         /* Set up block specification.  */
2462         spec = &ctx->block_specs[0];
2463         spec->is_split = 0;
2464         spec->block_type = LZX_BLOCKTYPE_ALIGNED;
2465         spec->window_pos = 0;
2466         spec->block_size = ctx->window_size;
2467         spec->num_chosen_matches = num_matches;
2468         spec->chosen_matches_start_pos = 0;
2469         lzx_make_huffman_codes(&freqs, &spec->codes);
2470 }
2471
2472 static void
2473 do_call_insn_translation(u32 *call_insn_target, int input_pos,
2474                          s32 file_size)
2475 {
2476         s32 abs_offset;
2477         s32 rel_offset;
2478
2479         rel_offset = le32_to_cpu(*call_insn_target);
2480         if (rel_offset >= -input_pos && rel_offset < file_size) {
2481                 if (rel_offset < file_size - input_pos) {
2482                         /* "good translation" */
2483                         abs_offset = rel_offset + input_pos;
2484                 } else {
2485                         /* "compensating translation" */
2486                         abs_offset = rel_offset - file_size;
2487                 }
2488                 *call_insn_target = cpu_to_le32(abs_offset);
2489         }
2490 }
2491
2492 /* This is the reverse of undo_call_insn_preprocessing() in lzx-decompress.c.
2493  * See the comment above that function for more information.  */
2494 static void
2495 do_call_insn_preprocessing(u8 data[], int size)
2496 {
2497         for (int i = 0; i < size - 10; i++) {
2498                 if (data[i] == 0xe8) {
2499                         do_call_insn_translation((u32*)&data[i + 1], i,
2500                                                  LZX_WIM_MAGIC_FILESIZE);
2501                         i += 4;
2502                 }
2503         }
2504 }
2505
2506 /* API function documented in wimlib.h  */
2507 WIMLIBAPI unsigned
2508 wimlib_lzx_compress2(const void                 * const restrict uncompressed_data,
2509                      unsigned                     const          uncompressed_len,
2510                      void                       * const restrict compressed_data,
2511                      struct wimlib_lzx_context  * const restrict lzx_ctx)
2512 {
2513         struct lzx_compressor *ctx = (struct lzx_compressor*)lzx_ctx;
2514         struct output_bitstream ostream;
2515         unsigned compressed_len;
2516
2517         if (uncompressed_len < 100) {
2518                 LZX_DEBUG("Too small to bother compressing.");
2519                 return 0;
2520         }
2521
2522         if (uncompressed_len > 32768) {
2523                 LZX_DEBUG("Only up to 32768 bytes of uncompressed data are supported.");
2524                 return 0;
2525         }
2526
2527         wimlib_assert(lzx_ctx != NULL);
2528
2529         LZX_DEBUG("Attempting to compress %u bytes...", uncompressed_len);
2530
2531         /* The input data must be preprocessed.  To avoid changing the original
2532          * input, copy it to a temporary buffer.  */
2533         memcpy(ctx->window, uncompressed_data, uncompressed_len);
2534         ctx->window_size = uncompressed_len;
2535
2536         /* This line is unnecessary; it just avoids inconsequential accesses of
2537          * uninitialized memory that would show up in memory-checking tools such
2538          * as valgrind.  */
2539         memset(&ctx->window[ctx->window_size], 0, 12);
2540
2541         LZX_DEBUG("Preprocessing data...");
2542
2543         /* Before doing any actual compression, do the call instruction (0xe8
2544          * byte) translation on the uncompressed data.  */
2545         do_call_insn_preprocessing(ctx->window, ctx->window_size);
2546
2547         LZX_DEBUG("Preparing blocks...");
2548
2549         /* Prepare the compressed data.  */
2550         if (ctx->params.algorithm == WIMLIB_LZX_ALGORITHM_FAST)
2551                 lzx_prepare_block_fast(ctx);
2552         else
2553                 lzx_prepare_blocks(ctx);
2554
2555         LZX_DEBUG("Writing compressed blocks...");
2556
2557         /* Generate the compressed data.  */
2558         init_output_bitstream(&ostream, compressed_data, ctx->window_size - 1);
2559         lzx_write_all_blocks(ctx, &ostream);
2560
2561         LZX_DEBUG("Flushing bitstream...");
2562         if (flush_output_bitstream(&ostream)) {
2563                 /* If the bitstream cannot be flushed, then the output space was
2564                  * exhausted.  */
2565                 LZX_DEBUG("Data did not compress to less than original length!");
2566                 return 0;
2567         }
2568
2569         /* Compute the length of the compressed data.  */
2570         compressed_len = ostream.bit_output - (u8*)compressed_data;
2571
2572         LZX_DEBUG("Done: compressed %u => %u bytes.",
2573                   uncompressed_len, compressed_len);
2574
2575 #if defined(ENABLE_LZX_DEBUG) || defined(ENABLE_VERIFY_COMPRESSION)
2576         /* Verify that we really get the same thing back when decompressing.  */
2577         {
2578                 u8 buf[uncompressed_len];
2579                 int ret;
2580                 unsigned i;
2581
2582                 ret = wimlib_lzx_decompress(compressed_data, compressed_len,
2583                                             buf, uncompressed_len);
2584                 if (ret) {
2585                         ERROR("Failed to decompress data we "
2586                               "compressed using LZX algorithm");
2587                         wimlib_assert(0);
2588                         return 0;
2589                 }
2590
2591                 bool bad = false;
2592                 const u8 * udata = uncompressed_data;
2593                 for (i = 0; i < uncompressed_len; i++) {
2594                         if (buf[i] != udata[i]) {
2595                                 bad = true;
2596                                 ERROR("Data we compressed using LZX algorithm "
2597                                       "didn't decompress to original "
2598                                       "(difference at idx %u: c %#02x, u %#02x)",
2599                                       i, buf[i], udata[i]);
2600                         }
2601                 }
2602                 if (bad) {
2603                         wimlib_assert(0);
2604                         return 0;
2605                 }
2606         }
2607 #endif
2608         return compressed_len;
2609 }
2610
2611 static bool
2612 lzx_params_compatible(const struct wimlib_lzx_params *oldparams,
2613                       const struct wimlib_lzx_params *newparams)
2614 {
2615         return 0 == memcmp(oldparams, newparams, sizeof(struct wimlib_lzx_params));
2616 }
2617
2618 /* API function documented in wimlib.h  */
2619 WIMLIBAPI int
2620 wimlib_lzx_alloc_context(const struct wimlib_lzx_params *params,
2621                          struct wimlib_lzx_context **ctx_pp)
2622 {
2623
2624         LZX_DEBUG("Allocating LZX context...");
2625
2626         struct lzx_compressor *ctx;
2627
2628         static const struct wimlib_lzx_params fast_default = {
2629                 .size_of_this = sizeof(struct wimlib_lzx_params),
2630                 .algorithm = WIMLIB_LZX_ALGORITHM_FAST,
2631                 .use_defaults = 0,
2632                 .alg_params = {
2633                         .fast = {
2634                         },
2635                 },
2636         };
2637         static const struct wimlib_lzx_params slow_default = {
2638                 .size_of_this = sizeof(struct wimlib_lzx_params),
2639                 .algorithm = WIMLIB_LZX_ALGORITHM_SLOW,
2640                 .use_defaults = 0,
2641                 .alg_params = {
2642                         .slow = {
2643                                 .use_len2_matches = 1,
2644                                 .num_fast_bytes = 32,
2645                                 .num_optim_passes = 3,
2646                                 .num_split_passes = 3,
2647                                 .main_nostat_cost = 15,
2648                                 .len_nostat_cost = 15,
2649                                 .aligned_nostat_cost = 7,
2650                         },
2651                 },
2652         };
2653
2654         if (params == NULL) {
2655                 LZX_DEBUG("Using default algorithm and parameters.");
2656                 params = &slow_default;
2657         }
2658
2659         if (params->algorithm != WIMLIB_LZX_ALGORITHM_SLOW &&
2660             params->algorithm != WIMLIB_LZX_ALGORITHM_FAST)
2661         {
2662                 LZX_DEBUG("Invalid algorithm.");
2663                 return WIMLIB_ERR_INVALID_PARAM;
2664         }
2665
2666         if (params->use_defaults) {
2667                 if (params->algorithm == WIMLIB_LZX_ALGORITHM_SLOW)
2668                         params = &slow_default;
2669                 else
2670                         params = &fast_default;
2671         }
2672
2673         if (params->size_of_this != sizeof(struct wimlib_lzx_params)) {
2674                 LZX_DEBUG("Invalid parameter structure size!");
2675                 return WIMLIB_ERR_INVALID_PARAM;
2676         }
2677
2678         if (params->algorithm == WIMLIB_LZX_ALGORITHM_SLOW) {
2679                 if (params->alg_params.slow.num_fast_bytes < 3 ||
2680                     params->alg_params.slow.num_fast_bytes > 257)
2681                 {
2682                         LZX_DEBUG("Invalid number of fast bytes!");
2683                         return WIMLIB_ERR_INVALID_PARAM;
2684                 }
2685
2686                 if (params->alg_params.slow.num_optim_passes < 1)
2687                 {
2688                         LZX_DEBUG("Invalid number of optimization passes!");
2689                         return WIMLIB_ERR_INVALID_PARAM;
2690                 }
2691
2692                 if (params->alg_params.slow.main_nostat_cost < 1 ||
2693                     params->alg_params.slow.main_nostat_cost > 16)
2694                 {
2695                         LZX_DEBUG("Invalid main_nostat_cost!");
2696                         return WIMLIB_ERR_INVALID_PARAM;
2697                 }
2698
2699                 if (params->alg_params.slow.len_nostat_cost < 1 ||
2700                     params->alg_params.slow.len_nostat_cost > 16)
2701                 {
2702                         LZX_DEBUG("Invalid len_nostat_cost!");
2703                         return WIMLIB_ERR_INVALID_PARAM;
2704                 }
2705
2706                 if (params->alg_params.slow.aligned_nostat_cost < 1 ||
2707                     params->alg_params.slow.aligned_nostat_cost > 8)
2708                 {
2709                         LZX_DEBUG("Invalid aligned_nostat_cost!");
2710                         return WIMLIB_ERR_INVALID_PARAM;
2711                 }
2712         }
2713
2714         if (ctx_pp == NULL) {
2715                 LZX_DEBUG("Check parameters only.");
2716                 return 0;
2717         }
2718
2719         ctx = *(struct lzx_compressor**)ctx_pp;
2720
2721         if (ctx && lzx_params_compatible(&ctx->params, params))
2722                 return 0;
2723
2724         LZX_DEBUG("Allocating memory.");
2725
2726         ctx = MALLOC(sizeof(struct lzx_compressor));
2727         if (ctx == NULL)
2728                 goto err;
2729
2730         size_t block_specs_length;
2731
2732         if (params->algorithm == WIMLIB_LZX_ALGORITHM_SLOW)
2733                 block_specs_length = ((1 << (params->alg_params.slow.num_split_passes + 1)) - 1);
2734         else
2735                 block_specs_length = 1;
2736         ctx->block_specs = MALLOC(block_specs_length * sizeof(ctx->block_specs[0]));
2737         if (ctx->block_specs == NULL)
2738                 goto err_free_ctx;
2739
2740         if (params->algorithm == WIMLIB_LZX_ALGORITHM_SLOW) {
2741                 ctx->hash_tab = MALLOC((LZX_LZ_HASH_SIZE + 2 * LZX_MAX_WINDOW_SIZE) *
2742                                         sizeof(ctx->hash_tab[0]));
2743                 if (ctx->hash_tab == NULL)
2744                         goto err_free_block_specs;
2745                 ctx->child_tab = ctx->hash_tab + LZX_LZ_HASH_SIZE;
2746         } else {
2747                 ctx->hash_tab = NULL;
2748                 ctx->child_tab = NULL;
2749         }
2750
2751         if (params->algorithm == WIMLIB_LZX_ALGORITHM_SLOW &&
2752             params->alg_params.slow.use_len2_matches)
2753         {
2754                 ctx->digram_tab = MALLOC(256 * 256 * sizeof(ctx->digram_tab[0]));
2755                 if (ctx->digram_tab == NULL)
2756                         goto err_free_hash_tab;
2757         } else {
2758                 ctx->digram_tab = NULL;
2759         }
2760
2761         if (params->algorithm == WIMLIB_LZX_ALGORITHM_SLOW) {
2762                 ctx->cached_matches = MALLOC(10 * LZX_MAX_WINDOW_SIZE *
2763                                              sizeof(ctx->cached_matches[0]));
2764                 if (ctx->cached_matches == NULL)
2765                         goto err_free_digram_tab;
2766         } else {
2767                 ctx->cached_matches = NULL;
2768         }
2769
2770         if (params->algorithm == WIMLIB_LZX_ALGORITHM_SLOW) {
2771                 ctx->optimum = MALLOC((LZX_PARAM_OPTIM_ARRAY_SIZE + LZX_MAX_MATCH) *
2772                                        sizeof(ctx->optimum[0]));
2773                 if (ctx->optimum == NULL)
2774                         goto err_free_cached_matches;
2775         } else {
2776                 ctx->optimum = NULL;
2777         }
2778
2779         size_t chosen_matches_length;
2780         if (params->algorithm == WIMLIB_LZX_ALGORITHM_SLOW)
2781                 chosen_matches_length = LZX_MAX_WINDOW_SIZE *
2782                                         (params->alg_params.slow.num_split_passes + 1);
2783         else
2784                 chosen_matches_length = LZX_MAX_WINDOW_SIZE;
2785
2786         ctx->chosen_matches = MALLOC(chosen_matches_length *
2787                                      sizeof(ctx->chosen_matches[0]));
2788         if (ctx->chosen_matches == NULL)
2789                 goto err_free_optimum;
2790
2791         memcpy(&ctx->params, params, sizeof(struct wimlib_lzx_params));
2792         memset(&ctx->zero_codes, 0, sizeof(ctx->zero_codes));
2793
2794         LZX_DEBUG("Successfully allocated new LZX context.");
2795
2796         wimlib_lzx_free_context(*ctx_pp);
2797         *ctx_pp = (struct wimlib_lzx_context*)ctx;
2798         return 0;
2799
2800 err_free_optimum:
2801         FREE(ctx->optimum);
2802 err_free_cached_matches:
2803         FREE(ctx->cached_matches);
2804 err_free_digram_tab:
2805         FREE(ctx->digram_tab);
2806 err_free_hash_tab:
2807         FREE(ctx->hash_tab);
2808 err_free_block_specs:
2809         FREE(ctx->block_specs);
2810 err_free_ctx:
2811         FREE(ctx);
2812 err:
2813         LZX_DEBUG("Ran out of memory.");
2814         return WIMLIB_ERR_NOMEM;
2815 }
2816
2817 /* API function documented in wimlib.h  */
2818 WIMLIBAPI void
2819 wimlib_lzx_free_context(struct wimlib_lzx_context *_ctx)
2820 {
2821         struct lzx_compressor *ctx = (struct lzx_compressor*)_ctx;
2822
2823         if (ctx) {
2824                 FREE(ctx->chosen_matches);
2825                 FREE(ctx->optimum);
2826                 FREE(ctx->cached_matches);
2827                 FREE(ctx->digram_tab);
2828                 FREE(ctx->hash_tab);
2829                 FREE(ctx->block_specs);
2830                 FREE(ctx);
2831         }
2832 }
2833
2834 /* API function documented in wimlib.h  */
2835 WIMLIBAPI unsigned
2836 wimlib_lzx_compress(const void * const restrict uncompressed_data,
2837                     unsigned     const          uncompressed_len,
2838                     void       * const restrict compressed_data)
2839 {
2840         int ret;
2841         struct wimlib_lzx_context *ctx;
2842         unsigned compressed_len;
2843
2844         ret = wimlib_lzx_alloc_context(NULL, &ctx);
2845         if (ret) {
2846                 wimlib_assert(ret != WIMLIB_ERR_INVALID_PARAM);
2847                 WARNING("Couldn't allocate LZX compression context: %"TS"",
2848                         wimlib_get_error_string(ret));
2849                 return 0;
2850         }
2851
2852         compressed_len = wimlib_lzx_compress2(uncompressed_data,
2853                                               uncompressed_len,
2854                                               compressed_data,
2855                                               ctx);
2856
2857         wimlib_lzx_free_context(ctx);
2858
2859         return compressed_len;
2860 }