* cache. However, fallback behavior (immediately terminating the block) on
* cache overflow is still required.
*/
-#define LZX_CACHE_PER_POS 6
+#define LZX_CACHE_PER_POS 7
/*
* LZX_CACHE_LENGTH is the number of lz_match structures in the match cache,
/*
* LZX_BIT_COST is a scaling factor that represents the cost to output one bit.
- * THis makes it possible to consider fractional bit costs.
+ * This makes it possible to consider fractional bit costs.
*
* Note: this is only useful as a statistical trick for when the true costs are
* unknown. In reality, each token in LZX requires a whole number of bits to
#define LZX_CONSIDER_ALIGNED_COSTS 0
/*
- * The maximum compression level at which we use the faster algorithm.
+ * LZX_MAX_FAST_LEVEL is the maximum compression level at which we use the
+ * faster algorithm.
*/
#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 actually speeds up
+ * hash function is trivial), but using a smaller hash table speeds up
* compression due to reduced cache pressure.
*/
#define LZX_HASH2_ORDER 12
#include "wimlib/bt_matchfinder.h"
#include "wimlib/compress_common.h"
#include "wimlib/compressor_ops.h"
-#include "wimlib/endianness.h"
#include "wimlib/error.h"
#include "wimlib/hc_matchfinder.h"
#include "wimlib/lz_extend.h"
/* Pointer to the compress() implementation chosen at allocation time */
void (*impl)(struct lzx_compressor *, struct lzx_output_bitstream *);
+ /* If true, the compressor need not preserve the input buffer if it
+ * compresses the data successfully. */
+ bool destructive;
+
/* The Huffman symbol frequency counters for the current block. */
struct lzx_freqs freqs;
* contains the number of matches that were found at
* that position; this is followed by the matches
* themselves, if any, sorted by strictly increasing
- * length and strictly increasing offset.
+ * length.
*
* Note: in rare cases, there will be a very high number
* of matches in the block and this array will overflow.
};
};
-/* Compute a hash value for the next 2 bytes of uncompressed data. */
-static inline u32
-lz_hash_2_bytes(const u8 *in_next)
-{
- u16 next_2_bytes = load_u16_unaligned(in_next);
- if (LZX_HASH2_ORDER == 16)
- return next_2_bytes;
- else
- return lz_hash(next_2_bytes, LZX_HASH2_ORDER);
-}
-
/*
* Structure to keep track of the current state of sending bits to the
* compressed output buffer.
u32 bitcount;
/* Pointer to the start of the output buffer. */
- le16 *start;
+ u8 *start;
/* Pointer to the position in the output buffer at which the next coding
* unit should be written. */
- le16 *next;
+ u8 *next;
- /* Pointer past the end of the output buffer. */
- le16 *end;
+ /* Pointer just past the end of the output buffer, rounded down to a
+ * 2-byte boundary. */
+ u8 *end;
};
/*
os->bitcount = 0;
os->start = buffer;
os->next = os->start;
- os->end = os->start + size / sizeof(le16);
+ os->end = os->start + (size & ~1);
}
/*
* bits in @bits cannot be set. At most 17 bits can be written at once.
*
* @max_num_bits is a compile-time constant that specifies the maximum number of
- * bits that can ever be written at the call site. Currently, it is used to
- * optimize away the conditional code for writing a second 16-bit coding unit
- * when writing fewer than 17 bits.
+ * bits that can ever be written at the call site. It is used to optimize away
+ * the conditional code for writing a second 16-bit coding unit when writing
+ * fewer than 17 bits.
*
* If the output buffer space is exhausted, then the bits will be ignored, and
* lzx_flush_output() will return 0 when it gets called.
os->bitcount -= 16;
/* Write a coding unit, unless it would overflow the buffer. */
- if (os->next != os->end)
- put_unaligned_u16_le(os->bitbuf >> os->bitcount, os->next++);
+ if (os->next != os->end) {
+ put_unaligned_u16_le(os->bitbuf >> os->bitcount, os->next);
+ os->next += 2;
+ }
/* If writing 17 bits, a second coding unit might need to be
* written. But because 'max_num_bits' is a compile-time
* constant, the compiler will optimize away this code at most
* call sites. */
if (max_num_bits == 17 && os->bitcount == 16) {
- if (os->next != os->end)
- put_unaligned_u16_le(os->bitbuf, os->next++);
+ if (os->next != os->end) {
+ put_unaligned_u16_le(os->bitbuf, os->next);
+ os->next += 2;
+ }
os->bitcount = 0;
}
}
/* Use when @num_bits is a compile-time constant. Otherwise use
* lzx_write_varbits(). */
static inline void
-lzx_write_bits(struct lzx_output_bitstream *os,
- const u32 bits, const unsigned num_bits)
+lzx_write_bits(struct lzx_output_bitstream *os, u32 bits, unsigned num_bits)
{
lzx_write_varbits(os, bits, num_bits, num_bits);
}
if (os->next == os->end)
return 0;
- if (os->bitcount != 0)
- put_unaligned_u16_le(os->bitbuf << (16 - os->bitcount), os->next++);
+ if (os->bitcount != 0) {
+ put_unaligned_u16_le(os->bitbuf << (16 - os->bitcount), os->next);
+ os->next += 2;
+ }
- return (const u8 *)os->next - (const u8 *)os->start;
+ return os->next - os->start;
}
/* Build the main, length, and aligned offset Huffman codes used in LZX.
* Also, note that because of the presence of the recent offsets queue (which is
* a type of adaptive state), the algorithm cannot work backwards and compute
* "cost to end" instead of "cost to beginning". Furthermore, the way the
- * algorithm handles this adaptive state in the "minimum-cost" parse is actually
+ * algorithm handles this adaptive state in the "minimum cost" parse is actually
* only an approximation. It's possible for the globally optimal, minimum cost
* path to contain a prefix, ending at a position, where that path prefix is
* *not* the minimum cost path to that position. This can happen if such a path
}
} while (cur_node != end_node);
- /* Return the match offset queue at the end of the minimum-cost path. */
+ /* Return the match offset queue at the end of the minimum cost path. */
return QUEUE(block_end);
}
max_len = in_end - in_next;
nice_len = min(max_len, nice_len);
- /* This extra check is needed to ensure that
- * reading the next 3 bytes when looking for a
- * length 2 match is valid. In addition, we
- * cannot allow ourselves to find 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 <
- max(LZ_HASH_REQUIRED_NBYTES, 3)))
- {
+ /* 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)) {
in_next++;
cache_ptr->length = 0;
cache_ptr++;
lz_matchptr = cache_ptr + 1;
/* Check for a length 2 match. */
- hash2 = lz_hash_2_bytes(in_next);
+ 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 (matchfinder_node_valid(cur_match) &&
(LZX_HASH2_ORDER == 16 ||
load_u16_unaligned(&in_begin[cur_match]) ==
- load_u16_unaligned(in_next)) &&
- in_begin[cur_match + 2] != in_next[2])
+ load_u16_unaligned(in_next)))
{
lz_matchptr->length = 2;
lz_matchptr->offset = in_next - &in_begin[cur_match];
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 <
- max(LZ_HASH_REQUIRED_NBYTES, 3)))
- {
+ if (unlikely(max_len < 3)) {
in_next++;
cache_ptr->length = 0;
cache_ptr++;
continue;
}
}
- c->hash2_tab[lz_hash_2_bytes(in_next)] =
+ c->hash2_tab[lz_hash_2_bytes(in_next, LZX_HASH2_ORDER)] =
in_next - in_begin;
bt_matchfinder_skip_position(&c->bt_mf,
in_begin,
}
static u64
-lzx_get_needed_memory(size_t max_bufsize, unsigned compression_level)
+lzx_get_needed_memory(size_t max_bufsize, unsigned compression_level,
+ bool destructive)
{
u64 size = 0;
return 0;
size += lzx_get_compressor_size(max_bufsize, compression_level);
- size += max_bufsize; /* in_buffer */
+ if (!destructive)
+ size += max_bufsize; /* in_buffer */
return size;
}
static int
lzx_create_compressor(size_t max_bufsize, unsigned compression_level,
- void **c_ret)
+ bool destructive, void **c_ret)
{
unsigned window_order;
struct lzx_compressor *c;
if (!c)
goto oom0;
+ c->destructive = destructive;
+
c->num_main_syms = lzx_get_num_main_syms(window_order);
c->window_order = window_order;
- c->in_buffer = MALLOC(max_bufsize);
- if (!c->in_buffer)
- goto oom1;
+ if (!c->destructive) {
+ c->in_buffer = MALLOC(max_bufsize);
+ if (!c->in_buffer)
+ goto oom1;
+ }
if (compression_level <= LZX_MAX_FAST_LEVEL) {
{
struct lzx_compressor *c = _c;
struct lzx_output_bitstream os;
+ size_t result;
/* Don't bother trying to compress very small inputs. */
if (in_nbytes < 100)
return 0;
/* Copy the input data into the internal buffer and preprocess it. */
- memcpy(c->in_buffer, in, in_nbytes);
+ if (c->destructive)
+ c->in_buffer = (void *)in;
+ else
+ memcpy(c->in_buffer, in, in_nbytes);
c->in_nbytes = in_nbytes;
lzx_do_e8_preprocessing(c->in_buffer, in_nbytes);
(*c->impl)(c, &os);
/* Flush the output bitstream and return the compressed size or 0. */
- return lzx_flush_output(&os);
+ result = lzx_flush_output(&os);
+ if (!result && c->destructive)
+ lzx_undo_e8_preprocessing(c->in_buffer, c->in_nbytes);
+ return result;
}
static void
{
struct lzx_compressor *c = _c;
- FREE(c->in_buffer);
+ if (!c->destructive)
+ FREE(c->in_buffer);
ALIGNED_FREE(c);
}
git://wimlib.net / wimlib / blobdiff