*
* The following copying information applies to this specific source code file:
*
- * Written in 2012-2015 by Eric Biggers <ebiggers3@gmail.com>
+ * Written in 2012-2016 by Eric Biggers <ebiggers3@gmail.com>
*
* 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
# include "config.h"
#endif
-#include "wimlib/decompress_common.h"
-
#include <string.h>
-#define USE_WORD_FILL
-
-#ifdef __GNUC__
-# ifdef __SSE2__
-# undef USE_WORD_FILL
-# define USE_SSE2_FILL
-# include <emmintrin.h>
-# endif
+#ifdef __SSE2__
+# include <emmintrin.h>
#endif
-/* Construct a direct mapping entry in the lookup table. */
+#include "wimlib/decompress_common.h"
+
+/* Construct a direct mapping entry in the decode table. */
#define MAKE_DIRECT_ENTRY(symbol, length) ((symbol) | ((length) << 11))
/*
const unsigned max_codeword_len)
{
const unsigned table_num_entries = 1 << table_bits;
+ unsigned offsets[max_codeword_len + 1];
unsigned len_counts[max_codeword_len + 1];
u16 sorted_syms[num_syms];
- int left;
+ s32 remainder;
void *decode_table_ptr;
unsigned sym_idx;
unsigned codeword_len;
- unsigned stores_per_loop;
unsigned decode_table_pos;
-#ifdef USE_WORD_FILL
- const unsigned entries_per_word = WORDBYTES / sizeof(decode_table[0]);
-#endif
-
-#ifdef USE_SSE2_FILL
- const unsigned entries_per_xmm = sizeof(__m128i) / sizeof(decode_table[0]);
-#endif
-
- /* 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. */
+ /* Count how many symbols have each codeword 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]]++;
- /* 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;
+ /* 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. */
+ remainder = 1;
for (unsigned len = 1; len <= max_codeword_len; len++) {
- left <<= 1;
- left -= len_counts[len];
- if (unlikely(left < 0)) {
+ remainder <<= 1;
+ remainder -= len_counts[len];
+ if (unlikely(remainder < 0)) {
/* The lengths overflow the codespace; that is, the code
* is over-subscribed. */
return -1;
}
}
- if (unlikely(left != 0)) {
+ if (unlikely(remainder != 0)) {
/* The lengths do not fill the codespace; that is, they form an
- * incomplete set. */
- if (left == (1 << max_codeword_len)) {
+ * incomplete code. */
+ if (remainder == (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
return -1;
}
- /* Sort the symbols primarily by length and secondarily by symbol order.
- */
- {
- unsigned offsets[max_codeword_len + 1];
+ /* Sort the symbols primarily by increasing codeword length and
+ * secondarily by increasing symbol value. */
- /* 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];
+ /* 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];
- /* 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;
- }
+ /* Use the 'offsets' array to sort the symbols. */
+ for (unsigned sym = 0; sym < num_syms; sym++)
+ sorted_syms[offsets[lens[sym]]++] = sym;
- /* Fill entries for codewords with length <= table_bits
+ /*
+ * 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
* 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). */
+ * 16-bit accesses (1 entry/store).
+ */
decode_table_ptr = decode_table;
- sym_idx = 0;
+ sym_idx = offsets[0];
codeword_len = 1;
-#ifdef USE_SSE2_FILL
- /* 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) {
+#ifdef __SSE2__
+ /* Fill entries one 128-bit vector (8 entries) at a time. */
+ for (unsigned stores_per_loop = (1 << (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 machine_word_t version below, the
* 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;
-
- entry = MAKE_DIRECT_ENTRY(sorted_syms[sym_idx], codeword_len);
-
- v = _mm_set1_epi16(entry);
- p = (__m128i*)decode_table_ptr;
- n = stores_per_loop;
+ __m128i v = _mm_set1_epi16(
+ MAKE_DIRECT_ENTRY(sorted_syms[sym_idx],
+ codeword_len));
+ unsigned n = stores_per_loop;
do {
- *p++ = v;
+ *(__m128i *)decode_table_ptr = v;
+ decode_table_ptr += sizeof(__m128i);
} while (--n);
- decode_table_ptr = p;
}
}
-#endif /* USE_SSE2_FILL */
+#endif /* __SSE2__ */
-#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) {
+ /* Fill entries one word (2 or 4 entries) at a time. */
+ for (unsigned stores_per_loop = (1 << (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++) {
* gcc 'may_alias' extension. */
typedef machine_word_t _may_alias_attribute aliased_word_t;
- machine_word_t v;
- aliased_word_t *p;
- unsigned n;
+ aliased_word_t v;
+ unsigned n = stores_per_loop;
STATIC_ASSERT(WORDBITS == 32 || WORDBITS == 64);
-
v = MAKE_DIRECT_ENTRY(sorted_syms[sym_idx], codeword_len);
v |= v << 16;
v |= v << (WORDBITS == 64 ? 32 : 0);
- p = (aliased_word_t *)decode_table_ptr;
- n = stores_per_loop;
-
do {
- *p++ = v;
+ *(aliased_word_t *)decode_table_ptr = v;
+ decode_table_ptr += sizeof(aliased_word_t);
} while (--n);
- decode_table_ptr = p;
}
}
-#endif /* USE_WORD_FILL */
- /* 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) {
+ /* Fill entries one at a time. */
+ for (unsigned stores_per_loop = (1 << (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 entry;
- u16 *p;
- unsigned n;
-
- entry = MAKE_DIRECT_ENTRY(sorted_syms[sym_idx], codeword_len);
-
- p = (u16*)decode_table_ptr;
- n = stores_per_loop;
-
+ u16 entry = MAKE_DIRECT_ENTRY(sorted_syms[sym_idx],
+ codeword_len);
+ unsigned n = stores_per_loop;
do {
- *p++ = entry;
+ *(u16 *)decode_table_ptr = entry;
+ decode_table_ptr += sizeof(u16);
} while (--n);
-
- decode_table_ptr = p;
}
}
* there are codewords longer than table_bits for which we must
* generate binary trees. */
- decode_table_pos = (u16*)decode_table_ptr - decode_table;
+ decode_table_pos = (u16 *)decode_table_ptr - decode_table;
if (decode_table_pos != table_num_entries) {
unsigned j;
unsigned next_free_tree_slot;
git://wimlib.net / wimlib / commitdiff