- 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]);
- }