]>
git.proxmox.com Git - mirror_edk2.git/blob - Tools/Source/TianoTools/Common/EfiCompress.c
3 Copyright (c) 2004, Intel Corporation
4 All rights reserved. This program and the accompanying materials
5 are licensed and made available under the terms and conditions of the BSD License
6 which accompanies this distribution. The full text of the license may be found at
7 http://opensource.org/licenses/bsd-license.php
9 THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
10 WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
18 Compression routine. The compression algorithm is a mixture of
19 LZ77 and Huffman coding. LZ77 transforms the source data into a
20 sequence of Original Characters and Pointers to repeated strings.
21 This sequence is further divided into Blocks and Huffman codings
22 are applied to each Block.
26 #include "EfiCompress.h"
36 #define WNDSIZ (1U << WNDBIT)
38 #define BLKSIZ (1U << 14) // 16 * 1024U
39 #define PERC_FLAG 0x80000000U
42 #define MAX_HASH_VAL (3 * WNDSIZ + (WNDSIZ / 512 + 1) * UINT8_MAX)
43 #define HASH(p, c) ((p) + ((c) << (WNDBIT - 9)) + WNDSIZ * 2)
44 #define CRCPOLY 0xA001
45 #define UPDATE_CRC(c) mCrc = mCrcTable[(mCrc ^ (c)) & 0xFF] ^ (mCrc >> UINT8_BIT)
48 // C: the Char&Len Set; P: the Position Set; T: the exTra Set
50 #define NC (UINT8_MAX + MAXMATCH + 2 - THRESHOLD)
52 #define NP (WNDBIT + 1)
54 #define NT (CODE_BIT + 3)
62 // Function Prototypes
64 STATIC VOID
PutDword(IN UINT32 Data
);
242 IN UINT16 FreqParm
[],
243 OUT UINT8 LenParm
[ ],
244 OUT UINT16 CodeParm
[]
250 static UINT8
*mSrc
, *mDst
, *mSrcUpperLimit
, *mDstUpperLimit
;
252 static UINT8
*mLevel
, *mText
, *mChildCount
, *mBuf
, mCLen
[NC
], mPTLen
[NPT
], *mLen
;
253 static INT16 mHeap
[NC
+ 1];
254 static INT32 mRemainder
, mMatchLen
, mBitCount
, mHeapSize
, mN
;
255 static UINT32 mBufSiz
= 0, mOutputPos
, mOutputMask
, mSubBitBuf
, mCrc
;
256 static UINT32 mCompSize
, mOrigSize
;
258 static UINT16
*mFreq
, *mSortPtr
, mLenCnt
[17], mLeft
[2 * NC
- 1], mRight
[2 * NC
- 1], mCrcTable
[UINT8_MAX
+ 1],
259 mCFreq
[2 * NC
- 1], mCTable
[4096], mCCode
[NC
], mPFreq
[2 * NP
- 1], mPTCode
[NPT
], mTFreq
[2 * NT
- 1];
261 static NODE mPos
, mMatchPos
, mAvail
, *mPosition
, *mParent
, *mPrev
, *mNext
= NULL
;
271 IN OUT UINT32
*DstSize
277 The main compression routine.
281 SrcBuffer - The buffer storing the source data
282 SrcSize - The size of source data
283 DstBuffer - The buffer to store the compressed data
284 DstSize - On input, the size of DstBuffer; On output,
285 the size of the actual compressed data.
289 EFI_BUFFER_TOO_SMALL - The DstBuffer is too small. In this case,
290 DstSize contains the size needed.
291 EFI_SUCCESS - Compression is successful.
292 EFI_OUT_OF_RESOURCES - No resource to complete function.
312 mSrcUpperLimit
= mSrc
+ SrcSize
;
314 mDstUpperLimit
= mDst
+*DstSize
;
321 mOrigSize
= mCompSize
= 0;
328 if (EFI_ERROR (Status
)) {
329 return EFI_OUT_OF_RESOURCES
;
332 // Null terminate the compressed data
334 if (mDst
< mDstUpperLimit
) {
338 // Fill in compressed size and original size
341 PutDword (mCompSize
+ 1);
342 PutDword (mOrigSize
);
347 if (mCompSize
+ 1 + 8 > *DstSize
) {
348 *DstSize
= mCompSize
+ 1 + 8;
349 return EFI_BUFFER_TOO_SMALL
;
351 *DstSize
= mCompSize
+ 1 + 8;
366 Put a dword to output stream
370 Data - the dword to put
376 if (mDst
< mDstUpperLimit
) {
377 *mDst
++ = (UINT8
) (((UINT8
) (Data
)) & 0xff);
380 if (mDst
< mDstUpperLimit
) {
381 *mDst
++ = (UINT8
) (((UINT8
) (Data
>> 0x08)) & 0xff);
384 if (mDst
< mDstUpperLimit
) {
385 *mDst
++ = (UINT8
) (((UINT8
) (Data
>> 0x10)) & 0xff);
388 if (mDst
< mDstUpperLimit
) {
389 *mDst
++ = (UINT8
) (((UINT8
) (Data
>> 0x18)) & 0xff);
402 Allocate memory spaces for data structures used in compression process
409 EFI_SUCCESS - Memory is allocated successfully
410 EFI_OUT_OF_RESOURCES - Allocation fails
416 mText
= malloc (WNDSIZ
* 2 + MAXMATCH
);
417 for (Index
= 0; Index
< WNDSIZ
* 2 + MAXMATCH
; Index
++) {
421 mLevel
= malloc ((WNDSIZ
+ UINT8_MAX
+ 1) * sizeof (*mLevel
));
422 mChildCount
= malloc ((WNDSIZ
+ UINT8_MAX
+ 1) * sizeof (*mChildCount
));
423 mPosition
= malloc ((WNDSIZ
+ UINT8_MAX
+ 1) * sizeof (*mPosition
));
424 mParent
= malloc (WNDSIZ
* 2 * sizeof (*mParent
));
425 mPrev
= malloc (WNDSIZ
* 2 * sizeof (*mPrev
));
426 mNext
= malloc ((MAX_HASH_VAL
+ 1) * sizeof (*mNext
));
429 mBuf
= malloc (mBufSiz
);
430 while (mBuf
== NULL
) {
431 mBufSiz
= (mBufSiz
/ 10U) * 9U;
432 if (mBufSiz
< 4 * 1024U) {
433 return EFI_OUT_OF_RESOURCES
;
436 mBuf
= malloc (mBufSiz
);
452 Called when compression is completed to free memory previously allocated.
464 if (mLevel
!= NULL
) {
468 if (mChildCount
!= NULL
) {
472 if (mPosition
!= NULL
) {
476 if (mParent
!= NULL
) {
504 Initialize String Info Log data structures
514 for (Index
= WNDSIZ
; Index
<= WNDSIZ
+ UINT8_MAX
; Index
++) {
516 mPosition
[Index
] = NIL
; /* sentinel */
519 for (Index
= WNDSIZ
; Index
< WNDSIZ
* 2; Index
++) {
520 mParent
[Index
] = NIL
;
524 for (Index
= 1; Index
< WNDSIZ
- 1; Index
++) {
525 mNext
[Index
] = (NODE
) (Index
+ 1);
528 mNext
[WNDSIZ
- 1] = NIL
;
529 for (Index
= WNDSIZ
* 2; Index
<= MAX_HASH_VAL
; Index
++) {
544 Find child node given the parent node and the edge character
548 NodeQ - the parent node
549 CharC - the edge character
553 The child node (NIL if not found)
559 NodeR
= mNext
[HASH (NodeQ
, CharC
)];
563 mParent
[NIL
] = NodeQ
;
564 while (mParent
[NodeR
] != NodeQ
) {
565 NodeR
= mNext
[NodeR
];
582 Create a new child for a given parent node.
586 Parent - the parent node
587 CharC - the edge character
588 Child - the child node
597 Node1
= (NODE
) HASH (Parent
, CharC
);
598 Node2
= mNext
[Node1
];
599 mNext
[Node1
] = Child
;
600 mNext
[Child
] = Node2
;
601 mPrev
[Node2
] = Child
;
602 mPrev
[Child
] = Node1
;
603 mParent
[Child
] = Parent
;
604 mChildCount
[Parent
]++;
620 Old - the node to split
631 mChildCount
[New
] = 0;
632 TempNode
= mPrev
[Old
];
633 mPrev
[New
] = TempNode
;
634 mNext
[TempNode
] = New
;
635 TempNode
= mNext
[Old
];
636 mNext
[New
] = TempNode
;
637 mPrev
[TempNode
] = New
;
638 mParent
[New
] = mParent
[Old
];
639 mLevel
[New
] = (UINT8
) mMatchLen
;
640 mPosition
[New
] = mPos
;
641 MakeChild (New
, mText
[mMatchPos
+ mMatchLen
], Old
);
642 MakeChild (New
, mText
[mPos
+ mMatchLen
], mPos
);
654 Insert string info for current position into the String Info Log
670 if (mMatchLen
>= 4) {
672 // We have just got a long match, the target tree
673 // can be located by MatchPos + 1. Travese the tree
674 // from bottom up to get to a proper starting point.
675 // The usage of PERC_FLAG ensures proper node deletion
676 // in DeleteNode() later.
679 NodeR
= (NODE
) ((mMatchPos
+ 1) | WNDSIZ
);
680 NodeQ
= mParent
[NodeR
];
681 while (NodeQ
== NIL
) {
682 NodeR
= mNext
[NodeR
];
683 NodeQ
= mParent
[NodeR
];
686 while (mLevel
[NodeQ
] >= mMatchLen
) {
688 NodeQ
= mParent
[NodeQ
];
692 while (mPosition
[NodeT
] < 0) {
693 mPosition
[NodeT
] = mPos
;
694 NodeT
= mParent
[NodeT
];
697 if (NodeT
< WNDSIZ
) {
698 mPosition
[NodeT
] = (NODE
) (mPos
| (UINT32
) PERC_FLAG
);
702 // Locate the target tree
704 NodeQ
= (NODE
) (mText
[mPos
] + WNDSIZ
);
705 CharC
= mText
[mPos
+ 1];
706 NodeR
= Child (NodeQ
, CharC
);
708 MakeChild (NodeQ
, CharC
, mPos
);
716 // Traverse down the tree to find a match.
717 // Update Position value along the route.
718 // Node split or creation is involved.
721 if (NodeR
>= WNDSIZ
) {
725 Index2
= mLevel
[NodeR
];
726 mMatchPos
= (NODE
) (mPosition
[NodeR
] & (UINT32
)~PERC_FLAG
);
729 if (mMatchPos
>= mPos
) {
733 t1
= &mText
[mPos
+ mMatchLen
];
734 t2
= &mText
[mMatchPos
+ mMatchLen
];
735 while (mMatchLen
< Index2
) {
746 if (mMatchLen
>= MAXMATCH
) {
750 mPosition
[NodeR
] = mPos
;
752 NodeR
= Child (NodeQ
, *t1
);
754 MakeChild (NodeQ
, *t1
, mPos
);
761 NodeT
= mPrev
[NodeR
];
764 NodeT
= mNext
[NodeR
];
767 mParent
[mPos
] = NodeQ
;
768 mParent
[NodeR
] = NIL
;
771 // Special usage of 'next'
786 Delete outdated string info. (The Usage of PERC_FLAG
787 ensures a clean deletion)
801 if (mParent
[mPos
] == NIL
) {
807 mNext
[NodeR
] = NodeS
;
808 mPrev
[NodeS
] = NodeR
;
809 NodeR
= mParent
[mPos
];
811 if (NodeR
>= WNDSIZ
) {
815 mChildCount
[NodeR
]--;
816 if (mChildCount
[NodeR
] > 1) {
820 NodeT
= (NODE
) (mPosition
[NodeR
] & (UINT32
)~PERC_FLAG
);
826 NodeQ
= mParent
[NodeR
];
827 NodeU
= mPosition
[NodeQ
];
828 while (NodeU
& (UINT32
) PERC_FLAG
) {
829 NodeU
&= (UINT32
)~PERC_FLAG
;
838 mPosition
[NodeQ
] = (NODE
) (NodeS
| WNDSIZ
);
839 NodeQ
= mParent
[NodeQ
];
840 NodeU
= mPosition
[NodeQ
];
843 if (NodeQ
< WNDSIZ
) {
852 mPosition
[NodeQ
] = (NODE
) (NodeS
| WNDSIZ
| (UINT32
) PERC_FLAG
);
855 NodeS
= Child (NodeR
, mText
[NodeT
+ mLevel
[NodeR
]]);
856 NodeT
= mPrev
[NodeS
];
857 NodeU
= mNext
[NodeS
];
858 mNext
[NodeT
] = NodeU
;
859 mPrev
[NodeU
] = NodeT
;
860 NodeT
= mPrev
[NodeR
];
861 mNext
[NodeT
] = NodeS
;
862 mPrev
[NodeS
] = NodeT
;
863 NodeT
= mNext
[NodeR
];
864 mPrev
[NodeT
] = NodeS
;
865 mNext
[NodeS
] = NodeT
;
866 mParent
[NodeS
] = mParent
[NodeR
];
867 mParent
[NodeR
] = NIL
;
868 mNext
[NodeR
] = mAvail
;
881 Advance the current position (read in new data if needed).
882 Delete outdated string info. Find a match string for current position.
894 if (mPos
== WNDSIZ
* 2) {
895 memmove (&mText
[0], &mText
[WNDSIZ
], WNDSIZ
+ MAXMATCH
);
896 Number
= FreadCrc (&mText
[WNDSIZ
+ MAXMATCH
], WNDSIZ
);
897 mRemainder
+= Number
;
914 The main controlling routine for compression process.
920 EFI_SUCCESS - The compression is successful
921 EFI_OUT_0F_RESOURCES - Not enough memory for compression process
929 Status
= AllocateMemory ();
930 if (EFI_ERROR (Status
)) {
939 mRemainder
= FreadCrc (&mText
[WNDSIZ
], WNDSIZ
+ MAXMATCH
);
944 if (mMatchLen
> mRemainder
) {
945 mMatchLen
= mRemainder
;
948 while (mRemainder
> 0) {
949 LastMatchLen
= mMatchLen
;
950 LastMatchPos
= mMatchPos
;
952 if (mMatchLen
> mRemainder
) {
953 mMatchLen
= mRemainder
;
956 if (mMatchLen
> LastMatchLen
|| LastMatchLen
< THRESHOLD
) {
958 // Not enough benefits are gained by outputting a pointer,
959 // so just output the original character
961 Output (mText
[mPos
- 1], 0);
965 if (LastMatchLen
== THRESHOLD
) {
966 if (((mPos
- LastMatchPos
- 2) & (WNDSIZ
- 1)) > (1U << 11)) {
967 Output (mText
[mPos
- 1], 0);
972 // Outputting a pointer is beneficial enough, do it.
975 LastMatchLen
+ (UINT8_MAX
+ 1 - THRESHOLD
),
976 (mPos
- LastMatchPos
- 2) & (WNDSIZ
- 1)
979 while (LastMatchLen
> 0) {
984 if (mMatchLen
> mRemainder
) {
985 mMatchLen
= mRemainder
;
1002 Routine Description:
1004 Count the frequencies for the Extra Set
1017 for (Index
= 0; Index
< NT
; Index
++) {
1022 while (Number
> 0 && mCLen
[Number
- 1] == 0) {
1027 while (Index
< Number
) {
1028 Index3
= mCLen
[Index
++];
1031 while (Index
< Number
&& mCLen
[Index
] == 0) {
1037 mTFreq
[0] = (UINT16
) (mTFreq
[0] + Count
);
1038 } else if (Count
<= 18) {
1040 } else if (Count
== 19) {
1047 mTFreq
[Index3
+ 2]++;
1061 Routine Description:
1063 Outputs the code length array for the Extra Set or the Position Set.
1067 Number - the number of symbols
1068 nbit - the number of bits needed to represent 'n'
1069 Special - the special symbol that needs to be take care of
1078 while (Number
> 0 && mPTLen
[Number
- 1] == 0) {
1082 PutBits (nbit
, Number
);
1084 while (Index
< Number
) {
1085 Index3
= mPTLen
[Index
++];
1087 PutBits (3, Index3
);
1089 PutBits (Index3
- 3, (1U << (Index3
- 3)) - 2);
1092 if (Index
== Special
) {
1093 while (Index
< 6 && mPTLen
[Index
] == 0) {
1097 PutBits (2, (Index
- 3) & 3);
1109 Routine Description:
1111 Outputs the code length array for Char&Length Set
1125 while (Number
> 0 && mCLen
[Number
- 1] == 0) {
1129 PutBits (CBIT
, Number
);
1131 while (Index
< Number
) {
1132 Index3
= mCLen
[Index
++];
1135 while (Index
< Number
&& mCLen
[Index
] == 0) {
1141 for (Index3
= 0; Index3
< Count
; Index3
++) {
1142 PutBits (mPTLen
[0], mPTCode
[0]);
1144 } else if (Count
<= 18) {
1145 PutBits (mPTLen
[1], mPTCode
[1]);
1146 PutBits (4, Count
- 3);
1147 } else if (Count
== 19) {
1148 PutBits (mPTLen
[0], mPTCode
[0]);
1149 PutBits (mPTLen
[1], mPTCode
[1]);
1152 PutBits (mPTLen
[2], mPTCode
[2]);
1153 PutBits (CBIT
, Count
- 20);
1156 PutBits (mPTLen
[Index3
+ 2], mPTCode
[Index3
+ 2]);
1167 PutBits (mCLen
[Value
], mCCode
[Value
]);
1186 PutBits (mPTLen
[Index
], mPTCode
[Index
]);
1188 PutBits (Index
- 1, Value
& (0xFFFFFFFFU
>> (32 - Index
+ 1)));
1199 Routine Description:
1201 Huffman code the block and output it.
1220 Root
= MakeTree (NC
, mCFreq
, mCLen
, mCCode
);
1221 Size
= mCFreq
[Root
];
1225 Root
= MakeTree (NT
, mTFreq
, mPTLen
, mPTCode
);
1227 WritePTLen (NT
, TBIT
, 3);
1230 PutBits (TBIT
, Root
);
1238 PutBits (CBIT
, Root
);
1241 Root
= MakeTree (NP
, mPFreq
, mPTLen
, mPTCode
);
1243 WritePTLen (NP
, PBIT
, -1);
1246 PutBits (PBIT
, Root
);
1250 for (Index
= 0; Index
< Size
; Index
++) {
1251 if (Index
% UINT8_BIT
== 0) {
1252 Flags
= mBuf
[Pos
++];
1257 if (Flags
& (1U << (UINT8_BIT
- 1))) {
1258 EncodeC (mBuf
[Pos
++] + (1U << UINT8_BIT
));
1259 Index3
= mBuf
[Pos
++];
1260 for (Index2
= 0; Index2
< 3; Index2
++) {
1261 Index3
<<= UINT8_BIT
;
1262 Index3
+= mBuf
[Pos
++];
1267 EncodeC (mBuf
[Pos
++]);
1271 for (Index
= 0; Index
< NC
; Index
++) {
1275 for (Index
= 0; Index
< NP
; Index
++) {
1288 Routine Description:
1290 Outputs an Original Character or a Pointer
1294 CharC - The original character or the 'String Length' element of a Pointer
1295 Pos - The 'Position' field of a Pointer
1303 if ((mOutputMask
>>= 1) == 0) {
1304 mOutputMask
= 1U << (UINT8_BIT
- 1);
1306 // Check the buffer overflow per outputing UINT8_BIT symbols
1307 // which is an Original Character or a Pointer. The biggest
1308 // symbol is a Pointer which occupies 5 bytes.
1310 if (mOutputPos
>= mBufSiz
- 5 * UINT8_BIT
) {
1315 CPos
= mOutputPos
++;
1319 mBuf
[mOutputPos
++] = (UINT8
) CharC
;
1321 if (CharC
>= (1U << UINT8_BIT
)) {
1322 mBuf
[CPos
] |= mOutputMask
;
1323 mBuf
[mOutputPos
++] = (UINT8
) (Pos
>> 24);
1324 mBuf
[mOutputPos
++] = (UINT8
) (Pos
>> 16);
1325 mBuf
[mOutputPos
++] = (UINT8
) (Pos
>> (UINT8_BIT
));
1326 mBuf
[mOutputPos
++] = (UINT8
) Pos
;
1345 for (Index
= 0; Index
< NC
; Index
++) {
1349 for (Index
= 0; Index
< NP
; Index
++) {
1353 mOutputPos
= mOutputMask
= 0;
1367 // Flush remaining bits
1369 PutBits (UINT8_BIT
- 1, 0);
1384 for (Index
= 0; Index
<= UINT8_MAX
; Index
++) {
1386 for (Index2
= 0; Index2
< UINT8_BIT
; Index2
++) {
1388 Temp
= (Temp
>> 1) ^ CRCPOLY
;
1394 mCrcTable
[Index
] = (UINT16
) Temp
;
1406 Routine Description:
1408 Outputs rightmost n bits of x
1412 Number - the rightmost n bits of the data is used
1421 while (Number
>= mBitCount
) {
1423 // Number -= mBitCount should never equal to 32
1425 Temp
= (UINT8
) (mSubBitBuf
| (Value
>> (Number
-= mBitCount
)));
1426 if (mDst
< mDstUpperLimit
) {
1432 mBitCount
= UINT8_BIT
;
1435 mSubBitBuf
|= Value
<< (mBitCount
-= Number
);
1446 Routine Description:
1452 Pointer - the buffer to hold the data
1453 Number - number of bytes to read
1457 number of bytes actually read
1463 for (Index
= 0; mSrc
< mSrcUpperLimit
&& Index
< Number
; Index
++) {
1464 *Pointer
++ = *mSrc
++;
1470 mOrigSize
+= Number
;
1472 while (Index
>= 0) {
1473 UPDATE_CRC (*Pointer
++);
1486 mBitCount
= UINT8_BIT
;
1497 Routine Description:
1499 Count the number of each code length for a Huffman tree.
1503 Index - the top node
1509 static INT32 Depth
= 0;
1512 mLenCnt
[(Depth
< 16) ? Depth
: 16]++;
1515 CountLen (mLeft
[Index
]);
1516 CountLen (mRight
[Index
]);
1528 Routine Description:
1530 Create code length array for a Huffman tree
1534 Root - the root of the tree
1546 for (Index
= 0; Index
<= 16; Index
++) {
1553 // Adjust the length count array so that
1554 // no code will be generated longer than its designated length
1557 for (Index
= 16; Index
> 0; Index
--) {
1558 Cum
+= mLenCnt
[Index
] << (16 - Index
);
1561 while (Cum
!= (1U << 16)) {
1563 for (Index
= 15; Index
> 0; Index
--) {
1564 if (mLenCnt
[Index
] != 0) {
1566 mLenCnt
[Index
+ 1] += 2;
1574 for (Index
= 16; Index
> 0; Index
--) {
1575 Index3
= mLenCnt
[Index
];
1577 while (Index3
>= 0) {
1578 mLen
[*mSortPtr
++] = (UINT8
) Index
;
1594 // priority queue: send Index-th entry down heap
1596 Index3
= mHeap
[Index
];
1598 while (Index2
<= mHeapSize
) {
1599 if (Index2
< mHeapSize
&& mFreq
[mHeap
[Index2
]] > mFreq
[mHeap
[Index2
+ 1]]) {
1603 if (mFreq
[Index3
] <= mFreq
[mHeap
[Index2
]]) {
1607 mHeap
[Index
] = mHeap
[Index2
];
1612 mHeap
[Index
] = (INT16
) Index3
;
1624 Routine Description:
1626 Assign code to each symbol based on the code length array
1630 Number - number of symbols
1631 Len - the code length array
1632 Code - stores codes for each symbol
1642 for (Index
= 1; Index
<= 16; Index
++) {
1643 Start
[Index
+ 1] = (UINT16
) ((Start
[Index
] + mLenCnt
[Index
]) << 1);
1646 for (Index
= 0; Index
< Number
; Index
++) {
1647 Code
[Index
] = Start
[Len
[Index
]]++;
1655 IN UINT16 FreqParm
[],
1656 OUT UINT8 LenParm
[ ],
1657 OUT UINT16 CodeParm
[]
1661 Routine Description:
1663 Generates Huffman codes given a frequency distribution of symbols
1667 NParm - number of symbols
1668 FreqParm - frequency of each symbol
1669 LenParm - code length for each symbol
1670 CodeParm - code for each symbol
1674 Root of the Huffman tree.
1684 // make tree, calculate len[], return root
1692 for (Index
= 0; Index
< mN
; Index
++) {
1696 mHeap
[mHeapSize
] = (INT16
) Index
;
1700 if (mHeapSize
< 2) {
1701 CodeParm
[mHeap
[1]] = 0;
1705 for (Index
= mHeapSize
/ 2; Index
>= 1; Index
--) {
1707 // make priority queue
1712 mSortPtr
= CodeParm
;
1716 *mSortPtr
++ = (UINT16
) Index
;
1719 mHeap
[1] = mHeap
[mHeapSize
--];
1723 *mSortPtr
++ = (UINT16
) Index2
;
1727 mFreq
[Index3
] = (UINT16
) (mFreq
[Index
] + mFreq
[Index2
]);
1728 mHeap
[1] = (INT16
) Index3
;
1730 mLeft
[Index3
] = (UINT16
) Index
;
1731 mRight
[Index3
] = (UINT16
) Index2
;
1732 } while (mHeapSize
> 1);
1734 mSortPtr
= CodeParm
;
1736 MakeCode (NParm
, LenParm
, CodeParm
);