+ /* Literal */
+ if (end_node < cur_node + 1)
+ (++end_node)->cost = INFINITE_COST;
+ const u32 cur_and_lit_cost = cur_node->cost +
+ lzms_literal_cost(c, cur_node->state.main_state,
+ *in_next);
+ if (cur_and_lit_cost < (cur_node + 1)->cost) {
+ (cur_node + 1)->cost = cur_and_lit_cost;
+ (cur_node + 1)->item = (struct lzms_item) {
+ .length = 1,
+ .source = *in_next,
+ };
+ (cur_node + 1)->num_extra_items = 0;
+ } else if (c->try_lit_lzrep0 && in_end - (in_next + 1) >= 2) {
+ /* try lit + LZ-rep0 */
+ const u32 offset =
+ (cur_node->state.prev_lz_offset) ?
+ cur_node->state.prev_lz_offset :
+ cur_node->state.recent_lz_offsets[0];
+
+ if (load_u16_unaligned(in_next + 1) ==
+ load_u16_unaligned(in_next + 1 - offset))
+ {
+ const u32 rep0_len = lz_extend(in_next + 1,
+ in_next + 1 - offset,
+ 2,
+ min(in_end - (in_next + 1),
+ c->mf.nice_match_len));
+
+ unsigned main_state = cur_node->state.main_state;
+
+ /* Update main_state after literal */
+ main_state = (main_state << 1 | 0) % LZMS_NUM_MAIN_PROBS;
+
+ /* Add cost of LZ-rep0 */
+ const u32 cost = cur_and_lit_cost +
+ lzms_bit_1_cost(main_state, c->probs.main) +
+ lzms_bit_0_cost(cur_node->state.match_state,
+ c->probs.match) +
+ lzms_bit_1_cost(cur_node->state.lz_state,
+ c->probs.lz) +
+ lzms_bit_0_cost(cur_node->state.lz_rep_states[0],
+ c->probs.lz_rep[0]) +
+ lzms_fast_length_cost(c, rep0_len);
+
+ const u32 total_len = 1 + rep0_len;
+
+ while (end_node < cur_node + total_len)
+ (++end_node)->cost = INFINITE_COST;
+
+ if (cost < (cur_node + total_len)->cost) {
+ (cur_node + total_len)->cost = cost;
+ (cur_node + total_len)->item = (struct lzms_item) {
+ .length = rep0_len,
+ .source = 0,
+ };
+ (cur_node + total_len)->extra_items[0] = (struct lzms_item) {
+ .length = 1,
+ .source = *in_next,
+ };
+ (cur_node + total_len)->num_extra_items = 1;
+ }
+ }
+ }
+
+ /* Advance to the next position. */
+ in_next++;
+ cur_node++;
+
+ /* The lowest-cost path to the current position is now known.
+ * Finalize the adaptive state that results from taking this
+ * lowest-cost path. */
+ struct lzms_item item_to_take = cur_node->item;
+ struct lzms_optimum_node *source_node = cur_node - item_to_take.length;
+ int next_item_idx = -1;
+ for (unsigned i = 0; i < cur_node->num_extra_items; i++) {
+ item_to_take = cur_node->extra_items[i];
+ source_node -= item_to_take.length;
+ next_item_idx++;
+ }
+ cur_node->state = source_node->state;
+ for (;;) {
+ const u32 length = item_to_take.length;
+ u32 source = item_to_take.source;
+
+ cur_node->state.upcoming_lz_offset = 0;
+ cur_node->state.upcoming_delta_pair = 0;
+ if (length > 1) {
+ /* Match */
+
+ lzms_update_main_state(&cur_node->state, 1);
+
+ if (source & DELTA_SOURCE_TAG) {
+ /* Delta match */
+
+ lzms_update_match_state(&cur_node->state, 1);
+ source &= ~DELTA_SOURCE_TAG;
+
+ if (source >= LZMS_NUM_DELTA_REPS) {
+ /* Explicit offset delta match */
+ lzms_update_delta_state(&cur_node->state, 0);
+ cur_node->state.upcoming_delta_pair =
+ source - (LZMS_NUM_DELTA_REPS - 1);
+ } else {
+ /* Repeat offset delta match */
+ int rep_idx = source;
+
+ lzms_update_delta_state(&cur_node->state, 1);
+ lzms_update_delta_rep_states(&cur_node->state, rep_idx);
+
+ cur_node->state.upcoming_delta_pair =
+ cur_node->state.recent_delta_pairs[rep_idx];
+
+ for (int i = rep_idx; i < LZMS_NUM_DELTA_REPS; i++)
+ cur_node->state.recent_delta_pairs[i] =
+ cur_node->state.recent_delta_pairs[i + 1];
+ }
+ } else {
+ lzms_update_match_state(&cur_node->state, 0);
+
+ if (source >= LZMS_NUM_LZ_REPS) {
+ /* Explicit offset LZ match */
+ lzms_update_lz_state(&cur_node->state, 0);
+ cur_node->state.upcoming_lz_offset =
+ source - (LZMS_NUM_LZ_REPS - 1);
+ } else {
+ /* Repeat offset LZ match */
+ int rep_idx = source;
+
+ lzms_update_lz_state(&cur_node->state, 1);
+ lzms_update_lz_rep_states(&cur_node->state, rep_idx);
+
+ cur_node->state.upcoming_lz_offset =
+ cur_node->state.recent_lz_offsets[rep_idx];
+
+ for (int i = rep_idx; i < LZMS_NUM_LZ_REPS; i++)
+ cur_node->state.recent_lz_offsets[i] =
+ cur_node->state.recent_lz_offsets[i + 1];
+ }
+ }
+ } else {
+ /* Literal */
+ lzms_update_main_state(&cur_node->state, 0);
+ }
+
+ lzms_update_lru_queues(&cur_node->state);
+
+ if (next_item_idx < 0)
+ break;
+ if (next_item_idx == 0)
+ item_to_take = cur_node->item;
+ else
+ item_to_take = cur_node->extra_items[next_item_idx - 1];
+ --next_item_idx;
+ }