src/liblzma/lzma/lzma2_encoder.c

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //
   3 /// \file       lzma2_encoder.c
   4 /// \brief      LZMA2 encoder
   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 "lz_encoder.h"
  22 #include "lzma_encoder.h"
  23 #include "fastpos.h"
  24 #include "lzma2_encoder.h"
  25
  26
  27 struct lzma_coder_s {
  28         enum {
  29                 SEQ_INIT,
  30                 SEQ_LZMA_ENCODE,
  31                 SEQ_LZMA_COPY,
  32                 SEQ_UNCOMPRESSED_HEADER,
  33                 SEQ_UNCOMPRESSED_COPY,
  34         } sequence;
  35
  36         /// LZMA encoder
  37         lzma_coder *lzma;
  38
  39         /// If this is not NULL, we will check new options from this
  40         /// structure when starting a new chunk.
  41         const lzma_options_lzma *opt_new;
  42
  43         /// LZMA options currently in use.
  44         lzma_options_lzma opt_cur;
  45
  46         bool need_properties;
  47         bool need_state_reset;
  48         bool need_dictionary_reset;
  49
  50         /// Uncompressed size of a chunk
  51         size_t uncompressed_size;
  52
  53         /// Compressed size of a chunk (excluding headers); this is also used
  54         /// to indicate the end of buf[] in SEQ_LZMA_COPY.
  55         size_t compressed_size;
  56
  57         /// Read position in buf[]
  58         size_t buf_pos;
  59
  60         /// Buffer to hold the chunk header and LZMA compressed data
  61         uint8_t buf[LZMA2_HEADER_MAX + LZMA2_CHUNK_MAX];
  62 };
  63
  64
  65 static void
  66 lzma2_header_lzma(lzma_coder *coder)
  67 {
  68         assert(coder->uncompressed_size > 0);
  69         assert(coder->uncompressed_size <= LZMA2_UNCOMPRESSED_MAX);
  70         assert(coder->compressed_size > 0);
  71         assert(coder->compressed_size <= LZMA2_CHUNK_MAX);
  72
  73         size_t pos;
  74
  75         if (coder->need_properties) {
  76                 pos = 0;
  77
  78                 if (coder->need_dictionary_reset)
  79                         coder->buf[pos] = 0x80 + (3 << 5);
  80                 else
  81                         coder->buf[pos] = 0x80 + (2 << 5);
  82         } else {
  83                 pos = 1;
  84
  85                 if (coder->need_state_reset)
  86                         coder->buf[pos] = 0x80 + (1 << 5);
  87                 else
  88                         coder->buf[pos] = 0x80;
  89         }
  90
  91         // Set the start position for copying.
  92         coder->buf_pos = pos;
  93
  94         // Uncompressed size
  95         size_t size = coder->uncompressed_size - 1;
  96         coder->buf[pos++] += size >> 16;
  97         coder->buf[pos++] = (size >> 8) & 0xFF;
  98         coder->buf[pos++] = size & 0xFF;
  99
 100         // Compressed size
 101         size = coder->compressed_size - 1;
 102         coder->buf[pos++] = size >> 8;
 103         coder->buf[pos++] = size & 0xFF;
 104
 105         // Properties, if needed
 106         if (coder->need_properties)
 107                 lzma_lzma_lclppb_encode(&coder->opt_cur, coder->buf + pos);
 108
 109         coder->need_properties = false;
 110         coder->need_state_reset = false;
 111         coder->need_dictionary_reset = false;
 112
 113         // The copying code uses coder->compressed_size to indicate the end
 114         // of coder->buf[], so we need add the maximum size of the header here.
 115         coder->compressed_size += LZMA2_HEADER_MAX;
 116
 117         return;
 118 }
 119
 120
 121 static void
 122 lzma2_header_uncompressed(lzma_coder *coder)
 123 {
 124         assert(coder->uncompressed_size > 0);
 125         assert(coder->uncompressed_size <= LZMA2_CHUNK_MAX);
 126
 127         // If this is the first chunk, we need to include dictionary
 128         // reset indicator.
 129         if (coder->need_dictionary_reset)
 130                 coder->buf[0] = 1;
 131         else
 132                 coder->buf[0] = 2;
 133
 134         coder->need_dictionary_reset = false;
 135
 136         // "Compressed" size
 137         coder->buf[1] = (coder->uncompressed_size - 1) >> 8;
 138         coder->buf[2] = (coder->uncompressed_size - 1) & 0xFF;
 139
 140         // Set the start position for copying.
 141         coder->buf_pos = 0;
 142         return;
 143 }
 144
 145
 146 static lzma_ret
 147 lzma2_encode(lzma_coder *restrict coder, lzma_mf *restrict mf,
 148                 uint8_t *restrict out, size_t *restrict out_pos,
 149                 size_t out_size)
 150 {
 151         while (*out_pos < out_size)
 152         switch (coder->sequence) {
 153         case SEQ_INIT:
 154                 // If there's no input left and we are flushing or finishing,
 155                 // don't start a new chunk.
 156                 if (mf_unencoded(mf) == 0) {
 157                         // Write end of payload marker if finishing.
 158                         if (mf->action == LZMA_FINISH)
 159                                 out[(*out_pos)++] = 0;
 160
 161                         return mf->action == LZMA_RUN
 162                                         ? LZMA_OK : LZMA_STREAM_END;
 163                 }
 164
 165                 // Look if there are new options. At least for now,
 166                 // only lc/lp/pb can be changed.
 167                 if (coder->opt_new != NULL
 168                                 && (coder->opt_cur.lc != coder->opt_new->lc
 169                                 || coder->opt_cur.lp != coder->opt_new->lp
 170                                 || coder->opt_cur.pb != coder->opt_new->pb)) {
 171                         // Options have been changed, copy them to opt_cur.
 172                         // These get validated as part of
 173                         // lzma_lzma_encoder_reset() below.
 174                         coder->opt_cur.lc = coder->opt_new->lc;
 175                         coder->opt_cur.lp = coder->opt_new->lp;
 176                         coder->opt_cur.pb = coder->opt_new->pb;
 177
 178                         // We need to write the new options and reset
 179                         // the encoder state.
 180                         coder->need_properties = true;
 181                         coder->need_state_reset = true;
 182                 }
 183
 184                 if (coder->need_state_reset)
 185                         return_if_error(lzma_lzma_encoder_reset(
 186                                         coder->lzma, &coder->opt_cur));
 187
 188                 coder->uncompressed_size = 0;
 189                 coder->compressed_size = 0;
 190                 coder->sequence = SEQ_LZMA_ENCODE;
 191
 192         // Fall through
 193
 194         case SEQ_LZMA_ENCODE: {
 195                 // Calculate how much more uncompressed data this chunk
 196                 // could accept.
 197                 const uint32_t left = LZMA2_UNCOMPRESSED_MAX
 198                                 - coder->uncompressed_size;
 199                 uint32_t limit;
 200
 201                 if (left < mf->match_len_max) {
 202                         // Must flush immediatelly since the next LZMA symbol
 203                         // could make the uncompressed size of the chunk too
 204                         // big.
 205                         limit = 0;
 206                 } else {
 207                         // Calculate maximum read_limit that is OK from point
 208                         // of view of LZMA2 chunk size.
 209                         limit = mf->read_pos - mf->read_ahead
 210                                         + left - mf->match_len_max;
 211                 }
 212
 213                 // Save the start position so that we can update
 214                 // coder->uncompressed_size.
 215                 const uint32_t read_start = mf->read_pos - mf->read_ahead;
 216
 217                 // Call the LZMA encoder until the chunk is finished.
 218                 const lzma_ret ret = lzma_lzma_encode(coder->lzma, mf,
 219                                 coder->buf + LZMA2_HEADER_MAX,
 220                                 &coder->compressed_size,
 221                                 LZMA2_CHUNK_MAX, limit);
 222
 223                 coder->uncompressed_size += mf->read_pos - mf->read_ahead
 224                                 - read_start;
 225
 226                 assert(coder->compressed_size <= LZMA2_CHUNK_MAX);
 227                 assert(coder->uncompressed_size <= LZMA2_UNCOMPRESSED_MAX);
 228
 229                 if (ret != LZMA_STREAM_END)
 230                         return LZMA_OK;
 231
 232                 // See if the chunk compressed. If it didn't, we encode it
 233                 // as uncompressed chunk. This saves a few bytes of space
 234                 // and makes decoding faster.
 235                 if (coder->compressed_size >= coder->uncompressed_size) {
 236                         coder->uncompressed_size += mf->read_ahead;
 237                         assert(coder->uncompressed_size
 238                                         <= LZMA2_UNCOMPRESSED_MAX);
 239                         mf->read_ahead = 0;
 240                         lzma2_header_uncompressed(coder);
 241                         coder->need_state_reset = true;
 242                         coder->sequence = SEQ_UNCOMPRESSED_HEADER;
 243                         break;
 244                 }
 245
 246                 // The chunk did compress at least by one byte, so we store
 247                 // the chunk as LZMA.
 248                 lzma2_header_lzma(coder);
 249
 250                 coder->sequence = SEQ_LZMA_COPY;
 251         }
 252
 253         // Fall through
 254
 255         case SEQ_LZMA_COPY:
 256                 // Copy the compressed chunk along its headers to the
 257                 // output buffer.
 258                 lzma_bufcpy(coder->buf, &coder->buf_pos,
 259                                 coder->compressed_size,
 260                                 out, out_pos, out_size);
 261                 if (coder->buf_pos != coder->compressed_size)
 262                         return LZMA_OK;
 263
 264                 coder->sequence = SEQ_INIT;
 265                 break;
 266
 267         case SEQ_UNCOMPRESSED_HEADER:
 268                 // Copy the three-byte header to indicate uncompressed chunk.
 269                 lzma_bufcpy(coder->buf, &coder->buf_pos,
 270                                 LZMA2_HEADER_UNCOMPRESSED,
 271                                 out, out_pos, out_size);
 272                 if (coder->buf_pos != LZMA2_HEADER_UNCOMPRESSED)
 273                         return LZMA_OK;
 274
 275                 coder->sequence = SEQ_UNCOMPRESSED_COPY;
 276
 277         // Fall through
 278
 279         case SEQ_UNCOMPRESSED_COPY:
 280                 // Copy the uncompressed data as is from the dictionary
 281                 // to the output buffer.
 282                 mf_read(mf, out, out_pos, out_size, &coder->uncompressed_size);
 283                 if (coder->uncompressed_size != 0)
 284                         return LZMA_OK;
 285
 286                 coder->sequence = SEQ_INIT;
 287                 break;
 288         }
 289
 290         return LZMA_OK;
 291 }
 292
 293
 294 static void
 295 lzma2_encoder_end(lzma_coder *coder, lzma_allocator *allocator)
 296 {
 297         lzma_free(coder->lzma, allocator);
 298         lzma_free(coder, allocator);
 299         return;
 300 }
 301
 302
 303 static lzma_ret
 304 lzma2_encoder_init(lzma_lz_encoder *lz, lzma_allocator *allocator,
 305                 const void *options, lzma_lz_options *lz_options)
 306 {
 307         if (options == NULL)
 308                 return LZMA_PROG_ERROR;
 309
 310         if (lz->coder == NULL) {
 311                 lz->coder = lzma_alloc(sizeof(lzma_coder), allocator);
 312                 if (lz->coder == NULL)
 313                         return LZMA_MEM_ERROR;
 314
 315                 lz->code = &lzma2_encode;
 316                 lz->end = &lzma2_encoder_end;
 317
 318                 lz->coder->lzma = NULL;
 319         }
 320
 321         lz->coder->sequence = SEQ_INIT;
 322         lz->coder->need_properties = true;
 323         lz->coder->need_state_reset = false;
 324         lz->coder->need_dictionary_reset = true;
 325
 326         lz->coder->opt_cur = *(const lzma_options_lzma *)(options);
 327         lz->coder->opt_new = lz->coder->opt_cur.persistent
 328                                 ? options : NULL;
 329
 330         // Initialize LZMA encoder
 331         return_if_error(lzma_lzma_encoder_create(&lz->coder->lzma, allocator,
 332                         &lz->coder->opt_cur, lz_options));
 333
 334         // Make sure that we will always have enough history available in
 335         // case we need to use uncompressed chunks. They are used when the
 336         // compressed size of a chunk is not smaller than the uncompressed
 337         // size, so we need to have at least LZMA2_COMPRESSED_MAX bytes
 338         // history available.
 339         if (lz_options->before_size + lz_options->dict_size < LZMA2_CHUNK_MAX)
 340                 lz_options->before_size
 341                                 = LZMA2_CHUNK_MAX - lz_options->dict_size;
 342
 343         return LZMA_OK;
 344 }
 345
 346
 347 extern lzma_ret
 348 lzma_lzma2_encoder_init(lzma_next_coder *next, lzma_allocator *allocator,
 349                 const lzma_filter_info *filters)
 350 {
 351         return lzma_lz_encoder_init(
 352                         next, allocator, filters, &lzma2_encoder_init);
 353 }
 354
 355
 356 extern uint64_t
 357 lzma_lzma2_encoder_memusage(const void *options)
 358 {
 359         const uint64_t lzma_mem = lzma_lzma_encoder_memusage(options);
 360         if (lzma_mem == UINT64_MAX)
 361                 return UINT64_MAX;
 362
 363         return sizeof(lzma_coder) + lzma_mem;
 364 }
 365
 366
 367 extern lzma_ret
 368 lzma_lzma2_props_encode(const void *options, uint8_t *out)
 369 {
 370         const lzma_options_lzma *const opt = options;
 371         uint32_t d = MAX(opt->dict_size, LZMA_DICT_SIZE_MIN);
 372
 373         // Round up to to the next 2^n - 1 or 2^n + 2^(n - 1) - 1 depending
 374         // on which one is the next:
 375         --d;
 376         d |= d >> 2;
 377         d |= d >> 3;
 378         d |= d >> 4;
 379         d |= d >> 8;
 380         d |= d >> 16;
 381
 382         // Get the highest two bits using the proper encoding:
 383         if (d == UINT32_MAX)
 384                 out[0] = 40;
 385         else
 386                 out[0] = get_pos_slot(d + 1) - 24;
 387
 388         return LZMA_OK;
 389 }