+
+ /* Write the end-of-data symbol (needed for MS compatibility) */
+ xpress_write_bits(&os, c->codewords[XPRESS_END_OF_DATA],
+ c->lens[XPRESS_END_OF_DATA]);
+
+ /* Flush any pending data. Then return the compressed size if the
+ * compressed data fit in the output buffer, or 0 if it did not. */
+ out_size = xpress_flush_output(&os);
+ if (out_size == 0)
+ return 0;
+
+ return out_size + XPRESS_NUM_SYMBOLS / 2;
+}
+
+/* Tally the Huffman symbol for a literal and return the intermediate
+ * representation of that literal. */
+static inline struct xpress_item
+xpress_record_literal(struct xpress_compressor *c, unsigned literal)
+{
+ c->freqs[literal]++;
+
+ return (struct xpress_item) {
+ .data = literal,
+ };
+}
+
+/* Tally the Huffman symbol for a match and return the intermediate
+ * representation of that match. */
+static inline struct xpress_item
+xpress_record_match(struct xpress_compressor *c, unsigned length, unsigned offset)
+{
+ unsigned adjusted_len = length - XPRESS_MIN_MATCH_LEN;
+ unsigned len_hdr = min(adjusted_len, 0xF);
+ unsigned offset_high_bit = fls32(offset);
+ unsigned sym = XPRESS_NUM_CHARS + ((offset_high_bit << 4) | len_hdr);
+
+ c->freqs[sym]++;
+
+ return (struct xpress_item) {
+ .data = (u64)sym |
+ ((u64)adjusted_len << 9) |
+ ((u64)offset_high_bit << 25) |
+ ((u64)(offset ^ (1U << offset_high_bit)) << 29),
+ };
+}
+
+/*
+ * This is the "greedy" XPRESS compressor. It always chooses the longest match.
+ * (Exception: as a heuristic, we pass up length 3 matches that have large
+ * offsets.)
+ */
+static size_t
+xpress_compress_greedy(struct xpress_compressor * restrict c,
+ const void * restrict in, size_t in_nbytes,
+ void * restrict out, size_t out_nbytes_avail)
+{
+ const u8 * const in_base = in;
+ const u8 * in_next = in_base;
+ const u8 * const in_end = in_base + in_nbytes;
+ struct xpress_item *next_chosen_item = c->chosen_items;
+ unsigned len_3_too_far;
+
+ if (in_nbytes <= 8192)
+ len_3_too_far = 2048;
+ else
+ len_3_too_far = 4096;
+
+ hc_matchfinder_init(&c->hc_mf);
+
+ do {
+ unsigned length;
+ unsigned offset;
+
+ length = hc_matchfinder_longest_match(&c->hc_mf,
+ in_base,
+ in_next,
+ XPRESS_MIN_MATCH_LEN - 1,
+ in_end - in_next,
+ min(in_end - in_next, c->nice_match_length),
+ c->max_search_depth,
+ &offset);
+ if (length >= XPRESS_MIN_MATCH_LEN &&
+ !(length == XPRESS_MIN_MATCH_LEN && offset >= len_3_too_far))
+ {
+ /* Match found */
+ *next_chosen_item++ =
+ xpress_record_match(c, length, offset);
+ in_next += 1;
+ hc_matchfinder_skip_positions(&c->hc_mf,
+ in_base,
+ in_next,
+ in_end,
+ length - 1);
+ in_next += length - 1;
+ } else {
+ /* No match found */
+ *next_chosen_item++ =
+ xpress_record_literal(c, *in_next);
+ in_next += 1;
+ }
+ } while (in_next != in_end);
+
+ return xpress_write(c, out, out_nbytes_avail,
+ next_chosen_item - c->chosen_items, false);
+}
+
+/*
+ * This is the "lazy" XPRESS compressor. Before choosing a match, it checks to
+ * see if there's a longer match at the next position. If yes, it outputs a
+ * literal and continues to the next position. If no, it outputs the match.
+ */
+static size_t
+xpress_compress_lazy(struct xpress_compressor * restrict c,
+ const void * restrict in, size_t in_nbytes,
+ void * restrict out, size_t out_nbytes_avail)
+{
+ const u8 * const in_base = in;
+ const u8 * in_next = in_base;
+ const u8 * const in_end = in_base + in_nbytes;
+ struct xpress_item *next_chosen_item = c->chosen_items;
+ unsigned len_3_too_far;
+
+ if (in_nbytes <= 8192)
+ len_3_too_far = 2048;
+ else
+ len_3_too_far = 4096;
+
+ hc_matchfinder_init(&c->hc_mf);
+
+ do {
+ unsigned cur_len;
+ unsigned cur_offset;
+ unsigned next_len;
+ unsigned next_offset;
+
+ /* Find the longest match at the current position. */
+ cur_len = hc_matchfinder_longest_match(&c->hc_mf,
+ in_base,
+ in_next,
+ XPRESS_MIN_MATCH_LEN - 1,
+ in_end - in_next,
+ min(in_end - in_next, c->nice_match_length),
+ c->max_search_depth,
+ &cur_offset);
+ in_next += 1;
+
+ if (cur_len < XPRESS_MIN_MATCH_LEN ||
+ (cur_len == XPRESS_MIN_MATCH_LEN &&
+ cur_offset >= len_3_too_far))
+ {
+ /* No match found. Choose a literal. */
+ *next_chosen_item++ =
+ xpress_record_literal(c, *(in_next - 1));
+ continue;
+ }
+
+ have_cur_match:
+ /* We have a match at the current position. */
+
+ /* If the current match is very long, choose it immediately. */
+ if (cur_len >= c->nice_match_length) {
+
+ *next_chosen_item++ =
+ xpress_record_match(c, cur_len, cur_offset);
+
+ hc_matchfinder_skip_positions(&c->hc_mf,
+ in_base,
+ in_next,
+ in_end,
+ cur_len - 1);
+ in_next += cur_len - 1;
+ continue;
+ }
+
+ /*
+ * Try to find a match at the next position.
+ *
+ * Note: since we already have a match at the *current*
+ * position, we use only half the 'max_search_depth' when
+ * checking the *next* position. This is a useful trade-off
+ * because it's more worthwhile to use a greater search depth on
+ * the initial match than on the next match (since a lot of the
+ * time, that next match won't even be used).
+ *
+ * Note: it's possible to structure the code such that there's
+ * only one call to longest_match(), which handles both the
+ * "find the initial match" and "try to find a longer match"
+ * cases. However, it is faster to have two call sites, with
+ * longest_match() inlined at each.
+ */
+ next_len = hc_matchfinder_longest_match(&c->hc_mf,
+ in_base,
+ in_next,
+ cur_len,
+ in_end - in_next,
+ min(in_end - in_next, c->nice_match_length),
+ c->max_search_depth / 2,
+ &next_offset);
+ in_next += 1;
+
+ if (next_len > cur_len) {
+ /* Found a longer match at the next position, so output
+ * a literal. */
+ *next_chosen_item++ =
+ xpress_record_literal(c, *(in_next - 2));
+ cur_len = next_len;
+ cur_offset = next_offset;
+ goto have_cur_match;
+ } else {
+ /* Didn't find a longer match at the next position, so
+ * output the current match. */
+ *next_chosen_item++ =
+ xpress_record_match(c, cur_len, cur_offset);
+ hc_matchfinder_skip_positions(&c->hc_mf,
+ in_base,
+ in_next,
+ in_end,
+ cur_len - 2);
+ in_next += cur_len - 2;
+ continue;
+ }
+ } while (in_next != in_end);
+
+ return xpress_write(c, out, out_nbytes_avail,
+ next_chosen_item - c->chosen_items, false);
+}
+
+#if SUPPORT_NEAR_OPTIMAL_PARSING
+
+/*
+ * Set Huffman symbol costs for the first optimization pass.
+ *
+ * It works well to assume that each Huffman symbol is equally probable. This
+ * results in each symbol being assigned a cost of -log2(1.0/num_syms) where
+ * 'num_syms' is the number of symbols in the alphabet.
+ */
+static void
+xpress_set_default_costs(struct xpress_compressor *c)
+{
+ for (unsigned i = 0; i < XPRESS_NUM_SYMBOLS; i++)
+ c->costs[i] = 9;
+}
+
+/* Update the cost model based on the codeword lengths @c->lens. */
+static void
+xpress_update_costs(struct xpress_compressor *c)
+{
+ for (unsigned i = 0; i < XPRESS_NUM_SYMBOLS; i++)
+ c->costs[i] = c->lens[i] ? c->lens[i] : XPRESS_MAX_CODEWORD_LEN;
+}
+
+/*
+ * Follow the minimum cost path in the graph of possible match/literal choices
+ * and compute the frequencies of the Huffman symbols that are needed to output
+ * those matches and literals.
+ */
+static void
+xpress_tally_item_list(struct xpress_compressor *c,
+ struct xpress_optimum_node *end_optimum_ptr)
+{
+ struct xpress_optimum_node *cur_optimum_ptr = c->optimum_nodes;
+
+ do {
+ unsigned length = cur_optimum_ptr->item & OPTIMUM_LEN_MASK;
+ unsigned offset = cur_optimum_ptr->item >> OPTIMUM_OFFSET_SHIFT;
+
+ if (length == 1) {
+ /* Literal */
+ unsigned literal = offset;
+
+ c->freqs[literal]++;
+ } else {
+ /* Match */
+ unsigned adjusted_len;
+ unsigned offset_high_bit;
+ unsigned len_hdr;
+ unsigned sym;
+
+ adjusted_len = length - XPRESS_MIN_MATCH_LEN;
+ offset_high_bit = fls32(offset);
+ len_hdr = min(0xF, adjusted_len);
+ sym = XPRESS_NUM_CHARS + ((offset_high_bit << 4) | len_hdr);
+
+ c->freqs[sym]++;
+ }
+ cur_optimum_ptr += length;
+ } while (cur_optimum_ptr != end_optimum_ptr);
+}
+
+/*
+ * Find a new minimum cost path through the graph of possible match/literal
+ * choices. We find the minimum cost path from 'c->optimum_nodes[0]', which
+ * represents the node at the beginning of the input buffer, to
+ * 'c->optimum_nodes[in_nbytes]', which represents the node at the end of the
+ * input buffer. Edge costs are evaluated using the cost model 'c->costs'.
+ *
+ * The algorithm works backward, starting at 'c->optimum_nodes[in_nbytes]' and
+ * proceeding backwards one position at a time. At each position, the minimum
+ * cost to reach 'c->optimum_nodes[in_nbytes]' from that position is computed
+ * and the match/literal choice is saved.
+ */
+static void
+xpress_find_min_cost_path(struct xpress_compressor *c, size_t in_nbytes,
+ struct lz_match *end_cache_ptr)
+{
+ struct xpress_optimum_node *cur_optimum_ptr = c->optimum_nodes + in_nbytes;
+ struct lz_match *cache_ptr = end_cache_ptr;
+
+ cur_optimum_ptr->cost_to_end = 0;
+ do {
+ unsigned literal;
+ u32 best_item;
+ u32 best_cost_to_end;
+ unsigned num_matches;
+ struct lz_match *match;
+ unsigned len;
+
+ cur_optimum_ptr--;
+ cache_ptr--;
+
+ literal = cache_ptr->offset;
+
+ /* Consider coding a literal. */
+ best_item = ((u32)literal << OPTIMUM_OFFSET_SHIFT) | 1;
+ best_cost_to_end = c->costs[literal] +
+ (cur_optimum_ptr + 1)->cost_to_end;
+
+ num_matches = cache_ptr->length;
+
+ if (num_matches == 0) {
+ /* No matches; the only choice is the literal. */
+ cur_optimum_ptr->cost_to_end = best_cost_to_end;
+ cur_optimum_ptr->item = best_item;
+ continue;
+ }
+
+ /*
+ * Consider each match length from the minimum
+ * (XPRESS_MIN_MATCH_LEN) to the length of the longest match
+ * found at this position. For each length, consider only the
+ * smallest offset for which that length is available. Although
+ * this is not guaranteed to be optimal due to the possibility
+ * of a larger offset costing less than a smaller offset to
+ * code, this is a very useful heuristic.
+ */
+ match = cache_ptr - num_matches;
+ len = XPRESS_MIN_MATCH_LEN;
+ if (cache_ptr[-1].length < 0xF + XPRESS_MIN_MATCH_LEN) {
+ /* All lengths are small. Optimize accordingly. */
+ do {
+ unsigned offset;
+ unsigned offset_high_bit;
+ u32 offset_cost;
+
+ offset = match->offset;
+ offset_high_bit = fls32(offset);
+ offset_cost = offset_high_bit;
+ do {
+ unsigned len_hdr;
+ unsigned sym;
+ u32 cost_to_end;
+
+ len_hdr = len - XPRESS_MIN_MATCH_LEN;
+ sym = XPRESS_NUM_CHARS +
+ ((offset_high_bit << 4) | len_hdr);
+ cost_to_end =
+ offset_cost + c->costs[sym] +
+ (cur_optimum_ptr + len)->cost_to_end;
+ if (cost_to_end < best_cost_to_end) {
+ best_cost_to_end = cost_to_end;
+ best_item =
+ ((u32)offset <<
+ OPTIMUM_OFFSET_SHIFT) | len;
+ }
+ } while (++len <= match->length);
+ } while (++match != cache_ptr);
+ } else {
+ /* Some lengths are big. */
+ do {
+ unsigned offset;
+ unsigned offset_high_bit;
+ u32 offset_cost;
+
+ offset = match->offset;
+ offset_high_bit = fls32(offset);
+ offset_cost = offset_high_bit;
+ do {
+ unsigned adjusted_len;
+ unsigned len_hdr;
+ unsigned sym;
+ u32 cost_to_end;
+
+ adjusted_len = len - XPRESS_MIN_MATCH_LEN;
+ len_hdr = min(adjusted_len, 0xF);
+ sym = XPRESS_NUM_CHARS +
+ ((offset_high_bit << 4) | len_hdr);
+ cost_to_end =
+ offset_cost + c->costs[sym] +
+ (cur_optimum_ptr + len)->cost_to_end;
+ if (adjusted_len >= 0xF) {
+ cost_to_end += 8;
+ if (adjusted_len - 0xF >= 0xFF)
+ cost_to_end += 16;
+ }
+ if (cost_to_end < best_cost_to_end) {
+ best_cost_to_end = cost_to_end;
+ best_item =
+ ((u32)offset <<
+ OPTIMUM_OFFSET_SHIFT) | len;
+ }
+ } while (++len <= match->length);
+ } while (++match != cache_ptr);
+ }
+ cache_ptr -= num_matches;
+ cur_optimum_ptr->cost_to_end = best_cost_to_end;
+ cur_optimum_ptr->item = best_item;
+ } while (cur_optimum_ptr != c->optimum_nodes);
+}
+
+/*
+ * This routine finds matches at each position in the buffer in[0...in_nbytes].
+ * The matches are cached in the array c->match_cache, and the return value is a
+ * pointer past the last slot in this array that was filled.
+ */
+static struct lz_match *
+xpress_find_matches(struct xpress_compressor * restrict c,
+ const void * restrict in, size_t in_nbytes)
+{
+ const u8 * const in_base = in;
+ const u8 *in_next = in_base;
+ const u8 * const in_end = in_base + in_nbytes;
+ struct lz_match *cache_ptr = c->match_cache;
+ unsigned long prev_hash = 0;
+
+ bt_matchfinder_init(&c->bt_mf);
+
+ do {
+ unsigned num_matches;
+
+ /* If we've found so many matches that the cache might overflow
+ * if we keep finding more, then stop finding matches. This
+ * case is very unlikely. */
+ if (unlikely(cache_ptr >= c->cache_overflow_mark)) {
+ do {
+ cache_ptr->length = 0;
+ cache_ptr->offset = *in_next++;
+ cache_ptr++;
+ } while (in_next != in_end);
+ return cache_ptr;
+ }
+
+ /* Find matches with the current position using the binary tree
+ * matchfinder and save them in the next available slots in
+ * the match cache. */
+ num_matches =
+ bt_matchfinder_get_matches(&c->bt_mf,
+ in_base,
+ in_next,
+ XPRESS_MIN_MATCH_LEN,
+ in_end - in_next,
+ min(in_end - in_next, c->nice_match_length),
+ c->max_search_depth,
+ &prev_hash,
+ cache_ptr);
+ cache_ptr += num_matches;
+ cache_ptr->length = num_matches;
+ cache_ptr->offset = *in_next;
+ in_next++;
+ cache_ptr++;
+
+ if (num_matches) {
+ /*
+ * If there was a very long match found, then don't
+ * cache any matches for the bytes covered by that
+ * match. This avoids degenerate behavior when
+ * compressing highly redundant data, where the number
+ * of matches can be very large.
+ *
+ * This heuristic doesn't actually hurt the compression
+ * ratio very much. If there's a long match, then the
+ * data must be highly compressible, so it doesn't
+ * matter as much what we do.
+ */
+ unsigned best_len = cache_ptr[-2].length;
+ if (best_len >= c->nice_match_length) {
+ --best_len;
+ do {
+ bt_matchfinder_skip_position(&c->bt_mf,
+ in_base,
+ in_next,
+ in_end,
+ min(in_end - in_next,
+ c->nice_match_length),
+ c->max_search_depth,
+ &prev_hash);
+
+ cache_ptr->length = 0;
+ cache_ptr->offset = *in_next++;
+ cache_ptr++;
+ } while (--best_len);
+ }
+ }
+ } while (in_next != in_end);
+
+ return cache_ptr;
+}
+
+/*
+ * This is the "near-optimal" XPRESS compressor. It computes a compressed
+ * representation of the input buffer by executing a minimum cost path search
+ * over the graph of possible match/literal choices, assuming a certain cost for
+ * each Huffman symbol. The result is usually close to optimal, but it is *not*
+ * guaranteed to be optimal because of (a) heuristic restrictions in which
+ * matches are considered, and (b) symbol costs are unknown until those symbols
+ * have already been chosen --- so iterative optimization must be used, and the
+ * algorithm might converge on a local optimum rather than a global optimum.
+ */
+static size_t
+xpress_compress_near_optimal(struct xpress_compressor * restrict c,
+ const void * restrict in, size_t in_nbytes,
+ void * restrict out, size_t out_nbytes_avail)
+{
+ struct lz_match *end_cache_ptr;
+ unsigned num_passes_remaining = c->num_optim_passes;
+
+ /* Run the input buffer through the matchfinder and save the results. */
+ end_cache_ptr = xpress_find_matches(c, in, in_nbytes);
+
+ /* The first optimization pass uses a default cost model. Each
+ * additional optimization pass uses a cost model derived from the
+ * Huffman code computed in the previous pass. */
+ xpress_set_default_costs(c);
+ do {
+ xpress_find_min_cost_path(c, in_nbytes, end_cache_ptr);
+ xpress_tally_item_list(c, c->optimum_nodes + in_nbytes);
+ if (num_passes_remaining > 1) {
+ c->freqs[XPRESS_END_OF_DATA]++;
+ xpress_make_huffman_code(c);
+ xpress_update_costs(c);
+ xpress_reset_symbol_frequencies(c);