X-Git-Url: https://wimlib.net/git/?a=blobdiff_plain;f=include%2Fwimlib%2Flzms.h;h=94bcba826f772e1af34a15ca35638964588a5aab;hb=e6a50e92c221b5c4ce2d86caa1ba2093b20f3ac3;hp=ff3888eb67f1a99098dfb5548ece603f84c3cf82;hpb=637f86d129be63bb9dc431e8e2ead370330ca5ce;p=wimlib diff --git a/include/wimlib/lzms.h b/include/wimlib/lzms.h index ff3888eb..94bcba82 100644 --- a/include/wimlib/lzms.h +++ b/include/wimlib/lzms.h @@ -1,54 +1,26 @@ +/* + * 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_DEBUG DEBUG # define LZMS_ASSERT wimlib_assert +# include "wimlib/assert.h" +# include "wimlib/error.h" #else # define LZMS_DEBUG(format, ...) # define LZMS_ASSERT(...) #endif -#define LZMS_NUM_RECENT_OFFSETS 3 - -#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 - extern void lzms_x86_filter(u8 data[], s32 size, s32 last_target_usages[], bool undo); @@ -57,9 +29,9 @@ struct lzms_probability_entry { /* 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 @@ -101,35 +73,45 @@ struct lzms_lru_queues { struct lzms_delta_lru_queues delta; }; -extern u32 lzms_position_slot_base[LZMS_MAX_NUM_OFFSET_SYMS + 1]; +/* 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]; +extern u8 lzms_extra_length_bits[LZMS_NUM_LEN_SYMS]; extern void -lzms_init_slot_bases(void); +lzms_init_slots(void); -extern u32 +extern unsigned lzms_get_slot(u32 value, const u32 slot_base_tab[], unsigned num_slots); -static inline u32 -lzms_get_position_slot(u32 value) +/* Return the offset slot for the specified offset */ +static inline unsigned +lzms_get_offset_slot(u32 offset) { - return lzms_get_slot(value, lzms_position_slot_base, - LZMS_MAX_NUM_OFFSET_SYMS); + return lzms_get_slot(offset, lzms_offset_slot_base, LZMS_MAX_NUM_OFFSET_SYMS); } -static inline u32 -lzms_get_length_slot(u32 value) +/* Return the length slot for the specified length */ +static inline unsigned +lzms_get_length_slot(u32 length) { - return lzms_get_slot(value, 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); @@ -137,4 +119,36 @@ 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 */