]>
git.proxmox.com Git - mirror_edk2.git/blob - BaseTools/Source/C/Common/TianoCompress.c
2 Compression routine. The compression algorithm is a mixture of LZ77 and Huffman
3 coding. LZ77 transforms the source data into a sequence of Original Characters
4 and Pointers to repeated strings. This sequence is further divided into Blocks
5 and Huffman codings are applied to each Block.
7 Copyright (c) 2006 - 2016, Intel Corporation. All rights reserved.<BR>
8 This program and the accompanying materials
9 are licensed and made available under the terms and conditions of the BSD License
10 which accompanies this distribution. The full text of the license may be found at
11 http://opensource.org/licenses/bsd-license.php
13 THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
14 WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
25 #define UINT8_MAX 0xff
30 #define WNDSIZ (1U << WNDBIT)
32 #define BLKSIZ (1U << 14) // 16 * 1024U
33 #define PERC_FLAG 0x80000000U
36 #define MAX_HASH_VAL (3 * WNDSIZ + (WNDSIZ / 512 + 1) * UINT8_MAX)
37 #define HASH(p, c) ((p) + ((c) << (WNDBIT - 9)) + WNDSIZ * 2)
38 #define CRCPOLY 0xA001
39 #define UPDATE_CRC(c) mCrc = mCrcTable[(mCrc ^ (c)) & 0xFF] ^ (mCrc >> UINT8_BIT)
42 // C: the Char&Len Set; P: the Position Set; T: the exTra Set
44 #define NC (UINT8_MAX + MAXMATCH + 2 - THRESHOLD)
46 #define NP (WNDBIT + 1)
48 #define NT (CODE_BIT + 3)
56 // Function Prototypes
241 IN UINT16 FreqParm
[],
242 OUT UINT8 LenParm
[ ],
243 OUT UINT16 CodeParm
[]
249 STATIC UINT8
*mSrc
, *mDst
, *mSrcUpperLimit
, *mDstUpperLimit
;
251 STATIC UINT8
*mLevel
, *mText
, *mChildCount
, *mBuf
, mCLen
[NC
], mPTLen
[NPT
], *mLen
;
252 STATIC INT16 mHeap
[NC
+ 1];
253 STATIC INT32 mRemainder
, mMatchLen
, mBitCount
, mHeapSize
, mN
;
254 STATIC UINT32 mBufSiz
= 0, mOutputPos
, mOutputMask
, mSubBitBuf
, mCrc
;
255 STATIC UINT32 mCompSize
, mOrigSize
;
257 STATIC UINT16
*mFreq
, *mSortPtr
, mLenCnt
[17], mLeft
[2 * NC
- 1], mRight
[2 * NC
- 1], mCrcTable
[UINT8_MAX
+ 1],
258 mCFreq
[2 * NC
- 1], mCCode
[NC
], mPFreq
[2 * NP
- 1], mPTCode
[NPT
], mTFreq
[2 * NT
- 1];
260 STATIC NODE mPos
, mMatchPos
, mAvail
, *mPosition
, *mParent
, *mPrev
, *mNext
= NULL
;
270 IN OUT UINT32
*DstSize
276 The internal implementation of [Efi/Tiano]Compress().
280 SrcBuffer - The buffer storing the source data
281 SrcSize - The size of source data
282 DstBuffer - The buffer to store the compressed data
283 DstSize - On input, the size of DstBuffer; On output,
284 the size of the actual compressed data.
285 Version - The version of de/compression algorithm.
286 Version 1 for UEFI 2.0 de/compression algorithm.
287 Version 2 for Tiano de/compression algorithm.
291 EFI_BUFFER_TOO_SMALL - The DstBuffer is too small. In this case,
292 DstSize contains the size needed.
293 EFI_SUCCESS - Compression is successful.
294 EFI_OUT_OF_RESOURCES - No resource to complete function.
295 EFI_INVALID_PARAMETER - Parameter supplied is wrong.
315 mSrcUpperLimit
= mSrc
+ SrcSize
;
317 mDstUpperLimit
= mDst
+*DstSize
;
324 mOrigSize
= mCompSize
= 0;
331 if (EFI_ERROR (Status
)) {
332 return EFI_OUT_OF_RESOURCES
;
335 // Null terminate the compressed data
337 if (mDst
< mDstUpperLimit
) {
341 // Fill in compressed size and original size
344 PutDword (mCompSize
+ 1);
345 PutDword (mOrigSize
);
350 if (mCompSize
+ 1 + 8 > *DstSize
) {
351 *DstSize
= mCompSize
+ 1 + 8;
352 return EFI_BUFFER_TOO_SMALL
;
354 *DstSize
= mCompSize
+ 1 + 8;
369 Put a dword to output stream
373 Data - the dword to put
379 if (mDst
< mDstUpperLimit
) {
380 *mDst
++ = (UINT8
) (((UINT8
) (Data
)) & 0xff);
383 if (mDst
< mDstUpperLimit
) {
384 *mDst
++ = (UINT8
) (((UINT8
) (Data
>> 0x08)) & 0xff);
387 if (mDst
< mDstUpperLimit
) {
388 *mDst
++ = (UINT8
) (((UINT8
) (Data
>> 0x10)) & 0xff);
391 if (mDst
< mDstUpperLimit
) {
392 *mDst
++ = (UINT8
) (((UINT8
) (Data
>> 0x18)) & 0xff);
405 Allocate memory spaces for data structures used in compression process
412 EFI_SUCCESS - Memory is allocated successfully
413 EFI_OUT_OF_RESOURCES - Allocation fails
419 mText
= malloc (WNDSIZ
* 2 + MAXMATCH
);
421 return EFI_OUT_OF_RESOURCES
;
423 for (Index
= 0; Index
< WNDSIZ
* 2 + MAXMATCH
; Index
++) {
427 mLevel
= malloc ((WNDSIZ
+ UINT8_MAX
+ 1) * sizeof (*mLevel
));
428 mChildCount
= malloc ((WNDSIZ
+ UINT8_MAX
+ 1) * sizeof (*mChildCount
));
429 mPosition
= malloc ((WNDSIZ
+ UINT8_MAX
+ 1) * sizeof (*mPosition
));
430 mParent
= malloc (WNDSIZ
* 2 * sizeof (*mParent
));
431 mPrev
= malloc (WNDSIZ
* 2 * sizeof (*mPrev
));
432 mNext
= malloc ((MAX_HASH_VAL
+ 1) * sizeof (*mNext
));
433 if (mLevel
== NULL
|| mChildCount
== NULL
|| mPosition
== NULL
||
434 mParent
== NULL
|| mPrev
== NULL
|| mNext
== NULL
) {
435 return EFI_OUT_OF_RESOURCES
;
439 mBuf
= malloc (mBufSiz
);
440 while (mBuf
== NULL
) {
441 mBufSiz
= (mBufSiz
/ 10U) * 9U;
442 if (mBufSiz
< 4 * 1024U) {
443 return EFI_OUT_OF_RESOURCES
;
446 mBuf
= malloc (mBufSiz
);
462 Called when compression is completed to free memory previously allocated.
474 if (mLevel
!= NULL
) {
478 if (mChildCount
!= NULL
) {
482 if (mPosition
!= NULL
) {
486 if (mParent
!= NULL
) {
514 Initialize String Info Log data structures
524 for (Index
= WNDSIZ
; Index
<= WNDSIZ
+ UINT8_MAX
; Index
++) {
526 mPosition
[Index
] = NIL
; /* sentinel */
529 for (Index
= WNDSIZ
; Index
< WNDSIZ
* 2; Index
++) {
530 mParent
[Index
] = NIL
;
534 for (Index
= 1; Index
< WNDSIZ
- 1; Index
++) {
535 mNext
[Index
] = (NODE
) (Index
+ 1);
538 mNext
[WNDSIZ
- 1] = NIL
;
539 for (Index
= WNDSIZ
* 2; Index
<= MAX_HASH_VAL
; Index
++) {
554 Find child node given the parent node and the edge character
558 NodeQ - the parent node
559 CharC - the edge character
563 The child node (NIL if not found)
569 NodeR
= mNext
[HASH (NodeQ
, CharC
)];
573 mParent
[NIL
] = NodeQ
;
574 while (mParent
[NodeR
] != NodeQ
) {
575 NodeR
= mNext
[NodeR
];
592 Create a new child for a given parent node.
596 Parent - the parent node
597 CharC - the edge character
598 Child - the child node
607 Node1
= (NODE
) HASH (Parent
, CharC
);
608 Node2
= mNext
[Node1
];
609 mNext
[Node1
] = Child
;
610 mNext
[Child
] = Node2
;
611 mPrev
[Node2
] = Child
;
612 mPrev
[Child
] = Node1
;
613 mParent
[Child
] = Parent
;
614 mChildCount
[Parent
]++;
630 Old - the node to split
641 mChildCount
[New
] = 0;
642 TempNode
= mPrev
[Old
];
643 mPrev
[New
] = TempNode
;
644 mNext
[TempNode
] = New
;
645 TempNode
= mNext
[Old
];
646 mNext
[New
] = TempNode
;
647 mPrev
[TempNode
] = New
;
648 mParent
[New
] = mParent
[Old
];
649 mLevel
[New
] = (UINT8
) mMatchLen
;
650 mPosition
[New
] = mPos
;
651 MakeChild (New
, mText
[mMatchPos
+ mMatchLen
], Old
);
652 MakeChild (New
, mText
[mPos
+ mMatchLen
], mPos
);
664 Insert string info for current position into the String Info Log
680 if (mMatchLen
>= 4) {
682 // We have just got a long match, the target tree
683 // can be located by MatchPos + 1. Travese the tree
684 // from bottom up to get to a proper starting point.
685 // The usage of PERC_FLAG ensures proper node deletion
686 // in DeleteNode() later.
689 NodeR
= (NODE
) ((mMatchPos
+ 1) | WNDSIZ
);
690 NodeQ
= mParent
[NodeR
];
691 while (NodeQ
== NIL
) {
692 NodeR
= mNext
[NodeR
];
693 NodeQ
= mParent
[NodeR
];
696 while (mLevel
[NodeQ
] >= mMatchLen
) {
698 NodeQ
= mParent
[NodeQ
];
702 while (mPosition
[NodeT
] < 0) {
703 mPosition
[NodeT
] = mPos
;
704 NodeT
= mParent
[NodeT
];
707 if (NodeT
< WNDSIZ
) {
708 mPosition
[NodeT
] = (NODE
) (mPos
| (UINT32
) PERC_FLAG
);
712 // Locate the target tree
714 NodeQ
= (NODE
) (mText
[mPos
] + WNDSIZ
);
715 CharC
= mText
[mPos
+ 1];
716 NodeR
= Child (NodeQ
, CharC
);
718 MakeChild (NodeQ
, CharC
, mPos
);
726 // Traverse down the tree to find a match.
727 // Update Position value along the route.
728 // Node split or creation is involved.
731 if (NodeR
>= WNDSIZ
) {
735 Index2
= mLevel
[NodeR
];
736 mMatchPos
= (NODE
) (mPosition
[NodeR
] & (UINT32
)~PERC_FLAG
);
739 if (mMatchPos
>= mPos
) {
743 t1
= &mText
[mPos
+ mMatchLen
];
744 t2
= &mText
[mMatchPos
+ mMatchLen
];
745 while (mMatchLen
< Index2
) {
756 if (mMatchLen
>= MAXMATCH
) {
760 mPosition
[NodeR
] = mPos
;
762 NodeR
= Child (NodeQ
, *t1
);
764 MakeChild (NodeQ
, *t1
, mPos
);
771 NodeT
= mPrev
[NodeR
];
774 NodeT
= mNext
[NodeR
];
777 mParent
[mPos
] = NodeQ
;
778 mParent
[NodeR
] = NIL
;
781 // Special usage of 'next'
796 Delete outdated string info. (The Usage of PERC_FLAG
797 ensures a clean deletion)
811 if (mParent
[mPos
] == NIL
) {
817 mNext
[NodeR
] = NodeS
;
818 mPrev
[NodeS
] = NodeR
;
819 NodeR
= mParent
[mPos
];
821 if (NodeR
>= WNDSIZ
) {
825 mChildCount
[NodeR
]--;
826 if (mChildCount
[NodeR
] > 1) {
830 NodeT
= (NODE
) (mPosition
[NodeR
] & (UINT32
)~PERC_FLAG
);
836 NodeQ
= mParent
[NodeR
];
837 NodeU
= mPosition
[NodeQ
];
838 while (NodeU
& (UINT32
) PERC_FLAG
) {
839 NodeU
&= (UINT32
)~PERC_FLAG
;
848 mPosition
[NodeQ
] = (NODE
) (NodeS
| WNDSIZ
);
849 NodeQ
= mParent
[NodeQ
];
850 NodeU
= mPosition
[NodeQ
];
853 if (NodeQ
< WNDSIZ
) {
862 mPosition
[NodeQ
] = (NODE
) (NodeS
| WNDSIZ
| (UINT32
) PERC_FLAG
);
865 NodeS
= Child (NodeR
, mText
[NodeT
+ mLevel
[NodeR
]]);
866 NodeT
= mPrev
[NodeS
];
867 NodeU
= mNext
[NodeS
];
868 mNext
[NodeT
] = NodeU
;
869 mPrev
[NodeU
] = NodeT
;
870 NodeT
= mPrev
[NodeR
];
871 mNext
[NodeT
] = NodeS
;
872 mPrev
[NodeS
] = NodeT
;
873 NodeT
= mNext
[NodeR
];
874 mPrev
[NodeT
] = NodeS
;
875 mNext
[NodeS
] = NodeT
;
876 mParent
[NodeS
] = mParent
[NodeR
];
877 mParent
[NodeR
] = NIL
;
878 mNext
[NodeR
] = mAvail
;
891 Advance the current position (read in new data if needed).
892 Delete outdated string info. Find a match string for current position.
904 if (mPos
== WNDSIZ
* 2) {
905 memmove (&mText
[0], &mText
[WNDSIZ
], WNDSIZ
+ MAXMATCH
);
906 Number
= FreadCrc (&mText
[WNDSIZ
+ MAXMATCH
], WNDSIZ
);
907 mRemainder
+= Number
;
924 The main controlling routine for compression process.
930 EFI_SUCCESS - The compression is successful
931 EFI_OUT_0F_RESOURCES - Not enough memory for compression process
939 Status
= AllocateMemory ();
940 if (EFI_ERROR (Status
)) {
949 mRemainder
= FreadCrc (&mText
[WNDSIZ
], WNDSIZ
+ MAXMATCH
);
954 if (mMatchLen
> mRemainder
) {
955 mMatchLen
= mRemainder
;
958 while (mRemainder
> 0) {
959 LastMatchLen
= mMatchLen
;
960 LastMatchPos
= mMatchPos
;
962 if (mMatchLen
> mRemainder
) {
963 mMatchLen
= mRemainder
;
966 if (mMatchLen
> LastMatchLen
|| LastMatchLen
< THRESHOLD
) {
968 // Not enough benefits are gained by outputting a pointer,
969 // so just output the original character
971 Output (mText
[mPos
- 1], 0);
975 if (LastMatchLen
== THRESHOLD
) {
976 if (((mPos
- LastMatchPos
- 2) & (WNDSIZ
- 1)) > (1U << 11)) {
977 Output (mText
[mPos
- 1], 0);
982 // Outputting a pointer is beneficial enough, do it.
985 LastMatchLen
+ (UINT8_MAX
+ 1 - THRESHOLD
),
986 (mPos
- LastMatchPos
- 2) & (WNDSIZ
- 1)
989 while (LastMatchLen
> 0) {
994 if (mMatchLen
> mRemainder
) {
995 mMatchLen
= mRemainder
;
1012 Routine Description:
1014 Count the frequencies for the Extra Set
1027 for (Index
= 0; Index
< NT
; Index
++) {
1032 while (Number
> 0 && mCLen
[Number
- 1] == 0) {
1037 while (Index
< Number
) {
1038 Index3
= mCLen
[Index
++];
1041 while (Index
< Number
&& mCLen
[Index
] == 0) {
1047 mTFreq
[0] = (UINT16
) (mTFreq
[0] + Count
);
1048 } else if (Count
<= 18) {
1050 } else if (Count
== 19) {
1057 mTFreq
[Index3
+ 2]++;
1071 Routine Description:
1073 Outputs the code length array for the Extra Set or the Position Set.
1077 Number - the number of symbols
1078 nbit - the number of bits needed to represent 'n'
1079 Special - the special symbol that needs to be take care of
1088 while (Number
> 0 && mPTLen
[Number
- 1] == 0) {
1092 PutBits (nbit
, Number
);
1094 while (Index
< Number
) {
1095 Index3
= mPTLen
[Index
++];
1097 PutBits (3, Index3
);
1099 PutBits (Index3
- 3, (1U << (Index3
- 3)) - 2);
1102 if (Index
== Special
) {
1103 while (Index
< 6 && mPTLen
[Index
] == 0) {
1107 PutBits (2, (Index
- 3) & 3);
1119 Routine Description:
1121 Outputs the code length array for Char&Length Set
1135 while (Number
> 0 && mCLen
[Number
- 1] == 0) {
1139 PutBits (CBIT
, Number
);
1141 while (Index
< Number
) {
1142 Index3
= mCLen
[Index
++];
1145 while (Index
< Number
&& mCLen
[Index
] == 0) {
1151 for (Index3
= 0; Index3
< Count
; Index3
++) {
1152 PutBits (mPTLen
[0], mPTCode
[0]);
1154 } else if (Count
<= 18) {
1155 PutBits (mPTLen
[1], mPTCode
[1]);
1156 PutBits (4, Count
- 3);
1157 } else if (Count
== 19) {
1158 PutBits (mPTLen
[0], mPTCode
[0]);
1159 PutBits (mPTLen
[1], mPTCode
[1]);
1162 PutBits (mPTLen
[2], mPTCode
[2]);
1163 PutBits (CBIT
, Count
- 20);
1166 PutBits (mPTLen
[Index3
+ 2], mPTCode
[Index3
+ 2]);
1177 PutBits (mCLen
[Value
], mCCode
[Value
]);
1196 PutBits (mPTLen
[Index
], mPTCode
[Index
]);
1198 PutBits (Index
- 1, Value
& (0xFFFFFFFFU
>> (32 - Index
+ 1)));
1209 Routine Description:
1211 Huffman code the block and output it.
1230 Root
= MakeTree (NC
, mCFreq
, mCLen
, mCCode
);
1231 Size
= mCFreq
[Root
];
1235 Root
= MakeTree (NT
, mTFreq
, mPTLen
, mPTCode
);
1237 WritePTLen (NT
, TBIT
, 3);
1240 PutBits (TBIT
, Root
);
1248 PutBits (CBIT
, Root
);
1251 Root
= MakeTree (NP
, mPFreq
, mPTLen
, mPTCode
);
1253 WritePTLen (NP
, PBIT
, -1);
1256 PutBits (PBIT
, Root
);
1260 for (Index
= 0; Index
< Size
; Index
++) {
1261 if (Index
% UINT8_BIT
== 0) {
1262 Flags
= mBuf
[Pos
++];
1267 if (Flags
& (1U << (UINT8_BIT
- 1))) {
1268 EncodeC (mBuf
[Pos
++] + (1U << UINT8_BIT
));
1269 Index3
= mBuf
[Pos
++];
1270 for (Index2
= 0; Index2
< 3; Index2
++) {
1271 Index3
<<= UINT8_BIT
;
1272 Index3
+= mBuf
[Pos
++];
1277 EncodeC (mBuf
[Pos
++]);
1281 for (Index
= 0; Index
< NC
; Index
++) {
1285 for (Index
= 0; Index
< NP
; Index
++) {
1298 Routine Description:
1300 Outputs an Original Character or a Pointer
1304 CharC - The original character or the 'String Length' element of a Pointer
1305 Pos - The 'Position' field of a Pointer
1313 if ((mOutputMask
>>= 1) == 0) {
1314 mOutputMask
= 1U << (UINT8_BIT
- 1);
1316 // Check the buffer overflow per outputing UINT8_BIT symbols
1317 // which is an Original Character or a Pointer. The biggest
1318 // symbol is a Pointer which occupies 5 bytes.
1320 if (mOutputPos
>= mBufSiz
- 5 * UINT8_BIT
) {
1325 CPos
= mOutputPos
++;
1329 mBuf
[mOutputPos
++] = (UINT8
) CharC
;
1331 if (CharC
>= (1U << UINT8_BIT
)) {
1332 mBuf
[CPos
] |= mOutputMask
;
1333 mBuf
[mOutputPos
++] = (UINT8
) (Pos
>> 24);
1334 mBuf
[mOutputPos
++] = (UINT8
) (Pos
>> 16);
1335 mBuf
[mOutputPos
++] = (UINT8
) (Pos
>> (UINT8_BIT
));
1336 mBuf
[mOutputPos
++] = (UINT8
) Pos
;
1355 for (Index
= 0; Index
< NC
; Index
++) {
1359 for (Index
= 0; Index
< NP
; Index
++) {
1363 mOutputPos
= mOutputMask
= 0;
1377 // Flush remaining bits
1379 PutBits (UINT8_BIT
- 1, 0);
1394 for (Index
= 0; Index
<= UINT8_MAX
; Index
++) {
1396 for (Index2
= 0; Index2
< UINT8_BIT
; Index2
++) {
1398 Temp
= (Temp
>> 1) ^ CRCPOLY
;
1404 mCrcTable
[Index
] = (UINT16
) Temp
;
1416 Routine Description:
1418 Outputs rightmost n bits of x
1422 Number - the rightmost n bits of the data is used
1431 while (Number
>= mBitCount
) {
1433 // Number -= mBitCount should never equal to 32
1435 Temp
= (UINT8
) (mSubBitBuf
| (Value
>> (Number
-= mBitCount
)));
1436 if (mDst
< mDstUpperLimit
) {
1442 mBitCount
= UINT8_BIT
;
1445 mSubBitBuf
|= Value
<< (mBitCount
-= Number
);
1456 Routine Description:
1462 Pointer - the buffer to hold the data
1463 Number - number of bytes to read
1467 number of bytes actually read
1473 for (Index
= 0; mSrc
< mSrcUpperLimit
&& Index
< Number
; Index
++) {
1474 *Pointer
++ = *mSrc
++;
1480 mOrigSize
+= Number
;
1482 while (Index
>= 0) {
1483 UPDATE_CRC (*Pointer
++);
1496 mBitCount
= UINT8_BIT
;
1507 Routine Description:
1509 Count the number of each code length for a Huffman tree.
1513 Index - the top node
1519 STATIC INT32 Depth
= 0;
1522 mLenCnt
[(Depth
< 16) ? Depth
: 16]++;
1525 CountLen (mLeft
[Index
]);
1526 CountLen (mRight
[Index
]);
1538 Routine Description:
1540 Create code length array for a Huffman tree
1544 Root - the root of the tree
1556 for (Index
= 0; Index
<= 16; Index
++) {
1563 // Adjust the length count array so that
1564 // no code will be generated longer than its designated length
1567 for (Index
= 16; Index
> 0; Index
--) {
1568 Cum
+= mLenCnt
[Index
] << (16 - Index
);
1571 while (Cum
!= (1U << 16)) {
1573 for (Index
= 15; Index
> 0; Index
--) {
1574 if (mLenCnt
[Index
] != 0) {
1576 mLenCnt
[Index
+ 1] += 2;
1584 for (Index
= 16; Index
> 0; Index
--) {
1585 Index3
= mLenCnt
[Index
];
1587 while (Index3
>= 0) {
1588 mLen
[*mSortPtr
++] = (UINT8
) Index
;
1604 // priority queue: send Index-th entry down heap
1606 Index3
= mHeap
[Index
];
1608 while (Index2
<= mHeapSize
) {
1609 if (Index2
< mHeapSize
&& mFreq
[mHeap
[Index2
]] > mFreq
[mHeap
[Index2
+ 1]]) {
1613 if (mFreq
[Index3
] <= mFreq
[mHeap
[Index2
]]) {
1617 mHeap
[Index
] = mHeap
[Index2
];
1622 mHeap
[Index
] = (INT16
) Index3
;
1634 Routine Description:
1636 Assign code to each symbol based on the code length array
1640 Number - number of symbols
1641 Len - the code length array
1642 Code - stores codes for each symbol
1652 for (Index
= 1; Index
<= 16; Index
++) {
1653 Start
[Index
+ 1] = (UINT16
) ((Start
[Index
] + mLenCnt
[Index
]) << 1);
1656 for (Index
= 0; Index
< Number
; Index
++) {
1657 Code
[Index
] = Start
[Len
[Index
]]++;
1665 IN UINT16 FreqParm
[],
1666 OUT UINT8 LenParm
[ ],
1667 OUT UINT16 CodeParm
[]
1671 Routine Description:
1673 Generates Huffman codes given a frequency distribution of symbols
1677 NParm - number of symbols
1678 FreqParm - frequency of each symbol
1679 LenParm - code length for each symbol
1680 CodeParm - code for each symbol
1684 Root of the Huffman tree.
1694 // make tree, calculate len[], return root
1702 for (Index
= 0; Index
< mN
; Index
++) {
1706 mHeap
[mHeapSize
] = (INT16
) Index
;
1710 if (mHeapSize
< 2) {
1711 CodeParm
[mHeap
[1]] = 0;
1715 for (Index
= mHeapSize
/ 2; Index
>= 1; Index
--) {
1717 // make priority queue
1722 mSortPtr
= CodeParm
;
1726 *mSortPtr
++ = (UINT16
) Index
;
1729 mHeap
[1] = mHeap
[mHeapSize
--];
1733 *mSortPtr
++ = (UINT16
) Index2
;
1737 mFreq
[Index3
] = (UINT16
) (mFreq
[Index
] + mFreq
[Index2
]);
1738 mHeap
[1] = (INT16
) Index3
;
1740 mLeft
[Index3
] = (UINT16
) Index
;
1741 mRight
[Index3
] = (UINT16
) Index2
;
1742 } while (mHeapSize
> 1);
1744 mSortPtr
= CodeParm
;
1746 MakeCode (NParm
, LenParm
, CodeParm
);