1229159Sadrian/* 2229159Sadrian * LZMA2 definitions 3229159Sadrian * 4229159Sadrian * Authors: Lasse Collin <lasse.collin@tukaani.org> 5229159Sadrian * Igor Pavlov <http://7-zip.org/> 6229159Sadrian * 7229159Sadrian * This file has been put into the public domain. 8229159Sadrian * You can do whatever you want with this file. 9229159Sadrian */ 10229159Sadrian 11229159Sadrian#ifndef XZ_LZMA2_H 12229159Sadrian#define XZ_LZMA2_H 13229159Sadrian 14229159Sadrian/* Range coder constants */ 15229159Sadrian#define RC_SHIFT_BITS 8 16229159Sadrian#define RC_TOP_BITS 24 17229159Sadrian#define RC_TOP_VALUE (1 << RC_TOP_BITS) 18229159Sadrian#define RC_BIT_MODEL_TOTAL_BITS 11 19229159Sadrian#define RC_BIT_MODEL_TOTAL (1 << RC_BIT_MODEL_TOTAL_BITS) 20229159Sadrian#define RC_MOVE_BITS 5 21229159Sadrian 22229159Sadrian/* 23229159Sadrian * Maximum number of position states. A position state is the lowest pb 24229159Sadrian * number of bits of the current uncompressed offset. In some places there 25229159Sadrian * are different sets of probabilities for different position states. 26229159Sadrian */ 27229159Sadrian#define POS_STATES_MAX (1 << 4) 28229159Sadrian 29229159Sadrian/* 30229159Sadrian * This enum is used to track which LZMA symbols have occurred most recently 31229159Sadrian * and in which order. This information is used to predict the next symbol. 32229159Sadrian * 33229159Sadrian * Symbols: 34229159Sadrian * - Literal: One 8-bit byte 35229159Sadrian * - Match: Repeat a chunk of data at some distance 36229159Sadrian * - Long repeat: Multi-byte match at a recently seen distance 37229159Sadrian * - Short repeat: One-byte repeat at a recently seen distance 38229159Sadrian * 39229159Sadrian * The symbol names are in from STATE_oldest_older_previous. REP means 40229159Sadrian * either short or long repeated match, and NONLIT means any non-literal. 41229159Sadrian */ 42229159Sadrianenum lzma_state { 43229159Sadrian STATE_LIT_LIT, 44229159Sadrian STATE_MATCH_LIT_LIT, 45229159Sadrian STATE_REP_LIT_LIT, 46229159Sadrian STATE_SHORTREP_LIT_LIT, 47229159Sadrian STATE_MATCH_LIT, 48229159Sadrian STATE_REP_LIT, 49229159Sadrian STATE_SHORTREP_LIT, 50229159Sadrian STATE_LIT_MATCH, 51229159Sadrian STATE_LIT_LONGREP, 52229159Sadrian STATE_LIT_SHORTREP, 53229159Sadrian STATE_NONLIT_MATCH, 54229159Sadrian STATE_NONLIT_REP 55229159Sadrian}; 56229159Sadrian 57229159Sadrian/* Total number of states */ 58229159Sadrian#define STATES 12 59229159Sadrian 60229159Sadrian/* The lowest 7 states indicate that the previous state was a literal. */ 61229159Sadrian#define LIT_STATES 7 62229159Sadrian 63229159Sadrian/* Indicate that the latest symbol was a literal. */ 64229159Sadrianstatic inline void lzma_state_literal(enum lzma_state *state) 65229159Sadrian{ 66229159Sadrian if (*state <= STATE_SHORTREP_LIT_LIT) 67229159Sadrian *state = STATE_LIT_LIT; 68229159Sadrian else if (*state <= STATE_LIT_SHORTREP) 69229159Sadrian *state -= 3; 70229159Sadrian else 71229159Sadrian *state -= 6; 72229159Sadrian} 73229159Sadrian 74229159Sadrian/* Indicate that the latest symbol was a match. */ 75229159Sadrianstatic inline void lzma_state_match(enum lzma_state *state) 76229159Sadrian{ 77229159Sadrian *state = *state < LIT_STATES ? STATE_LIT_MATCH : STATE_NONLIT_MATCH; 78229159Sadrian} 79229159Sadrian 80229159Sadrian/* Indicate that the latest state was a long repeated match. */ 81229159Sadrianstatic inline void lzma_state_long_rep(enum lzma_state *state) 82229159Sadrian{ 83229159Sadrian *state = *state < LIT_STATES ? STATE_LIT_LONGREP : STATE_NONLIT_REP; 84229159Sadrian} 85229159Sadrian 86229159Sadrian/* Indicate that the latest symbol was a short match. */ 87229159Sadrianstatic inline void lzma_state_short_rep(enum lzma_state *state) 88229159Sadrian{ 89229159Sadrian *state = *state < LIT_STATES ? STATE_LIT_SHORTREP : STATE_NONLIT_REP; 90229159Sadrian} 91229159Sadrian 92229159Sadrian/* Test if the previous symbol was a literal. */ 93229159Sadrianstatic inline bool lzma_state_is_literal(enum lzma_state state) 94229159Sadrian{ 95229159Sadrian return state < LIT_STATES; 96229159Sadrian} 97229159Sadrian 98229159Sadrian/* Each literal coder is divided in three sections: 99229159Sadrian * - 0x001-0x0FF: Without match byte 100229159Sadrian * - 0x101-0x1FF: With match byte; match bit is 0 101229159Sadrian * - 0x201-0x2FF: With match byte; match bit is 1 102229159Sadrian * 103229159Sadrian * Match byte is used when the previous LZMA symbol was something else than 104229159Sadrian * a literal (that is, it was some kind of match). 105229159Sadrian */ 106229159Sadrian#define LITERAL_CODER_SIZE 0x300 107229159Sadrian 108229159Sadrian/* Maximum number of literal coders */ 109229159Sadrian#define LITERAL_CODERS_MAX (1 << 4) 110229159Sadrian 111229159Sadrian/* Minimum length of a match is two bytes. */ 112229159Sadrian#define MATCH_LEN_MIN 2 113229159Sadrian 114229159Sadrian/* Match length is encoded with 4, 5, or 10 bits. 115229159Sadrian * 116229159Sadrian * Length Bits 117229159Sadrian * 2-9 4 = Choice=0 + 3 bits 118229159Sadrian * 10-17 5 = Choice=1 + Choice2=0 + 3 bits 119229159Sadrian * 18-273 10 = Choice=1 + Choice2=1 + 8 bits 120229159Sadrian */ 121229159Sadrian#define LEN_LOW_BITS 3 122229159Sadrian#define LEN_LOW_SYMBOLS (1 << LEN_LOW_BITS) 123229159Sadrian#define LEN_MID_BITS 3 124229159Sadrian#define LEN_MID_SYMBOLS (1 << LEN_MID_BITS) 125229159Sadrian#define LEN_HIGH_BITS 8 126229159Sadrian#define LEN_HIGH_SYMBOLS (1 << LEN_HIGH_BITS) 127229159Sadrian#define LEN_SYMBOLS (LEN_LOW_SYMBOLS + LEN_MID_SYMBOLS + LEN_HIGH_SYMBOLS) 128229159Sadrian 129229159Sadrian/* 130229159Sadrian * Maximum length of a match is 273 which is a result of the encoding 131229159Sadrian * described above. 132229159Sadrian */ 133229159Sadrian#define MATCH_LEN_MAX (MATCH_LEN_MIN + LEN_SYMBOLS - 1) 134229159Sadrian 135229159Sadrian/* 136229159Sadrian * Different sets of probabilities are used for match distances that have 137229159Sadrian * very short match length: Lengths of 2, 3, and 4 bytes have a separate 138229159Sadrian * set of probabilities for each length. The matches with longer length 139229159Sadrian * use a shared set of probabilities. 140229159Sadrian */ 141229159Sadrian#define DIST_STATES 4 142229159Sadrian 143229159Sadrian/* 144229159Sadrian * Get the index of the appropriate probability array for decoding 145229159Sadrian * the distance slot. 146229159Sadrian */ 147229159Sadrianstatic inline uint32_t lzma_get_dist_state(uint32_t len) 148229159Sadrian{ 149229159Sadrian return len < DIST_STATES + MATCH_LEN_MIN 150229159Sadrian ? len - MATCH_LEN_MIN : DIST_STATES - 1; 151229159Sadrian} 152229159Sadrian 153229159Sadrian/* 154229159Sadrian * The highest two bits of a 32-bit match distance are encoded using six bits. 155229159Sadrian * This six-bit value is called a distance slot. This way encoding a 32-bit 156229159Sadrian * value takes 6-36 bits, larger values taking more bits. 157229159Sadrian */ 158229159Sadrian#define DIST_SLOT_BITS 6 159229159Sadrian#define DIST_SLOTS (1 << DIST_SLOT_BITS) 160229159Sadrian 161229159Sadrian/* Match distances up to 127 are fully encoded using probabilities. Since 162229159Sadrian * the highest two bits (distance slot) are always encoded using six bits, 163229159Sadrian * the distances 0-3 don't need any additional bits to encode, since the 164229159Sadrian * distance slot itself is the same as the actual distance. DIST_MODEL_START 165229159Sadrian * indicates the first distance slot where at least one additional bit is 166229159Sadrian * needed. 167229159Sadrian */ 168229159Sadrian#define DIST_MODEL_START 4 169229159Sadrian 170229159Sadrian/* 171229159Sadrian * Match distances greater than 127 are encoded in three pieces: 172229159Sadrian * - distance slot: the highest two bits 173229159Sadrian * - direct bits: 2-26 bits below the highest two bits 174229159Sadrian * - alignment bits: four lowest bits 175229159Sadrian * 176229159Sadrian * Direct bits don't use any probabilities. 177229159Sadrian * 178229159Sadrian * The distance slot value of 14 is for distances 128-191. 179229159Sadrian */ 180229159Sadrian#define DIST_MODEL_END 14 181229159Sadrian 182229159Sadrian/* Distance slots that indicate a distance <= 127. */ 183229159Sadrian#define FULL_DISTANCES_BITS (DIST_MODEL_END / 2) 184229159Sadrian#define FULL_DISTANCES (1 << FULL_DISTANCES_BITS) 185229159Sadrian 186229159Sadrian/* 187229159Sadrian * For match distances greater than 127, only the highest two bits and the 188229159Sadrian * lowest four bits (alignment) is encoded using probabilities. 189229159Sadrian */ 190229159Sadrian#define ALIGN_BITS 4 191229159Sadrian#define ALIGN_SIZE (1 << ALIGN_BITS) 192229159Sadrian#define ALIGN_MASK (ALIGN_SIZE - 1) 193229159Sadrian 194229159Sadrian/* Total number of all probability variables */ 195229159Sadrian#define PROBS_TOTAL (1846 + LITERAL_CODERS_MAX * LITERAL_CODER_SIZE) 196229159Sadrian 197229159Sadrian/* 198229159Sadrian * LZMA remembers the four most recent match distances. Reusing these 199229159Sadrian * distances tends to take less space than re-encoding the actual 200229159Sadrian * distance value. 201229159Sadrian */ 202229159Sadrian#define REPS 4 203229159Sadrian 204229159Sadrian#endif 205