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