X-Git-Url: https://wimlib.net/git/?a=blobdiff_plain;f=src%2Fdecompress_common.c;h=3b49274886fed539e3614982f546927101fd0db8;hb=3a803d0087d51ea3caa80378bbae615fa45537c5;hp=767527d94bec63b53088e145da8ef98c6d17a860;hpb=883833a4b3dabec325edf1ca938000f91d587c00;p=wimlib diff --git a/src/decompress_common.c b/src/decompress_common.c index 767527d9..3b492748 100644 --- a/src/decompress_common.c +++ b/src/decompress_common.c @@ -2,431 +2,334 @@ * 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. + * The following copying information applies to this specific source code file: * - * 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. + * Written in 2012-2016 by Eric Biggers * - * 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. + * To the extent possible under law, the author(s) have dedicated all copyright + * and related and neighboring rights to this software to the public domain + * worldwide via the Creative Commons Zero 1.0 Universal Public Domain + * Dedication (the "CC0"). * - * You should have received a copy of the GNU General Public License - * along with wimlib; if not, see http://www.gnu.org/licenses/. + * This software 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 CC0 for more details. + * + * You should have received a copy of the CC0 along with this software; if not + * see . */ #ifdef HAVE_CONFIG_H # include "config.h" #endif -#include "wimlib/decompress_common.h" -#include "wimlib/error.h" -#include "wimlib/util.h" - #include -#ifdef __GNUC__ -# ifdef __SSE2__ -# define USE_SSE2_FILL -# include -# else -# define USE_LONG_FILL -# endif +#ifdef __SSE2__ +# include #endif +#include "wimlib/decompress_common.h" + /* - * 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() - * - * @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). + * Given an alphabet of symbols and the length of each symbol's codeword in a + * canonical prefix code, build a table for quickly decoding symbols that were + * encoded with that code. * - * @num_syms: Number of symbols in the alphabet, including symbols - * that do not appear in this particular input chunk. + * A _prefix code_ is an assignment of bitstrings called _codewords_ to symbols + * such that no whole codeword is a prefix of any other. A prefix code might be + * a _Huffman code_, which means that it is an optimum prefix code for a given + * list of symbol frequencies and was generated by the Huffman algorithm. + * Although the prefix codes processed here will ordinarily be "Huffman codes", + * strictly speaking the decoder cannot know whether a given code was actually + * generated by the Huffman algorithm or not. * - * @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. + * 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 equal length is the same as the lexicographic ordering of the + * corresponding symbols. The advantage of using a canonical prefix code is + * that the codewords can be reconstructed from only the symbol => codeword + * length mapping. This eliminates the need to transmit the codewords + * explicitly. Instead, they can be enumerated in lexicographic order after + * sorting the symbols primarily by increasing codeword length and secondarily + * by increasing symbol value. * - * @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. + * However, the decoder's real goal is to decode symbols with the code, not just + * generate the list of codewords. Consequently, this function directly builds + * a table for efficiently decoding symbols using the code. The basic idea is + * that given the next 'max_codeword_len' bits of input, the decoder can look up + * the next 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 have '2^(max_codeword_len - n)' entries. The index of each such entry, + * considered as a bitstring of length 'max_codeword_len', will contain the + * corresponding codeword as a prefix. * - * @max_codeword_len: The longest codeword length allowed in the compression - * format. + * That's the basic idea, but we extend it in two ways: * - * Returns 0 on success; returns -1 if the length values do not correspond to a - * valid Huffman tree. + * - Often the maximum codeword length is too long for it to be efficient to + * build the full decode table whenever a new code is used. Instead, we build + * a "root" table using only '2^table_bits' entries, where 'table_bits <= + * max_codeword_len'. Then, a lookup of 'table_bits' bits produces either a + * symbol directly (for codewords not longer than 'table_bits'), or the index + * of a subtable which must be indexed with additional bits of input to fully + * decode the symbol (for codewords longer than 'table_bits'). * - * 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. + * - Whenever the decoder decodes a symbol, it needs to know the codeword length + * so that it can remove the appropriate number of input bits. The obvious + * solution would be to simply retain the codeword lengths array and use the + * decoded symbol as an index into it. However, that would require two array + * accesses when decoding each symbol. Our strategy is to instead store the + * codeword length directly in the decode table entry along with the symbol. * - * 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. + * See MAKE_DECODE_TABLE_ENTRY() for full details on the format of decode table + * entries, and see read_huffsym() for full details on how symbols are decoded. * - * 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. + * @decode_table: + * The array in which to build the decode table. This must have been + * declared by the DECODE_TABLE() macro. This may alias @lens, since all + * @lens are consumed before the decode table is written to. + * + * @num_syms: + * The number of symbols in the alphabet. + * + * @table_bits: + * The log base 2 of the number of entries in the root table. + * + * @lens: + * An array of length @num_syms, indexed by symbol, that gives the length + * of the codeword, in bits, for each symbol. The length can be 0, which + * means that the symbol does not have a codeword assigned. In addition, + * @lens may alias @decode_table, as noted above. + * + * @max_codeword_len: + * The maximum codeword length permitted for this code. All entries in + * 'lens' must be less than or equal to this value. + * + * @working_space + * A temporary array that was declared with DECODE_TABLE_WORKING_SPACE(). + * + * 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[], unsigned num_syms, + unsigned table_bits, const u8 lens[], + unsigned max_codeword_len, u16 working_space[]) { - 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; + u16 * const len_counts = &working_space[0]; + u16 * const offsets = &working_space[1 * (max_codeword_len + 1)]; + u16 * const sorted_syms = &working_space[2 * (max_codeword_len + 1)]; + s32 remainder = 1; + void *entry_ptr = decode_table; + unsigned codeword_len = 1; unsigned sym_idx; - unsigned codeword_len; - unsigned stores_per_loop; - -#ifdef USE_LONG_FILL - const unsigned entries_per_long = sizeof(unsigned long) / 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); + unsigned codeword; + unsigned subtable_pos; + unsigned subtable_bits; + unsigned subtable_prefix; + + /* Count how many codewords have each length, including 0. */ + 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 */ - left = 1; + /* It is already guaranteed that all lengths are <= max_codeword_len, + * but it cannot be assumed they form a complete prefix code. A + * codeword of length n should require a proportion of the codespace + * equaling (1/2)^n. The code is complete if and only if, by this + * measure, the codespace is exactly filled by the lengths. */ 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)"); + remainder = (remainder << 1) - len_counts[len]; + /* Do the lengths overflow the codespace? */ + if (unlikely(remainder < 0)) return -1; - } } - if (unlikely(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 { - DEBUG("Invalid Huffman code (incomplete set)"); + if (remainder != 0) { + /* The lengths do not fill the codespace; that is, they form an + * incomplete code. This is permitted only if the code is empty + * (contains no symbols). */ + + if (unlikely(remainder != 1U << max_codeword_len)) return -1; - } + + /* The code is empty. When processing a well-formed stream, the + * decode table need not be initialized in this case. However, + * we cannot assume the stream is well-formed, so we must + * initialize the decode table anyway. Setting all entries to 0 + * makes the decode table always produce symbol '0' without + * consuming any bits, which is good enough. */ + memset(decode_table, 0, sizeof(decode_table[0]) << table_bits); + return 0; } - /* Generate offsets into symbol table for each length for sorting */ - offsets[1] = 0; - for (unsigned len = 1; len < max_codeword_len; len++) + /* Sort the symbols primarily by increasing codeword length and + * secondarily by increasing symbol value. */ + + /* Initialize 'offsets' so that 'offsets[len]' is the number of + * codewords shorter than 'len' bits, including length 0. */ + offsets[0] = 0; + for (unsigned len = 0; 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. */ + /* Use the 'offsets' array to sort the symbols. */ 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. */ - 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. */ - stores_per_loop = (1 << (table_bits - codeword_len)) / entries_per_xmm; - for (; stores_per_loop != 0; codeword_len++, stores_per_loop >>= 1) { + sorted_syms[offsets[lens[sym]]++] = sym; + + /* + * Fill the root table entries for codewords no longer than table_bits. + * + * The table will start with entries for the shortest codeword(s), which + * will 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 + * word accesses (2 or 4 entries/store), then change to 16-bit accesses + * (1 entry/store). + */ + sym_idx = offsets[0]; + +#ifdef __SSE2__ + /* Fill entries one 128-bit vector (8 entries) at a time. */ + for (unsigned stores_per_loop = (1U << (table_bits - codeword_len)) / + (sizeof(__m128i) / sizeof(decode_table[0])); + 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 + /* Note: unlike in the "word" 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; - __m128i v; - __m128i *p; - unsigned n; - - sym = sorted_syms[sym_idx]; - - v = _mm_set1_epi16(sym); - p = (__m128i*)decode_table_ptr; - n = stores_per_loop; + * it to access an array of u16 will not violate strict + * aliasing. */ + __m128i v = _mm_set1_epi16( + MAKE_DECODE_TABLE_ENTRY(sorted_syms[sym_idx], + codeword_len)); + unsigned n = stores_per_loop; do { - *p++ = v; + *(__m128i *)entry_ptr = v; + entry_ptr += sizeof(v); } while (--n); - decode_table_ptr = p; } } -#endif /* USE_SSE2_FILL */ +#endif /* __SSE2__ */ -#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; - for (; stores_per_loop != 0; codeword_len++, stores_per_loop >>= 1) { +#ifdef __GNUC__ + /* Fill entries one word (2 or 4 entries) at a time. */ + for (unsigned stores_per_loop = (1U << (table_bits - codeword_len)) / + (WORDBYTES / sizeof(decode_table[0])); + 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; - - sym = sorted_syms[sym_idx]; - - BUILD_BUG_ON(sizeof(aliased_long_t) != 4 && - sizeof(aliased_long_t) != 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; - } - - p = (aliased_long_t *)decode_table_ptr; - n = stores_per_loop; - + /* 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 + __attribute__((may_alias)) aliased_word_t; + aliased_word_t v = repeat_u16( + MAKE_DECODE_TABLE_ENTRY(sorted_syms[sym_idx], + codeword_len)); + unsigned n = stores_per_loop; do { - *p++ = v; + *(aliased_word_t *)entry_ptr = v; + entry_ptr += sizeof(v); } while (--n); - decode_table_ptr = p; } } -#endif /* USE_LONG_FILL */ +#endif /* __GNUC__ */ - /* Fill in the Huffman decode table 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) { + /* Fill entries one at a time. */ + for (unsigned stores_per_loop = (1U << (table_bits - codeword_len)); + 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 *p; - unsigned n; - - sym = sorted_syms[sym_idx]; - - p = (u16*)decode_table_ptr; - n = stores_per_loop; - + u16 v = MAKE_DECODE_TABLE_ENTRY(sorted_syms[sym_idx], + codeword_len); + unsigned n = stores_per_loop; do { - *p++ = sym; + *(u16 *)entry_ptr = v; + entry_ptr += sizeof(v); } 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. */ - - decode_table_pos = (u16*)decode_table_ptr - decode_table; - if (decode_table_pos != table_num_entries) { - unsigned j; - 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. - * */ - 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. */ - 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) - { - unsigned end_sym_idx = sym_idx + len_counts[codeword_len]; - for (; sym_idx < end_sym_idx; sym_idx++, cur_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. */ - 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; + /* If all symbols were processed, then no subtables are required. */ + if (sym_idx == num_syms) + return 0; + + /* At least one subtable is required. Process the remaining symbols. */ + codeword = ((u16 *)entry_ptr - decode_table) << 1; + subtable_pos = 1U << table_bits; + subtable_bits = table_bits; + subtable_prefix = -1; + do { + while (len_counts[codeword_len] == 0) { + codeword_len++; + codeword <<= 1; + } - /* 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) */ + unsigned prefix = codeword >> (codeword_len - table_bits); + + /* Start a new subtable if the first 'table_bits' bits of the + * codeword don't match the prefix for the previous subtable, or + * if this will be the first subtable. */ + if (prefix != subtable_prefix) { + + subtable_prefix = prefix; + + /* + * Calculate the subtable length. If the codeword + * length exceeds 'table_bits' by n, then the subtable + * needs at least 2^n entries. But it may need more; if + * there are fewer than 2^n codewords of length + * 'table_bits + n' remaining, then n will need to be + * incremented to bring in longer codewords until the + * subtable can be filled completely. Note that it + * always will, eventually, be possible to fill the + * subtable, since it was previously verified that the + * code is complete. + */ + subtable_bits = codeword_len - table_bits; + remainder = (s32)1 << subtable_bits; + for (;;) { + remainder -= len_counts[table_bits + + subtable_bits]; + if (remainder <= 0) + break; + subtable_bits++; + remainder <<= 1; } + + /* Create the entry that points from the root table to + * the subtable. This entry contains the index of the + * start of the subtable and the number of bits with + * which the subtable is indexed (the log base 2 of the + * number of entries it contains). */ + decode_table[subtable_prefix] = + MAKE_DECODE_TABLE_ENTRY(subtable_pos, + subtable_bits); } - } - 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; + /* Fill the subtable entries for this symbol. */ + u16 entry = MAKE_DECODE_TABLE_ENTRY(sorted_syms[sym_idx], + codeword_len - table_bits); + unsigned n = 1U << (subtable_bits - (codeword_len - + table_bits)); + do { + decode_table[subtable_pos++] = entry; + } while (--n); - 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); - } + len_counts[codeword_len]--; + codeword++; + } while (++sym_idx < num_syms); - 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; }