1207753Smm/////////////////////////////////////////////////////////////////////////////// 2207753Smm// 3207753Smm/// \file lzma_common.h 4207753Smm/// \brief Private definitions common to LZMA encoder and decoder 5207753Smm/// 6207753Smm// Authors: Igor Pavlov 7207753Smm// Lasse Collin 8207753Smm// 9207753Smm// This file has been put into the public domain. 10207753Smm// You can do whatever you want with this file. 11207753Smm// 12207753Smm/////////////////////////////////////////////////////////////////////////////// 13207753Smm 14207753Smm#ifndef LZMA_LZMA_COMMON_H 15207753Smm#define LZMA_LZMA_COMMON_H 16207753Smm 17207753Smm#include "common.h" 18207753Smm#include "range_common.h" 19207753Smm 20207753Smm 21207753Smm/////////////////// 22207753Smm// Miscellaneous // 23207753Smm/////////////////// 24207753Smm 25207753Smm/// Maximum number of position states. A position state is the lowest pos bits 26207753Smm/// number of bits of the current uncompressed offset. In some places there 27207753Smm/// are different sets of probabilities for different pos states. 28207753Smm#define POS_STATES_MAX (1 << LZMA_PB_MAX) 29207753Smm 30207753Smm 31207753Smm/// Validates lc, lp, and pb. 32207753Smmstatic inline bool 33207753Smmis_lclppb_valid(const lzma_options_lzma *options) 34207753Smm{ 35207753Smm return options->lc <= LZMA_LCLP_MAX && options->lp <= LZMA_LCLP_MAX 36207753Smm && options->lc + options->lp <= LZMA_LCLP_MAX 37207753Smm && options->pb <= LZMA_PB_MAX; 38207753Smm} 39207753Smm 40207753Smm 41207753Smm/////////// 42207753Smm// State // 43207753Smm/////////// 44207753Smm 45207753Smm/// This enum is used to track which events have occurred most recently and 46207753Smm/// in which order. This information is used to predict the next event. 47207753Smm/// 48207753Smm/// Events: 49207753Smm/// - Literal: One 8-bit byte 50207753Smm/// - Match: Repeat a chunk of data at some distance 51207753Smm/// - Long repeat: Multi-byte match at a recently seen distance 52207753Smm/// - Short repeat: One-byte repeat at a recently seen distance 53207753Smm/// 54207753Smm/// The event names are in from STATE_oldest_older_previous. REP means 55207753Smm/// either short or long repeated match, and NONLIT means any non-literal. 56207753Smmtypedef enum { 57207753Smm STATE_LIT_LIT, 58207753Smm STATE_MATCH_LIT_LIT, 59207753Smm STATE_REP_LIT_LIT, 60207753Smm STATE_SHORTREP_LIT_LIT, 61207753Smm STATE_MATCH_LIT, 62207753Smm STATE_REP_LIT, 63207753Smm STATE_SHORTREP_LIT, 64207753Smm STATE_LIT_MATCH, 65207753Smm STATE_LIT_LONGREP, 66207753Smm STATE_LIT_SHORTREP, 67207753Smm STATE_NONLIT_MATCH, 68207753Smm STATE_NONLIT_REP, 69207753Smm} lzma_lzma_state; 70207753Smm 71207753Smm 72207753Smm/// Total number of states 73207753Smm#define STATES 12 74207753Smm 75207753Smm/// The lowest 7 states indicate that the previous state was a literal. 76207753Smm#define LIT_STATES 7 77207753Smm 78207753Smm 79207753Smm/// Indicate that the latest state was a literal. 80207753Smm#define update_literal(state) \ 81207753Smm state = ((state) <= STATE_SHORTREP_LIT_LIT \ 82207753Smm ? STATE_LIT_LIT \ 83207753Smm : ((state) <= STATE_LIT_SHORTREP \ 84207753Smm ? (state) - 3 \ 85207753Smm : (state) - 6)) 86207753Smm 87207753Smm/// Indicate that the latest state was a match. 88207753Smm#define update_match(state) \ 89207753Smm state = ((state) < LIT_STATES ? STATE_LIT_MATCH : STATE_NONLIT_MATCH) 90207753Smm 91207753Smm/// Indicate that the latest state was a long repeated match. 92207753Smm#define update_long_rep(state) \ 93207753Smm state = ((state) < LIT_STATES ? STATE_LIT_LONGREP : STATE_NONLIT_REP) 94207753Smm 95207753Smm/// Indicate that the latest state was a short match. 96207753Smm#define update_short_rep(state) \ 97207753Smm state = ((state) < LIT_STATES ? STATE_LIT_SHORTREP : STATE_NONLIT_REP) 98207753Smm 99207753Smm/// Test if the previous state was a literal. 100207753Smm#define is_literal_state(state) \ 101207753Smm ((state) < LIT_STATES) 102207753Smm 103207753Smm 104207753Smm///////////// 105207753Smm// Literal // 106207753Smm///////////// 107207753Smm 108207753Smm/// Each literal coder is divided in three sections: 109207753Smm/// - 0x001-0x0FF: Without match byte 110207753Smm/// - 0x101-0x1FF: With match byte; match bit is 0 111207753Smm/// - 0x201-0x2FF: With match byte; match bit is 1 112207753Smm/// 113207753Smm/// Match byte is used when the previous LZMA symbol was something else than 114207753Smm/// a literal (that is, it was some kind of match). 115207753Smm#define LITERAL_CODER_SIZE 0x300 116207753Smm 117207753Smm/// Maximum number of literal coders 118207753Smm#define LITERAL_CODERS_MAX (1 << LZMA_LCLP_MAX) 119207753Smm 120207753Smm/// Locate the literal coder for the next literal byte. The choice depends on 121207753Smm/// - the lowest literal_pos_bits bits of the position of the current 122207753Smm/// byte; and 123207753Smm/// - the highest literal_context_bits bits of the previous byte. 124207753Smm#define literal_subcoder(probs, lc, lp_mask, pos, prev_byte) \ 125207753Smm ((probs)[(((pos) & lp_mask) << lc) + ((prev_byte) >> (8 - lc))]) 126207753Smm 127207753Smm 128207753Smmstatic inline void 129207753Smmliteral_init(probability (*probs)[LITERAL_CODER_SIZE], 130207753Smm uint32_t lc, uint32_t lp) 131207753Smm{ 132207753Smm assert(lc + lp <= LZMA_LCLP_MAX); 133207753Smm 134207753Smm const uint32_t coders = 1U << (lc + lp); 135207753Smm 136207753Smm for (uint32_t i = 0; i < coders; ++i) 137207753Smm for (uint32_t j = 0; j < LITERAL_CODER_SIZE; ++j) 138207753Smm bit_reset(probs[i][j]); 139207753Smm 140207753Smm return; 141207753Smm} 142207753Smm 143207753Smm 144207753Smm////////////////// 145207753Smm// Match length // 146207753Smm////////////////// 147207753Smm 148207753Smm// Minimum length of a match is two bytes. 149207753Smm#define MATCH_LEN_MIN 2 150207753Smm 151207753Smm// Match length is encoded with 4, 5, or 10 bits. 152207753Smm// 153207753Smm// Length Bits 154207753Smm// 2-9 4 = Choice=0 + 3 bits 155207753Smm// 10-17 5 = Choice=1 + Choice2=0 + 3 bits 156207753Smm// 18-273 10 = Choice=1 + Choice2=1 + 8 bits 157207753Smm#define LEN_LOW_BITS 3 158207753Smm#define LEN_LOW_SYMBOLS (1 << LEN_LOW_BITS) 159207753Smm#define LEN_MID_BITS 3 160207753Smm#define LEN_MID_SYMBOLS (1 << LEN_MID_BITS) 161207753Smm#define LEN_HIGH_BITS 8 162207753Smm#define LEN_HIGH_SYMBOLS (1 << LEN_HIGH_BITS) 163207753Smm#define LEN_SYMBOLS (LEN_LOW_SYMBOLS + LEN_MID_SYMBOLS + LEN_HIGH_SYMBOLS) 164207753Smm 165207753Smm// Maximum length of a match is 273 which is a result of the encoding 166207753Smm// described above. 167207753Smm#define MATCH_LEN_MAX (MATCH_LEN_MIN + LEN_SYMBOLS - 1) 168207753Smm 169207753Smm 170207753Smm//////////////////// 171207753Smm// Match distance // 172207753Smm//////////////////// 173207753Smm 174207753Smm// Different set of probabilities is used for match distances that have very 175207753Smm// short match length: Lengths of 2, 3, and 4 bytes have a separate set of 176207753Smm// probabilities for each length. The matches with longer length use a shared 177207753Smm// set of probabilities. 178207753Smm#define LEN_TO_POS_STATES 4 179207753Smm 180207753Smm// Macro to get the index of the appropriate probability array. 181207753Smm#define get_len_to_pos_state(len) \ 182207753Smm ((len) < LEN_TO_POS_STATES + MATCH_LEN_MIN \ 183207753Smm ? (len) - MATCH_LEN_MIN \ 184207753Smm : LEN_TO_POS_STATES - 1) 185207753Smm 186207753Smm// The highest two bits of a match distance (pos slot) are encoded using six 187207753Smm// bits. See fastpos.h for more explanation. 188207753Smm#define POS_SLOT_BITS 6 189207753Smm#define POS_SLOTS (1 << POS_SLOT_BITS) 190207753Smm 191207753Smm// Match distances up to 127 are fully encoded using probabilities. Since 192207753Smm// the highest two bits (pos slot) are always encoded using six bits, the 193207753Smm// distances 0-3 don't need any additional bits to encode, since the pos 194207753Smm// slot itself is the same as the actual distance. START_POS_MODEL_INDEX 195207753Smm// indicates the first pos slot where at least one additional bit is needed. 196207753Smm#define START_POS_MODEL_INDEX 4 197207753Smm 198207753Smm// Match distances greater than 127 are encoded in three pieces: 199207753Smm// - pos slot: the highest two bits 200207753Smm// - direct bits: 2-26 bits below the highest two bits 201207753Smm// - alignment bits: four lowest bits 202207753Smm// 203207753Smm// Direct bits don't use any probabilities. 204207753Smm// 205207753Smm// The pos slot value of 14 is for distances 128-191 (see the table in 206207753Smm// fastpos.h to understand why). 207207753Smm#define END_POS_MODEL_INDEX 14 208207753Smm 209207753Smm// Pos slots that indicate a distance <= 127. 210207753Smm#define FULL_DISTANCES_BITS (END_POS_MODEL_INDEX / 2) 211207753Smm#define FULL_DISTANCES (1 << FULL_DISTANCES_BITS) 212207753Smm 213207753Smm// For match distances greater than 127, only the highest two bits and the 214207753Smm// lowest four bits (alignment) is encoded using probabilities. 215207753Smm#define ALIGN_BITS 4 216207753Smm#define ALIGN_TABLE_SIZE (1 << ALIGN_BITS) 217207753Smm#define ALIGN_MASK (ALIGN_TABLE_SIZE - 1) 218207753Smm 219207753Smm// LZMA remembers the four most recent match distances. Reusing these distances 220207753Smm// tends to take less space than re-encoding the actual distance value. 221207753Smm#define REP_DISTANCES 4 222207753Smm 223207753Smm#endif 224