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


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