]>
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 - 2014, 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
);
420 for (Index
= 0; Index
< WNDSIZ
* 2 + MAXMATCH
; Index
++) {
424 mLevel
= malloc ((WNDSIZ
+ UINT8_MAX
+ 1) * sizeof (*mLevel
));
425 mChildCount
= malloc ((WNDSIZ
+ UINT8_MAX
+ 1) * sizeof (*mChildCount
));
426 mPosition
= malloc ((WNDSIZ
+ UINT8_MAX
+ 1) * sizeof (*mPosition
));
427 mParent
= malloc (WNDSIZ
* 2 * sizeof (*mParent
));
428 mPrev
= malloc (WNDSIZ
* 2 * sizeof (*mPrev
));
429 mNext
= malloc ((MAX_HASH_VAL
+ 1) * sizeof (*mNext
));
432 mBuf
= malloc (mBufSiz
);
433 while (mBuf
== NULL
) {
434 mBufSiz
= (mBufSiz
/ 10U) * 9U;
435 if (mBufSiz
< 4 * 1024U) {
436 return EFI_OUT_OF_RESOURCES
;
439 mBuf
= malloc (mBufSiz
);
455 Called when compression is completed to free memory previously allocated.
467 if (mLevel
!= NULL
) {
471 if (mChildCount
!= NULL
) {
475 if (mPosition
!= NULL
) {
479 if (mParent
!= NULL
) {
507 Initialize String Info Log data structures
517 for (Index
= WNDSIZ
; Index
<= WNDSIZ
+ UINT8_MAX
; Index
++) {
519 mPosition
[Index
] = NIL
; /* sentinel */
522 for (Index
= WNDSIZ
; Index
< WNDSIZ
* 2; Index
++) {
523 mParent
[Index
] = NIL
;
527 for (Index
= 1; Index
< WNDSIZ
- 1; Index
++) {
528 mNext
[Index
] = (NODE
) (Index
+ 1);
531 mNext
[WNDSIZ
- 1] = NIL
;
532 for (Index
= WNDSIZ
* 2; Index
<= MAX_HASH_VAL
; Index
++) {
547 Find child node given the parent node and the edge character
551 NodeQ - the parent node
552 CharC - the edge character
556 The child node (NIL if not found)
562 NodeR
= mNext
[HASH (NodeQ
, CharC
)];
566 mParent
[NIL
] = NodeQ
;
567 while (mParent
[NodeR
] != NodeQ
) {
568 NodeR
= mNext
[NodeR
];
585 Create a new child for a given parent node.
589 Parent - the parent node
590 CharC - the edge character
591 Child - the child node
600 Node1
= (NODE
) HASH (Parent
, CharC
);
601 Node2
= mNext
[Node1
];
602 mNext
[Node1
] = Child
;
603 mNext
[Child
] = Node2
;
604 mPrev
[Node2
] = Child
;
605 mPrev
[Child
] = Node1
;
606 mParent
[Child
] = Parent
;
607 mChildCount
[Parent
]++;
623 Old - the node to split
634 mChildCount
[New
] = 0;
635 TempNode
= mPrev
[Old
];
636 mPrev
[New
] = TempNode
;
637 mNext
[TempNode
] = New
;
638 TempNode
= mNext
[Old
];
639 mNext
[New
] = TempNode
;
640 mPrev
[TempNode
] = New
;
641 mParent
[New
] = mParent
[Old
];
642 mLevel
[New
] = (UINT8
) mMatchLen
;
643 mPosition
[New
] = mPos
;
644 MakeChild (New
, mText
[mMatchPos
+ mMatchLen
], Old
);
645 MakeChild (New
, mText
[mPos
+ mMatchLen
], mPos
);
657 Insert string info for current position into the String Info Log
673 if (mMatchLen
>= 4) {
675 // We have just got a long match, the target tree
676 // can be located by MatchPos + 1. Travese the tree
677 // from bottom up to get to a proper starting point.
678 // The usage of PERC_FLAG ensures proper node deletion
679 // in DeleteNode() later.
682 NodeR
= (NODE
) ((mMatchPos
+ 1) | WNDSIZ
);
683 NodeQ
= mParent
[NodeR
];
684 while (NodeQ
== NIL
) {
685 NodeR
= mNext
[NodeR
];
686 NodeQ
= mParent
[NodeR
];
689 while (mLevel
[NodeQ
] >= mMatchLen
) {
691 NodeQ
= mParent
[NodeQ
];
695 while (mPosition
[NodeT
] < 0) {
696 mPosition
[NodeT
] = mPos
;
697 NodeT
= mParent
[NodeT
];
700 if (NodeT
< WNDSIZ
) {
701 mPosition
[NodeT
] = (NODE
) (mPos
| (UINT32
) PERC_FLAG
);
705 // Locate the target tree
707 NodeQ
= (NODE
) (mText
[mPos
] + WNDSIZ
);
708 CharC
= mText
[mPos
+ 1];
709 NodeR
= Child (NodeQ
, CharC
);
711 MakeChild (NodeQ
, CharC
, mPos
);
719 // Traverse down the tree to find a match.
720 // Update Position value along the route.
721 // Node split or creation is involved.
724 if (NodeR
>= WNDSIZ
) {
728 Index2
= mLevel
[NodeR
];
729 mMatchPos
= (NODE
) (mPosition
[NodeR
] & (UINT32
)~PERC_FLAG
);
732 if (mMatchPos
>= mPos
) {
736 t1
= &mText
[mPos
+ mMatchLen
];
737 t2
= &mText
[mMatchPos
+ mMatchLen
];
738 while (mMatchLen
< Index2
) {
749 if (mMatchLen
>= MAXMATCH
) {
753 mPosition
[NodeR
] = mPos
;
755 NodeR
= Child (NodeQ
, *t1
);
757 MakeChild (NodeQ
, *t1
, mPos
);
764 NodeT
= mPrev
[NodeR
];
767 NodeT
= mNext
[NodeR
];
770 mParent
[mPos
] = NodeQ
;
771 mParent
[NodeR
] = NIL
;
774 // Special usage of 'next'
789 Delete outdated string info. (The Usage of PERC_FLAG
790 ensures a clean deletion)
804 if (mParent
[mPos
] == NIL
) {
810 mNext
[NodeR
] = NodeS
;
811 mPrev
[NodeS
] = NodeR
;
812 NodeR
= mParent
[mPos
];
814 if (NodeR
>= WNDSIZ
) {
818 mChildCount
[NodeR
]--;
819 if (mChildCount
[NodeR
] > 1) {
823 NodeT
= (NODE
) (mPosition
[NodeR
] & (UINT32
)~PERC_FLAG
);
829 NodeQ
= mParent
[NodeR
];
830 NodeU
= mPosition
[NodeQ
];
831 while (NodeU
& (UINT32
) PERC_FLAG
) {
832 NodeU
&= (UINT32
)~PERC_FLAG
;
841 mPosition
[NodeQ
] = (NODE
) (NodeS
| WNDSIZ
);
842 NodeQ
= mParent
[NodeQ
];
843 NodeU
= mPosition
[NodeQ
];
846 if (NodeQ
< WNDSIZ
) {
855 mPosition
[NodeQ
] = (NODE
) (NodeS
| WNDSIZ
| (UINT32
) PERC_FLAG
);
858 NodeS
= Child (NodeR
, mText
[NodeT
+ mLevel
[NodeR
]]);
859 NodeT
= mPrev
[NodeS
];
860 NodeU
= mNext
[NodeS
];
861 mNext
[NodeT
] = NodeU
;
862 mPrev
[NodeU
] = NodeT
;
863 NodeT
= mPrev
[NodeR
];
864 mNext
[NodeT
] = NodeS
;
865 mPrev
[NodeS
] = NodeT
;
866 NodeT
= mNext
[NodeR
];
867 mPrev
[NodeT
] = NodeS
;
868 mNext
[NodeS
] = NodeT
;
869 mParent
[NodeS
] = mParent
[NodeR
];
870 mParent
[NodeR
] = NIL
;
871 mNext
[NodeR
] = mAvail
;
884 Advance the current position (read in new data if needed).
885 Delete outdated string info. Find a match string for current position.
897 if (mPos
== WNDSIZ
* 2) {
898 memmove (&mText
[0], &mText
[WNDSIZ
], WNDSIZ
+ MAXMATCH
);
899 Number
= FreadCrc (&mText
[WNDSIZ
+ MAXMATCH
], WNDSIZ
);
900 mRemainder
+= Number
;
917 The main controlling routine for compression process.
923 EFI_SUCCESS - The compression is successful
924 EFI_OUT_0F_RESOURCES - Not enough memory for compression process
932 Status
= AllocateMemory ();
933 if (EFI_ERROR (Status
)) {
942 mRemainder
= FreadCrc (&mText
[WNDSIZ
], WNDSIZ
+ MAXMATCH
);
947 if (mMatchLen
> mRemainder
) {
948 mMatchLen
= mRemainder
;
951 while (mRemainder
> 0) {
952 LastMatchLen
= mMatchLen
;
953 LastMatchPos
= mMatchPos
;
955 if (mMatchLen
> mRemainder
) {
956 mMatchLen
= mRemainder
;
959 if (mMatchLen
> LastMatchLen
|| LastMatchLen
< THRESHOLD
) {
961 // Not enough benefits are gained by outputting a pointer,
962 // so just output the original character
964 Output (mText
[mPos
- 1], 0);
968 if (LastMatchLen
== THRESHOLD
) {
969 if (((mPos
- LastMatchPos
- 2) & (WNDSIZ
- 1)) > (1U << 11)) {
970 Output (mText
[mPos
- 1], 0);
975 // Outputting a pointer is beneficial enough, do it.
978 LastMatchLen
+ (UINT8_MAX
+ 1 - THRESHOLD
),
979 (mPos
- LastMatchPos
- 2) & (WNDSIZ
- 1)
982 while (LastMatchLen
> 0) {
987 if (mMatchLen
> mRemainder
) {
988 mMatchLen
= mRemainder
;
1005 Routine Description:
1007 Count the frequencies for the Extra Set
1020 for (Index
= 0; Index
< NT
; Index
++) {
1025 while (Number
> 0 && mCLen
[Number
- 1] == 0) {
1030 while (Index
< Number
) {
1031 Index3
= mCLen
[Index
++];
1034 while (Index
< Number
&& mCLen
[Index
] == 0) {
1040 mTFreq
[0] = (UINT16
) (mTFreq
[0] + Count
);
1041 } else if (Count
<= 18) {
1043 } else if (Count
== 19) {
1050 mTFreq
[Index3
+ 2]++;
1064 Routine Description:
1066 Outputs the code length array for the Extra Set or the Position Set.
1070 Number - the number of symbols
1071 nbit - the number of bits needed to represent 'n'
1072 Special - the special symbol that needs to be take care of
1081 while (Number
> 0 && mPTLen
[Number
- 1] == 0) {
1085 PutBits (nbit
, Number
);
1087 while (Index
< Number
) {
1088 Index3
= mPTLen
[Index
++];
1090 PutBits (3, Index3
);
1092 PutBits (Index3
- 3, (1U << (Index3
- 3)) - 2);
1095 if (Index
== Special
) {
1096 while (Index
< 6 && mPTLen
[Index
] == 0) {
1100 PutBits (2, (Index
- 3) & 3);
1112 Routine Description:
1114 Outputs the code length array for Char&Length Set
1128 while (Number
> 0 && mCLen
[Number
- 1] == 0) {
1132 PutBits (CBIT
, Number
);
1134 while (Index
< Number
) {
1135 Index3
= mCLen
[Index
++];
1138 while (Index
< Number
&& mCLen
[Index
] == 0) {
1144 for (Index3
= 0; Index3
< Count
; Index3
++) {
1145 PutBits (mPTLen
[0], mPTCode
[0]);
1147 } else if (Count
<= 18) {
1148 PutBits (mPTLen
[1], mPTCode
[1]);
1149 PutBits (4, Count
- 3);
1150 } else if (Count
== 19) {
1151 PutBits (mPTLen
[0], mPTCode
[0]);
1152 PutBits (mPTLen
[1], mPTCode
[1]);
1155 PutBits (mPTLen
[2], mPTCode
[2]);
1156 PutBits (CBIT
, Count
- 20);
1159 PutBits (mPTLen
[Index3
+ 2], mPTCode
[Index3
+ 2]);
1170 PutBits (mCLen
[Value
], mCCode
[Value
]);
1189 PutBits (mPTLen
[Index
], mPTCode
[Index
]);
1191 PutBits (Index
- 1, Value
& (0xFFFFFFFFU
>> (32 - Index
+ 1)));
1202 Routine Description:
1204 Huffman code the block and output it.
1223 Root
= MakeTree (NC
, mCFreq
, mCLen
, mCCode
);
1224 Size
= mCFreq
[Root
];
1228 Root
= MakeTree (NT
, mTFreq
, mPTLen
, mPTCode
);
1230 WritePTLen (NT
, TBIT
, 3);
1233 PutBits (TBIT
, Root
);
1241 PutBits (CBIT
, Root
);
1244 Root
= MakeTree (NP
, mPFreq
, mPTLen
, mPTCode
);
1246 WritePTLen (NP
, PBIT
, -1);
1249 PutBits (PBIT
, Root
);
1253 for (Index
= 0; Index
< Size
; Index
++) {
1254 if (Index
% UINT8_BIT
== 0) {
1255 Flags
= mBuf
[Pos
++];
1260 if (Flags
& (1U << (UINT8_BIT
- 1))) {
1261 EncodeC (mBuf
[Pos
++] + (1U << UINT8_BIT
));
1262 Index3
= mBuf
[Pos
++];
1263 for (Index2
= 0; Index2
< 3; Index2
++) {
1264 Index3
<<= UINT8_BIT
;
1265 Index3
+= mBuf
[Pos
++];
1270 EncodeC (mBuf
[Pos
++]);
1274 for (Index
= 0; Index
< NC
; Index
++) {
1278 for (Index
= 0; Index
< NP
; Index
++) {
1291 Routine Description:
1293 Outputs an Original Character or a Pointer
1297 CharC - The original character or the 'String Length' element of a Pointer
1298 Pos - The 'Position' field of a Pointer
1306 if ((mOutputMask
>>= 1) == 0) {
1307 mOutputMask
= 1U << (UINT8_BIT
- 1);
1309 // Check the buffer overflow per outputing UINT8_BIT symbols
1310 // which is an Original Character or a Pointer. The biggest
1311 // symbol is a Pointer which occupies 5 bytes.
1313 if (mOutputPos
>= mBufSiz
- 5 * UINT8_BIT
) {
1318 CPos
= mOutputPos
++;
1322 mBuf
[mOutputPos
++] = (UINT8
) CharC
;
1324 if (CharC
>= (1U << UINT8_BIT
)) {
1325 mBuf
[CPos
] |= mOutputMask
;
1326 mBuf
[mOutputPos
++] = (UINT8
) (Pos
>> 24);
1327 mBuf
[mOutputPos
++] = (UINT8
) (Pos
>> 16);
1328 mBuf
[mOutputPos
++] = (UINT8
) (Pos
>> (UINT8_BIT
));
1329 mBuf
[mOutputPos
++] = (UINT8
) Pos
;
1348 for (Index
= 0; Index
< NC
; Index
++) {
1352 for (Index
= 0; Index
< NP
; Index
++) {
1356 mOutputPos
= mOutputMask
= 0;
1370 // Flush remaining bits
1372 PutBits (UINT8_BIT
- 1, 0);
1387 for (Index
= 0; Index
<= UINT8_MAX
; Index
++) {
1389 for (Index2
= 0; Index2
< UINT8_BIT
; Index2
++) {
1391 Temp
= (Temp
>> 1) ^ CRCPOLY
;
1397 mCrcTable
[Index
] = (UINT16
) Temp
;
1409 Routine Description:
1411 Outputs rightmost n bits of x
1415 Number - the rightmost n bits of the data is used
1424 while (Number
>= mBitCount
) {
1426 // Number -= mBitCount should never equal to 32
1428 Temp
= (UINT8
) (mSubBitBuf
| (Value
>> (Number
-= mBitCount
)));
1429 if (mDst
< mDstUpperLimit
) {
1435 mBitCount
= UINT8_BIT
;
1438 mSubBitBuf
|= Value
<< (mBitCount
-= Number
);
1449 Routine Description:
1455 Pointer - the buffer to hold the data
1456 Number - number of bytes to read
1460 number of bytes actually read
1466 for (Index
= 0; mSrc
< mSrcUpperLimit
&& Index
< Number
; Index
++) {
1467 *Pointer
++ = *mSrc
++;
1473 mOrigSize
+= Number
;
1475 while (Index
>= 0) {
1476 UPDATE_CRC (*Pointer
++);
1489 mBitCount
= UINT8_BIT
;
1500 Routine Description:
1502 Count the number of each code length for a Huffman tree.
1506 Index - the top node
1512 STATIC INT32 Depth
= 0;
1515 mLenCnt
[(Depth
< 16) ? Depth
: 16]++;
1518 CountLen (mLeft
[Index
]);
1519 CountLen (mRight
[Index
]);
1531 Routine Description:
1533 Create code length array for a Huffman tree
1537 Root - the root of the tree
1549 for (Index
= 0; Index
<= 16; Index
++) {
1556 // Adjust the length count array so that
1557 // no code will be generated longer than its designated length
1560 for (Index
= 16; Index
> 0; Index
--) {
1561 Cum
+= mLenCnt
[Index
] << (16 - Index
);
1564 while (Cum
!= (1U << 16)) {
1566 for (Index
= 15; Index
> 0; Index
--) {
1567 if (mLenCnt
[Index
] != 0) {
1569 mLenCnt
[Index
+ 1] += 2;
1577 for (Index
= 16; Index
> 0; Index
--) {
1578 Index3
= mLenCnt
[Index
];
1580 while (Index3
>= 0) {
1581 mLen
[*mSortPtr
++] = (UINT8
) Index
;
1597 // priority queue: send Index-th entry down heap
1599 Index3
= mHeap
[Index
];
1601 while (Index2
<= mHeapSize
) {
1602 if (Index2
< mHeapSize
&& mFreq
[mHeap
[Index2
]] > mFreq
[mHeap
[Index2
+ 1]]) {
1606 if (mFreq
[Index3
] <= mFreq
[mHeap
[Index2
]]) {
1610 mHeap
[Index
] = mHeap
[Index2
];
1615 mHeap
[Index
] = (INT16
) Index3
;
1627 Routine Description:
1629 Assign code to each symbol based on the code length array
1633 Number - number of symbols
1634 Len - the code length array
1635 Code - stores codes for each symbol
1645 for (Index
= 1; Index
<= 16; Index
++) {
1646 Start
[Index
+ 1] = (UINT16
) ((Start
[Index
] + mLenCnt
[Index
]) << 1);
1649 for (Index
= 0; Index
< Number
; Index
++) {
1650 Code
[Index
] = Start
[Len
[Index
]]++;
1658 IN UINT16 FreqParm
[],
1659 OUT UINT8 LenParm
[ ],
1660 OUT UINT16 CodeParm
[]
1664 Routine Description:
1666 Generates Huffman codes given a frequency distribution of symbols
1670 NParm - number of symbols
1671 FreqParm - frequency of each symbol
1672 LenParm - code length for each symbol
1673 CodeParm - code for each symbol
1677 Root of the Huffman tree.
1687 // make tree, calculate len[], return root
1695 for (Index
= 0; Index
< mN
; Index
++) {
1699 mHeap
[mHeapSize
] = (INT16
) Index
;
1703 if (mHeapSize
< 2) {
1704 CodeParm
[mHeap
[1]] = 0;
1708 for (Index
= mHeapSize
/ 2; Index
>= 1; Index
--) {
1710 // make priority queue
1715 mSortPtr
= CodeParm
;
1719 *mSortPtr
++ = (UINT16
) Index
;
1722 mHeap
[1] = mHeap
[mHeapSize
--];
1726 *mSortPtr
++ = (UINT16
) Index2
;
1730 mFreq
[Index3
] = (UINT16
) (mFreq
[Index
] + mFreq
[Index2
]);
1731 mHeap
[1] = (INT16
) Index3
;
1733 mLeft
[Index3
] = (UINT16
) Index
;
1734 mRight
[Index3
] = (UINT16
) Index2
;
1735 } while (mHeapSize
> 1);
1737 mSortPtr
= CodeParm
;
1739 MakeCode (NParm
, LenParm
, CodeParm
);