lib/xz/xz_lzma2.h

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