1 ///////////////////////////////////////////////////////////////////////////////
4 /// \brief LZ out window
6 // Authors: Igor Pavlov
9 // This file has been put into the public domain.
10 // You can do whatever you want with this file.
12 ///////////////////////////////////////////////////////////////////////////////
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.
20 #include "lz_decoder.h"
24 /// Dictionary (history buffer)
27 /// The actual LZ-based decoder e.g. LZMA
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.
35 /// True if the next filter in the chain has returned LZMA_STREAM_END.
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.
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
49 uint8_t buffer[LZMA_BUFFER_SIZE];
55 lz_decoder_reset(lzma_coder *coder)
59 coder->dict.buf[coder->dict.size - 1] = '\0';
60 coder->dict.need_reset = false;
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)
72 // Wrap the dictionary if needed.
73 if (coder->dict.pos == coder->dict.size)
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;
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 + MIN(out_size - *out_pos,
85 coder->dict.size - coder->dict.pos);
87 // Call the coder->lz.code() to do the actual decoding.
88 const lzma_ret ret = coder->lz.code(
89 coder->lz.coder, &coder->dict,
92 // Copy the decoded data from the dictionary to the out[]
94 const size_t copy_size = coder->dict.pos - dict_start;
95 assert(copy_size <= out_size - *out_pos);
96 memcpy(out + *out_pos, coder->dict.buf + dict_start,
98 *out_pos += copy_size;
100 // Reset the dictionary if so requested by coder->lz.code().
101 if (coder->dict.need_reset) {
102 lz_decoder_reset(coder);
104 // Since we reset dictionary, we don't check if
105 // dictionary became full.
106 if (ret != LZMA_OK || *out_pos == out_size)
109 // Return if everything got decoded or an error
110 // occurred, or if there's no more data to decode.
112 // Note that detecting if there's something to decode
113 // is done by looking if dictionary become full
114 // instead of looking if *in_pos == in_size. This
115 // is because it is possible that all the input was
116 // consumed already but some data is pending to be
117 // written to the dictionary.
118 if (ret != LZMA_OK || *out_pos == out_size
119 || coder->dict.pos < coder->dict.size)
127 lz_decode(lzma_coder *coder,
128 lzma_allocator *allocator lzma_attribute((unused)),
129 const uint8_t *restrict in, size_t *restrict in_pos,
130 size_t in_size, uint8_t *restrict out,
131 size_t *restrict out_pos, size_t out_size,
134 if (coder->next.code == NULL)
135 return decode_buffer(coder, in, in_pos, in_size,
136 out, out_pos, out_size);
138 // We aren't the last coder in the chain, we need to decode
139 // our input to a temporary buffer.
140 while (*out_pos < out_size) {
141 // Fill the temporary buffer if it is empty.
142 if (!coder->next_finished
143 && coder->temp.pos == coder->temp.size) {
145 coder->temp.size = 0;
147 const lzma_ret ret = coder->next.code(
149 allocator, in, in_pos, in_size,
150 coder->temp.buffer, &coder->temp.size,
151 LZMA_BUFFER_SIZE, action);
153 if (ret == LZMA_STREAM_END)
154 coder->next_finished = true;
155 else if (ret != LZMA_OK || coder->temp.size == 0)
159 if (coder->this_finished) {
160 if (coder->temp.size != 0)
161 return LZMA_DATA_ERROR;
163 if (coder->next_finished)
164 return LZMA_STREAM_END;
169 const lzma_ret ret = decode_buffer(coder, coder->temp.buffer,
170 &coder->temp.pos, coder->temp.size,
171 out, out_pos, out_size);
173 if (ret == LZMA_STREAM_END)
174 coder->this_finished = true;
175 else if (ret != LZMA_OK)
177 else if (coder->next_finished && *out_pos < out_size)
178 return LZMA_DATA_ERROR;
186 lz_decoder_end(lzma_coder *coder, lzma_allocator *allocator)
188 lzma_next_end(&coder->next, allocator);
189 lzma_free(coder->dict.buf, allocator);
191 if (coder->lz.end != NULL)
192 coder->lz.end(coder->lz.coder, allocator);
194 lzma_free(coder->lz.coder, allocator);
196 lzma_free(coder, allocator);
202 lzma_lz_decoder_init(lzma_next_coder *next, lzma_allocator *allocator,
203 const lzma_filter_info *filters,
204 lzma_ret (*lz_init)(lzma_lz_decoder *lz,
205 lzma_allocator *allocator, const void *options,
206 lzma_lz_options *lz_options))
208 // Allocate the base structure if it isn't already allocated.
209 if (next->coder == NULL) {
210 next->coder = lzma_alloc(sizeof(lzma_coder), allocator);
211 if (next->coder == NULL)
212 return LZMA_MEM_ERROR;
214 next->code = &lz_decode;
215 next->end = &lz_decoder_end;
217 next->coder->dict.buf = NULL;
218 next->coder->dict.size = 0;
219 next->coder->lz = LZMA_LZ_DECODER_INIT;
220 next->coder->next = LZMA_NEXT_CODER_INIT;
223 // Allocate and initialize the LZ-based decoder. It will also give
224 // us the dictionary size.
225 lzma_lz_options lz_options;
226 return_if_error(lz_init(&next->coder->lz, allocator,
227 filters[0].options, &lz_options));
229 // If the dictionary size is very small, increase it to 4096 bytes.
230 // This is to prevent constant wrapping of the dictionary, which
231 // would slow things down. The downside is that since we don't check
232 // separately for the real dictionary size, we may happily accept
234 if (lz_options.dict_size < 4096)
235 lz_options.dict_size = 4096;
237 // Make dictionary size a multipe of 16. Some LZ-based decoders like
238 // LZMA use the lowest bits lzma_dict.pos to know the alignment of the
239 // data. Aligned buffer is also good when memcpying from the
240 // dictionary to the output buffer, since applications are
241 // recommended to give aligned buffers to liblzma.
243 // Avoid integer overflow.
244 if (lz_options.dict_size > SIZE_MAX - 15)
245 return LZMA_MEM_ERROR;
247 lz_options.dict_size = (lz_options.dict_size + 15) & ~((size_t)(15));
249 // Allocate and initialize the dictionary.
250 if (next->coder->dict.size != lz_options.dict_size) {
251 lzma_free(next->coder->dict.buf, allocator);
252 next->coder->dict.buf
253 = lzma_alloc(lz_options.dict_size, allocator);
254 if (next->coder->dict.buf == NULL)
255 return LZMA_MEM_ERROR;
257 next->coder->dict.size = lz_options.dict_size;
260 lz_decoder_reset(next->coder);
262 // Use the preset dictionary if it was given to us.
263 if (lz_options.preset_dict != NULL
264 && lz_options.preset_dict_size > 0) {
265 // If the preset dictionary is bigger than the actual
266 // dictionary, copy only the tail.
267 const size_t copy_size = MIN(lz_options.preset_dict_size,
268 lz_options.dict_size);
269 const size_t offset = lz_options.preset_dict_size - copy_size;
270 memcpy(next->coder->dict.buf, lz_options.preset_dict + offset,
272 next->coder->dict.pos = copy_size;
273 next->coder->dict.full = copy_size;
276 // Miscellaneous initializations
277 next->coder->next_finished = false;
278 next->coder->this_finished = false;
279 next->coder->temp.pos = 0;
280 next->coder->temp.size = 0;
282 // Initialize the next filter in the chain, if any.
283 return lzma_next_filter_init(&next->coder->next, allocator,
289 lzma_lz_decoder_memusage(size_t dictionary_size)
291 return sizeof(lzma_coder) + (uint64_t)(dictionary_size);
296 lzma_lz_decoder_uncompressed(lzma_coder *coder, lzma_vli uncompressed_size)
298 coder->lz.set_uncompressed(coder->lz.coder, uncompressed_size);