src/liblzma/lz/lz_encoder.c

///////////////////////////////////////////////////////////////////////////////
//
/// \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 bool
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)
{
	lz->sequence = SEQ_START;
	lz->uncompressed_size = uncompressed_size;
	lz->temp_size = 0;

	///////////////
	// 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.
	lz->size = buffer_size;

	// Reset in window variables.
	lz->offset = 0;
	lz->read_pos = 0;
	lz->read_limit = 0;
	lz->write_pos = 0;
	lz->pending = 0;


	//////////////////
	// 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);

	// Move the sliding window if needed.
	if (coder->lz.read_pos >= coder->lz.size - coder->lz.keep_size_after)
		move_window(&coder->lz);

	size_t in_used;
	lzma_ret ret;
	if (coder->next.code == NULL) {
		// Not using a filter, simply memcpy() as much as possible.
		in_used = bufcpy(in, in_pos, in_size, coder->lz.buffer,
				&coder->lz.write_pos, coder->lz.size);

		if (action != LZMA_RUN && *in_pos == in_size)
			ret = LZMA_STREAM_END;
		else
			ret = LZMA_OK;

	} else {
		const size_t in_start = *in_pos;
		ret = coder->next.code(coder->next.coder, allocator,
				in, in_pos, in_size,
				coder->lz.buffer, &coder->lz.write_pos,
				coder->lz.size, action);
		in_used = *in_pos - in_start;
	}

	assert(coder->lz.uncompressed_size >= in_used);
	if (coder->lz.uncompressed_size != LZMA_VLI_VALUE_UNKNOWN)
		coder->lz.uncompressed_size -= in_used;

	// If end of stream has been reached or flushing completed, 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) {
		assert(*in_pos == in_size);
		coder->lz.read_limit = coder->lz.write_pos;
		ret = LZMA_OK;

		switch (action) {
		case LZMA_SYNC_FLUSH:
			coder->lz.sequence = SEQ_FLUSH;
			break;

		case LZMA_FINISH:
			coder->lz.sequence = SEQ_FINISH;
			break;

		default:
			assert(0);
			ret = LZMA_PROG_ERROR;
			break;
		}

	} 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;
	}

	// Switch to finishing mode if we have got all the input data.
	// lzma_lz_encode() won't return LZMA_STREAM_END until LZMA_FINISH
	// is used.
	//
	// NOTE: When LZMA is used together with other filters, it is possible
	// that coder->lz.sequence gets set to SEQ_FINISH before the next
	// encoder has returned LZMA_STREAM_END. This is somewhat ugly, but
	// works correctly, because the next encoder cannot have any more
	// output left to be produced. If it had, then our known Uncompressed
	// Size would be invalid, which would mean that we have a bad bug.
// 	if (ret == LZMA_OK && coder->lz.uncompressed_size == 0)
// 		coder->lz.sequence = SEQ_FINISH;
	// The above breaks normal encoding with known uncompressed size
	// if input chunk size is a multiple of uncompressed size. Commenting
	// the above out breaks LZMA_SYNC_FLUSH at end of stream whose
	// uncompressed size is known. Support for encoding with known
	// uncompressed may get dropped completely so I won't fix this now.

	// Restart the match finder after finished LZMA_SYNC_FLUSH.
	if (coder->lz.pending > 0
			&& coder->lz.read_pos < coder->lz.read_limit) {
		// Match finder may update coder->pending and expects it to
		// start from zero, so use a temporary variable.
		const size_t pending = coder->lz.pending;
		coder->lz.pending = 0;

		// Rewind read_pos so that the match finder can hash
		// the pending bytes.
		assert(coder->lz.read_pos >= pending);
		coder->lz.read_pos -= pending;
		coder->lz.skip(&coder->lz, pending);
	}

	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)
{
	// Flush the temporary output buffer, which may be used when the
	// encoder runs of out of space in primary output buffer (the out,
	// *out_pos, and out_size variables).
	if (coder->lz.temp_size > 0) {
		const size_t out_avail = out_size - *out_pos;
		if (out_avail < coder->lz.temp_size) {
			// Cannot copy everything. Copy as much as possible
			// and move the data in lz.temp to the beginning of
			// that buffer.
			memcpy(out + *out_pos, coder->lz.temp, out_avail);
			*out_pos += out_avail;
			memmove(coder->lz.temp, coder->lz.temp + out_avail,
					coder->lz.temp_size - out_avail);
			coder->lz.temp_size -= out_avail;
			return LZMA_OK;
		}

		// We can copy everything from coder->lz.temp to out.
		memcpy(out + *out_pos, coder->lz.temp, coder->lz.temp_size);
		*out_pos += coder->lz.temp_size;
		coder->lz.temp_size = 0;
	}

	switch (coder->lz.sequence) {
	case SEQ_START:
		assert(coder->lz.read_pos == coder->lz.write_pos);

		// If there is no new input data and LZMA_SYNC_FLUSH is used
		// immediatelly after previous LZMA_SYNC_FLUSH finished or
		// at the very beginning of the input stream, we return
		// LZMA_STREAM_END immediatelly. Writing a flush marker
		// to the very beginning of the stream or right after previous
		// flush marker is not allowed by the LZMA stream format.
		if (*in_pos == in_size && action == LZMA_SYNC_FLUSH)
			return LZMA_STREAM_END;

		coder->lz.sequence = SEQ_RUN;
		break;

	case SEQ_FLUSH_END:
		// During an earlier call to this function, flushing was
		// otherwise finished except some data was left pending
		// in coder->lz.buffer. Now we have copied all that data
		// to the output buffer and can return LZMA_STREAM_END.
		coder->lz.sequence = SEQ_START;
		assert(action == LZMA_SYNC_FLUSH);
		return LZMA_STREAM_END;

	case SEQ_END:
		// This is like the above flushing case, but for finishing
		// the encoding.
		//
		// NOTE: action is not necesarily LZMA_FINISH; it can
		// be LZMA_RUN or LZMA_SYNC_FLUSH too in case it is used
		// at the end of the stream with known Uncompressed Size.
		return action != LZMA_RUN ? LZMA_STREAM_END : LZMA_OK;

	default:
		break;
	}

	while (*out_pos < out_size
			&& (*in_pos < in_size || action != LZMA_RUN)) {
		// Read more data to coder->lz.buffer if needed.
		if (coder->lz.sequence == SEQ_RUN
				&& coder->lz.read_pos >= coder->lz.read_limit)
			return_if_error(fill_window(coder, allocator,
					in, in_pos, in_size, action));

		// Encode
		if (coder->lz.process(coder, out, out_pos, out_size)) {
			if (coder->lz.sequence == SEQ_FLUSH) {
				assert(action == LZMA_SYNC_FLUSH);
				if (coder->lz.temp_size == 0) {
					// Flushing was finished successfully.
					coder->lz.sequence = SEQ_START;
				} else {
					// Flushing was otherwise finished,
					// except that some data was left
					// into coder->lz.buffer.
					coder->lz.sequence = SEQ_FLUSH_END;
				}
			} else {
				// NOTE: action may be LZMA_RUN here in case
				// Uncompressed Size is known and we have
				// processed all the data already.
				assert(coder->lz.sequence == SEQ_FINISH);
				coder->lz.sequence = SEQ_END;
			}

			return action != LZMA_RUN && coder->lz.temp_size == 0
					? LZMA_STREAM_END : LZMA_OK;
		}
	}

	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;
}