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 <stdlib.h>
  40 #include <string.h>
  41
  42 /*
  43  * Writes @match, which is a match given in the intermediate representation for
  44  * XPRESS matches, to the output stream @ostream.
  45  *
  46  * @codewords and @lens provide the Huffman code that is being used.
  47  */
  48 static int
  49 xpress_write_match(struct output_bitstream *ostream, u32 match,
  50                    const u16 codewords[], const u8 lens[])
  51 {
  52         u32 adjusted_match_len = match & 0xffff;
  53         u32 match_offset = match >> 16;
  54         u32 len_hdr = min(adjusted_match_len, 0xf);
  55         u32 offset_bsr = bsr32(match_offset);
  56         u32 sym = len_hdr | (offset_bsr << 4) | XPRESS_NUM_CHARS;
  57         int ret;
  58
  59         ret = bitstream_put_bits(ostream, codewords[sym], lens[sym]);
  60         if (ret != 0)
  61                 return ret;
  62
  63         if (adjusted_match_len >= 0xf) {
  64                 u8 byte1 = min(adjusted_match_len - 0xf, 0xff);
  65                 ret = bitstream_put_byte(ostream, byte1);
  66                 if (ret != 0)
  67                         return ret;
  68                 if (byte1 == 0xff) {
  69                         ret = bitstream_put_two_bytes(ostream, adjusted_match_len);
  70                         if (ret != 0)
  71                                 return ret;
  72                 }
  73         }
  74         return bitstream_put_bits(ostream,
  75                                   match_offset ^ (1 << offset_bsr), offset_bsr);
  76 }
  77
  78 static int
  79 xpress_write_compressed_literals(struct output_bitstream *ostream,
  80                                  const u32 match_tab[],
  81                                  unsigned num_matches,
  82                                  const u16 codewords[],
  83                                  const u8 lens[])
  84 {
  85         for (unsigned i = 0; i < num_matches; i++) {
  86                 int ret;
  87                 u32 match = match_tab[i];
  88
  89                 if (match >= XPRESS_NUM_CHARS) /* match */
  90                         ret = xpress_write_match(ostream, match, codewords,
  91                                                  lens);
  92                 else /* literal byte */
  93                         ret = bitstream_put_bits(ostream, codewords[match],
  94                                                  lens[match]);
  95                 if (ret != 0)
  96                         return ret;
  97         }
  98         return bitstream_put_bits(ostream, codewords[XPRESS_END_OF_DATA],
  99                                   lens[XPRESS_END_OF_DATA]);
 100 }
 101
 102 static u32
 103 xpress_record_literal(u8 literal, void *__freq_tab)
 104 {
 105         freq_t *freq_tab = __freq_tab;
 106         freq_tab[literal]++;
 107         return literal;
 108 }
 109
 110 static u32
 111 xpress_record_match(unsigned match_offset, unsigned match_len,
 112                     void *freq_tab, void *ignore)
 113 {
 114         wimlib_assert(match_len >= XPRESS_MIN_MATCH &&
 115                       match_len <= XPRESS_MAX_MATCH);
 116         wimlib_assert(match_offset >= XPRESS_MIN_OFFSET &&
 117                       match_offset <= XPRESS_MAX_OFFSET);
 118
 119         /*
 120          * The intermediate representation of XPRESS matches is as follows:
 121          *
 122          * bits    description
 123          * ----    -----------------------------------------------------------
 124          *
 125          * 16-31   match offset (XPRESS_MIN_OFFSET < x < XPRESS_MAX_OFFSET)
 126          *
 127          * 0-15    adjusted match length (0 <= x <= XPRESS_MAX_MATCH - XPRESS_MIN_MATCH)
 128          *
 129          * Literals are simply represented as themselves and can be
 130          * distinguished from matches by the fact that only literals will have
 131          * the upper three bytes completely clear. */
 132
 133         u32 adjusted_match_len = match_len - XPRESS_MIN_MATCH;
 134         u32 len_hdr = min(adjusted_match_len, 0xf);
 135         u32 offset_bsr = bsr32(match_offset);
 136         u32 sym = len_hdr | (offset_bsr << 4) | XPRESS_NUM_CHARS;
 137         ((freq_t*)freq_tab)[sym]++;
 138         return adjusted_match_len | (match_offset << 16);
 139 }
 140
 141 static const struct lz_params xpress_lz_params = {
 142         .min_match      = XPRESS_MIN_MATCH,
 143         .max_match      = XPRESS_MAX_MATCH,
 144         .good_match     = 16,
 145         .nice_match     = 32,
 146         .max_chain_len  = 16,
 147         .max_lazy_match = 16,
 148         .too_far        = 4096,
 149 };
 150
 151 /* Documented in wimlib.h */
 152 WIMLIBAPI unsigned
 153 wimlib_xpress_compress(const void *__uncompressed_data,
 154                        unsigned uncompressed_len, void *__compressed_data)
 155 {
 156         u8 *compressed_data = __compressed_data;
 157         struct output_bitstream ostream;
 158         u32 match_tab[uncompressed_len];
 159         freq_t freq_tab[XPRESS_NUM_SYMBOLS];
 160         u16 codewords[XPRESS_NUM_SYMBOLS];
 161         u8 lens[XPRESS_NUM_SYMBOLS];
 162         unsigned num_matches;
 163         unsigned compressed_len;
 164         unsigned i;
 165         int ret;
 166         u8 uncompressed_data[uncompressed_len + 8];
 167
 168         memcpy(uncompressed_data, __uncompressed_data, uncompressed_len);
 169         memset(uncompressed_data + uncompressed_len, 0, 8);
 170
 171         wimlib_assert(uncompressed_len <= 32768);
 172
 173         /* XPRESS requires 256 bytes of overhead for the Huffman tables, so it's
 174          * impossible cannot compress 256 bytes or less of data to less than the
 175          * input size.
 176          *
 177          * +1 to take into account that the buffer for compressed data is 1 byte
 178          * smaller than the buffer for uncompressed data.
 179          *
 180          * +4 to take into account that init_output_bitstream() requires at
 181          * least 4 bytes of data. */
 182         if (uncompressed_len < XPRESS_NUM_SYMBOLS / 2 + 1 + 4)
 183                 return 0;
 184
 185         ZERO_ARRAY(freq_tab);
 186         num_matches = lz_analyze_block(uncompressed_data, uncompressed_len,
 187                                        match_tab, xpress_record_match,
 188                                        xpress_record_literal, freq_tab,
 189                                        NULL, freq_tab,
 190                                        &xpress_lz_params);
 191
 192         freq_tab[XPRESS_END_OF_DATA]++;
 193
 194         make_canonical_huffman_code(XPRESS_NUM_SYMBOLS, XPRESS_MAX_CODEWORD_LEN,
 195                                     freq_tab, lens, codewords);
 196
 197         /* IMPORTANT NOTE:
 198          *
 199          * It's tempting to output the 512 Huffman codeword lengths using the
 200          * bitstream_put_bits() function.  However, this is NOT correct because
 201          * bitstream_put_bits() will output 2 bytes at a time in little-endian
 202          * order, which is the order that is needed for the compressed literals.
 203          * However, the bytes in the lengths table are in order, so they need to
 204          * be written one at a time without using bitstream_put_bits().
 205          *
 206          * Because of this, init_output_bitstream() is not called until after
 207          * the lengths table is output.
 208          */
 209         for (i = 0; i < XPRESS_NUM_SYMBOLS; i += 2)
 210                 *compressed_data++ = (lens[i] & 0xf) | (lens[i + 1] << 4);
 211
 212         init_output_bitstream(&ostream, compressed_data,
 213                               uncompressed_len - XPRESS_NUM_SYMBOLS / 2 - 1);
 214
 215         ret = xpress_write_compressed_literals(&ostream, match_tab,
 216                                                num_matches, codewords, lens);
 217         if (ret)
 218                 return 0;
 219
 220         /* Flush any bits that are buffered. */
 221         ret = flush_output_bitstream(&ostream);
 222         if (ret)
 223                 return 0;
 224
 225         /* Assert that there are no output bytes between the ostream.output
 226          * pointer and the ostream.next_bit_output pointer.  This can only
 227          * happen if bytes had been written at the ostream.output pointer before
 228          * the last bit word was written to the stream.  But, this does not
 229          * occur since xpress_write_match() always finishes by writing some bits
 230          * (a Huffman symbol), and the bitstream was just flushed. */
 231         wimlib_assert(ostream.output - ostream.next_bit_output == 2);
 232
 233         /* The length of the compressed data is supposed to be the value of the
 234          * ostream.output pointer before flushing, which is now the
 235          * output.next_bit_output pointer after flushing.
 236          *
 237          * There will be an extra 2 bytes at the ostream.bit_output pointer,
 238          * which is zeroed out.  (These 2 bytes may be either the last bytes in
 239          * the compressed data, in which case they are actually unnecessary, or
 240          * they may precede a number of bytes embedded into the bitstream.) */
 241         if (ostream.bit_output >
 242             (const u8*)__compressed_data + uncompressed_len - 3)
 243                 return 0;
 244         *(u16*)ostream.bit_output = cpu_to_le16(0);
 245         compressed_len = ostream.next_bit_output - (const u8*)__compressed_data;
 246
 247         wimlib_assert(compressed_len <= uncompressed_len - 1);
 248
 249 #ifdef ENABLE_VERIFY_COMPRESSION
 250         /* Verify that we really get the same thing back when decompressing. */
 251         {
 252                 u8 buf[uncompressed_len];
 253                 ret = wimlib_xpress_decompress(__compressed_data, compressed_len,
 254                                                buf, uncompressed_len);
 255                 if (ret) {
 256                         ERROR("xpress_compress(): Failed to decompress data we "
 257                               "compressed");
 258                         abort();
 259                 }
 260                 for (i = 0; i < uncompressed_len; i++) {
 261                         if (buf[i] != uncompressed_data[i]) {
 262                                 ERROR("xpress_compress(): Data we compressed didn't "
 263                                       "decompress to the original data (difference at "
 264                                       "byte %u of %u)", i + 1, uncompressed_len);
 265                                 abort();
 266                         }
 267                 }
 268         }
 269 #endif
 270         return compressed_len;
 271 }