Add an unpatched version of xz, XZ Utils, to /trunk/deps/third_party

xz/src/liblzma/common/block_buffer_encoder.c

+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       block_buffer_encoder.c
+/// \brief      Single-call .xz Block encoder
+//
+//  Author:     Lasse Collin
+//
+//  This file has been put into the public domain.
+//  You can do whatever you want with this file.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include "block_encoder.h"
+#include "filter_encoder.h"
+#include "lzma2_encoder.h"
+#include "check.h"
+
+
+/// Estimate the maximum size of the Block Header and Check fields for
+/// a Block that uses LZMA2 uncompressed chunks. We could use
+/// lzma_block_header_size() but this is simpler.
+///
+/// Block Header Size + Block Flags + Compressed Size
+/// + Uncompressed Size + Filter Flags for LZMA2 + CRC32 + Check
+/// and round up to the next multiple of four to take Header Padding
+/// into account.
+#define HEADERS_BOUND ((1 + 1 + 2 * LZMA_VLI_BYTES_MAX + 3 + 4 \
+                + LZMA_CHECK_SIZE_MAX + 3) & ~3)
+
+
+static lzma_vli
+lzma2_bound(lzma_vli uncompressed_size)
+{
+        // Prevent integer overflow in overhead calculation.
+        if (uncompressed_size > COMPRESSED_SIZE_MAX)
+                return 0;
+
+        // Calculate the exact overhead of the LZMA2 headers: Round
+        // uncompressed_size up to the next multiple of LZMA2_CHUNK_MAX,
+        // multiply by the size of per-chunk header, and add one byte for
+        // the end marker.
+        const lzma_vli overhead = ((uncompressed_size + LZMA2_CHUNK_MAX - 1)
+                                / LZMA2_CHUNK_MAX)
+                        * LZMA2_HEADER_UNCOMPRESSED + 1;
+
+        // Catch the possible integer overflow.
+        if (COMPRESSED_SIZE_MAX - overhead < uncompressed_size)
+                return 0;
+
+        return uncompressed_size + overhead;
+}
+
+
+extern LZMA_API(size_t)
+lzma_block_buffer_bound(size_t uncompressed_size)
+{
+        // For now, if the data doesn't compress, we always use uncompressed
+        // chunks of LZMA2. In future we may use Subblock filter too, but
+        // but for simplicity we probably will still use the same bound
+        // calculation even though Subblock filter would have slightly less
+        // overhead.
+        lzma_vli lzma2_size = lzma2_bound(uncompressed_size);
+        if (lzma2_size == 0)
+                return 0;
+
+        // Take Block Padding into account.
+        lzma2_size = (lzma2_size + 3) & ~LZMA_VLI_C(3);
+
+#if SIZE_MAX < LZMA_VLI_MAX
+        // Catch the possible integer overflow on 32-bit systems. There's no
+        // overflow on 64-bit systems, because lzma2_bound() already takes
+        // into account the size of the headers in the Block.
+        if (SIZE_MAX - HEADERS_BOUND < lzma2_size)
+                return 0;
+#endif
+
+        return HEADERS_BOUND + lzma2_size;
+}
+
+
+static lzma_ret
+block_encode_uncompressed(lzma_block *block, const uint8_t *in, size_t in_size,
+                uint8_t *out, size_t *out_pos, size_t out_size)
+{
+        // TODO: Figure out if the last filter is LZMA2 or Subblock and use
+        // that filter to encode the uncompressed chunks.
+
+        // Use LZMA2 uncompressed chunks. We wouldn't need a dictionary at
+        // all, but LZMA2 always requires a dictionary, so use the minimum
+        // value to minimize memory usage of the decoder.
+        lzma_options_lzma lzma2 = {
+                .dict_size = LZMA_DICT_SIZE_MIN,
+        };
+
+        lzma_filter filters[2];
+        filters[0].id = LZMA_FILTER_LZMA2;
+        filters[0].options = &lzma2;
+        filters[1].id = LZMA_VLI_UNKNOWN;
+
+        // Set the above filter options to *block temporarily so that we can
+        // encode the Block Header.
+        lzma_filter *filters_orig = block->filters;
+        block->filters = filters;
+
+        if (lzma_block_header_size(block) != LZMA_OK) {
+                block->filters = filters_orig;
+                return LZMA_PROG_ERROR;
+        }
+
+        // Check that there's enough output space. The caller has already
+        // set block->compressed_size to what lzma2_bound() has returned,
+        // so we can reuse that value. We know that compressed_size is a
+        // known valid VLI and header_size is a small value so their sum
+        // will never overflow.
+        assert(block->compressed_size == lzma2_bound(in_size));
+        if (out_size - *out_pos
+                        < block->header_size + block->compressed_size) {
+                block->filters = filters_orig;
+                return LZMA_BUF_ERROR;
+        }
+
+        if (lzma_block_header_encode(block, out + *out_pos) != LZMA_OK) {
+                block->filters = filters_orig;
+                return LZMA_PROG_ERROR;
+        }
+
+        block->filters = filters_orig;
+        *out_pos += block->header_size;
+
+        // Encode the data using LZMA2 uncompressed chunks.
+        size_t in_pos = 0;
+        uint8_t control = 0x01; // Dictionary reset
+
+        while (in_pos < in_size) {
+                // Control byte: Indicate uncompressed chunk, of which
+                // the first resets the dictionary.
+                out[(*out_pos)++] = control;
+                control = 0x02; // No dictionary reset
+
+                // Size of the uncompressed chunk
+                const size_t copy_size
+                                = my_min(in_size - in_pos, LZMA2_CHUNK_MAX);
+                out[(*out_pos)++] = (copy_size - 1) >> 8;
+                out[(*out_pos)++] = (copy_size - 1) & 0xFF;
+
+                // The actual data
+                assert(*out_pos + copy_size <= out_size);
+                memcpy(out + *out_pos, in + in_pos, copy_size);
+
+                in_pos += copy_size;
+                *out_pos += copy_size;
+        }
+
+        // End marker
+        out[(*out_pos)++] = 0x00;
+        assert(*out_pos <= out_size);
+
+        return LZMA_OK;
+}
+
+
+static lzma_ret
+block_encode_normal(lzma_block *block, lzma_allocator *allocator,
+                const uint8_t *in, size_t in_size,
+                uint8_t *out, size_t *out_pos, size_t out_size)
+{
+        // Find out the size of the Block Header.
+        block->compressed_size = lzma2_bound(in_size);
+        if (block->compressed_size == 0)
+                return LZMA_DATA_ERROR;
+
+        block->uncompressed_size = in_size;
+        return_if_error(lzma_block_header_size(block));
+
+        // Reserve space for the Block Header and skip it for now.
+        if (out_size - *out_pos <= block->header_size)
+                return LZMA_BUF_ERROR;
+
+        const size_t out_start = *out_pos;
+        *out_pos += block->header_size;
+
+        // Limit out_size so that we stop encoding if the output would grow
+        // bigger than what uncompressed Block would be.
+        if (out_size - *out_pos > block->compressed_size)
+                out_size = *out_pos + block->compressed_size;
+
+        // TODO: In many common cases this could be optimized to use
+        // significantly less memory.
+        lzma_next_coder raw_encoder = LZMA_NEXT_CODER_INIT;
+        lzma_ret ret = lzma_raw_encoder_init(
+                        &raw_encoder, allocator, block->filters);
+
+        if (ret == LZMA_OK) {
+                size_t in_pos = 0;
+                ret = raw_encoder.code(raw_encoder.coder, allocator,
+                                in, &in_pos, in_size, out, out_pos, out_size,
+                                LZMA_FINISH);
+        }
+
+        // NOTE: This needs to be run even if lzma_raw_encoder_init() failed.
+        lzma_next_end(&raw_encoder, allocator);
+
+        if (ret == LZMA_STREAM_END) {
+                // Compression was successful. Write the Block Header.
+                block->compressed_size
+                                = *out_pos - (out_start + block->header_size);
+                ret = lzma_block_header_encode(block, out + out_start);
+                if (ret != LZMA_OK)
+                        ret = LZMA_PROG_ERROR;
+
+        } else if (ret == LZMA_OK) {
+                // Output buffer became full.
+                ret = LZMA_BUF_ERROR;
+        }
+
+        // Reset *out_pos if something went wrong.
+        if (ret != LZMA_OK)
+                *out_pos = out_start;
+
+        return ret;
+}
+
+
+extern LZMA_API(lzma_ret)
+lzma_block_buffer_encode(lzma_block *block, lzma_allocator *allocator,
+                const uint8_t *in, size_t in_size,
+                uint8_t *out, size_t *out_pos, size_t out_size)
+{
+        // Sanity checks
+        if (block == NULL || block->filters == NULL
+                        || (in == NULL && in_size != 0) || out == NULL
+                        || out_pos == NULL || *out_pos > out_size)
+                return LZMA_PROG_ERROR;
+
+        // Check the version field.
+        if (block->version != 0)
+                return LZMA_OPTIONS_ERROR;
+
+        // Size of a Block has to be a multiple of four, so limit the size
+        // here already. This way we don't need to check it again when adding
+        // Block Padding.
+        out_size -= (out_size - *out_pos) & 3;
+
+        // Get the size of the Check field.
+        const size_t check_size = lzma_check_size(block->check);
+        if (check_size == UINT32_MAX)
+                return LZMA_PROG_ERROR;
+
+        // Reserve space for the Check field.
+        if (out_size - *out_pos <= check_size)
+                return LZMA_BUF_ERROR;
+
+        out_size -= check_size;
+
+        // Do the actual compression.
+        const lzma_ret ret = block_encode_normal(block, allocator,
+                        in, in_size, out, out_pos, out_size);
+        if (ret != LZMA_OK) {
+                // If the error was something else than output buffer
+                // becoming full, return the error now.
+                if (ret != LZMA_BUF_ERROR)
+                        return ret;
+
+                // The data was uncompressible (at least with the options
+                // given to us) or the output buffer was too small. Use the
+                // uncompressed chunks of LZMA2 to wrap the data into a valid
+                // Block. If we haven't been given enough output space, even
+                // this may fail.
+                return_if_error(block_encode_uncompressed(block, in, in_size,
+                                out, out_pos, out_size));
+        }
+
+        assert(*out_pos <= out_size);
+
+        // Block Padding. No buffer overflow here, because we already adjusted
+        // out_size so that (out_size - out_start) is a multiple of four.
+        // Thus, if the buffer is full, the loop body can never run.
+        for (size_t i = (size_t)(block->compressed_size); i & 3; ++i) {
+                assert(*out_pos < out_size);
+                out[(*out_pos)++] = 0x00;
+        }
+
+        // If there's no Check field, we are done now.
+        if (check_size > 0) {
+                // Calculate the integrity check. We reserved space for
+                // the Check field earlier so we don't need to check for
+                // available output space here.
+                lzma_check_state check;
+                lzma_check_init(&check, block->check);
+                lzma_check_update(&check, block->check, in, in_size);
+                lzma_check_finish(&check, block->check);
+
+                memcpy(block->raw_check, check.buffer.u8, check_size);
+                memcpy(out + *out_pos, check.buffer.u8, check_size);
+                *out_pos += check_size;
+        }
+
+        return LZMA_OK;
+}