wimlib.net Git - wimlib/blob - src/decompress_common.c

   1 /*
   2  * decompress_common.c
   3  *
   4  * Code for decompression shared among multiple compression formats.
   5  */
   6
   7 /*
   8  * Copyright (C) 2012, 2013 Eric Biggers
   9  *
  10  * This file is part of wimlib, a library for working with WIM files.
  11  *
  12  * wimlib is free software; you can redistribute it and/or modify it under the
  13  * terms of the GNU General Public License as published by the Free
  14  * Software Foundation; either version 3 of the License, or (at your option)
  15  * any later version.
  16  *
  17  * wimlib is distributed in the hope that it will be useful, but WITHOUT ANY
  18  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
  19  * A PARTICULAR PURPOSE. See the GNU General Public License for more
  20  * details.
  21  *
  22  * You should have received a copy of the GNU General Public License
  23  * along with wimlib; if not, see http://www.gnu.org/licenses/.
  24  */
  25
  26 #ifdef HAVE_CONFIG_H
  27 #  include "config.h"
  28 #endif
  29
  30 #include "wimlib/decompress_common.h"
  31 #include "wimlib/error.h"
  32 #include "wimlib/util.h"
  33
  34 #include <string.h>
  35
  36 #ifdef __GNUC__
  37 #  ifdef __SSE2__
  38 #    define USE_SSE2_FILL
  39 #    include <emmintrin.h>
  40 #  else
  41 #    define USE_LONG_FILL
  42 #  endif
  43 #endif
  44
  45 /*
  46  * make_huffman_decode_table: - Builds a fast huffman decoding table from an
  47  * array that gives the length of the codeword for each symbol in the alphabet.
  48  * Originally based on code written by David Tritscher (taken the original LZX
  49  * decompression code); also heavily modified to add some optimizations used in
  50  * the zlib code, as well as more comments; also added some optimizations to
  51  * make filling in the decode table entries faster (may not help significantly
  52  * though).
  53  *
  54  * @decode_table:       The array in which to create the fast huffman decoding
  55  *                      table.  It must have a length of at least
  56  *                      (2**table_bits) + 2 * num_syms to guarantee
  57  *                      that there is enough space.  Also must be 16-byte
  58  *                      aligned (at least when USE_SSE2_FILL gets defined).
  59  *
  60  * @num_syms:           Number of symbols in the alphabet, including symbols
  61  *                      that do not appear in this particular input chunk.
  62  *
  63  * @table_bits:         Any symbols with a code length of table_bits or less can
  64  *                      be decoded in one lookup of the table.  2**table_bits
  65  *                      must be greater than or equal to @num_syms if there are
  66  *                      any Huffman codes longer than @table_bits.
  67  *
  68  * @lens:               An array of length @num_syms, indexable by symbol, that
  69  *                      gives the length of the Huffman codeword for that
  70  *                      symbol.  Because the Huffman tree is in canonical form,
  71  *                      it can be reconstructed by only knowing the length of
  72  *                      the codeword for each symbol.  It is assumed, but not
  73  *                      checked, that every length is less than
  74  *                      @max_codeword_len.
  75  *
  76  * @max_codeword_len:   The longest codeword length allowed in the compression
  77  *                      format.
  78  *
  79  * Returns 0 on success; returns -1 if the length values do not correspond to a
  80  * valid Huffman tree.
  81  *
  82  * The format of the Huffamn decoding table is as follows.  The first (1 <<
  83  * table_bits) entries of the table are indexed by chunks of the input of size
  84  * @table_bits.  If the next Huffman codeword in the input happens to have a
  85  * length of exactly @table_bits, the symbol is simply read directly from the
  86  * decoding table.  Alternatively, if the next Huffman codeword has length _less
  87  * than_ @table_bits, the symbol is also read directly from the decode table;
  88  * this is possible because every entry in the table that is indexed by an
  89  * integer that has the shorter codeword as a binary prefix is filled in with
  90  * the appropriate symbol.  If a codeword has length n <= table_bits, it will
  91  * have 2**(table_bits - n) possible suffixes, and thus that many entries in the
  92  * decoding table.
  93  *
  94  * It's a bit more complicated if the next Huffman codeword has length of more
  95  * than @table_bits.  The table entry indexed by the first @table_bits of that
  96  * codeword cannot give the appropriate symbol directly, because that entry is
  97  * guaranteed to be referenced by the Huffman codewords of multiple symbols.
  98  * And while the LZX compression format does not allow codes longer than 16
  99  * bits, a table of size (2 ** 16) = 65536 entries would be too slow to create.
 100  *
 101  * There are several different ways to make it possible to look up the symbols
 102  * for codewords longer than @table_bits.  One way is to make the entries for
 103  * the prefixes of length @table_bits of those entries be pointers to additional
 104  * decoding tables that are indexed by some number of additional bits of the
 105  * codeword.  The technique used here is a bit simpler, however: just store the
 106  * needed subtrees of the Huffman tree in the decoding table after the lookup
 107  * entries, beginning at index (2**table_bits).  Real pointers are replaced by
 108  * indices into the decoding table, and symbol entries are distinguished from
 109  * pointers by the fact that values less than @num_syms must be symbol values.
 110  */
 111 int
 112 make_huffman_decode_table(u16 *decode_table,  unsigned num_syms,
 113                           unsigned table_bits, const u8 *lens,
 114                           unsigned max_codeword_len)
 115 {
 116         unsigned len_counts[max_codeword_len + 1];
 117         u16 sorted_syms[num_syms];
 118         unsigned offsets[max_codeword_len + 1];
 119         const unsigned table_num_entries = 1 << table_bits;
 120         int left;
 121         unsigned decode_table_pos;
 122         void *decode_table_ptr;
 123         unsigned sym_idx;
 124         unsigned codeword_len;
 125         unsigned stores_per_loop;
 126
 127 #ifdef USE_LONG_FILL
 128         const unsigned entries_per_long = sizeof(unsigned long) / sizeof(decode_table[0]);
 129 #endif
 130
 131 #ifdef USE_SSE2_FILL
 132         const unsigned entries_per_xmm = sizeof(__m128i) / sizeof(decode_table[0]);
 133 #endif
 134
 135         wimlib_assert2((uintptr_t)decode_table % DECODE_TABLE_ALIGNMENT == 0);
 136
 137         /* accumulate lengths for codes */
 138         for (unsigned i = 0; i <= max_codeword_len; i++)
 139                 len_counts[i] = 0;
 140
 141         for (unsigned sym = 0; sym < num_syms; sym++) {
 142                 wimlib_assert2(lens[sym] <= max_codeword_len);
 143                 len_counts[lens[sym]]++;
 144         }
 145
 146         /* check for an over-subscribed or incomplete set of lengths */
 147         left = 1;
 148         for (unsigned len = 1; len <= max_codeword_len; len++) {
 149                 left <<= 1;
 150                 left -= len_counts[len];
 151                 if (unlikely(left < 0)) { /* over-subscribed */
 152                         DEBUG("Invalid Huffman code (over-subscribed)");
 153                         return -1;
 154                 }
 155         }
 156
 157         if (unlikely(left != 0)) /* incomplete set */{
 158                 if (left == 1 << max_codeword_len) {
 159                         /* Empty code--- okay in XPRESS and LZX */
 160                         memset(decode_table, 0,
 161                                table_num_entries * sizeof(decode_table[0]));
 162                         return 0;
 163                 } else {
 164                         DEBUG("Invalid Huffman code (incomplete set)");
 165                         return -1;
 166                 }
 167         }
 168
 169         /* Generate offsets into symbol table for each length for sorting */
 170         offsets[1] = 0;
 171         for (unsigned len = 1; len < max_codeword_len; len++)
 172                 offsets[len + 1] = offsets[len] + len_counts[len];
 173
 174         /* Sort symbols primarily by length and secondarily by symbol order.
 175          * This is basically a count-sort over the codeword lengths. */
 176         for (unsigned sym = 0; sym < num_syms; sym++)
 177                 if (lens[sym] != 0)
 178                         sorted_syms[offsets[lens[sym]]++] = sym;
 179
 180         /* Fill entries for codewords short enough for a direct mapping.  We can
 181          * take advantage of the ordering of the codewords, since the Huffman
 182          * code is canonical.  It must be the case that all the codewords of
 183          * some length L numerically precede all the codewords of length L + 1.
 184          * Furthermore, if we have 2 symbols A and B with the same codeword
 185          * length but symbol A is sorted before symbol B, then then we know that
 186          * the codeword for A numerically precedes the codeword for B. */
 187         decode_table_ptr = decode_table;
 188         sym_idx = 0;
 189         codeword_len = 1;
 190 #ifdef USE_SSE2_FILL
 191         /* Fill in the Huffman decode table entries one 128-bit vector at a
 192          * time.  This is 8 entries per store. */
 193         stores_per_loop = (1 << (table_bits - codeword_len)) / entries_per_xmm;
 194         for (; stores_per_loop != 0; codeword_len++, stores_per_loop >>= 1) {
 195                 unsigned end_sym_idx = sym_idx + len_counts[codeword_len];
 196                 for (; sym_idx < end_sym_idx; sym_idx++) {
 197                         /* Note: unlike in the 'long' version below, the __m128i
 198                          * type already has __attribute__((may_alias)), so using
 199                          * it to access the decode table, which is an array of
 200                          * unsigned shorts, will not violate strict aliasing. */
 201                         u16 sym;
 202                         __m128i v;
 203                         __m128i *p;
 204                         unsigned n;
 205
 206                         sym = sorted_syms[sym_idx];
 207
 208                         v = _mm_set1_epi16(sym);
 209                         p = (__m128i*)decode_table_ptr;
 210                         n = stores_per_loop;
 211                         do {
 212                                 *p++ = v;
 213                         } while (--n);
 214                         decode_table_ptr = p;
 215                 }
 216         }
 217 #endif /* USE_SSE2_FILL */
 218
 219 #ifdef USE_LONG_FILL
 220         /* Fill in the Huffman decode table entries one 'unsigned long' at a
 221          * time.  On 32-bit systems this is 2 entries per store, while on 64-bit
 222          * systems this is 4 entries per store. */
 223         stores_per_loop = (1 << (table_bits - codeword_len)) / entries_per_long;
 224         for (; stores_per_loop != 0; codeword_len++, stores_per_loop >>= 1) {
 225                 unsigned end_sym_idx = sym_idx + len_counts[codeword_len];
 226                 for (; sym_idx < end_sym_idx; sym_idx++) {
 227
 228                         /* Accessing the array of unsigned shorts as unsigned
 229                          * longs would violate strict aliasing and would require
 230                          * compiling the code with -fno-strict-aliasing to
 231                          * guarantee correctness.  To work around this problem,
 232                          * use the gcc 'may_alias' extension to define a special
 233                          * unsigned long type that may alias any other in-memory
 234                          * variable.  */
 235                         typedef unsigned long __attribute__((may_alias)) aliased_long_t;
 236
 237                         u16 sym;
 238                         aliased_long_t *p;
 239                         aliased_long_t v;
 240                         unsigned n;
 241
 242                         sym = sorted_syms[sym_idx];
 243
 244                         BUILD_BUG_ON(sizeof(aliased_long_t) != 4 &&
 245                                      sizeof(aliased_long_t) != 8);
 246
 247                         v = sym;
 248                         if (sizeof(aliased_long_t) >= 4)
 249                                 v |= v << 16;
 250                         if (sizeof(aliased_long_t) >= 8) {
 251                                 /* This may produce a compiler warning if an
 252                                  * aliased_long_t is 32 bits, but this won't be
 253                                  * executed unless an aliased_long_t is at least
 254                                  * 64 bits anyway. */
 255                                 v |= v << 32;
 256                         }
 257
 258                         p = (aliased_long_t *)decode_table_ptr;
 259                         n = stores_per_loop;
 260
 261                         do {
 262                                 *p++ = v;
 263                         } while (--n);
 264                         decode_table_ptr = p;
 265                 }
 266         }
 267 #endif /* USE_LONG_FILL */
 268
 269         /* Fill in the Huffman decode table entries one 16-bit integer at a
 270          * time. */
 271         stores_per_loop = (1 << (table_bits - codeword_len));
 272         for (; stores_per_loop != 0; codeword_len++, stores_per_loop >>= 1) {
 273                 unsigned end_sym_idx = sym_idx + len_counts[codeword_len];
 274                 for (; sym_idx < end_sym_idx; sym_idx++) {
 275                         u16 sym;
 276                         u16 *p;
 277                         unsigned n;
 278
 279                         sym = sorted_syms[sym_idx];
 280
 281                         p = (u16*)decode_table_ptr;
 282                         n = stores_per_loop;
 283
 284                         do {
 285                                 *p++ = sym;
 286                         } while (--n);
 287
 288                         decode_table_ptr = p;
 289                 }
 290         }
 291
 292         /* If we've filled in the entire table, we are done.  Otherwise, there
 293          * are codes longer than table bits that we need to store in the
 294          * tree-like structure at the end of the table rather than directly in
 295          * the main decode table itself. */
 296
 297         decode_table_pos = (u16*)decode_table_ptr - decode_table;
 298         if (decode_table_pos != table_num_entries) {
 299                 unsigned j;
 300                 unsigned next_free_tree_slot;
 301                 unsigned cur_codeword;
 302
 303                 wimlib_assert2(decode_table_pos < table_num_entries);
 304
 305                 /* Fill in the remaining entries, which correspond to codes
 306                  * longer than @table_bits.
 307                  *
 308                  * First, zero out the rest of the entries.  This is necessary
 309                  * so that the entries appear as "unallocated" in the next part.
 310                  * */
 311                 j = decode_table_pos;
 312                 do {
 313                         decode_table[j] = 0;
 314                 } while (++j != table_num_entries);
 315
 316                 /* Assert that 2**table_bits is at least num_syms.  If this
 317                  * wasn't the case, we wouldn't be able to distinguish pointer
 318                  * entries from symbol entries. */
 319                 wimlib_assert2(table_num_entries >= num_syms);
 320
 321
 322                 /* The tree nodes are allocated starting at decode_table[1 <<
 323                  * table_bits].  Remember that the full size of the table,
 324                  * including the extra space for the tree nodes, is actually
 325                  * 2**table_bits + 2 * num_syms slots, while table_num_entries
 326                  * is only 2**table_bits. */
 327                 next_free_tree_slot = table_num_entries;
 328
 329                 /* The current Huffman codeword  */
 330                 cur_codeword = decode_table_pos << 1;
 331
 332                 /* Go through every codeword of length greater than @table_bits,
 333                  * primarily in order of codeword length and secondarily in
 334                  * order of symbol. */
 335                 wimlib_assert2(codeword_len == table_bits + 1);
 336                 for (; codeword_len <= max_codeword_len; codeword_len++, cur_codeword <<= 1)
 337                 {
 338                         unsigned end_sym_idx = sym_idx + len_counts[codeword_len];
 339                         for (; sym_idx < end_sym_idx; sym_idx++, cur_codeword++) {
 340                                 unsigned sym = sorted_syms[sym_idx];
 341                                 unsigned extra_bits = codeword_len - table_bits;
 342
 343                                 /* index of the current node; find it from the
 344                                  * prefix of the current Huffman codeword. */
 345                                 unsigned node_idx = cur_codeword >> extra_bits;
 346                                 wimlib_assert2(node_idx < table_num_entries);
 347
 348                                 /* Go through each bit of the current Huffman
 349                                  * codeword beyond the prefix of length
 350                                  * @table_bits and walk the tree, allocating any
 351                                  * slots that have not yet been allocated. */
 352                                 do {
 353
 354                                         /* If the current tree node points to
 355                                          * nowhere but we need to follow it,
 356                                          * allocate a new node for it to point
 357                                          * to. */
 358                                         if (decode_table[node_idx] == 0) {
 359                                                 decode_table[node_idx] = next_free_tree_slot;
 360                                                 decode_table[next_free_tree_slot++] = 0;
 361                                                 decode_table[next_free_tree_slot++] = 0;
 362                                                 wimlib_assert2(next_free_tree_slot <=
 363                                                                table_num_entries + 2 * num_syms);
 364                                         }
 365
 366                                         /* Set node_idx to left child */
 367                                         node_idx = decode_table[node_idx];
 368
 369                                         /* Is the next bit 0 or 1? If 0, go left
 370                                          * (already done).  If 1, go right by
 371                                          * incrementing node_idx. */
 372                                         --extra_bits;
 373                                         node_idx += (cur_codeword >> extra_bits) & 1;
 374                                 } while (extra_bits != 0);
 375
 376                                 /* node_idx is now the index of the leaf entry
 377                                  * into which the actual symbol will go. */
 378                                 decode_table[node_idx] = sym;
 379
 380                                 /* Note: cur_codeword is always incremented at
 381                                  * the end of this loop because this is how
 382                                  * canonical Huffman codes are generated (add 1
 383                                  * for each code, then left shift whenever the
 384                                  * code length increases) */
 385                         }
 386                 }
 387         }
 388         return 0;
 389 }
 390
 391 /* Reads a Huffman-encoded symbol from the bistream when the number of remaining
 392  * bits is less than the maximum codeword length. */
 393 int
 394 read_huffsym_near_end_of_input(struct input_bitstream *istream,
 395                                const u16 decode_table[],
 396                                const u8 lens[],
 397                                unsigned num_syms,
 398                                unsigned table_bits,
 399                                unsigned *n)
 400 {
 401         unsigned bitsleft = istream->bitsleft;
 402         unsigned key_size;
 403         u16 sym;
 404         u16 key_bits;
 405
 406         if (table_bits > bitsleft) {
 407                 key_size = bitsleft;
 408                 bitsleft = 0;
 409                 key_bits = bitstream_peek_bits(istream, key_size) <<
 410                                                 (table_bits - key_size);
 411         } else {
 412                 key_size = table_bits;
 413                 bitsleft -= table_bits;
 414                 key_bits = bitstream_peek_bits(istream, table_bits);
 415         }
 416
 417         sym = decode_table[key_bits];
 418         if (sym >= num_syms) {
 419                 bitstream_remove_bits(istream, key_size);
 420                 do {
 421                         if (bitsleft == 0)
 422                                 return -1;
 423                         key_bits = sym + bitstream_peek_bits(istream, 1);
 424                         bitstream_remove_bits(istream, 1);
 425                         bitsleft--;
 426                 } while ((sym = decode_table[key_bits]) >= num_syms);
 427         } else {
 428                 bitstream_remove_bits(istream, lens[sym]);
 429         }
 430         *n = sym;
 431         return 0;
 432 }