X-Git-Url: https://wimlib.net/git/?p=wimlib;a=blobdiff_plain;f=src%2Fdecompress_common.c;h=a490882d8542cd230877f6405ff34988ba98b322;hp=767527d94bec63b53088e145da8ef98c6d17a860;hb=658ee1d652613948b29c412d75b3732801c2a235;hpb=883833a4b3dabec325edf1ca938000f91d587c00 diff --git a/src/decompress_common.c b/src/decompress_common.c index 767527d9..a490882d 100644 --- a/src/decompress_common.c +++ b/src/decompress_common.c @@ -2,25 +2,12 @@ * decompress_common.c * * Code for decompression shared among multiple compression formats. - */ - -/* - * Copyright (C) 2012, 2013 Eric Biggers * - * This file is part of wimlib, a library for working with WIM files. + * Author: Eric Biggers + * Year: 2012 - 2014 * - * wimlib is free software; you can redistribute it and/or modify it under the - * terms of the GNU General Public License as published by the Free - * Software Foundation; either version 3 of the License, or (at your option) - * any later version. - * - * wimlib is distributed in the hope that it will be useful, but WITHOUT ANY - * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR - * A PARTICULAR PURPOSE. See the GNU General Public License for more - * details. - * - * You should have received a copy of the GNU General Public License - * along with wimlib; if not, see http://www.gnu.org/licenses/. + * The author dedicates this file to the public domain. + * You can do whatever you want with this file. */ #ifdef HAVE_CONFIG_H @@ -28,184 +15,242 @@ #endif #include "wimlib/decompress_common.h" -#include "wimlib/error.h" -#include "wimlib/util.h" #include +#define USE_WORD_FILL + #ifdef __GNUC__ # ifdef __SSE2__ +# undef USE_WORD_FILL # define USE_SSE2_FILL # include -# else -# define USE_LONG_FILL # endif #endif +/* Construct a direct mapping entry in the lookup table. */ +#define MAKE_DIRECT_ENTRY(symbol, length) ((symbol) | ((length) << 11)) + /* - * make_huffman_decode_table: - 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; also added some optimizations to - * make filling in the decode table entries faster (may not help significantly - * though). + * make_huffman_decode_table() - + * + * Build a decoding table for a canonical prefix code, or "Huffman code". + * + * This takes as input the length of the codeword for each symbol in the + * alphabet and produces as output a table that can be used for fast + * decoding of prefix-encoded symbols using read_huffsym(). + * + * Strictly speaking, a canonical prefix code might not be a Huffman + * code. But this algorithm will work either way; and in fact, since + * Huffman codes are defined in terms of symbol frequencies, there is no + * way for the decompressor to know whether the code is a true Huffman + * code or not until all symbols have been decoded. + * + * Because the prefix code is assumed to be "canonical", it can be + * reconstructed directly from the codeword lengths. A prefix code is + * canonical if and only if a longer codeword never lexicographically + * precedes a shorter codeword, and the lexicographic ordering of + * codewords of the same length is the same as the lexicographic ordering + * of the corresponding symbols. Consequently, we can sort the symbols + * primarily by codeword length and secondarily by symbol value, then + * reconstruct the prefix code by generating codewords lexicographically + * in that order. * - * @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. Also must be 16-byte - * aligned (at least when USE_SSE2_FILL gets defined). + * This function does not, however, generate the prefix code explicitly. + * Instead, it directly builds a table for decoding symbols using the + * code. The basic idea is this: given the next 'max_codeword_len' bits + * in the input, we can look up the decoded symbol by indexing a table + * containing 2**max_codeword_len entries. A codeword with length + * 'max_codeword_len' will have exactly one entry in this table, whereas + * a codeword shorter than 'max_codeword_len' will have multiple entries + * in this table. Precisely, a codeword of length n will be represented + * by 2**(max_codeword_len - n) entries in this table. The 0-based index + * of each such entry will contain the corresponding codeword as a prefix + * when zero-padded on the left to 'max_codeword_len' binary digits. * - * @num_syms: Number of symbols in the alphabet, including symbols - * that do not appear in this particular input chunk. + * That's the basic idea, but we implement two optimizations regarding + * the format of the decode table itself: * - * @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. + * - For many compression formats, the maximum codeword length is too + * long for it to be efficient to build the full decoding table + * whenever a new prefix code is used. Instead, we can build the table + * using only 2**table_bits entries, where 'table_bits' is some number + * less than or equal to 'max_codeword_len'. Then, only codewords of + * length 'table_bits' and shorter can be directly looked up. For + * longer codewords, the direct lookup instead produces the root of a + * binary tree. Using this tree, the decoder can do traditional + * bit-by-bit decoding of the remainder of the codeword. Child nodes + * are allocated in extra entries at the end of the table; leaf nodes + * contain symbols. Note that the long-codeword case is, in general, + * not performance critical, since in Huffman codes the most frequently + * used symbols are assigned the shortest codeword lengths. * - * @lens: An array of length @num_syms, indexable by symbol, that - * gives the length of the Huffman codeword 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. + * - When we decode a symbol using a direct lookup of the table, we still + * need to know its length so that the bitstream can be advanced by the + * appropriate number of bits. The simple solution is to simply retain + * the 'lens' array and use the decoded symbol as an index into it. + * However, this requires two separate array accesses in the fast path. + * The optimization is to store the length directly in the decode + * table. We use the bottom 11 bits for the symbol and the top 5 bits + * for the length. In addition, to combine this optimization with the + * previous one, we introduce a special case where the top 2 bits of + * the length are both set if the entry is actually the root of a + * binary tree. * - * @max_codeword_len: The longest codeword length allowed in the compression - * format. + * @decode_table: + * The array in which to create the decoding table. This must be + * 16-byte aligned and must have a length of at least + * ((2**table_bits) + 2 * num_syms) entries. This is permitted to + * alias @lens, since all information from @lens is consumed before +* anything is written to @decode_table. * - * Returns 0 on success; returns -1 if the length values do not correspond to a - * valid Huffman tree. + * @num_syms: + * The number of symbols in the alphabet; also, the length of the + * 'lens' array. Must be less than or equal to + * DECODE_TABLE_MAX_SYMBOLS. * - * 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. + * @table_bits: + * The order of the decode table size, as explained above. Must be + * less than or equal to DECODE_TABLE_MAX_TABLE_BITS. * - * 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. + * @lens: + * An array of length @num_syms, indexable by symbol, that gives the + * length of the codeword, in bits, for that symbol. The length can + * be 0, which means that the symbol does not have a codeword + * assigned. This is permitted to alias @decode_table, since all + * information from @lens is consumed before anything is written to + * @decode_table. * - * 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. + * @max_codeword_len: + * The longest codeword length allowed in the compression format. + * All entries in 'lens' must be less than or equal to this value. + * This must be less than or equal to DECODE_TABLE_MAX_CODEWORD_LEN. + * + * Returns 0 on success, or -1 if the lengths do not form a valid prefix + * code. */ int -make_huffman_decode_table(u16 *decode_table, unsigned num_syms, - unsigned table_bits, const u8 *lens, - unsigned max_codeword_len) +make_huffman_decode_table(u16 decode_table[const], + const unsigned num_syms, + const unsigned table_bits, + const u8 lens[const], + const unsigned max_codeword_len) { + const unsigned table_num_entries = 1 << table_bits; 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; int left; - unsigned decode_table_pos; void *decode_table_ptr; unsigned sym_idx; unsigned codeword_len; unsigned stores_per_loop; + unsigned decode_table_pos; -#ifdef USE_LONG_FILL - const unsigned entries_per_long = sizeof(unsigned long) / sizeof(decode_table[0]); +#ifdef USE_WORD_FILL + const unsigned entries_per_word = WORDSIZE / sizeof(decode_table[0]); #endif #ifdef USE_SSE2_FILL const unsigned entries_per_xmm = sizeof(__m128i) / sizeof(decode_table[0]); #endif - wimlib_assert2((uintptr_t)decode_table % DECODE_TABLE_ALIGNMENT == 0); - - /* accumulate lengths for codes */ - for (unsigned i = 0; i <= max_codeword_len; i++) - len_counts[i] = 0; - - for (unsigned sym = 0; sym < num_syms; sym++) { - wimlib_assert2(lens[sym] <= max_codeword_len); + /* Count how many symbols have each possible codeword length. + * Note that a length of 0 indicates the corresponding symbol is not + * used in the code and therefore does not have a codeword. */ + for (unsigned len = 0; len <= max_codeword_len; len++) + len_counts[len] = 0; + for (unsigned sym = 0; sym < num_syms; sym++) len_counts[lens[sym]]++; - } - /* check for an over-subscribed or incomplete set of lengths */ + /* We can assume all lengths are <= max_codeword_len, but we + * cannot assume they form a valid prefix code. A codeword of + * length n should require a proportion of the codespace equaling + * (1/2)^n. The code is valid if and only if the codespace is + * exactly filled by the lengths, by this measure. */ left = 1; for (unsigned len = 1; len <= max_codeword_len; len++) { left <<= 1; left -= len_counts[len]; - if (unlikely(left < 0)) { /* over-subscribed */ - DEBUG("Invalid Huffman code (over-subscribed)"); + if (unlikely(left < 0)) { + /* The lengths overflow the codespace; that is, the code + * is over-subscribed. */ return -1; } } - if (unlikely(left != 0)) /* incomplete set */{ - if (left == 1 << max_codeword_len) { - /* Empty code--- okay in XPRESS and LZX */ + if (unlikely(left != 0)) { + /* The lengths do not fill the codespace; that is, they form an + * incomplete set. */ + if (left == (1 << max_codeword_len)) { + /* The code is completely empty. This is arguably + * invalid, but in fact it is valid in LZX and XPRESS, + * so we must allow it. By definition, no symbols can + * be decoded with an empty code. Consequently, we + * technically don't even need to fill in the decode + * table. However, to avoid accessing uninitialized + * memory if the algorithm nevertheless attempts to + * decode symbols using such a code, we zero out the + * decode table. */ memset(decode_table, 0, table_num_entries * sizeof(decode_table[0])); return 0; - } else { - DEBUG("Invalid Huffman code (incomplete set)"); - return -1; } + 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 the symbols primarily by length and secondarily by symbol order. + */ + { + unsigned offsets[max_codeword_len + 1]; + + /* Initialize 'offsets' so that offsets[len] for 1 <= len <= + * max_codeword_len is the number of codewords shorter than + * 'len' bits. */ + offsets[1] = 0; + for (unsigned len = 1; len < max_codeword_len; len++) + offsets[len + 1] = offsets[len] + len_counts[len]; + + /* Use the 'offsets' array to sort the symbols. + * Note that we do not include symbols that are not used in the + * code. Consequently, fewer than 'num_syms' entries in + * 'sorted_syms' may be filled. */ + for (unsigned sym = 0; sym < num_syms; sym++) + if (lens[sym] != 0) + sorted_syms[offsets[lens[sym]]++] = sym; + } - /* Sort symbols primarily by length and secondarily by symbol order. - * This is basically a count-sort over the codeword lengths. */ - for (unsigned sym = 0; sym < num_syms; sym++) - if (lens[sym] != 0) - sorted_syms[offsets[lens[sym]]++] = sym; - - /* 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. */ + /* Fill entries for codewords with length <= table_bits + * --- that is, those short enough for a direct mapping. + * + * The table will start with entries for the shortest codeword(s), which + * have the most entries. From there, the number of entries per + * codeword will decrease. As an optimization, we may begin filling + * entries with SSE2 vector accesses (8 entries/store), then change to + * 'machine_word_t' accesses (2 or 4 entries/store), then change to + * 16-bit accesses (1 entry/store). */ decode_table_ptr = decode_table; sym_idx = 0; codeword_len = 1; #ifdef USE_SSE2_FILL - /* Fill in the Huffman decode table entries one 128-bit vector at a - * time. This is 8 entries per store. */ + /* Fill the entries one 128-bit vector at a time. + * This is 8 entries per store. */ stores_per_loop = (1 << (table_bits - codeword_len)) / entries_per_xmm; for (; stores_per_loop != 0; codeword_len++, stores_per_loop >>= 1) { unsigned end_sym_idx = sym_idx + len_counts[codeword_len]; for (; sym_idx < end_sym_idx; sym_idx++) { - /* Note: unlike in the 'long' version below, the __m128i - * type already has __attribute__((may_alias)), so using - * it to access the decode table, which is an array of - * unsigned shorts, will not violate strict aliasing. */ - u16 sym; + /* Note: unlike in the machine_word_t version below, the + * __m128i type already has __attribute__((may_alias)), + * so using it to access the decode table, which is an + * array of unsigned shorts, will not violate strict + * aliasing. */ + u16 entry; __m128i v; __m128i *p; unsigned n; - sym = sorted_syms[sym_idx]; + entry = MAKE_DIRECT_ENTRY(sorted_syms[sym_idx], codeword_len); - v = _mm_set1_epi16(sym); + v = _mm_set1_epi16(entry); p = (__m128i*)decode_table_ptr; n = stores_per_loop; do { @@ -216,46 +261,33 @@ make_huffman_decode_table(u16 *decode_table, unsigned num_syms, } #endif /* USE_SSE2_FILL */ -#ifdef USE_LONG_FILL - /* Fill in the Huffman decode table entries one 'unsigned long' at a - * time. On 32-bit systems this is 2 entries per store, while on 64-bit - * systems this is 4 entries per store. */ - stores_per_loop = (1 << (table_bits - codeword_len)) / entries_per_long; +#ifdef USE_WORD_FILL + /* Fill the entries one machine word at a time. + * On 32-bit systems this is 2 entries per store, while on 64-bit + * systems this is 4 entries per store. */ + stores_per_loop = (1 << (table_bits - codeword_len)) / entries_per_word; for (; stores_per_loop != 0; codeword_len++, stores_per_loop >>= 1) { unsigned end_sym_idx = sym_idx + len_counts[codeword_len]; for (; sym_idx < end_sym_idx; sym_idx++) { - /* Accessing the array of unsigned shorts as unsigned - * longs would violate strict aliasing and would require - * compiling the code with -fno-strict-aliasing to - * guarantee correctness. To work around this problem, - * use the gcc 'may_alias' extension to define a special - * unsigned long type that may alias any other in-memory - * variable. */ - typedef unsigned long __attribute__((may_alias)) aliased_long_t; - - u16 sym; - aliased_long_t *p; - aliased_long_t v; - unsigned n; + /* Accessing the array of u16 as u32 or u64 would + * violate strict aliasing and would require compiling + * the code with -fno-strict-aliasing to guarantee + * correctness. To work around this problem, use the + * gcc 'may_alias' extension. */ + typedef machine_word_t _may_alias_attribute aliased_word_t; - sym = sorted_syms[sym_idx]; + machine_word_t v; + aliased_word_t *p; + unsigned n; - BUILD_BUG_ON(sizeof(aliased_long_t) != 4 && - sizeof(aliased_long_t) != 8); + STATIC_ASSERT(WORDSIZE == 4 || WORDSIZE == 8); - v = sym; - if (sizeof(aliased_long_t) >= 4) - v |= v << 16; - if (sizeof(aliased_long_t) >= 8) { - /* This may produce a compiler warning if an - * aliased_long_t is 32 bits, but this won't be - * executed unless an aliased_long_t is at least - * 64 bits anyway. */ - v |= v << 32; - } + v = MAKE_DIRECT_ENTRY(sorted_syms[sym_idx], codeword_len); + v |= v << 16; + v |= v << (WORDSIZE == 8 ? 32 : 0); - p = (aliased_long_t *)decode_table_ptr; + p = (aliased_word_t *)decode_table_ptr; n = stores_per_loop; do { @@ -264,35 +296,33 @@ make_huffman_decode_table(u16 *decode_table, unsigned num_syms, decode_table_ptr = p; } } -#endif /* USE_LONG_FILL */ +#endif /* USE_WORD_FILL */ - /* Fill in the Huffman decode table entries one 16-bit integer at a - * time. */ + /* Fill the entries one 16-bit integer at a time. */ stores_per_loop = (1 << (table_bits - codeword_len)); for (; stores_per_loop != 0; codeword_len++, stores_per_loop >>= 1) { unsigned end_sym_idx = sym_idx + len_counts[codeword_len]; for (; sym_idx < end_sym_idx; sym_idx++) { - u16 sym; + u16 entry; u16 *p; unsigned n; - sym = sorted_syms[sym_idx]; + entry = MAKE_DIRECT_ENTRY(sorted_syms[sym_idx], codeword_len); p = (u16*)decode_table_ptr; n = stores_per_loop; do { - *p++ = sym; + *p++ = entry; } while (--n); decode_table_ptr = p; } } - /* If we've filled in the entire table, we are done. Otherwise, there - * are codes longer than table bits that we need to store in the - * tree-like structure at the end of the table rather than directly in - * the main decode table itself. */ + /* If we've filled in the entire table, we are done. Otherwise, + * there are codewords longer than table_bits for which we must + * generate binary trees. */ decode_table_pos = (u16*)decode_table_ptr - decode_table; if (decode_table_pos != table_num_entries) { @@ -300,133 +330,85 @@ make_huffman_decode_table(u16 *decode_table, unsigned num_syms, unsigned next_free_tree_slot; unsigned cur_codeword; - wimlib_assert2(decode_table_pos < table_num_entries); - - /* 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. - * */ + /* First, zero out the remaining entries. This is + * necessary so that these entries appear as + * "unallocated" in the next part. Each of these entries + * will eventually be filled with the representation of + * the root node of a binary tree. */ j = decode_table_pos; do { decode_table[j] = 0; } while (++j != table_num_entries); - /* 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 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. */ + /* We allocate child nodes starting at the end of the + * direct lookup table. Note that there should be + * 2*num_syms extra entries for this purpose, although + * fewer than this may actually be needed. */ next_free_tree_slot = table_num_entries; - /* The current Huffman codeword */ - cur_codeword = decode_table_pos << 1; - - /* Go through every codeword of length greater than @table_bits, - * primarily in order of codeword length and secondarily in - * order of symbol. */ - wimlib_assert2(codeword_len == table_bits + 1); - for (; codeword_len <= max_codeword_len; codeword_len++, cur_codeword <<= 1) + /* Iterate through each codeword with length greater than + * 'table_bits', primarily in order of codeword length + * and secondarily in order of symbol. */ + for (cur_codeword = decode_table_pos << 1; + codeword_len <= max_codeword_len; + codeword_len++, cur_codeword <<= 1) { unsigned end_sym_idx = sym_idx + len_counts[codeword_len]; - for (; sym_idx < end_sym_idx; sym_idx++, cur_codeword++) { + for (; sym_idx < end_sym_idx; sym_idx++, cur_codeword++) + { + /* 'sym' is the symbol represented by the + * codeword. */ unsigned sym = sorted_syms[sym_idx]; + unsigned extra_bits = codeword_len - table_bits; - /* 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. */ + /* Go through each bit of the current codeword + * beyond the prefix of length @table_bits and + * walk the appropriate binary tree, allocating + * any slots that have not yet been allocated. + * + * Note that the 'pointer' entry to the binary + * tree, which is stored in the direct lookup + * portion of the table, is represented + * identically to other internal (non-leaf) + * nodes of the binary tree; it can be thought + * of as simply the root of the tree. The + * representation of these internal nodes is + * simply the index of the left child combined + * with the special bits 0xC000 to distingush + * the entry from direct mapping and leaf node + * entries. */ do { - /* If the current tree node points to - * nowhere but we need to follow it, - * allocate a new node for it to point - * to. */ + /* At least one bit remains in the + * codeword, but the current node is an + * unallocated leaf. Change it to an + * internal node. */ if (decode_table[node_idx] == 0) { - decode_table[node_idx] = next_free_tree_slot; + decode_table[node_idx] = + next_free_tree_slot | 0xC000; 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. */ + /* Go to the left child if the next bit + * in the codeword is 0; otherwise go to + * the right child. */ + node_idx = decode_table[node_idx] & 0x3FFF; --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. */ + /* We've traversed the tree using the entire + * codeword, and we're now at the entry where + * the actual symbol will be stored. This is + * distinguished from internal nodes by not + * having its high two bits set. */ decode_table[node_idx] = sym; - - /* Note: cur_codeword is always incremented at - * the end of this loop because this is how - * canonical Huffman codes are generated (add 1 - * for each code, then left shift whenever the - * code length increases) */ } } } return 0; } - -/* Reads a Huffman-encoded symbol from the bistream when the number of remaining - * bits is less than the maximum codeword length. */ -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) -{ - 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); - } - - sym = decode_table[key_bits]; - if (sym >= num_syms) { - bitstream_remove_bits(istream, key_size); - do { - if (bitsleft == 0) - 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]); - } - *n = sym; - return 0; -}