src/liblzma/common/block_buffer_encoder.c

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //
   3 /// \file       block_buffer_encoder.c
   4 /// \brief      Single-call .xz Block encoder
   5 //
   6 //  Copyright (C) 2009 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 "block_encoder.h"
  21 #include "filter_encoder.h"
  22 #include "lzma2_encoder.h"
  23 #include "check.h"
  24
  25
  26 /// Estimate the maximum size of the Block Header and Check fields for
  27 /// a Block that uses LZMA2 uncompressed chunks. We could use
  28 /// lzma_block_header_size() but this is simpler.
  29 ///
  30 /// Block Header Size + Block Flags + Compressed Size
  31 /// + Uncompressed Size + Filter Flags for LZMA2 + CRC32 + Check
  32 /// and round up to the next multiple of four to take Header Padding
  33 /// into account.
  34 #define HEADERS_BOUND ((1 + 1 + 2 * LZMA_VLI_BYTES_MAX + 3 + 4 \
  35                 + LZMA_CHECK_SIZE_MAX + 3) & ~3)
  36
  37
  38 static lzma_vli
  39 lzma2_bound(lzma_vli uncompressed_size)
  40 {
  41         // Prevent integer overflow in overhead calculation.
  42         if (uncompressed_size > COMPRESSED_SIZE_MAX)
  43                 return 0;
  44
  45         // Calculate the exact overhead of the LZMA2 headers: Round
  46         // uncompressed_size up to the next multiple of LZMA2_CHUNK_MAX,
  47         // multiply by the size of per-chunk header, and add one byte for
  48         // the end marker.
  49         const lzma_vli overhead = ((uncompressed_size + LZMA2_CHUNK_MAX - 1)
  50                                 / LZMA2_CHUNK_MAX)
  51                         * LZMA2_HEADER_UNCOMPRESSED + 1;
  52
  53         // Catch the possible integer overflow.
  54         if (COMPRESSED_SIZE_MAX - overhead < uncompressed_size)
  55                 return 0;
  56
  57         return uncompressed_size + overhead;
  58 }
  59
  60
  61 extern LZMA_API size_t
  62 lzma_block_buffer_bound(size_t uncompressed_size)
  63 {
  64         // For now, if the data doesn't compress, we always use uncompressed
  65         // chunks of LZMA2. In future we may use Subblock filter too, but
  66         // but for simplicity we probably will still use the same bound
  67         // calculation even though Subblock filter would have slightly less
  68         // overhead.
  69         lzma_vli lzma2_size = lzma2_bound(uncompressed_size);
  70         if (lzma2_size == 0)
  71                 return 0;
  72
  73         // Take Block Padding into account.
  74         lzma2_size = (lzma2_size + 3) & ~LZMA_VLI_C(3);
  75
  76 #if SIZE_MAX < LZMA_VLI_MAX
  77         // Catch the possible integer overflow on 32-bit systems. There's no
  78         // overflow on 64-bit systems, because lzma2_bound() already takes
  79         // into account the size of the headers in the Block.
  80         if (SIZE_MAX - HEADERS_BOUND < lzma2_size)
  81                 return 0;
  82 #endif
  83
  84         return HEADERS_BOUND + lzma2_size;
  85 }
  86
  87
  88 static lzma_ret
  89 block_encode_uncompressed(lzma_block *block, const uint8_t *in, size_t in_size,
  90                 uint8_t *out, size_t *out_pos, size_t out_size)
  91 {
  92         // TODO: Figure out if the last filter is LZMA2 or Subblock and use
  93         // that filter to encode the uncompressed chunks.
  94
  95         // Use LZMA2 uncompressed chunks. We wouldn't need a dictionary at
  96         // all, but LZMA2 always requires a dictionary, so use the minimum
  97         // value to minimize memory usage of the decoder.
  98         lzma_options_lzma lzma2 = {
  99                 .dict_size = LZMA_DICT_SIZE_MIN,
 100         };
 101
 102         lzma_filter filters[2];
 103         filters[0].id = LZMA_FILTER_LZMA2;
 104         filters[0].options = &lzma2;
 105         filters[1].id = LZMA_VLI_UNKNOWN;
 106
 107         // Set the above filter options to *block temporarily so that we can
 108         // encode the Block Header.
 109         lzma_filter *filters_orig = block->filters;
 110         block->filters = filters;
 111
 112         if (lzma_block_header_size(block) != LZMA_OK) {
 113                 block->filters = filters_orig;
 114                 return LZMA_PROG_ERROR;
 115         }
 116
 117         // Check that there's enough output space. The caller has already
 118         // set block->compressed_size to what lzma2_bound() has returned,
 119         // so we can reuse that value. We know that compressed_size is a
 120         // known valid VLI and header_size is a small value so their sum
 121         // will never overflow.
 122         assert(block->compressed_size == lzma2_bound(in_size));
 123         if (out_size - *out_pos
 124                         < block->header_size + block->compressed_size) {
 125                 block->filters = filters_orig;
 126                 return LZMA_BUF_ERROR;
 127         }
 128
 129         if (lzma_block_header_encode(block, out + *out_pos) != LZMA_OK) {
 130                 block->filters = filters_orig;
 131                 return LZMA_PROG_ERROR;
 132         }
 133
 134         block->filters = filters_orig;
 135         *out_pos += block->header_size;
 136
 137         // Encode the data using LZMA2 uncompressed chunks.
 138         size_t in_pos = 0;
 139         uint8_t control = 0x01; // Dictionary reset
 140
 141         while (in_pos < in_size) {
 142                 // Control byte: Indicate uncompressed chunk, of which
 143                 // the first resets the dictionary.
 144                 out[(*out_pos)++] = control;
 145                 control = 0x02; // No dictionary reset
 146
 147                 // Size of the uncompressed chunk
 148                 const size_t copy_size
 149                                 = MIN(in_size - in_pos, LZMA2_CHUNK_MAX);
 150                 out[(*out_pos)++] = (copy_size - 1) >> 8;
 151                 out[(*out_pos)++] = (copy_size - 1) & 0xFF;
 152
 153                 // The actual data
 154                 assert(*out_pos + copy_size <= out_size);
 155                 memcpy(out + *out_pos, in + in_pos, copy_size);
 156
 157                 in_pos += copy_size;
 158                 *out_pos += copy_size;
 159         }
 160
 161         // End marker
 162         out[(*out_pos)++] = 0x00;
 163         assert(*out_pos <= out_size);
 164
 165         return LZMA_OK;
 166 }
 167
 168
 169 static lzma_ret
 170 block_encode_normal(lzma_block *block, lzma_allocator *allocator,
 171                 const uint8_t *in, size_t in_size,
 172                 uint8_t *out, size_t *out_pos, size_t out_size)
 173 {
 174         // Find out the size of the Block Header.
 175         block->compressed_size = lzma2_bound(in_size);
 176         if (block->compressed_size == 0)
 177                 return LZMA_DATA_ERROR;
 178
 179         block->uncompressed_size = in_size;
 180         return_if_error(lzma_block_header_size(block));
 181
 182         // Reserve space for the Block Header and skip it for now.
 183         if (out_size - *out_pos <= block->header_size)
 184                 return LZMA_BUF_ERROR;
 185
 186         const size_t out_start = *out_pos;
 187         *out_pos += block->header_size;
 188
 189         // Limit out_size so that we stop encoding if the output would grow
 190         // bigger than what uncompressed Block would be.
 191         if (out_size - *out_pos > block->compressed_size)
 192                 out_size = *out_pos + block->compressed_size;
 193
 194         // TODO: In many common cases this could be optimized to use
 195         // significantly less memory.
 196         lzma_next_coder raw_encoder = LZMA_NEXT_CODER_INIT;
 197         lzma_ret ret = lzma_raw_encoder_init(
 198                         &raw_encoder, allocator, block->filters);
 199
 200         if (ret == LZMA_OK) {
 201                 size_t in_pos = 0;
 202                 ret = raw_encoder.code(raw_encoder.coder, allocator,
 203                                 in, &in_pos, in_size, out, out_pos, out_size,
 204                                 LZMA_FINISH);
 205         }
 206
 207         // NOTE: This needs to be run even if lzma_raw_encoder_init() failed.
 208         lzma_next_end(&raw_encoder, allocator);
 209
 210         if (ret == LZMA_STREAM_END) {
 211                 // Compression was successful. Write the Block Header.
 212                 block->compressed_size
 213                                 = *out_pos - (out_start + block->header_size);
 214                 ret = lzma_block_header_encode(block, out + out_start);
 215                 if (ret != LZMA_OK)
 216                         ret = LZMA_PROG_ERROR;
 217
 218         } else if (ret == LZMA_OK) {
 219                 // Output buffer became full.
 220                 ret = LZMA_BUF_ERROR;
 221         }
 222
 223         // Reset *out_pos if something went wrong.
 224         if (ret != LZMA_OK)
 225                 *out_pos = out_start;
 226
 227         return ret;
 228 }
 229
 230
 231 extern LZMA_API lzma_ret
 232 lzma_block_buffer_encode(lzma_block *block, lzma_allocator *allocator,
 233                 const uint8_t *in, size_t in_size,
 234                 uint8_t *out, size_t *out_pos, size_t out_size)
 235 {
 236         // Sanity checks
 237         if (block == NULL || block->filters == NULL
 238                         || (in == NULL && in_size != 0) || out == NULL
 239                         || out_pos == NULL || *out_pos > out_size)
 240                 return LZMA_PROG_ERROR;
 241
 242         // Check the version field.
 243         if (block->version != 0)
 244                 return LZMA_OPTIONS_ERROR;
 245
 246         // Size of a Block has to be a multiple of four, so limit the size
 247         // here already. This way we don't need to check it again when adding
 248         // Block Padding.
 249         out_size -= (out_size - *out_pos) & 3;
 250
 251         // Get the size of the Check field.
 252         const size_t check_size = lzma_check_size(block->check);
 253         if (check_size == UINT32_MAX)
 254                 return LZMA_PROG_ERROR;
 255
 256         // Reserve space for the Check field.
 257         if (out_size - *out_pos <= check_size)
 258                 return LZMA_BUF_ERROR;
 259
 260         out_size -= check_size;
 261
 262         // Do the actual compression.
 263         const lzma_ret ret = block_encode_normal(block, allocator,
 264                         in, in_size, out, out_pos, out_size);
 265         if (ret != LZMA_OK) {
 266                 // If the error was something else than output buffer
 267                 // becoming full, return the error now.
 268                 if (ret != LZMA_BUF_ERROR)
 269                         return ret;
 270
 271                 // The data was uncompressible (at least with the options
 272                 // given to us) or the output buffer was too small. Use the
 273                 // uncompressed chunks of LZMA2 to wrap the data into a valid
 274                 // Block. If we haven't been given enough output space, even
 275                 // this may fail.
 276                 return_if_error(block_encode_uncompressed(block, in, in_size,
 277                                 out, out_pos, out_size));
 278         }
 279
 280         assert(*out_pos <= out_size);
 281
 282         // Block Padding. No buffer overflow here, because we already adjusted
 283         // out_size so that (out_size - out_start) is a multiple of four.
 284         // Thus, if the buffer is full, the loop body can never run.
 285         for (size_t i = (size_t)(block->compressed_size); i & 3; ++i) {
 286                 assert(*out_pos < out_size);
 287                 out[(*out_pos)++] = 0x00;
 288         }
 289
 290         // If there's no Check field, we are done now.
 291         if (check_size > 0) {
 292                 // Calculate the integrity check. We reserved space for
 293                 // the Check field earlier so we don't need to check for
 294                 // available output space here.
 295                 lzma_check_state check;
 296                 lzma_check_init(&check, block->check);
 297                 lzma_check_update(&check, block->check, in, in_size);
 298                 lzma_check_finish(&check, block->check);
 299
 300                 memcpy(out + *out_pos, check.buffer.u8, check_size);
 301                 *out_pos += check_size;
 302         }
 303
 304         return LZMA_OK;
 305 }