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