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.
610 @retval TRUE The operation was successful.
611 @retval FALSE The operation failed due to insufficient memory.
624 if (mPos
== WNDSIZ
* 2) {
625 Temp
= AllocateZeroPool (WNDSIZ
+ MAXMATCH
);
629 CopyMem (Temp
, &mText
[WNDSIZ
], WNDSIZ
+ MAXMATCH
);
630 CopyMem (&mText
[0], Temp
, WNDSIZ
+ MAXMATCH
);
632 LoopVar8
= FreadCrc (&mText
[WNDSIZ
+ MAXMATCH
], WNDSIZ
);
633 mRemainder
+= LoopVar8
;
644 Send entry LoopVar1 down the queue.
646 @param[in] LoopVar1 The index of the item to move.
659 // priority queue: send i-th entry down heap
663 while (LoopVar1
<= mHeapSize
) {
664 if (LoopVar1
< mHeapSize
&& mFreq
[mHeap
[LoopVar1
]] > mFreq
[mHeap
[LoopVar1
+ 1]]) {
668 if (mFreq
[LoopVar2
] <= mFreq
[mHeap
[LoopVar1
]]) {
672 mHeap
[i
] = mHeap
[LoopVar1
];
677 mHeap
[i
] = (INT16
) LoopVar2
;
681 Count the number of each code length for a Huffman tree.
683 @param[in] LoopVar1 The top node.
691 if (LoopVar1
< mTempInt32
) {
692 mLenCnt
[(mHuffmanDepth
< 16) ? mHuffmanDepth
: 16]++;
695 CountLen (mLeft
[LoopVar1
]);
696 CountLen (mRight
[LoopVar1
]);
702 Create code length array for a Huffman tree.
704 @param[in] Root The root of the tree.
717 for (LoopVar1
= 0; LoopVar1
<= 16; LoopVar1
++) {
718 mLenCnt
[LoopVar1
] = 0;
724 // Adjust the length count array so that
725 // no code will be generated longer than its designated length
728 for (LoopVar1
= 16; LoopVar1
> 0; LoopVar1
--) {
729 Cum
+= mLenCnt
[LoopVar1
] << (16 - LoopVar1
);
732 while (Cum
!= (1U << 16)) {
734 for (LoopVar1
= 15; LoopVar1
> 0; LoopVar1
--) {
735 if (mLenCnt
[LoopVar1
] != 0) {
737 mLenCnt
[LoopVar1
+ 1] += 2;
745 for (LoopVar1
= 16; LoopVar1
> 0; LoopVar1
--) {
746 LoopVar2
= mLenCnt
[LoopVar1
];
748 while (LoopVar2
>= 0) {
749 mLen
[*mSortPtr
++] = (UINT8
) LoopVar1
;
756 Assign code to each symbol based on the code length array.
758 @param[in] LoopVar8 The number of symbols.
759 @param[in] Len The code length array.
760 @param[out] Code The stores codes for each symbol.
774 for (LoopVar1
= 1; LoopVar1
<= 16; LoopVar1
++) {
775 Start
[LoopVar1
+ 1] = (UINT16
) ((Start
[LoopVar1
] + mLenCnt
[LoopVar1
]) << 1);
778 for (LoopVar1
= 0; LoopVar1
< LoopVar8
; LoopVar1
++) {
779 Code
[LoopVar1
] = Start
[Len
[LoopVar1
]]++;
784 Generates Huffman codes given a frequency distribution of symbols.
786 @param[in] NParm The number of symbols.
787 @param[in] FreqParm The frequency of each symbol.
788 @param[out] LenParm The code length for each symbol.
789 @param[out] CodeParm The code for each symbol.
791 @return The root of the Huffman tree.
797 IN UINT16 FreqParm
[ ],
798 OUT UINT8 LenParm
[ ],
799 OUT UINT16 CodeParm
[ ]
811 // make tree, calculate len[], return root
819 for (LoopVar1
= 0; LoopVar1
< mTempInt32
; LoopVar1
++) {
821 if ((mFreq
[LoopVar1
]) != 0) {
823 mHeap
[mHeapSize
] = (INT16
) LoopVar1
;
828 CodeParm
[mHeap
[1]] = 0;
832 for (LoopVar1
= mHeapSize
/ 2; LoopVar1
>= 1; LoopVar1
--) {
834 // make priority queue
842 if (LoopVar1
< mTempInt32
) {
843 *mSortPtr
++ = (UINT16
) LoopVar1
;
846 mHeap
[1] = mHeap
[mHeapSize
--];
849 if (LoopVar2
< mTempInt32
) {
850 *mSortPtr
++ = (UINT16
) LoopVar2
;
854 mFreq
[LoopVar3
] = (UINT16
) (mFreq
[LoopVar1
] + mFreq
[LoopVar2
]);
855 mHeap
[1] = (INT16
) LoopVar3
;
857 mLeft
[LoopVar3
] = (UINT16
) LoopVar1
;
858 mRight
[LoopVar3
] = (UINT16
) LoopVar2
;
859 } while (mHeapSize
> 1);
863 MakeCode (NParm
, LenParm
, CodeParm
);
872 Outputs rightmost LoopVar8 bits of x
874 @param[in] LoopVar8 The rightmost LoopVar8 bits of the data is used.
875 @param[in] x The data.
886 if (LoopVar8
< mBitCount
) {
887 mSubBitBuf
|= x
<< (mBitCount
-= LoopVar8
);
890 Temp
= (UINT8
)(mSubBitBuf
| (x
>> (LoopVar8
-= mBitCount
)));
891 if (mDst
< mDstUpperLimit
) {
896 if (LoopVar8
< UINT8_BIT
) {
897 mSubBitBuf
= x
<< (mBitCount
= UINT8_BIT
- LoopVar8
);
900 Temp
= (UINT8
)(x
>> (LoopVar8
- UINT8_BIT
));
901 if (mDst
< mDstUpperLimit
) {
906 mSubBitBuf
= x
<< (mBitCount
= 2 * UINT8_BIT
- LoopVar8
);
912 Encode a signed 32 bit number.
914 @param[in] LoopVar5 The number to encode.
922 PutBits (mCLen
[LoopVar5
], mCCode
[LoopVar5
]);
926 Encode a unsigned 32 bit number.
928 @param[in] LoopVar7 The number to encode.
942 while (LoopVar6
!= 0) {
947 PutBits (mPTLen
[LoopVar5
], mPTCode
[LoopVar5
]);
949 PutBits(LoopVar5
- 1, LoopVar7
& (0xFFFFU
>> (17 - LoopVar5
)));
954 Count the frequencies for the Extra Set.
971 for (LoopVar1
= 0; LoopVar1
< NT
; LoopVar1
++) {
972 mTFreq
[LoopVar1
] = 0;
976 while (LoopVar8
> 0 && mCLen
[LoopVar8
- 1] == 0) {
981 while (LoopVar1
< LoopVar8
) {
982 LoopVar3
= mCLen
[LoopVar1
++];
985 while (LoopVar1
< LoopVar8
&& mCLen
[LoopVar1
] == 0) {
991 mTFreq
[0] = (UINT16
) (mTFreq
[0] + Count
);
992 } else if (Count
<= 18) {
994 } else if (Count
== 19) {
1001 ASSERT((LoopVar3
+2)<(2 * NT
- 1));
1002 mTFreq
[LoopVar3
+ 2]++;
1008 Outputs the code length array for the Extra Set or the Position Set.
1010 @param[in] LoopVar8 The number of symbols.
1011 @param[in] nbit The number of bits needed to represent 'LoopVar8'.
1012 @param[in] Special The special symbol that needs to be take care of.
1027 while (LoopVar8
> 0 && mPTLen
[LoopVar8
- 1] == 0) {
1031 PutBits (nbit
, LoopVar8
);
1033 while (LoopVar1
< LoopVar8
) {
1034 LoopVar3
= mPTLen
[LoopVar1
++];
1035 if (LoopVar3
<= 6) {
1036 PutBits (3, LoopVar3
);
1038 PutBits (LoopVar3
- 3, (1U << (LoopVar3
- 3)) - 2);
1041 if (LoopVar1
== Special
) {
1042 while (LoopVar1
< 6 && mPTLen
[LoopVar1
] == 0) {
1046 PutBits (2, (LoopVar1
- 3) & 3);
1052 Outputs the code length array for Char&Length Set.
1069 while (LoopVar8
> 0 && mCLen
[LoopVar8
- 1] == 0) {
1073 PutBits (CBIT
, LoopVar8
);
1075 while (LoopVar1
< LoopVar8
) {
1076 LoopVar3
= mCLen
[LoopVar1
++];
1077 if (LoopVar3
== 0) {
1079 while (LoopVar1
< LoopVar8
&& mCLen
[LoopVar1
] == 0) {
1085 for (LoopVar3
= 0; LoopVar3
< Count
; LoopVar3
++) {
1086 PutBits (mPTLen
[0], mPTCode
[0]);
1088 } else if (Count
<= 18) {
1089 PutBits (mPTLen
[1], mPTCode
[1]);
1090 PutBits (4, Count
- 3);
1091 } else if (Count
== 19) {
1092 PutBits (mPTLen
[0], mPTCode
[0]);
1093 PutBits (mPTLen
[1], mPTCode
[1]);
1096 PutBits (mPTLen
[2], mPTCode
[2]);
1097 PutBits (CBIT
, Count
- 20);
1100 ASSERT((LoopVar3
+2)<NPT
);
1101 PutBits (mPTLen
[LoopVar3
+ 2], mPTCode
[LoopVar3
+ 2]);
1107 Huffman code the block and output it.
1129 Root
= MakeTree (NC
, mCFreq
, mCLen
, mCCode
);
1130 Size
= mCFreq
[Root
];
1134 Root
= MakeTree (NT
, mTFreq
, mPTLen
, mPTCode
);
1136 WritePTLen (NT
, TBIT
, 3);
1139 PutBits (TBIT
, Root
);
1147 PutBits (CBIT
, Root
);
1150 Root
= MakeTree (NP
, mPFreq
, mPTLen
, mPTCode
);
1152 WritePTLen (NP
, PBIT
, -1);
1155 PutBits (PBIT
, Root
);
1159 for (LoopVar1
= 0; LoopVar1
< Size
; LoopVar1
++) {
1160 if (LoopVar1
% UINT8_BIT
== 0) {
1161 Flags
= mBuf
[Pos
++];
1165 if ((Flags
& (1U << (UINT8_BIT
- 1))) != 0){
1166 EncodeC(mBuf
[Pos
++] + (1U << UINT8_BIT
));
1167 LoopVar3
= mBuf
[Pos
++] << UINT8_BIT
;
1168 LoopVar3
+= mBuf
[Pos
++];
1172 EncodeC (mBuf
[Pos
++]);
1176 SetMem (mCFreq
, NC
* sizeof (UINT16
), 0);
1177 SetMem (mPFreq
, NP
* sizeof (UINT16
), 0);
1181 Start the huffman encoding.
1190 SetMem (mCFreq
, NC
* sizeof (UINT16
), 0);
1191 SetMem (mPFreq
, NP
* sizeof (UINT16
), 0);
1193 mOutputPos
= mOutputMask
= 0;
1195 mBitCount
= UINT8_BIT
;
1200 Outputs an Original Character or a Pointer.
1202 @param[in] LoopVar5 The original character or the 'String Length' element of
1204 @param[in] LoopVar7 The 'Position' field of a Pointer.
1215 if ((mOutputMask
>>= 1) == 0) {
1216 mOutputMask
= 1U << (UINT8_BIT
- 1);
1217 if (mOutputPos
>= mBufSiz
- 3 * UINT8_BIT
) {
1222 CPos
= mOutputPos
++;
1225 mBuf
[mOutputPos
++] = (UINT8
) LoopVar5
;
1227 if (LoopVar5
>= (1U << UINT8_BIT
)) {
1228 mBuf
[CPos
] = (UINT8
)(mBuf
[CPos
]|mOutputMask
);
1229 mBuf
[mOutputPos
++] = (UINT8
)(LoopVar7
>> UINT8_BIT
);
1230 mBuf
[mOutputPos
++] = (UINT8
) LoopVar7
;
1232 while (LoopVar7
!=0) {
1241 End the huffman encoding.
1253 // Flush remaining bits
1255 PutBits (UINT8_BIT
- 1, 0);
1259 The main controlling routine for compression process.
1261 @retval EFI_SUCCESS The compression is successful.
1262 @retval EFI_OUT_0F_RESOURCES Not enough memory for compression process.
1274 Status
= AllocateMemory ();
1275 if (EFI_ERROR (Status
)) {
1284 mRemainder
= FreadCrc (&mText
[WNDSIZ
], WNDSIZ
+ MAXMATCH
);
1289 if (mMatchLen
> mRemainder
) {
1290 mMatchLen
= mRemainder
;
1293 while (mRemainder
> 0) {
1294 LastMatchLen
= mMatchLen
;
1295 LastMatchPos
= mMatchPos
;
1296 if (!GetNextMatch ()) {
1297 Status
= EFI_OUT_OF_RESOURCES
;
1299 if (mMatchLen
> mRemainder
) {
1300 mMatchLen
= mRemainder
;
1303 if (mMatchLen
> LastMatchLen
|| LastMatchLen
< THRESHOLD
) {
1305 // Not enough benefits are gained by outputting a pointer,
1306 // so just output the original character
1308 CompressOutput(mText
[mPos
- 1], 0);
1311 // Outputting a pointer is beneficial enough, do it.
1314 CompressOutput(LastMatchLen
+ (UINT8_MAX
+ 1 - THRESHOLD
),
1315 (mPos
- LastMatchPos
- 2) & (WNDSIZ
- 1));
1317 while (LastMatchLen
> 0) {
1318 if (!GetNextMatch ()) {
1319 Status
= EFI_OUT_OF_RESOURCES
;
1324 if (mMatchLen
> mRemainder
) {
1325 mMatchLen
= mRemainder
;
1336 The compression routine.
1338 @param[in] SrcBuffer The buffer containing the source data.
1339 @param[in] SrcSize The number of bytes in SrcBuffer.
1340 @param[in] DstBuffer The buffer to put the compressed image in.
1341 @param[in, out] DstSize On input the size (in bytes) of DstBuffer, on
1342 return the number of bytes placed in DstBuffer.
1344 @retval EFI_SUCCESS The compression was sucessful.
1345 @retval EFI_BUFFER_TOO_SMALL The buffer was too small. DstSize is required.
1353 IN OUT UINT64
*DstSize
1372 mSrcUpperLimit
= mSrc
+ SrcSize
;
1374 mDstUpperLimit
= mDst
+*DstSize
;
1381 mOrigSize
= mCompSize
= 0;
1388 if (EFI_ERROR (Status
)) {
1389 return EFI_OUT_OF_RESOURCES
;
1392 // Null terminate the compressed data
1394 if (mDst
< mDstUpperLimit
) {
1398 // Fill in compressed size and original size
1401 PutDword (mCompSize
+ 1);
1402 PutDword (mOrigSize
);
1407 if (mCompSize
+ 1 + 8 > *DstSize
) {
1408 *DstSize
= mCompSize
+ 1 + 8;
1409 return EFI_BUFFER_TOO_SMALL
;
1411 *DstSize
= mCompSize
+ 1 + 8;