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


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