+/*
+ * Find a new minimum cost path through the graph of possible match/literal
+ * choices. We find the minimum cost path from 'c->optimum_nodes[0]', which
+ * represents the node at the beginning of the input buffer, to
+ * 'c->optimum_nodes[in_nbytes]', which represents the node at the end of the
+ * input buffer. Edge costs are evaluated using the cost model 'c->costs'.
+ *
+ * The algorithm works backward, starting at 'c->optimum_nodes[in_nbytes]' and
+ * proceeding backwards one position at a time. At each position, the minimum
+ * cost to reach 'c->optimum_nodes[in_nbytes]' from that position is computed
+ * and the match/literal choice is saved.
+ */
+static void
+xpress_find_min_cost_path(struct xpress_compressor *c, size_t in_nbytes,
+ struct lz_match *end_cache_ptr)
+{
+ struct xpress_optimum_node *cur_optimum_ptr = c->optimum_nodes + in_nbytes;
+ struct lz_match *cache_ptr = end_cache_ptr;
+
+ cur_optimum_ptr->cost_to_end = 0;
+ do {
+ unsigned literal;
+ u32 best_item;
+ u32 best_cost_to_end;
+ unsigned num_matches;
+ struct lz_match *match;
+ unsigned len;
+
+ cur_optimum_ptr--;
+ cache_ptr--;
+
+ literal = cache_ptr->offset;
+
+ /* Consider coding a literal. */
+ best_item = ((u32)literal << OPTIMUM_OFFSET_SHIFT) | 1;
+ best_cost_to_end = c->costs[literal] +
+ (cur_optimum_ptr + 1)->cost_to_end;
+
+ num_matches = cache_ptr->length;
+
+ if (num_matches == 0) {
+ /* No matches; the only choice is the literal. */
+ cur_optimum_ptr->cost_to_end = best_cost_to_end;
+ cur_optimum_ptr->item = best_item;
+ continue;
+ }
+
+ /*
+ * Consider each match length from the minimum
+ * (XPRESS_MIN_MATCH_LEN) to the length of the longest match
+ * found at this position. For each length, consider only the
+ * smallest offset for which that length is available. Although
+ * this is not guaranteed to be optimal due to the possibility
+ * of a larger offset costing less than a smaller offset to
+ * code, this is a very useful heuristic.
+ */
+ match = cache_ptr - num_matches;
+ len = XPRESS_MIN_MATCH_LEN;
+ if (cache_ptr[-1].length < 0xF + XPRESS_MIN_MATCH_LEN) {
+ /* All lengths are small. Optimize accordingly. */
+ do {
+ unsigned offset;
+ unsigned offset_high_bit;
+ u32 offset_cost;
+
+ offset = match->offset;
+ offset_high_bit = fls32(offset);
+ offset_cost = offset_high_bit;
+ do {
+ unsigned len_hdr;
+ unsigned sym;
+ u32 cost_to_end;
+
+ len_hdr = len - XPRESS_MIN_MATCH_LEN;
+ sym = XPRESS_NUM_CHARS +
+ ((offset_high_bit << 4) | len_hdr);
+ cost_to_end =
+ offset_cost + c->costs[sym] +
+ (cur_optimum_ptr + len)->cost_to_end;
+ if (cost_to_end < best_cost_to_end) {
+ best_cost_to_end = cost_to_end;
+ best_item =
+ ((u32)offset <<
+ OPTIMUM_OFFSET_SHIFT) | len;
+ }
+ } while (++len <= match->length);
+ } while (++match != cache_ptr);
+ } else {
+ /* Some lengths are big. */
+ do {
+ unsigned offset;
+ unsigned offset_high_bit;
+ u32 offset_cost;
+
+ offset = match->offset;
+ offset_high_bit = fls32(offset);
+ offset_cost = offset_high_bit;
+ do {
+ unsigned adjusted_len;
+ unsigned len_hdr;
+ unsigned sym;
+ u32 cost_to_end;
+
+ adjusted_len = len - XPRESS_MIN_MATCH_LEN;
+ len_hdr = min(adjusted_len, 0xF);
+ sym = XPRESS_NUM_CHARS +
+ ((offset_high_bit << 4) | len_hdr);
+ cost_to_end =
+ offset_cost + c->costs[sym] +
+ (cur_optimum_ptr + len)->cost_to_end;
+ if (adjusted_len >= 0xF) {
+ cost_to_end += 8;
+ if (adjusted_len - 0xF >= 0xFF)
+ cost_to_end += 16;
+ }
+ if (cost_to_end < best_cost_to_end) {
+ best_cost_to_end = cost_to_end;
+ best_item =
+ ((u32)offset <<
+ OPTIMUM_OFFSET_SHIFT) | len;
+ }
+ } while (++len <= match->length);
+ } while (++match != cache_ptr);
+ }
+ cache_ptr -= num_matches;
+ cur_optimum_ptr->cost_to_end = best_cost_to_end;
+ cur_optimum_ptr->item = best_item;
+ } while (cur_optimum_ptr != c->optimum_nodes);
+}