wimlib.net Git - wimlib/blob - src/xpress-compress.c

   1 /*
   2  * xpress-compress.c
   3  *
   4  * A compressor that produces output compatible with the XPRESS (Huffman
   5  * version) compression format.
   6  */
   7
   8 /*
   9  * Copyright (C) 2012, 2013, 2014 Eric Biggers
  10  *
  11  * This file is part of wimlib, a library for working with WIM files.
  12  *
  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)
  16  * any later version.
  17  *
  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
  21  * details.
  22  *
  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/.
  25  */
  26
  27 #ifdef HAVE_CONFIG_H
  28 #  include "config.h"
  29 #endif
  30
  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"
  37
  38 #include <string.h>
  39
  40 #define XPRESS_CACHE_PER_POS            8
  41 #define XPRESS_OPTIM_ARRAY_LENGTH       4096
  42
  43 struct xpress_compressor;
  44 struct xpress_item;
  45 struct xpress_mc_pos_data;
  46
  47 struct xpress_compressor_params {
  48
  49         /* Only used when choose_items_func == xpress_choose_items_near_optimal  */
  50         u32 num_optim_passes;
  51
  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.
  57          *
  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
  60          * matches.)  */
  61         u32 (*choose_items_func)(struct xpress_compressor *c);
  62
  63         /* Match-finding algorithm and parameters  */
  64         enum lz_mf_algo mf_algo;
  65         u32 max_search_depth;
  66         u32 nice_match_length;
  67 };
  68
  69 /* XPRESS compressor state.  */
  70 struct xpress_compressor {
  71
  72         /* Parameters determined based on the compression level.  */
  73         struct xpress_compressor_params params;
  74
  75         /* Lempel-Ziv match-finder  */
  76         struct lz_mf *mf;
  77
  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];
  90
  91         /* The selected sequence of matches/literals  */
  92         struct xpress_item *chosen_items;
  93
  94         /* Data currently being compressed  */
  95         const u8 *cur_window;
  96         u32 cur_window_size;
  97
  98         /* Symbol frequency counters  */
  99         u32 freqs[XPRESS_NUM_SYMBOLS];
 100
 101         /* The current Huffman code  */
 102         u32 codewords[XPRESS_NUM_SYMBOLS];
 103         u8 lens[XPRESS_NUM_SYMBOLS];
 104 };
 105
 106 /* Match-chooser position data.
 107  * See corresponding declaration in lzx-compress.c for more information.  */
 108 struct xpress_mc_pos_data {
 109         u32 cost;
 110 #define MC_INFINITE_COST ((u32)~0UL)
 111
 112         union {
 113                 struct {
 114                         u32 link;
 115                         u32 match_offset;
 116                 } prev;
 117                 struct {
 118                         u32 link;
 119                         u32 match_offset;
 120                 } next;
 121         };
 122 };
 123
 124 /* Intermediate XPRESS match/literal representation.  */
 125 struct xpress_item {
 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.  */
 129 };
 130
 131 /* Output an XPRESS match.  */
 132 static void
 133 xpress_write_match(struct xpress_item match, struct output_bitstream *ostream,
 134                    const u32 codewords[], const u8 lens[])
 135 {
 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);
 139
 140         /* Huffman symbol  */
 141         bitstream_put_bits(ostream, codewords[sym], lens[sym]);
 142
 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);
 148                 if (byte1 == 0xff) {
 149                         bitstream_put_byte(ostream, match.adjusted_len & 0xff);
 150                         bitstream_put_byte(ostream, match.adjusted_len >> 8);
 151                 }
 152         }
 153
 154         /* Offset bits  */
 155         bitstream_put_bits(ostream, match.offset ^ (1U << offset_bsr), offset_bsr);
 156 }
 157
 158 /* Output a sequence of XPRESS matches and literals.  */
 159 static void
 160 xpress_write_items(struct output_bitstream *ostream,
 161                    const struct xpress_item items[], u32 num_items,
 162                    const u32 codewords[], const u8 lens[])
 163 {
 164         for (u32 i = 0; i < num_items; i++) {
 165                 if (items[i].offset) {
 166                         /* Match  */
 167                         xpress_write_match(items[i], ostream, codewords, lens);
 168                 } else {
 169                         /* Literal  */
 170                         unsigned lit = items[i].adjusted_len;
 171                         bitstream_put_bits(ostream, codewords[lit], lens[lit]);
 172                 }
 173         }
 174         /* End-of-data symbol (required for MS compatibility)  */
 175         bitstream_put_bits(ostream, codewords[XPRESS_END_OF_DATA], lens[XPRESS_END_OF_DATA]);
 176 }
 177
 178 /* Make the Huffman code for XPRESS.
 179  *
 180  * Takes as input c->freqs and produces as output c->lens and c->codewords.  */
 181 static void
 182 xpress_make_huffman_code(struct xpress_compressor *c)
 183 {
 184         make_canonical_huffman_code(XPRESS_NUM_SYMBOLS, XPRESS_MAX_CODEWORD_LEN,
 185                                     c->freqs, c->lens, c->codewords);
 186 }
 187
 188 /* Account for the Huffman symbol that would be produced by outputting the
 189  * specified literal.  Returns the intermediate representation of the literal.
 190  */
 191 static inline struct xpress_item
 192 xpress_tally_literal(u8 lit, u32 freqs[])
 193 {
 194         freqs[lit]++;
 195         return (struct xpress_item) { .offset = 0, .adjusted_len = lit };
 196 }
 197
 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[])
 202 {
 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);
 206
 207         freqs[sym]++;
 208         return (struct xpress_item) { .offset = offset,
 209                                       .adjusted_len = adjusted_len };
 210 }
 211
 212 static unsigned
 213 xpress_get_matches_fillcache(struct xpress_compressor *c,
 214                              const struct lz_match **matches_ret)
 215 {
 216         struct lz_match *cache_ptr;
 217         struct lz_match *matches;
 218         unsigned num_matches;
 219
 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;
 226         } else {
 227                 num_matches = 0;
 228         }
 229         c->cur_window_ptr++;
 230         *matches_ret = matches;
 231         return num_matches;
 232 }
 233
 234 static unsigned
 235 xpress_get_matches_usecache(struct xpress_compressor *c,
 236                             const struct lz_match **matches_ret)
 237 {
 238         struct lz_match *cache_ptr;
 239         struct lz_match *matches;
 240         unsigned num_matches;
 241
 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;
 247         } else {
 248                 num_matches = 0;
 249         }
 250         c->cur_window_ptr++;
 251         *matches_ret = matches;
 252         return num_matches;
 253 }
 254
 255 static unsigned
 256 xpress_get_matches_usecache_nocheck(struct xpress_compressor *c,
 257                                     const struct lz_match **matches_ret)
 258 {
 259         struct lz_match *cache_ptr;
 260         struct lz_match *matches;
 261         unsigned num_matches;
 262
 263         cache_ptr = c->cache_ptr;
 264         matches = cache_ptr + 1;
 265         num_matches = cache_ptr->len;
 266         c->cache_ptr = matches + num_matches;
 267         c->cur_window_ptr++;
 268         *matches_ret = matches;
 269         return num_matches;
 270 }
 271
 272 static unsigned
 273 xpress_get_matches_noncaching(struct xpress_compressor *c,
 274                               const struct lz_match **matches_ret)
 275 {
 276         c->cur_window_ptr++;
 277         *matches_ret = c->cached_matches;
 278         return lz_mf_get_matches(c->mf, c->cached_matches);
 279 }
 280
 281 /*
 282  * Find matches at the next position in the window.
 283  *
 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
 286  * offset.
 287  */
 288 static inline unsigned
 289 xpress_get_matches(struct xpress_compressor *c,
 290                    const struct lz_match **matches_ret)
 291 {
 292         return (*c->get_matches_func)(c, matches_ret);
 293 }
 294
 295 static void
 296 xpress_skip_bytes_fillcache(struct xpress_compressor *c, u32 n)
 297 {
 298         struct lz_match *cache_ptr;
 299
 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)) {
 304                 do {
 305                         cache_ptr->len = 0;
 306                         cache_ptr += 1;
 307                 } while (--n && likely(cache_ptr <= c->cache_limit));
 308         }
 309         c->cache_ptr = cache_ptr;
 310 }
 311
 312 static void
 313 xpress_skip_bytes_usecache(struct xpress_compressor *c, u32 n)
 314 {
 315         struct lz_match *cache_ptr;
 316
 317         c->cur_window_ptr += n;
 318         cache_ptr = c->cache_ptr;
 319         if (likely(cache_ptr <= c->cache_limit)) {
 320                 do {
 321                         cache_ptr += 1 + cache_ptr->len;
 322                 } while (--n && likely(cache_ptr <= c->cache_limit));
 323         }
 324         c->cache_ptr = cache_ptr;
 325 }
 326
 327 static void
 328 xpress_skip_bytes_usecache_nocheck(struct xpress_compressor *c, u32 n)
 329 {
 330         struct lz_match *cache_ptr;
 331
 332         c->cur_window_ptr += n;
 333         cache_ptr = c->cache_ptr;
 334         do {
 335                 cache_ptr += 1 + cache_ptr->len;
 336         } while (--n);
 337         c->cache_ptr = cache_ptr;
 338 }
 339
 340 static void
 341 xpress_skip_bytes_noncaching(struct xpress_compressor *c, u32 n)
 342 {
 343         c->cur_window_ptr += n;
 344         lz_mf_skip_positions(c->mf, n);
 345 }
 346
 347 /*
 348  * Skip the specified number of positions in the window (don't search for
 349  * matches at them).
 350  */
 351 static inline void
 352 xpress_skip_bytes(struct xpress_compressor *c, u32 n)
 353 {
 354         return (*c->skip_bytes_func)(c, n);
 355 }
 356
 357 /*
 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).
 360  */
 361 static inline u32
 362 xpress_prev_literal_cost(const struct xpress_compressor *c)
 363 {
 364         return c->costs[*(c->cur_window_ptr - 1)];
 365 }
 366
 367 /*
 368  * Reverse the linked list of near-optimal matches so that they can be returned
 369  * in forwards order.
 370  *
 371  * Returns the first match in the list.
 372  */
 373 static struct lz_match
 374 xpress_match_chooser_reverse_list(struct xpress_compressor *c, unsigned cur_pos)
 375 {
 376         unsigned prev_link, saved_prev_link;
 377         u32 prev_match_offset, saved_prev_match_offset;
 378
 379         c->optimum_end_idx = cur_pos;
 380
 381         saved_prev_link = c->optimum[cur_pos].prev.link;
 382         saved_prev_match_offset = c->optimum[cur_pos].prev.match_offset;
 383
 384         do {
 385                 prev_link = saved_prev_link;
 386                 prev_match_offset = saved_prev_match_offset;
 387
 388                 saved_prev_link = c->optimum[prev_link].prev.link;
 389                 saved_prev_match_offset = c->optimum[prev_link].prev.match_offset;
 390
 391                 c->optimum[prev_link].next.link = cur_pos;
 392                 c->optimum[prev_link].next.match_offset = prev_match_offset;
 393
 394                 cur_pos = prev_link;
 395         } while (cur_pos != 0);
 396
 397         c->optimum_cur_idx = c->optimum[0].next.link;
 398
 399         return (struct lz_match)
 400                 { .len = c->optimum_cur_idx,
 401                   .offset = c->optimum[0].next.match_offset,
 402                 };
 403 }
 404
 405 /*
 406  * Near-optimal parsing.
 407  *
 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.
 414  */
 415 static struct lz_match
 416 xpress_choose_near_optimal_item(struct xpress_compressor *c)
 417 {
 418         const struct lz_match *matches;
 419         unsigned num_matches;
 420         struct lz_match match;
 421         unsigned cur_pos;
 422         unsigned end_pos;
 423         struct xpress_mc_pos_data * const optimum = c->optimum;
 424
 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 -
 428                                     c->optimum_cur_idx;
 429                 match.offset = optimum[c->optimum_cur_idx].next.match_offset;
 430
 431                 c->optimum_cur_idx = optimum[c->optimum_cur_idx].next.link;
 432                 return match;
 433         }
 434
 435         c->optimum_cur_idx = 0;
 436         c->optimum_end_idx = 0;
 437
 438         num_matches = xpress_get_matches(c, &matches);
 439
 440         if (num_matches == 0)
 441                 return (struct lz_match) {};
 442
 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];
 447         }
 448
 449         /* Consider coding a literal.  */
 450         optimum[1].cost = xpress_prev_literal_cost(c);
 451         optimum[1].prev.link = 0;
 452
 453         optimum[2].cost = MC_INFINITE_COST;
 454
 455         {
 456                 /* Consider coding a match.  Cost evaluation is hand-inlined so
 457                  * that we can do some performance hacks.  */
 458
 459                 unsigned i = 0;
 460                 unsigned len = 3;
 461                 struct xpress_mc_pos_data *optimum_ptr = &optimum[len];
 462
 463                 if (matches[num_matches - 1].len < 0xf + XPRESS_MIN_MATCH_LEN) {
 464                         do {
 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);
 470                                 do {
 471                                         optimum_ptr->prev.link = 0;
 472                                         optimum_ptr->prev.match_offset = offset;
 473                                         optimum_ptr->cost = offset_bsr + c->costs[sym];
 474                                         sym++;
 475                                         optimum_ptr++;
 476                                 } while (++len <= matches[i].len);
 477                         } while (++i != num_matches);
 478                 } else {
 479                         do {
 480                                 u32 offset = matches[i].offset;
 481                                 u32 offset_bsr = bsr32(offset);
 482                                 do {
 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) {
 489                                                 cost += 8;
 490                                                 if (adjusted_len - 0xf >= 0xff)
 491                                                         cost += 16;
 492                                         }
 493
 494                                         optimum_ptr->prev.link = 0;
 495                                         optimum_ptr->prev.match_offset = offset;
 496                                         optimum_ptr->cost = cost;
 497                                         optimum_ptr++;
 498                                 } while (++len <= matches[i].len);
 499                         } while (++i != num_matches);
 500                 }
 501         }
 502
 503         end_pos = matches[num_matches - 1].len;
 504         cur_pos = 1;
 505         do {
 506                 u32 cost;
 507                 u32 longest_len;
 508
 509                 num_matches = xpress_get_matches(c, &matches);
 510
 511                 if (num_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);
 516
 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;
 521
 522                                 xpress_skip_bytes(c, longest_len - 1);
 523
 524                                 return match;
 525                         }
 526                 } else {
 527                         longest_len = 1;
 528                 }
 529
 530                 while (end_pos < cur_pos + longest_len)
 531                         optimum[++end_pos].cost = MC_INFINITE_COST;
 532
 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;
 538                 }
 539
 540                 if (num_matches) {
 541                         /* Consider coding a match.  Cost evaluation is
 542                          * hand-inlined so that we can do some performance
 543                          * hacks.  */
 544                         unsigned i = 0;
 545                         unsigned len = 3;
 546                         struct xpress_mc_pos_data *optimum_ptr = &optimum[cur_pos + 3];
 547                         u32 cur_cost = optimum[cur_pos].cost;
 548
 549                         if (matches[num_matches - 1].len < 0xf + XPRESS_MIN_MATCH_LEN) {
 550                                 do {
 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);
 556
 557                                         u32 base_cost = cur_cost + offset_bsr;
 558                                         do {
 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;
 564                                                 }
 565                                                 sym++;
 566                                                 optimum_ptr++;
 567                                         } while (++len <= matches[i].len);
 568                                 } while (++i != num_matches);
 569                         } else {
 570                                 do {
 571                                         u32 offset = matches[i].offset;
 572                                         u32 offset_bsr = bsr32(offset);
 573
 574                                         u32 base_cost = cur_cost + offset_bsr;
 575                                         do {
 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);
 580
 581                                                 cost = base_cost + c->costs[sym];
 582                                                 if (adjusted_len >= 0xf) {
 583                                                         cost += 8;
 584                                                         if (adjusted_len - 0xf >= 0xff)
 585                                                                 cost += 16;
 586                                                 }
 587
 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;
 592                                                 }
 593                                                 optimum_ptr++;
 594                                         } while (++len <= matches[i].len);
 595                                 } while (++i != num_matches);
 596                         }
 597                 }
 598
 599                 cur_pos++;
 600
 601         } while (cur_pos != end_pos && cur_pos != XPRESS_OPTIM_ARRAY_LENGTH);
 602
 603         return xpress_match_chooser_reverse_list(c, cur_pos);
 604 }
 605
 606 /* Set default XPRESS Huffman symbol costs to kick-start the iterative
 607  * optimization algorithm.  */
 608 static void
 609 xpress_set_default_costs(u8 costs[])
 610 {
 611         unsigned i;
 612
 613         for (i = 0; i < XPRESS_NUM_CHARS; i++)
 614                 costs[i] = 8;
 615
 616         for (; i < XPRESS_NUM_SYMBOLS; i++)
 617                 costs[i] = 10;
 618 }
 619
 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)
 622  * codeword.  */
 623 static void
 624 xpress_set_costs(u8 costs[], const u8 lens[])
 625 {
 626         for (unsigned i = 0; i < XPRESS_NUM_SYMBOLS; i++)
 627                 costs[i] = lens[i] ? lens[i] : XPRESS_MAX_CODEWORD_LEN;
 628 }
 629
 630 /* Near-optimal parsing  */
 631 static u32
 632 xpress_choose_items_near_optimal(struct xpress_compressor *c)
 633 {
 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;
 640
 641         xpress_set_default_costs(c->costs);
 642         c->optimum_cur_idx = 0;
 643         c->optimum_end_idx = 0;
 644
 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;
 648         } else {
 649                 c->get_matches_func = xpress_get_matches_noncaching;
 650                 c->skip_bytes_func = xpress_skip_bytes_noncaching;
 651         }
 652
 653         lz_mf_load_window(c->mf, c->cur_window, c->cur_window_size);
 654
 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));
 661
 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;
 668                         } else {
 669                                 xpress_tally_literal(*window_ptr, c->freqs);
 670                                 window_ptr += 1;
 671                         }
 672                 }
 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;
 679                 } else {
 680                         c->get_matches_func = xpress_get_matches_usecache;
 681                         c->skip_bytes_func = xpress_skip_bytes_usecache;
 682                 }
 683         }
 684
 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;
 691
 692         u32 unseen_cost = 9;
 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,
 697                                                          raw_item.offset,
 698                                                          c->freqs);
 699                         window_ptr += raw_item.len;
 700                 } else {
 701                         xpress_item = xpress_tally_literal(*window_ptr,
 702                                                            c->freqs);
 703                         window_ptr += 1;
 704                 }
 705                 *next_chosen_item++ = xpress_item;
 706
 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)
 712                 {
 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)
 717                                 unseen_cost++;
 718                 }
 719         }
 720         c->freqs[XPRESS_END_OF_DATA]++;
 721         xpress_make_huffman_code(c);
 722         return next_chosen_item - c->chosen_items;
 723 }
 724
 725 /* Lazy parsing  */
 726 static u32
 727 xpress_choose_items_lazy(struct xpress_compressor *c)
 728 {
 729         struct lz_mf *mf;
 730         u32 len_3_too_far;
 731         const u8 *window_ptr;
 732         const u8 *window_end;
 733         u32 num_matches;
 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;
 737
 738         mf = c->mf;
 739
 740         lz_mf_load_window(mf, c->cur_window, c->cur_window_size);
 741
 742         if (c->cur_window_size <= 8192)
 743                 len_3_too_far = 2048;
 744         else
 745                 len_3_too_far = 4096;
 746
 747         memset(c->freqs, 0, sizeof(c->freqs));
 748
 749         window_ptr = c->cur_window;
 750         window_end = c->cur_window + c->cur_window_size;
 751         next_chosen_item = c->chosen_items;
 752
 753         for (;;) {
 754
 755                 /* Don't have match at previous position  */
 756
 757                 num_matches = lz_mf_get_matches(mf, matches);
 758                 window_ptr++;
 759
 760                 if (num_matches == 0 ||
 761                     (matches[num_matches - 1].len == 3 &&
 762                      matches[num_matches - 1].offset >= len_3_too_far))
 763                 {
 764                         /* No matches found => output literal  */
 765                         *next_chosen_item++ = xpress_tally_literal(*(window_ptr - 1),
 766                                                                    c->freqs);
 767                         if (window_ptr == window_end)
 768                                 break;
 769                         continue;
 770                 }
 771
 772                 prev_match = matches[num_matches - 1];
 773
 774         have_prev_match:
 775                 /* Have match at previous position  */
 776
 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,
 780                                                                  prev_match.offset,
 781                                                                  c->freqs);
 782                         lz_mf_skip_positions(mf, prev_match.len - 1);
 783                         window_ptr += prev_match.len - 1;
 784                         if (window_ptr == window_end)
 785                                 break;
 786                         continue;
 787                 }
 788
 789                 num_matches = lz_mf_get_matches(mf, matches);
 790                 window_ptr++;
 791
 792                 if (num_matches == 0 ||
 793                     (matches[num_matches - 1].len <= prev_match.len))
 794                 {
 795                         /* Next match is not longer => output previous match  */
 796                         *next_chosen_item++ = xpress_tally_match(prev_match.len,
 797                                                                  prev_match.offset,
 798                                                                  c->freqs);
 799                         lz_mf_skip_positions(mf, prev_match.len - 2);
 800                         window_ptr += prev_match.len - 2;
 801                         if (window_ptr == window_end)
 802                                 break;
 803                         continue;
 804                 }
 805
 806                 /* Next match is longer => output literal  */
 807
 808                 *next_chosen_item++ = xpress_tally_literal(*(window_ptr - 2),
 809                                                            c->freqs);
 810
 811                 prev_match = matches[num_matches - 1];
 812
 813                 goto have_prev_match;
 814         }
 815
 816         c->freqs[XPRESS_END_OF_DATA]++;
 817         xpress_make_huffman_code(c);
 818         return next_chosen_item - c->chosen_items;
 819 }
 820
 821 /* Greedy parsing  */
 822 static u32
 823 xpress_choose_items_greedy(struct xpress_compressor *c)
 824 {
 825         struct lz_mf *mf;
 826         u32 len_3_too_far;
 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)];
 830         u32 num_matches;
 831         struct xpress_item *next_chosen_item;
 832
 833         mf = c->mf;
 834
 835         lz_mf_load_window(mf, c->cur_window, c->cur_window_size);
 836
 837         if (c->cur_window_size <= 8192)
 838                 len_3_too_far = 2048;
 839         else
 840                 len_3_too_far = 4096;
 841
 842         memset(c->freqs, 0, sizeof(c->freqs));
 843
 844         window_ptr = c->cur_window;
 845         window_end = c->cur_window + c->cur_window_size;
 846         next_chosen_item = c->chosen_items;
 847
 848         do {
 849                 /* Get longest match at the current position.  */
 850                 num_matches = lz_mf_get_matches(mf, matches);
 851
 852                 if (num_matches == 0 ||
 853                     (matches[num_matches - 1].len == 3 &&
 854                      matches[num_matches - 1].offset >= len_3_too_far))
 855                 {
 856                         *next_chosen_item++ = xpress_tally_literal(*window_ptr, c->freqs);
 857                         window_ptr += 1;
 858                 } else {
 859                         u32 len = matches[num_matches - 1].len;
 860                         u32 offset = matches[num_matches - 1].offset;
 861
 862                         *next_chosen_item++ = xpress_tally_match(len, offset, c->freqs);
 863                         lz_mf_skip_positions(mf, len - 1);
 864                         window_ptr += len;
 865                 }
 866         } while (window_ptr != window_end);
 867
 868         c->freqs[XPRESS_END_OF_DATA]++;
 869         xpress_make_huffman_code(c);
 870         return next_chosen_item - c->chosen_items;
 871 }
 872
 873 /* Huffman-only parsing  */
 874 static u32
 875 xpress_choose_items_huffonly(struct xpress_compressor *c)
 876 {
 877         const u8 *window_ptr;
 878         const u8 *window_end;
 879         struct xpress_item *next_chosen_item;
 880
 881         memset(c->freqs, 0, sizeof(c->freqs));
 882
 883         window_ptr = c->cur_window;
 884         window_end = c->cur_window + c->cur_window_size;
 885         next_chosen_item = c->chosen_items;
 886
 887         do {
 888                 *next_chosen_item++ = xpress_tally_literal(*window_ptr++, c->freqs);
 889         } while (window_ptr != window_end);
 890
 891         c->freqs[XPRESS_END_OF_DATA]++;
 892         xpress_make_huffman_code(c);
 893         return next_chosen_item - c->chosen_items;
 894 }
 895
 896 /* Given the specified compression level and maximum window size, build the
 897  * parameters to use for XPRESS compression.  */
 898 static void
 899 xpress_build_params(unsigned int compression_level, u32 max_window_size,
 900                     struct xpress_compressor_params *xpress_params)
 901 {
 902         memset(xpress_params, 0, sizeof(*xpress_params));
 903
 904         if (compression_level == 1) {
 905
 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;
 909
 910         } else if (compression_level < 30) {
 911
 912                 /* Greedy parsing  */
 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;
 917
 918         } else if (compression_level < 60) {
 919
 920                 /* Lazy parsing  */
 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;
 925
 926         } else {
 927
 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;
 932                 else
 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);
 939         }
 940 }
 941
 942 /* Given the specified XPRESS parameters and maximum window size, build the
 943  * parameters to use for match-finding.  */
 944 static void
 945 xpress_build_mf_params(const struct xpress_compressor_params *xpress_params,
 946                        u32 max_window_size, struct lz_mf_params *mf_params)
 947 {
 948         memset(mf_params, 0, sizeof(*mf_params));
 949
 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;
 956 }
 957
 958 static inline bool
 959 xpress_window_size_valid(size_t window_size)
 960 {
 961         return (window_size > 0 && window_size <= XPRESS_MAX_OFFSET + 1);
 962 }
 963
 964 static void
 965 xpress_free_compressor(void *_c);
 966
 967 static u64
 968 xpress_get_needed_memory(size_t max_window_size, unsigned int compression_level)
 969 {
 970         u64 size = 0;
 971         struct xpress_compressor_params params;
 972
 973         if (!xpress_window_size_valid(max_window_size))
 974                 return 0;
 975
 976         xpress_build_params(compression_level, max_window_size, &params);
 977
 978         size += sizeof(struct xpress_compressor);
 979
 980         size += lz_mf_get_needed_memory(params.mf_algo, max_window_size);
 981
 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);
 989                 } else {
 990                         size += params.max_search_depth * sizeof(struct lz_match);
 991                 }
 992         }
 993
 994         size += max_window_size * sizeof(struct xpress_item);
 995
 996         return size;
 997 }
 998
 999 static int
1000 xpress_create_compressor(size_t max_window_size, unsigned int compression_level,
1001                          void **c_ret)
1002 {
1003         struct xpress_compressor *c;
1004         struct xpress_compressor_params params;
1005         struct lz_mf_params mf_params;
1006
1007         if (!xpress_window_size_valid(max_window_size))
1008                 return WIMLIB_ERR_INVALID_PARAM;
1009
1010         xpress_build_params(compression_level, max_window_size, &params);
1011         xpress_build_mf_params(&params, max_window_size, &mf_params);
1012
1013         c = CALLOC(1, sizeof(struct xpress_compressor));
1014         if (!c)
1015                 goto oom;
1016
1017         c->params = params;
1018
1019         c->mf = lz_mf_alloc(&mf_params);
1020         if (!c->mf)
1021                 goto oom;
1022
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));
1027                 if (!c->optimum)
1028                         goto oom;
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)
1034                                 goto oom;
1035                         c->cache_limit = c->cached_matches + cache_len -
1036                                            (params.max_search_depth + 1);
1037                 } else {
1038                         c->cached_matches = MALLOC(params.max_search_depth *
1039                                                    sizeof(struct lz_match));
1040                         if (!c->cached_matches)
1041                                 goto oom;
1042                 }
1043         }
1044
1045         c->chosen_items = MALLOC(max_window_size * sizeof(struct xpress_item));
1046         if (!c->chosen_items)
1047                 goto oom;
1048
1049         *c_ret = c;
1050         return 0;
1051
1052 oom:
1053         xpress_free_compressor(c);
1054         return WIMLIB_ERR_NOMEM;
1055 }
1056
1057 static size_t
1058 xpress_compress(const void *uncompressed_data, size_t uncompressed_size,
1059                 void *compressed_data, size_t compressed_size_avail, void *_c)
1060 {
1061         struct xpress_compressor *c = _c;
1062         u32 num_chosen_items;
1063         u8 *cptr;
1064         struct output_bitstream ostream;
1065         u32 compressed_size;
1066
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
1069          * input size.
1070          *
1071          * +1 to take into account that the buffer for compressed data is 1 byte
1072          * smaller than the buffer for uncompressed data.
1073          *
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)
1077                 return 0;
1078
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);
1083
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);
1088
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);
1094
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)
1098                 return 0;
1099
1100         /* Return the length of the compressed data.  */
1101         return compressed_size + XPRESS_NUM_SYMBOLS / 2;
1102 }
1103
1104 static void
1105 xpress_free_compressor(void *_c)
1106 {
1107         struct xpress_compressor *c = _c;
1108
1109         if (c) {
1110                 lz_mf_free(c->mf);
1111                 FREE(c->cached_matches);
1112                 FREE(c->optimum);
1113                 FREE(c->chosen_items);
1114                 FREE(c);
1115         }
1116 }
1117
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,
1123 };