X-Git-Url: https://wimlib.net/git/?p=wimlib;a=blobdiff_plain;f=src%2Flzx_compress.c;h=47d8bf0be9714e7fe1a9a1f846d6f1cf9f92cff7;hp=ac65c5dcaf15f7aa01a8803dbb578472524da08f;hb=4b076a156796c1c0358c2e7e3c6610a2e772dd49;hpb=7e71e0ea5e7c2958cef2cc3522367a7da82e4728 diff --git a/src/lzx_compress.c b/src/lzx_compress.c index ac65c5dc..47d8bf0b 100644 --- a/src/lzx_compress.c +++ b/src/lzx_compress.c @@ -114,10 +114,9 @@ #define LZX_BIT_COST 16 /* - * Consideration of aligned offset costs is disabled for now, due to - * insufficient benefit gained from the time spent. + * Should the compressor take into account the costs of aligned offset symbols? */ -#define LZX_CONSIDER_ALIGNED_COSTS 0 +#define LZX_CONSIDER_ALIGNED_COSTS 1 /* * LZX_MAX_FAST_LEVEL is the maximum compression level at which we use the @@ -126,13 +125,12 @@ #define LZX_MAX_FAST_LEVEL 34 /* - * LZX_HASH2_ORDER is the log base 2 of the number of entries in the hash table - * for finding length 2 matches. This can be as high as 16 (in which case the - * hash function is trivial), but using a smaller hash table speeds up - * compression due to reduced cache pressure. + * BT_MATCHFINDER_HASH2_ORDER is the log base 2 of the number of entries in the + * hash table for finding length 2 matches. This could be as high as 16, but + * using a smaller hash table speeds up compression due to reduced cache + * pressure. */ -#define LZX_HASH2_ORDER 12 -#define LZX_HASH2_LENGTH (1UL << LZX_HASH2_ORDER) +#define BT_MATCHFINDER_HASH2_ORDER 12 /* * These are the compressor-side limits on the codeword lengths for each Huffman @@ -154,16 +152,16 @@ #include "wimlib/util.h" /* Matchfinders with 16-bit positions */ -#define pos_t u16 -#define MF_SUFFIX _16 +#define mf_pos_t u16 +#define MF_SUFFIX _16 #include "wimlib/bt_matchfinder.h" #include "wimlib/hc_matchfinder.h" /* Matchfinders with 32-bit positions */ -#undef pos_t +#undef mf_pos_t #undef MF_SUFFIX -#define pos_t u32 -#define MF_SUFFIX _32 +#define mf_pos_t u32 +#define MF_SUFFIX _32 #include "wimlib/bt_matchfinder.h" #include "wimlib/hc_matchfinder.h" @@ -485,9 +483,6 @@ struct lzx_compressor { LZX_MAX_MATCHES_PER_POS + LZX_MAX_MATCH_LEN - 1]; - /* Hash table for finding length 2 matches */ - u32 hash2_tab[LZX_HASH2_LENGTH]; - /* Binary trees matchfinder (MUST BE LAST!!!) */ union { struct bt_matchfinder_16 bt_mf_16; @@ -1023,9 +1018,6 @@ lzx_write_compressed_block(const u8 *block_begin, const struct lzx_lens * prev_lens, struct lzx_output_bitstream * os) { - LZX_ASSERT(block_type == LZX_BLOCKTYPE_ALIGNED || - block_type == LZX_BLOCKTYPE_VERBATIM); - /* The first three bits indicate the type of block and are one of the * LZX_BLOCKTYPE_* constants. */ lzx_write_bits(os, block_type, 3); @@ -1564,16 +1556,18 @@ lzx_find_min_cost_path(struct lzx_compressor * const restrict c, u32 offset_data = offset + LZX_OFFSET_ADJUSTMENT; unsigned offset_slot = lzx_comp_get_offset_slot(c, offset_data, is_16_bit); + u32 base_cost = cur_node->cost; + + #if LZX_CONSIDER_ALIGNED_COSTS + if (offset_data >= 16) + base_cost += c->costs.aligned[offset_data & + LZX_ALIGNED_OFFSET_BITMASK]; + #endif + do { - u32 cost = cur_node->cost + + u32 cost = base_cost + c->costs.match_cost[offset_slot][ next_len - LZX_MIN_MATCH_LEN]; - #if LZX_CONSIDER_ALIGNED_COSTS - if (lzx_extra_offset_bits[offset_slot] >= - LZX_NUM_ALIGNED_OFFSET_BITS) - cost += c->costs.aligned[offset_data & - LZX_ALIGNED_OFFSET_BITMASK]; - #endif if (cost < (cur_node + next_len)->cost) { (cur_node + next_len)->cost = cost; (cur_node + next_len)->item = @@ -1591,8 +1585,7 @@ lzx_find_min_cost_path(struct lzx_compressor * const restrict c, * of coding the literal is integrated into the queue update * code below. */ literal = *in_next++; - cost = cur_node->cost + - c->costs.main[lzx_main_symbol_for_literal(literal)]; + cost = cur_node->cost + c->costs.main[literal]; /* Advance to the next position. */ cur_node++; @@ -1632,17 +1625,17 @@ lzx_find_min_cost_path(struct lzx_compressor * const restrict c, static void lzx_compute_match_costs(struct lzx_compressor *c) { - unsigned num_offset_slots = lzx_get_num_offset_slots(c->window_order); + unsigned num_offset_slots = (c->num_main_syms - LZX_NUM_CHARS) / LZX_NUM_LEN_HEADERS; struct lzx_costs *costs = &c->costs; for (unsigned offset_slot = 0; offset_slot < num_offset_slots; offset_slot++) { u32 extra_cost = (u32)lzx_extra_offset_bits[offset_slot] * LZX_BIT_COST; - unsigned main_symbol = lzx_main_symbol_for_match(offset_slot, 0); + unsigned main_symbol = LZX_NUM_CHARS + (offset_slot * LZX_NUM_LEN_HEADERS); unsigned i; #if LZX_CONSIDER_ALIGNED_COSTS - if (lzx_extra_offset_bits[offset_slot] >= LZX_NUM_ALIGNED_OFFSET_BITS) + if (offset_slot >= 8) extra_cost -= LZX_NUM_ALIGNED_OFFSET_BITS * LZX_BIT_COST; #endif @@ -1785,14 +1778,12 @@ lzx_compress_near_optimal(struct lzx_compressor *c, const u8 * const in_begin = c->in_buffer; const u8 * in_next = in_begin; const u8 * const in_end = in_begin + c->in_nbytes; - unsigned max_len = LZX_MAX_MATCH_LEN; - unsigned nice_len = min(c->nice_match_length, max_len); - u32 next_hash; + u32 max_len = LZX_MAX_MATCH_LEN; + u32 nice_len = min(c->nice_match_length, max_len); + u32 next_hashes[2] = {}; struct lzx_lru_queue queue; CALL_BT_MF(is_16_bit, c, bt_matchfinder_init); - memset(c->hash2_tab, 0, sizeof(c->hash2_tab)); - next_hash = bt_matchfinder_hash_3_bytes(in_next); lzx_lru_queue_init(&queue); do { @@ -1805,22 +1796,14 @@ lzx_compress_near_optimal(struct lzx_compressor *c, struct lz_match *cache_ptr = c->match_cache; do { struct lz_match *lz_matchptr; - u32 hash2; - pos_t cur_match; - unsigned best_len; + u32 best_len; /* If approaching the end of the input buffer, adjust * 'max_len' and 'nice_len' accordingly. */ if (unlikely(max_len > in_end - in_next)) { max_len = in_end - in_next; nice_len = min(max_len, nice_len); - - /* This extra check is needed to ensure that we - * never output a length 2 match of the very - * last two bytes with the very first two bytes, - * since such a match has an offset too large to - * be represented. */ - if (unlikely(max_len < 3)) { + if (unlikely(max_len < 5)) { in_next++; cache_ptr->length = 0; cache_ptr++; @@ -1828,33 +1811,16 @@ lzx_compress_near_optimal(struct lzx_compressor *c, } } - lz_matchptr = cache_ptr + 1; - - /* Check for a length 2 match. */ - hash2 = lz_hash_2_bytes(in_next, LZX_HASH2_ORDER); - cur_match = c->hash2_tab[hash2]; - c->hash2_tab[hash2] = in_next - in_begin; - if (cur_match != 0 && - (LZX_HASH2_ORDER == 16 || - load_u16_unaligned(&in_begin[cur_match]) == - load_u16_unaligned(in_next))) - { - lz_matchptr->length = 2; - lz_matchptr->offset = in_next - &in_begin[cur_match]; - lz_matchptr++; - } - - /* Check for matches of length >= 3. */ + /* Check for matches. */ lz_matchptr = CALL_BT_MF(is_16_bit, c, bt_matchfinder_get_matches, in_begin, - in_next, - 3, + in_next - in_begin, max_len, nice_len, c->max_search_depth, - &next_hash, + next_hashes, &best_len, - lz_matchptr); + cache_ptr + 1); in_next++; cache_ptr->length = lz_matchptr - (cache_ptr + 1); cache_ptr = lz_matchptr; @@ -1877,22 +1843,20 @@ lzx_compress_near_optimal(struct lzx_compressor *c, if (unlikely(max_len > in_end - in_next)) { max_len = in_end - in_next; nice_len = min(max_len, nice_len); - if (unlikely(max_len < 3)) { + if (unlikely(max_len < 5)) { in_next++; cache_ptr->length = 0; cache_ptr++; continue; } } - c->hash2_tab[lz_hash_2_bytes(in_next, LZX_HASH2_ORDER)] = - in_next - in_begin; CALL_BT_MF(is_16_bit, c, bt_matchfinder_skip_position, in_begin, - in_next, - in_end, + in_next - in_begin, + max_len, nice_len, c->max_search_depth, - &next_hash); + next_hashes); in_next++; cache_ptr->length = 0; cache_ptr++; @@ -1940,7 +1904,6 @@ lzx_find_longest_repeat_offset_match(const u8 * const in_next, unsigned *rep_max_idx_ret) { STATIC_ASSERT(LZX_NUM_RECENT_OFFSETS == 3); - LZX_ASSERT(bytes_remaining >= 2); const unsigned max_len = min(bytes_remaining, LZX_MAX_MATCH_LEN); const u16 next_2_bytes = load_u16_unaligned(in_next); @@ -2294,8 +2257,8 @@ lzx_create_compressor(size_t max_bufsize, unsigned compression_level, c->impl = lzx_compress_lazy_16; else c->impl = lzx_compress_lazy_32; - c->max_search_depth = (36 * compression_level) / 20; - c->nice_match_length = (72 * compression_level) / 20; + c->max_search_depth = (60 * compression_level) / 20; + c->nice_match_length = (80 * compression_level) / 20; /* lzx_compress_lazy() needs max_search_depth >= 2 because it * halves the max_search_depth when attempting a lazy match, and @@ -2314,7 +2277,7 @@ lzx_create_compressor(size_t max_bufsize, unsigned compression_level, /* Scale nice_match_length and max_search_depth with the * compression level. */ c->max_search_depth = (24 * compression_level) / 50; - c->nice_match_length = (32 * compression_level) / 50; + c->nice_match_length = (48 * compression_level) / 50; /* Set a number of optimization passes appropriate for the * compression level. */ @@ -2375,7 +2338,7 @@ lzx_compress(const void *restrict in, size_t in_nbytes, else memcpy(c->in_buffer, in, in_nbytes); c->in_nbytes = in_nbytes; - lzx_do_e8_preprocessing(c->in_buffer, in_nbytes); + lzx_preprocess(c->in_buffer, in_nbytes); /* Initially, the previous Huffman codeword lengths are all zeroes. */ c->codes_index = 0; @@ -2390,7 +2353,7 @@ lzx_compress(const void *restrict in, size_t in_nbytes, /* Flush the output bitstream and return the compressed size or 0. */ result = lzx_flush_output(&os); if (!result && c->destructive) - lzx_undo_e8_preprocessing(c->in_buffer, c->in_nbytes); + lzx_postprocess(c->in_buffer, c->in_nbytes); return result; }