src/liblzma/lz/lz_decoder.h

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //
   3 /// \file       lz_decoder.h
   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 #ifndef LZMA_LZ_OUT_H
  22 #define LZMA_LZ_OUT_H
  23
  24 #include "common.h"
  25
  26
  27 /// Get a byte from the history buffer.
  28 #define lz_get_byte(lz, distance) \
  29         ((distance) < (lz).pos \
  30                 ? (lz).dict[(lz).pos - (distance) - 1] \
  31                 : (lz).dict[(lz).pos - (distance) - 1 + (lz).end])
  32
  33
  34 /// Test if dictionary is empty.
  35 #define lz_is_empty(lz) \
  36         ((lz).pos == 0 && !(lz).is_full)
  37
  38
  39 #define LZMA_LZ_DECODER_INIT \
  40         (lzma_lz_decoder){ .dict = NULL, .size = 0, .match_max_len = 0 }
  41
  42
  43 typedef struct {
  44         /// Function to do the actual decoding (LZMA or Inflate)
  45         bool (*process)(lzma_coder *restrict coder, const uint8_t *restrict in,
  46                         size_t *restrict in_pos, size_t size_in,
  47                         bool has_safe_buffer);
  48
  49         /// Pointer to dictionary (history) buffer.
  50         /// \note Not 'restrict' because can alias next_out.
  51         uint8_t *dict;
  52
  53         /// Next write goes to dict[pos].
  54         size_t pos;
  55
  56         /// Next byte to flush is buffer[start].
  57         size_t start;
  58
  59         /// First byte to not flush is buffer[end].
  60         size_t end;
  61
  62         /// First position to which data must not be written.
  63         size_t limit;
  64
  65         /// True if dictionary has needed wrapping.
  66         bool is_full;
  67
  68         /// True if process() has detected End of Payload Marker.
  69         bool eopm_detected;
  70
  71         /// True if the next coder in the chain has returned LZMA_STREAM_END.
  72         bool next_finished;
  73
  74         /// True if the LZ decoder (e.g. LZMA) has detected End of Payload
  75         /// Marker. This may become true before next_finished becomes true.
  76         bool this_finished;
  77
  78         /// When pos >= must_flush_pos, we must not call process().
  79         size_t must_flush_pos;
  80
  81         /// Maximum number of bytes that a single decoding loop inside
  82         /// process() can produce data into dict. This amount is kept
  83         /// always available at dict + pos i.e. it is safe to write a byte
  84         /// to dict[pos + match_max_len - 1].
  85         size_t match_max_len;
  86
  87         /// Number of bytes allocated to dict.
  88         size_t size;
  89
  90         /// Requested size of the dictionary. This is needed because we avoid
  91         /// using extremely tiny history buffers.
  92         size_t requested_size;
  93
  94         /// Uncompressed Size or LZMA_VLI_VALUE_UNKNOWN if unknown.
  95         lzma_vli uncompressed_size;
  96
  97         /// Number of bytes currently in temp[].
  98         size_t temp_size;
  99
 100         /// Temporary buffer needed when
 101         /// 1) we cannot make the input buffer completely empty; or
 102         /// 2) we are not the last filter in the chain.
 103         uint8_t temp[LZMA_BUFFER_SIZE];
 104
 105 } lzma_lz_decoder;
 106
 107
 108 /////////////////////////
 109 // Function prototypes //
 110 /////////////////////////
 111
 112 extern lzma_ret lzma_lz_decoder_reset(lzma_lz_decoder *lz,
 113                 lzma_allocator *allocator, bool (*process)(
 114                         lzma_coder *restrict coder, const uint8_t *restrict in,
 115                         size_t *restrict in_pos, size_t in_size,
 116                         bool has_safe_buffer),
 117                 size_t history_size, size_t match_max_len);
 118
 119 extern lzma_ret lzma_lz_decode(lzma_coder *coder, lzma_allocator *allocator,
 120                 const uint8_t *restrict in, size_t *restrict in_pos,
 121                 size_t in_size, uint8_t *restrict out,
 122                 size_t *restrict out_pos, size_t out_size,
 123                 lzma_action action);
 124
 125 /// Deallocates the history buffer if one exists.
 126 extern void lzma_lz_decoder_end(
 127                 lzma_lz_decoder *lz, lzma_allocator *allocator);
 128
 129 //////////////////////
 130 // Inline functions //
 131 //////////////////////
 132
 133 // Repeat a block of data from the history. Because memcpy() is faster
 134 // than copying byte by byte in a loop, the copying process gets split
 135 // into three cases:
 136 // 1. distance < length
 137 //    Source and target areas overlap, thus we can't use memcpy()
 138 //    (nor memmove()) safely.
 139 //    TODO: If this is common enough, it might be worth optimizing this
 140 //    more e.g. by checking if distance > sizeof(uint8_t*) and using
 141 //    memcpy in small chunks.
 142 // 2. distance < pos
 143 //    This is the easiest and the fastest case. The block being copied
 144 //    is a contiguous piece in the history buffer. The buffer offset
 145 //    doesn't need wrapping.
 146 // 3. distance >= pos
 147 //    We need to wrap the position, because otherwise we would try copying
 148 //    behind the first byte of the allocated buffer. It is possible that
 149 //    the block is fragmeneted into two pieces, thus we might need to call
 150 //    memcpy() twice.
 151 // NOTE: The function using this macro must ensure that length is positive
 152 // and that distance is FIXME
 153 static inline bool
 154 lzma_lz_out_repeat(lzma_lz_decoder *lz, size_t distance, size_t length)
 155 {
 156         // Validate offset of the block to be repeated. It doesn't
 157         // make sense to copy data behind the beginning of the stream.
 158         // Leaving this check away would lead to a security problem,
 159         // in which e.g. the data of the previously decoded file(s)
 160         // would be leaked (or whatever happens to be in unused
 161         // part of the dictionary buffer).
 162         if (unlikely(distance >= lz->pos && !lz->is_full))
 163                 return false;
 164
 165         // It also doesn't make sense to copy data farer than
 166         // the dictionary size.
 167         if (unlikely(distance >= lz->requested_size))
 168                 return false;
 169
 170         // The caller must have checked these!
 171         assert(distance <= lz->size);
 172         assert(length > 0);
 173         assert(length <= lz->match_max_len);
 174
 175         // Copy the amount of data requested by the decoder.
 176         if (distance < length) {
 177                 // Source and target areas overlap, thus we can't use
 178                 // memcpy() nor even memmove() safely. :-(
 179                 // TODO: Copying byte by byte is slow. It might be
 180                 // worth optimizing this more if this case is common.
 181                 do {
 182                         lz->dict[lz->pos] = lz_get_byte(*lz, distance);
 183                         ++lz->pos;
 184                 } while (--length > 0);
 185
 186         } else if (distance < lz->pos) {
 187                 // The easiest and fastest case
 188                 memcpy(lz->dict + lz->pos,
 189                                 lz->dict + lz->pos - distance - 1,
 190                                 length);
 191                 lz->pos += length;
 192
 193         } else {
 194                 // The bigger the dictionary, the more rare this
 195                 // case occurs. We need to "wrap" the dict, thus
 196                 // we might need two memcpy() to copy all the data.
 197                 assert(lz->is_full);
 198                 const uint32_t copy_pos = lz->pos - distance - 1 + lz->end;
 199                 uint32_t copy_size = lz->end - copy_pos;
 200
 201                 if (copy_size < length) {
 202                         memcpy(lz->dict + lz->pos, lz->dict + copy_pos,
 203                                         copy_size);
 204                         lz->pos += copy_size;
 205                         copy_size = length - copy_size;
 206                         memcpy(lz->dict + lz->pos, lz->dict, copy_size);
 207                         lz->pos += copy_size;
 208                 } else {
 209                         memcpy(lz->dict + lz->pos, lz->dict + copy_pos,
 210                                         length);
 211                         lz->pos += length;
 212                 }
 213         }
 214
 215         return true;
 216 }
 217
 218 #endif