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 SPDX-License-Identifier: BSD-2-Clause-Patent
15 #include <Library/MemoryAllocationLib.h>
16 #include <Library/BaseMemoryLib.h>
17 #include <Library/DebugLib.h>
18 #include <Library/ShellLib.h>
26 #define UINT8_MAX 0xff
31 #define WNDSIZ (1U << WNDBIT)
33 #define BLKSIZ (1U << 14) // 16 * 1024U
34 #define PERC_FLAG 0x8000U
37 #define MAX_HASH_VAL (3 * WNDSIZ + (WNDSIZ / 512 + 1) * UINT8_MAX)
38 #define HASH(LoopVar7, LoopVar5) ((LoopVar7) + ((LoopVar5) << (WNDBIT - 9)) + WNDSIZ * 2)
39 #define CRCPOLY 0xA001
40 #define UPDATE_CRC(LoopVar5) mCrc = mCrcTable[(mCrc ^ (LoopVar5)) & 0xFF] ^ (mCrc >> UINT8_BIT)
43 // C: the Char&Len Set; P: the Position Set; T: the exTra Set
45 #define NC (UINT8_MAX + MAXMATCH + 2 - THRESHOLD)
47 #define NP (WNDBIT + 1)
49 #define NT (CODE_BIT + 3)
57 // Function Prototypes
61 Put a dword to output stream
63 @param[in] Data The dword to put.
75 STATIC UINT8
*mSrcUpperLimit
;
76 STATIC UINT8
*mDstUpperLimit
;
80 STATIC UINT8
*mChildCount
;
82 STATIC UINT8 mCLen
[NC
];
83 STATIC UINT8 mPTLen
[NPT
];
85 STATIC INT16 mHeap
[NC
+ 1];
86 STATIC INT32 mRemainder
;
87 STATIC INT32 mMatchLen
;
88 STATIC INT32 mBitCount
;
89 STATIC INT32 mHeapSize
;
90 STATIC INT32 mTempInt32
;
91 STATIC UINT32 mBufSiz
= 0;
92 STATIC UINT32 mOutputPos
;
93 STATIC UINT32 mOutputMask
;
94 STATIC UINT32 mSubBitBuf
;
96 STATIC UINT32 mCompSize
;
97 STATIC UINT32 mOrigSize
;
100 STATIC UINT16
*mSortPtr
;
101 STATIC UINT16 mLenCnt
[17];
102 STATIC UINT16 mLeft
[2 * NC
- 1];
103 STATIC UINT16 mRight
[2 * NC
- 1];
104 STATIC UINT16 mCrcTable
[UINT8_MAX
+ 1];
105 STATIC UINT16 mCFreq
[2 * NC
- 1];
106 STATIC UINT16 mCCode
[NC
];
107 STATIC UINT16 mPFreq
[2 * NP
- 1];
108 STATIC UINT16 mPTCode
[NPT
];
109 STATIC UINT16 mTFreq
[2 * NT
- 1];
112 STATIC NODE mMatchPos
;
114 STATIC NODE
*mPosition
;
115 STATIC NODE
*mParent
;
117 STATIC NODE
*mNext
= NULL
;
118 INT32 mHuffmanDepth
= 0;
135 for (LoopVar1
= 0; LoopVar1
<= UINT8_MAX
; LoopVar1
++) {
137 for (LoopVar2
= 0; LoopVar2
< UINT8_BIT
; LoopVar2
++) {
138 if ((LoopVar4
& 1) != 0) {
139 LoopVar4
= (LoopVar4
>> 1) ^ CRCPOLY
;
145 mCrcTable
[LoopVar1
] = (UINT16
) LoopVar4
;
150 Put a dword to output stream
152 @param[in] Data The dword to put.
159 if (mDst
< mDstUpperLimit
) {
160 *mDst
++ = (UINT8
) (((UINT8
) (Data
)) & 0xff);
163 if (mDst
< mDstUpperLimit
) {
164 *mDst
++ = (UINT8
) (((UINT8
) (Data
>> 0x08)) & 0xff);
167 if (mDst
< mDstUpperLimit
) {
168 *mDst
++ = (UINT8
) (((UINT8
) (Data
>> 0x10)) & 0xff);
171 if (mDst
< mDstUpperLimit
) {
172 *mDst
++ = (UINT8
) (((UINT8
) (Data
>> 0x18)) & 0xff);
177 Allocate memory spaces for data structures used in compression process.
179 @retval EFI_SUCCESS Memory was allocated successfully.
180 @retval EFI_OUT_OF_RESOURCES A memory allocation failed.
187 mText
= AllocateZeroPool (WNDSIZ
* 2 + MAXMATCH
);
188 mLevel
= AllocateZeroPool ((WNDSIZ
+ UINT8_MAX
+ 1) * sizeof (*mLevel
));
189 mChildCount
= AllocateZeroPool ((WNDSIZ
+ UINT8_MAX
+ 1) * sizeof (*mChildCount
));
190 mPosition
= AllocateZeroPool ((WNDSIZ
+ UINT8_MAX
+ 1) * sizeof (*mPosition
));
191 mParent
= AllocateZeroPool (WNDSIZ
* 2 * sizeof (*mParent
));
192 mPrev
= AllocateZeroPool (WNDSIZ
* 2 * sizeof (*mPrev
));
193 mNext
= AllocateZeroPool ((MAX_HASH_VAL
+ 1) * sizeof (*mNext
));
196 mBuf
= AllocateZeroPool (mBufSiz
);
197 while (mBuf
== NULL
) {
198 mBufSiz
= (mBufSiz
/ 10U) * 9U;
199 if (mBufSiz
< 4 * 1024U) {
200 return EFI_OUT_OF_RESOURCES
;
203 mBuf
= AllocateZeroPool (mBufSiz
);
212 Called when compression is completed to free memory previously allocated.
220 SHELL_FREE_NON_NULL (mText
);
221 SHELL_FREE_NON_NULL (mLevel
);
222 SHELL_FREE_NON_NULL (mChildCount
);
223 SHELL_FREE_NON_NULL (mPosition
);
224 SHELL_FREE_NON_NULL (mParent
);
225 SHELL_FREE_NON_NULL (mPrev
);
226 SHELL_FREE_NON_NULL (mNext
);
227 SHELL_FREE_NON_NULL (mBuf
);
231 Initialize String Info Log data structures.
240 SetMem (mLevel
+ WNDSIZ
, (UINT8_MAX
+ 1) * sizeof (UINT8
), 1);
241 SetMem (mPosition
+ WNDSIZ
, (UINT8_MAX
+ 1) * sizeof (NODE
), 0);
243 SetMem (mParent
+ WNDSIZ
, WNDSIZ
* sizeof (NODE
), 0);
246 for (LoopVar1
= 1; LoopVar1
< WNDSIZ
- 1; LoopVar1
++) {
247 mNext
[LoopVar1
] = (NODE
) (LoopVar1
+ 1);
250 mNext
[WNDSIZ
- 1] = NIL
;
251 SetMem (mNext
+ WNDSIZ
* 2, (MAX_HASH_VAL
- WNDSIZ
* 2 + 1) * sizeof (NODE
), 0);
255 Find child node given the parent node and the edge character
257 @param[in] LoopVar6 The parent node.
258 @param[in] LoopVar5 The edge character.
260 @return The child node.
261 @retval NIL(Zero) No child could be found.
272 LoopVar4
= mNext
[HASH (LoopVar6
, LoopVar5
)];
273 mParent
[NIL
] = LoopVar6
; /* sentinel */
274 while (mParent
[LoopVar4
] != LoopVar6
) {
275 LoopVar4
= mNext
[LoopVar4
];
282 Create a new child for a given parent node.
284 @param[in] LoopVar6 The parent node.
285 @param[in] LoopVar5 The edge character.
286 @param[in] LoopVar4 The child node.
299 LoopVar12
= (NODE
) HASH (LoopVar6
, LoopVar5
);
300 LoopVar10
= mNext
[LoopVar12
];
301 mNext
[LoopVar12
] = LoopVar4
;
302 mNext
[LoopVar4
] = LoopVar10
;
303 mPrev
[LoopVar10
] = LoopVar4
;
304 mPrev
[LoopVar4
] = LoopVar12
;
305 mParent
[LoopVar4
] = LoopVar6
;
306 mChildCount
[LoopVar6
]++;
312 @param[in] Old The node to split.
325 mChildCount
[New
] = 0;
326 LoopVar10
= mPrev
[Old
];
327 mPrev
[New
] = LoopVar10
;
328 mNext
[LoopVar10
] = New
;
329 LoopVar10
= mNext
[Old
];
330 mNext
[New
] = LoopVar10
;
331 mPrev
[LoopVar10
] = New
;
332 mParent
[New
] = mParent
[Old
];
333 mLevel
[New
] = (UINT8
) mMatchLen
;
334 mPosition
[New
] = mPos
;
335 MakeChild (New
, mText
[mMatchPos
+ mMatchLen
], Old
);
336 MakeChild (New
, mText
[mPos
+ mMatchLen
], mPos
);
340 Insert string info for current position into the String Info Log.
359 if (mMatchLen
>= 4) {
361 // We have just got a long match, the target tree
362 // can be located by MatchPos + 1. Travese the tree
363 // from bottom up to get to a proper starting point.
364 // The usage of PERC_FLAG ensures proper node deletion
365 // in DeleteNode() later.
368 LoopVar4
= (NODE
) ((mMatchPos
+ 1) | WNDSIZ
);
369 LoopVar6
= mParent
[LoopVar4
];
370 while (LoopVar6
== NIL
) {
371 LoopVar4
= mNext
[LoopVar4
];
372 LoopVar6
= mParent
[LoopVar4
];
375 while (mLevel
[LoopVar6
] >= mMatchLen
) {
377 LoopVar6
= mParent
[LoopVar6
];
380 LoopVar10
= LoopVar6
;
381 while (mPosition
[LoopVar10
] < 0) {
382 mPosition
[LoopVar10
] = mPos
;
383 LoopVar10
= mParent
[LoopVar10
];
386 if (LoopVar10
< WNDSIZ
) {
387 mPosition
[LoopVar10
] = (NODE
) (mPos
| PERC_FLAG
);
391 // Locate the target tree
393 LoopVar6
= (NODE
) (mText
[mPos
] + WNDSIZ
);
394 LoopVar5
= mText
[mPos
+ 1];
395 LoopVar4
= Child (LoopVar6
, LoopVar5
);
396 if (LoopVar4
== NIL
) {
397 MakeChild (LoopVar6
, LoopVar5
, mPos
);
405 // Traverse down the tree to find a match.
406 // Update Position value along the route.
407 // Node split or creation is involved.
410 if (LoopVar4
>= WNDSIZ
) {
412 mMatchPos
= LoopVar4
;
414 LoopVar2
= mLevel
[LoopVar4
];
415 mMatchPos
= (NODE
) (mPosition
[LoopVar4
] & ~PERC_FLAG
);
418 if (mMatchPos
>= mPos
) {
422 TempString3
= &mText
[mPos
+ mMatchLen
];
423 TempString2
= &mText
[mMatchPos
+ mMatchLen
];
424 while (mMatchLen
< LoopVar2
) {
425 if (*TempString3
!= *TempString2
) {
435 if (mMatchLen
>= MAXMATCH
) {
439 mPosition
[LoopVar4
] = mPos
;
441 LoopVar4
= Child (LoopVar6
, *TempString3
);
442 if (LoopVar4
== NIL
) {
443 MakeChild (LoopVar6
, *TempString3
, mPos
);
450 LoopVar10
= mPrev
[LoopVar4
];
451 mPrev
[mPos
] = LoopVar10
;
452 mNext
[LoopVar10
] = mPos
;
453 LoopVar10
= mNext
[LoopVar4
];
454 mNext
[mPos
] = LoopVar10
;
455 mPrev
[LoopVar10
] = mPos
;
456 mParent
[mPos
] = LoopVar6
;
457 mParent
[LoopVar4
] = NIL
;
460 // Special usage of 'next'
462 mNext
[LoopVar4
] = mPos
;
467 Delete outdated string info. (The Usage of PERC_FLAG
468 ensures a clean deletion).
486 if (mParent
[mPos
] == NIL
) {
490 LoopVar4
= mPrev
[mPos
];
491 LoopVar11
= mNext
[mPos
];
492 mNext
[LoopVar4
] = LoopVar11
;
493 mPrev
[LoopVar11
] = LoopVar4
;
494 LoopVar4
= mParent
[mPos
];
496 if (LoopVar4
>= WNDSIZ
) {
500 mChildCount
[LoopVar4
]--;
501 if (mChildCount
[LoopVar4
] > 1) {
505 LoopVar10
= (NODE
) (mPosition
[LoopVar4
] & ~PERC_FLAG
);
506 if (LoopVar10
>= mPos
) {
510 LoopVar11
= LoopVar10
;
511 LoopVar6
= mParent
[LoopVar4
];
512 LoopVar9
= mPosition
[LoopVar6
];
513 while ((LoopVar9
& PERC_FLAG
) != 0){
514 LoopVar9
&= ~PERC_FLAG
;
515 if (LoopVar9
>= mPos
) {
519 if (LoopVar9
> LoopVar11
) {
520 LoopVar11
= LoopVar9
;
523 mPosition
[LoopVar6
] = (NODE
) (LoopVar11
| WNDSIZ
);
524 LoopVar6
= mParent
[LoopVar6
];
525 LoopVar9
= mPosition
[LoopVar6
];
528 if (LoopVar6
< WNDSIZ
) {
529 if (LoopVar9
>= mPos
) {
533 if (LoopVar9
> LoopVar11
) {
534 LoopVar11
= LoopVar9
;
537 mPosition
[LoopVar6
] = (NODE
) (LoopVar11
| WNDSIZ
| PERC_FLAG
);
540 LoopVar11
= Child (LoopVar4
, mText
[LoopVar10
+ mLevel
[LoopVar4
]]);
541 LoopVar10
= mPrev
[LoopVar11
];
542 LoopVar9
= mNext
[LoopVar11
];
543 mNext
[LoopVar10
] = LoopVar9
;
544 mPrev
[LoopVar9
] = LoopVar10
;
545 LoopVar10
= mPrev
[LoopVar4
];
546 mNext
[LoopVar10
] = LoopVar11
;
547 mPrev
[LoopVar11
] = LoopVar10
;
548 LoopVar10
= mNext
[LoopVar4
];
549 mPrev
[LoopVar10
] = LoopVar11
;
550 mNext
[LoopVar11
] = LoopVar10
;
551 mParent
[LoopVar11
] = mParent
[LoopVar4
];
552 mParent
[LoopVar4
] = NIL
;
553 mNext
[LoopVar4
] = mAvail
;
560 @param[out] LoopVar7 The buffer to hold the data.
561 @param[in] LoopVar8 The number of bytes to read.
563 @return The number of bytes actually read.
573 for (LoopVar1
= 0; mSrc
< mSrcUpperLimit
&& LoopVar1
< LoopVar8
; LoopVar1
++) {
574 *LoopVar7
++ = *mSrc
++;
579 LoopVar7
-= LoopVar8
;
580 mOrigSize
+= LoopVar8
;
582 while (LoopVar1
>= 0) {
583 UPDATE_CRC (*LoopVar7
++);
591 Advance the current position (read in new data if needed).
592 Delete outdated string info. Find a match string for current position.
594 @retval TRUE The operation was successful.
595 @retval FALSE The operation failed due to insufficient memory.
607 if (mPos
== WNDSIZ
* 2) {
608 Temp
= AllocateZeroPool (WNDSIZ
+ MAXMATCH
);
612 CopyMem (Temp
, &mText
[WNDSIZ
], WNDSIZ
+ MAXMATCH
);
613 CopyMem (&mText
[0], Temp
, WNDSIZ
+ MAXMATCH
);
615 LoopVar8
= FreadCrc (&mText
[WNDSIZ
+ MAXMATCH
], WNDSIZ
);
616 mRemainder
+= LoopVar8
;
627 Send entry LoopVar1 down the queue.
629 @param[in] LoopVar1 The index of the item to move.
641 // priority queue: send i-th entry down heap
645 while (LoopVar1
<= mHeapSize
) {
646 if (LoopVar1
< mHeapSize
&& mFreq
[mHeap
[LoopVar1
]] > mFreq
[mHeap
[LoopVar1
+ 1]]) {
650 if (mFreq
[LoopVar2
] <= mFreq
[mHeap
[LoopVar1
]]) {
654 mHeap
[i
] = mHeap
[LoopVar1
];
659 mHeap
[i
] = (INT16
) LoopVar2
;
663 Count the number of each code length for a Huffman tree.
665 @param[in] LoopVar1 The top node.
672 if (LoopVar1
< mTempInt32
) {
673 mLenCnt
[(mHuffmanDepth
< 16) ? mHuffmanDepth
: 16]++;
676 CountLen (mLeft
[LoopVar1
]);
677 CountLen (mRight
[LoopVar1
]);
683 Create code length array for a Huffman tree.
685 @param[in] Root The root of the tree.
697 for (LoopVar1
= 0; LoopVar1
<= 16; LoopVar1
++) {
698 mLenCnt
[LoopVar1
] = 0;
704 // Adjust the length count array so that
705 // no code will be generated longer than its designated length
708 for (LoopVar1
= 16; LoopVar1
> 0; LoopVar1
--) {
709 Cum
+= mLenCnt
[LoopVar1
] << (16 - LoopVar1
);
712 while (Cum
!= (1U << 16)) {
714 for (LoopVar1
= 15; LoopVar1
> 0; LoopVar1
--) {
715 if (mLenCnt
[LoopVar1
] != 0) {
717 mLenCnt
[LoopVar1
+ 1] += 2;
725 for (LoopVar1
= 16; LoopVar1
> 0; LoopVar1
--) {
726 LoopVar2
= mLenCnt
[LoopVar1
];
728 while (LoopVar2
>= 0) {
729 mLen
[*mSortPtr
++] = (UINT8
) LoopVar1
;
736 Assign code to each symbol based on the code length array.
738 @param[in] LoopVar8 The number of symbols.
739 @param[in] Len The code length array.
740 @param[out] Code The stores codes for each symbol.
753 for (LoopVar1
= 1; LoopVar1
<= 16; LoopVar1
++) {
754 Start
[LoopVar1
+ 1] = (UINT16
) ((Start
[LoopVar1
] + mLenCnt
[LoopVar1
]) << 1);
757 for (LoopVar1
= 0; LoopVar1
< LoopVar8
; LoopVar1
++) {
758 Code
[LoopVar1
] = Start
[Len
[LoopVar1
]]++;
763 Generates Huffman codes given a frequency distribution of symbols.
765 @param[in] NParm The number of symbols.
766 @param[in] FreqParm The frequency of each symbol.
767 @param[out] LenParm The code length for each symbol.
768 @param[out] CodeParm The code for each symbol.
770 @return The root of the Huffman tree.
775 IN UINT16 FreqParm
[ ],
776 OUT UINT8 LenParm
[ ],
777 OUT UINT16 CodeParm
[ ]
789 // make tree, calculate len[], return root
797 for (LoopVar1
= 0; LoopVar1
< mTempInt32
; LoopVar1
++) {
799 if ((mFreq
[LoopVar1
]) != 0) {
801 mHeap
[mHeapSize
] = (INT16
) LoopVar1
;
806 CodeParm
[mHeap
[1]] = 0;
810 for (LoopVar1
= mHeapSize
/ 2; LoopVar1
>= 1; LoopVar1
--) {
812 // make priority queue
820 if (LoopVar1
< mTempInt32
) {
821 *mSortPtr
++ = (UINT16
) LoopVar1
;
824 mHeap
[1] = mHeap
[mHeapSize
--];
827 if (LoopVar2
< mTempInt32
) {
828 *mSortPtr
++ = (UINT16
) LoopVar2
;
832 mFreq
[LoopVar3
] = (UINT16
) (mFreq
[LoopVar1
] + mFreq
[LoopVar2
]);
833 mHeap
[1] = (INT16
) LoopVar3
;
835 mLeft
[LoopVar3
] = (UINT16
) LoopVar1
;
836 mRight
[LoopVar3
] = (UINT16
) LoopVar2
;
837 } while (mHeapSize
> 1);
841 MakeCode (NParm
, LenParm
, CodeParm
);
850 Outputs rightmost LoopVar8 bits of x
852 @param[in] LoopVar8 The rightmost LoopVar8 bits of the data is used.
853 @param[in] x The data.
863 if (LoopVar8
< mBitCount
) {
864 mSubBitBuf
|= x
<< (mBitCount
-= LoopVar8
);
867 Temp
= (UINT8
)(mSubBitBuf
| (x
>> (LoopVar8
-= mBitCount
)));
868 if (mDst
< mDstUpperLimit
) {
873 if (LoopVar8
< UINT8_BIT
) {
874 mSubBitBuf
= x
<< (mBitCount
= UINT8_BIT
- LoopVar8
);
877 Temp
= (UINT8
)(x
>> (LoopVar8
- UINT8_BIT
));
878 if (mDst
< mDstUpperLimit
) {
883 mSubBitBuf
= x
<< (mBitCount
= 2 * UINT8_BIT
- LoopVar8
);
889 Encode a signed 32 bit number.
891 @param[in] LoopVar5 The number to encode.
898 PutBits (mCLen
[LoopVar5
], mCCode
[LoopVar5
]);
902 Encode a unsigned 32 bit number.
904 @param[in] LoopVar7 The number to encode.
917 while (LoopVar6
!= 0) {
922 PutBits (mPTLen
[LoopVar5
], mPTCode
[LoopVar5
]);
924 PutBits(LoopVar5
- 1, LoopVar7
& (0xFFFFU
>> (17 - LoopVar5
)));
929 Count the frequencies for the Extra Set.
945 for (LoopVar1
= 0; LoopVar1
< NT
; LoopVar1
++) {
946 mTFreq
[LoopVar1
] = 0;
950 while (LoopVar8
> 0 && mCLen
[LoopVar8
- 1] == 0) {
955 while (LoopVar1
< LoopVar8
) {
956 LoopVar3
= mCLen
[LoopVar1
++];
959 while (LoopVar1
< LoopVar8
&& mCLen
[LoopVar1
] == 0) {
965 mTFreq
[0] = (UINT16
) (mTFreq
[0] + Count
);
966 } else if (Count
<= 18) {
968 } else if (Count
== 19) {
975 ASSERT((LoopVar3
+2)<(2 * NT
- 1));
976 mTFreq
[LoopVar3
+ 2]++;
982 Outputs the code length array for the Extra Set or the Position Set.
984 @param[in] LoopVar8 The number of symbols.
985 @param[in] nbit The number of bits needed to represent 'LoopVar8'.
986 @param[in] Special The special symbol that needs to be take care of.
1000 while (LoopVar8
> 0 && mPTLen
[LoopVar8
- 1] == 0) {
1004 PutBits (nbit
, LoopVar8
);
1006 while (LoopVar1
< LoopVar8
) {
1007 LoopVar3
= mPTLen
[LoopVar1
++];
1008 if (LoopVar3
<= 6) {
1009 PutBits (3, LoopVar3
);
1011 PutBits (LoopVar3
- 3, (1U << (LoopVar3
- 3)) - 2);
1014 if (LoopVar1
== Special
) {
1015 while (LoopVar1
< 6 && mPTLen
[LoopVar1
] == 0) {
1019 PutBits (2, (LoopVar1
- 3) & 3);
1025 Outputs the code length array for Char&Length Set.
1041 while (LoopVar8
> 0 && mCLen
[LoopVar8
- 1] == 0) {
1045 PutBits (CBIT
, LoopVar8
);
1047 while (LoopVar1
< LoopVar8
) {
1048 LoopVar3
= mCLen
[LoopVar1
++];
1049 if (LoopVar3
== 0) {
1051 while (LoopVar1
< LoopVar8
&& mCLen
[LoopVar1
] == 0) {
1057 for (LoopVar3
= 0; LoopVar3
< Count
; LoopVar3
++) {
1058 PutBits (mPTLen
[0], mPTCode
[0]);
1060 } else if (Count
<= 18) {
1061 PutBits (mPTLen
[1], mPTCode
[1]);
1062 PutBits (4, Count
- 3);
1063 } else if (Count
== 19) {
1064 PutBits (mPTLen
[0], mPTCode
[0]);
1065 PutBits (mPTLen
[1], mPTCode
[1]);
1068 PutBits (mPTLen
[2], mPTCode
[2]);
1069 PutBits (CBIT
, Count
- 20);
1072 ASSERT((LoopVar3
+2)<NPT
);
1073 PutBits (mPTLen
[LoopVar3
+ 2], mPTCode
[LoopVar3
+ 2]);
1079 Huffman code the block and output it.
1100 Root
= MakeTree (NC
, mCFreq
, mCLen
, mCCode
);
1101 Size
= mCFreq
[Root
];
1105 Root
= MakeTree (NT
, mTFreq
, mPTLen
, mPTCode
);
1107 WritePTLen (NT
, TBIT
, 3);
1110 PutBits (TBIT
, Root
);
1118 PutBits (CBIT
, Root
);
1121 Root
= MakeTree (NP
, mPFreq
, mPTLen
, mPTCode
);
1123 WritePTLen (NP
, PBIT
, -1);
1126 PutBits (PBIT
, Root
);
1130 for (LoopVar1
= 0; LoopVar1
< Size
; LoopVar1
++) {
1131 if (LoopVar1
% UINT8_BIT
== 0) {
1132 Flags
= mBuf
[Pos
++];
1136 if ((Flags
& (1U << (UINT8_BIT
- 1))) != 0){
1137 EncodeC(mBuf
[Pos
++] + (1U << UINT8_BIT
));
1138 LoopVar3
= mBuf
[Pos
++] << UINT8_BIT
;
1139 LoopVar3
+= mBuf
[Pos
++];
1143 EncodeC (mBuf
[Pos
++]);
1147 SetMem (mCFreq
, NC
* sizeof (UINT16
), 0);
1148 SetMem (mPFreq
, NP
* sizeof (UINT16
), 0);
1152 Start the huffman encoding.
1160 SetMem (mCFreq
, NC
* sizeof (UINT16
), 0);
1161 SetMem (mPFreq
, NP
* sizeof (UINT16
), 0);
1163 mOutputPos
= mOutputMask
= 0;
1165 mBitCount
= UINT8_BIT
;
1170 Outputs an Original Character or a Pointer.
1172 @param[in] LoopVar5 The original character or the 'String Length' element of
1174 @param[in] LoopVar7 The 'Position' field of a Pointer.
1184 if ((mOutputMask
>>= 1) == 0) {
1185 mOutputMask
= 1U << (UINT8_BIT
- 1);
1186 if (mOutputPos
>= mBufSiz
- 3 * UINT8_BIT
) {
1191 CPos
= mOutputPos
++;
1194 mBuf
[mOutputPos
++] = (UINT8
) LoopVar5
;
1196 if (LoopVar5
>= (1U << UINT8_BIT
)) {
1197 mBuf
[CPos
] = (UINT8
)(mBuf
[CPos
]|mOutputMask
);
1198 mBuf
[mOutputPos
++] = (UINT8
)(LoopVar7
>> UINT8_BIT
);
1199 mBuf
[mOutputPos
++] = (UINT8
) LoopVar7
;
1201 while (LoopVar7
!=0) {
1210 End the huffman encoding.
1221 // Flush remaining bits
1223 PutBits (UINT8_BIT
- 1, 0);
1227 The main controlling routine for compression process.
1229 @retval EFI_SUCCESS The compression is successful.
1230 @retval EFI_OUT_0F_RESOURCES Not enough memory for compression process.
1241 Status
= AllocateMemory ();
1242 if (EFI_ERROR (Status
)) {
1251 mRemainder
= FreadCrc (&mText
[WNDSIZ
], WNDSIZ
+ MAXMATCH
);
1256 if (mMatchLen
> mRemainder
) {
1257 mMatchLen
= mRemainder
;
1260 while (mRemainder
> 0) {
1261 LastMatchLen
= mMatchLen
;
1262 LastMatchPos
= mMatchPos
;
1263 if (!GetNextMatch ()) {
1264 Status
= EFI_OUT_OF_RESOURCES
;
1266 if (mMatchLen
> mRemainder
) {
1267 mMatchLen
= mRemainder
;
1270 if (mMatchLen
> LastMatchLen
|| LastMatchLen
< THRESHOLD
) {
1272 // Not enough benefits are gained by outputting a pointer,
1273 // so just output the original character
1275 CompressOutput(mText
[mPos
- 1], 0);
1278 // Outputting a pointer is beneficial enough, do it.
1281 CompressOutput(LastMatchLen
+ (UINT8_MAX
+ 1 - THRESHOLD
),
1282 (mPos
- LastMatchPos
- 2) & (WNDSIZ
- 1));
1284 while (LastMatchLen
> 0) {
1285 if (!GetNextMatch ()) {
1286 Status
= EFI_OUT_OF_RESOURCES
;
1291 if (mMatchLen
> mRemainder
) {
1292 mMatchLen
= mRemainder
;
1303 The compression routine.
1305 @param[in] SrcBuffer The buffer containing the source data.
1306 @param[in] SrcSize Number of bytes in SrcBuffer.
1307 @param[in] DstBuffer The buffer to put the compressed image in.
1308 @param[in, out] DstSize On input the size (in bytes) of DstBuffer, on
1309 return the number of bytes placed in DstBuffer.
1311 @retval EFI_SUCCESS The compression was sucessful.
1312 @retval EFI_BUFFER_TOO_SMALL The buffer was too small. DstSize is required.
1319 IN OUT UINT64
*DstSize
1338 mSrcUpperLimit
= mSrc
+ SrcSize
;
1340 mDstUpperLimit
= mDst
+*DstSize
;
1347 mOrigSize
= mCompSize
= 0;
1354 if (EFI_ERROR (Status
)) {
1355 return EFI_OUT_OF_RESOURCES
;
1358 // Null terminate the compressed data
1360 if (mDst
< mDstUpperLimit
) {
1364 // Fill in compressed size and original size
1367 PutDword (mCompSize
+ 1);
1368 PutDword (mOrigSize
);
1373 if (mCompSize
+ 1 + 8 > *DstSize
) {
1374 *DstSize
= mCompSize
+ 1 + 8;
1375 return EFI_BUFFER_TOO_SMALL
;
1377 *DstSize
= mCompSize
+ 1 + 8;