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 "raw_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         bool use_eopm;
  55
  56         enum {
  57                 SEQ_FILL,
  58                 SEQ_FLUSH,
  59                 SEQ_RLE_COUNT_0,
  60                 SEQ_RLE_COUNT_1,
  61                 SEQ_RLE_COUNT_2,
  62                 SEQ_RLE_COUNT_3,
  63                 SEQ_RLE_SIZE,
  64                 SEQ_RLE_DATA,
  65                 SEQ_DATA_SIZE_0,
  66                 SEQ_DATA_SIZE_1,
  67                 SEQ_DATA_SIZE_2,
  68                 SEQ_DATA_SIZE_3,
  69                 SEQ_DATA,
  70                 SEQ_SUBFILTER_INIT,
  71                 SEQ_SUBFILTER_FLAGS,
  72         } sequence;
  73
  74         /// Pointer to the options given by the application. This is used
  75         /// for two-way communication with the application.
  76         lzma_options_subblock *options;
  77
  78         /// Position in various arrays.
  79         size_t pos;
  80
  81         /// Holds subblock.size - 1 or rle.size - 1 when encoding size
  82         /// of Data or Repeat Count.
  83         uint32_t tmp;
  84
  85         struct {
  86                 /// This is a copy of options->alignment, or
  87                 /// LZMA_SUBBLOCK_ALIGNMENT_DEFAULT if options is NULL.
  88                 uint32_t multiple;
  89
  90                 /// Number of input bytes which we have processed and started
  91                 /// writing out. 32-bit integer is enough since we care only
  92                 /// about the lowest bits when fixing alignment.
  93                 uint32_t in_pos;
  94
  95                 /// Number of bytes written out.
  96                 uint32_t out_pos;
  97         } alignment;
  98
  99         struct {
 100                 /// Pointer to allocated buffer holding the Data field
 101                 /// of Subblock Type "Data".
 102                 uint8_t *data;
 103
 104                 /// Number of bytes in the buffer.
 105                 size_t size;
 106
 107                 /// Allocated size of the buffer.
 108                 size_t limit;
 109
 110                 /// Number of input bytes that we have already read but
 111                 /// not yet started writing out. This can be different
 112                 /// to `size' when using Subfilter. That's why we track
 113                 /// in_pending separately for RLE (see below).
 114                 uint32_t in_pending;
 115         } subblock;
 116
 117         struct {
 118                 /// Buffer to hold the data that may be coded with
 119                 /// Subblock Type `Repeating Data'.
 120                 uint8_t buffer[LZMA_SUBBLOCK_RLE_MAX];
 121
 122                 /// Number of bytes in buffer[].
 123                 size_t size;
 124
 125                 /// Number of times the first `size' bytes of buffer[]
 126                 /// will be repeated.
 127                 uint64_t count;
 128
 129                 /// Like subblock.in_pending above, but for RLE.
 130                 uint32_t in_pending;
 131         } rle;
 132
 133         struct {
 134                 enum {
 135                         SUB_NONE,
 136                         SUB_SET,
 137                         SUB_RUN,
 138                         SUB_FLUSH,
 139                         SUB_FINISH,
 140                         SUB_END_MARKER,
 141                 } mode;
 142
 143                 /// This is a copy of options->allow_subfilters. We use
 144                 /// this to verify that the application doesn't change
 145                 /// the value of allow_subfilters.
 146                 bool allow;
 147
 148                 /// When this is true, application is not allowed to modify
 149                 /// options->subblock_mode. We may still modify it here.
 150                 bool mode_locked;
 151
 152                 /// True if we have encoded at least one byte of data with
 153                 /// the Subfilter.
 154                 bool got_input;
 155
 156                 /// Track the amount of input available once
 157                 /// LZMA_SUBFILTER_FINISH has been enabled.
 158                 /// This is needed for sanity checking (kind
 159                 /// of duplicating what common/code.c does).
 160                 size_t in_avail;
 161
 162                 /// Buffer for the Filter Flags field written after
 163                 /// the `Set Subfilter' indicator.
 164                 uint8_t *flags;
 165
 166                 /// Size of Filter Flags field.
 167                 uint32_t flags_size;
 168
 169                 /// Pointers to Subfilter.
 170                 lzma_next_coder subcoder;
 171
 172         } subfilter;
 173
 174         /// Temporary buffer used when we are not the last filter in the chain.
 175         struct {
 176                 size_t pos;
 177                 size_t size;
 178                 uint8_t buffer[LZMA_BUFFER_SIZE];
 179         } temp;
 180 };
 181
 182
 183 /// \brief      Aligns the output buffer
 184 ///
 185 /// Aligns the output buffer so that after skew bytes the output position is
 186 /// a multiple of coder->alignment.multiple.
 187 static bool
 188 subblock_align(lzma_coder *coder, uint8_t *restrict out,
 189                 size_t *restrict out_pos, size_t out_size,
 190                 size_t chunk_size, uint32_t skew)
 191 {
 192         assert(*out_pos < out_size);
 193
 194         // Fix the alignment only if it makes sense at least a little.
 195         if (chunk_size >= MIN_CHUNK_SIZE_FOR_ALIGN) {
 196                 const uint32_t target = coder->alignment.in_pos
 197                                 % coder->alignment.multiple;
 198
 199                 while ((coder->alignment.out_pos + skew)
 200                                 % coder->alignment.multiple != target) {
 201                         // Zero indicates padding.
 202                         write_byte(0x00);
 203
 204                         // Check if output buffer got full and indicate it to
 205                         // the caller.
 206                         if (*out_pos == out_size)
 207                                 return true;
 208                 }
 209         }
 210
 211         // Output buffer is not full.
 212         return false;
 213 }
 214
 215
 216 /// \brief      Checks if buffer contains repeated data
 217 ///
 218 /// \param      needle      Buffer containing a single repeat chunk
 219 /// \param      needle_size Size of needle in bytes
 220 /// \param      buf         Buffer to search for repeated needles
 221 /// \param      buf_chunks  Buffer size is buf_chunks * needle_size.
 222 ///
 223 /// \return     True if the whole buf is filled with repeated needles.
 224 ///
 225 static bool
 226 is_repeating(const uint8_t *restrict needle, size_t needle_size,
 227                 const uint8_t *restrict buf, size_t buf_chunks)
 228 {
 229         while (buf_chunks-- != 0) {
 230                 if (memcmp(buf, needle, needle_size) != 0)
 231                         return false;
 232
 233                 buf += needle_size;
 234         }
 235
 236         return true;
 237 }
 238
 239
 240 /// \brief      Optimizes the repeating style and updates coder->sequence
 241 static void
 242 subblock_rle_flush(lzma_coder *coder)
 243 {
 244         // The Subblock decoder can use memset() when the size of the data
 245         // being repeated is one byte, so we check if the RLE buffer is
 246         // filled with a single repeating byte.
 247         if (coder->rle.size > 1) {
 248                 const uint8_t b = coder->rle.buffer[0];
 249                 size_t i = 0;
 250                 while (true) {
 251                         if (coder->rle.buffer[i] != b)
 252                                 break;
 253
 254                         if (++i == coder->rle.size) {
 255                                 // TODO Integer overflow check maybe,
 256                                 // although this needs at least 2**63 bytes
 257                                 // of input until it gets triggered...
 258                                 coder->rle.count *= coder->rle.size;
 259                                 coder->rle.size = 1;
 260                                 break;
 261                         }
 262                 }
 263         }
 264
 265         if (coder->rle.count == 1) {
 266                 // The buffer should be repeated only once. It is
 267                 // waste of space to use Repeating Data. Instead,
 268                 // write a regular Data Subblock. See SEQ_RLE_COUNT_0
 269                 // in subblock_buffer() for more info.
 270                 coder->tmp = coder->rle.size - 1;
 271         } else if (coder->rle.count > REPEAT_COUNT_MAX) {
 272                 // There's so much to repeat that it doesn't fit into
 273                 // 28-bit integer. We will write two or more Subblocks
 274                 // of type Repeating Data.
 275                 coder->tmp = REPEAT_COUNT_MAX - 1;
 276         } else {
 277                 coder->tmp = coder->rle.count - 1;
 278         }
 279
 280         coder->sequence = SEQ_RLE_COUNT_0;
 281
 282         return;
 283 }
 284
 285
 286 /// \brief      Resizes coder->subblock.data for a new size limit
 287 static lzma_ret
 288 subblock_data_size(lzma_coder *coder, lzma_allocator *allocator,
 289                 size_t new_limit)
 290 {
 291         // Verify that the new limit is valid.
 292         if (new_limit < LZMA_SUBBLOCK_DATA_SIZE_MIN
 293                         || new_limit > LZMA_SUBBLOCK_DATA_SIZE_MAX)
 294                 return LZMA_HEADER_ERROR;
 295
 296         // Ff the new limit is different than the previous one, we need
 297         // to reallocate the data buffer.
 298         if (new_limit != coder->subblock.limit) {
 299                 lzma_free(coder->subblock.data, allocator);
 300                 coder->subblock.data = lzma_alloc(new_limit, allocator);
 301                 if (coder->subblock.data == NULL)
 302                         return LZMA_MEM_ERROR;
 303         }
 304
 305         coder->subblock.limit = new_limit;
 306
 307         return LZMA_OK;
 308 }
 309
 310
 311 static lzma_ret
 312 subblock_buffer(lzma_coder *coder, lzma_allocator *allocator,
 313                 const uint8_t *restrict in, size_t *restrict in_pos,
 314                 size_t in_size, uint8_t *restrict out,
 315                 size_t *restrict out_pos, size_t out_size, lzma_action action)
 316 {
 317         // Changing allow_subfilter is not allowed.
 318         if (coder->options != NULL && coder->subfilter.allow
 319                         != coder->options->allow_subfilters)
 320                 return LZMA_PROG_ERROR;
 321
 322         // Check if we need to do something special with the Subfilter.
 323         if (coder->subfilter.allow) {
 324                 assert(coder->options != NULL);
 325
 326                 // See if subfilter_mode has been changed.
 327                 switch (coder->options->subfilter_mode) {
 328                 case LZMA_SUBFILTER_NONE:
 329                         if (coder->subfilter.mode != SUB_NONE)
 330                                 return LZMA_PROG_ERROR;
 331                         break;
 332
 333                 case LZMA_SUBFILTER_SET:
 334                         if (coder->subfilter.mode_locked
 335                                         || coder->subfilter.mode != SUB_NONE)
 336                                 return LZMA_PROG_ERROR;
 337
 338                         coder->subfilter.mode = SUB_SET;
 339                         coder->subfilter.got_input = false;
 340
 341                         if (coder->sequence == SEQ_FILL)
 342                                 coder->sequence = SEQ_FLUSH;
 343
 344                         break;
 345
 346                 case LZMA_SUBFILTER_RUN:
 347                         if (coder->subfilter.mode != SUB_RUN)
 348                                 return LZMA_PROG_ERROR;
 349
 350                         break;
 351
 352                 case LZMA_SUBFILTER_FINISH: {
 353                         const size_t in_avail = in_size - *in_pos;
 354
 355                         if (coder->subfilter.mode == SUB_RUN) {
 356                                 if (coder->subfilter.mode_locked)
 357                                         return LZMA_PROG_ERROR;
 358
 359                                 coder->subfilter.mode = SUB_FINISH;
 360                                 coder->subfilter.in_avail = in_avail;
 361
 362                         } else if (coder->subfilter.mode != SUB_FINISH
 363                                         || coder->subfilter.in_avail
 364                                                 != in_avail) {
 365                                 return LZMA_PROG_ERROR;
 366                         }
 367
 368                         break;
 369                 }
 370
 371                 default:
 372                         return LZMA_HEADER_ERROR;
 373                 }
 374
 375                 // If we are sync-flushing or finishing, the application may
 376                 // no longer change subfilter_mode. Note that this check is
 377                 // done after checking the new subfilter_mode above; this
 378                 // way the application may e.g. set LZMA_SUBFILTER_SET and
 379                 // LZMA_SYNC_FLUSH at the same time, but it cannot modify
 380                 // subfilter_mode on the later lzma_code() calls before
 381                 // we have returned LZMA_STREAM_END.
 382                 if (action != LZMA_RUN)
 383                         coder->subfilter.mode_locked = true;
 384         }
 385
 386         // Main loop
 387         while (*out_pos < out_size)
 388         switch (coder->sequence) {
 389         case SEQ_FILL:
 390                 // Grab the new Subblock Data Size and reallocate the buffer.
 391                 if (coder->subblock.size == 0 && coder->options != NULL
 392                                 && coder->options->subblock_data_size
 393                                         != coder->subblock.limit)
 394                         return_if_error(subblock_data_size(coder,
 395                                         allocator, coder->options
 396                                                 ->subblock_data_size));
 397
 398                 if (coder->subfilter.mode == SUB_NONE) {
 399                         assert(coder->subfilter.subcoder.code == NULL);
 400
 401                         // No Subfilter is enabled, just copy the data as is.
 402                         coder->subblock.in_pending += bufcpy(
 403                                         in, in_pos, in_size,
 404                                         coder->subblock.data,
 405                                         &coder->subblock.size,
 406                                         coder->subblock.limit);
 407
 408                         // If we ran out of input before the whole buffer
 409                         // was filled, return to application.
 410                         if (coder->subblock.size < coder->subblock.limit
 411                                         && action == LZMA_RUN)
 412                                 return LZMA_OK;
 413
 414                 } else {
 415                         assert(coder->options->subfilter_mode
 416                                         != LZMA_SUBFILTER_SET);
 417
 418                         // Using LZMA_FINISH automatically toggles
 419                         // LZMA_SUBFILTER_FINISH.
 420                         //
 421                         // NOTE: It is possible that application had set
 422                         // LZMA_SUBFILTER_SET and LZMA_FINISH at the same
 423                         // time. In that case it is possible that we will
 424                         // cycle to LZMA_SUBFILTER_RUN, LZMA_SUBFILTER_FINISH,
 425                         // and back to LZMA_SUBFILTER_NONE in a single
 426                         // Subblock encoder function call.
 427                         if (action == LZMA_FINISH) {
 428                                 coder->options->subfilter_mode
 429                                                 = LZMA_SUBFILTER_FINISH;
 430                                 coder->subfilter.mode = SUB_FINISH;
 431                         }
 432
 433                         const size_t in_start = *in_pos;
 434
 435                         const lzma_ret ret = coder->subfilter.subcoder.code(
 436                                         coder->subfilter.subcoder.coder,
 437                                         allocator, in, in_pos, in_size,
 438                                         coder->subblock.data,
 439                                         &coder->subblock.size,
 440                                         coder->subblock.limit,
 441                                         coder->subfilter.mode == SUB_FINISH
 442                                                 ? LZMA_FINISH : action);
 443
 444                         const size_t in_used = *in_pos - in_start;
 445                         coder->subblock.in_pending += in_used;
 446                         if (in_used > 0)
 447                                 coder->subfilter.got_input = true;
 448
 449                         coder->subfilter.in_avail = in_size - *in_pos;
 450
 451                         if (ret == LZMA_STREAM_END) {
 452                                 // All currently available input must have
 453                                 // been processed.
 454                                 assert(*in_pos == in_size);
 455
 456                                 // Flush now. Even if coder->subblock.size
 457                                 // happened to be zero, we still need to go
 458                                 // to SEQ_FLUSH to possibly finish RLE or
 459                                 // write the Subfilter Unset indicator.
 460                                 coder->sequence = SEQ_FLUSH;
 461
 462                                 if (coder->subfilter.mode == SUB_RUN) {
 463                                         // Flushing with Subfilter enabled.
 464                                         assert(action == LZMA_SYNC_FLUSH);
 465                                         coder->subfilter.mode = SUB_FLUSH;
 466                                         break;
 467                                 }
 468
 469                                 // Subfilter finished its job.
 470                                 assert(coder->subfilter.mode == SUB_FINISH
 471                                                 || action == LZMA_FINISH);
 472
 473                                 // At least one byte of input must have been
 474                                 // encoded with the Subfilter. This is
 475                                 // required by the file format specification.
 476                                 if (!coder->subfilter.got_input)
 477                                         return LZMA_PROG_ERROR;
 478
 479                                 // We don't strictly need to do this, but
 480                                 // doing it sounds like a good idea, because
 481                                 // otherwise the Subfilter's memory could be
 482                                 // left allocated for long time, and would
 483                                 // just waste memory.
 484                                 lzma_next_coder_end(&coder->subfilter.subcoder,
 485                                                 allocator);
 486
 487                                 // We need to flush the currently buffered
 488                                 // data and write Unset Subfilter marker.
 489                                 // Note that we cannot set
 490                                 // coder->options->subfilter_mode to
 491                                 // LZMA_SUBFILTER_NONE yet, because we
 492                                 // haven't written the Unset Subfilter
 493                                 // marker yet.
 494                                 coder->subfilter.mode = SUB_END_MARKER;
 495                                 coder->sequence = SEQ_FLUSH;
 496                                 break;
 497                         }
 498
 499                         // Return if we couldn't fill the buffer or
 500                         // if an error occurred.
 501                         if (coder->subblock.size < coder->subblock.limit
 502                                         || ret != LZMA_OK)
 503                                 return ret;
 504                 }
 505
 506                 coder->sequence = SEQ_FLUSH;
 507
 508                 // SEQ_FILL doesn't produce any output so falling through
 509                 // to SEQ_FLUSH is safe.
 510                 assert(*out_pos < out_size);
 511
 512         // Fall through
 513
 514         case SEQ_FLUSH:
 515                 if (coder->options != NULL) {
 516                         // Update the alignment variable.
 517                         coder->alignment.multiple = coder->options->alignment;
 518                         if (coder->alignment.multiple
 519                                         < LZMA_SUBBLOCK_ALIGNMENT_MIN
 520                                         || coder->alignment.multiple
 521                                         > LZMA_SUBBLOCK_ALIGNMENT_MAX)
 522                                 return LZMA_HEADER_ERROR;
 523
 524                         // Run-length encoder
 525                         //
 526                         // First check if there is some data pending and we
 527                         // have an obvious need to flush it immediatelly.
 528                         if (coder->rle.count > 0
 529                                         && (coder->rle.size
 530                                                         != coder->options->rle
 531                                                 || coder->subblock.size
 532                                                         % coder->rle.size)) {
 533                                 subblock_rle_flush(coder);
 534                                 break;
 535                         }
 536
 537                         // Grab the (possibly new) RLE chunk size and
 538                         // validate it.
 539                         coder->rle.size = coder->options->rle;
 540                         if (coder->rle.size > LZMA_SUBBLOCK_RLE_MAX)
 541                                 return LZMA_HEADER_ERROR;
 542
 543                         if (coder->subblock.size != 0
 544                                         && coder->rle.size
 545                                                 != LZMA_SUBBLOCK_RLE_OFF
 546                                         && coder->subblock.size
 547                                                 % coder->rle.size == 0) {
 548
 549                                 // Initialize coder->rle.buffer if we don't
 550                                 // have RLE already running.
 551                                 if (coder->rle.count == 0)
 552                                         memcpy(coder->rle.buffer,
 553                                                         coder->subblock.data,
 554                                                         coder->rle.size);
 555
 556                                 // Test if coder->subblock.data is repeating.
 557                                 // If coder->rle.count would overflow, we
 558                                 // force flushing. Forced flushing shouldn't
 559                                 // really happen in real-world situations.
 560                                 const size_t count = coder->subblock.size
 561                                                 / coder->rle.size;
 562                                 if (UINT64_MAX - count > coder->rle.count
 563                                                 && is_repeating(
 564                                                         coder->rle.buffer,
 565                                                         coder->rle.size,
 566                                                         coder->subblock.data,
 567                                                         count)) {
 568                                         coder->rle.count += count;
 569                                         coder->rle.in_pending += coder
 570                                                         ->subblock.in_pending;
 571                                         coder->subblock.in_pending = 0;
 572                                         coder->subblock.size = 0;
 573
 574                                 } else if (coder->rle.count > 0) {
 575                                         // It's not repeating or at least not
 576                                         // with the same byte sequence as the
 577                                         // earlier Subblock Data buffers. We
 578                                         // have some data pending in the RLE
 579                                         // buffer already, so do a flush.
 580                                         // Once flushed, we will check again
 581                                         // if the Subblock Data happens to
 582                                         // contain a different repeating
 583                                         // sequence.
 584                                         subblock_rle_flush(coder);
 585                                         break;
 586                                 }
 587                         }
 588                 }
 589
 590                 // If we now have some data left in coder->subblock, the RLE
 591                 // buffer is empty and we must write a regular Subblock Data.
 592                 if (coder->subblock.size > 0) {
 593                         assert(coder->rle.count == 0);
 594                         coder->tmp = coder->subblock.size - 1;
 595                         coder->sequence = SEQ_DATA_SIZE_0;
 596                         break;
 597                 }
 598
 599                 // Check if we should enable Subfilter.
 600                 if (coder->subfilter.mode == SUB_SET) {
 601                         if (coder->rle.count > 0)
 602                                 subblock_rle_flush(coder);
 603                         else
 604                                 coder->sequence = SEQ_SUBFILTER_INIT;
 605                         break;
 606                 }
 607
 608                 // Check if we have just finished Subfiltering.
 609                 if (coder->subfilter.mode == SUB_END_MARKER) {
 610                         if (coder->rle.count > 0) {
 611                                 subblock_rle_flush(coder);
 612                                 break;
 613                         }
 614
 615                         coder->options->subfilter_mode = LZMA_SUBFILTER_NONE;
 616                         coder->subfilter.mode = SUB_NONE;
 617
 618                         write_byte(0x50);
 619                         if (*out_pos == out_size)
 620                                 return LZMA_OK;
 621                 }
 622
 623                 // Check if we have already written everything.
 624                 if (action != LZMA_RUN && *in_pos == in_size
 625                                 && (coder->subfilter.mode == SUB_NONE
 626                                 || coder->subfilter.mode == SUB_FLUSH)) {
 627                         if (coder->rle.count > 0) {
 628                                 subblock_rle_flush(coder);
 629                                 break;
 630                         }
 631
 632                         if (action == LZMA_SYNC_FLUSH) {
 633                                 if (coder->subfilter.mode == SUB_FLUSH)
 634                                         coder->subfilter.mode = SUB_RUN;
 635
 636                                 coder->subfilter.mode_locked = false;
 637                                 coder->sequence = SEQ_FILL;
 638
 639                         } else if (coder->use_eopm) {
 640                                 assert(action == LZMA_FINISH);
 641
 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                 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                 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
 790                                 == LZMA_VLI_VALUE_UNKNOWN)
 791                         return LZMA_HEADER_ERROR;
 792
 793                 // Initialize a raw encoder to work as a Subfilter.
 794                 lzma_options_filter options[2];
 795                 options[0] = coder->options->subfilter_options;
 796                 options[1].id = LZMA_VLI_VALUE_UNKNOWN;
 797
 798                 return_if_error(lzma_raw_encoder_init(
 799                                 &coder->subfilter.subcoder, allocator,
 800                                 options, LZMA_VLI_VALUE_UNKNOWN, false));
 801
 802                 // Encode the Filter Flags field into a buffer. This should
 803                 // never fail since we have already successfully initialized
 804                 // the Subfilter itself. Check it still, and return
 805                 // LZMA_PROG_ERROR instead of whatever the ret would say.
 806                 lzma_ret ret = lzma_filter_flags_size(
 807                                 &coder->subfilter.flags_size, options);
 808                 assert(ret == LZMA_OK);
 809                 if (ret != LZMA_OK)
 810                         return LZMA_PROG_ERROR;
 811
 812                 coder->subfilter.flags = lzma_alloc(
 813                                 coder->subfilter.flags_size, allocator);
 814                 if (coder->subfilter.flags == NULL)
 815                         return LZMA_MEM_ERROR;
 816
 817                 // Now we have a big-enough buffer. Encode the Filter Flags.
 818                 // Like above, this should never fail.
 819                 size_t dummy = 0;
 820                 ret = lzma_filter_flags_encode(coder->subfilter.flags,
 821                                 &dummy, coder->subfilter.flags_size, options);
 822                 assert(ret == LZMA_OK);
 823                 assert(dummy == coder->subfilter.flags_size);
 824                 if (ret != LZMA_OK || dummy != coder->subfilter.flags_size)
 825                         return LZMA_PROG_ERROR;
 826
 827                 // Write a Subblock indicating a new Subfilter.
 828                 write_byte(0x40);
 829
 830                 coder->options->subfilter_mode = LZMA_SUBFILTER_RUN;
 831                 coder->subfilter.mode = SUB_RUN;
 832                 coder->alignment.out_pos += coder->subfilter.flags_size;
 833                 coder->sequence = SEQ_SUBFILTER_FLAGS;
 834
 835                 // It is safe to fall through because SEQ_SUBFILTER_FLAGS
 836                 // uses bufcpy() which doesn't write unless there is output
 837                 // space.
 838         }
 839
 840         // Fall through
 841
 842         case SEQ_SUBFILTER_FLAGS:
 843                 // Copy the Filter Flags to the output stream.
 844                 bufcpy(coder->subfilter.flags, &coder->pos,
 845                                 coder->subfilter.flags_size,
 846                                 out, out_pos, out_size);
 847                 if (coder->pos < coder->subfilter.flags_size)
 848                         return LZMA_OK;
 849
 850                 lzma_free(coder->subfilter.flags, allocator);
 851                 coder->subfilter.flags = NULL;
 852
 853                 coder->pos = 0;
 854                 coder->sequence = SEQ_FILL;
 855                 break;
 856
 857         default:
 858                 return LZMA_PROG_ERROR;
 859         }
 860
 861         return LZMA_OK;
 862 }
 863
 864
 865 static lzma_ret
 866 subblock_encode(lzma_coder *coder, lzma_allocator *allocator,
 867                 const uint8_t *restrict in, size_t *restrict in_pos,
 868                 size_t in_size, uint8_t *restrict out,
 869                 size_t *restrict out_pos, size_t out_size, lzma_action action)
 870 {
 871         if (coder->next.code == NULL)
 872                 return subblock_buffer(coder, allocator, in, in_pos, in_size,
 873                                 out, out_pos, out_size, action);
 874
 875         while (*out_pos < out_size
 876                         && (*in_pos < in_size || action != LZMA_RUN)) {
 877                 if (!coder->next_finished
 878                                 && coder->temp.pos == coder->temp.size) {
 879                         coder->temp.pos = 0;
 880                         coder->temp.size = 0;
 881
 882                         const lzma_ret ret = coder->next.code(coder->next.coder,
 883                                         allocator, in, in_pos, in_size,
 884                                         coder->temp.buffer, &coder->temp.size,
 885                                         LZMA_BUFFER_SIZE, action);
 886                         if (ret == LZMA_STREAM_END) {
 887                                 assert(action != LZMA_RUN);
 888                                 coder->next_finished = true;
 889                         } else if (coder->temp.size == 0 || ret != LZMA_OK) {
 890                                 return ret;
 891                         }
 892                 }
 893
 894                 const lzma_ret ret = subblock_buffer(coder, allocator,
 895                                 coder->temp.buffer, &coder->temp.pos,
 896                                 coder->temp.size, out, out_pos, out_size,
 897                                 coder->next_finished ? LZMA_FINISH : LZMA_RUN);
 898                 if (ret == LZMA_STREAM_END) {
 899                         assert(action != LZMA_RUN);
 900                         assert(coder->next_finished);
 901                         return LZMA_STREAM_END;
 902                 }
 903
 904                 if (ret != LZMA_OK)
 905                         return ret;
 906         }
 907
 908         return LZMA_OK;
 909 }
 910
 911
 912 static void
 913 subblock_encoder_end(lzma_coder *coder, lzma_allocator *allocator)
 914 {
 915         lzma_next_coder_end(&coder->next, allocator);
 916         lzma_next_coder_end(&coder->subfilter.subcoder, allocator);
 917         lzma_free(coder->subblock.data, allocator);
 918         lzma_free(coder->subfilter.flags, 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_coder_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->use_eopm = filters[0].uncompressed_size
 951                         == LZMA_VLI_VALUE_UNKNOWN;
 952         next->coder->pos = 0;
 953
 954         next->coder->alignment.in_pos = 0;
 955         next->coder->alignment.out_pos = 0;
 956         next->coder->subblock.size = 0;
 957         next->coder->subblock.in_pending = 0;
 958         next->coder->rle.count = 0;
 959         next->coder->rle.in_pending = 0;
 960         next->coder->subfilter.mode = SUB_NONE;
 961         next->coder->subfilter.mode_locked = false;
 962
 963         next->coder->temp.pos = 0;
 964         next->coder->temp.size = 0;
 965
 966         // Grab some values from the options structure if it is available.
 967         size_t subblock_size_limit;
 968         if (next->coder->options != NULL) {
 969                 if (next->coder->options->alignment
 970                                         < LZMA_SUBBLOCK_ALIGNMENT_MIN
 971                                 || next->coder->options->alignment
 972                                         > LZMA_SUBBLOCK_ALIGNMENT_MAX) {
 973                         subblock_encoder_end(next->coder, allocator);
 974                         return LZMA_HEADER_ERROR;
 975                 }
 976                 next->coder->alignment.multiple
 977                                 = next->coder->options->alignment;
 978                 next->coder->subfilter.allow
 979                                 = next->coder->options->allow_subfilters;
 980                 subblock_size_limit = next->coder->options->subblock_data_size;
 981         } else {
 982                 next->coder->alignment.multiple
 983                                 = LZMA_SUBBLOCK_ALIGNMENT_DEFAULT;
 984                 next->coder->subfilter.allow = false;
 985                 subblock_size_limit = LZMA_SUBBLOCK_DATA_SIZE_DEFAULT;
 986         }
 987
 988         return_if_error(subblock_data_size(next->coder, allocator,
 989                                 subblock_size_limit));
 990
 991         return lzma_next_filter_init(
 992                         &next->coder->next, allocator, filters + 1);
 993 }