204 lines · c
1/* SPDX-License-Identifier: 0BSD */2 3/*4 * LZMA2 definitions5 *6 * Authors: Lasse Collin <lasse.collin@tukaani.org>7 * Igor Pavlov <https://7-zip.org/>8 */9 10#ifndef XZ_LZMA2_H11#define XZ_LZMA2_H12 13/* Range coder constants */14#define RC_SHIFT_BITS 815#define RC_TOP_BITS 2416#define RC_TOP_VALUE (1 << RC_TOP_BITS)17#define RC_BIT_MODEL_TOTAL_BITS 1118#define RC_BIT_MODEL_TOTAL (1 << RC_BIT_MODEL_TOTAL_BITS)19#define RC_MOVE_BITS 520 21/*22 * Maximum number of position states. A position state is the lowest pb23 * number of bits of the current uncompressed offset. In some places there24 * 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 recently30 * and in which order. This information is used to predict the next symbol.31 *32 * Symbols:33 * - Literal: One 8-bit byte34 * - Match: Repeat a chunk of data at some distance35 * - Long repeat: Multi-byte match at a recently seen distance36 * - Short repeat: One-byte repeat at a recently seen distance37 *38 * The symbol names are in from STATE_oldest_older_previous. REP means39 * either short or long repeated match, and NONLIT means any non-literal.40 */41enum 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_REP54};55 56/* Total number of states */57#define STATES 1258 59/* The lowest 7 states indicate that the previous state was a literal. */60#define LIT_STATES 761 62/* Indicate that the latest symbol was a literal. */63static 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 else70 *state -= 6;71}72 73/* Indicate that the latest symbol was a match. */74static 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. */80static 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. */86static 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. */92static 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 byte99 * - 0x101-0x1FF: With match byte; match bit is 0100 * - 0x201-0x2FF: With match byte; match bit is 1101 *102 * Match byte is used when the previous LZMA symbol was something else than103 * a literal (that is, it was some kind of match).104 */105#define LITERAL_CODER_SIZE 0x300106 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 2112 113/* Match length is encoded with 4, 5, or 10 bits.114 *115 * Length Bits116 * 2-9 4 = Choice=0 + 3 bits117 * 10-17 5 = Choice=1 + Choice2=0 + 3 bits118 * 18-273 10 = Choice=1 + Choice2=1 + 8 bits119 */120#define LEN_LOW_BITS 3121#define LEN_LOW_SYMBOLS (1 << LEN_LOW_BITS)122#define LEN_MID_BITS 3123#define LEN_MID_SYMBOLS (1 << LEN_MID_BITS)124#define LEN_HIGH_BITS 8125#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 encoding130 * 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 have136 * very short match length: Lengths of 2, 3, and 4 bytes have a separate137 * set of probabilities for each length. The matches with longer length138 * use a shared set of probabilities.139 */140#define DIST_STATES 4141 142/*143 * Get the index of the appropriate probability array for decoding144 * the distance slot.145 */146static inline uint32_t lzma_get_dist_state(uint32_t len)147{148 return len < DIST_STATES + MATCH_LEN_MIN149 ? 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-bit155 * value takes 6-36 bits, larger values taking more bits.156 */157#define DIST_SLOT_BITS 6158#define DIST_SLOTS (1 << DIST_SLOT_BITS)159 160/* Match distances up to 127 are fully encoded using probabilities. Since161 * 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 the163 * distance slot itself is the same as the actual distance. DIST_MODEL_START164 * indicates the first distance slot where at least one additional bit is165 * needed.166 */167#define DIST_MODEL_START 4168 169/*170 * Match distances greater than 127 are encoded in three pieces:171 * - distance slot: the highest two bits172 * - direct bits: 2-26 bits below the highest two bits173 * - alignment bits: four lowest bits174 *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 14180 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 the187 * lowest four bits (alignment) is encoded using probabilities.188 */189#define ALIGN_BITS 4190#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 these198 * distances tends to take less space than re-encoding the actual199 * distance value.200 */201#define REPS 4202 203#endif204