wimlib.net Git - wimlib/blob - src/xpress_compress.c

   1 /*
   2  * xpress_compress.c
   3  *
   4  * A compressor for the XPRESS compression format (Huffman variant).
   5  */
   6
   7 /*
   8  * Copyright (C) 2012, 2013, 2014 Eric Biggers
   9  *
  10  * This file is free software; you can redistribute it and/or modify it under
  11  * the terms of the GNU Lesser General Public License as published by the Free
  12  * Software Foundation; either version 3 of the License, or (at your option) any
  13  * later version.
  14  *
  15  * This file is distributed in the hope that it will be useful, but WITHOUT
  16  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  17  * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
  18  * details.
  19  *
  20  * You should have received a copy of the GNU Lesser General Public License
  21  * along with this file; if not, see http://www.gnu.org/licenses/.
  22  */
  23
  24 #ifdef HAVE_CONFIG_H
  25 #  include "config.h"
  26 #endif
  27
  28 /*
  29  * The maximum buffer size, in bytes, that can be compressed.  An XPRESS
  30  * compressor instance must be created with a 'max_bufsize' less than or equal
  31  * to this value.
  32  */
  33 #define XPRESS_MAX_BUFSIZE              65536
  34
  35 /*
  36  * Define to 1 to enable the near-optimal parsing algorithm at high compression
  37  * levels.  The near-optimal parsing algorithm produces a compression ratio
  38  * significantly better than the greedy and lazy algorithms.  However, it is
  39  * much slower.
  40  */
  41 #define SUPPORT_NEAR_OPTIMAL_PARSING    1
  42
  43 /*
  44  * The lowest compression level at which near-optimal parsing is enabled.
  45  */
  46 #define MIN_LEVEL_FOR_NEAR_OPTIMAL      60
  47
  48 /*
  49  * The window order for the matchfinder.  This must be the base 2 logarithm of
  50  * the maximum buffer size.
  51  */
  52 #define MATCHFINDER_WINDOW_ORDER        16
  53
  54 /*
  55  * Although XPRESS can potentially use a sliding window, it isn't well suited
  56  * for large buffers of data because there is no way to reset the Huffman code.
  57  * Therefore, we only allow buffers in which there is no restriction on match
  58  * offsets (no sliding window).  This simplifies the code and allows some
  59  * optimizations.
  60  */
  61 #define MATCHFINDER_IS_SLIDING          0
  62
  63 #include <string.h>
  64
  65 #include "wimlib/bitops.h"
  66 #include "wimlib/compress_common.h"
  67 #include "wimlib/compressor_ops.h"
  68 #include "wimlib/endianness.h"
  69 #include "wimlib/error.h"
  70 #include "wimlib/hc_matchfinder.h"
  71 #include "wimlib/unaligned.h"
  72 #include "wimlib/util.h"
  73 #include "wimlib/xpress_constants.h"
  74
  75 #if SUPPORT_NEAR_OPTIMAL_PARSING
  76
  77 /*
  78  * CACHE_RESERVE_PER_POS is the number of lz_match structures to reserve in the
  79  * match cache for each byte position.  This value should be high enough so that
  80  * virtually the time, all matches found in the input buffer can fit in the
  81  * match cache.  However, fallback behavior on cache overflow is still required.
  82  */
  83 #define CACHE_RESERVE_PER_POS   8
  84
  85 /*
  86  * We use a binary-tree based matchfinder for optimal parsing because it can
  87  * find more matches in the same number of steps compared to hash-chain based
  88  * matchfinders.  In addition, since we need to find matches at almost every
  89  * position, there isn't much penalty for keeping the sequences sorted in the
  90  * binary trees.
  91  */
  92 #include "wimlib/bt_matchfinder.h"
  93
  94 struct xpress_optimum_node;
  95
  96 #endif /* SUPPORT_NEAR_OPTIMAL_PARSING */
  97
  98 struct xpress_item;
  99
 100 /* The main XPRESS compressor structure  */
 101 struct xpress_compressor {
 102
 103         /* Pointer to the compress() implementation chosen at allocation time */
 104         size_t (*impl)(struct xpress_compressor *,
 105                        const void *, size_t, void *, size_t);
 106
 107         /* Symbol frequency counters for the Huffman code  */
 108         u32 freqs[XPRESS_NUM_SYMBOLS];
 109
 110         /* The Huffman codewords and their lengths  */
 111         u32 codewords[XPRESS_NUM_SYMBOLS];
 112         u8 lens[XPRESS_NUM_SYMBOLS];
 113
 114         /* The "nice" match length: if a match of this length is found, then
 115          * choose it immediately without further consideration.  */
 116         unsigned nice_match_length;
 117
 118         /* The maximum search depth: consider at most this many potential
 119          * matches at each position.  */
 120         unsigned max_search_depth;
 121
 122         union {
 123                 /* Data for greedy or lazy parsing  */
 124                 struct {
 125                         struct hc_matchfinder hc_mf;
 126                         struct xpress_item *chosen_items;
 127                         u8 nonoptimal_end[0];
 128                 };
 129
 130         #if SUPPORT_NEAR_OPTIMAL_PARSING
 131                 /* Data for near-optimal parsing  */
 132                 struct {
 133                         struct bt_matchfinder bt_mf;
 134                         struct xpress_optimum_node *optimum_nodes;
 135                         struct lz_match *match_cache;
 136                         struct lz_match *cache_overflow_mark;
 137                         unsigned num_optim_passes;
 138                         u32 costs[XPRESS_NUM_SYMBOLS];
 139                         u8 optimal_end[0];
 140                 };
 141         #endif
 142         };
 143 };
 144
 145 #if SUPPORT_NEAR_OPTIMAL_PARSING
 146
 147 /*
 148  * This structure represents a byte position in the input buffer and a node in
 149  * the graph of possible match/literal choices.
 150  *
 151  * Logically, each incoming edge to this node is labeled with a literal or a
 152  * match that can be taken to reach this position from an earlier position; and
 153  * each outgoing edge from this node is labeled with a literal or a match that
 154  * can be taken to advance from this position to a later position.
 155  *
 156  * But these "edges" are actually stored elsewhere (in 'match_cache').  Here we
 157  * associate with each node just two pieces of information:
 158  *
 159  *      'cost_to_end' is the minimum cost to reach the end of the buffer from
 160  *      this position.
 161  *
 162  *      'item' represents the literal or match that must be chosen from here to
 163  *      reach the end of the buffer with the minimum cost.  Equivalently, this
 164  *      can be interpreted as the label of the outgoing edge on the minimum cost
 165  *      path to the "end of buffer" node from this node.
 166  */
 167 struct xpress_optimum_node {
 168
 169         u32 cost_to_end;
 170
 171         /*
 172          * Notes on the match/literal representation used here:
 173          *
 174          *      The low bits of 'item' are the length: 1 if the item is a
 175          *      literal, or the match length if the item is a match.
 176          *
 177          *      The high bits of 'item' are the actual literal byte if the item
 178          *      is a literal, or the match offset if the item is a match.
 179          */
 180 #define OPTIMUM_OFFSET_SHIFT    16
 181 #define OPTIMUM_LEN_MASK        (((u32)1 << OPTIMUM_OFFSET_SHIFT) - 1)
 182         u32 item;
 183 };
 184
 185 #endif /* SUPPORT_NEAR_OPTIMAL_PARSING */
 186
 187 /* An intermediate representation of an XPRESS match or literal  */
 188 struct xpress_item {
 189         /*
 190          * Bits 0  -  8: Symbol
 191          * Bits 9  - 24: Length - XPRESS_MIN_MATCH_LEN
 192          * Bits 25 - 28: Number of extra offset bits
 193          * Bits 29+    : Extra offset bits
 194          *
 195          * Unfortunately, gcc generates worse code if we use real bitfields here.
 196          */
 197         u64 data;
 198 };
 199
 200 /*
 201  * Structure to keep track of the current state of sending compressed data to
 202  * the output buffer.
 203  *
 204  * The XPRESS bitstream is encoded as a sequence of little endian 16-bit coding
 205  * units interwoven with literal bytes.
 206  */
 207 struct xpress_output_bitstream {
 208
 209         /* Bits that haven't yet been written to the output buffer.  */
 210         u32 bitbuf;
 211
 212         /* Number of bits currently held in @bitbuf.  */
 213         u32 bitcount;
 214
 215         /* Pointer to the start of the output buffer.  */
 216         u8 *start;
 217
 218         /* Pointer to the location in the ouput buffer at which to write the
 219          * next 16 bits.  */
 220         u8 *next_bits;
 221
 222         /* Pointer to the location in the output buffer at which to write the
 223          * next 16 bits, after @next_bits.  */
 224         u8 *next_bits2;
 225
 226         /* Pointer to the location in the output buffer at which to write the
 227          * next literal byte.  */
 228         u8 *next_byte;
 229
 230         /* Pointer to the end of the output buffer.  */
 231         u8 *end;
 232 };
 233
 234 /* Reset the symbol frequencies for the XPRESS Huffman code.  */
 235 static void
 236 xpress_reset_symbol_frequencies(struct xpress_compressor *c)
 237 {
 238         memset(c->freqs, 0, sizeof(c->freqs));
 239 }
 240
 241 /*
 242  * Make the Huffman code for XPRESS.
 243  *
 244  * Input: c->freqs
 245  * Output: c->lens and c->codewords
 246  */
 247 static void
 248 xpress_make_huffman_code(struct xpress_compressor *c)
 249 {
 250         make_canonical_huffman_code(XPRESS_NUM_SYMBOLS, XPRESS_MAX_CODEWORD_LEN,
 251                                     c->freqs, c->lens, c->codewords);
 252 }
 253
 254 /*
 255  * Initialize the output bitstream.
 256  *
 257  * @os
 258  *      The output bitstream structure to initialize.
 259  * @buffer
 260  *      The output buffer.
 261  * @size
 262  *      Size of @buffer, in bytes.  Must be at least 4.
 263  */
 264 static void
 265 xpress_init_output(struct xpress_output_bitstream *os, void *buffer, size_t size)
 266 {
 267         os->bitbuf = 0;
 268         os->bitcount = 0;
 269         os->start = buffer;
 270         os->next_bits = os->start;
 271         os->next_bits2 = os->start + 2;
 272         os->next_byte = os->start + 4;
 273         os->end = os->start + size;
 274 }
 275
 276 /*
 277  * Write some bits to the output bitstream.
 278  *
 279  * The bits are given by the low-order @num_bits bits of @bits.  Higher-order
 280  * bits in @bits cannot be set.  At most 16 bits can be written at once.
 281  *
 282  * If the output buffer space is exhausted, then the bits will be ignored, and
 283  * xpress_flush_output() will return 0 when it gets called.
 284  */
 285 static inline void
 286 xpress_write_bits(struct xpress_output_bitstream *os,
 287                   const u32 bits, const unsigned num_bits)
 288 {
 289         /* This code is optimized for XPRESS, which never needs to write more
 290          * than 16 bits at once.  */
 291
 292         os->bitcount += num_bits;
 293         os->bitbuf = (os->bitbuf << num_bits) | bits;
 294
 295         if (os->bitcount > 16) {
 296                 os->bitcount -= 16;
 297                 if (os->end - os->next_byte >= 2) {
 298                         put_unaligned_u16_le(os->bitbuf >> os->bitcount, os->next_bits);
 299                         os->next_bits = os->next_bits2;
 300                         os->next_bits2 = os->next_byte;
 301                         os->next_byte += 2;
 302                 }
 303         }
 304 }
 305
 306 /*
 307  * Interweave a literal byte into the output bitstream.
 308  */
 309 static inline void
 310 xpress_write_byte(struct xpress_output_bitstream *os, u8 byte)
 311 {
 312         if (os->next_byte < os->end)
 313                 *os->next_byte++ = byte;
 314 }
 315
 316 /*
 317  * Interweave two literal bytes into the output bitstream.
 318  */
 319 static inline void
 320 xpress_write_u16(struct xpress_output_bitstream *os, u16 v)
 321 {
 322         if (os->end - os->next_byte >= 2) {
 323                 put_unaligned_u16_le(v, os->next_byte);
 324                 os->next_byte += 2;
 325         }
 326 }
 327
 328 /*
 329  * Flush the last coding unit to the output buffer if needed.  Return the total
 330  * number of bytes written to the output buffer, or 0 if an overflow occurred.
 331  */
 332 static size_t
 333 xpress_flush_output(struct xpress_output_bitstream *os)
 334 {
 335         if (os->end - os->next_byte < 2)
 336                 return 0;
 337
 338         put_unaligned_u16_le(os->bitbuf << (16 - os->bitcount), os->next_bits);
 339         put_unaligned_u16_le(0, os->next_bits2);
 340
 341         return os->next_byte - os->start;
 342 }
 343
 344 static inline void
 345 xpress_write_extra_length_bytes(struct xpress_output_bitstream *os,
 346                                 unsigned adjusted_len)
 347 {
 348         /* If length >= 18, output one extra length byte.
 349          * If length >= 273, output three (total) extra length bytes.  */
 350         if (adjusted_len >= 0xF) {
 351                 u8 byte1 = min(adjusted_len - 0xF, 0xFF);
 352                 xpress_write_byte(os, byte1);
 353                 if (byte1 == 0xFF)
 354                         xpress_write_u16(os, adjusted_len);
 355         }
 356 }
 357
 358 /* Output a match or literal.  */
 359 static inline void
 360 xpress_write_item(struct xpress_item item, struct xpress_output_bitstream *os,
 361                   const u32 codewords[], const u8 lens[])
 362 {
 363         u64 data = item.data;
 364         unsigned symbol = data & 0x1FF;
 365
 366         xpress_write_bits(os, codewords[symbol], lens[symbol]);
 367
 368         if (symbol >= XPRESS_NUM_CHARS) {
 369                 /* Match, not a literal  */
 370                 xpress_write_extra_length_bytes(os, (data >> 9) & 0xFFFF);
 371                 xpress_write_bits(os, data >> 29, (data >> 25) & 0xF);
 372         }
 373 }
 374
 375 /* Output a sequence of XPRESS matches and literals.  */
 376 static void
 377 xpress_write_items(struct xpress_output_bitstream *os,
 378                    const struct xpress_item items[], size_t num_items,
 379                    const u32 codewords[], const u8 lens[])
 380 {
 381         for (size_t i = 0; i < num_items; i++)
 382                 xpress_write_item(items[i], os, codewords, lens);
 383 }
 384
 385 #if SUPPORT_NEAR_OPTIMAL_PARSING
 386
 387 /*
 388  * Follow the minimum cost path in the graph of possible match/literal choices
 389  * and write out the matches/literals using the specified Huffman code.
 390  *
 391  * Note: this is slightly duplicated with xpress_write_items().  However, we
 392  * don't want to waste time translating between intermediate match/literal
 393  * representations.
 394  */
 395 static void
 396 xpress_write_item_list(struct xpress_output_bitstream *os,
 397                        struct xpress_optimum_node *optimum_nodes,
 398                        size_t count, const u32 codewords[], const u8 lens[])
 399 {
 400         struct xpress_optimum_node *cur_optimum_ptr = optimum_nodes;
 401         struct xpress_optimum_node *end_optimum_ptr = optimum_nodes + count;
 402         do {
 403                 unsigned length = cur_optimum_ptr->item & OPTIMUM_LEN_MASK;
 404                 unsigned offset = cur_optimum_ptr->item >> OPTIMUM_OFFSET_SHIFT;
 405
 406                 if (length == 1) {
 407                         /* Literal  */
 408                         unsigned literal = offset;
 409
 410                         xpress_write_bits(os, codewords[literal], lens[literal]);
 411                 } else {
 412                         /* Match  */
 413                         unsigned adjusted_len;
 414                         unsigned offset_high_bit;
 415                         unsigned len_hdr;
 416                         unsigned sym;
 417
 418                         adjusted_len = length - XPRESS_MIN_MATCH_LEN;
 419                         offset_high_bit = fls32(offset);
 420                         len_hdr = min(0xF, adjusted_len);
 421                         sym = XPRESS_NUM_CHARS + ((offset_high_bit << 4) | len_hdr);
 422
 423                         xpress_write_bits(os, codewords[sym], lens[sym]);
 424                         xpress_write_extra_length_bytes(os, adjusted_len);
 425                         xpress_write_bits(os, offset - (1U << offset_high_bit),
 426                                           offset_high_bit);
 427                 }
 428                 cur_optimum_ptr += length;
 429         } while (cur_optimum_ptr != end_optimum_ptr);
 430 }
 431 #endif /* SUPPORT_NEAR_OPTIMAL_PARSING */
 432
 433 /*
 434  * Output the XPRESS-compressed data, given the sequence of match/literal
 435  * "items" that was chosen to represent the input data.
 436  *
 437  * If @near_optimal is %false, then the items are taken from the array
 438  * c->chosen_items[0...count].
 439  *
 440  * If @near_optimal is %true, then the items are taken from the minimum cost
 441  * path stored in c->optimum_nodes[0...count].
 442  */
 443 static size_t
 444 xpress_write(struct xpress_compressor *c, void *out, size_t out_nbytes_avail,
 445              size_t count, bool near_optimal)
 446 {
 447         u8 *cptr;
 448         struct xpress_output_bitstream os;
 449         size_t out_size;
 450
 451         /* Account for the end-of-data symbol and make the Huffman code.  */
 452         c->freqs[XPRESS_END_OF_DATA]++;
 453         xpress_make_huffman_code(c);
 454
 455         /* Output the Huffman code as a series of 512 4-bit lengths.  */
 456         cptr = out;
 457         for (unsigned i = 0; i < XPRESS_NUM_SYMBOLS; i += 2)
 458                 *cptr++ = (c->lens[i + 1] << 4) | c->lens[i];
 459
 460         xpress_init_output(&os, cptr, out_nbytes_avail - XPRESS_NUM_SYMBOLS / 2);
 461
 462         /* Output the Huffman-encoded items.  */
 463 #if SUPPORT_NEAR_OPTIMAL_PARSING
 464         if (near_optimal) {
 465                 xpress_write_item_list(&os, c->optimum_nodes, count,
 466                                        c->codewords, c->lens);
 467
 468         } else
 469 #endif
 470         {
 471                 xpress_write_items(&os, c->chosen_items, count,
 472                                    c->codewords, c->lens);
 473         }
 474
 475         /* Write the end-of-data symbol (needed for MS compatibility)  */
 476         xpress_write_bits(&os, c->codewords[XPRESS_END_OF_DATA],
 477                           c->lens[XPRESS_END_OF_DATA]);
 478
 479         /* Flush any pending data.  Then return the compressed size if the
 480          * compressed data fit in the output buffer, or 0 if it did not.  */
 481         out_size = xpress_flush_output(&os);
 482         if (out_size == 0)
 483                 return 0;
 484
 485         return out_size + XPRESS_NUM_SYMBOLS / 2;
 486 }
 487
 488 /* Tally the Huffman symbol for a literal and return the intermediate
 489  * representation of that literal.  */
 490 static inline struct xpress_item
 491 xpress_record_literal(struct xpress_compressor *c, unsigned literal)
 492 {
 493         c->freqs[literal]++;
 494
 495         return (struct xpress_item) {
 496                 .data = literal,
 497         };
 498 }
 499
 500 /* Tally the Huffman symbol for a match and return the intermediate
 501  * representation of that match.  */
 502 static inline struct xpress_item
 503 xpress_record_match(struct xpress_compressor *c, unsigned length, unsigned offset)
 504 {
 505         unsigned adjusted_len = length - XPRESS_MIN_MATCH_LEN;
 506         unsigned len_hdr = min(adjusted_len, 0xF);
 507         unsigned offset_high_bit = fls32(offset);
 508         unsigned sym = XPRESS_NUM_CHARS + ((offset_high_bit << 4) | len_hdr);
 509
 510         c->freqs[sym]++;
 511
 512         return (struct xpress_item) {
 513                 .data = (u64)sym |
 514                         ((u64)adjusted_len << 9) |
 515                         ((u64)offset_high_bit << 25) |
 516                         ((u64)(offset ^ (1U << offset_high_bit)) << 29),
 517         };
 518 }
 519
 520 /*
 521  * This is the "greedy" XPRESS compressor. It always chooses the longest match.
 522  * (Exception: as a heuristic, we pass up length 3 matches that have large
 523  * offsets.)
 524  */
 525 static size_t
 526 xpress_compress_greedy(struct xpress_compressor * restrict c,
 527                        const void * restrict in, size_t in_nbytes,
 528                        void * restrict out, size_t out_nbytes_avail)
 529 {
 530         const u8 * const in_base = in;
 531         const u8 *       in_next = in_base;
 532         const u8 * const in_end = in_base + in_nbytes;
 533         struct xpress_item *next_chosen_item = c->chosen_items;
 534         unsigned len_3_too_far;
 535
 536         if (in_nbytes <= 8192)
 537                 len_3_too_far = 2048;
 538         else
 539                 len_3_too_far = 4096;
 540
 541         hc_matchfinder_init(&c->hc_mf);
 542
 543         do {
 544                 unsigned length;
 545                 unsigned offset;
 546
 547                 length = hc_matchfinder_longest_match(&c->hc_mf,
 548                                                       in_base,
 549                                                       in_next,
 550                                                       XPRESS_MIN_MATCH_LEN - 1,
 551                                                       in_end - in_next,
 552                                                       min(in_end - in_next, c->nice_match_length),
 553                                                       c->max_search_depth,
 554                                                       &offset);
 555                 if (length >= XPRESS_MIN_MATCH_LEN &&
 556                     !(length == XPRESS_MIN_MATCH_LEN && offset >= len_3_too_far))
 557                 {
 558                         /* Match found  */
 559                         *next_chosen_item++ =
 560                                 xpress_record_match(c, length, offset);
 561                         in_next += 1;
 562                         hc_matchfinder_skip_positions(&c->hc_mf,
 563                                                       in_base,
 564                                                       in_next,
 565                                                       in_end,
 566                                                       length - 1);
 567                         in_next += length - 1;
 568                 } else {
 569                         /* No match found  */
 570                         *next_chosen_item++ =
 571                                 xpress_record_literal(c, *in_next);
 572                         in_next += 1;
 573                 }
 574         } while (in_next != in_end);
 575
 576         return xpress_write(c, out, out_nbytes_avail,
 577                             next_chosen_item - c->chosen_items, false);
 578 }
 579
 580 /*
 581  * This is the "lazy" XPRESS compressor.  Before choosing a match, it checks to
 582  * see if there's a longer match at the next position.  If yes, it outputs a
 583  * literal and continues to the next position.  If no, it outputs the match.
 584  */
 585 static size_t
 586 xpress_compress_lazy(struct xpress_compressor * restrict c,
 587                      const void * restrict in, size_t in_nbytes,
 588                      void * restrict out, size_t out_nbytes_avail)
 589 {
 590         const u8 * const in_base = in;
 591         const u8 *       in_next = in_base;
 592         const u8 * const in_end = in_base + in_nbytes;
 593         struct xpress_item *next_chosen_item = c->chosen_items;
 594         unsigned len_3_too_far;
 595
 596         if (in_nbytes <= 8192)
 597                 len_3_too_far = 2048;
 598         else
 599                 len_3_too_far = 4096;
 600
 601         hc_matchfinder_init(&c->hc_mf);
 602
 603         do {
 604                 unsigned cur_len;
 605                 unsigned cur_offset;
 606                 unsigned next_len;
 607                 unsigned next_offset;
 608
 609                 /* Find the longest match at the current position.  */
 610                 cur_len = hc_matchfinder_longest_match(&c->hc_mf,
 611                                                        in_base,
 612                                                        in_next,
 613                                                        XPRESS_MIN_MATCH_LEN - 1,
 614                                                        in_end - in_next,
 615                                                        min(in_end - in_next, c->nice_match_length),
 616                                                        c->max_search_depth,
 617                                                        &cur_offset);
 618                 in_next += 1;
 619
 620                 if (cur_len < XPRESS_MIN_MATCH_LEN ||
 621                     (cur_len == XPRESS_MIN_MATCH_LEN &&
 622                      cur_offset >= len_3_too_far))
 623                 {
 624                         /* No match found.  Choose a literal.  */
 625                         *next_chosen_item++ =
 626                                 xpress_record_literal(c, *(in_next - 1));
 627                         continue;
 628                 }
 629
 630         have_cur_match:
 631                 /* We have a match at the current position.  */
 632
 633                 /* If the current match is very long, choose it immediately.  */
 634                 if (cur_len >= c->nice_match_length) {
 635
 636                         *next_chosen_item++ =
 637                                 xpress_record_match(c, cur_len, cur_offset);
 638
 639                         hc_matchfinder_skip_positions(&c->hc_mf,
 640                                                       in_base,
 641                                                       in_next,
 642                                                       in_end,
 643                                                       cur_len - 1);
 644                         in_next += cur_len - 1;
 645                         continue;
 646                 }
 647
 648                 /*
 649                  * Try to find a match at the next position.
 650                  *
 651                  * Note: since we already have a match at the *current*
 652                  * position, we use only half the 'max_search_depth' when
 653                  * checking the *next* position.  This is a useful trade-off
 654                  * because it's more worthwhile to use a greater search depth on
 655                  * the initial match than on the next match (since a lot of the
 656                  * time, that next match won't even be used).
 657                  *
 658                  * Note: it's possible to structure the code such that there's
 659                  * only one call to longest_match(), which handles both the
 660                  * "find the initial match" and "try to find a longer match"
 661                  * cases.  However, it is faster to have two call sites, with
 662                  * longest_match() inlined at each.
 663                  */
 664                 next_len = hc_matchfinder_longest_match(&c->hc_mf,
 665                                                         in_base,
 666                                                         in_next,
 667                                                         cur_len,
 668                                                         in_end - in_next,
 669                                                         min(in_end - in_next, c->nice_match_length),
 670                                                         c->max_search_depth / 2,
 671                                                         &next_offset);
 672                 in_next += 1;
 673
 674                 if (next_len > cur_len) {
 675                         /* Found a longer match at the next position, so output
 676                          * a literal.  */
 677                         *next_chosen_item++ =
 678                                 xpress_record_literal(c, *(in_next - 2));
 679                         cur_len = next_len;
 680                         cur_offset = next_offset;
 681                         goto have_cur_match;
 682                 } else {
 683                         /* Didn't find a longer match at the next position, so
 684                          * output the current match.  */
 685                         *next_chosen_item++ =
 686                                 xpress_record_match(c, cur_len, cur_offset);
 687                         hc_matchfinder_skip_positions(&c->hc_mf,
 688                                                       in_base,
 689                                                       in_next,
 690                                                       in_end,
 691                                                       cur_len - 2);
 692                         in_next += cur_len - 2;
 693                         continue;
 694                 }
 695         } while (in_next != in_end);
 696
 697         return xpress_write(c, out, out_nbytes_avail,
 698                             next_chosen_item - c->chosen_items, false);
 699 }
 700
 701 #if SUPPORT_NEAR_OPTIMAL_PARSING
 702
 703 /*
 704  * Set Huffman symbol costs for the first optimization pass.
 705  *
 706  * It works well to assume that each Huffman symbol is equally probable.  This
 707  * results in each symbol being assigned a cost of -log2(1.0/num_syms) where
 708  * 'num_syms' is the number of symbols in the alphabet.
 709  */
 710 static void
 711 xpress_set_default_costs(struct xpress_compressor *c)
 712 {
 713         for (unsigned i = 0; i < XPRESS_NUM_SYMBOLS; i++)
 714                 c->costs[i] = 9;
 715 }
 716
 717 /* Update the cost model based on the codeword lengths @c->lens.  */
 718 static void
 719 xpress_update_costs(struct xpress_compressor *c)
 720 {
 721         for (unsigned i = 0; i < XPRESS_NUM_SYMBOLS; i++)
 722                 c->costs[i] = c->lens[i] ? c->lens[i] : XPRESS_MAX_CODEWORD_LEN;
 723 }
 724
 725 /*
 726  * Follow the minimum cost path in the graph of possible match/literal choices
 727  * and compute the frequencies of the Huffman symbols that are needed to output
 728  * those matches and literals.
 729  */
 730 static void
 731 xpress_tally_item_list(struct xpress_compressor *c,
 732                        struct xpress_optimum_node *end_optimum_ptr)
 733 {
 734         struct xpress_optimum_node *cur_optimum_ptr = c->optimum_nodes;
 735
 736         do {
 737                 unsigned length = cur_optimum_ptr->item & OPTIMUM_LEN_MASK;
 738                 unsigned offset = cur_optimum_ptr->item >> OPTIMUM_OFFSET_SHIFT;
 739
 740                 if (length == 1) {
 741                         /* Literal  */
 742                         unsigned literal = offset;
 743
 744                         c->freqs[literal]++;
 745                 } else {
 746                         /* Match  */
 747                         unsigned adjusted_len;
 748                         unsigned offset_high_bit;
 749                         unsigned len_hdr;
 750                         unsigned sym;
 751
 752                         adjusted_len = length - XPRESS_MIN_MATCH_LEN;
 753                         offset_high_bit = fls32(offset);
 754                         len_hdr = min(0xF, adjusted_len);
 755                         sym = XPRESS_NUM_CHARS + ((offset_high_bit << 4) | len_hdr);
 756
 757                         c->freqs[sym]++;
 758                 }
 759                 cur_optimum_ptr += length;
 760         } while (cur_optimum_ptr != end_optimum_ptr);
 761 }
 762
 763 /*
 764  * Find a new minimum cost path through the graph of possible match/literal
 765  * choices.  We find the minimum cost path from 'c->optimum_nodes[0]', which
 766  * represents the node at the beginning of the input buffer, to
 767  * 'c->optimum_nodes[in_nbytes]', which represents the node at the end of the
 768  * input buffer.  Edge costs are evaluated using the cost model 'c->costs'.
 769  *
 770  * The algorithm works backward, starting at 'c->optimum_nodes[in_nbytes]' and
 771  * proceeding backwards one position at a time.  At each position, the minimum
 772  * cost to reach 'c->optimum_nodes[in_nbytes]' from that position is computed
 773  * and the match/literal choice is saved.
 774  */
 775 static void
 776 xpress_find_min_cost_path(struct xpress_compressor *c, size_t in_nbytes,
 777                           struct lz_match *end_cache_ptr)
 778 {
 779         struct xpress_optimum_node *cur_optimum_ptr = c->optimum_nodes + in_nbytes;
 780         struct lz_match *cache_ptr = end_cache_ptr;
 781
 782         cur_optimum_ptr->cost_to_end = 0;
 783         do {
 784                 unsigned literal;
 785                 u32 best_item;
 786                 u32 best_cost_to_end;
 787                 unsigned num_matches;
 788                 struct lz_match *match;
 789                 unsigned len;
 790
 791                 cur_optimum_ptr--;
 792                 cache_ptr--;
 793
 794                 literal = cache_ptr->offset;
 795
 796                 /* Consider coding a literal.  */
 797                 best_item = ((u32)literal << OPTIMUM_OFFSET_SHIFT) | 1;
 798                 best_cost_to_end = c->costs[literal] +
 799                                    (cur_optimum_ptr + 1)->cost_to_end;
 800
 801                 num_matches = cache_ptr->length;
 802
 803                 if (num_matches == 0) {
 804                         /* No matches; the only choice is the literal.  */
 805                         cur_optimum_ptr->cost_to_end = best_cost_to_end;
 806                         cur_optimum_ptr->item = best_item;
 807                         continue;
 808                 }
 809
 810                 /*
 811                  * Consider each match length from the minimum
 812                  * (XPRESS_MIN_MATCH_LEN) to the length of the longest match
 813                  * found at this position.  For each length, consider only the
 814                  * smallest offset for which that length is available.  Although
 815                  * this is not guaranteed to be optimal due to the possibility
 816                  * of a larger offset costing less than a smaller offset to
 817                  * code, this is a very useful heuristic.
 818                  */
 819                 match = cache_ptr - num_matches;
 820                 len = XPRESS_MIN_MATCH_LEN;
 821                 if (cache_ptr[-1].length < 0xF + XPRESS_MIN_MATCH_LEN) {
 822                         /* All lengths are small.  Optimize accordingly.  */
 823                         do {
 824                                 unsigned offset;
 825                                 unsigned offset_high_bit;
 826                                 u32 offset_cost;
 827
 828                                 offset = match->offset;
 829                                 offset_high_bit = fls32(offset);
 830                                 offset_cost = offset_high_bit;
 831                                 do {
 832                                         unsigned len_hdr;
 833                                         unsigned sym;
 834                                         u32 cost_to_end;
 835
 836                                         len_hdr = len - XPRESS_MIN_MATCH_LEN;
 837                                         sym = XPRESS_NUM_CHARS +
 838                                               ((offset_high_bit << 4) | len_hdr);
 839                                         cost_to_end =
 840                                                 offset_cost + c->costs[sym] +
 841                                                 (cur_optimum_ptr + len)->cost_to_end;
 842                                         if (cost_to_end < best_cost_to_end) {
 843                                                 best_cost_to_end = cost_to_end;
 844                                                 best_item =
 845                                                         ((u32)offset <<
 846                                                          OPTIMUM_OFFSET_SHIFT) | len;
 847                                         }
 848                                 } while (++len <= match->length);
 849                         } while (++match != cache_ptr);
 850                 } else {
 851                         /* Some lengths are big.  */
 852                         do {
 853                                 unsigned offset;
 854                                 unsigned offset_high_bit;
 855                                 u32 offset_cost;
 856
 857                                 offset = match->offset;
 858                                 offset_high_bit = fls32(offset);
 859                                 offset_cost = offset_high_bit;
 860                                 do {
 861                                         unsigned adjusted_len;
 862                                         unsigned len_hdr;
 863                                         unsigned sym;
 864                                         u32 cost_to_end;
 865
 866                                         adjusted_len = len - XPRESS_MIN_MATCH_LEN;
 867                                         len_hdr = min(adjusted_len, 0xF);
 868                                         sym = XPRESS_NUM_CHARS +
 869                                               ((offset_high_bit << 4) | len_hdr);
 870                                         cost_to_end =
 871                                                 offset_cost + c->costs[sym] +
 872                                                 (cur_optimum_ptr + len)->cost_to_end;
 873                                         if (adjusted_len >= 0xF) {
 874                                                 cost_to_end += 8;
 875                                                 if (adjusted_len - 0xF >= 0xFF)
 876                                                         cost_to_end += 16;
 877                                         }
 878                                         if (cost_to_end < best_cost_to_end) {
 879                                                 best_cost_to_end = cost_to_end;
 880                                                 best_item =
 881                                                         ((u32)offset <<
 882                                                          OPTIMUM_OFFSET_SHIFT) | len;
 883                                         }
 884                                 } while (++len <= match->length);
 885                         } while (++match != cache_ptr);
 886                 }
 887                 cache_ptr -= num_matches;
 888                 cur_optimum_ptr->cost_to_end = best_cost_to_end;
 889                 cur_optimum_ptr->item = best_item;
 890         } while (cur_optimum_ptr != c->optimum_nodes);
 891 }
 892
 893 /*
 894  * This routine finds matches at each position in the buffer in[0...in_nbytes].
 895  * The matches are cached in the array c->match_cache, and the return value is a
 896  * pointer past the last slot in this array that was filled.
 897  */
 898 static struct lz_match *
 899 xpress_find_matches(struct xpress_compressor * restrict c,
 900                     const void * restrict in, size_t in_nbytes)
 901 {
 902         const u8 * const in_base = in;
 903         const u8 *in_next = in_base;
 904         const u8 * const in_end = in_base + in_nbytes;
 905         struct lz_match *cache_ptr = c->match_cache;
 906         unsigned long prev_hash = 0;
 907
 908         bt_matchfinder_init(&c->bt_mf);
 909
 910         do {
 911                 unsigned num_matches;
 912
 913                 /* If we've found so many matches that the cache might overflow
 914                  * if we keep finding more, then stop finding matches.  This
 915                  * case is very unlikely.  */
 916                 if (unlikely(cache_ptr >= c->cache_overflow_mark)) {
 917                         do {
 918                                 cache_ptr->length = 0;
 919                                 cache_ptr->offset = *in_next++;
 920                                 cache_ptr++;
 921                         } while (in_next != in_end);
 922                         return cache_ptr;
 923                 }
 924
 925                 /* Find matches with the current position using the binary tree
 926                  * matchfinder and save them in the next available slots in
 927                  * the match cache.  */
 928                 num_matches =
 929                         bt_matchfinder_get_matches(&c->bt_mf,
 930                                                    in_base,
 931                                                    in_next,
 932                                                    XPRESS_MIN_MATCH_LEN,
 933                                                    in_end - in_next,
 934                                                    min(in_end - in_next, c->nice_match_length),
 935                                                    c->max_search_depth,
 936                                                    &prev_hash,
 937                                                    cache_ptr);
 938                 cache_ptr += num_matches;
 939                 cache_ptr->length = num_matches;
 940                 cache_ptr->offset = *in_next;
 941                 in_next++;
 942                 cache_ptr++;
 943
 944                 if (num_matches) {
 945                         /*
 946                          * If there was a very long match found, then don't
 947                          * cache any matches for the bytes covered by that
 948                          * match.  This avoids degenerate behavior when
 949                          * compressing highly redundant data, where the number
 950                          * of matches can be very large.
 951                          *
 952                          * This heuristic doesn't actually hurt the compression
 953                          * ratio very much.  If there's a long match, then the
 954                          * data must be highly compressible, so it doesn't
 955                          * matter as much what we do.
 956                          */
 957                         unsigned best_len = cache_ptr[-2].length;
 958                         if (best_len >= c->nice_match_length) {
 959                                 --best_len;
 960                                 do {
 961                                         bt_matchfinder_skip_position(&c->bt_mf,
 962                                                                      in_base,
 963                                                                      in_next,
 964                                                                      in_end,
 965                                                                      min(in_end - in_next,
 966                                                                          c->nice_match_length),
 967                                                                      c->max_search_depth,
 968                                                                      &prev_hash);
 969
 970                                         cache_ptr->length = 0;
 971                                         cache_ptr->offset = *in_next++;
 972                                         cache_ptr++;
 973                                 } while (--best_len);
 974                         }
 975                 }
 976         } while (in_next != in_end);
 977
 978         return cache_ptr;
 979 }
 980
 981 /*
 982  * This is the "near-optimal" XPRESS compressor.  It computes a compressed
 983  * representation of the input buffer by executing a minimum cost path search
 984  * over the graph of possible match/literal choices, assuming a certain cost for
 985  * each Huffman symbol.  The result is usually close to optimal, but it is *not*
 986  * guaranteed to be optimal because of (a) heuristic restrictions in which
 987  * matches are considered, and (b) symbol costs are unknown until those symbols
 988  * have already been chosen --- so iterative optimization must be used, and the
 989  * algorithm might converge on a local optimum rather than a global optimum.
 990  */
 991 static size_t
 992 xpress_compress_near_optimal(struct xpress_compressor * restrict c,
 993                              const void * restrict in, size_t in_nbytes,
 994                              void * restrict out, size_t out_nbytes_avail)
 995 {
 996         struct lz_match *end_cache_ptr;
 997         unsigned num_passes_remaining = c->num_optim_passes;
 998
 999         /* Run the input buffer through the matchfinder and save the results. */
1000         end_cache_ptr = xpress_find_matches(c, in, in_nbytes);
1001
1002         /* The first optimization pass uses a default cost model.  Each
1003          * additional optimization pass uses a cost model derived from the
1004          * Huffman code computed in the previous pass.  */
1005         xpress_set_default_costs(c);
1006         do {
1007                 xpress_find_min_cost_path(c, in_nbytes, end_cache_ptr);
1008                 xpress_tally_item_list(c, c->optimum_nodes + in_nbytes);
1009                 if (num_passes_remaining > 1) {
1010                         c->freqs[XPRESS_END_OF_DATA]++;
1011                         xpress_make_huffman_code(c);
1012                         xpress_update_costs(c);
1013                         xpress_reset_symbol_frequencies(c);
1014                 }
1015         } while (--num_passes_remaining);
1016
1017         return xpress_write(c, out, out_nbytes_avail, in_nbytes, true);
1018 }
1019
1020 #endif /* SUPPORT_NEAR_OPTIMAL_PARSING */
1021
1022 static u64
1023 xpress_get_needed_memory(size_t max_bufsize, unsigned compression_level)
1024 {
1025         size_t size = 0;
1026
1027         if (max_bufsize > XPRESS_MAX_BUFSIZE)
1028                 return 0;
1029
1030         if (compression_level < MIN_LEVEL_FOR_NEAR_OPTIMAL ||
1031             !SUPPORT_NEAR_OPTIMAL_PARSING) {
1032                 size += offsetof(struct xpress_compressor, nonoptimal_end);
1033                 size += max_bufsize * sizeof(struct xpress_item);
1034         }
1035 #if SUPPORT_NEAR_OPTIMAL_PARSING
1036         else {
1037                 size += offsetof(struct xpress_compressor, optimal_end);
1038                 size += (max_bufsize + 1) * sizeof(struct xpress_optimum_node);
1039                 size += ((max_bufsize * CACHE_RESERVE_PER_POS) +
1040                          XPRESS_MAX_MATCH_LEN + max_bufsize) *
1041                                 sizeof(struct lz_match);
1042         }
1043 #endif
1044         return size;
1045 }
1046
1047 static int
1048 xpress_create_compressor(size_t max_bufsize, unsigned compression_level,
1049                          void **c_ret)
1050 {
1051         struct xpress_compressor *c;
1052
1053         if (max_bufsize > XPRESS_MAX_BUFSIZE)
1054                 return WIMLIB_ERR_INVALID_PARAM;
1055
1056         if (compression_level < 30) {
1057                 c = ALIGNED_MALLOC(offsetof(struct xpress_compressor,
1058                                             nonoptimal_end),
1059                                    MATCHFINDER_ALIGNMENT);
1060                 if (!c)
1061                         return WIMLIB_ERR_NOMEM;
1062                 c->impl = xpress_compress_greedy;
1063                 c->max_search_depth = (compression_level * 24) / 16;
1064                 c->nice_match_length = (compression_level * 48) / 16;
1065                 c->chosen_items = MALLOC(max_bufsize * sizeof(struct xpress_item));
1066                 if (!c->chosen_items) {
1067                         ALIGNED_FREE(c);
1068                         return WIMLIB_ERR_NOMEM;
1069                 }
1070         } else if (compression_level < MIN_LEVEL_FOR_NEAR_OPTIMAL ||
1071                    !SUPPORT_NEAR_OPTIMAL_PARSING)
1072         {
1073                 c = ALIGNED_MALLOC(offsetof(struct xpress_compressor,
1074                                             nonoptimal_end),
1075                                    MATCHFINDER_ALIGNMENT);
1076                 if (!c)
1077                         return WIMLIB_ERR_NOMEM;
1078
1079                 c->impl = xpress_compress_lazy;
1080                 c->max_search_depth = (compression_level * 24) / 32;
1081                 c->nice_match_length = (compression_level * 48) / 32;
1082                 c->chosen_items = MALLOC(max_bufsize * sizeof(struct xpress_item));
1083                 if (!c->chosen_items) {
1084                         ALIGNED_FREE(c);
1085                         return WIMLIB_ERR_NOMEM;
1086                 }
1087         }
1088 #if SUPPORT_NEAR_OPTIMAL_PARSING
1089         else {
1090                 c = ALIGNED_MALLOC(offsetof(struct xpress_compressor,
1091                                             optimal_end),
1092                                    MATCHFINDER_ALIGNMENT);
1093                 if (!c)
1094                         return WIMLIB_ERR_NOMEM;
1095                 c->impl = xpress_compress_near_optimal;
1096                 c->max_search_depth = (compression_level * 32) / 100;
1097                 c->nice_match_length = (compression_level * 50) / 100;
1098                 c->num_optim_passes = compression_level / 40;
1099
1100                 c->optimum_nodes = MALLOC((max_bufsize + 1) *
1101                                           sizeof(struct xpress_optimum_node));
1102                 c->match_cache = MALLOC(((max_bufsize * CACHE_RESERVE_PER_POS) +
1103                                          XPRESS_MAX_MATCH_LEN + max_bufsize) *
1104                                         sizeof(struct lz_match));
1105                 if (!c->optimum_nodes || !c->match_cache) {
1106                         FREE(c->optimum_nodes);
1107                         FREE(c->match_cache);
1108                         ALIGNED_FREE(c);
1109                         return WIMLIB_ERR_NOMEM;
1110                 }
1111                 c->cache_overflow_mark =
1112                         &c->match_cache[max_bufsize * CACHE_RESERVE_PER_POS];
1113         }
1114 #endif /* SUPPORT_NEAR_OPTIMAL_PARSING */
1115
1116         *c_ret = c;
1117         return 0;
1118 }
1119
1120 static size_t
1121 xpress_compress(const void *in, size_t in_nbytes,
1122                 void *out, size_t out_nbytes_avail, void *_c)
1123 {
1124         struct xpress_compressor *c = _c;
1125
1126         if (out_nbytes_avail <= XPRESS_NUM_SYMBOLS / 2 + 4)
1127                 return 0;
1128
1129         xpress_reset_symbol_frequencies(c);
1130
1131         return (*c->impl)(c, in, in_nbytes, out, out_nbytes_avail);
1132 }
1133
1134 static void
1135 xpress_free_compressor(void *_c)
1136 {
1137         struct xpress_compressor *c = _c;
1138
1139         if (c) {
1140         #if SUPPORT_NEAR_OPTIMAL_PARSING
1141                 if (c->impl == xpress_compress_near_optimal) {
1142                         FREE(c->optimum_nodes);
1143                         FREE(c->match_cache);
1144                 } else
1145         #endif
1146                         FREE(c->chosen_items);
1147                 ALIGNED_FREE(c);
1148         }
1149 }
1150
1151 const struct compressor_ops xpress_compressor_ops = {
1152         .get_needed_memory  = xpress_get_needed_memory,
1153         .create_compressor  = xpress_create_compressor,
1154         .compress           = xpress_compress,
1155         .free_compressor    = xpress_free_compressor,
1156 };