linux/lib/xz/xz_lzma2.h
<<
>>
Prefs
   1/*
   2 * LZMA2 definitions
   3 *
   4 * Authors: Lasse Collin <lasse.collin@tukaani.org>
   5 *          Igor Pavlov <http://7-zip.org/>
   6 *
   7 * This file has been put into the public domain.
   8 * You can do whatever you want with this file.
   9 */
  10
  11#ifndef XZ_LZMA2_H
  12#define XZ_LZMA2_H
  13
  14/* Range coder constants */
  15#define RC_SHIFT_BITS 8
  16#define RC_TOP_BITS 24
  17#define RC_TOP_VALUE (1 << RC_TOP_BITS)
  18#define RC_BIT_MODEL_TOTAL_BITS 11
  19#define RC_BIT_MODEL_TOTAL (1 << RC_BIT_MODEL_TOTAL_BITS)
  20#define RC_MOVE_BITS 5
  21
  22/*
  23 * Maximum number of position states. A position state is the lowest pb
  24 * number of bits of the current uncompressed offset. In some places there
  25 * are different sets of probabilities for different position states.
  26 */
  27#define POS_STATES_MAX (1 << 4)
  28
  29/*
  30 * This enum is used to track which LZMA symbols have occurred most recently
  31 * and in which order. This information is used to predict the next symbol.
  32 *
  33 * Symbols:
  34 *  - Literal: One 8-bit byte
  35 *  - Match: Repeat a chunk of data at some distance
  36 *  - Long repeat: Multi-byte match at a recently seen distance
  37 *  - Short repeat: One-byte repeat at a recently seen distance
  38 *
  39 * The symbol names are in from STATE_oldest_older_previous. REP means
  40 * either short or long repeated match, and NONLIT means any non-literal.
  41 */
  42enum lzma_state {
  43        STATE_LIT_LIT,
  44        STATE_MATCH_LIT_LIT,
  45        STATE_REP_LIT_LIT,
  46        STATE_SHORTREP_LIT_LIT,
  47        STATE_MATCH_LIT,
  48        STATE_REP_LIT,
  49        STATE_SHORTREP_LIT,
  50        STATE_LIT_MATCH,
  51        STATE_LIT_LONGREP,
  52        STATE_LIT_SHORTREP,
  53        STATE_NONLIT_MATCH,
  54        STATE_NONLIT_REP
  55};
  56
  57/* Total number of states */
  58#define STATES 12
  59
  60/* The lowest 7 states indicate that the previous state was a literal. */
  61#define LIT_STATES 7
  62
  63/* Indicate that the latest symbol was a literal. */
  64static inline void lzma_state_literal(enum lzma_state *state)
  65{
  66        if (*state <= STATE_SHORTREP_LIT_LIT)
  67                *state = STATE_LIT_LIT;
  68        else if (*state <= STATE_LIT_SHORTREP)
  69                *state -= 3;
  70        else
  71                *state -= 6;
  72}
  73
  74/* Indicate that the latest symbol was a match. */
  75static inline void lzma_state_match(enum lzma_state *state)
  76{
  77        *state = *state < LIT_STATES ? STATE_LIT_MATCH : STATE_NONLIT_MATCH;
  78}
  79
  80/* Indicate that the latest state was a long repeated match. */
  81static inline void lzma_state_long_rep(enum lzma_state *state)
  82{
  83        *state = *state < LIT_STATES ? STATE_LIT_LONGREP : STATE_NONLIT_REP;
  84}
  85
  86/* Indicate that the latest symbol was a short match. */
  87static inline void lzma_state_short_rep(enum lzma_state *state)
  88{
  89        *state = *state < LIT_STATES ? STATE_LIT_SHORTREP : STATE_NONLIT_REP;
  90}
  91
  92/* Test if the previous symbol was a literal. */
  93static inline bool lzma_state_is_literal(enum lzma_state state)
  94{
  95        return state < LIT_STATES;
  96}
  97
  98/* Each literal coder is divided in three sections:
  99 *   - 0x001-0x0FF: Without match byte
 100 *   - 0x101-0x1FF: With match byte; match bit is 0
 101 *   - 0x201-0x2FF: With match byte; match bit is 1
 102 *
 103 * Match byte is used when the previous LZMA symbol was something else than
 104 * a literal (that is, it was some kind of match).
 105 */
 106#define LITERAL_CODER_SIZE 0x300
 107
 108/* Maximum number of literal coders */
 109#define LITERAL_CODERS_MAX (1 << 4)
 110
 111/* Minimum length of a match is two bytes. */
 112#define MATCH_LEN_MIN 2
 113
 114/* Match length is encoded with 4, 5, or 10 bits.
 115 *
 116 * Length   Bits
 117 *  2-9      4 = Choice=0 + 3 bits
 118 * 10-17     5 = Choice=1 + Choice2=0 + 3 bits
 119 * 18-273   10 = Choice=1 + Choice2=1 + 8 bits
 120 */
 121#define LEN_LOW_BITS 3
 122#define LEN_LOW_SYMBOLS (1 << LEN_LOW_BITS)
 123#define LEN_MID_BITS 3
 124#define LEN_MID_SYMBOLS (1 << LEN_MID_BITS)
 125#define LEN_HIGH_BITS 8
 126#define LEN_HIGH_SYMBOLS (1 << LEN_HIGH_BITS)
 127#define LEN_SYMBOLS (LEN_LOW_SYMBOLS + LEN_MID_SYMBOLS + LEN_HIGH_SYMBOLS)
 128
 129/*
 130 * Maximum length of a match is 273 which is a result of the encoding
 131 * described above.
 132 */
 133#define MATCH_LEN_MAX (MATCH_LEN_MIN + LEN_SYMBOLS - 1)
 134
 135/*
 136 * Different sets of probabilities are used for match distances that have
 137 * very short match length: Lengths of 2, 3, and 4 bytes have a separate
 138 * set of probabilities for each length. The matches with longer length
 139 * use a shared set of probabilities.
 140 */
 141#define DIST_STATES 4
 142
 143/*
 144 * Get the index of the appropriate probability array for decoding
 145 * the distance slot.
 146 */
 147static inline uint32_t lzma_get_dist_state(uint32_t len)
 148{
 149        return len < DIST_STATES + MATCH_LEN_MIN
 150                        ? len - MATCH_LEN_MIN : DIST_STATES - 1;
 151}
 152
 153/*
 154 * The highest two bits of a 32-bit match distance are encoded using six bits.
 155 * This six-bit value is called a distance slot. This way encoding a 32-bit
 156 * value takes 6-36 bits, larger values taking more bits.
 157 */
 158#define DIST_SLOT_BITS 6
 159#define DIST_SLOTS (1 << DIST_SLOT_BITS)
 160
 161/* Match distances up to 127 are fully encoded using probabilities. Since
 162 * the highest two bits (distance slot) are always encoded using six bits,
 163 * the distances 0-3 don't need any additional bits to encode, since the
 164 * distance slot itself is the same as the actual distance. DIST_MODEL_START
 165 * indicates the first distance slot where at least one additional bit is
 166 * needed.
 167 */
 168#define DIST_MODEL_START 4
 169
 170/*
 171 * Match distances greater than 127 are encoded in three pieces:
 172 *   - distance slot: the highest two bits
 173 *   - direct bits: 2-26 bits below the highest two bits
 174 *   - alignment bits: four lowest bits
 175 *
 176 * Direct bits don't use any probabilities.
 177 *
 178 * The distance slot value of 14 is for distances 128-191.
 179 */
 180#define DIST_MODEL_END 14
 181
 182/* Distance slots that indicate a distance <= 127. */
 183#define FULL_DISTANCES_BITS (DIST_MODEL_END / 2)
 184#define FULL_DISTANCES (1 << FULL_DISTANCES_BITS)
 185
 186/*
 187 * For match distances greater than 127, only the highest two bits and the
 188 * lowest four bits (alignment) is encoded using probabilities.
 189 */
 190#define ALIGN_BITS 4
 191#define ALIGN_SIZE (1 << ALIGN_BITS)
 192#define ALIGN_MASK (ALIGN_SIZE - 1)
 193
 194/* Total number of all probability variables */
 195#define PROBS_TOTAL (1846 + LITERAL_CODERS_MAX * LITERAL_CODER_SIZE)
 196
 197/*
 198 * LZMA remembers the four most recent match distances. Reusing these
 199 * distances tends to take less space than re-encoding the actual
 200 * distance value.
 201 */
 202#define REPS 4
 203
 204#endif
 205
lxr.linux.no kindly hosted by Redpill Linpro AS, provider of Linux consulting and operations services since 1995.