source: vbox/trunk/src/libs/liblzma-5.8.1/lz/lz_decoder.c@ 108911

// SPDX-License-Identifier: 0BSD

///////////////////////////////////////////////////////////////////////////////
//
/// \file       lz_decoder.c
/// \brief      LZ out window
///
//  Authors:    Igor Pavlov
//              Lasse Collin
//
///////////////////////////////////////////////////////////////////////////////

// liblzma supports multiple LZ77-based filters. The LZ part is shared
// between these filters. The LZ code takes care of dictionary handling
// and passing the data between filters in the chain. The filter-specific
// part decodes from the input buffer to the dictionary.


#include "lz_decoder.h"


typedef struct {
        /// Dictionary (history buffer)
        lzma_dict dict;

        /// The actual LZ-based decoder e.g. LZMA
        lzma_lz_decoder lz;

        /// Next filter in the chain, if any. Note that LZMA and LZMA2 are
        /// only allowed as the last filter, but the long-range filter in
        /// future can be in the middle of the chain.
        lzma_next_coder next;

        /// True if the next filter in the chain has returned LZMA_STREAM_END.
        bool next_finished;

        /// True if the LZ decoder (e.g. LZMA) has detected end of payload
        /// marker. This may become true before next_finished becomes true.
        bool this_finished;

        /// Temporary buffer needed when the LZ-based filter is not the last
        /// filter in the chain. The output of the next filter is first
        /// decoded into buffer[], which is then used as input for the actual
        /// LZ-based decoder.
        struct {
                size_t pos;
                size_t size;
                uint8_t buffer[LZMA_BUFFER_SIZE];
        } temp;
} lzma_coder;


static void
lz_decoder_reset(lzma_coder *coder)
{
        coder->dict.pos = LZ_DICT_INIT_POS;
        coder->dict.full = 0;
        coder->dict.buf[LZ_DICT_INIT_POS - 1] = '\0';
        coder->dict.has_wrapped = false;
        coder->dict.need_reset = false;
        return;
}


static lzma_ret
decode_buffer(lzma_coder *coder,
                const uint8_t *restrict in, size_t *restrict in_pos,
                size_t in_size, uint8_t *restrict out,
                size_t *restrict out_pos, size_t out_size)
{
        while (true) {
                // Wrap the dictionary if needed.
                if (coder->dict.pos == coder->dict.size) {
                        // See the comment of #define LZ_DICT_REPEAT_MAX.
                        coder->dict.pos = LZ_DICT_REPEAT_MAX;
                        coder->dict.has_wrapped = true;
                        memcpy(coder->dict.buf, coder->dict.buf
                                                + coder->dict.size
                                                - LZ_DICT_REPEAT_MAX,
                                        LZ_DICT_REPEAT_MAX);
                }

                // Store the current dictionary position. It is needed to know
                // where to start copying to the out[] buffer.
                const size_t dict_start = coder->dict.pos;

                // Calculate how much we allow coder->lz.code() to decode.
                // It must not decode past the end of the dictionary
                // buffer, and we don't want it to decode more than is
                // actually needed to fill the out[] buffer.
                coder->dict.limit = coder->dict.pos
                                + my_min(out_size - *out_pos,
                                        coder->dict.size - coder->dict.pos);

                // Call the coder->lz.code() to do the actual decoding.
                const lzma_ret ret = coder->lz.code(
                                coder->lz.coder, &coder->dict,
                                in, in_pos, in_size);

                // Copy the decoded data from the dictionary to the out[]
                // buffer. Do it conditionally because out can be NULL
                // (in which case copy_size is always 0). Calling memcpy()
                // with a null-pointer is undefined even if the third
                // argument is 0.
                const size_t copy_size = coder->dict.pos - dict_start;
                assert(copy_size <= out_size - *out_pos);

                if (copy_size > 0)
                        memcpy(out + *out_pos, coder->dict.buf + dict_start,
                                        copy_size);

                *out_pos += copy_size;

                // Reset the dictionary if so requested by coder->lz.code().
                if (coder->dict.need_reset) {
                        lz_decoder_reset(coder);

                        // Since we reset dictionary, we don't check if
                        // dictionary became full.
                        if (ret != LZMA_OK || *out_pos == out_size)
                                return ret;
                } else {
                        // Return if everything got decoded or an error
                        // occurred, or if there's no more data to decode.
                        //
                        // Note that detecting if there's something to decode
                        // is done by looking if dictionary become full
                        // instead of looking if *in_pos == in_size. This
                        // is because it is possible that all the input was
                        // consumed already but some data is pending to be
                        // written to the dictionary.
                        if (ret != LZMA_OK || *out_pos == out_size
                                        || coder->dict.pos < coder->dict.size)
                                return ret;
                }
        }
}


static lzma_ret
lz_decode(void *coder_ptr, const lzma_allocator *allocator,
                const uint8_t *restrict in, size_t *restrict in_pos,
                size_t in_size, uint8_t *restrict out,
                size_t *restrict out_pos, size_t out_size,
                lzma_action action)
{
        lzma_coder *coder = coder_ptr;

        if (coder->next.code == NULL)
                return decode_buffer(coder, in, in_pos, in_size,
                                out, out_pos, out_size);

        // We aren't the last coder in the chain, we need to decode
        // our input to a temporary buffer.
        while (*out_pos < out_size) {
                // Fill the temporary buffer if it is empty.
                if (!coder->next_finished
                                && coder->temp.pos == coder->temp.size) {
                        coder->temp.pos = 0;
                        coder->temp.size = 0;

                        const lzma_ret ret = coder->next.code(
                                        coder->next.coder,
                                        allocator, in, in_pos, in_size,
                                        coder->temp.buffer, &coder->temp.size,
                                        LZMA_BUFFER_SIZE, action);

                        if (ret == LZMA_STREAM_END)
                                coder->next_finished = true;
                        else if (ret != LZMA_OK || coder->temp.size == 0)
                                return ret;
                }

                if (coder->this_finished) {
                        if (coder->temp.size != 0)
                                return LZMA_DATA_ERROR;

                        if (coder->next_finished)
                                return LZMA_STREAM_END;

                        return LZMA_OK;
                }

                const lzma_ret ret = decode_buffer(coder, coder->temp.buffer,
                                &coder->temp.pos, coder->temp.size,
                                out, out_pos, out_size);

                if (ret == LZMA_STREAM_END)
                        coder->this_finished = true;
                else if (ret != LZMA_OK)
                        return ret;
                else if (coder->next_finished && *out_pos < out_size)
                        return LZMA_DATA_ERROR;
        }

        return LZMA_OK;
}


static void
lz_decoder_end(void *coder_ptr, const lzma_allocator *allocator)
{
        lzma_coder *coder = coder_ptr;

        lzma_next_end(&coder->next, allocator);
        lzma_free(coder->dict.buf, allocator);

        if (coder->lz.end != NULL)
                coder->lz.end(coder->lz.coder, allocator);
        else
                lzma_free(coder->lz.coder, allocator);

        lzma_free(coder, allocator);
        return;
}


extern lzma_ret
lzma_lz_decoder_init(lzma_next_coder *next, const lzma_allocator *allocator,
                const lzma_filter_info *filters,
                lzma_ret (*lz_init)(lzma_lz_decoder *lz,
                        const lzma_allocator *allocator,
                        lzma_vli id, const void *options,
                        lzma_lz_options *lz_options))
{
        // Allocate the base structure if it isn't already allocated.
        lzma_coder *coder = next->coder;
        if (coder == NULL) {
                coder = lzma_alloc(sizeof(lzma_coder), allocator);
                if (coder == NULL)
                        return LZMA_MEM_ERROR;

                next->coder = coder;
                next->code = &lz_decode;
                next->end = &lz_decoder_end;

                coder->dict.buf = NULL;
                coder->dict.size = 0;
                coder->lz = LZMA_LZ_DECODER_INIT;
                coder->next = LZMA_NEXT_CODER_INIT;
        }

        // Allocate and initialize the LZ-based decoder. It will also give
        // us the dictionary size.
        lzma_lz_options lz_options;
        return_if_error(lz_init(&coder->lz, allocator,
                        filters[0].id, filters[0].options, &lz_options));

        // If the dictionary size is very small, increase it to 4096 bytes.
        // This is to prevent constant wrapping of the dictionary, which
        // would slow things down. The downside is that since we don't check
        // separately for the real dictionary size, we may happily accept
        // corrupt files.
        if (lz_options.dict_size < 4096)
                lz_options.dict_size = 4096;

        // Make dictionary size a multiple of 16. Some LZ-based decoders like
        // LZMA use the lowest bits lzma_dict.pos to know the alignment of the
        // data. Aligned buffer is also good when memcpying from the
        // dictionary to the output buffer, since applications are
        // recommended to give aligned buffers to liblzma.
        //
        // Reserve 2 * LZ_DICT_REPEAT_MAX bytes of extra space which is
        // needed for alloc_size. Reserve also LZ_DICT_EXTRA bytes of extra
        // space which is *not* counted in alloc_size or coder->dict.size.
        //
        // Avoid integer overflow.
        if (lz_options.dict_size > SIZE_MAX - 15 - 2 * LZ_DICT_REPEAT_MAX
                        - LZ_DICT_EXTRA)
                return LZMA_MEM_ERROR;

        lz_options.dict_size = (lz_options.dict_size + 15) & ~((size_t)(15));

        // Reserve extra space as explained in the comment
        // of #define LZ_DICT_REPEAT_MAX.
        const size_t alloc_size
                        = lz_options.dict_size + 2 * LZ_DICT_REPEAT_MAX;

        // Allocate and initialize the dictionary.
        if (coder->dict.size != alloc_size) {
                lzma_free(coder->dict.buf, allocator);

                // The LZ_DICT_EXTRA bytes at the end of the buffer aren't
                // included in alloc_size. These extra bytes allow
                // dict_repeat() to read and write more data than requested.
                // Otherwise this extra space is ignored.
                coder->dict.buf = lzma_alloc(alloc_size + LZ_DICT_EXTRA,
                                allocator);
                if (coder->dict.buf == NULL)
                        return LZMA_MEM_ERROR;

                // NOTE: Yes, alloc_size, not lz_options.dict_size. The way
                // coder->dict.full is updated will take care that we will
                // still reject distances larger than lz_options.dict_size.
                coder->dict.size = alloc_size;
        }

        lz_decoder_reset(next->coder);

        // Use the preset dictionary if it was given to us.
        if (lz_options.preset_dict != NULL
                        && lz_options.preset_dict_size > 0) {
                // If the preset dictionary is bigger than the actual
                // dictionary, copy only the tail.
                const size_t copy_size = my_min(lz_options.preset_dict_size,
                                lz_options.dict_size);
                const size_t offset = lz_options.preset_dict_size - copy_size;
                memcpy(coder->dict.buf + coder->dict.pos,
                                lz_options.preset_dict + offset,
                                copy_size);

                // dict.pos isn't zero after lz_decoder_reset().
                coder->dict.pos += copy_size;
                coder->dict.full = copy_size;
        }

        // Miscellaneous initializations
        coder->next_finished = false;
        coder->this_finished = false;
        coder->temp.pos = 0;
        coder->temp.size = 0;

        // Initialize the next filter in the chain, if any.
        return lzma_next_filter_init(&coder->next, allocator, filters + 1);
}


extern uint64_t
lzma_lz_decoder_memusage(size_t dictionary_size)
{
        return sizeof(lzma_coder) + (uint64_t)(dictionary_size)
                        + 2 * LZ_DICT_REPEAT_MAX + LZ_DICT_EXTRA;
}