+ 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. */
+
+ window_ptr = &c->cur_window[c->match_window_pos];
+
+ if (window_ptr == block_end) {
+ c->queue = *begin_queue;
+ return;
+ }
+
+ cur_optimum_ptr = c->optimum;
+ cur_optimum_ptr->cost = 0;
+ cur_optimum_ptr->queue = *begin_queue;
+
+ end_optimum_ptr = cur_optimum_ptr;
+
+ /* The following loop runs once for each per byte in the window, except
+ * in a couple shortcut cases. */
+ for (;;) {
+
+ /* Find explicit offset matches with the current position. */
+ num_matches = lzx_get_matches(c, &matches);
+
+ if (num_matches) {
+ /*
+ * Find the longest repeat offset match with the current
+ * position.
+ *
+ * Heuristics:
+ *
+ * - Only search for repeat offset matches if the
+ * match-finder already found at least one match.
+ *
+ * - Only consider the longest repeat offset match. It
+ * seems to be rare for the optimal parse to include a
+ * repeat offset match that doesn't have the longest
+ * length (allowing for the possibility that not all
+ * of that length is actually used).
+ */
+ rep_max_len = lzx_repsearch(window_ptr,
+ block_end - window_ptr,
+ &cur_optimum_ptr->queue,
+ &rep_max_idx);
+
+ if (rep_max_len) {
+ /* If there's a very long repeat offset match,
+ * choose it immediately. */
+ if (rep_max_len >= c->params.nice_match_length) {
+
+ swap(cur_optimum_ptr->queue.R[0],
+ cur_optimum_ptr->queue.R[rep_max_idx]);
+ begin_queue = &cur_optimum_ptr->queue;
+
+ cur_optimum_ptr += rep_max_len;
+ cur_optimum_ptr->mc_item_data =
+ (rep_max_idx << MC_OFFSET_SHIFT) |
+ rep_max_len;
+
+ lzx_skip_bytes(c, rep_max_len - 1);
+ break;
+ }
+
+ /* If reaching any positions for the first time,
+ * initialize their costs to "infinity". */
+ while (end_optimum_ptr < cur_optimum_ptr + rep_max_len)
+ (++end_optimum_ptr)->cost = MC_INFINITE_COST;
+
+ /* Consider coding a repeat offset match. */
+ lzx_consider_repeat_offset_match(c,
+ cur_optimum_ptr,
+ rep_max_len,
+ rep_max_idx);
+ }
+
+ longest_len = matches[num_matches - 1].len;
+
+ /* If there's a very long explicit offset match, choose
+ * it immediately. */
+ if (longest_len >= c->params.nice_match_length) {
+
+ cur_optimum_ptr->queue.R[2] =
+ cur_optimum_ptr->queue.R[1];
+ cur_optimum_ptr->queue.R[1] =
+ cur_optimum_ptr->queue.R[0];
+ cur_optimum_ptr->queue.R[0] =
+ matches[num_matches - 1].offset;
+ begin_queue = &cur_optimum_ptr->queue;
+
+ offset_data = matches[num_matches - 1].offset +
+ LZX_OFFSET_OFFSET;
+ cur_optimum_ptr += longest_len;
+ cur_optimum_ptr->mc_item_data =
+ (offset_data << MC_OFFSET_SHIFT) |
+ longest_len;
+
+ lzx_skip_bytes(c, longest_len - 1);
+ break;
+ }
+
+ /* If reaching any positions for the first time,
+ * initialize their costs to "infinity". */
+ while (end_optimum_ptr < cur_optimum_ptr + longest_len)
+ (++end_optimum_ptr)->cost = MC_INFINITE_COST;
+
+ /* Consider coding an explicit offset match. */
+ lzx_consider_explicit_offset_matches(c, cur_optimum_ptr,
+ matches, num_matches);
+ } else {
+ /* No matches found. The only choice at this position
+ * is to code a literal. */
+
+ if (end_optimum_ptr == cur_optimum_ptr) {
+ #if 1
+ /* Optimization for single literals. */
+ if (likely(cur_optimum_ptr == c->optimum)) {
+ lzx_declare_literal(c, *window_ptr++,
+ next_chosen_item);
+ if (window_ptr == block_end) {
+ c->queue = cur_optimum_ptr->queue;
+ return;
+ }
+ continue;
+ }
+ #endif
+ (++end_optimum_ptr)->cost = MC_INFINITE_COST;
+ }
+ }
+
+ /* Consider coding a literal.
+
+ * To avoid an extra unpredictable brench, actually checking the
+ * preferability of coding a literal is integrated into the
+ * queue update code below. */
+ literal = *window_ptr++;
+ cost = cur_optimum_ptr->cost + lzx_literal_cost(literal, &c->costs);
+
+ /* Advance to the next position. */
+ cur_optimum_ptr++;
+
+ /* The lowest-cost path to the current position is now known.
+ * Finalize the recent offsets queue that results from taking
+ * this lowest-cost path. */
+
+ if (cost < cur_optimum_ptr->cost) {
+ /* Literal: queue remains unchanged. */
+ cur_optimum_ptr->cost = cost;
+ cur_optimum_ptr->mc_item_data = (literal << MC_OFFSET_SHIFT) | 1;
+ cur_optimum_ptr->queue = (cur_optimum_ptr - 1)->queue;
+ } else {
+ /* Match: queue update is needed. */
+ len = cur_optimum_ptr->mc_item_data & MC_LEN_MASK;
+ offset_data = cur_optimum_ptr->mc_item_data >> MC_OFFSET_SHIFT;
+ if (offset_data >= LZX_NUM_RECENT_OFFSETS) {
+ /* Explicit offset match: offset is inserted at front */
+ cur_optimum_ptr->queue.R[0] = offset_data - LZX_OFFSET_OFFSET;
+ cur_optimum_ptr->queue.R[1] = (cur_optimum_ptr - len)->queue.R[0];
+ cur_optimum_ptr->queue.R[2] = (cur_optimum_ptr - len)->queue.R[1];
+ } else {
+ /* Repeat offset match: offset is swapped to front */
+ cur_optimum_ptr->queue = (cur_optimum_ptr - len)->queue;
+ swap(cur_optimum_ptr->queue.R[0],
+ cur_optimum_ptr->queue.R[offset_data]);
+ }
+ }
+
+ /*
+ * This loop will terminate when either of the following
+ * conditions is true:
+ *
+ * (1) cur_optimum_ptr == end_optimum_ptr
+ *
+ * There are no paths that extend beyond the current
+ * position. In this case, any path to a later position
+ * must pass through the current position, so we can go
+ * ahead and choose the list of items that led to this
+ * position.
+ *
+ * (2) cur_optimum_ptr == &c->optimum[LZX_OPTIM_ARRAY_LENGTH]
+ *
+ * This bounds the number of times the algorithm can step
+ * forward before it is guaranteed to start choosing items.
+ * This limits the memory usage. But
+ * LZX_OPTIM_ARRAY_LENGTH is high enough that on most
+ * inputs this limit is never reached.
+ *
+ * Note: no check for end-of-block is needed because
+ * end-of-block will trigger condition (1).
+ */
+ if (cur_optimum_ptr == end_optimum_ptr ||
+ cur_optimum_ptr == &c->optimum[LZX_OPTIM_ARRAY_LENGTH])
+ {
+ begin_queue = &cur_optimum_ptr->queue;
+ break;
+ }
+ }
+
+ /* Choose the current list of items that constitute the minimum-cost
+ * path to the current position. */
+ lzx_declare_item_list(c, cur_optimum_ptr, next_chosen_item);
+ goto begin;