]> pd.if.org Git - zpackage/blob - lzma/lz/lz_decoder.c
add missing schema file
[zpackage] / lzma / lz / lz_decoder.c
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.
95                 const size_t copy_size = coder->dict.pos - dict_start;
96                 assert(copy_size <= out_size - *out_pos);
97                 memcpy(out + *out_pos, coder->dict.buf + dict_start,
98                                 copy_size);
99                 *out_pos += copy_size;
100
101                 // Reset the dictionary if so requested by coder->lz.code().
102                 if (coder->dict.need_reset) {
103                         lz_decoder_reset(coder);
104
105                         // Since we reset dictionary, we don't check if
106                         // dictionary became full.
107                         if (ret != LZMA_OK || *out_pos == out_size)
108                                 return ret;
109                 } else {
110                         // Return if everything got decoded or an error
111                         // occurred, or if there's no more data to decode.
112                         //
113                         // Note that detecting if there's something to decode
114                         // is done by looking if dictionary become full
115                         // instead of looking if *in_pos == in_size. This
116                         // is because it is possible that all the input was
117                         // consumed already but some data is pending to be
118                         // written to the dictionary.
119                         if (ret != LZMA_OK || *out_pos == out_size
120                                         || coder->dict.pos < coder->dict.size)
121                                 return ret;
122                 }
123         }
124 }
125
126
127 static lzma_ret
128 lz_decode(void *coder_ptr,
129                 const lzma_allocator *allocator lzma_attribute((__unused__)),
130                 const uint8_t *restrict in, size_t *restrict in_pos,
131                 size_t in_size, uint8_t *restrict out,
132                 size_t *restrict out_pos, size_t out_size,
133                 lzma_action action)
134 {
135         lzma_coder *coder = coder_ptr;
136
137         if (coder->next.code == NULL)
138                 return decode_buffer(coder, in, in_pos, in_size,
139                                 out, out_pos, out_size);
140
141         // We aren't the last coder in the chain, we need to decode
142         // our input to a temporary buffer.
143         while (*out_pos < out_size) {
144                 // Fill the temporary buffer if it is empty.
145                 if (!coder->next_finished
146                                 && coder->temp.pos == coder->temp.size) {
147                         coder->temp.pos = 0;
148                         coder->temp.size = 0;
149
150                         const lzma_ret ret = coder->next.code(
151                                         coder->next.coder,
152                                         allocator, in, in_pos, in_size,
153                                         coder->temp.buffer, &coder->temp.size,
154                                         LZMA_BUFFER_SIZE, action);
155
156                         if (ret == LZMA_STREAM_END)
157                                 coder->next_finished = true;
158                         else if (ret != LZMA_OK || coder->temp.size == 0)
159                                 return ret;
160                 }
161
162                 if (coder->this_finished) {
163                         if (coder->temp.size != 0)
164                                 return LZMA_DATA_ERROR;
165
166                         if (coder->next_finished)
167                                 return LZMA_STREAM_END;
168
169                         return LZMA_OK;
170                 }
171
172                 const lzma_ret ret = decode_buffer(coder, coder->temp.buffer,
173                                 &coder->temp.pos, coder->temp.size,
174                                 out, out_pos, out_size);
175
176                 if (ret == LZMA_STREAM_END)
177                         coder->this_finished = true;
178                 else if (ret != LZMA_OK)
179                         return ret;
180                 else if (coder->next_finished && *out_pos < out_size)
181                         return LZMA_DATA_ERROR;
182         }
183
184         return LZMA_OK;
185 }
186
187
188 static void
189 lz_decoder_end(void *coder_ptr, const lzma_allocator *allocator)
190 {
191         lzma_coder *coder = coder_ptr;
192
193         lzma_next_end(&coder->next, allocator);
194         lzma_free(coder->dict.buf, allocator);
195
196         if (coder->lz.end != NULL)
197                 coder->lz.end(coder->lz.coder, allocator);
198         else
199                 lzma_free(coder->lz.coder, allocator);
200
201         lzma_free(coder, allocator);
202         return;
203 }
204
205
206 extern lzma_ret
207 lzma_lz_decoder_init(lzma_next_coder *next, const lzma_allocator *allocator,
208                 const lzma_filter_info *filters,
209                 lzma_ret (*lz_init)(lzma_lz_decoder *lz,
210                         const lzma_allocator *allocator, const void *options,
211                         lzma_lz_options *lz_options))
212 {
213         // Allocate the base structure if it isn't already allocated.
214         lzma_coder *coder = next->coder;
215         if (coder == NULL) {
216                 coder = lzma_alloc(sizeof(lzma_coder), allocator);
217                 if (coder == NULL)
218                         return LZMA_MEM_ERROR;
219
220                 next->coder = coder;
221                 next->code = &lz_decode;
222                 next->end = &lz_decoder_end;
223
224                 coder->dict.buf = NULL;
225                 coder->dict.size = 0;
226                 coder->lz = LZMA_LZ_DECODER_INIT;
227                 coder->next = LZMA_NEXT_CODER_INIT;
228         }
229
230         // Allocate and initialize the LZ-based decoder. It will also give
231         // us the dictionary size.
232         lzma_lz_options lz_options;
233         return_if_error(lz_init(&coder->lz, allocator,
234                         filters[0].options, &lz_options));
235
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
240         // corrupt files.
241         if (lz_options.dict_size < 4096)
242                 lz_options.dict_size = 4096;
243
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.
249         //
250         // Avoid integer overflow.
251         if (lz_options.dict_size > SIZE_MAX - 15)
252                 return LZMA_MEM_ERROR;
253
254         lz_options.dict_size = (lz_options.dict_size + 15) & ~((size_t)(15));
255
256         // Allocate and initialize the dictionary.
257         if (coder->dict.size != lz_options.dict_size) {
258                 lzma_free(coder->dict.buf, allocator);
259                 coder->dict.buf
260                                 = lzma_alloc(lz_options.dict_size, allocator);
261                 if (coder->dict.buf == NULL)
262                         return LZMA_MEM_ERROR;
263
264                 coder->dict.size = lz_options.dict_size;
265         }
266
267         lz_decoder_reset(next->coder);
268
269         // Use the preset dictionary if it was given to us.
270         if (lz_options.preset_dict != NULL
271                         && lz_options.preset_dict_size > 0) {
272                 // If the preset dictionary is bigger than the actual
273                 // dictionary, copy only the tail.
274                 const size_t copy_size = my_min(lz_options.preset_dict_size,
275                                 lz_options.dict_size);
276                 const size_t offset = lz_options.preset_dict_size - copy_size;
277                 memcpy(coder->dict.buf, lz_options.preset_dict + offset,
278                                 copy_size);
279                 coder->dict.pos = copy_size;
280                 coder->dict.full = copy_size;
281         }
282
283         // Miscellaneous initializations
284         coder->next_finished = false;
285         coder->this_finished = false;
286         coder->temp.pos = 0;
287         coder->temp.size = 0;
288
289         // Initialize the next filter in the chain, if any.
290         return lzma_next_filter_init(&coder->next, allocator, filters + 1);
291 }
292
293
294 extern uint64_t
295 lzma_lz_decoder_memusage(size_t dictionary_size)
296 {
297         return sizeof(lzma_coder) + (uint64_t)(dictionary_size);
298 }
299
300
301 extern void
302 lzma_lz_decoder_uncompressed(void *coder_ptr, lzma_vli uncompressed_size)
303 {
304         lzma_coder *coder = coder_ptr;
305         coder->lz.set_uncompressed(coder->lz.coder, uncompressed_size);
306 }