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