aboutsummaryrefslogtreecommitdiffstats
path: root/contrib/libs/xz/liblzma/lz
diff options
context:
space:
mode:
authorthegeorg <thegeorg@yandex-team.ru>2022-05-07 11:12:39 +0300
committerthegeorg <thegeorg@yandex-team.ru>2022-05-07 11:12:39 +0300
commita0c9cd069ff45244eeb9caa2fcadf1e9bc4a840d (patch)
treec9a178299041ce75a8b6d3edb644521c0f13c092 /contrib/libs/xz/liblzma/lz
parentd47cdd245c4b49c8e273c80a2e2b29ee5b2071c3 (diff)
downloadydb-a0c9cd069ff45244eeb9caa2fcadf1e9bc4a840d.tar.gz
Improve layout of contrib/libs/lzma
* Rename contrib/libs/xz to contrib/libs/lzma (yamaker project is updated accordingly) * Move xz/liblzma/ya.make to top level * Update provides.pbtxt and PEERDIRs as necessary ref:1bb07a87b6adb738965483167fa64e7ad5da1e2b
Diffstat (limited to 'contrib/libs/xz/liblzma/lz')
-rw-r--r--contrib/libs/xz/liblzma/lz/lz_decoder.c311
-rw-r--r--contrib/libs/xz/liblzma/lz/lz_decoder.h234
-rw-r--r--contrib/libs/xz/liblzma/lz/lz_encoder.c616
-rw-r--r--contrib/libs/xz/liblzma/lz/lz_encoder.h327
-rw-r--r--contrib/libs/xz/liblzma/lz/lz_encoder_hash.h108
-rw-r--r--contrib/libs/xz/liblzma/lz/lz_encoder_mf.c744
6 files changed, 0 insertions, 2340 deletions
diff --git a/contrib/libs/xz/liblzma/lz/lz_decoder.c b/contrib/libs/xz/liblzma/lz/lz_decoder.c
deleted file mode 100644
index 09b574388f..0000000000
--- a/contrib/libs/xz/liblzma/lz/lz_decoder.c
+++ /dev/null
@@ -1,311 +0,0 @@
-///////////////////////////////////////////////////////////////////////////////
-//
-/// \file lz_decoder.c
-/// \brief LZ out window
-///
-// Authors: Igor Pavlov
-// Lasse Collin
-//
-// This file has been put into the public domain.
-// You can do whatever you want with this file.
-//
-///////////////////////////////////////////////////////////////////////////////
-
-// liblzma supports multiple LZ77-based filters. The LZ part is shared
-// between these filters. The LZ code takes care of dictionary handling
-// and passing the data between filters in the chain. The filter-specific
-// part decodes from the input buffer to the dictionary.
-
-
-#include "lz_decoder.h"
-
-
-typedef struct {
- /// Dictionary (history buffer)
- lzma_dict dict;
-
- /// The actual LZ-based decoder e.g. LZMA
- lzma_lz_decoder lz;
-
- /// Next filter in the chain, if any. Note that LZMA and LZMA2 are
- /// only allowed as the last filter, but the long-range filter in
- /// future can be in the middle of the chain.
- lzma_next_coder next;
-
- /// True if the next filter in the chain has returned LZMA_STREAM_END.
- bool next_finished;
-
- /// True if the LZ decoder (e.g. LZMA) has detected end of payload
- /// marker. This may become true before next_finished becomes true.
- bool this_finished;
-
- /// Temporary buffer needed when the LZ-based filter is not the last
- /// filter in the chain. The output of the next filter is first
- /// decoded into buffer[], which is then used as input for the actual
- /// LZ-based decoder.
- struct {
- size_t pos;
- size_t size;
- uint8_t buffer[LZMA_BUFFER_SIZE];
- } temp;
-} lzma_coder;
-
-
-static void
-lz_decoder_reset(lzma_coder *coder)
-{
- coder->dict.pos = 0;
- coder->dict.full = 0;
- coder->dict.buf[coder->dict.size - 1] = '\0';
- coder->dict.need_reset = false;
- return;
-}
-
-
-static lzma_ret
-decode_buffer(lzma_coder *coder,
- 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)
-{
- while (true) {
- // Wrap the dictionary if needed.
- if (coder->dict.pos == coder->dict.size)
- coder->dict.pos = 0;
-
- // Store the current dictionary position. It is needed to know
- // where to start copying to the out[] buffer.
- const size_t dict_start = coder->dict.pos;
-
- // Calculate how much we allow coder->lz.code() to decode.
- // It must not decode past the end of the dictionary
- // buffer, and we don't want it to decode more than is
- // actually needed to fill the out[] buffer.
- coder->dict.limit = coder->dict.pos
- + my_min(out_size - *out_pos,
- coder->dict.size - coder->dict.pos);
-
- // Call the coder->lz.code() to do the actual decoding.
- const lzma_ret ret = coder->lz.code(
- coder->lz.coder, &coder->dict,
- in, in_pos, in_size);
-
- // Copy the decoded data from the dictionary to the out[]
- // buffer. Do it conditionally because out can be NULL
- // (in which case copy_size is always 0). Calling memcpy()
- // with a null-pointer is undefined even if the third
- // argument is 0.
- const size_t copy_size = coder->dict.pos - dict_start;
- assert(copy_size <= out_size - *out_pos);
-
- if (copy_size > 0)
- memcpy(out + *out_pos, coder->dict.buf + dict_start,
- copy_size);
-
- *out_pos += copy_size;
-
- // Reset the dictionary if so requested by coder->lz.code().
- if (coder->dict.need_reset) {
- lz_decoder_reset(coder);
-
- // Since we reset dictionary, we don't check if
- // dictionary became full.
- if (ret != LZMA_OK || *out_pos == out_size)
- return ret;
- } else {
- // Return if everything got decoded or an error
- // occurred, or if there's no more data to decode.
- //
- // Note that detecting if there's something to decode
- // is done by looking if dictionary become full
- // instead of looking if *in_pos == in_size. This
- // is because it is possible that all the input was
- // consumed already but some data is pending to be
- // written to the dictionary.
- if (ret != LZMA_OK || *out_pos == out_size
- || coder->dict.pos < coder->dict.size)
- return ret;
- }
- }
-}
-
-
-static lzma_ret
-lz_decode(void *coder_ptr, const 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)
-{
- lzma_coder *coder = coder_ptr;
-
- if (coder->next.code == NULL)
- return decode_buffer(coder, in, in_pos, in_size,
- out, out_pos, out_size);
-
- // We aren't the last coder in the chain, we need to decode
- // our input to a temporary buffer.
- while (*out_pos < out_size) {
- // Fill the temporary buffer if it is empty.
- if (!coder->next_finished
- && coder->temp.pos == coder->temp.size) {
- coder->temp.pos = 0;
- coder->temp.size = 0;
-
- const lzma_ret ret = coder->next.code(
- coder->next.coder,
- allocator, in, in_pos, in_size,
- coder->temp.buffer, &coder->temp.size,
- LZMA_BUFFER_SIZE, action);
-
- if (ret == LZMA_STREAM_END)
- coder->next_finished = true;
- else if (ret != LZMA_OK || coder->temp.size == 0)
- return ret;
- }
-
- if (coder->this_finished) {
- if (coder->temp.size != 0)
- return LZMA_DATA_ERROR;
-
- if (coder->next_finished)
- return LZMA_STREAM_END;
-
- return LZMA_OK;
- }
-
- const lzma_ret ret = decode_buffer(coder, coder->temp.buffer,
- &coder->temp.pos, coder->temp.size,
- out, out_pos, out_size);
-
- if (ret == LZMA_STREAM_END)
- coder->this_finished = true;
- else if (ret != LZMA_OK)
- return ret;
- else if (coder->next_finished && *out_pos < out_size)
- return LZMA_DATA_ERROR;
- }
-
- return LZMA_OK;
-}
-
-
-static void
-lz_decoder_end(void *coder_ptr, const lzma_allocator *allocator)
-{
- lzma_coder *coder = coder_ptr;
-
- lzma_next_end(&coder->next, allocator);
- lzma_free(coder->dict.buf, 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_decoder_init(lzma_next_coder *next, const lzma_allocator *allocator,
- const lzma_filter_info *filters,
- lzma_ret (*lz_init)(lzma_lz_decoder *lz,
- const lzma_allocator *allocator, const void *options,
- lzma_lz_options *lz_options))
-{
- // Allocate the base structure if it isn't already allocated.
- lzma_coder *coder = next->coder;
- if (coder == NULL) {
- coder = lzma_alloc(sizeof(lzma_coder), allocator);
- if (coder == NULL)
- return LZMA_MEM_ERROR;
-
- next->coder = coder;
- next->code = &lz_decode;
- next->end = &lz_decoder_end;
-
- coder->dict.buf = NULL;
- coder->dict.size = 0;
- coder->lz = LZMA_LZ_DECODER_INIT;
- coder->next = LZMA_NEXT_CODER_INIT;
- }
-
- // Allocate and initialize the LZ-based decoder. It will also give
- // us the dictionary size.
- lzma_lz_options lz_options;
- return_if_error(lz_init(&coder->lz, allocator,
- filters[0].options, &lz_options));
-
- // If the dictionary size is very small, increase it to 4096 bytes.
- // This is to prevent constant wrapping of the dictionary, which
- // would slow things down. The downside is that since we don't check
- // separately for the real dictionary size, we may happily accept
- // corrupt files.
- if (lz_options.dict_size < 4096)
- lz_options.dict_size = 4096;
-
- // Make dictionary size a multiple of 16. Some LZ-based decoders like
- // LZMA use the lowest bits lzma_dict.pos to know the alignment of the
- // data. Aligned buffer is also good when memcpying from the
- // dictionary to the output buffer, since applications are
- // recommended to give aligned buffers to liblzma.
- //
- // Avoid integer overflow.
- if (lz_options.dict_size > SIZE_MAX - 15)
- return LZMA_MEM_ERROR;
-
- lz_options.dict_size = (lz_options.dict_size + 15) & ~((size_t)(15));
-
- // Allocate and initialize the dictionary.
- if (coder->dict.size != lz_options.dict_size) {
- lzma_free(coder->dict.buf, allocator);
- coder->dict.buf
- = lzma_alloc(lz_options.dict_size, allocator);
- if (coder->dict.buf == NULL)
- return LZMA_MEM_ERROR;
-
- coder->dict.size = lz_options.dict_size;
- }
-
- lz_decoder_reset(next->coder);
-
- // Use the preset dictionary if it was given to us.
- if (lz_options.preset_dict != NULL
- && lz_options.preset_dict_size > 0) {
- // If the preset dictionary is bigger than the actual
- // dictionary, copy only the tail.
- const size_t copy_size = my_min(lz_options.preset_dict_size,
- lz_options.dict_size);
- const size_t offset = lz_options.preset_dict_size - copy_size;
- memcpy(coder->dict.buf, lz_options.preset_dict + offset,
- copy_size);
- coder->dict.pos = copy_size;
- coder->dict.full = copy_size;
- }
-
- // Miscellaneous initializations
- coder->next_finished = false;
- coder->this_finished = false;
- coder->temp.pos = 0;
- coder->temp.size = 0;
-
- // Initialize the next filter in the chain, if any.
- return lzma_next_filter_init(&coder->next, allocator, filters + 1);
-}
-
-
-extern uint64_t
-lzma_lz_decoder_memusage(size_t dictionary_size)
-{
- return sizeof(lzma_coder) + (uint64_t)(dictionary_size);
-}
-
-
-extern void
-lzma_lz_decoder_uncompressed(void *coder_ptr, lzma_vli uncompressed_size)
-{
- lzma_coder *coder = coder_ptr;
- coder->lz.set_uncompressed(coder->lz.coder, uncompressed_size);
-}
diff --git a/contrib/libs/xz/liblzma/lz/lz_decoder.h b/contrib/libs/xz/liblzma/lz/lz_decoder.h
deleted file mode 100644
index 754ccf37c6..0000000000
--- a/contrib/libs/xz/liblzma/lz/lz_decoder.h
+++ /dev/null
@@ -1,234 +0,0 @@
-///////////////////////////////////////////////////////////////////////////////
-//
-/// \file lz_decoder.h
-/// \brief LZ out window
-///
-// Authors: Igor Pavlov
-// Lasse Collin
-//
-// This file has been put into the public domain.
-// You can do whatever you want with this file.
-//
-///////////////////////////////////////////////////////////////////////////////
-
-#ifndef LZMA_LZ_DECODER_H
-#define LZMA_LZ_DECODER_H
-
-#include "common.h"
-
-
-typedef struct {
- /// Pointer to the dictionary buffer. It can be an allocated buffer
- /// internal to liblzma, or it can a be a buffer given by the
- /// application when in single-call mode (not implemented yet).
- uint8_t *buf;
-
- /// Write position in dictionary. The next byte will be written to
- /// buf[pos].
- size_t pos;
-
- /// Indicates how full the dictionary is. This is used by
- /// dict_is_distance_valid() to detect corrupt files that would
- /// read beyond the beginning of the dictionary.
- size_t full;
-
- /// Write limit
- size_t limit;
-
- /// Size of the dictionary
- size_t size;
-
- /// True when dictionary should be reset before decoding more data.
- bool need_reset;
-
-} lzma_dict;
-
-
-typedef struct {
- size_t dict_size;
- const uint8_t *preset_dict;
- size_t preset_dict_size;
-} lzma_lz_options;
-
-
-typedef struct {
- /// Data specific to the LZ-based decoder
- void *coder;
-
- /// Function to decode from in[] to *dict
- lzma_ret (*code)(void *coder,
- lzma_dict *restrict dict, const uint8_t *restrict in,
- size_t *restrict in_pos, size_t in_size);
-
- void (*reset)(void *coder, const void *options);
-
- /// Set the uncompressed size
- void (*set_uncompressed)(void *coder, lzma_vli uncompressed_size);
-
- /// Free allocated resources
- void (*end)(void *coder, const lzma_allocator *allocator);
-
-} lzma_lz_decoder;
-
-
-#define LZMA_LZ_DECODER_INIT \
- (lzma_lz_decoder){ \
- .coder = NULL, \
- .code = NULL, \
- .reset = NULL, \
- .set_uncompressed = NULL, \
- .end = NULL, \
- }
-
-
-extern lzma_ret lzma_lz_decoder_init(lzma_next_coder *next,
- const lzma_allocator *allocator,
- const lzma_filter_info *filters,
- lzma_ret (*lz_init)(lzma_lz_decoder *lz,
- const lzma_allocator *allocator, const void *options,
- lzma_lz_options *lz_options));
-
-extern uint64_t lzma_lz_decoder_memusage(size_t dictionary_size);
-
-extern void lzma_lz_decoder_uncompressed(
- void *coder, lzma_vli uncompressed_size);
-
-
-//////////////////////
-// Inline functions //
-//////////////////////
-
-/// Get a byte from the history buffer.
-static inline uint8_t
-dict_get(const lzma_dict *const dict, const uint32_t distance)
-{
- return dict->buf[dict->pos - distance - 1
- + (distance < dict->pos ? 0 : dict->size)];
-}
-
-
-/// Test if dictionary is empty.
-static inline bool
-dict_is_empty(const lzma_dict *const dict)
-{
- return dict->full == 0;
-}
-
-
-/// Validate the match distance
-static inline bool
-dict_is_distance_valid(const lzma_dict *const dict, const size_t distance)
-{
- return dict->full > distance;
-}
-
-
-/// Repeat *len bytes at distance.
-static inline bool
-dict_repeat(lzma_dict *dict, uint32_t distance, uint32_t *len)
-{
- // Don't write past the end of the dictionary.
- const size_t dict_avail = dict->limit - dict->pos;
- uint32_t left = my_min(dict_avail, *len);
- *len -= left;
-
- // Repeat a block of data from the history. Because memcpy() is faster
- // than copying byte by byte in a loop, the copying process gets split
- // into three cases.
- if (distance < left) {
- // Source and target areas overlap, thus we can't use
- // memcpy() nor even memmove() safely.
- do {
- dict->buf[dict->pos] = dict_get(dict, distance);
- ++dict->pos;
- } while (--left > 0);
-
- } else if (distance < dict->pos) {
- // The easiest and fastest case
- memcpy(dict->buf + dict->pos,
- dict->buf + dict->pos - distance - 1,
- left);
- dict->pos += left;
-
- } else {
- // The bigger the dictionary, the more rare this
- // case occurs. We need to "wrap" the dict, thus
- // we might need two memcpy() to copy all the data.
- assert(dict->full == dict->size);
- const uint32_t copy_pos
- = dict->pos - distance - 1 + dict->size;
- uint32_t copy_size = dict->size - copy_pos;
-
- if (copy_size < left) {
- memmove(dict->buf + dict->pos, dict->buf + copy_pos,
- copy_size);
- dict->pos += copy_size;
- copy_size = left - copy_size;
- memcpy(dict->buf + dict->pos, dict->buf, copy_size);
- dict->pos += copy_size;
- } else {
- memmove(dict->buf + dict->pos, dict->buf + copy_pos,
- left);
- dict->pos += left;
- }
- }
-
- // Update how full the dictionary is.
- if (dict->full < dict->pos)
- dict->full = dict->pos;
-
- return unlikely(*len != 0);
-}
-
-
-/// Puts one byte into the dictionary. Returns true if the dictionary was
-/// already full and the byte couldn't be added.
-static inline bool
-dict_put(lzma_dict *dict, uint8_t byte)
-{
- if (unlikely(dict->pos == dict->limit))
- return true;
-
- dict->buf[dict->pos++] = byte;
-
- if (dict->pos > dict->full)
- dict->full = dict->pos;
-
- return false;
-}
-
-
-/// Copies arbitrary amount of data into the dictionary.
-static inline void
-dict_write(lzma_dict *restrict dict, const uint8_t *restrict in,
- size_t *restrict in_pos, size_t in_size,
- size_t *restrict left)
-{
- // NOTE: If we are being given more data than the size of the
- // dictionary, it could be possible to optimize the LZ decoder
- // so that not everything needs to go through the dictionary.
- // This shouldn't be very common thing in practice though, and
- // the slowdown of one extra memcpy() isn't bad compared to how
- // much time it would have taken if the data were compressed.
-
- if (in_size - *in_pos > *left)
- in_size = *in_pos + *left;
-
- *left -= lzma_bufcpy(in, in_pos, in_size,
- dict->buf, &dict->pos, dict->limit);
-
- if (dict->pos > dict->full)
- dict->full = dict->pos;
-
- return;
-}
-
-
-static inline void
-dict_reset(lzma_dict *dict)
-{
- dict->need_reset = true;
- return;
-}
-
-#endif
diff --git a/contrib/libs/xz/liblzma/lz/lz_encoder.c b/contrib/libs/xz/liblzma/lz/lz_encoder.c
deleted file mode 100644
index ad7a303acb..0000000000
--- a/contrib/libs/xz/liblzma/lz/lz_encoder.c
+++ /dev/null
@@ -1,616 +0,0 @@
-///////////////////////////////////////////////////////////////////////////////
-//
-/// \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"
-
-// See lz_encoder_hash.h. This is a bit hackish but avoids making
-// endianness a conditional in makefiles.
-#if defined(WORDS_BIGENDIAN) && !defined(HAVE_SMALL)
-# error #include "lz_encoder_hash_table.h"
-#endif
-
-#include "memcmplen.h"
-
-
-typedef struct {
- /// 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;
-} lzma_coder;
-
-
-/// \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, const 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;
- lzma_ret ret;
- if (coder->next.code == NULL) {
- // Not using a filter, simply memcpy() as much as possible.
- 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 {
- ret = coder->next.code(coder->next.coder, allocator,
- in, in_pos, in_size,
- coder->mf.buffer, &write_pos,
- coder->mf.size, action);
- }
-
- coder->mf.write_pos = write_pos;
-
- // Silence Valgrind. lzma_memcmplen() can read extra bytes
- // and Valgrind will give warnings if those bytes are uninitialized
- // because Valgrind cannot see that the values of the uninitialized
- // bytes are eventually ignored.
- memzero(coder->mf.buffer + write_pos, LZMA_MEMCMPLEN_EXTRA);
-
- // 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 uint32_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(void *coder_ptr, const 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)
-{
- lzma_coder *coder = coder_ptr;
-
- 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, const 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 limiting 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;
-*/
-
- const uint32_t old_hash_count = mf->hash_count;
- const uint32_t old_sons_count = mf->sons_count;
- mf->hash_count = hs;
- mf->sons_count = mf->cyclic_size;
- if (is_bt)
- mf->sons_count *= 2;
-
- // Deallocate the old hash array if it exists and has different size
- // than what is needed now.
- if (old_hash_count != mf->hash_count
- || old_sons_count != mf->sons_count) {
- lzma_free(mf->hash, allocator);
- mf->hash = NULL;
-
- lzma_free(mf->son, allocator);
- mf->son = NULL;
- }
-
- // Maximum number of match finder cycles
- mf->depth = lz_options->depth;
- if (mf->depth == 0) {
- if (is_bt)
- mf->depth = 16 + mf->nice_len / 2;
- else
- mf->depth = 4 + mf->nice_len / 4;
- }
-
- return false;
-}
-
-
-static bool
-lz_encoder_init(lzma_mf *mf, const lzma_allocator *allocator,
- const lzma_lz_options *lz_options)
-{
- // Allocate the history buffer.
- if (mf->buffer == NULL) {
- // lzma_memcmplen() is used for the dictionary buffer
- // so we need to allocate a few extra bytes to prevent
- // it from reading past the end of the buffer.
- mf->buffer = lzma_alloc(mf->size + LZMA_MEMCMPLEN_EXTRA,
- allocator);
- if (mf->buffer == NULL)
- return true;
-
- // Keep Valgrind happy with lzma_memcmplen() and initialize
- // the extra bytes whose value may get read but which will
- // effectively get ignored.
- memzero(mf->buffer + mf->size, LZMA_MEMCMPLEN_EXTRA);
- }
-
- // 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;
-
-#if UINT32_MAX >= SIZE_MAX / 4
- // Check for integer overflow. (Huge dictionaries are not
- // possible on 32-bit CPU.)
- if (mf->hash_count > SIZE_MAX / sizeof(uint32_t)
- || mf->sons_count > SIZE_MAX / sizeof(uint32_t))
- return true;
-#endif
-
- // Allocate and initialize the hash table. Since EMPTY_HASH_VALUE
- // is zero, we can use lzma_alloc_zero() or memzero() for mf->hash.
- //
- // We don't need to initialize mf->son, but not doing that may
- // make Valgrind complain in normalization (see normalize() in
- // lz_encoder_mf.c). Skipping the initialization is *very* good
- // when big dictionary is used but only small amount of data gets
- // actually compressed: most of the mf->son won't get actually
- // allocated by the kernel, so we avoid wasting RAM and improve
- // initialization speed a lot.
- if (mf->hash == NULL) {
- mf->hash = lzma_alloc_zero(mf->hash_count * sizeof(uint32_t),
- allocator);
- mf->son = lzma_alloc(mf->sons_count * sizeof(uint32_t),
- allocator);
-
- if (mf->hash == NULL || mf->son == NULL) {
- lzma_free(mf->hash, allocator);
- mf->hash = NULL;
-
- lzma_free(mf->son, allocator);
- mf->son = NULL;
-
- return true;
- }
- } else {
-/*
- for (uint32_t i = 0; i < mf->hash_count; ++i)
- mf->hash[i] = EMPTY_HASH_VALUE;
-*/
- memzero(mf->hash, mf->hash_count * sizeof(uint32_t));
- }
-
- mf->cyclic_pos = 0;
-
- // 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 = my_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,
- .son = NULL,
- .hash_count = 0,
- .sons_count = 0,
- };
-
- // 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_count) + mf.sons_count) * sizeof(uint32_t)
- + mf.size + sizeof(lzma_coder);
-}
-
-
-static void
-lz_encoder_end(void *coder_ptr, const lzma_allocator *allocator)
-{
- lzma_coder *coder = coder_ptr;
-
- lzma_next_end(&coder->next, allocator);
-
- lzma_free(coder->mf.son, 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;
-}
-
-
-static lzma_ret
-lz_encoder_update(void *coder_ptr, const lzma_allocator *allocator,
- const lzma_filter *filters_null lzma_attribute((__unused__)),
- const lzma_filter *reversed_filters)
-{
- lzma_coder *coder = coder_ptr;
-
- if (coder->lz.options_update == NULL)
- return LZMA_PROG_ERROR;
-
- return_if_error(coder->lz.options_update(
- coder->lz.coder, reversed_filters));
-
- return lzma_next_filter_update(
- &coder->next, allocator, reversed_filters + 1);
-}
-
-
-extern lzma_ret
-lzma_lz_encoder_init(lzma_next_coder *next, const lzma_allocator *allocator,
- const lzma_filter_info *filters,
- lzma_ret (*lz_init)(lzma_lz_encoder *lz,
- const 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.
- lzma_coder *coder = next->coder;
- if (coder == NULL) {
- coder = lzma_alloc(sizeof(lzma_coder), allocator);
- if (coder == NULL)
- return LZMA_MEM_ERROR;
-
- next->coder = coder;
- next->code = &lz_encode;
- next->end = &lz_encoder_end;
- next->update = &lz_encoder_update;
-
- coder->lz.coder = NULL;
- coder->lz.code = NULL;
- coder->lz.end = NULL;
-
- // mf.size is initialized to silence Valgrind
- // when used on optimized binaries (GCC may reorder
- // code in a way that Valgrind gets unhappy).
- coder->mf.buffer = NULL;
- coder->mf.size = 0;
- coder->mf.hash = NULL;
- coder->mf.son = NULL;
- coder->mf.hash_count = 0;
- coder->mf.sons_count = 0;
-
- coder->next = LZMA_NEXT_CODER_INIT;
- }
-
- // Initialize the LZ-based encoder.
- lzma_lz_options lz_options;
- return_if_error(lz_init(&coder->lz, allocator,
- filters[0].options, &lz_options));
-
- // Setup the size information into coder->mf and deallocate
- // old buffers if they have wrong size.
- if (lz_encoder_prepare(&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(&coder->mf, allocator, &lz_options))
- return LZMA_MEM_ERROR;
-
- // Initialize the next filter in the chain, if any.
- return lzma_next_filter_init(&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;
-}
diff --git a/contrib/libs/xz/liblzma/lz/lz_encoder.h b/contrib/libs/xz/liblzma/lz/lz_encoder.h
deleted file mode 100644
index 426dcd8a38..0000000000
--- a/contrib/libs/xz/liblzma/lz/lz_encoder.h
+++ /dev/null
@@ -1,327 +0,0 @@
-///////////////////////////////////////////////////////////////////////////////
-//
-/// \file lz_encoder.h
-/// \brief LZ in window and match finder API
-///
-// Authors: Igor Pavlov
-// Lasse Collin
-//
-// This file has been put into the public domain.
-// You can do whatever you want with this file.
-//
-///////////////////////////////////////////////////////////////////////////////
-
-#ifndef LZMA_LZ_ENCODER_H
-#define LZMA_LZ_ENCODER_H
-
-#include "common.h"
-
-
-/// A table of these is used by the LZ-based encoder to hold
-/// the length-distance pairs found by the match finder.
-typedef struct {
- uint32_t len;
- uint32_t dist;
-} lzma_match;
-
-
-typedef struct lzma_mf_s lzma_mf;
-struct lzma_mf_s {
- ///////////////
- // In Window //
- ///////////////
-
- /// Pointer to buffer with data to be compressed
- uint8_t *buffer;
-
- /// Total size of the allocated buffer (that is, including all
- /// the extra space)
- uint32_t size;
-
- /// Number of bytes that must be kept available in our input history.
- /// That is, once keep_size_before bytes have been processed,
- /// buffer[read_pos - keep_size_before] is the oldest byte that
- /// must be available for reading.
- uint32_t keep_size_before;
-
- /// Number of bytes that must be kept in buffer after read_pos.
- /// That is, read_pos <= write_pos - keep_size_after as long as
- /// action is LZMA_RUN; when action != LZMA_RUN, read_pos is allowed
- /// to reach write_pos so that the last bytes get encoded too.
- uint32_t keep_size_after;
-
- /// Match finders store locations of matches using 32-bit integers.
- /// To avoid adjusting several megabytes of integers every time the
- /// input window is moved with move_window, we only adjust the
- /// offset of the buffer. Thus, buffer[value_in_hash_table - offset]
- /// is the byte pointed by value_in_hash_table.
- uint32_t offset;
-
- /// buffer[read_pos] is the next byte to run through the match
- /// finder. This is incremented in the match finder once the byte
- /// has been processed.
- uint32_t read_pos;
-
- /// Number of bytes that have been ran through the match finder, but
- /// which haven't been encoded by the LZ-based encoder yet.
- uint32_t read_ahead;
-
- /// As long as read_pos is less than read_limit, there is enough
- /// input available in buffer for at least one encoding loop.
- ///
- /// Because of the stateful API, read_limit may and will get greater
- /// than read_pos quite often. This is taken into account when
- /// calculating the value for keep_size_after.
- uint32_t read_limit;
-
- /// buffer[write_pos] is the first byte that doesn't contain valid
- /// uncompressed data; that is, the next input byte will be copied
- /// to buffer[write_pos].
- uint32_t write_pos;
-
- /// Number of bytes not hashed before read_pos. This is needed to
- /// restart the match finder after LZMA_SYNC_FLUSH.
- uint32_t pending;
-
- //////////////////
- // Match Finder //
- //////////////////
-
- /// Find matches. Returns the number of distance-length pairs written
- /// to the matches array. This is called only via lzma_mf_find().
- uint32_t (*find)(lzma_mf *mf, lzma_match *matches);
-
- /// Skips num bytes. This is like find() but doesn't make the
- /// distance-length pairs available, thus being a little faster.
- /// This is called only via mf_skip().
- void (*skip)(lzma_mf *mf, uint32_t num);
-
- uint32_t *hash;
- uint32_t *son;
- uint32_t cyclic_pos;
- uint32_t cyclic_size; // Must be dictionary size + 1.
- uint32_t hash_mask;
-
- /// Maximum number of loops in the match finder
- uint32_t depth;
-
- /// Maximum length of a match that the match finder will try to find.
- uint32_t nice_len;
-
- /// Maximum length of a match supported by the LZ-based encoder.
- /// If the longest match found by the match finder is nice_len,
- /// mf_find() tries to expand it up to match_len_max bytes.
- uint32_t match_len_max;
-
- /// When running out of input, binary tree match finders need to know
- /// if it is due to flushing or finishing. The action is used also
- /// by the LZ-based encoders themselves.
- lzma_action action;
-
- /// Number of elements in hash[]
- uint32_t hash_count;
-
- /// Number of elements in son[]
- uint32_t sons_count;
-};
-
-
-typedef struct {
- /// Extra amount of data to keep available before the "actual"
- /// dictionary.
- size_t before_size;
-
- /// Size of the history buffer
- size_t dict_size;
-
- /// Extra amount of data to keep available after the "actual"
- /// dictionary.
- size_t after_size;
-
- /// Maximum length of a match that the LZ-based encoder can accept.
- /// This is used to extend matches of length nice_len to the
- /// maximum possible length.
- size_t match_len_max;
-
- /// Match finder will search matches up to this length.
- /// This must be less than or equal to match_len_max.
- size_t nice_len;
-
- /// Type of the match finder to use
- lzma_match_finder match_finder;
-
- /// Maximum search depth
- uint32_t depth;
-
- /// TODO: Comment
- const uint8_t *preset_dict;
-
- uint32_t preset_dict_size;
-
-} lzma_lz_options;
-
-
-// The total usable buffer space at any moment outside the match finder:
-// before_size + dict_size + after_size + match_len_max
-//
-// In reality, there's some extra space allocated to prevent the number of
-// memmove() calls reasonable. The bigger the dict_size is, the bigger
-// this extra buffer will be since with bigger dictionaries memmove() would
-// also take longer.
-//
-// A single encoder loop in the LZ-based encoder may call the match finder
-// (mf_find() or mf_skip()) at most after_size times. In other words,
-// a single encoder loop may increment lzma_mf.read_pos at most after_size
-// times. Since matches are looked up to
-// lzma_mf.buffer[lzma_mf.read_pos + match_len_max - 1], the total
-// amount of extra buffer needed after dict_size becomes
-// after_size + match_len_max.
-//
-// before_size has two uses. The first one is to keep literals available
-// in cases when the LZ-based encoder has made some read ahead.
-// TODO: Maybe this could be changed by making the LZ-based encoders to
-// store the actual literals as they do with length-distance pairs.
-//
-// Algorithms such as LZMA2 first try to compress a chunk, and then check
-// if the encoded result is smaller than the uncompressed one. If the chunk
-// was uncompressible, it is better to store it in uncompressed form in
-// the output stream. To do this, the whole uncompressed chunk has to be
-// still available in the history buffer. before_size achieves that.
-
-
-typedef struct {
- /// Data specific to the LZ-based encoder
- void *coder;
-
- /// Function to encode from *dict to out[]
- lzma_ret (*code)(void *coder,
- lzma_mf *restrict mf, uint8_t *restrict out,
- size_t *restrict out_pos, size_t out_size);
-
- /// Free allocated resources
- void (*end)(void *coder, const lzma_allocator *allocator);
-
- /// Update the options in the middle of the encoding.
- lzma_ret (*options_update)(void *coder, const lzma_filter *filter);
-
-} lzma_lz_encoder;
-
-
-// Basic steps:
-// 1. Input gets copied into the dictionary.
-// 2. Data in dictionary gets run through the match finder byte by byte.
-// 3. The literals and matches are encoded using e.g. LZMA.
-//
-// The bytes that have been ran through the match finder, but not encoded yet,
-// are called `read ahead'.
-
-
-/// Get pointer to the first byte not ran through the match finder
-static inline const uint8_t *
-mf_ptr(const lzma_mf *mf)
-{
- return mf->buffer + mf->read_pos;
-}
-
-
-/// Get the number of bytes that haven't been ran through the match finder yet.
-static inline uint32_t
-mf_avail(const lzma_mf *mf)
-{
- return mf->write_pos - mf->read_pos;
-}
-
-
-/// Get the number of bytes that haven't been encoded yet (some of these
-/// bytes may have been ran through the match finder though).
-static inline uint32_t
-mf_unencoded(const lzma_mf *mf)
-{
- return mf->write_pos - mf->read_pos + mf->read_ahead;
-}
-
-
-/// Calculate the absolute offset from the beginning of the most recent
-/// dictionary reset. Only the lowest four bits are important, so there's no
-/// problem that we don't know the 64-bit size of the data encoded so far.
-///
-/// NOTE: When moving the input window, we need to do it so that the lowest
-/// bits of dict->read_pos are not modified to keep this macro working
-/// as intended.
-static inline uint32_t
-mf_position(const lzma_mf *mf)
-{
- return mf->read_pos - mf->read_ahead;
-}
-
-
-/// Since everything else begins with mf_, use it also for lzma_mf_find().
-#define mf_find lzma_mf_find
-
-
-/// Skip the given number of bytes. This is used when a good match was found.
-/// For example, if mf_find() finds a match of 200 bytes long, the first byte
-/// of that match was already consumed by mf_find(), and the rest 199 bytes
-/// have to be skipped with mf_skip(mf, 199).
-static inline void
-mf_skip(lzma_mf *mf, uint32_t amount)
-{
- if (amount != 0) {
- mf->skip(mf, amount);
- mf->read_ahead += amount;
- }
-}
-
-
-/// Copies at most *left number of bytes from the history buffer
-/// to out[]. This is needed by LZMA2 to encode uncompressed chunks.
-static inline void
-mf_read(lzma_mf *mf, uint8_t *out, size_t *out_pos, size_t out_size,
- size_t *left)
-{
- const size_t out_avail = out_size - *out_pos;
- const size_t copy_size = my_min(out_avail, *left);
-
- assert(mf->read_ahead == 0);
- assert(mf->read_pos >= *left);
-
- memcpy(out + *out_pos, mf->buffer + mf->read_pos - *left,
- copy_size);
-
- *out_pos += copy_size;
- *left -= copy_size;
- return;
-}
-
-
-extern lzma_ret lzma_lz_encoder_init(
- lzma_next_coder *next, const lzma_allocator *allocator,
- const lzma_filter_info *filters,
- lzma_ret (*lz_init)(lzma_lz_encoder *lz,
- const lzma_allocator *allocator, const void *options,
- lzma_lz_options *lz_options));
-
-
-extern uint64_t lzma_lz_encoder_memusage(const lzma_lz_options *lz_options);
-
-
-// These are only for LZ encoder's internal use.
-extern uint32_t lzma_mf_find(
- lzma_mf *mf, uint32_t *count, lzma_match *matches);
-
-extern uint32_t lzma_mf_hc3_find(lzma_mf *dict, lzma_match *matches);
-extern void lzma_mf_hc3_skip(lzma_mf *dict, uint32_t amount);
-
-extern uint32_t lzma_mf_hc4_find(lzma_mf *dict, lzma_match *matches);
-extern void lzma_mf_hc4_skip(lzma_mf *dict, uint32_t amount);
-
-extern uint32_t lzma_mf_bt2_find(lzma_mf *dict, lzma_match *matches);
-extern void lzma_mf_bt2_skip(lzma_mf *dict, uint32_t amount);
-
-extern uint32_t lzma_mf_bt3_find(lzma_mf *dict, lzma_match *matches);
-extern void lzma_mf_bt3_skip(lzma_mf *dict, uint32_t amount);
-
-extern uint32_t lzma_mf_bt4_find(lzma_mf *dict, lzma_match *matches);
-extern void lzma_mf_bt4_skip(lzma_mf *dict, uint32_t amount);
-
-#endif
diff --git a/contrib/libs/xz/liblzma/lz/lz_encoder_hash.h b/contrib/libs/xz/liblzma/lz/lz_encoder_hash.h
deleted file mode 100644
index fb15c58146..0000000000
--- a/contrib/libs/xz/liblzma/lz/lz_encoder_hash.h
+++ /dev/null
@@ -1,108 +0,0 @@
-///////////////////////////////////////////////////////////////////////////////
-//
-/// \file lz_encoder_hash.h
-/// \brief Hash macros for match finders
-//
-// Author: Igor Pavlov
-//
-// This file has been put into the public domain.
-// You can do whatever you want with this file.
-//
-///////////////////////////////////////////////////////////////////////////////
-
-#ifndef LZMA_LZ_ENCODER_HASH_H
-#define LZMA_LZ_ENCODER_HASH_H
-
-#if defined(WORDS_BIGENDIAN) && !defined(HAVE_SMALL)
- // This is to make liblzma produce the same output on big endian
- // systems that it does on little endian systems. lz_encoder.c
- // takes care of including the actual table.
- extern const uint32_t lzma_lz_hash_table[256];
-# define hash_table lzma_lz_hash_table
-#else
-# include "check.h"
-# define hash_table lzma_crc32_table[0]
-#endif
-
-#define HASH_2_SIZE (UINT32_C(1) << 10)
-#define HASH_3_SIZE (UINT32_C(1) << 16)
-#define HASH_4_SIZE (UINT32_C(1) << 20)
-
-#define HASH_2_MASK (HASH_2_SIZE - 1)
-#define HASH_3_MASK (HASH_3_SIZE - 1)
-#define HASH_4_MASK (HASH_4_SIZE - 1)
-
-#define FIX_3_HASH_SIZE (HASH_2_SIZE)
-#define FIX_4_HASH_SIZE (HASH_2_SIZE + HASH_3_SIZE)
-#define FIX_5_HASH_SIZE (HASH_2_SIZE + HASH_3_SIZE + HASH_4_SIZE)
-
-// Endianness doesn't matter in hash_2_calc() (no effect on the output).
-#ifdef TUKLIB_FAST_UNALIGNED_ACCESS
-# define hash_2_calc() \
- const uint32_t hash_value = read16ne(cur)
-#else
-# define hash_2_calc() \
- const uint32_t hash_value \
- = (uint32_t)(cur[0]) | ((uint32_t)(cur[1]) << 8)
-#endif
-
-#define hash_3_calc() \
- const uint32_t temp = hash_table[cur[0]] ^ cur[1]; \
- const uint32_t hash_2_value = temp & HASH_2_MASK; \
- const uint32_t hash_value \
- = (temp ^ ((uint32_t)(cur[2]) << 8)) & mf->hash_mask
-
-#define hash_4_calc() \
- const uint32_t temp = hash_table[cur[0]] ^ cur[1]; \
- const uint32_t hash_2_value = temp & HASH_2_MASK; \
- const uint32_t hash_3_value \
- = (temp ^ ((uint32_t)(cur[2]) << 8)) & HASH_3_MASK; \
- const uint32_t hash_value = (temp ^ ((uint32_t)(cur[2]) << 8) \
- ^ (hash_table[cur[3]] << 5)) & mf->hash_mask
-
-
-// The following are not currently used.
-
-#define hash_5_calc() \
- const uint32_t temp = hash_table[cur[0]] ^ cur[1]; \
- const uint32_t hash_2_value = temp & HASH_2_MASK; \
- const uint32_t hash_3_value \
- = (temp ^ ((uint32_t)(cur[2]) << 8)) & HASH_3_MASK; \
- uint32_t hash_4_value = (temp ^ ((uint32_t)(cur[2]) << 8) ^ \
- ^ hash_table[cur[3]] << 5); \
- const uint32_t hash_value \
- = (hash_4_value ^ (hash_table[cur[4]] << 3)) \
- & mf->hash_mask; \
- hash_4_value &= HASH_4_MASK
-
-/*
-#define hash_zip_calc() \
- const uint32_t hash_value \
- = (((uint32_t)(cur[0]) | ((uint32_t)(cur[1]) << 8)) \
- ^ hash_table[cur[2]]) & 0xFFFF
-*/
-
-#define hash_zip_calc() \
- const uint32_t hash_value \
- = (((uint32_t)(cur[2]) | ((uint32_t)(cur[0]) << 8)) \
- ^ hash_table[cur[1]]) & 0xFFFF
-
-#define mt_hash_2_calc() \
- const uint32_t hash_2_value \
- = (hash_table[cur[0]] ^ cur[1]) & HASH_2_MASK
-
-#define mt_hash_3_calc() \
- const uint32_t temp = hash_table[cur[0]] ^ cur[1]; \
- const uint32_t hash_2_value = temp & HASH_2_MASK; \
- const uint32_t hash_3_value \
- = (temp ^ ((uint32_t)(cur[2]) << 8)) & HASH_3_MASK
-
-#define mt_hash_4_calc() \
- const uint32_t temp = hash_table[cur[0]] ^ cur[1]; \
- const uint32_t hash_2_value = temp & HASH_2_MASK; \
- const uint32_t hash_3_value \
- = (temp ^ ((uint32_t)(cur[2]) << 8)) & HASH_3_MASK; \
- const uint32_t hash_4_value = (temp ^ ((uint32_t)(cur[2]) << 8) ^ \
- (hash_table[cur[3]] << 5)) & HASH_4_MASK
-
-#endif
diff --git a/contrib/libs/xz/liblzma/lz/lz_encoder_mf.c b/contrib/libs/xz/liblzma/lz/lz_encoder_mf.c
deleted file mode 100644
index d03657a7c9..0000000000
--- a/contrib/libs/xz/liblzma/lz/lz_encoder_mf.c
+++ /dev/null
@@ -1,744 +0,0 @@
-///////////////////////////////////////////////////////////////////////////////
-//
-/// \file lz_encoder_mf.c
-/// \brief Match finders
-///
-// 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 "memcmplen.h"
-
-
-/// \brief Find matches starting from the current byte
-///
-/// \return The length of the longest match found
-extern uint32_t
-lzma_mf_find(lzma_mf *mf, uint32_t *count_ptr, lzma_match *matches)
-{
- // Call the match finder. It returns the number of length-distance
- // pairs found.
- // FIXME: Minimum count is zero, what _exactly_ is the maximum?
- const uint32_t count = mf->find(mf, matches);
-
- // Length of the longest match; assume that no matches were found
- // and thus the maximum length is zero.
- uint32_t len_best = 0;
-
- if (count > 0) {
-#ifndef NDEBUG
- // Validate the matches.
- for (uint32_t i = 0; i < count; ++i) {
- assert(matches[i].len <= mf->nice_len);
- assert(matches[i].dist < mf->read_pos);
- assert(memcmp(mf_ptr(mf) - 1,
- mf_ptr(mf) - matches[i].dist - 2,
- matches[i].len) == 0);
- }
-#endif
-
- // The last used element in the array contains
- // the longest match.
- len_best = matches[count - 1].len;
-
- // If a match of maximum search length was found, try to
- // extend the match to maximum possible length.
- if (len_best == mf->nice_len) {
- // The limit for the match length is either the
- // maximum match length supported by the LZ-based
- // encoder or the number of bytes left in the
- // dictionary, whichever is smaller.
- uint32_t limit = mf_avail(mf) + 1;
- if (limit > mf->match_len_max)
- limit = mf->match_len_max;
-
- // Pointer to the byte we just ran through
- // the match finder.
- const uint8_t *p1 = mf_ptr(mf) - 1;
-
- // Pointer to the beginning of the match. We need -1
- // here because the match distances are zero based.
- const uint8_t *p2 = p1 - matches[count - 1].dist - 1;
-
- len_best = lzma_memcmplen(p1, p2, len_best, limit);
- }
- }
-
- *count_ptr = count;
-
- // Finally update the read position to indicate that match finder was
- // run for this dictionary offset.
- ++mf->read_ahead;
-
- return len_best;
-}
-
-
-/// Hash value to indicate unused element in the hash. Since we start the
-/// positions from dict_size + 1, zero is always too far to qualify
-/// as usable match position.
-#define EMPTY_HASH_VALUE 0
-
-
-/// Normalization must be done when lzma_mf.offset + lzma_mf.read_pos
-/// reaches MUST_NORMALIZE_POS.
-#define MUST_NORMALIZE_POS UINT32_MAX
-
-
-/// \brief Normalizes hash values
-///
-/// The hash arrays store positions of match candidates. The positions are
-/// relative to an arbitrary offset that is not the same as the absolute
-/// offset in the input stream. The relative position of the current byte
-/// is lzma_mf.offset + lzma_mf.read_pos. The distances of the matches are
-/// the differences of the current read position and the position found from
-/// the hash.
-///
-/// To prevent integer overflows of the offsets stored in the hash arrays,
-/// we need to "normalize" the stored values now and then. During the
-/// normalization, we drop values that indicate distance greater than the
-/// dictionary size, thus making space for new values.
-static void
-normalize(lzma_mf *mf)
-{
- assert(mf->read_pos + mf->offset == MUST_NORMALIZE_POS);
-
- // In future we may not want to touch the lowest bits, because there
- // may be match finders that use larger resolution than one byte.
- const uint32_t subvalue
- = (MUST_NORMALIZE_POS - mf->cyclic_size);
- // & ~((UINT32_C(1) << 10) - 1);
-
- for (uint32_t i = 0; i < mf->hash_count; ++i) {
- // If the distance is greater than the dictionary size,
- // we can simply mark the hash element as empty.
- if (mf->hash[i] <= subvalue)
- mf->hash[i] = EMPTY_HASH_VALUE;
- else
- mf->hash[i] -= subvalue;
- }
-
- for (uint32_t i = 0; i < mf->sons_count; ++i) {
- // Do the same for mf->son.
- //
- // NOTE: There may be uninitialized elements in mf->son.
- // Valgrind may complain that the "if" below depends on
- // an uninitialized value. In this case it is safe to ignore
- // the warning. See also the comments in lz_encoder_init()
- // in lz_encoder.c.
- if (mf->son[i] <= subvalue)
- mf->son[i] = EMPTY_HASH_VALUE;
- else
- mf->son[i] -= subvalue;
- }
-
- // Update offset to match the new locations.
- mf->offset -= subvalue;
-
- return;
-}
-
-
-/// Mark the current byte as processed from point of view of the match finder.
-static void
-move_pos(lzma_mf *mf)
-{
- if (++mf->cyclic_pos == mf->cyclic_size)
- mf->cyclic_pos = 0;
-
- ++mf->read_pos;
- assert(mf->read_pos <= mf->write_pos);
-
- if (unlikely(mf->read_pos + mf->offset == UINT32_MAX))
- normalize(mf);
-}
-
-
-/// When flushing, we cannot run the match finder unless there is nice_len
-/// bytes available in the dictionary. Instead, we skip running the match
-/// finder (indicating that no match was found), and count how many bytes we
-/// have ignored this way.
-///
-/// When new data is given after the flushing was completed, the match finder
-/// is restarted by rewinding mf->read_pos backwards by mf->pending. Then
-/// the missed bytes are added to the hash using the match finder's skip
-/// function (with small amount of input, it may start using mf->pending
-/// again if flushing).
-///
-/// Due to this rewinding, we don't touch cyclic_pos or test for
-/// normalization. It will be done when the match finder's skip function
-/// catches up after a flush.
-static void
-move_pending(lzma_mf *mf)
-{
- ++mf->read_pos;
- assert(mf->read_pos <= mf->write_pos);
- ++mf->pending;
-}
-
-
-/// Calculate len_limit and determine if there is enough input to run
-/// the actual match finder code. Sets up "cur" and "pos". This macro
-/// is used by all find functions and binary tree skip functions. Hash
-/// chain skip function doesn't need len_limit so a simpler code is used
-/// in them.
-#define header(is_bt, len_min, ret_op) \
- uint32_t len_limit = mf_avail(mf); \
- if (mf->nice_len <= len_limit) { \
- len_limit = mf->nice_len; \
- } else if (len_limit < (len_min) \
- || (is_bt && mf->action == LZMA_SYNC_FLUSH)) { \
- assert(mf->action != LZMA_RUN); \
- move_pending(mf); \
- ret_op; \
- } \
- const uint8_t *cur = mf_ptr(mf); \
- const uint32_t pos = mf->read_pos + mf->offset
-
-
-/// Header for find functions. "return 0" indicates that zero matches
-/// were found.
-#define header_find(is_bt, len_min) \
- header(is_bt, len_min, return 0); \
- uint32_t matches_count = 0
-
-
-/// Header for a loop in a skip function. "continue" tells to skip the rest
-/// of the code in the loop.
-#define header_skip(is_bt, len_min) \
- header(is_bt, len_min, continue)
-
-
-/// Calls hc_find_func() or bt_find_func() and calculates the total number
-/// of matches found. Updates the dictionary position and returns the number
-/// of matches found.
-#define call_find(func, len_best) \
-do { \
- matches_count = func(len_limit, pos, cur, cur_match, mf->depth, \
- mf->son, mf->cyclic_pos, mf->cyclic_size, \
- matches + matches_count, len_best) \
- - matches; \
- move_pos(mf); \
- return matches_count; \
-} while (0)
-
-
-////////////////
-// Hash Chain //
-////////////////
-
-#if defined(HAVE_MF_HC3) || defined(HAVE_MF_HC4)
-///
-///
-/// \param len_limit Don't look for matches longer than len_limit.
-/// \param pos lzma_mf.read_pos + lzma_mf.offset
-/// \param cur Pointer to current byte (mf_ptr(mf))
-/// \param cur_match Start position of the current match candidate
-/// \param depth Maximum length of the hash chain
-/// \param son lzma_mf.son (contains the hash chain)
-/// \param cyclic_pos
-/// \param cyclic_size
-/// \param matches Array to hold the matches.
-/// \param len_best The length of the longest match found so far.
-static lzma_match *
-hc_find_func(
- const uint32_t len_limit,
- const uint32_t pos,
- const uint8_t *const cur,
- uint32_t cur_match,
- uint32_t depth,
- uint32_t *const son,
- const uint32_t cyclic_pos,
- const uint32_t cyclic_size,
- lzma_match *matches,
- uint32_t len_best)
-{
- son[cyclic_pos] = cur_match;
-
- while (true) {
- const uint32_t delta = pos - cur_match;
- if (depth-- == 0 || delta >= cyclic_size)
- return matches;
-
- const uint8_t *const pb = cur - delta;
- cur_match = son[cyclic_pos - delta
- + (delta > cyclic_pos ? cyclic_size : 0)];
-
- if (pb[len_best] == cur[len_best] && pb[0] == cur[0]) {
- uint32_t len = lzma_memcmplen(pb, cur, 1, len_limit);
-
- if (len_best < len) {
- len_best = len;
- matches->len = len;
- matches->dist = delta - 1;
- ++matches;
-
- if (len == len_limit)
- return matches;
- }
- }
- }
-}
-
-
-#define hc_find(len_best) \
- call_find(hc_find_func, len_best)
-
-
-#define hc_skip() \
-do { \
- mf->son[mf->cyclic_pos] = cur_match; \
- move_pos(mf); \
-} while (0)
-
-#endif
-
-
-#ifdef HAVE_MF_HC3
-extern uint32_t
-lzma_mf_hc3_find(lzma_mf *mf, lzma_match *matches)
-{
- header_find(false, 3);
-
- hash_3_calc();
-
- const uint32_t delta2 = pos - mf->hash[hash_2_value];
- const uint32_t cur_match = mf->hash[FIX_3_HASH_SIZE + hash_value];
-
- mf->hash[hash_2_value] = pos;
- mf->hash[FIX_3_HASH_SIZE + hash_value] = pos;
-
- uint32_t len_best = 2;
-
- if (delta2 < mf->cyclic_size && *(cur - delta2) == *cur) {
- len_best = lzma_memcmplen(cur - delta2, cur,
- len_best, len_limit);
-
- matches[0].len = len_best;
- matches[0].dist = delta2 - 1;
- matches_count = 1;
-
- if (len_best == len_limit) {
- hc_skip();
- return 1; // matches_count
- }
- }
-
- hc_find(len_best);
-}
-
-
-extern void
-lzma_mf_hc3_skip(lzma_mf *mf, uint32_t amount)
-{
- do {
- if (mf_avail(mf) < 3) {
- move_pending(mf);
- continue;
- }
-
- const uint8_t *cur = mf_ptr(mf);
- const uint32_t pos = mf->read_pos + mf->offset;
-
- hash_3_calc();
-
- const uint32_t cur_match
- = mf->hash[FIX_3_HASH_SIZE + hash_value];
-
- mf->hash[hash_2_value] = pos;
- mf->hash[FIX_3_HASH_SIZE + hash_value] = pos;
-
- hc_skip();
-
- } while (--amount != 0);
-}
-#endif
-
-
-#ifdef HAVE_MF_HC4
-extern uint32_t
-lzma_mf_hc4_find(lzma_mf *mf, lzma_match *matches)
-{
- header_find(false, 4);
-
- hash_4_calc();
-
- uint32_t delta2 = pos - mf->hash[hash_2_value];
- const uint32_t delta3
- = pos - mf->hash[FIX_3_HASH_SIZE + hash_3_value];
- const uint32_t cur_match = mf->hash[FIX_4_HASH_SIZE + hash_value];
-
- mf->hash[hash_2_value ] = pos;
- mf->hash[FIX_3_HASH_SIZE + hash_3_value] = pos;
- mf->hash[FIX_4_HASH_SIZE + hash_value] = pos;
-
- uint32_t len_best = 1;
-
- if (delta2 < mf->cyclic_size && *(cur - delta2) == *cur) {
- len_best = 2;
- matches[0].len = 2;
- matches[0].dist = delta2 - 1;
- matches_count = 1;
- }
-
- if (delta2 != delta3 && delta3 < mf->cyclic_size
- && *(cur - delta3) == *cur) {
- len_best = 3;
- matches[matches_count++].dist = delta3 - 1;
- delta2 = delta3;
- }
-
- if (matches_count != 0) {
- len_best = lzma_memcmplen(cur - delta2, cur,
- len_best, len_limit);
-
- matches[matches_count - 1].len = len_best;
-
- if (len_best == len_limit) {
- hc_skip();
- return matches_count;
- }
- }
-
- if (len_best < 3)
- len_best = 3;
-
- hc_find(len_best);
-}
-
-
-extern void
-lzma_mf_hc4_skip(lzma_mf *mf, uint32_t amount)
-{
- do {
- if (mf_avail(mf) < 4) {
- move_pending(mf);
- continue;
- }
-
- const uint8_t *cur = mf_ptr(mf);
- const uint32_t pos = mf->read_pos + mf->offset;
-
- hash_4_calc();
-
- const uint32_t cur_match
- = mf->hash[FIX_4_HASH_SIZE + hash_value];
-
- mf->hash[hash_2_value] = pos;
- mf->hash[FIX_3_HASH_SIZE + hash_3_value] = pos;
- mf->hash[FIX_4_HASH_SIZE + hash_value] = pos;
-
- hc_skip();
-
- } while (--amount != 0);
-}
-#endif
-
-
-/////////////////
-// Binary Tree //
-/////////////////
-
-#if defined(HAVE_MF_BT2) || defined(HAVE_MF_BT3) || defined(HAVE_MF_BT4)
-static lzma_match *
-bt_find_func(
- const uint32_t len_limit,
- const uint32_t pos,
- const uint8_t *const cur,
- uint32_t cur_match,
- uint32_t depth,
- uint32_t *const son,
- const uint32_t cyclic_pos,
- const uint32_t cyclic_size,
- lzma_match *matches,
- uint32_t len_best)
-{
- uint32_t *ptr0 = son + (cyclic_pos << 1) + 1;
- uint32_t *ptr1 = son + (cyclic_pos << 1);
-
- uint32_t len0 = 0;
- uint32_t len1 = 0;
-
- while (true) {
- const uint32_t delta = pos - cur_match;
- if (depth-- == 0 || delta >= cyclic_size) {
- *ptr0 = EMPTY_HASH_VALUE;
- *ptr1 = EMPTY_HASH_VALUE;
- return matches;
- }
-
- uint32_t *const pair = son + ((cyclic_pos - delta
- + (delta > cyclic_pos ? cyclic_size : 0))
- << 1);
-
- const uint8_t *const pb = cur - delta;
- uint32_t len = my_min(len0, len1);
-
- if (pb[len] == cur[len]) {
- len = lzma_memcmplen(pb, cur, len + 1, len_limit);
-
- if (len_best < len) {
- len_best = len;
- matches->len = len;
- matches->dist = delta - 1;
- ++matches;
-
- if (len == len_limit) {
- *ptr1 = pair[0];
- *ptr0 = pair[1];
- return matches;
- }
- }
- }
-
- if (pb[len] < cur[len]) {
- *ptr1 = cur_match;
- ptr1 = pair + 1;
- cur_match = *ptr1;
- len1 = len;
- } else {
- *ptr0 = cur_match;
- ptr0 = pair;
- cur_match = *ptr0;
- len0 = len;
- }
- }
-}
-
-
-static void
-bt_skip_func(
- const uint32_t len_limit,
- const uint32_t pos,
- const uint8_t *const cur,
- uint32_t cur_match,
- uint32_t depth,
- uint32_t *const son,
- const uint32_t cyclic_pos,
- const uint32_t cyclic_size)
-{
- uint32_t *ptr0 = son + (cyclic_pos << 1) + 1;
- uint32_t *ptr1 = son + (cyclic_pos << 1);
-
- uint32_t len0 = 0;
- uint32_t len1 = 0;
-
- while (true) {
- const uint32_t delta = pos - cur_match;
- if (depth-- == 0 || delta >= cyclic_size) {
- *ptr0 = EMPTY_HASH_VALUE;
- *ptr1 = EMPTY_HASH_VALUE;
- return;
- }
-
- uint32_t *pair = son + ((cyclic_pos - delta
- + (delta > cyclic_pos ? cyclic_size : 0))
- << 1);
- const uint8_t *pb = cur - delta;
- uint32_t len = my_min(len0, len1);
-
- if (pb[len] == cur[len]) {
- len = lzma_memcmplen(pb, cur, len + 1, len_limit);
-
- if (len == len_limit) {
- *ptr1 = pair[0];
- *ptr0 = pair[1];
- return;
- }
- }
-
- if (pb[len] < cur[len]) {
- *ptr1 = cur_match;
- ptr1 = pair + 1;
- cur_match = *ptr1;
- len1 = len;
- } else {
- *ptr0 = cur_match;
- ptr0 = pair;
- cur_match = *ptr0;
- len0 = len;
- }
- }
-}
-
-
-#define bt_find(len_best) \
- call_find(bt_find_func, len_best)
-
-#define bt_skip() \
-do { \
- bt_skip_func(len_limit, pos, cur, cur_match, mf->depth, \
- mf->son, mf->cyclic_pos, \
- mf->cyclic_size); \
- move_pos(mf); \
-} while (0)
-
-#endif
-
-
-#ifdef HAVE_MF_BT2
-extern uint32_t
-lzma_mf_bt2_find(lzma_mf *mf, lzma_match *matches)
-{
- header_find(true, 2);
-
- hash_2_calc();
-
- const uint32_t cur_match = mf->hash[hash_value];
- mf->hash[hash_value] = pos;
-
- bt_find(1);
-}
-
-
-extern void
-lzma_mf_bt2_skip(lzma_mf *mf, uint32_t amount)
-{
- do {
- header_skip(true, 2);
-
- hash_2_calc();
-
- const uint32_t cur_match = mf->hash[hash_value];
- mf->hash[hash_value] = pos;
-
- bt_skip();
-
- } while (--amount != 0);
-}
-#endif
-
-
-#ifdef HAVE_MF_BT3
-extern uint32_t
-lzma_mf_bt3_find(lzma_mf *mf, lzma_match *matches)
-{
- header_find(true, 3);
-
- hash_3_calc();
-
- const uint32_t delta2 = pos - mf->hash[hash_2_value];
- const uint32_t cur_match = mf->hash[FIX_3_HASH_SIZE + hash_value];
-
- mf->hash[hash_2_value] = pos;
- mf->hash[FIX_3_HASH_SIZE + hash_value] = pos;
-
- uint32_t len_best = 2;
-
- if (delta2 < mf->cyclic_size && *(cur - delta2) == *cur) {
- len_best = lzma_memcmplen(
- cur, cur - delta2, len_best, len_limit);
-
- matches[0].len = len_best;
- matches[0].dist = delta2 - 1;
- matches_count = 1;
-
- if (len_best == len_limit) {
- bt_skip();
- return 1; // matches_count
- }
- }
-
- bt_find(len_best);
-}
-
-
-extern void
-lzma_mf_bt3_skip(lzma_mf *mf, uint32_t amount)
-{
- do {
- header_skip(true, 3);
-
- hash_3_calc();
-
- const uint32_t cur_match
- = mf->hash[FIX_3_HASH_SIZE + hash_value];
-
- mf->hash[hash_2_value] = pos;
- mf->hash[FIX_3_HASH_SIZE + hash_value] = pos;
-
- bt_skip();
-
- } while (--amount != 0);
-}
-#endif
-
-
-#ifdef HAVE_MF_BT4
-extern uint32_t
-lzma_mf_bt4_find(lzma_mf *mf, lzma_match *matches)
-{
- header_find(true, 4);
-
- hash_4_calc();
-
- uint32_t delta2 = pos - mf->hash[hash_2_value];
- const uint32_t delta3
- = pos - mf->hash[FIX_3_HASH_SIZE + hash_3_value];
- const uint32_t cur_match = mf->hash[FIX_4_HASH_SIZE + hash_value];
-
- mf->hash[hash_2_value] = pos;
- mf->hash[FIX_3_HASH_SIZE + hash_3_value] = pos;
- mf->hash[FIX_4_HASH_SIZE + hash_value] = pos;
-
- uint32_t len_best = 1;
-
- if (delta2 < mf->cyclic_size && *(cur - delta2) == *cur) {
- len_best = 2;
- matches[0].len = 2;
- matches[0].dist = delta2 - 1;
- matches_count = 1;
- }
-
- if (delta2 != delta3 && delta3 < mf->cyclic_size
- && *(cur - delta3) == *cur) {
- len_best = 3;
- matches[matches_count++].dist = delta3 - 1;
- delta2 = delta3;
- }
-
- if (matches_count != 0) {
- len_best = lzma_memcmplen(
- cur, cur - delta2, len_best, len_limit);
-
- matches[matches_count - 1].len = len_best;
-
- if (len_best == len_limit) {
- bt_skip();
- return matches_count;
- }
- }
-
- if (len_best < 3)
- len_best = 3;
-
- bt_find(len_best);
-}
-
-
-extern void
-lzma_mf_bt4_skip(lzma_mf *mf, uint32_t amount)
-{
- do {
- header_skip(true, 4);
-
- hash_4_calc();
-
- const uint32_t cur_match
- = mf->hash[FIX_4_HASH_SIZE + hash_value];
-
- mf->hash[hash_2_value] = pos;
- mf->hash[FIX_3_HASH_SIZE + hash_3_value] = pos;
- mf->hash[FIX_4_HASH_SIZE + hash_value] = pos;
-
- bt_skip();
-
- } while (--amount != 0);
-}
-#endif