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