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 - 2011, 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>
30 #define UINT8_MAX 0xff
35 #define WNDSIZ (1U << WNDBIT)
37 #define BLKSIZ (1U << 14) // 16 * 1024U
38 #define PERC_FLAG 0x8000U
41 #define MAX_HASH_VAL (3 * WNDSIZ + (WNDSIZ / 512 + 1) * UINT8_MAX)
42 #define HASH(LoopVar7, LoopVar5) ((LoopVar7) + ((LoopVar5) << (WNDBIT - 9)) + WNDSIZ * 2)
43 #define CRCPOLY 0xA001
44 #define UPDATE_CRC(LoopVar5) mCrc = mCrcTable[(mCrc ^ (LoopVar5)) & 0xFF] ^ (mCrc >> UINT8_BIT)
47 // C: the Char&Len Set; P: the Position Set; T: the exTra Set
49 #define NC (UINT8_MAX + MAXMATCH + 2 - THRESHOLD)
51 #define NP (WNDBIT + 1)
53 #define NT (CODE_BIT + 3)
61 // Function Prototypes
65 Put a dword to output stream
67 @param[in] Data The dword to put.
80 STATIC UINT8
*mSrcUpperLimit
;
81 STATIC UINT8
*mDstUpperLimit
;
85 STATIC UINT8
*mChildCount
;
87 STATIC UINT8 mCLen
[NC
];
88 STATIC UINT8 mPTLen
[NPT
];
90 STATIC INT16 mHeap
[NC
+ 1];
91 STATIC INT32 mRemainder
;
92 STATIC INT32 mMatchLen
;
93 STATIC INT32 mBitCount
;
94 STATIC INT32 mHeapSize
;
95 STATIC INT32 mTempInt32
;
96 STATIC UINT32 mBufSiz
= 0;
97 STATIC UINT32 mOutputPos
;
98 STATIC UINT32 mOutputMask
;
99 STATIC UINT32 mSubBitBuf
;
101 STATIC UINT32 mCompSize
;
102 STATIC UINT32 mOrigSize
;
104 STATIC UINT16
*mFreq
;
105 STATIC UINT16
*mSortPtr
;
106 STATIC UINT16 mLenCnt
[17];
107 STATIC UINT16 mLeft
[2 * NC
- 1];
108 STATIC UINT16 mRight
[2 * NC
- 1];
109 STATIC UINT16 mCrcTable
[UINT8_MAX
+ 1];
110 STATIC UINT16 mCFreq
[2 * NC
- 1];
111 STATIC UINT16 mCCode
[NC
];
112 STATIC UINT16 mPFreq
[2 * NP
- 1];
113 STATIC UINT16 mPTCode
[NPT
];
114 STATIC UINT16 mTFreq
[2 * NT
- 1];
117 STATIC NODE mMatchPos
;
119 STATIC NODE
*mPosition
;
120 STATIC NODE
*mParent
;
122 STATIC NODE
*mNext
= NULL
;
123 INT32 mHuffmanDepth
= 0;
141 for (LoopVar1
= 0; LoopVar1
<= UINT8_MAX
; LoopVar1
++) {
143 for (LoopVar2
= 0; LoopVar2
< UINT8_BIT
; LoopVar2
++) {
144 if ((LoopVar4
& 1) != 0) {
145 LoopVar4
= (LoopVar4
>> 1) ^ CRCPOLY
;
151 mCrcTable
[LoopVar1
] = (UINT16
) LoopVar4
;
156 Put a dword to output stream
158 @param[in] Data The dword to put.
166 if (mDst
< mDstUpperLimit
) {
167 *mDst
++ = (UINT8
) (((UINT8
) (Data
)) & 0xff);
170 if (mDst
< mDstUpperLimit
) {
171 *mDst
++ = (UINT8
) (((UINT8
) (Data
>> 0x08)) & 0xff);
174 if (mDst
< mDstUpperLimit
) {
175 *mDst
++ = (UINT8
) (((UINT8
) (Data
>> 0x10)) & 0xff);
178 if (mDst
< mDstUpperLimit
) {
179 *mDst
++ = (UINT8
) (((UINT8
) (Data
>> 0x18)) & 0xff);
184 Allocate memory spaces for data structures used in compression process.
186 @retval EFI_SUCCESS Memory was allocated successfully.
187 @retval EFI_OUT_OF_RESOURCES A memory allocation failed.
195 mText
= AllocateZeroPool (WNDSIZ
* 2 + MAXMATCH
);
196 mLevel
= AllocateZeroPool ((WNDSIZ
+ UINT8_MAX
+ 1) * sizeof (*mLevel
));
197 mChildCount
= AllocateZeroPool ((WNDSIZ
+ UINT8_MAX
+ 1) * sizeof (*mChildCount
));
198 mPosition
= AllocateZeroPool ((WNDSIZ
+ UINT8_MAX
+ 1) * sizeof (*mPosition
));
199 mParent
= AllocateZeroPool (WNDSIZ
* 2 * sizeof (*mParent
));
200 mPrev
= AllocateZeroPool (WNDSIZ
* 2 * sizeof (*mPrev
));
201 mNext
= AllocateZeroPool ((MAX_HASH_VAL
+ 1) * sizeof (*mNext
));
204 mBuf
= AllocateZeroPool (mBufSiz
);
205 while (mBuf
== NULL
) {
206 mBufSiz
= (mBufSiz
/ 10U) * 9U;
207 if (mBufSiz
< 4 * 1024U) {
208 return EFI_OUT_OF_RESOURCES
;
211 mBuf
= AllocateZeroPool (mBufSiz
);
220 Called when compression is completed to free memory previously allocated.
229 SHELL_FREE_NON_NULL (mText
);
230 SHELL_FREE_NON_NULL (mLevel
);
231 SHELL_FREE_NON_NULL (mChildCount
);
232 SHELL_FREE_NON_NULL (mPosition
);
233 SHELL_FREE_NON_NULL (mParent
);
234 SHELL_FREE_NON_NULL (mPrev
);
235 SHELL_FREE_NON_NULL (mNext
);
236 SHELL_FREE_NON_NULL (mBuf
);
240 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.
623 if (mPos
== WNDSIZ
* 2) {
624 Temp
= AllocateZeroPool (WNDSIZ
+ MAXMATCH
);
625 CopyMem (Temp
, &mText
[WNDSIZ
], WNDSIZ
+ MAXMATCH
);
626 CopyMem (&mText
[0], Temp
, WNDSIZ
+ MAXMATCH
);
628 LoopVar8
= FreadCrc (&mText
[WNDSIZ
+ MAXMATCH
], WNDSIZ
);
629 mRemainder
+= LoopVar8
;
638 Send entry LoopVar1 down the queue.
640 @param[in] LoopVar1 The index of the item to move.
653 // priority queue: send i-th entry down heap
657 while (LoopVar1
<= mHeapSize
) {
658 if (LoopVar1
< mHeapSize
&& mFreq
[mHeap
[LoopVar1
]] > mFreq
[mHeap
[LoopVar1
+ 1]]) {
662 if (mFreq
[LoopVar2
] <= mFreq
[mHeap
[LoopVar1
]]) {
666 mHeap
[i
] = mHeap
[LoopVar1
];
671 mHeap
[i
] = (INT16
) LoopVar2
;
675 Count the number of each code length for a Huffman tree.
677 @param[in] LoopVar1 The top node.
685 if (LoopVar1
< mTempInt32
) {
686 mLenCnt
[(mHuffmanDepth
< 16) ? mHuffmanDepth
: 16]++;
689 CountLen (mLeft
[LoopVar1
]);
690 CountLen (mRight
[LoopVar1
]);
696 Create code length array for a Huffman tree.
698 @param[in] Root The root of the tree.
711 for (LoopVar1
= 0; LoopVar1
<= 16; LoopVar1
++) {
712 mLenCnt
[LoopVar1
] = 0;
718 // Adjust the length count array so that
719 // no code will be generated longer than its designated length
722 for (LoopVar1
= 16; LoopVar1
> 0; LoopVar1
--) {
723 Cum
+= mLenCnt
[LoopVar1
] << (16 - LoopVar1
);
726 while (Cum
!= (1U << 16)) {
728 for (LoopVar1
= 15; LoopVar1
> 0; LoopVar1
--) {
729 if (mLenCnt
[LoopVar1
] != 0) {
731 mLenCnt
[LoopVar1
+ 1] += 2;
739 for (LoopVar1
= 16; LoopVar1
> 0; LoopVar1
--) {
740 LoopVar2
= mLenCnt
[LoopVar1
];
742 while (LoopVar2
>= 0) {
743 mLen
[*mSortPtr
++] = (UINT8
) LoopVar1
;
750 Assign code to each symbol based on the code length array.
752 @param[in] LoopVar8 The number of symbols.
753 @param[in] Len The code length array.
754 @param[out] Code The stores codes for each symbol.
768 for (LoopVar1
= 1; LoopVar1
<= 16; LoopVar1
++) {
769 Start
[LoopVar1
+ 1] = (UINT16
) ((Start
[LoopVar1
] + mLenCnt
[LoopVar1
]) << 1);
772 for (LoopVar1
= 0; LoopVar1
< LoopVar8
; LoopVar1
++) {
773 Code
[LoopVar1
] = Start
[Len
[LoopVar1
]]++;
778 Generates Huffman codes given a frequency distribution of symbols.
780 @param[in] NParm The number of symbols.
781 @param[in] FreqParm The frequency of each symbol.
782 @param[out] LenParm The code length for each symbol.
783 @param[out] CodeParm The code for each symbol.
785 @return The root of the Huffman tree.
791 IN UINT16 FreqParm
[ ],
792 OUT UINT8 LenParm
[ ],
793 OUT UINT16 CodeParm
[ ]
805 // make tree, calculate len[], return root
813 for (LoopVar1
= 0; LoopVar1
< mTempInt32
; LoopVar1
++) {
815 if ((mFreq
[LoopVar1
]) != 0) {
817 mHeap
[mHeapSize
] = (INT16
) LoopVar1
;
822 CodeParm
[mHeap
[1]] = 0;
826 for (LoopVar1
= mHeapSize
/ 2; LoopVar1
>= 1; LoopVar1
--) {
828 // make priority queue
836 if (LoopVar1
< mTempInt32
) {
837 *mSortPtr
++ = (UINT16
) LoopVar1
;
840 mHeap
[1] = mHeap
[mHeapSize
--];
843 if (LoopVar2
< mTempInt32
) {
844 *mSortPtr
++ = (UINT16
) LoopVar2
;
848 mFreq
[LoopVar3
] = (UINT16
) (mFreq
[LoopVar1
] + mFreq
[LoopVar2
]);
849 mHeap
[1] = (INT16
) LoopVar3
;
851 mLeft
[LoopVar3
] = (UINT16
) LoopVar1
;
852 mRight
[LoopVar3
] = (UINT16
) LoopVar2
;
853 } while (mHeapSize
> 1);
857 MakeCode (NParm
, LenParm
, CodeParm
);
866 Outputs rightmost LoopVar8 bits of x
868 @param[in] LoopVar8 The rightmost LoopVar8 bits of the data is used.
869 @param[in] x The data.
880 if (LoopVar8
< mBitCount
) {
881 mSubBitBuf
|= x
<< (mBitCount
-= LoopVar8
);
884 Temp
= (UINT8
)(mSubBitBuf
| (x
>> (LoopVar8
-= mBitCount
)));
885 if (mDst
< mDstUpperLimit
) {
890 if (LoopVar8
< UINT8_BIT
) {
891 mSubBitBuf
= x
<< (mBitCount
= UINT8_BIT
- LoopVar8
);
894 Temp
= (UINT8
)(x
>> (LoopVar8
- UINT8_BIT
));
895 if (mDst
< mDstUpperLimit
) {
900 mSubBitBuf
= x
<< (mBitCount
= 2 * UINT8_BIT
- LoopVar8
);
906 Encode a signed 32 bit number.
908 @param[in] LoopVar5 The number to encode.
916 PutBits (mCLen
[LoopVar5
], mCCode
[LoopVar5
]);
920 Encode a unsigned 32 bit number.
922 @param[in] LoopVar7 The number to encode.
936 while (LoopVar6
!= 0) {
941 PutBits (mPTLen
[LoopVar5
], mPTCode
[LoopVar5
]);
943 PutBits(LoopVar5
- 1, LoopVar7
& (0xFFFFU
>> (17 - LoopVar5
)));
948 Count the frequencies for the Extra Set.
965 for (LoopVar1
= 0; LoopVar1
< NT
; LoopVar1
++) {
966 mTFreq
[LoopVar1
] = 0;
970 while (LoopVar8
> 0 && mCLen
[LoopVar8
- 1] == 0) {
975 while (LoopVar1
< LoopVar8
) {
976 LoopVar3
= mCLen
[LoopVar1
++];
979 while (LoopVar1
< LoopVar8
&& mCLen
[LoopVar1
] == 0) {
985 mTFreq
[0] = (UINT16
) (mTFreq
[0] + Count
);
986 } else if (Count
<= 18) {
988 } else if (Count
== 19) {
995 ASSERT((LoopVar3
+2)<(2 * NT
- 1));
996 mTFreq
[LoopVar3
+ 2]++;
1002 Outputs the code length array for the Extra Set or the Position Set.
1004 @param[in] LoopVar8 The number of symbols.
1005 @param[in] nbit The number of bits needed to represent 'LoopVar8'.
1006 @param[in] Special The special symbol that needs to be take care of.
1021 while (LoopVar8
> 0 && mPTLen
[LoopVar8
- 1] == 0) {
1025 PutBits (nbit
, LoopVar8
);
1027 while (LoopVar1
< LoopVar8
) {
1028 LoopVar3
= mPTLen
[LoopVar1
++];
1029 if (LoopVar3
<= 6) {
1030 PutBits (3, LoopVar3
);
1032 PutBits (LoopVar3
- 3, (1U << (LoopVar3
- 3)) - 2);
1035 if (LoopVar1
== Special
) {
1036 while (LoopVar1
< 6 && mPTLen
[LoopVar1
] == 0) {
1040 PutBits (2, (LoopVar1
- 3) & 3);
1046 Outputs the code length array for Char&Length Set
1064 while (LoopVar8
> 0 && mCLen
[LoopVar8
- 1] == 0) {
1068 PutBits (CBIT
, LoopVar8
);
1070 while (LoopVar1
< LoopVar8
) {
1071 LoopVar3
= mCLen
[LoopVar1
++];
1072 if (LoopVar3
== 0) {
1074 while (LoopVar1
< LoopVar8
&& mCLen
[LoopVar1
] == 0) {
1080 for (LoopVar3
= 0; LoopVar3
< Count
; LoopVar3
++) {
1081 PutBits (mPTLen
[0], mPTCode
[0]);
1083 } else if (Count
<= 18) {
1084 PutBits (mPTLen
[1], mPTCode
[1]);
1085 PutBits (4, Count
- 3);
1086 } else if (Count
== 19) {
1087 PutBits (mPTLen
[0], mPTCode
[0]);
1088 PutBits (mPTLen
[1], mPTCode
[1]);
1091 PutBits (mPTLen
[2], mPTCode
[2]);
1092 PutBits (CBIT
, Count
- 20);
1095 ASSERT((LoopVar3
+2)<NPT
);
1096 PutBits (mPTLen
[LoopVar3
+ 2], mPTCode
[LoopVar3
+ 2]);
1102 Huffman code the block and output it.
1124 Root
= MakeTree (NC
, mCFreq
, mCLen
, mCCode
);
1125 Size
= mCFreq
[Root
];
1129 Root
= MakeTree (NT
, mTFreq
, mPTLen
, mPTCode
);
1131 WritePTLen (NT
, TBIT
, 3);
1134 PutBits (TBIT
, Root
);
1142 PutBits (CBIT
, Root
);
1145 Root
= MakeTree (NP
, mPFreq
, mPTLen
, mPTCode
);
1147 WritePTLen (NP
, PBIT
, -1);
1150 PutBits (PBIT
, Root
);
1154 for (LoopVar1
= 0; LoopVar1
< Size
; LoopVar1
++) {
1155 if (LoopVar1
% UINT8_BIT
== 0) {
1156 Flags
= mBuf
[Pos
++];
1160 if ((Flags
& (1U << (UINT8_BIT
- 1))) != 0){
1161 EncodeC(mBuf
[Pos
++] + (1U << UINT8_BIT
));
1162 LoopVar3
= mBuf
[Pos
++] << UINT8_BIT
;
1163 LoopVar3
+= mBuf
[Pos
++];
1167 EncodeC (mBuf
[Pos
++]);
1171 SetMem (mCFreq
, NC
* sizeof (UINT16
), 0);
1172 SetMem (mPFreq
, NP
* sizeof (UINT16
), 0);
1176 Start the huffman encoding.
1185 SetMem (mCFreq
, NC
* sizeof (UINT16
), 0);
1186 SetMem (mPFreq
, NP
* sizeof (UINT16
), 0);
1188 mOutputPos
= mOutputMask
= 0;
1190 mBitCount
= UINT8_BIT
;
1195 Outputs an Original Character or a Pointer.
1197 @param[in] LoopVar5 The original character or the 'String Length' element of
1199 @param[in] LoopVar7 The 'Position' field of a Pointer.
1210 if ((mOutputMask
>>= 1) == 0) {
1211 mOutputMask
= 1U << (UINT8_BIT
- 1);
1212 if (mOutputPos
>= mBufSiz
- 3 * UINT8_BIT
) {
1217 CPos
= mOutputPos
++;
1220 mBuf
[mOutputPos
++] = (UINT8
) LoopVar5
;
1222 if (LoopVar5
>= (1U << UINT8_BIT
)) {
1223 mBuf
[CPos
] = (UINT8
)(mBuf
[CPos
]|mOutputMask
);
1224 mBuf
[mOutputPos
++] = (UINT8
)(LoopVar7
>> UINT8_BIT
);
1225 mBuf
[mOutputPos
++] = (UINT8
) LoopVar7
;
1227 while (LoopVar7
!=0) {
1236 End the huffman encoding.
1248 // Flush remaining bits
1250 PutBits (UINT8_BIT
- 1, 0);
1254 The main controlling routine for compression process.
1256 @retval EFI_SUCCESS The compression is successful.
1257 @retval EFI_OUT_0F_RESOURCES Not enough memory for compression process.
1269 Status
= AllocateMemory ();
1270 if (EFI_ERROR (Status
)) {
1279 mRemainder
= FreadCrc (&mText
[WNDSIZ
], WNDSIZ
+ MAXMATCH
);
1284 if (mMatchLen
> mRemainder
) {
1285 mMatchLen
= mRemainder
;
1288 while (mRemainder
> 0) {
1289 LastMatchLen
= mMatchLen
;
1290 LastMatchPos
= mMatchPos
;
1292 if (mMatchLen
> mRemainder
) {
1293 mMatchLen
= mRemainder
;
1296 if (mMatchLen
> LastMatchLen
|| LastMatchLen
< THRESHOLD
) {
1298 // Not enough benefits are gained by outputting a pointer,
1299 // so just output the original character
1301 CompressOutput(mText
[mPos
- 1], 0);
1304 // Outputting a pointer is beneficial enough, do it.
1307 CompressOutput(LastMatchLen
+ (UINT8_MAX
+ 1 - THRESHOLD
),
1308 (mPos
- LastMatchPos
- 2) & (WNDSIZ
- 1));
1310 while (LastMatchLen
> 0) {
1315 if (mMatchLen
> mRemainder
) {
1316 mMatchLen
= mRemainder
;
1327 The compression routine.
1329 @param[in] SrcBuffer The buffer containing the source data.
1330 @param[in] SrcSize The number of bytes in SrcBuffer.
1331 @param[in] DstBuffer The buffer to put the compressed image in.
1332 @param[in,out] DstSize On input the size (in bytes) of DstBuffer, on
1333 return the number of bytes placed in DstBuffer.
1335 @retval EFI_SUCCESS The compression was sucessful.
1336 @retval EFI_BUFFER_TOO_SMALL The buffer was too small. DstSize is required.
1344 IN OUT UINT64
*DstSize
1363 mSrcUpperLimit
= mSrc
+ SrcSize
;
1365 mDstUpperLimit
= mDst
+*DstSize
;
1372 mOrigSize
= mCompSize
= 0;
1379 if (EFI_ERROR (Status
)) {
1380 return EFI_OUT_OF_RESOURCES
;
1383 // Null terminate the compressed data
1385 if (mDst
< mDstUpperLimit
) {
1389 // Fill in compressed size and original size
1392 PutDword (mCompSize
+ 1);
1393 PutDword (mOrigSize
);
1398 if (mCompSize
+ 1 + 8 > *DstSize
) {
1399 *DstSize
= mCompSize
+ 1 + 8;
1400 return EFI_BUFFER_TOO_SMALL
;
1402 *DstSize
= mCompSize
+ 1 + 8;