src/liblzma/lzma/lzma2_encoder.c

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