X-Git-Url: https://wimlib.net/git/?p=wimlib;a=blobdiff_plain;f=src%2Fdecompress_common.c;h=76fb1278ab0efed9cdd2ca8cffe2bd5ecd10d8b3;hp=66440efe203acaed25f56d6a45ddf07d12c25ab7;hb=21da2526eff64cdb8e3cb509d34af182d764c701;hpb=4e4f9c37fe7dfedb4408b72466666eb136d62c50 diff --git a/src/decompress_common.c b/src/decompress_common.c index 66440efe..76fb1278 100644 --- a/src/decompress_common.c +++ b/src/decompress_common.c @@ -15,16 +15,16 @@ #endif #include "wimlib/decompress_common.h" -#include "wimlib/util.h" /* for BUILD_BUG_ON() */ #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 @@ -98,9 +98,11 @@ * binary tree. * * @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. + * 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. * * @num_syms: * The number of symbols in the alphabet; also, the length of the @@ -115,7 +117,9 @@ * 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. + * assigned. This is permitted to alias @decode_table, since all + * information from @lens is consumed before anything is written to + * @decode_table. * * @max_codeword_len: * The longest codeword length allowed in the compression format. @@ -126,10 +130,10 @@ * code. */ int -make_huffman_decode_table(u16 decode_table[const restrict], +make_huffman_decode_table(u16 decode_table[const], const unsigned num_syms, const unsigned table_bits, - const u8 lens[const restrict], + const u8 lens[const], const unsigned max_codeword_len) { const unsigned table_num_entries = 1 << table_bits; @@ -142,22 +146,14 @@ make_huffman_decode_table(u16 decode_table[const restrict], 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 - /* Check parameters if assertions are enabled. */ - wimlib_assert2((uintptr_t)decode_table % DECODE_TABLE_ALIGNMENT == 0); - wimlib_assert2(num_syms <= DECODE_TABLE_MAX_SYMBOLS); - wimlib_assert2(table_bits <= DECODE_TABLE_MAX_TABLE_BITS); - wimlib_assert2(max_codeword_len <= DECODE_TABLE_MAX_CODEWORD_LEN); - 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. */ @@ -230,7 +226,7 @@ make_huffman_decode_table(u16 decode_table[const restrict], * 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 - * 'unsigned long' accesses (2 or 4 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; @@ -242,11 +238,11 @@ make_huffman_decode_table(u16 decode_table[const restrict], 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. - */ + /* 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; @@ -265,36 +261,33 @@ make_huffman_decode_table(u16 decode_table[const restrict], } #endif /* USE_SSE2_FILL */ -#ifdef USE_LONG_FILL - /* Fill the entries one 'unsigned long' at a time. +#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_long; + 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; - - unsigned long v; - aliased_long_t *p; + /* 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; + + machine_word_t v; + aliased_word_t *p; unsigned n; - BUILD_BUG_ON(sizeof(unsigned long) != 4 && - sizeof(unsigned long) != 8); + STATIC_ASSERT(WORDSIZE == 4 || WORDSIZE == 8); v = MAKE_DIRECT_ENTRY(sorted_syms[sym_idx], codeword_len); v |= v << 16; - v |= v << (sizeof(unsigned long) == 8 ? 32 : 0); + 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 { @@ -303,7 +296,7 @@ make_huffman_decode_table(u16 decode_table[const restrict], decode_table_ptr = p; } } -#endif /* USE_LONG_FILL */ +#endif /* USE_WORD_FILL */ /* Fill the entries one 16-bit integer at a time. */ stores_per_loop = (1 << (table_bits - codeword_len)); @@ -384,7 +377,7 @@ make_huffman_decode_table(u16 decode_table[const restrict], * 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 + * with the special bits 0xC000 to distinguish * the entry from direct mapping and leaf node * entries. */ do {