wimlib.net Git - wimlib/blob - src/xpress-comp.c

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