1 files changed, 481 insertions, 0 deletions
diff --git a/src/liblzma/lz/lz_encoder.c b/src/liblzma/lz/lz_encoder.c
new file mode 100644
index 00000000..bc38cae2
--- /dev/null
+++ b/src/liblzma/lz/lz_encoder.c
@@ -0,0 +1,481 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file       lz_encoder.c
+/// \brief      LZ in window
+//
+//  Copyright (C) 1999-2006 Igor Pavlov
+//  Copyright (C) 2007 Lasse Collin
+//
+//  This library is free software; you can redistribute it and/or
+//  modify it under the terms of the GNU Lesser General Public
+//  License as published by the Free Software Foundation; either
+//  version 2.1 of the License, or (at your option) any later version.
+//
+//  This library is distributed in the hope that it will be useful,
+//  but WITHOUT ANY WARRANTY; without even the implied warranty of
+//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+//  Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include "lz_encoder_private.h"
+
+// Hash Chains
+#ifdef HAVE_HC3
+#	include "hc3.h"
+#endif
+#ifdef HAVE_HC4
+#	include "hc4.h"
+#endif
+
+// Binary Trees
+#ifdef HAVE_BT2
+#	include "bt2.h"
+#endif
+#ifdef HAVE_BT3
+#	include "bt3.h"
+#endif
+#ifdef HAVE_BT4
+#	include "bt4.h"
+#endif
+
+
+/// This is needed in two places so provide a macro.
+#define get_cyclic_buffer_size(history_size) ((history_size) + 1)
+
+
+/// Calculate certain match finder properties and validate the calculated
+/// values. This is as its own function, because *num_items is needed to
+/// calculate memory requirements in common/memory.c.
+extern uint32_t
+lzma_lz_encoder_hash_properties(lzma_match_finder match_finder,
+		uint32_t history_size, uint32_t *restrict hash_mask,
+		uint32_t *restrict hash_size_sum, uint32_t *restrict num_items)
+{
+	uint32_t fix_hash_size;
+	uint32_t sons;
+
+	switch (match_finder) {
+#ifdef HAVE_HC3
+	case LZMA_MF_HC3:
+		fix_hash_size = LZMA_HC3_FIX_HASH_SIZE;
+		sons = 1;
+		break;
+#endif
+#ifdef HAVE_HC4
+	case LZMA_MF_HC4:
+		fix_hash_size = LZMA_HC4_FIX_HASH_SIZE;
+		sons = 1;
+		break;
+#endif
+#ifdef HAVE_BT2
+	case LZMA_MF_BT2:
+		fix_hash_size = LZMA_BT2_FIX_HASH_SIZE;
+		sons = 2;
+		break;
+#endif
+#ifdef HAVE_BT3
+	case LZMA_MF_BT3:
+		fix_hash_size = LZMA_BT3_FIX_HASH_SIZE;
+		sons = 2;
+		break;
+#endif
+#ifdef HAVE_BT4
+	case LZMA_MF_BT4:
+		fix_hash_size = LZMA_BT4_FIX_HASH_SIZE;
+		sons = 2;
+		break;
+#endif
+	default:
+		return true;
+	}
+
+	uint32_t hs;
+
+#ifdef HAVE_LZMA_BT2
+	if (match_finder == LZMA_BT2) {
+		// NOTE: hash_mask is not used by the BT2 match finder,
+		// but it is initialized just in case.
+		hs = LZMA_BT2_HASH_SIZE;
+		*hash_mask = 0;
+	} else
+#endif
+	{
+		hs = history_size - 1;
+		hs |= (hs >> 1);
+		hs |= (hs >> 2);
+		hs |= (hs >> 4);
+		hs |= (hs >> 8);
+		hs >>= 1;
+		hs |= 0xFFFF;
+
+		if (hs > (UINT32_C(1) << 24)) {
+			if (match_finder == LZMA_MF_HC4
+					|| match_finder == LZMA_MF_BT4)
+				hs >>= 1;
+			else
+				hs = (1 << 24) - 1;
+		}
+
+		*hash_mask = hs;
+		++hs;
+	}
+
+	*hash_size_sum = hs + fix_hash_size;
+
+	*num_items = *hash_size_sum
+			+ get_cyclic_buffer_size(history_size) * sons;
+
+	return false;
+}
+
+
+extern lzma_ret
+lzma_lz_encoder_reset(lzma_lz_encoder *lz, lzma_allocator *allocator,
+		bool (*process)(lzma_coder *coder, uint8_t *restrict out,
+			size_t *restrict out_pos, size_t out_size),
+		lzma_vli uncompressed_size,
+		size_t history_size, size_t additional_buffer_before,
+		size_t match_max_len, size_t additional_buffer_after,
+		lzma_match_finder match_finder, uint32_t match_finder_cycles,
+		const uint8_t *preset_dictionary,
+		size_t preset_dictionary_size)
+{
+	// Set uncompressed size.
+	lz->uncompressed_size = uncompressed_size;
+
+	///////////////
+	// In Window //
+	///////////////
+
+	// Validate history size.
+	if (history_size < LZMA_DICTIONARY_SIZE_MIN
+			|| history_size > LZMA_DICTIONARY_SIZE_MAX) {
+		lzma_lz_encoder_end(lz, allocator);
+		return LZMA_HEADER_ERROR;
+	}
+
+	assert(history_size <= MAX_VAL_FOR_NORMALIZE - 256);
+	assert(LZMA_DICTIONARY_SIZE_MAX <= MAX_VAL_FOR_NORMALIZE - 256);
+
+	// Calculate the size of the history buffer to allocate.
+	// TODO: Get a reason for magic constant of 256.
+	const size_t size_reserv = (history_size + additional_buffer_before
+			+ match_max_len + additional_buffer_after) / 2 + 256;
+
+	lz->keep_size_before = history_size + additional_buffer_before;
+	lz->keep_size_after = match_max_len + additional_buffer_after;
+
+	const size_t buffer_size = lz->keep_size_before + lz->keep_size_after
+			+ size_reserv;
+
+	// Allocate history buffer if its size has changed.
+	if (buffer_size != lz->size) {
+		lzma_free(lz->buffer, allocator);
+		lz->buffer = lzma_alloc(buffer_size, allocator);
+		if (lz->buffer == NULL) {
+			lzma_lz_encoder_end(lz, allocator);
+			return LZMA_MEM_ERROR;
+		}
+	}
+
+	// Allocation successful. Store the new size and calculate
+	// must_move_pos.
+	lz->size = buffer_size;
+	lz->must_move_pos = lz->size - lz->keep_size_after;
+
+	// Reset in window variables.
+	lz->offset = 0;
+	lz->read_pos = 0;
+	lz->read_limit = 0;
+	lz->write_pos = 0;
+	lz->stream_end_was_reached = false;
+
+
+	//////////////////
+	// Match Finder //
+	//////////////////
+
+	// Validate match_finder, set function pointers and a few match
+	// finder specific variables.
+	switch (match_finder) {
+#ifdef HAVE_HC3
+	case LZMA_MF_HC3:
+		lz->get_matches = &lzma_hc3_get_matches;
+		lz->skip = &lzma_hc3_skip;
+		lz->cut_value = 8 + (match_max_len >> 2);
+		break;
+#endif
+#ifdef HAVE_HC4
+	case LZMA_MF_HC4:
+		lz->get_matches = &lzma_hc4_get_matches;
+		lz->skip = &lzma_hc4_skip;
+		lz->cut_value = 8 + (match_max_len >> 2);
+		break;
+#endif
+#ifdef HAVE_BT2
+	case LZMA_MF_BT2:
+		lz->get_matches = &lzma_bt2_get_matches;
+		lz->skip = &lzma_bt2_skip;
+		lz->cut_value = 16 + (match_max_len >> 1);
+		break;
+#endif
+#ifdef HAVE_BT3
+	case LZMA_MF_BT3:
+		lz->get_matches = &lzma_bt3_get_matches;
+		lz->skip = &lzma_bt3_skip;
+		lz->cut_value = 16 + (match_max_len >> 1);
+		break;
+#endif
+#ifdef HAVE_BT4
+	case LZMA_MF_BT4:
+		lz->get_matches = &lzma_bt4_get_matches;
+		lz->skip = &lzma_bt4_skip;
+		lz->cut_value = 16 + (match_max_len >> 1);
+		break;
+#endif
+	default:
+		lzma_lz_encoder_end(lz, allocator);
+		return LZMA_HEADER_ERROR;
+	}
+
+	// Check if we have been requested to use a non-default cut_value.
+	if (match_finder_cycles > 0)
+		lz->cut_value = match_finder_cycles;
+
+	lz->match_max_len = match_max_len;
+	lz->cyclic_buffer_size = get_cyclic_buffer_size(history_size);
+
+	uint32_t hash_size_sum;
+	uint32_t num_items;
+	if (lzma_lz_encoder_hash_properties(match_finder, history_size,
+			&lz->hash_mask, &hash_size_sum, &num_items)) {
+		lzma_lz_encoder_end(lz, allocator);
+		return LZMA_HEADER_ERROR;
+	}
+
+	if (num_items != lz->num_items) {
+#if UINT32_MAX >= SIZE_MAX / 4
+		// Check for integer overflow. (Huge dictionaries are not
+		// possible on 32-bit CPU.)
+		if (num_items > SIZE_MAX / sizeof(uint32_t)) {
+			lzma_lz_encoder_end(lz, allocator);
+			return LZMA_MEM_ERROR;
+		}
+#endif
+
+		const size_t size_in_bytes
+				= (size_t)(num_items) * sizeof(uint32_t);
+
+		lzma_free(lz->hash, allocator);
+		lz->hash = lzma_alloc(size_in_bytes, allocator);
+		if (lz->hash == NULL) {
+			lzma_lz_encoder_end(lz, allocator);
+			return LZMA_MEM_ERROR;
+		}
+
+		lz->num_items = num_items;
+	}
+
+	lz->son = lz->hash + hash_size_sum;
+
+	// Reset the hash table to empty hash values.
+	{
+		uint32_t *restrict items = lz->hash;
+
+		for (uint32_t i = 0; i < hash_size_sum; ++i)
+			items[i] = EMPTY_HASH_VALUE;
+	}
+
+	lz->cyclic_buffer_pos = 0;
+
+	// Because zero is used as empty hash value, make the first byte
+	// appear at buffer[1 - offset].
+	++lz->offset;
+
+	// If we are using a preset dictionary, read it now.
+	// TODO: This isn't implemented yet so return LZMA_HEADER_ERROR.
+	if (preset_dictionary != NULL && preset_dictionary_size > 0) {
+		lzma_lz_encoder_end(lz, allocator);
+		return LZMA_HEADER_ERROR;
+	}
+
+	// Set the process function pointer.
+	lz->process = process;
+
+	return LZMA_OK;
+}
+
+
+extern void
+lzma_lz_encoder_end(lzma_lz_encoder *lz, lzma_allocator *allocator)
+{
+	lzma_free(lz->hash, allocator);
+	lz->hash = NULL;
+	lz->num_items = 0;
+
+	lzma_free(lz->buffer, allocator);
+	lz->buffer = NULL;
+	lz->size = 0;
+
+	return;
+}
+
+
+/// \brief      Moves the data in the input window to free space for new data
+///
+/// lz->buffer is a sliding input window, which keeps lz->keep_size_before
+/// bytes of input history available all the time. Now and then we need to
+/// "slide" the buffer to make space for the new data to the end of the
+/// buffer. At the same time, data older than keep_size_before is dropped.
+///
+static void
+move_window(lzma_lz_encoder *lz)
+{
+	// buffer[move_offset] will become buffer[0].
+	assert(lz->read_pos > lz->keep_size_after);
+	size_t move_offset = lz->read_pos - lz->keep_size_before;
+
+	// We need one additional byte, since move_pos() moves on 1 byte.
+	// TODO: Clean up? At least document more.
+	if (move_offset > 0)
+		--move_offset;
+
+	assert(lz->write_pos > move_offset);
+	const size_t move_size = lz->write_pos - move_offset;
+
+	assert(move_offset + move_size <= lz->size);
+
+	memmove(lz->buffer, lz->buffer + move_offset, move_size);
+
+	lz->offset += move_offset;
+	lz->read_pos -= move_offset;
+	lz->read_limit -= move_offset;
+	lz->write_pos -= move_offset;
+
+	return;
+}
+
+
+/// \brief      Tries to fill the input window (lz->buffer)
+///
+/// If we are the last encoder in the chain, our input data is in in[].
+/// Otherwise we call the next filter in the chain to process in[] and
+/// write its output to lz->buffer.
+///
+/// This function must not be called once it has returned LZMA_STREAM_END.
+///
+static lzma_ret
+fill_window(lzma_coder *coder, lzma_allocator *allocator, const uint8_t *in,
+		size_t *in_pos, size_t in_size, lzma_action action)
+{
+	assert(coder->lz.read_pos <= coder->lz.write_pos);
+	lzma_ret ret;
+
+	// Move the sliding window if needed.
+	if (coder->lz.read_pos >= coder->lz.must_move_pos)
+		move_window(&coder->lz);
+
+	if (coder->next.code == NULL) {
+		// Not using a filter, simply memcpy() as much as possible.
+		bufcpy(in, in_pos, in_size, coder->lz.buffer,
+				&coder->lz.write_pos, coder->lz.size);
+
+		if (action == LZMA_FINISH && *in_pos == in_size)
+			ret = LZMA_STREAM_END;
+		else
+			ret = LZMA_OK;
+
+	} else {
+		ret = coder->next.code(coder->next.coder, allocator,
+				in, in_pos, in_size,
+				coder->lz.buffer, &coder->lz.write_pos,
+				coder->lz.size, action);
+	}
+
+	// If end of stream has been reached, we allow the encoder to process
+	// all the input (that is, read_pos is allowed to reach write_pos).
+	// Otherwise we keep keep_size_after bytes available as prebuffer.
+	if (ret == LZMA_STREAM_END) {
+		coder->lz.stream_end_was_reached = true;
+		coder->lz.read_limit = coder->lz.write_pos;
+
+	} else if (coder->lz.write_pos > coder->lz.keep_size_after) {
+		// This needs to be done conditionally, because if we got
+		// only little new input, there may be too little input
+		// to do any encoding yet.
+		coder->lz.read_limit = coder->lz.write_pos
+				- coder->lz.keep_size_after;
+	}
+
+	return ret;
+}
+
+
+extern lzma_ret
+lzma_lz_encode(lzma_coder *coder, lzma_allocator *allocator,
+		const uint8_t *restrict in, size_t *restrict in_pos,
+		size_t in_size,
+		uint8_t *restrict out, size_t *restrict out_pos,
+		size_t out_size, lzma_action action)
+{
+	while (*out_pos < out_size
+			&& (*in_pos < in_size || action == LZMA_FINISH)) {
+		// Fill the input window if there is no more usable data.
+		if (!coder->lz.stream_end_was_reached && coder->lz.read_pos
+				>= coder->lz.read_limit) {
+			const lzma_ret ret = fill_window(coder, allocator,
+					in, in_pos, in_size, action);
+			if (ret != LZMA_OK && ret != LZMA_STREAM_END)
+				return ret;
+		}
+
+		// Encode
+		if (coder->lz.process(coder, out, out_pos, out_size))
+			return LZMA_STREAM_END;
+	}
+
+	return LZMA_OK;
+}
+
+
+/// \brief      Normalizes hash values
+///
+/// lzma_lz_normalize is called when lz->pos hits MAX_VAL_FOR_NORMALIZE,
+/// which currently happens once every 2 GiB of input data (to be exact,
+/// after the first 2 GiB it happens once every 2 GiB minus dictionary_size
+/// bytes). lz->pos is incremented by lzma_lz_move_pos().
+///
+/// lz->hash contains big amount of offsets relative to lz->buffer.
+/// The offsets are stored as uint32_t, which is the only reasonable
+/// datatype for these offsets; uint64_t would waste far too much RAM
+/// and uint16_t would limit the dictionary to 64 KiB (far too small).
+///
+/// When compressing files over 2 GiB, lz->buffer needs to be moved forward
+/// to avoid integer overflows. We scan the lz->hash array and fix every
+/// value to match the updated lz->buffer.
+extern void
+lzma_lz_encoder_normalize(lzma_lz_encoder *lz)
+{
+	const uint32_t subvalue = lz->read_pos - lz->cyclic_buffer_size;
+	assert(subvalue <= INT32_MAX);
+
+	{
+		const uint32_t num_items = lz->num_items;
+		uint32_t *restrict items = lz->hash;
+
+		for (uint32_t i = 0; i < num_items; ++i) {
+			// If the distance is greater than the dictionary
+			// size, we can simply mark the item as empty.
+			if (items[i] <= subvalue)
+				items[i] = EMPTY_HASH_VALUE;
+			else
+				items[i] -= subvalue;
+		}
+	}
+
+	// Update offset to match the new locations.
+	lz->offset -= subvalue;
+
+	return;
+}