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 #include "lz_decoder.h"
  22
  23
  24 /// Minimum size of allocated dictionary
  25 #define DICT_SIZE_MIN 8192
  26
  27 /// When there is less than this amount of data available for decoding,
  28 /// it is moved to the temporary buffer which
  29 ///   - protects from reads past the end of the buffer; and
  30 ///   - stored the incomplete data between lzma_code() calls.
  31 ///
  32 /// \note       TEMP_LIMIT must be at least as much as
  33 ///             REQUIRED_IN_BUFFER_SIZE defined in lzma_decoder.c.
  34 #define TEMP_LIMIT 32
  35
  36 // lzma_lz_decoder.dict[] must be three times the size of TEMP_LIMIT.
  37 // 2 * TEMP_LIMIT is used for the actual data, and the third TEMP_LIMIT
  38 // bytes is needed for safety to allow decode_dummy() in lzma_decoder.c
  39 // to read past end of the buffer. This way it should be both fast and simple.
  40 #if LZMA_BUFFER_SIZE < 3 * TEMP_LIMIT
  41 #       error LZMA_BUFFER_SIZE < 3 * TEMP_LIMIT
  42 #endif
  43
  44
  45 struct lzma_coder_s {
  46         lzma_next_coder next;
  47         lzma_lz_decoder lz;
  48
  49         // There are more members in this structure but they are not
  50         // visible in LZ coder.
  51 };
  52
  53
  54 /// - Copy as much data as possible from lz->dict[] to out[].
  55 /// - Update *out_pos, lz->start, and lz->end accordingly.
  56 /// - Wrap lz-pos to the beginning of lz->dict[] if there is a danger that
  57 ///   it may go past the end of the buffer (lz->pos >= lz->must_flush_pos).
  58 static inline bool
  59 flush(lzma_lz_decoder *restrict lz, uint8_t *restrict out,
  60                 size_t *restrict out_pos, size_t out_size)
  61 {
  62         // Flush uncompressed data from the history buffer to
  63         // the output buffer. This is done in two phases.
  64
  65         assert(lz->start <= lz->end);
  66
  67         // Flush if pos < start < end.
  68         if (lz->pos < lz->start && lz->start < lz->end) {
  69                 bufcpy(lz->dict, &lz->start, lz->end, out, out_pos, out_size);
  70
  71                 // If we reached end of the data in history buffer,
  72                 // wrap to the beginning.
  73                 if (lz->start == lz->end)
  74                         lz->start = 0;
  75         }
  76
  77         // Flush if start start < pos <= end. This is not as `else' for
  78         // previous `if' because the previous one may make this one true.
  79         if (lz->start < lz->pos) {
  80                 bufcpy(lz->dict, &lz->start,
  81                                 lz->pos, out, out_pos, out_size);
  82
  83                 if (lz->pos >= lz->must_flush_pos) {
  84                         // Wrap the flushing position if we have
  85                         // flushed the whole history buffer.
  86                         if (lz->pos == lz->start)
  87                                 lz->start = 0;
  88
  89                         // Wrap the write position and store to lz.end
  90                         // how much there is new data available.
  91                         lz->end = lz->pos;
  92                         lz->pos = 0;
  93                         lz->is_full = true;
  94                 }
  95         }
  96
  97         assert(lz->pos < lz->must_flush_pos);
  98
  99         return *out_pos == out_size;
 100 }
 101
 102
 103 /// Calculate safe value for lz->limit. If no safe value can be found,
 104 /// set lz->limit to zero. When flushing, only as little data will be
 105 /// decoded as is needed to fill the output buffer (lowers both latency
 106 /// and throughput).
 107 ///
 108 /// \return     true if there is no space for new uncompressed data.
 109 ///
 110 static inline bool
 111 set_limit(lzma_lz_decoder *lz, size_t out_avail, bool flushing)
 112 {
 113         // Set the limit so that writing to dict[limit + match_max_len - 1]
 114         // doesn't overwrite any unflushed data and doesn't write past the
 115         // end of the dict buffer.
 116         if (lz->start <= lz->pos) {
 117                 // We can fill the buffer from pos till the end
 118                 // of the dict buffer.
 119                 lz->limit = lz->must_flush_pos;
 120         } else if (lz->pos + lz->match_max_len < lz->start) {
 121                 // There's some unflushed data between pos and end of the
 122                 // buffer. Limit so that we don't overwrite the unflushed data.
 123                 lz->limit = lz->start - lz->match_max_len;
 124         } else {
 125                 // Buffer is too full.
 126                 lz->limit = 0;
 127                 return true;
 128         }
 129
 130         // Finetune the limit a bit if it isn't zero.
 131
 132         assert(lz->limit > lz->pos);
 133         const size_t dict_avail = lz->limit - lz->pos;
 134
 135         if (lz->uncompressed_size < dict_avail) {
 136                 // Finishing a stream that doesn't have
 137                 // an end of stream marker.
 138                 lz->limit = lz->pos + lz->uncompressed_size;
 139
 140         } else if (flushing && out_avail < dict_avail) {
 141                 // Flushing enabled, decoding only as little as needed to
 142                 // fill the out buffer (if there's enough input, of course).
 143                 lz->limit = lz->pos + out_avail;
 144         }
 145
 146         return lz->limit == lz->pos;
 147 }
 148
 149
 150 /// Takes care of wrapping the data into temporary buffer when needed,
 151 /// and calls the actual decoder.
 152 ///
 153 /// \return     true if error occurred
 154 ///
 155 static inline bool
 156 call_process(lzma_coder *restrict coder, const uint8_t *restrict in,
 157                 size_t *restrict in_pos, size_t in_size)
 158 {
 159         // It would be nice and simple if we could just give in[] to the
 160         // decoder, but the requirement of zlib-like API forces us to be
 161         // able to make *in_pos == in_size whenever there is enough output
 162         // space. If needed, we will append a few bytes from in[] to
 163         // a temporary buffer and decode enough to reach the part that
 164         // was copied from in[]. Then we can continue with the real in[].
 165
 166         bool error;
 167         const size_t dict_old_pos = coder->lz.pos;
 168         const size_t in_avail = in_size - *in_pos;
 169
 170         if (coder->lz.temp_size + in_avail < 2 * TEMP_LIMIT) {
 171                 // Copy all the available input from in[] to temp[].
 172                 memcpy(coder->lz.temp + coder->lz.temp_size,
 173                                 in + *in_pos, in_avail);
 174                 coder->lz.temp_size += in_avail;
 175                 *in_pos += in_avail;
 176                 assert(*in_pos == in_size);
 177
 178                 // Decode as much as possible.
 179                 size_t temp_used = 0;
 180                 error = coder->lz.process(coder, coder->lz.temp, &temp_used,
 181                                 coder->lz.temp_size, true);
 182                 assert(temp_used <= coder->lz.temp_size);
 183
 184                 // Move the remaining data to the beginning of temp[].
 185                 coder->lz.temp_size -= temp_used;
 186                 memmove(coder->lz.temp, coder->lz.temp + temp_used,
 187                                 coder->lz.temp_size);
 188
 189         } else if (coder->lz.temp_size > 0) {
 190                 // Fill temp[] unless it is already full because we aren't
 191                 // the last filter in the chain.
 192                 size_t copy_size = 0;
 193                 if (coder->lz.temp_size < 2 * TEMP_LIMIT) {
 194                         assert(*in_pos < in_size);
 195                         copy_size = 2 * TEMP_LIMIT - coder->lz.temp_size;
 196                         memcpy(coder->lz.temp + coder->lz.temp_size,
 197                                         in + *in_pos, copy_size);
 198                         // NOTE: We don't update lz.temp_size or *in_pos yet.
 199                 }
 200
 201                 size_t temp_used = 0;
 202                 error = coder->lz.process(coder, coder->lz.temp, &temp_used,
 203                                 coder->lz.temp_size + copy_size, false);
 204
 205                 if (temp_used < coder->lz.temp_size) {
 206                         // Only very little input data was consumed. Move
 207                         // the unprocessed data to the beginning temp[].
 208                         coder->lz.temp_size += copy_size - temp_used;
 209                         memmove(coder->lz.temp, coder->lz.temp + temp_used,
 210                                         coder->lz.temp_size);
 211                         *in_pos += copy_size;
 212                         assert(*in_pos <= in_size);
 213
 214                 } else {
 215                         // We were able to decode so much data that next time
 216                         // we can decode directly from in[]. That is, we can
 217                         // consider temp[] to be empty now.
 218                         *in_pos += temp_used - coder->lz.temp_size;
 219                         coder->lz.temp_size = 0;
 220                         assert(*in_pos <= in_size);
 221                 }
 222
 223         } else {
 224                 // Decode directly from in[].
 225                 error = coder->lz.process(coder, in, in_pos, in_size, false);
 226                 assert(*in_pos <= in_size);
 227         }
 228
 229         assert(coder->lz.pos >= dict_old_pos);
 230         if (coder->lz.uncompressed_size != LZMA_VLI_VALUE_UNKNOWN) {
 231                 // Update uncompressed size.
 232                 coder->lz.uncompressed_size -= coder->lz.pos - dict_old_pos;
 233
 234                 // Check that End of Payload Marker hasn't been detected
 235                 // since it must not be present because uncompressed size
 236                 // is known.
 237                 if (coder->lz.eopm_detected)
 238                         error = true;
 239         }
 240
 241         return error;
 242 }
 243
 244
 245 static lzma_ret
 246 decode_buffer(lzma_coder *coder,
 247                 const uint8_t *restrict in, size_t *restrict in_pos,
 248                 size_t in_size, uint8_t *restrict out,
 249                 size_t *restrict out_pos, size_t out_size,
 250                 bool flushing)
 251 {
 252         bool stop = false;
 253
 254         while (true) {
 255                 // Flush from coder->lz.dict to out[].
 256                 flush(&coder->lz, out, out_pos, out_size);
 257
 258                 // All done?
 259                 if (*out_pos == out_size
 260                                 || stop
 261                                 || coder->lz.eopm_detected
 262                                 || coder->lz.uncompressed_size == 0)
 263                         break;
 264
 265                 // Set write limit in the dictionary.
 266                 if (set_limit(&coder->lz, out_size - *out_pos, flushing))
 267                         break;
 268
 269                 // Decode more data.
 270                 if (call_process(coder, in, in_pos, in_size))
 271                         return LZMA_DATA_ERROR;
 272
 273                 // Set stop to true if we must not call call_process() again
 274                 // during this function call.
 275                 // FIXME: Can this make the loop exist too early? It wouldn't
 276                 // cause data corruption so not a critical problem. It can
 277                 // happen if dictionary gets full and lz.temp still contains
 278                 // a few bytes data that we could decode right now.
 279                 if (*in_pos == in_size && coder->lz.temp_size <= TEMP_LIMIT
 280                                 && coder->lz.pos < coder->lz.limit)
 281                         stop = true;
 282         }
 283
 284         // If we have decoded everything (EOPM detected or uncompressed_size
 285         // bytes were processed) to the history buffer, and also flushed
 286         // everything from the history buffer, our job is done.
 287         if ((coder->lz.eopm_detected
 288                         || coder->lz.uncompressed_size == 0)
 289                         && coder->lz.start == coder->lz.pos)
 290                 return LZMA_STREAM_END;
 291
 292         return LZMA_OK;
 293 }
 294
 295
 296 extern lzma_ret
 297 lzma_lz_decode(lzma_coder *coder,
 298                 lzma_allocator *allocator lzma_attribute((unused)),
 299                 const uint8_t *restrict in, size_t *restrict in_pos,
 300                 size_t in_size, uint8_t *restrict out,
 301                 size_t *restrict out_pos, size_t out_size,
 302                 lzma_action action)
 303 {
 304         if (coder->next.code == NULL) {
 305                 const lzma_ret ret = decode_buffer(coder, in, in_pos, in_size,
 306                                 out, out_pos, out_size,
 307                                 action == LZMA_SYNC_FLUSH);
 308
 309                 if (*out_pos == out_size || ret == LZMA_STREAM_END) {
 310                         // Unread to make coder->temp[] empty. This is easy,
 311                         // because we know that all the data currently in
 312                         // coder->temp[] has been copied form in[] during this
 313                         // call to the decoder.
 314                         //
 315                         // If we didn't do this, we could have data left in
 316                         // coder->temp[] when end of stream is reached. That
 317                         // data could be left there from *previous* call to
 318                         // the decoder; in that case we wouldn't know where
 319                         // to put that data.
 320                         assert(*in_pos >= coder->lz.temp_size);
 321                         *in_pos -= coder->lz.temp_size;
 322                         coder->lz.temp_size = 0;
 323                 }
 324
 325                 return ret;
 326         }
 327
 328         // We aren't the last coder in the chain, we need to decode
 329         // our input to a temporary buffer.
 330         const bool flushing = action == LZMA_SYNC_FLUSH;
 331         while (*out_pos < out_size) {
 332                 if (!coder->lz.next_finished
 333                                 && coder->lz.temp_size < LZMA_BUFFER_SIZE) {
 334                         const lzma_ret ret = coder->next.code(
 335                                         coder->next.coder,
 336                                         allocator, in, in_pos, in_size,
 337                                         coder->lz.temp, &coder->lz.temp_size,
 338                                         LZMA_BUFFER_SIZE, action);
 339
 340                         if (ret == LZMA_STREAM_END)
 341                                 coder->lz.next_finished = true;
 342                         else if (coder->lz.temp_size < LZMA_BUFFER_SIZE
 343                                         || ret != LZMA_OK)
 344                                 return ret;
 345                 }
 346
 347                 if (coder->lz.this_finished) {
 348                         if (coder->lz.temp_size != 0)
 349                                 return LZMA_DATA_ERROR;
 350
 351                         if (coder->lz.next_finished)
 352                                 return LZMA_STREAM_END;
 353
 354                         return LZMA_OK;
 355                 }
 356
 357                 size_t dummy = 0;
 358                 const lzma_ret ret = decode_buffer(coder, NULL, &dummy, 0,
 359                                 out, out_pos, out_size, flushing);
 360
 361                 if (ret == LZMA_STREAM_END)
 362                         coder->lz.this_finished = true;
 363                 else if (ret != LZMA_OK)
 364                         return ret;
 365                 else if (coder->lz.next_finished && *out_pos < out_size)
 366                         return LZMA_DATA_ERROR;
 367         }
 368
 369         return LZMA_OK;
 370 }
 371
 372
 373 /// \brief      Initializes LZ part of the LZMA decoder or Inflate
 374 ///
 375 /// \param      history_size    Number of bytes the LZ out window is
 376 ///                             supposed keep available from the output
 377 ///                             history.
 378 /// \param      match_max_len   Number of bytes a single decoding loop
 379 ///                             can advance the write position (lz->pos)
 380 ///                             in the history buffer (lz->dict).
 381 ///
 382 /// \note       This function is called by LZMA decoder and Inflate init()s.
 383 ///             It's up to those functions allocate *lz and initialize it
 384 ///             with LZMA_LZ_DECODER_INIT.
 385 extern lzma_ret
 386 lzma_lz_decoder_reset(lzma_lz_decoder *lz, lzma_allocator *allocator,
 387                 bool (*process)(lzma_coder *restrict coder,
 388                         const uint8_t *restrict in, size_t *restrict in_pos,
 389                         size_t in_size, bool has_safe_buffer),
 390                 lzma_vli uncompressed_size,
 391                 size_t history_size, size_t match_max_len)
 392 {
 393         // Set uncompressed size.
 394         lz->uncompressed_size = uncompressed_size;
 395
 396         // Limit the history size to roughly sane values. This is primarily
 397         // to prevent integer overflows.
 398         if (history_size > UINT32_MAX / 2)
 399                 return LZMA_HEADER_ERROR;
 400
 401         // Store the value actually requested. We use it for sanity checks
 402         // when repeating data from the history buffer.
 403         lz->requested_size = history_size;
 404
 405         // Avoid tiny history buffer sizes for performance reasons.
 406         // TODO: Test if this actually helps...
 407         if (history_size < DICT_SIZE_MIN)
 408                 history_size = DICT_SIZE_MIN;
 409
 410         // The real size of the history buffer is a bit bigger than
 411         // requested by our caller. This allows us to do some optimizations,
 412         // which help not only speed but simplicity of the code; specifically,
 413         // we can make sure that there is always at least match_max_len
 414         // bytes immediatelly available for writing without a need to wrap
 415         // the history buffer.
 416         const size_t dict_real_size = history_size + 2 * match_max_len + 1;
 417
 418         // Reallocate memory if needed.
 419         if (history_size != lz->size || match_max_len != lz->match_max_len) {
 420                 // Destroy the old buffer.
 421                 lzma_lz_decoder_end(lz, allocator);
 422
 423                 lz->size = history_size;
 424                 lz->match_max_len = match_max_len;
 425                 lz->must_flush_pos = history_size + match_max_len + 1;
 426
 427                 lz->dict = lzma_alloc(dict_real_size, allocator);
 428                 if (lz->dict == NULL)
 429                         return LZMA_MEM_ERROR;
 430         }
 431
 432         // Reset the variables so that lz_get_byte(lz, 0) will return '\0'.
 433         lz->pos = 0;
 434         lz->start = 0;
 435         lz->end = dict_real_size;
 436         lz->is_full = false;
 437         lz->eopm_detected = false;
 438         lz->next_finished = false;
 439         lz->this_finished = false;
 440         lz->temp_size = 0;
 441
 442         // Clean up the temporary buffer to make it very sure that there are
 443         // no information leaks when multiple steams are decoded with the
 444         // same decoder structures.
 445         memzero(lz->temp, LZMA_BUFFER_SIZE);
 446
 447         // Set the process function pointer.
 448         lz->process = process;
 449
 450         return LZMA_OK;
 451 }
 452
 453
 454 extern void
 455 lzma_lz_decoder_end(lzma_lz_decoder *lz, lzma_allocator *allocator)
 456 {
 457         lzma_free(lz->dict, allocator);
 458         lz->dict = NULL;
 459         lz->size = 0;
 460         lz->match_max_len = 0;
 461         return;
 462 }