contrib/xz/src/liblzma/subblock/subblock_encoder.c

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