range_decoder.h File Reference

Range Decoder. More...

#include "range_common.h"

Go to the source code of this file.

Data Structures
struct	lzma_range_decoder

Macros
#define	LZMA_RANGE_DECODER_CONFIG   0
#define	RC_BIT_MODEL_OFFSET    ((UINT32_C(1) << RC_MOVE_BITS) - 1 - RC_BIT_MODEL_TOTAL)
#define	rc_to_local(range_decoder, in_pos, fast_mode_in_required)
#define	rc_is_fast_allowed()
	Evaluates to true if there is enough input remaining to use fast mode.
#define	rc_from_local(range_decoder, in_pos)
	Stores the local copes back to the range decoder structure.
#define	rc_reset(range_decoder)
	Resets the range decoder structure.
#define	rc_is_finished(range_decoder)
#define	rc_normalize()
#define	rc_normalize_safe(seq)
#define	rc_if_0(prob)
#define	rc_if_0_safe(prob, seq)
#define	rc_update_0(prob)
#define	rc_update_1(prob)
#define	rc_bit_last(prob, action0, action1)
#define	rc_bit_last_safe(prob, action0, action1, seq)
#define	rc_bit(prob, action0, action1)
#define	rc_bit_safe(prob, action0, action1, seq)
#define	rc_bittree_bit(prob)
#define	rc_bittree3(probs, final_add)
#define	rc_bittree6(probs, final_add)
#define	rc_bittree8(probs, final_add)
#define	rc_bittree_rev4(probs)
#define	rc_bit_add_if_1(probs, dest, value_to_add_if_1)
#define	decode_with_match_bit
#define	rc_matched_literal(probs_base_var, match_byte)
#define	rc_direct(dest, count_var)
	Decode a bit without using a probability.
#define	rc_direct_safe(dest, count_var, seq)
#define	rc_c_bit(prob, action_bit, action_neg)

Detailed Description

Range Decoder.

Macro Definition Documentation

decode_with_match_bit

#define decode_with_match_bit

Value:

        t_match_byte <<= 1; \
        t_match_bit = t_match_byte & t_offset; \
        t_subcoder_index = t_offset + t_match_bit + symbol; \
        rc_bit(probs[t_subcoder_index], \
                t_offset &= ~t_match_bit, \
                t_offset &= t_match_bit)

LZMA_RANGE_DECODER_CONFIG

#define LZMA_RANGE_DECODER_CONFIG   0

rc_bit

#define rc_bit	(		prob,
			action0,
			action1 )

Value:

    rc_bit_last(prob, \
        symbol <<= 1; action0, \
        symbol = (symbol << 1) + 1; action1);

Decodes one bit, updates "symbol", and runs action0 or action1 depending on the decoded bit.

rc_bit_add_if_1

#define rc_bit_add_if_1	(		probs,
			dest,
			value_to_add_if_1 )

Value:

    rc_bit(probs[symbol], \
        , \
        dest += value_to_add_if_1);

rc_bit_last

#define rc_bit_last	(		prob,
			action0,
			action1 )

Value:

do { \
    rc_if_0(prob) { \
        rc_update_0(prob); \
        action0; \
    } else { \
        rc_update_1(prob); \
        action1; \
    } \
} while (0)

Decodes one bit and runs action0 or action1 depending on the decoded bit. This macro is used as the last step in bittree reverse decoders since those don't use "symbol" for anything else than indexing the probability arrays.

rc_bit_last_safe

#define rc_bit_last_safe	(		prob,
			action0,
			action1,
			seq )

Value:

do { \
    rc_if_0_safe(prob, seq) { \
        rc_update_0(prob); \
        action0; \
    } else { \
        rc_update_1(prob); \
        action1; \
    } \
} while (0)

RC_BIT_MODEL_OFFSET

#define RC_BIT_MODEL_OFFSET    ((UINT32_C(1) << RC_MOVE_BITS) - 1 - RC_BIT_MODEL_TOTAL)

rc_bit_safe

#define rc_bit_safe	(		prob,
			action0,
			action1,
			seq )

Value:

    rc_bit_last_safe(prob, \
        symbol <<= 1; action0, \
        symbol = (symbol << 1) + 1; action1, \
        seq);

rc_bittree3

#define rc_bittree3	(		probs,
			final_add )

Value:

do { \
    symbol = 1; \
    rc_bittree_bit(probs[symbol]); \
    rc_bittree_bit(probs[symbol]); \
    rc_bittree_bit(probs[symbol]); \
    symbol += (uint32_t)(final_add); \
} while (0)

rc_bittree6

#define rc_bittree6	(		probs,
			final_add )

Value:

do { \
    symbol = 1; \
    rc_bittree_bit(probs[symbol]); \
    rc_bittree_bit(probs[symbol]); \
    rc_bittree_bit(probs[symbol]); \
    rc_bittree_bit(probs[symbol]); \
    rc_bittree_bit(probs[symbol]); \
    rc_bittree_bit(probs[symbol]); \
    symbol += (uint32_t)(final_add); \
} while (0)

rc_bittree8

#define rc_bittree8	(		probs,
			final_add )

Value:

do { \
    symbol = 1; \
    rc_bittree_bit(probs[symbol]); \
    rc_bittree_bit(probs[symbol]); \
    rc_bittree_bit(probs[symbol]); \
    rc_bittree_bit(probs[symbol]); \
    rc_bittree_bit(probs[symbol]); \
    rc_bittree_bit(probs[symbol]); \
    rc_bittree_bit(probs[symbol]); \
    rc_bittree_bit(probs[symbol]); \
    symbol += (uint32_t)(final_add); \
} while (0)

rc_bittree_bit

#define rc_bittree_bit

(

prob

)

Value:

    rc_bit(prob, , )

rc_bittree_rev4

#define rc_bittree_rev4

(

probs

)

Value:

do { \
    symbol = 0; \
    rc_bit_last(probs[symbol + 1], , symbol += 1); \
    rc_bit_last(probs[symbol + 2], , symbol += 2); \
    rc_bit_last(probs[symbol + 4], , symbol += 4); \
    rc_bit_last(probs[symbol + 8], , symbol += 8); \
} while (0)

rc_c_bit

#define rc_c_bit	(		prob,
			action_bit,
			action_neg )

Value:

do { \
    probability *p = &(prob); \
    rc_normalize(); \
    rc_bound = (rc.range >> RC_BIT_MODEL_TOTAL_BITS) * *p; \
    uint32_t rc_mask = rc.code >= rc_bound; /* rc_mask = decoded bit */ \
    action_bit; /* action when rc_mask is 0 or 1 */ \
    /* rc_mask becomes 0 if bit is 0 and 0xFFFFFFFF if bit is 1: */ \
    rc_mask = 0U - rc_mask; \
    rc.range &= rc_mask; /* If bit 0: set rc.range = 0 */ \
    rc_bound ^= rc_mask; \
    rc_bound -= rc_mask; /* If bit 1: rc_bound = 0U - rc_bound */ \
    rc.range += rc_bound; \
    rc_bound &= rc_mask; \
    rc.code += rc_bound; \
    action_neg; /* action when rc_mask is 0 or 0xFFFFFFFF */ \
    rc_mask = ~rc_mask; /* If bit 0: all bits are set in rc_mask */ \
    rc_mask &= RC_BIT_MODEL_OFFSET; \
    *p -= (*p + rc_mask) >> RC_MOVE_BITS; \
} while (0)

Decode a bit using a branchless method. This reduces the number of mispredicted branches and thus can improve speed.

rc_direct

#define rc_direct	(		dest,
			count_var )

Value:

do { \
    dest = (dest << 1) + 1; \
    rc_normalize(); \
    rc.range >>= 1; \
    rc.code -= rc.range; \
    rc_bound = UINT32_C(0) - (rc.code >> 31); \
    dest += rc_bound; \
    rc.code += rc.range & rc_bound; \
} while (--count_var > 0)

Decode a bit without using a probability.

rc_direct_safe

#define rc_direct_safe	(		dest,
			count_var,
			seq )

Value:

do { \
    rc_normalize_safe(seq); \
    rc.range >>= 1; \
    rc.code -= rc.range; \
    rc_bound = UINT32_C(0) - (rc.code >> 31); \
    rc.code += rc.range & rc_bound; \
    dest = (dest << 1) + (rc_bound + 1); \
} while (--count_var > 0)

rc_from_local

#define rc_from_local	(		range_decoder,
			in_pos )

Value:

do { \
    range_decoder = rc; \
    in_pos = (size_t)(rc_in_ptr - in); \
} while (0)

Stores the local copes back to the range decoder structure.

rc_if_0

#define rc_if_0

(

prob

)

Value:

    rc_normalize(); \
    rc_bound = (rc.range >> RC_BIT_MODEL_TOTAL_BITS) * (prob); \
    if (rc.code < rc_bound)

Start decoding a bit. This must be used together with rc_update_0() and rc_update_1():

rc_if_0(prob) {
    rc_update_0(prob);
    // Do something
} else {
    rc_update_1(prob);
    // Do something else
}

rc_if_0_safe

#define rc_if_0_safe	(		prob,
			seq )

Value:

    rc_normalize_safe(seq); \
    rc_bound = (rc.range >> RC_BIT_MODEL_TOTAL_BITS) * (prob); \
    if (rc.code < rc_bound)

rc_is_fast_allowed

#define rc_is_fast_allowed

(

)

Value:

(rc_in_ptr < rc_in_fast_end)

Evaluates to true if there is enough input remaining to use fast mode.

rc_is_finished

#define rc_is_finished

(

range_decoder

)

Value:

    ((range_decoder).code == 0)

When decoding has been properly finished, rc.code is always zero unless the input stream is corrupt. So checking this can catch some corrupt files especially if they don't have any other integrity check.

rc_matched_literal

#define rc_matched_literal	(		probs_base_var,
			match_byte )

Value:

do { \
    uint32_t t_match_byte = (match_byte); \
    uint32_t t_match_bit; \
    uint32_t t_subcoder_index; \
    uint32_t t_offset = 0x100; \
    symbol = 1; \
    decode_with_match_bit; \
    decode_with_match_bit; \
    decode_with_match_bit; \
    decode_with_match_bit; \
    decode_with_match_bit; \
    decode_with_match_bit; \
    decode_with_match_bit; \
    decode_with_match_bit; \
} while (0)

rc_normalize

#define rc_normalize

(

)

Value:

do { \
    if (rc.range < RC_TOP_VALUE) { \
        rc.range <<= RC_SHIFT_BITS; \
        rc.code = (rc.code << RC_SHIFT_BITS) | *rc_in_ptr++; \
    } \
} while (0)

rc_normalize_safe

#define rc_normalize_safe

(

seq

)

Value:

do { \
    if (rc.range < RC_TOP_VALUE) { \
        if (rc_in_ptr == rc_in_end) { \
            coder->sequence = seq; \
            goto out; \
        } \
        rc.range <<= RC_SHIFT_BITS; \
        rc.code = (rc.code << RC_SHIFT_BITS) | *rc_in_ptr++; \
    } \
} while (0)

If more input is needed but there is no more input available, "goto out" is used to jump out of the main decoder loop. The "_safe" macros are used in the Resumable decoder mode in order to save the sequence to continue decoding from that point later.

rc_reset

#define rc_reset

(

range_decoder

)

Value:

do { \
    (range_decoder).range = UINT32_MAX; \
    (range_decoder).code = 0; \
    (range_decoder).init_bytes_left = 5; \
} while (0)

Resets the range decoder structure.

rc_to_local

#define rc_to_local	(		range_decoder,
			in_pos,
			fast_mode_in_required )

Value:

    lzma_range_decoder rc = range_decoder; \
    const uint8_t *rc_in_ptr = in + (in_pos); \
    const uint8_t *rc_in_end = in + in_size; \
    const uint8_t *rc_in_fast_end \
            = (rc_in_end - rc_in_ptr) <= (fast_mode_in_required) \
            ? rc_in_ptr \
            : rc_in_end - (fast_mode_in_required); \
    (void)rc_in_fast_end; /* Silence a warning with HAVE_SMALL. */ \
    uint32_t rc_bound

Makes local copies of range decoder and *in_pos variables. Doing this improves speed significantly. The range decoder macros expect also variables 'in' and 'in_size' to be defined.

rc_update_0

#define rc_update_0

(

prob

)

Value:

do { \
    rc.range = rc_bound; \
    prob += (RC_BIT_MODEL_TOTAL - (prob)) >> RC_MOVE_BITS; \
    /* prob -= ((prob) + RC_BIT_MODEL_OFFSET) >> RC_MOVE_BITS; */ \
} while (0)

Update the range decoder state and the used probability variable to match a decoded bit of 0.

The x86-64 assembly uses the commented method but it seems that, at least on x86-64, the first version is slightly faster as C code.

rc_update_1

#define rc_update_1

(

prob

)

Value:

do { \
    rc.range -= rc_bound; \
    rc.code -= rc_bound; \
    prob -= (prob) >> RC_MOVE_BITS; \
} while (0)

Update the range decoder state and the used probability variable to match a decoded bit of 1.