4 * Copyright (C) 2012 Eric Biggers
6 * wimlib - Library for working with WIM files
8 * This library is free software; you can redistribute it and/or modify it under
9 * the terms of the GNU Lesser General Public License as published by the Free
10 * Software Foundation; either version 2.1 of the License, or (at your option) any
13 * This library is distributed in the hope that it will be useful, but WITHOUT ANY
14 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
15 * PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.
17 * You should have received a copy of the GNU Lesser General Public License along
18 * with this library; if not, write to the Free Software Foundation, Inc., 59
19 * Temple Place, Suite 330, Boston, MA 02111-1307 USA
27 //#define ENABLE_LZX_DEBUG
28 #ifdef ENABLE_LZX_DEBUG
29 # define LZX_DEBUG DEBUG
31 # define LZX_DEBUG(format, ...)
35 /* Constants, some defined by the LZX specification: */
37 /* The smallest and largest allowed match lengths. */
38 #define LZX_MIN_MATCH 2
39 #define LZX_MAX_MATCH 257
41 /* Number of values an uncompressed literal byte can represent. */
42 #define LZX_NUM_CHARS 256
44 /* Each LZX block begins with 3 bits that determines the block type: */
45 #define LZX_BLOCKTYPE_VERBATIM 1
46 #define LZX_BLOCKTYPE_ALIGNED 2
47 #define LZX_BLOCKTYPE_UNCOMPRESSED 3
48 /* values 0, and 4 through 7, are invalid. */
51 #define LZX_NUM_PRIMARY_LENS 7 /* this one missing from spec! */
53 /* Only valid for 32768 block size! */
54 #define LZX_NUM_POSITION_SLOTS 30
56 /* Read the LZX specification for information about the Huffman trees used in
57 * the LZX compression format. Basically there are 4 of them: The main tree,
58 * the length tree, the pre tree, and the aligned tree. The main tree and
59 * length tree are given at the beginning of VERBATIM and ALIGNED blocks as a
60 * list of *_NUM_SYMBOLS code length values. They are read using the
61 * read_code_lens() function and built using the make_decode_table() function.
62 * The decode table is not a real tree but rather a table that we can index by
63 * some number of bits (*_TABLEBITS) of the input to quickly look up the symbol
64 * corresponding to a Huffman code.
66 * The ALIGNED tree is only present on ALIGNED blocks.
68 * A PRETREE is used to encode the code lengths for the main tree and the length
69 * tree. There is a separate pretree for each half of the main tree. */
71 #define LZX_MAINTREE_NUM_SYMBOLS (LZX_NUM_CHARS + \
72 (LZX_NUM_POSITION_SLOTS << 3))
73 #define LZX_MAINTREE_TABLEBITS 12
75 #define LZX_LENTREE_NUM_SYMBOLS 249
76 #define LZX_LENTREE_TABLEBITS 12
78 #define LZX_PRETREE_NUM_SYMBOLS 20
79 #define LZX_PRETREE_TABLEBITS 6
80 #define LZX_PRETREE_ELEMENT_SIZE 4
83 #define LZX_ALIGNEDTREE_NUM_SYMBOLS 8
84 #define LZX_ALIGNEDTREE_TABLEBITS 7
85 #define LZX_ALIGNEDTREE_ELEMENT_SIZE 3
87 /* Maximum allowed length of a Huffman code. */
88 #define LZX_MAX_CODEWORD_LEN 16
90 /* For the LZX-compressed blocks in WIM files, this value is always used as the
91 * filesize parameter for the call instruction (0xe8 byte) preprocessing, even
92 * though the blocks themselves are not this size, and the size of the actual
93 * file resource in the WIM file is very likely to be something entirely
94 * different as well. */
95 #define LZX_MAGIC_FILESIZE 12000000
97 extern const u8 lzx_extra_bits[51];
98 extern const u32 lzx_position_base[51];
100 /* Least-recently used queue for match offsets. */
107 extern int lzx_decompress(const void *compressed_data, uint compressed_len,
108 void *uncompressed_data, uint uncompressed_len);
110 extern int lzx_compress(const void *uncompressed_data, uint uncompressed_len,
111 void *compressed_data, uint *compressed_len_ret);
113 #endif /* _WIMLIB_LZX_H */