2 Main file for compression routine.
4 Compression routine. The compression algorithm is a mixture of
5 LZ77 and Huffman coding. LZ77 transforms the source data into a
6 sequence of Original Characters and Pointers to repeated strings.
7 This sequence is further divided into Blocks and Huffman codings
8 are applied to each Block.
10 Copyright (c) 2007 - 2014, Intel Corporation. All rights reserved.<BR>
11 This program and the accompanying materials
12 are licensed and made available under the terms and conditions of the BSD License
13 which accompanies this distribution. The full text of the license may be found at
14 http://opensource.org/licenses/bsd-license.php
16 THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
17 WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
21 #include <Library/MemoryAllocationLib.h>
22 #include <Library/BaseMemoryLib.h>
23 #include <Library/DebugLib.h>
24 #include <ShellBase.h>
31 #define UINT8_MAX 0xff
36 #define WNDSIZ (1U << WNDBIT)
38 #define BLKSIZ (1U << 14) // 16 * 1024U
39 #define PERC_FLAG 0x8000U
42 #define MAX_HASH_VAL (3 * WNDSIZ + (WNDSIZ / 512 + 1) * UINT8_MAX)
43 #define HASH(LoopVar7, LoopVar5) ((LoopVar7) + ((LoopVar5) << (WNDBIT - 9)) + WNDSIZ * 2)
44 #define CRCPOLY 0xA001
45 #define UPDATE_CRC(LoopVar5) mCrc = mCrcTable[(mCrc ^ (LoopVar5)) & 0xFF] ^ (mCrc >> UINT8_BIT)
48 // C: the Char&Len Set; P: the Position Set; T: the exTra Set
50 #define NC (UINT8_MAX + MAXMATCH + 2 - THRESHOLD)
52 #define NP (WNDBIT + 1)
54 #define NT (CODE_BIT + 3)
62 // Function Prototypes
66 Put a dword to output stream
68 @param[in] Data The dword to put.
81 STATIC UINT8
*mSrcUpperLimit
;
82 STATIC UINT8
*mDstUpperLimit
;
86 STATIC UINT8
*mChildCount
;
88 STATIC UINT8 mCLen
[NC
];
89 STATIC UINT8 mPTLen
[NPT
];
91 STATIC INT16 mHeap
[NC
+ 1];
92 STATIC INT32 mRemainder
;
93 STATIC INT32 mMatchLen
;
94 STATIC INT32 mBitCount
;
95 STATIC INT32 mHeapSize
;
96 STATIC INT32 mTempInt32
;
97 STATIC UINT32 mBufSiz
= 0;
98 STATIC UINT32 mOutputPos
;
99 STATIC UINT32 mOutputMask
;
100 STATIC UINT32 mSubBitBuf
;
102 STATIC UINT32 mCompSize
;
103 STATIC UINT32 mOrigSize
;
105 STATIC UINT16
*mFreq
;
106 STATIC UINT16
*mSortPtr
;
107 STATIC UINT16 mLenCnt
[17];
108 STATIC UINT16 mLeft
[2 * NC
- 1];
109 STATIC UINT16 mRight
[2 * NC
- 1];
110 STATIC UINT16 mCrcTable
[UINT8_MAX
+ 1];
111 STATIC UINT16 mCFreq
[2 * NC
- 1];
112 STATIC UINT16 mCCode
[NC
];
113 STATIC UINT16 mPFreq
[2 * NP
- 1];
114 STATIC UINT16 mPTCode
[NPT
];
115 STATIC UINT16 mTFreq
[2 * NT
- 1];
118 STATIC NODE mMatchPos
;
120 STATIC NODE
*mPosition
;
121 STATIC NODE
*mParent
;
123 STATIC NODE
*mNext
= NULL
;
124 INT32 mHuffmanDepth
= 0;
142 for (LoopVar1
= 0; LoopVar1
<= UINT8_MAX
; LoopVar1
++) {
144 for (LoopVar2
= 0; LoopVar2
< UINT8_BIT
; LoopVar2
++) {
145 if ((LoopVar4
& 1) != 0) {
146 LoopVar4
= (LoopVar4
>> 1) ^ CRCPOLY
;
152 mCrcTable
[LoopVar1
] = (UINT16
) LoopVar4
;
157 Put a dword to output stream
159 @param[in] Data The dword to put.
167 if (mDst
< mDstUpperLimit
) {
168 *mDst
++ = (UINT8
) (((UINT8
) (Data
)) & 0xff);
171 if (mDst
< mDstUpperLimit
) {
172 *mDst
++ = (UINT8
) (((UINT8
) (Data
>> 0x08)) & 0xff);
175 if (mDst
< mDstUpperLimit
) {
176 *mDst
++ = (UINT8
) (((UINT8
) (Data
>> 0x10)) & 0xff);
179 if (mDst
< mDstUpperLimit
) {
180 *mDst
++ = (UINT8
) (((UINT8
) (Data
>> 0x18)) & 0xff);
185 Allocate memory spaces for data structures used in compression process.
187 @retval EFI_SUCCESS Memory was allocated successfully.
188 @retval EFI_OUT_OF_RESOURCES A memory allocation failed.
196 mText
= AllocateZeroPool (WNDSIZ
* 2 + MAXMATCH
);
197 mLevel
= AllocateZeroPool ((WNDSIZ
+ UINT8_MAX
+ 1) * sizeof (*mLevel
));
198 mChildCount
= AllocateZeroPool ((WNDSIZ
+ UINT8_MAX
+ 1) * sizeof (*mChildCount
));
199 mPosition
= AllocateZeroPool ((WNDSIZ
+ UINT8_MAX
+ 1) * sizeof (*mPosition
));
200 mParent
= AllocateZeroPool (WNDSIZ
* 2 * sizeof (*mParent
));
201 mPrev
= AllocateZeroPool (WNDSIZ
* 2 * sizeof (*mPrev
));
202 mNext
= AllocateZeroPool ((MAX_HASH_VAL
+ 1) * sizeof (*mNext
));
205 mBuf
= AllocateZeroPool (mBufSiz
);
206 while (mBuf
== NULL
) {
207 mBufSiz
= (mBufSiz
/ 10U) * 9U;
208 if (mBufSiz
< 4 * 1024U) {
209 return EFI_OUT_OF_RESOURCES
;
212 mBuf
= AllocateZeroPool (mBufSiz
);
221 Called when compression is completed to free memory previously allocated.
230 SHELL_FREE_NON_NULL (mText
);
231 SHELL_FREE_NON_NULL (mLevel
);
232 SHELL_FREE_NON_NULL (mChildCount
);
233 SHELL_FREE_NON_NULL (mPosition
);
234 SHELL_FREE_NON_NULL (mParent
);
235 SHELL_FREE_NON_NULL (mPrev
);
236 SHELL_FREE_NON_NULL (mNext
);
237 SHELL_FREE_NON_NULL (mBuf
);
241 Initialize String Info Log data structures.
251 SetMem (mLevel
+ WNDSIZ
, (UINT8_MAX
+ 1) * sizeof (UINT8
), 1);
252 SetMem (mPosition
+ WNDSIZ
, (UINT8_MAX
+ 1) * sizeof (NODE
), 0);
254 SetMem (mParent
+ WNDSIZ
, WNDSIZ
* sizeof (NODE
), 0);
257 for (LoopVar1
= 1; LoopVar1
< WNDSIZ
- 1; LoopVar1
++) {
258 mNext
[LoopVar1
] = (NODE
) (LoopVar1
+ 1);
261 mNext
[WNDSIZ
- 1] = NIL
;
262 SetMem (mNext
+ WNDSIZ
* 2, (MAX_HASH_VAL
- WNDSIZ
* 2 + 1) * sizeof (NODE
), 0);
266 Find child node given the parent node and the edge character
268 @param[in] LoopVar6 The parent node.
269 @param[in] LoopVar5 The edge character.
271 @return The child node.
272 @retval NIL(Zero) No child could be found.
284 LoopVar4
= mNext
[HASH (LoopVar6
, LoopVar5
)];
285 mParent
[NIL
] = LoopVar6
; /* sentinel */
286 while (mParent
[LoopVar4
] != LoopVar6
) {
287 LoopVar4
= mNext
[LoopVar4
];
294 Create a new child for a given parent node.
296 @param[in] LoopVar6 The parent node.
297 @param[in] LoopVar5 The edge character.
298 @param[in] LoopVar4 The child node.
312 LoopVar12
= (NODE
) HASH (LoopVar6
, LoopVar5
);
313 LoopVar10
= mNext
[LoopVar12
];
314 mNext
[LoopVar12
] = LoopVar4
;
315 mNext
[LoopVar4
] = LoopVar10
;
316 mPrev
[LoopVar10
] = LoopVar4
;
317 mPrev
[LoopVar4
] = LoopVar12
;
318 mParent
[LoopVar4
] = LoopVar6
;
319 mChildCount
[LoopVar6
]++;
325 @param[in] Old The node to split.
339 mChildCount
[New
] = 0;
340 LoopVar10
= mPrev
[Old
];
341 mPrev
[New
] = LoopVar10
;
342 mNext
[LoopVar10
] = New
;
343 LoopVar10
= mNext
[Old
];
344 mNext
[New
] = LoopVar10
;
345 mPrev
[LoopVar10
] = New
;
346 mParent
[New
] = mParent
[Old
];
347 mLevel
[New
] = (UINT8
) mMatchLen
;
348 mPosition
[New
] = mPos
;
349 MakeChild (New
, mText
[mMatchPos
+ mMatchLen
], Old
);
350 MakeChild (New
, mText
[mPos
+ mMatchLen
], mPos
);
354 Insert string info for current position into the String Info Log.
374 if (mMatchLen
>= 4) {
376 // We have just got a long match, the target tree
377 // can be located by MatchPos + 1. Travese the tree
378 // from bottom up to get to a proper starting point.
379 // The usage of PERC_FLAG ensures proper node deletion
380 // in DeleteNode() later.
383 LoopVar4
= (NODE
) ((mMatchPos
+ 1) | WNDSIZ
);
384 LoopVar6
= mParent
[LoopVar4
];
385 while (LoopVar6
== NIL
) {
386 LoopVar4
= mNext
[LoopVar4
];
387 LoopVar6
= mParent
[LoopVar4
];
390 while (mLevel
[LoopVar6
] >= mMatchLen
) {
392 LoopVar6
= mParent
[LoopVar6
];
395 LoopVar10
= LoopVar6
;
396 while (mPosition
[LoopVar10
] < 0) {
397 mPosition
[LoopVar10
] = mPos
;
398 LoopVar10
= mParent
[LoopVar10
];
401 if (LoopVar10
< WNDSIZ
) {
402 mPosition
[LoopVar10
] = (NODE
) (mPos
| PERC_FLAG
);
406 // Locate the target tree
408 LoopVar6
= (NODE
) (mText
[mPos
] + WNDSIZ
);
409 LoopVar5
= mText
[mPos
+ 1];
410 LoopVar4
= Child (LoopVar6
, LoopVar5
);
411 if (LoopVar4
== NIL
) {
412 MakeChild (LoopVar6
, LoopVar5
, mPos
);
420 // Traverse down the tree to find a match.
421 // Update Position value along the route.
422 // Node split or creation is involved.
425 if (LoopVar4
>= WNDSIZ
) {
427 mMatchPos
= LoopVar4
;
429 LoopVar2
= mLevel
[LoopVar4
];
430 mMatchPos
= (NODE
) (mPosition
[LoopVar4
] & ~PERC_FLAG
);
433 if (mMatchPos
>= mPos
) {
437 TempString3
= &mText
[mPos
+ mMatchLen
];
438 TempString2
= &mText
[mMatchPos
+ mMatchLen
];
439 while (mMatchLen
< LoopVar2
) {
440 if (*TempString3
!= *TempString2
) {
450 if (mMatchLen
>= MAXMATCH
) {
454 mPosition
[LoopVar4
] = mPos
;
456 LoopVar4
= Child (LoopVar6
, *TempString3
);
457 if (LoopVar4
== NIL
) {
458 MakeChild (LoopVar6
, *TempString3
, mPos
);
465 LoopVar10
= mPrev
[LoopVar4
];
466 mPrev
[mPos
] = LoopVar10
;
467 mNext
[LoopVar10
] = mPos
;
468 LoopVar10
= mNext
[LoopVar4
];
469 mNext
[mPos
] = LoopVar10
;
470 mPrev
[LoopVar10
] = mPos
;
471 mParent
[mPos
] = LoopVar6
;
472 mParent
[LoopVar4
] = NIL
;
475 // Special usage of 'next'
477 mNext
[LoopVar4
] = mPos
;
482 Delete outdated string info. (The Usage of PERC_FLAG
483 ensures a clean deletion).
502 if (mParent
[mPos
] == NIL
) {
506 LoopVar4
= mPrev
[mPos
];
507 LoopVar11
= mNext
[mPos
];
508 mNext
[LoopVar4
] = LoopVar11
;
509 mPrev
[LoopVar11
] = LoopVar4
;
510 LoopVar4
= mParent
[mPos
];
512 if (LoopVar4
>= WNDSIZ
) {
516 mChildCount
[LoopVar4
]--;
517 if (mChildCount
[LoopVar4
] > 1) {
521 LoopVar10
= (NODE
) (mPosition
[LoopVar4
] & ~PERC_FLAG
);
522 if (LoopVar10
>= mPos
) {
526 LoopVar11
= LoopVar10
;
527 LoopVar6
= mParent
[LoopVar4
];
528 LoopVar9
= mPosition
[LoopVar6
];
529 while ((LoopVar9
& PERC_FLAG
) != 0){
530 LoopVar9
&= ~PERC_FLAG
;
531 if (LoopVar9
>= mPos
) {
535 if (LoopVar9
> LoopVar11
) {
536 LoopVar11
= LoopVar9
;
539 mPosition
[LoopVar6
] = (NODE
) (LoopVar11
| WNDSIZ
);
540 LoopVar6
= mParent
[LoopVar6
];
541 LoopVar9
= mPosition
[LoopVar6
];
544 if (LoopVar6
< WNDSIZ
) {
545 if (LoopVar9
>= mPos
) {
549 if (LoopVar9
> LoopVar11
) {
550 LoopVar11
= LoopVar9
;
553 mPosition
[LoopVar6
] = (NODE
) (LoopVar11
| WNDSIZ
| PERC_FLAG
);
556 LoopVar11
= Child (LoopVar4
, mText
[LoopVar10
+ mLevel
[LoopVar4
]]);
557 LoopVar10
= mPrev
[LoopVar11
];
558 LoopVar9
= mNext
[LoopVar11
];
559 mNext
[LoopVar10
] = LoopVar9
;
560 mPrev
[LoopVar9
] = LoopVar10
;
561 LoopVar10
= mPrev
[LoopVar4
];
562 mNext
[LoopVar10
] = LoopVar11
;
563 mPrev
[LoopVar11
] = LoopVar10
;
564 LoopVar10
= mNext
[LoopVar4
];
565 mPrev
[LoopVar10
] = LoopVar11
;
566 mNext
[LoopVar11
] = LoopVar10
;
567 mParent
[LoopVar11
] = mParent
[LoopVar4
];
568 mParent
[LoopVar4
] = NIL
;
569 mNext
[LoopVar4
] = mAvail
;
576 @param[out] LoopVar7 The buffer to hold the data.
577 @param[in] LoopVar8 The number of bytes to read.
579 @return The number of bytes actually read.
590 for (LoopVar1
= 0; mSrc
< mSrcUpperLimit
&& LoopVar1
< LoopVar8
; LoopVar1
++) {
591 *LoopVar7
++ = *mSrc
++;
596 LoopVar7
-= LoopVar8
;
597 mOrigSize
+= LoopVar8
;
599 while (LoopVar1
>= 0) {
600 UPDATE_CRC (*LoopVar7
++);
608 Advance the current position (read in new data if needed).
609 Delete outdated string info. Find a match string for current position.
611 @retval TRUE The operation was successful.
612 @retval FALSE The operation failed due to insufficient memory.
625 if (mPos
== WNDSIZ
* 2) {
626 Temp
= AllocateZeroPool (WNDSIZ
+ MAXMATCH
);
630 CopyMem (Temp
, &mText
[WNDSIZ
], WNDSIZ
+ MAXMATCH
);
631 CopyMem (&mText
[0], Temp
, WNDSIZ
+ MAXMATCH
);
633 LoopVar8
= FreadCrc (&mText
[WNDSIZ
+ MAXMATCH
], WNDSIZ
);
634 mRemainder
+= LoopVar8
;
645 Send entry LoopVar1 down the queue.
647 @param[in] LoopVar1 The index of the item to move.
660 // priority queue: send i-th entry down heap
664 while (LoopVar1
<= mHeapSize
) {
665 if (LoopVar1
< mHeapSize
&& mFreq
[mHeap
[LoopVar1
]] > mFreq
[mHeap
[LoopVar1
+ 1]]) {
669 if (mFreq
[LoopVar2
] <= mFreq
[mHeap
[LoopVar1
]]) {
673 mHeap
[i
] = mHeap
[LoopVar1
];
678 mHeap
[i
] = (INT16
) LoopVar2
;
682 Count the number of each code length for a Huffman tree.
684 @param[in] LoopVar1 The top node.
692 if (LoopVar1
< mTempInt32
) {
693 mLenCnt
[(mHuffmanDepth
< 16) ? mHuffmanDepth
: 16]++;
696 CountLen (mLeft
[LoopVar1
]);
697 CountLen (mRight
[LoopVar1
]);
703 Create code length array for a Huffman tree.
705 @param[in] Root The root of the tree.
718 for (LoopVar1
= 0; LoopVar1
<= 16; LoopVar1
++) {
719 mLenCnt
[LoopVar1
] = 0;
725 // Adjust the length count array so that
726 // no code will be generated longer than its designated length
729 for (LoopVar1
= 16; LoopVar1
> 0; LoopVar1
--) {
730 Cum
+= mLenCnt
[LoopVar1
] << (16 - LoopVar1
);
733 while (Cum
!= (1U << 16)) {
735 for (LoopVar1
= 15; LoopVar1
> 0; LoopVar1
--) {
736 if (mLenCnt
[LoopVar1
] != 0) {
738 mLenCnt
[LoopVar1
+ 1] += 2;
746 for (LoopVar1
= 16; LoopVar1
> 0; LoopVar1
--) {
747 LoopVar2
= mLenCnt
[LoopVar1
];
749 while (LoopVar2
>= 0) {
750 mLen
[*mSortPtr
++] = (UINT8
) LoopVar1
;
757 Assign code to each symbol based on the code length array.
759 @param[in] LoopVar8 The number of symbols.
760 @param[in] Len The code length array.
761 @param[out] Code The stores codes for each symbol.
775 for (LoopVar1
= 1; LoopVar1
<= 16; LoopVar1
++) {
776 Start
[LoopVar1
+ 1] = (UINT16
) ((Start
[LoopVar1
] + mLenCnt
[LoopVar1
]) << 1);
779 for (LoopVar1
= 0; LoopVar1
< LoopVar8
; LoopVar1
++) {
780 Code
[LoopVar1
] = Start
[Len
[LoopVar1
]]++;
785 Generates Huffman codes given a frequency distribution of symbols.
787 @param[in] NParm The number of symbols.
788 @param[in] FreqParm The frequency of each symbol.
789 @param[out] LenParm The code length for each symbol.
790 @param[out] CodeParm The code for each symbol.
792 @return The root of the Huffman tree.
798 IN UINT16 FreqParm
[ ],
799 OUT UINT8 LenParm
[ ],
800 OUT UINT16 CodeParm
[ ]
812 // make tree, calculate len[], return root
820 for (LoopVar1
= 0; LoopVar1
< mTempInt32
; LoopVar1
++) {
822 if ((mFreq
[LoopVar1
]) != 0) {
824 mHeap
[mHeapSize
] = (INT16
) LoopVar1
;
829 CodeParm
[mHeap
[1]] = 0;
833 for (LoopVar1
= mHeapSize
/ 2; LoopVar1
>= 1; LoopVar1
--) {
835 // make priority queue
843 if (LoopVar1
< mTempInt32
) {
844 *mSortPtr
++ = (UINT16
) LoopVar1
;
847 mHeap
[1] = mHeap
[mHeapSize
--];
850 if (LoopVar2
< mTempInt32
) {
851 *mSortPtr
++ = (UINT16
) LoopVar2
;
855 mFreq
[LoopVar3
] = (UINT16
) (mFreq
[LoopVar1
] + mFreq
[LoopVar2
]);
856 mHeap
[1] = (INT16
) LoopVar3
;
858 mLeft
[LoopVar3
] = (UINT16
) LoopVar1
;
859 mRight
[LoopVar3
] = (UINT16
) LoopVar2
;
860 } while (mHeapSize
> 1);
864 MakeCode (NParm
, LenParm
, CodeParm
);
873 Outputs rightmost LoopVar8 bits of x
875 @param[in] LoopVar8 The rightmost LoopVar8 bits of the data is used.
876 @param[in] x The data.
887 if (LoopVar8
< mBitCount
) {
888 mSubBitBuf
|= x
<< (mBitCount
-= LoopVar8
);
891 Temp
= (UINT8
)(mSubBitBuf
| (x
>> (LoopVar8
-= mBitCount
)));
892 if (mDst
< mDstUpperLimit
) {
897 if (LoopVar8
< UINT8_BIT
) {
898 mSubBitBuf
= x
<< (mBitCount
= UINT8_BIT
- LoopVar8
);
901 Temp
= (UINT8
)(x
>> (LoopVar8
- UINT8_BIT
));
902 if (mDst
< mDstUpperLimit
) {
907 mSubBitBuf
= x
<< (mBitCount
= 2 * UINT8_BIT
- LoopVar8
);
913 Encode a signed 32 bit number.
915 @param[in] LoopVar5 The number to encode.
923 PutBits (mCLen
[LoopVar5
], mCCode
[LoopVar5
]);
927 Encode a unsigned 32 bit number.
929 @param[in] LoopVar7 The number to encode.
943 while (LoopVar6
!= 0) {
948 PutBits (mPTLen
[LoopVar5
], mPTCode
[LoopVar5
]);
950 PutBits(LoopVar5
- 1, LoopVar7
& (0xFFFFU
>> (17 - LoopVar5
)));
955 Count the frequencies for the Extra Set.
972 for (LoopVar1
= 0; LoopVar1
< NT
; LoopVar1
++) {
973 mTFreq
[LoopVar1
] = 0;
977 while (LoopVar8
> 0 && mCLen
[LoopVar8
- 1] == 0) {
982 while (LoopVar1
< LoopVar8
) {
983 LoopVar3
= mCLen
[LoopVar1
++];
986 while (LoopVar1
< LoopVar8
&& mCLen
[LoopVar1
] == 0) {
992 mTFreq
[0] = (UINT16
) (mTFreq
[0] + Count
);
993 } else if (Count
<= 18) {
995 } else if (Count
== 19) {
1002 ASSERT((LoopVar3
+2)<(2 * NT
- 1));
1003 mTFreq
[LoopVar3
+ 2]++;
1009 Outputs the code length array for the Extra Set or the Position Set.
1011 @param[in] LoopVar8 The number of symbols.
1012 @param[in] nbit The number of bits needed to represent 'LoopVar8'.
1013 @param[in] Special The special symbol that needs to be take care of.
1028 while (LoopVar8
> 0 && mPTLen
[LoopVar8
- 1] == 0) {
1032 PutBits (nbit
, LoopVar8
);
1034 while (LoopVar1
< LoopVar8
) {
1035 LoopVar3
= mPTLen
[LoopVar1
++];
1036 if (LoopVar3
<= 6) {
1037 PutBits (3, LoopVar3
);
1039 PutBits (LoopVar3
- 3, (1U << (LoopVar3
- 3)) - 2);
1042 if (LoopVar1
== Special
) {
1043 while (LoopVar1
< 6 && mPTLen
[LoopVar1
] == 0) {
1047 PutBits (2, (LoopVar1
- 3) & 3);
1053 Outputs the code length array for Char&Length Set.
1070 while (LoopVar8
> 0 && mCLen
[LoopVar8
- 1] == 0) {
1074 PutBits (CBIT
, LoopVar8
);
1076 while (LoopVar1
< LoopVar8
) {
1077 LoopVar3
= mCLen
[LoopVar1
++];
1078 if (LoopVar3
== 0) {
1080 while (LoopVar1
< LoopVar8
&& mCLen
[LoopVar1
] == 0) {
1086 for (LoopVar3
= 0; LoopVar3
< Count
; LoopVar3
++) {
1087 PutBits (mPTLen
[0], mPTCode
[0]);
1089 } else if (Count
<= 18) {
1090 PutBits (mPTLen
[1], mPTCode
[1]);
1091 PutBits (4, Count
- 3);
1092 } else if (Count
== 19) {
1093 PutBits (mPTLen
[0], mPTCode
[0]);
1094 PutBits (mPTLen
[1], mPTCode
[1]);
1097 PutBits (mPTLen
[2], mPTCode
[2]);
1098 PutBits (CBIT
, Count
- 20);
1101 ASSERT((LoopVar3
+2)<NPT
);
1102 PutBits (mPTLen
[LoopVar3
+ 2], mPTCode
[LoopVar3
+ 2]);
1108 Huffman code the block and output it.
1130 Root
= MakeTree (NC
, mCFreq
, mCLen
, mCCode
);
1131 Size
= mCFreq
[Root
];
1135 Root
= MakeTree (NT
, mTFreq
, mPTLen
, mPTCode
);
1137 WritePTLen (NT
, TBIT
, 3);
1140 PutBits (TBIT
, Root
);
1148 PutBits (CBIT
, Root
);
1151 Root
= MakeTree (NP
, mPFreq
, mPTLen
, mPTCode
);
1153 WritePTLen (NP
, PBIT
, -1);
1156 PutBits (PBIT
, Root
);
1160 for (LoopVar1
= 0; LoopVar1
< Size
; LoopVar1
++) {
1161 if (LoopVar1
% UINT8_BIT
== 0) {
1162 Flags
= mBuf
[Pos
++];
1166 if ((Flags
& (1U << (UINT8_BIT
- 1))) != 0){
1167 EncodeC(mBuf
[Pos
++] + (1U << UINT8_BIT
));
1168 LoopVar3
= mBuf
[Pos
++] << UINT8_BIT
;
1169 LoopVar3
+= mBuf
[Pos
++];
1173 EncodeC (mBuf
[Pos
++]);
1177 SetMem (mCFreq
, NC
* sizeof (UINT16
), 0);
1178 SetMem (mPFreq
, NP
* sizeof (UINT16
), 0);
1182 Start the huffman encoding.
1191 SetMem (mCFreq
, NC
* sizeof (UINT16
), 0);
1192 SetMem (mPFreq
, NP
* sizeof (UINT16
), 0);
1194 mOutputPos
= mOutputMask
= 0;
1196 mBitCount
= UINT8_BIT
;
1201 Outputs an Original Character or a Pointer.
1203 @param[in] LoopVar5 The original character or the 'String Length' element of
1205 @param[in] LoopVar7 The 'Position' field of a Pointer.
1216 if ((mOutputMask
>>= 1) == 0) {
1217 mOutputMask
= 1U << (UINT8_BIT
- 1);
1218 if (mOutputPos
>= mBufSiz
- 3 * UINT8_BIT
) {
1223 CPos
= mOutputPos
++;
1226 mBuf
[mOutputPos
++] = (UINT8
) LoopVar5
;
1228 if (LoopVar5
>= (1U << UINT8_BIT
)) {
1229 mBuf
[CPos
] = (UINT8
)(mBuf
[CPos
]|mOutputMask
);
1230 mBuf
[mOutputPos
++] = (UINT8
)(LoopVar7
>> UINT8_BIT
);
1231 mBuf
[mOutputPos
++] = (UINT8
) LoopVar7
;
1233 while (LoopVar7
!=0) {
1242 End the huffman encoding.
1254 // Flush remaining bits
1256 PutBits (UINT8_BIT
- 1, 0);
1260 The main controlling routine for compression process.
1262 @retval EFI_SUCCESS The compression is successful.
1263 @retval EFI_OUT_0F_RESOURCES Not enough memory for compression process.
1275 Status
= AllocateMemory ();
1276 if (EFI_ERROR (Status
)) {
1285 mRemainder
= FreadCrc (&mText
[WNDSIZ
], WNDSIZ
+ MAXMATCH
);
1290 if (mMatchLen
> mRemainder
) {
1291 mMatchLen
= mRemainder
;
1294 while (mRemainder
> 0) {
1295 LastMatchLen
= mMatchLen
;
1296 LastMatchPos
= mMatchPos
;
1297 if (!GetNextMatch ()) {
1298 Status
= EFI_OUT_OF_RESOURCES
;
1300 if (mMatchLen
> mRemainder
) {
1301 mMatchLen
= mRemainder
;
1304 if (mMatchLen
> LastMatchLen
|| LastMatchLen
< THRESHOLD
) {
1306 // Not enough benefits are gained by outputting a pointer,
1307 // so just output the original character
1309 CompressOutput(mText
[mPos
- 1], 0);
1312 // Outputting a pointer is beneficial enough, do it.
1315 CompressOutput(LastMatchLen
+ (UINT8_MAX
+ 1 - THRESHOLD
),
1316 (mPos
- LastMatchPos
- 2) & (WNDSIZ
- 1));
1318 while (LastMatchLen
> 0) {
1319 if (!GetNextMatch ()) {
1320 Status
= EFI_OUT_OF_RESOURCES
;
1325 if (mMatchLen
> mRemainder
) {
1326 mMatchLen
= mRemainder
;
1337 The compression routine.
1339 @param[in] SrcBuffer The buffer containing the source data.
1340 @param[in] SrcSize The number of bytes in SrcBuffer.
1341 @param[in] DstBuffer The buffer to put the compressed image in.
1342 @param[in, out] DstSize On input the size (in bytes) of DstBuffer, on
1343 return the number of bytes placed in DstBuffer.
1345 @retval EFI_SUCCESS The compression was sucessful.
1346 @retval EFI_BUFFER_TOO_SMALL The buffer was too small. DstSize is required.
1354 IN OUT UINT64
*DstSize
1373 mSrcUpperLimit
= mSrc
+ SrcSize
;
1375 mDstUpperLimit
= mDst
+*DstSize
;
1382 mOrigSize
= mCompSize
= 0;
1389 if (EFI_ERROR (Status
)) {
1390 return EFI_OUT_OF_RESOURCES
;
1393 // Null terminate the compressed data
1395 if (mDst
< mDstUpperLimit
) {
1399 // Fill in compressed size and original size
1402 PutDword (mCompSize
+ 1);
1403 PutDword (mOrigSize
);
1408 if (mCompSize
+ 1 + 8 > *DstSize
) {
1409 *DstSize
= mCompSize
+ 1 + 8;
1410 return EFI_BUFFER_TOO_SMALL
;
1412 *DstSize
= mCompSize
+ 1 + 8;