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