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 // liblzma supports multiple LZ77-based filters. The LZ part is shared
22 // between these filters. The LZ code takes care of dictionary handling
23 // and passing the data between filters in the chain. The filter-specific
24 // part decodes from the input buffer to the dictionary.
27 #include "lz_decoder.h"
31 /// Dictionary (history buffer)
34 /// The actual LZ-based decoder e.g. LZMA
37 /// Next filter in the chain, if any. Note that LZMA and LZMA2 are
38 /// only allowed as the last filter, but the long-range filter in
39 /// future can be in the middle of the chain.
42 /// True if the next filter in the chain has returned LZMA_STREAM_END.
45 /// True if the LZ decoder (e.g. LZMA) has detected end of payload
46 /// marker. This may become true before next_finished becomes true.
49 /// Temporary buffer needed when the LZ-based filter is not the last
50 /// filter in the chain. The output of the next filter is first
51 /// decoded into buffer[], which is then used as input for the actual
56 uint8_t buffer[LZMA_BUFFER_SIZE];
62 lz_decoder_reset(lzma_coder *coder)
66 coder->dict.buf[coder->dict.size - 1] = '\0';
67 coder->dict.need_reset = false;
73 decode_buffer(lzma_coder *coder,
74 const uint8_t *restrict in, size_t *restrict in_pos,
75 size_t in_size, uint8_t *restrict out,
76 size_t *restrict out_pos, size_t out_size)
79 // Wrap the dictionary if needed.
80 if (coder->dict.pos == coder->dict.size)
83 // Store the current dictionary position. It is needed to know
84 // where to start copying to the out[] buffer.
85 const size_t dict_start = coder->dict.pos;
87 // Calculate how much we allow coder->lz.code() to decode.
88 // It must not decode past the end of the dictionary
89 // buffer, and we don't want it to decode more than is
90 // actually needed to fill the out[] buffer.
91 coder->dict.limit = coder->dict.pos + MIN(out_size - *out_pos,
92 coder->dict.size - coder->dict.pos);
94 // Call the coder->lz.code() to do the actual decoding.
95 const lzma_ret ret = coder->lz.code(
96 coder->lz.coder, &coder->dict,
99 // Copy the decoded data from the dictionary to the out[]
101 const size_t copy_size = coder->dict.pos - dict_start;
102 assert(copy_size <= out_size - *out_pos);
103 memcpy(out + *out_pos, coder->dict.buf + dict_start,
105 *out_pos += copy_size;
107 // Reset the dictionary if so requested by coder->lz.code().
108 if (coder->dict.need_reset) {
109 lz_decoder_reset(coder);
111 // Since we reset dictionary, we don't check if
112 // dictionary became full.
113 if (ret != LZMA_OK || *out_pos == out_size)
116 // Return if everything got decoded or an error
117 // occurred, or if there's no more data to decode.
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)
134 lz_decode(lzma_coder *coder,
135 lzma_allocator *allocator lzma_attribute((unused)),
136 const uint8_t *restrict in, size_t *restrict in_pos,
137 size_t in_size, uint8_t *restrict out,
138 size_t *restrict out_pos, size_t out_size,
141 if (coder->next.code == NULL)
142 return decode_buffer(coder, in, in_pos, in_size,
143 out, out_pos, out_size);
145 // We aren't the last coder in the chain, we need to decode
146 // our input to a temporary buffer.
147 while (*out_pos < out_size) {
148 // Fill the temporary buffer if it is empty.
149 if (!coder->next_finished
150 && coder->temp.pos == coder->temp.size) {
152 coder->temp.size = 0;
154 const lzma_ret ret = coder->next.code(
156 allocator, in, in_pos, in_size,
157 coder->temp.buffer, &coder->temp.size,
158 LZMA_BUFFER_SIZE, action);
160 if (ret == LZMA_STREAM_END)
161 coder->next_finished = true;
162 else if (ret != LZMA_OK || coder->temp.size == 0)
166 if (coder->this_finished) {
167 if (coder->temp.size != 0)
168 return LZMA_DATA_ERROR;
170 if (coder->next_finished)
171 return LZMA_STREAM_END;
176 const lzma_ret ret = decode_buffer(coder, coder->temp.buffer,
177 &coder->temp.pos, coder->temp.size,
178 out, out_pos, out_size);
180 if (ret == LZMA_STREAM_END)
181 coder->this_finished = true;
182 else if (ret != LZMA_OK)
184 else if (coder->next_finished && *out_pos < out_size)
185 return LZMA_DATA_ERROR;
193 lz_decoder_end(lzma_coder *coder, lzma_allocator *allocator)
195 lzma_next_end(&coder->next, allocator);
196 lzma_free(coder->dict.buf, allocator);
198 if (coder->lz.end != NULL)
199 coder->lz.end(coder->lz.coder, allocator);
201 lzma_free(coder->lz.coder, allocator);
203 lzma_free(coder, allocator);
209 lzma_lz_decoder_init(lzma_next_coder *next, lzma_allocator *allocator,
210 const lzma_filter_info *filters,
211 lzma_ret (*lz_init)(lzma_lz_decoder *lz,
212 lzma_allocator *allocator, const void *options,
215 // Allocate the base structure if it isn't already allocated.
216 if (next->coder == NULL) {
217 next->coder = lzma_alloc(sizeof(lzma_coder), allocator);
218 if (next->coder == NULL)
219 return LZMA_MEM_ERROR;
221 next->code = &lz_decode;
222 next->end = &lz_decoder_end;
224 next->coder->dict.buf = NULL;
225 next->coder->dict.size = 0;
226 next->coder->lz = LZMA_LZ_DECODER_INIT;
227 next->coder->next = LZMA_NEXT_CODER_INIT;
230 // Allocate and initialize the LZ-based decoder. It will also give
231 // us the dictionary size.
233 return_if_error(lz_init(&next->coder->lz, allocator,
234 filters[0].options, &dict_size));
236 // If the dictionary size is very small, increase it to 4096 bytes.
237 // This is to prevent constant wrapping of the dictionary, which
238 // would slow things down. The downside is that since we don't check
239 // separately for the real dictionary size, we may happily accept
241 if (dict_size < 4096)
244 // Make dictionary size a multipe of 16. Some LZ-based decoders like
245 // LZMA use the lowest bits lzma_dict.pos to know the alignment of the
246 // data. Aligned buffer is also good when memcpying from the
247 // dictionary to the output buffer, since applications are
248 // recommended to give aligned buffers to liblzma.
250 // Avoid integer overflow.
251 if (dict_size > SIZE_MAX - 15)
252 return LZMA_MEM_ERROR;
254 dict_size = (dict_size + 15) & ~((size_t)(15));
256 // Allocate and initialize the dictionary.
257 if (next->coder->dict.size != dict_size) {
258 lzma_free(next->coder->dict.buf, allocator);
259 next->coder->dict.buf = lzma_alloc(dict_size, allocator);
260 if (next->coder->dict.buf == NULL)
261 return LZMA_MEM_ERROR;
263 next->coder->dict.size = dict_size;
266 lz_decoder_reset(next->coder);
268 // Miscellaneous initializations
269 next->coder->next_finished = false;
270 next->coder->this_finished = false;
271 next->coder->temp.pos = 0;
272 next->coder->temp.size = 0;
274 // Initialize the next filter in the chain, if any.
275 return lzma_next_filter_init(&next->coder->next, allocator,
281 lzma_lz_decoder_memusage(size_t dictionary_size)
283 return sizeof(lzma_coder) + (uint64_t)(dictionary_size);
288 lzma_lz_decoder_uncompressed(lzma_coder *coder, lzma_vli uncompressed_size)
290 coder->lz.set_uncompressed(coder->lz.coder, uncompressed_size);