175534c0c7a38e5aba180b98a012961204fe4d1f
[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/compressor_ops.h"
35 #include "wimlib/compress_common.h"
36 #include "wimlib/error.h"
37 #include "wimlib/lz_hash.h"
38 #include "wimlib/util.h"
39 #include "wimlib/xpress.h"
40
41 #ifdef HAVE_ALLOCA_H
42 #  include <alloca.h>
43 #endif
44 #include <stdlib.h>
45 #include <string.h>
46
47 struct xpress_record_ctx {
48         input_idx_t freqs[XPRESS_NUM_SYMBOLS];
49         struct xpress_match *matches;
50 };
51
52 struct xpress_compressor {
53         u8 *window;
54         u32 max_window_size;
55         struct xpress_match *matches;
56         input_idx_t *prev_tab;
57         u16 codewords[XPRESS_NUM_SYMBOLS];
58         u8 lens[XPRESS_NUM_SYMBOLS];
59         struct xpress_record_ctx record_ctx;
60 };
61
62 /* Intermediate XPRESS match/literal representation.  */
63 struct xpress_match {
64         u16 adjusted_len;  /* Match length minus XPRESS_MIN_MATCH_LEN */
65         u16 offset;        /* Match offset */
66         /* For literals, offset == 0 and adjusted_len is the literal.  */
67 };
68
69 /*
70  * Writes @match, which is a match given in the intermediate representation for
71  * XPRESS matches, to the output stream @ostream.
72  *
73  * @codewords and @lens provide the Huffman code that is being used.
74  */
75 static void
76 xpress_write_match(struct xpress_match match,
77                    struct output_bitstream *restrict ostream,
78                    const u16 codewords[restrict],
79                    const u8 lens[restrict])
80 {
81         u8 len_hdr = min(match.adjusted_len, 0xf);
82         u8 offset_bsr = bsr32(match.offset);
83         unsigned sym = XPRESS_NUM_CHARS + ((offset_bsr << 4) | len_hdr);
84
85         bitstream_put_bits(ostream, codewords[sym], lens[sym]);
86
87         if (match.adjusted_len >= 0xf) {
88                 u8 byte1 = min(match.adjusted_len - 0xf, 0xff);
89                 bitstream_put_byte(ostream, byte1);
90                 if (byte1 == 0xff) {
91                         bitstream_put_byte(ostream, match.adjusted_len & 0xff);
92                         bitstream_put_byte(ostream, match.adjusted_len >> 8);
93                 }
94         }
95         bitstream_put_bits(ostream, match.offset ^ (1U << offset_bsr), offset_bsr);
96 }
97
98 static void
99 xpress_write_matches_and_literals(struct output_bitstream *ostream,
100                                   const struct xpress_match matches[restrict],
101                                   input_idx_t num_matches,
102                                   const u16 codewords[restrict],
103                                   const u8 lens[restrict])
104 {
105         for (input_idx_t i = 0; i < num_matches; i++) {
106                 if (matches[i].offset) {
107                         /* Real match  */
108                         xpress_write_match(matches[i], ostream, codewords, lens);
109                 } else {
110                         /* Literal byte  */
111                         u8 lit = matches[i].adjusted_len;
112                         bitstream_put_bits(ostream, codewords[lit], lens[lit]);
113                 }
114         }
115         bitstream_put_bits(ostream, codewords[XPRESS_END_OF_DATA], lens[XPRESS_END_OF_DATA]);
116 }
117
118 static void
119 xpress_record_literal(u8 lit, void *_ctx)
120 {
121         struct xpress_record_ctx *ctx = _ctx;
122         ctx->freqs[lit]++;
123         *(ctx->matches++) = (struct xpress_match) { .offset = 0, .adjusted_len = lit };
124 }
125
126 static void
127 xpress_record_match(unsigned len, unsigned offset, void *_ctx)
128 {
129         struct xpress_record_ctx *ctx = _ctx;
130
131         XPRESS_ASSERT(len >= XPRESS_MIN_MATCH_LEN);
132         XPRESS_ASSERT(len <= XPRESS_MAX_MATCH_LEN);
133         XPRESS_ASSERT(offset >= XPRESS_MIN_OFFSET);
134         XPRESS_ASSERT(offset <= XPRESS_MAX_OFFSET);
135
136         unsigned adjusted_len = len - XPRESS_MIN_MATCH_LEN;
137         unsigned len_hdr = min(adjusted_len, 0xf);
138         unsigned sym = XPRESS_NUM_CHARS + ((bsr32(offset) << 4) | len_hdr);
139
140         XPRESS_ASSERT(sym >= XPRESS_NUM_CHARS);
141         XPRESS_ASSERT(sym < XPRESS_NUM_SYMBOLS);
142
143         ctx->freqs[sym]++;
144         *(ctx->matches++) = (struct xpress_match) { .offset = offset,
145                                                     .adjusted_len = adjusted_len };
146 }
147
148 static const struct lz_params xpress_lz_params = {
149         .min_match      = XPRESS_MIN_MATCH_LEN,
150         .max_match      = XPRESS_MAX_MATCH_LEN,
151         .max_offset     = XPRESS_MAX_OFFSET,
152         .good_match     = 16,
153         .nice_match     = 32,
154         .max_chain_len  = 16,
155         .max_lazy_match = 16,
156         .too_far        = 4096,
157 };
158
159 static size_t
160 xpress_compress(const void *uncompressed_data, size_t uncompressed_size,
161                 void *compressed_data, size_t compressed_size_avail, void *_c)
162 {
163         struct xpress_compressor *c = _c;
164         u8 *cptr = compressed_data;
165         struct output_bitstream ostream;
166         input_idx_t num_matches;
167         input_idx_t i;
168         size_t compressed_size;
169
170         /* XPRESS requires 256 bytes of overhead for the Huffman code, so it's
171          * impossible to 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 (compressed_size_avail < XPRESS_NUM_SYMBOLS / 2 + 1 + 4)
180                 return 0;
181
182         /* Copy the data to a temporary buffer, but only to avoid
183          * inconsequential accesses of uninitialized memory in
184          * lz_analyze_block().  */
185         memcpy(c->window, uncompressed_data, uncompressed_size);
186         memset(c->window + uncompressed_size, 0, 8);
187
188         /* Determine match/literal sequence to divide the data into.  */
189         memset(c->record_ctx.freqs, 0, sizeof(c->record_ctx.freqs));
190         c->record_ctx.matches = c->matches;
191         lz_analyze_block(c->window,
192                          uncompressed_size,
193                          xpress_record_match,
194                          xpress_record_literal,
195                          &c->record_ctx,
196                          &xpress_lz_params,
197                          c->prev_tab);
198
199         num_matches = (c->record_ctx.matches - c->matches);
200
201         /* Account for end of data symbol.  */
202         c->record_ctx.freqs[XPRESS_END_OF_DATA]++;
203
204         /* Build the Huffman code.  */
205         make_canonical_huffman_code(XPRESS_NUM_SYMBOLS, XPRESS_MAX_CODEWORD_LEN,
206                                     c->record_ctx.freqs, c->lens, c->codewords);
207
208         /* Output the Huffman code as a series of 512 4-bit lengths.  */
209         for (i = 0; i < XPRESS_NUM_SYMBOLS; i += 2)
210                 *cptr++ = (c->lens[i] & 0xf) | (c->lens[i + 1] << 4);
211
212         /* Output the encoded matches/literals.  */
213         init_output_bitstream(&ostream, cptr,
214                               compressed_size_avail - XPRESS_NUM_SYMBOLS / 2 - 1);
215
216         xpress_write_matches_and_literals(&ostream, c->matches,
217                                           num_matches, c->codewords, c->lens);
218
219         /* Flush any pending data and get the length of the compressed data.  */
220         compressed_size = flush_output_bitstream(&ostream);
221         if (compressed_size == ~(input_idx_t)0)
222                 return 0;
223
224         compressed_size += XPRESS_NUM_SYMBOLS / 2;
225
226 #if defined(ENABLE_XPRESS_DEBUG) || defined(ENABLE_VERIFY_COMPRESSION)
227         /* Verify that we really get the same thing back when decompressing.  */
228         {
229                 struct wimlib_decompressor *decompressor;
230
231                 if (0 == wimlib_create_decompressor(WIMLIB_COMPRESSION_TYPE_XPRESS,
232                                                     c->max_window_size,
233                                                     NULL,
234                                                     &decompressor))
235                 {
236                         int ret;
237                         ret = wimlib_decompress(compressed_data,
238                                                 compressed_size,
239                                                 c->window,
240                                                 uncompressed_size,
241                                                 decompressor);
242                         wimlib_free_decompressor(decompressor);
243
244                         if (ret) {
245                                 ERROR("Failed to decompress data we "
246                                       "compressed using XPRESS algorithm");
247                                 wimlib_assert(0);
248                                 return 0;
249                         }
250                         if (memcmp(uncompressed_data, c->window,
251                                    uncompressed_size))
252                         {
253                                 ERROR("Data we compressed using XPRESS algorithm "
254                                       "didn't decompress to original");
255                                 wimlib_assert(0);
256                                 return 0;
257                         }
258                 } else {
259                         WARNING("Failed to create decompressor for "
260                                 "data verification!");
261                 }
262         }
263 #endif
264
265         return compressed_size;
266 }
267
268 static void
269 xpress_free_compressor(void *_c)
270 {
271         struct xpress_compressor *c = _c;
272
273         if (c) {
274                 FREE(c->window);
275                 FREE(c->matches);
276                 FREE(c->prev_tab);
277                 FREE(c);
278         }
279 }
280
281 static int
282 xpress_create_compressor(size_t max_window_size,
283                          const struct wimlib_compressor_params_header *params,
284                          void **c_ret)
285 {
286         struct xpress_compressor *c;
287
288         if (max_window_size == 0 || max_window_size > (1U << 26))
289                 return WIMLIB_ERR_INVALID_PARAM;
290
291         c = CALLOC(1, sizeof(struct xpress_compressor));
292         if (c == NULL)
293                 goto oom;
294
295         c->window = MALLOC(max_window_size + 8);
296         if (c->window == NULL)
297                 goto oom;
298
299         c->max_window_size = max_window_size;
300
301         c->matches = MALLOC(max_window_size * sizeof(c->matches[0]));
302         if (c->matches == NULL)
303                 goto oom;
304
305         c->prev_tab = MALLOC(max_window_size * sizeof(c->prev_tab[0]));
306         if (c->prev_tab == NULL)
307                 goto oom;
308
309         *c_ret = c;
310         return 0;
311
312 oom:
313         xpress_free_compressor(c);
314         return WIMLIB_ERR_NOMEM;
315 }
316
317 static u64
318 xpress_get_needed_memory(size_t max_window_size,
319                          const struct wimlib_compressor_params_header *params)
320 {
321         u64 size = 0;
322
323         size += sizeof(struct xpress_compressor);
324         size += max_window_size + 8;
325         size += max_window_size * sizeof(((struct xpress_compressor*)0)->matches[0]);
326         size += max_window_size * sizeof(((struct xpress_compressor*)0)->prev_tab[0]);
327
328         return size;
329 }
330
331 const struct compressor_ops xpress_compressor_ops = {
332         .get_needed_memory  = xpress_get_needed_memory,
333         .create_compressor  = xpress_create_compressor,
334         .compress           = xpress_compress,
335         .free_compressor    = xpress_free_compressor,
336 };