Put the interesting parts of XZ Utils into the public domain.

[icculus/xz.git] / src / liblzma / lz / lz_encoder.c

///////////////////////////////////////////////////////////////////////////////
//
/// \file       lz_encoder.c
/// \brief      LZ in window
///
//  Authors:    Igor Pavlov
//              Lasse Collin
//
//  This file has been put into the public domain.
//  You can do whatever you want with this file.
//
///////////////////////////////////////////////////////////////////////////////

#include "lz_encoder.h"
#include "lz_encoder_hash.h"
#include "check.h"


struct lzma_coder_s {
        /// LZ-based encoder e.g. LZMA
        lzma_lz_encoder lz;

        /// History buffer and match finder
        lzma_mf mf;

        /// Next coder in the chain
        lzma_next_coder next;
};


/// \brief      Moves the data in the input window to free space for new data
///
/// mf->buffer is a sliding input window, which keeps mf->keep_size_before
/// bytes of input history available all the time. Now and then we need to
/// "slide" the buffer to make space for the new data to the end of the
/// buffer. At the same time, data older than keep_size_before is dropped.
///
static void
move_window(lzma_mf *mf)
{
        // Align the move to a multiple of 16 bytes. Some LZ-based encoders
        // like LZMA use the lowest bits of mf->read_pos to know the
        // alignment of the uncompressed data. We also get better speed
        // for memmove() with aligned buffers.
        assert(mf->read_pos > mf->keep_size_before);
        const uint32_t move_offset
                = (mf->read_pos - mf->keep_size_before) & ~UINT32_C(15);

        assert(mf->write_pos > move_offset);
        const size_t move_size = mf->write_pos - move_offset;

        assert(move_offset + move_size <= mf->size);

        memmove(mf->buffer, mf->buffer + move_offset, move_size);

        mf->offset += move_offset;
        mf->read_pos -= move_offset;
        mf->read_limit -= move_offset;
        mf->write_pos -= move_offset;

        return;
}


/// \brief      Tries to fill the input window (mf->buffer)
///
/// If we are the last encoder in the chain, our input data is in in[].
/// Otherwise we call the next filter in the chain to process in[] and
/// write its output to mf->buffer.
///
/// This function must not be called once it has returned LZMA_STREAM_END.
///
static lzma_ret
fill_window(lzma_coder *coder, lzma_allocator *allocator, const uint8_t *in,
                size_t *in_pos, size_t in_size, lzma_action action)
{
        assert(coder->mf.read_pos <= coder->mf.write_pos);

        // Move the sliding window if needed.
        if (coder->mf.read_pos >= coder->mf.size - coder->mf.keep_size_after)
                move_window(&coder->mf);

        // Maybe this is ugly, but lzma_mf uses uint32_t for most things
        // (which I find cleanest), but we need size_t here when filling
        // the history window.
        size_t write_pos = coder->mf.write_pos;
        size_t in_used;
        lzma_ret ret;
        if (coder->next.code == NULL) {
                // Not using a filter, simply memcpy() as much as possible.
                in_used = lzma_bufcpy(in, in_pos, in_size, coder->mf.buffer,
                                &write_pos, coder->mf.size);

                ret = action != LZMA_RUN && *in_pos == in_size
                                ? LZMA_STREAM_END : LZMA_OK;

        } else {
                const size_t in_start = *in_pos;
                ret = coder->next.code(coder->next.coder, allocator,
                                in, in_pos, in_size,
                                coder->mf.buffer, &write_pos,
                                coder->mf.size, action);
                in_used = *in_pos - in_start;
        }

        coder->mf.write_pos = write_pos;

        // If end of stream has been reached or flushing completed, we allow
        // the encoder to process all the input (that is, read_pos is allowed
        // to reach write_pos). Otherwise we keep keep_size_after bytes
        // available as prebuffer.
        if (ret == LZMA_STREAM_END) {
                assert(*in_pos == in_size);
                ret = LZMA_OK;
                coder->mf.action = action;
                coder->mf.read_limit = coder->mf.write_pos;

        } else if (coder->mf.write_pos > coder->mf.keep_size_after) {
                // This needs to be done conditionally, because if we got
                // only little new input, there may be too little input
                // to do any encoding yet.
                coder->mf.read_limit = coder->mf.write_pos
                                - coder->mf.keep_size_after;
        }

        // Restart the match finder after finished LZMA_SYNC_FLUSH.
        if (coder->mf.pending > 0
                        && coder->mf.read_pos < coder->mf.read_limit) {
                // Match finder may update coder->pending and expects it to
                // start from zero, so use a temporary variable.
                const size_t pending = coder->mf.pending;
                coder->mf.pending = 0;

                // Rewind read_pos so that the match finder can hash
                // the pending bytes.
                assert(coder->mf.read_pos >= pending);
                coder->mf.read_pos -= pending;

                // Call the skip function directly instead of using
                // mf_skip(), since we don't want to touch mf->read_ahead.
                coder->mf.skip(&coder->mf, pending);
        }

        return ret;
}


static lzma_ret
lz_encode(lzma_coder *coder, lzma_allocator *allocator,
                const uint8_t *restrict in, size_t *restrict in_pos,
                size_t in_size,
                uint8_t *restrict out, size_t *restrict out_pos,
                size_t out_size, lzma_action action)
{
        while (*out_pos < out_size
                        && (*in_pos < in_size || action != LZMA_RUN)) {
                // Read more data to coder->mf.buffer if needed.
                if (coder->mf.action == LZMA_RUN && coder->mf.read_pos
                                >= coder->mf.read_limit)
                        return_if_error(fill_window(coder, allocator,
                                        in, in_pos, in_size, action));

                // Encode
                const lzma_ret ret = coder->lz.code(coder->lz.coder,
                                &coder->mf, out, out_pos, out_size);
                if (ret != LZMA_OK) {
                        // Setting this to LZMA_RUN for cases when we are
                        // flushing. It doesn't matter when finishing or if
                        // an error occurred.
                        coder->mf.action = LZMA_RUN;
                        return ret;
                }
        }

        return LZMA_OK;
}


static bool
lz_encoder_prepare(lzma_mf *mf, lzma_allocator *allocator,
                const lzma_lz_options *lz_options)
{
        // For now, the dictionary size is limited to 1.5 GiB. This may grow
        // in the future if needed, but it needs a little more work than just
        // changing this check.
        if (lz_options->dict_size < LZMA_DICT_SIZE_MIN
                        || lz_options->dict_size
                                > (UINT32_C(1) << 30) + (UINT32_C(1) << 29)
                        || lz_options->nice_len > lz_options->match_len_max)
                return true;

        mf->keep_size_before = lz_options->before_size + lz_options->dict_size;

        mf->keep_size_after = lz_options->after_size
                        + lz_options->match_len_max;

        // To avoid constant memmove()s, allocate some extra space. Since
        // memmove()s become more expensive when the size of the buffer
        // increases, we reserve more space when a large dictionary is
        // used to make the memmove() calls rarer.
        //
        // This works with dictionaries up to about 3 GiB. If bigger
        // dictionary is wanted, some extra work is needed:
        //   - Several variables in lzma_mf have to be changed from uint32_t
        //     to size_t.
        //   - Memory usage calculation needs something too, e.g. use uint64_t
        //     for mf->size.
        uint32_t reserve = lz_options->dict_size / 2;
        if (reserve > (UINT32_C(1) << 30))
                reserve /= 2;

        reserve += (lz_options->before_size + lz_options->match_len_max
                        + lz_options->after_size) / 2 + (UINT32_C(1) << 19);

        const uint32_t old_size = mf->size;
        mf->size = mf->keep_size_before + reserve + mf->keep_size_after;

        // Deallocate the old history buffer if it exists but has different
        // size than what is needed now.
        if (mf->buffer != NULL && old_size != mf->size) {
                lzma_free(mf->buffer, allocator);
                mf->buffer = NULL;
        }

        // Match finder options
        mf->match_len_max = lz_options->match_len_max;
        mf->nice_len = lz_options->nice_len;

        // cyclic_size has to stay smaller than 2 Gi. Note that this doesn't
        // mean limitting dictionary size to less than 2 GiB. With a match
        // finder that uses multibyte resolution (hashes start at e.g. every
        // fourth byte), cyclic_size would stay below 2 Gi even when
        // dictionary size is greater than 2 GiB.
        //
        // It would be possible to allow cyclic_size >= 2 Gi, but then we
        // would need to be careful to use 64-bit types in various places
        // (size_t could do since we would need bigger than 32-bit address
        // space anyway). It would also require either zeroing a multigigabyte
        // buffer at initialization (waste of time and RAM) or allow
        // normalization in lz_encoder_mf.c to access uninitialized
        // memory to keep the code simpler. The current way is simple and
        // still allows pretty big dictionaries, so I don't expect these
        // limits to change.
        mf->cyclic_size = lz_options->dict_size + 1;

        // Validate the match finder ID and setup the function pointers.
        switch (lz_options->match_finder) {
#ifdef HAVE_MF_HC3
        case LZMA_MF_HC3:
                mf->find = &lzma_mf_hc3_find;
                mf->skip = &lzma_mf_hc3_skip;
                break;
#endif
#ifdef HAVE_MF_HC4
        case LZMA_MF_HC4:
                mf->find = &lzma_mf_hc4_find;
                mf->skip = &lzma_mf_hc4_skip;
                break;
#endif
#ifdef HAVE_MF_BT2
        case LZMA_MF_BT2:
                mf->find = &lzma_mf_bt2_find;
                mf->skip = &lzma_mf_bt2_skip;
                break;
#endif
#ifdef HAVE_MF_BT3
        case LZMA_MF_BT3:
                mf->find = &lzma_mf_bt3_find;
                mf->skip = &lzma_mf_bt3_skip;
                break;
#endif
#ifdef HAVE_MF_BT4
        case LZMA_MF_BT4:
                mf->find = &lzma_mf_bt4_find;
                mf->skip = &lzma_mf_bt4_skip;
                break;
#endif

        default:
                return true;
        }

        // Calculate the sizes of mf->hash and mf->son and check that
        // nice_len is big enough for the selected match finder.
        const uint32_t hash_bytes = lz_options->match_finder & 0x0F;
        if (hash_bytes > mf->nice_len)
                return true;

        const bool is_bt = (lz_options->match_finder & 0x10) != 0;
        uint32_t hs;

        if (hash_bytes == 2) {
                hs = 0xFFFF;
        } else {
                // Round dictionary size up to the next 2^n - 1 so it can
                // be used as a hash mask.
                hs = lz_options->dict_size - 1;
                hs |= hs >> 1;
                hs |= hs >> 2;
                hs |= hs >> 4;
                hs |= hs >> 8;
                hs >>= 1;
                hs |= 0xFFFF;

                if (hs > (UINT32_C(1) << 24)) {
                        if (hash_bytes == 3)
                                hs = (UINT32_C(1) << 24) - 1;
                        else
                                hs >>= 1;
                }
        }

        mf->hash_mask = hs;

        ++hs;
        if (hash_bytes > 2)
                hs += HASH_2_SIZE;
        if (hash_bytes > 3)
                hs += HASH_3_SIZE;
/*
        No match finder uses this at the moment.
        if (mf->hash_bytes > 4)
                hs += HASH_4_SIZE;
*/

        // If the above code calculating hs is modified, make sure that
        // this assertion stays valid (UINT32_MAX / 5 is not strictly the
        // exact limit). If it doesn't, you need to calculate that
        // hash_size_sum + sons_count cannot overflow.
        assert(hs < UINT32_MAX / 5);

        const uint32_t old_count = mf->hash_size_sum + mf->sons_count;
        mf->hash_size_sum = hs;
        mf->sons_count = mf->cyclic_size;
        if (is_bt)
                mf->sons_count *= 2;

        const uint32_t new_count = mf->hash_size_sum + mf->sons_count;

        // Deallocate the old hash array if it exists and has different size
        // than what is needed now.
        if (mf->hash != NULL && old_count != new_count) {
                lzma_free(mf->hash, allocator);
                mf->hash = NULL;
        }

        // Maximum number of match finder cycles
        mf->depth = lz_options->depth;
        if (mf->depth == 0) {
                mf->depth = 16 + (mf->nice_len / 2);
                if (!is_bt)
                        mf->depth /= 2;
        }

        return false;
}


static bool
lz_encoder_init(lzma_mf *mf, lzma_allocator *allocator,
                const lzma_lz_options *lz_options)
{
        // Allocate the history buffer.
        if (mf->buffer == NULL) {
                mf->buffer = lzma_alloc(mf->size, allocator);
                if (mf->buffer == NULL)
                        return true;
        }

        // Use cyclic_size as initial mf->offset. This allows
        // avoiding a few branches in the match finders. The downside is
        // that match finder needs to be normalized more often, which may
        // hurt performance with huge dictionaries.
        mf->offset = mf->cyclic_size;
        mf->read_pos = 0;
        mf->read_ahead = 0;
        mf->read_limit = 0;
        mf->write_pos = 0;
        mf->pending = 0;

        // Allocate match finder's hash array.
        const size_t alloc_count = mf->hash_size_sum + mf->sons_count;

#if UINT32_MAX >= SIZE_MAX / 4
        // Check for integer overflow. (Huge dictionaries are not
        // possible on 32-bit CPU.)
        if (alloc_count > SIZE_MAX / sizeof(uint32_t))
                return true;
#endif

        if (mf->hash == NULL) {
                mf->hash = lzma_alloc(alloc_count * sizeof(uint32_t),
                                allocator);
                if (mf->hash == NULL)
                        return true;
        }

        mf->son = mf->hash + mf->hash_size_sum;
        mf->cyclic_pos = 0;

        // Initialize the hash table. Since EMPTY_HASH_VALUE is zero, we
        // can use memset().
/*
        for (uint32_t i = 0; i < hash_size_sum; ++i)
                mf->hash[i] = EMPTY_HASH_VALUE;
*/
        memzero(mf->hash, (size_t)(mf->hash_size_sum) * sizeof(uint32_t));

        // We don't need to initialize mf->son, but not doing that will
        // make Valgrind complain in normalization (see normalize() in
        // lz_encoder_mf.c).
        //
        // Skipping this initialization is *very* good when big dictionary is
        // used but only small amount of data gets actually compressed: most
        // of the mf->hash won't get actually allocated by the kernel, so
        // we avoid wasting RAM and improve initialization speed a lot.
        //memzero(mf->son, (size_t)(mf->sons_count) * sizeof(uint32_t));

        // Handle preset dictionary.
        if (lz_options->preset_dict != NULL
                        && lz_options->preset_dict_size > 0) {
                // If the preset dictionary is bigger than the actual
                // dictionary, use only the tail.
                mf->write_pos = MIN(lz_options->preset_dict_size, mf->size);
                memcpy(mf->buffer, lz_options->preset_dict
                                + lz_options->preset_dict_size - mf->write_pos,
                                mf->write_pos);
                mf->action = LZMA_SYNC_FLUSH;
                mf->skip(mf, mf->write_pos);
        }

        mf->action = LZMA_RUN;

        return false;
}


extern uint64_t
lzma_lz_encoder_memusage(const lzma_lz_options *lz_options)
{
        // Old buffers must not exist when calling lz_encoder_prepare().
        lzma_mf mf = {
                .buffer = NULL,
                .hash = NULL,
        };

        // Setup the size information into mf.
        if (lz_encoder_prepare(&mf, NULL, lz_options))
                return UINT64_MAX;

        // Calculate the memory usage.
        return (uint64_t)(mf.hash_size_sum + mf.sons_count)
                                * sizeof(uint32_t)
                        + (uint64_t)(mf.size) + sizeof(lzma_coder);
}


static void
lz_encoder_end(lzma_coder *coder, lzma_allocator *allocator)
{
        lzma_next_end(&coder->next, allocator);

        lzma_free(coder->mf.hash, allocator);
        lzma_free(coder->mf.buffer, allocator);

        if (coder->lz.end != NULL)
                coder->lz.end(coder->lz.coder, allocator);
        else
                lzma_free(coder->lz.coder, allocator);

        lzma_free(coder, allocator);
        return;
}


extern lzma_ret
lzma_lz_encoder_init(lzma_next_coder *next, lzma_allocator *allocator,
                const lzma_filter_info *filters,
                lzma_ret (*lz_init)(lzma_lz_encoder *lz,
                        lzma_allocator *allocator, const void *options,
                        lzma_lz_options *lz_options))
{
#ifdef HAVE_SMALL
        // We need that the CRC32 table has been initialized.
        lzma_crc32_init();
#endif

        // Allocate and initialize the base data structure.
        if (next->coder == NULL) {
                next->coder = lzma_alloc(sizeof(lzma_coder), allocator);
                if (next->coder == NULL)
                        return LZMA_MEM_ERROR;

                next->code = &lz_encode;
                next->end = &lz_encoder_end;

                next->coder->lz.coder = NULL;
                next->coder->lz.code = NULL;
                next->coder->lz.end = NULL;

                next->coder->mf.buffer = NULL;
                next->coder->mf.hash = NULL;

                next->coder->next = LZMA_NEXT_CODER_INIT;
        }

        // Initialize the LZ-based encoder.
        lzma_lz_options lz_options;
        return_if_error(lz_init(&next->coder->lz, allocator,
                        filters[0].options, &lz_options));

        // Setup the size information into next->coder->mf and deallocate
        // old buffers if they have wrong size.
        if (lz_encoder_prepare(&next->coder->mf, allocator, &lz_options))
                return LZMA_OPTIONS_ERROR;

        // Allocate new buffers if needed, and do the rest of
        // the initialization.
        if (lz_encoder_init(&next->coder->mf, allocator, &lz_options))
                return LZMA_MEM_ERROR;

        // Initialize the next filter in the chain, if any.
        return lzma_next_filter_init(&next->coder->next, allocator,
                        filters + 1);
}


extern LZMA_API(lzma_bool)
lzma_mf_is_supported(lzma_match_finder mf)
{
        bool ret = false;

#ifdef HAVE_MF_HC3
        if (mf == LZMA_MF_HC3)
                ret = true;
#endif

#ifdef HAVE_MF_HC4
        if (mf == LZMA_MF_HC4)
                ret = true;
#endif

#ifdef HAVE_MF_BT2
        if (mf == LZMA_MF_BT2)
                ret = true;
#endif

#ifdef HAVE_MF_BT3
        if (mf == LZMA_MF_BT3)
                ret = true;
#endif

#ifdef HAVE_MF_BT4
        if (mf == LZMA_MF_BT4)
                ret = true;
#endif

        return ret;
}