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