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/types.h"
11 //#define ENABLE_LZX_DEBUG
12 #ifdef ENABLE_LZX_DEBUG
13 # define LZX_DEBUG DEBUG
14 # define LZX_ASSERT wimlib_assert
16 # define LZX_DEBUG(format, ...)
17 # define LZX_ASSERT(...)
20 /* Constants, most of which are defined by the LZX specification: */
22 /* The smallest and largest allowed match lengths. */
23 #define LZX_MIN_MATCH_LEN 2
24 #define LZX_MAX_MATCH_LEN 257
26 /* Number of values an uncompressed literal byte can represent. */
27 #define LZX_NUM_CHARS 256
29 /* Each LZX block begins with 3 bits that determines the block type. Below are
30 * the valid block types. Values 0, and 4 through 7, are invalid. */
31 #define LZX_BLOCKTYPE_VERBATIM 1
32 #define LZX_BLOCKTYPE_ALIGNED 2
33 #define LZX_BLOCKTYPE_UNCOMPRESSED 3
35 #define LZX_NUM_PRIMARY_LENS 7 /* this one missing from spec! */
37 /* NOTE: There are really 51 position slots in the LZX format as a whole, but
38 * only 30 are needed to allow for the window to be up to 32768 bytes long,
39 * which is the maximum in the WIM format. */
40 #define LZX_NUM_POSITION_SLOTS 30
42 /* Read the LZX specification for information about the Huffman trees used in
43 * the LZX compression format. Basically there are 4 of them: The main tree,
44 * the length tree, the pre tree, and the aligned tree. The main tree and
45 * length tree are given at the beginning of VERBATIM and ALIGNED blocks as a
46 * list of *_NUM_SYMBOLS code length values. They are read using the
47 * read_code_lens() function and built using the make_decode_table() function.
48 * The decode table is not a real tree but rather a table that we can index by
49 * some number of bits (*_TABLEBITS) of the input to quickly look up the symbol
50 * corresponding to a Huffman code.
52 * The ALIGNED tree is only present on ALIGNED blocks.
54 * A PRECODE is used to encode the code lengths for the main tree and the length
55 * tree. There is a separate pretree for each half of the main tree. */
57 #define LZX_MAINCODE_NUM_SYMBOLS (LZX_NUM_CHARS + \
58 (LZX_NUM_POSITION_SLOTS << 3))
59 #define LZX_MAINCODE_TABLEBITS 11
61 #define LZX_LENCODE_NUM_SYMBOLS 249
62 #define LZX_LENCODE_TABLEBITS 10
64 #define LZX_PRECODE_NUM_SYMBOLS 20
65 #define LZX_PRECODE_TABLEBITS 6
66 #define LZX_PRECODE_ELEMENT_SIZE 4
68 #define LZX_ALIGNEDCODE_NUM_SYMBOLS 8
69 #define LZX_ALIGNEDCODE_TABLEBITS 7
70 #define LZX_ALIGNEDCODE_ELEMENT_SIZE 3
72 /* Maximum allowed length of Huffman codewords. */
73 #define LZX_MAX_MAIN_CODEWORD_LEN 16
74 #define LZX_MAX_LEN_CODEWORD_LEN 16
75 #define LZX_MAX_PRE_CODEWORD_LEN 16
76 #define LZX_MAX_ALIGNED_CODEWORD_LEN 8
78 /* For the LZX-compressed blocks in WIM files, this value is always used as the
79 * filesize parameter for the call instruction (0xe8 byte) preprocessing, even
80 * though the blocks themselves are not this size, and the size of the actual
81 * file resource in the WIM file is very likely to be something entirely
82 * different as well. */
83 #define LZX_WIM_MAGIC_FILESIZE 12000000
85 #define LZX_BLOCKTYPE_NBITS 3
86 #define LZX_BLOCKSIZE_NBITS 16
88 #define USE_LZX_EXTRA_BITS_ARRAY
90 #ifdef USE_LZX_EXTRA_BITS_ARRAY
91 extern const u8 lzx_extra_bits[];
94 /* Given the number of a LZX position slot, return the number of extra bits that
95 * are needed to encode the match offset. */
96 static inline unsigned
97 lzx_get_num_extra_bits(unsigned position_slot)
99 #ifdef USE_LZX_EXTRA_BITS_ARRAY
101 return lzx_extra_bits[position_slot];
103 /* Calculate directly using a shift and subtraction. */
104 LZX_ASSERT(position_slot >= 2 && position_slot <= 37);
105 return (position_slot >> 1) - 1;
109 extern const u32 lzx_position_base[];
111 #define LZX_NUM_RECENT_OFFSETS 3
113 /* Least-recently used queue for match offsets. */
114 struct lzx_lru_queue {
115 u32 R[LZX_NUM_RECENT_OFFSETS];
118 /* In the LZX format, an offset of n bytes is actually encoded
119 * as (n + LZX_OFFSET_OFFSET). */
120 #define LZX_OFFSET_OFFSET (LZX_NUM_RECENT_OFFSETS - 1)
123 lzx_lru_queue_init(struct lzx_lru_queue *queue)
125 for (unsigned i = 0; i < LZX_NUM_RECENT_OFFSETS; i++)
129 #endif /* _WIMLIB_LZX_H */