* 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,
#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
#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"
* 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);
}
* 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)))
- {
+ 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,