X-Git-Url: https://wimlib.net/git/?a=blobdiff_plain;f=src%2Flzms-decompress.c;h=43cd9acbf760887d060c63b9ad8cbfe6d7a449b6;hb=a5f0f107247cc6400c0bd25f41e49d658fd2b7d7;hp=6cc6dab326e795484ed678a3716cf06bff77efe0;hpb=67c5f2c5954d07c25f57b6d9aedb73fb3720ec0b;p=wimlib diff --git a/src/lzms-decompress.c b/src/lzms-decompress.c index 6cc6dab3..43cd9acb 100644 --- a/src/lzms-decompress.c +++ b/src/lzms-decompress.c @@ -3,22 +3,20 @@ */ /* - * Copyright (C) 2013 Eric Biggers + * Copyright (C) 2013, 2014 Eric Biggers * - * This file is part of wimlib, a library for working with WIM files. + * This file is free software; you can redistribute it and/or modify it under + * the terms of the GNU Lesser General Public License as published by the Free + * Software Foundation; either version 3 of the License, or (at your option) any + * later version. * - * wimlib is free software; you can redistribute it and/or modify it under the - * terms of the GNU General Public License as published by the Free - * Software Foundation; either version 3 of the License, or (at your option) - * any later version. - * - * wimlib is distributed in the hope that it will be useful, but WITHOUT ANY - * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR - * A PARTICULAR PURPOSE. See the GNU General Public License for more + * This file is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS + * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more * details. * - * You should have received a copy of the GNU General Public License - * along with wimlib; if not, see http://www.gnu.org/licenses/. + * You should have received a copy of the GNU Lesser General Public License + * along with this file; if not, see http://www.gnu.org/licenses/. */ /* @@ -66,11 +64,17 @@ * * 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 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 - * references to the first 3 at any given time. The queue must be initialized - * to the offsets {1, 2, 3, 4}. + * except for a quirk: inserting anything to the front of the queue must be + * delayed by one LZMS item. The reason for this is presumably that there is + * almost no reason to code the same match offset twice in a row, since you + * might as well have coded a longer match at that offset. For this same + * reason, it also is a requirement that when an offset in the queue is used, + * that offset is removed from the queue immediately (and made pending for + * front-insertion after the following decoded item), and everything to the + * right is shifted left one queue slot. This creates a need for an "overflow" + * fourth entry in the queue, even though it is only possible to decode + * references to the first 3 entries at any given time. The queue must be + * initialized to the offsets {1, 2, 3, 4}. * * Repeat delta matches are handled similarly, but for them there are two queues * updated in lock-step: one for powers and one for raw offsets. The power @@ -131,10 +135,10 @@ * 1024 symbols have been decoded with it. * * - The LZ offset code, used for decoding the offsets of standard LZ77 - * matches. Each symbol represents a position slot, which corresponds to a + * matches. Each symbol represents an offset slot, which corresponds to a * base value and some number of extra bits which must be read and added to * the base value to reconstitute the full offset. The number of symbols in - * this code is the number of position slots needed to represent all possible + * this code is the number of offset slots needed to represent all possible * offsets in the uncompressed block. This code must be rebuilt whenever * 1024 symbols have been decoded with it. * @@ -145,7 +149,7 @@ * symbols have been decoded with it. * * - The delta offset code, used for decoding the offsets of delta matches. - * Each symbol corresponds to a position slot, which corresponds to a base + * Each symbol corresponds to an offset slot, which corresponds to a base * value and some number of extra bits which must be read and added to the * base value to reconstitute the full offset. The number of symbols in this * code is equal to the number of symbols in the LZ offset code. This code @@ -160,18 +164,28 @@ * have equal frequency. Following that, each code must be rebuilt whenever a * certain number of symbols has been decoded with it. * - * In general, multiple valid Huffman codes can be constructed from a set of - * symbol frequencies. Like other compression formats such as XPRESS, LZX, and - * DEFLATE, the LZMS format solves this ambiguity by requiring that all Huffman - * codes be constructed in canonical form. This form requires that same-length - * codewords be lexicographically ordered the same way as the corresponding - * symbols and that all shorter codewords lexicographically precede longer - * codewords. + * Like other compression formats such as XPRESS, LZX, and DEFLATE, the LZMS + * format requires that all Huffman codes be constructed in canonical form. + * This form requires that same-length codewords be lexicographically ordered + * the same way as the corresponding symbols and that all shorter codewords + * lexicographically precede longer codewords. Such a code can be constructed + * directly from codeword lengths, although in LZMS this is not actually + * necessary because the codes are built using adaptive symbol frequencies. + * + * Even with the canonical code restriction, the same frequencies can be used to + * construct multiple valid Huffman codes. Therefore, the decompressor needs to + * construct the right one. Specifically, the LZMS format requires that the + * Huffman code be constructed as if the well-known priority queue algorithm is + * used and frequency ties are always broken in favor of leaf nodes. See + * make_canonical_huffman_code() in compress_common.c for more information. * - * Codewords in all the LZMS Huffman codes are limited to 15 bits. If the - * canonical code for a given set of symbol frequencies has any codewords longer - * than 15 bits, then all frequencies must be divided by 2, rounding up, and the - * code construction must be attempted again. + * Codewords in LZMS are guaranteed to not exceed 15 bits. The format otherwise + * places no restrictions on codeword length. Therefore, the Huffman code + * construction algorithm that a correct LZMS decompressor uses need not + * implement length-limited code construction. But if it does (e.g. by virtue + * of being shared among multiple compression algorithms), the details of how it + * does so are unimportant, provided that the maximum codeword length parameter + * is set to at least 15 bits. * * 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 @@ -190,10 +204,10 @@ # include "config.h" #endif -#include "wimlib.h" #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" @@ -304,7 +318,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. */ @@ -498,38 +512,15 @@ lzms_range_decode_bit(struct lzms_range_decoder *dec) /* Load the probability entry corresponding to the current state. */ prob_entry = &dec->prob_entries[dec->state]; - /* Treat the number of zero bits in the most recently decoded - * LZMS_PROBABILITY_MAX bits with this probability entry as the chance, - * out of LZMS_PROBABILITY_MAX, that the next bit will be a 0. However, - * don't allow 0% or 100% probabilities. */ - prob = prob_entry->num_recent_zero_bits; - if (prob == LZMS_PROBABILITY_MAX) - prob = LZMS_PROBABILITY_MAX - 1; - else if (prob == 0) - prob = 1; + /* Get the probability that the next bit is 0. */ + prob = lzms_get_probability(prob_entry); /* Decode the next bit. */ bit = lzms_range_decoder_raw_decode_bit(dec->rd, prob); - /* Update the state based on the newly decoded bit. */ + /* Update the state and probability entry based on the decoded bit. */ dec->state = (((dec->state << 1) | bit) & dec->mask); - - /* Update the recent bits, including the cached count of 0's. */ - BUILD_BUG_ON(LZMS_PROBABILITY_MAX > sizeof(prob_entry->recent_bits) * 8); - if (bit == 0) { - if (prob_entry->recent_bits & (1ULL << (LZMS_PROBABILITY_MAX - 1))) { - /* Replacing 1 bit with 0 bit; increment the zero count. - */ - prob_entry->num_recent_zero_bits++; - } - } else { - if (!(prob_entry->recent_bits & (1ULL << (LZMS_PROBABILITY_MAX - 1)))) { - /* Replacing 0 bit with 1 bit; decrement the zero count. - */ - prob_entry->num_recent_zero_bits--; - } - } - prob_entry->recent_bits = (prob_entry->recent_bits << 1) | bit; + lzms_update_probability_entry(prob_entry, bit); /* Return the decoded bit. */ return bit; @@ -637,8 +628,8 @@ lzms_decode_value(struct lzms_huffman_decoder *dec) 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. */ + /* Read the slot (offset slot, length slot, etc.), which is encoded as a + * Huffman symbol. */ slot = lzms_huffman_decode_symbol(dec); /* Get the number of extra bits needed to represent the range of values @@ -664,7 +655,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!"); @@ -676,11 +666,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; } @@ -879,7 +868,7 @@ lzms_init_decompressor(struct lzms_decompressor *ctx, const void *cdata, unsigned clen, void *ubuf, unsigned ulen) { - unsigned num_position_slots; + unsigned num_offset_slots; LZMS_DEBUG("Initializing decompressor (clen=%u, ulen=%u)", clen, ulen); @@ -895,11 +884,11 @@ lzms_init_decompressor(struct lzms_decompressor *ctx, * backwards) */ lzms_input_bitstream_init(&ctx->is, cdata, clen / 2); - /* Calculate the number of position slots needed for this compressed + /* Calculate the number of offset slots needed for this compressed * block. */ - num_position_slots = lzms_get_position_slot(ulen - 1) + 1; + num_offset_slots = lzms_get_offset_slot(ulen - 1) + 1; - LZMS_DEBUG("Using %u position slots", num_position_slots); + LZMS_DEBUG("Using %u offset slots", num_offset_slots); /* Initialize Huffman decoders for each alphabet used in the compressed * representation. */ @@ -908,9 +897,9 @@ lzms_init_decompressor(struct lzms_decompressor *ctx, LZMS_LITERAL_CODE_REBUILD_FREQ); lzms_init_huffman_decoder(&ctx->lz_offset_decoder, &ctx->is, - lzms_position_slot_base, - lzms_extra_position_bits, - num_position_slots, + lzms_offset_slot_base, + lzms_extra_offset_bits, + num_offset_slots, LZMS_LZ_OFFSET_CODE_REBUILD_FREQ); lzms_init_huffman_decoder(&ctx->length_decoder, &ctx->is, @@ -920,9 +909,9 @@ lzms_init_decompressor(struct lzms_decompressor *ctx, LZMS_LENGTH_CODE_REBUILD_FREQ); lzms_init_huffman_decoder(&ctx->delta_offset_decoder, &ctx->is, - lzms_position_slot_base, - lzms_extra_position_bits, - num_position_slots, + lzms_offset_slot_base, + lzms_extra_offset_bits, + num_offset_slots, LZMS_DELTA_OFFSET_CODE_REBUILD_FREQ); lzms_init_huffman_decoder(&ctx->delta_power_decoder, &ctx->is, @@ -999,21 +988,11 @@ lzms_decompress(const void *compressed_data, size_t compressed_size, } /* Handle the trivial case where nothing needs to be decompressed. - * (Necessary because a window of size 0 does not have a valid position + * (Necessary because a window of size 0 does not have a valid offset * slot.) */ if (uncompressed_size == 0) return 0; - /* The x86 post-processor requires that the uncompressed length fit into - * a signed 32-bit integer. Also, the position slot table cannot be - * searched for a position of INT32_MAX or greater. */ - if (uncompressed_size >= INT32_MAX) { - LZMS_DEBUG("Uncompressed length too large " - "(got %zu, expected < INT32_MAX)", - uncompressed_size); - return -1; - } - /* Decode the literals and matches. */ if (lzms_decode_items(compressed_data, compressed_size, uncompressed_data, uncompressed_size, ctx)) @@ -1032,21 +1011,26 @@ lzms_free_decompressor(void *_ctx) { struct lzms_decompressor *ctx = _ctx; - FREE(ctx); + ALIGNED_FREE(ctx); } static int -lzms_create_decompressor(size_t max_block_size, - const struct wimlib_decompressor_params_header *params, - void **ctx_ret) +lzms_create_decompressor(size_t max_block_size, void **ctx_ret) { struct lzms_decompressor *ctx; - ctx = MALLOC(sizeof(struct lzms_decompressor)); + /* The x86 post-processor requires that the uncompressed length fit into + * a signed 32-bit integer. Also, the offset slot table cannot be + * searched for an offset of INT32_MAX or greater. */ + if (max_block_size >= INT32_MAX) + return WIMLIB_ERR_INVALID_PARAM; + + 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. */ + /* Initialize offset and length slot data if not done already. */ lzms_init_slots(); *ctx_ret = ctx;