+
+ c->cur_window_ptr = c->cur_window;
+ window_ptr = c->cur_window;
+ window_end = window_ptr + c->cur_window_size;
+ c->cache_ptr = c->cached_matches;
+ memset(c->freqs, 0, sizeof(c->freqs));
+ next_chosen_item = c->chosen_items;
+
+ u32 unseen_cost = 9;
+ while (window_ptr != window_end) {
+ raw_item = xpress_choose_near_optimal_item(c);
+ if (raw_item.len >= XPRESS_MIN_MATCH_LEN) {
+ xpress_item = xpress_tally_match(raw_item.len,
+ raw_item.offset,
+ c->freqs);
+ window_ptr += raw_item.len;
+ } else {
+ xpress_item = xpress_tally_literal(*window_ptr,
+ c->freqs);
+ window_ptr += 1;
+ }
+ *next_chosen_item++ = xpress_item;
+
+ /* When doing one-pass near-optimal parsing, rebuild the Huffman
+ * code occasionally. */
+ if (unlikely((next_chosen_item - c->chosen_items) % 2048 == 0) &&
+ c->cur_window_size >= 16384 &&
+ c->params.num_optim_passes == 1)
+ {
+ xpress_make_huffman_code(c);
+ for (unsigned i = 0; i < XPRESS_NUM_SYMBOLS; i++)
+ c->costs[i] = c->lens[i] ? c->lens[i] : unseen_cost;
+ if (unseen_cost < 15)
+ unseen_cost++;
+ }
+ }
+ c->freqs[XPRESS_END_OF_DATA]++;
+ xpress_make_huffman_code(c);
+ return next_chosen_item - c->chosen_items;
+}
+
+/* Lazy parsing */
+static u32
+xpress_choose_items_lazy(struct xpress_compressor *c)
+{
+ struct lz_mf *mf;
+ u32 len_3_too_far;
+ const u8 *window_ptr;
+ const u8 *window_end;
+ u32 num_matches;
+ struct lz_match matches[min(c->params.nice_match_length, c->params.max_search_depth)];
+ struct xpress_item *next_chosen_item;
+ struct lz_match prev_match;
+
+ mf = c->mf;
+
+ lz_mf_load_window(mf, c->cur_window, c->cur_window_size);
+
+ if (c->cur_window_size <= 8192)
+ len_3_too_far = 2048;
+ else
+ len_3_too_far = 4096;
+
+ memset(c->freqs, 0, sizeof(c->freqs));
+
+ window_ptr = c->cur_window;
+ window_end = c->cur_window + c->cur_window_size;
+ next_chosen_item = c->chosen_items;
+
+ for (;;) {
+
+ /* 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 */
+ *next_chosen_item++ = xpress_tally_literal(*(window_ptr - 1),
+ c->freqs);
+ if (window_ptr == window_end)
+ break;
+ 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 */
+ *next_chosen_item++ = xpress_tally_match(prev_match.len,
+ prev_match.offset,
+ c->freqs);
+ lz_mf_skip_positions(mf, prev_match.len - 1);
+ window_ptr += prev_match.len - 1;
+ if (window_ptr == window_end)
+ break;
+ 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 */
+ *next_chosen_item++ = xpress_tally_match(prev_match.len,
+ prev_match.offset,
+ c->freqs);
+ lz_mf_skip_positions(mf, prev_match.len - 2);
+ window_ptr += prev_match.len - 2;
+ if (window_ptr == window_end)
+ break;
+ continue;
+ }
+
+ /* Next match is longer => output literal */
+
+ *next_chosen_item++ = xpress_tally_literal(*(window_ptr - 2),
+ c->freqs);
+
+ prev_match = matches[num_matches - 1];
+
+ goto have_prev_match;
+ }
+
+ c->freqs[XPRESS_END_OF_DATA]++;
+ xpress_make_huffman_code(c);
+ return next_chosen_item - c->chosen_items;
+}
+
+/* Greedy parsing */
+static u32
+xpress_choose_items_greedy(struct xpress_compressor *c)
+{
+ struct lz_mf *mf;
+ u32 len_3_too_far;
+ const u8 *window_ptr;
+ const u8 *window_end;
+ struct lz_match matches[min(c->params.nice_match_length, c->params.max_search_depth)];
+ u32 num_matches;
+ struct xpress_item *next_chosen_item;
+
+ mf = c->mf;
+
+ lz_mf_load_window(mf, c->cur_window, c->cur_window_size);
+
+ if (c->cur_window_size <= 8192)
+ len_3_too_far = 2048;
+ else
+ len_3_too_far = 4096;
+
+ memset(c->freqs, 0, sizeof(c->freqs));
+
+ window_ptr = c->cur_window;
+ window_end = c->cur_window + c->cur_window_size;
+ next_chosen_item = c->chosen_items;
+
+ 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))
+ {
+ *next_chosen_item++ = xpress_tally_literal(*window_ptr, c->freqs);
+ window_ptr += 1;
+ } else {
+ u32 len = matches[num_matches - 1].len;
+ u32 offset = matches[num_matches - 1].offset;
+
+ *next_chosen_item++ = xpress_tally_match(len, offset, c->freqs);
+ lz_mf_skip_positions(mf, len - 1);
+ window_ptr += len;
+ }
+ } while (window_ptr != window_end);
+
+ c->freqs[XPRESS_END_OF_DATA]++;
+ xpress_make_huffman_code(c);
+ return next_chosen_item - c->chosen_items;
+}
+
+/* Huffman-only parsing */
+static u32
+xpress_choose_items_huffonly(struct xpress_compressor *c)
+{
+ const u8 *window_ptr;
+ const u8 *window_end;
+ struct xpress_item *next_chosen_item;
+
+ memset(c->freqs, 0, sizeof(c->freqs));
+
+ window_ptr = c->cur_window;
+ window_end = c->cur_window + c->cur_window_size;
+ next_chosen_item = c->chosen_items;
+
+ do {
+ *next_chosen_item++ = xpress_tally_literal(*window_ptr++, c->freqs);
+ } while (window_ptr != window_end);
+
+ c->freqs[XPRESS_END_OF_DATA]++;
+ xpress_make_huffman_code(c);
+ return next_chosen_item - c->chosen_items;
+}
+
+/* Given the specified compression level and maximum window size, build the
+ * parameters to use for XPRESS compression. */
+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));
+
+ if (compression_level == 1) {
+
+ /* Huffman only (no Lempel-Ziv matches) */
+ xpress_params->mf_algo = LZ_MF_NULL;
+ xpress_params->choose_items_func = xpress_choose_items_huffonly;
+
+ } else if (compression_level < 30) {
+
+ /* Greedy parsing */
+ xpress_params->mf_algo = LZ_MF_HASH_CHAINS;
+ xpress_params->choose_items_func = xpress_choose_items_greedy;
+ xpress_params->nice_match_length = compression_level;
+ xpress_params->max_search_depth = compression_level / 2;
+
+ } else if (compression_level < 60) {
+
+ /* Lazy parsing */
+ xpress_params->mf_algo = LZ_MF_HASH_CHAINS;
+ xpress_params->choose_items_func = xpress_choose_items_lazy;
+ 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_items_near_optimal;
+ 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);
+ }
+}
+
+/* Given the specified XPRESS parameters and maximum window size, build the
+ * parameters to use for match-finding. */
+static void
+xpress_build_mf_params(const struct xpress_compressor_params *xpress_params,
+ u32 max_window_size, struct lz_mf_params *mf_params)
+{
+ memset(mf_params, 0, sizeof(*mf_params));
+
+ mf_params->algorithm = xpress_params->mf_algo;
+ mf_params->max_window_size = max_window_size;
+ mf_params->min_match_len = XPRESS_MIN_MATCH_LEN;
+ mf_params->max_match_len = XPRESS_MAX_MATCH_LEN;
+ mf_params->max_search_depth = xpress_params->max_search_depth;
+ mf_params->nice_match_len = xpress_params->nice_match_length;
+}
+
+static void
+xpress_free_compressor(void *_c);
+
+static u64
+xpress_get_needed_memory(size_t max_window_size, unsigned int compression_level)
+{
+ u64 size = 0;
+ struct xpress_compressor_params params;
+
+ if (max_window_size > XPRESS_MAX_OFFSET + 1)
+ return 0;
+
+ xpress_build_params(compression_level, max_window_size, ¶ms);
+
+ size += sizeof(struct xpress_compressor);
+
+ size += lz_mf_get_needed_memory(params.mf_algo, max_window_size);
+
+ if (params.choose_items_func == xpress_choose_items_near_optimal) {
+ size += (XPRESS_OPTIM_ARRAY_LENGTH + params.nice_match_length) *
+ sizeof(struct xpress_mc_pos_data);
+ if (params.num_optim_passes > 1) {
+ size_t cache_len = max(max_window_size * XPRESS_CACHE_PER_POS,
+ params.max_search_depth + 1);
+ size += cache_len * sizeof(struct lz_match);
+ } else {
+ size += params.max_search_depth * sizeof(struct lz_match);
+ }
+ }
+
+ size += max_window_size * sizeof(struct xpress_item);
+
+ return size;
+}
+
+static int
+xpress_create_compressor(size_t max_window_size, unsigned int compression_level,
+ void **c_ret)
+{
+ struct xpress_compressor *c;
+ struct xpress_compressor_params params;
+ struct lz_mf_params mf_params;
+
+ if (max_window_size > XPRESS_MAX_OFFSET + 1)
+ return WIMLIB_ERR_INVALID_PARAM;
+
+ xpress_build_params(compression_level, max_window_size, ¶ms);
+ xpress_build_mf_params(¶ms, max_window_size, &mf_params);
+
+ c = CALLOC(1, sizeof(struct xpress_compressor));
+ if (!c)
+ goto oom;
+
+ c->params = params;
+
+ c->mf = lz_mf_alloc(&mf_params);
+ if (!c->mf)
+ goto oom;
+
+ if (params.choose_items_func == xpress_choose_items_near_optimal) {
+ c->optimum = MALLOC((XPRESS_OPTIM_ARRAY_LENGTH +
+ params.nice_match_length) *
+ sizeof(struct xpress_mc_pos_data));
+ if (!c->optimum)
+ goto oom;
+ if (params.num_optim_passes > 1) {
+ size_t cache_len = max(max_window_size * XPRESS_CACHE_PER_POS,
+ params.max_search_depth + 1);
+ c->cached_matches = MALLOC(cache_len * sizeof(struct lz_match));
+ if (!c->cached_matches)
+ goto oom;
+ c->cache_limit = c->cached_matches + cache_len -
+ (params.max_search_depth + 1);
+ } else {
+ c->cached_matches = MALLOC(params.max_search_depth *
+ sizeof(struct lz_match));
+ if (!c->cached_matches)
+ goto oom;
+ }
+ }
+
+ c->chosen_items = MALLOC(max_window_size * sizeof(struct xpress_item));
+ if (!c->chosen_items)
+ goto oom;
+
+ *c_ret = c;