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