Adding upstream version 3.3.0+dfsg1.upstream/3.3.0+dfsg1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 1175 insertions, 0 deletions

diff --git a/libfreerdp/codec/xcrush.c b/libfreerdp/codec/xcrush.c
new file mode 100644
index 0000000..eed2a86
--- /dev/null
+++ b/libfreerdp/codec/xcrush.c
@@ -0,0 +1,1175 @@
+/**
+ * FreeRDP: A Remote Desktop Protocol Implementation
+ * XCrush (RDP6.1) Bulk Data Compression
+ *
+ * Copyright 2014 Marc-Andre Moreau <marcandre.moreau@gmail.com>
+ * Copyright 2017 Armin Novak <armin.novak@thincast.com>
+ * Copyright 2017 Thincast Technologies GmbH
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <winpr/assert.h>
+#include <freerdp/config.h>
+
+#include <winpr/crt.h>
+#include <winpr/print.h>
+#include <winpr/bitstream.h>
+
+#include <freerdp/log.h>
+#include "xcrush.h"
+
+#define TAG FREERDP_TAG("codec")
+
+#pragma pack(push, 1)
+
+typedef struct
+{
+	UINT32 MatchOffset;
+	UINT32 ChunkOffset;
+	UINT32 MatchLength;
+} XCRUSH_MATCH_INFO;
+
+typedef struct
+{
+	UINT32 offset;
+	UINT32 next;
+} XCRUSH_CHUNK;
+
+typedef struct
+{
+	UINT16 seed;
+	UINT16 size;
+} XCRUSH_SIGNATURE;
+
+typedef struct
+{
+	UINT16 MatchLength;
+	UINT16 MatchOutputOffset;
+	UINT32 MatchHistoryOffset;
+} RDP61_MATCH_DETAILS;
+
+typedef struct
+{
+	BYTE Level1ComprFlags;
+	BYTE Level2ComprFlags;
+	UINT16 MatchCount;
+	RDP61_MATCH_DETAILS* MatchDetails;
+	BYTE* Literals;
+} RDP61_COMPRESSED_DATA;
+
+#pragma pack(pop)
+
+struct s_XCRUSH_CONTEXT
+{
+	ALIGN64 BOOL Compressor;
+	ALIGN64 MPPC_CONTEXT* mppc;
+	ALIGN64 BYTE* HistoryPtr;
+	ALIGN64 UINT32 HistoryOffset;
+	ALIGN64 UINT32 HistoryBufferSize;
+	ALIGN64 BYTE HistoryBuffer[2000000];
+	ALIGN64 BYTE BlockBuffer[16384];
+	ALIGN64 UINT32 CompressionFlags;
+	ALIGN64 UINT32 SignatureIndex;
+	ALIGN64 UINT32 SignatureCount;
+	ALIGN64 XCRUSH_SIGNATURE Signatures[1000];
+	ALIGN64 UINT32 ChunkHead;
+	ALIGN64 UINT32 ChunkTail;
+	ALIGN64 XCRUSH_CHUNK Chunks[65534];
+	ALIGN64 UINT16 NextChunks[65536];
+	ALIGN64 UINT32 OriginalMatchCount;
+	ALIGN64 UINT32 OptimizedMatchCount;
+	ALIGN64 XCRUSH_MATCH_INFO OriginalMatches[1000];
+	ALIGN64 XCRUSH_MATCH_INFO OptimizedMatches[1000];
+};
+
+//#define DEBUG_XCRUSH 1
+#if defined(DEBUG_XCRUSH)
+static const char* xcrush_get_level_2_compression_flags_string(UINT32 flags)
+{
+	flags &= 0xE0;
+
+	if (flags == 0)
+		return "PACKET_UNCOMPRESSED";
+	else if (flags == PACKET_COMPRESSED)
+		return "PACKET_COMPRESSED";
+	else if (flags == PACKET_AT_FRONT)
+		return "PACKET_AT_FRONT";
+	else if (flags == PACKET_FLUSHED)
+		return "PACKET_FLUSHED";
+	else if (flags == (PACKET_COMPRESSED | PACKET_AT_FRONT))
+		return "PACKET_COMPRESSED | PACKET_AT_FRONT";
+	else if (flags == (PACKET_COMPRESSED | PACKET_FLUSHED))
+		return "PACKET_COMPRESSED | PACKET_FLUSHED";
+	else if (flags == (PACKET_AT_FRONT | PACKET_FLUSHED))
+		return "PACKET_AT_FRONT | PACKET_FLUSHED";
+	else if (flags == (PACKET_COMPRESSED | PACKET_AT_FRONT | PACKET_FLUSHED))
+		return "PACKET_COMPRESSED | PACKET_AT_FRONT | PACKET_FLUSHED";
+
+	return "PACKET_UNKNOWN";
+}
+
+static const char* xcrush_get_level_1_compression_flags_string(UINT32 flags)
+{
+	flags &= 0x17;
+
+	if (flags == 0)
+		return "L1_UNKNOWN";
+	else if (flags == L1_PACKET_AT_FRONT)
+		return "L1_PACKET_AT_FRONT";
+	else if (flags == L1_NO_COMPRESSION)
+		return "L1_NO_COMPRESSION";
+	else if (flags == L1_COMPRESSED)
+		return "L1_COMPRESSED";
+	else if (flags == L1_INNER_COMPRESSION)
+		return "L1_INNER_COMPRESSION";
+	else if (flags == (L1_PACKET_AT_FRONT | L1_NO_COMPRESSION))
+		return "L1_PACKET_AT_FRONT | L1_NO_COMPRESSION";
+	else if (flags == (L1_PACKET_AT_FRONT | L1_COMPRESSED))
+		return "L1_PACKET_AT_FRONT | L1_COMPRESSED";
+	else if (flags == (L1_PACKET_AT_FRONT | L1_INNER_COMPRESSION))
+		return "L1_PACKET_AT_FRONT | L1_INNER_COMPRESSION";
+	else if (flags == (L1_NO_COMPRESSION | L1_COMPRESSED))
+		return "L1_NO_COMPRESSION | L1_COMPRESSED";
+	else if (flags == (L1_NO_COMPRESSION | L1_INNER_COMPRESSION))
+		return "L1_NO_COMPRESSION | L1_INNER_COMPRESSION";
+	else if (flags == (L1_COMPRESSED | L1_INNER_COMPRESSION))
+		return "L1_COMPRESSED | L1_INNER_COMPRESSION";
+	else if (flags == (L1_NO_COMPRESSION | L1_COMPRESSED | L1_INNER_COMPRESSION))
+		return "L1_NO_COMPRESSION | L1_COMPRESSED | L1_INNER_COMPRESSION";
+	else if (flags == (L1_PACKET_AT_FRONT | L1_COMPRESSED | L1_INNER_COMPRESSION))
+		return "L1_PACKET_AT_FRONT | L1_COMPRESSED | L1_INNER_COMPRESSION";
+	else if (flags == (L1_PACKET_AT_FRONT | L1_NO_COMPRESSION | L1_INNER_COMPRESSION))
+		return "L1_PACKET_AT_FRONT | L1_NO_COMPRESSION | L1_INNER_COMPRESSION";
+	else if (flags == (L1_PACKET_AT_FRONT | L1_NO_COMPRESSION | L1_COMPRESSED))
+		return "L1_PACKET_AT_FRONT | L1_NO_COMPRESSION | L1_COMPRESSED";
+	else if (flags ==
+	         (L1_PACKET_AT_FRONT | L1_NO_COMPRESSION | L1_COMPRESSED | L1_INNER_COMPRESSION))
+		return "L1_PACKET_AT_FRONT | L1_NO_COMPRESSION | L1_COMPRESSED | L1_INNER_COMPRESSION";
+
+	return "L1_UNKNOWN";
+}
+#endif
+
+static UINT32 xcrush_update_hash(const BYTE* data, UINT32 size)
+{
+	const BYTE* end = NULL;
+	UINT32 seed = 5381; /* same value as in djb2 */
+
+	WINPR_ASSERT(data);
+	WINPR_ASSERT(size >= 4);
+
+	if (size > 32)
+	{
+		size = 32;
+		seed = 5413;
+	}
+
+	end = &data[size - 4];
+
+	while (data < end)
+	{
+		seed += (data[3] ^ data[0]) + (data[1] << 8);
+		data += 4;
+	}
+
+	return (UINT16)seed;
+}
+
+static int xcrush_append_chunk(XCRUSH_CONTEXT* xcrush, const BYTE* data, UINT32* beg, UINT32 end)
+{
+	UINT32 size = 0;
+
+	WINPR_ASSERT(xcrush);
+	WINPR_ASSERT(data);
+	WINPR_ASSERT(beg);
+
+	if (xcrush->SignatureIndex >= xcrush->SignatureCount)
+		return 0;
+
+	size = end - *beg;
+
+	if (size > 65535)
+		return 0;
+
+	if (size >= 15)
+	{
+		UINT32 seed = xcrush_update_hash(&data[*beg], (UINT16)size);
+		xcrush->Signatures[xcrush->SignatureIndex].size = size;
+		xcrush->Signatures[xcrush->SignatureIndex].seed = seed;
+		xcrush->SignatureIndex++;
+		*beg = end;
+	}
+
+	return 1;
+}
+
+static int xcrush_compute_chunks(XCRUSH_CONTEXT* xcrush, const BYTE* data, UINT32 size,
+                                 UINT32* pIndex)
+{
+	UINT32 offset = 0;
+	UINT32 rotation = 0;
+	UINT32 accumulator = 0;
+
+	WINPR_ASSERT(xcrush);
+	WINPR_ASSERT(data);
+	WINPR_ASSERT(pIndex);
+
+	*pIndex = 0;
+	xcrush->SignatureIndex = 0;
+
+	if (size < 128)
+		return 0;
+
+	for (UINT32 i = 0; i < 32; i++)
+	{
+		rotation = _rotl(accumulator, 1);
+		accumulator = data[i] ^ rotation;
+	}
+
+	for (UINT32 i = 0; i < size - 64; i++)
+	{
+		rotation = _rotl(accumulator, 1);
+		accumulator = data[i + 32] ^ data[i] ^ rotation;
+
+		if (!(accumulator & 0x7F))
+		{
+			if (!xcrush_append_chunk(xcrush, data, &offset, i + 32))
+				return 0;
+		}
+
+		i++;
+		rotation = _rotl(accumulator, 1);
+		accumulator = data[i + 32] ^ data[i] ^ rotation;
+
+		if (!(accumulator & 0x7F))
+		{
+			if (!xcrush_append_chunk(xcrush, data, &offset, i + 32))
+				return 0;
+		}
+
+		i++;
+		rotation = _rotl(accumulator, 1);
+		accumulator = data[i + 32] ^ data[i] ^ rotation;
+
+		if (!(accumulator & 0x7F))
+		{
+			if (!xcrush_append_chunk(xcrush, data, &offset, i + 32))
+				return 0;
+		}
+
+		i++;
+		rotation = _rotl(accumulator, 1);
+		accumulator = data[i + 32] ^ data[i] ^ rotation;
+
+		if (!(accumulator & 0x7F))
+		{
+			if (!xcrush_append_chunk(xcrush, data, &offset, i + 32))
+				return 0;
+		}
+	}
+
+	if ((size == offset) || xcrush_append_chunk(xcrush, data, &offset, size))
+	{
+		*pIndex = xcrush->SignatureIndex;
+		return 1;
+	}
+
+	return 0;
+}
+
+static UINT32 xcrush_compute_signatures(XCRUSH_CONTEXT* xcrush, const BYTE* data, UINT32 size)
+{
+	UINT32 index = 0;
+
+	if (xcrush_compute_chunks(xcrush, data, size, &index))
+		return index;
+
+	return 0;
+}
+
+static void xcrush_clear_hash_table_range(XCRUSH_CONTEXT* xcrush, UINT32 beg, UINT32 end)
+{
+	WINPR_ASSERT(xcrush);
+
+	for (UINT32 index = 0; index < 65536; index++)
+	{
+		if (xcrush->NextChunks[index] >= beg)
+		{
+			if (xcrush->NextChunks[index] <= end)
+			{
+				xcrush->NextChunks[index] = 0;
+			}
+		}
+	}
+
+	for (UINT32 index = 0; index < 65534; index++)
+	{
+		if (xcrush->Chunks[index].next >= beg)
+		{
+			if (xcrush->Chunks[index].next <= end)
+			{
+				xcrush->Chunks[index].next = 0;
+			}
+		}
+	}
+}
+
+static int xcrush_find_next_matching_chunk(XCRUSH_CONTEXT* xcrush, XCRUSH_CHUNK* chunk,
+                                           XCRUSH_CHUNK** pNextChunk)
+{
+	UINT32 index = 0;
+	XCRUSH_CHUNK* next = NULL;
+
+	WINPR_ASSERT(xcrush);
+
+	if (!chunk)
+		return -4001; /* error */
+
+	if (chunk->next)
+	{
+		index = (chunk - xcrush->Chunks) / sizeof(XCRUSH_CHUNK);
+
+		if (index >= 65534)
+			return -4002; /* error */
+
+		if ((index < xcrush->ChunkHead) || (chunk->next >= xcrush->ChunkHead))
+		{
+			if (chunk->next >= 65534)
+				return -4003; /* error */
+
+			next = &xcrush->Chunks[chunk->next];
+		}
+	}
+
+	WINPR_ASSERT(pNextChunk);
+	*pNextChunk = next;
+	return 1;
+}
+
+static int xcrush_insert_chunk(XCRUSH_CONTEXT* xcrush, XCRUSH_SIGNATURE* signature, UINT32 offset,
+                               XCRUSH_CHUNK** pPrevChunk)
+{
+	UINT32 seed = 0;
+	UINT32 index = 0;
+
+	WINPR_ASSERT(xcrush);
+
+	if (xcrush->ChunkHead >= 65530)
+	{
+		xcrush->ChunkHead = 1;
+		xcrush->ChunkTail = 1;
+	}
+
+	if (xcrush->ChunkHead >= xcrush->ChunkTail)
+	{
+		xcrush_clear_hash_table_range(xcrush, xcrush->ChunkTail, xcrush->ChunkTail + 10000);
+		xcrush->ChunkTail += 10000;
+	}
+
+	index = xcrush->ChunkHead++;
+
+	if (xcrush->ChunkHead >= 65534)
+		return -3001; /* error */
+
+	xcrush->Chunks[index].offset = offset;
+	seed = signature->seed;
+
+	if (seed >= 65536)
+		return -3002; /* error */
+
+	if (xcrush->NextChunks[seed])
+	{
+		if (xcrush->NextChunks[seed] >= 65534)
+			return -3003; /* error */
+
+		WINPR_ASSERT(pPrevChunk);
+		*pPrevChunk = &xcrush->Chunks[xcrush->NextChunks[seed]];
+	}
+
+	xcrush->Chunks[index].next = xcrush->NextChunks[seed] & 0xFFFF;
+	xcrush->NextChunks[seed] = index;
+	return 1;
+}
+
+static int xcrush_find_match_length(XCRUSH_CONTEXT* xcrush, UINT32 MatchOffset, UINT32 ChunkOffset,
+                                    UINT32 HistoryOffset, UINT32 SrcSize, UINT32 MaxMatchLength,
+                                    XCRUSH_MATCH_INFO* MatchInfo)
+{
+	UINT32 MatchSymbol = 0;
+	UINT32 ChunkSymbol = 0;
+	BYTE* ChunkBuffer = NULL;
+	BYTE* MatchBuffer = NULL;
+	BYTE* MatchStartPtr = NULL;
+	BYTE* ForwardChunkPtr = NULL;
+	BYTE* ReverseChunkPtr = NULL;
+	BYTE* ForwardMatchPtr = NULL;
+	BYTE* ReverseMatchPtr = NULL;
+	BYTE* HistoryBufferEnd = NULL;
+	UINT32 ReverseMatchLength = 0;
+	UINT32 ForwardMatchLength = 0;
+	UINT32 TotalMatchLength = 0;
+	BYTE* HistoryBuffer = NULL;
+	UINT32 HistoryBufferSize = 0;
+
+	WINPR_ASSERT(xcrush);
+	WINPR_ASSERT(MatchInfo);
+
+	HistoryBuffer = xcrush->HistoryBuffer;
+	HistoryBufferSize = xcrush->HistoryBufferSize;
+	HistoryBufferEnd = &HistoryBuffer[HistoryOffset + SrcSize];
+
+	if (MatchOffset > HistoryBufferSize)
+		return -2001; /* error */
+
+	MatchBuffer = &HistoryBuffer[MatchOffset];
+
+	if (ChunkOffset > HistoryBufferSize)
+		return -2002; /* error */
+
+	ChunkBuffer = &HistoryBuffer[ChunkOffset];
+
+	if (MatchOffset == ChunkOffset)
+		return -2003; /* error */
+
+	if (MatchBuffer < HistoryBuffer)
+		return -2004; /* error */
+
+	if (ChunkBuffer < HistoryBuffer)
+		return -2005; /* error */
+
+	ForwardMatchPtr = &HistoryBuffer[MatchOffset];
+	ForwardChunkPtr = &HistoryBuffer[ChunkOffset];
+
+	if ((&MatchBuffer[MaxMatchLength + 1] < HistoryBufferEnd) &&
+	    (MatchBuffer[MaxMatchLength + 1] != ChunkBuffer[MaxMatchLength + 1]))
+	{
+		return 0;
+	}
+
+	while (1)
+	{
+		MatchSymbol = *ForwardMatchPtr++;
+		ChunkSymbol = *ForwardChunkPtr++;
+
+		if (MatchSymbol != ChunkSymbol)
+			break;
+
+		if (ForwardMatchPtr > HistoryBufferEnd)
+			break;
+
+		ForwardMatchLength++;
+	}
+
+	ReverseMatchPtr = MatchBuffer - 1;
+	ReverseChunkPtr = ChunkBuffer - 1;
+
+	while ((ReverseMatchPtr > &HistoryBuffer[HistoryOffset]) && (ReverseChunkPtr > HistoryBuffer) &&
+	       (*ReverseMatchPtr == *ReverseChunkPtr))
+	{
+		ReverseMatchLength++;
+		ReverseMatchPtr--;
+		ReverseChunkPtr--;
+	}
+
+	MatchStartPtr = MatchBuffer - ReverseMatchLength;
+	TotalMatchLength = ReverseMatchLength + ForwardMatchLength;
+
+	if (TotalMatchLength < 11)
+		return 0;
+
+	if (MatchStartPtr < HistoryBuffer)
+		return -2006; /* error */
+
+	MatchInfo->MatchOffset = MatchStartPtr - HistoryBuffer;
+	MatchInfo->ChunkOffset = ChunkBuffer - ReverseMatchLength - HistoryBuffer;
+	MatchInfo->MatchLength = TotalMatchLength;
+	return (int)TotalMatchLength;
+}
+
+static int xcrush_find_all_matches(XCRUSH_CONTEXT* xcrush, UINT32 SignatureIndex,
+                                   UINT32 HistoryOffset, UINT32 SrcOffset, UINT32 SrcSize)
+{
+	UINT32 j = 0;
+	int status = 0;
+	UINT32 ChunkIndex = 0;
+	UINT32 ChunkCount = 0;
+	XCRUSH_CHUNK* chunk = NULL;
+	UINT32 MatchLength = 0;
+	UINT32 MaxMatchLength = 0;
+	UINT32 PrevMatchEnd = 0;
+	XCRUSH_SIGNATURE* Signatures = NULL;
+	XCRUSH_MATCH_INFO MaxMatchInfo = { 0 };
+
+	WINPR_ASSERT(xcrush);
+
+	Signatures = xcrush->Signatures;
+
+	for (UINT32 i = 0; i < SignatureIndex; i++)
+	{
+		XCRUSH_MATCH_INFO MatchInfo = { 0 };
+		UINT32 offset = SrcOffset + HistoryOffset;
+
+		if (!Signatures[i].size)
+			return -1001; /* error */
+
+		status = xcrush_insert_chunk(xcrush, &Signatures[i], offset, &chunk);
+
+		if (status < 0)
+			return status;
+
+		if (chunk && (SrcOffset + HistoryOffset + Signatures[i].size >= PrevMatchEnd))
+		{
+			ChunkCount = 0;
+			MaxMatchLength = 0;
+
+			while (chunk)
+			{
+				if ((chunk->offset < HistoryOffset) || (chunk->offset < offset) ||
+				    (chunk->offset > SrcSize + HistoryOffset))
+				{
+					status = xcrush_find_match_length(xcrush, offset, chunk->offset, HistoryOffset,
+					                                  SrcSize, MaxMatchLength, &MatchInfo);
+
+					if (status < 0)
+						return status; /* error */
+
+					MatchLength = (UINT32)status;
+
+					if (MatchLength > MaxMatchLength)
+					{
+						MaxMatchLength = MatchLength;
+						MaxMatchInfo.MatchOffset = MatchInfo.MatchOffset;
+						MaxMatchInfo.ChunkOffset = MatchInfo.ChunkOffset;
+						MaxMatchInfo.MatchLength = MatchInfo.MatchLength;
+
+						if (MatchLength > 256)
+							break;
+					}
+				}
+
+				ChunkIndex = ChunkCount++;
+
+				if (ChunkIndex > 4)
+					break;
+
+				status = xcrush_find_next_matching_chunk(xcrush, chunk, &chunk);
+
+				if (status < 0)
+					return status; /* error */
+			}
+
+			if (MaxMatchLength)
+			{
+				xcrush->OriginalMatches[j].MatchOffset = MaxMatchInfo.MatchOffset;
+				xcrush->OriginalMatches[j].ChunkOffset = MaxMatchInfo.ChunkOffset;
+				xcrush->OriginalMatches[j].MatchLength = MaxMatchInfo.MatchLength;
+
+				if (xcrush->OriginalMatches[j].MatchOffset < HistoryOffset)
+					return -1002; /* error */
+
+				PrevMatchEnd =
+				    xcrush->OriginalMatches[j].MatchLength + xcrush->OriginalMatches[j].MatchOffset;
+				j++;
+
+				if (j >= 1000)
+					return -1003; /* error */
+			}
+		}
+
+		SrcOffset += Signatures[i].size;
+
+		if (SrcOffset > SrcSize)
+			return -1004; /* error */
+	}
+
+	if (SrcOffset > SrcSize)
+		return -1005; /* error */
+
+	return (int)j;
+}
+
+static int xcrush_optimize_matches(XCRUSH_CONTEXT* xcrush)
+{
+	UINT32 j = 0;
+	UINT32 MatchDiff = 0;
+	UINT32 PrevMatchEnd = 0;
+	UINT32 TotalMatchLength = 0;
+	UINT32 OriginalMatchCount = 0;
+	UINT32 OptimizedMatchCount = 0;
+	XCRUSH_MATCH_INFO* OriginalMatch = NULL;
+	XCRUSH_MATCH_INFO* OptimizedMatch = NULL;
+	XCRUSH_MATCH_INFO* OriginalMatches = NULL;
+	XCRUSH_MATCH_INFO* OptimizedMatches = NULL;
+
+	WINPR_ASSERT(xcrush);
+
+	OriginalMatches = xcrush->OriginalMatches;
+	OriginalMatchCount = xcrush->OriginalMatchCount;
+	OptimizedMatches = xcrush->OptimizedMatches;
+
+	for (UINT32 i = 0; i < OriginalMatchCount; i++)
+	{
+		if (OriginalMatches[i].MatchOffset <= PrevMatchEnd)
+		{
+			if ((OriginalMatches[i].MatchOffset < PrevMatchEnd) &&
+			    (OriginalMatches[i].MatchLength + OriginalMatches[i].MatchOffset >
+			     PrevMatchEnd + 6))
+			{
+				MatchDiff = PrevMatchEnd - OriginalMatches[i].MatchOffset;
+				OriginalMatch = &OriginalMatches[i];
+				OptimizedMatch = &OptimizedMatches[j];
+				OptimizedMatch->MatchOffset = OriginalMatch->MatchOffset;
+				OptimizedMatch->ChunkOffset = OriginalMatch->ChunkOffset;
+				OptimizedMatch->MatchLength = OriginalMatch->MatchLength;
+
+				if (OptimizedMatches[j].MatchLength <= MatchDiff)
+					return -5001; /* error */
+
+				if (MatchDiff >= 20000)
+					return -5002; /* error */
+
+				OptimizedMatches[j].MatchLength -= MatchDiff;
+				OptimizedMatches[j].MatchOffset += MatchDiff;
+				OptimizedMatches[j].ChunkOffset += MatchDiff;
+				PrevMatchEnd = OptimizedMatches[j].MatchLength + OptimizedMatches[j].MatchOffset;
+				TotalMatchLength += OptimizedMatches[j].MatchLength;
+				j++;
+			}
+		}
+		else
+		{
+			OriginalMatch = &OriginalMatches[i];
+			OptimizedMatch = &OptimizedMatches[j];
+			OptimizedMatch->MatchOffset = OriginalMatch->MatchOffset;
+			OptimizedMatch->ChunkOffset = OriginalMatch->ChunkOffset;
+			OptimizedMatch->MatchLength = OriginalMatch->MatchLength;
+			PrevMatchEnd = OptimizedMatches[j].MatchLength + OptimizedMatches[j].MatchOffset;
+			TotalMatchLength += OptimizedMatches[j].MatchLength;
+			j++;
+		}
+	}
+
+	OptimizedMatchCount = j;
+	xcrush->OptimizedMatchCount = OptimizedMatchCount;
+	return (int)TotalMatchLength;
+}
+
+static int xcrush_generate_output(XCRUSH_CONTEXT* xcrush, BYTE* OutputBuffer, UINT32 OutputSize,
+                                  UINT32 HistoryOffset, UINT32* pDstSize)
+{
+	BYTE* Literals = NULL;
+	BYTE* OutputEnd = NULL;
+	UINT32 MatchIndex = 0;
+	UINT32 MatchOffset = 0;
+	UINT16 MatchLength = 0;
+	UINT32 MatchCount = 0;
+	UINT32 CurrentOffset = 0;
+	UINT32 MatchOffsetDiff = 0;
+	UINT32 HistoryOffsetDiff = 0;
+	RDP61_MATCH_DETAILS* MatchDetails = NULL;
+
+	WINPR_ASSERT(xcrush);
+	WINPR_ASSERT(OutputBuffer);
+	WINPR_ASSERT(OutputSize >= 2);
+	WINPR_ASSERT(pDstSize);
+
+	MatchCount = xcrush->OptimizedMatchCount;
+	OutputEnd = &OutputBuffer[OutputSize];
+
+	if (&OutputBuffer[2] >= &OutputBuffer[OutputSize])
+		return -6001; /* error */
+
+	Data_Write_UINT16(OutputBuffer, MatchCount);
+	MatchDetails = (RDP61_MATCH_DETAILS*)&OutputBuffer[2];
+	Literals = (BYTE*)&MatchDetails[MatchCount];
+
+	if (Literals > OutputEnd)
+		return -6002; /* error */
+
+	for (MatchIndex = 0; MatchIndex < MatchCount; MatchIndex++)
+	{
+		Data_Write_UINT16(&MatchDetails[MatchIndex].MatchLength,
+		                  xcrush->OptimizedMatches[MatchIndex].MatchLength);
+		Data_Write_UINT16(&MatchDetails[MatchIndex].MatchOutputOffset,
+		                  xcrush->OptimizedMatches[MatchIndex].MatchOffset - HistoryOffset);
+		Data_Write_UINT32(&MatchDetails[MatchIndex].MatchHistoryOffset,
+		                  xcrush->OptimizedMatches[MatchIndex].ChunkOffset);
+	}
+
+	CurrentOffset = HistoryOffset;
+
+	for (MatchIndex = 0; MatchIndex < MatchCount; MatchIndex++)
+	{
+		MatchLength = (UINT16)(xcrush->OptimizedMatches[MatchIndex].MatchLength);
+		MatchOffset = xcrush->OptimizedMatches[MatchIndex].MatchOffset;
+
+		if (MatchOffset <= CurrentOffset)
+		{
+			if (MatchOffset != CurrentOffset)
+				return -6003; /* error */
+
+			CurrentOffset = MatchOffset + MatchLength;
+		}
+		else
+		{
+			MatchOffsetDiff = MatchOffset - CurrentOffset;
+
+			if (Literals + MatchOffset - CurrentOffset >= OutputEnd)
+				return -6004; /* error */
+
+			CopyMemory(Literals, &xcrush->HistoryBuffer[CurrentOffset], MatchOffsetDiff);
+
+			if (Literals >= OutputEnd)
+				return -6005; /* error */
+
+			Literals += MatchOffsetDiff;
+			CurrentOffset = MatchOffset + MatchLength;
+		}
+	}
+
+	HistoryOffsetDiff = xcrush->HistoryOffset - CurrentOffset;
+
+	if (Literals + HistoryOffsetDiff >= OutputEnd)
+		return -6006; /* error */
+
+	CopyMemory(Literals, &xcrush->HistoryBuffer[CurrentOffset], HistoryOffsetDiff);
+	*pDstSize = Literals + HistoryOffsetDiff - OutputBuffer;
+	return 1;
+}
+
+static INLINE size_t xcrush_copy_bytes(BYTE* dst, const BYTE* src, size_t num)
+{
+	WINPR_ASSERT(dst);
+	WINPR_ASSERT(src);
+
+	if (src + num < dst || src > dst + num)
+		memcpy(dst, src, num);
+	else if (src != dst)
+	{
+		// src and dst overlaps
+		// we should copy the area that doesn't overlap repeatly
+		const size_t diff = (dst > src) ? dst - src : src - dst;
+		const size_t rest = num % diff;
+		const size_t end = num - rest;
+
+		for (size_t a = 0; a < end; a += diff)
+			memcpy(&dst[a], &src[a], diff);
+
+		if (rest != 0)
+			memcpy(&dst[end], &src[end], rest);
+	}
+
+	return num;
+}
+
+static int xcrush_decompress_l1(XCRUSH_CONTEXT* xcrush, const BYTE* pSrcData, UINT32 SrcSize,
+                                const BYTE** ppDstData, UINT32* pDstSize, UINT32 flags)
+{
+	const BYTE* pSrcEnd = NULL;
+	const BYTE* Literals = NULL;
+	UINT16 MatchCount = 0;
+	UINT16 MatchIndex = 0;
+	BYTE* OutputPtr = NULL;
+	size_t OutputLength = 0;
+	UINT32 OutputOffset = 0;
+	BYTE* HistoryPtr = NULL;
+	BYTE* HistoryBuffer = NULL;
+	BYTE* HistoryBufferEnd = NULL;
+	UINT32 HistoryBufferSize = 0;
+	UINT16 MatchLength = 0;
+	UINT16 MatchOutputOffset = 0;
+	UINT32 MatchHistoryOffset = 0;
+	const RDP61_MATCH_DETAILS* MatchDetails = NULL;
+
+	WINPR_ASSERT(xcrush);
+
+	if (SrcSize < 1)
+		return -1001;
+
+	WINPR_ASSERT(pSrcData);
+	WINPR_ASSERT(ppDstData);
+	WINPR_ASSERT(pDstSize);
+
+	if (flags & L1_PACKET_AT_FRONT)
+		xcrush->HistoryOffset = 0;
+
+	pSrcEnd = &pSrcData[SrcSize];
+	HistoryBuffer = xcrush->HistoryBuffer;
+	HistoryBufferSize = xcrush->HistoryBufferSize;
+	HistoryBufferEnd = &(HistoryBuffer[HistoryBufferSize]);
+	xcrush->HistoryPtr = HistoryPtr = &(HistoryBuffer[xcrush->HistoryOffset]);
+
+	if (flags & L1_NO_COMPRESSION)
+	{
+		Literals = pSrcData;
+	}
+	else
+	{
+		if (!(flags & L1_COMPRESSED))
+			return -1002;
+
+		if ((pSrcData + 2) > pSrcEnd)
+			return -1003;
+
+		Data_Read_UINT16(pSrcData, MatchCount);
+		MatchDetails = (const RDP61_MATCH_DETAILS*)&pSrcData[2];
+		Literals = (const BYTE*)&MatchDetails[MatchCount];
+		OutputOffset = 0;
+
+		if (Literals > pSrcEnd)
+			return -1004;
+
+		for (MatchIndex = 0; MatchIndex < MatchCount; MatchIndex++)
+		{
+			Data_Read_UINT16(&MatchDetails[MatchIndex].MatchLength, MatchLength);
+			Data_Read_UINT16(&MatchDetails[MatchIndex].MatchOutputOffset, MatchOutputOffset);
+			Data_Read_UINT32(&MatchDetails[MatchIndex].MatchHistoryOffset, MatchHistoryOffset);
+
+			if (MatchOutputOffset < OutputOffset)
+				return -1005;
+
+			if (MatchLength > HistoryBufferSize)
+				return -1006;
+
+			if (MatchHistoryOffset > HistoryBufferSize)
+				return -1007;
+
+			OutputLength = MatchOutputOffset - OutputOffset;
+
+			if ((MatchOutputOffset - OutputOffset) > HistoryBufferSize)
+				return -1008;
+
+			if (OutputLength > 0)
+			{
+				if ((&HistoryPtr[OutputLength] >= HistoryBufferEnd) || (Literals >= pSrcEnd) ||
+				    (&Literals[OutputLength] > pSrcEnd))
+					return -1009;
+
+				xcrush_copy_bytes(HistoryPtr, Literals, OutputLength);
+				HistoryPtr += OutputLength;
+				Literals += OutputLength;
+				OutputOffset += OutputLength;
+
+				if (Literals > pSrcEnd)
+					return -1010;
+			}
+
+			OutputPtr = &xcrush->HistoryBuffer[MatchHistoryOffset];
+
+			if ((&HistoryPtr[MatchLength] >= HistoryBufferEnd) ||
+			    (&OutputPtr[MatchLength] >= HistoryBufferEnd))
+				return -1011;
+
+			xcrush_copy_bytes(HistoryPtr, OutputPtr, MatchLength);
+			OutputOffset += MatchLength;
+			HistoryPtr += MatchLength;
+		}
+	}
+
+	if (Literals < pSrcEnd)
+	{
+		OutputLength = pSrcEnd - Literals;
+
+		if ((&HistoryPtr[OutputLength] >= HistoryBufferEnd) || (&Literals[OutputLength] > pSrcEnd))
+			return -1012;
+
+		xcrush_copy_bytes(HistoryPtr, Literals, OutputLength);
+		HistoryPtr += OutputLength;
+	}
+
+	xcrush->HistoryOffset = HistoryPtr - HistoryBuffer;
+	*pDstSize = HistoryPtr - xcrush->HistoryPtr;
+	*ppDstData = xcrush->HistoryPtr;
+	return 1;
+}
+
+int xcrush_decompress(XCRUSH_CONTEXT* xcrush, const BYTE* pSrcData, UINT32 SrcSize,
+                      const BYTE** ppDstData, UINT32* pDstSize, UINT32 flags)
+{
+	int status = 0;
+	UINT32 DstSize = 0;
+	const BYTE* pDstData = NULL;
+	BYTE Level1ComprFlags = 0;
+	BYTE Level2ComprFlags = 0;
+
+	WINPR_ASSERT(xcrush);
+
+	if (SrcSize < 2)
+		return -1;
+
+	WINPR_ASSERT(pSrcData);
+	WINPR_ASSERT(ppDstData);
+	WINPR_ASSERT(pDstSize);
+
+	Level1ComprFlags = pSrcData[0];
+	Level2ComprFlags = pSrcData[1];
+	pSrcData += 2;
+	SrcSize -= 2;
+
+	if (flags & PACKET_FLUSHED)
+	{
+		ZeroMemory(xcrush->HistoryBuffer, xcrush->HistoryBufferSize);
+		xcrush->HistoryOffset = 0;
+	}
+
+	if (!(Level2ComprFlags & PACKET_COMPRESSED))
+	{
+		status =
+		    xcrush_decompress_l1(xcrush, pSrcData, SrcSize, ppDstData, pDstSize, Level1ComprFlags);
+		return status;
+	}
+
+	status =
+	    mppc_decompress(xcrush->mppc, pSrcData, SrcSize, &pDstData, &DstSize, Level2ComprFlags);
+
+	if (status < 0)
+		return status;
+
+	status = xcrush_decompress_l1(xcrush, pDstData, DstSize, ppDstData, pDstSize, Level1ComprFlags);
+	return status;
+}
+
+static int xcrush_compress_l1(XCRUSH_CONTEXT* xcrush, const BYTE* pSrcData, UINT32 SrcSize,
+                              BYTE* pDstData, UINT32* pDstSize, UINT32* pFlags)
+{
+	int status = 0;
+	UINT32 Flags = 0;
+	UINT32 HistoryOffset = 0;
+	BYTE* HistoryPtr = NULL;
+	BYTE* HistoryBuffer = NULL;
+	UINT32 SignatureIndex = 0;
+
+	WINPR_ASSERT(xcrush);
+	WINPR_ASSERT(pSrcData);
+	WINPR_ASSERT(SrcSize > 0);
+	WINPR_ASSERT(pDstData);
+	WINPR_ASSERT(pDstSize);
+	WINPR_ASSERT(pFlags);
+
+	if (xcrush->HistoryOffset + SrcSize + 8 > xcrush->HistoryBufferSize)
+	{
+		xcrush->HistoryOffset = 0;
+		Flags |= L1_PACKET_AT_FRONT;
+	}
+
+	HistoryOffset = xcrush->HistoryOffset;
+	HistoryBuffer = xcrush->HistoryBuffer;
+	HistoryPtr = &HistoryBuffer[HistoryOffset];
+	MoveMemory(HistoryPtr, pSrcData, SrcSize);
+	xcrush->HistoryOffset += SrcSize;
+
+	if (SrcSize > 50)
+	{
+		SignatureIndex = xcrush_compute_signatures(xcrush, pSrcData, SrcSize);
+
+		if (SignatureIndex)
+		{
+			status = xcrush_find_all_matches(xcrush, SignatureIndex, HistoryOffset, 0, SrcSize);
+
+			if (status < 0)
+				return status;
+
+			xcrush->OriginalMatchCount = (UINT32)status;
+			xcrush->OptimizedMatchCount = 0;
+
+			if (xcrush->OriginalMatchCount)
+			{
+				status = xcrush_optimize_matches(xcrush);
+
+				if (status < 0)
+					return status;
+			}
+
+			if (xcrush->OptimizedMatchCount)
+			{
+				status = xcrush_generate_output(xcrush, pDstData, SrcSize, HistoryOffset, pDstSize);
+
+				if (status < 0)
+					return status;
+
+				Flags |= L1_COMPRESSED;
+			}
+		}
+	}
+
+	if (!(Flags & L1_COMPRESSED))
+	{
+		Flags |= L1_NO_COMPRESSION;
+		*pDstSize = SrcSize;
+	}
+
+	*pFlags = Flags;
+	return 1;
+}
+
+int xcrush_compress(XCRUSH_CONTEXT* xcrush, const BYTE* pSrcData, UINT32 SrcSize, BYTE* pDstBuffer,
+                    const BYTE** ppDstData, UINT32* pDstSize, UINT32* pFlags)
+{
+	int status = 0;
+	UINT32 DstSize = 0;
+	BYTE* pDstData = NULL;
+	const BYTE* CompressedData = NULL;
+	UINT32 CompressedDataSize = 0;
+	BYTE* OriginalData = NULL;
+	UINT32 OriginalDataSize = 0;
+	UINT32 Level1ComprFlags = 0;
+	UINT32 Level2ComprFlags = 0;
+	UINT32 CompressionLevel = 3;
+
+	WINPR_ASSERT(xcrush);
+	WINPR_ASSERT(pSrcData);
+	WINPR_ASSERT(SrcSize > 0);
+	WINPR_ASSERT(ppDstData);
+	WINPR_ASSERT(pDstSize);
+	WINPR_ASSERT(pFlags);
+
+	if (SrcSize > 16384)
+		return -1001;
+
+	if ((SrcSize + 2) > *pDstSize)
+		return -1002;
+
+	OriginalData = pDstBuffer;
+	*ppDstData = pDstBuffer;
+	OriginalDataSize = SrcSize;
+	pDstData = xcrush->BlockBuffer;
+	CompressedDataSize = SrcSize;
+	status = xcrush_compress_l1(xcrush, pSrcData, SrcSize, pDstData, &CompressedDataSize,
+	                            &Level1ComprFlags);
+
+	if (status < 0)
+		return status;
+
+	if (Level1ComprFlags & L1_COMPRESSED)
+	{
+		CompressedData = pDstData;
+
+		if (CompressedDataSize > SrcSize)
+			return -1003;
+	}
+	else
+	{
+		CompressedData = pSrcData;
+
+		if (CompressedDataSize != SrcSize)
+			return -1004;
+	}
+
+	status = 0;
+	pDstData = &OriginalData[2];
+	DstSize = OriginalDataSize - 2;
+
+	if (CompressedDataSize > 50)
+	{
+		const BYTE* pUnusedDstData = NULL;
+		status = mppc_compress(xcrush->mppc, CompressedData, CompressedDataSize, pDstData,
+		                       &pUnusedDstData, &DstSize, &Level2ComprFlags);
+	}
+
+	if (status < 0)
+		return status;
+
+	if (!status || (Level2ComprFlags & PACKET_FLUSHED))
+	{
+		if (CompressedDataSize > DstSize)
+		{
+			xcrush_context_reset(xcrush, TRUE);
+			*ppDstData = pSrcData;
+			*pDstSize = SrcSize;
+			*pFlags = 0;
+			return 1;
+		}
+
+		DstSize = CompressedDataSize;
+		CopyMemory(&OriginalData[2], CompressedData, CompressedDataSize);
+	}
+
+	if (Level2ComprFlags & PACKET_COMPRESSED)
+	{
+		Level2ComprFlags |= xcrush->CompressionFlags;
+		xcrush->CompressionFlags = 0;
+	}
+	else if (Level2ComprFlags & PACKET_FLUSHED)
+	{
+		xcrush->CompressionFlags = PACKET_FLUSHED;
+	}
+
+	Level1ComprFlags |= L1_INNER_COMPRESSION;
+	OriginalData[0] = (BYTE)Level1ComprFlags;
+	OriginalData[1] = (BYTE)Level2ComprFlags;
+#if defined(DEBUG_XCRUSH)
+	WLog_DBG(TAG, "XCrushCompress: Level1ComprFlags: %s Level2ComprFlags: %s",
+	         xcrush_get_level_1_compression_flags_string(Level1ComprFlags),
+	         xcrush_get_level_2_compression_flags_string(Level2ComprFlags));
+#endif
+
+	if (*pDstSize < (DstSize + 2))
+		return -1006;
+
+	*pDstSize = DstSize + 2;
+	*pFlags = PACKET_COMPRESSED | CompressionLevel;
+	return 1;
+}
+
+void xcrush_context_reset(XCRUSH_CONTEXT* xcrush, BOOL flush)
+{
+	WINPR_ASSERT(xcrush);
+
+	xcrush->SignatureIndex = 0;
+	xcrush->SignatureCount = 1000;
+	ZeroMemory(&(xcrush->Signatures), sizeof(XCRUSH_SIGNATURE) * xcrush->SignatureCount);
+	xcrush->CompressionFlags = 0;
+	xcrush->ChunkHead = xcrush->ChunkTail = 1;
+	ZeroMemory(&(xcrush->Chunks), sizeof(xcrush->Chunks));
+	ZeroMemory(&(xcrush->NextChunks), sizeof(xcrush->NextChunks));
+	ZeroMemory(&(xcrush->OriginalMatches), sizeof(xcrush->OriginalMatches));
+	ZeroMemory(&(xcrush->OptimizedMatches), sizeof(xcrush->OptimizedMatches));
+
+	if (flush)
+		xcrush->HistoryOffset = xcrush->HistoryBufferSize + 1;
+	else
+		xcrush->HistoryOffset = 0;
+
+	mppc_context_reset(xcrush->mppc, flush);
+}
+
+XCRUSH_CONTEXT* xcrush_context_new(BOOL Compressor)
+{
+	XCRUSH_CONTEXT* xcrush = (XCRUSH_CONTEXT*)calloc(1, sizeof(XCRUSH_CONTEXT));
+
+	if (!xcrush)
+		goto fail;
+
+	xcrush->Compressor = Compressor;
+	xcrush->mppc = mppc_context_new(1, Compressor);
+	if (!xcrush->mppc)
+		goto fail;
+	xcrush->HistoryBufferSize = 2000000;
+	xcrush_context_reset(xcrush, FALSE);
+
+	return xcrush;
+fail:
+	xcrush_context_free(xcrush);
+
+	return NULL;
+}
+
+void xcrush_context_free(XCRUSH_CONTEXT* xcrush)
+{
+	if (xcrush)
+	{
+		mppc_context_free(xcrush->mppc);
+		free(xcrush);
+	}
+}