Intel Extensible Firmware Interface - Manual (Page 991)

Compression Source Code
Version 1.10 12/01/02 H-27
STATIC
INT32
MakeTree (
IN INT32 NParm,
IN UINT16 FreqParm[],
OUT UINT8 LenParm[],
OUT UINT16 CodeParm[]
)
/*++
Routine Description:
Generates Huffman codes given a frequency distribution of symbols
Arguments:
NParm - number of symbols
FreqParm - frequency of each symbol
LenParm - code length for each symbol
CodeParm - code for each symbol
Returns:
Root of the Huffman tree.
--*/
{
INT32 i, j, k, Avail;
//
// make tree, calculate len[], return root
//
mN = NParm;
mFreq = FreqParm;
mLen = LenParm;
Avail = mN;
mHeapSize = 0;
mHeap[1] = 0;
for (i = 0; i < mN; i++) {
mLen[i] = 0;
if (mFreq[i]) {
mHeap[++mHeapSize] = (INT16)i;
}
}
if (mHeapSize < 2) {
CodeParm[mHeap[1]] = 0;
return mHeap[1];
}
for (i = mHeapSize / 2; i >= 1; i--) {
//
// make priority queue
//
DownHeap(i);
}
mSortPtr = CodeParm;
do {
i = mHeap[1];