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_DECODER_H
  22 #define LZMA_LZ_DECODER_H
  23
  24 #include "common.h"
  25
  26
  27 typedef struct {
  28         /// Pointer to the dictionary buffer. It can be an allocated buffer
  29         /// internal to liblzma, or it can a be a buffer given by the
  30         /// application when in single-call mode (not implemented yet).
  31         uint8_t *buf;
  32
  33         /// Write position in dictionary. The next byte will be written to
  34         /// buf[pos].
  35         size_t pos;
  36
  37         /// Indicates how full the dictionary is. This is used by
  38         /// dict_is_distance_valid() to detect corrupt files that would
  39         /// read beyond the beginning of the dictionary.
  40         size_t full;
  41
  42         /// Write limit
  43         size_t limit;
  44
  45         /// Size of the dictionary
  46         size_t size;
  47
  48 } lzma_dict;
  49
  50
  51 typedef struct {
  52         /// Data specific to the LZ-based decoder
  53         lzma_coder *coder;
  54
  55         /// Function to decode from in[] to *dict
  56         lzma_ret (*code)(lzma_coder *restrict coder,
  57                         lzma_dict *restrict dict, const uint8_t *restrict in,
  58                         size_t *restrict in_pos, size_t in_size);
  59
  60         void (*reset)(lzma_coder *coder, const void *options);
  61
  62         /// Set the uncompressed size
  63         void (*set_uncompressed)(lzma_coder *coder,
  64                         lzma_vli uncompressed_size);
  65
  66         /// Free allocated resources
  67         void (*end)(lzma_coder *coder, lzma_allocator *allocator);
  68
  69 } lzma_lz_decoder;
  70
  71
  72 #define LZMA_LZ_DECODER_INIT \
  73         (lzma_lz_decoder){ \
  74                 .coder = NULL, \
  75                 .code = NULL, \
  76                 .reset = NULL, \
  77                 .set_uncompressed = NULL, \
  78                 .end = NULL, \
  79         }
  80
  81
  82 extern lzma_ret lzma_lz_decoder_init(lzma_next_coder *next,
  83                 lzma_allocator *allocator, const lzma_filter_info *filters,
  84                 lzma_ret (*lz_init)(lzma_lz_decoder *lz,
  85                         lzma_allocator *allocator, const void *options,
  86                         size_t *dict_size));
  87
  88 extern uint64_t lzma_lz_decoder_memusage(size_t dictionary_size);
  89
  90 extern void lzma_lz_decoder_uncompressed(
  91                 lzma_coder *coder, lzma_vli uncompressed_size);
  92
  93
  94 //////////////////////
  95 // Inline functions //
  96 //////////////////////
  97
  98 /// Get a byte from the history buffer.
  99 static inline uint8_t
 100 dict_get(const lzma_dict *const dict, const uint32_t distance)
 101 {
 102         return dict->buf[dict->pos - distance - 1
 103                         + (distance < dict->pos ? 0 : dict->size)];
 104 }
 105
 106
 107 /// Test if dictionary is empty.
 108 static inline bool
 109 dict_is_empty(const lzma_dict *const dict)
 110 {
 111         return dict->full == 0;
 112 }
 113
 114
 115 /// Validate the match distance
 116 static inline bool
 117 dict_is_distance_valid(const lzma_dict *const dict, const size_t distance)
 118 {
 119         return dict->full >= distance;
 120 }
 121
 122
 123 /// Repeat *len bytes at distance.
 124 static inline bool
 125 dict_repeat(lzma_dict *dict, uint32_t distance, uint32_t *len)
 126 {
 127         // Don't write past the end of the dictionary.
 128         const size_t dict_avail = dict->limit - dict->pos;
 129         uint32_t left = MIN(dict_avail, *len);
 130         *len -= left;
 131
 132         // Repeat a block of data from the history. Because memcpy() is faster
 133         // than copying byte by byte in a loop, the copying process gets split
 134         // into three cases.
 135         if (distance < left) {
 136                 // Source and target areas overlap, thus we can't use
 137                 // memcpy() nor even memmove() safely.
 138                 do {
 139                         dict->buf[dict->pos] = dict_get(dict, distance);
 140                         ++dict->pos;
 141                 } while (--left > 0);
 142
 143         } else if (distance < dict->pos) {
 144                 // The easiest and fastest case
 145                 memcpy(dict->buf + dict->pos,
 146                                 dict->buf + dict->pos - distance - 1,
 147                                 left);
 148                 dict->pos += left;
 149
 150         } else {
 151                 // The bigger the dictionary, the more rare this
 152                 // case occurs. We need to "wrap" the dict, thus
 153                 // we might need two memcpy() to copy all the data.
 154                 assert(dict->full == dict->size);
 155                 const uint32_t copy_pos
 156                                 = dict->pos - distance - 1 + dict->size;
 157                 uint32_t copy_size = dict->size - copy_pos;
 158
 159                 if (copy_size < left) {
 160                         memcpy(dict->buf + dict->pos, dict->buf + copy_pos,
 161                                         copy_size);
 162                         dict->pos += copy_size;
 163                         copy_size = left - copy_size;
 164                         memcpy(dict->buf + dict->pos, dict->buf, copy_size);
 165                         dict->pos += copy_size;
 166                 } else {
 167                         memcpy(dict->buf + dict->pos, dict->buf + copy_pos,
 168                                         left);
 169                         dict->pos += left;
 170                 }
 171         }
 172
 173         // Update how full the dictionary is.
 174         if (dict->full < dict->pos)
 175                 dict->full = dict->pos;
 176
 177         return unlikely(*len != 0);
 178 }
 179
 180
 181 /// Puts one byte into the dictionary. Returns true if the dictionary was
 182 /// already full and the byte couldn't be added.
 183 static inline bool
 184 dict_put(lzma_dict *dict, uint8_t byte)
 185 {
 186         if (unlikely(dict->pos == dict->limit))
 187                 return true;
 188
 189         dict->buf[dict->pos++] = byte;
 190
 191         if (dict->pos > dict->full)
 192                 dict->full = dict->pos;
 193
 194         return false;
 195 }
 196
 197
 198 /// Copies arbitrary amount of data into the dictionary.
 199 static inline void
 200 dict_write(lzma_dict *restrict dict, const uint8_t *restrict in,
 201                 size_t *restrict in_pos, size_t in_size,
 202                 size_t *restrict left)
 203 {
 204         // NOTE: If we are being given more data than the size of the
 205         // dictionary, it could be possible to optimize the LZ decoder
 206         // so that not everything needs to go through the dictionary.
 207         // This shouldn't be very common thing in practice though, and
 208         // the slowdown of one extra memcpy() isn't bad compared to how
 209         // much time it would have taken if the data were compressed.
 210
 211         if (in_size - *in_pos > *left)
 212                 in_size = *in_pos + *left;
 213
 214         *left -= lzma_bufcpy(in, in_pos, in_size,
 215                         dict->buf, &dict->pos, dict->limit);
 216
 217         if (dict->pos > dict->full)
 218                 dict->full = dict->pos;
 219
 220         return;
 221 }
 222
 223
 224 static inline void
 225 dict_reset(lzma_dict *dict)
 226 {
 227         dict->pos = 0;
 228         dict->full = 0;
 229         dict->buf[dict->size - 1] = '\0';
 230 }
 231
 232 #endif