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