4 * XPRESS compression routines.
6 * Copyright (C) 2012 Eric Biggers
8 * wimlib - Library for working with WIM files
10 * This library is free software; you can redistribute it and/or modify it under
11 * the terms of the GNU Lesser General Public License as published by the Free
12 * Software Foundation; either version 2.1 of the License, or (at your option) any
15 * This library is distributed in the hope that it will be useful, but WITHOUT ANY
16 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
17 * PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.
19 * You should have received a copy of the GNU Lesser General Public License along
20 * with this library; if not, write to the Free Software Foundation, Inc., 59
21 * Temple Place, Suite 330, Boston, MA 02111-1307 USA
24 /* See the comments in xpress-decomp.c about the XPRESS format. */
32 static inline u32 bsr32(u32 n)
34 #if defined(__x86__) || defined(__x86_64__)
41 while ((n >>= 1) != 0)
49 * Writes @match, which is a match given in the intermediate representation for
50 * XPRESS matches, to the output stream @ostream.
52 * @codewords and @lens provide the Huffman code that is being used.
54 static int xpress_write_match(struct output_bitstream *ostream, u32 match,
55 const u16 codewords[], const u8 lens[])
65 main_sym = (match & 0xff);
66 huff_sym = main_sym + XPRESS_NUM_CHARS;
67 ret = bitstream_put_bits(ostream, codewords[huff_sym], lens[huff_sym]);
71 offset_bsr = main_sym >> 4;
73 match_len = (match >> 8) & 0xff;
74 match_offset = (match >> 16);
77 match_len -= XPRESS_MIN_MATCH;
78 if (match_len >= 0xf) {
79 byte1 = (u8)(match_len - 0xf);
80 ret = bitstream_put_byte(ostream, byte1);
84 ret = bitstream_put_two_bytes(ostream, match_len);
89 return bitstream_put_bits(ostream, match_offset ^ (1 << offset_bsr),
93 static int xpress_write_compressed_literals(struct output_bitstream *ostream,
94 const u32 match_tab[],
96 const u16 codewords[],
103 for (i = 0; i < num_matches; i++) {
104 match = match_tab[i];
105 if (match >= XPRESS_NUM_CHARS) {
107 ret = xpress_write_match(ostream, match, codewords,
113 ret = bitstream_put_bits(ostream, codewords[match],
119 return bitstream_put_bits(ostream, codewords[256], lens[256]);
122 static u32 xpress_record_literal(u8 literal, void *__freq_tab)
124 u32 *freq_tab = __freq_tab;
129 static u32 xpress_record_match(uint match_offset, uint match_len,
130 void *__freq_tab, void *ignore)
132 u32 *freq_tab = __freq_tab;
137 wimlib_assert(match_len >= XPRESS_MIN_MATCH &&
138 match_len <= XPRESS_MAX_MATCH);
139 wimlib_assert(match_offset > 0);
141 len_hdr = min(match_len - XPRESS_MIN_MATCH, 15);
142 offset_bsr = bsr32(match_offset);
143 match = (offset_bsr << 4) | len_hdr;
144 freq_tab[match + XPRESS_NUM_CHARS]++;
145 match |= match_len << 8;
146 match |= match_offset << 16;
150 static const struct lz_params xpress_lz_params = {
152 .max_match = XPRESS_MAX_MATCH,
156 .max_lazy_match = 16,
161 * Performs XPRESS compression on a block of data.
163 * @__uncompressed_data: Pointer to the data to be compressed.
164 * @uncompressed_len: Length, in bytes, of the data to be compressed.
165 * @__compressed_data: Pointer to a location at least (@uncompressed_len - 1)
166 * bytes long into which the compressed data may be
168 * @compressed_len_ret: A pointer to an unsigned int into which the length of
169 * the compressed data may be returned.
171 * Returns zero if compression was successfully performed. In that case
172 * @compressed_data and @compressed_len_ret will contain the compressed data and
173 * its length. A return value of nonzero means that compressing the data did
174 * not reduce its size, and @compressed_data will not contain the full
177 int xpress_compress(const void *__uncompressed_data, uint uncompressed_len,
178 void *__compressed_data, uint *compressed_len_ret)
180 const u8 *uncompressed_data = __uncompressed_data;
181 u8 *compressed_data = __compressed_data;
182 struct output_bitstream ostream;
183 u32 match_tab[uncompressed_len];
184 u32 freq_tab[XPRESS_NUM_SYMBOLS];
185 u16 codewords[XPRESS_NUM_SYMBOLS];
186 u8 lens[XPRESS_NUM_SYMBOLS];
192 XPRESS_DEBUG("uncompressed_len = %u\n", uncompressed_len);
194 if (uncompressed_len < 300)
197 ZERO_ARRAY(freq_tab);
199 num_matches = lz_analyze_block(uncompressed_data, uncompressed_len,
200 match_tab, xpress_record_match,
201 xpress_record_literal, freq_tab,
205 XPRESS_DEBUG("using %u matches\n", num_matches);
209 make_canonical_huffman_code(XPRESS_NUM_SYMBOLS, XPRESS_MAX_CODEWORD_LEN,
210 freq_tab, lens, codewords);
214 * It's tempting to output the 512 Huffman codeword lengths using the
215 * bitstream_put_bits() function. However, this is NOT correct because
216 * bitstream_put_bits() will output 2 bytes at a time in little-endian
217 * order, which is the order that is needed for the compressed literals.
218 * However, the bytes in the lengths table are in order, so they need to
219 * be written one at a time without using bitstream_put_bits().
221 * Because of this, init_output_bitstream() is not called until after
222 * the lengths table is output.
224 for (i = 0; i < XPRESS_NUM_SYMBOLS; i += 2)
225 *compressed_data++ = (lens[i] & 0xf) | (lens[i + 1] << 4);
227 init_output_bitstream(&ostream, compressed_data, uncompressed_len -
228 XPRESS_NUM_SYMBOLS / 2 - 1);
230 ret = xpress_write_compressed_literals(&ostream, match_tab, num_matches,
235 ret = flush_output_bitstream(&ostream);
240 compressed_len = ostream.output - (u8*)__compressed_data;
242 XPRESS_DEBUG("Compressed %u => %u bytes\n",
243 uncompressed_len, compressed_len);
245 *compressed_len_ret = compressed_len;
247 #ifdef ENABLE_VERIFY_COMPRESSION
248 /* Verify that we really get the same thing back when decompressing. */
249 XPRESS_DEBUG("Verifying the compressed data.\n");
250 u8 buf[uncompressed_len];
251 ret = xpress_decompress(__compressed_data, compressed_len, buf,
254 fprintf(stderr, "xpress_compress(): Failed to decompress data "
258 for (i = 0; i < uncompressed_len; i++) {
259 if (buf[i] != uncompressed_data[i]) {
260 fprintf(stderr, "xpress_compress(): Data we compressed "
261 "didn't decompress to the original data "
262 "(difference at byte %u of %u)\n",
263 i + 1, uncompressed_len);
267 XPRESS_DEBUG("Compression verified to be correct.\n");