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 - 2018, 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 <Library/ShellLib.h>
32 #define UINT8_MAX 0xff
37 #define WNDSIZ (1U << WNDBIT)
39 #define BLKSIZ (1U << 14) // 16 * 1024U
40 #define PERC_FLAG 0x8000U
43 #define MAX_HASH_VAL (3 * WNDSIZ + (WNDSIZ / 512 + 1) * UINT8_MAX)
44 #define HASH(LoopVar7, LoopVar5) ((LoopVar7) + ((LoopVar5) << (WNDBIT - 9)) + WNDSIZ * 2)
45 #define CRCPOLY 0xA001
46 #define UPDATE_CRC(LoopVar5) mCrc = mCrcTable[(mCrc ^ (LoopVar5)) & 0xFF] ^ (mCrc >> UINT8_BIT)
49 // C: the Char&Len Set; P: the Position Set; T: the exTra Set
51 #define NC (UINT8_MAX + MAXMATCH + 2 - THRESHOLD)
53 #define NP (WNDBIT + 1)
55 #define NT (CODE_BIT + 3)
63 // Function Prototypes
67 Put a dword to output stream
69 @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;
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.
165 if (mDst
< mDstUpperLimit
) {
166 *mDst
++ = (UINT8
) (((UINT8
) (Data
)) & 0xff);
169 if (mDst
< mDstUpperLimit
) {
170 *mDst
++ = (UINT8
) (((UINT8
) (Data
>> 0x08)) & 0xff);
173 if (mDst
< mDstUpperLimit
) {
174 *mDst
++ = (UINT8
) (((UINT8
) (Data
>> 0x10)) & 0xff);
177 if (mDst
< mDstUpperLimit
) {
178 *mDst
++ = (UINT8
) (((UINT8
) (Data
>> 0x18)) & 0xff);
183 Allocate memory spaces for data structures used in compression process.
185 @retval EFI_SUCCESS Memory was allocated successfully.
186 @retval EFI_OUT_OF_RESOURCES A memory allocation failed.
193 mText
= AllocateZeroPool (WNDSIZ
* 2 + MAXMATCH
);
194 mLevel
= AllocateZeroPool ((WNDSIZ
+ UINT8_MAX
+ 1) * sizeof (*mLevel
));
195 mChildCount
= AllocateZeroPool ((WNDSIZ
+ UINT8_MAX
+ 1) * sizeof (*mChildCount
));
196 mPosition
= AllocateZeroPool ((WNDSIZ
+ UINT8_MAX
+ 1) * sizeof (*mPosition
));
197 mParent
= AllocateZeroPool (WNDSIZ
* 2 * sizeof (*mParent
));
198 mPrev
= AllocateZeroPool (WNDSIZ
* 2 * sizeof (*mPrev
));
199 mNext
= AllocateZeroPool ((MAX_HASH_VAL
+ 1) * sizeof (*mNext
));
202 mBuf
= AllocateZeroPool (mBufSiz
);
203 while (mBuf
== NULL
) {
204 mBufSiz
= (mBufSiz
/ 10U) * 9U;
205 if (mBufSiz
< 4 * 1024U) {
206 return EFI_OUT_OF_RESOURCES
;
209 mBuf
= AllocateZeroPool (mBufSiz
);
218 Called when compression is completed to free memory previously allocated.
226 SHELL_FREE_NON_NULL (mText
);
227 SHELL_FREE_NON_NULL (mLevel
);
228 SHELL_FREE_NON_NULL (mChildCount
);
229 SHELL_FREE_NON_NULL (mPosition
);
230 SHELL_FREE_NON_NULL (mParent
);
231 SHELL_FREE_NON_NULL (mPrev
);
232 SHELL_FREE_NON_NULL (mNext
);
233 SHELL_FREE_NON_NULL (mBuf
);
237 Initialize String Info Log data structures.
246 SetMem (mLevel
+ WNDSIZ
, (UINT8_MAX
+ 1) * sizeof (UINT8
), 1);
247 SetMem (mPosition
+ WNDSIZ
, (UINT8_MAX
+ 1) * sizeof (NODE
), 0);
249 SetMem (mParent
+ WNDSIZ
, WNDSIZ
* sizeof (NODE
), 0);
252 for (LoopVar1
= 1; LoopVar1
< WNDSIZ
- 1; LoopVar1
++) {
253 mNext
[LoopVar1
] = (NODE
) (LoopVar1
+ 1);
256 mNext
[WNDSIZ
- 1] = NIL
;
257 SetMem (mNext
+ WNDSIZ
* 2, (MAX_HASH_VAL
- WNDSIZ
* 2 + 1) * sizeof (NODE
), 0);
261 Find child node given the parent node and the edge character
263 @param[in] LoopVar6 The parent node.
264 @param[in] LoopVar5 The edge character.
266 @return The child node.
267 @retval NIL(Zero) No child could be found.
278 LoopVar4
= mNext
[HASH (LoopVar6
, LoopVar5
)];
279 mParent
[NIL
] = LoopVar6
; /* sentinel */
280 while (mParent
[LoopVar4
] != LoopVar6
) {
281 LoopVar4
= mNext
[LoopVar4
];
288 Create a new child for a given parent node.
290 @param[in] LoopVar6 The parent node.
291 @param[in] LoopVar5 The edge character.
292 @param[in] LoopVar4 The child node.
305 LoopVar12
= (NODE
) HASH (LoopVar6
, LoopVar5
);
306 LoopVar10
= mNext
[LoopVar12
];
307 mNext
[LoopVar12
] = LoopVar4
;
308 mNext
[LoopVar4
] = LoopVar10
;
309 mPrev
[LoopVar10
] = LoopVar4
;
310 mPrev
[LoopVar4
] = LoopVar12
;
311 mParent
[LoopVar4
] = LoopVar6
;
312 mChildCount
[LoopVar6
]++;
318 @param[in] Old The node to split.
331 mChildCount
[New
] = 0;
332 LoopVar10
= mPrev
[Old
];
333 mPrev
[New
] = LoopVar10
;
334 mNext
[LoopVar10
] = New
;
335 LoopVar10
= mNext
[Old
];
336 mNext
[New
] = LoopVar10
;
337 mPrev
[LoopVar10
] = New
;
338 mParent
[New
] = mParent
[Old
];
339 mLevel
[New
] = (UINT8
) mMatchLen
;
340 mPosition
[New
] = mPos
;
341 MakeChild (New
, mText
[mMatchPos
+ mMatchLen
], Old
);
342 MakeChild (New
, mText
[mPos
+ mMatchLen
], mPos
);
346 Insert string info for current position into the String Info Log.
365 if (mMatchLen
>= 4) {
367 // We have just got a long match, the target tree
368 // can be located by MatchPos + 1. Travese the tree
369 // from bottom up to get to a proper starting point.
370 // The usage of PERC_FLAG ensures proper node deletion
371 // in DeleteNode() later.
374 LoopVar4
= (NODE
) ((mMatchPos
+ 1) | WNDSIZ
);
375 LoopVar6
= mParent
[LoopVar4
];
376 while (LoopVar6
== NIL
) {
377 LoopVar4
= mNext
[LoopVar4
];
378 LoopVar6
= mParent
[LoopVar4
];
381 while (mLevel
[LoopVar6
] >= mMatchLen
) {
383 LoopVar6
= mParent
[LoopVar6
];
386 LoopVar10
= LoopVar6
;
387 while (mPosition
[LoopVar10
] < 0) {
388 mPosition
[LoopVar10
] = mPos
;
389 LoopVar10
= mParent
[LoopVar10
];
392 if (LoopVar10
< WNDSIZ
) {
393 mPosition
[LoopVar10
] = (NODE
) (mPos
| PERC_FLAG
);
397 // Locate the target tree
399 LoopVar6
= (NODE
) (mText
[mPos
] + WNDSIZ
);
400 LoopVar5
= mText
[mPos
+ 1];
401 LoopVar4
= Child (LoopVar6
, LoopVar5
);
402 if (LoopVar4
== NIL
) {
403 MakeChild (LoopVar6
, LoopVar5
, mPos
);
411 // Traverse down the tree to find a match.
412 // Update Position value along the route.
413 // Node split or creation is involved.
416 if (LoopVar4
>= WNDSIZ
) {
418 mMatchPos
= LoopVar4
;
420 LoopVar2
= mLevel
[LoopVar4
];
421 mMatchPos
= (NODE
) (mPosition
[LoopVar4
] & ~PERC_FLAG
);
424 if (mMatchPos
>= mPos
) {
428 TempString3
= &mText
[mPos
+ mMatchLen
];
429 TempString2
= &mText
[mMatchPos
+ mMatchLen
];
430 while (mMatchLen
< LoopVar2
) {
431 if (*TempString3
!= *TempString2
) {
441 if (mMatchLen
>= MAXMATCH
) {
445 mPosition
[LoopVar4
] = mPos
;
447 LoopVar4
= Child (LoopVar6
, *TempString3
);
448 if (LoopVar4
== NIL
) {
449 MakeChild (LoopVar6
, *TempString3
, mPos
);
456 LoopVar10
= mPrev
[LoopVar4
];
457 mPrev
[mPos
] = LoopVar10
;
458 mNext
[LoopVar10
] = mPos
;
459 LoopVar10
= mNext
[LoopVar4
];
460 mNext
[mPos
] = LoopVar10
;
461 mPrev
[LoopVar10
] = mPos
;
462 mParent
[mPos
] = LoopVar6
;
463 mParent
[LoopVar4
] = NIL
;
466 // Special usage of 'next'
468 mNext
[LoopVar4
] = mPos
;
473 Delete outdated string info. (The Usage of PERC_FLAG
474 ensures a clean deletion).
492 if (mParent
[mPos
] == NIL
) {
496 LoopVar4
= mPrev
[mPos
];
497 LoopVar11
= mNext
[mPos
];
498 mNext
[LoopVar4
] = LoopVar11
;
499 mPrev
[LoopVar11
] = LoopVar4
;
500 LoopVar4
= mParent
[mPos
];
502 if (LoopVar4
>= WNDSIZ
) {
506 mChildCount
[LoopVar4
]--;
507 if (mChildCount
[LoopVar4
] > 1) {
511 LoopVar10
= (NODE
) (mPosition
[LoopVar4
] & ~PERC_FLAG
);
512 if (LoopVar10
>= mPos
) {
516 LoopVar11
= LoopVar10
;
517 LoopVar6
= mParent
[LoopVar4
];
518 LoopVar9
= mPosition
[LoopVar6
];
519 while ((LoopVar9
& PERC_FLAG
) != 0){
520 LoopVar9
&= ~PERC_FLAG
;
521 if (LoopVar9
>= mPos
) {
525 if (LoopVar9
> LoopVar11
) {
526 LoopVar11
= LoopVar9
;
529 mPosition
[LoopVar6
] = (NODE
) (LoopVar11
| WNDSIZ
);
530 LoopVar6
= mParent
[LoopVar6
];
531 LoopVar9
= mPosition
[LoopVar6
];
534 if (LoopVar6
< WNDSIZ
) {
535 if (LoopVar9
>= mPos
) {
539 if (LoopVar9
> LoopVar11
) {
540 LoopVar11
= LoopVar9
;
543 mPosition
[LoopVar6
] = (NODE
) (LoopVar11
| WNDSIZ
| PERC_FLAG
);
546 LoopVar11
= Child (LoopVar4
, mText
[LoopVar10
+ mLevel
[LoopVar4
]]);
547 LoopVar10
= mPrev
[LoopVar11
];
548 LoopVar9
= mNext
[LoopVar11
];
549 mNext
[LoopVar10
] = LoopVar9
;
550 mPrev
[LoopVar9
] = LoopVar10
;
551 LoopVar10
= mPrev
[LoopVar4
];
552 mNext
[LoopVar10
] = LoopVar11
;
553 mPrev
[LoopVar11
] = LoopVar10
;
554 LoopVar10
= mNext
[LoopVar4
];
555 mPrev
[LoopVar10
] = LoopVar11
;
556 mNext
[LoopVar11
] = LoopVar10
;
557 mParent
[LoopVar11
] = mParent
[LoopVar4
];
558 mParent
[LoopVar4
] = NIL
;
559 mNext
[LoopVar4
] = mAvail
;
566 @param[out] LoopVar7 The buffer to hold the data.
567 @param[in] LoopVar8 The number of bytes to read.
569 @return The number of bytes actually read.
579 for (LoopVar1
= 0; mSrc
< mSrcUpperLimit
&& LoopVar1
< LoopVar8
; LoopVar1
++) {
580 *LoopVar7
++ = *mSrc
++;
585 LoopVar7
-= LoopVar8
;
586 mOrigSize
+= LoopVar8
;
588 while (LoopVar1
>= 0) {
589 UPDATE_CRC (*LoopVar7
++);
597 Advance the current position (read in new data if needed).
598 Delete outdated string info. Find a match string for current position.
600 @retval TRUE The operation was successful.
601 @retval FALSE The operation failed due to insufficient memory.
613 if (mPos
== WNDSIZ
* 2) {
614 Temp
= AllocateZeroPool (WNDSIZ
+ MAXMATCH
);
618 CopyMem (Temp
, &mText
[WNDSIZ
], WNDSIZ
+ MAXMATCH
);
619 CopyMem (&mText
[0], Temp
, WNDSIZ
+ MAXMATCH
);
621 LoopVar8
= FreadCrc (&mText
[WNDSIZ
+ MAXMATCH
], WNDSIZ
);
622 mRemainder
+= LoopVar8
;
633 Send entry LoopVar1 down the queue.
635 @param[in] LoopVar1 The index of the item to move.
647 // priority queue: send i-th entry down heap
651 while (LoopVar1
<= mHeapSize
) {
652 if (LoopVar1
< mHeapSize
&& mFreq
[mHeap
[LoopVar1
]] > mFreq
[mHeap
[LoopVar1
+ 1]]) {
656 if (mFreq
[LoopVar2
] <= mFreq
[mHeap
[LoopVar1
]]) {
660 mHeap
[i
] = mHeap
[LoopVar1
];
665 mHeap
[i
] = (INT16
) LoopVar2
;
669 Count the number of each code length for a Huffman tree.
671 @param[in] LoopVar1 The top node.
678 if (LoopVar1
< mTempInt32
) {
679 mLenCnt
[(mHuffmanDepth
< 16) ? mHuffmanDepth
: 16]++;
682 CountLen (mLeft
[LoopVar1
]);
683 CountLen (mRight
[LoopVar1
]);
689 Create code length array for a Huffman tree.
691 @param[in] Root The root of the tree.
703 for (LoopVar1
= 0; LoopVar1
<= 16; LoopVar1
++) {
704 mLenCnt
[LoopVar1
] = 0;
710 // Adjust the length count array so that
711 // no code will be generated longer than its designated length
714 for (LoopVar1
= 16; LoopVar1
> 0; LoopVar1
--) {
715 Cum
+= mLenCnt
[LoopVar1
] << (16 - LoopVar1
);
718 while (Cum
!= (1U << 16)) {
720 for (LoopVar1
= 15; LoopVar1
> 0; LoopVar1
--) {
721 if (mLenCnt
[LoopVar1
] != 0) {
723 mLenCnt
[LoopVar1
+ 1] += 2;
731 for (LoopVar1
= 16; LoopVar1
> 0; LoopVar1
--) {
732 LoopVar2
= mLenCnt
[LoopVar1
];
734 while (LoopVar2
>= 0) {
735 mLen
[*mSortPtr
++] = (UINT8
) LoopVar1
;
742 Assign code to each symbol based on the code length array.
744 @param[in] LoopVar8 The number of symbols.
745 @param[in] Len The code length array.
746 @param[out] Code The stores codes for each symbol.
759 for (LoopVar1
= 1; LoopVar1
<= 16; LoopVar1
++) {
760 Start
[LoopVar1
+ 1] = (UINT16
) ((Start
[LoopVar1
] + mLenCnt
[LoopVar1
]) << 1);
763 for (LoopVar1
= 0; LoopVar1
< LoopVar8
; LoopVar1
++) {
764 Code
[LoopVar1
] = Start
[Len
[LoopVar1
]]++;
769 Generates Huffman codes given a frequency distribution of symbols.
771 @param[in] NParm The number of symbols.
772 @param[in] FreqParm The frequency of each symbol.
773 @param[out] LenParm The code length for each symbol.
774 @param[out] CodeParm The code for each symbol.
776 @return The root of the Huffman tree.
781 IN UINT16 FreqParm
[ ],
782 OUT UINT8 LenParm
[ ],
783 OUT UINT16 CodeParm
[ ]
795 // make tree, calculate len[], return root
803 for (LoopVar1
= 0; LoopVar1
< mTempInt32
; LoopVar1
++) {
805 if ((mFreq
[LoopVar1
]) != 0) {
807 mHeap
[mHeapSize
] = (INT16
) LoopVar1
;
812 CodeParm
[mHeap
[1]] = 0;
816 for (LoopVar1
= mHeapSize
/ 2; LoopVar1
>= 1; LoopVar1
--) {
818 // make priority queue
826 if (LoopVar1
< mTempInt32
) {
827 *mSortPtr
++ = (UINT16
) LoopVar1
;
830 mHeap
[1] = mHeap
[mHeapSize
--];
833 if (LoopVar2
< mTempInt32
) {
834 *mSortPtr
++ = (UINT16
) LoopVar2
;
838 mFreq
[LoopVar3
] = (UINT16
) (mFreq
[LoopVar1
] + mFreq
[LoopVar2
]);
839 mHeap
[1] = (INT16
) LoopVar3
;
841 mLeft
[LoopVar3
] = (UINT16
) LoopVar1
;
842 mRight
[LoopVar3
] = (UINT16
) LoopVar2
;
843 } while (mHeapSize
> 1);
847 MakeCode (NParm
, LenParm
, CodeParm
);
856 Outputs rightmost LoopVar8 bits of x
858 @param[in] LoopVar8 The rightmost LoopVar8 bits of the data is used.
859 @param[in] x The data.
869 if (LoopVar8
< mBitCount
) {
870 mSubBitBuf
|= x
<< (mBitCount
-= LoopVar8
);
873 Temp
= (UINT8
)(mSubBitBuf
| (x
>> (LoopVar8
-= mBitCount
)));
874 if (mDst
< mDstUpperLimit
) {
879 if (LoopVar8
< UINT8_BIT
) {
880 mSubBitBuf
= x
<< (mBitCount
= UINT8_BIT
- LoopVar8
);
883 Temp
= (UINT8
)(x
>> (LoopVar8
- UINT8_BIT
));
884 if (mDst
< mDstUpperLimit
) {
889 mSubBitBuf
= x
<< (mBitCount
= 2 * UINT8_BIT
- LoopVar8
);
895 Encode a signed 32 bit number.
897 @param[in] LoopVar5 The number to encode.
904 PutBits (mCLen
[LoopVar5
], mCCode
[LoopVar5
]);
908 Encode a unsigned 32 bit number.
910 @param[in] LoopVar7 The number to encode.
923 while (LoopVar6
!= 0) {
928 PutBits (mPTLen
[LoopVar5
], mPTCode
[LoopVar5
]);
930 PutBits(LoopVar5
- 1, LoopVar7
& (0xFFFFU
>> (17 - LoopVar5
)));
935 Count the frequencies for the Extra Set.
951 for (LoopVar1
= 0; LoopVar1
< NT
; LoopVar1
++) {
952 mTFreq
[LoopVar1
] = 0;
956 while (LoopVar8
> 0 && mCLen
[LoopVar8
- 1] == 0) {
961 while (LoopVar1
< LoopVar8
) {
962 LoopVar3
= mCLen
[LoopVar1
++];
965 while (LoopVar1
< LoopVar8
&& mCLen
[LoopVar1
] == 0) {
971 mTFreq
[0] = (UINT16
) (mTFreq
[0] + Count
);
972 } else if (Count
<= 18) {
974 } else if (Count
== 19) {
981 ASSERT((LoopVar3
+2)<(2 * NT
- 1));
982 mTFreq
[LoopVar3
+ 2]++;
988 Outputs the code length array for the Extra Set or the Position Set.
990 @param[in] LoopVar8 The number of symbols.
991 @param[in] nbit The number of bits needed to represent 'LoopVar8'.
992 @param[in] Special The special symbol that needs to be take care of.
1006 while (LoopVar8
> 0 && mPTLen
[LoopVar8
- 1] == 0) {
1010 PutBits (nbit
, LoopVar8
);
1012 while (LoopVar1
< LoopVar8
) {
1013 LoopVar3
= mPTLen
[LoopVar1
++];
1014 if (LoopVar3
<= 6) {
1015 PutBits (3, LoopVar3
);
1017 PutBits (LoopVar3
- 3, (1U << (LoopVar3
- 3)) - 2);
1020 if (LoopVar1
== Special
) {
1021 while (LoopVar1
< 6 && mPTLen
[LoopVar1
] == 0) {
1025 PutBits (2, (LoopVar1
- 3) & 3);
1031 Outputs the code length array for Char&Length Set.
1047 while (LoopVar8
> 0 && mCLen
[LoopVar8
- 1] == 0) {
1051 PutBits (CBIT
, LoopVar8
);
1053 while (LoopVar1
< LoopVar8
) {
1054 LoopVar3
= mCLen
[LoopVar1
++];
1055 if (LoopVar3
== 0) {
1057 while (LoopVar1
< LoopVar8
&& mCLen
[LoopVar1
] == 0) {
1063 for (LoopVar3
= 0; LoopVar3
< Count
; LoopVar3
++) {
1064 PutBits (mPTLen
[0], mPTCode
[0]);
1066 } else if (Count
<= 18) {
1067 PutBits (mPTLen
[1], mPTCode
[1]);
1068 PutBits (4, Count
- 3);
1069 } else if (Count
== 19) {
1070 PutBits (mPTLen
[0], mPTCode
[0]);
1071 PutBits (mPTLen
[1], mPTCode
[1]);
1074 PutBits (mPTLen
[2], mPTCode
[2]);
1075 PutBits (CBIT
, Count
- 20);
1078 ASSERT((LoopVar3
+2)<NPT
);
1079 PutBits (mPTLen
[LoopVar3
+ 2], mPTCode
[LoopVar3
+ 2]);
1085 Huffman code the block and output it.
1106 Root
= MakeTree (NC
, mCFreq
, mCLen
, mCCode
);
1107 Size
= mCFreq
[Root
];
1111 Root
= MakeTree (NT
, mTFreq
, mPTLen
, mPTCode
);
1113 WritePTLen (NT
, TBIT
, 3);
1116 PutBits (TBIT
, Root
);
1124 PutBits (CBIT
, Root
);
1127 Root
= MakeTree (NP
, mPFreq
, mPTLen
, mPTCode
);
1129 WritePTLen (NP
, PBIT
, -1);
1132 PutBits (PBIT
, Root
);
1136 for (LoopVar1
= 0; LoopVar1
< Size
; LoopVar1
++) {
1137 if (LoopVar1
% UINT8_BIT
== 0) {
1138 Flags
= mBuf
[Pos
++];
1142 if ((Flags
& (1U << (UINT8_BIT
- 1))) != 0){
1143 EncodeC(mBuf
[Pos
++] + (1U << UINT8_BIT
));
1144 LoopVar3
= mBuf
[Pos
++] << UINT8_BIT
;
1145 LoopVar3
+= mBuf
[Pos
++];
1149 EncodeC (mBuf
[Pos
++]);
1153 SetMem (mCFreq
, NC
* sizeof (UINT16
), 0);
1154 SetMem (mPFreq
, NP
* sizeof (UINT16
), 0);
1158 Start the huffman encoding.
1166 SetMem (mCFreq
, NC
* sizeof (UINT16
), 0);
1167 SetMem (mPFreq
, NP
* sizeof (UINT16
), 0);
1169 mOutputPos
= mOutputMask
= 0;
1171 mBitCount
= UINT8_BIT
;
1176 Outputs an Original Character or a Pointer.
1178 @param[in] LoopVar5 The original character or the 'String Length' element of
1180 @param[in] LoopVar7 The 'Position' field of a Pointer.
1190 if ((mOutputMask
>>= 1) == 0) {
1191 mOutputMask
= 1U << (UINT8_BIT
- 1);
1192 if (mOutputPos
>= mBufSiz
- 3 * UINT8_BIT
) {
1197 CPos
= mOutputPos
++;
1200 mBuf
[mOutputPos
++] = (UINT8
) LoopVar5
;
1202 if (LoopVar5
>= (1U << UINT8_BIT
)) {
1203 mBuf
[CPos
] = (UINT8
)(mBuf
[CPos
]|mOutputMask
);
1204 mBuf
[mOutputPos
++] = (UINT8
)(LoopVar7
>> UINT8_BIT
);
1205 mBuf
[mOutputPos
++] = (UINT8
) LoopVar7
;
1207 while (LoopVar7
!=0) {
1216 End the huffman encoding.
1227 // Flush remaining bits
1229 PutBits (UINT8_BIT
- 1, 0);
1233 The main controlling routine for compression process.
1235 @retval EFI_SUCCESS The compression is successful.
1236 @retval EFI_OUT_0F_RESOURCES Not enough memory for compression process.
1247 Status
= AllocateMemory ();
1248 if (EFI_ERROR (Status
)) {
1257 mRemainder
= FreadCrc (&mText
[WNDSIZ
], WNDSIZ
+ MAXMATCH
);
1262 if (mMatchLen
> mRemainder
) {
1263 mMatchLen
= mRemainder
;
1266 while (mRemainder
> 0) {
1267 LastMatchLen
= mMatchLen
;
1268 LastMatchPos
= mMatchPos
;
1269 if (!GetNextMatch ()) {
1270 Status
= EFI_OUT_OF_RESOURCES
;
1272 if (mMatchLen
> mRemainder
) {
1273 mMatchLen
= mRemainder
;
1276 if (mMatchLen
> LastMatchLen
|| LastMatchLen
< THRESHOLD
) {
1278 // Not enough benefits are gained by outputting a pointer,
1279 // so just output the original character
1281 CompressOutput(mText
[mPos
- 1], 0);
1284 // Outputting a pointer is beneficial enough, do it.
1287 CompressOutput(LastMatchLen
+ (UINT8_MAX
+ 1 - THRESHOLD
),
1288 (mPos
- LastMatchPos
- 2) & (WNDSIZ
- 1));
1290 while (LastMatchLen
> 0) {
1291 if (!GetNextMatch ()) {
1292 Status
= EFI_OUT_OF_RESOURCES
;
1297 if (mMatchLen
> mRemainder
) {
1298 mMatchLen
= mRemainder
;
1309 The compression routine.
1311 @param[in] SrcBuffer The buffer containing the source data.
1312 @param[in] SrcSize Number of bytes in SrcBuffer.
1313 @param[in] DstBuffer The buffer to put the compressed image in.
1314 @param[in, out] DstSize On input the size (in bytes) of DstBuffer, on
1315 return the number of bytes placed in DstBuffer.
1317 @retval EFI_SUCCESS The compression was sucessful.
1318 @retval EFI_BUFFER_TOO_SMALL The buffer was too small. DstSize is required.
1325 IN OUT UINT64
*DstSize
1344 mSrcUpperLimit
= mSrc
+ SrcSize
;
1346 mDstUpperLimit
= mDst
+*DstSize
;
1353 mOrigSize
= mCompSize
= 0;
1360 if (EFI_ERROR (Status
)) {
1361 return EFI_OUT_OF_RESOURCES
;
1364 // Null terminate the compressed data
1366 if (mDst
< mDstUpperLimit
) {
1370 // Fill in compressed size and original size
1373 PutDword (mCompSize
+ 1);
1374 PutDword (mOrigSize
);
1379 if (mCompSize
+ 1 + 8 > *DstSize
) {
1380 *DstSize
= mCompSize
+ 1 + 8;
1381 return EFI_BUFFER_TOO_SMALL
;
1383 *DstSize
= mCompSize
+ 1 + 8;