1 /** @file
2 Compression routine. The compression algorithm is a mixture of LZ77 and Huffman
3 coding. LZ77 transforms the source data into a sequence of Original Characters
4 and Pointers to repeated strings.
5 This sequence is further divided into Blocks and Huffman codings are applied to
6 each Block.
7
8 Copyright (c) 2007 - 2016, Intel Corporation. All rights reserved.<BR>
9 This program and the accompanying materials
10 are licensed and made available under the terms and conditions of the BSD License
11 which accompanies this distribution. The full text of the license may be found at
12 http://opensource.org/licenses/bsd-license.php
13
14 THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
15 WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
16
17 **/
18
19 #include "Compress.h"
20 #include "TianoCompress.h"
21 #include "EfiUtilityMsgs.h"
22 #include "ParseInf.h"
23 #include <stdio.h>
24 #include "assert.h"
25
26 //
27 // Macro Definitions
28 //
29 static BOOLEAN VerboseMode = FALSE;
30 static BOOLEAN QuietMode = FALSE;
31 #undef UINT8_MAX
32 #define UINT8_MAX 0xff
33 #define UINT8_BIT 8
34 #define THRESHOLD 3
35 #define INIT_CRC 0
36 #define WNDBIT 19
37 #define WNDSIZ (1U << WNDBIT)
38 #define MAXMATCH 256
39 #define BLKSIZ (1U << 14) // 16 * 1024U
40 #define PERC_FLAG 0x80000000U
41 #define CODE_BIT 16
42 #define NIL 0
43 #define MAX_HASH_VAL (3 * WNDSIZ + (WNDSIZ / 512 + 1) * UINT8_MAX)
44 #define HASH(p, c) ((p) + ((c) << (WNDBIT - 9)) + WNDSIZ * 2)
45 #define CRCPOLY 0xA001
46 #define UPDATE_CRC(c) mCrc = mCrcTable[(mCrc ^ (c)) & 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 5
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 //
64 // Global Variables
65 //
66 STATIC BOOLEAN ENCODE = FALSE;
67 STATIC BOOLEAN DECODE = FALSE;
68 STATIC UINT8 *mSrc, *mDst, *mSrcUpperLimit, *mDstUpperLimit;
69 STATIC UINT8 *mLevel, *mText, *mChildCount, *mBuf, mCLen[NC], mPTLen[NPT], *mLen;
70 STATIC INT16 mHeap[NC + 1];
71 STATIC INT32 mRemainder, mMatchLen, mBitCount, mHeapSize, mN;
72 STATIC UINT32 mBufSiz = 0, mOutputPos, mOutputMask, mSubBitBuf, mCrc;
73 STATIC UINT32 mCompSize, mOrigSize;
74
75 STATIC UINT16 *mFreq, *mSortPtr, mLenCnt[17], mLeft[2 * NC - 1], mRight[2 * NC - 1], mCrcTable[UINT8_MAX + 1],
76 mCFreq[2 * NC - 1], mCCode[NC], mPFreq[2 * NP - 1], mPTCode[NPT], mTFreq[2 * NT - 1];
77
78 STATIC NODE mPos, mMatchPos, mAvail, *mPosition, *mParent, *mPrev, *mNext = NULL;
79
80 static UINT64 DebugLevel;
81 static BOOLEAN DebugMode;
82 //
83 // functions
84 //
85 EFI_STATUS
TianoCompress(IN UINT8 * SrcBuffer,IN UINT32 SrcSize,IN UINT8 * DstBuffer,IN OUT UINT32 * DstSize)86 TianoCompress (
87 IN UINT8 *SrcBuffer,
88 IN UINT32 SrcSize,
89 IN UINT8 *DstBuffer,
90 IN OUT UINT32 *DstSize
91 )
92 /*++
93
94 Routine Description:
95
96 The internal implementation of [Efi/Tiano]Compress().
97
98 Arguments:
99
100 SrcBuffer - The buffer storing the source data
101 SrcSize - The size of source data
102 DstBuffer - The buffer to store the compressed data
103
104 Version - The version of de/compression algorithm.
105 Version 1 for EFI 1.1 de/compression algorithm.
106 Version 2 for Tiano de/compression algorithm.
107
108 Returns:
109
110 EFI_BUFFER_TOO_SMALL - The DstBuffer is too small. In this case,
111 DstSize contains the size needed.
112 EFI_SUCCESS - Compression is successful.
113 EFI_OUT_OF_RESOURCES - No resource to complete function.
114 EFI_INVALID_PARAMETER - Parameter supplied is wrong.
115
116 --*/
117 {
118 EFI_STATUS Status;
119
120 //
121 // Initializations
122 //
123 mBufSiz = 0;
124 mBuf = NULL;
125 mText = NULL;
126 mLevel = NULL;
127 mChildCount = NULL;
128 mPosition = NULL;
129 mParent = NULL;
130 mPrev = NULL;
131 mNext = NULL;
132
133
134 mSrc = SrcBuffer;
135 mSrcUpperLimit = mSrc + SrcSize;
136 mDst = DstBuffer;
137 mDstUpperLimit = mDst +*DstSize;
138
139 PutDword (0L);
140 PutDword (0L);
141
142 MakeCrcTable ();
143
144 mOrigSize = mCompSize = 0;
145 mCrc = INIT_CRC;
146
147 //
148 // Compress it
149 //
150 Status = Encode ();
151 if (EFI_ERROR (Status)) {
152 return EFI_OUT_OF_RESOURCES;
153 }
154
155 //
156 // Null terminate the compressed data
157 //
158
159 if (mDst < mDstUpperLimit) {
160 *mDst++ = 0;
161 }
162
163 //
164 // Fill in compressed size and original size
165 //
166 mDst = DstBuffer;
167
168 PutDword (mCompSize + 1);
169 PutDword (mOrigSize);
170 //
171 // Return
172 //
173
174 if (mCompSize + 1 + 8 > *DstSize) {
175 *DstSize = mCompSize + 1 + 8;
176 return EFI_BUFFER_TOO_SMALL;
177 } else {
178 *DstSize = mCompSize + 1 + 8;
179 return EFI_SUCCESS;
180 }
181 }
182
183 STATIC
184 VOID
PutDword(IN UINT32 Data)185 PutDword (
186 IN UINT32 Data
187 )
188 /*++
189
190 Routine Description:
191
192 Put a dword to output stream
193
194 Arguments:
195
196 Data - the dword to put
197
198 Returns: (VOID)
199
200 --*/
201 {
202 if (mDst < mDstUpperLimit) {
203 *mDst++ = (UINT8) (((UINT8) (Data)) & 0xff);
204 }
205
206 if (mDst < mDstUpperLimit) {
207 *mDst++ = (UINT8) (((UINT8) (Data >> 0x08)) & 0xff);
208 }
209
210 if (mDst < mDstUpperLimit) {
211 *mDst++ = (UINT8) (((UINT8) (Data >> 0x10)) & 0xff);
212 }
213
214 if (mDst < mDstUpperLimit) {
215 *mDst++ = (UINT8) (((UINT8) (Data >> 0x18)) & 0xff);
216 }
217 }
218
219 STATIC
220 EFI_STATUS
AllocateMemory(VOID)221 AllocateMemory (
222 VOID
223 )
224 /*++
225
226 Routine Description:
227
228 Allocate memory spaces for data structures used in compression process
229
230 Argements:
231 VOID
232
233 Returns:
234
235 EFI_SUCCESS - Memory is allocated successfully
236 EFI_OUT_OF_RESOURCES - Allocation fails
237
238 --*/
239 {
240 UINT32 Index;
241
242 mText = malloc (WNDSIZ * 2 + MAXMATCH);
243 if (mText == NULL) {
244 Error (NULL, 0, 4001, "Resource", "memory cannot be allocated!");
245 return EFI_OUT_OF_RESOURCES;
246 }
247 for (Index = 0; Index < WNDSIZ * 2 + MAXMATCH; Index++) {
248 mText[Index] = 0;
249 }
250
251 mLevel = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mLevel));
252 mChildCount = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mChildCount));
253 mPosition = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mPosition));
254 mParent = malloc (WNDSIZ * 2 * sizeof (*mParent));
255 mPrev = malloc (WNDSIZ * 2 * sizeof (*mPrev));
256 mNext = malloc ((MAX_HASH_VAL + 1) * sizeof (*mNext));
257 if (mLevel == NULL || mChildCount == NULL || mPosition == NULL ||
258 mParent == NULL || mPrev == NULL || mNext == NULL) {
259 Error (NULL, 0, 4001, "Resource", "memory cannot be allocated!");
260 return EFI_OUT_OF_RESOURCES;
261 }
262
263 mBufSiz = BLKSIZ;
264 mBuf = malloc (mBufSiz);
265 while (mBuf == NULL) {
266 mBufSiz = (mBufSiz / 10U) * 9U;
267 if (mBufSiz < 4 * 1024U) {
268 return EFI_OUT_OF_RESOURCES;
269 }
270
271 mBuf = malloc (mBufSiz);
272 }
273
274 mBuf[0] = 0;
275
276 return EFI_SUCCESS;
277 }
278
279 VOID
FreeMemory(VOID)280 FreeMemory (
281 VOID
282 )
283 /*++
284
285 Routine Description:
286
287 Called when compression is completed to free memory previously allocated.
288
289 Arguments: (VOID)
290
291 Returns: (VOID)
292
293 --*/
294 {
295 if (mText != NULL) {
296 free (mText);
297 }
298
299 if (mLevel != NULL) {
300 free (mLevel);
301 }
302
303 if (mChildCount != NULL) {
304 free (mChildCount);
305 }
306
307 if (mPosition != NULL) {
308 free (mPosition);
309 }
310
311 if (mParent != NULL) {
312 free (mParent);
313 }
314
315 if (mPrev != NULL) {
316 free (mPrev);
317 }
318
319 if (mNext != NULL) {
320 free (mNext);
321 }
322
323 if (mBuf != NULL) {
324 free (mBuf);
325 }
326
327 return ;
328 }
329
330 STATIC
331 VOID
InitSlide(VOID)332 InitSlide (
333 VOID
334 )
335 /*++
336
337 Routine Description:
338
339 Initialize String Info Log data structures
340
341 Arguments: (VOID)
342
343 Returns: (VOID)
344
345 --*/
346 {
347 NODE Index;
348
349 for (Index = WNDSIZ; Index <= WNDSIZ + UINT8_MAX; Index++) {
350 mLevel[Index] = 1;
351 mPosition[Index] = NIL; // sentinel
352 }
353
354 for (Index = WNDSIZ; Index < WNDSIZ * 2; Index++) {
355 mParent[Index] = NIL;
356 }
357
358 mAvail = 1;
359 for (Index = 1; Index < WNDSIZ - 1; Index++) {
360 mNext[Index] = (NODE) (Index + 1);
361 }
362
363 mNext[WNDSIZ - 1] = NIL;
364 for (Index = WNDSIZ * 2; Index <= MAX_HASH_VAL; Index++) {
365 mNext[Index] = NIL;
366 }
367 }
368
369 STATIC
370 NODE
Child(IN NODE NodeQ,IN UINT8 CharC)371 Child (
372 IN NODE NodeQ,
373 IN UINT8 CharC
374 )
375 /*++
376
377 Routine Description:
378
379 Find child node given the parent node and the edge character
380
381 Arguments:
382
383 NodeQ - the parent node
384 CharC - the edge character
385
386 Returns:
387
388 The child node (NIL if not found)
389
390 --*/
391 {
392 NODE NodeR;
393
394 NodeR = mNext[HASH (NodeQ, CharC)];
395 //
396 // sentinel
397 //
398 mParent[NIL] = NodeQ;
399 while (mParent[NodeR] != NodeQ) {
400 NodeR = mNext[NodeR];
401 }
402
403 return NodeR;
404 }
405
406 STATIC
407 VOID
MakeChild(IN NODE Parent,IN UINT8 CharC,IN NODE Child)408 MakeChild (
409 IN NODE Parent,
410 IN UINT8 CharC,
411 IN NODE Child
412 )
413 /*++
414
415 Routine Description:
416
417 Create a new child for a given parent node.
418
419 Arguments:
420
421 Parent - the parent node
422 CharC - the edge character
423 Child - the child node
424
425 Returns: (VOID)
426
427 --*/
428 {
429 NODE Node1;
430 NODE Node2;
431
432 Node1 = (NODE) HASH (Parent, CharC);
433 Node2 = mNext[Node1];
434 mNext[Node1] = Child;
435 mNext[Child] = Node2;
436 mPrev[Node2] = Child;
437 mPrev[Child] = Node1;
438 mParent[Child] = Parent;
439 mChildCount[Parent]++;
440 }
441
442 STATIC
443 VOID
Split(NODE Old)444 Split (
445 NODE Old
446 )
447 /*++
448
449 Routine Description:
450
451 Split a node.
452
453 Arguments:
454
455 Old - the node to split
456
457 Returns: (VOID)
458
459 --*/
460 {
461 NODE New;
462 NODE TempNode;
463
464 New = mAvail;
465 mAvail = mNext[New];
466 mChildCount[New] = 0;
467 TempNode = mPrev[Old];
468 mPrev[New] = TempNode;
469 mNext[TempNode] = New;
470 TempNode = mNext[Old];
471 mNext[New] = TempNode;
472 mPrev[TempNode] = New;
473 mParent[New] = mParent[Old];
474 mLevel[New] = (UINT8) mMatchLen;
475 mPosition[New] = mPos;
476 MakeChild (New, mText[mMatchPos + mMatchLen], Old);
477 MakeChild (New, mText[mPos + mMatchLen], mPos);
478 }
479
480 STATIC
481 VOID
InsertNode(VOID)482 InsertNode (
483 VOID
484 )
485 /*++
486
487 Routine Description:
488
489 Insert string info for current position into the String Info Log
490
491 Arguments: (VOID)
492
493 Returns: (VOID)
494
495 --*/
496 {
497 NODE NodeQ;
498 NODE NodeR;
499 NODE Index2;
500 NODE NodeT;
501 UINT8 CharC;
502 UINT8 *t1;
503 UINT8 *t2;
504
505 if (mMatchLen >= 4) {
506 //
507 // We have just got a long match, the target tree
508 // can be located by MatchPos + 1. Travese the tree
509 // from bottom up to get to a proper starting point.
510 // The usage of PERC_FLAG ensures proper node deletion
511 // in DeleteNode() later.
512 //
513 mMatchLen--;
514 NodeR = (NODE) ((mMatchPos + 1) | WNDSIZ);
515 NodeQ = mParent[NodeR];
516 while (NodeQ == NIL) {
517 NodeR = mNext[NodeR];
518 NodeQ = mParent[NodeR];
519 }
520
521 while (mLevel[NodeQ] >= mMatchLen) {
522 NodeR = NodeQ;
523 NodeQ = mParent[NodeQ];
524 }
525
526 NodeT = NodeQ;
527 while (mPosition[NodeT] < 0) {
528 mPosition[NodeT] = mPos;
529 NodeT = mParent[NodeT];
530 }
531
532 if (NodeT < WNDSIZ) {
533 mPosition[NodeT] = (NODE) (mPos | (UINT32) PERC_FLAG);
534 }
535 } else {
536 //
537 // Locate the target tree
538 //
539 NodeQ = (NODE) (mText[mPos] + WNDSIZ);
540 CharC = mText[mPos + 1];
541 NodeR = Child (NodeQ, CharC);
542 if (NodeR == NIL) {
543 MakeChild (NodeQ, CharC, mPos);
544 mMatchLen = 1;
545 return ;
546 }
547
548 mMatchLen = 2;
549 }
550 //
551 // Traverse down the tree to find a match.
552 // Update Position value along the route.
553 // Node split or creation is involved.
554 //
555 for (;;) {
556 if (NodeR >= WNDSIZ) {
557 Index2 = MAXMATCH;
558 mMatchPos = NodeR;
559 } else {
560 Index2 = mLevel[NodeR];
561 mMatchPos = (NODE) (mPosition[NodeR] & (UINT32)~PERC_FLAG);
562 }
563
564 if (mMatchPos >= mPos) {
565 mMatchPos -= WNDSIZ;
566 }
567
568 t1 = &mText[mPos + mMatchLen];
569 t2 = &mText[mMatchPos + mMatchLen];
570 while (mMatchLen < Index2) {
571 if (*t1 != *t2) {
572 Split (NodeR);
573 return ;
574 }
575
576 mMatchLen++;
577 t1++;
578 t2++;
579 }
580
581 if (mMatchLen >= MAXMATCH) {
582 break;
583 }
584
585 mPosition[NodeR] = mPos;
586 NodeQ = NodeR;
587 NodeR = Child (NodeQ, *t1);
588 if (NodeR == NIL) {
589 MakeChild (NodeQ, *t1, mPos);
590 return ;
591 }
592
593 mMatchLen++;
594 }
595
596 NodeT = mPrev[NodeR];
597 mPrev[mPos] = NodeT;
598 mNext[NodeT] = mPos;
599 NodeT = mNext[NodeR];
600 mNext[mPos] = NodeT;
601 mPrev[NodeT] = mPos;
602 mParent[mPos] = NodeQ;
603 mParent[NodeR] = NIL;
604
605 //
606 // Special usage of 'next'
607 //
608 mNext[NodeR] = mPos;
609
610 }
611
612 STATIC
613 VOID
DeleteNode(VOID)614 DeleteNode (
615 VOID
616 )
617 /*++
618
619 Routine Description:
620
621 Delete outdated string info. (The Usage of PERC_FLAG
622 ensures a clean deletion)
623
624 Arguments: (VOID)
625
626 Returns: (VOID)
627
628 --*/
629 {
630 NODE NodeQ;
631 NODE NodeR;
632 NODE NodeS;
633 NODE NodeT;
634 NODE NodeU;
635
636 if (mParent[mPos] == NIL) {
637 return ;
638 }
639
640 NodeR = mPrev[mPos];
641 NodeS = mNext[mPos];
642 mNext[NodeR] = NodeS;
643 mPrev[NodeS] = NodeR;
644 NodeR = mParent[mPos];
645 mParent[mPos] = NIL;
646 if (NodeR >= WNDSIZ) {
647 return ;
648 }
649
650 mChildCount[NodeR]--;
651 if (mChildCount[NodeR] > 1) {
652 return ;
653 }
654
655 NodeT = (NODE) (mPosition[NodeR] & (UINT32)~PERC_FLAG);
656 if (NodeT >= mPos) {
657 NodeT -= WNDSIZ;
658 }
659
660 NodeS = NodeT;
661 NodeQ = mParent[NodeR];
662 NodeU = mPosition[NodeQ];
663 while (NodeU & (UINT32) PERC_FLAG) {
664 NodeU &= (UINT32)~PERC_FLAG;
665 if (NodeU >= mPos) {
666 NodeU -= WNDSIZ;
667 }
668
669 if (NodeU > NodeS) {
670 NodeS = NodeU;
671 }
672
673 mPosition[NodeQ] = (NODE) (NodeS | WNDSIZ);
674 NodeQ = mParent[NodeQ];
675 NodeU = mPosition[NodeQ];
676 }
677
678 if (NodeQ < WNDSIZ) {
679 if (NodeU >= mPos) {
680 NodeU -= WNDSIZ;
681 }
682
683 if (NodeU > NodeS) {
684 NodeS = NodeU;
685 }
686
687 mPosition[NodeQ] = (NODE) (NodeS | WNDSIZ | (UINT32) PERC_FLAG);
688 }
689
690 NodeS = Child (NodeR, mText[NodeT + mLevel[NodeR]]);
691 NodeT = mPrev[NodeS];
692 NodeU = mNext[NodeS];
693 mNext[NodeT] = NodeU;
694 mPrev[NodeU] = NodeT;
695 NodeT = mPrev[NodeR];
696 mNext[NodeT] = NodeS;
697 mPrev[NodeS] = NodeT;
698 NodeT = mNext[NodeR];
699 mPrev[NodeT] = NodeS;
700 mNext[NodeS] = NodeT;
701 mParent[NodeS] = mParent[NodeR];
702 mParent[NodeR] = NIL;
703 mNext[NodeR] = mAvail;
704 mAvail = NodeR;
705 }
706
707 STATIC
708 VOID
GetNextMatch(VOID)709 GetNextMatch (
710 VOID
711 )
712 /*++
713
714 Routine Description:
715
716 Advance the current position (read in new data if needed).
717 Delete outdated string info. Find a match string for current position.
718
719 Arguments: (VOID)
720
721 Returns: (VOID)
722
723 --*/
724 {
725 INT32 Number;
726
727 mRemainder--;
728 mPos++;
729 if (mPos == WNDSIZ * 2) {
730 memmove (&mText[0], &mText[WNDSIZ], WNDSIZ + MAXMATCH);
731 Number = FreadCrc (&mText[WNDSIZ + MAXMATCH], WNDSIZ);
732 mRemainder += Number;
733 mPos = WNDSIZ;
734 }
735
736 DeleteNode ();
737 InsertNode ();
738 }
739
740 STATIC
741 EFI_STATUS
Encode(VOID)742 Encode (
743 VOID
744 )
745 /*++
746
747 Routine Description:
748
749 The main controlling routine for compression process.
750
751 Arguments: (VOID)
752
753 Returns:
754
755 EFI_SUCCESS - The compression is successful
756 EFI_OUT_0F_RESOURCES - Not enough memory for compression process
757
758 --*/
759 {
760 EFI_STATUS Status;
761 INT32 LastMatchLen;
762 NODE LastMatchPos;
763
764 Status = AllocateMemory ();
765 if (EFI_ERROR (Status)) {
766 FreeMemory ();
767 return Status;
768 }
769
770 InitSlide ();
771
772 HufEncodeStart ();
773
774 mRemainder = FreadCrc (&mText[WNDSIZ], WNDSIZ + MAXMATCH);
775
776 mMatchLen = 0;
777 mPos = WNDSIZ;
778 InsertNode ();
779 if (mMatchLen > mRemainder) {
780 mMatchLen = mRemainder;
781 }
782
783 while (mRemainder > 0) {
784 LastMatchLen = mMatchLen;
785 LastMatchPos = mMatchPos;
786 GetNextMatch ();
787 if (mMatchLen > mRemainder) {
788 mMatchLen = mRemainder;
789 }
790
791 if (mMatchLen > LastMatchLen || LastMatchLen < THRESHOLD) {
792 //
793 // Not enough benefits are gained by outputting a pointer,
794 // so just output the original character
795 //
796 Output (mText[mPos - 1], 0);
797
798 } else {
799
800 if (LastMatchLen == THRESHOLD) {
801 if (((mPos - LastMatchPos - 2) & (WNDSIZ - 1)) > (1U << 11)) {
802 Output (mText[mPos - 1], 0);
803 continue;
804 }
805 }
806 //
807 // Outputting a pointer is beneficial enough, do it.
808 //
809 Output (
810 LastMatchLen + (UINT8_MAX + 1 - THRESHOLD),
811 (mPos - LastMatchPos - 2) & (WNDSIZ - 1)
812 );
813 LastMatchLen--;
814 while (LastMatchLen > 0) {
815 GetNextMatch ();
816 LastMatchLen--;
817 }
818
819 if (mMatchLen > mRemainder) {
820 mMatchLen = mRemainder;
821 }
822 }
823 }
824
825 HufEncodeEnd ();
826 FreeMemory ();
827 return EFI_SUCCESS;
828 }
829
830 STATIC
831 VOID
CountTFreq(VOID)832 CountTFreq (
833 VOID
834 )
835 /*++
836
837 Routine Description:
838
839 Count the frequencies for the Extra Set
840
841 Arguments: (VOID)
842
843 Returns: (VOID)
844
845 --*/
846 {
847 INT32 Index;
848 INT32 Index3;
849 INT32 Number;
850 INT32 Count;
851
852 for (Index = 0; Index < NT; Index++) {
853 mTFreq[Index] = 0;
854 }
855
856 Number = NC;
857 while (Number > 0 && mCLen[Number - 1] == 0) {
858 Number--;
859 }
860
861 Index = 0;
862 while (Index < Number) {
863 Index3 = mCLen[Index++];
864 if (Index3 == 0) {
865 Count = 1;
866 while (Index < Number && mCLen[Index] == 0) {
867 Index++;
868 Count++;
869 }
870
871 if (Count <= 2) {
872 mTFreq[0] = (UINT16) (mTFreq[0] + Count);
873 } else if (Count <= 18) {
874 mTFreq[1]++;
875 } else if (Count == 19) {
876 mTFreq[0]++;
877 mTFreq[1]++;
878 } else {
879 mTFreq[2]++;
880 }
881 } else {
882 mTFreq[Index3 + 2]++;
883 }
884 }
885 }
886
887 STATIC
888 VOID
WritePTLen(IN INT32 Number,IN INT32 nbit,IN INT32 Special)889 WritePTLen (
890 IN INT32 Number,
891 IN INT32 nbit,
892 IN INT32 Special
893 )
894 /*++
895
896 Routine Description:
897
898 Outputs the code length array for the Extra Set or the Position Set.
899
900 Arguments:
901
902 Number - the number of symbols
903 nbit - the number of bits needed to represent 'n'
904 Special - the special symbol that needs to be take care of
905
906 Returns: (VOID)
907
908 --*/
909 {
910 INT32 Index;
911 INT32 Index3;
912
913 while (Number > 0 && mPTLen[Number - 1] == 0) {
914 Number--;
915 }
916
917 PutBits (nbit, Number);
918 Index = 0;
919 while (Index < Number) {
920 Index3 = mPTLen[Index++];
921 if (Index3 <= 6) {
922 PutBits (3, Index3);
923 } else {
924 PutBits (Index3 - 3, (1U << (Index3 - 3)) - 2);
925 }
926
927 if (Index == Special) {
928 while (Index < 6 && mPTLen[Index] == 0) {
929 Index++;
930 }
931
932 PutBits (2, (Index - 3) & 3);
933 }
934 }
935 }
936
937 STATIC
938 VOID
WriteCLen(VOID)939 WriteCLen (
940 VOID
941 )
942 /*++
943
944 Routine Description:
945
946 Outputs the code length array for Char&Length Set
947
948 Arguments: (VOID)
949
950 Returns: (VOID)
951
952 --*/
953 {
954 INT32 Index;
955 INT32 Index3;
956 INT32 Number;
957 INT32 Count;
958
959 Number = NC;
960 while (Number > 0 && mCLen[Number - 1] == 0) {
961 Number--;
962 }
963
964 PutBits (CBIT, Number);
965 Index = 0;
966 while (Index < Number) {
967 Index3 = mCLen[Index++];
968 if (Index3 == 0) {
969 Count = 1;
970 while (Index < Number && mCLen[Index] == 0) {
971 Index++;
972 Count++;
973 }
974
975 if (Count <= 2) {
976 for (Index3 = 0; Index3 < Count; Index3++) {
977 PutBits (mPTLen[0], mPTCode[0]);
978 }
979 } else if (Count <= 18) {
980 PutBits (mPTLen[1], mPTCode[1]);
981 PutBits (4, Count - 3);
982 } else if (Count == 19) {
983 PutBits (mPTLen[0], mPTCode[0]);
984 PutBits (mPTLen[1], mPTCode[1]);
985 PutBits (4, 15);
986 } else {
987 PutBits (mPTLen[2], mPTCode[2]);
988 PutBits (CBIT, Count - 20);
989 }
990 } else {
991 PutBits (mPTLen[Index3 + 2], mPTCode[Index3 + 2]);
992 }
993 }
994 }
995
996 STATIC
997 VOID
EncodeC(IN INT32 Value)998 EncodeC (
999 IN INT32 Value
1000 )
1001 {
1002 PutBits (mCLen[Value], mCCode[Value]);
1003 }
1004
1005 STATIC
1006 VOID
EncodeP(IN UINT32 Value)1007 EncodeP (
1008 IN UINT32 Value
1009 )
1010 {
1011 UINT32 Index;
1012 UINT32 NodeQ;
1013
1014 Index = 0;
1015 NodeQ = Value;
1016 while (NodeQ) {
1017 NodeQ >>= 1;
1018 Index++;
1019 }
1020
1021 PutBits (mPTLen[Index], mPTCode[Index]);
1022 if (Index > 1) {
1023 PutBits (Index - 1, Value & (0xFFFFFFFFU >> (32 - Index + 1)));
1024 }
1025 }
1026
1027 STATIC
1028 VOID
SendBlock(VOID)1029 SendBlock (
1030 VOID
1031 )
1032 /*++
1033
1034 Routine Description:
1035
1036 Huffman code the block and output it.
1037
1038 Arguments:
1039 (VOID)
1040
1041 Returns:
1042 (VOID)
1043
1044 --*/
1045 {
1046 UINT32 Index;
1047 UINT32 Index2;
1048 UINT32 Index3;
1049 UINT32 Flags;
1050 UINT32 Root;
1051 UINT32 Pos;
1052 UINT32 Size;
1053 Flags = 0;
1054
1055 Root = MakeTree (NC, mCFreq, mCLen, mCCode);
1056 Size = mCFreq[Root];
1057
1058 PutBits (16, Size);
1059 if (Root >= NC) {
1060 CountTFreq ();
1061 Root = MakeTree (NT, mTFreq, mPTLen, mPTCode);
1062 if (Root >= NT) {
1063 WritePTLen (NT, TBIT, 3);
1064 } else {
1065 PutBits (TBIT, 0);
1066 PutBits (TBIT, Root);
1067 }
1068
1069 WriteCLen ();
1070 } else {
1071 PutBits (TBIT, 0);
1072 PutBits (TBIT, 0);
1073 PutBits (CBIT, 0);
1074 PutBits (CBIT, Root);
1075 }
1076
1077 Root = MakeTree (NP, mPFreq, mPTLen, mPTCode);
1078 if (Root >= NP) {
1079 WritePTLen (NP, PBIT, -1);
1080 } else {
1081 PutBits (PBIT, 0);
1082 PutBits (PBIT, Root);
1083 }
1084
1085 Pos = 0;
1086 for (Index = 0; Index < Size; Index++) {
1087 if (Index % UINT8_BIT == 0) {
1088 Flags = mBuf[Pos++];
1089 } else {
1090 Flags <<= 1;
1091 }
1092
1093 if (Flags & (1U << (UINT8_BIT - 1))) {
1094 EncodeC (mBuf[Pos++] + (1U << UINT8_BIT));
1095 Index3 = mBuf[Pos++];
1096 for (Index2 = 0; Index2 < 3; Index2++) {
1097 Index3 <<= UINT8_BIT;
1098 Index3 += mBuf[Pos++];
1099 }
1100
1101 EncodeP (Index3);
1102 } else {
1103 EncodeC (mBuf[Pos++]);
1104 }
1105 }
1106
1107 for (Index = 0; Index < NC; Index++) {
1108 mCFreq[Index] = 0;
1109 }
1110
1111 for (Index = 0; Index < NP; Index++) {
1112 mPFreq[Index] = 0;
1113 }
1114 }
1115
1116 STATIC
1117 VOID
Output(IN UINT32 CharC,IN UINT32 Pos)1118 Output (
1119 IN UINT32 CharC,
1120 IN UINT32 Pos
1121 )
1122 /*++
1123
1124 Routine Description:
1125
1126 Outputs an Original Character or a Pointer
1127
1128 Arguments:
1129
1130 CharC - The original character or the 'String Length' element of a Pointer
1131 Pos - The 'Position' field of a Pointer
1132
1133 Returns: (VOID)
1134
1135 --*/
1136 {
1137 STATIC UINT32 CPos;
1138
1139 if ((mOutputMask >>= 1) == 0) {
1140 mOutputMask = 1U << (UINT8_BIT - 1);
1141 //
1142 // Check the buffer overflow per outputing UINT8_BIT symbols
1143 // which is an Original Character or a Pointer. The biggest
1144 // symbol is a Pointer which occupies 5 bytes.
1145 //
1146 if (mOutputPos >= mBufSiz - 5 * UINT8_BIT) {
1147 SendBlock ();
1148 mOutputPos = 0;
1149 }
1150
1151 CPos = mOutputPos++;
1152 mBuf[CPos] = 0;
1153 }
1154
1155 mBuf[mOutputPos++] = (UINT8) CharC;
1156 mCFreq[CharC]++;
1157 if (CharC >= (1U << UINT8_BIT)) {
1158 mBuf[CPos] |= mOutputMask;
1159 mBuf[mOutputPos++] = (UINT8) (Pos >> 24);
1160 mBuf[mOutputPos++] = (UINT8) (Pos >> 16);
1161 mBuf[mOutputPos++] = (UINT8) (Pos >> (UINT8_BIT));
1162 mBuf[mOutputPos++] = (UINT8) Pos;
1163 CharC = 0;
1164 while (Pos) {
1165 Pos >>= 1;
1166 CharC++;
1167 }
1168
1169 mPFreq[CharC]++;
1170 }
1171 }
1172
1173 STATIC
1174 VOID
HufEncodeStart(VOID)1175 HufEncodeStart (
1176 VOID
1177 )
1178 {
1179 INT32 Index;
1180
1181 for (Index = 0; Index < NC; Index++) {
1182 mCFreq[Index] = 0;
1183 }
1184
1185 for (Index = 0; Index < NP; Index++) {
1186 mPFreq[Index] = 0;
1187 }
1188
1189 mOutputPos = mOutputMask = 0;
1190 InitPutBits ();
1191 return ;
1192 }
1193
1194 STATIC
1195 VOID
HufEncodeEnd(VOID)1196 HufEncodeEnd (
1197 VOID
1198 )
1199 {
1200 SendBlock ();
1201
1202 //
1203 // Flush remaining bits
1204 //
1205 PutBits (UINT8_BIT - 1, 0);
1206
1207 return ;
1208 }
1209
1210 STATIC
1211 VOID
MakeCrcTable(VOID)1212 MakeCrcTable (
1213 VOID
1214 )
1215 {
1216 UINT32 Index;
1217 UINT32 Index2;
1218 UINT32 Temp;
1219
1220 for (Index = 0; Index <= UINT8_MAX; Index++) {
1221 Temp = Index;
1222 for (Index2 = 0; Index2 < UINT8_BIT; Index2++) {
1223 if (Temp & 1) {
1224 Temp = (Temp >> 1) ^ CRCPOLY;
1225 } else {
1226 Temp >>= 1;
1227 }
1228 }
1229
1230 mCrcTable[Index] = (UINT16) Temp;
1231 }
1232 }
1233
1234 STATIC
1235 VOID
PutBits(IN INT32 Number,IN UINT32 Value)1236 PutBits (
1237 IN INT32 Number,
1238 IN UINT32 Value
1239 )
1240 /*++
1241
1242 Routine Description:
1243
1244 Outputs rightmost n bits of x
1245
1246 Arguments:
1247
1248 Number - the rightmost n bits of the data is used
1249 x - the data
1250
1251 Returns: (VOID)
1252
1253 --*/
1254 {
1255 UINT8 Temp;
1256
1257 while (Number >= mBitCount) {
1258 //
1259 // Number -= mBitCount should never equal to 32
1260 //
1261 Temp = (UINT8) (mSubBitBuf | (Value >> (Number -= mBitCount)));
1262
1263 if (mDst < mDstUpperLimit) {
1264 *mDst++ = Temp;
1265 }
1266
1267 mCompSize++;
1268 mSubBitBuf = 0;
1269 mBitCount = UINT8_BIT;
1270 }
1271
1272 mSubBitBuf |= Value << (mBitCount -= Number);
1273 }
1274
1275 STATIC
1276 INT32
FreadCrc(OUT UINT8 * Pointer,IN INT32 Number)1277 FreadCrc (
1278 OUT UINT8 *Pointer,
1279 IN INT32 Number
1280 )
1281 /*++
1282
1283 Routine Description:
1284
1285 Read in source data
1286
1287 Arguments:
1288
1289 Pointer - the buffer to hold the data
1290 Number - number of bytes to read
1291
1292 Returns:
1293
1294 number of bytes actually read
1295
1296 --*/
1297 {
1298 INT32 Index;
1299
1300 for (Index = 0; mSrc < mSrcUpperLimit && Index < Number; Index++) {
1301 *Pointer++ = *mSrc++;
1302 }
1303
1304 Number = Index;
1305
1306 Pointer -= Number;
1307 mOrigSize += Number;
1308
1309 Index--;
1310 while (Index >= 0) {
1311 UPDATE_CRC (*Pointer++);
1312 Index--;
1313 }
1314
1315 return Number;
1316 }
1317
1318 STATIC
1319 VOID
InitPutBits(VOID)1320 InitPutBits (
1321 VOID
1322 )
1323 {
1324 mBitCount = UINT8_BIT;
1325 mSubBitBuf = 0;
1326 }
1327
1328 STATIC
1329 VOID
CountLen(IN INT32 Index)1330 CountLen (
1331 IN INT32 Index
1332 )
1333 /*++
1334
1335 Routine Description:
1336
1337 Count the number of each code length for a Huffman tree.
1338
1339 Arguments:
1340
1341 Index - the top node
1342
1343 Returns: (VOID)
1344
1345 --*/
1346 {
1347 STATIC INT32 Depth = 0;
1348
1349 if (Index < mN) {
1350 mLenCnt[(Depth < 16) ? Depth : 16]++;
1351 } else {
1352 Depth++;
1353 CountLen (mLeft[Index]);
1354 CountLen (mRight[Index]);
1355 Depth--;
1356 }
1357 }
1358
1359 STATIC
1360 VOID
MakeLen(IN INT32 Root)1361 MakeLen (
1362 IN INT32 Root
1363 )
1364 /*++
1365
1366 Routine Description:
1367
1368 Create code length array for a Huffman tree
1369
1370 Arguments:
1371
1372 Root - the root of the tree
1373
1374 Returns:
1375
1376 VOID
1377
1378 --*/
1379 {
1380 INT32 Index;
1381 INT32 Index3;
1382 UINT32 Cum;
1383
1384 for (Index = 0; Index <= 16; Index++) {
1385 mLenCnt[Index] = 0;
1386 }
1387
1388 CountLen (Root);
1389
1390 //
1391 // Adjust the length count array so that
1392 // no code will be generated longer than its designated length
1393 //
1394 Cum = 0;
1395 for (Index = 16; Index > 0; Index--) {
1396 Cum += mLenCnt[Index] << (16 - Index);
1397 }
1398
1399 while (Cum != (1U << 16)) {
1400 mLenCnt[16]--;
1401 for (Index = 15; Index > 0; Index--) {
1402 if (mLenCnt[Index] != 0) {
1403 mLenCnt[Index]--;
1404 mLenCnt[Index + 1] += 2;
1405 break;
1406 }
1407 }
1408
1409 Cum--;
1410 }
1411
1412 for (Index = 16; Index > 0; Index--) {
1413 Index3 = mLenCnt[Index];
1414 Index3--;
1415 while (Index3 >= 0) {
1416 mLen[*mSortPtr++] = (UINT8) Index;
1417 Index3--;
1418 }
1419 }
1420 }
1421
1422 STATIC
1423 VOID
DownHeap(IN INT32 Index)1424 DownHeap (
1425 IN INT32 Index
1426 )
1427 {
1428 INT32 Index2;
1429 INT32 Index3;
1430
1431 //
1432 // priority queue: send Index-th entry down heap
1433 //
1434 Index3 = mHeap[Index];
1435 Index2 = 2 * Index;
1436 while (Index2 <= mHeapSize) {
1437 if (Index2 < mHeapSize && mFreq[mHeap[Index2]] > mFreq[mHeap[Index2 + 1]]) {
1438 Index2++;
1439 }
1440
1441 if (mFreq[Index3] <= mFreq[mHeap[Index2]]) {
1442 break;
1443 }
1444
1445 mHeap[Index] = mHeap[Index2];
1446 Index = Index2;
1447 Index2 = 2 * Index;
1448 }
1449
1450 mHeap[Index] = (INT16) Index3;
1451 }
1452
1453 STATIC
1454 VOID
MakeCode(IN INT32 Number,IN UINT8 Len[],OUT UINT16 Code[])1455 MakeCode (
1456 IN INT32 Number,
1457 IN UINT8 Len[ ],
1458 OUT UINT16 Code[]
1459 )
1460 /*++
1461
1462 Routine Description:
1463
1464 Assign code to each symbol based on the code length array
1465
1466 Arguments:
1467
1468 Number - number of symbols
1469 Len - the code length array
1470 Code - stores codes for each symbol
1471
1472 Returns: (VOID)
1473
1474 --*/
1475 {
1476 INT32 Index;
1477 UINT16 Start[18];
1478
1479 Start[1] = 0;
1480 for (Index = 1; Index <= 16; Index++) {
1481 Start[Index + 1] = (UINT16) ((Start[Index] + mLenCnt[Index]) << 1);
1482 }
1483
1484 for (Index = 0; Index < Number; Index++) {
1485 Code[Index] = Start[Len[Index]]++;
1486 }
1487 }
1488
1489 STATIC
1490 INT32
MakeTree(IN INT32 NParm,IN UINT16 FreqParm[],OUT UINT8 LenParm[],OUT UINT16 CodeParm[])1491 MakeTree (
1492 IN INT32 NParm,
1493 IN UINT16 FreqParm[],
1494 OUT UINT8 LenParm[ ],
1495 OUT UINT16 CodeParm[]
1496 )
1497 /*++
1498
1499 Routine Description:
1500
1501 Generates Huffman codes given a frequency distribution of symbols
1502
1503 Arguments:
1504
1505 NParm - number of symbols
1506 FreqParm - frequency of each symbol
1507 LenParm - code length for each symbol
1508 CodeParm - code for each symbol
1509
1510 Returns:
1511
1512 Root of the Huffman tree.
1513
1514 --*/
1515 {
1516 INT32 Index;
1517 INT32 Index2;
1518 INT32 Index3;
1519 INT32 Avail;
1520
1521 //
1522 // make tree, calculate len[], return root
1523 //
1524 mN = NParm;
1525 mFreq = FreqParm;
1526 mLen = LenParm;
1527 Avail = mN;
1528 mHeapSize = 0;
1529 mHeap[1] = 0;
1530 for (Index = 0; Index < mN; Index++) {
1531 mLen[Index] = 0;
1532 if (mFreq[Index]) {
1533 mHeapSize++;
1534 mHeap[mHeapSize] = (INT16) Index;
1535 }
1536 }
1537
1538 if (mHeapSize < 2) {
1539 CodeParm[mHeap[1]] = 0;
1540 return mHeap[1];
1541 }
1542
1543 for (Index = mHeapSize / 2; Index >= 1; Index--) {
1544 //
1545 // make priority queue
1546 //
1547 DownHeap (Index);
1548 }
1549
1550 mSortPtr = CodeParm;
1551 do {
1552 Index = mHeap[1];
1553 if (Index < mN) {
1554 *mSortPtr++ = (UINT16) Index;
1555 }
1556
1557 mHeap[1] = mHeap[mHeapSize--];
1558 DownHeap (1);
1559 Index2 = mHeap[1];
1560 if (Index2 < mN) {
1561 *mSortPtr++ = (UINT16) Index2;
1562 }
1563
1564 Index3 = Avail++;
1565 mFreq[Index3] = (UINT16) (mFreq[Index] + mFreq[Index2]);
1566 mHeap[1] = (INT16) Index3;
1567 DownHeap (1);
1568 mLeft[Index3] = (UINT16) Index;
1569 mRight[Index3] = (UINT16) Index2;
1570 } while (mHeapSize > 1);
1571
1572 mSortPtr = CodeParm;
1573 MakeLen (Index3);
1574 MakeCode (NParm, LenParm, CodeParm);
1575
1576 //
1577 // return root
1578 //
1579 return Index3;
1580 }
1581
1582 EFI_STATUS
GetFileContents(IN char * InputFileName,OUT UINT8 * FileBuffer,OUT UINT32 * BufferLength)1583 GetFileContents (
1584 IN char *InputFileName,
1585 OUT UINT8 *FileBuffer,
1586 OUT UINT32 *BufferLength
1587 )
1588 /*++
1589
1590 Routine Description:
1591
1592 Get the contents of file specified in InputFileName
1593 into FileBuffer.
1594
1595 Arguments:
1596
1597 InputFileName - Name of the input file.
1598
1599 FileBuffer - Output buffer to contain data
1600
1601 BufferLength - Actual length of the data
1602
1603 Returns:
1604
1605 EFI_SUCCESS on successful return
1606 EFI_ABORTED if unable to open input file.
1607
1608 --*/
1609 {
1610 UINTN Size;
1611 UINTN FileSize;
1612 FILE *InputFile;
1613
1614 Size = 0;
1615 //
1616 // Copy the file contents to the output buffer.
1617 //
1618 InputFile = fopen (LongFilePath (InputFileName), "rb");
1619 if (InputFile == NULL) {
1620 Error (NULL, 0, 0001, "Error opening file: %s", InputFileName);
1621 return EFI_ABORTED;
1622 }
1623
1624 fseek (InputFile, 0, SEEK_END);
1625 FileSize = ftell (InputFile);
1626 fseek (InputFile, 0, SEEK_SET);
1627 //
1628 // Now read the contents of the file into the buffer
1629 //
1630 if (FileSize > 0 && FileBuffer != NULL) {
1631 if (fread (FileBuffer, FileSize, 1, InputFile) != 1) {
1632 Error (NULL, 0, 0004, "Error reading contents of input file: %s", InputFileName);
1633 fclose (InputFile);
1634 return EFI_ABORTED;
1635 }
1636 }
1637
1638 fclose (InputFile);
1639 Size += (UINTN) FileSize;
1640 *BufferLength = Size;
1641
1642 if (FileBuffer != NULL) {
1643 return EFI_SUCCESS;
1644 } else {
1645 return EFI_BUFFER_TOO_SMALL;
1646 }
1647 }
1648
1649 VOID
Version(VOID)1650 Version (
1651 VOID
1652 )
1653 /*++
1654
1655 Routine Description:
1656
1657 Displays the standard utility information to SDTOUT
1658
1659 Arguments:
1660
1661 None
1662
1663 Returns:
1664
1665 None
1666
1667 --*/
1668 {
1669 fprintf (stdout, "%s Version %d.%d %s \n", UTILITY_NAME, UTILITY_MAJOR_VERSION, UTILITY_MINOR_VERSION, __BUILD_VERSION);
1670 }
1671
1672 VOID
Usage(VOID)1673 Usage (
1674 VOID
1675 )
1676 /*++
1677
1678 Routine Description:
1679
1680 Displays the utility usage syntax to STDOUT
1681
1682 Arguments:
1683
1684 None
1685
1686 Returns:
1687
1688 None
1689
1690 --*/
1691 {
1692 //
1693 // Summary usage
1694 //
1695 fprintf (stdout, "Usage: %s -e|-d [options] <input_file>\n\n", UTILITY_NAME);
1696
1697 //
1698 // Copyright declaration
1699 //
1700 fprintf (stdout, "Copyright (c) 2007 - 2014, Intel Corporation. All rights reserved.\n\n");
1701
1702 //
1703 // Details Option
1704 //
1705 fprintf (stdout, "Options:\n");
1706 fprintf (stdout, " -o FileName, --output FileName\n\
1707 File will be created to store the ouput content.\n");
1708 fprintf (stdout, " -v, --verbose\n\
1709 Turn on verbose output with informational messages.\n");
1710 fprintf (stdout, " -q, --quiet\n\
1711 Disable all messages except key message and fatal error\n");
1712 fprintf (stdout, " --debug [0-9]\n\
1713 Enable debug messages, at input debug level.\n");
1714 fprintf (stdout, " --version\n\
1715 Show program's version number and exit.\n");
1716 fprintf (stdout, " -h, --help\n\
1717 Show this help message and exit.\n");
1718 }
1719
1720
1721 int
main(int argc,char * argv[])1722 main (
1723 int argc,
1724 char *argv[]
1725 )
1726 /*++
1727
1728 Routine Description:
1729
1730 Main
1731
1732 Arguments:
1733
1734 command line parameters
1735
1736 Returns:
1737
1738 EFI_SUCCESS Section header successfully generated and section concatenated.
1739 EFI_ABORTED Could not generate the section
1740 EFI_OUT_OF_RESOURCES No resource to complete the operation.
1741
1742 --*/
1743 {
1744 FILE *OutputFile;
1745 char *OutputFileName;
1746 char *InputFileName;
1747 FILE *InputFile;
1748 EFI_STATUS Status;
1749 UINT8 *FileBuffer;
1750 UINT8 *OutBuffer;
1751 UINT32 InputLength;
1752 UINT32 DstSize;
1753 SCRATCH_DATA *Scratch;
1754 UINT8 *Src;
1755 UINT32 OrigSize;
1756
1757 SetUtilityName(UTILITY_NAME);
1758
1759 FileBuffer = NULL;
1760 Src = NULL;
1761 OutBuffer = NULL;
1762 Scratch = NULL;
1763 OrigSize = 0;
1764 InputLength = 0;
1765 InputFileName = NULL;
1766 OutputFileName = NULL;
1767 InputFile = NULL;
1768 OutputFile = NULL;
1769 DstSize=0;
1770 DebugLevel = 0;
1771 DebugMode = FALSE;
1772
1773 //
1774 // Verify the correct number of arguments
1775 //
1776 if (argc == 1) {
1777 Error (NULL, 0, 1001, "Missing options", "No input options specified.");
1778 Usage();
1779 return 0;
1780 }
1781
1782 if ((strcmp(argv[1], "-h") == 0) || (strcmp(argv[1], "--help") == 0)) {
1783 Usage();
1784 return 0;
1785 }
1786
1787 if ((strcmp(argv[1], "--version") == 0)) {
1788 Version();
1789 return 0;
1790 }
1791
1792 argc--;
1793 argv++;
1794 if (strcmp(argv[0],"-e") == 0) {
1795 //
1796 // encode the input file
1797 //
1798 ENCODE = TRUE;
1799 argc--;
1800 argv++;
1801 } else if (strcmp(argv[0], "-d") == 0) {
1802 //
1803 // decode the input file
1804 //
1805 DECODE = TRUE;
1806 argc--;
1807 argv++;
1808 } else {
1809 //
1810 // Error command line
1811 //
1812 Error (NULL, 0, 1003, "Invalid option value", "the options specified are not recognized.");
1813 Usage();
1814 return 1;
1815 }
1816
1817 while (argc > 0) {
1818 if ((strcmp(argv[0], "-v") == 0) || (stricmp(argv[0], "--verbose") == 0)) {
1819 VerboseMode = TRUE;
1820 argc--;
1821 argv++;
1822 continue;
1823 }
1824
1825 if (stricmp (argv[0], "--debug") == 0) {
1826 argc-=2;
1827 argv++;
1828 Status = AsciiStringToUint64(argv[0], FALSE, &DebugLevel);
1829 if (DebugLevel > 9) {
1830 Error (NULL, 0 ,2000, "Invalid parameter", "Unrecognized argument %s", argv[0]);
1831 goto ERROR;
1832 }
1833 if (DebugLevel>=5 && DebugLevel <=9){
1834 DebugMode = TRUE;
1835 } else {
1836 DebugMode = FALSE;
1837 }
1838 argv++;
1839 continue;
1840 }
1841
1842 if ((strcmp(argv[0], "-q") == 0) || (stricmp (argv[0], "--quiet") == 0)) {
1843 QuietMode = TRUE;
1844 argc--;
1845 argv++;
1846 continue;
1847 }
1848
1849 if ((strcmp(argv[0], "-o") == 0) || (stricmp (argv[0], "--output") == 0)) {
1850 if (argv[1] == NULL || argv[1][0] == '-') {
1851 Error (NULL, 0, 1003, "Invalid option value", "Output File name is missing for -o option");
1852 goto ERROR;
1853 }
1854 OutputFileName = argv[1];
1855 argc -=2;
1856 argv +=2;
1857 continue;
1858 }
1859
1860 if (argv[0][0]!='-') {
1861 InputFileName = argv[0];
1862 argc--;
1863 argv++;
1864 continue;
1865 }
1866
1867 Error (NULL, 0, 1000, "Unknown option", argv[0]);
1868 goto ERROR;
1869 }
1870
1871 if (InputFileName == NULL) {
1872 Error (NULL, 0, 1001, "Missing options", "No input files specified.");
1873 goto ERROR;
1874 }
1875
1876 //
1877 // All Parameters has been parsed, now set the message print level
1878 //
1879 if (QuietMode) {
1880 SetPrintLevel(40);
1881 } else if (VerboseMode) {
1882 SetPrintLevel(15);
1883 } else if (DebugMode) {
1884 SetPrintLevel(DebugLevel);
1885 }
1886
1887 if (VerboseMode) {
1888 VerboseMsg("%s tool start.\n", UTILITY_NAME);
1889 }
1890 Scratch = (SCRATCH_DATA *)malloc(sizeof(SCRATCH_DATA));
1891 if (Scratch == NULL) {
1892 Error (NULL, 0, 4001, "Resource:", "Memory cannot be allocated!");
1893 goto ERROR;
1894 }
1895
1896 InputFile = fopen (LongFilePath (InputFileName), "rb");
1897 if (InputFile == NULL) {
1898 Error (NULL, 0, 0001, "Error opening input file", InputFileName);
1899 goto ERROR;
1900 }
1901
1902 Status = GetFileContents(
1903 InputFileName,
1904 FileBuffer,
1905 &InputLength);
1906
1907 if (Status == EFI_BUFFER_TOO_SMALL) {
1908 FileBuffer = (UINT8 *) malloc (InputLength);
1909 if (FileBuffer == NULL) {
1910 Error (NULL, 0, 4001, "Resource:", "Memory cannot be allocated!");
1911 goto ERROR;
1912 }
1913
1914 Status = GetFileContents (
1915 InputFileName,
1916 FileBuffer,
1917 &InputLength
1918 );
1919 }
1920
1921 if (EFI_ERROR(Status)) {
1922 Error (NULL, 0, 0004, "Error getting contents of file: %s", InputFileName);
1923 goto ERROR;
1924 }
1925
1926 if (OutputFileName == NULL) {
1927 OutputFileName = DEFAULT_OUTPUT_FILE;
1928 }
1929 OutputFile = fopen (LongFilePath (OutputFileName), "wb");
1930 if (OutputFile == NULL) {
1931 Error (NULL, 0, 0001, "Error opening output file for writing", OutputFileName);
1932 goto ERROR;
1933 }
1934
1935 if (ENCODE) {
1936 //
1937 // First call TianoCompress to get DstSize
1938 //
1939 if (DebugMode) {
1940 DebugMsg(UTILITY_NAME, 0, DebugLevel, "Encoding", NULL);
1941 }
1942 Status = TianoCompress ((UINT8 *)FileBuffer, InputLength, OutBuffer, &DstSize);
1943
1944 if (Status == EFI_BUFFER_TOO_SMALL) {
1945 OutBuffer = (UINT8 *) malloc (DstSize);
1946 if (OutBuffer == NULL) {
1947 Error (NULL, 0, 4001, "Resource:", "Memory cannot be allocated!");
1948 goto ERROR;
1949 }
1950 }
1951
1952 Status = TianoCompress ((UINT8 *)FileBuffer, InputLength, OutBuffer, &DstSize);
1953 if (Status != EFI_SUCCESS) {
1954 Error (NULL, 0, 0007, "Error compressing file", NULL);
1955 goto ERROR;
1956 }
1957
1958 if (OutBuffer == NULL) {
1959 Error (NULL, 0, 4001, "Resource:", "Memory cannot be allocated!");
1960 goto ERROR;
1961 }
1962
1963 fwrite(OutBuffer,(size_t)DstSize, 1, OutputFile);
1964 fclose(OutputFile);
1965 fclose(InputFile);
1966 free(Scratch);
1967 free(FileBuffer);
1968 free(OutBuffer);
1969
1970 if (DebugMode) {
1971 DebugMsg(UTILITY_NAME, 0, DebugLevel, "Encoding Successful!\n", NULL);
1972 }
1973 if (VerboseMode) {
1974 VerboseMsg("Encoding successful\n");
1975 }
1976 return 0;
1977 }
1978 else if (DECODE) {
1979 if (DebugMode) {
1980 DebugMsg(UTILITY_NAME, 0, DebugLevel, "Decoding\n", NULL);
1981 }
1982 //
1983 // Get Compressed file original size
1984 //
1985 Src = (UINT8 *)FileBuffer;
1986 OrigSize = Src[4] + (Src[5] << 8) + (Src[6] << 16) + (Src[7] << 24);
1987
1988 //
1989 // Allocate OutputBuffer
1990 //
1991 OutBuffer = (UINT8 *)malloc(OrigSize);
1992 if (OutBuffer == NULL) {
1993 Error (NULL, 0, 4001, "Resource:", "Memory cannot be allocated!");
1994 goto ERROR;
1995 }
1996
1997 Status = Decompress((VOID *)FileBuffer, (VOID *)OutBuffer, (VOID *)Scratch, 2);
1998 if (Status != EFI_SUCCESS) {
1999 goto ERROR;
2000 }
2001
2002 fwrite(OutBuffer, (size_t)(Scratch->mOrigSize), 1, OutputFile);
2003 fclose(OutputFile);
2004 fclose(InputFile);
2005 free(Scratch);
2006 free(FileBuffer);
2007 free(OutBuffer);
2008
2009 if (DebugMode) {
2010 DebugMsg(UTILITY_NAME, 0, DebugLevel, "Encoding successful!\n", NULL);
2011 }
2012
2013 if (VerboseMode) {
2014 VerboseMsg("Decoding successful\n");
2015 }
2016 return 0;
2017 }
2018
2019 ERROR:
2020 if (DebugMode) {
2021 if (ENCODE) {
2022 DebugMsg(UTILITY_NAME, 0, DebugLevel, "Encoding Error\n", NULL);
2023 } else if (DECODE) {
2024 DebugMsg(UTILITY_NAME, 0, DebugLevel, "Decoding Error\n", NULL);
2025 }
2026 }
2027 if (OutputFile != NULL) {
2028 fclose(OutputFile);
2029 }
2030 if (InputFile != NULL) {
2031 fclose (InputFile);
2032 }
2033 if (Scratch != NULL) {
2034 free(Scratch);
2035 }
2036 if (FileBuffer != NULL) {
2037 free(FileBuffer);
2038 }
2039 if (OutBuffer != NULL) {
2040 free(OutBuffer);
2041 }
2042
2043 if (VerboseMode) {
2044 VerboseMsg("%s tool done with return code is 0x%x.\n", UTILITY_NAME, GetUtilityStatus ());
2045 }
2046 return GetUtilityStatus ();
2047 }
2048
2049 VOID
FillBuf(IN SCRATCH_DATA * Sd,IN UINT16 NumOfBits)2050 FillBuf (
2051 IN SCRATCH_DATA *Sd,
2052 IN UINT16 NumOfBits
2053 )
2054 /*++
2055
2056 Routine Description:
2057
2058 Shift mBitBuf NumOfBits left. Read in NumOfBits of bits from source.
2059
2060 Arguments:
2061
2062 Sd - The global scratch data
2063 NumOfBits - The number of bits to shift and read.
2064
2065 Returns: (VOID)
2066
2067 --*/
2068 {
2069 Sd->mBitBuf = (UINT32) (Sd->mBitBuf << NumOfBits);
2070
2071 while (NumOfBits > Sd->mBitCount) {
2072
2073 Sd->mBitBuf |= (UINT32) (Sd->mSubBitBuf << (NumOfBits = (UINT16) (NumOfBits - Sd->mBitCount)));
2074
2075 if (Sd->mCompSize > 0) {
2076 //
2077 // Get 1 byte into SubBitBuf
2078 //
2079 Sd->mCompSize--;
2080 Sd->mSubBitBuf = 0;
2081 Sd->mSubBitBuf = Sd->mSrcBase[Sd->mInBuf++];
2082 Sd->mBitCount = 8;
2083
2084 } else {
2085 //
2086 // No more bits from the source, just pad zero bit.
2087 //
2088 Sd->mSubBitBuf = 0;
2089 Sd->mBitCount = 8;
2090
2091 }
2092 }
2093
2094 Sd->mBitCount = (UINT16) (Sd->mBitCount - NumOfBits);
2095 Sd->mBitBuf |= Sd->mSubBitBuf >> Sd->mBitCount;
2096 }
2097
2098 UINT32
GetBits(IN SCRATCH_DATA * Sd,IN UINT16 NumOfBits)2099 GetBits (
2100 IN SCRATCH_DATA *Sd,
2101 IN UINT16 NumOfBits
2102 )
2103 /*++
2104
2105 Routine Description:
2106
2107 Get NumOfBits of bits out from mBitBuf. Fill mBitBuf with subsequent
2108 NumOfBits of bits from source. Returns NumOfBits of bits that are
2109 popped out.
2110
2111 Arguments:
2112
2113 Sd - The global scratch data.
2114 NumOfBits - The number of bits to pop and read.
2115
2116 Returns:
2117
2118 The bits that are popped out.
2119
2120 --*/
2121 {
2122 UINT32 OutBits;
2123
2124 OutBits = (UINT32) (Sd->mBitBuf >> (BITBUFSIZ - NumOfBits));
2125
2126 FillBuf (Sd, NumOfBits);
2127
2128 return OutBits;
2129 }
2130
2131 UINT16
MakeTable(IN SCRATCH_DATA * Sd,IN UINT16 NumOfChar,IN UINT8 * BitLen,IN UINT16 TableBits,OUT UINT16 * Table)2132 MakeTable (
2133 IN SCRATCH_DATA *Sd,
2134 IN UINT16 NumOfChar,
2135 IN UINT8 *BitLen,
2136 IN UINT16 TableBits,
2137 OUT UINT16 *Table
2138 )
2139 /*++
2140
2141 Routine Description:
2142
2143 Creates Huffman Code mapping table according to code length array.
2144
2145 Arguments:
2146
2147 Sd - The global scratch data
2148 NumOfChar - Number of symbols in the symbol set
2149 BitLen - Code length array
2150 TableBits - The width of the mapping table
2151 Table - The table
2152
2153 Returns:
2154
2155 0 - OK.
2156 BAD_TABLE - The table is corrupted.
2157
2158 --*/
2159 {
2160 UINT16 Count[17];
2161 UINT16 Weight[17];
2162 UINT16 Start[18];
2163 UINT16 *Pointer;
2164 UINT16 Index3;
2165 UINT16 Index;
2166 UINT16 Len;
2167 UINT16 Char;
2168 UINT16 JuBits;
2169 UINT16 Avail;
2170 UINT16 NextCode;
2171 UINT16 Mask;
2172 UINT16 WordOfStart;
2173 UINT16 WordOfCount;
2174
2175 for (Index = 0; Index <= 16; Index++) {
2176 Count[Index] = 0;
2177 }
2178
2179 for (Index = 0; Index < NumOfChar; Index++) {
2180 Count[BitLen[Index]]++;
2181 }
2182
2183 Start[0] = 0;
2184 Start[1] = 0;
2185
2186 for (Index = 1; Index <= 16; Index++) {
2187 WordOfStart = Start[Index];
2188 WordOfCount = Count[Index];
2189 Start[Index + 1] = (UINT16) (WordOfStart + (WordOfCount << (16 - Index)));
2190 }
2191
2192 if (Start[17] != 0) {
2193 //
2194 //(1U << 16)
2195 //
2196 return (UINT16) BAD_TABLE;
2197 }
2198
2199 JuBits = (UINT16) (16 - TableBits);
2200
2201 Weight[0] = 0;
2202 for (Index = 1; Index <= TableBits; Index++) {
2203 Start[Index] >>= JuBits;
2204 Weight[Index] = (UINT16) (1U << (TableBits - Index));
2205 }
2206
2207 while (Index <= 16) {
2208 Weight[Index] = (UINT16) (1U << (16 - Index));
2209 Index++;
2210 }
2211
2212 Index = (UINT16) (Start[TableBits + 1] >> JuBits);
2213
2214 if (Index != 0) {
2215 Index3 = (UINT16) (1U << TableBits);
2216 while (Index != Index3) {
2217 Table[Index++] = 0;
2218 }
2219 }
2220
2221 Avail = NumOfChar;
2222 Mask = (UINT16) (1U << (15 - TableBits));
2223
2224 for (Char = 0; Char < NumOfChar; Char++) {
2225
2226 Len = BitLen[Char];
2227 if (Len == 0 || Len >= 17) {
2228 continue;
2229 }
2230
2231 NextCode = (UINT16) (Start[Len] + Weight[Len]);
2232
2233 if (Len <= TableBits) {
2234
2235 for (Index = Start[Len]; Index < NextCode; Index++) {
2236 Table[Index] = Char;
2237 }
2238
2239 } else {
2240
2241 Index3 = Start[Len];
2242 Pointer = &Table[Index3 >> JuBits];
2243 Index = (UINT16) (Len - TableBits);
2244
2245 while (Index != 0) {
2246 if (*Pointer == 0) {
2247 Sd->mRight[Avail] = Sd->mLeft[Avail] = 0;
2248 *Pointer = Avail++;
2249 }
2250
2251 if (Index3 & Mask) {
2252 Pointer = &Sd->mRight[*Pointer];
2253 } else {
2254 Pointer = &Sd->mLeft[*Pointer];
2255 }
2256
2257 Index3 <<= 1;
2258 Index--;
2259 }
2260
2261 *Pointer = Char;
2262
2263 }
2264
2265 Start[Len] = NextCode;
2266 }
2267 //
2268 // Succeeds
2269 //
2270 return 0;
2271 }
2272
2273 UINT32
DecodeP(IN SCRATCH_DATA * Sd)2274 DecodeP (
2275 IN SCRATCH_DATA *Sd
2276 )
2277 /*++
2278
2279 Routine Description:
2280
2281 Decodes a position value.
2282
2283 Arguments:
2284
2285 Sd - the global scratch data
2286
2287 Returns:
2288
2289 The position value decoded.
2290
2291 --*/
2292 {
2293 UINT16 Val;
2294 UINT32 Mask;
2295 UINT32 Pos;
2296
2297 Val = Sd->mPTTable[Sd->mBitBuf >> (BITBUFSIZ - 8)];
2298
2299 if (Val >= MAXNP) {
2300 Mask = 1U << (BITBUFSIZ - 1 - 8);
2301
2302 do {
2303
2304 if (Sd->mBitBuf & Mask) {
2305 Val = Sd->mRight[Val];
2306 } else {
2307 Val = Sd->mLeft[Val];
2308 }
2309
2310 Mask >>= 1;
2311 } while (Val >= MAXNP);
2312 }
2313 //
2314 // Advance what we have read
2315 //
2316 FillBuf (Sd, Sd->mPTLen[Val]);
2317
2318 Pos = Val;
2319 if (Val > 1) {
2320 Pos = (UINT32) ((1U << (Val - 1)) + GetBits (Sd, (UINT16) (Val - 1)));
2321 }
2322
2323 return Pos;
2324 }
2325
2326 UINT16
ReadPTLen(IN SCRATCH_DATA * Sd,IN UINT16 nn,IN UINT16 nbit,IN UINT16 Special)2327 ReadPTLen (
2328 IN SCRATCH_DATA *Sd,
2329 IN UINT16 nn,
2330 IN UINT16 nbit,
2331 IN UINT16 Special
2332 )
2333 /*++
2334
2335 Routine Description:
2336
2337 Reads code lengths for the Extra Set or the Position Set
2338
2339 Arguments:
2340
2341 Sd - The global scratch data
2342 nn - Number of symbols
2343 nbit - Number of bits needed to represent nn
2344 Special - The special symbol that needs to be taken care of
2345
2346 Returns:
2347
2348 0 - OK.
2349 BAD_TABLE - Table is corrupted.
2350
2351 --*/
2352 {
2353 UINT16 Number;
2354 UINT16 CharC;
2355 volatile UINT16 Index;
2356 UINT32 Mask;
2357
2358 assert (nn <= NPT);
2359
2360 Number = (UINT16) GetBits (Sd, nbit);
2361
2362 if (Number == 0) {
2363 CharC = (UINT16) GetBits (Sd, nbit);
2364
2365 for (Index = 0; Index < 256; Index++) {
2366 Sd->mPTTable[Index] = CharC;
2367 }
2368
2369 for (Index = 0; Index < nn; Index++) {
2370 Sd->mPTLen[Index] = 0;
2371 }
2372
2373 return 0;
2374 }
2375
2376 Index = 0;
2377
2378 while (Index < Number) {
2379
2380 CharC = (UINT16) (Sd->mBitBuf >> (BITBUFSIZ - 3));
2381
2382 if (CharC == 7) {
2383 Mask = 1U << (BITBUFSIZ - 1 - 3);
2384 while (Mask & Sd->mBitBuf) {
2385 Mask >>= 1;
2386 CharC += 1;
2387 }
2388 }
2389
2390 FillBuf (Sd, (UINT16) ((CharC < 7) ? 3 : CharC - 3));
2391
2392 Sd->mPTLen[Index++] = (UINT8) CharC;
2393
2394 if (Index == Special) {
2395 CharC = (UINT16) GetBits (Sd, 2);
2396 while ((INT16) (--CharC) >= 0) {
2397 Sd->mPTLen[Index++] = 0;
2398 }
2399 }
2400 }
2401
2402 while (Index < nn) {
2403 Sd->mPTLen[Index++] = 0;
2404 }
2405
2406 return MakeTable (Sd, nn, Sd->mPTLen, 8, Sd->mPTTable);
2407 }
2408
2409 VOID
ReadCLen(SCRATCH_DATA * Sd)2410 ReadCLen (
2411 SCRATCH_DATA *Sd
2412 )
2413 /*++
2414
2415 Routine Description:
2416
2417 Reads code lengths for Char&Len Set.
2418
2419 Arguments:
2420
2421 Sd - the global scratch data
2422
2423 Returns: (VOID)
2424
2425 --*/
2426 {
2427 UINT16 Number;
2428 UINT16 CharC;
2429 volatile UINT16 Index;
2430 UINT32 Mask;
2431
2432 Number = (UINT16) GetBits (Sd, CBIT);
2433
2434 if (Number == 0) {
2435 CharC = (UINT16) GetBits (Sd, CBIT);
2436
2437 for (Index = 0; Index < NC; Index++) {
2438 Sd->mCLen[Index] = 0;
2439 }
2440
2441 for (Index = 0; Index < 4096; Index++) {
2442 Sd->mCTable[Index] = CharC;
2443 }
2444
2445 return ;
2446 }
2447
2448 Index = 0;
2449 while (Index < Number) {
2450
2451 CharC = Sd->mPTTable[Sd->mBitBuf >> (BITBUFSIZ - 8)];
2452 if (CharC >= NT) {
2453 Mask = 1U << (BITBUFSIZ - 1 - 8);
2454
2455 do {
2456
2457 if (Mask & Sd->mBitBuf) {
2458 CharC = Sd->mRight[CharC];
2459 } else {
2460 CharC = Sd->mLeft[CharC];
2461 }
2462
2463 Mask >>= 1;
2464
2465 } while (CharC >= NT);
2466 }
2467 //
2468 // Advance what we have read
2469 //
2470 FillBuf (Sd, Sd->mPTLen[CharC]);
2471
2472 if (CharC <= 2) {
2473
2474 if (CharC == 0) {
2475 CharC = 1;
2476 } else if (CharC == 1) {
2477 CharC = (UINT16) (GetBits (Sd, 4) + 3);
2478 } else if (CharC == 2) {
2479 CharC = (UINT16) (GetBits (Sd, CBIT) + 20);
2480 }
2481
2482 while ((INT16) (--CharC) >= 0) {
2483 Sd->mCLen[Index++] = 0;
2484 }
2485
2486 } else {
2487
2488 Sd->mCLen[Index++] = (UINT8) (CharC - 2);
2489
2490 }
2491 }
2492
2493 while (Index < NC) {
2494 Sd->mCLen[Index++] = 0;
2495 }
2496
2497 MakeTable (Sd, NC, Sd->mCLen, 12, Sd->mCTable);
2498
2499 return ;
2500 }
2501
2502 UINT16
DecodeC(SCRATCH_DATA * Sd)2503 DecodeC (
2504 SCRATCH_DATA *Sd
2505 )
2506 /*++
2507
2508 Routine Description:
2509
2510 Decode a character/length value.
2511
2512 Arguments:
2513
2514 Sd - The global scratch data.
2515
2516 Returns:
2517
2518 The value decoded.
2519
2520 --*/
2521 {
2522 UINT16 Index2;
2523 UINT32 Mask;
2524
2525 if (Sd->mBlockSize == 0) {
2526 //
2527 // Starting a new block
2528 //
2529 Sd->mBlockSize = (UINT16) GetBits (Sd, 16);
2530 Sd->mBadTableFlag = ReadPTLen (Sd, NT, TBIT, 3);
2531 if (Sd->mBadTableFlag != 0) {
2532 return 0;
2533 }
2534
2535 ReadCLen (Sd);
2536
2537 Sd->mBadTableFlag = ReadPTLen (Sd, MAXNP, Sd->mPBit, (UINT16) (-1));
2538 if (Sd->mBadTableFlag != 0) {
2539 return 0;
2540 }
2541 }
2542
2543 Sd->mBlockSize--;
2544 Index2 = Sd->mCTable[Sd->mBitBuf >> (BITBUFSIZ - 12)];
2545
2546 if (Index2 >= NC) {
2547 Mask = 1U << (BITBUFSIZ - 1 - 12);
2548
2549 do {
2550 if (Sd->mBitBuf & Mask) {
2551 Index2 = Sd->mRight[Index2];
2552 } else {
2553 Index2 = Sd->mLeft[Index2];
2554 }
2555
2556 Mask >>= 1;
2557 } while (Index2 >= NC);
2558 }
2559 //
2560 // Advance what we have read
2561 //
2562 FillBuf (Sd, Sd->mCLen[Index2]);
2563
2564 return Index2;
2565 }
2566
2567 VOID
Decode(SCRATCH_DATA * Sd)2568 Decode (
2569 SCRATCH_DATA *Sd
2570 )
2571 /*++
2572
2573 Routine Description:
2574
2575 Decode the source data and put the resulting data into the destination buffer.
2576
2577 Arguments:
2578
2579 Sd - The global scratch data
2580
2581 Returns: (VOID)
2582
2583 --*/
2584 {
2585 UINT16 BytesRemain;
2586 UINT32 DataIdx;
2587 UINT16 CharC;
2588
2589 BytesRemain = (UINT16) (-1);
2590
2591 DataIdx = 0;
2592
2593 for (;;) {
2594 CharC = DecodeC (Sd);
2595 if (Sd->mBadTableFlag != 0) {
2596 goto Done ;
2597 }
2598
2599 if (CharC < 256) {
2600 //
2601 // Process an Original character
2602 //
2603 if (Sd->mOutBuf >= Sd->mOrigSize) {
2604 goto Done ;
2605 } else {
2606 Sd->mDstBase[Sd->mOutBuf++] = (UINT8) CharC;
2607 }
2608
2609 } else {
2610 //
2611 // Process a Pointer
2612 //
2613 CharC = (UINT16) (CharC - (UINT8_MAX + 1 - THRESHOLD));
2614
2615 BytesRemain = CharC;
2616
2617 DataIdx = Sd->mOutBuf - DecodeP (Sd) - 1;
2618
2619 BytesRemain--;
2620 while ((INT16) (BytesRemain) >= 0) {
2621 Sd->mDstBase[Sd->mOutBuf++] = Sd->mDstBase[DataIdx++];
2622 if (Sd->mOutBuf >= Sd->mOrigSize) {
2623 goto Done ;
2624 }
2625
2626 BytesRemain--;
2627 }
2628 }
2629 }
2630
2631 Done:
2632 return ;
2633 }
2634
2635 RETURN_STATUS
2636 EFIAPI
Decompress(IN VOID * Source,IN OUT VOID * Destination,IN OUT VOID * Scratch,IN UINT32 Version)2637 Decompress (
2638 IN VOID *Source,
2639 IN OUT VOID *Destination,
2640 IN OUT VOID *Scratch,
2641 IN UINT32 Version
2642 )
2643 /*++
2644
2645 Routine Description:
2646
2647 The internal implementation of Decompress().
2648
2649 Arguments:
2650
2651 Source - The source buffer containing the compressed data.
2652 Destination - The destination buffer to store the decompressed data
2653 Scratch - The buffer used internally by the decompress routine. This buffer is needed to store intermediate data.
2654 Version - 1 for EFI1.1 Decompress algoruthm, 2 for Tiano Decompress algorithm
2655
2656 Returns:
2657
2658 RETURN_SUCCESS - Decompression is successfull
2659 RETURN_INVALID_PARAMETER - The source data is corrupted
2660
2661 --*/
2662 {
2663 volatile UINT32 Index;
2664 UINT32 CompSize;
2665 UINT32 OrigSize;
2666 SCRATCH_DATA *Sd;
2667 CONST UINT8 *Src;
2668 UINT8 *Dst;
2669
2670 //
2671 // Verify input is not NULL
2672 //
2673 assert(Source);
2674 // assert(Destination);
2675 assert(Scratch);
2676
2677 Src = (UINT8 *)Source;
2678 Dst = (UINT8 *)Destination;
2679
2680 Sd = (SCRATCH_DATA *) Scratch;
2681 CompSize = Src[0] + (Src[1] << 8) + (Src[2] << 16) + (Src[3] << 24);
2682 OrigSize = Src[4] + (Src[5] << 8) + (Src[6] << 16) + (Src[7] << 24);
2683
2684 //
2685 // If compressed file size is 0, return
2686 //
2687 if (OrigSize == 0) {
2688 return RETURN_SUCCESS;
2689 }
2690
2691 Src = Src + 8;
2692
2693 for (Index = 0; Index < sizeof (SCRATCH_DATA); Index++) {
2694 ((UINT8 *) Sd)[Index] = 0;
2695 }
2696 //
2697 // The length of the field 'Position Set Code Length Array Size' in Block Header.
2698 // For EFI 1.1 de/compression algorithm(Version 1), mPBit = 4
2699 // For Tiano de/compression algorithm(Version 2), mPBit = 5
2700 //
2701 switch (Version) {
2702 case 1 :
2703 Sd->mPBit = 4;
2704 break;
2705 case 2 :
2706 Sd->mPBit = 5;
2707 break;
2708 default:
2709 assert(FALSE);
2710 }
2711 Sd->mSrcBase = (UINT8 *)Src;
2712 Sd->mDstBase = Dst;
2713 Sd->mCompSize = CompSize;
2714 Sd->mOrigSize = OrigSize;
2715
2716 //
2717 // Fill the first BITBUFSIZ bits
2718 //
2719 FillBuf (Sd, BITBUFSIZ);
2720
2721 //
2722 // Decompress it
2723 //
2724
2725 Decode (Sd);
2726
2727 if (Sd->mBadTableFlag != 0) {
2728 //
2729 // Something wrong with the source
2730 //
2731 return RETURN_INVALID_PARAMETER;
2732 }
2733
2734 return RETURN_SUCCESS;
2735 }
2736
2737
2738