src/liblzma/subblock/subblock_encoder.c

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //
   3 /// \file       subblock_encoder.c
   4 /// \brief      Encoder of the Subblock filter
   5 //
   6 //  Copyright (C) 2007, 2008 Lasse Collin
   7 //
   8 //  This library is free software; you can redistribute it and/or
   9 //  modify it under the terms of the GNU Lesser General Public
  10 //  License as published by the Free Software Foundation; either
  11 //  version 2.1 of the License, or (at your option) any later version.
  12 //
  13 //  This library is distributed in the hope that it will be useful,
  14 //  but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16 //  Lesser General Public License for more details.
  17 //
  18 ///////////////////////////////////////////////////////////////////////////////
  19
  20 #include "subblock_encoder.h"
  21 #include "filter_encoder.h"
  22
  23
  24 /// Maximum number of repeats that a single Repeating Data can indicate.
  25 /// This is directly from the file format specification.
  26 #define REPEAT_COUNT_MAX (1U << 28)
  27
  28 /// Number of bytes the data chunk (not including the header part) must be
  29 /// before we care about alignment. This is somewhat arbitrary. It just
  30 /// doesn't make sense to waste bytes for alignment when the data chunk
  31 /// is very small.
  32 #define MIN_CHUNK_SIZE_FOR_ALIGN 4
  33
  34 /// Number of bytes of the header part of Subblock Type `Data'. This is
  35 /// used as the `skew' argument for subblock_align().
  36 #define ALIGN_SKEW_DATA 4
  37
  38 /// Like above but for Repeating Data.
  39 #define ALIGN_SKEW_REPEATING_DATA 5
  40
  41 /// Writes one byte to output buffer and updates the alignment counter.
  42 #define write_byte(b) \
  43 do { \
  44         assert(*out_pos < out_size); \
  45         out[*out_pos] = b; \
  46         ++*out_pos; \
  47         ++coder->alignment.out_pos; \
  48 } while (0)
  49
  50
  51 struct lzma_coder_s {
  52         lzma_next_coder next;
  53         bool next_finished;
  54
  55         enum {
  56                 SEQ_FILL,
  57                 SEQ_FLUSH,
  58                 SEQ_RLE_COUNT_0,
  59                 SEQ_RLE_COUNT_1,
  60                 SEQ_RLE_COUNT_2,
  61                 SEQ_RLE_COUNT_3,
  62                 SEQ_RLE_SIZE,
  63                 SEQ_RLE_DATA,
  64                 SEQ_DATA_SIZE_0,
  65                 SEQ_DATA_SIZE_1,
  66                 SEQ_DATA_SIZE_2,
  67                 SEQ_DATA_SIZE_3,
  68                 SEQ_DATA,
  69                 SEQ_SUBFILTER_INIT,
  70                 SEQ_SUBFILTER_FLAGS,
  71         } sequence;
  72
  73         /// Pointer to the options given by the application. This is used
  74         /// for two-way communication with the application.
  75         lzma_options_subblock *options;
  76
  77         /// Position in various arrays.
  78         size_t pos;
  79
  80         /// Holds subblock.size - 1 or rle.size - 1 when encoding size
  81         /// of Data or Repeat Count.
  82         uint32_t tmp;
  83
  84         struct {
  85                 /// This is a copy of options->alignment, or
  86                 /// LZMA_SUBBLOCK_ALIGNMENT_DEFAULT if options is NULL.
  87                 uint32_t multiple;
  88
  89                 /// Number of input bytes which we have processed and started
  90                 /// writing out. 32-bit integer is enough since we care only
  91                 /// about the lowest bits when fixing alignment.
  92                 uint32_t in_pos;
  93
  94                 /// Number of bytes written out.
  95                 uint32_t out_pos;
  96         } alignment;
  97
  98         struct {
  99                 /// Pointer to allocated buffer holding the Data field
 100                 /// of Subblock Type "Data".
 101                 uint8_t *data;
 102
 103                 /// Number of bytes in the buffer.
 104                 size_t size;
 105
 106                 /// Allocated size of the buffer.
 107                 size_t limit;
 108
 109                 /// Number of input bytes that we have already read but
 110                 /// not yet started writing out. This can be different
 111                 /// to `size' when using Subfilter. That's why we track
 112                 /// in_pending separately for RLE (see below).
 113                 uint32_t in_pending;
 114         } subblock;
 115
 116         struct {
 117                 /// Buffer to hold the data that may be coded with
 118                 /// Subblock Type `Repeating Data'.
 119                 uint8_t buffer[LZMA_SUBBLOCK_RLE_MAX];
 120
 121                 /// Number of bytes in buffer[].
 122                 size_t size;
 123
 124                 /// Number of times the first `size' bytes of buffer[]
 125                 /// will be repeated.
 126                 uint64_t count;
 127
 128                 /// Like subblock.in_pending above, but for RLE.
 129                 uint32_t in_pending;
 130         } rle;
 131
 132         struct {
 133                 enum {
 134                         SUB_NONE,
 135                         SUB_SET,
 136                         SUB_RUN,
 137                         SUB_FLUSH,
 138                         SUB_FINISH,
 139                         SUB_END_MARKER,
 140                 } mode;
 141
 142                 /// This is a copy of options->allow_subfilters. We use
 143                 /// this to verify that the application doesn't change
 144                 /// the value of allow_subfilters.
 145                 bool allow;
 146
 147                 /// When this is true, application is not allowed to modify
 148                 /// options->subblock_mode. We may still modify it here.
 149                 bool mode_locked;
 150
 151                 /// True if we have encoded at least one byte of data with
 152                 /// the Subfilter.
 153                 bool got_input;
 154
 155                 /// Track the amount of input available once
 156                 /// LZMA_SUBFILTER_FINISH has been enabled.
 157                 /// This is needed for sanity checking (kind
 158                 /// of duplicating what common/code.c does).
 159                 size_t in_avail;
 160
 161                 /// Buffer for the Filter Flags field written after
 162                 /// the `Set Subfilter' indicator.
 163                 uint8_t *flags;
 164
 165                 /// Size of Filter Flags field.
 166                 uint32_t flags_size;
 167
 168                 /// Pointers to Subfilter.
 169                 lzma_next_coder subcoder;
 170
 171         } subfilter;
 172
 173         /// Temporary buffer used when we are not the last filter in the chain.
 174         struct {
 175                 size_t pos;
 176                 size_t size;
 177                 uint8_t buffer[LZMA_BUFFER_SIZE];
 178         } temp;
 179 };
 180
 181
 182 /// \brief      Aligns the output buffer
 183 ///
 184 /// Aligns the output buffer so that after skew bytes the output position is
 185 /// a multiple of coder->alignment.multiple.
 186 static bool
 187 subblock_align(lzma_coder *coder, uint8_t *restrict out,
 188                 size_t *restrict out_pos, size_t out_size,
 189                 size_t chunk_size, uint32_t skew)
 190 {
 191         assert(*out_pos < out_size);
 192
 193         // Fix the alignment only if it makes sense at least a little.
 194         if (chunk_size >= MIN_CHUNK_SIZE_FOR_ALIGN) {
 195                 const uint32_t target = coder->alignment.in_pos
 196                                 % coder->alignment.multiple;
 197
 198                 while ((coder->alignment.out_pos + skew)
 199                                 % coder->alignment.multiple != target) {
 200                         // Zero indicates padding.
 201                         write_byte(0x00);
 202
 203                         // Check if output buffer got full and indicate it to
 204                         // the caller.
 205                         if (*out_pos == out_size)
 206                                 return true;
 207                 }
 208         }
 209
 210         // Output buffer is not full.
 211         return false;
 212 }
 213
 214
 215 /// \brief      Checks if buffer contains repeated data
 216 ///
 217 /// \param      needle      Buffer containing a single repeat chunk
 218 /// \param      needle_size Size of needle in bytes
 219 /// \param      buf         Buffer to search for repeated needles
 220 /// \param      buf_chunks  Buffer size is buf_chunks * needle_size.
 221 ///
 222 /// \return     True if the whole buf is filled with repeated needles.
 223 ///
 224 static bool
 225 is_repeating(const uint8_t *restrict needle, size_t needle_size,
 226                 const uint8_t *restrict buf, size_t buf_chunks)
 227 {
 228         while (buf_chunks-- != 0) {
 229                 if (memcmp(buf, needle, needle_size) != 0)
 230                         return false;
 231
 232                 buf += needle_size;
 233         }
 234
 235         return true;
 236 }
 237
 238
 239 /// \brief      Optimizes the repeating style and updates coder->sequence
 240 static void
 241 subblock_rle_flush(lzma_coder *coder)
 242 {
 243         // The Subblock decoder can use memset() when the size of the data
 244         // being repeated is one byte, so we check if the RLE buffer is
 245         // filled with a single repeating byte.
 246         if (coder->rle.size > 1) {
 247                 const uint8_t b = coder->rle.buffer[0];
 248                 size_t i = 0;
 249                 while (true) {
 250                         if (coder->rle.buffer[i] != b)
 251                                 break;
 252
 253                         if (++i == coder->rle.size) {
 254                                 // TODO Integer overflow check maybe,
 255                                 // although this needs at least 2**63 bytes
 256                                 // of input until it gets triggered...
 257                                 coder->rle.count *= coder->rle.size;
 258                                 coder->rle.size = 1;
 259                                 break;
 260                         }
 261                 }
 262         }
 263
 264         if (coder->rle.count == 1) {
 265                 // The buffer should be repeated only once. It is
 266                 // waste of space to use Repeating Data. Instead,
 267                 // write a regular Data Subblock. See SEQ_RLE_COUNT_0
 268                 // in subblock_buffer() for more info.
 269                 coder->tmp = coder->rle.size - 1;
 270         } else if (coder->rle.count > REPEAT_COUNT_MAX) {
 271                 // There's so much to repeat that it doesn't fit into
 272                 // 28-bit integer. We will write two or more Subblocks
 273                 // of type Repeating Data.
 274                 coder->tmp = REPEAT_COUNT_MAX - 1;
 275         } else {
 276                 coder->tmp = coder->rle.count - 1;
 277         }
 278
 279         coder->sequence = SEQ_RLE_COUNT_0;
 280
 281         return;
 282 }
 283
 284
 285 /// \brief      Resizes coder->subblock.data for a new size limit
 286 static lzma_ret
 287 subblock_data_size(lzma_coder *coder, lzma_allocator *allocator,
 288                 size_t new_limit)
 289 {
 290         // Verify that the new limit is valid.
 291         if (new_limit < LZMA_SUBBLOCK_DATA_SIZE_MIN
 292                         || new_limit > LZMA_SUBBLOCK_DATA_SIZE_MAX)
 293                 return LZMA_OPTIONS_ERROR;
 294
 295         // Ff the new limit is different than the previous one, we need
 296         // to reallocate the data buffer.
 297         if (new_limit != coder->subblock.limit) {
 298                 lzma_free(coder->subblock.data, allocator);
 299                 coder->subblock.data = lzma_alloc(new_limit, allocator);
 300                 if (coder->subblock.data == NULL)
 301                         return LZMA_MEM_ERROR;
 302         }
 303
 304         coder->subblock.limit = new_limit;
 305
 306         return LZMA_OK;
 307 }
 308
 309
 310 static lzma_ret
 311 subblock_buffer(lzma_coder *coder, lzma_allocator *allocator,
 312                 const uint8_t *restrict in, size_t *restrict in_pos,
 313                 size_t in_size, uint8_t *restrict out,
 314                 size_t *restrict out_pos, size_t out_size, lzma_action action)
 315 {
 316         // Changing allow_subfilter is not allowed.
 317         if (coder->options != NULL && coder->subfilter.allow
 318                         != coder->options->allow_subfilters)
 319                 return LZMA_PROG_ERROR;
 320
 321         // Check if we need to do something special with the Subfilter.
 322         if (coder->subfilter.allow) {
 323                 assert(coder->options != NULL);
 324
 325                 // See if subfilter_mode has been changed.
 326                 switch (coder->options->subfilter_mode) {
 327                 case LZMA_SUBFILTER_NONE:
 328                         if (coder->subfilter.mode != SUB_NONE)
 329                                 return LZMA_PROG_ERROR;
 330                         break;
 331
 332                 case LZMA_SUBFILTER_SET:
 333                         if (coder->subfilter.mode_locked
 334                                         || coder->subfilter.mode != SUB_NONE)
 335                                 return LZMA_PROG_ERROR;
 336
 337                         coder->subfilter.mode = SUB_SET;
 338                         coder->subfilter.got_input = false;
 339
 340                         if (coder->sequence == SEQ_FILL)
 341                                 coder->sequence = SEQ_FLUSH;
 342
 343                         break;
 344
 345                 case LZMA_SUBFILTER_RUN:
 346                         if (coder->subfilter.mode != SUB_RUN)
 347                                 return LZMA_PROG_ERROR;
 348
 349                         break;
 350
 351                 case LZMA_SUBFILTER_FINISH: {
 352                         const size_t in_avail = in_size - *in_pos;
 353
 354                         if (coder->subfilter.mode == SUB_RUN) {
 355                                 if (coder->subfilter.mode_locked)
 356                                         return LZMA_PROG_ERROR;
 357
 358                                 coder->subfilter.mode = SUB_FINISH;
 359                                 coder->subfilter.in_avail = in_avail;
 360
 361                         } else if (coder->subfilter.mode != SUB_FINISH
 362                                         || coder->subfilter.in_avail
 363                                                 != in_avail) {
 364                                 return LZMA_PROG_ERROR;
 365                         }
 366
 367                         break;
 368                 }
 369
 370                 default:
 371                         return LZMA_OPTIONS_ERROR;
 372                 }
 373
 374                 // If we are sync-flushing or finishing, the application may
 375                 // no longer change subfilter_mode. Note that this check is
 376                 // done after checking the new subfilter_mode above; this
 377                 // way the application may e.g. set LZMA_SUBFILTER_SET and
 378                 // LZMA_SYNC_FLUSH at the same time, but it cannot modify
 379                 // subfilter_mode on the later lzma_code() calls before
 380                 // we have returned LZMA_STREAM_END.
 381                 if (action != LZMA_RUN)
 382                         coder->subfilter.mode_locked = true;
 383         }
 384
 385         // Main loop
 386         while (*out_pos < out_size)
 387         switch (coder->sequence) {
 388         case SEQ_FILL:
 389                 // Grab the new Subblock Data Size and reallocate the buffer.
 390                 if (coder->subblock.size == 0 && coder->options != NULL
 391                                 && coder->options->subblock_data_size
 392                                         != coder->subblock.limit)
 393                         return_if_error(subblock_data_size(coder,
 394                                         allocator, coder->options
 395                                                 ->subblock_data_size));
 396
 397                 if (coder->subfilter.mode == SUB_NONE) {
 398                         assert(coder->subfilter.subcoder.code == NULL);
 399
 400                         // No Subfilter is enabled, just copy the data as is.
 401                         coder->subblock.in_pending += lzma_bufcpy(
 402                                         in, in_pos, in_size,
 403                                         coder->subblock.data,
 404                                         &coder->subblock.size,
 405                                         coder->subblock.limit);
 406
 407                         // If we ran out of input before the whole buffer
 408                         // was filled, return to application.
 409                         if (coder->subblock.size < coder->subblock.limit
 410                                         && action == LZMA_RUN)
 411                                 return LZMA_OK;
 412
 413                 } else {
 414                         assert(coder->options->subfilter_mode
 415                                         != LZMA_SUBFILTER_SET);
 416
 417                         // Using LZMA_FINISH automatically toggles
 418                         // LZMA_SUBFILTER_FINISH.
 419                         //
 420                         // NOTE: It is possible that application had set
 421                         // LZMA_SUBFILTER_SET and LZMA_FINISH at the same
 422                         // time. In that case it is possible that we will
 423                         // cycle to LZMA_SUBFILTER_RUN, LZMA_SUBFILTER_FINISH,
 424                         // and back to LZMA_SUBFILTER_NONE in a single
 425                         // Subblock encoder function call.
 426                         if (action == LZMA_FINISH) {
 427                                 coder->options->subfilter_mode
 428                                                 = LZMA_SUBFILTER_FINISH;
 429                                 coder->subfilter.mode = SUB_FINISH;
 430                         }
 431
 432                         const size_t in_start = *in_pos;
 433
 434                         const lzma_ret ret = coder->subfilter.subcoder.code(
 435                                         coder->subfilter.subcoder.coder,
 436                                         allocator, in, in_pos, in_size,
 437                                         coder->subblock.data,
 438                                         &coder->subblock.size,
 439                                         coder->subblock.limit,
 440                                         coder->subfilter.mode == SUB_FINISH
 441                                                 ? LZMA_FINISH : action);
 442
 443                         const size_t in_used = *in_pos - in_start;
 444                         coder->subblock.in_pending += in_used;
 445                         if (in_used > 0)
 446                                 coder->subfilter.got_input = true;
 447
 448                         coder->subfilter.in_avail = in_size - *in_pos;
 449
 450                         if (ret == LZMA_STREAM_END) {
 451                                 // All currently available input must have
 452                                 // been processed.
 453                                 assert(*in_pos == in_size);
 454
 455                                 // Flush now. Even if coder->subblock.size
 456                                 // happened to be zero, we still need to go
 457                                 // to SEQ_FLUSH to possibly finish RLE or
 458                                 // write the Subfilter Unset indicator.
 459                                 coder->sequence = SEQ_FLUSH;
 460
 461                                 if (coder->subfilter.mode == SUB_RUN) {
 462                                         // Flushing with Subfilter enabled.
 463                                         assert(action == LZMA_SYNC_FLUSH);
 464                                         coder->subfilter.mode = SUB_FLUSH;
 465                                         break;
 466                                 }
 467
 468                                 // Subfilter finished its job.
 469                                 assert(coder->subfilter.mode == SUB_FINISH
 470                                                 || action == LZMA_FINISH);
 471
 472                                 // At least one byte of input must have been
 473                                 // encoded with the Subfilter. This is
 474                                 // required by the file format specification.
 475                                 if (!coder->subfilter.got_input)
 476                                         return LZMA_PROG_ERROR;
 477
 478                                 // We don't strictly need to do this, but
 479                                 // doing it sounds like a good idea, because
 480                                 // otherwise the Subfilter's memory could be
 481                                 // left allocated for long time, and would
 482                                 // just waste memory.
 483                                 lzma_next_end(&coder->subfilter.subcoder,
 484                                                 allocator);
 485
 486                                 // We need to flush the currently buffered
 487                                 // data and write Unset Subfilter marker.
 488                                 // Note that we cannot set
 489                                 // coder->options->subfilter_mode to
 490                                 // LZMA_SUBFILTER_NONE yet, because we
 491                                 // haven't written the Unset Subfilter
 492                                 // marker yet.
 493                                 coder->subfilter.mode = SUB_END_MARKER;
 494                                 coder->sequence = SEQ_FLUSH;
 495                                 break;
 496                         }
 497
 498                         // Return if we couldn't fill the buffer or
 499                         // if an error occurred.
 500                         if (coder->subblock.size < coder->subblock.limit
 501                                         || ret != LZMA_OK)
 502                                 return ret;
 503                 }
 504
 505                 coder->sequence = SEQ_FLUSH;
 506
 507                 // SEQ_FILL doesn't produce any output so falling through
 508                 // to SEQ_FLUSH is safe.
 509                 assert(*out_pos < out_size);
 510
 511         // Fall through
 512
 513         case SEQ_FLUSH:
 514                 if (coder->options != NULL) {
 515                         // Update the alignment variable.
 516                         coder->alignment.multiple = coder->options->alignment;
 517                         if (coder->alignment.multiple
 518                                         < LZMA_SUBBLOCK_ALIGNMENT_MIN
 519                                         || coder->alignment.multiple
 520                                         > LZMA_SUBBLOCK_ALIGNMENT_MAX)
 521                                 return LZMA_OPTIONS_ERROR;
 522
 523                         // Run-length encoder
 524                         //
 525                         // First check if there is some data pending and we
 526                         // have an obvious need to flush it immediatelly.
 527                         if (coder->rle.count > 0
 528                                         && (coder->rle.size
 529                                                         != coder->options->rle
 530                                                 || coder->subblock.size
 531                                                         % coder->rle.size)) {
 532                                 subblock_rle_flush(coder);
 533                                 break;
 534                         }
 535
 536                         // Grab the (possibly new) RLE chunk size and
 537                         // validate it.
 538                         coder->rle.size = coder->options->rle;
 539                         if (coder->rle.size > LZMA_SUBBLOCK_RLE_MAX)
 540                                 return LZMA_OPTIONS_ERROR;
 541
 542                         if (coder->subblock.size != 0
 543                                         && coder->rle.size
 544                                                 != LZMA_SUBBLOCK_RLE_OFF
 545                                         && coder->subblock.size
 546                                                 % coder->rle.size == 0) {
 547
 548                                 // Initialize coder->rle.buffer if we don't
 549                                 // have RLE already running.
 550                                 if (coder->rle.count == 0)
 551                                         memcpy(coder->rle.buffer,
 552                                                         coder->subblock.data,
 553                                                         coder->rle.size);
 554
 555                                 // Test if coder->subblock.data is repeating.
 556                                 // If coder->rle.count would overflow, we
 557                                 // force flushing. Forced flushing shouldn't
 558                                 // really happen in real-world situations.
 559                                 const size_t count = coder->subblock.size
 560                                                 / coder->rle.size;
 561                                 if (UINT64_MAX - count > coder->rle.count
 562                                                 && is_repeating(
 563                                                         coder->rle.buffer,
 564                                                         coder->rle.size,
 565                                                         coder->subblock.data,
 566                                                         count)) {
 567                                         coder->rle.count += count;
 568                                         coder->rle.in_pending += coder
 569                                                         ->subblock.in_pending;
 570                                         coder->subblock.in_pending = 0;
 571                                         coder->subblock.size = 0;
 572
 573                                 } else if (coder->rle.count > 0) {
 574                                         // It's not repeating or at least not
 575                                         // with the same byte sequence as the
 576                                         // earlier Subblock Data buffers. We
 577                                         // have some data pending in the RLE
 578                                         // buffer already, so do a flush.
 579                                         // Once flushed, we will check again
 580                                         // if the Subblock Data happens to
 581                                         // contain a different repeating
 582                                         // sequence.
 583                                         subblock_rle_flush(coder);
 584                                         break;
 585                                 }
 586                         }
 587                 }
 588
 589                 // If we now have some data left in coder->subblock, the RLE
 590                 // buffer is empty and we must write a regular Subblock Data.
 591                 if (coder->subblock.size > 0) {
 592                         assert(coder->rle.count == 0);
 593                         coder->tmp = coder->subblock.size - 1;
 594                         coder->sequence = SEQ_DATA_SIZE_0;
 595                         break;
 596                 }
 597
 598                 // Check if we should enable Subfilter.
 599                 if (coder->subfilter.mode == SUB_SET) {
 600                         if (coder->rle.count > 0)
 601                                 subblock_rle_flush(coder);
 602                         else
 603                                 coder->sequence = SEQ_SUBFILTER_INIT;
 604                         break;
 605                 }
 606
 607                 // Check if we have just finished Subfiltering.
 608                 if (coder->subfilter.mode == SUB_END_MARKER) {
 609                         if (coder->rle.count > 0) {
 610                                 subblock_rle_flush(coder);
 611                                 break;
 612                         }
 613
 614                         coder->options->subfilter_mode = LZMA_SUBFILTER_NONE;
 615                         coder->subfilter.mode = SUB_NONE;
 616
 617                         write_byte(0x50);
 618                         if (*out_pos == out_size)
 619                                 return LZMA_OK;
 620                 }
 621
 622                 // Check if we have already written everything.
 623                 if (action != LZMA_RUN && *in_pos == in_size
 624                                 && (coder->subfilter.mode == SUB_NONE
 625                                 || coder->subfilter.mode == SUB_FLUSH)) {
 626                         if (coder->rle.count > 0) {
 627                                 subblock_rle_flush(coder);
 628                                 break;
 629                         }
 630
 631                         if (action == LZMA_SYNC_FLUSH) {
 632                                 if (coder->subfilter.mode == SUB_FLUSH)
 633                                         coder->subfilter.mode = SUB_RUN;
 634
 635                                 coder->subfilter.mode_locked = false;
 636                                 coder->sequence = SEQ_FILL;
 637
 638                         } else {
 639                                 assert(action == LZMA_FINISH);
 640
 641                                 // Write EOPM.
 642                                 // NOTE: No need to use write_byte() here
 643                                 // since we are finishing.
 644                                 out[*out_pos] = 0x10;
 645                                 ++*out_pos;
 646                         }
 647
 648                         return LZMA_STREAM_END;
 649                 }
 650
 651                 // Otherwise we have more work to do.
 652                 coder->sequence = SEQ_FILL;
 653                 break;
 654
 655         case SEQ_RLE_COUNT_0:
 656                 assert(coder->rle.count > 0);
 657
 658                 if (coder->rle.count == 1) {
 659                         // The buffer should be repeated only once. Fix
 660                         // the alignment and write the first byte of
 661                         // Subblock Type `Data'.
 662                         if (subblock_align(coder, out, out_pos, out_size,
 663                                         coder->rle.size, ALIGN_SKEW_DATA))
 664                                 return LZMA_OK;
 665
 666                         write_byte(0x20 | (coder->tmp & 0x0F));
 667
 668                 } else {
 669                         // We have something to actually repeat, which should
 670                         // mean that it takes less space with run-length
 671                         // encoding.
 672                         if (subblock_align(coder, out, out_pos, out_size,
 673                                                 coder->rle.size,
 674                                                 ALIGN_SKEW_REPEATING_DATA))
 675                                 return LZMA_OK;
 676
 677                         write_byte(0x30 | (coder->tmp & 0x0F));
 678                 }
 679
 680                 // NOTE: If we have to write more than one Repeating Data
 681                 // due to rle.count > REPEAT_COUNT_MAX, the subsequent
 682                 // Repeating Data Subblocks may get wrong alignment, because
 683                 // we add rle.in_pending to alignment.in_pos at once instead
 684                 // of adding only as much as this particular Repeating Data
 685                 // consumed input data. Correct alignment is always restored
 686                 // after all the required Repeating Data Subblocks have been
 687                 // written. This problem occurs in such a weird cases that
 688                 // it's not worth fixing.
 689                 coder->alignment.out_pos += coder->rle.size;
 690                 coder->alignment.in_pos += coder->rle.in_pending;
 691                 coder->rle.in_pending = 0;
 692
 693                 coder->sequence = SEQ_RLE_COUNT_1;
 694                 break;
 695
 696         case SEQ_RLE_COUNT_1:
 697                 write_byte(coder->tmp >> 4);
 698                 coder->sequence = SEQ_RLE_COUNT_2;
 699                 break;
 700
 701         case SEQ_RLE_COUNT_2:
 702                 write_byte(coder->tmp >> 12);
 703                 coder->sequence = SEQ_RLE_COUNT_3;
 704                 break;
 705
 706         case SEQ_RLE_COUNT_3:
 707                 write_byte(coder->tmp >> 20);
 708
 709                 // Again, see if we are writing regular Data or Repeating Data.
 710                 // In the former case, we skip SEQ_RLE_SIZE.
 711                 if (coder->rle.count == 1)
 712                         coder->sequence = SEQ_RLE_DATA;
 713                 else
 714                         coder->sequence = SEQ_RLE_SIZE;
 715
 716                 if (coder->rle.count > REPEAT_COUNT_MAX)
 717                         coder->rle.count -= REPEAT_COUNT_MAX;
 718                 else
 719                         coder->rle.count = 0;
 720
 721                 break;
 722
 723         case SEQ_RLE_SIZE:
 724                 assert(coder->rle.size >= LZMA_SUBBLOCK_RLE_MIN);
 725                 assert(coder->rle.size <= LZMA_SUBBLOCK_RLE_MAX);
 726                 write_byte(coder->rle.size - 1);
 727                 coder->sequence = SEQ_RLE_DATA;
 728                 break;
 729
 730         case SEQ_RLE_DATA:
 731                 lzma_bufcpy(coder->rle.buffer, &coder->pos, coder->rle.size,
 732                                 out, out_pos, out_size);
 733                 if (coder->pos < coder->rle.size)
 734                         return LZMA_OK;
 735
 736                 coder->pos = 0;
 737                 coder->sequence = SEQ_FLUSH;
 738                 break;
 739
 740         case SEQ_DATA_SIZE_0:
 741                 // We need four bytes for the Size field.
 742                 if (subblock_align(coder, out, out_pos, out_size,
 743                                 coder->subblock.size, ALIGN_SKEW_DATA))
 744                         return LZMA_OK;
 745
 746                 coder->alignment.out_pos += coder->subblock.size;
 747                 coder->alignment.in_pos += coder->subblock.in_pending;
 748                 coder->subblock.in_pending = 0;
 749
 750                 write_byte(0x20 | (coder->tmp & 0x0F));
 751                 coder->sequence = SEQ_DATA_SIZE_1;
 752                 break;
 753
 754         case SEQ_DATA_SIZE_1:
 755                 write_byte(coder->tmp >> 4);
 756                 coder->sequence = SEQ_DATA_SIZE_2;
 757                 break;
 758
 759         case SEQ_DATA_SIZE_2:
 760                 write_byte(coder->tmp >> 12);
 761                 coder->sequence = SEQ_DATA_SIZE_3;
 762                 break;
 763
 764         case SEQ_DATA_SIZE_3:
 765                 write_byte(coder->tmp >> 20);
 766                 coder->sequence = SEQ_DATA;
 767                 break;
 768
 769         case SEQ_DATA:
 770                 lzma_bufcpy(coder->subblock.data, &coder->pos,
 771                                 coder->subblock.size, out, out_pos, out_size);
 772                 if (coder->pos < coder->subblock.size)
 773                         return LZMA_OK;
 774
 775                 coder->subblock.size = 0;
 776                 coder->pos = 0;
 777                 coder->sequence = SEQ_FLUSH;
 778                 break;
 779
 780         case SEQ_SUBFILTER_INIT: {
 781                 assert(coder->subblock.size == 0);
 782                 assert(coder->subblock.in_pending == 0);
 783                 assert(coder->rle.count == 0);
 784                 assert(coder->rle.in_pending == 0);
 785                 assert(coder->subfilter.mode == SUB_SET);
 786                 assert(coder->options != NULL);
 787
 788                 // There must be a filter specified.
 789                 if (coder->options->subfilter_options.id == LZMA_VLI_UNKNOWN)
 790                         return LZMA_OPTIONS_ERROR;
 791
 792                 // Initialize a raw encoder to work as a Subfilter.
 793                 lzma_filter options[2];
 794                 options[0] = coder->options->subfilter_options;
 795                 options[1].id = LZMA_VLI_UNKNOWN;
 796
 797                 return_if_error(lzma_raw_encoder_init(
 798                                 &coder->subfilter.subcoder, allocator,
 799                                 options));
 800
 801                 // Encode the Filter Flags field into a buffer. This should
 802                 // never fail since we have already successfully initialized
 803                 // the Subfilter itself. Check it still, and return
 804                 // LZMA_PROG_ERROR instead of whatever the ret would say.
 805                 lzma_ret ret = lzma_filter_flags_size(
 806                                 &coder->subfilter.flags_size, options);
 807                 assert(ret == LZMA_OK);
 808                 if (ret != LZMA_OK)
 809                         return LZMA_PROG_ERROR;
 810
 811                 coder->subfilter.flags = lzma_alloc(
 812                                 coder->subfilter.flags_size, allocator);
 813                 if (coder->subfilter.flags == NULL)
 814                         return LZMA_MEM_ERROR;
 815
 816                 // Now we have a big-enough buffer. Encode the Filter Flags.
 817                 // Like above, this should never fail.
 818                 size_t dummy = 0;
 819                 ret = lzma_filter_flags_encode(options, coder->subfilter.flags,
 820                                 &dummy, coder->subfilter.flags_size);
 821                 assert(ret == LZMA_OK);
 822                 assert(dummy == coder->subfilter.flags_size);
 823                 if (ret != LZMA_OK || dummy != coder->subfilter.flags_size)
 824                         return LZMA_PROG_ERROR;
 825
 826                 // Write a Subblock indicating a new Subfilter.
 827                 write_byte(0x40);
 828
 829                 coder->options->subfilter_mode = LZMA_SUBFILTER_RUN;
 830                 coder->subfilter.mode = SUB_RUN;
 831                 coder->alignment.out_pos += coder->subfilter.flags_size;
 832                 coder->sequence = SEQ_SUBFILTER_FLAGS;
 833
 834                 // It is safe to fall through because SEQ_SUBFILTER_FLAGS
 835                 // uses lzma_bufcpy() which doesn't write unless there is
 836                 // output space.
 837         }
 838
 839         // Fall through
 840
 841         case SEQ_SUBFILTER_FLAGS:
 842                 // Copy the Filter Flags to the output stream.
 843                 lzma_bufcpy(coder->subfilter.flags, &coder->pos,
 844                                 coder->subfilter.flags_size,
 845                                 out, out_pos, out_size);
 846                 if (coder->pos < coder->subfilter.flags_size)
 847                         return LZMA_OK;
 848
 849                 lzma_free(coder->subfilter.flags, allocator);
 850                 coder->subfilter.flags = NULL;
 851
 852                 coder->pos = 0;
 853                 coder->sequence = SEQ_FILL;
 854                 break;
 855
 856         default:
 857                 return LZMA_PROG_ERROR;
 858         }
 859
 860         return LZMA_OK;
 861 }
 862
 863
 864 static lzma_ret
 865 subblock_encode(lzma_coder *coder, lzma_allocator *allocator,
 866                 const uint8_t *restrict in, size_t *restrict in_pos,
 867                 size_t in_size, uint8_t *restrict out,
 868                 size_t *restrict out_pos, size_t out_size, lzma_action action)
 869 {
 870         if (coder->next.code == NULL)
 871                 return subblock_buffer(coder, allocator, in, in_pos, in_size,
 872                                 out, out_pos, out_size, action);
 873
 874         while (*out_pos < out_size
 875                         && (*in_pos < in_size || action != LZMA_RUN)) {
 876                 if (!coder->next_finished
 877                                 && coder->temp.pos == coder->temp.size) {
 878                         coder->temp.pos = 0;
 879                         coder->temp.size = 0;
 880
 881                         const lzma_ret ret = coder->next.code(coder->next.coder,
 882                                         allocator, in, in_pos, in_size,
 883                                         coder->temp.buffer, &coder->temp.size,
 884                                         LZMA_BUFFER_SIZE, action);
 885                         if (ret == LZMA_STREAM_END) {
 886                                 assert(action != LZMA_RUN);
 887                                 coder->next_finished = true;
 888                         } else if (coder->temp.size == 0 || ret != LZMA_OK) {
 889                                 return ret;
 890                         }
 891                 }
 892
 893                 const lzma_ret ret = subblock_buffer(coder, allocator,
 894                                 coder->temp.buffer, &coder->temp.pos,
 895                                 coder->temp.size, out, out_pos, out_size,
 896                                 coder->next_finished ? LZMA_FINISH : LZMA_RUN);
 897                 if (ret == LZMA_STREAM_END) {
 898                         assert(action != LZMA_RUN);
 899                         assert(coder->next_finished);
 900                         return LZMA_STREAM_END;
 901                 }
 902
 903                 if (ret != LZMA_OK)
 904                         return ret;
 905         }
 906
 907         return LZMA_OK;
 908 }
 909
 910
 911 static void
 912 subblock_encoder_end(lzma_coder *coder, lzma_allocator *allocator)
 913 {
 914         lzma_next_end(&coder->next, allocator);
 915         lzma_next_end(&coder->subfilter.subcoder, allocator);
 916         lzma_free(coder->subblock.data, allocator);
 917         lzma_free(coder->subfilter.flags, allocator);
 918         lzma_free(coder, allocator);
 919         return;
 920 }
 921
 922
 923 extern lzma_ret
 924 lzma_subblock_encoder_init(lzma_next_coder *next, lzma_allocator *allocator,
 925                 const lzma_filter_info *filters)
 926 {
 927         if (next->coder == NULL) {
 928                 next->coder = lzma_alloc(sizeof(lzma_coder), allocator);
 929                 if (next->coder == NULL)
 930                         return LZMA_MEM_ERROR;
 931
 932                 next->code = &subblock_encode;
 933                 next->end = &subblock_encoder_end;
 934
 935                 next->coder->next = LZMA_NEXT_CODER_INIT;
 936                 next->coder->subblock.data = NULL;
 937                 next->coder->subblock.limit = 0;
 938                 next->coder->subfilter.subcoder = LZMA_NEXT_CODER_INIT;
 939         } else {
 940                 lzma_next_end(&next->coder->subfilter.subcoder,
 941                                 allocator);
 942                 lzma_free(next->coder->subfilter.flags, allocator);
 943         }
 944
 945         next->coder->subfilter.flags = NULL;
 946
 947         next->coder->next_finished = false;
 948         next->coder->sequence = SEQ_FILL;
 949         next->coder->options = filters[0].options;
 950         next->coder->pos = 0;
 951
 952         next->coder->alignment.in_pos = 0;
 953         next->coder->alignment.out_pos = 0;
 954         next->coder->subblock.size = 0;
 955         next->coder->subblock.in_pending = 0;
 956         next->coder->rle.count = 0;
 957         next->coder->rle.in_pending = 0;
 958         next->coder->subfilter.mode = SUB_NONE;
 959         next->coder->subfilter.mode_locked = false;
 960
 961         next->coder->temp.pos = 0;
 962         next->coder->temp.size = 0;
 963
 964         // Grab some values from the options structure if it is available.
 965         size_t subblock_size_limit;
 966         if (next->coder->options != NULL) {
 967                 if (next->coder->options->alignment
 968                                         < LZMA_SUBBLOCK_ALIGNMENT_MIN
 969                                 || next->coder->options->alignment
 970                                         > LZMA_SUBBLOCK_ALIGNMENT_MAX) {
 971                         subblock_encoder_end(next->coder, allocator);
 972                         return LZMA_OPTIONS_ERROR;
 973                 }
 974                 next->coder->alignment.multiple
 975                                 = next->coder->options->alignment;
 976                 next->coder->subfilter.allow
 977                                 = next->coder->options->allow_subfilters;
 978                 subblock_size_limit = next->coder->options->subblock_data_size;
 979         } else {
 980                 next->coder->alignment.multiple
 981                                 = LZMA_SUBBLOCK_ALIGNMENT_DEFAULT;
 982                 next->coder->subfilter.allow = false;
 983                 subblock_size_limit = LZMA_SUBBLOCK_DATA_SIZE_DEFAULT;
 984         }
 985
 986         return_if_error(subblock_data_size(next->coder, allocator,
 987                                 subblock_size_limit));
 988
 989         return lzma_next_filter_init(
 990                         &next->coder->next, allocator, filters + 1);
 991 }