+ const u8 *window_ptr;
+ const u8 *window_end;
+ struct lzms_mc_pos_data *cur_optimum_ptr;
+ struct lzms_mc_pos_data *end_optimum_ptr;
+ u32 num_matches;
+ u32 longest_len;
+ u32 rep_max_len;
+ unsigned rep_max_idx;
+ unsigned literal;
+ unsigned i;
+ u32 cost;
+ u32 len;
+ u32 offset_data;
+
+ window_ptr = c->cur_window;
+ window_end = window_ptr + c->cur_window_size;
+
+ lzms_init_adaptive_state(&c->optimum[0].state);
+
+begin:
+ /* Start building a new list of items, which will correspond to the next
+ * piece of the overall minimum-cost path. */
+
+ cur_optimum_ptr = c->optimum;
+ cur_optimum_ptr->cost = 0;
+ end_optimum_ptr = cur_optimum_ptr;
+
+ /* States should currently be consistent with the encoders. */
+ LZMS_ASSERT(cur_optimum_ptr->state.main_state == c->main_range_encoder.state);
+ LZMS_ASSERT(cur_optimum_ptr->state.match_state == c->match_range_encoder.state);
+ LZMS_ASSERT(cur_optimum_ptr->state.lz_match_state == c->lz_match_range_encoder.state);
+ for (i = 0; i < LZMS_NUM_RECENT_OFFSETS - 1; i++)
+ LZMS_ASSERT(cur_optimum_ptr->state.lz_repeat_match_state[i] ==
+ c->lz_repeat_match_range_encoders[i].state);
+
+ if (window_ptr == window_end)
+ return;
+
+ /* 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 = lz_mf_get_matches(c->mf, 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).
+ */
+ if (likely(window_ptr - c->cur_window >= LZMS_MAX_INIT_RECENT_OFFSET)) {
+ BUILD_BUG_ON(LZMS_NUM_RECENT_OFFSETS != 3);
+ rep_max_len = lz_repsearch3(window_ptr,
+ window_end - window_ptr,
+ cur_optimum_ptr->state.lru.recent_offsets,
+ &rep_max_idx);
+ } else {
+ rep_max_len = 0;
+ }
+
+ 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) {
+
+ lz_mf_skip_positions(c->mf, rep_max_len - 1);
+ window_ptr += rep_max_len;
+
+ if (cur_optimum_ptr != c->optimum)
+ lzms_encode_item_list(c, cur_optimum_ptr);
+
+ lzms_encode_lz_repeat_offset_match(c, rep_max_len,
+ rep_max_idx);
+
+ c->optimum[0].state = cur_optimum_ptr->state;
+
+ lzms_update_main_state(&c->optimum[0].state, 1);
+ lzms_update_match_state(&c->optimum[0].state, 0);
+ lzms_update_lz_match_state(&c->optimum[0].state, 1);
+ lzms_update_lz_repeat_match_state(&c->optimum[0].state,
+ rep_max_idx);
+
+ c->optimum[0].state.lru.upcoming_offset =
+ c->optimum[0].state.lru.recent_offsets[rep_max_idx];
+
+ for (i = rep_max_idx; i < LZMS_NUM_RECENT_OFFSETS; i++)
+ c->optimum[0].state.lru.recent_offsets[i] =
+ c->optimum[0].state.lru.recent_offsets[i + 1];
+
+ lzms_update_lz_lru_queue(&c->optimum[0].state.lru);
+ goto begin;
+ }
+
+ /* 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. */
+ lzms_consider_lz_repeat_offset_match(c, cur_optimum_ptr,
+ rep_max_len, rep_max_idx);
+ }
+
+ longest_len = c->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) {
+
+ lz_mf_skip_positions(c->mf, longest_len - 1);
+ window_ptr += longest_len;
+
+ if (cur_optimum_ptr != c->optimum)
+ lzms_encode_item_list(c, cur_optimum_ptr);