6061e730e7b63f9e45ee867aac3f81f510f7e721
[wimlib] / include / wimlib / lzx.h
1 #ifndef _WIMLIB_LZX_H
2 #define _WIMLIB_LZX_H
3
4 #include "wimlib/assert.h"
5 #include "wimlib/types.h"
6
7 //#define ENABLE_LZX_DEBUG
8 #ifdef ENABLE_LZX_DEBUG
9 #       define LZX_DEBUG DEBUG
10 #       define LZX_ASSERT wimlib_assert
11 #else
12 #       define LZX_DEBUG(format, ...)
13 #       define LZX_ASSERT(...)
14 #endif
15
16 /* Constants, most of which are defined by the LZX specification: */
17
18 /* The smallest and largest allowed match lengths. */
19 #define LZX_MIN_MATCH                2
20 #define LZX_MAX_MATCH                257
21
22 /* Number of values an uncompressed literal byte can represent. */
23 #define LZX_NUM_CHARS                256
24
25 /* Each LZX block begins with 3 bits that determines the block type.  Below are
26  * the valid block types.  Values 0, and 4 through 7, are invalid. */
27 #define LZX_BLOCKTYPE_VERBATIM       1
28 #define LZX_BLOCKTYPE_ALIGNED        2
29 #define LZX_BLOCKTYPE_UNCOMPRESSED   3
30
31 #define LZX_NUM_PRIMARY_LENS         7  /* this one missing from spec! */
32
33 /* NOTE: There are really 51 position slots in the LZX format as a whole, but
34  * only 30 are needed to allow for the window to be up to 32768 bytes long,
35  * which is the maximum in the WIM format. */
36 #define LZX_NUM_POSITION_SLOTS       30
37
38 /* Read the LZX specification for information about the Huffman trees used in
39  * the LZX compression format.  Basically there are 4 of them: The main tree,
40  * the length tree, the pre tree, and the aligned tree.  The main tree and
41  * length tree are given at the beginning of VERBATIM and ALIGNED blocks as a
42  * list of *_NUM_SYMBOLS code length values.  They are read using the
43  * read_code_lens() function and built using the make_decode_table() function.
44  * The decode table is not a real tree but rather a table that we can index by
45  * some number of bits (*_TABLEBITS) of the input to quickly look up the symbol
46  * corresponding to a Huffman code.
47  *
48  * The ALIGNED tree is only present on ALIGNED blocks.
49  *
50  * A PRETREE is used to encode the code lengths for the main tree and the length
51  * tree.  There is a separate pretree for each half of the main tree.  */
52
53 #define LZX_MAINTREE_NUM_SYMBOLS         (LZX_NUM_CHARS + \
54                                         (LZX_NUM_POSITION_SLOTS << 3))
55 #define LZX_MAINTREE_TABLEBITS          11
56
57 #define LZX_LENTREE_NUM_SYMBOLS         249
58 #define LZX_LENTREE_TABLEBITS           10
59
60 #define LZX_PRETREE_NUM_SYMBOLS         20
61 #define LZX_PRETREE_TABLEBITS           6
62 #define LZX_PRETREE_ELEMENT_SIZE        4
63
64 #define LZX_ALIGNEDTREE_NUM_SYMBOLS     8
65 #define LZX_ALIGNEDTREE_TABLEBITS       7
66 #define LZX_ALIGNEDTREE_ELEMENT_SIZE    3
67
68 /* Maximum allowed length of a Huffman code. */
69 #define LZX_MAX_CODEWORD_LEN            16
70
71 /* For the LZX-compressed blocks in WIM files, this value is always used as the
72  * filesize parameter for the call instruction (0xe8 byte) preprocessing, even
73  * though the blocks themselves are not this size, and the size of the actual
74  * file resource in the WIM file is very likely to be something entirely
75  * different as well.  */
76 #define LZX_WIM_MAGIC_FILESIZE          12000000
77
78 #define LZX_BLOCKTYPE_NBITS     3
79 #define LZX_BLOCKSIZE_NBITS     16
80
81 #define USE_LZX_EXTRA_BITS_ARRAY
82
83 #ifdef USE_LZX_EXTRA_BITS_ARRAY
84 extern const u8 lzx_extra_bits[LZX_NUM_POSITION_SLOTS];
85 #endif
86
87 /* Given the number of a LZX position slot, return the number of extra bits that
88  * are needed to encode the match offset. */
89 static inline unsigned
90 lzx_get_num_extra_bits(unsigned position_slot)
91 {
92 #ifdef USE_LZX_EXTRA_BITS_ARRAY
93         /* Use a table */
94         return lzx_extra_bits[position_slot];
95 #else
96         /* Calculate directly using a shift and subtraction. */
97         wimlib_assert(position_slot >= 2 && position_slot <= 37);
98         return (position_slot >> 1) - 1;
99 #endif
100 }
101
102 extern const u32 lzx_position_base[LZX_NUM_POSITION_SLOTS];
103
104 /* Least-recently used queue for match offsets. */
105 struct lzx_lru_queue {
106         u32 R0;
107         u32 R1;
108         u32 R2;
109 };
110
111 #endif /* _WIMLIB_LZX_H */