+ cache_ptr = c->cache_ptr;
+ matches = cache_ptr + 1;
+ if (cache_ptr <= c->cache_limit) {
+ num_matches = cache_ptr->len;
+ c->cache_ptr = matches + num_matches;
+ } else {
+ num_matches = 0;
+ }
+ c->match_window_pos++;
+ *matches_ret = matches;
+ return num_matches;
+}
+
+static unsigned
+lzx_get_matches_usecache_nocheck(struct lzx_compressor *c,
+ const struct lz_match **matches_ret)
+{
+ struct lz_match *cache_ptr;
+ struct lz_match *matches;
+ unsigned num_matches;
+
+ cache_ptr = c->cache_ptr;
+ matches = cache_ptr + 1;
+ num_matches = cache_ptr->len;
+ c->cache_ptr = matches + num_matches;
+ c->match_window_pos++;
+ *matches_ret = matches;
+ return num_matches;
+}
+
+static unsigned
+lzx_get_matches_nocache_singleblock(struct lzx_compressor *c,
+ const struct lz_match **matches_ret)
+{
+ struct lz_match *matches;
+ unsigned num_matches;
+
+ matches = c->cache_ptr;
+ num_matches = lz_mf_get_matches(c->mf, matches);
+ c->match_window_pos++;
+ *matches_ret = matches;
+ return num_matches;
+}
+
+static unsigned
+lzx_get_matches_nocache_multiblock(struct lzx_compressor *c,
+ const struct lz_match **matches_ret)
+{
+ struct lz_match *matches;
+ unsigned num_matches;
+
+ matches = c->cache_ptr;
+ num_matches = lz_mf_get_matches(c->mf, matches);
+ num_matches = maybe_truncate_matches(matches, num_matches, c);
+ c->match_window_pos++;
+ *matches_ret = matches;
+ return num_matches;
+}
+
+/*
+ * Find matches at the next position in the window.
+ *
+ * Returns the number of matches found and sets *matches_ret to point to the
+ * matches array. The matches will be sorted by strictly increasing length and
+ * offset.
+ */
+static inline unsigned
+lzx_get_matches(struct lzx_compressor *c,
+ const struct lz_match **matches_ret)
+{
+ return (*c->get_matches_func)(c, matches_ret);
+}
+
+static void
+lzx_skip_bytes_fillcache(struct lzx_compressor *c, unsigned n)
+{
+ struct lz_match *cache_ptr;
+
+ cache_ptr = c->cache_ptr;
+ c->match_window_pos += n;
+ lz_mf_skip_positions(c->mf, n);
+ if (cache_ptr <= c->cache_limit) {
+ do {
+ cache_ptr->len = 0;
+ cache_ptr += 1;
+ } while (--n && cache_ptr <= c->cache_limit);
+ }
+ c->cache_ptr = cache_ptr;
+}
+
+static void
+lzx_skip_bytes_usecache(struct lzx_compressor *c, unsigned n)
+{
+ struct lz_match *cache_ptr;
+
+ cache_ptr = c->cache_ptr;
+ c->match_window_pos += n;
+ if (cache_ptr <= c->cache_limit) {
+ do {
+ cache_ptr += 1 + cache_ptr->len;
+ } while (--n && cache_ptr <= c->cache_limit);
+ }
+ c->cache_ptr = cache_ptr;
+}
+
+static void
+lzx_skip_bytes_usecache_nocheck(struct lzx_compressor *c, unsigned n)
+{
+ struct lz_match *cache_ptr;
+
+ cache_ptr = c->cache_ptr;
+ c->match_window_pos += n;
+ do {
+ cache_ptr += 1 + cache_ptr->len;
+ } while (--n);
+ c->cache_ptr = cache_ptr;
+}
+
+static void
+lzx_skip_bytes_nocache(struct lzx_compressor *c, unsigned n)
+{
+ c->match_window_pos += n;
+ lz_mf_skip_positions(c->mf, n);
+}
+
+/*
+ * Skip the specified number of positions in the window (don't search for
+ * matches at them).
+ */
+static inline void
+lzx_skip_bytes(struct lzx_compressor *c, unsigned n)
+{
+ return (*c->skip_bytes_func)(c, n);
+}
+
+/*
+ * Reverse the linked list of near-optimal matches so that they can be returned
+ * in forwards order.
+ *
+ * Returns the first match in the list.
+ */
+static struct lz_match
+lzx_match_chooser_reverse_list(struct lzx_compressor *c, unsigned cur_pos)
+{
+ unsigned prev_link, saved_prev_link;
+ unsigned prev_match_offset, saved_prev_match_offset;
+
+ c->optimum_end_idx = cur_pos;
+
+ saved_prev_link = c->optimum[cur_pos].prev.link;
+ saved_prev_match_offset = c->optimum[cur_pos].prev.match_offset;
+
+ do {
+ prev_link = saved_prev_link;
+ prev_match_offset = saved_prev_match_offset;
+
+ saved_prev_link = c->optimum[prev_link].prev.link;
+ saved_prev_match_offset = c->optimum[prev_link].prev.match_offset;
+
+ c->optimum[prev_link].next.link = cur_pos;
+ c->optimum[prev_link].next.match_offset = prev_match_offset;
+
+ cur_pos = prev_link;
+ } while (cur_pos != 0);
+
+ c->optimum_cur_idx = c->optimum[0].next.link;
+
+ return (struct lz_match)
+ { .len = c->optimum_cur_idx,
+ .offset = c->optimum[0].next.match_offset,
+ };
+}
+
+/*
+ * Find the longest repeat offset match.
+ *
+ * If no match of at least LZX_MIN_MATCH_LEN bytes is found, then return 0.
+ *
+ * If a match of at least LZX_MIN_MATCH_LEN bytes is found, then return its
+ * length and set *slot_ret to the index of its offset in @queue.
+ */
+static inline u32
+lzx_repsearch(const u8 * const strptr, const u32 bytes_remaining,
+ const struct lzx_lru_queue *queue, unsigned *slot_ret)
+{
+ BUILD_BUG_ON(LZX_MIN_MATCH_LEN != 2);
+ return lz_repsearch(strptr, bytes_remaining, LZX_MAX_MATCH_LEN,
+ queue->R, LZX_NUM_RECENT_OFFSETS, slot_ret);
+}
+
+/*
+ * lzx_choose_near_optimal_item() -
+ *
+ * Choose an approximately optimal match or literal to use at the next position
+ * in the string, or "window", being LZ-encoded.
+ *
+ * This is based on algorithms used in 7-Zip, including the DEFLATE encoder
+ * and the LZMA encoder, written by Igor Pavlov.
+ *
+ * Unlike a greedy parser that always takes the longest match, or even a "lazy"
+ * parser with one match/literal look-ahead like zlib, the algorithm used here
+ * may look ahead many matches/literals to determine the approximately optimal
+ * match/literal to code next. The motivation is that the compression ratio is
+ * improved if the compressor can do things like use a shorter-than-possible
+ * match in order to allow a longer match later, and also take into account the
+ * estimated real cost of coding each match/literal based on the underlying
+ * entropy encoding.
+ *
+ * Still, this is not a true optimal parser for several reasons:
+ *
+ * - Real compression formats use entropy encoding of the literal/match
+ * sequence, so the real cost of coding each match or literal is unknown until
+ * the parse is fully determined. It can be approximated based on iterative
+ * parses, but the end result is not guaranteed to be globally optimal.
+ *
+ * - Very long matches are chosen immediately. This is because locations with
+ * long matches are likely to have many possible alternatives that would cause
+ * slow optimal parsing, but also such locations are already highly
+ * compressible so it is not too harmful to just grab the longest match.
+ *
+ * - Not all possible matches at each location are considered because the
+ * underlying match-finder limits the number and type of matches produced at
+ * each position. For example, for a given match length it's usually not
+ * worth it to only consider matches other than the lowest-offset match,
+ * except in the case of a repeat offset.
+ *
+ * - Although we take into account the adaptive state (in LZX, the recent offset
+ * queue), coding decisions made with respect to the adaptive state will be
+ * locally optimal but will not necessarily be globally optimal. This is
+ * because the algorithm only keeps the least-costly path to get to a given
+ * location and does not take into account that a slightly more costly path
+ * could result in a different adaptive state that ultimately results in a
+ * lower global cost.
+ *
+ * - The array space used by this function is bounded, so in degenerate cases it
+ * is forced to start returning matches/literals before the algorithm has
+ * really finished.
+ *
+ * Each call to this function does one of two things:
+ *
+ * 1. Build a sequence of near-optimal matches/literals, up to some point, that
+ * will be returned by subsequent calls to this function, then return the
+ * first one.
+ *
+ * OR
+ *
+ * 2. Return the next match/literal previously computed by a call to this
+ * function.
+ *
+ * The return value is a (length, offset) pair specifying the match or literal
+ * chosen. For literals, the length is 0 or 1 and the offset is meaningless.
+ */
+static struct lz_match
+lzx_choose_near_optimal_item(struct lzx_compressor *c)
+{
+ unsigned num_matches;
+ const struct lz_match *matches;
+ struct lz_match match;
+ u32 longest_len;
+ u32 longest_rep_len;
+ unsigned longest_rep_slot;
+ unsigned cur_pos;
+ unsigned end_pos;
+ struct lzx_mc_pos_data *optimum = c->optimum;
+
+ if (c->optimum_cur_idx != c->optimum_end_idx) {
+ /* Case 2: Return the next match/literal already found. */
+ match.len = optimum[c->optimum_cur_idx].next.link -
+ c->optimum_cur_idx;
+ match.offset = optimum[c->optimum_cur_idx].next.match_offset;
+
+ c->optimum_cur_idx = optimum[c->optimum_cur_idx].next.link;
+ return match;
+ }
+
+ /* Case 1: Compute a new list of matches/literals to return. */
+
+ c->optimum_cur_idx = 0;
+ c->optimum_end_idx = 0;
+
+ /* Search for matches at repeat offsets. As a heuristic, we only keep
+ * the one with the longest match length. */
+ if (likely(c->match_window_pos >= 1)) {
+ longest_rep_len = lzx_repsearch(&c->cur_window[c->match_window_pos],
+ c->match_window_end - c->match_window_pos,
+ &c->queue,
+ &longest_rep_slot);
+ } else {
+ longest_rep_len = 0;
+ }
+
+ /* If there's a long match with a repeat offset, choose it immediately. */
+ if (longest_rep_len >= c->params.nice_match_length) {
+ lzx_skip_bytes(c, longest_rep_len);
+ return (struct lz_match) {
+ .len = longest_rep_len,
+ .offset = c->queue.R[longest_rep_slot],
+ };
+ }
+
+ /* Find other matches. */
+ num_matches = lzx_get_matches(c, &matches);
+
+ /* If there's a long match, choose it immediately. */
+ if (num_matches) {
+ longest_len = matches[num_matches - 1].len;
+ if (longest_len >= c->params.nice_match_length) {
+ lzx_skip_bytes(c, longest_len - 1);
+ return matches[num_matches - 1];
+ }
+ } else {
+ longest_len = 1;
+ }
+
+ /* Calculate the cost to reach the next position by coding a literal. */
+ optimum[1].queue = c->queue;
+ optimum[1].cost = lzx_literal_cost(c->cur_window[c->match_window_pos - 1],
+ &c->costs);
+ optimum[1].prev.link = 0;