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