#include "wimlib/endianness.h"
#include "wimlib/error.h"
#include "wimlib/lz_mf.h"
+#include "wimlib/lz_repsearch.h"
#include "wimlib/lzx.h"
#include "wimlib/util.h"
#include <string.h>
/* Allocated size of @cur_window. */
u32 max_window_size;
+ /* log2 order of the LZX window size for LZ match offset encoding
+ * purposes. Will be >= LZX_MIN_WINDOW_ORDER and <=
+ * LZX_MAX_WINDOW_ORDER.
+ *
+ * Note: 1 << @window_order is normally equal to @max_window_size, but
+ * it will be greater than @max_window_size in the event that the
+ * compressor was created with a non-power-of-2 block size. (See
+ * lzx_get_window_order().) */
+ unsigned window_order;
+
/* Compression parameters. */
struct lzx_compressor_params params;
unsigned (*get_matches_func)(struct lzx_compressor *, const struct lz_match **);
void (*skip_bytes_func)(struct lzx_compressor *, unsigned n);
- /* Number of symbols in the main alphabet (depends on the
- * @max_window_size since it determines the maximum allowed offset). */
+ /* Number of symbols in the main alphabet (depends on the @window_order
+ * since it determines the maximum allowed offset). */
unsigned num_main_syms;
/* The current match offset LRU queue. */
static void
lzx_write_compressed_block(int block_type,
u32 block_size,
- u32 max_window_size,
+ unsigned window_order,
unsigned num_main_syms,
struct lzx_item * chosen_items,
u32 num_chosen_items,
} else {
lzx_write_bits(os, 0, 1);
- if (max_window_size >= 65536)
+ if (window_order >= 16)
lzx_write_bits(os, block_size >> 16, 8);
lzx_write_bits(os, block_size & 0xFFFF, 16);
lzx_write_compressed_block(spec->block_type,
spec->block_size,
- c->max_window_size,
+ c->window_order,
c->num_main_syms,
spec->chosen_items,
spec->num_chosen_items,
};
}
+/*
+ * Find the longest repeat offset match.
+ *
+ * If no match of at least LZX_MIN_MATCH_LEN bytes is found, then return 0.
+ *
+ * If a match of at least LZX_MIN_MATCH_LEN bytes is found, then return its
+ * length and set *slot_ret to the index of its offset in @queue.
+ */
+static inline u32
+lzx_repsearch(const u8 * const strptr, const u32 bytes_remaining,
+ const struct lzx_lru_queue *queue, unsigned *slot_ret)
+{
+ BUILD_BUG_ON(LZX_MIN_MATCH_LEN != 2);
+ return lz_repsearch(strptr, bytes_remaining, LZX_MAX_MATCH_LEN,
+ queue->R, LZX_NUM_RECENT_OFFSETS, slot_ret);
+}
+
/*
* lzx_choose_near_optimal_match() -
*
/* Search for matches at repeat offsets. As a heuristic, we only keep
* the one with the longest match length. */
- longest_rep_len = LZX_MIN_MATCH_LEN - 1;
- if (c->match_window_pos >= 1) {
- unsigned limit = min(LZX_MAX_MATCH_LEN,
- c->match_window_end - c->match_window_pos);
- for (int i = 0; i < LZX_NUM_RECENT_OFFSETS; i++) {
- u32 offset = c->queue.R[i];
- const u8 *strptr = &c->cur_window[c->match_window_pos];
- const u8 *matchptr = strptr - offset;
- unsigned len = 0;
- while (len < limit && strptr[len] == matchptr[len])
- len++;
- if (len > longest_rep_len) {
- longest_rep_len = len;
- longest_rep_slot = i;
- }
- }
+ if (likely(c->match_window_pos >= 1)) {
+ longest_rep_len = lzx_repsearch(&c->cur_window[c->match_window_pos],
+ c->match_window_end - c->match_window_pos,
+ &c->queue,
+ &longest_rep_slot);
+ } else {
+ longest_rep_len = 0;
}
/* If there's a long match with a repeat offset, choose it immediately. */
}
end_pos = longest_len;
- if (longest_rep_len >= LZX_MIN_MATCH_LEN) {
+ if (longest_rep_len) {
+
+ LZX_ASSERT(longest_rep_len >= LZX_MIN_MATCH_LEN);
+
u32 cost;
while (end_pos < longest_rep_len)
/* Search for matches at repeat offsets. Again, as a heuristic
* we only keep the longest one. */
- longest_rep_len = LZX_MIN_MATCH_LEN - 1;
- unsigned limit = min(LZX_MAX_MATCH_LEN,
- c->match_window_end - c->match_window_pos);
- for (int i = 0; i < LZX_NUM_RECENT_OFFSETS; i++) {
- u32 offset = optimum[cur_pos].queue.R[i];
- const u8 *strptr = &c->cur_window[c->match_window_pos];
- const u8 *matchptr = strptr - offset;
- unsigned len = 0;
- while (len < limit && strptr[len] == matchptr[len])
- len++;
- if (len > longest_rep_len) {
- longest_rep_len = len;
- longest_rep_slot = i;
- }
- }
+ longest_rep_len = lzx_repsearch(&c->cur_window[c->match_window_pos],
+ c->match_window_end - c->match_window_pos,
+ &optimum[cur_pos].queue,
+ &longest_rep_slot);
/* If we found a long match at a repeat offset, choose it
* immediately. */
* of the longest repeat offset match. Still didn't seem quite
* worth it, though.
*/
- if (longest_rep_len >= LZX_MIN_MATCH_LEN) {
+ if (longest_rep_len) {
+
+ LZX_ASSERT(longest_rep_len >= LZX_MIN_MATCH_LEN);
while (end_pos < cur_pos + longest_rep_len)
optimum[++end_pos].cost = MC_INFINITE_COST;
lzx_free_compressor(void *_c);
static u64
-lzx_get_needed_memory(size_t max_window_size, unsigned int compression_level)
+lzx_get_needed_memory(size_t max_block_size, unsigned int compression_level)
{
struct lzx_compressor_params params;
u64 size = 0;
+ unsigned window_order;
+ u32 max_window_size;
- if (!lzx_window_size_valid(max_window_size))
+ window_order = lzx_get_window_order(max_block_size);
+ if (window_order == 0)
return 0;
+ max_window_size = max_block_size;
lzx_build_params(compression_level, max_window_size, ¶ms);
}
static int
-lzx_create_compressor(size_t max_window_size, unsigned int compression_level,
+lzx_create_compressor(size_t max_block_size, unsigned int compression_level,
void **c_ret)
{
struct lzx_compressor *c;
struct lzx_compressor_params params;
struct lz_mf_params mf_params;
+ unsigned window_order;
+ u32 max_window_size;
- if (!lzx_window_size_valid(max_window_size))
+ window_order = lzx_get_window_order(max_block_size);
+ if (window_order == 0)
return WIMLIB_ERR_INVALID_PARAM;
+ max_window_size = max_block_size;
lzx_build_params(compression_level, max_window_size, ¶ms);
lzx_build_mf_params(¶ms, max_window_size, &mf_params);
goto oom;
c->params = params;
- c->num_main_syms = lzx_get_num_main_syms(max_window_size);
+ c->num_main_syms = lzx_get_num_main_syms(window_order);
c->max_window_size = max_window_size;
+ c->window_order = window_order;
c->cur_window = ALIGNED_MALLOC(max_window_size, 16);
if (!c->cur_window)
git://wimlib.net / wimlib / blobdiff