src/liblzma/lz/lz_decoder.c

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //
   3 /// \file       lz_decoder.c
   4 /// \brief      LZ out window
   5 //
   6 //  Copyright (C) 1999-2006 Igor Pavlov
   7 //  Copyright (C) 2007 Lasse Collin
   8 //
   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.
  13 //
  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.
  18 //
  19 ///////////////////////////////////////////////////////////////////////////////
  20
  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.
  25
  26
  27 #include "lz_decoder.h"
  28
  29
  30 struct lzma_coder_s {
  31         /// Dictionary (history buffer)
  32         lzma_dict dict;
  33
  34         /// The actual LZ-based decoder e.g. LZMA
  35         lzma_lz_decoder lz;
  36
  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.
  40         lzma_next_coder next;
  41
  42         /// True if the next filter in the chain has returned LZMA_STREAM_END.
  43         bool next_finished;
  44
  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.
  47         bool this_finished;
  48
  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
  52         /// LZ-based decoder.
  53         struct {
  54                 size_t pos;
  55                 size_t size;
  56                 uint8_t buffer[LZMA_BUFFER_SIZE];
  57         } temp;
  58 };
  59
  60
  61 static void
  62 lz_decoder_reset(lzma_coder *coder)
  63 {
  64         coder->dict.pos = 0;
  65         coder->dict.full = 0;
  66         coder->dict.buf[coder->dict.size - 1] = '\0';
  67         coder->dict.need_reset = false;
  68         return;
  69 }
  70
  71
  72 static lzma_ret
  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)
  77 {
  78         while (true) {
  79                 // Wrap the dictionary if needed.
  80                 if (coder->dict.pos == coder->dict.size)
  81                         coder->dict.pos = 0;
  82
  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;
  86
  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);
  93
  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,
  97                                 in, in_pos, in_size);
  98
  99                 // Copy the decoded data from the dictionary to the out[]
 100                 // buffer.
 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,
 104                                 copy_size);
 105                 *out_pos += copy_size;
 106
 107                 // Reset the dictionary if so requested by coder->lz.code().
 108                 if (coder->dict.need_reset) {
 109                         lz_decoder_reset(coder);
 110
 111                         // Since we reset dictionary, we don't check if
 112                         // dictionary became full.
 113                         if (ret != LZMA_OK || *out_pos == out_size)
 114                                 return ret;
 115                 } else {
 116                         // Return if everything got decoded or an error
 117                         // occurred, or if there's no more data to decode.
 118                         //
 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)
 127                                 return ret;
 128                 }
 129         }
 130 }
 131
 132
 133 static lzma_ret
 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,
 139                 lzma_action action)
 140 {
 141         if (coder->next.code == NULL)
 142                 return decode_buffer(coder, in, in_pos, in_size,
 143                                 out, out_pos, out_size);
 144
 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) {
 151                         coder->temp.pos = 0;
 152                         coder->temp.size = 0;
 153
 154                         const lzma_ret ret = coder->next.code(
 155                                         coder->next.coder,
 156                                         allocator, in, in_pos, in_size,
 157                                         coder->temp.buffer, &coder->temp.size,
 158                                         LZMA_BUFFER_SIZE, action);
 159
 160                         if (ret == LZMA_STREAM_END)
 161                                 coder->next_finished = true;
 162                         else if (ret != LZMA_OK || coder->temp.size == 0)
 163                                 return ret;
 164                 }
 165
 166                 if (coder->this_finished) {
 167                         if (coder->temp.size != 0)
 168                                 return LZMA_DATA_ERROR;
 169
 170                         if (coder->next_finished)
 171                                 return LZMA_STREAM_END;
 172
 173                         return LZMA_OK;
 174                 }
 175
 176                 const lzma_ret ret = decode_buffer(coder, coder->temp.buffer,
 177                                 &coder->temp.pos, coder->temp.size,
 178                                 out, out_pos, out_size);
 179
 180                 if (ret == LZMA_STREAM_END)
 181                         coder->this_finished = true;
 182                 else if (ret != LZMA_OK)
 183                         return ret;
 184                 else if (coder->next_finished && *out_pos < out_size)
 185                         return LZMA_DATA_ERROR;
 186         }
 187
 188         return LZMA_OK;
 189 }
 190
 191
 192 static void
 193 lz_decoder_end(lzma_coder *coder, lzma_allocator *allocator)
 194 {
 195         lzma_next_end(&coder->next, allocator);
 196         lzma_free(coder->dict.buf, allocator);
 197
 198         if (coder->lz.end != NULL)
 199                 coder->lz.end(coder->lz.coder, allocator);
 200         else
 201                 lzma_free(coder->lz.coder, allocator);
 202
 203         lzma_free(coder, allocator);
 204         return;
 205 }
 206
 207
 208 extern lzma_ret
 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,
 213                         size_t *dict_size))
 214 {
 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;
 220
 221                 next->code = &lz_decode;
 222                 next->end = &lz_decoder_end;
 223
 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;
 228         }
 229
 230         // Allocate and initialize the LZ-based decoder. It will also give
 231         // us the dictionary size.
 232         size_t dict_size;
 233         return_if_error(lz_init(&next->coder->lz, allocator,
 234                         filters[0].options, &dict_size));
 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 (dict_size < 4096)
 242                 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 (dict_size > SIZE_MAX - 15)
 252                 return LZMA_MEM_ERROR;
 253
 254         dict_size = (dict_size + 15) & ~((size_t)(15));
 255
 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;
 262
 263                 next->coder->dict.size = dict_size;
 264         }
 265
 266         lz_decoder_reset(next->coder);
 267
 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;
 273
 274         // Initialize the next filter in the chain, if any.
 275         return lzma_next_filter_init(&next->coder->next, allocator,
 276                         filters + 1);
 277 }
 278
 279
 280 extern uint64_t
 281 lzma_lz_decoder_memusage(size_t dictionary_size)
 282 {
 283         return sizeof(lzma_coder) + (uint64_t)(dictionary_size);
 284 }
 285
 286
 287 extern void
 288 lzma_lz_decoder_uncompressed(lzma_coder *coder, lzma_vli uncompressed_size)
 289 {
 290         coder->lz.set_uncompressed(coder->lz.coder, uncompressed_size);
 291 }