4 * A compressor that produces output compatible with the XPRESS (Huffman
5 * version) compression format.
9 * Copyright (C) 2012, 2013, 2014 Eric Biggers
11 * This file is part of wimlib, a library for working with WIM files.
13 * wimlib is free software; you can redistribute it and/or modify it under the
14 * terms of the GNU General Public License as published by the Free
15 * Software Foundation; either version 3 of the License, or (at your option)
18 * wimlib is distributed in the hope that it will be useful, but WITHOUT ANY
19 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
20 * A PARTICULAR PURPOSE. See the GNU General Public License for more
23 * You should have received a copy of the GNU General Public License
24 * along with wimlib; if not, see http://www.gnu.org/licenses/.
31 #include "wimlib/compressor_ops.h"
32 #include "wimlib/compress_common.h"
33 #include "wimlib/error.h"
34 #include "wimlib/lz_mf.h"
35 #include "wimlib/util.h"
36 #include "wimlib/xpress.h"
40 #define XPRESS_CACHE_PER_POS 8
41 #define XPRESS_OPTIM_ARRAY_LENGTH 4096
43 struct xpress_compressor;
45 struct xpress_mc_pos_data;
47 struct xpress_compressor_params {
49 /* Only used when choose_items_func == xpress_choose_items_near_optimal */
52 /* Given the data to compress (c->cur_window, c->cur_window_size),
53 * 'choose_items_func' fills in c->chosen_items with the intermediate
54 * representation of the match/literal sequence to output. Also fills
55 * in c->codewords and c->lens to provide the Huffman code with which
56 * these items should be output.
58 * Returns the number of items written to c->chosen_items. This can be
59 * at most c->cur_window_size. (The worst case is all literals, no
61 u32 (*choose_items_func)(struct xpress_compressor *c);
63 /* Match-finding algorithm and parameters */
64 enum lz_mf_algo mf_algo;
66 u32 nice_match_length;
69 /* XPRESS compressor state. */
70 struct xpress_compressor {
72 /* Parameters determined based on the compression level. */
73 struct xpress_compressor_params params;
75 /* Lempel-Ziv match-finder */
78 /* Optimal parsing data */
79 unsigned (*get_matches_func)(struct xpress_compressor *,
80 const struct lz_match **);
81 void (*skip_bytes_func)(struct xpress_compressor *, u32 n);
82 const u8 *cur_window_ptr;
83 struct lz_match *cached_matches;
84 struct lz_match *cache_ptr;
85 struct lz_match *cache_limit;
86 struct xpress_mc_pos_data *optimum;
87 unsigned optimum_cur_idx;
88 unsigned optimum_end_idx;
89 u8 costs[XPRESS_NUM_SYMBOLS];
91 /* The selected sequence of matches/literals */
92 struct xpress_item *chosen_items;
94 /* Data currently being compressed */
98 /* Symbol frequency counters */
99 u32 freqs[XPRESS_NUM_SYMBOLS];
101 /* The current Huffman code */
102 u32 codewords[XPRESS_NUM_SYMBOLS];
103 u8 lens[XPRESS_NUM_SYMBOLS];
106 /* Match-chooser position data.
107 * See corresponding declaration in lzx-compress.c for more information. */
108 struct xpress_mc_pos_data {
110 #define MC_INFINITE_COST ((u32)~0UL)
124 /* Intermediate XPRESS match/literal representation. */
126 u16 adjusted_len; /* Match length minus XPRESS_MIN_MATCH_LEN */
127 u16 offset; /* Match offset */
128 /* For literals, offset == 0 and adjusted_len is the literal byte. */
131 /* Output an XPRESS match. */
133 xpress_write_match(struct xpress_item match, struct output_bitstream *ostream,
134 const u32 codewords[], const u8 lens[])
136 unsigned len_hdr = min(match.adjusted_len, 0xf);
137 unsigned offset_bsr = bsr32(match.offset);
138 unsigned sym = XPRESS_NUM_CHARS + ((offset_bsr << 4) | len_hdr);
141 bitstream_put_bits(ostream, codewords[sym], lens[sym]);
143 /* If length >= 18, one extra length byte.
144 * If length >= 273, three (total) extra length bytes. */
145 if (match.adjusted_len >= 0xf) {
146 u8 byte1 = min(match.adjusted_len - 0xf, 0xff);
147 bitstream_put_byte(ostream, byte1);
149 bitstream_put_byte(ostream, match.adjusted_len & 0xff);
150 bitstream_put_byte(ostream, match.adjusted_len >> 8);
155 bitstream_put_bits(ostream, match.offset ^ (1U << offset_bsr), offset_bsr);
158 /* Output a sequence of XPRESS matches and literals. */
160 xpress_write_items(struct output_bitstream *ostream,
161 const struct xpress_item items[], u32 num_items,
162 const u32 codewords[], const u8 lens[])
164 for (u32 i = 0; i < num_items; i++) {
165 if (items[i].offset) {
167 xpress_write_match(items[i], ostream, codewords, lens);
170 unsigned lit = items[i].adjusted_len;
171 bitstream_put_bits(ostream, codewords[lit], lens[lit]);
174 /* End-of-data symbol (required for MS compatibility) */
175 bitstream_put_bits(ostream, codewords[XPRESS_END_OF_DATA], lens[XPRESS_END_OF_DATA]);
178 /* Make the Huffman code for XPRESS.
180 * Takes as input c->freqs and produces as output c->lens and c->codewords. */
182 xpress_make_huffman_code(struct xpress_compressor *c)
184 make_canonical_huffman_code(XPRESS_NUM_SYMBOLS, XPRESS_MAX_CODEWORD_LEN,
185 c->freqs, c->lens, c->codewords);
188 /* Account for the Huffman symbol that would be produced by outputting the
189 * specified literal. Returns the intermediate representation of the literal.
191 static inline struct xpress_item
192 xpress_tally_literal(u8 lit, u32 freqs[])
195 return (struct xpress_item) { .offset = 0, .adjusted_len = lit };
198 /* Account for the Huffman symbol that would be produced by outputting the
199 * specified match. Returns the intermediate representation of the match. */
200 static inline struct xpress_item
201 xpress_tally_match(u32 len, u32 offset, u32 freqs[])
203 u32 adjusted_len = len - XPRESS_MIN_MATCH_LEN;
204 unsigned len_hdr = min(adjusted_len, 0xf);
205 unsigned sym = XPRESS_NUM_CHARS + ((bsr32(offset) << 4) | len_hdr);
208 return (struct xpress_item) { .offset = offset,
209 .adjusted_len = adjusted_len };
213 xpress_get_matches_fillcache(struct xpress_compressor *c,
214 const struct lz_match **matches_ret)
216 struct lz_match *cache_ptr;
217 struct lz_match *matches;
218 unsigned num_matches;
220 cache_ptr = c->cache_ptr;
221 matches = cache_ptr + 1;
222 if (likely(cache_ptr <= c->cache_limit)) {
223 num_matches = lz_mf_get_matches(c->mf, matches);
224 cache_ptr->len = num_matches;
225 c->cache_ptr = matches + num_matches;
230 *matches_ret = matches;
235 xpress_get_matches_usecache(struct xpress_compressor *c,
236 const struct lz_match **matches_ret)
238 struct lz_match *cache_ptr;
239 struct lz_match *matches;
240 unsigned num_matches;
242 cache_ptr = c->cache_ptr;
243 matches = cache_ptr + 1;
244 if (likely(cache_ptr <= c->cache_limit)) {
245 num_matches = cache_ptr->len;
246 c->cache_ptr = matches + num_matches;
251 *matches_ret = matches;
256 xpress_get_matches_usecache_nocheck(struct xpress_compressor *c,
257 const struct lz_match **matches_ret)
259 struct lz_match *cache_ptr;
260 struct lz_match *matches;
261 unsigned num_matches;
263 cache_ptr = c->cache_ptr;
264 matches = cache_ptr + 1;
265 num_matches = cache_ptr->len;
266 c->cache_ptr = matches + num_matches;
268 *matches_ret = matches;
273 xpress_get_matches_noncaching(struct xpress_compressor *c,
274 const struct lz_match **matches_ret)
277 *matches_ret = c->cached_matches;
278 return lz_mf_get_matches(c->mf, c->cached_matches);
282 * Find matches at the next position in the window.
284 * Returns the number of matches found and sets *matches_ret to point to the
285 * matches array. The matches will be sorted by strictly increasing length and
288 static inline unsigned
289 xpress_get_matches(struct xpress_compressor *c,
290 const struct lz_match **matches_ret)
292 return (*c->get_matches_func)(c, matches_ret);
296 xpress_skip_bytes_fillcache(struct xpress_compressor *c, u32 n)
298 struct lz_match *cache_ptr;
300 c->cur_window_ptr += n;
301 cache_ptr = c->cache_ptr;
302 lz_mf_skip_positions(c->mf, n);
303 if (likely(cache_ptr <= c->cache_limit)) {
307 } while (--n && likely(cache_ptr <= c->cache_limit));
309 c->cache_ptr = cache_ptr;
313 xpress_skip_bytes_usecache(struct xpress_compressor *c, u32 n)
315 struct lz_match *cache_ptr;
317 c->cur_window_ptr += n;
318 cache_ptr = c->cache_ptr;
319 if (likely(cache_ptr <= c->cache_limit)) {
321 cache_ptr += 1 + cache_ptr->len;
322 } while (--n && likely(cache_ptr <= c->cache_limit));
324 c->cache_ptr = cache_ptr;
328 xpress_skip_bytes_usecache_nocheck(struct xpress_compressor *c, u32 n)
330 struct lz_match *cache_ptr;
332 c->cur_window_ptr += n;
333 cache_ptr = c->cache_ptr;
335 cache_ptr += 1 + cache_ptr->len;
337 c->cache_ptr = cache_ptr;
341 xpress_skip_bytes_noncaching(struct xpress_compressor *c, u32 n)
343 c->cur_window_ptr += n;
344 lz_mf_skip_positions(c->mf, n);
348 * Skip the specified number of positions in the window (don't search for
352 xpress_skip_bytes(struct xpress_compressor *c, u32 n)
354 return (*c->skip_bytes_func)(c, n);
358 * Returns the cost, in bits, required to output the literal from the previous
359 * window position (the position at which matches were last searched).
362 xpress_prev_literal_cost(const struct xpress_compressor *c)
364 return c->costs[*(c->cur_window_ptr - 1)];
368 * Reverse the linked list of near-optimal matches so that they can be returned
371 * Returns the first match in the list.
373 static struct lz_match
374 xpress_match_chooser_reverse_list(struct xpress_compressor *c, unsigned cur_pos)
376 unsigned prev_link, saved_prev_link;
377 u32 prev_match_offset, saved_prev_match_offset;
379 c->optimum_end_idx = cur_pos;
381 saved_prev_link = c->optimum[cur_pos].prev.link;
382 saved_prev_match_offset = c->optimum[cur_pos].prev.match_offset;
385 prev_link = saved_prev_link;
386 prev_match_offset = saved_prev_match_offset;
388 saved_prev_link = c->optimum[prev_link].prev.link;
389 saved_prev_match_offset = c->optimum[prev_link].prev.match_offset;
391 c->optimum[prev_link].next.link = cur_pos;
392 c->optimum[prev_link].next.match_offset = prev_match_offset;
395 } while (cur_pos != 0);
397 c->optimum_cur_idx = c->optimum[0].next.link;
399 return (struct lz_match)
400 { .len = c->optimum_cur_idx,
401 .offset = c->optimum[0].next.match_offset,
406 * Near-optimal parsing.
408 * This does a forward lowest-cost path search. The search is terminated when a
409 * sufficiently long match is found, when the search reaches a position with no
410 * alternatives, or when the temporary 'optimum' array fills up. After
411 * termination of the search, matches/literals will be returned one by one by
412 * successive calls to this function. Once all the matches/literals are used
413 * up, the next call to this function will begin a new search.
415 static struct lz_match
416 xpress_choose_near_optimal_item(struct xpress_compressor *c)
418 const struct lz_match *matches;
419 unsigned num_matches;
420 struct lz_match match;
423 struct xpress_mc_pos_data * const optimum = c->optimum;
425 if (c->optimum_cur_idx != c->optimum_end_idx) {
426 /* Return previously computed match or literal. */
427 match.len = optimum[c->optimum_cur_idx].next.link -
429 match.offset = optimum[c->optimum_cur_idx].next.match_offset;
431 c->optimum_cur_idx = optimum[c->optimum_cur_idx].next.link;
435 c->optimum_cur_idx = 0;
436 c->optimum_end_idx = 0;
438 num_matches = xpress_get_matches(c, &matches);
440 if (num_matches == 0)
441 return (struct lz_match) {};
443 if (matches[num_matches - 1].len >= c->params.nice_match_length) {
444 /* Take the long match immediately. */
445 xpress_skip_bytes(c, matches[num_matches - 1].len - 1);
446 return matches[num_matches - 1];
449 /* Consider coding a literal. */
450 optimum[1].cost = xpress_prev_literal_cost(c);
451 optimum[1].prev.link = 0;
453 optimum[2].cost = MC_INFINITE_COST;
456 /* Consider coding a match. Cost evaluation is hand-inlined so
457 * that we can do some performance hacks. */
461 struct xpress_mc_pos_data *optimum_ptr = &optimum[len];
463 if (matches[num_matches - 1].len < 0xf + XPRESS_MIN_MATCH_LEN) {
465 u32 offset = matches[i].offset;
466 u32 offset_bsr = bsr32(offset);
467 unsigned len_hdr = len - XPRESS_MIN_MATCH_LEN;
468 unsigned sym = XPRESS_NUM_CHARS +
469 ((offset_bsr << 4) | len_hdr);
471 optimum_ptr->prev.link = 0;
472 optimum_ptr->prev.match_offset = offset;
473 optimum_ptr->cost = offset_bsr + c->costs[sym];
476 } while (++len <= matches[i].len);
477 } while (++i != num_matches);
480 u32 offset = matches[i].offset;
481 u32 offset_bsr = bsr32(offset);
483 u32 adjusted_len = len - XPRESS_MIN_MATCH_LEN;
484 unsigned len_hdr = min(adjusted_len, 0xf);
485 unsigned sym = XPRESS_NUM_CHARS +
486 ((offset_bsr << 4) | len_hdr);
487 u32 cost = offset_bsr + c->costs[sym];
488 if (adjusted_len >= 0xf) {
490 if (adjusted_len - 0xf >= 0xff)
494 optimum_ptr->prev.link = 0;
495 optimum_ptr->prev.match_offset = offset;
496 optimum_ptr->cost = cost;
498 } while (++len <= matches[i].len);
499 } while (++i != num_matches);
503 end_pos = matches[num_matches - 1].len;
509 num_matches = xpress_get_matches(c, &matches);
512 longest_len = matches[num_matches - 1].len;
513 if (longest_len >= c->params.nice_match_length) {
514 /* Take the long match immediately. */
515 match = xpress_match_chooser_reverse_list(c, cur_pos);
517 optimum[cur_pos].next.match_offset =
518 matches[num_matches - 1].offset;
519 optimum[cur_pos].next.link = cur_pos + longest_len;
520 c->optimum_end_idx = cur_pos + longest_len;
522 xpress_skip_bytes(c, longest_len - 1);
530 while (end_pos < cur_pos + longest_len)
531 optimum[++end_pos].cost = MC_INFINITE_COST;
533 /* Consider coding a literal. */
534 cost = optimum[cur_pos].cost + xpress_prev_literal_cost(c);
535 if (cost < optimum[cur_pos + 1].cost) {
536 optimum[cur_pos + 1].cost = cost;
537 optimum[cur_pos + 1].prev.link = cur_pos;
541 /* Consider coding a match. Cost evaluation is
542 * hand-inlined so that we can do some performance
546 struct xpress_mc_pos_data *optimum_ptr = &optimum[cur_pos + 3];
547 u32 cur_cost = optimum[cur_pos].cost;
549 if (matches[num_matches - 1].len < 0xf + XPRESS_MIN_MATCH_LEN) {
551 u32 offset = matches[i].offset;
552 u32 offset_bsr = bsr32(offset);
553 unsigned len_hdr = len - XPRESS_MIN_MATCH_LEN;
554 unsigned sym = XPRESS_NUM_CHARS +
555 ((offset_bsr << 4) | len_hdr);
557 u32 base_cost = cur_cost + offset_bsr;
559 cost = base_cost + c->costs[sym];
560 if (cost < optimum_ptr->cost) {
561 optimum_ptr->prev.link = cur_pos;
562 optimum_ptr->prev.match_offset = offset;
563 optimum_ptr->cost = cost;
567 } while (++len <= matches[i].len);
568 } while (++i != num_matches);
571 u32 offset = matches[i].offset;
572 u32 offset_bsr = bsr32(offset);
574 u32 base_cost = cur_cost + offset_bsr;
576 u32 adjusted_len = len - XPRESS_MIN_MATCH_LEN;
577 unsigned len_hdr = min(adjusted_len, 0xf);
578 unsigned sym = XPRESS_NUM_CHARS +
579 ((offset_bsr << 4) | len_hdr);
581 cost = base_cost + c->costs[sym];
582 if (adjusted_len >= 0xf) {
584 if (adjusted_len - 0xf >= 0xff)
588 if (cost < optimum_ptr->cost) {
589 optimum_ptr->prev.link = cur_pos;
590 optimum_ptr->prev.match_offset = offset;
591 optimum_ptr->cost = cost;
594 } while (++len <= matches[i].len);
595 } while (++i != num_matches);
601 } while (cur_pos != end_pos && cur_pos != XPRESS_OPTIM_ARRAY_LENGTH);
603 return xpress_match_chooser_reverse_list(c, cur_pos);
606 /* Set default XPRESS Huffman symbol costs to kick-start the iterative
607 * optimization algorithm. */
609 xpress_set_default_costs(u8 costs[])
613 for (i = 0; i < XPRESS_NUM_CHARS; i++)
616 for (; i < XPRESS_NUM_SYMBOLS; i++)
620 /* Copy the Huffman codeword lengths array @lens to the Huffman symbol costs
621 * array @costs, but also assign a default cost to each 0-length (unused)
624 xpress_set_costs(u8 costs[], const u8 lens[])
626 for (unsigned i = 0; i < XPRESS_NUM_SYMBOLS; i++)
627 costs[i] = lens[i] ? lens[i] : XPRESS_MAX_CODEWORD_LEN;
630 /* Near-optimal parsing */
632 xpress_choose_items_near_optimal(struct xpress_compressor *c)
634 u32 num_passes_remaining = c->params.num_optim_passes;
635 const u8 *window_ptr;
636 const u8 *window_end;
637 struct xpress_item *next_chosen_item;
638 struct lz_match raw_item;
639 struct xpress_item xpress_item;
641 xpress_set_default_costs(c->costs);
642 c->optimum_cur_idx = 0;
643 c->optimum_end_idx = 0;
645 if (c->params.num_optim_passes > 1) {
646 c->get_matches_func = xpress_get_matches_fillcache;
647 c->skip_bytes_func = xpress_skip_bytes_fillcache;
649 c->get_matches_func = xpress_get_matches_noncaching;
650 c->skip_bytes_func = xpress_skip_bytes_noncaching;
653 lz_mf_load_window(c->mf, c->cur_window, c->cur_window_size);
655 while (--num_passes_remaining) {
656 c->cur_window_ptr = c->cur_window;
657 window_ptr = c->cur_window;
658 window_end = window_ptr + c->cur_window_size;
659 c->cache_ptr = c->cached_matches;
660 memset(c->freqs, 0, sizeof(c->freqs));
662 while (window_ptr != window_end) {
663 raw_item = xpress_choose_near_optimal_item(c);
664 if (raw_item.len >= XPRESS_MIN_MATCH_LEN) {
665 xpress_tally_match(raw_item.len,
666 raw_item.offset, c->freqs);
667 window_ptr += raw_item.len;
669 xpress_tally_literal(*window_ptr, c->freqs);
673 c->freqs[XPRESS_END_OF_DATA]++;
674 xpress_make_huffman_code(c);
675 xpress_set_costs(c->costs, c->lens);
676 if (c->cache_ptr <= c->cache_limit) {
677 c->get_matches_func = xpress_get_matches_usecache_nocheck;
678 c->skip_bytes_func = xpress_skip_bytes_usecache_nocheck;
680 c->get_matches_func = xpress_get_matches_usecache;
681 c->skip_bytes_func = xpress_skip_bytes_usecache;
685 c->cur_window_ptr = c->cur_window;
686 window_ptr = c->cur_window;
687 window_end = window_ptr + c->cur_window_size;
688 c->cache_ptr = c->cached_matches;
689 memset(c->freqs, 0, sizeof(c->freqs));
690 next_chosen_item = c->chosen_items;
693 while (window_ptr != window_end) {
694 raw_item = xpress_choose_near_optimal_item(c);
695 if (raw_item.len >= XPRESS_MIN_MATCH_LEN) {
696 xpress_item = xpress_tally_match(raw_item.len,
699 window_ptr += raw_item.len;
701 xpress_item = xpress_tally_literal(*window_ptr,
705 *next_chosen_item++ = xpress_item;
707 /* When doing one-pass near-optimal parsing, rebuild the Huffman
708 * code occasionally. */
709 if (unlikely((next_chosen_item - c->chosen_items) % 2048 == 0) &&
710 c->cur_window_size >= 16384 &&
711 c->params.num_optim_passes == 1)
713 xpress_make_huffman_code(c);
714 for (unsigned i = 0; i < XPRESS_NUM_SYMBOLS; i++)
715 c->costs[i] = c->lens[i] ? c->lens[i] : unseen_cost;
716 if (unseen_cost < 15)
720 c->freqs[XPRESS_END_OF_DATA]++;
721 xpress_make_huffman_code(c);
722 return next_chosen_item - c->chosen_items;
727 xpress_choose_items_lazy(struct xpress_compressor *c)
731 const u8 *window_ptr;
732 const u8 *window_end;
734 struct lz_match matches[min(c->params.nice_match_length, c->params.max_search_depth)];
735 struct xpress_item *next_chosen_item;
736 struct lz_match prev_match;
740 lz_mf_load_window(mf, c->cur_window, c->cur_window_size);
742 if (c->cur_window_size <= 8192)
743 len_3_too_far = 2048;
745 len_3_too_far = 4096;
747 memset(c->freqs, 0, sizeof(c->freqs));
749 window_ptr = c->cur_window;
750 window_end = c->cur_window + c->cur_window_size;
751 next_chosen_item = c->chosen_items;
755 /* Don't have match at previous position */
757 num_matches = lz_mf_get_matches(mf, matches);
760 if (num_matches == 0 ||
761 (matches[num_matches - 1].len == 3 &&
762 matches[num_matches - 1].offset >= len_3_too_far))
764 /* No matches found => output literal */
765 *next_chosen_item++ = xpress_tally_literal(*(window_ptr - 1),
767 if (window_ptr == window_end)
772 prev_match = matches[num_matches - 1];
775 /* Have match at previous position */
777 if (prev_match.len >= c->params.nice_match_length) {
778 /* Very long match found => output immediately */
779 *next_chosen_item++ = xpress_tally_match(prev_match.len,
782 lz_mf_skip_positions(mf, prev_match.len - 1);
783 window_ptr += prev_match.len - 1;
784 if (window_ptr == window_end)
789 num_matches = lz_mf_get_matches(mf, matches);
792 if (num_matches == 0 ||
793 (matches[num_matches - 1].len <= prev_match.len))
795 /* Next match is not longer => output previous match */
796 *next_chosen_item++ = xpress_tally_match(prev_match.len,
799 lz_mf_skip_positions(mf, prev_match.len - 2);
800 window_ptr += prev_match.len - 2;
801 if (window_ptr == window_end)
806 /* Next match is longer => output literal */
808 *next_chosen_item++ = xpress_tally_literal(*(window_ptr - 2),
811 prev_match = matches[num_matches - 1];
813 goto have_prev_match;
816 c->freqs[XPRESS_END_OF_DATA]++;
817 xpress_make_huffman_code(c);
818 return next_chosen_item - c->chosen_items;
823 xpress_choose_items_greedy(struct xpress_compressor *c)
827 const u8 *window_ptr;
828 const u8 *window_end;
829 struct lz_match matches[min(c->params.nice_match_length, c->params.max_search_depth)];
831 struct xpress_item *next_chosen_item;
835 lz_mf_load_window(mf, c->cur_window, c->cur_window_size);
837 if (c->cur_window_size <= 8192)
838 len_3_too_far = 2048;
840 len_3_too_far = 4096;
842 memset(c->freqs, 0, sizeof(c->freqs));
844 window_ptr = c->cur_window;
845 window_end = c->cur_window + c->cur_window_size;
846 next_chosen_item = c->chosen_items;
849 /* Get longest match at the current position. */
850 num_matches = lz_mf_get_matches(mf, matches);
852 if (num_matches == 0 ||
853 (matches[num_matches - 1].len == 3 &&
854 matches[num_matches - 1].offset >= len_3_too_far))
856 *next_chosen_item++ = xpress_tally_literal(*window_ptr, c->freqs);
859 u32 len = matches[num_matches - 1].len;
860 u32 offset = matches[num_matches - 1].offset;
862 *next_chosen_item++ = xpress_tally_match(len, offset, c->freqs);
863 lz_mf_skip_positions(mf, len - 1);
866 } while (window_ptr != window_end);
868 c->freqs[XPRESS_END_OF_DATA]++;
869 xpress_make_huffman_code(c);
870 return next_chosen_item - c->chosen_items;
873 /* Huffman-only parsing */
875 xpress_choose_items_huffonly(struct xpress_compressor *c)
877 const u8 *window_ptr;
878 const u8 *window_end;
879 struct xpress_item *next_chosen_item;
881 memset(c->freqs, 0, sizeof(c->freqs));
883 window_ptr = c->cur_window;
884 window_end = c->cur_window + c->cur_window_size;
885 next_chosen_item = c->chosen_items;
888 *next_chosen_item++ = xpress_tally_literal(*window_ptr++, c->freqs);
889 } while (window_ptr != window_end);
891 c->freqs[XPRESS_END_OF_DATA]++;
892 xpress_make_huffman_code(c);
893 return next_chosen_item - c->chosen_items;
896 /* Given the specified compression level and maximum window size, build the
897 * parameters to use for XPRESS compression. */
899 xpress_build_params(unsigned int compression_level, u32 max_window_size,
900 struct xpress_compressor_params *xpress_params)
902 memset(xpress_params, 0, sizeof(*xpress_params));
904 if (compression_level == 1) {
906 /* Huffman only (no Lempel-Ziv matches) */
907 xpress_params->mf_algo = LZ_MF_NULL;
908 xpress_params->choose_items_func = xpress_choose_items_huffonly;
910 } else if (compression_level < 30) {
913 xpress_params->mf_algo = LZ_MF_HASH_CHAINS;
914 xpress_params->choose_items_func = xpress_choose_items_greedy;
915 xpress_params->nice_match_length = compression_level;
916 xpress_params->max_search_depth = compression_level / 2;
918 } else if (compression_level < 60) {
921 xpress_params->mf_algo = LZ_MF_HASH_CHAINS;
922 xpress_params->choose_items_func = xpress_choose_items_lazy;
923 xpress_params->nice_match_length = compression_level;
924 xpress_params->max_search_depth = compression_level / 2;
928 /* Near-optimal parsing */
929 xpress_params->choose_items_func = xpress_choose_items_near_optimal;
930 if (max_window_size >= 32768)
931 xpress_params->mf_algo = LZ_MF_BINARY_TREES;
933 xpress_params->mf_algo = LZ_MF_HASH_CHAINS;
934 xpress_params->num_optim_passes = compression_level / 40;
935 xpress_params->nice_match_length = min(compression_level / 2,
936 XPRESS_MAX_MATCH_LEN);
937 xpress_params->max_search_depth = min(compression_level,
938 XPRESS_MAX_MATCH_LEN);
942 /* Given the specified XPRESS parameters and maximum window size, build the
943 * parameters to use for match-finding. */
945 xpress_build_mf_params(const struct xpress_compressor_params *xpress_params,
946 u32 max_window_size, struct lz_mf_params *mf_params)
948 memset(mf_params, 0, sizeof(*mf_params));
950 mf_params->algorithm = xpress_params->mf_algo;
951 mf_params->max_window_size = max_window_size;
952 mf_params->min_match_len = XPRESS_MIN_MATCH_LEN;
953 mf_params->max_match_len = XPRESS_MAX_MATCH_LEN;
954 mf_params->max_search_depth = xpress_params->max_search_depth;
955 mf_params->nice_match_len = xpress_params->nice_match_length;
959 xpress_window_size_valid(size_t window_size)
961 return (window_size > 0 && window_size <= XPRESS_MAX_OFFSET + 1);
965 xpress_free_compressor(void *_c);
968 xpress_get_needed_memory(size_t max_window_size, unsigned int compression_level)
971 struct xpress_compressor_params params;
973 if (!xpress_window_size_valid(max_window_size))
976 xpress_build_params(compression_level, max_window_size, ¶ms);
978 size += sizeof(struct xpress_compressor);
980 size += lz_mf_get_needed_memory(params.mf_algo, max_window_size);
982 if (params.choose_items_func == xpress_choose_items_near_optimal) {
983 size += (XPRESS_OPTIM_ARRAY_LENGTH + params.nice_match_length) *
984 sizeof(struct xpress_mc_pos_data);
985 if (params.num_optim_passes > 1) {
986 size_t cache_len = max(max_window_size * XPRESS_CACHE_PER_POS,
987 params.max_search_depth + 1);
988 size += cache_len * sizeof(struct lz_match);
990 size += params.max_search_depth * sizeof(struct lz_match);
994 size += max_window_size * sizeof(struct xpress_item);
1000 xpress_create_compressor(size_t max_window_size, unsigned int compression_level,
1003 struct xpress_compressor *c;
1004 struct xpress_compressor_params params;
1005 struct lz_mf_params mf_params;
1007 if (!xpress_window_size_valid(max_window_size))
1008 return WIMLIB_ERR_INVALID_PARAM;
1010 xpress_build_params(compression_level, max_window_size, ¶ms);
1011 xpress_build_mf_params(¶ms, max_window_size, &mf_params);
1013 c = CALLOC(1, sizeof(struct xpress_compressor));
1019 c->mf = lz_mf_alloc(&mf_params);
1023 if (params.choose_items_func == xpress_choose_items_near_optimal) {
1024 c->optimum = MALLOC((XPRESS_OPTIM_ARRAY_LENGTH +
1025 params.nice_match_length) *
1026 sizeof(struct xpress_mc_pos_data));
1029 if (params.num_optim_passes > 1) {
1030 size_t cache_len = max(max_window_size * XPRESS_CACHE_PER_POS,
1031 params.max_search_depth + 1);
1032 c->cached_matches = MALLOC(cache_len * sizeof(struct lz_match));
1033 if (!c->cached_matches)
1035 c->cache_limit = c->cached_matches + cache_len -
1036 (params.max_search_depth + 1);
1038 c->cached_matches = MALLOC(params.max_search_depth *
1039 sizeof(struct lz_match));
1040 if (!c->cached_matches)
1045 c->chosen_items = MALLOC(max_window_size * sizeof(struct xpress_item));
1046 if (!c->chosen_items)
1053 xpress_free_compressor(c);
1054 return WIMLIB_ERR_NOMEM;
1058 xpress_compress(const void *uncompressed_data, size_t uncompressed_size,
1059 void *compressed_data, size_t compressed_size_avail, void *_c)
1061 struct xpress_compressor *c = _c;
1062 u32 num_chosen_items;
1064 struct output_bitstream ostream;
1065 u32 compressed_size;
1067 /* XPRESS requires 256 bytes of overhead for the Huffman code, so it's
1068 * impossible to compress 256 bytes or less of data to less than the
1071 * +1 to take into account that the buffer for compressed data is 1 byte
1072 * smaller than the buffer for uncompressed data.
1074 * +4 to take into account that init_output_bitstream() requires at
1075 * least 4 bytes of data. */
1076 if (compressed_size_avail < XPRESS_NUM_SYMBOLS / 2 + 1 + 4)
1079 /* Determine match/literal sequence to divide the data into. */
1080 c->cur_window = uncompressed_data;
1081 c->cur_window_size = uncompressed_size;
1082 num_chosen_items = (*c->params.choose_items_func)(c);
1084 /* Output the Huffman code as a series of 512 4-bit lengths. */
1085 cptr = compressed_data;
1086 for (unsigned i = 0; i < XPRESS_NUM_SYMBOLS; i += 2)
1087 *cptr++ = (c->lens[i] & 0xf) | (c->lens[i + 1] << 4);
1089 /* Output the encoded matches/literals. */
1090 init_output_bitstream(&ostream, cptr,
1091 compressed_size_avail - XPRESS_NUM_SYMBOLS / 2 - 1);
1092 xpress_write_items(&ostream, c->chosen_items, num_chosen_items,
1093 c->codewords, c->lens);
1095 /* Flush any pending data and get the length of the compressed data. */
1096 compressed_size = flush_output_bitstream(&ostream);
1097 if (compressed_size == (u32)~0UL)
1100 /* Return the length of the compressed data. */
1101 return compressed_size + XPRESS_NUM_SYMBOLS / 2;
1105 xpress_free_compressor(void *_c)
1107 struct xpress_compressor *c = _c;
1111 FREE(c->cached_matches);
1113 FREE(c->chosen_items);
1118 const struct compressor_ops xpress_compressor_ops = {
1119 .get_needed_memory = xpress_get_needed_memory,
1120 .create_compressor = xpress_create_compressor,
1121 .compress = xpress_compress,
1122 .free_compressor = xpress_free_compressor,