lzma_common.h revision 272461
1/////////////////////////////////////////////////////////////////////////////// 2// 3/// \file lzma_common.h 4/// \brief Private definitions common to LZMA encoder and decoder 5/// 6// Authors: Igor Pavlov 7// Lasse Collin 8// 9// This file has been put into the public domain. 10// You can do whatever you want with this file. 11// 12/////////////////////////////////////////////////////////////////////////////// 13 14#ifndef LZMA_LZMA_COMMON_H 15#define LZMA_LZMA_COMMON_H 16 17#include "common.h" 18#include "range_common.h" 19 20 21/////////////////// 22// Miscellaneous // 23/////////////////// 24 25/// Maximum number of position states. A position state is the lowest pos bits 26/// number of bits of the current uncompressed offset. In some places there 27/// are different sets of probabilities for different pos states. 28#define POS_STATES_MAX (1 << LZMA_PB_MAX) 29 30 31/// Validates lc, lp, and pb. 32static inline bool 33is_lclppb_valid(const lzma_options_lzma *options) 34{ 35 return options->lc <= LZMA_LCLP_MAX && options->lp <= LZMA_LCLP_MAX 36 && options->lc + options->lp <= LZMA_LCLP_MAX 37 && options->pb <= LZMA_PB_MAX; 38} 39 40 41/////////// 42// State // 43/////////// 44 45/// This enum is used to track which events have occurred most recently and 46/// in which order. This information is used to predict the next event. 47/// 48/// Events: 49/// - Literal: One 8-bit byte 50/// - Match: Repeat a chunk of data at some distance 51/// - Long repeat: Multi-byte match at a recently seen distance 52/// - Short repeat: One-byte repeat at a recently seen distance 53/// 54/// The event names are in from STATE_oldest_older_previous. REP means 55/// either short or long repeated match, and NONLIT means any non-literal. 56typedef enum { 57 STATE_LIT_LIT, 58 STATE_MATCH_LIT_LIT, 59 STATE_REP_LIT_LIT, 60 STATE_SHORTREP_LIT_LIT, 61 STATE_MATCH_LIT, 62 STATE_REP_LIT, 63 STATE_SHORTREP_LIT, 64 STATE_LIT_MATCH, 65 STATE_LIT_LONGREP, 66 STATE_LIT_SHORTREP, 67 STATE_NONLIT_MATCH, 68 STATE_NONLIT_REP, 69} lzma_lzma_state; 70 71 72/// Total number of states 73#define STATES 12 74 75/// The lowest 7 states indicate that the previous state was a literal. 76#define LIT_STATES 7 77 78 79/// Indicate that the latest state was a literal. 80#define update_literal(state) \ 81 state = ((state) <= STATE_SHORTREP_LIT_LIT \ 82 ? STATE_LIT_LIT \ 83 : ((state) <= STATE_LIT_SHORTREP \ 84 ? (state) - 3 \ 85 : (state) - 6)) 86 87/// Indicate that the latest state was a match. 88#define update_match(state) \ 89 state = ((state) < LIT_STATES ? STATE_LIT_MATCH : STATE_NONLIT_MATCH) 90 91/// Indicate that the latest state was a long repeated match. 92#define update_long_rep(state) \ 93 state = ((state) < LIT_STATES ? STATE_LIT_LONGREP : STATE_NONLIT_REP) 94 95/// Indicate that the latest state was a short match. 96#define update_short_rep(state) \ 97 state = ((state) < LIT_STATES ? STATE_LIT_SHORTREP : STATE_NONLIT_REP) 98 99/// Test if the previous state was a literal. 100#define is_literal_state(state) \ 101 ((state) < LIT_STATES) 102 103 104///////////// 105// Literal // 106///////////// 107 108/// Each literal coder is divided in three sections: 109/// - 0x001-0x0FF: Without match byte 110/// - 0x101-0x1FF: With match byte; match bit is 0 111/// - 0x201-0x2FF: With match byte; match bit is 1 112/// 113/// Match byte is used when the previous LZMA symbol was something else than 114/// a literal (that is, it was some kind of match). 115#define LITERAL_CODER_SIZE 0x300 116 117/// Maximum number of literal coders 118#define LITERAL_CODERS_MAX (1 << LZMA_LCLP_MAX) 119 120/// Locate the literal coder for the next literal byte. The choice depends on 121/// - the lowest literal_pos_bits bits of the position of the current 122/// byte; and 123/// - the highest literal_context_bits bits of the previous byte. 124#define literal_subcoder(probs, lc, lp_mask, pos, prev_byte) \ 125 ((probs)[(((pos) & lp_mask) << lc) + ((prev_byte) >> (8 - lc))]) 126 127 128static inline void 129literal_init(probability (*probs)[LITERAL_CODER_SIZE], 130 uint32_t lc, uint32_t lp) 131{ 132 assert(lc + lp <= LZMA_LCLP_MAX); 133 134 const uint32_t coders = 1U << (lc + lp); 135 136 for (uint32_t i = 0; i < coders; ++i) 137 for (uint32_t j = 0; j < LITERAL_CODER_SIZE; ++j) 138 bit_reset(probs[i][j]); 139 140 return; 141} 142 143 144////////////////// 145// Match length // 146////////////////// 147 148// Minimum length of a match is two bytes. 149#define MATCH_LEN_MIN 2 150 151// Match length is encoded with 4, 5, or 10 bits. 152// 153// Length Bits 154// 2-9 4 = Choice=0 + 3 bits 155// 10-17 5 = Choice=1 + Choice2=0 + 3 bits 156// 18-273 10 = Choice=1 + Choice2=1 + 8 bits 157#define LEN_LOW_BITS 3 158#define LEN_LOW_SYMBOLS (1 << LEN_LOW_BITS) 159#define LEN_MID_BITS 3 160#define LEN_MID_SYMBOLS (1 << LEN_MID_BITS) 161#define LEN_HIGH_BITS 8 162#define LEN_HIGH_SYMBOLS (1 << LEN_HIGH_BITS) 163#define LEN_SYMBOLS (LEN_LOW_SYMBOLS + LEN_MID_SYMBOLS + LEN_HIGH_SYMBOLS) 164 165// Maximum length of a match is 273 which is a result of the encoding 166// described above. 167#define MATCH_LEN_MAX (MATCH_LEN_MIN + LEN_SYMBOLS - 1) 168 169 170//////////////////// 171// Match distance // 172//////////////////// 173 174// Different set of probabilities is used for match distances that have very 175// short match length: Lengths of 2, 3, and 4 bytes have a separate set of 176// probabilities for each length. The matches with longer length use a shared 177// set of probabilities. 178#define LEN_TO_POS_STATES 4 179 180// Macro to get the index of the appropriate probability array. 181#define get_len_to_pos_state(len) \ 182 ((len) < LEN_TO_POS_STATES + MATCH_LEN_MIN \ 183 ? (len) - MATCH_LEN_MIN \ 184 : LEN_TO_POS_STATES - 1) 185 186// The highest two bits of a match distance (pos slot) are encoded using six 187// bits. See fastpos.h for more explanation. 188#define POS_SLOT_BITS 6 189#define POS_SLOTS (1 << POS_SLOT_BITS) 190 191// Match distances up to 127 are fully encoded using probabilities. Since 192// the highest two bits (pos slot) are always encoded using six bits, the 193// distances 0-3 don't need any additional bits to encode, since the pos 194// slot itself is the same as the actual distance. START_POS_MODEL_INDEX 195// indicates the first pos slot where at least one additional bit is needed. 196#define START_POS_MODEL_INDEX 4 197 198// Match distances greater than 127 are encoded in three pieces: 199// - pos slot: the highest two bits 200// - direct bits: 2-26 bits below the highest two bits 201// - alignment bits: four lowest bits 202// 203// Direct bits don't use any probabilities. 204// 205// The pos slot value of 14 is for distances 128-191 (see the table in 206// fastpos.h to understand why). 207#define END_POS_MODEL_INDEX 14 208 209// Pos slots that indicate a distance <= 127. 210#define FULL_DISTANCES_BITS (END_POS_MODEL_INDEX / 2) 211#define FULL_DISTANCES (1 << FULL_DISTANCES_BITS) 212 213// For match distances greater than 127, only the highest two bits and the 214// lowest four bits (alignment) is encoded using probabilities. 215#define ALIGN_BITS 4 216#define ALIGN_TABLE_SIZE (1 << ALIGN_BITS) 217#define ALIGN_MASK (ALIGN_TABLE_SIZE - 1) 218 219// LZMA remembers the four most recent match distances. Reusing these distances 220// tends to take less space than re-encoding the actual distance value. 221#define REP_DISTANCES 4 222 223#endif 224