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

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

17 files changed, 5068 insertions, 0 deletions

diff --git a/src/liblzma/lzma/Makefile.inc b/src/liblzma/lzma/Makefile.inc
new file mode 100644
index 0000000..25440d8
--- /dev/null
+++ b/src/liblzma/lzma/Makefile.inc
@@ -0,0 +1,44 @@
+##
+## Author: Lasse Collin
+##
+## This file has been put into the public domain.
+## You can do whatever you want with this file.
+##
+
+EXTRA_DIST += lzma/fastpos_tablegen.c
+
+liblzma_la_SOURCES += \
+	lzma/lzma_common.h \
+	lzma/lzma_encoder_presets.c
+
+if COND_ENCODER_LZMA1
+liblzma_la_SOURCES += \
+	lzma/fastpos.h \
+	lzma/lzma_encoder.h \
+	lzma/lzma_encoder.c \
+	lzma/lzma_encoder_private.h \
+	lzma/lzma_encoder_optimum_fast.c \
+	lzma/lzma_encoder_optimum_normal.c
+
+if !COND_SMALL
+liblzma_la_SOURCES += lzma/fastpos_table.c
+endif
+endif
+
+if COND_DECODER_LZMA1
+liblzma_la_SOURCES += \
+	lzma/lzma_decoder.c \
+	lzma/lzma_decoder.h
+endif
+
+if COND_ENCODER_LZMA2
+liblzma_la_SOURCES += \
+	lzma/lzma2_encoder.c \
+	lzma/lzma2_encoder.h
+endif
+
+if COND_DECODER_LZMA2
+liblzma_la_SOURCES += \
+	lzma/lzma2_decoder.c \
+	lzma/lzma2_decoder.h
+endif
diff --git a/src/liblzma/lzma/fastpos.h b/src/liblzma/lzma/fastpos.h
new file mode 100644
index 0000000..dbeb16f
--- /dev/null
+++ b/src/liblzma/lzma/fastpos.h
@@ -0,0 +1,142 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       fastpos.h
+/// \brief      Kind of two-bit version of bit scan reverse
+///
+//  Authors:    Igor Pavlov
+//              Lasse Collin
+//
+//  This file has been put into the public domain.
+//  You can do whatever you want with this file.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#ifndef LZMA_FASTPOS_H
+#define LZMA_FASTPOS_H
+
+// LZMA encodes match distances by storing the highest two bits using
+// a six-bit value [0, 63], and then the missing lower bits.
+// Dictionary size is also stored using this encoding in the .xz
+// file format header.
+//
+// fastpos.h provides a way to quickly find out the correct six-bit
+// values. The following table gives some examples of this encoding:
+//
+//     dist   return
+//       0       0
+//       1       1
+//       2       2
+//       3       3
+//       4       4
+//       5       4
+//       6       5
+//       7       5
+//       8       6
+//      11       6
+//      12       7
+//     ...      ...
+//      15       7
+//      16       8
+//      17       8
+//     ...      ...
+//      23       8
+//      24       9
+//      25       9
+//     ...      ...
+//
+//
+// Provided functions or macros
+// ----------------------------
+//
+// get_dist_slot(dist) is the basic version. get_dist_slot_2(dist)
+// assumes that dist >= FULL_DISTANCES, thus the result is at least
+// FULL_DISTANCES_BITS * 2. Using get_dist_slot(dist) instead of
+// get_dist_slot_2(dist) would give the same result, but get_dist_slot_2(dist)
+// should be tiny bit faster due to the assumption being made.
+//
+//
+// Size vs. speed
+// --------------
+//
+// With some CPUs that have fast BSR (bit scan reverse) instruction, the
+// size optimized version is slightly faster than the bigger table based
+// approach. Such CPUs include Intel Pentium Pro, Pentium II, Pentium III
+// and Core 2 (possibly others). AMD K7 seems to have slower BSR, but that
+// would still have speed roughly comparable to the table version. Older
+// x86 CPUs like the original Pentium have very slow BSR; on those systems
+// the table version is a lot faster.
+//
+// On some CPUs, the table version is a lot faster when using position
+// dependent code, but with position independent code the size optimized
+// version is slightly faster. This occurs at least on 32-bit SPARC (no
+// ASM optimizations).
+//
+// I'm making the table version the default, because that has good speed
+// on all systems I have tried. The size optimized version is sometimes
+// slightly faster, but sometimes it is a lot slower.
+
+#ifdef HAVE_SMALL
+#	define get_dist_slot(dist) \
+		((dist) <= 4 ? (dist) : get_dist_slot_2(dist))
+
+static inline uint32_t
+get_dist_slot_2(uint32_t dist)
+{
+	const uint32_t i = bsr32(dist);
+	return (i + i) + ((dist >> (i - 1)) & 1);
+}
+
+
+#else
+
+#define FASTPOS_BITS 13
+
+lzma_attr_visibility_hidden
+extern const uint8_t lzma_fastpos[1 << FASTPOS_BITS];
+
+
+#define fastpos_shift(extra, n) \
+	((extra) + (n) * (FASTPOS_BITS - 1))
+
+#define fastpos_limit(extra, n) \
+	(UINT32_C(1) << (FASTPOS_BITS + fastpos_shift(extra, n)))
+
+#define fastpos_result(dist, extra, n) \
+	(uint32_t)(lzma_fastpos[(dist) >> fastpos_shift(extra, n)]) \
+			+ 2 * fastpos_shift(extra, n)
+
+
+static inline uint32_t
+get_dist_slot(uint32_t dist)
+{
+	// If it is small enough, we can pick the result directly from
+	// the precalculated table.
+	if (dist < fastpos_limit(0, 0))
+		return lzma_fastpos[dist];
+
+	if (dist < fastpos_limit(0, 1))
+		return fastpos_result(dist, 0, 1);
+
+	return fastpos_result(dist, 0, 2);
+}
+
+
+#ifdef FULL_DISTANCES_BITS
+static inline uint32_t
+get_dist_slot_2(uint32_t dist)
+{
+	assert(dist >= FULL_DISTANCES);
+
+	if (dist < fastpos_limit(FULL_DISTANCES_BITS - 1, 0))
+		return fastpos_result(dist, FULL_DISTANCES_BITS - 1, 0);
+
+	if (dist < fastpos_limit(FULL_DISTANCES_BITS - 1, 1))
+		return fastpos_result(dist, FULL_DISTANCES_BITS - 1, 1);
+
+	return fastpos_result(dist, FULL_DISTANCES_BITS - 1, 2);
+}
+#endif
+
+#endif
+
+#endif
diff --git a/src/liblzma/lzma/fastpos_table.c b/src/liblzma/lzma/fastpos_table.c
new file mode 100644
index 0000000..6a3ceac
--- /dev/null
+++ b/src/liblzma/lzma/fastpos_table.c
@@ -0,0 +1,519 @@
+/* This file has been automatically generated by fastpos_tablegen.c. */
+
+#include "common.h"
+#include "fastpos.h"
+
+const uint8_t lzma_fastpos[1 << FASTPOS_BITS] = {
+	  0,  1,  2,  3,  4,  4,  5,  5,  6,  6,  6,  6,  7,  7,  7,  7,
+	  8,  8,  8,  8,  8,  8,  8,  8,  9,  9,  9,  9,  9,  9,  9,  9,
+	 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
+	 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
+	 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
+	 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
+	 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
+	 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
+	 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
+	 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
+	 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
+	 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
+	 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
+	 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
+	 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
+	 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
+	 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
+	 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
+	 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
+	 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
+	 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
+	 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
+	 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
+	 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
+	 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
+	 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
+	 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
+	 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
+	 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
+	 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
+	 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
+	 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
+	 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
+	 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
+	 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
+	 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
+	 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
+	 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
+	 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
+	 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
+	 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
+	 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
+	 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
+	 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
+	 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
+	 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
+	 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
+	 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
+	 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
+	 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
+	 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
+	 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
+	 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
+	 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
+	 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
+	 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
+	 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
+	 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
+	 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
+	 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
+	 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
+	 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
+	 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
+	 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
+	 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
+	 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
+	 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
+	 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
+	 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
+	 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
+	 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
+	 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
+	 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
+	 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
+	 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
+	 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
+	 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
+	 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
+	 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
+	 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
+	 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
+	 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
+	 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
+	 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
+	 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
+	 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
+	 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
+	 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
+	 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
+	 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
+	 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
+	 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
+	 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
+	 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
+	 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
+	 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
+	 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
+	 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
+	 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
+	 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
+	 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
+	 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
+	 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
+	 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
+	 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
+	 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
+	 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
+	 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
+	 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
+	 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
+	 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
+	 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
+	 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
+	 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
+	 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
+	 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
+	 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
+	 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
+	 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
+	 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
+	 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
+	 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
+	 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
+	 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
+	 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
+	 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
+	 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
+	 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+	 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25
+};
diff --git a/src/liblzma/lzma/fastpos_tablegen.c b/src/liblzma/lzma/fastpos_tablegen.c
new file mode 100644
index 0000000..57ed150
--- /dev/null
+++ b/src/liblzma/lzma/fastpos_tablegen.c
@@ -0,0 +1,57 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       fastpos_tablegen.c
+/// \brief      Generates the lzma_fastpos[] lookup table
+///
+//  Authors:    Igor Pavlov
+//              Lasse Collin
+//
+//  This file has been put into the public domain.
+//  You can do whatever you want with this file.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include <inttypes.h>
+#include <stdio.h>
+
+#define lzma_attr_visibility_hidden
+#include "fastpos.h"
+
+
+int
+main(void)
+{
+	uint8_t fastpos[1 << FASTPOS_BITS];
+
+	const uint8_t fast_slots = 2 * FASTPOS_BITS;
+	uint32_t c = 2;
+
+	fastpos[0] = 0;
+	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)
+			fastpos[c] = slot_fast;
+	}
+
+	printf("/* This file has been automatically generated "
+			"by fastpos_tablegen.c. */\n\n"
+			"#include \"common.h\"\n"
+			"#include \"fastpos.h\"\n\n"
+			"const uint8_t lzma_fastpos[1 << FASTPOS_BITS] = {");
+
+	for (size_t i = 0; i < (1 << FASTPOS_BITS); ++i) {
+		if (i % 16 == 0)
+			printf("\n\t");
+
+		printf("%3u", (unsigned int)(fastpos[i]));
+
+		if (i != (1 << FASTPOS_BITS) - 1)
+			printf(",");
+	}
+
+	printf("\n};\n");
+
+	return 0;
+}
diff --git a/src/liblzma/lzma/lzma2_decoder.c b/src/liblzma/lzma/lzma2_decoder.c
new file mode 100644
index 0000000..567df49
--- /dev/null
+++ b/src/liblzma/lzma/lzma2_decoder.c
@@ -0,0 +1,311 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       lzma2_decoder.c
+/// \brief      LZMA2 decoder
+///
+//  Authors:    Igor Pavlov
+//              Lasse Collin
+//
+//  This file has been put into the public domain.
+//  You can do whatever you want with this file.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include "lzma2_decoder.h"
+#include "lz_decoder.h"
+#include "lzma_decoder.h"
+
+
+typedef struct {
+	enum sequence {
+		SEQ_CONTROL,
+		SEQ_UNCOMPRESSED_1,
+		SEQ_UNCOMPRESSED_2,
+		SEQ_COMPRESSED_0,
+		SEQ_COMPRESSED_1,
+		SEQ_PROPERTIES,
+		SEQ_LZMA,
+		SEQ_COPY,
+	} sequence;
+
+	/// Sequence after the size fields have been decoded.
+	enum sequence next_sequence;
+
+	/// LZMA decoder
+	lzma_lz_decoder lzma;
+
+	/// Uncompressed size of LZMA chunk
+	size_t uncompressed_size;
+
+	/// Compressed size of the chunk (naturally equals to uncompressed
+	/// size of uncompressed chunk)
+	size_t compressed_size;
+
+	/// True if properties are needed. This is false before the
+	/// first LZMA chunk.
+	bool need_properties;
+
+	/// True if dictionary reset is needed. This is false before the
+	/// first chunk (LZMA or uncompressed).
+	bool need_dictionary_reset;
+
+	lzma_options_lzma options;
+} lzma_lzma2_coder;
+
+
+static lzma_ret
+lzma2_decode(void *coder_ptr, lzma_dict *restrict dict,
+		const uint8_t *restrict in, size_t *restrict in_pos,
+		size_t in_size)
+{
+	lzma_lzma2_coder *restrict coder = coder_ptr;
+
+	// With SEQ_LZMA it is possible that no new input is needed to do
+	// some progress. The rest of the sequences assume that there is
+	// at least one byte of input.
+	while (*in_pos < in_size || coder->sequence == SEQ_LZMA)
+	switch (coder->sequence) {
+	case SEQ_CONTROL: {
+		const uint32_t control = in[*in_pos];
+		++*in_pos;
+
+		// End marker
+		if (control == 0x00)
+			return LZMA_STREAM_END;
+
+		if (control >= 0xE0 || control == 1) {
+			// Dictionary reset implies that next LZMA chunk has
+			// to set new properties.
+			coder->need_properties = true;
+			coder->need_dictionary_reset = true;
+		} else if (coder->need_dictionary_reset) {
+			return LZMA_DATA_ERROR;
+		}
+
+		if (control >= 0x80) {
+			// LZMA chunk. The highest five bits of the
+			// uncompressed size are taken from the control byte.
+			coder->uncompressed_size = (control & 0x1F) << 16;
+			coder->sequence = SEQ_UNCOMPRESSED_1;
+
+			// See if there are new properties or if we need to
+			// reset the state.
+			if (control >= 0xC0) {
+				// When there are new properties, state reset
+				// is done at SEQ_PROPERTIES.
+				coder->need_properties = false;
+				coder->next_sequence = SEQ_PROPERTIES;
+
+			} else if (coder->need_properties) {
+				return LZMA_DATA_ERROR;
+
+			} else {
+				coder->next_sequence = SEQ_LZMA;
+
+				// If only state reset is wanted with old
+				// properties, do the resetting here for
+				// simplicity.
+				if (control >= 0xA0)
+					coder->lzma.reset(coder->lzma.coder,
+							&coder->options);
+			}
+		} else {
+			// Invalid control values
+			if (control > 2)
+				return LZMA_DATA_ERROR;
+
+			// It's uncompressed chunk
+			coder->sequence = SEQ_COMPRESSED_0;
+			coder->next_sequence = SEQ_COPY;
+		}
+
+		if (coder->need_dictionary_reset) {
+			// Finish the dictionary reset and let the caller
+			// flush the dictionary to the actual output buffer.
+			coder->need_dictionary_reset = false;
+			dict_reset(dict);
+			return LZMA_OK;
+		}
+
+		break;
+	}
+
+	case SEQ_UNCOMPRESSED_1:
+		coder->uncompressed_size += (uint32_t)(in[(*in_pos)++]) << 8;
+		coder->sequence = SEQ_UNCOMPRESSED_2;
+		break;
+
+	case SEQ_UNCOMPRESSED_2:
+		coder->uncompressed_size += in[(*in_pos)++] + 1U;
+		coder->sequence = SEQ_COMPRESSED_0;
+		coder->lzma.set_uncompressed(coder->lzma.coder,
+				coder->uncompressed_size, false);
+		break;
+
+	case SEQ_COMPRESSED_0:
+		coder->compressed_size = (uint32_t)(in[(*in_pos)++]) << 8;
+		coder->sequence = SEQ_COMPRESSED_1;
+		break;
+
+	case SEQ_COMPRESSED_1:
+		coder->compressed_size += in[(*in_pos)++] + 1U;
+		coder->sequence = coder->next_sequence;
+		break;
+
+	case SEQ_PROPERTIES:
+		if (lzma_lzma_lclppb_decode(&coder->options, in[(*in_pos)++]))
+			return LZMA_DATA_ERROR;
+
+		coder->lzma.reset(coder->lzma.coder, &coder->options);
+
+		coder->sequence = SEQ_LZMA;
+		break;
+
+	case SEQ_LZMA: {
+		// Store the start offset so that we can update
+		// coder->compressed_size later.
+		const size_t in_start = *in_pos;
+
+		// Decode from in[] to *dict.
+		const lzma_ret ret = coder->lzma.code(coder->lzma.coder,
+				dict, in, in_pos, in_size);
+
+		// Validate and update coder->compressed_size.
+		const size_t in_used = *in_pos - in_start;
+		if (in_used > coder->compressed_size)
+			return LZMA_DATA_ERROR;
+
+		coder->compressed_size -= in_used;
+
+		// Return if we didn't finish the chunk, or an error occurred.
+		if (ret != LZMA_STREAM_END)
+			return ret;
+
+		// The LZMA decoder must have consumed the whole chunk now.
+		// We don't need to worry about uncompressed size since it
+		// is checked by the LZMA decoder.
+		if (coder->compressed_size != 0)
+			return LZMA_DATA_ERROR;
+
+		coder->sequence = SEQ_CONTROL;
+		break;
+	}
+
+	case SEQ_COPY: {
+		// Copy from input to the dictionary as is.
+		dict_write(dict, in, in_pos, in_size, &coder->compressed_size);
+		if (coder->compressed_size != 0)
+			return LZMA_OK;
+
+		coder->sequence = SEQ_CONTROL;
+		break;
+	}
+
+	default:
+		assert(0);
+		return LZMA_PROG_ERROR;
+	}
+
+	return LZMA_OK;
+}
+
+
+static void
+lzma2_decoder_end(void *coder_ptr, const lzma_allocator *allocator)
+{
+	lzma_lzma2_coder *coder = coder_ptr;
+
+	assert(coder->lzma.end == NULL);
+	lzma_free(coder->lzma.coder, allocator);
+
+	lzma_free(coder, allocator);
+
+	return;
+}
+
+
+static lzma_ret
+lzma2_decoder_init(lzma_lz_decoder *lz, const lzma_allocator *allocator,
+		lzma_vli id lzma_attribute((__unused__)), const void *opt,
+		lzma_lz_options *lz_options)
+{
+	lzma_lzma2_coder *coder = lz->coder;
+	if (coder == NULL) {
+		coder = lzma_alloc(sizeof(lzma_lzma2_coder), allocator);
+		if (coder == NULL)
+			return LZMA_MEM_ERROR;
+
+		lz->coder = coder;
+		lz->code = &lzma2_decode;
+		lz->end = &lzma2_decoder_end;
+
+		coder->lzma = LZMA_LZ_DECODER_INIT;
+	}
+
+	const lzma_options_lzma *options = opt;
+
+	coder->sequence = SEQ_CONTROL;
+	coder->need_properties = true;
+	coder->need_dictionary_reset = options->preset_dict == NULL
+			|| options->preset_dict_size == 0;
+
+	return lzma_lzma_decoder_create(&coder->lzma,
+			allocator, options, lz_options);
+}
+
+
+extern lzma_ret
+lzma_lzma2_decoder_init(lzma_next_coder *next, const lzma_allocator *allocator,
+		const lzma_filter_info *filters)
+{
+	// LZMA2 can only be the last filter in the chain. This is enforced
+	// by the raw_decoder initialization.
+	assert(filters[1].init == NULL);
+
+	return lzma_lz_decoder_init(next, allocator, filters,
+			&lzma2_decoder_init);
+}
+
+
+extern uint64_t
+lzma_lzma2_decoder_memusage(const void *options)
+{
+	return sizeof(lzma_lzma2_coder)
+			+ lzma_lzma_decoder_memusage_nocheck(options);
+}
+
+
+extern lzma_ret
+lzma_lzma2_props_decode(void **options, const lzma_allocator *allocator,
+		const uint8_t *props, size_t props_size)
+{
+	if (props_size != 1)
+		return LZMA_OPTIONS_ERROR;
+
+	// Check that reserved bits are unset.
+	if (props[0] & 0xC0)
+		return LZMA_OPTIONS_ERROR;
+
+	// Decode the dictionary size.
+	if (props[0] > 40)
+		return LZMA_OPTIONS_ERROR;
+
+	lzma_options_lzma *opt = lzma_alloc(
+			sizeof(lzma_options_lzma), allocator);
+	if (opt == NULL)
+		return LZMA_MEM_ERROR;
+
+	if (props[0] == 40) {
+		opt->dict_size = UINT32_MAX;
+	} else {
+		opt->dict_size = 2 | (props[0] & 1U);
+		opt->dict_size <<= props[0] / 2U + 11;
+	}
+
+	opt->preset_dict = NULL;
+	opt->preset_dict_size = 0;
+
+	*options = opt;
+
+	return LZMA_OK;
+}
diff --git a/src/liblzma/lzma/lzma2_decoder.h b/src/liblzma/lzma/lzma2_decoder.h
new file mode 100644
index 0000000..ef2dcbf
--- /dev/null
+++ b/src/liblzma/lzma/lzma2_decoder.h
@@ -0,0 +1,29 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       lzma2_decoder.h
+/// \brief      LZMA2 decoder
+///
+//  Authors:    Igor Pavlov
+//              Lasse Collin
+//
+//  This file has been put into the public domain.
+//  You can do whatever you want with this file.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#ifndef LZMA_LZMA2_DECODER_H
+#define LZMA_LZMA2_DECODER_H
+
+#include "common.h"
+
+extern lzma_ret lzma_lzma2_decoder_init(lzma_next_coder *next,
+		const lzma_allocator *allocator,
+		const lzma_filter_info *filters);
+
+extern uint64_t lzma_lzma2_decoder_memusage(const void *options);
+
+extern lzma_ret lzma_lzma2_props_decode(
+		void **options, const lzma_allocator *allocator,
+		const uint8_t *props, size_t props_size);
+
+#endif
diff --git a/src/liblzma/lzma/lzma2_encoder.c b/src/liblzma/lzma/lzma2_encoder.c
new file mode 100644
index 0000000..4b6b231
--- /dev/null
+++ b/src/liblzma/lzma/lzma2_encoder.c
@@ -0,0 +1,414 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       lzma2_encoder.c
+/// \brief      LZMA2 encoder
+///
+//  Authors:    Igor Pavlov
+//              Lasse Collin
+//
+//  This file has been put into the public domain.
+//  You can do whatever you want with this file.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include "lz_encoder.h"
+#include "lzma_encoder.h"
+#include "fastpos.h"
+#include "lzma2_encoder.h"
+
+
+typedef struct {
+	enum {
+		SEQ_INIT,
+		SEQ_LZMA_ENCODE,
+		SEQ_LZMA_COPY,
+		SEQ_UNCOMPRESSED_HEADER,
+		SEQ_UNCOMPRESSED_COPY,
+	} sequence;
+
+	/// LZMA encoder
+	void *lzma;
+
+	/// LZMA options currently in use.
+	lzma_options_lzma opt_cur;
+
+	bool need_properties;
+	bool need_state_reset;
+	bool need_dictionary_reset;
+
+	/// Uncompressed size of a chunk
+	size_t uncompressed_size;
+
+	/// Compressed size of a chunk (excluding headers); this is also used
+	/// to indicate the end of buf[] in SEQ_LZMA_COPY.
+	size_t compressed_size;
+
+	/// Read position in buf[]
+	size_t buf_pos;
+
+	/// Buffer to hold the chunk header and LZMA compressed data
+	uint8_t buf[LZMA2_HEADER_MAX + LZMA2_CHUNK_MAX];
+} lzma_lzma2_coder;
+
+
+static void
+lzma2_header_lzma(lzma_lzma2_coder *coder)
+{
+	assert(coder->uncompressed_size > 0);
+	assert(coder->uncompressed_size <= LZMA2_UNCOMPRESSED_MAX);
+	assert(coder->compressed_size > 0);
+	assert(coder->compressed_size <= LZMA2_CHUNK_MAX);
+
+	size_t pos;
+
+	if (coder->need_properties) {
+		pos = 0;
+
+		if (coder->need_dictionary_reset)
+			coder->buf[pos] = 0x80 + (3 << 5);
+		else
+			coder->buf[pos] = 0x80 + (2 << 5);
+	} else {
+		pos = 1;
+
+		if (coder->need_state_reset)
+			coder->buf[pos] = 0x80 + (1 << 5);
+		else
+			coder->buf[pos] = 0x80;
+	}
+
+	// Set the start position for copying.
+	coder->buf_pos = pos;
+
+	// Uncompressed size
+	size_t size = coder->uncompressed_size - 1;
+	coder->buf[pos++] += size >> 16;
+	coder->buf[pos++] = (size >> 8) & 0xFF;
+	coder->buf[pos++] = size & 0xFF;
+
+	// Compressed size
+	size = coder->compressed_size - 1;
+	coder->buf[pos++] = size >> 8;
+	coder->buf[pos++] = size & 0xFF;
+
+	// Properties, if needed
+	if (coder->need_properties)
+		lzma_lzma_lclppb_encode(&coder->opt_cur, coder->buf + pos);
+
+	coder->need_properties = false;
+	coder->need_state_reset = false;
+	coder->need_dictionary_reset = false;
+
+	// The copying code uses coder->compressed_size to indicate the end
+	// of coder->buf[], so we need add the maximum size of the header here.
+	coder->compressed_size += LZMA2_HEADER_MAX;
+
+	return;
+}
+
+
+static void
+lzma2_header_uncompressed(lzma_lzma2_coder *coder)
+{
+	assert(coder->uncompressed_size > 0);
+	assert(coder->uncompressed_size <= LZMA2_CHUNK_MAX);
+
+	// If this is the first chunk, we need to include dictionary
+	// reset indicator.
+	if (coder->need_dictionary_reset)
+		coder->buf[0] = 1;
+	else
+		coder->buf[0] = 2;
+
+	coder->need_dictionary_reset = false;
+
+	// "Compressed" size
+	coder->buf[1] = (coder->uncompressed_size - 1) >> 8;
+	coder->buf[2] = (coder->uncompressed_size - 1) & 0xFF;
+
+	// Set the start position for copying.
+	coder->buf_pos = 0;
+	return;
+}
+
+
+static lzma_ret
+lzma2_encode(void *coder_ptr, lzma_mf *restrict mf,
+		uint8_t *restrict out, size_t *restrict out_pos,
+		size_t out_size)
+{
+	lzma_lzma2_coder *restrict coder = coder_ptr;
+
+	while (*out_pos < out_size)
+	switch (coder->sequence) {
+	case SEQ_INIT:
+		// If there's no input left and we are flushing or finishing,
+		// don't start a new chunk.
+		if (mf_unencoded(mf) == 0) {
+			// Write end of payload marker if finishing.
+			if (mf->action == LZMA_FINISH)
+				out[(*out_pos)++] = 0;
+
+			return mf->action == LZMA_RUN
+					? LZMA_OK : LZMA_STREAM_END;
+		}
+
+		if (coder->need_state_reset)
+			return_if_error(lzma_lzma_encoder_reset(
+					coder->lzma, &coder->opt_cur));
+
+		coder->uncompressed_size = 0;
+		coder->compressed_size = 0;
+		coder->sequence = SEQ_LZMA_ENCODE;
+
+	// Fall through
+
+	case SEQ_LZMA_ENCODE: {
+		// Calculate how much more uncompressed data this chunk
+		// could accept.
+		const uint32_t left = LZMA2_UNCOMPRESSED_MAX
+				- coder->uncompressed_size;
+		uint32_t limit;
+
+		if (left < mf->match_len_max) {
+			// Must flush immediately since the next LZMA symbol
+			// could make the uncompressed size of the chunk too
+			// big.
+			limit = 0;
+		} else {
+			// Calculate maximum read_limit that is OK from point
+			// of view of LZMA2 chunk size.
+			limit = mf->read_pos - mf->read_ahead
+					+ left - mf->match_len_max;
+		}
+
+		// Save the start position so that we can update
+		// coder->uncompressed_size.
+		const uint32_t read_start = mf->read_pos - mf->read_ahead;
+
+		// Call the LZMA encoder until the chunk is finished.
+		const lzma_ret ret = lzma_lzma_encode(coder->lzma, mf,
+				coder->buf + LZMA2_HEADER_MAX,
+				&coder->compressed_size,
+				LZMA2_CHUNK_MAX, limit);
+
+		coder->uncompressed_size += mf->read_pos - mf->read_ahead
+				- read_start;
+
+		assert(coder->compressed_size <= LZMA2_CHUNK_MAX);
+		assert(coder->uncompressed_size <= LZMA2_UNCOMPRESSED_MAX);
+
+		if (ret != LZMA_STREAM_END)
+			return LZMA_OK;
+
+		// See if the chunk compressed. If it didn't, we encode it
+		// as uncompressed chunk. This saves a few bytes of space
+		// and makes decoding faster.
+		if (coder->compressed_size >= coder->uncompressed_size) {
+			coder->uncompressed_size += mf->read_ahead;
+			assert(coder->uncompressed_size
+					<= LZMA2_UNCOMPRESSED_MAX);
+			mf->read_ahead = 0;
+			lzma2_header_uncompressed(coder);
+			coder->need_state_reset = true;
+			coder->sequence = SEQ_UNCOMPRESSED_HEADER;
+			break;
+		}
+
+		// The chunk did compress at least by one byte, so we store
+		// the chunk as LZMA.
+		lzma2_header_lzma(coder);
+
+		coder->sequence = SEQ_LZMA_COPY;
+	}
+
+	// Fall through
+
+	case SEQ_LZMA_COPY:
+		// Copy the compressed chunk along its headers to the
+		// output buffer.
+		lzma_bufcpy(coder->buf, &coder->buf_pos,
+				coder->compressed_size,
+				out, out_pos, out_size);
+		if (coder->buf_pos != coder->compressed_size)
+			return LZMA_OK;
+
+		coder->sequence = SEQ_INIT;
+		break;
+
+	case SEQ_UNCOMPRESSED_HEADER:
+		// Copy the three-byte header to indicate uncompressed chunk.
+		lzma_bufcpy(coder->buf, &coder->buf_pos,
+				LZMA2_HEADER_UNCOMPRESSED,
+				out, out_pos, out_size);
+		if (coder->buf_pos != LZMA2_HEADER_UNCOMPRESSED)
+			return LZMA_OK;
+
+		coder->sequence = SEQ_UNCOMPRESSED_COPY;
+
+	// Fall through
+
+	case SEQ_UNCOMPRESSED_COPY:
+		// Copy the uncompressed data as is from the dictionary
+		// to the output buffer.
+		mf_read(mf, out, out_pos, out_size, &coder->uncompressed_size);
+		if (coder->uncompressed_size != 0)
+			return LZMA_OK;
+
+		coder->sequence = SEQ_INIT;
+		break;
+	}
+
+	return LZMA_OK;
+}
+
+
+static void
+lzma2_encoder_end(void *coder_ptr, const lzma_allocator *allocator)
+{
+	lzma_lzma2_coder *coder = coder_ptr;
+	lzma_free(coder->lzma, allocator);
+	lzma_free(coder, allocator);
+	return;
+}
+
+
+static lzma_ret
+lzma2_encoder_options_update(void *coder_ptr, const lzma_filter *filter)
+{
+	lzma_lzma2_coder *coder = coder_ptr;
+
+	// New options can be set only when there is no incomplete chunk.
+	// This is the case at the beginning of the raw stream and right
+	// after LZMA_SYNC_FLUSH.
+	if (filter->options == NULL || coder->sequence != SEQ_INIT)
+		return LZMA_PROG_ERROR;
+
+	// Look if there are new options. At least for now,
+	// only lc/lp/pb can be changed.
+	const lzma_options_lzma *opt = filter->options;
+	if (coder->opt_cur.lc != opt->lc || coder->opt_cur.lp != opt->lp
+			|| coder->opt_cur.pb != opt->pb) {
+		// Validate the options.
+		if (opt->lc > LZMA_LCLP_MAX || opt->lp > LZMA_LCLP_MAX
+				|| opt->lc + opt->lp > LZMA_LCLP_MAX
+				|| opt->pb > LZMA_PB_MAX)
+			return LZMA_OPTIONS_ERROR;
+
+		// The new options will be used when the encoder starts
+		// a new LZMA2 chunk.
+		coder->opt_cur.lc = opt->lc;
+		coder->opt_cur.lp = opt->lp;
+		coder->opt_cur.pb = opt->pb;
+		coder->need_properties = true;
+		coder->need_state_reset = true;
+	}
+
+	return LZMA_OK;
+}
+
+
+static lzma_ret
+lzma2_encoder_init(lzma_lz_encoder *lz, const lzma_allocator *allocator,
+		lzma_vli id lzma_attribute((__unused__)), const void *options,
+		lzma_lz_options *lz_options)
+{
+	if (options == NULL)
+		return LZMA_PROG_ERROR;
+
+	lzma_lzma2_coder *coder = lz->coder;
+	if (coder == NULL) {
+		coder = lzma_alloc(sizeof(lzma_lzma2_coder), allocator);
+		if (coder == NULL)
+			return LZMA_MEM_ERROR;
+
+		lz->coder = coder;
+		lz->code = &lzma2_encode;
+		lz->end = &lzma2_encoder_end;
+		lz->options_update = &lzma2_encoder_options_update;
+
+		coder->lzma = NULL;
+	}
+
+	coder->opt_cur = *(const lzma_options_lzma *)(options);
+
+	coder->sequence = SEQ_INIT;
+	coder->need_properties = true;
+	coder->need_state_reset = false;
+	coder->need_dictionary_reset
+			= coder->opt_cur.preset_dict == NULL
+			|| coder->opt_cur.preset_dict_size == 0;
+
+	// Initialize LZMA encoder
+	return_if_error(lzma_lzma_encoder_create(&coder->lzma, allocator,
+			LZMA_FILTER_LZMA2, &coder->opt_cur, lz_options));
+
+	// Make sure that we will always have enough history available in
+	// case we need to use uncompressed chunks. They are used when the
+	// compressed size of a chunk is not smaller than the uncompressed
+	// size, so we need to have at least LZMA2_COMPRESSED_MAX bytes
+	// history available.
+	if (lz_options->before_size + lz_options->dict_size < LZMA2_CHUNK_MAX)
+		lz_options->before_size
+				= LZMA2_CHUNK_MAX - lz_options->dict_size;
+
+	return LZMA_OK;
+}
+
+
+extern lzma_ret
+lzma_lzma2_encoder_init(lzma_next_coder *next, const lzma_allocator *allocator,
+		const lzma_filter_info *filters)
+{
+	return lzma_lz_encoder_init(
+			next, allocator, filters, &lzma2_encoder_init);
+}
+
+
+extern uint64_t
+lzma_lzma2_encoder_memusage(const void *options)
+{
+	const uint64_t lzma_mem = lzma_lzma_encoder_memusage(options);
+	if (lzma_mem == UINT64_MAX)
+		return UINT64_MAX;
+
+	return sizeof(lzma_lzma2_coder) + lzma_mem;
+}
+
+
+extern lzma_ret
+lzma_lzma2_props_encode(const void *options, uint8_t *out)
+{
+	if (options == NULL)
+		return LZMA_PROG_ERROR;
+
+	const lzma_options_lzma *const opt = options;
+	uint32_t d = my_max(opt->dict_size, LZMA_DICT_SIZE_MIN);
+
+	// Round up to the next 2^n - 1 or 2^n + 2^(n - 1) - 1 depending
+	// on which one is the next:
+	--d;
+	d |= d >> 2;
+	d |= d >> 3;
+	d |= d >> 4;
+	d |= d >> 8;
+	d |= d >> 16;
+
+	// Get the highest two bits using the proper encoding:
+	if (d == UINT32_MAX)
+		out[0] = 40;
+	else
+		out[0] = get_dist_slot(d + 1) - 24;
+
+	return LZMA_OK;
+}
+
+
+extern uint64_t
+lzma_lzma2_block_size(const void *options)
+{
+	const lzma_options_lzma *const opt = options;
+
+	// Use at least 1 MiB to keep compression ratio better.
+	return my_max((uint64_t)(opt->dict_size) * 3, UINT64_C(1) << 20);
+}
diff --git a/src/liblzma/lzma/lzma2_encoder.h b/src/liblzma/lzma/lzma2_encoder.h
new file mode 100644
index 0000000..515f183
--- /dev/null
+++ b/src/liblzma/lzma/lzma2_encoder.h
@@ -0,0 +1,43 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       lzma2_encoder.h
+/// \brief      LZMA2 encoder
+///
+//  Authors:    Igor Pavlov
+//              Lasse Collin
+//
+//  This file has been put into the public domain.
+//  You can do whatever you want with this file.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#ifndef LZMA_LZMA2_ENCODER_H
+#define LZMA_LZMA2_ENCODER_H
+
+#include "common.h"
+
+
+/// Maximum number of bytes of actual data per chunk (no headers)
+#define LZMA2_CHUNK_MAX (UINT32_C(1) << 16)
+
+/// Maximum uncompressed size of LZMA chunk (no headers)
+#define LZMA2_UNCOMPRESSED_MAX (UINT32_C(1) << 21)
+
+/// Maximum size of LZMA2 headers
+#define LZMA2_HEADER_MAX 6
+
+/// Size of a header for uncompressed chunk
+#define LZMA2_HEADER_UNCOMPRESSED 3
+
+
+extern lzma_ret lzma_lzma2_encoder_init(
+		lzma_next_coder *next, const lzma_allocator *allocator,
+		const lzma_filter_info *filters);
+
+extern uint64_t lzma_lzma2_encoder_memusage(const void *options);
+
+extern lzma_ret lzma_lzma2_props_encode(const void *options, uint8_t *out);
+
+extern uint64_t lzma_lzma2_block_size(const void *options);
+
+#endif
diff --git a/src/liblzma/lzma/lzma_common.h b/src/liblzma/lzma/lzma_common.h
new file mode 100644
index 0000000..9d040d9
--- /dev/null
+++ b/src/liblzma/lzma/lzma_common.h
@@ -0,0 +1,225 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       lzma_common.h
+/// \brief      Private definitions common to LZMA encoder and decoder
+///
+//  Authors:    Igor Pavlov
+//              Lasse Collin
+//
+//  This file has been put into the public domain.
+//  You can do whatever you want with this file.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#ifndef LZMA_LZMA_COMMON_H
+#define LZMA_LZMA_COMMON_H
+
+#include "common.h"
+#include "range_common.h"
+
+
+///////////////////
+// Miscellaneous //
+///////////////////
+
+/// Maximum number of position states. A position state is the lowest pos bits
+/// number of bits of the current uncompressed offset. In some places there
+/// are different sets of probabilities for different pos states.
+#define POS_STATES_MAX (1 << LZMA_PB_MAX)
+
+
+/// Validates lc, lp, and pb.
+static inline bool
+is_lclppb_valid(const lzma_options_lzma *options)
+{
+	return options->lc <= LZMA_LCLP_MAX && options->lp <= LZMA_LCLP_MAX
+			&& options->lc + options->lp <= LZMA_LCLP_MAX
+			&& options->pb <= LZMA_PB_MAX;
+}
+
+
+///////////
+// State //
+///////////
+
+/// This enum is used to track which events have occurred most recently and
+/// in which order. This information is used to predict the next event.
+///
+/// Events:
+///  - Literal: One 8-bit byte
+///  - Match: Repeat a chunk of data at some distance
+///  - Long repeat: Multi-byte match at a recently seen distance
+///  - Short repeat: One-byte repeat at a recently seen distance
+///
+/// The event names are in from STATE_oldest_older_previous. REP means
+/// either short or long repeated match, and NONLIT means any non-literal.
+typedef enum {
+	STATE_LIT_LIT,
+	STATE_MATCH_LIT_LIT,
+	STATE_REP_LIT_LIT,
+	STATE_SHORTREP_LIT_LIT,
+	STATE_MATCH_LIT,
+	STATE_REP_LIT,
+	STATE_SHORTREP_LIT,
+	STATE_LIT_MATCH,
+	STATE_LIT_LONGREP,
+	STATE_LIT_SHORTREP,
+	STATE_NONLIT_MATCH,
+	STATE_NONLIT_REP,
+} lzma_lzma_state;
+
+
+/// Total number of states
+#define STATES 12
+
+/// The lowest 7 states indicate that the previous state was a literal.
+#define LIT_STATES 7
+
+
+/// Indicate that the latest state was a literal.
+#define update_literal(state) \
+	state = ((state) <= STATE_SHORTREP_LIT_LIT \
+			? STATE_LIT_LIT \
+			: ((state) <= STATE_LIT_SHORTREP \
+				? (state) - 3 \
+				: (state) - 6))
+
+/// Indicate that the latest state was a match.
+#define update_match(state) \
+	state = ((state) < LIT_STATES ? STATE_LIT_MATCH : STATE_NONLIT_MATCH)
+
+/// Indicate that the latest state was a long repeated match.
+#define update_long_rep(state) \
+	state = ((state) < LIT_STATES ? STATE_LIT_LONGREP : STATE_NONLIT_REP)
+
+/// Indicate that the latest state was a short match.
+#define update_short_rep(state) \
+	state = ((state) < LIT_STATES ? STATE_LIT_SHORTREP : STATE_NONLIT_REP)
+
+/// Test if the previous state was a literal.
+#define is_literal_state(state) \
+	((state) < LIT_STATES)
+
+
+/////////////
+// Literal //
+/////////////
+
+/// 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
+///
+/// Match byte is used when the previous LZMA symbol was something else than
+/// a literal (that is, it was some kind of match).
+#define LITERAL_CODER_SIZE 0x300
+
+/// Maximum number of literal coders
+#define LITERAL_CODERS_MAX (1 << LZMA_LCLP_MAX)
+
+/// 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_subcoder(probs, lc, lp_mask, pos, prev_byte) \
+	((probs)[(((pos) & (lp_mask)) << (lc)) \
+			+ ((uint32_t)(prev_byte) >> (8U - (lc)))])
+
+
+static inline void
+literal_init(probability (*probs)[LITERAL_CODER_SIZE],
+		uint32_t lc, uint32_t lp)
+{
+	assert(lc + lp <= LZMA_LCLP_MAX);
+
+	const uint32_t coders = 1U << (lc + lp);
+
+	for (uint32_t i = 0; i < coders; ++i)
+		for (uint32_t j = 0; j < LITERAL_CODER_SIZE; ++j)
+			bit_reset(probs[i][j]);
+
+	return;
+}
+
+
+//////////////////
+// Match length //
+//////////////////
+
+// Minimum length of a match is two bytes.
+#define MATCH_LEN_MIN 2
+
+// Match length is encoded with 4, 5, or 10 bits.
+//
+// Length   Bits
+//  2-9      4 = Choice=0 + 3 bits
+// 10-17     5 = Choice=1 + Choice2=0 + 3 bits
+// 18-273   10 = Choice=1 + Choice2=1 + 8 bits
+#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)
+
+// Maximum length of a match is 273 which is a result of the encoding
+// described above.
+#define MATCH_LEN_MAX (MATCH_LEN_MIN + LEN_SYMBOLS - 1)
+
+
+////////////////////
+// Match distance //
+////////////////////
+
+// Different sets of probabilities are used for match distances that have very
+// short match length: Lengths of 2, 3, and 4 bytes have a separate set of
+// probabilities for each length. The matches with longer length use a shared
+// set of probabilities.
+#define DIST_STATES 4
+
+// Macro to get the index of the appropriate probability array.
+#define get_dist_state(len) \
+	((len) < DIST_STATES + MATCH_LEN_MIN \
+		? (len) - MATCH_LEN_MIN \
+		: DIST_STATES - 1)
+
+// The highest two bits of a match distance (distance slot) are encoded
+// using six bits. See fastpos.h for more explanation.
+#define DIST_SLOT_BITS 6
+#define DIST_SLOTS (1 << DIST_SLOT_BITS)
+
+// Match distances up to 127 are fully encoded using probabilities. Since
+// the highest two bits (distance slot) are always encoded using six bits,
+// the distances 0-3 don't need any additional bits to encode, since the
+// distance slot itself is the same as the actual distance. DIST_MODEL_START
+// indicates the first distance slot where at least one additional bit is
+// needed.
+#define DIST_MODEL_START 4
+
+// Match distances greater than 127 are encoded in three pieces:
+//   - distance slot: the highest two bits
+//   - direct bits: 2-26 bits below the highest two bits
+//   - alignment bits: four lowest bits
+//
+// Direct bits don't use any probabilities.
+//
+// The distance slot value of 14 is for distances 128-191 (see the table in
+// fastpos.h to understand why).
+#define DIST_MODEL_END 14
+
+// Distance slots that indicate a distance <= 127.
+#define FULL_DISTANCES_BITS (DIST_MODEL_END / 2)
+#define FULL_DISTANCES (1 << FULL_DISTANCES_BITS)
+
+// For match distances greater than 127, only the highest two bits and the
+// lowest four bits (alignment) is encoded using probabilities.
+#define ALIGN_BITS 4
+#define ALIGN_SIZE (1 << ALIGN_BITS)
+#define ALIGN_MASK (ALIGN_SIZE - 1)
+
+// LZMA remembers the four most recent match distances. Reusing these distances
+// tends to take less space than re-encoding the actual distance value.
+#define REPS 4
+
+#endif
diff --git a/src/liblzma/lzma/lzma_decoder.c b/src/liblzma/lzma/lzma_decoder.c
new file mode 100644
index 0000000..26c148a
--- /dev/null
+++ b/src/liblzma/lzma/lzma_decoder.c
@@ -0,0 +1,1133 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       lzma_decoder.c
+/// \brief      LZMA decoder
+///
+//  Authors:    Igor Pavlov
+//              Lasse Collin
+//
+//  This file has been put into the public domain.
+//  You can do whatever you want with this file.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include "lz_decoder.h"
+#include "lzma_common.h"
+#include "lzma_decoder.h"
+#include "range_decoder.h"
+
+// The macros unroll loops with switch statements.
+// Silence warnings about missing fall-through comments.
+#if TUKLIB_GNUC_REQ(7, 0)
+#	pragma GCC diagnostic ignored "-Wimplicit-fallthrough"
+#endif
+
+
+#ifdef HAVE_SMALL
+
+// Macros for (somewhat) size-optimized code.
+#define seq_4(seq) seq
+
+#define seq_6(seq) seq
+
+#define seq_8(seq) seq
+
+#define seq_len(seq) \
+	seq ## _CHOICE, \
+	seq ## _CHOICE2, \
+	seq ## _BITTREE
+
+#define len_decode(target, ld, pos_state, seq) \
+do { \
+case seq ## _CHOICE: \
+	rc_if_0(ld.choice, seq ## _CHOICE) { \
+		rc_update_0(ld.choice); \
+		probs = ld.low[pos_state];\
+		limit = LEN_LOW_SYMBOLS; \
+		target = MATCH_LEN_MIN; \
+	} else { \
+		rc_update_1(ld.choice); \
+case seq ## _CHOICE2: \
+		rc_if_0(ld.choice2, seq ## _CHOICE2) { \
+			rc_update_0(ld.choice2); \
+			probs = ld.mid[pos_state]; \
+			limit = LEN_MID_SYMBOLS; \
+			target = MATCH_LEN_MIN + LEN_LOW_SYMBOLS; \
+		} else { \
+			rc_update_1(ld.choice2); \
+			probs = ld.high; \
+			limit = LEN_HIGH_SYMBOLS; \
+			target = MATCH_LEN_MIN + LEN_LOW_SYMBOLS \
+					+ LEN_MID_SYMBOLS; \
+		} \
+	} \
+	symbol = 1; \
+case seq ## _BITTREE: \
+	do { \
+		rc_bit(probs[symbol], , , seq ## _BITTREE); \
+	} while (symbol < limit); \
+	target += symbol - limit; \
+} while (0)
+
+#else // HAVE_SMALL
+
+// Unrolled versions
+#define seq_4(seq) \
+	seq ## 0, \
+	seq ## 1, \
+	seq ## 2, \
+	seq ## 3
+
+#define seq_6(seq) \
+	seq ## 0, \
+	seq ## 1, \
+	seq ## 2, \
+	seq ## 3, \
+	seq ## 4, \
+	seq ## 5
+
+#define seq_8(seq) \
+	seq ## 0, \
+	seq ## 1, \
+	seq ## 2, \
+	seq ## 3, \
+	seq ## 4, \
+	seq ## 5, \
+	seq ## 6, \
+	seq ## 7
+
+#define seq_len(seq) \
+	seq ## _CHOICE, \
+	seq ## _LOW0, \
+	seq ## _LOW1, \
+	seq ## _LOW2, \
+	seq ## _CHOICE2, \
+	seq ## _MID0, \
+	seq ## _MID1, \
+	seq ## _MID2, \
+	seq ## _HIGH0, \
+	seq ## _HIGH1, \
+	seq ## _HIGH2, \
+	seq ## _HIGH3, \
+	seq ## _HIGH4, \
+	seq ## _HIGH5, \
+	seq ## _HIGH6, \
+	seq ## _HIGH7
+
+#define len_decode(target, ld, pos_state, seq) \
+do { \
+	symbol = 1; \
+case seq ## _CHOICE: \
+	rc_if_0(ld.choice, seq ## _CHOICE) { \
+		rc_update_0(ld.choice); \
+		rc_bit_case(ld.low[pos_state][symbol], , , seq ## _LOW0); \
+		rc_bit_case(ld.low[pos_state][symbol], , , seq ## _LOW1); \
+		rc_bit_case(ld.low[pos_state][symbol], , , seq ## _LOW2); \
+		target = symbol - LEN_LOW_SYMBOLS + MATCH_LEN_MIN; \
+	} else { \
+		rc_update_1(ld.choice); \
+case seq ## _CHOICE2: \
+		rc_if_0(ld.choice2, seq ## _CHOICE2) { \
+			rc_update_0(ld.choice2); \
+			rc_bit_case(ld.mid[pos_state][symbol], , , \
+					seq ## _MID0); \
+			rc_bit_case(ld.mid[pos_state][symbol], , , \
+					seq ## _MID1); \
+			rc_bit_case(ld.mid[pos_state][symbol], , , \
+					seq ## _MID2); \
+			target = symbol - LEN_MID_SYMBOLS \
+					+ MATCH_LEN_MIN + LEN_LOW_SYMBOLS; \
+		} else { \
+			rc_update_1(ld.choice2); \
+			rc_bit_case(ld.high[symbol], , , seq ## _HIGH0); \
+			rc_bit_case(ld.high[symbol], , , seq ## _HIGH1); \
+			rc_bit_case(ld.high[symbol], , , seq ## _HIGH2); \
+			rc_bit_case(ld.high[symbol], , , seq ## _HIGH3); \
+			rc_bit_case(ld.high[symbol], , , seq ## _HIGH4); \
+			rc_bit_case(ld.high[symbol], , , seq ## _HIGH5); \
+			rc_bit_case(ld.high[symbol], , , seq ## _HIGH6); \
+			rc_bit_case(ld.high[symbol], , , seq ## _HIGH7); \
+			target = symbol - LEN_HIGH_SYMBOLS \
+					+ MATCH_LEN_MIN \
+					+ LEN_LOW_SYMBOLS + LEN_MID_SYMBOLS; \
+		} \
+	} \
+} while (0)
+
+#endif // HAVE_SMALL
+
+
+/// Length decoder probabilities; see comments in lzma_common.h.
+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;
+
+
+typedef struct {
+	///////////////////
+	// Probabilities //
+	///////////////////
+
+	/// Literals; see comments in lzma_common.h.
+	probability literal[LITERAL_CODERS_MAX][LITERAL_CODER_SIZE];
+
+	/// 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_len_decoder.
+	probability is_rep0_long[STATES][POS_STATES_MAX];
+
+	/// Probability tree for the highest two bits of the match distance.
+	/// There is a separate probability tree for match lengths of
+	/// 2 (i.e. MATCH_LEN_MIN), 3, 4, and [5, 273].
+	probability dist_slot[DIST_STATES][DIST_SLOTS];
+
+	/// Probability trees for additional bits for match distance when the
+	/// distance is in the range [4, 127].
+	probability pos_special[FULL_DISTANCES - DIST_MODEL_END];
+
+	/// Probability tree for the lowest four bits of a match distance
+	/// that is equal to or greater than 128.
+	probability pos_align[ALIGN_SIZE];
+
+	/// Length of a normal match
+	lzma_length_decoder match_len_decoder;
+
+	/// Length of a repeated match
+	lzma_length_decoder rep_len_decoder;
+
+	///////////////////
+	// Decoder state //
+	///////////////////
+
+	// Range coder
+	lzma_range_decoder rc;
+
+	// Types of the most recently seen LZMA symbols
+	lzma_lzma_state 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_mask; // (1U << pb) - 1
+	uint32_t literal_context_bits;
+	uint32_t literal_pos_mask;
+
+	/// Uncompressed size as bytes, or LZMA_VLI_UNKNOWN if end of
+	/// payload marker is expected.
+	lzma_vli uncompressed_size;
+
+	/// True if end of payload marker (EOPM) is allowed even when
+	/// uncompressed_size is known; false if EOPM must not be present.
+	/// This is ignored if uncompressed_size == LZMA_VLI_UNKNOWN.
+	bool allow_eopm;
+
+	////////////////////////////////
+	// State of incomplete symbol //
+	////////////////////////////////
+
+	/// Position where to continue the decoder loop
+	enum {
+		SEQ_NORMALIZE,
+		SEQ_IS_MATCH,
+		seq_8(SEQ_LITERAL),
+		seq_8(SEQ_LITERAL_MATCHED),
+		SEQ_LITERAL_WRITE,
+		SEQ_IS_REP,
+		seq_len(SEQ_MATCH_LEN),
+		seq_6(SEQ_DIST_SLOT),
+		SEQ_DIST_MODEL,
+		SEQ_DIRECT,
+		seq_4(SEQ_ALIGN),
+		SEQ_EOPM,
+		SEQ_IS_REP0,
+		SEQ_SHORTREP,
+		SEQ_IS_REP0_LONG,
+		SEQ_IS_REP1,
+		SEQ_IS_REP2,
+		seq_len(SEQ_REP_LEN),
+		SEQ_COPY,
+	} sequence;
+
+	/// Base of the current probability tree
+	probability *probs;
+
+	/// Symbol being decoded. This is also used as an index variable in
+	/// bittree decoders: probs[symbol]
+	uint32_t symbol;
+
+	/// Used as a loop termination condition on bittree decoders and
+	/// direct bits decoder.
+	uint32_t limit;
+
+	/// Matched literal decoder: 0x100 or 0 to help avoiding branches.
+	/// Bittree reverse decoders: Offset of the next bit: 1 << offset
+	uint32_t offset;
+
+	/// If decoding a literal: match byte.
+	/// If decoding a match: length of the match.
+	uint32_t len;
+} lzma_lzma1_decoder;
+
+
+static lzma_ret
+lzma_decode(void *coder_ptr, lzma_dict *restrict dictptr,
+		const uint8_t *restrict in,
+		size_t *restrict in_pos, size_t in_size)
+{
+	lzma_lzma1_decoder *restrict coder = coder_ptr;
+
+	////////////////////
+	// Initialization //
+	////////////////////
+
+	{
+		const lzma_ret ret = rc_read_init(
+				&coder->rc, in, in_pos, in_size);
+		if (ret != LZMA_STREAM_END)
+			return ret;
+	}
+
+	///////////////
+	// Variables //
+	///////////////
+
+	// Making local copies of often-used variables improves both
+	// speed and readability.
+
+	lzma_dict dict = *dictptr;
+
+	const size_t dict_start = dict.pos;
+
+	// Range decoder
+	rc_to_local(coder->rc, *in_pos);
+
+	// 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;
+
+	const uint32_t pos_mask = coder->pos_mask;
+
+	// These variables are actually needed only if we last time ran
+	// out of input in the middle of the decoder loop.
+	probability *probs = coder->probs;
+	uint32_t symbol = coder->symbol;
+	uint32_t limit = coder->limit;
+	uint32_t offset = coder->offset;
+	uint32_t len = coder->len;
+
+	const uint32_t literal_pos_mask = coder->literal_pos_mask;
+	const uint32_t literal_context_bits = coder->literal_context_bits;
+
+	// Temporary variables
+	uint32_t pos_state = dict.pos & pos_mask;
+
+	lzma_ret ret = LZMA_OK;
+
+	// This is true when the next LZMA symbol is allowed to be EOPM.
+	// That is, if this is false, then EOPM is considered
+	// an invalid symbol and we will return LZMA_DATA_ERROR.
+	//
+	// EOPM is always required (not just allowed) when
+	// the uncompressed size isn't known. When uncompressed size
+	// is known, eopm_is_valid may be set to true later.
+	bool eopm_is_valid = coder->uncompressed_size == LZMA_VLI_UNKNOWN;
+
+	// If uncompressed size is known and there is enough output space
+	// to decode all the data, limit the available buffer space so that
+	// the main loop won't try to decode past the end of the stream.
+	bool might_finish_without_eopm = false;
+	if (coder->uncompressed_size != LZMA_VLI_UNKNOWN
+			&& coder->uncompressed_size <= dict.limit - dict.pos) {
+		dict.limit = dict.pos + (size_t)(coder->uncompressed_size);
+		might_finish_without_eopm = true;
+	}
+
+	// The main decoder loop. The "switch" is used to restart the decoder at
+	// correct location. Once restarted, the "switch" is no longer used.
+	switch (coder->sequence)
+	while (true) {
+		// Calculate new pos_state. This is skipped on the first loop
+		// since we already calculated it when setting up the local
+		// variables.
+		pos_state = dict.pos & pos_mask;
+
+	case SEQ_NORMALIZE:
+	case SEQ_IS_MATCH:
+		if (unlikely(might_finish_without_eopm
+				&& dict.pos == dict.limit)) {
+			// In rare cases there is a useless byte that needs
+			// to be read anyway.
+			rc_normalize(SEQ_NORMALIZE);
+
+			// If the range decoder state is such that we can
+			// be at the end of the LZMA stream, then the
+			// decoding is finished.
+			if (rc_is_finished(rc)) {
+				ret = LZMA_STREAM_END;
+				goto out;
+			}
+
+			// If the caller hasn't allowed EOPM to be present
+			// together with known uncompressed size, then the
+			// LZMA stream is corrupt.
+			if (!coder->allow_eopm) {
+				ret = LZMA_DATA_ERROR;
+				goto out;
+			}
+
+			// Otherwise continue decoding with the expectation
+			// that the next LZMA symbol is EOPM.
+			eopm_is_valid = true;
+		}
+
+		rc_if_0(coder->is_match[state][pos_state], SEQ_IS_MATCH) {
+			rc_update_0(coder->is_match[state][pos_state]);
+
+			// It's a literal i.e. a single 8-bit byte.
+
+			probs = literal_subcoder(coder->literal,
+					literal_context_bits, literal_pos_mask,
+					dict.pos, dict_get(&dict, 0));
+			symbol = 1;
+
+			if (is_literal_state(state)) {
+				// Decode literal without match byte.
+#ifdef HAVE_SMALL
+	case SEQ_LITERAL:
+				do {
+					rc_bit(probs[symbol], , , SEQ_LITERAL);
+				} while (symbol < (1 << 8));
+#else
+				rc_bit_case(probs[symbol], , , SEQ_LITERAL0);
+				rc_bit_case(probs[symbol], , , SEQ_LITERAL1);
+				rc_bit_case(probs[symbol], , , SEQ_LITERAL2);
+				rc_bit_case(probs[symbol], , , SEQ_LITERAL3);
+				rc_bit_case(probs[symbol], , , SEQ_LITERAL4);
+				rc_bit_case(probs[symbol], , , SEQ_LITERAL5);
+				rc_bit_case(probs[symbol], , , SEQ_LITERAL6);
+				rc_bit_case(probs[symbol], , , SEQ_LITERAL7);
+#endif
+			} else {
+				// Decode literal with match byte.
+				//
+				// We store the byte we compare against
+				// ("match byte") to "len" to minimize the
+				// number of variables we need to store
+				// between decoder calls.
+				len = (uint32_t)(dict_get(&dict, rep0)) << 1;
+
+				// The usage of "offset" allows omitting some
+				// branches, which should give tiny speed
+				// improvement on some CPUs. "offset" gets
+				// set to zero if match_bit didn't match.
+				offset = 0x100;
+
+#ifdef HAVE_SMALL
+	case SEQ_LITERAL_MATCHED:
+				do {
+					const uint32_t match_bit
+							= len & offset;
+					const uint32_t subcoder_index
+							= offset + match_bit
+							+ symbol;
+
+					rc_bit(probs[subcoder_index],
+							offset &= ~match_bit,
+							offset &= match_bit,
+							SEQ_LITERAL_MATCHED);
+
+					// It seems to be faster to do this
+					// here instead of putting it to the
+					// beginning of the loop and then
+					// putting the "case" in the middle
+					// of the loop.
+					len <<= 1;
+
+				} while (symbol < (1 << 8));
+#else
+				// Unroll the loop.
+				uint32_t match_bit;
+				uint32_t subcoder_index;
+
+#	define d(seq) \
+		case seq: \
+			match_bit = len & offset; \
+			subcoder_index = offset + match_bit + symbol; \
+			rc_bit(probs[subcoder_index], \
+					offset &= ~match_bit, \
+					offset &= match_bit, \
+					seq)
+
+				d(SEQ_LITERAL_MATCHED0);
+				len <<= 1;
+				d(SEQ_LITERAL_MATCHED1);
+				len <<= 1;
+				d(SEQ_LITERAL_MATCHED2);
+				len <<= 1;
+				d(SEQ_LITERAL_MATCHED3);
+				len <<= 1;
+				d(SEQ_LITERAL_MATCHED4);
+				len <<= 1;
+				d(SEQ_LITERAL_MATCHED5);
+				len <<= 1;
+				d(SEQ_LITERAL_MATCHED6);
+				len <<= 1;
+				d(SEQ_LITERAL_MATCHED7);
+#	undef d
+#endif
+			}
+
+			//update_literal(state);
+			// Use a lookup table to update to literal state,
+			// since compared to other state updates, this would
+			// need two branches.
+			static const lzma_lzma_state next_state[] = {
+				STATE_LIT_LIT,
+				STATE_LIT_LIT,
+				STATE_LIT_LIT,
+				STATE_LIT_LIT,
+				STATE_MATCH_LIT_LIT,
+				STATE_REP_LIT_LIT,
+				STATE_SHORTREP_LIT_LIT,
+				STATE_MATCH_LIT,
+				STATE_REP_LIT,
+				STATE_SHORTREP_LIT,
+				STATE_MATCH_LIT,
+				STATE_REP_LIT
+			};
+			state = next_state[state];
+
+	case SEQ_LITERAL_WRITE:
+			if (unlikely(dict_put(&dict, symbol))) {
+				coder->sequence = SEQ_LITERAL_WRITE;
+				goto out;
+			}
+
+			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.
+
+		rc_update_1(coder->is_match[state][pos_state]);
+
+	case SEQ_IS_REP:
+		rc_if_0(coder->is_rep[state], SEQ_IS_REP) {
+			// Not a repeated match
+			rc_update_0(coder->is_rep[state]);
+			update_match(state);
+
+			// 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.
+			len_decode(len, coder->match_len_decoder,
+					pos_state, SEQ_MATCH_LEN);
+
+			// Prepare to decode the highest two bits of the
+			// match distance.
+			probs = coder->dist_slot[get_dist_state(len)];
+			symbol = 1;
+
+#ifdef HAVE_SMALL
+	case SEQ_DIST_SLOT:
+			do {
+				rc_bit(probs[symbol], , , SEQ_DIST_SLOT);
+			} while (symbol < DIST_SLOTS);
+#else
+			rc_bit_case(probs[symbol], , , SEQ_DIST_SLOT0);
+			rc_bit_case(probs[symbol], , , SEQ_DIST_SLOT1);
+			rc_bit_case(probs[symbol], , , SEQ_DIST_SLOT2);
+			rc_bit_case(probs[symbol], , , SEQ_DIST_SLOT3);
+			rc_bit_case(probs[symbol], , , SEQ_DIST_SLOT4);
+			rc_bit_case(probs[symbol], , , SEQ_DIST_SLOT5);
+#endif
+			// Get rid of the highest bit that was needed for
+			// indexing of the probability array.
+			symbol -= DIST_SLOTS;
+			assert(symbol <= 63);
+
+			if (symbol < DIST_MODEL_START) {
+				// Match distances [0, 3] have only two bits.
+				rep0 = symbol;
+			} else {
+				// Decode the lowest [1, 29] bits of
+				// the match distance.
+				limit = (symbol >> 1) - 1;
+				assert(limit >= 1 && limit <= 30);
+				rep0 = 2 + (symbol & 1);
+
+				if (symbol < DIST_MODEL_END) {
+					// Prepare to decode the low bits for
+					// a distance of [4, 127].
+					assert(limit <= 5);
+					rep0 <<= limit;
+					assert(rep0 <= 96);
+					// -1 is fine, because we start
+					// decoding at probs[1], not probs[0].
+					// NOTE: This violates the C standard,
+					// since we are doing pointer
+					// arithmetic past the beginning of
+					// the array.
+					assert((int32_t)(rep0 - symbol - 1)
+							>= -1);
+					assert((int32_t)(rep0 - symbol - 1)
+							<= 82);
+					probs = coder->pos_special + rep0
+							- symbol - 1;
+					symbol = 1;
+					offset = 0;
+	case SEQ_DIST_MODEL:
+#ifdef HAVE_SMALL
+					do {
+						rc_bit(probs[symbol], ,
+							rep0 += 1U << offset,
+							SEQ_DIST_MODEL);
+					} while (++offset < limit);
+#else
+					switch (limit) {
+					case 5:
+						assert(offset == 0);
+						rc_bit(probs[symbol], ,
+							rep0 += 1U,
+							SEQ_DIST_MODEL);
+						++offset;
+						--limit;
+					case 4:
+						rc_bit(probs[symbol], ,
+							rep0 += 1U << offset,
+							SEQ_DIST_MODEL);
+						++offset;
+						--limit;
+					case 3:
+						rc_bit(probs[symbol], ,
+							rep0 += 1U << offset,
+							SEQ_DIST_MODEL);
+						++offset;
+						--limit;
+					case 2:
+						rc_bit(probs[symbol], ,
+							rep0 += 1U << offset,
+							SEQ_DIST_MODEL);
+						++offset;
+						--limit;
+					case 1:
+						// We need "symbol" only for
+						// indexing the probability
+						// array, thus we can use
+						// rc_bit_last() here to omit
+						// the unneeded updating of
+						// "symbol".
+						rc_bit_last(probs[symbol], ,
+							rep0 += 1U << offset,
+							SEQ_DIST_MODEL);
+					}
+#endif
+				} else {
+					// The distance is >= 128. Decode the
+					// lower bits without probabilities
+					// except the lowest four bits.
+					assert(symbol >= 14);
+					assert(limit >= 6);
+					limit -= ALIGN_BITS;
+					assert(limit >= 2);
+	case SEQ_DIRECT:
+					// Not worth manual unrolling
+					do {
+						rc_direct(rep0, SEQ_DIRECT);
+					} while (--limit > 0);
+
+					// Decode the lowest four bits using
+					// probabilities.
+					rep0 <<= ALIGN_BITS;
+					symbol = 1;
+#ifdef HAVE_SMALL
+					offset = 0;
+	case SEQ_ALIGN:
+					do {
+						rc_bit(coder->pos_align[
+								symbol], ,
+							rep0 += 1U << offset,
+							SEQ_ALIGN);
+					} while (++offset < ALIGN_BITS);
+#else
+	case SEQ_ALIGN0:
+					rc_bit(coder->pos_align[symbol], ,
+							rep0 += 1, SEQ_ALIGN0);
+	case SEQ_ALIGN1:
+					rc_bit(coder->pos_align[symbol], ,
+							rep0 += 2, SEQ_ALIGN1);
+	case SEQ_ALIGN2:
+					rc_bit(coder->pos_align[symbol], ,
+							rep0 += 4, SEQ_ALIGN2);
+	case SEQ_ALIGN3:
+					// Like in SEQ_DIST_MODEL, we don't
+					// need "symbol" for anything else
+					// than indexing the probability array.
+					rc_bit_last(coder->pos_align[symbol], ,
+							rep0 += 8, SEQ_ALIGN3);
+#endif
+
+					if (rep0 == UINT32_MAX) {
+						// End of payload marker was
+						// found. It may only be
+						// present if
+						//   - uncompressed size is
+						//     unknown or
+						//   - after known uncompressed
+						//     size amount of bytes has
+						//     been decompressed and
+						//     caller has indicated
+						//     that EOPM might be used
+						//     (it's not allowed in
+						//     LZMA2).
+						if (!eopm_is_valid) {
+							ret = LZMA_DATA_ERROR;
+							goto out;
+						}
+
+	case SEQ_EOPM:
+						// LZMA1 stream with
+						// end-of-payload marker.
+						rc_normalize(SEQ_EOPM);
+						ret = rc_is_finished(rc)
+							? LZMA_STREAM_END
+							: LZMA_DATA_ERROR;
+						goto out;
+					}
+				}
+			}
+
+			// Validate the distance we just decoded.
+			if (unlikely(!dict_is_distance_valid(&dict, rep0))) {
+				ret = LZMA_DATA_ERROR;
+				goto out;
+			}
+
+		} else {
+			rc_update_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.
+			//
+			// There cannot be a match if we haven't produced
+			// any output, so check that first.
+			if (unlikely(!dict_is_distance_valid(&dict, 0))) {
+				ret = LZMA_DATA_ERROR;
+				goto out;
+			}
+
+	case SEQ_IS_REP0:
+			rc_if_0(coder->is_rep0[state], SEQ_IS_REP0) {
+				rc_update_0(coder->is_rep0[state]);
+				// The distance is rep0.
+
+	case SEQ_IS_REP0_LONG:
+				rc_if_0(coder->is_rep0_long[state][pos_state],
+						SEQ_IS_REP0_LONG) {
+					rc_update_0(coder->is_rep0_long[
+							state][pos_state]);
+
+					update_short_rep(state);
+
+	case SEQ_SHORTREP:
+					if (unlikely(dict_put(&dict, dict_get(
+							&dict, rep0)))) {
+						coder->sequence = SEQ_SHORTREP;
+						goto out;
+					}
+
+					continue;
+				}
+
+				// Repeating more than one byte at
+				// distance of rep0.
+				rc_update_1(coder->is_rep0_long[
+						state][pos_state]);
+
+			} else {
+				rc_update_1(coder->is_rep0[state]);
+
+	case SEQ_IS_REP1:
+				// 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.
+				rc_if_0(coder->is_rep1[state], SEQ_IS_REP1) {
+					rc_update_0(coder->is_rep1[state]);
+
+					const uint32_t distance = rep1;
+					rep1 = rep0;
+					rep0 = distance;
+
+				} else {
+					rc_update_1(coder->is_rep1[state]);
+	case SEQ_IS_REP2:
+					rc_if_0(coder->is_rep2[state],
+							SEQ_IS_REP2) {
+						rc_update_0(coder->is_rep2[
+								state]);
+
+						const uint32_t distance = rep2;
+						rep2 = rep1;
+						rep1 = rep0;
+						rep0 = distance;
+
+					} else {
+						rc_update_1(coder->is_rep2[
+								state]);
+
+						const uint32_t distance = rep3;
+						rep3 = rep2;
+						rep2 = rep1;
+						rep1 = rep0;
+						rep0 = distance;
+					}
+				}
+			}
+
+			update_long_rep(state);
+
+			// Decode the length of the repeated match.
+			len_decode(len, coder->rep_len_decoder,
+					pos_state, SEQ_REP_LEN);
+		}
+
+		/////////////////////////////////
+		// 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_LEN_MIN);
+		assert(len <= MATCH_LEN_MAX);
+
+	case SEQ_COPY:
+		// Repeat len bytes from distance of rep0.
+		if (unlikely(dict_repeat(&dict, rep0, &len))) {
+			coder->sequence = SEQ_COPY;
+			goto out;
+		}
+	}
+
+out:
+	// Save state
+
+	// NOTE: Must not copy dict.limit.
+	dictptr->pos = dict.pos;
+	dictptr->full = dict.full;
+
+	rc_from_local(coder->rc, *in_pos);
+
+	coder->state = state;
+	coder->rep0 = rep0;
+	coder->rep1 = rep1;
+	coder->rep2 = rep2;
+	coder->rep3 = rep3;
+
+	coder->probs = probs;
+	coder->symbol = symbol;
+	coder->limit = limit;
+	coder->offset = offset;
+	coder->len = len;
+
+	// Update the remaining amount of uncompressed data if uncompressed
+	// size was known.
+	if (coder->uncompressed_size != LZMA_VLI_UNKNOWN) {
+		coder->uncompressed_size -= dict.pos - dict_start;
+
+		// If we have gotten all the output but the decoder wants
+		// to write more output, the file is corrupt. There are
+		// three SEQ values where output is produced.
+		if (coder->uncompressed_size == 0 && ret == LZMA_OK
+				&& (coder->sequence == SEQ_LITERAL_WRITE
+					|| coder->sequence == SEQ_SHORTREP
+					|| coder->sequence == SEQ_COPY))
+			ret = LZMA_DATA_ERROR;
+	}
+
+	if (ret == LZMA_STREAM_END) {
+		// Reset the range decoder so that it is ready to reinitialize
+		// for a new LZMA2 chunk.
+		rc_reset(coder->rc);
+		coder->sequence = SEQ_IS_MATCH;
+	}
+
+	return ret;
+}
+
+
+
+static void
+lzma_decoder_uncompressed(void *coder_ptr, lzma_vli uncompressed_size,
+		bool allow_eopm)
+{
+	lzma_lzma1_decoder *coder = coder_ptr;
+	coder->uncompressed_size = uncompressed_size;
+	coder->allow_eopm = allow_eopm;
+}
+
+
+static void
+lzma_decoder_reset(void *coder_ptr, const void *opt)
+{
+	lzma_lzma1_decoder *coder = coder_ptr;
+	const lzma_options_lzma *options = opt;
+
+	// NOTE: We assume that lc/lp/pb are valid since they were
+	// successfully decoded with lzma_lzma_decode_properties().
+
+	// Calculate pos_mask. We don't need pos_bits as is for anything.
+	coder->pos_mask = (1U << options->pb) - 1;
+
+	// Initialize the literal decoder.
+	literal_init(coder->literal, options->lc, options->lp);
+
+	coder->literal_context_bits = options->lc;
+	coder->literal_pos_mask = (1U << options->lp) - 1;
+
+	// State
+	coder->state = STATE_LIT_LIT;
+	coder->rep0 = 0;
+	coder->rep1 = 0;
+	coder->rep2 = 0;
+	coder->rep3 = 0;
+	coder->pos_mask = (1U << options->pb) - 1;
+
+	// Range decoder
+	rc_reset(coder->rc);
+
+	// Bit and bittree decoders
+	for (uint32_t i = 0; i < STATES; ++i) {
+		for (uint32_t j = 0; j <= coder->pos_mask; ++j) {
+			bit_reset(coder->is_match[i][j]);
+			bit_reset(coder->is_rep0_long[i][j]);
+		}
+
+		bit_reset(coder->is_rep[i]);
+		bit_reset(coder->is_rep0[i]);
+		bit_reset(coder->is_rep1[i]);
+		bit_reset(coder->is_rep2[i]);
+	}
+
+	for (uint32_t i = 0; i < DIST_STATES; ++i)
+		bittree_reset(coder->dist_slot[i], DIST_SLOT_BITS);
+
+	for (uint32_t i = 0; i < FULL_DISTANCES - DIST_MODEL_END; ++i)
+		bit_reset(coder->pos_special[i]);
+
+	bittree_reset(coder->pos_align, ALIGN_BITS);
+
+	// Len decoders (also bit/bittree)
+	const uint32_t num_pos_states = 1U << options->pb;
+	bit_reset(coder->match_len_decoder.choice);
+	bit_reset(coder->match_len_decoder.choice2);
+	bit_reset(coder->rep_len_decoder.choice);
+	bit_reset(coder->rep_len_decoder.choice2);
+
+	for (uint32_t pos_state = 0; pos_state < num_pos_states; ++pos_state) {
+		bittree_reset(coder->match_len_decoder.low[pos_state],
+				LEN_LOW_BITS);
+		bittree_reset(coder->match_len_decoder.mid[pos_state],
+				LEN_MID_BITS);
+
+		bittree_reset(coder->rep_len_decoder.low[pos_state],
+				LEN_LOW_BITS);
+		bittree_reset(coder->rep_len_decoder.mid[pos_state],
+				LEN_MID_BITS);
+	}
+
+	bittree_reset(coder->match_len_decoder.high, LEN_HIGH_BITS);
+	bittree_reset(coder->rep_len_decoder.high, LEN_HIGH_BITS);
+
+	coder->sequence = SEQ_IS_MATCH;
+	coder->probs = NULL;
+	coder->symbol = 0;
+	coder->limit = 0;
+	coder->offset = 0;
+	coder->len = 0;
+
+	return;
+}
+
+
+extern lzma_ret
+lzma_lzma_decoder_create(lzma_lz_decoder *lz, const lzma_allocator *allocator,
+		const lzma_options_lzma *options, lzma_lz_options *lz_options)
+{
+	if (lz->coder == NULL) {
+		lz->coder = lzma_alloc(sizeof(lzma_lzma1_decoder), allocator);
+		if (lz->coder == NULL)
+			return LZMA_MEM_ERROR;
+
+		lz->code = &lzma_decode;
+		lz->reset = &lzma_decoder_reset;
+		lz->set_uncompressed = &lzma_decoder_uncompressed;
+	}
+
+	// All dictionary sizes are OK here. LZ decoder will take care of
+	// the special cases.
+	lz_options->dict_size = options->dict_size;
+	lz_options->preset_dict = options->preset_dict;
+	lz_options->preset_dict_size = options->preset_dict_size;
+
+	return LZMA_OK;
+}
+
+
+/// Allocate and initialize LZMA decoder. This is used only via LZ
+/// initialization (lzma_lzma_decoder_init() passes function pointer to
+/// the LZ initialization).
+static lzma_ret
+lzma_decoder_init(lzma_lz_decoder *lz, const lzma_allocator *allocator,
+		lzma_vli id, const void *options, lzma_lz_options *lz_options)
+{
+	if (!is_lclppb_valid(options))
+		return LZMA_PROG_ERROR;
+
+	lzma_vli uncomp_size = LZMA_VLI_UNKNOWN;
+	bool allow_eopm = true;
+
+	if (id == LZMA_FILTER_LZMA1EXT) {
+		const lzma_options_lzma *opt = options;
+
+		// Only one flag is supported.
+		if (opt->ext_flags & ~LZMA_LZMA1EXT_ALLOW_EOPM)
+			return LZMA_OPTIONS_ERROR;
+
+		// FIXME? Using lzma_vli instead of uint64_t is weird because
+		// this has nothing to do with .xz headers and variable-length
+		// integer encoding. On the other hand, using LZMA_VLI_UNKNOWN
+		// instead of UINT64_MAX is clearer when unknown size is
+		// meant. A problem with using lzma_vli is that now we
+		// allow > LZMA_VLI_MAX which is fine in this file but
+		// it's still confusing. Note that alone_decoder.c also
+		// allows > LZMA_VLI_MAX when setting uncompressed size.
+		uncomp_size = opt->ext_size_low
+				+ ((uint64_t)(opt->ext_size_high) << 32);
+		allow_eopm = (opt->ext_flags & LZMA_LZMA1EXT_ALLOW_EOPM) != 0
+				|| uncomp_size == LZMA_VLI_UNKNOWN;
+	}
+
+	return_if_error(lzma_lzma_decoder_create(
+			lz, allocator, options, lz_options));
+
+	lzma_decoder_reset(lz->coder, options);
+	lzma_decoder_uncompressed(lz->coder, uncomp_size, allow_eopm);
+
+	return LZMA_OK;
+}
+
+
+extern lzma_ret
+lzma_lzma_decoder_init(lzma_next_coder *next, const lzma_allocator *allocator,
+		const lzma_filter_info *filters)
+{
+	// LZMA can only be the last filter in the chain. This is enforced
+	// by the raw_decoder initialization.
+	assert(filters[1].init == NULL);
+
+	return lzma_lz_decoder_init(next, allocator, filters,
+			&lzma_decoder_init);
+}
+
+
+extern bool
+lzma_lzma_lclppb_decode(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->pb = byte / (9 * 5);
+	byte -= options->pb * 9 * 5;
+	options->lp = byte / 9;
+	options->lc = byte - options->lp * 9;
+
+	return options->lc + options->lp > LZMA_LCLP_MAX;
+}
+
+
+extern uint64_t
+lzma_lzma_decoder_memusage_nocheck(const void *options)
+{
+	const lzma_options_lzma *const opt = options;
+	return sizeof(lzma_lzma1_decoder)
+			+ lzma_lz_decoder_memusage(opt->dict_size);
+}
+
+
+extern uint64_t
+lzma_lzma_decoder_memusage(const void *options)
+{
+	if (!is_lclppb_valid(options))
+		return UINT64_MAX;
+
+	return lzma_lzma_decoder_memusage_nocheck(options);
+}
+
+
+extern lzma_ret
+lzma_lzma_props_decode(void **options, const lzma_allocator *allocator,
+		const uint8_t *props, size_t props_size)
+{
+	if (props_size != 5)
+		return LZMA_OPTIONS_ERROR;
+
+	lzma_options_lzma *opt
+			= lzma_alloc(sizeof(lzma_options_lzma), allocator);
+	if (opt == NULL)
+		return LZMA_MEM_ERROR;
+
+	if (lzma_lzma_lclppb_decode(opt, props[0]))
+		goto error;
+
+	// All dictionary sizes are accepted, including zero. LZ decoder
+	// will automatically use a dictionary at least a few KiB even if
+	// a smaller dictionary is requested.
+	opt->dict_size = read32le(props + 1);
+
+	opt->preset_dict = NULL;
+	opt->preset_dict_size = 0;
+
+	*options = opt;
+
+	return LZMA_OK;
+
+error:
+	lzma_free(opt, allocator);
+	return LZMA_OPTIONS_ERROR;
+}
diff --git a/src/liblzma/lzma/lzma_decoder.h b/src/liblzma/lzma/lzma_decoder.h
new file mode 100644
index 0000000..1427bc2
--- /dev/null
+++ b/src/liblzma/lzma/lzma_decoder.h
@@ -0,0 +1,53 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       lzma_decoder.h
+/// \brief      LZMA decoder API
+///
+//  Authors:    Igor Pavlov
+//              Lasse Collin
+//
+//  This file has been put into the public domain.
+//  You can do whatever you want with this file.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#ifndef LZMA_LZMA_DECODER_H
+#define LZMA_LZMA_DECODER_H
+
+#include "common.h"
+
+
+/// Allocates and initializes LZMA decoder
+extern lzma_ret lzma_lzma_decoder_init(lzma_next_coder *next,
+		const lzma_allocator *allocator,
+		const lzma_filter_info *filters);
+
+extern uint64_t lzma_lzma_decoder_memusage(const void *options);
+
+extern lzma_ret lzma_lzma_props_decode(
+		void **options, const lzma_allocator *allocator,
+		const uint8_t *props, size_t props_size);
+
+
+/// \brief      Decodes the LZMA Properties byte (lc/lp/pb)
+///
+/// \return     true if error occurred, false on success
+///
+extern bool lzma_lzma_lclppb_decode(
+		lzma_options_lzma *options, uint8_t byte);
+
+
+#ifdef LZMA_LZ_DECODER_H
+/// Allocate and setup function pointers only. This is used by LZMA1 and
+/// LZMA2 decoders.
+extern lzma_ret lzma_lzma_decoder_create(
+		lzma_lz_decoder *lz, const lzma_allocator *allocator,
+		const lzma_options_lzma *opt, lzma_lz_options *lz_options);
+
+/// Gets memory usage without validating lc/lp/pb. This is used by LZMA2
+/// decoder, because raw LZMA2 decoding doesn't need lc/lp/pb.
+extern uint64_t lzma_lzma_decoder_memusage_nocheck(const void *options);
+
+#endif
+
+#endif
diff --git a/src/liblzma/lzma/lzma_encoder.c b/src/liblzma/lzma/lzma_encoder.c
new file mode 100644
index 0000000..559c63e
--- /dev/null
+++ b/src/liblzma/lzma/lzma_encoder.c
@@ -0,0 +1,784 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       lzma_encoder.c
+/// \brief      LZMA encoder
+///
+//  Authors:    Igor Pavlov
+//              Lasse Collin
+//
+//  This file has been put into the public domain.
+//  You can do whatever you want with this file.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include "lzma2_encoder.h"
+#include "lzma_encoder_private.h"
+#include "fastpos.h"
+
+
+/////////////
+// Literal //
+/////////////
+
+static inline void
+literal_matched(lzma_range_encoder *rc, probability *subcoder,
+		uint32_t match_byte, uint32_t symbol)
+{
+	uint32_t offset = 0x100;
+	symbol += UINT32_C(1) << 8;
+
+	do {
+		match_byte <<= 1;
+		const uint32_t match_bit = match_byte & offset;
+		const uint32_t subcoder_index
+				= offset + match_bit + (symbol >> 8);
+		const uint32_t bit = (symbol >> 7) & 1;
+		rc_bit(rc, &subcoder[subcoder_index], bit);
+
+		symbol <<= 1;
+		offset &= ~(match_byte ^ symbol);
+
+	} while (symbol < (UINT32_C(1) << 16));
+}
+
+
+static inline void
+literal(lzma_lzma1_encoder *coder, lzma_mf *mf, uint32_t position)
+{
+	// Locate the literal byte to be encoded and the subcoder.
+	const uint8_t cur_byte = mf->buffer[
+			mf->read_pos - mf->read_ahead];
+	probability *subcoder = literal_subcoder(coder->literal,
+			coder->literal_context_bits, coder->literal_pos_mask,
+			position, mf->buffer[mf->read_pos - mf->read_ahead - 1]);
+
+	if (is_literal_state(coder->state)) {
+		// Previous LZMA-symbol was a literal. Encode a normal
+		// literal without a match byte.
+		rc_bittree(&coder->rc, subcoder, 8, cur_byte);
+	} else {
+		// Previous LZMA-symbol was a match. Use the last byte of
+		// the match as a "match byte". That is, compare the bits
+		// of the current literal and the match byte.
+		const uint8_t match_byte = mf->buffer[
+				mf->read_pos - coder->reps[0] - 1
+				- mf->read_ahead];
+		literal_matched(&coder->rc, subcoder, match_byte, cur_byte);
+	}
+
+	update_literal(coder->state);
+}
+
+
+//////////////////
+// Match length //
+//////////////////
+
+static void
+length_update_prices(lzma_length_encoder *lc, const uint32_t pos_state)
+{
+	const uint32_t table_size = lc->table_size;
+	lc->counters[pos_state] = table_size;
+
+	const uint32_t a0 = rc_bit_0_price(lc->choice);
+	const uint32_t a1 = rc_bit_1_price(lc->choice);
+	const uint32_t b0 = a1 + rc_bit_0_price(lc->choice2);
+	const uint32_t b1 = a1 + rc_bit_1_price(lc->choice2);
+	uint32_t *const prices = lc->prices[pos_state];
+
+	uint32_t i;
+	for (i = 0; i < table_size && i < LEN_LOW_SYMBOLS; ++i)
+		prices[i] = a0 + rc_bittree_price(lc->low[pos_state],
+				LEN_LOW_BITS, i);
+
+	for (; i < table_size && i < LEN_LOW_SYMBOLS + LEN_MID_SYMBOLS; ++i)
+		prices[i] = b0 + rc_bittree_price(lc->mid[pos_state],
+				LEN_MID_BITS, i - LEN_LOW_SYMBOLS);
+
+	for (; i < table_size; ++i)
+		prices[i] = b1 + rc_bittree_price(lc->high, LEN_HIGH_BITS,
+				i - LEN_LOW_SYMBOLS - LEN_MID_SYMBOLS);
+
+	return;
+}
+
+
+static inline void
+length(lzma_range_encoder *rc, lzma_length_encoder *lc,
+		const uint32_t pos_state, uint32_t len, const bool fast_mode)
+{
+	assert(len <= MATCH_LEN_MAX);
+	len -= MATCH_LEN_MIN;
+
+	if (len < LEN_LOW_SYMBOLS) {
+		rc_bit(rc, &lc->choice, 0);
+		rc_bittree(rc, lc->low[pos_state], LEN_LOW_BITS, len);
+	} else {
+		rc_bit(rc, &lc->choice, 1);
+		len -= LEN_LOW_SYMBOLS;
+
+		if (len < LEN_MID_SYMBOLS) {
+			rc_bit(rc, &lc->choice2, 0);
+			rc_bittree(rc, lc->mid[pos_state], LEN_MID_BITS, len);
+		} else {
+			rc_bit(rc, &lc->choice2, 1);
+			len -= LEN_MID_SYMBOLS;
+			rc_bittree(rc, lc->high, LEN_HIGH_BITS, len);
+		}
+	}
+
+	// Only getoptimum uses the prices so don't update the table when
+	// in fast mode.
+	if (!fast_mode)
+		if (--lc->counters[pos_state] == 0)
+			length_update_prices(lc, pos_state);
+}
+
+
+///////////
+// Match //
+///////////
+
+static inline void
+match(lzma_lzma1_encoder *coder, const uint32_t pos_state,
+		const uint32_t distance, const uint32_t len)
+{
+	update_match(coder->state);
+
+	length(&coder->rc, &coder->match_len_encoder, pos_state, len,
+			coder->fast_mode);
+
+	const uint32_t dist_slot = get_dist_slot(distance);
+	const uint32_t dist_state = get_dist_state(len);
+	rc_bittree(&coder->rc, coder->dist_slot[dist_state],
+			DIST_SLOT_BITS, dist_slot);
+
+	if (dist_slot >= DIST_MODEL_START) {
+		const uint32_t footer_bits = (dist_slot >> 1) - 1;
+		const uint32_t base = (2 | (dist_slot & 1)) << footer_bits;
+		const uint32_t dist_reduced = distance - base;
+
+		if (dist_slot < DIST_MODEL_END) {
+			// Careful here: base - dist_slot - 1 can be -1, but
+			// rc_bittree_reverse starts at probs[1], not probs[0].
+			rc_bittree_reverse(&coder->rc,
+				coder->dist_special + base - dist_slot - 1,
+				footer_bits, dist_reduced);
+		} else {
+			rc_direct(&coder->rc, dist_reduced >> ALIGN_BITS,
+					footer_bits - ALIGN_BITS);
+			rc_bittree_reverse(
+					&coder->rc, coder->dist_align,
+					ALIGN_BITS, dist_reduced & ALIGN_MASK);
+			++coder->align_price_count;
+		}
+	}
+
+	coder->reps[3] = coder->reps[2];
+	coder->reps[2] = coder->reps[1];
+	coder->reps[1] = coder->reps[0];
+	coder->reps[0] = distance;
+	++coder->match_price_count;
+}
+
+
+////////////////////
+// Repeated match //
+////////////////////
+
+static inline void
+rep_match(lzma_lzma1_encoder *coder, const uint32_t pos_state,
+		const uint32_t rep, const uint32_t len)
+{
+	if (rep == 0) {
+		rc_bit(&coder->rc, &coder->is_rep0[coder->state], 0);
+		rc_bit(&coder->rc,
+				&coder->is_rep0_long[coder->state][pos_state],
+				len != 1);
+	} else {
+		const uint32_t distance = coder->reps[rep];
+		rc_bit(&coder->rc, &coder->is_rep0[coder->state], 1);
+
+		if (rep == 1) {
+			rc_bit(&coder->rc, &coder->is_rep1[coder->state], 0);
+		} else {
+			rc_bit(&coder->rc, &coder->is_rep1[coder->state], 1);
+			rc_bit(&coder->rc, &coder->is_rep2[coder->state],
+					rep - 2);
+
+			if (rep == 3)
+				coder->reps[3] = coder->reps[2];
+
+			coder->reps[2] = coder->reps[1];
+		}
+
+		coder->reps[1] = coder->reps[0];
+		coder->reps[0] = distance;
+	}
+
+	if (len == 1) {
+		update_short_rep(coder->state);
+	} else {
+		length(&coder->rc, &coder->rep_len_encoder, pos_state, len,
+				coder->fast_mode);
+		update_long_rep(coder->state);
+	}
+}
+
+
+//////////
+// Main //
+//////////
+
+static void
+encode_symbol(lzma_lzma1_encoder *coder, lzma_mf *mf,
+		uint32_t back, uint32_t len, uint32_t position)
+{
+	const uint32_t pos_state = position & coder->pos_mask;
+
+	if (back == UINT32_MAX) {
+		// Literal i.e. eight-bit byte
+		assert(len == 1);
+		rc_bit(&coder->rc,
+				&coder->is_match[coder->state][pos_state], 0);
+		literal(coder, mf, position);
+	} else {
+		// Some type of match
+		rc_bit(&coder->rc,
+			&coder->is_match[coder->state][pos_state], 1);
+
+		if (back < REPS) {
+			// It's a repeated match i.e. the same distance
+			// has been used earlier.
+			rc_bit(&coder->rc, &coder->is_rep[coder->state], 1);
+			rep_match(coder, pos_state, back, len);
+		} else {
+			// Normal match
+			rc_bit(&coder->rc, &coder->is_rep[coder->state], 0);
+			match(coder, pos_state, back - REPS, len);
+		}
+	}
+
+	assert(mf->read_ahead >= len);
+	mf->read_ahead -= len;
+}
+
+
+static bool
+encode_init(lzma_lzma1_encoder *coder, lzma_mf *mf)
+{
+	assert(mf_position(mf) == 0);
+	assert(coder->uncomp_size == 0);
+
+	if (mf->read_pos == mf->read_limit) {
+		if (mf->action == LZMA_RUN)
+			return false; // We cannot do anything.
+
+		// We are finishing (we cannot get here when flushing).
+		assert(mf->write_pos == mf->read_pos);
+		assert(mf->action == LZMA_FINISH);
+	} else {
+		// Do the actual initialization. The first LZMA symbol must
+		// always be a literal.
+		mf_skip(mf, 1);
+		mf->read_ahead = 0;
+		rc_bit(&coder->rc, &coder->is_match[0][0], 0);
+		rc_bittree(&coder->rc, coder->literal[0], 8, mf->buffer[0]);
+		++coder->uncomp_size;
+	}
+
+	// Initialization is done (except if empty file).
+	coder->is_initialized = true;
+
+	return true;
+}
+
+
+static void
+encode_eopm(lzma_lzma1_encoder *coder, uint32_t position)
+{
+	const uint32_t pos_state = position & coder->pos_mask;
+	rc_bit(&coder->rc, &coder->is_match[coder->state][pos_state], 1);
+	rc_bit(&coder->rc, &coder->is_rep[coder->state], 0);
+	match(coder, pos_state, UINT32_MAX, MATCH_LEN_MIN);
+}
+
+
+/// Number of bytes that a single encoding loop in lzma_lzma_encode() can
+/// consume from the dictionary. This limit comes from lzma_lzma_optimum()
+/// and may need to be updated if that function is significantly modified.
+#define LOOP_INPUT_MAX (OPTS + 1)
+
+
+extern lzma_ret
+lzma_lzma_encode(lzma_lzma1_encoder *restrict coder, lzma_mf *restrict mf,
+		uint8_t *restrict out, size_t *restrict out_pos,
+		size_t out_size, uint32_t limit)
+{
+	// Initialize the stream if no data has been encoded yet.
+	if (!coder->is_initialized && !encode_init(coder, mf))
+		return LZMA_OK;
+
+	// Encode pending output bytes from the range encoder.
+	// At the start of the stream, encode_init() encodes one literal.
+	// Later there can be pending output only with LZMA1 because LZMA2
+	// ensures that there is always enough output space. Thus when using
+	// LZMA2, rc_encode() calls in this function will always return false.
+	if (rc_encode(&coder->rc, out, out_pos, out_size)) {
+		// We don't get here with LZMA2.
+		assert(limit == UINT32_MAX);
+		return LZMA_OK;
+	}
+
+	// If the range encoder was flushed in an earlier call to this
+	// function but there wasn't enough output buffer space, those
+	// bytes would have now been encoded by the above rc_encode() call
+	// and the stream has now been finished. This can only happen with
+	// LZMA1 as LZMA2 always provides enough output buffer space.
+	if (coder->is_flushed) {
+		assert(limit == UINT32_MAX);
+		return LZMA_STREAM_END;
+	}
+
+	while (true) {
+		// With LZMA2 we need to take care that compressed size of
+		// a chunk doesn't get too big.
+		// FIXME? Check if this could be improved.
+		if (limit != UINT32_MAX
+				&& (mf->read_pos - mf->read_ahead >= limit
+					|| *out_pos + rc_pending(&coder->rc)
+						>= LZMA2_CHUNK_MAX
+							- LOOP_INPUT_MAX))
+			break;
+
+		// Check that there is some input to process.
+		if (mf->read_pos >= mf->read_limit) {
+			if (mf->action == LZMA_RUN)
+				return LZMA_OK;
+
+			if (mf->read_ahead == 0)
+				break;
+		}
+
+		// Get optimal match (repeat position and length).
+		// Value ranges for pos:
+		//   - [0, REPS): repeated match
+		//   - [REPS, UINT32_MAX):
+		//     match at (pos - REPS)
+		//   - UINT32_MAX: not a match but a literal
+		// Value ranges for len:
+		//   - [MATCH_LEN_MIN, MATCH_LEN_MAX]
+		uint32_t len;
+		uint32_t back;
+
+		if (coder->fast_mode)
+			lzma_lzma_optimum_fast(coder, mf, &back, &len);
+		else
+			lzma_lzma_optimum_normal(coder, mf, &back, &len,
+					(uint32_t)(coder->uncomp_size));
+
+		encode_symbol(coder, mf, back, len,
+				(uint32_t)(coder->uncomp_size));
+
+		// If output size limiting is active (out_limit != 0), check
+		// if encoding this LZMA symbol would make the output size
+		// exceed the specified limit.
+		if (coder->out_limit != 0 && rc_encode_dummy(
+				&coder->rc, coder->out_limit)) {
+			// The most recent LZMA symbol would make the output
+			// too big. Throw it away.
+			rc_forget(&coder->rc);
+
+			// FIXME: Tell the LZ layer to not read more input as
+			// it would be waste of time. This doesn't matter if
+			// output-size-limited encoding is done with a single
+			// call though.
+
+			break;
+		}
+
+		// This symbol will be encoded so update the uncompressed size.
+		coder->uncomp_size += len;
+
+		// Encode the LZMA symbol.
+		if (rc_encode(&coder->rc, out, out_pos, out_size)) {
+			// Once again, this can only happen with LZMA1.
+			assert(limit == UINT32_MAX);
+			return LZMA_OK;
+		}
+	}
+
+	// Make the uncompressed size available to the application.
+	if (coder->uncomp_size_ptr != NULL)
+		*coder->uncomp_size_ptr = coder->uncomp_size;
+
+	// LZMA2 doesn't use EOPM at LZMA level.
+	//
+	// Plain LZMA streams without EOPM aren't supported except when
+	// output size limiting is enabled.
+	if (coder->use_eopm)
+		encode_eopm(coder, (uint32_t)(coder->uncomp_size));
+
+	// Flush the remaining bytes from the range encoder.
+	rc_flush(&coder->rc);
+
+	// Copy the remaining bytes to the output buffer. If there
+	// isn't enough output space, we will copy out the remaining
+	// bytes on the next call to this function.
+	if (rc_encode(&coder->rc, out, out_pos, out_size)) {
+		// This cannot happen with LZMA2.
+		assert(limit == UINT32_MAX);
+
+		coder->is_flushed = true;
+		return LZMA_OK;
+	}
+
+	return LZMA_STREAM_END;
+}
+
+
+static lzma_ret
+lzma_encode(void *coder, lzma_mf *restrict mf,
+		uint8_t *restrict out, size_t *restrict out_pos,
+		size_t out_size)
+{
+	// Plain LZMA has no support for sync-flushing.
+	if (unlikely(mf->action == LZMA_SYNC_FLUSH))
+		return LZMA_OPTIONS_ERROR;
+
+	return lzma_lzma_encode(coder, mf, out, out_pos, out_size, UINT32_MAX);
+}
+
+
+static lzma_ret
+lzma_lzma_set_out_limit(
+		void *coder_ptr, uint64_t *uncomp_size, uint64_t out_limit)
+{
+	// Minimum output size is 5 bytes but that cannot hold any output
+	// so we use 6 bytes.
+	if (out_limit < 6)
+		return LZMA_BUF_ERROR;
+
+	lzma_lzma1_encoder *coder = coder_ptr;
+	coder->out_limit = out_limit;
+	coder->uncomp_size_ptr = uncomp_size;
+	coder->use_eopm = false;
+	return LZMA_OK;
+}
+
+
+////////////////////
+// Initialization //
+////////////////////
+
+static bool
+is_options_valid(const lzma_options_lzma *options)
+{
+	// Validate some of the options. LZ encoder validates nice_len too
+	// but we need a valid value here earlier.
+	return is_lclppb_valid(options)
+			&& options->nice_len >= MATCH_LEN_MIN
+			&& options->nice_len <= MATCH_LEN_MAX
+			&& (options->mode == LZMA_MODE_FAST
+				|| options->mode == LZMA_MODE_NORMAL);
+}
+
+
+static void
+set_lz_options(lzma_lz_options *lz_options, const lzma_options_lzma *options)
+{
+	// LZ encoder initialization does the validation for these so we
+	// don't need to validate here.
+	lz_options->before_size = OPTS;
+	lz_options->dict_size = options->dict_size;
+	lz_options->after_size = LOOP_INPUT_MAX;
+	lz_options->match_len_max = MATCH_LEN_MAX;
+	lz_options->nice_len = my_max(mf_get_hash_bytes(options->mf),
+				options->nice_len);
+	lz_options->match_finder = options->mf;
+	lz_options->depth = options->depth;
+	lz_options->preset_dict = options->preset_dict;
+	lz_options->preset_dict_size = options->preset_dict_size;
+	return;
+}
+
+
+static void
+length_encoder_reset(lzma_length_encoder *lencoder,
+		const uint32_t num_pos_states, const bool fast_mode)
+{
+	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);
+
+	if (!fast_mode)
+		for (uint32_t pos_state = 0; pos_state < num_pos_states;
+				++pos_state)
+			length_update_prices(lencoder, pos_state);
+
+	return;
+}
+
+
+extern lzma_ret
+lzma_lzma_encoder_reset(lzma_lzma1_encoder *coder,
+		const lzma_options_lzma *options)
+{
+	if (!is_options_valid(options))
+		return LZMA_OPTIONS_ERROR;
+
+	coder->pos_mask = (1U << options->pb) - 1;
+	coder->literal_context_bits = options->lc;
+	coder->literal_pos_mask = (1U << options->lp) - 1;
+
+	// Range coder
+	rc_reset(&coder->rc);
+
+	// State
+	coder->state = STATE_LIT_LIT;
+	for (size_t i = 0; i < REPS; ++i)
+		coder->reps[i] = 0;
+
+	literal_init(coder->literal, options->lc, options->lp);
+
+	// Bit encoders
+	for (size_t i = 0; i < STATES; ++i) {
+		for (size_t j = 0; j <= coder->pos_mask; ++j) {
+			bit_reset(coder->is_match[i][j]);
+			bit_reset(coder->is_rep0_long[i][j]);
+		}
+
+		bit_reset(coder->is_rep[i]);
+		bit_reset(coder->is_rep0[i]);
+		bit_reset(coder->is_rep1[i]);
+		bit_reset(coder->is_rep2[i]);
+	}
+
+	for (size_t i = 0; i < FULL_DISTANCES - DIST_MODEL_END; ++i)
+		bit_reset(coder->dist_special[i]);
+
+	// Bit tree encoders
+	for (size_t i = 0; i < DIST_STATES; ++i)
+		bittree_reset(coder->dist_slot[i], DIST_SLOT_BITS);
+
+	bittree_reset(coder->dist_align, ALIGN_BITS);
+
+	// Length encoders
+	length_encoder_reset(&coder->match_len_encoder,
+			1U << options->pb, coder->fast_mode);
+
+	length_encoder_reset(&coder->rep_len_encoder,
+			1U << options->pb, coder->fast_mode);
+
+	// Price counts are incremented every time appropriate probabilities
+	// are changed. price counts are set to zero when the price tables
+	// are updated, which is done when the appropriate price counts have
+	// big enough value, and lzma_mf.read_ahead == 0 which happens at
+	// least every OPTS (a few thousand) possible price count increments.
+	//
+	// By resetting price counts to UINT32_MAX / 2, we make sure that the
+	// price tables will be initialized before they will be used (since
+	// the value is definitely big enough), and that it is OK to increment
+	// price counts without risk of integer overflow (since UINT32_MAX / 2
+	// is small enough). The current code doesn't increment price counts
+	// before initializing price tables, but it maybe done in future if
+	// we add support for saving the state between LZMA2 chunks.
+	coder->match_price_count = UINT32_MAX / 2;
+	coder->align_price_count = UINT32_MAX / 2;
+
+	coder->opts_end_index = 0;
+	coder->opts_current_index = 0;
+
+	return LZMA_OK;
+}
+
+
+extern lzma_ret
+lzma_lzma_encoder_create(void **coder_ptr, const lzma_allocator *allocator,
+		lzma_vli id, const lzma_options_lzma *options,
+		lzma_lz_options *lz_options)
+{
+	assert(id == LZMA_FILTER_LZMA1 || id == LZMA_FILTER_LZMA1EXT
+			|| id == LZMA_FILTER_LZMA2);
+
+	// Allocate lzma_lzma1_encoder if it wasn't already allocated.
+	if (*coder_ptr == NULL) {
+		*coder_ptr = lzma_alloc(sizeof(lzma_lzma1_encoder), allocator);
+		if (*coder_ptr == NULL)
+			return LZMA_MEM_ERROR;
+	}
+
+	lzma_lzma1_encoder *coder = *coder_ptr;
+
+	// Set compression mode. Note that we haven't validated the options
+	// yet. Invalid options will get rejected by lzma_lzma_encoder_reset()
+	// call at the end of this function.
+	switch (options->mode) {
+		case LZMA_MODE_FAST:
+			coder->fast_mode = true;
+			break;
+
+		case LZMA_MODE_NORMAL: {
+			coder->fast_mode = false;
+
+			// Set dist_table_size.
+			// Round the dictionary size up to next 2^n.
+			//
+			// Currently the maximum encoder dictionary size
+			// is 1.5 GiB due to lz_encoder.c and here we need
+			// to be below 2 GiB to make the rounded up value
+			// fit in an uint32_t and avoid an infinite while-loop
+			// (and undefined behavior due to a too large shift).
+			// So do the same check as in LZ encoder,
+			// limiting to 1.5 GiB.
+			if (options->dict_size > (UINT32_C(1) << 30)
+					+ (UINT32_C(1) << 29))
+				return LZMA_OPTIONS_ERROR;
+
+			uint32_t log_size = 0;
+			while ((UINT32_C(1) << log_size) < options->dict_size)
+				++log_size;
+
+			coder->dist_table_size = log_size * 2;
+
+			// Length encoders' price table size
+			const uint32_t nice_len = my_max(
+					mf_get_hash_bytes(options->mf),
+					options->nice_len);
+
+			coder->match_len_encoder.table_size
+					= nice_len + 1 - MATCH_LEN_MIN;
+			coder->rep_len_encoder.table_size
+					= nice_len + 1 - MATCH_LEN_MIN;
+			break;
+		}
+
+		default:
+			return LZMA_OPTIONS_ERROR;
+	}
+
+	// We don't need to write the first byte as literal if there is
+	// a non-empty preset dictionary. encode_init() wouldn't even work
+	// if there is a non-empty preset dictionary, because encode_init()
+	// assumes that position is zero and previous byte is also zero.
+	coder->is_initialized = options->preset_dict != NULL
+			&& options->preset_dict_size > 0;
+	coder->is_flushed = false;
+	coder->uncomp_size = 0;
+	coder->uncomp_size_ptr = NULL;
+
+	// Output size limiting is disabled by default.
+	coder->out_limit = 0;
+
+	// Determine if end marker is wanted:
+	//   - It is never used with LZMA2.
+	//   - It is always used with LZMA_FILTER_LZMA1 (unless
+	//     lzma_lzma_set_out_limit() is called later).
+	//   - LZMA_FILTER_LZMA1EXT has a flag for it in the options.
+	coder->use_eopm = (id == LZMA_FILTER_LZMA1);
+	if (id == LZMA_FILTER_LZMA1EXT) {
+		// Check if unsupported flags are present.
+		if (options->ext_flags & ~LZMA_LZMA1EXT_ALLOW_EOPM)
+			return LZMA_OPTIONS_ERROR;
+
+		coder->use_eopm = (options->ext_flags
+				& LZMA_LZMA1EXT_ALLOW_EOPM) != 0;
+
+		// TODO? As long as there are no filters that change the size
+		// of the data, it is enough to look at lzma_stream.total_in
+		// after encoding has been finished to know the uncompressed
+		// size of the LZMA1 stream. But in the future there could be
+		// filters that change the size of the data and then total_in
+		// doesn't work as the LZMA1 stream size might be different
+		// due to another filter in the chain. The problem is simple
+		// to solve: Add another flag to ext_flags and then set
+		// coder->uncomp_size_ptr to the address stored in
+		// lzma_options_lzma.reserved_ptr2 (or _ptr1).
+	}
+
+	set_lz_options(lz_options, options);
+
+	return lzma_lzma_encoder_reset(coder, options);
+}
+
+
+static lzma_ret
+lzma_encoder_init(lzma_lz_encoder *lz, const lzma_allocator *allocator,
+		lzma_vli id, const void *options, lzma_lz_options *lz_options)
+{
+	lz->code = &lzma_encode;
+	lz->set_out_limit = &lzma_lzma_set_out_limit;
+	return lzma_lzma_encoder_create(
+			&lz->coder, allocator, id, options, lz_options);
+}
+
+
+extern lzma_ret
+lzma_lzma_encoder_init(lzma_next_coder *next, const lzma_allocator *allocator,
+		const lzma_filter_info *filters)
+{
+	return lzma_lz_encoder_init(
+			next, allocator, filters, &lzma_encoder_init);
+}
+
+
+extern uint64_t
+lzma_lzma_encoder_memusage(const void *options)
+{
+	if (!is_options_valid(options))
+		return UINT64_MAX;
+
+	lzma_lz_options lz_options;
+	set_lz_options(&lz_options, options);
+
+	const uint64_t lz_memusage = lzma_lz_encoder_memusage(&lz_options);
+	if (lz_memusage == UINT64_MAX)
+		return UINT64_MAX;
+
+	return (uint64_t)(sizeof(lzma_lzma1_encoder)) + lz_memusage;
+}
+
+
+extern bool
+lzma_lzma_lclppb_encode(const lzma_options_lzma *options, uint8_t *byte)
+{
+	if (!is_lclppb_valid(options))
+		return true;
+
+	*byte = (options->pb * 5 + options->lp) * 9 + options->lc;
+	assert(*byte <= (4 * 5 + 4) * 9 + 8);
+
+	return false;
+}
+
+
+#ifdef HAVE_ENCODER_LZMA1
+extern lzma_ret
+lzma_lzma_props_encode(const void *options, uint8_t *out)
+{
+	if (options == NULL)
+		return LZMA_PROG_ERROR;
+
+	const lzma_options_lzma *const opt = options;
+
+	if (lzma_lzma_lclppb_encode(opt, out))
+		return LZMA_PROG_ERROR;
+
+	write32le(out + 1, opt->dict_size);
+
+	return LZMA_OK;
+}
+#endif
+
+
+extern LZMA_API(lzma_bool)
+lzma_mode_is_supported(lzma_mode mode)
+{
+	return mode == LZMA_MODE_FAST || mode == LZMA_MODE_NORMAL;
+}
diff --git a/src/liblzma/lzma/lzma_encoder.h b/src/liblzma/lzma/lzma_encoder.h
new file mode 100644
index 0000000..84d8c91
--- /dev/null
+++ b/src/liblzma/lzma/lzma_encoder.h
@@ -0,0 +1,59 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       lzma_encoder.h
+/// \brief      LZMA encoder API
+///
+//  Authors:    Igor Pavlov
+//              Lasse Collin
+//
+//  This file has been put into the public domain.
+//  You can do whatever you want with this file.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#ifndef LZMA_LZMA_ENCODER_H
+#define LZMA_LZMA_ENCODER_H
+
+#include "common.h"
+
+
+typedef struct lzma_lzma1_encoder_s lzma_lzma1_encoder;
+
+
+extern lzma_ret lzma_lzma_encoder_init(lzma_next_coder *next,
+		const lzma_allocator *allocator,
+		const lzma_filter_info *filters);
+
+
+extern uint64_t lzma_lzma_encoder_memusage(const void *options);
+
+extern lzma_ret lzma_lzma_props_encode(const void *options, uint8_t *out);
+
+
+/// Encodes lc/lp/pb into one byte. Returns false on success and true on error.
+extern bool lzma_lzma_lclppb_encode(
+		const lzma_options_lzma *options, uint8_t *byte);
+
+
+#ifdef LZMA_LZ_ENCODER_H
+
+/// Initializes raw LZMA encoder; this is used by LZMA2.
+extern lzma_ret lzma_lzma_encoder_create(
+		void **coder_ptr, const lzma_allocator *allocator,
+		lzma_vli id, const lzma_options_lzma *options,
+		lzma_lz_options *lz_options);
+
+
+/// Resets an already initialized LZMA encoder; this is used by LZMA2.
+extern lzma_ret lzma_lzma_encoder_reset(
+		lzma_lzma1_encoder *coder, const lzma_options_lzma *options);
+
+
+extern lzma_ret lzma_lzma_encode(lzma_lzma1_encoder *restrict coder,
+		lzma_mf *restrict mf, uint8_t *restrict out,
+		size_t *restrict out_pos, size_t out_size,
+		uint32_t read_limit);
+
+#endif
+
+#endif
diff --git a/src/liblzma/lzma/lzma_encoder_optimum_fast.c b/src/liblzma/lzma/lzma_encoder_optimum_fast.c
new file mode 100644
index 0000000..6c53d2b
--- /dev/null
+++ b/src/liblzma/lzma/lzma_encoder_optimum_fast.c
@@ -0,0 +1,170 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       lzma_encoder_optimum_fast.c
+//
+//  Author:     Igor Pavlov
+//
+//  This file has been put into the public domain.
+//  You can do whatever you want with this file.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include "lzma_encoder_private.h"
+#include "memcmplen.h"
+
+
+#define change_pair(small_dist, big_dist) \
+	(((big_dist) >> 7) > (small_dist))
+
+
+extern void
+lzma_lzma_optimum_fast(lzma_lzma1_encoder *restrict coder,
+		lzma_mf *restrict mf,
+		uint32_t *restrict back_res, uint32_t *restrict len_res)
+{
+	const uint32_t nice_len = mf->nice_len;
+
+	uint32_t len_main;
+	uint32_t matches_count;
+	if (mf->read_ahead == 0) {
+		len_main = mf_find(mf, &matches_count, coder->matches);
+	} else {
+		assert(mf->read_ahead == 1);
+		len_main = coder->longest_match_length;
+		matches_count = coder->matches_count;
+	}
+
+	const uint8_t *buf = mf_ptr(mf) - 1;
+	const uint32_t buf_avail = my_min(mf_avail(mf) + 1, MATCH_LEN_MAX);
+
+	if (buf_avail < 2) {
+		// There's not enough input left to encode a match.
+		*back_res = UINT32_MAX;
+		*len_res = 1;
+		return;
+	}
+
+	// Look for repeated matches; scan the previous four match distances
+	uint32_t rep_len = 0;
+	uint32_t rep_index = 0;
+
+	for (uint32_t i = 0; i < REPS; ++i) {
+		// Pointer to the beginning of the match candidate
+		const uint8_t *const buf_back = buf - coder->reps[i] - 1;
+
+		// If the first two bytes (2 == MATCH_LEN_MIN) do not match,
+		// this rep is not useful.
+		if (not_equal_16(buf, buf_back))
+			continue;
+
+		// The first two bytes matched.
+		// Calculate the length of the match.
+		const uint32_t len = lzma_memcmplen(
+				buf, buf_back, 2, buf_avail);
+
+		// If we have found a repeated match that is at least
+		// nice_len long, return it immediately.
+		if (len >= nice_len) {
+			*back_res = i;
+			*len_res = len;
+			mf_skip(mf, len - 1);
+			return;
+		}
+
+		if (len > rep_len) {
+			rep_index = i;
+			rep_len = len;
+		}
+	}
+
+	// We didn't find a long enough repeated match. Encode it as a normal
+	// match if the match length is at least nice_len.
+	if (len_main >= nice_len) {
+		*back_res = coder->matches[matches_count - 1].dist + REPS;
+		*len_res = len_main;
+		mf_skip(mf, len_main - 1);
+		return;
+	}
+
+	uint32_t back_main = 0;
+	if (len_main >= 2) {
+		back_main = coder->matches[matches_count - 1].dist;
+
+		while (matches_count > 1 && len_main ==
+				coder->matches[matches_count - 2].len + 1) {
+			if (!change_pair(coder->matches[
+						matches_count - 2].dist,
+					back_main))
+				break;
+
+			--matches_count;
+			len_main = coder->matches[matches_count - 1].len;
+			back_main = coder->matches[matches_count - 1].dist;
+		}
+
+		if (len_main == 2 && back_main >= 0x80)
+			len_main = 1;
+	}
+
+	if (rep_len >= 2) {
+		if (rep_len + 1 >= len_main
+				|| (rep_len + 2 >= len_main
+					&& back_main > (UINT32_C(1) << 9))
+				|| (rep_len + 3 >= len_main
+					&& back_main > (UINT32_C(1) << 15))) {
+			*back_res = rep_index;
+			*len_res = rep_len;
+			mf_skip(mf, rep_len - 1);
+			return;
+		}
+	}
+
+	if (len_main < 2 || buf_avail <= 2) {
+		*back_res = UINT32_MAX;
+		*len_res = 1;
+		return;
+	}
+
+	// Get the matches for the next byte. If we find a better match,
+	// the current byte is encoded as a literal.
+	coder->longest_match_length = mf_find(mf,
+			&coder->matches_count, coder->matches);
+
+	if (coder->longest_match_length >= 2) {
+		const uint32_t new_dist = coder->matches[
+				coder->matches_count - 1].dist;
+
+		if ((coder->longest_match_length >= len_main
+					&& new_dist < back_main)
+				|| (coder->longest_match_length == len_main + 1
+					&& !change_pair(back_main, new_dist))
+				|| (coder->longest_match_length > len_main + 1)
+				|| (coder->longest_match_length + 1 >= len_main
+					&& len_main >= 3
+					&& change_pair(new_dist, back_main))) {
+			*back_res = UINT32_MAX;
+			*len_res = 1;
+			return;
+		}
+	}
+
+	// In contrast to LZMA SDK, dictionary could not have been moved
+	// between mf_find() calls, thus it is safe to just increment
+	// the old buf pointer instead of recalculating it with mf_ptr().
+	++buf;
+
+	const uint32_t limit = my_max(2, len_main - 1);
+
+	for (uint32_t i = 0; i < REPS; ++i) {
+		if (memcmp(buf, buf - coder->reps[i] - 1, limit) == 0) {
+			*back_res = UINT32_MAX;
+			*len_res = 1;
+			return;
+		}
+	}
+
+	*back_res = back_main + REPS;
+	*len_res = len_main;
+	mf_skip(mf, len_main - 2);
+	return;
+}
diff --git a/src/liblzma/lzma/lzma_encoder_optimum_normal.c b/src/liblzma/lzma/lzma_encoder_optimum_normal.c
new file mode 100644
index 0000000..101c8d4
--- /dev/null
+++ b/src/liblzma/lzma/lzma_encoder_optimum_normal.c
@@ -0,0 +1,859 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       lzma_encoder_optimum_normal.c
+//
+//  Author:     Igor Pavlov
+//
+//  This file has been put into the public domain.
+//  You can do whatever you want with this file.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include "lzma_encoder_private.h"
+#include "fastpos.h"
+#include "memcmplen.h"
+
+
+////////////
+// Prices //
+////////////
+
+static uint32_t
+get_literal_price(const lzma_lzma1_encoder *const coder, const uint32_t pos,
+		const uint32_t prev_byte, const bool match_mode,
+		uint32_t match_byte, uint32_t symbol)
+{
+	const probability *const subcoder = literal_subcoder(coder->literal,
+			coder->literal_context_bits, coder->literal_pos_mask,
+			pos, prev_byte);
+
+	uint32_t price = 0;
+
+	if (!match_mode) {
+		price = rc_bittree_price(subcoder, 8, symbol);
+	} else {
+		uint32_t offset = 0x100;
+		symbol += UINT32_C(1) << 8;
+
+		do {
+			match_byte <<= 1;
+
+			const uint32_t match_bit = match_byte & offset;
+			const uint32_t subcoder_index
+					= offset + match_bit + (symbol >> 8);
+			const uint32_t bit = (symbol >> 7) & 1;
+			price += rc_bit_price(subcoder[subcoder_index], bit);
+
+			symbol <<= 1;
+			offset &= ~(match_byte ^ symbol);
+
+		} while (symbol < (UINT32_C(1) << 16));
+	}
+
+	return price;
+}
+
+
+static inline uint32_t
+get_len_price(const lzma_length_encoder *const lencoder,
+		const uint32_t len, const uint32_t pos_state)
+{
+	// NOTE: Unlike the other price tables, length prices are updated
+	// in lzma_encoder.c
+	return lencoder->prices[pos_state][len - MATCH_LEN_MIN];
+}
+
+
+static inline uint32_t
+get_short_rep_price(const lzma_lzma1_encoder *const coder,
+		const lzma_lzma_state state, const uint32_t pos_state)
+{
+	return rc_bit_0_price(coder->is_rep0[state])
+		+ rc_bit_0_price(coder->is_rep0_long[state][pos_state]);
+}
+
+
+static inline uint32_t
+get_pure_rep_price(const lzma_lzma1_encoder *const coder, const uint32_t rep_index,
+		const lzma_lzma_state state, uint32_t pos_state)
+{
+	uint32_t price;
+
+	if (rep_index == 0) {
+		price = rc_bit_0_price(coder->is_rep0[state]);
+		price += rc_bit_1_price(coder->is_rep0_long[state][pos_state]);
+	} else {
+		price = rc_bit_1_price(coder->is_rep0[state]);
+
+		if (rep_index == 1) {
+			price += rc_bit_0_price(coder->is_rep1[state]);
+		} else {
+			price += rc_bit_1_price(coder->is_rep1[state]);
+			price += rc_bit_price(coder->is_rep2[state],
+					rep_index - 2);
+		}
+	}
+
+	return price;
+}
+
+
+static inline uint32_t
+get_rep_price(const lzma_lzma1_encoder *const coder, const uint32_t rep_index,
+		const uint32_t len, const lzma_lzma_state state,
+		const uint32_t pos_state)
+{
+	return get_len_price(&coder->rep_len_encoder, len, pos_state)
+		+ get_pure_rep_price(coder, rep_index, state, pos_state);
+}
+
+
+static inline uint32_t
+get_dist_len_price(const lzma_lzma1_encoder *const coder, const uint32_t dist,
+		const uint32_t len, const uint32_t pos_state)
+{
+	const uint32_t dist_state = get_dist_state(len);
+	uint32_t price;
+
+	if (dist < FULL_DISTANCES) {
+		price = coder->dist_prices[dist_state][dist];
+	} else {
+		const uint32_t dist_slot = get_dist_slot_2(dist);
+		price = coder->dist_slot_prices[dist_state][dist_slot]
+				+ coder->align_prices[dist & ALIGN_MASK];
+	}
+
+	price += get_len_price(&coder->match_len_encoder, len, pos_state);
+
+	return price;
+}
+
+
+static void
+fill_dist_prices(lzma_lzma1_encoder *coder)
+{
+	for (uint32_t dist_state = 0; dist_state < DIST_STATES; ++dist_state) {
+
+		uint32_t *const dist_slot_prices
+				= coder->dist_slot_prices[dist_state];
+
+		// Price to encode the dist_slot.
+		for (uint32_t dist_slot = 0;
+				dist_slot < coder->dist_table_size; ++dist_slot)
+			dist_slot_prices[dist_slot] = rc_bittree_price(
+					coder->dist_slot[dist_state],
+					DIST_SLOT_BITS, dist_slot);
+
+		// For matches with distance >= FULL_DISTANCES, add the price
+		// of the direct bits part of the match distance. (Align bits
+		// are handled by fill_align_prices()).
+		for (uint32_t dist_slot = DIST_MODEL_END;
+				dist_slot < coder->dist_table_size;
+				++dist_slot)
+			dist_slot_prices[dist_slot] += rc_direct_price(
+					((dist_slot >> 1) - 1) - ALIGN_BITS);
+
+		// Distances in the range [0, 3] are fully encoded with
+		// dist_slot, so they are used for coder->dist_prices
+		// as is.
+		for (uint32_t i = 0; i < DIST_MODEL_START; ++i)
+			coder->dist_prices[dist_state][i]
+					= dist_slot_prices[i];
+	}
+
+	// Distances in the range [4, 127] depend on dist_slot and
+	// dist_special. We do this in a loop separate from the above
+	// loop to avoid redundant calls to get_dist_slot().
+	for (uint32_t i = DIST_MODEL_START; i < FULL_DISTANCES; ++i) {
+		const uint32_t dist_slot = get_dist_slot(i);
+		const uint32_t footer_bits = ((dist_slot >> 1) - 1);
+		const uint32_t base = (2 | (dist_slot & 1)) << footer_bits;
+		const uint32_t price = rc_bittree_reverse_price(
+				coder->dist_special + base - dist_slot - 1,
+				footer_bits, i - base);
+
+		for (uint32_t dist_state = 0; dist_state < DIST_STATES;
+				++dist_state)
+			coder->dist_prices[dist_state][i]
+					= price + coder->dist_slot_prices[
+						dist_state][dist_slot];
+	}
+
+	coder->match_price_count = 0;
+	return;
+}
+
+
+static void
+fill_align_prices(lzma_lzma1_encoder *coder)
+{
+	for (uint32_t i = 0; i < ALIGN_SIZE; ++i)
+		coder->align_prices[i] = rc_bittree_reverse_price(
+				coder->dist_align, ALIGN_BITS, i);
+
+	coder->align_price_count = 0;
+	return;
+}
+
+
+/////////////
+// Optimal //
+/////////////
+
+static inline void
+make_literal(lzma_optimal *optimal)
+{
+	optimal->back_prev = UINT32_MAX;
+	optimal->prev_1_is_literal = false;
+}
+
+
+static inline void
+make_short_rep(lzma_optimal *optimal)
+{
+	optimal->back_prev = 0;
+	optimal->prev_1_is_literal = false;
+}
+
+
+#define is_short_rep(optimal) \
+	((optimal).back_prev == 0)
+
+
+static void
+backward(lzma_lzma1_encoder *restrict coder, uint32_t *restrict len_res,
+		uint32_t *restrict back_res, uint32_t cur)
+{
+	coder->opts_end_index = cur;
+
+	uint32_t pos_mem = coder->opts[cur].pos_prev;
+	uint32_t back_mem = coder->opts[cur].back_prev;
+
+	do {
+		if (coder->opts[cur].prev_1_is_literal) {
+			make_literal(&coder->opts[pos_mem]);
+			coder->opts[pos_mem].pos_prev = pos_mem - 1;
+
+			if (coder->opts[cur].prev_2) {
+				coder->opts[pos_mem - 1].prev_1_is_literal
+						= false;
+				coder->opts[pos_mem - 1].pos_prev
+						= coder->opts[cur].pos_prev_2;
+				coder->opts[pos_mem - 1].back_prev
+						= coder->opts[cur].back_prev_2;
+			}
+		}
+
+		const uint32_t pos_prev = pos_mem;
+		const uint32_t back_cur = back_mem;
+
+		back_mem = coder->opts[pos_prev].back_prev;
+		pos_mem = coder->opts[pos_prev].pos_prev;
+
+		coder->opts[pos_prev].back_prev = back_cur;
+		coder->opts[pos_prev].pos_prev = cur;
+		cur = pos_prev;
+
+	} while (cur != 0);
+
+	coder->opts_current_index = coder->opts[0].pos_prev;
+	*len_res = coder->opts[0].pos_prev;
+	*back_res = coder->opts[0].back_prev;
+
+	return;
+}
+
+
+//////////
+// Main //
+//////////
+
+static inline uint32_t
+helper1(lzma_lzma1_encoder *restrict coder, lzma_mf *restrict mf,
+		uint32_t *restrict back_res, uint32_t *restrict len_res,
+		uint32_t position)
+{
+	const uint32_t nice_len = mf->nice_len;
+
+	uint32_t len_main;
+	uint32_t matches_count;
+
+	if (mf->read_ahead == 0) {
+		len_main = mf_find(mf, &matches_count, coder->matches);
+	} else {
+		assert(mf->read_ahead == 1);
+		len_main = coder->longest_match_length;
+		matches_count = coder->matches_count;
+	}
+
+	const uint32_t buf_avail = my_min(mf_avail(mf) + 1, MATCH_LEN_MAX);
+	if (buf_avail < 2) {
+		*back_res = UINT32_MAX;
+		*len_res = 1;
+		return UINT32_MAX;
+	}
+
+	const uint8_t *const buf = mf_ptr(mf) - 1;
+
+	uint32_t rep_lens[REPS];
+	uint32_t rep_max_index = 0;
+
+	for (uint32_t i = 0; i < REPS; ++i) {
+		const uint8_t *const buf_back = buf - coder->reps[i] - 1;
+
+		if (not_equal_16(buf, buf_back)) {
+			rep_lens[i] = 0;
+			continue;
+		}
+
+		rep_lens[i] = lzma_memcmplen(buf, buf_back, 2, buf_avail);
+
+		if (rep_lens[i] > rep_lens[rep_max_index])
+			rep_max_index = i;
+	}
+
+	if (rep_lens[rep_max_index] >= nice_len) {
+		*back_res = rep_max_index;
+		*len_res = rep_lens[rep_max_index];
+		mf_skip(mf, *len_res - 1);
+		return UINT32_MAX;
+	}
+
+
+	if (len_main >= nice_len) {
+		*back_res = coder->matches[matches_count - 1].dist + REPS;
+		*len_res = len_main;
+		mf_skip(mf, len_main - 1);
+		return UINT32_MAX;
+	}
+
+	const uint8_t current_byte = *buf;
+	const uint8_t match_byte = *(buf - coder->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 UINT32_MAX;
+	}
+
+	coder->opts[0].state = coder->state;
+
+	const uint32_t pos_state = position & coder->pos_mask;
+
+	coder->opts[1].price = rc_bit_0_price(
+				coder->is_match[coder->state][pos_state])
+			+ get_literal_price(coder, position, buf[-1],
+				!is_literal_state(coder->state),
+				match_byte, current_byte);
+
+	make_literal(&coder->opts[1]);
+
+	const uint32_t match_price = rc_bit_1_price(
+			coder->is_match[coder->state][pos_state]);
+	const uint32_t rep_match_price = match_price
+			+ rc_bit_1_price(coder->is_rep[coder->state]);
+
+	if (match_byte == current_byte) {
+		const uint32_t short_rep_price = rep_match_price
+				+ get_short_rep_price(
+					coder, coder->state, pos_state);
+
+		if (short_rep_price < coder->opts[1].price) {
+			coder->opts[1].price = short_rep_price;
+			make_short_rep(&coder->opts[1]);
+		}
+	}
+
+	const uint32_t len_end = my_max(len_main, rep_lens[rep_max_index]);
+
+	if (len_end < 2) {
+		*back_res = coder->opts[1].back_prev;
+		*len_res = 1;
+		return UINT32_MAX;
+	}
+
+	coder->opts[1].pos_prev = 0;
+
+	for (uint32_t i = 0; i < REPS; ++i)
+		coder->opts[0].backs[i] = coder->reps[i];
+
+	uint32_t len = len_end;
+	do {
+		coder->opts[len].price = RC_INFINITY_PRICE;
+	} while (--len >= 2);
+
+
+	for (uint32_t i = 0; i < REPS; ++i) {
+		uint32_t rep_len = rep_lens[i];
+		if (rep_len < 2)
+			continue;
+
+		const uint32_t price = rep_match_price + get_pure_rep_price(
+				coder, i, coder->state, pos_state);
+
+		do {
+			const uint32_t cur_and_len_price = price
+					+ get_len_price(
+						&coder->rep_len_encoder,
+						rep_len, pos_state);
+
+			if (cur_and_len_price < coder->opts[rep_len].price) {
+				coder->opts[rep_len].price = cur_and_len_price;
+				coder->opts[rep_len].pos_prev = 0;
+				coder->opts[rep_len].back_prev = i;
+				coder->opts[rep_len].prev_1_is_literal = false;
+			}
+		} while (--rep_len >= 2);
+	}
+
+
+	const uint32_t normal_match_price = match_price
+			+ rc_bit_0_price(coder->is_rep[coder->state]);
+
+	len = rep_lens[0] >= 2 ? rep_lens[0] + 1 : 2;
+	if (len <= len_main) {
+		uint32_t i = 0;
+		while (len > coder->matches[i].len)
+			++i;
+
+		for(; ; ++len) {
+			const uint32_t dist = coder->matches[i].dist;
+			const uint32_t cur_and_len_price = normal_match_price
+					+ get_dist_len_price(coder,
+						dist, len, pos_state);
+
+			if (cur_and_len_price < coder->opts[len].price) {
+				coder->opts[len].price = cur_and_len_price;
+				coder->opts[len].pos_prev = 0;
+				coder->opts[len].back_prev = dist + REPS;
+				coder->opts[len].prev_1_is_literal = false;
+			}
+
+			if (len == coder->matches[i].len)
+				if (++i == matches_count)
+					break;
+		}
+	}
+
+	return len_end;
+}
+
+
+static inline uint32_t
+helper2(lzma_lzma1_encoder *coder, uint32_t *reps, const uint8_t *buf,
+		uint32_t len_end, uint32_t position, const uint32_t cur,
+		const uint32_t nice_len, const uint32_t buf_avail_full)
+{
+	uint32_t matches_count = coder->matches_count;
+	uint32_t new_len = coder->longest_match_length;
+	uint32_t pos_prev = coder->opts[cur].pos_prev;
+	lzma_lzma_state state;
+
+	if (coder->opts[cur].prev_1_is_literal) {
+		--pos_prev;
+
+		if (coder->opts[cur].prev_2) {
+			state = coder->opts[coder->opts[cur].pos_prev_2].state;
+
+			if (coder->opts[cur].back_prev_2 < REPS)
+				update_long_rep(state);
+			else
+				update_match(state);
+
+		} else {
+			state = coder->opts[pos_prev].state;
+		}
+
+		update_literal(state);
+
+	} else {
+		state = coder->opts[pos_prev].state;
+	}
+
+	if (pos_prev == cur - 1) {
+		if (is_short_rep(coder->opts[cur]))
+			update_short_rep(state);
+		else
+			update_literal(state);
+	} else {
+		uint32_t pos;
+		if (coder->opts[cur].prev_1_is_literal
+				&& coder->opts[cur].prev_2) {
+			pos_prev = coder->opts[cur].pos_prev_2;
+			pos = coder->opts[cur].back_prev_2;
+			update_long_rep(state);
+		} else {
+			pos = coder->opts[cur].back_prev;
+			if (pos < REPS)
+				update_long_rep(state);
+			else
+				update_match(state);
+		}
+
+		if (pos < REPS) {
+			reps[0] = coder->opts[pos_prev].backs[pos];
+
+			uint32_t i;
+			for (i = 1; i <= pos; ++i)
+				reps[i] = coder->opts[pos_prev].backs[i - 1];
+
+			for (; i < REPS; ++i)
+				reps[i] = coder->opts[pos_prev].backs[i];
+
+		} else {
+			reps[0] = pos - REPS;
+
+			for (uint32_t i = 1; i < REPS; ++i)
+				reps[i] = coder->opts[pos_prev].backs[i - 1];
+		}
+	}
+
+	coder->opts[cur].state = state;
+
+	for (uint32_t i = 0; i < REPS; ++i)
+		coder->opts[cur].backs[i] = reps[i];
+
+	const uint32_t cur_price = coder->opts[cur].price;
+
+	const uint8_t current_byte = *buf;
+	const uint8_t match_byte = *(buf - reps[0] - 1);
+
+	const uint32_t pos_state = position & coder->pos_mask;
+
+	const uint32_t cur_and_1_price = cur_price
+			+ rc_bit_0_price(coder->is_match[state][pos_state])
+			+ get_literal_price(coder, position, buf[-1],
+			!is_literal_state(state), match_byte, current_byte);
+
+	bool next_is_literal = false;
+
+	if (cur_and_1_price < coder->opts[cur + 1].price) {
+		coder->opts[cur + 1].price = cur_and_1_price;
+		coder->opts[cur + 1].pos_prev = cur;
+		make_literal(&coder->opts[cur + 1]);
+		next_is_literal = true;
+	}
+
+	const uint32_t match_price = cur_price
+			+ rc_bit_1_price(coder->is_match[state][pos_state]);
+	const uint32_t rep_match_price = match_price
+			+ rc_bit_1_price(coder->is_rep[state]);
+
+	if (match_byte == current_byte
+			&& !(coder->opts[cur + 1].pos_prev < cur
+				&& coder->opts[cur + 1].back_prev == 0)) {
+
+		const uint32_t short_rep_price = rep_match_price
+				+ get_short_rep_price(coder, state, pos_state);
+
+		if (short_rep_price <= coder->opts[cur + 1].price) {
+			coder->opts[cur + 1].price = short_rep_price;
+			coder->opts[cur + 1].pos_prev = cur;
+			make_short_rep(&coder->opts[cur + 1]);
+			next_is_literal = true;
+		}
+	}
+
+	if (buf_avail_full < 2)
+		return len_end;
+
+	const uint32_t buf_avail = my_min(buf_avail_full, nice_len);
+
+	if (!next_is_literal && match_byte != current_byte) { // speed optimization
+		// try literal + rep0
+		const uint8_t *const buf_back = buf - reps[0] - 1;
+		const uint32_t limit = my_min(buf_avail_full, nice_len + 1);
+
+		const uint32_t len_test = lzma_memcmplen(buf, buf_back, 1, limit) - 1;
+
+		if (len_test >= 2) {
+			lzma_lzma_state state_2 = state;
+			update_literal(state_2);
+
+			const uint32_t pos_state_next = (position + 1) & coder->pos_mask;
+			const uint32_t next_rep_match_price = cur_and_1_price
+					+ rc_bit_1_price(coder->is_match[state_2][pos_state_next])
+					+ rc_bit_1_price(coder->is_rep[state_2]);
+
+			//for (; len_test >= 2; --len_test) {
+			const uint32_t offset = cur + 1 + len_test;
+
+			while (len_end < offset)
+				coder->opts[++len_end].price = RC_INFINITY_PRICE;
+
+			const uint32_t cur_and_len_price = next_rep_match_price
+					+ get_rep_price(coder, 0, len_test,
+						state_2, pos_state_next);
+
+			if (cur_and_len_price < coder->opts[offset].price) {
+				coder->opts[offset].price = cur_and_len_price;
+				coder->opts[offset].pos_prev = cur + 1;
+				coder->opts[offset].back_prev = 0;
+				coder->opts[offset].prev_1_is_literal = true;
+				coder->opts[offset].prev_2 = false;
+			}
+			//}
+		}
+	}
+
+
+	uint32_t start_len = 2; // speed optimization
+
+	for (uint32_t rep_index = 0; rep_index < REPS; ++rep_index) {
+		const uint8_t *const buf_back = buf - reps[rep_index] - 1;
+		if (not_equal_16(buf, buf_back))
+			continue;
+
+		uint32_t len_test = lzma_memcmplen(buf, buf_back, 2, buf_avail);
+
+		while (len_end < cur + len_test)
+			coder->opts[++len_end].price = RC_INFINITY_PRICE;
+
+		const uint32_t len_test_temp = len_test;
+		const uint32_t price = rep_match_price + get_pure_rep_price(
+				coder, rep_index, state, pos_state);
+
+		do {
+			const uint32_t cur_and_len_price = price
+					+ get_len_price(&coder->rep_len_encoder,
+							len_test, pos_state);
+
+			if (cur_and_len_price < coder->opts[cur + len_test].price) {
+				coder->opts[cur + len_test].price = cur_and_len_price;
+				coder->opts[cur + len_test].pos_prev = cur;
+				coder->opts[cur + len_test].back_prev = rep_index;
+				coder->opts[cur + len_test].prev_1_is_literal = 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 = my_min(buf_avail_full,
+				len_test_2 + nice_len);
+		// NOTE: len_test_2 may be greater than limit so the call to
+		// lzma_memcmplen() must be done conditionally.
+		if (len_test_2 < limit)
+			len_test_2 = lzma_memcmplen(buf, buf_back, len_test_2, limit);
+
+		len_test_2 -= len_test + 1;
+
+		if (len_test_2 >= 2) {
+			lzma_lzma_state state_2 = state;
+			update_long_rep(state_2);
+
+			uint32_t pos_state_next = (position + len_test) & coder->pos_mask;
+
+			const uint32_t cur_and_len_literal_price = price
+					+ get_len_price(&coder->rep_len_encoder,
+						len_test, pos_state)
+					+ rc_bit_0_price(coder->is_match[state_2][pos_state_next])
+					+ get_literal_price(coder, position + len_test,
+						buf[len_test - 1], true,
+						buf_back[len_test], buf[len_test]);
+
+			update_literal(state_2);
+
+			pos_state_next = (position + len_test + 1) & coder->pos_mask;
+
+			const uint32_t next_rep_match_price = cur_and_len_literal_price
+					+ rc_bit_1_price(coder->is_match[state_2][pos_state_next])
+					+ rc_bit_1_price(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->opts[++len_end].price = RC_INFINITY_PRICE;
+
+			const uint32_t cur_and_len_price = next_rep_match_price
+					+ get_rep_price(coder, 0, len_test_2,
+						state_2, pos_state_next);
+
+			if (cur_and_len_price < coder->opts[offset].price) {
+				coder->opts[offset].price = cur_and_len_price;
+				coder->opts[offset].pos_prev = cur + len_test + 1;
+				coder->opts[offset].back_prev = 0;
+				coder->opts[offset].prev_1_is_literal = true;
+				coder->opts[offset].prev_2 = true;
+				coder->opts[offset].pos_prev_2 = cur;
+				coder->opts[offset].back_prev_2 = rep_index;
+			}
+			//}
+		}
+	}
+
+
+	//for (uint32_t len_test = 2; len_test <= new_len; ++len_test)
+	if (new_len > buf_avail) {
+		new_len = buf_avail;
+
+		matches_count = 0;
+		while (new_len > coder->matches[matches_count].len)
+			++matches_count;
+
+		coder->matches[matches_count++].len = new_len;
+	}
+
+
+	if (new_len >= start_len) {
+		const uint32_t normal_match_price = match_price
+				+ rc_bit_0_price(coder->is_rep[state]);
+
+		while (len_end < cur + new_len)
+			coder->opts[++len_end].price = RC_INFINITY_PRICE;
+
+		uint32_t i = 0;
+		while (start_len > coder->matches[i].len)
+			++i;
+
+		for (uint32_t len_test = start_len; ; ++len_test) {
+			const uint32_t cur_back = coder->matches[i].dist;
+			uint32_t cur_and_len_price = normal_match_price
+					+ get_dist_len_price(coder,
+						cur_back, len_test, pos_state);
+
+			if (cur_and_len_price < coder->opts[cur + len_test].price) {
+				coder->opts[cur + len_test].price = cur_and_len_price;
+				coder->opts[cur + len_test].pos_prev = cur;
+				coder->opts[cur + len_test].back_prev
+						= cur_back + REPS;
+				coder->opts[cur + len_test].prev_1_is_literal = false;
+			}
+
+			if (len_test == coder->matches[i].len) {
+				// Try Match + Literal + Rep0
+				const uint8_t *const buf_back = buf - cur_back - 1;
+				uint32_t len_test_2 = len_test + 1;
+				const uint32_t limit = my_min(buf_avail_full,
+						len_test_2 + nice_len);
+
+				// NOTE: len_test_2 may be greater than limit
+				// so the call to lzma_memcmplen() must be
+				// done conditionally.
+				if (len_test_2 < limit)
+					len_test_2 = lzma_memcmplen(buf, buf_back,
+							len_test_2, limit);
+
+				len_test_2 -= len_test + 1;
+
+				if (len_test_2 >= 2) {
+					lzma_lzma_state state_2 = state;
+					update_match(state_2);
+					uint32_t pos_state_next
+							= (position + len_test) & coder->pos_mask;
+
+					const uint32_t cur_and_len_literal_price = cur_and_len_price
+							+ rc_bit_0_price(
+								coder->is_match[state_2][pos_state_next])
+							+ get_literal_price(coder,
+								position + len_test,
+								buf[len_test - 1],
+								true,
+								buf_back[len_test],
+								buf[len_test]);
+
+					update_literal(state_2);
+					pos_state_next = (pos_state_next + 1) & coder->pos_mask;
+
+					const uint32_t next_rep_match_price
+							= cur_and_len_literal_price
+							+ rc_bit_1_price(
+								coder->is_match[state_2][pos_state_next])
+							+ rc_bit_1_price(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->opts[++len_end].price = RC_INFINITY_PRICE;
+
+					cur_and_len_price = next_rep_match_price
+							+ get_rep_price(coder, 0, len_test_2,
+								state_2, pos_state_next);
+
+					if (cur_and_len_price < coder->opts[offset].price) {
+						coder->opts[offset].price = cur_and_len_price;
+						coder->opts[offset].pos_prev = cur + len_test + 1;
+						coder->opts[offset].back_prev = 0;
+						coder->opts[offset].prev_1_is_literal = true;
+						coder->opts[offset].prev_2 = true;
+						coder->opts[offset].pos_prev_2 = cur;
+						coder->opts[offset].back_prev_2
+								= cur_back + REPS;
+					}
+					//}
+				}
+
+				if (++i == matches_count)
+					break;
+			}
+		}
+	}
+
+	return len_end;
+}
+
+
+extern void
+lzma_lzma_optimum_normal(lzma_lzma1_encoder *restrict coder,
+		lzma_mf *restrict mf,
+		uint32_t *restrict back_res, uint32_t *restrict len_res,
+		uint32_t position)
+{
+	// If we have symbols pending, return the next pending symbol.
+	if (coder->opts_end_index != coder->opts_current_index) {
+		assert(mf->read_ahead > 0);
+		*len_res = coder->opts[coder->opts_current_index].pos_prev
+				- coder->opts_current_index;
+		*back_res = coder->opts[coder->opts_current_index].back_prev;
+		coder->opts_current_index = coder->opts[
+				coder->opts_current_index].pos_prev;
+		return;
+	}
+
+	// Update the price tables. In LZMA SDK <= 4.60 (and possibly later)
+	// this was done in both initialization function and in the main loop.
+	// In liblzma they were moved into this single place.
+	if (mf->read_ahead == 0) {
+		if (coder->match_price_count >= (1 << 7))
+			fill_dist_prices(coder);
+
+		if (coder->align_price_count >= ALIGN_SIZE)
+			fill_align_prices(coder);
+	}
+
+	// TODO: This needs quite a bit of cleaning still. But splitting
+	// the original function into two pieces makes it at least a little
+	// more readable, since those two parts don't share many variables.
+
+	uint32_t len_end = helper1(coder, mf, back_res, len_res, position);
+	if (len_end == UINT32_MAX)
+		return;
+
+	uint32_t reps[REPS];
+	memcpy(reps, coder->reps, sizeof(reps));
+
+	uint32_t cur;
+	for (cur = 1; cur < len_end; ++cur) {
+		assert(cur < OPTS);
+
+		coder->longest_match_length = mf_find(
+				mf, &coder->matches_count, coder->matches);
+
+		if (coder->longest_match_length >= mf->nice_len)
+			break;
+
+		len_end = helper2(coder, reps, mf_ptr(mf) - 1, len_end,
+				position + cur, cur, mf->nice_len,
+				my_min(mf_avail(mf) + 1, OPTS - 1 - cur));
+	}
+
+	backward(coder, len_res, back_res, cur);
+	return;
+}
diff --git a/src/liblzma/lzma/lzma_encoder_presets.c b/src/liblzma/lzma/lzma_encoder_presets.c
new file mode 100644
index 0000000..711df02
--- /dev/null
+++ b/src/liblzma/lzma/lzma_encoder_presets.c
@@ -0,0 +1,64 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       lzma_encoder_presets.c
+/// \brief      Encoder presets
+/// \note       xz needs this even when only decoding is enabled.
+//
+//  Author:     Lasse Collin
+//
+//  This file has been put into the public domain.
+//  You can do whatever you want with this file.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include "common.h"
+
+
+extern LZMA_API(lzma_bool)
+lzma_lzma_preset(lzma_options_lzma *options, uint32_t preset)
+{
+	const uint32_t level = preset & LZMA_PRESET_LEVEL_MASK;
+	const uint32_t flags = preset & ~LZMA_PRESET_LEVEL_MASK;
+	const uint32_t supported_flags = LZMA_PRESET_EXTREME;
+
+	if (level > 9 || (flags & ~supported_flags))
+		return true;
+
+	options->preset_dict = NULL;
+	options->preset_dict_size = 0;
+
+	options->lc = LZMA_LC_DEFAULT;
+	options->lp = LZMA_LP_DEFAULT;
+	options->pb = LZMA_PB_DEFAULT;
+
+	static const uint8_t dict_pow2[]
+			= { 18, 20, 21, 22, 22, 23, 23, 24, 25, 26 };
+	options->dict_size = UINT32_C(1) << dict_pow2[level];
+
+	if (level <= 3) {
+		options->mode = LZMA_MODE_FAST;
+		options->mf = level == 0 ? LZMA_MF_HC3 : LZMA_MF_HC4;
+		options->nice_len = level <= 1 ? 128 : 273;
+		static const uint8_t depths[] = { 4, 8, 24, 48 };
+		options->depth = depths[level];
+	} else {
+		options->mode = LZMA_MODE_NORMAL;
+		options->mf = LZMA_MF_BT4;
+		options->nice_len = level == 4 ? 16 : level == 5 ? 32 : 64;
+		options->depth = 0;
+	}
+
+	if (flags & LZMA_PRESET_EXTREME) {
+		options->mode = LZMA_MODE_NORMAL;
+		options->mf = LZMA_MF_BT4;
+		if (level == 3 || level == 5) {
+			options->nice_len = 192;
+			options->depth = 0;
+		} else {
+			options->nice_len = 273;
+			options->depth = 512;
+		}
+	}
+
+	return false;
+}
diff --git a/src/liblzma/lzma/lzma_encoder_private.h b/src/liblzma/lzma/lzma_encoder_private.h
new file mode 100644
index 0000000..b228c57
--- /dev/null
+++ b/src/liblzma/lzma/lzma_encoder_private.h
@@ -0,0 +1,162 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       lzma_encoder_private.h
+/// \brief      Private definitions for LZMA encoder
+///
+//  Authors:    Igor Pavlov
+//              Lasse Collin
+//
+//  This file has been put into the public domain.
+//  You can do whatever you want with this file.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#ifndef LZMA_LZMA_ENCODER_PRIVATE_H
+#define LZMA_LZMA_ENCODER_PRIVATE_H
+
+#include "lz_encoder.h"
+#include "range_encoder.h"
+#include "lzma_common.h"
+#include "lzma_encoder.h"
+
+
+// Macro to compare if the first two bytes in two buffers differ. This is
+// needed in lzma_lzma_optimum_*() to test if the match is at least
+// MATCH_LEN_MIN bytes. Unaligned access gives tiny gain so there's no
+// reason to not use it when it is supported.
+#ifdef TUKLIB_FAST_UNALIGNED_ACCESS
+#	define not_equal_16(a, b) (read16ne(a) != read16ne(b))
+#else
+#	define not_equal_16(a, b) \
+		((a)[0] != (b)[0] || (a)[1] != (b)[1])
+#endif
+
+
+// Optimal - Number of entries in the optimum array.
+#define OPTS (1 << 12)
+
+
+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 {
+	lzma_lzma_state state;
+
+	bool prev_1_is_literal;
+	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[REPS];
+
+} lzma_optimal;
+
+
+struct lzma_lzma1_encoder_s {
+	/// Range encoder
+	lzma_range_encoder rc;
+
+	/// Uncompressed size (doesn't include possible preset dictionary)
+	uint64_t uncomp_size;
+
+	/// If non-zero, produce at most this much output.
+	/// Some input may then be missing from the output.
+	uint64_t out_limit;
+
+	/// If the above out_limit is non-zero, *uncomp_size_ptr is set to
+	/// the amount of uncompressed data that we were able to fit
+	/// in the output buffer.
+	uint64_t *uncomp_size_ptr;
+
+	/// State
+	lzma_lzma_state state;
+
+	/// The four most recent match distances
+	uint32_t reps[REPS];
+
+	/// Array of match candidates
+	lzma_match matches[MATCH_LEN_MAX + 1];
+
+	/// Number of match candidates in matches[]
+	uint32_t matches_count;
+
+	/// Variable to hold the length of the longest match between calls
+	/// to lzma_lzma_optimum_*().
+	uint32_t longest_match_length;
+
+	/// True if using getoptimumfast
+	bool fast_mode;
+
+	/// True if the encoder has been initialized by encoding the first
+	/// byte as a literal.
+	bool is_initialized;
+
+	/// True if the range encoder has been flushed, but not all bytes
+	/// have been written to the output buffer yet.
+	bool is_flushed;
+
+	/// True if end of payload marker will be written.
+	bool use_eopm;
+
+	uint32_t pos_mask;         ///< (1 << pos_bits) - 1
+	uint32_t literal_context_bits;
+	uint32_t literal_pos_mask;
+
+	// These are the same as in lzma_decoder.c. See comments there.
+	probability literal[LITERAL_CODERS_MAX][LITERAL_CODER_SIZE];
+	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 dist_slot[DIST_STATES][DIST_SLOTS];
+	probability dist_special[FULL_DISTANCES - DIST_MODEL_END];
+	probability dist_align[ALIGN_SIZE];
+
+	// These are the same as in lzma_decoder.c except that the encoders
+	// include also price tables.
+	lzma_length_encoder match_len_encoder;
+	lzma_length_encoder rep_len_encoder;
+
+	// Price tables
+	uint32_t dist_slot_prices[DIST_STATES][DIST_SLOTS];
+	uint32_t dist_prices[DIST_STATES][FULL_DISTANCES];
+	uint32_t dist_table_size;
+	uint32_t match_price_count;
+
+	uint32_t align_prices[ALIGN_SIZE];
+	uint32_t align_price_count;
+
+	// Optimal
+	uint32_t opts_end_index;
+	uint32_t opts_current_index;
+	lzma_optimal opts[OPTS];
+};
+
+
+extern void lzma_lzma_optimum_fast(
+		lzma_lzma1_encoder *restrict coder, lzma_mf *restrict mf,
+		uint32_t *restrict back_res, uint32_t *restrict len_res);
+
+extern void lzma_lzma_optimum_normal(lzma_lzma1_encoder *restrict coder,
+		lzma_mf *restrict mf, uint32_t *restrict back_res,
+		uint32_t *restrict len_res, uint32_t position);
+
+#endif