+/*
+ * lzms.h
+ *
+ * Declarations shared between LZMS compression and decompression.
+ */
+
#ifndef _WIMLIB_LZMS_H
#define _WIMLIB_LZMS_H
-/* Constants for the LZMS data compression format. See the comments in
- * lzms-decompress.c for more information about this format. */
+#include "wimlib/lzms_constants.h"
+#include "wimlib/util.h"
//#define ENABLE_LZMS_DEBUG
#ifdef ENABLE_LZMS_DEBUG
# define LZMS_ASSERT(...)
#endif
-#define LZMS_NUM_RECENT_OFFSETS 3
-#define LZMS_MAX_INIT_RECENT_OFFSET (LZMS_NUM_RECENT_OFFSETS + 1)
-
-#define LZMS_PROBABILITY_BITS 6
-#define LZMS_PROBABILITY_MAX (1U << LZMS_PROBABILITY_BITS)
-#define LZMS_INITIAL_PROBABILITY 48
-#define LZMS_INITIAL_RECENT_BITS 0x0000000055555555ULL
-
-#define LZMS_NUM_MAIN_STATES 16
-#define LZMS_NUM_MATCH_STATES 32
-#define LZMS_NUM_LZ_MATCH_STATES 64
-#define LZMS_NUM_LZ_REPEAT_MATCH_STATES 64
-#define LZMS_NUM_DELTA_MATCH_STATES 64
-#define LZMS_NUM_DELTA_REPEAT_MATCH_STATES 64
-#define LZMS_MAX_NUM_STATES 64
-
-#define LZMS_NUM_LITERAL_SYMS 256
-#define LZMS_NUM_LEN_SYMS 54
-#define LZMS_NUM_DELTA_POWER_SYMS 8
-#define LZMS_MAX_NUM_OFFSET_SYMS 799
-#define LZMS_MAX_NUM_SYMS 799
-
-#define LZMS_MAX_CODEWORD_LEN 15
-
-#define LZMS_LITERAL_CODE_REBUILD_FREQ 1024
-#define LZMS_LZ_OFFSET_CODE_REBUILD_FREQ 1024
-#define LZMS_LENGTH_CODE_REBUILD_FREQ 512
-#define LZMS_DELTA_OFFSET_CODE_REBUILD_FREQ 1024
-#define LZMS_DELTA_POWER_CODE_REBUILD_FREQ 512
-
-#define LZMS_X86_MAX_GOOD_TARGET_OFFSET 65535
-#define LZMS_X86_MAX_TRANSLATION_OFFSET 1023
-
-/* Code shared between the LZMS decompressor and compressor. */
-
-#include <wimlib/util.h>
-
extern void
lzms_x86_filter(u8 data[], s32 size, s32 last_target_usages[], bool undo);
/* Number of zeroes in the most recent LZMS_PROBABILITY_MAX bits that
* have been coded using this probability entry. This is a cached value
- * because it can be computed as LZMS_PROBABILITY_MAX minus the Hamming
- * weight of the low-order LZMS_PROBABILITY_MAX bits of @recent_bits.
- * */
+ * because it can be computed as LZMS_PROBABILITY_MAX minus the number
+ * of bits set in the low-order LZMS_PROBABILITY_MAX bits of
+ * @recent_bits. */
u32 num_recent_zero_bits;
/* The most recent LZMS_PROBABILITY_MAX bits that have been coded using
struct lzms_delta_lru_queues delta;
};
-extern u32 lzms_position_slot_base[LZMS_MAX_NUM_OFFSET_SYMS + 1];
-
-extern u8 lzms_extra_position_bits[LZMS_MAX_NUM_OFFSET_SYMS];
-
-extern u16 lzms_order_to_position_slot_bounds[30][2];
+/* Offset slot tables */
+extern u32 lzms_offset_slot_base[LZMS_MAX_NUM_OFFSET_SYMS + 1];
+extern u8 lzms_extra_offset_bits[LZMS_MAX_NUM_OFFSET_SYMS];
+/* Length slot tables */
extern u32 lzms_length_slot_base[LZMS_NUM_LEN_SYMS + 1];
-
-#define LZMS_NUM_FAST_LENGTHS 1024
-extern u8 lzms_length_slot_fast[LZMS_NUM_FAST_LENGTHS];
-
extern u8 lzms_extra_length_bits[LZMS_NUM_LEN_SYMS];
extern void
lzms_init_slots(void);
-/* Return the slot for the specified value. */
-extern u32
-lzms_get_slot(u32 value, const u32 slot_base_tab[], u32 num_slots);
+extern unsigned
+lzms_get_slot(u32 value, const u32 slot_base_tab[], unsigned num_slots);
-static inline u32
-lzms_get_position_slot(u32 position)
+/* Return the offset slot for the specified offset */
+static inline unsigned
+lzms_get_offset_slot(u32 offset)
{
- u32 order = bsr32(position);
- u32 l = lzms_order_to_position_slot_bounds[order][0];
- u32 r = lzms_order_to_position_slot_bounds[order][1];
-
- for (;;) {
- u32 slot = (l + r) / 2;
- if (position >= lzms_position_slot_base[slot]) {
- if (position < lzms_position_slot_base[slot + 1])
- return slot;
- else
- l = slot + 1;
- } else {
- r = slot - 1;
- }
- }
+ return lzms_get_slot(offset, lzms_offset_slot_base, LZMS_MAX_NUM_OFFSET_SYMS);
}
-static inline u32
+/* Return the length slot for the specified length */
+static inline unsigned
lzms_get_length_slot(u32 length)
{
- if (likely(length < LZMS_NUM_FAST_LENGTHS))
- return lzms_length_slot_fast[length];
- else
- return lzms_get_slot(length, lzms_length_slot_base,
- LZMS_NUM_LEN_SYMS);
+ return lzms_get_slot(length, lzms_length_slot_base, LZMS_NUM_LEN_SYMS);
}
+extern void
+lzms_init_lz_lru_queues(struct lzms_lz_lru_queues *lz);
+
+extern void
+lzms_init_delta_lru_queues(struct lzms_delta_lru_queues *delta);
+
extern void
lzms_init_lru_queues(struct lzms_lru_queues *lru);
extern void
-lzms_update_lz_lru_queues(struct lzms_lz_lru_queues *lz);
+lzms_update_lz_lru_queue(struct lzms_lz_lru_queues *lz);
extern void
lzms_update_delta_lru_queues(struct lzms_delta_lru_queues *delta);
extern void
lzms_update_lru_queues(struct lzms_lru_queues *lru);
+/* Given a decoded bit, update the probability entry. */
+static inline void
+lzms_update_probability_entry(struct lzms_probability_entry *prob_entry, int bit)
+{
+ s32 delta_zero_bits;
+
+ BUILD_BUG_ON(LZMS_PROBABILITY_MAX != sizeof(prob_entry->recent_bits) * 8);
+
+ delta_zero_bits = (s32)(prob_entry->recent_bits >> (LZMS_PROBABILITY_MAX - 1)) - bit;
+
+ prob_entry->num_recent_zero_bits += delta_zero_bits;
+ prob_entry->recent_bits <<= 1;
+ prob_entry->recent_bits |= bit;
+}
+
+/* Given a probability entry, return the chance out of LZMS_PROBABILITY_MAX that
+ * the next decoded bit will be a 0. */
+static inline u32
+lzms_get_probability(const struct lzms_probability_entry *prob_entry)
+{
+ u32 prob;
+
+ prob = prob_entry->num_recent_zero_bits;
+
+ /* 0% and 100% probabilities aren't allowed. */
+ if (prob == 0)
+ prob++;
+ if (prob == LZMS_PROBABILITY_MAX)
+ prob--;
+ return prob;
+}
+
#endif /* _WIMLIB_LZMS_H */
git://wimlib.net / wimlib / blobdiff