From 7e19ce1965d0e7e60f2dd75337c5170513b98945 Mon Sep 17 00:00:00 2001 From: Eric Biggers Date: Mon, 4 Jul 2016 17:01:38 -0500 Subject: [PATCH] lzx word bitstream --- include/wimlib/decompress_common.h | 61 ++++++++++++++++++------------ src/lzx_decompress.c | 49 +++++++++--------------- src/xpress_decompress.c | 5 ++- 3 files changed, 58 insertions(+), 57 deletions(-) diff --git a/include/wimlib/decompress_common.h b/include/wimlib/decompress_common.h index 20790464..1ef8d569 100644 --- a/include/wimlib/decompress_common.h +++ b/include/wimlib/decompress_common.h @@ -37,10 +37,10 @@ struct input_bitstream { /* Bits that have been read from the input buffer. The bits are * left-justified; the next bit is always bit 31. */ - u32 bitbuf; + machine_word_t bitbuf; /* Number of bits currently held in @bitbuf. */ - u32 bitsleft; + machine_word_t bitsleft; /* Pointer to the next byte to be retrieved from the input buffer. */ const u8 *next; @@ -77,26 +77,43 @@ bitstream_ensure_bits(struct input_bitstream *is, const unsigned num_bits) if (is->bitsleft >= num_bits) return; - if (unlikely(is->end - is->next < 2)) - goto overflow; + /*if (unlikely(is->end - is->next < 6))*/ + /*goto slow;*/ - is->bitbuf |= (u32)get_unaligned_le16(is->next) << (16 - is->bitsleft); - is->next += 2; - is->bitsleft += 16; + /*is->bitbuf |= (machine_word_t)get_unaligned_le16(is->next + 0) << (WORDBITS - 16 - is->bitsleft);*/ + /*is->bitbuf |= (machine_word_t)get_unaligned_le16(is->next + 2) << (WORDBITS - 32 - is->bitsleft);*/ + /*is->bitbuf |= (machine_word_t)get_unaligned_le16(is->next + 4) << (WORDBITS - 48 - is->bitsleft);*/ + /*is->next += 6;*/ + /*is->bitsleft += 48;*/ - if (unlikely(num_bits == 17 && is->bitsleft == 16)) { - if (unlikely(is->end - is->next < 2)) - goto overflow; + /*return;*/ - is->bitbuf |= (u32)get_unaligned_le16(is->next); +/*slow:*/ + if (likely(is->end - is->next >= 2)) { + is->bitbuf |= + (machine_word_t)get_unaligned_le16(is->next) << + (WORDBITS - 16 - is->bitsleft); is->next += 2; - is->bitsleft = 32; } - - return; - -overflow: - is->bitsleft = 32; + is->bitsleft += 16; + if (unlikely(num_bits > 16 && is->bitsleft < num_bits)) { + if (likely(is->end - is->next >= 2)) { + is->bitbuf |= + (machine_word_t)get_unaligned_le16(is->next) << + (WORDBITS - 16 - is->bitsleft); + is->next += 2; + } + is->bitsleft += 16; + if (unlikely(num_bits > 32 && is->bitsleft < num_bits)) { + if (likely(is->end - is->next >= 2)) { + is->bitbuf |= + (machine_word_t)get_unaligned_le16(is->next) << + (WORDBITS - 16 - is->bitsleft); + is->next += 2; + } + is->bitsleft += 16; + } + } } /* Return the next @num_bits bits from the bitstream, without removing them. @@ -105,7 +122,7 @@ overflow: static inline u32 bitstream_peek_bits(const struct input_bitstream *is, const unsigned num_bits) { - return (is->bitbuf >> 1) >> (sizeof(is->bitbuf) * 8 - num_bits - 1); + return (is->bitbuf >> 1) >> (WORDBITS - num_bits - 1); } /* Remove @num_bits from the bitstream. There must be at least @num_bits @@ -214,17 +231,13 @@ bitstream_align(struct input_bitstream *is) * lzms_decompress.c. */ static inline unsigned -read_huffsym(struct input_bitstream *is, const u16 decode_table[], - unsigned table_bits, unsigned max_codeword_len) +pop_huffsym(struct input_bitstream *is, const u16 decode_table[], + unsigned table_bits, unsigned max_codeword_len) { unsigned entry; unsigned sym; unsigned len; - /* If the bitbuffer contains fewer bits than might be required by a - * single codeword, then refill it. */ - bitstream_ensure_bits(is, max_codeword_len); - /* Index the root table by the next 'table_bits' bits of input. */ entry = decode_table[bitstream_peek_bits(is, table_bits)]; diff --git a/src/lzx_decompress.c b/src/lzx_decompress.c index 45b6e38a..2c12c2ce 100644 --- a/src/lzx_decompress.c +++ b/src/lzx_decompress.c @@ -107,32 +107,9 @@ struct lzx_decompressor { static inline unsigned read_presym(const struct lzx_decompressor *d, struct input_bitstream *is) { - return read_huffsym(is, d->precode_decode_table, - LZX_PRECODE_TABLEBITS, LZX_MAX_PRE_CODEWORD_LEN); -} - -/* Read a Huffman-encoded symbol using the main code. */ -static inline unsigned -read_mainsym(const struct lzx_decompressor *d, struct input_bitstream *is) -{ - return read_huffsym(is, d->maincode_decode_table, - LZX_MAINCODE_TABLEBITS, LZX_MAX_MAIN_CODEWORD_LEN); -} - -/* Read a Huffman-encoded symbol using the length code. */ -static inline unsigned -read_lensym(const struct lzx_decompressor *d, struct input_bitstream *is) -{ - return read_huffsym(is, d->lencode_decode_table, - LZX_LENCODE_TABLEBITS, LZX_MAX_LEN_CODEWORD_LEN); -} - -/* Read a Huffman-encoded symbol using the aligned offset code. */ -static inline unsigned -read_alignedsym(const struct lzx_decompressor *d, struct input_bitstream *is) -{ - return read_huffsym(is, d->alignedcode_decode_table, - LZX_ALIGNEDCODE_TABLEBITS, LZX_MAX_ALIGNED_CODEWORD_LEN); + bitstream_ensure_bits(is, LZX_MAX_PRE_CODEWORD_LEN); + return pop_huffsym(is, d->precode_decode_table, LZX_PRECODE_TABLEBITS, + LZX_MAX_PRE_CODEWORD_LEN); } /* @@ -367,7 +344,11 @@ lzx_decompress_block(struct lzx_decompressor *d, struct input_bitstream *is, u32 offset; unsigned offset_slot; - mainsym = read_mainsym(d, is); + bitstream_ensure_bits(is, 48); + + mainsym = pop_huffsym(is, d->maincode_decode_table, + LZX_MAINCODE_TABLEBITS, + LZX_MAX_MAIN_CODEWORD_LEN); if (mainsym < LZX_NUM_CHARS) { /* Literal */ *out_next++ = mainsym; @@ -382,8 +363,11 @@ lzx_decompress_block(struct lzx_decompressor *d, struct input_bitstream *is, offset_slot = mainsym / LZX_NUM_LEN_HEADERS; /* If needed, read a length symbol to decode the full length. */ - if (length == LZX_NUM_PRIMARY_LENS) - length += read_lensym(d, is); + if (length == LZX_NUM_PRIMARY_LENS) { + length += pop_huffsym(is, d->lencode_decode_table, + LZX_LENCODE_TABLEBITS, + LZX_MAX_LEN_CODEWORD_LEN); + } length += LZX_MIN_MATCH_LEN; if (offset_slot < LZX_NUM_RECENT_OFFSETS) { @@ -397,10 +381,13 @@ lzx_decompress_block(struct lzx_decompressor *d, struct input_bitstream *is, recent_offsets[offset_slot] = recent_offsets[0]; } else { /* Explicit offset */ - offset = bitstream_read_bits(is, d->extra_offset_bits[offset_slot]); + offset = bitstream_pop_bits(is, d->extra_offset_bits[offset_slot]); if (offset_slot >= min_aligned_offset_slot) { offset = (offset << LZX_NUM_ALIGNED_OFFSET_BITS) | - read_alignedsym(d, is); + pop_huffsym(is, + d->alignedcode_decode_table, + LZX_ALIGNEDCODE_TABLEBITS, + LZX_MAX_ALIGNED_CODEWORD_LEN); } offset += lzx_offset_slot_base[offset_slot]; diff --git a/src/xpress_decompress.c b/src/xpress_decompress.c index 9fd5ac5e..77758697 100644 --- a/src/xpress_decompress.c +++ b/src/xpress_decompress.c @@ -116,8 +116,9 @@ xpress_decompress(const void *restrict compressed_data, size_t compressed_size, u32 length; u32 offset; - sym = read_huffsym(&is, u.decode_table, - XPRESS_TABLEBITS, XPRESS_MAX_CODEWORD_LEN); + bitstream_ensure_bits(&is, XPRESS_MAX_CODEWORD_LEN); + sym = pop_huffsym(&is, u.decode_table, XPRESS_TABLEBITS, + XPRESS_MAX_CODEWORD_LEN); if (sym < XPRESS_NUM_CHARS) { /* Literal */ *out_next++ = sym; -- 2.46.1