diff options
author | thegeorg <thegeorg@yandex-team.ru> | 2022-05-07 11:12:39 +0300 |
---|---|---|
committer | thegeorg <thegeorg@yandex-team.ru> | 2022-05-07 11:12:39 +0300 |
commit | a0c9cd069ff45244eeb9caa2fcadf1e9bc4a840d (patch) | |
tree | c9a178299041ce75a8b6d3edb644521c0f13c092 /contrib/libs/xz/liblzma/lz | |
parent | d47cdd245c4b49c8e273c80a2e2b29ee5b2071c3 (diff) | |
download | ydb-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.c | 311 | ||||
-rw-r--r-- | contrib/libs/xz/liblzma/lz/lz_decoder.h | 234 | ||||
-rw-r--r-- | contrib/libs/xz/liblzma/lz/lz_encoder.c | 616 | ||||
-rw-r--r-- | contrib/libs/xz/liblzma/lz/lz_encoder.h | 327 | ||||
-rw-r--r-- | contrib/libs/xz/liblzma/lz/lz_encoder_hash.h | 108 | ||||
-rw-r--r-- | contrib/libs/xz/liblzma/lz/lz_encoder_mf.c | 744 |
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 |