Imported to git.

7 files changed, 1728 insertions, 0 deletions

diff --git a/src/liblzma/subblock/Makefile.am b/src/liblzma/subblock/Makefile.am
new file mode 100644
index 00000000..8f2daf59
--- /dev/null
+++ b/src/liblzma/subblock/Makefile.am
@@ -0,0 +1,33 @@
+##
+##  Copyright (C) 2007 Lasse Collin
+##
+##  This library is free software; you can redistribute it and/or
+##  modify it under the terms of the GNU Lesser General Public
+##  License as published by the Free Software Foundation; either
+##  version 2.1 of the License, or (at your option) any later version.
+##
+##  This library is distributed in the hope that it will be useful,
+##  but WITHOUT ANY WARRANTY; without even the implied warranty of
+##  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+##  Lesser General Public License for more details.
+##
+
+noinst_LTLIBRARIES = libsubblock.la
+libsubblock_la_SOURCES =
+libsubblock_la_CPPFLAGS = \
+	-I@top_srcdir@/src/liblzma/api \
+	-I@top_srcdir@/src/liblzma/common
+
+if COND_MAIN_ENCODER
+libsubblock_la_SOURCES += \
+	subblock_encoder.c \
+	subblock_encoder.h
+endif
+
+if COND_MAIN_DECODER
+libsubblock_la_SOURCES += \
+	subblock_decoder.c \
+	subblock_decoder.h \
+	subblock_decoder_helper.c \
+	subblock_decoder_helper.h
+endif
diff --git a/src/liblzma/subblock/subblock_decoder.c b/src/liblzma/subblock/subblock_decoder.c
new file mode 100644
index 00000000..ef3c289f
--- /dev/null
+++ b/src/liblzma/subblock/subblock_decoder.c
@@ -0,0 +1,681 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       subblock_decoder.c
+/// \brief      Decoder of the Subblock filter
+//
+//  Copyright (C) 2007 Lasse Collin
+//
+//  This library is free software; you can redistribute it and/or
+//  modify it under the terms of the GNU Lesser General Public
+//  License as published by the Free Software Foundation; either
+//  version 2.1 of the License, or (at your option) any later version.
+//
+//  This library is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+//  Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include "subblock_decoder.h"
+#include "subblock_decoder_helper.h"
+#include "raw_decoder.h"
+
+
+/// Maximum number of consecutive Subblocks with Subblock Type Padding
+#define PADDING_MAX 31
+
+
+struct lzma_coder_s {
+	lzma_next_coder next;
+
+	enum {
+		SEQ_FLAGS,
+		SEQ_SIZE_1,
+		SEQ_SIZE_2,
+		SEQ_SIZE_3,
+		SEQ_DATA,
+		SEQ_REPEAT_COUNT_1,
+		SEQ_REPEAT_COUNT_2,
+		SEQ_REPEAT_COUNT_3,
+		SEQ_REPEAT_SIZE,
+		SEQ_REPEAT_READ_DATA,
+		SEQ_REPEAT_FAST,
+		SEQ_REPEAT_NORMAL,
+		SEQ_FILTER_FLAGS,
+		SEQ_FILTER_END,
+	} sequence;
+
+	/// Number of bytes left in the current Subblock Data field.
+	size_t size;
+
+	/// Uncompressed Size, or LZMA_VLI_VALUE_UNKNOWN if unknown.
+	lzma_vli uncompressed_size;
+
+	/// Number of consecutive Subblocks with Subblock Type Padding
+	uint32_t padding;
+
+	/// True when .next.code() has returned LZMA_STREAM_END.
+	bool next_finished;
+
+	/// True when the Subblock decoder has detected End of Payload Marker.
+	/// This may become true before next_finished becomes true.
+	bool this_finished;
+
+	/// True if Subfilters are allowed.
+	bool allow_subfilters;
+
+	/// Indicates if at least one byte of decoded output has been
+	/// produced after enabling Subfilter.
+	bool got_output_with_subfilter;
+
+	/// Possible subfilter
+	lzma_next_coder subfilter;
+
+	/// Filter Flags decoder is needed to parse the ID and Properties
+	/// of the subfilter.
+	lzma_next_coder filter_flags_decoder;
+
+	/// The filter_flags_decoder stores its results here.
+	lzma_options_filter filter_flags;
+
+	/// Options for the Subblock decoder helper. This is used to tell
+	/// the helper when it should return LZMA_STREAM_END to the subfilter.
+	lzma_options_subblock_helper helper;
+
+	struct {
+		/// How many times buffer should be repeated
+		size_t count;
+
+		/// Size of the buffer
+		size_t size;
+
+		/// Position in the buffer
+		size_t pos;
+
+		/// Buffer to hold the data to be repeated
+		uint8_t buffer[LZMA_SUBBLOCK_RLE_MAX];
+	} repeat;
+
+	/// Temporary buffer needed when the Subblock filter is not the last
+	/// filter in the chain. The output of the next filter is first
+	/// decoded into buffer[], which is then used as input for the actual
+	/// Subblock decoder.
+	struct {
+		size_t pos;
+		size_t size;
+		uint8_t buffer[LZMA_BUFFER_SIZE];
+	} temp;
+};
+
+
+/// Values of valid Subblock Flags
+enum {
+	FLAG_PADDING,
+	FLAG_EOPM,
+	FLAG_DATA,
+	FLAG_REPEAT,
+	FLAG_SET_SUBFILTER,
+	FLAG_END_SUBFILTER,
+};
+
+
+/// Substracts size from coder->uncompressed_size uncompressed size is known
+/// and size isn't bigger than coder->uncompressed_size.
+static inline bool
+update_uncompressed_size(lzma_coder *coder, size_t size)
+{
+	if (coder->uncompressed_size != LZMA_VLI_VALUE_UNKNOWN) {
+		if ((lzma_vli)(size) > coder->uncompressed_size)
+			return true;
+
+		coder->uncompressed_size -= size;
+	}
+
+	return false;
+}
+
+
+/// Calls the subfilter and updates coder->uncompressed_size.
+static lzma_ret
+subfilter_decode(lzma_coder *coder, lzma_allocator *allocator,
+		const uint8_t *in, size_t *in_pos,
+		size_t in_size, uint8_t *restrict out,
+		size_t *restrict out_pos, size_t out_size, lzma_action action)
+{
+	assert(coder->subfilter.code != NULL);
+
+	const size_t out_start = *out_pos;
+
+	// Call the subfilter.
+	const lzma_ret ret = coder->subfilter.code(
+			coder->subfilter.coder, allocator,
+			in, in_pos, in_size, out, out_pos, out_size, action);
+
+	// Update uncompressed_size.
+	if (update_uncompressed_size(coder, *out_pos - out_start))
+		return LZMA_DATA_ERROR;
+
+	return ret;
+}
+
+
+static lzma_ret
+decode_buffer(lzma_coder *coder, lzma_allocator *allocator,
+		const uint8_t *in, size_t *in_pos,
+		size_t in_size, uint8_t *restrict out,
+		size_t *restrict out_pos, size_t out_size, lzma_action action)
+{
+	while (*out_pos < out_size && (*in_pos < in_size
+			|| coder->sequence == SEQ_DATA))
+	switch (coder->sequence) {
+	case SEQ_FLAGS: {
+		if ((in[*in_pos] >> 4) != FLAG_PADDING)
+			coder->padding = 0;
+
+		// Do the correct action depending on the Subblock Type.
+		switch (in[*in_pos] >> 4) {
+		case FLAG_PADDING:
+			// Only check that reserved bits are zero.
+// 			if (++coder->padding > PADDING_MAX
+// 					|| in[*in_pos] & 0x0F)
+// 				return LZMA_DATA_ERROR;
+			++*in_pos;
+			break;
+
+		case FLAG_EOPM:
+			// Check that reserved bits are zero.
+			if (in[*in_pos] & 0x0F)
+				return LZMA_DATA_ERROR;
+
+			// There must be no Subfilter enabled.
+			if (coder->subfilter.code != NULL)
+				return LZMA_DATA_ERROR;
+
+			// End of Payload Marker must not be used if
+			// uncompressed size is known.
+			if (coder->uncompressed_size != LZMA_VLI_VALUE_UNKNOWN)
+				return LZMA_DATA_ERROR;
+
+			++*in_pos;
+			return LZMA_STREAM_END;
+
+		case FLAG_DATA:
+			// First four bits of the Subblock Data size.
+			coder->size = in[*in_pos] & 0x0F;
+			++*in_pos;
+			coder->got_output_with_subfilter = true;
+			coder->sequence = SEQ_SIZE_1;
+			break;
+
+		case FLAG_REPEAT:
+			// First four bits of the Repeat Count. We use
+			// coder->size as a temporary place for it.
+			coder->size = in[*in_pos] & 0x0F;
+			++*in_pos;
+			coder->got_output_with_subfilter = true;
+			coder->sequence = SEQ_REPEAT_COUNT_1;
+			break;
+
+		case FLAG_SET_SUBFILTER: {
+			if ((in[*in_pos] & 0x0F)
+					|| coder->subfilter.code != NULL
+					|| !coder->allow_subfilters)
+				return LZMA_DATA_ERROR;
+
+			assert(coder->filter_flags.options == NULL);
+			const lzma_ret ret = lzma_filter_flags_decoder_init(
+					&coder->filter_flags_decoder,
+					allocator, &coder->filter_flags);
+			if (ret != LZMA_OK)
+				return ret;
+
+			coder->got_output_with_subfilter = false;
+
+			++*in_pos;
+			coder->sequence = SEQ_FILTER_FLAGS;
+			break;
+		}
+
+		case FLAG_END_SUBFILTER:
+			if (coder->subfilter.code == NULL
+					|| !coder->got_output_with_subfilter)
+				return LZMA_DATA_ERROR;
+
+			// Tell the helper filter to indicate End of Input
+			// to our subfilter.
+			coder->helper.end_was_reached = true;
+
+			size_t dummy = 0;
+			const lzma_ret ret = subfilter_decode(coder, allocator,
+					NULL, &dummy, 0, out, out_pos,out_size,
+					action);
+
+			// If we didn't reach the end of the subfilter's output
+			// yet, return to the application. On the next call we
+			// will get to this same switch-case again, because we
+			// haven't updated *in_pos yet.
+			if (ret != LZMA_STREAM_END)
+				return ret;
+
+			// Free Subfilter's memory. This is a bit debatable,
+			// since we could avoid some malloc()/free() calls
+			// if the same Subfilter gets used soon again. But
+			// if Subfilter isn't used again, we could leave
+			// a memory-hogging filter dangling until someone
+			// frees Subblock filter itself.
+			lzma_next_coder_end(&coder->subfilter, allocator);
+
+			// Free memory used for subfilter options. This is
+			// safe, because we don't support any Subfilter that
+			// would allow pointers in the options structure.
+			lzma_free(coder->filter_flags.options, allocator);
+			coder->filter_flags.options = NULL;
+
+			++*in_pos;
+
+			if (coder->uncompressed_size == 0)
+				return LZMA_STREAM_END;
+
+			break;
+
+		default:
+			return LZMA_DATA_ERROR;
+		}
+
+		break;
+	}
+
+	case SEQ_SIZE_1:
+	case SEQ_REPEAT_COUNT_1:
+		// We use the same code to parse
+		//  - the Size (28 bits) in Subblocks of type Data; and
+		//  - the Repeat count (28 bits) in Subblocks of type
+		//    Repeating Data.
+		coder->size |= (size_t)(in[*in_pos]) << 4;
+		++*in_pos;
+		++coder->sequence;
+		break;
+
+	case SEQ_SIZE_2:
+	case SEQ_REPEAT_COUNT_2:
+		coder->size |= (size_t)(in[*in_pos]) << 12;
+		++*in_pos;
+		++coder->sequence;
+		break;
+
+	case SEQ_SIZE_3:
+	case SEQ_REPEAT_COUNT_3:
+		coder->size |= (size_t)(in[*in_pos]) << 20;
+
+		// The real value is the stored value plus one.
+		++coder->size;
+
+		++*in_pos;
+		++coder->sequence;
+		break;
+
+	case SEQ_REPEAT_SIZE:
+		// Move the Repeat Count to the correct variable and parse
+		// the Size of the Data to be repeated.
+		coder->repeat.count = coder->size;
+		coder->repeat.size = (size_t)(in[*in_pos]) + 1;
+		coder->repeat.pos = 0;
+		++*in_pos;
+		coder->sequence = SEQ_REPEAT_READ_DATA;
+		break;
+
+	case SEQ_REPEAT_READ_DATA: {
+		// Fill coder->repeat.buffer[].
+		const size_t in_avail = in_size - *in_pos;
+		const size_t out_avail
+				= coder->repeat.size - coder->repeat.pos;
+		const size_t copy_size = MIN(in_avail, out_avail);
+
+		memcpy(coder->repeat.buffer + coder->repeat.pos,
+				in + *in_pos, copy_size);
+		*in_pos += copy_size;
+		coder->repeat.pos += copy_size;
+
+		if (coder->repeat.pos == coder->repeat.size) {
+			coder->repeat.pos = 0;
+
+			if (coder->repeat.size == 1
+					&& coder->subfilter.code == NULL)
+				coder->sequence = SEQ_REPEAT_FAST;
+			else
+				coder->sequence = SEQ_REPEAT_NORMAL;
+		}
+
+		break;
+	}
+
+	case SEQ_REPEAT_FAST: {
+		// Optimization for cases when there is only one byte to
+		// repeat and no Subfilter.
+		const size_t out_avail = out_size - *out_pos;
+		const size_t copy_size = MIN(coder->repeat.count, out_avail);
+
+		memset(out + *out_pos, coder->repeat.buffer[0], copy_size);
+
+		*out_pos += copy_size;
+		coder->repeat.count -= copy_size;
+
+		if (update_uncompressed_size(coder, copy_size))
+			return LZMA_DATA_ERROR;
+
+		if (coder->repeat.count == 0) {
+			if (coder->uncompressed_size == 0)
+				return LZMA_STREAM_END;
+		} else {
+			return LZMA_OK;
+		}
+
+		coder->sequence = SEQ_FLAGS;
+		break;
+	}
+
+	case SEQ_REPEAT_NORMAL:
+		do {
+			// Cycle the repeat buffer if needed.
+			if (coder->repeat.pos == coder->repeat.size) {
+				if (--coder->repeat.count == 0) {
+					coder->sequence = SEQ_FLAGS;
+					break;
+				}
+
+				coder->repeat.pos = 0;
+			}
+
+			if (coder->subfilter.code == NULL) {
+				const size_t copy_size = bufcpy(
+						coder->repeat.buffer,
+						&coder->repeat.pos,
+						coder->repeat.size,
+						out, out_pos, out_size);
+
+				if (update_uncompressed_size(coder, copy_size))
+					return LZMA_DATA_ERROR;
+
+			} else {
+				const lzma_ret ret = subfilter_decode(
+						coder, allocator,
+						coder->repeat.buffer,
+						&coder->repeat.pos,
+						coder->repeat.size,
+						out, out_pos, out_size,
+						action);
+
+				if (ret == LZMA_STREAM_END) {
+					// End of Subfilter can occur only at
+					// a Subblock boundary.
+					if (coder->repeat.pos
+							!= coder->repeat.size
+							|| --coder->repeat
+								.count != 0)
+						return LZMA_DATA_ERROR;
+
+					// We need a Subblock with Unset
+					// Subfilter before more data.
+					coder->sequence = SEQ_FILTER_END;
+					break;
+
+				} else if (ret != LZMA_OK) {
+					return ret;
+				}
+			}
+		} while (*out_pos < out_size);
+
+		break;
+
+	case SEQ_DATA: {
+		// Limit the amount of input to match the available
+		// Subblock Data size.
+		size_t in_limit;
+		if (in_size - *in_pos > coder->size)
+			in_limit = *in_pos + coder->size;
+		else
+			in_limit = in_size;
+
+		if (coder->subfilter.code == NULL) {
+			const size_t copy_size = bufcpy(
+					in, in_pos, in_limit,
+					out, out_pos, out_size);
+
+			coder->size -= copy_size;
+
+			if (update_uncompressed_size(coder, copy_size))
+				return LZMA_DATA_ERROR;
+
+		} else {
+			const size_t in_start = *in_pos;
+			const lzma_ret ret = subfilter_decode(
+					coder, allocator,
+					in, in_pos, in_limit,
+					out, out_pos, out_size,
+					action);
+
+			// Update the number of unprocessed bytes left in
+			// this Subblock. This assert() is true because
+			// in_limit prevents *in_pos getting too big.
+			assert(*in_pos - in_start <= coder->size);
+			coder->size -= *in_pos - in_start;
+
+			if (ret == LZMA_STREAM_END) {
+				// End of Subfilter can occur only at
+				// a Subblock boundary.
+				if (coder->size != 0)
+					return LZMA_DATA_ERROR;
+
+				// We need a Subblock with Unset
+				// Subfilter before more data.
+				coder->sequence = SEQ_FILTER_END;
+				break;
+			}
+
+			if (ret != LZMA_OK)
+				return ret;
+		}
+
+		// If we couldn't process the whole Subblock Data yet, return.
+		if (coder->size > 0)
+			return LZMA_OK;
+
+		// Check if we have decoded all the data.
+		if (coder->uncompressed_size == 0
+				&& coder->subfilter.code == NULL)
+			return LZMA_STREAM_END;
+
+		coder->sequence = SEQ_FLAGS;
+		break;
+	}
+
+	case SEQ_FILTER_FLAGS: {
+		lzma_ret ret = coder->filter_flags_decoder.code(
+				coder->filter_flags_decoder.coder, allocator,
+				in, in_pos, in_size, NULL, NULL, 0, LZMA_RUN);
+		if (ret != LZMA_STREAM_END)
+			return ret == LZMA_HEADER_ERROR
+					? LZMA_DATA_ERROR : ret;
+
+		// Don't free the filter_flags_decoder. It doesn't take much
+		// memory and we may need it again.
+
+		// Initialize the Subfilter. Subblock and Copy filters are
+		// not allowed.
+		if (coder->filter_flags.id == LZMA_FILTER_COPY
+				|| coder->filter_flags.id
+					== LZMA_FILTER_SUBBLOCK)
+			return LZMA_DATA_ERROR;
+
+		coder->helper.end_was_reached = false;
+
+		lzma_options_filter filters[3] = {
+			{
+				.id = coder->filter_flags.id,
+				.options = coder->filter_flags.options,
+			}, {
+				.id = LZMA_FILTER_SUBBLOCK_HELPER,
+				.options = &coder->helper,
+			}, {
+				.id = LZMA_VLI_VALUE_UNKNOWN,
+				.options = NULL,
+			}
+		};
+
+		// Optimization: We know that LZMA uses End of Payload Marker
+		// (not End of Input), so we can omit the helper filter.
+		if (filters[0].id == LZMA_FILTER_LZMA)
+			filters[1].id = LZMA_VLI_VALUE_UNKNOWN;
+
+		ret = lzma_raw_decoder_init(&coder->subfilter, allocator,
+				filters, LZMA_VLI_VALUE_UNKNOWN, false);
+		if (ret != LZMA_OK)
+			return ret;
+
+		coder->sequence = SEQ_FLAGS;
+		break;
+	}
+
+	case SEQ_FILTER_END:
+		// We are in the beginning of a Subblock. The next Subblock
+		// whose type is not Padding, must indicate end of Subfilter.
+		if (in[*in_pos] == (FLAG_PADDING << 4)) {
+			++*in_pos;
+			break;
+		}
+
+		if (in[*in_pos] != (FLAG_END_SUBFILTER << 4))
+			return LZMA_DATA_ERROR;
+
+		coder->sequence = SEQ_FLAGS;
+		break;
+
+	default:
+		return LZMA_PROG_ERROR;
+	}
+
+	return LZMA_OK;
+}
+
+
+static lzma_ret
+subblock_decode(lzma_coder *coder, lzma_allocator *allocator,
+		const uint8_t *restrict in, size_t *restrict in_pos,
+		size_t in_size, uint8_t *restrict out,
+		size_t *restrict out_pos, size_t out_size, lzma_action action)
+{
+	if (coder->next.code == NULL)
+		return decode_buffer(coder, allocator, in, in_pos, in_size,
+				out, out_pos, out_size, action);
+
+	while (*out_pos < out_size) {
+		if (!coder->next_finished
+				&& coder->temp.pos == coder->temp.size) {
+			coder->temp.pos = 0;
+			coder->temp.size = 0;
+
+			const lzma_ret ret = coder->next.code(
+					coder->next.coder,
+					allocator, in, in_pos, in_size,
+					coder->temp.buffer, &coder->temp.size,
+					LZMA_BUFFER_SIZE, action);
+
+			if (ret == LZMA_STREAM_END)
+				coder->next_finished = true;
+			else if (coder->temp.size == 0 || ret != LZMA_OK)
+				return ret;
+		}
+
+		if (coder->this_finished) {
+			if (coder->temp.pos != coder->temp.size)
+				return LZMA_DATA_ERROR;
+
+			if (coder->next_finished)
+				return LZMA_STREAM_END;
+
+			return LZMA_OK;
+		}
+
+		const lzma_ret ret = decode_buffer(coder, allocator,
+				coder->temp.buffer, &coder->temp.pos,
+				coder->temp.size,
+				out, out_pos, out_size, action);
+
+		if (ret == LZMA_STREAM_END)
+			// The next coder in the chain hasn't finished
+			// yet. If the input data is valid, there
+			// must be no more output coming, but the
+			// next coder may still need a litle more
+			// input to detect End of Payload Marker.
+			coder->this_finished = true;
+		else if (ret != LZMA_OK)
+			return ret;
+		else if (coder->next_finished && *out_pos < out_size)
+			return LZMA_DATA_ERROR;
+	}
+
+	return LZMA_OK;
+}
+
+
+static void
+subblock_decoder_end(lzma_coder *coder, lzma_allocator *allocator)
+{
+	lzma_next_coder_end(&coder->next, allocator);
+	lzma_next_coder_end(&coder->subfilter, allocator);
+	lzma_next_coder_end(&coder->filter_flags_decoder, allocator);
+	lzma_free(coder->filter_flags.options, allocator);
+	lzma_free(coder, allocator);
+	return;
+}
+
+
+extern lzma_ret
+lzma_subblock_decoder_init(lzma_next_coder *next, lzma_allocator *allocator,
+		const lzma_filter_info *filters)
+{
+	if (next->coder == NULL) {
+		next->coder = lzma_alloc(sizeof(lzma_coder), allocator);
+		if (next->coder == NULL)
+			return LZMA_MEM_ERROR;
+
+		next->coder->next = LZMA_NEXT_CODER_INIT;
+		next->coder->subfilter = LZMA_NEXT_CODER_INIT;
+		next->coder->filter_flags_decoder = LZMA_NEXT_CODER_INIT;
+
+	} else {
+		lzma_next_coder_end(&next->coder->subfilter, allocator);
+		lzma_free(next->coder->filter_flags.options, allocator);
+	}
+
+	next->coder->filter_flags.options = NULL;
+
+	next->coder->sequence = SEQ_FLAGS;
+	next->coder->uncompressed_size = filters[0].uncompressed_size;
+	next->coder->padding = 0;
+	next->coder->next_finished = false;
+	next->coder->this_finished = false;
+	next->coder->temp.pos = 0;
+	next->coder->temp.size = 0;
+
+	if (filters[0].options != NULL)
+		next->coder->allow_subfilters = ((lzma_options_subblock *)(
+				filters[0].options))->allow_subfilters;
+	else
+		next->coder->allow_subfilters = false;
+
+	{
+		const lzma_ret ret = lzma_next_filter_init(&next->coder->next,
+				allocator, filters + 1);
+		if (ret != LZMA_OK) {
+			subblock_decoder_end(next->coder, allocator);
+			return ret;
+		}
+	}
+
+	next->code = &subblock_decode;
+	next->end = &subblock_decoder_end;
+
+	return LZMA_OK;
+}
diff --git a/src/liblzma/subblock/subblock_decoder.h b/src/liblzma/subblock/subblock_decoder.h
new file mode 100644
index 00000000..724ef357
--- /dev/null
+++ b/src/liblzma/subblock/subblock_decoder.h
@@ -0,0 +1,29 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       subblock_decoder.h
+/// \brief      Decoder of the Subblock filter
+//
+//  Copyright (C) 2007 Lasse Collin
+//
+//  This library is free software; you can redistribute it and/or
+//  modify it under the terms of the GNU Lesser General Public
+//  License as published by the Free Software Foundation; either
+//  version 2.1 of the License, or (at your option) any later version.
+//
+//  This library is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+//  Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#ifndef LZMA_SUBBLOCK_DECODER_H
+#define LZMA_SUBBLOCK_DECODER_H
+
+#include "common.h"
+
+
+extern lzma_ret lzma_subblock_decoder_init(lzma_next_coder *next,
+		lzma_allocator *allocator, const lzma_filter_info *filters);
+
+#endif
diff --git a/src/liblzma/subblock/subblock_decoder_helper.c b/src/liblzma/subblock/subblock_decoder_helper.c
new file mode 100644
index 00000000..5ff24431
--- /dev/null
+++ b/src/liblzma/subblock/subblock_decoder_helper.c
@@ -0,0 +1,80 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       subblock_decoder_helper.c
+/// \brief      Helper filter for the Subblock decoder
+///
+/// This filter is used to indicate End of Input for subfilters needing it.
+//
+//  Copyright (C) 2007 Lasse Collin
+//
+//  This library is free software; you can redistribute it and/or
+//  modify it under the terms of the GNU Lesser General Public
+//  License as published by the Free Software Foundation; either
+//  version 2.1 of the License, or (at your option) any later version.
+//
+//  This library is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+//  Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include "subblock_decoder_helper.h"
+
+
+struct lzma_coder_s {
+	const lzma_options_subblock_helper *options;
+};
+
+
+static lzma_ret
+helper_decode(lzma_coder *coder,
+		lzma_allocator *allocator lzma_attribute((unused)),
+		const uint8_t *restrict in, size_t *restrict in_pos,
+		size_t in_size, uint8_t *restrict out,
+		size_t *restrict out_pos, size_t out_size,
+		lzma_action action lzma_attribute((unused)))
+{
+	// If end_was_reached is true, we cannot have any input.
+	assert(!coder->options->end_was_reached || *in_pos == in_size);
+
+	// We can safely copy as much as possible, because we are never
+	// given more data than a single Subblock Data field.
+	bufcpy(in, in_pos, in_size, out, out_pos, out_size);
+
+	// Return LZMA_STREAM_END when instructed so by the Subblock decoder.
+	return coder->options->end_was_reached ? LZMA_STREAM_END : LZMA_OK;
+}
+
+
+static void
+helper_end(lzma_coder *coder, lzma_allocator *allocator)
+{
+	lzma_free(coder, allocator);
+	return;
+}
+
+
+extern lzma_ret
+lzma_subblock_decoder_helper_init(lzma_next_coder *next,
+		lzma_allocator *allocator, const lzma_filter_info *filters)
+{
+	// This is always the last filter in the chain.
+	assert(filters[1].init == NULL);
+
+	// We never know uncompressed size.
+	assert(filters[0].uncompressed_size == LZMA_VLI_VALUE_UNKNOWN);
+
+	if (next->coder == NULL) {
+		next->coder = lzma_alloc(sizeof(lzma_coder), allocator);
+		if (next->coder == NULL)
+			return LZMA_MEM_ERROR;
+		
+		next->code = &helper_decode;
+		next->end = helper_end;
+	}
+
+	next->coder->options = filters[0].options;
+
+	return LZMA_OK;
+}
diff --git a/src/liblzma/subblock/subblock_decoder_helper.h b/src/liblzma/subblock/subblock_decoder_helper.h
new file mode 100644
index 00000000..2a3e999e
--- /dev/null
+++ b/src/liblzma/subblock/subblock_decoder_helper.h
@@ -0,0 +1,36 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       subblock_decoder_helper.h
+/// \brief      Helper filter for the Subblock decoder
+///
+/// This filter is used to indicate End of Input for subfilters needing it.
+//
+//  Copyright (C) 2007 Lasse Collin
+//
+//  This library is free software; you can redistribute it and/or
+//  modify it under the terms of the GNU Lesser General Public
+//  License as published by the Free Software Foundation; either
+//  version 2.1 of the License, or (at your option) any later version.
+//
+//  This library is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+//  Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#ifndef LZMA_SUBBLOCK_DECODER_HELPER_H
+#define LZMA_SUBBLOCK_DECODER_HELPER_H
+
+#include "common.h"
+
+
+typedef struct {
+	bool end_was_reached;
+} lzma_options_subblock_helper;
+
+
+extern lzma_ret lzma_subblock_decoder_helper_init(lzma_next_coder *next,
+		lzma_allocator *allocator, const lzma_filter_info *filters);
+
+#endif
diff --git a/src/liblzma/subblock/subblock_encoder.c b/src/liblzma/subblock/subblock_encoder.c
new file mode 100644
index 00000000..9fa95b24
--- /dev/null
+++ b/src/liblzma/subblock/subblock_encoder.c
@@ -0,0 +1,841 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       subblock_encoder.c
+/// \brief      Encoder of the Subblock filter
+//
+//  Copyright (C) 2007 Lasse Collin
+//
+//  This library is free software; you can redistribute it and/or
+//  modify it under the terms of the GNU Lesser General Public
+//  License as published by the Free Software Foundation; either
+//  version 2.1 of the License, or (at your option) any later version.
+//
+//  This library is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+//  Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include "subblock_encoder.h"
+#include "raw_encoder.h"
+
+
+#define REPEAT_COUNT_MAX (1U << 28)
+
+/// Number of bytes the data chunk being repeated must be before we care
+/// about alignment. This is somewhat arbitrary. It just doesn't make sense
+/// to waste bytes for alignment when the data chunk is very small.
+///
+/// TODO Rename and use this also for Subblock Data?
+#define RLE_MIN_SIZE_FOR_ALIGN 3
+
+#define write_byte(b) \
+do { \
+	out[*out_pos] = b; \
+	++*out_pos; \
+	++coder->alignment.out_pos; \
+} while (0)
+
+
+struct lzma_coder_s {
+	lzma_next_coder next;
+	bool next_finished;
+
+	enum {
+		SEQ_FILL,
+		SEQ_FLUSH,
+		SEQ_RLE_COUNT_0,
+		SEQ_RLE_COUNT_1,
+		SEQ_RLE_COUNT_2,
+		SEQ_RLE_COUNT_3,
+		SEQ_RLE_SIZE,
+		SEQ_RLE_DATA,
+		SEQ_DATA_SIZE_0,
+		SEQ_DATA_SIZE_1,
+		SEQ_DATA_SIZE_2,
+		SEQ_DATA_SIZE_3,
+		SEQ_DATA,
+		SEQ_SUBFILTER_INIT,
+		SEQ_SUBFILTER_FLAGS,
+	} sequence;
+
+	lzma_options_subblock *options;
+
+	lzma_vli uncompressed_size;
+
+	size_t pos;
+	uint32_t tmp;
+
+	struct {
+		uint32_t multiple;
+		uint32_t in_pending;
+		uint32_t in_pos;
+		uint32_t out_pos;
+	} alignment;
+
+	struct {
+		uint8_t *data;
+		size_t size;
+		size_t limit;
+	} subblock;
+
+	struct {
+		uint8_t buffer[LZMA_SUBBLOCK_RLE_MAX];
+		size_t size;
+		lzma_vli count;
+	} rle;
+
+	struct {
+		enum {
+			SUB_NONE,
+			SUB_SET,
+			SUB_RUN,
+			SUB_FINISH,
+			SUB_END_MARKER,
+		} mode;
+
+		bool got_input;
+
+		uint8_t *flags;
+		size_t flags_size;
+
+		lzma_next_coder subcoder;
+
+	} subfilter;
+
+	struct {
+		size_t pos;
+		size_t size;
+		uint8_t buffer[LZMA_BUFFER_SIZE];
+	} temp;
+};
+
+
+/// \brief      Aligns the output buffer
+///
+/// Aligns the output buffer so that after skew bytes the output position is
+/// a multiple of coder->alignment.multiple.
+static bool
+subblock_align(lzma_coder *coder, uint8_t *restrict out,
+		size_t *restrict out_pos, size_t out_size, uint32_t skew)
+{
+	assert(*out_pos < out_size);
+
+	const uint32_t target = coder->alignment.in_pos
+			% coder->alignment.multiple;
+
+	while ((coder->alignment.out_pos + skew)
+			% coder->alignment.multiple != target) {
+		// Zero indicates padding.
+		write_byte(0x00);
+
+		// Check if output buffer got full and indicate it to
+		// the caller.
+		if (*out_pos == out_size)
+			return true;
+	}
+
+	coder->alignment.in_pos += coder->alignment.in_pending;
+	coder->alignment.in_pending = 0;
+
+	// Output buffer is not full.
+	return false;
+}
+
+
+/// \brief      Checks if buffer contains repeated data
+///
+/// \param      needle      Buffer containing a single repeat chunk
+/// \param      needle_size Size of needle in bytes
+/// \param      buf         Buffer to search for repeated needles
+/// \param      buf_chunks  Buffer size is buf_chunks * needle_size.
+///
+/// \return     True if the whole buf is filled with repeated needles.
+///
+static bool
+is_repeating(const uint8_t *restrict needle, size_t needle_size,
+		const uint8_t *restrict buf, size_t buf_chunks)
+{
+	while (buf_chunks-- != 0) {
+		if (memcmp(buf, needle, needle_size) != 0)
+			return false;
+
+		buf += needle_size;
+	}
+
+	return true;
+}
+
+
+/// \brief      Optimizes the repeating style and updates coder->sequence
+static void
+subblock_rle_flush(lzma_coder *coder)
+{
+	// The Subblock decoder can use memset() when the size of the data
+	// being repeated is one byte, so we check if the RLE buffer is
+	// filled with a single repeating byte.
+	if (coder->rle.size > 1) {
+		const uint8_t b = coder->rle.buffer[0];
+		size_t i = 0;
+		while (true) {
+			if (coder->rle.buffer[i] != b)
+				break;
+
+			if (++i == coder->rle.size) {
+				// TODO Integer overflow check maybe,
+				// although this needs at least 2**63 bytes
+				// of input until it gets triggered...
+				coder->rle.count *= coder->rle.size;
+				coder->rle.size = 1;
+				break;
+			}
+		}
+	}
+
+	if (coder->rle.count > REPEAT_COUNT_MAX)
+		coder->tmp = REPEAT_COUNT_MAX - 1;
+	else
+		coder->tmp = coder->rle.count - 1;
+
+	coder->sequence = SEQ_RLE_COUNT_0;
+
+	return;
+}
+
+
+/// \brief      Resizes coder->subblock.data for a new size limit
+static lzma_ret
+subblock_data_size(lzma_coder *coder, lzma_allocator *allocator,
+		size_t new_limit)
+{
+	// Verify that the new limit is valid.
+	if (new_limit < LZMA_SUBBLOCK_DATA_SIZE_MIN
+			|| new_limit > LZMA_SUBBLOCK_DATA_SIZE_MAX)
+		return LZMA_HEADER_ERROR;
+
+	// Ff the new limit is different than the previous one, we need
+	// to reallocate the data buffer.
+	if (new_limit != coder->subblock.limit) {
+		lzma_free(coder->subblock.data, allocator);
+		coder->subblock.data = lzma_alloc(new_limit, allocator);
+		if (coder->subblock.data == NULL)
+			return LZMA_MEM_ERROR;
+	}
+
+	coder->subblock.limit = new_limit;
+
+	return LZMA_OK;
+}
+
+
+static lzma_ret
+subblock_buffer(lzma_coder *coder, lzma_allocator *allocator,
+		const uint8_t *restrict in, size_t *restrict in_pos,
+		size_t in_size, uint8_t *restrict out,
+		size_t *restrict out_pos, size_t out_size, lzma_action action)
+{
+	// Verify that there is a sane amount of input.
+	if (coder->uncompressed_size != LZMA_VLI_VALUE_UNKNOWN) {
+		const lzma_vli in_avail = in_size - *in_pos;
+		if (action == LZMA_FINISH) {
+			if (in_avail != coder->uncompressed_size)
+				return LZMA_DATA_ERROR;
+		} else {
+			if (in_avail > coder->uncompressed_size)
+				return LZMA_DATA_ERROR;
+		}
+	}
+
+	// Check if we need to do something special with the Subfilter.
+	if (coder->options != NULL && coder->options->allow_subfilters) {
+		switch (coder->options->subfilter_mode) {
+		case LZMA_SUBFILTER_NONE:
+			if (coder->subfilter.mode != SUB_NONE)
+				return LZMA_PROG_ERROR;
+			break;
+
+		case LZMA_SUBFILTER_SET:
+			if (coder->subfilter.mode != SUB_NONE)
+				return LZMA_HEADER_ERROR;
+
+			coder->subfilter.mode = SUB_SET;
+			coder->subfilter.got_input = false;
+
+			if (coder->sequence == SEQ_FILL)
+				coder->sequence = SEQ_FLUSH;
+
+			break;
+
+		case LZMA_SUBFILTER_RUN:
+			if (coder->subfilter.mode != SUB_RUN)
+				return LZMA_PROG_ERROR;
+			break;
+
+		case LZMA_SUBFILTER_FINISH:
+			if (coder->subfilter.mode == SUB_RUN)
+				coder->subfilter.mode = SUB_FINISH;
+			else if (coder->subfilter.mode != SUB_FINISH)
+				return LZMA_PROG_ERROR;
+
+			if (!coder->subfilter.got_input)
+				return LZMA_PROG_ERROR;
+
+			break;
+
+		default:
+			return LZMA_HEADER_ERROR;
+		}
+	}
+
+	// Main loop
+	while (*out_pos < out_size)
+	switch (coder->sequence) {
+	case SEQ_FILL: {
+		// Grab the new Subblock Data Size and reallocate the buffer.
+		if (coder->subblock.size == 0 && coder->options != NULL
+				&& coder->options->subblock_data_size
+					!= coder->subblock.limit) {
+			const lzma_ret ret = subblock_data_size(coder,
+					allocator, coder->options
+						->subblock_data_size);
+			if (ret != LZMA_OK)
+				return ret;
+		}
+
+		if (coder->subfilter.mode == SUB_NONE) {
+			assert(coder->subfilter.subcoder.code == NULL);
+
+			// No Subfilter is enabled, just copy the data as is.
+			// NOTE: uncompressed_size cannot overflow because we
+			// have checked/ it in the beginning of this function.
+			const size_t in_used = bufcpy(in, in_pos, in_size,
+					coder->subblock.data,
+					&coder->subblock.size,
+					coder->subblock.limit);
+
+			if (coder->uncompressed_size != LZMA_VLI_VALUE_UNKNOWN)
+				coder->uncompressed_size -= in_used;
+
+			coder->alignment.in_pending += in_used;
+
+		} else {
+			const size_t in_start = *in_pos;
+			lzma_ret ret;
+
+			if (coder->subfilter.mode == SUB_FINISH) {
+				// Let the Subfilter write out pending data,
+				// but don't give it any new input anymore.
+				size_t dummy = 0;
+				ret = coder->subfilter.subcoder.code(coder
+						->subfilter.subcoder.coder,
+						allocator, NULL, &dummy, 0,
+						coder->subblock.data,
+						&coder->subblock.size,
+						coder->subblock.limit,
+						LZMA_FINISH);
+			} else {
+				// Give our input data to the Subfilter. Note
+				// that action can be LZMA_FINISH. In that
+				// case, we filter everything until the end
+				// of the input. The application isn't required
+				// to separately set LZMA_SUBBLOCK_FINISH.
+				ret = coder->subfilter.subcoder.code(coder
+						->subfilter.subcoder.coder,
+						allocator, in, in_pos, in_size,
+						coder->subblock.data,
+						&coder->subblock.size,
+						coder->subblock.limit,
+						action);
+			}
+
+			const size_t in_used = *in_pos - in_start;
+
+			if (in_used > 0)
+				coder->subfilter.got_input = true;
+
+			// NOTE: uncompressed_size cannot overflow because we
+			// have checked it in the beginning of this function.
+			if (coder->uncompressed_size != LZMA_VLI_VALUE_UNKNOWN)
+				coder->uncompressed_size -= *in_pos - in_start;
+
+			coder->alignment.in_pending += in_used;
+
+			if (ret == LZMA_STREAM_END) {
+				// We don't strictly need to do this, but
+				// doing it sounds like a good idea, because
+				// otherwise the Subfilter's memory could be
+				// left allocated for long time, and would
+				// just waste memory.
+				lzma_next_coder_end(&coder->subfilter.subcoder,
+						allocator);
+
+				assert(coder->options != NULL);
+				coder->options->subfilter_mode
+						= LZMA_SUBFILTER_NONE;
+
+				assert(coder->subfilter.mode == SUB_FINISH
+						|| action == LZMA_FINISH);
+				coder->subfilter.mode = SUB_END_MARKER;
+
+				// Flush now. Even if coder->subblock.size
+				// happens to be zero, we still need to go
+				// to SEQ_FLUSH to write the Subfilter Unset
+				// indicator.
+				coder->sequence = SEQ_FLUSH;
+				break;
+			}
+
+			// Return if an error occurred.
+			if (ret != LZMA_OK)
+				return ret;
+		}
+
+		// If we ran out of input before the whole buffer
+		// was filled, return to application.
+		if (coder->subblock.size < coder->subblock.limit
+				&& action != LZMA_FINISH)
+			return LZMA_OK;
+
+		coder->sequence = SEQ_FLUSH;
+	}
+
+	// Fall through
+
+	case SEQ_FLUSH:
+		if (coder->options != NULL) {
+			// Update the alignment variable.
+			coder->alignment.multiple = coder->options->alignment;
+			if (coder->alignment.multiple
+					< LZMA_SUBBLOCK_ALIGNMENT_MIN
+					|| coder->alignment.multiple
+					> LZMA_SUBBLOCK_ALIGNMENT_MAX)
+				return LZMA_HEADER_ERROR;
+
+			// Run-length encoder
+			//
+			// First check if there is some data pending and we
+			// have an obvious need to flush it immediatelly.
+			if (coder->rle.count > 0
+					&& (coder->rle.size
+							!= coder->options->rle
+						|| coder->subblock.size
+							% coder->rle.size)) {
+				subblock_rle_flush(coder);
+				break;
+			}
+
+			// Grab the (possibly new) RLE chunk size and
+			// validate it.
+			coder->rle.size = coder->options->rle;
+			if (coder->rle.size > LZMA_SUBBLOCK_RLE_MAX)
+				return LZMA_HEADER_ERROR;
+
+			if (coder->subblock.size != 0
+					&& coder->rle.size
+						!= LZMA_SUBBLOCK_RLE_OFF
+					&& coder->subblock.size
+						% coder->rle.size == 0) {
+
+				// Initialize coder->rle.buffer if we don't
+				// have RLE already running.
+				if (coder->rle.count == 0)
+					memcpy(coder->rle.buffer,
+							coder->subblock.data,
+							coder->rle.size);
+
+				// Test if coder->subblock.data is repeating.
+				const size_t count = coder->subblock.size
+						/ coder->rle.size;
+				if (is_repeating(coder->rle.buffer,
+						coder->rle.size,
+						coder->subblock.data, count)) {
+					if (LZMA_VLI_VALUE_MAX - count
+							< coder->rle.count)
+						return LZMA_PROG_ERROR;
+
+					coder->rle.count += count;
+					coder->subblock.size = 0;
+
+				} else if (coder->rle.count > 0) {
+					// It's not repeating or at least not
+					// with the same byte sequence as the
+					// earlier Subblock Data buffers. We
+					// have some data pending in the RLE
+					// buffer already, so do a flush.
+					// Once flushed, we will check again
+					// if the Subblock Data happens to
+					// contain a different repeating
+					// sequence.
+					subblock_rle_flush(coder);
+					break;
+				}
+			}
+		}
+
+		// If we now have some data left in coder->subblock, the RLE
+		// buffer is empty and we must write a regular Subblock Data.
+		if (coder->subblock.size > 0) {
+			assert(coder->rle.count == 0);
+			coder->tmp = coder->subblock.size - 1;
+			coder->sequence = SEQ_DATA_SIZE_0;
+			break;
+		}
+
+		// Check if we should enable Subfilter.
+		if (coder->subfilter.mode == SUB_SET) {
+			if (coder->rle.count > 0)
+				subblock_rle_flush(coder);
+			else
+				coder->sequence = SEQ_SUBFILTER_INIT;
+			break;
+		}
+
+		// Check if we have just finished Subfiltering.
+		if (coder->subfilter.mode == SUB_END_MARKER) {
+			if (coder->rle.count > 0) {
+				subblock_rle_flush(coder);
+				break;
+			}
+
+			write_byte(0x50);
+			coder->subfilter.mode = SUB_NONE;
+			if (*out_pos == out_size)
+				return LZMA_OK;
+		}
+
+		// Check if we have already written everything.
+		if (action == LZMA_FINISH && *in_pos == in_size
+				&& coder->subfilter.mode == SUB_NONE) {
+			if (coder->rle.count > 0) {
+				subblock_rle_flush(coder);
+				break;
+			}
+
+			if (coder->uncompressed_size
+					== LZMA_VLI_VALUE_UNKNOWN) {
+				// NOTE: No need to use write_byte() here
+				// since we are finishing.
+				out[*out_pos] = 0x10;
+				++*out_pos;
+			} else if (coder->uncompressed_size != 0) {
+				return LZMA_DATA_ERROR;
+			}
+
+			return LZMA_STREAM_END;
+		}
+
+		// Otherwise we have more work to do.
+		coder->sequence = SEQ_FILL;
+		break;
+
+	case SEQ_RLE_COUNT_0:
+		// Make the Data field properly aligned, but only if the data
+		// chunk to be repeated isn't extremely small. We have four
+		// bytes for Count and one byte for Size, thus the number five.
+		if (coder->rle.size >= RLE_MIN_SIZE_FOR_ALIGN
+				&& subblock_align(
+					coder, out, out_pos, out_size, 5))
+			return LZMA_OK;
+
+		assert(coder->rle.count > 0);
+
+		write_byte(0x30 | (coder->tmp & 0x0F));
+
+		coder->sequence = SEQ_RLE_COUNT_1;
+		break;
+
+	case SEQ_RLE_COUNT_1:
+		write_byte(coder->tmp >> 4);
+		coder->sequence = SEQ_RLE_COUNT_2;
+		break;
+
+	case SEQ_RLE_COUNT_2:
+		write_byte(coder->tmp >> 12);
+		coder->sequence = SEQ_RLE_COUNT_3;
+		break;
+
+	case SEQ_RLE_COUNT_3:
+		write_byte(coder->tmp >> 20);
+
+		if (coder->rle.count > REPEAT_COUNT_MAX)
+			coder->rle.count -= REPEAT_COUNT_MAX;
+		else
+			coder->rle.count = 0;
+
+		coder->sequence = SEQ_RLE_SIZE;
+		break;
+
+	case SEQ_RLE_SIZE:
+		assert(coder->rle.size >= LZMA_SUBBLOCK_RLE_MIN);
+		assert(coder->rle.size <= LZMA_SUBBLOCK_RLE_MAX);
+		write_byte(coder->rle.size - 1);
+		coder->sequence = SEQ_RLE_DATA;
+		break;
+
+	case SEQ_RLE_DATA:
+		bufcpy(coder->rle.buffer, &coder->pos, coder->rle.size,
+				out, out_pos, out_size);
+		if (coder->pos < coder->rle.size)
+			return LZMA_OK;
+
+		coder->alignment.out_pos += coder->rle.size;
+
+		coder->pos = 0;
+		coder->sequence = SEQ_FLUSH;
+		break;
+
+	case SEQ_DATA_SIZE_0:
+		// We need four bytes for the Size field.
+		if (subblock_align(coder, out, out_pos, out_size, 4))
+			return LZMA_OK;
+
+		write_byte(0x20 | (coder->tmp & 0x0F));
+		coder->sequence = SEQ_DATA_SIZE_1;
+		break;
+
+	case SEQ_DATA_SIZE_1:
+		write_byte(coder->tmp >> 4);
+		coder->sequence = SEQ_DATA_SIZE_2;
+		break;
+
+	case SEQ_DATA_SIZE_2:
+		write_byte(coder->tmp >> 12);
+		coder->sequence = SEQ_DATA_SIZE_3;
+		break;
+
+	case SEQ_DATA_SIZE_3:
+		write_byte(coder->tmp >> 20);
+		coder->sequence = SEQ_DATA;
+		break;
+
+	case SEQ_DATA:
+		bufcpy(coder->subblock.data, &coder->pos,
+				coder->subblock.size, out, out_pos, out_size);
+		if (coder->pos < coder->subblock.size)
+			return LZMA_OK;
+
+		coder->alignment.out_pos += coder->subblock.size;
+
+		coder->subblock.size = 0;
+		coder->pos = 0;
+		coder->sequence = SEQ_FLUSH;
+		break;
+
+	case SEQ_SUBFILTER_INIT: {
+		assert(coder->subblock.size == 0);
+		assert(coder->rle.count == 0);
+		assert(coder->subfilter.mode == SUB_SET);
+		assert(coder->options != NULL);
+
+		// There must be a filter specified.
+		if (coder->options->subfilter_options.id
+				== LZMA_VLI_VALUE_UNKNOWN)
+			return LZMA_HEADER_ERROR;
+
+		// Initialize a raw encoder to work as a Subfilter.
+		lzma_options_filter options[2];
+		options[0] = coder->options->subfilter_options;
+		options[1].id = LZMA_VLI_VALUE_UNKNOWN;
+
+		lzma_ret ret = lzma_raw_encoder_init(
+				&coder->subfilter.subcoder, allocator,
+				options, LZMA_VLI_VALUE_UNKNOWN, false);
+		if (ret != LZMA_OK)
+			return ret;
+
+		// Encode the Filter Flags field into a buffer. This should
+		// never fail since we have already successfully initialized
+		// the Subfilter itself. Check it still, and return
+		// LZMA_PROG_ERROR instead of whatever the ret would say.
+		ret = lzma_filter_flags_size(
+				&coder->subfilter.flags_size, options);
+		assert(ret == LZMA_OK);
+		if (ret != LZMA_OK)
+			return LZMA_PROG_ERROR;
+
+		coder->subfilter.flags = lzma_alloc(
+				coder->subfilter.flags_size, allocator);
+		if (coder->subfilter.flags == NULL)
+			return LZMA_MEM_ERROR;
+
+		// Now we have a big-enough buffer. Encode the Filter Flags.
+		// Like above, this should never fail.
+		size_t dummy = 0;
+		ret = lzma_filter_flags_encode(coder->subfilter.flags,
+				&dummy, coder->subfilter.flags_size, options);
+		assert(ret == LZMA_OK);
+		assert(dummy == coder->subfilter.flags_size);
+		if (ret != LZMA_OK || dummy != coder->subfilter.flags_size)
+			return LZMA_PROG_ERROR;
+
+		// Write a Subblock indicating a new Subfilter.
+		write_byte(0x40);
+
+		coder->options->subfilter_mode = LZMA_SUBFILTER_RUN;
+		coder->subfilter.mode = SUB_RUN;
+		coder->sequence = SEQ_SUBFILTER_FLAGS;
+	}
+
+	// Fall through
+
+	case SEQ_SUBFILTER_FLAGS:
+		// Copy the Filter Flags to the output stream.
+		bufcpy(coder->subfilter.flags, &coder->pos,
+				coder->subfilter.flags_size,
+				out, out_pos, out_size);
+		if (coder->pos < coder->subfilter.flags_size)
+			return LZMA_OK;
+
+		lzma_free(coder->subfilter.flags, allocator);
+		coder->subfilter.flags = NULL;
+
+		coder->pos = 0;
+		coder->sequence = SEQ_FILL;
+		break;
+
+	default:
+		return LZMA_PROG_ERROR;
+	}
+
+	return LZMA_OK;
+}
+
+
+static lzma_ret
+subblock_encode(lzma_coder *coder, lzma_allocator *allocator,
+		const uint8_t *restrict in, size_t *restrict in_pos,
+		size_t in_size, uint8_t *restrict out,
+		size_t *restrict out_pos, size_t out_size, lzma_action action)
+{
+	if (coder->next.code == NULL)
+		return subblock_buffer(coder, allocator, in, in_pos, in_size,
+				out, out_pos, out_size, action);
+
+	while (*out_pos < out_size
+			&& (*in_pos < in_size || action == LZMA_FINISH)) {
+		if (!coder->next_finished
+				&& coder->temp.pos == coder->temp.size) {
+			coder->temp.pos = 0;
+			coder->temp.size = 0;
+
+			const lzma_ret ret = coder->next.code(coder->next.coder,
+					allocator, in, in_pos, in_size,
+					coder->temp.buffer, &coder->temp.size,
+					LZMA_BUFFER_SIZE, action);
+			if (ret == LZMA_STREAM_END) {
+				assert(action == LZMA_FINISH);
+				coder->next_finished = true;
+			} else if (coder->temp.size == 0 || ret != LZMA_OK) {
+				return ret;
+			}
+		}
+
+		const lzma_ret ret = subblock_buffer(coder, allocator,
+				coder->temp.buffer, &coder->temp.pos,
+				coder->temp.size, out, out_pos, out_size,
+				coder->next_finished ? LZMA_FINISH : LZMA_RUN);
+		if (ret == LZMA_STREAM_END) {
+			assert(action == LZMA_FINISH);
+			assert(coder->next_finished);
+			return LZMA_STREAM_END;
+		}
+
+		if (ret != LZMA_OK)
+			return ret;
+	}
+
+	return LZMA_OK;
+}
+
+
+static void
+subblock_encoder_end(lzma_coder *coder, lzma_allocator *allocator)
+{
+	lzma_next_coder_end(&coder->next, allocator);
+	lzma_next_coder_end(&coder->subfilter.subcoder, allocator);
+	lzma_free(coder->subblock.data, allocator);
+	lzma_free(coder->subfilter.flags, allocator);
+	return;
+}
+
+
+extern lzma_ret
+lzma_subblock_encoder_init(lzma_next_coder *next, lzma_allocator *allocator,
+		const lzma_filter_info *filters)
+{
+	if (next->coder == NULL) {
+		next->coder = lzma_alloc(sizeof(lzma_coder), allocator);
+		if (next->coder == NULL)
+			return LZMA_MEM_ERROR;
+
+		next->coder->next = LZMA_NEXT_CODER_INIT;
+		next->coder->subblock.data = NULL;
+		next->coder->subblock.limit = 0;
+		next->coder->subfilter.subcoder = LZMA_NEXT_CODER_INIT;
+	} else {
+		lzma_next_coder_end(&next->coder->subfilter.subcoder,
+				allocator);
+		lzma_free(next->coder->subfilter.flags, allocator);
+	}
+
+	next->coder->subfilter.flags = NULL;
+
+	next->coder->next_finished = false;
+	next->coder->sequence = SEQ_FILL;
+	next->coder->options = filters[0].options;
+	next->coder->uncompressed_size = filters[0].uncompressed_size;
+	next->coder->pos = 0;
+
+	next->coder->alignment.in_pending = 0;
+	next->coder->alignment.in_pos = 0;
+	next->coder->alignment.out_pos = 0;
+	next->coder->subblock.size = 0;
+	next->coder->rle.count = 0;
+	next->coder->subfilter.mode = SUB_NONE;
+
+	next->coder->temp.pos = 0;
+	next->coder->temp.size = 0;
+
+	// Grab some values from the options structure if it is available.
+	size_t subblock_size_limit;
+	if (next->coder->options != NULL) {
+		if (next->coder->options->alignment
+					< LZMA_SUBBLOCK_ALIGNMENT_MIN
+				|| next->coder->options->alignment
+					> LZMA_SUBBLOCK_ALIGNMENT_MAX) {
+			subblock_encoder_end(next->coder, allocator);
+			return LZMA_HEADER_ERROR;
+		}
+		next->coder->alignment.multiple
+				= next->coder->options->alignment;
+		subblock_size_limit = next->coder->options->subblock_data_size;
+	} else {
+		next->coder->alignment.multiple
+				= LZMA_SUBBLOCK_ALIGNMENT_DEFAULT;
+		subblock_size_limit = LZMA_SUBBLOCK_DATA_SIZE_DEFAULT;
+	}
+
+	{
+		const lzma_ret ret = subblock_data_size(next->coder, allocator,
+				subblock_size_limit);
+		if (ret != LZMA_OK) {
+			subblock_encoder_end(next->coder, allocator);
+			return ret;
+		}
+	}
+
+	{
+		const lzma_ret ret = lzma_next_filter_init(&next->coder->next,
+				allocator, filters + 1);
+		if (ret != LZMA_OK) {
+			subblock_encoder_end(next->coder, allocator);
+			return ret;
+		}
+	}
+
+	next->code = &subblock_encode;
+	next->end = &subblock_encoder_end;
+
+	return LZMA_OK;
+}
diff --git a/src/liblzma/subblock/subblock_encoder.h b/src/liblzma/subblock/subblock_encoder.h
new file mode 100644
index 00000000..3ef9e2e4
--- /dev/null
+++ b/src/liblzma/subblock/subblock_encoder.h
@@ -0,0 +1,28 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       subblock_encoder.h
+/// \brief      Encoder of the Subblock filter
+//
+//  Copyright (C) 2007 Lasse Collin
+//
+//  This library is free software; you can redistribute it and/or
+//  modify it under the terms of the GNU Lesser General Public
+//  License as published by the Free Software Foundation; either
+//  version 2.1 of the License, or (at your option) any later version.
+//
+//  This library is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+//  Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#ifndef LZMA_SUBBLOCK_ENCODER_H
+#define LZMA_SUBBLOCK_ENCODER_H
+
+#include "common.h"
+
+extern lzma_ret lzma_subblock_encoder_init(lzma_next_coder *next,
+		lzma_allocator *allocator, const lzma_filter_info *filters);
+
+#endif