X-Git-Url: https://wimlib.net/git/?p=wimlib;a=blobdiff_plain;f=src%2Fdecompress.c;h=c9965a0ffeaf22aad2a8f373272c7b03e5b2d371;hp=6d4b41e2285512d33ad21e8a360a0d61931ca198;hb=30826518fab5bb66fec87355324a2f0474fc66c1;hpb=1ab60207e56968e480be6400c67844017598b7dd diff --git a/src/decompress.c b/src/decompress.c index 6d4b41e2..c9965a0f 100644 --- a/src/decompress.c +++ b/src/decompress.c @@ -1,11 +1,12 @@ /* * decompress.c * - * Functions used for decompression. + * Generic functions for decompression, wrapping around actual decompression + * implementations. */ /* - * Copyright (C) 2012 Eric Biggers + * Copyright (C) 2013 Eric Biggers * * This file is part of wimlib, a library for working with WIM files. * @@ -23,306 +24,122 @@ * along with wimlib; if not, see http://www.gnu.org/licenses/. */ -#include "decompress.h" -#include +#ifdef HAVE_CONFIG_H +# include "config.h" +#endif -/* - * Builds a fast huffman decoding table from an array that gives the length of - * the codeword for each symbol in the alphabet. Originally based on code - * written by David Tritscher (taken the original LZX decompression code); also - * heavily modified to add some optimizations used in the zlib code, as well as - * more comments. - * - * @decode_table: The array in which to create the fast huffman decoding - * table. It must have a length of at least - * (2**table_bits) + 2 * num_syms to guarantee - * that there is enough space. - * - * @num_syms: Total number of symbols in the Huffman tree. - * - * @table_bits: Any symbols with a code length of table_bits or less can - * be decoded in one lookup of the table. 2**table_bits - * must be greater than or equal to @num_syms if there are - * any Huffman codes longer than @table_bits. - * - * @lens: An array of length @num_syms, indexable by symbol, that - * gives the length of the Huffman codeward for that - * symbol. Because the Huffman tree is in canonical form, - * it can be reconstructed by only knowing the length of - * the codeword for each symbol. It is assumed, but not - * checked, that every length is less than - * @max_codeword_len. - * - * @max_codeword_len: The longest codeword length allowed in the compression - * format. - * - * Returns 0 on success; returns -1 if the length values do not correspond to a - * valid Huffman tree. - * - * The format of the Huffamn decoding table is as follows. The first (1 << - * table_bits) entries of the table are indexed by chunks of the input of size - * @table_bits. If the next Huffman codeword in the input happens to have a - * length of exactly @table_bits, the symbol is simply read directly from the - * decoding table. Alternatively, if the next Huffman codeword has length _less - * than_ @table_bits, the symbol is also read directly from the decode table; - * this is possible because every entry in the table that is indexed by an - * integer that has the shorter codeword as a binary prefix is filled in with - * the appropriate symbol. If a codeword has length n <= table_bits, it will - * have 2**(table_bits - n) possible suffixes, and thus that many entries in the - * decoding table. - * - * It's a bit more complicated if the next Huffman codeword has length of more - * than @table_bits. The table entry indexed by the first @table_bits of that - * codeword cannot give the appropriate symbol directly, because that entry is - * guaranteed to be referenced by the Huffman codewords of multiple symbols. - * And while the LZX compression format does not allow codes longer than 16 - * bits, a table of size (2 ** 16) = 65536 entries would be too slow to create. - * - * There are several different ways to make it possible to look up the symbols - * for codewords longer than @table_bits. One way is to make the entries for - * the prefixes of length @table_bits of those entries be pointers to additional - * decoding tables that are indexed by some number of additional bits of the - * codeword. The technique used here is a bit simpler, however: just store the - * needed subtrees of the Huffman tree in the decoding table after the lookup - * entries, beginning at index (2**table_bits). Real pointers are replaced by - * indices into the decoding table, and symbol entries are distinguished from - * pointers by the fact that values less than @num_syms must be symbol values. - */ -int make_huffman_decode_table(u16 decode_table[], unsigned num_syms, - unsigned table_bits, const u8 lens[], - unsigned max_codeword_len) -{ - unsigned len_counts[max_codeword_len + 1]; - u16 sorted_syms[num_syms]; - unsigned offsets[max_codeword_len + 1]; - const unsigned table_num_entries = 1 << table_bits; +#include "wimlib.h" +#include "wimlib/decompressor_ops.h" +#include "wimlib/util.h" - /* accumulate lengths for codes */ - for (unsigned i = 0; i <= max_codeword_len; i++) - len_counts[i] = 0; +struct wimlib_decompressor { + const struct decompressor_ops *ops; + void *private; +}; - for (unsigned sym = 0; sym < num_syms; sym++) { - wimlib_assert2(lens[sym] <= max_codeword_len); - len_counts[lens[sym]]++; - } +static const struct decompressor_ops *decompressor_ops[] = { + [WIMLIB_COMPRESSION_TYPE_XPRESS] = &xpress_decompressor_ops, + [WIMLIB_COMPRESSION_TYPE_LZX] = &lzx_decompressor_ops, + [WIMLIB_COMPRESSION_TYPE_LZMS] = &lzms_decompressor_ops, +}; - /* check for an over-subscribed or incomplete set of lengths */ - int left = 1; - for (unsigned len = 1; len <= max_codeword_len; len++) { - left <<= 1; - left -= len_counts[len]; - if (left < 0) { /* over-subscribed */ - ERROR("Invalid Huffman code (over-subscribed)"); - return -1; - } - } - if (left != 0) /* incomplete set */{ - if (left == 1 << max_codeword_len) { - /* Empty code--- okay in XPRESS and LZX */ - memset(decode_table, 0, - table_num_entries * sizeof(decode_table[0])); - return 0; - } else { - ERROR("Invalid Huffman code (incomplete set)"); - return -1; - } - } - - /* Generate offsets into symbol table for each length for sorting */ - offsets[1] = 0; - for (unsigned len = 1; len < max_codeword_len; len++) - offsets[len + 1] = offsets[len] + len_counts[len]; - - /* Sort symbols primarily by length and secondarily by symbol order. - * This is basically a count-sort over the codeword lengths. - * In the process, calculate the number of symbols that have nonzero - * length and are therefore used in the symbol stream. */ - unsigned num_used_syms = 0; - for (unsigned sym = 0; sym < num_syms; sym++) { - if (lens[sym] != 0) { - sorted_syms[offsets[lens[sym]]++] = sym; - num_used_syms++; - } - } - - /* Fill entries for codewords short enough for a direct mapping. We can - * take advantage of the ordering of the codewords, since the Huffman - * code is canonical. It must be the case that all the codewords of - * some length L numerically precede all the codewords of length L + 1. - * Furthermore, if we have 2 symbols A and B with the same codeword - * length but symbol A is sorted before symbol B, then then we know that - * the codeword for A numerically precedes the codeword for B. */ - unsigned decode_table_pos = 0; - unsigned i = 0; +static struct wimlib_decompressor_params_header * +decompressor_default_params[ARRAY_LEN(decompressor_ops)] = { +}; - wimlib_assert2(num_used_syms != 0); - while (1) { - unsigned sym = sorted_syms[i]; - unsigned codeword_len = lens[sym]; - if (codeword_len > table_bits) - break; +static bool +decompressor_ctype_valid(int ctype) +{ + return (ctype >= 0 && + ctype < ARRAY_LEN(decompressor_ops) && + decompressor_ops[ctype] != NULL); +} - unsigned num_entries = 1 << (table_bits - codeword_len); - if (num_entries >= - (sizeof(unsigned long) / sizeof(decode_table[0]))) - { - wimlib_assert2(decode_table_pos % 4 == 0); - BUILD_BUG_ON(sizeof(unsigned long) != 4 && - sizeof(unsigned long) != 8); +WIMLIBAPI int +wimlib_set_default_decompressor_params(enum wimlib_compression_type ctype, + const struct wimlib_decompressor_params_header *params) +{ + struct wimlib_decompressor_params_header *dup; - unsigned long *p = (unsigned long *)&decode_table[decode_table_pos]; - unsigned long n = num_entries / - (sizeof(unsigned long) / - sizeof(decode_table[0])); - unsigned long v = sym; - if (sizeof(unsigned long) >= 4) - v |= v << 16; - if (sizeof(unsigned long) >= 8) - v |= v << 32; - do { - *p++ = v; - } while (--n); + if (!decompressor_ctype_valid(ctype)) + return WIMLIB_ERR_INVALID_COMPRESSION_TYPE; - decode_table_pos += num_entries; - } else { - do { - decode_table[decode_table_pos++] = sym; - } while (--num_entries); - } - wimlib_assert2(decode_table_pos <= table_num_entries); - if (++i == num_used_syms) { - wimlib_assert2(decode_table_pos == table_num_entries); - /* No codewords were longer than @table_bits, so the - * table is now entirely filled with the codewords. */ - return 0; - } + dup = NULL; + if (params) { + dup = memdup(params, params->size); + if (dup == NULL) + return WIMLIB_ERR_NOMEM; } - wimlib_assert2(i < num_used_syms); - wimlib_assert2(decode_table_pos < table_num_entries); + FREE(decompressor_default_params[ctype]); + decompressor_default_params[ctype] = dup; + return 0; +} - /* Fill in the remaining entries, which correspond to codes longer than - * @table_bits. - * - * First, zero out the rest of the entries. This is necessary so that - * the entries appear as "unallocated" in the next part. */ - { - unsigned j = decode_table_pos; - do { - decode_table[j] = 0; - } while (++j != table_num_entries); +void +cleanup_decompressor_params(void) +{ + for (size_t i = 0; i < ARRAY_LEN(decompressor_default_params); i++) { + FREE(decompressor_default_params[i]); + decompressor_default_params[i] = NULL; } +} - /* Assert that 2**table_bits is at least num_syms. If this wasn't the - * case, we wouldn't be able to distinguish pointer entries from symbol - * entries. */ - wimlib_assert2(table_num_entries >= num_syms); - - /* The current Huffman codeword */ - unsigned cur_codeword = decode_table_pos; - - /* The tree nodes are allocated starting at decode_table[1 << - * table_bits]. Remember that the full size of the table, including the - * extra space for the tree nodes, is actually 2**table_bits + 2 * - * num_syms slots, while table_num_entries is only 2**table_Bits. */ - unsigned next_free_tree_slot = table_num_entries; - - /* Go through every codeword of length greater than @table_bits, - * primarily in order of codeword length and secondarily in order of - * symbol. */ - unsigned prev_codeword_len = table_bits; - do { - unsigned sym = sorted_syms[i]; - unsigned codeword_len = lens[sym]; - unsigned extra_bits = codeword_len - table_bits; - unsigned extra_mask; - - cur_codeword <<= (codeword_len - prev_codeword_len); - prev_codeword_len = codeword_len; - - /* index of the current node; find it from the prefix of the - * current Huffman codeword. */ - unsigned node_idx = cur_codeword >> extra_bits; - wimlib_assert2(node_idx < table_num_entries); - - /* Go through each bit of the current Huffman codeword beyond - * the prefix of length @table_bits and walk the tree, - * allocating any slots that have not yet been allocated. */ - do { - - /* If the current tree node points to nowhere - * but we need to follow it, allocate a new node - * for it to point to. */ - if (decode_table[node_idx] == 0) { - decode_table[node_idx] = next_free_tree_slot; - decode_table[next_free_tree_slot++] = 0; - decode_table[next_free_tree_slot++] = 0; - wimlib_assert2(next_free_tree_slot <= - table_num_entries + 2 * num_syms); - } - - /* Set node_idx to left child */ - node_idx = decode_table[node_idx]; - - /* Is the next bit 0 or 1? If 0, go left (already done). - * If 1, go right by incrementing node_idx. */ - --extra_bits; - node_idx += (cur_codeword >> extra_bits) & 1; - } while (extra_bits != 0); - - /* node_idx is now the index of the leaf entry into which the - * actual symbol will go. */ - decode_table[node_idx] = sym; - - /* cur_codeword is always incremented because this is - * how canonical Huffman codes are generated (add 1 for - * each code, then left shift whenever the code length - * increases) */ - cur_codeword++; - } while (++i != num_used_syms); +WIMLIBAPI int +wimlib_create_decompressor(enum wimlib_compression_type ctype, + size_t max_block_size, + const struct wimlib_decompressor_params_header *extra_params, + struct wimlib_decompressor **dec_ret) +{ + struct wimlib_decompressor *dec; + + if (dec_ret == NULL) + return WIMLIB_ERR_INVALID_PARAM; + + if (!decompressor_ctype_valid(ctype)) + return WIMLIB_ERR_INVALID_COMPRESSION_TYPE; + + dec = MALLOC(sizeof(*dec)); + if (dec == NULL) + return WIMLIB_ERR_NOMEM; + dec->ops = decompressor_ops[ctype]; + dec->private = NULL; + if (dec->ops->create_decompressor) { + const struct wimlib_decompressor_params_header *params; + int ret; + + if (extra_params) + params = extra_params; + else + params = decompressor_default_params[ctype]; + ret = dec->ops->create_decompressor(max_block_size, + params, + &dec->private); + if (ret) { + FREE(dec); + return ret; + } + } + *dec_ret = dec; return 0; } -/* Reads a Huffman-encoded symbol when it is known there are less than - * MAX_CODE_LEN bits remaining in the bitstream. */ -int read_huffsym_near_end_of_input(struct input_bitstream *istream, - const u16 decode_table[], - const u8 lens[], - unsigned num_syms, - unsigned table_bits, - unsigned *n) +WIMLIBAPI int +wimlib_decompress(const void *compressed_data, size_t compressed_size, + void *uncompressed_data, size_t uncompressed_size, + struct wimlib_decompressor *dec) { - unsigned bitsleft = istream->bitsleft; - unsigned key_size; - u16 sym; - u16 key_bits; - - if (table_bits > bitsleft) { - key_size = bitsleft; - bitsleft = 0; - key_bits = bitstream_peek_bits(istream, key_size) << - (table_bits - key_size); - } else { - key_size = table_bits; - bitsleft -= table_bits; - key_bits = bitstream_peek_bits(istream, table_bits); - } + return dec->ops->decompress(compressed_data, compressed_size, + uncompressed_data, uncompressed_size, + dec->private); +} - sym = decode_table[key_bits]; - if (sym >= num_syms) { - bitstream_remove_bits(istream, key_size); - do { - if (bitsleft == 0) { - ERROR("Input stream exhausted"); - return -1; - } - key_bits = sym + bitstream_peek_bits(istream, 1); - bitstream_remove_bits(istream, 1); - bitsleft--; - } while ((sym = decode_table[key_bits]) >= num_syms); - } else { - bitstream_remove_bits(istream, lens[sym]); +WIMLIBAPI void +wimlib_free_decompressor(struct wimlib_decompressor *dec) +{ + if (dec) { + if (dec->ops->free_decompressor) + dec->ops->free_decompressor(dec->private); + FREE(dec); } - *n = sym; - return 0; }