+ unsigned i;
+
+ LZX_ASSERT(block_type == LZX_BLOCKTYPE_ALIGNED ||
+ block_type == LZX_BLOCKTYPE_VERBATIM);
+ LZX_ASSERT(block_size <= LZX_MAX_WINDOW_SIZE);
+ LZX_ASSERT(num_chosen_matches <= LZX_MAX_WINDOW_SIZE);
+ lzx_assert_codes_valid(codes);
+
+ /* The first three bits indicate the type of block and are one of the
+ * LZX_BLOCKTYPE_* constants. */
+ bitstream_put_bits(ostream, block_type, LZX_BLOCKTYPE_NBITS);
+
+ /* The next bit indicates whether the block size is the default (32768),
+ * indicated by a 1 bit, or whether the block size is given by the next
+ * 16 bits, indicated by a 0 bit. */
+ if (block_size == LZX_DEFAULT_BLOCK_SIZE) {
+ bitstream_put_bits(ostream, 1, 1);
+ } else {
+ bitstream_put_bits(ostream, 0, 1);
+ bitstream_put_bits(ostream, block_size, LZX_BLOCKSIZE_NBITS);
+ }
+
+ /* Write out lengths of the main code. Note that the LZX specification
+ * incorrectly states that the aligned offset code comes after the
+ * length code, but in fact it is the very first tree to be written
+ * (before the main code). */
+ if (block_type == LZX_BLOCKTYPE_ALIGNED)
+ for (i = 0; i < LZX_ALIGNEDTREE_NUM_SYMBOLS; i++)
+ bitstream_put_bits(ostream, codes->lens.aligned[i],
+ LZX_ALIGNEDTREE_ELEMENT_SIZE);
+
+ LZX_DEBUG("Writing main code...");
+
+ /* Write the pre-tree and lengths for the first LZX_NUM_CHARS symbols in
+ * the main code, which are the codewords for literal bytes. */
+ lzx_write_compressed_code(ostream,
+ codes->lens.main,
+ prev_codes->lens.main,
+ LZX_NUM_CHARS);
+
+ /* Write the pre-tree and lengths for the rest of the main code, which
+ * are the codewords for match headers. */
+ lzx_write_compressed_code(ostream,
+ codes->lens.main + LZX_NUM_CHARS,
+ prev_codes->lens.main + LZX_NUM_CHARS,
+ LZX_MAINTREE_NUM_SYMBOLS - LZX_NUM_CHARS);
+
+ LZX_DEBUG("Writing length code...");
+
+ /* Write the pre-tree and lengths for the length code. */
+ lzx_write_compressed_code(ostream,
+ codes->lens.len,
+ prev_codes->lens.len,
+ LZX_LENTREE_NUM_SYMBOLS);
+
+ LZX_DEBUG("Writing matches and literals...");
+
+ /* Write the actual matches and literals. */
+ lzx_write_matches_and_literals(ostream, block_type,
+ chosen_matches, num_chosen_matches,
+ codes);
+
+ LZX_DEBUG("Done writing block.");
+}
+
+/* Write the LZX block of index @block_number, or write its children recursively
+ * if it is a split block.
+ *
+ * @prev_codes is a pointer to the Huffman codes for the most recent block
+ * written, or all zeroes if this is the first block.
+ *
+ * Return a pointer to the Huffman codes for the last block written. */
+static struct lzx_codes *
+lzx_write_block_recursive(struct lzx_compressor *ctx,
+ unsigned block_number,
+ struct lzx_codes * prev_codes,
+ struct output_bitstream *ostream)
+{
+ struct lzx_block_spec *spec = &ctx->block_specs[block_number - 1];
+
+ if (spec->is_split) {
+ prev_codes = lzx_write_block_recursive(ctx, block_number * 2 + 0,
+ prev_codes, ostream);
+ prev_codes = lzx_write_block_recursive(ctx, block_number * 2 + 1,
+ prev_codes, ostream);
+ } else {
+ LZX_DEBUG("Writing block #%u (type=%d, size=%u, num_chosen_matches=%u)...",
+ block_number, spec->block_type, spec->block_size,
+ spec->num_chosen_matches);
+ lzx_write_compressed_block(spec->block_type,
+ spec->block_size,
+ &ctx->chosen_matches[spec->chosen_matches_start_pos],
+ spec->num_chosen_matches,
+ &spec->codes,
+ prev_codes,
+ ostream);
+ prev_codes = &spec->codes;
+ }
+ return prev_codes;
+}
+
+/* Write out the LZX blocks that were computed. */
+static void
+lzx_write_all_blocks(struct lzx_compressor *ctx, struct output_bitstream *ostream)
+{
+ lzx_write_block_recursive(ctx, 1, &ctx->zero_codes, ostream);
+}
+
+static u32
+lzx_record_literal(u8 literal, void *_freqs)
+{
+ struct lzx_freqs *freqs = _freqs;
+
+ freqs->main[literal]++;
+
+ return (u32)literal;
+}
+
+/* Constructs a match from an offset and a length, and updates the LRU queue and
+ * the frequency of symbols in the main, length, and aligned offset alphabets.
+ * The return value is a 32-bit number that provides the match in an
+ * intermediate representation documented below. */
+static u32
+lzx_record_match(unsigned match_offset, unsigned match_len,
+ void *_freqs, void *_queue)
+{
+ struct lzx_freqs *freqs = _freqs;
+ struct lzx_lru_queue *queue = _queue;
+ unsigned position_slot;
+ unsigned position_footer = 0;
+ u32 len_header;
+ u32 len_pos_header;
+ unsigned len_footer;
+ unsigned adjusted_match_len;
+
+ LZX_ASSERT(match_len >= LZX_MIN_MATCH && match_len <= LZX_MAX_MATCH);
+
+ /* If possible, encode this offset as a repeated offset. */
+ if (match_offset == queue->R0) {
+ position_slot = 0;
+ } else if (match_offset == queue->R1) {
+ swap(queue->R0, queue->R1);
+ position_slot = 1;
+ } else if (match_offset == queue->R2) {
+ swap(queue->R0, queue->R2);
+ position_slot = 2;
+ } else {
+ /* Not a repeated offset. */
+
+ /* offsets of 0, 1, and 2 are reserved for the repeated offset
+ * codes, so non-repeated offsets must be encoded as 3+. The
+ * minimum offset is 1, so encode the offsets offset by 2. */
+ unsigned formatted_offset = match_offset + 2;
+
+ queue->R2 = queue->R1;
+ queue->R1 = queue->R0;
+ queue->R0 = match_offset;
+
+ /* The (now-formatted) offset will actually be encoded as a
+ * small position slot number that maps to a certain hard-coded
+ * offset (position base), followed by a number of extra bits---
+ * the position footer--- that are added to the position base to
+ * get the original formatted offset. */
+
+ position_slot = lzx_get_position_slot(formatted_offset);
+ position_footer = formatted_offset &
+ ((1 << lzx_get_num_extra_bits(position_slot)) - 1);
+ }
+
+ adjusted_match_len = match_len - LZX_MIN_MATCH;
+
+
+ /* The match length must be at least 2, so let the adjusted match length
+ * be the match length minus 2.
+ *
+ * If it is less than 7, the adjusted match length is encoded as a 3-bit
+ * number offset by 2. Otherwise, the 3-bit length header is all 1's
+ * and the actual adjusted length is given as a symbol encoded with the
+ * length tree, offset by 7.
+ */
+ if (adjusted_match_len < LZX_NUM_PRIMARY_LENS) {
+ len_header = adjusted_match_len;
+ } else {
+ len_header = LZX_NUM_PRIMARY_LENS;
+ len_footer = adjusted_match_len - LZX_NUM_PRIMARY_LENS;
+ freqs->len[len_footer]++;
+ }
+ len_pos_header = (position_slot << 3) | len_header;
+
+ freqs->main[len_pos_header + LZX_NUM_CHARS]++;
+
+ /* Equivalent to:
+ * if (lzx_extra_bits[position_slot] >= 3) */
+ if (position_slot >= 8)
+ freqs->aligned[position_footer & 7]++;
+
+ /* Pack the position slot, position footer, and match length into an
+ * intermediate representation.
+ *
+ * bits description
+ * ---- -----------------------------------------------------------
+ *
+ * 31 1 if a match, 0 if a literal.
+ *
+ * 30-25 position slot. This can be at most 50, so it will fit in 6
+ * bits.
+ *
+ * 8-24 position footer. This is the offset of the real formatted
+ * offset from the position base. This can be at most 17 bits
+ * (since lzx_extra_bits[LZX_NUM_POSITION_SLOTS - 1] is 17).
+ *
+ * 0-7 length of match, offset by 2. This can be at most
+ * (LZX_MAX_MATCH - 2) == 255, so it will fit in 8 bits. */
+ return 0x80000000 |
+ (position_slot << 25) |
+ (position_footer << 8) |
+ (adjusted_match_len);
+}
+
+/* Set the cost model @ctx->costs from the Huffman codeword lengths specified in
+ * @lens.
+ *
+ * These are basically the same thing, except that the Huffman codewords with
+ * length 0 correspond to symbols with zero frequency that still need to be
+ * assigned actual costs. The specific values assigned are arbitrary, but they
+ * should be fairly high (near the maximum codeword length) to take into account
+ * the fact that uses of these symbols are expected to be rare.
+ */
+static void
+lzx_set_costs(struct lzx_compressor * ctx, const struct lzx_lens * lens)
+{
+ unsigned i;
+
+ memcpy(&ctx->costs, lens, sizeof(struct lzx_lens));
+
+ for (i = 0; i < LZX_MAINTREE_NUM_SYMBOLS; i++)
+ if (ctx->costs.main[i] == 0)
+ ctx->costs.main[i] = ctx->params.slow.main_nostat_cost;
+
+ for (i = 0; i < LZX_LENTREE_NUM_SYMBOLS; i++)
+ if (ctx->costs.len[i] == 0)
+ ctx->costs.len[i] = ctx->params.slow.len_nostat_cost;
+
+ for (i = 0; i < LZX_ALIGNEDTREE_NUM_SYMBOLS; i++)
+ if (ctx->costs.aligned[i] == 0)
+ ctx->costs.aligned[i] = ctx->params.slow.aligned_nostat_cost;
+}
+
+static u32
+lzx_literal_cost(u8 c, const struct lzx_lens * costs)
+{
+ return costs->main[c];
+}
+
+/* Given a (length, offset) pair that could be turned into a valid LZX match as
+ * well as costs for the codewords in the main, length, and aligned Huffman
+ * codes, return the approximate number of bits it will take to represent this
+ * match in the compressed output. */
+static unsigned
+lzx_match_cost(unsigned length, unsigned offset, const struct lzx_lens *costs
+
+#if LZX_PARAM_ACCOUNT_FOR_LRU
+ , struct lzx_lru_queue *queue
+#endif
+ )
+{
+ unsigned position_slot, len_header, main_symbol;
+ unsigned cost = 0;
+
+ /* Calculate position slot and length header, then combine them into the
+ * main symbol. */
+
+#if LZX_PARAM_ACCOUNT_FOR_LRU
+ if (offset == queue->R0) {
+ position_slot = 0;
+ } else if (offset == queue->R1) {
+ swap(queue->R0, queue->R1);
+ position_slot = 1;
+ } else if (offset == queue->R2) {
+ swap(queue->R0, queue->R2);
+ position_slot = 2;
+ } else
+#endif
+ position_slot = lzx_get_position_slot(offset + 2);
+
+ len_header = min(length - LZX_MIN_MATCH, LZX_NUM_PRIMARY_LENS);
+ main_symbol = ((position_slot << 3) | len_header) + LZX_NUM_CHARS;
+
+ /* Account for main symbol. */
+ cost += costs->main[main_symbol];
+
+ /* Account for extra position information. */
+ unsigned num_extra_bits = lzx_get_num_extra_bits(position_slot);
+ if (num_extra_bits >= 3) {
+ cost += num_extra_bits - 3;
+ cost += costs->aligned[(offset + LZX_MIN_MATCH) & 7];
+ } else {
+ cost += num_extra_bits;
+ }
+
+ /* Account for extra length information. */
+ if (length - LZX_MIN_MATCH >= LZX_NUM_PRIMARY_LENS)
+ cost += costs->len[length - LZX_MIN_MATCH - LZX_NUM_PRIMARY_LENS];
+
+ return cost;
+}
+
+/* This procedure effectively creates a new binary tree corresponding to the
+ * current string at the same time that it searches the existing tree nodes for
+ * matches. This is the same algorithm as that used in GetMatchesSpec1() in
+ * 7-Zip, but it is hopefully explained a little more clearly below. */
+static unsigned
+lzx_lz_get_matches(const u8 window[restrict],
+ const unsigned bytes_remaining,
+ const unsigned strstart,
+ const unsigned max_length,
+ u16 child_tab[restrict],
+ unsigned cur_match,
+ const unsigned prev_len,
+ struct raw_match * const matches)
+{
+ u16 *new_tree_lt_ptr = &child_tab[strstart * 2];
+ u16 *new_tree_gt_ptr = &child_tab[strstart * 2 + 1];
+
+ u16 longest_lt_match_len = 0;
+ u16 longest_gt_match_len = 0;
+
+ /* Maximum number of nodes to walk down before stopping */
+ unsigned depth = max_length;
+
+ /* Length of longest match found so far */
+ unsigned longest_match_len = prev_len;
+
+ /* Maximum length of match to return */
+ unsigned len_limit = min(bytes_remaining, max_length);
+
+ /* Number of matches found so far */
+ unsigned num_matches = 0;
+
+ for (;;) {
+
+ /* Stop if too many nodes were traversed or if there is no next
+ * node */
+ if (depth-- == 0 || cur_match == 0) {
+ *new_tree_gt_ptr = 0;
+ *new_tree_lt_ptr = 0;
+ return num_matches;
+ }
+
+ /* Load the pointers to the children of the binary tree node
+ * corresponding to the current match */
+ u16 * const cur_match_ptrs = &child_tab[cur_match * 2];
+
+ /* Set up pointers to the current match and to the current
+ * string */
+ const u8 * const matchptr = &window[cur_match];
+ const u8 * const strptr = &window[strstart];
+
+ /* Determine position at which to start comparing */
+ u16 len = min(longest_lt_match_len,
+ longest_gt_match_len);
+
+ if (matchptr[len] == strptr[len]) {
+
+ /* Extend the match as far as possible. */
+ while (++len != len_limit)
+ if (matchptr[len] != strptr[len])
+ break;
+
+ /* Record this match if it is the longest found so far.
+ */
+ if (len > longest_match_len) {
+ longest_match_len = len;
+ matches[num_matches].len = len;
+ matches[num_matches].offset = strstart - cur_match;
+ num_matches++;
+
+ if (len == len_limit) {
+ /* Length limit was reached. Link left pointer
+ * in the new tree with left subtree of current
+ * match tree, and link the right pointer in the
+ * new tree with the right subtree of the
+ * current match tree. This in effect deletes
+ * the node for the currrent match, which is
+ * desirable because the current match is the
+ * same as the current string up until the
+ * length limit, so in subsequent queries it
+ * will never be preferable to the current
+ * position. */
+ *new_tree_lt_ptr = cur_match_ptrs[0];
+ *new_tree_gt_ptr = cur_match_ptrs[1];
+ return num_matches;
+ }
+ }
+ }
+
+ if (matchptr[len] < strptr[len]) {
+ /* Case 1: The current match is lexicographically less
+ * than the current string.
+ *
+ * Since we are searching the binary tree structures, we
+ * need to walk down to the *right* subtree of the
+ * current match's node to get to a match that is
+ * lexicographically *greater* than the current match
+ * but still lexicographically *lesser* than the current
+ * string.
+ *
+ * At the same time, we link the entire binary tree
+ * corresponding to the current match into the
+ * appropriate place in the new binary tree being built
+ * for the current string. */
+ *new_tree_lt_ptr = cur_match;
+ new_tree_lt_ptr = &cur_match_ptrs[1];
+ cur_match = *new_tree_lt_ptr;
+ longest_lt_match_len = len;
+ } else {
+ /* Case 2: The current match is lexicographically
+ * greater than the current string.
+ *
+ * This is analogous to Case 1 above, but everything
+ * happens in the other direction.
+ */
+ *new_tree_gt_ptr = cur_match;
+ new_tree_gt_ptr = &cur_match_ptrs[0];
+ cur_match = *new_tree_gt_ptr;
+ longest_gt_match_len = len;
+ }
+ }
+}
+
+/* Equivalent to lzx_lz_get_matches(), but only updates the tree and doesn't
+ * return matches. See that function for details (including comments). */
+static void
+lzx_lz_skip_matches(const u8 window[restrict],
+ const unsigned bytes_remaining,
+ const unsigned strstart,
+ const unsigned max_length,
+ u16 child_tab[restrict],
+ unsigned cur_match,
+ const unsigned prev_len)
+{
+ u16 *new_tree_lt_ptr = &child_tab[strstart * 2];
+ u16 *new_tree_gt_ptr = &child_tab[strstart * 2 + 1];
+
+ u16 longest_lt_match_len = 0;
+ u16 longest_gt_match_len = 0;
+
+ unsigned depth = max_length;
+
+ unsigned longest_match_len = prev_len;
+
+ unsigned len_limit = min(bytes_remaining, max_length);
+
+ for (;;) {
+ if (depth-- == 0 || cur_match == 0) {
+ *new_tree_gt_ptr = 0;
+ *new_tree_lt_ptr = 0;
+ return;
+ }
+
+ u16 * const cur_match_ptrs = &child_tab[cur_match * 2];
+
+ const u8 * const matchptr = &window[cur_match];
+ const u8 * const strptr = &window[strstart];
+
+ u16 len = min(longest_lt_match_len,
+ longest_gt_match_len);
+
+ if (matchptr[len] == strptr[len]) {
+ while (++len != len_limit)
+ if (matchptr[len] != strptr[len])
+ break;
+
+ if (len > longest_match_len) {
+ longest_match_len = len;
+
+ if (len == len_limit) {
+ *new_tree_lt_ptr = cur_match_ptrs[0];
+ *new_tree_gt_ptr = cur_match_ptrs[1];
+ return;
+ }
+ }
+ }
+
+ if (matchptr[len] < strptr[len]) {
+ *new_tree_lt_ptr = cur_match;
+ new_tree_lt_ptr = &cur_match_ptrs[1];
+ cur_match = *new_tree_lt_ptr;
+ longest_lt_match_len = len;
+ } else {
+ *new_tree_gt_ptr = cur_match;
+ new_tree_gt_ptr = &cur_match_ptrs[0];
+ cur_match = *new_tree_gt_ptr;
+ longest_gt_match_len = len;
+ }
+ }
+}
+
+static unsigned
+lzx_lz_get_matches_caching(struct lzx_compressor *ctx,
+ struct raw_match **matches_ret);
+
+/* Tell the match-finder to skip the specified number of bytes (@n) in the
+ * input. */
+static void
+lzx_lz_skip_bytes(struct lzx_compressor *ctx, unsigned n)
+{
+
+#if LZX_PARAM_DONT_SKIP_MATCHES
+ /* Option 1: Still cache the matches from the positions skipped. They
+ * will then be available in later passes. */
+ struct raw_match *matches;
+ while (n--)
+ lzx_lz_get_matches_caching(ctx, &matches);
+#else
+ /* Option 2: Mark the positions skipped as having no matches available,
+ * but we still need to update the binary tree in case subsequent
+ * positions have matches at the current position. */
+ LZX_ASSERT(n <= ctx->match_window_end - ctx->match_window_pos);
+ if (ctx->matches_already_found) {
+ while (n--) {
+ LZX_ASSERT(ctx->cached_matches[ctx->cached_matches_pos].offset ==
+ ctx->match_window_pos);
+ ctx->cached_matches_pos += ctx->cached_matches[ctx->cached_matches_pos].len + 1;
+ ctx->match_window_pos++;
+ }
+ } else {
+ while (n--) {
+ if (ctx->params.slow.use_len2_matches &&
+ ctx->match_window_end - ctx->match_window_pos >= 2) {
+ unsigned c1 = ctx->window[ctx->match_window_pos];
+ unsigned c2 = ctx->window[ctx->match_window_pos + 1];
+ unsigned digram = c1 | (c2 << 8);
+ ctx->digram_tab[digram] = ctx->match_window_pos;
+ }
+ if (ctx->match_window_end - ctx->match_window_pos >= 3) {
+ unsigned hash;
+ unsigned cur_match;
+
+ hash = lzx_lz_compute_hash(&ctx->window[ctx->match_window_pos]);
+
+ cur_match = ctx->hash_tab[hash];
+ ctx->hash_tab[hash] = ctx->match_window_pos;
+
+ lzx_lz_skip_matches(ctx->window,
+ ctx->match_window_end - ctx->match_window_pos,
+ ctx->match_window_pos,
+ ctx->params.slow.num_fast_bytes,
+ ctx->child_tab,
+ cur_match, 1);
+ }
+ ctx->cached_matches[ctx->cached_matches_pos].len = 0;
+ ctx->cached_matches[ctx->cached_matches_pos].offset = ctx->match_window_pos;
+ ctx->cached_matches_pos++;
+ ctx->match_window_pos++;
+ }
+ }
+#endif /* !LZX_PARAM_DONT_SKIP_MATCHES */
+}
+
+/* Retrieve a list of matches available at the next position in the input.
+ *
+ * The return value is the number of matches found, and a pointer to them is
+ * written to @matches_ret. The matches will be sorted in order by length.
+ *
+ * This is essentially a wrapper around lzx_lz_get_matches() that caches its
+ * output the first time and also performs the needed hashing.
+ */
+static unsigned
+lzx_lz_get_matches_caching(struct lzx_compressor *ctx,
+ struct raw_match **matches_ret)
+{
+ unsigned num_matches;
+ struct raw_match *matches;
+
+ LZX_ASSERT(ctx->match_window_end >= ctx->match_window_pos);
+
+ matches = &ctx->cached_matches[ctx->cached_matches_pos + 1];
+
+ if (ctx->matches_already_found) {
+ num_matches = ctx->cached_matches[ctx->cached_matches_pos].len;
+ LZX_ASSERT(ctx->cached_matches[ctx->cached_matches_pos].offset == ctx->match_window_pos);
+
+ for (int i = (int)num_matches - 1; i >= 0; i--) {
+ if (ctx->match_window_pos + matches[i].len > ctx->match_window_end)
+ matches[i].len = ctx->match_window_end - ctx->match_window_pos;
+ else
+ break;
+ }
+ } else {
+ unsigned prev_len = 1;
+ struct raw_match * matches_ret = &ctx->cached_matches[ctx->cached_matches_pos + 1];
+ num_matches = 0;
+
+ if (ctx->params.slow.use_len2_matches &&
+ ctx->match_window_end - ctx->match_window_pos >= 3) {
+ unsigned c1 = ctx->window[ctx->match_window_pos];
+ unsigned c2 = ctx->window[ctx->match_window_pos + 1];
+ unsigned digram = c1 | (c2 << 8);
+ unsigned cur_match;
+
+ cur_match = ctx->digram_tab[digram];
+ ctx->digram_tab[digram] = ctx->match_window_pos;
+ if (cur_match != 0 &&
+ ctx->window[cur_match + 2] != ctx->window[ctx->match_window_pos + 2])
+ {
+ matches_ret->len = 2;
+ matches_ret->offset = ctx->match_window_pos - cur_match;
+ matches_ret++;
+ num_matches++;
+ prev_len = 2;
+ }
+ }
+ if (ctx->match_window_end - ctx->match_window_pos >= 3) {
+ unsigned hash;
+ unsigned cur_match;
+
+ hash = lzx_lz_compute_hash(&ctx->window[ctx->match_window_pos]);
+
+ cur_match = ctx->hash_tab[hash];
+ ctx->hash_tab[hash] = ctx->match_window_pos;
+ num_matches += lzx_lz_get_matches(ctx->window,
+ ctx->match_window_end - ctx->match_window_pos,
+ ctx->match_window_pos,
+ ctx->params.slow.num_fast_bytes,
+ ctx->child_tab,
+ cur_match,
+ prev_len,
+ matches_ret);
+ }
+
+ ctx->cached_matches[ctx->cached_matches_pos].len = num_matches;
+ ctx->cached_matches[ctx->cached_matches_pos].offset = ctx->match_window_pos;
+
+ if (num_matches) {
+ struct raw_match *longest_match_ptr =
+ &ctx->cached_matches[ctx->cached_matches_pos + 1 +
+ num_matches - 1];
+ u16 len = longest_match_ptr->len;
+
+ /* If the longest match returned by the match-finder
+ * reached the number of fast bytes, extend it as much
+ * as possible. */
+ if (len == ctx->params.slow.num_fast_bytes) {
+ const unsigned maxlen =
+ min(ctx->match_window_end - ctx->match_window_pos,
+ LZX_MAX_MATCH);
+
+ const u8 * const matchptr =
+ &ctx->window[ctx->match_window_pos - longest_match_ptr->offset];
+
+ const u8 * const strptr =
+ &ctx->window[ctx->match_window_pos];
+
+ while (len < maxlen && matchptr[len] == strptr[len])
+ len++;
+ }
+ longest_match_ptr->len = len;
+ }
+ }
+ ctx->cached_matches_pos += num_matches + 1;
+ *matches_ret = matches;
+
+#if 0
+ printf("\n");
+ for (unsigned i = 0; i < num_matches; i++)
+ {
+ printf("Len %u Offset %u\n", matches[i].len, matches[i].offset);
+ }
+#endif
+
+ for (unsigned i = 0; i < num_matches; i++) {
+ LZX_ASSERT(matches[i].len <= LZX_MAX_MATCH);
+ if (matches[i].len >= LZX_MIN_MATCH) {
+ LZX_ASSERT(matches[i].offset <= ctx->match_window_pos);
+ LZX_ASSERT(matches[i].len <= ctx->match_window_end - ctx->match_window_pos);
+ LZX_ASSERT(!memcmp(&ctx->window[ctx->match_window_pos],
+ &ctx->window[ctx->match_window_pos - matches[i].offset],
+ matches[i].len));
+ }
+ }
+
+ ctx->match_window_pos++;
+ return num_matches;
+}
+
+/*
+ * Reverse the linked list of near-optimal matches so that they can be returned
+ * in forwards order.
+ *
+ * Returns the first match in the list.
+ */
+static struct raw_match
+lzx_lz_reverse_near_optimal_match_list(struct lzx_compressor *ctx,
+ unsigned cur_pos)
+{
+ unsigned prev_link, saved_prev_link;
+ unsigned prev_match_offset, saved_prev_match_offset;
+
+ ctx->optimum_end_idx = cur_pos;
+
+ saved_prev_link = ctx->optimum[cur_pos].prev.link;
+ saved_prev_match_offset = ctx->optimum[cur_pos].prev.match_offset;
+
+ do {
+ prev_link = saved_prev_link;
+ prev_match_offset = saved_prev_match_offset;
+
+ saved_prev_link = ctx->optimum[prev_link].prev.link;
+ saved_prev_match_offset = ctx->optimum[prev_link].prev.match_offset;
+
+ ctx->optimum[prev_link].next.link = cur_pos;
+ ctx->optimum[prev_link].next.match_offset = prev_match_offset;
+
+ cur_pos = prev_link;
+ } while (cur_pos != 0);
+
+ ctx->optimum_cur_idx = ctx->optimum[0].next.link;
+
+ return (struct raw_match)
+ { .len = ctx->optimum_cur_idx,
+ .offset = ctx->optimum[0].next.match_offset,
+ };
+}
+
+/*
+ * lzx_lz_get_near_optimal_match() -
+ *
+ * Choose the "best" match or literal to use at the next position in the input.
+ *
+ * Unlike a "greedy" parser that always takes the longest match, or even a
+ * parser with one match/literal look-ahead like zlib, the algorithm used here
+ * may look ahead many matches/literals to determine the best match/literal to
+ * output next. The motivation is that the compression ratio is improved if the
+ * compressor can do things like use a shorter-than-possible match in order to
+ * allow a longer match later, and also take into account the Huffman code cost
+ * model rather than simply assuming that longer is better. It is not a true
+ * "optimal" parser, however, since some shortcuts can be taken; for example, if
+ * a match is very long, the parser just chooses it immediately before too much
+ * time is wasting considering many different alternatives that are unlikely to
+ * be better.
+ *
+ * This algorithm is based on that used in 7-Zip's DEFLATE encoder.
+ *
+ * Each call to this function does one of two things:
+ *
+ * 1. Build a near-optimal sequence of matches/literals, up to some point, that
+ * will be returned by subsequent calls to this function, then return the
+ * first one.
+ *
+ * OR
+ *
+ * 2. Return the next match/literal previously computed by a call to this
+ * function;
+ *
+ * This function relies on the following state in the compressor context:
+ *
+ * ctx->window (read-only: preprocessed data being compressed)
+ * ctx->cost (read-only: cost model to use)
+ * ctx->optimum (internal state; leave uninitialized)
+ * ctx->optimum_cur_idx (must set to 0 before first call)
+ * ctx->optimum_end_idx (must set to 0 before first call)
+ * ctx->hash_tab (must set to 0 before first call)
+ * ctx->cached_matches (internal state; leave uninitialized)
+ * ctx->cached_matches_pos (initialize to 0 before first call; save and
+ * restore value if restarting parse from a
+ * certain position)
+ * ctx->match_window_pos (must initialize to position of next match to
+ * return; subsequent calls return subsequent
+ * matches)
+ * ctx->match_window_end (must initialize to limit of match-finding region;
+ * subsequent calls use the same limit)
+ *
+ * The return value is a (length, offset) pair specifying the match or literal
+ * chosen. For literals, length is either 0 or 1 and offset is meaningless.
+ */
+static struct raw_match
+lzx_lz_get_near_optimal_match(struct lzx_compressor * ctx)
+{
+#if 0
+ /* Testing: literals only */
+ ctx->match_window_pos++;
+ return (struct raw_match) { .len = 0 };
+#elif 0
+ /* Testing: greedy parsing */
+ struct raw_match *matches;
+ unsigned num_matches;
+ struct raw_match match = {.len = 0};
+
+ num_matches = lzx_lz_get_matches_caching(ctx, &matches);
+ if (num_matches) {
+ match = matches[num_matches - 1];
+ lzx_lz_skip_bytes(ctx, match.len - 1);
+ }
+ return match;
+#else
+ unsigned num_possible_matches;
+ struct raw_match *possible_matches;
+ struct raw_match match;
+ unsigned longest_match_len;
+ unsigned len, match_idx;
+
+ if (ctx->optimum_cur_idx != ctx->optimum_end_idx) {
+ /* Case 2: Return the next match/literal already found. */
+ match.len = ctx->optimum[ctx->optimum_cur_idx].next.link -
+ ctx->optimum_cur_idx;
+ match.offset = ctx->optimum[ctx->optimum_cur_idx].next.match_offset;
+
+ ctx->optimum_cur_idx = ctx->optimum[ctx->optimum_cur_idx].next.link;
+ return match;
+ }
+
+ /* Case 1: Compute a new list of matches/literals to return. */
+
+ ctx->optimum_cur_idx = 0;
+ ctx->optimum_end_idx = 0;
+
+ /* Get matches at this position. */
+ num_possible_matches = lzx_lz_get_matches_caching(ctx, &possible_matches);
+
+ /* If no matches found, return literal. */
+ if (num_possible_matches == 0)
+ return (struct raw_match){ .len = 0 };
+
+ /* The matches that were found are sorted by length. Get the length of
+ * the longest one. */
+ longest_match_len = possible_matches[num_possible_matches - 1].len;
+
+ /* Greedy heuristic: if the longest match that was found is greater
+ * than the number of fast bytes, return it immediately; don't both
+ * doing more work. */
+ if (longest_match_len > ctx->params.slow.num_fast_bytes) {
+ lzx_lz_skip_bytes(ctx, longest_match_len - 1);
+ return possible_matches[num_possible_matches - 1];
+ }
+
+ /* Calculate the cost to reach the next position by outputting a
+ * literal. */
+#if LZX_PARAM_ACCOUNT_FOR_LRU
+ ctx->optimum[0].queue = ctx->queue;
+ ctx->optimum[1].queue = ctx->optimum[0].queue;
+#endif
+ ctx->optimum[1].cost = lzx_literal_cost(ctx->window[ctx->match_window_pos],
+ &ctx->costs);
+ ctx->optimum[1].prev.link = 0;
+
+ /* Calculate the cost to reach any position up to and including that
+ * reached by the longest match, using the shortest (i.e. closest) match
+ * that reaches each position. */
+ match_idx = 0;
+ BUILD_BUG_ON(LZX_MIN_MATCH != 2);
+ for (len = LZX_MIN_MATCH; len <= longest_match_len; len++) {
+
+ LZX_ASSERT(match_idx < num_possible_matches);
+
+ #if LZX_PARAM_ACCOUNT_FOR_LRU
+ ctx->optimum[len].queue = ctx->optimum[0].queue;
+ #endif
+ ctx->optimum[len].prev.link = 0;
+ ctx->optimum[len].prev.match_offset = possible_matches[match_idx].offset;
+ ctx->optimum[len].cost = lzx_match_cost(len,
+ possible_matches[match_idx].offset,
+ &ctx->costs
+ #if LZX_PARAM_ACCOUNT_FOR_LRU
+ , &ctx->optimum[len].queue
+ #endif
+ );
+ if (len == possible_matches[match_idx].len)
+ match_idx++;
+ }
+
+ unsigned cur_pos = 0;
+
+ /* len_end: greatest index forward at which costs have been calculated
+ * so far */
+ unsigned len_end = longest_match_len;
+
+
+ for (;;) {
+ /* Advance to next position. */
+ cur_pos++;
+
+ if (cur_pos == len_end || cur_pos == LZX_PARAM_OPTIM_ARRAY_SIZE)
+ return lzx_lz_reverse_near_optimal_match_list(ctx, cur_pos);
+
+ /* retrieve the number of matches available at this position */
+ num_possible_matches = lzx_lz_get_matches_caching(ctx,
+ &possible_matches);
+
+ unsigned new_len = 0;
+
+ if (num_possible_matches != 0) {
+ new_len = possible_matches[num_possible_matches - 1].len;
+
+ /* Greedy heuristic: if we found a match greater than
+ * the number of fast bytes, stop immediately. */
+ if (new_len > ctx->params.slow.num_fast_bytes) {
+
+ /* Build the list of matches to return and get
+ * the first one. */
+ match = lzx_lz_reverse_near_optimal_match_list(ctx, cur_pos);
+
+ /* Append the long match to the end of the list. */
+ ctx->optimum[cur_pos].next.match_offset =
+ possible_matches[num_possible_matches - 1].offset;
+ ctx->optimum[cur_pos].next.link = cur_pos + new_len;
+ ctx->optimum_end_idx = cur_pos + new_len;
+
+ /* Skip over the remaining bytes of the long match. */
+ lzx_lz_skip_bytes(ctx, new_len - 1);
+
+ /* Return first match in the list */
+ return match;
+ }
+ }
+
+ /* Consider proceeding with a literal byte. */
+ u32 cur_cost = ctx->optimum[cur_pos].cost;
+ u32 cur_plus_literal_cost = cur_cost +
+ lzx_literal_cost(ctx->window[ctx->match_window_pos - 1],
+ &ctx->costs);
+ if (cur_plus_literal_cost < ctx->optimum[cur_pos + 1].cost) {
+ ctx->optimum[cur_pos + 1].cost = cur_plus_literal_cost;
+ ctx->optimum[cur_pos + 1].prev.link = cur_pos;
+ #if LZX_PARAM_ACCOUNT_FOR_LRU
+ ctx->optimum[cur_pos + 1].queue = ctx->optimum[cur_pos].queue;
+ #endif
+ }
+
+ if (num_possible_matches == 0)
+ continue;
+
+ /* Consider proceeding with a match. */
+
+ while (len_end < cur_pos + new_len)
+ ctx->optimum[++len_end].cost = ~(u32)0;
+
+ match_idx = 0;
+ for (len = LZX_MIN_MATCH; len <= new_len; len++) {
+ LZX_ASSERT(match_idx < num_possible_matches);
+ #if LZX_PARAM_ACCOUNT_FOR_LRU
+ struct lzx_lru_queue q = ctx->optimum[cur_pos].queue;
+ #endif
+ u32 cost = cur_cost + lzx_match_cost(len,
+ possible_matches[match_idx].offset,
+ &ctx->costs
+ #if LZX_PARAM_ACCOUNT_FOR_LRU
+ , &q
+ #endif
+ );
+
+ if (cost < ctx->optimum[cur_pos + len].cost) {
+ ctx->optimum[cur_pos + len].cost = cost;
+ ctx->optimum[cur_pos + len].prev.link = cur_pos;
+ ctx->optimum[cur_pos + len].prev.match_offset =
+ possible_matches[match_idx].offset;
+ #if LZX_PARAM_ACCOUNT_FOR_LRU
+ ctx->optimum[cur_pos + len].queue = q;
+ #endif
+ }
+
+ if (len == possible_matches[match_idx].len)
+ match_idx++;
+ }
+ }
+#endif
+}
+
+static unsigned
+lzx_huffman_code_output_cost(const u8 lens[restrict],
+ const freq_t freqs[restrict],
+ unsigned num_syms)
+{
+ unsigned cost = 0;
+
+ for (unsigned i = 0; i < num_syms; i++)
+ cost += (unsigned)lens[i] * (unsigned)freqs[i];
+
+ return cost;
+}
+
+/* Return the number of bits required to output the lengths for the specified
+ * Huffman code in compressed format (encoded with a precode). */
+static unsigned
+lzx_code_cost(const u8 lens[], const u8 prev_lens[], unsigned num_syms)
+{
+ u8 output_syms[num_syms];
+ freq_t precode_freqs[LZX_PRETREE_NUM_SYMBOLS];
+ u8 precode_lens[LZX_PRETREE_NUM_SYMBOLS];
+ u16 precode_codewords[LZX_PRETREE_NUM_SYMBOLS];
+ unsigned cost = 0;
+ unsigned num_additional_bits;
+
+ /* Acount for the lengths of the precode itself. */
+ cost += LZX_PRETREE_NUM_SYMBOLS * LZX_PRETREE_ELEMENT_SIZE;
+
+ lzx_build_precode(lens, prev_lens, num_syms,
+ precode_freqs, output_syms,
+ precode_lens, precode_codewords,
+ &num_additional_bits);
+
+ /* Account for all precode symbols output. */
+ cost += lzx_huffman_code_output_cost(precode_lens, precode_freqs,
+ LZX_PRETREE_NUM_SYMBOLS);
+
+ /* Account for additional bits. */
+ cost += num_additional_bits;
+
+ return cost;
+}
+
+/* Account for extra bits in the main symbols. */
+static void
+lzx_update_mainsym_match_costs(int block_type,
+ u8 main_lens[LZX_MAINTREE_NUM_SYMBOLS])
+{
+ unsigned i;
+
+ LZX_ASSERT(block_type == LZX_BLOCKTYPE_ALIGNED ||
+ block_type == LZX_BLOCKTYPE_VERBATIM);
+
+ for (i = LZX_NUM_CHARS; i < LZX_MAINTREE_NUM_SYMBOLS; i++) {
+ unsigned position_slot = (i >> 3) & 0x1f;
+
+ /* If it's a verbatim block, add the number of extra bits
+ * corresponding to the position slot.
+ *
+ * If it's an aligned block and there would normally be at least
+ * 3 extra bits, count 3 less because they will be output as an
+ * aligned offset symbol instead. */
+ unsigned num_extra_bits = lzx_get_num_extra_bits(position_slot);
+
+ if (block_type == LZX_BLOCKTYPE_ALIGNED && num_extra_bits >= 3)
+ num_extra_bits -= 3;
+ main_lens[i] += num_extra_bits;
+ }
+}
+
+/*
+ * Compute the costs, in bits, to output a compressed block as aligned offset
+ * and verbatim.
+ *
+ * @block_size
+ * Number of bytes of uncompressed data the block represents.
+ * @codes
+ * Huffman codes that will be used when outputting the block.
+ * @prev_codes
+ * Huffman codes for the previous block, or all zeroes if this is the first
+ * block.
+ * @freqs
+ * Frequencies of Huffman symbols that will be output in the block.
+ * @aligned_cost_ret
+ * Cost of aligned block will be returned here.
+ * @verbatim_cost_ret
+ * Cost of verbatim block will be returned here.
+ */
+static void
+lzx_compute_compressed_block_costs(unsigned block_size,
+ const struct lzx_codes *codes,
+ const struct lzx_codes *prev_codes,
+ const struct lzx_freqs *freqs,
+ unsigned * aligned_cost_ret,
+ unsigned * verbatim_cost_ret)
+{
+ unsigned common_cost = 0;
+ unsigned aligned_cost = 0;
+ unsigned verbatim_cost = 0;
+
+ u8 updated_main_lens[LZX_MAINTREE_NUM_SYMBOLS];
+
+ /* Account for cost of block header. */
+ common_cost += LZX_BLOCKTYPE_NBITS;
+ if (block_size == LZX_DEFAULT_BLOCK_SIZE)
+ common_cost += 1;
+ else
+ common_cost += LZX_BLOCKSIZE_NBITS;
+
+ /* Account for cost of outputting aligned offset code. */
+ aligned_cost += LZX_ALIGNEDTREE_NUM_SYMBOLS * LZX_ALIGNEDTREE_ELEMENT_SIZE;
+
+ /* Account for cost of outputting main and length codes. */
+ common_cost += lzx_code_cost(codes->lens.main,
+ prev_codes->lens.main,
+ LZX_NUM_CHARS);
+ common_cost += lzx_code_cost(codes->lens.main + LZX_NUM_CHARS,
+ prev_codes->lens.main + LZX_NUM_CHARS,
+ LZX_MAINTREE_NUM_SYMBOLS - LZX_NUM_CHARS);
+ common_cost += lzx_code_cost(codes->lens.len,
+ prev_codes->lens.len,
+ LZX_LENTREE_NUM_SYMBOLS);
+
+ /* Account for cost to output main, length, and aligned symbols, taking
+ * into account extra position bits. */
+
+ memcpy(updated_main_lens, codes->lens.main, LZX_MAINTREE_NUM_SYMBOLS);
+ lzx_update_mainsym_match_costs(LZX_BLOCKTYPE_VERBATIM, updated_main_lens);
+ verbatim_cost += lzx_huffman_code_output_cost(updated_main_lens,
+ freqs->main,
+ LZX_MAINTREE_NUM_SYMBOLS);
+ memcpy(updated_main_lens, codes->lens.main, LZX_MAINTREE_NUM_SYMBOLS);
+ lzx_update_mainsym_match_costs(LZX_BLOCKTYPE_ALIGNED, updated_main_lens);
+ aligned_cost += lzx_huffman_code_output_cost(updated_main_lens,
+ freqs->main,
+ LZX_MAINTREE_NUM_SYMBOLS);
+
+ common_cost += lzx_huffman_code_output_cost(codes->lens.len,
+ freqs->len,
+ LZX_LENTREE_NUM_SYMBOLS);
+
+ aligned_cost += lzx_huffman_code_output_cost(codes->lens.aligned,
+ freqs->aligned,
+ LZX_ALIGNEDTREE_NUM_SYMBOLS);
+
+ *aligned_cost_ret = aligned_cost + common_cost;
+ *verbatim_cost_ret = verbatim_cost + common_cost;
+}
+
+/* Prepare a (nonsplit) compressed block. */
+static unsigned
+lzx_prepare_compressed_block(struct lzx_compressor *ctx, unsigned block_number,
+ struct lzx_codes *prev_codes)
+{
+ struct lzx_block_spec *spec = &ctx->block_specs[block_number - 1];
+ unsigned orig_cached_matches_pos = ctx->cached_matches_pos;
+ struct lzx_lru_queue orig_queue = ctx->queue;
+ struct lzx_freqs freqs;
+ unsigned cost;
+
+ /* Here's where the real work happens. The following loop runs one or
+ * more times, each time using a cost model based on the Huffman codes
+ * computed from the previous iteration (the first iteration uses a
+ * default model). Each iteration of the loop uses a heuristic
+ * algorithm to divide the block into near-optimal matches/literals from
+ * beginning to end. */
+ LZX_ASSERT(ctx->params.slow.num_optim_passes >= 1);
+ spec->num_chosen_matches = 0;
+ for (unsigned pass = 0; pass < ctx->params.slow.num_optim_passes; pass++)
+ {
+ LZX_DEBUG("Block %u: Match-choosing pass %u of %u",
+ block_number, pass + 1,
+ ctx->params.slow.num_optim_passes);
+
+ /* Reset frequency tables. */
+ memset(&freqs, 0, sizeof(freqs));
+
+ /* Reset match offset LRU queue. */
+ ctx->queue = orig_queue;
+
+ /* Reset match-finding position. */
+ ctx->cached_matches_pos = orig_cached_matches_pos;
+ ctx->match_window_pos = spec->window_pos;
+ ctx->match_window_end = spec->window_pos + spec->block_size;
+
+ /* Set cost model. */
+ lzx_set_costs(ctx, &spec->codes.lens);
+
+ unsigned window_pos = spec->window_pos;
+ unsigned end = window_pos + spec->block_size;
+
+ while (window_pos < end) {
+ struct raw_match match;
+ struct lzx_match lzx_match;
+
+ match = lzx_lz_get_near_optimal_match(ctx);
+
+ if (match.len >= LZX_MIN_MATCH) {
+
+ /* Best to output a match here. */
+
+ LZX_ASSERT(match.len <= LZX_MAX_MATCH);
+ LZX_ASSERT(!memcmp(&ctx->window[window_pos],
+ &ctx->window[window_pos - match.offset],
+ match.len));
+
+ /* Tally symbol frequencies. */
+ lzx_match.data = lzx_record_match(match.offset,
+ match.len,
+ &freqs,
+ &ctx->queue);
+
+ window_pos += match.len;
+ } else {
+ /* Best to output a literal here. */
+
+ /* Tally symbol frequencies. */
+ lzx_match.data = lzx_record_literal(ctx->window[window_pos],
+ &freqs);
+
+ window_pos += 1;
+ }
+
+ /* If it's the last pass, save the match/literal in
+ * intermediate form. */
+ if (pass == ctx->params.slow.num_optim_passes - 1) {
+ ctx->chosen_matches[spec->chosen_matches_start_pos +
+ spec->num_chosen_matches] = lzx_match;
+
+ spec->num_chosen_matches++;
+ }
+ }
+ LZX_ASSERT(window_pos == end);
+
+ /* Build Huffman codes using the new frequencies. */
+ lzx_make_huffman_codes(&freqs, &spec->codes);
+
+ /* The first time we get here is when the full input has been
+ * processed, so the match-finding is done. */
+ ctx->matches_already_found = true;
+ }
+
+ LZX_DEBUG("Block %u: saved %u matches/literals @ %u",
+ block_number, spec->num_chosen_matches,
+ spec->chosen_matches_start_pos);
+
+ unsigned aligned_cost;
+ unsigned verbatim_cost;
+
+ lzx_compute_compressed_block_costs(spec->block_size,
+ &spec->codes,
+ prev_codes,
+ &freqs,
+ &aligned_cost,
+ &verbatim_cost);
+
+ /* Choose whether to make the block aligned offset or verbatim. */
+ if (aligned_cost < verbatim_cost) {
+ spec->block_type = LZX_BLOCKTYPE_ALIGNED;
+ cost = aligned_cost;
+ LZX_DEBUG("Using aligned block (cost %u vs %u for verbatim)",
+ aligned_cost, verbatim_cost);
+ } else {
+ spec->block_type = LZX_BLOCKTYPE_VERBATIM;
+ cost = verbatim_cost;
+ LZX_DEBUG("Using verbatim block (cost %u vs %u for aligned)",
+ verbatim_cost, aligned_cost);
+ }
+
+ LZX_DEBUG("Block %u is %u => %u bytes unsplit.",
+ block_number, spec->block_size, cost / 8);
+
+ return cost;
+}
+
+/*
+ * lzx_prepare_block_recursive() -
+ *
+ * Given a (possibly nonproper) sub-sequence of the preprocessed input, compute
+ * the LZX block(s) that it should be output as.
+ *
+ * This function initially considers the case where the given sub-sequence of
+ * the preprocessed input be output as a single block. This block is calculated
+ * and its cost (number of bits required to output it) is computed.
+ *
+ * Then, if @max_split_level is greater than zero, a split into two evenly sized
+ * subblocks is considered. The block is recursively split in this way,
+ * potentially up to the depth specified by @max_split_level. The cost of the
+ * split block is compared to the cost of the single block, and the lower cost
+ * solution is used.
+ *
+ * For each compressed output block computed, the sequence of matches/literals
+ * and the corresponding Huffman codes for the block are produced and saved.
+ *
+ * The return value is the approximate number of bits the block (or all
+ * subblocks, in the case that the split block had lower cost), will take up
+ * when written to the compressed output.
+ */
+static unsigned
+lzx_prepare_block_recursive(struct lzx_compressor * ctx,
+ unsigned block_number,
+ unsigned max_split_level,
+ struct lzx_codes **prev_codes_p)
+{
+ struct lzx_block_spec *spec = &ctx->block_specs[block_number - 1];
+ unsigned cost;
+ unsigned orig_cached_matches_pos;
+ struct lzx_lru_queue orig_queue, nonsplit_queue;
+ struct lzx_codes *prev_codes = *prev_codes_p;
+
+ LZX_DEBUG("Preparing block %u...", block_number);
+
+ /* Save positions of chosen and cached matches, and the match offset LRU
+ * queue, so that they can be restored if splitting is attempted. */
+ orig_cached_matches_pos = ctx->cached_matches_pos;
+ orig_queue = ctx->queue;
+
+ /* Consider outputting the input subsequence as a single block. */
+ spec->is_split = 0;
+ cost = lzx_prepare_compressed_block(ctx, block_number, prev_codes);
+ nonsplit_queue = ctx->queue;
+
+ *prev_codes_p = &spec->codes;
+
+ /* If the maximum split level is at least one, consider splitting the
+ * block in two. */
+ if (max_split_level--) {
+
+ LZX_DEBUG("Calculating split of block %u...", block_number);
+
+ struct lzx_block_spec *spec1, *spec2;
+ unsigned split_cost;
+
+ ctx->cached_matches_pos = orig_cached_matches_pos;
+ ctx->queue = orig_queue;
+
+ /* Prepare and get the cost of the first sub-block. */
+ spec1 = &ctx->block_specs[block_number * 2 - 1];
+ spec1->codes.lens = spec->codes.lens;
+ spec1->window_pos = spec->window_pos;
+ spec1->block_size = spec->block_size / 2;
+ spec1->chosen_matches_start_pos = spec->chosen_matches_start_pos +
+ LZX_MAX_WINDOW_SIZE;
+ split_cost = lzx_prepare_block_recursive(ctx,
+ block_number * 2,
+ max_split_level,
+ &prev_codes);
+
+ /* Prepare and get the cost of the second sub-block. */
+ spec2 = spec1 + 1;
+ spec2->codes.lens = spec->codes.lens;
+ spec2->window_pos = spec->window_pos + spec1->block_size;
+ spec2->block_size = spec->block_size - spec1->block_size;
+ spec2->chosen_matches_start_pos = spec1->chosen_matches_start_pos +
+ spec1->block_size;
+ split_cost += lzx_prepare_block_recursive(ctx,
+ block_number * 2 + 1,
+ max_split_level,
+ &prev_codes);
+
+ /* Compare the cost of the whole block with that of the split
+ * block. Choose the lower cost solution. */
+ if (split_cost < cost) {
+ LZX_DEBUG("Splitting block %u is worth it "
+ "(%u => %u bytes).",
+ block_number, cost / 8, split_cost / 8);
+ spec->is_split = 1;
+ cost = split_cost;
+ *prev_codes_p = prev_codes;
+ } else {
+ LZX_DEBUG("Splitting block %u is NOT worth it "
+ "(%u => %u bytes).",
+ block_number, cost / 8, split_cost / 8);
+ ctx->queue = nonsplit_queue;
+ }
+ }
+
+ return cost;
+}
+
+/* Empirical averages */
+static const u8 lzx_default_mainsym_costs[LZX_MAINTREE_NUM_SYMBOLS] = {
+ 7, 9, 9, 10, 9, 10, 10, 10, 9, 10, 9, 10, 10, 9, 10, 10, 9, 10, 10, 11,
+ 10, 10, 10, 11, 10, 11, 11, 11, 10, 11, 11, 11, 8, 11, 9, 10, 9, 10, 11,
+ 11, 9, 9, 11, 10, 10, 9, 9, 9, 8, 8, 8, 8, 8, 9, 9, 9, 8, 8, 9, 9, 9, 9,
+ 10, 10, 10, 8, 9, 8, 8, 8, 8, 9, 9, 9, 10, 10, 8, 8, 9, 9, 8, 10, 9, 8,
+ 8, 9, 8, 9, 9, 10, 10, 10, 9, 10, 11, 9, 10, 8, 9, 8, 8, 8, 8, 9, 8, 8,
+ 9, 9, 8, 8, 8, 8, 8, 10, 8, 8, 7, 8, 9, 9, 9, 9, 10, 11, 10, 10, 11, 11,
+ 10, 11, 11, 10, 10, 11, 11, 11, 10, 10, 11, 10, 11, 10, 11, 11, 10, 11,
+ 11, 12, 11, 11, 11, 12, 11, 11, 11, 11, 11, 11, 11, 12, 10, 11, 11, 11,
+ 11, 11, 11, 12, 11, 11, 11, 11, 11, 12, 11, 11, 10, 11, 11, 11, 11, 11,
+ 11, 11, 10, 11, 11, 11, 11, 11, 11, 11, 10, 11, 11, 11, 11, 11, 11, 11,
+ 10, 11, 11, 11, 11, 11, 11, 11, 10, 11, 11, 11, 11, 12, 11, 11, 10, 11,
+ 11, 11, 11, 12, 11, 11, 10, 11, 11, 11, 10, 12, 11, 11, 10, 10, 11, 10,
+ 10, 11, 11, 11, 10, 11, 11, 11, 10, 11, 11, 11, 10, 11, 11, 11, 10, 11,
+ 10, 9, 8, 7, 10, 10, 11, 10, 11, 7, 9, 9, 11, 11, 11, 12, 11, 9, 10, 10,
+ 12, 12, 13, 13, 12, 11, 10, 12, 12, 14, 14, 14, 13, 12, 9, 12, 13, 14,
+ 14, 14, 14, 14, 9, 10, 13, 14, 14, 14, 14, 14, 9, 9, 11, 11, 13, 13, 13,
+ 14, 9, 9, 11, 12, 12, 13, 13, 13, 8, 8, 11, 11, 12, 12, 12, 11, 9, 9,
+ 10, 11, 12, 12, 12, 11, 8, 9, 10, 10, 11, 12, 11, 10, 9, 9, 10, 11, 11,
+ 12, 11, 10, 8, 9, 10, 10, 11, 11, 11, 9, 9, 9, 10, 11, 11, 11, 11, 9, 8,
+ 8, 10, 10, 11, 11, 11, 9, 9, 9, 10, 10, 11, 11, 11, 9, 9, 8, 9, 10, 11,
+ 11, 11, 9, 10, 9, 10, 11, 11, 11, 11, 9, 14, 9, 9, 10, 10, 11, 10, 9,
+ 14, 9, 10, 11, 11, 11, 11, 9, 14, 9, 10, 10, 11, 11, 11, 9, 14, 10, 10,
+ 11, 11, 12, 11, 10, 14, 10, 10, 10, 11, 11, 11, 10, 14, 11, 11, 11, 11,
+ 12, 12, 10, 14, 10, 11, 11, 11, 12, 11, 10, 14, 11, 11, 11, 12, 12, 12,
+ 11, 15, 11, 11, 11, 12, 12, 12, 11, 14, 12, 12, 12, 12, 13, 12, 11, 15,
+ 12, 12, 12, 13, 13, 13, 12, 15, 14, 13, 14, 14, 14, 14, 13,
+};
+
+/* Empirical averages */
+static const u8 lzx_default_lensym_costs[LZX_LENTREE_NUM_SYMBOLS] = {
+ 5, 5, 5, 5, 5, 6, 5, 5, 6, 7, 7, 7, 8, 8, 7, 8, 9, 9, 9, 9, 10, 9, 9,
+ 10, 9, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 12, 12, 12, 11, 12, 12,
+ 12, 12, 12, 12, 13, 12, 12, 12, 13, 12, 13, 13, 12, 12, 13, 12, 13, 13,
+ 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 14, 13, 14, 13, 14, 13,
+ 14, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
+ 14, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
+ 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
+ 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
+ 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
+ 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
+ 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
+ 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
+ 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
+ 14, 14, 14, 14, 14, 14, 14, 14, 14, 10,
+};
+
+/*
+ * Set default symbol costs.
+ */
+static void
+lzx_set_default_costs(struct lzx_lens * lens)
+{
+ unsigned i;
+
+#if LZX_PARAM_USE_EMPIRICAL_DEFAULT_COSTS
+ memcpy(&lens->main, lzx_default_mainsym_costs, LZX_MAINTREE_NUM_SYMBOLS);
+ memcpy(&lens->len, lzx_default_lensym_costs, LZX_LENTREE_NUM_SYMBOLS);
+
+#else
+ /* Literal symbols */
+ for (i = 0; i < LZX_NUM_CHARS; i++)
+ lens->main[i] = 8;
+
+ /* Match header symbols */
+ for (; i < LZX_MAINTREE_NUM_SYMBOLS; i++)
+ lens->main[i] = 10;
+
+ /* Length symbols */
+ for (i = 0; i < LZX_LENTREE_NUM_SYMBOLS; i++)
+ lens->len[i] = 8;
+#endif
+
+ /* Aligned offset symbols */
+ for (i = 0; i < LZX_ALIGNEDTREE_NUM_SYMBOLS; i++)
+ lens->aligned[i] = 3;
+}
+
+/*
+ * lzx_prepare_blocks() -
+ *
+ * Calculate the blocks to split the preprocessed data into.
+ *
+ * Input --- the preprocessed data:
+ *
+ * ctx->window[]
+ * ctx->window_size
+ *
+ * Working space:
+ * Match finding:
+ * ctx->hash_tab
+ * ctx->child_tab
+ * ctx->cached_matches
+ * ctx->cached_matches_pos
+ * ctx->matches_already_found
+ *
+ * Block cost modeling:
+ * ctx->costs
+ * ctx->block_specs (also an output)
+ *
+ * Match choosing:
+ * ctx->optimum
+ * ctx->optimum_cur_idx
+ * ctx->optimum_end_idx
+ * ctx->chosen_matches (also an output)
+ *
+ * Output --- the block specifications and the corresponding match/literal data:
+ *
+ * ctx->block_specs[]
+ * ctx->chosen_matches[]
+ *
+ * The return value is the approximate number of bits the compressed data will
+ * take up.
+ */
+static unsigned
+lzx_prepare_blocks(struct lzx_compressor * ctx)
+{
+ /* This function merely does some initializations, then passes control
+ * to lzx_prepare_block_recursive(). */
+
+ /* 1. Initialize match-finding variables. */
+
+ /* Zero all entries in the hash table, indicating that no length-3
+ * character sequences have been discovered in the input yet. */
+ memset(ctx->hash_tab, 0, LZX_LZ_HASH_SIZE * 2 * sizeof(ctx->hash_tab[0]));
+ if (ctx->params.slow.use_len2_matches)
+ memset(ctx->digram_tab, 0, 256 * 256 * sizeof(ctx->digram_tab[0]));
+ /* Note: ctx->child_tab need not be initialized. */
+
+ /* No matches have been found and cached yet. */
+ ctx->cached_matches_pos = 0;
+ ctx->matches_already_found = false;
+
+ /* 2. Initialize match-choosing variables. */
+ ctx->optimum_cur_idx = 0;
+ ctx->optimum_end_idx = 0;
+ /* Note: ctx->optimum need not be initialized. */
+ ctx->block_specs[0].chosen_matches_start_pos = 0;
+
+ /* 3. Set block 1 (index 0) to represent the entire input data. */
+ ctx->block_specs[0].block_size = ctx->window_size;
+ ctx->block_specs[0].window_pos = 0;
+
+ /* 4. Set up a default Huffman symbol cost model for block 1 (index 0).
+ * The model will be refined later. */
+ lzx_set_default_costs(&ctx->block_specs[0].codes.lens);
+
+ /* 5. Initialize the match offset LRU queue. */
+ ctx->queue = (struct lzx_lru_queue){1, 1, 1};
+
+ /* 6. Pass control to recursive procedure. */
+ struct lzx_codes * prev_codes = &ctx->zero_codes;
+ return lzx_prepare_block_recursive(ctx, 1,
+ ctx->params.slow.num_split_passes,
+ &prev_codes);
+}
+
+/*
+ * This is the fast version of lzx_prepare_blocks(). This version "quickly"
+ * prepares a single compressed block containing the entire input. See the
+ * description of the "Fast algorithm" at the beginning of this file for more
+ * information.
+ *
+ * Input --- the preprocessed data:
+ *
+ * ctx->window[]
+ * ctx->window_size
+ *
+ * Working space:
+ * ctx->queue
+ *
+ * Output --- the block specifications and the corresponding match/literal data:
+ *
+ * ctx->block_specs[]
+ * ctx->chosen_matches[]
+ */
+static void
+lzx_prepare_block_fast(struct lzx_compressor * ctx)
+{
+ unsigned num_matches;
+ struct lzx_freqs freqs;
+ struct lzx_block_spec *spec;
+
+ /* Parameters to hash chain LZ match finder */
+ static const struct lz_params lzx_lz_params = {
+ /* LZX_MIN_MATCH == 2, but 2-character matches are rarely
+ * useful; the minimum match for compression is set to 3
+ * instead. */
+ .min_match = 3,
+ .max_match = LZX_MAX_MATCH,
+ .good_match = LZX_MAX_MATCH,
+ .nice_match = LZX_MAX_MATCH,
+ .max_chain_len = LZX_MAX_MATCH,
+ .max_lazy_match = LZX_MAX_MATCH,
+ .too_far = 4096,
+ };
+
+ /* Initialize symbol frequencies and match offset LRU queue. */
+ memset(&freqs, 0, sizeof(struct lzx_freqs));
+ ctx->queue = (struct lzx_lru_queue){ 1, 1, 1 };
+
+ /* Determine series of matches/literals to output. */
+ num_matches = lz_analyze_block(ctx->window,
+ ctx->window_size,
+ (u32*)ctx->chosen_matches,
+ lzx_record_match,
+ lzx_record_literal,
+ &freqs,
+ &ctx->queue,
+ &freqs,
+ &lzx_lz_params);
+
+
+ /* Set up block specification. */
+ spec = &ctx->block_specs[0];
+ spec->is_split = 0;
+ spec->block_type = LZX_BLOCKTYPE_ALIGNED;
+ spec->window_pos = 0;
+ spec->block_size = ctx->window_size;
+ spec->num_chosen_matches = num_matches;
+ spec->chosen_matches_start_pos = 0;
+ lzx_make_huffman_codes(&freqs, &spec->codes);
+}
+
+static void
+do_call_insn_translation(u32 *call_insn_target, int input_pos,
+ s32 file_size)
+{
+ s32 abs_offset;
+ s32 rel_offset;