4 * XPRESS compression routines.
6 * See the comments in xpress-decompress.c about the XPRESS format.
10 * Copyright (C) 2012, 2013 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 #include "wimlib/assert.h"
34 #include "wimlib/compress.h"
35 #include "wimlib/error.h"
36 #include "wimlib/util.h"
37 #include "wimlib/xpress.h"
43 * Writes @match, which is a match given in the intermediate representation for
44 * XPRESS matches, to the output stream @ostream.
46 * @codewords and @lens provide the Huffman code that is being used.
49 xpress_write_match(struct output_bitstream *restrict ostream,
51 const u16 codewords[restrict],
52 const u8 lens[restrict])
54 u32 adjusted_match_len = match & 0xffff;
55 u32 match_offset = match >> 16;
56 u32 len_hdr = min(adjusted_match_len, 0xf);
57 u32 offset_bsr = bsr32(match_offset);
58 u32 sym = len_hdr | (offset_bsr << 4) | XPRESS_NUM_CHARS;
61 ret = bitstream_put_bits(ostream, codewords[sym], lens[sym]);
65 if (adjusted_match_len >= 0xf) {
66 u8 byte1 = min(adjusted_match_len - 0xf, 0xff);
67 ret = bitstream_put_byte(ostream, byte1);
71 ret = bitstream_put_two_bytes(ostream, adjusted_match_len);
76 return bitstream_put_bits(ostream,
77 match_offset ^ (1 << offset_bsr), offset_bsr);
81 xpress_write_compressed_literals(struct output_bitstream *ostream,
82 const u32 match_tab[restrict],
84 const u16 codewords[restrict],
85 const u8 lens[restrict])
87 for (unsigned i = 0; i < num_matches; i++) {
89 u32 match = match_tab[i];
91 if (match >= XPRESS_NUM_CHARS) /* match */
92 ret = xpress_write_match(ostream, match, codewords,
94 else /* literal byte */
95 ret = bitstream_put_bits(ostream, codewords[match],
100 return bitstream_put_bits(ostream, codewords[XPRESS_END_OF_DATA],
101 lens[XPRESS_END_OF_DATA]);
105 xpress_record_literal(u8 literal, void *_freq_tab)
107 freq_t *freq_tab = _freq_tab;
113 xpress_record_match(unsigned match_offset, unsigned match_len,
114 void *freq_tab, void *_ignore)
116 wimlib_assert(match_len >= XPRESS_MIN_MATCH &&
117 match_len <= XPRESS_MAX_MATCH);
118 wimlib_assert(match_offset >= XPRESS_MIN_OFFSET &&
119 match_offset <= XPRESS_MAX_OFFSET);
122 * The intermediate representation of XPRESS matches is as follows:
125 * ---- -----------------------------------------------------------
127 * 16-31 match offset (XPRESS_MIN_OFFSET < x < XPRESS_MAX_OFFSET)
129 * 0-15 adjusted match length (0 <= x <= XPRESS_MAX_MATCH - XPRESS_MIN_MATCH)
131 * Literals are simply represented as themselves and can be
132 * distinguished from matches by the fact that only literals will have
133 * the upper three bytes completely clear. */
135 u32 adjusted_match_len = match_len - XPRESS_MIN_MATCH;
136 u32 len_hdr = min(adjusted_match_len, 0xf);
137 u32 offset_bsr = bsr32(match_offset);
138 u32 sym = len_hdr | (offset_bsr << 4) | XPRESS_NUM_CHARS;
139 ((freq_t*)freq_tab)[sym]++;
140 return adjusted_match_len | (match_offset << 16);
143 static const struct lz_params xpress_lz_params = {
144 .min_match = XPRESS_MIN_MATCH,
145 .max_match = XPRESS_MAX_MATCH,
149 .max_lazy_match = 16,
153 /* API function documented in wimlib.h */
155 wimlib_xpress_compress(const void * restrict _uncompressed_data,
156 unsigned uncompressed_len,
157 void * restrict _compressed_data)
159 u8 *compressed_data = _compressed_data;
160 struct output_bitstream ostream;
161 u32 match_tab[uncompressed_len];
162 freq_t freq_tab[XPRESS_NUM_SYMBOLS];
163 u16 codewords[XPRESS_NUM_SYMBOLS];
164 u8 lens[XPRESS_NUM_SYMBOLS];
165 unsigned num_matches;
166 unsigned compressed_len;
169 u8 uncompressed_data[uncompressed_len + 8];
171 memcpy(uncompressed_data, _uncompressed_data, uncompressed_len);
172 memset(uncompressed_data + uncompressed_len, 0, 8);
174 wimlib_assert(uncompressed_len <= 32768);
176 /* XPRESS requires 256 bytes of overhead for the Huffman tables, so it's
177 * impossible cannot compress 256 bytes or less of data to less than the
180 * +1 to take into account that the buffer for compressed data is 1 byte
181 * smaller than the buffer for uncompressed data.
183 * +4 to take into account that init_output_bitstream() requires at
184 * least 4 bytes of data. */
185 if (uncompressed_len < XPRESS_NUM_SYMBOLS / 2 + 1 + 4)
188 ZERO_ARRAY(freq_tab);
189 num_matches = lz_analyze_block(uncompressed_data, uncompressed_len,
190 match_tab, xpress_record_match,
191 xpress_record_literal, freq_tab,
195 freq_tab[XPRESS_END_OF_DATA]++;
197 make_canonical_huffman_code(XPRESS_NUM_SYMBOLS, XPRESS_MAX_CODEWORD_LEN,
198 freq_tab, lens, codewords);
202 * It's tempting to output the 512 Huffman codeword lengths using the
203 * bitstream_put_bits() function. However, this is NOT correct because
204 * bitstream_put_bits() will output 2 bytes at a time in little-endian
205 * order, which is the order that is needed for the compressed literals.
206 * However, the bytes in the lengths table are in order, so they need to
207 * be written one at a time without using bitstream_put_bits().
209 * Because of this, init_output_bitstream() is not called until after
210 * the lengths table is output.
212 for (i = 0; i < XPRESS_NUM_SYMBOLS; i += 2)
213 *compressed_data++ = (lens[i] & 0xf) | (lens[i + 1] << 4);
215 init_output_bitstream(&ostream, compressed_data,
216 uncompressed_len - XPRESS_NUM_SYMBOLS / 2 - 1);
218 ret = xpress_write_compressed_literals(&ostream, match_tab,
219 num_matches, codewords, lens);
223 /* Flush any bits that are buffered. */
224 ret = flush_output_bitstream(&ostream);
228 /* Assert that there are no output bytes between the ostream.output
229 * pointer and the ostream.next_bit_output pointer. This can only
230 * happen if bytes had been written at the ostream.output pointer before
231 * the last bit word was written to the stream. But, this does not
232 * occur since xpress_write_match() always finishes by writing some bits
233 * (a Huffman symbol), and the bitstream was just flushed. */
234 wimlib_assert(ostream.output - ostream.next_bit_output == 2);
236 /* The length of the compressed data is supposed to be the value of the
237 * ostream.output pointer before flushing, which is now the
238 * output.next_bit_output pointer after flushing.
240 * There will be an extra 2 bytes at the ostream.bit_output pointer,
241 * which is zeroed out. (These 2 bytes may be either the last bytes in
242 * the compressed data, in which case they are actually unnecessary, or
243 * they may precede a number of bytes embedded into the bitstream.) */
244 if (ostream.bit_output >
245 (const u8*)_compressed_data + uncompressed_len - 3)
247 *(u16*)ostream.bit_output = cpu_to_le16(0);
248 compressed_len = ostream.next_bit_output - (const u8*)_compressed_data;
250 wimlib_assert(compressed_len <= uncompressed_len - 1);
252 #ifdef ENABLE_VERIFY_COMPRESSION
253 /* Verify that we really get the same thing back when decompressing. */
255 u8 buf[uncompressed_len];
256 ret = wimlib_xpress_decompress(_compressed_data, compressed_len,
257 buf, uncompressed_len);
259 ERROR("xpress_compress(): Failed to decompress data we "
263 for (i = 0; i < uncompressed_len; i++) {
264 if (buf[i] != uncompressed_data[i]) {
265 ERROR("xpress_compress(): Data we compressed didn't "
266 "decompress to the original data (difference at "
267 "byte %u of %u)", i + 1, uncompressed_len);
273 return compressed_len;