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