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 {
48 struct lz_match (*choose_item_func)(struct xpress_compressor *);
50 enum lz_mf_algo mf_algo;
51 u32 nice_match_length;
55 /* XPRESS compressor state. */
56 struct xpress_compressor {
58 /* Parameters determined based on the compression level. */
59 struct xpress_compressor_params params;
61 unsigned (*get_matches_func)(struct xpress_compressor *,
62 const struct lz_match **);
63 void (*skip_bytes_func)(struct xpress_compressor *, u32 n);
66 /* Data currently being compressed */
70 /* Lempel-Ziv match-finder */
73 const u8 *cur_window_ptr;
75 /* Match cache, used when doing multiple optimization passes. */
76 struct lz_match *cached_matches;
77 struct lz_match *cache_ptr;
78 struct lz_match *cache_limit;
80 /* Optimal parsing data */
81 struct xpress_mc_pos_data *optimum;
82 unsigned optimum_cur_idx;
83 unsigned optimum_end_idx;
84 u8 costs[XPRESS_NUM_SYMBOLS];
86 /* Lazy parsing data */
87 struct lz_match prev_match;
89 /* The selected sequence of matches/literals */
90 struct xpress_item *chosen_items;
92 /* Symbol frequency counters */
93 u32 freqs[XPRESS_NUM_SYMBOLS];
95 /* The current Huffman code */
96 u32 codewords[XPRESS_NUM_SYMBOLS];
97 u8 lens[XPRESS_NUM_SYMBOLS];
100 /* Match-chooser position data.
101 * See corresponding declaration in lzx-compress.c for more information. */
102 struct xpress_mc_pos_data {
104 #define MC_INFINITE_COST ((u32)~0UL)
118 /* Intermediate XPRESS match/literal representation. */
120 u16 adjusted_len; /* Match length minus XPRESS_MIN_MATCH_LEN */
121 u16 offset; /* Match offset */
122 /* For literals, offset == 0 and adjusted_len is the literal byte. */
125 /* Output an XPRESS match. */
127 xpress_write_match(struct xpress_item match, struct output_bitstream *ostream,
128 const u32 codewords[], const u8 lens[])
130 unsigned len_hdr = min(match.adjusted_len, 0xf);
131 unsigned offset_bsr = bsr32(match.offset);
132 unsigned sym = XPRESS_NUM_CHARS + ((offset_bsr << 4) | len_hdr);
135 bitstream_put_bits(ostream, codewords[sym], lens[sym]);
137 /* If length >= 18, one extra length byte.
138 * If length >= 273, three (total) extra length bytes. */
139 if (match.adjusted_len >= 0xf) {
140 u8 byte1 = min(match.adjusted_len - 0xf, 0xff);
141 bitstream_put_byte(ostream, byte1);
143 bitstream_put_byte(ostream, match.adjusted_len & 0xff);
144 bitstream_put_byte(ostream, match.adjusted_len >> 8);
149 bitstream_put_bits(ostream, match.offset ^ (1U << offset_bsr), offset_bsr);
152 /* Output a sequence of XPRESS matches and literals. */
154 xpress_write_items(struct output_bitstream *ostream,
155 const struct xpress_item items[], u32 num_items,
156 const u32 codewords[], const u8 lens[])
158 for (u32 i = 0; i < num_items; i++) {
159 if (items[i].offset) {
161 xpress_write_match(items[i], ostream, codewords, lens);
164 unsigned lit = items[i].adjusted_len;
165 bitstream_put_bits(ostream, codewords[lit], lens[lit]);
168 /* End-of-data symbol (required for MS compatibility) */
169 bitstream_put_bits(ostream, codewords[XPRESS_END_OF_DATA], lens[XPRESS_END_OF_DATA]);
172 /* Make the Huffman code for XPRESS.
174 * Takes as input c->freqs and produces as output c->lens and c->codewords. */
176 xpress_make_huffman_code(struct xpress_compressor *c)
178 make_canonical_huffman_code(XPRESS_NUM_SYMBOLS, XPRESS_MAX_CODEWORD_LEN,
179 c->freqs, c->lens, c->codewords);
182 /* Account for the Huffman symbol that would be produced by outputting the
183 * specified literal. Returns the intermediate representation of the literal.
185 static inline struct xpress_item
186 xpress_tally_literal(u8 lit, u32 freqs[])
189 return (struct xpress_item) { .offset = 0, .adjusted_len = lit };
192 /* Account for the Huffman symbol that would be produced by outputting the
193 * specified match. Returns the intermediate representation of the match. */
194 static inline struct xpress_item
195 xpress_tally_match(u32 len, u32 offset, u32 freqs[])
197 u32 adjusted_len = len - XPRESS_MIN_MATCH_LEN;
198 unsigned len_hdr = min(adjusted_len, 0xf);
199 unsigned sym = XPRESS_NUM_CHARS + ((bsr32(offset) << 4) | len_hdr);
202 return (struct xpress_item) { .offset = offset,
203 .adjusted_len = adjusted_len };
207 xpress_get_matches_fillcache(struct xpress_compressor *c,
208 const struct lz_match **matches_ret)
210 struct lz_match *cache_ptr;
211 struct lz_match *matches;
212 unsigned num_matches;
214 cache_ptr = c->cache_ptr;
215 matches = cache_ptr + 1;
216 if (likely(cache_ptr <= c->cache_limit)) {
217 num_matches = lz_mf_get_matches(c->mf, matches);
218 cache_ptr->len = num_matches;
219 c->cache_ptr = matches + num_matches;
224 *matches_ret = matches;
229 xpress_get_matches_usecache(struct xpress_compressor *c,
230 const struct lz_match **matches_ret)
232 struct lz_match *cache_ptr;
233 struct lz_match *matches;
234 unsigned num_matches;
236 cache_ptr = c->cache_ptr;
237 matches = cache_ptr + 1;
238 if (likely(cache_ptr <= c->cache_limit)) {
239 num_matches = cache_ptr->len;
240 c->cache_ptr = matches + num_matches;
245 *matches_ret = matches;
250 xpress_get_matches_usecache_nocheck(struct xpress_compressor *c,
251 const struct lz_match **matches_ret)
253 struct lz_match *cache_ptr;
254 struct lz_match *matches;
255 unsigned num_matches;
257 cache_ptr = c->cache_ptr;
258 matches = cache_ptr + 1;
259 num_matches = cache_ptr->len;
260 c->cache_ptr = matches + num_matches;
262 *matches_ret = matches;
267 xpress_get_matches_noncaching(struct xpress_compressor *c,
268 const struct lz_match **matches_ret)
271 *matches_ret = c->cached_matches;
272 return lz_mf_get_matches(c->mf, c->cached_matches);
276 * Find matches at the next position in the window.
278 * Returns the number of matches found and sets *matches_ret to point to the
279 * matches array. The matches will be sorted by strictly increasing length and
282 static inline unsigned
283 xpress_get_matches(struct xpress_compressor *c,
284 const struct lz_match **matches_ret)
286 return (*c->get_matches_func)(c, matches_ret);
290 xpress_skip_bytes_fillcache(struct xpress_compressor *c, u32 n)
292 struct lz_match *cache_ptr;
294 c->cur_window_ptr += n;
295 cache_ptr = c->cache_ptr;
296 lz_mf_skip_positions(c->mf, n);
297 if (likely(cache_ptr <= c->cache_limit)) {
301 } while (--n && likely(cache_ptr <= c->cache_limit));
303 c->cache_ptr = cache_ptr;
307 xpress_skip_bytes_usecache(struct xpress_compressor *c, u32 n)
309 struct lz_match *cache_ptr;
311 c->cur_window_ptr += n;
312 cache_ptr = c->cache_ptr;
313 if (likely(cache_ptr <= c->cache_limit)) {
315 cache_ptr += 1 + cache_ptr->len;
316 } while (--n && likely(cache_ptr <= c->cache_limit));
318 c->cache_ptr = cache_ptr;
322 xpress_skip_bytes_usecache_nocheck(struct xpress_compressor *c, u32 n)
324 struct lz_match *cache_ptr;
326 c->cur_window_ptr += n;
327 cache_ptr = c->cache_ptr;
329 cache_ptr += 1 + cache_ptr->len;
331 c->cache_ptr = cache_ptr;
335 xpress_skip_bytes_noncaching(struct xpress_compressor *c, u32 n)
337 c->cur_window_ptr += n;
338 lz_mf_skip_positions(c->mf, n);
342 * Skip the specified number of positions in the window (don't search for
346 xpress_skip_bytes(struct xpress_compressor *c, u32 n)
348 return (*c->skip_bytes_func)(c, n);
352 * Returns the cost, in bits, required to output the literal from the previous
353 * window position (the position at which matches were last searched).
356 xpress_prev_literal_cost(const struct xpress_compressor *c)
358 return c->costs[*(c->cur_window_ptr - 1)];
362 * Reverse the linked list of near-optimal matches so that they can be returned
365 * Returns the first match in the list.
367 static struct lz_match
368 xpress_match_chooser_reverse_list(struct xpress_compressor *c, unsigned cur_pos)
370 unsigned prev_link, saved_prev_link;
371 u32 prev_match_offset, saved_prev_match_offset;
373 c->optimum_end_idx = cur_pos;
375 saved_prev_link = c->optimum[cur_pos].prev.link;
376 saved_prev_match_offset = c->optimum[cur_pos].prev.match_offset;
379 prev_link = saved_prev_link;
380 prev_match_offset = saved_prev_match_offset;
382 saved_prev_link = c->optimum[prev_link].prev.link;
383 saved_prev_match_offset = c->optimum[prev_link].prev.match_offset;
385 c->optimum[prev_link].next.link = cur_pos;
386 c->optimum[prev_link].next.match_offset = prev_match_offset;
389 } while (cur_pos != 0);
391 c->optimum_cur_idx = c->optimum[0].next.link;
393 return (struct lz_match)
394 { .len = c->optimum_cur_idx,
395 .offset = c->optimum[0].next.match_offset,
400 * Near-optimal parsing.
402 * This does a forward lowest-cost path search. The search is terminated when a
403 * sufficiently long match is found, when the search reaches a position with no
404 * alternatives, or when the temporary 'optimum' array fills up. After
405 * termination of the search, matches/literals will be returned one by one by
406 * successive calls to this function. Once all the matches/literals are used
407 * up, the next call to this function will begin a new search.
409 static struct lz_match
410 xpress_choose_near_optimal_item(struct xpress_compressor *c)
412 const struct lz_match *matches;
413 unsigned num_matches;
414 struct lz_match match;
417 struct xpress_mc_pos_data * const optimum = c->optimum;
419 if (c->optimum_cur_idx != c->optimum_end_idx) {
420 /* Return previously computed match or literal. */
421 match.len = optimum[c->optimum_cur_idx].next.link -
423 match.offset = optimum[c->optimum_cur_idx].next.match_offset;
425 c->optimum_cur_idx = optimum[c->optimum_cur_idx].next.link;
429 c->optimum_cur_idx = 0;
430 c->optimum_end_idx = 0;
432 num_matches = xpress_get_matches(c, &matches);
434 if (num_matches == 0)
435 return (struct lz_match) {};
437 if (matches[num_matches - 1].len >= c->params.nice_match_length) {
438 /* Take the long match immediately. */
439 xpress_skip_bytes(c, matches[num_matches - 1].len - 1);
440 return matches[num_matches - 1];
443 /* Consider coding a literal. */
444 optimum[1].cost = xpress_prev_literal_cost(c);
445 optimum[1].prev.link = 0;
447 optimum[2].cost = MC_INFINITE_COST;
450 /* Consider coding a match. Cost evaluation is hand-inlined so
451 * that we can do some performance hacks. */
455 struct xpress_mc_pos_data *optimum_ptr = &optimum[len];
457 if (matches[num_matches - 1].len < 0xf + XPRESS_MIN_MATCH_LEN) {
459 u32 offset = matches[i].offset;
460 u32 offset_bsr = bsr32(offset);
461 unsigned len_hdr = len - XPRESS_MIN_MATCH_LEN;
462 unsigned sym = XPRESS_NUM_CHARS +
463 ((offset_bsr << 4) | len_hdr);
465 optimum_ptr->prev.link = 0;
466 optimum_ptr->prev.match_offset = offset;
467 optimum_ptr->cost = offset_bsr + c->costs[sym];
470 } while (++len <= matches[i].len);
471 } while (++i != num_matches);
474 u32 offset = matches[i].offset;
475 u32 offset_bsr = bsr32(offset);
477 u32 adjusted_len = len - XPRESS_MIN_MATCH_LEN;
478 unsigned len_hdr = min(adjusted_len, 0xf);
479 unsigned sym = XPRESS_NUM_CHARS +
480 ((offset_bsr << 4) | len_hdr);
481 u32 cost = offset_bsr + c->costs[sym];
482 if (adjusted_len >= 0xf) {
484 if (adjusted_len - 0xf >= 0xff)
488 optimum_ptr->prev.link = 0;
489 optimum_ptr->prev.match_offset = offset;
490 optimum_ptr->cost = cost;
492 } while (++len <= matches[i].len);
493 } while (++i != num_matches);
497 end_pos = matches[num_matches - 1].len;
503 num_matches = xpress_get_matches(c, &matches);
506 longest_len = matches[num_matches - 1].len;
507 if (longest_len >= c->params.nice_match_length) {
508 /* Take the long match immediately. */
509 match = xpress_match_chooser_reverse_list(c, cur_pos);
511 optimum[cur_pos].next.match_offset =
512 matches[num_matches - 1].offset;
513 optimum[cur_pos].next.link = cur_pos + longest_len;
514 c->optimum_end_idx = cur_pos + longest_len;
516 xpress_skip_bytes(c, longest_len - 1);
524 while (end_pos < cur_pos + longest_len)
525 optimum[++end_pos].cost = MC_INFINITE_COST;
527 /* Consider coding a literal. */
528 cost = optimum[cur_pos].cost + xpress_prev_literal_cost(c);
529 if (cost < optimum[cur_pos + 1].cost) {
530 optimum[cur_pos + 1].cost = cost;
531 optimum[cur_pos + 1].prev.link = cur_pos;
535 /* Consider coding a match. Cost evaluation is
536 * hand-inlined so that we can do some performance
540 struct xpress_mc_pos_data *optimum_ptr = &optimum[cur_pos + 3];
541 u32 cur_cost = optimum[cur_pos].cost;
543 if (matches[num_matches - 1].len < 0xf + XPRESS_MIN_MATCH_LEN) {
545 u32 offset = matches[i].offset;
546 u32 offset_bsr = bsr32(offset);
547 unsigned len_hdr = len - XPRESS_MIN_MATCH_LEN;
548 unsigned sym = XPRESS_NUM_CHARS +
549 ((offset_bsr << 4) | len_hdr);
551 u32 base_cost = cur_cost + offset_bsr;
553 cost = base_cost + c->costs[sym];
554 if (cost < optimum_ptr->cost) {
555 optimum_ptr->prev.link = cur_pos;
556 optimum_ptr->prev.match_offset = offset;
557 optimum_ptr->cost = cost;
561 } while (++len <= matches[i].len);
562 } while (++i != num_matches);
565 u32 offset = matches[i].offset;
566 u32 offset_bsr = bsr32(offset);
568 u32 base_cost = cur_cost + offset_bsr;
570 u32 adjusted_len = len - XPRESS_MIN_MATCH_LEN;
571 unsigned len_hdr = min(adjusted_len, 0xf);
572 unsigned sym = XPRESS_NUM_CHARS +
573 ((offset_bsr << 4) | len_hdr);
575 cost = base_cost + c->costs[sym];
576 if (adjusted_len >= 0xf) {
578 if (adjusted_len - 0xf >= 0xff)
582 if (cost < optimum_ptr->cost) {
583 optimum_ptr->prev.link = cur_pos;
584 optimum_ptr->prev.match_offset = offset;
585 optimum_ptr->cost = cost;
588 } while (++len <= matches[i].len);
589 } while (++i != num_matches);
595 } while (cur_pos != end_pos && cur_pos != XPRESS_OPTIM_ARRAY_LENGTH);
597 return xpress_match_chooser_reverse_list(c, cur_pos);
601 static struct lz_match
602 xpress_choose_lazy_item(struct xpress_compressor *c)
604 const struct lz_match *matches;
605 struct lz_match cur_match;
606 struct lz_match next_match;
609 if (c->prev_match.len) {
610 cur_match = c->prev_match;
611 c->prev_match.len = 0;
613 num_matches = xpress_get_matches(c, &matches);
614 if (num_matches == 0 ||
615 (matches[num_matches - 1].len == 3 &&
616 matches[num_matches - 1].offset >= c->len_3_too_far))
622 /* With lazy parsing we only consider the longest match at each
624 cur_match = matches[num_matches - 1];
627 if (cur_match.len >= c->params.nice_match_length) {
628 xpress_skip_bytes(c, cur_match.len - 1);
632 num_matches = xpress_get_matches(c, &matches);
633 if (num_matches == 0 ||
634 (matches[num_matches - 1].len == 3 &&
635 matches[num_matches - 1].offset >= c->len_3_too_far))
637 xpress_skip_bytes(c, cur_match.len - 2);
641 next_match = matches[num_matches - 1];
643 if (next_match.len <= cur_match.len) {
644 xpress_skip_bytes(c, cur_match.len - 2);
647 /* Longer match at next position. Choose a literal here so we
648 * will get to use the longer match. */
649 c->prev_match = next_match;
655 /* Greedy parsing. */
656 static struct lz_match
657 xpress_choose_greedy_item(struct xpress_compressor *c)
659 const struct lz_match *matches;
662 num_matches = xpress_get_matches(c, &matches);
663 if (num_matches == 0 ||
664 (matches[num_matches - 1].len == 3 &&
665 matches[num_matches - 1].offset >= c->len_3_too_far))
666 return (struct lz_match) {};
668 xpress_skip_bytes(c, matches[num_matches - 1].len - 1);
669 return matches[num_matches - 1];
672 /* Always choose a literal. */
673 static struct lz_match
674 xpress_choose_literal(struct xpress_compressor *c)
676 return (struct lz_match) {};
680 * Return the next match or literal to use, delegating to the currently selected
681 * match-choosing algorithm.
683 * If the length of the returned 'struct lz_match' is less than
684 * XPRESS_MIN_MATCH_LEN, then it is really a literal.
686 static inline struct lz_match
687 xpress_choose_item(struct xpress_compressor *c)
689 return (*c->params.choose_item_func)(c);
692 /* Set default XPRESS Huffman symbol costs to kick-start the iterative
693 * optimization algorithm. */
695 xpress_set_default_costs(u8 costs[])
699 for (i = 0; i < XPRESS_NUM_CHARS; i++)
702 for (; i < XPRESS_NUM_SYMBOLS; i++)
706 /* Copy the Huffman codeword lengths array @lens to the Huffman symbol costs
707 * array @costs, but also assign a default cost to each 0-length (unused)
710 xpress_set_costs(u8 costs[], const u8 lens[])
712 for (unsigned i = 0; i < XPRESS_NUM_SYMBOLS; i++)
713 costs[i] = lens[i] ? lens[i] : XPRESS_MAX_CODEWORD_LEN;
717 * Given the data to compress (c->cur_window, c->cur_window_size), fills in
718 * c->chosen_items with the intermediate representation of the match/literal
719 * sequence to output. Also fills in c->codewords and c->lens to provide the
720 * Huffman code with which these items should be output.
722 * Returns the number of items written to c->chosen_items. This can be at most
723 * c->cur_window_size. (The worst case is all literals, no matches.)
726 xpress_choose_items(struct xpress_compressor *c)
728 u32 num_passes_remaining = c->params.num_optim_passes;
729 const u8 *window_ptr;
730 const u8 *window_end;
731 struct xpress_item *next_chosen_item;
732 struct lz_match raw_item;
733 struct xpress_item xpress_item;
735 if (c->params.choose_item_func == xpress_choose_near_optimal_item) {
736 xpress_set_default_costs(c->costs);
737 c->optimum_cur_idx = 0;
738 c->optimum_end_idx = 0;
740 c->prev_match.len = 0;
741 if (c->cur_window_size <= 8192)
742 c->len_3_too_far = 2048;
744 c->len_3_too_far = 4096;
747 if (c->params.num_optim_passes > 1) {
748 c->get_matches_func = xpress_get_matches_fillcache;
749 c->skip_bytes_func = xpress_skip_bytes_fillcache;
751 c->get_matches_func = xpress_get_matches_noncaching;
752 c->skip_bytes_func = xpress_skip_bytes_noncaching;
755 lz_mf_load_window(c->mf, c->cur_window, c->cur_window_size);
757 while (--num_passes_remaining) {
758 window_ptr = c->cur_window_ptr = c->cur_window;
759 window_end = window_ptr + c->cur_window_size;
760 c->cache_ptr = c->cached_matches;
761 memset(c->freqs, 0, sizeof(c->freqs));
763 while (window_ptr != window_end) {
764 raw_item = xpress_choose_item(c);
765 if (raw_item.len >= XPRESS_MIN_MATCH_LEN) {
766 xpress_tally_match(raw_item.len,
767 raw_item.offset, c->freqs);
768 window_ptr += raw_item.len;
770 xpress_tally_literal(*window_ptr, c->freqs);
774 c->freqs[XPRESS_END_OF_DATA]++;
775 xpress_make_huffman_code(c);
776 xpress_set_costs(c->costs, c->lens);
777 if (c->cache_ptr <= c->cache_limit) {
778 c->get_matches_func = xpress_get_matches_usecache_nocheck;
779 c->skip_bytes_func = xpress_skip_bytes_usecache_nocheck;
781 c->get_matches_func = xpress_get_matches_usecache;
782 c->skip_bytes_func = xpress_skip_bytes_usecache;
786 window_ptr = c->cur_window_ptr = c->cur_window;
787 window_end = window_ptr + c->cur_window_size;
788 c->cache_ptr = c->cached_matches;
789 memset(c->freqs, 0, sizeof(c->freqs));
790 next_chosen_item = c->chosen_items;
793 while (window_ptr != window_end) {
794 raw_item = xpress_choose_item(c);
795 if (raw_item.len >= XPRESS_MIN_MATCH_LEN) {
796 xpress_item = xpress_tally_match(raw_item.len,
799 window_ptr += raw_item.len;
801 xpress_item = xpress_tally_literal(*window_ptr,
805 *next_chosen_item++ = xpress_item;
807 /* When doing one-pass near-optimal parsing, rebuild the Huffman
808 * code occasionally. */
809 if (unlikely((next_chosen_item - c->chosen_items) % 2048 == 0) &&
810 c->params.choose_item_func == xpress_choose_near_optimal_item &&
811 c->cur_window_size >= 16384 &&
812 c->params.num_optim_passes == 1)
814 xpress_make_huffman_code(c);
815 for (unsigned i = 0; i < XPRESS_NUM_SYMBOLS; i++)
816 c->costs[i] = c->lens[i] ? c->lens[i] : unseen_cost;
817 if (unseen_cost < 15)
821 c->freqs[XPRESS_END_OF_DATA]++;
822 xpress_make_huffman_code(c);
823 return next_chosen_item - c->chosen_items;
826 /* Given the specified compression level and maximum window size, build the
827 * parameters to use for XPRESS compression. */
829 xpress_build_params(unsigned int compression_level, u32 max_window_size,
830 struct xpress_compressor_params *xpress_params)
832 memset(xpress_params, 0, sizeof(*xpress_params));
834 if (compression_level == 1) {
836 /* Huffman only (no Lempel-Ziv matches) */
837 xpress_params->mf_algo = LZ_MF_NULL;
838 xpress_params->choose_item_func = xpress_choose_literal;
839 xpress_params->num_optim_passes = 1;
841 } else if (compression_level < 30) {
844 xpress_params->mf_algo = LZ_MF_HASH_CHAINS;
845 xpress_params->choose_item_func = xpress_choose_greedy_item;
846 xpress_params->num_optim_passes = 1;
847 xpress_params->nice_match_length = compression_level;
848 xpress_params->max_search_depth = compression_level / 2;
850 } else if (compression_level < 60) {
853 xpress_params->mf_algo = LZ_MF_HASH_CHAINS;
854 xpress_params->choose_item_func = xpress_choose_lazy_item;
855 xpress_params->num_optim_passes = 1;
856 xpress_params->nice_match_length = compression_level;
857 xpress_params->max_search_depth = compression_level / 2;
861 /* Near-optimal parsing */
862 xpress_params->choose_item_func = xpress_choose_near_optimal_item;
863 if (max_window_size >= 32768)
864 xpress_params->mf_algo = LZ_MF_BINARY_TREES;
866 xpress_params->mf_algo = LZ_MF_HASH_CHAINS;
867 xpress_params->num_optim_passes = compression_level / 40;
868 xpress_params->nice_match_length = min(compression_level / 2,
869 XPRESS_MAX_MATCH_LEN);
870 xpress_params->max_search_depth = min(compression_level,
871 XPRESS_MAX_MATCH_LEN);
875 /* Given the specified XPRESS parameters and maximum window size, build the
876 * parameters to use for match-finding. */
878 xpress_build_mf_params(const struct xpress_compressor_params *xpress_params,
879 u32 max_window_size, struct lz_mf_params *mf_params)
881 memset(mf_params, 0, sizeof(*mf_params));
883 mf_params->algorithm = xpress_params->mf_algo;
884 mf_params->max_window_size = max_window_size;
885 mf_params->min_match_len = XPRESS_MIN_MATCH_LEN;
886 mf_params->max_match_len = XPRESS_MAX_MATCH_LEN;
887 mf_params->max_search_depth = xpress_params->max_search_depth;
888 mf_params->nice_match_len = xpress_params->nice_match_length;
892 xpress_window_size_valid(size_t window_size)
894 return (window_size > 0 && window_size <= XPRESS_MAX_OFFSET + 1);
898 xpress_free_compressor(void *_c);
901 xpress_get_needed_memory(size_t max_window_size, unsigned int compression_level)
904 struct xpress_compressor_params params;
906 if (!xpress_window_size_valid(max_window_size))
909 xpress_build_params(compression_level, max_window_size, ¶ms);
911 size += sizeof(struct xpress_compressor);
913 size += lz_mf_get_needed_memory(params.mf_algo, max_window_size);
915 if (params.num_optim_passes > 1) {
916 size_t cache_len = max(max_window_size * XPRESS_CACHE_PER_POS,
917 params.max_search_depth + 1);
918 size += cache_len * sizeof(struct lz_match);
920 size += params.max_search_depth * sizeof(struct lz_match);
923 if (params.choose_item_func == xpress_choose_near_optimal_item) {
924 size += (XPRESS_OPTIM_ARRAY_LENGTH + params.nice_match_length) *
925 sizeof(struct xpress_mc_pos_data);
928 size += max_window_size * sizeof(struct xpress_item);
934 xpress_create_compressor(size_t max_window_size, unsigned int compression_level,
937 struct xpress_compressor *c;
938 struct xpress_compressor_params params;
939 struct lz_mf_params mf_params;
941 if (!xpress_window_size_valid(max_window_size))
942 return WIMLIB_ERR_INVALID_PARAM;
944 xpress_build_params(compression_level, max_window_size, ¶ms);
945 xpress_build_mf_params(¶ms, max_window_size, &mf_params);
947 c = CALLOC(1, sizeof(struct xpress_compressor));
953 c->mf = lz_mf_alloc(&mf_params);
957 if (params.num_optim_passes > 1) {
958 size_t cache_len = max(max_window_size * XPRESS_CACHE_PER_POS,
959 params.max_search_depth + 1);
960 c->cached_matches = MALLOC(cache_len * sizeof(struct lz_match));
961 if (!c->cached_matches)
963 c->cache_limit = c->cached_matches + cache_len -
964 (params.max_search_depth + 1);
966 c->cached_matches = MALLOC(params.max_search_depth *
967 sizeof(struct lz_match));
968 if (!c->cached_matches)
972 if (params.choose_item_func == xpress_choose_near_optimal_item) {
973 c->optimum = MALLOC((XPRESS_OPTIM_ARRAY_LENGTH +
974 params.nice_match_length) *
975 sizeof(struct xpress_mc_pos_data));
980 c->chosen_items = MALLOC(max_window_size * sizeof(struct xpress_item));
981 if (!c->chosen_items)
988 xpress_free_compressor(c);
989 return WIMLIB_ERR_NOMEM;
993 xpress_compress(const void *uncompressed_data, size_t uncompressed_size,
994 void *compressed_data, size_t compressed_size_avail, void *_c)
996 struct xpress_compressor *c = _c;
997 u32 num_chosen_items;
999 struct output_bitstream ostream;
1000 u32 compressed_size;
1002 /* XPRESS requires 256 bytes of overhead for the Huffman code, so it's
1003 * impossible to compress 256 bytes or less of data to less than the
1006 * +1 to take into account that the buffer for compressed data is 1 byte
1007 * smaller than the buffer for uncompressed data.
1009 * +4 to take into account that init_output_bitstream() requires at
1010 * least 4 bytes of data. */
1011 if (compressed_size_avail < XPRESS_NUM_SYMBOLS / 2 + 1 + 4)
1014 /* Determine match/literal sequence to divide the data into. */
1015 c->cur_window = uncompressed_data;
1016 c->cur_window_size = uncompressed_size;
1017 num_chosen_items = xpress_choose_items(c);
1019 /* Output the Huffman code as a series of 512 4-bit lengths. */
1020 cptr = compressed_data;
1021 for (unsigned i = 0; i < XPRESS_NUM_SYMBOLS; i += 2)
1022 *cptr++ = (c->lens[i] & 0xf) | (c->lens[i + 1] << 4);
1024 /* Output the encoded matches/literals. */
1025 init_output_bitstream(&ostream, cptr,
1026 compressed_size_avail - XPRESS_NUM_SYMBOLS / 2 - 1);
1027 xpress_write_items(&ostream, c->chosen_items, num_chosen_items,
1028 c->codewords, c->lens);
1030 /* Flush any pending data and get the length of the compressed data. */
1031 compressed_size = flush_output_bitstream(&ostream);
1032 if (compressed_size == (u32)~0UL)
1035 /* Return the length of the compressed data. */
1036 return compressed_size + XPRESS_NUM_SYMBOLS / 2;
1040 xpress_free_compressor(void *_c)
1042 struct xpress_compressor *c = _c;
1046 FREE(c->cached_matches);
1048 FREE(c->chosen_items);
1053 const struct compressor_ops xpress_compressor_ops = {
1054 .get_needed_memory = xpress_get_needed_memory,
1055 .create_compressor = xpress_create_compressor,
1056 .compress = xpress_compress,
1057 .free_compressor = xpress_free_compressor,