contrib/xz/src/liblzma/common/block_buffer_encoder.c

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