Sync EDKII BaseTools to BaseTools project r1903.
[efi/edk2/.git] / edk2 / BaseTools / Source / C / TianoCompress / TianoCompress.c
1 /** @file\r
2 \r
3 Copyright (c) 2007 - 2010, 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 "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
36 static BOOLEAN VerboseMode = FALSE;\r
37 static 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
73 STATIC BOOLEAN ENCODE = FALSE;\r
74 STATIC BOOLEAN DECODE = FALSE;\r
75 STATIC UINT8  *mSrc, *mDst, *mSrcUpperLimit, *mDstUpperLimit;\r
76 STATIC UINT8  *mLevel, *mText, *mChildCount, *mBuf, mCLen[NC], mPTLen[NPT], *mLen;\r
77 STATIC INT16  mHeap[NC + 1];\r
78 STATIC INT32  mRemainder, mMatchLen, mBitCount, mHeapSize, mN;\r
79 STATIC UINT32 mBufSiz = 0, mOutputPos, mOutputMask, mSubBitBuf, mCrc;\r
80 STATIC UINT32 mCompSize, mOrigSize;\r
81 \r
82 STATIC 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
85 STATIC NODE   mPos, mMatchPos, mAvail, *mPosition, *mParent, *mPrev, *mNext = NULL;\r
86 \r
87 static  UINT64     DebugLevel;\r
88 static  BOOLEAN    DebugMode;\r
89 //\r
90 // functions\r
91 //\r
92 EFI_STATUS\r
93 TianoCompress (\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
101 Routine Description:\r
102 \r
103   The internal implementation of [Efi/Tiano]Compress().\r
104 \r
105 Arguments:\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
115 Returns:\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
183     return EFI_BUFFER_TOO_SMALL;\r
184   } else {\r
185     *DstSize = mCompSize + 1 + 8;   \r
186     return EFI_SUCCESS;\r
187   }\r
188 }\r
189 \r
190 STATIC\r
191 VOID\r
192 PutDword (\r
193   IN UINT32 Data\r
194   )\r
195 /*++\r
196 \r
197 Routine Description:\r
198 \r
199   Put a dword to output stream\r
200   \r
201 Arguments:\r
202 \r
203   Data    - the dword to put\r
204   \r
205 Returns: (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
226 STATIC\r
227 EFI_STATUS\r
228 AllocateMemory (\r
229   VOID\r
230   )\r
231 /*++\r
232 \r
233 Routine Description:\r
234 \r
235   Allocate memory spaces for data structures used in compression process\r
236   \r
237 Argements: \r
238   VOID\r
239 \r
240 Returns:\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
277 VOID\r
278 FreeMemory (\r
279   VOID\r
280   )\r
281 /*++\r
282 \r
283 Routine Description:\r
284 \r
285   Called when compression is completed to free memory previously allocated.\r
286   \r
287 Arguments: (VOID)\r
288 \r
289 Returns: (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
328 STATIC\r
329 VOID\r
330 InitSlide (\r
331   VOID\r
332   )\r
333 /*++\r
334 \r
335 Routine Description:\r
336 \r
337   Initialize String Info Log data structures\r
338   \r
339 Arguments: (VOID)\r
340 \r
341 Returns: (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
367 STATIC\r
368 NODE\r
369 Child (\r
370   IN NODE  NodeQ,\r
371   IN UINT8 CharC\r
372   )\r
373 /*++\r
374 \r
375 Routine Description:\r
376 \r
377   Find child node given the parent node and the edge character\r
378   \r
379 Arguments:\r
380 \r
381   NodeQ       - the parent node\r
382   CharC       - the edge character\r
383   \r
384 Returns:\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
404 STATIC\r
405 VOID\r
406 MakeChild (\r
407   IN NODE  Parent,\r
408   IN UINT8 CharC,\r
409   IN NODE  Child\r
410   )\r
411 /*++\r
412 \r
413 Routine Description:\r
414 \r
415   Create a new child for a given parent node.\r
416   \r
417 Arguments:\r
418 \r
419   Parent       - the parent node\r
420   CharC   - the edge character\r
421   Child       - the child node\r
422   \r
423 Returns: (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
440 STATIC\r
441 VOID\r
442 Split (\r
443   NODE Old\r
444   )\r
445 /*++\r
446 \r
447 Routine Description:\r
448 \r
449   Split a node.\r
450   \r
451 Arguments:\r
452 \r
453   Old     - the node to split\r
454   \r
455 Returns: (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
478 STATIC\r
479 VOID\r
480 InsertNode (\r
481   VOID\r
482   )\r
483 /*++\r
484 \r
485 Routine Description:\r
486 \r
487   Insert string info for current position into the String Info Log\r
488   \r
489 Arguments: (VOID)\r
490 \r
491 Returns: (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
610 STATIC\r
611 VOID\r
612 DeleteNode (\r
613   VOID\r
614   )\r
615 /*++\r
616 \r
617 Routine Description:\r
618 \r
619   Delete outdated string info. (The Usage of PERC_FLAG\r
620   ensures a clean deletion)\r
621   \r
622 Arguments: (VOID)\r
623 \r
624 Returns: (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
705 STATIC\r
706 VOID\r
707 GetNextMatch (\r
708   VOID\r
709   )\r
710 /*++\r
711 \r
712 Routine 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
717 Arguments: (VOID)\r
718 \r
719 Returns: (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
738 STATIC\r
739 EFI_STATUS\r
740 Encode (\r
741   VOID\r
742   )\r
743 /*++\r
744 \r
745 Routine Description:\r
746 \r
747   The main controlling routine for compression process.\r
748 \r
749 Arguments: (VOID)\r
750 \r
751 Returns:\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
828 STATIC\r
829 VOID\r
830 CountTFreq (\r
831   VOID\r
832   )\r
833 /*++\r
834 \r
835 Routine Description:\r
836 \r
837   Count the frequencies for the Extra Set\r
838   \r
839 Arguments: (VOID)\r
840 \r
841 Returns: (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
885 STATIC\r
886 VOID\r
887 WritePTLen (\r
888   IN INT32 Number,\r
889   IN INT32 nbit,\r
890   IN INT32 Special\r
891   )\r
892 /*++\r
893 \r
894 Routine Description:\r
895 \r
896   Outputs the code length array for the Extra Set or the Position Set.\r
897   \r
898 Arguments:\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
904 Returns: (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
935 STATIC\r
936 VOID\r
937 WriteCLen (\r
938   VOID\r
939   )\r
940 /*++\r
941 \r
942 Routine Description:\r
943 \r
944   Outputs the code length array for Char&Length Set\r
945   \r
946 Arguments: (VOID)\r
947 \r
948 Returns: (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
994 STATIC\r
995 VOID\r
996 EncodeC (\r
997   IN INT32 Value\r
998   )\r
999 {\r
1000   PutBits (mCLen[Value], mCCode[Value]);\r
1001 }\r
1002 \r
1003 STATIC\r
1004 VOID\r
1005 EncodeP (\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
1025 STATIC\r
1026 VOID\r
1027 SendBlock (\r
1028   VOID\r
1029   )\r
1030 /*++\r
1031 \r
1032 Routine Description:\r
1033 \r
1034   Huffman code the block and output it.\r
1035   \r
1036 Arguments: \r
1037   (VOID)\r
1038 \r
1039 Returns: \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
1114 STATIC\r
1115 VOID\r
1116 Output (\r
1117   IN UINT32 CharC,\r
1118   IN UINT32 Pos\r
1119   )\r
1120 /*++\r
1121 \r
1122 Routine Description:\r
1123 \r
1124   Outputs an Original Character or a Pointer\r
1125 \r
1126 Arguments:\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
1131 Returns: (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
1171 STATIC\r
1172 VOID\r
1173 HufEncodeStart (\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
1192 STATIC\r
1193 VOID\r
1194 HufEncodeEnd (\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
1208 STATIC\r
1209 VOID\r
1210 MakeCrcTable (\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
1232 STATIC\r
1233 VOID\r
1234 PutBits (\r
1235   IN INT32  Number,\r
1236   IN UINT32 Value\r
1237   )\r
1238 /*++\r
1239 \r
1240 Routine Description:\r
1241 \r
1242   Outputs rightmost n bits of x\r
1243 \r
1244 Arguments:\r
1245 \r
1246   Number   - the rightmost n bits of the data is used\r
1247   x   - the data \r
1248 \r
1249 Returns: (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
1273 STATIC\r
1274 INT32\r
1275 FreadCrc (\r
1276   OUT UINT8 *Pointer,\r
1277   IN  INT32 Number\r
1278   )\r
1279 /*++\r
1280 \r
1281 Routine Description:\r
1282 \r
1283   Read in source data\r
1284   \r
1285 Arguments:\r
1286 \r
1287   Pointer   - the buffer to hold the data\r
1288   Number   - number of bytes to read\r
1289 \r
1290 Returns:\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
1316 STATIC\r
1317 VOID\r
1318 InitPutBits (\r
1319   VOID\r
1320   )\r
1321 {\r
1322   mBitCount   = UINT8_BIT;\r
1323   mSubBitBuf  = 0;\r
1324 }\r
1325 \r
1326 STATIC\r
1327 VOID\r
1328 CountLen (\r
1329   IN INT32 Index\r
1330   )\r
1331 /*++\r
1332 \r
1333 Routine Description:\r
1334 \r
1335   Count the number of each code length for a Huffman tree.\r
1336   \r
1337 Arguments:\r
1338 \r
1339   Index   - the top node\r
1340   \r
1341 Returns: (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
1357 STATIC\r
1358 VOID\r
1359 MakeLen (\r
1360   IN INT32 Root\r
1361   )\r
1362 /*++\r
1363 \r
1364 Routine Description:\r
1365 \r
1366   Create code length array for a Huffman tree\r
1367   \r
1368 Arguments:\r
1369 \r
1370   Root   - the root of the tree\r
1371   \r
1372 Returns:\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
1420 STATIC\r
1421 VOID\r
1422 DownHeap (\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
1451 STATIC\r
1452 VOID\r
1453 MakeCode (\r
1454   IN  INT32       Number,\r
1455   IN  UINT8 Len[  ],\r
1456   OUT UINT16 Code[]\r
1457   )\r
1458 /*++\r
1459 \r
1460 Routine Description:\r
1461 \r
1462   Assign code to each symbol based on the code length array\r
1463   \r
1464 Arguments:\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
1470 Returns: (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
1487 STATIC\r
1488 INT32\r
1489 MakeTree (\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
1497 Routine Description:\r
1498 \r
1499   Generates Huffman codes given a frequency distribution of symbols\r
1500   \r
1501 Arguments:\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
1508 Returns:\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
1580 EFI_STATUS\r
1581 GetFileContents (\r
1582   IN char    *InputFileName,\r
1583   OUT UINT8   *FileBuffer,\r
1584   OUT UINT32  *BufferLength\r
1585   )\r
1586 /*++\r
1587         \r
1588 Routine Description:\r
1589            \r
1590   Get the contents of file specified in InputFileName\r
1591   into FileBuffer.\r
1592             \r
1593 Arguments:\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
1601 Returns:\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
1647 VOID\r
1648 Version (\r
1649   VOID\r
1650   )\r
1651 /*++\r
1652 \r
1653 Routine Description:\r
1654 \r
1655   Displays the standard utility information to SDTOUT\r
1656 \r
1657 Arguments:\r
1658 \r
1659   None\r
1660 \r
1661 Returns:\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
1670 VOID\r
1671 Usage (\r
1672   VOID\r
1673   )\r
1674 /*++\r
1675 \r
1676 Routine Description:\r
1677 \r
1678   Displays the utility usage syntax to STDOUT\r
1679 \r
1680 Arguments:\r
1681 \r
1682   None\r
1683 \r
1684 Returns:\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
1698   fprintf (stdout, "Copyright (c) 2007 - 2010, Intel Corporation. All rights reserved.\n\n");\r
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
1719 int\r
1720 main (\r
1721   int  argc,\r
1722   char *argv[]\r
1723   )\r
1724 /*++\r
1725 \r
1726 Routine Description:\r
1727 \r
1728   Main\r
1729 \r
1730 Arguments:\r
1731 \r
1732   command line parameters\r
1733 \r
1734 Returns:\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
2010 ERROR:\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
2034 VOID\r
2035 FillBuf (\r
2036   IN  SCRATCH_DATA  *Sd,\r
2037   IN  UINT16        NumOfBits\r
2038   )\r
2039 /*++\r
2040 \r
2041 Routine Description:\r
2042 \r
2043   Shift mBitBuf NumOfBits left. Read in NumOfBits of bits from source.\r
2044 \r
2045 Arguments:\r
2046 \r
2047   Sd        - The global scratch data\r
2048   NumOfBits  - The number of bits to shift and read.\r
2049 \r
2050 Returns: (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
2083 UINT32\r
2084 GetBits (\r
2085   IN  SCRATCH_DATA  *Sd,\r
2086   IN  UINT16        NumOfBits\r
2087   )\r
2088 /*++\r
2089 \r
2090 Routine 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
2096 Arguments:\r
2097 \r
2098   Sd            - The global scratch data.\r
2099   NumOfBits     - The number of bits to pop and read.\r
2100 \r
2101 Returns:\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
2116 UINT16\r
2117 MakeTable (\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
2126 Routine Description:\r
2127 \r
2128   Creates Huffman Code mapping table according to code length array.\r
2129 \r
2130 Arguments:\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
2138 Returns:\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
2256 UINT32\r
2257 DecodeP (\r
2258   IN  SCRATCH_DATA  *Sd\r
2259   )\r
2260 /*++\r
2261 \r
2262 Routine Description:\r
2263 \r
2264   Decodes a position value.\r
2265 \r
2266 Arguments:\r
2267 \r
2268   Sd      - the global scratch data\r
2269 \r
2270 Returns:\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
2309 UINT16\r
2310 ReadPTLen (\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
2318 Routine Description:\r
2319 \r
2320   Reads code lengths for the Extra Set or the Position Set\r
2321 \r
2322 Arguments:\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
2329 Returns:\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
2390 VOID\r
2391 ReadCLen (\r
2392   SCRATCH_DATA  *Sd\r
2393   )\r
2394 /*++\r
2395 \r
2396 Routine Description:\r
2397 \r
2398   Reads code lengths for Char&Len Set.\r
2399 \r
2400 Arguments:\r
2401 \r
2402   Sd    - the global scratch data\r
2403 \r
2404 Returns: (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
2483 UINT16\r
2484 DecodeC (\r
2485   SCRATCH_DATA  *Sd\r
2486   )\r
2487 /*++\r
2488 \r
2489 Routine Description:\r
2490 \r
2491   Decode a character/length value.\r
2492 \r
2493 Arguments:\r
2494 \r
2495   Sd    - The global scratch data.\r
2496 \r
2497 Returns:\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
2548 VOID\r
2549 Decode (\r
2550   SCRATCH_DATA  *Sd\r
2551   )\r
2552 /*++\r
2553 \r
2554 Routine Description:\r
2555 \r
2556   Decode the source data and put the resulting data into the destination buffer.\r
2557 \r
2558 Arguments:\r
2559 \r
2560   Sd            - The global scratch data\r
2561 \r
2562 Returns: (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
2612 Done:\r
2613   return ;\r
2614 }\r
2615 \r
2616 RETURN_STATUS\r
2617 EFIAPI\r
2618 Decompress (\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
2626 Routine Description:\r
2627 \r
2628   The internal implementation of Decompress().\r
2629 \r
2630 Arguments:\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
2637 Returns:\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