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 size_t rest = 0;
776 if (diff != 0)
777 rest = num % diff;
778 const size_t end = num - rest;
779
780 for (size_t a = 0; a < end; a += diff)
781 memcpy(&dst[a], &src[a], diff);
782
783 if (rest != 0)
784 memcpy(&dst[end], &src[end], rest);
785
786 return num;
787}
788
789static inline size_t xcrush_copy_bytes(BYTE* dst, const BYTE* src, size_t num)
790{
791 WINPR_ASSERT(dst);
792 WINPR_ASSERT(src);
793
794 if (src + num < dst || src > dst + num)
795 memcpy(dst, src, num);
796 else if (src != dst)
797 return xcrush_copy_bytes_no_overlap(dst, src, num);
798
799 return num;
800}
801
802static int xcrush_decompress_l1(XCRUSH_CONTEXT* WINPR_RESTRICT xcrush,
803 const BYTE* WINPR_RESTRICT pSrcData, UINT32 SrcSize,
804 const BYTE** WINPR_RESTRICT ppDstData,
805 UINT32* WINPR_RESTRICT pDstSize, UINT32 flags)
806{
807 const BYTE* pSrcEnd = NULL;
808 const BYTE* Literals = NULL;
809 UINT16 MatchCount = 0;
810 UINT16 MatchIndex = 0;
811 BYTE* OutputPtr = NULL;
812 size_t OutputLength = 0;
813 size_t OutputOffset = 0;
814 BYTE* HistoryPtr = NULL;
815 BYTE* HistoryBuffer = NULL;
816 BYTE* HistoryBufferEnd = NULL;
817 UINT32 HistoryBufferSize = 0;
818 UINT16 MatchLength = 0;
819 UINT16 MatchOutputOffset = 0;
820 UINT32 MatchHistoryOffset = 0;
821 const RDP61_MATCH_DETAILS* MatchDetails = NULL;
822
823 WINPR_ASSERT(xcrush);
824
825 if (SrcSize < 1)
826 return -1001;
827
828 WINPR_ASSERT(pSrcData);
829 WINPR_ASSERT(ppDstData);
830 WINPR_ASSERT(pDstSize);
831
832 if (flags & L1_PACKET_AT_FRONT)
833 xcrush->HistoryOffset = 0;
834
835 pSrcEnd = &pSrcData[SrcSize];
836 HistoryBuffer = xcrush->HistoryBuffer;
837 HistoryBufferSize = xcrush->HistoryBufferSize;
838 HistoryBufferEnd = &(HistoryBuffer[HistoryBufferSize]);
839 xcrush->HistoryPtr = HistoryPtr = &(HistoryBuffer[xcrush->HistoryOffset]);
840
841 if (flags & L1_NO_COMPRESSION)
842 {
843 Literals = pSrcData;
844 }
845 else
846 {
847 if (!(flags & L1_COMPRESSED))
848 return -1002;
849
850 if ((pSrcData + 2) > pSrcEnd)
851 return -1003;
852
853 MatchCount = winpr_Data_Get_UINT16(pSrcData);
854 MatchDetails = (const RDP61_MATCH_DETAILS*)&pSrcData[2];
855 Literals = (const BYTE*)&MatchDetails[MatchCount];
856 OutputOffset = 0;
857
858 if (Literals > pSrcEnd)
859 return -1004;
860
861 for (MatchIndex = 0; MatchIndex < MatchCount; MatchIndex++)
862 {
863 MatchLength = winpr_Data_Get_UINT16(&MatchDetails[MatchIndex].MatchLength);
864 MatchOutputOffset = winpr_Data_Get_UINT16(&MatchDetails[MatchIndex].MatchOutputOffset);
865 MatchHistoryOffset =
866 winpr_Data_Get_UINT32(&MatchDetails[MatchIndex].MatchHistoryOffset);
867
868 if (MatchOutputOffset < OutputOffset)
869 return -1005;
870
871 if (MatchLength > HistoryBufferSize)
872 return -1006;
873
874 if (MatchHistoryOffset > HistoryBufferSize)
875 return -1007;
876
877 OutputLength = MatchOutputOffset - OutputOffset;
878
879 if ((MatchOutputOffset - OutputOffset) > HistoryBufferSize)
880 return -1008;
881
882 if (OutputLength > 0)
883 {
884 if ((&HistoryPtr[OutputLength] >= HistoryBufferEnd) || (Literals >= pSrcEnd) ||
885 (&Literals[OutputLength] > pSrcEnd))
886 return -1009;
887
888 xcrush_copy_bytes(HistoryPtr, Literals, OutputLength);
889 HistoryPtr += OutputLength;
890 Literals += OutputLength;
891 OutputOffset += OutputLength;
892
893 if (Literals > pSrcEnd)
894 return -1010;
895 }
896
897 OutputPtr = &xcrush->HistoryBuffer[MatchHistoryOffset];
898
899 if ((&HistoryPtr[MatchLength] >= HistoryBufferEnd) ||
900 (&OutputPtr[MatchLength] >= HistoryBufferEnd))
901 return -1011;
902
903 xcrush_copy_bytes(HistoryPtr, OutputPtr, MatchLength);
904 OutputOffset += MatchLength;
905 HistoryPtr += MatchLength;
906 }
907 }
908
909 if (Literals < pSrcEnd)
910 {
911 OutputLength = WINPR_ASSERTING_INT_CAST(size_t, pSrcEnd - Literals);
912
913 if ((&HistoryPtr[OutputLength] >= HistoryBufferEnd) || (&Literals[OutputLength] > pSrcEnd))
914 return -1012;
915
916 xcrush_copy_bytes(HistoryPtr, Literals, OutputLength);
917 HistoryPtr += OutputLength;
918 }
919
920 const intptr_t diff = HistoryPtr - HistoryBuffer;
921 if ((diff < 0) || (diff > UINT32_MAX))
922 return -1;
923 xcrush->HistoryOffset = (UINT32)diff;
924
925 const intptr_t sizediff = HistoryPtr - xcrush->HistoryPtr;
926 if ((sizediff < 0) || (sizediff > UINT32_MAX))
927 return -1;
928 *pDstSize = (UINT32)sizediff;
929 *ppDstData = xcrush->HistoryPtr;
930 return 1;
931}
932
933int xcrush_decompress(XCRUSH_CONTEXT* WINPR_RESTRICT xcrush, const BYTE* WINPR_RESTRICT pSrcData,
934 UINT32 SrcSize, const BYTE** WINPR_RESTRICT ppDstData,
935 UINT32* WINPR_RESTRICT pDstSize, UINT32 flags)
936{
937 int status = 0;
938 UINT32 DstSize = 0;
939 const BYTE* pDstData = NULL;
940 BYTE Level1ComprFlags = 0;
941 BYTE Level2ComprFlags = 0;
942
943 WINPR_ASSERT(xcrush);
944
945 if (SrcSize < 2)
946 return -1;
947
948 WINPR_ASSERT(pSrcData);
949 WINPR_ASSERT(ppDstData);
950 WINPR_ASSERT(pDstSize);
951
952 Level1ComprFlags = pSrcData[0];
953 Level2ComprFlags = pSrcData[1];
954 pSrcData += 2;
955 SrcSize -= 2;
956
957 if (flags & PACKET_FLUSHED)
958 {
959 ZeroMemory(xcrush->HistoryBuffer, xcrush->HistoryBufferSize);
960 xcrush->HistoryOffset = 0;
961 }
962
963 if (!(Level2ComprFlags & PACKET_COMPRESSED))
964 {
965 status =
966 xcrush_decompress_l1(xcrush, pSrcData, SrcSize, ppDstData, pDstSize, Level1ComprFlags);
967 return status;
968 }
969
970 status =
971 mppc_decompress(xcrush->mppc, pSrcData, SrcSize, &pDstData, &DstSize, Level2ComprFlags);
972
973 if (status < 0)
974 return status;
975
976 status = xcrush_decompress_l1(xcrush, pDstData, DstSize, ppDstData, pDstSize, Level1ComprFlags);
977 return status;
978}
979
980static int xcrush_compress_l1(XCRUSH_CONTEXT* WINPR_RESTRICT xcrush,
981 const BYTE* WINPR_RESTRICT pSrcData, UINT32 SrcSize,
982 BYTE* WINPR_RESTRICT pDstData, UINT32* WINPR_RESTRICT pDstSize,
983 UINT32* WINPR_RESTRICT pFlags)
984{
985 int status = 0;
986 UINT32 Flags = 0;
987 UINT32 HistoryOffset = 0;
988 BYTE* HistoryPtr = NULL;
989 BYTE* HistoryBuffer = NULL;
990 UINT32 SignatureIndex = 0;
991
992 WINPR_ASSERT(xcrush);
993 WINPR_ASSERT(pSrcData);
994 WINPR_ASSERT(SrcSize > 0);
995 WINPR_ASSERT(pDstData);
996 WINPR_ASSERT(pDstSize);
997 WINPR_ASSERT(pFlags);
998
999 if (xcrush->HistoryOffset + SrcSize + 8 > xcrush->HistoryBufferSize)
1000 {
1001 xcrush->HistoryOffset = 0;
1002 Flags |= L1_PACKET_AT_FRONT;
1003 }
1004
1005 HistoryOffset = xcrush->HistoryOffset;
1006 HistoryBuffer = xcrush->HistoryBuffer;
1007 HistoryPtr = &HistoryBuffer[HistoryOffset];
1008 MoveMemory(HistoryPtr, pSrcData, SrcSize);
1009 xcrush->HistoryOffset += SrcSize;
1010
1011 if (SrcSize > 50)
1012 {
1013 SignatureIndex = xcrush_compute_signatures(xcrush, pSrcData, SrcSize);
1014
1015 if (SignatureIndex)
1016 {
1017 status = xcrush_find_all_matches(xcrush, SignatureIndex, HistoryOffset, 0, SrcSize);
1018
1019 if (status < 0)
1020 return status;
1021
1022 xcrush->OriginalMatchCount = (UINT32)status;
1023 xcrush->OptimizedMatchCount = 0;
1024
1025 if (xcrush->OriginalMatchCount)
1026 {
1027 status = xcrush_optimize_matches(xcrush);
1028
1029 if (status < 0)
1030 return status;
1031 }
1032
1033 if (xcrush->OptimizedMatchCount)
1034 {
1035 status = xcrush_generate_output(xcrush, pDstData, SrcSize, HistoryOffset, pDstSize);
1036
1037 if (status < 0)
1038 return status;
1039
1040 Flags |= L1_COMPRESSED;
1041 }
1042 }
1043 }
1044
1045 if (!(Flags & L1_COMPRESSED))
1046 {
1047 Flags |= L1_NO_COMPRESSION;
1048 *pDstSize = SrcSize;
1049 }
1050
1051 *pFlags = Flags;
1052 return 1;
1053}
1054
1055int xcrush_compress(XCRUSH_CONTEXT* WINPR_RESTRICT xcrush, const BYTE* WINPR_RESTRICT pSrcData,
1056 UINT32 SrcSize, BYTE* WINPR_RESTRICT pDstBuffer,
1057 const BYTE** WINPR_RESTRICT ppDstData, UINT32* WINPR_RESTRICT pDstSize,
1058 UINT32* WINPR_RESTRICT pFlags)
1059{
1060 int status = 0;
1061 UINT32 DstSize = 0;
1062 BYTE* pDstData = NULL;
1063 const BYTE* CompressedData = NULL;
1064 UINT32 CompressedDataSize = 0;
1065 BYTE* OriginalData = NULL;
1066 UINT32 OriginalDataSize = 0;
1067 UINT32 Level1ComprFlags = 0;
1068 UINT32 Level2ComprFlags = 0;
1069 UINT32 CompressionLevel = 3;
1070
1071 WINPR_ASSERT(xcrush);
1072 WINPR_ASSERT(pSrcData);
1073 WINPR_ASSERT(SrcSize > 0);
1074 WINPR_ASSERT(ppDstData);
1075 WINPR_ASSERT(pDstSize);
1076 WINPR_ASSERT(pFlags);
1077
1078 if (SrcSize > 16384)
1079 return -1001;
1080
1081 if ((SrcSize + 2) > *pDstSize)
1082 return -1002;
1083
1084 OriginalData = pDstBuffer;
1085 *ppDstData = pDstBuffer;
1086 OriginalDataSize = SrcSize;
1087 pDstData = xcrush->BlockBuffer;
1088 CompressedDataSize = SrcSize;
1089 status = xcrush_compress_l1(xcrush, pSrcData, SrcSize, pDstData, &CompressedDataSize,
1090 &Level1ComprFlags);
1091
1092 if (status < 0)
1093 return status;
1094
1095 if (Level1ComprFlags & L1_COMPRESSED)
1096 {
1097 CompressedData = pDstData;
1098
1099 if (CompressedDataSize > SrcSize)
1100 return -1003;
1101 }
1102 else
1103 {
1104 CompressedData = pSrcData;
1105
1106 if (CompressedDataSize != SrcSize)
1107 return -1004;
1108 }
1109
1110 status = 0;
1111 pDstData = &OriginalData[2];
1112 DstSize = OriginalDataSize - 2;
1113
1114 if (CompressedDataSize > 50)
1115 {
1116 const BYTE* pUnusedDstData = NULL;
1117 status = mppc_compress(xcrush->mppc, CompressedData, CompressedDataSize, pDstData,
1118 &pUnusedDstData, &DstSize, &Level2ComprFlags);
1119 }
1120
1121 if (status < 0)
1122 return status;
1123
1124 if (!status || (Level2ComprFlags & PACKET_FLUSHED))
1125 {
1126 if (CompressedDataSize > DstSize)
1127 {
1128 xcrush_context_reset(xcrush, TRUE);
1129 *ppDstData = pSrcData;
1130 *pDstSize = SrcSize;
1131 *pFlags = 0;
1132 return 1;
1133 }
1134
1135 DstSize = CompressedDataSize;
1136 CopyMemory(&OriginalData[2], CompressedData, CompressedDataSize);
1137 }
1138
1139 if (Level2ComprFlags & PACKET_COMPRESSED)
1140 {
1141 Level2ComprFlags |= xcrush->CompressionFlags;
1142 xcrush->CompressionFlags = 0;
1143 }
1144 else if (Level2ComprFlags & PACKET_FLUSHED)
1145 {
1146 xcrush->CompressionFlags = PACKET_FLUSHED;
1147 }
1148
1149 Level1ComprFlags |= L1_INNER_COMPRESSION;
1150 OriginalData[0] = (BYTE)Level1ComprFlags;
1151 OriginalData[1] = (BYTE)Level2ComprFlags;
1152#if defined(DEBUG_XCRUSH)
1153 WLog_DBG(TAG, "XCrushCompress: Level1ComprFlags: %s Level2ComprFlags: %s",
1154 xcrush_get_level_1_compression_flags_string(Level1ComprFlags),
1155 xcrush_get_level_2_compression_flags_string(Level2ComprFlags));
1156#endif
1157
1158 if (*pDstSize < (DstSize + 2))
1159 return -1006;
1160
1161 *pDstSize = DstSize + 2;
1162 *pFlags = PACKET_COMPRESSED | CompressionLevel;
1163 return 1;
1164}
1165
1166void xcrush_context_reset(XCRUSH_CONTEXT* WINPR_RESTRICT xcrush, BOOL flush)
1167{
1168 WINPR_ASSERT(xcrush);
1169
1170 xcrush->SignatureIndex = 0;
1171 xcrush->SignatureCount = 1000;
1172 ZeroMemory(&(xcrush->Signatures), sizeof(XCRUSH_SIGNATURE) * xcrush->SignatureCount);
1173 xcrush->CompressionFlags = 0;
1174 xcrush->ChunkHead = xcrush->ChunkTail = 1;
1175 ZeroMemory(&(xcrush->Chunks), sizeof(xcrush->Chunks));
1176 ZeroMemory(&(xcrush->NextChunks), sizeof(xcrush->NextChunks));
1177 ZeroMemory(&(xcrush->OriginalMatches), sizeof(xcrush->OriginalMatches));
1178 ZeroMemory(&(xcrush->OptimizedMatches), sizeof(xcrush->OptimizedMatches));
1179
1180 if (flush)
1181 xcrush->HistoryOffset = xcrush->HistoryBufferSize + 1;
1182 else
1183 xcrush->HistoryOffset = 0;
1184
1185 mppc_context_reset(xcrush->mppc, flush);
1186}
1187
1188XCRUSH_CONTEXT* xcrush_context_new(BOOL Compressor)
1189{
1190 XCRUSH_CONTEXT* xcrush = (XCRUSH_CONTEXT*)calloc(1, sizeof(XCRUSH_CONTEXT));
1191
1192 if (!xcrush)
1193 goto fail;
1194
1195 xcrush->Compressor = Compressor;
1196 xcrush->mppc = mppc_context_new(1, Compressor);
1197 if (!xcrush->mppc)
1198 goto fail;
1199 xcrush->HistoryBufferSize = 2000000;
1200 xcrush_context_reset(xcrush, FALSE);
1201
1202 return xcrush;
1203fail:
1204 xcrush_context_free(xcrush);
1205
1206 return NULL;
1207}
1208
1209void xcrush_context_free(XCRUSH_CONTEXT* xcrush)
1210{
1211 if (xcrush)
1212 {
1213 mppc_context_free(xcrush->mppc);
1214 free(xcrush);
1215 }
1216}