Adding upstream version 5.6.1+really5.4.5.upstream/5.6.1+really5.4.5

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

8 files changed, 2456 insertions, 0 deletions

diff --git a/src/liblzma/lz/Makefile.inc b/src/liblzma/lz/Makefile.inc
new file mode 100644
index 0000000..75742a8
--- /dev/null
+++ b/src/liblzma/lz/Makefile.inc
@@ -0,0 +1,22 @@
+##
+## Author: Lasse Collin
+##
+## This file has been put into the public domain.
+## You can do whatever you want with this file.
+##
+
+if COND_ENCODER_LZ
+liblzma_la_SOURCES += \
+	lz/lz_encoder.c \
+	lz/lz_encoder.h \
+	lz/lz_encoder_hash.h \
+	lz/lz_encoder_hash_table.h \
+	lz/lz_encoder_mf.c
+endif
+
+
+if COND_DECODER_LZ
+liblzma_la_SOURCES += \
+	lz/lz_decoder.c \
+	lz/lz_decoder.h
+endif
diff --git a/src/liblzma/lz/lz_decoder.c b/src/liblzma/lz/lz_decoder.c
new file mode 100644
index 0000000..06c95c1
--- /dev/null
+++ b/src/liblzma/lz/lz_decoder.c
@@ -0,0 +1,304 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \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,
+			lzma_vli id, 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].id, 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);
+}
diff --git a/src/liblzma/lz/lz_decoder.h b/src/liblzma/lz/lz_decoder.h
new file mode 100644
index 0000000..ad80d4d
--- /dev/null
+++ b/src/liblzma/lz/lz_decoder.h
@@ -0,0 +1,234 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \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. If uncompressed_size == LZMA_VLI_UNKNOWN
+	/// then allow_eopm will always be true.
+	void (*set_uncompressed)(void *coder, lzma_vli uncompressed_size,
+			bool allow_eopm);
+
+	/// 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,
+			lzma_vli id, const void *options,
+			lzma_lz_options *lz_options));
+
+extern uint64_t lzma_lz_decoder_memusage(size_t dictionary_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/src/liblzma/lz/lz_encoder.c b/src/liblzma/lz/lz_encoder.c
new file mode 100644
index 0000000..5489085
--- /dev/null
+++ b/src/liblzma/lz/lz_encoder.c
@@ -0,0 +1,633 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \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)
+#	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.
+	//
+	// NOTE: Since 5.3.5beta the LZMA encoder ensures that nice_len
+	// is big enough for the selected match finder. This makes it
+	// easier for applications as nice_len = 2 will always be accepted
+	// even though the effective value can be slightly bigger.
+	const uint32_t hash_bytes
+			= mf_get_hash_bytes(lz_options->match_finder);
+	assert(hash_bytes <= mf->nice_len);
+
+	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);
+}
+
+
+static lzma_ret
+lz_encoder_set_out_limit(void *coder_ptr, uint64_t *uncomp_size,
+		uint64_t out_limit)
+{
+	lzma_coder *coder = coder_ptr;
+
+	// This is supported only if there are no other filters chained.
+	if (coder->next.code == NULL && coder->lz.set_out_limit != NULL)
+		return coder->lz.set_out_limit(
+				coder->lz.coder, uncomp_size, out_limit);
+
+	return LZMA_OPTIONS_ERROR;
+}
+
+
+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,
+			lzma_vli id, const void *options,
+			lzma_lz_options *lz_options))
+{
+#if defined(HAVE_SMALL) && !defined(HAVE_FUNC_ATTRIBUTE_CONSTRUCTOR)
+	// 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;
+		next->set_out_limit = &lz_encoder_set_out_limit;
+
+		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].id, 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)
+{
+	switch (mf) {
+#ifdef HAVE_MF_HC3
+	case LZMA_MF_HC3:
+		return true;
+#endif
+#ifdef HAVE_MF_HC4
+	case LZMA_MF_HC4:
+		return true;
+#endif
+#ifdef HAVE_MF_BT2
+	case LZMA_MF_BT2:
+		return true;
+#endif
+#ifdef HAVE_MF_BT3
+	case LZMA_MF_BT3:
+		return true;
+#endif
+#ifdef HAVE_MF_BT4
+	case LZMA_MF_BT4:
+		return true;
+#endif
+	default:
+		return false;
+	}
+}
diff --git a/src/liblzma/lz/lz_encoder.h b/src/liblzma/lz/lz_encoder.h
new file mode 100644
index 0000000..ffcba02
--- /dev/null
+++ b/src/liblzma/lz/lz_encoder.h
@@ -0,0 +1,341 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \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 incompressible, 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);
+
+	/// Set maximum allowed output size
+	lzma_ret (*set_out_limit)(void *coder, uint64_t *uncomp_size,
+			uint64_t out_limit);
+
+} 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 how many bytes the match finder hashes in its initial step.
+/// This is also the minimum nice_len value with the match finder.
+static inline uint32_t
+mf_get_hash_bytes(lzma_match_finder match_finder)
+{
+	return (uint32_t)match_finder & 0x0F;
+}
+
+
+/// 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,
+			lzma_vli id, 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/src/liblzma/lz/lz_encoder_hash.h b/src/liblzma/lz/lz_encoder_hash.h
new file mode 100644
index 0000000..4d9971a
--- /dev/null
+++ b/src/liblzma/lz/lz_encoder_hash.h
@@ -0,0 +1,109 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \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.
+	lzma_attr_visibility_hidden
+	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/src/liblzma/lz/lz_encoder_hash_table.h b/src/liblzma/lz/lz_encoder_hash_table.h
new file mode 100644
index 0000000..8c51717
--- /dev/null
+++ b/src/liblzma/lz/lz_encoder_hash_table.h
@@ -0,0 +1,68 @@
+/* This file has been automatically generated by crc32_tablegen.c. */
+
+const uint32_t lzma_lz_hash_table[256] = {
+	0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA,
+	0x076DC419, 0x706AF48F, 0xE963A535, 0x9E6495A3,
+	0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988,
+	0x09B64C2B, 0x7EB17CBD, 0xE7B82D07, 0x90BF1D91,
+	0x1DB71064, 0x6AB020F2, 0xF3B97148, 0x84BE41DE,
+	0x1ADAD47D, 0x6DDDE4EB, 0xF4D4B551, 0x83D385C7,
+	0x136C9856, 0x646BA8C0, 0xFD62F97A, 0x8A65C9EC,
+	0x14015C4F, 0x63066CD9, 0xFA0F3D63, 0x8D080DF5,
+	0x3B6E20C8, 0x4C69105E, 0xD56041E4, 0xA2677172,
+	0x3C03E4D1, 0x4B04D447, 0xD20D85FD, 0xA50AB56B,
+	0x35B5A8FA, 0x42B2986C, 0xDBBBC9D6, 0xACBCF940,
+	0x32D86CE3, 0x45DF5C75, 0xDCD60DCF, 0xABD13D59,
+	0x26D930AC, 0x51DE003A, 0xC8D75180, 0xBFD06116,
+	0x21B4F4B5, 0x56B3C423, 0xCFBA9599, 0xB8BDA50F,
+	0x2802B89E, 0x5F058808, 0xC60CD9B2, 0xB10BE924,
+	0x2F6F7C87, 0x58684C11, 0xC1611DAB, 0xB6662D3D,
+	0x76DC4190, 0x01DB7106, 0x98D220BC, 0xEFD5102A,
+	0x71B18589, 0x06B6B51F, 0x9FBFE4A5, 0xE8B8D433,
+	0x7807C9A2, 0x0F00F934, 0x9609A88E, 0xE10E9818,
+	0x7F6A0DBB, 0x086D3D2D, 0x91646C97, 0xE6635C01,
+	0x6B6B51F4, 0x1C6C6162, 0x856530D8, 0xF262004E,
+	0x6C0695ED, 0x1B01A57B, 0x8208F4C1, 0xF50FC457,
+	0x65B0D9C6, 0x12B7E950, 0x8BBEB8EA, 0xFCB9887C,
+	0x62DD1DDF, 0x15DA2D49, 0x8CD37CF3, 0xFBD44C65,
+	0x4DB26158, 0x3AB551CE, 0xA3BC0074, 0xD4BB30E2,
+	0x4ADFA541, 0x3DD895D7, 0xA4D1C46D, 0xD3D6F4FB,
+	0x4369E96A, 0x346ED9FC, 0xAD678846, 0xDA60B8D0,
+	0x44042D73, 0x33031DE5, 0xAA0A4C5F, 0xDD0D7CC9,
+	0x5005713C, 0x270241AA, 0xBE0B1010, 0xC90C2086,
+	0x5768B525, 0x206F85B3, 0xB966D409, 0xCE61E49F,
+	0x5EDEF90E, 0x29D9C998, 0xB0D09822, 0xC7D7A8B4,
+	0x59B33D17, 0x2EB40D81, 0xB7BD5C3B, 0xC0BA6CAD,
+	0xEDB88320, 0x9ABFB3B6, 0x03B6E20C, 0x74B1D29A,
+	0xEAD54739, 0x9DD277AF, 0x04DB2615, 0x73DC1683,
+	0xE3630B12, 0x94643B84, 0x0D6D6A3E, 0x7A6A5AA8,
+	0xE40ECF0B, 0x9309FF9D, 0x0A00AE27, 0x7D079EB1,
+	0xF00F9344, 0x8708A3D2, 0x1E01F268, 0x6906C2FE,
+	0xF762575D, 0x806567CB, 0x196C3671, 0x6E6B06E7,
+	0xFED41B76, 0x89D32BE0, 0x10DA7A5A, 0x67DD4ACC,
+	0xF9B9DF6F, 0x8EBEEFF9, 0x17B7BE43, 0x60B08ED5,
+	0xD6D6A3E8, 0xA1D1937E, 0x38D8C2C4, 0x4FDFF252,
+	0xD1BB67F1, 0xA6BC5767, 0x3FB506DD, 0x48B2364B,
+	0xD80D2BDA, 0xAF0A1B4C, 0x36034AF6, 0x41047A60,
+	0xDF60EFC3, 0xA867DF55, 0x316E8EEF, 0x4669BE79,
+	0xCB61B38C, 0xBC66831A, 0x256FD2A0, 0x5268E236,
+	0xCC0C7795, 0xBB0B4703, 0x220216B9, 0x5505262F,
+	0xC5BA3BBE, 0xB2BD0B28, 0x2BB45A92, 0x5CB36A04,
+	0xC2D7FFA7, 0xB5D0CF31, 0x2CD99E8B, 0x5BDEAE1D,
+	0x9B64C2B0, 0xEC63F226, 0x756AA39C, 0x026D930A,
+	0x9C0906A9, 0xEB0E363F, 0x72076785, 0x05005713,
+	0x95BF4A82, 0xE2B87A14, 0x7BB12BAE, 0x0CB61B38,
+	0x92D28E9B, 0xE5D5BE0D, 0x7CDCEFB7, 0x0BDBDF21,
+	0x86D3D2D4, 0xF1D4E242, 0x68DDB3F8, 0x1FDA836E,
+	0x81BE16CD, 0xF6B9265B, 0x6FB077E1, 0x18B74777,
+	0x88085AE6, 0xFF0F6A70, 0x66063BCA, 0x11010B5C,
+	0x8F659EFF, 0xF862AE69, 0x616BFFD3, 0x166CCF45,
+	0xA00AE278, 0xD70DD2EE, 0x4E048354, 0x3903B3C2,
+	0xA7672661, 0xD06016F7, 0x4969474D, 0x3E6E77DB,
+	0xAED16A4A, 0xD9D65ADC, 0x40DF0B66, 0x37D83BF0,
+	0xA9BCAE53, 0xDEBB9EC5, 0x47B2CF7F, 0x30B5FFE9,
+	0xBDBDF21C, 0xCABAC28A, 0x53B39330, 0x24B4A3A6,
+	0xBAD03605, 0xCDD70693, 0x54DE5729, 0x23D967BF,
+	0xB3667A2E, 0xC4614AB8, 0x5D681B02, 0x2A6F2B94,
+	0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D
+};
diff --git a/src/liblzma/lz/lz_encoder_mf.c b/src/liblzma/lz/lz_encoder_mf.c
new file mode 100644
index 0000000..1fdc2d7
--- /dev/null
+++ b/src/liblzma/lz/lz_encoder_mf.c
@@ -0,0 +1,745 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \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 = (uint32_t)(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      lzma_mf.cyclic_pos
+/// \param      cyclic_size     lzma_mf_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