enable -q/-v/-d interface for EfiRom, GenVtf and TianoCompress tool and use the commo...
[efi/basetools/.git] / Source / C / TianoCompress / TianoCompress.c
1 /*++\r
2 \r
3 Copyright (c) 2007, Intel Corporation                                              \r
4 All rights reserved. This program and the accompanying materials                          \r
5 are licensed and made available under the terms and conditions of the BSD License         \r
6 which accompanies this distribution.  The full text of the license may be found at        \r
7 http://opensource.org/licenses/bsd-license.php                                            \r
8                                                                                           \r
9 THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,                     \r
10 WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.             \r
11 \r
12 Module Name:\r
13 \r
14   TianoCompress.c\r
15 \r
16 Abstract:\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 <stdio.h>\r
29 #include "assert.h"\r
30 \r
31 //\r
32 // Macro Definitions\r
33 //\r
34 static BOOLEAN VerboseMode = FALSE;\r
35 static BOOLEAN QuietMode = FALSE;\r
36 #define UINT8_MAX     0xff\r
37 #define UINT8_BIT     8\r
38 #define THRESHOLD     3\r
39 #define INIT_CRC      0\r
40 #define WNDBIT        19\r
41 #define WNDSIZ        (1U << WNDBIT)\r
42 #define MAXMATCH      256\r
43 #define BLKSIZ        (1U << 14)  // 16 * 1024U\r
44 #define PERC_FLAG     0x80000000U\r
45 #define CODE_BIT      16\r
46 #define NIL           0\r
47 #define MAX_HASH_VAL  (3 * WNDSIZ + (WNDSIZ / 512 + 1) * UINT8_MAX)\r
48 #define HASH(p, c)    ((p) + ((c) << (WNDBIT - 9)) + WNDSIZ * 2)\r
49 #define CRCPOLY       0xA001\r
50 #define UPDATE_CRC(c) mCrc = mCrcTable[(mCrc ^ (c)) & 0xFF] ^ (mCrc >> UINT8_BIT)\r
51 \r
52 //\r
53 // C: the Char&Len Set; P: the Position Set; T: the exTra Set\r
54 //\r
55 //#define NC    (UINT8_MAX + MAXMATCH + 2 - THRESHOLD)\r
56 #define CBIT  9\r
57 #define NP    (WNDBIT + 1)\r
58 #define PBIT  5\r
59 //#define NT    (CODE_BIT + 3)\r
60 //#define TBIT  5\r
61 //#if NT > NP\r
62 //#define NPT NT\r
63 //#else\r
64 //#define NPT NP\r
65 //#endif\r
66 \r
67 //\r
68 //  Global Variables\r
69 //\r
70 STATIC BOOLEAN ENCODE = FALSE;\r
71 STATIC BOOLEAN DECODE = FALSE;\r
72 STATIC UINT8  *mSrc, *mDst, *mSrcUpperLimit, *mDstUpperLimit;\r
73 STATIC UINT8  *mLevel, *mText, *mChildCount, *mBuf, mCLen[NC], mPTLen[NPT], *mLen;\r
74 STATIC INT16  mHeap[NC + 1];\r
75 STATIC INT32  mRemainder, mMatchLen, mBitCount, mHeapSize, mN;\r
76 STATIC UINT32 mBufSiz = 0, mOutputPos, mOutputMask, mSubBitBuf, mCrc;\r
77 STATIC UINT32 mCompSize, mOrigSize;\r
78 \r
79 STATIC UINT16 *mFreq, *mSortPtr, mLenCnt[17], mLeft[2 * NC - 1], mRight[2 * NC - 1], mCrcTable[UINT8_MAX + 1],\r
80   mCFreq[2 * NC - 1], mCTable[4096], mCCode[NC], mPFreq[2 * NP - 1], mPTCode[NPT], mTFreq[2 * NT - 1];\r
81 \r
82 STATIC NODE   mPos, mMatchPos, mAvail, *mPosition, *mParent, *mPrev, *mNext = NULL;\r
83 \r
84 static  UINTN      DebugLevel;\r
85 static  BOOLEAN    DebugMode;\r
86 //\r
87 // functions\r
88 //\r
89 EFI_STATUS\r
90 TianoCompress (\r
91   IN      UINT8   *SrcBuffer,\r
92   IN      UINT32  SrcSize,\r
93   IN      UINT8   *DstBuffer,\r
94   IN OUT  UINT32  *DstSize\r
95   )\r
96 /*++\r
97 \r
98 Routine Description:\r
99 \r
100   The internal implementation of [Efi/Tiano]Compress().\r
101 \r
102 Arguments:\r
103 \r
104   SrcBuffer   - The buffer storing the source data\r
105   SrcSize     - The size of source data\r
106   DstBuffer   - The buffer to store the compressed data\r
107   \r
108   Version     - The version of de/compression algorithm.\r
109                 Version 1 for EFI 1.1 de/compression algorithm.\r
110                 Version 2 for Tiano de/compression algorithm.\r
111 \r
112 Returns:\r
113 \r
114   EFI_BUFFER_TOO_SMALL  - The DstBuffer is too small. In this case,\r
115                 DstSize contains the size needed.\r
116   EFI_SUCCESS           - Compression is successful.\r
117   EFI_OUT_OF_RESOURCES  - No resource to complete function.\r
118   EFI_INVALID_PARAMETER - Parameter supplied is wrong.\r
119 \r
120 --*/\r
121 {\r
122   EFI_STATUS  Status;\r
123 \r
124   //\r
125   // Initializations\r
126   //\r
127   mBufSiz         = 0;\r
128   mBuf            = NULL;\r
129   mText           = NULL;\r
130   mLevel          = NULL;\r
131   mChildCount     = NULL;\r
132   mPosition       = NULL;\r
133   mParent         = NULL;\r
134   mPrev           = NULL;\r
135   mNext           = NULL;\r
136 \r
137 \r
138   mSrc            = SrcBuffer;\r
139   mSrcUpperLimit  = mSrc + SrcSize;\r
140   mDst            = DstBuffer;\r
141   mDstUpperLimit  = mDst +*DstSize;\r
142     \r
143   PutDword (0L);\r
144   PutDword (0L);\r
145   \r
146   MakeCrcTable ();\r
147   \r
148   mOrigSize             = mCompSize = 0;\r
149   mCrc                  = INIT_CRC;\r
150 \r
151   //\r
152   // Compress it\r
153   //\r
154   Status = Encode ();\r
155   if (EFI_ERROR (Status)) {\r
156     return EFI_OUT_OF_RESOURCES;\r
157   }\r
158   \r
159   //\r
160   // Null terminate the compressed data\r
161   //\r
162 \r
163   if (mDst < mDstUpperLimit) {\r
164     *mDst++ = 0;\r
165   }\r
166 \r
167   //\r
168   // Fill in compressed size and original size\r
169   //\r
170   mDst = DstBuffer; \r
171  \r
172   PutDword (mCompSize + 1);\r
173   PutDword (mOrigSize);\r
174   //\r
175   // Return\r
176   //\r
177 \r
178   if (mCompSize + 1 + 8 > *DstSize) {\r
179     *DstSize = mCompSize + 1 + 8;    \r
180        return EFI_BUFFER_TOO_SMALL;\r
181     } else {\r
182     *DstSize = mCompSize + 1 + 8;   \r
183       return EFI_SUCCESS;\r
184    }\r
185   return EFI_SUCCESS;\r
186 }\r
187 \r
188 STATIC\r
189 VOID\r
190 PutDword (\r
191   IN UINT32 Data\r
192   )\r
193 /*++\r
194 \r
195 Routine Description:\r
196 \r
197   Put a dword to output stream\r
198   \r
199 Arguments:\r
200 \r
201   Data    - the dword to put\r
202   \r
203 Returns: (VOID)\r
204   \r
205 --*/\r
206 {\r
207   if (mDst < mDstUpperLimit) {\r
208     *mDst++ = (UINT8) (((UINT8) (Data)) & 0xff);\r
209   }\r
210 \r
211   if (mDst < mDstUpperLimit) {\r
212     *mDst++ = (UINT8) (((UINT8) (Data >> 0x08)) & 0xff);\r
213   }\r
214 \r
215   if (mDst < mDstUpperLimit) {\r
216     *mDst++ = (UINT8) (((UINT8) (Data >> 0x10)) & 0xff);\r
217   }\r
218 \r
219   if (mDst < mDstUpperLimit) {\r
220     *mDst++ = (UINT8) (((UINT8) (Data >> 0x18)) & 0xff);\r
221   }\r
222 }\r
223 \r
224 STATIC\r
225 EFI_STATUS\r
226 AllocateMemory (\r
227   VOID\r
228   )\r
229 /*++\r
230 \r
231 Routine Description:\r
232 \r
233   Allocate memory spaces for data structures used in compression process\r
234   \r
235 Argements: \r
236   VOID\r
237 \r
238 Returns:\r
239 \r
240   EFI_SUCCESS           - Memory is allocated successfully\r
241   EFI_OUT_OF_RESOURCES  - Allocation fails\r
242 \r
243 --*/\r
244 {\r
245   UINT32  Index;\r
246 \r
247   mText = malloc (WNDSIZ * 2 + MAXMATCH);\r
248   for (Index = 0; Index < WNDSIZ * 2 + MAXMATCH; Index++) {\r
249     mText[Index] = 0;\r
250   }\r
251 \r
252   mLevel      = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mLevel));\r
253   mChildCount = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mChildCount));\r
254   mPosition   = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mPosition));\r
255   mParent     = malloc (WNDSIZ * 2 * sizeof (*mParent));\r
256   mPrev       = malloc (WNDSIZ * 2 * sizeof (*mPrev));\r
257   mNext       = malloc ((MAX_HASH_VAL + 1) * sizeof (*mNext));\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
275 VOID\r
276 FreeMemory (\r
277   VOID\r
278   )\r
279 /*++\r
280 \r
281 Routine Description:\r
282 \r
283   Called when compression is completed to free memory previously allocated.\r
284   \r
285 Arguments: (VOID)\r
286 \r
287 Returns: (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
326 STATIC\r
327 VOID\r
328 InitSlide (\r
329   VOID\r
330   )\r
331 /*++\r
332 \r
333 Routine Description:\r
334 \r
335   Initialize String Info Log data structures\r
336   \r
337 Arguments: (VOID)\r
338 \r
339 Returns: (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
365 STATIC\r
366 NODE\r
367 Child (\r
368   IN NODE  NodeQ,\r
369   IN UINT8 CharC\r
370   )\r
371 /*++\r
372 \r
373 Routine Description:\r
374 \r
375   Find child node given the parent node and the edge character\r
376   \r
377 Arguments:\r
378 \r
379   NodeQ       - the parent node\r
380   CharC       - the edge character\r
381   \r
382 Returns:\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
402 STATIC\r
403 VOID\r
404 MakeChild (\r
405   IN NODE  Parent,\r
406   IN UINT8 CharC,\r
407   IN NODE  Child\r
408   )\r
409 /*++\r
410 \r
411 Routine Description:\r
412 \r
413   Create a new child for a given parent node.\r
414   \r
415 Arguments:\r
416 \r
417   Parent       - the parent node\r
418   CharC   - the edge character\r
419   Child       - the child node\r
420   \r
421 Returns: (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
438 STATIC\r
439 VOID\r
440 Split (\r
441   NODE Old\r
442   )\r
443 /*++\r
444 \r
445 Routine Description:\r
446 \r
447   Split a node.\r
448   \r
449 Arguments:\r
450 \r
451   Old     - the node to split\r
452   \r
453 Returns: (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
476 STATIC\r
477 VOID\r
478 InsertNode (\r
479   VOID\r
480   )\r
481 /*++\r
482 \r
483 Routine Description:\r
484 \r
485   Insert string info for current position into the String Info Log\r
486   \r
487 Arguments: (VOID)\r
488 \r
489 Returns: (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. Travese 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
608 STATIC\r
609 VOID\r
610 DeleteNode (\r
611   VOID\r
612   )\r
613 /*++\r
614 \r
615 Routine Description:\r
616 \r
617   Delete outdated string info. (The Usage of PERC_FLAG\r
618   ensures a clean deletion)\r
619   \r
620 Arguments: (VOID)\r
621 \r
622 Returns: (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
703 STATIC\r
704 VOID\r
705 GetNextMatch (\r
706   VOID\r
707   )\r
708 /*++\r
709 \r
710 Routine 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
715 Arguments: (VOID)\r
716 \r
717 Returns: (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
736 STATIC\r
737 EFI_STATUS\r
738 Encode (\r
739   VOID\r
740   )\r
741 /*++\r
742 \r
743 Routine Description:\r
744 \r
745   The main controlling routine for compression process.\r
746 \r
747 Arguments: (VOID)\r
748 \r
749 Returns:\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
826 STATIC\r
827 VOID\r
828 CountTFreq (\r
829   VOID\r
830   )\r
831 /*++\r
832 \r
833 Routine Description:\r
834 \r
835   Count the frequencies for the Extra Set\r
836   \r
837 Arguments: (VOID)\r
838 \r
839 Returns: (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
883 STATIC\r
884 VOID\r
885 WritePTLen (\r
886   IN INT32 Number,\r
887   IN INT32 nbit,\r
888   IN INT32 Special\r
889   )\r
890 /*++\r
891 \r
892 Routine Description:\r
893 \r
894   Outputs the code length array for the Extra Set or the Position Set.\r
895   \r
896 Arguments:\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
902 Returns: (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
933 STATIC\r
934 VOID\r
935 WriteCLen (\r
936   VOID\r
937   )\r
938 /*++\r
939 \r
940 Routine Description:\r
941 \r
942   Outputs the code length array for Char&Length Set\r
943   \r
944 Arguments: (VOID)\r
945 \r
946 Returns: (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
992 STATIC\r
993 VOID\r
994 EncodeC (\r
995   IN INT32 Value\r
996   )\r
997 {\r
998   PutBits (mCLen[Value], mCCode[Value]);\r
999 }\r
1000 \r
1001 STATIC\r
1002 VOID\r
1003 EncodeP (\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
1023 STATIC\r
1024 VOID\r
1025 SendBlock (\r
1026   VOID\r
1027   )\r
1028 /*++\r
1029 \r
1030 Routine Description:\r
1031 \r
1032   Huffman code the block and output it.\r
1033   \r
1034 Arguments: \r
1035   (VOID)\r
1036 \r
1037 Returns: \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
1112 STATIC\r
1113 VOID\r
1114 Output (\r
1115   IN UINT32 CharC,\r
1116   IN UINT32 Pos\r
1117   )\r
1118 /*++\r
1119 \r
1120 Routine Description:\r
1121 \r
1122   Outputs an Original Character or a Pointer\r
1123 \r
1124 Arguments:\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
1129 Returns: (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
1169 STATIC\r
1170 VOID\r
1171 HufEncodeStart (\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
1190 STATIC\r
1191 VOID\r
1192 HufEncodeEnd (\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
1206 STATIC\r
1207 VOID\r
1208 MakeCrcTable (\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
1230 STATIC\r
1231 VOID\r
1232 PutBits (\r
1233   IN INT32  Number,\r
1234   IN UINT32 Value\r
1235   )\r
1236 /*++\r
1237 \r
1238 Routine Description:\r
1239 \r
1240   Outputs rightmost n bits of x\r
1241 \r
1242 Arguments:\r
1243 \r
1244   Number   - the rightmost n bits of the data is used\r
1245   x   - the data \r
1246 \r
1247 Returns: (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
1271 STATIC\r
1272 INT32\r
1273 FreadCrc (\r
1274   OUT UINT8 *Pointer,\r
1275   IN  INT32 Number\r
1276   )\r
1277 /*++\r
1278 \r
1279 Routine Description:\r
1280 \r
1281   Read in source data\r
1282   \r
1283 Arguments:\r
1284 \r
1285   Pointer   - the buffer to hold the data\r
1286   Number   - number of bytes to read\r
1287 \r
1288 Returns:\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
1314 STATIC\r
1315 VOID\r
1316 InitPutBits (\r
1317   VOID\r
1318   )\r
1319 {\r
1320   mBitCount   = UINT8_BIT;\r
1321   mSubBitBuf  = 0;\r
1322 }\r
1323 \r
1324 STATIC\r
1325 VOID\r
1326 CountLen (\r
1327   IN INT32 Index\r
1328   )\r
1329 /*++\r
1330 \r
1331 Routine Description:\r
1332 \r
1333   Count the number of each code length for a Huffman tree.\r
1334   \r
1335 Arguments:\r
1336 \r
1337   Index   - the top node\r
1338   \r
1339 Returns: (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
1355 STATIC\r
1356 VOID\r
1357 MakeLen (\r
1358   IN INT32 Root\r
1359   )\r
1360 /*++\r
1361 \r
1362 Routine Description:\r
1363 \r
1364   Create code length array for a Huffman tree\r
1365   \r
1366 Arguments:\r
1367 \r
1368   Root   - the root of the tree\r
1369   \r
1370 Returns:\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
1418 STATIC\r
1419 VOID\r
1420 DownHeap (\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
1449 STATIC\r
1450 VOID\r
1451 MakeCode (\r
1452   IN  INT32       Number,\r
1453   IN  UINT8 Len[  ],\r
1454   OUT UINT16 Code[]\r
1455   )\r
1456 /*++\r
1457 \r
1458 Routine Description:\r
1459 \r
1460   Assign code to each symbol based on the code length array\r
1461   \r
1462 Arguments:\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
1468 Returns: (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
1485 STATIC\r
1486 INT32\r
1487 MakeTree (\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
1495 Routine Description:\r
1496 \r
1497   Generates Huffman codes given a frequency distribution of symbols\r
1498   \r
1499 Arguments:\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
1506 Returns:\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
1578 EFI_STATUS\r
1579 GetFileContents (\r
1580   IN char    *InputFileName,\r
1581   OUT UINT8   *FileBuffer,\r
1582   OUT UINT32  *BufferLength\r
1583   )\r
1584 /*++\r
1585         \r
1586 Routine Description:\r
1587            \r
1588   Get the contents of file specified in InputFileName\r
1589   into FileBuffer.\r
1590             \r
1591 Arguments:\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
1599 Returns:\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   INTN    Index;\r
1609   FILE    *InputFile;\r
1610 \r
1611   Size = 0;\r
1612   //\r
1613   // Copy the file contents to the output buffer.\r
1614   //\r
1615   InputFile = fopen (InputFileName, "rb");\r
1616     if (InputFile == NULL) {\r
1617       Error(NULL, 0, 0001, "Error opening file: %s", InputFileName);\r
1618       return EFI_ABORTED;\r
1619     }\r
1620   \r
1621   fseek (InputFile, 0, SEEK_END);\r
1622   FileSize = ftell (InputFile);\r
1623   fseek (InputFile, 0, SEEK_SET);\r
1624     //\r
1625     // Now read the contents of the file into the buffer\r
1626     // \r
1627     if (FileSize > 0 && FileBuffer != NULL) {\r
1628       if (fread (FileBuffer, FileSize, 1, InputFile) != 1) {\r
1629         Error(NULL, 0, 0004, "Error reading contents of input file: %s", InputFileName);\r
1630         fclose (InputFile);\r
1631         return EFI_ABORTED;\r
1632       }\r
1633     }\r
1634 \r
1635   fclose (InputFile);\r
1636   Size += (UINTN) FileSize;\r
1637   *BufferLength = Size;\r
1638   \r
1639   if (FileBuffer != NULL) {\r
1640     return EFI_SUCCESS;\r
1641   } else {\r
1642     return EFI_BUFFER_TOO_SMALL;\r
1643   }\r
1644 }\r
1645 \r
1646 VOID\r
1647 Version (\r
1648   VOID\r
1649   )\r
1650 /*++\r
1651 \r
1652 Routine Description:\r
1653 \r
1654   Displays the standard utility information to SDTOUT\r
1655 \r
1656 Arguments:\r
1657 \r
1658   None\r
1659 \r
1660 Returns:\r
1661 \r
1662   None\r
1663 \r
1664 --*/\r
1665 {\r
1666   fprintf (stdout, "%s Version %d.%d\n", UTILITY_NAME, UTILITY_MAJOR_VERSION, UTILITY_MINOR_VERSION);\r
1667 }\r
1668 \r
1669 VOID\r
1670 Usage (\r
1671   VOID\r
1672   )\r
1673 /*++\r
1674 \r
1675 Routine Description:\r
1676 \r
1677   Displays the utility usage syntax to STDOUT\r
1678 \r
1679 Arguments:\r
1680 \r
1681   None\r
1682 \r
1683 Returns:\r
1684 \r
1685   None\r
1686 \r
1687 --*/\r
1688 {\r
1689   //\r
1690   // Summary usage\r
1691   //\r
1692   fprintf (stdout, "Usage: %s -e|-d [options] <input_file>\n\n", UTILITY_NAME);\r
1693   \r
1694   //\r
1695   // Copyright declaration\r
1696   // \r
1697   fprintf (stdout, "Copyright (c) 2007, Intel Corporation. All rights reserved.\n\n");\r
1698 \r
1699   //\r
1700   // Details Option\r
1701   //\r
1702   fprintf (stdout, "Options:\n");\r
1703   fprintf (stdout, "  -o FileName, --output FileName\n\\r
1704             File will be created to store the ouput content.\n");\r
1705   fprintf (stdout, "  -v, --verbose\n\\r
1706             Turn on verbose output with informational messages.\n");\r
1707   fprintf (stdout, "  --version\n\\r
1708             Show program's version number and exit.\n");\r
1709   fprintf (stdout, "  -h, --help\n\\r
1710             Show this help message and exit.\n");\r
1711   fprintf (stdout, "  -q, --quiet\n\\r
1712          Disable all messages except FATAL ERRORS.\n");\r
1713   fprintf (stdout, "  -d, --debug [#,0-9]\n\\r
1714          Enable debug messages at level #.\n");  \r
1715 }\r
1716 \r
1717 \r
1718 int\r
1719 main (\r
1720   int  argc,\r
1721   char *argv[]\r
1722   )\r
1723 /*++\r
1724 \r
1725 Routine Description:\r
1726 \r
1727   Main\r
1728 \r
1729 Arguments:\r
1730 \r
1731   command line parameters\r
1732 \r
1733 Returns:\r
1734 \r
1735   EFI_SUCCESS    Section header successfully generated and section concatenated.\r
1736   EFI_ABORTED    Could not generate the section\r
1737   EFI_OUT_OF_RESOURCES  No resource to complete the operation.\r
1738 \r
1739 --*/  \r
1740 {\r
1741   FILE       *OutputFile;\r
1742   char       *OutputFileName;\r
1743   char       *InputFileName;\r
1744   FILE       *InputFile;\r
1745   EFI_STATUS Status;\r
1746   UINT8      *FileBuffer;\r
1747   UINT8      *OutBuffer;\r
1748   UINT32     InputLength;\r
1749   UINT32     DstSize;\r
1750   SCRATCH_DATA      *Scratch;\r
1751   UINT8      *Src;\r
1752   UINT32     OrigSize;\r
1753 \r
1754   SetUtilityName(UTILITY_NAME);\r
1755   \r
1756   FileBuffer = NULL;\r
1757   Src = NULL;\r
1758   OutBuffer = NULL;\r
1759   OrigSize = 0;\r
1760   InputLength = 0;\r
1761   InputFileName = NULL;\r
1762   OutputFileName = NULL;\r
1763   DstSize=0;\r
1764   DebugLevel = 0;\r
1765   DebugMode = FALSE;\r
1766 \r
1767   //\r
1768   // Verify the correct number of arguments\r
1769   //\r
1770   if (argc == 1) {\r
1771     Usage();\r
1772     return 0;\r
1773   }\r
1774   \r
1775   if ((strcmp(argv[1], "-h") == 0) || (strcmp(argv[1], "--help") == 0) || \r
1776       (strcmp(argv[1], "-?") == 0) || (strcmp(argv[1], "/?") == 0)) {\r
1777     Usage();\r
1778     return 0;\r
1779   }\r
1780   \r
1781   if ( (strcmp(argv[1], "--version") == 0)) {\r
1782     Version();\r
1783     return 0;\r
1784   }\r
1785 \r
1786   argc--;\r
1787   argv++;\r
1788   if (strcmp(argv[0],"-e") == 0) {\r
1789   //\r
1790   // encode the input file\r
1791   //\r
1792   ENCODE = TRUE;\r
1793   argc--;\r
1794   argv++;\r
1795   }\r
1796   else if (strcmp(argv[0], "-d") == 0) {\r
1797   //\r
1798   // decode the input file\r
1799   //\r
1800   DECODE = TRUE;\r
1801   argc--;\r
1802   argv++;\r
1803   }\r
1804   else {\r
1805   //\r
1806   // Error command line\r
1807   //\r
1808   Usage();\r
1809   return 1;\r
1810   }\r
1811 \r
1812   while (argc > 0) {\r
1813    if ((strcmp(argv[0], "-v") == 0) || (stricmp(argv[0], "--verbose") == 0)) {\r
1814     VerboseMode = TRUE;\r
1815     argc--;\r
1816     argv++;\r
1817     continue;\r
1818   }\r
1819    if ((stricmp (argv[0], "-d") == 0) || (stricmp (argv[0], "--debug") == 0)) {\r
1820      argc-=2;\r
1821      argv++;\r
1822      Status = AsciiStringToUint64(argv[0], FALSE, &DebugLevel);\r
1823      if (DebugLevel > 9 || DebugLevel < 0) {\r
1824        Error(NULL, 0 ,2000, "Invalid parameter", "Unrecognized argument %s", argv[0]);\r
1825        goto ERROR;\r
1826      }\r
1827      if (DebugLevel>=5 && DebugLevel <=9){\r
1828        DebugMode = TRUE;\r
1829      } else {\r
1830        DebugMode = FALSE;\r
1831      }\r
1832      argv++;\r
1833      continue;\r
1834    }\r
1835    if ((strcmp(argv[0], "-q") == 0) || (stricmp (argv[0], "--debug") == 0)) {\r
1836      QuietMode = TRUE;\r
1837      argc--;\r
1838      argv++;\r
1839      continue;\r
1840    }\r
1841    if ((strcmp(argv[0], "-o") == 0) || (stricmp (argv[0], "--output") == 0)) {\r
1842     argc-=2;\r
1843     argv++;\r
1844     OutputFileName = argv[0];\r
1845     argv++;\r
1846     continue; \r
1847     }\r
1848    if (argv[0][0]!='-') {\r
1849    InputFileName = argv[0];\r
1850    argc--;\r
1851    argv++;\r
1852    continue;\r
1853    }\r
1854     Error (NULL, 0, 1000, "Unknown option", argv[0]);\r
1855     goto ERROR;     \r
1856   }\r
1857 \r
1858   if (InputFileName == NULL) {\r
1859     Error(NULL, 0, 2000, " Invalid parameter");\r
1860     Usage();\r
1861     return 1;    \r
1862   }\r
1863 \r
1864 //\r
1865 // All Parameters has been parsed, now set the message print level\r
1866 //\r
1867   if (QuietMode) {\r
1868     SetPrintLevel(40);\r
1869   } else if (VerboseMode) {\r
1870     SetPrintLevel(15);\r
1871   } else if (DebugMode) {\r
1872     SetPrintLevel(DebugLevel);\r
1873   }\r
1874   \r
1875   if (VerboseMode) {\r
1876     VerboseMsg("%s tool start.\n", UTILITY_NAME);\r
1877    }\r
1878   Scratch = (SCRATCH_DATA *)malloc(sizeof(SCRATCH_DATA));\r
1879   if (Scratch == NULL) {\r
1880     Error(NULL, 0, 4001, "Resource:", "Memory cannot be allocated!");\r
1881     goto ERROR;\r
1882   }\r
1883     \r
1884   InputFile = fopen (InputFileName, "rb");\r
1885   if (InputFile == NULL) {\r
1886     Error(NULL, 0, 0001, "Error opening input file", InputFileName);\r
1887     goto ERROR;\r
1888   }\r
1889         \r
1890   Status = GetFileContents(\r
1891             InputFileName,\r
1892             FileBuffer,\r
1893             &InputLength);\r
1894 \r
1895   if (Status == EFI_BUFFER_TOO_SMALL) {\r
1896     FileBuffer = (UINT8 *) malloc (InputLength);\r
1897     if (FileBuffer == NULL) {\r
1898       Error(NULL, 0, 4001, "Resource:", "Memory cannot be allocated!");\r
1899       return EFI_OUT_OF_RESOURCES;\r
1900     }\r
1901 \r
1902     Status = GetFileContents (\r
1903               InputFileName,\r
1904               FileBuffer,\r
1905               &InputLength\r
1906               );\r
1907   }\r
1908 \r
1909   if (EFI_ERROR(Status)) {\r
1910     free(FileBuffer);\r
1911     return 1;\r
1912   }\r
1913    \r
1914   if (OutputFileName != NULL) {\r
1915     OutputFile = fopen (OutputFileName, "wb");\r
1916     if (OutputFile == NULL) {\r
1917       Error(NULL, 0, 0001, "Error opening output file for writing", OutputFileName);\r
1918     if (InputFile != NULL) {\r
1919       fclose (InputFile);\r
1920       }\r
1921       goto ERROR;\r
1922       }\r
1923     } else {\r
1924       OutputFileName = DEFAULT_OUTPUT_FILE;\r
1925       OutputFile = fopen (OutputFileName, "wb");\r
1926     }\r
1927     \r
1928   if (ENCODE) {\r
1929   //\r
1930   // First call TianoCompress to get DstSize\r
1931   //\r
1932   if (DebugMode) {\r
1933     DebugMsg(UTILITY_NAME, 0, DebugLevel, "Encoding");\r
1934   }\r
1935   Status = TianoCompress ((UINT8 *)FileBuffer, InputLength, OutBuffer, &DstSize);\r
1936   \r
1937   if (Status == EFI_BUFFER_TOO_SMALL) {\r
1938     OutBuffer = (UINT8 *) malloc (DstSize);\r
1939     if (OutBuffer == NULL) {\r
1940       Error(NULL, 0, 4001, "Resource:", "Memory cannot be allocated!");\r
1941       goto ERROR;\r
1942     }\r
1943   }\r
1944   Status = TianoCompress ((UINT8 *)FileBuffer, InputLength, OutBuffer, &DstSize);\r
1945   if (Status != EFI_SUCCESS) {\r
1946     Error(NULL, 0, 0007, "Error compressing file");\r
1947     goto ERROR;\r
1948   }\r
1949 \r
1950   fwrite(OutBuffer,(size_t)DstSize, 1, OutputFile);\r
1951   free(Scratch);\r
1952   free(FileBuffer);\r
1953   free(OutBuffer);\r
1954 \r
1955   if (DebugMode) {\r
1956     DebugMsg(UTILITY_NAME, 0, DebugLevel, "Encoding Successful!\n");\r
1957   }\r
1958   if (VerboseMode) {\r
1959     VerboseMsg("Encoding successful\n");\r
1960   }\r
1961   return 0;  \r
1962   }\r
1963   else if (DECODE) {\r
1964   if (DebugMode) {\r
1965     DebugMsg(UTILITY_NAME, 0, DebugLevel, "Decoding\n");\r
1966   }\r
1967   //\r
1968   // Get Compressed file original size\r
1969   // \r
1970   Src     = (UINT8 *)FileBuffer;                     \r
1971   OrigSize  = Src[4] + (Src[5] << 8) + (Src[6] << 16) + (Src[7] << 24);  \r
1972   \r
1973   //\r
1974   // Allocate OutputBuffer\r
1975   //\r
1976   OutBuffer = (UINT8 *)malloc(OrigSize);\r
1977   if (OutBuffer == NULL) {\r
1978     Error(NULL, 0, 4001, "Resource:", "Memory cannot be allocated!");\r
1979     goto ERROR;\r
1980    }  \r
1981 \r
1982   Status = Decompress((VOID *)FileBuffer, (VOID *)OutBuffer, (VOID *)Scratch, 2);\r
1983   if (Status != EFI_SUCCESS) {\r
1984    goto ERROR;  \r
1985   }\r
1986 \r
1987   fwrite(OutBuffer, (size_t)(Scratch->mOrigSize), 1, OutputFile);\r
1988   free(Scratch);\r
1989   free(FileBuffer);\r
1990   free(OutBuffer);\r
1991 \r
1992   if (DebugMode) {\r
1993     DebugMsg(UTILITY_NAME, 0, DebugLevel, "Encoding successful!\n");\r
1994   }\r
1995   \r
1996   if (VerboseMode) {\r
1997     VerboseMsg("Decoding successful\n");\r
1998   }\r
1999   return 0;\r
2000   }\r
2001   \r
2002 ERROR:\r
2003   if (DebugMode) {\r
2004     if (ENCODE) {\r
2005       DebugMsg(UTILITY_NAME, 0, DebugLevel, "Encoding Error\n");\r
2006     } else if (DECODE) {\r
2007       DebugMsg(UTILITY_NAME, 0, DebugLevel, "Decoding Error\n");\r
2008     }\r
2009   }\r
2010   free(Scratch);\r
2011   free(FileBuffer);\r
2012   free(OutBuffer);\r
2013   if (VerboseMode) {\r
2014     VerboseMsg("%s tool done with return code is 0x%x.\n", UTILITY_NAME, GetUtilityStatus ());\r
2015   }\r
2016   return GetUtilityStatus ();\r
2017 }\r
2018 \r
2019 VOID\r
2020 FillBuf (\r
2021   IN  SCRATCH_DATA  *Sd,\r
2022   IN  UINT16        NumOfBits\r
2023   )\r
2024 /*++\r
2025 \r
2026 Routine Description:\r
2027 \r
2028   Shift mBitBuf NumOfBits left. Read in NumOfBits of bits from source.\r
2029 \r
2030 Arguments:\r
2031 \r
2032   Sd        - The global scratch data\r
2033   NumOfBits  - The number of bits to shift and read.\r
2034 \r
2035 Returns: (VOID)\r
2036 \r
2037 --*/\r
2038 {\r
2039   Sd->mBitBuf = (UINT32) (Sd->mBitBuf << NumOfBits);\r
2040 \r
2041   while (NumOfBits > Sd->mBitCount) {\r
2042 \r
2043     Sd->mBitBuf |= (UINT32) (Sd->mSubBitBuf << (NumOfBits = (UINT16) (NumOfBits - Sd->mBitCount)));\r
2044 \r
2045     if (Sd->mCompSize > 0) {\r
2046       //\r
2047       // Get 1 byte into SubBitBuf\r
2048       //\r
2049       Sd->mCompSize--;\r
2050       Sd->mSubBitBuf  = 0;\r
2051       Sd->mSubBitBuf  = Sd->mSrcBase[Sd->mInBuf++];\r
2052       Sd->mBitCount   = 8;\r
2053 \r
2054     } else {\r
2055       //\r
2056       // No more bits from the source, just pad zero bit.\r
2057       //\r
2058       Sd->mSubBitBuf  = 0;\r
2059       Sd->mBitCount   = 8;\r
2060 \r
2061     }\r
2062   }\r
2063 \r
2064   Sd->mBitCount = (UINT16) (Sd->mBitCount - NumOfBits);\r
2065   Sd->mBitBuf |= Sd->mSubBitBuf >> Sd->mBitCount;\r
2066 }\r
2067 \r
2068 UINT32\r
2069 GetBits (\r
2070   IN  SCRATCH_DATA  *Sd,\r
2071   IN  UINT16        NumOfBits\r
2072   )\r
2073 /*++\r
2074 \r
2075 Routine Description:\r
2076 \r
2077   Get NumOfBits of bits out from mBitBuf. Fill mBitBuf with subsequent \r
2078   NumOfBits of bits from source. Returns NumOfBits of bits that are \r
2079   popped out.\r
2080 \r
2081 Arguments:\r
2082 \r
2083   Sd            - The global scratch data.\r
2084   NumOfBits     - The number of bits to pop and read.\r
2085 \r
2086 Returns:\r
2087 \r
2088   The bits that are popped out.\r
2089 \r
2090 --*/\r
2091 {\r
2092   UINT32  OutBits;\r
2093 \r
2094   OutBits = (UINT32) (Sd->mBitBuf >> (BITBUFSIZ - NumOfBits));\r
2095 \r
2096   FillBuf (Sd, NumOfBits);\r
2097 \r
2098   return OutBits;\r
2099 }\r
2100 \r
2101 UINT16\r
2102 MakeTable (\r
2103   IN  SCRATCH_DATA  *Sd,\r
2104   IN  UINT16        NumOfChar,\r
2105   IN  UINT8         *BitLen,\r
2106   IN  UINT16        TableBits,\r
2107   OUT UINT16        *Table\r
2108   )\r
2109 /*++\r
2110 \r
2111 Routine Description:\r
2112 \r
2113   Creates Huffman Code mapping table according to code length array.\r
2114 \r
2115 Arguments:\r
2116 \r
2117   Sd        - The global scratch data\r
2118   NumOfChar - Number of symbols in the symbol set\r
2119   BitLen    - Code length array\r
2120   TableBits - The width of the mapping table\r
2121   Table     - The table\r
2122   \r
2123 Returns:\r
2124   \r
2125   0         - OK.\r
2126   BAD_TABLE - The table is corrupted.\r
2127 \r
2128 --*/\r
2129 {\r
2130   UINT16  Count[17];\r
2131   UINT16  Weight[17];\r
2132   UINT16  Start[18];\r
2133   UINT16  *Pointer;\r
2134   UINT16  Index3;\r
2135   volatile UINT16  Index;\r
2136   UINT16  Len;\r
2137   UINT16  Char;\r
2138   UINT16  JuBits;\r
2139   UINT16  Avail;\r
2140   UINT16  NextCode;\r
2141   UINT16  Mask;\r
2142   UINT16  WordOfStart;\r
2143   UINT16  WordOfCount;\r
2144 \r
2145   for (Index = 1; Index <= 16; Index++) {\r
2146     Count[Index] = 0;\r
2147   }\r
2148 \r
2149   for (Index = 0; Index < NumOfChar; Index++) {\r
2150     Count[BitLen[Index]]++;\r
2151   }\r
2152 \r
2153   Start[1] = 0;\r
2154 \r
2155   for (Index = 1; Index <= 16; Index++) {\r
2156     WordOfStart = Start[Index];\r
2157     WordOfCount = Count[Index];\r
2158     Start[Index + 1] = (UINT16) (WordOfStart + (WordOfCount << (16 - Index)));\r
2159   }\r
2160 \r
2161   if (Start[17] != 0) {\r
2162     //\r
2163     //(1U << 16)\r
2164     //\r
2165     return (UINT16) BAD_TABLE;\r
2166   }\r
2167 \r
2168   JuBits = (UINT16) (16 - TableBits);\r
2169 \r
2170   for (Index = 1; Index <= TableBits; Index++) {\r
2171     Start[Index] >>= JuBits;\r
2172     Weight[Index] = (UINT16) (1U << (TableBits - Index));\r
2173   }\r
2174 \r
2175   while (Index <= 16) {\r
2176     Weight[Index] = (UINT16) (1U << (16 - Index));\r
2177     Index++;\r
2178   }\r
2179 \r
2180   Index = (UINT16) (Start[TableBits + 1] >> JuBits);\r
2181 \r
2182   if (Index != 0) {\r
2183     Index3 = (UINT16) (1U << TableBits);\r
2184     while (Index != Index3) {\r
2185       Table[Index++] = 0;\r
2186     }\r
2187   }\r
2188 \r
2189   Avail = NumOfChar;\r
2190   Mask  = (UINT16) (1U << (15 - TableBits));\r
2191 \r
2192   for (Char = 0; Char < NumOfChar; Char++) {\r
2193 \r
2194     Len = BitLen[Char];\r
2195     if (Len == 0) {\r
2196       continue;\r
2197     }\r
2198 \r
2199     NextCode = (UINT16) (Start[Len] + Weight[Len]);\r
2200 \r
2201     if (Len <= TableBits) {\r
2202 \r
2203       for (Index = Start[Len]; Index < NextCode; Index++) {\r
2204         Table[Index] = Char;\r
2205       }\r
2206 \r
2207     } else {\r
2208 \r
2209       Index3  = Start[Len];\r
2210       Pointer = &Table[Index3 >> JuBits];\r
2211       Index   = (UINT16) (Len - TableBits);\r
2212 \r
2213       while (Index != 0) {\r
2214         if (*Pointer == 0) {\r
2215           Sd->mRight[Avail]                     = Sd->mLeft[Avail] = 0;\r
2216           *Pointer = Avail++;\r
2217         }\r
2218 \r
2219         if (Index3 & Mask) {\r
2220           Pointer = &Sd->mRight[*Pointer];\r
2221         } else {\r
2222           Pointer = &Sd->mLeft[*Pointer];\r
2223         }\r
2224 \r
2225         Index3 <<= 1;\r
2226         Index--;\r
2227       }\r
2228 \r
2229       *Pointer = Char;\r
2230 \r
2231     }\r
2232 \r
2233     Start[Len] = NextCode;\r
2234   }\r
2235   //\r
2236   // Succeeds\r
2237   //\r
2238   return 0;\r
2239 }\r
2240 \r
2241 UINT32\r
2242 DecodeP (\r
2243   IN  SCRATCH_DATA  *Sd\r
2244   )\r
2245 /*++\r
2246 \r
2247 Routine Description:\r
2248 \r
2249   Decodes a position value.\r
2250 \r
2251 Arguments:\r
2252 \r
2253   Sd      - the global scratch data\r
2254 \r
2255 Returns:\r
2256 \r
2257   The position value decoded.\r
2258 \r
2259 --*/\r
2260 {\r
2261   UINT16  Val;\r
2262   UINT32  Mask;\r
2263   UINT32  Pos;\r
2264 \r
2265   Val = Sd->mPTTable[Sd->mBitBuf >> (BITBUFSIZ - 8)];\r
2266 \r
2267   if (Val >= MAXNP) {\r
2268     Mask = 1U << (BITBUFSIZ - 1 - 8);\r
2269 \r
2270     do {\r
2271 \r
2272       if (Sd->mBitBuf & Mask) {\r
2273         Val = Sd->mRight[Val];\r
2274       } else {\r
2275         Val = Sd->mLeft[Val];\r
2276       }\r
2277 \r
2278       Mask >>= 1;\r
2279     } while (Val >= MAXNP);\r
2280   }\r
2281   //\r
2282   // Advance what we have read\r
2283   //\r
2284   FillBuf (Sd, Sd->mPTLen[Val]);\r
2285 \r
2286   Pos = Val;\r
2287   if (Val > 1) {\r
2288     Pos = (UINT32) ((1U << (Val - 1)) + GetBits (Sd, (UINT16) (Val - 1)));\r
2289   }\r
2290 \r
2291   return Pos;\r
2292 }\r
2293 \r
2294 UINT16\r
2295 ReadPTLen (\r
2296   IN  SCRATCH_DATA  *Sd,\r
2297   IN  UINT16        nn,\r
2298   IN  UINT16        nbit,\r
2299   IN  UINT16        Special\r
2300   )\r
2301 /*++\r
2302 \r
2303 Routine Description:\r
2304 \r
2305   Reads code lengths for the Extra Set or the Position Set\r
2306 \r
2307 Arguments:\r
2308 \r
2309   Sd        - The global scratch data\r
2310   nn        - Number of symbols\r
2311   nbit      - Number of bits needed to represent nn\r
2312   Special   - The special symbol that needs to be taken care of \r
2313 \r
2314 Returns:\r
2315 \r
2316   0         - OK.\r
2317   BAD_TABLE - Table is corrupted.\r
2318 \r
2319 --*/\r
2320 {\r
2321   UINT16  Number;\r
2322   UINT16  CharC;\r
2323   volatile UINT16  Index;\r
2324   UINT32  Mask;\r
2325 \r
2326   Number = (UINT16) GetBits (Sd, nbit);\r
2327 \r
2328   if (Number == 0) {\r
2329     CharC = (UINT16) GetBits (Sd, nbit);\r
2330 \r
2331     for (Index = 0; Index < 256; Index++) {\r
2332       Sd->mPTTable[Index] = CharC;\r
2333     }\r
2334 \r
2335     for (Index = 0; Index < nn; Index++) {\r
2336       Sd->mPTLen[Index] = 0;\r
2337     }\r
2338 \r
2339     return 0;\r
2340   }\r
2341 \r
2342   Index = 0;\r
2343 \r
2344   while (Index < Number) {\r
2345 \r
2346     CharC = (UINT16) (Sd->mBitBuf >> (BITBUFSIZ - 3));\r
2347 \r
2348     if (CharC == 7) {\r
2349       Mask = 1U << (BITBUFSIZ - 1 - 3);\r
2350       while (Mask & Sd->mBitBuf) {\r
2351         Mask >>= 1;\r
2352         CharC += 1;\r
2353       }\r
2354     }\r
2355 \r
2356     FillBuf (Sd, (UINT16) ((CharC < 7) ? 3 : CharC - 3));\r
2357 \r
2358     Sd->mPTLen[Index++] = (UINT8) CharC;\r
2359 \r
2360     if (Index == Special) {\r
2361       CharC = (UINT16) GetBits (Sd, 2);\r
2362       while ((INT16) (--CharC) >= 0) {\r
2363         Sd->mPTLen[Index++] = 0;\r
2364       }\r
2365     }\r
2366   }\r
2367 \r
2368   while (Index < nn) {\r
2369     Sd->mPTLen[Index++] = 0;\r
2370   }\r
2371 \r
2372   return MakeTable (Sd, nn, Sd->mPTLen, 8, Sd->mPTTable);\r
2373 }\r
2374 \r
2375 VOID\r
2376 ReadCLen (\r
2377   SCRATCH_DATA  *Sd\r
2378   )\r
2379 /*++\r
2380 \r
2381 Routine Description:\r
2382 \r
2383   Reads code lengths for Char&Len Set.\r
2384 \r
2385 Arguments:\r
2386 \r
2387   Sd    - the global scratch data\r
2388 \r
2389 Returns: (VOID)\r
2390 \r
2391 --*/\r
2392 {\r
2393   UINT16  Number;\r
2394   UINT16  CharC;\r
2395   volatile UINT16  Index;\r
2396   UINT32  Mask;\r
2397 \r
2398   Number = (UINT16) GetBits (Sd, CBIT);\r
2399 \r
2400   if (Number == 0) {\r
2401     CharC = (UINT16) GetBits (Sd, CBIT);\r
2402 \r
2403     for (Index = 0; Index < NC; Index++) {\r
2404       Sd->mCLen[Index] = 0;\r
2405     }\r
2406 \r
2407     for (Index = 0; Index < 4096; Index++) {\r
2408       Sd->mCTable[Index] = CharC;\r
2409     }\r
2410 \r
2411     return ;\r
2412   }\r
2413 \r
2414   Index = 0;\r
2415   while (Index < Number) {\r
2416 \r
2417     CharC = Sd->mPTTable[Sd->mBitBuf >> (BITBUFSIZ - 8)];\r
2418     if (CharC >= NT) {\r
2419       Mask = 1U << (BITBUFSIZ - 1 - 8);\r
2420 \r
2421       do {\r
2422 \r
2423         if (Mask & Sd->mBitBuf) {\r
2424           CharC = Sd->mRight[CharC];\r
2425         } else {\r
2426           CharC = Sd->mLeft[CharC];\r
2427         }\r
2428 \r
2429         Mask >>= 1;\r
2430 \r
2431       } while (CharC >= NT);\r
2432     }\r
2433     //\r
2434     // Advance what we have read\r
2435     //\r
2436     FillBuf (Sd, Sd->mPTLen[CharC]);\r
2437 \r
2438     if (CharC <= 2) {\r
2439 \r
2440       if (CharC == 0) {\r
2441         CharC = 1;\r
2442       } else if (CharC == 1) {\r
2443         CharC = (UINT16) (GetBits (Sd, 4) + 3);\r
2444       } else if (CharC == 2) {\r
2445         CharC = (UINT16) (GetBits (Sd, CBIT) + 20);\r
2446       }\r
2447 \r
2448       while ((INT16) (--CharC) >= 0) {\r
2449         Sd->mCLen[Index++] = 0;\r
2450       }\r
2451 \r
2452     } else {\r
2453 \r
2454       Sd->mCLen[Index++] = (UINT8) (CharC - 2);\r
2455 \r
2456     }\r
2457   }\r
2458 \r
2459   while (Index < NC) {\r
2460     Sd->mCLen[Index++] = 0;\r
2461   }\r
2462 \r
2463   MakeTable (Sd, NC, Sd->mCLen, 12, Sd->mCTable);\r
2464 \r
2465   return ;\r
2466 }\r
2467 \r
2468 UINT16\r
2469 DecodeC (\r
2470   SCRATCH_DATA  *Sd\r
2471   )\r
2472 /*++\r
2473 \r
2474 Routine Description:\r
2475 \r
2476   Decode a character/length value.\r
2477 \r
2478 Arguments:\r
2479 \r
2480   Sd    - The global scratch data.\r
2481 \r
2482 Returns:\r
2483 \r
2484   The value decoded.\r
2485 \r
2486 --*/\r
2487 {\r
2488   UINT16  Index2;\r
2489   UINT32  Mask;\r
2490 \r
2491   if (Sd->mBlockSize == 0) {\r
2492     //\r
2493     // Starting a new block\r
2494     //\r
2495     Sd->mBlockSize    = (UINT16) GetBits (Sd, 16);\r
2496     Sd->mBadTableFlag = ReadPTLen (Sd, NT, TBIT, 3);\r
2497     if (Sd->mBadTableFlag != 0) {\r
2498       return 0;\r
2499     }\r
2500 \r
2501     ReadCLen (Sd);\r
2502 \r
2503     Sd->mBadTableFlag = ReadPTLen (Sd, MAXNP, Sd->mPBit, (UINT16) (-1));\r
2504     if (Sd->mBadTableFlag != 0) {\r
2505       return 0;\r
2506     }\r
2507   }\r
2508 \r
2509   Sd->mBlockSize--;\r
2510   Index2 = Sd->mCTable[Sd->mBitBuf >> (BITBUFSIZ - 12)];\r
2511 \r
2512   if (Index2 >= NC) {\r
2513     Mask = 1U << (BITBUFSIZ - 1 - 12);\r
2514 \r
2515     do {\r
2516       if (Sd->mBitBuf & Mask) {\r
2517         Index2 = Sd->mRight[Index2];\r
2518       } else {\r
2519         Index2 = Sd->mLeft[Index2];\r
2520       }\r
2521 \r
2522       Mask >>= 1;\r
2523     } while (Index2 >= NC);\r
2524   }\r
2525   //\r
2526   // Advance what we have read\r
2527   //\r
2528   FillBuf (Sd, Sd->mCLen[Index2]);\r
2529 \r
2530   return Index2;\r
2531 }\r
2532 \r
2533 VOID\r
2534 Decode (\r
2535   SCRATCH_DATA  *Sd\r
2536   )\r
2537 /*++\r
2538 \r
2539 Routine Description:\r
2540 \r
2541   Decode the source data and put the resulting data into the destination buffer.\r
2542 \r
2543 Arguments:\r
2544 \r
2545   Sd            - The global scratch data\r
2546 \r
2547 Returns: (VOID)\r
2548 \r
2549  --*/\r
2550 {\r
2551   UINT16  BytesRemain;\r
2552   UINT32  DataIdx;\r
2553   UINT16  CharC;\r
2554 \r
2555   BytesRemain = (UINT16) (-1);\r
2556 \r
2557   DataIdx     = 0;\r
2558 \r
2559   for (;;) {\r
2560     CharC = DecodeC (Sd);\r
2561     if (Sd->mBadTableFlag != 0) {\r
2562       goto Done ;\r
2563     }\r
2564 \r
2565     if (CharC < 256) {\r
2566       //\r
2567       // Process an Original character\r
2568       //\r
2569       if (Sd->mOutBuf >= Sd->mOrigSize) {\r
2570         goto Done ;\r
2571       } else {\r
2572         Sd->mDstBase[Sd->mOutBuf++] = (UINT8) CharC;\r
2573       }\r
2574 \r
2575     } else {\r
2576       //\r
2577       // Process a Pointer\r
2578       //\r
2579       CharC       = (UINT16) (CharC - (UINT8_MAX + 1 - THRESHOLD));\r
2580 \r
2581       BytesRemain = CharC;\r
2582 \r
2583       DataIdx     = Sd->mOutBuf - DecodeP (Sd) - 1;\r
2584 \r
2585       BytesRemain--;\r
2586       while ((INT16) (BytesRemain) >= 0) {\r
2587         Sd->mDstBase[Sd->mOutBuf++] = Sd->mDstBase[DataIdx++];\r
2588         if (Sd->mOutBuf >= Sd->mOrigSize) {\r
2589           goto Done ;\r
2590         }\r
2591 \r
2592         BytesRemain--;\r
2593       }\r
2594     }\r
2595   }\r
2596 \r
2597 Done:\r
2598   return ;\r
2599 }\r
2600 \r
2601 RETURN_STATUS\r
2602 EFIAPI\r
2603 Decompress (\r
2604   IN VOID  *Source,\r
2605   IN OUT VOID    *Destination,\r
2606   IN OUT VOID    *Scratch,\r
2607   IN UINT32      Version\r
2608   )\r
2609 /*++\r
2610 \r
2611 Routine Description:\r
2612 \r
2613   The internal implementation of Decompress().\r
2614 \r
2615 Arguments:\r
2616 \r
2617   Source          - The source buffer containing the compressed data.\r
2618   Destination     - The destination buffer to store the decompressed data\r
2619   Scratch         - The buffer used internally by the decompress routine. This  buffer is needed to store intermediate data.\r
2620   Version         - 1 for EFI1.1 Decompress algoruthm, 2 for Tiano Decompress algorithm\r
2621 \r
2622 Returns:\r
2623 \r
2624   RETURN_SUCCESS           - Decompression is successfull\r
2625   RETURN_INVALID_PARAMETER - The source data is corrupted\r
2626 \r
2627 --*/\r
2628 {\r
2629   volatile UINT32  Index;\r
2630   UINT32           CompSize;\r
2631   UINT32           OrigSize;\r
2632   SCRATCH_DATA     *Sd;\r
2633   CONST UINT8      *Src;\r
2634   UINT8            *Dst;\r
2635 \r
2636   //\r
2637   // Verify input is not NULL\r
2638   //\r
2639   assert(Source);\r
2640 //  assert(Destination);\r
2641   assert(Scratch);\r
2642   \r
2643   Src     = (UINT8 *)Source;\r
2644   Dst     = (UINT8 *)Destination;\r
2645 \r
2646   Sd      = (SCRATCH_DATA *) Scratch;\r
2647   CompSize  = Src[0] + (Src[1] << 8) + (Src[2] << 16) + (Src[3] << 24);\r
2648   OrigSize  = Src[4] + (Src[5] << 8) + (Src[6] << 16) + (Src[7] << 24);\r
2649   \r
2650   //\r
2651   // If compressed file size is 0, return\r
2652   //\r
2653   if (OrigSize == 0) {\r
2654     return RETURN_SUCCESS;\r
2655   }\r
2656 \r
2657   Src = Src + 8;\r
2658 \r
2659   for (Index = 0; Index < sizeof (SCRATCH_DATA); Index++) {\r
2660     ((UINT8 *) Sd)[Index] = 0;\r
2661   }\r
2662   //\r
2663   // The length of the field 'Position Set Code Length Array Size' in Block Header.\r
2664   // For EFI 1.1 de/compression algorithm(Version 1), mPBit = 4\r
2665   // For Tiano de/compression algorithm(Version 2), mPBit = 5\r
2666   //\r
2667   switch (Version) {\r
2668     case 1 :\r
2669       Sd->mPBit = 4;\r
2670       break;\r
2671     case 2 :\r
2672       Sd->mPBit = 5;\r
2673       break;\r
2674     default:\r
2675       assert(FALSE);\r
2676   }\r
2677   Sd->mSrcBase  = (UINT8 *)Src;\r
2678   Sd->mDstBase  = Dst;\r
2679   Sd->mCompSize = CompSize;\r
2680   Sd->mOrigSize = OrigSize;\r
2681 \r
2682   //\r
2683   // Fill the first BITBUFSIZ bits\r
2684   //\r
2685   FillBuf (Sd, BITBUFSIZ);\r
2686 \r
2687   //\r
2688   // Decompress it\r
2689   //\r
2690   \r
2691   Decode (Sd);\r
2692   \r
2693   if (Sd->mBadTableFlag != 0) {\r
2694     //\r
2695     // Something wrong with the source\r
2696     //\r
2697     return RETURN_INVALID_PARAMETER;\r
2698   }\r
2699 \r
2700   return RETURN_SUCCESS;\r
2701 }\r
2702 \r