Fix sequential extraction, and include progress info
[wimlib] / src / xpress-comp.c
1 /*
2  * xpress-comp.c
3  *
4  * XPRESS compression routines.
5  *
6  * See the comments in xpress-decomp.c about the XPRESS format.
7  */
8
9 /*
10  * Copyright (C) 2012 Eric 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 "comp.h"
30 #include <stdlib.h>
31 #include <string.h>
32
33 static inline u32 bsr32(u32 n)
34 {
35 #if defined(__x86__) || defined(__x86_64__)
36         asm("bsrl %0, %0;"
37                         : "=r"(n)
38                         : "0" (n));
39         return n;
40 #else
41         u32 pow = 0;
42         while ((n >>= 1) != 0)
43                 pow++;
44         return pow;
45 #endif
46 }
47
48
49 /*
50  * Writes @match, which is a match given in the intermediate representation for
51  * XPRESS matches, to the output stream @ostream.
52  *
53  * @codewords and @lens provide the Huffman code that is being used.
54  */
55 static int xpress_write_match(struct output_bitstream *ostream, u32 match,
56                               const u16 codewords[], const u8 lens[])
57 {
58         uint main_sym;
59         uint huff_sym;
60         uint offset_bsr;
61         uint match_len;
62         uint match_offset;
63         int ret;
64         u8 byte1;
65
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]);
69         if (ret != 0)
70                 return ret;
71
72         offset_bsr = main_sym >> 4;
73
74         match_len = (match >> 8) & 0xff;
75         match_offset = (match >> 16);
76
77
78         match_len -= XPRESS_MIN_MATCH;
79         if (match_len >= 0xf) {
80                 byte1 = (u8)(match_len - 0xf);
81                 ret = bitstream_put_byte(ostream, byte1);
82                 if (ret != 0)
83                         return ret;
84                 if (byte1 == 0xff) {
85                         ret = bitstream_put_two_bytes(ostream, match_len);
86                         if (ret != 0)
87                                 return ret;
88                 }
89         }
90         return bitstream_put_bits(ostream, match_offset ^ (1 << offset_bsr),
91                                                         offset_bsr);
92 }
93
94 static int xpress_write_compressed_literals(struct output_bitstream *ostream,
95                                             const u32 match_tab[],
96                                             uint num_matches,
97                                             const u16 codewords[],
98                                             const u8 lens[])
99 {
100         uint i;
101         u32 match;
102         int ret;
103
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,
108                                                  lens);
109                 else /* literal byte */
110                         ret = bitstream_put_bits(ostream, codewords[match],
111                                                  lens[match]);
112                 if (ret != 0)
113                         return ret;
114         }
115         return bitstream_put_bits(ostream, codewords[256], lens[256]);
116 }
117
118 static u32 xpress_record_literal(u8 literal, void *__freq_tab)
119 {
120         u32 *freq_tab = __freq_tab;
121         freq_tab[literal]++;
122         return literal;
123 }
124
125 static u32 xpress_record_match(uint match_offset, uint match_len,
126                                void *__freq_tab, void *ignore)
127 {
128         u32 *freq_tab = __freq_tab;
129         u32 len_hdr;
130         u32 offset_bsr;
131         u32 match;
132
133         wimlib_assert(match_len >= XPRESS_MIN_MATCH &&
134                       match_len <= XPRESS_MAX_MATCH);
135         wimlib_assert(match_offset > 0);
136
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;
143         return match;
144 }
145
146 static const struct lz_params xpress_lz_params = {
147         .min_match      = 3,
148         .max_match      = XPRESS_MAX_MATCH,
149         .good_match     = 16,
150         .nice_match     = 32,
151         .max_chain_len  = 16,
152         .max_lazy_match = 16,
153         .too_far        = 4096,
154 };
155
156 /*
157  * Performs XPRESS compression on a block of data.
158  *
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
163  *                              written.
164  * @compressed_len_ret: A pointer to an unsigned int into which the length of
165  *                              the compressed data may be returned.
166  *
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
171  * compressed data.
172  */
173 int xpress_compress(const void *__uncompressed_data, uint uncompressed_len,
174                     void *__compressed_data, uint *compressed_len_ret)
175 {
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];
183         uint num_matches;
184         uint compressed_len;
185         uint i;
186         int ret;
187
188         XPRESS_DEBUG("uncompressed_len = %u", uncompressed_len);
189
190         if (uncompressed_len < 300)
191                 return 1;
192
193         ZERO_ARRAY(freq_tab);
194
195         num_matches = lz_analyze_block(uncompressed_data, uncompressed_len,
196                                        match_tab, xpress_record_match,
197                                        xpress_record_literal, freq_tab,
198                                        NULL, freq_tab,
199                                        &xpress_lz_params);
200
201         XPRESS_DEBUG("using %u matches", num_matches);
202
203         freq_tab[256]++;
204
205         make_canonical_huffman_code(XPRESS_NUM_SYMBOLS, XPRESS_MAX_CODEWORD_LEN,
206                                     freq_tab, lens, codewords);
207
208         /* IMPORTANT NOTE:
209          *
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().
216          *
217          * Because of this, init_output_bitstream() is not called until after
218          * the lengths table is output.
219          */
220         for (i = 0; i < XPRESS_NUM_SYMBOLS; i += 2)
221                 *compressed_data++ = (lens[i] & 0xf) | (lens[i + 1] << 4);
222
223         init_output_bitstream(&ostream, compressed_data,
224                               uncompressed_len - XPRESS_NUM_SYMBOLS / 2 - 1);
225
226         ret = xpress_write_compressed_literals(&ostream, match_tab,
227                                                num_matches, codewords, lens);
228         if (ret != 0)
229                 return ret;
230
231         /* Flush any bits that are buffered. */
232         ret = flush_output_bitstream(&ostream);
233         if (ret != 0)
234                 return ret;
235
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);
243
244         /*
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.
248          *
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.)
253          */
254         if (ostream.bit_output >
255             (const u8*)__compressed_data + uncompressed_len - 3)
256                 return 1;
257         *(u16*)ostream.bit_output = cpu_to_le16(0);
258         compressed_len = ostream.next_bit_output - (const u8*)__compressed_data;
259
260         wimlib_assert(compressed_len <= uncompressed_len - 1);
261
262         XPRESS_DEBUG("Compressed %u => %u bytes",
263                      uncompressed_len, compressed_len);
264
265         *compressed_len_ret = compressed_len;
266
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,
272                                 uncompressed_len);
273         if (ret != 0) {
274                 ERROR("xpress_compress(): Failed to decompress data we "
275                       "compressed");
276                 abort();
277         }
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);
283                         abort();
284                 }
285         }
286         XPRESS_DEBUG("Compression verified to be correct.");
287 #endif
288
289         return 0;
290
291 }