X-Git-Url: https://wimlib.net/git/?p=wimlib;a=blobdiff_plain;f=include%2Fwimlib%2Fdecompress_common.h;h=fab3c3e009413c4ef9ed4b9f0a4a6a3a672cc1a9;hp=3b20f4e09e74b744be139817df513d5b2f6c9372;hb=31786dbc470c919893bf4fc5cc91a0f73cbee720;hpb=63be24f6367f907c49d3bc1d6ac86311bd0cba68 diff --git a/include/wimlib/decompress_common.h b/include/wimlib/decompress_common.h index 3b20f4e0..fab3c3e0 100644 --- a/include/wimlib/decompress_common.h +++ b/include/wimlib/decompress_common.h @@ -2,6 +2,9 @@ * decompress_common.h * * Header for decompression code shared by multiple compression formats. + * + * The author dedicates this file to the public domain. + * You can do whatever you want with this file. */ #ifndef _WIMLIB_DECOMPRESS_COMMON_H @@ -9,15 +12,9 @@ #include "wimlib/assert.h" #include "wimlib/compiler.h" -#include "wimlib/error.h" #include "wimlib/endianness.h" #include "wimlib/types.h" -#ifndef INPUT_IDX_T_DEFINED -#define INPUT_IDX_T_DEFINED -typedef u32 input_idx_t; -#endif - /* Structure to encapsulate a block of in-memory data that is being interpreted * as a stream of bits. * @@ -37,13 +34,13 @@ struct input_bitstream { const u8 *data; /* Number of bytes of data that are left. */ - input_idx_t data_bytes_left; + u32 data_bytes_left; }; /* Initializes a bitstream to receive its input from @data. */ static inline void init_input_bitstream(struct input_bitstream *istream, - const void *data, input_idx_t num_data_bytes) + const void *data, u32 num_data_bytes) { istream->bitbuf = 0; istream->bitsleft = 0; @@ -129,48 +126,127 @@ bitstream_read_byte(struct input_bitstream *istream) return *istream->data++; } + +/* 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 + +/* 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 + +/* 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. */ + * 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 * restrict istream, - const u16 decode_table[restrict], - const u8 lens[restrict], - unsigned num_syms, - unsigned table_bits, - unsigned max_codeword_len) +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); - /* Use the next table_bits of the input as an index into the - * decode_table. */ - u16 key_bits = bitstream_peek_bits(istream, table_bits); - - u16 sym = decode_table[key_bits]; - - if (likely(sym < num_syms)) { - /* Fast case: The decode table directly provided the symbol. */ - bitstream_remove_bits(istream, lens[sym]); + /* 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_pop_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; } - return sym; } 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 */ +/* + * Copy a LZ77 match at (dst - offset) to dst. + * + * The length and offset must be already validated --- that is, (dst - offset) + * can't underrun the output buffer, and (dst + length) can't overrun the output + * buffer. Also, the length cannot be 0. + * + * @winend points to the byte past the end of the output buffer. + * This function won't write any data beyond this position. + */ +static inline void +lz_copy(u8 *dst, unsigned length, unsigned offset, const u8 *winend) +{ + const u8 *src = dst - offset; +#if defined(__x86_64__) || defined(__i386__) + /* Copy one 'unsigned long' at a time. On i386 and x86_64 this is + * faster than copying one byte at a time, unless the data is + * near-random and all the matches have very short lengths. Note that + * since this requires unaligned memory accesses, it won't necessarily + * be faster on every architecture. + * + * Also note that we might copy more than the length of the match. For + * example, if an 'unsigned long' is 8 bytes and the match is of length + * 5, then we'll simply copy 8 bytes. This is okay as long as we don't + * write beyond the end of the output buffer, hence the check for + * (winend - (dst + length) >= sizeof(unsigned long) - 1). */ + if (offset >= sizeof(unsigned long) && + winend - (dst + length) >= sizeof(unsigned long) - 1) + { + /* Access memory through a packed struct. This tricks the + * compiler into allowing unaligned memory accesses. */ + struct ulong_wrapper { + unsigned long v; + } _packed_attribute; + + const u8 *end = dst + length; + do { + unsigned long v = ((struct ulong_wrapper *)src)->v; + ((struct ulong_wrapper *)dst)->v = v; + dst += sizeof(unsigned long); + src += sizeof(unsigned long); + } while (dst < end); + + return; + } +#endif + do { + *dst++ = *src++; + } while (--length); +} + +#endif /* _WIMLIB_DECOMPRESS_COMMON_H */