b1fd3bd068477d6c2d44477cb4b0460a1a8b4518
[wimlib] / src / xpress-compress.c
1 /*
2  * xpress-compress.c
3  *
4  * XPRESS compression routines.
5  *
6  * See the comments in xpress-decompress.c about the XPRESS format.
7  */
8
9 /*
10  * Copyright (C) 2012, 2013 Biggers
11  *
12  * This file is part of wimlib, a library for working with WIM files.
13  *
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)
17  * any later version.
18  *
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
22  * details.
23  *
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/.
26  */
27
28 #include "xpress.h"
29 #include "compress.h"
30 #include <stdlib.h>
31 #include <string.h>
32
33 /*
34  * Writes @match, which is a match given in the intermediate representation for
35  * XPRESS matches, to the output stream @ostream.
36  *
37  * @codewords and @lens provide the Huffman code that is being used.
38  */
39 static int xpress_write_match(struct output_bitstream *ostream, u32 match,
40                               const u16 codewords[], const u8 lens[])
41 {
42         u32 adjusted_match_len = match & 0xffff;
43         u32 match_offset = match >> 16;
44         u32 len_hdr = min(adjusted_match_len, 0xf);
45         u32 offset_bsr = bsr32(match_offset);
46         u32 sym = len_hdr | (offset_bsr << 4) | XPRESS_NUM_CHARS;
47         int ret;
48
49         ret = bitstream_put_bits(ostream, codewords[sym], lens[sym]);
50         if (ret != 0)
51                 return ret;
52
53         if (adjusted_match_len >= 0xf) {
54                 u8 byte1 = min(adjusted_match_len - 0xf, 0xff);
55                 ret = bitstream_put_byte(ostream, byte1);
56                 if (ret != 0)
57                         return ret;
58                 if (byte1 == 0xff) {
59                         ret = bitstream_put_two_bytes(ostream, adjusted_match_len);
60                         if (ret != 0)
61                                 return ret;
62                 }
63         }
64         return bitstream_put_bits(ostream,
65                                   match_offset ^ (1 << offset_bsr), offset_bsr);
66 }
67
68 static int xpress_write_compressed_literals(struct output_bitstream *ostream,
69                                             const u32 match_tab[],
70                                             unsigned num_matches,
71                                             const u16 codewords[],
72                                             const u8 lens[])
73 {
74         for (unsigned i = 0; i < num_matches; i++) {
75                 int ret;
76                 u32 match = match_tab[i];
77
78                 if (match >= XPRESS_NUM_CHARS) /* match */
79                         ret = xpress_write_match(ostream, match, codewords,
80                                                  lens);
81                 else /* literal byte */
82                         ret = bitstream_put_bits(ostream, codewords[match],
83                                                  lens[match]);
84                 if (ret != 0)
85                         return ret;
86         }
87         return bitstream_put_bits(ostream, codewords[XPRESS_END_OF_DATA],
88                                   lens[XPRESS_END_OF_DATA]);
89 }
90
91 static u32 xpress_record_literal(u8 literal, void *__freq_tab)
92 {
93         freq_t *freq_tab = __freq_tab;
94         freq_tab[literal]++;
95         return literal;
96 }
97
98 static u32 xpress_record_match(unsigned match_offset, unsigned match_len,
99                                void *freq_tab, void *ignore)
100 {
101         wimlib_assert(match_len >= XPRESS_MIN_MATCH &&
102                       match_len <= XPRESS_MAX_MATCH);
103         wimlib_assert(match_offset >= XPRESS_MIN_OFFSET &&
104                       match_offset <= XPRESS_MAX_OFFSET);
105
106         /*
107          * The intermediate representation of XPRESS matches is as follows:
108          *
109          * bits    description
110          * ----    -----------------------------------------------------------
111          *
112          * 16-31   match offset (XPRESS_MIN_OFFSET < x < XPRESS_MAX_OFFSET)
113          *
114          * 0-15    adjusted match length (0 <= x <= XPRESS_MAX_MATCH - XPRESS_MIN_MATCH)
115          *
116          * Literals are simply represented as themselves and can be
117          * distinguished from matches by the fact that only literals will have
118          * the upper three bytes completely clear. */
119
120         u32 adjusted_match_len = match_len - XPRESS_MIN_MATCH;
121         u32 len_hdr = min(adjusted_match_len, 0xf);
122         u32 offset_bsr = bsr32(match_offset);
123         u32 sym = len_hdr | (offset_bsr << 4) | XPRESS_NUM_CHARS;
124         ((freq_t*)freq_tab)[sym]++;
125         return adjusted_match_len | (match_offset << 16);
126 }
127
128 static const struct lz_params xpress_lz_params = {
129         .min_match      = XPRESS_MIN_MATCH,
130         .max_match      = XPRESS_MAX_MATCH,
131         .good_match     = 16,
132         .nice_match     = 32,
133         .max_chain_len  = 16,
134         .max_lazy_match = 16,
135         .too_far        = 4096,
136 };
137
138 /*
139  * Performs XPRESS compression on a block of data.
140  *
141  * @__uncompressed_data:  Pointer to the data to be compressed.
142  * @uncompressed_len:   Length, in bytes, of the data to be compressed.
143  * @__compressed_data:  Pointer to a location at least (@uncompressed_len - 1)
144  *                              bytes long into which the compressed data may be
145  *                              written.
146  * @compressed_len_ret: A pointer to an unsigned int into which the length of
147  *                              the compressed data may be returned.
148  *
149  * Returns zero if compression was successfully performed.  In that case
150  * @compressed_data and @compressed_len_ret will contain the compressed data and
151  * its length.  A return value of nonzero means that compressing the data did
152  * not reduce its size, and @compressed_data will not contain the full
153  * compressed data.
154  */
155 int xpress_compress(const void *__uncompressed_data, unsigned uncompressed_len,
156                     void *__compressed_data, unsigned *compressed_len_ret)
157 {
158         const u8 *uncompressed_data = __uncompressed_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;
167         unsigned i;
168         int ret;
169
170         /* XPRESS requires 256 bytes of overhead for the Huffman tables, so it's
171          * impossible cannot compress 256 bytes or less of data to less than the
172          * input size.
173          *
174          * +1 to take into account that the buffer for compressed data is 1 byte
175          * smaller than the buffer for uncompressed data.
176          *
177          * +4 to take into account that init_output_bitstream() requires at
178          * least 4 bytes of data. */
179         if (uncompressed_len < XPRESS_NUM_SYMBOLS / 2 + 1 + 4)
180                 return 1;
181
182         ZERO_ARRAY(freq_tab);
183         num_matches = lz_analyze_block(uncompressed_data, uncompressed_len,
184                                        match_tab, xpress_record_match,
185                                        xpress_record_literal, freq_tab,
186                                        NULL, freq_tab,
187                                        &xpress_lz_params);
188
189         freq_tab[XPRESS_END_OF_DATA]++;
190
191         make_canonical_huffman_code(XPRESS_NUM_SYMBOLS, XPRESS_MAX_CODEWORD_LEN,
192                                     freq_tab, lens, codewords);
193
194         /* IMPORTANT NOTE:
195          *
196          * It's tempting to output the 512 Huffman codeword lengths using the
197          * bitstream_put_bits() function.  However, this is NOT correct because
198          * bitstream_put_bits() will output 2 bytes at a time in little-endian
199          * order, which is the order that is needed for the compressed literals.
200          * However, the bytes in the lengths table are in order, so they need to
201          * be written one at a time without using bitstream_put_bits().
202          *
203          * Because of this, init_output_bitstream() is not called until after
204          * the lengths table is output.
205          */
206         for (i = 0; i < XPRESS_NUM_SYMBOLS; i += 2)
207                 *compressed_data++ = (lens[i] & 0xf) | (lens[i + 1] << 4);
208
209         init_output_bitstream(&ostream, compressed_data,
210                               uncompressed_len - XPRESS_NUM_SYMBOLS / 2 - 1);
211
212         ret = xpress_write_compressed_literals(&ostream, match_tab,
213                                                num_matches, codewords, lens);
214         if (ret != 0)
215                 return ret;
216
217         /* Flush any bits that are buffered. */
218         ret = flush_output_bitstream(&ostream);
219         if (ret != 0)
220                 return ret;
221
222         /* Assert that there are no output bytes between the ostream.output
223          * pointer and the ostream.next_bit_output pointer.  This can only
224          * happen if bytes had been written at the ostream.output pointer before
225          * the last bit word was written to the stream.  But, this does not
226          * occur since xpress_write_match() always finishes by writing some bits
227          * (a Huffman symbol), and the bitstream was just flushed. */
228         wimlib_assert(ostream.output - ostream.next_bit_output == 2);
229
230         /* The length of the compressed data is supposed to be the value of the
231          * ostream.output pointer before flushing, which is now the
232          * output.next_bit_output pointer after flushing.
233          *
234          * There will be an extra 2 bytes at the ostream.bit_output pointer,
235          * which is zeroed out.  (These 2 bytes may be either the last bytes in
236          * the compressed data, in which case they are actually unnecessary, or
237          * they may precede a number of bytes embedded into the bitstream.) */
238         if (ostream.bit_output >
239             (const u8*)__compressed_data + uncompressed_len - 3)
240                 return 1;
241         *(u16*)ostream.bit_output = cpu_to_le16(0);
242         compressed_len = ostream.next_bit_output - (const u8*)__compressed_data;
243
244         wimlib_assert(compressed_len <= uncompressed_len - 1);
245
246         *compressed_len_ret = compressed_len;
247
248 #ifdef ENABLE_VERIFY_COMPRESSION
249         /* Verify that we really get the same thing back when decompressing. */
250         u8 buf[uncompressed_len];
251         ret = xpress_decompress(__compressed_data, compressed_len, buf,
252                                 uncompressed_len);
253         if (ret != 0) {
254                 ERROR("xpress_compress(): Failed to decompress data we "
255                       "compressed");
256                 abort();
257         }
258         for (i = 0; i < uncompressed_len; i++) {
259                 if (buf[i] != uncompressed_data[i]) {
260                         ERROR("xpress_compress(): Data we compressed didn't "
261                               "decompress to the original data (difference at "
262                               "byte %u of %u)", i + 1, uncompressed_len);
263                         abort();
264                 }
265         }
266 #endif
267         return 0;
268 }