+#define XPRESS_CACHE_PER_POS 8
+#define XPRESS_OPTIM_ARRAY_LENGTH 4096
+
+struct xpress_compressor;
+struct xpress_item;
+struct xpress_mc_pos_data;
+
+struct xpress_compressor_params {
+
+ /* Only used when choose_items_func == xpress_choose_items_near_optimal */
+ u32 num_optim_passes;
+
+ /* Given the data to compress (c->cur_window, c->cur_window_size),
+ * 'choose_items_func' fills in c->chosen_items with the intermediate
+ * representation of the match/literal sequence to output. Also fills
+ * in c->codewords and c->lens to provide the Huffman code with which
+ * these items should be output.
+ *
+ * Returns the number of items written to c->chosen_items. This can be
+ * at most c->cur_window_size. (The worst case is all literals, no
+ * matches.) */
+ u32 (*choose_items_func)(struct xpress_compressor *c);
+
+ /* Match-finding algorithm and parameters */
+ enum lz_mf_algo mf_algo;
+ u32 max_search_depth;
+ u32 nice_match_length;
+};
+
+/* XPRESS compressor state. */
+struct xpress_compressor {
+
+ /* Parameters determined based on the compression level. */
+ struct xpress_compressor_params params;
+
+ /* Lempel-Ziv match-finder */
+ struct lz_mf *mf;
+
+ /* Optimal parsing data */
+ unsigned (*get_matches_func)(struct xpress_compressor *,
+ const struct lz_match **);
+ void (*skip_bytes_func)(struct xpress_compressor *, u32 n);
+ const u8 *cur_window_ptr;
+ struct lz_match *cached_matches;
+ struct lz_match *cache_ptr;
+ struct lz_match *cache_limit;
+ struct xpress_mc_pos_data *optimum;
+ unsigned optimum_cur_idx;
+ unsigned optimum_end_idx;
+ u8 costs[XPRESS_NUM_SYMBOLS];
+
+ /* The selected sequence of matches/literals */
+ struct xpress_item *chosen_items;
+
+ /* Data currently being compressed */
+ const u8 *cur_window;
+ u32 cur_window_size;
+
+ /* Symbol frequency counters */
+ u32 freqs[XPRESS_NUM_SYMBOLS];
+
+ /* The current Huffman code */
+ u32 codewords[XPRESS_NUM_SYMBOLS];
+ u8 lens[XPRESS_NUM_SYMBOLS];
+};
+
+/* Match-chooser position data.
+ * See corresponding declaration in lzx-compress.c for more information. */
+struct xpress_mc_pos_data {
+ u32 cost;
+#define MC_INFINITE_COST ((u32)~0UL)
+
+ union {
+ struct {
+ u32 link;
+ u32 match_offset;
+ } prev;
+ struct {
+ u32 link;
+ u32 match_offset;
+ } next;
+ };
+};
+
+/* Intermediate XPRESS match/literal representation. */
+struct xpress_item {
+ u16 adjusted_len; /* Match length minus XPRESS_MIN_MATCH_LEN */
+ u16 offset; /* Match offset */
+ /* For literals, offset == 0 and adjusted_len is the literal byte. */
+};
+
+/* Output an XPRESS match. */
+static void
+xpress_write_match(struct xpress_item match, struct output_bitstream *ostream,
+ const u32 codewords[], const u8 lens[])
+{
+ unsigned len_hdr = min(match.adjusted_len, 0xf);
+ unsigned offset_bsr = bsr32(match.offset);
+ unsigned sym = XPRESS_NUM_CHARS + ((offset_bsr << 4) | len_hdr);
+
+ /* Huffman symbol */
+ bitstream_put_bits(ostream, codewords[sym], lens[sym]);
+
+ /* If length >= 18, one extra length byte.
+ * If length >= 273, three (total) extra length bytes. */
+ if (match.adjusted_len >= 0xf) {
+ u8 byte1 = min(match.adjusted_len - 0xf, 0xff);
+ bitstream_put_byte(ostream, byte1);
+ if (byte1 == 0xff) {
+ bitstream_put_byte(ostream, match.adjusted_len & 0xff);
+ bitstream_put_byte(ostream, match.adjusted_len >> 8);
+ }
+ }
+
+ /* Offset bits */
+ bitstream_put_bits(ostream, match.offset ^ (1U << offset_bsr), offset_bsr);
+}
+
+/* Output a sequence of XPRESS matches and literals. */
+static void
+xpress_write_items(struct output_bitstream *ostream,
+ const struct xpress_item items[], u32 num_items,
+ const u32 codewords[], const u8 lens[])
+{
+ for (u32 i = 0; i < num_items; i++) {
+ if (items[i].offset) {
+ /* Match */
+ xpress_write_match(items[i], ostream, codewords, lens);
+ } else {
+ /* Literal */
+ unsigned lit = items[i].adjusted_len;
+ bitstream_put_bits(ostream, codewords[lit], lens[lit]);
+ }
+ }
+ /* End-of-data symbol (required for MS compatibility) */
+ bitstream_put_bits(ostream, codewords[XPRESS_END_OF_DATA], lens[XPRESS_END_OF_DATA]);
+}
+
+/* Make the Huffman code for XPRESS.
+ *
+ * Takes as input c->freqs and produces as output c->lens and c->codewords. */
+static void
+xpress_make_huffman_code(struct xpress_compressor *c)
+{
+ make_canonical_huffman_code(XPRESS_NUM_SYMBOLS, XPRESS_MAX_CODEWORD_LEN,
+ c->freqs, c->lens, c->codewords);
+}
+
+/* Account for the Huffman symbol that would be produced by outputting the
+ * specified literal. Returns the intermediate representation of the literal.
+ */
+static inline struct xpress_item
+xpress_tally_literal(u8 lit, u32 freqs[])
+{
+ freqs[lit]++;
+ return (struct xpress_item) { .offset = 0, .adjusted_len = lit };
+}
+
+/* Account for the Huffman symbol that would be produced by outputting the
+ * specified match. Returns the intermediate representation of the match. */
+static inline struct xpress_item
+xpress_tally_match(u32 len, u32 offset, u32 freqs[])
+{
+ u32 adjusted_len = len - XPRESS_MIN_MATCH_LEN;
+ unsigned len_hdr = min(adjusted_len, 0xf);
+ unsigned sym = XPRESS_NUM_CHARS + ((bsr32(offset) << 4) | len_hdr);
+
+ freqs[sym]++;
+ return (struct xpress_item) { .offset = offset,
+ .adjusted_len = adjusted_len };
+}
+
+static unsigned
+xpress_get_matches_fillcache(struct xpress_compressor *c,
+ const struct lz_match **matches_ret)
+{
+ struct lz_match *cache_ptr;
+ struct lz_match *matches;
+ unsigned num_matches;
+
+ cache_ptr = c->cache_ptr;
+ matches = cache_ptr + 1;
+ if (likely(cache_ptr <= c->cache_limit)) {
+ num_matches = lz_mf_get_matches(c->mf, matches);
+ cache_ptr->len = num_matches;
+ c->cache_ptr = matches + num_matches;
+ } else {
+ num_matches = 0;
+ }
+ c->cur_window_ptr++;
+ *matches_ret = matches;
+ return num_matches;
+}
+
+static unsigned
+xpress_get_matches_usecache(struct xpress_compressor *c,
+ const struct lz_match **matches_ret)
+{
+ struct lz_match *cache_ptr;
+ struct lz_match *matches;
+ unsigned num_matches;
+
+ cache_ptr = c->cache_ptr;
+ matches = cache_ptr + 1;
+ if (likely(cache_ptr <= c->cache_limit)) {
+ num_matches = cache_ptr->len;
+ c->cache_ptr = matches + num_matches;
+ } else {
+ num_matches = 0;
+ }
+ c->cur_window_ptr++;
+ *matches_ret = matches;
+ return num_matches;
+}
+
+static unsigned
+xpress_get_matches_usecache_nocheck(struct xpress_compressor *c,
+ const struct lz_match **matches_ret)
+{
+ struct lz_match *cache_ptr;
+ struct lz_match *matches;
+ unsigned num_matches;
+
+ cache_ptr = c->cache_ptr;
+ matches = cache_ptr + 1;
+ num_matches = cache_ptr->len;
+ c->cache_ptr = matches + num_matches;
+ c->cur_window_ptr++;
+ *matches_ret = matches;
+ return num_matches;
+}
+
+static unsigned
+xpress_get_matches_noncaching(struct xpress_compressor *c,
+ const struct lz_match **matches_ret)
+{
+ c->cur_window_ptr++;
+ *matches_ret = c->cached_matches;
+ return lz_mf_get_matches(c->mf, c->cached_matches);
+}
+