///////////////////////////////////////////////////////////////////////////////

//

/// \file lz_decoder.c

/// \brief LZ out window

///

// Authors: Igor Pavlov

// Lasse Collin

//

// This file has been put into the public domain.

// You can do whatever you want with this file.

//

///////////////////////////////////////////////////////////////////////////////

// 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"

struct lzma_coder_s {

/// 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;

};

static void

lz_decoder_reset(lzma_coder *coder)

{

coder->dict.pos = 0;

coder->dict.full = 0;

coder->dict.buf[coder->dict.size - 1] = '\0';

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)

coder->dict.pos = 0;

// 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.

const size_t copy_size = coder->dict.pos - dict_start;

assert(copy_size <= out_size - *out_pos);

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(lzma_coder *coder,

lzma_allocator *allocator lzma_attribute((unused)),

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)

{

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(lzma_coder *coder, lzma_allocator *allocator)

{

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, lzma_allocator *allocator,

const lzma_filter_info *filters,

lzma_ret (*lz_init)(lzma_lz_decoder *lz,

lzma_allocator *allocator, const void *options,

lzma_lz_options *lz_options))

{

// Allocate the base structure if it isn't already allocated.

if (next->coder == NULL) {

next->coder = lzma_alloc(sizeof(lzma_coder), allocator);

if (next->coder == NULL)

return LZMA_MEM_ERROR;

next->code = &lz_decode;

next->end = &lz_decoder_end;

next->coder->dict.buf = NULL;

next->coder->dict.size = 0;

next->coder->lz = LZMA_LZ_DECODER_INIT;

next->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(&next->coder->lz, allocator,

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 multipe 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.

//

// Avoid integer overflow.

if (lz_options.dict_size > SIZE_MAX - 15)

return LZMA_MEM_ERROR;

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

// Allocate and initialize the dictionary.

if (next->coder->dict.size != lz_options.dict_size) {

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

next->coder->dict.buf

= lzma_alloc(lz_options.dict_size, allocator);

if (next->coder->dict.buf == NULL)

return LZMA_MEM_ERROR;

next->coder->dict.size = lz_options.dict_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(next->coder->dict.buf, lz_options.preset_dict + offset,

copy_size);

next->coder->dict.pos = copy_size;

next->coder->dict.full = copy_size;

}

// Miscellaneous initializations

next->coder->next_finished = false;

next->coder->this_finished = false;

next->coder->temp.pos = 0;

next->coder->temp.size = 0;

// Initialize the next filter in the chain, if any.

return lzma_next_filter_init(&next->coder->next, allocator,

filters + 1);

}

extern uint64_t

lzma_lz_decoder_memusage(size_t dictionary_size)

{

return sizeof(lzma_coder) + (uint64_t)(dictionary_size);

}

extern void

lzma_lz_decoder_uncompressed(lzma_coder *coder, lzma_vli uncompressed_size)

{

coder->lz.set_uncompressed(coder->lz.coder, uncompressed_size);

}