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 } 307