1 ///////////////////////////////////////////////////////////////////////////////
4 /// \brief LZ out window
6 // Copyright (C) 1999-2006 Igor Pavlov
7 // Copyright (C) 2007 Lasse Collin
9 // This library is free software; you can redistribute it and/or
10 // modify it under the terms of the GNU Lesser General Public
11 // License as published by the Free Software Foundation; either
12 // version 2.1 of the License, or (at your option) any later version.
14 // This library is distributed in the hope that it will be useful,
15 // but WITHOUT ANY WARRANTY; without even the implied warranty of
16 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 // Lesser General Public License for more details.
19 ///////////////////////////////////////////////////////////////////////////////
21 #include "lz_decoder.h"
24 /// Minimum size of allocated dictionary
25 #define DICT_SIZE_MIN 8192
27 /// When there is less than this amount of data available for decoding,
28 /// it is moved to the temporary buffer which
29 /// - protects from reads past the end of the buffer; and
30 /// - stored the incomplete data between lzma_code() calls.
32 /// \note TEMP_LIMIT must be at least as much as
33 /// REQUIRED_IN_BUFFER_SIZE defined in lzma_decoder.c.
36 // lzma_lz_decoder.dict[] must be three times the size of TEMP_LIMIT.
37 // 2 * TEMP_LIMIT is used for the actual data, and the third TEMP_LIMIT
38 // bytes is needed for safety to allow decode_dummy() in lzma_decoder.c
39 // to read past end of the buffer. This way it should be both fast and simple.
40 #if LZMA_BUFFER_SIZE < 3 * TEMP_LIMIT
41 # error LZMA_BUFFER_SIZE < 3 * TEMP_LIMIT
49 // There are more members in this structure but they are not
50 // visible in LZ coder.
54 /// - Copy as much data as possible from lz->dict[] to out[].
55 /// - Update *out_pos, lz->start, and lz->end accordingly.
56 /// - Wrap lz-pos to the beginning of lz->dict[] if there is a danger that
57 /// it may go past the end of the buffer (lz->pos >= lz->must_flush_pos).
59 flush(lzma_lz_decoder *restrict lz, uint8_t *restrict out,
60 size_t *restrict out_pos, size_t out_size)
62 // Flush uncompressed data from the history buffer to
63 // the output buffer. This is done in two phases.
65 assert(lz->start <= lz->end);
67 // Flush if pos < start < end.
68 if (lz->pos < lz->start && lz->start < lz->end) {
69 bufcpy(lz->dict, &lz->start, lz->end, out, out_pos, out_size);
71 // If we reached end of the data in history buffer,
72 // wrap to the beginning.
73 if (lz->start == lz->end)
77 // Flush if start start < pos <= end. This is not as `else' for
78 // previous `if' because the previous one may make this one true.
79 if (lz->start < lz->pos) {
80 bufcpy(lz->dict, &lz->start,
81 lz->pos, out, out_pos, out_size);
83 if (lz->pos >= lz->must_flush_pos) {
84 // Wrap the flushing position if we have
85 // flushed the whole history buffer.
86 if (lz->pos == lz->start)
89 // Wrap the write position and store to lz.end
90 // how much there is new data available.
97 assert(lz->pos < lz->must_flush_pos);
99 return *out_pos == out_size;
103 /// Calculate safe value for lz->limit. If no safe value can be found,
104 /// set lz->limit to zero. When flushing, only as little data will be
105 /// decoded as is needed to fill the output buffer (lowers both latency
108 /// \return true if there is no space for new uncompressed data.
111 set_limit(lzma_lz_decoder *lz, size_t out_avail, bool flushing)
113 // Set the limit so that writing to dict[limit + match_max_len - 1]
114 // doesn't overwrite any unflushed data and doesn't write past the
115 // end of the dict buffer.
116 if (lz->start <= lz->pos) {
117 // We can fill the buffer from pos till the end
118 // of the dict buffer.
119 lz->limit = lz->must_flush_pos;
120 } else if (lz->pos + lz->match_max_len < lz->start) {
121 // There's some unflushed data between pos and end of the
122 // buffer. Limit so that we don't overwrite the unflushed data.
123 lz->limit = lz->start - lz->match_max_len;
125 // Buffer is too full.
130 // Finetune the limit a bit if it isn't zero.
132 assert(lz->limit > lz->pos);
133 const size_t dict_avail = lz->limit - lz->pos;
135 if (lz->uncompressed_size < dict_avail) {
136 // Finishing a stream that doesn't have
137 // an end of stream marker.
138 lz->limit = lz->pos + lz->uncompressed_size;
140 } else if (flushing && out_avail < dict_avail) {
141 // Flushing enabled, decoding only as little as needed to
142 // fill the out buffer (if there's enough input, of course).
143 lz->limit = lz->pos + out_avail;
146 return lz->limit == lz->pos;
150 /// Takes care of wrapping the data into temporary buffer when needed,
151 /// and calls the actual decoder.
153 /// \return true if error occurred
156 call_process(lzma_coder *restrict coder, const uint8_t *restrict in,
157 size_t *restrict in_pos, size_t in_size)
159 // It would be nice and simple if we could just give in[] to the
160 // decoder, but the requirement of zlib-like API forces us to be
161 // able to make *in_pos == in_size whenever there is enough output
162 // space. If needed, we will append a few bytes from in[] to
163 // a temporary buffer and decode enough to reach the part that
164 // was copied from in[]. Then we can continue with the real in[].
167 const size_t dict_old_pos = coder->lz.pos;
168 const size_t in_avail = in_size - *in_pos;
170 if (coder->lz.temp_size + in_avail < 2 * TEMP_LIMIT) {
171 // Copy all the available input from in[] to temp[].
172 memcpy(coder->lz.temp + coder->lz.temp_size,
173 in + *in_pos, in_avail);
174 coder->lz.temp_size += in_avail;
176 assert(*in_pos == in_size);
178 // Decode as much as possible.
179 size_t temp_used = 0;
180 error = coder->lz.process(coder, coder->lz.temp, &temp_used,
181 coder->lz.temp_size, true);
182 assert(temp_used <= coder->lz.temp_size);
184 // Move the remaining data to the beginning of temp[].
185 coder->lz.temp_size -= temp_used;
186 memmove(coder->lz.temp, coder->lz.temp + temp_used,
187 coder->lz.temp_size);
189 } else if (coder->lz.temp_size > 0) {
190 // Fill temp[] unless it is already full because we aren't
191 // the last filter in the chain.
192 size_t copy_size = 0;
193 if (coder->lz.temp_size < 2 * TEMP_LIMIT) {
194 assert(*in_pos < in_size);
195 copy_size = 2 * TEMP_LIMIT - coder->lz.temp_size;
196 memcpy(coder->lz.temp + coder->lz.temp_size,
197 in + *in_pos, copy_size);
198 // NOTE: We don't update lz.temp_size or *in_pos yet.
201 size_t temp_used = 0;
202 error = coder->lz.process(coder, coder->lz.temp, &temp_used,
203 coder->lz.temp_size + copy_size, false);
205 if (temp_used < coder->lz.temp_size) {
206 // Only very little input data was consumed. Move
207 // the unprocessed data to the beginning temp[].
208 coder->lz.temp_size += copy_size - temp_used;
209 memmove(coder->lz.temp, coder->lz.temp + temp_used,
210 coder->lz.temp_size);
211 *in_pos += copy_size;
212 assert(*in_pos <= in_size);
215 // We were able to decode so much data that next time
216 // we can decode directly from in[]. That is, we can
217 // consider temp[] to be empty now.
218 *in_pos += temp_used - coder->lz.temp_size;
219 coder->lz.temp_size = 0;
220 assert(*in_pos <= in_size);
224 // Decode directly from in[].
225 error = coder->lz.process(coder, in, in_pos, in_size, false);
226 assert(*in_pos <= in_size);
229 assert(coder->lz.pos >= dict_old_pos);
230 if (coder->lz.uncompressed_size != LZMA_VLI_VALUE_UNKNOWN) {
231 // Update uncompressed size.
232 coder->lz.uncompressed_size -= coder->lz.pos - dict_old_pos;
234 // Check that End of Payload Marker hasn't been detected
235 // since it must not be present because uncompressed size
237 if (coder->lz.eopm_detected)
246 decode_buffer(lzma_coder *coder,
247 const uint8_t *restrict in, size_t *restrict in_pos,
248 size_t in_size, uint8_t *restrict out,
249 size_t *restrict out_pos, size_t out_size,
255 // Flush from coder->lz.dict to out[].
256 flush(&coder->lz, out, out_pos, out_size);
259 if (*out_pos == out_size
261 || coder->lz.eopm_detected
262 || coder->lz.uncompressed_size == 0)
265 // Set write limit in the dictionary.
266 if (set_limit(&coder->lz, out_size - *out_pos, flushing))
270 if (call_process(coder, in, in_pos, in_size))
271 return LZMA_DATA_ERROR;
273 // Set stop to true if we must not call call_process() again
274 // during this function call.
275 // FIXME: Can this make the loop exist too early? It wouldn't
276 // cause data corruption so not a critical problem. It can
277 // happen if dictionary gets full and lz.temp still contains
278 // a few bytes data that we could decode right now.
279 if (*in_pos == in_size && coder->lz.temp_size <= TEMP_LIMIT
280 && coder->lz.pos < coder->lz.limit)
284 // If we have decoded everything (EOPM detected or uncompressed_size
285 // bytes were processed) to the history buffer, and also flushed
286 // everything from the history buffer, our job is done.
287 if ((coder->lz.eopm_detected
288 || coder->lz.uncompressed_size == 0)
289 && coder->lz.start == coder->lz.pos)
290 return LZMA_STREAM_END;
297 lzma_lz_decode(lzma_coder *coder,
298 lzma_allocator *allocator lzma_attribute((unused)),
299 const uint8_t *restrict in, size_t *restrict in_pos,
300 size_t in_size, uint8_t *restrict out,
301 size_t *restrict out_pos, size_t out_size,
304 if (coder->next.code == NULL) {
305 const lzma_ret ret = decode_buffer(coder, in, in_pos, in_size,
306 out, out_pos, out_size,
307 action == LZMA_SYNC_FLUSH);
309 if (*out_pos == out_size || ret == LZMA_STREAM_END) {
310 // Unread to make coder->temp[] empty. This is easy,
311 // because we know that all the data currently in
312 // coder->temp[] has been copied form in[] during this
313 // call to the decoder.
315 // If we didn't do this, we could have data left in
316 // coder->temp[] when end of stream is reached. That
317 // data could be left there from *previous* call to
318 // the decoder; in that case we wouldn't know where
320 assert(*in_pos >= coder->lz.temp_size);
321 *in_pos -= coder->lz.temp_size;
322 coder->lz.temp_size = 0;
328 // We aren't the last coder in the chain, we need to decode
329 // our input to a temporary buffer.
330 const bool flushing = action == LZMA_SYNC_FLUSH;
331 while (*out_pos < out_size) {
332 if (!coder->lz.next_finished
333 && coder->lz.temp_size < LZMA_BUFFER_SIZE) {
334 const lzma_ret ret = coder->next.code(
336 allocator, in, in_pos, in_size,
337 coder->lz.temp, &coder->lz.temp_size,
338 LZMA_BUFFER_SIZE, action);
340 if (ret == LZMA_STREAM_END)
341 coder->lz.next_finished = true;
342 else if (coder->lz.temp_size < LZMA_BUFFER_SIZE
347 if (coder->lz.this_finished) {
348 if (coder->lz.temp_size != 0)
349 return LZMA_DATA_ERROR;
351 if (coder->lz.next_finished)
352 return LZMA_STREAM_END;
358 const lzma_ret ret = decode_buffer(coder, NULL, &dummy, 0,
359 out, out_pos, out_size, flushing);
361 if (ret == LZMA_STREAM_END)
362 coder->lz.this_finished = true;
363 else if (ret != LZMA_OK)
365 else if (coder->lz.next_finished && *out_pos < out_size)
366 return LZMA_DATA_ERROR;
373 /// \brief Initializes LZ part of the LZMA decoder or Inflate
375 /// \param history_size Number of bytes the LZ out window is
376 /// supposed keep available from the output
378 /// \param match_max_len Number of bytes a single decoding loop
379 /// can advance the write position (lz->pos)
380 /// in the history buffer (lz->dict).
382 /// \note This function is called by LZMA decoder and Inflate init()s.
383 /// It's up to those functions allocate *lz and initialize it
384 /// with LZMA_LZ_DECODER_INIT.
386 lzma_lz_decoder_reset(lzma_lz_decoder *lz, lzma_allocator *allocator,
387 bool (*process)(lzma_coder *restrict coder,
388 const uint8_t *restrict in, size_t *restrict in_pos,
389 size_t in_size, bool has_safe_buffer),
390 size_t history_size, size_t match_max_len)
392 // Known uncompressed size is used only with LZMA_Alone files so we
393 // set it always to unknown by default.
394 lz->uncompressed_size = LZMA_VLI_VALUE_UNKNOWN;
396 // Limit the history size to roughly sane values. This is primarily
397 // to prevent integer overflows.
398 if (history_size > UINT32_MAX / 2)
399 return LZMA_HEADER_ERROR;
401 // Store the value actually requested. We use it for sanity checks
402 // when repeating data from the history buffer.
403 lz->requested_size = history_size;
405 // Avoid tiny history buffer sizes for performance reasons.
406 // TODO: Test if this actually helps...
407 if (history_size < DICT_SIZE_MIN)
408 history_size = DICT_SIZE_MIN;
410 // The real size of the history buffer is a bit bigger than
411 // requested by our caller. This allows us to do some optimizations,
412 // which help not only speed but simplicity of the code; specifically,
413 // we can make sure that there is always at least match_max_len
414 // bytes immediatelly available for writing without a need to wrap
415 // the history buffer.
416 const size_t dict_real_size = history_size + 2 * match_max_len + 1;
418 // Reallocate memory if needed.
419 if (history_size != lz->size || match_max_len != lz->match_max_len) {
420 // Destroy the old buffer.
421 lzma_lz_decoder_end(lz, allocator);
423 lz->size = history_size;
424 lz->match_max_len = match_max_len;
425 lz->must_flush_pos = history_size + match_max_len + 1;
427 lz->dict = lzma_alloc(dict_real_size, allocator);
428 if (lz->dict == NULL)
429 return LZMA_MEM_ERROR;
432 // Reset the variables so that lz_get_byte(lz, 0) will return '\0'.
435 lz->end = dict_real_size;
436 lz->dict[dict_real_size - 1] = 0;
438 lz->eopm_detected = false;
439 lz->next_finished = false;
440 lz->this_finished = false;
443 // Clean up the temporary buffer to make it very sure that there are
444 // no information leaks when multiple steams are decoded with the
445 // same decoder structures.
446 memzero(lz->temp, LZMA_BUFFER_SIZE);
448 // Set the process function pointer.
449 lz->process = process;
456 lzma_lz_decoder_end(lzma_lz_decoder *lz, lzma_allocator *allocator)
458 lzma_free(lz->dict, allocator);
461 lz->match_max_len = 0;