Compiler stuff
[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 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 #ifdef HAVE_CONFIG_H
29 #  include "config.h"
30 #endif
31
32 #include "wimlib.h"
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"
38
39 #include <stdlib.h>
40 #include <string.h>
41
42 /*
43  * Writes @match, which is a match given in the intermediate representation for
44  * XPRESS matches, to the output stream @ostream.
45  *
46  * @codewords and @lens provide the Huffman code that is being used.
47  */
48 static int
49 xpress_write_match(struct output_bitstream *restrict ostream,
50                    u32 match,
51                    const u16 codewords[restrict],
52                    const u8 lens[restrict])
53 {
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;
59         int ret;
60
61         ret = bitstream_put_bits(ostream, codewords[sym], lens[sym]);
62         if (ret)
63                 return ret;
64
65         if (adjusted_match_len >= 0xf) {
66                 u8 byte1 = min(adjusted_match_len - 0xf, 0xff);
67                 ret = bitstream_put_byte(ostream, byte1);
68                 if (ret)
69                         return ret;
70                 if (byte1 == 0xff) {
71                         ret = bitstream_put_two_bytes(ostream, adjusted_match_len);
72                         if (ret)
73                                 return ret;
74                 }
75         }
76         return bitstream_put_bits(ostream,
77                                   match_offset ^ (1 << offset_bsr), offset_bsr);
78 }
79
80 static int
81 xpress_write_compressed_literals(struct output_bitstream *ostream,
82                                  const u32 match_tab[restrict],
83                                  unsigned num_matches,
84                                  const u16 codewords[restrict],
85                                  const u8 lens[restrict])
86 {
87         for (unsigned i = 0; i < num_matches; i++) {
88                 int ret;
89                 u32 match = match_tab[i];
90
91                 if (match >= XPRESS_NUM_CHARS) /* match */
92                         ret = xpress_write_match(ostream, match, codewords,
93                                                  lens);
94                 else /* literal byte */
95                         ret = bitstream_put_bits(ostream, codewords[match],
96                                                  lens[match]);
97                 if (ret)
98                         return ret;
99         }
100         return bitstream_put_bits(ostream, codewords[XPRESS_END_OF_DATA],
101                                   lens[XPRESS_END_OF_DATA]);
102 }
103
104 static u32
105 xpress_record_literal(u8 literal, void *_freq_tab)
106 {
107         freq_t *freq_tab = _freq_tab;
108         freq_tab[literal]++;
109         return literal;
110 }
111
112 static u32
113 xpress_record_match(unsigned match_offset, unsigned match_len,
114                     void *freq_tab, void *_ignore)
115 {
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);
120
121         /*
122          * The intermediate representation of XPRESS matches is as follows:
123          *
124          * bits    description
125          * ----    -----------------------------------------------------------
126          *
127          * 16-31   match offset (XPRESS_MIN_OFFSET < x < XPRESS_MAX_OFFSET)
128          *
129          * 0-15    adjusted match length (0 <= x <= XPRESS_MAX_MATCH - XPRESS_MIN_MATCH)
130          *
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. */
134
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);
141 }
142
143 static const struct lz_params xpress_lz_params = {
144         .min_match      = XPRESS_MIN_MATCH,
145         .max_match      = XPRESS_MAX_MATCH,
146         .good_match     = 16,
147         .nice_match     = 32,
148         .max_chain_len  = 16,
149         .max_lazy_match = 16,
150         .too_far        = 4096,
151 };
152
153 /* Documented in wimlib.h */
154 WIMLIBAPI unsigned
155 wimlib_xpress_compress(const void * restrict _uncompressed_data,
156                        unsigned uncompressed_len,
157                        void * restrict _compressed_data)
158 {
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         u8 uncompressed_data[uncompressed_len + 8];
170
171         memcpy(uncompressed_data, _uncompressed_data, uncompressed_len);
172         memset(uncompressed_data + uncompressed_len, 0, 8);
173
174         wimlib_assert(uncompressed_len <= 32768);
175
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
178          * input size.
179          *
180          * +1 to take into account that the buffer for compressed data is 1 byte
181          * smaller than the buffer for uncompressed data.
182          *
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)
186                 return 0;
187
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,
192                                        NULL, freq_tab,
193                                        &xpress_lz_params);
194
195         freq_tab[XPRESS_END_OF_DATA]++;
196
197         make_canonical_huffman_code(XPRESS_NUM_SYMBOLS, XPRESS_MAX_CODEWORD_LEN,
198                                     freq_tab, lens, codewords);
199
200         /* IMPORTANT NOTE:
201          *
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().
208          *
209          * Because of this, init_output_bitstream() is not called until after
210          * the lengths table is output.
211          */
212         for (i = 0; i < XPRESS_NUM_SYMBOLS; i += 2)
213                 *compressed_data++ = (lens[i] & 0xf) | (lens[i + 1] << 4);
214
215         init_output_bitstream(&ostream, compressed_data,
216                               uncompressed_len - XPRESS_NUM_SYMBOLS / 2 - 1);
217
218         ret = xpress_write_compressed_literals(&ostream, match_tab,
219                                                num_matches, codewords, lens);
220         if (ret)
221                 return 0;
222
223         /* Flush any bits that are buffered. */
224         ret = flush_output_bitstream(&ostream);
225         if (ret)
226                 return 0;
227
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);
235
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.
239          *
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)
246                 return 0;
247         *(u16*)ostream.bit_output = cpu_to_le16(0);
248         compressed_len = ostream.next_bit_output - (const u8*)_compressed_data;
249
250         wimlib_assert(compressed_len <= uncompressed_len - 1);
251
252 #ifdef ENABLE_VERIFY_COMPRESSION
253         /* Verify that we really get the same thing back when decompressing. */
254         {
255                 u8 buf[uncompressed_len];
256                 ret = wimlib_xpress_decompress(_compressed_data, compressed_len,
257                                                buf, uncompressed_len);
258                 if (ret) {
259                         ERROR("xpress_compress(): Failed to decompress data we "
260                               "compressed");
261                         abort();
262                 }
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);
268                                 abort();
269                         }
270                 }
271         }
272 #endif
273         return compressed_len;
274 }