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