]> git.proxmox.com Git - mirror_edk2.git/blob - ShellPkg/Library/UefiShellDebug1CommandsLib/Compress.c
projects / mirror_edk2.git / blob
? search:


736d2a35b3ac595de1232f1e533e60ec3d2ff256
[mirror_edk2.git] / ShellPkg / Library / UefiShellDebug1CommandsLib / Compress.c
1 /** @file
2 Main file for compression routine.
3
4 Compression routine. The compression algorithm is a mixture of
5 LZ77 and Huffman coding. LZ77 transforms the source data into a
6 sequence of Original Characters and Pointers to repeated strings.
7 This sequence is further divided into Blocks and Huffman codings
8 are applied to each Block.
9
10 Copyright (c) 2007 - 2016, Intel Corporation. All rights reserved.<BR>
11 This program and the accompanying materials
12 are licensed and made available under the terms and conditions of the BSD License
13 which accompanies this distribution. The full text of the license may be found at
14 http://opensource.org/licenses/bsd-license.php
15
16 THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
17 WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
18
19 **/
20 #include <Uefi.h>
21 #include <Library/MemoryAllocationLib.h>
22 #include <Library/BaseMemoryLib.h>
23 #include <Library/DebugLib.h>
24 #include <Library/ShellLib.h>
25
26 //
27 // Macro Definitions
28 //
29 typedef INT16 NODE;
30 #define UINT8_MAX 0xff
31 #define UINT8_BIT 8
32 #define THRESHOLD 3
33 #define INIT_CRC 0
34 #define WNDBIT 13
35 #define WNDSIZ (1U << WNDBIT)
36 #define MAXMATCH 256
37 #define BLKSIZ (1U << 14) // 16 * 1024U
38 #define PERC_FLAG 0x8000U
39 #define CODE_BIT 16
40 #define NIL 0
41 #define MAX_HASH_VAL (3 * WNDSIZ + (WNDSIZ / 512 + 1) * UINT8_MAX)
42 #define HASH(LoopVar7, LoopVar5) ((LoopVar7) + ((LoopVar5) << (WNDBIT - 9)) + WNDSIZ * 2)
43 #define CRCPOLY 0xA001
44 #define UPDATE_CRC(LoopVar5) mCrc = mCrcTable[(mCrc ^ (LoopVar5)) & 0xFF] ^ (mCrc >> UINT8_BIT)
45
46 //
47 // C: the Char&Len Set; P: the Position Set; T: the exTra Set
48 //
49 #define NC (UINT8_MAX + MAXMATCH + 2 - THRESHOLD)
50 #define CBIT 9
51 #define NP (WNDBIT + 1)
52 #define PBIT 4
53 #define NT (CODE_BIT + 3)
54 #define TBIT 5
55 #if NT > NP
56 #define NPT NT
57 #else
58 #define NPT NP
59 #endif
60 //
61 // Function Prototypes
62 //
63
64 /**
65 Put a dword to output stream
66
67 @param[in] Data The dword to put.
68 **/
69 VOID
70 PutDword(
71 IN UINT32 Data
72 );
73
74 //
75 // Global Variables
76 //
77 STATIC UINT8 *mSrc;
78 STATIC UINT8 *mDst;
79 STATIC UINT8 *mSrcUpperLimit;
80 STATIC UINT8 *mDstUpperLimit;
81
82 STATIC UINT8 *mLevel;
83 STATIC UINT8 *mText;
84 STATIC UINT8 *mChildCount;
85 STATIC UINT8 *mBuf;
86 STATIC UINT8 mCLen[NC];
87 STATIC UINT8 mPTLen[NPT];
88 STATIC UINT8 *mLen;
89 STATIC INT16 mHeap[NC + 1];
90 STATIC INT32 mRemainder;
91 STATIC INT32 mMatchLen;
92 STATIC INT32 mBitCount;
93 STATIC INT32 mHeapSize;
94 STATIC INT32 mTempInt32;
95 STATIC UINT32 mBufSiz = 0;
96 STATIC UINT32 mOutputPos;
97 STATIC UINT32 mOutputMask;
98 STATIC UINT32 mSubBitBuf;
99 STATIC UINT32 mCrc;
100 STATIC UINT32 mCompSize;
101 STATIC UINT32 mOrigSize;
102
103 STATIC UINT16 *mFreq;
104 STATIC UINT16 *mSortPtr;
105 STATIC UINT16 mLenCnt[17];
106 STATIC UINT16 mLeft[2 * NC - 1];
107 STATIC UINT16 mRight[2 * NC - 1];
108 STATIC UINT16 mCrcTable[UINT8_MAX + 1];
109 STATIC UINT16 mCFreq[2 * NC - 1];
110 STATIC UINT16 mCCode[NC];
111 STATIC UINT16 mPFreq[2 * NP - 1];
112 STATIC UINT16 mPTCode[NPT];
113 STATIC UINT16 mTFreq[2 * NT - 1];
114
115 STATIC NODE mPos;
116 STATIC NODE mMatchPos;
117 STATIC NODE mAvail;
118 STATIC NODE *mPosition;
119 STATIC NODE *mParent;
120 STATIC NODE *mPrev;
121 STATIC NODE *mNext = NULL;
122 INT32 mHuffmanDepth = 0;
123
124 /**
125 Make a CRC table.
126
127 **/
128 VOID
129 MakeCrcTable (
130 VOID
131 )
132 {
133 UINT32 LoopVar1;
134
135 UINT32 LoopVar2;
136
137 UINT32 LoopVar4;
138
139 for (LoopVar1 = 0; LoopVar1 <= UINT8_MAX; LoopVar1++) {
140 LoopVar4 = LoopVar1;
141 for (LoopVar2 = 0; LoopVar2 < UINT8_BIT; LoopVar2++) {
142 if ((LoopVar4 & 1) != 0) {
143 LoopVar4 = (LoopVar4 >> 1) ^ CRCPOLY;
144 } else {
145 LoopVar4 >>= 1;
146 }
147 }
148
149 mCrcTable[LoopVar1] = (UINT16) LoopVar4;
150 }
151 }
152
153 /**
154 Put a dword to output stream
155
156 @param[in] Data The dword to put.
157 **/
158 VOID
159 PutDword (
160 IN UINT32 Data
161 )
162 {
163 if (mDst < mDstUpperLimit) {
164 *mDst++ = (UINT8) (((UINT8) (Data)) & 0xff);
165 }
166
167 if (mDst < mDstUpperLimit) {
168 *mDst++ = (UINT8) (((UINT8) (Data >> 0x08)) & 0xff);
169 }
170
171 if (mDst < mDstUpperLimit) {
172 *mDst++ = (UINT8) (((UINT8) (Data >> 0x10)) & 0xff);
173 }
174
175 if (mDst < mDstUpperLimit) {
176 *mDst++ = (UINT8) (((UINT8) (Data >> 0x18)) & 0xff);
177 }
178 }
179
180 /**
181 Allocate memory spaces for data structures used in compression process.
182
183 @retval EFI_SUCCESS Memory was allocated successfully.
184 @retval EFI_OUT_OF_RESOURCES A memory allocation failed.
185 **/
186 EFI_STATUS
187 AllocateMemory (
188 VOID
189 )
190 {
191 mText = AllocateZeroPool (WNDSIZ * 2 + MAXMATCH);
192 mLevel = AllocateZeroPool ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mLevel));
193 mChildCount = AllocateZeroPool ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mChildCount));
194 mPosition = AllocateZeroPool ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mPosition));
195 mParent = AllocateZeroPool (WNDSIZ * 2 * sizeof (*mParent));
196 mPrev = AllocateZeroPool (WNDSIZ * 2 * sizeof (*mPrev));
197 mNext = AllocateZeroPool ((MAX_HASH_VAL + 1) * sizeof (*mNext));
198
199 mBufSiz = BLKSIZ;
200 mBuf = AllocateZeroPool (mBufSiz);
201 while (mBuf == NULL) {
202 mBufSiz = (mBufSiz / 10U) * 9U;
203 if (mBufSiz < 4 * 1024U) {
204 return EFI_OUT_OF_RESOURCES;
205 }
206
207 mBuf = AllocateZeroPool (mBufSiz);
208 }
209
210 mBuf[0] = 0;
211
212 return EFI_SUCCESS;
213 }
214
215 /**
216 Called when compression is completed to free memory previously allocated.
217
218 **/
219 VOID
220 FreeMemory (
221 VOID
222 )
223 {
224 SHELL_FREE_NON_NULL (mText);
225 SHELL_FREE_NON_NULL (mLevel);
226 SHELL_FREE_NON_NULL (mChildCount);
227 SHELL_FREE_NON_NULL (mPosition);
228 SHELL_FREE_NON_NULL (mParent);
229 SHELL_FREE_NON_NULL (mPrev);
230 SHELL_FREE_NON_NULL (mNext);
231 SHELL_FREE_NON_NULL (mBuf);
232 }
233
234 /**
235 Initialize String Info Log data structures.
236 **/
237 VOID
238 InitSlide (
239 VOID
240 )
241 {
242 NODE LoopVar1;
243
244 SetMem (mLevel + WNDSIZ, (UINT8_MAX + 1) * sizeof (UINT8), 1);
245 SetMem (mPosition + WNDSIZ, (UINT8_MAX + 1) * sizeof (NODE), 0);
246
247 SetMem (mParent + WNDSIZ, WNDSIZ * sizeof (NODE), 0);
248
249 mAvail = 1;
250 for (LoopVar1 = 1; LoopVar1 < WNDSIZ - 1; LoopVar1++) {
251 mNext[LoopVar1] = (NODE) (LoopVar1 + 1);
252 }
253
254 mNext[WNDSIZ - 1] = NIL;
255 SetMem (mNext + WNDSIZ * 2, (MAX_HASH_VAL - WNDSIZ * 2 + 1) * sizeof (NODE), 0);
256 }
257
258 /**
259 Find child node given the parent node and the edge character
260
261 @param[in] LoopVar6 The parent node.
262 @param[in] LoopVar5 The edge character.
263
264 @return The child node.
265 @retval NIL(Zero) No child could be found.
266
267 **/
268 NODE
269 Child (
270 IN NODE LoopVar6,
271 IN UINT8 LoopVar5
272 )
273 {
274 NODE LoopVar4;
275
276 LoopVar4 = mNext[HASH (LoopVar6, LoopVar5)];
277 mParent[NIL] = LoopVar6; /* sentinel */
278 while (mParent[LoopVar4] != LoopVar6) {
279 LoopVar4 = mNext[LoopVar4];
280 }
281
282 return LoopVar4;
283 }
284
285 /**
286 Create a new child for a given parent node.
287
288 @param[in] LoopVar6 The parent node.
289 @param[in] LoopVar5 The edge character.
290 @param[in] LoopVar4 The child node.
291 **/
292 VOID
293 MakeChild (
294 IN NODE LoopVar6,
295 IN UINT8 LoopVar5,
296 IN NODE LoopVar4
297 )
298 {
299 NODE LoopVar12;
300
301 NODE LoopVar10;
302
303 LoopVar12 = (NODE) HASH (LoopVar6, LoopVar5);
304 LoopVar10 = mNext[LoopVar12];
305 mNext[LoopVar12] = LoopVar4;
306 mNext[LoopVar4] = LoopVar10;
307 mPrev[LoopVar10] = LoopVar4;
308 mPrev[LoopVar4] = LoopVar12;
309 mParent[LoopVar4] = LoopVar6;
310 mChildCount[LoopVar6]++;
311 }
312
313 /**
314 Split a node.
315
316 @param[in] Old The node to split.
317 **/
318 VOID
319 Split (
320 IN NODE Old
321 )
322 {
323 NODE New;
324
325 NODE LoopVar10;
326
327 New = mAvail;
328 mAvail = mNext[New];
329 mChildCount[New] = 0;
330 LoopVar10 = mPrev[Old];
331 mPrev[New] = LoopVar10;
332 mNext[LoopVar10] = New;
333 LoopVar10 = mNext[Old];
334 mNext[New] = LoopVar10;
335 mPrev[LoopVar10] = New;
336 mParent[New] = mParent[Old];
337 mLevel[New] = (UINT8) mMatchLen;
338 mPosition[New] = mPos;
339 MakeChild (New, mText[mMatchPos + mMatchLen], Old);
340 MakeChild (New, mText[mPos + mMatchLen], mPos);
341 }
342
343 /**
344 Insert string info for current position into the String Info Log.
345
346 **/
347 VOID
348 InsertNode (
349 VOID
350 )
351 {
352 NODE LoopVar6;
353
354 NODE LoopVar4;
355
356 NODE LoopVar2;
357
358 NODE LoopVar10;
359 UINT8 LoopVar5;
360 UINT8 *TempString3;
361 UINT8 *TempString2;
362
363 if (mMatchLen >= 4) {
364 //
365 // We have just got a long match, the target tree
366 // can be located by MatchPos + 1. Travese the tree
367 // from bottom up to get to a proper starting point.
368 // The usage of PERC_FLAG ensures proper node deletion
369 // in DeleteNode() later.
370 //
371 mMatchLen--;
372 LoopVar4 = (NODE) ((mMatchPos + 1) | WNDSIZ);
373 LoopVar6 = mParent[LoopVar4];
374 while (LoopVar6 == NIL) {
375 LoopVar4 = mNext[LoopVar4];
376 LoopVar6 = mParent[LoopVar4];
377 }
378
379 while (mLevel[LoopVar6] >= mMatchLen) {
380 LoopVar4 = LoopVar6;
381 LoopVar6 = mParent[LoopVar6];
382 }
383
384 LoopVar10 = LoopVar6;
385 while (mPosition[LoopVar10] < 0) {
386 mPosition[LoopVar10] = mPos;
387 LoopVar10 = mParent[LoopVar10];
388 }
389
390 if (LoopVar10 < WNDSIZ) {
391 mPosition[LoopVar10] = (NODE) (mPos | PERC_FLAG);
392 }
393 } else {
394 //
395 // Locate the target tree
396 //
397 LoopVar6 = (NODE) (mText[mPos] + WNDSIZ);
398 LoopVar5 = mText[mPos + 1];
399 LoopVar4 = Child (LoopVar6, LoopVar5);
400 if (LoopVar4 == NIL) {
401 MakeChild (LoopVar6, LoopVar5, mPos);
402 mMatchLen = 1;
403 return ;
404 }
405
406 mMatchLen = 2;
407 }
408 //
409 // Traverse down the tree to find a match.
410 // Update Position value along the route.
411 // Node split or creation is involved.
412 //
413 for (;;) {
414 if (LoopVar4 >= WNDSIZ) {
415 LoopVar2 = MAXMATCH;
416 mMatchPos = LoopVar4;
417 } else {
418 LoopVar2 = mLevel[LoopVar4];
419 mMatchPos = (NODE) (mPosition[LoopVar4] & ~PERC_FLAG);
420 }
421
422 if (mMatchPos >= mPos) {
423 mMatchPos -= WNDSIZ;
424 }
425
426 TempString3 = &mText[mPos + mMatchLen];
427 TempString2 = &mText[mMatchPos + mMatchLen];
428 while (mMatchLen < LoopVar2) {
429 if (*TempString3 != *TempString2) {
430 Split (LoopVar4);
431 return ;
432 }
433
434 mMatchLen++;
435 TempString3++;
436 TempString2++;
437 }
438
439 if (mMatchLen >= MAXMATCH) {
440 break;
441 }
442
443 mPosition[LoopVar4] = mPos;
444 LoopVar6 = LoopVar4;
445 LoopVar4 = Child (LoopVar6, *TempString3);
446 if (LoopVar4 == NIL) {
447 MakeChild (LoopVar6, *TempString3, mPos);
448 return ;
449 }
450
451 mMatchLen++;
452 }
453
454 LoopVar10 = mPrev[LoopVar4];
455 mPrev[mPos] = LoopVar10;
456 mNext[LoopVar10] = mPos;
457 LoopVar10 = mNext[LoopVar4];
458 mNext[mPos] = LoopVar10;
459 mPrev[LoopVar10] = mPos;
460 mParent[mPos] = LoopVar6;
461 mParent[LoopVar4] = NIL;
462
463 //
464 // Special usage of 'next'
465 //
466 mNext[LoopVar4] = mPos;
467
468 }
469
470 /**
471 Delete outdated string info. (The Usage of PERC_FLAG
472 ensures a clean deletion).
473
474 **/
475 VOID
476 DeleteNode (
477 VOID
478 )
479 {
480 NODE LoopVar6;
481
482 NODE LoopVar4;
483
484 NODE LoopVar11;
485
486 NODE LoopVar10;
487
488 NODE LoopVar9;
489
490 if (mParent[mPos] == NIL) {
491 return ;
492 }
493
494 LoopVar4 = mPrev[mPos];
495 LoopVar11 = mNext[mPos];
496 mNext[LoopVar4] = LoopVar11;
497 mPrev[LoopVar11] = LoopVar4;
498 LoopVar4 = mParent[mPos];
499 mParent[mPos] = NIL;
500 if (LoopVar4 >= WNDSIZ) {
501 return ;
502 }
503
504 mChildCount[LoopVar4]--;
505 if (mChildCount[LoopVar4] > 1) {
506 return ;
507 }
508
509 LoopVar10 = (NODE) (mPosition[LoopVar4] & ~PERC_FLAG);
510 if (LoopVar10 >= mPos) {
511 LoopVar10 -= WNDSIZ;
512 }
513
514 LoopVar11 = LoopVar10;
515 LoopVar6 = mParent[LoopVar4];
516 LoopVar9 = mPosition[LoopVar6];
517 while ((LoopVar9 & PERC_FLAG) != 0){
518 LoopVar9 &= ~PERC_FLAG;
519 if (LoopVar9 >= mPos) {
520 LoopVar9 -= WNDSIZ;
521 }
522
523 if (LoopVar9 > LoopVar11) {
524 LoopVar11 = LoopVar9;
525 }
526
527 mPosition[LoopVar6] = (NODE) (LoopVar11 | WNDSIZ);
528 LoopVar6 = mParent[LoopVar6];
529 LoopVar9 = mPosition[LoopVar6];
530 }
531
532 if (LoopVar6 < WNDSIZ) {
533 if (LoopVar9 >= mPos) {
534 LoopVar9 -= WNDSIZ;
535 }
536
537 if (LoopVar9 > LoopVar11) {
538 LoopVar11 = LoopVar9;
539 }
540
541 mPosition[LoopVar6] = (NODE) (LoopVar11 | WNDSIZ | PERC_FLAG);
542 }
543
544 LoopVar11 = Child (LoopVar4, mText[LoopVar10 + mLevel[LoopVar4]]);
545 LoopVar10 = mPrev[LoopVar11];
546 LoopVar9 = mNext[LoopVar11];
547 mNext[LoopVar10] = LoopVar9;
548 mPrev[LoopVar9] = LoopVar10;
549 LoopVar10 = mPrev[LoopVar4];
550 mNext[LoopVar10] = LoopVar11;
551 mPrev[LoopVar11] = LoopVar10;
552 LoopVar10 = mNext[LoopVar4];
553 mPrev[LoopVar10] = LoopVar11;
554 mNext[LoopVar11] = LoopVar10;
555 mParent[LoopVar11] = mParent[LoopVar4];
556 mParent[LoopVar4] = NIL;
557 mNext[LoopVar4] = mAvail;
558 mAvail = LoopVar4;
559 }
560
561 /**
562 Read in source data
563
564 @param[out] LoopVar7 The buffer to hold the data.
565 @param[in] LoopVar8 The number of bytes to read.
566
567 @return The number of bytes actually read.
568 **/
569 INT32
570 FreadCrc (
571 OUT UINT8 *LoopVar7,
572 IN INT32 LoopVar8
573 )
574 {
575 INT32 LoopVar1;
576
577 for (LoopVar1 = 0; mSrc < mSrcUpperLimit && LoopVar1 < LoopVar8; LoopVar1++) {
578 *LoopVar7++ = *mSrc++;
579 }
580
581 LoopVar8 = LoopVar1;
582
583 LoopVar7 -= LoopVar8;
584 mOrigSize += LoopVar8;
585 LoopVar1--;
586 while (LoopVar1 >= 0) {
587 UPDATE_CRC (*LoopVar7++);
588 LoopVar1--;
589 }
590
591 return LoopVar8;
592 }
593
594 /**
595 Advance the current position (read in new data if needed).
596 Delete outdated string info. Find a match string for current position.
597
598 @retval TRUE The operation was successful.
599 @retval FALSE The operation failed due to insufficient memory.
600 **/
601 BOOLEAN
602 GetNextMatch (
603 VOID
604 )
605 {
606 INT32 LoopVar8;
607 VOID *Temp;
608
609 mRemainder--;
610 mPos++;
611 if (mPos == WNDSIZ * 2) {
612 Temp = AllocateZeroPool (WNDSIZ + MAXMATCH);
613 if (Temp == NULL) {
614 return (FALSE);
615 }
616 CopyMem (Temp, &mText[WNDSIZ], WNDSIZ + MAXMATCH);
617 CopyMem (&mText[0], Temp, WNDSIZ + MAXMATCH);
618 FreePool (Temp);
619 LoopVar8 = FreadCrc (&mText[WNDSIZ + MAXMATCH], WNDSIZ);
620 mRemainder += LoopVar8;
621 mPos = WNDSIZ;
622 }
623
624 DeleteNode ();
625 InsertNode ();
626
627 return (TRUE);
628 }
629
630 /**
631 Send entry LoopVar1 down the queue.
632
633 @param[in] LoopVar1 The index of the item to move.
634 **/
635 VOID
636 DownHeap (
637 IN INT32 i
638 )
639 {
640 INT32 LoopVar1;
641
642 INT32 LoopVar2;
643
644 //
645 // priority queue: send i-th entry down heap
646 //
647 LoopVar2 = mHeap[i];
648 LoopVar1 = 2 * i;
649 while (LoopVar1 <= mHeapSize) {
650 if (LoopVar1 < mHeapSize && mFreq[mHeap[LoopVar1]] > mFreq[mHeap[LoopVar1 + 1]]) {
651 LoopVar1++;
652 }
653
654 if (mFreq[LoopVar2] <= mFreq[mHeap[LoopVar1]]) {
655 break;
656 }
657
658 mHeap[i] = mHeap[LoopVar1];
659 i = LoopVar1;
660 LoopVar1 = 2 * i;
661 }
662
663 mHeap[i] = (INT16) LoopVar2;
664 }
665
666 /**
667 Count the number of each code length for a Huffman tree.
668
669 @param[in] LoopVar1 The top node.
670 **/
671 VOID
672 CountLen (
673 IN INT32 LoopVar1
674 )
675 {
676 if (LoopVar1 < mTempInt32) {
677 mLenCnt[(mHuffmanDepth < 16) ? mHuffmanDepth : 16]++;
678 } else {
679 mHuffmanDepth++;
680 CountLen (mLeft[LoopVar1]);
681 CountLen (mRight[LoopVar1]);
682 mHuffmanDepth--;
683 }
684 }
685
686 /**
687 Create code length array for a Huffman tree.
688
689 @param[in] Root The root of the tree.
690 **/
691 VOID
692 MakeLen (
693 IN INT32 Root
694 )
695 {
696 INT32 LoopVar1;
697
698 INT32 LoopVar2;
699 UINT32 Cum;
700
701 for (LoopVar1 = 0; LoopVar1 <= 16; LoopVar1++) {
702 mLenCnt[LoopVar1] = 0;
703 }
704
705 CountLen (Root);
706
707 //
708 // Adjust the length count array so that
709 // no code will be generated longer than its designated length
710 //
711 Cum = 0;
712 for (LoopVar1 = 16; LoopVar1 > 0; LoopVar1--) {
713 Cum += mLenCnt[LoopVar1] << (16 - LoopVar1);
714 }
715
716 while (Cum != (1U << 16)) {
717 mLenCnt[16]--;
718 for (LoopVar1 = 15; LoopVar1 > 0; LoopVar1--) {
719 if (mLenCnt[LoopVar1] != 0) {
720 mLenCnt[LoopVar1]--;
721 mLenCnt[LoopVar1 + 1] += 2;
722 break;
723 }
724 }
725
726 Cum--;
727 }
728
729 for (LoopVar1 = 16; LoopVar1 > 0; LoopVar1--) {
730 LoopVar2 = mLenCnt[LoopVar1];
731 LoopVar2--;
732 while (LoopVar2 >= 0) {
733 mLen[*mSortPtr++] = (UINT8) LoopVar1;
734 LoopVar2--;
735 }
736 }
737 }
738
739 /**
740 Assign code to each symbol based on the code length array.
741
742 @param[in] LoopVar8 The number of symbols.
743 @param[in] Len The code length array.
744 @param[out] Code The stores codes for each symbol.
745 **/
746 VOID
747 MakeCode (
748 IN INT32 LoopVar8,
749 IN UINT8 Len[ ],
750 OUT UINT16 Code[ ]
751 )
752 {
753 INT32 LoopVar1;
754 UINT16 Start[18];
755
756 Start[1] = 0;
757 for (LoopVar1 = 1; LoopVar1 <= 16; LoopVar1++) {
758 Start[LoopVar1 + 1] = (UINT16) ((Start[LoopVar1] + mLenCnt[LoopVar1]) << 1);
759 }
760
761 for (LoopVar1 = 0; LoopVar1 < LoopVar8; LoopVar1++) {
762 Code[LoopVar1] = Start[Len[LoopVar1]]++;
763 }
764 }
765
766 /**
767 Generates Huffman codes given a frequency distribution of symbols.
768
769 @param[in] NParm The number of symbols.
770 @param[in] FreqParm The frequency of each symbol.
771 @param[out] LenParm The code length for each symbol.
772 @param[out] CodeParm The code for each symbol.
773
774 @return The root of the Huffman tree.
775 **/
776 INT32
777 MakeTree (
778 IN INT32 NParm,
779 IN UINT16 FreqParm[ ],
780 OUT UINT8 LenParm[ ],
781 OUT UINT16 CodeParm[ ]
782 )
783 {
784 INT32 LoopVar1;
785
786 INT32 LoopVar2;
787
788 INT32 LoopVar3;
789
790 INT32 Avail;
791
792 //
793 // make tree, calculate len[], return root
794 //
795 mTempInt32 = NParm;
796 mFreq = FreqParm;
797 mLen = LenParm;
798 Avail = mTempInt32;
799 mHeapSize = 0;
800 mHeap[1] = 0;
801 for (LoopVar1 = 0; LoopVar1 < mTempInt32; LoopVar1++) {
802 mLen[LoopVar1] = 0;
803 if ((mFreq[LoopVar1]) != 0) {
804 mHeapSize++;
805 mHeap[mHeapSize] = (INT16) LoopVar1;
806 }
807 }
808
809 if (mHeapSize < 2) {
810 CodeParm[mHeap[1]] = 0;
811 return mHeap[1];
812 }
813
814 for (LoopVar1 = mHeapSize / 2; LoopVar1 >= 1; LoopVar1--) {
815 //
816 // make priority queue
817 //
818 DownHeap (LoopVar1);
819 }
820
821 mSortPtr = CodeParm;
822 do {
823 LoopVar1 = mHeap[1];
824 if (LoopVar1 < mTempInt32) {
825 *mSortPtr++ = (UINT16) LoopVar1;
826 }
827
828 mHeap[1] = mHeap[mHeapSize--];
829 DownHeap (1);
830 LoopVar2 = mHeap[1];
831 if (LoopVar2 < mTempInt32) {
832 *mSortPtr++ = (UINT16) LoopVar2;
833 }
834
835 LoopVar3 = Avail++;
836 mFreq[LoopVar3] = (UINT16) (mFreq[LoopVar1] + mFreq[LoopVar2]);
837 mHeap[1] = (INT16) LoopVar3;
838 DownHeap (1);
839 mLeft[LoopVar3] = (UINT16) LoopVar1;
840 mRight[LoopVar3] = (UINT16) LoopVar2;
841 } while (mHeapSize > 1);
842
843 mSortPtr = CodeParm;
844 MakeLen (LoopVar3);
845 MakeCode (NParm, LenParm, CodeParm);
846
847 //
848 // return root
849 //
850 return LoopVar3;
851 }
852
853 /**
854 Outputs rightmost LoopVar8 bits of x
855
856 @param[in] LoopVar8 The rightmost LoopVar8 bits of the data is used.
857 @param[in] x The data.
858 **/
859 VOID
860 PutBits (
861 IN INT32 LoopVar8,
862 IN UINT32 x
863 )
864 {
865 UINT8 Temp;
866
867 if (LoopVar8 < mBitCount) {
868 mSubBitBuf |= x << (mBitCount -= LoopVar8);
869 } else {
870
871 Temp = (UINT8)(mSubBitBuf | (x >> (LoopVar8 -= mBitCount)));
872 if (mDst < mDstUpperLimit) {
873 *mDst++ = Temp;
874 }
875 mCompSize++;
876
877 if (LoopVar8 < UINT8_BIT) {
878 mSubBitBuf = x << (mBitCount = UINT8_BIT - LoopVar8);
879 } else {
880
881 Temp = (UINT8)(x >> (LoopVar8 - UINT8_BIT));
882 if (mDst < mDstUpperLimit) {
883 *mDst++ = Temp;
884 }
885 mCompSize++;
886
887 mSubBitBuf = x << (mBitCount = 2 * UINT8_BIT - LoopVar8);
888 }
889 }
890 }
891
892 /**
893 Encode a signed 32 bit number.
894
895 @param[in] LoopVar5 The number to encode.
896 **/
897 VOID
898 EncodeC (
899 IN INT32 LoopVar5
900 )
901 {
902 PutBits (mCLen[LoopVar5], mCCode[LoopVar5]);
903 }
904
905 /**
906 Encode a unsigned 32 bit number.
907
908 @param[in] LoopVar7 The number to encode.
909 **/
910 VOID
911 EncodeP (
912 IN UINT32 LoopVar7
913 )
914 {
915 UINT32 LoopVar5;
916
917 UINT32 LoopVar6;
918
919 LoopVar5 = 0;
920 LoopVar6 = LoopVar7;
921 while (LoopVar6 != 0) {
922 LoopVar6 >>= 1;
923 LoopVar5++;
924 }
925
926 PutBits (mPTLen[LoopVar5], mPTCode[LoopVar5]);
927 if (LoopVar5 > 1) {
928 PutBits(LoopVar5 - 1, LoopVar7 & (0xFFFFU >> (17 - LoopVar5)));
929 }
930 }
931
932 /**
933 Count the frequencies for the Extra Set.
934
935 **/
936 VOID
937 CountTFreq (
938 VOID
939 )
940 {
941 INT32 LoopVar1;
942
943 INT32 LoopVar3;
944
945 INT32 LoopVar8;
946
947 INT32 Count;
948
949 for (LoopVar1 = 0; LoopVar1 < NT; LoopVar1++) {
950 mTFreq[LoopVar1] = 0;
951 }
952
953 LoopVar8 = NC;
954 while (LoopVar8 > 0 && mCLen[LoopVar8 - 1] == 0) {
955 LoopVar8--;
956 }
957
958 LoopVar1 = 0;
959 while (LoopVar1 < LoopVar8) {
960 LoopVar3 = mCLen[LoopVar1++];
961 if (LoopVar3 == 0) {
962 Count = 1;
963 while (LoopVar1 < LoopVar8 && mCLen[LoopVar1] == 0) {
964 LoopVar1++;
965 Count++;
966 }
967
968 if (Count <= 2) {
969 mTFreq[0] = (UINT16) (mTFreq[0] + Count);
970 } else if (Count <= 18) {
971 mTFreq[1]++;
972 } else if (Count == 19) {
973 mTFreq[0]++;
974 mTFreq[1]++;
975 } else {
976 mTFreq[2]++;
977 }
978 } else {
979 ASSERT((LoopVar3+2)<(2 * NT - 1));
980 mTFreq[LoopVar3 + 2]++;
981 }
982 }
983 }
984
985 /**
986 Outputs the code length array for the Extra Set or the Position Set.
987
988 @param[in] LoopVar8 The number of symbols.
989 @param[in] nbit The number of bits needed to represent 'LoopVar8'.
990 @param[in] Special The special symbol that needs to be take care of.
991
992 **/
993 VOID
994 WritePTLen (
995 IN INT32 LoopVar8,
996 IN INT32 nbit,
997 IN INT32 Special
998 )
999 {
1000 INT32 LoopVar1;
1001
1002 INT32 LoopVar3;
1003
1004 while (LoopVar8 > 0 && mPTLen[LoopVar8 - 1] == 0) {
1005 LoopVar8--;
1006 }
1007
1008 PutBits (nbit, LoopVar8);
1009 LoopVar1 = 0;
1010 while (LoopVar1 < LoopVar8) {
1011 LoopVar3 = mPTLen[LoopVar1++];
1012 if (LoopVar3 <= 6) {
1013 PutBits (3, LoopVar3);
1014 } else {
1015 PutBits (LoopVar3 - 3, (1U << (LoopVar3 - 3)) - 2);
1016 }
1017
1018 if (LoopVar1 == Special) {
1019 while (LoopVar1 < 6 && mPTLen[LoopVar1] == 0) {
1020 LoopVar1++;
1021 }
1022
1023 PutBits (2, (LoopVar1 - 3) & 3);
1024 }
1025 }
1026 }
1027
1028 /**
1029 Outputs the code length array for Char&Length Set.
1030 **/
1031 VOID
1032 WriteCLen (
1033 VOID
1034 )
1035 {
1036 INT32 LoopVar1;
1037
1038 INT32 LoopVar3;
1039
1040 INT32 LoopVar8;
1041
1042 INT32 Count;
1043
1044 LoopVar8 = NC;
1045 while (LoopVar8 > 0 && mCLen[LoopVar8 - 1] == 0) {
1046 LoopVar8--;
1047 }
1048
1049 PutBits (CBIT, LoopVar8);
1050 LoopVar1 = 0;
1051 while (LoopVar1 < LoopVar8) {
1052 LoopVar3 = mCLen[LoopVar1++];
1053 if (LoopVar3 == 0) {
1054 Count = 1;
1055 while (LoopVar1 < LoopVar8 && mCLen[LoopVar1] == 0) {
1056 LoopVar1++;
1057 Count++;
1058 }
1059
1060 if (Count <= 2) {
1061 for (LoopVar3 = 0; LoopVar3 < Count; LoopVar3++) {
1062 PutBits (mPTLen[0], mPTCode[0]);
1063 }
1064 } else if (Count <= 18) {
1065 PutBits (mPTLen[1], mPTCode[1]);
1066 PutBits (4, Count - 3);
1067 } else if (Count == 19) {
1068 PutBits (mPTLen[0], mPTCode[0]);
1069 PutBits (mPTLen[1], mPTCode[1]);
1070 PutBits (4, 15);
1071 } else {
1072 PutBits (mPTLen[2], mPTCode[2]);
1073 PutBits (CBIT, Count - 20);
1074 }
1075 } else {
1076 ASSERT((LoopVar3+2)<NPT);
1077 PutBits (mPTLen[LoopVar3 + 2], mPTCode[LoopVar3 + 2]);
1078 }
1079 }
1080 }
1081
1082 /**
1083 Huffman code the block and output it.
1084
1085 **/
1086 VOID
1087 SendBlock (
1088 VOID
1089 )
1090 {
1091 UINT32 LoopVar1;
1092
1093 UINT32 LoopVar3;
1094
1095 UINT32 Flags;
1096
1097 UINT32 Root;
1098
1099 UINT32 Pos;
1100
1101 UINT32 Size;
1102 Flags = 0;
1103
1104 Root = MakeTree (NC, mCFreq, mCLen, mCCode);
1105 Size = mCFreq[Root];
1106 PutBits (16, Size);
1107 if (Root >= NC) {
1108 CountTFreq ();
1109 Root = MakeTree (NT, mTFreq, mPTLen, mPTCode);
1110 if (Root >= NT) {
1111 WritePTLen (NT, TBIT, 3);
1112 } else {
1113 PutBits (TBIT, 0);
1114 PutBits (TBIT, Root);
1115 }
1116
1117 WriteCLen ();
1118 } else {
1119 PutBits (TBIT, 0);
1120 PutBits (TBIT, 0);
1121 PutBits (CBIT, 0);
1122 PutBits (CBIT, Root);
1123 }
1124
1125 Root = MakeTree (NP, mPFreq, mPTLen, mPTCode);
1126 if (Root >= NP) {
1127 WritePTLen (NP, PBIT, -1);
1128 } else {
1129 PutBits (PBIT, 0);
1130 PutBits (PBIT, Root);
1131 }
1132
1133 Pos = 0;
1134 for (LoopVar1 = 0; LoopVar1 < Size; LoopVar1++) {
1135 if (LoopVar1 % UINT8_BIT == 0) {
1136 Flags = mBuf[Pos++];
1137 } else {
1138 Flags <<= 1;
1139 }
1140 if ((Flags & (1U << (UINT8_BIT - 1))) != 0){
1141 EncodeC(mBuf[Pos++] + (1U << UINT8_BIT));
1142 LoopVar3 = mBuf[Pos++] << UINT8_BIT;
1143 LoopVar3 += mBuf[Pos++];
1144
1145 EncodeP (LoopVar3);
1146 } else {
1147 EncodeC (mBuf[Pos++]);
1148 }
1149 }
1150
1151 SetMem (mCFreq, NC * sizeof (UINT16), 0);
1152 SetMem (mPFreq, NP * sizeof (UINT16), 0);
1153 }
1154
1155 /**
1156 Start the huffman encoding.
1157
1158 **/
1159 VOID
1160 HufEncodeStart (
1161 VOID
1162 )
1163 {
1164 SetMem (mCFreq, NC * sizeof (UINT16), 0);
1165 SetMem (mPFreq, NP * sizeof (UINT16), 0);
1166
1167 mOutputPos = mOutputMask = 0;
1168
1169 mBitCount = UINT8_BIT;
1170 mSubBitBuf = 0;
1171 }
1172
1173 /**
1174 Outputs an Original Character or a Pointer.
1175
1176 @param[in] LoopVar5 The original character or the 'String Length' element of
1177 a Pointer.
1178 @param[in] LoopVar7 The 'Position' field of a Pointer.
1179 **/
1180 VOID
1181 CompressOutput (
1182 IN UINT32 LoopVar5,
1183 IN UINT32 LoopVar7
1184 )
1185 {
1186 STATIC UINT32 CPos;
1187
1188 if ((mOutputMask >>= 1) == 0) {
1189 mOutputMask = 1U << (UINT8_BIT - 1);
1190 if (mOutputPos >= mBufSiz - 3 * UINT8_BIT) {
1191 SendBlock ();
1192 mOutputPos = 0;
1193 }
1194
1195 CPos = mOutputPos++;
1196 mBuf[CPos] = 0;
1197 }
1198 mBuf[mOutputPos++] = (UINT8) LoopVar5;
1199 mCFreq[LoopVar5]++;
1200 if (LoopVar5 >= (1U << UINT8_BIT)) {
1201 mBuf[CPos] = (UINT8)(mBuf[CPos]|mOutputMask);
1202 mBuf[mOutputPos++] = (UINT8)(LoopVar7 >> UINT8_BIT);
1203 mBuf[mOutputPos++] = (UINT8) LoopVar7;
1204 LoopVar5 = 0;
1205 while (LoopVar7!=0) {
1206 LoopVar7 >>= 1;
1207 LoopVar5++;
1208 }
1209 mPFreq[LoopVar5]++;
1210 }
1211 }
1212
1213 /**
1214 End the huffman encoding.
1215
1216 **/
1217 VOID
1218 HufEncodeEnd (
1219 VOID
1220 )
1221 {
1222 SendBlock ();
1223
1224 //
1225 // Flush remaining bits
1226 //
1227 PutBits (UINT8_BIT - 1, 0);
1228 }
1229
1230 /**
1231 The main controlling routine for compression process.
1232
1233 @retval EFI_SUCCESS The compression is successful.
1234 @retval EFI_OUT_0F_RESOURCES Not enough memory for compression process.
1235 **/
1236 EFI_STATUS
1237 Encode (
1238 VOID
1239 )
1240 {
1241 EFI_STATUS Status;
1242 INT32 LastMatchLen;
1243 NODE LastMatchPos;
1244
1245 Status = AllocateMemory ();
1246 if (EFI_ERROR (Status)) {
1247 FreeMemory ();
1248 return Status;
1249 }
1250
1251 InitSlide ();
1252
1253 HufEncodeStart ();
1254
1255 mRemainder = FreadCrc (&mText[WNDSIZ], WNDSIZ + MAXMATCH);
1256
1257 mMatchLen = 0;
1258 mPos = WNDSIZ;
1259 InsertNode ();
1260 if (mMatchLen > mRemainder) {
1261 mMatchLen = mRemainder;
1262 }
1263
1264 while (mRemainder > 0) {
1265 LastMatchLen = mMatchLen;
1266 LastMatchPos = mMatchPos;
1267 if (!GetNextMatch ()) {
1268 Status = EFI_OUT_OF_RESOURCES;
1269 }
1270 if (mMatchLen > mRemainder) {
1271 mMatchLen = mRemainder;
1272 }
1273
1274 if (mMatchLen > LastMatchLen || LastMatchLen < THRESHOLD) {
1275 //
1276 // Not enough benefits are gained by outputting a pointer,
1277 // so just output the original character
1278 //
1279 CompressOutput(mText[mPos - 1], 0);
1280 } else {
1281 //
1282 // Outputting a pointer is beneficial enough, do it.
1283 //
1284
1285 CompressOutput(LastMatchLen + (UINT8_MAX + 1 - THRESHOLD),
1286 (mPos - LastMatchPos - 2) & (WNDSIZ - 1));
1287 LastMatchLen--;
1288 while (LastMatchLen > 0) {
1289 if (!GetNextMatch ()) {
1290 Status = EFI_OUT_OF_RESOURCES;
1291 }
1292 LastMatchLen--;
1293 }
1294
1295 if (mMatchLen > mRemainder) {
1296 mMatchLen = mRemainder;
1297 }
1298 }
1299 }
1300
1301 HufEncodeEnd ();
1302 FreeMemory ();
1303 return (Status);
1304 }
1305
1306 /**
1307 The compression routine.
1308
1309 @param[in] SrcBuffer The buffer containing the source data.
1310 @param[in] SrcSize The number of bytes in SrcBuffer.
1311 @param[in] DstBuffer The buffer to put the compressed image in.
1312 @param[in, out] DstSize On input the size (in bytes) of DstBuffer, on
1313 return the number of bytes placed in DstBuffer.
1314
1315 @retval EFI_SUCCESS The compression was sucessful.
1316 @retval EFI_BUFFER_TOO_SMALL The buffer was too small. DstSize is required.
1317 **/
1318 EFI_STATUS
1319 Compress (
1320 IN VOID *SrcBuffer,
1321 IN UINT64 SrcSize,
1322 IN VOID *DstBuffer,
1323 IN OUT UINT64 *DstSize
1324 )
1325 {
1326 EFI_STATUS Status;
1327
1328 //
1329 // Initializations
1330 //
1331 mBufSiz = 0;
1332 mBuf = NULL;
1333 mText = NULL;
1334 mLevel = NULL;
1335 mChildCount = NULL;
1336 mPosition = NULL;
1337 mParent = NULL;
1338 mPrev = NULL;
1339 mNext = NULL;
1340
1341 mSrc = SrcBuffer;
1342 mSrcUpperLimit = mSrc + SrcSize;
1343 mDst = DstBuffer;
1344 mDstUpperLimit = mDst +*DstSize;
1345
1346 PutDword (0L);
1347 PutDword (0L);
1348
1349 MakeCrcTable ();
1350
1351 mOrigSize = mCompSize = 0;
1352 mCrc = INIT_CRC;
1353
1354 //
1355 // Compress it
1356 //
1357 Status = Encode ();
1358 if (EFI_ERROR (Status)) {
1359 return EFI_OUT_OF_RESOURCES;
1360 }
1361 //
1362 // Null terminate the compressed data
1363 //
1364 if (mDst < mDstUpperLimit) {
1365 *mDst++ = 0;
1366 }
1367 //
1368 // Fill in compressed size and original size
1369 //
1370 mDst = DstBuffer;
1371 PutDword (mCompSize + 1);
1372 PutDword (mOrigSize);
1373
1374 //
1375 // Return
1376 //
1377 if (mCompSize + 1 + 8 > *DstSize) {
1378 *DstSize = mCompSize + 1 + 8;
1379 return EFI_BUFFER_TOO_SMALL;
1380 } else {
1381 *DstSize = mCompSize + 1 + 8;
1382 return EFI_SUCCESS;
1383 }
1384
1385 }
1386
EFI Development Kit II mirror for PVE