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/endianness.h"
34 #include "wimlib/error.h"
35 #include "wimlib/lz_mf.h"
36 #include "wimlib/util.h"
37 #include "wimlib/xpress.h"
41 #define XPRESS_CACHE_PER_POS 8
42 #define XPRESS_OPTIM_ARRAY_LENGTH 4096
44 struct xpress_compressor;
46 struct xpress_mc_pos_data;
48 struct xpress_compressor_params {
50 /* Only used when choose_items_func == xpress_choose_items_near_optimal */
53 /* Given the data to compress (c->cur_window, c->cur_window_size),
54 * 'choose_items_func' fills in c->chosen_items with the intermediate
55 * representation of the match/literal sequence to output. Also fills
56 * in c->codewords and c->lens to provide the Huffman code with which
57 * these items should be output.
59 * Returns the number of items written to c->chosen_items. This can be
60 * at most c->cur_window_size. (The worst case is all literals, no
62 u32 (*choose_items_func)(struct xpress_compressor *c);
64 /* Match-finding algorithm and parameters */
65 enum lz_mf_algo mf_algo;
67 u32 nice_match_length;
70 /* XPRESS compressor state. */
71 struct xpress_compressor {
73 /* Parameters determined based on the compression level. */
74 struct xpress_compressor_params params;
76 /* Lempel-Ziv match-finder */
79 /* Optimal parsing data */
80 unsigned (*get_matches_func)(struct xpress_compressor *,
81 const struct lz_match **);
82 void (*skip_bytes_func)(struct xpress_compressor *, u32 n);
83 const u8 *cur_window_ptr;
84 struct lz_match *cached_matches;
85 struct lz_match *cache_ptr;
86 struct lz_match *cache_limit;
87 struct xpress_mc_pos_data *optimum;
88 unsigned optimum_cur_idx;
89 unsigned optimum_end_idx;
90 u8 costs[XPRESS_NUM_SYMBOLS];
92 /* The selected sequence of matches/literals */
93 struct xpress_item *chosen_items;
95 /* Data currently being compressed */
99 /* Symbol frequency counters */
100 u32 freqs[XPRESS_NUM_SYMBOLS];
102 /* The current Huffman code */
103 u32 codewords[XPRESS_NUM_SYMBOLS];
104 u8 lens[XPRESS_NUM_SYMBOLS];
107 /* Match-chooser position data.
108 * See corresponding declaration in lzx-compress.c for more information. */
109 struct xpress_mc_pos_data {
111 #define MC_INFINITE_COST ((u32)~0UL)
125 /* Intermediate XPRESS match/literal representation. */
127 u16 adjusted_len; /* Match length minus XPRESS_MIN_MATCH_LEN */
128 u16 offset; /* Match offset */
129 /* For literals, offset == 0 and adjusted_len is the literal byte. */
133 * Structure to keep track of the current state of sending data to the
134 * compressed output buffer.
136 * The XPRESS bitstream is encoded as a sequence of little endian 16-bit coding
137 * units interwoven with literal bytes.
139 struct xpress_output_bitstream {
141 /* Bits that haven't yet been written to the output buffer. */
144 /* Number of bits currently held in @bitbuf. */
147 /* Pointer to the start of the output buffer. */
150 /* Pointer to the location in the ouput buffer at which to write the
154 /* Pointer to the location in the output buffer at which to write the
155 * next 16 bits, after @next_bits. */
158 /* Pointer to the location in the output buffer at which to write the
159 * next literal byte. */
162 /* Pointer to the end of the output buffer. */
167 * Initialize the output bitstream.
170 * The output bitstream structure to initialize.
172 * The buffer to write to.
174 * Size of @buffer, in bytes. Must be at least 4.
177 xpress_init_output(struct xpress_output_bitstream *os, void *buffer, u32 size)
182 os->next_bits = os->start;
183 os->next_bits2 = os->start + 2;
184 os->next_byte = os->start + 4;
185 os->end = os->start + size;
189 * Write some bits to the output bitstream.
191 * The bits are given by the low-order @num_bits bits of @bits. Higher-order
192 * bits in @bits cannot be set. At most 16 bits can be written at once.
194 * If the output buffer space is exhausted, then the bits will be ignored, and
195 * xpress_flush_output() will return 0 when it gets called.
197 static _always_inline_attribute void
198 xpress_write_bits(struct xpress_output_bitstream *os,
199 const u32 bits, const unsigned int num_bits)
201 /* This code is optimized for XPRESS, which never needs to write more
202 * than 16 bits at once. */
204 os->bitcount += num_bits;
205 os->bitbuf = (os->bitbuf << num_bits) | bits;
207 if (os->bitcount > 16) {
209 if (os->end - os->next_byte >= 2) {
210 *(le16 *)os->next_bits = cpu_to_le16(os->bitbuf >> os->bitcount);
211 os->next_bits = os->next_bits2;
212 os->next_bits2 = os->next_byte;
219 * Interweave a literal byte into the output bitstream.
221 static _always_inline_attribute void
222 xpress_write_byte(struct xpress_output_bitstream *os, u8 byte)
224 if (os->next_byte < os->end)
225 *os->next_byte++ = byte;
229 * Flush the last coding unit to the output buffer if needed. Return the total
230 * number of bytes written to the output buffer, or 0 if an overflow occurred.
233 xpress_flush_output(struct xpress_output_bitstream *os)
235 if (unlikely(os->end - os->next_byte < 2))
238 *(le16 *)os->next_bits = cpu_to_le16(os->bitbuf << (16 - os->bitcount));
239 *(le16 *)os->next_bits2 = cpu_to_le16(0);
241 return os->next_byte - os->start;
244 /* Output an XPRESS match. */
246 xpress_write_match(struct xpress_item match, struct xpress_output_bitstream *os,
247 const u32 codewords[], const u8 lens[])
249 unsigned len_hdr = min(match.adjusted_len, 0xf);
250 unsigned offset_bsr = bsr32(match.offset);
251 unsigned sym = XPRESS_NUM_CHARS + ((offset_bsr << 4) | len_hdr);
254 xpress_write_bits(os, codewords[sym], lens[sym]);
256 /* If length >= 18, one extra length byte.
257 * If length >= 273, three (total) extra length bytes. */
258 if (match.adjusted_len >= 0xf) {
259 u8 byte1 = min(match.adjusted_len - 0xf, 0xff);
260 xpress_write_byte(os, byte1);
262 xpress_write_byte(os, match.adjusted_len & 0xff);
263 xpress_write_byte(os, match.adjusted_len >> 8);
268 xpress_write_bits(os, match.offset ^ (1U << offset_bsr), offset_bsr);
271 /* Output a sequence of XPRESS matches and literals. */
273 xpress_write_items(struct xpress_output_bitstream *os,
274 const struct xpress_item items[], u32 num_items,
275 const u32 codewords[], const u8 lens[])
277 for (u32 i = 0; i < num_items; i++) {
278 if (items[i].offset) {
280 xpress_write_match(items[i], os, codewords, lens);
283 unsigned lit = items[i].adjusted_len;
284 xpress_write_bits(os, codewords[lit], lens[lit]);
287 /* End-of-data symbol (required for MS compatibility) */
288 xpress_write_bits(os, codewords[XPRESS_END_OF_DATA], lens[XPRESS_END_OF_DATA]);
291 /* Make the Huffman code for XPRESS.
293 * Takes as input c->freqs and produces as output c->lens and c->codewords. */
295 xpress_make_huffman_code(struct xpress_compressor *c)
297 make_canonical_huffman_code(XPRESS_NUM_SYMBOLS, XPRESS_MAX_CODEWORD_LEN,
298 c->freqs, c->lens, c->codewords);
301 /* Account for the Huffman symbol that would be produced by outputting the
302 * specified literal. Returns the intermediate representation of the literal.
304 static inline struct xpress_item
305 xpress_tally_literal(u8 lit, u32 freqs[])
308 return (struct xpress_item) { .offset = 0, .adjusted_len = lit };
311 /* Account for the Huffman symbol that would be produced by outputting the
312 * specified match. Returns the intermediate representation of the match. */
313 static inline struct xpress_item
314 xpress_tally_match(u32 len, u32 offset, u32 freqs[])
316 u32 adjusted_len = len - XPRESS_MIN_MATCH_LEN;
317 unsigned len_hdr = min(adjusted_len, 0xf);
318 unsigned sym = XPRESS_NUM_CHARS + ((bsr32(offset) << 4) | len_hdr);
321 return (struct xpress_item) { .offset = offset,
322 .adjusted_len = adjusted_len };
326 xpress_get_matches_fillcache(struct xpress_compressor *c,
327 const struct lz_match **matches_ret)
329 struct lz_match *cache_ptr;
330 struct lz_match *matches;
331 unsigned num_matches;
333 cache_ptr = c->cache_ptr;
334 matches = cache_ptr + 1;
335 if (likely(cache_ptr <= c->cache_limit)) {
336 num_matches = lz_mf_get_matches(c->mf, matches);
337 cache_ptr->len = num_matches;
338 c->cache_ptr = matches + num_matches;
343 *matches_ret = matches;
348 xpress_get_matches_usecache(struct xpress_compressor *c,
349 const struct lz_match **matches_ret)
351 struct lz_match *cache_ptr;
352 struct lz_match *matches;
353 unsigned num_matches;
355 cache_ptr = c->cache_ptr;
356 matches = cache_ptr + 1;
357 if (likely(cache_ptr <= c->cache_limit)) {
358 num_matches = cache_ptr->len;
359 c->cache_ptr = matches + num_matches;
364 *matches_ret = matches;
369 xpress_get_matches_usecache_nocheck(struct xpress_compressor *c,
370 const struct lz_match **matches_ret)
372 struct lz_match *cache_ptr;
373 struct lz_match *matches;
374 unsigned num_matches;
376 cache_ptr = c->cache_ptr;
377 matches = cache_ptr + 1;
378 num_matches = cache_ptr->len;
379 c->cache_ptr = matches + num_matches;
381 *matches_ret = matches;
386 xpress_get_matches_noncaching(struct xpress_compressor *c,
387 const struct lz_match **matches_ret)
390 *matches_ret = c->cached_matches;
391 return lz_mf_get_matches(c->mf, c->cached_matches);
395 * Find matches at the next position in the window.
397 * Returns the number of matches found and sets *matches_ret to point to the
398 * matches array. The matches will be sorted by strictly increasing length and
401 static inline unsigned
402 xpress_get_matches(struct xpress_compressor *c,
403 const struct lz_match **matches_ret)
405 return (*c->get_matches_func)(c, matches_ret);
409 xpress_skip_bytes_fillcache(struct xpress_compressor *c, u32 n)
411 struct lz_match *cache_ptr;
413 c->cur_window_ptr += n;
414 cache_ptr = c->cache_ptr;
415 lz_mf_skip_positions(c->mf, n);
416 if (likely(cache_ptr <= c->cache_limit)) {
420 } while (--n && likely(cache_ptr <= c->cache_limit));
422 c->cache_ptr = cache_ptr;
426 xpress_skip_bytes_usecache(struct xpress_compressor *c, u32 n)
428 struct lz_match *cache_ptr;
430 c->cur_window_ptr += n;
431 cache_ptr = c->cache_ptr;
432 if (likely(cache_ptr <= c->cache_limit)) {
434 cache_ptr += 1 + cache_ptr->len;
435 } while (--n && likely(cache_ptr <= c->cache_limit));
437 c->cache_ptr = cache_ptr;
441 xpress_skip_bytes_usecache_nocheck(struct xpress_compressor *c, u32 n)
443 struct lz_match *cache_ptr;
445 c->cur_window_ptr += n;
446 cache_ptr = c->cache_ptr;
448 cache_ptr += 1 + cache_ptr->len;
450 c->cache_ptr = cache_ptr;
454 xpress_skip_bytes_noncaching(struct xpress_compressor *c, u32 n)
456 c->cur_window_ptr += n;
457 lz_mf_skip_positions(c->mf, n);
461 * Skip the specified number of positions in the window (don't search for
465 xpress_skip_bytes(struct xpress_compressor *c, u32 n)
467 return (*c->skip_bytes_func)(c, n);
471 * Returns the cost, in bits, required to output the literal from the previous
472 * window position (the position at which matches were last searched).
475 xpress_prev_literal_cost(const struct xpress_compressor *c)
477 return c->costs[*(c->cur_window_ptr - 1)];
481 * Reverse the linked list of near-optimal matches so that they can be returned
484 * Returns the first match in the list.
486 static struct lz_match
487 xpress_match_chooser_reverse_list(struct xpress_compressor *c, unsigned cur_pos)
489 unsigned prev_link, saved_prev_link;
490 u32 prev_match_offset, saved_prev_match_offset;
492 c->optimum_end_idx = cur_pos;
494 saved_prev_link = c->optimum[cur_pos].prev.link;
495 saved_prev_match_offset = c->optimum[cur_pos].prev.match_offset;
498 prev_link = saved_prev_link;
499 prev_match_offset = saved_prev_match_offset;
501 saved_prev_link = c->optimum[prev_link].prev.link;
502 saved_prev_match_offset = c->optimum[prev_link].prev.match_offset;
504 c->optimum[prev_link].next.link = cur_pos;
505 c->optimum[prev_link].next.match_offset = prev_match_offset;
508 } while (cur_pos != 0);
510 c->optimum_cur_idx = c->optimum[0].next.link;
512 return (struct lz_match)
513 { .len = c->optimum_cur_idx,
514 .offset = c->optimum[0].next.match_offset,
519 * Near-optimal parsing.
521 * This does a forward lowest-cost path search. The search is terminated when a
522 * sufficiently long match is found, when the search reaches a position with no
523 * alternatives, or when the temporary 'optimum' array fills up. After
524 * termination of the search, matches/literals will be returned one by one by
525 * successive calls to this function. Once all the matches/literals are used
526 * up, the next call to this function will begin a new search.
528 static struct lz_match
529 xpress_choose_near_optimal_item(struct xpress_compressor *c)
531 const struct lz_match *matches;
532 unsigned num_matches;
533 struct lz_match match;
536 struct xpress_mc_pos_data * const optimum = c->optimum;
538 if (c->optimum_cur_idx != c->optimum_end_idx) {
539 /* Return previously computed match or literal. */
540 match.len = optimum[c->optimum_cur_idx].next.link -
542 match.offset = optimum[c->optimum_cur_idx].next.match_offset;
544 c->optimum_cur_idx = optimum[c->optimum_cur_idx].next.link;
548 c->optimum_cur_idx = 0;
549 c->optimum_end_idx = 0;
551 num_matches = xpress_get_matches(c, &matches);
553 if (num_matches == 0)
554 return (struct lz_match) {};
556 if (matches[num_matches - 1].len >= c->params.nice_match_length) {
557 /* Take the long match immediately. */
558 xpress_skip_bytes(c, matches[num_matches - 1].len - 1);
559 return matches[num_matches - 1];
562 /* Consider coding a literal. */
563 optimum[1].cost = xpress_prev_literal_cost(c);
564 optimum[1].prev.link = 0;
566 optimum[2].cost = MC_INFINITE_COST;
569 /* Consider coding a match. Cost evaluation is hand-inlined so
570 * that we can do some performance hacks. */
574 struct xpress_mc_pos_data *optimum_ptr = &optimum[len];
576 if (matches[num_matches - 1].len < 0xf + XPRESS_MIN_MATCH_LEN) {
578 u32 offset = matches[i].offset;
579 u32 offset_bsr = bsr32(offset);
580 unsigned len_hdr = len - XPRESS_MIN_MATCH_LEN;
581 unsigned sym = XPRESS_NUM_CHARS +
582 ((offset_bsr << 4) | len_hdr);
584 optimum_ptr->prev.link = 0;
585 optimum_ptr->prev.match_offset = offset;
586 optimum_ptr->cost = offset_bsr + c->costs[sym];
589 } while (++len <= matches[i].len);
590 } while (++i != num_matches);
593 u32 offset = matches[i].offset;
594 u32 offset_bsr = bsr32(offset);
596 u32 adjusted_len = len - XPRESS_MIN_MATCH_LEN;
597 unsigned len_hdr = min(adjusted_len, 0xf);
598 unsigned sym = XPRESS_NUM_CHARS +
599 ((offset_bsr << 4) | len_hdr);
600 u32 cost = offset_bsr + c->costs[sym];
601 if (adjusted_len >= 0xf) {
603 if (adjusted_len - 0xf >= 0xff)
607 optimum_ptr->prev.link = 0;
608 optimum_ptr->prev.match_offset = offset;
609 optimum_ptr->cost = cost;
611 } while (++len <= matches[i].len);
612 } while (++i != num_matches);
616 end_pos = matches[num_matches - 1].len;
622 num_matches = xpress_get_matches(c, &matches);
625 longest_len = matches[num_matches - 1].len;
626 if (longest_len >= c->params.nice_match_length) {
627 /* Take the long match immediately. */
628 match = xpress_match_chooser_reverse_list(c, cur_pos);
630 optimum[cur_pos].next.match_offset =
631 matches[num_matches - 1].offset;
632 optimum[cur_pos].next.link = cur_pos + longest_len;
633 c->optimum_end_idx = cur_pos + longest_len;
635 xpress_skip_bytes(c, longest_len - 1);
643 while (end_pos < cur_pos + longest_len)
644 optimum[++end_pos].cost = MC_INFINITE_COST;
646 /* Consider coding a literal. */
647 cost = optimum[cur_pos].cost + xpress_prev_literal_cost(c);
648 if (cost < optimum[cur_pos + 1].cost) {
649 optimum[cur_pos + 1].cost = cost;
650 optimum[cur_pos + 1].prev.link = cur_pos;
654 /* Consider coding a match. Cost evaluation is
655 * hand-inlined so that we can do some performance
659 struct xpress_mc_pos_data *optimum_ptr = &optimum[cur_pos + 3];
660 u32 cur_cost = optimum[cur_pos].cost;
662 if (matches[num_matches - 1].len < 0xf + XPRESS_MIN_MATCH_LEN) {
664 u32 offset = matches[i].offset;
665 u32 offset_bsr = bsr32(offset);
666 unsigned len_hdr = len - XPRESS_MIN_MATCH_LEN;
667 unsigned sym = XPRESS_NUM_CHARS +
668 ((offset_bsr << 4) | len_hdr);
670 u32 base_cost = cur_cost + offset_bsr;
672 cost = base_cost + c->costs[sym];
673 if (cost < optimum_ptr->cost) {
674 optimum_ptr->prev.link = cur_pos;
675 optimum_ptr->prev.match_offset = offset;
676 optimum_ptr->cost = cost;
680 } while (++len <= matches[i].len);
681 } while (++i != num_matches);
684 u32 offset = matches[i].offset;
685 u32 offset_bsr = bsr32(offset);
687 u32 base_cost = cur_cost + offset_bsr;
689 u32 adjusted_len = len - XPRESS_MIN_MATCH_LEN;
690 unsigned len_hdr = min(adjusted_len, 0xf);
691 unsigned sym = XPRESS_NUM_CHARS +
692 ((offset_bsr << 4) | len_hdr);
694 cost = base_cost + c->costs[sym];
695 if (adjusted_len >= 0xf) {
697 if (adjusted_len - 0xf >= 0xff)
701 if (cost < optimum_ptr->cost) {
702 optimum_ptr->prev.link = cur_pos;
703 optimum_ptr->prev.match_offset = offset;
704 optimum_ptr->cost = cost;
707 } while (++len <= matches[i].len);
708 } while (++i != num_matches);
714 } while (cur_pos != end_pos && cur_pos != XPRESS_OPTIM_ARRAY_LENGTH);
716 return xpress_match_chooser_reverse_list(c, cur_pos);
719 /* Set default XPRESS Huffman symbol costs to kick-start the iterative
720 * optimization algorithm. */
722 xpress_set_default_costs(u8 costs[])
726 for (i = 0; i < XPRESS_NUM_CHARS; i++)
729 for (; i < XPRESS_NUM_SYMBOLS; i++)
733 /* Copy the Huffman codeword lengths array @lens to the Huffman symbol costs
734 * array @costs, but also assign a default cost to each 0-length (unused)
737 xpress_set_costs(u8 costs[], const u8 lens[])
739 for (unsigned i = 0; i < XPRESS_NUM_SYMBOLS; i++)
740 costs[i] = lens[i] ? lens[i] : XPRESS_MAX_CODEWORD_LEN;
743 /* Near-optimal parsing */
745 xpress_choose_items_near_optimal(struct xpress_compressor *c)
747 u32 num_passes_remaining = c->params.num_optim_passes;
748 const u8 *window_ptr;
749 const u8 *window_end;
750 struct xpress_item *next_chosen_item;
751 struct lz_match raw_item;
752 struct xpress_item xpress_item;
754 xpress_set_default_costs(c->costs);
755 c->optimum_cur_idx = 0;
756 c->optimum_end_idx = 0;
758 if (c->params.num_optim_passes > 1) {
759 c->get_matches_func = xpress_get_matches_fillcache;
760 c->skip_bytes_func = xpress_skip_bytes_fillcache;
762 c->get_matches_func = xpress_get_matches_noncaching;
763 c->skip_bytes_func = xpress_skip_bytes_noncaching;
766 lz_mf_load_window(c->mf, c->cur_window, c->cur_window_size);
768 while (--num_passes_remaining) {
769 c->cur_window_ptr = c->cur_window;
770 window_ptr = c->cur_window;
771 window_end = window_ptr + c->cur_window_size;
772 c->cache_ptr = c->cached_matches;
773 memset(c->freqs, 0, sizeof(c->freqs));
775 while (window_ptr != window_end) {
776 raw_item = xpress_choose_near_optimal_item(c);
777 if (raw_item.len >= XPRESS_MIN_MATCH_LEN) {
778 xpress_tally_match(raw_item.len,
779 raw_item.offset, c->freqs);
780 window_ptr += raw_item.len;
782 xpress_tally_literal(*window_ptr, c->freqs);
786 c->freqs[XPRESS_END_OF_DATA]++;
787 xpress_make_huffman_code(c);
788 xpress_set_costs(c->costs, c->lens);
789 if (c->cache_ptr <= c->cache_limit) {
790 c->get_matches_func = xpress_get_matches_usecache_nocheck;
791 c->skip_bytes_func = xpress_skip_bytes_usecache_nocheck;
793 c->get_matches_func = xpress_get_matches_usecache;
794 c->skip_bytes_func = xpress_skip_bytes_usecache;
798 c->cur_window_ptr = c->cur_window;
799 window_ptr = c->cur_window;
800 window_end = window_ptr + c->cur_window_size;
801 c->cache_ptr = c->cached_matches;
802 memset(c->freqs, 0, sizeof(c->freqs));
803 next_chosen_item = c->chosen_items;
806 while (window_ptr != window_end) {
807 raw_item = xpress_choose_near_optimal_item(c);
808 if (raw_item.len >= XPRESS_MIN_MATCH_LEN) {
809 xpress_item = xpress_tally_match(raw_item.len,
812 window_ptr += raw_item.len;
814 xpress_item = xpress_tally_literal(*window_ptr,
818 *next_chosen_item++ = xpress_item;
820 /* When doing one-pass near-optimal parsing, rebuild the Huffman
821 * code occasionally. */
822 if (unlikely((next_chosen_item - c->chosen_items) % 2048 == 0) &&
823 c->cur_window_size >= 16384 &&
824 c->params.num_optim_passes == 1)
826 xpress_make_huffman_code(c);
827 for (unsigned i = 0; i < XPRESS_NUM_SYMBOLS; i++)
828 c->costs[i] = c->lens[i] ? c->lens[i] : unseen_cost;
829 if (unseen_cost < 15)
833 c->freqs[XPRESS_END_OF_DATA]++;
834 xpress_make_huffman_code(c);
835 return next_chosen_item - c->chosen_items;
840 xpress_choose_items_lazy(struct xpress_compressor *c)
844 const u8 *window_ptr;
845 const u8 *window_end;
847 struct lz_match matches[min(c->params.nice_match_length, c->params.max_search_depth)];
848 struct xpress_item *next_chosen_item;
849 struct lz_match prev_match;
853 lz_mf_load_window(mf, c->cur_window, c->cur_window_size);
855 if (c->cur_window_size <= 8192)
856 len_3_too_far = 2048;
858 len_3_too_far = 4096;
860 memset(c->freqs, 0, sizeof(c->freqs));
862 window_ptr = c->cur_window;
863 window_end = c->cur_window + c->cur_window_size;
864 next_chosen_item = c->chosen_items;
868 /* Don't have match at previous position */
870 num_matches = lz_mf_get_matches(mf, matches);
873 if (num_matches == 0 ||
874 (matches[num_matches - 1].len == 3 &&
875 matches[num_matches - 1].offset >= len_3_too_far))
877 /* No matches found => output literal */
878 *next_chosen_item++ = xpress_tally_literal(*(window_ptr - 1),
880 if (window_ptr == window_end)
885 prev_match = matches[num_matches - 1];
888 /* Have match at previous position */
890 if (prev_match.len >= c->params.nice_match_length) {
891 /* Very long match found => output immediately */
892 *next_chosen_item++ = xpress_tally_match(prev_match.len,
895 lz_mf_skip_positions(mf, prev_match.len - 1);
896 window_ptr += prev_match.len - 1;
897 if (window_ptr == window_end)
902 num_matches = lz_mf_get_matches(mf, matches);
905 if (num_matches == 0 ||
906 (matches[num_matches - 1].len <= prev_match.len))
908 /* Next match is not longer => output previous match */
909 *next_chosen_item++ = xpress_tally_match(prev_match.len,
912 lz_mf_skip_positions(mf, prev_match.len - 2);
913 window_ptr += prev_match.len - 2;
914 if (window_ptr == window_end)
919 /* Next match is longer => output literal */
921 *next_chosen_item++ = xpress_tally_literal(*(window_ptr - 2),
924 prev_match = matches[num_matches - 1];
926 goto have_prev_match;
929 c->freqs[XPRESS_END_OF_DATA]++;
930 xpress_make_huffman_code(c);
931 return next_chosen_item - c->chosen_items;
936 xpress_choose_items_greedy(struct xpress_compressor *c)
940 const u8 *window_ptr;
941 const u8 *window_end;
942 struct lz_match matches[min(c->params.nice_match_length, c->params.max_search_depth)];
944 struct xpress_item *next_chosen_item;
948 lz_mf_load_window(mf, c->cur_window, c->cur_window_size);
950 if (c->cur_window_size <= 8192)
951 len_3_too_far = 2048;
953 len_3_too_far = 4096;
955 memset(c->freqs, 0, sizeof(c->freqs));
957 window_ptr = c->cur_window;
958 window_end = c->cur_window + c->cur_window_size;
959 next_chosen_item = c->chosen_items;
962 /* Get longest match at the current position. */
963 num_matches = lz_mf_get_matches(mf, matches);
965 if (num_matches == 0 ||
966 (matches[num_matches - 1].len == 3 &&
967 matches[num_matches - 1].offset >= len_3_too_far))
969 *next_chosen_item++ = xpress_tally_literal(*window_ptr, c->freqs);
972 u32 len = matches[num_matches - 1].len;
973 u32 offset = matches[num_matches - 1].offset;
975 *next_chosen_item++ = xpress_tally_match(len, offset, c->freqs);
976 lz_mf_skip_positions(mf, len - 1);
979 } while (window_ptr != window_end);
981 c->freqs[XPRESS_END_OF_DATA]++;
982 xpress_make_huffman_code(c);
983 return next_chosen_item - c->chosen_items;
986 /* Huffman-only parsing */
988 xpress_choose_items_huffonly(struct xpress_compressor *c)
990 const u8 *window_ptr;
991 const u8 *window_end;
992 struct xpress_item *next_chosen_item;
994 memset(c->freqs, 0, sizeof(c->freqs));
996 window_ptr = c->cur_window;
997 window_end = c->cur_window + c->cur_window_size;
998 next_chosen_item = c->chosen_items;
1001 *next_chosen_item++ = xpress_tally_literal(*window_ptr++, c->freqs);
1002 } while (window_ptr != window_end);
1004 c->freqs[XPRESS_END_OF_DATA]++;
1005 xpress_make_huffman_code(c);
1006 return next_chosen_item - c->chosen_items;
1009 /* Given the specified compression level and maximum window size, build the
1010 * parameters to use for XPRESS compression. */
1012 xpress_build_params(unsigned int compression_level, u32 max_window_size,
1013 struct xpress_compressor_params *xpress_params)
1015 memset(xpress_params, 0, sizeof(*xpress_params));
1017 if (compression_level == 1) {
1019 /* Huffman only (no Lempel-Ziv matches) */
1020 xpress_params->mf_algo = LZ_MF_NULL;
1021 xpress_params->choose_items_func = xpress_choose_items_huffonly;
1023 } else if (compression_level < 30) {
1025 /* Greedy parsing */
1026 xpress_params->mf_algo = LZ_MF_HASH_CHAINS;
1027 xpress_params->choose_items_func = xpress_choose_items_greedy;
1028 xpress_params->nice_match_length = compression_level;
1029 xpress_params->max_search_depth = compression_level / 2;
1031 } else if (compression_level < 60) {
1034 xpress_params->mf_algo = LZ_MF_HASH_CHAINS;
1035 xpress_params->choose_items_func = xpress_choose_items_lazy;
1036 xpress_params->nice_match_length = compression_level;
1037 xpress_params->max_search_depth = compression_level / 2;
1041 /* Near-optimal parsing */
1042 xpress_params->choose_items_func = xpress_choose_items_near_optimal;
1043 if (max_window_size >= 32768)
1044 xpress_params->mf_algo = LZ_MF_BINARY_TREES;
1046 xpress_params->mf_algo = LZ_MF_HASH_CHAINS;
1047 xpress_params->num_optim_passes = compression_level / 40;
1048 xpress_params->nice_match_length = min(compression_level / 2,
1049 XPRESS_MAX_MATCH_LEN);
1050 xpress_params->max_search_depth = min(compression_level,
1051 XPRESS_MAX_MATCH_LEN);
1055 /* Given the specified XPRESS parameters and maximum window size, build the
1056 * parameters to use for match-finding. */
1058 xpress_build_mf_params(const struct xpress_compressor_params *xpress_params,
1059 u32 max_window_size, struct lz_mf_params *mf_params)
1061 memset(mf_params, 0, sizeof(*mf_params));
1063 mf_params->algorithm = xpress_params->mf_algo;
1064 mf_params->max_window_size = max_window_size;
1065 mf_params->min_match_len = XPRESS_MIN_MATCH_LEN;
1066 mf_params->max_match_len = XPRESS_MAX_MATCH_LEN;
1067 mf_params->max_search_depth = xpress_params->max_search_depth;
1068 mf_params->nice_match_len = xpress_params->nice_match_length;
1072 xpress_window_size_valid(size_t window_size)
1074 return (window_size > 0 && window_size <= XPRESS_MAX_OFFSET + 1);
1078 xpress_free_compressor(void *_c);
1081 xpress_get_needed_memory(size_t max_window_size, unsigned int compression_level)
1084 struct xpress_compressor_params params;
1086 if (!xpress_window_size_valid(max_window_size))
1089 xpress_build_params(compression_level, max_window_size, ¶ms);
1091 size += sizeof(struct xpress_compressor);
1093 size += lz_mf_get_needed_memory(params.mf_algo, max_window_size);
1095 if (params.choose_items_func == xpress_choose_items_near_optimal) {
1096 size += (XPRESS_OPTIM_ARRAY_LENGTH + params.nice_match_length) *
1097 sizeof(struct xpress_mc_pos_data);
1098 if (params.num_optim_passes > 1) {
1099 size_t cache_len = max(max_window_size * XPRESS_CACHE_PER_POS,
1100 params.max_search_depth + 1);
1101 size += cache_len * sizeof(struct lz_match);
1103 size += params.max_search_depth * sizeof(struct lz_match);
1107 size += max_window_size * sizeof(struct xpress_item);
1113 xpress_create_compressor(size_t max_window_size, unsigned int compression_level,
1116 struct xpress_compressor *c;
1117 struct xpress_compressor_params params;
1118 struct lz_mf_params mf_params;
1120 if (!xpress_window_size_valid(max_window_size))
1121 return WIMLIB_ERR_INVALID_PARAM;
1123 xpress_build_params(compression_level, max_window_size, ¶ms);
1124 xpress_build_mf_params(¶ms, max_window_size, &mf_params);
1126 c = CALLOC(1, sizeof(struct xpress_compressor));
1132 c->mf = lz_mf_alloc(&mf_params);
1136 if (params.choose_items_func == xpress_choose_items_near_optimal) {
1137 c->optimum = MALLOC((XPRESS_OPTIM_ARRAY_LENGTH +
1138 params.nice_match_length) *
1139 sizeof(struct xpress_mc_pos_data));
1142 if (params.num_optim_passes > 1) {
1143 size_t cache_len = max(max_window_size * XPRESS_CACHE_PER_POS,
1144 params.max_search_depth + 1);
1145 c->cached_matches = MALLOC(cache_len * sizeof(struct lz_match));
1146 if (!c->cached_matches)
1148 c->cache_limit = c->cached_matches + cache_len -
1149 (params.max_search_depth + 1);
1151 c->cached_matches = MALLOC(params.max_search_depth *
1152 sizeof(struct lz_match));
1153 if (!c->cached_matches)
1158 c->chosen_items = MALLOC(max_window_size * sizeof(struct xpress_item));
1159 if (!c->chosen_items)
1166 xpress_free_compressor(c);
1167 return WIMLIB_ERR_NOMEM;
1171 xpress_compress(const void *uncompressed_data, size_t uncompressed_size,
1172 void *compressed_data, size_t compressed_size_avail, void *_c)
1174 struct xpress_compressor *c = _c;
1175 u32 num_chosen_items;
1177 struct xpress_output_bitstream os;
1178 u32 compressed_size;
1180 /* XPRESS requires 256 bytes of overhead for the Huffman code, so it's
1181 * impossible to compress 256 bytes or less of data to less than the
1183 if (compressed_size_avail < XPRESS_NUM_SYMBOLS / 2 + 50)
1186 /* Determine match/literal sequence to divide the data into. */
1187 c->cur_window = uncompressed_data;
1188 c->cur_window_size = uncompressed_size;
1189 num_chosen_items = (*c->params.choose_items_func)(c);
1191 /* Output the Huffman code as a series of 512 4-bit lengths. */
1192 cptr = compressed_data;
1193 for (unsigned i = 0; i < XPRESS_NUM_SYMBOLS; i += 2)
1194 *cptr++ = (c->lens[i] & 0xf) | (c->lens[i + 1] << 4);
1196 /* Output the encoded matches/literals. */
1197 xpress_init_output(&os, cptr,
1198 compressed_size_avail - XPRESS_NUM_SYMBOLS / 2);
1199 xpress_write_items(&os, c->chosen_items, num_chosen_items,
1200 c->codewords, c->lens);
1202 /* Flush any pending data and get the length of the compressed data. */
1203 compressed_size = xpress_flush_output(&os);
1204 if (compressed_size == 0)
1207 /* Return the length of the compressed data. */
1208 return compressed_size + XPRESS_NUM_SYMBOLS / 2;
1212 xpress_free_compressor(void *_c)
1214 struct xpress_compressor *c = _c;
1218 FREE(c->cached_matches);
1220 FREE(c->chosen_items);
1225 const struct compressor_ops xpress_compressor_ops = {
1226 .get_needed_memory = xpress_get_needed_memory,
1227 .create_compressor = xpress_create_compressor,
1228 .compress = xpress_compress,
1229 .free_compressor = xpress_free_compressor,