FreeRDP
Loading...
Searching...
No Matches
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
36typedef struct
37{
38 UINT32 MatchOffset;
39 UINT32 ChunkOffset;
40 UINT32 MatchLength;
41} XCRUSH_MATCH_INFO;
42
43typedef struct
44{
45 UINT32 offset;
46 UINT32 next;
47} XCRUSH_CHUNK;
48
49typedef struct
50{
51 UINT16 seed;
52 UINT16 size;
53} XCRUSH_SIGNATURE;
54
55typedef struct
56{
57 UINT16 MatchLength;
58 UINT16 MatchOutputOffset;
59 UINT32 MatchHistoryOffset;
60} RDP61_MATCH_DETAILS;
61
62typedef 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
73struct 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)
98static 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
122static 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
164static 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
189static 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
219static 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
294static 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
305static 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
333static 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
369static 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
409static 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
509static 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
611static 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
677static 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
769static 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
787static 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
800static 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 size_t 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
931int 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
978static 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
1053int 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
1164void 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
1186XCRUSH_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;
1201fail:
1202 xcrush_context_free(xcrush);
1203
1204 return NULL;
1205}
1206
1207void xcrush_context_free(XCRUSH_CONTEXT* xcrush)
1208{
1209 if (xcrush)
1210 {
1211 mppc_context_free(xcrush->mppc);
1212 free(xcrush);
1213 }
1214}