4 /* Constants for the LZMS data compression format. See the comments in
5 * lzms-decompress.c for more information about this format. */
7 //#define ENABLE_LZMS_DEBUG
8 #ifdef ENABLE_LZMS_DEBUG
9 # define LZMS_DEBUG DEBUG
10 # define LZMS_ASSERT wimlib_assert
11 # include "wimlib/assert.h"
12 # include "wimlib/error.h"
14 # define LZMS_DEBUG(format, ...)
15 # define LZMS_ASSERT(...)
18 #define LZMS_NUM_RECENT_OFFSETS 3
20 #define LZMS_PROBABILITY_BITS 6
21 #define LZMS_PROBABILITY_MAX (1U << LZMS_PROBABILITY_BITS)
22 #define LZMS_INITIAL_PROBABILITY 48
23 #define LZMS_INITIAL_RECENT_BITS 0x0000000055555555ULL
25 #define LZMS_NUM_MAIN_STATES 16
26 #define LZMS_NUM_MATCH_STATES 32
27 #define LZMS_NUM_LZ_MATCH_STATES 64
28 #define LZMS_NUM_LZ_REPEAT_MATCH_STATES 64
29 #define LZMS_NUM_DELTA_MATCH_STATES 64
30 #define LZMS_NUM_DELTA_REPEAT_MATCH_STATES 64
31 #define LZMS_MAX_NUM_STATES 64
33 #define LZMS_NUM_LITERAL_SYMS 256
34 #define LZMS_NUM_LEN_SYMS 54
35 #define LZMS_NUM_DELTA_POWER_SYMS 8
36 #define LZMS_MAX_NUM_OFFSET_SYMS 799
37 #define LZMS_MAX_NUM_SYMS 799
39 #define LZMS_MAX_CODEWORD_LEN 15
41 #define LZMS_LITERAL_CODE_REBUILD_FREQ 1024
42 #define LZMS_LZ_OFFSET_CODE_REBUILD_FREQ 1024
43 #define LZMS_LENGTH_CODE_REBUILD_FREQ 512
44 #define LZMS_DELTA_OFFSET_CODE_REBUILD_FREQ 1024
45 #define LZMS_DELTA_POWER_CODE_REBUILD_FREQ 512
47 #define LZMS_X86_MAX_GOOD_TARGET_OFFSET 65535
48 #define LZMS_X86_MAX_TRANSLATION_OFFSET 1023
50 /* Code shared between the LZMS decompressor and compressor. */
52 #include <wimlib/util.h>
55 lzms_x86_filter(u8 data[], s32 size, s32 last_target_usages[], bool undo);
57 /* Probability entry for use by the range coder when in a specific state. */
58 struct lzms_probability_entry {
60 /* Number of zeroes in the most recent LZMS_PROBABILITY_MAX bits that
61 * have been coded using this probability entry. This is a cached value
62 * because it can be computed as LZMS_PROBABILITY_MAX minus the Hamming
63 * weight of the low-order LZMS_PROBABILITY_MAX bits of @recent_bits.
65 u32 num_recent_zero_bits;
67 /* The most recent LZMS_PROBABILITY_MAX bits that have been coded using
68 * this probability entry. The size of this variable, in bits, must be
69 * at least LZMS_PROBABILITY_MAX. */
73 /* LRU queues for LZ matches. */
74 struct lzms_lz_lru_queues {
76 /* Recent LZ match offsets */
77 u32 recent_offsets[LZMS_NUM_RECENT_OFFSETS + 1];
79 /* These variables are used to delay updates to the LRU queues by one
85 /* LRU queues for delta matches. */
86 struct lzms_delta_lru_queues {
88 /* Recent delta match powers and offsets */
89 u32 recent_powers[LZMS_NUM_RECENT_OFFSETS + 1];
90 u32 recent_offsets[LZMS_NUM_RECENT_OFFSETS + 1];
92 /* These variables are used to delay updates to the LRU queues by one
100 /* LRU (least-recently-used) queues for match information. */
101 struct lzms_lru_queues {
102 struct lzms_lz_lru_queues lz;
103 struct lzms_delta_lru_queues delta;
106 extern u32 lzms_position_slot_base[LZMS_MAX_NUM_OFFSET_SYMS + 1];
108 extern u8 lzms_extra_position_bits[LZMS_MAX_NUM_OFFSET_SYMS];
110 extern u16 lzms_order_to_position_slot_bounds[30][2];
112 extern u32 lzms_length_slot_base[LZMS_NUM_LEN_SYMS + 1];
114 #define LZMS_NUM_FAST_LENGTHS 1024
115 extern u8 lzms_length_slot_fast[LZMS_NUM_FAST_LENGTHS];
117 extern u8 lzms_extra_length_bits[LZMS_NUM_LEN_SYMS];
120 lzms_init_slots(void);
122 /* Return the slot for the specified value. */
124 lzms_get_slot(u32 value, const u32 slot_base_tab[], u32 num_slots);
127 lzms_get_position_slot(u32 position)
129 u32 order = bsr32(position);
130 u32 l = lzms_order_to_position_slot_bounds[order][0];
131 u32 r = lzms_order_to_position_slot_bounds[order][1];
134 u32 slot = (l + r) / 2;
135 if (position >= lzms_position_slot_base[slot]) {
136 if (position < lzms_position_slot_base[slot + 1])
147 lzms_get_length_slot(u32 length)
149 if (likely(length < LZMS_NUM_FAST_LENGTHS))
150 return lzms_length_slot_fast[length];
152 return lzms_get_slot(length, lzms_length_slot_base,
157 lzms_init_lru_queues(struct lzms_lru_queues *lru);
160 lzms_update_lz_lru_queues(struct lzms_lz_lru_queues *lz);
163 lzms_update_delta_lru_queues(struct lzms_delta_lru_queues *delta);
166 lzms_update_lru_queues(struct lzms_lru_queues *lru);
168 #endif /* _WIMLIB_LZMS_H */