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