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 - 2016, 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>
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.
79 STATIC UINT8
*mSrcUpperLimit
;
80 STATIC UINT8
*mDstUpperLimit
;
84 STATIC UINT8
*mChildCount
;
86 STATIC UINT8 mCLen
[NC
];
87 STATIC UINT8 mPTLen
[NPT
];
89 STATIC INT16 mHeap
[NC
+ 1];
90 STATIC INT32 mRemainder
;
91 STATIC INT32 mMatchLen
;
92 STATIC INT32 mBitCount
;
93 STATIC INT32 mHeapSize
;
94 STATIC INT32 mTempInt32
;
95 STATIC UINT32 mBufSiz
= 0;
96 STATIC UINT32 mOutputPos
;
97 STATIC UINT32 mOutputMask
;
98 STATIC UINT32 mSubBitBuf
;
100 STATIC UINT32 mCompSize
;
101 STATIC UINT32 mOrigSize
;
103 STATIC UINT16
*mFreq
;
104 STATIC UINT16
*mSortPtr
;
105 STATIC UINT16 mLenCnt
[17];
106 STATIC UINT16 mLeft
[2 * NC
- 1];
107 STATIC UINT16 mRight
[2 * NC
- 1];
108 STATIC UINT16 mCrcTable
[UINT8_MAX
+ 1];
109 STATIC UINT16 mCFreq
[2 * NC
- 1];
110 STATIC UINT16 mCCode
[NC
];
111 STATIC UINT16 mPFreq
[2 * NP
- 1];
112 STATIC UINT16 mPTCode
[NPT
];
113 STATIC UINT16 mTFreq
[2 * NT
- 1];
116 STATIC NODE mMatchPos
;
118 STATIC NODE
*mPosition
;
119 STATIC NODE
*mParent
;
121 STATIC NODE
*mNext
= NULL
;
122 INT32 mHuffmanDepth
= 0;
139 for (LoopVar1
= 0; LoopVar1
<= UINT8_MAX
; LoopVar1
++) {
141 for (LoopVar2
= 0; LoopVar2
< UINT8_BIT
; LoopVar2
++) {
142 if ((LoopVar4
& 1) != 0) {
143 LoopVar4
= (LoopVar4
>> 1) ^ CRCPOLY
;
149 mCrcTable
[LoopVar1
] = (UINT16
) LoopVar4
;
154 Put a dword to output stream
156 @param[in] Data The dword to put.
163 if (mDst
< mDstUpperLimit
) {
164 *mDst
++ = (UINT8
) (((UINT8
) (Data
)) & 0xff);
167 if (mDst
< mDstUpperLimit
) {
168 *mDst
++ = (UINT8
) (((UINT8
) (Data
>> 0x08)) & 0xff);
171 if (mDst
< mDstUpperLimit
) {
172 *mDst
++ = (UINT8
) (((UINT8
) (Data
>> 0x10)) & 0xff);
175 if (mDst
< mDstUpperLimit
) {
176 *mDst
++ = (UINT8
) (((UINT8
) (Data
>> 0x18)) & 0xff);
181 Allocate memory spaces for data structures used in compression process.
183 @retval EFI_SUCCESS Memory was allocated successfully.
184 @retval EFI_OUT_OF_RESOURCES A memory allocation failed.
191 mText
= AllocateZeroPool (WNDSIZ
* 2 + MAXMATCH
);
192 mLevel
= AllocateZeroPool ((WNDSIZ
+ UINT8_MAX
+ 1) * sizeof (*mLevel
));
193 mChildCount
= AllocateZeroPool ((WNDSIZ
+ UINT8_MAX
+ 1) * sizeof (*mChildCount
));
194 mPosition
= AllocateZeroPool ((WNDSIZ
+ UINT8_MAX
+ 1) * sizeof (*mPosition
));
195 mParent
= AllocateZeroPool (WNDSIZ
* 2 * sizeof (*mParent
));
196 mPrev
= AllocateZeroPool (WNDSIZ
* 2 * sizeof (*mPrev
));
197 mNext
= AllocateZeroPool ((MAX_HASH_VAL
+ 1) * sizeof (*mNext
));
200 mBuf
= AllocateZeroPool (mBufSiz
);
201 while (mBuf
== NULL
) {
202 mBufSiz
= (mBufSiz
/ 10U) * 9U;
203 if (mBufSiz
< 4 * 1024U) {
204 return EFI_OUT_OF_RESOURCES
;
207 mBuf
= AllocateZeroPool (mBufSiz
);
216 Called when compression is completed to free memory previously allocated.
224 SHELL_FREE_NON_NULL (mText
);
225 SHELL_FREE_NON_NULL (mLevel
);
226 SHELL_FREE_NON_NULL (mChildCount
);
227 SHELL_FREE_NON_NULL (mPosition
);
228 SHELL_FREE_NON_NULL (mParent
);
229 SHELL_FREE_NON_NULL (mPrev
);
230 SHELL_FREE_NON_NULL (mNext
);
231 SHELL_FREE_NON_NULL (mBuf
);
235 Initialize String Info Log data structures.
244 SetMem (mLevel
+ WNDSIZ
, (UINT8_MAX
+ 1) * sizeof (UINT8
), 1);
245 SetMem (mPosition
+ WNDSIZ
, (UINT8_MAX
+ 1) * sizeof (NODE
), 0);
247 SetMem (mParent
+ WNDSIZ
, WNDSIZ
* sizeof (NODE
), 0);
250 for (LoopVar1
= 1; LoopVar1
< WNDSIZ
- 1; LoopVar1
++) {
251 mNext
[LoopVar1
] = (NODE
) (LoopVar1
+ 1);
254 mNext
[WNDSIZ
- 1] = NIL
;
255 SetMem (mNext
+ WNDSIZ
* 2, (MAX_HASH_VAL
- WNDSIZ
* 2 + 1) * sizeof (NODE
), 0);
259 Find child node given the parent node and the edge character
261 @param[in] LoopVar6 The parent node.
262 @param[in] LoopVar5 The edge character.
264 @return The child node.
265 @retval NIL(Zero) No child could be found.
276 LoopVar4
= mNext
[HASH (LoopVar6
, LoopVar5
)];
277 mParent
[NIL
] = LoopVar6
; /* sentinel */
278 while (mParent
[LoopVar4
] != LoopVar6
) {
279 LoopVar4
= mNext
[LoopVar4
];
286 Create a new child for a given parent node.
288 @param[in] LoopVar6 The parent node.
289 @param[in] LoopVar5 The edge character.
290 @param[in] LoopVar4 The child node.
303 LoopVar12
= (NODE
) HASH (LoopVar6
, LoopVar5
);
304 LoopVar10
= mNext
[LoopVar12
];
305 mNext
[LoopVar12
] = LoopVar4
;
306 mNext
[LoopVar4
] = LoopVar10
;
307 mPrev
[LoopVar10
] = LoopVar4
;
308 mPrev
[LoopVar4
] = LoopVar12
;
309 mParent
[LoopVar4
] = LoopVar6
;
310 mChildCount
[LoopVar6
]++;
316 @param[in] Old The node to split.
329 mChildCount
[New
] = 0;
330 LoopVar10
= mPrev
[Old
];
331 mPrev
[New
] = LoopVar10
;
332 mNext
[LoopVar10
] = New
;
333 LoopVar10
= mNext
[Old
];
334 mNext
[New
] = LoopVar10
;
335 mPrev
[LoopVar10
] = New
;
336 mParent
[New
] = mParent
[Old
];
337 mLevel
[New
] = (UINT8
) mMatchLen
;
338 mPosition
[New
] = mPos
;
339 MakeChild (New
, mText
[mMatchPos
+ mMatchLen
], Old
);
340 MakeChild (New
, mText
[mPos
+ mMatchLen
], mPos
);
344 Insert string info for current position into the String Info Log.
363 if (mMatchLen
>= 4) {
365 // We have just got a long match, the target tree
366 // can be located by MatchPos + 1. Travese the tree
367 // from bottom up to get to a proper starting point.
368 // The usage of PERC_FLAG ensures proper node deletion
369 // in DeleteNode() later.
372 LoopVar4
= (NODE
) ((mMatchPos
+ 1) | WNDSIZ
);
373 LoopVar6
= mParent
[LoopVar4
];
374 while (LoopVar6
== NIL
) {
375 LoopVar4
= mNext
[LoopVar4
];
376 LoopVar6
= mParent
[LoopVar4
];
379 while (mLevel
[LoopVar6
] >= mMatchLen
) {
381 LoopVar6
= mParent
[LoopVar6
];
384 LoopVar10
= LoopVar6
;
385 while (mPosition
[LoopVar10
] < 0) {
386 mPosition
[LoopVar10
] = mPos
;
387 LoopVar10
= mParent
[LoopVar10
];
390 if (LoopVar10
< WNDSIZ
) {
391 mPosition
[LoopVar10
] = (NODE
) (mPos
| PERC_FLAG
);
395 // Locate the target tree
397 LoopVar6
= (NODE
) (mText
[mPos
] + WNDSIZ
);
398 LoopVar5
= mText
[mPos
+ 1];
399 LoopVar4
= Child (LoopVar6
, LoopVar5
);
400 if (LoopVar4
== NIL
) {
401 MakeChild (LoopVar6
, LoopVar5
, mPos
);
409 // Traverse down the tree to find a match.
410 // Update Position value along the route.
411 // Node split or creation is involved.
414 if (LoopVar4
>= WNDSIZ
) {
416 mMatchPos
= LoopVar4
;
418 LoopVar2
= mLevel
[LoopVar4
];
419 mMatchPos
= (NODE
) (mPosition
[LoopVar4
] & ~PERC_FLAG
);
422 if (mMatchPos
>= mPos
) {
426 TempString3
= &mText
[mPos
+ mMatchLen
];
427 TempString2
= &mText
[mMatchPos
+ mMatchLen
];
428 while (mMatchLen
< LoopVar2
) {
429 if (*TempString3
!= *TempString2
) {
439 if (mMatchLen
>= MAXMATCH
) {
443 mPosition
[LoopVar4
] = mPos
;
445 LoopVar4
= Child (LoopVar6
, *TempString3
);
446 if (LoopVar4
== NIL
) {
447 MakeChild (LoopVar6
, *TempString3
, mPos
);
454 LoopVar10
= mPrev
[LoopVar4
];
455 mPrev
[mPos
] = LoopVar10
;
456 mNext
[LoopVar10
] = mPos
;
457 LoopVar10
= mNext
[LoopVar4
];
458 mNext
[mPos
] = LoopVar10
;
459 mPrev
[LoopVar10
] = mPos
;
460 mParent
[mPos
] = LoopVar6
;
461 mParent
[LoopVar4
] = NIL
;
464 // Special usage of 'next'
466 mNext
[LoopVar4
] = mPos
;
471 Delete outdated string info. (The Usage of PERC_FLAG
472 ensures a clean deletion).
490 if (mParent
[mPos
] == NIL
) {
494 LoopVar4
= mPrev
[mPos
];
495 LoopVar11
= mNext
[mPos
];
496 mNext
[LoopVar4
] = LoopVar11
;
497 mPrev
[LoopVar11
] = LoopVar4
;
498 LoopVar4
= mParent
[mPos
];
500 if (LoopVar4
>= WNDSIZ
) {
504 mChildCount
[LoopVar4
]--;
505 if (mChildCount
[LoopVar4
] > 1) {
509 LoopVar10
= (NODE
) (mPosition
[LoopVar4
] & ~PERC_FLAG
);
510 if (LoopVar10
>= mPos
) {
514 LoopVar11
= LoopVar10
;
515 LoopVar6
= mParent
[LoopVar4
];
516 LoopVar9
= mPosition
[LoopVar6
];
517 while ((LoopVar9
& PERC_FLAG
) != 0){
518 LoopVar9
&= ~PERC_FLAG
;
519 if (LoopVar9
>= mPos
) {
523 if (LoopVar9
> LoopVar11
) {
524 LoopVar11
= LoopVar9
;
527 mPosition
[LoopVar6
] = (NODE
) (LoopVar11
| WNDSIZ
);
528 LoopVar6
= mParent
[LoopVar6
];
529 LoopVar9
= mPosition
[LoopVar6
];
532 if (LoopVar6
< WNDSIZ
) {
533 if (LoopVar9
>= mPos
) {
537 if (LoopVar9
> LoopVar11
) {
538 LoopVar11
= LoopVar9
;
541 mPosition
[LoopVar6
] = (NODE
) (LoopVar11
| WNDSIZ
| PERC_FLAG
);
544 LoopVar11
= Child (LoopVar4
, mText
[LoopVar10
+ mLevel
[LoopVar4
]]);
545 LoopVar10
= mPrev
[LoopVar11
];
546 LoopVar9
= mNext
[LoopVar11
];
547 mNext
[LoopVar10
] = LoopVar9
;
548 mPrev
[LoopVar9
] = LoopVar10
;
549 LoopVar10
= mPrev
[LoopVar4
];
550 mNext
[LoopVar10
] = LoopVar11
;
551 mPrev
[LoopVar11
] = LoopVar10
;
552 LoopVar10
= mNext
[LoopVar4
];
553 mPrev
[LoopVar10
] = LoopVar11
;
554 mNext
[LoopVar11
] = LoopVar10
;
555 mParent
[LoopVar11
] = mParent
[LoopVar4
];
556 mParent
[LoopVar4
] = NIL
;
557 mNext
[LoopVar4
] = mAvail
;
564 @param[out] LoopVar7 The buffer to hold the data.
565 @param[in] LoopVar8 The number of bytes to read.
567 @return The number of bytes actually read.
577 for (LoopVar1
= 0; mSrc
< mSrcUpperLimit
&& LoopVar1
< LoopVar8
; LoopVar1
++) {
578 *LoopVar7
++ = *mSrc
++;
583 LoopVar7
-= LoopVar8
;
584 mOrigSize
+= LoopVar8
;
586 while (LoopVar1
>= 0) {
587 UPDATE_CRC (*LoopVar7
++);
595 Advance the current position (read in new data if needed).
596 Delete outdated string info. Find a match string for current position.
598 @retval TRUE The operation was successful.
599 @retval FALSE The operation failed due to insufficient memory.
611 if (mPos
== WNDSIZ
* 2) {
612 Temp
= AllocateZeroPool (WNDSIZ
+ MAXMATCH
);
616 CopyMem (Temp
, &mText
[WNDSIZ
], WNDSIZ
+ MAXMATCH
);
617 CopyMem (&mText
[0], Temp
, WNDSIZ
+ MAXMATCH
);
619 LoopVar8
= FreadCrc (&mText
[WNDSIZ
+ MAXMATCH
], WNDSIZ
);
620 mRemainder
+= LoopVar8
;
631 Send entry LoopVar1 down the queue.
633 @param[in] LoopVar1 The index of the item to move.
645 // priority queue: send i-th entry down heap
649 while (LoopVar1
<= mHeapSize
) {
650 if (LoopVar1
< mHeapSize
&& mFreq
[mHeap
[LoopVar1
]] > mFreq
[mHeap
[LoopVar1
+ 1]]) {
654 if (mFreq
[LoopVar2
] <= mFreq
[mHeap
[LoopVar1
]]) {
658 mHeap
[i
] = mHeap
[LoopVar1
];
663 mHeap
[i
] = (INT16
) LoopVar2
;
667 Count the number of each code length for a Huffman tree.
669 @param[in] LoopVar1 The top node.
676 if (LoopVar1
< mTempInt32
) {
677 mLenCnt
[(mHuffmanDepth
< 16) ? mHuffmanDepth
: 16]++;
680 CountLen (mLeft
[LoopVar1
]);
681 CountLen (mRight
[LoopVar1
]);
687 Create code length array for a Huffman tree.
689 @param[in] Root The root of the tree.
701 for (LoopVar1
= 0; LoopVar1
<= 16; LoopVar1
++) {
702 mLenCnt
[LoopVar1
] = 0;
708 // Adjust the length count array so that
709 // no code will be generated longer than its designated length
712 for (LoopVar1
= 16; LoopVar1
> 0; LoopVar1
--) {
713 Cum
+= mLenCnt
[LoopVar1
] << (16 - LoopVar1
);
716 while (Cum
!= (1U << 16)) {
718 for (LoopVar1
= 15; LoopVar1
> 0; LoopVar1
--) {
719 if (mLenCnt
[LoopVar1
] != 0) {
721 mLenCnt
[LoopVar1
+ 1] += 2;
729 for (LoopVar1
= 16; LoopVar1
> 0; LoopVar1
--) {
730 LoopVar2
= mLenCnt
[LoopVar1
];
732 while (LoopVar2
>= 0) {
733 mLen
[*mSortPtr
++] = (UINT8
) LoopVar1
;
740 Assign code to each symbol based on the code length array.
742 @param[in] LoopVar8 The number of symbols.
743 @param[in] Len The code length array.
744 @param[out] Code The stores codes for each symbol.
757 for (LoopVar1
= 1; LoopVar1
<= 16; LoopVar1
++) {
758 Start
[LoopVar1
+ 1] = (UINT16
) ((Start
[LoopVar1
] + mLenCnt
[LoopVar1
]) << 1);
761 for (LoopVar1
= 0; LoopVar1
< LoopVar8
; LoopVar1
++) {
762 Code
[LoopVar1
] = Start
[Len
[LoopVar1
]]++;
767 Generates Huffman codes given a frequency distribution of symbols.
769 @param[in] NParm The number of symbols.
770 @param[in] FreqParm The frequency of each symbol.
771 @param[out] LenParm The code length for each symbol.
772 @param[out] CodeParm The code for each symbol.
774 @return The root of the Huffman tree.
779 IN UINT16 FreqParm
[ ],
780 OUT UINT8 LenParm
[ ],
781 OUT UINT16 CodeParm
[ ]
793 // make tree, calculate len[], return root
801 for (LoopVar1
= 0; LoopVar1
< mTempInt32
; LoopVar1
++) {
803 if ((mFreq
[LoopVar1
]) != 0) {
805 mHeap
[mHeapSize
] = (INT16
) LoopVar1
;
810 CodeParm
[mHeap
[1]] = 0;
814 for (LoopVar1
= mHeapSize
/ 2; LoopVar1
>= 1; LoopVar1
--) {
816 // make priority queue
824 if (LoopVar1
< mTempInt32
) {
825 *mSortPtr
++ = (UINT16
) LoopVar1
;
828 mHeap
[1] = mHeap
[mHeapSize
--];
831 if (LoopVar2
< mTempInt32
) {
832 *mSortPtr
++ = (UINT16
) LoopVar2
;
836 mFreq
[LoopVar3
] = (UINT16
) (mFreq
[LoopVar1
] + mFreq
[LoopVar2
]);
837 mHeap
[1] = (INT16
) LoopVar3
;
839 mLeft
[LoopVar3
] = (UINT16
) LoopVar1
;
840 mRight
[LoopVar3
] = (UINT16
) LoopVar2
;
841 } while (mHeapSize
> 1);
845 MakeCode (NParm
, LenParm
, CodeParm
);
854 Outputs rightmost LoopVar8 bits of x
856 @param[in] LoopVar8 The rightmost LoopVar8 bits of the data is used.
857 @param[in] x The data.
867 if (LoopVar8
< mBitCount
) {
868 mSubBitBuf
|= x
<< (mBitCount
-= LoopVar8
);
871 Temp
= (UINT8
)(mSubBitBuf
| (x
>> (LoopVar8
-= mBitCount
)));
872 if (mDst
< mDstUpperLimit
) {
877 if (LoopVar8
< UINT8_BIT
) {
878 mSubBitBuf
= x
<< (mBitCount
= UINT8_BIT
- LoopVar8
);
881 Temp
= (UINT8
)(x
>> (LoopVar8
- UINT8_BIT
));
882 if (mDst
< mDstUpperLimit
) {
887 mSubBitBuf
= x
<< (mBitCount
= 2 * UINT8_BIT
- LoopVar8
);
893 Encode a signed 32 bit number.
895 @param[in] LoopVar5 The number to encode.
902 PutBits (mCLen
[LoopVar5
], mCCode
[LoopVar5
]);
906 Encode a unsigned 32 bit number.
908 @param[in] LoopVar7 The number to encode.
921 while (LoopVar6
!= 0) {
926 PutBits (mPTLen
[LoopVar5
], mPTCode
[LoopVar5
]);
928 PutBits(LoopVar5
- 1, LoopVar7
& (0xFFFFU
>> (17 - LoopVar5
)));
933 Count the frequencies for the Extra Set.
949 for (LoopVar1
= 0; LoopVar1
< NT
; LoopVar1
++) {
950 mTFreq
[LoopVar1
] = 0;
954 while (LoopVar8
> 0 && mCLen
[LoopVar8
- 1] == 0) {
959 while (LoopVar1
< LoopVar8
) {
960 LoopVar3
= mCLen
[LoopVar1
++];
963 while (LoopVar1
< LoopVar8
&& mCLen
[LoopVar1
] == 0) {
969 mTFreq
[0] = (UINT16
) (mTFreq
[0] + Count
);
970 } else if (Count
<= 18) {
972 } else if (Count
== 19) {
979 ASSERT((LoopVar3
+2)<(2 * NT
- 1));
980 mTFreq
[LoopVar3
+ 2]++;
986 Outputs the code length array for the Extra Set or the Position Set.
988 @param[in] LoopVar8 The number of symbols.
989 @param[in] nbit The number of bits needed to represent 'LoopVar8'.
990 @param[in] Special The special symbol that needs to be take care of.
1004 while (LoopVar8
> 0 && mPTLen
[LoopVar8
- 1] == 0) {
1008 PutBits (nbit
, LoopVar8
);
1010 while (LoopVar1
< LoopVar8
) {
1011 LoopVar3
= mPTLen
[LoopVar1
++];
1012 if (LoopVar3
<= 6) {
1013 PutBits (3, LoopVar3
);
1015 PutBits (LoopVar3
- 3, (1U << (LoopVar3
- 3)) - 2);
1018 if (LoopVar1
== Special
) {
1019 while (LoopVar1
< 6 && mPTLen
[LoopVar1
] == 0) {
1023 PutBits (2, (LoopVar1
- 3) & 3);
1029 Outputs the code length array for Char&Length Set.
1045 while (LoopVar8
> 0 && mCLen
[LoopVar8
- 1] == 0) {
1049 PutBits (CBIT
, LoopVar8
);
1051 while (LoopVar1
< LoopVar8
) {
1052 LoopVar3
= mCLen
[LoopVar1
++];
1053 if (LoopVar3
== 0) {
1055 while (LoopVar1
< LoopVar8
&& mCLen
[LoopVar1
] == 0) {
1061 for (LoopVar3
= 0; LoopVar3
< Count
; LoopVar3
++) {
1062 PutBits (mPTLen
[0], mPTCode
[0]);
1064 } else if (Count
<= 18) {
1065 PutBits (mPTLen
[1], mPTCode
[1]);
1066 PutBits (4, Count
- 3);
1067 } else if (Count
== 19) {
1068 PutBits (mPTLen
[0], mPTCode
[0]);
1069 PutBits (mPTLen
[1], mPTCode
[1]);
1072 PutBits (mPTLen
[2], mPTCode
[2]);
1073 PutBits (CBIT
, Count
- 20);
1076 ASSERT((LoopVar3
+2)<NPT
);
1077 PutBits (mPTLen
[LoopVar3
+ 2], mPTCode
[LoopVar3
+ 2]);
1083 Huffman code the block and output it.
1104 Root
= MakeTree (NC
, mCFreq
, mCLen
, mCCode
);
1105 Size
= mCFreq
[Root
];
1109 Root
= MakeTree (NT
, mTFreq
, mPTLen
, mPTCode
);
1111 WritePTLen (NT
, TBIT
, 3);
1114 PutBits (TBIT
, Root
);
1122 PutBits (CBIT
, Root
);
1125 Root
= MakeTree (NP
, mPFreq
, mPTLen
, mPTCode
);
1127 WritePTLen (NP
, PBIT
, -1);
1130 PutBits (PBIT
, Root
);
1134 for (LoopVar1
= 0; LoopVar1
< Size
; LoopVar1
++) {
1135 if (LoopVar1
% UINT8_BIT
== 0) {
1136 Flags
= mBuf
[Pos
++];
1140 if ((Flags
& (1U << (UINT8_BIT
- 1))) != 0){
1141 EncodeC(mBuf
[Pos
++] + (1U << UINT8_BIT
));
1142 LoopVar3
= mBuf
[Pos
++] << UINT8_BIT
;
1143 LoopVar3
+= mBuf
[Pos
++];
1147 EncodeC (mBuf
[Pos
++]);
1151 SetMem (mCFreq
, NC
* sizeof (UINT16
), 0);
1152 SetMem (mPFreq
, NP
* sizeof (UINT16
), 0);
1156 Start the huffman encoding.
1164 SetMem (mCFreq
, NC
* sizeof (UINT16
), 0);
1165 SetMem (mPFreq
, NP
* sizeof (UINT16
), 0);
1167 mOutputPos
= mOutputMask
= 0;
1169 mBitCount
= UINT8_BIT
;
1174 Outputs an Original Character or a Pointer.
1176 @param[in] LoopVar5 The original character or the 'String Length' element of
1178 @param[in] LoopVar7 The 'Position' field of a Pointer.
1188 if ((mOutputMask
>>= 1) == 0) {
1189 mOutputMask
= 1U << (UINT8_BIT
- 1);
1190 if (mOutputPos
>= mBufSiz
- 3 * UINT8_BIT
) {
1195 CPos
= mOutputPos
++;
1198 mBuf
[mOutputPos
++] = (UINT8
) LoopVar5
;
1200 if (LoopVar5
>= (1U << UINT8_BIT
)) {
1201 mBuf
[CPos
] = (UINT8
)(mBuf
[CPos
]|mOutputMask
);
1202 mBuf
[mOutputPos
++] = (UINT8
)(LoopVar7
>> UINT8_BIT
);
1203 mBuf
[mOutputPos
++] = (UINT8
) LoopVar7
;
1205 while (LoopVar7
!=0) {
1214 End the huffman encoding.
1225 // Flush remaining bits
1227 PutBits (UINT8_BIT
- 1, 0);
1231 The main controlling routine for compression process.
1233 @retval EFI_SUCCESS The compression is successful.
1234 @retval EFI_OUT_0F_RESOURCES Not enough memory for compression process.
1245 Status
= AllocateMemory ();
1246 if (EFI_ERROR (Status
)) {
1255 mRemainder
= FreadCrc (&mText
[WNDSIZ
], WNDSIZ
+ MAXMATCH
);
1260 if (mMatchLen
> mRemainder
) {
1261 mMatchLen
= mRemainder
;
1264 while (mRemainder
> 0) {
1265 LastMatchLen
= mMatchLen
;
1266 LastMatchPos
= mMatchPos
;
1267 if (!GetNextMatch ()) {
1268 Status
= EFI_OUT_OF_RESOURCES
;
1270 if (mMatchLen
> mRemainder
) {
1271 mMatchLen
= mRemainder
;
1274 if (mMatchLen
> LastMatchLen
|| LastMatchLen
< THRESHOLD
) {
1276 // Not enough benefits are gained by outputting a pointer,
1277 // so just output the original character
1279 CompressOutput(mText
[mPos
- 1], 0);
1282 // Outputting a pointer is beneficial enough, do it.
1285 CompressOutput(LastMatchLen
+ (UINT8_MAX
+ 1 - THRESHOLD
),
1286 (mPos
- LastMatchPos
- 2) & (WNDSIZ
- 1));
1288 while (LastMatchLen
> 0) {
1289 if (!GetNextMatch ()) {
1290 Status
= EFI_OUT_OF_RESOURCES
;
1295 if (mMatchLen
> mRemainder
) {
1296 mMatchLen
= mRemainder
;
1307 The compression routine.
1309 @param[in] SrcBuffer The buffer containing the source data.
1310 @param[in] SrcSize The number of bytes in SrcBuffer.
1311 @param[in] DstBuffer The buffer to put the compressed image in.
1312 @param[in, out] DstSize On input the size (in bytes) of DstBuffer, on
1313 return the number of bytes placed in DstBuffer.
1315 @retval EFI_SUCCESS The compression was sucessful.
1316 @retval EFI_BUFFER_TOO_SMALL The buffer was too small. DstSize is required.
1323 IN OUT UINT64
*DstSize
1342 mSrcUpperLimit
= mSrc
+ SrcSize
;
1344 mDstUpperLimit
= mDst
+*DstSize
;
1351 mOrigSize
= mCompSize
= 0;
1358 if (EFI_ERROR (Status
)) {
1359 return EFI_OUT_OF_RESOURCES
;
1362 // Null terminate the compressed data
1364 if (mDst
< mDstUpperLimit
) {
1368 // Fill in compressed size and original size
1371 PutDword (mCompSize
+ 1);
1372 PutDword (mOrigSize
);
1377 if (mCompSize
+ 1 + 8 > *DstSize
) {
1378 *DstSize
= mCompSize
+ 1 + 8;
1379 return EFI_BUFFER_TOO_SMALL
;
1381 *DstSize
= mCompSize
+ 1 + 8;