contrib/xz/src/liblzma/lzma/lzma_common.h

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //
   3 /// \file       lzma_common.h
   4 /// \brief      Private definitions common to LZMA encoder and decoder
   5 ///
   6 //  Authors:    Igor Pavlov
   7 //              Lasse Collin
   8 //
   9 //  This file has been put into the public domain.
  10 //  You can do whatever you want with this file.
  11 //
  12 ///////////////////////////////////////////////////////////////////////////////
  13
  14 #ifndef LZMA_LZMA_COMMON_H
  15 #define LZMA_LZMA_COMMON_H
  16
  17 #include "common.h"
  18 #include "range_common.h"
  19
  20
  21 ///////////////////
  22 // Miscellaneous //
  23 ///////////////////
  24
  25 /// Maximum number of position states. A position state is the lowest pos bits
  26 /// number of bits of the current uncompressed offset. In some places there
  27 /// are different sets of probabilities for different pos states.
  28 #define POS_STATES_MAX (1 << LZMA_PB_MAX)
  29
  30
  31 /// Validates lc, lp, and pb.
  32 static inline bool
  33 is_lclppb_valid(const lzma_options_lzma *options)
  34 {
  35         return options->lc <= LZMA_LCLP_MAX && options->lp <= LZMA_LCLP_MAX
  36                         && options->lc + options->lp <= LZMA_LCLP_MAX
  37                         && options->pb <= LZMA_PB_MAX;
  38 }
  39
  40
  41 ///////////
  42 // State //
  43 ///////////
  44
  45 /// This enum is used to track which events have occurred most recently and
  46 /// in which order. This information is used to predict the next event.
  47 ///
  48 /// Events:
  49 ///  - Literal: One 8-bit byte
  50 ///  - Match: Repeat a chunk of data at some distance
  51 ///  - Long repeat: Multi-byte match at a recently seen distance
  52 ///  - Short repeat: One-byte repeat at a recently seen distance
  53 ///
  54 /// The event names are in from STATE_oldest_older_previous. REP means
  55 /// either short or long repeated match, and NONLIT means any non-literal.
  56 typedef enum {
  57         STATE_LIT_LIT,
  58         STATE_MATCH_LIT_LIT,
  59         STATE_REP_LIT_LIT,
  60         STATE_SHORTREP_LIT_LIT,
  61         STATE_MATCH_LIT,
  62         STATE_REP_LIT,
  63         STATE_SHORTREP_LIT,
  64         STATE_LIT_MATCH,
  65         STATE_LIT_LONGREP,
  66         STATE_LIT_SHORTREP,
  67         STATE_NONLIT_MATCH,
  68         STATE_NONLIT_REP,
  69 } lzma_lzma_state;
  70
  71
  72 /// Total number of states
  73 #define STATES 12
  74
  75 /// The lowest 7 states indicate that the previous state was a literal.
  76 #define LIT_STATES 7
  77
  78
  79 /// Indicate that the latest state was a literal.
  80 #define update_literal(state) \
  81         state = ((state) <= STATE_SHORTREP_LIT_LIT \
  82                         ? STATE_LIT_LIT \
  83                         : ((state) <= STATE_LIT_SHORTREP \
  84                                 ? (state) - 3 \
  85                                 : (state) - 6))
  86
  87 /// Indicate that the latest state was a match.
  88 #define update_match(state) \
  89         state = ((state) < LIT_STATES ? STATE_LIT_MATCH : STATE_NONLIT_MATCH)
  90
  91 /// Indicate that the latest state was a long repeated match.
  92 #define update_long_rep(state) \
  93         state = ((state) < LIT_STATES ? STATE_LIT_LONGREP : STATE_NONLIT_REP)
  94
  95 /// Indicate that the latest state was a short match.
  96 #define update_short_rep(state) \
  97         state = ((state) < LIT_STATES ? STATE_LIT_SHORTREP : STATE_NONLIT_REP)
  98
  99 /// Test if the previous state was a literal.
 100 #define is_literal_state(state) \
 101         ((state) < LIT_STATES)
 102
 103
 104 /////////////
 105 // Literal //
 106 /////////////
 107
 108 /// Each literal coder is divided in three sections:
 109 ///   - 0x001-0x0FF: Without match byte
 110 ///   - 0x101-0x1FF: With match byte; match bit is 0
 111 ///   - 0x201-0x2FF: With match byte; match bit is 1
 112 ///
 113 /// Match byte is used when the previous LZMA symbol was something else than
 114 /// a literal (that is, it was some kind of match).
 115 #define LITERAL_CODER_SIZE 0x300
 116
 117 /// Maximum number of literal coders
 118 #define LITERAL_CODERS_MAX (1 << LZMA_LCLP_MAX)
 119
 120 /// Locate the literal coder for the next literal byte. The choice depends on
 121 ///   - the lowest literal_pos_bits bits of the position of the current
 122 ///     byte; and
 123 ///   - the highest literal_context_bits bits of the previous byte.
 124 #define literal_subcoder(probs, lc, lp_mask, pos, prev_byte) \
 125         ((probs)[(((pos) & lp_mask) << lc) + ((prev_byte) >> (8 - lc))])
 126
 127
 128 static inline void
 129 literal_init(probability (*probs)[LITERAL_CODER_SIZE],
 130                 uint32_t lc, uint32_t lp)
 131 {
 132         assert(lc + lp <= LZMA_LCLP_MAX);
 133
 134         const uint32_t coders = 1U << (lc + lp);
 135
 136         for (uint32_t i = 0; i < coders; ++i)
 137                 for (uint32_t j = 0; j < LITERAL_CODER_SIZE; ++j)
 138                         bit_reset(probs[i][j]);
 139
 140         return;
 141 }
 142
 143
 144 //////////////////
 145 // Match length //
 146 //////////////////
 147
 148 // Minimum length of a match is two bytes.
 149 #define MATCH_LEN_MIN 2
 150
 151 // Match length is encoded with 4, 5, or 10 bits.
 152 //
 153 // Length   Bits
 154 //  2-9      4 = Choice=0 + 3 bits
 155 // 10-17     5 = Choice=1 + Choice2=0 + 3 bits
 156 // 18-273   10 = Choice=1 + Choice2=1 + 8 bits
 157 #define LEN_LOW_BITS 3
 158 #define LEN_LOW_SYMBOLS (1 << LEN_LOW_BITS)
 159 #define LEN_MID_BITS 3
 160 #define LEN_MID_SYMBOLS (1 << LEN_MID_BITS)
 161 #define LEN_HIGH_BITS 8
 162 #define LEN_HIGH_SYMBOLS (1 << LEN_HIGH_BITS)
 163 #define LEN_SYMBOLS (LEN_LOW_SYMBOLS + LEN_MID_SYMBOLS + LEN_HIGH_SYMBOLS)
 164
 165 // Maximum length of a match is 273 which is a result of the encoding
 166 // described above.
 167 #define MATCH_LEN_MAX (MATCH_LEN_MIN + LEN_SYMBOLS - 1)
 168
 169
 170 ////////////////////
 171 // Match distance //
 172 ////////////////////
 173
 174 // Different set of probabilities is used for match distances that have very
 175 // short match length: Lengths of 2, 3, and 4 bytes have a separate set of
 176 // probabilities for each length. The matches with longer length use a shared
 177 // set of probabilities.
 178 #define LEN_TO_POS_STATES 4
 179
 180 // Macro to get the index of the appropriate probability array.
 181 #define get_len_to_pos_state(len) \
 182         ((len) < LEN_TO_POS_STATES + MATCH_LEN_MIN \
 183                 ? (len) - MATCH_LEN_MIN \
 184                 : LEN_TO_POS_STATES - 1)
 185
 186 // The highest two bits of a match distance (pos slot) are encoded using six
 187 // bits. See fastpos.h for more explanation.
 188 #define POS_SLOT_BITS 6
 189 #define POS_SLOTS (1 << POS_SLOT_BITS)
 190
 191 // Match distances up to 127 are fully encoded using probabilities. Since
 192 // the highest two bits (pos slot) are always encoded using six bits, the
 193 // distances 0-3 don't need any additional bits to encode, since the pos
 194 // slot itself is the same as the actual distance. START_POS_MODEL_INDEX
 195 // indicates the first pos slot where at least one additional bit is needed.
 196 #define START_POS_MODEL_INDEX 4
 197
 198 // Match distances greater than 127 are encoded in three pieces:
 199 //   - pos slot: the highest two bits
 200 //   - direct bits: 2-26 bits below the highest two bits
 201 //   - alignment bits: four lowest bits
 202 //
 203 // Direct bits don't use any probabilities.
 204 //
 205 // The pos slot value of 14 is for distances 128-191 (see the table in
 206 // fastpos.h to understand why).
 207 #define END_POS_MODEL_INDEX 14
 208
 209 // Pos slots that indicate a distance <= 127.
 210 #define FULL_DISTANCES_BITS (END_POS_MODEL_INDEX / 2)
 211 #define FULL_DISTANCES (1 << FULL_DISTANCES_BITS)
 212
 213 // For match distances greater than 127, only the highest two bits and the
 214 // lowest four bits (alignment) is encoded using probabilities.
 215 #define ALIGN_BITS 4
 216 #define ALIGN_TABLE_SIZE (1 << ALIGN_BITS)
 217 #define ALIGN_MASK (ALIGN_TABLE_SIZE - 1)
 218
 219 // LZMA remembers the four most recent match distances. Reusing these distances
 220 // tends to take less space than re-encoding the actual distance value.
 221 #define REP_DISTANCES 4
 222
 223 #endif