src/liblzma/lzma/lzma2_decoder.c

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //
   3 /// \file       lzma2_decoder.c
   4 /// \brief      LZMA2 decoder
   5 //
   6 //  Copyright (C) 1999-2008 Igor Pavlov
   7 //  Copyright (C) 2008 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 "lzma2_decoder.h"
  22 #include "lz_decoder.h"
  23 #include "lzma_decoder.h"
  24
  25
  26 struct lzma_coder_s {
  27         enum sequence {
  28                 SEQ_CONTROL,
  29                 SEQ_UNCOMPRESSED_1,
  30                 SEQ_UNCOMPRESSED_2,
  31                 SEQ_COMPRESSED_0,
  32                 SEQ_COMPRESSED_1,
  33                 SEQ_PROPERTIES,
  34                 SEQ_LZMA,
  35                 SEQ_COPY,
  36         } sequence;
  37
  38         /// Sequence after the size fields have been decoded.
  39         enum sequence next_sequence;
  40
  41         /// LZMA decoder
  42         lzma_lz_decoder lzma;
  43
  44         /// Uncompressed size of LZMA chunk
  45         size_t uncompressed_size;
  46
  47         /// Compressed size of the chunk (naturally equals to uncompressed
  48         /// size of uncompressed chunk)
  49         size_t compressed_size;
  50
  51         /// True if properties are needed. This is false before the
  52         /// first LZMA chunk.
  53         bool need_properties;
  54
  55         /// True if dictionary reset is needed. This is false before the
  56         /// first chunk (LZMA or uncompressed).
  57         bool need_dictionary_reset;
  58
  59         lzma_options_lzma options;
  60 };
  61
  62
  63 static lzma_ret
  64 lzma2_decode(lzma_coder *restrict coder, lzma_dict *restrict dict,
  65                 const uint8_t *restrict in, size_t *restrict in_pos,
  66                 size_t in_size)
  67 {
  68         // With SEQ_LZMA it is possible that no new input is needed to do
  69         // some progress. The rest of the sequences assume that there is
  70         // at least one byte of input.
  71         while (*in_pos < in_size || coder->sequence == SEQ_LZMA)
  72         switch (coder->sequence) {
  73         case SEQ_CONTROL: {
  74                 const uint32_t control = in[*in_pos];
  75                 ++*in_pos;
  76
  77                 if (control >= 0xE0 || control == 1) {
  78                         // Dictionary reset implies that next LZMA chunk has
  79                         // to set new properties.
  80                         coder->need_properties = true;
  81                         coder->need_dictionary_reset = true;
  82                 } else if (coder->need_dictionary_reset) {
  83                         return LZMA_DATA_ERROR;
  84                 }
  85
  86                 if (control >= 0x80) {
  87                         // LZMA chunk. The highest five bits of the
  88                         // uncompressed size are taken from the control byte.
  89                         coder->uncompressed_size = (control & 0x1F) << 16;
  90                         coder->sequence = SEQ_UNCOMPRESSED_1;
  91
  92                         // See if there are new properties or if we need to
  93                         // reset the state.
  94                         if (control >= 0xC0) {
  95                                 // When there are new properties, state reset
  96                                 // is done at SEQ_PROPERTIES.
  97                                 coder->need_properties = false;
  98                                 coder->next_sequence = SEQ_PROPERTIES;
  99
 100                         } else if (coder->need_properties) {
 101                                 return LZMA_DATA_ERROR;
 102
 103                         } else {
 104                                 coder->next_sequence = SEQ_LZMA;
 105
 106                                 // If only state reset is wanted with old
 107                                 // properties, do the resetting here for
 108                                 // simplicity.
 109                                 if (control >= 0xA0)
 110                                         coder->lzma.reset(coder->lzma.coder,
 111                                                         &coder->options);
 112                         }
 113                 } else {
 114                         // End marker
 115                         if (control == 0x00)
 116                                 return LZMA_STREAM_END;
 117
 118                         // Invalid control values
 119                         if (control > 2)
 120                                 return LZMA_DATA_ERROR;
 121
 122                         // It's uncompressed chunk
 123                         coder->sequence = SEQ_COMPRESSED_0;
 124                         coder->next_sequence = SEQ_COPY;
 125                 }
 126
 127                 if (coder->need_dictionary_reset) {
 128                         // Finish the dictionary reset and let the caller
 129                         // flush the dictionary to the actual output buffer.
 130                         coder->need_dictionary_reset = false;
 131                         dict_reset(dict);
 132                         return LZMA_OK;
 133                 }
 134
 135                 break;
 136         }
 137
 138         case SEQ_UNCOMPRESSED_1:
 139                 coder->uncompressed_size += (uint32_t)(in[(*in_pos)++]) << 8;
 140                 coder->sequence = SEQ_UNCOMPRESSED_2;
 141                 break;
 142
 143         case SEQ_UNCOMPRESSED_2:
 144                 coder->uncompressed_size += in[(*in_pos)++] + 1;
 145                 coder->sequence = SEQ_COMPRESSED_0;
 146                 coder->lzma.set_uncompressed(coder->lzma.coder,
 147                                 coder->uncompressed_size);
 148                 break;
 149
 150         case SEQ_COMPRESSED_0:
 151                 coder->compressed_size = (uint32_t)(in[(*in_pos)++]) << 8;
 152                 coder->sequence = SEQ_COMPRESSED_1;
 153                 break;
 154
 155         case SEQ_COMPRESSED_1:
 156                 coder->compressed_size += in[(*in_pos)++] + 1;
 157                 coder->sequence = coder->next_sequence;
 158                 break;
 159
 160         case SEQ_PROPERTIES:
 161                 if (lzma_lzma_lclppb_decode(&coder->options, in[(*in_pos)++]))
 162                         return LZMA_DATA_ERROR;
 163
 164                 coder->lzma.reset(coder->lzma.coder, &coder->options);
 165
 166                 coder->sequence = SEQ_LZMA;
 167                 break;
 168
 169         case SEQ_LZMA: {
 170                 // Store the start offset so that we can update
 171                 // coder->compressed_size later.
 172                 const size_t in_start = *in_pos;
 173
 174                 // Decode from in[] to *dict.
 175                 const lzma_ret ret = coder->lzma.code(coder->lzma.coder,
 176                                 dict, in, in_pos, in_size);
 177
 178                 // Validate and update coder->compressed_size.
 179                 const size_t in_used = *in_pos - in_start;
 180                 if (in_used > coder->compressed_size)
 181                         return LZMA_DATA_ERROR;
 182
 183                 coder->compressed_size -= in_used;
 184
 185                 // Return if we didn't finish the chunk, or an error occurred.
 186                 if (ret != LZMA_STREAM_END)
 187                         return ret;
 188
 189                 // The LZMA decoder must have consumed the whole chunk now.
 190                 // We don't need to worry about uncompressed size since it
 191                 // is checked by the LZMA decoder.
 192                 if (coder->compressed_size != 0)
 193                         return LZMA_DATA_ERROR;
 194
 195                 coder->sequence = SEQ_CONTROL;
 196                 break;
 197         }
 198
 199         case SEQ_COPY: {
 200                 // Copy from input to the dictionary as is.
 201                 // FIXME Can copy too much?
 202                 dict_write(dict, in, in_pos, in_size, &coder->compressed_size);
 203                 if (coder->compressed_size != 0)
 204                         return LZMA_OK;
 205
 206                 coder->sequence = SEQ_CONTROL;
 207                 break;
 208         }
 209
 210         default:
 211                 assert(0);
 212                 return LZMA_PROG_ERROR;
 213         }
 214
 215         return LZMA_OK;
 216 }
 217
 218
 219 static void
 220 lzma2_decoder_end(lzma_coder *coder, lzma_allocator *allocator)
 221 {
 222         assert(coder->lzma.end == NULL);
 223         lzma_free(coder->lzma.coder, allocator);
 224
 225         lzma_free(coder, allocator);
 226
 227         return;
 228 }
 229
 230
 231 static lzma_ret
 232 lzma2_decoder_init(lzma_lz_decoder *lz, lzma_allocator *allocator,
 233                 const void *opt, lzma_lz_options *lz_options)
 234 {
 235         if (lz->coder == NULL) {
 236                 lz->coder = lzma_alloc(sizeof(lzma_coder), allocator);
 237                 if (lz->coder == NULL)
 238                         return LZMA_MEM_ERROR;
 239
 240                 lz->code = &lzma2_decode;
 241                 lz->end = &lzma2_decoder_end;
 242
 243                 lz->coder->lzma = LZMA_LZ_DECODER_INIT;
 244         }
 245
 246         const lzma_options_lzma *options = opt;
 247
 248         lz->coder->sequence = SEQ_CONTROL;
 249         lz->coder->need_properties = true;
 250         lz->coder->need_dictionary_reset = options->preset_dict == NULL
 251                         || options->preset_dict_size == 0;
 252
 253         return lzma_lzma_decoder_create(&lz->coder->lzma,
 254                         allocator, options, lz_options);
 255 }
 256
 257
 258 extern lzma_ret
 259 lzma_lzma2_decoder_init(lzma_next_coder *next, lzma_allocator *allocator,
 260                 const lzma_filter_info *filters)
 261 {
 262         // LZMA2 can only be the last filter in the chain. This is enforced
 263         // by the raw_decoder initialization.
 264         assert(filters[1].init == NULL);
 265
 266         return lzma_lz_decoder_init(next, allocator, filters,
 267                         &lzma2_decoder_init);
 268 }
 269
 270
 271 extern uint64_t
 272 lzma_lzma2_decoder_memusage(const void *options)
 273 {
 274         return sizeof(lzma_coder)
 275                         + lzma_lzma_decoder_memusage_nocheck(options);
 276 }
 277
 278
 279 extern lzma_ret
 280 lzma_lzma2_props_decode(void **options, lzma_allocator *allocator,
 281                 const uint8_t *props, size_t props_size)
 282 {
 283         if (props_size != 1)
 284                 return LZMA_OPTIONS_ERROR;
 285
 286         // Check that reserved bits are unset.
 287         if (props[0] & 0xC0)
 288                 return LZMA_OPTIONS_ERROR;
 289
 290         // Decode the dictionary size.
 291         if (props[0] > 40)
 292                 return LZMA_OPTIONS_ERROR;
 293
 294         lzma_options_lzma *opt = lzma_alloc(
 295                         sizeof(lzma_options_lzma), allocator);
 296         if (opt == NULL)
 297                 return LZMA_MEM_ERROR;
 298
 299         if (props[0] == 40) {
 300                 opt->dict_size = UINT32_MAX;
 301         } else {
 302                 opt->dict_size = 2 | (props[0] & 1);
 303                 opt->dict_size <<= props[0] / 2 + 11;
 304         }
 305
 306         opt->preset_dict = NULL;
 307         opt->preset_dict_size = 0;
 308
 309         *options = opt;
 310
 311         return LZMA_OK;
 312 }