wimlib.net Git - wimlib/blob - 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 const struct compressor_ops xpress_compressor_ops = {
 318         .create_compressor  = xpress_create_compressor,
 319         .compress           = xpress_compress,
 320         .free_compressor    = xpress_free_compressor,
 321 };