10578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync/* 20578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * LZMA2 definitions 30578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * 40578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * Authors: Lasse Collin <lasse.collin@tukaani.org> 50578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * Igor Pavlov <http://7-zip.org/> 60578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * 70578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * This file has been put into the public domain. 80578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * You can do whatever you want with this file. 90578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync */ 100578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync 110578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync#ifndef XZ_LZMA2_H 120578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync#define XZ_LZMA2_H 130578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync 140578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync/* Range coder constants */ 150578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync#define RC_SHIFT_BITS 8 160578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync#define RC_TOP_BITS 24 170578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync#define RC_TOP_VALUE (1 << RC_TOP_BITS) 180578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync#define RC_BIT_MODEL_TOTAL_BITS 11 190578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync#define RC_BIT_MODEL_TOTAL (1 << RC_BIT_MODEL_TOTAL_BITS) 200578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync#define RC_MOVE_BITS 5 210578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync 220578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync/* 230578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * Maximum number of position states. A position state is the lowest pb 240578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * number of bits of the current uncompressed offset. In some places there 250578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * are different sets of probabilities for different position states. 260578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync */ 270578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync#define POS_STATES_MAX (1 << 4) 280578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync 290578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync/* 300578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * This enum is used to track which LZMA symbols have occurred most recently 310578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * and in which order. This information is used to predict the next symbol. 320578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * 330578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * Symbols: 340578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * - Literal: One 8-bit byte 350578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * - Match: Repeat a chunk of data at some distance 360578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * - Long repeat: Multi-byte match at a recently seen distance 370578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * - Short repeat: One-byte repeat at a recently seen distance 380578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * 390578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * The symbol names are in from STATE_oldest_older_previous. REP means 400578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * either short or long repeated match, and NONLIT means any non-literal. 410578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync */ 420578287ba49f36d031f6d61bb53f5b54f56c65a3repo syncenum lzma_state { 430578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync STATE_LIT_LIT, 440578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync STATE_MATCH_LIT_LIT, 450578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync STATE_REP_LIT_LIT, 460578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync STATE_SHORTREP_LIT_LIT, 470578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync STATE_MATCH_LIT, 480578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync STATE_REP_LIT, 490578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync STATE_SHORTREP_LIT, 500578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync STATE_LIT_MATCH, 510578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync STATE_LIT_LONGREP, 520578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync STATE_LIT_SHORTREP, 530578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync STATE_NONLIT_MATCH, 540578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync STATE_NONLIT_REP 550578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync}; 560578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync 570578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync/* Total number of states */ 580578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync#define STATES 12 590578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync 600578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync/* The lowest 7 states indicate that the previous state was a literal. */ 610578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync#define LIT_STATES 7 620578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync 630578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync/* Indicate that the latest symbol was a literal. */ 640578287ba49f36d031f6d61bb53f5b54f56c65a3repo syncstatic inline void lzma_state_literal(enum lzma_state *state) 650578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync{ 660578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync if (*state <= STATE_SHORTREP_LIT_LIT) 670578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync *state = STATE_LIT_LIT; 680578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync else if (*state <= STATE_LIT_SHORTREP) 690578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync *state -= 3; 700578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync else 710578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync *state -= 6; 720578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync} 730578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync 740578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync/* Indicate that the latest symbol was a match. */ 750578287ba49f36d031f6d61bb53f5b54f56c65a3repo syncstatic inline void lzma_state_match(enum lzma_state *state) 760578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync{ 770578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync *state = *state < LIT_STATES ? STATE_LIT_MATCH : STATE_NONLIT_MATCH; 780578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync} 790578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync 800578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync/* Indicate that the latest state was a long repeated match. */ 810578287ba49f36d031f6d61bb53f5b54f56c65a3repo syncstatic inline void lzma_state_long_rep(enum lzma_state *state) 820578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync{ 830578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync *state = *state < LIT_STATES ? STATE_LIT_LONGREP : STATE_NONLIT_REP; 840578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync} 850578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync 860578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync/* Indicate that the latest symbol was a short match. */ 870578287ba49f36d031f6d61bb53f5b54f56c65a3repo syncstatic inline void lzma_state_short_rep(enum lzma_state *state) 880578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync{ 890578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync *state = *state < LIT_STATES ? STATE_LIT_SHORTREP : STATE_NONLIT_REP; 900578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync} 910578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync 920578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync/* Test if the previous symbol was a literal. */ 930578287ba49f36d031f6d61bb53f5b54f56c65a3repo syncstatic inline bool lzma_state_is_literal(enum lzma_state state) 940578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync{ 950578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync return state < LIT_STATES; 960578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync} 970578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync 980578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync/* Each literal coder is divided in three sections: 990578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * - 0x001-0x0FF: Without match byte 1000578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * - 0x101-0x1FF: With match byte; match bit is 0 1010578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * - 0x201-0x2FF: With match byte; match bit is 1 1020578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * 1030578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * Match byte is used when the previous LZMA symbol was something else than 1040578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * a literal (that is, it was some kind of match). 1050578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync */ 1060578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync#define LITERAL_CODER_SIZE 0x300 1070578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync 1080578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync/* Maximum number of literal coders */ 1090578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync#define LITERAL_CODERS_MAX (1 << 4) 1100578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync 1110578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync/* Minimum length of a match is two bytes. */ 1120578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync#define MATCH_LEN_MIN 2 1130578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync 1140578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync/* Match length is encoded with 4, 5, or 10 bits. 1150578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * 1160578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * Length Bits 1170578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * 2-9 4 = Choice=0 + 3 bits 1180578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * 10-17 5 = Choice=1 + Choice2=0 + 3 bits 1190578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * 18-273 10 = Choice=1 + Choice2=1 + 8 bits 1200578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync */ 1210578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync#define LEN_LOW_BITS 3 1220578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync#define LEN_LOW_SYMBOLS (1 << LEN_LOW_BITS) 1230578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync#define LEN_MID_BITS 3 1240578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync#define LEN_MID_SYMBOLS (1 << LEN_MID_BITS) 1250578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync#define LEN_HIGH_BITS 8 1260578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync#define LEN_HIGH_SYMBOLS (1 << LEN_HIGH_BITS) 1270578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync#define LEN_SYMBOLS (LEN_LOW_SYMBOLS + LEN_MID_SYMBOLS + LEN_HIGH_SYMBOLS) 1280578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync 1290578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync/* 1300578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * Maximum length of a match is 273 which is a result of the encoding 1310578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * described above. 1320578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync */ 1330578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync#define MATCH_LEN_MAX (MATCH_LEN_MIN + LEN_SYMBOLS - 1) 1340578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync 1350578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync/* 1360578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * Different sets of probabilities are used for match distances that have 1370578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * very short match length: Lengths of 2, 3, and 4 bytes have a separate 1380578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * set of probabilities for each length. The matches with longer length 1390578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * use a shared set of probabilities. 1400578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync */ 1410578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync#define DIST_STATES 4 1420578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync 1430578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync/* 1440578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * Get the index of the appropriate probability array for decoding 1450578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * the distance slot. 1460578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync */ 1470578287ba49f36d031f6d61bb53f5b54f56c65a3repo syncstatic inline uint32_t lzma_get_dist_state(uint32_t len) 1480578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync{ 1490578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync return len < DIST_STATES + MATCH_LEN_MIN 1500578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync ? len - MATCH_LEN_MIN : DIST_STATES - 1; 1510578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync} 1520578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync 1530578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync/* 1540578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * The highest two bits of a 32-bit match distance are encoded using six bits. 1550578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * This six-bit value is called a distance slot. This way encoding a 32-bit 1560578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * value takes 6-36 bits, larger values taking more bits. 1570578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync */ 1580578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync#define DIST_SLOT_BITS 6 1590578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync#define DIST_SLOTS (1 << DIST_SLOT_BITS) 1600578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync 1610578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync/* Match distances up to 127 are fully encoded using probabilities. Since 1620578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * the highest two bits (distance slot) are always encoded using six bits, 1630578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * the distances 0-3 don't need any additional bits to encode, since the 1640578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * distance slot itself is the same as the actual distance. DIST_MODEL_START 1650578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * indicates the first distance slot where at least one additional bit is 1660578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * needed. 1670578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync */ 1680578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync#define DIST_MODEL_START 4 1690578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync 1700578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync/* 1710578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * Match distances greater than 127 are encoded in three pieces: 1720578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * - distance slot: the highest two bits 1730578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * - direct bits: 2-26 bits below the highest two bits 1740578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * - alignment bits: four lowest bits 1750578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * 1760578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * Direct bits don't use any probabilities. 1770578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * 1780578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * The distance slot value of 14 is for distances 128-191. 1790578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync */ 1800578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync#define DIST_MODEL_END 14 1810578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync 1820578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync/* Distance slots that indicate a distance <= 127. */ 1830578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync#define FULL_DISTANCES_BITS (DIST_MODEL_END / 2) 1840578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync#define FULL_DISTANCES (1 << FULL_DISTANCES_BITS) 1850578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync 1860578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync/* 1870578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * For match distances greater than 127, only the highest two bits and the 1880578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * lowest four bits (alignment) is encoded using probabilities. 1890578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync */ 1900578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync#define ALIGN_BITS 4 1910578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync#define ALIGN_SIZE (1 << ALIGN_BITS) 1920578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync#define ALIGN_MASK (ALIGN_SIZE - 1) 1930578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync 1940578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync/* Total number of all probability variables */ 1950578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync#define PROBS_TOTAL (1846 + LITERAL_CODERS_MAX * LITERAL_CODER_SIZE) 1960578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync 1970578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync/* 1980578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * LZMA remembers the four most recent match distances. Reusing these 1990578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * distances tends to take less space than re-encoding the actual 2000578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync * distance value. 2010578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync */ 2020578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync#define REPS 4 2030578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync 2040578287ba49f36d031f6d61bb53f5b54f56c65a3repo sync#endif 205