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.
250 SetMem (mLevel
+ WNDSIZ
, (UINT8_MAX
+ 1) * sizeof (UINT8
), 1);
251 SetMem (mPosition
+ WNDSIZ
, (UINT8_MAX
+ 1) * sizeof (NODE
), 0);
253 SetMem (mParent
+ WNDSIZ
, WNDSIZ
* sizeof (NODE
), 0);
256 for (LoopVar1
= 1; LoopVar1
< WNDSIZ
- 1; LoopVar1
++) {
257 mNext
[LoopVar1
] = (NODE
) (LoopVar1
+ 1);
260 mNext
[WNDSIZ
- 1] = NIL
;
261 SetMem (mNext
+ WNDSIZ
* 2, (MAX_HASH_VAL
- WNDSIZ
* 2 + 1) * sizeof (NODE
), 0);
265 Find child node given the parent node and the edge character
267 @param[in] LoopVar6 The parent node.
268 @param[in] LoopVar5 The edge character.
270 @return The child node.
271 @retval NIL(Zero) No child could be found.
283 LoopVar4
= mNext
[HASH (LoopVar6
, LoopVar5
)];
284 mParent
[NIL
] = LoopVar6
; /* sentinel */
285 while (mParent
[LoopVar4
] != LoopVar6
) {
286 LoopVar4
= mNext
[LoopVar4
];
293 Create a new child for a given parent node.
295 @param[in] LoopVar6 The parent node.
296 @param[in] LoopVar5 The edge character.
297 @param[in] LoopVar4 The child node.
311 LoopVar12
= (NODE
) HASH (LoopVar6
, LoopVar5
);
312 LoopVar10
= mNext
[LoopVar12
];
313 mNext
[LoopVar12
] = LoopVar4
;
314 mNext
[LoopVar4
] = LoopVar10
;
315 mPrev
[LoopVar10
] = LoopVar4
;
316 mPrev
[LoopVar4
] = LoopVar12
;
317 mParent
[LoopVar4
] = LoopVar6
;
318 mChildCount
[LoopVar6
]++;
324 @param[in] Old The node to split.
338 mChildCount
[New
] = 0;
339 LoopVar10
= mPrev
[Old
];
340 mPrev
[New
] = LoopVar10
;
341 mNext
[LoopVar10
] = New
;
342 LoopVar10
= mNext
[Old
];
343 mNext
[New
] = LoopVar10
;
344 mPrev
[LoopVar10
] = New
;
345 mParent
[New
] = mParent
[Old
];
346 mLevel
[New
] = (UINT8
) mMatchLen
;
347 mPosition
[New
] = mPos
;
348 MakeChild (New
, mText
[mMatchPos
+ mMatchLen
], Old
);
349 MakeChild (New
, mText
[mPos
+ mMatchLen
], mPos
);
353 Insert string info for current position into the String Info Log.
373 if (mMatchLen
>= 4) {
375 // We have just got a long match, the target tree
376 // can be located by MatchPos + 1. Travese the tree
377 // from bottom up to get to a proper starting point.
378 // The usage of PERC_FLAG ensures proper node deletion
379 // in DeleteNode() later.
382 LoopVar4
= (NODE
) ((mMatchPos
+ 1) | WNDSIZ
);
383 LoopVar6
= mParent
[LoopVar4
];
384 while (LoopVar6
== NIL
) {
385 LoopVar4
= mNext
[LoopVar4
];
386 LoopVar6
= mParent
[LoopVar4
];
389 while (mLevel
[LoopVar6
] >= mMatchLen
) {
391 LoopVar6
= mParent
[LoopVar6
];
394 LoopVar10
= LoopVar6
;
395 while (mPosition
[LoopVar10
] < 0) {
396 mPosition
[LoopVar10
] = mPos
;
397 LoopVar10
= mParent
[LoopVar10
];
400 if (LoopVar10
< WNDSIZ
) {
401 mPosition
[LoopVar10
] = (NODE
) (mPos
| PERC_FLAG
);
405 // Locate the target tree
407 LoopVar6
= (NODE
) (mText
[mPos
] + WNDSIZ
);
408 LoopVar5
= mText
[mPos
+ 1];
409 LoopVar4
= Child (LoopVar6
, LoopVar5
);
410 if (LoopVar4
== NIL
) {
411 MakeChild (LoopVar6
, LoopVar5
, mPos
);
419 // Traverse down the tree to find a match.
420 // Update Position value along the route.
421 // Node split or creation is involved.
424 if (LoopVar4
>= WNDSIZ
) {
426 mMatchPos
= LoopVar4
;
428 LoopVar2
= mLevel
[LoopVar4
];
429 mMatchPos
= (NODE
) (mPosition
[LoopVar4
] & ~PERC_FLAG
);
432 if (mMatchPos
>= mPos
) {
436 TempString3
= &mText
[mPos
+ mMatchLen
];
437 TempString2
= &mText
[mMatchPos
+ mMatchLen
];
438 while (mMatchLen
< LoopVar2
) {
439 if (*TempString3
!= *TempString2
) {
449 if (mMatchLen
>= MAXMATCH
) {
453 mPosition
[LoopVar4
] = mPos
;
455 LoopVar4
= Child (LoopVar6
, *TempString3
);
456 if (LoopVar4
== NIL
) {
457 MakeChild (LoopVar6
, *TempString3
, mPos
);
464 LoopVar10
= mPrev
[LoopVar4
];
465 mPrev
[mPos
] = LoopVar10
;
466 mNext
[LoopVar10
] = mPos
;
467 LoopVar10
= mNext
[LoopVar4
];
468 mNext
[mPos
] = LoopVar10
;
469 mPrev
[LoopVar10
] = mPos
;
470 mParent
[mPos
] = LoopVar6
;
471 mParent
[LoopVar4
] = NIL
;
474 // Special usage of 'next'
476 mNext
[LoopVar4
] = mPos
;
481 Delete outdated string info. (The Usage of PERC_FLAG
482 ensures a clean deletion).
501 if (mParent
[mPos
] == NIL
) {
505 LoopVar4
= mPrev
[mPos
];
506 LoopVar11
= mNext
[mPos
];
507 mNext
[LoopVar4
] = LoopVar11
;
508 mPrev
[LoopVar11
] = LoopVar4
;
509 LoopVar4
= mParent
[mPos
];
511 if (LoopVar4
>= WNDSIZ
) {
515 mChildCount
[LoopVar4
]--;
516 if (mChildCount
[LoopVar4
] > 1) {
520 LoopVar10
= (NODE
) (mPosition
[LoopVar4
] & ~PERC_FLAG
);
521 if (LoopVar10
>= mPos
) {
525 LoopVar11
= LoopVar10
;
526 LoopVar6
= mParent
[LoopVar4
];
527 LoopVar9
= mPosition
[LoopVar6
];
528 while ((LoopVar9
& PERC_FLAG
) != 0){
529 LoopVar9
&= ~PERC_FLAG
;
530 if (LoopVar9
>= mPos
) {
534 if (LoopVar9
> LoopVar11
) {
535 LoopVar11
= LoopVar9
;
538 mPosition
[LoopVar6
] = (NODE
) (LoopVar11
| WNDSIZ
);
539 LoopVar6
= mParent
[LoopVar6
];
540 LoopVar9
= mPosition
[LoopVar6
];
543 if (LoopVar6
< WNDSIZ
) {
544 if (LoopVar9
>= mPos
) {
548 if (LoopVar9
> LoopVar11
) {
549 LoopVar11
= LoopVar9
;
552 mPosition
[LoopVar6
] = (NODE
) (LoopVar11
| WNDSIZ
| PERC_FLAG
);
555 LoopVar11
= Child (LoopVar4
, mText
[LoopVar10
+ mLevel
[LoopVar4
]]);
556 LoopVar10
= mPrev
[LoopVar11
];
557 LoopVar9
= mNext
[LoopVar11
];
558 mNext
[LoopVar10
] = LoopVar9
;
559 mPrev
[LoopVar9
] = LoopVar10
;
560 LoopVar10
= mPrev
[LoopVar4
];
561 mNext
[LoopVar10
] = LoopVar11
;
562 mPrev
[LoopVar11
] = LoopVar10
;
563 LoopVar10
= mNext
[LoopVar4
];
564 mPrev
[LoopVar10
] = LoopVar11
;
565 mNext
[LoopVar11
] = LoopVar10
;
566 mParent
[LoopVar11
] = mParent
[LoopVar4
];
567 mParent
[LoopVar4
] = NIL
;
568 mNext
[LoopVar4
] = mAvail
;
575 @param[out] LoopVar7 The buffer to hold the data.
576 @param[in] LoopVar8 The number of bytes to read.
578 @return The number of bytes actually read.
589 for (LoopVar1
= 0; mSrc
< mSrcUpperLimit
&& LoopVar1
< LoopVar8
; LoopVar1
++) {
590 *LoopVar7
++ = *mSrc
++;
595 LoopVar7
-= LoopVar8
;
596 mOrigSize
+= LoopVar8
;
598 while (LoopVar1
>= 0) {
599 UPDATE_CRC (*LoopVar7
++);
607 Advance the current position (read in new data if needed).
608 Delete outdated string info. Find a match string for current position.
622 if (mPos
== WNDSIZ
* 2) {
623 Temp
= AllocateZeroPool (WNDSIZ
+ MAXMATCH
);
624 CopyMem (Temp
, &mText
[WNDSIZ
], WNDSIZ
+ MAXMATCH
);
625 CopyMem (&mText
[0], Temp
, WNDSIZ
+ MAXMATCH
);
627 LoopVar8
= FreadCrc (&mText
[WNDSIZ
+ MAXMATCH
], WNDSIZ
);
628 mRemainder
+= LoopVar8
;
637 Send entry LoopVar1 down the queue.
639 @param[in] LoopVar1 The index of the item to move.
652 // priority queue: send i-th entry down heap
656 while (LoopVar1
<= mHeapSize
) {
657 if (LoopVar1
< mHeapSize
&& mFreq
[mHeap
[LoopVar1
]] > mFreq
[mHeap
[LoopVar1
+ 1]]) {
661 if (mFreq
[LoopVar2
] <= mFreq
[mHeap
[LoopVar1
]]) {
665 mHeap
[i
] = mHeap
[LoopVar1
];
670 mHeap
[i
] = (INT16
) LoopVar2
;
674 Count the number of each code length for a Huffman tree.
676 @param[in] LoopVar1 The top node.
684 if (LoopVar1
< mTempInt32
) {
685 mLenCnt
[(mHuffmanDepth
< 16) ? mHuffmanDepth
: 16]++;
688 CountLen (mLeft
[LoopVar1
]);
689 CountLen (mRight
[LoopVar1
]);
695 Create code length array for a Huffman tree.
697 @param[in] Root The root of the tree.
710 for (LoopVar1
= 0; LoopVar1
<= 16; LoopVar1
++) {
711 mLenCnt
[LoopVar1
] = 0;
717 // Adjust the length count array so that
718 // no code will be generated longer than its designated length
721 for (LoopVar1
= 16; LoopVar1
> 0; LoopVar1
--) {
722 Cum
+= mLenCnt
[LoopVar1
] << (16 - LoopVar1
);
725 while (Cum
!= (1U << 16)) {
727 for (LoopVar1
= 15; LoopVar1
> 0; LoopVar1
--) {
728 if (mLenCnt
[LoopVar1
] != 0) {
730 mLenCnt
[LoopVar1
+ 1] += 2;
738 for (LoopVar1
= 16; LoopVar1
> 0; LoopVar1
--) {
739 LoopVar2
= mLenCnt
[LoopVar1
];
741 while (LoopVar2
>= 0) {
742 mLen
[*mSortPtr
++] = (UINT8
) LoopVar1
;
749 Assign code to each symbol based on the code length array.
751 @param[in] LoopVar8 The number of symbols.
752 @param[in] Len The code length array.
753 @param[out] Code The stores codes for each symbol.
767 for (LoopVar1
= 1; LoopVar1
<= 16; LoopVar1
++) {
768 Start
[LoopVar1
+ 1] = (UINT16
) ((Start
[LoopVar1
] + mLenCnt
[LoopVar1
]) << 1);
771 for (LoopVar1
= 0; LoopVar1
< LoopVar8
; LoopVar1
++) {
772 Code
[LoopVar1
] = Start
[Len
[LoopVar1
]]++;
777 Generates Huffman codes given a frequency distribution of symbols.
779 @param[in] NParm The number of symbols.
780 @param[in] FreqParm The frequency of each symbol.
781 @param[out] LenParm The code length for each symbol.
782 @param[out] CodeParm The code for each symbol.
784 @return The root of the Huffman tree.
790 IN UINT16 FreqParm
[ ],
791 OUT UINT8 LenParm
[ ],
792 OUT UINT16 CodeParm
[ ]
804 // make tree, calculate len[], return root
812 for (LoopVar1
= 0; LoopVar1
< mTempInt32
; LoopVar1
++) {
814 if ((mFreq
[LoopVar1
]) != 0) {
816 mHeap
[mHeapSize
] = (INT16
) LoopVar1
;
821 CodeParm
[mHeap
[1]] = 0;
825 for (LoopVar1
= mHeapSize
/ 2; LoopVar1
>= 1; LoopVar1
--) {
827 // make priority queue
835 if (LoopVar1
< mTempInt32
) {
836 *mSortPtr
++ = (UINT16
) LoopVar1
;
839 mHeap
[1] = mHeap
[mHeapSize
--];
842 if (LoopVar2
< mTempInt32
) {
843 *mSortPtr
++ = (UINT16
) LoopVar2
;
847 mFreq
[LoopVar3
] = (UINT16
) (mFreq
[LoopVar1
] + mFreq
[LoopVar2
]);
848 mHeap
[1] = (INT16
) LoopVar3
;
850 mLeft
[LoopVar3
] = (UINT16
) LoopVar1
;
851 mRight
[LoopVar3
] = (UINT16
) LoopVar2
;
852 } while (mHeapSize
> 1);
856 MakeCode (NParm
, LenParm
, CodeParm
);
865 Outputs rightmost LoopVar8 bits of x
867 @param[in] LoopVar8 The rightmost LoopVar8 bits of the data is used.
868 @param[in] x The data.
879 if (LoopVar8
< mBitCount
) {
880 mSubBitBuf
|= x
<< (mBitCount
-= LoopVar8
);
883 Temp
= (UINT8
)(mSubBitBuf
| (x
>> (LoopVar8
-= mBitCount
)));
884 if (mDst
< mDstUpperLimit
) {
889 if (LoopVar8
< UINT8_BIT
) {
890 mSubBitBuf
= x
<< (mBitCount
= UINT8_BIT
- LoopVar8
);
893 Temp
= (UINT8
)(x
>> (LoopVar8
- UINT8_BIT
));
894 if (mDst
< mDstUpperLimit
) {
899 mSubBitBuf
= x
<< (mBitCount
= 2 * UINT8_BIT
- LoopVar8
);
905 Encode a signed 32 bit number.
907 @param[in] LoopVar5 The number to encode.
915 PutBits (mCLen
[LoopVar5
], mCCode
[LoopVar5
]);
919 Encode a unsigned 32 bit number.
921 @param[in] LoopVar7 The number to encode.
935 while (LoopVar6
!= 0) {
940 PutBits (mPTLen
[LoopVar5
], mPTCode
[LoopVar5
]);
942 PutBits(LoopVar5
- 1, LoopVar7
& (0xFFFFU
>> (17 - LoopVar5
)));
947 Count the frequencies for the Extra Set.
964 for (LoopVar1
= 0; LoopVar1
< NT
; LoopVar1
++) {
965 mTFreq
[LoopVar1
] = 0;
969 while (LoopVar8
> 0 && mCLen
[LoopVar8
- 1] == 0) {
974 while (LoopVar1
< LoopVar8
) {
975 LoopVar3
= mCLen
[LoopVar1
++];
978 while (LoopVar1
< LoopVar8
&& mCLen
[LoopVar1
] == 0) {
984 mTFreq
[0] = (UINT16
) (mTFreq
[0] + Count
);
985 } else if (Count
<= 18) {
987 } else if (Count
== 19) {
994 ASSERT((LoopVar3
+2)<(2 * NT
- 1));
995 mTFreq
[LoopVar3
+ 2]++;
1001 Outputs the code length array for the Extra Set or the Position Set.
1003 @param[in] LoopVar8 The number of symbols.
1004 @param[in] nbit The number of bits needed to represent 'LoopVar8'.
1005 @param[in] Special The special symbol that needs to be take care of.
1020 while (LoopVar8
> 0 && mPTLen
[LoopVar8
- 1] == 0) {
1024 PutBits (nbit
, LoopVar8
);
1026 while (LoopVar1
< LoopVar8
) {
1027 LoopVar3
= mPTLen
[LoopVar1
++];
1028 if (LoopVar3
<= 6) {
1029 PutBits (3, LoopVar3
);
1031 PutBits (LoopVar3
- 3, (1U << (LoopVar3
- 3)) - 2);
1034 if (LoopVar1
== Special
) {
1035 while (LoopVar1
< 6 && mPTLen
[LoopVar1
] == 0) {
1039 PutBits (2, (LoopVar1
- 3) & 3);
1045 Outputs the code length array for Char&Length Set.
1062 while (LoopVar8
> 0 && mCLen
[LoopVar8
- 1] == 0) {
1066 PutBits (CBIT
, LoopVar8
);
1068 while (LoopVar1
< LoopVar8
) {
1069 LoopVar3
= mCLen
[LoopVar1
++];
1070 if (LoopVar3
== 0) {
1072 while (LoopVar1
< LoopVar8
&& mCLen
[LoopVar1
] == 0) {
1078 for (LoopVar3
= 0; LoopVar3
< Count
; LoopVar3
++) {
1079 PutBits (mPTLen
[0], mPTCode
[0]);
1081 } else if (Count
<= 18) {
1082 PutBits (mPTLen
[1], mPTCode
[1]);
1083 PutBits (4, Count
- 3);
1084 } else if (Count
== 19) {
1085 PutBits (mPTLen
[0], mPTCode
[0]);
1086 PutBits (mPTLen
[1], mPTCode
[1]);
1089 PutBits (mPTLen
[2], mPTCode
[2]);
1090 PutBits (CBIT
, Count
- 20);
1093 ASSERT((LoopVar3
+2)<NPT
);
1094 PutBits (mPTLen
[LoopVar3
+ 2], mPTCode
[LoopVar3
+ 2]);
1100 Huffman code the block and output it.
1122 Root
= MakeTree (NC
, mCFreq
, mCLen
, mCCode
);
1123 Size
= mCFreq
[Root
];
1127 Root
= MakeTree (NT
, mTFreq
, mPTLen
, mPTCode
);
1129 WritePTLen (NT
, TBIT
, 3);
1132 PutBits (TBIT
, Root
);
1140 PutBits (CBIT
, Root
);
1143 Root
= MakeTree (NP
, mPFreq
, mPTLen
, mPTCode
);
1145 WritePTLen (NP
, PBIT
, -1);
1148 PutBits (PBIT
, Root
);
1152 for (LoopVar1
= 0; LoopVar1
< Size
; LoopVar1
++) {
1153 if (LoopVar1
% UINT8_BIT
== 0) {
1154 Flags
= mBuf
[Pos
++];
1158 if ((Flags
& (1U << (UINT8_BIT
- 1))) != 0){
1159 EncodeC(mBuf
[Pos
++] + (1U << UINT8_BIT
));
1160 LoopVar3
= mBuf
[Pos
++] << UINT8_BIT
;
1161 LoopVar3
+= mBuf
[Pos
++];
1165 EncodeC (mBuf
[Pos
++]);
1169 SetMem (mCFreq
, NC
* sizeof (UINT16
), 0);
1170 SetMem (mPFreq
, NP
* sizeof (UINT16
), 0);
1174 Start the huffman encoding.
1183 SetMem (mCFreq
, NC
* sizeof (UINT16
), 0);
1184 SetMem (mPFreq
, NP
* sizeof (UINT16
), 0);
1186 mOutputPos
= mOutputMask
= 0;
1188 mBitCount
= UINT8_BIT
;
1193 Outputs an Original Character or a Pointer.
1195 @param[in] LoopVar5 The original character or the 'String Length' element of
1197 @param[in] LoopVar7 The 'Position' field of a Pointer.
1208 if ((mOutputMask
>>= 1) == 0) {
1209 mOutputMask
= 1U << (UINT8_BIT
- 1);
1210 if (mOutputPos
>= mBufSiz
- 3 * UINT8_BIT
) {
1215 CPos
= mOutputPos
++;
1218 mBuf
[mOutputPos
++] = (UINT8
) LoopVar5
;
1220 if (LoopVar5
>= (1U << UINT8_BIT
)) {
1221 mBuf
[CPos
] = (UINT8
)(mBuf
[CPos
]|mOutputMask
);
1222 mBuf
[mOutputPos
++] = (UINT8
)(LoopVar7
>> UINT8_BIT
);
1223 mBuf
[mOutputPos
++] = (UINT8
) LoopVar7
;
1225 while (LoopVar7
!=0) {
1234 End the huffman encoding.
1246 // Flush remaining bits
1248 PutBits (UINT8_BIT
- 1, 0);
1252 The main controlling routine for compression process.
1254 @retval EFI_SUCCESS The compression is successful.
1255 @retval EFI_OUT_0F_RESOURCES Not enough memory for compression process.
1267 Status
= AllocateMemory ();
1268 if (EFI_ERROR (Status
)) {
1277 mRemainder
= FreadCrc (&mText
[WNDSIZ
], WNDSIZ
+ MAXMATCH
);
1282 if (mMatchLen
> mRemainder
) {
1283 mMatchLen
= mRemainder
;
1286 while (mRemainder
> 0) {
1287 LastMatchLen
= mMatchLen
;
1288 LastMatchPos
= mMatchPos
;
1290 if (mMatchLen
> mRemainder
) {
1291 mMatchLen
= mRemainder
;
1294 if (mMatchLen
> LastMatchLen
|| LastMatchLen
< THRESHOLD
) {
1296 // Not enough benefits are gained by outputting a pointer,
1297 // so just output the original character
1299 CompressOutput(mText
[mPos
- 1], 0);
1302 // Outputting a pointer is beneficial enough, do it.
1305 CompressOutput(LastMatchLen
+ (UINT8_MAX
+ 1 - THRESHOLD
),
1306 (mPos
- LastMatchPos
- 2) & (WNDSIZ
- 1));
1308 while (LastMatchLen
> 0) {
1313 if (mMatchLen
> mRemainder
) {
1314 mMatchLen
= mRemainder
;
1325 The compression routine.
1327 @param[in] SrcBuffer The buffer containing the source data.
1328 @param[in] SrcSize The number of bytes in SrcBuffer.
1329 @param[in] DstBuffer The buffer to put the compressed image in.
1330 @param[in,out] DstSize On input the size (in bytes) of DstBuffer, on
1331 return the number of bytes placed in DstBuffer.
1333 @retval EFI_SUCCESS The compression was sucessful.
1334 @retval EFI_BUFFER_TOO_SMALL The buffer was too small. DstSize is required.
1342 IN OUT UINT64
*DstSize
1361 mSrcUpperLimit
= mSrc
+ SrcSize
;
1363 mDstUpperLimit
= mDst
+*DstSize
;
1370 mOrigSize
= mCompSize
= 0;
1377 if (EFI_ERROR (Status
)) {
1378 return EFI_OUT_OF_RESOURCES
;
1381 // Null terminate the compressed data
1383 if (mDst
< mDstUpperLimit
) {
1387 // Fill in compressed size and original size
1390 PutDword (mCompSize
+ 1);
1391 PutDword (mOrigSize
);
1396 if (mCompSize
+ 1 + 8 > *DstSize
) {
1397 *DstSize
= mCompSize
+ 1 + 8;
1398 return EFI_BUFFER_TOO_SMALL
;
1400 *DstSize
= mCompSize
+ 1 + 8;