1 // SPDX-License-Identifier: 0BSD
2
3 ///////////////////////////////////////////////////////////////////////////////
4 //
5 /// \file lzma2_decoder.c
6 /// \brief LZMA2 decoder
7 ///
8 // Authors: Igor Pavlov
9 // Lasse Collin
10 //
11 ///////////////////////////////////////////////////////////////////////////////
12
13 #include "lzma2_decoder.h"
14 #include "lz_decoder.h"
15 #include "lzma_decoder.h"
16
17
18 typedef struct {
19 enum sequence {
20 SEQ_CONTROL,
21 SEQ_UNCOMPRESSED_1,
22 SEQ_UNCOMPRESSED_2,
23 SEQ_COMPRESSED_0,
24 SEQ_COMPRESSED_1,
25 SEQ_PROPERTIES,
26 SEQ_LZMA,
27 SEQ_COPY,
28 } sequence;
29
30 /// Sequence after the size fields have been decoded.
31 enum sequence next_sequence;
32
33 /// LZMA decoder
34 lzma_lz_decoder lzma;
35
36 /// Uncompressed size of LZMA chunk
37 size_t uncompressed_size;
38
39 /// Compressed size of the chunk (naturally equals to uncompressed
40 /// size of uncompressed chunk)
41 size_t compressed_size;
42
43 /// True if properties are needed. This is false before the
44 /// first LZMA chunk.
45 bool need_properties;
46
47 /// True if dictionary reset is needed. This is false before the
48 /// first chunk (LZMA or uncompressed).
49 bool need_dictionary_reset;
50
51 lzma_options_lzma options;
52 } lzma_lzma2_coder;
53
54
55 static lzma_ret
lzma2_decode(void * coder_ptr,lzma_dict * restrict dict,const uint8_t * restrict in,size_t * restrict in_pos,size_t in_size)56 lzma2_decode(void *coder_ptr, lzma_dict *restrict dict,
57 const uint8_t *restrict in, size_t *restrict in_pos,
58 size_t in_size)
59 {
60 lzma_lzma2_coder *restrict coder = coder_ptr;
61
62 // With SEQ_LZMA it is possible that no new input is needed to do
63 // some progress. The rest of the sequences assume that there is
64 // at least one byte of input.
65 while (*in_pos < in_size || coder->sequence == SEQ_LZMA)
66 switch (coder->sequence) {
67 case SEQ_CONTROL: {
68 const uint32_t control = in[*in_pos];
69 ++*in_pos;
70
71 // End marker
72 if (control == 0x00)
73 return LZMA_STREAM_END;
74
75 if (control >= 0xE0 || control == 1) {
76 // Dictionary reset implies that next LZMA chunk has
77 // to set new properties.
78 coder->need_properties = true;
79 coder->need_dictionary_reset = true;
80 } else if (coder->need_dictionary_reset) {
81 return LZMA_DATA_ERROR;
82 }
83
84 if (control >= 0x80) {
85 // LZMA chunk. The highest five bits of the
86 // uncompressed size are taken from the control byte.
87 coder->uncompressed_size = (control & 0x1F) << 16;
88 coder->sequence = SEQ_UNCOMPRESSED_1;
89
90 // See if there are new properties or if we need to
91 // reset the state.
92 if (control >= 0xC0) {
93 // When there are new properties, state reset
94 // is done at SEQ_PROPERTIES.
95 coder->need_properties = false;
96 coder->next_sequence = SEQ_PROPERTIES;
97
98 } else if (coder->need_properties) {
99 return LZMA_DATA_ERROR;
100
101 } else {
102 coder->next_sequence = SEQ_LZMA;
103
104 // If only state reset is wanted with old
105 // properties, do the resetting here for
106 // simplicity.
107 if (control >= 0xA0)
108 coder->lzma.reset(coder->lzma.coder,
109 &coder->options);
110 }
111 } else {
112 // Invalid control values
113 if (control > 2)
114 return LZMA_DATA_ERROR;
115
116 // It's uncompressed chunk
117 coder->sequence = SEQ_COMPRESSED_0;
118 coder->next_sequence = SEQ_COPY;
119 }
120
121 if (coder->need_dictionary_reset) {
122 // Finish the dictionary reset and let the caller
123 // flush the dictionary to the actual output buffer.
124 coder->need_dictionary_reset = false;
125 dict_reset(dict);
126 return LZMA_OK;
127 }
128
129 break;
130 }
131
132 case SEQ_UNCOMPRESSED_1:
133 coder->uncompressed_size += (uint32_t)(in[(*in_pos)++]) << 8;
134 coder->sequence = SEQ_UNCOMPRESSED_2;
135 break;
136
137 case SEQ_UNCOMPRESSED_2:
138 coder->uncompressed_size += in[(*in_pos)++] + 1U;
139 coder->sequence = SEQ_COMPRESSED_0;
140 coder->lzma.set_uncompressed(coder->lzma.coder,
141 coder->uncompressed_size, false);
142 break;
143
144 case SEQ_COMPRESSED_0:
145 coder->compressed_size = (uint32_t)(in[(*in_pos)++]) << 8;
146 coder->sequence = SEQ_COMPRESSED_1;
147 break;
148
149 case SEQ_COMPRESSED_1:
150 coder->compressed_size += in[(*in_pos)++] + 1U;
151 coder->sequence = coder->next_sequence;
152 break;
153
154 case SEQ_PROPERTIES:
155 if (lzma_lzma_lclppb_decode(&coder->options, in[(*in_pos)++]))
156 return LZMA_DATA_ERROR;
157
158 coder->lzma.reset(coder->lzma.coder, &coder->options);
159
160 coder->sequence = SEQ_LZMA;
161 break;
162
163 case SEQ_LZMA: {
164 // Store the start offset so that we can update
165 // coder->compressed_size later.
166 const size_t in_start = *in_pos;
167
168 // LZMA2 stream ends with the end marker (0x00), so there
169 // must be at least one byte after this chunk. Let the
170 // decoder read at most one byte past the end of the chunk.
171 // If the decoder reads the extra byte, then the input is
172 // corrupt. This way we won't produce (much) junk output
173 // from the input bytes that are past the end of this chunk.
174 // The extra byte makes things simpler, because we can ignore
175 // uncompressed size and not think about some corner cases.
176 //
177 // NOTE: It's not a security issue (information leak) to
178 // pass more input to the decoder than the chunk size.
179 // If an attacker can modify the compressed input, then the
180 // attacker can modify a chunk header so that it specifies
181 // a too large compressed size. liblzma <= 5.8.3 didn't
182 // have in_limit; in_size was passed to the decoder as is.
183 const size_t in_limit = *in_pos + my_min(in_size - *in_pos,
184 coder->compressed_size + 1);
185
186 // Decode from in[] to *dict.
187 const lzma_ret ret = coder->lzma.code(coder->lzma.coder,
188 dict, in, in_pos, in_limit);
189
190 // Validate and update coder->compressed_size. If the input
191 // is corrupt, let the caller still see the newly-decoded
192 // output even if it is (partially) corrupt. It might allow
193 // users to recover a small amount of useful data.
194 const size_t in_used = *in_pos - in_start;
195 if (in_used > coder->compressed_size)
196 return LZMA_DATA_ERROR;
197
198 coder->compressed_size -= in_used;
199
200 // Return if we didn't finish the chunk, or an error occurred.
201 if (ret != LZMA_STREAM_END)
202 return ret;
203
204 // The LZMA decoder must have consumed the whole chunk now.
205 // We don't need to worry about uncompressed size since it
206 // is checked by the LZMA decoder.
207 if (coder->compressed_size != 0)
208 return LZMA_DATA_ERROR;
209
210 coder->sequence = SEQ_CONTROL;
211 break;
212 }
213
214 case SEQ_COPY: {
215 // Copy from input to the dictionary as is.
216 dict_write(dict, in, in_pos, in_size, &coder->compressed_size);
217 if (coder->compressed_size != 0)
218 return LZMA_OK;
219
220 coder->sequence = SEQ_CONTROL;
221 break;
222 }
223
224 default:
225 assert(0);
226 return LZMA_PROG_ERROR;
227 }
228
229 return LZMA_OK;
230 }
231
232
233 static void
lzma2_decoder_end(void * coder_ptr,const lzma_allocator * allocator)234 lzma2_decoder_end(void *coder_ptr, const lzma_allocator *allocator)
235 {
236 lzma_lzma2_coder *coder = coder_ptr;
237
238 assert(coder->lzma.end == NULL);
239 lzma_free(coder->lzma.coder, allocator);
240
241 lzma_free(coder, allocator);
242
243 return;
244 }
245
246
247 static lzma_ret
lzma2_decoder_init(lzma_lz_decoder * lz,const lzma_allocator * allocator,lzma_vli id lzma_attribute ((__unused__)),const void * opt,lzma_lz_options * lz_options)248 lzma2_decoder_init(lzma_lz_decoder *lz, const lzma_allocator *allocator,
249 lzma_vli id lzma_attribute((__unused__)), const void *opt,
250 lzma_lz_options *lz_options)
251 {
252 lzma_lzma2_coder *coder = lz->coder;
253 if (coder == NULL) {
254 coder = lzma_alloc(sizeof(lzma_lzma2_coder), allocator);
255 if (coder == NULL)
256 return LZMA_MEM_ERROR;
257
258 lz->coder = coder;
259 lz->code = &lzma2_decode;
260 lz->end = &lzma2_decoder_end;
261
262 coder->lzma = LZMA_LZ_DECODER_INIT;
263 }
264
265 const lzma_options_lzma *options = opt;
266
267 coder->sequence = SEQ_CONTROL;
268 coder->need_properties = true;
269 coder->need_dictionary_reset = options->preset_dict == NULL
270 || options->preset_dict_size == 0;
271
272 return lzma_lzma_decoder_create(&coder->lzma,
273 allocator, options, lz_options);
274 }
275
276
277 extern lzma_ret
lzma_lzma2_decoder_init(lzma_next_coder * next,const lzma_allocator * allocator,const lzma_filter_info * filters)278 lzma_lzma2_decoder_init(lzma_next_coder *next, const lzma_allocator *allocator,
279 const lzma_filter_info *filters)
280 {
281 // LZMA2 can only be the last filter in the chain. This is enforced
282 // by the raw_decoder initialization.
283 assert(filters[1].init == NULL);
284
285 return lzma_lz_decoder_init(next, allocator, filters,
286 &lzma2_decoder_init);
287 }
288
289
290 extern uint64_t
lzma_lzma2_decoder_memusage(const void * options)291 lzma_lzma2_decoder_memusage(const void *options)
292 {
293 return sizeof(lzma_lzma2_coder)
294 + lzma_lzma_decoder_memusage_nocheck(options);
295 }
296
297
298 extern lzma_ret
lzma_lzma2_props_decode(void ** options,const lzma_allocator * allocator,const uint8_t * props,size_t props_size)299 lzma_lzma2_props_decode(void **options, const lzma_allocator *allocator,
300 const uint8_t *props, size_t props_size)
301 {
302 if (props_size != 1)
303 return LZMA_OPTIONS_ERROR;
304
305 // Check that reserved bits are unset.
306 if (props[0] & 0xC0)
307 return LZMA_OPTIONS_ERROR;
308
309 // Decode the dictionary size.
310 if (props[0] > 40)
311 return LZMA_OPTIONS_ERROR;
312
313 lzma_options_lzma *opt = lzma_alloc(
314 sizeof(lzma_options_lzma), allocator);
315 if (opt == NULL)
316 return LZMA_MEM_ERROR;
317
318 if (props[0] == 40) {
319 opt->dict_size = UINT32_MAX;
320 } else {
321 opt->dict_size = 2 | (props[0] & 1U);
322 opt->dict_size <<= props[0] / 2U + 11;
323 }
324
325 opt->preset_dict = NULL;
326 opt->preset_dict_size = 0;
327
328 *options = opt;
329
330 return LZMA_OK;
331 }
332