FreeRDP
xcrush.c
1 
22 #include <winpr/assert.h>
23 #include <freerdp/config.h>
24 
25 #include <winpr/crt.h>
26 #include <winpr/print.h>
27 #include <winpr/bitstream.h>
28 
29 #include <freerdp/log.h>
30 #include "xcrush.h"
31 
32 #pragma pack(push, 1)
33 
34 typedef struct
35 {
36  UINT32 MatchOffset;
37  UINT32 ChunkOffset;
38  UINT32 MatchLength;
39 } XCRUSH_MATCH_INFO;
40 
41 typedef struct
42 {
43  UINT32 offset;
44  UINT32 next;
45 } XCRUSH_CHUNK;
46 
47 typedef struct
48 {
49  UINT16 seed;
50  UINT16 size;
51 } XCRUSH_SIGNATURE;
52 
53 typedef struct
54 {
55  UINT16 MatchLength;
56  UINT16 MatchOutputOffset;
57  UINT32 MatchHistoryOffset;
58 } RDP61_MATCH_DETAILS;
59 
60 typedef struct
61 {
62  BYTE Level1ComprFlags;
63  BYTE Level2ComprFlags;
64  UINT16 MatchCount;
65  RDP61_MATCH_DETAILS* MatchDetails;
66  BYTE* Literals;
67 } RDP61_COMPRESSED_DATA;
68 
69 #pragma pack(pop)
70 
71 struct s_XCRUSH_CONTEXT
72 {
73  ALIGN64 BOOL Compressor;
74  ALIGN64 MPPC_CONTEXT* mppc;
75  ALIGN64 BYTE* HistoryPtr;
76  ALIGN64 UINT32 HistoryOffset;
77  ALIGN64 UINT32 HistoryBufferSize;
78  ALIGN64 BYTE HistoryBuffer[2000000];
79  ALIGN64 BYTE BlockBuffer[16384];
80  ALIGN64 UINT32 CompressionFlags;
81  ALIGN64 UINT32 SignatureIndex;
82  ALIGN64 UINT32 SignatureCount;
83  ALIGN64 XCRUSH_SIGNATURE Signatures[1000];
84  ALIGN64 UINT32 ChunkHead;
85  ALIGN64 UINT32 ChunkTail;
86  ALIGN64 XCRUSH_CHUNK Chunks[65534];
87  ALIGN64 UINT16 NextChunks[65536];
88  ALIGN64 UINT32 OriginalMatchCount;
89  ALIGN64 UINT32 OptimizedMatchCount;
90  ALIGN64 XCRUSH_MATCH_INFO OriginalMatches[1000];
91  ALIGN64 XCRUSH_MATCH_INFO OptimizedMatches[1000];
92 };
93 
94 //#define DEBUG_XCRUSH 1
95 #if defined(DEBUG_XCRUSH)
96 static const char* xcrush_get_level_2_compression_flags_string(UINT32 flags)
97 {
98  flags &= 0xE0;
99 
100  if (flags == 0)
101  return "PACKET_UNCOMPRESSED";
102  else if (flags == PACKET_COMPRESSED)
103  return "PACKET_COMPRESSED";
104  else if (flags == PACKET_AT_FRONT)
105  return "PACKET_AT_FRONT";
106  else if (flags == PACKET_FLUSHED)
107  return "PACKET_FLUSHED";
108  else if (flags == (PACKET_COMPRESSED | PACKET_AT_FRONT))
109  return "PACKET_COMPRESSED | PACKET_AT_FRONT";
110  else if (flags == (PACKET_COMPRESSED | PACKET_FLUSHED))
111  return "PACKET_COMPRESSED | PACKET_FLUSHED";
112  else if (flags == (PACKET_AT_FRONT | PACKET_FLUSHED))
113  return "PACKET_AT_FRONT | PACKET_FLUSHED";
114  else if (flags == (PACKET_COMPRESSED | PACKET_AT_FRONT | PACKET_FLUSHED))
115  return "PACKET_COMPRESSED | PACKET_AT_FRONT | PACKET_FLUSHED";
116 
117  return "PACKET_UNKNOWN";
118 }
119 
120 static const char* xcrush_get_level_1_compression_flags_string(UINT32 flags)
121 {
122  flags &= 0x17;
123 
124  if (flags == 0)
125  return "L1_UNKNOWN";
126  else if (flags == L1_PACKET_AT_FRONT)
127  return "L1_PACKET_AT_FRONT";
128  else if (flags == L1_NO_COMPRESSION)
129  return "L1_NO_COMPRESSION";
130  else if (flags == L1_COMPRESSED)
131  return "L1_COMPRESSED";
132  else if (flags == L1_INNER_COMPRESSION)
133  return "L1_INNER_COMPRESSION";
134  else if (flags == (L1_PACKET_AT_FRONT | L1_NO_COMPRESSION))
135  return "L1_PACKET_AT_FRONT | L1_NO_COMPRESSION";
136  else if (flags == (L1_PACKET_AT_FRONT | L1_COMPRESSED))
137  return "L1_PACKET_AT_FRONT | L1_COMPRESSED";
138  else if (flags == (L1_PACKET_AT_FRONT | L1_INNER_COMPRESSION))
139  return "L1_PACKET_AT_FRONT | L1_INNER_COMPRESSION";
140  else if (flags == (L1_NO_COMPRESSION | L1_COMPRESSED))
141  return "L1_NO_COMPRESSION | L1_COMPRESSED";
142  else if (flags == (L1_NO_COMPRESSION | L1_INNER_COMPRESSION))
143  return "L1_NO_COMPRESSION | L1_INNER_COMPRESSION";
144  else if (flags == (L1_COMPRESSED | L1_INNER_COMPRESSION))
145  return "L1_COMPRESSED | L1_INNER_COMPRESSION";
146  else if (flags == (L1_NO_COMPRESSION | L1_COMPRESSED | L1_INNER_COMPRESSION))
147  return "L1_NO_COMPRESSION | L1_COMPRESSED | L1_INNER_COMPRESSION";
148  else if (flags == (L1_PACKET_AT_FRONT | L1_COMPRESSED | L1_INNER_COMPRESSION))
149  return "L1_PACKET_AT_FRONT | L1_COMPRESSED | L1_INNER_COMPRESSION";
150  else if (flags == (L1_PACKET_AT_FRONT | L1_NO_COMPRESSION | L1_INNER_COMPRESSION))
151  return "L1_PACKET_AT_FRONT | L1_NO_COMPRESSION | L1_INNER_COMPRESSION";
152  else if (flags == (L1_PACKET_AT_FRONT | L1_NO_COMPRESSION | L1_COMPRESSED))
153  return "L1_PACKET_AT_FRONT | L1_NO_COMPRESSION | L1_COMPRESSED";
154  else if (flags ==
155  (L1_PACKET_AT_FRONT | L1_NO_COMPRESSION | L1_COMPRESSED | L1_INNER_COMPRESSION))
156  return "L1_PACKET_AT_FRONT | L1_NO_COMPRESSION | L1_COMPRESSED | L1_INNER_COMPRESSION";
157 
158  return "L1_UNKNOWN";
159 }
160 #endif
161 
162 static UINT32 xcrush_update_hash(const BYTE* WINPR_RESTRICT data, UINT32 size)
163 {
164  const BYTE* end = NULL;
165  UINT32 seed = 5381; /* same value as in djb2 */
166 
167  WINPR_ASSERT(data);
168  WINPR_ASSERT(size >= 4);
169 
170  if (size > 32)
171  {
172  size = 32;
173  seed = 5413;
174  }
175 
176  end = &data[size - 4];
177 
178  while (data < end)
179  {
180  seed += (data[3] ^ data[0]) + (data[1] << 8);
181  data += 4;
182  }
183 
184  return (UINT16)seed;
185 }
186 
187 static int xcrush_append_chunk(XCRUSH_CONTEXT* WINPR_RESTRICT xcrush,
188  const BYTE* WINPR_RESTRICT data, UINT32* WINPR_RESTRICT beg,
189  UINT32 end)
190 {
191  UINT32 size = 0;
192 
193  WINPR_ASSERT(xcrush);
194  WINPR_ASSERT(data);
195  WINPR_ASSERT(beg);
196 
197  if (xcrush->SignatureIndex >= xcrush->SignatureCount)
198  return 0;
199 
200  size = end - *beg;
201 
202  if (size > 65535)
203  return 0;
204 
205  if (size >= 15)
206  {
207  UINT32 seed = xcrush_update_hash(&data[*beg], (UINT16)size);
208  xcrush->Signatures[xcrush->SignatureIndex].size = size;
209  xcrush->Signatures[xcrush->SignatureIndex].seed = seed;
210  xcrush->SignatureIndex++;
211  *beg = end;
212  }
213 
214  return 1;
215 }
216 
217 static int xcrush_compute_chunks(XCRUSH_CONTEXT* WINPR_RESTRICT xcrush,
218  const BYTE* WINPR_RESTRICT data, UINT32 size,
219  UINT32* WINPR_RESTRICT pIndex)
220 {
221  UINT32 offset = 0;
222  UINT32 rotation = 0;
223  UINT32 accumulator = 0;
224 
225  WINPR_ASSERT(xcrush);
226  WINPR_ASSERT(data);
227  WINPR_ASSERT(pIndex);
228 
229  *pIndex = 0;
230  xcrush->SignatureIndex = 0;
231 
232  if (size < 128)
233  return 0;
234 
235  for (UINT32 i = 0; i < 32; i++)
236  {
237  rotation = _rotl(accumulator, 1);
238  accumulator = data[i] ^ rotation;
239  }
240 
241  for (UINT32 i = 0; i < size - 64; i++)
242  {
243  rotation = _rotl(accumulator, 1);
244  accumulator = data[i + 32] ^ data[i] ^ rotation;
245 
246  if (!(accumulator & 0x7F))
247  {
248  if (!xcrush_append_chunk(xcrush, data, &offset, i + 32))
249  return 0;
250  }
251 
252  i++;
253  rotation = _rotl(accumulator, 1);
254  accumulator = data[i + 32] ^ data[i] ^ rotation;
255 
256  if (!(accumulator & 0x7F))
257  {
258  if (!xcrush_append_chunk(xcrush, data, &offset, i + 32))
259  return 0;
260  }
261 
262  i++;
263  rotation = _rotl(accumulator, 1);
264  accumulator = data[i + 32] ^ data[i] ^ rotation;
265 
266  if (!(accumulator & 0x7F))
267  {
268  if (!xcrush_append_chunk(xcrush, data, &offset, i + 32))
269  return 0;
270  }
271 
272  i++;
273  rotation = _rotl(accumulator, 1);
274  accumulator = data[i + 32] ^ data[i] ^ rotation;
275 
276  if (!(accumulator & 0x7F))
277  {
278  if (!xcrush_append_chunk(xcrush, data, &offset, i + 32))
279  return 0;
280  }
281  }
282 
283  if ((size == offset) || xcrush_append_chunk(xcrush, data, &offset, size))
284  {
285  *pIndex = xcrush->SignatureIndex;
286  return 1;
287  }
288 
289  return 0;
290 }
291 
292 static UINT32 xcrush_compute_signatures(XCRUSH_CONTEXT* WINPR_RESTRICT xcrush,
293  const BYTE* WINPR_RESTRICT data, UINT32 size)
294 {
295  UINT32 index = 0;
296 
297  if (xcrush_compute_chunks(xcrush, data, size, &index))
298  return index;
299 
300  return 0;
301 }
302 
303 static void xcrush_clear_hash_table_range(XCRUSH_CONTEXT* WINPR_RESTRICT xcrush, UINT32 beg,
304  UINT32 end)
305 {
306  WINPR_ASSERT(xcrush);
307 
308  for (UINT32 index = 0; index < 65536; index++)
309  {
310  if (xcrush->NextChunks[index] >= beg)
311  {
312  if (xcrush->NextChunks[index] <= end)
313  {
314  xcrush->NextChunks[index] = 0;
315  }
316  }
317  }
318 
319  for (UINT32 index = 0; index < 65534; index++)
320  {
321  if (xcrush->Chunks[index].next >= beg)
322  {
323  if (xcrush->Chunks[index].next <= end)
324  {
325  xcrush->Chunks[index].next = 0;
326  }
327  }
328  }
329 }
330 
331 static int xcrush_find_next_matching_chunk(XCRUSH_CONTEXT* WINPR_RESTRICT xcrush,
332  XCRUSH_CHUNK* WINPR_RESTRICT chunk,
333  XCRUSH_CHUNK** WINPR_RESTRICT pNextChunk)
334 {
335  XCRUSH_CHUNK* next = NULL;
336 
337  WINPR_ASSERT(xcrush);
338 
339  if (!chunk)
340  return -4001; /* error */
341 
342  if (chunk->next)
343  {
344  // NOLINTNEXTLINE(bugprone-sizeof-expression)
345  const intptr_t diff = (chunk - xcrush->Chunks);
346  if (diff < 0)
347  return -4011;
348 
349  const size_t index = (size_t)diff / sizeof(XCRUSH_CHUNK);
350  if (index >= 65534)
351  return -4002; /* error */
352 
353  if ((index < xcrush->ChunkHead) || (chunk->next >= xcrush->ChunkHead))
354  {
355  if (chunk->next >= 65534)
356  return -4003; /* error */
357 
358  next = &xcrush->Chunks[chunk->next];
359  }
360  }
361 
362  WINPR_ASSERT(pNextChunk);
363  *pNextChunk = next;
364  return 1;
365 }
366 
367 static int xcrush_insert_chunk(XCRUSH_CONTEXT* WINPR_RESTRICT xcrush,
368  XCRUSH_SIGNATURE* WINPR_RESTRICT signature, UINT32 offset,
369  XCRUSH_CHUNK** WINPR_RESTRICT pPrevChunk)
370 {
371  UINT32 seed = 0;
372  UINT32 index = 0;
373 
374  WINPR_ASSERT(xcrush);
375 
376  if (xcrush->ChunkHead >= 65530)
377  {
378  xcrush->ChunkHead = 1;
379  xcrush->ChunkTail = 1;
380  }
381 
382  if (xcrush->ChunkHead >= xcrush->ChunkTail)
383  {
384  xcrush_clear_hash_table_range(xcrush, xcrush->ChunkTail, xcrush->ChunkTail + 10000);
385  xcrush->ChunkTail += 10000;
386  }
387 
388  index = xcrush->ChunkHead++;
389 
390  if (xcrush->ChunkHead >= 65534)
391  return -3001; /* error */
392 
393  xcrush->Chunks[index].offset = offset;
394  seed = signature->seed;
395 
396  if (seed >= 65536)
397  return -3002; /* error */
398 
399  if (xcrush->NextChunks[seed])
400  {
401  if (xcrush->NextChunks[seed] >= 65534)
402  return -3003; /* error */
403 
404  WINPR_ASSERT(pPrevChunk);
405  *pPrevChunk = &xcrush->Chunks[xcrush->NextChunks[seed]];
406  }
407 
408  xcrush->Chunks[index].next = xcrush->NextChunks[seed] & 0xFFFF;
409  xcrush->NextChunks[seed] = index;
410  return 1;
411 }
412 
413 static int xcrush_find_match_length(XCRUSH_CONTEXT* WINPR_RESTRICT xcrush, UINT32 MatchOffset,
414  UINT32 ChunkOffset, UINT32 HistoryOffset, UINT32 SrcSize,
415  UINT32 MaxMatchLength,
416  XCRUSH_MATCH_INFO* WINPR_RESTRICT MatchInfo)
417 {
418  UINT32 MatchSymbol = 0;
419  UINT32 ChunkSymbol = 0;
420  BYTE* ChunkBuffer = NULL;
421  BYTE* MatchBuffer = NULL;
422  BYTE* MatchStartPtr = NULL;
423  BYTE* ForwardChunkPtr = NULL;
424  BYTE* ReverseChunkPtr = NULL;
425  BYTE* ForwardMatchPtr = NULL;
426  BYTE* ReverseMatchPtr = NULL;
427  BYTE* HistoryBufferEnd = NULL;
428  UINT32 ReverseMatchLength = 0;
429  UINT32 ForwardMatchLength = 0;
430  UINT32 TotalMatchLength = 0;
431  BYTE* HistoryBuffer = NULL;
432  UINT32 HistoryBufferSize = 0;
433 
434  WINPR_ASSERT(xcrush);
435  WINPR_ASSERT(MatchInfo);
436 
437  HistoryBuffer = xcrush->HistoryBuffer;
438  HistoryBufferSize = xcrush->HistoryBufferSize;
439  HistoryBufferEnd = &HistoryBuffer[HistoryOffset + SrcSize];
440 
441  if (MatchOffset > HistoryBufferSize)
442  return -2001; /* error */
443 
444  MatchBuffer = &HistoryBuffer[MatchOffset];
445 
446  if (ChunkOffset > HistoryBufferSize)
447  return -2002; /* error */
448 
449  ChunkBuffer = &HistoryBuffer[ChunkOffset];
450 
451  if (MatchOffset == ChunkOffset)
452  return -2003; /* error */
453 
454  if (MatchBuffer < HistoryBuffer)
455  return -2004; /* error */
456 
457  if (ChunkBuffer < HistoryBuffer)
458  return -2005; /* error */
459 
460  ForwardMatchPtr = &HistoryBuffer[MatchOffset];
461  ForwardChunkPtr = &HistoryBuffer[ChunkOffset];
462 
463  if ((&MatchBuffer[MaxMatchLength + 1] < HistoryBufferEnd) &&
464  (MatchBuffer[MaxMatchLength + 1] != ChunkBuffer[MaxMatchLength + 1]))
465  {
466  return 0;
467  }
468 
469  while (1)
470  {
471  MatchSymbol = *ForwardMatchPtr++;
472  ChunkSymbol = *ForwardChunkPtr++;
473 
474  if (MatchSymbol != ChunkSymbol)
475  break;
476 
477  if (ForwardMatchPtr > HistoryBufferEnd)
478  break;
479 
480  ForwardMatchLength++;
481  }
482 
483  ReverseMatchPtr = MatchBuffer - 1;
484  ReverseChunkPtr = ChunkBuffer - 1;
485 
486  while ((ReverseMatchPtr > &HistoryBuffer[HistoryOffset]) && (ReverseChunkPtr > HistoryBuffer) &&
487  (*ReverseMatchPtr == *ReverseChunkPtr))
488  {
489  ReverseMatchLength++;
490  ReverseMatchPtr--;
491  ReverseChunkPtr--;
492  }
493 
494  MatchStartPtr = MatchBuffer - ReverseMatchLength;
495  TotalMatchLength = ReverseMatchLength + ForwardMatchLength;
496 
497  if (TotalMatchLength < 11)
498  return 0;
499 
500  if (MatchStartPtr < HistoryBuffer)
501  return -2006; /* error */
502 
503  const intptr_t diff = MatchStartPtr - HistoryBuffer;
504  const intptr_t cdiff = ChunkBuffer - ReverseMatchLength - HistoryBuffer;
505  if ((diff > UINT32_MAX) || (diff < 0) || (cdiff < 0) || (cdiff > UINT32_MAX))
506  return -1;
507  MatchInfo->MatchOffset = (UINT32)diff;
508  MatchInfo->ChunkOffset = (UINT32)cdiff;
509  MatchInfo->MatchLength = TotalMatchLength;
510  return (int)TotalMatchLength;
511 }
512 
513 static int xcrush_find_all_matches(XCRUSH_CONTEXT* WINPR_RESTRICT xcrush, UINT32 SignatureIndex,
514  UINT32 HistoryOffset, UINT32 SrcOffset, UINT32 SrcSize)
515 {
516  UINT32 j = 0;
517  int status = 0;
518  UINT32 ChunkIndex = 0;
519  UINT32 ChunkCount = 0;
520  XCRUSH_CHUNK* chunk = NULL;
521  UINT32 MatchLength = 0;
522  UINT32 MaxMatchLength = 0;
523  UINT32 PrevMatchEnd = 0;
524  XCRUSH_SIGNATURE* Signatures = NULL;
525  XCRUSH_MATCH_INFO MaxMatchInfo = { 0 };
526 
527  WINPR_ASSERT(xcrush);
528 
529  Signatures = xcrush->Signatures;
530 
531  for (UINT32 i = 0; i < SignatureIndex; i++)
532  {
533  XCRUSH_MATCH_INFO MatchInfo = { 0 };
534  UINT32 offset = SrcOffset + HistoryOffset;
535 
536  if (!Signatures[i].size)
537  return -1001; /* error */
538 
539  status = xcrush_insert_chunk(xcrush, &Signatures[i], offset, &chunk);
540 
541  if (status < 0)
542  return status;
543 
544  if (chunk && (SrcOffset + HistoryOffset + Signatures[i].size >= PrevMatchEnd))
545  {
546  ChunkCount = 0;
547  MaxMatchLength = 0;
548 
549  while (chunk)
550  {
551  if ((chunk->offset < HistoryOffset) || (chunk->offset < offset) ||
552  (chunk->offset > SrcSize + HistoryOffset))
553  {
554  status = xcrush_find_match_length(xcrush, offset, chunk->offset, HistoryOffset,
555  SrcSize, MaxMatchLength, &MatchInfo);
556 
557  if (status < 0)
558  return status; /* error */
559 
560  MatchLength = (UINT32)status;
561 
562  if (MatchLength > MaxMatchLength)
563  {
564  MaxMatchLength = MatchLength;
565  MaxMatchInfo.MatchOffset = MatchInfo.MatchOffset;
566  MaxMatchInfo.ChunkOffset = MatchInfo.ChunkOffset;
567  MaxMatchInfo.MatchLength = MatchInfo.MatchLength;
568 
569  if (MatchLength > 256)
570  break;
571  }
572  }
573 
574  ChunkIndex = ChunkCount++;
575 
576  if (ChunkIndex > 4)
577  break;
578 
579  status = xcrush_find_next_matching_chunk(xcrush, chunk, &chunk);
580 
581  if (status < 0)
582  return status; /* error */
583  }
584 
585  if (MaxMatchLength)
586  {
587  xcrush->OriginalMatches[j].MatchOffset = MaxMatchInfo.MatchOffset;
588  xcrush->OriginalMatches[j].ChunkOffset = MaxMatchInfo.ChunkOffset;
589  xcrush->OriginalMatches[j].MatchLength = MaxMatchInfo.MatchLength;
590 
591  if (xcrush->OriginalMatches[j].MatchOffset < HistoryOffset)
592  return -1002; /* error */
593 
594  PrevMatchEnd =
595  xcrush->OriginalMatches[j].MatchLength + xcrush->OriginalMatches[j].MatchOffset;
596  j++;
597 
598  if (j >= 1000)
599  return -1003; /* error */
600  }
601  }
602 
603  SrcOffset += Signatures[i].size;
604 
605  if (SrcOffset > SrcSize)
606  return -1004; /* error */
607  }
608 
609  if (SrcOffset > SrcSize)
610  return -1005; /* error */
611 
612  return (int)j;
613 }
614 
615 static int xcrush_optimize_matches(XCRUSH_CONTEXT* WINPR_RESTRICT xcrush)
616 {
617  UINT32 j = 0;
618  UINT32 MatchDiff = 0;
619  UINT32 PrevMatchEnd = 0;
620  UINT32 TotalMatchLength = 0;
621  UINT32 OriginalMatchCount = 0;
622  UINT32 OptimizedMatchCount = 0;
623  XCRUSH_MATCH_INFO* OriginalMatch = NULL;
624  XCRUSH_MATCH_INFO* OptimizedMatch = NULL;
625  XCRUSH_MATCH_INFO* OriginalMatches = NULL;
626  XCRUSH_MATCH_INFO* OptimizedMatches = NULL;
627 
628  WINPR_ASSERT(xcrush);
629 
630  OriginalMatches = xcrush->OriginalMatches;
631  OriginalMatchCount = xcrush->OriginalMatchCount;
632  OptimizedMatches = xcrush->OptimizedMatches;
633 
634  for (UINT32 i = 0; i < OriginalMatchCount; i++)
635  {
636  if (OriginalMatches[i].MatchOffset <= PrevMatchEnd)
637  {
638  if ((OriginalMatches[i].MatchOffset < PrevMatchEnd) &&
639  (OriginalMatches[i].MatchLength + OriginalMatches[i].MatchOffset >
640  PrevMatchEnd + 6))
641  {
642  MatchDiff = PrevMatchEnd - OriginalMatches[i].MatchOffset;
643  OriginalMatch = &OriginalMatches[i];
644  OptimizedMatch = &OptimizedMatches[j];
645  OptimizedMatch->MatchOffset = OriginalMatch->MatchOffset;
646  OptimizedMatch->ChunkOffset = OriginalMatch->ChunkOffset;
647  OptimizedMatch->MatchLength = OriginalMatch->MatchLength;
648 
649  if (OptimizedMatches[j].MatchLength <= MatchDiff)
650  return -5001; /* error */
651 
652  if (MatchDiff >= 20000)
653  return -5002; /* error */
654 
655  OptimizedMatches[j].MatchLength -= MatchDiff;
656  OptimizedMatches[j].MatchOffset += MatchDiff;
657  OptimizedMatches[j].ChunkOffset += MatchDiff;
658  PrevMatchEnd = OptimizedMatches[j].MatchLength + OptimizedMatches[j].MatchOffset;
659  TotalMatchLength += OptimizedMatches[j].MatchLength;
660  j++;
661  }
662  }
663  else
664  {
665  OriginalMatch = &OriginalMatches[i];
666  OptimizedMatch = &OptimizedMatches[j];
667  OptimizedMatch->MatchOffset = OriginalMatch->MatchOffset;
668  OptimizedMatch->ChunkOffset = OriginalMatch->ChunkOffset;
669  OptimizedMatch->MatchLength = OriginalMatch->MatchLength;
670  PrevMatchEnd = OptimizedMatches[j].MatchLength + OptimizedMatches[j].MatchOffset;
671  TotalMatchLength += OptimizedMatches[j].MatchLength;
672  j++;
673  }
674  }
675 
676  OptimizedMatchCount = j;
677  xcrush->OptimizedMatchCount = OptimizedMatchCount;
678  return (int)TotalMatchLength;
679 }
680 
681 static int xcrush_generate_output(XCRUSH_CONTEXT* WINPR_RESTRICT xcrush,
682  BYTE* WINPR_RESTRICT OutputBuffer, UINT32 OutputSize,
683  UINT32 HistoryOffset, UINT32* WINPR_RESTRICT pDstSize)
684 {
685  BYTE* Literals = NULL;
686  BYTE* OutputEnd = NULL;
687  UINT32 MatchIndex = 0;
688  UINT32 MatchOffset = 0;
689  UINT16 MatchLength = 0;
690  UINT32 MatchCount = 0;
691  UINT32 CurrentOffset = 0;
692  UINT32 MatchOffsetDiff = 0;
693  UINT32 HistoryOffsetDiff = 0;
694  RDP61_MATCH_DETAILS* MatchDetails = NULL;
695 
696  WINPR_ASSERT(xcrush);
697  WINPR_ASSERT(OutputBuffer);
698  WINPR_ASSERT(OutputSize >= 2);
699  WINPR_ASSERT(pDstSize);
700 
701  MatchCount = xcrush->OptimizedMatchCount;
702  OutputEnd = &OutputBuffer[OutputSize];
703 
704  if (&OutputBuffer[2] >= &OutputBuffer[OutputSize])
705  return -6001; /* error */
706 
707  Data_Write_UINT16(OutputBuffer, MatchCount);
708  MatchDetails = (RDP61_MATCH_DETAILS*)&OutputBuffer[2];
709  Literals = (BYTE*)&MatchDetails[MatchCount];
710 
711  if (Literals > OutputEnd)
712  return -6002; /* error */
713 
714  for (MatchIndex = 0; MatchIndex < MatchCount; MatchIndex++)
715  {
716  Data_Write_UINT16(&MatchDetails[MatchIndex].MatchLength,
717  xcrush->OptimizedMatches[MatchIndex].MatchLength);
718  Data_Write_UINT16(&MatchDetails[MatchIndex].MatchOutputOffset,
719  xcrush->OptimizedMatches[MatchIndex].MatchOffset - HistoryOffset);
720  Data_Write_UINT32(&MatchDetails[MatchIndex].MatchHistoryOffset,
721  xcrush->OptimizedMatches[MatchIndex].ChunkOffset);
722  }
723 
724  CurrentOffset = HistoryOffset;
725 
726  for (MatchIndex = 0; MatchIndex < MatchCount; MatchIndex++)
727  {
728  MatchLength = (UINT16)(xcrush->OptimizedMatches[MatchIndex].MatchLength);
729  MatchOffset = xcrush->OptimizedMatches[MatchIndex].MatchOffset;
730 
731  if (MatchOffset <= CurrentOffset)
732  {
733  if (MatchOffset != CurrentOffset)
734  return -6003; /* error */
735 
736  CurrentOffset = MatchOffset + MatchLength;
737  }
738  else
739  {
740  MatchOffsetDiff = MatchOffset - CurrentOffset;
741 
742  if (Literals + MatchOffset - CurrentOffset >= OutputEnd)
743  return -6004; /* error */
744 
745  CopyMemory(Literals, &xcrush->HistoryBuffer[CurrentOffset], MatchOffsetDiff);
746 
747  if (Literals >= OutputEnd)
748  return -6005; /* error */
749 
750  Literals += MatchOffsetDiff;
751  CurrentOffset = MatchOffset + MatchLength;
752  }
753  }
754 
755  HistoryOffsetDiff = xcrush->HistoryOffset - CurrentOffset;
756 
757  if (Literals + HistoryOffsetDiff >= OutputEnd)
758  return -6006; /* error */
759 
760  CopyMemory(Literals, &xcrush->HistoryBuffer[CurrentOffset], HistoryOffsetDiff);
761  const intptr_t diff = Literals + HistoryOffsetDiff - OutputBuffer;
762  if ((diff < 0) || (diff > UINT32_MAX))
763  return -1;
764  *pDstSize = (UINT32)diff;
765  return 1;
766 }
767 
768 static INLINE size_t xcrush_copy_bytes_no_overlap(BYTE* WINPR_RESTRICT dst,
769  const BYTE* WINPR_RESTRICT src, size_t num)
770 {
771  // src and dst overlaps
772  // we should copy the area that doesn't overlap repeatly
773  const size_t diff = (dst > src) ? dst - src : src - dst;
774  const size_t rest = num % diff;
775  const size_t end = num - rest;
776 
777  for (size_t a = 0; a < end; a += diff)
778  memcpy(&dst[a], &src[a], diff);
779 
780  if (rest != 0)
781  memcpy(&dst[end], &src[end], rest);
782 
783  return num;
784 }
785 
786 static INLINE size_t xcrush_copy_bytes(BYTE* dst, const BYTE* src, size_t num)
787 {
788  WINPR_ASSERT(dst);
789  WINPR_ASSERT(src);
790 
791  if (src + num < dst || src > dst + num)
792  memcpy(dst, src, num);
793  else if (src != dst)
794  return xcrush_copy_bytes_no_overlap(dst, src, num);
795 
796  return num;
797 }
798 
799 static int xcrush_decompress_l1(XCRUSH_CONTEXT* WINPR_RESTRICT xcrush,
800  const BYTE* WINPR_RESTRICT pSrcData, UINT32 SrcSize,
801  const BYTE** WINPR_RESTRICT ppDstData,
802  UINT32* WINPR_RESTRICT pDstSize, UINT32 flags)
803 {
804  const BYTE* pSrcEnd = NULL;
805  const BYTE* Literals = NULL;
806  UINT16 MatchCount = 0;
807  UINT16 MatchIndex = 0;
808  BYTE* OutputPtr = NULL;
809  size_t OutputLength = 0;
810  UINT32 OutputOffset = 0;
811  BYTE* HistoryPtr = NULL;
812  BYTE* HistoryBuffer = NULL;
813  BYTE* HistoryBufferEnd = NULL;
814  UINT32 HistoryBufferSize = 0;
815  UINT16 MatchLength = 0;
816  UINT16 MatchOutputOffset = 0;
817  UINT32 MatchHistoryOffset = 0;
818  const RDP61_MATCH_DETAILS* MatchDetails = NULL;
819 
820  WINPR_ASSERT(xcrush);
821 
822  if (SrcSize < 1)
823  return -1001;
824 
825  WINPR_ASSERT(pSrcData);
826  WINPR_ASSERT(ppDstData);
827  WINPR_ASSERT(pDstSize);
828 
829  if (flags & L1_PACKET_AT_FRONT)
830  xcrush->HistoryOffset = 0;
831 
832  pSrcEnd = &pSrcData[SrcSize];
833  HistoryBuffer = xcrush->HistoryBuffer;
834  HistoryBufferSize = xcrush->HistoryBufferSize;
835  HistoryBufferEnd = &(HistoryBuffer[HistoryBufferSize]);
836  xcrush->HistoryPtr = HistoryPtr = &(HistoryBuffer[xcrush->HistoryOffset]);
837 
838  if (flags & L1_NO_COMPRESSION)
839  {
840  Literals = pSrcData;
841  }
842  else
843  {
844  if (!(flags & L1_COMPRESSED))
845  return -1002;
846 
847  if ((pSrcData + 2) > pSrcEnd)
848  return -1003;
849 
850  Data_Read_UINT16(pSrcData, MatchCount);
851  MatchDetails = (const RDP61_MATCH_DETAILS*)&pSrcData[2];
852  Literals = (const BYTE*)&MatchDetails[MatchCount];
853  OutputOffset = 0;
854 
855  if (Literals > pSrcEnd)
856  return -1004;
857 
858  for (MatchIndex = 0; MatchIndex < MatchCount; MatchIndex++)
859  {
860  Data_Read_UINT16(&MatchDetails[MatchIndex].MatchLength, MatchLength);
861  Data_Read_UINT16(&MatchDetails[MatchIndex].MatchOutputOffset, MatchOutputOffset);
862  Data_Read_UINT32(&MatchDetails[MatchIndex].MatchHistoryOffset, MatchHistoryOffset);
863 
864  if (MatchOutputOffset < OutputOffset)
865  return -1005;
866 
867  if (MatchLength > HistoryBufferSize)
868  return -1006;
869 
870  if (MatchHistoryOffset > HistoryBufferSize)
871  return -1007;
872 
873  OutputLength = MatchOutputOffset - OutputOffset;
874 
875  if ((MatchOutputOffset - OutputOffset) > HistoryBufferSize)
876  return -1008;
877 
878  if (OutputLength > 0)
879  {
880  if ((&HistoryPtr[OutputLength] >= HistoryBufferEnd) || (Literals >= pSrcEnd) ||
881  (&Literals[OutputLength] > pSrcEnd))
882  return -1009;
883 
884  xcrush_copy_bytes(HistoryPtr, Literals, OutputLength);
885  HistoryPtr += OutputLength;
886  Literals += OutputLength;
887  OutputOffset += OutputLength;
888 
889  if (Literals > pSrcEnd)
890  return -1010;
891  }
892 
893  OutputPtr = &xcrush->HistoryBuffer[MatchHistoryOffset];
894 
895  if ((&HistoryPtr[MatchLength] >= HistoryBufferEnd) ||
896  (&OutputPtr[MatchLength] >= HistoryBufferEnd))
897  return -1011;
898 
899  xcrush_copy_bytes(HistoryPtr, OutputPtr, MatchLength);
900  OutputOffset += MatchLength;
901  HistoryPtr += MatchLength;
902  }
903  }
904 
905  if (Literals < pSrcEnd)
906  {
907  OutputLength = pSrcEnd - Literals;
908 
909  if ((&HistoryPtr[OutputLength] >= HistoryBufferEnd) || (&Literals[OutputLength] > pSrcEnd))
910  return -1012;
911 
912  xcrush_copy_bytes(HistoryPtr, Literals, OutputLength);
913  HistoryPtr += OutputLength;
914  }
915 
916  const intptr_t diff = HistoryPtr - HistoryBuffer;
917  if ((diff < 0) || (diff > UINT32_MAX))
918  return -1;
919  xcrush->HistoryOffset = (UINT32)diff;
920 
921  const intptr_t sizediff = HistoryPtr - xcrush->HistoryPtr;
922  if ((sizediff < 0) || (sizediff > UINT32_MAX))
923  return -1;
924  *pDstSize = (UINT32)sizediff;
925  *ppDstData = xcrush->HistoryPtr;
926  return 1;
927 }
928 
929 int xcrush_decompress(XCRUSH_CONTEXT* WINPR_RESTRICT xcrush, const BYTE* WINPR_RESTRICT pSrcData,
930  UINT32 SrcSize, const BYTE** WINPR_RESTRICT ppDstData,
931  UINT32* WINPR_RESTRICT pDstSize, UINT32 flags)
932 {
933  int status = 0;
934  UINT32 DstSize = 0;
935  const BYTE* pDstData = NULL;
936  BYTE Level1ComprFlags = 0;
937  BYTE Level2ComprFlags = 0;
938 
939  WINPR_ASSERT(xcrush);
940 
941  if (SrcSize < 2)
942  return -1;
943 
944  WINPR_ASSERT(pSrcData);
945  WINPR_ASSERT(ppDstData);
946  WINPR_ASSERT(pDstSize);
947 
948  Level1ComprFlags = pSrcData[0];
949  Level2ComprFlags = pSrcData[1];
950  pSrcData += 2;
951  SrcSize -= 2;
952 
953  if (flags & PACKET_FLUSHED)
954  {
955  ZeroMemory(xcrush->HistoryBuffer, xcrush->HistoryBufferSize);
956  xcrush->HistoryOffset = 0;
957  }
958 
959  if (!(Level2ComprFlags & PACKET_COMPRESSED))
960  {
961  status =
962  xcrush_decompress_l1(xcrush, pSrcData, SrcSize, ppDstData, pDstSize, Level1ComprFlags);
963  return status;
964  }
965 
966  status =
967  mppc_decompress(xcrush->mppc, pSrcData, SrcSize, &pDstData, &DstSize, Level2ComprFlags);
968 
969  if (status < 0)
970  return status;
971 
972  status = xcrush_decompress_l1(xcrush, pDstData, DstSize, ppDstData, pDstSize, Level1ComprFlags);
973  return status;
974 }
975 
976 static int xcrush_compress_l1(XCRUSH_CONTEXT* WINPR_RESTRICT xcrush,
977  const BYTE* WINPR_RESTRICT pSrcData, UINT32 SrcSize,
978  BYTE* WINPR_RESTRICT pDstData, UINT32* WINPR_RESTRICT pDstSize,
979  UINT32* WINPR_RESTRICT pFlags)
980 {
981  int status = 0;
982  UINT32 Flags = 0;
983  UINT32 HistoryOffset = 0;
984  BYTE* HistoryPtr = NULL;
985  BYTE* HistoryBuffer = NULL;
986  UINT32 SignatureIndex = 0;
987 
988  WINPR_ASSERT(xcrush);
989  WINPR_ASSERT(pSrcData);
990  WINPR_ASSERT(SrcSize > 0);
991  WINPR_ASSERT(pDstData);
992  WINPR_ASSERT(pDstSize);
993  WINPR_ASSERT(pFlags);
994 
995  if (xcrush->HistoryOffset + SrcSize + 8 > xcrush->HistoryBufferSize)
996  {
997  xcrush->HistoryOffset = 0;
998  Flags |= L1_PACKET_AT_FRONT;
999  }
1000 
1001  HistoryOffset = xcrush->HistoryOffset;
1002  HistoryBuffer = xcrush->HistoryBuffer;
1003  HistoryPtr = &HistoryBuffer[HistoryOffset];
1004  MoveMemory(HistoryPtr, pSrcData, SrcSize);
1005  xcrush->HistoryOffset += SrcSize;
1006 
1007  if (SrcSize > 50)
1008  {
1009  SignatureIndex = xcrush_compute_signatures(xcrush, pSrcData, SrcSize);
1010 
1011  if (SignatureIndex)
1012  {
1013  status = xcrush_find_all_matches(xcrush, SignatureIndex, HistoryOffset, 0, SrcSize);
1014 
1015  if (status < 0)
1016  return status;
1017 
1018  xcrush->OriginalMatchCount = (UINT32)status;
1019  xcrush->OptimizedMatchCount = 0;
1020 
1021  if (xcrush->OriginalMatchCount)
1022  {
1023  status = xcrush_optimize_matches(xcrush);
1024 
1025  if (status < 0)
1026  return status;
1027  }
1028 
1029  if (xcrush->OptimizedMatchCount)
1030  {
1031  status = xcrush_generate_output(xcrush, pDstData, SrcSize, HistoryOffset, pDstSize);
1032 
1033  if (status < 0)
1034  return status;
1035 
1036  Flags |= L1_COMPRESSED;
1037  }
1038  }
1039  }
1040 
1041  if (!(Flags & L1_COMPRESSED))
1042  {
1043  Flags |= L1_NO_COMPRESSION;
1044  *pDstSize = SrcSize;
1045  }
1046 
1047  *pFlags = Flags;
1048  return 1;
1049 }
1050 
1051 int xcrush_compress(XCRUSH_CONTEXT* WINPR_RESTRICT xcrush, const BYTE* WINPR_RESTRICT pSrcData,
1052  UINT32 SrcSize, BYTE* WINPR_RESTRICT pDstBuffer,
1053  const BYTE** WINPR_RESTRICT ppDstData, UINT32* WINPR_RESTRICT pDstSize,
1054  UINT32* WINPR_RESTRICT pFlags)
1055 {
1056  int status = 0;
1057  UINT32 DstSize = 0;
1058  BYTE* pDstData = NULL;
1059  const BYTE* CompressedData = NULL;
1060  UINT32 CompressedDataSize = 0;
1061  BYTE* OriginalData = NULL;
1062  UINT32 OriginalDataSize = 0;
1063  UINT32 Level1ComprFlags = 0;
1064  UINT32 Level2ComprFlags = 0;
1065  UINT32 CompressionLevel = 3;
1066 
1067  WINPR_ASSERT(xcrush);
1068  WINPR_ASSERT(pSrcData);
1069  WINPR_ASSERT(SrcSize > 0);
1070  WINPR_ASSERT(ppDstData);
1071  WINPR_ASSERT(pDstSize);
1072  WINPR_ASSERT(pFlags);
1073 
1074  if (SrcSize > 16384)
1075  return -1001;
1076 
1077  if ((SrcSize + 2) > *pDstSize)
1078  return -1002;
1079 
1080  OriginalData = pDstBuffer;
1081  *ppDstData = pDstBuffer;
1082  OriginalDataSize = SrcSize;
1083  pDstData = xcrush->BlockBuffer;
1084  CompressedDataSize = SrcSize;
1085  status = xcrush_compress_l1(xcrush, pSrcData, SrcSize, pDstData, &CompressedDataSize,
1086  &Level1ComprFlags);
1087 
1088  if (status < 0)
1089  return status;
1090 
1091  if (Level1ComprFlags & L1_COMPRESSED)
1092  {
1093  CompressedData = pDstData;
1094 
1095  if (CompressedDataSize > SrcSize)
1096  return -1003;
1097  }
1098  else
1099  {
1100  CompressedData = pSrcData;
1101 
1102  if (CompressedDataSize != SrcSize)
1103  return -1004;
1104  }
1105 
1106  status = 0;
1107  pDstData = &OriginalData[2];
1108  DstSize = OriginalDataSize - 2;
1109 
1110  if (CompressedDataSize > 50)
1111  {
1112  const BYTE* pUnusedDstData = NULL;
1113  status = mppc_compress(xcrush->mppc, CompressedData, CompressedDataSize, pDstData,
1114  &pUnusedDstData, &DstSize, &Level2ComprFlags);
1115  }
1116 
1117  if (status < 0)
1118  return status;
1119 
1120  if (!status || (Level2ComprFlags & PACKET_FLUSHED))
1121  {
1122  if (CompressedDataSize > DstSize)
1123  {
1124  xcrush_context_reset(xcrush, TRUE);
1125  *ppDstData = pSrcData;
1126  *pDstSize = SrcSize;
1127  *pFlags = 0;
1128  return 1;
1129  }
1130 
1131  DstSize = CompressedDataSize;
1132  CopyMemory(&OriginalData[2], CompressedData, CompressedDataSize);
1133  }
1134 
1135  if (Level2ComprFlags & PACKET_COMPRESSED)
1136  {
1137  Level2ComprFlags |= xcrush->CompressionFlags;
1138  xcrush->CompressionFlags = 0;
1139  }
1140  else if (Level2ComprFlags & PACKET_FLUSHED)
1141  {
1142  xcrush->CompressionFlags = PACKET_FLUSHED;
1143  }
1144 
1145  Level1ComprFlags |= L1_INNER_COMPRESSION;
1146  OriginalData[0] = (BYTE)Level1ComprFlags;
1147  OriginalData[1] = (BYTE)Level2ComprFlags;
1148 #if defined(DEBUG_XCRUSH)
1149  WLog_DBG(TAG, "XCrushCompress: Level1ComprFlags: %s Level2ComprFlags: %s",
1150  xcrush_get_level_1_compression_flags_string(Level1ComprFlags),
1151  xcrush_get_level_2_compression_flags_string(Level2ComprFlags));
1152 #endif
1153 
1154  if (*pDstSize < (DstSize + 2))
1155  return -1006;
1156 
1157  *pDstSize = DstSize + 2;
1158  *pFlags = PACKET_COMPRESSED | CompressionLevel;
1159  return 1;
1160 }
1161 
1162 void xcrush_context_reset(XCRUSH_CONTEXT* WINPR_RESTRICT xcrush, BOOL flush)
1163 {
1164  WINPR_ASSERT(xcrush);
1165 
1166  xcrush->SignatureIndex = 0;
1167  xcrush->SignatureCount = 1000;
1168  ZeroMemory(&(xcrush->Signatures), sizeof(XCRUSH_SIGNATURE) * xcrush->SignatureCount);
1169  xcrush->CompressionFlags = 0;
1170  xcrush->ChunkHead = xcrush->ChunkTail = 1;
1171  ZeroMemory(&(xcrush->Chunks), sizeof(xcrush->Chunks));
1172  ZeroMemory(&(xcrush->NextChunks), sizeof(xcrush->NextChunks));
1173  ZeroMemory(&(xcrush->OriginalMatches), sizeof(xcrush->OriginalMatches));
1174  ZeroMemory(&(xcrush->OptimizedMatches), sizeof(xcrush->OptimizedMatches));
1175 
1176  if (flush)
1177  xcrush->HistoryOffset = xcrush->HistoryBufferSize + 1;
1178  else
1179  xcrush->HistoryOffset = 0;
1180 
1181  mppc_context_reset(xcrush->mppc, flush);
1182 }
1183 
1184 XCRUSH_CONTEXT* xcrush_context_new(BOOL Compressor)
1185 {
1186  XCRUSH_CONTEXT* xcrush = (XCRUSH_CONTEXT*)calloc(1, sizeof(XCRUSH_CONTEXT));
1187 
1188  if (!xcrush)
1189  goto fail;
1190 
1191  xcrush->Compressor = Compressor;
1192  xcrush->mppc = mppc_context_new(1, Compressor);
1193  if (!xcrush->mppc)
1194  goto fail;
1195  xcrush->HistoryBufferSize = 2000000;
1196  xcrush_context_reset(xcrush, FALSE);
1197 
1198  return xcrush;
1199 fail:
1200  xcrush_context_free(xcrush);
1201 
1202  return NULL;
1203 }
1204 
1205 void xcrush_context_free(XCRUSH_CONTEXT* xcrush)
1206 {
1207  if (xcrush)
1208  {
1209  mppc_context_free(xcrush->mppc);
1210  free(xcrush);
1211  }
1212 }