1 /* 2 * LZMA2 definitions 3 * 4 * Authors: Lasse Collin <lasse.collin@tukaani.org> 5 * Igor Pavlov <https://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 */ 42 enum 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. */ 64 static 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. */ 75 static 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. */ 81 static 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. */ 87 static 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. */ 93 static 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 */ 147 static 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