-
- /* Account for the main symbol. */
- main_symbol = ((position_slot << 3) | len_header) + LZX_NUM_CHARS;
-
- freqs->main[main_symbol]++;
-
- /* In an aligned offset block, 3 bits of the position footer are output
- * as an aligned offset symbol. Account for this, although we may
- * ultimately decide to output the block as verbatim. */
-
- /* The following check is equivalent to:
- *
- * if (lzx_extra_bits[position_slot] >= 3)
- *
- * Note that this correctly excludes position slots that correspond to
- * recent offsets. */
- if (position_slot >= 8)
- freqs->aligned[position_footer & 7]++;
-
- /* Pack the position slot, position footer, and match length into an
- * intermediate representation. See `struct lzx_item' for details.
- */
- LZX_ASSERT(LZX_MAX_POSITION_SLOTS <= 64);
- LZX_ASSERT(lzx_get_num_extra_bits(LZX_MAX_POSITION_SLOTS - 1) <= 17);
- LZX_ASSERT(LZX_MAX_MATCH_LEN - LZX_MIN_MATCH_LEN + 1 <= 256);
-
- LZX_ASSERT(position_slot <= (1U << (31 - 25)) - 1);
- LZX_ASSERT(position_footer <= (1U << (25 - 8)) - 1);
- LZX_ASSERT(adjusted_match_len <= (1U << (8 - 0)) - 1);
- return 0x80000000 |
- (position_slot << 25) |
- (position_footer << 8) |
- (adjusted_match_len);
-}
-
-/* Returns the cost, in bits, to output a literal byte using the specified cost
- * model. */
-static u32
-lzx_literal_cost(u8 c, const struct lzx_costs * 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. Take into account the match offset LRU
- * queue and also updates it. */
-static u32
-lzx_match_cost(unsigned length, u32 offset, const struct lzx_costs *costs,
- struct lzx_lru_queue *queue)
-{
- unsigned position_slot;
- unsigned len_header, main_symbol;
- unsigned num_extra_bits;
- u32 cost = 0;
-
- position_slot = lzx_get_position_slot(offset, queue);
-
- len_header = min(length - LZX_MIN_MATCH_LEN, 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. */
- 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_OFFSET_OFFSET) & 7];
- } else {
- cost += num_extra_bits;
- }
-
- /* Account for extra length information. */
- if (len_header == LZX_NUM_PRIMARY_LENS)
- cost += costs->len[length - LZX_MIN_MATCH_LEN - LZX_NUM_PRIMARY_LENS];
-
- return cost;
-
-}
-
-
-/* Set the cost model @c->costs from the Huffman codeword lengths specified in
- * @lens.
- *
- * The cost model and codeword lengths are almost the same thing, but 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 *c, const struct lzx_lens * lens,
- unsigned nostat)
-{
- unsigned i;
-
- /* Main code */
- for (i = 0; i < c->num_main_syms; i++)
- c->costs.main[i] = lens->main[i] ? lens->main[i] : nostat;
-
- /* Length code */
- for (i = 0; i < LZX_LENCODE_NUM_SYMBOLS; i++)
- c->costs.len[i] = lens->len[i] ? lens->len[i] : nostat;
-
- /* Aligned offset code */
- for (i = 0; i < LZX_ALIGNEDCODE_NUM_SYMBOLS; i++)
- c->costs.aligned[i] = lens->aligned[i] ? lens->aligned[i] : nostat / 2;
-}
-
-/* Don't allow matches to span the end of an LZX block. */
-static inline u32
-maybe_truncate_matches(struct lz_match matches[], u32 num_matches,
- struct lzx_compressor *c)
-{
- if (c->match_window_end < c->cur_window_size && num_matches != 0) {
- u32 limit = c->match_window_end - c->match_window_pos;
-
- if (limit >= LZX_MIN_MATCH_LEN) {
-
- u32 i = num_matches - 1;
- do {
- if (matches[i].len >= limit) {
- matches[i].len = limit;
-
- /* Truncation might produce multiple
- * matches with length 'limit'. Keep at
- * most 1. */
- num_matches = i + 1;
- }
- } while (i--);
- } else {
- num_matches = 0;
- }
- }
- return num_matches;
-}
-
-static unsigned
-lzx_get_matches_fillcache_singleblock(struct lzx_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->match_window_pos++;
- *matches_ret = matches;
- return num_matches;
-}