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