lzma_encoder_private.h File Reference

Private definitions for LZMA encoder. More...

#include "lz_encoder.h"
#include "range_encoder.h"
#include "lzma_common.h"
#include "lzma_encoder.h"

Go to the source code of this file.

Classes
struct	lzma_length_encoder
struct	lzma_optimal
struct	lzma_lzma1_encoder_s

Macros
#define	not_equal_16(a, b)    ((a)[0] != (b)[0] || (a)[1] != (b)[1])
#define	OPTS   (1 << 12)

Functions
void	lzma_lzma_optimum_fast (lzma_lzma1_encoder *restrict coder, lzma_mf *restrict mf, uint32_t *restrict back_res, uint32_t *restrict len_res)
void	lzma_lzma_optimum_normal (lzma_lzma1_encoder *restrict coder, lzma_mf *restrict mf, uint32_t *restrict back_res, uint32_t *restrict len_res, uint32_t position)

Detailed Description

Private definitions for LZMA encoder.

Definition in file lzma_encoder_private.h.

Macro Definition Documentation

not_equal_16

#define not_equal_16	(		a,
			b
	)		((a)[0] != (b)[0] || (a)[1] != (b)[1])

Definition at line 30 of file lzma_encoder_private.h.

OPTS

#define OPTS   (1 << 12)

Definition at line 36 of file lzma_encoder_private.h.

Function Documentation

lzma_lzma_optimum_fast()

void lzma_lzma_optimum_fast	(	lzma_lzma1_encoder *restrict	coder,
		lzma_mf *restrict	mf,
		uint32_t *restrict	back_res,
		uint32_t *restrict	len_res
	)

Definition at line 21 of file lzma_encoder_optimum_fast.c.

{
    const uint32_t nice_len = mf->nice_len;
 
    uint32_t len_main;
    uint32_t matches_count;
    if (mf->read_ahead == 0) {
        len_main = mf_find(mf, &matches_count, coder->matches);
    } else {
        assert(mf->read_ahead == 1);
        len_main = coder->longest_match_length;
        matches_count = coder->matches_count;
    }
 
    const uint8_t *buf = mf_ptr(mf) - 1;
    const uint32_t buf_avail = my_min(mf_avail(mf) + 1, MATCH_LEN_MAX);
 
    if (buf_avail < 2) {
        // There's not enough input left to encode a match.
        *back_res = UINT32_MAX;
        *len_res = 1;
        return;
    }
 
    // Look for repeated matches; scan the previous four match distances
    uint32_t rep_len = 0;
    uint32_t rep_index = 0;
 
    for (uint32_t i = 0; i < REPS; ++i) {
        // Pointer to the beginning of the match candidate
        const uint8_t *const buf_back = buf - coder->reps[i] - 1;
 
        // If the first two bytes (2 == MATCH_LEN_MIN) do not match,
        // this rep is not useful.
        if (not_equal_16(buf, buf_back))
            continue;
 
        // The first two bytes matched.
        // Calculate the length of the match.
        const uint32_t len = lzma_memcmplen(
                buf, buf_back, 2, buf_avail);
 
        // If we have found a repeated match that is at least
        // nice_len long, return it immediately.
        if (len >= nice_len) {
            *back_res = i;
            *len_res = len;
            mf_skip(mf, len - 1);
            return;
        }
 
        if (len > rep_len) {
            rep_index = i;
            rep_len = len;
        }
    }
 
    // We didn't find a long enough repeated match. Encode it as a normal
    // match if the match length is at least nice_len.
    if (len_main >= nice_len) {
        *back_res = coder->matches[matches_count - 1].dist + REPS;
        *len_res = len_main;
        mf_skip(mf, len_main - 1);
        return;
    }
 
    uint32_t back_main = 0;
    if (len_main >= 2) {
        back_main = coder->matches[matches_count - 1].dist;
 
        while (matches_count > 1 && len_main ==
                coder->matches[matches_count - 2].len + 1) {
            if (!change_pair(coder->matches[
                        matches_count - 2].dist,
                    back_main))
                break;
 
            --matches_count;
            len_main = coder->matches[matches_count - 1].len;
            back_main = coder->matches[matches_count - 1].dist;
        }
 
        if (len_main == 2 && back_main >= 0x80)
            len_main = 1;
    }
 
    if (rep_len >= 2) {
        if (rep_len + 1 >= len_main
                || (rep_len + 2 >= len_main
                    && back_main > (UINT32_C(1) << 9))
                || (rep_len + 3 >= len_main
                    && back_main > (UINT32_C(1) << 15))) {
            *back_res = rep_index;
            *len_res = rep_len;
            mf_skip(mf, rep_len - 1);
            return;
        }
    }
 
    if (len_main < 2 || buf_avail <= 2) {
        *back_res = UINT32_MAX;
        *len_res = 1;
        return;
    }
 
    // Get the matches for the next byte. If we find a better match,
    // the current byte is encoded as a literal.
    coder->longest_match_length = mf_find(mf,
            &coder->matches_count, coder->matches);
 
    if (coder->longest_match_length >= 2) {
        const uint32_t new_dist = coder->matches[
                coder->matches_count - 1].dist;
 
        if ((coder->longest_match_length >= len_main
                    && new_dist < back_main)
                || (coder->longest_match_length == len_main + 1
                    && !change_pair(back_main, new_dist))
                || (coder->longest_match_length > len_main + 1)
                || (coder->longest_match_length + 1 >= len_main
                    && len_main >= 3
                    && change_pair(new_dist, back_main))) {
            *back_res = UINT32_MAX;
            *len_res = 1;
            return;
        }
    }
 
    // In contrast to LZMA SDK, dictionary could not have been moved
    // between mf_find() calls, thus it is safe to just increment
    // the old buf pointer instead of recalculating it with mf_ptr().
    ++buf;
 
    const uint32_t limit = my_max(2, len_main - 1);
 
    for (uint32_t i = 0; i < REPS; ++i) {
        if (memcmp(buf, buf - coder->reps[i] - 1, limit) == 0) {
            *back_res = UINT32_MAX;
            *len_res = 1;
            return;
        }
    }
 
    *back_res = back_main + REPS;
    *len_res = len_main;
    mf_skip(mf, len_main - 2);
    return;
}

References assert(), change_pair, i, len, limit, MATCH_LEN_MAX, mf_avail(), mf_find, mf_ptr(), mf_skip(), my_max, my_min, not_equal_16, REPS, UINT32_C, and UINT32_MAX.

Referenced by lzma_lzma_encode().

lzma_lzma_optimum_normal()

void lzma_lzma_optimum_normal	(	lzma_lzma1_encoder *restrict	coder,
		lzma_mf *restrict	mf,
		uint32_t *restrict	back_res,
		uint32_t *restrict	len_res,
		uint32_t	position
	)

Definition at line 804 of file lzma_encoder_optimum_normal.c.

{
    // If we have symbols pending, return the next pending symbol.
    if (coder->opts_end_index != coder->opts_current_index) {
        assert(mf->read_ahead > 0);
        *len_res = coder->opts[coder->opts_current_index].pos_prev
                - coder->opts_current_index;
        *back_res = coder->opts[coder->opts_current_index].back_prev;
        coder->opts_current_index = coder->opts[
                coder->opts_current_index].pos_prev;
        return;
    }
 
    // Update the price tables. In LZMA SDK <= 4.60 (and possibly later)
    // this was done in both initialization function and in the main loop.
    // In liblzma they were moved into this single place.
    if (mf->read_ahead == 0) {
        if (coder->match_price_count >= (1 << 7))
            fill_dist_prices(coder);
 
        if (coder->align_price_count >= ALIGN_SIZE)
            fill_align_prices(coder);
    }
 
    // TODO: This needs quite a bit of cleaning still. But splitting
    // the original function into two pieces makes it at least a little
    // more readable, since those two parts don't share many variables.
 
    uint32_t len_end = helper1(coder, mf, back_res, len_res, position);
    if (len_end == UINT32_MAX)
        return;
 
    uint32_t reps[REPS];
    memcpy(reps, coder->reps, sizeof(reps));
 
    uint32_t cur;
    for (cur = 1; cur < len_end; ++cur) {
        assert(cur < OPTS);
 
        coder->longest_match_length = mf_find(
                mf, &coder->matches_count, coder->matches);
 
        if (coder->longest_match_length >= mf->nice_len)
            break;
 
        len_end = helper2(coder, reps, mf_ptr(mf) - 1, len_end,
                position + cur, cur, mf->nice_len,
                my_min(mf_avail(mf) + 1, OPTS - 1 - cur));
    }
 
    backward(coder, len_res, back_res, cur);
    return;
}

References ALIGN_SIZE, assert(), backward(), fill_align_prices(), fill_dist_prices(), helper1(), helper2(), memcpy(), mf_avail(), mf_find, mf_ptr(), my_min, OPTS, REPS, and UINT32_MAX.

Referenced by lzma_lzma_encode().