X-Git-Url: https://wimlib.net/git/?p=wimlib;a=blobdiff_plain;f=src%2Flzms-decompress.c;h=1ddc3f19dfdce40e9b0bc8e8833505654fd95595;hp=f2fcb60ebcd94b10f78c02207df6ec9926e50dcb;hb=500874ebbf2839d2c93db2b4094817c219946f29;hpb=027518fa61bd9232ff7fa7ecd270546d920c912f diff --git a/src/lzms-decompress.c b/src/lzms-decompress.c index f2fcb60e..1ddc3f19 100644 --- a/src/lzms-decompress.c +++ b/src/lzms-decompress.c @@ -35,7 +35,7 @@ * is a container format from which the locations and sizes (both compressed and * uncompressed) of the constituent blocks can be determined. * - * A LZMS-compressed block must be read in 16-bit little endian units from both + * An LZMS-compressed block must be read in 16-bit little endian units from both * directions. One logical bitstream starts at the front of the block and * proceeds forwards. Another logical bitstream starts at the end of the block * and proceeds backwards. Bits read from the forwards bitstream constitute @@ -65,7 +65,7 @@ * offset is 1, regardless of match length. * * For LZ matches, up to 3 repeat offsets are allowed, similar to some other - * LZ-based formats such as LZX and LZMA. They must updated in a LRU fashion, + * LZ-based formats such as LZX and LZMA. They must updated in an LRU fashion, * except for a quirk: updates to the queue must be delayed by one LZMS item, * except for the removal of a repeat match. As a result, 4 entries are * actually needed in the queue, even though it is only possible to decode @@ -173,7 +173,7 @@ * than 15 bits, then all frequencies must be divided by 2, rounding up, and the * code construction must be attempted again. * - * A LZMS-compressed block seemingly cannot have a compressed size greater than + * An LZMS-compressed block seemingly cannot have a compressed size greater than * or equal to the uncompressed size. In such cases the block must be stored * uncompressed. * @@ -194,7 +194,6 @@ #include "wimlib/compress_common.h" #include "wimlib/decompressor_ops.h" #include "wimlib/decompress_common.h" -#include "wimlib/error.h" #include "wimlib/lzms.h" #include "wimlib/util.h" @@ -233,7 +232,7 @@ struct lzms_input_bitstream { * at a time, this needs to be 64 bits rather than 32 bits. */ u64 bitbuf; - /* Number of bits in @bitbuf that are are used. */ + /* Number of bits in @bitbuf that are used. */ unsigned num_filled_bits; /* Pointer to the one past the next little-endian 16-bit integer in the @@ -284,6 +283,8 @@ struct lzms_huffman_decoder { * read using this decoder. */ const u32 *slot_base_tab; + const u8 *extra_bits_tab; + /* Number of symbols that have been read using this code far. Reset to * 0 whenever the code is rebuilt. */ u32 num_syms_read; @@ -303,7 +304,7 @@ struct lzms_huffman_decoder { u8 lens[LZMS_MAX_NUM_SYMS]; /* The codeword of each symbol in the Huffman code. */ - u16 codewords[LZMS_MAX_NUM_SYMS]; + u32 codewords[LZMS_MAX_NUM_SYMS]; /* A table for quickly decoding symbols encoded using the Huffman code. */ @@ -346,8 +347,8 @@ struct lzms_decompressor { struct lzms_huffman_decoder delta_power_decoder; struct lzms_huffman_decoder delta_offset_decoder; - /* LRU (least-recently-used) queues for match information. */ - struct lzms_lru_queues lru; + /* LRU (least-recently-used) queues for match information. */ + struct lzms_lru_queues lru; /* Used for postprocessing. */ s32 last_target_usages[65536]; @@ -567,9 +568,11 @@ lzms_rebuild_adaptive_huffman_code(struct lzms_huffman_decoder *dec) static u32 lzms_huffman_decode_symbol(struct lzms_huffman_decoder *dec) { - const u8 *lens = dec->lens; const u16 *decode_table = dec->decode_table; struct lzms_input_bitstream *is = dec->is; + u16 entry; + u16 key_bits; + u16 sym; /* The Huffman codes used in LZMS are adaptive and must be rebuilt * whenever a certain number of symbols have been read. Each such @@ -587,28 +590,31 @@ lzms_huffman_decode_symbol(struct lzms_huffman_decoder *dec) dec->num_syms_read = 0; } - /* In the following Huffman decoding implementation, the first - * LZMS_DECODE_TABLE_BITS of the input are used as an offset into a - * decode table. The entry will either provide the decoded symbol - * directly, or else a "real" Huffman binary tree will be searched to - * decode the symbol. */ - + /* XXX: Copied from read_huffsym() (decompress_common.h), since this + * uses a different input bitstream type. Should unify the + * implementations. */ lzms_input_bitstream_ensure_bits(is, LZMS_MAX_CODEWORD_LEN); - u16 key_bits = lzms_input_bitstream_peek_bits(is, LZMS_DECODE_TABLE_BITS); - u16 sym = decode_table[key_bits]; - - if (sym < dec->num_syms) { - /* Fast case: The decode table directly provided the symbol. */ - lzms_input_bitstream_remove_bits(is, lens[sym]); + /* Index the decode table by the next table_bits bits of the input. */ + key_bits = lzms_input_bitstream_peek_bits(is, LZMS_DECODE_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. */ + lzms_input_bitstream_remove_bits(is, entry >> 11); + sym = 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 in order to + * decode the symbol. */ lzms_input_bitstream_remove_bits(is, LZMS_DECODE_TABLE_BITS); do { - key_bits = sym + lzms_input_bitstream_pop_bits(is, 1); - } while ((sym = decode_table[key_bits]) >= dec->num_syms); + key_bits = (entry & 0x3FFF) + lzms_input_bitstream_pop_bits(is, 1); + } while ((entry = decode_table[key_bits]) >= 0xC000); + sym = entry; } /* Tally and return the decoded symbol. */ @@ -628,19 +634,19 @@ lzms_decode_value(struct lzms_huffman_decoder *dec) unsigned num_extra_bits; u32 extra_bits; + LZMS_ASSERT(dec->slot_base_tab != NULL); + LZMS_ASSERT(dec->extra_bits_tab != NULL); + /* Read the slot (position slot, length slot, etc.), which is encoded as * a Huffman symbol. */ slot = lzms_huffman_decode_symbol(dec); - LZMS_ASSERT(dec->slot_base_tab != NULL); - /* Get the number of extra bits needed to represent the range of values * that share the slot. */ - num_extra_bits = bsr32(dec->slot_base_tab[slot + 1] - - dec->slot_base_tab[slot]); + num_extra_bits = dec->extra_bits_tab[slot]; - /* Read the number of extra bits and add them to the slot to form the - * final decoded value. */ + /* Read the number of extra bits and add them to the slot base to form + * the final decoded value. */ extra_bits = lzms_input_bitstream_read_bits(dec->is, num_extra_bits); return dec->slot_base_tab[slot] + extra_bits; } @@ -795,6 +801,7 @@ lzms_decode_delta_match(struct lzms_decompressor *ctx) return lzms_copy_delta_match(ctx, length, power, raw_offset); } +/* Decode an LZ or delta match. */ static int lzms_decode_match(struct lzms_decompressor *ctx) { @@ -831,8 +838,7 @@ lzms_decode_item(struct lzms_decompressor *ctx) if (ret) return ret; - /* Update LRU queues */ - lzms_update_lru_queues(&ctx->lru); + lzms_update_lru_queues(&ctx->lru); return 0; } @@ -852,11 +858,14 @@ lzms_init_range_decoder(struct lzms_range_decoder *dec, static void lzms_init_huffman_decoder(struct lzms_huffman_decoder *dec, struct lzms_input_bitstream *is, - const u32 *slot_base_tab, unsigned num_syms, + const u32 *slot_base_tab, + const u8 *extra_bits_tab, + unsigned num_syms, unsigned rebuild_freq) { dec->is = is; dec->slot_base_tab = slot_base_tab; + dec->extra_bits_tab = extra_bits_tab; dec->num_syms = num_syms; dec->num_syms_read = rebuild_freq; dec->rebuild_freq = rebuild_freq; @@ -886,9 +895,6 @@ lzms_init_decompressor(struct lzms_decompressor *ctx, * backwards) */ lzms_input_bitstream_init(&ctx->is, cdata, clen / 2); - /* Initialize position and length slot bases if not done already. */ - lzms_init_slot_bases(); - /* Calculate the number of position slots needed for this compressed * block. */ num_position_slots = lzms_get_position_slot(ulen - 1) + 1; @@ -898,23 +904,29 @@ lzms_init_decompressor(struct lzms_decompressor *ctx, /* Initialize Huffman decoders for each alphabet used in the compressed * representation. */ lzms_init_huffman_decoder(&ctx->literal_decoder, &ctx->is, - NULL, LZMS_NUM_LITERAL_SYMS, + NULL, NULL, LZMS_NUM_LITERAL_SYMS, LZMS_LITERAL_CODE_REBUILD_FREQ); lzms_init_huffman_decoder(&ctx->lz_offset_decoder, &ctx->is, - lzms_position_slot_base, num_position_slots, + lzms_position_slot_base, + lzms_extra_position_bits, + num_position_slots, LZMS_LZ_OFFSET_CODE_REBUILD_FREQ); lzms_init_huffman_decoder(&ctx->length_decoder, &ctx->is, - lzms_length_slot_base, LZMS_NUM_LEN_SYMS, + lzms_length_slot_base, + lzms_extra_length_bits, + LZMS_NUM_LEN_SYMS, LZMS_LENGTH_CODE_REBUILD_FREQ); lzms_init_huffman_decoder(&ctx->delta_offset_decoder, &ctx->is, - lzms_position_slot_base, num_position_slots, + lzms_position_slot_base, + lzms_extra_position_bits, + num_position_slots, LZMS_DELTA_OFFSET_CODE_REBUILD_FREQ); lzms_init_huffman_decoder(&ctx->delta_power_decoder, &ctx->is, - NULL, LZMS_NUM_DELTA_POWER_SYMS, + NULL, NULL, LZMS_NUM_DELTA_POWER_SYMS, LZMS_DELTA_POWER_CODE_REBUILD_FREQ); @@ -941,7 +953,7 @@ lzms_init_decompressor(struct lzms_decompressor *ctx, &ctx->rd, LZMS_NUM_DELTA_REPEAT_MATCH_STATES); /* Initialize LRU match information. */ - lzms_init_lru_queues(&ctx->lru); + lzms_init_lru_queues(&ctx->lru); LZMS_DEBUG("Decompressor successfully initialized"); } @@ -978,7 +990,7 @@ lzms_decompress(const void *compressed_data, size_t compressed_size, return -1; } - /* A LZMS-compressed data block should be evenly divisible into 16-bit + /* An LZMS-compressed data block should be evenly divisible into 16-bit * integers. */ if (compressed_size % 2 != 0) { LZMS_DEBUG("Compressed size not divisible by 2 (got %zu)", @@ -1020,7 +1032,7 @@ lzms_free_decompressor(void *_ctx) { struct lzms_decompressor *ctx = _ctx; - FREE(ctx); + ALIGNED_FREE(ctx); } static int @@ -1030,10 +1042,14 @@ lzms_create_decompressor(size_t max_block_size, { struct lzms_decompressor *ctx; - ctx = MALLOC(sizeof(struct lzms_decompressor)); + ctx = ALIGNED_MALLOC(sizeof(struct lzms_decompressor), + DECODE_TABLE_ALIGNMENT); if (ctx == NULL) return WIMLIB_ERR_NOMEM; + /* Initialize position and length slot data if not done already. */ + lzms_init_slots(); + *ctx_ret = ctx; return 0; }