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