4 /* Constants for the LZX data compression format. See the comments in
5 * lzx-compress.c and lzx-decompress.c for more information about this format.
8 #include "wimlib/assert.h"
9 #include "wimlib/compiler.h"
10 #include "wimlib/util.h"
11 #include "wimlib/types.h"
13 //#define ENABLE_LZX_DEBUG
14 #ifdef ENABLE_LZX_DEBUG
15 # define LZX_DEBUG DEBUG
16 # define LZX_ASSERT wimlib_assert
18 # define LZX_DEBUG(format, ...)
19 # define LZX_ASSERT(...)
22 /* Constants, most of which are defined by the LZX specification: */
24 /* The smallest and largest allowed match lengths. */
25 #define LZX_MIN_MATCH_LEN 2
26 #define LZX_MAX_MATCH_LEN 257
28 /* Number of values an uncompressed literal byte can represent. */
29 #define LZX_NUM_CHARS 256
31 /* Each LZX block begins with 3 bits that determines the block type. Below are
32 * the valid block types. Values 0, and 4 through 7, are invalid. */
33 #define LZX_BLOCKTYPE_VERBATIM 1
34 #define LZX_BLOCKTYPE_ALIGNED 2
35 #define LZX_BLOCKTYPE_UNCOMPRESSED 3
37 #define LZX_NUM_PRIMARY_LENS 7
39 /* The number of position slots varies from 30 to 51 depending on the window
40 * size (see comment in lzx-decompress.c). */
41 #define LZX_MAX_POSITION_SLOTS 51
43 #define LZX_MIN_WINDOW_ORDER 15
44 #define LZX_MAX_WINDOW_ORDER 21
45 #define LZX_MIN_WINDOW_SIZE (1U << LZX_MIN_WINDOW_ORDER) /* 32768 */
46 #define LZX_MAX_WINDOW_SIZE (1U << LZX_MAX_WINDOW_ORDER) /* 2097152 */
48 /* Read the LZX specification for information about the Huffman trees used in
49 * the LZX compression format. Basically there are 4 of them: The main tree,
50 * the length tree, the pre tree, and the aligned tree. The main tree and
51 * length tree are given at the beginning of VERBATIM and ALIGNED blocks as a
52 * list of *_NUM_SYMBOLS code length values. They are read using the
53 * read_code_lens() function and built using the make_decode_table() function.
54 * The decode table is not a real tree but rather a table that we can index by
55 * some number of bits (*_TABLEBITS) of the input to quickly look up the symbol
56 * corresponding to a Huffman code.
58 * The ALIGNED tree is only present on ALIGNED blocks.
60 * A PRECODE is used to encode the code lengths for the main tree and the length
61 * tree. There is a separate pretree for each half of the main tree. */
63 #define LZX_MAINCODE_MAX_NUM_SYMBOLS (LZX_NUM_CHARS + (LZX_MAX_POSITION_SLOTS << 3))
64 #define LZX_MAINCODE_TABLEBITS 11
66 #define LZX_LENCODE_NUM_SYMBOLS 249
67 #define LZX_LENCODE_TABLEBITS 10
69 #define LZX_PRECODE_NUM_SYMBOLS 20
70 #define LZX_PRECODE_TABLEBITS 6
71 #define LZX_PRECODE_ELEMENT_SIZE 4
73 #define LZX_ALIGNEDCODE_NUM_SYMBOLS 8
74 #define LZX_ALIGNEDCODE_TABLEBITS 7
75 #define LZX_ALIGNEDCODE_ELEMENT_SIZE 3
77 /* Maximum allowed length of Huffman codewords. */
78 #define LZX_MAX_MAIN_CODEWORD_LEN 16
79 #define LZX_MAX_LEN_CODEWORD_LEN 16
80 #define LZX_MAX_PRE_CODEWORD_LEN 16
81 #define LZX_MAX_ALIGNED_CODEWORD_LEN 8
83 /* For the LZX-compressed blocks in WIM files, this value is always used as the
84 * filesize parameter for the call instruction (0xe8 byte) preprocessing, even
85 * though the blocks themselves are not this size, and the size of the actual
86 * file resource in the WIM file is very likely to be something entirely
87 * different as well. */
88 #define LZX_WIM_MAGIC_FILESIZE 12000000
90 /* Assumed LZX block size when the encoded block size begins with a 0 bit. */
91 #define LZX_DEFAULT_BLOCK_SIZE 32768
93 #define USE_LZX_EXTRA_BITS_ARRAY
95 #ifdef USE_LZX_EXTRA_BITS_ARRAY
96 extern const u8 lzx_extra_bits[LZX_MAX_POSITION_SLOTS];
99 /* Given the number of an LZX position slot, return the number of extra bits that
100 * are needed to encode the match offset. */
101 static inline unsigned
102 lzx_get_num_extra_bits(unsigned position_slot)
104 #ifdef USE_LZX_EXTRA_BITS_ARRAY
106 return lzx_extra_bits[position_slot];
108 /* Calculate directly using a shift and subtraction. */
109 LZX_ASSERT(position_slot >= 2 && position_slot <= 37);
110 return (position_slot >> 1) - 1;
114 extern const u32 lzx_position_base[LZX_MAX_POSITION_SLOTS];
116 /* Returns the LZX position slot that corresponds to a given formatted offset.
118 * Logically, this returns the smallest i such that
119 * formatted_offset >= lzx_position_base[i].
121 * The actual implementation below takes advantage of the regularity of the
122 * numbers in the lzx_position_base array to calculate the slot directly from
123 * the formatted offset without actually looking at the array.
125 static inline unsigned
126 lzx_get_position_slot_raw(u32 formatted_offset)
128 if (formatted_offset >= 196608) {
129 return (formatted_offset >> 17) + 34;
131 LZX_ASSERT(2 <= formatted_offset && formatted_offset < 655360);
132 unsigned mssb_idx = bsr32(formatted_offset);
133 return (mssb_idx << 1) |
134 ((formatted_offset >> (mssb_idx - 1)) & 1);
138 extern bool lzx_window_size_valid(size_t window_size);
139 extern unsigned lzx_get_num_main_syms(u32 window_size);
141 #define LZX_NUM_RECENT_OFFSETS 3
143 /* Least-recently used queue for match offsets. */
144 struct lzx_lru_queue {
145 u32 R[LZX_NUM_RECENT_OFFSETS];
148 _aligned_attribute(8) /* Improves performance of LZX compression by 1% - 2%;
149 specifically, this speeds up
150 lzx_get_near_optimal_match(). */
154 /* In the LZX format, an offset of n bytes is actually encoded
155 * as (n + LZX_OFFSET_OFFSET). */
156 #define LZX_OFFSET_OFFSET (LZX_NUM_RECENT_OFFSETS - 1)
158 /* Initialize the LZX least-recently-used match offset queue at the beginning of
159 * a new window for either decompression or compression. */
161 lzx_lru_queue_init(struct lzx_lru_queue *queue)
163 for (unsigned i = 0; i < LZX_NUM_RECENT_OFFSETS; i++)
168 lzx_do_e8_preprocessing(u8 *data, s32 size);
171 lzx_undo_e8_preprocessing(u8 *data, s32 size);
173 #endif /* _WIMLIB_LZX_H */