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