lz_encoder.h File Reference

LZ in window and match finder API. More...

#include "common.h"

Go to the source code of this file.

Classes
struct	lzma_match
struct	lzma_mf_s
struct	lzma_lz_options
struct	lzma_lz_encoder

Macros
#define	mf_find   lzma_mf_find
	Since everything else begins with mf_, use it also for lzma_mf_find(). More...

Typedefs
typedef struct lzma_mf_s	lzma_mf

Functions
static const uint8_t *	mf_ptr (const lzma_mf *mf)
	Get pointer to the first byte not ran through the match finder. More...
static uint32_t	mf_avail (const lzma_mf *mf)
	Get the number of bytes that haven't been ran through the match finder yet. More...
static uint32_t	mf_unencoded (const lzma_mf *mf)
static uint32_t	mf_position (const lzma_mf *mf)
static void	mf_skip (lzma_mf *mf, uint32_t amount)
static void	mf_read (lzma_mf *mf, uint8_t *out, size_t *out_pos, size_t out_size, size_t *left)
lzma_ret	lzma_lz_encoder_init (lzma_next_coder *next, const lzma_allocator *allocator, const lzma_filter_info *filters, lzma_ret(*lz_init)(lzma_lz_encoder *lz, const lzma_allocator *allocator, const void *options, lzma_lz_options *lz_options))
uint64_t	lzma_lz_encoder_memusage (const lzma_lz_options *lz_options)
uint32_t	lzma_mf_find (lzma_mf *mf, uint32_t *count, lzma_match *matches)
	Find matches starting from the current byte. More...
uint32_t	lzma_mf_hc3_find (lzma_mf *dict, lzma_match *matches)
void	lzma_mf_hc3_skip (lzma_mf *dict, uint32_t amount)
uint32_t	lzma_mf_hc4_find (lzma_mf *dict, lzma_match *matches)
void	lzma_mf_hc4_skip (lzma_mf *dict, uint32_t amount)
uint32_t	lzma_mf_bt2_find (lzma_mf *dict, lzma_match *matches)
void	lzma_mf_bt2_skip (lzma_mf *dict, uint32_t amount)
uint32_t	lzma_mf_bt3_find (lzma_mf *dict, lzma_match *matches)
void	lzma_mf_bt3_skip (lzma_mf *dict, uint32_t amount)
uint32_t	lzma_mf_bt4_find (lzma_mf *dict, lzma_match *matches)
void	lzma_mf_bt4_skip (lzma_mf *dict, uint32_t amount)

Detailed Description

LZ in window and match finder API.

Definition in file lz_encoder.h.

Macro Definition Documentation

mf_find

#define mf_find   lzma_mf_find

Since everything else begins with mf_, use it also for lzma_mf_find().

Definition at line 259 of file lz_encoder.h.

Typedef Documentation

lzma_mf

typedef struct lzma_mf_s lzma_mf

Definition at line 1 of file lz_encoder.h.

Function Documentation

lzma_lz_encoder_init()

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

Definition at line 525 of file lz_encoder.c.

{
#ifdef HAVE_SMALL
    // We need that the CRC32 table has been initialized.
    lzma_crc32_init();
#endif
 
    // Allocate and initialize the base data structure.
    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_encode;
        next->end = &lz_encoder_end;
        next->update = &lz_encoder_update;
 
        coder->lz.coder = NULL;
        coder->lz.code = NULL;
        coder->lz.end = NULL;
 
        // mf.size is initialized to silence Valgrind
        // when used on optimized binaries (GCC may reorder
        // code in a way that Valgrind gets unhappy).
        coder->mf.buffer = NULL;
        coder->mf.size = 0;
        coder->mf.hash = NULL;
        coder->mf.son = NULL;
        coder->mf.hash_count = 0;
        coder->mf.sons_count = 0;
 
        coder->next = LZMA_NEXT_CODER_INIT;
    }
 
    // Initialize the LZ-based encoder.
    lzma_lz_options lz_options;
    return_if_error(lz_init(&coder->lz, allocator,
            filters[0].options, &lz_options));
 
    // Setup the size information into coder->mf and deallocate
    // old buffers if they have wrong size.
    if (lz_encoder_prepare(&coder->mf, allocator, &lz_options))
        return LZMA_OPTIONS_ERROR;
 
    // Allocate new buffers if needed, and do the rest of
    // the initialization.
    if (lz_encoder_init(&coder->mf, allocator, &lz_options))
        return LZMA_MEM_ERROR;
 
    // Initialize the next filter in the chain, if any.
    return lzma_next_filter_init(&coder->next, allocator, filters + 1);
}

References allocator, lzma_mf_s::buffer, lzma_next_coder_s::code, lzma_lz_decoder::code, lzma_next_coder_s::coder, lzma_lz_decoder::coder, lzma_next_coder_s::end, lzma_lz_decoder::end, filters, lzma_mf_s::hash, lzma_mf_s::hash_count, lzma_coder::lz, lz_encode(), lz_encoder_end(), lz_encoder_init(), lz_encoder_prepare(), lz_encoder_update(), lzma_alloc(), lzma_crc32_init(), LZMA_MEM_ERROR, LZMA_NEXT_CODER_INIT, lzma_next_filter_init(), LZMA_OPTIONS_ERROR, lzma_coder::mf, lzma_coder::next, NULL, lzma_filter::options, return_if_error, lzma_mf_s::size, lzma_mf_s::son, lzma_mf_s::sons_count, and lzma_next_coder_s::update.

Referenced by lzma_lzma2_encoder_init(), and lzma_lzma_encoder_init().

lzma_lz_encoder_memusage()

uint64_t lzma_lz_encoder_memusage

(

const lzma_lz_options *

lz_options

)

Definition at line 464 of file lz_encoder.c.

{
    // Old buffers must not exist when calling lz_encoder_prepare().
    lzma_mf mf = {
        .buffer = NULL,
        .hash = NULL,
        .son = NULL,
        .hash_count = 0,
        .sons_count = 0,
    };
 
    // Setup the size information into mf.
    if (lz_encoder_prepare(&mf, NULL, lz_options))
        return UINT64_MAX;
 
    // Calculate the memory usage.
    return ((uint64_t)(mf.hash_count) + mf.sons_count) * sizeof(uint32_t)
            + mf.size + sizeof(lzma_coder);
}

References lzma_mf_s::buffer, lzma_mf_s::hash_count, lz_encoder_prepare(), NULL, lzma_mf_s::size, lzma_mf_s::sons_count, and UINT64_MAX.

Referenced by lzma_lzma_encoder_memusage().

lzma_mf_bt2_find()

uint32_t lzma_mf_bt2_find	(	lzma_mf *	dict,
		lzma_match *	matches
	)

Referenced by lz_encoder_prepare().

lzma_mf_bt2_skip()

void lzma_mf_bt2_skip	(	lzma_mf *	dict,
		uint32_t	amount
	)

Referenced by lz_encoder_prepare().

lzma_mf_bt3_find()

uint32_t lzma_mf_bt3_find	(	lzma_mf *	dict,
		lzma_match *	matches
	)

Referenced by lz_encoder_prepare().

lzma_mf_bt3_skip()

void lzma_mf_bt3_skip	(	lzma_mf *	dict,
		uint32_t	amount
	)

Referenced by lz_encoder_prepare().

lzma_mf_bt4_find()

uint32_t lzma_mf_bt4_find	(	lzma_mf *	dict,
		lzma_match *	matches
	)

Referenced by lz_encoder_prepare().

lzma_mf_bt4_skip()

void lzma_mf_bt4_skip	(	lzma_mf *	dict,
		uint32_t	amount
	)

Referenced by lz_encoder_prepare().

lzma_mf_find()

uint32_t lzma_mf_find	(	lzma_mf *	mf,
		uint32_t *	count_ptr,
		lzma_match *	matches
	)

Find matches starting from the current byte.

Returns

The length of the longest match found

Definition at line 23 of file lz_encoder_mf.c.

{
    // Call the match finder. It returns the number of length-distance
    // pairs found.
    // FIXME: Minimum count is zero, what _exactly_ is the maximum?
    const uint32_t count = mf->find(mf, matches);
 
    // Length of the longest match; assume that no matches were found
    // and thus the maximum length is zero.
    uint32_t len_best = 0;
 
    if (count > 0) {
#ifndef NDEBUG
        // Validate the matches.
        for (uint32_t i = 0; i < count; ++i) {
            assert(matches[i].len <= mf->nice_len);
            assert(matches[i].dist < mf->read_pos);
            assert(memcmp(mf_ptr(mf) - 1,
                mf_ptr(mf) - matches[i].dist - 2,
                matches[i].len) == 0);
        }
#endif
 
        // The last used element in the array contains
        // the longest match.
        len_best = matches[count - 1].len;
 
        // If a match of maximum search length was found, try to
        // extend the match to maximum possible length.
        if (len_best == mf->nice_len) {
            // The limit for the match length is either the
            // maximum match length supported by the LZ-based
            // encoder or the number of bytes left in the
            // dictionary, whichever is smaller.
            uint32_t limit = mf_avail(mf) + 1;
            if (limit > mf->match_len_max)
                limit = mf->match_len_max;
 
            // Pointer to the byte we just ran through
            // the match finder.
            const uint8_t *p1 = mf_ptr(mf) - 1;
 
            // Pointer to the beginning of the match. We need -1
            // here because the match distances are zero based.
            const uint8_t *p2 = p1 - matches[count - 1].dist - 1;
 
            len_best = lzma_memcmplen(p1, p2, len_best, limit);
        }
    }
 
    *count_ptr = count;
 
    // Finally update the read position to indicate that match finder was
    // run for this dictionary offset.
    ++mf->read_ahead;
 
    return len_best;
}

References assert(), count, lzma_match::dist, lzma_mf_s::find, i, len, lzma_match::len, limit, lzma_mf_s::match_len_max, mf_avail(), mf_ptr(), lzma_mf_s::nice_len, and lzma_mf_s::read_ahead.

lzma_mf_hc3_find()

uint32_t lzma_mf_hc3_find	(	lzma_mf *	dict,
		lzma_match *	matches
	)

Referenced by lz_encoder_prepare().

lzma_mf_hc3_skip()

void lzma_mf_hc3_skip	(	lzma_mf *	dict,
		uint32_t	amount
	)

Referenced by lz_encoder_prepare().

lzma_mf_hc4_find()

uint32_t lzma_mf_hc4_find	(	lzma_mf *	dict,
		lzma_match *	matches
	)

Referenced by lz_encoder_prepare().

lzma_mf_hc4_skip()

void lzma_mf_hc4_skip	(	lzma_mf *	dict,
		uint32_t	amount
	)

Referenced by lz_encoder_prepare().

mf_avail()

static uint32_t mf_avail ( const lzma_mf *  mf )

inlinestatic

Get the number of bytes that haven't been ran through the match finder yet.

Definition at line 229 of file lz_encoder.h.

{
    return mf->write_pos - mf->read_pos;
}

References lzma_mf_s::read_pos, and lzma_mf_s::write_pos.

Referenced by helper1(), lzma_lzma_optimum_fast(), lzma_lzma_optimum_normal(), and lzma_mf_find().

mf_position()

static uint32_t mf_position ( const lzma_mf *  mf )

inlinestatic

Calculate the absolute offset from the beginning of the most recent dictionary reset. Only the lowest four bits are important, so there's no problem that we don't know the 64-bit size of the data encoded so far.

NOTE: When moving the input window, we need to do it so that the lowest bits of dict->read_pos are not modified to keep this macro working as intended.

Definition at line 252 of file lz_encoder.h.

{
    return mf->read_pos - mf->read_ahead;
}

References lzma_mf_s::read_ahead, and lzma_mf_s::read_pos.

Referenced by encode_init(), and lzma_lzma_encode().

mf_ptr()

static const uint8_t* mf_ptr ( const lzma_mf *  mf )

inlinestatic

Get pointer to the first byte not ran through the match finder.

Definition at line 221 of file lz_encoder.h.

{
    return mf->buffer + mf->read_pos;
}

References lzma_mf_s::buffer, and lzma_mf_s::read_pos.

Referenced by helper1(), lzma_lzma_optimum_fast(), lzma_lzma_optimum_normal(), and lzma_mf_find().

mf_read()

static void mf_read ( lzma_mf *  mf, uint8_t *  out, size_t *  out_pos, size_t  out_size, size_t *  left  )

inlinestatic

Copies at most *left number of bytes from the history buffer to out[]. This is needed by LZMA2 to encode uncompressed chunks.

Definition at line 279 of file lz_encoder.h.

{
    const size_t out_avail = out_size - *out_pos;
    const size_t copy_size = my_min(out_avail, *left);
 
    assert(mf->read_ahead == 0);
    assert(mf->read_pos >= *left);
 
    memcpy(out + *out_pos, mf->buffer + mf->read_pos - *left,
            copy_size);
 
    *out_pos += copy_size;
    *left -= copy_size;
    return;
}

References assert(), lzma_mf_s::buffer, memcpy(), my_min, out, out_pos, lzma_mf_s::read_ahead, and lzma_mf_s::read_pos.

Referenced by lzma2_encode().

mf_skip()

static void mf_skip ( lzma_mf *  mf, uint32_t  amount  )

inlinestatic

Skip the given number of bytes. This is used when a good match was found. For example, if mf_find() finds a match of 200 bytes long, the first byte of that match was already consumed by mf_find(), and the rest 199 bytes have to be skipped with mf_skip(mf, 199).

Definition at line 267 of file lz_encoder.h.

{
    if (amount != 0) {
        mf->skip(mf, amount);
        mf->read_ahead += amount;
    }
}

References lzma_mf_s::read_ahead, and lzma_mf_s::skip.

Referenced by encode_init(), helper1(), and lzma_lzma_optimum_fast().

mf_unencoded()

static uint32_t mf_unencoded ( const lzma_mf *  mf )

inlinestatic

Get the number of bytes that haven't been encoded yet (some of these bytes may have been ran through the match finder though).

Definition at line 238 of file lz_encoder.h.

{
    return mf->write_pos - mf->read_pos + mf->read_ahead;
}

References lzma_mf_s::read_ahead, lzma_mf_s::read_pos, and lzma_mf_s::write_pos.

Referenced by lzma2_encode().