X-Git-Url: https://wimlib.net/git/?p=wimlib;a=blobdiff_plain;f=src%2Flzms-compress.c;h=5a2e3ed5a1e0453041e2c93568bd74b8c3b0a48a;hp=3169218288c79c676911ea3376be2a3688c4b3e9;hb=027518fa61bd9232ff7fa7ecd270546d920c912f;hpb=95ab133e80c52b6a0b0de85ba172447d5d9b68eb diff --git a/src/lzms-compress.c b/src/lzms-compress.c index 31692182..5a2e3ed5 100644 --- a/src/lzms-compress.c +++ b/src/lzms-compress.c @@ -39,6 +39,8 @@ #include "wimlib/compress_common.h" #include "wimlib/endianness.h" #include "wimlib/error.h" +#include "wimlib/lz_hash.h" +#include "wimlib/lz_sarray.h" #include "wimlib/lzms.h" #include "wimlib/util.h" @@ -173,6 +175,9 @@ struct lzms_compressor { * as the window. */ u32 *prev_tab; + /* Suffix array match-finder. */ + struct lz_sarray lz_sarray; + /* Maximum block size this compressor instantiation allows. This is the * allocated size of @window. */ u32 max_block_size; @@ -200,33 +205,13 @@ struct lzms_compressor { struct lzms_huffman_encoder delta_power_encoder; struct lzms_huffman_encoder delta_offset_encoder; - /* LRU (least-recently-used) queue of LZ match offsets. */ - u64 recent_lz_offsets[LZMS_NUM_RECENT_OFFSETS + 1]; - - /* LRU (least-recently-used) queue of delta match powers. */ - u32 recent_delta_powers[LZMS_NUM_RECENT_OFFSETS + 1]; - - /* LRU (least-recently-used) queue of delta match offsets. */ - u32 recent_delta_offsets[LZMS_NUM_RECENT_OFFSETS + 1]; - - /* These variables are used to delay updates to the LRU queues by one - * decoded item. */ - u32 prev_lz_offset; - u32 prev_delta_power; - u32 prev_delta_offset; - u32 upcoming_lz_offset; - u32 upcoming_delta_power; - u32 upcoming_delta_offset; + /* LRU (least-recently-used) queues for match information. */ + struct lzms_lru_queues lru; /* Used for preprocessing. */ s32 last_target_usages[65536]; }; -struct lzms_match { - u32 length; - u32 offset; -}; - /* Initialize the output bitstream @os to write forwards to the specified * compressed data buffer @out that is @out_limit 16-bit integers long. */ static void @@ -484,9 +469,9 @@ lzms_encode_value(struct lzms_huffman_encoder *enc, u32 value) static void lzms_begin_encode_item(struct lzms_compressor *ctx) { - ctx->upcoming_delta_offset = 0; - ctx->upcoming_lz_offset = 0; - ctx->upcoming_delta_power = 0; + ctx->lru.lz.upcoming_offset = 0; + ctx->lru.delta.upcoming_offset = 0; + ctx->lru.delta.upcoming_power = 0; } static void @@ -494,26 +479,7 @@ lzms_end_encode_item(struct lzms_compressor *ctx, u32 length) { LZMS_ASSERT(ctx->window_size - ctx->cur_window_pos >= length); ctx->cur_window_pos += length; - - /* Update LRU queues */ - if (ctx->prev_lz_offset != 0) { - for (int i = LZMS_NUM_RECENT_OFFSETS - 1; i >= 0; i--) - ctx->recent_lz_offsets[i + 1] = ctx->recent_lz_offsets[i]; - ctx->recent_lz_offsets[0] = ctx->prev_lz_offset; - } - - if (ctx->prev_delta_offset != 0) { - for (int i = LZMS_NUM_RECENT_OFFSETS - 1; i >= 0; i--) { - ctx->recent_delta_powers[i + 1] = ctx->recent_delta_powers[i]; - ctx->recent_delta_offsets[i + 1] = ctx->recent_delta_offsets[i]; - } - ctx->recent_delta_powers[0] = ctx->prev_delta_power; - ctx->recent_delta_offsets[0] = ctx->prev_delta_offset; - } - - ctx->prev_lz_offset = ctx->upcoming_lz_offset; - ctx->prev_delta_offset = ctx->upcoming_delta_offset; - ctx->prev_delta_power = ctx->upcoming_delta_power; + lzms_update_lru_queues(&ctx->lru); } /* Encode a literal byte. */ @@ -555,7 +521,7 @@ lzms_encode_lz_match(struct lzms_compressor *ctx, u32 length, u32 offset) for (recent_offset_idx = 0; recent_offset_idx < LZMS_NUM_RECENT_OFFSETS; recent_offset_idx++) - if (offset == ctx->recent_lz_offsets[recent_offset_idx]) + if (offset == ctx->lru.lz.recent_offsets[recent_offset_idx]) break; if (recent_offset_idx == LZMS_NUM_RECENT_OFFSETS) { @@ -586,7 +552,7 @@ lzms_encode_lz_match(struct lzms_compressor *ctx, u32 length, u32 offset) /* Initial update of the LZ match offset LRU queue. */ for (; i < LZMS_NUM_RECENT_OFFSETS; i++) - ctx->recent_lz_offsets[i] = ctx->recent_lz_offsets[i + 1]; + ctx->lru.lz.recent_offsets[i] = ctx->lru.lz.recent_offsets[i + 1]; } /* Encode the match length. */ @@ -594,23 +560,11 @@ lzms_encode_lz_match(struct lzms_compressor *ctx, u32 length, u32 offset) /* Save the match offset for later insertion at the front of the LZ * match offset LRU queue. */ - ctx->upcoming_lz_offset = offset; + ctx->lru.lz.upcoming_offset = offset; lzms_end_encode_item(ctx, length); } -static struct lzms_match -lzms_get_best_match(struct lzms_compressor *ctx) -{ - struct lzms_match match; - - /* TODO */ - - match.length = 0; - - return match; -} - static void lzms_record_literal(u8 literal, void *_ctx) { @@ -651,25 +605,77 @@ lzms_fast_encode(struct lzms_compressor *ctx) } +/* Fast heuristic cost evaluation to use in the inner loop of the match-finder. + * Unlike lzms_match_cost() which does a true cost evaluation, this simply + * prioritize matches based on their offset. */ +static input_idx_t +lzms_match_cost_fast(input_idx_t length, input_idx_t offset, const void *_lru) +{ + const struct lzms_lz_lru_queues *lru = _lru; + + + /* It seems well worth it to take the time to give priority to recently + * used offsets. */ + for (input_idx_t i = 0; i < LZMS_NUM_RECENT_OFFSETS; i++) + if (offset == lru->recent_offsets[i]) + return i; + + return offset; +} + +static void +lzms_lz_skip_bytes(struct lzms_compressor *ctx, u32 n) +{ + while (n--) + lz_sarray_skip_position(&ctx->lz_sarray); +} + +static struct raw_match +lzms_get_near_optimal_match(struct lzms_compressor *ctx) +{ + struct raw_match matches[10]; + u32 num_matches; + + num_matches = lz_sarray_get_matches(&ctx->lz_sarray, + matches, + lzms_match_cost_fast, + &ctx->lru.lz); + if (num_matches == 0) + return (struct raw_match) { .len = 0 }; + #if 0 + fprintf(stderr, "Pos %u/%u: %u matches\n", + lz_sarray_get_pos(&ctx->lz_sarray) - 1, + ctx->window_size, num_matches); + for (u32 i = 0; i < num_matches; i++) + fprintf(stderr, "\tLen %u Offset %u\n", matches[i].len, matches[i].offset); +#endif + + lzms_lz_skip_bytes(ctx, matches[0].len - 1); + return matches[0]; +} + static void lzms_slow_encode(struct lzms_compressor *ctx) { - struct lzms_match match; + struct raw_match match; + + /* Load window into suffix array match-finder. */ + lz_sarray_load_window(&ctx->lz_sarray, ctx->window, ctx->window_size); /* TODO */ while (ctx->cur_window_pos != ctx->window_size) { - match = lzms_get_best_match(ctx); - if (match.length == 0) { + + match = lzms_get_near_optimal_match(ctx); + if (match.len == 0) { /* Literal */ lzms_encode_literal(ctx, ctx->window[ctx->cur_window_pos]); } else { /* LZ match */ - lzms_encode_lz_match(ctx, match.length, match.offset); + lzms_encode_lz_match(ctx, match.len, match.offset); } } } -#endif static void lzms_init_range_encoder(struct lzms_range_encoder *enc, @@ -709,6 +715,7 @@ lzms_init_compressor(struct lzms_compressor *ctx, const u8 *udata, u32 ulen, /* Copy the uncompressed data into the @ctx->window buffer. */ memcpy(ctx->window, udata, ulen); + memset(&ctx->window[ulen], 0, 8); ctx->cur_window_pos = 0; ctx->window_size = ulen; @@ -772,20 +779,8 @@ lzms_init_compressor(struct lzms_compressor *ctx, const u8 *udata, u32 ulen, lzms_init_range_encoder(&ctx->delta_repeat_match_range_encoders[i], &ctx->rc, LZMS_NUM_DELTA_REPEAT_MATCH_STATES); - /* Initialize the LRU queue for recent match offsets. */ - for (size_t i = 0; i < LZMS_NUM_RECENT_OFFSETS + 1; i++) - ctx->recent_lz_offsets[i] = i + 1; - - for (size_t i = 0; i < LZMS_NUM_RECENT_OFFSETS + 1; i++) { - ctx->recent_delta_powers[i] = 0; - ctx->recent_delta_offsets[i] = i + 1; - } - ctx->prev_lz_offset = 0; - ctx->prev_delta_offset = 0; - ctx->prev_delta_power = 0; - ctx->upcoming_lz_offset = 0; - ctx->upcoming_delta_offset = 0; - ctx->upcoming_delta_power = 0; + /* Initialize LRU match information. */ + lzms_init_lru_queues(&ctx->lru); } /* Flush the output streams, prepare the final compressed data, and return its @@ -875,7 +870,10 @@ lzms_compress(const void *uncompressed_data, size_t uncompressed_size, /* Determine and output a literal/match sequence that decompresses to * the preprocessed data. */ - lzms_fast_encode(ctx); + if (1) + lzms_slow_encode(ctx); + else + lzms_fast_encode(ctx); /* Get and return the compressed data size. */ compressed_size = lzms_finalize(ctx, compressed_data, @@ -941,6 +939,7 @@ lzms_free_compressor(void *_ctx) if (ctx) { FREE(ctx->window); FREE(ctx->prev_tab); + lz_sarray_destroy(&ctx->lz_sarray); FREE(ctx); } } @@ -961,7 +960,7 @@ lzms_create_compressor(size_t max_block_size, if (ctx == NULL) goto oom; - ctx->window = MALLOC(max_block_size); + ctx->window = MALLOC(max_block_size + 8); if (ctx->window == NULL) goto oom; @@ -969,6 +968,15 @@ lzms_create_compressor(size_t max_block_size, if (ctx->prev_tab == NULL) goto oom; + if (!lz_sarray_init(&ctx->lz_sarray, + max_block_size, + 2, + max_block_size, + 100, + 10)) + goto oom; + + ctx->max_block_size = max_block_size; *ctx_ret = ctx;