X-Git-Url: https://wimlib.net/git/?a=blobdiff_plain;f=src%2Flzms-decompress.c;h=532dfb59c9393f3b486c4c3661e07af283e6c951;hb=9d38cdb02481552e1f3c7f56181623b2b60fe857;hp=32ce082c29b1ebb6a5940a60619d74c7bbfe3d74;hpb=abe65b1f2f12bcedec1103cc7924897720f919be;p=wimlib diff --git a/src/lzms-decompress.c b/src/lzms-decompress.c index 32ce082c..532dfb59 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. * @@ -232,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 @@ -304,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. */ @@ -347,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]; @@ -568,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 @@ -588,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. */ @@ -659,7 +664,6 @@ static int lzms_copy_lz_match(struct lzms_decompressor *ctx, u32 length, u32 offset) { u8 *out_next; - u8 *matchptr; if (length > ctx->out_end - ctx->out_next) { LZMS_DEBUG("Match overrun!"); @@ -671,11 +675,10 @@ lzms_copy_lz_match(struct lzms_decompressor *ctx, u32 length, u32 offset) } out_next = ctx->out_next; - matchptr = out_next - offset; - while (length--) - *out_next++ = *matchptr++; - ctx->out_next = out_next; + lz_copy(out_next, length, offset, ctx->out_end); + ctx->out_next = out_next + length; + return 0; } @@ -796,7 +799,7 @@ lzms_decode_delta_match(struct lzms_decompressor *ctx) return lzms_copy_delta_match(ctx, length, power, raw_offset); } -/* Decode a LZ or delta match. */ +/* Decode an LZ or delta match. */ static int lzms_decode_match(struct lzms_decompressor *ctx) { @@ -833,7 +836,7 @@ lzms_decode_item(struct lzms_decompressor *ctx) if (ret) return ret; - lzms_update_lru_queues(&ctx->lru); + lzms_update_lru_queues(&ctx->lru); return 0; } @@ -948,7 +951,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"); } @@ -985,7 +988,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)", @@ -1027,7 +1030,7 @@ lzms_free_decompressor(void *_ctx) { struct lzms_decompressor *ctx = _ctx; - FREE(ctx); + ALIGNED_FREE(ctx); } static int @@ -1037,7 +1040,8 @@ 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;