/src/FreeRDP/libfreerdp/codec/xcrush.c

Source (jump to first uncovered line)
/**
 * 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);
  }
}

Coverage Report

Created: 2024-05-20 06:11