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 mCTable
[4096];
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
252 SetMem (mLevel
+ WNDSIZ
, (UINT8_MAX
+ 1) * sizeof (UINT8
), 1);
253 SetMem (mPosition
+ WNDSIZ
, (UINT8_MAX
+ 1) * sizeof (NODE
), 0);
255 SetMem (mParent
+ WNDSIZ
, WNDSIZ
* sizeof (NODE
), 0);
258 for (LoopVar1
= 1; LoopVar1
< WNDSIZ
- 1; LoopVar1
++) {
259 mNext
[LoopVar1
] = (NODE
) (LoopVar1
+ 1);
262 mNext
[WNDSIZ
- 1] = NIL
;
263 SetMem (mNext
+ WNDSIZ
* 2, (MAX_HASH_VAL
- WNDSIZ
* 2 + 1) * sizeof (NODE
), 0);
267 Find child node given the parent node and the edge character
269 @param[in] LoopVar6 The parent node.
270 @param[in] LoopVar5 The edge character.
272 @return The child node.
273 @retval NIL(Zero) No child could be found.
285 LoopVar4
= mNext
[HASH (LoopVar6
, LoopVar5
)];
286 mParent
[NIL
] = LoopVar6
; /* sentinel */
287 while (mParent
[LoopVar4
] != LoopVar6
) {
288 LoopVar4
= mNext
[LoopVar4
];
295 Create a new child for a given parent node.
297 @param[in] LoopVar6 The parent node.
298 @param[in] LoopVar5 The edge character.
299 @param[in] LoopVar4 The child node.
313 LoopVar12
= (NODE
) HASH (LoopVar6
, LoopVar5
);
314 LoopVar10
= mNext
[LoopVar12
];
315 mNext
[LoopVar12
] = LoopVar4
;
316 mNext
[LoopVar4
] = LoopVar10
;
317 mPrev
[LoopVar10
] = LoopVar4
;
318 mPrev
[LoopVar4
] = LoopVar12
;
319 mParent
[LoopVar4
] = LoopVar6
;
320 mChildCount
[LoopVar6
]++;
326 @param[in] Old The node to split.
340 mChildCount
[New
] = 0;
341 LoopVar10
= mPrev
[Old
];
342 mPrev
[New
] = LoopVar10
;
343 mNext
[LoopVar10
] = New
;
344 LoopVar10
= mNext
[Old
];
345 mNext
[New
] = LoopVar10
;
346 mPrev
[LoopVar10
] = New
;
347 mParent
[New
] = mParent
[Old
];
348 mLevel
[New
] = (UINT8
) mMatchLen
;
349 mPosition
[New
] = mPos
;
350 MakeChild (New
, mText
[mMatchPos
+ mMatchLen
], Old
);
351 MakeChild (New
, mText
[mPos
+ mMatchLen
], mPos
);
355 Insert string info for current position into the String Info Log.
375 if (mMatchLen
>= 4) {
377 // We have just got a long match, the target tree
378 // can be located by MatchPos + 1. Travese the tree
379 // from bottom up to get to a proper starting point.
380 // The usage of PERC_FLAG ensures proper node deletion
381 // in DeleteNode() later.
384 LoopVar4
= (NODE
) ((mMatchPos
+ 1) | WNDSIZ
);
385 LoopVar6
= mParent
[LoopVar4
];
386 while (LoopVar6
== NIL
) {
387 LoopVar4
= mNext
[LoopVar4
];
388 LoopVar6
= mParent
[LoopVar4
];
391 while (mLevel
[LoopVar6
] >= mMatchLen
) {
393 LoopVar6
= mParent
[LoopVar6
];
396 LoopVar10
= LoopVar6
;
397 while (mPosition
[LoopVar10
] < 0) {
398 mPosition
[LoopVar10
] = mPos
;
399 LoopVar10
= mParent
[LoopVar10
];
402 if (LoopVar10
< WNDSIZ
) {
403 mPosition
[LoopVar10
] = (NODE
) (mPos
| PERC_FLAG
);
407 // Locate the target tree
409 LoopVar6
= (NODE
) (mText
[mPos
] + WNDSIZ
);
410 LoopVar5
= mText
[mPos
+ 1];
411 LoopVar4
= Child (LoopVar6
, LoopVar5
);
412 if (LoopVar4
== NIL
) {
413 MakeChild (LoopVar6
, LoopVar5
, mPos
);
421 // Traverse down the tree to find a match.
422 // Update Position value along the route.
423 // Node split or creation is involved.
426 if (LoopVar4
>= WNDSIZ
) {
428 mMatchPos
= LoopVar4
;
430 LoopVar2
= mLevel
[LoopVar4
];
431 mMatchPos
= (NODE
) (mPosition
[LoopVar4
] & ~PERC_FLAG
);
434 if (mMatchPos
>= mPos
) {
438 TempString3
= &mText
[mPos
+ mMatchLen
];
439 TempString2
= &mText
[mMatchPos
+ mMatchLen
];
440 while (mMatchLen
< LoopVar2
) {
441 if (*TempString3
!= *TempString2
) {
451 if (mMatchLen
>= MAXMATCH
) {
455 mPosition
[LoopVar4
] = mPos
;
457 LoopVar4
= Child (LoopVar6
, *TempString3
);
458 if (LoopVar4
== NIL
) {
459 MakeChild (LoopVar6
, *TempString3
, mPos
);
466 LoopVar10
= mPrev
[LoopVar4
];
467 mPrev
[mPos
] = LoopVar10
;
468 mNext
[LoopVar10
] = mPos
;
469 LoopVar10
= mNext
[LoopVar4
];
470 mNext
[mPos
] = LoopVar10
;
471 mPrev
[LoopVar10
] = mPos
;
472 mParent
[mPos
] = LoopVar6
;
473 mParent
[LoopVar4
] = NIL
;
476 // Special usage of 'next'
478 mNext
[LoopVar4
] = mPos
;
483 Delete outdated string info. (The Usage of PERC_FLAG
484 ensures a clean deletion).
503 if (mParent
[mPos
] == NIL
) {
507 LoopVar4
= mPrev
[mPos
];
508 LoopVar11
= mNext
[mPos
];
509 mNext
[LoopVar4
] = LoopVar11
;
510 mPrev
[LoopVar11
] = LoopVar4
;
511 LoopVar4
= mParent
[mPos
];
513 if (LoopVar4
>= WNDSIZ
) {
517 mChildCount
[LoopVar4
]--;
518 if (mChildCount
[LoopVar4
] > 1) {
522 LoopVar10
= (NODE
) (mPosition
[LoopVar4
] & ~PERC_FLAG
);
523 if (LoopVar10
>= mPos
) {
527 LoopVar11
= LoopVar10
;
528 LoopVar6
= mParent
[LoopVar4
];
529 LoopVar9
= mPosition
[LoopVar6
];
530 while ((LoopVar9
& PERC_FLAG
) != 0){
531 LoopVar9
&= ~PERC_FLAG
;
532 if (LoopVar9
>= mPos
) {
536 if (LoopVar9
> LoopVar11
) {
537 LoopVar11
= LoopVar9
;
540 mPosition
[LoopVar6
] = (NODE
) (LoopVar11
| WNDSIZ
);
541 LoopVar6
= mParent
[LoopVar6
];
542 LoopVar9
= mPosition
[LoopVar6
];
545 if (LoopVar6
< WNDSIZ
) {
546 if (LoopVar9
>= mPos
) {
550 if (LoopVar9
> LoopVar11
) {
551 LoopVar11
= LoopVar9
;
554 mPosition
[LoopVar6
] = (NODE
) (LoopVar11
| WNDSIZ
| PERC_FLAG
);
557 LoopVar11
= Child (LoopVar4
, mText
[LoopVar10
+ mLevel
[LoopVar4
]]);
558 LoopVar10
= mPrev
[LoopVar11
];
559 LoopVar9
= mNext
[LoopVar11
];
560 mNext
[LoopVar10
] = LoopVar9
;
561 mPrev
[LoopVar9
] = LoopVar10
;
562 LoopVar10
= mPrev
[LoopVar4
];
563 mNext
[LoopVar10
] = LoopVar11
;
564 mPrev
[LoopVar11
] = LoopVar10
;
565 LoopVar10
= mNext
[LoopVar4
];
566 mPrev
[LoopVar10
] = LoopVar11
;
567 mNext
[LoopVar11
] = LoopVar10
;
568 mParent
[LoopVar11
] = mParent
[LoopVar4
];
569 mParent
[LoopVar4
] = NIL
;
570 mNext
[LoopVar4
] = mAvail
;
577 @param[out] LoopVar7 The buffer to hold the data.
578 @param[in] LoopVar8 The number of bytes to read.
580 @return The number of bytes actually read.
591 for (LoopVar1
= 0; mSrc
< mSrcUpperLimit
&& LoopVar1
< LoopVar8
; LoopVar1
++) {
592 *LoopVar7
++ = *mSrc
++;
597 LoopVar7
-= LoopVar8
;
598 mOrigSize
+= LoopVar8
;
600 while (LoopVar1
>= 0) {
601 UPDATE_CRC (*LoopVar7
++);
609 Advance the current position (read in new data if needed).
610 Delete outdated string info. Find a match string for current position.
624 if (mPos
== WNDSIZ
* 2) {
625 Temp
= AllocateZeroPool (WNDSIZ
+ MAXMATCH
);
626 CopyMem (Temp
, &mText
[WNDSIZ
], WNDSIZ
+ MAXMATCH
);
627 CopyMem (&mText
[0], Temp
, WNDSIZ
+ MAXMATCH
);
629 LoopVar8
= FreadCrc (&mText
[WNDSIZ
+ MAXMATCH
], WNDSIZ
);
630 mRemainder
+= LoopVar8
;
639 Send entry LoopVar1 down the queue.
641 @param[in] LoopVar1 The index of the item to move.
654 // priority queue: send i-th entry down heap
658 while (LoopVar1
<= mHeapSize
) {
659 if (LoopVar1
< mHeapSize
&& mFreq
[mHeap
[LoopVar1
]] > mFreq
[mHeap
[LoopVar1
+ 1]]) {
663 if (mFreq
[LoopVar2
] <= mFreq
[mHeap
[LoopVar1
]]) {
667 mHeap
[i
] = mHeap
[LoopVar1
];
672 mHeap
[i
] = (INT16
) LoopVar2
;
676 Count the number of each code length for a Huffman tree.
678 @param[in] LoopVar1 The top node.
686 if (LoopVar1
< mTempInt32
) {
687 mLenCnt
[(mHuffmanDepth
< 16) ? mHuffmanDepth
: 16]++;
690 CountLen (mLeft
[LoopVar1
]);
691 CountLen (mRight
[LoopVar1
]);
697 Create code length array for a Huffman tree.
699 @param[in] Root The root of the tree.
712 for (LoopVar1
= 0; LoopVar1
<= 16; LoopVar1
++) {
713 mLenCnt
[LoopVar1
] = 0;
719 // Adjust the length count array so that
720 // no code will be generated longer than its designated length
723 for (LoopVar1
= 16; LoopVar1
> 0; LoopVar1
--) {
724 Cum
+= mLenCnt
[LoopVar1
] << (16 - LoopVar1
);
727 while (Cum
!= (1U << 16)) {
729 for (LoopVar1
= 15; LoopVar1
> 0; LoopVar1
--) {
730 if (mLenCnt
[LoopVar1
] != 0) {
732 mLenCnt
[LoopVar1
+ 1] += 2;
740 for (LoopVar1
= 16; LoopVar1
> 0; LoopVar1
--) {
741 LoopVar2
= mLenCnt
[LoopVar1
];
743 while (LoopVar2
>= 0) {
744 mLen
[*mSortPtr
++] = (UINT8
) LoopVar1
;
751 Assign code to each symbol based on the code length array.
753 @param[in] LoopVar8 The number of symbols.
754 @param[in] Len The code length array.
755 @param[out] Code The stores codes for each symbol.
769 for (LoopVar1
= 1; LoopVar1
<= 16; LoopVar1
++) {
770 Start
[LoopVar1
+ 1] = (UINT16
) ((Start
[LoopVar1
] + mLenCnt
[LoopVar1
]) << 1);
773 for (LoopVar1
= 0; LoopVar1
< LoopVar8
; LoopVar1
++) {
774 Code
[LoopVar1
] = Start
[Len
[LoopVar1
]]++;
779 Generates Huffman codes given a frequency distribution of symbols.
781 @param[in] NParm The number of symbols.
782 @param[in] FreqParm The frequency of each symbol.
783 @param[out] LenParm The code length for each symbol.
784 @param[out] CodeParm The code for each symbol.
786 @return The root of the Huffman tree.
792 IN UINT16 FreqParm
[ ],
793 OUT UINT8 LenParm
[ ],
794 OUT UINT16 CodeParm
[ ]
806 // make tree, calculate len[], return root
814 for (LoopVar1
= 0; LoopVar1
< mTempInt32
; LoopVar1
++) {
816 if ((mFreq
[LoopVar1
]) != 0) {
818 mHeap
[mHeapSize
] = (INT16
) LoopVar1
;
823 CodeParm
[mHeap
[1]] = 0;
827 for (LoopVar1
= mHeapSize
/ 2; LoopVar1
>= 1; LoopVar1
--) {
829 // make priority queue
837 if (LoopVar1
< mTempInt32
) {
838 *mSortPtr
++ = (UINT16
) LoopVar1
;
841 mHeap
[1] = mHeap
[mHeapSize
--];
844 if (LoopVar2
< mTempInt32
) {
845 *mSortPtr
++ = (UINT16
) LoopVar2
;
849 mFreq
[LoopVar3
] = (UINT16
) (mFreq
[LoopVar1
] + mFreq
[LoopVar2
]);
850 mHeap
[1] = (INT16
) LoopVar3
;
852 mLeft
[LoopVar3
] = (UINT16
) LoopVar1
;
853 mRight
[LoopVar3
] = (UINT16
) LoopVar2
;
854 } while (mHeapSize
> 1);
858 MakeCode (NParm
, LenParm
, CodeParm
);
867 Outputs rightmost LoopVar8 bits of x
869 @param[in] LoopVar8 The rightmost LoopVar8 bits of the data is used.
870 @param[in] x The data.
881 if (LoopVar8
< mBitCount
) {
882 mSubBitBuf
|= x
<< (mBitCount
-= LoopVar8
);
885 Temp
= (UINT8
)(mSubBitBuf
| (x
>> (LoopVar8
-= mBitCount
)));
886 if (mDst
< mDstUpperLimit
) {
891 if (LoopVar8
< UINT8_BIT
) {
892 mSubBitBuf
= x
<< (mBitCount
= UINT8_BIT
- LoopVar8
);
895 Temp
= (UINT8
)(x
>> (LoopVar8
- UINT8_BIT
));
896 if (mDst
< mDstUpperLimit
) {
901 mSubBitBuf
= x
<< (mBitCount
= 2 * UINT8_BIT
- LoopVar8
);
907 Encode a signed 32 bit number.
909 @param[in] LoopVar5 The number to encode.
917 PutBits (mCLen
[LoopVar5
], mCCode
[LoopVar5
]);
921 Encode a unsigned 32 bit number.
923 @param[in] LoopVar7 The number to encode.
937 while (LoopVar6
!= 0) {
942 PutBits (mPTLen
[LoopVar5
], mPTCode
[LoopVar5
]);
944 PutBits(LoopVar5
- 1, LoopVar7
& (0xFFFFU
>> (17 - LoopVar5
)));
949 Count the frequencies for the Extra Set.
966 for (LoopVar1
= 0; LoopVar1
< NT
; LoopVar1
++) {
967 mTFreq
[LoopVar1
] = 0;
971 while (LoopVar8
> 0 && mCLen
[LoopVar8
- 1] == 0) {
976 while (LoopVar1
< LoopVar8
) {
977 LoopVar3
= mCLen
[LoopVar1
++];
980 while (LoopVar1
< LoopVar8
&& mCLen
[LoopVar1
] == 0) {
986 mTFreq
[0] = (UINT16
) (mTFreq
[0] + Count
);
987 } else if (Count
<= 18) {
989 } else if (Count
== 19) {
996 ASSERT((LoopVar3
+2)<(2 * NT
- 1));
997 mTFreq
[LoopVar3
+ 2]++;
1003 Outputs the code length array for the Extra Set or the Position Set.
1005 @param[in] LoopVar8 The number of symbols.
1006 @param[in] nbit The number of bits needed to represent 'LoopVar8'.
1007 @param[in] Special The special symbol that needs to be take care of.
1022 while (LoopVar8
> 0 && mPTLen
[LoopVar8
- 1] == 0) {
1026 PutBits (nbit
, LoopVar8
);
1028 while (LoopVar1
< LoopVar8
) {
1029 LoopVar3
= mPTLen
[LoopVar1
++];
1030 if (LoopVar3
<= 6) {
1031 PutBits (3, LoopVar3
);
1033 PutBits (LoopVar3
- 3, (1U << (LoopVar3
- 3)) - 2);
1036 if (LoopVar1
== Special
) {
1037 while (LoopVar1
< 6 && mPTLen
[LoopVar1
] == 0) {
1041 PutBits (2, (LoopVar1
- 3) & 3);
1047 Outputs the code length array for Char&Length Set
1065 while (LoopVar8
> 0 && mCLen
[LoopVar8
- 1] == 0) {
1069 PutBits (CBIT
, LoopVar8
);
1071 while (LoopVar1
< LoopVar8
) {
1072 LoopVar3
= mCLen
[LoopVar1
++];
1073 if (LoopVar3
== 0) {
1075 while (LoopVar1
< LoopVar8
&& mCLen
[LoopVar1
] == 0) {
1081 for (LoopVar3
= 0; LoopVar3
< Count
; LoopVar3
++) {
1082 PutBits (mPTLen
[0], mPTCode
[0]);
1084 } else if (Count
<= 18) {
1085 PutBits (mPTLen
[1], mPTCode
[1]);
1086 PutBits (4, Count
- 3);
1087 } else if (Count
== 19) {
1088 PutBits (mPTLen
[0], mPTCode
[0]);
1089 PutBits (mPTLen
[1], mPTCode
[1]);
1092 PutBits (mPTLen
[2], mPTCode
[2]);
1093 PutBits (CBIT
, Count
- 20);
1096 ASSERT((LoopVar3
+2)<NPT
);
1097 PutBits (mPTLen
[LoopVar3
+ 2], mPTCode
[LoopVar3
+ 2]);
1103 Huffman code the block and output it.
1125 Root
= MakeTree (NC
, mCFreq
, mCLen
, mCCode
);
1126 Size
= mCFreq
[Root
];
1130 Root
= MakeTree (NT
, mTFreq
, mPTLen
, mPTCode
);
1132 WritePTLen (NT
, TBIT
, 3);
1135 PutBits (TBIT
, Root
);
1143 PutBits (CBIT
, Root
);
1146 Root
= MakeTree (NP
, mPFreq
, mPTLen
, mPTCode
);
1148 WritePTLen (NP
, PBIT
, -1);
1151 PutBits (PBIT
, Root
);
1155 for (LoopVar1
= 0; LoopVar1
< Size
; LoopVar1
++) {
1156 if (LoopVar1
% UINT8_BIT
== 0) {
1157 Flags
= mBuf
[Pos
++];
1161 if ((Flags
& (1U << (UINT8_BIT
- 1))) != 0){
1162 EncodeC(mBuf
[Pos
++] + (1U << UINT8_BIT
));
1163 LoopVar3
= mBuf
[Pos
++] << UINT8_BIT
;
1164 LoopVar3
+= mBuf
[Pos
++];
1168 EncodeC (mBuf
[Pos
++]);
1172 SetMem (mCFreq
, NC
* sizeof (UINT16
), 0);
1173 SetMem (mPFreq
, NP
* sizeof (UINT16
), 0);
1177 Start the huffman encoding.
1186 SetMem (mCFreq
, NC
* sizeof (UINT16
), 0);
1187 SetMem (mPFreq
, NP
* sizeof (UINT16
), 0);
1189 mOutputPos
= mOutputMask
= 0;
1191 mBitCount
= UINT8_BIT
;
1196 Outputs an Original Character or a Pointer.
1198 @param[in] LoopVar5 The original character or the 'String Length' element of
1200 @param[in] LoopVar7 The 'Position' field of a Pointer.
1211 if ((mOutputMask
>>= 1) == 0) {
1212 mOutputMask
= 1U << (UINT8_BIT
- 1);
1213 if (mOutputPos
>= mBufSiz
- 3 * UINT8_BIT
) {
1218 CPos
= mOutputPos
++;
1221 mBuf
[mOutputPos
++] = (UINT8
) LoopVar5
;
1223 if (LoopVar5
>= (1U << UINT8_BIT
)) {
1224 mBuf
[CPos
] = (UINT8
)(mBuf
[CPos
]|mOutputMask
);
1225 mBuf
[mOutputPos
++] = (UINT8
)(LoopVar7
>> UINT8_BIT
);
1226 mBuf
[mOutputPos
++] = (UINT8
) LoopVar7
;
1228 while (LoopVar7
!=0) {
1237 End the huffman encoding.
1249 // Flush remaining bits
1251 PutBits (UINT8_BIT
- 1, 0);
1255 The main controlling routine for compression process.
1257 @retval EFI_SUCCESS The compression is successful.
1258 @retval EFI_OUT_0F_RESOURCES Not enough memory for compression process.
1270 Status
= AllocateMemory ();
1271 if (EFI_ERROR (Status
)) {
1280 mRemainder
= FreadCrc (&mText
[WNDSIZ
], WNDSIZ
+ MAXMATCH
);
1285 if (mMatchLen
> mRemainder
) {
1286 mMatchLen
= mRemainder
;
1289 while (mRemainder
> 0) {
1290 LastMatchLen
= mMatchLen
;
1291 LastMatchPos
= mMatchPos
;
1293 if (mMatchLen
> mRemainder
) {
1294 mMatchLen
= mRemainder
;
1297 if (mMatchLen
> LastMatchLen
|| LastMatchLen
< THRESHOLD
) {
1299 // Not enough benefits are gained by outputting a pointer,
1300 // so just output the original character
1302 CompressOutput(mText
[mPos
- 1], 0);
1305 // Outputting a pointer is beneficial enough, do it.
1308 CompressOutput(LastMatchLen
+ (UINT8_MAX
+ 1 - THRESHOLD
),
1309 (mPos
- LastMatchPos
- 2) & (WNDSIZ
- 1));
1311 while (LastMatchLen
> 0) {
1316 if (mMatchLen
> mRemainder
) {
1317 mMatchLen
= mRemainder
;
1328 The compression routine.
1330 @param[in] SrcBuffer The buffer containing the source data.
1331 @param[in] SrcSize The number of bytes in SrcBuffer.
1332 @param[in] DstBuffer The buffer to put the compressed image in.
1333 @param[in,out] DstSize On input the size (in bytes) of DstBuffer, on
1334 return the number of bytes placed in DstBuffer.
1336 @retval EFI_SUCCESS The compression was sucessful.
1337 @retval EFI_BUFFER_TOO_SMALL The buffer was too small. DstSize is required.
1345 IN OUT UINT64
*DstSize
1364 mSrcUpperLimit
= mSrc
+ SrcSize
;
1366 mDstUpperLimit
= mDst
+*DstSize
;
1373 mOrigSize
= mCompSize
= 0;
1380 if (EFI_ERROR (Status
)) {
1381 return EFI_OUT_OF_RESOURCES
;
1384 // Null terminate the compressed data
1386 if (mDst
< mDstUpperLimit
) {
1390 // Fill in compressed size and original size
1393 PutDword (mCompSize
+ 1);
1394 PutDword (mOrigSize
);
1399 if (mCompSize
+ 1 + 8 > *DstSize
) {
1400 *DstSize
= mCompSize
+ 1 + 8;
1401 return EFI_BUFFER_TOO_SMALL
;
1403 *DstSize
= mCompSize
+ 1 + 8;