Restoring authorship annotation for <thegeorg@yandex-team.ru>. Commit 1 of 2.

7 files changed, 2403 insertions, 2403 deletions

diff --git a/contrib/libs/xz/liblzma/lz/lz_decoder.c b/contrib/libs/xz/liblzma/lz/lz_decoder.c
index c7086440bf..4e73992585 100644
--- a/contrib/libs/xz/liblzma/lz/lz_decoder.c
+++ b/contrib/libs/xz/liblzma/lz/lz_decoder.c
@@ -1,306 +1,306 @@
-///////////////////////////////////////////////////////////////////////////////
-//
-/// \file       lz_decoder.c
-/// \brief      LZ out window
-///
-//  Authors:    Igor Pavlov
-//              Lasse Collin
-//
-//  This file has been put into the public domain.
-//  You can do whatever you want with this file.
-//
-///////////////////////////////////////////////////////////////////////////////
-
-// liblzma supports multiple LZ77-based filters. The LZ part is shared
-// between these filters. The LZ code takes care of dictionary handling
-// and passing the data between filters in the chain. The filter-specific
-// part decodes from the input buffer to the dictionary.
-
-
-#include "lz_decoder.h"
-
-
-typedef struct {
-	/// Dictionary (history buffer)
-	lzma_dict dict;
-
-	/// The actual LZ-based decoder e.g. LZMA
-	lzma_lz_decoder lz;
-
-	/// Next filter in the chain, if any. Note that LZMA and LZMA2 are
-	/// only allowed as the last filter, but the long-range filter in
-	/// future can be in the middle of the chain.
-	lzma_next_coder next;
-
-	/// True if the next filter in the chain has returned LZMA_STREAM_END.
-	bool next_finished;
-
-	/// True if the LZ decoder (e.g. LZMA) has detected end of payload
-	/// marker. This may become true before next_finished becomes true.
-	bool this_finished;
-
-	/// Temporary buffer needed when the LZ-based 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
-	/// LZ-based decoder.
-	struct {
-		size_t pos;
-		size_t size;
-		uint8_t buffer[LZMA_BUFFER_SIZE];
-	} temp;
-} lzma_coder;
-
-
-static void
-lz_decoder_reset(lzma_coder *coder)
-{
-	coder->dict.pos = 0;
-	coder->dict.full = 0;
-	coder->dict.buf[coder->dict.size - 1] = '\0';
-	coder->dict.need_reset = false;
-	return;
-}
-
-
-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)
-{
-	while (true) {
-		// Wrap the dictionary if needed.
-		if (coder->dict.pos == coder->dict.size)
-			coder->dict.pos = 0;
-
-		// Store the current dictionary position. It is needed to know
-		// where to start copying to the out[] buffer.
-		const size_t dict_start = coder->dict.pos;
-
-		// Calculate how much we allow coder->lz.code() to decode.
-		// It must not decode past the end of the dictionary
-		// buffer, and we don't want it to decode more than is
-		// actually needed to fill the out[] buffer.
-		coder->dict.limit = coder->dict.pos
-				+ my_min(out_size - *out_pos,
-					coder->dict.size - coder->dict.pos);
-
-		// Call the coder->lz.code() to do the actual decoding.
-		const lzma_ret ret = coder->lz.code(
-				coder->lz.coder, &coder->dict,
-				in, in_pos, in_size);
-
-		// Copy the decoded data from the dictionary to the out[]
-		// buffer.
-		const size_t copy_size = coder->dict.pos - dict_start;
-		assert(copy_size <= out_size - *out_pos);
-		memcpy(out + *out_pos, coder->dict.buf + dict_start,
-				copy_size);
-		*out_pos += copy_size;
-
-		// Reset the dictionary if so requested by coder->lz.code().
-		if (coder->dict.need_reset) {
-			lz_decoder_reset(coder);
-
-			// Since we reset dictionary, we don't check if
-			// dictionary became full.
-			if (ret != LZMA_OK || *out_pos == out_size)
-				return ret;
-		} else {
-			// Return if everything got decoded or an error
-			// occurred, or if there's no more data to decode.
-			//
-			// Note that detecting if there's something to decode
-			// is done by looking if dictionary become full
-			// instead of looking if *in_pos == in_size. This
-			// is because it is possible that all the input was
-			// consumed already but some data is pending to be
-			// written to the dictionary.
-			if (ret != LZMA_OK || *out_pos == out_size
-					|| coder->dict.pos < coder->dict.size)
-				return ret;
-		}
-	}
-}
-
-
-static lzma_ret
-lz_decode(void *coder_ptr,
-		const 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_coder *coder = coder_ptr;
-
-	if (coder->next.code == NULL)
-		return decode_buffer(coder, in, in_pos, in_size,
-				out, out_pos, out_size);
-
-	// We aren't the last coder in the chain, we need to decode
-	// our input to a temporary buffer.
-	while (*out_pos < out_size) {
-		// Fill the temporary buffer if it is empty.
-		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 (ret != LZMA_OK || coder->temp.size == 0)
-				return ret;
-		}
-
-		if (coder->this_finished) {
-			if (coder->temp.size != 0)
-				return LZMA_DATA_ERROR;
-
-			if (coder->next_finished)
-				return LZMA_STREAM_END;
-
-			return LZMA_OK;
-		}
-
-		const lzma_ret ret = decode_buffer(coder, coder->temp.buffer,
-				&coder->temp.pos, coder->temp.size,
-				out, out_pos, out_size);
-
-		if (ret == LZMA_STREAM_END)
-			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
-lz_decoder_end(void *coder_ptr, const lzma_allocator *allocator)
-{
-	lzma_coder *coder = coder_ptr;
-
-	lzma_next_end(&coder->next, allocator);
-	lzma_free(coder->dict.buf, allocator);
-
-	if (coder->lz.end != NULL)
-		coder->lz.end(coder->lz.coder, allocator);
-	else
-		lzma_free(coder->lz.coder, allocator);
-
-	lzma_free(coder, allocator);
-	return;
-}
-
-
-extern lzma_ret
-lzma_lz_decoder_init(lzma_next_coder *next, const lzma_allocator *allocator,
-		const lzma_filter_info *filters,
-		lzma_ret (*lz_init)(lzma_lz_decoder *lz,
-			const lzma_allocator *allocator, const void *options,
-			lzma_lz_options *lz_options))
-{
-	// Allocate the base structure if it isn't already allocated.
-	lzma_coder *coder = next->coder;
-	if (coder == NULL) {
-		coder = lzma_alloc(sizeof(lzma_coder), allocator);
-		if (coder == NULL)
-			return LZMA_MEM_ERROR;
-
-		next->coder = coder;
-		next->code = &lz_decode;
-		next->end = &lz_decoder_end;
-
-		coder->dict.buf = NULL;
-		coder->dict.size = 0;
-		coder->lz = LZMA_LZ_DECODER_INIT;
-		coder->next = LZMA_NEXT_CODER_INIT;
-	}
-
-	// Allocate and initialize the LZ-based decoder. It will also give
-	// us the dictionary size.
-	lzma_lz_options lz_options;
-	return_if_error(lz_init(&coder->lz, allocator,
-			filters[0].options, &lz_options));
-
-	// If the dictionary size is very small, increase it to 4096 bytes.
-	// This is to prevent constant wrapping of the dictionary, which
-	// would slow things down. The downside is that since we don't check
-	// separately for the real dictionary size, we may happily accept
-	// corrupt files.
-	if (lz_options.dict_size < 4096)
-		lz_options.dict_size = 4096;
-
-	// Make dictionary size a multipe of 16. Some LZ-based decoders like
-	// LZMA use the lowest bits lzma_dict.pos to know the alignment of the
-	// data. Aligned buffer is also good when memcpying from the
-	// dictionary to the output buffer, since applications are
-	// recommended to give aligned buffers to liblzma.
-	//
-	// Avoid integer overflow.
-	if (lz_options.dict_size > SIZE_MAX - 15)
-		return LZMA_MEM_ERROR;
-
-	lz_options.dict_size = (lz_options.dict_size + 15) & ~((size_t)(15));
-
-	// Allocate and initialize the dictionary.
-	if (coder->dict.size != lz_options.dict_size) {
-		lzma_free(coder->dict.buf, allocator);
-		coder->dict.buf
-				= lzma_alloc(lz_options.dict_size, allocator);
-		if (coder->dict.buf == NULL)
-			return LZMA_MEM_ERROR;
-
-		coder->dict.size = lz_options.dict_size;
-	}
-
-	lz_decoder_reset(next->coder);
-
-	// Use the preset dictionary if it was given to us.
-	if (lz_options.preset_dict != NULL
-			&& lz_options.preset_dict_size > 0) {
-		// If the preset dictionary is bigger than the actual
-		// dictionary, copy only the tail.
-		const size_t copy_size = my_min(lz_options.preset_dict_size,
-				lz_options.dict_size);
-		const size_t offset = lz_options.preset_dict_size - copy_size;
-		memcpy(coder->dict.buf, lz_options.preset_dict + offset,
-				copy_size);
-		coder->dict.pos = copy_size;
-		coder->dict.full = copy_size;
-	}
-
-	// Miscellaneous initializations
-	coder->next_finished = false;
-	coder->this_finished = false;
-	coder->temp.pos = 0;
-	coder->temp.size = 0;
-
-	// Initialize the next filter in the chain, if any.
-	return lzma_next_filter_init(&coder->next, allocator, filters + 1);
-}
-
-
-extern uint64_t
-lzma_lz_decoder_memusage(size_t dictionary_size)
-{
-	return sizeof(lzma_coder) + (uint64_t)(dictionary_size);
-}
-
-
-extern void
-lzma_lz_decoder_uncompressed(void *coder_ptr, lzma_vli uncompressed_size)
-{
-	lzma_coder *coder = coder_ptr;
-	coder->lz.set_uncompressed(coder->lz.coder, uncompressed_size);
-}
+/////////////////////////////////////////////////////////////////////////////// 
+// 
+/// \file       lz_decoder.c 
+/// \brief      LZ out window 
+/// 
+//  Authors:    Igor Pavlov 
+//              Lasse Collin 
+// 
+//  This file has been put into the public domain. 
+//  You can do whatever you want with this file. 
+// 
+/////////////////////////////////////////////////////////////////////////////// 
+ 
+// liblzma supports multiple LZ77-based filters. The LZ part is shared 
+// between these filters. The LZ code takes care of dictionary handling 
+// and passing the data between filters in the chain. The filter-specific 
+// part decodes from the input buffer to the dictionary. 
+ 
+ 
+#include "lz_decoder.h" 
+ 
+ 
+typedef struct { 
+	/// Dictionary (history buffer) 
+	lzma_dict dict; 
+ 
+	/// The actual LZ-based decoder e.g. LZMA 
+	lzma_lz_decoder lz; 
+ 
+	/// Next filter in the chain, if any. Note that LZMA and LZMA2 are 
+	/// only allowed as the last filter, but the long-range filter in 
+	/// future can be in the middle of the chain. 
+	lzma_next_coder next; 
+ 
+	/// True if the next filter in the chain has returned LZMA_STREAM_END. 
+	bool next_finished; 
+ 
+	/// True if the LZ decoder (e.g. LZMA) has detected end of payload 
+	/// marker. This may become true before next_finished becomes true. 
+	bool this_finished; 
+ 
+	/// Temporary buffer needed when the LZ-based 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 
+	/// LZ-based decoder. 
+	struct { 
+		size_t pos; 
+		size_t size; 
+		uint8_t buffer[LZMA_BUFFER_SIZE]; 
+	} temp; 
+} lzma_coder; 
+ 
+ 
+static void 
+lz_decoder_reset(lzma_coder *coder) 
+{ 
+	coder->dict.pos = 0; 
+	coder->dict.full = 0; 
+	coder->dict.buf[coder->dict.size - 1] = '\0'; 
+	coder->dict.need_reset = false; 
+	return; 
+} 
+ 
+ 
+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) 
+{ 
+	while (true) { 
+		// Wrap the dictionary if needed. 
+		if (coder->dict.pos == coder->dict.size) 
+			coder->dict.pos = 0; 
+ 
+		// Store the current dictionary position. It is needed to know 
+		// where to start copying to the out[] buffer. 
+		const size_t dict_start = coder->dict.pos; 
+ 
+		// Calculate how much we allow coder->lz.code() to decode. 
+		// It must not decode past the end of the dictionary 
+		// buffer, and we don't want it to decode more than is 
+		// actually needed to fill the out[] buffer. 
+		coder->dict.limit = coder->dict.pos 
+				+ my_min(out_size - *out_pos, 
+					coder->dict.size - coder->dict.pos); 
+ 
+		// Call the coder->lz.code() to do the actual decoding. 
+		const lzma_ret ret = coder->lz.code( 
+				coder->lz.coder, &coder->dict, 
+				in, in_pos, in_size); 
+ 
+		// Copy the decoded data from the dictionary to the out[] 
+		// buffer. 
+		const size_t copy_size = coder->dict.pos - dict_start; 
+		assert(copy_size <= out_size - *out_pos); 
+		memcpy(out + *out_pos, coder->dict.buf + dict_start, 
+				copy_size); 
+		*out_pos += copy_size; 
+ 
+		// Reset the dictionary if so requested by coder->lz.code(). 
+		if (coder->dict.need_reset) { 
+			lz_decoder_reset(coder); 
+ 
+			// Since we reset dictionary, we don't check if 
+			// dictionary became full. 
+			if (ret != LZMA_OK || *out_pos == out_size) 
+				return ret; 
+		} else { 
+			// Return if everything got decoded or an error 
+			// occurred, or if there's no more data to decode. 
+			// 
+			// Note that detecting if there's something to decode 
+			// is done by looking if dictionary become full 
+			// instead of looking if *in_pos == in_size. This 
+			// is because it is possible that all the input was 
+			// consumed already but some data is pending to be 
+			// written to the dictionary. 
+			if (ret != LZMA_OK || *out_pos == out_size 
+					|| coder->dict.pos < coder->dict.size) 
+				return ret; 
+		} 
+	} 
+} 
+ 
+ 
+static lzma_ret 
+lz_decode(void *coder_ptr, 
+		const 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_coder *coder = coder_ptr; 
+ 
+	if (coder->next.code == NULL) 
+		return decode_buffer(coder, in, in_pos, in_size, 
+				out, out_pos, out_size); 
+ 
+	// We aren't the last coder in the chain, we need to decode 
+	// our input to a temporary buffer. 
+	while (*out_pos < out_size) { 
+		// Fill the temporary buffer if it is empty. 
+		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 (ret != LZMA_OK || coder->temp.size == 0) 
+				return ret; 
+		} 
+ 
+		if (coder->this_finished) { 
+			if (coder->temp.size != 0) 
+				return LZMA_DATA_ERROR; 
+ 
+			if (coder->next_finished) 
+				return LZMA_STREAM_END; 
+ 
+			return LZMA_OK; 
+		} 
+ 
+		const lzma_ret ret = decode_buffer(coder, coder->temp.buffer, 
+				&coder->temp.pos, coder->temp.size, 
+				out, out_pos, out_size); 
+ 
+		if (ret == LZMA_STREAM_END) 
+			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 
+lz_decoder_end(void *coder_ptr, const lzma_allocator *allocator) 
+{ 
+	lzma_coder *coder = coder_ptr; 
+ 
+	lzma_next_end(&coder->next, allocator); 
+	lzma_free(coder->dict.buf, allocator); 
+ 
+	if (coder->lz.end != NULL) 
+		coder->lz.end(coder->lz.coder, allocator); 
+	else 
+		lzma_free(coder->lz.coder, allocator); 
+ 
+	lzma_free(coder, allocator); 
+	return; 
+} 
+ 
+ 
+extern lzma_ret 
+lzma_lz_decoder_init(lzma_next_coder *next, const lzma_allocator *allocator, 
+		const lzma_filter_info *filters, 
+		lzma_ret (*lz_init)(lzma_lz_decoder *lz, 
+			const lzma_allocator *allocator, const void *options, 
+			lzma_lz_options *lz_options)) 
+{ 
+	// Allocate the base structure if it isn't already allocated. 
+	lzma_coder *coder = next->coder; 
+	if (coder == NULL) { 
+		coder = lzma_alloc(sizeof(lzma_coder), allocator); 
+		if (coder == NULL) 
+			return LZMA_MEM_ERROR; 
+ 
+		next->coder = coder; 
+		next->code = &lz_decode; 
+		next->end = &lz_decoder_end; 
+ 
+		coder->dict.buf = NULL; 
+		coder->dict.size = 0; 
+		coder->lz = LZMA_LZ_DECODER_INIT; 
+		coder->next = LZMA_NEXT_CODER_INIT; 
+	} 
+ 
+	// Allocate and initialize the LZ-based decoder. It will also give 
+	// us the dictionary size. 
+	lzma_lz_options lz_options; 
+	return_if_error(lz_init(&coder->lz, allocator, 
+			filters[0].options, &lz_options)); 
+ 
+	// If the dictionary size is very small, increase it to 4096 bytes. 
+	// This is to prevent constant wrapping of the dictionary, which 
+	// would slow things down. The downside is that since we don't check 
+	// separately for the real dictionary size, we may happily accept 
+	// corrupt files. 
+	if (lz_options.dict_size < 4096) 
+		lz_options.dict_size = 4096; 
+ 
+	// Make dictionary size a multipe of 16. Some LZ-based decoders like 
+	// LZMA use the lowest bits lzma_dict.pos to know the alignment of the 
+	// data. Aligned buffer is also good when memcpying from the 
+	// dictionary to the output buffer, since applications are 
+	// recommended to give aligned buffers to liblzma. 
+	// 
+	// Avoid integer overflow. 
+	if (lz_options.dict_size > SIZE_MAX - 15) 
+		return LZMA_MEM_ERROR; 
+ 
+	lz_options.dict_size = (lz_options.dict_size + 15) & ~((size_t)(15)); 
+ 
+	// Allocate and initialize the dictionary. 
+	if (coder->dict.size != lz_options.dict_size) { 
+		lzma_free(coder->dict.buf, allocator); 
+		coder->dict.buf 
+				= lzma_alloc(lz_options.dict_size, allocator); 
+		if (coder->dict.buf == NULL) 
+			return LZMA_MEM_ERROR; 
+ 
+		coder->dict.size = lz_options.dict_size; 
+	} 
+ 
+	lz_decoder_reset(next->coder); 
+ 
+	// Use the preset dictionary if it was given to us. 
+	if (lz_options.preset_dict != NULL 
+			&& lz_options.preset_dict_size > 0) { 
+		// If the preset dictionary is bigger than the actual 
+		// dictionary, copy only the tail. 
+		const size_t copy_size = my_min(lz_options.preset_dict_size, 
+				lz_options.dict_size); 
+		const size_t offset = lz_options.preset_dict_size - copy_size; 
+		memcpy(coder->dict.buf, lz_options.preset_dict + offset, 
+				copy_size); 
+		coder->dict.pos = copy_size; 
+		coder->dict.full = copy_size; 
+	} 
+ 
+	// Miscellaneous initializations 
+	coder->next_finished = false; 
+	coder->this_finished = false; 
+	coder->temp.pos = 0; 
+	coder->temp.size = 0; 
+ 
+	// Initialize the next filter in the chain, if any. 
+	return lzma_next_filter_init(&coder->next, allocator, filters + 1); 
+} 
+ 
+ 
+extern uint64_t 
+lzma_lz_decoder_memusage(size_t dictionary_size) 
+{ 
+	return sizeof(lzma_coder) + (uint64_t)(dictionary_size); 
+} 
+ 
+ 
+extern void 
+lzma_lz_decoder_uncompressed(void *coder_ptr, lzma_vli uncompressed_size) 
+{ 
+	lzma_coder *coder = coder_ptr; 
+	coder->lz.set_uncompressed(coder->lz.coder, uncompressed_size); 
+} 
diff --git a/contrib/libs/xz/liblzma/lz/lz_decoder.h b/contrib/libs/xz/liblzma/lz/lz_decoder.h
index 754ccf37c6..63cf912257 100644
--- a/contrib/libs/xz/liblzma/lz/lz_decoder.h
+++ b/contrib/libs/xz/liblzma/lz/lz_decoder.h
@@ -1,234 +1,234 @@
-///////////////////////////////////////////////////////////////////////////////
-//
-/// \file       lz_decoder.h
-/// \brief      LZ out window
-///
-//  Authors:    Igor Pavlov
-//              Lasse Collin
-//
-//  This file has been put into the public domain.
-//  You can do whatever you want with this file.
-//
-///////////////////////////////////////////////////////////////////////////////
-
-#ifndef LZMA_LZ_DECODER_H
-#define LZMA_LZ_DECODER_H
-
-#include "common.h"
-
-
-typedef struct {
-	/// Pointer to the dictionary buffer. It can be an allocated buffer
-	/// internal to liblzma, or it can a be a buffer given by the
-	/// application when in single-call mode (not implemented yet).
-	uint8_t *buf;
-
-	/// Write position in dictionary. The next byte will be written to
-	/// buf[pos].
-	size_t pos;
-
-	/// Indicates how full the dictionary is. This is used by
-	/// dict_is_distance_valid() to detect corrupt files that would
-	/// read beyond the beginning of the dictionary.
-	size_t full;
-
-	/// Write limit
-	size_t limit;
-
-	/// Size of the dictionary
-	size_t size;
-
-	/// True when dictionary should be reset before decoding more data.
-	bool need_reset;
-
-} lzma_dict;
-
-
-typedef struct {
-	size_t dict_size;
-	const uint8_t *preset_dict;
-	size_t preset_dict_size;
-} lzma_lz_options;
-
-
-typedef struct {
-	/// Data specific to the LZ-based decoder
-	void *coder;
-
-	/// Function to decode from in[] to *dict
-	lzma_ret (*code)(void *coder,
-			lzma_dict *restrict dict, const uint8_t *restrict in,
-			size_t *restrict in_pos, size_t in_size);
-
-	void (*reset)(void *coder, const void *options);
-
-	/// Set the uncompressed size
-	void (*set_uncompressed)(void *coder, lzma_vli uncompressed_size);
-
-	/// Free allocated resources
-	void (*end)(void *coder, const lzma_allocator *allocator);
-
-} lzma_lz_decoder;
-
-
-#define LZMA_LZ_DECODER_INIT \
-	(lzma_lz_decoder){ \
-		.coder = NULL, \
-		.code = NULL, \
-		.reset = NULL, \
-		.set_uncompressed = NULL, \
-		.end = NULL, \
-	}
-
-
-extern lzma_ret lzma_lz_decoder_init(lzma_next_coder *next,
-		const lzma_allocator *allocator,
-		const lzma_filter_info *filters,
-		lzma_ret (*lz_init)(lzma_lz_decoder *lz,
-			const lzma_allocator *allocator, const void *options,
-			lzma_lz_options *lz_options));
-
-extern uint64_t lzma_lz_decoder_memusage(size_t dictionary_size);
-
-extern void lzma_lz_decoder_uncompressed(
-		void *coder, lzma_vli uncompressed_size);
-
-
-//////////////////////
-// Inline functions //
-//////////////////////
-
-/// Get a byte from the history buffer.
-static inline uint8_t
-dict_get(const lzma_dict *const dict, const uint32_t distance)
-{
-	return dict->buf[dict->pos - distance - 1
-			+ (distance < dict->pos ? 0 : dict->size)];
-}
-
-
-/// Test if dictionary is empty.
-static inline bool
-dict_is_empty(const lzma_dict *const dict)
-{
-	return dict->full == 0;
-}
-
-
-/// Validate the match distance
-static inline bool
-dict_is_distance_valid(const lzma_dict *const dict, const size_t distance)
-{
-	return dict->full > distance;
-}
-
-
-/// Repeat *len bytes at distance.
-static inline bool
-dict_repeat(lzma_dict *dict, uint32_t distance, uint32_t *len)
-{
-	// Don't write past the end of the dictionary.
-	const size_t dict_avail = dict->limit - dict->pos;
-	uint32_t left = my_min(dict_avail, *len);
-	*len -= left;
-
-	// Repeat a block of data from the history. Because memcpy() is faster
-	// than copying byte by byte in a loop, the copying process gets split
-	// into three cases.
-	if (distance < left) {
-		// Source and target areas overlap, thus we can't use
-		// memcpy() nor even memmove() safely.
-		do {
-			dict->buf[dict->pos] = dict_get(dict, distance);
-			++dict->pos;
-		} while (--left > 0);
-
-	} else if (distance < dict->pos) {
-		// The easiest and fastest case
-		memcpy(dict->buf + dict->pos,
-				dict->buf + dict->pos - distance - 1,
-				left);
-		dict->pos += left;
-
-	} else {
-		// The bigger the dictionary, the more rare this
-		// case occurs. We need to "wrap" the dict, thus
-		// we might need two memcpy() to copy all the data.
-		assert(dict->full == dict->size);
-		const uint32_t copy_pos
-				= dict->pos - distance - 1 + dict->size;
-		uint32_t copy_size = dict->size - copy_pos;
-
-		if (copy_size < left) {
-			memmove(dict->buf + dict->pos, dict->buf + copy_pos,
-					copy_size);
-			dict->pos += copy_size;
-			copy_size = left - copy_size;
-			memcpy(dict->buf + dict->pos, dict->buf, copy_size);
-			dict->pos += copy_size;
-		} else {
-			memmove(dict->buf + dict->pos, dict->buf + copy_pos,
-					left);
-			dict->pos += left;
-		}
-	}
-
-	// Update how full the dictionary is.
-	if (dict->full < dict->pos)
-		dict->full = dict->pos;
-
-	return unlikely(*len != 0);
-}
-
-
-/// Puts one byte into the dictionary. Returns true if the dictionary was
-/// already full and the byte couldn't be added.
-static inline bool
-dict_put(lzma_dict *dict, uint8_t byte)
-{
-	if (unlikely(dict->pos == dict->limit))
-		return true;
-
-	dict->buf[dict->pos++] = byte;
-
-	if (dict->pos > dict->full)
-		dict->full = dict->pos;
-
-	return false;
-}
-
-
-/// Copies arbitrary amount of data into the dictionary.
-static inline void
-dict_write(lzma_dict *restrict dict, const uint8_t *restrict in,
-		size_t *restrict in_pos, size_t in_size,
-		size_t *restrict left)
-{
-	// NOTE: If we are being given more data than the size of the
-	// dictionary, it could be possible to optimize the LZ decoder
-	// so that not everything needs to go through the dictionary.
-	// This shouldn't be very common thing in practice though, and
-	// the slowdown of one extra memcpy() isn't bad compared to how
-	// much time it would have taken if the data were compressed.
-
-	if (in_size - *in_pos > *left)
-		in_size = *in_pos + *left;
-
-	*left -= lzma_bufcpy(in, in_pos, in_size,
-			dict->buf, &dict->pos, dict->limit);
-
-	if (dict->pos > dict->full)
-		dict->full = dict->pos;
-
-	return;
-}
-
-
-static inline void
-dict_reset(lzma_dict *dict)
-{
-	dict->need_reset = true;
-	return;
-}
-
-#endif
+/////////////////////////////////////////////////////////////////////////////// 
+// 
+/// \file       lz_decoder.h 
+/// \brief      LZ out window 
+/// 
+//  Authors:    Igor Pavlov 
+//              Lasse Collin 
+// 
+//  This file has been put into the public domain. 
+//  You can do whatever you want with this file. 
+// 
+/////////////////////////////////////////////////////////////////////////////// 
+ 
+#ifndef LZMA_LZ_DECODER_H 
+#define LZMA_LZ_DECODER_H 
+ 
+#include "common.h" 
+ 
+ 
+typedef struct { 
+	/// Pointer to the dictionary buffer. It can be an allocated buffer 
+	/// internal to liblzma, or it can a be a buffer given by the 
+	/// application when in single-call mode (not implemented yet). 
+	uint8_t *buf; 
+ 
+	/// Write position in dictionary. The next byte will be written to 
+	/// buf[pos]. 
+	size_t pos; 
+ 
+	/// Indicates how full the dictionary is. This is used by 
+	/// dict_is_distance_valid() to detect corrupt files that would 
+	/// read beyond the beginning of the dictionary. 
+	size_t full; 
+ 
+	/// Write limit 
+	size_t limit; 
+ 
+	/// Size of the dictionary 
+	size_t size; 
+ 
+	/// True when dictionary should be reset before decoding more data. 
+	bool need_reset; 
+ 
+} lzma_dict; 
+ 
+ 
+typedef struct { 
+	size_t dict_size; 
+	const uint8_t *preset_dict; 
+	size_t preset_dict_size; 
+} lzma_lz_options; 
+ 
+ 
+typedef struct { 
+	/// Data specific to the LZ-based decoder 
+	void *coder; 
+ 
+	/// Function to decode from in[] to *dict 
+	lzma_ret (*code)(void *coder, 
+			lzma_dict *restrict dict, const uint8_t *restrict in, 
+			size_t *restrict in_pos, size_t in_size); 
+ 
+	void (*reset)(void *coder, const void *options); 
+ 
+	/// Set the uncompressed size 
+	void (*set_uncompressed)(void *coder, lzma_vli uncompressed_size); 
+ 
+	/// Free allocated resources 
+	void (*end)(void *coder, const lzma_allocator *allocator); 
+ 
+} lzma_lz_decoder; 
+ 
+ 
+#define LZMA_LZ_DECODER_INIT \ 
+	(lzma_lz_decoder){ \ 
+		.coder = NULL, \ 
+		.code = NULL, \ 
+		.reset = NULL, \ 
+		.set_uncompressed = NULL, \ 
+		.end = NULL, \ 
+	} 
+ 
+ 
+extern lzma_ret lzma_lz_decoder_init(lzma_next_coder *next, 
+		const lzma_allocator *allocator, 
+		const lzma_filter_info *filters, 
+		lzma_ret (*lz_init)(lzma_lz_decoder *lz, 
+			const lzma_allocator *allocator, const void *options, 
+			lzma_lz_options *lz_options)); 
+ 
+extern uint64_t lzma_lz_decoder_memusage(size_t dictionary_size); 
+ 
+extern void lzma_lz_decoder_uncompressed( 
+		void *coder, lzma_vli uncompressed_size); 
+ 
+ 
+////////////////////// 
+// Inline functions // 
+////////////////////// 
+ 
+/// Get a byte from the history buffer. 
+static inline uint8_t 
+dict_get(const lzma_dict *const dict, const uint32_t distance) 
+{ 
+	return dict->buf[dict->pos - distance - 1 
+			+ (distance < dict->pos ? 0 : dict->size)]; 
+} 
+ 
+ 
+/// Test if dictionary is empty. 
+static inline bool 
+dict_is_empty(const lzma_dict *const dict) 
+{ 
+	return dict->full == 0; 
+} 
+ 
+ 
+/// Validate the match distance 
+static inline bool 
+dict_is_distance_valid(const lzma_dict *const dict, const size_t distance) 
+{ 
+	return dict->full > distance; 
+} 
+ 
+ 
+/// Repeat *len bytes at distance. 
+static inline bool 
+dict_repeat(lzma_dict *dict, uint32_t distance, uint32_t *len) 
+{ 
+	// Don't write past the end of the dictionary. 
+	const size_t dict_avail = dict->limit - dict->pos; 
+	uint32_t left = my_min(dict_avail, *len); 
+	*len -= left; 
+ 
+	// Repeat a block of data from the history. Because memcpy() is faster 
+	// than copying byte by byte in a loop, the copying process gets split 
+	// into three cases. 
+	if (distance < left) { 
+		// Source and target areas overlap, thus we can't use 
+		// memcpy() nor even memmove() safely. 
+		do { 
+			dict->buf[dict->pos] = dict_get(dict, distance); 
+			++dict->pos; 
+		} while (--left > 0); 
+ 
+	} else if (distance < dict->pos) { 
+		// The easiest and fastest case 
+		memcpy(dict->buf + dict->pos, 
+				dict->buf + dict->pos - distance - 1, 
+				left); 
+		dict->pos += left; 
+ 
+	} else { 
+		// The bigger the dictionary, the more rare this 
+		// case occurs. We need to "wrap" the dict, thus 
+		// we might need two memcpy() to copy all the data. 
+		assert(dict->full == dict->size); 
+		const uint32_t copy_pos 
+				= dict->pos - distance - 1 + dict->size; 
+		uint32_t copy_size = dict->size - copy_pos; 
+ 
+		if (copy_size < left) { 
+			memmove(dict->buf + dict->pos, dict->buf + copy_pos, 
+					copy_size); 
+			dict->pos += copy_size; 
+			copy_size = left - copy_size; 
+			memcpy(dict->buf + dict->pos, dict->buf, copy_size); 
+			dict->pos += copy_size; 
+		} else { 
+			memmove(dict->buf + dict->pos, dict->buf + copy_pos, 
+					left); 
+			dict->pos += left; 
+		} 
+	} 
+ 
+	// Update how full the dictionary is. 
+	if (dict->full < dict->pos) 
+		dict->full = dict->pos; 
+ 
+	return unlikely(*len != 0); 
+} 
+ 
+ 
+/// Puts one byte into the dictionary. Returns true if the dictionary was 
+/// already full and the byte couldn't be added. 
+static inline bool 
+dict_put(lzma_dict *dict, uint8_t byte) 
+{ 
+	if (unlikely(dict->pos == dict->limit)) 
+		return true; 
+ 
+	dict->buf[dict->pos++] = byte; 
+ 
+	if (dict->pos > dict->full) 
+		dict->full = dict->pos; 
+ 
+	return false; 
+} 
+ 
+ 
+/// Copies arbitrary amount of data into the dictionary. 
+static inline void 
+dict_write(lzma_dict *restrict dict, const uint8_t *restrict in, 
+		size_t *restrict in_pos, size_t in_size, 
+		size_t *restrict left) 
+{ 
+	// NOTE: If we are being given more data than the size of the 
+	// dictionary, it could be possible to optimize the LZ decoder 
+	// so that not everything needs to go through the dictionary. 
+	// This shouldn't be very common thing in practice though, and 
+	// the slowdown of one extra memcpy() isn't bad compared to how 
+	// much time it would have taken if the data were compressed. 
+ 
+	if (in_size - *in_pos > *left) 
+		in_size = *in_pos + *left; 
+ 
+	*left -= lzma_bufcpy(in, in_pos, in_size, 
+			dict->buf, &dict->pos, dict->limit); 
+ 
+	if (dict->pos > dict->full) 
+		dict->full = dict->pos; 
+ 
+	return; 
+} 
+ 
+ 
+static inline void 
+dict_reset(lzma_dict *dict) 
+{ 
+	dict->need_reset = true; 
+	return; 
+} 
+ 
+#endif 
diff --git a/contrib/libs/xz/liblzma/lz/lz_encoder.c b/contrib/libs/xz/liblzma/lz/lz_encoder.c
index 9a74b7c47c..0fa72bbf18 100644
--- a/contrib/libs/xz/liblzma/lz/lz_encoder.c
+++ b/contrib/libs/xz/liblzma/lz/lz_encoder.c
@@ -1,616 +1,616 @@
-///////////////////////////////////////////////////////////////////////////////
-//
-/// \file       lz_encoder.c
-/// \brief      LZ in window
-///
-//  Authors:    Igor Pavlov
-//              Lasse Collin
-//
-//  This file has been put into the public domain.
-//  You can do whatever you want with this file.
-//
-///////////////////////////////////////////////////////////////////////////////
-
-#include "lz_encoder.h"
-#include "lz_encoder_hash.h"
-
-// See lz_encoder_hash.h. This is a bit hackish but avoids making
-// endianness a conditional in makefiles.
-#if defined(WORDS_BIGENDIAN) && !defined(HAVE_SMALL)
-#	include "lz_encoder_hash_table.h"
-#endif
-
-#include "memcmplen.h"
-
-
-typedef struct {
-	/// LZ-based encoder e.g. LZMA
-	lzma_lz_encoder lz;
-
-	/// History buffer and match finder
-	lzma_mf mf;
-
-	/// Next coder in the chain
-	lzma_next_coder next;
-} lzma_coder;
-
-
-/// \brief      Moves the data in the input window to free space for new data
-///
-/// mf->buffer is a sliding input window, which keeps mf->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_mf *mf)
-{
-	// Align the move to a multiple of 16 bytes. Some LZ-based encoders
-	// like LZMA use the lowest bits of mf->read_pos to know the
-	// alignment of the uncompressed data. We also get better speed
-	// for memmove() with aligned buffers.
-	assert(mf->read_pos > mf->keep_size_before);
-	const uint32_t move_offset
-		= (mf->read_pos - mf->keep_size_before) & ~UINT32_C(15);
-
-	assert(mf->write_pos > move_offset);
-	const size_t move_size = mf->write_pos - move_offset;
-
-	assert(move_offset + move_size <= mf->size);
-
-	memmove(mf->buffer, mf->buffer + move_offset, move_size);
-
-	mf->offset += move_offset;
-	mf->read_pos -= move_offset;
-	mf->read_limit -= move_offset;
-	mf->write_pos -= move_offset;
-
-	return;
-}
-
-
-/// \brief      Tries to fill the input window (mf->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 mf->buffer.
-///
-/// This function must not be called once it has returned LZMA_STREAM_END.
-///
-static lzma_ret
-fill_window(lzma_coder *coder, const lzma_allocator *allocator,
-		const uint8_t *in, size_t *in_pos, size_t in_size,
-		lzma_action action)
-{
-	assert(coder->mf.read_pos <= coder->mf.write_pos);
-
-	// Move the sliding window if needed.
-	if (coder->mf.read_pos >= coder->mf.size - coder->mf.keep_size_after)
-		move_window(&coder->mf);
-
-	// Maybe this is ugly, but lzma_mf uses uint32_t for most things
-	// (which I find cleanest), but we need size_t here when filling
-	// the history window.
-	size_t write_pos = coder->mf.write_pos;
-	lzma_ret ret;
-	if (coder->next.code == NULL) {
-		// Not using a filter, simply memcpy() as much as possible.
-		lzma_bufcpy(in, in_pos, in_size, coder->mf.buffer,
-				&write_pos, coder->mf.size);
-
-		ret = action != LZMA_RUN && *in_pos == in_size
-				? LZMA_STREAM_END : LZMA_OK;
-
-	} else {
-		ret = coder->next.code(coder->next.coder, allocator,
-				in, in_pos, in_size,
-				coder->mf.buffer, &write_pos,
-				coder->mf.size, action);
-	}
-
-	coder->mf.write_pos = write_pos;
-
-	// Silence Valgrind. lzma_memcmplen() can read extra bytes
-	// and Valgrind will give warnings if those bytes are uninitialized
-	// because Valgrind cannot see that the values of the uninitialized
-	// bytes are eventually ignored.
-	memzero(coder->mf.buffer + write_pos, LZMA_MEMCMPLEN_EXTRA);
-
-	// 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);
-		ret = LZMA_OK;
-		coder->mf.action = action;
-		coder->mf.read_limit = coder->mf.write_pos;
-
-	} else if (coder->mf.write_pos > coder->mf.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->mf.read_limit = coder->mf.write_pos
-				- coder->mf.keep_size_after;
-	}
-
-	// Restart the match finder after finished LZMA_SYNC_FLUSH.
-	if (coder->mf.pending > 0
-			&& coder->mf.read_pos < coder->mf.read_limit) {
-		// Match finder may update coder->pending and expects it to
-		// start from zero, so use a temporary variable.
-		const uint32_t pending = coder->mf.pending;
-		coder->mf.pending = 0;
-
-		// Rewind read_pos so that the match finder can hash
-		// the pending bytes.
-		assert(coder->mf.read_pos >= pending);
-		coder->mf.read_pos -= pending;
-
-		// Call the skip function directly instead of using
-		// mf_skip(), since we don't want to touch mf->read_ahead.
-		coder->mf.skip(&coder->mf, pending);
-	}
-
-	return ret;
-}
-
-
-static lzma_ret
-lz_encode(void *coder_ptr, const 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)
-{
-	lzma_coder *coder = coder_ptr;
-
-	while (*out_pos < out_size
-			&& (*in_pos < in_size || action != LZMA_RUN)) {
-		// Read more data to coder->mf.buffer if needed.
-		if (coder->mf.action == LZMA_RUN && coder->mf.read_pos
-				>= coder->mf.read_limit)
-			return_if_error(fill_window(coder, allocator,
-					in, in_pos, in_size, action));
-
-		// Encode
-		const lzma_ret ret = coder->lz.code(coder->lz.coder,
-				&coder->mf, out, out_pos, out_size);
-		if (ret != LZMA_OK) {
-			// Setting this to LZMA_RUN for cases when we are
-			// flushing. It doesn't matter when finishing or if
-			// an error occurred.
-			coder->mf.action = LZMA_RUN;
-			return ret;
-		}
-	}
-
-	return LZMA_OK;
-}
-
-
-static bool
-lz_encoder_prepare(lzma_mf *mf, const lzma_allocator *allocator,
-		const lzma_lz_options *lz_options)
-{
-	// For now, the dictionary size is limited to 1.5 GiB. This may grow
-	// in the future if needed, but it needs a little more work than just
-	// changing this check.
-	if (lz_options->dict_size < LZMA_DICT_SIZE_MIN
-			|| lz_options->dict_size
-				> (UINT32_C(1) << 30) + (UINT32_C(1) << 29)
-			|| lz_options->nice_len > lz_options->match_len_max)
-		return true;
-
-	mf->keep_size_before = lz_options->before_size + lz_options->dict_size;
-
-	mf->keep_size_after = lz_options->after_size
-			+ lz_options->match_len_max;
-
-	// To avoid constant memmove()s, allocate some extra space. Since
-	// memmove()s become more expensive when the size of the buffer
-	// increases, we reserve more space when a large dictionary is
-	// used to make the memmove() calls rarer.
-	//
-	// This works with dictionaries up to about 3 GiB. If bigger
-	// dictionary is wanted, some extra work is needed:
-	//   - Several variables in lzma_mf have to be changed from uint32_t
-	//     to size_t.
-	//   - Memory usage calculation needs something too, e.g. use uint64_t
-	//     for mf->size.
-	uint32_t reserve = lz_options->dict_size / 2;
-	if (reserve > (UINT32_C(1) << 30))
-		reserve /= 2;
-
-	reserve += (lz_options->before_size + lz_options->match_len_max
-			+ lz_options->after_size) / 2 + (UINT32_C(1) << 19);
-
-	const uint32_t old_size = mf->size;
-	mf->size = mf->keep_size_before + reserve + mf->keep_size_after;
-
-	// Deallocate the old history buffer if it exists but has different
-	// size than what is needed now.
-	if (mf->buffer != NULL && old_size != mf->size) {
-		lzma_free(mf->buffer, allocator);
-		mf->buffer = NULL;
-	}
-
-	// Match finder options
-	mf->match_len_max = lz_options->match_len_max;
-	mf->nice_len = lz_options->nice_len;
-
-	// cyclic_size has to stay smaller than 2 Gi. Note that this doesn't
-	// mean limiting dictionary size to less than 2 GiB. With a match
-	// finder that uses multibyte resolution (hashes start at e.g. every
-	// fourth byte), cyclic_size would stay below 2 Gi even when
-	// dictionary size is greater than 2 GiB.
-	//
-	// It would be possible to allow cyclic_size >= 2 Gi, but then we
-	// would need to be careful to use 64-bit types in various places
-	// (size_t could do since we would need bigger than 32-bit address
-	// space anyway). It would also require either zeroing a multigigabyte
-	// buffer at initialization (waste of time and RAM) or allow
-	// normalization in lz_encoder_mf.c to access uninitialized
-	// memory to keep the code simpler. The current way is simple and
-	// still allows pretty big dictionaries, so I don't expect these
-	// limits to change.
-	mf->cyclic_size = lz_options->dict_size + 1;
-
-	// Validate the match finder ID and setup the function pointers.
-	switch (lz_options->match_finder) {
-#ifdef HAVE_MF_HC3
-	case LZMA_MF_HC3:
-		mf->find = &lzma_mf_hc3_find;
-		mf->skip = &lzma_mf_hc3_skip;
-		break;
-#endif
-#ifdef HAVE_MF_HC4
-	case LZMA_MF_HC4:
-		mf->find = &lzma_mf_hc4_find;
-		mf->skip = &lzma_mf_hc4_skip;
-		break;
-#endif
-#ifdef HAVE_MF_BT2
-	case LZMA_MF_BT2:
-		mf->find = &lzma_mf_bt2_find;
-		mf->skip = &lzma_mf_bt2_skip;
-		break;
-#endif
-#ifdef HAVE_MF_BT3
-	case LZMA_MF_BT3:
-		mf->find = &lzma_mf_bt3_find;
-		mf->skip = &lzma_mf_bt3_skip;
-		break;
-#endif
-#ifdef HAVE_MF_BT4
-	case LZMA_MF_BT4:
-		mf->find = &lzma_mf_bt4_find;
-		mf->skip = &lzma_mf_bt4_skip;
-		break;
-#endif
-
-	default:
-		return true;
-	}
-
-	// Calculate the sizes of mf->hash and mf->son and check that
-	// nice_len is big enough for the selected match finder.
-	const uint32_t hash_bytes = lz_options->match_finder & 0x0F;
-	if (hash_bytes > mf->nice_len)
-		return true;
-
-	const bool is_bt = (lz_options->match_finder & 0x10) != 0;
-	uint32_t hs;
-
-	if (hash_bytes == 2) {
-		hs = 0xFFFF;
-	} else {
-		// Round dictionary size up to the next 2^n - 1 so it can
-		// be used as a hash mask.
-		hs = lz_options->dict_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 (hash_bytes == 3)
-				hs = (UINT32_C(1) << 24) - 1;
-			else
-				hs >>= 1;
-		}
-	}
-
-	mf->hash_mask = hs;
-
-	++hs;
-	if (hash_bytes > 2)
-		hs += HASH_2_SIZE;
-	if (hash_bytes > 3)
-		hs += HASH_3_SIZE;
-/*
-	No match finder uses this at the moment.
-	if (mf->hash_bytes > 4)
-		hs += HASH_4_SIZE;
-*/
-
-	const uint32_t old_hash_count = mf->hash_count;
-	const uint32_t old_sons_count = mf->sons_count;
-	mf->hash_count = hs;
-	mf->sons_count = mf->cyclic_size;
-	if (is_bt)
-		mf->sons_count *= 2;
-
-	// Deallocate the old hash array if it exists and has different size
-	// than what is needed now.
-	if (old_hash_count != mf->hash_count
-			|| old_sons_count != mf->sons_count) {
-		lzma_free(mf->hash, allocator);
-		mf->hash = NULL;
-
-		lzma_free(mf->son, allocator);
-		mf->son = NULL;
-	}
-
-	// Maximum number of match finder cycles
-	mf->depth = lz_options->depth;
-	if (mf->depth == 0) {
-		if (is_bt)
-			mf->depth = 16 + mf->nice_len / 2;
-		else
-			mf->depth = 4 + mf->nice_len / 4;
-	}
-
-	return false;
-}
-
-
-static bool
-lz_encoder_init(lzma_mf *mf, const lzma_allocator *allocator,
-		const lzma_lz_options *lz_options)
-{
-	// Allocate the history buffer.
-	if (mf->buffer == NULL) {
-		// lzma_memcmplen() is used for the dictionary buffer
-		// so we need to allocate a few extra bytes to prevent
-		// it from reading past the end of the buffer.
-		mf->buffer = lzma_alloc(mf->size + LZMA_MEMCMPLEN_EXTRA,
-				allocator);
-		if (mf->buffer == NULL)
-			return true;
-
-		// Keep Valgrind happy with lzma_memcmplen() and initialize
-		// the extra bytes whose value may get read but which will
-		// effectively get ignored.
-		memzero(mf->buffer + mf->size, LZMA_MEMCMPLEN_EXTRA);
-	}
-
-	// Use cyclic_size as initial mf->offset. This allows
-	// avoiding a few branches in the match finders. The downside is
-	// that match finder needs to be normalized more often, which may
-	// hurt performance with huge dictionaries.
-	mf->offset = mf->cyclic_size;
-	mf->read_pos = 0;
-	mf->read_ahead = 0;
-	mf->read_limit = 0;
-	mf->write_pos = 0;
-	mf->pending = 0;
-
-#if UINT32_MAX >= SIZE_MAX / 4
-	// Check for integer overflow. (Huge dictionaries are not
-	// possible on 32-bit CPU.)
-	if (mf->hash_count > SIZE_MAX / sizeof(uint32_t)
-			|| mf->sons_count > SIZE_MAX / sizeof(uint32_t))
-		return true;
-#endif
-
-	// Allocate and initialize the hash table. Since EMPTY_HASH_VALUE
-	// is zero, we can use lzma_alloc_zero() or memzero() for mf->hash.
-	//
-	// We don't need to initialize mf->son, but not doing that may
-	// make Valgrind complain in normalization (see normalize() in
-	// lz_encoder_mf.c). Skipping the initialization is *very* good
-	// when big dictionary is used but only small amount of data gets
-	// actually compressed: most of the mf->son won't get actually
-	// allocated by the kernel, so we avoid wasting RAM and improve
-	// initialization speed a lot.
-	if (mf->hash == NULL) {
-		mf->hash = lzma_alloc_zero(mf->hash_count * sizeof(uint32_t),
-				allocator);
-		mf->son = lzma_alloc(mf->sons_count * sizeof(uint32_t),
-				allocator);
-
-		if (mf->hash == NULL || mf->son == NULL) {
-			lzma_free(mf->hash, allocator);
-			mf->hash = NULL;
-
-			lzma_free(mf->son, allocator);
-			mf->son = NULL;
-
-			return true;
-		}
-	} else {
-/*
-		for (uint32_t i = 0; i < mf->hash_count; ++i)
-			mf->hash[i] = EMPTY_HASH_VALUE;
-*/
-		memzero(mf->hash, mf->hash_count * sizeof(uint32_t));
-	}
-
-	mf->cyclic_pos = 0;
-
-	// Handle preset dictionary.
-	if (lz_options->preset_dict != NULL
-			&& lz_options->preset_dict_size > 0) {
-		// If the preset dictionary is bigger than the actual
-		// dictionary, use only the tail.
-		mf->write_pos = my_min(lz_options->preset_dict_size, mf->size);
-		memcpy(mf->buffer, lz_options->preset_dict
-				+ lz_options->preset_dict_size - mf->write_pos,
-				mf->write_pos);
-		mf->action = LZMA_SYNC_FLUSH;
-		mf->skip(mf, mf->write_pos);
-	}
-
-	mf->action = LZMA_RUN;
-
-	return false;
-}
-
-
-extern uint64_t
-lzma_lz_encoder_memusage(const lzma_lz_options *lz_options)
-{
-	// Old buffers must not exist when calling lz_encoder_prepare().
-	lzma_mf mf = {
-		.buffer = NULL,
-		.hash = NULL,
-		.son = NULL,
-		.hash_count = 0,
-		.sons_count = 0,
-	};
-
-	// Setup the size information into mf.
-	if (lz_encoder_prepare(&mf, NULL, lz_options))
-		return UINT64_MAX;
-
-	// Calculate the memory usage.
-	return ((uint64_t)(mf.hash_count) + mf.sons_count) * sizeof(uint32_t)
-			+ mf.size + sizeof(lzma_coder);
-}
-
-
-static void
-lz_encoder_end(void *coder_ptr, const lzma_allocator *allocator)
-{
-	lzma_coder *coder = coder_ptr;
-
-	lzma_next_end(&coder->next, allocator);
-
-	lzma_free(coder->mf.son, allocator);
-	lzma_free(coder->mf.hash, allocator);
-	lzma_free(coder->mf.buffer, allocator);
-
-	if (coder->lz.end != NULL)
-		coder->lz.end(coder->lz.coder, allocator);
-	else
-		lzma_free(coder->lz.coder, allocator);
-
-	lzma_free(coder, allocator);
-	return;
-}
-
-
-static lzma_ret
-lz_encoder_update(void *coder_ptr, const lzma_allocator *allocator,
-		const lzma_filter *filters_null lzma_attribute((__unused__)),
-		const lzma_filter *reversed_filters)
-{
-	lzma_coder *coder = coder_ptr;
-
-	if (coder->lz.options_update == NULL)
-		return LZMA_PROG_ERROR;
-
-	return_if_error(coder->lz.options_update(
-			coder->lz.coder, reversed_filters));
-
-	return lzma_next_filter_update(
-			&coder->next, allocator, reversed_filters + 1);
-}
-
-
-extern lzma_ret
-lzma_lz_encoder_init(lzma_next_coder *next, const lzma_allocator *allocator,
-		const lzma_filter_info *filters,
-		lzma_ret (*lz_init)(lzma_lz_encoder *lz,
-			const lzma_allocator *allocator, const void *options,
-			lzma_lz_options *lz_options))
-{
-#ifdef HAVE_SMALL
-	// We need that the CRC32 table has been initialized.
-	lzma_crc32_init();
-#endif
-
-	// Allocate and initialize the base data structure.
-	lzma_coder *coder = next->coder;
-	if (coder == NULL) {
-		coder = lzma_alloc(sizeof(lzma_coder), allocator);
-		if (coder == NULL)
-			return LZMA_MEM_ERROR;
-
-		next->coder = coder;
-		next->code = &lz_encode;
-		next->end = &lz_encoder_end;
-		next->update = &lz_encoder_update;
-
-		coder->lz.coder = NULL;
-		coder->lz.code = NULL;
-		coder->lz.end = NULL;
-
-		// mf.size is initialized to silence Valgrind
-		// when used on optimized binaries (GCC may reorder
-		// code in a way that Valgrind gets unhappy).
-		coder->mf.buffer = NULL;
-		coder->mf.size = 0;
-		coder->mf.hash = NULL;
-		coder->mf.son = NULL;
-		coder->mf.hash_count = 0;
-		coder->mf.sons_count = 0;
-
-		coder->next = LZMA_NEXT_CODER_INIT;
-	}
-
-	// Initialize the LZ-based encoder.
-	lzma_lz_options lz_options;
-	return_if_error(lz_init(&coder->lz, allocator,
-			filters[0].options, &lz_options));
-
-	// Setup the size information into coder->mf and deallocate
-	// old buffers if they have wrong size.
-	if (lz_encoder_prepare(&coder->mf, allocator, &lz_options))
-		return LZMA_OPTIONS_ERROR;
-
-	// Allocate new buffers if needed, and do the rest of
-	// the initialization.
-	if (lz_encoder_init(&coder->mf, allocator, &lz_options))
-		return LZMA_MEM_ERROR;
-
-	// Initialize the next filter in the chain, if any.
-	return lzma_next_filter_init(&coder->next, allocator, filters + 1);
-}
-
-
-extern LZMA_API(lzma_bool)
-lzma_mf_is_supported(lzma_match_finder mf)
-{
-	bool ret = false;
-
-#ifdef HAVE_MF_HC3
-	if (mf == LZMA_MF_HC3)
-		ret = true;
-#endif
-
-#ifdef HAVE_MF_HC4
-	if (mf == LZMA_MF_HC4)
-		ret = true;
-#endif
-
-#ifdef HAVE_MF_BT2
-	if (mf == LZMA_MF_BT2)
-		ret = true;
-#endif
-
-#ifdef HAVE_MF_BT3
-	if (mf == LZMA_MF_BT3)
-		ret = true;
-#endif
-
-#ifdef HAVE_MF_BT4
-	if (mf == LZMA_MF_BT4)
-		ret = true;
-#endif
-
-	return ret;
-}
+/////////////////////////////////////////////////////////////////////////////// 
+// 
+/// \file       lz_encoder.c 
+/// \brief      LZ in window 
+/// 
+//  Authors:    Igor Pavlov 
+//              Lasse Collin 
+// 
+//  This file has been put into the public domain. 
+//  You can do whatever you want with this file. 
+// 
+/////////////////////////////////////////////////////////////////////////////// 
+ 
+#include "lz_encoder.h" 
+#include "lz_encoder_hash.h" 
+ 
+// See lz_encoder_hash.h. This is a bit hackish but avoids making 
+// endianness a conditional in makefiles. 
+#if defined(WORDS_BIGENDIAN) && !defined(HAVE_SMALL) 
+#	include "lz_encoder_hash_table.h" 
+#endif 
+ 
+#include "memcmplen.h" 
+ 
+ 
+typedef struct { 
+	/// LZ-based encoder e.g. LZMA 
+	lzma_lz_encoder lz; 
+ 
+	/// History buffer and match finder 
+	lzma_mf mf; 
+ 
+	/// Next coder in the chain 
+	lzma_next_coder next; 
+} lzma_coder; 
+ 
+ 
+/// \brief      Moves the data in the input window to free space for new data 
+/// 
+/// mf->buffer is a sliding input window, which keeps mf->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_mf *mf) 
+{ 
+	// Align the move to a multiple of 16 bytes. Some LZ-based encoders 
+	// like LZMA use the lowest bits of mf->read_pos to know the 
+	// alignment of the uncompressed data. We also get better speed 
+	// for memmove() with aligned buffers. 
+	assert(mf->read_pos > mf->keep_size_before); 
+	const uint32_t move_offset 
+		= (mf->read_pos - mf->keep_size_before) & ~UINT32_C(15); 
+ 
+	assert(mf->write_pos > move_offset); 
+	const size_t move_size = mf->write_pos - move_offset; 
+ 
+	assert(move_offset + move_size <= mf->size); 
+ 
+	memmove(mf->buffer, mf->buffer + move_offset, move_size); 
+ 
+	mf->offset += move_offset; 
+	mf->read_pos -= move_offset; 
+	mf->read_limit -= move_offset; 
+	mf->write_pos -= move_offset; 
+ 
+	return; 
+} 
+ 
+ 
+/// \brief      Tries to fill the input window (mf->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 mf->buffer. 
+/// 
+/// This function must not be called once it has returned LZMA_STREAM_END. 
+/// 
+static lzma_ret 
+fill_window(lzma_coder *coder, const lzma_allocator *allocator, 
+		const uint8_t *in, size_t *in_pos, size_t in_size, 
+		lzma_action action) 
+{ 
+	assert(coder->mf.read_pos <= coder->mf.write_pos); 
+ 
+	// Move the sliding window if needed. 
+	if (coder->mf.read_pos >= coder->mf.size - coder->mf.keep_size_after) 
+		move_window(&coder->mf); 
+ 
+	// Maybe this is ugly, but lzma_mf uses uint32_t for most things 
+	// (which I find cleanest), but we need size_t here when filling 
+	// the history window. 
+	size_t write_pos = coder->mf.write_pos; 
+	lzma_ret ret; 
+	if (coder->next.code == NULL) { 
+		// Not using a filter, simply memcpy() as much as possible. 
+		lzma_bufcpy(in, in_pos, in_size, coder->mf.buffer, 
+				&write_pos, coder->mf.size); 
+ 
+		ret = action != LZMA_RUN && *in_pos == in_size 
+				? LZMA_STREAM_END : LZMA_OK; 
+ 
+	} else { 
+		ret = coder->next.code(coder->next.coder, allocator, 
+				in, in_pos, in_size, 
+				coder->mf.buffer, &write_pos, 
+				coder->mf.size, action); 
+	} 
+ 
+	coder->mf.write_pos = write_pos; 
+ 
+	// Silence Valgrind. lzma_memcmplen() can read extra bytes 
+	// and Valgrind will give warnings if those bytes are uninitialized 
+	// because Valgrind cannot see that the values of the uninitialized 
+	// bytes are eventually ignored. 
+	memzero(coder->mf.buffer + write_pos, LZMA_MEMCMPLEN_EXTRA); 
+ 
+	// 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); 
+		ret = LZMA_OK; 
+		coder->mf.action = action; 
+		coder->mf.read_limit = coder->mf.write_pos; 
+ 
+	} else if (coder->mf.write_pos > coder->mf.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->mf.read_limit = coder->mf.write_pos 
+				- coder->mf.keep_size_after; 
+	} 
+ 
+	// Restart the match finder after finished LZMA_SYNC_FLUSH. 
+	if (coder->mf.pending > 0 
+			&& coder->mf.read_pos < coder->mf.read_limit) { 
+		// Match finder may update coder->pending and expects it to 
+		// start from zero, so use a temporary variable. 
+		const uint32_t pending = coder->mf.pending; 
+		coder->mf.pending = 0; 
+ 
+		// Rewind read_pos so that the match finder can hash 
+		// the pending bytes. 
+		assert(coder->mf.read_pos >= pending); 
+		coder->mf.read_pos -= pending; 
+ 
+		// Call the skip function directly instead of using 
+		// mf_skip(), since we don't want to touch mf->read_ahead. 
+		coder->mf.skip(&coder->mf, pending); 
+	} 
+ 
+	return ret; 
+} 
+ 
+ 
+static lzma_ret 
+lz_encode(void *coder_ptr, const 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) 
+{ 
+	lzma_coder *coder = coder_ptr; 
+ 
+	while (*out_pos < out_size 
+			&& (*in_pos < in_size || action != LZMA_RUN)) { 
+		// Read more data to coder->mf.buffer if needed. 
+		if (coder->mf.action == LZMA_RUN && coder->mf.read_pos 
+				>= coder->mf.read_limit) 
+			return_if_error(fill_window(coder, allocator, 
+					in, in_pos, in_size, action)); 
+ 
+		// Encode 
+		const lzma_ret ret = coder->lz.code(coder->lz.coder, 
+				&coder->mf, out, out_pos, out_size); 
+		if (ret != LZMA_OK) { 
+			// Setting this to LZMA_RUN for cases when we are 
+			// flushing. It doesn't matter when finishing or if 
+			// an error occurred. 
+			coder->mf.action = LZMA_RUN; 
+			return ret; 
+		} 
+	} 
+ 
+	return LZMA_OK; 
+} 
+ 
+ 
+static bool 
+lz_encoder_prepare(lzma_mf *mf, const lzma_allocator *allocator, 
+		const lzma_lz_options *lz_options) 
+{ 
+	// For now, the dictionary size is limited to 1.5 GiB. This may grow 
+	// in the future if needed, but it needs a little more work than just 
+	// changing this check. 
+	if (lz_options->dict_size < LZMA_DICT_SIZE_MIN 
+			|| lz_options->dict_size 
+				> (UINT32_C(1) << 30) + (UINT32_C(1) << 29) 
+			|| lz_options->nice_len > lz_options->match_len_max) 
+		return true; 
+ 
+	mf->keep_size_before = lz_options->before_size + lz_options->dict_size; 
+ 
+	mf->keep_size_after = lz_options->after_size 
+			+ lz_options->match_len_max; 
+ 
+	// To avoid constant memmove()s, allocate some extra space. Since 
+	// memmove()s become more expensive when the size of the buffer 
+	// increases, we reserve more space when a large dictionary is 
+	// used to make the memmove() calls rarer. 
+	// 
+	// This works with dictionaries up to about 3 GiB. If bigger 
+	// dictionary is wanted, some extra work is needed: 
+	//   - Several variables in lzma_mf have to be changed from uint32_t 
+	//     to size_t. 
+	//   - Memory usage calculation needs something too, e.g. use uint64_t 
+	//     for mf->size. 
+	uint32_t reserve = lz_options->dict_size / 2; 
+	if (reserve > (UINT32_C(1) << 30)) 
+		reserve /= 2; 
+ 
+	reserve += (lz_options->before_size + lz_options->match_len_max 
+			+ lz_options->after_size) / 2 + (UINT32_C(1) << 19); 
+ 
+	const uint32_t old_size = mf->size; 
+	mf->size = mf->keep_size_before + reserve + mf->keep_size_after; 
+ 
+	// Deallocate the old history buffer if it exists but has different 
+	// size than what is needed now. 
+	if (mf->buffer != NULL && old_size != mf->size) { 
+		lzma_free(mf->buffer, allocator); 
+		mf->buffer = NULL; 
+	} 
+ 
+	// Match finder options 
+	mf->match_len_max = lz_options->match_len_max; 
+	mf->nice_len = lz_options->nice_len; 
+ 
+	// cyclic_size has to stay smaller than 2 Gi. Note that this doesn't 
+	// mean limiting dictionary size to less than 2 GiB. With a match 
+	// finder that uses multibyte resolution (hashes start at e.g. every 
+	// fourth byte), cyclic_size would stay below 2 Gi even when 
+	// dictionary size is greater than 2 GiB. 
+	// 
+	// It would be possible to allow cyclic_size >= 2 Gi, but then we 
+	// would need to be careful to use 64-bit types in various places 
+	// (size_t could do since we would need bigger than 32-bit address 
+	// space anyway). It would also require either zeroing a multigigabyte 
+	// buffer at initialization (waste of time and RAM) or allow 
+	// normalization in lz_encoder_mf.c to access uninitialized 
+	// memory to keep the code simpler. The current way is simple and 
+	// still allows pretty big dictionaries, so I don't expect these 
+	// limits to change. 
+	mf->cyclic_size = lz_options->dict_size + 1; 
+ 
+	// Validate the match finder ID and setup the function pointers. 
+	switch (lz_options->match_finder) { 
+#ifdef HAVE_MF_HC3 
+	case LZMA_MF_HC3: 
+		mf->find = &lzma_mf_hc3_find; 
+		mf->skip = &lzma_mf_hc3_skip; 
+		break; 
+#endif 
+#ifdef HAVE_MF_HC4 
+	case LZMA_MF_HC4: 
+		mf->find = &lzma_mf_hc4_find; 
+		mf->skip = &lzma_mf_hc4_skip; 
+		break; 
+#endif 
+#ifdef HAVE_MF_BT2 
+	case LZMA_MF_BT2: 
+		mf->find = &lzma_mf_bt2_find; 
+		mf->skip = &lzma_mf_bt2_skip; 
+		break; 
+#endif 
+#ifdef HAVE_MF_BT3 
+	case LZMA_MF_BT3: 
+		mf->find = &lzma_mf_bt3_find; 
+		mf->skip = &lzma_mf_bt3_skip; 
+		break; 
+#endif 
+#ifdef HAVE_MF_BT4 
+	case LZMA_MF_BT4: 
+		mf->find = &lzma_mf_bt4_find; 
+		mf->skip = &lzma_mf_bt4_skip; 
+		break; 
+#endif 
+ 
+	default: 
+		return true; 
+	} 
+ 
+	// Calculate the sizes of mf->hash and mf->son and check that 
+	// nice_len is big enough for the selected match finder. 
+	const uint32_t hash_bytes = lz_options->match_finder & 0x0F; 
+	if (hash_bytes > mf->nice_len) 
+		return true; 
+ 
+	const bool is_bt = (lz_options->match_finder & 0x10) != 0; 
+	uint32_t hs; 
+ 
+	if (hash_bytes == 2) { 
+		hs = 0xFFFF; 
+	} else { 
+		// Round dictionary size up to the next 2^n - 1 so it can 
+		// be used as a hash mask. 
+		hs = lz_options->dict_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 (hash_bytes == 3) 
+				hs = (UINT32_C(1) << 24) - 1; 
+			else 
+				hs >>= 1; 
+		} 
+	} 
+ 
+	mf->hash_mask = hs; 
+ 
+	++hs; 
+	if (hash_bytes > 2) 
+		hs += HASH_2_SIZE; 
+	if (hash_bytes > 3) 
+		hs += HASH_3_SIZE; 
+/* 
+	No match finder uses this at the moment. 
+	if (mf->hash_bytes > 4) 
+		hs += HASH_4_SIZE; 
+*/ 
+ 
+	const uint32_t old_hash_count = mf->hash_count; 
+	const uint32_t old_sons_count = mf->sons_count; 
+	mf->hash_count = hs; 
+	mf->sons_count = mf->cyclic_size; 
+	if (is_bt) 
+		mf->sons_count *= 2; 
+ 
+	// Deallocate the old hash array if it exists and has different size 
+	// than what is needed now. 
+	if (old_hash_count != mf->hash_count 
+			|| old_sons_count != mf->sons_count) { 
+		lzma_free(mf->hash, allocator); 
+		mf->hash = NULL; 
+ 
+		lzma_free(mf->son, allocator); 
+		mf->son = NULL; 
+	} 
+ 
+	// Maximum number of match finder cycles 
+	mf->depth = lz_options->depth; 
+	if (mf->depth == 0) { 
+		if (is_bt) 
+			mf->depth = 16 + mf->nice_len / 2; 
+		else 
+			mf->depth = 4 + mf->nice_len / 4; 
+	} 
+ 
+	return false; 
+} 
+ 
+ 
+static bool 
+lz_encoder_init(lzma_mf *mf, const lzma_allocator *allocator, 
+		const lzma_lz_options *lz_options) 
+{ 
+	// Allocate the history buffer. 
+	if (mf->buffer == NULL) { 
+		// lzma_memcmplen() is used for the dictionary buffer 
+		// so we need to allocate a few extra bytes to prevent 
+		// it from reading past the end of the buffer. 
+		mf->buffer = lzma_alloc(mf->size + LZMA_MEMCMPLEN_EXTRA, 
+				allocator); 
+		if (mf->buffer == NULL) 
+			return true; 
+ 
+		// Keep Valgrind happy with lzma_memcmplen() and initialize 
+		// the extra bytes whose value may get read but which will 
+		// effectively get ignored. 
+		memzero(mf->buffer + mf->size, LZMA_MEMCMPLEN_EXTRA); 
+	} 
+ 
+	// Use cyclic_size as initial mf->offset. This allows 
+	// avoiding a few branches in the match finders. The downside is 
+	// that match finder needs to be normalized more often, which may 
+	// hurt performance with huge dictionaries. 
+	mf->offset = mf->cyclic_size; 
+	mf->read_pos = 0; 
+	mf->read_ahead = 0; 
+	mf->read_limit = 0; 
+	mf->write_pos = 0; 
+	mf->pending = 0; 
+ 
+#if UINT32_MAX >= SIZE_MAX / 4 
+	// Check for integer overflow. (Huge dictionaries are not 
+	// possible on 32-bit CPU.) 
+	if (mf->hash_count > SIZE_MAX / sizeof(uint32_t) 
+			|| mf->sons_count > SIZE_MAX / sizeof(uint32_t)) 
+		return true; 
+#endif 
+ 
+	// Allocate and initialize the hash table. Since EMPTY_HASH_VALUE 
+	// is zero, we can use lzma_alloc_zero() or memzero() for mf->hash. 
+	// 
+	// We don't need to initialize mf->son, but not doing that may 
+	// make Valgrind complain in normalization (see normalize() in 
+	// lz_encoder_mf.c). Skipping the initialization is *very* good 
+	// when big dictionary is used but only small amount of data gets 
+	// actually compressed: most of the mf->son won't get actually 
+	// allocated by the kernel, so we avoid wasting RAM and improve 
+	// initialization speed a lot. 
+	if (mf->hash == NULL) { 
+		mf->hash = lzma_alloc_zero(mf->hash_count * sizeof(uint32_t), 
+				allocator); 
+		mf->son = lzma_alloc(mf->sons_count * sizeof(uint32_t), 
+				allocator); 
+ 
+		if (mf->hash == NULL || mf->son == NULL) { 
+			lzma_free(mf->hash, allocator); 
+			mf->hash = NULL; 
+ 
+			lzma_free(mf->son, allocator); 
+			mf->son = NULL; 
+ 
+			return true; 
+		} 
+	} else { 
+/* 
+		for (uint32_t i = 0; i < mf->hash_count; ++i) 
+			mf->hash[i] = EMPTY_HASH_VALUE; 
+*/ 
+		memzero(mf->hash, mf->hash_count * sizeof(uint32_t)); 
+	} 
+ 
+	mf->cyclic_pos = 0; 
+ 
+	// Handle preset dictionary. 
+	if (lz_options->preset_dict != NULL 
+			&& lz_options->preset_dict_size > 0) { 
+		// If the preset dictionary is bigger than the actual 
+		// dictionary, use only the tail. 
+		mf->write_pos = my_min(lz_options->preset_dict_size, mf->size); 
+		memcpy(mf->buffer, lz_options->preset_dict 
+				+ lz_options->preset_dict_size - mf->write_pos, 
+				mf->write_pos); 
+		mf->action = LZMA_SYNC_FLUSH; 
+		mf->skip(mf, mf->write_pos); 
+	} 
+ 
+	mf->action = LZMA_RUN; 
+ 
+	return false; 
+} 
+ 
+ 
+extern uint64_t 
+lzma_lz_encoder_memusage(const lzma_lz_options *lz_options) 
+{ 
+	// Old buffers must not exist when calling lz_encoder_prepare(). 
+	lzma_mf mf = { 
+		.buffer = NULL, 
+		.hash = NULL, 
+		.son = NULL, 
+		.hash_count = 0, 
+		.sons_count = 0, 
+	}; 
+ 
+	// Setup the size information into mf. 
+	if (lz_encoder_prepare(&mf, NULL, lz_options)) 
+		return UINT64_MAX; 
+ 
+	// Calculate the memory usage. 
+	return ((uint64_t)(mf.hash_count) + mf.sons_count) * sizeof(uint32_t) 
+			+ mf.size + sizeof(lzma_coder); 
+} 
+ 
+ 
+static void 
+lz_encoder_end(void *coder_ptr, const lzma_allocator *allocator) 
+{ 
+	lzma_coder *coder = coder_ptr; 
+ 
+	lzma_next_end(&coder->next, allocator); 
+ 
+	lzma_free(coder->mf.son, allocator); 
+	lzma_free(coder->mf.hash, allocator); 
+	lzma_free(coder->mf.buffer, allocator); 
+ 
+	if (coder->lz.end != NULL) 
+		coder->lz.end(coder->lz.coder, allocator); 
+	else 
+		lzma_free(coder->lz.coder, allocator); 
+ 
+	lzma_free(coder, allocator); 
+	return; 
+} 
+ 
+ 
+static lzma_ret 
+lz_encoder_update(void *coder_ptr, const lzma_allocator *allocator, 
+		const lzma_filter *filters_null lzma_attribute((__unused__)), 
+		const lzma_filter *reversed_filters) 
+{ 
+	lzma_coder *coder = coder_ptr; 
+ 
+	if (coder->lz.options_update == NULL) 
+		return LZMA_PROG_ERROR; 
+ 
+	return_if_error(coder->lz.options_update( 
+			coder->lz.coder, reversed_filters)); 
+ 
+	return lzma_next_filter_update( 
+			&coder->next, allocator, reversed_filters + 1); 
+} 
+ 
+ 
+extern lzma_ret 
+lzma_lz_encoder_init(lzma_next_coder *next, const lzma_allocator *allocator, 
+		const lzma_filter_info *filters, 
+		lzma_ret (*lz_init)(lzma_lz_encoder *lz, 
+			const lzma_allocator *allocator, const void *options, 
+			lzma_lz_options *lz_options)) 
+{ 
+#ifdef HAVE_SMALL 
+	// We need that the CRC32 table has been initialized. 
+	lzma_crc32_init(); 
+#endif 
+ 
+	// Allocate and initialize the base data structure. 
+	lzma_coder *coder = next->coder; 
+	if (coder == NULL) { 
+		coder = lzma_alloc(sizeof(lzma_coder), allocator); 
+		if (coder == NULL) 
+			return LZMA_MEM_ERROR; 
+ 
+		next->coder = coder; 
+		next->code = &lz_encode; 
+		next->end = &lz_encoder_end; 
+		next->update = &lz_encoder_update; 
+ 
+		coder->lz.coder = NULL; 
+		coder->lz.code = NULL; 
+		coder->lz.end = NULL; 
+ 
+		// mf.size is initialized to silence Valgrind 
+		// when used on optimized binaries (GCC may reorder 
+		// code in a way that Valgrind gets unhappy). 
+		coder->mf.buffer = NULL; 
+		coder->mf.size = 0; 
+		coder->mf.hash = NULL; 
+		coder->mf.son = NULL; 
+		coder->mf.hash_count = 0; 
+		coder->mf.sons_count = 0; 
+ 
+		coder->next = LZMA_NEXT_CODER_INIT; 
+	} 
+ 
+	// Initialize the LZ-based encoder. 
+	lzma_lz_options lz_options; 
+	return_if_error(lz_init(&coder->lz, allocator, 
+			filters[0].options, &lz_options)); 
+ 
+	// Setup the size information into coder->mf and deallocate 
+	// old buffers if they have wrong size. 
+	if (lz_encoder_prepare(&coder->mf, allocator, &lz_options)) 
+		return LZMA_OPTIONS_ERROR; 
+ 
+	// Allocate new buffers if needed, and do the rest of 
+	// the initialization. 
+	if (lz_encoder_init(&coder->mf, allocator, &lz_options)) 
+		return LZMA_MEM_ERROR; 
+ 
+	// Initialize the next filter in the chain, if any. 
+	return lzma_next_filter_init(&coder->next, allocator, filters + 1); 
+} 
+ 
+ 
+extern LZMA_API(lzma_bool) 
+lzma_mf_is_supported(lzma_match_finder mf) 
+{ 
+	bool ret = false; 
+ 
+#ifdef HAVE_MF_HC3 
+	if (mf == LZMA_MF_HC3) 
+		ret = true; 
+#endif 
+ 
+#ifdef HAVE_MF_HC4 
+	if (mf == LZMA_MF_HC4) 
+		ret = true; 
+#endif 
+ 
+#ifdef HAVE_MF_BT2 
+	if (mf == LZMA_MF_BT2) 
+		ret = true; 
+#endif 
+ 
+#ifdef HAVE_MF_BT3 
+	if (mf == LZMA_MF_BT3) 
+		ret = true; 
+#endif 
+ 
+#ifdef HAVE_MF_BT4 
+	if (mf == LZMA_MF_BT4) 
+		ret = true; 
+#endif 
+ 
+	return ret; 
+} 
diff --git a/contrib/libs/xz/liblzma/lz/lz_encoder.h b/contrib/libs/xz/liblzma/lz/lz_encoder.h
index 426dcd8a38..5b95e53cd4 100644
--- a/contrib/libs/xz/liblzma/lz/lz_encoder.h
+++ b/contrib/libs/xz/liblzma/lz/lz_encoder.h
@@ -1,327 +1,327 @@
-///////////////////////////////////////////////////////////////////////////////
-//
-/// \file       lz_encoder.h
-/// \brief      LZ in window and match finder API
-///
-//  Authors:    Igor Pavlov
-//              Lasse Collin
-//
-//  This file has been put into the public domain.
-//  You can do whatever you want with this file.
-//
-///////////////////////////////////////////////////////////////////////////////
-
-#ifndef LZMA_LZ_ENCODER_H
-#define LZMA_LZ_ENCODER_H
-
-#include "common.h"
-
-
-/// A table of these is used by the LZ-based encoder to hold
-/// the length-distance pairs found by the match finder.
-typedef struct {
-	uint32_t len;
-	uint32_t dist;
-} lzma_match;
-
-
-typedef struct lzma_mf_s lzma_mf;
-struct lzma_mf_s {
-	///////////////
-	// In Window //
-	///////////////
-
-	/// Pointer to buffer with data to be compressed
-	uint8_t *buffer;
-
-	/// Total size of the allocated buffer (that is, including all
-	/// the extra space)
-	uint32_t size;
-
-	/// Number of bytes that must be kept available in our input history.
-	/// That is, once keep_size_before bytes have been processed,
-	/// buffer[read_pos - keep_size_before] is the oldest byte that
-	/// must be available for reading.
-	uint32_t keep_size_before;
-
-	/// Number of bytes that must be kept in buffer after read_pos.
-	/// That is, read_pos <= write_pos - keep_size_after as long as
-	/// action is LZMA_RUN; when action != LZMA_RUN, read_pos is allowed
-	/// to reach write_pos so that the last bytes get encoded too.
-	uint32_t keep_size_after;
-
-	/// Match finders store locations of matches using 32-bit integers.
-	/// To avoid adjusting several megabytes of integers every time the
-	/// input window is moved with move_window, we only adjust the
-	/// offset of the buffer. Thus, buffer[value_in_hash_table - offset]
-	/// is the byte pointed by value_in_hash_table.
-	uint32_t offset;
-
-	/// buffer[read_pos] is the next byte to run through the match
-	/// finder. This is incremented in the match finder once the byte
-	/// has been processed.
-	uint32_t read_pos;
-
-	/// Number of bytes that have been ran through the match finder, but
-	/// which haven't been encoded by the LZ-based encoder yet.
-	uint32_t read_ahead;
-
-	/// As long as read_pos is less than read_limit, there is enough
-	/// input available in buffer for at least one encoding loop.
-	///
-	/// Because of the stateful API, read_limit may and will get greater
-	/// than read_pos quite often. This is taken into account when
-	/// calculating the value for keep_size_after.
-	uint32_t read_limit;
-
-	/// buffer[write_pos] is the first byte that doesn't contain valid
-	/// uncompressed data; that is, the next input byte will be copied
-	/// to buffer[write_pos].
-	uint32_t write_pos;
-
-	/// Number of bytes not hashed before read_pos. This is needed to
-	/// restart the match finder after LZMA_SYNC_FLUSH.
-	uint32_t pending;
-
-	//////////////////
-	// Match Finder //
-	//////////////////
-
-	/// Find matches. Returns the number of distance-length pairs written
-	/// to the matches array. This is called only via lzma_mf_find().
-	uint32_t (*find)(lzma_mf *mf, lzma_match *matches);
-
-	/// Skips num bytes. This is like find() but doesn't make the
-	/// distance-length pairs available, thus being a little faster.
-	/// This is called only via mf_skip().
-	void (*skip)(lzma_mf *mf, uint32_t num);
-
-	uint32_t *hash;
-	uint32_t *son;
-	uint32_t cyclic_pos;
-	uint32_t cyclic_size; // Must be dictionary size + 1.
-	uint32_t hash_mask;
-
-	/// Maximum number of loops in the match finder
-	uint32_t depth;
-
-	/// Maximum length of a match that the match finder will try to find.
-	uint32_t nice_len;
-
-	/// Maximum length of a match supported by the LZ-based encoder.
-	/// If the longest match found by the match finder is nice_len,
-	/// mf_find() tries to expand it up to match_len_max bytes.
-	uint32_t match_len_max;
-
-	/// When running out of input, binary tree match finders need to know
-	/// if it is due to flushing or finishing. The action is used also
-	/// by the LZ-based encoders themselves.
-	lzma_action action;
-
-	/// Number of elements in hash[]
-	uint32_t hash_count;
-
-	/// Number of elements in son[]
-	uint32_t sons_count;
-};
-
-
-typedef struct {
-	/// Extra amount of data to keep available before the "actual"
-	/// dictionary.
-	size_t before_size;
-
-	/// Size of the history buffer
-	size_t dict_size;
-
-	/// Extra amount of data to keep available after the "actual"
-	/// dictionary.
-	size_t after_size;
-
-	/// Maximum length of a match that the LZ-based encoder can accept.
-	/// This is used to extend matches of length nice_len to the
-	/// maximum possible length.
-	size_t match_len_max;
-
-	/// Match finder will search matches up to this length.
-	/// This must be less than or equal to match_len_max.
-	size_t nice_len;
-
-	/// Type of the match finder to use
-	lzma_match_finder match_finder;
-
-	/// Maximum search depth
-	uint32_t depth;
-
-	/// TODO: Comment
-	const uint8_t *preset_dict;
-
-	uint32_t preset_dict_size;
-
-} lzma_lz_options;
-
-
-// The total usable buffer space at any moment outside the match finder:
-// before_size + dict_size + after_size + match_len_max
-//
-// In reality, there's some extra space allocated to prevent the number of
-// memmove() calls reasonable. The bigger the dict_size is, the bigger
-// this extra buffer will be since with bigger dictionaries memmove() would
-// also take longer.
-//
-// A single encoder loop in the LZ-based encoder may call the match finder
-// (mf_find() or mf_skip()) at most after_size times. In other words,
-// a single encoder loop may increment lzma_mf.read_pos at most after_size
-// times. Since matches are looked up to
-// lzma_mf.buffer[lzma_mf.read_pos + match_len_max - 1], the total
-// amount of extra buffer needed after dict_size becomes
-// after_size + match_len_max.
-//
-// before_size has two uses. The first one is to keep literals available
-// in cases when the LZ-based encoder has made some read ahead.
-// TODO: Maybe this could be changed by making the LZ-based encoders to
-// store the actual literals as they do with length-distance pairs.
-//
-// Algorithms such as LZMA2 first try to compress a chunk, and then check
-// if the encoded result is smaller than the uncompressed one. If the chunk
-// was uncompressible, it is better to store it in uncompressed form in
-// the output stream. To do this, the whole uncompressed chunk has to be
-// still available in the history buffer. before_size achieves that.
-
-
-typedef struct {
-	/// Data specific to the LZ-based encoder
-	void *coder;
-
-	/// Function to encode from *dict to out[]
-	lzma_ret (*code)(void *coder,
-			lzma_mf *restrict mf, uint8_t *restrict out,
-			size_t *restrict out_pos, size_t out_size);
-
-	/// Free allocated resources
-	void (*end)(void *coder, const lzma_allocator *allocator);
-
-	/// Update the options in the middle of the encoding.
-	lzma_ret (*options_update)(void *coder, const lzma_filter *filter);
-
-} lzma_lz_encoder;
-
-
-// Basic steps:
-//  1. Input gets copied into the dictionary.
-//  2. Data in dictionary gets run through the match finder byte by byte.
-//  3. The literals and matches are encoded using e.g. LZMA.
-//
-// The bytes that have been ran through the match finder, but not encoded yet,
-// are called `read ahead'.
-
-
-/// Get pointer to the first byte not ran through the match finder
-static inline const uint8_t *
-mf_ptr(const lzma_mf *mf)
-{
-	return mf->buffer + mf->read_pos;
-}
-
-
-/// Get the number of bytes that haven't been ran through the match finder yet.
-static inline uint32_t
-mf_avail(const lzma_mf *mf)
-{
-	return mf->write_pos - mf->read_pos;
-}
-
-
-/// Get the number of bytes that haven't been encoded yet (some of these
-/// bytes may have been ran through the match finder though).
-static inline uint32_t
-mf_unencoded(const lzma_mf *mf)
-{
-	return mf->write_pos - mf->read_pos + mf->read_ahead;
-}
-
-
-/// Calculate the absolute offset from the beginning of the most recent
-/// dictionary reset. Only the lowest four bits are important, so there's no
-/// problem that we don't know the 64-bit size of the data encoded so far.
-///
-/// NOTE: When moving the input window, we need to do it so that the lowest
-/// bits of dict->read_pos are not modified to keep this macro working
-/// as intended.
-static inline uint32_t
-mf_position(const lzma_mf *mf)
-{
-	return mf->read_pos - mf->read_ahead;
-}
-
-
-/// Since everything else begins with mf_, use it also for lzma_mf_find().
-#define mf_find lzma_mf_find
-
-
-/// Skip the given number of bytes. This is used when a good match was found.
-/// For example, if mf_find() finds a match of 200 bytes long, the first byte
-/// of that match was already consumed by mf_find(), and the rest 199 bytes
-/// have to be skipped with mf_skip(mf, 199).
-static inline void
-mf_skip(lzma_mf *mf, uint32_t amount)
-{
-	if (amount != 0) {
-		mf->skip(mf, amount);
-		mf->read_ahead += amount;
-	}
-}
-
-
-/// Copies at most *left number of bytes from the history buffer
-/// to out[]. This is needed by LZMA2 to encode uncompressed chunks.
-static inline void
-mf_read(lzma_mf *mf, uint8_t *out, size_t *out_pos, size_t out_size,
-		size_t *left)
-{
-	const size_t out_avail = out_size - *out_pos;
-	const size_t copy_size = my_min(out_avail, *left);
-
-	assert(mf->read_ahead == 0);
-	assert(mf->read_pos >= *left);
-
-	memcpy(out + *out_pos, mf->buffer + mf->read_pos - *left,
-			copy_size);
-
-	*out_pos += copy_size;
-	*left -= copy_size;
-	return;
-}
-
-
-extern lzma_ret lzma_lz_encoder_init(
-		lzma_next_coder *next, const lzma_allocator *allocator,
-		const lzma_filter_info *filters,
-		lzma_ret (*lz_init)(lzma_lz_encoder *lz,
-			const lzma_allocator *allocator, const void *options,
-			lzma_lz_options *lz_options));
-
-
-extern uint64_t lzma_lz_encoder_memusage(const lzma_lz_options *lz_options);
-
-
-// These are only for LZ encoder's internal use.
-extern uint32_t lzma_mf_find(
-		lzma_mf *mf, uint32_t *count, lzma_match *matches);
-
-extern uint32_t lzma_mf_hc3_find(lzma_mf *dict, lzma_match *matches);
-extern void lzma_mf_hc3_skip(lzma_mf *dict, uint32_t amount);
-
-extern uint32_t lzma_mf_hc4_find(lzma_mf *dict, lzma_match *matches);
-extern void lzma_mf_hc4_skip(lzma_mf *dict, uint32_t amount);
-
-extern uint32_t lzma_mf_bt2_find(lzma_mf *dict, lzma_match *matches);
-extern void lzma_mf_bt2_skip(lzma_mf *dict, uint32_t amount);
-
-extern uint32_t lzma_mf_bt3_find(lzma_mf *dict, lzma_match *matches);
-extern void lzma_mf_bt3_skip(lzma_mf *dict, uint32_t amount);
-
-extern uint32_t lzma_mf_bt4_find(lzma_mf *dict, lzma_match *matches);
-extern void lzma_mf_bt4_skip(lzma_mf *dict, uint32_t amount);
-
-#endif
+/////////////////////////////////////////////////////////////////////////////// 
+// 
+/// \file       lz_encoder.h 
+/// \brief      LZ in window and match finder API 
+/// 
+//  Authors:    Igor Pavlov 
+//              Lasse Collin 
+// 
+//  This file has been put into the public domain. 
+//  You can do whatever you want with this file. 
+// 
+/////////////////////////////////////////////////////////////////////////////// 
+ 
+#ifndef LZMA_LZ_ENCODER_H 
+#define LZMA_LZ_ENCODER_H 
+ 
+#include "common.h" 
+ 
+ 
+/// A table of these is used by the LZ-based encoder to hold 
+/// the length-distance pairs found by the match finder. 
+typedef struct { 
+	uint32_t len; 
+	uint32_t dist; 
+} lzma_match; 
+ 
+ 
+typedef struct lzma_mf_s lzma_mf; 
+struct lzma_mf_s { 
+	/////////////// 
+	// In Window // 
+	/////////////// 
+ 
+	/// Pointer to buffer with data to be compressed 
+	uint8_t *buffer; 
+ 
+	/// Total size of the allocated buffer (that is, including all 
+	/// the extra space) 
+	uint32_t size; 
+ 
+	/// Number of bytes that must be kept available in our input history. 
+	/// That is, once keep_size_before bytes have been processed, 
+	/// buffer[read_pos - keep_size_before] is the oldest byte that 
+	/// must be available for reading. 
+	uint32_t keep_size_before; 
+ 
+	/// Number of bytes that must be kept in buffer after read_pos. 
+	/// That is, read_pos <= write_pos - keep_size_after as long as 
+	/// action is LZMA_RUN; when action != LZMA_RUN, read_pos is allowed 
+	/// to reach write_pos so that the last bytes get encoded too. 
+	uint32_t keep_size_after; 
+ 
+	/// Match finders store locations of matches using 32-bit integers. 
+	/// To avoid adjusting several megabytes of integers every time the 
+	/// input window is moved with move_window, we only adjust the 
+	/// offset of the buffer. Thus, buffer[value_in_hash_table - offset] 
+	/// is the byte pointed by value_in_hash_table. 
+	uint32_t offset; 
+ 
+	/// buffer[read_pos] is the next byte to run through the match 
+	/// finder. This is incremented in the match finder once the byte 
+	/// has been processed. 
+	uint32_t read_pos; 
+ 
+	/// Number of bytes that have been ran through the match finder, but 
+	/// which haven't been encoded by the LZ-based encoder yet. 
+	uint32_t read_ahead; 
+ 
+	/// As long as read_pos is less than read_limit, there is enough 
+	/// input available in buffer for at least one encoding loop. 
+	/// 
+	/// Because of the stateful API, read_limit may and will get greater 
+	/// than read_pos quite often. This is taken into account when 
+	/// calculating the value for keep_size_after. 
+	uint32_t read_limit; 
+ 
+	/// buffer[write_pos] is the first byte that doesn't contain valid 
+	/// uncompressed data; that is, the next input byte will be copied 
+	/// to buffer[write_pos]. 
+	uint32_t write_pos; 
+ 
+	/// Number of bytes not hashed before read_pos. This is needed to 
+	/// restart the match finder after LZMA_SYNC_FLUSH. 
+	uint32_t pending; 
+ 
+	////////////////// 
+	// Match Finder // 
+	////////////////// 
+ 
+	/// Find matches. Returns the number of distance-length pairs written 
+	/// to the matches array. This is called only via lzma_mf_find(). 
+	uint32_t (*find)(lzma_mf *mf, lzma_match *matches); 
+ 
+	/// Skips num bytes. This is like find() but doesn't make the 
+	/// distance-length pairs available, thus being a little faster. 
+	/// This is called only via mf_skip(). 
+	void (*skip)(lzma_mf *mf, uint32_t num); 
+ 
+	uint32_t *hash; 
+	uint32_t *son; 
+	uint32_t cyclic_pos; 
+	uint32_t cyclic_size; // Must be dictionary size + 1. 
+	uint32_t hash_mask; 
+ 
+	/// Maximum number of loops in the match finder 
+	uint32_t depth; 
+ 
+	/// Maximum length of a match that the match finder will try to find. 
+	uint32_t nice_len; 
+ 
+	/// Maximum length of a match supported by the LZ-based encoder. 
+	/// If the longest match found by the match finder is nice_len, 
+	/// mf_find() tries to expand it up to match_len_max bytes. 
+	uint32_t match_len_max; 
+ 
+	/// When running out of input, binary tree match finders need to know 
+	/// if it is due to flushing or finishing. The action is used also 
+	/// by the LZ-based encoders themselves. 
+	lzma_action action; 
+ 
+	/// Number of elements in hash[] 
+	uint32_t hash_count; 
+ 
+	/// Number of elements in son[] 
+	uint32_t sons_count; 
+}; 
+ 
+ 
+typedef struct { 
+	/// Extra amount of data to keep available before the "actual" 
+	/// dictionary. 
+	size_t before_size; 
+ 
+	/// Size of the history buffer 
+	size_t dict_size; 
+ 
+	/// Extra amount of data to keep available after the "actual" 
+	/// dictionary. 
+	size_t after_size; 
+ 
+	/// Maximum length of a match that the LZ-based encoder can accept. 
+	/// This is used to extend matches of length nice_len to the 
+	/// maximum possible length. 
+	size_t match_len_max; 
+ 
+	/// Match finder will search matches up to this length. 
+	/// This must be less than or equal to match_len_max. 
+	size_t nice_len; 
+ 
+	/// Type of the match finder to use 
+	lzma_match_finder match_finder; 
+ 
+	/// Maximum search depth 
+	uint32_t depth; 
+ 
+	/// TODO: Comment 
+	const uint8_t *preset_dict; 
+ 
+	uint32_t preset_dict_size; 
+ 
+} lzma_lz_options; 
+ 
+ 
+// The total usable buffer space at any moment outside the match finder: 
+// before_size + dict_size + after_size + match_len_max 
+// 
+// In reality, there's some extra space allocated to prevent the number of 
+// memmove() calls reasonable. The bigger the dict_size is, the bigger 
+// this extra buffer will be since with bigger dictionaries memmove() would 
+// also take longer. 
+// 
+// A single encoder loop in the LZ-based encoder may call the match finder 
+// (mf_find() or mf_skip()) at most after_size times. In other words, 
+// a single encoder loop may increment lzma_mf.read_pos at most after_size 
+// times. Since matches are looked up to 
+// lzma_mf.buffer[lzma_mf.read_pos + match_len_max - 1], the total 
+// amount of extra buffer needed after dict_size becomes 
+// after_size + match_len_max. 
+// 
+// before_size has two uses. The first one is to keep literals available 
+// in cases when the LZ-based encoder has made some read ahead. 
+// TODO: Maybe this could be changed by making the LZ-based encoders to 
+// store the actual literals as they do with length-distance pairs. 
+// 
+// Algorithms such as LZMA2 first try to compress a chunk, and then check 
+// if the encoded result is smaller than the uncompressed one. If the chunk 
+// was uncompressible, it is better to store it in uncompressed form in 
+// the output stream. To do this, the whole uncompressed chunk has to be 
+// still available in the history buffer. before_size achieves that. 
+ 
+ 
+typedef struct { 
+	/// Data specific to the LZ-based encoder 
+	void *coder; 
+ 
+	/// Function to encode from *dict to out[] 
+	lzma_ret (*code)(void *coder, 
+			lzma_mf *restrict mf, uint8_t *restrict out, 
+			size_t *restrict out_pos, size_t out_size); 
+ 
+	/// Free allocated resources 
+	void (*end)(void *coder, const lzma_allocator *allocator); 
+ 
+	/// Update the options in the middle of the encoding. 
+	lzma_ret (*options_update)(void *coder, const lzma_filter *filter); 
+ 
+} lzma_lz_encoder; 
+ 
+ 
+// Basic steps: 
+//  1. Input gets copied into the dictionary. 
+//  2. Data in dictionary gets run through the match finder byte by byte. 
+//  3. The literals and matches are encoded using e.g. LZMA. 
+// 
+// The bytes that have been ran through the match finder, but not encoded yet, 
+// are called `read ahead'. 
+ 
+ 
+/// Get pointer to the first byte not ran through the match finder 
+static inline const uint8_t * 
+mf_ptr(const lzma_mf *mf) 
+{ 
+	return mf->buffer + mf->read_pos; 
+} 
+ 
+ 
+/// Get the number of bytes that haven't been ran through the match finder yet. 
+static inline uint32_t 
+mf_avail(const lzma_mf *mf) 
+{ 
+	return mf->write_pos - mf->read_pos; 
+} 
+ 
+ 
+/// Get the number of bytes that haven't been encoded yet (some of these 
+/// bytes may have been ran through the match finder though). 
+static inline uint32_t 
+mf_unencoded(const lzma_mf *mf) 
+{ 
+	return mf->write_pos - mf->read_pos + mf->read_ahead; 
+} 
+ 
+ 
+/// Calculate the absolute offset from the beginning of the most recent 
+/// dictionary reset. Only the lowest four bits are important, so there's no 
+/// problem that we don't know the 64-bit size of the data encoded so far. 
+/// 
+/// NOTE: When moving the input window, we need to do it so that the lowest 
+/// bits of dict->read_pos are not modified to keep this macro working 
+/// as intended. 
+static inline uint32_t 
+mf_position(const lzma_mf *mf) 
+{ 
+	return mf->read_pos - mf->read_ahead; 
+} 
+ 
+ 
+/// Since everything else begins with mf_, use it also for lzma_mf_find(). 
+#define mf_find lzma_mf_find 
+ 
+ 
+/// Skip the given number of bytes. This is used when a good match was found. 
+/// For example, if mf_find() finds a match of 200 bytes long, the first byte 
+/// of that match was already consumed by mf_find(), and the rest 199 bytes 
+/// have to be skipped with mf_skip(mf, 199). 
+static inline void 
+mf_skip(lzma_mf *mf, uint32_t amount) 
+{ 
+	if (amount != 0) { 
+		mf->skip(mf, amount); 
+		mf->read_ahead += amount; 
+	} 
+} 
+ 
+ 
+/// Copies at most *left number of bytes from the history buffer 
+/// to out[]. This is needed by LZMA2 to encode uncompressed chunks. 
+static inline void 
+mf_read(lzma_mf *mf, uint8_t *out, size_t *out_pos, size_t out_size, 
+		size_t *left) 
+{ 
+	const size_t out_avail = out_size - *out_pos; 
+	const size_t copy_size = my_min(out_avail, *left); 
+ 
+	assert(mf->read_ahead == 0); 
+	assert(mf->read_pos >= *left); 
+ 
+	memcpy(out + *out_pos, mf->buffer + mf->read_pos - *left, 
+			copy_size); 
+ 
+	*out_pos += copy_size; 
+	*left -= copy_size; 
+	return; 
+} 
+ 
+ 
+extern lzma_ret lzma_lz_encoder_init( 
+		lzma_next_coder *next, const lzma_allocator *allocator, 
+		const lzma_filter_info *filters, 
+		lzma_ret (*lz_init)(lzma_lz_encoder *lz, 
+			const lzma_allocator *allocator, const void *options, 
+			lzma_lz_options *lz_options)); 
+ 
+ 
+extern uint64_t lzma_lz_encoder_memusage(const lzma_lz_options *lz_options); 
+ 
+ 
+// These are only for LZ encoder's internal use. 
+extern uint32_t lzma_mf_find( 
+		lzma_mf *mf, uint32_t *count, lzma_match *matches); 
+ 
+extern uint32_t lzma_mf_hc3_find(lzma_mf *dict, lzma_match *matches); 
+extern void lzma_mf_hc3_skip(lzma_mf *dict, uint32_t amount); 
+ 
+extern uint32_t lzma_mf_hc4_find(lzma_mf *dict, lzma_match *matches); 
+extern void lzma_mf_hc4_skip(lzma_mf *dict, uint32_t amount); 
+ 
+extern uint32_t lzma_mf_bt2_find(lzma_mf *dict, lzma_match *matches); 
+extern void lzma_mf_bt2_skip(lzma_mf *dict, uint32_t amount); 
+ 
+extern uint32_t lzma_mf_bt3_find(lzma_mf *dict, lzma_match *matches); 
+extern void lzma_mf_bt3_skip(lzma_mf *dict, uint32_t amount); 
+ 
+extern uint32_t lzma_mf_bt4_find(lzma_mf *dict, lzma_match *matches); 
+extern void lzma_mf_bt4_skip(lzma_mf *dict, uint32_t amount); 
+ 
+#endif 
diff --git a/contrib/libs/xz/liblzma/lz/lz_encoder_hash.h b/contrib/libs/xz/liblzma/lz/lz_encoder_hash.h
index 342a333d16..aa6131e14f 100644
--- a/contrib/libs/xz/liblzma/lz/lz_encoder_hash.h
+++ b/contrib/libs/xz/liblzma/lz/lz_encoder_hash.h
@@ -1,108 +1,108 @@
-///////////////////////////////////////////////////////////////////////////////
-//
-/// \file       lz_encoder_hash.h
-/// \brief      Hash macros for match finders
-//
-//  Author:     Igor Pavlov
-//
-//  This file has been put into the public domain.
-//  You can do whatever you want with this file.
-//
-///////////////////////////////////////////////////////////////////////////////
-
-#ifndef LZMA_LZ_ENCODER_HASH_H
-#define LZMA_LZ_ENCODER_HASH_H
-
-#if defined(WORDS_BIGENDIAN) && !defined(HAVE_SMALL)
-	// This is to make liblzma produce the same output on big endian
-	// systems that it does on little endian systems. lz_encoder.c
-	// takes care of including the actual table.
-	extern const uint32_t lzma_lz_hash_table[256];
-#	define hash_table lzma_lz_hash_table
-#else
-#	include "check.h"
-#	define hash_table lzma_crc32_table[0]
-#endif
-
-#define HASH_2_SIZE (UINT32_C(1) << 10)
-#define HASH_3_SIZE (UINT32_C(1) << 16)
-#define HASH_4_SIZE (UINT32_C(1) << 20)
-
-#define HASH_2_MASK (HASH_2_SIZE - 1)
-#define HASH_3_MASK (HASH_3_SIZE - 1)
-#define HASH_4_MASK (HASH_4_SIZE - 1)
-
-#define FIX_3_HASH_SIZE (HASH_2_SIZE)
-#define FIX_4_HASH_SIZE (HASH_2_SIZE + HASH_3_SIZE)
-#define FIX_5_HASH_SIZE (HASH_2_SIZE + HASH_3_SIZE + HASH_4_SIZE)
-
-// Endianness doesn't matter in hash_2_calc() (no effect on the output).
-#ifdef TUKLIB_FAST_UNALIGNED_ACCESS
-#	define hash_2_calc() \
-		const uint32_t hash_value = *(const uint16_t *)(cur)
-#else
-#	define hash_2_calc() \
-		const uint32_t hash_value \
-			= (uint32_t)(cur[0]) | ((uint32_t)(cur[1]) << 8)
-#endif
-
-#define hash_3_calc() \
-	const uint32_t temp = hash_table[cur[0]] ^ cur[1]; \
-	const uint32_t hash_2_value = temp & HASH_2_MASK; \
-	const uint32_t hash_value \
-			= (temp ^ ((uint32_t)(cur[2]) << 8)) & mf->hash_mask
-
-#define hash_4_calc() \
-	const uint32_t temp = hash_table[cur[0]] ^ cur[1]; \
-	const uint32_t hash_2_value = temp & HASH_2_MASK; \
-	const uint32_t hash_3_value \
-			= (temp ^ ((uint32_t)(cur[2]) << 8)) & HASH_3_MASK; \
-	const uint32_t hash_value = (temp ^ ((uint32_t)(cur[2]) << 8) \
-			^ (hash_table[cur[3]] << 5)) & mf->hash_mask
-
-
-// The following are not currently used.
-
-#define hash_5_calc() \
-	const uint32_t temp = hash_table[cur[0]] ^ cur[1]; \
-	const uint32_t hash_2_value = temp & HASH_2_MASK; \
-	const uint32_t hash_3_value \
-			= (temp ^ ((uint32_t)(cur[2]) << 8)) & HASH_3_MASK; \
-	uint32_t hash_4_value = (temp ^ ((uint32_t)(cur[2]) << 8) ^ \
-			^ hash_table[cur[3]] << 5); \
-	const uint32_t hash_value \
-			= (hash_4_value ^ (hash_table[cur[4]] << 3)) \
-				& mf->hash_mask; \
-	hash_4_value &= HASH_4_MASK
-
-/*
-#define hash_zip_calc() \
-	const uint32_t hash_value \
-			= (((uint32_t)(cur[0]) | ((uint32_t)(cur[1]) << 8)) \
-				^ hash_table[cur[2]]) & 0xFFFF
-*/
-
-#define hash_zip_calc() \
-	const uint32_t hash_value \
-			= (((uint32_t)(cur[2]) | ((uint32_t)(cur[0]) << 8)) \
-				^ hash_table[cur[1]]) & 0xFFFF
-
-#define mt_hash_2_calc() \
-	const uint32_t hash_2_value \
-			= (hash_table[cur[0]] ^ cur[1]) & HASH_2_MASK
-
-#define mt_hash_3_calc() \
-	const uint32_t temp = hash_table[cur[0]] ^ cur[1]; \
-	const uint32_t hash_2_value = temp & HASH_2_MASK; \
-	const uint32_t hash_3_value \
-			= (temp ^ ((uint32_t)(cur[2]) << 8)) & HASH_3_MASK
-
-#define mt_hash_4_calc() \
-	const uint32_t temp = hash_table[cur[0]] ^ cur[1]; \
-	const uint32_t hash_2_value = temp & HASH_2_MASK; \
-	const uint32_t hash_3_value \
-			= (temp ^ ((uint32_t)(cur[2]) << 8)) & HASH_3_MASK; \
-	const uint32_t hash_4_value = (temp ^ ((uint32_t)(cur[2]) << 8) ^ \
-			(hash_table[cur[3]] << 5)) & HASH_4_MASK
-
-#endif
+/////////////////////////////////////////////////////////////////////////////// 
+// 
+/// \file       lz_encoder_hash.h 
+/// \brief      Hash macros for match finders 
+// 
+//  Author:     Igor Pavlov 
+// 
+//  This file has been put into the public domain. 
+//  You can do whatever you want with this file. 
+// 
+/////////////////////////////////////////////////////////////////////////////// 
+ 
+#ifndef LZMA_LZ_ENCODER_HASH_H 
+#define LZMA_LZ_ENCODER_HASH_H 
+ 
+#if defined(WORDS_BIGENDIAN) && !defined(HAVE_SMALL) 
+	// This is to make liblzma produce the same output on big endian 
+	// systems that it does on little endian systems. lz_encoder.c 
+	// takes care of including the actual table. 
+	extern const uint32_t lzma_lz_hash_table[256]; 
+#	define hash_table lzma_lz_hash_table 
+#else 
+#	include "check.h" 
+#	define hash_table lzma_crc32_table[0] 
+#endif 
+ 
+#define HASH_2_SIZE (UINT32_C(1) << 10) 
+#define HASH_3_SIZE (UINT32_C(1) << 16) 
+#define HASH_4_SIZE (UINT32_C(1) << 20) 
+ 
+#define HASH_2_MASK (HASH_2_SIZE - 1) 
+#define HASH_3_MASK (HASH_3_SIZE - 1) 
+#define HASH_4_MASK (HASH_4_SIZE - 1) 
+ 
+#define FIX_3_HASH_SIZE (HASH_2_SIZE) 
+#define FIX_4_HASH_SIZE (HASH_2_SIZE + HASH_3_SIZE) 
+#define FIX_5_HASH_SIZE (HASH_2_SIZE + HASH_3_SIZE + HASH_4_SIZE) 
+ 
+// Endianness doesn't matter in hash_2_calc() (no effect on the output). 
+#ifdef TUKLIB_FAST_UNALIGNED_ACCESS 
+#	define hash_2_calc() \ 
+		const uint32_t hash_value = *(const uint16_t *)(cur) 
+#else 
+#	define hash_2_calc() \ 
+		const uint32_t hash_value \ 
+			= (uint32_t)(cur[0]) | ((uint32_t)(cur[1]) << 8) 
+#endif 
+ 
+#define hash_3_calc() \ 
+	const uint32_t temp = hash_table[cur[0]] ^ cur[1]; \ 
+	const uint32_t hash_2_value = temp & HASH_2_MASK; \ 
+	const uint32_t hash_value \ 
+			= (temp ^ ((uint32_t)(cur[2]) << 8)) & mf->hash_mask 
+ 
+#define hash_4_calc() \ 
+	const uint32_t temp = hash_table[cur[0]] ^ cur[1]; \ 
+	const uint32_t hash_2_value = temp & HASH_2_MASK; \ 
+	const uint32_t hash_3_value \ 
+			= (temp ^ ((uint32_t)(cur[2]) << 8)) & HASH_3_MASK; \ 
+	const uint32_t hash_value = (temp ^ ((uint32_t)(cur[2]) << 8) \ 
+			^ (hash_table[cur[3]] << 5)) & mf->hash_mask 
+ 
+ 
+// The following are not currently used. 
+ 
+#define hash_5_calc() \ 
+	const uint32_t temp = hash_table[cur[0]] ^ cur[1]; \ 
+	const uint32_t hash_2_value = temp & HASH_2_MASK; \ 
+	const uint32_t hash_3_value \ 
+			= (temp ^ ((uint32_t)(cur[2]) << 8)) & HASH_3_MASK; \ 
+	uint32_t hash_4_value = (temp ^ ((uint32_t)(cur[2]) << 8) ^ \ 
+			^ hash_table[cur[3]] << 5); \ 
+	const uint32_t hash_value \ 
+			= (hash_4_value ^ (hash_table[cur[4]] << 3)) \ 
+				& mf->hash_mask; \ 
+	hash_4_value &= HASH_4_MASK 
+ 
+/* 
+#define hash_zip_calc() \ 
+	const uint32_t hash_value \ 
+			= (((uint32_t)(cur[0]) | ((uint32_t)(cur[1]) << 8)) \ 
+				^ hash_table[cur[2]]) & 0xFFFF 
+*/ 
+ 
+#define hash_zip_calc() \ 
+	const uint32_t hash_value \ 
+			= (((uint32_t)(cur[2]) | ((uint32_t)(cur[0]) << 8)) \ 
+				^ hash_table[cur[1]]) & 0xFFFF 
+ 
+#define mt_hash_2_calc() \ 
+	const uint32_t hash_2_value \ 
+			= (hash_table[cur[0]] ^ cur[1]) & HASH_2_MASK 
+ 
+#define mt_hash_3_calc() \ 
+	const uint32_t temp = hash_table[cur[0]] ^ cur[1]; \ 
+	const uint32_t hash_2_value = temp & HASH_2_MASK; \ 
+	const uint32_t hash_3_value \ 
+			= (temp ^ ((uint32_t)(cur[2]) << 8)) & HASH_3_MASK 
+ 
+#define mt_hash_4_calc() \ 
+	const uint32_t temp = hash_table[cur[0]] ^ cur[1]; \ 
+	const uint32_t hash_2_value = temp & HASH_2_MASK; \ 
+	const uint32_t hash_3_value \ 
+			= (temp ^ ((uint32_t)(cur[2]) << 8)) & HASH_3_MASK; \ 
+	const uint32_t hash_4_value = (temp ^ ((uint32_t)(cur[2]) << 8) ^ \ 
+			(hash_table[cur[3]] << 5)) & HASH_4_MASK 
+ 
+#endif 
diff --git a/contrib/libs/xz/liblzma/lz/lz_encoder_hash_table.h b/contrib/libs/xz/liblzma/lz/lz_encoder_hash_table.h
index 8c51717d70..a366f7af34 100644
--- a/contrib/libs/xz/liblzma/lz/lz_encoder_hash_table.h
+++ b/contrib/libs/xz/liblzma/lz/lz_encoder_hash_table.h
@@ -1,68 +1,68 @@
-/* This file has been automatically generated by crc32_tablegen.c. */
-
-const uint32_t lzma_lz_hash_table[256] = {
-	0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA,
-	0x076DC419, 0x706AF48F, 0xE963A535, 0x9E6495A3,
-	0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988,
-	0x09B64C2B, 0x7EB17CBD, 0xE7B82D07, 0x90BF1D91,
-	0x1DB71064, 0x6AB020F2, 0xF3B97148, 0x84BE41DE,
-	0x1ADAD47D, 0x6DDDE4EB, 0xF4D4B551, 0x83D385C7,
-	0x136C9856, 0x646BA8C0, 0xFD62F97A, 0x8A65C9EC,
-	0x14015C4F, 0x63066CD9, 0xFA0F3D63, 0x8D080DF5,
-	0x3B6E20C8, 0x4C69105E, 0xD56041E4, 0xA2677172,
-	0x3C03E4D1, 0x4B04D447, 0xD20D85FD, 0xA50AB56B,
-	0x35B5A8FA, 0x42B2986C, 0xDBBBC9D6, 0xACBCF940,
-	0x32D86CE3, 0x45DF5C75, 0xDCD60DCF, 0xABD13D59,
-	0x26D930AC, 0x51DE003A, 0xC8D75180, 0xBFD06116,
-	0x21B4F4B5, 0x56B3C423, 0xCFBA9599, 0xB8BDA50F,
-	0x2802B89E, 0x5F058808, 0xC60CD9B2, 0xB10BE924,
-	0x2F6F7C87, 0x58684C11, 0xC1611DAB, 0xB6662D3D,
-	0x76DC4190, 0x01DB7106, 0x98D220BC, 0xEFD5102A,
-	0x71B18589, 0x06B6B51F, 0x9FBFE4A5, 0xE8B8D433,
-	0x7807C9A2, 0x0F00F934, 0x9609A88E, 0xE10E9818,
-	0x7F6A0DBB, 0x086D3D2D, 0x91646C97, 0xE6635C01,
-	0x6B6B51F4, 0x1C6C6162, 0x856530D8, 0xF262004E,
-	0x6C0695ED, 0x1B01A57B, 0x8208F4C1, 0xF50FC457,
-	0x65B0D9C6, 0x12B7E950, 0x8BBEB8EA, 0xFCB9887C,
-	0x62DD1DDF, 0x15DA2D49, 0x8CD37CF3, 0xFBD44C65,
-	0x4DB26158, 0x3AB551CE, 0xA3BC0074, 0xD4BB30E2,
-	0x4ADFA541, 0x3DD895D7, 0xA4D1C46D, 0xD3D6F4FB,
-	0x4369E96A, 0x346ED9FC, 0xAD678846, 0xDA60B8D0,
-	0x44042D73, 0x33031DE5, 0xAA0A4C5F, 0xDD0D7CC9,
-	0x5005713C, 0x270241AA, 0xBE0B1010, 0xC90C2086,
-	0x5768B525, 0x206F85B3, 0xB966D409, 0xCE61E49F,
-	0x5EDEF90E, 0x29D9C998, 0xB0D09822, 0xC7D7A8B4,
-	0x59B33D17, 0x2EB40D81, 0xB7BD5C3B, 0xC0BA6CAD,
-	0xEDB88320, 0x9ABFB3B6, 0x03B6E20C, 0x74B1D29A,
-	0xEAD54739, 0x9DD277AF, 0x04DB2615, 0x73DC1683,
-	0xE3630B12, 0x94643B84, 0x0D6D6A3E, 0x7A6A5AA8,
-	0xE40ECF0B, 0x9309FF9D, 0x0A00AE27, 0x7D079EB1,
-	0xF00F9344, 0x8708A3D2, 0x1E01F268, 0x6906C2FE,
-	0xF762575D, 0x806567CB, 0x196C3671, 0x6E6B06E7,
-	0xFED41B76, 0x89D32BE0, 0x10DA7A5A, 0x67DD4ACC,
-	0xF9B9DF6F, 0x8EBEEFF9, 0x17B7BE43, 0x60B08ED5,
-	0xD6D6A3E8, 0xA1D1937E, 0x38D8C2C4, 0x4FDFF252,
-	0xD1BB67F1, 0xA6BC5767, 0x3FB506DD, 0x48B2364B,
-	0xD80D2BDA, 0xAF0A1B4C, 0x36034AF6, 0x41047A60,
-	0xDF60EFC3, 0xA867DF55, 0x316E8EEF, 0x4669BE79,
-	0xCB61B38C, 0xBC66831A, 0x256FD2A0, 0x5268E236,
-	0xCC0C7795, 0xBB0B4703, 0x220216B9, 0x5505262F,
-	0xC5BA3BBE, 0xB2BD0B28, 0x2BB45A92, 0x5CB36A04,
-	0xC2D7FFA7, 0xB5D0CF31, 0x2CD99E8B, 0x5BDEAE1D,
-	0x9B64C2B0, 0xEC63F226, 0x756AA39C, 0x026D930A,
-	0x9C0906A9, 0xEB0E363F, 0x72076785, 0x05005713,
-	0x95BF4A82, 0xE2B87A14, 0x7BB12BAE, 0x0CB61B38,
-	0x92D28E9B, 0xE5D5BE0D, 0x7CDCEFB7, 0x0BDBDF21,
-	0x86D3D2D4, 0xF1D4E242, 0x68DDB3F8, 0x1FDA836E,
-	0x81BE16CD, 0xF6B9265B, 0x6FB077E1, 0x18B74777,
-	0x88085AE6, 0xFF0F6A70, 0x66063BCA, 0x11010B5C,
-	0x8F659EFF, 0xF862AE69, 0x616BFFD3, 0x166CCF45,
-	0xA00AE278, 0xD70DD2EE, 0x4E048354, 0x3903B3C2,
-	0xA7672661, 0xD06016F7, 0x4969474D, 0x3E6E77DB,
-	0xAED16A4A, 0xD9D65ADC, 0x40DF0B66, 0x37D83BF0,
-	0xA9BCAE53, 0xDEBB9EC5, 0x47B2CF7F, 0x30B5FFE9,
-	0xBDBDF21C, 0xCABAC28A, 0x53B39330, 0x24B4A3A6,
-	0xBAD03605, 0xCDD70693, 0x54DE5729, 0x23D967BF,
-	0xB3667A2E, 0xC4614AB8, 0x5D681B02, 0x2A6F2B94,
-	0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D
-};
+/* This file has been automatically generated by crc32_tablegen.c. */ 
+ 
+const uint32_t lzma_lz_hash_table[256] = { 
+	0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA, 
+	0x076DC419, 0x706AF48F, 0xE963A535, 0x9E6495A3, 
+	0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988, 
+	0x09B64C2B, 0x7EB17CBD, 0xE7B82D07, 0x90BF1D91, 
+	0x1DB71064, 0x6AB020F2, 0xF3B97148, 0x84BE41DE, 
+	0x1ADAD47D, 0x6DDDE4EB, 0xF4D4B551, 0x83D385C7, 
+	0x136C9856, 0x646BA8C0, 0xFD62F97A, 0x8A65C9EC, 
+	0x14015C4F, 0x63066CD9, 0xFA0F3D63, 0x8D080DF5, 
+	0x3B6E20C8, 0x4C69105E, 0xD56041E4, 0xA2677172, 
+	0x3C03E4D1, 0x4B04D447, 0xD20D85FD, 0xA50AB56B, 
+	0x35B5A8FA, 0x42B2986C, 0xDBBBC9D6, 0xACBCF940, 
+	0x32D86CE3, 0x45DF5C75, 0xDCD60DCF, 0xABD13D59, 
+	0x26D930AC, 0x51DE003A, 0xC8D75180, 0xBFD06116, 
+	0x21B4F4B5, 0x56B3C423, 0xCFBA9599, 0xB8BDA50F, 
+	0x2802B89E, 0x5F058808, 0xC60CD9B2, 0xB10BE924, 
+	0x2F6F7C87, 0x58684C11, 0xC1611DAB, 0xB6662D3D, 
+	0x76DC4190, 0x01DB7106, 0x98D220BC, 0xEFD5102A, 
+	0x71B18589, 0x06B6B51F, 0x9FBFE4A5, 0xE8B8D433, 
+	0x7807C9A2, 0x0F00F934, 0x9609A88E, 0xE10E9818, 
+	0x7F6A0DBB, 0x086D3D2D, 0x91646C97, 0xE6635C01, 
+	0x6B6B51F4, 0x1C6C6162, 0x856530D8, 0xF262004E, 
+	0x6C0695ED, 0x1B01A57B, 0x8208F4C1, 0xF50FC457, 
+	0x65B0D9C6, 0x12B7E950, 0x8BBEB8EA, 0xFCB9887C, 
+	0x62DD1DDF, 0x15DA2D49, 0x8CD37CF3, 0xFBD44C65, 
+	0x4DB26158, 0x3AB551CE, 0xA3BC0074, 0xD4BB30E2, 
+	0x4ADFA541, 0x3DD895D7, 0xA4D1C46D, 0xD3D6F4FB, 
+	0x4369E96A, 0x346ED9FC, 0xAD678846, 0xDA60B8D0, 
+	0x44042D73, 0x33031DE5, 0xAA0A4C5F, 0xDD0D7CC9, 
+	0x5005713C, 0x270241AA, 0xBE0B1010, 0xC90C2086, 
+	0x5768B525, 0x206F85B3, 0xB966D409, 0xCE61E49F, 
+	0x5EDEF90E, 0x29D9C998, 0xB0D09822, 0xC7D7A8B4, 
+	0x59B33D17, 0x2EB40D81, 0xB7BD5C3B, 0xC0BA6CAD, 
+	0xEDB88320, 0x9ABFB3B6, 0x03B6E20C, 0x74B1D29A, 
+	0xEAD54739, 0x9DD277AF, 0x04DB2615, 0x73DC1683, 
+	0xE3630B12, 0x94643B84, 0x0D6D6A3E, 0x7A6A5AA8, 
+	0xE40ECF0B, 0x9309FF9D, 0x0A00AE27, 0x7D079EB1, 
+	0xF00F9344, 0x8708A3D2, 0x1E01F268, 0x6906C2FE, 
+	0xF762575D, 0x806567CB, 0x196C3671, 0x6E6B06E7, 
+	0xFED41B76, 0x89D32BE0, 0x10DA7A5A, 0x67DD4ACC, 
+	0xF9B9DF6F, 0x8EBEEFF9, 0x17B7BE43, 0x60B08ED5, 
+	0xD6D6A3E8, 0xA1D1937E, 0x38D8C2C4, 0x4FDFF252, 
+	0xD1BB67F1, 0xA6BC5767, 0x3FB506DD, 0x48B2364B, 
+	0xD80D2BDA, 0xAF0A1B4C, 0x36034AF6, 0x41047A60, 
+	0xDF60EFC3, 0xA867DF55, 0x316E8EEF, 0x4669BE79, 
+	0xCB61B38C, 0xBC66831A, 0x256FD2A0, 0x5268E236, 
+	0xCC0C7795, 0xBB0B4703, 0x220216B9, 0x5505262F, 
+	0xC5BA3BBE, 0xB2BD0B28, 0x2BB45A92, 0x5CB36A04, 
+	0xC2D7FFA7, 0xB5D0CF31, 0x2CD99E8B, 0x5BDEAE1D, 
+	0x9B64C2B0, 0xEC63F226, 0x756AA39C, 0x026D930A, 
+	0x9C0906A9, 0xEB0E363F, 0x72076785, 0x05005713, 
+	0x95BF4A82, 0xE2B87A14, 0x7BB12BAE, 0x0CB61B38, 
+	0x92D28E9B, 0xE5D5BE0D, 0x7CDCEFB7, 0x0BDBDF21, 
+	0x86D3D2D4, 0xF1D4E242, 0x68DDB3F8, 0x1FDA836E, 
+	0x81BE16CD, 0xF6B9265B, 0x6FB077E1, 0x18B74777, 
+	0x88085AE6, 0xFF0F6A70, 0x66063BCA, 0x11010B5C, 
+	0x8F659EFF, 0xF862AE69, 0x616BFFD3, 0x166CCF45, 
+	0xA00AE278, 0xD70DD2EE, 0x4E048354, 0x3903B3C2, 
+	0xA7672661, 0xD06016F7, 0x4969474D, 0x3E6E77DB, 
+	0xAED16A4A, 0xD9D65ADC, 0x40DF0B66, 0x37D83BF0, 
+	0xA9BCAE53, 0xDEBB9EC5, 0x47B2CF7F, 0x30B5FFE9, 
+	0xBDBDF21C, 0xCABAC28A, 0x53B39330, 0x24B4A3A6, 
+	0xBAD03605, 0xCDD70693, 0x54DE5729, 0x23D967BF, 
+	0xB3667A2E, 0xC4614AB8, 0x5D681B02, 0x2A6F2B94, 
+	0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D 
+}; 
diff --git a/contrib/libs/xz/liblzma/lz/lz_encoder_mf.c b/contrib/libs/xz/liblzma/lz/lz_encoder_mf.c
index 78520779f1..740e17d718 100644
--- a/contrib/libs/xz/liblzma/lz/lz_encoder_mf.c
+++ b/contrib/libs/xz/liblzma/lz/lz_encoder_mf.c
@@ -1,744 +1,744 @@
-///////////////////////////////////////////////////////////////////////////////
-//
-/// \file       lz_encoder_mf.c
-/// \brief      Match finders
-///
-//  Authors:    Igor Pavlov
-//              Lasse Collin
-//
-//  This file has been put into the public domain.
-//  You can do whatever you want with this file.
-//
-///////////////////////////////////////////////////////////////////////////////
-
-#include "lz_encoder.h"
-#include "lz_encoder_hash.h"
-#include "memcmplen.h"
-
-
-/// \brief      Find matches starting from the current byte
-///
-/// \return     The length of the longest match found
-extern uint32_t
-lzma_mf_find(lzma_mf *mf, uint32_t *count_ptr, lzma_match *matches)
-{
-	// Call the match finder. It returns the number of length-distance
-	// pairs found.
-	// FIXME: Minimum count is zero, what _exactly_ is the maximum?
-	const uint32_t count = mf->find(mf, matches);
-
-	// Length of the longest match; assume that no matches were found
-	// and thus the maximum length is zero.
-	uint32_t len_best = 0;
-
-	if (count > 0) {
-#ifndef NDEBUG
-		// Validate the matches.
-		for (uint32_t i = 0; i < count; ++i) {
-			assert(matches[i].len <= mf->nice_len);
-			assert(matches[i].dist < mf->read_pos);
-			assert(memcmp(mf_ptr(mf) - 1,
-				mf_ptr(mf) - matches[i].dist - 2,
-				matches[i].len) == 0);
-		}
-#endif
-
-		// The last used element in the array contains
-		// the longest match.
-		len_best = matches[count - 1].len;
-
-		// If a match of maximum search length was found, try to
-		// extend the match to maximum possible length.
-		if (len_best == mf->nice_len) {
-			// The limit for the match length is either the
-			// maximum match length supported by the LZ-based
-			// encoder or the number of bytes left in the
-			// dictionary, whichever is smaller.
-			uint32_t limit = mf_avail(mf) + 1;
-			if (limit > mf->match_len_max)
-				limit = mf->match_len_max;
-
-			// Pointer to the byte we just ran through
-			// the match finder.
-			const uint8_t *p1 = mf_ptr(mf) - 1;
-
-			// Pointer to the beginning of the match. We need -1
-			// here because the match distances are zero based.
-			const uint8_t *p2 = p1 - matches[count - 1].dist - 1;
-
-			len_best = lzma_memcmplen(p1, p2, len_best, limit);
-		}
-	}
-
-	*count_ptr = count;
-
-	// Finally update the read position to indicate that match finder was
-	// run for this dictionary offset.
-	++mf->read_ahead;
-
-	return len_best;
-}
-
-
-/// Hash value to indicate unused element in the hash. Since we start the
-/// positions from dict_size + 1, zero is always too far to qualify
-/// as usable match position.
-#define EMPTY_HASH_VALUE 0
-
-
-/// Normalization must be done when lzma_mf.offset + lzma_mf.read_pos
-/// reaches MUST_NORMALIZE_POS.
-#define MUST_NORMALIZE_POS UINT32_MAX
-
-
-/// \brief      Normalizes hash values
-///
-/// The hash arrays store positions of match candidates. The positions are
-/// relative to an arbitrary offset that is not the same as the absolute
-/// offset in the input stream. The relative position of the current byte
-/// is lzma_mf.offset + lzma_mf.read_pos. The distances of the matches are
-/// the differences of the current read position and the position found from
-/// the hash.
-///
-/// To prevent integer overflows of the offsets stored in the hash arrays,
-/// we need to "normalize" the stored values now and then. During the
-/// normalization, we drop values that indicate distance greater than the
-/// dictionary size, thus making space for new values.
-static void
-normalize(lzma_mf *mf)
-{
-	assert(mf->read_pos + mf->offset == MUST_NORMALIZE_POS);
-
-	// In future we may not want to touch the lowest bits, because there
-	// may be match finders that use larger resolution than one byte.
-	const uint32_t subvalue
-			= (MUST_NORMALIZE_POS - mf->cyclic_size);
-				// & (~(UINT32_C(1) << 10) - 1);
-
-	for (uint32_t i = 0; i < mf->hash_count; ++i) {
-		// If the distance is greater than the dictionary size,
-		// we can simply mark the hash element as empty.
-		if (mf->hash[i] <= subvalue)
-			mf->hash[i] = EMPTY_HASH_VALUE;
-		else
-			mf->hash[i] -= subvalue;
-	}
-
-	for (uint32_t i = 0; i < mf->sons_count; ++i) {
-		// Do the same for mf->son.
-		//
-		// NOTE: There may be uninitialized elements in mf->son.
-		// Valgrind may complain that the "if" below depends on
-		// an uninitialized value. In this case it is safe to ignore
-		// the warning. See also the comments in lz_encoder_init()
-		// in lz_encoder.c.
-		if (mf->son[i] <= subvalue)
-			mf->son[i] = EMPTY_HASH_VALUE;
-		else
-			mf->son[i] -= subvalue;
-	}
-
-	// Update offset to match the new locations.
-	mf->offset -= subvalue;
-
-	return;
-}
-
-
-/// Mark the current byte as processed from point of view of the match finder.
-static void
-move_pos(lzma_mf *mf)
-{
-	if (++mf->cyclic_pos == mf->cyclic_size)
-		mf->cyclic_pos = 0;
-
-	++mf->read_pos;
-	assert(mf->read_pos <= mf->write_pos);
-
-	if (unlikely(mf->read_pos + mf->offset == UINT32_MAX))
-		normalize(mf);
-}
-
-
-/// When flushing, we cannot run the match finder unless there is nice_len
-/// bytes available in the dictionary. Instead, we skip running the match
-/// finder (indicating that no match was found), and count how many bytes we
-/// have ignored this way.
-///
-/// When new data is given after the flushing was completed, the match finder
-/// is restarted by rewinding mf->read_pos backwards by mf->pending. Then
-/// the missed bytes are added to the hash using the match finder's skip
-/// function (with small amount of input, it may start using mf->pending
-/// again if flushing).
-///
-/// Due to this rewinding, we don't touch cyclic_pos or test for
-/// normalization. It will be done when the match finder's skip function
-/// catches up after a flush.
-static void
-move_pending(lzma_mf *mf)
-{
-	++mf->read_pos;
-	assert(mf->read_pos <= mf->write_pos);
-	++mf->pending;
-}
-
-
-/// Calculate len_limit and determine if there is enough input to run
-/// the actual match finder code. Sets up "cur" and "pos". This macro
-/// is used by all find functions and binary tree skip functions. Hash
-/// chain skip function doesn't need len_limit so a simpler code is used
-/// in them.
-#define header(is_bt, len_min, ret_op) \
-	uint32_t len_limit = mf_avail(mf); \
-	if (mf->nice_len <= len_limit) { \
-		len_limit = mf->nice_len; \
-	} else if (len_limit < (len_min) \
-			|| (is_bt && mf->action == LZMA_SYNC_FLUSH)) { \
-		assert(mf->action != LZMA_RUN); \
-		move_pending(mf); \
-		ret_op; \
-	} \
-	const uint8_t *cur = mf_ptr(mf); \
-	const uint32_t pos = mf->read_pos + mf->offset
-
-
-/// Header for find functions. "return 0" indicates that zero matches
-/// were found.
-#define header_find(is_bt, len_min) \
-	header(is_bt, len_min, return 0); \
-	uint32_t matches_count = 0
-
-
-/// Header for a loop in a skip function. "continue" tells to skip the rest
-/// of the code in the loop.
-#define header_skip(is_bt, len_min) \
-	header(is_bt, len_min, continue)
-
-
-/// Calls hc_find_func() or bt_find_func() and calculates the total number
-/// of matches found. Updates the dictionary position and returns the number
-/// of matches found.
-#define call_find(func, len_best) \
-do { \
-	matches_count = func(len_limit, pos, cur, cur_match, mf->depth, \
-				mf->son, mf->cyclic_pos, mf->cyclic_size, \
-				matches + matches_count, len_best) \
-			- matches; \
-	move_pos(mf); \
-	return matches_count; \
-} while (0)
-
-
-////////////////
-// Hash Chain //
-////////////////
-
-#if defined(HAVE_MF_HC3) || defined(HAVE_MF_HC4)
-///
-///
-/// \param      len_limit       Don't look for matches longer than len_limit.
-/// \param      pos             lzma_mf.read_pos + lzma_mf.offset
-/// \param      cur             Pointer to current byte (mf_ptr(mf))
-/// \param      cur_match       Start position of the current match candidate
-/// \param      depth           Maximum length of the hash chain
-/// \param      son             lzma_mf.son (contains the hash chain)
-/// \param      cyclic_pos
-/// \param      cyclic_size
-/// \param      matches         Array to hold the matches.
-/// \param      len_best        The length of the longest match found so far.
-static lzma_match *
-hc_find_func(
-		const uint32_t len_limit,
-		const uint32_t pos,
-		const uint8_t *const cur,
-		uint32_t cur_match,
-		uint32_t depth,
-		uint32_t *const son,
-		const uint32_t cyclic_pos,
-		const uint32_t cyclic_size,
-		lzma_match *matches,
-		uint32_t len_best)
-{
-	son[cyclic_pos] = cur_match;
-
-	while (true) {
-		const uint32_t delta = pos - cur_match;
-		if (depth-- == 0 || delta >= cyclic_size)
-			return matches;
-
-		const uint8_t *const pb = cur - delta;
-		cur_match = son[cyclic_pos - delta
-				+ (delta > cyclic_pos ? cyclic_size : 0)];
-
-		if (pb[len_best] == cur[len_best] && pb[0] == cur[0]) {
-			uint32_t len = lzma_memcmplen(pb, cur, 1, len_limit);
-
-			if (len_best < len) {
-				len_best = len;
-				matches->len = len;
-				matches->dist = delta - 1;
-				++matches;
-
-				if (len == len_limit)
-					return matches;
-			}
-		}
-	}
-}
-
-
-#define hc_find(len_best) \
-	call_find(hc_find_func, len_best)
-
-
-#define hc_skip() \
-do { \
-	mf->son[mf->cyclic_pos] = cur_match; \
-	move_pos(mf); \
-} while (0)
-
-#endif
-
-
-#ifdef HAVE_MF_HC3
-extern uint32_t
-lzma_mf_hc3_find(lzma_mf *mf, lzma_match *matches)
-{
-	header_find(false, 3);
-
-	hash_3_calc();
-
-	const uint32_t delta2 = pos - mf->hash[hash_2_value];
-	const uint32_t cur_match = mf->hash[FIX_3_HASH_SIZE + hash_value];
-
-	mf->hash[hash_2_value] = pos;
-	mf->hash[FIX_3_HASH_SIZE + hash_value] = pos;
-
-	uint32_t len_best = 2;
-
-	if (delta2 < mf->cyclic_size && *(cur - delta2) == *cur) {
-		len_best = lzma_memcmplen(cur - delta2, cur,
-				len_best, len_limit);
-
-		matches[0].len = len_best;
-		matches[0].dist = delta2 - 1;
-		matches_count = 1;
-
-		if (len_best == len_limit) {
-			hc_skip();
-			return 1; // matches_count
-		}
-	}
-
-	hc_find(len_best);
-}
-
-
-extern void
-lzma_mf_hc3_skip(lzma_mf *mf, uint32_t amount)
-{
-	do {
-		if (mf_avail(mf) < 3) {
-			move_pending(mf);
-			continue;
-		}
-
-		const uint8_t *cur = mf_ptr(mf);
-		const uint32_t pos = mf->read_pos + mf->offset;
-
-		hash_3_calc();
-
-		const uint32_t cur_match
-				= mf->hash[FIX_3_HASH_SIZE + hash_value];
-
-		mf->hash[hash_2_value] = pos;
-		mf->hash[FIX_3_HASH_SIZE + hash_value] = pos;
-
-		hc_skip();
-
-	} while (--amount != 0);
-}
-#endif
-
-
-#ifdef HAVE_MF_HC4
-extern uint32_t
-lzma_mf_hc4_find(lzma_mf *mf, lzma_match *matches)
-{
-	header_find(false, 4);
-
-	hash_4_calc();
-
-	uint32_t delta2 = pos - mf->hash[hash_2_value];
-	const uint32_t delta3
-			= pos - mf->hash[FIX_3_HASH_SIZE + hash_3_value];
-	const uint32_t cur_match = mf->hash[FIX_4_HASH_SIZE + hash_value];
-
-	mf->hash[hash_2_value ] = pos;
-	mf->hash[FIX_3_HASH_SIZE + hash_3_value] = pos;
-	mf->hash[FIX_4_HASH_SIZE + hash_value] = pos;
-
-	uint32_t len_best = 1;
-
-	if (delta2 < mf->cyclic_size && *(cur - delta2) == *cur) {
-		len_best = 2;
-		matches[0].len = 2;
-		matches[0].dist = delta2 - 1;
-		matches_count = 1;
-	}
-
-	if (delta2 != delta3 && delta3 < mf->cyclic_size
-			&& *(cur - delta3) == *cur) {
-		len_best = 3;
-		matches[matches_count++].dist = delta3 - 1;
-		delta2 = delta3;
-	}
-
-	if (matches_count != 0) {
-		len_best = lzma_memcmplen(cur - delta2, cur,
-				len_best, len_limit);
-
-		matches[matches_count - 1].len = len_best;
-
-		if (len_best == len_limit) {
-			hc_skip();
-			return matches_count;
-		}
-	}
-
-	if (len_best < 3)
-		len_best = 3;
-
-	hc_find(len_best);
-}
-
-
-extern void
-lzma_mf_hc4_skip(lzma_mf *mf, uint32_t amount)
-{
-	do {
-		if (mf_avail(mf) < 4) {
-			move_pending(mf);
-			continue;
-		}
-
-		const uint8_t *cur = mf_ptr(mf);
-		const uint32_t pos = mf->read_pos + mf->offset;
-
-		hash_4_calc();
-
-		const uint32_t cur_match
-				= mf->hash[FIX_4_HASH_SIZE + hash_value];
-
-		mf->hash[hash_2_value] = pos;
-		mf->hash[FIX_3_HASH_SIZE + hash_3_value] = pos;
-		mf->hash[FIX_4_HASH_SIZE + hash_value] = pos;
-
-		hc_skip();
-
-	} while (--amount != 0);
-}
-#endif
-
-
-/////////////////
-// Binary Tree //
-/////////////////
-
-#if defined(HAVE_MF_BT2) || defined(HAVE_MF_BT3) || defined(HAVE_MF_BT4)
-static lzma_match *
-bt_find_func(
-		const uint32_t len_limit,
-		const uint32_t pos,
-		const uint8_t *const cur,
-		uint32_t cur_match,
-		uint32_t depth,
-		uint32_t *const son,
-		const uint32_t cyclic_pos,
-		const uint32_t cyclic_size,
-		lzma_match *matches,
-		uint32_t len_best)
-{
-	uint32_t *ptr0 = son + (cyclic_pos << 1) + 1;
-	uint32_t *ptr1 = son + (cyclic_pos << 1);
-
-	uint32_t len0 = 0;
-	uint32_t len1 = 0;
-
-	while (true) {
-		const uint32_t delta = pos - cur_match;
-		if (depth-- == 0 || delta >= cyclic_size) {
-			*ptr0 = EMPTY_HASH_VALUE;
-			*ptr1 = EMPTY_HASH_VALUE;
-			return matches;
-		}
-
-		uint32_t *const pair = son + ((cyclic_pos - delta
-				+ (delta > cyclic_pos ? cyclic_size : 0))
-				<< 1);
-
-		const uint8_t *const pb = cur - delta;
-		uint32_t len = my_min(len0, len1);
-
-		if (pb[len] == cur[len]) {
-			len = lzma_memcmplen(pb, cur, len + 1, len_limit);
-
-			if (len_best < len) {
-				len_best = len;
-				matches->len = len;
-				matches->dist = delta - 1;
-				++matches;
-
-				if (len == len_limit) {
-					*ptr1 = pair[0];
-					*ptr0 = pair[1];
-					return matches;
-				}
-			}
-		}
-
-		if (pb[len] < cur[len]) {
-			*ptr1 = cur_match;
-			ptr1 = pair + 1;
-			cur_match = *ptr1;
-			len1 = len;
-		} else {
-			*ptr0 = cur_match;
-			ptr0 = pair;
-			cur_match = *ptr0;
-			len0 = len;
-		}
-	}
-}
-
-
-static void
-bt_skip_func(
-		const uint32_t len_limit,
-		const uint32_t pos,
-		const uint8_t *const cur,
-		uint32_t cur_match,
-		uint32_t depth,
-		uint32_t *const son,
-		const uint32_t cyclic_pos,
-		const uint32_t cyclic_size)
-{
-	uint32_t *ptr0 = son + (cyclic_pos << 1) + 1;
-	uint32_t *ptr1 = son + (cyclic_pos << 1);
-
-	uint32_t len0 = 0;
-	uint32_t len1 = 0;
-
-	while (true) {
-		const uint32_t delta = pos - cur_match;
-		if (depth-- == 0 || delta >= cyclic_size) {
-			*ptr0 = EMPTY_HASH_VALUE;
-			*ptr1 = EMPTY_HASH_VALUE;
-			return;
-		}
-
-		uint32_t *pair = son + ((cyclic_pos - delta
-				+ (delta > cyclic_pos ? cyclic_size : 0))
-				<< 1);
-		const uint8_t *pb = cur - delta;
-		uint32_t len = my_min(len0, len1);
-
-		if (pb[len] == cur[len]) {
-			len = lzma_memcmplen(pb, cur, len + 1, len_limit);
-
-			if (len == len_limit) {
-				*ptr1 = pair[0];
-				*ptr0 = pair[1];
-				return;
-			}
-		}
-
-		if (pb[len] < cur[len]) {
-			*ptr1 = cur_match;
-			ptr1 = pair + 1;
-			cur_match = *ptr1;
-			len1 = len;
-		} else {
-			*ptr0 = cur_match;
-			ptr0 = pair;
-			cur_match = *ptr0;
-			len0 = len;
-		}
-	}
-}
-
-
-#define bt_find(len_best) \
-	call_find(bt_find_func, len_best)
-
-#define bt_skip() \
-do { \
-	bt_skip_func(len_limit, pos, cur, cur_match, mf->depth, \
-			mf->son, mf->cyclic_pos, \
-			mf->cyclic_size); \
-	move_pos(mf); \
-} while (0)
-
-#endif
-
-
-#ifdef HAVE_MF_BT2
-extern uint32_t
-lzma_mf_bt2_find(lzma_mf *mf, lzma_match *matches)
-{
-	header_find(true, 2);
-
-	hash_2_calc();
-
-	const uint32_t cur_match = mf->hash[hash_value];
-	mf->hash[hash_value] = pos;
-
-	bt_find(1);
-}
-
-
-extern void
-lzma_mf_bt2_skip(lzma_mf *mf, uint32_t amount)
-{
-	do {
-		header_skip(true, 2);
-
-		hash_2_calc();
-
-		const uint32_t cur_match = mf->hash[hash_value];
-		mf->hash[hash_value] = pos;
-
-		bt_skip();
-
-	} while (--amount != 0);
-}
-#endif
-
-
-#ifdef HAVE_MF_BT3
-extern uint32_t
-lzma_mf_bt3_find(lzma_mf *mf, lzma_match *matches)
-{
-	header_find(true, 3);
-
-	hash_3_calc();
-
-	const uint32_t delta2 = pos - mf->hash[hash_2_value];
-	const uint32_t cur_match = mf->hash[FIX_3_HASH_SIZE + hash_value];
-
-	mf->hash[hash_2_value] = pos;
-	mf->hash[FIX_3_HASH_SIZE + hash_value] = pos;
-
-	uint32_t len_best = 2;
-
-	if (delta2 < mf->cyclic_size && *(cur - delta2) == *cur) {
-		len_best = lzma_memcmplen(
-				cur, cur - delta2, len_best, len_limit);
-
-		matches[0].len = len_best;
-		matches[0].dist = delta2 - 1;
-		matches_count = 1;
-
-		if (len_best == len_limit) {
-			bt_skip();
-			return 1; // matches_count
-		}
-	}
-
-	bt_find(len_best);
-}
-
-
-extern void
-lzma_mf_bt3_skip(lzma_mf *mf, uint32_t amount)
-{
-	do {
-		header_skip(true, 3);
-
-		hash_3_calc();
-
-		const uint32_t cur_match
-				= mf->hash[FIX_3_HASH_SIZE + hash_value];
-
-		mf->hash[hash_2_value] = pos;
-		mf->hash[FIX_3_HASH_SIZE + hash_value] = pos;
-
-		bt_skip();
-
-	} while (--amount != 0);
-}
-#endif
-
-
-#ifdef HAVE_MF_BT4
-extern uint32_t
-lzma_mf_bt4_find(lzma_mf *mf, lzma_match *matches)
-{
-	header_find(true, 4);
-
-	hash_4_calc();
-
-	uint32_t delta2 = pos - mf->hash[hash_2_value];
-	const uint32_t delta3
-			= pos - mf->hash[FIX_3_HASH_SIZE + hash_3_value];
-	const uint32_t cur_match = mf->hash[FIX_4_HASH_SIZE + hash_value];
-
-	mf->hash[hash_2_value] = pos;
-	mf->hash[FIX_3_HASH_SIZE + hash_3_value] = pos;
-	mf->hash[FIX_4_HASH_SIZE + hash_value] = pos;
-
-	uint32_t len_best = 1;
-
-	if (delta2 < mf->cyclic_size && *(cur - delta2) == *cur) {
-		len_best = 2;
-		matches[0].len = 2;
-		matches[0].dist = delta2 - 1;
-		matches_count = 1;
-	}
-
-	if (delta2 != delta3 && delta3 < mf->cyclic_size
-			&& *(cur - delta3) == *cur) {
-		len_best = 3;
-		matches[matches_count++].dist = delta3 - 1;
-		delta2 = delta3;
-	}
-
-	if (matches_count != 0) {
-		len_best = lzma_memcmplen(
-				cur, cur - delta2, len_best, len_limit);
-
-		matches[matches_count - 1].len = len_best;
-
-		if (len_best == len_limit) {
-			bt_skip();
-			return matches_count;
-		}
-	}
-
-	if (len_best < 3)
-		len_best = 3;
-
-	bt_find(len_best);
-}
-
-
-extern void
-lzma_mf_bt4_skip(lzma_mf *mf, uint32_t amount)
-{
-	do {
-		header_skip(true, 4);
-
-		hash_4_calc();
-
-		const uint32_t cur_match
-				= mf->hash[FIX_4_HASH_SIZE + hash_value];
-
-		mf->hash[hash_2_value] = pos;
-		mf->hash[FIX_3_HASH_SIZE + hash_3_value] = pos;
-		mf->hash[FIX_4_HASH_SIZE + hash_value] = pos;
-
-		bt_skip();
-
-	} while (--amount != 0);
-}
-#endif
+/////////////////////////////////////////////////////////////////////////////// 
+// 
+/// \file       lz_encoder_mf.c 
+/// \brief      Match finders 
+/// 
+//  Authors:    Igor Pavlov 
+//              Lasse Collin 
+// 
+//  This file has been put into the public domain. 
+//  You can do whatever you want with this file. 
+// 
+/////////////////////////////////////////////////////////////////////////////// 
+ 
+#include "lz_encoder.h" 
+#include "lz_encoder_hash.h" 
+#include "memcmplen.h" 
+ 
+ 
+/// \brief      Find matches starting from the current byte 
+/// 
+/// \return     The length of the longest match found 
+extern uint32_t 
+lzma_mf_find(lzma_mf *mf, uint32_t *count_ptr, lzma_match *matches) 
+{ 
+	// Call the match finder. It returns the number of length-distance 
+	// pairs found. 
+	// FIXME: Minimum count is zero, what _exactly_ is the maximum? 
+	const uint32_t count = mf->find(mf, matches); 
+ 
+	// Length of the longest match; assume that no matches were found 
+	// and thus the maximum length is zero. 
+	uint32_t len_best = 0; 
+ 
+	if (count > 0) { 
+#ifndef NDEBUG 
+		// Validate the matches. 
+		for (uint32_t i = 0; i < count; ++i) { 
+			assert(matches[i].len <= mf->nice_len); 
+			assert(matches[i].dist < mf->read_pos); 
+			assert(memcmp(mf_ptr(mf) - 1, 
+				mf_ptr(mf) - matches[i].dist - 2, 
+				matches[i].len) == 0); 
+		} 
+#endif 
+ 
+		// The last used element in the array contains 
+		// the longest match. 
+		len_best = matches[count - 1].len; 
+ 
+		// If a match of maximum search length was found, try to 
+		// extend the match to maximum possible length. 
+		if (len_best == mf->nice_len) { 
+			// The limit for the match length is either the 
+			// maximum match length supported by the LZ-based 
+			// encoder or the number of bytes left in the 
+			// dictionary, whichever is smaller. 
+			uint32_t limit = mf_avail(mf) + 1; 
+			if (limit > mf->match_len_max) 
+				limit = mf->match_len_max; 
+ 
+			// Pointer to the byte we just ran through 
+			// the match finder. 
+			const uint8_t *p1 = mf_ptr(mf) - 1; 
+ 
+			// Pointer to the beginning of the match. We need -1 
+			// here because the match distances are zero based. 
+			const uint8_t *p2 = p1 - matches[count - 1].dist - 1; 
+ 
+			len_best = lzma_memcmplen(p1, p2, len_best, limit); 
+		} 
+	} 
+ 
+	*count_ptr = count; 
+ 
+	// Finally update the read position to indicate that match finder was 
+	// run for this dictionary offset. 
+	++mf->read_ahead; 
+ 
+	return len_best; 
+} 
+ 
+ 
+/// Hash value to indicate unused element in the hash. Since we start the 
+/// positions from dict_size + 1, zero is always too far to qualify 
+/// as usable match position. 
+#define EMPTY_HASH_VALUE 0 
+ 
+ 
+/// Normalization must be done when lzma_mf.offset + lzma_mf.read_pos 
+/// reaches MUST_NORMALIZE_POS. 
+#define MUST_NORMALIZE_POS UINT32_MAX 
+ 
+ 
+/// \brief      Normalizes hash values 
+/// 
+/// The hash arrays store positions of match candidates. The positions are 
+/// relative to an arbitrary offset that is not the same as the absolute 
+/// offset in the input stream. The relative position of the current byte 
+/// is lzma_mf.offset + lzma_mf.read_pos. The distances of the matches are 
+/// the differences of the current read position and the position found from 
+/// the hash. 
+/// 
+/// To prevent integer overflows of the offsets stored in the hash arrays, 
+/// we need to "normalize" the stored values now and then. During the 
+/// normalization, we drop values that indicate distance greater than the 
+/// dictionary size, thus making space for new values. 
+static void 
+normalize(lzma_mf *mf) 
+{ 
+	assert(mf->read_pos + mf->offset == MUST_NORMALIZE_POS); 
+ 
+	// In future we may not want to touch the lowest bits, because there 
+	// may be match finders that use larger resolution than one byte. 
+	const uint32_t subvalue 
+			= (MUST_NORMALIZE_POS - mf->cyclic_size); 
+				// & (~(UINT32_C(1) << 10) - 1); 
+ 
+	for (uint32_t i = 0; i < mf->hash_count; ++i) { 
+		// If the distance is greater than the dictionary size, 
+		// we can simply mark the hash element as empty. 
+		if (mf->hash[i] <= subvalue) 
+			mf->hash[i] = EMPTY_HASH_VALUE; 
+		else 
+			mf->hash[i] -= subvalue; 
+	} 
+ 
+	for (uint32_t i = 0; i < mf->sons_count; ++i) { 
+		// Do the same for mf->son. 
+		// 
+		// NOTE: There may be uninitialized elements in mf->son. 
+		// Valgrind may complain that the "if" below depends on 
+		// an uninitialized value. In this case it is safe to ignore 
+		// the warning. See also the comments in lz_encoder_init() 
+		// in lz_encoder.c. 
+		if (mf->son[i] <= subvalue) 
+			mf->son[i] = EMPTY_HASH_VALUE; 
+		else 
+			mf->son[i] -= subvalue; 
+	} 
+ 
+	// Update offset to match the new locations. 
+	mf->offset -= subvalue; 
+ 
+	return; 
+} 
+ 
+ 
+/// Mark the current byte as processed from point of view of the match finder. 
+static void 
+move_pos(lzma_mf *mf) 
+{ 
+	if (++mf->cyclic_pos == mf->cyclic_size) 
+		mf->cyclic_pos = 0; 
+ 
+	++mf->read_pos; 
+	assert(mf->read_pos <= mf->write_pos); 
+ 
+	if (unlikely(mf->read_pos + mf->offset == UINT32_MAX)) 
+		normalize(mf); 
+} 
+ 
+ 
+/// When flushing, we cannot run the match finder unless there is nice_len 
+/// bytes available in the dictionary. Instead, we skip running the match 
+/// finder (indicating that no match was found), and count how many bytes we 
+/// have ignored this way. 
+/// 
+/// When new data is given after the flushing was completed, the match finder 
+/// is restarted by rewinding mf->read_pos backwards by mf->pending. Then 
+/// the missed bytes are added to the hash using the match finder's skip 
+/// function (with small amount of input, it may start using mf->pending 
+/// again if flushing). 
+/// 
+/// Due to this rewinding, we don't touch cyclic_pos or test for 
+/// normalization. It will be done when the match finder's skip function 
+/// catches up after a flush. 
+static void 
+move_pending(lzma_mf *mf) 
+{ 
+	++mf->read_pos; 
+	assert(mf->read_pos <= mf->write_pos); 
+	++mf->pending; 
+} 
+ 
+ 
+/// Calculate len_limit and determine if there is enough input to run 
+/// the actual match finder code. Sets up "cur" and "pos". This macro 
+/// is used by all find functions and binary tree skip functions. Hash 
+/// chain skip function doesn't need len_limit so a simpler code is used 
+/// in them. 
+#define header(is_bt, len_min, ret_op) \ 
+	uint32_t len_limit = mf_avail(mf); \ 
+	if (mf->nice_len <= len_limit) { \ 
+		len_limit = mf->nice_len; \ 
+	} else if (len_limit < (len_min) \ 
+			|| (is_bt && mf->action == LZMA_SYNC_FLUSH)) { \ 
+		assert(mf->action != LZMA_RUN); \ 
+		move_pending(mf); \ 
+		ret_op; \ 
+	} \ 
+	const uint8_t *cur = mf_ptr(mf); \ 
+	const uint32_t pos = mf->read_pos + mf->offset 
+ 
+ 
+/// Header for find functions. "return 0" indicates that zero matches 
+/// were found. 
+#define header_find(is_bt, len_min) \ 
+	header(is_bt, len_min, return 0); \ 
+	uint32_t matches_count = 0 
+ 
+ 
+/// Header for a loop in a skip function. "continue" tells to skip the rest 
+/// of the code in the loop. 
+#define header_skip(is_bt, len_min) \ 
+	header(is_bt, len_min, continue) 
+ 
+ 
+/// Calls hc_find_func() or bt_find_func() and calculates the total number 
+/// of matches found. Updates the dictionary position and returns the number 
+/// of matches found. 
+#define call_find(func, len_best) \ 
+do { \ 
+	matches_count = func(len_limit, pos, cur, cur_match, mf->depth, \ 
+				mf->son, mf->cyclic_pos, mf->cyclic_size, \ 
+				matches + matches_count, len_best) \ 
+			- matches; \ 
+	move_pos(mf); \ 
+	return matches_count; \ 
+} while (0) 
+ 
+ 
+//////////////// 
+// Hash Chain // 
+//////////////// 
+ 
+#if defined(HAVE_MF_HC3) || defined(HAVE_MF_HC4) 
+/// 
+/// 
+/// \param      len_limit       Don't look for matches longer than len_limit. 
+/// \param      pos             lzma_mf.read_pos + lzma_mf.offset 
+/// \param      cur             Pointer to current byte (mf_ptr(mf)) 
+/// \param      cur_match       Start position of the current match candidate 
+/// \param      depth           Maximum length of the hash chain 
+/// \param      son             lzma_mf.son (contains the hash chain) 
+/// \param      cyclic_pos 
+/// \param      cyclic_size 
+/// \param      matches         Array to hold the matches. 
+/// \param      len_best        The length of the longest match found so far. 
+static lzma_match * 
+hc_find_func( 
+		const uint32_t len_limit, 
+		const uint32_t pos, 
+		const uint8_t *const cur, 
+		uint32_t cur_match, 
+		uint32_t depth, 
+		uint32_t *const son, 
+		const uint32_t cyclic_pos, 
+		const uint32_t cyclic_size, 
+		lzma_match *matches, 
+		uint32_t len_best) 
+{ 
+	son[cyclic_pos] = cur_match; 
+ 
+	while (true) { 
+		const uint32_t delta = pos - cur_match; 
+		if (depth-- == 0 || delta >= cyclic_size) 
+			return matches; 
+ 
+		const uint8_t *const pb = cur - delta; 
+		cur_match = son[cyclic_pos - delta 
+				+ (delta > cyclic_pos ? cyclic_size : 0)]; 
+ 
+		if (pb[len_best] == cur[len_best] && pb[0] == cur[0]) { 
+			uint32_t len = lzma_memcmplen(pb, cur, 1, len_limit); 
+ 
+			if (len_best < len) { 
+				len_best = len; 
+				matches->len = len; 
+				matches->dist = delta - 1; 
+				++matches; 
+ 
+				if (len == len_limit) 
+					return matches; 
+			} 
+		} 
+	} 
+} 
+ 
+ 
+#define hc_find(len_best) \ 
+	call_find(hc_find_func, len_best) 
+ 
+ 
+#define hc_skip() \ 
+do { \ 
+	mf->son[mf->cyclic_pos] = cur_match; \ 
+	move_pos(mf); \ 
+} while (0) 
+ 
+#endif 
+ 
+ 
+#ifdef HAVE_MF_HC3 
+extern uint32_t 
+lzma_mf_hc3_find(lzma_mf *mf, lzma_match *matches) 
+{ 
+	header_find(false, 3); 
+ 
+	hash_3_calc(); 
+ 
+	const uint32_t delta2 = pos - mf->hash[hash_2_value]; 
+	const uint32_t cur_match = mf->hash[FIX_3_HASH_SIZE + hash_value]; 
+ 
+	mf->hash[hash_2_value] = pos; 
+	mf->hash[FIX_3_HASH_SIZE + hash_value] = pos; 
+ 
+	uint32_t len_best = 2; 
+ 
+	if (delta2 < mf->cyclic_size && *(cur - delta2) == *cur) { 
+		len_best = lzma_memcmplen(cur - delta2, cur, 
+				len_best, len_limit); 
+ 
+		matches[0].len = len_best; 
+		matches[0].dist = delta2 - 1; 
+		matches_count = 1; 
+ 
+		if (len_best == len_limit) { 
+			hc_skip(); 
+			return 1; // matches_count 
+		} 
+	} 
+ 
+	hc_find(len_best); 
+} 
+ 
+ 
+extern void 
+lzma_mf_hc3_skip(lzma_mf *mf, uint32_t amount) 
+{ 
+	do { 
+		if (mf_avail(mf) < 3) { 
+			move_pending(mf); 
+			continue; 
+		} 
+ 
+		const uint8_t *cur = mf_ptr(mf); 
+		const uint32_t pos = mf->read_pos + mf->offset; 
+ 
+		hash_3_calc(); 
+ 
+		const uint32_t cur_match 
+				= mf->hash[FIX_3_HASH_SIZE + hash_value]; 
+ 
+		mf->hash[hash_2_value] = pos; 
+		mf->hash[FIX_3_HASH_SIZE + hash_value] = pos; 
+ 
+		hc_skip(); 
+ 
+	} while (--amount != 0); 
+} 
+#endif 
+ 
+ 
+#ifdef HAVE_MF_HC4 
+extern uint32_t 
+lzma_mf_hc4_find(lzma_mf *mf, lzma_match *matches) 
+{ 
+	header_find(false, 4); 
+ 
+	hash_4_calc(); 
+ 
+	uint32_t delta2 = pos - mf->hash[hash_2_value]; 
+	const uint32_t delta3 
+			= pos - mf->hash[FIX_3_HASH_SIZE + hash_3_value]; 
+	const uint32_t cur_match = mf->hash[FIX_4_HASH_SIZE + hash_value]; 
+ 
+	mf->hash[hash_2_value ] = pos; 
+	mf->hash[FIX_3_HASH_SIZE + hash_3_value] = pos; 
+	mf->hash[FIX_4_HASH_SIZE + hash_value] = pos; 
+ 
+	uint32_t len_best = 1; 
+ 
+	if (delta2 < mf->cyclic_size && *(cur - delta2) == *cur) { 
+		len_best = 2; 
+		matches[0].len = 2; 
+		matches[0].dist = delta2 - 1; 
+		matches_count = 1; 
+	} 
+ 
+	if (delta2 != delta3 && delta3 < mf->cyclic_size 
+			&& *(cur - delta3) == *cur) { 
+		len_best = 3; 
+		matches[matches_count++].dist = delta3 - 1; 
+		delta2 = delta3; 
+	} 
+ 
+	if (matches_count != 0) { 
+		len_best = lzma_memcmplen(cur - delta2, cur, 
+				len_best, len_limit); 
+ 
+		matches[matches_count - 1].len = len_best; 
+ 
+		if (len_best == len_limit) { 
+			hc_skip(); 
+			return matches_count; 
+		} 
+	} 
+ 
+	if (len_best < 3) 
+		len_best = 3; 
+ 
+	hc_find(len_best); 
+} 
+ 
+ 
+extern void 
+lzma_mf_hc4_skip(lzma_mf *mf, uint32_t amount) 
+{ 
+	do { 
+		if (mf_avail(mf) < 4) { 
+			move_pending(mf); 
+			continue; 
+		} 
+ 
+		const uint8_t *cur = mf_ptr(mf); 
+		const uint32_t pos = mf->read_pos + mf->offset; 
+ 
+		hash_4_calc(); 
+ 
+		const uint32_t cur_match 
+				= mf->hash[FIX_4_HASH_SIZE + hash_value]; 
+ 
+		mf->hash[hash_2_value] = pos; 
+		mf->hash[FIX_3_HASH_SIZE + hash_3_value] = pos; 
+		mf->hash[FIX_4_HASH_SIZE + hash_value] = pos; 
+ 
+		hc_skip(); 
+ 
+	} while (--amount != 0); 
+} 
+#endif 
+ 
+ 
+///////////////// 
+// Binary Tree // 
+///////////////// 
+ 
+#if defined(HAVE_MF_BT2) || defined(HAVE_MF_BT3) || defined(HAVE_MF_BT4) 
+static lzma_match * 
+bt_find_func( 
+		const uint32_t len_limit, 
+		const uint32_t pos, 
+		const uint8_t *const cur, 
+		uint32_t cur_match, 
+		uint32_t depth, 
+		uint32_t *const son, 
+		const uint32_t cyclic_pos, 
+		const uint32_t cyclic_size, 
+		lzma_match *matches, 
+		uint32_t len_best) 
+{ 
+	uint32_t *ptr0 = son + (cyclic_pos << 1) + 1; 
+	uint32_t *ptr1 = son + (cyclic_pos << 1); 
+ 
+	uint32_t len0 = 0; 
+	uint32_t len1 = 0; 
+ 
+	while (true) { 
+		const uint32_t delta = pos - cur_match; 
+		if (depth-- == 0 || delta >= cyclic_size) { 
+			*ptr0 = EMPTY_HASH_VALUE; 
+			*ptr1 = EMPTY_HASH_VALUE; 
+			return matches; 
+		} 
+ 
+		uint32_t *const pair = son + ((cyclic_pos - delta 
+				+ (delta > cyclic_pos ? cyclic_size : 0)) 
+				<< 1); 
+ 
+		const uint8_t *const pb = cur - delta; 
+		uint32_t len = my_min(len0, len1); 
+ 
+		if (pb[len] == cur[len]) { 
+			len = lzma_memcmplen(pb, cur, len + 1, len_limit); 
+ 
+			if (len_best < len) { 
+				len_best = len; 
+				matches->len = len; 
+				matches->dist = delta - 1; 
+				++matches; 
+ 
+				if (len == len_limit) { 
+					*ptr1 = pair[0]; 
+					*ptr0 = pair[1]; 
+					return matches; 
+				} 
+			} 
+		} 
+ 
+		if (pb[len] < cur[len]) { 
+			*ptr1 = cur_match; 
+			ptr1 = pair + 1; 
+			cur_match = *ptr1; 
+			len1 = len; 
+		} else { 
+			*ptr0 = cur_match; 
+			ptr0 = pair; 
+			cur_match = *ptr0; 
+			len0 = len; 
+		} 
+	} 
+} 
+ 
+ 
+static void 
+bt_skip_func( 
+		const uint32_t len_limit, 
+		const uint32_t pos, 
+		const uint8_t *const cur, 
+		uint32_t cur_match, 
+		uint32_t depth, 
+		uint32_t *const son, 
+		const uint32_t cyclic_pos, 
+		const uint32_t cyclic_size) 
+{ 
+	uint32_t *ptr0 = son + (cyclic_pos << 1) + 1; 
+	uint32_t *ptr1 = son + (cyclic_pos << 1); 
+ 
+	uint32_t len0 = 0; 
+	uint32_t len1 = 0; 
+ 
+	while (true) { 
+		const uint32_t delta = pos - cur_match; 
+		if (depth-- == 0 || delta >= cyclic_size) { 
+			*ptr0 = EMPTY_HASH_VALUE; 
+			*ptr1 = EMPTY_HASH_VALUE; 
+			return; 
+		} 
+ 
+		uint32_t *pair = son + ((cyclic_pos - delta 
+				+ (delta > cyclic_pos ? cyclic_size : 0)) 
+				<< 1); 
+		const uint8_t *pb = cur - delta; 
+		uint32_t len = my_min(len0, len1); 
+ 
+		if (pb[len] == cur[len]) { 
+			len = lzma_memcmplen(pb, cur, len + 1, len_limit); 
+ 
+			if (len == len_limit) { 
+				*ptr1 = pair[0]; 
+				*ptr0 = pair[1]; 
+				return; 
+			} 
+		} 
+ 
+		if (pb[len] < cur[len]) { 
+			*ptr1 = cur_match; 
+			ptr1 = pair + 1; 
+			cur_match = *ptr1; 
+			len1 = len; 
+		} else { 
+			*ptr0 = cur_match; 
+			ptr0 = pair; 
+			cur_match = *ptr0; 
+			len0 = len; 
+		} 
+	} 
+} 
+ 
+ 
+#define bt_find(len_best) \ 
+	call_find(bt_find_func, len_best) 
+ 
+#define bt_skip() \ 
+do { \ 
+	bt_skip_func(len_limit, pos, cur, cur_match, mf->depth, \ 
+			mf->son, mf->cyclic_pos, \ 
+			mf->cyclic_size); \ 
+	move_pos(mf); \ 
+} while (0) 
+ 
+#endif 
+ 
+ 
+#ifdef HAVE_MF_BT2 
+extern uint32_t 
+lzma_mf_bt2_find(lzma_mf *mf, lzma_match *matches) 
+{ 
+	header_find(true, 2); 
+ 
+	hash_2_calc(); 
+ 
+	const uint32_t cur_match = mf->hash[hash_value]; 
+	mf->hash[hash_value] = pos; 
+ 
+	bt_find(1); 
+} 
+ 
+ 
+extern void 
+lzma_mf_bt2_skip(lzma_mf *mf, uint32_t amount) 
+{ 
+	do { 
+		header_skip(true, 2); 
+ 
+		hash_2_calc(); 
+ 
+		const uint32_t cur_match = mf->hash[hash_value]; 
+		mf->hash[hash_value] = pos; 
+ 
+		bt_skip(); 
+ 
+	} while (--amount != 0); 
+} 
+#endif 
+ 
+ 
+#ifdef HAVE_MF_BT3 
+extern uint32_t 
+lzma_mf_bt3_find(lzma_mf *mf, lzma_match *matches) 
+{ 
+	header_find(true, 3); 
+ 
+	hash_3_calc(); 
+ 
+	const uint32_t delta2 = pos - mf->hash[hash_2_value]; 
+	const uint32_t cur_match = mf->hash[FIX_3_HASH_SIZE + hash_value]; 
+ 
+	mf->hash[hash_2_value] = pos; 
+	mf->hash[FIX_3_HASH_SIZE + hash_value] = pos; 
+ 
+	uint32_t len_best = 2; 
+ 
+	if (delta2 < mf->cyclic_size && *(cur - delta2) == *cur) { 
+		len_best = lzma_memcmplen( 
+				cur, cur - delta2, len_best, len_limit); 
+ 
+		matches[0].len = len_best; 
+		matches[0].dist = delta2 - 1; 
+		matches_count = 1; 
+ 
+		if (len_best == len_limit) { 
+			bt_skip(); 
+			return 1; // matches_count 
+		} 
+	} 
+ 
+	bt_find(len_best); 
+} 
+ 
+ 
+extern void 
+lzma_mf_bt3_skip(lzma_mf *mf, uint32_t amount) 
+{ 
+	do { 
+		header_skip(true, 3); 
+ 
+		hash_3_calc(); 
+ 
+		const uint32_t cur_match 
+				= mf->hash[FIX_3_HASH_SIZE + hash_value]; 
+ 
+		mf->hash[hash_2_value] = pos; 
+		mf->hash[FIX_3_HASH_SIZE + hash_value] = pos; 
+ 
+		bt_skip(); 
+ 
+	} while (--amount != 0); 
+} 
+#endif 
+ 
+ 
+#ifdef HAVE_MF_BT4 
+extern uint32_t 
+lzma_mf_bt4_find(lzma_mf *mf, lzma_match *matches) 
+{ 
+	header_find(true, 4); 
+ 
+	hash_4_calc(); 
+ 
+	uint32_t delta2 = pos - mf->hash[hash_2_value]; 
+	const uint32_t delta3 
+			= pos - mf->hash[FIX_3_HASH_SIZE + hash_3_value]; 
+	const uint32_t cur_match = mf->hash[FIX_4_HASH_SIZE + hash_value]; 
+ 
+	mf->hash[hash_2_value] = pos; 
+	mf->hash[FIX_3_HASH_SIZE + hash_3_value] = pos; 
+	mf->hash[FIX_4_HASH_SIZE + hash_value] = pos; 
+ 
+	uint32_t len_best = 1; 
+ 
+	if (delta2 < mf->cyclic_size && *(cur - delta2) == *cur) { 
+		len_best = 2; 
+		matches[0].len = 2; 
+		matches[0].dist = delta2 - 1; 
+		matches_count = 1; 
+	} 
+ 
+	if (delta2 != delta3 && delta3 < mf->cyclic_size 
+			&& *(cur - delta3) == *cur) { 
+		len_best = 3; 
+		matches[matches_count++].dist = delta3 - 1; 
+		delta2 = delta3; 
+	} 
+ 
+	if (matches_count != 0) { 
+		len_best = lzma_memcmplen( 
+				cur, cur - delta2, len_best, len_limit); 
+ 
+		matches[matches_count - 1].len = len_best; 
+ 
+		if (len_best == len_limit) { 
+			bt_skip(); 
+			return matches_count; 
+		} 
+	} 
+ 
+	if (len_best < 3) 
+		len_best = 3; 
+ 
+	bt_find(len_best); 
+} 
+ 
+ 
+extern void 
+lzma_mf_bt4_skip(lzma_mf *mf, uint32_t amount) 
+{ 
+	do { 
+		header_skip(true, 4); 
+ 
+		hash_4_calc(); 
+ 
+		const uint32_t cur_match 
+				= mf->hash[FIX_4_HASH_SIZE + hash_value]; 
+ 
+		mf->hash[hash_2_value] = pos; 
+		mf->hash[FIX_3_HASH_SIZE + hash_3_value] = pos; 
+		mf->hash[FIX_4_HASH_SIZE + hash_value] = pos; 
+ 
+		bt_skip(); 
+ 
+	} while (--amount != 0); 
+} 
+#endif