1/* SPDX-License-Identifier: 0BSD */
2
3/*
4 * LZMA2 definitions
5 *
6 * Authors: Lasse Collin <lasse.collin@tukaani.org>
7 * Igor Pavlov <https://7-zip.org/>
8 */
9
10#ifndef XZ_LZMA2_H
11#define XZ_LZMA2_H
12
13/* Range coder constants */
14#define RC_SHIFT_BITS 8
15#define RC_TOP_BITS 24
16#define RC_TOP_VALUE (1 << RC_TOP_BITS)
17#define RC_BIT_MODEL_TOTAL_BITS 11
18#define RC_BIT_MODEL_TOTAL (1 << RC_BIT_MODEL_TOTAL_BITS)
19#define RC_MOVE_BITS 5
20
21/*
22 * Maximum number of position states. A position state is the lowest pb
23 * number of bits of the current uncompressed offset. In some places there
24 * are different sets of probabilities for different position states.
25 */
26#define POS_STATES_MAX (1 << 4)
27
28/*
29 * This enum is used to track which LZMA symbols have occurred most recently
30 * and in which order. This information is used to predict the next symbol.
31 *
32 * Symbols:
33 * - Literal: One 8-bit byte
34 * - Match: Repeat a chunk of data at some distance
35 * - Long repeat: Multi-byte match at a recently seen distance
36 * - Short repeat: One-byte repeat at a recently seen distance
37 *
38 * The symbol names are in from STATE_oldest_older_previous. REP means
39 * either short or long repeated match, and NONLIT means any non-literal.
40 */
41enum lzma_state {
42 STATE_LIT_LIT,
43 STATE_MATCH_LIT_LIT,
44 STATE_REP_LIT_LIT,
45 STATE_SHORTREP_LIT_LIT,
46 STATE_MATCH_LIT,
47 STATE_REP_LIT,
48 STATE_SHORTREP_LIT,
49 STATE_LIT_MATCH,
50 STATE_LIT_LONGREP,
51 STATE_LIT_SHORTREP,
52 STATE_NONLIT_MATCH,
53 STATE_NONLIT_REP
54};
55
56/* Total number of states */
57#define STATES 12
58
59/* The lowest 7 states indicate that the previous state was a literal. */
60#define LIT_STATES 7
61
62/* Indicate that the latest symbol was a literal. */
63static inline void lzma_state_literal(enum lzma_state *state)
64{
65 if (*state <= STATE_SHORTREP_LIT_LIT)
66 *state = STATE_LIT_LIT;
67 else if (*state <= STATE_LIT_SHORTREP)
68 *state -= 3;
69 else
70 *state -= 6;
71}
72
73/* Indicate that the latest symbol was a match. */
74static inline void lzma_state_match(enum lzma_state *state)
75{
76 *state = *state < LIT_STATES ? STATE_LIT_MATCH : STATE_NONLIT_MATCH;
77}
78
79/* Indicate that the latest state was a long repeated match. */
80static inline void lzma_state_long_rep(enum lzma_state *state)
81{
82 *state = *state < LIT_STATES ? STATE_LIT_LONGREP : STATE_NONLIT_REP;
83}
84
85/* Indicate that the latest symbol was a short match. */
86static inline void lzma_state_short_rep(enum lzma_state *state)
87{
88 *state = *state < LIT_STATES ? STATE_LIT_SHORTREP : STATE_NONLIT_REP;
89}
90
91/* Test if the previous symbol was a literal. */
92static inline bool lzma_state_is_literal(enum lzma_state state)
93{
94 return state < LIT_STATES;
95}
96
97/* Each literal coder is divided in three sections:
98 * - 0x001-0x0FF: Without match byte
99 * - 0x101-0x1FF: With match byte; match bit is 0
100 * - 0x201-0x2FF: With match byte; match bit is 1
101 *
102 * Match byte is used when the previous LZMA symbol was something else than
103 * a literal (that is, it was some kind of match).
104 */
105#define LITERAL_CODER_SIZE 0x300
106
107/* Maximum number of literal coders */
108#define LITERAL_CODERS_MAX (1 << 4)
109
110/* Minimum length of a match is two bytes. */
111#define MATCH_LEN_MIN 2
112
113/* Match length is encoded with 4, 5, or 10 bits.
114 *
115 * Length Bits
116 * 2-9 4 = Choice=0 + 3 bits
117 * 10-17 5 = Choice=1 + Choice2=0 + 3 bits
118 * 18-273 10 = Choice=1 + Choice2=1 + 8 bits
119 */
120#define LEN_LOW_BITS 3
121#define LEN_LOW_SYMBOLS (1 << LEN_LOW_BITS)
122#define LEN_MID_BITS 3
123#define LEN_MID_SYMBOLS (1 << LEN_MID_BITS)
124#define LEN_HIGH_BITS 8
125#define LEN_HIGH_SYMBOLS (1 << LEN_HIGH_BITS)
126#define LEN_SYMBOLS (LEN_LOW_SYMBOLS + LEN_MID_SYMBOLS + LEN_HIGH_SYMBOLS)
127
128/*
129 * Maximum length of a match is 273 which is a result of the encoding
130 * described above.
131 */
132#define MATCH_LEN_MAX (MATCH_LEN_MIN + LEN_SYMBOLS - 1)
133
134/*
135 * Different sets of probabilities are used for match distances that have
136 * very short match length: Lengths of 2, 3, and 4 bytes have a separate
137 * set of probabilities for each length. The matches with longer length
138 * use a shared set of probabilities.
139 */
140#define DIST_STATES 4
141
142/*
143 * Get the index of the appropriate probability array for decoding
144 * the distance slot.
145 */
146static inline uint32_t lzma_get_dist_state(uint32_t len)
147{
148 return len < DIST_STATES + MATCH_LEN_MIN
149 ? len - MATCH_LEN_MIN : DIST_STATES - 1;
150}
151
152/*
153 * The highest two bits of a 32-bit match distance are encoded using six bits.
154 * This six-bit value is called a distance slot. This way encoding a 32-bit
155 * value takes 6-36 bits, larger values taking more bits.
156 */
157#define DIST_SLOT_BITS 6
158#define DIST_SLOTS (1 << DIST_SLOT_BITS)
159
160/* Match distances up to 127 are fully encoded using probabilities. Since
161 * the highest two bits (distance slot) are always encoded using six bits,
162 * the distances 0-3 don't need any additional bits to encode, since the
163 * distance slot itself is the same as the actual distance. DIST_MODEL_START
164 * indicates the first distance slot where at least one additional bit is
165 * needed.
166 */
167#define DIST_MODEL_START 4
168
169/*
170 * Match distances greater than 127 are encoded in three pieces:
171 * - distance slot: the highest two bits
172 * - direct bits: 2-26 bits below the highest two bits
173 * - alignment bits: four lowest bits
174 *
175 * Direct bits don't use any probabilities.
176 *
177 * The distance slot value of 14 is for distances 128-191.
178 */
179#define DIST_MODEL_END 14
180
181/* Distance slots that indicate a distance <= 127. */
182#define FULL_DISTANCES_BITS (DIST_MODEL_END / 2)
183#define FULL_DISTANCES (1 << FULL_DISTANCES_BITS)
184
185/*
186 * For match distances greater than 127, only the highest two bits and the
187 * lowest four bits (alignment) is encoded using probabilities.
188 */
189#define ALIGN_BITS 4
190#define ALIGN_SIZE (1 << ALIGN_BITS)
191#define ALIGN_MASK (ALIGN_SIZE - 1)
192
193/* Total number of all probability variables */
194#define PROBS_TOTAL (1846 + LITERAL_CODERS_MAX * LITERAL_CODER_SIZE)
195
196/*
197 * LZMA remembers the four most recent match distances. Reusing these
198 * distances tends to take less space than re-encoding the actual
199 * distance value.
200 */
201#define REPS 4
202
203#endif
204