4 * XPRESS compression routines.
6 * See the comments in xpress-decomp.c about the XPRESS format.
10 * Copyright (C) 2012 Eric Biggers
12 * This file is part of wimlib, a library for working with WIM files.
14 * wimlib is free software; you can redistribute it and/or modify it under the
15 * terms of the GNU General Public License as published by the Free
16 * Software Foundation; either version 3 of the License, or (at your option)
19 * wimlib is distributed in the hope that it will be useful, but WITHOUT ANY
20 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
21 * A PARTICULAR PURPOSE. See the GNU General Public License for more
24 * You should have received a copy of the GNU General Public License
25 * along with wimlib; if not, see http://www.gnu.org/licenses/.
33 static inline u32 bsr32(u32 n)
35 #if defined(__x86__) || defined(__x86_64__)
42 while ((n >>= 1) != 0)
50 * Writes @match, which is a match given in the intermediate representation for
51 * XPRESS matches, to the output stream @ostream.
53 * @codewords and @lens provide the Huffman code that is being used.
55 static int xpress_write_match(struct output_bitstream *ostream, u32 match,
56 const u16 codewords[], const u8 lens[])
66 main_sym = (match & 0xff);
67 huff_sym = main_sym + XPRESS_NUM_CHARS;
68 ret = bitstream_put_bits(ostream, codewords[huff_sym], lens[huff_sym]);
72 offset_bsr = main_sym >> 4;
74 match_len = (match >> 8) & 0xff;
75 match_offset = (match >> 16);
78 match_len -= XPRESS_MIN_MATCH;
79 if (match_len >= 0xf) {
80 byte1 = (u8)(match_len - 0xf);
81 ret = bitstream_put_byte(ostream, byte1);
85 ret = bitstream_put_two_bytes(ostream, match_len);
90 return bitstream_put_bits(ostream, match_offset ^ (1 << offset_bsr),
94 static int xpress_write_compressed_literals(struct output_bitstream *ostream,
95 const u32 match_tab[],
97 const u16 codewords[],
104 for (i = 0; i < num_matches; i++) {
105 match = match_tab[i];
106 if (match >= XPRESS_NUM_CHARS) /* match */
107 ret = xpress_write_match(ostream, match, codewords,
109 else /* literal byte */
110 ret = bitstream_put_bits(ostream, codewords[match],
115 return bitstream_put_bits(ostream, codewords[256], lens[256]);
118 static u32 xpress_record_literal(u8 literal, void *__freq_tab)
120 u32 *freq_tab = __freq_tab;
125 static u32 xpress_record_match(uint match_offset, uint match_len,
126 void *__freq_tab, void *ignore)
128 u32 *freq_tab = __freq_tab;
133 wimlib_assert(match_len >= XPRESS_MIN_MATCH &&
134 match_len <= XPRESS_MAX_MATCH);
135 wimlib_assert(match_offset > 0);
137 len_hdr = min(match_len - XPRESS_MIN_MATCH, 15);
138 offset_bsr = bsr32(match_offset);
139 match = (offset_bsr << 4) | len_hdr;
140 freq_tab[match + XPRESS_NUM_CHARS]++;
141 match |= match_len << 8;
142 match |= match_offset << 16;
146 static const struct lz_params xpress_lz_params = {
148 .max_match = XPRESS_MAX_MATCH,
152 .max_lazy_match = 16,
157 * Performs XPRESS compression on a block of data.
159 * @__uncompressed_data: Pointer to the data to be compressed.
160 * @uncompressed_len: Length, in bytes, of the data to be compressed.
161 * @__compressed_data: Pointer to a location at least (@uncompressed_len - 1)
162 * bytes long into which the compressed data may be
164 * @compressed_len_ret: A pointer to an unsigned int into which the length of
165 * the compressed data may be returned.
167 * Returns zero if compression was successfully performed. In that case
168 * @compressed_data and @compressed_len_ret will contain the compressed data and
169 * its length. A return value of nonzero means that compressing the data did
170 * not reduce its size, and @compressed_data will not contain the full
173 int xpress_compress(const void *__uncompressed_data, uint uncompressed_len,
174 void *__compressed_data, uint *compressed_len_ret)
176 const u8 *uncompressed_data = __uncompressed_data;
177 u8 *compressed_data = __compressed_data;
178 struct output_bitstream ostream;
179 u32 match_tab[uncompressed_len];
180 u32 freq_tab[XPRESS_NUM_SYMBOLS];
181 u16 codewords[XPRESS_NUM_SYMBOLS];
182 u8 lens[XPRESS_NUM_SYMBOLS];
188 XPRESS_DEBUG("uncompressed_len = %u", uncompressed_len);
190 if (uncompressed_len < 300)
193 ZERO_ARRAY(freq_tab);
195 num_matches = lz_analyze_block(uncompressed_data, uncompressed_len,
196 match_tab, xpress_record_match,
197 xpress_record_literal, freq_tab,
201 XPRESS_DEBUG("using %u matches", num_matches);
205 make_canonical_huffman_code(XPRESS_NUM_SYMBOLS, XPRESS_MAX_CODEWORD_LEN,
206 freq_tab, lens, codewords);
210 * It's tempting to output the 512 Huffman codeword lengths using the
211 * bitstream_put_bits() function. However, this is NOT correct because
212 * bitstream_put_bits() will output 2 bytes at a time in little-endian
213 * order, which is the order that is needed for the compressed literals.
214 * However, the bytes in the lengths table are in order, so they need to
215 * be written one at a time without using bitstream_put_bits().
217 * Because of this, init_output_bitstream() is not called until after
218 * the lengths table is output.
220 for (i = 0; i < XPRESS_NUM_SYMBOLS; i += 2)
221 *compressed_data++ = (lens[i] & 0xf) | (lens[i + 1] << 4);
223 init_output_bitstream(&ostream, compressed_data,
224 uncompressed_len - XPRESS_NUM_SYMBOLS / 2 - 1);
226 ret = xpress_write_compressed_literals(&ostream, match_tab,
227 num_matches, codewords, lens);
231 /* Flush any bits that are buffered. */
232 ret = flush_output_bitstream(&ostream);
236 /* Assert that there are no output bytes between the ostream.output
237 * pointer and the ostream.next_bit_output pointer. This can only
238 * happen if bytes had been written at the ostream.output pointer before
239 * the last bit word was written to the stream. But, this does not
240 * occur since xpress_write_match() always finishes by writing some bits
241 * (a Huffman symbol), and the bitstream was just flushed. */
242 wimlib_assert(ostream.output - ostream.next_bit_output == 2);
245 * The length of the compressed data is supposed to be the value of the
246 * ostream.output pointer before flushing, which is now the
247 * output.next_bit_output pointer after flushing.
249 * There will be an extra 2 bytes at the ostream.bit_output pointer,
250 * which is zeroed out. (These 2 bytes may be either the last bytes in
251 * the compressed data, in which case they are actually unnecessary, or
252 * they may precede a number of bytes embedded into the bitstream.)
254 if (ostream.bit_output >
255 (const u8*)__compressed_data + uncompressed_len - 3)
257 *(u16*)ostream.bit_output = cpu_to_le16(0);
258 compressed_len = ostream.next_bit_output - (const u8*)__compressed_data;
260 wimlib_assert(compressed_len <= uncompressed_len - 1);
262 XPRESS_DEBUG("Compressed %u => %u bytes",
263 uncompressed_len, compressed_len);
265 *compressed_len_ret = compressed_len;
267 #ifdef ENABLE_VERIFY_COMPRESSION
268 /* Verify that we really get the same thing back when decompressing. */
269 XPRESS_DEBUG("Verifying the compressed data.");
270 u8 buf[uncompressed_len];
271 ret = xpress_decompress(__compressed_data, compressed_len, buf,
274 ERROR("xpress_compress(): Failed to decompress data we "
278 for (i = 0; i < uncompressed_len; i++) {
279 if (buf[i] != uncompressed_data[i]) {
280 ERROR("xpress_compress(): Data we compressed didn't "
281 "decompress to the original data (difference at "
282 "byte %u of %u)", i + 1, uncompressed_len);
286 XPRESS_DEBUG("Compression verified to be correct.");