1 /* -*- mode: C; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 // vim: expandtab:ts=8:sw=4:softtabstop=4:
3 ///////////////////////////////////////////////////////////////////////////////
4 //
5 /// \file lzma2_decoder.c
6 /// \brief LZMA2 decoder
7 ///
8 // Authors: Igor Pavlov
9 // Lasse Collin
10 //
11 // This file has been put into the public domain.
12 // You can do whatever you want with this file.
13 //
14 ///////////////////////////////////////////////////////////////////////////////
15
16 #include "lzma2_decoder.h"
17 #include "lz_decoder.h"
18 #include "lzma_decoder.h"
19
20
21 struct lzma_coder_s {
22 enum sequence {
23 SEQ_CONTROL,
24 SEQ_UNCOMPRESSED_1,
25 SEQ_UNCOMPRESSED_2,
26 SEQ_COMPRESSED_0,
27 SEQ_COMPRESSED_1,
28 SEQ_PROPERTIES,
29 SEQ_LZMA,
30 SEQ_COPY,
31 } sequence;
32
33 /// Sequence after the size fields have been decoded.
34 enum sequence next_sequence;
35
36 /// LZMA decoder
37 lzma_lz_decoder lzma;
38
39 /// Uncompressed size of LZMA chunk
40 size_t uncompressed_size;
41
42 /// Compressed size of the chunk (naturally equals to uncompressed
43 /// size of uncompressed chunk)
44 size_t compressed_size;
45
46 /// True if properties are needed. This is false before the
47 /// first LZMA chunk.
48 bool need_properties;
49
50 /// True if dictionary reset is needed. This is false before the
51 /// first chunk (LZMA or uncompressed).
52 bool need_dictionary_reset;
53
54 lzma_options_lzma options;
55 };
56
57
58 static lzma_ret
lzma2_decode(lzma_coder * restrict coder,lzma_dict * restrict dict,const uint8_t * restrict in,size_t * restrict in_pos,size_t in_size)59 lzma2_decode(lzma_coder *restrict coder, lzma_dict *restrict dict,
60 const uint8_t *restrict in, size_t *restrict in_pos,
61 size_t in_size)
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 if (control >= 0xE0 || control == 1) {
73 // Dictionary reset implies that next LZMA chunk has
74 // to set new properties.
75 coder->need_properties = true;
76 coder->need_dictionary_reset = true;
77 } else if (coder->need_dictionary_reset) {
78 return LZMA_DATA_ERROR;
79 }
80
81 if (control >= 0x80) {
82 // LZMA chunk. The highest five bits of the
83 // uncompressed size are taken from the control byte.
84 coder->uncompressed_size = (control & 0x1F) << 16;
85 coder->sequence = SEQ_UNCOMPRESSED_1;
86
87 // See if there are new properties or if we need to
88 // reset the state.
89 if (control >= 0xC0) {
90 // When there are new properties, state reset
91 // is done at SEQ_PROPERTIES.
92 coder->need_properties = false;
93 coder->next_sequence = SEQ_PROPERTIES;
94
95 } else if (coder->need_properties) {
96 return LZMA_DATA_ERROR;
97
98 } else {
99 coder->next_sequence = SEQ_LZMA;
100
101 // If only state reset is wanted with old
102 // properties, do the resetting here for
103 // simplicity.
104 if (control >= 0xA0)
105 coder->lzma.reset(coder->lzma.coder,
106 &coder->options);
107 }
108 } else {
109 // End marker
110 if (control == 0x00)
111 return LZMA_STREAM_END;
112
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)++] + 1;
140 coder->sequence = SEQ_COMPRESSED_0;
141 coder->lzma.set_uncompressed(coder->lzma.coder,
142 coder->uncompressed_size);
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)++] + 1;
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 // FIXME Can copy too much?
197 dict_write(dict, in, in_pos, in_size, &coder->compressed_size);
198 if (coder->compressed_size != 0)
199 return LZMA_OK;
200
201 coder->sequence = SEQ_CONTROL;
202 break;
203 }
204
205 default:
206 assert(0);
207 return LZMA_PROG_ERROR;
208 }
209
210 return LZMA_OK;
211 }
212
213
214 static void
lzma2_decoder_end(lzma_coder * coder,lzma_allocator * allocator)215 lzma2_decoder_end(lzma_coder *coder, lzma_allocator *allocator)
216 {
217 assert(coder->lzma.end == NULL);
218 lzma_free(coder->lzma.coder, allocator);
219
220 lzma_free(coder, allocator);
221
222 return;
223 }
224
225
226 static lzma_ret
lzma2_decoder_init(lzma_lz_decoder * lz,lzma_allocator * allocator,const void * opt,lzma_lz_options * lz_options)227 lzma2_decoder_init(lzma_lz_decoder *lz, lzma_allocator *allocator,
228 const void *opt, lzma_lz_options *lz_options)
229 {
230 if (lz->coder == NULL) {
231 lz->coder = lzma_alloc(sizeof(lzma_coder), allocator);
232 if (lz->coder == NULL)
233 return LZMA_MEM_ERROR;
234
235 lz->code = &lzma2_decode;
236 lz->end = &lzma2_decoder_end;
237
238 lz->coder->lzma = LZMA_LZ_DECODER_INIT;
239 }
240
241 const lzma_options_lzma *options = opt;
242
243 lz->coder->sequence = SEQ_CONTROL;
244 lz->coder->need_properties = true;
245 lz->coder->need_dictionary_reset = options->preset_dict == NULL
246 || options->preset_dict_size == 0;
247
248 return lzma_lzma_decoder_create(&lz->coder->lzma,
249 allocator, options, lz_options);
250 }
251
252
253 extern lzma_ret
lzma_lzma2_decoder_init(lzma_next_coder * next,lzma_allocator * allocator,const lzma_filter_info * filters)254 lzma_lzma2_decoder_init(lzma_next_coder *next, lzma_allocator *allocator,
255 const lzma_filter_info *filters)
256 {
257 // LZMA2 can only be the last filter in the chain. This is enforced
258 // by the raw_decoder initialization.
259 assert(filters[1].init == NULL);
260
261 return lzma_lz_decoder_init(next, allocator, filters,
262 &lzma2_decoder_init);
263 }
264
265
266 extern uint64_t
lzma_lzma2_decoder_memusage(const void * options)267 lzma_lzma2_decoder_memusage(const void *options)
268 {
269 return sizeof(lzma_coder)
270 + lzma_lzma_decoder_memusage_nocheck(options);
271 }
272
273
274 extern lzma_ret
lzma_lzma2_props_decode(void ** options,lzma_allocator * allocator,const uint8_t * props,size_t props_size)275 lzma_lzma2_props_decode(void **options, lzma_allocator *allocator,
276 const uint8_t *props, size_t props_size)
277 {
278 if (props_size != 1)
279 return LZMA_OPTIONS_ERROR;
280
281 // Check that reserved bits are unset.
282 if (props[0] & 0xC0)
283 return LZMA_OPTIONS_ERROR;
284
285 // Decode the dictionary size.
286 if (props[0] > 40)
287 return LZMA_OPTIONS_ERROR;
288
289 lzma_options_lzma *opt = lzma_alloc(
290 sizeof(lzma_options_lzma), allocator);
291 if (opt == NULL)
292 return LZMA_MEM_ERROR;
293
294 if (props[0] == 40) {
295 opt->dict_size = UINT32_MAX;
296 } else {
297 opt->dict_size = 2 | (props[0] & 1);
298 opt->dict_size <<= props[0] / 2 + 11;
299 }
300
301 opt->preset_dict = NULL;
302 opt->preset_dict_size = 0;
303
304 *options = opt;
305
306 return LZMA_OK;
307 }
308