1 /** @file
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.
6
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
12
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.
15
16 **/
17
18 #include "Compress.h"
19
20
21 //
22 // Macro Definitions
23 //
24
25 #undef UINT8_MAX
26 typedef INT16 NODE;
27 #define UINT8_MAX 0xff
28 #define UINT8_BIT 8
29 #define THRESHOLD 3
30 #define INIT_CRC 0
31 #define WNDBIT 13
32 #define WNDSIZ (1U << WNDBIT)
33 #define MAXMATCH 256
34 #define PERC_FLAG 0x8000U
35 #define CODE_BIT 16
36 #define NIL 0
37 #define MAX_HASH_VAL (3 * WNDSIZ + (WNDSIZ / 512 + 1) * UINT8_MAX)
38 #define HASH(p, c) ((p) + ((c) << (WNDBIT - 9)) + WNDSIZ * 2)
39 #define CRCPOLY 0xA001
40 #define UPDATE_CRC(c) mCrc = mCrcTable[(mCrc ^ (c)) & 0xFF] ^ (mCrc >> UINT8_BIT)
41
42 //
43 // C: the Char&Len Set; P: the Position Set; T: the exTra Set
44 //
45
46 #define NC (UINT8_MAX + MAXMATCH + 2 - THRESHOLD)
47 #define CBIT 9
48 #define NP (WNDBIT + 1)
49 #define PBIT 4
50 #define NT (CODE_BIT + 3)
51 #define TBIT 5
52 #if NT > NP
53 #define NPT NT
54 #else
55 #define NPT NP
56 #endif
57
58 //
59 // Function Prototypes
60 //
61
62 STATIC
63 VOID
64 PutDword(
65 IN UINT32 Data
66 );
67
68 STATIC
69 EFI_STATUS
70 AllocateMemory (
71 );
72
73 STATIC
74 VOID
75 FreeMemory (
76 );
77
78 STATIC
79 VOID
80 InitSlide (
81 );
82
83 STATIC
84 NODE
85 Child (
86 IN NODE q,
87 IN UINT8 c
88 );
89
90 STATIC
91 VOID
92 MakeChild (
93 IN NODE q,
94 IN UINT8 c,
95 IN NODE r
96 );
97
98 STATIC
99 VOID
100 Split (
101 IN NODE Old
102 );
103
104 STATIC
105 VOID
106 InsertNode (
107 );
108
109 STATIC
110 VOID
111 DeleteNode (
112 );
113
114 STATIC
115 VOID
116 GetNextMatch (
117 );
118
119 STATIC
120 EFI_STATUS
121 Encode (
122 );
123
124 STATIC
125 VOID
126 CountTFreq (
127 );
128
129 STATIC
130 VOID
131 WritePTLen (
132 IN INT32 n,
133 IN INT32 nbit,
134 IN INT32 Special
135 );
136
137 STATIC
138 VOID
139 WriteCLen (
140 );
141
142 STATIC
143 VOID
144 EncodeC (
145 IN INT32 c
146 );
147
148 STATIC
149 VOID
150 EncodeP (
151 IN UINT32 p
152 );
153
154 STATIC
155 VOID
156 SendBlock (
157 );
158
159 STATIC
160 VOID
161 Output (
162 IN UINT32 c,
163 IN UINT32 p
164 );
165
166 STATIC
167 VOID
168 HufEncodeStart (
169 );
170
171 STATIC
172 VOID
173 HufEncodeEnd (
174 );
175
176 STATIC
177 VOID
178 MakeCrcTable (
179 );
180
181 STATIC
182 VOID
183 PutBits (
184 IN INT32 n,
185 IN UINT32 x
186 );
187
188 STATIC
189 INT32
190 FreadCrc (
191 OUT UINT8 *p,
192 IN INT32 n
193 );
194
195 STATIC
196 VOID
197 InitPutBits (
198 );
199
200 STATIC
201 VOID
202 CountLen (
203 IN INT32 i
204 );
205
206 STATIC
207 VOID
208 MakeLen (
209 IN INT32 Root
210 );
211
212 STATIC
213 VOID
214 DownHeap (
215 IN INT32 i
216 );
217
218 STATIC
219 VOID
220 MakeCode (
221 IN INT32 n,
222 IN UINT8 Len[],
223 OUT UINT16 Code[]
224 );
225
226 STATIC
227 INT32
228 MakeTree (
229 IN INT32 NParm,
230 IN UINT16 FreqParm[],
231 OUT UINT8 LenParm[],
232 OUT UINT16 CodeParm[]
233 );
234
235
236 //
237 // Global Variables
238 //
239
240 STATIC UINT8 *mSrc, *mDst, *mSrcUpperLimit, *mDstUpperLimit;
241
242 STATIC UINT8 *mLevel, *mText, *mChildCount, *mBuf, mCLen[NC], mPTLen[NPT], *mLen;
243 STATIC INT16 mHeap[NC + 1];
244 STATIC INT32 mRemainder, mMatchLen, mBitCount, mHeapSize, mN;
245 STATIC UINT32 mBufSiz = 0, mOutputPos, mOutputMask, mSubBitBuf, mCrc;
246 STATIC UINT32 mCompSize, mOrigSize;
247
248 STATIC UINT16 *mFreq, *mSortPtr, mLenCnt[17], mLeft[2 * NC - 1], mRight[2 * NC - 1],
249 mCrcTable[UINT8_MAX + 1], mCFreq[2 * NC - 1],mCCode[NC],
250 mPFreq[2 * NP - 1], mPTCode[NPT], mTFreq[2 * NT - 1];
251
252 STATIC NODE mPos, mMatchPos, mAvail, *mPosition, *mParent, *mPrev, *mNext = NULL;
253
254
255 //
256 // functions
257 //
258
259 EFI_STATUS
EfiCompress(IN UINT8 * SrcBuffer,IN UINT32 SrcSize,IN UINT8 * DstBuffer,IN OUT UINT32 * DstSize)260 EfiCompress (
261 IN UINT8 *SrcBuffer,
262 IN UINT32 SrcSize,
263 IN UINT8 *DstBuffer,
264 IN OUT UINT32 *DstSize
265 )
266 /*++
267
268 Routine Description:
269
270 The main compression routine.
271
272 Arguments:
273
274 SrcBuffer - The buffer storing the source data
275 SrcSize - The size of source data
276 DstBuffer - The buffer to store the compressed data
277 DstSize - On input, the size of DstBuffer; On output,
278 the size of the actual compressed data.
279
280 Returns:
281
282 EFI_BUFFER_TOO_SMALL - The DstBuffer is too small. In this case,
283 DstSize contains the size needed.
284 EFI_SUCCESS - Compression is successful.
285
286 --*/
287 {
288 EFI_STATUS Status = EFI_SUCCESS;
289
290 //
291 // Initializations
292 //
293 mBufSiz = 0;
294 mBuf = NULL;
295 mText = NULL;
296 mLevel = NULL;
297 mChildCount = NULL;
298 mPosition = NULL;
299 mParent = NULL;
300 mPrev = NULL;
301 mNext = NULL;
302
303
304 mSrc = SrcBuffer;
305 mSrcUpperLimit = mSrc + SrcSize;
306 mDst = DstBuffer;
307 mDstUpperLimit = mDst + *DstSize;
308
309 PutDword(0L);
310 PutDword(0L);
311
312 MakeCrcTable ();
313
314 mOrigSize = mCompSize = 0;
315 mCrc = INIT_CRC;
316
317 //
318 // Compress it
319 //
320
321 Status = Encode();
322 if (EFI_ERROR (Status)) {
323 return EFI_OUT_OF_RESOURCES;
324 }
325
326 //
327 // Null terminate the compressed data
328 //
329 if (mDst < mDstUpperLimit) {
330 *mDst++ = 0;
331 }
332
333 //
334 // Fill in compressed size and original size
335 //
336 mDst = DstBuffer;
337 PutDword(mCompSize+1);
338 PutDword(mOrigSize);
339
340 //
341 // Return
342 //
343
344 if (mCompSize + 1 + 8 > *DstSize) {
345 *DstSize = mCompSize + 1 + 8;
346 return EFI_BUFFER_TOO_SMALL;
347 } else {
348 *DstSize = mCompSize + 1 + 8;
349 return EFI_SUCCESS;
350 }
351
352 }
353
354 STATIC
355 VOID
PutDword(IN UINT32 Data)356 PutDword(
357 IN UINT32 Data
358 )
359 /*++
360
361 Routine Description:
362
363 Put a dword to output stream
364
365 Arguments:
366
367 Data - the dword to put
368
369 Returns: (VOID)
370
371 --*/
372 {
373 if (mDst < mDstUpperLimit) {
374 *mDst++ = (UINT8)(((UINT8)(Data )) & 0xff);
375 }
376
377 if (mDst < mDstUpperLimit) {
378 *mDst++ = (UINT8)(((UINT8)(Data >> 0x08)) & 0xff);
379 }
380
381 if (mDst < mDstUpperLimit) {
382 *mDst++ = (UINT8)(((UINT8)(Data >> 0x10)) & 0xff);
383 }
384
385 if (mDst < mDstUpperLimit) {
386 *mDst++ = (UINT8)(((UINT8)(Data >> 0x18)) & 0xff);
387 }
388 }
389
390 STATIC
391 EFI_STATUS
AllocateMemory()392 AllocateMemory ()
393 /*++
394
395 Routine Description:
396
397 Allocate memory spaces for data structures used in compression process
398
399 Argements: (VOID)
400
401 Returns:
402
403 EFI_SUCCESS - Memory is allocated successfully
404 EFI_OUT_OF_RESOURCES - Allocation fails
405
406 --*/
407 {
408 UINT32 i;
409
410 mText = malloc (WNDSIZ * 2 + MAXMATCH);
411 if (mText == NULL) {
412 return EFI_OUT_OF_RESOURCES;
413 }
414 for (i = 0 ; i < WNDSIZ * 2 + MAXMATCH; i ++) {
415 mText[i] = 0;
416 }
417
418 mLevel = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof(*mLevel));
419 mChildCount = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof(*mChildCount));
420 mPosition = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof(*mPosition));
421 mParent = malloc (WNDSIZ * 2 * sizeof(*mParent));
422 mPrev = malloc (WNDSIZ * 2 * sizeof(*mPrev));
423 mNext = malloc ((MAX_HASH_VAL + 1) * sizeof(*mNext));
424 if (mLevel == NULL || mChildCount == NULL || mPosition == NULL ||
425 mParent == NULL || mPrev == NULL || mNext == NULL) {
426 return EFI_OUT_OF_RESOURCES;
427 }
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
FreeMemory()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
InitSlide()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
Child(IN NODE q,IN UINT8 c)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
MakeChild(IN NODE q,IN UINT8 c,IN NODE r)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
Split(NODE Old)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
InsertNode()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
DeleteNode()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
GetNextMatch()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
Encode()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
CountTFreq()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
WritePTLen(IN INT32 n,IN INT32 nbit,IN INT32 Special)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
WriteCLen()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
EncodeC(IN INT32 c)1078 EncodeC (
1079 IN INT32 c
1080 )
1081 {
1082 PutBits(mCLen[c], mCCode[c]);
1083 }
1084
1085 STATIC
1086 VOID
EncodeP(IN UINT32 p)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
SendBlock()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
Output(IN UINT32 c,IN UINT32 p)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
HufEncodeStart()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
HufEncodeEnd()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
MakeCrcTable()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
PutBits(IN INT32 n,IN UINT32 x)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
FreadCrc(OUT UINT8 * p,IN INT32 n)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
InitPutBits()1361 InitPutBits ()
1362 {
1363 mBitCount = UINT8_BIT;
1364 mSubBitBuf = 0;
1365 }
1366
1367 STATIC
1368 VOID
CountLen(IN INT32 i)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
MakeLen(IN INT32 Root)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
DownHeap(IN INT32 i)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
MakeCode(IN INT32 n,IN UINT8 Len[],OUT UINT16 Code[])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
MakeTree(IN INT32 NParm,IN UINT16 FreqParm[],OUT UINT8 LenParm[],OUT UINT16 CodeParm[])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
1598