lz_decoder.h File Reference

LZ out window. More...

#include "common.h"

Go to the source code of this file.

Classes
struct	lzma_dict
struct	lzma_lz_options
struct	lzma_lz_decoder

Macros
#define	LZMA_LZ_DECODER_INIT

Functions
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, const void *options, lzma_lz_options *lz_options))
uint64_t	lzma_lz_decoder_memusage (size_t dictionary_size)
void	lzma_lz_decoder_uncompressed (void *coder, lzma_vli uncompressed_size)
static uint8_t	dict_get (const lzma_dict *const dict, const uint32_t distance)
	Get a byte from the history buffer. More...
static bool	dict_is_empty (const lzma_dict *const dict)
	Test if dictionary is empty. More...
static bool	dict_is_distance_valid (const lzma_dict *const dict, const size_t distance)
	Validate the match distance. More...
static bool	dict_repeat (lzma_dict *dict, uint32_t distance, uint32_t *len)
	Repeat *len bytes at distance. More...
static bool	dict_put (lzma_dict *dict, uint8_t byte)
static void	dict_write (lzma_dict *restrict dict, const uint8_t *restrict in, size_t *restrict in_pos, size_t in_size, size_t *restrict left)
	Copies arbitrary amount of data into the dictionary. More...
static void	dict_reset (lzma_dict *dict)

Detailed Description

LZ out window.

Definition in file lz_decoder.h.

Macro Definition Documentation

LZMA_LZ_DECODER_INIT

#define LZMA_LZ_DECODER_INIT

Value:

    (lzma_lz_decoder){ \
        .coder = NULL, \
        .code = NULL, \
        .reset = NULL, \
        .set_uncompressed = NULL, \
        .end = NULL, \
    }

Definition at line 74 of file lz_decoder.h.

Function Documentation

dict_get()

static uint8_t dict_get ( const lzma_dict *const  dict, const uint32_t  distance  )

inlinestatic

Get a byte from the history buffer.

Definition at line 103 of file lz_decoder.h.

{
    return dict->buf[dict->pos - distance - 1
            + (distance < dict->pos ? 0 : dict->size)];
}

References lzma_dict::buf, lzma_dict::pos, and lzma_dict::size.

Referenced by dict_repeat(), and lzma_decode().

dict_is_distance_valid()

static bool dict_is_distance_valid ( const lzma_dict *const  dict, const size_t  distance  )

inlinestatic

Validate the match distance.

Definition at line 120 of file lz_decoder.h.

{
    return dict->full > distance;
}

References lzma_dict::full.

Referenced by lzma_decode().

dict_is_empty()

static bool dict_is_empty ( const lzma_dict *const  dict )

inlinestatic

Test if dictionary is empty.

Definition at line 112 of file lz_decoder.h.

{
    return dict->full == 0;
}

References lzma_dict::full.

dict_put()

static bool dict_put ( lzma_dict *  dict, uint8_t  byte  )

inlinestatic

Puts one byte into the dictionary. Returns true if the dictionary was already full and the byte couldn't be added.

Definition at line 187 of file lz_decoder.h.

{
    if (unlikely(dict->pos == dict->limit))
        return true;
 
    dict->buf[dict->pos++] = byte;
 
    if (dict->pos > dict->full)
        dict->full = dict->pos;
 
    return false;
}

References lzma_dict::buf, lzma_dict::full, lzma_dict::limit, lzma_dict::pos, and unlikely.

Referenced by lzma_decode().

dict_repeat()

static bool dict_repeat ( lzma_dict *  dict, uint32_t  distance, uint32_t *  len  )

inlinestatic

Repeat *len bytes at distance.

Definition at line 128 of file lz_decoder.h.

{
    // Don't write past the end of the dictionary.
    const size_t dict_avail = dict->limit - dict->pos;
    uint32_t left = my_min(dict_avail, *len);
    *len -= left;
 
    // Repeat a block of data from the history. Because memcpy() is faster
    // than copying byte by byte in a loop, the copying process gets split
    // into three cases.
    if (distance < left) {
        // Source and target areas overlap, thus we can't use
        // memcpy() nor even memmove() safely.
        do {
            dict->buf[dict->pos] = dict_get(dict, distance);
            ++dict->pos;
        } while (--left > 0);
 
    } else if (distance < dict->pos) {
        // The easiest and fastest case
        memcpy(dict->buf + dict->pos,
                dict->buf + dict->pos - distance - 1,
                left);
        dict->pos += left;
 
    } else {
        // The bigger the dictionary, the more rare this
        // case occurs. We need to "wrap" the dict, thus
        // we might need two memcpy() to copy all the data.
        assert(dict->full == dict->size);
        const uint32_t copy_pos
                = dict->pos - distance - 1 + dict->size;
        uint32_t copy_size = dict->size - copy_pos;
 
        if (copy_size < left) {
            memmove(dict->buf + dict->pos, dict->buf + copy_pos,
                    copy_size);
            dict->pos += copy_size;
            copy_size = left - copy_size;
            memcpy(dict->buf + dict->pos, dict->buf, copy_size);
            dict->pos += copy_size;
        } else {
            memmove(dict->buf + dict->pos, dict->buf + copy_pos,
                    left);
            dict->pos += left;
        }
    }
 
    // Update how full the dictionary is.
    if (dict->full < dict->pos)
        dict->full = dict->pos;
 
    return unlikely(*len != 0);
}

References assert(), lzma_dict::buf, dict_get(), lzma_dict::full, len, lzma_dict::limit, memcpy(), my_min, pos, lzma_dict::pos, lzma_dict::size, and unlikely.

Referenced by lzma_decode().

dict_reset()

static void dict_reset ( lzma_dict *  dict )

inlinestatic

Definition at line 228 of file lz_decoder.h.

{
    dict->need_reset = true;
    return;
}

References lzma_dict::need_reset.

Referenced by lzma2_decode().

dict_write()

static void dict_write ( lzma_dict *restrict  dict, const uint8_t *restrict  in, size_t *restrict  in_pos, size_t  in_size, size_t *restrict  left  )

inlinestatic

Copies arbitrary amount of data into the dictionary.

Definition at line 203 of file lz_decoder.h.

{
    // NOTE: If we are being given more data than the size of the
    // dictionary, it could be possible to optimize the LZ decoder
    // so that not everything needs to go through the dictionary.
    // This shouldn't be very common thing in practice though, and
    // the slowdown of one extra memcpy() isn't bad compared to how
    // much time it would have taken if the data were compressed.
 
    if (in_size - *in_pos > *left)
        in_size = *in_pos + *left;
 
    *left -= lzma_bufcpy(in, in_pos, in_size,
            dict->buf, &dict->pos, dict->limit);
 
    if (dict->pos > dict->full)
        dict->full = dict->pos;
 
    return;
}

References in, in_pos, in_size, and lzma_bufcpy().

Referenced by lzma2_decode().

lzma_lz_decoder_init()

lzma_ret lzma_lz_decoder_init	(	lzma_next_coder *	next,
		const lzma_allocator *	allocator,
		const lzma_filter_info *	filters,
		lzma_ret(*)(lzma_lz_decoder *lz, const lzma_allocator *allocator, const void *options, lzma_lz_options *lz_options)	lz_init
	)

Definition at line 212 of file lz_decoder.c.

{
    // 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].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.
    //
    // 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 (coder->dict.size != lz_options.dict_size) {
        lzma_free(coder->dict.buf, allocator);
        coder->dict.buf
                = lzma_alloc(lz_options.dict_size, allocator);
        if (coder->dict.buf == NULL)
            return LZMA_MEM_ERROR;
 
        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(coder->dict.buf, lz_options.preset_dict + offset,
                copy_size);
        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);
}

References allocator, lzma_dict::buf, lzma_next_coder_s::code, lzma_next_coder_s::coder, lzma_coder::dict, lzma_lz_options::dict_size, lzma_next_coder_s::end, filters, lzma_dict::full, lzma_coder::lz, lz_decode(), lz_decoder_end(), lz_decoder_reset(), lzma_alloc(), lzma_free(), LZMA_LZ_DECODER_INIT, LZMA_MEM_ERROR, LZMA_NEXT_CODER_INIT, lzma_next_filter_init(), memcpy(), my_min, lzma_coder::next, lzma_coder::next_finished, NULL, lzma_filter::options, lzma_coder::pos, lzma_dict::pos, lzma_lz_options::preset_dict, lzma_lz_options::preset_dict_size, return_if_error, lzma_coder::size, lzma_dict::size, SIZE_MAX, lzma_coder::temp, and lzma_coder::this_finished.

Referenced by lzma_lzma2_decoder_init(), and lzma_lzma_decoder_init().

lzma_lz_decoder_memusage()

uint64_t lzma_lz_decoder_memusage

(

size_t

dictionary_size

)

Definition at line 300 of file lz_decoder.c.

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

Referenced by lzma_lzma_decoder_memusage_nocheck().

lzma_lz_decoder_uncompressed()

void lzma_lz_decoder_uncompressed	(	void *	coder,
		lzma_vli	uncompressed_size
	)

Definition at line 307 of file lz_decoder.c.

{
    lzma_coder *coder = coder_ptr;
    coder->lz.set_uncompressed(coder->lz.coder, uncompressed_size);
}

References lzma_lz_decoder::coder, lzma_coder::lz, lzma_lz_decoder::set_uncompressed, and uncompressed_size.

Referenced by alone_decode().