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