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         struct lz_match (*choose_item_func)(struct xpress_compressor *);
  49         u32 num_optim_passes;
  50         enum lz_mf_algo mf_algo;
  51         u32 nice_match_length;
  52         u32 max_search_depth;
  53 };
  54
  55 /* XPRESS compressor state.  */
  56 struct xpress_compressor {
  57
  58         /* Parameters determined based on the compression level.  */
  59         struct xpress_compressor_params params;
  60
  61         unsigned (*get_matches_func)(struct xpress_compressor *,
  62                                      const struct lz_match **);
  63         void (*skip_bytes_func)(struct xpress_compressor *, u32 n);
  64         u32 len_3_too_far;
  65
  66         /* Data currently being compressed  */
  67         const u8 *cur_window;
  68         u32 cur_window_size;
  69
  70         /* Lempel-Ziv match-finder  */
  71         struct lz_mf *mf;
  72
  73         const u8 *cur_window_ptr;
  74
  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;
  79
  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];
  85
  86         /* Lazy parsing data  */
  87         struct lz_match prev_match;
  88
  89         /* The selected sequence of matches/literals  */
  90         struct xpress_item *chosen_items;
  91
  92         /* Symbol frequency counters  */
  93         u32 freqs[XPRESS_NUM_SYMBOLS];
  94
  95         /* The current Huffman code  */
  96         u32 codewords[XPRESS_NUM_SYMBOLS];
  97         u8 lens[XPRESS_NUM_SYMBOLS];
  98 };
  99
 100 /* Match-chooser position data.
 101  * See corresponding declaration in lzx-compress.c for more information.  */
 102 struct xpress_mc_pos_data {
 103         u32 cost;
 104 #define MC_INFINITE_COST ((u32)~0UL)
 105
 106         union {
 107                 struct {
 108                         u32 link;
 109                         u32 match_offset;
 110                 } prev;
 111                 struct {
 112                         u32 link;
 113                         u32 match_offset;
 114                 } next;
 115         };
 116 };
 117
 118 /* Intermediate XPRESS match/literal representation.  */
 119 struct xpress_item {
 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.  */
 123 };
 124
 125 /* Output an XPRESS match.  */
 126 static void
 127 xpress_write_match(struct xpress_item match, struct output_bitstream *ostream,
 128                    const u32 codewords[], const u8 lens[])
 129 {
 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);
 133
 134         /* Huffman symbol  */
 135         bitstream_put_bits(ostream, codewords[sym], lens[sym]);
 136
 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);
 142                 if (byte1 == 0xff) {
 143                         bitstream_put_byte(ostream, match.adjusted_len & 0xff);
 144                         bitstream_put_byte(ostream, match.adjusted_len >> 8);
 145                 }
 146         }
 147
 148         /* Offset bits  */
 149         bitstream_put_bits(ostream, match.offset ^ (1U << offset_bsr), offset_bsr);
 150 }
 151
 152 /* Output a sequence of XPRESS matches and literals.  */
 153 static void
 154 xpress_write_items(struct output_bitstream *ostream,
 155                    const struct xpress_item items[], u32 num_items,
 156                    const u32 codewords[], const u8 lens[])
 157 {
 158         for (u32 i = 0; i < num_items; i++) {
 159                 if (items[i].offset) {
 160                         /* Match  */
 161                         xpress_write_match(items[i], ostream, codewords, lens);
 162                 } else {
 163                         /* Literal  */
 164                         unsigned lit = items[i].adjusted_len;
 165                         bitstream_put_bits(ostream, codewords[lit], lens[lit]);
 166                 }
 167         }
 168         /* End-of-data symbol (required for MS compatibility)  */
 169         bitstream_put_bits(ostream, codewords[XPRESS_END_OF_DATA], lens[XPRESS_END_OF_DATA]);
 170 }
 171
 172 /* Make the Huffman code for XPRESS.
 173  *
 174  * Takes as input c->freqs and produces as output c->lens and c->codewords.  */
 175 static void
 176 xpress_make_huffman_code(struct xpress_compressor *c)
 177 {
 178         make_canonical_huffman_code(XPRESS_NUM_SYMBOLS, XPRESS_MAX_CODEWORD_LEN,
 179                                     c->freqs, c->lens, c->codewords);
 180 }
 181
 182 /* Account for the Huffman symbol that would be produced by outputting the
 183  * specified literal.  Returns the intermediate representation of the literal.
 184  */
 185 static inline struct xpress_item
 186 xpress_tally_literal(u8 lit, u32 freqs[])
 187 {
 188         freqs[lit]++;
 189         return (struct xpress_item) { .offset = 0, .adjusted_len = lit };
 190 }
 191
 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[])
 196 {
 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);
 200
 201         freqs[sym]++;
 202         return (struct xpress_item) { .offset = offset,
 203                                       .adjusted_len = adjusted_len };
 204 }
 205
 206 static unsigned
 207 xpress_get_matches_fillcache(struct xpress_compressor *c,
 208                              const struct lz_match **matches_ret)
 209 {
 210         struct lz_match *cache_ptr;
 211         struct lz_match *matches;
 212         unsigned num_matches;
 213
 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;
 220         } else {
 221                 num_matches = 0;
 222         }
 223         c->cur_window_ptr++;
 224         *matches_ret = matches;
 225         return num_matches;
 226 }
 227
 228 static unsigned
 229 xpress_get_matches_usecache(struct xpress_compressor *c,
 230                             const struct lz_match **matches_ret)
 231 {
 232         struct lz_match *cache_ptr;
 233         struct lz_match *matches;
 234         unsigned num_matches;
 235
 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;
 241         } else {
 242                 num_matches = 0;
 243         }
 244         c->cur_window_ptr++;
 245         *matches_ret = matches;
 246         return num_matches;
 247 }
 248
 249 static unsigned
 250 xpress_get_matches_usecache_nocheck(struct xpress_compressor *c,
 251                                     const struct lz_match **matches_ret)
 252 {
 253         struct lz_match *cache_ptr;
 254         struct lz_match *matches;
 255         unsigned num_matches;
 256
 257         cache_ptr = c->cache_ptr;
 258         matches = cache_ptr + 1;
 259         num_matches = cache_ptr->len;
 260         c->cache_ptr = matches + num_matches;
 261         c->cur_window_ptr++;
 262         *matches_ret = matches;
 263         return num_matches;
 264 }
 265
 266 static unsigned
 267 xpress_get_matches_noncaching(struct xpress_compressor *c,
 268                               const struct lz_match **matches_ret)
 269 {
 270         c->cur_window_ptr++;
 271         *matches_ret = c->cached_matches;
 272         return lz_mf_get_matches(c->mf, c->cached_matches);
 273 }
 274
 275 /*
 276  * Find matches at the next position in the window.
 277  *
 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
 280  * offset.
 281  */
 282 static inline unsigned
 283 xpress_get_matches(struct xpress_compressor *c,
 284                    const struct lz_match **matches_ret)
 285 {
 286         return (*c->get_matches_func)(c, matches_ret);
 287 }
 288
 289 static void
 290 xpress_skip_bytes_fillcache(struct xpress_compressor *c, u32 n)
 291 {
 292         struct lz_match *cache_ptr;
 293
 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)) {
 298                 do {
 299                         cache_ptr->len = 0;
 300                         cache_ptr += 1;
 301                 } while (--n && likely(cache_ptr <= c->cache_limit));
 302         }
 303         c->cache_ptr = cache_ptr;
 304 }
 305
 306 static void
 307 xpress_skip_bytes_usecache(struct xpress_compressor *c, u32 n)
 308 {
 309         struct lz_match *cache_ptr;
 310
 311         c->cur_window_ptr += n;
 312         cache_ptr = c->cache_ptr;
 313         if (likely(cache_ptr <= c->cache_limit)) {
 314                 do {
 315                         cache_ptr += 1 + cache_ptr->len;
 316                 } while (--n && likely(cache_ptr <= c->cache_limit));
 317         }
 318         c->cache_ptr = cache_ptr;
 319 }
 320
 321 static void
 322 xpress_skip_bytes_usecache_nocheck(struct xpress_compressor *c, u32 n)
 323 {
 324         struct lz_match *cache_ptr;
 325
 326         c->cur_window_ptr += n;
 327         cache_ptr = c->cache_ptr;
 328         do {
 329                 cache_ptr += 1 + cache_ptr->len;
 330         } while (--n);
 331         c->cache_ptr = cache_ptr;
 332 }
 333
 334 static void
 335 xpress_skip_bytes_noncaching(struct xpress_compressor *c, u32 n)
 336 {
 337         c->cur_window_ptr += n;
 338         lz_mf_skip_positions(c->mf, n);
 339 }
 340
 341 /*
 342  * Skip the specified number of positions in the window (don't search for
 343  * matches at them).
 344  */
 345 static inline void
 346 xpress_skip_bytes(struct xpress_compressor *c, u32 n)
 347 {
 348         return (*c->skip_bytes_func)(c, n);
 349 }
 350
 351 /*
 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).
 354  */
 355 static inline u32
 356 xpress_prev_literal_cost(const struct xpress_compressor *c)
 357 {
 358         return c->costs[*(c->cur_window_ptr - 1)];
 359 }
 360
 361 /*
 362  * Reverse the linked list of near-optimal matches so that they can be returned
 363  * in forwards order.
 364  *
 365  * Returns the first match in the list.
 366  */
 367 static struct lz_match
 368 xpress_match_chooser_reverse_list(struct xpress_compressor *c, unsigned cur_pos)
 369 {
 370         unsigned prev_link, saved_prev_link;
 371         u32 prev_match_offset, saved_prev_match_offset;
 372
 373         c->optimum_end_idx = cur_pos;
 374
 375         saved_prev_link = c->optimum[cur_pos].prev.link;
 376         saved_prev_match_offset = c->optimum[cur_pos].prev.match_offset;
 377
 378         do {
 379                 prev_link = saved_prev_link;
 380                 prev_match_offset = saved_prev_match_offset;
 381
 382                 saved_prev_link = c->optimum[prev_link].prev.link;
 383                 saved_prev_match_offset = c->optimum[prev_link].prev.match_offset;
 384
 385                 c->optimum[prev_link].next.link = cur_pos;
 386                 c->optimum[prev_link].next.match_offset = prev_match_offset;
 387
 388                 cur_pos = prev_link;
 389         } while (cur_pos != 0);
 390
 391         c->optimum_cur_idx = c->optimum[0].next.link;
 392
 393         return (struct lz_match)
 394                 { .len = c->optimum_cur_idx,
 395                   .offset = c->optimum[0].next.match_offset,
 396                 };
 397 }
 398
 399 /*
 400  * Near-optimal parsing.
 401  *
 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.
 408  */
 409 static struct lz_match
 410 xpress_choose_near_optimal_item(struct xpress_compressor *c)
 411 {
 412         const struct lz_match *matches;
 413         unsigned num_matches;
 414         struct lz_match match;
 415         unsigned cur_pos;
 416         unsigned end_pos;
 417         struct xpress_mc_pos_data * const optimum = c->optimum;
 418
 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 -
 422                                     c->optimum_cur_idx;
 423                 match.offset = optimum[c->optimum_cur_idx].next.match_offset;
 424
 425                 c->optimum_cur_idx = optimum[c->optimum_cur_idx].next.link;
 426                 return match;
 427         }
 428
 429         c->optimum_cur_idx = 0;
 430         c->optimum_end_idx = 0;
 431
 432         num_matches = xpress_get_matches(c, &matches);
 433
 434         if (num_matches == 0)
 435                 return (struct lz_match) {};
 436
 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];
 441         }
 442
 443         /* Consider coding a literal.  */
 444         optimum[1].cost = xpress_prev_literal_cost(c);
 445         optimum[1].prev.link = 0;
 446
 447         optimum[2].cost = MC_INFINITE_COST;
 448
 449         {
 450                 /* Consider coding a match.  Cost evaluation is hand-inlined so
 451                  * that we can do some performance hacks.  */
 452
 453                 unsigned i = 0;
 454                 unsigned len = 3;
 455                 struct xpress_mc_pos_data *optimum_ptr = &optimum[len];
 456
 457                 if (matches[num_matches - 1].len < 0xf + XPRESS_MIN_MATCH_LEN) {
 458                         do {
 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);
 464                                 do {
 465                                         optimum_ptr->prev.link = 0;
 466                                         optimum_ptr->prev.match_offset = offset;
 467                                         optimum_ptr->cost = offset_bsr + c->costs[sym];
 468                                         sym++;
 469                                         optimum_ptr++;
 470                                 } while (++len <= matches[i].len);
 471                         } while (++i != num_matches);
 472                 } else {
 473                         do {
 474                                 u32 offset = matches[i].offset;
 475                                 u32 offset_bsr = bsr32(offset);
 476                                 do {
 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) {
 483                                                 cost += 8;
 484                                                 if (adjusted_len - 0xf >= 0xff)
 485                                                         cost += 16;
 486                                         }
 487
 488                                         optimum_ptr->prev.link = 0;
 489                                         optimum_ptr->prev.match_offset = offset;
 490                                         optimum_ptr->cost = cost;
 491                                         optimum_ptr++;
 492                                 } while (++len <= matches[i].len);
 493                         } while (++i != num_matches);
 494                 }
 495         }
 496
 497         end_pos = matches[num_matches - 1].len;
 498         cur_pos = 1;
 499         do {
 500                 u32 cost;
 501                 u32 longest_len;
 502
 503                 num_matches = xpress_get_matches(c, &matches);
 504
 505                 if (num_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);
 510
 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;
 515
 516                                 xpress_skip_bytes(c, longest_len - 1);
 517
 518                                 return match;
 519                         }
 520                 } else {
 521                         longest_len = 1;
 522                 }
 523
 524                 while (end_pos < cur_pos + longest_len)
 525                         optimum[++end_pos].cost = MC_INFINITE_COST;
 526
 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;
 532                 }
 533
 534                 if (num_matches) {
 535                         /* Consider coding a match.  Cost evaluation is
 536                          * hand-inlined so that we can do some performance
 537                          * hacks.  */
 538                         unsigned i = 0;
 539                         unsigned len = 3;
 540                         struct xpress_mc_pos_data *optimum_ptr = &optimum[cur_pos + 3];
 541                         u32 cur_cost = optimum[cur_pos].cost;
 542
 543                         if (matches[num_matches - 1].len < 0xf + XPRESS_MIN_MATCH_LEN) {
 544                                 do {
 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);
 550
 551                                         u32 base_cost = cur_cost + offset_bsr;
 552                                         do {
 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;
 558                                                 }
 559                                                 sym++;
 560                                                 optimum_ptr++;
 561                                         } while (++len <= matches[i].len);
 562                                 } while (++i != num_matches);
 563                         } else {
 564                                 do {
 565                                         u32 offset = matches[i].offset;
 566                                         u32 offset_bsr = bsr32(offset);
 567
 568                                         u32 base_cost = cur_cost + offset_bsr;
 569                                         do {
 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);
 574
 575                                                 cost = base_cost + c->costs[sym];
 576                                                 if (adjusted_len >= 0xf) {
 577                                                         cost += 8;
 578                                                         if (adjusted_len - 0xf >= 0xff)
 579                                                                 cost += 16;
 580                                                 }
 581
 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;
 586                                                 }
 587                                                 optimum_ptr++;
 588                                         } while (++len <= matches[i].len);
 589                                 } while (++i != num_matches);
 590                         }
 591                 }
 592
 593                 cur_pos++;
 594
 595         } while (cur_pos != end_pos && cur_pos != XPRESS_OPTIM_ARRAY_LENGTH);
 596
 597         return xpress_match_chooser_reverse_list(c, cur_pos);
 598 }
 599
 600 /* Lazy parsing.  */
 601 static struct lz_match
 602 xpress_choose_lazy_item(struct xpress_compressor *c)
 603 {
 604         const struct lz_match *matches;
 605         struct lz_match cur_match;
 606         struct lz_match next_match;
 607         u32 num_matches;
 608
 609         if (c->prev_match.len) {
 610                 cur_match = c->prev_match;
 611                 c->prev_match.len = 0;
 612         } else {
 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))
 617                 {
 618                         cur_match.len = 0;
 619                         return cur_match;
 620                 }
 621
 622                 /* With lazy parsing we only consider the longest match at each
 623                  * position.  */
 624                 cur_match = matches[num_matches - 1];
 625         }
 626
 627         if (cur_match.len >= c->params.nice_match_length) {
 628                 xpress_skip_bytes(c, cur_match.len - 1);
 629                 return cur_match;
 630         }
 631
 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))
 636         {
 637                 xpress_skip_bytes(c, cur_match.len - 2);
 638                 return cur_match;
 639         }
 640
 641         next_match = matches[num_matches - 1];
 642
 643         if (next_match.len <= cur_match.len) {
 644                 xpress_skip_bytes(c, cur_match.len - 2);
 645                 return cur_match;
 646         } else {
 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;
 650                 cur_match.len = 0;
 651                 return cur_match;
 652         }
 653 }
 654
 655 /* Greedy parsing.  */
 656 static struct lz_match
 657 xpress_choose_greedy_item(struct xpress_compressor *c)
 658 {
 659         const struct lz_match *matches;
 660         u32 num_matches;
 661
 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) {};
 667
 668         xpress_skip_bytes(c, matches[num_matches - 1].len - 1);
 669         return matches[num_matches - 1];
 670 }
 671
 672 /* Always choose a literal.  */
 673 static struct lz_match
 674 xpress_choose_literal(struct xpress_compressor *c)
 675 {
 676         return (struct lz_match) {};
 677 }
 678
 679 /*
 680  * Return the next match or literal to use, delegating to the currently selected
 681  * match-choosing algorithm.
 682  *
 683  * If the length of the returned 'struct lz_match' is less than
 684  * XPRESS_MIN_MATCH_LEN, then it is really a literal.
 685  */
 686 static inline struct lz_match
 687 xpress_choose_item(struct xpress_compressor *c)
 688 {
 689         return (*c->params.choose_item_func)(c);
 690 }
 691
 692 /* Set default XPRESS Huffman symbol costs to kick-start the iterative
 693  * optimization algorithm.  */
 694 static void
 695 xpress_set_default_costs(u8 costs[])
 696 {
 697         unsigned i;
 698
 699         for (i = 0; i < XPRESS_NUM_CHARS; i++)
 700                 costs[i] = 8;
 701
 702         for (; i < XPRESS_NUM_SYMBOLS; i++)
 703                 costs[i] = 10;
 704 }
 705
 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)
 708  * codeword.  */
 709 static void
 710 xpress_set_costs(u8 costs[], const u8 lens[])
 711 {
 712         for (unsigned i = 0; i < XPRESS_NUM_SYMBOLS; i++)
 713                 costs[i] = lens[i] ? lens[i] : XPRESS_MAX_CODEWORD_LEN;
 714 }
 715
 716 /*
 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.
 721  *
 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.)
 724  */
 725 static u32
 726 xpress_choose_items(struct xpress_compressor *c)
 727 {
 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;
 734
 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;
 739         } else {
 740                 c->prev_match.len = 0;
 741                 if (c->cur_window_size <= 8192)
 742                         c->len_3_too_far = 2048;
 743                 else
 744                         c->len_3_too_far = 4096;
 745         }
 746
 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;
 750         } else {
 751                 c->get_matches_func = xpress_get_matches_noncaching;
 752                 c->skip_bytes_func = xpress_skip_bytes_noncaching;
 753         }
 754
 755         lz_mf_load_window(c->mf, c->cur_window, c->cur_window_size);
 756
 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));
 762
 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;
 769                         } else {
 770                                 xpress_tally_literal(*window_ptr, c->freqs);
 771                                 window_ptr += 1;
 772                         }
 773                 }
 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;
 780                 } else {
 781                         c->get_matches_func = xpress_get_matches_usecache;
 782                         c->skip_bytes_func = xpress_skip_bytes_usecache;
 783                 }
 784         }
 785
 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;
 791
 792         u32 unseen_cost = 9;
 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,
 797                                                          raw_item.offset,
 798                                                          c->freqs);
 799                         window_ptr += raw_item.len;
 800                 } else {
 801                         xpress_item = xpress_tally_literal(*window_ptr,
 802                                                            c->freqs);
 803                         window_ptr += 1;
 804                 }
 805                 *next_chosen_item++ = xpress_item;
 806
 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)
 813                 {
 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)
 818                                 unseen_cost++;
 819                 }
 820         }
 821         c->freqs[XPRESS_END_OF_DATA]++;
 822         xpress_make_huffman_code(c);
 823         return next_chosen_item - c->chosen_items;
 824 }
 825
 826 /* Given the specified compression level and maximum window size, build the
 827  * parameters to use for XPRESS compression.  */
 828 static void
 829 xpress_build_params(unsigned int compression_level, u32 max_window_size,
 830                     struct xpress_compressor_params *xpress_params)
 831 {
 832         memset(xpress_params, 0, sizeof(*xpress_params));
 833
 834         if (compression_level == 1) {
 835
 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;
 840
 841         } else if (compression_level < 30) {
 842
 843                 /* Greedy parsing  */
 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;
 849
 850         } else if (compression_level < 60) {
 851
 852                 /* Lazy parsing  */
 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;
 858
 859         } else {
 860
 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;
 865                 else
 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);
 872         }
 873 }
 874
 875 /* Given the specified XPRESS parameters and maximum window size, build the
 876  * parameters to use for match-finding.  */
 877 static void
 878 xpress_build_mf_params(const struct xpress_compressor_params *xpress_params,
 879                        u32 max_window_size, struct lz_mf_params *mf_params)
 880 {
 881         memset(mf_params, 0, sizeof(*mf_params));
 882
 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;
 889 }
 890
 891 static inline bool
 892 xpress_window_size_valid(size_t window_size)
 893 {
 894         return (window_size > 0 && window_size <= XPRESS_MAX_OFFSET + 1);
 895 }
 896
 897 static void
 898 xpress_free_compressor(void *_c);
 899
 900 static u64
 901 xpress_get_needed_memory(size_t max_window_size, unsigned int compression_level)
 902 {
 903         u64 size = 0;
 904         struct xpress_compressor_params params;
 905
 906         if (!xpress_window_size_valid(max_window_size))
 907                 return 0;
 908
 909         xpress_build_params(compression_level, max_window_size, &params);
 910
 911         size += sizeof(struct xpress_compressor);
 912
 913         size += lz_mf_get_needed_memory(params.mf_algo, max_window_size);
 914
 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);
 919         } else {
 920                 size += params.max_search_depth * sizeof(struct lz_match);
 921         }
 922
 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);
 926         }
 927
 928         size += max_window_size * sizeof(struct xpress_item);
 929
 930         return size;
 931 }
 932
 933 static int
 934 xpress_create_compressor(size_t max_window_size, unsigned int compression_level,
 935                          void **c_ret)
 936 {
 937         struct xpress_compressor *c;
 938         struct xpress_compressor_params params;
 939         struct lz_mf_params mf_params;
 940
 941         if (!xpress_window_size_valid(max_window_size))
 942                 return WIMLIB_ERR_INVALID_PARAM;
 943
 944         xpress_build_params(compression_level, max_window_size, &params);
 945         xpress_build_mf_params(&params, max_window_size, &mf_params);
 946
 947         c = CALLOC(1, sizeof(struct xpress_compressor));
 948         if (!c)
 949                 goto oom;
 950
 951         c->params = params;
 952
 953         c->mf = lz_mf_alloc(&mf_params);
 954         if (!c->mf)
 955                 goto oom;
 956
 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)
 962                         goto oom;
 963                 c->cache_limit = c->cached_matches + cache_len -
 964                                    (params.max_search_depth + 1);
 965         } else {
 966                 c->cached_matches = MALLOC(params.max_search_depth *
 967                                            sizeof(struct lz_match));
 968                 if (!c->cached_matches)
 969                         goto oom;
 970         }
 971
 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));
 976                 if (!c->optimum)
 977                         goto oom;
 978         }
 979
 980         c->chosen_items = MALLOC(max_window_size * sizeof(struct xpress_item));
 981         if (!c->chosen_items)
 982                 goto oom;
 983
 984         *c_ret = c;
 985         return 0;
 986
 987 oom:
 988         xpress_free_compressor(c);
 989         return WIMLIB_ERR_NOMEM;
 990 }
 991
 992 static size_t
 993 xpress_compress(const void *uncompressed_data, size_t uncompressed_size,
 994                 void *compressed_data, size_t compressed_size_avail, void *_c)
 995 {
 996         struct xpress_compressor *c = _c;
 997         u32 num_chosen_items;
 998         u8 *cptr;
 999         struct output_bitstream ostream;
1000         u32 compressed_size;
1001
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
1004          * input size.
1005          *
1006          * +1 to take into account that the buffer for compressed data is 1 byte
1007          * smaller than the buffer for uncompressed data.
1008          *
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)
1012                 return 0;
1013
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);
1018
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);
1023
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);
1029
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)
1033                 return 0;
1034
1035         /* Return the length of the compressed data.  */
1036         return compressed_size + XPRESS_NUM_SYMBOLS / 2;
1037 }
1038
1039 static void
1040 xpress_free_compressor(void *_c)
1041 {
1042         struct xpress_compressor *c = _c;
1043
1044         if (c) {
1045                 lz_mf_free(c->mf);
1046                 FREE(c->cached_matches);
1047                 FREE(c->optimum);
1048                 FREE(c->chosen_items);
1049                 FREE(c);
1050         }
1051 }
1052
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,
1058 };