contrib/xz/src/liblzma/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 struct lzma_coder_s {
  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 };
  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(lzma_coder *coder,
 129                 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         if (coder->next.code == NULL)
 136                 return decode_buffer(coder, in, in_pos, in_size,
 137                                 out, out_pos, out_size);
 138
 139         // We aren't the last coder in the chain, we need to decode
 140         // our input to a temporary buffer.
 141         while (*out_pos < out_size) {
 142                 // Fill the temporary buffer if it is empty.
 143                 if (!coder->next_finished
 144                                 && coder->temp.pos == coder->temp.size) {
 145                         coder->temp.pos = 0;
 146                         coder->temp.size = 0;
 147
 148                         const lzma_ret ret = coder->next.code(
 149                                         coder->next.coder,
 150                                         allocator, in, in_pos, in_size,
 151                                         coder->temp.buffer, &coder->temp.size,
 152                                         LZMA_BUFFER_SIZE, action);
 153
 154                         if (ret == LZMA_STREAM_END)
 155                                 coder->next_finished = true;
 156                         else if (ret != LZMA_OK || coder->temp.size == 0)
 157                                 return ret;
 158                 }
 159
 160                 if (coder->this_finished) {
 161                         if (coder->temp.size != 0)
 162                                 return LZMA_DATA_ERROR;
 163
 164                         if (coder->next_finished)
 165                                 return LZMA_STREAM_END;
 166
 167                         return LZMA_OK;
 168                 }
 169
 170                 const lzma_ret ret = decode_buffer(coder, coder->temp.buffer,
 171                                 &coder->temp.pos, coder->temp.size,
 172                                 out, out_pos, out_size);
 173
 174                 if (ret == LZMA_STREAM_END)
 175                         coder->this_finished = true;
 176                 else if (ret != LZMA_OK)
 177                         return ret;
 178                 else if (coder->next_finished && *out_pos < out_size)
 179                         return LZMA_DATA_ERROR;
 180         }
 181
 182         return LZMA_OK;
 183 }
 184
 185
 186 static void
 187 lz_decoder_end(lzma_coder *coder, lzma_allocator *allocator)
 188 {
 189         lzma_next_end(&coder->next, allocator);
 190         lzma_free(coder->dict.buf, allocator);
 191
 192         if (coder->lz.end != NULL)
 193                 coder->lz.end(coder->lz.coder, allocator);
 194         else
 195                 lzma_free(coder->lz.coder, allocator);
 196
 197         lzma_free(coder, allocator);
 198         return;
 199 }
 200
 201
 202 extern lzma_ret
 203 lzma_lz_decoder_init(lzma_next_coder *next, lzma_allocator *allocator,
 204                 const lzma_filter_info *filters,
 205                 lzma_ret (*lz_init)(lzma_lz_decoder *lz,
 206                         lzma_allocator *allocator, const void *options,
 207                         lzma_lz_options *lz_options))
 208 {
 209         // Allocate the base structure if it isn't already allocated.
 210         if (next->coder == NULL) {
 211                 next->coder = lzma_alloc(sizeof(lzma_coder), allocator);
 212                 if (next->coder == NULL)
 213                         return LZMA_MEM_ERROR;
 214
 215                 next->code = &lz_decode;
 216                 next->end = &lz_decoder_end;
 217
 218                 next->coder->dict.buf = NULL;
 219                 next->coder->dict.size = 0;
 220                 next->coder->lz = LZMA_LZ_DECODER_INIT;
 221                 next->coder->next = LZMA_NEXT_CODER_INIT;
 222         }
 223
 224         // Allocate and initialize the LZ-based decoder. It will also give
 225         // us the dictionary size.
 226         lzma_lz_options lz_options;
 227         return_if_error(lz_init(&next->coder->lz, allocator,
 228                         filters[0].options, &lz_options));
 229
 230         // If the dictionary size is very small, increase it to 4096 bytes.
 231         // This is to prevent constant wrapping of the dictionary, which
 232         // would slow things down. The downside is that since we don't check
 233         // separately for the real dictionary size, we may happily accept
 234         // corrupt files.
 235         if (lz_options.dict_size < 4096)
 236                 lz_options.dict_size = 4096;
 237
 238         // Make dictionary size a multipe of 16. Some LZ-based decoders like
 239         // LZMA use the lowest bits lzma_dict.pos to know the alignment of the
 240         // data. Aligned buffer is also good when memcpying from the
 241         // dictionary to the output buffer, since applications are
 242         // recommended to give aligned buffers to liblzma.
 243         //
 244         // Avoid integer overflow.
 245         if (lz_options.dict_size > SIZE_MAX - 15)
 246                 return LZMA_MEM_ERROR;
 247
 248         lz_options.dict_size = (lz_options.dict_size + 15) & ~((size_t)(15));
 249
 250         // Allocate and initialize the dictionary.
 251         if (next->coder->dict.size != lz_options.dict_size) {
 252                 lzma_free(next->coder->dict.buf, allocator);
 253                 next->coder->dict.buf
 254                                 = lzma_alloc(lz_options.dict_size, allocator);
 255                 if (next->coder->dict.buf == NULL)
 256                         return LZMA_MEM_ERROR;
 257
 258                 next->coder->dict.size = lz_options.dict_size;
 259         }
 260
 261         lz_decoder_reset(next->coder);
 262
 263         // Use the preset dictionary if it was given to us.
 264         if (lz_options.preset_dict != NULL
 265                         && lz_options.preset_dict_size > 0) {
 266                 // If the preset dictionary is bigger than the actual
 267                 // dictionary, copy only the tail.
 268                 const size_t copy_size = my_min(lz_options.preset_dict_size,
 269                                 lz_options.dict_size);
 270                 const size_t offset = lz_options.preset_dict_size - copy_size;
 271                 memcpy(next->coder->dict.buf, lz_options.preset_dict + offset,
 272                                 copy_size);
 273                 next->coder->dict.pos = copy_size;
 274                 next->coder->dict.full = copy_size;
 275         }
 276
 277         // Miscellaneous initializations
 278         next->coder->next_finished = false;
 279         next->coder->this_finished = false;
 280         next->coder->temp.pos = 0;
 281         next->coder->temp.size = 0;
 282
 283         // Initialize the next filter in the chain, if any.
 284         return lzma_next_filter_init(&next->coder->next, allocator,
 285                         filters + 1);
 286 }
 287
 288
 289 extern uint64_t
 290 lzma_lz_decoder_memusage(size_t dictionary_size)
 291 {
 292         return sizeof(lzma_coder) + (uint64_t)(dictionary_size);
 293 }
 294
 295
 296 extern void
 297 lzma_lz_decoder_uncompressed(lzma_coder *coder, lzma_vli uncompressed_size)
 298 {
 299         coder->lz.set_uncompressed(coder->lz.coder, uncompressed_size);
 300 }