X-Git-Url: https://wimlib.net/git/?p=wimlib;a=blobdiff_plain;f=include%2Fwimlib%2Fdecompress_common.h;h=c25d5e84838324efdc2d0bd77a4760c81859dbe0;hp=4b5a7e3cdf89a34c407ab123ad7e603bf90d9acd;hb=fe548d263d477a745dfa5057f540cc5c35ecce89;hpb=883833a4b3dabec325edf1ca938000f91d587c00;ds=sidebyside diff --git a/include/wimlib/decompress_common.h b/include/wimlib/decompress_common.h index 4b5a7e3c..c25d5e84 100644 --- a/include/wimlib/decompress_common.h +++ b/include/wimlib/decompress_common.h @@ -9,7 +9,6 @@ #include "wimlib/assert.h" #include "wimlib/compiler.h" -#include "wimlib/error.h" #include "wimlib/endianness.h" #include "wimlib/types.h" @@ -51,22 +50,22 @@ init_input_bitstream(struct input_bitstream *istream, istream->data_bytes_left = num_data_bytes; } -/* Ensures that the bit buffer variable for the bitstream contains @num_bits - * bits. +/* Ensures the bit buffer variable for the bitstream contains at least @num_bits + * bits. Following this, bitstream_peek_bits() and/or bitstream_remove_bits() + * may be called on the bitstream to peek or remove up to @num_bits bits. * - * If there are at least @num_bits bits remaining in the bitstream, 0 is - * returned. Otherwise, -1 is returned. */ -static inline int + * If the input data is exhausted, any further bits are assumed to be 0. */ +static inline void bitstream_ensure_bits(struct input_bitstream *istream, unsigned num_bits) { for (int nbits = num_bits; (int)istream->bitsleft < nbits; nbits -= 16) { u16 nextword; unsigned shift; - if (unlikely(istream->data_bytes_left < 2)) - return -1; - - wimlib_assert2(istream->bitsleft <= sizeof(istream->bitbuf) * 8 - 16); + if (unlikely(istream->data_bytes_left < 2)) { + istream->bitsleft = num_bits; + return; + } nextword = le16_to_cpu(*(const le16*)istream->data); shift = sizeof(istream->bitbuf) * 8 - 16 - istream->bitsleft; @@ -74,37 +73,33 @@ bitstream_ensure_bits(struct input_bitstream *istream, unsigned num_bits) istream->data += 2; istream->bitsleft += 16; istream->data_bytes_left -= 2; - } - return 0; } -/* Returns the next @num_bits bits in the buffer variable, which must contain at - * least @num_bits bits, for the bitstream. */ +/* Returns the next @num_bits bits from the bitstream, without removing them. + * There must be at least @num_bits remaining in the buffer variable, from a + * previous call to bitstream_ensure_bits(). */ static inline u32 bitstream_peek_bits(const struct input_bitstream *istream, unsigned num_bits) { - wimlib_assert2(istream->bitsleft >= num_bits); - if (unlikely(num_bits == 0)) return 0; - return istream->bitbuf >> (sizeof(istream->bitbuf) * 8 - num_bits); } -/* Removes @num_bits bits from the buffer variable, which must contain at least - * @num_bits bits, for the bitstream. */ +/* Removes @num_bits from the bitstream. There must be at least @num_bits + * remaining in the buffer variable, from a previous call to + * bitstream_ensure_bits(). */ static inline void bitstream_remove_bits(struct input_bitstream *istream, unsigned num_bits) { - wimlib_assert2(istream->bitsleft >= num_bits); - istream->bitbuf <<= num_bits; istream->bitsleft -= num_bits; } -/* Gets and removes @num_bits bits from the buffer variable, which must contain - * at least @num_bits bits, for the bitstream. */ +/* Removes and returns @num_bits bits from the bitstream. There must be at + * least @num_bits remaining in the buffer variable, from a previous call to + * bitstream_ensure_bits(). */ static inline u32 bitstream_pop_bits(struct input_bitstream *istream, unsigned num_bits) { @@ -113,97 +108,95 @@ bitstream_pop_bits(struct input_bitstream *istream, unsigned num_bits) return n; } -/* Reads @num_bits bits from the input bitstream. On success, returns 0 and - * returns the requested bits in @n. If there are fewer than @num_bits - * remaining in the bitstream, -1 is returned. */ -static inline int -bitstream_read_bits(struct input_bitstream *istream, unsigned num_bits, u32 *n) +/* Reads and returns the next @num_bits bits from the bitstream. + * If the input data is exhausted, the bits are assumed to be 0. */ +static inline u32 +bitstream_read_bits(struct input_bitstream *istream, unsigned num_bits) { - if (unlikely(bitstream_ensure_bits(istream, num_bits))) - return -1; - - *n = bitstream_pop_bits(istream, num_bits); - return 0; + bitstream_ensure_bits(istream, num_bits); + return bitstream_pop_bits(istream, num_bits); } -/* Return the next literal byte embedded in the bitstream, or -1 if the input - * was exhausted. */ -static inline int +/* Reads and returns the next literal byte embedded in the bitstream. + * If the input data is exhausted, the byte is assumed to be 0. */ +static inline u8 bitstream_read_byte(struct input_bitstream *istream) { - if (unlikely(istream->data_bytes_left < 1)) - return -1; - + if (unlikely(istream->data_bytes_left == 0)) + return 0; istream->data_bytes_left--; return *istream->data++; } -/* Reads @num_bits bits from the buffer variable for a bistream without checking - * to see if that many bits are in the buffer or not. */ -static inline u32 -bitstream_read_bits_nocheck(struct input_bitstream *istream, unsigned num_bits) -{ - u32 n = bitstream_peek_bits(istream, num_bits); - bitstream_remove_bits(istream, num_bits); - return n; -} -extern 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); - -/* Read a Huffman-encoded symbol from a bitstream. */ -static inline int -read_huffsym(struct input_bitstream * restrict istream, - const u16 decode_table[restrict], - const u8 lens[restrict], - unsigned num_syms, - unsigned table_bits, - unsigned *restrict n, - unsigned max_codeword_len) -{ - /* If there are fewer bits remaining in the input than the maximum - * codeword length, use the slow path that has extra checks. */ - if (unlikely(bitstream_ensure_bits(istream, max_codeword_len))) { - return read_huffsym_near_end_of_input(istream, decode_table, - lens, num_syms, - table_bits, n); - } - - /* Use the next table_bits of the input as an index into the - * decode_table. */ - u16 key_bits = bitstream_peek_bits(istream, table_bits); +/* Needed alignment of decode_table parameter to make_huffman_decode_table(). + * + * Reason: We may fill the entries with SSE instructions without worrying + * about dealing with the unaligned case. */ +#define DECODE_TABLE_ALIGNMENT 16 - u16 sym = decode_table[key_bits]; +/* Maximum supported symbol count for make_huffman_decode_table(). + * + * Reason: In direct mapping entries, we store the symbol in 11 bits. */ +#define DECODE_TABLE_MAX_SYMBOLS 2048 - if (likely(sym < num_syms)) { - /* Fast case: The decode table directly provided the symbol. */ - bitstream_remove_bits(istream, lens[sym]); +/* Maximum supported table bits for make_huffman_decode_table(). + * + * Reason: In internal binary tree nodes, offsets are encoded in 14 bits. + * But the real limit is 13, because we allocate entries past the end of + * the direct lookup part of the table for binary tree nodes. (Note: if + * needed this limit could be removed by encoding the offsets relative to + * &decode_table[1 << table_bits].) */ +#define DECODE_TABLE_MAX_TABLE_BITS 13 + +/* Maximum supported codeword length for make_huffman_decode_table(). + * + * Reason: In direct mapping entries, we encode the codeword length in 5 + * bits, and the top 2 bits can't both be set because that has special + * meaning. */ +#define DECODE_TABLE_MAX_CODEWORD_LEN 23 + +/* Reads and returns the next Huffman-encoded symbol from a bitstream. If the + * input data is exhausted, the Huffman symbol is decoded as if the missing bits + * are all zeroes. + * + * XXX: This is mostly duplicated in lzms_huffman_decode_symbol() in + * lzms-decompress.c. */ +static inline u16 +read_huffsym(struct input_bitstream *istream, const u16 decode_table[], + unsigned table_bits, unsigned max_codeword_len) +{ + u16 entry; + u16 key_bits; + + bitstream_ensure_bits(istream, max_codeword_len); + + /* Index the decode table by the next table_bits bits of the input. */ + key_bits = bitstream_peek_bits(istream, table_bits); + entry = decode_table[key_bits]; + if (likely(entry < 0xC000)) { + /* Fast case: The decode table directly provided the + * symbol and codeword length. The low 11 bits are the + * symbol, and the high 5 bits are the codeword length. */ + bitstream_remove_bits(istream, entry >> 11); + return entry & 0x7FF; } else { - /* Slow case: The symbol took too many bits to include directly - * in the decode table, so search for it in a binary tree at the - * end of the decode table. */ + /* Slow case: The codeword for the symbol is longer than + * table_bits, so the symbol does not have an entry + * directly in the first (1 << table_bits) entries of the + * decode table. Traverse the appropriate binary tree + * bit-by-bit to decode the symbol. */ bitstream_remove_bits(istream, table_bits); do { - key_bits = sym + bitstream_peek_bits(istream, 1); - bitstream_remove_bits(istream, 1); - } while ((sym = decode_table[key_bits]) >= num_syms); + key_bits = (entry & 0x3FFF) + bitstream_pop_bits(istream, 1); + } while ((entry = decode_table[key_bits]) >= 0xC000); + return entry; } - *n = sym; - return 0; } extern int make_huffman_decode_table(u16 decode_table[], unsigned num_syms, - unsigned num_bits, const u8 lengths[], + unsigned num_bits, const u8 lens[], unsigned max_codeword_len); -/* Minimum alignment for the decode_table parameter to - * make_huffman_decode_table(). */ -#define DECODE_TABLE_ALIGNMENT 16 - -#endif /* _WIMLIB_DECOMPRESS_H */ +#endif /* _WIMLIB_DECOMPRESS_COMMON_H */