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 204