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