lzma_common.h

Go to the documentation of this file.

// SPDX-License-Identifier: 0BSD
 
//
//  Authors:    Igor Pavlov
//              Lasse Collin
//
 
#ifndef LZMA_LZMA_COMMON_H
#define LZMA_LZMA_COMMON_H
 
#include "common.h"
#include "range_common.h"
 
 
// Miscellaneous //
 
#define POS_STATES_MAX (1 << LZMA_PB_MAX)
 
 
static inline bool
is_lclppb_valid(const lzma_options_lzma *options)
{
    return options->lc <= LZMA_LCLP_MAX && options->lp <= LZMA_LCLP_MAX
            && options->lc + options->lp <= LZMA_LCLP_MAX
            && options->pb <= LZMA_PB_MAX;
}
 
 
// State //
 
typedef enum {
    STATE_LIT_LIT,
    STATE_MATCH_LIT_LIT,
    STATE_REP_LIT_LIT,
    STATE_SHORTREP_LIT_LIT,
    STATE_MATCH_LIT,
    STATE_REP_LIT,
    STATE_SHORTREP_LIT,
    STATE_LIT_MATCH,
    STATE_LIT_LONGREP,
    STATE_LIT_SHORTREP,
    STATE_NONLIT_MATCH,
    STATE_NONLIT_REP,
} lzma_lzma_state;
 
 
#define STATES 12
 
#define LIT_STATES 7
 
 
#define update_literal(state) \
    state = ((state) <= STATE_SHORTREP_LIT_LIT \
            ? STATE_LIT_LIT \
            : ((state) <= STATE_LIT_SHORTREP \
                ? (state) - 3 \
                : (state) - 6))
 
#define update_literal_normal(state) \
    state = ((state) <= STATE_SHORTREP_LIT_LIT \
            ? STATE_LIT_LIT \
            : (state) - 3);
 
#define update_literal_matched(state) \
    state = ((state) <= STATE_LIT_SHORTREP \
            ? (state) - 3 \
            : (state) - 6);
 
#define update_match(state) \
    state = ((state) < LIT_STATES ? STATE_LIT_MATCH : STATE_NONLIT_MATCH)
 
#define update_long_rep(state) \
    state = ((state) < LIT_STATES ? STATE_LIT_LONGREP : STATE_NONLIT_REP)
 
#define update_short_rep(state) \
    state = ((state) < LIT_STATES ? STATE_LIT_SHORTREP : STATE_NONLIT_REP)
 
#define is_literal_state(state) \
    ((state) < LIT_STATES)
 
 
// Literal //
 
#define LITERAL_CODER_SIZE UINT32_C(0x300)
 
#define LITERAL_CODERS_MAX (1 << LZMA_LCLP_MAX)
 
#define literal_mask_calc(lc, lp) \
    ((UINT32_C(0x100) << (lp)) - (UINT32_C(0x100) >> (lc)))
 
#define literal_subcoder(probs, lc, literal_mask, pos, prev_byte) \
    ((probs) + UINT32_C(3) * \
        (((((pos) << 8) + (prev_byte)) & (literal_mask)) << (lc)))
 
 
static inline void
literal_init(probability *probs, uint32_t lc, uint32_t lp)
{
    assert(lc + lp <= LZMA_LCLP_MAX);
 
    const size_t coders = LITERAL_CODER_SIZE << (lc + lp);
 
    for (size_t i = 0; i < coders; ++i)
        bit_reset(probs[i]);
 
    return;
}
 
 
// Match length //
 
// Minimum length of a match is two bytes.
#define MATCH_LEN_MIN 2
 
// Match length is encoded with 4, 5, or 10 bits.
//
// Length   Bits
//  2-9      4 = Choice=0 + 3 bits
// 10-17     5 = Choice=1 + Choice2=0 + 3 bits
// 18-273   10 = Choice=1 + Choice2=1 + 8 bits
#define LEN_LOW_BITS 3
#define LEN_LOW_SYMBOLS (1 << LEN_LOW_BITS)
#define LEN_MID_BITS 3
#define LEN_MID_SYMBOLS (1 << LEN_MID_BITS)
#define LEN_HIGH_BITS 8
#define LEN_HIGH_SYMBOLS (1 << LEN_HIGH_BITS)
#define LEN_SYMBOLS (LEN_LOW_SYMBOLS + LEN_MID_SYMBOLS + LEN_HIGH_SYMBOLS)
 
// Maximum length of a match is 273 which is a result of the encoding
// described above.
#define MATCH_LEN_MAX (MATCH_LEN_MIN + LEN_SYMBOLS - 1)
 
 
// Match distance //
 
// Different sets of probabilities are used for match distances that have very
// short match length: Lengths of 2, 3, and 4 bytes have a separate set of
// probabilities for each length. The matches with longer length use a shared
// set of probabilities.
#define DIST_STATES 4
 
// Macro to get the index of the appropriate probability array.
#define get_dist_state(len) \
    ((len) < DIST_STATES + MATCH_LEN_MIN \
        ? (len) - MATCH_LEN_MIN \
        : DIST_STATES - 1)
 
// The highest two bits of a match distance (distance slot) are encoded
// using six bits. See fastpos.h for more explanation.
#define DIST_SLOT_BITS 6
#define DIST_SLOTS (1 << DIST_SLOT_BITS)
 
// Match distances up to 127 are fully encoded using probabilities. Since
// the highest two bits (distance slot) are always encoded using six bits,
// the distances 0-3 don't need any additional bits to encode, since the
// distance slot itself is the same as the actual distance. DIST_MODEL_START
// indicates the first distance slot where at least one additional bit is
// needed.
#define DIST_MODEL_START 4
 
// Match distances greater than 127 are encoded in three pieces:
//   - distance slot: the highest two bits
//   - direct bits: 2-26 bits below the highest two bits
//   - alignment bits: four lowest bits
//
// Direct bits don't use any probabilities.
//
// The distance slot value of 14 is for distances 128-191 (see the table in
// fastpos.h to understand why).
#define DIST_MODEL_END 14
 
// Distance slots that indicate a distance <= 127.
#define FULL_DISTANCES_BITS (DIST_MODEL_END / 2)
#define FULL_DISTANCES (1 << FULL_DISTANCES_BITS)
 
// For match distances greater than 127, only the highest two bits and the
// lowest four bits (alignment) is encoded using probabilities.
#define ALIGN_BITS 4
#define ALIGN_SIZE (1 << ALIGN_BITS)
#define ALIGN_MASK (ALIGN_SIZE - 1)
 
// LZMA remembers the four most recent match distances. Reusing these distances
// tends to take less space than re-encoding the actual distance value.
#define REPS 4
 
#endif