]> git.proxmox.com Git - mirror_edk2.git/blame - BaseTools/Source/C/Common/TianoCompress.c
projects / mirror_edk2.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Check In tool source code based on Build tool project revision r1655.
[mirror_edk2.git] / BaseTools / Source / C / Common / TianoCompress.c
CommitLineData
30fdf114
LG		 1/** @file\r
2\r
3Copyright (c) 2006 - 2008, Intel Corporation \r
4All rights reserved. This program and the accompanying materials \r
5are licensed and made available under the terms and conditions of the BSD License \r
6which accompanies this distribution. The full text of the license may be found at \r
7http://opensource.org/licenses/bsd-license.php \r
8 \r
9THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS, \r
10WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED. \r
11\r
12Module Name:\r
13\r
14 TianoCompress.c\r
15\r
16Abstract:\r
17\r
18 Compression routine. The compression algorithm is a mixture of\r
19 LZ77 and Huffman coding. LZ77 transforms the source data into a\r
20 sequence of Original Characters and Pointers to repeated strings.\r
21 This sequence is further divided into Blocks and Huffman codings\r
22 are applied to each Block.\r
23\r
24**/\r
25\r
26#include "Compress.h"\r
27\r
28//\r
29// Macro Definitions\r
30//\r
31#undef UINT8_MAX\r
32typedef INT32 NODE;\r
33#define UINT8_MAX 0xff\r
34#define UINT8_BIT 8\r
35#define THRESHOLD 3\r
36#define INIT_CRC 0\r
37#define WNDBIT 19\r
38#define WNDSIZ (1U << WNDBIT)\r
39#define MAXMATCH 256\r
40#define BLKSIZ (1U << 14) // 16 * 1024U\r
41#define PERC_FLAG 0x80000000U\r
42#define CODE_BIT 16\r
43#define NIL 0\r
44#define MAX_HASH_VAL (3 * WNDSIZ + (WNDSIZ / 512 + 1) * UINT8_MAX)\r
45#define HASH(p, c) ((p) + ((c) << (WNDBIT - 9)) + WNDSIZ * 2)\r
46#define CRCPOLY 0xA001\r
47#define UPDATE_CRC(c) mCrc = mCrcTable[(mCrc ^ (c)) & 0xFF] ^ (mCrc >> UINT8_BIT)\r
48\r
49//\r
50// C: the Char&Len Set; P: the Position Set; T: the exTra Set\r
51//\r
52#define NC (UINT8_MAX + MAXMATCH + 2 - THRESHOLD)\r
53#define CBIT 9\r
54#define NP (WNDBIT + 1)\r
55#define PBIT 5\r
56#define NT (CODE_BIT + 3)\r
57#define TBIT 5\r
58#if NT > NP\r
59#define NPT NT\r
60#else\r
61#define NPT NP\r
62#endif\r
63//\r
64// Function Prototypes\r
65//\r
66\r
67STATIC\r
68VOID\r
69PutDword(\r
70 IN UINT32 Data\r
71 );\r
72\r
73STATIC\r
74EFI_STATUS\r
75AllocateMemory (\r
76 VOID\r
77 );\r
78\r
79STATIC\r
80VOID\r
81FreeMemory (\r
82 VOID\r
83 );\r
84\r
85STATIC\r
86VOID\r
87InitSlide (\r
88 VOID\r
89 );\r
90\r
91STATIC\r
92NODE\r
93Child (\r
94 IN NODE NodeQ,\r
95 IN UINT8 CharC\r
96 );\r
97\r
98STATIC\r
99VOID\r
100MakeChild (\r
101 IN NODE NodeQ,\r
102 IN UINT8 CharC,\r
103 IN NODE NodeR\r
104 );\r
105\r
106STATIC\r
107VOID\r
108Split (\r
109 IN NODE Old\r
110 );\r
111\r
112STATIC\r
113VOID\r
114InsertNode (\r
115 VOID\r
116 );\r
117\r
118STATIC\r
119VOID\r
120DeleteNode (\r
121 VOID\r
122 );\r
123\r
124STATIC\r
125VOID\r
126GetNextMatch (\r
127 VOID\r
128 );\r
129\r
130STATIC\r
131EFI_STATUS\r
132Encode (\r
133 VOID\r
134 );\r
135\r
136STATIC\r
137VOID\r
138CountTFreq (\r
139 VOID\r
140 );\r
141\r
142STATIC\r
143VOID\r
144WritePTLen (\r
145 IN INT32 Number,\r
146 IN INT32 nbit,\r
147 IN INT32 Special\r
148 );\r
149\r
150STATIC\r
151VOID\r
152WriteCLen (\r
153 VOID\r
154 );\r
155\r
156STATIC\r
157VOID\r
158EncodeC (\r
159 IN INT32 Value\r
160 );\r
161\r
162STATIC\r
163VOID\r
164EncodeP (\r
165 IN UINT32 Value\r
166 );\r
167\r
168STATIC\r
169VOID\r
170SendBlock (\r
171 VOID\r
172 );\r
173\r
174STATIC\r
175VOID\r
176Output (\r
177 IN UINT32 c,\r
178 IN UINT32 p\r
179 );\r
180\r
181STATIC\r
182VOID\r
183HufEncodeStart (\r
184 VOID\r
185 );\r
186\r
187STATIC\r
188VOID\r
189HufEncodeEnd (\r
190 VOID\r
191 );\r
192\r
193STATIC\r
194VOID\r
195MakeCrcTable (\r
196 VOID\r
197 );\r
198\r
199STATIC\r
200VOID\r
201PutBits (\r
202 IN INT32 Number,\r
203 IN UINT32 Value\r
204 );\r
205\r
206STATIC\r
207INT32\r
208FreadCrc (\r
209 OUT UINT8 *Pointer,\r
210 IN INT32 Number\r
211 );\r
212\r
213STATIC\r
214VOID\r
215InitPutBits (\r
216 VOID\r
217 );\r
218\r
219STATIC\r
220VOID\r
221CountLen (\r
222 IN INT32 Index\r
223 );\r
224\r
225STATIC\r
226VOID\r
227MakeLen (\r
228 IN INT32 Root\r
229 );\r
230\r
231STATIC\r
232VOID\r
233DownHeap (\r
234 IN INT32 Index\r
235 );\r
236\r
237STATIC\r
238VOID\r
239MakeCode (\r
240 IN INT32 Number,\r
241 IN UINT8 Len[ ],\r
242 OUT UINT16 Code[]\r
243 );\r
244\r
245STATIC\r
246INT32\r
247MakeTree (\r
248 IN INT32 NParm,\r
249 IN UINT16 FreqParm[],\r
250 OUT UINT8 LenParm[ ],\r
251 OUT UINT16 CodeParm[]\r
252 );\r
253\r
254//\r
255// Global Variables\r
256//\r
257STATIC UINT8 *mSrc, *mDst, *mSrcUpperLimit, *mDstUpperLimit;\r
258\r
259STATIC UINT8 *mLevel, *mText, *mChildCount, *mBuf, mCLen[NC], mPTLen[NPT], *mLen;\r
260STATIC INT16 mHeap[NC + 1];\r
261STATIC INT32 mRemainder, mMatchLen, mBitCount, mHeapSize, mN;\r
262STATIC UINT32 mBufSiz = 0, mOutputPos, mOutputMask, mSubBitBuf, mCrc;\r
263STATIC UINT32 mCompSize, mOrigSize;\r
264\r
265STATIC UINT16 *mFreq, *mSortPtr, mLenCnt[17], mLeft[2 * NC - 1], mRight[2 * NC - 1], mCrcTable[UINT8_MAX + 1],\r
266 mCFreq[2 * NC - 1], mCCode[NC], mPFreq[2 * NP - 1], mPTCode[NPT], mTFreq[2 * NT - 1];\r
267\r
268STATIC NODE mPos, mMatchPos, mAvail, *mPosition, *mParent, *mPrev, *mNext = NULL;\r
269\r
270//\r
271// functions\r
272//\r
273EFI_STATUS\r
274TianoCompress (\r
275 IN UINT8 *SrcBuffer,\r
276 IN UINT32 SrcSize,\r
277 IN UINT8 *DstBuffer,\r
278 IN OUT UINT32 *DstSize\r
279 )\r
280/*++\r
281\r
282Routine Description:\r
283\r
284 The internal implementation of [Efi/Tiano]Compress().\r
285\r
286Arguments:\r
287\r
288 SrcBuffer - The buffer storing the source data\r
289 SrcSize - The size of source data\r
290 DstBuffer - The buffer to store the compressed data\r
291 DstSize - On input, the size of DstBuffer; On output,\r
292 the size of the actual compressed data.\r
293 Version - The version of de/compression algorithm.\r
294 Version 1 for UEFI 2.0 de/compression algorithm.\r
295 Version 2 for Tiano de/compression algorithm.\r
296\r
297Returns:\r
298\r
299 EFI_BUFFER_TOO_SMALL - The DstBuffer is too small. In this case,\r
300 DstSize contains the size needed.\r
301 EFI_SUCCESS - Compression is successful.\r
302 EFI_OUT_OF_RESOURCES - No resource to complete function.\r
303 EFI_INVALID_PARAMETER - Parameter supplied is wrong.\r
304\r
305--*/\r
306{\r
307 EFI_STATUS Status;\r
308\r
309 //\r
310 // Initializations\r
311 //\r
312 mBufSiz = 0;\r
313 mBuf = NULL;\r
314 mText = NULL;\r
315 mLevel = NULL;\r
316 mChildCount = NULL;\r
317 mPosition = NULL;\r
318 mParent = NULL;\r
319 mPrev = NULL;\r
320 mNext = NULL;\r
321\r
322 mSrc = SrcBuffer;\r
323 mSrcUpperLimit = mSrc + SrcSize;\r
324 mDst = DstBuffer;\r
325 mDstUpperLimit = mDst +*DstSize;\r
326\r
327 PutDword (0L);\r
328 PutDword (0L);\r
329\r
330 MakeCrcTable ();\r
331\r
332 mOrigSize = mCompSize = 0;\r
333 mCrc = INIT_CRC;\r
334\r
335 //\r
336 // Compress it\r
337 //\r
338 Status = Encode ();\r
339 if (EFI_ERROR (Status)) {\r
340 return EFI_OUT_OF_RESOURCES;\r
341 }\r
342 //\r
343 // Null terminate the compressed data\r
344 //\r
345 if (mDst < mDstUpperLimit) {\r
346 *mDst++ = 0;\r
347 }\r
348 //\r
349 // Fill in compressed size and original size\r
350 //\r
351 mDst = DstBuffer;\r
352 PutDword (mCompSize + 1);\r
353 PutDword (mOrigSize);\r
354\r
355 //\r
356 // Return\r
357 //\r
358 if (mCompSize + 1 + 8 > *DstSize) {\r
359 *DstSize = mCompSize + 1 + 8;\r
360 return EFI_BUFFER_TOO_SMALL;\r
361 } else {\r
362 *DstSize = mCompSize + 1 + 8;\r
363 return EFI_SUCCESS;\r
364 }\r
365\r
366}\r
367\r
368STATIC\r
369VOID\r
370PutDword (\r
371 IN UINT32 Data\r
372 )\r
373/*++\r
374\r
375Routine Description:\r
376\r
377 Put a dword to output stream\r
378 \r
379Arguments:\r
380\r
381 Data - the dword to put\r
382 \r
383Returns: (VOID)\r
384 \r
385--*/\r
386{\r
387 if (mDst < mDstUpperLimit) {\r
388 *mDst++ = (UINT8) (((UINT8) (Data)) & 0xff);\r
389 }\r
390\r
391 if (mDst < mDstUpperLimit) {\r
392 *mDst++ = (UINT8) (((UINT8) (Data >> 0x08)) & 0xff);\r
393 }\r
394\r
395 if (mDst < mDstUpperLimit) {\r
396 *mDst++ = (UINT8) (((UINT8) (Data >> 0x10)) & 0xff);\r
397 }\r
398\r
399 if (mDst < mDstUpperLimit) {\r
400 *mDst++ = (UINT8) (((UINT8) (Data >> 0x18)) & 0xff);\r
401 }\r
402}\r
403\r
404STATIC\r
405EFI_STATUS\r
406AllocateMemory (\r
407 VOID\r
408 )\r
409/*++\r
410\r
411Routine Description:\r
412\r
413 Allocate memory spaces for data structures used in compression process\r
414 \r
415Argements: \r
416 VOID\r
417\r
418Returns:\r
419\r
420 EFI_SUCCESS - Memory is allocated successfully\r
421 EFI_OUT_OF_RESOURCES - Allocation fails\r
422\r
423--*/\r
424{\r
425 UINT32 Index;\r
426\r
427 mText = malloc (WNDSIZ * 2 + MAXMATCH);\r
428 for (Index = 0; Index < WNDSIZ * 2 + MAXMATCH; Index++) {\r
429 mText[Index] = 0;\r
430 }\r
431\r
432 mLevel = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mLevel));\r
433 mChildCount = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mChildCount));\r
434 mPosition = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mPosition));\r
435 mParent = malloc (WNDSIZ * 2 * sizeof (*mParent));\r
436 mPrev = malloc (WNDSIZ * 2 * sizeof (*mPrev));\r
437 mNext = malloc ((MAX_HASH_VAL + 1) * sizeof (*mNext));\r
438\r
439 mBufSiz = BLKSIZ;\r
440 mBuf = malloc (mBufSiz);\r
441 while (mBuf == NULL) {\r
442 mBufSiz = (mBufSiz / 10U) * 9U;\r
443 if (mBufSiz < 4 * 1024U) {\r
444 return EFI_OUT_OF_RESOURCES;\r
445 }\r
446\r
447 mBuf = malloc (mBufSiz);\r
448 }\r
449\r
450 mBuf[0] = 0;\r
451\r
452 return EFI_SUCCESS;\r
453}\r
454\r
455VOID\r
456FreeMemory (\r
457 VOID\r
458 )\r
459/*++\r
460\r
461Routine Description:\r
462\r
463 Called when compression is completed to free memory previously allocated.\r
464 \r
465Arguments: (VOID)\r
466\r
467Returns: (VOID)\r
468\r
469--*/\r
470{\r
471 if (mText != NULL) {\r
472 free (mText);\r
473 }\r
474\r
475 if (mLevel != NULL) {\r
476 free (mLevel);\r
477 }\r
478\r
479 if (mChildCount != NULL) {\r
480 free (mChildCount);\r
481 }\r
482\r
483 if (mPosition != NULL) {\r
484 free (mPosition);\r
485 }\r
486\r
487 if (mParent != NULL) {\r
488 free (mParent);\r
489 }\r
490\r
491 if (mPrev != NULL) {\r
492 free (mPrev);\r
493 }\r
494\r
495 if (mNext != NULL) {\r
496 free (mNext);\r
497 }\r
498\r
499 if (mBuf != NULL) {\r
500 free (mBuf);\r
501 }\r
502\r
503 return ;\r
504}\r
505\r
506STATIC\r
507VOID\r
508InitSlide (\r
509 VOID\r
510 )\r
511/*++\r
512\r
513Routine Description:\r
514\r
515 Initialize String Info Log data structures\r
516 \r
517Arguments: (VOID)\r
518\r
519Returns: (VOID)\r
520\r
521--*/\r
522{\r
523 NODE Index;\r
524\r
525 for (Index = WNDSIZ; Index <= WNDSIZ + UINT8_MAX; Index++) {\r
526 mLevel[Index] = 1;\r
527 mPosition[Index] = NIL; /* sentinel */\r
528 }\r
529\r
530 for (Index = WNDSIZ; Index < WNDSIZ * 2; Index++) {\r
531 mParent[Index] = NIL;\r
532 }\r
533\r
534 mAvail = 1;\r
535 for (Index = 1; Index < WNDSIZ - 1; Index++) {\r
536 mNext[Index] = (NODE) (Index + 1);\r
537 }\r
538\r
539 mNext[WNDSIZ - 1] = NIL;\r
540 for (Index = WNDSIZ * 2; Index <= MAX_HASH_VAL; Index++) {\r
541 mNext[Index] = NIL;\r
542 }\r
543}\r
544\r
545STATIC\r
546NODE\r
547Child (\r
548 IN NODE NodeQ,\r
549 IN UINT8 CharC\r
550 )\r
551/*++\r
552\r
553Routine Description:\r
554\r
555 Find child node given the parent node and the edge character\r
556 \r
557Arguments:\r
558\r
559 NodeQ - the parent node\r
560 CharC - the edge character\r
561 \r
562Returns:\r
563\r
564 The child node (NIL if not found) \r
565 \r
566--*/\r
567{\r
568 NODE NodeR;\r
569\r
570 NodeR = mNext[HASH (NodeQ, CharC)];\r
571 //\r
572 // sentinel\r
573 //\r
574 mParent[NIL] = NodeQ;\r
575 while (mParent[NodeR] != NodeQ) {\r
576 NodeR = mNext[NodeR];\r
577 }\r
578\r
579 return NodeR;\r
580}\r
581\r
582STATIC\r
583VOID\r
584MakeChild (\r
585 IN NODE Parent,\r
586 IN UINT8 CharC,\r
587 IN NODE Child\r
588 )\r
589/*++\r
590\r
591Routine Description:\r
592\r
593 Create a new child for a given parent node.\r
594 \r
595Arguments:\r
596\r
597 Parent - the parent node\r
598 CharC - the edge character\r
599 Child - the child node\r
600 \r
601Returns: (VOID)\r
602\r
603--*/\r
604{\r
605 NODE Node1;\r
606 NODE Node2;\r
607\r
608 Node1 = (NODE) HASH (Parent, CharC);\r
609 Node2 = mNext[Node1];\r
610 mNext[Node1] = Child;\r
611 mNext[Child] = Node2;\r
612 mPrev[Node2] = Child;\r
613 mPrev[Child] = Node1;\r
614 mParent[Child] = Parent;\r
615 mChildCount[Parent]++;\r
616}\r
617\r
618STATIC\r
619VOID\r
620Split (\r
621 NODE Old\r
622 )\r
623/*++\r
624\r
625Routine Description:\r
626\r
627 Split a node.\r
628 \r
629Arguments:\r
630\r
631 Old - the node to split\r
632 \r
633Returns: (VOID)\r
634\r
635--*/\r
636{\r
637 NODE New;\r
638 NODE TempNode;\r
639\r
640 New = mAvail;\r
641 mAvail = mNext[New];\r
642 mChildCount[New] = 0;\r
643 TempNode = mPrev[Old];\r
644 mPrev[New] = TempNode;\r
645 mNext[TempNode] = New;\r
646 TempNode = mNext[Old];\r
647 mNext[New] = TempNode;\r
648 mPrev[TempNode] = New;\r
649 mParent[New] = mParent[Old];\r
650 mLevel[New] = (UINT8) mMatchLen;\r
651 mPosition[New] = mPos;\r
652 MakeChild (New, mText[mMatchPos + mMatchLen], Old);\r
653 MakeChild (New, mText[mPos + mMatchLen], mPos);\r
654}\r
655\r
656STATIC\r
657VOID\r
658InsertNode (\r
659 VOID\r
660 )\r
661/*++\r
662\r
663Routine Description:\r
664\r
665 Insert string info for current position into the String Info Log\r
666 \r
667Arguments: (VOID)\r
668\r
669Returns: (VOID)\r
670\r
671--*/\r
672{\r
673 NODE NodeQ;\r
674 NODE NodeR;\r
675 NODE Index2;\r
676 NODE NodeT;\r
677 UINT8 CharC;\r
678 UINT8 *t1;\r
679 UINT8 *t2;\r
680\r
681 if (mMatchLen >= 4) {\r
682 //\r
683 // We have just got a long match, the target tree\r
684 // can be located by MatchPos + 1. Travese the tree\r
685 // from bottom up to get to a proper starting point.\r
686 // The usage of PERC_FLAG ensures proper node deletion\r
687 // in DeleteNode() later.\r
688 //\r
689 mMatchLen--;\r
690 NodeR = (NODE) ((mMatchPos + 1) | WNDSIZ);\r
691 NodeQ = mParent[NodeR];\r
692 while (NodeQ == NIL) {\r
693 NodeR = mNext[NodeR];\r
694 NodeQ = mParent[NodeR];\r
695 }\r
696\r
697 while (mLevel[NodeQ] >= mMatchLen) {\r
698 NodeR = NodeQ;\r
699 NodeQ = mParent[NodeQ];\r
700 }\r
701\r
702 NodeT = NodeQ;\r
703 while (mPosition[NodeT] < 0) {\r
704 mPosition[NodeT] = mPos;\r
705 NodeT = mParent[NodeT];\r
706 }\r
707\r
708 if (NodeT < WNDSIZ) {\r
709 mPosition[NodeT] = (NODE) (mPos | (UINT32) PERC_FLAG);\r
710 }\r
711 } else {\r
712 //\r
713 // Locate the target tree\r
714 //\r
715 NodeQ = (NODE) (mText[mPos] + WNDSIZ);\r
716 CharC = mText[mPos + 1];\r
717 NodeR = Child (NodeQ, CharC);\r
718 if (NodeR == NIL) {\r
719 MakeChild (NodeQ, CharC, mPos);\r
720 mMatchLen = 1;\r
721 return ;\r
722 }\r
723\r
724 mMatchLen = 2;\r
725 }\r
726 //\r
727 // Traverse down the tree to find a match.\r
728 // Update Position value along the route.\r
729 // Node split or creation is involved.\r
730 //\r
731 for (;;) {\r
732 if (NodeR >= WNDSIZ) {\r
733 Index2 = MAXMATCH;\r
734 mMatchPos = NodeR;\r
735 } else {\r
736 Index2 = mLevel[NodeR];\r
737 mMatchPos = (NODE) (mPosition[NodeR] & (UINT32)~PERC_FLAG);\r
738 }\r
739\r
740 if (mMatchPos >= mPos) {\r
741 mMatchPos -= WNDSIZ;\r
742 }\r
743\r
744 t1 = &mText[mPos + mMatchLen];\r
745 t2 = &mText[mMatchPos + mMatchLen];\r
746 while (mMatchLen < Index2) {\r
747 if (*t1 != *t2) {\r
748 Split (NodeR);\r
749 return ;\r
750 }\r
751\r
752 mMatchLen++;\r
753 t1++;\r
754 t2++;\r
755 }\r
756\r
757 if (mMatchLen >= MAXMATCH) {\r
758 break;\r
759 }\r
760\r
761 mPosition[NodeR] = mPos;\r
762 NodeQ = NodeR;\r
763 NodeR = Child (NodeQ, *t1);\r
764 if (NodeR == NIL) {\r
765 MakeChild (NodeQ, *t1, mPos);\r
766 return ;\r
767 }\r
768\r
769 mMatchLen++;\r
770 }\r
771\r
772 NodeT = mPrev[NodeR];\r
773 mPrev[mPos] = NodeT;\r
774 mNext[NodeT] = mPos;\r
775 NodeT = mNext[NodeR];\r
776 mNext[mPos] = NodeT;\r
777 mPrev[NodeT] = mPos;\r
778 mParent[mPos] = NodeQ;\r
779 mParent[NodeR] = NIL;\r
780\r
781 //\r
782 // Special usage of 'next'\r
783 //\r
784 mNext[NodeR] = mPos;\r
785\r
786}\r
787\r
788STATIC\r
789VOID\r
790DeleteNode (\r
791 VOID\r
792 )\r
793/*++\r
794\r
795Routine Description:\r
796\r
797 Delete outdated string info. (The Usage of PERC_FLAG\r
798 ensures a clean deletion)\r
799 \r
800Arguments: (VOID)\r
801\r
802Returns: (VOID)\r
803\r
804--*/\r
805{\r
806 NODE NodeQ;\r
807 NODE NodeR;\r
808 NODE NodeS;\r
809 NODE NodeT;\r
810 NODE NodeU;\r
811\r
812 if (mParent[mPos] == NIL) {\r
813 return ;\r
814 }\r
815\r
816 NodeR = mPrev[mPos];\r
817 NodeS = mNext[mPos];\r
818 mNext[NodeR] = NodeS;\r
819 mPrev[NodeS] = NodeR;\r
820 NodeR = mParent[mPos];\r
821 mParent[mPos] = NIL;\r
822 if (NodeR >= WNDSIZ) {\r
823 return ;\r
824 }\r
825\r
826 mChildCount[NodeR]--;\r
827 if (mChildCount[NodeR] > 1) {\r
828 return ;\r
829 }\r
830\r
831 NodeT = (NODE) (mPosition[NodeR] & (UINT32)~PERC_FLAG);\r
832 if (NodeT >= mPos) {\r
833 NodeT -= WNDSIZ;\r
834 }\r
835\r
836 NodeS = NodeT;\r
837 NodeQ = mParent[NodeR];\r
838 NodeU = mPosition[NodeQ];\r
839 while (NodeU & (UINT32) PERC_FLAG) {\r
840 NodeU &= (UINT32)~PERC_FLAG;\r
841 if (NodeU >= mPos) {\r
842 NodeU -= WNDSIZ;\r
843 }\r
844\r
845 if (NodeU > NodeS) {\r
846 NodeS = NodeU;\r
847 }\r
848\r
849 mPosition[NodeQ] = (NODE) (NodeS | WNDSIZ);\r
850 NodeQ = mParent[NodeQ];\r
851 NodeU = mPosition[NodeQ];\r
852 }\r
853\r
854 if (NodeQ < WNDSIZ) {\r
855 if (NodeU >= mPos) {\r
856 NodeU -= WNDSIZ;\r
857 }\r
858\r
859 if (NodeU > NodeS) {\r
860 NodeS = NodeU;\r
861 }\r
862\r
863 mPosition[NodeQ] = (NODE) (NodeS | WNDSIZ | (UINT32) PERC_FLAG);\r
864 }\r
865\r
866 NodeS = Child (NodeR, mText[NodeT + mLevel[NodeR]]);\r
867 NodeT = mPrev[NodeS];\r
868 NodeU = mNext[NodeS];\r
869 mNext[NodeT] = NodeU;\r
870 mPrev[NodeU] = NodeT;\r
871 NodeT = mPrev[NodeR];\r
872 mNext[NodeT] = NodeS;\r
873 mPrev[NodeS] = NodeT;\r
874 NodeT = mNext[NodeR];\r
875 mPrev[NodeT] = NodeS;\r
876 mNext[NodeS] = NodeT;\r
877 mParent[NodeS] = mParent[NodeR];\r
878 mParent[NodeR] = NIL;\r
879 mNext[NodeR] = mAvail;\r
880 mAvail = NodeR;\r
881}\r
882\r
883STATIC\r
884VOID\r
885GetNextMatch (\r
886 VOID\r
887 )\r
888/*++\r
889\r
890Routine Description:\r
891\r
892 Advance the current position (read in new data if needed).\r
893 Delete outdated string info. Find a match string for current position.\r
894\r
895Arguments: (VOID)\r
896\r
897Returns: (VOID)\r
898\r
899--*/\r
900{\r
901 INT32 Number;\r
902\r
903 mRemainder--;\r
904 mPos++;\r
905 if (mPos == WNDSIZ * 2) {\r
906 memmove (&mText[0], &mText[WNDSIZ], WNDSIZ + MAXMATCH);\r
907 Number = FreadCrc (&mText[WNDSIZ + MAXMATCH], WNDSIZ);\r
908 mRemainder += Number;\r
909 mPos = WNDSIZ;\r
910 }\r
911\r
912 DeleteNode ();\r
913 InsertNode ();\r
914}\r
915\r
916STATIC\r
917EFI_STATUS\r
918Encode (\r
919 VOID\r
920 )\r
921/*++\r
922\r
923Routine Description:\r
924\r
925 The main controlling routine for compression process.\r
926\r
927Arguments: (VOID)\r
928\r
929Returns:\r
930 \r
931 EFI_SUCCESS - The compression is successful\r
932 EFI_OUT_0F_RESOURCES - Not enough memory for compression process\r
933\r
934--*/\r
935{\r
936 EFI_STATUS Status;\r
937 INT32 LastMatchLen;\r
938 NODE LastMatchPos;\r
939\r
940 Status = AllocateMemory ();\r
941 if (EFI_ERROR (Status)) {\r
942 FreeMemory ();\r
943 return Status;\r
944 }\r
945\r
946 InitSlide ();\r
947\r
948 HufEncodeStart ();\r
949\r
950 mRemainder = FreadCrc (&mText[WNDSIZ], WNDSIZ + MAXMATCH);\r
951\r
952 mMatchLen = 0;\r
953 mPos = WNDSIZ;\r
954 InsertNode ();\r
955 if (mMatchLen > mRemainder) {\r
956 mMatchLen = mRemainder;\r
957 }\r
958\r
959 while (mRemainder > 0) {\r
960 LastMatchLen = mMatchLen;\r
961 LastMatchPos = mMatchPos;\r
962 GetNextMatch ();\r
963 if (mMatchLen > mRemainder) {\r
964 mMatchLen = mRemainder;\r
965 }\r
966\r
967 if (mMatchLen > LastMatchLen || LastMatchLen < THRESHOLD) {\r
968 //\r
969 // Not enough benefits are gained by outputting a pointer,\r
970 // so just output the original character\r
971 //\r
972 Output (mText[mPos - 1], 0);\r
973\r
974 } else {\r
975\r
976 if (LastMatchLen == THRESHOLD) {\r
977 if (((mPos - LastMatchPos - 2) & (WNDSIZ - 1)) > (1U << 11)) {\r
978 Output (mText[mPos - 1], 0);\r
979 continue;\r
980 }\r
981 }\r
982 //\r
983 // Outputting a pointer is beneficial enough, do it.\r
984 //\r
985 Output (\r
986 LastMatchLen + (UINT8_MAX + 1 - THRESHOLD),\r
987 (mPos - LastMatchPos - 2) & (WNDSIZ - 1)\r
988 );\r
989 LastMatchLen--;\r
990 while (LastMatchLen > 0) {\r
991 GetNextMatch ();\r
992 LastMatchLen--;\r
993 }\r
994\r
995 if (mMatchLen > mRemainder) {\r
996 mMatchLen = mRemainder;\r
997 }\r
998 }\r
999 }\r
1000\r
1001 HufEncodeEnd ();\r
1002 FreeMemory ();\r
1003 return EFI_SUCCESS;\r
1004}\r
1005\r
1006STATIC\r
1007VOID\r
1008CountTFreq (\r
1009 VOID\r
1010 )\r
1011/*++\r
1012\r
1013Routine Description:\r
1014\r
1015 Count the frequencies for the Extra Set\r
1016 \r
1017Arguments: (VOID)\r
1018\r
1019Returns: (VOID)\r
1020\r
1021--*/\r
1022{\r
1023 INT32 Index;\r
1024 INT32 Index3;\r
1025 INT32 Number;\r
1026 INT32 Count;\r
1027\r
1028 for (Index = 0; Index < NT; Index++) {\r
1029 mTFreq[Index] = 0;\r
1030 }\r
1031\r
1032 Number = NC;\r
1033 while (Number > 0 && mCLen[Number - 1] == 0) {\r
1034 Number--;\r
1035 }\r
1036\r
1037 Index = 0;\r
1038 while (Index < Number) {\r
1039 Index3 = mCLen[Index++];\r
1040 if (Index3 == 0) {\r
1041 Count = 1;\r
1042 while (Index < Number && mCLen[Index] == 0) {\r
1043 Index++;\r
1044 Count++;\r
1045 }\r
1046\r
1047 if (Count <= 2) {\r
1048 mTFreq[0] = (UINT16) (mTFreq[0] + Count);\r
1049 } else if (Count <= 18) {\r
1050 mTFreq[1]++;\r
1051 } else if (Count == 19) {\r
1052 mTFreq[0]++;\r
1053 mTFreq[1]++;\r
1054 } else {\r
1055 mTFreq[2]++;\r
1056 }\r
1057 } else {\r
1058 mTFreq[Index3 + 2]++;\r
1059 }\r
1060 }\r
1061}\r
1062\r
1063STATIC\r
1064VOID\r
1065WritePTLen (\r
1066 IN INT32 Number,\r
1067 IN INT32 nbit,\r
1068 IN INT32 Special\r
1069 )\r
1070/*++\r
1071\r
1072Routine Description:\r
1073\r
1074 Outputs the code length array for the Extra Set or the Position Set.\r
1075 \r
1076Arguments:\r
1077\r
1078 Number - the number of symbols\r
1079 nbit - the number of bits needed to represent 'n'\r
1080 Special - the special symbol that needs to be take care of\r
1081 \r
1082Returns: (VOID)\r
1083\r
1084--*/\r
1085{\r
1086 INT32 Index;\r
1087 INT32 Index3;\r
1088\r
1089 while (Number > 0 && mPTLen[Number - 1] == 0) {\r
1090 Number--;\r
1091 }\r
1092\r
1093 PutBits (nbit, Number);\r
1094 Index = 0;\r
1095 while (Index < Number) {\r
1096 Index3 = mPTLen[Index++];\r
1097 if (Index3 <= 6) {\r
1098 PutBits (3, Index3);\r
1099 } else {\r
1100 PutBits (Index3 - 3, (1U << (Index3 - 3)) - 2);\r
1101 }\r
1102\r
1103 if (Index == Special) {\r
1104 while (Index < 6 && mPTLen[Index] == 0) {\r
1105 Index++;\r
1106 }\r
1107\r
1108 PutBits (2, (Index - 3) & 3);\r
1109 }\r
1110 }\r
1111}\r
1112\r
1113STATIC\r
1114VOID\r
1115WriteCLen (\r
1116 VOID\r
1117 )\r
1118/*++\r
1119\r
1120Routine Description:\r
1121\r
1122 Outputs the code length array for Char&Length Set\r
1123 \r
1124Arguments: (VOID)\r
1125\r
1126Returns: (VOID)\r
1127\r
1128--*/\r
1129{\r
1130 INT32 Index;\r
1131 INT32 Index3;\r
1132 INT32 Number;\r
1133 INT32 Count;\r
1134\r
1135 Number = NC;\r
1136 while (Number > 0 && mCLen[Number - 1] == 0) {\r
1137 Number--;\r
1138 }\r
1139\r
1140 PutBits (CBIT, Number);\r
1141 Index = 0;\r
1142 while (Index < Number) {\r
1143 Index3 = mCLen[Index++];\r
1144 if (Index3 == 0) {\r
1145 Count = 1;\r
1146 while (Index < Number && mCLen[Index] == 0) {\r
1147 Index++;\r
1148 Count++;\r
1149 }\r
1150\r
1151 if (Count <= 2) {\r
1152 for (Index3 = 0; Index3 < Count; Index3++) {\r
1153 PutBits (mPTLen[0], mPTCode[0]);\r
1154 }\r
1155 } else if (Count <= 18) {\r
1156 PutBits (mPTLen[1], mPTCode[1]);\r
1157 PutBits (4, Count - 3);\r
1158 } else if (Count == 19) {\r
1159 PutBits (mPTLen[0], mPTCode[0]);\r
1160 PutBits (mPTLen[1], mPTCode[1]);\r
1161 PutBits (4, 15);\r
1162 } else {\r
1163 PutBits (mPTLen[2], mPTCode[2]);\r
1164 PutBits (CBIT, Count - 20);\r
1165 }\r
1166 } else {\r
1167 PutBits (mPTLen[Index3 + 2], mPTCode[Index3 + 2]);\r
1168 }\r
1169 }\r
1170}\r
1171\r
1172STATIC\r
1173VOID\r
1174EncodeC (\r
1175 IN INT32 Value\r
1176 )\r
1177{\r
1178 PutBits (mCLen[Value], mCCode[Value]);\r
1179}\r
1180\r
1181STATIC\r
1182VOID\r
1183EncodeP (\r
1184 IN UINT32 Value\r
1185 )\r
1186{\r
1187 UINT32 Index;\r
1188 UINT32 NodeQ;\r
1189\r
1190 Index = 0;\r
1191 NodeQ = Value;\r
1192 while (NodeQ) {\r
1193 NodeQ >>= 1;\r
1194 Index++;\r
1195 }\r
1196\r
1197 PutBits (mPTLen[Index], mPTCode[Index]);\r
1198 if (Index > 1) {\r
1199 PutBits (Index - 1, Value & (0xFFFFFFFFU >> (32 - Index + 1)));\r
1200 }\r
1201}\r
1202\r
1203STATIC\r
1204VOID\r
1205SendBlock (\r
1206 VOID\r
1207 )\r
1208/*++\r
1209\r
1210Routine Description:\r
1211\r
1212 Huffman code the block and output it.\r
1213 \r
1214Arguments: \r
1215 (VOID)\r
1216\r
1217Returns: \r
1218 (VOID)\r
1219\r
1220--*/\r
1221{\r
1222 UINT32 Index;\r
1223 UINT32 Index2;\r
1224 UINT32 Index3;\r
1225 UINT32 Flags;\r
1226 UINT32 Root;\r
1227 UINT32 Pos;\r
1228 UINT32 Size;\r
1229 Flags = 0;\r
1230\r
1231 Root = MakeTree (NC, mCFreq, mCLen, mCCode);\r
1232 Size = mCFreq[Root];\r
1233 PutBits (16, Size);\r
1234 if (Root >= NC) {\r
1235 CountTFreq ();\r
1236 Root = MakeTree (NT, mTFreq, mPTLen, mPTCode);\r
1237 if (Root >= NT) {\r
1238 WritePTLen (NT, TBIT, 3);\r
1239 } else {\r
1240 PutBits (TBIT, 0);\r
1241 PutBits (TBIT, Root);\r
1242 }\r
1243\r
1244 WriteCLen ();\r
1245 } else {\r
1246 PutBits (TBIT, 0);\r
1247 PutBits (TBIT, 0);\r
1248 PutBits (CBIT, 0);\r
1249 PutBits (CBIT, Root);\r
1250 }\r
1251\r
1252 Root = MakeTree (NP, mPFreq, mPTLen, mPTCode);\r
1253 if (Root >= NP) {\r
1254 WritePTLen (NP, PBIT, -1);\r
1255 } else {\r
1256 PutBits (PBIT, 0);\r
1257 PutBits (PBIT, Root);\r
1258 }\r
1259\r
1260 Pos = 0;\r
1261 for (Index = 0; Index < Size; Index++) {\r
1262 if (Index % UINT8_BIT == 0) {\r
1263 Flags = mBuf[Pos++];\r
1264 } else {\r
1265 Flags <<= 1;\r
1266 }\r
1267\r
1268 if (Flags & (1U << (UINT8_BIT - 1))) {\r
1269 EncodeC (mBuf[Pos++] + (1U << UINT8_BIT));\r
1270 Index3 = mBuf[Pos++];\r
1271 for (Index2 = 0; Index2 < 3; Index2++) {\r
1272 Index3 <<= UINT8_BIT;\r
1273 Index3 += mBuf[Pos++];\r
1274 }\r
1275\r
1276 EncodeP (Index3);\r
1277 } else {\r
1278 EncodeC (mBuf[Pos++]);\r
1279 }\r
1280 }\r
1281\r
1282 for (Index = 0; Index < NC; Index++) {\r
1283 mCFreq[Index] = 0;\r
1284 }\r
1285\r
1286 for (Index = 0; Index < NP; Index++) {\r
1287 mPFreq[Index] = 0;\r
1288 }\r
1289}\r
1290\r
1291STATIC\r
1292VOID\r
1293Output (\r
1294 IN UINT32 CharC,\r
1295 IN UINT32 Pos\r
1296 )\r
1297/*++\r
1298\r
1299Routine Description:\r
1300\r
1301 Outputs an Original Character or a Pointer\r
1302\r
1303Arguments:\r
1304\r
1305 CharC - The original character or the 'String Length' element of a Pointer\r
1306 Pos - The 'Position' field of a Pointer\r
1307\r
1308Returns: (VOID)\r
1309\r
1310--*/\r
1311{\r
1312 STATIC UINT32 CPos;\r
1313\r
1314 if ((mOutputMask >>= 1) == 0) {\r
1315 mOutputMask = 1U << (UINT8_BIT - 1);\r
1316 //\r
1317 // Check the buffer overflow per outputing UINT8_BIT symbols\r
1318 // which is an Original Character or a Pointer. The biggest\r
1319 // symbol is a Pointer which occupies 5 bytes.\r
1320 //\r
1321 if (mOutputPos >= mBufSiz - 5 * UINT8_BIT) {\r
1322 SendBlock ();\r
1323 mOutputPos = 0;\r
1324 }\r
1325\r
1326 CPos = mOutputPos++;\r
1327 mBuf[CPos] = 0;\r
1328 }\r
1329\r
1330 mBuf[mOutputPos++] = (UINT8) CharC;\r
1331 mCFreq[CharC]++;\r
1332 if (CharC >= (1U << UINT8_BIT)) {\r
1333 mBuf[CPos] |= mOutputMask;\r
1334 mBuf[mOutputPos++] = (UINT8) (Pos >> 24);\r
1335 mBuf[mOutputPos++] = (UINT8) (Pos >> 16);\r
1336 mBuf[mOutputPos++] = (UINT8) (Pos >> (UINT8_BIT));\r
1337 mBuf[mOutputPos++] = (UINT8) Pos;\r
1338 CharC = 0;\r
1339 while (Pos) {\r
1340 Pos >>= 1;\r
1341 CharC++;\r
1342 }\r
1343\r
1344 mPFreq[CharC]++;\r
1345 }\r
1346}\r
1347\r
1348STATIC\r
1349VOID\r
1350HufEncodeStart (\r
1351 VOID\r
1352 )\r
1353{\r
1354 INT32 Index;\r
1355\r
1356 for (Index = 0; Index < NC; Index++) {\r
1357 mCFreq[Index] = 0;\r
1358 }\r
1359\r
1360 for (Index = 0; Index < NP; Index++) {\r
1361 mPFreq[Index] = 0;\r
1362 }\r
1363\r
1364 mOutputPos = mOutputMask = 0;\r
1365 InitPutBits ();\r
1366 return ;\r
1367}\r
1368\r
1369STATIC\r
1370VOID\r
1371HufEncodeEnd (\r
1372 VOID\r
1373 )\r
1374{\r
1375 SendBlock ();\r
1376\r
1377 //\r
1378 // Flush remaining bits\r
1379 //\r
1380 PutBits (UINT8_BIT - 1, 0);\r
1381\r
1382 return ;\r
1383}\r
1384\r
1385STATIC\r
1386VOID\r
1387MakeCrcTable (\r
1388 VOID\r
1389 )\r
1390{\r
1391 UINT32 Index;\r
1392 UINT32 Index2;\r
1393 UINT32 Temp;\r
1394\r
1395 for (Index = 0; Index <= UINT8_MAX; Index++) {\r
1396 Temp = Index;\r
1397 for (Index2 = 0; Index2 < UINT8_BIT; Index2++) {\r
1398 if (Temp & 1) {\r
1399 Temp = (Temp >> 1) ^ CRCPOLY;\r
1400 } else {\r
1401 Temp >>= 1;\r
1402 }\r
1403 }\r
1404\r
1405 mCrcTable[Index] = (UINT16) Temp;\r
1406 }\r
1407}\r
1408\r
1409STATIC\r
1410VOID\r
1411PutBits (\r
1412 IN INT32 Number,\r
1413 IN UINT32 Value\r
1414 )\r
1415/*++\r
1416\r
1417Routine Description:\r
1418\r
1419 Outputs rightmost n bits of x\r
1420\r
1421Arguments:\r
1422\r
1423 Number - the rightmost n bits of the data is used\r
1424 x - the data \r
1425\r
1426Returns: (VOID)\r
1427\r
1428--*/\r
1429{\r
1430 UINT8 Temp;\r
1431\r
1432 while (Number >= mBitCount) {\r
1433 //\r
1434 // Number -= mBitCount should never equal to 32\r
1435 //\r
1436 Temp = (UINT8) (mSubBitBuf | (Value >> (Number -= mBitCount)));\r
1437 if (mDst < mDstUpperLimit) {\r
1438 *mDst++ = Temp;\r
1439 }\r
1440\r
1441 mCompSize++;\r
1442 mSubBitBuf = 0;\r
1443 mBitCount = UINT8_BIT;\r
1444 }\r
1445\r
1446 mSubBitBuf |= Value << (mBitCount -= Number);\r
1447}\r
1448\r
1449STATIC\r
1450INT32\r
1451FreadCrc (\r
1452 OUT UINT8 *Pointer,\r
1453 IN INT32 Number\r
1454 )\r
1455/*++\r
1456\r
1457Routine Description:\r
1458\r
1459 Read in source data\r
1460 \r
1461Arguments:\r
1462\r
1463 Pointer - the buffer to hold the data\r
1464 Number - number of bytes to read\r
1465\r
1466Returns:\r
1467\r
1468 number of bytes actually read\r
1469 \r
1470--*/\r
1471{\r
1472 INT32 Index;\r
1473\r
1474 for (Index = 0; mSrc < mSrcUpperLimit && Index < Number; Index++) {\r
1475 *Pointer++ = *mSrc++;\r
1476 }\r
1477\r
1478 Number = Index;\r
1479\r
1480 Pointer -= Number;\r
1481 mOrigSize += Number;\r
1482 Index--;\r
1483 while (Index >= 0) {\r
1484 UPDATE_CRC (*Pointer++);\r
1485 Index--;\r
1486 }\r
1487\r
1488 return Number;\r
1489}\r
1490\r
1491STATIC\r
1492VOID\r
1493InitPutBits (\r
1494 VOID\r
1495 )\r
1496{\r
1497 mBitCount = UINT8_BIT;\r
1498 mSubBitBuf = 0;\r
1499}\r
1500\r
1501STATIC\r
1502VOID\r
1503CountLen (\r
1504 IN INT32 Index\r
1505 )\r
1506/*++\r
1507\r
1508Routine Description:\r
1509\r
1510 Count the number of each code length for a Huffman tree.\r
1511 \r
1512Arguments:\r
1513\r
1514 Index - the top node\r
1515 \r
1516Returns: (VOID)\r
1517\r
1518--*/\r
1519{\r
1520 STATIC INT32 Depth = 0;\r
1521\r
1522 if (Index < mN) {\r
1523 mLenCnt[(Depth < 16) ? Depth : 16]++;\r
1524 } else {\r
1525 Depth++;\r
1526 CountLen (mLeft[Index]);\r
1527 CountLen (mRight[Index]);\r
1528 Depth--;\r
1529 }\r
1530}\r
1531\r
1532STATIC\r
1533VOID\r
1534MakeLen (\r
1535 IN INT32 Root\r
1536 )\r
1537/*++\r
1538\r
1539Routine Description:\r
1540\r
1541 Create code length array for a Huffman tree\r
1542 \r
1543Arguments:\r
1544\r
1545 Root - the root of the tree\r
1546 \r
1547Returns:\r
1548\r
1549 VOID\r
1550\r
1551--*/\r
1552{\r
1553 INT32 Index;\r
1554 INT32 Index3;\r
1555 UINT32 Cum;\r
1556\r
1557 for (Index = 0; Index <= 16; Index++) {\r
1558 mLenCnt[Index] = 0;\r
1559 }\r
1560\r
1561 CountLen (Root);\r
1562\r
1563 //\r
1564 // Adjust the length count array so that\r
1565 // no code will be generated longer than its designated length\r
1566 //\r
1567 Cum = 0;\r
1568 for (Index = 16; Index > 0; Index--) {\r
1569 Cum += mLenCnt[Index] << (16 - Index);\r
1570 }\r
1571\r
1572 while (Cum != (1U << 16)) {\r
1573 mLenCnt[16]--;\r
1574 for (Index = 15; Index > 0; Index--) {\r
1575 if (mLenCnt[Index] != 0) {\r
1576 mLenCnt[Index]--;\r
1577 mLenCnt[Index + 1] += 2;\r
1578 break;\r
1579 }\r
1580 }\r
1581\r
1582 Cum--;\r
1583 }\r
1584\r
1585 for (Index = 16; Index > 0; Index--) {\r
1586 Index3 = mLenCnt[Index];\r
1587 Index3--;\r
1588 while (Index3 >= 0) {\r
1589 mLen[*mSortPtr++] = (UINT8) Index;\r
1590 Index3--;\r
1591 }\r
1592 }\r
1593}\r
1594\r
1595STATIC\r
1596VOID\r
1597DownHeap (\r
1598 IN INT32 Index\r
1599 )\r
1600{\r
1601 INT32 Index2;\r
1602 INT32 Index3;\r
1603\r
1604 //\r
1605 // priority queue: send Index-th entry down heap\r
1606 //\r
1607 Index3 = mHeap[Index];\r
1608 Index2 = 2 * Index;\r
1609 while (Index2 <= mHeapSize) {\r
1610 if (Index2 < mHeapSize && mFreq[mHeap[Index2]] > mFreq[mHeap[Index2 + 1]]) {\r
1611 Index2++;\r
1612 }\r
1613\r
1614 if (mFreq[Index3] <= mFreq[mHeap[Index2]]) {\r
1615 break;\r
1616 }\r
1617\r
1618 mHeap[Index] = mHeap[Index2];\r
1619 Index = Index2;\r
1620 Index2 = 2 * Index;\r
1621 }\r
1622\r
1623 mHeap[Index] = (INT16) Index3;\r
1624}\r
1625\r
1626STATIC\r
1627VOID\r
1628MakeCode (\r
1629 IN INT32 Number,\r
1630 IN UINT8 Len[ ],\r
1631 OUT UINT16 Code[]\r
1632 )\r
1633/*++\r
1634\r
1635Routine Description:\r
1636\r
1637 Assign code to each symbol based on the code length array\r
1638 \r
1639Arguments:\r
1640\r
1641 Number - number of symbols\r
1642 Len - the code length array\r
1643 Code - stores codes for each symbol\r
1644\r
1645Returns: (VOID)\r
1646\r
1647--*/\r
1648{\r
1649 INT32 Index;\r
1650 UINT16 Start[18];\r
1651\r
1652 Start[1] = 0;\r
1653 for (Index = 1; Index <= 16; Index++) {\r
1654 Start[Index + 1] = (UINT16) ((Start[Index] + mLenCnt[Index]) << 1);\r
1655 }\r
1656\r
1657 for (Index = 0; Index < Number; Index++) {\r
1658 Code[Index] = Start[Len[Index]]++;\r
1659 }\r
1660}\r
1661\r
1662STATIC\r
1663INT32\r
1664MakeTree (\r
1665 IN INT32 NParm,\r
1666 IN UINT16 FreqParm[],\r
1667 OUT UINT8 LenParm[ ],\r
1668 OUT UINT16 CodeParm[]\r
1669 )\r
1670/*++\r
1671\r
1672Routine Description:\r
1673\r
1674 Generates Huffman codes given a frequency distribution of symbols\r
1675 \r
1676Arguments:\r
1677\r
1678 NParm - number of symbols\r
1679 FreqParm - frequency of each symbol\r
1680 LenParm - code length for each symbol\r
1681 CodeParm - code for each symbol\r
1682 \r
1683Returns:\r
1684\r
1685 Root of the Huffman tree.\r
1686 \r
1687--*/\r
1688{\r
1689 INT32 Index;\r
1690 INT32 Index2;\r
1691 INT32 Index3;\r
1692 INT32 Avail;\r
1693\r
1694 //\r
1695 // make tree, calculate len[], return root\r
1696 //\r
1697 mN = NParm;\r
1698 mFreq = FreqParm;\r
1699 mLen = LenParm;\r
1700 Avail = mN;\r
1701 mHeapSize = 0;\r
1702 mHeap[1] = 0;\r
1703 for (Index = 0; Index < mN; Index++) {\r
1704 mLen[Index] = 0;\r
1705 if (mFreq[Index]) {\r
1706 mHeapSize++;\r
1707 mHeap[mHeapSize] = (INT16) Index;\r
1708 }\r
1709 }\r
1710\r
1711 if (mHeapSize < 2) {\r
1712 CodeParm[mHeap[1]] = 0;\r
1713 return mHeap[1];\r
1714 }\r
1715\r
1716 for (Index = mHeapSize / 2; Index >= 1; Index--) {\r
1717 //\r
1718 // make priority queue\r
1719 //\r
1720 DownHeap (Index);\r
1721 }\r
1722\r
1723 mSortPtr = CodeParm;\r
1724 do {\r
1725 Index = mHeap[1];\r
1726 if (Index < mN) {\r
1727 *mSortPtr++ = (UINT16) Index;\r
1728 }\r
1729\r
1730 mHeap[1] = mHeap[mHeapSize--];\r
1731 DownHeap (1);\r
1732 Index2 = mHeap[1];\r
1733 if (Index2 < mN) {\r
1734 *mSortPtr++ = (UINT16) Index2;\r
1735 }\r
1736\r
1737 Index3 = Avail++;\r
1738 mFreq[Index3] = (UINT16) (mFreq[Index] + mFreq[Index2]);\r
1739 mHeap[1] = (INT16) Index3;\r
1740 DownHeap (1);\r
1741 mLeft[Index3] = (UINT16) Index;\r
1742 mRight[Index3] = (UINT16) Index2;\r
1743 } while (mHeapSize > 1);\r
1744\r
1745 mSortPtr = CodeParm;\r
1746 MakeLen (Index3);\r
1747 MakeCode (NParm, LenParm, CodeParm);\r
1748\r
1749 //\r
1750 // return root\r
1751 //\r
1752 return Index3;\r
1753}\r
EFI Development Kit II mirror for PVE