]> git.proxmox.com Git - mirror_edk2.git/blob - BaseTools/Source/C/Common/TianoCompress.c
projects / mirror_edk2.git / blob
? search:


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