+lzms_skip_bytes(struct lzms_compressor *ctx, u32 n)
+{
+ lz_bt_skip_positions(&ctx->mf, n);
+}
+
+static u32
+lzms_get_literal_cost(struct lzms_compressor *ctx,
+ struct lzms_adaptive_state *state, u8 literal)
+{
+ u32 cost = 0;
+
+ state->lru.upcoming_offset = 0;
+ lzms_update_lz_lru_queues(&state->lru);
+
+ cost += lzms_rc_bit_cost(&ctx->main_range_encoder,
+ &state->main_state, 0);
+
+ cost += lzms_huffman_symbol_cost(&ctx->literal_encoder, literal);
+
+ return cost;
+}
+
+static u32
+lzms_get_lz_match_cost_nolen(struct lzms_compressor *ctx,
+ struct lzms_adaptive_state *state, u32 offset)
+{
+ u32 cost = 0;
+ int recent_offset_idx;
+
+ cost += lzms_rc_bit_cost(&ctx->main_range_encoder,
+ &state->main_state, 1);
+ cost += lzms_rc_bit_cost(&ctx->match_range_encoder,
+ &state->match_state, 0);
+
+ for (recent_offset_idx = 0;
+ recent_offset_idx < LZMS_NUM_RECENT_OFFSETS;
+ recent_offset_idx++)
+ if (offset == state->lru.recent_offsets[recent_offset_idx])
+ break;
+
+ if (recent_offset_idx == LZMS_NUM_RECENT_OFFSETS) {
+ /* Explicit offset. */
+ cost += lzms_rc_bit_cost(&ctx->lz_match_range_encoder,
+ &state->lz_match_state, 0);
+
+ cost += lzms_offset_cost(&ctx->lz_offset_encoder, offset);
+ } else {
+ int i;
+
+ /* Recent offset. */
+ cost += lzms_rc_bit_cost(&ctx->lz_match_range_encoder,
+ &state->lz_match_state, 1);
+
+ for (i = 0; i < recent_offset_idx; i++)
+ cost += lzms_rc_bit_cost(&ctx->lz_repeat_match_range_encoders[i],
+ &state->lz_repeat_match_state[i], 0);
+
+ if (i < LZMS_NUM_RECENT_OFFSETS - 1)
+ cost += lzms_rc_bit_cost(&ctx->lz_repeat_match_range_encoders[i],
+ &state->lz_repeat_match_state[i], 1);
+
+
+ /* Initial update of the LZ match offset LRU queue. */
+ for (; i < LZMS_NUM_RECENT_OFFSETS; i++)
+ state->lru.recent_offsets[i] = state->lru.recent_offsets[i + 1];
+ }
+
+
+ state->lru.upcoming_offset = offset;
+ lzms_update_lz_lru_queues(&state->lru);
+
+ return cost;
+}
+
+static u32
+lzms_get_lz_match_cost(struct lzms_compressor *ctx,
+ struct lzms_adaptive_state *state,
+ u32 length, u32 offset)
+{
+ return lzms_get_lz_match_cost_nolen(ctx, state, offset) +
+ lzms_get_length_cost(&ctx->length_encoder, length);
+}
+
+static struct raw_match
+lzms_match_chooser_reverse_list(struct lzms_compressor *ctx, unsigned cur_pos)
+{
+ unsigned prev_link, saved_prev_link;
+ unsigned prev_match_offset, saved_prev_match_offset;
+
+ ctx->optimum_end_idx = cur_pos;
+
+ saved_prev_link = ctx->optimum[cur_pos].prev.link;
+ saved_prev_match_offset = ctx->optimum[cur_pos].prev.match_offset;
+
+ do {
+ prev_link = saved_prev_link;
+ prev_match_offset = saved_prev_match_offset;
+
+ saved_prev_link = ctx->optimum[prev_link].prev.link;
+ saved_prev_match_offset = ctx->optimum[prev_link].prev.match_offset;
+
+ ctx->optimum[prev_link].next.link = cur_pos;
+ ctx->optimum[prev_link].next.match_offset = prev_match_offset;
+
+ cur_pos = prev_link;
+ } while (cur_pos != 0);
+
+ ctx->optimum_cur_idx = ctx->optimum[0].next.link;
+
+ return (struct raw_match)
+ { .len = ctx->optimum_cur_idx,
+ .offset = ctx->optimum[0].next.match_offset,
+ };
+}
+
+/* This is similar to lzx_get_near_optimal_match() in lzx-compress.c.
+ * Read that one if you want to understand it. */
+static struct raw_match
+lzms_get_near_optimal_match(struct lzms_compressor *ctx)
+{
+ u32 num_matches;
+ struct raw_match *matches;
+ struct raw_match match;
+ u32 longest_len;
+ u32 longest_rep_len;
+ u32 longest_rep_offset;
+ unsigned cur_pos;
+ unsigned end_pos;
+ struct lzms_adaptive_state initial_state;
+
+ if (ctx->optimum_cur_idx != ctx->optimum_end_idx) {
+ match.len = ctx->optimum[ctx->optimum_cur_idx].next.link -
+ ctx->optimum_cur_idx;
+ match.offset = ctx->optimum[ctx->optimum_cur_idx].next.match_offset;
+
+ ctx->optimum_cur_idx = ctx->optimum[ctx->optimum_cur_idx].next.link;
+ return match;
+ }
+
+ ctx->optimum_cur_idx = 0;
+ ctx->optimum_end_idx = 0;
+
+ longest_rep_len = ctx->params.min_match_length - 1;
+ if (lz_bt_get_position(&ctx->mf) >= LZMS_MAX_INIT_RECENT_OFFSET) {
+ u32 limit = min(ctx->params.max_match_length,
+ lz_bt_get_remaining_size(&ctx->mf));
+ for (int i = 0; i < LZMS_NUM_RECENT_OFFSETS; i++) {
+ u32 offset = ctx->lru.lz.recent_offsets[i];
+ const u8 *strptr = lz_bt_get_window_ptr(&ctx->mf);
+ const u8 *matchptr = strptr - offset;
+ u32 len = 0;
+ while (len < limit && strptr[len] == matchptr[len])
+ len++;
+ if (len > longest_rep_len) {
+ longest_rep_len = len;
+ longest_rep_offset = offset;
+ }
+ }
+ }
+
+ if (longest_rep_len >= ctx->params.nice_match_length) {
+ lzms_skip_bytes(ctx, longest_rep_len);
+ return (struct raw_match) {
+ .len = longest_rep_len,
+ .offset = longest_rep_offset,
+ };
+ }
+
+ num_matches = lzms_get_matches(ctx, &matches);
+
+ if (num_matches) {
+ longest_len = matches[num_matches - 1].len;
+ if (longest_len >= ctx->params.nice_match_length) {
+ lzms_skip_bytes(ctx, longest_len - 1);
+ return matches[num_matches - 1];
+ }
+ } else {
+ longest_len = 1;
+ }
+
+ initial_state.lru = ctx->lru.lz;
+ initial_state.main_state = ctx->main_range_encoder.state;
+ initial_state.match_state = ctx->match_range_encoder.state;
+ initial_state.lz_match_state = ctx->lz_match_range_encoder.state;
+ for (int i = 0; i < LZMS_NUM_RECENT_OFFSETS - 1; i++)
+ initial_state.lz_repeat_match_state[i] = ctx->lz_repeat_match_range_encoders[i].state;
+
+ ctx->optimum[1].state = initial_state;
+ ctx->optimum[1].cost = lzms_get_literal_cost(ctx,
+ &ctx->optimum[1].state,
+ *(lz_bt_get_window_ptr(&ctx->mf) - 1));
+ ctx->optimum[1].prev.link = 0;
+
+ for (u32 i = 0, len = 2; i < num_matches; i++) {
+ u32 offset = matches[i].offset;
+ struct lzms_adaptive_state state;
+ u32 position_cost;
+
+ state = initial_state;
+ position_cost = 0;
+ position_cost += lzms_get_lz_match_cost_nolen(ctx, &state, offset);
+
+ do {
+ u32 cost;
+
+ cost = position_cost;
+ cost += lzms_get_length_cost(&ctx->length_encoder, len);
+
+ ctx->optimum[len].state = state;
+ ctx->optimum[len].prev.link = 0;
+ ctx->optimum[len].prev.match_offset = offset;
+ ctx->optimum[len].cost = cost;
+ } while (++len <= matches[i].len);
+ }
+ end_pos = longest_len;
+
+ if (longest_rep_len >= ctx->params.min_match_length) {
+ struct lzms_adaptive_state state;
+ u32 cost;
+
+ while (end_pos < longest_rep_len)
+ ctx->optimum[++end_pos].cost = MC_INFINITE_COST;
+
+ state = initial_state;
+ cost = lzms_get_lz_match_cost(ctx,
+ &state,
+ longest_rep_len,
+ longest_rep_offset);
+ if (cost <= ctx->optimum[longest_rep_len].cost) {
+ ctx->optimum[longest_rep_len].state = state;
+ ctx->optimum[longest_rep_len].prev.link = 0;
+ ctx->optimum[longest_rep_len].prev.match_offset = longest_rep_offset;
+ ctx->optimum[longest_rep_len].cost = cost;
+ }
+ }
+
+ cur_pos = 0;
+ for (;;) {
+ u32 cost;
+ struct lzms_adaptive_state state;
+
+ cur_pos++;
+
+ if (cur_pos == end_pos || cur_pos == ctx->params.optim_array_length)
+ return lzms_match_chooser_reverse_list(ctx, cur_pos);
+
+ longest_rep_len = ctx->params.min_match_length - 1;
+ if (lz_bt_get_position(&ctx->mf) >= LZMS_MAX_INIT_RECENT_OFFSET) {
+ u32 limit = min(ctx->params.max_match_length,
+ lz_bt_get_remaining_size(&ctx->mf));
+ for (int i = 0; i < LZMS_NUM_RECENT_OFFSETS; i++) {
+ u32 offset = ctx->optimum[cur_pos].state.lru.recent_offsets[i];
+ const u8 *strptr = lz_bt_get_window_ptr(&ctx->mf);
+ const u8 *matchptr = strptr - offset;
+ u32 len = 0;
+ while (len < limit && strptr[len] == matchptr[len])
+ len++;
+ if (len > longest_rep_len) {
+ longest_rep_len = len;
+ longest_rep_offset = offset;
+ }
+ }
+ }
+
+ if (longest_rep_len >= ctx->params.nice_match_length) {
+ match = lzms_match_chooser_reverse_list(ctx, cur_pos);
+
+ ctx->optimum[cur_pos].next.match_offset = longest_rep_offset;
+ ctx->optimum[cur_pos].next.link = cur_pos + longest_rep_len;
+ ctx->optimum_end_idx = cur_pos + longest_rep_len;
+
+ lzms_skip_bytes(ctx, longest_rep_len);
+
+ return match;
+ }
+
+ num_matches = lzms_get_matches(ctx, &matches);
+
+ if (num_matches) {
+ longest_len = matches[num_matches - 1].len;
+ if (longest_len >= ctx->params.nice_match_length) {
+ match = lzms_match_chooser_reverse_list(ctx, cur_pos);
+
+ ctx->optimum[cur_pos].next.match_offset =
+ matches[num_matches - 1].offset;
+ ctx->optimum[cur_pos].next.link = cur_pos + longest_len;
+ ctx->optimum_end_idx = cur_pos + longest_len;