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