ad9dcff76de3718ba19a4a902bb4dfe4deb39353
[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 #ifdef HAVE_ALLOCA_H
40 #  include <alloca.h>
41 #endif
42
43 #include <string.h>
44
45 /* Intermediate XPRESS match/literal representation.  */
46 struct xpress_match {
47         u16 adjusted_len;  /* Match length minus XPRESS_MIN_MATCH_LEN */
48         u16 offset;        /* Match offset */
49         /* For literals, offset == 0 and adjusted_len is the literal.  */
50 };
51
52 /*
53  * Writes @match, which is a match given in the intermediate representation for
54  * XPRESS matches, to the output stream @ostream.
55  *
56  * @codewords and @lens provide the Huffman code that is being used.
57  */
58 static void
59 xpress_write_match(struct xpress_match match,
60                    struct output_bitstream *restrict ostream,
61                    const u16 codewords[restrict],
62                    const u8 lens[restrict])
63 {
64         u8 len_hdr = min(match.adjusted_len, 0xf);
65         u8 offset_bsr = bsr32(match.offset);
66         unsigned sym = XPRESS_NUM_CHARS + ((offset_bsr << 4) | len_hdr);
67
68         bitstream_put_bits(ostream, codewords[sym], lens[sym]);
69
70         if (match.adjusted_len >= 0xf) {
71                 u8 byte1 = min(match.adjusted_len - 0xf, 0xff);
72                 bitstream_put_byte(ostream, byte1);
73                 if (byte1 == 0xff) {
74                         bitstream_put_byte(ostream, match.adjusted_len & 0xff);
75                         bitstream_put_byte(ostream, match.adjusted_len >> 8);
76                 }
77         }
78         bitstream_put_bits(ostream, match.offset ^ (1U << offset_bsr), offset_bsr);
79 }
80
81 static void
82 xpress_write_matches_and_literals(struct output_bitstream *ostream,
83                                   const struct xpress_match matches[restrict],
84                                   input_idx_t num_matches,
85                                   const u16 codewords[restrict],
86                                   const u8 lens[restrict])
87 {
88         for (input_idx_t i = 0; i < num_matches; i++) {
89                 if (matches[i].offset) {
90                         /* Real match  */
91                         xpress_write_match(matches[i], ostream, codewords, lens);
92                 } else {
93                         /* Literal byte  */
94                         u8 lit = matches[i].adjusted_len;
95                         bitstream_put_bits(ostream, codewords[lit], lens[lit]);
96                 }
97         }
98         bitstream_put_bits(ostream, codewords[XPRESS_END_OF_DATA], lens[XPRESS_END_OF_DATA]);
99 }
100
101 struct xpress_record_ctx {
102         input_idx_t freqs[XPRESS_NUM_SYMBOLS];
103         struct xpress_match *matches;
104 };
105
106 static void
107 xpress_record_literal(u8 lit, void *_ctx)
108 {
109         struct xpress_record_ctx *ctx = _ctx;
110         ctx->freqs[lit]++;
111         *(ctx->matches++) = (struct xpress_match) { .offset = 0, .adjusted_len = lit };
112 }
113
114 static void
115 xpress_record_match(unsigned len, unsigned offset, void *_ctx)
116 {
117         struct xpress_record_ctx *ctx = _ctx;
118
119         XPRESS_ASSERT(len >= XPRESS_MIN_MATCH_LEN);
120         XPRESS_ASSERT(len <= XPRESS_MAX_MATCH_LEN);
121         XPRESS_ASSERT(offset >= XPRESS_MIN_OFFSET);
122         XPRESS_ASSERT(offset <= XPRESS_MAX_OFFSET);
123
124         unsigned adjusted_len = len - XPRESS_MIN_MATCH_LEN;
125         unsigned len_hdr = min(adjusted_len, 0xf);
126         unsigned sym = XPRESS_NUM_CHARS + ((bsr32(offset) << 4) | len_hdr);
127
128         XPRESS_ASSERT(sym >= XPRESS_NUM_CHARS);
129         XPRESS_ASSERT(sym < XPRESS_NUM_SYMBOLS);
130
131         ctx->freqs[sym]++;
132         *(ctx->matches++) = (struct xpress_match) { .offset = offset,
133                                                     .adjusted_len = adjusted_len };
134 }
135
136 static const struct lz_params xpress_lz_params = {
137         .min_match      = XPRESS_MIN_MATCH_LEN,
138         .max_match      = XPRESS_MAX_MATCH_LEN,
139         .max_offset     = XPRESS_MAX_OFFSET,
140         .good_match     = 16,
141         .nice_match     = 32,
142         .max_chain_len  = 16,
143         .max_lazy_match = 16,
144         .too_far        = 4096,
145 };
146
147 /* API function documented in wimlib.h  */
148 WIMLIBAPI unsigned
149 wimlib_xpress_compress(const void * restrict uncompressed_data,
150                        unsigned uncompressed_len,
151                        void * restrict compressed_data)
152 {
153         u8 *cptr = compressed_data;
154         struct output_bitstream ostream;
155
156         struct xpress_record_ctx record_ctx;
157
158         struct xpress_match *matches;
159         input_idx_t *prev_tab;
160         u8 *udata;
161
162         u16 codewords[XPRESS_NUM_SYMBOLS];
163         u8 lens[XPRESS_NUM_SYMBOLS];
164         input_idx_t num_matches;
165         input_idx_t compressed_len;
166         input_idx_t i;
167         const size_t stack_max = 65536;
168
169         /* XPRESS requires 256 bytes of overhead for the Huffman code, so it's
170          * impossible to compress 256 bytes or less of data to less than the
171          * input size.
172          *
173          * +1 to take into account that the buffer for compressed data is 1 byte
174          * smaller than the buffer for uncompressed data.
175          *
176          * +4 to take into account that init_output_bitstream() requires at
177          * least 4 bytes of data.  */
178         if (uncompressed_len < XPRESS_NUM_SYMBOLS / 2 + 1 + 4)
179                 return 0;
180
181         if (uncompressed_len <= stack_max) {
182                 matches = alloca(uncompressed_len * sizeof(matches[0]));
183                 udata = alloca(uncompressed_len + 8);
184                 prev_tab = alloca(uncompressed_len * sizeof(prev_tab[0]));
185         } else {
186                 matches = MALLOC(uncompressed_len * sizeof(matches[0]));
187                 udata = MALLOC(uncompressed_len + 8);
188                 prev_tab = MALLOC(uncompressed_len * sizeof(prev_tab[0]));
189                 if (matches == NULL || udata == NULL || prev_tab == NULL) {
190                         WARNING("Failed to allocate memory for compression...");
191                         compressed_len = 0;
192                         goto out_free;
193                 }
194         }
195
196         /* Copy the data to a temporary buffer, but only to avoid
197          * inconsequential accesses of uninitialized memory in
198          * lz_analyze_block().  */
199         memcpy(udata, uncompressed_data, uncompressed_len);
200         memset(udata + uncompressed_len, 0, 8);
201
202         /* Determine match/literal sequence to divide the data into.  */
203         ZERO_ARRAY(record_ctx.freqs);
204         record_ctx.matches = matches;
205         lz_analyze_block(udata,
206                          uncompressed_len,
207                          xpress_record_match,
208                          xpress_record_literal,
209                          &record_ctx,
210                          &xpress_lz_params,
211                          prev_tab);
212
213         num_matches = (record_ctx.matches - matches);
214
215         /* Account for end of data symbol.  */
216         record_ctx.freqs[XPRESS_END_OF_DATA]++;
217
218         /* Build the Huffman code.  */
219         make_canonical_huffman_code(XPRESS_NUM_SYMBOLS, XPRESS_MAX_CODEWORD_LEN,
220                                     record_ctx.freqs, lens, codewords);
221
222         /* Output the Huffman code as a series of 512 4-bit lengths.  */
223         for (i = 0; i < XPRESS_NUM_SYMBOLS; i += 2)
224                 *cptr++ = (lens[i] & 0xf) | (lens[i + 1] << 4);
225
226         /* Output the encoded matches/literals.  */
227         init_output_bitstream(&ostream, cptr,
228                               uncompressed_len - XPRESS_NUM_SYMBOLS / 2 - 1);
229         xpress_write_matches_and_literals(&ostream, matches,
230                                           num_matches, codewords, lens);
231
232         /* Flush any pending data and get the length of the compressed data.  */
233         compressed_len = flush_output_bitstream(&ostream);
234         if (compressed_len == ~(input_idx_t)0) {
235                 compressed_len = 0;
236                 goto out_free;
237         }
238         compressed_len += XPRESS_NUM_SYMBOLS / 2;
239
240 #if defined(ENABLE_XPRESS_DEBUG) || defined(ENABLE_VERIFY_COMPRESSION)
241         /* Verify that we really get the same thing back when decompressing.  */
242         if (wimlib_xpress_decompress(compressed_data, compressed_len,
243                                      udata, uncompressed_len))
244         {
245                 ERROR("Failed to decompress data we "
246                       "compressed using XPRESS algorithm");
247                 wimlib_assert(0);
248                 compressed_len = 0;
249                 goto out_free;
250         }
251
252         if (memcmp(uncompressed_data, udata, uncompressed_len)) {
253                 ERROR("Data we compressed using XPRESS algorithm "
254                       "didn't decompress to original");
255                 wimlib_assert(0);
256                 compressed_len = 0;
257                 goto out_free;
258         }
259 #endif
260
261 out_free:
262         if (uncompressed_len > stack_max) {
263                 FREE(matches);
264                 FREE(udata);
265                 FREE(prev_tab);
266         }
267         return compressed_len;
268 }