1 ///////////////////////////////////////////////////////////////////////////////
3 /// \file lzma_common.h
4 /// \brief Private definitions common to LZMA encoder and decoder
6 // Copyright (C) 1999-2006 Igor Pavlov
7 // Copyright (C) 2007 Lasse Collin
9 // This library is free software; you can redistribute it and/or
10 // modify it under the terms of the GNU Lesser General Public
11 // License as published by the Free Software Foundation; either
12 // version 2.1 of the License, or (at your option) any later version.
14 // This library is distributed in the hope that it will be useful,
15 // but WITHOUT ANY WARRANTY; without even the implied warranty of
16 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 // Lesser General Public License for more details.
19 ///////////////////////////////////////////////////////////////////////////////
21 #ifndef LZMA_LZMA_COMMON_H
22 #define LZMA_LZMA_COMMON_H
25 #include "range_common.h"
32 /// Maximum number of position states. A position state is the lowest pos bits
33 /// number of bits of the current uncompressed offset. In some places there
34 /// are different sets of probabilities for different pos states.
35 #define POS_STATES_MAX (1 << LZMA_PB_MAX)
38 /// Validates lc, lp, and pb.
40 is_lclppb_valid(const lzma_options_lzma *options)
42 return options->lc <= LZMA_LCLP_MAX && options->lp <= LZMA_LCLP_MAX
43 && options->lc + options->lp <= LZMA_LCLP_MAX
44 && options->pb <= LZMA_PB_MAX;
52 /// This enum is used to track which events have occurred most recently and
53 /// in which order. This information is used to predict the next event.
56 /// - Literal: One 8-bit byte
57 /// - Match: Repeat a chunk of data at some distance
58 /// - Long repeat: Multi-byte match at a recently seen distance
59 /// - Short repeat: One-byte repeat at a recently seen distance
61 /// The event names are in from STATE_oldest_older_previous. REP means
62 /// either short or long repeated match, and NONLIT means any non-literal.
67 STATE_SHORTREP_LIT_LIT,
79 /// Total number of states
82 /// The lowest 7 states indicate that the previous state was a literal.
86 /// Indicate that the latest state was a literal.
87 #define update_literal(state) \
88 state = ((state) <= STATE_SHORTREP_LIT_LIT \
90 : ((state) <= STATE_LIT_SHORTREP \
94 /// Indicate that the latest state was a match.
95 #define update_match(state) \
96 state = ((state) < LIT_STATES ? STATE_LIT_MATCH : STATE_NONLIT_MATCH)
98 /// Indicate that the latest state was a long repeated match.
99 #define update_long_rep(state) \
100 state = ((state) < LIT_STATES ? STATE_LIT_LONGREP : STATE_NONLIT_REP)
102 /// Indicate that the latest state was a short match.
103 #define update_short_rep(state) \
104 state = ((state) < LIT_STATES ? STATE_LIT_SHORTREP : STATE_NONLIT_REP)
106 /// Test if the previous state was a literal.
107 #define is_literal_state(state) \
108 ((state) < LIT_STATES)
115 /// Each literal coder is divided in three sections:
116 /// - 0x001-0x0FF: Without match byte
117 /// - 0x101-0x1FF: With match byte; match bit is 0
118 /// - 0x201-0x2FF: With match byte; match bit is 1
120 /// Match byte is used when the previous LZMA symbol was something else than
121 /// a literal (that is, it was some kind of match).
122 #define LITERAL_CODER_SIZE 0x300
124 /// Maximum number of literal coders
125 #define LITERAL_CODERS_MAX (1 << LZMA_LCLP_MAX)
127 /// Locate the literal coder for the next literal byte. The choice depends on
128 /// - the lowest literal_pos_bits bits of the position of the current
130 /// - the highest literal_context_bits bits of the previous byte.
131 #define literal_subcoder(probs, lc, lp_mask, pos, prev_byte) \
132 ((probs)[(((pos) & lp_mask) << lc) + ((prev_byte) >> (8 - lc))])
136 literal_init(probability (*probs)[LITERAL_CODER_SIZE],
137 uint32_t lc, uint32_t lp)
139 assert(lc + lp <= LZMA_LCLP_MAX);
141 const uint32_t coders = 1U << (lc + lp);
143 for (uint32_t i = 0; i < coders; ++i)
144 for (uint32_t j = 0; j < LITERAL_CODER_SIZE; ++j)
145 bit_reset(probs[i][j]);
155 // Minimum length of a match is two bytes.
156 #define MATCH_LEN_MIN 2
158 // Match length is encoded with 4, 5, or 10 bits.
161 // 2-9 4 = Choice=0 + 3 bits
162 // 10-17 5 = Choice=1 + Choice2=0 + 3 bits
163 // 18-273 10 = Choice=1 + Choice2=1 + 8 bits
164 #define LEN_LOW_BITS 3
165 #define LEN_LOW_SYMBOLS (1 << LEN_LOW_BITS)
166 #define LEN_MID_BITS 3
167 #define LEN_MID_SYMBOLS (1 << LEN_MID_BITS)
168 #define LEN_HIGH_BITS 8
169 #define LEN_HIGH_SYMBOLS (1 << LEN_HIGH_BITS)
170 #define LEN_SYMBOLS (LEN_LOW_SYMBOLS + LEN_MID_SYMBOLS + LEN_HIGH_SYMBOLS)
172 // Maximum length of a match is 273 which is a result of the encoding
174 #define MATCH_LEN_MAX (MATCH_LEN_MIN + LEN_SYMBOLS - 1)
181 // Different set of probabilities is used for match distances that have very
182 // short match length: Lengths of 2, 3, and 4 bytes have a separate set of
183 // probabilities for each length. The matches with longer length use a shared
184 // set of probabilities.
185 #define LEN_TO_POS_STATES 4
187 // Macro to get the index of the appropriate probability array.
188 #define get_len_to_pos_state(len) \
189 ((len) < LEN_TO_POS_STATES + MATCH_LEN_MIN \
190 ? (len) - MATCH_LEN_MIN \
191 : LEN_TO_POS_STATES - 1)
193 // The highest two bits of a match distance (pos slot) are encoded using six
194 // bits. See fastpos.h for more explanation.
195 #define POS_SLOT_BITS 6
196 #define POS_SLOTS (1 << POS_SLOT_BITS)
198 // Match distances up to 127 are fully encoded using probabilities. Since
199 // the highest two bits (pos slot) are always encoded using six bits, the
200 // distances 0-3 don't need any additional bits to encode, since the pos
201 // slot itself is the same as the actual distance. START_POS_MODEL_INDEX
202 // indicates the first pos slot where at least one additional bit is needed.
203 #define START_POS_MODEL_INDEX 4
205 // Match distances greater than 127 are encoded in three pieces:
206 // - pos slot: the highest two bits
207 // - direct bits: 2-26 bits below the highest two bits
208 // - alignment bits: four lowest bits
210 // Direct bits don't use any probabilities.
212 // The pos slot value of 14 is for distances 128-191 (see the table in
213 // fastpos.h to understand why).
214 #define END_POS_MODEL_INDEX 14
216 // Pos slots that indicate a distance <= 127.
217 #define FULL_DISTANCES_BITS (END_POS_MODEL_INDEX / 2)
218 #define FULL_DISTANCES (1 << FULL_DISTANCES_BITS)
220 // For match distances greater than 127, only the highest two bits and the
221 // lowest four bits (alignment) is encoded using probabilities.
223 #define ALIGN_TABLE_SIZE (1 << ALIGN_BITS)
224 #define ALIGN_MASK (ALIGN_TABLE_SIZE - 1)
226 // LZMA remembers the four most recent match distances. Reusing these distances
227 // tends to take less space than re-encoding the actual distance value.
228 #define REP_DISTANCES 4