src/liblzma/lz/lz_encoder.c

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //
   3 /// \file       lz_encoder.c
   4 /// \brief      LZ in window
   5 //
   6 //  Copyright (C) 1999-2008 Igor Pavlov
   7 //  Copyright (C) 2007-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 "lz_encoder_hash.h"
  23
  24
  25 struct lzma_coder_s {
  26         /// LZ-based encoder e.g. LZMA
  27         lzma_lz_encoder lz;
  28
  29         /// History buffer and match finder
  30         lzma_mf mf;
  31
  32         /// Next coder in the chain
  33         lzma_next_coder next;
  34 };
  35
  36
  37 /// \brief      Moves the data in the input window to free space for new data
  38 ///
  39 /// mf->buffer is a sliding input window, which keeps mf->keep_size_before
  40 /// bytes of input history available all the time. Now and then we need to
  41 /// "slide" the buffer to make space for the new data to the end of the
  42 /// buffer. At the same time, data older than keep_size_before is dropped.
  43 ///
  44 static void
  45 move_window(lzma_mf *mf)
  46 {
  47         // Align the move to a multiple of 16 bytes. Some LZ-based encoders
  48         // like LZMA use the lowest bits of mf->read_pos to know the
  49         // alignment of the uncompressed data. We also get better speed
  50         // for memmove() with aligned buffers.
  51         assert(mf->read_pos > mf->keep_size_before);
  52         const uint32_t move_offset
  53                 = (mf->read_pos - mf->keep_size_before) & ~UINT32_C(15);
  54
  55         assert(mf->write_pos > move_offset);
  56         const size_t move_size = mf->write_pos - move_offset;
  57
  58         assert(move_offset + move_size <= mf->size);
  59
  60         memmove(mf->buffer, mf->buffer + move_offset, move_size);
  61
  62         mf->offset += move_offset;
  63         mf->read_pos -= move_offset;
  64         mf->read_limit -= move_offset;
  65         mf->write_pos -= move_offset;
  66
  67         return;
  68 }
  69
  70
  71 /// \brief      Tries to fill the input window (mf->buffer)
  72 ///
  73 /// If we are the last encoder in the chain, our input data is in in[].
  74 /// Otherwise we call the next filter in the chain to process in[] and
  75 /// write its output to mf->buffer.
  76 ///
  77 /// This function must not be called once it has returned LZMA_STREAM_END.
  78 ///
  79 static lzma_ret
  80 fill_window(lzma_coder *coder, lzma_allocator *allocator, const uint8_t *in,
  81                 size_t *in_pos, size_t in_size, lzma_action action)
  82 {
  83         assert(coder->mf.read_pos <= coder->mf.write_pos);
  84
  85         // Move the sliding window if needed.
  86         if (coder->mf.read_pos >= coder->mf.size - coder->mf.keep_size_after)
  87                 move_window(&coder->mf);
  88
  89         size_t in_used;
  90         lzma_ret ret;
  91         if (coder->next.code == NULL) {
  92                 // Not using a filter, simply memcpy() as much as possible.
  93                 in_used = lzma_bufcpy(in, in_pos, in_size, coder->mf.buffer,
  94                                 &coder->mf.write_pos, coder->mf.size);
  95
  96                 ret = action != LZMA_RUN && *in_pos == in_size
  97                                 ? LZMA_STREAM_END : LZMA_OK;
  98
  99         } else {
 100                 const size_t in_start = *in_pos;
 101                 ret = coder->next.code(coder->next.coder, allocator,
 102                                 in, in_pos, in_size,
 103                                 coder->mf.buffer, &coder->mf.write_pos,
 104                                 coder->mf.size, action);
 105                 in_used = *in_pos - in_start;
 106         }
 107
 108         // If end of stream has been reached or flushing completed, we allow
 109         // the encoder to process all the input (that is, read_pos is allowed
 110         // to reach write_pos). Otherwise we keep keep_size_after bytes
 111         // available as prebuffer.
 112         if (ret == LZMA_STREAM_END) {
 113                 assert(*in_pos == in_size);
 114                 ret = LZMA_OK;
 115                 coder->mf.action = action;
 116                 coder->mf.read_limit = coder->mf.write_pos;
 117
 118         } else if (coder->mf.write_pos > coder->mf.keep_size_after) {
 119                 // This needs to be done conditionally, because if we got
 120                 // only little new input, there may be too little input
 121                 // to do any encoding yet.
 122                 coder->mf.read_limit = coder->mf.write_pos
 123                                 - coder->mf.keep_size_after;
 124         }
 125
 126         // Restart the match finder after finished LZMA_SYNC_FLUSH.
 127         if (coder->mf.pending > 0
 128                         && coder->mf.read_pos < coder->mf.read_limit) {
 129                 // Match finder may update coder->pending and expects it to
 130                 // start from zero, so use a temporary variable.
 131                 const size_t pending = coder->mf.pending;
 132                 coder->mf.pending = 0;
 133
 134                 // Rewind read_pos so that the match finder can hash
 135                 // the pending bytes.
 136                 assert(coder->mf.read_pos >= pending);
 137                 coder->mf.read_pos -= pending;
 138
 139                 // Call the skip function directly instead of using
 140                 // lz_dict_skip(), since we don't want to touch
 141                 // mf->read_ahead.
 142                 coder->mf.skip(&coder->mf, pending);
 143         }
 144
 145         return ret;
 146 }
 147
 148
 149 static lzma_ret
 150 lz_encode(lzma_coder *coder, lzma_allocator *allocator,
 151                 const uint8_t *restrict in, size_t *restrict in_pos,
 152                 size_t in_size,
 153                 uint8_t *restrict out, size_t *restrict out_pos,
 154                 size_t out_size, lzma_action action)
 155 {
 156         while (*out_pos < out_size
 157                         && (*in_pos < in_size || action != LZMA_RUN)) {
 158                 // Read more data to coder->mf.buffer if needed.
 159                 if (coder->mf.action == LZMA_RUN && coder->mf.read_pos
 160                                 >= coder->mf.read_limit)
 161                         return_if_error(fill_window(coder, allocator,
 162                                         in, in_pos, in_size, action));
 163
 164                 // Encode
 165                 const lzma_ret ret = coder->lz.code(coder->lz.coder,
 166                                 &coder->mf, out, out_pos, out_size);
 167                 if (ret != LZMA_OK) {
 168                         // Setting this to LZMA_RUN for cases when we are
 169                         // flushing. It doesn't matter when finishing or if
 170                         // an error occurred.
 171                         coder->mf.action = LZMA_RUN;
 172                         return ret;
 173                 }
 174         }
 175
 176         return LZMA_OK;
 177 }
 178
 179
 180 static bool
 181 lz_encoder_prepare(lzma_mf *mf, lzma_allocator *allocator,
 182                 const lzma_lz_options *lz_options)
 183 {
 184         if (lz_options->dictionary_size < LZMA_DICTIONARY_SIZE_MIN
 185                         || lz_options->dictionary_size
 186                                 > LZMA_DICTIONARY_SIZE_MAX
 187                         || lz_options->find_len_max
 188                                 > lz_options->match_len_max)
 189                 return true;
 190
 191         mf->keep_size_before = lz_options->before_size
 192                         + lz_options->dictionary_size;
 193
 194         mf->keep_size_after = lz_options->after_size
 195                         + lz_options->match_len_max;
 196
 197         // To avoid constant memmove()s, allocate some extra space. Since
 198         // memmove()s become more expensive when the size of the buffer
 199         // increases, we reserve more space when a large dictionary is
 200         // used to make the memmove() calls rarer.
 201         uint32_t reserve = lz_options->dictionary_size / 2;
 202         if (reserve > (UINT32_C(1) << 30))
 203                 reserve /= 2;
 204
 205         reserve += (lz_options->before_size + lz_options->match_len_max
 206                         + lz_options->after_size) / 2 + (UINT32_C(1) << 19);
 207
 208         const uint32_t old_size = mf->size;
 209         mf->size = mf->keep_size_before + reserve + mf->keep_size_after;
 210
 211         // FIXME Integer overflows
 212
 213         // Deallocate the old history buffer if it exists but has different
 214         // size than what is needed now.
 215         if (mf->buffer != NULL && old_size != mf->size) {
 216                 lzma_free(mf->buffer, allocator);
 217                 mf->buffer = NULL;
 218         }
 219
 220         // Match finder options
 221         mf->match_len_max = lz_options->match_len_max;
 222         mf->find_len_max = lz_options->find_len_max;
 223         mf->cyclic_buffer_size = lz_options->dictionary_size + 1;
 224
 225         // Validate the match finder ID and setup the function pointers.
 226         switch (lz_options->match_finder) {
 227 #ifdef HAVE_MF_HC3
 228         case LZMA_MF_HC3:
 229                 mf->find = &lzma_mf_hc3_find;
 230                 mf->skip = &lzma_mf_hc3_skip;
 231                 break;
 232 #endif
 233 #ifdef HAVE_MF_HC4
 234         case LZMA_MF_HC4:
 235                 mf->find = &lzma_mf_hc4_find;
 236                 mf->skip = &lzma_mf_hc4_skip;
 237                 break;
 238 #endif
 239 #ifdef HAVE_MF_BT2
 240         case LZMA_MF_BT2:
 241                 mf->find = &lzma_mf_bt2_find;
 242                 mf->skip = &lzma_mf_bt2_skip;
 243                 break;
 244 #endif
 245 #ifdef HAVE_MF_BT3
 246         case LZMA_MF_BT3:
 247                 mf->find = &lzma_mf_bt3_find;
 248                 mf->skip = &lzma_mf_bt3_skip;
 249                 break;
 250 #endif
 251 #ifdef HAVE_MF_BT4
 252         case LZMA_MF_BT4:
 253                 mf->find = &lzma_mf_bt4_find;
 254                 mf->skip = &lzma_mf_bt4_skip;
 255                 break;
 256 #endif
 257
 258         default:
 259                 return true;
 260         }
 261
 262         // Calculate the sizes of mf->hash and mf->son.
 263         const uint32_t hash_bytes = lz_options->match_finder & 0x0F;
 264         const bool is_bt = (lz_options->match_finder & 0x10) != 0;
 265         uint32_t hs;
 266
 267         if (hash_bytes == 2) {
 268                 hs = 0xFFFF;
 269         } else {
 270                 // Round dictionary size up to the next 2^n - 1 so it can
 271                 // be used as a hash mask.
 272                 hs = lz_options->dictionary_size - 1;
 273                 hs |= hs >> 1;
 274                 hs |= hs >> 2;
 275                 hs |= hs >> 4;
 276                 hs |= hs >> 8;
 277                 hs >>= 1;
 278                 hs |= 0xFFFF;
 279
 280                 if (hs > (UINT32_C(1) << 24)) {
 281                         if (hash_bytes == 3)
 282                                 hs = (UINT32_C(1) << 24) - 1;
 283                         else
 284                                 hs >>= 1;
 285                 }
 286         }
 287
 288         mf->hash_mask = hs;
 289
 290         ++hs;
 291         if (hash_bytes > 2)
 292                 hs += HASH_2_SIZE;
 293         if (hash_bytes > 3)
 294                 hs += HASH_3_SIZE;
 295 /*
 296         No match finder uses this at the moment.
 297         if (mf->hash_bytes > 4)
 298                 hs += HASH_4_SIZE;
 299 */
 300
 301         const uint32_t old_count = mf->hash_size_sum + mf->sons_count;
 302         mf->hash_size_sum = hs;
 303         mf->sons_count = mf->cyclic_buffer_size;
 304         if (is_bt)
 305                 mf->sons_count *= 2;
 306
 307         const uint32_t new_count = mf->hash_size_sum + mf->sons_count;
 308
 309         // Deallocate the old hash array if it exists and has different size
 310         // than what is needed now.
 311         if (mf->hash != NULL && old_count != new_count) {
 312                 lzma_free(mf->hash, allocator);
 313                 mf->hash = NULL;
 314         }
 315
 316         // Maximum number of match finder cycles
 317         mf->loops = lz_options->match_finder_cycles;
 318         if (mf->loops == 0) {
 319                 mf->loops = 16 + (lz_options->find_len_max / 2);
 320                 if (!is_bt)
 321                         mf->loops /= 2;
 322         }
 323
 324         return false;
 325 }
 326
 327
 328 static bool
 329 lz_encoder_init(lzma_mf *mf, lzma_allocator *allocator)
 330 {
 331         // Allocate the history buffer.
 332         if (mf->buffer == NULL) {
 333                 mf->buffer = lzma_alloc(mf->size, allocator);
 334                 if (mf->buffer == NULL)
 335                         return true;
 336         }
 337
 338         // Use cyclic_buffer_size as initial mf->offset. This allows
 339         // avoiding a few branches in the match finders. The downside is
 340         // that match finder needs to be normalized more often, which may
 341         // hurt performance with huge dictionaries.
 342         mf->offset = mf->cyclic_buffer_size;
 343         mf->read_pos = 0;
 344         mf->read_ahead = 0;
 345         mf->read_limit = 0;
 346         mf->write_pos = 0;
 347         mf->pending = 0;
 348
 349         // Allocate match finder's hash array.
 350         const size_t alloc_count = mf->hash_size_sum + mf->sons_count;
 351
 352 #if UINT32_MAX >= SIZE_MAX / 4
 353         // Check for integer overflow. (Huge dictionaries are not
 354         // possible on 32-bit CPU.)
 355         if (alloc_count > SIZE_MAX / sizeof(uint32_t))
 356                 return true;
 357 #endif
 358
 359         if (mf->hash == NULL) {
 360                 mf->hash = lzma_alloc(alloc_count * sizeof(uint32_t),
 361                                 allocator);
 362                 if (mf->hash == NULL)
 363                         return true;
 364         }
 365
 366         mf->son = mf->hash + mf->hash_size_sum;
 367         mf->cyclic_buffer_pos = 0;
 368
 369         // Initialize the hash table. Since EMPTY_HASH_VALUE is zero, we
 370         // can use memset().
 371 /*
 372         for (uint32_t i = 0; i < hash_size_sum; ++i)
 373                 mf->hash[i] = EMPTY_HASH_VALUE;
 374 */
 375         memzero(mf->hash, (size_t)(mf->hash_size_sum) * sizeof(uint32_t));
 376
 377         // We don't need to initialize mf->son, but not doing that will
 378         // make Valgrind complain in normalization (see normalize() in
 379         // lz_encoder_mf.c).
 380         //
 381         // Skipping this initialization is *very* good when big dictionary is
 382         // used but only small amount of data gets actually compressed: most
 383         // of the mf->hash won't get actually allocated by the kernel, so
 384         // we avoid wasting RAM and improve initialization speed a lot.
 385         //memzero(mf->son, (size_t)(mf->sons_count) * sizeof(uint32_t));
 386
 387         mf->action = LZMA_RUN;
 388
 389         return false;
 390 }
 391
 392
 393 extern uint64_t
 394 lzma_lz_encoder_memusage(const lzma_lz_options *lz_options)
 395 {
 396         // Old buffers must not exist when calling lz_encoder_prepare().
 397         lzma_mf mf = {
 398                 .buffer = NULL,
 399                 .hash = NULL,
 400         };
 401
 402         // Setup the size information into mf.
 403         if (lz_encoder_prepare(&mf, NULL, lz_options))
 404                 return UINT64_MAX;
 405
 406         // Calculate the memory usage.
 407         return (uint64_t)(mf.hash_size_sum + mf.sons_count)
 408                                 * sizeof(uint32_t)
 409                         + (uint64_t)(mf.size) + sizeof(lzma_coder);
 410 }
 411
 412
 413 static void
 414 lz_encoder_end(lzma_coder *coder, lzma_allocator *allocator)
 415 {
 416         lzma_next_end(&coder->next, allocator);
 417
 418         lzma_free(coder->mf.hash, allocator);
 419         lzma_free(coder->mf.buffer, allocator);
 420
 421         if (coder->lz.end != NULL)
 422                 coder->lz.end(coder->lz.coder, allocator);
 423         else
 424                 lzma_free(coder->lz.coder, allocator);
 425
 426         lzma_free(coder, allocator);
 427         return;
 428 }
 429
 430
 431 extern lzma_ret
 432 lzma_lz_encoder_init(lzma_next_coder *next, lzma_allocator *allocator,
 433                 const lzma_filter_info *filters,
 434                 lzma_ret (*lz_init)(lzma_lz_encoder *lz,
 435                         lzma_allocator *allocator, const void *options,
 436                         lzma_lz_options *lz_options))
 437 {
 438         // Allocate and initialize the base data structure.
 439         if (next->coder == NULL) {
 440                 next->coder = lzma_alloc(sizeof(lzma_coder), allocator);
 441                 if (next->coder == NULL)
 442                         return LZMA_MEM_ERROR;
 443
 444                 next->code = &lz_encode;
 445                 next->end = &lz_encoder_end;
 446
 447                 next->coder->lz.coder = NULL;
 448                 next->coder->lz.code = NULL;
 449                 next->coder->lz.end = NULL;
 450
 451                 next->coder->mf.buffer = NULL;
 452                 next->coder->mf.hash = NULL;
 453
 454                 next->coder->next = LZMA_NEXT_CODER_INIT;
 455         }
 456
 457         // Initialize the LZ-based encoder.
 458         lzma_lz_options lz_options;
 459         return_if_error(lz_init(&next->coder->lz, allocator,
 460                         filters[0].options, &lz_options));
 461
 462         // Setup the size information into next->coder->mf and deallocate
 463         // old buffers if they have wrong size.
 464         if (lz_encoder_prepare(&next->coder->mf, allocator, &lz_options))
 465                 return LZMA_HEADER_ERROR;
 466
 467         // Allocate new buffers if needed, and do the rest of
 468         // the initialization.
 469         if (lz_encoder_init(&next->coder->mf, allocator))
 470                 return LZMA_MEM_ERROR;
 471
 472         // Initialize the next filter in the chain, if any.
 473         return lzma_next_filter_init(&next->coder->next, allocator,
 474                         filters + 1);
 475 }
 476
 477
 478 extern LZMA_API lzma_bool
 479 lzma_mf_is_supported(lzma_match_finder mf)
 480 {
 481         bool ret = false;
 482
 483 #ifdef HAVE_MF_HC3
 484         if (mf == LZMA_MF_HC3)
 485                 ret = true;
 486 #endif
 487
 488 #ifdef HAVE_MF_HC4
 489         if (mf == LZMA_MF_HC4)
 490                 ret = true;
 491 #endif
 492
 493 #ifdef HAVE_MF_BT2
 494         if (mf == LZMA_MF_BT2)
 495                 ret = true;
 496 #endif
 497
 498 #ifdef HAVE_MF_BT3
 499         if (mf == LZMA_MF_BT3)
 500                 ret = true;
 501 #endif
 502
 503 #ifdef HAVE_MF_BT4
 504         if (mf == LZMA_MF_BT4)
 505                 ret = true;
 506 #endif
 507
 508         return ret;
 509 }