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