+ len = 2;
+ i = 0;
+ do {
+ offset_data = matches[i].offset + LZX_OFFSET_OFFSET;
+ position_cost = cur_optimum_ptr->cost;
+ offset_slot = lzx_get_offset_slot_raw(offset_data);
+ num_extra_bits = lzx_extra_offset_bits[offset_slot];
+ if (num_extra_bits >= 3) {
+ position_cost += num_extra_bits - 3;
+ position_cost += c->costs.aligned[offset_data & 7];
+ } else {
+ position_cost += num_extra_bits;
+ }
+ do {
+ cost = position_cost +
+ lzx_match_cost_raw(len, offset_slot, &c->costs);
+ if (cost < (cur_optimum_ptr + len)->cost) {
+ (cur_optimum_ptr + len)->cost = cost;
+ (cur_optimum_ptr + len)->mc_item_data =
+ (offset_data << MC_OFFSET_SHIFT) | len;
+ }
+ } while (++len <= matches[i].len);
+ } while (++i != num_matches);
+#endif
+}
+
+/*
+ * Search for repeat offset matches with the current position.
+ */
+static inline unsigned
+lzx_repsearch(const u8 * const strptr, const u32 bytes_remaining,
+ const struct lzx_lru_queue *queue, unsigned *rep_max_idx_ret)
+{
+ BUILD_BUG_ON(LZX_NUM_RECENT_OFFSETS != 3);
+ return lz_repsearch3(strptr, min(bytes_remaining, LZX_MAX_MATCH_LEN),
+ queue->R, rep_max_idx_ret);
+}
+
+/*
+ * The main near-optimal parsing routine.
+ *
+ * Briefly, the algorithm does an approximate minimum-cost path search to find a
+ * "near-optimal" sequence of matches and literals to output, based on the
+ * current cost model. The algorithm steps forward, position by position (byte
+ * by byte), and updates the minimum cost path to reach each later position that
+ * can be reached using a match or literal from the current position. This is
+ * essentially Dijkstra's algorithm in disguise: the graph nodes are positions,
+ * the graph edges are possible matches/literals to code, and the cost of each
+ * edge is the estimated number of bits that will be required to output the
+ * corresponding match or literal. But one difference is that we actually
+ * compute the lowest-cost path in pieces, where each piece is terminated when
+ * there are no choices to be made.
+ *
+ * This function will run this algorithm on the portion of the window from
+ * &c->cur_window[c->match_window_pos] to &c->cur_window[c->match_window_end].
+ *
+ * On entry, c->queue must be the current state of the match offset LRU queue,
+ * and c->costs must be the current cost model to use for Huffman symbols.
+ *
+ * On exit, c->queue will be the state that the LRU queue would be in if the
+ * chosen items were to be coded.
+ *
+ * If next_chosen_item != NULL, then all items chosen will be recorded (saved in
+ * the chosen_items array). Otherwise, all items chosen will only be tallied
+ * (symbol frequencies tallied in c->freqs).
+ */
+static void
+lzx_optim_pass(struct lzx_compressor *c, struct lzx_item **next_chosen_item)
+{
+ const u8 *block_end;
+ struct lzx_lru_queue *begin_queue;
+ const u8 *window_ptr;
+ struct lzx_mc_pos_data *cur_optimum_ptr;
+ struct lzx_mc_pos_data *end_optimum_ptr;
+ const struct lz_match *matches;
+ unsigned num_matches;
+ unsigned longest_len;
+ unsigned rep_max_len;
+ unsigned rep_max_idx;
+ unsigned literal;
+ unsigned len;
+ u32 cost;
+ u32 offset_data;
+
+ block_end = &c->cur_window[c->match_window_end];
+ begin_queue = &c->queue;
+begin:
+ /* Start building a new list of items, which will correspond to the next
+ * piece of the overall minimum-cost path.
+ *
+ * *begin_queue is the current state of the match offset LRU queue. */