Commit | Line | Data |
---|---|---|
836d13a6 LC |
1 | /* SPDX-License-Identifier: 0BSD */ |
2 | ||
24fa0402 LC |
3 | /* |
4 | * LZMA2 definitions | |
5 | * | |
6 | * Authors: Lasse Collin <lasse.collin@tukaani.org> | |
d89775fc | 7 | * Igor Pavlov <https://7-zip.org/> |
24fa0402 LC |
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 | */ | |
41 | enum 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. */ | |
63 | static 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. */ | |
74 | static 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. */ | |
80 | static 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. */ | |
86 | static 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. */ | |
92 | static 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 | */ | |
146 | static 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 |