+ } while (--num_passes_remaining);
+
+ /* Return the number of items chosen. */
+ return next_chosen_item - c->chosen_items;
+}
+
+/* Lazy parsing */
+static u32
+xpress_choose_lazy_items(struct xpress_compressor *c)
+{
+ const u8 *window_ptr = c->cur_window;
+ const u8 *window_end = &c->cur_window[c->cur_window_size];
+ struct xpress_item *next_chosen_item = c->chosen_items;
+ u32 len_3_too_far;
+ struct lz_mf *mf = c->mf;
+ struct lz_match *matches = c->cached_matches;
+ unsigned num_matches;
+ struct lz_match prev_match;
+
+ if (c->cur_window_size <= 8192)
+ len_3_too_far = 2048;
+ else
+ len_3_too_far = 4096;
+
+ do {
+ /* Don't have match at previous position */
+
+ num_matches = lz_mf_get_matches(mf, matches);
+ window_ptr++;
+
+ if (num_matches == 0 ||
+ (matches[num_matches - 1].len == 3 &&
+ matches[num_matches - 1].offset >= len_3_too_far))
+ {
+ /* No matches found => output literal */
+ xpress_declare_literal(c, *(window_ptr - 1),
+ &next_chosen_item);
+ continue;
+ }
+
+ prev_match = matches[num_matches - 1];
+
+ have_prev_match:
+ /* Have match at previous position */
+
+ if (prev_match.len >= c->params.nice_match_length) {
+ /* Very long match found => output immediately */
+ xpress_declare_match(c, prev_match.len,
+ prev_match.offset,
+ &next_chosen_item);
+ lz_mf_skip_positions(mf, prev_match.len - 1);
+ window_ptr += prev_match.len - 1;
+ continue;
+ }
+
+ num_matches = lz_mf_get_matches(mf, matches);
+ window_ptr++;
+
+ if (num_matches == 0 ||
+ (matches[num_matches - 1].len <= prev_match.len))
+ {
+ /* Next match is not longer => output previous match */
+ xpress_declare_match(c, prev_match.len,
+ prev_match.offset,
+ &next_chosen_item);
+ lz_mf_skip_positions(mf, prev_match.len - 2);
+ window_ptr += prev_match.len - 2;
+ continue;
+ }
+
+ /* Next match is longer => output literal */
+
+ xpress_declare_literal(c, *(window_ptr - 2), &next_chosen_item);
+
+ prev_match = matches[num_matches - 1];
+
+ goto have_prev_match;
+
+ } while (window_ptr != window_end);
+
+ return next_chosen_item - c->chosen_items;
+}
+
+/* Greedy parsing */
+static u32
+xpress_choose_greedy_items(struct xpress_compressor *c)
+{
+ const u8 *window_ptr = c->cur_window;
+ const u8 *window_end = &c->cur_window[c->cur_window_size];
+ struct xpress_item *next_chosen_item = c->chosen_items;
+ u32 len_3_too_far;
+ struct lz_mf *mf = c->mf;
+ struct lz_match *matches = c->cached_matches;
+ unsigned num_matches;
+
+ if (c->cur_window_size <= 8192)
+ len_3_too_far = 2048;
+ else
+ len_3_too_far = 4096;
+
+ do {
+ /* Get longest match at the current position. */
+ num_matches = lz_mf_get_matches(mf, matches);
+
+ if (num_matches == 0 ||
+ (matches[num_matches - 1].len == 3 &&
+ matches[num_matches - 1].offset >= len_3_too_far))
+ {
+ /* No match, or length 3 match with large offset.
+ * Choose a literal. */
+ xpress_declare_literal(c, *window_ptr, &next_chosen_item);
+ window_ptr += 1;
+ } else {
+ /* Match found. Choose it. */
+ unsigned len = matches[num_matches - 1].len;
+ unsigned offset = matches[num_matches - 1].offset;
+
+ xpress_declare_match(c, len, offset, &next_chosen_item);
+ lz_mf_skip_positions(mf, len - 1);
+ window_ptr += len;
+ }
+ } while (window_ptr != window_end);
+
+ return next_chosen_item - c->chosen_items;
+}
+
+/* Literals-only parsing */
+static u32
+xpress_choose_literals(struct xpress_compressor *c)
+{
+ const u8 *window_ptr = c->cur_window;
+ const u8 *window_end = &c->cur_window[c->cur_window_size];
+ struct xpress_item *next_chosen_item = c->chosen_items;
+
+ do {
+ xpress_declare_literal(c, *window_ptr++, &next_chosen_item);
+ } while (window_ptr != window_end);
+
+ return next_chosen_item - c->chosen_items;
+}
+
+/*
+ * 'choose_items_func' is provided a data buffer c->cur_window of length
+ * c->cur_window_size bytes. This data buffer will have already been loaded
+ * into the match-finder c->mf. 'choose_items_func' must choose the
+ * match/literal sequence to output to represent this data buffer. The
+ * intermediate representation of this match/literal sequence must be recorded
+ * in c->chosen_items, and the Huffman symbols used must be tallied in c->freqs.
+ * The return value must be the number of items written to c->chosen_items.
+ */
+static u32
+xpress_choose_items(struct xpress_compressor *c)
+{
+ return (*c->params.choose_items_func)(c);
+}
+
+/* Set internal compression parameters for the specified compression level and
+ * maximum window size. */
+static void
+xpress_build_params(unsigned int compression_level, u32 max_window_size,
+ struct xpress_compressor_params *xpress_params)
+{
+ memset(xpress_params, 0, sizeof(*xpress_params));
+ xpress_params->num_optim_passes = 1;
+
+ if (compression_level == 1) {
+
+ /* Literal-only parsing */
+ xpress_params->choose_items_func = xpress_choose_literals;
+ xpress_params->mf_algo = LZ_MF_NULL;
+
+ } else if (compression_level < 30) {
+
+ /* Greedy parsing */
+ xpress_params->choose_items_func = xpress_choose_greedy_items;
+ xpress_params->mf_algo = LZ_MF_HASH_CHAINS;
+ xpress_params->nice_match_length = compression_level;
+ xpress_params->max_search_depth = compression_level / 2;
+
+ } else if (compression_level < 60) {
+
+ /* Lazy parsing */
+ xpress_params->choose_items_func = xpress_choose_lazy_items;
+ xpress_params->mf_algo = LZ_MF_HASH_CHAINS;
+ xpress_params->nice_match_length = compression_level;
+ xpress_params->max_search_depth = compression_level / 2;
+
+ } else {
+
+ /* Near-optimal parsing */
+ xpress_params->choose_items_func = xpress_choose_near_optimal_items;
+ if (max_window_size >= 16384)
+ xpress_params->mf_algo = LZ_MF_BINARY_TREES;
+ else
+ xpress_params->mf_algo = LZ_MF_HASH_CHAINS;
+ xpress_params->num_optim_passes = compression_level / 40;
+ xpress_params->nice_match_length = min(compression_level / 2,
+ XPRESS_MAX_MATCH_LEN);
+ xpress_params->max_search_depth = min(compression_level,
+ XPRESS_MAX_MATCH_LEN);