Imported to git.

1 files changed, 462 insertions, 0 deletions

diff --git a/src/liblzma/lz/lz_decoder.c b/src/liblzma/lz/lz_decoder.c
new file mode 100644
index 00000000..9c110dec
--- /dev/null
+++ b/src/liblzma/lz/lz_decoder.c
@@ -0,0 +1,462 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       lz_decoder.c
+/// \brief      LZ out window
+//
+//  Copyright (C) 1999-2006 Igor Pavlov
+//  Copyright (C) 2007 Lasse Collin
+//
+//  This library is free software; you can redistribute it and/or
+//  modify it under the terms of the GNU Lesser General Public
+//  License as published by the Free Software Foundation; either
+//  version 2.1 of the License, or (at your option) any later version.
+//
+//  This library is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+//  Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include "lz_decoder.h"
+
+
+/// Minimum size of allocated dictionary
+#define DICT_SIZE_MIN 8192
+
+/// When there is less than this amount of data available for decoding,
+/// it is moved to the temporary buffer which
+///   - protects from reads past the end of the buffer; and
+///   - stored the incomplete data between lzma_code() calls.
+///
+/// \note       TEMP_LIMIT must be at least as much as
+///             REQUIRED_IN_BUFFER_SIZE defined in lzma_decoder.c.
+#define TEMP_LIMIT 32
+
+// lzma_lz_decoder.dict[] must be three times the size of TEMP_LIMIT.
+// 2 * TEMP_LIMIT is used for the actual data, and the third TEMP_LIMIT
+// bytes is needed for safety to allow decode_dummy() in lzma_decoder.c
+// to read past end of the buffer. This way it should be both fast and simple.
+#if LZMA_BUFFER_SIZE < 3 * TEMP_LIMIT
+#	error LZMA_BUFFER_SIZE < 3 * TEMP_LIMIT
+#endif
+
+
+struct lzma_coder_s {
+	lzma_next_coder next;
+	lzma_lz_decoder lz;
+
+	// There are more members in this structure but they are not
+	// visible in LZ coder.
+};
+
+
+/// - Copy as much data as possible from lz->dict[] to out[].
+/// - Update *out_pos, lz->start, and lz->end accordingly.
+/// - Wrap lz-pos to the beginning of lz->dict[] if there is a danger that
+///   it may go past the end of the buffer (lz->pos >= lz->must_flush_pos).
+static inline bool
+flush(lzma_lz_decoder *restrict lz, uint8_t *restrict out,
+		size_t *restrict out_pos, size_t out_size)
+{
+	// Flush uncompressed data from the history buffer to
+	// the output buffer. This is done in two phases.
+
+	assert(lz->start <= lz->end);
+
+	// Flush if pos < start < end.
+	if (lz->pos < lz->start && lz->start < lz->end) {
+		bufcpy(lz->dict, &lz->start, lz->end, out, out_pos, out_size);
+
+		// If we reached end of the data in history buffer,
+		// wrap to the beginning.
+		if (lz->start == lz->end)
+			lz->start = 0;
+	}
+
+	// Flush if start start < pos <= end. This is not as `else' for
+	// previous `if' because the previous one may make this one true.
+	if (lz->start < lz->pos) {
+		bufcpy(lz->dict, &lz->start,
+				lz->pos, out, out_pos, out_size);
+
+		if (lz->pos >= lz->must_flush_pos) {
+			// Wrap the flushing position if we have
+			// flushed the whole history buffer.
+			if (lz->pos == lz->start)
+				lz->start = 0;
+
+			// Wrap the write position and store to lz.end
+			// how much there is new data available.
+			lz->end = lz->pos;
+			lz->pos = 0;
+			lz->is_full = true;
+		}
+	}
+
+	assert(lz->pos < lz->must_flush_pos);
+
+	return *out_pos == out_size;
+}
+
+
+/// Calculate safe value for lz->limit. If no safe value can be found,
+/// set lz->limit to zero. When flushing, only as little data will be
+/// decoded as is needed to fill the output buffer (lowers both latency
+/// and throughput).
+///
+/// \return     true if there is no space for new uncompressed data.
+///
+static inline bool
+set_limit(lzma_lz_decoder *lz, size_t out_avail, bool flushing)
+{
+	// Set the limit so that writing to dict[limit + match_max_len - 1]
+	// doesn't overwrite any unflushed data and doesn't write past the
+	// end of the dict buffer.
+	if (lz->start <= lz->pos) {
+		// We can fill the buffer from pos till the end
+		// of the dict buffer.
+		lz->limit = lz->must_flush_pos;
+	} else if (lz->pos + lz->match_max_len < lz->start) {
+		// There's some unflushed data between pos and end of the
+		// buffer. Limit so that we don't overwrite the unflushed data.
+		lz->limit = lz->start - lz->match_max_len;
+	} else {
+		// Buffer is too full.
+		lz->limit = 0;
+		return true;
+	}
+
+	// Finetune the limit a bit if it isn't zero.
+
+	assert(lz->limit > lz->pos);
+	const size_t dict_avail = lz->limit - lz->pos;
+
+	if (lz->uncompressed_size < dict_avail) {
+		// Finishing a stream that doesn't have
+		// an end of stream marker.
+		lz->limit = lz->pos + lz->uncompressed_size;
+
+	} else if (flushing && out_avail < dict_avail) {
+		// Flushing enabled, decoding only as little as needed to
+		// fill the out buffer (if there's enough input, of course).
+		lz->limit = lz->pos + out_avail;
+	}
+
+	return lz->limit == lz->pos;
+}
+
+
+/// Takes care of wrapping the data into temporary buffer when needed,
+/// and calls the actual decoder.
+///
+/// \return     true if error occurred
+///
+static inline bool
+call_process(lzma_coder *restrict coder, const uint8_t *restrict in,
+		size_t *restrict in_pos, size_t in_size)
+{
+	// It would be nice and simple if we could just give in[] to the
+	// decoder, but the requirement of zlib-like API forces us to be
+	// able to make *in_pos == in_size whenever there is enough output
+	// space. If needed, we will append a few bytes from in[] to
+	// a temporary buffer and decode enough to reach the part that
+	// was copied from in[]. Then we can continue with the real in[].
+
+	bool error;
+	const size_t dict_old_pos = coder->lz.pos;
+	const size_t in_avail = in_size - *in_pos;
+
+	if (coder->lz.temp_size + in_avail < 2 * TEMP_LIMIT) {
+		// Copy all the available input from in[] to temp[].
+		memcpy(coder->lz.temp + coder->lz.temp_size,
+				in + *in_pos, in_avail);
+		coder->lz.temp_size += in_avail;
+		*in_pos += in_avail;
+		assert(*in_pos == in_size);
+
+		// Decode as much as possible.
+		size_t temp_used = 0;
+		error = coder->lz.process(coder, coder->lz.temp, &temp_used,
+				coder->lz.temp_size, true);
+		assert(temp_used <= coder->lz.temp_size);
+
+		// Move the remaining data to the beginning of temp[].
+		coder->lz.temp_size -= temp_used;
+		memmove(coder->lz.temp, coder->lz.temp + temp_used,
+				coder->lz.temp_size);
+
+	} else if (coder->lz.temp_size > 0) {
+		// Fill temp[] unless it is already full because we aren't
+		// the last filter in the chain.
+		size_t copy_size = 0;
+		if (coder->lz.temp_size < 2 * TEMP_LIMIT) {
+			assert(*in_pos < in_size);
+			copy_size = 2 * TEMP_LIMIT - coder->lz.temp_size;
+			memcpy(coder->lz.temp + coder->lz.temp_size,
+					in + *in_pos, copy_size);
+			// NOTE: We don't update lz.temp_size or *in_pos yet.
+		}
+
+		size_t temp_used = 0;
+		error = coder->lz.process(coder, coder->lz.temp, &temp_used,
+				coder->lz.temp_size + copy_size, false);
+
+		if (temp_used < coder->lz.temp_size) {
+			// Only very little input data was consumed. Move
+			// the unprocessed data to the beginning temp[].
+			coder->lz.temp_size += copy_size - temp_used;
+			memmove(coder->lz.temp, coder->lz.temp + temp_used,
+					coder->lz.temp_size);
+			*in_pos += copy_size;
+			assert(*in_pos <= in_size);
+
+		} else {
+			// We were able to decode so much data that next time
+			// we can decode directly from in[]. That is, we can
+			// consider temp[] to be empty now.
+			*in_pos += temp_used - coder->lz.temp_size;
+			coder->lz.temp_size = 0;
+			assert(*in_pos <= in_size);
+		}
+
+	} else {
+		// Decode directly from in[].
+		error = coder->lz.process(coder, in, in_pos, in_size, false);
+		assert(*in_pos <= in_size);
+	}
+
+	assert(coder->lz.pos >= dict_old_pos);
+	if (coder->lz.uncompressed_size != LZMA_VLI_VALUE_UNKNOWN) {
+		// Update uncompressed size.
+		coder->lz.uncompressed_size -= coder->lz.pos - dict_old_pos;
+
+		// Check that End of Payload Marker hasn't been detected
+		// since it must not be present because uncompressed size
+		// is known.
+		if (coder->lz.eopm_detected)
+			error = true;
+	}
+
+	return error;
+}
+
+
+static lzma_ret
+decode_buffer(lzma_coder *coder,
+		const uint8_t *restrict in, size_t *restrict in_pos,
+		size_t in_size, uint8_t *restrict out,
+		size_t *restrict out_pos, size_t out_size,
+		bool flushing)
+{
+	bool stop = false;
+
+	while (true) {
+		// Flush from coder->lz.dict to out[].
+		flush(&coder->lz, out, out_pos, out_size);
+
+		// All done?
+		if (*out_pos == out_size
+				|| stop
+				|| coder->lz.eopm_detected
+				|| coder->lz.uncompressed_size == 0)
+			break;
+
+		// Set write limit in the dictionary.
+		if (set_limit(&coder->lz, out_size - *out_pos, flushing))
+			break;
+
+		// Decode more data.
+		if (call_process(coder, in, in_pos, in_size))
+			return LZMA_DATA_ERROR;
+
+		// Set stop to true if we must not call call_process() again
+		// during this function call.
+		// FIXME: Can this make the loop exist too early? It wouldn't
+		// cause data corruption so not a critical problem. It can
+		// happen if dictionary gets full and lz.temp still contains
+		// a few bytes data that we could decode right now.
+		if (*in_pos == in_size && coder->lz.temp_size <= TEMP_LIMIT
+				&& coder->lz.pos < coder->lz.limit)
+			stop = true;
+	}
+
+	// If we have decoded everything (EOPM detected or uncompressed_size
+	// bytes were processed) to the history buffer, and also flushed
+	// everything from the history buffer, our job is done.
+	if ((coder->lz.eopm_detected
+			|| coder->lz.uncompressed_size == 0)
+			&& coder->lz.start == coder->lz.pos)
+		return LZMA_STREAM_END;
+
+	return LZMA_OK;
+}
+
+
+extern lzma_ret
+lzma_lz_decode(lzma_coder *coder,
+		lzma_allocator *allocator lzma_attribute((unused)),
+		const uint8_t *restrict in, size_t *restrict in_pos,
+		size_t in_size, uint8_t *restrict out,
+		size_t *restrict out_pos, size_t out_size,
+		lzma_action action)
+{
+	if (coder->next.code == NULL) {
+		const lzma_ret ret = decode_buffer(coder, in, in_pos, in_size,
+				out, out_pos, out_size,
+				action == LZMA_SYNC_FLUSH);
+
+		if (*out_pos == out_size || ret == LZMA_STREAM_END) {
+			// Unread to make coder->temp[] empty. This is easy,
+			// because we know that all the data currently in
+			// coder->temp[] has been copied form in[] during this
+			// call to the decoder.
+			//
+			// If we didn't do this, we could have data left in
+			// coder->temp[] when end of stream is reached. That
+			// data could be left there from *previous* call to
+			// the decoder; in that case we wouldn't know where
+			// to put that data.
+			assert(*in_pos >= coder->lz.temp_size);
+			*in_pos -= coder->lz.temp_size;
+			coder->lz.temp_size = 0;
+		}
+
+		return ret;
+	}
+
+	// We aren't the last coder in the chain, we need to decode
+	// our input to a temporary buffer.
+	const bool flushing = action == LZMA_SYNC_FLUSH;
+	while (*out_pos < out_size) {
+		if (!coder->lz.next_finished
+				&& coder->lz.temp_size < LZMA_BUFFER_SIZE) {
+			const lzma_ret ret = coder->next.code(
+					coder->next.coder,
+					allocator, in, in_pos, in_size,
+					coder->lz.temp, &coder->lz.temp_size,
+					LZMA_BUFFER_SIZE, action);
+
+			if (ret == LZMA_STREAM_END)
+				coder->lz.next_finished = true;
+			else if (coder->lz.temp_size < LZMA_BUFFER_SIZE
+					|| ret != LZMA_OK)
+				return ret;
+		}
+
+		if (coder->lz.this_finished) {
+			if (coder->lz.temp_size != 0)
+				return LZMA_DATA_ERROR;
+
+			if (coder->lz.next_finished)
+				return LZMA_STREAM_END;
+
+			return LZMA_OK;
+		}
+
+		size_t dummy = 0;
+		const lzma_ret ret = decode_buffer(coder, NULL, &dummy, 0,
+				out, out_pos, out_size, flushing);
+
+		if (ret == LZMA_STREAM_END)
+			coder->lz.this_finished = true;
+		else if (ret != LZMA_OK)
+			return ret;
+		else if (coder->lz.next_finished && *out_pos < out_size)
+			return LZMA_DATA_ERROR;
+	}
+
+	return LZMA_OK;
+}
+
+
+/// \brief      Initializes LZ part of the LZMA decoder or Inflate
+///
+/// \param      history_size    Number of bytes the LZ out window is
+///                             supposed keep available from the output
+///                             history.
+/// \param      match_max_len   Number of bytes a single decoding loop
+///                             can advance the write position (lz->pos)
+///                             in the history buffer (lz->dict).
+///
+/// \note       This function is called by LZMA decoder and Inflate init()s.
+///             It's up to those functions allocate *lz and initialize it
+///             with LZMA_LZ_DECODER_INIT.
+extern lzma_ret
+lzma_lz_decoder_reset(lzma_lz_decoder *lz, lzma_allocator *allocator,
+		bool (*process)(lzma_coder *restrict coder,
+			const uint8_t *restrict in, size_t *restrict in_pos,
+			size_t in_size, bool has_safe_buffer),
+		lzma_vli uncompressed_size,
+		size_t history_size, size_t match_max_len)
+{
+	// Set uncompressed size.
+	lz->uncompressed_size = uncompressed_size;
+
+	// Limit the history size to roughly sane values. This is primarily
+	// to prevent integer overflows.
+	if (history_size > UINT32_MAX / 2)
+		return LZMA_HEADER_ERROR;
+
+	// Store the value actually requested. We use it for sanity checks
+	// when repeating data from the history buffer.
+	lz->requested_size = history_size;
+
+	// Avoid tiny history buffer sizes for performance reasons.
+	// TODO: Test if this actually helps...
+	if (history_size < DICT_SIZE_MIN)
+		history_size = DICT_SIZE_MIN;
+
+	// The real size of the history buffer is a bit bigger than
+	// requested by our caller. This allows us to do some optimizations,
+	// which help not only speed but simplicity of the code; specifically,
+	// we can make sure that there is always at least match_max_len
+	// bytes immediatelly available for writing without a need to wrap
+	// the history buffer.
+	const size_t dict_real_size = history_size + 2 * match_max_len + 1;
+
+	// Reallocate memory if needed.
+	if (history_size != lz->size || match_max_len != lz->match_max_len) {
+		// Destroy the old buffer.
+		lzma_lz_decoder_end(lz, allocator);
+
+		lz->size = history_size;
+		lz->match_max_len = match_max_len;
+		lz->must_flush_pos = history_size + match_max_len + 1;
+
+		lz->dict = lzma_alloc(dict_real_size, allocator);
+		if (lz->dict == NULL)
+			return LZMA_MEM_ERROR;
+	}
+
+	// Clean up the buffers to make it very sure that there are
+	// no information leaks when multiple steams are decoded
+	// with the same decoder structures.
+	memzero(lz->dict, dict_real_size);
+	memzero(lz->temp, LZMA_BUFFER_SIZE);
+
+	// Reset the variables so that lz_get_byte(lz, 0) will return '\0'.
+	lz->pos = 0;
+	lz->start = 0;
+	lz->end = dict_real_size;
+	lz->is_full = false;
+	lz->eopm_detected = false;
+	lz->next_finished = false;
+	lz->this_finished = false;
+
+	// Set the process function pointer.
+	lz->process = process;
+
+	return LZMA_OK;
+}
+
+
+extern void
+lzma_lz_decoder_end(lzma_lz_decoder *lz, lzma_allocator *allocator)
+{
+	lzma_free(lz->dict, allocator);
+	lz->dict = NULL;
+	lz->size = 0;
+	lz->match_max_len = 0;
+	return;
+}