Imported to git.

33 files changed, 5513 insertions, 0 deletions

diff --git a/src/liblzma/lz/Makefile.am b/src/liblzma/lz/Makefile.am
new file mode 100644
index 00000000..5c27e2f2
--- /dev/null
+++ b/src/liblzma/lz/Makefile.am
@@ -0,0 +1,63 @@
+##
+##  Copyright (C) 2007 Lasse Collin
+##
+##  This library is free software; you can redistribute it and/or
+##  modify it under the terms of the GNU Lesser General Public
+##  License as published by the Free Software Foundation; either
+##  version 2.1 of the License, or (at your option) any later version.
+##
+##  This library is distributed in the hope that it will be useful,
+##  but WITHOUT ANY WARRANTY; without even the implied warranty of
+##  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+##  Lesser General Public License for more details.
+##
+
+noinst_LTLIBRARIES = liblz.la
+liblz_la_CPPFLAGS = \
+	-I@top_srcdir@/src/liblzma/api \
+	-I@top_srcdir@/src/liblzma/common \
+	-I@top_srcdir@/src/liblzma/check
+liblz_la_SOURCES =
+
+
+if COND_MAIN_ENCODER
+liblz_la_SOURCES += \
+	lz_encoder.c \
+	lz_encoder.h \
+	lz_encoder_private.h \
+	match_c.h \
+	match_h.h
+
+if COND_MF_HC3
+liblz_la_SOURCES += hc3.c hc3.h
+liblz_la_CPPFLAGS += -DHAVE_HC3
+endif
+
+if COND_MF_HC4
+liblz_la_SOURCES += hc4.c hc4.h
+liblz_la_CPPFLAGS += -DHAVE_HC4
+endif
+
+if COND_MF_BT2
+liblz_la_SOURCES += bt2.c bt2.h
+liblz_la_CPPFLAGS += -DHAVE_BT2
+endif
+
+if COND_MF_BT3
+liblz_la_SOURCES += bt3.c bt3.h
+liblz_la_CPPFLAGS += -DHAVE_BT3
+endif
+
+if COND_MF_BT4
+liblz_la_SOURCES += bt4.c bt4.h
+liblz_la_CPPFLAGS += -DHAVE_BT4
+endif
+
+endif
+
+
+if COND_MAIN_DECODER
+liblz_la_SOURCES += \
+	lz_decoder.c \
+	lz_decoder.h
+endif
diff --git a/src/liblzma/lz/bt2.c b/src/liblzma/lz/bt2.c
new file mode 100644
index 00000000..7dc4cb80
--- /dev/null
+++ b/src/liblzma/lz/bt2.c
@@ -0,0 +1,27 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       bt2.c
+/// \brief      Binary Tree 2
+//
+//  Copyright (C) 1999-2006 Igor Pavlov
+//  Copyright (C) 2007 Lasse Collin
+//
+//  This library is free software; you can redistribute it and/or
+//  modify it under the terms of the GNU Lesser General Public
+//  License as published by the Free Software Foundation; either
+//  version 2.1 of the License, or (at your option) any later version.
+//
+//  This library is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+//  Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include "bt2.h"
+
+#undef IS_HASH_CHAIN
+#undef HASH_ARRAY_2
+#undef HASH_ARRAY_3
+
+#include "match_c.h"
diff --git a/src/liblzma/lz/bt2.h b/src/liblzma/lz/bt2.h
new file mode 100644
index 00000000..33cb52cd
--- /dev/null
+++ b/src/liblzma/lz/bt2.h
@@ -0,0 +1,31 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       bt2.h
+/// \brief      Binary Tree 2
+//
+//  Copyright (C) 1999-2006 Igor Pavlov
+//  Copyright (C) 2007 Lasse Collin
+//
+//  This library is free software; you can redistribute it and/or
+//  modify it under the terms of the GNU Lesser General Public
+//  License as published by the Free Software Foundation; either
+//  version 2.1 of the License, or (at your option) any later version.
+//
+//  This library is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+//  Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#ifndef LZMA_BT2_H
+#define LZMA_BT2_H
+
+#undef LZMA_MATCH_FINDER_NAME_LOWER
+#undef LZMA_MATCH_FINDER_NAME_UPPER
+#define LZMA_MATCH_FINDER_NAME_LOWER bt2
+#define LZMA_MATCH_FINDER_NAME_UPPER BT2
+
+#include "match_h.h"
+
+#endif
diff --git a/src/liblzma/lz/bt3.c b/src/liblzma/lz/bt3.c
new file mode 100644
index 00000000..d44310f3
--- /dev/null
+++ b/src/liblzma/lz/bt3.c
@@ -0,0 +1,29 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       bt3.c
+/// \brief      Binary Tree 3
+//
+//  Copyright (C) 1999-2006 Igor Pavlov
+//  Copyright (C) 2007 Lasse Collin
+//
+//  This library is free software; you can redistribute it and/or
+//  modify it under the terms of the GNU Lesser General Public
+//  License as published by the Free Software Foundation; either
+//  version 2.1 of the License, or (at your option) any later version.
+//
+//  This library is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+//  Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include "bt3.h"
+
+#undef IS_HASH_CHAIN
+#undef HASH_ARRAY_2
+#undef HASH_ARRAY_3
+
+#define HASH_ARRAY_2
+
+#include "match_c.h"
diff --git a/src/liblzma/lz/bt3.h b/src/liblzma/lz/bt3.h
new file mode 100644
index 00000000..247c7e5f
--- /dev/null
+++ b/src/liblzma/lz/bt3.h
@@ -0,0 +1,31 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       bt3.h
+/// \brief      Binary Tree 3
+//
+//  Copyright (C) 1999-2006 Igor Pavlov
+//  Copyright (C) 2007 Lasse Collin
+//
+//  This library is free software; you can redistribute it and/or
+//  modify it under the terms of the GNU Lesser General Public
+//  License as published by the Free Software Foundation; either
+//  version 2.1 of the License, or (at your option) any later version.
+//
+//  This library is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+//  Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#ifndef LZMA_BT3_H
+#define LZMA_BT3_H
+
+#undef LZMA_MATCH_FINDER_NAME_LOWER
+#undef LZMA_MATCH_FINDER_NAME_UPPER
+#define LZMA_MATCH_FINDER_NAME_LOWER bt3
+#define LZMA_MATCH_FINDER_NAME_UPPER BT3
+
+#include "match_h.h"
+
+#endif
diff --git a/src/liblzma/lz/bt4.c b/src/liblzma/lz/bt4.c
new file mode 100644
index 00000000..6e1042c9
--- /dev/null
+++ b/src/liblzma/lz/bt4.c
@@ -0,0 +1,30 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       bt4.c
+/// \brief      Binary Tree 4
+//
+//  Copyright (C) 1999-2006 Igor Pavlov
+//  Copyright (C) 2007 Lasse Collin
+//
+//  This library is free software; you can redistribute it and/or
+//  modify it under the terms of the GNU Lesser General Public
+//  License as published by the Free Software Foundation; either
+//  version 2.1 of the License, or (at your option) any later version.
+//
+//  This library is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+//  Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include "bt4.h"
+
+#undef IS_HASH_CHAIN
+#undef HASH_ARRAY_2
+#undef HASH_ARRAY_3
+
+#define HASH_ARRAY_2
+#define HASH_ARRAY_3
+
+#include "match_c.h"
diff --git a/src/liblzma/lz/bt4.h b/src/liblzma/lz/bt4.h
new file mode 100644
index 00000000..e3fcf6ac
--- /dev/null
+++ b/src/liblzma/lz/bt4.h
@@ -0,0 +1,31 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       bt4.h
+/// \brief      Binary Tree 4
+//
+//  Copyright (C) 1999-2006 Igor Pavlov
+//  Copyright (C) 2007 Lasse Collin
+//
+//  This library is free software; you can redistribute it and/or
+//  modify it under the terms of the GNU Lesser General Public
+//  License as published by the Free Software Foundation; either
+//  version 2.1 of the License, or (at your option) any later version.
+//
+//  This library is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+//  Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#ifndef LZMA_BT4_H
+#define LZMA_BT4_H
+
+#undef LZMA_MATCH_FINDER_NAME_LOWER
+#undef LZMA_MATCH_FINDER_NAME_UPPER
+#define LZMA_MATCH_FINDER_NAME_LOWER bt4
+#define LZMA_MATCH_FINDER_NAME_UPPER BT4
+
+#include "match_h.h"
+
+#endif
diff --git a/src/liblzma/lz/hc3.c b/src/liblzma/lz/hc3.c
new file mode 100644
index 00000000..22b5689b
--- /dev/null
+++ b/src/liblzma/lz/hc3.c
@@ -0,0 +1,30 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       hc3.c
+/// \brief      Hash Chain 3
+//
+//  Copyright (C) 1999-2006 Igor Pavlov
+//  Copyright (C) 2007 Lasse Collin
+//
+//  This library is free software; you can redistribute it and/or
+//  modify it under the terms of the GNU Lesser General Public
+//  License as published by the Free Software Foundation; either
+//  version 2.1 of the License, or (at your option) any later version.
+//
+//  This library is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+//  Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include "hc3.h"
+
+#undef IS_HASH_CHAIN
+#undef HASH_ARRAY_2
+#undef HASH_ARRAY_3
+
+#define IS_HASH_CHAIN
+#define HASH_ARRAY_2
+
+#include "match_c.h"
diff --git a/src/liblzma/lz/hc3.h b/src/liblzma/lz/hc3.h
new file mode 100644
index 00000000..97be0b1d
--- /dev/null
+++ b/src/liblzma/lz/hc3.h
@@ -0,0 +1,31 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       hc3.h
+/// \brief      Hash Chain 3
+//
+//  Copyright (C) 1999-2006 Igor Pavlov
+//  Copyright (C) 2007 Lasse Collin
+//
+//  This library is free software; you can redistribute it and/or
+//  modify it under the terms of the GNU Lesser General Public
+//  License as published by the Free Software Foundation; either
+//  version 2.1 of the License, or (at your option) any later version.
+//
+//  This library is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+//  Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#ifndef LZMA_HC3_H
+#define LZMA_HC3_H
+
+#undef LZMA_MATCH_FINDER_NAME_LOWER
+#undef LZMA_MATCH_FINDER_NAME_UPPER
+#define LZMA_MATCH_FINDER_NAME_LOWER hc3
+#define LZMA_MATCH_FINDER_NAME_UPPER HC3
+
+#include "match_h.h"
+
+#endif
diff --git a/src/liblzma/lz/hc4.c b/src/liblzma/lz/hc4.c
new file mode 100644
index 00000000..a55cfd09
--- /dev/null
+++ b/src/liblzma/lz/hc4.c
@@ -0,0 +1,31 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       hc4.c
+/// \brief      Hash Chain 4
+//
+//  Copyright (C) 1999-2006 Igor Pavlov
+//  Copyright (C) 2007 Lasse Collin
+//
+//  This library is free software; you can redistribute it and/or
+//  modify it under the terms of the GNU Lesser General Public
+//  License as published by the Free Software Foundation; either
+//  version 2.1 of the License, or (at your option) any later version.
+//
+//  This library is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+//  Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include "hc4.h"
+
+#undef IS_HASH_CHAIN
+#undef HASH_ARRAY_2
+#undef HASH_ARRAY_3
+
+#define IS_HASH_CHAIN
+#define HASH_ARRAY_2
+#define HASH_ARRAY_3
+
+#include "match_c.h"
diff --git a/src/liblzma/lz/hc4.h b/src/liblzma/lz/hc4.h
new file mode 100644
index 00000000..dc072e2f
--- /dev/null
+++ b/src/liblzma/lz/hc4.h
@@ -0,0 +1,31 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       hc4.h
+/// \brief      Hash Chain 4
+//
+//  Copyright (C) 1999-2006 Igor Pavlov
+//  Copyright (C) 2007 Lasse Collin
+//
+//  This library is free software; you can redistribute it and/or
+//  modify it under the terms of the GNU Lesser General Public
+//  License as published by the Free Software Foundation; either
+//  version 2.1 of the License, or (at your option) any later version.
+//
+//  This library is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+//  Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#ifndef LZMA_HC4_H
+#define LZMA_HC4_H
+
+#undef LZMA_MATCH_FINDER_NAME_LOWER
+#undef LZMA_MATCH_FINDER_NAME_UPPER
+#define LZMA_MATCH_FINDER_NAME_LOWER hc4
+#define LZMA_MATCH_FINDER_NAME_UPPER HC4
+
+#include "match_h.h"
+
+#endif
diff --git a/src/liblzma/lz/lz_decoder.c b/src/liblzma/lz/lz_decoder.c
new file mode 100644
index 00000000..9c110dec
--- /dev/null
+++ b/src/liblzma/lz/lz_decoder.c
@@ -0,0 +1,462 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       lz_decoder.c
+/// \brief      LZ out window
+//
+//  Copyright (C) 1999-2006 Igor Pavlov
+//  Copyright (C) 2007 Lasse Collin
+//
+//  This library is free software; you can redistribute it and/or
+//  modify it under the terms of the GNU Lesser General Public
+//  License as published by the Free Software Foundation; either
+//  version 2.1 of the License, or (at your option) any later version.
+//
+//  This library is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+//  Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include "lz_decoder.h"
+
+
+/// Minimum size of allocated dictionary
+#define DICT_SIZE_MIN 8192
+
+/// When there is less than this amount of data available for decoding,
+/// it is moved to the temporary buffer which
+///   - protects from reads past the end of the buffer; and
+///   - stored the incomplete data between lzma_code() calls.
+///
+/// \note       TEMP_LIMIT must be at least as much as
+///             REQUIRED_IN_BUFFER_SIZE defined in lzma_decoder.c.
+#define TEMP_LIMIT 32
+
+// lzma_lz_decoder.dict[] must be three times the size of TEMP_LIMIT.
+// 2 * TEMP_LIMIT is used for the actual data, and the third TEMP_LIMIT
+// bytes is needed for safety to allow decode_dummy() in lzma_decoder.c
+// to read past end of the buffer. This way it should be both fast and simple.
+#if LZMA_BUFFER_SIZE < 3 * TEMP_LIMIT
+#	error LZMA_BUFFER_SIZE < 3 * TEMP_LIMIT
+#endif
+
+
+struct lzma_coder_s {
+	lzma_next_coder next;
+	lzma_lz_decoder lz;
+
+	// There are more members in this structure but they are not
+	// visible in LZ coder.
+};
+
+
+/// - Copy as much data as possible from lz->dict[] to out[].
+/// - Update *out_pos, lz->start, and lz->end accordingly.
+/// - Wrap lz-pos to the beginning of lz->dict[] if there is a danger that
+///   it may go past the end of the buffer (lz->pos >= lz->must_flush_pos).
+static inline bool
+flush(lzma_lz_decoder *restrict lz, uint8_t *restrict out,
+		size_t *restrict out_pos, size_t out_size)
+{
+	// Flush uncompressed data from the history buffer to
+	// the output buffer. This is done in two phases.
+
+	assert(lz->start <= lz->end);
+
+	// Flush if pos < start < end.
+	if (lz->pos < lz->start && lz->start < lz->end) {
+		bufcpy(lz->dict, &lz->start, lz->end, out, out_pos, out_size);
+
+		// If we reached end of the data in history buffer,
+		// wrap to the beginning.
+		if (lz->start == lz->end)
+			lz->start = 0;
+	}
+
+	// Flush if start start < pos <= end. This is not as `else' for
+	// previous `if' because the previous one may make this one true.
+	if (lz->start < lz->pos) {
+		bufcpy(lz->dict, &lz->start,
+				lz->pos, out, out_pos, out_size);
+
+		if (lz->pos >= lz->must_flush_pos) {
+			// Wrap the flushing position if we have
+			// flushed the whole history buffer.
+			if (lz->pos == lz->start)
+				lz->start = 0;
+
+			// Wrap the write position and store to lz.end
+			// how much there is new data available.
+			lz->end = lz->pos;
+			lz->pos = 0;
+			lz->is_full = true;
+		}
+	}
+
+	assert(lz->pos < lz->must_flush_pos);
+
+	return *out_pos == out_size;
+}
+
+
+/// Calculate safe value for lz->limit. If no safe value can be found,
+/// set lz->limit to zero. When flushing, only as little data will be
+/// decoded as is needed to fill the output buffer (lowers both latency
+/// and throughput).
+///
+/// \return     true if there is no space for new uncompressed data.
+///
+static inline bool
+set_limit(lzma_lz_decoder *lz, size_t out_avail, bool flushing)
+{
+	// Set the limit so that writing to dict[limit + match_max_len - 1]
+	// doesn't overwrite any unflushed data and doesn't write past the
+	// end of the dict buffer.
+	if (lz->start <= lz->pos) {
+		// We can fill the buffer from pos till the end
+		// of the dict buffer.
+		lz->limit = lz->must_flush_pos;
+	} else if (lz->pos + lz->match_max_len < lz->start) {
+		// There's some unflushed data between pos and end of the
+		// buffer. Limit so that we don't overwrite the unflushed data.
+		lz->limit = lz->start - lz->match_max_len;
+	} else {
+		// Buffer is too full.
+		lz->limit = 0;
+		return true;
+	}
+
+	// Finetune the limit a bit if it isn't zero.
+
+	assert(lz->limit > lz->pos);
+	const size_t dict_avail = lz->limit - lz->pos;
+
+	if (lz->uncompressed_size < dict_avail) {
+		// Finishing a stream that doesn't have
+		// an end of stream marker.
+		lz->limit = lz->pos + lz->uncompressed_size;
+
+	} else if (flushing && out_avail < dict_avail) {
+		// Flushing enabled, decoding only as little as needed to
+		// fill the out buffer (if there's enough input, of course).
+		lz->limit = lz->pos + out_avail;
+	}
+
+	return lz->limit == lz->pos;
+}
+
+
+/// Takes care of wrapping the data into temporary buffer when needed,
+/// and calls the actual decoder.
+///
+/// \return     true if error occurred
+///
+static inline bool
+call_process(lzma_coder *restrict coder, const uint8_t *restrict in,
+		size_t *restrict in_pos, size_t in_size)
+{
+	// It would be nice and simple if we could just give in[] to the
+	// decoder, but the requirement of zlib-like API forces us to be
+	// able to make *in_pos == in_size whenever there is enough output
+	// space. If needed, we will append a few bytes from in[] to
+	// a temporary buffer and decode enough to reach the part that
+	// was copied from in[]. Then we can continue with the real in[].
+
+	bool error;
+	const size_t dict_old_pos = coder->lz.pos;
+	const size_t in_avail = in_size - *in_pos;
+
+	if (coder->lz.temp_size + in_avail < 2 * TEMP_LIMIT) {
+		// Copy all the available input from in[] to temp[].
+		memcpy(coder->lz.temp + coder->lz.temp_size,
+				in + *in_pos, in_avail);
+		coder->lz.temp_size += in_avail;
+		*in_pos += in_avail;
+		assert(*in_pos == in_size);
+
+		// Decode as much as possible.
+		size_t temp_used = 0;
+		error = coder->lz.process(coder, coder->lz.temp, &temp_used,
+				coder->lz.temp_size, true);
+		assert(temp_used <= coder->lz.temp_size);
+
+		// Move the remaining data to the beginning of temp[].
+		coder->lz.temp_size -= temp_used;
+		memmove(coder->lz.temp, coder->lz.temp + temp_used,
+				coder->lz.temp_size);
+
+	} else if (coder->lz.temp_size > 0) {
+		// Fill temp[] unless it is already full because we aren't
+		// the last filter in the chain.
+		size_t copy_size = 0;
+		if (coder->lz.temp_size < 2 * TEMP_LIMIT) {
+			assert(*in_pos < in_size);
+			copy_size = 2 * TEMP_LIMIT - coder->lz.temp_size;
+			memcpy(coder->lz.temp + coder->lz.temp_size,
+					in + *in_pos, copy_size);
+			// NOTE: We don't update lz.temp_size or *in_pos yet.
+		}
+
+		size_t temp_used = 0;
+		error = coder->lz.process(coder, coder->lz.temp, &temp_used,
+				coder->lz.temp_size + copy_size, false);
+
+		if (temp_used < coder->lz.temp_size) {
+			// Only very little input data was consumed. Move
+			// the unprocessed data to the beginning temp[].
+			coder->lz.temp_size += copy_size - temp_used;
+			memmove(coder->lz.temp, coder->lz.temp + temp_used,
+					coder->lz.temp_size);
+			*in_pos += copy_size;
+			assert(*in_pos <= in_size);
+
+		} else {
+			// We were able to decode so much data that next time
+			// we can decode directly from in[]. That is, we can
+			// consider temp[] to be empty now.
+			*in_pos += temp_used - coder->lz.temp_size;
+			coder->lz.temp_size = 0;
+			assert(*in_pos <= in_size);
+		}
+
+	} else {
+		// Decode directly from in[].
+		error = coder->lz.process(coder, in, in_pos, in_size, false);
+		assert(*in_pos <= in_size);
+	}
+
+	assert(coder->lz.pos >= dict_old_pos);
+	if (coder->lz.uncompressed_size != LZMA_VLI_VALUE_UNKNOWN) {
+		// Update uncompressed size.
+		coder->lz.uncompressed_size -= coder->lz.pos - dict_old_pos;
+
+		// Check that End of Payload Marker hasn't been detected
+		// since it must not be present because uncompressed size
+		// is known.
+		if (coder->lz.eopm_detected)
+			error = true;
+	}
+
+	return error;
+}
+
+
+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,
+		bool flushing)
+{
+	bool stop = false;
+
+	while (true) {
+		// Flush from coder->lz.dict to out[].
+		flush(&coder->lz, out, out_pos, out_size);
+
+		// All done?
+		if (*out_pos == out_size
+				|| stop
+				|| coder->lz.eopm_detected
+				|| coder->lz.uncompressed_size == 0)
+			break;
+
+		// Set write limit in the dictionary.
+		if (set_limit(&coder->lz, out_size - *out_pos, flushing))
+			break;
+
+		// Decode more data.
+		if (call_process(coder, in, in_pos, in_size))
+			return LZMA_DATA_ERROR;
+
+		// Set stop to true if we must not call call_process() again
+		// during this function call.
+		// FIXME: Can this make the loop exist too early? It wouldn't
+		// cause data corruption so not a critical problem. It can
+		// happen if dictionary gets full and lz.temp still contains
+		// a few bytes data that we could decode right now.
+		if (*in_pos == in_size && coder->lz.temp_size <= TEMP_LIMIT
+				&& coder->lz.pos < coder->lz.limit)
+			stop = true;
+	}
+
+	// If we have decoded everything (EOPM detected or uncompressed_size
+	// bytes were processed) to the history buffer, and also flushed
+	// everything from the history buffer, our job is done.
+	if ((coder->lz.eopm_detected
+			|| coder->lz.uncompressed_size == 0)
+			&& coder->lz.start == coder->lz.pos)
+		return LZMA_STREAM_END;
+
+	return LZMA_OK;
+}
+
+
+extern lzma_ret
+lzma_lz_decode(lzma_coder *coder,
+		lzma_allocator *allocator lzma_attribute((unused)),
+		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)
+{
+	if (coder->next.code == NULL) {
+		const lzma_ret ret = decode_buffer(coder, in, in_pos, in_size,
+				out, out_pos, out_size,
+				action == LZMA_SYNC_FLUSH);
+
+		if (*out_pos == out_size || ret == LZMA_STREAM_END) {
+			// Unread to make coder->temp[] empty. This is easy,
+			// because we know that all the data currently in
+			// coder->temp[] has been copied form in[] during this
+			// call to the decoder.
+			//
+			// If we didn't do this, we could have data left in
+			// coder->temp[] when end of stream is reached. That
+			// data could be left there from *previous* call to
+			// the decoder; in that case we wouldn't know where
+			// to put that data.
+			assert(*in_pos >= coder->lz.temp_size);
+			*in_pos -= coder->lz.temp_size;
+			coder->lz.temp_size = 0;
+		}
+
+		return ret;
+	}
+
+	// We aren't the last coder in the chain, we need to decode
+	// our input to a temporary buffer.
+	const bool flushing = action == LZMA_SYNC_FLUSH;
+	while (*out_pos < out_size) {
+		if (!coder->lz.next_finished
+				&& coder->lz.temp_size < LZMA_BUFFER_SIZE) {
+			const lzma_ret ret = coder->next.code(
+					coder->next.coder,
+					allocator, in, in_pos, in_size,
+					coder->lz.temp, &coder->lz.temp_size,
+					LZMA_BUFFER_SIZE, action);
+
+			if (ret == LZMA_STREAM_END)
+				coder->lz.next_finished = true;
+			else if (coder->lz.temp_size < LZMA_BUFFER_SIZE
+					|| ret != LZMA_OK)
+				return ret;
+		}
+
+		if (coder->lz.this_finished) {
+			if (coder->lz.temp_size != 0)
+				return LZMA_DATA_ERROR;
+
+			if (coder->lz.next_finished)
+				return LZMA_STREAM_END;
+
+			return LZMA_OK;
+		}
+
+		size_t dummy = 0;
+		const lzma_ret ret = decode_buffer(coder, NULL, &dummy, 0,
+				out, out_pos, out_size, flushing);
+
+		if (ret == LZMA_STREAM_END)
+			coder->lz.this_finished = true;
+		else if (ret != LZMA_OK)
+			return ret;
+		else if (coder->lz.next_finished && *out_pos < out_size)
+			return LZMA_DATA_ERROR;
+	}
+
+	return LZMA_OK;
+}
+
+
+/// \brief      Initializes LZ part of the LZMA decoder or Inflate
+///
+/// \param      history_size    Number of bytes the LZ out window is
+///                             supposed keep available from the output
+///                             history.
+/// \param      match_max_len   Number of bytes a single decoding loop
+///                             can advance the write position (lz->pos)
+///                             in the history buffer (lz->dict).
+///
+/// \note       This function is called by LZMA decoder and Inflate init()s.
+///             It's up to those functions allocate *lz and initialize it
+///             with LZMA_LZ_DECODER_INIT.
+extern lzma_ret
+lzma_lz_decoder_reset(lzma_lz_decoder *lz, lzma_allocator *allocator,
+		bool (*process)(lzma_coder *restrict coder,
+			const uint8_t *restrict in, size_t *restrict in_pos,
+			size_t in_size, bool has_safe_buffer),
+		lzma_vli uncompressed_size,
+		size_t history_size, size_t match_max_len)
+{
+	// Set uncompressed size.
+	lz->uncompressed_size = uncompressed_size;
+
+	// Limit the history size to roughly sane values. This is primarily
+	// to prevent integer overflows.
+	if (history_size > UINT32_MAX / 2)
+		return LZMA_HEADER_ERROR;
+
+	// Store the value actually requested. We use it for sanity checks
+	// when repeating data from the history buffer.
+	lz->requested_size = history_size;
+
+	// Avoid tiny history buffer sizes for performance reasons.
+	// TODO: Test if this actually helps...
+	if (history_size < DICT_SIZE_MIN)
+		history_size = DICT_SIZE_MIN;
+
+	// The real size of the history buffer is a bit bigger than
+	// requested by our caller. This allows us to do some optimizations,
+	// which help not only speed but simplicity of the code; specifically,
+	// we can make sure that there is always at least match_max_len
+	// bytes immediatelly available for writing without a need to wrap
+	// the history buffer.
+	const size_t dict_real_size = history_size + 2 * match_max_len + 1;
+
+	// Reallocate memory if needed.
+	if (history_size != lz->size || match_max_len != lz->match_max_len) {
+		// Destroy the old buffer.
+		lzma_lz_decoder_end(lz, allocator);
+
+		lz->size = history_size;
+		lz->match_max_len = match_max_len;
+		lz->must_flush_pos = history_size + match_max_len + 1;
+
+		lz->dict = lzma_alloc(dict_real_size, allocator);
+		if (lz->dict == NULL)
+			return LZMA_MEM_ERROR;
+	}
+
+	// Clean up the buffers to make it very sure that there are
+	// no information leaks when multiple steams are decoded
+	// with the same decoder structures.
+	memzero(lz->dict, dict_real_size);
+	memzero(lz->temp, LZMA_BUFFER_SIZE);
+
+	// Reset the variables so that lz_get_byte(lz, 0) will return '\0'.
+	lz->pos = 0;
+	lz->start = 0;
+	lz->end = dict_real_size;
+	lz->is_full = false;
+	lz->eopm_detected = false;
+	lz->next_finished = false;
+	lz->this_finished = false;
+
+	// Set the process function pointer.
+	lz->process = process;
+
+	return LZMA_OK;
+}
+
+
+extern void
+lzma_lz_decoder_end(lzma_lz_decoder *lz, lzma_allocator *allocator)
+{
+	lzma_free(lz->dict, allocator);
+	lz->dict = NULL;
+	lz->size = 0;
+	lz->match_max_len = 0;
+	return;
+}
diff --git a/src/liblzma/lz/lz_decoder.h b/src/liblzma/lz/lz_decoder.h
new file mode 100644
index 00000000..a8a585cd
--- /dev/null
+++ b/src/liblzma/lz/lz_decoder.h
@@ -0,0 +1,214 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       lz_decoder.h
+/// \brief      LZ out window
+//
+//  Copyright (C) 1999-2006 Igor Pavlov
+//  Copyright (C) 2007 Lasse Collin
+//
+//  This library is free software; you can redistribute it and/or
+//  modify it under the terms of the GNU Lesser General Public
+//  License as published by the Free Software Foundation; either
+//  version 2.1 of the License, or (at your option) any later version.
+//
+//  This library is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+//  Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#ifndef LZMA_LZ_OUT_H
+#define LZMA_LZ_OUT_H
+
+#include "common.h"
+
+
+/// Get a byte from the history buffer.
+#define lz_get_byte(lz, distance) \
+	((distance) < (lz).pos \
+		? (lz).dict[(lz).pos - (distance) - 1] \
+		: (lz).dict[(lz).pos - (distance) - 1 + (lz).end])
+
+
+#define LZMA_LZ_DECODER_INIT \
+	(lzma_lz_decoder){ .dict = NULL, .size = 0, .match_max_len = 0 }
+
+
+typedef struct {
+	/// Function to do the actual decoding (LZMA or Inflate)
+	bool (*process)(lzma_coder *restrict coder, const uint8_t *restrict in,
+			size_t *restrict in_pos, size_t size_in,
+			bool has_safe_buffer);
+
+	/// Pointer to dictionary (history) buffer.
+	/// \note Not 'restrict' because can alias next_out.
+	uint8_t *dict;
+
+	/// Next write goes to dict[pos].
+	size_t pos;
+
+	/// Next byte to flush is buffer[start].
+	size_t start;
+
+	/// First byte to not flush is buffer[end].
+	size_t end;
+
+	/// First position to which data must not be written.
+	size_t limit;
+
+	/// True if dictionary has needed wrapping.
+	bool is_full;
+
+	/// True if process() has detected End of Payload Marker.
+	bool eopm_detected;
+
+	/// True if the next coder 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;
+
+	/// When pos >= must_flush_pos, we must not call process().
+	size_t must_flush_pos;
+
+	/// Maximum number of bytes that a single decoding loop inside
+	/// process() can produce data into dict. This amount is kept
+	/// always available at dict + pos i.e. it is safe to write a byte
+	/// to dict[pos + match_max_len - 1].
+	size_t match_max_len;
+
+	/// Number of bytes allocated to dict.
+	size_t size;
+
+	/// Requested size of the dictionary. This is needed because we avoid
+	/// using extremely tiny history buffers.
+	size_t requested_size;
+
+	/// Uncompressed Size or LZMA_VLI_VALUE_UNKNOWN if unknown.
+	lzma_vli uncompressed_size;
+
+	/// Number of bytes currently in temp[].
+	size_t temp_size;
+
+	/// Temporary buffer needed when
+	/// 1) we cannot make the input buffer completely empty; or
+	/// 2) we are not the last filter in the chain.
+	uint8_t temp[LZMA_BUFFER_SIZE];
+
+} lzma_lz_decoder;
+
+
+/////////////////////////
+// Function prototypes //
+/////////////////////////
+
+extern lzma_ret lzma_lz_decoder_reset(lzma_lz_decoder *lz,
+		lzma_allocator *allocator, bool (*process)(
+			lzma_coder *restrict coder, const uint8_t *restrict in,
+			size_t *restrict in_pos, size_t in_size,
+			bool has_safe_buffer),
+		lzma_vli uncompressed_size,
+		size_t history_size, size_t match_max_len);
+
+extern lzma_ret lzma_lz_decode(lzma_coder *coder, lzma_allocator *allocator,
+		const uint8_t *restrict in, size_t *restrict in_pos,
+		size_t in_size, uint8_t *restrict out,
+		size_t *restrict out_pos, size_t out_size,
+		lzma_action action);
+
+/// Deallocates the history buffer if one exists.
+extern void lzma_lz_decoder_end(
+		lzma_lz_decoder *lz, lzma_allocator *allocator);
+
+//////////////////////
+// Inline functions //
+//////////////////////
+
+// 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:
+// 1. distance < length
+//    Source and target areas overlap, thus we can't use memcpy()
+//    (nor memmove()) safely.
+//    TODO: If this is common enough, it might be worth optimizing this
+//    more e.g. by checking if distance > sizeof(uint8_t*) and using
+//    memcpy in small chunks.
+// 2. distance < pos
+//    This is the easiest and the fastest case. The block being copied
+//    is a contiguous piece in the history buffer. The buffer offset
+//    doesn't need wrapping.
+// 3. distance >= pos
+//    We need to wrap the position, because otherwise we would try copying
+//    behind the first byte of the allocated buffer. It is possible that
+//    the block is fragmeneted into two pieces, thus we might need to call
+//    memcpy() twice.
+// NOTE: The function using this macro must ensure that length is positive
+// and that distance is FIXME
+static inline bool
+lzma_lz_out_repeat(lzma_lz_decoder *lz, size_t distance, size_t length)
+{
+	// Validate offset of the block to be repeated. It doesn't
+	// make sense to copy data behind the beginning of the stream.
+	// Leaving this check away would lead to a security problem,
+	// in which e.g. the data of the previously decoded file(s)
+	// would be leaked (or whatever happens to be in unused
+	// part of the dictionary buffer).
+	if (distance >= lz->pos && !lz->is_full)
+		return false;
+
+	// It also doesn't make sense to copy data farer than
+	// the dictionary size.
+	if (distance >= lz->requested_size)
+		return false;
+
+	// The caller must have checked these!
+	assert(distance <= lz->size);
+	assert(length > 0);
+	assert(length <= lz->match_max_len);
+
+	// Copy the amount of data requested by the decoder.
+	if (distance < length) {
+		// Source and target areas overlap, thus we can't use
+		// memcpy() nor even memmove() safely. :-(
+		// TODO: Copying byte by byte is slow. It might be
+		// worth optimizing this more if this case is common.
+		do {
+			lz->dict[lz->pos] = lz_get_byte(*lz, distance);
+			++lz->pos;
+		} while (--length > 0);
+
+	} else if (distance < lz->pos) {
+		// The easiest and fastest case
+		memcpy(lz->dict + lz->pos,
+				lz->dict + lz->pos - distance - 1,
+				length);
+		lz->pos += length;
+
+	} 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(lz->is_full);
+		const uint32_t copy_pos = lz->pos - distance - 1 + lz->end;
+		uint32_t copy_size = lz->end - copy_pos;
+
+		if (copy_size < length) {
+			memcpy(lz->dict + lz->pos, lz->dict + copy_pos,
+					copy_size);
+			lz->pos += copy_size;
+			copy_size = length - copy_size;
+			memcpy(lz->dict + lz->pos, lz->dict, copy_size);
+			lz->pos += copy_size;
+		} else {
+			memcpy(lz->dict + lz->pos, lz->dict + copy_pos,
+					length);
+			lz->pos += length;
+		}
+	}
+
+	return true;
+}
+
+#endif
diff --git a/src/liblzma/lz/lz_encoder.c b/src/liblzma/lz/lz_encoder.c
new file mode 100644
index 00000000..bc38cae2
--- /dev/null
+++ b/src/liblzma/lz/lz_encoder.c
@@ -0,0 +1,481 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       lz_encoder.c
+/// \brief      LZ in window
+//
+//  Copyright (C) 1999-2006 Igor Pavlov
+//  Copyright (C) 2007 Lasse Collin
+//
+//  This library is free software; you can redistribute it and/or
+//  modify it under the terms of the GNU Lesser General Public
+//  License as published by the Free Software Foundation; either
+//  version 2.1 of the License, or (at your option) any later version.
+//
+//  This library is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+//  Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include "lz_encoder_private.h"
+
+// Hash Chains
+#ifdef HAVE_HC3
+#	include "hc3.h"
+#endif
+#ifdef HAVE_HC4
+#	include "hc4.h"
+#endif
+
+// Binary Trees
+#ifdef HAVE_BT2
+#	include "bt2.h"
+#endif
+#ifdef HAVE_BT3
+#	include "bt3.h"
+#endif
+#ifdef HAVE_BT4
+#	include "bt4.h"
+#endif
+
+
+/// This is needed in two places so provide a macro.
+#define get_cyclic_buffer_size(history_size) ((history_size) + 1)
+
+
+/// Calculate certain match finder properties and validate the calculated
+/// values. This is as its own function, because *num_items is needed to
+/// calculate memory requirements in common/memory.c.
+extern uint32_t
+lzma_lz_encoder_hash_properties(lzma_match_finder match_finder,
+		uint32_t history_size, uint32_t *restrict hash_mask,
+		uint32_t *restrict hash_size_sum, uint32_t *restrict num_items)
+{
+	uint32_t fix_hash_size;
+	uint32_t sons;
+
+	switch (match_finder) {
+#ifdef HAVE_HC3
+	case LZMA_MF_HC3:
+		fix_hash_size = LZMA_HC3_FIX_HASH_SIZE;
+		sons = 1;
+		break;
+#endif
+#ifdef HAVE_HC4
+	case LZMA_MF_HC4:
+		fix_hash_size = LZMA_HC4_FIX_HASH_SIZE;
+		sons = 1;
+		break;
+#endif
+#ifdef HAVE_BT2
+	case LZMA_MF_BT2:
+		fix_hash_size = LZMA_BT2_FIX_HASH_SIZE;
+		sons = 2;
+		break;
+#endif
+#ifdef HAVE_BT3
+	case LZMA_MF_BT3:
+		fix_hash_size = LZMA_BT3_FIX_HASH_SIZE;
+		sons = 2;
+		break;
+#endif
+#ifdef HAVE_BT4
+	case LZMA_MF_BT4:
+		fix_hash_size = LZMA_BT4_FIX_HASH_SIZE;
+		sons = 2;
+		break;
+#endif
+	default:
+		return true;
+	}
+
+	uint32_t hs;
+
+#ifdef HAVE_LZMA_BT2
+	if (match_finder == LZMA_BT2) {
+		// NOTE: hash_mask is not used by the BT2 match finder,
+		// but it is initialized just in case.
+		hs = LZMA_BT2_HASH_SIZE;
+		*hash_mask = 0;
+	} else
+#endif
+	{
+		hs = history_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 (match_finder == LZMA_MF_HC4
+					|| match_finder == LZMA_MF_BT4)
+				hs >>= 1;
+			else
+				hs = (1 << 24) - 1;
+		}
+
+		*hash_mask = hs;
+		++hs;
+	}
+
+	*hash_size_sum = hs + fix_hash_size;
+
+	*num_items = *hash_size_sum
+			+ get_cyclic_buffer_size(history_size) * sons;
+
+	return false;
+}
+
+
+extern lzma_ret
+lzma_lz_encoder_reset(lzma_lz_encoder *lz, lzma_allocator *allocator,
+		bool (*process)(lzma_coder *coder, uint8_t *restrict out,
+			size_t *restrict out_pos, size_t out_size),
+		lzma_vli uncompressed_size,
+		size_t history_size, size_t additional_buffer_before,
+		size_t match_max_len, size_t additional_buffer_after,
+		lzma_match_finder match_finder, uint32_t match_finder_cycles,
+		const uint8_t *preset_dictionary,
+		size_t preset_dictionary_size)
+{
+	// Set uncompressed size.
+	lz->uncompressed_size = uncompressed_size;
+
+	///////////////
+	// In Window //
+	///////////////
+
+	// Validate history size.
+	if (history_size < LZMA_DICTIONARY_SIZE_MIN
+			|| history_size > LZMA_DICTIONARY_SIZE_MAX) {
+		lzma_lz_encoder_end(lz, allocator);
+		return LZMA_HEADER_ERROR;
+	}
+
+	assert(history_size <= MAX_VAL_FOR_NORMALIZE - 256);
+	assert(LZMA_DICTIONARY_SIZE_MAX <= MAX_VAL_FOR_NORMALIZE - 256);
+
+	// Calculate the size of the history buffer to allocate.
+	// TODO: Get a reason for magic constant of 256.
+	const size_t size_reserv = (history_size + additional_buffer_before
+			+ match_max_len + additional_buffer_after) / 2 + 256;
+
+	lz->keep_size_before = history_size + additional_buffer_before;
+	lz->keep_size_after = match_max_len + additional_buffer_after;
+
+	const size_t buffer_size = lz->keep_size_before + lz->keep_size_after
+			+ size_reserv;
+
+	// Allocate history buffer if its size has changed.
+	if (buffer_size != lz->size) {
+		lzma_free(lz->buffer, allocator);
+		lz->buffer = lzma_alloc(buffer_size, allocator);
+		if (lz->buffer == NULL) {
+			lzma_lz_encoder_end(lz, allocator);
+			return LZMA_MEM_ERROR;
+		}
+	}
+
+	// Allocation successful. Store the new size and calculate
+	// must_move_pos.
+	lz->size = buffer_size;
+	lz->must_move_pos = lz->size - lz->keep_size_after;
+
+	// Reset in window variables.
+	lz->offset = 0;
+	lz->read_pos = 0;
+	lz->read_limit = 0;
+	lz->write_pos = 0;
+	lz->stream_end_was_reached = false;
+
+
+	//////////////////
+	// Match Finder //
+	//////////////////
+
+	// Validate match_finder, set function pointers and a few match
+	// finder specific variables.
+	switch (match_finder) {
+#ifdef HAVE_HC3
+	case LZMA_MF_HC3:
+		lz->get_matches = &lzma_hc3_get_matches;
+		lz->skip = &lzma_hc3_skip;
+		lz->cut_value = 8 + (match_max_len >> 2);
+		break;
+#endif
+#ifdef HAVE_HC4
+	case LZMA_MF_HC4:
+		lz->get_matches = &lzma_hc4_get_matches;
+		lz->skip = &lzma_hc4_skip;
+		lz->cut_value = 8 + (match_max_len >> 2);
+		break;
+#endif
+#ifdef HAVE_BT2
+	case LZMA_MF_BT2:
+		lz->get_matches = &lzma_bt2_get_matches;
+		lz->skip = &lzma_bt2_skip;
+		lz->cut_value = 16 + (match_max_len >> 1);
+		break;
+#endif
+#ifdef HAVE_BT3
+	case LZMA_MF_BT3:
+		lz->get_matches = &lzma_bt3_get_matches;
+		lz->skip = &lzma_bt3_skip;
+		lz->cut_value = 16 + (match_max_len >> 1);
+		break;
+#endif
+#ifdef HAVE_BT4
+	case LZMA_MF_BT4:
+		lz->get_matches = &lzma_bt4_get_matches;
+		lz->skip = &lzma_bt4_skip;
+		lz->cut_value = 16 + (match_max_len >> 1);
+		break;
+#endif
+	default:
+		lzma_lz_encoder_end(lz, allocator);
+		return LZMA_HEADER_ERROR;
+	}
+
+	// Check if we have been requested to use a non-default cut_value.
+	if (match_finder_cycles > 0)
+		lz->cut_value = match_finder_cycles;
+
+	lz->match_max_len = match_max_len;
+	lz->cyclic_buffer_size = get_cyclic_buffer_size(history_size);
+
+	uint32_t hash_size_sum;
+	uint32_t num_items;
+	if (lzma_lz_encoder_hash_properties(match_finder, history_size,
+			&lz->hash_mask, &hash_size_sum, &num_items)) {
+		lzma_lz_encoder_end(lz, allocator);
+		return LZMA_HEADER_ERROR;
+	}
+
+	if (num_items != lz->num_items) {
+#if UINT32_MAX >= SIZE_MAX / 4
+		// Check for integer overflow. (Huge dictionaries are not
+		// possible on 32-bit CPU.)
+		if (num_items > SIZE_MAX / sizeof(uint32_t)) {
+			lzma_lz_encoder_end(lz, allocator);
+			return LZMA_MEM_ERROR;
+		}
+#endif
+
+		const size_t size_in_bytes
+				= (size_t)(num_items) * sizeof(uint32_t);
+
+		lzma_free(lz->hash, allocator);
+		lz->hash = lzma_alloc(size_in_bytes, allocator);
+		if (lz->hash == NULL) {
+			lzma_lz_encoder_end(lz, allocator);
+			return LZMA_MEM_ERROR;
+		}
+
+		lz->num_items = num_items;
+	}
+
+	lz->son = lz->hash + hash_size_sum;
+
+	// Reset the hash table to empty hash values.
+	{
+		uint32_t *restrict items = lz->hash;
+
+		for (uint32_t i = 0; i < hash_size_sum; ++i)
+			items[i] = EMPTY_HASH_VALUE;
+	}
+
+	lz->cyclic_buffer_pos = 0;
+
+	// Because zero is used as empty hash value, make the first byte
+	// appear at buffer[1 - offset].
+	++lz->offset;
+
+	// If we are using a preset dictionary, read it now.
+	// TODO: This isn't implemented yet so return LZMA_HEADER_ERROR.
+	if (preset_dictionary != NULL && preset_dictionary_size > 0) {
+		lzma_lz_encoder_end(lz, allocator);
+		return LZMA_HEADER_ERROR;
+	}
+
+	// Set the process function pointer.
+	lz->process = process;
+
+	return LZMA_OK;
+}
+
+
+extern void
+lzma_lz_encoder_end(lzma_lz_encoder *lz, lzma_allocator *allocator)
+{
+	lzma_free(lz->hash, allocator);
+	lz->hash = NULL;
+	lz->num_items = 0;
+
+	lzma_free(lz->buffer, allocator);
+	lz->buffer = NULL;
+	lz->size = 0;
+
+	return;
+}
+
+
+/// \brief      Moves the data in the input window to free space for new data
+///
+/// lz->buffer is a sliding input window, which keeps lz->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_lz_encoder *lz)
+{
+	// buffer[move_offset] will become buffer[0].
+	assert(lz->read_pos > lz->keep_size_after);
+	size_t move_offset = lz->read_pos - lz->keep_size_before;
+
+	// We need one additional byte, since move_pos() moves on 1 byte.
+	// TODO: Clean up? At least document more.
+	if (move_offset > 0)
+		--move_offset;
+
+	assert(lz->write_pos > move_offset);
+	const size_t move_size = lz->write_pos - move_offset;
+
+	assert(move_offset + move_size <= lz->size);
+
+	memmove(lz->buffer, lz->buffer + move_offset, move_size);
+
+	lz->offset += move_offset;
+	lz->read_pos -= move_offset;
+	lz->read_limit -= move_offset;
+	lz->write_pos -= move_offset;
+
+	return;
+}
+
+
+/// \brief      Tries to fill the input window (lz->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 lz->buffer.
+///
+/// This function must not be called once it has returned LZMA_STREAM_END.
+///
+static lzma_ret
+fill_window(lzma_coder *coder, lzma_allocator *allocator, const uint8_t *in,
+		size_t *in_pos, size_t in_size, lzma_action action)
+{
+	assert(coder->lz.read_pos <= coder->lz.write_pos);
+	lzma_ret ret;
+
+	// Move the sliding window if needed.
+	if (coder->lz.read_pos >= coder->lz.must_move_pos)
+		move_window(&coder->lz);
+
+	if (coder->next.code == NULL) {
+		// Not using a filter, simply memcpy() as much as possible.
+		bufcpy(in, in_pos, in_size, coder->lz.buffer,
+				&coder->lz.write_pos, coder->lz.size);
+
+		if (action == LZMA_FINISH && *in_pos == in_size)
+			ret = LZMA_STREAM_END;
+		else
+			ret = LZMA_OK;
+
+	} else {
+		ret = coder->next.code(coder->next.coder, allocator,
+				in, in_pos, in_size,
+				coder->lz.buffer, &coder->lz.write_pos,
+				coder->lz.size, action);
+	}
+
+	// If end of stream has been reached, 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) {
+		coder->lz.stream_end_was_reached = true;
+		coder->lz.read_limit = coder->lz.write_pos;
+
+	} else if (coder->lz.write_pos > coder->lz.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->lz.read_limit = coder->lz.write_pos
+				- coder->lz.keep_size_after;
+	}
+
+	return ret;
+}
+
+
+extern lzma_ret
+lzma_lz_encode(lzma_coder *coder, lzma_allocator *allocator,
+		const uint8_t *restrict in, size_t *restrict in_pos,
+		size_t in_size,
+		uint8_t *restrict out, size_t *restrict out_pos,
+		size_t out_size, lzma_action action)
+{
+	while (*out_pos < out_size
+			&& (*in_pos < in_size || action == LZMA_FINISH)) {
+		// Fill the input window if there is no more usable data.
+		if (!coder->lz.stream_end_was_reached && coder->lz.read_pos
+				>= coder->lz.read_limit) {
+			const lzma_ret ret = fill_window(coder, allocator,
+					in, in_pos, in_size, action);
+			if (ret != LZMA_OK && ret != LZMA_STREAM_END)
+				return ret;
+		}
+
+		// Encode
+		if (coder->lz.process(coder, out, out_pos, out_size))
+			return LZMA_STREAM_END;
+	}
+
+	return LZMA_OK;
+}
+
+
+/// \brief      Normalizes hash values
+///
+/// lzma_lz_normalize is called when lz->pos hits MAX_VAL_FOR_NORMALIZE,
+/// which currently happens once every 2 GiB of input data (to be exact,
+/// after the first 2 GiB it happens once every 2 GiB minus dictionary_size
+/// bytes). lz->pos is incremented by lzma_lz_move_pos().
+///
+/// lz->hash contains big amount of offsets relative to lz->buffer.
+/// The offsets are stored as uint32_t, which is the only reasonable
+/// datatype for these offsets; uint64_t would waste far too much RAM
+/// and uint16_t would limit the dictionary to 64 KiB (far too small).
+///
+/// When compressing files over 2 GiB, lz->buffer needs to be moved forward
+/// to avoid integer overflows. We scan the lz->hash array and fix every
+/// value to match the updated lz->buffer.
+extern void
+lzma_lz_encoder_normalize(lzma_lz_encoder *lz)
+{
+	const uint32_t subvalue = lz->read_pos - lz->cyclic_buffer_size;
+	assert(subvalue <= INT32_MAX);
+
+	{
+		const uint32_t num_items = lz->num_items;
+		uint32_t *restrict items = lz->hash;
+
+		for (uint32_t i = 0; i < num_items; ++i) {
+			// If the distance is greater than the dictionary
+			// size, we can simply mark the item as empty.
+			if (items[i] <= subvalue)
+				items[i] = EMPTY_HASH_VALUE;
+			else
+				items[i] -= subvalue;
+		}
+	}
+
+	// Update offset to match the new locations.
+	lz->offset -= subvalue;
+
+	return;
+}
diff --git a/src/liblzma/lz/lz_encoder.h b/src/liblzma/lz/lz_encoder.h
new file mode 100644
index 00000000..b39c88e5
--- /dev/null
+++ b/src/liblzma/lz/lz_encoder.h
@@ -0,0 +1,161 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       lz_encoder.h
+/// \brief      LZ in window and match finder API
+//
+//  Copyright (C) 1999-2006 Igor Pavlov
+//  Copyright (C) 2007 Lasse Collin
+//
+//  This library is free software; you can redistribute it and/or
+//  modify it under the terms of the GNU Lesser General Public
+//  License as published by the Free Software Foundation; either
+//  version 2.1 of the License, or (at your option) any later version.
+//
+//  This library is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+//  Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#ifndef LZMA_LZ_ENCODER_H
+#define LZMA_LZ_ENCODER_H
+
+#include "common.h"
+
+
+typedef struct lzma_lz_encoder_s lzma_lz_encoder;
+struct lzma_lz_encoder_s {
+	enum {
+		SEQ_INIT,
+		SEQ_RUN,
+		SEQ_FINISH,
+		SEQ_END
+	} sequence;
+
+	bool (*process)(lzma_coder *coder, uint8_t *restrict out,
+			size_t *restrict out_pos, size_t out_size);
+
+	lzma_vli uncompressed_size;
+
+	///////////////
+	// 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)
+	size_t size;
+
+	/// 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[match_finder_pos - offset]
+	/// is the byte pointed by match_finder_pos.
+	size_t offset;
+
+	/// buffer[read_pos] is the current byte.
+	size_t read_pos;
+
+	/// 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.
+	size_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].
+	size_t write_pos;
+
+	/// When read_pos >= must_move_pos, move_window() must be called
+	/// to make more space for the input data.
+	size_t must_move_pos;
+
+	/// 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.
+	size_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
+	/// stream_end_was_reached is false (once it is true, read_pos
+	/// is allowed to reach write_pos).
+	size_t keep_size_after;
+
+	/// This is set to true once the last byte of the input data has
+	/// been copied to buffer.
+	bool stream_end_was_reached;
+
+	//////////////////
+	// Match Finder //
+	//////////////////
+
+	// Pointers to match finder functions
+	void (*get_matches)(lzma_lz_encoder *restrict lz,
+			uint32_t *restrict distances);
+	void (*skip)(lzma_lz_encoder *restrict lz, uint32_t num);
+
+	// Match finder data
+	uint32_t *hash; // TODO: Check if hash aliases son
+	uint32_t *son;  //       and add 'restrict' if possible.
+	uint32_t cyclic_buffer_pos;
+	uint32_t cyclic_buffer_size; // Must be dictionary_size + 1.
+	uint32_t hash_mask;
+	uint32_t cut_value;
+	uint32_t hash_size_sum;
+	uint32_t num_items;
+	uint32_t match_max_len;
+};
+
+
+#define LZMA_LZ_ENCODER_INIT \
+	(lzma_lz_encoder){ \
+		.buffer = NULL, \
+		.size = 0, \
+		.hash = NULL, \
+		.num_items = 0, \
+	}
+
+
+/// Calculates
+extern uint32_t lzma_lz_encoder_hash_properties(lzma_match_finder match_finder,
+		uint32_t history_size, uint32_t *restrict hash_mask,
+		uint32_t *restrict hash_size_sum,
+		uint32_t *restrict num_items);
+
+// NOTE: liblzma doesn't use callback API like LZMA SDK does. The caller
+// must make sure that keep_size_after is big enough for single encoding pass
+// i.e. keep_size_after >= maximum number of bytes possibly needed after
+// the current position between calls to lzma_lz_read().
+extern lzma_ret lzma_lz_encoder_reset(lzma_lz_encoder *lz,
+		lzma_allocator *allocator,
+		bool (*process)(lzma_coder *coder, uint8_t *restrict out,
+			size_t *restrict out_pos, size_t out_size),
+		lzma_vli uncompressed_size,
+		size_t history_size, size_t additional_buffer_before,
+		size_t match_max_len, size_t additional_buffer_after,
+		lzma_match_finder match_finder, uint32_t match_finder_cycles,
+		const uint8_t *preset_dictionary,
+		size_t preset_dictionary_size);
+
+/// Frees memory allocated for in window and match finder buffers.
+extern void lzma_lz_encoder_end(
+		lzma_lz_encoder *lz, lzma_allocator *allocator);
+
+extern lzma_ret lzma_lz_encode(lzma_coder *coder,
+		lzma_allocator *allocator lzma_attribute((unused)),
+		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);
+
+/// This should not be called directly, but only via move_pos() macro.
+extern void lzma_lz_encoder_normalize(lzma_lz_encoder *lz);
+
+#endif
diff --git a/src/liblzma/lz/lz_encoder_private.h b/src/liblzma/lz/lz_encoder_private.h
new file mode 100644
index 00000000..638fcb2d
--- /dev/null
+++ b/src/liblzma/lz/lz_encoder_private.h
@@ -0,0 +1,40 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       lz_encoder_private.h
+/// \brief      Private definitions for LZ encoder
+//
+//  Copyright (C) 1999-2006 Igor Pavlov
+//  Copyright (C) 2007 Lasse Collin
+//
+//  This library is free software; you can redistribute it and/or
+//  modify it under the terms of the GNU Lesser General Public
+//  License as published by the Free Software Foundation; either
+//  version 2.1 of the License, or (at your option) any later version.
+//
+//  This library is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+//  Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#ifndef LZMA_LZ_ENCODER_PRIVATE_H
+#define LZMA_LZ_ENCODER_PRIVATE_H
+
+#include "lz_encoder.h"
+
+/// Value used to indicate unused slot
+#define EMPTY_HASH_VALUE 0
+
+/// When the dictionary and hash variables need to be adjusted to prevent
+/// integer overflows. Since we use uint32_t to store the offsets, half
+/// of it is the biggest safe limit.
+#define MAX_VAL_FOR_NORMALIZE (UINT32_MAX / 2)
+
+
+struct lzma_coder_s {
+	lzma_next_coder next;
+	lzma_lz_encoder lz;
+};
+
+#endif
diff --git a/src/liblzma/lz/match_c.h b/src/liblzma/lz/match_c.h
new file mode 100644
index 00000000..68766385
--- /dev/null
+++ b/src/liblzma/lz/match_c.h
@@ -0,0 +1,401 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       match_c.h
+/// \brief      Template for different match finders
+///
+/// This file is included by hc3.c, hc4, bt2.c, bt3.c and bt4.c. Each file
+/// sets slighly different #defines, resulting the different match finders.
+//
+//  Copyright (C) 1999-2006 Igor Pavlov
+//  Copyright (C) 2007 Lasse Collin
+//
+//  This library is free software; you can redistribute it and/or
+//  modify it under the terms of the GNU Lesser General Public
+//  License as published by the Free Software Foundation; either
+//  version 2.1 of the License, or (at your option) any later version.
+//
+//  This library is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+//  Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+//////////////
+// Includes //
+//////////////
+
+#include "check.h"
+
+
+///////////////
+// Constants //
+///////////////
+
+#define START_MAX_LEN 1
+
+#ifdef HASH_ARRAY_2
+#	define NUM_HASH_DIRECT_BYTES 0
+#	define HASH_2_SIZE (1 << 10)
+#	ifdef HASH_ARRAY_3
+#		define NUM_HASH_BYTES 4
+#		define HASH_3_SIZE (1 << 16)
+#		define HASH_3_OFFSET HASH_2_SIZE
+#		define FIX_HASH_SIZE (HASH_2_SIZE + HASH_3_SIZE)
+#	else
+#		define NUM_HASH_BYTES 3
+#		define FIX_HASH_SIZE HASH_2_SIZE
+#	endif
+#	define HASH_SIZE 0
+#	define MIN_MATCH_CHECK NUM_HASH_BYTES
+#else
+#	define NUM_HASH_DIRECT_BYTES 2
+#	define NUM_HASH_BYTES 2
+#	define HASH_SIZE (1 << (8 * NUM_HASH_BYTES))
+#	define MIN_MATCH_CHECK (NUM_HASH_BYTES + 1)
+#	define FIX_HASH_SIZE 0
+#endif
+
+
+////////////
+// Macros //
+////////////
+
+#ifdef HASH_ARRAY_2
+#	ifdef HASH_ARRAY_3
+#		define HASH_CALC() \
+		do { \
+			const uint32_t temp = lzma_crc32_table[0][ \
+					cur[0]] ^ cur[1]; \
+			hash_2_value = temp & (HASH_2_SIZE - 1); \
+			hash_3_value = (temp ^ ((uint32_t)(cur[2]) << 8)) \
+					& (HASH_3_SIZE - 1); \
+			hash_value = (temp ^ ((uint32_t)(cur[2]) << 8) \
+					^ (lzma_crc32_table[0][cur[3]] << 5)) \
+					& lz->hash_mask; \
+		} while (0)
+#	else
+#		define HASH_CALC() \
+		do { \
+			const uint32_t temp = lzma_crc32_table[0][ \
+					cur[0]] ^ cur[1]; \
+			hash_2_value = temp & (HASH_2_SIZE - 1); \
+			hash_value = (temp ^ ((uint32_t)(cur[2]) << 8)) \
+					& lz->hash_mask; \
+		} while (0)
+#	endif
+#else
+#	define HASH_CALC() hash_value = cur[0] ^ ((uint32_t)(cur[1]) << 8)
+#endif
+
+
+// Moves the current read position forward by one byte. In LZMA SDK,
+// CLZInWindow::MovePos() can read more input data if needed, because of
+// the callback style API. In liblzma we must have ensured earlier, that
+// there is enough data available in lz->buffer.
+#define move_pos() \
+do { \
+	if (++lz->cyclic_buffer_pos == lz->cyclic_buffer_size) \
+		lz->cyclic_buffer_pos = 0; \
+	++lz->read_pos; \
+	assert(lz->read_pos <= lz->write_pos); \
+	if (lz->read_pos == MAX_VAL_FOR_NORMALIZE) \
+		lzma_lz_encoder_normalize(lz); \
+} while (0)
+
+
+//////////////////////
+// Global constants //
+//////////////////////
+
+LZMA_HASH_SIZE(LZMA_MATCH_FINDER_NAME_UPPER) = HASH_SIZE;
+LZMA_FIX_HASH_SIZE(LZMA_MATCH_FINDER_NAME_UPPER) = FIX_HASH_SIZE;
+
+
+///////////////////
+// API functions //
+///////////////////
+
+LZMA_GET_MATCHES(LZMA_MATCH_FINDER_NAME_LOWER)
+{
+	uint32_t len_limit;
+	if (lz->read_pos + lz->match_max_len <= lz->write_pos) {
+		len_limit = lz->match_max_len;
+	} else {
+		assert(lz->stream_end_was_reached);
+		len_limit = lz->write_pos - lz->read_pos;
+		if (len_limit < MIN_MATCH_CHECK) {
+			distances[0] = 0;
+			move_pos();
+			return;
+		}
+	}
+
+	int32_t offset = 1;
+	const uint32_t match_min_pos
+			= lz->read_pos + lz->offset > lz->cyclic_buffer_size
+			? lz->read_pos + lz->offset - lz->cyclic_buffer_size
+			: 0;
+	const uint8_t *cur = lz->buffer + lz->read_pos;
+	uint32_t max_len = START_MAX_LEN; // to avoid items for len < hash_size
+
+#ifdef HASH_ARRAY_2
+	uint32_t hash_2_value;
+#	ifdef HASH_ARRAY_3
+	uint32_t hash_3_value;
+#	endif
+#endif
+	uint32_t hash_value;
+	HASH_CALC();
+
+	uint32_t cur_match = lz->hash[FIX_HASH_SIZE + hash_value];
+#ifdef HASH_ARRAY_2
+	uint32_t cur_match2 = lz->hash[hash_2_value];
+#	ifdef HASH_ARRAY_3
+	uint32_t cur_match3 = lz->hash[HASH_3_OFFSET + hash_3_value];
+#	endif
+	lz->hash[hash_2_value] = lz->read_pos + lz->offset;
+
+	if (cur_match2 > match_min_pos) {
+		if (lz->buffer[cur_match2 - lz->offset] == cur[0]) {
+			max_len = 2;
+			distances[offset++] = 2;
+			distances[offset++] = lz->read_pos + lz->offset
+					- cur_match2 - 1;
+		}
+	}
+
+#	ifdef HASH_ARRAY_3
+	lz->hash[HASH_3_OFFSET + hash_3_value] = lz->read_pos + lz->offset;
+	if (cur_match3 > match_min_pos) {
+		if (lz->buffer[cur_match3 - lz->offset] == cur[0]) {
+			if (cur_match3 == cur_match2)
+				offset -= 2;
+
+			max_len = 3;
+			distances[offset++] = 3;
+			distances[offset++] = lz->read_pos + lz->offset
+					- cur_match3 - 1;
+			cur_match2 = cur_match3;
+		}
+	}
+#	endif
+
+	if (offset != 1 && cur_match2 == cur_match) {
+		offset -= 2;
+		max_len = START_MAX_LEN;
+	}
+#endif
+
+	lz->hash[FIX_HASH_SIZE + hash_value] = lz->read_pos + lz->offset;
+
+#ifdef IS_HASH_CHAIN
+	lz->son[lz->cyclic_buffer_pos] = cur_match;
+#else
+	uint32_t *ptr0 = lz->son + (lz->cyclic_buffer_pos << 1) + 1;
+	uint32_t *ptr1 = lz->son + (lz->cyclic_buffer_pos << 1);
+
+	uint32_t len0 = NUM_HASH_DIRECT_BYTES;
+	uint32_t len1 = NUM_HASH_DIRECT_BYTES;
+#endif
+
+#if NUM_HASH_DIRECT_BYTES != 0
+	if (cur_match > match_min_pos) {
+		if (lz->buffer[cur_match + NUM_HASH_DIRECT_BYTES - lz->offset]
+				!= cur[NUM_HASH_DIRECT_BYTES]) {
+			max_len = NUM_HASH_DIRECT_BYTES;
+			distances[offset++] = NUM_HASH_DIRECT_BYTES;
+			distances[offset++] = lz->read_pos + lz->offset
+					- cur_match - 1;
+		}
+	}
+#endif
+
+	uint32_t count = lz->cut_value;
+
+	while (true) {
+		if (cur_match <= match_min_pos || count-- == 0) {
+#ifndef IS_HASH_CHAIN
+			*ptr0 = EMPTY_HASH_VALUE;
+			*ptr1 = EMPTY_HASH_VALUE;
+#endif
+			break;
+		}
+
+		const uint32_t delta = lz->read_pos + lz->offset - cur_match;
+		const uint32_t cyclic_pos = delta <= lz->cyclic_buffer_pos
+				? lz->cyclic_buffer_pos - delta
+				: lz->cyclic_buffer_pos - delta
+					+ lz->cyclic_buffer_size;
+		uint32_t *pair = lz->son +
+#ifdef IS_HASH_CHAIN
+				cyclic_pos;
+#else
+				(cyclic_pos << 1);
+#endif
+
+		const uint8_t *pb = lz->buffer + cur_match - lz->offset;
+		uint32_t len =
+#ifdef IS_HASH_CHAIN
+				NUM_HASH_DIRECT_BYTES;
+		if (pb[max_len] == cur[max_len])
+#else
+				MIN(len0, len1);
+#endif
+
+		if (pb[len] == cur[len]) {
+			while (++len != len_limit)
+				if (pb[len] != cur[len])
+					break;
+
+			if (max_len < len) {
+				max_len = len;
+				distances[offset++] = len;
+				distances[offset++] = delta - 1;
+				if (len == len_limit) {
+#ifndef IS_HASH_CHAIN
+					*ptr1 = pair[0];
+					*ptr0 = pair[1];
+#endif
+					break;
+				}
+			}
+		}
+
+#ifdef IS_HASH_CHAIN
+		cur_match = *pair;
+#else
+		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;
+		}
+#endif
+	}
+
+	distances[0] = offset - 1;
+
+	move_pos();
+
+	return;
+}
+
+
+LZMA_SKIP(LZMA_MATCH_FINDER_NAME_LOWER)
+{
+	do {
+#ifdef IS_HASH_CHAIN
+		if (lz->write_pos - lz->read_pos < NUM_HASH_BYTES) {
+			move_pos();
+			continue;
+		}
+#else
+		uint32_t len_limit;
+		if (lz->read_pos + lz->match_max_len <= lz->write_pos) {
+			len_limit = lz->match_max_len;
+		} else {
+			assert(lz->stream_end_was_reached == true);
+			len_limit = lz->write_pos - lz->read_pos;
+			if (len_limit < MIN_MATCH_CHECK) {
+				move_pos();
+				continue;
+			}
+		}
+		const uint32_t match_min_pos
+			= lz->read_pos + lz->offset > lz->cyclic_buffer_size
+			? lz->read_pos + lz->offset - lz->cyclic_buffer_size
+			: 0;
+#endif
+
+		const uint8_t *cur = lz->buffer + lz->read_pos;
+
+#ifdef HASH_ARRAY_2
+		uint32_t hash_2_value;
+#	ifdef HASH_ARRAY_3
+		uint32_t hash_3_value;
+		uint32_t hash_value;
+		HASH_CALC();
+		lz->hash[HASH_3_OFFSET + hash_3_value]
+				= lz->read_pos + lz->offset;
+#	else
+		uint32_t hash_value;
+		HASH_CALC();
+#	endif
+		lz->hash[hash_2_value] = lz->read_pos + lz->offset;
+#else
+		uint32_t hash_value;
+		HASH_CALC();
+#endif
+
+		uint32_t cur_match = lz->hash[FIX_HASH_SIZE + hash_value];
+		lz->hash[FIX_HASH_SIZE + hash_value]
+				= lz->read_pos + lz->offset;
+
+#ifdef IS_HASH_CHAIN
+		lz->son[lz->cyclic_buffer_pos] = cur_match;
+#else
+		uint32_t *ptr0 = lz->son + (lz->cyclic_buffer_pos << 1) + 1;
+		uint32_t *ptr1 = lz->son + (lz->cyclic_buffer_pos << 1);
+
+		uint32_t len0 = NUM_HASH_DIRECT_BYTES;
+		uint32_t len1 = NUM_HASH_DIRECT_BYTES;
+		uint32_t count = lz->cut_value;
+
+		while (true) {
+			if (cur_match <= match_min_pos || count-- == 0) {
+				*ptr0 = EMPTY_HASH_VALUE;
+				*ptr1 = EMPTY_HASH_VALUE;
+				break;
+			}
+
+			const uint32_t delta = lz->read_pos
+					+ lz->offset - cur_match;
+			const uint32_t cyclic_pos
+					= delta <= lz->cyclic_buffer_pos
+					? lz->cyclic_buffer_pos - delta
+					: lz->cyclic_buffer_pos - delta
+						+ lz->cyclic_buffer_size;
+			uint32_t *pair = lz->son + (cyclic_pos << 1);
+
+			const uint8_t *pb = lz->buffer + cur_match
+					- lz->offset;
+			uint32_t len = MIN(len0, len1);
+
+			if (pb[len] == cur[len]) {
+				while (++len != len_limit)
+					if (pb[len] != cur[len])
+						break;
+
+				if (len == len_limit) {
+					*ptr1 = pair[0];
+					*ptr0 = pair[1];
+					break;
+				}
+			}
+
+			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;
+			}
+		}
+#endif
+
+		move_pos();
+
+	} while (--num != 0);
+
+	return;
+}
diff --git a/src/liblzma/lz/match_h.h b/src/liblzma/lz/match_h.h
new file mode 100644
index 00000000..2eae90ba
--- /dev/null
+++ b/src/liblzma/lz/match_h.h
@@ -0,0 +1,69 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       match_h.h
+/// \brief      Header template for different match finders
+//
+//  Copyright (C) 1999-2006 Igor Pavlov
+//  Copyright (C) 2007 Lasse Collin
+//
+//  This library is free software; you can redistribute it and/or
+//  modify it under the terms of the GNU Lesser General Public
+//  License as published by the Free Software Foundation; either
+//  version 2.1 of the License, or (at your option) any later version.
+//
+//  This library is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+//  Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include "lz_encoder_private.h"
+
+
+//////////////////////
+// Global constants //
+//////////////////////
+
+#undef LZMA_HASH_SIZE
+#undef LZMA_FIX_HASH_SIZE
+#undef LZMA_HASH_SIZE_C
+#undef LZMA_FIX_HASH_SIZE_C
+
+#define LZMA_HASH_SIZE(mf_name) LZMA_HASH_SIZE_C(mf_name)
+#define LZMA_FIX_HASH_SIZE(mf_name) LZMA_FIX_HASH_SIZE_C(mf_name)
+
+#define LZMA_HASH_SIZE_C(mf_name) \
+	const uint32_t LZMA_ ## mf_name ## _HASH_SIZE
+
+#define LZMA_FIX_HASH_SIZE_C(mf_name) \
+	const uint32_t LZMA_ ## mf_name ## _FIX_HASH_SIZE
+
+extern LZMA_HASH_SIZE(LZMA_MATCH_FINDER_NAME_UPPER);
+extern LZMA_FIX_HASH_SIZE(LZMA_MATCH_FINDER_NAME_UPPER);
+
+
+///////////////
+// Functions //
+///////////////
+
+#undef LZMA_GET_MATCHES
+#undef LZMA_SKIP
+#undef LZMA_GET_MATCHES_C
+#undef LZMA_SKIP_C
+
+#define LZMA_GET_MATCHES(mf_name) LZMA_GET_MATCHES_C(mf_name)
+#define LZMA_SKIP(mf_name) LZMA_SKIP_C(mf_name)
+
+#define LZMA_GET_MATCHES_C(mf_name) \
+	extern void lzma_ ## mf_name ## _get_matches( \
+			lzma_lz_encoder *restrict lz, \
+			uint32_t *restrict distances)
+
+#define LZMA_SKIP_C(mf_name) \
+	extern void lzma_ ## mf_name ## _skip( \
+			lzma_lz_encoder *lz, uint32_t num)
+
+LZMA_GET_MATCHES(LZMA_MATCH_FINDER_NAME_LOWER);
+
+LZMA_SKIP(LZMA_MATCH_FINDER_NAME_LOWER);
diff --git a/src/liblzma/lzma.pc.in b/src/liblzma/lzma.pc.in
new file mode 100644
index 00000000..5bf9bb10
--- /dev/null
+++ b/src/liblzma/lzma.pc.in
@@ -0,0 +1,11 @@
+prefix=@prefix@
+exec_prefix=@exec_prefix@
+libdir=@libdir@
+includedir=@includedir@
+
+Name: liblzma
+Description: LZMA compression library
+URL: http://tukaani.org/lzma/
+Version: @PACKAGE_VERSION@
+Cflags: -I${includedir}
+Libs: -L${libdir} -llzma
diff --git a/src/liblzma/lzma/Makefile.am b/src/liblzma/lzma/Makefile.am
new file mode 100644
index 00000000..48f3bb23
--- /dev/null
+++ b/src/liblzma/lzma/Makefile.am
@@ -0,0 +1,43 @@
+##
+##  Copyright (C) 2007 Lasse Collin
+##
+##  This library is free software; you can redistribute it and/or
+##  modify it under the terms of the GNU Lesser General Public
+##  License as published by the Free Software Foundation; either
+##  version 2.1 of the License, or (at your option) any later version.
+##
+##  This library is distributed in the hope that it will be useful,
+##  but WITHOUT ANY WARRANTY; without even the implied warranty of
+##  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+##  Lesser General Public License for more details.
+##
+
+noinst_LTLIBRARIES = liblzma4.la
+liblzma4_la_CPPFLAGS = \
+	-I@top_srcdir@/src/liblzma/api \
+	-I@top_srcdir@/src/liblzma/common \
+	-I@top_srcdir@/src/liblzma/lz \
+	-I@top_srcdir@/src/liblzma/rangecoder
+
+liblzma4_la_SOURCES = \
+	lzma_common.h \
+	lzma_literal.c \
+	lzma_literal.h
+
+if COND_MAIN_ENCODER
+liblzma4_la_SOURCES += \
+	lzma_encoder.h \
+	lzma_encoder.c \
+	lzma_encoder_presets.c \
+	lzma_encoder_private.h \
+	lzma_encoder_init.c \
+	lzma_encoder_features.c \
+	lzma_encoder_getoptimum.c \
+	lzma_encoder_getoptimumfast.c
+endif
+
+if COND_MAIN_DECODER
+liblzma4_la_SOURCES += \
+	lzma_decoder.c \
+	lzma_decoder.h
+endif
diff --git a/src/liblzma/lzma/lzma_common.h b/src/liblzma/lzma/lzma_common.h
new file mode 100644
index 00000000..4ff59ae6
--- /dev/null
+++ b/src/liblzma/lzma/lzma_common.h
@@ -0,0 +1,128 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       lzma_common.h
+/// \brief      Private definitions common to LZMA encoder and decoder
+//
+//  Copyright (C) 1999-2006 Igor Pavlov
+//  Copyright (C) 2007 Lasse Collin
+//
+//  This library is free software; you can redistribute it and/or
+//  modify it under the terms of the GNU Lesser General Public
+//  License as published by the Free Software Foundation; either
+//  version 2.1 of the License, or (at your option) any later version.
+//
+//  This library is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+//  Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#ifndef LZMA_LZMA_COMMON_H
+#define LZMA_LZMA_COMMON_H
+
+#include "common.h"
+#include "lzma_literal.h"
+#include "range_common.h"
+
+
+///////////////
+// Constants //
+///////////////
+
+#define REP_DISTANCES 4
+#define STATES 12
+#define LIT_STATES 7
+
+#define POS_SLOT_BITS 6
+#define DICT_LOG_SIZE_MAX 30
+#define DIST_TABLE_SIZE_MAX (DICT_LOG_SIZE_MAX * 2)
+#if (UINT32_C(1) << DICT_LOG_SIZE_MAX) != LZMA_DICTIONARY_SIZE_MAX
+#	error DICT_LOG_SIZE_MAX is inconsistent with LZMA_DICTIONARY_SIZE_MAX
+#endif
+
+// 2 is for speed optimization
+#define LEN_TO_POS_STATES_BITS 2
+#define LEN_TO_POS_STATES (1 << LEN_TO_POS_STATES_BITS)
+
+#define MATCH_MIN_LEN 2
+
+#define ALIGN_BITS 4
+#define ALIGN_TABLE_SIZE (1 << ALIGN_BITS)
+#define ALIGN_MASK (ALIGN_TABLE_SIZE - 1)
+
+#define START_POS_MODEL_INDEX 4
+#define END_POS_MODEL_INDEX 14
+#define POS_MODELS (END_POS_MODEL_INDEX - START_POS_MODEL_INDEX)
+
+#define FULL_DISTANCES (1 << (END_POS_MODEL_INDEX / 2))
+
+#define LIT_POS_STATES_BITS_MAX LZMA_LITERAL_POS_BITS_MAX
+#define LIT_CONTEXT_BITS_MAX LZMA_LITERAL_CONTEXT_BITS_MAX
+
+#define POS_STATES_BITS_MAX LZMA_POS_BITS_MAX
+#define POS_STATES_MAX (1 << POS_STATES_BITS_MAX)
+
+
+// Length coder & Length price table encoder
+#define LEN_LOW_BITS 3
+#define LEN_LOW_SYMBOLS (1 << LEN_LOW_BITS)
+#define LEN_MID_BITS 3
+#define LEN_MID_SYMBOLS (1 << LEN_MID_BITS)
+#define LEN_HIGH_BITS 8
+#define LEN_HIGH_SYMBOLS (1 << LEN_HIGH_BITS)
+#define LEN_SYMBOLS (LEN_LOW_SYMBOLS + LEN_MID_SYMBOLS + LEN_HIGH_SYMBOLS)
+#define LEN_SPEC_SYMBOLS (LOW_LOW_SYMBOLS + LEN_MID_LEN_SYMBOLS)
+#define MATCH_MAX_LEN (MATCH_MIN_LEN + LEN_SYMBOLS - 1)
+
+// Total number of probs in a Len Encoder
+#define LEN_CODER_TOTAL_PROBS (LEN_HIGH_CODER + LEN_HIGH_SYMBOLS)
+
+// Price table size of Len Encoder
+#define LEN_PRICES (LEN_SYMBOLS << POS_STATES_BITS_MAX)
+
+
+// Optimal - Number of entries in the optimum array.
+#define OPTS (1 << 12)
+
+
+// Miscellaneous
+#define INFINITY_PRICE 0x0FFFFFFF
+
+
+////////////
+// Macros //
+////////////
+
+#define get_len_to_pos_state(len) \
+	((len) < LEN_TO_POS_STATES + MATCH_MIN_LEN \
+		? (len) - MATCH_MIN_LEN \
+		: LEN_TO_POS_STATES - 1)
+
+
+///////////
+// State //
+///////////
+
+// Used for updating strm->data->state in both encoder and decoder.
+
+#define update_char(index) \
+	index = ((index) < 4 \
+			? 0 \
+			: ((index) < 10 \
+				? (index) - 3 \
+				: (index) - 6))
+
+#define update_match(index) \
+	index = ((index) < LIT_STATES ? 7 : 10)
+
+#define update_rep(index) \
+	index = ((index) < LIT_STATES ? 8 : 11)
+
+#define update_short_rep(index) \
+	index = ((index) < LIT_STATES ? 9 : 11)
+
+#define is_char_state(index) \
+	((index) < LIT_STATES)
+
+#endif
diff --git a/src/liblzma/lzma/lzma_decoder.c b/src/liblzma/lzma/lzma_decoder.c
new file mode 100644
index 00000000..6e2c166d
--- /dev/null
+++ b/src/liblzma/lzma/lzma_decoder.c
@@ -0,0 +1,844 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       lzma_decoder.c
+/// \brief      LZMA decoder
+//
+//  Copyright (C) 1999-2006 Igor Pavlov
+//  Copyright (C) 2007 Lasse Collin
+//
+//  This library is free software; you can redistribute it and/or
+//  modify it under the terms of the GNU Lesser General Public
+//  License as published by the Free Software Foundation; either
+//  version 2.1 of the License, or (at your option) any later version.
+//
+//  This library is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+//  Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include "lzma_common.h"
+#include "lzma_decoder.h"
+#include "lz_decoder.h"
+#include "range_decoder.h"
+
+
+/// REQUIRED_IN_BUFFER_SIZE is the number of required input bytes
+/// for the worst case: longest match with longest distance.
+/// LZMA_IN_BUFFER_SIZE must be larger than REQUIRED_IN_BUFFER_SIZE.
+/// 23 bits = 2 (match select) + 10 (len) + 6 (distance) + 4 (align)
+///         + 1 (rc_normalize)
+///
+/// \todo       Is this correct for sure?
+///
+#define REQUIRED_IN_BUFFER_SIZE \
+	((23 * (BIT_MODEL_TOTAL_BITS - MOVE_BITS + 1) + 26 + 9) / 8)
+
+
+// Length decoders are easiest to have as macros, because they use range
+// decoder macros, which use local variables rc_range and rc_code.
+
+#define length_decode(target, len_decoder, pos_state) \
+do { \
+	if_bit_0(len_decoder.choice) { \
+		update_bit_0(len_decoder.choice); \
+		target = MATCH_MIN_LEN; \
+		bittree_decode(target, \
+				len_decoder.low[pos_state], LEN_LOW_BITS); \
+	} else { \
+		update_bit_1(len_decoder.choice); \
+		if_bit_0(len_decoder.choice2) { \
+			update_bit_0(len_decoder.choice2); \
+			target = MATCH_MIN_LEN + LEN_LOW_SYMBOLS; \
+			bittree_decode(target, len_decoder.mid[pos_state], \
+					LEN_MID_BITS); \
+		} else { \
+			update_bit_1(len_decoder.choice2); \
+			target = MATCH_MIN_LEN + LEN_LOW_SYMBOLS \
+					+ LEN_MID_SYMBOLS; \
+			bittree_decode(target, len_decoder.high, \
+					LEN_HIGH_BITS); \
+		} \
+	} \
+} while (0)
+
+
+#define length_decode_dummy(target, len_decoder, pos_state) \
+do { \
+	if_bit_0(len_decoder.choice) { \
+		update_bit_0_dummy(); \
+		target = MATCH_MIN_LEN; \
+		bittree_decode_dummy(target, \
+				len_decoder.low[pos_state], LEN_LOW_BITS); \
+	} else { \
+		update_bit_1_dummy(); \
+		if_bit_0(len_decoder.choice2) { \
+			update_bit_0_dummy(); \
+			target = MATCH_MIN_LEN + LEN_LOW_SYMBOLS; \
+			bittree_decode_dummy(target, \
+					len_decoder.mid[pos_state], \
+					LEN_MID_BITS); \
+		} else { \
+			update_bit_1_dummy(); \
+			target = MATCH_MIN_LEN + LEN_LOW_SYMBOLS \
+					+ LEN_MID_SYMBOLS; \
+			bittree_decode_dummy(target, len_decoder.high, \
+					LEN_HIGH_BITS); \
+		} \
+	} \
+} while (0)
+
+
+typedef struct {
+	probability choice;
+	probability choice2;
+	probability low[POS_STATES_MAX][LEN_LOW_SYMBOLS];
+	probability mid[POS_STATES_MAX][LEN_MID_SYMBOLS];
+	probability high[LEN_HIGH_SYMBOLS];
+} lzma_length_decoder;
+
+
+struct lzma_coder_s {
+	/// Data of the next coder, if any.
+	lzma_next_coder next;
+
+	/// Sliding output window a.k.a. dictionary a.k.a. history buffer.
+	lzma_lz_decoder lz;
+
+	// Range coder
+	lzma_range_decoder rc;
+
+	// State
+	uint32_t state;
+	uint32_t rep0;      ///< Distance of the latest match
+	uint32_t rep1;      ///< Distance of second latest match
+	uint32_t rep2;      ///< Distance of third latest match
+	uint32_t rep3;      ///< Distance of fourth latest match
+	uint32_t pos_bits;
+	uint32_t pos_mask;
+	uint32_t now_pos; // Lowest 32-bits are enough here.
+
+	lzma_literal_coder *literal_coder;
+
+	/// If 1, it's a match. Otherwise it's a single 8-bit literal.
+	probability is_match[STATES][POS_STATES_MAX];
+
+	/// If 1, it's a repeated match. The distance is one of rep0 .. rep3.
+	probability is_rep[STATES];
+
+	/// If 0, distance of a repeated match is rep0.
+	/// Otherwise check is_rep1.
+	probability is_rep0[STATES];
+
+	/// If 0, distance of a repeated match is rep1.
+	/// Otherwise check is_rep2.
+	probability is_rep1[STATES];
+
+	/// If 0, distance of a repeated match is rep2. Otherwise it is rep3.
+	probability is_rep2[STATES];
+
+	/// If 1, the repeated match has length of one byte. Otherwise
+	/// the length is decoded from rep_match_len_decoder.
+	probability is_rep0_long[STATES][POS_STATES_MAX];
+
+	probability pos_slot_decoder[LEN_TO_POS_STATES][1 << POS_SLOT_BITS];
+	probability pos_decoders[FULL_DISTANCES - END_POS_MODEL_INDEX];
+	probability pos_align_decoder[1 << ALIGN_BITS];
+
+	/// Length of a match
+	lzma_length_decoder len_decoder;
+
+	/// Length of a repeated match.
+	lzma_length_decoder rep_match_len_decoder;
+
+	/// The first five bytes of LZMA compressed data are treated
+	/// specially. Once they are read, this stays at zero.
+	size_t init_bytes_left;
+};
+
+
+/// \brief      Check if the next iteration of the decoder loop can be run.
+///
+/// \note       There must always be REQUIRED_IN_BUFFER_SIZE bytes
+///             readable space!
+///
+static bool lzma_attribute((pure))
+decode_dummy(const lzma_coder *restrict coder,
+		const uint8_t *restrict in, size_t in_pos_local,
+		const size_t in_size, uint32_t rc_range, uint32_t rc_code,
+		uint32_t state, uint32_t rep0, const uint32_t now_pos)
+{
+	uint32_t rc_bound;
+
+	do {
+		const uint32_t pos_state = now_pos & coder->pos_mask;
+
+		if_bit_0(coder->is_match[state][pos_state]) {
+			// It's a literal i.e. a single 8-bit byte.
+
+			update_bit_0_dummy();
+
+			const probability *subcoder = literal_get_subcoder(
+					coder->literal_coder,
+					now_pos, lz_get_byte(coder->lz, 0));
+			uint32_t symbol = 1;
+
+			if (!is_char_state(state)) {
+				// Decode literal with match byte.
+
+				assert(rep0 != UINT32_MAX);
+				uint32_t match_byte
+						= lz_get_byte(coder->lz, rep0);
+
+				do {
+					match_byte <<= 1;
+					const uint32_t match_bit
+							= match_byte & 0x100;
+					const uint32_t subcoder_index = 0x100
+							+ match_bit + symbol;
+
+					if_bit_0(subcoder[subcoder_index]) {
+						update_bit_0_dummy();
+						symbol <<= 1;
+						if (match_bit != 0)
+							break;
+					} else {
+						update_bit_1_dummy();
+						symbol = (symbol << 1) | 1;
+						if (match_bit == 0)
+							break;
+					}
+				} while (symbol < 0x100);
+			}
+
+			// Decode literal without match byte. This is also
+			// the tail of the with-match-byte function.
+			while (symbol < 0x100) {
+				if_bit_0(subcoder[symbol]) {
+					update_bit_0_dummy();
+					symbol <<= 1;
+				} else {
+					update_bit_1_dummy();
+					symbol = (symbol << 1) | 1;
+				}
+			}
+
+			break;
+		}
+
+		update_bit_1_dummy();
+		uint32_t len;
+
+		if_bit_0(coder->is_rep[state]) {
+			update_bit_0_dummy();
+			length_decode_dummy(len, coder->len_decoder, pos_state);
+			update_match(state);
+
+			const uint32_t len_to_pos_state
+					= get_len_to_pos_state(len);
+			uint32_t pos_slot = 0;
+			bittree_decode_dummy(pos_slot, coder->pos_slot_decoder[
+					len_to_pos_state], POS_SLOT_BITS);
+			assert(pos_slot <= 63);
+
+			if (pos_slot >= START_POS_MODEL_INDEX) {
+				uint32_t direct_bits = (pos_slot >> 1) - 1;
+				assert(direct_bits >= 1 && direct_bits <= 31);
+				rep0 = 2 | (pos_slot & 1);
+
+				if (pos_slot < END_POS_MODEL_INDEX) {
+					assert(direct_bits <= 5);
+					rep0 <<= direct_bits;
+					assert(rep0 <= 96);
+					// -1 is fine, because
+					// bittree_reverse_decode()
+					// starts from table index [1]
+					// (not [0]).
+					assert((int32_t)(rep0 - pos_slot - 1)
+							>= -1);
+					assert((int32_t)(rep0 - pos_slot - 1)
+							<= 82);
+					// We add the result to rep0, so rep0
+					// must not be part of second argument
+					// of the macro.
+					const int32_t offset
+						= rep0 - pos_slot - 1;
+					bittree_reverse_decode_dummy(
+						coder->pos_decoders + offset,
+						direct_bits);
+				} else {
+					// Decode direct bits
+					assert(pos_slot >= 14);
+					assert(direct_bits >= 6);
+					direct_bits -= ALIGN_BITS;
+					assert(direct_bits >= 2);
+					do {
+						rc_normalize();
+						rc_range >>= 1;
+						const uint32_t t
+							= (rc_code - rc_range)
+							>> 31;
+						rc_code -= rc_range & (t - 1);
+					} while (--direct_bits > 0);
+					rep0 <<= ALIGN_BITS;
+
+					bittree_reverse_decode_dummy(
+						coder->pos_align_decoder,
+						ALIGN_BITS);
+				}
+			}
+
+		} else {
+			update_bit_1_dummy();
+
+			if_bit_0(coder->is_rep0[state]) {
+				update_bit_0_dummy();
+
+				if_bit_0(coder->is_rep0_long[state][
+						pos_state]) {
+					update_bit_0_dummy();
+					break;
+				} else {
+					update_bit_1_dummy();
+				}
+
+			} else {
+				update_bit_1_dummy();
+
+				if_bit_0(coder->is_rep1[state]) {
+					update_bit_0_dummy();
+				} else {
+					update_bit_1_dummy();
+
+					if_bit_0(coder->is_rep2[state]) {
+						update_bit_0_dummy();
+					} else {
+						update_bit_1_dummy();
+					}
+				}
+			}
+
+			length_decode_dummy(len, coder->rep_match_len_decoder,
+					pos_state);
+		}
+	} while (0);
+
+	rc_normalize();
+
+	// Validate the buffer position.
+	if (in_pos_local > in_size)
+		return false;
+
+	return true;
+}
+
+
+static bool
+decode_real(lzma_coder *restrict coder, const uint8_t *restrict in,
+		size_t *restrict in_pos, size_t in_size, bool has_safe_buffer)
+{
+	////////////////////
+	// Initialization //
+	////////////////////
+
+	while (coder->init_bytes_left > 0) {
+		if (*in_pos == in_size)
+			return false;
+
+		coder->rc.code = (coder->rc.code << 8) | in[*in_pos];
+		++*in_pos;
+		--coder->init_bytes_left;
+	}
+
+
+	///////////////
+	// Variables //
+	///////////////
+
+	// Making local copies of often-used variables improves both
+	// speed and readability.
+
+	// Range decoder
+	rc_to_local(coder->rc);
+
+	// State
+	uint32_t state = coder->state;
+	uint32_t rep0 = coder->rep0;
+	uint32_t rep1 = coder->rep1;
+	uint32_t rep2 = coder->rep2;
+	uint32_t rep3 = coder->rep3;
+
+	// Misc
+	uint32_t now_pos = coder->now_pos;
+
+	// Variables derived from decoder settings
+	const uint32_t pos_mask = coder->pos_mask;
+
+	size_t in_pos_local = *in_pos; // Local copy
+	size_t in_limit;
+	if (in_size <= REQUIRED_IN_BUFFER_SIZE)
+		in_limit = 0;
+	else
+		in_limit = in_size - REQUIRED_IN_BUFFER_SIZE;
+
+
+	while (coder->lz.pos < coder->lz.limit && (in_pos_local < in_limit
+			|| (has_safe_buffer && decode_dummy(
+				coder, in, in_pos_local, in_size,
+				rc_range, rc_code, state, rep0, now_pos)))) {
+
+		/////////////////////
+		// Actual decoding //
+		/////////////////////
+
+		const uint32_t pos_state = now_pos & pos_mask;
+
+		if_bit_0(coder->is_match[state][pos_state]) {
+			update_bit_0(coder->is_match[state][pos_state]);
+
+			// It's a literal i.e. a single 8-bit byte.
+
+			probability *subcoder = literal_get_subcoder(
+					coder->literal_coder,
+					now_pos, lz_get_byte(coder->lz, 0));
+			uint32_t symbol = 1;
+
+			if (!is_char_state(state)) {
+				// Decode literal with match byte.
+
+				assert(rep0 != UINT32_MAX);
+				uint32_t match_byte
+						= lz_get_byte(coder->lz, rep0);
+
+				do {
+					match_byte <<= 1;
+					const uint32_t match_bit
+							= match_byte & 0x100;
+					const uint32_t subcoder_index = 0x100
+							+ match_bit + symbol;
+
+					if_bit_0(subcoder[subcoder_index]) {
+						update_bit_0(subcoder[
+							subcoder_index]);
+						symbol <<= 1;
+						if (match_bit != 0)
+							break;
+					} else {
+						update_bit_1(subcoder[
+							subcoder_index]);
+						symbol = (symbol << 1) | 1;
+						if (match_bit == 0)
+							break;
+					}
+				} while (symbol < 0x100);
+			}
+
+			// Decode literal without match byte. This is also
+			// the tail of the with-match-byte function.
+			while (symbol < 0x100) {
+				if_bit_0(subcoder[symbol]) {
+					update_bit_0(subcoder[symbol]);
+					symbol <<= 1;
+				} else {
+					update_bit_1(subcoder[symbol]);
+					symbol = (symbol << 1) | 1;
+				}
+			}
+
+			// Put the decoded byte to the dictionary, update the
+			// decoder state, and start a new decoding loop.
+			coder->lz.dict[coder->lz.pos++] = (uint8_t)(symbol);
+			++now_pos;
+			update_char(state);
+			continue;
+		}
+
+		// Instead of a new byte we are going to get a byte range
+		// (distance and length) which will be repeated from our
+		// output history.
+
+		update_bit_1(coder->is_match[state][pos_state]);
+		uint32_t len;
+
+		if_bit_0(coder->is_rep[state]) {
+			update_bit_0(coder->is_rep[state]);
+
+			// Not a repeated match
+			//
+			// We will decode a new distance and store
+			// the value to rep0.
+
+			// The latest three match distances are kept in
+			// memory in case there are repeated matches.
+			rep3 = rep2;
+			rep2 = rep1;
+			rep1 = rep0;
+
+			// Decode the length of the match.
+			length_decode(len, coder->len_decoder, pos_state);
+
+			update_match(state);
+
+			const uint32_t len_to_pos_state
+					= get_len_to_pos_state(len);
+			uint32_t pos_slot = 0;
+			bittree_decode(pos_slot, coder->pos_slot_decoder[
+					len_to_pos_state], POS_SLOT_BITS);
+			assert(pos_slot <= 63);
+
+			if (pos_slot >= START_POS_MODEL_INDEX) {
+				uint32_t direct_bits = (pos_slot >> 1) - 1;
+				assert(direct_bits >= 1 && direct_bits <= 30);
+				rep0 = 2 | (pos_slot & 1);
+
+				if (pos_slot < END_POS_MODEL_INDEX) {
+					assert(direct_bits <= 5);
+					rep0 <<= direct_bits;
+					assert(rep0 <= 96);
+					// -1 is fine, because
+					// bittree_reverse_decode()
+					// starts from table index [1]
+					// (not [0]).
+					assert((int32_t)(rep0 - pos_slot - 1)
+							>= -1);
+					assert((int32_t)(rep0 - pos_slot - 1)
+							<= 82);
+					// We add the result to rep0, so rep0
+					// must not be part of second argument
+					// of the macro.
+					const int32_t offset
+						= rep0 - pos_slot - 1;
+					bittree_reverse_decode(rep0,
+						coder->pos_decoders + offset,
+						direct_bits);
+				} else {
+					// Decode direct bits
+					assert(pos_slot >= 14);
+					assert(direct_bits >= 6);
+					direct_bits -= ALIGN_BITS;
+					assert(direct_bits >= 2);
+					do {
+						rc_normalize();
+						rc_range >>= 1;
+						const uint32_t t
+							= (rc_code - rc_range)
+							>> 31;
+						rc_code -= rc_range & (t - 1);
+						rep0 = (rep0 << 1) | (1 - t);
+					} while (--direct_bits > 0);
+					rep0 <<= ALIGN_BITS;
+
+					bittree_reverse_decode(rep0,
+						coder->pos_align_decoder,
+						ALIGN_BITS);
+
+					if (rep0 == UINT32_MAX) {
+						// End of Payload Marker found.
+						coder->lz.eopm_detected = true;
+						break;
+					}
+				}
+			} else {
+				rep0 = pos_slot;
+			}
+
+		} else {
+			update_bit_1(coder->is_rep[state]);
+
+			// Repeated match
+			//
+			// The match distance is a value that we have had
+			// earlier. The latest four match distances are
+			// available as rep0, rep1, rep2 and rep3. We will
+			// now decode which of them is the new distance.
+
+			if_bit_0(coder->is_rep0[state]) {
+				update_bit_0(coder->is_rep0[state]);
+
+				// The distance is rep0.
+
+				if_bit_0(coder->is_rep0_long[state][
+						pos_state]) {
+					update_bit_0(coder->is_rep0_long[
+							state][pos_state]);
+
+					// Repeating exactly one byte. For
+					// simplicity, it is done here inline
+					// instead of at the end of the main
+					// loop.
+
+					update_short_rep(state);
+
+					// Security/sanity checks. See the end
+					// of the main loop for explanation
+					// of these.
+					if ((rep0 >= coder->lz.pos
+							&& !coder->lz.is_full)
+							|| in_pos_local
+								> in_size)
+						goto error;
+
+					// Repeat one byte and start a new
+					// decoding loop.
+					coder->lz.dict[coder->lz.pos]
+							= lz_get_byte(
+							coder->lz, rep0);
+					++coder->lz.pos;
+					++now_pos;
+					continue;
+
+				} else {
+					update_bit_1(coder->is_rep0_long[
+							state][pos_state]);
+
+					// Repeating more than one byte at
+					// distance of rep0.
+				}
+
+			} else {
+				update_bit_1(coder->is_rep0[state]);
+
+				// The distance is rep1, rep2 or rep3. Once
+				// we find out which one of these three, it
+				// is stored to rep0 and rep1, rep2 and rep3
+				// are updated accordingly.
+
+				uint32_t distance;
+
+				if_bit_0(coder->is_rep1[state]) {
+					update_bit_0(coder->is_rep1[state]);
+					distance = rep1;
+				} else {
+					update_bit_1(coder->is_rep1[state]);
+
+					if_bit_0(coder->is_rep2[state]) {
+						update_bit_0(coder->is_rep2[
+								state]);
+						distance = rep2;
+					} else {
+						update_bit_1(coder->is_rep2[
+								state]);
+						distance = rep3;
+						rep3 = rep2;
+					}
+
+					rep2 = rep1;
+				}
+
+				rep1 = rep0;
+				rep0 = distance;
+			}
+
+			// Decode the length of the repeated match.
+			length_decode(len, coder->rep_match_len_decoder,
+					pos_state);
+
+			update_rep(state);
+		}
+
+
+		/////////////////////////////////
+		// Repeat from history buffer. //
+		/////////////////////////////////
+
+		// The length is always between these limits. There is no way
+		// to trigger the algorithm to set len outside this range.
+		assert(len >= MATCH_MIN_LEN);
+		assert(len <= MATCH_MAX_LEN);
+
+		now_pos += len;
+
+		// Validate the buffer position to avoid buffer overflows
+		// on corrupted input data.
+		if (in_pos_local > in_size)
+			goto error;
+
+		// Repeat len bytes from distance of rep0.
+		if (!lzma_lz_out_repeat(&coder->lz, rep0, len))
+			goto error;
+	}
+
+	rc_normalize();
+
+
+	/////////////////////////////////
+	// Update the *data structure. //
+	/////////////////////////////////
+
+	// Range decoder
+	rc_from_local(coder->rc);
+
+	// State
+	coder->state = state;
+	coder->rep0 = rep0;
+	coder->rep1 = rep1;
+	coder->rep2 = rep2;
+	coder->rep3 = rep3;
+
+	// Misc
+	coder->now_pos = now_pos;
+	*in_pos = in_pos_local;
+
+	return false;
+
+error:
+	return true;
+}
+
+
+static void
+lzma_decoder_end(lzma_coder *coder, lzma_allocator *allocator)
+{
+	lzma_next_coder_end(&coder->next, allocator);
+	lzma_lz_decoder_end(&coder->lz, allocator);
+	lzma_literal_end(&coder->literal_coder, allocator);
+	lzma_free(coder, allocator);
+	return;
+}
+
+
+extern lzma_ret
+lzma_lzma_decoder_init(lzma_next_coder *next, lzma_allocator *allocator,
+		const lzma_filter_info *filters)
+{
+	// Validate pos_bits. Other options are validated by the
+	// respective initialization functions.
+	const lzma_options_lzma *options = filters[0].options;
+	if (options->pos_bits > LZMA_POS_BITS_MAX)
+		return LZMA_HEADER_ERROR;
+
+	// Allocate memory for the decoder if needed.
+	if (next->coder == NULL) {
+		next->coder = lzma_alloc(sizeof(lzma_coder), allocator);
+		if (next->coder == NULL)
+			return LZMA_MEM_ERROR;
+
+		// Initialize variables so that we know later that we don't
+		// have an existing decoder initialized.
+		next->coder->next = LZMA_NEXT_CODER_INIT;
+		next->coder->lz = LZMA_LZ_DECODER_INIT;
+		next->coder->literal_coder = NULL;
+	}
+
+	// Store the pos_bits and calculate pos_mask.
+	next->coder->pos_bits = options->pos_bits;
+	next->coder->pos_mask = (1U << next->coder->pos_bits) - 1;
+
+	// Allocate (if needed) and initialize the literal decoder.
+	{
+		const lzma_ret ret = lzma_literal_init(
+				&next->coder->literal_coder, allocator,
+				options->literal_context_bits,
+				options->literal_pos_bits);
+		if (ret != LZMA_OK) {
+			lzma_free(next->coder, allocator);
+			next->coder = NULL;
+			return ret;
+		}
+	}
+
+	// Allocate and initialize the LZ decoder.
+	{
+		const lzma_ret ret = lzma_lz_decoder_reset(
+				&next->coder->lz, allocator, &decode_real,
+				filters[0].uncompressed_size,
+				options->dictionary_size, MATCH_MAX_LEN);
+		if (ret != LZMA_OK) {
+			lzma_literal_end(&next->coder->literal_coder,
+					allocator);
+			lzma_free(next->coder, allocator);
+			next->coder = NULL;
+			return ret;
+		}
+	}
+
+	// State
+	next->coder->state = 0;
+	next->coder->rep0 = 0;
+	next->coder->rep1 = 0;
+	next->coder->rep2 = 0;
+	next->coder->rep3 = 0;
+	next->coder->pos_bits = options->pos_bits;
+	next->coder->pos_mask = (1 << next->coder->pos_bits) - 1;
+	next->coder->now_pos = 0;
+	next->coder->init_bytes_left = 5;
+
+	// Range decoder
+	rc_reset(next->coder->rc);
+
+	// Bit and bittree decoders
+	for (uint32_t i = 0; i < STATES; ++i) {
+		for (uint32_t j = 0; j <= next->coder->pos_mask; ++j) {
+			bit_reset(next->coder->is_match[i][j]);
+			bit_reset(next->coder->is_rep0_long[i][j]);
+		}
+
+		bit_reset(next->coder->is_rep[i]);
+		bit_reset(next->coder->is_rep0[i]);
+		bit_reset(next->coder->is_rep1[i]);
+		bit_reset(next->coder->is_rep2[i]);
+	}
+
+	for (uint32_t i = 0; i < LEN_TO_POS_STATES; ++i)
+		bittree_reset(next->coder->pos_slot_decoder[i], POS_SLOT_BITS);
+
+	for (uint32_t i = 0; i < FULL_DISTANCES - END_POS_MODEL_INDEX; ++i)
+		bit_reset(next->coder->pos_decoders[i]);
+
+	bittree_reset(next->coder->pos_align_decoder, ALIGN_BITS);
+
+	// Len decoders (also bit/bittree)
+	const uint32_t num_pos_states = 1 << next->coder->pos_bits;
+	bit_reset(next->coder->len_decoder.choice);
+	bit_reset(next->coder->len_decoder.choice2);
+	bit_reset(next->coder->rep_match_len_decoder.choice);
+	bit_reset(next->coder->rep_match_len_decoder.choice2);
+
+	for (uint32_t pos_state = 0; pos_state < num_pos_states; ++pos_state) {
+		bittree_reset(next->coder->len_decoder.low[pos_state],
+				LEN_LOW_BITS);
+		bittree_reset(next->coder->len_decoder.mid[pos_state],
+				LEN_MID_BITS);
+
+		bittree_reset(next->coder->rep_match_len_decoder.low[
+				pos_state], LEN_LOW_BITS);
+		bittree_reset(next->coder->rep_match_len_decoder.mid[
+				pos_state], LEN_MID_BITS);
+	}
+
+	bittree_reset(next->coder->len_decoder.high, LEN_HIGH_BITS);
+	bittree_reset(next->coder->rep_match_len_decoder.high, LEN_HIGH_BITS);
+
+	// Initialize the next decoder in the chain, if any.
+	{
+		const lzma_ret ret = lzma_next_filter_init(&next->coder->next,
+				allocator, filters + 1);
+		if (ret != LZMA_OK) {
+			lzma_decoder_end(next->coder, allocator);
+			return ret;
+		}
+	}
+
+	// Initialization successful. Set the function pointers.
+	next->code = &lzma_lz_decode;
+	next->end = &lzma_decoder_end;
+
+	return LZMA_OK;
+}
+
+
+extern bool
+lzma_lzma_decode_properties(lzma_options_lzma *options, uint8_t byte)
+{
+	if (byte > (4 * 5 + 4) * 9 + 8)
+		return true;
+
+	// See the file format specification to understand this.
+	options->pos_bits = byte / (9 * 5);
+	byte -= options->pos_bits * 9 * 5;
+	options->literal_pos_bits = byte / 9;
+	options->literal_context_bits = byte - options->literal_pos_bits * 9;
+
+	return false;
+}
diff --git a/src/liblzma/lzma/lzma_decoder.h b/src/liblzma/lzma/lzma_decoder.h
new file mode 100644
index 00000000..929c2bff
--- /dev/null
+++ b/src/liblzma/lzma/lzma_decoder.h
@@ -0,0 +1,41 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       lzma_decoder.h
+/// \brief      LZMA decoder API
+//
+//  Copyright (C) 1999-2006 Igor Pavlov
+//  Copyright (C) 2007 Lasse Collin
+//
+//  This library is free software; you can redistribute it and/or
+//  modify it under the terms of the GNU Lesser General Public
+//  License as published by the Free Software Foundation; either
+//  version 2.1 of the License, or (at your option) any later version.
+//
+//  This library is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+//  Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#ifndef LZMA_LZMA_DECODER_H
+#define LZMA_LZMA_DECODER_H
+
+#include "common.h"
+
+
+/// \brief      Allocates and initializes LZMA decoder
+extern lzma_ret lzma_lzma_decoder_init(lzma_next_coder *next,
+		lzma_allocator *allocator, const lzma_filter_info *filters);
+
+/// \brief      Decodes the LZMA Properties byte (lc/lp/pb)
+///
+/// \return     true if error occorred, false on success
+///
+extern bool lzma_lzma_decode_properties(
+		lzma_options_lzma *options, uint8_t byte);
+
+// There is no public lzma_lzma_encode() because lzma_lz_encode() works
+// as a wrapper for it.
+
+#endif
diff --git a/src/liblzma/lzma/lzma_encoder.c b/src/liblzma/lzma/lzma_encoder.c
new file mode 100644
index 00000000..f9c1e3fe
--- /dev/null
+++ b/src/liblzma/lzma/lzma_encoder.c
@@ -0,0 +1,413 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       lzma_encoder.c
+/// \brief      LZMA encoder
+//
+//  Copyright (C) 1999-2006 Igor Pavlov
+//  Copyright (C) 2007 Lasse Collin
+//
+//  This library is free software; you can redistribute it and/or
+//  modify it under the terms of the GNU Lesser General Public
+//  License as published by the Free Software Foundation; either
+//  version 2.1 of the License, or (at your option) any later version.
+//
+//  This library is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+//  Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+// NOTE: If you want to keep the line length in 80 characters, set
+//       tab width to 4 or less in your editor when editing this file.
+
+
+#include "lzma_encoder_private.h"
+
+
+////////////
+// Macros //
+////////////
+
+// These are as macros mostly because they use local range encoder variables.
+
+#define literal_encode(subcoder, symbol) \
+do { \
+	uint32_t context = 1; \
+	int i = 8; \
+	do { \
+		--i; \
+		const uint32_t bit = ((symbol) >> i) & 1; \
+		bit_encode(subcoder[context], bit); \
+		context = (context << 1) | bit; \
+	} while (i != 0); \
+} while (0)
+
+
+#define literal_encode_matched(subcoder, match_byte, symbol) \
+do { \
+	uint32_t context = 1; \
+	int i = 8; \
+	do { \
+		--i; \
+		uint32_t bit = ((symbol) >> i) & 1; \
+		const uint32_t match_bit = ((match_byte) >> i) & 1; \
+		const uint32_t subcoder_index = 0x100 + (match_bit << 8) + context; \
+		bit_encode(subcoder[subcoder_index], bit); \
+		context = (context << 1) | bit; \
+		if (match_bit != bit) { \
+			while (i != 0) { \
+				--i; \
+				bit = ((symbol) >> i) & 1; \
+				bit_encode(subcoder[context], bit); \
+				context = (context << 1) | bit; \
+			} \
+			break; \
+		} \
+	} while (i != 0); \
+} while (0)
+
+
+#define length_encode(length_encoder, symbol, pos_state, update_price) \
+do { \
+	\
+	if ((symbol) < LEN_LOW_SYMBOLS) { \
+		bit_encode_0((length_encoder).choice); \
+		bittree_encode((length_encoder).low[pos_state], \
+				LEN_LOW_BITS, symbol); \
+	} else { \
+		bit_encode_1((length_encoder).choice); \
+		if ((symbol) < LEN_LOW_SYMBOLS + LEN_MID_SYMBOLS) { \
+			bit_encode_0((length_encoder).choice2); \
+			bittree_encode((length_encoder).mid[pos_state], \
+					LEN_MID_BITS, \
+					(symbol) - LEN_LOW_SYMBOLS); \
+		} else { \
+			bit_encode_1((length_encoder).choice2); \
+			bittree_encode((length_encoder).high, LEN_HIGH_BITS, \
+					(symbol) - LEN_LOW_SYMBOLS \
+					- LEN_MID_SYMBOLS); \
+		} \
+	} \
+	if (update_price) \
+		if (--(length_encoder).counters[pos_state] == 0) \
+			lzma_length_encoder_update_table(&(length_encoder), pos_state); \
+} while (0)
+
+
+///////////////
+// Functions //
+///////////////
+
+/// \brief      Updates price table of the length encoder
+///
+/// All all the other prices in LZMA, these are used by lzma_get_optimum().
+///
+extern void
+lzma_length_encoder_update_table(lzma_length_encoder *lencoder,
+		const uint32_t pos_state)
+{
+	const uint32_t num_symbols = lencoder->table_size;
+	const uint32_t a0 = bit_get_price_0(lencoder->choice);
+	const uint32_t a1 = bit_get_price_1(lencoder->choice);
+	const uint32_t b0 = a1 + bit_get_price_0(lencoder->choice2);
+	const uint32_t b1 = a1 + bit_get_price_1(lencoder->choice2);
+
+	uint32_t *prices = lencoder->prices[pos_state];
+	uint32_t i = 0;
+
+	for (i = 0; i < num_symbols && i < LEN_LOW_SYMBOLS; ++i) {
+		prices[i] = a0;
+		bittree_get_price(prices[i], lencoder->low[pos_state],
+				LEN_LOW_BITS, i);
+	}
+
+	for (; i < num_symbols && i < LEN_LOW_SYMBOLS + LEN_MID_SYMBOLS; ++i) {
+		prices[i] = b0;
+		bittree_get_price(prices[i], lencoder->mid[pos_state],
+				LEN_MID_BITS, i - LEN_LOW_SYMBOLS);
+	}
+
+	for (; i < num_symbols; ++i) {
+		prices[i] = b1;
+		bittree_get_price(prices[i], lencoder->high, LEN_HIGH_BITS,
+				i - LEN_LOW_SYMBOLS - LEN_MID_SYMBOLS);
+	}
+
+	lencoder->counters[pos_state] = num_symbols;
+
+	return;
+}
+
+
+/**
+ * \brief       LZMA encoder
+ *
+ * \return      true if end of stream was reached, false otherwise.
+ */
+extern bool
+lzma_lzma_encode(lzma_coder *coder, uint8_t *restrict out,
+		size_t *restrict out_pos, size_t out_size)
+{
+	// Flush the range encoder's temporary buffer to out[].
+	// Return immediatelly if not everything could be flushed.
+	if (rc_flush_buffer(&coder->rc, out, out_pos, out_size))
+		return false;
+
+	// Return immediatelly if we have already finished our work.
+	if (coder->lz.stream_end_was_reached
+			&& coder->is_initialized
+			&& coder->lz.read_pos == coder->lz.write_pos
+			&& coder->additional_offset == 0)
+		return true;
+
+	// Local copies
+	rc_to_local(coder->rc);
+	size_t out_pos_local = *out_pos;
+	const uint32_t pos_mask = coder->pos_mask;
+	const bool best_compression = coder->best_compression;
+
+	// Initialize the stream if no data has been encoded yet.
+	if (!coder->is_initialized) {
+		if (coder->lz.read_pos == coder->lz.read_limit) {
+			// Cannot initialize, because there is no input data.
+			if (!coder->lz.stream_end_was_reached)
+				return false;
+
+			// If we get here, we are encoding an empty file.
+			// Initialization is skipped completely.
+			assert(coder->lz.write_pos == coder->lz.read_pos);
+
+		} else {
+			// Do the actual initialization.
+			uint32_t len;
+			uint32_t num_distance_pairs;
+			lzma_read_match_distances(coder, &len, &num_distance_pairs);
+
+			bit_encode_0(coder->is_match[coder->state][0]);
+			update_char(coder->state);
+
+			const uint8_t cur_byte = coder->lz.buffer[
+					coder->lz.read_pos - coder->additional_offset];
+			probability *subcoder = literal_get_subcoder(coder->literal_coder,
+					coder->now_pos, coder->previous_byte);
+			literal_encode(subcoder, cur_byte);
+
+			coder->previous_byte = cur_byte;
+			--coder->additional_offset;
+			++coder->now_pos;
+
+			assert(coder->additional_offset == 0);
+		}
+
+		// Initialization is done (except if empty file).
+		coder->is_initialized = true;
+	}
+
+	// Encoding loop
+	while (true) {
+		// Check that there is free output space.
+		if (out_pos_local == out_size)
+			break;
+
+		assert(rc_buffer_size == 0);
+
+		// Check that there is some input to process.
+		if (coder->lz.read_pos >= coder->lz.read_limit) {
+			// If end of input has been reached, we must keep
+			// encoding until additional_offset becomes zero.
+			if (!coder->lz.stream_end_was_reached
+					|| coder->additional_offset == 0)
+				break;
+		}
+
+		assert(coder->lz.read_pos <= coder->lz.write_pos);
+
+#ifndef NDEBUG
+		if (coder->lz.stream_end_was_reached) {
+			assert(coder->lz.read_limit == coder->lz.write_pos);
+		} else {
+			assert(coder->lz.read_limit + coder->lz.keep_size_after
+					== coder->lz.write_pos);
+		}
+#endif
+
+		const uint32_t pos_state = coder->now_pos & pos_mask;
+
+		uint32_t pos;
+		uint32_t len;
+
+		// Get optimal match (repeat position and length).
+		// Value ranges for pos:
+		//   - [0, REP_DISTANCES): repeated match
+		//   - [REP_DISTANCES, UINT32_MAX): match at (pos - REP_DISTANCES)
+		//   - UINT32_MAX: not a match but a literal
+		// Value ranges for len:
+		//   - [MATCH_MIN_LEN, MATCH_MAX_LEN]
+		if (best_compression)
+			lzma_get_optimum(coder, &pos, &len);
+		else
+			lzma_get_optimum_fast(coder, &pos, &len);
+
+		if (len == 1 && pos == UINT32_MAX) {
+			// It's a literal.
+			bit_encode_0(coder->is_match[coder->state][pos_state]);
+
+			const uint8_t cur_byte = coder->lz.buffer[
+					coder->lz.read_pos - coder->additional_offset];
+			probability *subcoder = literal_get_subcoder(coder->literal_coder,
+					coder->now_pos, coder->previous_byte);
+
+			if (is_char_state(coder->state)) {
+				literal_encode(subcoder, cur_byte);
+			} else {
+				const uint8_t match_byte = coder->lz.buffer[
+						coder->lz.read_pos
+						- coder->rep_distances[0] - 1
+						- coder->additional_offset];
+				literal_encode_matched(subcoder, match_byte, cur_byte);
+			}
+
+			update_char(coder->state);
+			coder->previous_byte = cur_byte;
+
+		} else {
+			// It's a match.
+			bit_encode_1(coder->is_match[coder->state][pos_state]);
+
+			if (pos < REP_DISTANCES) {
+				// It's a repeated match i.e. the same distance
+				// has been used earlier.
+				bit_encode_1(coder->is_rep[coder->state]);
+
+				if (pos == 0) {
+					bit_encode_0(coder->is_rep0[coder->state]);
+					const uint32_t symbol = (len == 1) ? 0 : 1;
+					bit_encode(coder->is_rep0_long[coder->state][pos_state],
+							symbol);
+				} else {
+					const uint32_t distance = coder->rep_distances[pos];
+					bit_encode_1(coder->is_rep0[coder->state]);
+
+					if (pos == 1) {
+						bit_encode_0(coder->is_rep1[coder->state]);
+					} else {
+						bit_encode_1(coder->is_rep1[coder->state]);
+						bit_encode(coder->is_rep2[coder->state], pos - 2);
+
+						if (pos == 3)
+							coder->rep_distances[3] = coder->rep_distances[2];
+
+						coder->rep_distances[2] = coder->rep_distances[1];
+					}
+
+					coder->rep_distances[1] = coder->rep_distances[0];
+					coder->rep_distances[0] = distance;
+				}
+
+				if (len == 1) {
+					update_short_rep(coder->state);
+				} else {
+					length_encode(coder->rep_match_len_encoder,
+							len - MATCH_MIN_LEN, pos_state,
+							best_compression);
+					update_rep(coder->state);
+				}
+
+			} else {
+				bit_encode_0(coder->is_rep[coder->state]);
+				update_match(coder->state);
+				length_encode(coder->len_encoder, len - MATCH_MIN_LEN,
+						pos_state, best_compression);
+				pos -= REP_DISTANCES;
+
+				const uint32_t pos_slot = get_pos_slot(pos);
+				const uint32_t len_to_pos_state = get_len_to_pos_state(len);
+				bittree_encode(coder->pos_slot_encoder[len_to_pos_state],
+						POS_SLOT_BITS, pos_slot);
+
+				if (pos_slot >= START_POS_MODEL_INDEX) {
+					const uint32_t footer_bits = (pos_slot >> 1) - 1;
+					const uint32_t base = (2 | (pos_slot & 1)) << footer_bits;
+					const uint32_t pos_reduced = pos - base;
+
+					if (pos_slot < END_POS_MODEL_INDEX) {
+						bittree_reverse_encode(
+								coder->pos_encoders + base - pos_slot - 1,
+								footer_bits, pos_reduced);
+					} else {
+						rc_encode_direct_bits(pos_reduced >> ALIGN_BITS,
+								footer_bits - ALIGN_BITS);
+						bittree_reverse_encode(coder->pos_align_encoder,
+								ALIGN_BITS, pos_reduced & ALIGN_MASK);
+						++coder->align_price_count;
+					}
+				}
+
+				coder->rep_distances[3] = coder->rep_distances[2];
+				coder->rep_distances[2] = coder->rep_distances[1];
+				coder->rep_distances[1] = coder->rep_distances[0];
+				coder->rep_distances[0] = pos;
+				++coder->match_price_count;
+			}
+
+			coder->previous_byte = coder->lz.buffer[
+					coder->lz.read_pos + len - 1
+					- coder->additional_offset];
+		}
+
+		assert(coder->additional_offset >= len);
+		coder->additional_offset -= len;
+		coder->now_pos += len;
+	}
+
+	// Check if everything is done.
+	bool all_done = false;
+	if (coder->lz.stream_end_was_reached
+			&& coder->lz.read_pos == coder->lz.write_pos
+			&& coder->additional_offset == 0) {
+		// Write end of stream marker. It is encoded as a match with
+		// distance of UINT32_MAX. Match length is needed but it is
+		// ignored by the decoder.
+		if (coder->lz.uncompressed_size == LZMA_VLI_VALUE_UNKNOWN) {
+			const uint32_t pos_state = coder->now_pos & pos_mask;
+			bit_encode_1(coder->is_match[coder->state][pos_state]);
+			bit_encode_0(coder->is_rep[coder->state]);
+			update_match(coder->state);
+
+			const uint32_t len = MATCH_MIN_LEN; // MATCH_MAX_LEN;
+			length_encode(coder->len_encoder, len - MATCH_MIN_LEN,
+					pos_state, best_compression);
+
+			const uint32_t pos_slot = (1 << POS_SLOT_BITS) - 1;
+			const uint32_t len_to_pos_state = get_len_to_pos_state(len);
+			bittree_encode(coder->pos_slot_encoder[len_to_pos_state],
+					POS_SLOT_BITS, pos_slot);
+
+			const uint32_t footer_bits = 30;
+			const uint32_t pos_reduced
+					= (UINT32_C(1) << footer_bits) - 1;
+			rc_encode_direct_bits(pos_reduced >> ALIGN_BITS,
+					footer_bits - ALIGN_BITS);
+
+			bittree_reverse_encode(coder->pos_align_encoder, ALIGN_BITS,
+					pos_reduced & ALIGN_MASK);
+		}
+
+		// Flush the last bytes of compressed data from
+		// the range coder to the output buffer.
+		rc_flush();
+
+		// All done. Note that some output bytes might be
+		// pending in coder->buffer. lzma_encode() will
+		// take care of those bytes.
+		if (rc_buffer_size == 0)
+			all_done = true;
+	}
+
+	// Store local variables back to *coder.
+	rc_from_local(coder->rc);
+	*out_pos = out_pos_local;
+
+	return all_done;
+}
diff --git a/src/liblzma/lzma/lzma_encoder.h b/src/liblzma/lzma/lzma_encoder.h
new file mode 100644
index 00000000..1c57f80a
--- /dev/null
+++ b/src/liblzma/lzma/lzma_encoder.h
@@ -0,0 +1,35 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       lzma_encoder.h
+/// \brief      LZMA method handler API
+//
+//  Copyright (C) 1999-2006 Igor Pavlov
+//  Copyright (C) 2007 Lasse Collin
+//
+//  This library is free software; you can redistribute it and/or
+//  modify it under the terms of the GNU Lesser General Public
+//  License as published by the Free Software Foundation; either
+//  version 2.1 of the License, or (at your option) any later version.
+//
+//  This library is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+//  Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#ifndef LZMA_LZMA_ENCODER_H
+#define LZMA_LZMA_ENCODER_H
+
+#include "common.h"
+
+extern lzma_ret lzma_lzma_encoder_init(lzma_next_coder *next,
+		lzma_allocator *allocator, const lzma_filter_info *filters);
+
+extern bool lzma_lzma_encode_properties(
+		const lzma_options_lzma *options, uint8_t *byte);
+
+/// Initializes the lzma_fastpos[] array.
+extern void lzma_fastpos_init(void);
+
+#endif
diff --git a/src/liblzma/lzma/lzma_encoder_features.c b/src/liblzma/lzma/lzma_encoder_features.c
new file mode 100644
index 00000000..56e59c6a
--- /dev/null
+++ b/src/liblzma/lzma/lzma_encoder_features.c
@@ -0,0 +1,59 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       lzma_encoder_features.c
+/// \brief      Information about features enabled at compile time
+//
+//  Copyright (C) 2007 Lasse Collin
+//
+//  This library is free software; you can redistribute it and/or
+//  modify it under the terms of the GNU Lesser General Public
+//  License as published by the Free Software Foundation; either
+//  version 2.1 of the License, or (at your option) any later version.
+//
+//  This library is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+//  Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include "common.h"
+
+
+static lzma_mode modes[] = {
+	LZMA_MODE_FAST,
+	LZMA_MODE_BEST,
+	LZMA_MODE_INVALID
+};
+
+
+LZMA_API const lzma_mode *const lzma_available_modes = modes;
+
+
+static lzma_match_finder match_finders[] = {
+#ifdef HAVE_MF_HC3
+	LZMA_MF_HC3,
+#endif
+
+#ifdef HAVE_MF_HC4
+	LZMA_MF_HC4,
+#endif
+
+#ifdef HAVE_MF_BT2
+	LZMA_MF_BT2,
+#endif
+
+#ifdef HAVE_MF_BT3
+	LZMA_MF_BT3,
+#endif
+
+#ifdef HAVE_MF_BT4
+	LZMA_MF_BT4,
+#endif
+
+	LZMA_MF_INVALID
+};
+
+
+LZMA_API const lzma_match_finder *const lzma_available_match_finders
+		= match_finders;
diff --git a/src/liblzma/lzma/lzma_encoder_getoptimum.c b/src/liblzma/lzma/lzma_encoder_getoptimum.c
new file mode 100644
index 00000000..cdeb3145
--- /dev/null
+++ b/src/liblzma/lzma/lzma_encoder_getoptimum.c
@@ -0,0 +1,893 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       lzma_encoder_getoptimum.c
+//
+//  Copyright (C) 1999-2006 Igor Pavlov
+//  Copyright (C) 2007 Lasse Collin
+//
+//  This library is free software; you can redistribute it and/or
+//  modify it under the terms of the GNU Lesser General Public
+//  License as published by the Free Software Foundation; either
+//  version 2.1 of the License, or (at your option) any later version.
+//
+//  This library is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+//  Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+// NOTE: If you want to keep the line length in 80 characters, set
+//       tab width to 4 or less in your editor when editing this file.
+
+
+// "Would you love the monster code?
+//  Could you understand beauty of the beast?"
+//      --Adapted from Lordi's "Would you love a monster man".
+
+
+#include "lzma_encoder_private.h"
+
+
+#define length_get_price(length_encoder, symbol, pos_state) \
+	(length_encoder).prices[pos_state][symbol]
+
+
+#define get_rep_len_1_price(state, pos_state) \
+	bit_get_price_0(coder->is_rep0[state]) \
+			+ bit_get_price_0(coder->is_rep0_long[state][pos_state])
+
+
+// Adds to price_target.
+#define get_pure_rep_price(price_target, rep_index, state, pos_state) \
+do { \
+	if ((rep_index) == 0) { \
+		price_target += bit_get_price_0(coder->is_rep0[state]); \
+		price_target += bit_get_price_1( \
+				coder->is_rep0_long[state][pos_state]); \
+	} else { \
+		price_target += bit_get_price_1(coder->is_rep0[state]); \
+		if ((rep_index) == 1) { \
+			price_target += bit_get_price_0(coder->is_rep1[state]); \
+		} else { \
+			price_target += bit_get_price_1(coder->is_rep1[state]); \
+			price_target += bit_get_price( \
+					coder->is_rep2[state], (rep_index) - 2); \
+		} \
+	} \
+} while (0)
+
+
+// Adds to price_target.
+#define get_rep_price(price_target, rep_index, len, state, pos_state) \
+do { \
+	get_pure_rep_price(price_target, rep_index, state, pos_state); \
+	price_target += length_get_price(coder->rep_match_len_encoder, \
+			(len) - MATCH_MIN_LEN, pos_state); \
+} while (0)
+
+
+// Adds to price_target.
+#define get_pos_len_price(price_target, pos, len, pos_state) \
+do { \
+	const uint32_t len_to_pos_state_tmp = get_len_to_pos_state(len); \
+	if ((pos) < FULL_DISTANCES) { \
+		price_target += distances_prices[len_to_pos_state_tmp][pos]; \
+	} else { \
+		price_target \
+				+= pos_slot_prices[len_to_pos_state_tmp][get_pos_slot_2(pos)] \
+				+ align_prices[(pos) & ALIGN_MASK]; \
+	} \
+	price_target += length_get_price( \
+			coder->len_encoder, (len) - MATCH_MIN_LEN, pos_state); \
+} while (0)
+
+
+// Three macros to manipulate lzma_optimal structures:
+#define make_as_char(opt) \
+do { \
+	(opt).back_prev = UINT32_MAX; \
+	(opt).prev_1_is_char = false; \
+} while (0)
+
+
+#define make_as_short_rep(opt) \
+do { \
+	(opt).back_prev = 0; \
+	(opt).prev_1_is_char = false; \
+} while (0)
+
+
+#define is_short_rep(opt) \
+	((opt).back_prev == 0)
+
+
+static void
+fill_distances_prices(lzma_coder *coder)
+{
+	uint32_t temp_prices[FULL_DISTANCES];
+
+	for (uint32_t i = START_POS_MODEL_INDEX; i < FULL_DISTANCES; ++i) {
+		const uint32_t pos_slot = get_pos_slot(i);
+		const uint32_t footer_bits = ((pos_slot >> 1) - 1);
+		const uint32_t base = (2 | (pos_slot & 1)) << footer_bits;
+		temp_prices[i] = 0;
+		bittree_reverse_get_price(temp_prices[i],
+				coder->pos_encoders + base - pos_slot - 1,
+				footer_bits, i - base);
+	}
+
+	const uint32_t dist_table_size = coder->dist_table_size;
+
+	for (uint32_t len_to_pos_state = 0;
+			len_to_pos_state < LEN_TO_POS_STATES;
+			++len_to_pos_state) {
+
+		const probability *encoder = coder->pos_slot_encoder[len_to_pos_state];
+		uint32_t *pos_slot_prices = coder->pos_slot_prices[len_to_pos_state];
+
+		for (uint32_t pos_slot = 0;
+				pos_slot < dist_table_size;
+				++pos_slot) {
+			pos_slot_prices[pos_slot] = 0;
+			bittree_get_price(pos_slot_prices[pos_slot], encoder,
+					POS_SLOT_BITS, pos_slot);
+		}
+
+		for (uint32_t pos_slot = END_POS_MODEL_INDEX;
+				pos_slot < dist_table_size;
+				++pos_slot)
+			pos_slot_prices[pos_slot] += (((pos_slot >> 1) - 1)
+					- ALIGN_BITS) << BIT_PRICE_SHIFT_BITS;
+
+
+		uint32_t *distances_prices
+				= coder->distances_prices[len_to_pos_state];
+
+		uint32_t i;
+		for (i = 0; i < START_POS_MODEL_INDEX; ++i)
+			distances_prices[i] = pos_slot_prices[i];
+
+		for (; i < FULL_DISTANCES; ++i)
+			distances_prices[i] = pos_slot_prices[get_pos_slot(i)]
+					+ temp_prices[i];
+	}
+
+	coder->match_price_count = 0;
+
+	return;
+}
+
+
+static void
+fill_align_prices(lzma_coder *coder)
+{
+	for (uint32_t i = 0; i < ALIGN_TABLE_SIZE; ++i) {
+		uint32_t tmp = 0;
+		bittree_reverse_get_price(tmp, coder->pos_align_encoder,
+				ALIGN_BITS, i);
+		coder->align_prices[i] = tmp;
+	}
+
+	coder->align_price_count = 0;
+}
+
+
+// The first argument is a pointer returned by literal_get_subcoder().
+static uint32_t
+literal_get_price(const probability *encoders, const bool match_mode,
+		const uint8_t match_byte, const uint8_t symbol)
+{
+	uint32_t price = 0;
+	uint32_t context = 1;
+	int i = 8;
+
+	if (match_mode) {
+		do {
+			--i;
+			const uint32_t match_bit = (match_byte >> i) & 1;
+			const uint32_t bit = (symbol >> i) & 1;
+			const uint32_t subcoder_index
+					= 0x100 + (match_bit << 8) + context;
+
+			price += bit_get_price(encoders[subcoder_index], bit);
+			context = (context << 1) | bit;
+
+			if (match_bit != bit)
+				break;
+
+		} while (i != 0);
+	}
+
+	while (i != 0) {
+		--i;
+		const uint32_t bit = (symbol >> i) & 1;
+		price += bit_get_price(encoders[context], bit);
+		context = (context << 1) | bit;
+	}
+
+	return price;
+}
+
+
+static void
+backward(lzma_coder *restrict coder, uint32_t *restrict len_res,
+		uint32_t *restrict back_res, uint32_t cur)
+{
+	coder->optimum_end_index = cur;
+
+	uint32_t pos_mem = coder->optimum[cur].pos_prev;
+	uint32_t back_mem = coder->optimum[cur].back_prev;
+
+	do {
+		if (coder->optimum[cur].prev_1_is_char) {
+			make_as_char(coder->optimum[pos_mem]);
+			coder->optimum[pos_mem].pos_prev = pos_mem - 1;
+
+			if (coder->optimum[cur].prev_2) {
+				coder->optimum[pos_mem - 1].prev_1_is_char = false;
+				coder->optimum[pos_mem - 1].pos_prev
+						= coder->optimum[cur].pos_prev_2;
+				coder->optimum[pos_mem - 1].back_prev
+						= coder->optimum[cur].back_prev_2;
+			}
+		}
+
+		uint32_t pos_prev = pos_mem;
+		uint32_t back_cur = back_mem;
+
+		back_mem = coder->optimum[pos_prev].back_prev;
+		pos_mem = coder->optimum[pos_prev].pos_prev;
+
+		coder->optimum[pos_prev].back_prev = back_cur;
+		coder->optimum[pos_prev].pos_prev = cur;
+		cur = pos_prev;
+
+	} while (cur != 0);
+
+	coder->optimum_current_index = coder->optimum[0].pos_prev;
+	*len_res = coder->optimum[0].pos_prev;
+	*back_res = coder->optimum[0].back_prev;
+
+	return;
+}
+
+
+extern void
+lzma_get_optimum(lzma_coder *restrict coder,
+		uint32_t *restrict back_res, uint32_t *restrict len_res)
+{
+	// Update the price tables. In the C++ LZMA SDK 4.42 this was done in both
+	// initialization function and in the main loop. In liblzma they were
+	// moved into this single place.
+	if (coder->additional_offset == 0) {
+		if (coder->match_price_count >= (1 << 7))
+			fill_distances_prices(coder);
+
+		if (coder->align_price_count >= ALIGN_TABLE_SIZE)
+			fill_align_prices(coder);
+	}
+
+
+	if (coder->optimum_end_index != coder->optimum_current_index) {
+		*len_res = coder->optimum[coder->optimum_current_index].pos_prev
+				- coder->optimum_current_index;
+		*back_res = coder->optimum[coder->optimum_current_index].back_prev;
+		coder->optimum_current_index = coder->optimum[
+				coder->optimum_current_index].pos_prev;
+		return;
+	}
+
+	coder->optimum_current_index = 0;
+	coder->optimum_end_index = 0;
+
+
+	const uint32_t fast_bytes = coder->fast_bytes;
+	uint32_t *match_distances = coder->match_distances;
+
+	uint32_t len_main;
+	uint32_t num_distance_pairs;
+
+	if (!coder->longest_match_was_found) {
+		lzma_read_match_distances(coder, &len_main, &num_distance_pairs);
+	} else {
+		len_main = coder->longest_match_length;
+		num_distance_pairs = coder->num_distance_pairs;
+		coder->longest_match_was_found = false;
+	}
+
+
+	const uint8_t *buf = coder->lz.buffer + coder->lz.read_pos - 1;
+	uint32_t num_available_bytes
+			= coder->lz.write_pos - coder->lz.read_pos + 1;
+	if (num_available_bytes < 2) {
+		*back_res = UINT32_MAX;
+		*len_res = 1;
+		return;
+	}
+
+	if (num_available_bytes > MATCH_MAX_LEN)
+		num_available_bytes = MATCH_MAX_LEN;
+
+
+	uint32_t reps[REP_DISTANCES];
+	uint32_t rep_lens[REP_DISTANCES];
+	uint32_t rep_max_index = 0;
+
+	for (uint32_t i = 0; i < REP_DISTANCES; ++i) {
+		reps[i] = coder->rep_distances[i];
+		const uint32_t back_offset = reps[i] + 1;
+
+		if (buf[0] != *(buf - back_offset)
+				|| buf[1] != *(buf + 1 - back_offset)) {
+			rep_lens[i] = 0;
+			continue;
+		}
+
+		uint32_t len_test;
+		for (len_test = 2; len_test < num_available_bytes
+				&& buf[len_test] == *(buf + len_test - back_offset);
+				++len_test) ;
+
+		rep_lens[i] = len_test;
+		if (len_test > rep_lens[rep_max_index])
+			rep_max_index = i;
+	}
+
+	if (rep_lens[rep_max_index] >= fast_bytes) {
+		*back_res = rep_max_index;
+		*len_res = rep_lens[rep_max_index];
+		move_pos(*len_res - 1);
+		return;
+	}
+
+
+	if (len_main >= fast_bytes) {
+		*back_res = match_distances[num_distance_pairs] + REP_DISTANCES;
+		*len_res = len_main;
+		move_pos(len_main - 1);
+		return;
+	}
+
+	uint8_t current_byte = *buf;
+	uint8_t match_byte = *(buf - reps[0] - 1);
+
+	if (len_main < 2 && current_byte != match_byte
+			&& rep_lens[rep_max_index] < 2) {
+		*back_res = UINT32_MAX;
+		*len_res = 1;
+		return;
+	}
+
+	const uint32_t pos_mask = coder->pos_mask;
+
+	coder->optimum[0].state = coder->state;
+
+	uint32_t position = coder->now_pos;
+	uint32_t pos_state = (position & pos_mask);
+
+	coder->optimum[1].price = bit_get_price_0(
+				coder->is_match[coder->state][pos_state])
+			+ literal_get_price(
+				literal_get_subcoder(coder->literal_coder,
+					position, coder->previous_byte),
+				!is_char_state(coder->state), match_byte, current_byte);
+
+	make_as_char(coder->optimum[1]);
+
+	uint32_t match_price
+			= bit_get_price_1(coder->is_match[coder->state][pos_state]);
+	uint32_t rep_match_price
+			= match_price + bit_get_price_1(coder->is_rep[coder->state]);
+
+
+	if (match_byte == current_byte) {
+		const uint32_t short_rep_price = rep_match_price
+				+ get_rep_len_1_price(coder->state, pos_state);
+
+		if (short_rep_price < coder->optimum[1].price) {
+			coder->optimum[1].price = short_rep_price;
+			make_as_short_rep(coder->optimum[1]);
+		}
+	}
+
+	uint32_t len_end = (len_main >= rep_lens[rep_max_index])
+			? len_main
+			: rep_lens[rep_max_index];
+
+	if (len_end < 2) {
+		*back_res = coder->optimum[1].back_prev;
+		*len_res = 1;
+		return;
+	}
+
+	coder->optimum[1].pos_prev = 0;
+
+	for (uint32_t i = 0; i < REP_DISTANCES; ++i)
+		coder->optimum[0].backs[i] = reps[i];
+
+	uint32_t len = len_end;
+	do {
+		coder->optimum[len].price = INFINITY_PRICE;
+	} while (--len >= 2);
+
+
+	uint32_t (*distances_prices)[FULL_DISTANCES] = coder->distances_prices;
+	uint32_t (*pos_slot_prices)[DIST_TABLE_SIZE_MAX] = coder->pos_slot_prices;
+	uint32_t *align_prices = coder->align_prices;
+
+	for (uint32_t i = 0; i < REP_DISTANCES; ++i) {
+		uint32_t rep_len = rep_lens[i];
+		if (rep_len < 2)
+			continue;
+
+		uint32_t price = rep_match_price;
+		get_pure_rep_price(price, i, coder->state, pos_state);
+
+		do {
+			const uint32_t cur_and_len_price = price
+					+ length_get_price(
+					coder->rep_match_len_encoder,
+					rep_len - 2, pos_state);
+
+			if (cur_and_len_price < coder->optimum[rep_len].price) {
+				coder->optimum[rep_len].price = cur_and_len_price;
+				coder->optimum[rep_len].pos_prev = 0;
+				coder->optimum[rep_len].back_prev = i;
+				coder->optimum[rep_len].prev_1_is_char = false;
+			}
+		} while (--rep_len >= 2);
+	}
+
+
+	uint32_t normal_match_price = match_price
+			+ bit_get_price_0(coder->is_rep[coder->state]);
+
+	len = (rep_lens[0] >= 2) ? rep_lens[0] + 1 : 2;
+
+	if (len <= len_main) {
+		uint32_t offs = 0;
+
+		while (len > match_distances[offs + 1])
+			offs += 2;
+
+		for(; ; ++len) {
+			const uint32_t distance = match_distances[offs + 2];
+			uint32_t cur_and_len_price = normal_match_price;
+			get_pos_len_price(cur_and_len_price, distance, len, pos_state);
+
+			if (cur_and_len_price < coder->optimum[len].price) {
+				coder->optimum[len].price = cur_and_len_price;
+				coder->optimum[len].pos_prev = 0;
+				coder->optimum[len].back_prev = distance + REP_DISTANCES;
+				coder->optimum[len].prev_1_is_char = false;
+			}
+
+			if (len == match_distances[offs + 1]) {
+				offs += 2;
+				if (offs == num_distance_pairs)
+					break;
+			}
+		}
+	}
+
+
+	//////////////////
+	// Big loop ;-) //
+	//////////////////
+
+	uint32_t cur = 0;
+
+	// The rest of this function is a huge while-loop. To avoid extreme
+	// indentation, the indentation level is not increased here.
+	while (true) {
+
+	++cur;
+
+	assert(cur < OPTS);
+
+	if (cur == len_end) {
+		backward(coder, len_res, back_res, cur);
+		return;
+	}
+
+	uint32_t new_len;
+
+	lzma_read_match_distances(coder, &new_len, &num_distance_pairs);
+
+	if (new_len >= fast_bytes) {
+		coder->num_distance_pairs = num_distance_pairs;
+		coder->longest_match_length = new_len;
+		coder->longest_match_was_found = true;
+		backward(coder, len_res, back_res, cur);
+		return;
+	}
+
+
+	++position;
+
+	uint32_t pos_prev = coder->optimum[cur].pos_prev;
+	uint32_t state;
+
+	if (coder->optimum[cur].prev_1_is_char) {
+		--pos_prev;
+
+		if (coder->optimum[cur].prev_2) {
+			state = coder->optimum[coder->optimum[cur].pos_prev_2].state;
+
+			if (coder->optimum[cur].back_prev_2 < REP_DISTANCES)
+				update_rep(state);
+			else
+				update_match(state);
+
+		} else {
+			state = coder->optimum[pos_prev].state;
+		}
+
+		update_char(state);
+
+	} else {
+		state = coder->optimum[pos_prev].state;
+	}
+
+	if (pos_prev == cur - 1) {
+		if (is_short_rep(coder->optimum[cur]))
+			update_short_rep(state);
+		else
+			update_char(state);
+	} else {
+		uint32_t pos;
+		if (coder->optimum[cur].prev_1_is_char && coder->optimum[cur].prev_2) {
+			pos_prev = coder->optimum[cur].pos_prev_2;
+			pos = coder->optimum[cur].back_prev_2;
+			update_rep(state);
+		} else {
+			pos = coder->optimum[cur].back_prev;
+			if (pos < REP_DISTANCES)
+				update_rep(state);
+			else
+				update_match(state);
+		}
+
+		if (pos < REP_DISTANCES) {
+			reps[0] = coder->optimum[pos_prev].backs[pos];
+
+			uint32_t i;
+			for (i = 1; i <= pos; ++i)
+				reps[i] = coder->optimum[pos_prev].backs[i - 1];
+
+			for (; i < REP_DISTANCES; ++i)
+				reps[i] = coder->optimum[pos_prev].backs[i];
+
+		} else {
+			reps[0] = pos - REP_DISTANCES;
+
+			for (uint32_t i = 1; i < REP_DISTANCES; ++i)
+				reps[i] = coder->optimum[pos_prev].backs[i - 1];
+		}
+	}
+
+	coder->optimum[cur].state = state;
+
+	for (uint32_t i = 0; i < REP_DISTANCES; ++i)
+		coder->optimum[cur].backs[i] = reps[i];
+
+	const uint32_t cur_price = coder->optimum[cur].price;
+
+	buf = coder->lz.buffer + coder->lz.read_pos - 1;
+	current_byte = *buf;
+	match_byte = *(buf - reps[0] - 1);
+
+	pos_state = position & pos_mask;
+
+	const uint32_t cur_and_1_price = cur_price
+			+ bit_get_price_0(coder->is_match[state][pos_state])
+			+ literal_get_price(
+				literal_get_subcoder(coder->literal_coder,
+					position, buf[-1]),
+        		!is_char_state(state), match_byte, current_byte);
+
+	bool next_is_char = false;
+
+	if (cur_and_1_price < coder->optimum[cur + 1].price) {
+		coder->optimum[cur + 1].price = cur_and_1_price;
+		coder->optimum[cur + 1].pos_prev = cur;
+		make_as_char(coder->optimum[cur + 1]);
+		next_is_char = true;
+	}
+
+	match_price = cur_price
+			+ bit_get_price_1(coder->is_match[state][pos_state]);
+	rep_match_price = match_price
+			+ bit_get_price_1(coder->is_rep[state]);
+
+	if (match_byte == current_byte
+			&& !(coder->optimum[cur + 1].pos_prev < cur
+			&& coder->optimum[cur + 1].back_prev == 0)) {
+
+		const uint32_t short_rep_price = rep_match_price
+				+ get_rep_len_1_price(state, pos_state);
+
+		if (short_rep_price <= coder->optimum[cur + 1].price) {
+			coder->optimum[cur + 1].price = short_rep_price;
+			coder->optimum[cur + 1].pos_prev = cur;
+			make_as_short_rep(coder->optimum[cur + 1]);
+			next_is_char = true;
+		}
+	}
+
+	uint32_t num_available_bytes_full
+			= coder->lz.write_pos - coder->lz.read_pos + 1;
+	num_available_bytes_full = MIN(OPTS - 1 - cur, num_available_bytes_full);
+	num_available_bytes = num_available_bytes_full;
+
+	if (num_available_bytes < 2)
+		continue;
+
+	if (num_available_bytes > fast_bytes)
+		num_available_bytes = fast_bytes;
+
+	if (!next_is_char && match_byte != current_byte) { // speed optimization
+		// try literal + rep0
+		const uint32_t back_offset = reps[0] + 1;
+		const uint32_t limit = MIN(num_available_bytes_full, fast_bytes + 1);
+
+		uint32_t temp;
+		for (temp = 1; temp < limit
+				&& buf[temp] == *(buf + temp - back_offset);
+				++temp) ;
+
+		const uint32_t len_test_2 = temp - 1;
+
+		if (len_test_2 >= 2) {
+			uint32_t state_2 = state;
+			update_char(state_2);
+
+			const uint32_t pos_state_next = (position + 1) & pos_mask;
+			const uint32_t next_rep_match_price = cur_and_1_price
+					+ bit_get_price_1(coder->is_match[state_2][pos_state_next])
+					+ bit_get_price_1(coder->is_rep[state_2]);
+
+			// for (; len_test_2 >= 2; --len_test_2) {
+			const uint32_t offset = cur + 1 + len_test_2;
+
+			while (len_end < offset)
+				coder->optimum[++len_end].price = INFINITY_PRICE;
+
+			uint32_t cur_and_len_price = next_rep_match_price;
+			get_rep_price(cur_and_len_price,
+					0, len_test_2, state_2, pos_state_next);
+
+			if (cur_and_len_price < coder->optimum[offset].price) {
+				coder->optimum[offset].price = cur_and_len_price;
+				coder->optimum[offset].pos_prev = cur + 1;
+				coder->optimum[offset].back_prev = 0;
+				coder->optimum[offset].prev_1_is_char = true;
+				coder->optimum[offset].prev_2 = false;
+			}
+// 			}
+		}
+	}
+
+
+	uint32_t start_len = 2; // speed optimization
+
+	for (uint32_t rep_index = 0; rep_index < REP_DISTANCES; ++rep_index) {
+		const uint32_t back_offset = reps[rep_index] + 1;
+
+		if (buf[0] != *(buf - back_offset) || buf[1] != *(buf + 1 - back_offset))
+			continue;
+
+		uint32_t len_test;
+		for (len_test = 2; len_test < num_available_bytes
+				&& buf[len_test] == *(buf + len_test - back_offset);
+				++len_test) ;
+
+		while (len_end < cur + len_test)
+			coder->optimum[++len_end].price = INFINITY_PRICE;
+
+		const uint32_t len_test_temp = len_test;
+		uint32_t price = rep_match_price;
+		get_pure_rep_price(price, rep_index, state, pos_state);
+
+		do {
+			const uint32_t cur_and_len_price = price
+					+ length_get_price(coder->rep_match_len_encoder,
+							len_test - 2, pos_state);
+
+			if (cur_and_len_price < coder->optimum[cur + len_test].price) {
+				coder->optimum[cur + len_test].price = cur_and_len_price;
+				coder->optimum[cur + len_test].pos_prev = cur;
+				coder->optimum[cur + len_test].back_prev = rep_index;
+				coder->optimum[cur + len_test].prev_1_is_char = false;
+			}
+		} while (--len_test >= 2);
+
+		len_test = len_test_temp;
+
+		if (rep_index == 0)
+			start_len = len_test + 1;
+
+
+		uint32_t len_test_2 = len_test + 1;
+		const uint32_t limit = MIN(num_available_bytes_full,
+				len_test_2 + fast_bytes);
+		for (; len_test_2 < limit
+				&& buf[len_test_2] == *(buf + len_test_2 - back_offset);
+				++len_test_2) ;
+
+		len_test_2 -= len_test + 1;
+
+		if (len_test_2 >= 2) {
+			uint32_t state_2 = state;
+			update_rep(state_2);
+
+			uint32_t pos_state_next = (position + len_test) & pos_mask;
+
+			const uint32_t cur_and_len_char_price = price
+					+ length_get_price(coder->rep_match_len_encoder,
+						len_test - 2, pos_state)
+					+ bit_get_price_0(coder->is_match[state_2][pos_state_next])
+					+ literal_get_price(
+						literal_get_subcoder(coder->literal_coder,
+							position + len_test, buf[len_test - 1]),
+						true, *(buf + len_test - back_offset), buf[len_test]);
+
+			update_char(state_2);
+
+			pos_state_next = (position + len_test + 1) & pos_mask;
+
+			const uint32_t next_rep_match_price = cur_and_len_char_price
+					+ bit_get_price_1(coder->is_match[state_2][pos_state_next])
+					+ bit_get_price_1(coder->is_rep[state_2]);
+
+// 			for(; len_test_2 >= 2; len_test_2--) {
+			const uint32_t offset = cur + len_test + 1 + len_test_2;
+
+			while (len_end < offset)
+				coder->optimum[++len_end].price = INFINITY_PRICE;
+
+			uint32_t cur_and_len_price = next_rep_match_price;
+			get_rep_price(cur_and_len_price,
+					0, len_test_2, state_2, pos_state_next);
+
+			if (cur_and_len_price < coder->optimum[offset].price) {
+				coder->optimum[offset].price = cur_and_len_price;
+				coder->optimum[offset].pos_prev = cur + len_test + 1;
+				coder->optimum[offset].back_prev = 0;
+				coder->optimum[offset].prev_1_is_char = true;
+				coder->optimum[offset].prev_2 = true;
+				coder->optimum[offset].pos_prev_2 = cur;
+				coder->optimum[offset].back_prev_2 = rep_index;
+			}
+// 			}
+		}
+	}
+
+
+// 	for (uint32_t len_test = 2; len_test <= new_len; ++len_test)
+	if (new_len > num_available_bytes) {
+		new_len = num_available_bytes;
+
+		for (num_distance_pairs = 0;
+				new_len > match_distances[num_distance_pairs + 1];
+				num_distance_pairs += 2) ;
+
+		match_distances[num_distance_pairs + 1] = new_len;
+		num_distance_pairs += 2;
+	}
+
+
+	if (new_len >= start_len) {
+		normal_match_price = match_price
+				+ bit_get_price_0(coder->is_rep[state]);
+
+		while (len_end < cur + new_len)
+			coder->optimum[++len_end].price = INFINITY_PRICE;
+
+		uint32_t offs = 0;
+		while (start_len > match_distances[offs + 1])
+			offs += 2;
+
+		uint32_t cur_back = match_distances[offs + 2];
+		uint32_t pos_slot = get_pos_slot_2(cur_back);
+
+		for (uint32_t len_test = start_len; ; ++len_test) {
+			uint32_t cur_and_len_price = normal_match_price;
+			const uint32_t len_to_pos_state = get_len_to_pos_state(len_test);
+
+			if (cur_back < FULL_DISTANCES)
+				cur_and_len_price += distances_prices[
+						len_to_pos_state][cur_back];
+			else
+				cur_and_len_price += pos_slot_prices[
+						len_to_pos_state][pos_slot]
+						+ align_prices[cur_back & ALIGN_MASK];
+
+			cur_and_len_price += length_get_price(coder->len_encoder,
+					len_test - MATCH_MIN_LEN, pos_state);
+
+			if (cur_and_len_price < coder->optimum[cur + len_test].price) {
+				coder->optimum[cur + len_test].price = cur_and_len_price;
+				coder->optimum[cur + len_test].pos_prev = cur;
+				coder->optimum[cur + len_test].back_prev
+						= cur_back + REP_DISTANCES;
+				coder->optimum[cur + len_test].prev_1_is_char = false;
+			}
+
+			if (len_test == match_distances[offs + 1]) {
+				// Try Match + Literal + Rep0
+				const uint32_t back_offset = cur_back + 1;
+				uint32_t len_test_2 = len_test + 1;
+				const uint32_t limit = MIN(num_available_bytes_full,
+						len_test_2 + fast_bytes);
+
+				for (; len_test_2 < limit &&
+						buf[len_test_2] == *(buf + len_test_2 - back_offset);
+						++len_test_2) ;
+
+				len_test_2 -= len_test + 1;
+
+				if (len_test_2 >= 2) {
+					uint32_t state_2 = state;
+					update_match(state_2);
+					uint32_t pos_state_next
+							= (position + len_test) & pos_mask;
+
+					const uint32_t cur_and_len_char_price = cur_and_len_price
+							+ bit_get_price_0(
+								coder->is_match[state_2][pos_state_next])
+							+ literal_get_price(
+								literal_get_subcoder(
+									coder->literal_coder,
+									position + len_test,
+									buf[len_test - 1]),
+								true,
+								*(buf + len_test - back_offset),
+								buf[len_test]);
+
+					update_char(state_2);
+					pos_state_next = (pos_state_next + 1) & pos_mask;
+
+					const uint32_t next_rep_match_price
+							= cur_and_len_char_price
+							+ bit_get_price_1(
+								coder->is_match[state_2][pos_state_next])
+							+ bit_get_price_1(coder->is_rep[state_2]);
+
+					// for(; len_test_2 >= 2; --len_test_2) {
+					const uint32_t offset = cur + len_test + 1 + len_test_2;
+
+					while (len_end < offset)
+						coder->optimum[++len_end].price = INFINITY_PRICE;
+
+					cur_and_len_price = next_rep_match_price;
+					get_rep_price(cur_and_len_price,
+							0, len_test_2, state_2, pos_state_next);
+
+					if (cur_and_len_price < coder->optimum[offset].price) {
+						coder->optimum[offset].price = cur_and_len_price;
+						coder->optimum[offset].pos_prev = cur + len_test + 1;
+						coder->optimum[offset].back_prev = 0;
+						coder->optimum[offset].prev_1_is_char = true;
+						coder->optimum[offset].prev_2 = true;
+						coder->optimum[offset].pos_prev_2 = cur;
+						coder->optimum[offset].back_prev_2
+								= cur_back + REP_DISTANCES;
+					}
+// 					}
+				}
+
+				offs += 2;
+				if (offs == num_distance_pairs)
+					break;
+
+				cur_back = match_distances[offs + 2];
+				if (cur_back >= FULL_DISTANCES)
+					pos_slot = get_pos_slot_2(cur_back);
+			}
+		}
+	}
+
+	} // Closes: while (true)
+}
diff --git a/src/liblzma/lzma/lzma_encoder_getoptimumfast.c b/src/liblzma/lzma/lzma_encoder_getoptimumfast.c
new file mode 100644
index 00000000..e6cee19d
--- /dev/null
+++ b/src/liblzma/lzma/lzma_encoder_getoptimumfast.c
@@ -0,0 +1,201 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       lzma_encoder_getoptimumfast.c
+//
+//  Copyright (C) 1999-2006 Igor Pavlov
+//  Copyright (C) 2007 Lasse Collin
+//
+//  This library is free software; you can redistribute it and/or
+//  modify it under the terms of the GNU Lesser General Public
+//  License as published by the Free Software Foundation; either
+//  version 2.1 of the License, or (at your option) any later version.
+//
+//  This library is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+//  Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+// NOTE: If you want to keep the line length in 80 characters, set
+//       tab width to 4 or less in your editor when editing this file.
+
+
+#include "lzma_encoder_private.h"
+
+
+#define change_pair(small_dist, big_dist) \
+	(((big_dist) >> 7) > (small_dist))
+
+
+extern void
+lzma_get_optimum_fast(lzma_coder *restrict coder,
+		uint32_t *restrict back_res, uint32_t *restrict len_res)
+{
+	// Local copies
+	const uint32_t fast_bytes = coder->fast_bytes;
+
+	uint32_t len_main;
+	uint32_t num_distance_pairs;
+	if (!coder->longest_match_was_found) {
+		lzma_read_match_distances(coder, &len_main, &num_distance_pairs);
+	} else {
+		len_main = coder->longest_match_length;
+		num_distance_pairs = coder->num_distance_pairs;
+		coder->longest_match_was_found = false;
+	}
+
+	const uint8_t *buf = coder->lz.buffer + coder->lz.read_pos - 1;
+	uint32_t num_available_bytes
+			= coder->lz.write_pos - coder->lz.read_pos + 1;
+
+	if (num_available_bytes < 2) {
+		// There's not enough input left to encode a match.
+		*back_res = UINT32_MAX;
+		*len_res = 1;
+		return;
+	}
+
+	if (num_available_bytes > MATCH_MAX_LEN)
+		num_available_bytes = MATCH_MAX_LEN;
+
+
+	// Look for repetitive matches; scan the previous four match distances
+	uint32_t rep_lens[REP_DISTANCES];
+	uint32_t rep_max_index = 0;
+
+	for (uint32_t i = 0; i < REP_DISTANCES; ++i) {
+		const uint32_t back_offset = coder->rep_distances[i] + 1;
+
+		// If the first two bytes (2 == MATCH_MIN_LEN) do not match,
+		// this rep_distance[i] is not useful. This is indicated
+		// using zero as the length of the repetitive match.
+		if (buf[0] != *(buf - back_offset)
+				|| buf[1] != *(buf + 1 - back_offset)) {
+			rep_lens[i] = 0;
+			continue;
+		}
+
+		// The first two bytes matched.
+		// Calculate the length of the match.
+		uint32_t len;
+		for (len = 2; len < num_available_bytes
+				&& buf[len] == *(buf + len - back_offset);
+				++len) ;
+
+		// If we have found a repetitive match that is at least
+		// as long as fast_bytes, return it immediatelly.
+		if (len >= fast_bytes) {
+			*back_res = i;
+			*len_res = len;
+			move_pos(len - 1);
+			return;
+		}
+
+		rep_lens[i] = len;
+
+		// After this loop, rep_lens[rep_max_index] is the biggest
+		// value of all values in rep_lens[].
+		if (len > rep_lens[rep_max_index])
+			rep_max_index = i;
+	}
+
+
+	if (len_main >= fast_bytes) {
+		*back_res = coder->match_distances[num_distance_pairs]
+				+ REP_DISTANCES;
+		*len_res = len_main;
+		move_pos(len_main - 1);
+		return;
+	}
+
+	uint32_t back_main = 0;
+	if (len_main >= 2) {
+		back_main = coder->match_distances[num_distance_pairs];
+
+		while (num_distance_pairs > 2 && len_main ==
+				coder->match_distances[num_distance_pairs - 3] + 1) {
+			if (!change_pair(coder->match_distances[
+					num_distance_pairs - 2], back_main))
+				break;
+
+			num_distance_pairs -= 2;
+			len_main = coder->match_distances[num_distance_pairs - 1];
+			back_main = coder->match_distances[num_distance_pairs];
+		}
+
+		if (len_main == 2 && back_main >= 0x80)
+			len_main = 1;
+	}
+
+	if (rep_lens[rep_max_index] >= 2) {
+		if (rep_lens[rep_max_index] + 1 >= len_main
+				|| (rep_lens[rep_max_index] + 2 >= len_main
+					&& (back_main > (1 << 9)))
+				|| (rep_lens[rep_max_index] + 3 >= len_main
+					&& (back_main > (1 << 15)))) {
+			*back_res = rep_max_index;
+			*len_res = rep_lens[rep_max_index];
+			move_pos(*len_res - 1);
+			return;
+		}
+	}
+
+	if (len_main >= 2 && num_available_bytes > 2) {
+		lzma_read_match_distances(coder, &coder->longest_match_length,
+				&coder->num_distance_pairs);
+
+		if (coder->longest_match_length >= 2) {
+			const uint32_t new_distance = coder->match_distances[
+					coder->num_distance_pairs];
+
+			if ((coder->longest_match_length >= len_main
+						&& new_distance < back_main)
+					|| (coder->longest_match_length == len_main + 1
+						&& !change_pair(back_main, new_distance))
+					|| (coder->longest_match_length > len_main + 1)
+					|| (coder->longest_match_length + 1 >= len_main
+						&& len_main >= 3
+						&& change_pair(new_distance, back_main))) {
+				coder->longest_match_was_found = true;
+				*back_res = UINT32_MAX;
+				*len_res = 1;
+				return;
+			}
+		}
+
+		++buf;
+		--num_available_bytes;
+
+		for (uint32_t i = 0; i < REP_DISTANCES; ++i) {
+			const uint32_t back_offset = coder->rep_distances[i] + 1;
+
+			if (buf[1] != *(buf + 1 - back_offset)
+					|| buf[2] != *(buf + 2 - back_offset)) {
+				rep_lens[i] = 0;
+				continue;
+			}
+
+			uint32_t len;
+			for (len = 2; len < num_available_bytes
+					&& buf[len] == *(buf + len - back_offset);
+					++len) ;
+
+			if (len + 1 >= len_main) {
+				coder->longest_match_was_found = true;
+				*back_res = UINT32_MAX;
+				*len_res = 1;
+				return;
+			}
+		}
+
+		*back_res = back_main + REP_DISTANCES;
+		*len_res = len_main;
+		move_pos(len_main - 2);
+		return;
+	}
+
+	*back_res = UINT32_MAX;
+	*len_res = 1;
+	return;
+}
diff --git a/src/liblzma/lzma/lzma_encoder_init.c b/src/liblzma/lzma/lzma_encoder_init.c
new file mode 100644
index 00000000..d7807529
--- /dev/null
+++ b/src/liblzma/lzma/lzma_encoder_init.c
@@ -0,0 +1,245 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       lzma_encoder_init.c
+/// \brief      Creating, resetting and destroying the LZMA encoder
+//
+//  Copyright (C) 1999-2006 Igor Pavlov
+//  Copyright (C) 2007 Lasse Collin
+//
+//  This library is free software; you can redistribute it and/or
+//  modify it under the terms of the GNU Lesser General Public
+//  License as published by the Free Software Foundation; either
+//  version 2.1 of the License, or (at your option) any later version.
+//
+//  This library is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+//  Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include "lzma_encoder_private.h"
+
+
+uint8_t lzma_fastpos[1 << 11];
+
+extern void
+lzma_fastpos_init(void)
+{
+	static const uint8_t fast_slots = 22;
+
+	int c = 2;
+	lzma_fastpos[0] = 0;
+	lzma_fastpos[1] = 1;
+
+	for (uint8_t slot_fast = 2; slot_fast < fast_slots; ++slot_fast) {
+		const uint32_t k = (1 << ((slot_fast >> 1) - 1));
+
+		for (uint32_t j = 0; j < k; ++j, ++c)
+			lzma_fastpos[c] = slot_fast;
+	}
+
+	return;
+}
+
+
+/// \brief      Initializes the length encoder
+static void
+length_encoder_reset(lzma_length_encoder *lencoder,
+		const uint32_t num_pos_states, const uint32_t table_size)
+{
+	// NLength::CPriceTableEncoder::SetTableSize()
+	lencoder->table_size = table_size;
+
+	// NLength::CEncoder::Init()
+	bit_reset(lencoder->choice);
+	bit_reset(lencoder->choice2);
+
+	for (size_t pos_state = 0; pos_state < num_pos_states; ++pos_state) {
+		bittree_reset(lencoder->low[pos_state], LEN_LOW_BITS);
+		bittree_reset(lencoder->mid[pos_state], LEN_MID_BITS);
+	}
+
+	bittree_reset(lencoder->high, LEN_HIGH_BITS);
+
+	// NLength::CPriceTableEncoder::UpdateTables()
+	for (size_t pos_state = 0; pos_state < num_pos_states; ++pos_state)
+		lzma_length_encoder_update_table(lencoder, pos_state);
+
+	return;
+}
+
+
+static void
+lzma_lzma_encoder_end(lzma_coder *coder, lzma_allocator *allocator)
+{
+	lzma_lz_encoder_end(&coder->lz, allocator);
+	lzma_literal_end(&coder->literal_coder, allocator);
+	lzma_free(coder, allocator);
+	return;
+}
+
+
+extern lzma_ret
+lzma_lzma_encoder_init(lzma_next_coder *next, lzma_allocator *allocator,
+		const lzma_filter_info *filters)
+{
+	if (next->coder == NULL) {
+		next->coder = lzma_alloc(sizeof(lzma_coder), allocator);
+		if (next->coder == NULL)
+			return LZMA_MEM_ERROR;
+
+		next->coder->next = LZMA_NEXT_CODER_INIT;
+		next->coder->lz = LZMA_LZ_ENCODER_INIT;
+		next->coder->literal_coder = NULL;
+	}
+
+	// Validate options that aren't validated elsewhere.
+	const lzma_options_lzma *options = filters[0].options;
+	if (options->pos_bits > LZMA_POS_BITS_MAX
+			|| options->fast_bytes < LZMA_FAST_BYTES_MIN
+			|| options->fast_bytes > LZMA_FAST_BYTES_MAX) {
+		lzma_lzma_encoder_end(next->coder, allocator);
+		return LZMA_HEADER_ERROR;
+	}
+
+	// Set compression mode.
+	switch (options->mode) {
+		case LZMA_MODE_FAST:
+			next->coder->best_compression = false;
+			break;
+
+		case LZMA_MODE_BEST:
+			next->coder->best_compression = true;
+			break;
+
+		default:
+			lzma_lzma_encoder_end(next->coder, allocator);
+			return LZMA_HEADER_ERROR;
+	}
+
+	// Initialize literal coder.
+	{
+		const lzma_ret ret = lzma_literal_init(
+				&next->coder->literal_coder, allocator,
+				options->literal_context_bits,
+				options->literal_pos_bits);
+		if (ret != LZMA_OK) {
+			lzma_lzma_encoder_end(next->coder, allocator);
+			return ret;
+		}
+	}
+
+	// Initialize LZ encoder.
+	{
+		const lzma_ret ret = lzma_lz_encoder_reset(
+				&next->coder->lz, allocator, &lzma_lzma_encode,
+				filters[0].uncompressed_size,
+				options->dictionary_size, OPTS,
+				options->fast_bytes, MATCH_MAX_LEN + 1 + OPTS,
+				options->match_finder,
+				options->match_finder_cycles,
+				options->preset_dictionary,
+				options->preset_dictionary_size);
+		if (ret != LZMA_OK) {
+			lzma_lzma_encoder_end(next->coder, allocator);
+			return ret;
+		}
+	}
+
+	// Set dist_table_size.
+	{
+		// Round the dictionary size up to next 2^n.
+		uint32_t log_size;
+		for (log_size = 0; (UINT32_C(1) << log_size)
+				< options->dictionary_size; ++log_size) ;
+
+		next->coder->dist_table_size = log_size * 2;
+	}
+
+	// Misc FIXME desc
+	next->coder->dictionary_size = options->dictionary_size;
+	next->coder->pos_mask = (1U << options->pos_bits) - 1;
+	next->coder->fast_bytes = options->fast_bytes;
+
+	// Range coder
+	rc_reset(next->coder->rc);
+
+	// State
+	next->coder->state = 0;
+	next->coder->previous_byte = 0;
+	for (size_t i = 0; i < REP_DISTANCES; ++i)
+		next->coder->rep_distances[i] = 0;
+
+	// Bit encoders
+	for (size_t i = 0; i < STATES; ++i) {
+		for (size_t j = 0; j <= next->coder->pos_mask; ++j) {
+			bit_reset(next->coder->is_match[i][j]);
+			bit_reset(next->coder->is_rep0_long[i][j]);
+		}
+
+		bit_reset(next->coder->is_rep[i]);
+		bit_reset(next->coder->is_rep0[i]);
+		bit_reset(next->coder->is_rep1[i]);
+		bit_reset(next->coder->is_rep2[i]);
+	}
+
+	for (size_t i = 0; i < FULL_DISTANCES - END_POS_MODEL_INDEX; ++i)
+		bit_reset(next->coder->pos_encoders[i]);
+
+	// Bit tree encoders
+	for (size_t i = 0; i < LEN_TO_POS_STATES; ++i)
+		bittree_reset(next->coder->pos_slot_encoder[i], POS_SLOT_BITS);
+
+	bittree_reset(next->coder->pos_align_encoder, ALIGN_BITS);
+
+	// Length encoders
+	length_encoder_reset(&next->coder->len_encoder, 1U << options->pos_bits,
+			options->fast_bytes + 1 - MATCH_MIN_LEN);
+
+	length_encoder_reset(&next->coder->rep_match_len_encoder,
+			1U << options->pos_bits,
+			next->coder->fast_bytes + 1 - MATCH_MIN_LEN);
+
+	// Misc
+	next->coder->longest_match_was_found = false;
+	next->coder->optimum_end_index = 0;
+	next->coder->optimum_current_index = 0;
+	next->coder->additional_offset = 0;
+
+	next->coder->now_pos = 0;
+	next->coder->is_initialized = false;
+
+	// Initialize the next decoder in the chain, if any.
+	{
+		const lzma_ret ret = lzma_next_filter_init(&next->coder->next,
+				allocator, filters + 1);
+		if (ret != LZMA_OK) {
+			lzma_lzma_encoder_end(next->coder, allocator);
+			return ret;
+		}
+	}
+
+	// Initialization successful. Set the function pointers.
+	next->code = &lzma_lz_encode;
+	next->end = &lzma_lzma_encoder_end;
+
+	return LZMA_OK;
+}
+
+
+extern bool
+lzma_lzma_encode_properties(const lzma_options_lzma *options, uint8_t *byte)
+{
+	if (options->literal_context_bits > LZMA_LITERAL_CONTEXT_BITS_MAX
+			|| options->literal_pos_bits
+				> LZMA_LITERAL_POS_BITS_MAX
+			|| options->pos_bits > LZMA_POS_BITS_MAX)
+		return true;
+
+	*byte = (options->pos_bits * 5 + options->literal_pos_bits) * 9
+			+ options->literal_context_bits;
+	assert(*byte <= (4 * 5 + 4) * 9 + 8);
+
+	return false;
+}
diff --git a/src/liblzma/lzma/lzma_encoder_presets.c b/src/liblzma/lzma/lzma_encoder_presets.c
new file mode 100644
index 00000000..966c7c86
--- /dev/null
+++ b/src/liblzma/lzma/lzma_encoder_presets.c
@@ -0,0 +1,34 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       lzma_encoder_presets.c
+/// \brief      Encoder presets
+//
+//  Copyright (C) 2007 Lasse Collin
+//
+//  This library is free software; you can redistribute it and/or
+//  modify it under the terms of the GNU Lesser General Public
+//  License as published by the Free Software Foundation; either
+//  version 2.1 of the License, or (at your option) any later version.
+//
+//  This library is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+//  Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include "common.h"
+
+
+LZMA_API const lzma_options_lzma lzma_preset_lzma[9] = {
+// dictionary_size  lc lp pb           mode            fb  mf          mfc
+{ UINT32_C(1) << 16, 3, 0, 2, NULL, 0, LZMA_MODE_FAST,  64, LZMA_MF_HC3, 0 },
+{ UINT32_C(1) << 20, 3, 0, 2, NULL, 0, LZMA_MODE_FAST,  64, LZMA_MF_HC4, 0 },
+{ UINT32_C(1) << 19, 3, 0, 2, NULL, 0, LZMA_MODE_BEST,  64, LZMA_MF_BT4, 0 },
+{ UINT32_C(1) << 20, 3, 0, 2, NULL, 0, LZMA_MODE_BEST,  64, LZMA_MF_BT4, 0 },
+{ UINT32_C(1) << 21, 3, 0, 2, NULL, 0, LZMA_MODE_BEST, 128, LZMA_MF_BT4, 0 },
+{ UINT32_C(1) << 22, 3, 0, 2, NULL, 0, LZMA_MODE_BEST, 128, LZMA_MF_BT4, 0 },
+{ UINT32_C(1) << 23, 3, 0, 2, NULL, 0, LZMA_MODE_BEST, 128, LZMA_MF_BT4, 0 },
+{ UINT32_C(1) << 24, 3, 0, 2, NULL, 0, LZMA_MODE_BEST, 273, LZMA_MF_BT4, 0 },
+{ UINT32_C(1) << 25, 3, 0, 2, NULL, 0, LZMA_MODE_BEST, 273, LZMA_MF_BT4, 0 },
+};
diff --git a/src/liblzma/lzma/lzma_encoder_private.h b/src/liblzma/lzma/lzma_encoder_private.h
new file mode 100644
index 00000000..7fb1566a
--- /dev/null
+++ b/src/liblzma/lzma/lzma_encoder_private.h
@@ -0,0 +1,225 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       lzma_encoder_private.h
+/// \brief      Private definitions for LZMA encoder
+//
+//  Copyright (C) 1999-2006 Igor Pavlov
+//  Copyright (C) 2007 Lasse Collin
+//
+//  This library is free software; you can redistribute it and/or
+//  modify it under the terms of the GNU Lesser General Public
+//  License as published by the Free Software Foundation; either
+//  version 2.1 of the License, or (at your option) any later version.
+//
+//  This library is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+//  Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#ifndef LZMA_LZMA_ENCODER_PRIVATE_H
+#define LZMA_LZMA_ENCODER_PRIVATE_H
+
+#include "lzma_encoder.h"
+#include "lzma_common.h"
+#include "lz_encoder.h"
+
+// We need space for about two encoding loops, because there is no check
+// for available buffer space before end of payload marker gets written.
+// 2*26 bytes should be enough for this... but Lasse isn't very sure about
+// the exact value. 64 bytes certainly is enough. :-)
+#define RC_BUFFER_SIZE 64
+#include "range_encoder.h"
+
+
+#define move_pos(num) \
+do { \
+	assert((int32_t)(num) >= 0); \
+	if ((num) != 0) { \
+		coder->additional_offset += num; \
+		coder->lz.skip(&coder->lz, num); \
+	} \
+} while (0)
+
+
+#define get_pos_slot(pos) \
+	((pos) < (1 << 11) \
+		? lzma_fastpos[pos] \
+		: ((pos) < (1 << 21) \
+			? lzma_fastpos[(pos) >> 10] + 20 \
+			: lzma_fastpos[(pos) >> 20] + 40))
+
+
+#define get_pos_slot_2(pos) \
+	((pos) < (1 << 17) \
+		? lzma_fastpos[(pos) >> 6] + 12 \
+		: ((pos) < (1 << 27) \
+			? lzma_fastpos[(pos) >> 16] + 32 \
+			: lzma_fastpos[(pos) >> 26] + 52))
+
+
+/// This isn't modified once its contents have been
+/// initialized by lzma_fastpos_init().
+extern uint8_t lzma_fastpos[1 << 11];
+
+
+typedef struct {
+	probability choice;
+	probability choice2;
+	probability low[POS_STATES_MAX][LEN_LOW_SYMBOLS];
+	probability mid[POS_STATES_MAX][LEN_MID_SYMBOLS];
+	probability high[LEN_HIGH_SYMBOLS];
+
+	uint32_t prices[POS_STATES_MAX][LEN_SYMBOLS];
+	uint32_t table_size;
+	uint32_t counters[POS_STATES_MAX];
+
+} lzma_length_encoder;
+
+
+typedef struct {
+	uint32_t state;
+
+	bool prev_1_is_char;
+	bool prev_2;
+
+	uint32_t pos_prev_2;
+	uint32_t back_prev_2;
+
+	uint32_t price;
+	uint32_t pos_prev;  // pos_next;
+	uint32_t back_prev;
+
+	uint32_t backs[4];
+
+} lzma_optimal;
+
+
+struct lzma_coder_s {
+	// Next coder in the chain
+	lzma_next_coder next;
+
+	// In window and match finder
+	lzma_lz_encoder lz;
+
+	// Range encoder
+	lzma_range_encoder rc;
+
+	// State
+	uint32_t state;
+	uint8_t previous_byte;
+	uint32_t rep_distances[REP_DISTANCES];
+
+	// Misc
+	uint32_t match_distances[MATCH_MAX_LEN * 2 + 2 + 1];
+	uint32_t num_distance_pairs;
+	uint32_t additional_offset;
+	uint32_t now_pos; // Lowest 32 bits are enough here.
+	bool best_compression;           ///< True when LZMA_MODE_BEST is used
+	bool is_initialized;
+
+	// Literal encoder
+	lzma_literal_coder *literal_coder;
+
+	// Bit encoders
+	probability is_match[STATES][POS_STATES_MAX];
+	probability is_rep[STATES];
+	probability is_rep0[STATES];
+	probability is_rep1[STATES];
+	probability is_rep2[STATES];
+	probability is_rep0_long[STATES][POS_STATES_MAX];
+	probability pos_encoders[FULL_DISTANCES - END_POS_MODEL_INDEX];
+
+	// Bit Tree Encoders
+	probability pos_slot_encoder[LEN_TO_POS_STATES][1 << POS_SLOT_BITS];
+	probability pos_align_encoder[1 << ALIGN_BITS];
+
+	// Length encoders
+	lzma_length_encoder len_encoder;
+	lzma_length_encoder rep_match_len_encoder;
+
+	// Optimal
+	lzma_optimal optimum[OPTS];
+	uint32_t optimum_end_index;
+	uint32_t optimum_current_index;
+	uint32_t longest_match_length;
+	bool longest_match_was_found;
+
+	// Prices
+	uint32_t pos_slot_prices[LEN_TO_POS_STATES][DIST_TABLE_SIZE_MAX];
+	uint32_t distances_prices[LEN_TO_POS_STATES][FULL_DISTANCES];
+	uint32_t align_prices[ALIGN_TABLE_SIZE];
+	uint32_t align_price_count;
+	uint32_t dist_table_size;
+	uint32_t match_price_count;
+
+	// LZMA specific settings
+	uint32_t dictionary_size;        ///< Size in bytes
+	uint32_t fast_bytes;
+	uint32_t pos_state_bits;
+	uint32_t pos_mask;         ///< (1 << pos_state_bits) - 1
+};
+
+
+extern void lzma_length_encoder_update_table(lzma_length_encoder *lencoder,
+		const uint32_t pos_state);
+
+extern bool lzma_lzma_encode(lzma_coder *coder, uint8_t *restrict out,
+		size_t *restrict out_pos, size_t out_size);
+
+extern void lzma_get_optimum(lzma_coder *restrict coder,
+		uint32_t *restrict back_res, uint32_t *restrict len_res);
+
+extern void lzma_get_optimum_fast(lzma_coder *restrict coder,
+		uint32_t *restrict back_res, uint32_t *restrict len_res);
+
+
+// NOTE: Don't add 'restrict'.
+static inline void
+lzma_read_match_distances(lzma_coder *coder,
+		uint32_t *len_res, uint32_t *num_distance_pairs)
+{
+	*len_res = 0;
+
+	coder->lz.get_matches(&coder->lz, coder->match_distances);
+
+	*num_distance_pairs = coder->match_distances[0];
+
+	if (*num_distance_pairs > 0) {
+		*len_res = coder->match_distances[*num_distance_pairs - 1];
+		assert(*len_res <= MATCH_MAX_LEN);
+
+		if (*len_res == coder->fast_bytes) {
+			uint32_t offset = *len_res - 1;
+			const uint32_t distance = coder->match_distances[
+					*num_distance_pairs] + 1;
+			uint32_t limit = MATCH_MAX_LEN - *len_res;
+
+			assert(offset + limit < coder->lz.keep_size_after);
+
+			// If we are close to end of the stream, we may need
+			// to limit the length of the match.
+			if (coder->lz.stream_end_was_reached
+					&& coder->lz.write_pos
+					< coder->lz.read_pos + offset + limit)
+				limit = coder->lz.write_pos
+					- (coder->lz.read_pos + offset);
+
+			offset += coder->lz.read_pos;
+			uint32_t i = 0;
+			while (i < limit && coder->lz.buffer[offset + i]
+					== coder->lz.buffer[
+						offset + i - distance])
+				++i;
+
+			*len_res += i;
+		}
+	}
+
+	++coder->additional_offset;
+
+	return;
+}
+
+#endif
diff --git a/src/liblzma/lzma/lzma_literal.c b/src/liblzma/lzma/lzma_literal.c
new file mode 100644
index 00000000..8f650fbf
--- /dev/null
+++ b/src/liblzma/lzma/lzma_literal.c
@@ -0,0 +1,74 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       lzma_literal.c
+/// \brief      Literal Coder
+//
+//  Copyright (C) 1999-2006 Igor Pavlov
+//  Copyright (C) 2007 Lasse Collin
+//
+//  This library is free software; you can redistribute it and/or
+//  modify it under the terms of the GNU Lesser General Public
+//  License as published by the Free Software Foundation; either
+//  version 2.1 of the License, or (at your option) any later version.
+//
+//  This library is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+//  Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include "lzma_literal.h"
+
+
+extern lzma_ret
+lzma_literal_init(lzma_literal_coder **coder, lzma_allocator *allocator,
+		uint32_t literal_context_bits, uint32_t literal_pos_bits)
+{
+	// Verify that arguments are sane.
+	if (literal_context_bits > LZMA_LITERAL_CONTEXT_BITS_MAX
+			|| literal_pos_bits > LZMA_LITERAL_POS_BITS_MAX)
+		return LZMA_HEADER_ERROR;
+
+	// Calculate the number of states the literal coder must store.
+	const uint32_t states = literal_states(
+			literal_pos_bits, literal_context_bits);
+
+	// Allocate a new literal coder, if needed.
+	if (*coder == NULL || (**coder).literal_context_bits
+				!= literal_context_bits
+			|| (**coder).literal_pos_bits != literal_pos_bits) {
+		// Free the old coder, if any.
+		lzma_free(*coder, allocator);
+
+		// Allocate a new one.
+		*coder = lzma_alloc(sizeof(lzma_literal_coder)
+				+ states * LIT_SIZE * sizeof(probability),
+				allocator);
+		if (*coder == NULL)
+			return LZMA_MEM_ERROR;
+
+		// Store the new settings.
+		(**coder).literal_context_bits = literal_context_bits;
+		(**coder).literal_pos_bits = literal_pos_bits;
+
+		// Calculate also the literal_pos_mask. It's not changed
+		// anywhere else than here.
+		(**coder).literal_pos_mask = (1 << literal_pos_bits) - 1;
+	}
+
+	// Reset the literal coder.
+	for (uint32_t i = 0; i < states; ++i)
+		for (uint32_t j = 0; j < LIT_SIZE; ++j)
+			bit_reset((**coder).coders[i][j]);
+
+	return LZMA_OK;
+}
+
+
+extern void
+lzma_literal_end(lzma_literal_coder **coder, lzma_allocator *allocator)
+{
+	lzma_free(*coder, allocator);
+	*coder = NULL;
+}
diff --git a/src/liblzma/lzma/lzma_literal.h b/src/liblzma/lzma/lzma_literal.h
new file mode 100644
index 00000000..174f5ed4
--- /dev/null
+++ b/src/liblzma/lzma/lzma_literal.h
@@ -0,0 +1,74 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       lzma_literal.h
+/// \brief      Literal Coder
+///
+/// This is used as is by both LZMA encoder and decoder.
+//
+//  Copyright (C) 1999-2006 Igor Pavlov
+//  Copyright (C) 2007 Lasse Collin
+//
+//  This library is free software; you can redistribute it and/or
+//  modify it under the terms of the GNU Lesser General Public
+//  License as published by the Free Software Foundation; either
+//  version 2.1 of the License, or (at your option) any later version.
+//
+//  This library is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+//  Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#ifndef LZMA_LITERAL_H
+#define LZMA_LITERAL_H
+
+#include "common.h"
+
+// We need typedef of `probability'.
+#include "range_common.h"
+
+
+/// Each literal coder is divided in three sections:
+///   - 0x001-0x0FF: Without match byte
+///   - 0x101-0x1FF: With match byte; match bit is 0
+///   - 0x201-0x2FF: With match byte; match bit is 1
+#define LIT_SIZE 0x300
+
+/// Calculate how many states are needed. Each state has
+/// LIT_SIZE `probability' variables.
+#define literal_states(literal_context_bits, literal_pos_bits) \
+	(1U << ((literal_context_bits) + (literal_pos_bits)))
+
+/// Locate the literal coder for the next literal byte. The choice depends on
+///   - the lowest literal_pos_bits bits of the position of the current
+///     byte; and
+///   - the highest literal_context_bits bits of the previous byte.
+#define literal_get_subcoder(literal_coder, pos, prev_byte) \
+	(literal_coder)->coders[(((pos) & (literal_coder)->literal_pos_mask) \
+			<< (literal_coder)->literal_context_bits) \
+		+ ((prev_byte) >> (8 - (literal_coder)->literal_context_bits))]
+
+
+typedef struct {
+	uint32_t literal_context_bits;
+	uint32_t literal_pos_bits;
+
+	/// literal_pos_mask is always (1 << literal_pos_bits) - 1.
+	uint32_t literal_pos_mask;
+
+	/// There are (1 << (literal_pos_bits + literal_context_bits))
+	/// literal coders.
+	probability coders[][LIT_SIZE];
+
+} lzma_literal_coder;
+
+
+extern lzma_ret lzma_literal_init(
+		lzma_literal_coder **coder, lzma_allocator *allocator,
+		uint32_t literal_context_bits, uint32_t literal_pos_bits);
+
+extern void lzma_literal_end(
+		lzma_literal_coder **coder, lzma_allocator *allocator);
+
+#endif