1 ///////////////////////////////////////////////////////////////////////////////
2 //
3 /// \file lz_decoder.c
4 /// \brief LZ out window
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 // liblzma supports multiple LZ77-based filters. The LZ part is shared
15 // between these filters. The LZ code takes care of dictionary handling
16 // and passing the data between filters in the chain. The filter-specific
17 // part decodes from the input buffer to the dictionary.
18
19
20 #include "lz_decoder.h"
21
22
23 typedef struct {
24 /// Dictionary (history buffer)
25 lzma_dict dict;
26
27 /// The actual LZ-based decoder e.g. LZMA
28 lzma_lz_decoder lz;
29
30 /// Next filter in the chain, if any. Note that LZMA and LZMA2 are
31 /// only allowed as the last filter, but the long-range filter in
32 /// future can be in the middle of the chain.
33 lzma_next_coder next;
34
35 /// True if the next filter in the chain has returned LZMA_STREAM_END.
36 bool next_finished;
37
38 /// True if the LZ decoder (e.g. LZMA) has detected end of payload
39 /// marker. This may become true before next_finished becomes true.
40 bool this_finished;
41
42 /// Temporary buffer needed when the LZ-based filter is not the last
43 /// filter in the chain. The output of the next filter is first
44 /// decoded into buffer[], which is then used as input for the actual
45 /// LZ-based decoder.
46 struct {
47 size_t pos;
48 size_t size;
49 uint8_t buffer[LZMA_BUFFER_SIZE];
50 } temp;
51 } lzma_coder;
52
53
54 static void
55 lz_decoder_reset(lzma_coder *coder)
56 {
57 coder->dict.pos = 0;
58 coder->dict.full = 0;
59 coder->dict.buf[coder->dict.size - 1] = '\0';
60 coder->dict.need_reset = false;
61 return;
62 }
63
64
65 static lzma_ret
66 decode_buffer(lzma_coder *coder,
67 const uint8_t *restrict in, size_t *restrict in_pos,
68 size_t in_size, uint8_t *restrict out,
69 size_t *restrict out_pos, size_t out_size)
70 {
71 while (true) {
72 // Wrap the dictionary if needed.
73 if (coder->dict.pos == coder->dict.size)
74 coder->dict.pos = 0;
75
76 // Store the current dictionary position. It is needed to know
77 // where to start copying to the out[] buffer.
78 const size_t dict_start = coder->dict.pos;
79
80 // Calculate how much we allow coder->lz.code() to decode.
81 // It must not decode past the end of the dictionary
82 // buffer, and we don't want it to decode more than is
83 // actually needed to fill the out[] buffer.
84 coder->dict.limit = coder->dict.pos
85 + my_min(out_size - *out_pos,
86 coder->dict.size - coder->dict.pos);
87
88 // Call the coder->lz.code() to do the actual decoding.
89 const lzma_ret ret = coder->lz.code(
90 coder->lz.coder, &coder->dict,
91 in, in_pos, in_size);
92
93 // Copy the decoded data from the dictionary to the out[]
94 // buffer. Do it conditionally because out can be NULL
95 // (in which case copy_size is always 0). Calling memcpy()
96 // with a null-pointer is undefined even if the third
97 // argument is 0.
98 const size_t copy_size = coder->dict.pos - dict_start;
99 assert(copy_size <= out_size - *out_pos);
100
101 if (copy_size > 0)
102 memcpy(out + *out_pos, coder->dict.buf + dict_start,
103 copy_size);
104
105 *out_pos += copy_size;
106
107 // Reset the dictionary if so requested by coder->lz.code().
108 if (coder->dict.need_reset) {
109 lz_decoder_reset(coder);
110
111 // Since we reset dictionary, we don't check if
112 // dictionary became full.
113 if (ret != LZMA_OK || *out_pos == out_size)
114 return ret;
115 } else {
116 // Return if everything got decoded or an error
117 // occurred, or if there's no more data to decode.
118 //
119 // Note that detecting if there's something to decode
120 // is done by looking if dictionary become full
121 // instead of looking if *in_pos == in_size. This
122 // is because it is possible that all the input was
123 // consumed already but some data is pending to be
124 // written to the dictionary.
125 if (ret != LZMA_OK || *out_pos == out_size
126 || coder->dict.pos < coder->dict.size)
127 return ret;
128 }
129 }
130 }
131
132
133 static lzma_ret
134 lz_decode(void *coder_ptr, const lzma_allocator *allocator,
135 const uint8_t *restrict in, size_t *restrict in_pos,
136 size_t in_size, uint8_t *restrict out,
137 size_t *restrict out_pos, size_t out_size,
138 lzma_action action)
139 {
140 lzma_coder *coder = coder_ptr;
141
142 if (coder->next.code == NULL)
143 return decode_buffer(coder, in, in_pos, in_size,
144 out, out_pos, out_size);
145
146 // We aren't the last coder in the chain, we need to decode
147 // our input to a temporary buffer.
148 while (*out_pos < out_size) {
149 // Fill the temporary buffer if it is empty.
150 if (!coder->next_finished
151 && coder->temp.pos == coder->temp.size) {
152 coder->temp.pos = 0;
153 coder->temp.size = 0;
154
155 const lzma_ret ret = coder->next.code(
156 coder->next.coder,
157 allocator, in, in_pos, in_size,
158 coder->temp.buffer, &coder->temp.size,
159 LZMA_BUFFER_SIZE, action);
160
161 if (ret == LZMA_STREAM_END)
162 coder->next_finished = true;
163 else if (ret != LZMA_OK || coder->temp.size == 0)
164 return ret;
165 }
166
167 if (coder->this_finished) {
168 if (coder->temp.size != 0)
169 return LZMA_DATA_ERROR;
170
171 if (coder->next_finished)
172 return LZMA_STREAM_END;
173
174 return LZMA_OK;
175 }
176
177 const lzma_ret ret = decode_buffer(coder, coder->temp.buffer,
178 &coder->temp.pos, coder->temp.size,
179 out, out_pos, out_size);
180
181 if (ret == LZMA_STREAM_END)
182 coder->this_finished = true;
183 else if (ret != LZMA_OK)
184 return ret;
185 else if (coder->next_finished && *out_pos < out_size)
186 return LZMA_DATA_ERROR;
187 }
188
189 return LZMA_OK;
190 }
191
192
193 static void
194 lz_decoder_end(void *coder_ptr, const lzma_allocator *allocator)
195 {
196 lzma_coder *coder = coder_ptr;
197
198 lzma_next_end(&coder->next, allocator);
199 lzma_free(coder->dict.buf, allocator);
200
201 if (coder->lz.end != NULL)
202 coder->lz.end(coder->lz.coder, allocator);
203 else
204 lzma_free(coder->lz.coder, allocator);
205
206 lzma_free(coder, allocator);
207 return;
208 }
209
210
211 extern lzma_ret
212 lzma_lz_decoder_init(lzma_next_coder *next, const lzma_allocator *allocator,
213 const lzma_filter_info *filters,
214 lzma_ret (*lz_init)(lzma_lz_decoder *lz,
215 const lzma_allocator *allocator,
216 lzma_vli id, const void *options,
217 lzma_lz_options *lz_options))
218 {
219 // Allocate the base structure if it isn't already allocated.
220 lzma_coder *coder = next->coder;
221 if (coder == NULL) {
222 coder = lzma_alloc(sizeof(lzma_coder), allocator);
223 if (coder == NULL)
224 return LZMA_MEM_ERROR;
225
226 next->coder = coder;
227 next->code = &lz_decode;
228 next->end = &lz_decoder_end;
229
230 coder->dict.buf = NULL;
231 coder->dict.size = 0;
232 coder->lz = LZMA_LZ_DECODER_INIT;
233 coder->next = LZMA_NEXT_CODER_INIT;
234 }
235
236 // Allocate and initialize the LZ-based decoder. It will also give
237 // us the dictionary size.
238 lzma_lz_options lz_options;
239 return_if_error(lz_init(&coder->lz, allocator,
240 filters[0].id, filters[0].options, &lz_options));
241
242 // If the dictionary size is very small, increase it to 4096 bytes.
243 // This is to prevent constant wrapping of the dictionary, which
244 // would slow things down. The downside is that since we don't check
245 // separately for the real dictionary size, we may happily accept
246 // corrupt files.
247 if (lz_options.dict_size < 4096)
248 lz_options.dict_size = 4096;
249
250 // Make dictionary size a multiple of 16. Some LZ-based decoders like
251 // LZMA use the lowest bits lzma_dict.pos to know the alignment of the
252 // data. Aligned buffer is also good when memcpying from the
253 // dictionary to the output buffer, since applications are
254 // recommended to give aligned buffers to liblzma.
255 //
256 // Avoid integer overflow.
257 if (lz_options.dict_size > SIZE_MAX - 15)
258 return LZMA_MEM_ERROR;
259
260 lz_options.dict_size = (lz_options.dict_size + 15) & ~((size_t)(15));
261
262 // Allocate and initialize the dictionary.
263 if (coder->dict.size != lz_options.dict_size) {
264 lzma_free(coder->dict.buf, allocator);
265 coder->dict.buf
266 = lzma_alloc(lz_options.dict_size, allocator);
267 if (coder->dict.buf == NULL)
268 return LZMA_MEM_ERROR;
269
270 coder->dict.size = lz_options.dict_size;
271 }
272
273 lz_decoder_reset(next->coder);
274
275 // Use the preset dictionary if it was given to us.
276 if (lz_options.preset_dict != NULL
277 && lz_options.preset_dict_size > 0) {
278 // If the preset dictionary is bigger than the actual
279 // dictionary, copy only the tail.
280 const size_t copy_size = my_min(lz_options.preset_dict_size,
281 lz_options.dict_size);
282 const size_t offset = lz_options.preset_dict_size - copy_size;
283 memcpy(coder->dict.buf, lz_options.preset_dict + offset,
284 copy_size);
285 coder->dict.pos = copy_size;
286 coder->dict.full = copy_size;
287 }
288
289 // Miscellaneous initializations
290 coder->next_finished = false;
291 coder->this_finished = false;
292 coder->temp.pos = 0;
293 coder->temp.size = 0;
294
295 // Initialize the next filter in the chain, if any.
296 return lzma_next_filter_init(&coder->next, allocator, filters + 1);
297 }
298
299
300 extern uint64_t
301 lzma_lz_decoder_memusage(size_t dictionary_size)
302 {
303 return sizeof(lzma_coder) + (uint64_t)(dictionary_size);
304 }