4 * Declarations shared between LZMS compression and decompression.
10 #include "wimlib/lzms_constants.h"
11 #include "wimlib/util.h"
13 //#define ENABLE_LZMS_DEBUG
14 #ifdef ENABLE_LZMS_DEBUG
15 # define LZMS_DEBUG DEBUG
16 # define LZMS_ASSERT wimlib_assert
17 # include "wimlib/assert.h"
18 # include "wimlib/error.h"
20 # define LZMS_DEBUG(format, ...)
21 # define LZMS_ASSERT(...)
25 lzms_x86_filter(u8 data[], s32 size, s32 last_target_usages[], bool undo);
27 /* Probability entry for use by the range coder when in a specific state. */
28 struct lzms_probability_entry {
30 /* Number of zeroes in the most recent LZMS_PROBABILITY_MAX bits that
31 * have been coded using this probability entry. This is a cached value
32 * because it can be computed as LZMS_PROBABILITY_MAX minus the number
33 * of bits set in the low-order LZMS_PROBABILITY_MAX bits of
35 u32 num_recent_zero_bits;
37 /* The most recent LZMS_PROBABILITY_MAX bits that have been coded using
38 * this probability entry. The size of this variable, in bits, must be
39 * at least LZMS_PROBABILITY_MAX. */
43 /* LRU queues for LZ matches. */
44 struct lzms_lz_lru_queues {
46 /* Recent LZ match offsets */
47 u32 recent_offsets[LZMS_NUM_RECENT_OFFSETS + 1];
49 /* These variables are used to delay updates to the LRU queues by one
55 /* LRU queues for delta matches. */
56 struct lzms_delta_lru_queues {
58 /* Recent delta match powers and offsets */
59 u32 recent_powers[LZMS_NUM_RECENT_OFFSETS + 1];
60 u32 recent_offsets[LZMS_NUM_RECENT_OFFSETS + 1];
62 /* These variables are used to delay updates to the LRU queues by one
70 /* LRU (least-recently-used) queues for match information. */
71 struct lzms_lru_queues {
72 struct lzms_lz_lru_queues lz;
73 struct lzms_delta_lru_queues delta;
76 /* Offset slot tables */
77 extern u32 lzms_offset_slot_base[LZMS_MAX_NUM_OFFSET_SYMS + 1];
78 extern u8 lzms_extra_offset_bits[LZMS_MAX_NUM_OFFSET_SYMS];
80 /* Length slot tables */
81 extern u32 lzms_length_slot_base[LZMS_NUM_LEN_SYMS + 1];
82 extern u8 lzms_extra_length_bits[LZMS_NUM_LEN_SYMS];
85 lzms_init_slots(void);
88 lzms_get_slot(u32 value, const u32 slot_base_tab[], unsigned num_slots);
90 /* Return the offset slot for the specified offset */
91 static inline unsigned
92 lzms_get_offset_slot(u32 offset)
94 return lzms_get_slot(offset, lzms_offset_slot_base, LZMS_MAX_NUM_OFFSET_SYMS);
97 /* Return the length slot for the specified length */
98 static inline unsigned
99 lzms_get_length_slot(u32 length)
101 return lzms_get_slot(length, lzms_length_slot_base, LZMS_NUM_LEN_SYMS);
105 lzms_init_lz_lru_queues(struct lzms_lz_lru_queues *lz);
108 lzms_init_delta_lru_queues(struct lzms_delta_lru_queues *delta);
111 lzms_init_lru_queues(struct lzms_lru_queues *lru);
114 lzms_update_lz_lru_queue(struct lzms_lz_lru_queues *lz);
117 lzms_update_delta_lru_queues(struct lzms_delta_lru_queues *delta);
120 lzms_update_lru_queues(struct lzms_lru_queues *lru);
122 /* Given a decoded bit, update the probability entry. */
124 lzms_update_probability_entry(struct lzms_probability_entry *prob_entry, int bit)
128 BUILD_BUG_ON(LZMS_PROBABILITY_MAX != sizeof(prob_entry->recent_bits) * 8);
130 delta_zero_bits = (s32)(prob_entry->recent_bits >> (LZMS_PROBABILITY_MAX - 1)) - bit;
132 prob_entry->num_recent_zero_bits += delta_zero_bits;
133 prob_entry->recent_bits <<= 1;
134 prob_entry->recent_bits |= bit;
137 /* Given a probability entry, return the chance out of LZMS_PROBABILITY_MAX that
138 * the next decoded bit will be a 0. */
140 lzms_get_probability(const struct lzms_probability_entry *prob_entry)
144 prob = prob_entry->num_recent_zero_bits;
146 /* 0% and 100% probabilities aren't allowed. */
149 if (prob == LZMS_PROBABILITY_MAX)
154 #endif /* _WIMLIB_LZMS_H */